Chapter 14: Narrow typeslinear-chapter14

Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

18 files changed, 535 insertions, 71 deletions

diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 48350957..9d425f7a 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -21,14 +21,24 @@ public class AddNode 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());
+        Type t1 = in(1)._type, t2 = in(2)._type;
+        if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP;
+        if( t1 instanceof TypeInteger i1 &&
+            t2 instanceof TypeInteger i2 ) {
+            if (i1.isConstant() && i2.isConstant())
+                return TypeInteger.constant(i1.value()+i2.value());
+            // Fold ranges like {0-1} + {2-3} into {2-4}.
+            if( !overflow(i1._min,i2._min) &&
+                !overflow(i1._max,i2._max) )
+                return TypeInteger.make(i1._min+i2._min,i1._max+i2._max);
         }
-        return in(1)._type.meet(in(2)._type);
+        return TypeInteger.BOT;
     }
 
+    private static boolean overflow( long x, long y ) {
+        if(    (x ^      y ) < 0 ) return false; // unequal signs, never overflow
+        return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow
+    }
     @Override
     public Node idealize () {
         Node lhs = in(1);
@@ -37,7 +47,7 @@ public class AddNode extends Node {
 
         // Add of 0.  We do not check for (0+x) because this will already
         // canonicalize to (x+0)
-        if( t2 instanceof TypeInteger i && i.value()==0 )
+        if( t2 instanceof TypeInteger i && i.isConstant() && i.value()==0 )
             return lhs;
 
         // Add of same to a multiply by 2
@@ -100,7 +110,7 @@ public class AddNode extends Node {
         return null;
     }
 
-    // Rotation is only valid for associative ops, e.g. Add, Mul, And, Or.
+    // 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)) ?
     // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
     static Node phiCon(Node op, boolean rotate) {
diff --git a/src/main/java/com/seaofnodes/simple/node/AndNode.java b/src/main/java/com/seaofnodes/simple/node/AndNode.java
new file mode 100644
index 00000000..350859db
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java
@@ -0,0 +1,66 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+public class AndNode extends Node {
+    public AndNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "And"; }
+
+    @Override public String glabel() { return "&"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("&"), visited);
+        return sb.append(")");
+    }
+
+    @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() )
+                return TypeInteger.constant(i0.value()&i1.value());
+            // Sharpen allowed bits if either value is narrowed
+            long mask = i0.mask() & i1.mask();
+            return mask < 0 ? TypeInteger.BOT : TypeInteger.make(0,mask);
+        }
+        return TypeInteger.BOT;
+    }
+
+    @Override
+    public Node idealize() {
+        Node lhs = in(1);
+        Node rhs = in(2);
+        Type t1 = lhs._type;
+        Type t2 = rhs._type;
+
+        // And of -1.  We do not check for (-1&x) because this will already
+        // canonicalize to (x&-1)
+        if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==-1 )
+            return lhs;
+
+        // Move constants to RHS: con*arg becomes arg*con
+        if ( t1.isConstant() && !t2.isConstant() )
+            return swap12();
+
+        // 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,true);
+        if( phicon!=null ) return phicon;
+
+        return null;
+    }
+    @Override Node copy(Node lhs, Node rhs) { return new AndNode(lhs,rhs); }
+    @Override String err() {
+        if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '&' " + in(1)._type;
+        if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '&' " + in(2)._type;
+        return null;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index 48faefd2..f0cca1e2 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -8,6 +8,7 @@ import com.seaofnodes.simple.type.TypeFloat;
 import com.seaofnodes.simple.type.TypeMemPtr;
 
 import java.util.BitSet;
+import static com.seaofnodes.simple.type.TypeInteger.*;
 
 abstract public class BoolNode extends Node {
 
@@ -31,30 +32,30 @@ abstract public class BoolNode 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(doOp(i0.value(), i1.value()) ? 1 : 0);
-        }
-        if( in(1)._type instanceof TypeFloat i0 &&
-            in(2)._type instanceof TypeFloat i1 ) {
-            if (i0.isConstant() && i1.isConstant())
-                return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0);
-        }
-        return TypeInteger.BOT;
+    public TypeInteger compute() {
+        Type t1 = in(1)._type;
+        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);
+        if( t1 instanceof TypeFloat f1 &&
+            t2 instanceof TypeFloat f2 &&
+            f1.isConstant() && f2.isConstant() )
+            return TypeInteger.constant(doOp(f1.value(), f2.value()) ? 1 : 0);
+        return BOOL;
     }
 
-    boolean doOp(long   lhs, long   rhs) { throw Utils.TODO(); }
+    TypeInteger doOp(TypeInteger t1, TypeInteger t2) { throw Utils.TODO(); }
     boolean doOp(double lhs, double rhs) { throw Utils.TODO(); }
