diff options
Diffstat (limited to 'chapter25/src')
11 files changed, 124 insertions, 10 deletions
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index ca2cc955..64892f3f 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -49,7 +49,7 @@ public class CodeGen { // -Dsimple.assert.expensive=0 disables these checks // -Dsimple.assert.expensive=1 checks every step // -Dsimple.assert.expensive=N checks once every 1<<N steps - private static final int EXPENSIVE_ASSERT_LOG = Integer.getInteger("simple.assert.expensive",8); + private static final int EXPENSIVE_ASSERT_LOG = Integer.getInteger("simple.assert.expensive",1); public static boolean expensiveAssert() { return EXPENSIVE_ASSERT_LOG > 0; } public static boolean expensiveAssert( int trip ) { if( EXPENSIVE_ASSERT_LOG <= 0 ) return false; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/AddNode.java index 46607c23..a29ba73b 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -37,7 +37,7 @@ public class AddNode extends ArithNode { // Add of 0. We do not check for (0+x) because this will already // canonicalize to (x+0) - if( t2 == TypeInteger.ZERO ) + if( t2 == TypeInteger.ZERO && lhs._type.isa(compute()) ) return lhs; // Add of same to a multiply by 2 diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/DivNode.java index dcc9a27a..f173f0ef 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -22,12 +22,12 @@ public class DivNode extends ArithNode { @Override public Node idealize() { // Div of 1. - if( in(2)._type == TypeInteger.TRUE ) + if( in(2)._type == TypeInteger.TRUE && in(1)._type.isa(compute()) ) return in(1); // Div of constant if( _mode==2 ) { - if( in(2)._type == TypeFloat.constant(1.) ) + if( in(2)._type == TypeFloat.constant(1.) && in(1)._type.isa(compute()) ) return in(1); if( in(2)._type instanceof TypeFloat f && f.isConstant() ) return new MulNode(in(1),ConstantNode.make(TypeFloat.constant(1.0/f.value())).peephole(),_mode); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 2261adab..34e5667e 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -65,7 +65,7 @@ public class MinusNode extends Node implements ModeNode { @Override public Node idealize() { // -(-x) is x - if( in(1) instanceof MinusNode minus ) + if( in(1) instanceof MinusNode minus && minus.in(1)._type.isa(compute()) ) return minus.in(1); // Can we decide int vs flt? diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/MulNode.java index e773ed57..bb99cad5 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -35,7 +35,7 @@ public class MulNode extends ArithNode { // Mul of 1. We do not check for (1*x) because this will already // canonicalize to (x*1) long c = i.value(); - if( c==1 ) return lhs; + if( c==1 ) return lhs._type.isa(compute()) ? lhs : super.idealize(); if( c==0 ) return CodeGen.CODE.ZERO; // Mul by a power of 2, +/-1. Bit patterns more complex than this // are unlikely to win on an X86 vs the normal "imul", and so diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/SarNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/SarNode.java index e3f99ed4..de21fead 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -28,7 +28,7 @@ public class SarNode extends ArithNode { Type t2 = rhs._type; // Sar of 0. - if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 && forceInt(lhs) ) + if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 && forceInt(lhs) && lhs._type instanceof TypeInteger ) return lhs; // TODO: x >> 3 >> (y ? 1 : 2) ==> x >> (y ? 4 : 5) diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ShlNode.java index 24d9bdb4..8f7b7b7e 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -33,7 +33,7 @@ public class ShlNode extends ArithNode { if( rhs._type instanceof TypeInteger shl && shl.isConstant() ) { // Shl of 0. - if( (shl.value()&63)==0 && forceInt(lhs) ) + if( (shl.value()&63)==0 && forceInt(lhs) && lhs._type instanceof TypeInteger ) return lhs; // (x + c) << i => (x << i) + (c << i) if( lhs instanceof AddNode add && addDep(add).in(2)._type instanceof TypeInteger c && c.isConstant() ) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 1bf7d118..2b268b42 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -23,7 +23,7 @@ public class ShrNode extends ArithNode { Type t2 = rhs._type; // Shr of 0. - if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 && forceInt(lhs) ) + if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 && forceInt(lhs) && lhs._type instanceof TypeInteger ) return lhs; // TODO: x >>> 3 >>> (y ? 1 : 2) ==> x >>> (y ? 4 : 5) diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/XorNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/XorNode.java index 27ebc3dc..a979bad8 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -26,7 +26,7 @@ public class XorNode extends ArithNode { // 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 && forceInt(lhs) ) + if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 && forceInt(lhs) && lhs._type instanceof TypeInteger ) return lhs; // Move constants to RHS: con*arg becomes arg*con diff --git a/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index 66bc4717..912c78ae 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -34,6 +34,7 @@ public class FuzzerWrap { }; private static final long[] OPEN_FAILING_SEEDS = { + 5948158604996761547L, }; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/IntegerIdentityTest.java b/chapter25/src/test/java/com/seaofnodes/simple/IntegerIdentityTest.java new file mode 100644 index 00000000..90864731 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/IntegerIdentityTest.java @@ -0,0 +1,113 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.*; + +public class IntegerIdentityTest { + private static final String[] OPS = {"And","Or","Xor","Shl","Sar","Shr","Add","Mul","Div"}; + + @Test public void testIdentityWaitsForIntegerInput() { + new CodeGen("return 0;").parse(); + for( String name : OPS ) { + Node lhs = input(Type.BOTTOM); + Node rhs = input(TypeInteger.constant(identity(name))); + Node op = op(name,lhs,rhs); + assertFalse(name,lhs._type.isa(op.compute())); + assertNull(name,op.idealize()); + // Model a provisional input lifting to int. The same fold can now fire. + lhs._type = TypeInteger.BOT; + assertSame(name,lhs,op.idealize()); + assertTrue(name,lhs._type.isa(op.compute())); + } + } + + @Test public void testNonIntegerIdentityCannotEraseTheOperator() { + new CodeGen("return 0;").parse(); + for( Type type : new Type[]{TypeFloat.constant(3.5),TypeScalar.BOT} ) + for( String name : OPS ) { + Node lhs=input(type); + Node op=op(name,lhs,input(TypeInteger.constant(identity(name)))); + assertNull(name,op.idealize()); + } + } + + @Test public void testIntegerIdentitiesAndMaskedShiftsStillFold() { + new CodeGen("return 0;").parse(); + for( String name : OPS ) + for( Type type : new Type[]{TypeInteger.BOT,TypeInteger.make(2,7),TypeInteger.constant(5)} ) { + Node lhs=input(type); + long[] identities = name.equals("And") ? new long[]{-1} : + name.equals("Shl") || name.equals("Sar") || name.equals("Shr") ? new long[]{0,64,-64} : new long[]{identity(name)}; + for( long identity : identities ) { + Node op=op(name,lhs,input(TypeInteger.constant(identity))); + assertSame(name,lhs,op.idealize()); + assertTrue(name,lhs._type.isa(op.compute())); + } + } + } + + @Test public void testFloatingIdentitiesKeepTheirResultType() { + new CodeGen("return 0;").parse(); + for( Type type : new Type[]{Type.BOTTOM,TypeInteger.BOT,TypeFloat.F64} ) { + Node lhs=input(type); + Node zero=input(TypeInteger.ZERO), one=input(TypeInteger.TRUE); + Node[] ops = {new AddNode(lhs,zero,(byte)2), new MulNode(lhs,one,(byte)2), + new DivNode(lhs,one,(byte)2), + new DivNode(lhs,input(TypeFloat.constant(1.)),(byte)2)}; + for( Node op : ops ) { + Node replacement=op.idealize(); + if( type==TypeFloat.F64 ) + assertSame(lhs,replacement); + else + assertNotSame(lhs,replacement); + if( replacement!=null ) + assertTrue(replacement.compute().isa(op.compute())); + } + } + } + + @Test public void testDoubleNegationWaitsForIntegerInput() { + new CodeGen("return 0;").parse(); + for( Type type : new Type[]{Type.BOTTOM,TypeFloat.constant(3.5),TypeScalar.BOT} ) { + Node lhs=input(type); + Node inner=new MinusNode(lhs,(byte)1); + inner._type=inner.compute(); + Node outer=new MinusNode(inner,(byte)1); + assertFalse(lhs._type.isa(outer.compute())); + assertNull(outer.idealize()); + lhs._type=TypeInteger.make(2,7); + inner._type=inner.compute(); + assertSame(lhs,outer.idealize()); + assertTrue(lhs._type.isa(outer.compute())); + } + } + + // These tests exercise idealize directly, before GVN or constant folding. + private static Node input(Type type) { + Node n = new ConstantNode(type); + n._type=type; + return n; + } + + private static long identity(String name) { + return name.equals("And") ? -1 : name.equals("Mul") || name.equals("Div") ? 1 : 0; + } + + private static Node op(String name, Node lhs, Node rhs) { + return switch(name) { + case "And" -> new AndNode(null,lhs,rhs); + case "Or" -> new OrNode(null,lhs,rhs); + case "Xor" -> new XorNode(null,lhs,rhs); + case "Shl" -> new ShlNode(null,lhs,rhs); + case "Sar" -> new SarNode(null,lhs,rhs); + case "Shr" -> new ShrNode(null,lhs,rhs); + case "Add" -> new AddNode(lhs,rhs,(byte)1); + case "Mul" -> new MulNode(lhs,rhs,(byte)1); + case "Div" -> new DivNode(lhs,rhs,(byte)1); + default -> throw new AssertionError(name); + }; + } +} |