<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<!-- Generated by HsColour, http://www.cs.york.ac.uk/fp/darcs/hscolour/ -->
<title>codeGen/CgLetNoEscape.lhs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
%
% (c) The University of Glasgow 2006
% (c) The GRASP/AQUA Project, Glasgow University, 1993-1998
%
%********************************************************
%* *
\section[CgLetNoEscape]{Handling ``let-no-escapes''}
%* *
%********************************************************
\begin{code}
<pre><a name="line-1"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>CgLetNoEscape</span> <span class='hs-layout'>(</span> <span class='hs-varid'>cgLetNoEscapeClosure</span> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-2"></a>
<a name="line-3"></a><span class='hs-cpp'>#include "HsVersions.h"</span>
<a name="line-4"></a>
<a name="line-5"></a><span class='hs-keyword'>import</span> <span class='hs-comment'>{-# SOURCE #-}</span> <span class='hs-conid'>CgExpr</span> <span class='hs-layout'>(</span> <span class='hs-varid'>cgExpr</span> <span class='hs-layout'>)</span>
<a name="line-6"></a>
<a name="line-7"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>StgSyn</span>
<a name="line-8"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>CgMonad</span>
<a name="line-9"></a>
<a name="line-10"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>CgBindery</span>
<a name="line-11"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>CgCase</span>
<a name="line-12"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>CgCon</span>
<a name="line-13"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>CgHeapery</span>
<a name="line-14"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>CgInfoTbls</span>
<a name="line-15"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>CgStackery</span>
<a name="line-16"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Cmm</span>
<a name="line-17"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>CmmUtils</span>
<a name="line-18"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>CLabel</span>
<a name="line-19"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>ClosureInfo</span>
<a name="line-20"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>CostCentre</span>
<a name="line-21"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Id</span>
<a name="line-22"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>SMRep</span>
<a name="line-23"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>BasicTypes</span>
</pre>\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
in
if ... then x else
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 when 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 ...
in
...(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}
<pre><a name="line-1"></a><a name="cgLetNoEscapeClosure"></a><span class='hs-definition'>cgLetNoEscapeClosure</span>
<a name="line-2"></a> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Id</span> <span class='hs-comment'>-- binder</span>
<a name="line-3"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>CostCentreStack</span> <span class='hs-comment'>-- NB: *** NOT USED *** ToDo (WDP 94/06)</span>
<a name="line-4"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>StgBinderInfo</span> <span class='hs-comment'>-- NB: ditto</span>
<a name="line-5"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>StgLiveVars</span> <span class='hs-comment'>-- variables live in RHS, including the binders</span>
<a name="line-6"></a> <span class='hs-comment'>-- themselves in the case of a recursive group</span>
<a name="line-7"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>EndOfBlockInfo</span> <span class='hs-comment'>-- where are we going to?</span>
<a name="line-8"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Maybe</span> <span class='hs-conid'>VirtualSpOffset</span> <span class='hs-comment'>-- Slot for current cost centre</span>
<a name="line-9"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>RecFlag</span> <span class='hs-comment'>-- is the binding recursive?</span>
<a name="line-10"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Id</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- args (as in \ args -> body)</span>
<a name="line-11"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>StgExpr</span> <span class='hs-comment'>-- body (as in above)</span>
<a name="line-12"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>FCode</span> <span class='hs-layout'>(</span><span class='hs-conid'>Id</span><span class='hs-layout'>,</span> <span class='hs-conid'>CgIdInfo</span><span class='hs-layout'>)</span>
<a name="line-13"></a>
<a name="line-14"></a><span class='hs-comment'>-- ToDo: deal with the cost-centre issues</span>
<a name="line-15"></a>
<a name="line-16"></a><span class='hs-definition'>cgLetNoEscapeClosure</span>
<a name="line-17"></a> <span class='hs-varid'>bndr</span> <span class='hs-varid'>cc</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>full_live_in_rhss</span>
<a name="line-18"></a> <span class='hs-varid'>rhs_eob_info</span> <span class='hs-varid'>cc_slot</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>args</span> <span class='hs-varid'>body</span>
<a name="line-19"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span>
<a name="line-20"></a> <span class='hs-varid'>arity</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>length</span> <span class='hs-varid'>args</span>
<a name="line-21"></a> <span class='hs-varid'>lf_info</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mkLFLetNoEscape</span> <span class='hs-varid'>arity</span>
<a name="line-22"></a> <span class='hs-keyword'>in</span>
<a name="line-23"></a> <span class='hs-comment'>-- saveVolatileVarsAndRegs done earlier in cgExpr.</span>
<a name="line-24"></a>
<a name="line-25"></a> <span class='hs-keyword'>do</span> <span class='hs-layout'>{</span> <span class='hs-layout'>(</span><span class='hs-varid'>vSp</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>forkEvalHelp</span> <span class='hs-varid'>rhs_eob_info</span>
<a name="line-26"></a>
<a name="line-27"></a> <span class='hs-layout'>(</span><span class='hs-keyword'>do</span> <span class='hs-layout'>{</span> <span class='hs-varid'>allocStackTop</span> <span class='hs-varid'>retAddrSizeW</span>
<a name="line-28"></a> <span class='hs-layout'>;</span> <span class='hs-varid'>nukeDeadBindings</span> <span class='hs-varid'>full_live_in_rhss</span> <span class='hs-layout'>}</span><span class='hs-layout'>)</span>
<a name="line-29"></a>
<a name="line-30"></a> <span class='hs-layout'>(</span><span class='hs-keyword'>do</span> <span class='hs-layout'>{</span> <span class='hs-varid'>deAllocStackTop</span> <span class='hs-varid'>retAddrSizeW</span>
<a name="line-31"></a> <span class='hs-layout'>;</span> <span class='hs-varid'>abs_c</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>forkProc</span> <span class='hs-varop'>$</span> <span class='hs-varid'>cgLetNoEscapeBody</span> <span class='hs-varid'>bndr</span> <span class='hs-varid'>cc</span>
<a name="line-32"></a> <span class='hs-varid'>cc_slot</span> <span class='hs-varid'>args</span> <span class='hs-varid'>body</span>
<a name="line-33"></a>
<a name="line-34"></a> <span class='hs-comment'>-- Ignore the label that comes back from</span>
<a name="line-35"></a> <span class='hs-comment'>-- mkRetDirectTarget. It must be conjured up elswhere</span>
<a name="line-36"></a> <span class='hs-layout'>;</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>emitReturnTarget</span> <span class='hs-layout'>(</span><span class='hs-varid'>idName</span> <span class='hs-varid'>bndr</span><span class='hs-layout'>)</span> <span class='hs-varid'>abs_c</span>
<a name="line-37"></a> <span class='hs-layout'>;</span> <span class='hs-varid'>return</span> <span class='hs-conid'>()</span> <span class='hs-layout'>}</span><span class='hs-layout'>)</span>
<a name="line-38"></a>
<a name="line-39"></a> <span class='hs-layout'>;</span> <span class='hs-varid'>returnFC</span> <span class='hs-layout'>(</span><span class='hs-varid'>bndr</span><span class='hs-layout'>,</span> <span class='hs-varid'>letNoEscapeIdInfo</span> <span class='hs-varid'>bndr</span> <span class='hs-varid'>vSp</span> <span class='hs-varid'>lf_info</span><span class='hs-layout'>)</span> <span class='hs-layout'>}</span>
</pre>\end{code}
\begin{code}
<pre><a name="line-1"></a><a name="cgLetNoEscapeBody"></a><span class='hs-definition'>cgLetNoEscapeBody</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Id</span> <span class='hs-comment'>-- Name of the joint point</span>
<a name="line-2"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>CostCentreStack</span>
<a name="line-3"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Maybe</span> <span class='hs-conid'>VirtualSpOffset</span>
<a name="line-4"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Id</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- Args</span>
<a name="line-5"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>StgExpr</span> <span class='hs-comment'>-- Body</span>
<a name="line-6"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Code</span>
<a name="line-7"></a>
<a name="line-8"></a><span class='hs-definition'>cgLetNoEscapeBody</span> <span class='hs-varid'>bndr</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>cc_slot</span> <span class='hs-varid'>all_args</span> <span class='hs-varid'>body</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-9"></a> <span class='hs-layout'>{</span> <span class='hs-layout'>(</span><span class='hs-varid'>arg_regs</span><span class='hs-layout'>,</span> <span class='hs-varid'>ptrs</span><span class='hs-layout'>,</span> <span class='hs-varid'>nptrs</span><span class='hs-layout'>,</span> <span class='hs-varid'>ret_slot</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>bindUnboxedTupleComponents</span> <span class='hs-varid'>all_args</span>
<a name="line-10"></a>
<a name="line-11"></a> <span class='hs-comment'>-- restore the saved cost centre. BUT: we must not free the stack slot</span>
<a name="line-12"></a> <span class='hs-comment'>-- containing the cost centre, because it might be needed for a</span>
<a name="line-13"></a> <span class='hs-comment'>-- recursive call to this let-no-escape.</span>
<a name="line-14"></a> <span class='hs-layout'>;</span> <span class='hs-varid'>restoreCurrentCostCentre</span> <span class='hs-varid'>cc_slot</span> <span class='hs-conid'>False</span><span class='hs-comment'>{-don't free-}</span>
<a name="line-15"></a>
<a name="line-16"></a> <span class='hs-comment'>-- Enter the closures cc, if required</span>
<a name="line-17"></a> <span class='hs-layout'>;</span> <span class='hs-comment'>-- enterCostCentreCode closure_info cc IsFunction</span>
<a name="line-18"></a>
<a name="line-19"></a> <span class='hs-comment'>-- The "return address" slot doesn't have a return address in it;</span>
<a name="line-20"></a> <span class='hs-comment'>-- but the heap-check needs it filled in if the heap-check fails.</span>
<a name="line-21"></a> <span class='hs-comment'>-- So we pass code to fill it in to the heap-check macro</span>
<a name="line-22"></a> <span class='hs-layout'>;</span> <span class='hs-varid'>sp_rel</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>getSpRelOffset</span> <span class='hs-varid'>ret_slot</span>
<a name="line-23"></a>
<a name="line-24"></a> <span class='hs-layout'>;</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>lbl</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mkReturnInfoLabel</span> <span class='hs-layout'>(</span><span class='hs-varid'>idUnique</span> <span class='hs-varid'>bndr</span><span class='hs-layout'>)</span>
<a name="line-25"></a> <span class='hs-varid'>frame_hdr_asst</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>oneStmt</span> <span class='hs-layout'>(</span><span class='hs-conid'>CmmStore</span> <span class='hs-varid'>sp_rel</span> <span class='hs-layout'>(</span><span class='hs-varid'>mkLblExpr</span> <span class='hs-varid'>lbl</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-26"></a>
<a name="line-27"></a> <span class='hs-comment'>-- Do heap check [ToDo: omit for non-recursive case by recording in</span>
<a name="line-28"></a> <span class='hs-comment'>-- in envt and absorbing at call site]</span>
<a name="line-29"></a> <span class='hs-layout'>;</span> <span class='hs-varid'>unbxTupleHeapCheck</span> <span class='hs-varid'>arg_regs</span> <span class='hs-varid'>ptrs</span> <span class='hs-varid'>nptrs</span> <span class='hs-varid'>frame_hdr_asst</span>
<a name="line-30"></a> <span class='hs-layout'>(</span><span class='hs-varid'>cgExpr</span> <span class='hs-varid'>body</span><span class='hs-layout'>)</span>
<a name="line-31"></a> <span class='hs-layout'>}</span>
</pre>\end{code}
</body>
</html>