-    Node copyF(Node lhs, Node rhs) { throw Utils.TODO(); }
+    Node copyF(Node lhs, Node rhs) { return null; }
 
     @Override
     public Node idealize() {
-        // Compare of same
-        if( in(1)==in(2) )
-            return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0));
-
         // Equals pushes constant to the right; 5==X becomes X==5.
         if( this instanceof EQ ) {
             if( !(in(2) instanceof ConstantNode) ) {
@@ -64,25 +65,52 @@ abstract public class BoolNode extends Node {
                     return in(1)._type instanceof TypeFloat ? new EQF(in(2),in(1)) : new EQ(in(2),in(1));
             }
             // Equals X==0 becomes a !X
-            if( (in(2)._type == TypeInteger.ZERO || in(2)._type == TypeMemPtr.NULLPTR) )
+            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;
     }
 
-    public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } Node copyF() { return new EQF(null,null); } }
-    public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs <  rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } Node copyF() { return new LTF(null,null); }}
-    public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } Node copyF() { return new LEF(null,null); } }
+    public static class EQ extends BoolNode {
+        public EQ(Node lhs, Node rhs) { super(lhs,rhs); }
+        String op() { return "=="; }
+        TypeInteger doOp(TypeInteger i1, TypeInteger i2) {
+            if( i1==i2 && i1.isConstant() ) return TRUE;
+            if( i1._max < i2._min || i1._min > i2._max ) return FALSE;
+            return BOOL;
+        }
+        Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); }
+        Node copyF() { return new EQF(null,null); }
+    }
+    public static class LT extends BoolNode {
+        public LT(Node lhs, Node rhs) { super(lhs,rhs); }
+        String op() { return "<" ; }
+        TypeInteger doOp(TypeInteger i1, TypeInteger i2) {
+            if( i1._max <  i2._min ) return TRUE;
+            if( i1._min >= i2._max ) return FALSE;
+            return BOOL;
+        }
+        Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); }
+        Node copyF() { return new LTF(null,null); }
+    }
+    public static class LE extends BoolNode {
+        public LE(Node lhs, Node rhs) { super(lhs,rhs); }
+        String op() { return "<="; }
+        TypeInteger doOp(TypeInteger i1, TypeInteger i2) {
+            if( i1._max <= i2._min ) return TRUE;
+            if( i1._min >  i2._max ) return FALSE;
+            return BOOL;
+        }
+        Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); }
+        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; } Node copyF() { return null; } }
-    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 copyF() { return null; } }
-    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 copyF() { return 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; } 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/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java
index e0c95019..da9571db 100644
--- a/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -21,14 +21,17 @@ public class DivNode 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 i1.value() == 0
+        Type t1 = in(1)._type, t2 = in(2)._type;
+        if( t1.isHigh() || t2.isHigh() )
+            return TypeInteger.TOP;
+        if( t1 instanceof TypeInteger i1 &&
+            t2 instanceof TypeInteger i2 ) {
+            if (i1.isConstant() && i2.isConstant())
+                return i2.value() == 0
                     ? TypeInteger.ZERO
-                    : TypeInteger.constant(i0.value()/i1.value());
+                    : TypeInteger.constant(i1.value()/i2.value());
         }
