<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta name="robots" content="index,nofollow">
<title>Zone - MLton Standard ML Compiler (SML Compiler)</title>
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="all" href="common.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="screen" href="screen.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="print" href="print.css">
<link rel="Start" href="Home">
</head>
<body lang="en" dir="ltr">
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-833377-1";
urchinTracker();
</script>
<table bgcolor = lightblue cellspacing = 0 style = "border: 0px;" width = 100%>
<tr>
<td style = "
border: 0px;
color: darkblue;
font-size: 150%;
text-align: left;">
<a class = mltona href="Home">MLton MLTONWIKIVERSION</a>
<td style = "
border: 0px;
font-size: 150%;
text-align: center;
width: 50%;">
Zone
<td style = "
border: 0px;
text-align: right;">
<table cellspacing = 0 style = "border: 0px">
<tr style = "vertical-align: middle;">
</table>
<tr style = "background-color: white;">
<td colspan = 3
style = "
border: 0px;
font-size:70%;
text-align: right;">
<a href = "Home">Home</a>
<a href = "TitleIndex">Index</a>
</table>
<div id="content" lang="en" dir="ltr">
Zone is an optimization pass for the <a href="SSA2">SSA2</a> <a href="IntermediateLanguage">IntermediateLanguage</a>, invoked from <a href="SSA2Simplify">SSA2Simplify</a>. <h2 id="head-55f8ebc805e65b5b71ddafdae390e3be2bcd69af">Description</h2>
<p>
This pass breaks large <a href="SSA2">SSA2</a> functions into zones, which are connected subgraphs of the dominator tree. For each zone, at the node that dominates the zone (the "zone root"), it places a tuple collecting all of the live variables at that node. It replaces any variables used in that zone with offsets from the tuple. The goal is to decrease the liveness information in large <a href="SSA">SSA</a> functions.
</p>
<h2 id="head-8781d615fd77be9578225c40ac67b9471394cced">Implementation</h2>
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-MLTONWIKIVERSION-release/mlton/ssa/zone.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">zone.sig</a> <a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-MLTONWIKIVERSION-release/mlton/ssa/zone.fun?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">zone.fun</a> <h2 id="head-35ec00231a68203708e39f0e2cc10b50c6bf62de">Details and Notes</h2>
<p>
Compute strongly-connected components to avoid put tuple constructions in loops.
</p>
<p>
There are two (expert) flags that govern the use of this pass
<pre> -max-function-size <n>
-zone-cut-depth <n>
</pre> Zone splitting only works when the number of basic blocks in a function is > <tt>n</tt>. The <tt>n</tt> used to cut the dominator tree is set by <tt>-zone-cut-depth</tt>.
</p>
<p>
There is currently no attempt to be safe-for-space. That is, the tuples are not restricted to containing only "small" values.
</p>
<p>
In the <tt>HOL</tt> program, the particular problem is the main function, which has 161,783 blocks and 257,519 variables -- the product of those two numbers being about 41 billion. Now, we're not likely going to need that much space since we use a sparse representation. But even 1/100th would really hurt. And of course this rules out bit vectors.
</p>
</div>
<p>
<hr>
Last edited on 2006-11-02 17:31:40 by <span title="76.16.241.4"><a href="MatthewFluet">MatthewFluet</a></span>.
</body></html>
