doc/guide/localhost/CombineConversions

   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>CombineConversions</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>CombineConversions</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p><a href="CombineConversions">CombineConversions</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 looks for and simplifies nested calls to (signed)
  39 extension/truncation.</p></div>
  40 </div>
  41 </div>
  42 <div class="sect1">
  43 <h2 id="_implementation">Implementation</h2>
  44 <div class="sectionbody">
  45 <div class="ulist"><ul>
  46 <li>
  47 <p>
  48 <a href="https://github.com/MLton/mlton/blob/master/mlton/ssa/combine-conversions.fun"><span class="monospaced">combine-conversions.fun</span></a>
  49 </p>
  50 </li>
  51 </ul></div>
  52 </div>
  53 </div>
  54 <div class="sect1">
  55 <h2 id="_details_and_notes">Details and Notes</h2>
  56 <div class="sectionbody">
  57 <div class="paragraph"><p>It processes each block in dfs order (visiting definitions before uses):</p></div>
  58 <div class="ulist"><ul>
  59 <li>
  60 <p>
  61 If the statement is not a <span class="monospaced">PrimApp</span> with <span class="monospaced">Word_extdToWord</span>, skip it.
  62 </p>
  63 </li>
  64 <li>
  65 <p>
  66 After processing a conversion, it tags the <span class="monospaced">Var</span> for subsequent use.
  67 </p>
  68 </li>
  69 <li>
  70 <p>
  71 When inspecting a conversion, check if the <span class="monospaced">Var</span> operand is also the
  72 result of a conversion. If it is, try to combine the two operations.
  73 Repeatedly simplify until hitting either a non-conversion <span class="monospaced">Var</span> or a
  74 case where the conversion cannot be simplified.
  75 </p>
  76 </li>
  77 </ul></div>
  78 <div class="paragraph"><p>The optimization rules are very simple:</p></div>
  79 <div class="listingblock">
  80 <div class="content monospaced">
  81 <pre>x1 = ...
  82 x2 = Word_extdToWord (W1, W2, {signed=s1}) x1
  83 x3 = Word_extdToWord (W2, W3, {signed=s2}) x2</pre>
  84 </div></div>
  85 <div class="ulist"><ul>
  86 <li>
  87 <p>
  88 If <span class="monospaced">W1 = W2</span>, then there is no conversions before <span class="monospaced">x_1</span>.
  89 </p>
  90 <div class="paragraph"><p>This is guaranteed because <span class="monospaced">W2 = W3</span> will always trigger optimization.</p></div>
  91 </li>
  92 <li>
  93 <p>
  94 Case <span class="monospaced">W1 &lt;= W3 &lt;= W2</span>:
  95 </p>
  96 <div class="listingblock">
  97 <div class="content monospaced">
  98 <pre>x3 = Word_extdToWord (W1, W3, {signed=s1}) x1</pre>
  99 </div></div>
 100 </li>
 101 <li>
 102 <p>
 103 Case <span class="monospaced">W1 &lt;  W2 &lt;  W3  AND  ((NOT s1) OR s2)</span>:
 104 </p>
 105 <div class="listingblock">
 106 <div class="content monospaced">
 107 <pre>x3 = Word_extdToWord (W1, W3, {signed=s1}) x1</pre>
 108 </div></div>
 109 </li>
 110 <li>
 111 <p>
 112 Case <span class="monospaced">W1 =  W2 &lt;  W3</span>:
 113 </p>
 114 <div class="paragraph"><p>unoptimized, because there are no conversions past <span class="monospaced">W1</span> and <span class="monospaced">x2 = x1</span></p></div>
 115 </li>
 116 <li>
 117 <p>
 118 Case <span class="monospaced">W3 &lt;= W2 &lt;= W1  OR  W3 &lt;= W1 &lt;= W2</span>:
 119 </p>
 120 <div class="listingblock">
 121 <div class="content monospaced">
 122 <pre>x_3 = Word_extdToWord (W1, W3, {signed=_}) x1</pre>
 123 </div></div>
 124 <div class="paragraph"><p>because <span class="monospaced">W3 &lt;= W1 &amp;&amp; W3 &lt;= W2</span>, just clip <span class="monospaced">x1</span></p></div>
 125 </li>
 126 <li>
 127 <p>
 128 Case <span class="monospaced">W2 &lt; W1 &lt;= W3  OR  W2 &lt; W3 &lt;= W1</span>:
 129 </p>
 130 <div class="paragraph"><p>unoptimized, because <span class="monospaced">W2 &lt; W1 &amp;&amp; W2 &lt; W3</span>, has truncation effect</p></div>
 131 </li>
 132 <li>
 133 <p>
 134 Case <span class="monospaced">W1 &lt; W2 &lt; W3  AND  (s1 AND (NOT s2))</span>:
 135 </p>
 136 <div class="paragraph"><p>unoptimized, because each conversion affects the result separately</p></div>
 137 </li>
 138 </ul></div>
 139 </div>
 140 </div>
 141 </div>
 142 <div id="footnotes"><hr></div>
 143 <div id="footer">
 144 <div id="footer-text">
 145 </div>
 146 <div id="footer-badges">
 147 </div>
 148 </div>
 149 </body>
 150 </html>