doc/guide/localhost/Zone

   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>Zone</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>Zone</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p><a href="Zone">Zone</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 breaks large <a href="SSA2">SSA2</a> functions into zones, which are
  39 connected subgraphs of the dominator tree.  For each zone, at the node
  40 that dominates the zone (the "zone root"), it places a tuple
  41 collecting all of the live variables at that node.  It replaces any
  42 variables used in that zone with offsets from the tuple.  The goal is
  43 to decrease the liveness information in large <a href="SSA">SSA</a> functions.</p></div>
  44 </div>
  45 </div>
  46 <div class="sect1">
  47 <h2 id="_implementation">Implementation</h2>
  48 <div class="sectionbody">
  49 <div class="ulist"><ul>
  50 <li>
  51 <p>
  52 <a href="https://github.com/MLton/mlton/blob/master/mlton/ssa/zone.fun"><span class="monospaced">zone.fun</span></a>
  53 </p>
  54 </li>
  55 </ul></div>
  56 </div>
  57 </div>
  58 <div class="sect1">
  59 <h2 id="_details_and_notes">Details and Notes</h2>
  60 <div class="sectionbody">
  61 <div class="paragraph"><p>Compute strongly-connected components to avoid put tuple constructions
  62 in loops.</p></div>
  63 <div class="paragraph"><p>There are two (expert) flags that govern the use of this pass</p></div>
  64 <div class="ulist"><ul>
  65 <li>
  66 <p>
  67 <span class="monospaced">-max-function-size &lt;n&gt;</span>
  68 </p>
  69 </li>
  70 <li>
  71 <p>
  72 <span class="monospaced">-zone-cut-depth &lt;n&gt;</span>
  73 </p>
  74 </li>
  75 </ul></div>
  76 <div class="paragraph"><p>Zone splitting only works when the number of basic blocks in a
  77 function is greater than <span class="monospaced">n</span>.  The <span class="monospaced">n</span> used to cut the dominator tree
  78 is set by <span class="monospaced">-zone-cut-depth</span>.</p></div>
  79 <div class="paragraph"><p>There is currently no attempt to be safe-for-space.  That is, the
  80 tuples are not restricted to containing only "small" values.</p></div>
  81 <div class="paragraph"><p>In the <span class="monospaced">HOL</span> program, the particular problem is the main function,
  82 which has 161,783 blocks and 257,519 variables&#8201;&#8212;&#8201;the product of those
  83 two numbers being about 41 billion.  Now, we&#8217;re not likely going to
  84 need that much space since we use a sparse representation.  But even
  85 1/100th would really hurt.  And of course this rules out bit vectors.</p></div>
  86 </div>
  87 </div>
  88 </div>
  89 <div id="footnotes"><hr></div>
  90 <div id="footer">
  91 <div id="footer-text">
  92 </div>
  93 <div id="footer-badges">
  94 </div>
  95 </div>
  96 </body>
  97 </html>