HCoop / hcoop / debian / mlton.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Import Debian changes 20180207-1
[hcoop/debian/mlton.git] / doc / guide / localhost / KnownCase
CommitLineData
7f918cf1
CE		 1<!DOCTYPE html>\r
2<html lang="en">\r
3<head>\r
4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">\r
5<meta name="generator" content="AsciiDoc 8.6.9">\r
6<title>KnownCase</title>\r
7<link rel="stylesheet" href="./asciidoc.css" type="text/css">\r
8<link rel="stylesheet" href="./pygments.css" type="text/css">\r
9\r
10\r
11<script type="text/javascript" src="./asciidoc.js"></script>\r
12<script type="text/javascript">\r
13/*<![CDATA[*/\r
14asciidoc.install();\r
15/*]]>*/\r
16</script>\r
17<link rel="stylesheet" href="./mlton.css" type="text/css">\r
18</head>\r
19<body class="article">\r
20<div id="banner">\r
21<div id="banner-home">\r
22<a href="./Home">MLton 20180207</a>\r
23</div>\r
24</div>\r
25<div id="header">\r
26<h1>KnownCase</h1>\r
27</div>\r
28<div id="content">\r
29<div id="preamble">\r
30<div class="sectionbody">\r
31<div class="paragraph"><p><a href="KnownCase">KnownCase</a> is an optimization pass for the <a href="SSA">SSA</a>\r
32<a href="IntermediateLanguage">IntermediateLanguage</a>, invoked from <a href="SSASimplify">SSASimplify</a>.</p></div>\r
33</div>\r
34</div>\r
35<div class="sect1">\r
36<h2 id="_description">Description</h2>\r
37<div class="sectionbody">\r
38<div class="paragraph"><p>This pass duplicates and simplifies <span class="monospaced">Case</span> transfers when the\r
39constructor of the scrutinee is known.</p></div>\r
40<div class="paragraph"><p>Uses <a href="Restore">Restore</a>.</p></div>\r
41<div class="paragraph"><p>For example, the program</p></div>\r
42<div class="listingblock">\r
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>\r
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>\r
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>\r
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>\r
47\r
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>\r
49</pre></div></div></div>\r
50<div class="paragraph"><p>gives rise to the <a href="SSA">SSA</a> function</p></div>\r
51<div class="listingblock">\r
52<div class="content monospaced">\r
53<pre>fun last_0 (x_142) = loopS_1 ()\r
54 loopS_1 ()\r
55 loop_11 (x_142)\r
56 loop_11 (x_143)\r
57 case x_143 of\r
58 nil_1 =&gt; L_73 | ::_0 =&gt; L_74\r
59 L_73 ()\r
60 return global_5\r
61 L_74 (x_145, x_144)\r
62 case x_145 of\r
63 nil_1 =&gt; L_75 | _ =&gt; L_76\r
64 L_75 ()\r
65 return x_144\r
66 L_76 ()\r
67 loop_11 (x_145)</pre>\r
68</div></div>\r
69<div class="paragraph"><p>which is simplified to</p></div>\r
70<div class="listingblock">\r
71<div class="content monospaced">\r
72<pre>fun last_0 (x_142) = loopS_1 ()\r
73 loopS_1 ()\r
74 case x_142 of\r
75 nil_1 =&gt; L_73 | ::_0 =&gt; L_118\r
76 L_73 ()\r
77 return global_5\r
78 L_118 (x_230, x_229)\r
79 L_74 (x_230, x_229, x_142)\r
80 L_74 (x_145, x_144, x_232)\r
81 case x_145 of\r
82 nil_1 =&gt; L_75 | ::_0 =&gt; L_114\r
83 L_75 ()\r
84 return x_144\r
85 L_114 (x_227, x_226)\r
86 L_74 (x_227, x_226, x_145)</pre>\r
87</div></div>\r
88</div>\r
89</div>\r
90<div class="sect1">\r
91<h2 id="_implementation">Implementation</h2>\r
92<div class="sectionbody">\r
93<div class="ulist"><ul>\r
94<li>\r
95<p>\r
96<a href="https://github.com/MLton/mlton/blob/master/mlton/ssa/known-case.fun"><span class="monospaced">known-case.fun</span></a>\r
97</p>\r
98</li>\r
99</ul></div>\r
100</div>\r
101</div>\r
102<div class="sect1">\r
103<h2 id="_details_and_notes">Details and Notes</h2>\r
104<div class="sectionbody">\r
105<div class="paragraph"><p>One interesting aspect of <a href="KnownCase">KnownCase</a>, is that it often has the\r
106effect of unrolling list traversals by one iteration, moving the\r
107<span class="monospaced">nil</span>/<span class="monospaced">::</span> check to the end of the loop, rather than the beginning.</p></div>\r
108</div>\r
109</div>\r
110</div>\r
111<div id="footnotes"><hr></div>\r
112<div id="footer">\r
113<div id="footer-text">\r
114</div>\r
115<div id="footer-badges">\r
116</div>\r
117</div>\r
118</body>\r
119</html>\r
mlton packaging