ghc/compiler/codeGen/CgLetNoEscape.lhs

   1 %
   2 % (c) The GRASP/AQUA Project, Glasgow University, 1993-1994
   3 %
   4 %********************************************************
   5 %*                                                      *
   6 \section[CgLetNoEscape]{Handling ``let-no-escapes''}
   7 %*                                                      *
   8 %********************************************************
   9
  10 \begin{code}
  11 #include "HsVersions.h"
  12
  13 module CgLetNoEscape ( cgLetNoEscapeClosure ) where
  14
  15 IMP_Ubiq(){-uitious-}
  16 IMPORT_DELOOPER(CgLoop2)                ( cgExpr )
  17
  18 import StgSyn
  19 import CgMonad
  20 import AbsCSyn
  21
  22 import CgBindery        ( letNoEscapeIdInfo, bindArgsToRegs,
  23                           bindNewToAStack, bindNewToBStack,
  24                           CgIdInfo
  25                         )
  26 import CgHeapery        ( heapCheck )
  27 import CgRetConv        ( assignRegs )
  28 import CgStackery       ( mkVirtStkOffsets )
  29 import CgUsages         ( setRealAndVirtualSps, getVirtSps )
  30 import CLabel           ( mkStdEntryLabel )
  31 import ClosureInfo      ( mkLFLetNoEscape )
  32 import CostCentre       ( CostCentre )
  33 import HeapOffs         ( SYN_IE(VirtualSpBOffset) )
  34 import Id               ( idPrimRep, SYN_IE(Id) )
  35 \end{code}
  36
  37 %************************************************************************
  38 %*                                                                      *
  39 \subsection[what-is-non-escaping]{What {\em is} a ``non-escaping let''?}
  40 %*                                                                      *
  41 %************************************************************************
  42
  43 [The {\em code} that detects these things is elsewhere.]
  44
  45 Consider:
  46 \begin{verbatim}
  47         let x = fvs \ args -> e
  48         in
  49                 if ... then x else
  50                 if ... then x else ...
  51 \end{verbatim}
  52 @x@ is used twice (so we probably can't unfold it), but when it is
  53 entered, the stack is deeper than it was then the definition of @x@
  54 happened.  Specifically, if instead of allocating a closure for @x@,
  55 we saved all @x@'s fvs on the stack, and remembered the stack depth at
  56 that moment, then whenever we enter @x@ we can simply set the stack
  57 pointer(s) to these remembered (compile-time-fixed) values, and jump
  58 to the code for @x@.
  59
  60 All of this is provided x is:
  61 \begin{enumerate}
  62 \item
  63 non-updatable;
  64 \item
  65 guaranteed to be entered before the stack retreats -- ie x is not
  66 buried in a heap-allocated closure, or passed as an argument to something;
  67 \item
  68 all the enters have exactly the right number of arguments,
  69 no more no less;
  70 \item
  71 all the enters are tail calls; that is, they return to the
  72 caller enclosing the definition of @x@.
  73 \end{enumerate}
  74
  75 Under these circumstances we say that @x@ is {\em non-escaping}.
  76
  77 An example of when (4) does {\em not} hold:
  78 \begin{verbatim}
  79         let x = ...
  80         in case x of ...alts...
  81 \end{verbatim}
  82
  83 Here, @x@ is certainly entered only when the stack is deeper than when
  84 @x@ is defined, but here it must return to \tr{...alts...} So we can't
  85 just adjust the stack down to @x@'s recalled points, because that
  86 would lost @alts@' context.
  87
  88 Things can get a little more complicated.  Consider:
  89 \begin{verbatim}
  90         let y = ...
  91         in let x = fvs \ args -> ...y...
  92         in ...x...
  93 \end{verbatim}
  94
  95 Now, if @x@ is used in a non-escaping way in \tr{...x...}, {\em and}
  96 @y@ is used in a non-escaping way in \tr{...y...}, {\em then} @y@ is
  97 non-escaping.
  98
  99 @x@ can even be recursive!  Eg:
 100 \begin{verbatim}
 101         letrec x = [y] \ [v] -> if v then x True else ...
 102         in
 103                 ...(x b)...
 104 \end{verbatim}
 105
 106
 107 %************************************************************************
 108 %*                                                                      *
 109 \subsection[codeGen-for-non-escaping]{Generating code for a ``non-escaping let''}
 110 %*                                                                      *
 111 %************************************************************************
 112
 113
 114 Generating code for this is fun.  It is all very very similar to what
 115 we do for a case expression.  The duality is between
 116 \begin{verbatim}
 117         let-no-escape x = b
 118         in e
 119 \end{verbatim}
 120 and
 121 \begin{verbatim}
 122         case e of ... -> b
 123 \end{verbatim}
 124
 125 That is, the RHS of @x@ (ie @b@) will execute {\em later}, just like
 126 the alternative of the case; it needs to be compiled in an environment
 127 in which all volatile bindings are forgotten, and the free vars are
 128 bound only to stable things like stack locations..  The @e@ part will
 129 execute {\em next}, just like the scrutinee of a case.
 130
 131 First, we need to save all @x@'s free vars
 132 on the stack, if they aren't there already.
 133
 134 \begin{code}
 135 cgLetNoEscapeClosure
 136         :: Id                   -- binder
 137         -> CostCentre           -- NB: *** NOT USED *** ToDo (WDP 94/06)
 138         -> StgBinderInfo        -- NB: ditto
 139         -> StgLiveVars  -- variables live in RHS, including the binders
 140                                 -- themselves in the case of a recursive group
 141         -> EndOfBlockInfo       -- where are we going to?
 142         -> Maybe VirtualSpBOffset -- Slot for current cost centre
 143         -> [Id]                 -- args (as in \ args -> body)
 144         -> StgExpr              -- body (as in above)
 145         -> FCode (Id, CgIdInfo)
 146
 147 -- ToDo: deal with the cost-centre issues
 148
 149 cgLetNoEscapeClosure binder cc bi full_live_in_rhss rhs_eob_info maybe_cc_slot args body
 150   = let
 151         arity   = length args
 152         lf_info = mkLFLetNoEscape arity full_live_in_rhss{-used???-}
 153     in
 154     forkEvalHelp
 155         rhs_eob_info
 156         (nukeDeadBindings full_live_in_rhss)
 157         (forkAbsC (cgLetNoEscapeBody args body))
 158                                         `thenFC` \ (vA, vB, code) ->
 159     let
 160         label = mkStdEntryLabel binder -- arity
 161     in
 162     absC (CCodeBlock label code) `thenC`
 163     returnFC (binder, letNoEscapeIdInfo binder vA vB lf_info)
 164 \end{code}
 165
 166 \begin{code}
 167 cgLetNoEscapeBody :: [Id]               -- Args
 168                   -> StgExpr    -- Body
 169                   -> Code
 170
 171 cgLetNoEscapeBody all_args rhs
 172   = getVirtSps          `thenFC` \ (vA, vB) ->
 173     let
 174         arg_kinds            = map idPrimRep all_args
 175         (arg_regs, _)        = assignRegs [{-nothing live-}] arg_kinds
 176         (reg_args, stk_args) = splitAt (length arg_regs) all_args
 177
 178         -- stk_args is the args which are passed on the stack at the fast-entry point
 179         -- Using them, we define the stack layout
 180         (spA_stk_args, spB_stk_args, stk_bxd_w_offsets, stk_ubxd_w_offsets)
 181           = mkVirtStkOffsets
 182                 vA vB           -- Initial virtual SpA, SpB
 183                 idPrimRep
 184                 stk_args
 185     in
 186
 187         -- Bind args to appropriate regs/stk locns
 188     bindArgsToRegs reg_args arg_regs                `thenC`
 189     mapCs bindNewToAStack stk_bxd_w_offsets         `thenC`
 190     mapCs bindNewToBStack stk_ubxd_w_offsets        `thenC`
 191     setRealAndVirtualSps spA_stk_args spB_stk_args  `thenC`
 192
 193 {-      ToDo: NOT SURE ABOUT COST CENTRES!
 194         -- Enter the closures cc, if required
 195         lexEnterCCcode closure_info maybe_cc        `thenC`
 196 -}
 197
 198         -- [No need for stack check; forkEvalHelp dealt with that]
 199
 200         -- Do heap check [ToDo: omit for non-recursive case by recording in
 201         --      in envt and absorbing at call site]
 202     heapCheck arg_regs False {- Node doesn't point to it -}  (
 203               -- heapCheck *encloses* the rest
 204
 205         -- Compile the body
 206     cgExpr rhs
 207     )
 208 \end{code}