1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta name="robots" content="index,nofollow">
<title>SimplifyTypes - MLton Standard ML Compiler (SML Compiler)</title>
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="all" href="common.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="screen" href="screen.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="print" href="print.css">
<link rel="Start" href="Home">
</head>
<body lang="en" dir="ltr">
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-833377-1";
urchinTracker();
</script>
<table bgcolor = lightblue cellspacing = 0 style = "border: 0px;" width = 100%>
<tr>
<td style = "
border: 0px;
color: darkblue;
font-size: 150%;
text-align: left;">
<a class = mltona href="Home">MLton MLTONWIKIVERSION</a>
<td style = "
border: 0px;
font-size: 150%;
text-align: center;
width: 50%;">
SimplifyTypes
<td style = "
border: 0px;
text-align: right;">
<table cellspacing = 0 style = "border: 0px">
<tr style = "vertical-align: middle;">
</table>
<tr style = "background-color: white;">
<td colspan = 3
style = "
border: 0px;
font-size:70%;
text-align: right;">
<a href = "Home">Home</a>
<a href = "TitleIndex">Index</a>
</table>
<div id="content" lang="en" dir="ltr">
SimplifyTypes is an optimization pass for the <a href="SSA">SSA</a> <a href="IntermediateLanguage">IntermediateLanguage</a>, invoked from <a href="SSASimplify">SSASimplify</a>. <h2 id="head-55f8ebc805e65b5b71ddafdae390e3be2bcd69af">Description</h2>
<p>
This pass computes a "cardinality" of each datatype, which is an abstraction of the number of values of the datatype.
</p>
<ul>
<li>
<p>
<tt>Zero</tt> means the datatype has no values (except for bottom).
</p>
</li>
<li>
<p>
<tt>One</tt> means the datatype has one value (except for bottom).
</p>
</li>
<li>
<p>
<tt>Many</tt> means the datatype has many values.
</p>
</li>
</ul>
<p>
This pass removes all datatypes whose cardinality is <tt>Zero</tt> or <tt>One</tt> and removes:
</p>
<ul>
<li>
<p>
components of tuples
</p>
</li>
<li>
<p>
function args
</p>
</li>
<li>
<p>
constructor args
</p>
</li>
</ul>
<p>
which are such datatypes.
</p>
<p>
This pass marks constructors as one of:
</p>
<ul>
<li>
<p>
<tt>Useless</tt>: it never appears in a <tt>ConApp</tt>.
</p>
</li>
<li>
<p>
<tt>Transparent</tt>: it is the only variant in its datatype and its argument type does not contain any uses of <tt>array</tt> or <tt>vector</tt>.
</p>
</li>
<li>
<p>
<tt>Useful</tt>: otherwise
</p>
</li>
</ul>
<p>
This pass also removes <tt>Useless</tt> and <tt>Transparent</tt> constructors.
</p>
<h2 id="head-8781d615fd77be9578225c40ac67b9471394cced">Implementation</h2>
<p>
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-MLTONWIKIVERSION-release/mlton/ssa/simplify-types.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">simplify-types.sig</a> <a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-MLTONWIKIVERSION-release/mlton/ssa/simplify-types.fun?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">simplify-types.fun</a>
</p>
<h2 id="head-35ec00231a68203708e39f0e2cc10b50c6bf62de">Details and Notes</h2>
<p>
This pass must happen before polymorphic equality is implemented because
</p>
<ol type="1">
<li>
<p>
it will make polymorphic equality faster because some types are simpler
</p>
</li>
<li>
<p>
it removes uses of polymorphic equality that must return true
</p>
</li>
</ol>
<p>
We must keep track of <tt>Transparent</tt> constructors whose argument type uses <tt>array</tt> because of datatypes like the following:
<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">T</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> t array
</FONT></B></PRE>
Such a datatype has <tt>Cardinality.Many</tt>, but we cannot eliminate the datatype and replace the lhs by the rhs, i.e. we must keep the circularity around.
</p>
<p>
Must do similar things for <tt>vectors</tt>.
</p>
<p>
Also, to eliminate as many <tt>Transparent</tt> constructors as possible, for something like the following,
<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">T</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> u array
</FONT></B><B><FONT COLOR="#A020F0">and</FONT></B><B><FONT COLOR="#228B22"> u </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">U</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> t vector
</FONT></B></PRE>
we (arbitrarily) expand one of the datatypes first. The result will be something like
<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><B><FONT COLOR="#228B22"> u </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">U</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> u array array
</FONT></B></PRE>
where all uses of <tt>t</tt> are replaced by <tt>u array</tt>.
</p>
</div>
<p>
<hr>
Last edited on 2009-12-11 14:54:29 by <span title="fenrir.cs.rit.edu"><a href="MatthewFluet">MatthewFluet</a></span>.
</body></html>
|
