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
|
package com.seaofnodes.simple;
import com.seaofnodes.simple.node.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Random;
/**
* The IterOptim runs after parsing. It iterates the peepholes to a fixed point
* so that no more peepholes apply. This should be linear because peepholes rarely
* (never?) increase code size. The graph should monotonically reduce in some
* dimension, which is usually size. It might also reduce in e.g. number of
* MulNodes or Load/Store nodes, swapping out more "expensive" Nodes for cheaper
* ones.
*
* The theoretical overall worklist is mindless just grabbing the next thing and
* doing it. If the graph changes, put the neighbors on the worklist. Lather,
* Rinse, Repeat until the worklist runs dry.
*
* The main issues we have to deal with:
*
* <ul>
* <li>Nodes have uses; replacing some set of Nodes with another requires more graph
* reworking. Not rocket science, but it can be fiddly. Its helpful to have a
* small set of graph munging utilities, and the strong invariant that the graph
* is stable and correct between peepholes. In our case `Node.subsume` does
* most of the munging, building on our prior stable Node utilities.</li>
*
* <li>Changing a Node also changes the graph "neighborhood". The neigbors need to
* be checked to see if THEY can also peephole, and so on. After any peephole
* or graph update we put a Nodes uses and defs on the worklist.</li>
*
* <li>Our strong invariant is that for all Nodes, either they are on the worklist
* OR no peephole applies. This invariant is easy to check, although expensive.
* Basically the normal "iterate peepholes to a fixed point" is linear, and this
* check is linear at each peephole step... so quadratic overall. Its a useful
* assert, but one we can disable once the overall algorithm is stable - and
* then turn it back on again when some new set of peepholes is misbehaving.
* The code for this is turned on in `IterOptim.iterate` as `assert
* progressOnList(stop);`</li>
* </ul>
*/
public abstract class IterPeeps {
private static final WorkList<Node> WORK = new WorkList<>();
public static <N extends Node> N add( N n ) {
return (N)WORK.push(n);
}
public static void addAll( ArrayList<Node> ary ) {
WORK.addAll(ary);
}
/**
* Iterate peepholes to a fixed point
*/
public static StopNode iterate(StopNode stop, boolean show) {
assert progressOnList(stop);
int cnt=0;
Node n;
while( (n=WORK.pop()) != null ) {
if( n.isDead() ) continue;
cnt++; // Useful for debugging, searching which peephole broke things
Node x = n.peepholeOpt();
if( x != null ) {
if( x.isDead() ) continue;
// peepholeOpt can return brand-new nodes, needing an initial type set
if( x._type==null ) x.setType(x.compute());
// Changes require neighbors onto the worklist
if( x != n || !(x instanceof ConstantNode) ) {
// All outputs of n (changing node) not x (prior existing node).
for( Node z : n._outputs ) WORK.push(z);
// Everybody gets a free "go again" in case they didn't get
// made in their final form.
WORK.push(x);
// If the result is not self, revisit all inputs (because
// there's a new user), and replace in the graph.
if( x != n ) {
for( Node z : n. _inputs ) WORK.push(z);
n.subsume(x);
}
}
// If there are distant neighbors, move to worklist
n.moveDepsToWorklist();
assert progressOnList(stop); // Very expensive assert
}
if( n.isUnused() && !(n instanceof StopNode) )
n.kill(); // Just plain dead
}
if( show )
System.out.println(new GraphVisualizer().generateDotOutput(stop,null,null));
return stop;
}
// Visit ALL nodes and confirm the invariant:
// Either you are on the WORK worklist OR running `iter()` makes no progress.
// This invariant ensures that no progress is missed, i.e., when the
// worklist is empty we have indeed done all that can be done. To help
// with debugging, the {@code assert} is broken out in a place where it is easy to
// stop if a change is found.
// Also, the normal usage of `iter()` may attempt peepholes with distance
// neighbors and these should fail, but will then try to add dependencies
// {@link #Node.addDep} which is a side effect in an assert. The {@link
// #midAssert} is used to stop this side effect.
private static boolean MID_ASSERT;
public static boolean midAssert() { return MID_ASSERT; }
private static boolean progressOnList(Node stop) {
MID_ASSERT = true;
int old_cnt = Node.ITER_CNT, old_nop = Node.ITER_NOP_CNT;
Node changed = stop.walk( n -> {
if( WORK.on(n) ) return null;
Node m = n.peepholeOpt();
if( m==null ) return null;
System.err.println("BREAK HERE FOR BUG");
return m;
});
Node.ITER_CNT = old_cnt; Node.ITER_NOP_CNT = old_nop;
MID_ASSERT = false;
return changed==null;
}
public static void reset() {
WORK.clear();
}
/**
* Classic WorkList, with a fast add/remove, dup removal, random pull.
* The Node's nid is used to check membership in the worklist.
*/
public static class WorkList<E extends Node> {
private Node[] _es;
private int _len;
private final BitSet _on; // Bit set if Node._nid is on WorkList
private final Random _R; // For randomizing pull from the WorkList
private final long _seed;
/* Useful stat - how many nodes are processed in the post parse iterative opt */
private long _totalWork = 0;
WorkList() { this(123); }
WorkList(long seed) {
_es = new Node[1];
_len=0;
_on = new BitSet();
_seed = seed;
_R = new Random();
_R.setSeed(_seed);
}
/**
* Pushes a Node on the WorkList, ensuring no duplicates
* If Node is null it will not be added.
*/
public E push( E x ) {
if( x==null ) return null;
int idx = x._nid;
if( !_on.get(idx) ) {
_on.set(idx);
if( _len==_es.length )
_es = Arrays.copyOf(_es,_len<<1);
_es[_len++] = x;
_totalWork++;
}
return x;
}
public void addAll( ArrayList<E> ary ) {
for( E n : ary )
push(n);
}
/**
* True if Node is on the WorkList
*/
boolean on( E x ) { return _on.get(x._nid); }
/**
* Removes a random Node from the WorkList; null if WorkList is empty
*/
E pop() {
if( _len == 0 ) return null;
int idx = _R.nextInt(_len);
E x = (E)_es[idx];
_es[idx] = _es[--_len]; // Compress array
_on.clear(x._nid);
return x;
}
public void clear() {
_len = 0;
_on.clear();
_R.setSeed(_seed);
_totalWork = 0;
}
}
}
|
