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
|
package com.seaofnodes.simple.node;
import com.seaofnodes.print.ExprPrinter;
import com.seaofnodes.simple.Parser;
import com.seaofnodes.simple.codegen.CodeGen;
import com.seaofnodes.simple.type.Type;
import com.seaofnodes.simple.util.BAOS;
import java.util.*;
public class RegionNode extends CFGNode {
// Source location for late discovered errors
public Parser.Lexer _loc;
public RegionNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; }
public RegionNode(RegionNode r, Parser.Lexer loc) { super(r); _loc = loc; }
public RegionNode(RegionNode r) { super(r); if( r!=null ) _loc = r._loc; }
@Override public Tag serialTag() { return Tag.Region; }
public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { baos.packed1(nIns()); }
static Node make( BAOS bais ) { return new RegionNode(null,new Node[bais.packed1()]); }
@Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
return p.p(label());
}
@Override public boolean blockHead() { return true; }
@Override
public Type compute() {
if( inProgress() ) return Type.CONTROL;
Type t = Type.XCONTROL;
for (int i = 1; i < nIns(); i++)
t = t.meet(in(i)._type);
return t;
}
@Override
public Node idealize() {
if( inProgress() ) return null;
Node progress = deadPath(false);
if( progress!=null ) return progress;
// If down to a single input, become that input
if( nIns()==2 && !hasPhi() )
return in(1); // Collapse if no Phis; 1-input Phis will collapse on their own
// If a CFG diamond with no merging, delete: "if( pred ) {} else {};"
if( !hasPhi() && nIns()>3 && // No Phi users, just a control user
in(1) instanceof CProjNode p1 &&
in(2) instanceof CProjNode p2 &&
addDepForwards(p1).in(0)==addDepForwards(p2).in(0) &&
p1.in(0) instanceof IfNode iff ) {
// Replace with the iff.ctrl directly
if( nIns()==3 ) return iff.ctrl();
// Just delete the path for fat Regions
setDef(1,iff.ctrl());
return delDef(2);
}
// Flatten stacked regions (no loops involved)
if( getClass() == RegionNode.class && nIns()>2 ) {
for( int i=1; i<nIns(); i++ )
if( cfg(i) instanceof RegionNode region && region.getClass() == RegionNode.class && region.nIns()>2 && !hasMidUser(region) ) {
assert !region.inProgress();
// Fold Phis
for( Node use : _outputs ) {
if( use instanceof PhiNode phi ) {
PhiNode phi2 = phi.in(i) instanceof PhiNode phi2x && phi2x.region()==region ? phi2x : null;
for( int j=1; j<region.nIns(); j++ )
phi.addDef(phi2==null ? phi.in(i) : phi2.in(j));
CodeGen.CODE.add(phi);
}
}
// Fold Region
for( int j=1; j<region.nIns(); j++ )
addDef(region.in(j));
setDef(i,CodeGen.CODE.XCTRL);
return this;
}
}
return null;
}
Node deadPath(boolean skipStart) {
// Delete dead paths into a Region
int path = findDeadInput(skipStart ? 2 :1);
if( path==0 ) return null;
// Do not delete the entry path of a loop (ok to remove the back edge
// and make the loop a single-entry Region which folds away the Loop).
// Folding the entry path confused the loop structure, moving the
// backedge to the entry point.
if( this instanceof LoopNode loop && loop.entry()==in(path) )
return null;
return removeDeadPath(path);
}
public Node removeDeadPath(int path) {
// Cannot use the obvious output iterator here, because a Phi deleting
// an input might recursively delete *itself*. This shuffles the
// output array, and we might miss iterating an unrelated Phi. So on
// rare occasions we repeat the loop to get all the Phis.
int nouts = 0;
while( nouts != nOuts() ) {
nouts = nOuts();
for( int i=0; i<nOuts(); i++ )
if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() ) {
CodeGen.CODE.addAll(phi.in(path)._outputs);
CodeGen.CODE.addAll(phi.delDef(path)._outputs);
}
}
if( !isDead() ) delDef(path);
return isDead() ? CodeGen.CODE.XCTRL : this;
}
private int findDeadInput(int startIdx) {
for( int i=startIdx; i<nIns(); i++ )
if( in(i)._type==Type.XCONTROL )
return i;
return 0; // All inputs alive
}
boolean hasPhi() {
for( Node phi : _outputs )
if( phi instanceof PhiNode )
return true;
return false;
}
// Is there a value in-between 2 Regions? Difficult to correctly fuse
// without extensive testing, so just ignore.
boolean hasMidUser(RegionNode r) {
for( Node use : r._outputs ) {
if( use==this ) continue;
if( use instanceof PhiNode ) {
for( Node data : use._outputs ) {
if( !(data instanceof PhiNode phi2) || phi2.region()!=this )
{ addDep(use); if( data!=null ) addDep(data); return true; }
}
} else
{ addDep(use); return true; } // Control user
}
return false;
}
// Immediate dominator of Region is a little more complicated.
@Override public int idepth() {
if( validIDepth() ) return _idepth;
int depth=0;
for( Node n : _inputs )
if( n!=null )
depth = Math.max(depth,((CFGNode)n).idepth()+1);
return cacheIDepth(depth);
}
@Override public CFGNode idom(Node dep) {
CFGNode lca = null;
// Recompute from predecessors: CFG edits can change the dominator.
for( int i=1; i<nIns(); i++ )
if( !cfg(i)._type.isHigh() )
lca = cfg(i).domLCA(lca,dep);
return lca;
}
// True if last input is null
public boolean inProgress() { return nIns()>1 && in(nIns()-1) == null; }
// Never equal if inProgress
@Override public boolean eq( Node n ) { return !inProgress(); }
}
|
