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
|
% MIR Optimisations (Design Notes)
De-Tuple
========
Purpose: Remove useless tuples created in `match (a, b) { (a,b) => { ... }}`
Algorithm
---------
Detect `Local(N) = Tuple(...)` and record.
If the contents of the tuple is invalidated, delete the record
If a recorded local is moved, delete record
If a recorded local is mutated, delete record
If a recorded local is used via field access, record the field and location
- If a field is accessed twice, delete the record
At the end of the block, remove original tuple assignment and propagate the values to destinations.
De-Temporary (version 1)
========================
Purpose: Eliminate useless temporaries
```
_1 = _0.1
_2 = foo(_1)
```
Algorithm
---------
- Where the pattern `Local(N) = Use(...)` is seen, record that statement as the assignment for `Local(N)`.
- Detect any uses of `Local(N)` in mutation context (e.g. `Field(Local(N), 0) = ...`) or as a borrow and remove from the
list (as these cause the local to diverge from its source).
- Detect any by-value or mutation uses of the origin value that would mean that moving the assignment forwards would
lead to a use-after-free or incorrect value.
- Find any uses of locals recorded locals
- If this is of a Copy value, the replacement
- Copy values can be reused freely
- If the value is used at the top level of the source RValue, do the replacemnet and remove the record
- !Copy value moved, so can't be moved again.
- Otherwise, remove the record
- The value was used, so then assignment can't be replaced with later and deleted.
Pseudocode
----------
```
for stmt in block.statements
{
check_for_mutate_or_borrow_of_dest();
check_for_mutate_or_move_of_source();
do_replacements(stmt);
if let Assign(e) = stmt
{
if let Local(idx) = e.dst && let Use(_) = e.src
{
assign_list.insert(idx, stmt_idx)
}
}
}
fn do_replacements(stmt)
{
visit_lvalues(stmt, |lv, usage| {
top_level = true;
// 1. Search for replacements
visit_lvalues(lv, |ilv, usage2| {
if Local(i) == ilv {
if replacement = find_replacement(i) {
if is_copy(ilv) {
ilv = replacement
}
else if top_level {
ilv = replacement
remove_replacement(i)
}
else {
remove_replacement(i)
}
}
}
});
// Early-return (don't recuse)
return true;
});
}
```
Return Backprop
===============
Purpose: Eliminate useless temporaries in creating the return value
Locate `RETURN = Local(N)` and replace use of Local(N) as assignment destination with RETURN
Note: Only replace assignments that are setting the value that will become the return value.
Algorithm
---------
TODO:
Pseudocode
----------
TODO:
Dead Assignment Elimination
===========================
Purpose: Remove dead code from previous passes
Remove assignments where the assigned value isn't read/borrowed before next assign
Algorithm
---------
Pseudocode
---------
Dead Drop Flag Elimination
==========================
Purpose: Remove unused (or unchanged) drop flags
Algorithm
---------
- Enumerate all changes to drop flags
- If a flag is never set, replace all uses with its default and delete
- If a flag is never used, delete
Constant Propagation
====================
Purpose: Allow deletion of useless code (`if false`) and expansion of `size_of` (and relevant optimisations)
Algorithm
---------
- Track assignments of slots with constants
- Erase record if the slot is invalidated
- Replace usage of the slot where possible with the constant
- Evaluate BinOps with both arguments a known slot
Value Forward Propagation
=========================
Purpose: Determine when a value has the same value in all paths to a BB and move the assignment into that BB
Inlining
========
Purpose: Inline simple methods
Algorithm
---------
- For each function call:
- Check if the called function is simple enough to be inlined
- A single BB - inline
- Three bbs (first being a function call) - inline
- First bb ends with a switch of a constant parameter, and all arms point to return or a return bb
CFG Simplification
==================
Purpose: Remove gotos to blocks that only have a single use
|
