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
|
<!DOCTYPE html>
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="generator" content="AsciiDoc 8.6.8">
<title>Restore</title>
<link rel="stylesheet" href="./asciidoc.css" type="text/css">
<link rel="stylesheet" href="./pygments.css" type="text/css">
<script type="text/javascript" src="./asciidoc.js"></script>
<script type="text/javascript">
/*<![CDATA[*/
asciidoc.install();
/*]]>*/
</script>
<link rel="stylesheet" href="./mlton.css" type="text/css"/>
</head>
<body class="article">
<div id="banner">
<div id="banner-home">
<a href="./Home">MLton 20130715</a>
</div>
</div>
<div id="header">
<h1>Restore</h1>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div class="paragraph"><p><a href="Restore">Restore</a> is a rewrite pass for the <a href="SSA">SSA</a> and <a href="SSA2">SSA2</a>
<a href="IntermediateLanguage">IntermediateLanguage</a>s, invoked from <a href="KnownCase">KnownCase</a> and
<a href="LocalRef">LocalRef</a>.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_description">Description</h2>
<div class="sectionbody">
<div class="paragraph"><p>This pass restores the SSA condition for a violating <a href="SSA">SSA</a> or
<a href="SSA2">SSA2</a> program; the program must satisfy:</p></div>
<div class="quoteblock">
<div class="content">
<div class="paragraph"><p>Every path from the root to a use of a variable (excluding globals)
passes through a def of that variable.</p></div>
</div>
<div class="attribution">
</div></div>
</div>
</div>
<div class="sect1">
<h2 id="_implementation">Implementation</h2>
<div class="sectionbody">
<div class="ulist"><ul>
<li>
<p>
<a href="https://github.com/MLton/mlton/blob/master/mlton/ssa/restore.sig"><span class="monospaced">restore.sig</span></a>
</p>
</li>
<li>
<p>
<a href="https://github.com/MLton/mlton/blob/master/mlton/ssa/restore.fun"><span class="monospaced">restore.fun</span></a>
</p>
</li>
<li>
<p>
<a href="https://github.com/MLton/mlton/blob/master/mlton/ssa/restore2.sig"><span class="monospaced">restore2.sig</span></a>
</p>
</li>
<li>
<p>
<a href="https://github.com/MLton/mlton/blob/master/mlton/ssa/restore2.fun"><span class="monospaced">restore2.fun</span></a>
</p>
</li>
</ul></div>
</div>
</div>
<div class="sect1">
<h2 id="_details_and_notes">Details and Notes</h2>
<div class="sectionbody">
<div class="paragraph"><p>Based primarily on Section 19.1 of <a href="References#Appel98"> Modern Compiler
Implementation in ML</a>.</p></div>
<div class="paragraph"><p>The main deviation is the calculation of liveness of the violating
variables, which is used to predicate the insertion of phi arguments.
This is due to the algorithm’s bias towards imperative languages, for
which it makes the assumption that all variables are defined in the
start block and all variables are "used" at exit.</p></div>
<div class="paragraph"><p>This is "optimized" for restoration of functions with small numbers of
violating variables — use bool vectors to represent sets of violating
variables.</p></div>
<div class="paragraph"><p>Also, we use a <span class="monospaced">Promise.t</span> to suspend part of the dominance frontier
computation.</p></div>
</div>
</div>
</div>
<div id="footnotes"><hr></div>
<div id="footer">
<div id="footer-text">
</div>
<div id="footer-badges">
</div>
</div>
</body>
</html>
|
