<!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>RefFlatten - 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%;">
RefFlatten
<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">
RefFlatten 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 flattens a <tt>ref</tt> cell into its containing object. The idea is to replace, where possible, a type like
<pre> (int ref * real)
</pre>with a type like
<pre> (int[m] * real)
</pre>where the <tt>[m]</tt> indicates a mutable field of a tuple.
</p>
<h2 id="head-8781d615fd77be9578225c40ac67b9471394cced">Implementation</h2>
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-MLTONWIKIVERSION-release/mlton/ssa/ref-flatten.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">ref-flatten.sig</a> <a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-MLTONWIKIVERSION-release/mlton/ssa/ref-flatten.fun?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">ref-flatten.fun</a> <h2 id="head-35ec00231a68203708e39f0e2cc10b50c6bf62de">Details and Notes</h2>
<p>
The savings is obvious, I hope. We avoid an extra heap-allocated object for the <tt>ref</tt>, which in the above case saves two words. We also save the time and code for the extra indirection at each get and set. There are lots of useful data structures (singly-linked and doubly-linked lists, union-find, Fibonacci heaps, ...) that I believe we are paying through the nose right now because of the absence of ref flattening.
</p>
<p>
The idea is to compute for each occurrence of a <tt>ref</tt> type in the program whether or not that <tt>ref</tt> can be represented as an offset of some object (constructor or tuple). As before, a unification-based whole-program with deep abstract values makes sure the analysis is consistent.
</p>
<p>
The only syntactic part of the analysis that remains is the part that checks that for a variable bound to a value constructed by <tt>Ref_ref</tt>:
</p>
<ul>
<li>
<p>
the object allocation is in the same block. This is pretty draconian, and it would be nice to generalize it some day to allow flattening as long as the <tt>ref</tt> allocation and object allocation "line up one-to-one" in the same loop-free chunk of code.
</p>
</li>
<li>
<p>
updates occur in the same block (and hence it is safe-for-space because the containing object is still alive). It would be nice to relax this to allow updates as long as it can be proved that the container is live.
</p>
</li>
</ul>
<p>
Prevent flattening of <tt>unit ref</tt>s.
</p>
<p>
RefFlatten is safe for space. The idea is to prevent a <tt>ref</tt> being flattened into an object that has a component of unbounded size (other than possibly the <tt>ref</tt> itself) unless we can prove that at each point the <tt>ref</tt> is live, then the containing object is live too. I used a pretty simple approximation to liveness.
</p>
</div>
<p>
<hr>
Last edited on 2009-12-11 14:55:23 by <span title="fenrir.cs.rit.edu"><a href="MatthewFluet">MatthewFluet</a></span>.
</body></html>
