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
195
196
197
198
199
200
201
202
203
204
205
206
207
|
# Chapter 6: Peepholes for If
English | [日本語](README.ja.md)
[Previous: Chapter 5](../chapter05/README.md) |
[Next: Chapter 7](../chapter07/README.md)
The grammar is unchanged from [Chapter 5](../chapter05/05-grammar.md).
# Table of Contents
1. [Type System Revision](#type-system-revision)
2. [Peephole of `if`](#peephole-of-if)
3. [`Region` and `Phi`](#region-and-phi)
4. [Discussion](#discussion)
5. [Expanding Peephole Beyond Constant Expressions](#expanding-peephole-beyond-constant-expressions)
6. [Dominators](#dominators)
You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter06) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter05...linear-chapter06) it to the previous chapter.
In this chapter we do not add new language features. Our goal is to add peephole optimization to `if` statements.
## Type System Revision
We now need to extend the type system to introduce another lattice structure, in addition to the Integer sub-lattice.
As before we denote "Top" by T and "Bottom" by ⊥.
* "Ctrl" represents a live control, whereas "~Ctrl" represents a dead control.
* "INT" refers to an integer value, note that integer values have their own sub-lattice.
| | ⊥ | Ctrl | ~Ctrl | T | INT |
|-------|---|------|-------|-------|-----|
| T | ⊥ | Ctrl | ~Ctrl | T | INT |
| Ctrl | ⊥ | Ctrl | Ctrl | Ctrl | ⊥ |
| ~Ctrl | ⊥ | Ctrl | ~Ctrl | ~Ctrl | ⊥ |
| ⊥ | ⊥ | ⊥ | ⊥ | ⊥ | ⊥ |
* "Top" meets any type is that type,
* "Bottom" meets any type is "Bottom",
* "Top", "Bottom", "Ctrl", "~Ctrl" are classed as simple types,
* "Ctrl" meets "~Ctrl" is "Ctrl"
* Unless covered above, a simple type meets non-simple results in "Bottom"
The entire revised Lattice is shown below:
## Peephole of `if`
* Our general strategy is to continue parsing the entire `if` statement even if we know that one branch is dead.
* This approach creates dead nodes which get cleaned up by dead code
elimination. The benefits are that we do not introduce special logic during
parsing, the normal graph building machinery takes care of cleaning up dead
nodes.
* When we peephole an `If` node we test if the predicate is a constant. If so,
then one branch or the other is dead, depending on if the constant is `0` or not.
* When we add the `Proj` nodes, in this scenario, we already know one of the projections is dead. The peephole of the
relevant `Proj` node replaces the `Proj` with a `Constant` of type "~Ctrl" indicating dead control.
* At this point our dead code elimination would kill the `If` node since it has no uses
- but we cannot do that because we need to continue the parse. The
important observation is that *we __can__ kill the `If` node after __both__
the `Proj` nodes have been created*, because any subsequent control flow can
only see the `Proj` nodes.
* To ensure this, we add a dummy user to `If` before creating the first `Proj` and remove it immediately after, allowing the
second `Proj` to trigger a dead code elimination of the `If`.
* The live `Proj` gets replaced by the parent of `If`, whereas the dead `Proj` gets replaced by "~Ctrl".
* The parsing then continues as normal.
* The other changes are when we reach the merge point with a dead control.
* Again keeping with our strategy we merge as normal, including creating `Phi` nodes.
* The `Region` may have one of its inputs as "~Ctrl". This will be seen
by the `Phi` which then optimizes itself. If the `Phi` has just one live
input, the `Phi` peephole replaces itself with the remaining input.
* Finally, at the end, when the `Region` node is peepholed, we see that it has only one live input and no Phi uses
and can be replaced with its one live input.
## `Region` and `Phi`
One of the invariants we maintain is that for each control input to a
`Region` every `Phi` has a 1-to-1 relationship with a data input. Thus, if a
`Region` loses a control input, every `Phi`'s corresponding data input must be
deleted. Conversely, we cannot collapse a Region until it has no dependent
`Phi`s.
When processing `If` we do not remove control inputs to a `Region`, instead the
dead control input is simply set to `Constant(~Ctrl)`. The peephole logic in
a `Phi` notices this and replaces itself with the live input.
## Discussion
With the changes above, our peephole optimization is able to fold dead code when
an `if` statement has a condition that evaluates to `true` or `false` at compile time.
Let's look at a simple example below:
```java
if( true ) return 2;
return 1;
```
Before peephole:
After peephole:
Another example:
```java
int a=1;
if( true )
a=2;
else
a=3;
return a;
```
Before peephole:
After peephole:
## Expanding Peephole Beyond Constant Expressions
While our peephole of the `CFG` collapses dead code when the expression is
a compile-time constant, it does not do as well as it could with the following example:
```java
int a = 0;
int b = 1;
if( arg ) {
a = 2;
if( arg ) { b = 2; }
else b = 3;
}
return a+b;
```
In this example, `arg` is defined externally, and we have to assume it is not a constant.
However, the code repeats the `if( arg )` condition in the inner `if` statement.
We know that if the outer `if( arg )` is true, then the *inner `if` must also evaluate to true*.
Our peephole at present cannot see this:
What we would like is for our peephole to see that the inner `if` is fully determined by the
outer `if` and thus, the code can be simplified as follows:
```java
int a = 0;
int b = 1;
if ( arg ) {
a = 2;
b = 2;
}
return a+b;
```
That is, the final outcome is either `4` if `arg` happens to be true, or `1` if `arg` happens to be false.
## Dominators
The key to implementing this peephole is the observation that the inner `if` is completely determined by the
outer `if`. In compiler parlance, we say that the outer `if` dominates the inner `if`.
There is a generic way to determine this type of domination; it involves constructing a dominator
tree. For details of how to do this, please refer to the paper `A Simple, Fast Dominance Algorithm`.[^1]
However, constructing a dominator tree is an expensive operation; one that we would not like to
do in the middle of parsing. Fortunately, since we do not have loops yet, we do not
have back edges in our control flow graph. Our control flow graph is essentially hierarchical, tree like.
Thus, a simple form of dominator identification is possible.
The main idea is that we can assign a `depth` to each control node, this represents the node's depth
in the hierarchy. We can compute this depth incrementally as we need to. The nodes that are deeper in the hierarchy
have a greater depth than the ones above.
Secondly we know that for our control nodes, except for `Region`s, there is only one incoming control edge,
which means that most control nodes have a single immediate dominating control node. `Region` nodes are different
as they can have one or more control edges; but, we know that for `if` statements, a `Region` node has exactly two
control inputs, one from each branch of the `if`. To find the immediate dominator of a `Region` node in the
limited scenario of an `if`, we can follow the immediate dominator of each branch until we find the common ancestor
node that dominates both the branches.
If this ancestor node is also an `if` and its predicate is the same as the current `if`, then we know that
the outcome of the present `if` is fully determined.
The code that does this check is in the [`compute` method of the `if`](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java#L38-L45).
The `idom` method in `Node` provides a default implementation of the depth based immediate dominator calculation.
`Region` [overrides this](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java#L57-L74) to implement the more complex search described above.
It turns out that to simplify the example above, we need a [further peephole in our `Add` node](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java#L64-L67).
With all these changes, the outcome of the peephole is just what we would like to see!
[^1]: Cooper, K. D. Cooper, Harvey, T. J., and Kennedy, K. (2001).
A Simple, Fast Dominance Algorithm.
|
