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
|
package com.seaofnodes.simple.node;
import com.seaofnodes.simple.codegen.CodeGen;
import com.seaofnodes.simple.type.*;
public class AddNode extends ArithNode {
@Override boolean allowFloat() { return true; }
public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
public AddNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs, mode); }
@Override public Tag serialTag() { return Tag.Add; }
@Override public String label() { return "Add"; }
@Override public String op() { return "+"; }
@Override long doOp( long x, long y ) { return x + y; }
@Override double doOp(double x, double y ) { return x + y; }
@Override TypeInteger doOp(TypeInteger x, TypeInteger y) {
// Fold ranges like {0-1} + {2-3} into {2-4}.
if( !overflow(x._min,y._min) &&
!overflow(x._max,y._max) )
return TypeInteger.make(x._min+y._min,x._max+y._max);
return TypeInteger.BOT;
}
@Override
public Node idealize () {
// Settle the one-shot arithmetic mode before applying family-specific
// algebraic identities.
if( _mode==0 )
return super.idealize();
Node lhs = in(1);
Node rhs = in(2);
if( rhs instanceof AddNode add && add.err()!=null )
return null;
Type t2 = rhs._type;
// Add of 0. We do not check for (0+x) because this will already
// canonicalize to (x+0)
if( t2 == TypeInteger.ZERO && lhs._type.isa(compute()) )
return lhs;
// Add of same to a multiply by 2
if( lhs==rhs && _mode==1 )
return new ShlNode(null,lhs,CodeGen.CODE.con(1));
// Goal: a left-spine set of adds, with constants on the rhs (which then fold).
// Move non-adds to RHS
if( !(lhs instanceof AddNode) && rhs instanceof AddNode )
return swap12();
// x+(-y) becomes x-y
if( rhs instanceof MinusNode minus )
return new SubNode(lhs,minus.in(1),_mode);
// Now we might see (add add non) or (add non non) or (add add add) but never (add non add)
// Do we have x + (y + z) ?
// Swap to (x + y) + z
// Rotate (add add add) to remove the add on RHS
if( rhs instanceof AddNode add )
return copy(copy(lhs,add.in(1)).peephole(), add.in(2));
// Now we might see (add add non) or (add non non) but never (add non add) nor (add add add)
if( !(lhs instanceof AddNode) ) {
// Rotate; look for (add (phi cons) con/(phi cons))
if( spine_cmp(lhs,rhs,this) ) return swap12();
Node n = phiCon(this,true);
return n == null ? super.idealize() : n;
}
// Now we only see (add add non)
// Dead data cycle; comes about from dead infinite loops. Do nothing,
// the loop will peep as dead after a bit.
if( lhs.nIns()>=2 && lhs.in(1) == lhs )
return null;
// Do we have (x + con1) + con2?
// Replace with (x + (con1+con2) which then fold the constants
// lhs.in(2) is con1 here
// If lhs.in(2) is not a constant, we add ourselves as a dependency
// because if it later became a constant then we could make this
// transformation.
if( addDep(lhs.in(2))._type.isConstant() && rhs._type.isConstant() )
return copy(lhs.in(1),copy(lhs.in(2),rhs).peephole());
// Do we have ((x + (phi cons)) + con) ?
// Do we have ((x + (phi cons)) + (phi cons)) ?
// Push constant up through the phi: x + (phi con0+con0 con1+con1...)
Node phicon = phiCon(this,true);
if( phicon!=null ) return phicon;
// Now we sort along the spine via rotates, to gather similar things together.
// Do we rotate (x + y) + z
// into (x + z) + y ?
if( spine_cmp(lhs.in(2),rhs,this) )
return copy(copy(lhs.in(1),rhs).peephole(),lhs.in(2));
return super.idealize();
}
// Rotation is only valid for associative ops, e.g. Add, Mul, And, Or, Xor.
// Do we have ((phi cons)|(x + (phi cons)) + con|(phi cons)|(op y con)) ?
// Push constant up through the phi: x + (phi con0+con0 con1+con1...)
static Node phiCon(Node op, boolean rotate) {
Node lhs = op.in(1);
Node rhs = op.in(2);
if( rhs._type==TypeInteger.TOP ) return null;
// LHS is either a Phi of constants, or another op with Phi of constants
PhiNode lphi = pcon(lhs,op);
if( rotate && lphi==null && lhs.nIns() > 2 ) {
// Only valid to rotate constants if both are same associative ops
if( lhs.getClass() != op.getClass() ) return null;
lphi = pcon(lhs.in(2),op); // Will rotate with the Phi push
}
if( lphi==null ) return null;
if( lphi.region().nIns() <=2 ) return null; // Phi is collapsing
// RHS is a constant or a Phi of constants
if( !(rhs instanceof ConstantNode) && pcon(rhs,op)==null )
return null;
// If both are Phis, must be same Region
if( rhs instanceof PhiNode && lphi.in(0) != rhs.in(0) )
return null;
// Note that this is the exact reverse of Phi pulling a common op down
// to reduce total op-count. We don't get in an endless push-up
// push-down peephole cycle because the constants all fold first.
Node[] ns = new Node[lphi.nIns()];
ns[0] = lphi.in(0);
// Push constant up through the phi: x + (phi con0+con0 con1+con1...)
for( int i=1; i<ns.length; i++ )
ns[i] = op.copy(lphi.in(i), rhs instanceof PhiNode ? rhs.in(i) : rhs).peephole();
String label = lphi._label + (rhs instanceof PhiNode rphi ? rphi._label : "");
Node phi = new PhiNode(label,ns).peephole();
// Rotate needs another op, otherwise just the phi
return lhs==lphi ? phi : op.copy(lhs.in(1),phi);
}
/**
* Tests if the op is a phi and has all constant inputs.
* If not, returns null.
* If op is a phi, but its inputs are not all constants, then dep is added as
* a dependency to the phi's non-const input, because if later the input turn into a constant
* dep can make progress.
*/
static PhiNode pcon(Node op, Node dep) {
return op instanceof PhiNode phi && !(phi instanceof ParmNode) && phi.allCons(dep) ? phi : null;
}
// Compare two off-spine nodes and decide what order they should be in.
// Do we rotate ((x + hi) + lo) into ((x + lo) + hi) ?
// Generally constants always go right, then Phi-of-constants, then muls, then others.
// Ties with in a category sort by node ID.
// TRUE if swapping hi and lo.
static boolean spine_cmp( Node hi, Node lo, Node dep ) {
if( lo._type.isConstant() || lo instanceof ConFldOffNode ) return false;
if( hi._type.isConstant() || hi instanceof ConFldOffNode ) return true ;
if( lo instanceof PhiNode lphi && lphi.region()._type==Type.XCONTROL ) return false;
if( hi instanceof PhiNode hphi && hphi.region()._type==Type.XCONTROL ) return false;
if( lo instanceof PhiNode && lo.allCons(dep) ) return false;
if( hi instanceof PhiNode && hi.allCons(dep) ) return true ;
if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true;
if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false;
// Same category of "others"
return lo._nid > hi._nid;
}
@Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs,_mode); }
}
|
