<?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>