doc/guide/localhost/KnownCase

   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>KnownCase</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>KnownCase</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p><a href="KnownCase">KnownCase</a> is an optimization pass for the <a href="SSA">SSA</a>
  32 <a href="IntermediateLanguage">IntermediateLanguage</a>, invoked from <a href="SSASimplify">SSASimplify</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 duplicates and simplifies <span class="monospaced">Case</span> transfers when the
  39 constructor of the scrutinee is known.</p></div>
  40 <div class="paragraph"><p>Uses <a href="Restore">Restore</a>.</p></div>
  41 <div class="paragraph"><p>For example, the program</p></div>
  42 <div class="listingblock">
  43 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="k">rec</span><span class="w"> </span><span class="n">last</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
  44 <span class="w">  </span><span class="k">fn</span><span class="w"> </span><span class="p">[]</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="mi">0</span><span class="w"></span>
  45 <span class="w">   </span><span class="p">|</span><span class="w"> </span><span class="p">[</span><span class="n">x</span><span class="p">]</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
  46 <span class="w">   </span><span class="p">|</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="n">::</span><span class="w"> </span><span class="n">l</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">last</span><span class="w"> </span><span class="n">l</span><span class="w"></span>
  47
  48 <span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">last</span><span class="w"> </span><span class="p">[</span><span class="mi">2</span><span class="p">,</span><span class="w"> </span><span class="mi">3</span><span class="p">,</span><span class="w"> </span><span class="mi">4</span><span class="p">,</span><span class="w"> </span><span class="mi">5</span><span class="p">,</span><span class="w"> </span><span class="mi">6</span><span class="p">,</span><span class="w"> </span><span class="mi">7</span><span class="p">]</span><span class="w"></span>
  49 </pre></div></div></div>
  50 <div class="paragraph"><p>gives rise to the <a href="SSA">SSA</a> function</p></div>
  51 <div class="listingblock">
  52 <div class="content monospaced">
  53 <pre>fun last_0 (x_142) = loopS_1 ()
  54   loopS_1 ()
  55     loop_11 (x_142)
  56   loop_11 (x_143)
  57     case x_143 of
  58       nil_1 =&gt; L_73 | ::_0 =&gt; L_74
  59   L_73 ()
  60     return global_5
  61   L_74 (x_145, x_144)
  62     case x_145 of
  63       nil_1 =&gt; L_75 | _ =&gt; L_76
  64   L_75 ()
  65     return x_144
  66   L_76 ()
  67     loop_11 (x_145)</pre>
  68 </div></div>
  69 <div class="paragraph"><p>which is simplified to</p></div>
  70 <div class="listingblock">
  71 <div class="content monospaced">
  72 <pre>fun last_0 (x_142) = loopS_1 ()
  73   loopS_1 ()
  74     case x_142 of
  75       nil_1 =&gt; L_73 | ::_0 =&gt; L_118
  76   L_73 ()
  77     return global_5
  78   L_118 (x_230, x_229)
  79     L_74 (x_230, x_229, x_142)
  80   L_74 (x_145, x_144, x_232)
  81     case x_145 of
  82       nil_1 =&gt; L_75 | ::_0 =&gt; L_114
  83   L_75 ()
  84     return x_144
  85   L_114 (x_227, x_226)
  86     L_74 (x_227, x_226, x_145)</pre>
  87 </div></div>
  88 </div>
  89 </div>
  90 <div class="sect1">
  91 <h2 id="_implementation">Implementation</h2>
  92 <div class="sectionbody">
  93 <div class="ulist"><ul>
  94 <li>
  95 <p>
  96 <a href="https://github.com/MLton/mlton/blob/master/mlton/ssa/known-case.fun"><span class="monospaced">known-case.fun</span></a>
  97 </p>
  98 </li>
  99 </ul></div>
 100 </div>
 101 </div>
 102 <div class="sect1">
 103 <h2 id="_details_and_notes">Details and Notes</h2>
 104 <div class="sectionbody">
 105 <div class="paragraph"><p>One interesting aspect of <a href="KnownCase">KnownCase</a>, is that it often has the
 106 effect of unrolling list traversals by one iteration, moving the
 107 <span class="monospaced">nil</span>/<span class="monospaced">::</span> check to the end of the loop, rather than the beginning.</p></div>
 108 </div>
 109 </div>
 110 </div>
 111 <div id="footnotes"><hr></div>
 112 <div id="footer">
 113 <div id="footer-text">
 114 </div>
 115 <div id="footer-badges">
 116 </div>
 117 </div>
 118 </body>
 119 </html>