[project @ 1998-12-18 17:40:31 by simonpj]
[ghc-hetmet.git] / ghc / compiler / codeGen / CgMonad.lhs
1 %
2 % (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
3 %
4 % $Id: CgMonad.lhs,v 1.16 1998/12/18 17:40:52 simonpj Exp $
5 %
6 \section[CgMonad]{The code generation monad}
7
8 See the beginning of the top-level @CodeGen@ module, to see how this
9 monadic stuff fits into the Big Picture.
10
11 \begin{code}
12 module CgMonad (
13         Code,   -- type
14         FCode,  -- type
15
16         initC, thenC, thenFC, listCs, listFCs, mapCs, mapFCs,
17         returnFC, fixC, absC, nopC, getAbsC,
18
19         forkClosureBody, forkStatics, forkAlts, forkEval,
20         forkEvalHelp, forkAbsC,
21         SemiTaggingStuff,
22
23         addBindC, addBindsC, modifyBindC, lookupBindC,
24
25         EndOfBlockInfo(..),
26         setEndOfBlockInfo, getEndOfBlockInfo,
27
28         setSRTLabel, getSRTLabel,
29
30         StackUsage, HeapUsage,
31
32         profCtrC,
33
34         costCentresC, moduleName,
35
36         Sequel(..), -- ToDo: unabstract?
37         sequelToAmode,
38
39         -- out of general friendliness, we also export ...
40         CgInfoDownwards(..), CgState(..),       -- non-abstract
41         CompilationInfo(..)
42     ) where
43
44 #include "HsVersions.h"
45
46 import {-# SOURCE #-} CgBindery ( CgIdInfo(..), CgBindings, maybeStkLoc, nukeVolatileBinds )
47 import {-# SOURCE #-} CgUsages  ( getSpRelOffset )
48
49 import AbsCSyn
50 import AbsCUtils        ( mkAbsCStmts )
51 import CmdLineOpts      ( opt_SccProfilingOn, opt_DoTickyProfiling )
52 import CLabel           ( CLabel, mkUpdEntryLabel )
53 import OccName          ( Module )
54 import DataCon          ( ConTag )
55 import Id               ( Id )
56 import VarEnv
57 import PrimRep          ( getPrimRepSize, PrimRep(..) )
58 import StgSyn           ( StgLiveVars )
59 import Outputable
60
61 infixr 9 `thenC`        -- Right-associative!
62 infixr 9 `thenFC`
63 \end{code}
64
65 %************************************************************************
66 %*                                                                      *
67 \subsection[CgMonad-environment]{Stuff for manipulating environments}
68 %*                                                                      *
69 %************************************************************************
70
71 This monadery has some information that it only passes {\em
72 downwards}, as well as some ``state'' which is modified as we go
73 along.
74
75 \begin{code}
76 data CgInfoDownwards    -- information only passed *downwards* by the monad
77   = MkCgInfoDown
78      CompilationInfo    -- COMPLETELY STATIC info about this compilation
79                         --  (e.g., what flags were passed to the compiler)
80
81      CgBindings         -- [Id -> info] : static environment
82
83      CLabel             -- label of the current SRT
84
85      EndOfBlockInfo     -- Info for stuff to do at end of basic block:
86
87
88 data CompilationInfo
89   = MkCompInfo
90         Module          -- the module name
91
92 data CgState
93   = MkCgState
94         AbstractC       -- code accumulated so far
95         CgBindings      -- [Id -> info] : *local* bindings environment
96                         -- Bindings for top-level things are given in the info-down part
97         CgStksAndHeapUsage
98 \end{code}
99
100 @EndOfBlockInfo@ tells what to do at the end of this block of code or,
101 if the expression is a @case@, what to do at the end of each
102 alternative.
103
104 \begin{code}
105 data EndOfBlockInfo
106   = EndOfBlockInfo
107         VirtualSpOffset   -- Args Sp: trim the stack to this point at a
108                           -- return; push arguments starting just
109                           -- above this point on a tail call.
110                           
111                           -- This is therefore the stk ptr as seen
112                           -- by a case alternative.
113         Sequel
114
115 initEobInfo = EndOfBlockInfo 0 (OnStack 0)
116 \end{code}
117
118 Any addressing modes inside @Sequel@ must be ``robust,'' in the sense
119 that it must survive stack pointer adjustments at the end of the
120 block.
121
122 \begin{code}
123 data Sequel
124   = OnStack 
125         VirtualSpOffset   -- Continuation is on the stack, at the
126                           -- specified location
127
128   | UpdateCode
129
130   | CaseAlts
131           CAddrMode   -- Jump to this; if the continuation is for a vectored
132                       -- case this might be the label of a return
133                       -- vector Guaranteed to be a non-volatile
134                       -- addressing mode (I think)
135           SemiTaggingStuff
136
137   | SeqFrame                    -- like CaseAlts but push a seq frame too.
138           CAddrMode
139           SemiTaggingStuff
140
141 type SemiTaggingStuff
142   = Maybe                           -- Maybe[1] we don't have any semi-tagging stuff...
143      ([(ConTag, JoinDetails)],      -- Alternatives
144       Maybe (Maybe Id, JoinDetails) -- Default (but Maybe[2] we don't have one)
145                                     -- Maybe[3] the default is a
146                                     -- bind-default (Just b); that is,
147                                     -- it expects a ptr to the thing
148                                     -- in Node, bound to b
149      )
150
151 type JoinDetails
152   = (AbstractC, CLabel)         -- Code to load regs from heap object + profiling macros,
153                                 -- and join point label
154
155 -- The abstract C is executed only from a successful semitagging
156 -- venture, when a case has looked at a variable, found that it's
157 -- evaluated, and wants to load up the contents and go to the join
158 -- point.
159
160 -- DIRE WARNING.
161 -- The OnStack case of sequelToAmode delivers an Amode which is only
162 -- valid just before the final control transfer, because it assumes
163 -- that Sp is pointing to the top word of the return address.  This
164 -- seems unclean but there you go.
165
166 sequelToAmode :: Sequel -> FCode CAddrMode
167
168 sequelToAmode (OnStack virt_sp_offset)
169   = getSpRelOffset virt_sp_offset `thenFC` \ sp_rel ->
170     returnFC (CVal sp_rel RetRep)
171
172 sequelToAmode UpdateCode = returnFC (CLbl mkUpdEntryLabel CodePtrRep)
173 sequelToAmode (CaseAlts amode _) = returnFC amode
174 sequelToAmode (SeqFrame _ _) = panic "sequelToAmode: SeqFrame"
175
176 type CgStksAndHeapUsage         -- stacks and heap usage information
177   = (StackUsage, HeapUsage)
178
179 type StackUsage =
180         (Int,              -- virtSp: Virtual offset of topmost allocated slot
181          [Int],            -- free:   List of free slots, in increasing order
182          Int,              -- realSp: Virtual offset of real stack pointer
183          Int)              -- hwSp:   Highest value ever taken by virtSp
184
185 type HeapUsage =
186         (HeapOffset,    -- virtHp: Virtual offset of highest-allocated word
187          HeapOffset)    -- realHp: Virtual offset of real heap ptr
188 \end{code}
189
190 NB: absolutely every one of the above Ints is really
191 a VirtualOffset of some description (the code generator
192 works entirely in terms of VirtualOffsets).
193
194 Initialisation.
195
196 \begin{code}
197 initialStateC = MkCgState AbsCNop emptyVarEnv initUsage
198
199 initUsage :: CgStksAndHeapUsage
200 initUsage  = ((0,[],0,0), (initVirtHp, initRealHp))
201 initVirtHp = panic "Uninitialised virtual Hp"
202 initRealHp = panic "Uninitialised real Hp"
203 \end{code}
204
205 "envInitForAlternatives" initialises the environment for a case alternative,
206 assuming that the alternative is entered after an evaluation.
207 This involves:
208
209    - zapping any volatile bindings, which aren't valid.
210    
211    - zapping the heap usage. It should be restored by a heap check.
212    
213    - setting the virtual AND real stack pointer fields to the given
214    virtual stack offsets.  this doesn't represent any {\em code}; it is a
215    prediction of where the real stack pointer will be when we come back
216    from the case analysis.
217    
218    - BUT LEAVING the rest of the stack-usage info because it is all
219    valid.  In particular, we leave the tail stack pointers unchanged,
220    becuase the alternative has to de-allocate the original @case@
221    expression's stack.  \end{itemize}
222
223 @stateIncUsage@$~e_1~e_2$ incorporates in $e_1$ the stack and heap high water
224 marks found in $e_2$.
225
226 \begin{code}
227 stateIncUsage :: CgState -> CgState -> CgState
228
229 stateIncUsage (MkCgState abs_c bs ((v,f,r,h1),(vH1,rH1)))
230               (MkCgState _     _  ((_,_,_,h2),(vH2, _)))
231      = MkCgState abs_c
232                  bs
233                  ((v,f,r,h1 `max` h2),
234                   (vH1 `max` vH2, rH1))
235 \end{code}
236
237 %************************************************************************
238 %*                                                                      *
239 \subsection[CgMonad-basics]{Basic code-generation monad magic}
240 %*                                                                      *
241 %************************************************************************
242
243 \begin{code}
244 type FCode a = CgInfoDownwards -> CgState -> (a, CgState)
245 type Code    = CgInfoDownwards -> CgState -> CgState
246
247 {-# INLINE thenC #-}
248 {-# INLINE thenFC #-}
249 {-# INLINE returnFC #-}
250 \end{code}
251 The Abstract~C is not in the environment so as to improve strictness.
252
253 \begin{code}
254 initC :: CompilationInfo -> Code -> AbstractC
255
256 initC cg_info code
257   = case (code (MkCgInfoDown 
258                         cg_info 
259                         (error "initC: statics")
260                         (error "initC: srt")
261                         initEobInfo)
262                initialStateC) of
263       MkCgState abc _ _ -> abc
264
265 returnFC :: a -> FCode a
266
267 returnFC val info_down state = (val, state)
268 \end{code}
269
270 \begin{code}
271 thenC :: Code
272       -> (CgInfoDownwards -> CgState -> a)
273       -> CgInfoDownwards -> CgState -> a
274
275 -- thenC has both of the following types:
276 -- thenC :: Code -> Code    -> Code
277 -- thenC :: Code -> FCode a -> FCode a
278
279 thenC m k info_down state
280   = k info_down new_state
281   where
282     new_state  = m info_down state
283
284 listCs :: [Code] -> Code
285
286 listCs []     info_down state = state
287 listCs (c:cs) info_down state = stateN
288   where
289     state1 = c         info_down state
290     stateN = listCs cs info_down state1
291
292 mapCs :: (a -> Code) -> [a] -> Code
293
294 mapCs f []     info_down state = state
295 mapCs f (c:cs) info_down state = stateN
296   where
297     state1 = (f c)      info_down state
298     stateN = mapCs f cs info_down state1
299 \end{code}
300
301 \begin{code}
302 thenFC  :: FCode a
303         -> (a -> CgInfoDownwards -> CgState -> c)
304         -> CgInfoDownwards -> CgState -> c
305
306 -- thenFC :: FCode a -> (a -> FCode b) -> FCode b
307 -- thenFC :: FCode a -> (a -> Code)    -> Code
308
309 thenFC m k info_down state
310   = k m_result info_down new_state
311   where
312     (m_result, new_state) = m info_down state
313
314 listFCs :: [FCode a] -> FCode [a]
315
316 listFCs []       info_down state = ([],             state)
317 listFCs (fc:fcs) info_down state = (thing : things, stateN)
318   where
319     (thing,  state1) = fc          info_down state
320     (things, stateN) = listFCs fcs info_down state1
321
322 mapFCs :: (a -> FCode b) -> [a] -> FCode [b]
323
324 mapFCs f []       info_down state = ([],             state)
325 mapFCs f (fc:fcs) info_down state = (thing : things, stateN)
326   where
327     (thing,  state1) = (f fc)       info_down state
328     (things, stateN) = mapFCs f fcs info_down state1
329 \end{code}
330
331 And the knot-tying combinator:
332 \begin{code}
333 fixC :: (a -> FCode a) -> FCode a
334 fixC fcode info_down state = result
335   where
336     result@(v, _) = fcode v info_down state
337     --      ^-------------^
338 \end{code}
339
340 @forkClosureBody@ takes a code, $c$, and compiles it in a completely
341 fresh environment, except that:
342         - compilation info and statics are passed in unchanged.
343 The current environment is passed on completely unaltered, except that
344 abstract C from the fork is incorporated.
345
346 @forkAbsC@ takes a code and compiles it in the current environment,
347 returning the abstract C thus constructed.  The current environment
348 is passed on completely unchanged.  It is pretty similar to @getAbsC@,
349 except that the latter does affect the environment. ToDo: combine?
350
351 @forkStatics@ $fc$ compiles $fc$ in an environment whose statics come
352 from the current bindings, but which is otherwise freshly initialised.
353 The Abstract~C returned is attached to the current state, but the
354 bindings and usage information is otherwise unchanged.
355
356 \begin{code}
357 forkClosureBody :: Code -> Code
358
359 forkClosureBody code
360         (MkCgInfoDown cg_info statics srt _)
361         (MkCgState absC_in binds un_usage)
362   = MkCgState (AbsCStmts absC_in absC_fork) binds un_usage
363   where
364     fork_state              = code body_info_down initialStateC
365     MkCgState absC_fork _ _ = fork_state
366     body_info_down = MkCgInfoDown cg_info statics srt initEobInfo
367
368 forkStatics :: FCode a -> FCode a
369
370 forkStatics fcode (MkCgInfoDown cg_info _ srt _)
371                   (MkCgState absC_in statics un_usage)
372   = (result, MkCgState (AbsCStmts absC_in absC_fork) statics un_usage)
373   where
374   (result, state) = fcode rhs_info_down initialStateC
375   MkCgState absC_fork _ _ = state       -- Don't merge these this line with the one
376                                         -- above or it becomes too strict!
377   rhs_info_down = MkCgInfoDown cg_info statics srt initEobInfo
378
379 forkAbsC :: Code -> FCode AbstractC
380 forkAbsC code info_down (MkCgState absC1 bs usage)
381   = (absC2, new_state)
382   where
383     MkCgState absC2 _ ((_, _, _,h2), _) =
384         code info_down (MkCgState AbsCNop bs usage)
385     ((v, f, r, h1), heap_usage) = usage
386
387     new_usage = ((v, f, r, h1 `max` h2), heap_usage)
388     new_state = MkCgState absC1 bs new_usage
389 \end{code}
390
391 @forkAlts@ $bs~d$ takes fcodes $bs$ for the branches of a @case@, and
392 an fcode for the default case $d$, and compiles each in the current
393 environment.  The current environment is passed on unmodified, except
394 that
395         - the worst stack high-water mark is incorporated
396         - the virtual Hp is moved on to the worst virtual Hp for the branches
397
398 \begin{code}
399 forkAlts :: [FCode a] -> FCode b -> FCode ([a],b)
400
401 forkAlts branch_fcodes deflt_fcode info_down in_state
402  = ((branch_results , deflt_result), out_state)
403   where
404     compile fc = fc info_down in_state
405
406     (branch_results, branch_out_states) = unzip (map compile branch_fcodes)
407
408     (deflt_result, deflt_out_state) = deflt_fcode info_down in_state
409
410     out_state = foldl stateIncUsage in_state (deflt_out_state:branch_out_states)
411                 -- NB foldl.  in_state is the *left* argument to stateIncUsage
412 \end{code}
413
414 @forkEval@ takes two blocks of code.
415
416    -  The first meddles with the environment to set it up as expected by
417       the alternatives of a @case@ which does an eval (or gc-possible primop).
418    -  The second block is the code for the alternatives.
419       (plus info for semi-tagging purposes)
420
421 @forkEval@ picks up the virtual stack pointer and returns a suitable
422 @EndOfBlockInfo@ for the caller to use, together with whatever value
423 is returned by the second block.
424
425 It uses @initEnvForAlternatives@ to initialise the environment, and
426 @stateIncUsageAlt@ to incorporate usage; the latter ignores the heap
427 usage.
428
429 \begin{code}
430 forkEval :: EndOfBlockInfo              -- For the body
431          -> Code                        -- Code to set environment
432          -> FCode Sequel                -- Semi-tagging info to store
433          -> FCode EndOfBlockInfo        -- The new end of block info
434
435 forkEval body_eob_info env_code body_code
436   = forkEvalHelp body_eob_info env_code body_code `thenFC` \ (v, sequel) ->
437     returnFC (EndOfBlockInfo v sequel)
438
439 forkEvalHelp :: EndOfBlockInfo  -- For the body
440              -> Code            -- Code to set environment
441              -> FCode a         -- The code to do after the eval
442              -> FCode (Int,     -- Sp
443                        a)       -- Result of the FCode
444
445 forkEvalHelp body_eob_info env_code body_code
446          info_down@(MkCgInfoDown cg_info statics srt _) state
447   = ((v,value_returned), state `stateIncUsageEval` state_at_end_return)
448   where
449     info_down_for_body = MkCgInfoDown cg_info statics srt body_eob_info
450
451     (MkCgState _ binds ((v,f,_,_), _)) = env_code info_down_for_body state
452         -- These v and f things are now set up as the body code expects them
453
454     (value_returned, state_at_end_return) 
455         = body_code info_down_for_body state_for_body
456
457     state_for_body = MkCgState AbsCNop
458                              (nukeVolatileBinds binds)
459                              ((v,f,v,v),
460                               (initVirtHp, initRealHp))
461
462
463 stateIncUsageEval :: CgState -> CgState -> CgState
464 stateIncUsageEval (MkCgState absC1 bs ((v,f,r,h1),heap_usage))
465                   (MkCgState absC2 _  ((_,_,_,h2),         _))
466      = MkCgState (absC1 `AbsCStmts` absC2)
467                  -- The AbsC coming back should consist only of nested declarations,
468                  -- notably of the return vector!
469                  bs
470                  ((v,f,r,h1 `max` h2), heap_usage)
471         -- We don't max the heap high-watermark because stateIncUsageEval is
472         -- used only in forkEval, which in turn is only used for blocks of code
473         -- which do their own heap-check.
474 \end{code}
475
476 %************************************************************************
477 %*                                                                      *
478 \subsection[CgMonad-spitting-AbstractC]{Spitting out @AbstractC@}
479 %*                                                                      *
480 %************************************************************************
481
482 @nopC@ is the no-op for the @Code@ monad; it adds no Abstract~C to the
483 environment; @absC@ glues @ab_C@ onto the Abstract~C collected so far.
484 \begin{code}
485 nopC :: Code
486 nopC info_down state = state
487
488 absC :: AbstractC -> Code
489 absC more_absC info_down state@(MkCgState absC binds usage)
490   = MkCgState (mkAbsCStmts absC more_absC) binds usage
491 \end{code}
492
493 These two are just like @absC@, except they examine the compilation
494 info (whether SCC profiling or profiling-ctrs going) and possibly emit
495 nothing.
496
497 \begin{code}
498 costCentresC :: FAST_STRING -> [CAddrMode] -> Code
499
500 costCentresC macro args _ state@(MkCgState absC binds usage)
501   = if opt_SccProfilingOn
502     then MkCgState (mkAbsCStmts absC (CCallProfCCMacro macro args)) binds usage
503     else state
504
505 profCtrC :: FAST_STRING -> [CAddrMode] -> Code
506
507 profCtrC macro args _ state@(MkCgState absC binds usage)
508   = if not opt_DoTickyProfiling
509     then state
510     else MkCgState (mkAbsCStmts absC (CCallProfCtrMacro macro args)) binds usage
511
512 {- Try to avoid adding too many special compilation strategies here.
513    It's better to modify the header files as necessary for particular
514    targets, so that we can get away with as few variants of .hc files
515    as possible.
516 -}
517 \end{code}
518
519 @getAbsC@ compiles the code in the current environment, and returns
520 the abstract C thus constructed (leaving the abstract C being carried
521 around in the state untouched).  @getAbsC@ does not generate any
522 in-line Abstract~C itself, but the environment it returns is that
523 obtained from the compilation.
524
525 \begin{code}
526 getAbsC :: Code -> FCode AbstractC
527
528 getAbsC code info_down (MkCgState absC binds usage)
529   = (absC2, MkCgState absC binds2 usage2)
530   where
531     (MkCgState absC2 binds2 usage2) 
532         = code info_down (MkCgState AbsCNop binds usage)
533 \end{code}
534
535 \begin{code}
536
537 moduleName :: FCode Module
538 moduleName (MkCgInfoDown (MkCompInfo mod_name) _ _ _) state
539   = (mod_name, state)
540
541 \end{code}
542
543 \begin{code}
544 setEndOfBlockInfo :: EndOfBlockInfo -> Code -> Code
545 setEndOfBlockInfo eob_info code (MkCgInfoDown c_info statics srt _) state
546   = code (MkCgInfoDown c_info statics srt eob_info) state
547
548 getEndOfBlockInfo :: FCode EndOfBlockInfo
549 getEndOfBlockInfo (MkCgInfoDown c_info statics _ eob_info) state
550   = (eob_info, state)
551 \end{code}
552
553 \begin{code}
554 getSRTLabel :: FCode CLabel
555 getSRTLabel (MkCgInfoDown _ _ srt _) state
556   = (srt, state)
557
558 setSRTLabel :: CLabel -> Code -> Code
559 setSRTLabel srt code (MkCgInfoDown c_info statics _ eob_info) state
560   = code (MkCgInfoDown c_info statics srt eob_info) state
561 \end{code}
562
563 %************************************************************************
564 %*                                                                      *
565 \subsection[CgMonad-bindery]{Monad things for fiddling with @CgBindings@}
566 %*                                                                      *
567 %************************************************************************
568
569 There are three basic routines, for adding (@addBindC@), modifying
570 (@modifyBindC@) and looking up (@lookupBindC@) bindings.
571
572 A @Id@ is bound to a @(VolatileLoc, StableLoc)@ triple.
573 The name should not already be bound. (nice ASSERT, eh?)
574
575 \begin{code}
576 addBindC :: Id -> CgIdInfo -> Code
577 addBindC name stuff_to_bind info_down (MkCgState absC binds usage)
578   = MkCgState absC (extendVarEnv binds name stuff_to_bind) usage
579
580 addBindsC :: [(Id, CgIdInfo)] -> Code
581 addBindsC new_bindings info_down (MkCgState absC binds usage)
582   = MkCgState absC new_binds usage
583   where
584     new_binds = foldl (\ binds (name,info) -> extendVarEnv binds name info)
585                       binds
586                       new_bindings
587
588 modifyBindC :: Id -> (CgIdInfo -> CgIdInfo) -> Code
589 modifyBindC name mangle_fn info_down (MkCgState absC binds usage)
590   = MkCgState absC (modifyVarEnv mangle_fn binds name) usage
591
592 lookupBindC :: Id -> FCode CgIdInfo
593 lookupBindC name info_down@(MkCgInfoDown _ static_binds srt _)
594                  state@(MkCgState absC local_binds usage)
595   = (val, state)
596   where
597     val = case (lookupVarEnv local_binds name) of
598             Nothing     -> try_static
599             Just this   -> this
600
601     try_static = 
602       case (lookupVarEnv static_binds name) of
603         Just this -> this
604         Nothing
605           -> pprPanic "lookupBindC:no info!\n"
606              (vcat [
607                 hsep [ptext SLIT("for:"), ppr name],
608                 ptext SLIT("(probably: data dependencies broken by an optimisation pass)"),
609                 ptext SLIT("static binds for:"),
610                 vcat [ ppr i | (MkCgIdInfo i _ _ _) <- rngVarEnv static_binds ],
611                 ptext SLIT("local binds for:"),
612                 vcat [ ppr i | (MkCgIdInfo i _ _ _) <- rngVarEnv local_binds ]
613               ])
614 \end{code}