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
|
# SCCP Within a Function
English | [日本語](README.ja.md)
[Previous: Methods and Types](../chapter23/README.md) |
[Next: SCCP Across Functions](../chapter-interprocedural-sccp/README.md)
This chapter introduces optimistic type analysis within each function. It
starts with the existing pessimistic peepholes, resets flow types to TOP,
then propagates reachable control and values to a fixed point. Calls keep
their conservative interfaces; discovering calls is the next chapter's topic.
The [chapter split](../docs/chapter-split.md) uses names while the chapter
boundaries settle. This is an independent compiler snapshot, extracted from
Chapter 24. The numbered snapshot remains a comparison baseline.
## Sparse Conditional Constant Propagation
[SCCP](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation)
is the top-down version of the same peephole/constant-folding work we have
been doing all along. The rules for the algorithm are well known from the
literature and commonly taught at the college level;
[example slides](https://www.cse.psu.edu/~gxt29/teaching/cse522s23/slides/08monotoneFramework.pdf).
- We have a lattice already
- We have SSA form already (hence the algorithm is *sparse*)
- We have a mapping from Nodes to Types (`Node._type`)
- We have transfer functions (`Node.compute`) already.
We initialize all `_type` fields to ⊤ (as opposed to ⊥), and place all Nodes on
a worklist. We pull a Node from the worklist, run the transfer function
`node.compute()`, and if the result changes from `node._type` we update
`node._type` and put its output neighbors on the worklist. A simplified
version with all asserts and debug helpers removed:
```java
while( (n = code._iter._work.pop()) != null ) {
Type nval = n.compute();
if( n._type != nval ) {
assert n._type.isa(nval); // Types start high and always fall
n._type = nval; // Update type in Node
code._iter.addAll(n._outputs);// Neighbors might change, need to inspect
}
}
```
This algorithm always terminates (and generally fairly quickly) and always
reaches a *fixed point*, as "best answer" subject to the limits of our lattice
and transfer functions. The resulting types are monotonically better than
those found by the peephole rules; we can then run the peephole rules on nodes
with improved types, to see if unrelated peepholes can fire - such as newly
discovered constants replacing computations with ConstantNodes.
The following is SSA pseudocode:
```text
int x0 = 1; // x0 = 1
while( rand ) {
x1 = phi(x0,x2); // x1 = BOT = phi(1,BOT)
x2 = 2 - x1; // x2 = BOT = 2 - BOT
}
return x1
```
Without SCCP, this small program cannot fold the computation of `x`.
A glance at the program tells us `x` must always be a `1` but
the bottom-up (pessimistic) approach decides that since x1 is BOT, x2 must be
BOT so x1 must be BOT. We need the optimistic approach to break the
stalemate, and just *assume* x1 is `1`, and then we can discover that x2 is
also a `1`. Folding the value does not prove the loop terminates or make
its condition and side effects removable.
The algorithm progresses from left to right and stops when no more changes
happen:
|Var|init|x0=1|x1=phi(1,T)|x2=2-x1|x1=phi(1,1)|
|---|----|----|-----------|-------|-----------|
|x0 | T | 1 | 1 | 1 | 1 |
|x1 | T | T | 1 | 1 | 1 |
|x2 | T | T | T | 1 | 1 |
### Conditional
Since our control flow is in the same graph as our data flow (that's the major
point of Sea-of-Nodes!), we need not do anything special and our algorithm is
*conditional* already. Again an example is interesting:
Again using SSA pseudocode:
```text
int x0 = 1; // x0 = 1
while( rand ) {
x1 = phi(x0,x4); // x1 = BOT = phi(1,BOT)
if( x1 == 1 ) // Since x1 is BOT, both true and false arms are taken
x2 = 2 - x1; // x2 = BOT = 2 - BOT
else x3 = 99; // x3 = 99
x4 = phi(x2,x3); // x4 = BOT = phi(BOT,99)
}
return x1
```
Again the algorithm progresses from left to right, although this time not all
paths are reachable. The `if` result is a pair of Control values, shown as
either `C` if the path is alive or `X` if not. This is used when we compute
`x4 = phi(x2,x3)`; the `PhiNode` ALSO checks the corresponding control input
from the `if` and only merges alive paths.
|Var|init |x0=1|x1=phi(1,T)| 1 == 1? | x2=2-x1 | x3=99 |x4=phi(C/1,X/99)|x1=phi(1,1)|
|---|-----|----|-----------|---------|---------|---------|----------------|-----------|
|x0 | T | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
|x1 | T | T | 1 | 1 | 1 | 1 | 1 | 1 |
|if | T | T | T | [C,X] | [C,X] | [C,X] | [C,X] | [C,X] |
|x2 | T | T | T | T | 1 | 1 | 1 | 1 |
|x3 | T | T | T | T | T | 99 | 99 | 99 |
|x4 | T | T | T | T | T | T | 1 | 1 |
This kind of conditional constant propagation really helps if a condition can
be proven true or false, as this removes a test and branch from the optimized
program. A common way this happens is with null tests; here is the same
program above, but using null pointers instead of integers:
```java
List head = notNullList();
while( rand ) {
if( head ) head = new List(head,payload);
else { head = null; default_action(); }
}
```
Here since `head` starts not-null, it can never be null and the
`default_action` can never happen, and the loop can
simplify:
```java
List head = notNullList();
while( rand ) {
head = new List(head,payload);
}
```
## Convergence and calls
Integer ranges can grow one value per loop trip. A loop Phi widens its range
after a bounded number of such steps. Constants stay precise; above-center
ranges must remain narrow so they can fall to constants monotonically.
During SCCP, each function retains its unknown-caller Start input. Call edges
are disconnected, and call results keep the summaries already established by
pessimistic analysis. Those summaries can be sharper than the written
signature, so discarding them would lose valid facts. Calls still carry
whole-memory effects. The solve discovers no new call edges.
After the solve, ordinary peepholes relink calls and apply inlining as before.
FinalizeIR removes uncalled bodies and detaches calls for scheduling. This
separates local optimistic analysis from the existing pessimistic call machinery.
`SccpTest` checks a loop fixed point and a function called with 1 and 2: its
parameter remains general here, while the following chapter infers [1,2].
A recursive function whose return type needs optimistic propagation through
calls can still report "No defined return type" here. The next chapter adds
that inference and the widening needed to make it converge; its
`Chapter24Test.testRecursiveWidening` exercises both recursive data cycles.
## Building and checking
Run `make lib` once for Java test dependencies, then `make tests` in this
directory. From the repository root, use `make tests CHAPTERS=chapter-sccp`.
The inherited tests retain their historical class names.
The [grammar](docs/24-grammar.md) includes chained comparisons inherited from
the extraction baseline. Their planned teaching home is with short-circuit
expressions. Allocator tuning is covered separately by the planned appendix.
|
