From 53c96d663da27ddab3eb09b38c6f471cc1a82563 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 13 Jun 2025 15:42:08 -0700 Subject: Chapter 25: SSA Before Types Are Known MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Jun Kawasaki Co-authored-by: Hadházy Tamás Co-authored-by: Claude Opus 5 --- .../java/com/seaofnodes/simple/ArithNodeTest.java | 96 ++++++++++++++++++++++ .../java/com/seaofnodes/simple/Chapter07Test.java | 10 +-- .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter12Test.java | 10 ++- .../com/seaofnodes/simple/Chapter14FloatTest.java | 2 +- .../java/com/seaofnodes/simple/Chapter14Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter18Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 6 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 16 +++- .../java/com/seaofnodes/simple/Chapter23Test.java | 24 +++--- .../com/seaofnodes/simple/ConvertNodeTest.java | 69 ++++++++++++++++ src/test/java/com/seaofnodes/simple/Eval2.java | 15 ++-- .../com/seaofnodes/simple/FloatPrecisionTest.java | 61 -------------- .../com/seaofnodes/simple/IncompleteTypesTest.java | 53 ++++++++++++ .../java/com/seaofnodes/simple/MergeSortTest.java | 10 +-- .../java/com/seaofnodes/simple/MinusNodeTest.java | 73 ++++++++++++++++ .../com/seaofnodes/simple/NarrowFieldTest.java | 89 ++++++++++++++++++++ src/test/java/com/seaofnodes/simple/TypeTest.java | 4 +- .../simple/codegen/RegAllocTestSupport.java | 6 +- 20 files changed, 445 insertions(+), 111 deletions(-) create mode 100644 src/test/java/com/seaofnodes/simple/ArithNodeTest.java create mode 100644 src/test/java/com/seaofnodes/simple/ConvertNodeTest.java delete mode 100644 src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java create mode 100644 src/test/java/com/seaofnodes/simple/IncompleteTypesTest.java create mode 100644 src/test/java/com/seaofnodes/simple/MinusNodeTest.java create mode 100644 src/test/java/com/seaofnodes/simple/NarrowFieldTest.java (limited to 'src/test') diff --git a/src/test/java/com/seaofnodes/simple/ArithNodeTest.java b/src/test/java/com/seaofnodes/simple/ArithNodeTest.java new file mode 100644 index 00000000..708c32a2 --- /dev/null +++ b/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 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 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 "+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/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java index 8db31bc1..daca77ab 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -18,7 +18,7 @@ while(arg < 10) { return arg; """); code.parse(); - assertEquals("return Phi(Loop,arg,(Phi_arg+1));", code.print()); + assertEquals("return Phi(Loop,arg,(Convert_i64(Phi_arg)+1));", code.print()); assertTrue(code.ctrl() instanceof CProjNode); } @@ -71,7 +71,7 @@ while(a < 10) { return b; """); code.parse(); - assertEquals("return Phi(Loop,2,Phi(Region,Phi_b,4));", code.print()); + assertEquals("return Convert_i64(Phi(Loop,2,Phi(Region,Phi_b,4)));", code.print()); assertTrue(code.ctrl() instanceof CProjNode); } @@ -107,7 +107,7 @@ while(a < 10) { return a; """); code.parse(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertEquals("return Phi(Loop,1,(Convert_i64(Phi_a)+3));", code.print()); assertTrue(code.ctrl() instanceof CProjNode); } @@ -165,7 +165,7 @@ while(a < 10) { return a; """); code.parse(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertEquals("return Phi(Loop,1,(Convert_i64(Phi_a)+3));", code.print()); assertTrue(code.ctrl() instanceof CProjNode); } @@ -198,7 +198,7 @@ while(a < 10) { return a; """); code.parse(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertEquals("return Phi(Loop,1,(Convert_i64(Phi_a)+3));", code.print()); assertTrue(code.ctrl() instanceof CProjNode); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java index f24d96eb..50410618 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -255,7 +255,7 @@ return 0!=0; int v0=0; while(0==1) while(v0) v0=1+v0; -return 0; +return 0; """); code.driver(CodeGen.Phase.FinalizeIR); assertEquals("return 0;", code.print()); diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 2ef209c5..2a86b11a 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -212,7 +212,7 @@ return a.f0.f1.f0.f1.f0; """); code.driver(CodeGen.Phase.LocalSched); assertEquals("return B;", code._stop.toString()); - assertEquals("B{f0=C},f1=A{f0=$cyclic,f1=$cyclic}}", Eval2.eval(code, 0)); + assertEquals("B{f0=C{f0=A{f0=$cyclic,f1=$cyclic},f1=$cyclic},f1=$cyclic}", Eval2.eval(code, 0)); } @Test @@ -278,6 +278,12 @@ return a.b.c.a.b.c.a.b.c.a.b.c.a.b.c.a.b.c; """); code.driver(CodeGen.Phase.LocalSched); assertEquals("return R;", code._stop.toString()); - assertEquals("R{a=C{a=N},b=V},c=H}},b=K{a=$cyclic,b=D{a=O},b=W},c=I}},c=P}},c=$cyclic}", Eval2.eval(code, 0)); + // All forward shapes are complete now. Following field a visits + // all 26 objects before closing the cycle; b and c revisit them. + String expected = "$cyclic"; + String chain = "RCNYJUFQBMXITEPALWHSDOZKVG"; + for( int i=chain.length()-1; i>=0; i-- ) + expected=chain.charAt(i)+"{a="+expected+",b=$cyclic,c=$cyclic}"; + assertEquals(expected,Eval2.eval(code,0)); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java index b0cf0a91..e9333837 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java +++ b/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java @@ -84,7 +84,7 @@ while( 1 ) { return guess; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)*0.5f));", code.print()); + assertEquals("return Phi(Loop,(flt)arg,((Phi_guess+(ToFloat/Phi_guess))*0.5f));", code.print()); assertEquals("3.0", Eval2.eval(code, 9)); assertEquals("1.414213562373095", Eval2.eval(code, 2)); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/src/test/java/com/seaofnodes/simple/Chapter14Test.java index b4a27c04..06d86f5f 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -176,7 +176,7 @@ while(v1) break; return v1; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("return Phi(Loop,(((1< }; """; CodeGen code = new CodeGen(src).driver(CodeGen.Phase.LocalSched); - assertEquals("Stop[ return Phi(Region,1,0,0,1); return Phi(Region,._hashCode,Phi(Region,123456789,Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code._stop.toString()); + assertEquals("Stop[ return Phi(Region,1,0,0,1); return Phi(Region,(!=0)._hashCode,Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code._stop.toString()); //assertEquals("-4898613127354160978", Eval2.eval(code, 2)); } @@ -398,7 +398,7 @@ val test_sqrt = { flt x -> flt farg = arg; return test_sqrt(farg); """; CodeGen code = new CodeGen(src).driver(Phase.LocalSched,"x86_64_v2", "SystemV"); - assertEquals("return Phi(Loop,(cvtf,arg),(mulf,(addf,(divf,cvtf,Phi_guess),Phi_guess),0.5f));", code.print()); + assertEquals("return Phi(Loop,(cvtf,arg),(mulf,(addf,Phi_guess,(divf,cvtf,Phi_guess)),0.5f));", code.print()); }; diff --git a/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/src/test/java/com/seaofnodes/simple/Chapter20Test.java index ba93a440..fe69e5ad 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -285,9 +285,9 @@ while (arg > 0) { } return arg; """; - testTarget(src,"x86_64_v2", "SystemV",3,null); - testTarget(src,"riscv" , "SystemV",2,null); - testTarget(src,"arm" , "SystemV",2,null); + testTarget(src,"x86_64_v2", "SystemV",1,null); + testTarget(src,"riscv" , "SystemV",0,null); + testTarget(src,"arm" , "SystemV",0,null); } // Original Chapter 20 allocation workload, kept fixed for cohort comparisons. @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 1bf65cfd..8442bbc8 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -467,9 +467,17 @@ while(true) { } return i; """; - testCPU(src,"x86_64_v2", "Win64" ,0,"return (inc,Phi(Loop,0,inc));"); - testCPU(src,"riscv" , "SystemV",0,"return ( Phi(Loop,0,addi) + #1 );"); - testCPU(src,"arm" , "SystemV",0,"return (inc,Phi(Loop,0,inc));"); + testCPU(src,"x86_64_v2", "Win64" ,0,"return (!=0)(inc,Phi(Loop,0,Phi(Region,(!=0),(!=0),0)));"); + testCPU(src,"riscv" , "SystemV",0,"return (!=0)( Phi(Loop,0,Phi(Region,(!=0),(!=0),0)) + #1 );"); + testCPU(src,"arm" , "SystemV",0,"return (!=0)(inc,Phi(Loop,0,Phi(Region,(!=0),(!=0),0)));"); + // Guards now survive into selection. They must preserve the loop's + // value through both continues and the final break without code. + EvalRisc5 r5 = TestRisc5.build("guardLoop",src,0,0,false); + assertEquals(0,r5.step(1000)); + assertEquals(2,r5.regs[riscv.A0]); + EvalArm64 a5 = TestArm64.build("guardLoop",src,0,0,false); + assertEquals(0,a5.step(1000)); + assertEquals(2,a5.regs[0]); } @Test public void testNewtonExport() throws IOException { @@ -498,7 +506,7 @@ val test_sqrt = { flt x -> } }; """; - TestC.run(src, "newtonFloat", null, result, 34); + TestC.run(src, "newtonFloat", null, result, TestC.CALL_CONVENTION.equals("Win64") ? 42 : 34); EvalRisc5 R5 = TestRisc5.build("newtonFloat",src, 0, 10, false); R5.fregs[riscv.FA0 - riscv.F_OFFSET] = 3.0; diff --git a/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 22be3af1..1dd21d08 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -115,7 +115,7 @@ var apply = { i64 x, { i64 -> u32 } fcn -> """ int a = 1; int b = 0; - + if(a++ || b++ ) { if(b == 0 && a == 2) { sys.io.p("Or"); @@ -149,7 +149,7 @@ var apply = { i64 x, { i64 -> u32 } fcn -> """ int a = 1; int b = 1; - + if(a && b) { sys.io.p("And"); } else { @@ -186,14 +186,14 @@ var apply = { i64 x, { i64 -> u32 } fcn -> String src2 = """ struct S { !S? !fld; }; - + val ptr = arg == 1 ? null : new S{fld = arg==1 ? null : new S{fld = null;};}; if( ptr && ptr.fld ) { sys.io.p("true"); } else { sys.io.p("false"); } - + return 0; """; CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); @@ -221,13 +221,13 @@ var apply = { i64 x, { i64 -> u32 } fcn -> """ int a = 1; int b = 1; - + int x=1; int y=1; int z=0; - + int g = x++ && y++ && z++; - + if(x == 2 && y == 2 && z == 1 && g == 0) { sys.io.p("Effected"); } else { @@ -259,13 +259,13 @@ var apply = { i64 x, { i64 -> u32 } fcn -> """ int a = 1; int b = 1; - + int x = -1; int y=1; int z= -1; - + int g = x++ || y++ || z++; - + int switch = 0; if(x == 4 || y == 4 || z == 4) { switch = -1; @@ -305,11 +305,11 @@ var apply = { i64 x, { i64 -> u32 } fcn -> // -*- mode: java; -*- int a = 1; int b = 1; - + var sq = { int x -> x*x; }; - + if(a && sq(0)) { sys.io.p("And"); } else { diff --git a/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java b/src/test/java/com/seaofnodes/simple/ConvertNodeTest.java new file mode 100644 index 00000000..2342b33a --- /dev/null +++ b/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 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 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 "+inputs.get(j)+ + " gave "+results[i]+" -> "+results[j]); + } + } + } +} diff --git a/src/test/java/com/seaofnodes/simple/Eval2.java b/src/test/java/com/seaofnodes/simple/Eval2.java index 2a10857b..762005cb 100644 --- a/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/src/test/java/com/seaofnodes/simple/Eval2.java @@ -254,23 +254,24 @@ public abstract class Eval2 { private static Object compute( Node n ) { return switch( n ) { case AddFNode adf -> d(adf.in(1)) + d(adf.in(2)); - case AddNode add -> x(add.in(1)) + x(add.in(2)); + case AddNode add -> add.mode()==2 ? (Object)(d(add.in(1)) + d(add.in(2))) : (Object)(x(add.in(1)) + x(add.in(2))); case AndNode and -> x(and.in(1)) & x(and.in(2)); case BoolNode.EQF eqf -> d(eqf.in(1)) == d(eqf.in(2)) ? 1L : 0L; case BoolNode.LEF lef -> d(lef.in(1)) <= d(lef.in(2)) ? 1L : 0L; case BoolNode.LTF ltf -> d(ltf.in(1)) < d(ltf.in(2)) ? 1L : 0L; case BoolNode.EQ eq -> Objects.equals(val(eq.in(1)), val(eq.in(2))) ? 1L : 0L; // Bool EQ supports pointers, nil, and integers - case BoolNode.LE le -> x(le .in(1)) <= x(le .in(2)) ? 1L : 0L; - case BoolNode.LT lt -> x(lt .in(1)) < x(lt .in(2)) ? 1L : 0L; + case BoolNode.LE le -> (le.isFloat() ? d(le.in(1))<=d(le.in(2)) : x(le.in(1))<=x(le.in(2))) ? 1L : 0L; + case BoolNode.LT lt -> (lt.isFloat() ? d(lt.in(1)) val(cast.in(1)); + case GuardNode guard -> val(guard.in(1)); case ConstantNode con -> con(con._con); case DivFNode dvf -> d(dvf.in(2))==0 ? 0D : d(dvf.in(1)) / d(dvf.in(2)); - case DivNode div -> x(div.in(2))==0 ? 0L : x(div.in(1)) / x(div.in(2)); + case DivNode div -> div.mode()==2 ? (Object)(d(div.in(2))==0 ? 0D : d(div.in(1))/d(div.in(2))) : (Object)(x(div.in(2))==0 ? 0L : x(div.in(1))/x(div.in(2))); case LoadNode ld -> load(ld); case MinusFNode mnf -> - d(mnf.in(1)); - case MinusNode sub -> - x(sub.in(1)); + case MinusNode sub -> sub.mode()==2 ? (Object)(-d(sub.in(1))) : (Object)(-x(sub.in(1))); case MulFNode mlf -> d(mlf.in(1)) * d(mlf.in(2)); - case MulNode mul -> x(mul.in(1)) * x(mul.in(2)); + case MulNode mul -> mul.mode()==2 ? (Object)(d(mul.in(1)) * d(mul.in(2))) : (Object)(x(mul.in(1)) * x(mul.in(2))); case NewNode alloc-> alloc(alloc); case NotNode not -> not(not); case OrNode or -> x(or .in(1)) | x(or .in(2)); @@ -281,7 +282,7 @@ public abstract class Eval2 { case ShlNode shl -> x(shl.in(1)) << x(shl.in(2)); case ShrNode shr -> x(shr.in(1)) >>>x(shr.in(2)); case StoreNode st -> store(st); - case SubNode sub -> x(sub.in(1)) - x(sub.in(2)); + case SubNode sub -> sub.mode()==2 ? (Object)(d(sub.in(1)) - d(sub.in(2))) : (Object)(x(sub.in(1)) - x(sub.in(2))); case SubFNode sbf -> d(sbf.in(1)) - d(sbf.in(2)); case RoundF32Node rnd -> (double)(float)d(rnd.in(1)); case ToIntegerNode cvt -> (long)d(cvt.in(1)); diff --git a/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java b/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java deleted file mode 100644 index 08902bb2..00000000 --- a/src/test/java/com/seaofnodes/simple/FloatPrecisionTest.java +++ /dev/null @@ -1,61 +0,0 @@ -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 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.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/src/test/java/com/seaofnodes/simple/IncompleteTypesTest.java b/src/test/java/com/seaofnodes/simple/IncompleteTypesTest.java new file mode 100644 index 00000000..419cac51 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/IncompleteTypesTest.java @@ -0,0 +1,53 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import com.seaofnodes.simple.type.TypeInteger; +import static org.junit.Assert.assertEquals; + +public class IncompleteTypesTest { + @Test public void testLoadFromUnsettledLoopPhi() { + String src = """ + struct C { int x; }; + val f={int n -> return new C { while(n--) if(n) x=1; }; }; + return f(arg).x; + """; + for( long seed : new long[]{123,456,789} ) { + var code = new CodeGen(src,TypeInteger.BOT,seed,true).driver(CodeGen.Phase.TypeCheck); + for( int arg=0; arg<6; arg++ ) + assertEquals("seed="+seed+" arg="+arg,arg<2 ? "0" : "1",Eval2.eval(code,arg)); + } + } + + @Test public void testForwardFieldAndNumericMode() { + // At the addition, neither the field's type nor its offset is known. + String src = """ + val add = { Later p -> return p.x + 1; }; + struct Later { flt x; }; + return add(new Later { x = 2.5; }); + """; + var code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + assertEquals("3.5",Eval2.eval(code,0)); + } + + @Test public void testForwardStore() { + // Resolve the field's alias and integer width after its declaration. + String src = """ + val set = { !Later p, int n -> p.x = n; return p.x; }; + struct Later { u8 x; }; + return set(new Later,258); + """; + var code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + assertEquals("2",Eval2.eval(code,0)); + for( String update : new String[]{"p.x += n","p.x++"} ) { + String updates = "val set = { !Later p, int n -> p.x=255; return "+update+"; }; " + + "struct Later { u8 x; }; return set(new Later,3);"; + // Seeds 2 and 13 let the Load resolve before the symbolic Store. + // It must wait for that Store's alias, not read an earlier Store. + for( long seed : new long[]{2,13,123} ) { + var result = new CodeGen(updates,TypeInteger.BOT,seed,true).driver(CodeGen.Phase.TypeCheck); + assertEquals(update.equals("p.x++") ? "255" : "2",Eval2.eval(result,0)); + } + } + } +} diff --git a/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/src/test/java/com/seaofnodes/simple/MergeSortTest.java index 453bd35c..324790a0 100644 --- a/src/test/java/com/seaofnodes/simple/MergeSortTest.java +++ b/src/test/java/com/seaofnodes/simple/MergeSortTest.java @@ -17,13 +17,13 @@ public class MergeSortTest { @Test public void testMergeSort0() throws IOException { // Test merge sort on a small array of primes String src = -""" +""" val merge_sort = { int[] a -> int[] !b = new int[a#]; copy_array (a, 0, a#, b); split_merge(a, 0, a#, b); }; - + val split_merge = { int[] !b, int begin, int end, int[] a -> if (end - begin <= 1) return 0; @@ -33,10 +33,10 @@ public class MergeSortTest { merge(b, begin, middle, end, a); return 0; }; - + val merge = { int[] !b, int begin, int middle, int end, int[] a -> int i = begin, j = middle; - + for (int k = begin; k < end; k++) { // && and || bool cond = false; @@ -48,7 +48,7 @@ public class MergeSortTest { else b[k] = a[j++]; } }; - + val copy_array = { int[] !a, int begin, int end, int[] b -> for (int k = begin; k < end; k++) b[k] = a[k]; diff --git a/src/test/java/com/seaofnodes/simple/MinusNodeTest.java b/src/test/java/com/seaofnodes/simple/MinusNodeTest.java new file mode 100644 index 00000000..497546df --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/MinusNodeTest.java @@ -0,0 +1,73 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.MinusNode; +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 MinusNodeTest { + @Test public void testMonotoneCompute() { + CodeGen code = new CodeGen("return 0;"); + // Type.gather also loads cached fixtures which do not survive later compiler resets. + ArrayList inputs = new ArrayList<>(Arrays.asList( + Type.BOTTOM,Type.CONTROL,Type.NIL,TypeScalar.BOT,TypePtr.PTR, + TypeMemPtr.BOT,TypeFunPtr.BOT,TypeMem.BOT, + TypeConAryB.make(new byte[]{1,2,3}))); + TypeInteger.gather(inputs); + TypeFloat.gather(inputs); + int size = inputs.size(); + for( int i=0; i "+inputs.get(j)+ + " gave "+results[i]+" -> "+results[j],results[i].isa(results[j])); + } + } + } + + @Test public void testUnresolvedInput() { + new CodeGen("return 0;").driver(CodeGen.Phase.Opto); + Node input = new ConstantNode(TypeInteger.TRUE); + MinusNode minus = new MinusNode(input); + assertSame(TypeInteger.constant(-1),minus.compute()); + input._type = Type.BOTTOM; + assertSame(Type.BOTTOM,minus.compute()); + minus.setMode((byte)1); + assertSame(Type.BOTTOM,minus.compute()); + } + + @Test public void testRecursiveFloat() { + CodeGen code = new CodeGen("val _neg = { int x -> x ? -_neg(x-1) : 1.0; }; return _neg(arg);") + .driver(CodeGen.Phase.TypeCheck); + for( int i=0; i<4; i++ ) + assertEquals((i&1)==0 ? "1.0" : "-1.0",Eval2.eval(code,i)); + } +} diff --git a/src/test/java/com/seaofnodes/simple/NarrowFieldTest.java b/src/test/java/com/seaofnodes/simple/NarrowFieldTest.java new file mode 100644 index 00000000..f6cc2e4b --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/NarrowFieldTest.java @@ -0,0 +1,89 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; +import com.seaofnodes.simple.node.FunNode; +import com.seaofnodes.simple.node.cpus.riscv.riscv; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.isa.eval.EvalRisc5; +import org.junit.Test; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; +import static org.junit.Assert.*; + +public class NarrowFieldTest { + private static final String[] TYPES = {"u8", "i8", "u16", "i16", "u32", "i32"}; + private static final long[] MINS = {0, -128, 0, -32768, 0, Integer.MIN_VALUE}; + private static final long[] MAXS = {255, 127, 65535, 32767, 0xffffffffL, Integer.MAX_VALUE}; + + // Both the method result and a later read must see the stored, narrowed value. + private static String source(int i, boolean increment, boolean argument) { + String name = "C"+i+(increment ? "Inc" : "Dec"); + long initial = argument ? 0 : (increment ? MAXS[i] : MINS[i]); + return "struct "+name+" { "+TYPES[i]+" x="+initial+"; " + +"val next_noInline={ -> x"+(increment ? "++" : "--")+"; return x; }; }; " + +"var c=new "+name+"; "+(argument ? "c.x=arg; " : "") + +"val a=c.next_noInline(); val b=c.next_noInline(); " + +"return a+10*b+100*c.x;"; + } + + private static long expected(int i, boolean increment) { + long first = increment ? MINS[i] : MAXS[i]; + long second = first+(increment ? 1 : -1); + return first+110*second; + } + + @Test public void testMethodResults() { + for( int i = 0; i ") + .append(source(i,increment,true)).append(" }; "); + declarations.append("__attribute__((CALL_CONV)) extern long long ").append(name).append("(long long);\n"); + checks.append("if (").append(name).append('(').append(increment ? MAXS[i] : MINS[i]) + .append("LL)!=").append(expected(i,increment)).append("LL) return 1;\n"); + } + Path dir = Path.of("build/objs"); + Files.createDirectories(dir); + Path driver = dir.resolve("narrowField.c"); + Files.writeString(driver,declarations+"int main(void) {\n"+checks+"return 0; }\n"); + String abi = TestC.OS.startsWith("Windows") ? "ms_abi" : "sysv_abi"; + TestC.run(src.toString(),TestC.CALL_CONVENTION,null,abi,driver.toString(),"build/objs/narrowField","S","",-1); + } + + @Test public void testRiscvMethodResults() throws IOException { + for( int i = 0; i=0); + byte[] image = new byte[1<<20]; + byte[] bits = code._encoding.bits(); + System.arraycopy(bits,0,image,0,bits.length); + EvalRisc5 cpu = new EvalRisc5(image,1<<16); + cpu._pc = entry; + assertEquals(src,0,cpu.step(100000)); + assertEquals(src,expected(i,increment),cpu.regs[riscv.A0]); + } + } +} diff --git a/src/test/java/com/seaofnodes/simple/TypeTest.java b/src/test/java/com/seaofnodes/simple/TypeTest.java index fd3fea9d..c7ba8caa 100644 --- a/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -47,8 +47,8 @@ public class TypeTest { // Test basic properties and GLB @Test public void testTypeAdHoc() { - Assert.assertEquals( Type.BOTTOM, TypeInteger.TRUE.meet(TypeNil.NIL) ); - Assert.assertEquals( Type.BOTTOM, TypeInteger.TOP .meet(TypeNil.NIL) ); + Assert.assertEquals( TypeScalar.BOT, TypeInteger.TRUE.meet(TypeNil.NIL) ); + Assert.assertEquals( TypeScalar.BOT, TypeInteger.TOP .meet(TypeNil.NIL) ); TypeStruct s1 = TypeStruct.make("s1",false, Field.make("a", TypeInteger.BOT,-1, false, false), diff --git a/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 0304c6a1..7a21c3a7 100644 --- a/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -118,7 +118,7 @@ public class RegAllocTestSupport { @Override public boolean commutes() { return true; } }; RegionNode region = new RegionNode(null,code._start,code._start); - new PhiNode("sum",TypeInteger.BOT,region,add,a); + new PhiNode("sum",region,add,a); code._cfg.add(region); assertTrue(BuildLRG.run(0,new RegAlloc(code))); } @@ -185,7 +185,7 @@ public class RegAllocTestSupport { Op def = new Op(A,null,null,false,code._start); Node top = new ConstantNode(com.seaofnodes.simple.type.Type.TOP); RegionNode region = new RegionNode(null,code._start,code._start); - PhiNode phi = new PhiNode("value",TypeInteger.BOT,region,slot==1 ? top : def,slot==2 ? top : def); + PhiNode phi = new PhiNode("value",region,slot==1 ? top : def,slot==2 ? top : def); phi._type = TypeInteger.BOT; new Op(null,A,null,false,region,phi); code._cfg.add(region); @@ -255,7 +255,7 @@ public class RegAllocTestSupport { RegAlloc alloc = new RegAlloc(code); Op init = new Op(A,null,null,false,code._start); LoopNode loop = new LoopNode(null,code._start); - PhiNode phi = new PhiNode("loop",TypeInteger.BOT,loop,init,null); + PhiNode phi = new PhiNode("loop",loop,init,null); Op back = new Op(A,A,null,false,loop,phi); phi.setDef(2,back); Op use = new Op(null,A,null,false,loop,phi); -- cgit v1.2.3