diff options
Diffstat (limited to 'chapter14/src/main/java')
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; } } |