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