Add TypeInteger ranges

5 files changed, 85 insertions, 65 deletions

diff --git a/chapter14/src/main/java/com/seaofnodes/simple/Parser.java b/chapter14/src/main/java/com/seaofnodes/simple/Parser.java
index fee5215e..032b4867 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/Parser.java
@@ -65,6 +65,7 @@ public class Parser {
             add("struct");
             add("true");
             add("while");
+            add("u8");
         }};
 
 
@@ -85,6 +86,7 @@ public class Parser {
         IterPeeps.reset();
         TYPES.clear();
         TYPES.put("int",TypeInteger.BOT);
+        //TYPES.put("u8" ,TypeInteger.U8 );
         TYPES.put("flt",TypeFloat  .BOT);
         SCHEDULED = false;
         _lexer = new Lexer(source);
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 48350957..32059b0d 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -37,7 +37,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
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 48faefd2..238be00e 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/chapter14/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,29 +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();
+        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));
+            return new ConstantNode(doOp(ZERO,ZERO));
 
         // Equals pushes constant to the right; 5==X becomes X==5.
         if( this instanceof EQ ) {
@@ -64,7 +66,7 @@ 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));
         }
 
@@ -77,12 +79,42 @@ abstract public class BoolNode extends Node {
         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; } }
+    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; } }
 
 }
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter14/src/main/java/com/seaofnodes/simple/type/Type.java
index 1f211430..9c938ef8 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -67,6 +67,7 @@ public class Type {
     }
 
     // Is high or on the lattice centerline.
+    public boolean isHigh       () { return _type==TTOP || _type==TXCTRL; }
     public boolean isHighOrConst() { return _type==TTOP || _type==TXCTRL; }
 
     // Strict constant values, things on the lattice centerline.
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter14/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index 8c77672b..7aac62ec 100644
--- a/chapter14/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/chapter14/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -9,23 +9,25 @@ public class TypeInteger extends Type {
 
     public final static TypeInteger TOP = make(false, 0);
     public final static TypeInteger BOT = make(false, 1);
-    public final static TypeInteger ZERO= make(true , 0);
-
-    public final boolean _is_con;
+    public final static TypeInteger BOOL= make(0,1);
+    public final static TypeInteger ZERO= make(0,0);
+    public final static TypeInteger FALSE=ZERO;
+    public final static TypeInteger TRUE= make(1,1);
 
     /**
-     * The constant value or
-     * if not constant then 1=bottom, 0=top.
+     * Describes an integer *range* - everything from min to max; both min and
+     * max are inclusive.  If min==max, this is a constant.
+     *
+     * If min <= max, this is a  below center (towards bottom).
+     * If min >  max, this is an above center (towards top).
      */
-    public final long _con;
+    public final long _min, _max;
 
-    private TypeInteger(boolean is_con, long con) {
-        super(TINT);
-        _is_con = is_con;
-        _con = con;
-    }
+    private TypeInteger(long min, long max) { super(TINT); _min = min; _max = max; }
+    public static TypeInteger make(long lo, long hi) {  return new TypeInteger(lo,hi).intern();  }
     public static TypeInteger make(boolean is_con, long con) {
-        return new TypeInteger(is_con,con).intern();
+        return make(is_con ? con : (con==0 ? Integer.MAX_VALUE : Integer.MIN_VALUE),
+                    is_con ? con : (con==0 ? Integer.MIN_VALUE : Integer.MAX_VALUE));
     }
 
     public static TypeInteger constant(long con) { return make(true, con); }
@@ -38,13 +40,15 @@ public class TypeInteger extends Type {
     public StringBuilder print(StringBuilder sb) {
         if( this==TOP ) return sb.append("IntTop");
         if( this==BOT ) return sb.append("IntBot");
-        return sb.append(_con);
+        if( isConstant() ) return sb.append(_min);
+        return sb.append("[").append(_min).append("-").append(_max).append("]");
     }
 
     @Override public String str() {
         if( this==TOP ) return "~int";
         if( this==BOT ) return  "int";
-        return ""+_con;
+        if( isConstant() ) return ""+_min;
+        return "["+_min+"-"+_max+"]";
     }
 
     /**
@@ -57,45 +61,26 @@ public class TypeInteger extends Type {
         return sb.append("Int");
     }
 
-    @Override
-    public boolean isHighOrConst() { return _is_con || _con==0; }
-
-    @Override
-    public boolean isConstant() { return _is_con; }
+    @Override public boolean isHigh       () { return _min >  _max; }
+    @Override public boolean isHighOrConst() { return _min >= _max; }
+    @Override public boolean isConstant   () { return _min == _max; }
 
-    public long value() { return _con; }
+    public long value() { assert isConstant(); return _min; }
 
     @Override
     public Type xmeet(Type other) {
         // Invariant from caller: 'this' != 'other' and same class (TypeInteger)
         TypeInteger i = (TypeInteger)other; // Contract
-        // BOT wins
-        if ( this==BOT ) return this;
-        if ( i   ==BOT ) return i   ;
-        // TOP loses
-        if ( i   ==TOP ) return this;
-        if ( this==TOP ) return i   ;
-        // Since both are constants, and are never equals (contract) unequals
-        // constants fall to bottom
-        return BOT;
-    }
-
-    @Override
-    public Type dual() {
-        if( isConstant() ) return this; // Constants are a self-dual
-        return _con==0 ? BOT : TOP;
+        return make(Math.min(_min,i._min), Math.max(_max,i._max));
     }
 
-    @Override
-    public Type glb() { return BOT; }
-
+    @Override public TypeInteger dual() { return make(_max,_min); }
+    @Override public Type glb() { return BOT; }
     @Override public TypeInteger makeInit() { return ZERO; }
-
-    @Override
-    int hash() { return (int)(_con ^ (_is_con ? 0 : 0x4000)); }
+    @Override int hash() { return (int)((_min ^ (_min>>32)) *(_max ^ (_max>>32))); }
     @Override
     public boolean eq( Type t ) {
         TypeInteger i = (TypeInteger)t; // Contract
-        return _con==i._con && _is_con==i._is_con;
+        return _min==i._min && _max==i._max;
     }
 }