4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
5 <meta name="generator" content="AsciiDoc 8.6.9">
6 <title>SimplifyTypes</title>
7 <link rel="stylesheet" href="./asciidoc.css" type="text/css">
8 <link rel="stylesheet" href="./pygments.css" type="text/css">
11 <script type="text/javascript" src="./asciidoc.js"></script>
12 <script type="text/javascript">
17 <link rel="stylesheet" href="./mlton.css" type="text/css">
19 <body class="article">
21 <div id="banner-home">
22 <a href="./Home">MLton 20180207</a>
26 <h1>SimplifyTypes</h1>
30 <div class="sectionbody">
31 <div class="paragraph"><p><a href="SimplifyTypes">SimplifyTypes</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>
36 <h2 id="_description">Description</h2>
37 <div class="sectionbody">
38 <div class="paragraph"><p>This pass computes a "cardinality" of each datatype, which is an
39 abstraction of the number of values of the datatype.</p></div>
40 <div class="ulist"><ul>
43 <span class="monospaced">Zero</span> means the datatype has no values (except for bottom).
48 <span class="monospaced">One</span> means the datatype has one value (except for bottom).
53 <span class="monospaced">Many</span> means the datatype has many values.
57 <div class="paragraph"><p>This pass removes all datatypes whose cardinality is <span class="monospaced">Zero</span> or <span class="monospaced">One</span>
58 and removes:</p></div>
59 <div class="ulist"><ul>
76 <div class="paragraph"><p>which are such datatypes.</p></div>
77 <div class="paragraph"><p>This pass marks constructors as one of:</p></div>
78 <div class="ulist"><ul>
81 <span class="monospaced">Useless</span>: it never appears in a <span class="monospaced">ConApp</span>.
86 <span class="monospaced">Transparent</span>: it is the only variant in its datatype and its argument type does not contain any uses of <span class="monospaced">array</span> or <span class="monospaced">vector</span>.
91 <span class="monospaced">Useful</span>: otherwise
95 <div class="paragraph"><p>This pass also removes <span class="monospaced">Useless</span> and <span class="monospaced">Transparent</span> constructors.</p></div>
99 <h2 id="_implementation">Implementation</h2>
100 <div class="sectionbody">
101 <div class="ulist"><ul>
104 <a href="https://github.com/MLton/mlton/blob/master/mlton/ssa/simplify-types.fun"><span class="monospaced">simplify-types.fun</span></a>
111 <h2 id="_details_and_notes">Details and Notes</h2>
112 <div class="sectionbody">
113 <div class="paragraph"><p>This pass must happen before polymorphic equality is implemented because</p></div>
114 <div class="ulist"><ul>
117 it will make polymorphic equality faster because some types are simpler
122 it removes uses of polymorphic equality that must return true
126 <div class="paragraph"><p>We must keep track of <span class="monospaced">Transparent</span> constructors whose argument type
127 uses <span class="monospaced">array</span> because of datatypes like the following:</p></div>
128 <div class="listingblock">
129 <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">T</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">array</span><span class="w"></span>
130 </pre></div></div></div>
131 <div class="paragraph"><p>Such a datatype has <span class="monospaced">Cardinality.Many</span>, but we cannot eliminate the
132 datatype and replace the lhs by the rhs, i.e. we must keep the
133 circularity around.</p></div>
134 <div class="paragraph"><p>Must do similar things for <span class="monospaced">vectors</span>.</p></div>
135 <div class="paragraph"><p>Also, to eliminate as many <span class="monospaced">Transparent</span> constructors as possible, for
136 something like the following,</p></div>
137 <div class="listingblock">
138 <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">T</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">array</span><span class="w"></span>
139 <span class="w"> </span><span class="k">and</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">U</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">vector</span><span class="w"></span>
140 </pre></div></div></div>
141 <div class="paragraph"><p>we (arbitrarily) expand one of the datatypes first. The result will
142 be something like</p></div>
143 <div class="listingblock">
144 <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">U</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">array</span><span class="w"> </span><span class="n">array</span><span class="w"></span>
145 </pre></div></div></div>
146 <div class="paragraph"><p>where all uses of <span class="monospaced">t</span> are replaced by <span class="monospaced">u array</span>.</p></div>
150 <div id="footnotes"><hr></div>
152 <div id="footer-text">
154 <div id="footer-badges">