From 7edca9823ec8ef0aed10c88fa07ef969792aab77 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 19 Oct 2026 14:56:14 -0700 Subject: Split from ch25, SCCP and interprocedural SCCP --- .../java/com/seaofnodes/simple/Chapter20Test.java | 430 +++++++++++++++++++++ 1 file changed, 430 insertions(+) create mode 100644 chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/Chapter20Test.java (limited to 'chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/Chapter20Test.java') diff --git a/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/Chapter20Test.java new file mode 100644 index 00000000..ba93a440 --- /dev/null +++ b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -0,0 +1,430 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; + + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.print.ASMPrinter; +import org.junit.Assert; +import org.junit.Ignore; +import org.junit.Test; +import static org.junit.Assert.*; + +public class Chapter20Test { + @Test public void testFlagSpills() throws Exception { + com.seaofnodes.simple.codegen.FlagSpillTestSupport.run(); + } + + @Test public void testAllocatorTopPhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.topPhi(); } + + @Test public void testNeverReturnAllocation() { + String[] sources = { + // A real integer return merged with a synthetic exit. + "if(arg) while(1) {} return arg+1;", + // TOP must not widen a non-null pointer or constrain a float register. + "struct S { int x; }; !S !s=new S; if(arg) while(1) {} return s;", + "if(arg) while(1) {} return 1.5;", + // Several synthetic exits into the same return. + "if(arg==1) while(1) {} if(arg==2) while(1) {} return arg+3;", + // No real return, including a merge of only synthetic exits. + "while(1) { arg+=1; }", + "if(arg) while(1) {} while(1) {}", + // Loop-carried memory and scalar self-conflicts exercise spilling. + "struct S { int x; int y; }; !S !a=new S; if(arg) while(1) { a.x+=arg; a.y+=a.x; } return a.x+a.y;" + }; + for( String target : new String[]{"x86_64_v2","riscv","arm"} ) + for( String src : sources ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.RegAlloc,target,"SystemV"); + com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); + assertNotNull(code._stop.walk(n -> { + if( n._type!=com.seaofnodes.simple.type.Type.TOP ) return null; + assertEquals(-1,code._regAlloc.regnum(n)); + for( var use : n.outs() ) + assertFalse(use instanceof com.seaofnodes.simple.node.SplitNode); + return n; + })); + code.encode(); + } + } + + @Test public void testAllocatorFixedNeighbor() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.uncoloredFixedNeighbor(); } + + @Test public void testNarrowStoreMasks() { + for( String type : new String[]{"i8","u8","i16","u16"} ) { + CodeGen code = new CodeGen("struct S { "+type+" x; }; !S !s=new S; s.x=arg; return 0;") + .driver(CodeGen.Phase.RegAlloc,"x86_64_v2","SystemV"); + int stores=0; + for( var bb : code._cfg ) + for( var node : bb.outs() ) + if( node instanceof com.seaofnodes.simple.node.cpus.x86_64_v2.StoreX86 st ) { + stores++; + assertEquals(-1,st.regmap(4).nextReg((short)15)); + } + assertEquals(1,stores); + } + } + + @Test public void testInlinedReturnValue() { + String src = """ +struct S { int x; }; +val f = { !S s -> s.x = g(); }; +val g = { -> 123; }; +!S !s = new S; +return f(s); +"""; + // The entry of g can disappear before its Return is folded into f. + // Exercise both worklist orders; deleting the entry does not kill 123. + for( int seed=0; seed<64; seed++ ) { + CodeGen code = new CodeGen(src,com.seaofnodes.simple.type.TypeInteger.BOT,seed,true).driver(CodeGen.Phase.TypeCheck); + assertEquals("seed "+seed, "123", Eval2.eval(code,0)); + } + } + + + @org.junit.Rule public final org.junit.rules.ErrorCollector _errors = new org.junit.rules.ErrorCollector(); + + @Test public void testAllocatorMasks() { com.seaofnodes.simple.codegen.RegAllocTestSupport.masks(); } + @Test public void testAllocatorUnion() { com.seaofnodes.simple.codegen.RegAllocTestSupport.union(); } + @Test public void testAllocatorCopyClobber() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyClobber(); } + @Test public void testAllocatorCommutativePhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.commutativePhi(); } + @Test public void testAllocatorKills() { com.seaofnodes.simple.codegen.RegAllocTestSupport.killWithoutResult(); } + @Test public void testAllocatorDependencies() { com.seaofnodes.simple.codegen.RegAllocTestSupport.nullUseMask(); } + @Test public void testAllocatorCloneClass() { com.seaofnodes.simple.codegen.RegAllocTestSupport.cloneRegisterClass(); } + + @Test public void testPrintingRegisters() throws Exception { + com.seaofnodes.simple.codegen.PrintRegTestSupport.check(); + } + + + @Ignore + @Test + public void testJig() { + CodeGen code = new CodeGen("return 0;"); + code.driver(CodeGen.Phase.TypeCheck); + assertEquals("return 0;", code._stop.toString()); + assertEquals("0", Eval2.eval(code, 2)); + } + + // Collect differences so every target runs; JUnit still fails the test. + private void testTarget(String src, String cpu, String os, int spills, String stop) { + _errors.checkSucceeds(() -> { testCPU(src,cpu,os,spills,stop); return null; }); + } + + static void testCPU(String src, String cpu, String os, int spills, String stop) { + CodeGen code = new CheckedCodeGen(src); + code.driver(CodeGen.Phase.RegAlloc,cpu,os); + SpillStats.record(code,"Chapter20",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); + if( stop!=null ) assertEquals(stop,code._stop.toString()); + } + + private void testAllCPUs( String src, int spills, String stop ) { + testTarget(src,"x86_64_v2", "SystemV",spills,stop); + testTarget(src,"riscv" , "SystemV",spills,stop); + testTarget(src,"arm" , "SystemV",spills,stop); + } + + @Test public void testAlloc0() { + testTarget("return new u8[arg];","x86_64_v2","SystemV",4,"return []u8;"); + testTarget("return new u8[arg];","riscv","SystemV",5,"return []u8;"); + testTarget("return new u8[arg];","arm","SystemV",5,"return []u8;"); + } + + @Test public void testBasic1() { + String src = "return arg | 2;"; + testTarget(src,"x86_64_v2", "SystemV",1,"return (ori,mov(arg));"); + testTarget(src,"riscv" , "SystemV",0,"return ( arg | #2 );"); + testTarget(src,"arm" , "SystemV",0,"return (ori,arg);"); + } + + @Test + public void testNewtonInteger() { + String src = +""" +// Newtons approximation to the square root +val sqrt = { int x -> + int guess = x; + while( 1 ) { + int next = (x/guess + guess)/2; + if( next == guess ) return guess; + guess = next; + } +}; +return sqrt(arg) + sqrt(arg+2); +"""; + testTarget(src,"x86_64_v2", "SystemV",40,null); + testTarget(src,"riscv" , "SystemV",17,null); + testTarget(src,"arm" , "SystemV",18,null); + } + + @Test + public void testNewtonFloat() { + String src = +""" +// Newtons approximation to the square root +val sqrt = { flt x -> + flt guess = x; + while( 1 ) { + flt next = (x/guess + guess)/2; + if( next == guess ) return guess; + guess = next; + } +}; +flt farg = arg; +return sqrt(farg) + sqrt(farg+2.0); +"""; + testTarget(src,"x86_64_v2", "SystemV",23,null); + testTarget(src,"riscv" , "SystemV",18,null); + testTarget(src,"arm" , "SystemV",18,null); + } + + @Test + public void testAlloc2() { + String src = "int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1];"; + testTarget(src,"x86_64_v2","SystemV",3,"return .[];"); + testTarget(src,"riscv","SystemV",6,"return .[];"); + testTarget(src,"arm","SystemV",6,"return .[];"); + } + + @Test + public void testArray1() { + String src = +""" +int[] !ary = new int[arg]; +// Fill [0,1,2,3,4,...] +for( int i=0; i + if( self == s ) return true; + if( self.cs# != s.cs# ) return false; + for( int i=0; i< self.cs#; i++ ) + if( self.cs[i] != s.cs[i] ) + return false; + return true; +}; + +val hashCode = { !String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; + +val _hashCodeString = { !String self -> + int hash=0; + if( self.cs ) { + for( int i=0; i< self.cs#; i++ ) + hash = hash*31 + self.cs[i]; + } + if( !hash ) hash = 123456789; + return hash; +}; + +!String !s = new String { cs = new u8[17]; }; +s.cs[0] = 67; // C +s.cs[1] = 108; // l +hashCode(s); +"""; + testTarget(src,"x86_64_v2", "SystemV",9,null); + testTarget(src,"riscv" , "SystemV",3,null); + testTarget(src,"arm" , "SystemV",0,null); + } + + @Test + public void testCast() { + String src = "struct Bar { int x; }; var b = arg ? new Bar; return b ? b.x++ + b.x++ : -1;"; + testTarget(src,"x86_64_v2","SystemV",1,null); + testTarget(src,"riscv","SystemV",2,null); + testTarget(src,"arm","SystemV",2,null); + } + + @Test + public void testFltArg() { + String src = "return {int i, flt f, int j->return i+f+j;};"; + testAllCPUs(src,0,null); + } + + @Test + public void testFlags1() { + String src = """ +bool b1 = arg == 1; +bool b2 = arg == 2; +if (b2) if (b1) return 1; +if (b1) return 2; +return 0; +"""; + testTarget(src,"x86_64_v2", "SystemV",0,"return Phi(Region,1,2,0);"); + testTarget(src,"riscv" , "SystemV",0,"return Phi(Region,1,2,0);"); + testTarget(src,"arm" , "SystemV",0,"return Phi(Region,1,2,0);"); + } + + @Test + public void testFlags2() { + String src = """ +bool b1 = arg == 1; +while (arg > 0) { + arg--; + if (b1) arg--; +} +return arg; +"""; + testTarget(src,"x86_64_v2", "SystemV",3,null); + testTarget(src,"riscv" , "SystemV",2,null); + testTarget(src,"arm" , "SystemV",2,null); + } + // Original Chapter 20 allocation workload, kept fixed for cohort comparisons. + @Test + public void testBrainfuck() { + var program = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.".getBytes(java.nio.charset.StandardCharsets.UTF_8); + var encoded = new StringBuilder("u8[] !program = new u8[").append(program.length).append("];"); + for (int i = 0; i < program.length; i++) { + int value = program[i] & 0xFF; + encoded.append("program[").append(i).append("] = ").append(value).append(";"); + } + + String src = encoded + """ + +int d = 0; +u8[] !output = new u8[0]; +u8[] !data = new u8[100]; + +for( int pc = 0; pc < program#; pc++ ) { + var command = program[pc]; + if (command == 62) { + d++; + } else if (command == 60) { + d--; + } else if (command == 43) { + data[d]++; + } else if (command == 45) { + data[d]--; + } else if (command == 46) { + // Output a byte; increase the output array size + var old = output; + output = new u8[output# + 1]; + for( int i = 0; i < old#; i++ ) + output[i] = old[i]; + output[old#] = data[d]; // Add the extra byte on the end + } else if (command == 44) { + data[d] = 42; + } else if (command == 91) { + if (data[d] == 0) { + for( int d = 1; d > 0; ) { + command = program[++pc]; + if (command == 91) d++; + if (command == 93) d--; + } + } + } else if (command == 93) { + if (data[d]) { + for( int d = 1; d > 0; ) { + command = program[--pc]; + if (command == 93) d++; + if (command == 91) d--; + } + } + } +} +return output; +"""; + testTarget(src,"x86_64_v2", "SystemV",40,null); + testTarget(src,"riscv" , "SystemV",28,null); + testTarget(src,"arm" , "SystemV",28,null); + //assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000)); + } + // Original Chapter 20 allocation workload, kept fixed for cohort comparisons. + @Test + public void testMergeSort() { + String src = +""" +// based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort + +val merge_sort = { int[] !a, int[] !b, int n -> + copy_array(a, 0, n, b); + split_merge(a, 0, n, b); +}; + +val split_merge = { int[] !b, int begin, int end, int[] a -> + if (end - begin <= 1) + return 0; + int middle = (end + begin) / 2; + split_merge(a, begin, middle, b); + split_merge(a, middle, end, b); + 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; + if (i < middle) { + if (j >= end) cond = true; + else if (a[i] <= a[j]) cond = true; + } + if (cond) b[k] = a[i++]; + 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]; +}; + +int[] !a = new int[arg]; +int[] !b = new int[a#]; + +for (int i = 0; i < a#; i++) + a[i] = a# - i; + +merge_sort(a, b, a#); + +return a; +"""; + testTarget(src,"x86_64_v2", "SystemV",52,null); + testTarget(src,"riscv" , "SystemV",44,null); + testTarget(src,"arm" , "SystemV",41,null); +//assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11)); + } + + + @Test public void testMemoryAllocation() { + for( String cpu : new String[]{"x86_64_v2","riscv","arm"} ) + for( String src : new String[]{Chapter10Test.NESTED_MEMORY,Chapter16Test.CONSTRUCTOR_MEMORY, + Chapter18Test.CALL_MEMORY,Chapter18Test.RECURSIVE_MEMORY, + "int[] !a = new int[3]; a[arg]=arg; return a[0]+1;"} ) { + var code = new CodeGen(src).driver(CodeGen.Phase.RegAlloc,cpu,"SystemV"); + com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); + code._stop.walk(n -> { + // Whole memory, precise Phis, and memory projections need no register. + if( n._type instanceof com.seaofnodes.simple.type.TypeMem ) + assertEquals(-1,code._regAlloc.regnum(n)); + if( n instanceof com.seaofnodes.simple.node.NewNode nn ) { + assertTrue(code._regAlloc.regnum(nn.proj(0))>=0); + assertEquals(-1,code._regAlloc.regnum(nn.proj(1))); + } + return null; + }); + } + } +} -- cgit v1.2.3