doc/guide/localhost/RefFlatten

   1 <!DOCTYPE html>
   2 <html lang="en">
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
   5 <meta name="generator" content="AsciiDoc 8.6.9">
   6 <title>RefFlatten</title>
   7 <link rel="stylesheet" href="./asciidoc.css" type="text/css">
   8 <link rel="stylesheet" href="./pygments.css" type="text/css">
   9
  10
  11 <script type="text/javascript" src="./asciidoc.js"></script>
  12 <script type="text/javascript">
  13 /*<![CDATA[*/
  14 asciidoc.install();
  15 /*]]>*/
  16 </script>
  17 <link rel="stylesheet" href="./mlton.css" type="text/css">
  18 </head>
  19 <body class="article">
  20 <div id="banner">
  21 <div id="banner-home">
  22 <a href="./Home">MLton 20180207</a>
  23 </div>
  24 </div>
  25 <div id="header">
  26 <h1>RefFlatten</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p><a href="RefFlatten">RefFlatten</a> is an optimization pass for the <a href="SSA2">SSA2</a>
  32 <a href="IntermediateLanguage">IntermediateLanguage</a>, invoked from <a href="SSA2Simplify">SSA2Simplify</a>.</p></div>
  33 </div>
  34 </div>
  35 <div class="sect1">
  36 <h2 id="_description">Description</h2>
  37 <div class="sectionbody">
  38 <div class="paragraph"><p>This pass flattens a <span class="monospaced">ref</span> cell into its containing object.
  39 The idea is to replace, where possible, a type like</p></div>
  40 <div class="listingblock">
  41 <div class="content monospaced">
  42 <pre>(int ref * real)</pre>
  43 </div></div>
  44 <div class="paragraph"><p>with a type like</p></div>
  45 <div class="listingblock">
  46 <div class="content monospaced">
  47 <pre>(int[m] * real)</pre>
  48 </div></div>
  49 <div class="paragraph"><p>where the <span class="monospaced">[m]</span> indicates a mutable field of a tuple.</p></div>
  50 </div>
  51 </div>
  52 <div class="sect1">
  53 <h2 id="_implementation">Implementation</h2>
  54 <div class="sectionbody">
  55 <div class="ulist"><ul>
  56 <li>
  57 <p>
  58 <a href="https://github.com/MLton/mlton/blob/master/mlton/ssa/ref-flatten.fun"><span class="monospaced">ref-flatten.fun</span></a>
  59 </p>
  60 </li>
  61 </ul></div>
  62 </div>
  63 </div>
  64 <div class="sect1">
  65 <h2 id="_details_and_notes">Details and Notes</h2>
  66 <div class="sectionbody">
  67 <div class="paragraph"><p>The savings is obvious, I hope.  We avoid an extra heap-allocated
  68 object for the <span class="monospaced">ref</span>, which in the above case saves two words.  We
  69 also save the time and code for the extra indirection at each get and
  70 set.  There are lots of useful data structures (singly-linked and
  71 doubly-linked lists, union-find, Fibonacci heaps, &#8230;) that I believe
  72 we are paying through the nose right now because of the absence of ref
  73 flattening.</p></div>
  74 <div class="paragraph"><p>The idea is to compute for each occurrence of a <span class="monospaced">ref</span> type in the
  75 program whether or not that <span class="monospaced">ref</span> can be represented as an offset of
  76 some object (constructor or tuple).  As before, a unification-based
  77 whole-program with deep abstract values makes sure the analysis is
  78 consistent.</p></div>
  79 <div class="paragraph"><p>The only syntactic part of the analysis that remains is the part that
  80 checks that for a variable bound to a value constructed by <span class="monospaced">Ref_ref</span>:</p></div>
  81 <div class="ulist"><ul>
  82 <li>
  83 <p>
  84 the object allocation is in the same block.  This is pretty
  85 draconian, and it would be nice to generalize it some day to allow
  86 flattening as long as the <span class="monospaced">ref</span> allocation and object allocation "line
  87 up one-to-one" in the same loop-free chunk of code.
  88 </p>
  89 </li>
  90 <li>
  91 <p>
  92 updates occur in the same block (and hence it is safe-for-space
  93 because the containing object is still alive).  It would be nice to
  94 relax this to allow updates as long as it can be provedthat the
  95 container is live.
  96 </p>
  97 </li>
  98 </ul></div>
  99 <div class="paragraph"><p>Prevent flattening of <span class="monospaced">unit ref</span>-s.</p></div>
 100 <div class="paragraph"><p><a href="RefFlatten">RefFlatten</a> is safe for space.  The idea is to prevent a <span class="monospaced">ref</span>
 101 being flattened into an object that has a component of unbounded size
 102 (other than possibly the <span class="monospaced">ref</span> itself) unless we can prove that at
 103 each point the <span class="monospaced">ref</span> is live, then the containing object is live too.
 104 I used a pretty simple approximation to liveness.</p></div>
 105 </div>
 106 </div>
 107 </div>
 108 <div id="footnotes"><hr></div>
 109 <div id="footer">
 110 <div id="footer-text">
 111 </div>
 112 <div id="footer-badges">
 113 </div>
 114 </div>
 115 </body>
 116 </html>