compiler/codeGen/CgLetNoEscape.lhs

   1 %
   2 % (c) The University of Glasgow 2006
   3 % (c) The GRASP/AQUA Project, Glasgow University, 1993-1998
   4 %
   5 %********************************************************
   6 %*                                                      *
   7 \section[CgLetNoEscape]{Handling ``let-no-escapes''}
   8 %*                                                      *
   9 %********************************************************
  10
  11 \begin{code}
  12 {-# OPTIONS_GHC -w #-}
  13 -- The above warning supression flag is a temporary kludge.
  14 -- While working on this module you are encouraged to remove it and fix
  15 -- any warnings in the module. See
  16 --     http://hackage.haskell.org/trac/ghc/wiki/WorkingConventions#Warnings
  17 -- for details
  18
  19 module CgLetNoEscape ( cgLetNoEscapeClosure ) where
  20
  21 #include "HsVersions.h"
  22
  23 import {-# SOURCE #-} CgExpr ( cgExpr )
  24
  25 import StgSyn
  26 import CgMonad
  27
  28 import CgBindery
  29 import CgCase
  30 import CgCon
  31 import CgHeapery
  32 import CgInfoTbls
  33 import CgStackery
  34 import Cmm
  35 import CmmUtils
  36 import CLabel
  37 import ClosureInfo
  38 import CostCentre
  39 import Var
  40 import SMRep
  41 import BasicTypes
  42 \end{code}
  43
  44 %************************************************************************
  45 %*                                                                      *
  46 \subsection[what-is-non-escaping]{What {\em is} a ``non-escaping let''?}
  47 %*                                                                      *
  48 %************************************************************************
  49
  50 [The {\em code} that detects these things is elsewhere.]
  51
  52 Consider:
  53 \begin{verbatim}
  54         let x = fvs \ args -> e
  55         in
  56                 if ... then x else
  57                 if ... then x else ...
  58 \end{verbatim}
  59 @x@ is used twice (so we probably can't unfold it), but when it is
  60 entered, the stack is deeper than it was when the definition of @x@
  61 happened.  Specifically, if instead of allocating a closure for @x@,
  62 we saved all @x@'s fvs on the stack, and remembered the stack depth at
  63 that moment, then whenever we enter @x@ we can simply set the stack
  64 pointer(s) to these remembered (compile-time-fixed) values, and jump
  65 to the code for @x@.
  66
  67 All of this is provided x is:
  68 \begin{enumerate}
  69 \item
  70 non-updatable;
  71 \item
  72 guaranteed to be entered before the stack retreats -- ie x is not
  73 buried in a heap-allocated closure, or passed as an argument to something;
  74 \item
  75 all the enters have exactly the right number of arguments,
  76 no more no less;
  77 \item
  78 all the enters are tail calls; that is, they return to the
  79 caller enclosing the definition of @x@.
  80 \end{enumerate}
  81
  82 Under these circumstances we say that @x@ is {\em non-escaping}.
  83
  84 An example of when (4) does {\em not} hold:
  85 \begin{verbatim}
  86         let x = ...
  87         in case x of ...alts...
  88 \end{verbatim}
  89
  90 Here, @x@ is certainly entered only when the stack is deeper than when
  91 @x@ is defined, but here it must return to \tr{...alts...} So we can't
  92 just adjust the stack down to @x@'s recalled points, because that
  93 would lost @alts@' context.
  94
  95 Things can get a little more complicated.  Consider:
  96 \begin{verbatim}
  97         let y = ...
  98         in let x = fvs \ args -> ...y...
  99         in ...x...
 100 \end{verbatim}
 101
 102 Now, if @x@ is used in a non-escaping way in \tr{...x...}, {\em and}
 103 @y@ is used in a non-escaping way in \tr{...y...}, {\em then} @y@ is
 104 non-escaping.
 105
 106 @x@ can even be recursive!  Eg:
 107 \begin{verbatim}
 108         letrec x = [y] \ [v] -> if v then x True else ...
 109         in
 110                 ...(x b)...
 111 \end{verbatim}
 112
 113
 114 %************************************************************************
 115 %*                                                                      *
 116 \subsection[codeGen-for-non-escaping]{Generating code for a ``non-escaping let''}
 117 %*                                                                      *
 118 %************************************************************************
 119
 120
 121 Generating code for this is fun.  It is all very very similar to what
 122 we do for a case expression.  The duality is between
 123 \begin{verbatim}
 124         let-no-escape x = b
 125         in e
 126 \end{verbatim}
 127 and
 128 \begin{verbatim}
 129         case e of ... -> b
 130 \end{verbatim}
 131
 132 That is, the RHS of @x@ (ie @b@) will execute {\em later}, just like
 133 the alternative of the case; it needs to be compiled in an environment
 134 in which all volatile bindings are forgotten, and the free vars are
 135 bound only to stable things like stack locations..  The @e@ part will
 136 execute {\em next}, just like the scrutinee of a case.
 137
 138 First, we need to save all @x@'s free vars
 139 on the stack, if they aren't there already.
 140
 141 \begin{code}
 142 cgLetNoEscapeClosure
 143         :: Id                   -- binder
 144         -> CostCentreStack      -- NB: *** NOT USED *** ToDo (WDP 94/06)
 145         -> StgBinderInfo        -- NB: ditto
 146         -> StgLiveVars          -- variables live in RHS, including the binders
 147                                 -- themselves in the case of a recursive group
 148         -> EndOfBlockInfo       -- where are we going to?
 149         -> Maybe VirtualSpOffset -- Slot for current cost centre
 150         -> RecFlag              -- is the binding recursive?
 151         -> [Id]                 -- args (as in \ args -> body)
 152         -> StgExpr              -- body (as in above)
 153         -> FCode (Id, CgIdInfo)
 154
 155 -- ToDo: deal with the cost-centre issues
 156
 157 cgLetNoEscapeClosure
 158         bndr cc binder_info full_live_in_rhss
 159         rhs_eob_info cc_slot rec args body
 160   = let
 161         arity   = length args
 162         lf_info = mkLFLetNoEscape arity
 163     in
 164     -- saveVolatileVarsAndRegs done earlier in cgExpr.
 165
 166     do  { (vSp, _) <- forkEvalHelp rhs_eob_info
 167
 168                 (do { allocStackTop retAddrSizeW
 169                     ; nukeDeadBindings full_live_in_rhss })
 170
 171                 (do { deAllocStackTop retAddrSizeW
 172                     ; abs_c <- forkProc $ cgLetNoEscapeBody bndr cc
 173                                                   cc_slot args body
 174
 175                         -- Ignore the label that comes back from
 176                         -- mkRetDirectTarget.  It must be conjured up elswhere
 177                     ; emitReturnTarget (idName bndr) abs_c
 178                     ; return () })
 179
 180         ; returnFC (bndr, letNoEscapeIdInfo bndr vSp lf_info) }
 181 \end{code}
 182
 183 \begin{code}
 184 cgLetNoEscapeBody :: Id         -- Name of the joint point
 185                   -> CostCentreStack
 186                   -> Maybe VirtualSpOffset
 187                   -> [Id]       -- Args
 188                   -> StgExpr    -- Body
 189                   -> Code
 190
 191 cgLetNoEscapeBody bndr cc cc_slot all_args body = do
 192   { (arg_regs, ptrs, nptrs, ret_slot) <- bindUnboxedTupleComponents all_args
 193
 194      -- restore the saved cost centre.  BUT: we must not free the stack slot
 195      -- containing the cost centre, because it might be needed for a
 196      -- recursive call to this let-no-escape.
 197   ; restoreCurrentCostCentre cc_slot False{-don't free-}
 198
 199         -- Enter the closures cc, if required
 200   ; -- enterCostCentreCode closure_info cc IsFunction
 201
 202         -- The "return address" slot doesn't have a return address in it;
 203         -- but the heap-check needs it filled in if the heap-check fails.
 204         -- So we pass code to fill it in to the heap-check macro
 205   ; sp_rel <- getSpRelOffset ret_slot
 206
 207   ; let lbl            = mkReturnInfoLabel (idUnique bndr)
 208         frame_hdr_asst = oneStmt (CmmStore sp_rel (mkLblExpr lbl))
 209
 210         -- Do heap check [ToDo: omit for non-recursive case by recording in
 211         --      in envt and absorbing at call site]
 212   ; unbxTupleHeapCheck arg_regs ptrs nptrs frame_hdr_asst
 213                         (cgExpr body)
 214   }
 215 \end{code}