From 6653a056b0d82568c40ca6e31b9fcc9ce3a8e9ee Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 6 Aug 2024 13:09:38 +0100 Subject: Chapter 14: Numeric Types MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Thalia Archibald Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Dibyendu Majumdar Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher Co-authored-by: Jun Kawasaki --- src/main/java/com/seaofnodes/simple/Parser.java | 154 ++++++++-- .../java/com/seaofnodes/simple/node/AddFNode.java | 37 +++ .../java/com/seaofnodes/simple/node/AddNode.java | 25 +- .../java/com/seaofnodes/simple/node/AndNode.java | 59 ++++ .../java/com/seaofnodes/simple/node/BoolNode.java | 96 +++++-- .../java/com/seaofnodes/simple/node/DivFNode.java | 39 +++ .../java/com/seaofnodes/simple/node/DivNode.java | 16 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 4 + .../java/com/seaofnodes/simple/node/MemOpNode.java | 2 +- .../com/seaofnodes/simple/node/MinusFNode.java | 30 ++ .../java/com/seaofnodes/simple/node/MinusNode.java | 11 +- .../java/com/seaofnodes/simple/node/MulFNode.java | 44 +++ .../java/com/seaofnodes/simple/node/MulNode.java | 14 +- src/main/java/com/seaofnodes/simple/node/Node.java | 28 +- .../java/com/seaofnodes/simple/node/NotNode.java | 6 +- .../java/com/seaofnodes/simple/node/OrNode.java | 56 ++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 2 +- .../com/seaofnodes/simple/node/RoundF32Node.java | 34 +++ .../java/com/seaofnodes/simple/node/SarNode.java | 49 ++++ .../java/com/seaofnodes/simple/node/ShlNode.java | 46 +++ .../java/com/seaofnodes/simple/node/ShrNode.java | 49 ++++ .../java/com/seaofnodes/simple/node/SubFNode.java | 37 +++ .../java/com/seaofnodes/simple/node/SubNode.java | 16 +- .../com/seaofnodes/simple/node/ToFloatNode.java | 25 ++ .../com/seaofnodes/simple/node/ToIntegerNode.java | 23 ++ .../java/com/seaofnodes/simple/node/XorNode.java | 56 ++++ .../simple/print/SimpleGraphAdapter.java | 2 +- .../simple/print/SimpleGraphObserver.java | 2 +- src/main/java/com/seaofnodes/simple/type/Type.java | 31 +- .../java/com/seaofnodes/simple/type/TypeFloat.java | 114 ++++++++ .../com/seaofnodes/simple/type/TypeInteger.java | 110 +++---- .../com/seaofnodes/simple/type/TypeMemPtr.java | 2 + .../com/seaofnodes/simple/type/TypeStruct.java | 2 +- .../java/com/seaofnodes/simple/Chapter06Test.java | 6 +- .../java/com/seaofnodes/simple/Chapter07Test.java | 1 - .../java/com/seaofnodes/simple/Chapter12Test.java | 44 ++- .../java/com/seaofnodes/simple/Chapter13Test.java | 2 +- .../com/seaofnodes/simple/Chapter14FloatTest.java | 114 ++++++++ .../java/com/seaofnodes/simple/Chapter14Test.java | 319 +++++++++++++++++++++ .../com/seaofnodes/simple/evaluator/Evaluator.java | 32 ++- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 59 +++- 41 files changed, 1614 insertions(+), 184 deletions(-) create mode 100644 src/main/java/com/seaofnodes/simple/node/AddFNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/AndNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/DivFNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MinusFNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MulFNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/OrNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/RoundF32Node.java create mode 100644 src/main/java/com/seaofnodes/simple/node/SarNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/ShlNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/ShrNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/SubFNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/ToFloatNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/XorNode.java create mode 100644 src/main/java/com/seaofnodes/simple/type/TypeFloat.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter14Test.java (limited to 'src') diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 3c8d8f40..0602d290 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -64,10 +64,19 @@ public class Parser { * List of keywords disallowed as identifiers */ private static final HashSet KEYWORDS = new HashSet<>(){{ + add("bool"); add("break"); + add("byte"); add("continue"); add("else"); + add("f32"); + add("f64"); add("false"); + add("flt"); + add("i16"); + add("i32"); + add("i64"); + add("i8"); add("if"); add("int"); add("new"); @@ -75,6 +84,10 @@ public class Parser { add("return"); add("struct"); add("true"); + add("u1"); + add("u16"); + add("u32"); + add("u8"); add("while"); }}; @@ -96,7 +109,20 @@ public class Parser { Node.reset(); IterPeeps.reset(); TYPES.clear(); - TYPES.put("int",TypeInteger.BOT); + TYPES.put("bool",TypeInteger.U1 ); + TYPES.put("byte",TypeInteger.U8 ); + TYPES.put("f32" ,TypeFloat .B32); + TYPES.put("f64" ,TypeFloat .BOT); + TYPES.put("flt" ,TypeFloat .BOT); + TYPES.put("i16" ,TypeInteger.I16); + TYPES.put("i32" ,TypeInteger.I32); + TYPES.put("i64" ,TypeInteger.BOT); + TYPES.put("i8" ,TypeInteger.I8 ); + TYPES.put("int" ,TypeInteger.BOT); + TYPES.put("u1" ,TypeInteger.U1 ); + TYPES.put("u16" ,TypeInteger.U16); + TYPES.put("u32" ,TypeInteger.U32); + TYPES.put("u8" ,TypeInteger.U8 ); SCHEDULED = false; _lexer = new Lexer(source); _scope = new ScopeNode(); @@ -200,7 +226,7 @@ public class Parser { * Only allowed in top level scope. * Structs cannot be redefined. * - * @return null + * @return The statement following the struct */ private Node parseStruct() { if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope"); @@ -220,7 +246,7 @@ public class Parser { TYPES.put(typeName, ts); // Insert the struct name in the collection of all struct names _aliases.put(typeName,_alias); _alias += ts._fields.length; - return null; + return parseStatement(); } /** @@ -435,6 +461,11 @@ public class Parser { throw error("Undefined name '" + name + "'"); t = _scope.lookupDeclaredType(name); } + // Auto-widen int to float + if( expr._type instanceof TypeInteger && t instanceof TypeFloat ) + expr = new ToFloatNode(expr).peephole(); + // Auto-narrow wide ints to narrow ints + expr = zsMask(expr,t); // Auto-deepen forward ref types Type e = expr._type; if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null ) @@ -476,7 +507,29 @@ public class Parser { * * @return an expression {@link Node}, never {@code null} */ - private Node parseExpression() { return parseComparison(); } + private Node parseExpression() { return parseBitwise(); } + + /** + * Parse an bitwise expression + * + * 
+     *     bitwise : compareExpr (('&' | '|' | '^') compareExpr)*
+     *
+ * @return a bitwise expression {@link Node}, never {@code null} + */ + private Node parseBitwise() { + Node lhs = parseComparison(); + while( true ) { + if( false ) ; + else if( match("&") ) lhs = new AndNode(lhs,null); + else if( match("|") ) lhs = new OrNode(lhs,null); + else if( match("^") ) lhs = new XorNode(lhs,null); + else break; + lhs.setDef(2,parseComparison()); + lhs = lhs.peephole(); + } + return lhs; + } /** * Parse an expression of the form: @@ -487,7 +540,7 @@ public class Parser { * @return an comparator expression {@link Node}, never {@code null} */ private Node parseComparison() { - var lhs = parseAddition(); + var lhs = parseShift(); while( true ) { int idx=0; boolean negate=false; // Test for any local nodes made, and "keep" lhs during peepholes @@ -500,14 +553,36 @@ public class Parser { else if( match(">" ) ) { idx=1; lhs = new BoolNode.LT(null, lhs); } else break; // Peepholes can fire, but lhs is already "hooked", kept alive - lhs.setDef(idx,parseAddition()); - lhs = lhs.peephole(); + lhs.setDef(idx,parseShift()); + lhs = lhs.widen().peephole(); if( negate ) // Extra negate for != lhs = new NotNode(lhs).peephole(); } return lhs; } + /** + * Parse an additive expression + * + * 
+     *     shiftExpr : additiveExpr (('<<' | '>>' | '>>>') additiveExpr)*
+     *
+ * @return a shift expression {@link Node}, never {@code null} + */ + private Node parseShift() { + Node lhs = parseAddition(); + while( true ) { + if( false ) ; + else if( match("<<") ) lhs = new ShlNode(lhs,null); + else if( match(">>>")) lhs = new ShrNode(lhs,null); + else if( match(">>") ) lhs = new SarNode(lhs,null); + else break; + lhs.setDef(2,parseAddition()); + lhs = lhs.widen().peephole(); + } + return lhs; + } + /** * Parse an additive expression * @@ -524,7 +599,7 @@ public class Parser { else if( match("-") ) lhs = new SubNode(lhs,null); else break; lhs.setDef(2,parseMultiplication()); - lhs = lhs.peephole(); + lhs = lhs.widen().peephole(); } return lhs; } @@ -545,7 +620,7 @@ public class Parser { else if( match("/") ) lhs = new DivNode(lhs,null); else break; lhs.setDef(2,parseUnary()); - lhs = lhs.peephole(); + lhs = lhs.widen().peephole(); } return lhs; } @@ -559,7 +634,7 @@ public class Parser { * @return a unary expression {@link Node}, never {@code null} */ private Node parseUnary() { - if (match("-")) return new MinusNode(parseUnary()).peephole(); + if (match("-")) return new MinusNode(parseUnary()).widen().peephole(); if (match("!")) return new NotNode(parseUnary()).peephole(); return parsePostfix(parsePrimary()); } @@ -644,6 +719,8 @@ public class Parser { else { Node val = parseExpression(); Type glb = base._fields[idx]._type; + // Auto-truncate when storing to narrow fields + val = zsMask(val,glb); store(name,alias,glb,expr,val,false); return expr; // "obj.a = expr" returns the expression while updating memory } @@ -653,11 +730,34 @@ public class Parser { return parsePostfix(new LoadNode(name, alias, declaredType.glb(), mem(), expr).peephole()); } + // zero/sign extend. "i" is limited to either classic unsigned (min==0) or + // classic signed (min=minus-power-of-2); max=power-of-2-minus-1. + private Node zsMask(Node val, Type t ) { + if( val._type instanceof TypeFloat && t instanceof TypeInteger ) + val = new ToIntegerNode(val).peephole(); + if( !(val._type instanceof TypeInteger tval && t instanceof TypeInteger t0 && !tval.isa(t0)) ) { + if( !(val._type instanceof TypeFloat tval && t instanceof TypeFloat t0 && !tval.isa(t0)) ) + return val; + // Float rounding + return new RoundF32Node(val).peephole(); + } + if( t0._min==0 ) // Unsigned + return new AndNode(val,new ConstantNode(TypeInteger.constant(t0._max)).peephole()).peephole(); + // Signed extension + int shift = Long.numberOfLeadingZeros(t0._max)-1; + Node shf = new ConstantNode(TypeInteger.constant(shift)).peephole(); + if( shf._type==TypeInteger.ZERO ) + return val; + return new SarNode(new ShlNode(val,shf.keep()).peephole(),shf.unkeep()).peephole(); + } + + /** * Parse integer literal * * 
      *     integerLiteral: [1-9][0-9]* | [0]
+     *     floatLiteral: [digits].[digits]?[e [digits]]?
      *
*/ private ConstantNode parseLiteral() { @@ -815,19 +915,37 @@ public class Parser { return String.valueOf(peek()); } - boolean isNumber() {return isNumber(peek());} + boolean isNumber(char ch) {return Character.isDigit(ch);} + // Return a constant Type, either TypeInteger or TypeFloat private Type parseNumber() { - String snum = parseNumberString(); - if (snum.length() > 1 && snum.charAt(0) == '0') - throw error("Syntax error: integer values cannot start with '0'"); - return TypeInteger.constant(Long.parseLong(snum)); + int old = _position; + int len = isLongOrDouble(); + if( len > 0 ) { + if( len > 1 && _input[old]=='0' ) + throw error("Syntax error: integer values cannot start with '0'"); + return TypeInteger.constant(Long.parseLong(new String(_input,old,len))); + } + return TypeFloat.constant(Double.parseDouble(new String(_input,old,-len))); } private String parseNumberString() { - int start = _position; - while (isNumber(nextChar())) ; - return new String(_input, start, --_position - start); + int old = _position; + int len = Math.abs(isLongOrDouble()); + _position += len; + return new String(_input,old,len); + } + + // Return +len that ends a long + // Return -len that ends a double + private int isLongOrDouble() { + int old = _position; + char c; + while( Character.isDigit(c=nextChar()) ) ; + if( !(c=='e' || c=='.') ) + return --_position - old; + while( Character.isDigit(c=nextChar()) || c=='e' || c=='.' ) ; + return -(--_position - old); } // First letter of an identifier diff --git a/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/src/main/java/com/seaofnodes/simple/node/AddFNode.java new file mode 100644 index 00000000..fd713156 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -0,0 +1,37 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + + +public class AddFNode extends Node { + public AddFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "AddF"; } + + @Override protected String format() { return "(%1+%2)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()+i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Type t2 = in(2)._type; + + // Add of 0. + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) + return lhs; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new AddFNode(lhs,rhs); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index eb7e2793..0046bd03 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -15,17 +15,23 @@ public class AddNode extends Node { @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; - if( t1==Type.TOP || t1==TypeInteger.TOP || - t2==Type.TOP || t2==TypeInteger.TOP ) - return TypeInteger.TOP; - if( t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger i1 ) { - if (i0.isConstant() && i1.isConstant()) - return TypeInteger.constant(i0.value()+i1.value()); + 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 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); @@ -34,7 +40,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 && lhs._type instanceof TypeInteger ) return lhs; // Add of same to a multiply by 2 @@ -97,7 +103,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) { @@ -169,6 +175,7 @@ public class AddNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } + @Override Node copyF() { return new AddFNode(null,null); } @Override public String err() { if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; 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..e2729e60 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -0,0 +1,59 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + + +public class AndNode extends Node { + public AndNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "And"; } + + @Override protected String format() { return "(%1&%2)"; } + + @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 && lhs._type instanceof TypeInteger ) + 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 63452dba..8a25e8d9 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -2,10 +2,14 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.type.TypeMemPtr; +import static com.seaofnodes.simple.type.TypeInteger.*; abstract public class BoolNode extends Node { @@ -23,52 +27,84 @@ abstract public class BoolNode extends Node { } @Override - public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1==Type.TOP || t1==TypeInteger.TOP || - t2==Type.TOP || t2==TypeInteger.TOP ) - return TypeInteger.TOP; - if( t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger 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; } - abstract boolean doOp(long lhs, long rhs); + TypeInteger doOp(TypeInteger t1, TypeInteger t2) { throw Utils.TODO(); } + boolean doOp(double lhs, double rhs) { throw Utils.TODO(); } @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) ) { // con==noncon becomes noncon==con - if( in(1) instanceof ConstantNode ) - return new EQ(in(2),in(1)); + if( in(1) instanceof ConstantNode || in(1)._nid > in(2)._nid ) // Equals sorts by NID otherwise: non.high == non.low becomes non.low == non.high - else if( in(1)._nid > in(2)._nid ) - return new EQ(in(2),in(1)); + 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 ((phi cons) cmp con) ? - // Do we have ((phi cons) cmp (phi cons)) ? - // Push the compare up through the phi: (phi con0 cmp con, con1 cmp con...) - 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); } } - 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); } } - 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); } } + 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 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/DivFNode.java b/src/main/java/com/seaofnodes/simple/node/DivFNode.java new file mode 100644 index 00000000..a3f4318d --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + + +public class DivFNode extends Node { + public DivFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "DivF"; } + + @Override protected String format() { return "(%1/%2)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()/i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Div of 1. + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==1 ) + return lhs; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new DivFNode(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 d7244ace..e725ace4 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -15,15 +15,14 @@ public class DivNode extends Node { @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; - if( t1==Type.TOP || t1==TypeInteger.TOP || - t2==Type.TOP || t2==TypeInteger.TOP ) + if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP; - if (t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger i1) { - if (i0.isConstant() && i1.isConstant()) - return i1.value() == 0 + 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 TypeInteger.BOT; } @@ -31,10 +30,11 @@ public class DivNode extends Node { @Override public Node idealize() { // Div of 1. - if( in(2)._type.isConstant() && in(2)._type instanceof TypeInteger i && i.value()==1 ) + if( in(2)._type.isConstant() && in(2)._type instanceof TypeInteger i && i.value()==1 && in(1)._type instanceof TypeInteger ) return in(1); return null; } @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); } + @Override Node copyF() { return new DivFNode(null,null); } } diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 277644f5..3191061c 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -96,4 +96,8 @@ public class LoadNode extends MemOpNode { Node px = phi.in(idx); return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr() && _alias==st1._alias; } + + 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 7c6afb0c..29d302cb 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/MinusFNode.java b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java new file mode 100644 index 00000000..1b45c7c5 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + + +public class MinusFNode extends Node { + public MinusFNode(Node in) { super(null, in); } + + @Override public String label() { return "MinusF"; } + + @Override protected String format() { return "(-%1)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0) + return i0.isConstant() ? TypeFloat.constant(-i0.value()) : i0; + return TypeFloat.BOT; + } + + @Override + public Node idealize() { + // -(-x) is x + if( in(1) instanceof MinusFNode minus ) + return minus.in(1); + + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 5b65b3fb..f56c423e 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -14,9 +14,13 @@ public class MinusNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeInteger i0) - return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; - return in(1)._type==Type.TOP ? TypeInteger.TOP : TypeInteger.BOT; + 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 in(1)._type.isHigh() ? TypeInteger.TOP : TypeInteger.BOT; } @Override @@ -27,4 +31,5 @@ public class MinusNode extends Node { return null; } + @Override Node copyF() { return new MinusFNode(null); } } diff --git a/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/src/main/java/com/seaofnodes/simple/node/MulFNode.java new file mode 100644 index 00000000..6a57f3c5 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -0,0 +1,44 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + + +public class MulFNode extends Node { + public MulFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "MulF"; } + + @Override protected String format() { return "(%1*%2)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()*i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Mul of 1. We do not check for (1*x) because this will already + // canonicalize to (x*1) + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==1 ) + return lhs; + + // Move constants to RHS: con*arg becomes arg*con + if ( t1.isConstant() && !t2.isConstant() ) + return swap12(); + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new MulFNode(lhs,rhs); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index b0359a52..c16edb4b 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -15,13 +15,12 @@ public class MulNode extends Node { @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; - if( t1==Type.TOP || t1==TypeInteger.TOP || - t2==Type.TOP || t2==TypeInteger.TOP ) + if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP; - if (t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger i1) { - if (i0.isConstant() && i1.isConstant()) - return TypeInteger.constant(i0.value()*i1.value()); + if( t1 instanceof TypeInteger i1 && + t2 instanceof TypeInteger i2 ) { + if (i1.isConstant() && i2.isConstant()) + return TypeInteger.constant(i1.value()*i2.value()); } return TypeInteger.BOT; } @@ -35,7 +34,7 @@ public class MulNode extends Node { // Mul 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 ) + if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==1 && lhs._type instanceof TypeInteger ) return lhs; // Move constants to RHS: con*arg becomes arg*con @@ -51,6 +50,7 @@ public class MulNode extends Node { return null; } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } + @Override Node copyF() { return new MulFNode(null,null); } @Override public String err() { if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 2c8596fa..4ee82187 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -8,6 +8,7 @@ import com.seaofnodes.simple.IRPrinter; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; import java.util.*; import java.util.function.Function; @@ -496,6 +497,26 @@ public abstract class Node extends BaseNode implements OutNode, Cloneable /** Return block start from a isCFG() */ public Node getBlockStart() { return null; } + // Semantic change to the graph (so NOT a peephole), used by the Parser. + // If any input is a float, flip to a float-flavored opcode and widen any + // non-float input. + public final Node widen() { + if( !hasFloatInput() ) return this; + Node flt = copyF(); + if( flt==null ) return this; + for( int i=1; i implements OutNode, Cloneable 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 5e556390..2e89f013 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -14,9 +14,11 @@ 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) : TypeInteger.BOT; case TypeMemPtr p0: // top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot // If input in null then true 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..67585423 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -0,0 +1,56 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + + +public class OrNode extends Node { + public OrNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Or"; } + + @Override protected String format() { return "(%1|%2)"; } + + @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 && lhs._type instanceof TypeInteger ) + 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 8dfa04cf..309cd8b5 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -12,7 +12,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; } 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..6be071a2 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java @@ -0,0 +1,34 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + + +public class RoundF32Node extends Node { + public RoundF32Node(Node lhs) { super(null, lhs); } + + @Override public String label() { return "RoundF32"; } + + @Override protected String format() { return "((f32)%1)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && i0.isConstant() ) + return TypeFloat.constant((float)i0.value()); + if( in(1)._type==TypeFloat.BOT ) return TypeFloat.B32; + 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..6ab7141f --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -0,0 +1,49 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + + +public class SarNode extends Node { + public SarNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Sar"; } + + @Override protected String format() { return "(%1>>%2)"; } + + @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 && lhs._type instanceof TypeInteger ) + 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..999fc7da --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -0,0 +1,46 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + + +public class ShlNode extends Node { + public ShlNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Shl"; } + + @Override protected String format() { return "(%1<<%2)"; } + + @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()< 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..b89f5191 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -0,0 +1,49 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + + +public class ShrNode extends Node { + public ShrNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Shr"; } + + @Override protected String format() { return "(%1>>>%2)"; } + + @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 && lhs._type instanceof TypeInteger ) + 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/SubFNode.java b/src/main/java/com/seaofnodes/simple/node/SubFNode.java new file mode 100644 index 00000000..2d218a03 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -0,0 +1,37 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + + +public class SubFNode extends Node { + public SubFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "SubF"; } + + @Override protected String format() { return "(%1-%2)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()-i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Type t2 = in(2)._type; + + // Sub of 0. + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) + return lhs; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new SubFNode(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 1589abe7..d5e54e73 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -15,18 +15,17 @@ public class SubNode extends Node { @Override public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1==Type.TOP || t1==TypeInteger.TOP || - t2==Type.TOP || t2==TypeInteger.TOP ) - return TypeInteger.TOP; // Sub of same is 0 if( in(1)==in(2) ) return TypeInteger.ZERO; - if (t1 instanceof TypeInteger i0 && - t2 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 TypeInteger.BOT; @@ -57,4 +56,5 @@ public class SubNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new SubNode(lhs,rhs); } + @Override Node copyF() { return new SubFNode(null,null); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java new file mode 100644 index 00000000..26cf50e1 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -0,0 +1,25 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import com.seaofnodes.simple.type.TypeInteger; + + +public class ToFloatNode extends Node { + public ToFloatNode(Node lhs) { super(null, lhs); } + + @Override public String label() { return "ToFloat"; } + + @Override protected String format() { return "(flt)%1"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && i0.isConstant() ) + return TypeFloat.constant(i0.value()); + return TypeFloat.BOT; + } + + @Override public Node idealize() { return null; } + @Override Node copy(Node lhs, Node rhs) { return new ToFloatNode(lhs); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java b/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java new file mode 100644 index 00000000..df740202 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java @@ -0,0 +1,23 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import com.seaofnodes.simple.type.TypeInteger; + +// Truncate toward zero, saturating overflow; NaN converts to zero. +public class ToIntegerNode extends Node { + public ToIntegerNode(Node lhs) { super(null,lhs); } + @Override public String label() { return "ToInteger"; } + @Override protected String format() { return "(int)%1"; } + + @Override public Type compute() { + Type t = in(1)._type; + if( t.isHigh() ) return TypeInteger.TOP; + if( t instanceof TypeFloat tf && tf.isConstant() ) + return TypeInteger.constant((long)tf.value()); + return TypeInteger.BOT; + } + + @Override public Node idealize() { return null; } + @Override Node copy(Node lhs, Node rhs) { return new ToIntegerNode(lhs); } +} 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..720fb8e4 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -0,0 +1,56 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + + +public class XorNode extends Node { + public XorNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Xor"; } + + @Override protected String format() { return "(%1^%2)"; } + + @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 && lhs._type instanceof TypeInteger ) + 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; + } +} diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index e65963db..26897a7c 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.type.TypeMem; -/** Chapter 12's view of the IR; browser, transport and layout are shared. */ +/** Chapter 14's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter { @Override protected String[] edgeNames(Node n) { diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index 3aabd79f..202aa9d9 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 13's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 14's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 93e27c76..49dc090a 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -33,11 +33,12 @@ public class Type { static final byte TXCTRL = 3; // Ctrl flow top (mini-lattice: any-xctrl-ctrl-all) static final byte TSIMPLE = 4; // End of the Simple Types static final byte TINT = 5; // All Integers; see TypeInteger - static final byte TTUPLE = 6; // Tuples; finite collections of unrelated Types, kept in parallel - static final byte TMEM = 7; // All memory (alias 0) or A slice of memory - with specific alias - static final byte TMEMPTR = 8; // Memory pointer type - static final byte TSTRUCT = 9; // Structs; tuples with named fields - static final byte TFLD =10; // Fields into struct + static final byte TFLT = 6; // All Integers; see TypeInteger + static final byte TTUPLE = 7; // Tuples; finite collections of unrelated Types, kept in parallel + static final byte TMEM = 8; // All memory (alias 0) or A slice of memory - with specific alias + static final byte TMEMPTR = 9; // Memory pointer type + static final byte TSTRUCT =10; // Structs; tuples with named fields + static final byte TFLD =11; // Fields into struct public final byte _type; @@ -55,6 +56,7 @@ public class Type { ts.add(CONTROL); Field.gather(ts); TypeInteger.gather(ts); + TypeFloat.gather(ts); TypeMem.gather(ts); TypeMemPtr.gather(ts); TypeStruct.gather(ts); @@ -66,6 +68,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. @@ -81,14 +84,16 @@ public class Type { // ---------------------------------------------------------- - // Notes on Type interning. - // At the moment it is not easy to reset the interned types - // because we hold static references to several types and these are scattered - // around. This means the INTERN cache will retain all types from - // every run of the Parser. For this to work correctly types must be - // rigorous about defining when they are the same. Also types need to be - // immutable once defined. - // The rationale for interning is performance. + // Notes on Type interning: At the moment it is not easy to reset the + // interned types because we hold static references to several types and + // these are scattered around. This means the INTERN cache will retain all + // types from every run of the Parser. For this to work correctly types + // must be rigorous about defining when they are the same. Also types need + // to be immutable once defined. The rationale for interning is + // *correctness* with cyclic type definitions. Simple structural recursive + // checks go exponential with merely sharing, but with cycles they will + // stack overflow and crash. Intering means we do not need to have sharing + // checks with every type compare, only during interning. // Factory method which interns "this" public T intern() { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java new file mode 100644 index 00000000..975c1a9e --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -0,0 +1,114 @@ +package com.seaofnodes.simple.type; + +import java.util.ArrayList; + +/** + * Float Type + */ +public class TypeFloat extends Type { + + public final static TypeFloat TOP = make((byte)-64, 0); + public final static TypeFloat T32 = make((byte)-32, 0); + public final static TypeFloat ZERO= make((byte) 0, 0); + public final static TypeFloat B32 = make((byte) 32, 0); + public final static TypeFloat BOT = make((byte) 64, 0); + + /** +/-64 for double; +/-32 for float, or 0 for constants */ + public final byte _sz; + + /** + * The constant value or 0 + */ + public final double _con; + + private TypeFloat(byte sz, double con) { + super(TFLT); + _sz = sz ; + _con = con; + } + private static TypeFloat make(byte sz, double con) { + return new TypeFloat(sz,con).intern(); + } + + public static TypeFloat constant(double con) { return make((byte)0, con); } + + public static void gather(ArrayList ts) { ts.add(ZERO); ts.add(BOT); ts.add(B32); ts.add(constant(3.141592653589793)); } + + // FIXME this display format is problematic + // In visualizer '#' gets prepended if its a constant + @Override + public StringBuilder print(StringBuilder sb) { + if( this==TOP ) return sb.append("FltTop"); + if( this==T32 ) return sb.append("F32Top"); + if( this==B32 ) return sb.append("F32Bot"); + if( this==BOT ) return sb.append("FltBot"); + return sb.append(_con); + } + + @Override public String str() { + if( this==TOP ) return "~flt"; + if( this==T32 ) return "~f32"; + if( this==B32 ) return "f32"; + if( this==BOT ) return "flt"; + return ""+_con+(isF32() ? "f" : ""); + } + + /** + * Display Type name in a format that's good for IR printer + */ + @Override + public StringBuilder typeName(StringBuilder sb) { + if( this==TOP ) return sb.append("FltTop"); + if( this==T32 ) return sb.append("F32Top"); + if( this==B32 ) return sb.append("F32Bot"); + if( this==BOT ) return sb.append("FltBot"); + return sb.append(isF32() ? "F32" : "Flt"); + } + + boolean isF32() { return ((float)_con)==_con; } + @Override public boolean isHigh() { return _sz< 0; } + @Override public boolean isHighOrConst() { return _sz<=0; } + @Override public boolean isConstant() { return _sz==0; } + + public double value() { return _con; } + + @Override + public Type xmeet(Type other) { + // Invariant from caller: 'this' != 'other' and same class (TypeFloat) + TypeFloat i = (TypeFloat)other; // Contract + // Larger size in i1, smaller in i0 + TypeFloat i0 = _sz < i._sz ? this : i; + TypeFloat i1 = _sz < i._sz ? i : this; + + if( i1._sz== 64 ) return BOT; + if( i0._sz==-64 ) return i1; + if( i1._sz== 32 ) + return i0._sz==0 && !i0.isF32() ? BOT : B32; + if( i1._sz!= 0 ) return i1; + // i1 is a constant + if( i0._sz==-32 ) + return i1.isF32() ? i1 : BOT; + // Since both are constants, and are never equals (contract) unequals + // constants fall to bottom + return i0.isF32() && i1.isF32() ? B32 : BOT; + } + + @Override + public Type dual() { + if( _sz==0 ) return this; // Constants are a self-dual + return make((byte)-_sz,0); + } + + @Override + public Type glb() { return BOT; } + + @Override public TypeFloat makeInit() { return ZERO; } + + @Override + int hash() { return (int)(Double.hashCode(_con) ^ _sz); } + @Override + public boolean eq( Type t ) { + TypeFloat i = (TypeFloat)t; // Contract + return _con==i._con && _sz==i._sz; + } +} diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 8c77672b..aca3e06b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -9,42 +9,56 @@ 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 ZERO= make(0,0); + public final static TypeInteger U1 = make(0,1); + public final static TypeInteger BOOL= U1; + public final static TypeInteger FALSE=ZERO; + public final static TypeInteger TRUE= make(1,1); + public final static TypeInteger I8 = make(-128,127); + public final static TypeInteger I16 = make(-32768,32767); + public final static TypeInteger I32 = make(-1L<<31,(1L<<31)-1); + + public final static TypeInteger U8 = make(0,255); + public final static TypeInteger U16 = make(0,65535); + public final static TypeInteger U32 = make(0,(1L<<32)-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 ? Long.MAX_VALUE : Long.MIN_VALUE), + is_con ? con : (con==0 ? Long.MIN_VALUE : Long.MAX_VALUE)); } public static TypeInteger constant(long con) { return make(true, con); } - public static void gather(ArrayList ts) { ts.add(ZERO); ts.add(BOT); } + public static void gather(ArrayList ts) { ts.add(ZERO); ts.add(BOT); ts.add(U1); ts.add(U8); } // FIXME this display format is problematic // In visualizer '#' gets prepended if its a constant @Override - public StringBuilder print(StringBuilder sb) { - if( this==TOP ) return sb.append("IntTop"); - if( this==BOT ) return sb.append("IntBot"); - return sb.append(_con); - } + public StringBuilder print(StringBuilder sb) { return sb.append(str()); } @Override public String str() { if( this==TOP ) return "~int"; if( this==BOT ) return "int"; - return ""+_con; + if( this==BOOL) return ("bool"); + if( this==I8 ) return ("i8"); + if( this==I16 ) return ("i16"); + if( this==I32 ) return ("i32"); + if( this==U8 ) return ("u8"); + if( this==U16 ) return ("u16"); + if( this==U32 ) return ("u32"); + if( isConstant() ) return ""+_min; + return "["+_min+"-"+_max+"]"; } /** @@ -57,45 +71,45 @@ 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; } - - public long value() { return _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() { assert isConstant(); return _min; } + + // AND-mask of forced zeros. e.g. unsigned types will return their mask; + // u8 will return 0xFF. But also a range of 16-18 (0x10-0x12) will return + // 0x13 - no value in the range {16,17,18} will allow bit 0x04 to be set. + public long mask() { + if( isHigh() ) return 0; + if( isConstant() ) return _min; + //if( _min<0 ) return -1L; + //if( _max==Long.MAX_VALUE ) return -1L; + // Those bit positions which differ min to max + long x = _min ^ _max; + // Highest '1' bit in the differ set. Since the range is from min to + // max, all values below here are possible. + long ff1 = Long.highestOneBit(x); + // Make a all-1's mask from ff1, and set over the same bits (either min + // or max is ok). + long mask = _min | (ff1-1) | ff1; + return mask; + } @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; } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 5caa816d..e6e40fe2 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -55,6 +55,8 @@ public class TypeMemPtr extends Type { public Type glb() { return make(_obj.glb(),true); } @Override public TypeMemPtr makeInit() { return NULLPTR; } + @Override public boolean isHigh() { return this==TOP; } + @Override int hash() { return _obj.hashCode() ^ (_nil ? 1024 : 0); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 02de7cc8..8ad59a39 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -38,7 +38,7 @@ public class TypeStruct extends Type { private static final TypeStruct S1F = make("S1"); private static final TypeStruct S2F = make("S2"); public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT), Field.make("s2",TypeMemPtr.make(S2F,false)) }); - private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeInteger.BOT), Field.make("s1",TypeMemPtr.make(S1F,false)) }); + private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeFloat .BOT), Field.make("s1",TypeMemPtr.make(S1F,false)) }); public static void gather(ArrayList ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); } public int find(String fname) { diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 43e46a5d..c5664c9d 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -27,10 +27,10 @@ return 1; int a = 1; if (arg) a = 2; -return (arg < a) < 3; +return (arg < a) < 3; // Because (arg < a) is a bool/uint1/[0-1], its always less than 3 """); StopNode stop = parser.parse().iterate(); - assertEquals("return ((arg 2 ) c = 1; +return c; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 99;", stop.toString()); + assertEquals(99L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testU8() { + Parser parser = new Parser( +""" +u8 b = 123; +b = b + 456;// Truncate +return b; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 67;", stop.toString()); + assertEquals(67L, Evaluator.evaluate(stop, 0)); + } + + + @Test + public void testU8While() { + Parser parser = new Parser( +""" +u8 b = 123; +while( b ) b = b + 456;// Truncate +return b; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop10,123,((Phi_b+456)&255));", stop.toString()); + } + + @Test + public void testU1() { + Parser parser = new Parser( +""" +bool b = 123; +b = b + 456;// Truncate +u1 c = b; // No more truncate needed +return c; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 1;", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testAnd() { + Parser parser = new Parser( +""" +int b = 123; +b = b+456 & 31; // Precedence +return b; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3;", stop.toString()); + assertEquals(3L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testRefLoad() { + Parser parser = new Parser( +""" +struct Foo { u1 b; } +Foo f = new Foo; +f.b = 123; +return f.b; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 1;", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testSigned() { + Parser parser = new Parser( +""" +i8 b = 255; // Chopped +return b; // Sign extend +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return -1;", stop.toString()); + assertEquals(-1L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testI8() { + Parser parser = new Parser( +""" +i8 b = arg; +b = b + 1;// Truncate +return b; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return (((((arg<<56)>>56)+1)<<56)>>56);", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testMask() { + Parser parser = new Parser( +""" +u16 mask = (1<<16)-1; // AND mask +int c = 123456789 & mask; +return c; // +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 52501;", stop.toString()); + assertEquals(52501L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testWrapMinus() { + Parser parser = new Parser( +""" +int MAX = 9223372036854775807; //0x7FFFFFFFFFFFFFFF; +int i = (arg&MAX) + -MAX + -1; // Basically (e0) + Long.MIN_VALUE +int j = -i; // Negating Long.MIN_VALUE wraps, cannot constant fold +if (arg) j = 1; +return j; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region29,1,(-((arg&9223372036854775807)+-9223372036854775808)));", stop.toString()); + assertEquals(-9223372036854775808L, Evaluator.evaluate(stop, 0)); + assertEquals(1L, Evaluator.evaluate(stop, 1)); + } + + @Test + public void testWrapShr() { + Parser parser = new Parser( +""" +return (arg >>> 1)==0; +"""); + StopNode stop = parser.parse().iterate(); + 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( +""" +return (arg | 123 ^ 456) >>> 1; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return (((arg|123)^456)>>>1);", stop.toString()); + assertEquals(217L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testMaskFloat() { + Parser parser = new Parser( +""" +flt f = arg; +arg = f & 0; +return arg; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot '&' FltBot",e.getMessage()); } + } + + @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().iterate(); + assertEquals("return Phi(Region34,.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().iterate(); + assertEquals("return ((arg>>Phi(Region33,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().iterate(); + assertEquals("return Phi(Region35,(arg==1),((flt)arg==Phi(Region24,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().iterate(); + assertEquals("return (arg==Phi(Region19,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().iterate(); + assertEquals("return (Phi(Region44,((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( +""" +i8 xi8 = 123456789; if( xi8 != 21 ) return -8; +i16 xi16 = 123456789; if( xi16 != -13035 ) return -16; +i32 xi32 = 123456789; if( xi32 != 123456789 ) return -32; +i64 xi64 = 123456789; if( xi64 != 123456789 ) return -64; +int xint = 123456789; if( xint != 123456789 ) return -64; + +u1 ui1 = 123456789; if( ui1 != 1 ) return 1; +u8 ui8 = 123456789; if( ui8 != 21 ) return 8; +u16 ui16 = 123456789; if( ui16 != 52501 ) return 16; +u32 ui32 = 123456789; if( ui32 != 123456789 ) return 32; + +flt fflt = 3.141592653589793; if( fflt != 3.141592653589793 ) return 3; +f64 ff64 = 3.141592653589793; if( ff64 != 3.141592653589793 ) return 3; +f32 ff32 = 3.141592653589793; if( ff32 != 3.1415927410125732) return 5; + +return 0; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 355d906b..afa35372 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -2,10 +2,7 @@ package com.seaofnodes.simple.evaluator; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.Field; -import com.seaofnodes.simple.type.TypeInteger; -import com.seaofnodes.simple.type.TypeMemPtr; -import com.seaofnodes.simple.type.TypeStruct; +import com.seaofnodes.simple.type.*; import java.lang.invoke.MethodHandle; import java.lang.invoke.MethodHandles; @@ -80,6 +77,10 @@ public class Evaluator { long in2 = vall(div.in(2)); return in2 == 0 ? 0 : vall(div.in(1)) / in2; } + private double div(DivFNode div) { + double in2 = vald(div.in(2)); + return in2 == 0 ? 0 : vald(div.in(1)) / in2; + } private Object alloc(NewNode alloc) { var type = ((TypeMemPtr)alloc.compute())._obj; @@ -115,10 +116,16 @@ public class Evaluator { if (v instanceof Number n) return n.longValue(); throw new AssertionError("Not a long " + v); } + private double vald(Node node) { + var v = val(node); + if (v instanceof Number n) return n.doubleValue(); + throw new AssertionError("Not a double " + v); + } private Object cons(ConstantNode cons) { var type = cons.compute(); if (type instanceof TypeInteger i) return i.value(); + if (type instanceof TypeFloat i) return i.value(); assert type instanceof TypeMemPtr; return null; } @@ -127,15 +134,32 @@ public class Evaluator { return switch (node) { case ConstantNode cons -> cons(cons); case AddNode add -> vall(add.in(1)) + vall(add.in(2)); + case AddFNode add -> vald(add.in(1)) + vald(add.in(2)); + case BoolNode.EQF eq -> vald(eq.in(1)) == vald(eq.in(2)) ? 1L : 0L; + case BoolNode.LEF le -> vald(le.in(1)) <= vald(le.in(2)) ? 1L : 0L; + case BoolNode.LTF lt -> vald(lt.in(1)) < vald(lt.in(2)) ? 1L : 0L; case BoolNode.EQ eq -> Objects.equals(val(eq.in(1)), val(eq.in(2))) ? 1L : 0L; case BoolNode.LE le -> vall(le.in(1)) <= vall(le.in(2)) ? 1L : 0L; case BoolNode.LT lt -> vall(lt.in(1)) < vall(lt.in(2)) ? 1L : 0L; case DivNode div -> div(div); + case DivFNode div -> div(div); case MinusNode minus -> -vall(minus.in(1)); + case MinusFNode minus -> -vald(minus.in(1)); case MulNode mul -> vall(mul.in(1)) * vall(mul.in(2)); + case MulFNode mul -> vald(mul.in(1)) * vald(mul.in(2)); case NotNode not -> isTrue(val(not.in(1))) ? 0L : 1L; case SubNode sub -> vall(sub.in(1)) - vall(sub.in(2)); + case SubFNode sub -> vald(sub.in(1)) - vald(sub.in(2)); + case ShlNode shl -> vall(shl.in(1)) << vall(shl.in(2)); + case ShrNode shr -> vall(shr.in(1)) >>> vall(shr.in(2)); + case SarNode sar -> vall(sar.in(1)) >> vall(sar.in(2)); + case AndNode and -> vall(and.in(1)) & vall(and.in(2)); + case OrNode or -> vall(or .in(1)) | vall(or .in(2)); + case XorNode xor -> vall(xor.in(1)) ^ vall(xor.in(2)); case CastNode cast -> val(cast.in(1)); + case RoundF32Node rnd -> (double)(float)vald(rnd.in(1)); + case ToIntegerNode cvt -> (long)vald(cvt.in(1)); + case ToFloatNode cast -> (double)vall(cast.in(1)); case LoadNode load -> load(load); case StoreNode store -> store(store); case MemMergeNode merge -> MEMORY; diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 14baadba..ec6e7816 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -2,8 +2,12 @@ package com.seaofnodes.simple.fuzzer; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.ScopeNode; +import com.seaofnodes.simple.type.TypeInteger; -import java.util.*; +import java.util.ArrayList; +import java.util.HashSet; +import java.util.List; +import java.util.Random; import java.util.function.Predicate; /** @@ -21,7 +25,7 @@ public class ScriptGenerator { private static final int MAX_BLOCK_DEPTH = 4; private static final int MAX_EXPRESSION_DEPTH = 10; private static final int MAX_SUFFIX_RECURSIVE_DEPTH = 10; - + /** * Number of spaces per indentation */ @@ -54,7 +58,7 @@ public class ScriptGenerator { /** * Binary operators. */ - private static final String[] BINARY_OP = {"==", "!=", "<", "<=", ">", ">=", "+", "-", "*", "/"}; + private static final String[] BINARY_OP = {"==", "!=", "<", "<=", ">", ">=", "+", "-", "*", "/", "&", ">>", ">>>", "<<"}; /** * Unary operators. */ @@ -87,8 +91,33 @@ public class ScriptGenerator { } - private static final Type TYPE_INT = new Type("int"); + private static final Type TYPE_FLT = new Type("flt"); + + private static class TypeInt extends Type { + + TypeInt(String name) { + super(name); + } + + @Override + boolean isa(Type other) { + return super.isa(other) || other == TYPE_FLT || other instanceof TypeInt; + } + } + + private static final List INTTYPES = new ArrayList<>(); + + static { + new Parser("", TypeInteger.BOT); + for(var e:Parser.TYPES.entrySet()) { + if (e.getValue() instanceof TypeInteger) { + INTTYPES.add(new TypeInt(e.getKey())); + } + } + } + private static final Type TYPE_INT = INTTYPES.stream().filter(t->t.name.equals("int")).findAny().get(); + private static final Type TYPE_BOOL = INTTYPES.stream().filter(t->t.name.equals("bool")).findAny().get(); private static class Variable { final String name; @@ -347,13 +376,18 @@ public class ScriptGenerator { return v; } + public TypeInt getIntType() { + return randFromList(INTTYPES); + } + /** * Get a random type * @return A random type */ private Type getType(boolean allowForward) { int t = random.nextInt(10); - if( t<5 || structs.isEmpty() ) return TYPE_INT; + if( t<5 || structs.isEmpty() ) return getIntType(); + if( t<7 ) return TYPE_FLT; if (allowForward && random.nextInt(10)==0) { int i=random.nextInt(forwardStructs.size()+1); if (i>0) return forwardStructs.get(i-1).nullable; @@ -433,7 +467,7 @@ public class ScriptGenerator { int idx = random.nextInt(forwardStructs.size()+10); TypeStruct struct; if (idx < 10) { - var name = getStructName(); + var name = getStructName(); struct = new TypeStruct(name); forwardStructs.add(struct); } else { @@ -546,7 +580,7 @@ public class ScriptGenerator { */ public int genIf() { sb.append("if("); - genExpression(TYPE_INT, true); + genExpression(TYPE_BOOL, true); sb.append(") "); var stop = genStatementBlock(); if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) { @@ -592,7 +626,7 @@ public class ScriptGenerator { */ public int genWhile() { sb.append("while("); - genExpression(TYPE_INT, true); + genExpression(TYPE_BOOL, true); sb.append(") "); loopDepth++; genStatementBlock(); @@ -710,7 +744,7 @@ public class ScriptGenerator { */ public void genExpression(Type type, boolean change) { if (change && generateInvalid()) type = getType(); - if (type != TYPE_INT) { + if (!(type instanceof TypeInt) && type != TYPE_FLT) { genUnary(type, false); return; } @@ -727,7 +761,7 @@ public class ScriptGenerator { */ public void genUnary(Type type, boolean change) { if (change && generateInvalid()) type = getType(); - if (type != TYPE_INT) { + if (!(type instanceof TypeInt) && type != TYPE_FLT) { genSuffix(type, false); return; } @@ -807,14 +841,15 @@ public class ScriptGenerator { */ public void genConst(Type type) { if (generateInvalid()) type = getType(); - if (type == TYPE_INT) { + if (type instanceof TypeInt || (type == TYPE_FLT && random.nextBoolean())) { var rand = random.nextInt(10); switch (rand) { case 0 -> sb.append("true"); case 1 -> sb.append("false"); default -> sb.append(random.nextInt(1<<(rand-2))); } - + } else if (type == TYPE_FLT) { + sb.append(random.nextFloat()); } else if (type instanceof TypeNullable n) { if ((n.base instanceof TypeStruct s && s.fields == null) || random.nextBoolean()) { sb.append("null"); -- cgit v1.2.3