diff options
Diffstat (limited to 'chapter14/src/main')
11 files changed, 64 insertions, 36 deletions
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java index f3b213fb..9d425f7a 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -22,8 +22,7 @@ public class AddNode extends Node { @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) - return TypeInteger.TOP; + if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP; if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) { if (i1.isConstant() && i2.isConstant()) @@ -37,7 +36,7 @@ public class AddNode extends Node { } private static boolean overflow( long x, long y ) { - if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow + if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow } @Override diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/AndNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/AndNode.java index 7e4b898b..350859db 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -21,6 +21,7 @@ public class AndNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 238be00e..f0cca1e2 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -37,6 +37,9 @@ abstract public class BoolNode extends Node { Type t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) return BOOL.dual(); + // Compare of same + if( in(1)==in(2) ) + return doOp(ZERO,ZERO); if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) return doOp(i1,i2); @@ -53,10 +56,6 @@ abstract public class BoolNode extends Node { @Override public Node idealize() { - // Compare of same - if( in(1)==in(2) ) - return new ConstantNode(doOp(ZERO,ZERO)); - // Equals pushes constant to the right; 5==X becomes X==5. if( this instanceof EQ ) { if( !(in(2) instanceof ConstantNode) ) { @@ -68,14 +67,11 @@ abstract public class BoolNode extends Node { // Equals X==0 becomes a !X if( (in(2)._type == ZERO || in(2)._type == TypeMemPtr.NULLPTR) ) return new NotNode(in(1)); + // Equals bool == 1 becomes bool + if( in(2)._type == TRUE && in(1)._type == BOOL ) + return in(1); } - // 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 = AddNode.phiCon(this,this instanceof EQ); - if( phicon!=null ) return phicon; - return null; } @@ -113,8 +109,8 @@ abstract public class BoolNode extends Node { Node copyF() { return new LEF(null,null); } } - public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } } - public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs < rhs; } } - public static class LEF extends LE { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } } + public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQF(lhs,rhs); } } + public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LTF(lhs,rhs); } } + public static class LEF extends LE { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LEF(lhs,rhs); } } } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/LoadNode.java index a033a7cf..78ccc8a9 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -73,4 +73,8 @@ public class LoadNode extends MemOpNode { Node px = phi.in(idx); return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr(); } + + Node copy(Node mem, Node ptr) { + return new LoadNode(_name,_alias,_declaredType,mem,ptr); + } } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java index 382f78ae..96b569b5 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java @@ -631,7 +631,12 @@ public abstract class Node implements OutNode { E x = pred.apply(this); if( x != null ) return x; for( Node def : _inputs ) if( def != null && (x = def._walk(pred)) != null ) return x; - for( Node use : _outputs ) if( use != null && (x = use._walk(pred)) != null ) return x; + // Unroll iterator to survive junk CME + for( int i=0; i<_outputs.size(); i++ ) { + Node use = _outputs.get(i); + if( use != null && (x = use._walk(pred)) != null ) + return x; + } return null; } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/OrNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/OrNode.java index 1b32d4fb..e18996b7 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -21,6 +21,7 @@ public class OrNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java index ebed8dd1..05584423 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -11,7 +11,7 @@ public class PhiNode extends Node { final String _label; // The Phi type we compute must stay within the domain of the Phi. - // Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. + // Example Int stays Int, Ptr stays Ptr, Mem stays Mem. final Type _declaredType; public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } @@ -81,9 +81,16 @@ public class PhiNode extends Node { lhss[i] = in(i).in(1); rhss[i] = in(i).in(2); } - Node phi_lhs = new PhiNode(_label, _declaredType,lhss).peephole(); - Node phi_rhs = new PhiNode(_label, _declaredType,rhss).peephole(); - return op.copy(phi_lhs,phi_rhs); + Node phi_lhs = new PhiNode(_label, in(1).in(1)._type.glb(),lhss).peephole(); + Node phi_rhs = new PhiNode(_label, in(1).in(2)._type.glb(),rhss).peephole(); + Node phi_op = op.copy(phi_lhs,phi_rhs); + phi_op.setType(phi_op.compute()); + // If losing precision, don't do it + if( !phi_op._type.isa(_type) ) { + phi_op.kill(); + return null; + } + return phi_op; } // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. @@ -114,9 +121,13 @@ public class PhiNode extends Node { } private boolean same_op() { - for( int i=2; i<nIns(); i++ ) - if( in(1).getClass() != in(i).getClass() ) - return false; + for( int i=2; i<nIns(); i++ ) { + if( in(1).getClass() != in(i).getClass() ) return false; + if( in(1).in(1)._type.glb() != in(i).in(1)._type.glb() ) return false; + if( in(1).in(2)._type.glb() != in(i).in(2)._type.glb() ) return false; + } + // Load merging needs an anti-dep check. + if( in(1) instanceof MemOpNode ) return false; return true; } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/SarNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/SarNode.java index ba99fde8..881a3812 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -21,14 +21,14 @@ public class SarNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) { - if( i0.isConstant() && i1.isConstant() ) - return TypeInteger.constant(i0.value()>>i1.value()); - if( i1.isConstant() ) { - int log = (int)i1.value(); - return TypeInteger.make(-1L<<(63-log),(1L<<(63-log))-1); - } + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; + if (in(1)._type instanceof TypeInteger i1 && + in(2)._type instanceof TypeInteger i2) { + if( i1.isConstant() && i2.isConstant() ) + return TypeInteger.constant(i1.value()>>i2.value()); + if( i2._min < 0 || i2._max >= 64 ) + return TypeInteger.BOT; + return TypeInteger.make(i1._min>>i2._min,i1._max>>i2._min); } return TypeInteger.BOT; } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/ShlNode.java index 097a899c..605c5d86 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -21,6 +21,7 @@ public class ShlNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if (in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1) { if( i0.isConstant() && i1.isConstant() ) diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 16d78ebf..bed18d2b 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -21,10 +21,19 @@ public class ShrNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) { - if( i0.isConstant() && i1.isConstant() ) - return TypeInteger.constant(i0.value()>>>i1.value()); + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; + if (in(1)._type instanceof TypeInteger i1 && + in(2)._type instanceof TypeInteger i2) { + if( i1.isConstant() && i2.isConstant() ) + return TypeInteger.constant(i1.value()>>>i2.value()); + if( i2._min < 0 || i2._max >= 64 ) + return TypeInteger.BOT; + // Zero shifting a negative makes a larger positive + // so get the endpoints correct. + long s1 = i1._min>>>i2._min; + long s2 = i1._max>>>i2._min; + boolean wrap = i1._min < 0 && i1._max >=0; + return TypeInteger.make(wrap ? 0 : Math.min(s1,s2),Math.max(s1,s2)); } return TypeInteger.BOT; } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/XorNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/XorNode.java index 30a88dca..3978f048 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -21,6 +21,7 @@ public class XorNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) |