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