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