Folding loads before phis needs more work (#116)

* Folding loads before phis needs more work

Have to check load alias & offset/field match.
Could work for stores as well, will need to check more inputs

* Preserve SAR/SHL sharpness with variant shifts

* phi-node cloning honors unrelated argument types

* bool can never do phiCon

* dont fold shifts outside the range 0-63

* Now allowed to fold Loads in Phi

Because honors glb() of inputs

* Correct shr of mixed sign

* yank load merge again

needs an anti-dep check

* Stop phi-merge if it loses precision

* wrap bug

13 files changed, 173 insertions, 37 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() )
diff --git a/chapter14/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter06Test.java
index cddf0ae2..516dbf09 100644
--- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter06Test.java
+++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter06Test.java
@@ -65,7 +65,7 @@ else
     b=5;
 return b;""", TypeInteger.BOT);
         StopNode stop = parser.parse().iterate(true);
-        assertEquals("return Phi(Region39,42,5);", stop.toString());
+        assertEquals("return Phi(Region34,42,5);", stop.toString());
     }
 
     @Test
diff --git a/chapter14/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter14Test.java
index 7d6fecf9..0464f3ec 100644
--- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter14Test.java
+++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter14Test.java
@@ -158,6 +158,19 @@ return j;
     }
 
     @Test
+    public void testWrapShr() {
+        Parser parser = new Parser(
+"""
+return (arg >>> 1)==0;
+""");
+        StopNode stop = parser.parse(false).iterate(true);
+        assertEquals("return (!(arg>>>1));", stop.toString());
+        assertEquals(1L, Evaluator.evaluate(stop, 0));
+        assertEquals(1L, Evaluator.evaluate(stop, 1));
+        assertEquals(0L, Evaluator.evaluate(stop, 2));
+    }
+
+    @Test
     public void testOr() {
         Parser parser = new Parser(
 """
@@ -181,6 +194,101 @@ return arg;
     }
 
     @Test
+    public void testLoadBug() {
+        Parser parser = new Parser(
+"""
+struct A { int i; }
+struct B { int i; }
+A a = new A;
+A t1 = new A;
+B b = new B;
+B t2 = new B;
+int i;
+if (arg) i = a.i;
+else     i = b.i;
+return i;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return Phi(Region31,.i,.i);", stop.toString());
+        assertEquals(0L, Evaluator.evaluate(stop, 0));
+    }
+
+    @Test
+    public void testBug2() {
+        Parser parser = new Parser(
+"""
+int z = 0;
+while (1) {
+    int j;
+    if (arg&3) {
+        j = arg >> 2;
+    } else {
+        j = (arg >> 3)+z;
+    }
+    return j+1;
+}
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return ((arg>>Phi(Region32,2,3))+1);", stop.toString());
+        assertEquals(1L, Evaluator.evaluate(stop, 0));
+        assertEquals(1L, Evaluator.evaluate(stop, 1));
+        assertEquals(2L, Evaluator.evaluate(stop, 7));
+        assertEquals(2L, Evaluator.evaluate(stop, 8));
+    }
+
+    @Test
+    public void testBug3() {
+        Parser parser = new Parser(
+"""
+flt f = arg;
+bool b;
+if (arg&3) b = f == 1.0;
+else       b = f == 2.0;
+if (arg&5) b = arg == 1;
+return b;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return Phi(Region37,(arg==1),((flt)arg==Phi(Region23,1.0,2.0)));", stop.toString());
+        assertEquals(1L, Evaluator.evaluate(stop, 1));
+        assertEquals(0L, Evaluator.evaluate(stop, 2));
+        assertEquals(0L, Evaluator.evaluate(stop, 3));
+    }
+
+    @Test
+    public void testBug4() {
+        Parser parser = new Parser(
+"""
+int i;
+if (arg&7) i=3;
+else       i=2;
+return (arg == i) == 1;
+""");
+        StopNode stop = parser.parse(false).iterate(true);
+        assertEquals("return (arg==Phi(Region18,3,2));", stop.toString());
+        assertEquals(0L, Evaluator.evaluate(stop,  0));
+        assertEquals(0L, Evaluator.evaluate(stop,  1));
+        assertEquals(0L, Evaluator.evaluate(stop,  2));
+        assertEquals(1L, Evaluator.evaluate(stop,  3));
+    }
+
+    @Test
+    public void testBug5() {
+        Parser parser = new Parser(
+"""
+int d = -1;
+while (1) {
+    int i = (arg & 7) + (9223372036854775807 - 7);
+    if (arg & 1) i = ((arg&3) + (9223372036854775807 - 3)) & d;
+    return i + -1;
+}
+""");
+        StopNode stop = parser.parse(false).iterate(true);
+        assertEquals("return (Phi(Region43,((arg&3)+9223372036854775804),((arg&7)+9223372036854775800))+-1);", stop.toString());
+        assertEquals(0x7FFFFFFFFFFFFFF7L, Evaluator.evaluate(stop,  0));
+        assertEquals(0x7FFFFFFFFFFFFFFCL, Evaluator.evaluate(stop,  1));
+    }
+
+    @Test
     public void testTypes() {
         Parser parser = new Parser(
 """