<!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>Restore - 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%;">
Restore
<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">
Restore is a rewrite pass for the <a href="SSA">SSA</a> and <a href="SSA2">SSA2</a> <a href="IntermediateLanguage">IntermediateLanguage</a>s, invoked from <a href="KnownCase">KnownCase</a> and <a href="LocalRef">LocalRef</a>. <h2 id="head-55f8ebc805e65b5b71ddafdae390e3be2bcd69af">Description</h2>
<p>
This pass restores the SSA condition for a violating <a href="SSA">SSA</a> or <a href="SSA2">SSA2</a> program; the program must satisfy:
</p>
<ul>
Every path from the root to a use of a variable (excluding globals) passes through a def of that variable.
</ul>
<h2 id="head-8781d615fd77be9578225c40ac67b9471394cced">Implementation</h2>
<p>
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-MLTONWIKIVERSION-release/mlton/ssa/restore.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">restore.sig</a> <a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-MLTONWIKIVERSION-release/mlton/ssa/restore.fun?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">restore.fun</a><br>
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-MLTONWIKIVERSION-release/mlton/ssa/restore2.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">restore2.sig</a> <a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-MLTONWIKIVERSION-release/mlton/ssa/restore2.fun?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">restore2.fun</a>
</p>
<h2 id="head-35ec00231a68203708e39f0e2cc10b50c6bf62de">Details and Notes</h2>
<p>
Based primarily on Section 19.1 of <a href = "References#Appel98">Modern Compiler Implementation in ML</a>.
</p>
<p>
The main deviation is the calculation of liveness of the violating variables, which is used to predicate the insertion of phi arguments. This is due to the algorithm's bias towards imperative languages, for which it makes the assumption that all variables are defined in the start block and all variables are "used" at exit.
</p>
<p>
This is "optimized" for restoration of functions with small numbers of violating variables -- use bool vectors to represent sets of violating variables.
</p>
<p>
Also, we use a <tt>Promise.t</tt> to suspend part of the dominance frontier computation.
</p>
</div>
<p>
<hr>
Last edited on 2010-03-02 15:18:03 by <span title="fenrir.cs.rit.edu"><a href="MatthewFluet">MatthewFluet</a></span>.
</body></html>
