[project @ 2001-09-22 10:53:03 by ken]
[ghc-hetmet.git] / ghc / compiler / codeGen / CgBindery.lhs
1 %
2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
3 %
4 \section[CgBindery]{Utility functions related to doing @CgBindings@}
5
6 \begin{code}
7 module CgBindery (
8         CgBindings, CgIdInfo,
9         StableLoc, VolatileLoc,
10
11         stableAmodeIdInfo, heapIdInfo, newTempAmodeAndIdInfo,
12         letNoEscapeIdInfo, idInfoToAmode,
13
14         addBindC, addBindsC,
15
16         nukeVolatileBinds,
17         nukeDeadBindings,
18
19         bindNewToStack,  rebindToStack,
20         bindNewToNode, bindNewToReg, bindArgsToRegs,
21         bindNewToTemp, bindNewPrimToAmode,
22         getArgAmode, getArgAmodes,
23         getCAddrModeAndInfo, getCAddrMode,
24         getCAddrModeIfVolatile, getVolatileRegs,
25
26         buildLivenessMask, buildContLivenessMask
27     ) where
28
29 #include "HsVersions.h"
30
31 import AbsCSyn
32 import CgMonad
33
34 import CgUsages         ( getHpRelOffset, getSpRelOffset, getRealSp )
35 import CgStackery       ( freeStackSlots )
36 import CLabel           ( mkClosureLabel,
37                           mkBitmapLabel, pprCLabel )
38 import ClosureInfo      ( mkLFImported, mkLFArgument, LambdaFormInfo )
39 import BitSet
40 import PrimRep          ( isFollowableRep, getPrimRepSize )
41 import Id               ( Id, idPrimRep, idType )
42 import Type             ( typePrimRep )
43 import VarEnv
44 import VarSet           ( varSetElems )
45 import Literal          ( Literal )
46 import Maybes           ( catMaybes, maybeToBool )
47 import Name             ( isLocalName, NamedThing(..) )
48 #ifdef DEBUG
49 import PprAbsC          ( pprAmode )
50 #endif
51 import PrimRep          ( PrimRep(..) )
52 import StgSyn           ( StgArg, StgLiveVars, GenStgArg(..), isStgTypeArg )
53 import Unique           ( Unique, Uniquable(..) )
54 import UniqSet          ( elementOfUniqSet )
55 import Util             ( zipWithEqual, sortLt )
56 import Outputable
57 \end{code}
58
59
60 %************************************************************************
61 %*                                                                      *
62 \subsection[Bindery-datatypes]{Data types}
63 %*                                                                      *
64 %************************************************************************
65
66 @(CgBinding a b)@ is a type of finite maps from a to b.
67
68 The assumption used to be that @lookupCgBind@ must get exactly one
69 match.  This is {\em completely wrong} in the case of compiling
70 letrecs (where knot-tying is used).  An initial binding is fed in (and
71 never evaluated); eventually, a correct binding is put into the
72 environment.  So there can be two bindings for a given name.
73
74 \begin{code}
75 type CgBindings = IdEnv CgIdInfo
76
77 data CgIdInfo
78   = MkCgIdInfo  Id      -- Id that this is the info for
79                 VolatileLoc
80                 StableLoc
81                 LambdaFormInfo
82
83 data VolatileLoc
84   = NoVolatileLoc
85   | TempVarLoc  Unique
86
87   | RegLoc      MagicId                 -- in one of the magic registers
88                                         -- (probably {Int,Float,Char,etc}Reg
89
90   | VirHpLoc    VirtualHeapOffset       -- Hp+offset (address of closure)
91
92   | VirNodeLoc  VirtualHeapOffset       -- Cts of offset indirect from Node
93                                         -- ie *(Node+offset)
94 \end{code}
95
96 @StableLoc@ encodes where an Id can be found, used by
97 the @CgBindings@ environment in @CgBindery@.
98
99 \begin{code}
100 data StableLoc
101   = NoStableLoc
102   | VirStkLoc           VirtualSpOffset
103   | LitLoc              Literal
104   | StableAmodeLoc      CAddrMode
105
106 -- these are so StableLoc can be abstract:
107
108 maybeStkLoc (VirStkLoc offset) = Just offset
109 maybeStkLoc _                  = Nothing
110 \end{code}
111
112 %************************************************************************
113 %*                                                                      *
114 \subsection[Bindery-idInfo]{Manipulating IdInfo}
115 %*                                                                      *
116 %************************************************************************
117
118 \begin{code}
119 stableAmodeIdInfo i amode lf_info = MkCgIdInfo i NoVolatileLoc (StableAmodeLoc amode) lf_info
120 heapIdInfo i offset       lf_info = MkCgIdInfo i (VirHpLoc offset) NoStableLoc lf_info
121 tempIdInfo i uniq         lf_info = MkCgIdInfo i (TempVarLoc uniq) NoStableLoc lf_info
122
123 letNoEscapeIdInfo i sp lf_info
124   = MkCgIdInfo i NoVolatileLoc (StableAmodeLoc (CJoinPoint sp)) lf_info
125
126 newTempAmodeAndIdInfo :: Id -> LambdaFormInfo -> (CAddrMode, CgIdInfo)
127
128 newTempAmodeAndIdInfo name lf_info
129   = (temp_amode, temp_idinfo)
130   where
131     uniq        = getUnique name
132     temp_amode  = CTemp uniq (idPrimRep name)
133     temp_idinfo = tempIdInfo name uniq lf_info
134
135 idInfoToAmode :: PrimRep -> CgIdInfo -> FCode CAddrMode
136 idInfoToAmode kind (MkCgIdInfo _ vol stab _) = idInfoPiecesToAmode kind vol stab
137
138 idInfoPiecesToAmode :: PrimRep -> VolatileLoc -> StableLoc -> FCode CAddrMode
139
140 idInfoPiecesToAmode kind (TempVarLoc uniq) stable_loc   = returnFC (CTemp uniq kind)
141 idInfoPiecesToAmode kind (RegLoc magic_id) stable_loc   = returnFC (CReg magic_id)
142
143 idInfoPiecesToAmode kind NoVolatileLoc (LitLoc lit)           = returnFC (CLit lit)
144 idInfoPiecesToAmode kind NoVolatileLoc (StableAmodeLoc amode) = returnFC amode
145
146 idInfoPiecesToAmode kind (VirNodeLoc nd_off) stable_loc
147   = returnFC (CVal (nodeRel nd_off) kind)
148     -- Virtual offsets from Node increase into the closures,
149     -- and so do Node-relative offsets (which we want in the CVal),
150     -- so there is no mucking about to do to the offset.
151
152 idInfoPiecesToAmode kind (VirHpLoc hp_off) stable_loc
153   = getHpRelOffset hp_off `thenFC` \ rel_hp ->
154     returnFC (CAddr rel_hp)
155
156 idInfoPiecesToAmode kind NoVolatileLoc (VirStkLoc i)
157   = getSpRelOffset i `thenFC` \ rel_sp ->
158     returnFC (CVal rel_sp kind)
159
160 #ifdef DEBUG
161 idInfoPiecesToAmode kind NoVolatileLoc NoStableLoc = panic "idInfoPiecesToAmode: no loc"
162 #endif
163 \end{code}
164
165 %************************************************************************
166 %*                                                                      *
167 \subsection[CgMonad-bindery]{Monad things for fiddling with @CgBindings@}
168 %*                                                                      *
169 %************************************************************************
170
171 There are three basic routines, for adding (@addBindC@), modifying
172 (@modifyBindC@) and looking up (@lookupBindC@) bindings.
173
174 A @Id@ is bound to a @(VolatileLoc, StableLoc)@ triple.
175 The name should not already be bound. (nice ASSERT, eh?)
176
177 \begin{code}
178 addBindC :: Id -> CgIdInfo -> Code
179 addBindC name stuff_to_bind = do
180         binds <- getBinds
181         setBinds $ extendVarEnv binds name stuff_to_bind
182
183 addBindsC :: [(Id, CgIdInfo)] -> Code
184 addBindsC new_bindings = do
185         binds <- getBinds
186         let new_binds = foldl (\ binds (name,info) -> extendVarEnv binds name info)
187                 binds
188                 new_bindings
189         setBinds new_binds
190
191 modifyBindC :: Id -> (CgIdInfo -> CgIdInfo) -> Code
192 modifyBindC name mangle_fn = do
193         binds <- getBinds
194         setBinds $ modifyVarEnv mangle_fn binds name
195
196 lookupBindC :: Id -> FCode CgIdInfo
197 lookupBindC name = do
198         static_binds <- getStaticBinds
199         local_binds <- getBinds
200         case (lookupVarEnv local_binds name) of
201                 Nothing -> case (lookupVarEnv static_binds name) of
202                         Nothing -> cgPanic (text "lookupBindC: no info for" <+> ppr name)
203                         Just this -> return this
204                 Just this -> return this
205                         
206 cgPanic :: SDoc -> FCode a
207 cgPanic doc = do
208         static_binds <- getStaticBinds
209         local_binds <- getBinds
210         srt <- getSRTLabel
211         pprPanic "cgPanic"
212                 (vcat [doc,
213                 ptext SLIT("static binds for:"),
214                 vcat [ ppr i | (MkCgIdInfo i _ _ _) <- rngVarEnv static_binds ],
215                 ptext SLIT("local binds for:"),
216                 vcat [ ppr i | (MkCgIdInfo i _ _ _) <- rngVarEnv local_binds ],
217                 ptext SLIT("SRT label") <+> pprCLabel srt
218               ])
219 \end{code}
220
221 %************************************************************************
222 %*                                                                      *
223 \subsection[Bindery-nuke-volatile]{Nuking volatile bindings}
224 %*                                                                      *
225 %************************************************************************
226
227 We sometimes want to nuke all the volatile bindings; we must be sure
228 we don't leave any (NoVolatile, NoStable) binds around...
229
230 \begin{code}
231 nukeVolatileBinds :: CgBindings -> CgBindings
232 nukeVolatileBinds binds
233   = mkVarEnv (foldr keep_if_stable [] (rngVarEnv binds))
234   where
235     keep_if_stable (MkCgIdInfo i _ NoStableLoc entry_info) acc = acc
236     keep_if_stable (MkCgIdInfo i _ stable_loc  entry_info) acc
237       = (i, MkCgIdInfo i NoVolatileLoc stable_loc entry_info) : acc
238 \end{code}
239
240
241 %************************************************************************
242 %*                                                                      *
243 \subsection[lookup-interface]{Interface functions to looking up bindings}
244 %*                                                                      *
245 %************************************************************************
246
247 I {\em think} all looking-up is done through @getCAddrMode(s)@.
248
249 \begin{code}
250 getCAddrModeAndInfo :: Id -> FCode (Id, CAddrMode, LambdaFormInfo)
251
252 getCAddrModeAndInfo id
253   | not (isLocalName name)
254   = returnFC (id, global_amode, mkLFImported id)
255         -- deals with imported or locally defined but externally visible ids
256         -- (CoreTidy makes all these into global names).
257
258   | otherwise = do -- *might* be a nested defn: in any case, it's something whose
259                 -- definition we will know about...
260         (MkCgIdInfo id' volatile_loc stable_loc lf_info) <- lookupBindC id
261         amode <- idInfoPiecesToAmode kind volatile_loc stable_loc
262         return (id', amode, lf_info)
263   where
264     name = getName id
265     global_amode = CLbl (mkClosureLabel name) kind
266     kind = idPrimRep id
267
268 getCAddrMode :: Id -> FCode CAddrMode
269 getCAddrMode name = do
270         (_, amode, _) <- getCAddrModeAndInfo name
271         return amode
272 \end{code}
273
274 \begin{code}
275 getCAddrModeIfVolatile :: Id -> FCode (Maybe CAddrMode)
276 getCAddrModeIfVolatile name
277 --  | toplevelishId name = returnFC Nothing
278 --  | otherwise
279         = do
280         (MkCgIdInfo _ volatile_loc stable_loc lf_info) <- lookupBindC name
281         case stable_loc of
282                 NoStableLoc -> do -- Aha!  So it is volatile!
283                         amode <- idInfoPiecesToAmode (idPrimRep name) volatile_loc NoStableLoc
284                         return $ Just amode
285                 a_stable_loc -> return Nothing
286 \end{code}
287
288 @getVolatileRegs@ gets a set of live variables, and returns a list of
289 all registers on which these variables depend.  These are the regs
290 which must be saved and restored across any C calls.  If a variable is
291 both in a volatile location (depending on a register) {\em and} a
292 stable one (notably, on the stack), we modify the current bindings to
293 forget the volatile one.
294
295 \begin{code}
296 getVolatileRegs :: StgLiveVars -> FCode [MagicId]
297
298 getVolatileRegs vars = do
299         stuff <- mapFCs snaffle_it (varSetElems vars)
300         returnFC $ catMaybes stuff
301         where
302         snaffle_it var = do
303                 (MkCgIdInfo _ volatile_loc stable_loc lf_info) <- lookupBindC var 
304                 let
305                 -- commoned-up code...
306                         consider_reg reg =
307                                 if not (isVolatileReg reg) then
308                                 -- Potentially dies across C calls
309                                 -- For now, that's everything; we leave
310                                 -- it to the save-macros to decide which
311                                 -- regs *really* need to be saved.
312                                         returnFC Nothing
313                                 else
314                                         case stable_loc of
315                                                 NoStableLoc -> returnFC (Just reg) -- got one!
316                                                 is_a_stable_loc -> do
317                                                         -- has both volatile & stable locations;
318                                                         -- force it to rely on the stable location
319                                                         modifyBindC var nuke_vol_bind 
320                                                         return Nothing
321                         in
322                         case volatile_loc of
323                                 RegLoc reg   -> consider_reg reg
324                                 VirHpLoc _   -> consider_reg Hp
325                                 VirNodeLoc _ -> consider_reg node
326                                 non_reg_loc  -> returnFC Nothing
327
328         nuke_vol_bind (MkCgIdInfo i _ stable_loc lf_info)
329                 = MkCgIdInfo i NoVolatileLoc stable_loc lf_info
330 \end{code}
331
332 \begin{code}
333 getArgAmodes :: [StgArg] -> FCode [CAddrMode]
334 getArgAmodes [] = returnFC []
335 getArgAmodes (atom:atoms)
336         | isStgTypeArg atom 
337         = getArgAmodes atoms
338         | otherwise = do
339                 amode <- getArgAmode  atom 
340                 amodes <- getArgAmodes atoms
341                 return ( amode : amodes )
342
343 getArgAmode :: StgArg -> FCode CAddrMode
344
345 getArgAmode (StgVarArg var) = getCAddrMode var          -- The common case
346 getArgAmode (StgLitArg lit) = returnFC (CLit lit)
347 \end{code}
348
349 %************************************************************************
350 %*                                                                      *
351 \subsection[binding-and-rebinding-interface]{Interface functions for binding and re-binding names}
352 %*                                                                      *
353 %************************************************************************
354
355 \begin{code}
356 bindNewToStack :: (Id, VirtualSpOffset) -> Code
357 bindNewToStack (name, offset)
358   = addBindC name info
359   where
360     info = MkCgIdInfo name NoVolatileLoc (VirStkLoc offset) mkLFArgument
361
362 bindNewToNode :: Id -> VirtualHeapOffset -> LambdaFormInfo -> Code
363 bindNewToNode name offset lf_info
364   = addBindC name info
365   where
366     info = MkCgIdInfo name (VirNodeLoc offset) NoStableLoc lf_info
367
368 -- Create a new temporary whose unique is that in the id,
369 -- bind the id to it, and return the addressing mode for the
370 -- temporary.
371 bindNewToTemp :: Id -> FCode CAddrMode
372 bindNewToTemp name
373   = let (temp_amode, id_info) = newTempAmodeAndIdInfo name mkLFArgument
374                 -- This is used only for things we don't know
375                 -- anything about; values returned by a case statement,
376                 -- for example.
377     in do
378                 addBindC name id_info
379                 return temp_amode
380
381 bindNewToReg :: Id -> MagicId -> LambdaFormInfo -> Code
382 bindNewToReg name magic_id lf_info
383   = addBindC name info
384   where
385     info = MkCgIdInfo name (RegLoc magic_id) NoStableLoc lf_info
386
387 bindArgsToRegs :: [Id] -> [MagicId] -> Code
388 bindArgsToRegs args regs
389   = listCs (zipWithEqual "bindArgsToRegs" bind args regs)
390   where
391     arg `bind` reg = bindNewToReg arg reg mkLFArgument
392 \end{code}
393
394 @bindNewPrimToAmode@ works only for certain addressing modes.  Making
395 this work for stack offsets is non-trivial (virt vs. real stack offset
396 difficulties).
397
398 \begin{code}
399 bindNewPrimToAmode :: Id -> CAddrMode -> Code
400 bindNewPrimToAmode name (CReg reg) 
401   = bindNewToReg name reg (panic "bindNewPrimToAmode")
402
403 bindNewPrimToAmode name (CTemp uniq kind)
404   = addBindC name (tempIdInfo name uniq (panic "bindNewPrimToAmode"))
405
406 #ifdef DEBUG
407 bindNewPrimToAmode name amode
408   = pprPanic "bindNew...:" (pprAmode amode)
409 #endif
410 \end{code}
411
412 \begin{code}
413 rebindToStack :: Id -> VirtualSpOffset -> Code
414 rebindToStack name offset
415   = modifyBindC name replace_stable_fn
416   where
417     replace_stable_fn (MkCgIdInfo i vol stab einfo)
418       = MkCgIdInfo i vol (VirStkLoc offset) einfo
419 \end{code}
420
421 %************************************************************************
422 %*                                                                      *
423 \subsection[CgBindery-liveness]{Build a liveness mask for the current stack}
424 %*                                                                      *
425 %************************************************************************
426
427 There are four kinds of things on the stack:
428
429         - pointer variables (bound in the environment)
430         - non-pointer variables (boudn in the environment)
431         - free slots (recorded in the stack free list)
432         - non-pointer data slots (recorded in the stack free list)
433
434 We build up a bitmap of non-pointer slots by looking down the
435 environment for all the non-pointer variables, and merging this with
436 the slots recorded in the stack free list.
437
438 There's a bit of a hack here to do with update frames: since nothing
439 is recorded in either the environment or the stack free list for an
440 update frame, the code below defaults to assuming the slots taken up
441 by an update frame contain pointers.  Furthermore, update frames are
442 always in slots 0-2 at the bottom of the stack.  The bitmap will
443 therefore end at slot 3, which is what we want (the update frame info
444 pointer has its own bitmap to describe the update frame).
445
446 \begin{code}
447 buildLivenessMask 
448         :: Unique               -- unique for for large bitmap label
449         -> VirtualSpOffset      -- offset from which the bitmap should start
450         -> FCode Liveness       -- mask for free/unlifted slots
451
452 buildLivenessMask uniq sp = do  
453
454         -- find all unboxed stack-resident ids
455         binds <- getBinds
456         ((vsp, free, _, _), heap_usage) <- getUsage
457         
458         let unboxed_slots = 
459                 [ (ofs, size) | 
460                 (MkCgIdInfo id _ (VirStkLoc ofs) _) <- rngVarEnv binds,
461                 let rep = idPrimRep id; size = getPrimRepSize rep,
462                 not (isFollowableRep rep),
463                 size > 0
464                 ]       
465                 
466         -- flatten this list into a list of unboxed stack slots
467         let flatten_slots = sortLt (<) 
468                 (foldr (\(ofs,size) r -> [ofs-size+1 .. ofs] ++ r) []
469                       unboxed_slots)
470
471         -- merge in the free slots
472         let all_slots = mergeSlots flatten_slots (map fst free) ++ 
473                     if vsp < sp then [vsp+1 .. sp] else []
474
475         -- recalibrate the list to be sp-relative
476         let rel_slots = reverse (map (sp-) all_slots)
477
478         -- build the bitmap
479         let liveness_mask 
480                = ASSERT(all (>=0) rel_slots 
481                         && rel_slots == sortLt (<) rel_slots) 
482                  (listToLivenessMask rel_slots)
483         
484         livenessToAbsC uniq liveness_mask
485
486 mergeSlots :: [Int] -> [Int] -> [Int]
487 mergeSlots cs [] = cs
488 mergeSlots [] ns = ns
489 mergeSlots (c:cs) (n:ns)
490  = if c < n then
491         c : mergeSlots cs (n:ns)
492    else if c > n then
493         n : mergeSlots (c:cs) ns
494    else
495         panic ("mergeSlots: equal slots: " ++ show (c:cs) ++ show (n:ns))
496
497 listToLivenessMask :: [Int] -> LivenessMask
498 listToLivenessMask []    = []
499 listToLivenessMask slots = 
500    mkBS this : listToLivenessMask (map (\x -> x-32) rest)
501    where (this,rest) = span (<32) slots
502
503 livenessToAbsC :: Unique -> LivenessMask -> FCode Liveness
504 livenessToAbsC uniq mask  =
505         absC (CBitmap lbl mask) `thenC`
506         returnFC (Liveness lbl mask)
507   where lbl = mkBitmapLabel uniq       
508 \end{code}
509
510 In a continuation, we want a liveness mask that starts from just after
511 the return address, which is on the stack at realSp.
512
513 \begin{code}
514 buildContLivenessMask
515         :: Unique
516         -> FCode Liveness
517 buildContLivenessMask uniq = do
518         realSp <- getRealSp
519         buildLivenessMask uniq (realSp-1)
520 \end{code}
521
522 %************************************************************************
523 %*                                                                      *
524 \subsection[CgMonad-deadslots]{Finding dead stack slots}
525 %*                                                                      *
526 %************************************************************************
527
528 nukeDeadBindings does the following:
529
530       - Removes all bindings from the environment other than those
531         for variables in the argument to nukeDeadBindings.
532       - Collects any stack slots so freed, and returns them to the  stack free
533         list.
534       - Moves the virtual stack pointer to point to the topmost used
535         stack locations.
536
537 You can have multi-word slots on the stack (where a Double# used to
538 be, for instance); if dead, such a slot will be reported as *several*
539 offsets (one per word).
540
541 Probably *naughty* to look inside monad...
542
543 \begin{code}
544 nukeDeadBindings :: StgLiveVars  -- All the *live* variables
545                  -> Code
546 nukeDeadBindings live_vars = do
547         binds <- getBinds
548         let (dead_stk_slots, bs') =
549                 dead_slots live_vars 
550                         [] []
551                         [ (i, b) | b@(MkCgIdInfo i _ _ _) <- rngVarEnv binds ]
552         setBinds $ mkVarEnv bs'
553         freeStackSlots dead_stk_slots
554 \end{code}
555
556 Several boring auxiliary functions to do the dirty work.
557
558 \begin{code}
559 dead_slots :: StgLiveVars
560            -> [(Id,CgIdInfo)]
561            -> [VirtualSpOffset]
562            -> [(Id,CgIdInfo)]
563            -> ([VirtualSpOffset], [(Id,CgIdInfo)])
564
565 -- dead_slots carries accumulating parameters for
566 --      filtered bindings, dead slots
567 dead_slots live_vars fbs ds []
568   = (ds, reverse fbs) -- Finished; rm the dups, if any
569
570 dead_slots live_vars fbs ds ((v,i):bs)
571   | v `elementOfUniqSet` live_vars
572     = dead_slots live_vars ((v,i):fbs) ds bs
573           -- Live, so don't record it in dead slots
574           -- Instead keep it in the filtered bindings
575
576   | otherwise
577     = case i of
578         MkCgIdInfo _ _ stable_loc _
579          | is_stk_loc && size > 0 ->
580            dead_slots live_vars fbs ([offset-size+1 .. offset] ++ ds) bs
581          where
582           maybe_stk_loc = maybeStkLoc stable_loc
583           is_stk_loc    = maybeToBool maybe_stk_loc
584           (Just offset) = maybe_stk_loc
585
586         _ -> dead_slots live_vars fbs ds bs
587   where
588
589     size :: Int
590     size = (getPrimRepSize . typePrimRep . idType) v
591
592 \end{code}