From 3e950abc9eb2bcafbb36761ace5fcf5707a503a3 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 5 Oct 2026 09:35:31 -0700 Subject: Partial integer update --- .../java/com/seaofnodes/simple/node/AddNode.java | 2 +- .../java/com/seaofnodes/simple/node/AndNode.java | 2 +- .../java/com/seaofnodes/simple/node/DivNode.java | 2 +- .../java/com/seaofnodes/simple/node/MulNode.java | 2 +- .../java/com/seaofnodes/simple/node/OrNode.java | 2 +- .../java/com/seaofnodes/simple/node/SarNode.java | 2 +- .../java/com/seaofnodes/simple/node/ShlNode.java | 2 +- .../java/com/seaofnodes/simple/node/ShrNode.java | 2 +- .../java/com/seaofnodes/simple/node/XorNode.java | 2 +- .../com/seaofnodes/simple/IntegerIdentityTest.java | 76 ++++++++++++++++++++++ 10 files changed, 85 insertions(+), 9 deletions(-) create mode 100644 chapter15/src/test/java/com/seaofnodes/simple/IntegerIdentityTest.java (limited to 'chapter15/src') diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/AddNode.java index 97d2bb9b..ea5fdfdf 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -48,7 +48,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.isConstant() && 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 diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/AndNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/AndNode.java index 7e4b898b..a170cc7e 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -41,7 +41,7 @@ public class AndNode extends Node { // 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 ) + 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 diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/DivNode.java index 76e98678..232390b2 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -37,7 +37,7 @@ public class DivNode extends Node { @Override public Node idealize() { // Div of 1. - if( in(2)._type == TypeInteger.TRUE ) + if( in(2)._type == TypeInteger.TRUE && in(1)._type instanceof TypeInteger ) return in(1); return null; } diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/MulNode.java index 6f679462..2b2d4bd2 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -41,7 +41,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 diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/OrNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/OrNode.java index 1b32d4fb..2c54e86c 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -38,7 +38,7 @@ public class OrNode extends Node { // 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 ) + 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 diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/SarNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/SarNode.java index ba99fde8..c1a34f9a 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -40,7 +40,7 @@ public class SarNode extends Node { Type t2 = rhs._type; // Sar of 0. - if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==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) diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/ShlNode.java index 28e6dd14..97fd7d0f 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -36,7 +36,7 @@ public class ShlNode extends Node { if( rhs._type instanceof TypeInteger shl && shl.isConstant() ) { // Shl of 0. - if( (shl.value()&63)==0 ) + if( (shl.value()&63)==0 && lhs._type instanceof TypeInteger ) return lhs; // (x + c) << i => (x << i) + (c << i) if( lhs instanceof AddNode add && add.in(2)._type instanceof TypeInteger c && c.isConstant() ) { diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 16d78ebf..f5539d2f 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -36,7 +36,7 @@ public class ShrNode extends Node { Type t2 = rhs._type; // Shr of 0. - if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==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) diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/XorNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/XorNode.java index 30a88dca..b46f4791 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -38,7 +38,7 @@ public class XorNode extends Node { // 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 ) + 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 diff --git a/chapter15/src/test/java/com/seaofnodes/simple/IntegerIdentityTest.java b/chapter15/src/test/java/com/seaofnodes/simple/IntegerIdentityTest.java new file mode 100644 index 00000000..97650f25 --- /dev/null +++ b/chapter15/src/test/java/com/seaofnodes/simple/IntegerIdentityTest.java @@ -0,0 +1,76 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +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 Parser("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 Parser("return 0;").parse(); + for( Type type : new Type[]{TypeFloat.constant(3.5)} ) + 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 Parser("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())); + } + } + } + + // 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(lhs,rhs); + case "Or" -> new OrNode(lhs,rhs); + case "Xor" -> new XorNode(lhs,rhs); + case "Shl" -> new ShlNode(lhs,rhs); + case "Sar" -> new SarNode(lhs,rhs); + case "Shr" -> new ShrNode(lhs,rhs); + case "Add" -> new AddNode(lhs,rhs); + case "Mul" -> new MulNode(lhs,rhs); + case "Div" -> new DivNode(lhs,rhs); + default -> throw new AssertionError(name); + }; + } +} -- cgit v1.2.3