<?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>simplCore/SAT.lhs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
%
% (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
%
%************************************************************************
Static Argument Transformation pass
%************************************************************************
May be seen as removing invariants from loops:
Arguments of recursive functions that do not change in recursive
calls are removed from the recursion, which is done locally
and only passes the arguments which effectively change.
Example:
map = /\ ab -> \f -> \xs -> case xs of
[] -> []
(a:b) -> f a : map f b
as map is recursively called with the same argument f (unmodified)
we transform it to
map = /\ ab -> \f -> \xs -> let map' ys = case ys of
[] -> []
(a:b) -> f a : map' b
in map' xs
Notice that for a compiler that uses lambda lifting this is
useless as map' will be transformed back to what map was.
We could possibly do the same for big lambdas, but we don't as
they will eventually be removed in later stages of the compiler,
therefore there is no penalty in keeping them.
We only apply the SAT when the number of static args is > 2. This
produces few bad cases. See
should_transform
in saTransform.
Here are the headline nofib results:
Size Allocs Runtime
Min +0.0% -13.7% -21.4%
Max +0.1% +0.0% +5.4%
Geometric Mean +0.0% -0.2% -6.9%
The previous patch, to fix polymorphic floatout demand signatures, is
essential to make this work well!
\begin{code}
<pre><a name="line-1"></a>
<a name="line-2"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>SAT</span> <span class='hs-layout'>(</span> <span class='hs-varid'>doStaticArgs</span> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-3"></a>
<a name="line-4"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Var</span>
<a name="line-5"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>CoreSyn</span>
<a name="line-6"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>CoreUtils</span>
<a name="line-7"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Type</span>
<a name="line-8"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Id</span>
<a name="line-9"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Name</span>
<a name="line-10"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>VarEnv</span>
<a name="line-11"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>UniqSupply</span>
<a name="line-12"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Util</span>
<a name="line-13"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>UniqFM</span>
<a name="line-14"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>VarSet</span>
<a name="line-15"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Unique</span>
<a name="line-16"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>UniqSet</span>
<a name="line-17"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Outputable</span>
<a name="line-18"></a>
<a name="line-19"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>List</span>
<a name="line-20"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>FastString</span>
<a name="line-21"></a>
<a name="line-22"></a><span class='hs-cpp'>#include "HsVersions.h"</span>
</pre>\end{code}
\begin{code}
<pre><a name="line-1"></a><a name="doStaticArgs"></a><span class='hs-definition'>doStaticArgs</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>UniqSupply</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>CoreBind</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>CoreBind</span><span class='hs-keyglyph'>]</span>
<a name="line-2"></a><span class='hs-definition'>doStaticArgs</span> <span class='hs-varid'>us</span> <span class='hs-varid'>binds</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>snd</span> <span class='hs-varop'>$</span> <span class='hs-varid'>mapAccumL</span> <span class='hs-varid'>sat_bind_threaded_us</span> <span class='hs-varid'>us</span> <span class='hs-varid'>binds</span>
<a name="line-3"></a> <span class='hs-keyword'>where</span>
<a name="line-4"></a> <span class='hs-varid'>sat_bind_threaded_us</span> <span class='hs-varid'>us</span> <span class='hs-varid'>bind</span> <span class='hs-keyglyph'>=</span>
<a name="line-5"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>us1</span><span class='hs-layout'>,</span> <span class='hs-varid'>us2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>splitUniqSupply</span> <span class='hs-varid'>us</span>
<a name="line-6"></a> <span class='hs-keyword'>in</span> <span class='hs-layout'>(</span><span class='hs-varid'>us1</span><span class='hs-layout'>,</span> <span class='hs-varid'>fst</span> <span class='hs-varop'>$</span> <span class='hs-varid'>runSAT</span> <span class='hs-varid'>us2</span> <span class='hs-layout'>(</span><span class='hs-varid'>satBind</span> <span class='hs-varid'>bind</span> <span class='hs-varid'>emptyUniqSet</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
</pre>\end{code}
\begin{code}
<pre><a name="line-1"></a><a name="satBind"></a><span class='hs-comment'>-- We don't bother to SAT recursive groups since it can lead</span>
<a name="line-2"></a><span class='hs-comment'>-- to massive code expansion: see Andre Santos' thesis for details.</span>
<a name="line-3"></a><span class='hs-comment'>-- This means we only apply the actual SAT to Rec groups of one element,</span>
<a name="line-4"></a><span class='hs-comment'>-- but we want to recurse into the others anyway to discover other binds</span>
<a name="line-5"></a><span class='hs-definition'>satBind</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>CoreBind</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IdSet</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SatM</span> <span class='hs-layout'>(</span><span class='hs-conid'>CoreBind</span><span class='hs-layout'>,</span> <span class='hs-conid'>IdSATInfo</span><span class='hs-layout'>)</span>
<a name="line-6"></a><span class='hs-definition'>satBind</span> <span class='hs-layout'>(</span><span class='hs-conid'>NonRec</span> <span class='hs-varid'>binder</span> <span class='hs-varid'>expr</span><span class='hs-layout'>)</span> <span class='hs-varid'>interesting_ids</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-7"></a> <span class='hs-layout'>(</span><span class='hs-varid'>expr'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_expr</span><span class='hs-layout'>,</span> <span class='hs-varid'>expr_app</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>satExpr</span> <span class='hs-varid'>expr</span> <span class='hs-varid'>interesting_ids</span>
<a name="line-8"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-conid'>NonRec</span> <span class='hs-varid'>binder</span> <span class='hs-varid'>expr'</span><span class='hs-layout'>,</span> <span class='hs-varid'>finalizeApp</span> <span class='hs-varid'>expr_app</span> <span class='hs-varid'>sat_info_expr</span><span class='hs-layout'>)</span>
<a name="line-9"></a><span class='hs-definition'>satBind</span> <span class='hs-layout'>(</span><span class='hs-conid'>Rec</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>binder</span><span class='hs-layout'>,</span> <span class='hs-varid'>rhs</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span> <span class='hs-varid'>interesting_ids</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-10"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>interesting_ids'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>interesting_ids</span> <span class='hs-varop'>`addOneToUniqSet`</span> <span class='hs-varid'>binder</span>
<a name="line-11"></a> <span class='hs-layout'>(</span><span class='hs-varid'>rhs_binders</span><span class='hs-layout'>,</span> <span class='hs-varid'>rhs_body</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>collectBinders</span> <span class='hs-varid'>rhs</span>
<a name="line-12"></a> <span class='hs-layout'>(</span><span class='hs-varid'>rhs_body'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_rhs_body</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>satTopLevelExpr</span> <span class='hs-varid'>rhs_body</span> <span class='hs-varid'>interesting_ids'</span>
<a name="line-13"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>sat_info_rhs_from_args</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>unitVarEnv</span> <span class='hs-varid'>binder</span> <span class='hs-layout'>(</span><span class='hs-varid'>bindersToSATInfo</span> <span class='hs-varid'>rhs_binders</span><span class='hs-layout'>)</span>
<a name="line-14"></a> <span class='hs-varid'>sat_info_rhs'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mergeIdSATInfo</span> <span class='hs-varid'>sat_info_rhs_from_args</span> <span class='hs-varid'>sat_info_rhs_body</span>
<a name="line-15"></a>
<a name="line-16"></a> <span class='hs-varid'>shadowing</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>binder</span> <span class='hs-varop'>`elementOfUniqSet`</span> <span class='hs-varid'>interesting_ids</span>
<a name="line-17"></a> <span class='hs-varid'>sat_info_rhs''</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>shadowing</span>
<a name="line-18"></a> <span class='hs-keyword'>then</span> <span class='hs-varid'>sat_info_rhs'</span> <span class='hs-varop'>`delFromUFM`</span> <span class='hs-varid'>binder</span> <span class='hs-comment'>-- For safety</span>
<a name="line-19"></a> <span class='hs-keyword'>else</span> <span class='hs-varid'>sat_info_rhs'</span>
<a name="line-20"></a>
<a name="line-21"></a> <span class='hs-varid'>bind'</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>saTransformMaybe</span> <span class='hs-varid'>binder</span> <span class='hs-layout'>(</span><span class='hs-varid'>lookupUFM</span> <span class='hs-varid'>sat_info_rhs'</span> <span class='hs-varid'>binder</span><span class='hs-layout'>)</span>
<a name="line-22"></a> <span class='hs-varid'>rhs_binders</span> <span class='hs-varid'>rhs_body'</span>
<a name="line-23"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>bind'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_rhs''</span><span class='hs-layout'>)</span>
<a name="line-24"></a><span class='hs-definition'>satBind</span> <span class='hs-layout'>(</span><span class='hs-conid'>Rec</span> <span class='hs-varid'>pairs</span><span class='hs-layout'>)</span> <span class='hs-varid'>interesting_ids</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-25"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>binders</span><span class='hs-layout'>,</span> <span class='hs-varid'>rhss</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>unzip</span> <span class='hs-varid'>pairs</span>
<a name="line-26"></a> <span class='hs-varid'>rhss_SATed</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>mapM</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>e</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>satTopLevelExpr</span> <span class='hs-varid'>e</span> <span class='hs-varid'>interesting_ids</span><span class='hs-layout'>)</span> <span class='hs-varid'>rhss</span>
<a name="line-27"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>rhss'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_rhss'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>unzip</span> <span class='hs-varid'>rhss_SATed</span>
<a name="line-28"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-conid'>Rec</span> <span class='hs-layout'>(</span><span class='hs-varid'>zipEqual</span> <span class='hs-str'>"satBind"</span> <span class='hs-varid'>binders</span> <span class='hs-varid'>rhss'</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>mergeIdSATInfos</span> <span class='hs-varid'>sat_info_rhss'</span><span class='hs-layout'>)</span>
</pre>\end{code}
\begin{code}
<pre><a name="line-1"></a><a name="App"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>App</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>VarApp</span> <span class='hs-conid'>Id</span> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>TypeApp</span> <span class='hs-conid'>Type</span>
<a name="line-2"></a><a name="Staticness"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>Staticness</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Static</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>NotStatic</span>
<a name="line-3"></a>
<a name="line-4"></a><a name="IdAppInfo"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>IdAppInfo</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-conid'>Id</span><span class='hs-layout'>,</span> <span class='hs-conid'>SATInfo</span><span class='hs-layout'>)</span>
<a name="line-5"></a>
<a name="line-6"></a><a name="SATInfo"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>SATInfo</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Staticness</span> <span class='hs-conid'>App</span><span class='hs-keyglyph'>]</span>
<a name="line-7"></a><a name="IdSATInfo"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>IdSATInfo</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>IdEnv</span> <span class='hs-conid'>SATInfo</span>
<a name="line-8"></a><a name="emptyIdSATInfo"></a><span class='hs-definition'>emptyIdSATInfo</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>IdSATInfo</span>
<a name="line-9"></a><span class='hs-definition'>emptyIdSATInfo</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>emptyUFM</span>
<a name="line-10"></a>
<a name="line-11"></a><span class='hs-comment'>{-
<a name="line-12"></a>pprIdSATInfo id_sat_info = vcat (map pprIdAndSATInfo (fmToList id_sat_info))
<a name="line-13"></a> where pprIdAndSATInfo (v, sat_info) = hang (ppr v <> colon) 4 (pprSATInfo sat_info)
<a name="line-14"></a>-}</span>
<a name="line-15"></a>
<a name="line-16"></a><a name="pprSATInfo"></a><span class='hs-definition'>pprSATInfo</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>SATInfo</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SDoc</span>
<a name="line-17"></a><span class='hs-definition'>pprSATInfo</span> <span class='hs-varid'>staticness</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>hcat</span> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-varid'>pprStaticness</span> <span class='hs-varid'>staticness</span>
<a name="line-18"></a>
<a name="line-19"></a><a name="pprStaticness"></a><span class='hs-definition'>pprStaticness</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Staticness</span> <span class='hs-conid'>App</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SDoc</span>
<a name="line-20"></a><span class='hs-definition'>pprStaticness</span> <span class='hs-layout'>(</span><span class='hs-conid'>Static</span> <span class='hs-layout'>(</span><span class='hs-conid'>VarApp</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ptext</span> <span class='hs-layout'>(</span><span class='hs-varid'>sLit</span> <span class='hs-str'>"SV"</span><span class='hs-layout'>)</span>
<a name="line-21"></a><span class='hs-definition'>pprStaticness</span> <span class='hs-layout'>(</span><span class='hs-conid'>Static</span> <span class='hs-layout'>(</span><span class='hs-conid'>TypeApp</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ptext</span> <span class='hs-layout'>(</span><span class='hs-varid'>sLit</span> <span class='hs-str'>"ST"</span><span class='hs-layout'>)</span>
<a name="line-22"></a><span class='hs-definition'>pprStaticness</span> <span class='hs-conid'>NotStatic</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ptext</span> <span class='hs-layout'>(</span><span class='hs-varid'>sLit</span> <span class='hs-str'>"NS"</span><span class='hs-layout'>)</span>
<a name="line-23"></a>
<a name="line-24"></a>
<a name="line-25"></a><a name="mergeSATInfo"></a><span class='hs-definition'>mergeSATInfo</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>SATInfo</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SATInfo</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SATInfo</span>
<a name="line-26"></a><span class='hs-definition'>mergeSATInfo</span> <span class='hs-conid'>[]</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-27"></a><span class='hs-definition'>mergeSATInfo</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-28"></a><span class='hs-definition'>mergeSATInfo</span> <span class='hs-layout'>(</span><span class='hs-conid'>NotStatic</span><span class='hs-conop'>:</span><span class='hs-varid'>statics</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>apps</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>NotStatic</span> <span class='hs-conop'>:</span> <span class='hs-varid'>mergeSATInfo</span> <span class='hs-varid'>statics</span> <span class='hs-varid'>apps</span>
<a name="line-29"></a><span class='hs-definition'>mergeSATInfo</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-conop'>:</span><span class='hs-varid'>statics</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>NotStatic</span><span class='hs-conop'>:</span><span class='hs-varid'>apps</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>NotStatic</span> <span class='hs-conop'>:</span> <span class='hs-varid'>mergeSATInfo</span> <span class='hs-varid'>statics</span> <span class='hs-varid'>apps</span>
<a name="line-30"></a><span class='hs-definition'>mergeSATInfo</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-conid'>Static</span> <span class='hs-layout'>(</span><span class='hs-conid'>VarApp</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>statics</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-conid'>Static</span> <span class='hs-layout'>(</span><span class='hs-conid'>VarApp</span> <span class='hs-varid'>v'</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>apps</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-keyword'>if</span> <span class='hs-varid'>v</span> <span class='hs-varop'>==</span> <span class='hs-varid'>v'</span> <span class='hs-keyword'>then</span> <span class='hs-conid'>Static</span> <span class='hs-layout'>(</span><span class='hs-conid'>VarApp</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyword'>else</span> <span class='hs-conid'>NotStatic</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-varid'>mergeSATInfo</span> <span class='hs-varid'>statics</span> <span class='hs-varid'>apps</span>
<a name="line-31"></a><span class='hs-definition'>mergeSATInfo</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-conid'>Static</span> <span class='hs-layout'>(</span><span class='hs-conid'>TypeApp</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>statics</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-conid'>Static</span> <span class='hs-layout'>(</span><span class='hs-conid'>TypeApp</span> <span class='hs-varid'>t'</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>apps</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-keyword'>if</span> <span class='hs-varid'>t</span> <span class='hs-varop'>`coreEqType`</span> <span class='hs-varid'>t'</span> <span class='hs-keyword'>then</span> <span class='hs-conid'>Static</span> <span class='hs-layout'>(</span><span class='hs-conid'>TypeApp</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span> <span class='hs-keyword'>else</span> <span class='hs-conid'>NotStatic</span><span class='hs-layout'>)</span> <span class='hs-conop'>:</span> <span class='hs-varid'>mergeSATInfo</span> <span class='hs-varid'>statics</span> <span class='hs-varid'>apps</span>
<a name="line-32"></a><span class='hs-definition'>mergeSATInfo</span> <span class='hs-varid'>l</span> <span class='hs-varid'>r</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pprPanic</span> <span class='hs-str'>"mergeSATInfo"</span> <span class='hs-varop'>$</span> <span class='hs-varid'>ptext</span> <span class='hs-layout'>(</span><span class='hs-varid'>sLit</span> <span class='hs-str'>"Left:"</span><span class='hs-layout'>)</span> <span class='hs-varop'><></span> <span class='hs-varid'>pprSATInfo</span> <span class='hs-varid'>l</span> <span class='hs-varop'><></span> <span class='hs-varid'>ptext</span> <span class='hs-layout'>(</span><span class='hs-varid'>sLit</span> <span class='hs-str'>", "</span><span class='hs-layout'>)</span>
<a name="line-33"></a> <span class='hs-varop'><></span> <span class='hs-varid'>ptext</span> <span class='hs-layout'>(</span><span class='hs-varid'>sLit</span> <span class='hs-str'>"Right:"</span><span class='hs-layout'>)</span> <span class='hs-varop'><></span> <span class='hs-varid'>pprSATInfo</span> <span class='hs-varid'>r</span>
<a name="line-34"></a>
<a name="line-35"></a><a name="mergeIdSATInfo"></a><span class='hs-definition'>mergeIdSATInfo</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>IdSATInfo</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IdSATInfo</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IdSATInfo</span>
<a name="line-36"></a><span class='hs-definition'>mergeIdSATInfo</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>plusUFM_C</span> <span class='hs-varid'>mergeSATInfo</span>
<a name="line-37"></a>
<a name="line-38"></a><a name="mergeIdSATInfos"></a><span class='hs-definition'>mergeIdSATInfos</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>IdSATInfo</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IdSATInfo</span>
<a name="line-39"></a><span class='hs-definition'>mergeIdSATInfos</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldl'</span> <span class='hs-varid'>mergeIdSATInfo</span> <span class='hs-varid'>emptyIdSATInfo</span>
<a name="line-40"></a>
<a name="line-41"></a><a name="bindersToSATInfo"></a><span class='hs-definition'>bindersToSATInfo</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Id</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SATInfo</span>
<a name="line-42"></a><span class='hs-definition'>bindersToSATInfo</span> <span class='hs-varid'>vs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>map</span> <span class='hs-layout'>(</span><span class='hs-conid'>Static</span> <span class='hs-varop'>.</span> <span class='hs-varid'>binderToApp</span><span class='hs-layout'>)</span> <span class='hs-varid'>vs</span>
<a name="line-43"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>binderToApp</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>isId</span> <span class='hs-varid'>v</span>
<a name="line-44"></a> <span class='hs-keyword'>then</span> <span class='hs-conid'>VarApp</span> <span class='hs-varid'>v</span>
<a name="line-45"></a> <span class='hs-keyword'>else</span> <span class='hs-conid'>TypeApp</span> <span class='hs-varop'>$</span> <span class='hs-varid'>mkTyVarTy</span> <span class='hs-varid'>v</span>
<a name="line-46"></a>
<a name="line-47"></a><a name="finalizeApp"></a><span class='hs-definition'>finalizeApp</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Maybe</span> <span class='hs-conid'>IdAppInfo</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IdSATInfo</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IdSATInfo</span>
<a name="line-48"></a><span class='hs-definition'>finalizeApp</span> <span class='hs-conid'>Nothing</span> <span class='hs-varid'>id_sat_info</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>id_sat_info</span>
<a name="line-49"></a><span class='hs-definition'>finalizeApp</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>v</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info'</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varid'>id_sat_info</span> <span class='hs-keyglyph'>=</span>
<a name="line-50"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>sat_info''</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>lookupUFM</span> <span class='hs-varid'>id_sat_info</span> <span class='hs-varid'>v</span> <span class='hs-keyword'>of</span>
<a name="line-51"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>sat_info'</span>
<a name="line-52"></a> <span class='hs-conid'>Just</span> <span class='hs-varid'>sat_info</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>mergeSATInfo</span> <span class='hs-varid'>sat_info</span> <span class='hs-varid'>sat_info'</span>
<a name="line-53"></a> <span class='hs-keyword'>in</span> <span class='hs-varid'>extendVarEnv</span> <span class='hs-varid'>id_sat_info</span> <span class='hs-varid'>v</span> <span class='hs-varid'>sat_info''</span>
</pre>\end{code}
\begin{code}
<pre><a name="line-1"></a><a name="satTopLevelExpr"></a><span class='hs-definition'>satTopLevelExpr</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>CoreExpr</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IdSet</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SatM</span> <span class='hs-layout'>(</span><span class='hs-conid'>CoreExpr</span><span class='hs-layout'>,</span> <span class='hs-conid'>IdSATInfo</span><span class='hs-layout'>)</span>
<a name="line-2"></a><span class='hs-definition'>satTopLevelExpr</span> <span class='hs-varid'>expr</span> <span class='hs-varid'>interesting_ids</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-3"></a> <span class='hs-layout'>(</span><span class='hs-varid'>expr'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_expr</span><span class='hs-layout'>,</span> <span class='hs-varid'>expr_app</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>satExpr</span> <span class='hs-varid'>expr</span> <span class='hs-varid'>interesting_ids</span>
<a name="line-4"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>expr'</span><span class='hs-layout'>,</span> <span class='hs-varid'>finalizeApp</span> <span class='hs-varid'>expr_app</span> <span class='hs-varid'>sat_info_expr</span><span class='hs-layout'>)</span>
<a name="line-5"></a>
<a name="line-6"></a><a name="satExpr"></a><span class='hs-definition'>satExpr</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>CoreExpr</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IdSet</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SatM</span> <span class='hs-layout'>(</span><span class='hs-conid'>CoreExpr</span><span class='hs-layout'>,</span> <span class='hs-conid'>IdSATInfo</span><span class='hs-layout'>,</span> <span class='hs-conid'>Maybe</span> <span class='hs-conid'>IdAppInfo</span><span class='hs-layout'>)</span>
<a name="line-7"></a><span class='hs-definition'>satExpr</span> <span class='hs-varid'>var</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Var</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-varid'>interesting_ids</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-8"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>app_info</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>v</span> <span class='hs-varop'>`elementOfUniqSet`</span> <span class='hs-varid'>interesting_ids</span>
<a name="line-9"></a> <span class='hs-keyword'>then</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>v</span><span class='hs-layout'>,</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span>
<a name="line-10"></a> <span class='hs-keyword'>else</span> <span class='hs-conid'>Nothing</span>
<a name="line-11"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>var</span><span class='hs-layout'>,</span> <span class='hs-varid'>emptyIdSATInfo</span><span class='hs-layout'>,</span> <span class='hs-varid'>app_info</span><span class='hs-layout'>)</span>
<a name="line-12"></a>
<a name="line-13"></a><span class='hs-definition'>satExpr</span> <span class='hs-varid'>lit</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Lit</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-14"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>lit</span><span class='hs-layout'>,</span> <span class='hs-varid'>emptyIdSATInfo</span><span class='hs-layout'>,</span> <span class='hs-conid'>Nothing</span><span class='hs-layout'>)</span>
<a name="line-15"></a>
<a name="line-16"></a><span class='hs-definition'>satExpr</span> <span class='hs-layout'>(</span><span class='hs-conid'>Lam</span> <span class='hs-varid'>binders</span> <span class='hs-varid'>body</span><span class='hs-layout'>)</span> <span class='hs-varid'>interesting_ids</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-17"></a> <span class='hs-layout'>(</span><span class='hs-varid'>body'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info</span><span class='hs-layout'>,</span> <span class='hs-varid'>this_app</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>satExpr</span> <span class='hs-varid'>body</span> <span class='hs-varid'>interesting_ids</span>
<a name="line-18"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-conid'>Lam</span> <span class='hs-varid'>binders</span> <span class='hs-varid'>body'</span><span class='hs-layout'>,</span> <span class='hs-varid'>finalizeApp</span> <span class='hs-varid'>this_app</span> <span class='hs-varid'>sat_info</span><span class='hs-layout'>,</span> <span class='hs-conid'>Nothing</span><span class='hs-layout'>)</span>
<a name="line-19"></a>
<a name="line-20"></a><span class='hs-definition'>satExpr</span> <span class='hs-layout'>(</span><span class='hs-conid'>App</span> <span class='hs-varid'>fn</span> <span class='hs-varid'>arg</span><span class='hs-layout'>)</span> <span class='hs-varid'>interesting_ids</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-21"></a> <span class='hs-layout'>(</span><span class='hs-varid'>fn'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_fn</span><span class='hs-layout'>,</span> <span class='hs-varid'>fn_app</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>satExpr</span> <span class='hs-varid'>fn</span> <span class='hs-varid'>interesting_ids</span>
<a name="line-22"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>satRemainder</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>boring</span> <span class='hs-varid'>fn'</span> <span class='hs-varid'>sat_info_fn</span>
<a name="line-23"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>fn_app</span> <span class='hs-keyword'>of</span>
<a name="line-24"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>satRemainder</span> <span class='hs-conid'>Nothing</span>
<a name="line-25"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>fn_id</span><span class='hs-layout'>,</span> <span class='hs-varid'>fn_app_info</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span>
<a name="line-26"></a> <span class='hs-comment'>-- TODO: remove this use of append somehow (use a data structure with O(1) append but a left-to-right kind of interface)</span>
<a name="line-27"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>satRemainderWithStaticness</span> <span class='hs-varid'>arg_staticness</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>satRemainder</span> <span class='hs-varop'>$</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>fn_id</span><span class='hs-layout'>,</span> <span class='hs-varid'>fn_app_info</span> <span class='hs-varop'>++</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>arg_staticness</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span>
<a name="line-28"></a> <span class='hs-keyword'>in</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>arg</span> <span class='hs-keyword'>of</span>
<a name="line-29"></a> <span class='hs-conid'>Type</span> <span class='hs-varid'>t</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>satRemainderWithStaticness</span> <span class='hs-varop'>$</span> <span class='hs-conid'>Static</span> <span class='hs-layout'>(</span><span class='hs-conid'>TypeApp</span> <span class='hs-varid'>t</span><span class='hs-layout'>)</span>
<a name="line-30"></a> <span class='hs-conid'>Var</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>satRemainderWithStaticness</span> <span class='hs-varop'>$</span> <span class='hs-conid'>Static</span> <span class='hs-layout'>(</span><span class='hs-conid'>VarApp</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span>
<a name="line-31"></a> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>satRemainderWithStaticness</span> <span class='hs-varop'>$</span> <span class='hs-conid'>NotStatic</span>
<a name="line-32"></a> <span class='hs-keyword'>where</span>
<a name="line-33"></a> <span class='hs-varid'>boring</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>CoreExpr</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>IdSATInfo</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Maybe</span> <span class='hs-conid'>IdAppInfo</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SatM</span> <span class='hs-layout'>(</span><span class='hs-conid'>CoreExpr</span><span class='hs-layout'>,</span> <span class='hs-conid'>IdSATInfo</span><span class='hs-layout'>,</span> <span class='hs-conid'>Maybe</span> <span class='hs-conid'>IdAppInfo</span><span class='hs-layout'>)</span>
<a name="line-34"></a> <span class='hs-varid'>boring</span> <span class='hs-varid'>fn'</span> <span class='hs-varid'>sat_info_fn</span> <span class='hs-varid'>app_info</span> <span class='hs-keyglyph'>=</span>
<a name="line-35"></a> <span class='hs-keyword'>do</span> <span class='hs-layout'>(</span><span class='hs-varid'>arg'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_arg</span><span class='hs-layout'>,</span> <span class='hs-varid'>arg_app</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>satExpr</span> <span class='hs-varid'>arg</span> <span class='hs-varid'>interesting_ids</span>
<a name="line-36"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>sat_info_arg'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>finalizeApp</span> <span class='hs-varid'>arg_app</span> <span class='hs-varid'>sat_info_arg</span>
<a name="line-37"></a> <span class='hs-varid'>sat_info</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mergeIdSATInfo</span> <span class='hs-varid'>sat_info_fn</span> <span class='hs-varid'>sat_info_arg'</span>
<a name="line-38"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-conid'>App</span> <span class='hs-varid'>fn'</span> <span class='hs-varid'>arg'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info</span><span class='hs-layout'>,</span> <span class='hs-varid'>app_info</span><span class='hs-layout'>)</span>
<a name="line-39"></a>
<a name="line-40"></a><span class='hs-definition'>satExpr</span> <span class='hs-layout'>(</span><span class='hs-conid'>Case</span> <span class='hs-varid'>expr</span> <span class='hs-varid'>bndr</span> <span class='hs-varid'>ty</span> <span class='hs-varid'>alts</span><span class='hs-layout'>)</span> <span class='hs-varid'>interesting_ids</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-41"></a> <span class='hs-layout'>(</span><span class='hs-varid'>expr'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_expr</span><span class='hs-layout'>,</span> <span class='hs-varid'>expr_app</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>satExpr</span> <span class='hs-varid'>expr</span> <span class='hs-varid'>interesting_ids</span>
<a name="line-42"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>sat_info_expr'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>finalizeApp</span> <span class='hs-varid'>expr_app</span> <span class='hs-varid'>sat_info_expr</span>
<a name="line-43"></a>
<a name="line-44"></a> <span class='hs-varid'>zipped_alts'</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>mapM</span> <span class='hs-varid'>satAlt</span> <span class='hs-varid'>alts</span>
<a name="line-45"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>alts'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_infos_alts</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>unzip</span> <span class='hs-varid'>zipped_alts'</span>
<a name="line-46"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-conid'>Case</span> <span class='hs-varid'>expr'</span> <span class='hs-varid'>bndr</span> <span class='hs-varid'>ty</span> <span class='hs-varid'>alts'</span><span class='hs-layout'>,</span> <span class='hs-varid'>mergeIdSATInfo</span> <span class='hs-varid'>sat_info_expr'</span> <span class='hs-layout'>(</span><span class='hs-varid'>mergeIdSATInfos</span> <span class='hs-varid'>sat_infos_alts</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-conid'>Nothing</span><span class='hs-layout'>)</span>
<a name="line-47"></a> <span class='hs-keyword'>where</span>
<a name="line-48"></a> <span class='hs-varid'>satAlt</span> <span class='hs-layout'>(</span><span class='hs-varid'>con</span><span class='hs-layout'>,</span> <span class='hs-varid'>bndrs</span><span class='hs-layout'>,</span> <span class='hs-varid'>expr</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-49"></a> <span class='hs-layout'>(</span><span class='hs-varid'>expr'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_expr</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>satTopLevelExpr</span> <span class='hs-varid'>expr</span> <span class='hs-varid'>interesting_ids</span>
<a name="line-50"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>con</span><span class='hs-layout'>,</span> <span class='hs-varid'>bndrs</span><span class='hs-layout'>,</span> <span class='hs-varid'>expr'</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_expr</span><span class='hs-layout'>)</span>
<a name="line-51"></a>
<a name="line-52"></a><span class='hs-definition'>satExpr</span> <span class='hs-layout'>(</span><span class='hs-conid'>Let</span> <span class='hs-varid'>bind</span> <span class='hs-varid'>body</span><span class='hs-layout'>)</span> <span class='hs-varid'>interesting_ids</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-53"></a> <span class='hs-layout'>(</span><span class='hs-varid'>body'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_body</span><span class='hs-layout'>,</span> <span class='hs-varid'>body_app</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>satExpr</span> <span class='hs-varid'>body</span> <span class='hs-varid'>interesting_ids</span>
<a name="line-54"></a> <span class='hs-layout'>(</span><span class='hs-varid'>bind'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_bind</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>satBind</span> <span class='hs-varid'>bind</span> <span class='hs-varid'>interesting_ids</span>
<a name="line-55"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-conid'>Let</span> <span class='hs-varid'>bind'</span> <span class='hs-varid'>body'</span><span class='hs-layout'>,</span> <span class='hs-varid'>mergeIdSATInfo</span> <span class='hs-varid'>sat_info_body</span> <span class='hs-varid'>sat_info_bind</span><span class='hs-layout'>,</span> <span class='hs-varid'>body_app</span><span class='hs-layout'>)</span>
<a name="line-56"></a>
<a name="line-57"></a><span class='hs-definition'>satExpr</span> <span class='hs-layout'>(</span><span class='hs-conid'>Note</span> <span class='hs-varid'>note</span> <span class='hs-varid'>expr</span><span class='hs-layout'>)</span> <span class='hs-varid'>interesting_ids</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-58"></a> <span class='hs-layout'>(</span><span class='hs-varid'>expr'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_expr</span><span class='hs-layout'>,</span> <span class='hs-varid'>expr_app</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>satExpr</span> <span class='hs-varid'>expr</span> <span class='hs-varid'>interesting_ids</span>
<a name="line-59"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-conid'>Note</span> <span class='hs-varid'>note</span> <span class='hs-varid'>expr'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_expr</span><span class='hs-layout'>,</span> <span class='hs-varid'>expr_app</span><span class='hs-layout'>)</span>
<a name="line-60"></a>
<a name="line-61"></a><span class='hs-definition'>satExpr</span> <span class='hs-varid'>ty</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Type</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-62"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>ty</span><span class='hs-layout'>,</span> <span class='hs-varid'>emptyIdSATInfo</span><span class='hs-layout'>,</span> <span class='hs-conid'>Nothing</span><span class='hs-layout'>)</span>
<a name="line-63"></a>
<a name="line-64"></a><span class='hs-definition'>satExpr</span> <span class='hs-layout'>(</span><span class='hs-conid'>Cast</span> <span class='hs-varid'>expr</span> <span class='hs-varid'>coercion</span><span class='hs-layout'>)</span> <span class='hs-varid'>interesting_ids</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-65"></a> <span class='hs-layout'>(</span><span class='hs-varid'>expr'</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_expr</span><span class='hs-layout'>,</span> <span class='hs-varid'>expr_app</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>satExpr</span> <span class='hs-varid'>expr</span> <span class='hs-varid'>interesting_ids</span>
<a name="line-66"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-conid'>Cast</span> <span class='hs-varid'>expr'</span> <span class='hs-varid'>coercion</span><span class='hs-layout'>,</span> <span class='hs-varid'>sat_info_expr</span><span class='hs-layout'>,</span> <span class='hs-varid'>expr_app</span><span class='hs-layout'>)</span>
</pre>\end{code}
%************************************************************************
Static Argument Transformation Monad
%************************************************************************
\begin{code}
<pre><a name="line-1"></a><a name="SatM"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>SatM</span> <span class='hs-varid'>result</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>UniqSM</span> <span class='hs-varid'>result</span>
<a name="line-2"></a>
<a name="line-3"></a><a name="runSAT"></a><span class='hs-definition'>runSAT</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>UniqSupply</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SatM</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-4"></a><span class='hs-definition'>runSAT</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>initUs_</span>
<a name="line-5"></a>
<a name="line-6"></a><a name="newUnique"></a><span class='hs-definition'>newUnique</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>SatM</span> <span class='hs-conid'>Unique</span>
<a name="line-7"></a><span class='hs-definition'>newUnique</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>getUniqueUs</span>
</pre>\end{code}
%************************************************************************
Static Argument Transformation Monad
%************************************************************************
To do the transformation, the game plan is to:
1. Create a small nonrecursive RHS that takes the
original arguments to the function but discards
the ones that are static and makes a call to the
SATed version with the remainder. We intend that
this will be inlined later, removing the overhead
2. Bind this nonrecursive RHS over the original body
WITH THE SAME UNIQUE as the original body so that
any recursive calls to the original now go via
the small wrapper
3. Rebind the original function to a new one which contains
our SATed function and just makes a call to it:
we call the thing making this call the local body
Example: transform this
map :: forall a b. (a->b) -> [a] -> [b]
map = /\ab. \(f:a->b) (as:[a]) -> body[map]
to
map :: forall a b. (a->b) -> [a] -> [b]
map = /\ab. \(f:a->b) (as:[a]) ->
letrec map' :: [a] -> [b]
-- The "worker function
map' = \(as:[a]) ->
let map :: forall a' b'. (a -> b) -> [a] -> [b]
-- The "shadow function
map = /\a'b'. \(f':(a->b) (as:[a]).
map' as
in body[map]
in map' as
Note [Shadow binding]
~~~~~~~~~~~~~~~~~~~~~
The calls to the inner map inside body[map] should get inlined
by the local re-binding of 'map'. We call this the "shadow binding".
But we can't use the original binder 'map' unchanged, because
it might be exported, in which case the shadow binding won't be
discarded as dead code after it is inlined.
So we use a hack: we make a new SysLocal binder with the *same* unique
as binder. (Another alternative would be to reset the export flag.)
Note [Binder type capture]
~~~~~~~~~~~~~~~~~~~~~~~~~~
Notice that in the inner map (the "shadow function"), the static arguments
are discarded -- it's as if they were underscores. Instead, mentions
of these arguments (notably in the types of dynamic arguments) are bound
by the *outer* lambdas of the main function. So we must make up fresh
names for the static arguments so that they do not capture variables
mentioned in the types of dynamic args.
In the map example, the shadow function must clone the static type
argument a,b, giving a',b', to ensure that in the \(as:[a]), the 'a'
is bound by the outer forall. We clone f' too for consistency, but
that doesn't matter either way because static Id arguments aren't
mentioned in the shadow binding at all.
If we don't we get something like this:
[Exported]
[Arity 3]
GHC.Base.until =
\ (@ a_aiK)
(p_a6T :: a_aiK -> GHC.Bool.Bool)
(f_a6V :: a_aiK -> a_aiK)
(x_a6X :: a_aiK) ->
letrec {
sat_worker_s1aU :: a_aiK -> a_aiK
[]
sat_worker_s1aU =
\ (x_a6X :: a_aiK) ->
let {
sat_shadow_r17 :: forall a_a3O.
(a_a3O -> GHC.Bool.Bool) -> (a_a3O -> a_a3O) -> a_a3O -> a_a3O
[]
sat_shadow_r17 =
\ (@ a_aiK)
(p_a6T :: a_aiK -> GHC.Bool.Bool)
(f_a6V :: a_aiK -> a_aiK)
(x_a6X :: a_aiK) ->
sat_worker_s1aU x_a6X } in
case p_a6T x_a6X of wild_X3y [ALWAYS Dead Nothing] {
GHC.Bool.False -> GHC.Base.until @ a_aiK p_a6T f_a6V (f_a6V x_a6X);
GHC.Bool.True -> x_a6X
}; } in
sat_worker_s1aU x_a6X
Where sat_shadow has captured the type variables of x_a6X etc as it has a a_aiK
type argument. This is bad because it means the application sat_worker_s1aU x_a6X
is not well typed.
\begin{code}
<pre><a name="line-1"></a><a name="saTransformMaybe"></a><span class='hs-definition'>saTransformMaybe</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Id</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Maybe</span> <span class='hs-conid'>SATInfo</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Id</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>CoreExpr</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SatM</span> <span class='hs-conid'>CoreBind</span>
<a name="line-2"></a><span class='hs-definition'>saTransformMaybe</span> <span class='hs-varid'>binder</span> <span class='hs-varid'>maybe_arg_staticness</span> <span class='hs-varid'>rhs_binders</span> <span class='hs-varid'>rhs_body</span>
<a name="line-3"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>Just</span> <span class='hs-varid'>arg_staticness</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>maybe_arg_staticness</span>
<a name="line-4"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>should_transform</span> <span class='hs-varid'>arg_staticness</span>
<a name="line-5"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>saTransform</span> <span class='hs-varid'>binder</span> <span class='hs-varid'>arg_staticness</span> <span class='hs-varid'>rhs_binders</span> <span class='hs-varid'>rhs_body</span>
<a name="line-6"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span>
<a name="line-7"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-conid'>Rec</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>binder</span><span class='hs-layout'>,</span> <span class='hs-varid'>mkLams</span> <span class='hs-varid'>rhs_binders</span> <span class='hs-varid'>rhs_body</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span>
<a name="line-8"></a> <span class='hs-keyword'>where</span>
<a name="line-9"></a> <span class='hs-varid'>should_transform</span> <span class='hs-varid'>staticness</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>n_static_args</span> <span class='hs-varop'>></span> <span class='hs-num'>1</span> <span class='hs-comment'>-- THIS IS THE DECISION POINT</span>
<a name="line-10"></a> <span class='hs-keyword'>where</span>
<a name="line-11"></a> <span class='hs-varid'>n_static_args</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>length</span> <span class='hs-layout'>(</span><span class='hs-varid'>filter</span> <span class='hs-varid'>isStaticValue</span> <span class='hs-varid'>staticness</span><span class='hs-layout'>)</span>
<a name="line-12"></a>
<a name="line-13"></a><a name="saTransform"></a><span class='hs-definition'>saTransform</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Id</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SATInfo</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Id</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>CoreExpr</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>SatM</span> <span class='hs-conid'>CoreBind</span>
<a name="line-14"></a><span class='hs-definition'>saTransform</span> <span class='hs-varid'>binder</span> <span class='hs-varid'>arg_staticness</span> <span class='hs-varid'>rhs_binders</span> <span class='hs-varid'>rhs_body</span>
<a name="line-15"></a> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span> <span class='hs-layout'>{</span> <span class='hs-varid'>shadow_lam_bndrs</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>mapM</span> <span class='hs-varid'>clone</span> <span class='hs-varid'>binders_w_staticness</span>
<a name="line-16"></a> <span class='hs-layout'>;</span> <span class='hs-varid'>uniq</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>newUnique</span>
<a name="line-17"></a> <span class='hs-layout'>;</span> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-conid'>NonRec</span> <span class='hs-varid'>binder</span> <span class='hs-layout'>(</span><span class='hs-varid'>mk_new_rhs</span> <span class='hs-varid'>uniq</span> <span class='hs-varid'>shadow_lam_bndrs</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-layout'>}</span>
<a name="line-18"></a> <span class='hs-keyword'>where</span>
<a name="line-19"></a> <span class='hs-comment'>-- Running example: foldr</span>
<a name="line-20"></a> <span class='hs-comment'>-- foldr \alpha \beta c n xs = e, for some e</span>
<a name="line-21"></a> <span class='hs-comment'>-- arg_staticness = [Static TypeApp, Static TypeApp, Static VarApp, Static VarApp, NonStatic]</span>
<a name="line-22"></a> <span class='hs-comment'>-- rhs_binders = [\alpha, \beta, c, n, xs]</span>
<a name="line-23"></a> <span class='hs-comment'>-- rhs_body = e</span>
<a name="line-24"></a>
<a name="line-25"></a> <span class='hs-varid'>binders_w_staticness</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>rhs_binders</span> <span class='hs-varop'>`zip`</span> <span class='hs-layout'>(</span><span class='hs-varid'>arg_staticness</span> <span class='hs-varop'>++</span> <span class='hs-varid'>repeat</span> <span class='hs-conid'>NotStatic</span><span class='hs-layout'>)</span>
<a name="line-26"></a> <span class='hs-comment'>-- Any extra args are assumed NotStatic</span>
<a name="line-27"></a>
<a name="line-28"></a> <span class='hs-varid'>non_static_args</span> <span class='hs-keyglyph'>::</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Var</span><span class='hs-keyglyph'>]</span>
<a name="line-29"></a> <span class='hs-comment'>-- non_static_args = [xs]</span>
<a name="line-30"></a> <span class='hs-comment'>-- rhs_binders_without_type_capture = [\alpha', \beta', c, n, xs]</span>
<a name="line-31"></a> <span class='hs-varid'>non_static_args</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>v</span> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>v</span><span class='hs-layout'>,</span> <span class='hs-conid'>NotStatic</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>binders_w_staticness</span><span class='hs-keyglyph'>]</span>
<a name="line-32"></a>
<a name="line-33"></a> <span class='hs-varid'>clone</span> <span class='hs-layout'>(</span><span class='hs-varid'>bndr</span><span class='hs-layout'>,</span> <span class='hs-conid'>NotStatic</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>return</span> <span class='hs-varid'>bndr</span>
<a name="line-34"></a> <span class='hs-varid'>clone</span> <span class='hs-layout'>(</span><span class='hs-varid'>bndr</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span> <span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span> <span class='hs-layout'>{</span> <span class='hs-varid'>uniq</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>newUnique</span>
<a name="line-35"></a> <span class='hs-layout'>;</span> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-varid'>setVarUnique</span> <span class='hs-varid'>bndr</span> <span class='hs-varid'>uniq</span><span class='hs-layout'>)</span> <span class='hs-layout'>}</span>
<a name="line-36"></a>
<a name="line-37"></a> <span class='hs-comment'>-- new_rhs = \alpha beta c n xs -> </span>
<a name="line-38"></a> <span class='hs-comment'>-- let sat_worker = \xs -> let sat_shadow = \alpha' beta' c n xs -> </span>
<a name="line-39"></a> <span class='hs-comment'>-- sat_worker xs </span>
<a name="line-40"></a> <span class='hs-comment'>-- in e</span>
<a name="line-41"></a> <span class='hs-comment'>-- in sat_worker xs</span>
<a name="line-42"></a> <span class='hs-varid'>mk_new_rhs</span> <span class='hs-varid'>uniq</span> <span class='hs-varid'>shadow_lam_bndrs</span>
<a name="line-43"></a> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mkLams</span> <span class='hs-varid'>rhs_binders</span> <span class='hs-varop'>$</span>
<a name="line-44"></a> <span class='hs-conid'>Let</span> <span class='hs-layout'>(</span><span class='hs-conid'>Rec</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>rec_body_bndr</span><span class='hs-layout'>,</span> <span class='hs-varid'>rec_body</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>)</span>
<a name="line-45"></a> <span class='hs-varid'>local_body</span>
<a name="line-46"></a> <span class='hs-keyword'>where</span>
<a name="line-47"></a> <span class='hs-varid'>local_body</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mkVarApps</span> <span class='hs-layout'>(</span><span class='hs-conid'>Var</span> <span class='hs-varid'>rec_body_bndr</span><span class='hs-layout'>)</span> <span class='hs-varid'>non_static_args</span>
<a name="line-48"></a>
<a name="line-49"></a> <span class='hs-varid'>rec_body</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mkLams</span> <span class='hs-varid'>non_static_args</span> <span class='hs-varop'>$</span>
<a name="line-50"></a> <span class='hs-conid'>Let</span> <span class='hs-layout'>(</span><span class='hs-conid'>NonRec</span> <span class='hs-varid'>shadow_bndr</span> <span class='hs-varid'>shadow_rhs</span><span class='hs-layout'>)</span> <span class='hs-varid'>rhs_body</span>
<a name="line-51"></a>
<a name="line-52"></a> <span class='hs-comment'>-- See Note [Binder type capture]</span>
<a name="line-53"></a> <span class='hs-varid'>shadow_rhs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mkLams</span> <span class='hs-varid'>shadow_lam_bndrs</span> <span class='hs-varid'>local_body</span>
<a name="line-54"></a> <span class='hs-comment'>-- nonrec_rhs = \alpha' beta' c n xs -> sat_worker xs</span>
<a name="line-55"></a>
<a name="line-56"></a> <span class='hs-varid'>rec_body_bndr</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mkSysLocal</span> <span class='hs-layout'>(</span><span class='hs-varid'>fsLit</span> <span class='hs-str'>"sat_worker"</span><span class='hs-layout'>)</span> <span class='hs-varid'>uniq</span> <span class='hs-layout'>(</span><span class='hs-varid'>exprType</span> <span class='hs-varid'>rec_body</span><span class='hs-layout'>)</span>
<a name="line-57"></a> <span class='hs-comment'>-- rec_body_bndr = sat_worker</span>
<a name="line-58"></a>
<a name="line-59"></a> <span class='hs-comment'>-- See Note [Shadow binding]; make a SysLocal</span>
<a name="line-60"></a> <span class='hs-varid'>shadow_bndr</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mkSysLocal</span> <span class='hs-layout'>(</span><span class='hs-varid'>occNameFS</span> <span class='hs-layout'>(</span><span class='hs-varid'>getOccName</span> <span class='hs-varid'>binder</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-61"></a> <span class='hs-layout'>(</span><span class='hs-varid'>idUnique</span> <span class='hs-varid'>binder</span><span class='hs-layout'>)</span>
<a name="line-62"></a> <span class='hs-layout'>(</span><span class='hs-varid'>exprType</span> <span class='hs-varid'>shadow_rhs</span><span class='hs-layout'>)</span>
<a name="line-63"></a>
<a name="line-64"></a><a name="isStaticValue"></a><span class='hs-definition'>isStaticValue</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Staticness</span> <span class='hs-conid'>App</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Bool</span>
<a name="line-65"></a><span class='hs-definition'>isStaticValue</span> <span class='hs-layout'>(</span><span class='hs-conid'>Static</span> <span class='hs-layout'>(</span><span class='hs-conid'>VarApp</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-66"></a><span class='hs-definition'>isStaticValue</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-67"></a>
</pre>\end{code}
</body>
</html>
