CgLetNoEscape.lhs 6.17 KB
Newer Older
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

15 16
IMP_Ubiq(){-uitious-}
IMPORT_DELOOPER(CgLoop2)		( cgExpr )
17

18 19 20 21
import StgSyn
import CgMonad
import AbsCSyn

22
import CgBindery	( letNoEscapeIdInfo, bindArgsToRegs,
23 24
			  bindNewToAStack, bindNewToBStack,
			  CgIdInfo
25
			)
26 27 28 29
import CgHeapery	( heapCheck )
import CgRetConv	( assignRegs )
import CgStackery	( mkVirtStkOffsets )
import CgUsages		( setRealAndVirtualSps, getVirtSps )
30
import CLabel		( mkStdEntryLabel )
31
import ClosureInfo	( mkLFLetNoEscape )
32
import HeapOffs		( SYN_IE(VirtualSpBOffset) )
33
import Id		( idPrimRep )
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
47 48
	in
	 	if ... then x else
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 ...
101
	in
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
138
	-> StgLiveVars	-- variables live in RHS, including the binders
139
				-- themselves in the case of a recursive group
140 141
	-> EndOfBlockInfo       -- where are we going to?
	-> Maybe VirtualSpBOffset -- Slot for current cost centre
142
	-> [Id]			-- args (as in \ args -> body)
143
    	-> StgExpr		-- body (as in above)
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
153 154
    forkEvalHelp
	rhs_eob_info
155
	(nukeDeadBindings full_live_in_rhss)
156
	(forkAbsC (cgLetNoEscapeBody args body))
157 158
	    	    	    	     	`thenFC` \ (vA, vB, code) ->
    let
159
	label = mkStdEntryLabel binder -- arity
160
    in
161
    absC (CCodeBlock label code) `thenC`
162 163 164 165 166
    returnFC (binder, letNoEscapeIdInfo binder vA vB lf_info)
\end{code}

\begin{code}
cgLetNoEscapeBody :: [Id]		-- Args
167
		  -> StgExpr	-- Body
168 169 170
		  -> Code

cgLetNoEscapeBody all_args rhs
171
  = getVirtSps		`thenFC` \ (vA, vB) ->
172
    let
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
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)
180
	  = mkVirtStkOffsets
181
		vA vB 		-- Initial virtual SpA, SpB
182
		idPrimRep
183 184 185 186
		stk_args
    in

	-- Bind args to appropriate regs/stk locns
187
    bindArgsToRegs reg_args arg_regs		    `thenC`
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}