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