[project @ 2001-10-15 16:03:04 by simonpj]
[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, seqMaybe )
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 id = do maybe_info <- lookupBindC_maybe id
198                     case maybe_info of
199                       Just info -> return info
200                       Nothing   -> cgLookupPanic id
201
202 lookupBindC_maybe :: Id -> FCode (Maybe CgIdInfo)
203 lookupBindC_maybe id
204   = do  static_binds <- getStaticBinds
205         local_binds  <- getBinds
206         return (lookupVarEnv local_binds id
207                         `seqMaybe`
208                 lookupVarEnv static_binds id)
209                         
210 cgLookupPanic :: Id -> FCode a
211 cgLookupPanic id
212   = do  static_binds <- getStaticBinds
213         local_binds <- getBinds
214         srt <- getSRTLabel
215         pprPanic "cgPanic"
216                 (vcat [ppr id,
217                 ptext SLIT("static binds for:"),
218                 vcat [ ppr i | (MkCgIdInfo i _ _ _) <- rngVarEnv static_binds ],
219                 ptext SLIT("local binds for:"),
220                 vcat [ ppr i | (MkCgIdInfo i _ _ _) <- rngVarEnv local_binds ],
221                 ptext SLIT("SRT label") <+> pprCLabel srt
222               ])
223 \end{code}
224
225 %************************************************************************
226 %*                                                                      *
227 \subsection[Bindery-nuke-volatile]{Nuking volatile bindings}
228 %*                                                                      *
229 %************************************************************************
230
231 We sometimes want to nuke all the volatile bindings; we must be sure
232 we don't leave any (NoVolatile, NoStable) binds around...
233
234 \begin{code}
235 nukeVolatileBinds :: CgBindings -> CgBindings
236 nukeVolatileBinds binds
237   = mkVarEnv (foldr keep_if_stable [] (rngVarEnv binds))
238   where
239     keep_if_stable (MkCgIdInfo i _ NoStableLoc entry_info) acc = acc
240     keep_if_stable (MkCgIdInfo i _ stable_loc  entry_info) acc
241       = (i, MkCgIdInfo i NoVolatileLoc stable_loc entry_info) : acc
242 \end{code}
243
244
245 %************************************************************************
246 %*                                                                      *
247 \subsection[lookup-interface]{Interface functions to looking up bindings}
248 %*                                                                      *
249 %************************************************************************
250
251 I {\em think} all looking-up is done through @getCAddrMode(s)@.
252
253 \begin{code}
254 getCAddrModeAndInfo :: Id -> FCode (Id, CAddrMode, LambdaFormInfo)
255
256 getCAddrModeAndInfo id
257   = do
258         maybe_cg_id_info <- lookupBindC_maybe id
259         case maybe_cg_id_info of
260
261                 -- Nothing => not in the environment, so should be imported
262           Nothing | isLocalName name -> cgLookupPanic id
263                   | otherwise        -> returnFC (id, global_amode, mkLFImported id)
264
265           Just (MkCgIdInfo id' volatile_loc stable_loc lf_info)
266                   -> do amode <- idInfoPiecesToAmode kind volatile_loc stable_loc
267                         return (id', amode, lf_info)
268   where
269     name = getName id
270     global_amode = CLbl (mkClosureLabel name) kind
271     kind = idPrimRep id
272
273 getCAddrMode :: Id -> FCode CAddrMode
274 getCAddrMode name = do
275         (_, amode, _) <- getCAddrModeAndInfo name
276         return amode
277 \end{code}
278
279 \begin{code}
280 getCAddrModeIfVolatile :: Id -> FCode (Maybe CAddrMode)
281 getCAddrModeIfVolatile name
282 --  | toplevelishId name = returnFC Nothing
283 --  | otherwise
284         = do
285         (MkCgIdInfo _ volatile_loc stable_loc lf_info) <- lookupBindC name
286         case stable_loc of
287                 NoStableLoc -> do -- Aha!  So it is volatile!
288                         amode <- idInfoPiecesToAmode (idPrimRep name) volatile_loc NoStableLoc
289                         return $ Just amode
290                 a_stable_loc -> return Nothing
291 \end{code}
292
293 @getVolatileRegs@ gets a set of live variables, and returns a list of
294 all registers on which these variables depend.  These are the regs
295 which must be saved and restored across any C calls.  If a variable is
296 both in a volatile location (depending on a register) {\em and} a
297 stable one (notably, on the stack), we modify the current bindings to
298 forget the volatile one.
299
300 \begin{code}
301 getVolatileRegs :: StgLiveVars -> FCode [MagicId]
302
303 getVolatileRegs vars = do
304         stuff <- mapFCs snaffle_it (varSetElems vars)
305         returnFC $ catMaybes stuff
306         where
307         snaffle_it var = do
308                 (MkCgIdInfo _ volatile_loc stable_loc lf_info) <- lookupBindC var 
309                 let
310                 -- commoned-up code...
311                         consider_reg reg =
312                                 if not (isVolatileReg reg) then
313                                 -- Potentially dies across C calls
314                                 -- For now, that's everything; we leave
315                                 -- it to the save-macros to decide which
316                                 -- regs *really* need to be saved.
317                                         returnFC Nothing
318                                 else
319                                         case stable_loc of
320                                                 NoStableLoc -> returnFC (Just reg) -- got one!
321                                                 is_a_stable_loc -> do
322                                                         -- has both volatile & stable locations;
323                                                         -- force it to rely on the stable location
324                                                         modifyBindC var nuke_vol_bind 
325                                                         return Nothing
326                         in
327                         case volatile_loc of
328                                 RegLoc reg   -> consider_reg reg
329                                 VirHpLoc _   -> consider_reg Hp
330                                 VirNodeLoc _ -> consider_reg node
331                                 non_reg_loc  -> returnFC Nothing
332
333         nuke_vol_bind (MkCgIdInfo i _ stable_loc lf_info)
334                 = MkCgIdInfo i NoVolatileLoc stable_loc lf_info
335 \end{code}
336
337 \begin{code}
338 getArgAmodes :: [StgArg] -> FCode [CAddrMode]
339 getArgAmodes [] = returnFC []
340 getArgAmodes (atom:atoms)
341         | isStgTypeArg atom 
342         = getArgAmodes atoms
343         | otherwise = do
344                 amode <- getArgAmode  atom 
345                 amodes <- getArgAmodes atoms
346                 return ( amode : amodes )
347
348 getArgAmode :: StgArg -> FCode CAddrMode
349
350 getArgAmode (StgVarArg var) = getCAddrMode var          -- The common case
351 getArgAmode (StgLitArg lit) = returnFC (CLit lit)
352 \end{code}
353
354 %************************************************************************
355 %*                                                                      *
356 \subsection[binding-and-rebinding-interface]{Interface functions for binding and re-binding names}
357 %*                                                                      *
358 %************************************************************************
359
360 \begin{code}
361 bindNewToStack :: (Id, VirtualSpOffset) -> Code
362 bindNewToStack (name, offset)
363   = addBindC name info
364   where
365     info = MkCgIdInfo name NoVolatileLoc (VirStkLoc offset) mkLFArgument
366
367 bindNewToNode :: Id -> VirtualHeapOffset -> LambdaFormInfo -> Code
368 bindNewToNode name offset lf_info
369   = addBindC name info
370   where
371     info = MkCgIdInfo name (VirNodeLoc offset) NoStableLoc lf_info
372
373 -- Create a new temporary whose unique is that in the id,
374 -- bind the id to it, and return the addressing mode for the
375 -- temporary.
376 bindNewToTemp :: Id -> FCode CAddrMode
377 bindNewToTemp name
378   = let (temp_amode, id_info) = newTempAmodeAndIdInfo name mkLFArgument
379                 -- This is used only for things we don't know
380                 -- anything about; values returned by a case statement,
381                 -- for example.
382     in do
383                 addBindC name id_info
384                 return temp_amode
385
386 bindNewToReg :: Id -> MagicId -> LambdaFormInfo -> Code
387 bindNewToReg name magic_id lf_info
388   = addBindC name info
389   where
390     info = MkCgIdInfo name (RegLoc magic_id) NoStableLoc lf_info
391
392 bindArgsToRegs :: [Id] -> [MagicId] -> Code
393 bindArgsToRegs args regs
394   = listCs (zipWithEqual "bindArgsToRegs" bind args regs)
395   where
396     arg `bind` reg = bindNewToReg arg reg mkLFArgument
397 \end{code}
398
399 @bindNewPrimToAmode@ works only for certain addressing modes.  Making
400 this work for stack offsets is non-trivial (virt vs. real stack offset
401 difficulties).
402
403 \begin{code}
404 bindNewPrimToAmode :: Id -> CAddrMode -> Code
405 bindNewPrimToAmode name (CReg reg) 
406   = bindNewToReg name reg (panic "bindNewPrimToAmode")
407
408 bindNewPrimToAmode name (CTemp uniq kind)
409   = addBindC name (tempIdInfo name uniq (panic "bindNewPrimToAmode"))
410
411 #ifdef DEBUG
412 bindNewPrimToAmode name amode
413   = pprPanic "bindNew...:" (pprAmode amode)
414 #endif
415 \end{code}
416
417 \begin{code}
418 rebindToStack :: Id -> VirtualSpOffset -> Code
419 rebindToStack name offset
420   = modifyBindC name replace_stable_fn
421   where
422     replace_stable_fn (MkCgIdInfo i vol stab einfo)
423       = MkCgIdInfo i vol (VirStkLoc offset) einfo
424 \end{code}
425
426 %************************************************************************
427 %*                                                                      *
428 \subsection[CgBindery-liveness]{Build a liveness mask for the current stack}
429 %*                                                                      *
430 %************************************************************************
431
432 There are four kinds of things on the stack:
433
434         - pointer variables (bound in the environment)
435         - non-pointer variables (boudn in the environment)
436         - free slots (recorded in the stack free list)
437         - non-pointer data slots (recorded in the stack free list)
438
439 We build up a bitmap of non-pointer slots by looking down the
440 environment for all the non-pointer variables, and merging this with
441 the slots recorded in the stack free list.
442
443 There's a bit of a hack here to do with update frames: since nothing
444 is recorded in either the environment or the stack free list for an
445 update frame, the code below defaults to assuming the slots taken up
446 by an update frame contain pointers.  Furthermore, update frames are
447 always in slots 0-2 at the bottom of the stack.  The bitmap will
448 therefore end at slot 3, which is what we want (the update frame info
449 pointer has its own bitmap to describe the update frame).
450
451 \begin{code}
452 buildLivenessMask 
453         :: Unique               -- unique for for large bitmap label
454         -> VirtualSpOffset      -- offset from which the bitmap should start
455         -> FCode Liveness       -- mask for free/unlifted slots
456
457 buildLivenessMask uniq sp = do  
458
459         -- find all unboxed stack-resident ids
460         binds <- getBinds
461         ((vsp, free, _, _), heap_usage) <- getUsage
462         
463         let unboxed_slots = 
464                 [ (ofs, size) | 
465                 (MkCgIdInfo id _ (VirStkLoc ofs) _) <- rngVarEnv binds,
466                 let rep = idPrimRep id; size = getPrimRepSize rep,
467                 not (isFollowableRep rep),
468                 size > 0
469                 ]       
470                 
471         -- flatten this list into a list of unboxed stack slots
472         let flatten_slots = sortLt (<) 
473                 (foldr (\(ofs,size) r -> [ofs-size+1 .. ofs] ++ r) []
474                       unboxed_slots)
475
476         -- merge in the free slots
477         let all_slots = mergeSlots flatten_slots (map fst free) ++ 
478                     if vsp < sp then [vsp+1 .. sp] else []
479
480         -- recalibrate the list to be sp-relative
481         let rel_slots = reverse (map (sp-) all_slots)
482
483         -- build the bitmap
484         let liveness_mask 
485                = ASSERT(all (>=0) rel_slots 
486                         && rel_slots == sortLt (<) rel_slots) 
487                  (listToLivenessMask rel_slots)
488         
489         livenessToAbsC uniq liveness_mask
490
491 mergeSlots :: [Int] -> [Int] -> [Int]
492 mergeSlots cs [] = cs
493 mergeSlots [] ns = ns
494 mergeSlots (c:cs) (n:ns)
495  = if c < n then
496         c : mergeSlots cs (n:ns)
497    else if c > n then
498         n : mergeSlots (c:cs) ns
499    else
500         panic ("mergeSlots: equal slots: " ++ show (c:cs) ++ show (n:ns))
501
502 listToLivenessMask :: [Int] -> LivenessMask
503 listToLivenessMask []    = []
504 listToLivenessMask slots = 
505    mkBS this : listToLivenessMask (map (\x -> x-32) rest)
506    where (this,rest) = span (<32) slots
507
508 livenessToAbsC :: Unique -> LivenessMask -> FCode Liveness
509 livenessToAbsC uniq mask  =
510         absC (CBitmap lbl mask) `thenC`
511         returnFC (Liveness lbl mask)
512   where lbl = mkBitmapLabel uniq       
513 \end{code}
514
515 In a continuation, we want a liveness mask that starts from just after
516 the return address, which is on the stack at realSp.
517
518 \begin{code}
519 buildContLivenessMask
520         :: Unique
521         -> FCode Liveness
522 buildContLivenessMask uniq = do
523         realSp <- getRealSp
524         buildLivenessMask uniq (realSp-1)
525 \end{code}
526
527 %************************************************************************
528 %*                                                                      *
529 \subsection[CgMonad-deadslots]{Finding dead stack slots}
530 %*                                                                      *
531 %************************************************************************
532
533 nukeDeadBindings does the following:
534
535       - Removes all bindings from the environment other than those
536         for variables in the argument to nukeDeadBindings.
537       - Collects any stack slots so freed, and returns them to the  stack free
538         list.
539       - Moves the virtual stack pointer to point to the topmost used
540         stack locations.
541
542 You can have multi-word slots on the stack (where a Double# used to
543 be, for instance); if dead, such a slot will be reported as *several*
544 offsets (one per word).
545
546 Probably *naughty* to look inside monad...
547
548 \begin{code}
549 nukeDeadBindings :: StgLiveVars  -- All the *live* variables
550                  -> Code
551 nukeDeadBindings live_vars = do
552         binds <- getBinds
553         let (dead_stk_slots, bs') =
554                 dead_slots live_vars 
555                         [] []
556                         [ (i, b) | b@(MkCgIdInfo i _ _ _) <- rngVarEnv binds ]
557         setBinds $ mkVarEnv bs'
558         freeStackSlots dead_stk_slots
559 \end{code}
560
561 Several boring auxiliary functions to do the dirty work.
562
563 \begin{code}
564 dead_slots :: StgLiveVars
565            -> [(Id,CgIdInfo)]
566            -> [VirtualSpOffset]
567            -> [(Id,CgIdInfo)]
568            -> ([VirtualSpOffset], [(Id,CgIdInfo)])
569
570 -- dead_slots carries accumulating parameters for
571 --      filtered bindings, dead slots
572 dead_slots live_vars fbs ds []
573   = (ds, reverse fbs) -- Finished; rm the dups, if any
574
575 dead_slots live_vars fbs ds ((v,i):bs)
576   | v `elementOfUniqSet` live_vars
577     = dead_slots live_vars ((v,i):fbs) ds bs
578           -- Live, so don't record it in dead slots
579           -- Instead keep it in the filtered bindings
580
581   | otherwise
582     = case i of
583         MkCgIdInfo _ _ stable_loc _
584          | is_stk_loc && size > 0 ->
585            dead_slots live_vars fbs ([offset-size+1 .. offset] ++ ds) bs
586          where
587           maybe_stk_loc = maybeStkLoc stable_loc
588           is_stk_loc    = maybeToBool maybe_stk_loc
589           (Just offset) = maybe_stk_loc
590
591         _ -> dead_slots live_vars fbs ds bs
592   where
593
594     size :: Int
595     size = (getPrimRepSize . typePrimRep . idType) v
596
597 \end{code}