From a04599b6fc90bbab443d883595a415238586a526 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 18 Aug 2024 10:37:43 -0700 Subject: Shift operators; sign extension --- .../main/java/com/seaofnodes/simple/Parser.java | 51 ++++++++++++++++++--- .../java/com/seaofnodes/simple/node/AndNode.java | 2 +- .../java/com/seaofnodes/simple/node/SarNode.java | 52 ++++++++++++++++++++++ .../java/com/seaofnodes/simple/node/ShlNode.java | 52 ++++++++++++++++++++++ .../java/com/seaofnodes/simple/node/ShrNode.java | 52 ++++++++++++++++++++++ .../com/seaofnodes/simple/type/TypeInteger.java | 1 + .../java/com/seaofnodes/simple/Chapter14Test.java | 26 +++++++++++ 7 files changed, 228 insertions(+), 8 deletions(-) create mode 100644 chapter14/src/main/java/com/seaofnodes/simple/node/SarNode.java create mode 100644 chapter14/src/main/java/com/seaofnodes/simple/node/ShlNode.java create mode 100644 chapter14/src/main/java/com/seaofnodes/simple/node/ShrNode.java (limited to 'chapter14') diff --git a/chapter14/src/main/java/com/seaofnodes/simple/Parser.java b/chapter14/src/main/java/com/seaofnodes/simple/Parser.java index de5565ab..5720ff8b 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/Parser.java @@ -59,6 +59,7 @@ public class Parser { add("else"); add("false"); add("flt"); + add("i8"); add("if"); add("int"); add("new"); @@ -93,11 +94,12 @@ public class Parser { TYPES.put("bool",TypeInteger.U1 ); TYPES.put("byte",TypeInteger.U8 ); TYPES.put("flt" ,TypeFloat .BOT); + TYPES.put("i8" ,TypeInteger.I8 ); TYPES.put("int" ,TypeInteger.BOT); TYPES.put("u1" ,TypeInteger.U1 ); - TYPES.put("u8" ,TypeInteger.U8 ); TYPES.put("u16" ,TypeInteger.U16); TYPES.put("u32" ,TypeInteger.U32); + TYPES.put("u8" ,TypeInteger.U8 ); SCHEDULED = false; _lexer = new Lexer(source); _scope = new ScopeNode(); @@ -446,8 +448,7 @@ public class Parser { if( expr._type instanceof TypeInteger && t instanceof TypeFloat ) expr = new ToFloatNode(expr).peephole(); // Auto-narrow wide ints to narrow ints - if( expr._type instanceof TypeInteger e0 && t instanceof TypeInteger t0 && !e0.isa(t) ) - expr = new AndNode(expr,new ConstantNode(TypeInteger.constant(t0._max-t0._min)).peephole()).peephole(); + expr = zsMask(expr,t); // Auto-deepen forward ref types Type e = expr._type; if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null ) @@ -520,7 +521,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 @@ -533,7 +534,7 @@ 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.setDef(idx,parseShift()); lhs = lhs.widen().peephole(); if( negate ) // Extra negate for != lhs = new NotNode(lhs).peephole(); @@ -541,6 +542,28 @@ public class Parser { 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 SarNode(lhs,null); + else if( match(">>>")) lhs = new ShrNode(lhs,null); + else break; + lhs.setDef(2,parseAddition()); + lhs = lhs.widen().peephole(); + } + return lhs; + } + /** * Parse an additive expression * @@ -674,8 +697,7 @@ public class Parser { Node val = parseExpression(); Type glb = base._fields[idx]._type; // Auto-truncate when storing to narrow fields - if( !val._type.isa(glb) && glb instanceof TypeInteger t0) - val = new AndNode(val,new ConstantNode(TypeInteger.constant(t0._max-t0._min)).peephole()).peephole(); + val = zsMask(val,glb); memAlias(alias, new StoreNode(name, alias,glb, memAlias(alias), expr, val, false).peephole()); return expr; // "obj.a = expr" returns the expression while updating memory } @@ -685,6 +707,21 @@ public class Parser { return parsePostfix(new LoadNode(name, alias, declaredType, memAlias(alias), 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 TypeInteger tval && t instanceof TypeInteger t0 && !tval.isa(t0)) ) + return val; + if( t0._min==0 ) + return new AndNode(val,new ConstantNode(TypeInteger.constant(t0._max)).peephole()).peephole(); + 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 * diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/AndNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/AndNode.java index 1a3995d4..f4933d9c 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -38,7 +38,7 @@ public class AndNode extends Node { // And of -1. We do not check for (0&x) because this will already // canonicalize to (x&0) - if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==-1 ) + if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==-1 ) return rhs; // Move constants to RHS: con*arg becomes arg*con diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/SarNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/SarNode.java new file mode 100644 index 00000000..f84b5789 --- /dev/null +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -0,0 +1,52 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +import java.util.BitSet; + +public class SarNode extends Node { + public SarNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Sar"; } + + @Override public String glabel() { return ">>"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append(">>"), visited); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type 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; + + // Sar of 0. + if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 ) + return lhs; + + // 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 SarNode(lhs,rhs); } +} diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/ShlNode.java new file mode 100644 index 00000000..5c7f43be --- /dev/null +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -0,0 +1,52 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +import java.util.BitSet; + +public class ShlNode extends Node { + public ShlNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Shl"; } + + @Override public String glabel() { return "<<"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("<<"), visited); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if( i0.isConstant() && i1.isConstant() ) + return TypeInteger.constant(i0.value()<>>"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append(">>>"), visited); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type 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; + + // Shr of 0. + if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 ) + return lhs; + + // 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 ShrNode(lhs,rhs); } +} 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 c84a4c13..0221da7a 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -17,6 +17,7 @@ public class TypeInteger extends Type { 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); + public final static TypeInteger I8 = make(-128,127); /** * Describes an integer *range* - everything from min to max; both min and diff --git a/chapter14/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter14Test.java index f76e1903..268111d8 100644 --- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -89,4 +89,30 @@ return f.b; 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(false).iterate(false); + assertEquals("return -1;", 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(false).iterate(false); + assertEquals("return 52501;", stop.toString()); + assertEquals(52501L, Evaluator.evaluate(stop, 0)); + } + } -- cgit v1.2.3