-        return in(1)._type.meet(in(2)._type);
+        return TypeInteger.BOT;
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index a033a7cf..78ccc8a9 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/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/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index 95319c24..76564db0 100644
--- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -14,7 +14,7 @@ public abstract class MemOpNode extends Node {
     public final Type _declaredType;
 
 
-    public MemOpNode(String name, int alias, Type glb, Node... nodes ) {
+    public MemOpNode(String name, int alias, Type glb, Node...  nodes) {
         super(nodes);
         _name  = name;
         _alias = alias;
diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index ae8e9e1b..8ba45d26 100644
--- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -20,8 +20,12 @@ public class MinusNode extends Node {
 
     @Override
     public Type compute() {
-        if (in(1)._type instanceof TypeInteger i0)
-            return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0;
+        if( in(1)._type instanceof TypeInteger i0 ) {
+            if( i0.isHigh() ) return TypeInteger.TOP;
+            // Catch overflow wrapping on `-Long.MIN_VALUE`
+            if( i0 == TypeInteger.BOT || i0._min == Long.MIN_VALUE ) return TypeInteger.BOT;
+            return TypeInteger.make(-i0._max,-i0._min);
+        }
         return TypeInteger.TOP.meet(in(1)._type);
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 8c8a6e0a..f231a97b 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -21,12 +21,15 @@ public class MulNode 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());
+        Type t1 = in(1)._type, t2 = in(2)._type;
+        if( t1.isHigh() || t2.isHigh() )
+            return TypeInteger.TOP;
+        if( t1 instanceof TypeInteger i1 &&
+            t2 instanceof TypeInteger i2 ) {
+            if (i1.isConstant() && i2.isConstant())
+                return TypeInteger.constant(i1.value()*i2.value());
         }
-        return in(1)._type.meet(in(2)._type);
+        return TypeInteger.BOT;
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index d846fcef..96b569b5 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -93,10 +93,8 @@ public abstract class Node implements OutNode {
     @Override
     public final String toString() {  return print(); }
 
-    // This is a *deep* print.  This version will fail on cycles, which we will
-    // correct later when we can parse programs with loops.  We print with a
-    // tik-tok style; the common _print0 calls the per-Node _print1, which
-    // calls back to _print0;
+    // This is a *deep* print.  We print with a tik-tok style; the common
+    // _print0 calls the per-Node _print1, which calls back to _print0;
     public final String print() {
         return _print0(new StringBuilder(), new BitSet()).toString();
     }
@@ -633,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/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java
index 3cf69520..b3c77c45 100644
--- a/src/main/java/com/seaofnodes/simple/node/NotNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -20,8 +20,9 @@ public class NotNode extends Node {
     @Override
     public Type compute() {
         Type t0 = in(1)._type;
+        if( t0.isHigh() ) return TypeInteger.BOOL.dual();
         switch( t0 ) {
-        case TypeInteger i0:  return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0;
+        case TypeInteger i0:  return i0._max < 0 || i0._min > 0 ? TypeInteger.FALSE : (i0==TypeInteger.ZERO ? TypeInteger.TRUE : TypeInteger.BOT);
         case TypeFloat   i0:  return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0;
         case TypeMemPtr p0:
             // top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot
diff --git a/src/main/java/com/seaofnodes/simple/node/OrNode.java b/src/main/java/com/seaofnodes/simple/node/OrNode.java
new file mode 100644
index 00000000..e18996b7
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java
@@ -0,0 +1,63 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+public class OrNode extends Node {
+    public OrNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Or"; }
+
+    @Override public String glabel() { return "|"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("|"), visited);
+        return sb.append(")");
+    }
+
+    @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() )
+                return TypeInteger.constant(i0.value()|i1.value());
+        }
+        return TypeInteger.BOT;
+    }
+
+    @Override
+    public Node idealize() {
+        Node lhs = in(1);
+        Node rhs = in(2);
+        Type t1 = lhs._type;
+        Type t2 = rhs._type;
+
+        // Or of 0.  We do not check for (0|x) because this will already
+        // canonicalize to (x|0)
+        if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 )
+            return lhs;
+
+        // Move constants to RHS: con*arg becomes arg*con
+        if ( t1.isConstant() && !t2.isConstant() )
+            return swap12();
+
+        // 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,true);
+        if( phicon!=null ) return phicon;
+
+        return null;
+    }
+    @Override Node copy(Node lhs, Node rhs) { return new OrNode(lhs,rhs); }
+    @Override String err() {
+        if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '|' " + in(1)._type;
+        if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '|' " + in(2)._type;
+        return null;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index ebed8dd1..05584423 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/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/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java b/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java
new file mode 100644
index 00000000..44d3a587
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java
@@ -0,0 +1,38 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeFloat;
+
+import java.util.BitSet;
+
+public class RoundF32Node extends Node {
+    public RoundF32Node(Node lhs) { super(null, lhs); }
+
+    @Override public String label() { return "RoundF32"; }
+
+    @Override public String glabel() { return "(f32)"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        return in(1)._print0(sb.append("((f32)"), visited).append(")");
+    }
+
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeFloat i0 && i0.isConstant() )
+            return TypeFloat.constant((float)i0.value());
+        return in(1)._type;
+    }
+
+    @Override
+    public Node idealize() {
+        Node lhs = in(1);
+        Type t1 = lhs._type;
+
+        // RoundF32 of float
+        if( t1 instanceof TypeFloat tf && tf._sz==32 )
+            return lhs;
+
+        return null;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/SarNode.java b/src/main/java/com/seaofnodes/simple/node/SarNode.java
new file mode 100644
index 00000000..881a3812
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/SarNode.java
@@ -0,0 +1,56 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+public class SarNode extends Node {
+    public SarNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Sar"; }
+
+    @Override public String glabel() { return ">>"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append(">>"), visited);
+        return sb.append(")");
+    }
+
+    @Override
+    public Type compute() {
+        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;
+    }
+
+    @Override
+    public Node idealize() {
+        Node lhs = in(1);
+        Node rhs = in(2);
+        Type t2 = rhs._type;
+
+        // Sar of 0.
+        if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 )
+            return lhs;
+
+        // TODO: x >> 3 >> (y ? 1 : 2) ==> x >> (y ? 4 : 5)
+
+        return null;
+    }
+    @Override Node copy(Node lhs, Node rhs) { return new SarNode(lhs,rhs); }
+    @Override String err() {
+        if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '>>' " + in(1)._type;
+        if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '>>' " + in(2)._type;
+        return null;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/src/main/java/com/seaofnodes/simple/node/ShlNode.java
new file mode 100644
index 00000000..605c5d86
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java
@@ -0,0 +1,53 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+public class ShlNode extends Node {
+    public ShlNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Shl"; }
+
+    @Override public String glabel() { return "<<"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("<<"), visited);
+        return sb.append(")");
+    }
+
+    @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() )
+                return TypeInteger.constant(i0.value()<<i1.value());
+        }
+        return TypeInteger.BOT;
+    }
+
+    @Override
+    public Node idealize() {
+        Node lhs = in(1);
+        Node rhs = in(2);
+        Type t2 = rhs._type;
+
+        // Shl of 0.
+        if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 )
+            return lhs;
+
+        // TODO: x << 3 << (y ? 1 : 2) ==> x << (y ? 4 : 5)
+
+        return null;
+    }
+    @Override Node copy(Node lhs, Node rhs) { return new ShlNode(lhs,rhs); }
+    @Override String err() {
+        if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '<<' " + in(1)._type;
+        if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '<<' " + in(2)._type;
+        return null;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java
new file mode 100644
index 00000000..bed18d2b
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java
@@ -0,0 +1,56 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+public class ShrNode extends Node {
+    public ShrNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Shr"; }
+
+    @Override public String glabel() { return ">>>"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append(">>>"), visited);
+        return sb.append(")");
+    }
+
+    @Override
+    public Type compute() {
+        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;
+    }
+
+    @Override
+    public Node idealize() {
+        Node lhs = in(1);
+        Node rhs = in(2);
+        Type t2 = rhs._type;
+
+        // Shr of 0.
+        if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 )
+            return lhs;
+
+        // TODO: x >>> 3 >>> (y ? 1 : 2) ==> x >>> (y ? 4 : 5)
+
+        return null;
+    }
+    @Override Node copy(Node lhs, Node rhs) { return new ShrNode(lhs,rhs); }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
index 81cc6076..6d2f1711 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -26,18 +26,20 @@ public class SubNode extends Node {
         if( in(1)==in(2) )
             return TypeInteger.ZERO;
 
-        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());
+        Type t1 = in(1)._type, t2 = in(2)._type;
+        if( t1.isHigh() || t2.isHigh() )
+            return TypeInteger.TOP;
+        if( t1 instanceof TypeInteger i1 &&
+            t2 instanceof TypeInteger i2 ) {
+            if (i1.isConstant() && i2.isConstant())
+                return TypeInteger.constant(i1.value()-i2.value());
         }
 
-        return in(1)._type.meet(in(2)._type);
+        return TypeInteger.BOT;
     }
 
     @Override
     public Node idealize() {
-
         // x - (-y) is x+y
         if( in(2) instanceof MinusNode minus )
             return new AddNode(in(1),minus.in(1));
diff --git a/src/main/java/com/seaofnodes/simple/node/XorNode.java b/src/main/java/com/seaofnodes/simple/node/XorNode.java
new file mode 100644
index 00000000..3978f048
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java
@@ -0,0 +1,63 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+
+import java.util.BitSet;
+
+public class XorNode extends Node {
+    public XorNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Xor"; }
+
+    @Override public String glabel() { return "^"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("^"), visited);
+        return sb.append(")");
+    }
+
+    @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() )
+                return TypeInteger.constant(i0.value()^i1.value());
+        }
+        return TypeInteger.BOT;
+    }
+
+    @Override
+    public Node idealize() {
+        Node lhs = in(1);
+        Node rhs = in(2);
+        Type t1 = lhs._type;
+        Type t2 = rhs._type;
+
+        // Xor of 0.  We do not check for (0^x) because this will already
+        // canonicalize to (x^0)
+        if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 )
+            return lhs;
+
+        // Move constants to RHS: con*arg becomes arg*con
+        if ( t1.isConstant() && !t2.isConstant() )
+            return swap12();
+
+        // 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,true);
+        if( phicon!=null ) return phicon;
+
+        return null;
+    }
+    @Override Node copy(Node lhs, Node rhs) { return new XorNode(lhs,rhs); }
+    @Override String err() {
+        if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '^' " + in(1)._type;
+        if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '^' " + in(2)._type;
+        return null;
+    }
+}