diff options
| author | Cliff Click <cliffc@acm.org> | 2026-10-28 15:05:08 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-28 15:05:08 -0700 |
| commit | 50924bbe7cfeecfe7aec1885dae9bbda0013ac1b (patch) | |
| tree | 2d04316faa3c73e2a2586de8f95f9b9fb248425f | |
| parent | 86ce5bc5d5018dcb62054d214b23f7a59b9c0d7d (diff) | |
| download | Simple-50924bbe7cfeecfe7aec1885dae9bbda0013ac1b.tar.gz Simple-50924bbe7cfeecfe7aec1885dae9bbda0013ac1b.zip | |
Remove _phase checks from Arith & Compute
Fix some monotonicty bugs, rounding bugs, in float ops
81 files changed, 1843 insertions, 86 deletions
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/AddFNode.java index fd713156..b1415e1c 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -14,10 +14,13 @@ public class AddFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/DivFNode.java index a3f4318d..9e5d5955 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -14,10 +14,13 @@ public class DivFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 6a57f3c5..32236759 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -14,10 +14,13 @@ public class MulFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 2d218a03..67a4e64b 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -14,10 +14,13 @@ public class SubFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter14/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/chapter14/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java new file mode 100644 index 00000000..7ad30b46 --- /dev/null +++ b/chapter14/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FloatPrecisionTest { + @Test public void testFloatPrecision() { + String[] ops = {"+1.0","-1.0","*3.0","/3.0"}; + long[] args = {16777216,-16777216,16777215,1}; + double[] results = {16777217.0,-16777217.0,50331645.0,1.0/3.0}; + for( int i = 0; i<ops.length; i++ ) { + String expr = "x"+ops[i]; + assertEquals(expr,Double.toString(results[i]), + evaluate("f32 x = arg; return "+expr+";",args[i])); + assertEquals(expr,Double.toString((float)results[i]), + evaluate("f32 x = arg; f32 y = "+expr+"; return y;",args[i])); + } + } + + private static String evaluate(String src, long arg) { + return Evaluator.evaluate(new Parser(src).parse().iterate(),arg).toString(); + } + + @Test public void testMonotoneCompute() { + new Parser(""); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.TOP,Type.BOTTOM,TypeFloat.B32,TypeFloat.BOT, + TypeFloat.B32.dual(),TypeFloat.BOT.dual())); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,3.0,16777216.0,16777217.0, + Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + // Isolated analysis inputs; no peepholes can fold the tested nodes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + for( Node op : new Node[]{new AddFNode(lhs,rhs),new SubFNode(lhs,rhs), + new MulFNode(lhs,rhs),new DivFNode(lhs,rhs)} ) { + Type[][] results = new Type[inputs.size()][inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = op.compute(); + } + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<inputs.size(); k++ ) + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(op.label()+": "+inputs.get(i)+" -> "+inputs.get(j)+ + ", other="+inputs.get(k)+"; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } +} diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/AddFNode.java index fd713156..b1415e1c 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -14,10 +14,13 @@ public class AddFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/DivFNode.java index a3f4318d..9e5d5955 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -14,10 +14,13 @@ public class DivFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 6a57f3c5..32236759 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -14,10 +14,13 @@ public class MulFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 2d218a03..67a4e64b 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -14,10 +14,13 @@ public class SubFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/chapter15/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java new file mode 100644 index 00000000..7ad30b46 --- /dev/null +++ b/chapter15/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FloatPrecisionTest { + @Test public void testFloatPrecision() { + String[] ops = {"+1.0","-1.0","*3.0","/3.0"}; + long[] args = {16777216,-16777216,16777215,1}; + double[] results = {16777217.0,-16777217.0,50331645.0,1.0/3.0}; + for( int i = 0; i<ops.length; i++ ) { + String expr = "x"+ops[i]; + assertEquals(expr,Double.toString(results[i]), + evaluate("f32 x = arg; return "+expr+";",args[i])); + assertEquals(expr,Double.toString((float)results[i]), + evaluate("f32 x = arg; f32 y = "+expr+"; return y;",args[i])); + } + } + + private static String evaluate(String src, long arg) { + return Evaluator.evaluate(new Parser(src).parse().iterate(),arg).toString(); + } + + @Test public void testMonotoneCompute() { + new Parser(""); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.TOP,Type.BOTTOM,TypeFloat.B32,TypeFloat.BOT, + TypeFloat.B32.dual(),TypeFloat.BOT.dual())); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,3.0,16777216.0,16777217.0, + Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + // Isolated analysis inputs; no peepholes can fold the tested nodes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + for( Node op : new Node[]{new AddFNode(lhs,rhs),new SubFNode(lhs,rhs), + new MulFNode(lhs,rhs),new DivFNode(lhs,rhs)} ) { + Type[][] results = new Type[inputs.size()][inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = op.compute(); + } + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<inputs.size(); k++ ) + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(op.label()+": "+inputs.get(i)+" -> "+inputs.get(j)+ + ", other="+inputs.get(k)+"; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } +} diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/AddFNode.java index fd713156..b1415e1c 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -14,10 +14,13 @@ public class AddFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/DivFNode.java index a3f4318d..9e5d5955 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -14,10 +14,13 @@ public class DivFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 6a57f3c5..32236759 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -14,10 +14,13 @@ public class MulFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 2d218a03..67a4e64b 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -14,10 +14,13 @@ public class SubFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/chapter16/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java new file mode 100644 index 00000000..7ad30b46 --- /dev/null +++ b/chapter16/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FloatPrecisionTest { + @Test public void testFloatPrecision() { + String[] ops = {"+1.0","-1.0","*3.0","/3.0"}; + long[] args = {16777216,-16777216,16777215,1}; + double[] results = {16777217.0,-16777217.0,50331645.0,1.0/3.0}; + for( int i = 0; i<ops.length; i++ ) { + String expr = "x"+ops[i]; + assertEquals(expr,Double.toString(results[i]), + evaluate("f32 x = arg; return "+expr+";",args[i])); + assertEquals(expr,Double.toString((float)results[i]), + evaluate("f32 x = arg; f32 y = "+expr+"; return y;",args[i])); + } + } + + private static String evaluate(String src, long arg) { + return Evaluator.evaluate(new Parser(src).parse().iterate(),arg).toString(); + } + + @Test public void testMonotoneCompute() { + new Parser(""); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.TOP,Type.BOTTOM,TypeFloat.B32,TypeFloat.BOT, + TypeFloat.B32.dual(),TypeFloat.BOT.dual())); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,3.0,16777216.0,16777217.0, + Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + // Isolated analysis inputs; no peepholes can fold the tested nodes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + for( Node op : new Node[]{new AddFNode(lhs,rhs),new SubFNode(lhs,rhs), + new MulFNode(lhs,rhs),new DivFNode(lhs,rhs)} ) { + Type[][] results = new Type[inputs.size()][inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = op.compute(); + } + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<inputs.size(); k++ ) + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(op.label()+": "+inputs.get(i)+" -> "+inputs.get(j)+ + ", other="+inputs.get(k)+"; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } +} diff --git a/chapter17a/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter17a/src/main/java/com/seaofnodes/simple/node/AddFNode.java index fd713156..b1415e1c 100644 --- a/chapter17a/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter17a/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -14,10 +14,13 @@ public class AddFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter17a/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter17a/src/main/java/com/seaofnodes/simple/node/DivFNode.java index c678ac3e..5cfaa0a2 100644 --- a/chapter17a/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/chapter17a/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -14,10 +14,13 @@ public class DivFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter17a/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter17a/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 6a57f3c5..32236759 100644 --- a/chapter17a/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/chapter17a/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -14,10 +14,13 @@ public class MulFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter17a/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter17a/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 2d218a03..67a4e64b 100644 --- a/chapter17a/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter17a/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -14,10 +14,13 @@ public class SubFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter17a/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/chapter17a/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java new file mode 100644 index 00000000..7ad30b46 --- /dev/null +++ b/chapter17a/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FloatPrecisionTest { + @Test public void testFloatPrecision() { + String[] ops = {"+1.0","-1.0","*3.0","/3.0"}; + long[] args = {16777216,-16777216,16777215,1}; + double[] results = {16777217.0,-16777217.0,50331645.0,1.0/3.0}; + for( int i = 0; i<ops.length; i++ ) { + String expr = "x"+ops[i]; + assertEquals(expr,Double.toString(results[i]), + evaluate("f32 x = arg; return "+expr+";",args[i])); + assertEquals(expr,Double.toString((float)results[i]), + evaluate("f32 x = arg; f32 y = "+expr+"; return y;",args[i])); + } + } + + private static String evaluate(String src, long arg) { + return Evaluator.evaluate(new Parser(src).parse().iterate(),arg).toString(); + } + + @Test public void testMonotoneCompute() { + new Parser(""); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.TOP,Type.BOTTOM,TypeFloat.B32,TypeFloat.BOT, + TypeFloat.B32.dual(),TypeFloat.BOT.dual())); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,3.0,16777216.0,16777217.0, + Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + // Isolated analysis inputs; no peepholes can fold the tested nodes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + for( Node op : new Node[]{new AddFNode(lhs,rhs),new SubFNode(lhs,rhs), + new MulFNode(lhs,rhs),new DivFNode(lhs,rhs)} ) { + Type[][] results = new Type[inputs.size()][inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = op.compute(); + } + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<inputs.size(); k++ ) + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(op.label()+": "+inputs.get(i)+" -> "+inputs.get(j)+ + ", other="+inputs.get(k)+"; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } +} diff --git a/chapter17b/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter17b/src/main/java/com/seaofnodes/simple/node/AddFNode.java index fd713156..b1415e1c 100644 --- a/chapter17b/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter17b/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -14,10 +14,13 @@ public class AddFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter17b/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter17b/src/main/java/com/seaofnodes/simple/node/DivFNode.java index c678ac3e..5cfaa0a2 100644 --- a/chapter17b/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/chapter17b/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -14,10 +14,13 @@ public class DivFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter17b/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter17b/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 6a57f3c5..32236759 100644 --- a/chapter17b/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/chapter17b/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -14,10 +14,13 @@ public class MulFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter17b/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter17b/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 2d218a03..67a4e64b 100644 --- a/chapter17b/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter17b/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -14,10 +14,13 @@ public class SubFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.BOT; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter17b/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/chapter17b/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java new file mode 100644 index 00000000..7ad30b46 --- /dev/null +++ b/chapter17b/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FloatPrecisionTest { + @Test public void testFloatPrecision() { + String[] ops = {"+1.0","-1.0","*3.0","/3.0"}; + long[] args = {16777216,-16777216,16777215,1}; + double[] results = {16777217.0,-16777217.0,50331645.0,1.0/3.0}; + for( int i = 0; i<ops.length; i++ ) { + String expr = "x"+ops[i]; + assertEquals(expr,Double.toString(results[i]), + evaluate("f32 x = arg; return "+expr+";",args[i])); + assertEquals(expr,Double.toString((float)results[i]), + evaluate("f32 x = arg; f32 y = "+expr+"; return y;",args[i])); + } + } + + private static String evaluate(String src, long arg) { + return Evaluator.evaluate(new Parser(src).parse().iterate(),arg).toString(); + } + + @Test public void testMonotoneCompute() { + new Parser(""); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.TOP,Type.BOTTOM,TypeFloat.B32,TypeFloat.BOT, + TypeFloat.B32.dual(),TypeFloat.BOT.dual())); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,3.0,16777216.0,16777217.0, + Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + // Isolated analysis inputs; no peepholes can fold the tested nodes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + for( Node op : new Node[]{new AddFNode(lhs,rhs),new SubFNode(lhs,rhs), + new MulFNode(lhs,rhs),new DivFNode(lhs,rhs)} ) { + Type[][] results = new Type[inputs.size()][inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = op.compute(); + } + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<inputs.size(); k++ ) + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(op.label()+": "+inputs.get(i)+" -> "+inputs.get(j)+ + ", other="+inputs.get(k)+"; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } +} diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/AddFNode.java index fd713156..3b37dc84 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -14,10 +14,13 @@ public class AddFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/DivFNode.java index a3f4318d..80b7dccf 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -14,10 +14,13 @@ public class DivFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 6a57f3c5..f24270cf 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -14,10 +14,13 @@ public class MulFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 2d218a03..4dbc141e 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -14,10 +14,13 @@ public class SubFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/chapter18/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java new file mode 100644 index 00000000..6b3ddae3 --- /dev/null +++ b/chapter18/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FloatPrecisionTest { + @Test public void testFloatPrecision() { + String[] ops = {"+1.0","-1.0","*3.0","/3.0"}; + long[] args = {16777216,-16777216,16777215,1}; + double[] results = {16777217.0,-16777217.0,50331645.0,1.0/3.0}; + for( int i = 0; i<ops.length; i++ ) { + String expr = "x"+ops[i]; + assertEquals(expr,Double.toString(results[i]), + evaluate("f32 x = arg; return "+expr+";",args[i])); + assertEquals(expr,Double.toString((float)results[i]), + evaluate("f32 x = arg; f32 y = "+expr+"; return y;",args[i])); + } + } + + private static String evaluate(String src, long arg) { + CodeGen code = new CodeGen(src).parse().iter(); + return Eval2.eval(code,arg); + } + + @Test public void testMonotoneCompute() { + new CodeGen(""); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.TOP,Type.BOTTOM,TypeFloat.F32,TypeFloat.F64, + TypeFloat.F32.dual(),TypeFloat.F64.dual())); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,3.0,16777216.0,16777217.0, + Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + // Isolated analysis inputs; no peepholes can fold the tested nodes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + for( Node op : new Node[]{new AddFNode(lhs,rhs),new SubFNode(lhs,rhs), + new MulFNode(lhs,rhs),new DivFNode(lhs,rhs)} ) { + Type[][] results = new Type[inputs.size()][inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = op.compute(); + } + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<inputs.size(); k++ ) + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(op.label()+": "+inputs.get(i)+" -> "+inputs.get(j)+ + ", other="+inputs.get(k)+"; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/AddFNode.java index fd713156..3b37dc84 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -14,10 +14,13 @@ public class AddFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/DivFNode.java index a3f4318d..80b7dccf 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -14,10 +14,13 @@ public class DivFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 6a57f3c5..f24270cf 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -14,10 +14,13 @@ public class MulFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 2d218a03..4dbc141e 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -14,10 +14,13 @@ public class SubFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter19/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/chapter19/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java new file mode 100644 index 00000000..6b3ddae3 --- /dev/null +++ b/chapter19/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FloatPrecisionTest { + @Test public void testFloatPrecision() { + String[] ops = {"+1.0","-1.0","*3.0","/3.0"}; + long[] args = {16777216,-16777216,16777215,1}; + double[] results = {16777217.0,-16777217.0,50331645.0,1.0/3.0}; + for( int i = 0; i<ops.length; i++ ) { + String expr = "x"+ops[i]; + assertEquals(expr,Double.toString(results[i]), + evaluate("f32 x = arg; return "+expr+";",args[i])); + assertEquals(expr,Double.toString((float)results[i]), + evaluate("f32 x = arg; f32 y = "+expr+"; return y;",args[i])); + } + } + + private static String evaluate(String src, long arg) { + CodeGen code = new CodeGen(src).parse().iter(); + return Eval2.eval(code,arg); + } + + @Test public void testMonotoneCompute() { + new CodeGen(""); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.TOP,Type.BOTTOM,TypeFloat.F32,TypeFloat.F64, + TypeFloat.F32.dual(),TypeFloat.F64.dual())); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,3.0,16777216.0,16777217.0, + Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + // Isolated analysis inputs; no peepholes can fold the tested nodes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + for( Node op : new Node[]{new AddFNode(lhs,rhs),new SubFNode(lhs,rhs), + new MulFNode(lhs,rhs),new DivFNode(lhs,rhs)} ) { + Type[][] results = new Type[inputs.size()][inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = op.compute(); + } + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<inputs.size(); k++ ) + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(op.label()+": "+inputs.get(i)+" -> "+inputs.get(j)+ + ", other="+inputs.get(k)+"; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } +} diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/AddFNode.java index fd713156..3b37dc84 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -14,10 +14,13 @@ public class AddFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/DivFNode.java index 149499f9..a0d95e06 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -14,10 +14,13 @@ public class DivFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 6a57f3c5..f24270cf 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -14,10 +14,13 @@ public class MulFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 2d218a03..4dbc141e 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -14,10 +14,13 @@ public class SubFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/chapter20/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java new file mode 100644 index 00000000..18ec2624 --- /dev/null +++ b/chapter20/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java @@ -0,0 +1,61 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FloatPrecisionTest { + @Test public void testFloatPrecision() { + String[] ops = {"+1.0","-1.0","*3.0","/3.0"}; + long[] args = {16777216,-16777216,16777215,1}; + double[] results = {16777217.0,-16777217.0,50331645.0,1.0/3.0}; + for( int i = 0; i<ops.length; i++ ) { + String expr = "x"+ops[i]; + assertEquals(expr,Double.toString(results[i]), + evaluate("f32 x = arg; return "+expr+";",args[i])); + assertEquals(expr,Double.toString((float)results[i]), + evaluate("f32 x = arg; f32 y = "+expr+"; return y;",args[i])); + } + } + + private static String evaluate(String src, long arg) { + CodeGen code = new CodeGen(src).parse().iter(); + return Eval2.eval(code,arg); + } + + @Test public void testMonotoneCompute() { + new CodeGen(""); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.TOP,Type.BOTTOM,TypeFloat.F32,TypeFloat.F64, + TypeFloat.F32.dual(),TypeFloat.F64.dual())); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,3.0,16777216.0,16777217.0, + Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + // Isolated analysis inputs; no peepholes can fold the tested nodes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + for( Node op : new Node[]{new AddFNode(lhs,rhs),new SubFNode(lhs,rhs), + new MulFNode(lhs,rhs),new DivFNode(lhs,rhs)} ) { + Type[][] results = new Type[inputs.size()][inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = op.compute(); + } + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<inputs.size(); k++ ) + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(op.label()+": "+inputs.get(i)+" -> "+inputs.get(j)+ + ", other="+inputs.get(k)+"; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } +} diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/AddFNode.java index fd713156..3b37dc84 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -14,10 +14,13 @@ public class AddFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/DivFNode.java index 149499f9..a0d95e06 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -14,10 +14,13 @@ public class DivFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 6a57f3c5..f24270cf 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -14,10 +14,13 @@ public class MulFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 2d218a03..4dbc141e 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -14,10 +14,13 @@ public class SubFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/chapter21/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java new file mode 100644 index 00000000..18ec2624 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java @@ -0,0 +1,61 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FloatPrecisionTest { + @Test public void testFloatPrecision() { + String[] ops = {"+1.0","-1.0","*3.0","/3.0"}; + long[] args = {16777216,-16777216,16777215,1}; + double[] results = {16777217.0,-16777217.0,50331645.0,1.0/3.0}; + for( int i = 0; i<ops.length; i++ ) { + String expr = "x"+ops[i]; + assertEquals(expr,Double.toString(results[i]), + evaluate("f32 x = arg; return "+expr+";",args[i])); + assertEquals(expr,Double.toString((float)results[i]), + evaluate("f32 x = arg; f32 y = "+expr+"; return y;",args[i])); + } + } + + private static String evaluate(String src, long arg) { + CodeGen code = new CodeGen(src).parse().iter(); + return Eval2.eval(code,arg); + } + + @Test public void testMonotoneCompute() { + new CodeGen(""); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.TOP,Type.BOTTOM,TypeFloat.F32,TypeFloat.F64, + TypeFloat.F32.dual(),TypeFloat.F64.dual())); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,3.0,16777216.0,16777217.0, + Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + // Isolated analysis inputs; no peepholes can fold the tested nodes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + for( Node op : new Node[]{new AddFNode(lhs,rhs),new SubFNode(lhs,rhs), + new MulFNode(lhs,rhs),new DivFNode(lhs,rhs)} ) { + Type[][] results = new Type[inputs.size()][inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = op.compute(); + } + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<inputs.size(); k++ ) + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(op.label()+": "+inputs.get(i)+" -> "+inputs.get(j)+ + ", other="+inputs.get(k)+"; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } +} diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/AddFNode.java index fd713156..3b37dc84 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -14,10 +14,13 @@ public class AddFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/DivFNode.java index 149499f9..a0d95e06 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -14,10 +14,13 @@ public class DivFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 6a57f3c5..f24270cf 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -14,10 +14,13 @@ public class MulFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 2d218a03..4dbc141e 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -14,10 +14,13 @@ public class SubFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/chapter22/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java new file mode 100644 index 00000000..b753ea79 --- /dev/null +++ b/chapter22/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java @@ -0,0 +1,61 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FloatPrecisionTest { + @Test public void testFloatPrecision() { + String[] ops = {"+1.0","-1.0","*3.0","/3.0"}; + long[] args = {16777216,-16777216,16777215,1}; + double[] results = {16777217.0,-16777217.0,50331645.0,1.0/3.0}; + for( int i = 0; i<ops.length; i++ ) { + String expr = "x"+ops[i]; + assertEquals(expr,Double.toString(results[i]), + evaluate("f32 x = arg; return "+expr+";",args[i])); + assertEquals(expr,Double.toString((float)results[i]), + evaluate("f32 x = arg; f32 y = "+expr+"; return y;",args[i])); + } + } + + private static String evaluate(String src, long arg) { + CodeGen code = new CodeGen(src).parse().iter().finalizeIR(); + return Eval2.eval(code,arg); + } + + @Test public void testMonotoneCompute() { + new CodeGen(""); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.TOP,Type.BOTTOM,TypeFloat.F32,TypeFloat.F64, + TypeFloat.F32.dual(),TypeFloat.F64.dual())); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,3.0,16777216.0,16777217.0, + Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + // Isolated analysis inputs; no peepholes can fold the tested nodes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + for( Node op : new Node[]{new AddFNode(lhs,rhs),new SubFNode(lhs,rhs), + new MulFNode(lhs,rhs),new DivFNode(lhs,rhs)} ) { + Type[][] results = new Type[inputs.size()][inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = op.compute(); + } + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<inputs.size(); k++ ) + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(op.label()+": "+inputs.get(i)+" -> "+inputs.get(j)+ + ", other="+inputs.get(k)+"; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } +} diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/AddFNode.java index fd713156..3b37dc84 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -14,10 +14,13 @@ public class AddFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/DivFNode.java index 149499f9..a0d95e06 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -14,10 +14,13 @@ public class DivFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/MulFNode.java index 6a57f3c5..f24270cf 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/MulFNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -14,10 +14,13 @@ public class MulFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 2d218a03..4dbc141e 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -14,10 +14,13 @@ public class SubFNode extends Node { @Override public Type compute() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return Type.TOP; 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()); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return in(1)._type.meet(in(2)._type); } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/chapter23/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java new file mode 100644 index 00000000..08902bb2 --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java @@ -0,0 +1,61 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FloatPrecisionTest { + @Test public void testFloatPrecision() { + String[] ops = {"+1.0","-1.0","*3.0","/3.0"}; + long[] args = {16777216,-16777216,16777215,1}; + double[] results = {16777217.0,-16777217.0,50331645.0,1.0/3.0}; + for( int i = 0; i<ops.length; i++ ) { + String expr = "x"+ops[i]; + assertEquals(expr,Double.toString(results[i]), + evaluate("f32 x = arg; return "+expr+";",args[i])); + assertEquals(expr,Double.toString((float)results[i]), + evaluate("f32 x = arg; f32 y = "+expr+"; return y;",args[i])); + } + } + + private static String evaluate(String src, long arg) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + return Eval2.eval(code,arg); + } + + @Test public void testMonotoneCompute() { + new CodeGen(""); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.TOP,Type.BOTTOM,TypeFloat.F32,TypeFloat.F64, + TypeFloat.F32.dual(),TypeFloat.F64.dual())); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,3.0,16777216.0,16777217.0, + Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + // Isolated analysis inputs; no peepholes can fold the tested nodes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + for( Node op : new Node[]{new AddFNode(lhs,rhs),new SubFNode(lhs,rhs), + new MulFNode(lhs,rhs),new DivFNode(lhs,rhs)} ) { + Type[][] results = new Type[inputs.size()][inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = op.compute(); + } + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<inputs.size(); k++ ) + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(op.label()+": "+inputs.get(i)+" -> "+inputs.get(j)+ + ", other="+inputs.get(k)+"; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } +} diff --git a/chapter24a/src/main/java/com/seaofnodes/simple/node/ArithFNode.java b/chapter24a/src/main/java/com/seaofnodes/simple/node/ArithFNode.java index dafba626..67743aa3 100644 --- a/chapter24a/src/main/java/com/seaofnodes/simple/node/ArithFNode.java +++ b/chapter24a/src/main/java/com/seaofnodes/simple/node/ArithFNode.java @@ -23,6 +23,8 @@ public abstract class ArithFNode extends Node { t2 instanceof TypeFloat f2 ) { if( f1.isConstant() && f2.isConstant() ) return TypeFloat.constant(doOp(f1.value(),f2.value())); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return t1.meet(t2); } diff --git a/chapter24a/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/chapter24a/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java new file mode 100644 index 00000000..08902bb2 --- /dev/null +++ b/chapter24a/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java @@ -0,0 +1,61 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FloatPrecisionTest { + @Test public void testFloatPrecision() { + String[] ops = {"+1.0","-1.0","*3.0","/3.0"}; + long[] args = {16777216,-16777216,16777215,1}; + double[] results = {16777217.0,-16777217.0,50331645.0,1.0/3.0}; + for( int i = 0; i<ops.length; i++ ) { + String expr = "x"+ops[i]; + assertEquals(expr,Double.toString(results[i]), + evaluate("f32 x = arg; return "+expr+";",args[i])); + assertEquals(expr,Double.toString((float)results[i]), + evaluate("f32 x = arg; f32 y = "+expr+"; return y;",args[i])); + } + } + + private static String evaluate(String src, long arg) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + return Eval2.eval(code,arg); + } + + @Test public void testMonotoneCompute() { + new CodeGen(""); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.TOP,Type.BOTTOM,TypeFloat.F32,TypeFloat.F64, + TypeFloat.F32.dual(),TypeFloat.F64.dual())); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,3.0,16777216.0,16777217.0, + Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + // Isolated analysis inputs; no peepholes can fold the tested nodes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + for( Node op : new Node[]{new AddFNode(lhs,rhs),new SubFNode(lhs,rhs), + new MulFNode(lhs,rhs),new DivFNode(lhs,rhs)} ) { + Type[][] results = new Type[inputs.size()][inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = op.compute(); + } + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<inputs.size(); k++ ) + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(op.label()+": "+inputs.get(i)+" -> "+inputs.get(j)+ + ", other="+inputs.get(k)+"; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } +} diff --git a/chapter24b/src/main/java/com/seaofnodes/simple/node/ArithFNode.java b/chapter24b/src/main/java/com/seaofnodes/simple/node/ArithFNode.java index dafba626..67743aa3 100644 --- a/chapter24b/src/main/java/com/seaofnodes/simple/node/ArithFNode.java +++ b/chapter24b/src/main/java/com/seaofnodes/simple/node/ArithFNode.java @@ -23,6 +23,8 @@ public abstract class ArithFNode extends Node { t2 instanceof TypeFloat f2 ) { if( f1.isConstant() && f2.isConstant() ) return TypeFloat.constant(doOp(f1.value(),f2.value())); + // Two f32 inputs can still produce a result needing f64 precision. + return TypeFloat.F64; } return t1.meet(t2); } diff --git a/chapter24b/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/chapter24b/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java new file mode 100644 index 00000000..08902bb2 --- /dev/null +++ b/chapter24b/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java @@ -0,0 +1,61 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FloatPrecisionTest { + @Test public void testFloatPrecision() { + String[] ops = {"+1.0","-1.0","*3.0","/3.0"}; + long[] args = {16777216,-16777216,16777215,1}; + double[] results = {16777217.0,-16777217.0,50331645.0,1.0/3.0}; + for( int i = 0; i<ops.length; i++ ) { + String expr = "x"+ops[i]; + assertEquals(expr,Double.toString(results[i]), + evaluate("f32 x = arg; return "+expr+";",args[i])); + assertEquals(expr,Double.toString((float)results[i]), + evaluate("f32 x = arg; f32 y = "+expr+"; return y;",args[i])); + } + } + + private static String evaluate(String src, long arg) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + return Eval2.eval(code,arg); + } + + @Test public void testMonotoneCompute() { + new CodeGen(""); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.TOP,Type.BOTTOM,TypeFloat.F32,TypeFloat.F64, + TypeFloat.F32.dual(),TypeFloat.F64.dual())); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,3.0,16777216.0,16777217.0, + Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + // Isolated analysis inputs; no peepholes can fold the tested nodes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + for( Node op : new Node[]{new AddFNode(lhs,rhs),new SubFNode(lhs,rhs), + new MulFNode(lhs,rhs),new DivFNode(lhs,rhs)} ) { + Type[][] results = new Type[inputs.size()][inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = op.compute(); + } + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<inputs.size(); k++ ) + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(op.label()+": "+inputs.get(i)+" -> "+inputs.get(j)+ + ", other="+inputs.get(k)+"; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } +} diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ArithNode.java index 5f0862b2..bdd918fd 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -106,12 +106,16 @@ public abstract class ArithNode extends Node implements ModeNode { @Override public final Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; + // Constant array payloads lie below their element ranges in the lattice. + if( t1 instanceof TypeConAry ary ) t1 = ary.elem(); + if( t2 instanceof TypeConAry ary ) t2 = ary.elem(); if( t1==null || t2==null ) return Type.TOP; if( t1.isHigh() || t2.isHigh() ) return Type.TOP; - if( t1==Type.BOTTOM || t2==Type.BOTTOM ) return Type.BOTTOM; + // Without numeric inputs, stay below both possible result families. + // Pointer modes belong to comparisons, not arithmetic. + if( !(t1 instanceof TypeInteger || t1 instanceof TypeFloat) || + !(t2 instanceof TypeInteger || t2 instanceof TypeFloat) ) return Type.BOTTOM; byte mode = _mode==0 ? mode(t1,t2) : _mode; - if( mode==0 ) - return CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() ? Type.BOTTOM : Type.TOP; if( mode==1 ) { if( t1 instanceof TypeInteger x && t2 instanceof TypeInteger y ) @@ -121,12 +125,10 @@ public abstract class ArithNode extends Node implements ModeNode { return TypeInteger.BOT; } // FP handling - if( t1 instanceof TypeFloat f1 && - t2 instanceof TypeFloat f2 ) { - if( f1.isConstant() && f2.isConstant() ) - return TypeFloat.constant(doOp(f1.value(),f2.value())); - return t1.meet(t2); - } + if( t1 instanceof TypeFloat f1 && t2 instanceof TypeFloat f2 && + f1.isConstant() && f2.isConstant() ) + return TypeFloat.constant(doOp(f1.value(),f2.value())); + // Two f32 inputs can still produce a result needing f64 precision. return TypeFloat.F64; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ConvertNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ConvertNode.java index c5be0123..7e527de2 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ConvertNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ConvertNode.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; import java.util.HashMap; @@ -29,14 +28,15 @@ public class ConvertNode extends Node { return p.p(label()).open().n(val()).close(); } - // The declaration fixes the result family during pessimistic parsing. - // From SCCP onward, preserve dead inputs and stronger facts in that family. + // The declaration bounds the result; preserve dead inputs and stronger + // scalar facts so SCCP can propagate constants through loop conversions. + // Managed pointers keep the declared type until idealize checks access: + // array element access must agree in both directions, so it cannot gate + // precision in this monotone transfer function. @Override public Type compute() { Type src = val()._type; - if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() ) { - if( src.isHigh() ) return Type.TOP; - if( (src.isa(_dst) && src.accessISA(_dst)) ) return src; - } + if( src.isHigh() ) return Type.TOP; + if( !(_dst instanceof TypeMemPtr) && src.isa(_dst) ) return src; return _dst; } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/ArithNodeTest.java b/chapter25/src/test/java/com/seaofnodes/simple/ArithNodeTest.java new file mode 100644 index 00000000..708c32a2 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/ArithNodeTest.java @@ -0,0 +1,96 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ArithNodeTest { + @Test public void testUnresolvedInput() { + new CodeGen("return 0;").driver(CodeGen.Phase.Opto); + Node lhs = new ConstantNode(TypeInteger.TRUE); + Node rhs = new ConstantNode(TypeInteger.TRUE); + ArithNode add = new AddNode(lhs,rhs); + assertSame(TypeInteger.constant(2),add.compute()); + lhs._type = TypeScalar.BOT; + assertSame(Type.BOTTOM,add.compute()); + add.setMode((byte)1); + assertSame(Type.BOTTOM,add.compute()); + } + + @Test public void testFloatPrecision() { + CodeGen code = new CodeGen("f32 x = arg; return x+1.0;").driver(CodeGen.Phase.TypeCheck); + assertEquals("1.6777217E7",Eval2.eval(code,16777216)); + code = new CodeGen("f32 x = arg; f32 y = x+1.0; return y;").driver(CodeGen.Phase.TypeCheck); + assertEquals("1.6777216E7",Eval2.eval(code,16777216)); + } + + @Test public void testMonotoneCompute() { + CodeGen code = new CodeGen("return 0;"); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.BOTTOM,Type.CONTROL,Type.NIL,TypeScalar.BOT,TypeMem.BOT)); + TypeInteger.gather(inputs); + TypeFloat.gather(inputs); + TypePtr.gather(inputs); + TypeMemPtr.gather(inputs); + TypeFunPtr.gather(inputs); + inputs.add(TypeConAryB.make(new byte[]{1,2,3})); + for( long value : new long[]{Long.MIN_VALUE,Long.MIN_VALUE+1,-1,1,Long.MAX_VALUE} ) + inputs.add(TypeInteger.constant(value)); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,16777216.0,16777217.0,Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + int size = inputs.size(); + for( int i = 0; i<size; i++ ) inputs.add(inputs.get(i).dual()); + size = inputs.size(); + + // Isolated inputs let us vary types without peepholes settling modes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + lhs.setDef(0,null); + rhs.setDef(0,null); + ArrayList<ArithNode> ops = new ArrayList<>(); + for( byte mode = 0; mode<3; mode++ ) { + ops.add(new AddNode(lhs,rhs,mode)); + ops.add(new SubNode(lhs,rhs,mode)); + ops.add(new MulNode(lhs,rhs,mode)); + ops.add(new DivNode(lhs,rhs,mode)); + } + ops.add(new AndNode(null,lhs,rhs)); + ops.add(new OrNode(null,lhs,rhs)); + ops.add(new XorNode(null,lhs,rhs)); + ops.add(new ShlNode(null,lhs,rhs)); + ops.add(new SarNode(null,lhs,rhs)); + ops.add(new ShrNode(null,lhs,rhs)); + Type[][][] expected = new Type[ops.size()][size][size]; + for( CodeGen.Phase phase : new CodeGen.Phase[]{CodeGen.Phase.Parse,CodeGen.Phase.Iter,CodeGen.Phase.Opto,CodeGen.Phase.IterPostOpto} ) { + code.driver(phase); + for( int op = 0; op<ops.size(); op++ ) { + ArithNode arith = ops.get(op); + Type[][] results = new Type[size][size]; + for( int i = 0; i<size; i++ ) + for( int j = 0; j<size; j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = arith.compute(); + if( phase==CodeGen.Phase.Parse ) expected[op][i][j] = results[i][j]; + else assertSame("Phase changed compute",expected[op][i][j],results[i][j]); + } + // Check the order relation in each argument independently. + // This covers both falling SCCP types and rising Iter types. + for( int i = 0; i<size; i++ ) + for( int j = 0; j<size; j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<size; k++ ) { + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(arith.getClass().getSimpleName()+" mode="+arith.mode()+": "+ + inputs.get(i)+" -> "+inputs.get(j)+", other="+inputs.get(k)+ + "; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } + } + } +} diff --git a/chapter25/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java b/chapter25/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java new file mode 100644 index 00000000..2342b33a --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java @@ -0,0 +1,69 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.ConvertNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.*; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ConvertNodeTest { + @Test public void testMonotoneCompute() { + CodeGen code = new CodeGen("return 0;"); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.BOTTOM,Type.CONTROL,Type.NIL,TypeScalar.BOT,TypeMem.BOT)); + TypeInteger.gather(inputs); + TypeFloat.gather(inputs); + TypePtr.gather(inputs); + TypeMemPtr.gather(inputs); + TypeFunPtr.gather(inputs); + // Writable arrays require matching element access in both directions. + // Widening the element's access can make that check pass while keeping + // a known length; compute must not suddenly gain that length fact. + for( TypeInteger len : new TypeInteger[]{TypeInteger.U32,TypeInteger.TRUE} ) + for( boolean elementRO : new boolean[]{false,true} ) + for( boolean arrayRO : new boolean[]{false,true} ) + inputs.add(TypeMemPtr.make(TypeStruct.makeAry("[]test",len,-1, + TypeMemPtr.TEST.withAccess(elementRO),-2,false)).withAccess(arrayRO)); + inputs.add(TypeConAryB.make(new byte[]{1,2,3})); + for( long value : new long[]{Long.MIN_VALUE,-129,-128,-1,0,1,127,128,255,256,Long.MAX_VALUE} ) + inputs.add(TypeInteger.constant(value)); + for( double value : new double[]{-0.0,0.0,1.0,16777217.0,Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + int size = inputs.size(); + for( int i = 0; i<size; i++ ) inputs.add(inputs.get(i).dual()); + + ArrayList<Type> destinations = new ArrayList<>(); + for( Type t : inputs ) + if( !t.isHigh() && (t instanceof TypeInteger || t instanceof TypeFloat || t instanceof TypeNil) ) + destinations.add(t); + + // Vary one isolated input without folding or lowering the conversion. + Node input = new ConstantNode(Type.BOTTOM); + input.setDef(0,null); + Type[][] expected = new Type[destinations.size()][inputs.size()]; + for( CodeGen.Phase phase : new CodeGen.Phase[]{CodeGen.Phase.Parse,CodeGen.Phase.Iter,CodeGen.Phase.Opto,CodeGen.Phase.IterPostOpto} ) { + code.driver(phase); + for( int d = 0; d<destinations.size(); d++ ) { + Type dst = destinations.get(d); + ConvertNode convert = new ConvertNode(dst,input); + Type[] results = new Type[inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) { + input._type = inputs.get(i); + results[i] = convert.compute(); + if( phase==CodeGen.Phase.Parse ) expected[d][i] = results[i]; + else assertSame("Phase changed compute for "+inputs.get(i)+" to "+dst,expected[d][i],results[i]); + } + // Check both rising Iter and falling SCCP with the same order. + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) && !results[i].isa(results[j]) ) + fail("Convert to "+dst+": "+inputs.get(i)+" -> "+inputs.get(j)+ + " gave "+results[i]+" -> "+results[j]); + } + } + } +} diff --git a/chapter26/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/chapter26/src/main/java/com/seaofnodes/simple/node/ArithNode.java index 5f0862b2..bdd918fd 100644 --- a/chapter26/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/chapter26/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -106,12 +106,16 @@ public abstract class ArithNode extends Node implements ModeNode { @Override public final Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; + // Constant array payloads lie below their element ranges in the lattice. + if( t1 instanceof TypeConAry ary ) t1 = ary.elem(); + if( t2 instanceof TypeConAry ary ) t2 = ary.elem(); if( t1==null || t2==null ) return Type.TOP; if( t1.isHigh() || t2.isHigh() ) return Type.TOP; - if( t1==Type.BOTTOM || t2==Type.BOTTOM ) return Type.BOTTOM; + // Without numeric inputs, stay below both possible result families. + // Pointer modes belong to comparisons, not arithmetic. + if( !(t1 instanceof TypeInteger || t1 instanceof TypeFloat) || + !(t2 instanceof TypeInteger || t2 instanceof TypeFloat) ) return Type.BOTTOM; byte mode = _mode==0 ? mode(t1,t2) : _mode; - if( mode==0 ) - return CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() ? Type.BOTTOM : Type.TOP; if( mode==1 ) { if( t1 instanceof TypeInteger x && t2 instanceof TypeInteger y ) @@ -121,12 +125,10 @@ public abstract class ArithNode extends Node implements ModeNode { return TypeInteger.BOT; } // FP handling - if( t1 instanceof TypeFloat f1 && - t2 instanceof TypeFloat f2 ) { - if( f1.isConstant() && f2.isConstant() ) - return TypeFloat.constant(doOp(f1.value(),f2.value())); - return t1.meet(t2); - } + if( t1 instanceof TypeFloat f1 && t2 instanceof TypeFloat f2 && + f1.isConstant() && f2.isConstant() ) + return TypeFloat.constant(doOp(f1.value(),f2.value())); + // Two f32 inputs can still produce a result needing f64 precision. return TypeFloat.F64; } diff --git a/chapter26/src/main/java/com/seaofnodes/simple/node/ConvertNode.java b/chapter26/src/main/java/com/seaofnodes/simple/node/ConvertNode.java index c5be0123..7e527de2 100644 --- a/chapter26/src/main/java/com/seaofnodes/simple/node/ConvertNode.java +++ b/chapter26/src/main/java/com/seaofnodes/simple/node/ConvertNode.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; import java.util.HashMap; @@ -29,14 +28,15 @@ public class ConvertNode extends Node { return p.p(label()).open().n(val()).close(); } - // The declaration fixes the result family during pessimistic parsing. - // From SCCP onward, preserve dead inputs and stronger facts in that family. + // The declaration bounds the result; preserve dead inputs and stronger + // scalar facts so SCCP can propagate constants through loop conversions. + // Managed pointers keep the declared type until idealize checks access: + // array element access must agree in both directions, so it cannot gate + // precision in this monotone transfer function. @Override public Type compute() { Type src = val()._type; - if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() ) { - if( src.isHigh() ) return Type.TOP; - if( (src.isa(_dst) && src.accessISA(_dst)) ) return src; - } + if( src.isHigh() ) return Type.TOP; + if( !(_dst instanceof TypeMemPtr) && src.isa(_dst) ) return src; return _dst; } diff --git a/chapter26/src/test/java/com/seaofnodes/simple/ArithNodeTest.java b/chapter26/src/test/java/com/seaofnodes/simple/ArithNodeTest.java new file mode 100644 index 00000000..708c32a2 --- /dev/null +++ b/chapter26/src/test/java/com/seaofnodes/simple/ArithNodeTest.java @@ -0,0 +1,96 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ArithNodeTest { + @Test public void testUnresolvedInput() { + new CodeGen("return 0;").driver(CodeGen.Phase.Opto); + Node lhs = new ConstantNode(TypeInteger.TRUE); + Node rhs = new ConstantNode(TypeInteger.TRUE); + ArithNode add = new AddNode(lhs,rhs); + assertSame(TypeInteger.constant(2),add.compute()); + lhs._type = TypeScalar.BOT; + assertSame(Type.BOTTOM,add.compute()); + add.setMode((byte)1); + assertSame(Type.BOTTOM,add.compute()); + } + + @Test public void testFloatPrecision() { + CodeGen code = new CodeGen("f32 x = arg; return x+1.0;").driver(CodeGen.Phase.TypeCheck); + assertEquals("1.6777217E7",Eval2.eval(code,16777216)); + code = new CodeGen("f32 x = arg; f32 y = x+1.0; return y;").driver(CodeGen.Phase.TypeCheck); + assertEquals("1.6777216E7",Eval2.eval(code,16777216)); + } + + @Test public void testMonotoneCompute() { + CodeGen code = new CodeGen("return 0;"); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.BOTTOM,Type.CONTROL,Type.NIL,TypeScalar.BOT,TypeMem.BOT)); + TypeInteger.gather(inputs); + TypeFloat.gather(inputs); + TypePtr.gather(inputs); + TypeMemPtr.gather(inputs); + TypeFunPtr.gather(inputs); + inputs.add(TypeConAryB.make(new byte[]{1,2,3})); + for( long value : new long[]{Long.MIN_VALUE,Long.MIN_VALUE+1,-1,1,Long.MAX_VALUE} ) + inputs.add(TypeInteger.constant(value)); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,16777216.0,16777217.0,Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + int size = inputs.size(); + for( int i = 0; i<size; i++ ) inputs.add(inputs.get(i).dual()); + size = inputs.size(); + + // Isolated inputs let us vary types without peepholes settling modes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + lhs.setDef(0,null); + rhs.setDef(0,null); + ArrayList<ArithNode> ops = new ArrayList<>(); + for( byte mode = 0; mode<3; mode++ ) { + ops.add(new AddNode(lhs,rhs,mode)); + ops.add(new SubNode(lhs,rhs,mode)); + ops.add(new MulNode(lhs,rhs,mode)); + ops.add(new DivNode(lhs,rhs,mode)); + } + ops.add(new AndNode(null,lhs,rhs)); + ops.add(new OrNode(null,lhs,rhs)); + ops.add(new XorNode(null,lhs,rhs)); + ops.add(new ShlNode(null,lhs,rhs)); + ops.add(new SarNode(null,lhs,rhs)); + ops.add(new ShrNode(null,lhs,rhs)); + Type[][][] expected = new Type[ops.size()][size][size]; + for( CodeGen.Phase phase : new CodeGen.Phase[]{CodeGen.Phase.Parse,CodeGen.Phase.Iter,CodeGen.Phase.Opto,CodeGen.Phase.IterPostOpto} ) { + code.driver(phase); + for( int op = 0; op<ops.size(); op++ ) { + ArithNode arith = ops.get(op); + Type[][] results = new Type[size][size]; + for( int i = 0; i<size; i++ ) + for( int j = 0; j<size; j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = arith.compute(); + if( phase==CodeGen.Phase.Parse ) expected[op][i][j] = results[i][j]; + else assertSame("Phase changed compute",expected[op][i][j],results[i][j]); + } + // Check the order relation in each argument independently. + // This covers both falling SCCP types and rising Iter types. + for( int i = 0; i<size; i++ ) + for( int j = 0; j<size; j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<size; k++ ) { + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(arith.getClass().getSimpleName()+" mode="+arith.mode()+": "+ + inputs.get(i)+" -> "+inputs.get(j)+", other="+inputs.get(k)+ + "; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } + } + } +} diff --git a/chapter26/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java b/chapter26/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java new file mode 100644 index 00000000..2342b33a --- /dev/null +++ b/chapter26/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java @@ -0,0 +1,69 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.ConvertNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.*; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ConvertNodeTest { + @Test public void testMonotoneCompute() { + CodeGen code = new CodeGen("return 0;"); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.BOTTOM,Type.CONTROL,Type.NIL,TypeScalar.BOT,TypeMem.BOT)); + TypeInteger.gather(inputs); + TypeFloat.gather(inputs); + TypePtr.gather(inputs); + TypeMemPtr.gather(inputs); + TypeFunPtr.gather(inputs); + // Writable arrays require matching element access in both directions. + // Widening the element's access can make that check pass while keeping + // a known length; compute must not suddenly gain that length fact. + for( TypeInteger len : new TypeInteger[]{TypeInteger.U32,TypeInteger.TRUE} ) + for( boolean elementRO : new boolean[]{false,true} ) + for( boolean arrayRO : new boolean[]{false,true} ) + inputs.add(TypeMemPtr.make(TypeStruct.makeAry("[]test",len,-1, + TypeMemPtr.TEST.withAccess(elementRO),-2,false)).withAccess(arrayRO)); + inputs.add(TypeConAryB.make(new byte[]{1,2,3})); + for( long value : new long[]{Long.MIN_VALUE,-129,-128,-1,0,1,127,128,255,256,Long.MAX_VALUE} ) + inputs.add(TypeInteger.constant(value)); + for( double value : new double[]{-0.0,0.0,1.0,16777217.0,Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + int size = inputs.size(); + for( int i = 0; i<size; i++ ) inputs.add(inputs.get(i).dual()); + + ArrayList<Type> destinations = new ArrayList<>(); + for( Type t : inputs ) + if( !t.isHigh() && (t instanceof TypeInteger || t instanceof TypeFloat || t instanceof TypeNil) ) + destinations.add(t); + + // Vary one isolated input without folding or lowering the conversion. + Node input = new ConstantNode(Type.BOTTOM); + input.setDef(0,null); + Type[][] expected = new Type[destinations.size()][inputs.size()]; + for( CodeGen.Phase phase : new CodeGen.Phase[]{CodeGen.Phase.Parse,CodeGen.Phase.Iter,CodeGen.Phase.Opto,CodeGen.Phase.IterPostOpto} ) { + code.driver(phase); + for( int d = 0; d<destinations.size(); d++ ) { + Type dst = destinations.get(d); + ConvertNode convert = new ConvertNode(dst,input); + Type[] results = new Type[inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) { + input._type = inputs.get(i); + results[i] = convert.compute(); + if( phase==CodeGen.Phase.Parse ) expected[d][i] = results[i]; + else assertSame("Phase changed compute for "+inputs.get(i)+" to "+dst,expected[d][i],results[i]); + } + // Check both rising Iter and falling SCCP with the same order. + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) && !results[i].isa(results[j]) ) + fail("Convert to "+dst+": "+inputs.get(i)+" -> "+inputs.get(j)+ + " gave "+results[i]+" -> "+results[j]); + } + } + } +} diff --git a/chapter27/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/chapter27/src/main/java/com/seaofnodes/simple/node/ArithNode.java index 5f0862b2..bdd918fd 100644 --- a/chapter27/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/chapter27/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -106,12 +106,16 @@ public abstract class ArithNode extends Node implements ModeNode { @Override public final Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; + // Constant array payloads lie below their element ranges in the lattice. + if( t1 instanceof TypeConAry ary ) t1 = ary.elem(); + if( t2 instanceof TypeConAry ary ) t2 = ary.elem(); if( t1==null || t2==null ) return Type.TOP; if( t1.isHigh() || t2.isHigh() ) return Type.TOP; - if( t1==Type.BOTTOM || t2==Type.BOTTOM ) return Type.BOTTOM; + // Without numeric inputs, stay below both possible result families. + // Pointer modes belong to comparisons, not arithmetic. + if( !(t1 instanceof TypeInteger || t1 instanceof TypeFloat) || + !(t2 instanceof TypeInteger || t2 instanceof TypeFloat) ) return Type.BOTTOM; byte mode = _mode==0 ? mode(t1,t2) : _mode; - if( mode==0 ) - return CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() ? Type.BOTTOM : Type.TOP; if( mode==1 ) { if( t1 instanceof TypeInteger x && t2 instanceof TypeInteger y ) @@ -121,12 +125,10 @@ public abstract class ArithNode extends Node implements ModeNode { return TypeInteger.BOT; } // FP handling - if( t1 instanceof TypeFloat f1 && - t2 instanceof TypeFloat f2 ) { - if( f1.isConstant() && f2.isConstant() ) - return TypeFloat.constant(doOp(f1.value(),f2.value())); - return t1.meet(t2); - } + if( t1 instanceof TypeFloat f1 && t2 instanceof TypeFloat f2 && + f1.isConstant() && f2.isConstant() ) + return TypeFloat.constant(doOp(f1.value(),f2.value())); + // Two f32 inputs can still produce a result needing f64 precision. return TypeFloat.F64; } diff --git a/chapter27/src/main/java/com/seaofnodes/simple/node/ConvertNode.java b/chapter27/src/main/java/com/seaofnodes/simple/node/ConvertNode.java index c5be0123..7e527de2 100644 --- a/chapter27/src/main/java/com/seaofnodes/simple/node/ConvertNode.java +++ b/chapter27/src/main/java/com/seaofnodes/simple/node/ConvertNode.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; import java.util.HashMap; @@ -29,14 +28,15 @@ public class ConvertNode extends Node { return p.p(label()).open().n(val()).close(); } - // The declaration fixes the result family during pessimistic parsing. - // From SCCP onward, preserve dead inputs and stronger facts in that family. + // The declaration bounds the result; preserve dead inputs and stronger + // scalar facts so SCCP can propagate constants through loop conversions. + // Managed pointers keep the declared type until idealize checks access: + // array element access must agree in both directions, so it cannot gate + // precision in this monotone transfer function. @Override public Type compute() { Type src = val()._type; - if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() ) { - if( src.isHigh() ) return Type.TOP; - if( (src.isa(_dst) && src.accessISA(_dst)) ) return src; - } + if( src.isHigh() ) return Type.TOP; + if( !(_dst instanceof TypeMemPtr) && src.isa(_dst) ) return src; return _dst; } diff --git a/chapter27/src/test/java/com/seaofnodes/simple/ArithNodeTest.java b/chapter27/src/test/java/com/seaofnodes/simple/ArithNodeTest.java new file mode 100644 index 00000000..708c32a2 --- /dev/null +++ b/chapter27/src/test/java/com/seaofnodes/simple/ArithNodeTest.java @@ -0,0 +1,96 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ArithNodeTest { + @Test public void testUnresolvedInput() { + new CodeGen("return 0;").driver(CodeGen.Phase.Opto); + Node lhs = new ConstantNode(TypeInteger.TRUE); + Node rhs = new ConstantNode(TypeInteger.TRUE); + ArithNode add = new AddNode(lhs,rhs); + assertSame(TypeInteger.constant(2),add.compute()); + lhs._type = TypeScalar.BOT; + assertSame(Type.BOTTOM,add.compute()); + add.setMode((byte)1); + assertSame(Type.BOTTOM,add.compute()); + } + + @Test public void testFloatPrecision() { + CodeGen code = new CodeGen("f32 x = arg; return x+1.0;").driver(CodeGen.Phase.TypeCheck); + assertEquals("1.6777217E7",Eval2.eval(code,16777216)); + code = new CodeGen("f32 x = arg; f32 y = x+1.0; return y;").driver(CodeGen.Phase.TypeCheck); + assertEquals("1.6777216E7",Eval2.eval(code,16777216)); + } + + @Test public void testMonotoneCompute() { + CodeGen code = new CodeGen("return 0;"); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.BOTTOM,Type.CONTROL,Type.NIL,TypeScalar.BOT,TypeMem.BOT)); + TypeInteger.gather(inputs); + TypeFloat.gather(inputs); + TypePtr.gather(inputs); + TypeMemPtr.gather(inputs); + TypeFunPtr.gather(inputs); + inputs.add(TypeConAryB.make(new byte[]{1,2,3})); + for( long value : new long[]{Long.MIN_VALUE,Long.MIN_VALUE+1,-1,1,Long.MAX_VALUE} ) + inputs.add(TypeInteger.constant(value)); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,16777216.0,16777217.0,Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + int size = inputs.size(); + for( int i = 0; i<size; i++ ) inputs.add(inputs.get(i).dual()); + size = inputs.size(); + + // Isolated inputs let us vary types without peepholes settling modes. + Node lhs = new ConstantNode(Type.BOTTOM); + Node rhs = new ConstantNode(Type.BOTTOM); + lhs.setDef(0,null); + rhs.setDef(0,null); + ArrayList<ArithNode> ops = new ArrayList<>(); + for( byte mode = 0; mode<3; mode++ ) { + ops.add(new AddNode(lhs,rhs,mode)); + ops.add(new SubNode(lhs,rhs,mode)); + ops.add(new MulNode(lhs,rhs,mode)); + ops.add(new DivNode(lhs,rhs,mode)); + } + ops.add(new AndNode(null,lhs,rhs)); + ops.add(new OrNode(null,lhs,rhs)); + ops.add(new XorNode(null,lhs,rhs)); + ops.add(new ShlNode(null,lhs,rhs)); + ops.add(new SarNode(null,lhs,rhs)); + ops.add(new ShrNode(null,lhs,rhs)); + Type[][][] expected = new Type[ops.size()][size][size]; + for( CodeGen.Phase phase : new CodeGen.Phase[]{CodeGen.Phase.Parse,CodeGen.Phase.Iter,CodeGen.Phase.Opto,CodeGen.Phase.IterPostOpto} ) { + code.driver(phase); + for( int op = 0; op<ops.size(); op++ ) { + ArithNode arith = ops.get(op); + Type[][] results = new Type[size][size]; + for( int i = 0; i<size; i++ ) + for( int j = 0; j<size; j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = arith.compute(); + if( phase==CodeGen.Phase.Parse ) expected[op][i][j] = results[i][j]; + else assertSame("Phase changed compute",expected[op][i][j],results[i][j]); + } + // Check the order relation in each argument independently. + // This covers both falling SCCP types and rising Iter types. + for( int i = 0; i<size; i++ ) + for( int j = 0; j<size; j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<size; k++ ) { + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(arith.getClass().getSimpleName()+" mode="+arith.mode()+": "+ + inputs.get(i)+" -> "+inputs.get(j)+", other="+inputs.get(k)+ + "; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } + } + } +} diff --git a/chapter27/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java b/chapter27/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java new file mode 100644 index 00000000..2342b33a --- /dev/null +++ b/chapter27/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java @@ -0,0 +1,69 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.ConvertNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.*; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ConvertNodeTest { + @Test public void testMonotoneCompute() { + CodeGen code = new CodeGen("return 0;"); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.BOTTOM,Type.CONTROL,Type.NIL,TypeScalar.BOT,TypeMem.BOT)); + TypeInteger.gather(inputs); + TypeFloat.gather(inputs); + TypePtr.gather(inputs); + TypeMemPtr.gather(inputs); + TypeFunPtr.gather(inputs); + // Writable arrays require matching element access in both directions. + // Widening the element's access can make that check pass while keeping + // a known length; compute must not suddenly gain that length fact. + for( TypeInteger len : new TypeInteger[]{TypeInteger.U32,TypeInteger.TRUE} ) + for( boolean elementRO : new boolean[]{false,true} ) + for( boolean arrayRO : new boolean[]{false,true} ) + inputs.add(TypeMemPtr.make(TypeStruct.makeAry("[]test",len,-1, + TypeMemPtr.TEST.withAccess(elementRO),-2,false)).withAccess(arrayRO)); + inputs.add(TypeConAryB.make(new byte[]{1,2,3})); + for( long value : new long[]{Long.MIN_VALUE,-129,-128,-1,0,1,127,128,255,256,Long.MAX_VALUE} ) + inputs.add(TypeInteger.constant(value)); + for( double value : new double[]{-0.0,0.0,1.0,16777217.0,Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + int size = inputs.size(); + for( int i = 0; i<size; i++ ) inputs.add(inputs.get(i).dual()); + + ArrayList<Type> destinations = new ArrayList<>(); + for( Type t : inputs ) + if( !t.isHigh() && (t instanceof TypeInteger || t instanceof TypeFloat || t instanceof TypeNil) ) + destinations.add(t); + + // Vary one isolated input without folding or lowering the conversion. + Node input = new ConstantNode(Type.BOTTOM); + input.setDef(0,null); + Type[][] expected = new Type[destinations.size()][inputs.size()]; + for( CodeGen.Phase phase : new CodeGen.Phase[]{CodeGen.Phase.Parse,CodeGen.Phase.Iter,CodeGen.Phase.Opto,CodeGen.Phase.IterPostOpto} ) { + code.driver(phase); + for( int d = 0; d<destinations.size(); d++ ) { + Type dst = destinations.get(d); + ConvertNode convert = new ConvertNode(dst,input); + Type[] results = new Type[inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) { + input._type = inputs.get(i); + results[i] = convert.compute(); + if( phase==CodeGen.Phase.Parse ) expected[d][i] = results[i]; + else assertSame("Phase changed compute for "+inputs.get(i)+" to "+dst,expected[d][i],results[i]); + } + // Check both rising Iter and falling SCCP with the same order. + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) && !results[i].isa(results[j]) ) + fail("Convert to "+dst+": "+inputs.get(i)+" -> "+inputs.get(j)+ + " gave "+results[i]+" -> "+results[j]); + } + } + } +} diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/ArithNode.java index 094b927f..8d5f36eb 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -108,12 +108,16 @@ public abstract class ArithNode extends Node implements ModeNode { @Override public final Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; + // Constant array payloads lie below their element ranges in the lattice. + if( t1 instanceof TypeConAry ary ) t1 = ary.elem(); + if( t2 instanceof TypeConAry ary ) t2 = ary.elem(); if( t1==null || t2==null ) return Type.TOP; if( t1.isHigh() || t2.isHigh() ) return Type.TOP; - if( t1==Type.BOTTOM || t2==Type.BOTTOM ) return Type.BOTTOM; + // Without numeric inputs, stay below both possible result families. + // Pointer modes belong to comparisons, not arithmetic. + if( !(t1 instanceof TypeInteger || t1 instanceof TypeFloat) || + !(t2 instanceof TypeInteger || t2 instanceof TypeFloat) ) return Type.BOTTOM; byte mode = _mode==0 ? mode(t1,t2) : _mode; - if( mode==0 ) - return CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() ? Type.BOTTOM : Type.TOP; if( mode==1 ) { if( t1 instanceof TypeInteger x && t2 instanceof TypeInteger y ) @@ -123,12 +127,10 @@ public abstract class ArithNode extends Node implements ModeNode { return TypeInteger.BOT; } // FP handling - if( t1 instanceof TypeFloat f1 && - t2 instanceof TypeFloat f2 ) { - if( f1.isConstant() && f2.isConstant() ) - return TypeFloat.constant(doOp(f1.value(),f2.value())); - return t1.meet(t2); - } + if( t1 instanceof TypeFloat f1 && t2 instanceof TypeFloat f2 && + f1.isConstant() && f2.isConstant() ) + return TypeFloat.constant(doOp(f1.value(),f2.value())); + // Two f32 inputs can still produce a result needing f64 precision. return TypeFloat.F64; } diff --git a/chapter28a/src/main/java/com/seaofnodes/simple/node/ConvertNode.java b/chapter28a/src/main/java/com/seaofnodes/simple/node/ConvertNode.java index cdc890a7..078c50ec 100644 --- a/chapter28a/src/main/java/com/seaofnodes/simple/node/ConvertNode.java +++ b/chapter28a/src/main/java/com/seaofnodes/simple/node/ConvertNode.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; import java.util.HashMap; @@ -29,14 +28,15 @@ public class ConvertNode extends Node { return p.p(label()).open().n(val()).close(); } - // The declaration fixes the result family during pessimistic parsing. - // From SCCP onward, preserve dead inputs and stronger facts in that family. + // The declaration bounds the result; preserve dead inputs and stronger + // scalar facts so SCCP can propagate constants through loop conversions. + // Managed pointers keep the declared type until idealize checks access: + // array element access must agree in both directions, so it cannot gate + // precision in this monotone transfer function. @Override public Type compute() { Type src = val()._type; - if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() ) { - if( src.isHigh() ) return Type.TOP; - if( (src.isa(_dst) && src.accessISA(_dst)) ) return src; - } + if( src.isHigh() ) return Type.TOP; + if( !(_dst instanceof TypeMemPtr) && src.isa(_dst) ) return src; return _dst; } diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/ArithNodeTest.java b/chapter28a/src/test/java/com/seaofnodes/simple/ArithNodeTest.java new file mode 100644 index 00000000..e912f224 --- /dev/null +++ b/chapter28a/src/test/java/com/seaofnodes/simple/ArithNodeTest.java @@ -0,0 +1,96 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ArithNodeTest { + @Test public void testUnresolvedInput() { + new CodeGen("return 0;").driver(CodeGen.Phase.Opto); + Node lhs = ConstantNode.seed(TypeInteger.TRUE); + Node rhs = ConstantNode.seed(TypeInteger.TRUE); + ArithNode add = new AddNode(lhs,rhs); + assertSame(TypeInteger.constant(2),add.compute()); + lhs._type = TypeScalar.BOT; + assertSame(Type.BOTTOM,add.compute()); + add.setMode((byte)1); + assertSame(Type.BOTTOM,add.compute()); + } + + @Test public void testFloatPrecision() { + CodeGen code = new CodeGen("f32 x = arg; return x+1.0;").driver(CodeGen.Phase.TypeCheck); + assertEquals("1.6777217E7",Eval2.eval(code,16777216)); + code = new CodeGen("f32 x = arg; f32 y = x+1.0; return y;").driver(CodeGen.Phase.TypeCheck); + assertEquals("1.6777216E7",Eval2.eval(code,16777216)); + } + + @Test public void testMonotoneCompute() { + CodeGen code = new CodeGen("return 0;"); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.BOTTOM,Type.CONTROL,Type.NIL,TypeScalar.BOT,TypeMem.BOT)); + TypeInteger.gather(inputs); + TypeFloat.gather(inputs); + TypePtr.gather(inputs); + TypeMemPtr.gather(inputs); + TypeFunPtr.gather(inputs); + inputs.add(TypeConAryB.make(new byte[]{1,2,3})); + for( long value : new long[]{Long.MIN_VALUE,Long.MIN_VALUE+1,-1,1,Long.MAX_VALUE} ) + inputs.add(TypeInteger.constant(value)); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,16777216.0,16777217.0,Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + int size = inputs.size(); + for( int i = 0; i<size; i++ ) inputs.add(inputs.get(i).dual()); + size = inputs.size(); + + // Isolated inputs let us vary types without peepholes settling modes. + Node lhs = ConstantNode.seed(Type.BOTTOM); + Node rhs = ConstantNode.seed(Type.BOTTOM); + lhs.setDef(0,null); + rhs.setDef(0,null); + ArrayList<ArithNode> ops = new ArrayList<>(); + for( byte mode = 0; mode<3; mode++ ) { + ops.add(new AddNode(lhs,rhs,mode)); + ops.add(new SubNode(lhs,rhs,mode)); + ops.add(new MulNode(lhs,rhs,mode)); + ops.add(new DivNode(lhs,rhs,mode)); + } + ops.add(new AndNode(null,lhs,rhs)); + ops.add(new OrNode(null,lhs,rhs)); + ops.add(new XorNode(null,lhs,rhs)); + ops.add(new ShlNode(null,lhs,rhs)); + ops.add(new SarNode(null,lhs,rhs)); + ops.add(new ShrNode(null,lhs,rhs)); + Type[][][] expected = new Type[ops.size()][size][size]; + for( CodeGen.Phase phase : new CodeGen.Phase[]{CodeGen.Phase.Parse,CodeGen.Phase.Iter,CodeGen.Phase.Opto,CodeGen.Phase.IterPostOpto} ) { + code.driver(phase); + for( int op = 0; op<ops.size(); op++ ) { + ArithNode arith = ops.get(op); + Type[][] results = new Type[size][size]; + for( int i = 0; i<size; i++ ) + for( int j = 0; j<size; j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = arith.compute(); + if( phase==CodeGen.Phase.Parse ) expected[op][i][j] = results[i][j]; + else assertSame("Phase changed compute",expected[op][i][j],results[i][j]); + } + // Check the order relation in each argument independently. + // This covers both falling SCCP types and rising Iter types. + for( int i = 0; i<size; i++ ) + for( int j = 0; j<size; j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<size; k++ ) { + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(arith.getClass().getSimpleName()+" mode="+arith.mode()+": "+ + inputs.get(i)+" -> "+inputs.get(j)+", other="+inputs.get(k)+ + "; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } + } + } +} diff --git a/chapter28a/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java b/chapter28a/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java new file mode 100644 index 00000000..96d73f26 --- /dev/null +++ b/chapter28a/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java @@ -0,0 +1,69 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.ConvertNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.*; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ConvertNodeTest { + @Test public void testMonotoneCompute() { + CodeGen code = new CodeGen("return 0;"); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.BOTTOM,Type.CONTROL,Type.NIL,TypeScalar.BOT,TypeMem.BOT)); + TypeInteger.gather(inputs); + TypeFloat.gather(inputs); + TypePtr.gather(inputs); + TypeMemPtr.gather(inputs); + TypeFunPtr.gather(inputs); + // Writable arrays require matching element access in both directions. + // Widening the element's access can make that check pass while keeping + // a known length; compute must not suddenly gain that length fact. + for( TypeInteger len : new TypeInteger[]{TypeInteger.U32,TypeInteger.TRUE} ) + for( boolean elementRO : new boolean[]{false,true} ) + for( boolean arrayRO : new boolean[]{false,true} ) + inputs.add(TypeMemPtr.make(TypeStruct.makeAry("[]test",len,-1, + TypeMemPtr.TEST.withAccess(elementRO),-2,false)).withAccess(arrayRO)); + inputs.add(TypeConAryB.make(new byte[]{1,2,3})); + for( long value : new long[]{Long.MIN_VALUE,-129,-128,-1,0,1,127,128,255,256,Long.MAX_VALUE} ) + inputs.add(TypeInteger.constant(value)); + for( double value : new double[]{-0.0,0.0,1.0,16777217.0,Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + int size = inputs.size(); + for( int i = 0; i<size; i++ ) inputs.add(inputs.get(i).dual()); + + ArrayList<Type> destinations = new ArrayList<>(); + for( Type t : inputs ) + if( !t.isHigh() && (t instanceof TypeInteger || t instanceof TypeFloat || t instanceof TypeNil) ) + destinations.add(t); + + // Vary one isolated input without folding or lowering the conversion. + Node input = ConstantNode.seed(Type.BOTTOM); + input.setDef(0,null); + Type[][] expected = new Type[destinations.size()][inputs.size()]; + for( CodeGen.Phase phase : new CodeGen.Phase[]{CodeGen.Phase.Parse,CodeGen.Phase.Iter,CodeGen.Phase.Opto,CodeGen.Phase.IterPostOpto} ) { + code.driver(phase); + for( int d = 0; d<destinations.size(); d++ ) { + Type dst = destinations.get(d); + ConvertNode convert = new ConvertNode(dst,input); + Type[] results = new Type[inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) { + input._type = inputs.get(i); + results[i] = convert.compute(); + if( phase==CodeGen.Phase.Parse ) expected[d][i] = results[i]; + else assertSame("Phase changed compute for "+inputs.get(i)+" to "+dst,expected[d][i],results[i]); + } + // Check both rising Iter and falling SCCP with the same order. + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) && !results[i].isa(results[j]) ) + fail("Convert to "+dst+": "+inputs.get(i)+" -> "+inputs.get(j)+ + " gave "+results[i]+" -> "+results[j]); + } + } + } +} diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/ArithNode.java index 92ebd587..e2a88944 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -111,12 +111,16 @@ public abstract class ArithNode extends Node implements ModeNode { @Override public final Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; + // Constant array payloads lie below their element ranges in the lattice. + if( t1 instanceof TypeConAry ary ) t1 = ary.elem(); + if( t2 instanceof TypeConAry ary ) t2 = ary.elem(); if( t1==null || t2==null ) return Type.TOP; if( t1.isHigh() || t2.isHigh() ) return Type.TOP; - if( t1==Type.BOTTOM || t2==Type.BOTTOM ) return Type.BOTTOM; + // Without numeric inputs, stay below both possible result families. + // Pointer modes belong to comparisons, not arithmetic. + if( !(t1 instanceof TypeInteger || t1 instanceof TypeFloat) || + !(t2 instanceof TypeInteger || t2 instanceof TypeFloat) ) return Type.BOTTOM; byte mode = _mode==0 ? mode(t1,t2) : _mode; - if( mode==0 ) - return CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() ? Type.BOTTOM : Type.TOP; if( mode==1 ) { if( t1 instanceof TypeInteger x && t2 instanceof TypeInteger y ) @@ -126,12 +130,10 @@ public abstract class ArithNode extends Node implements ModeNode { return TypeInteger.BOT; } // FP handling - if( t1 instanceof TypeFloat f1 && - t2 instanceof TypeFloat f2 ) { - if( f1.isConstant() && f2.isConstant() ) - return TypeFloat.constant(doOp(f1.value(),f2.value())); - return t1.meet(t2); - } + if( t1 instanceof TypeFloat f1 && t2 instanceof TypeFloat f2 && + f1.isConstant() && f2.isConstant() ) + return TypeFloat.constant(doOp(f1.value(),f2.value())); + // Two f32 inputs can still produce a result needing f64 precision. return TypeFloat.F64; } diff --git a/chapter28b/src/main/java/com/seaofnodes/simple/node/ConvertNode.java b/chapter28b/src/main/java/com/seaofnodes/simple/node/ConvertNode.java index cdc890a7..7f5398ef 100644 --- a/chapter28b/src/main/java/com/seaofnodes/simple/node/ConvertNode.java +++ b/chapter28b/src/main/java/com/seaofnodes/simple/node/ConvertNode.java @@ -3,13 +3,17 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; import java.util.HashMap; -// Convert a value to an authoritative destination type. The destination is -// known structurally from a declaration; the source family might sharpen later. +// Convert the incoming value; actual conversion depends on the _dst type. +// Convert ints to floats, ptrs to ints, nullable to not-null, etc. Once the +// input type is known precisely enough, the idealize() call triggers and +// replaces the Convert with a concrete conversion (e.g. toFloatNode). +// +// Convert has no runtime dynamic behavior; it must *always* get replaced with +// some concrete behavior (or its an error). public class ConvertNode extends Node { private Type _dst; @@ -29,14 +33,13 @@ public class ConvertNode extends Node { return p.p(label()).open().n(val()).close(); } - // The declaration fixes the result family during pessimistic parsing. - // From SCCP onward, preserve dead inputs and stronger facts in that family. + + // Not much to do here, if the input type is not sharp enough to fold into + // the proper conversion, its not sharp enough to do much else. @Override public Type compute() { Type src = val()._type; - if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() ) { - if( src.isHigh() ) return Type.TOP; - if( (src.isa(_dst) && src.accessISA(_dst)) ) return src; - } + if( src.isHigh() ) return Type.TOP; + if( !(_dst instanceof TypeMemPtr) && src.isa(_dst) ) return src; return _dst; } diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/ArithNodeTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/ArithNodeTest.java new file mode 100644 index 00000000..e912f224 --- /dev/null +++ b/chapter28b/src/test/java/com/seaofnodes/simple/ArithNodeTest.java @@ -0,0 +1,96 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ArithNodeTest { + @Test public void testUnresolvedInput() { + new CodeGen("return 0;").driver(CodeGen.Phase.Opto); + Node lhs = ConstantNode.seed(TypeInteger.TRUE); + Node rhs = ConstantNode.seed(TypeInteger.TRUE); + ArithNode add = new AddNode(lhs,rhs); + assertSame(TypeInteger.constant(2),add.compute()); + lhs._type = TypeScalar.BOT; + assertSame(Type.BOTTOM,add.compute()); + add.setMode((byte)1); + assertSame(Type.BOTTOM,add.compute()); + } + + @Test public void testFloatPrecision() { + CodeGen code = new CodeGen("f32 x = arg; return x+1.0;").driver(CodeGen.Phase.TypeCheck); + assertEquals("1.6777217E7",Eval2.eval(code,16777216)); + code = new CodeGen("f32 x = arg; f32 y = x+1.0; return y;").driver(CodeGen.Phase.TypeCheck); + assertEquals("1.6777216E7",Eval2.eval(code,16777216)); + } + + @Test public void testMonotoneCompute() { + CodeGen code = new CodeGen("return 0;"); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.BOTTOM,Type.CONTROL,Type.NIL,TypeScalar.BOT,TypeMem.BOT)); + TypeInteger.gather(inputs); + TypeFloat.gather(inputs); + TypePtr.gather(inputs); + TypeMemPtr.gather(inputs); + TypeFunPtr.gather(inputs); + inputs.add(TypeConAryB.make(new byte[]{1,2,3})); + for( long value : new long[]{Long.MIN_VALUE,Long.MIN_VALUE+1,-1,1,Long.MAX_VALUE} ) + inputs.add(TypeInteger.constant(value)); + for( double value : new double[]{-0.0,0.0,-1.0,1.0,16777216.0,16777217.0,Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + int size = inputs.size(); + for( int i = 0; i<size; i++ ) inputs.add(inputs.get(i).dual()); + size = inputs.size(); + + // Isolated inputs let us vary types without peepholes settling modes. + Node lhs = ConstantNode.seed(Type.BOTTOM); + Node rhs = ConstantNode.seed(Type.BOTTOM); + lhs.setDef(0,null); + rhs.setDef(0,null); + ArrayList<ArithNode> ops = new ArrayList<>(); + for( byte mode = 0; mode<3; mode++ ) { + ops.add(new AddNode(lhs,rhs,mode)); + ops.add(new SubNode(lhs,rhs,mode)); + ops.add(new MulNode(lhs,rhs,mode)); + ops.add(new DivNode(lhs,rhs,mode)); + } + ops.add(new AndNode(null,lhs,rhs)); + ops.add(new OrNode(null,lhs,rhs)); + ops.add(new XorNode(null,lhs,rhs)); + ops.add(new ShlNode(null,lhs,rhs)); + ops.add(new SarNode(null,lhs,rhs)); + ops.add(new ShrNode(null,lhs,rhs)); + Type[][][] expected = new Type[ops.size()][size][size]; + for( CodeGen.Phase phase : new CodeGen.Phase[]{CodeGen.Phase.Parse,CodeGen.Phase.Iter,CodeGen.Phase.Opto,CodeGen.Phase.IterPostOpto} ) { + code.driver(phase); + for( int op = 0; op<ops.size(); op++ ) { + ArithNode arith = ops.get(op); + Type[][] results = new Type[size][size]; + for( int i = 0; i<size; i++ ) + for( int j = 0; j<size; j++ ) { + lhs._type = inputs.get(i); + rhs._type = inputs.get(j); + results[i][j] = arith.compute(); + if( phase==CodeGen.Phase.Parse ) expected[op][i][j] = results[i][j]; + else assertSame("Phase changed compute",expected[op][i][j],results[i][j]); + } + // Check the order relation in each argument independently. + // This covers both falling SCCP types and rising Iter types. + for( int i = 0; i<size; i++ ) + for( int j = 0; j<size; j++ ) + if( inputs.get(i).isa(inputs.get(j)) ) + for( int k = 0; k<size; k++ ) { + if( !results[i][k].isa(results[j][k]) || !results[k][i].isa(results[k][j]) ) + fail(arith.getClass().getSimpleName()+" mode="+arith.mode()+": "+ + inputs.get(i)+" -> "+inputs.get(j)+", other="+inputs.get(k)+ + "; lhs results "+results[i][k]+" -> "+results[j][k]+ + "; rhs results "+results[k][i]+" -> "+results[k][j]); + } + } + } + } +} diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java new file mode 100644 index 00000000..96d73f26 --- /dev/null +++ b/chapter28b/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java @@ -0,0 +1,69 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.ConvertNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.*; +import java.util.ArrayList; +import java.util.Arrays; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ConvertNodeTest { + @Test public void testMonotoneCompute() { + CodeGen code = new CodeGen("return 0;"); + ArrayList<Type> inputs = new ArrayList<>(Arrays.asList( + Type.BOTTOM,Type.CONTROL,Type.NIL,TypeScalar.BOT,TypeMem.BOT)); + TypeInteger.gather(inputs); + TypeFloat.gather(inputs); + TypePtr.gather(inputs); + TypeMemPtr.gather(inputs); + TypeFunPtr.gather(inputs); + // Writable arrays require matching element access in both directions. + // Widening the element's access can make that check pass while keeping + // a known length; compute must not suddenly gain that length fact. + for( TypeInteger len : new TypeInteger[]{TypeInteger.U32,TypeInteger.TRUE} ) + for( boolean elementRO : new boolean[]{false,true} ) + for( boolean arrayRO : new boolean[]{false,true} ) + inputs.add(TypeMemPtr.make(TypeStruct.makeAry("[]test",len,-1, + TypeMemPtr.TEST.withAccess(elementRO),-2,false)).withAccess(arrayRO)); + inputs.add(TypeConAryB.make(new byte[]{1,2,3})); + for( long value : new long[]{Long.MIN_VALUE,-129,-128,-1,0,1,127,128,255,256,Long.MAX_VALUE} ) + inputs.add(TypeInteger.constant(value)); + for( double value : new double[]{-0.0,0.0,1.0,16777217.0,Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} ) + inputs.add(TypeFloat.constant(value)); + int size = inputs.size(); + for( int i = 0; i<size; i++ ) inputs.add(inputs.get(i).dual()); + + ArrayList<Type> destinations = new ArrayList<>(); + for( Type t : inputs ) + if( !t.isHigh() && (t instanceof TypeInteger || t instanceof TypeFloat || t instanceof TypeNil) ) + destinations.add(t); + + // Vary one isolated input without folding or lowering the conversion. + Node input = ConstantNode.seed(Type.BOTTOM); + input.setDef(0,null); + Type[][] expected = new Type[destinations.size()][inputs.size()]; + for( CodeGen.Phase phase : new CodeGen.Phase[]{CodeGen.Phase.Parse,CodeGen.Phase.Iter,CodeGen.Phase.Opto,CodeGen.Phase.IterPostOpto} ) { + code.driver(phase); + for( int d = 0; d<destinations.size(); d++ ) { + Type dst = destinations.get(d); + ConvertNode convert = new ConvertNode(dst,input); + Type[] results = new Type[inputs.size()]; + for( int i = 0; i<inputs.size(); i++ ) { + input._type = inputs.get(i); + results[i] = convert.compute(); + if( phase==CodeGen.Phase.Parse ) expected[d][i] = results[i]; + else assertSame("Phase changed compute for "+inputs.get(i)+" to "+dst,expected[d][i],results[i]); + } + // Check both rising Iter and falling SCCP with the same order. + for( int i = 0; i<inputs.size(); i++ ) + for( int j = 0; j<inputs.size(); j++ ) + if( inputs.get(i).isa(inputs.get(j)) && !results[i].isa(results[j]) ) + fail("Convert to "+dst+": "+inputs.get(i)+" -> "+inputs.get(j)+ + " gave "+results[i]+" -> "+results[j]); + } + } + } +} diff --git a/docs/roadmap.ja.md b/docs/roadmap.ja.md index 057e4440..fdaaff91 100644 --- a/docs/roadmap.ja.md +++ b/docs/roadmap.ja.md @@ -7,7 +7,7 @@ ## 正確性とコンパイル -- `ArithNode` と `ConvertNode` の型計算をフェーズに依存しない単調な規則にする。Eval2 の追加ロード時のスケジューリング用領域、`StopCUNode` の全呼び出し・関数要約の反復走査、Export 内に残るエンコード処理も整理する。 +- Eval2 の追加ロード時のスケジューリング用領域、`StopCUNode` の全呼び出し・関数要約の反復走査、Export 内に残るエンコード処理を整理する。 - 依存関係全体を調べ、変更を伝播してから保存 IR を再利用する、正しい増分ビルドを実装する。 - 型の読み込みからネイティブリンクまでのライブラリ変更を検出する。SHA-256 を含むシンボルの照合は将来案であり、Eval2 は整合したビルドを前提とする。 - コンパイル単位ごとの選択的ロードを、オブジェクト内の関数単位へ細分化する。 diff --git a/docs/roadmap.md b/docs/roadmap.md index 0878bbc7..ae450d82 100644 --- a/docs/roadmap.md +++ b/docs/roadmap.md @@ -13,9 +13,6 @@ design decisions and chapter boundaries. Remaining work: -- Remove phase-dependent transfer rules from `ArithNode.compute()` and - `ConvertNode.compute()`. Keep the same monotone rule in both pessimistic - and optimistic analysis. - Remove Eval2 scheduling scratch costs proportional to all previously allocated node IDs. Scheduling a newly loaded object should cost only for that graph and any affected existing nodes. |