Chapter 25: Modules, Separate Compilation, and SSA Constructionlinear

Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@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 <jun784@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

1 files changed, 142 insertions, 223 deletions

diff --git a/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/src/test/java/com/seaofnodes/simple/Chapter23Test.java
index 884e77e5..053621bd 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter23Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter23Test.java
@@ -11,7 +11,6 @@ import com.seaofnodes.simple.type.*;
 
 import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.cpus.riscv.riscv;
-import com.seaofnodes.simple.type.TypeInteger;
 import java.io.IOException;
 import java.nio.file.Files;
 import java.nio.file.Path;
@@ -25,7 +24,7 @@ public class Chapter23Test {
     @Test public void testDiagnosticTypeAccessors() throws Exception {
         new CodeGen("return 0;").parse();
         var tfp = TypeFunPtr.TEST;
-        var con = new ConstantNode(tfp);
+        var con = ConstantNode.raw(tfp);
         var call = new CallNode(null,con,con,con);
         var field = Type.class.getDeclaredField("VISIT");
         field.setAccessible(true);
@@ -45,335 +44,252 @@ public class Chapter23Test {
     }
 
 
-    @Test
-    public void testOrRhsLoopLocal() throws IOException {
-        checkOrRhsLoop("""
-            struct S { int f; };
-            int x = 0;
-            int result = (arg & 1) || (new S {
-                while (x < 3) x++;
-                f = ++x;
-            }).f;
-            return x * 10 + result;
-            """);
-    }
-
-    @Test
-    public void testOrRhsLoopMemory() throws IOException {
-        checkOrRhsLoop("""
-            struct S { int f; };
-            !S !s = new S;
-            int result = (arg & 1) || (new S {
-                while (s.f < 3) s.f++;
-                s.f++;
-                f = s.f;
-            }).f;
-            return s.f * 10 + result;
-            """);
-    }
-
-    private static void checkOrRhsLoop(String src) throws IOException {
-        CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV", null);
-        SpillStats.record(code,"Chapter23","riscv","SystemV");
-        for (int arg : new int[]{0, 1, 2, 3}) {
-            byte[] image = new byte[1 << 20];
-            System.arraycopy(code._encoding.bits(), 0, image, 0, code._encoding._bits.size());
-            EvalRisc5 r5 = new EvalRisc5(image, 1 << 16);
-            r5.regs[riscv.A0] = arg;
-            assertEquals("Execution must finish", 0, r5.step(1000));
-            // False LHS runs the loop and final increment, returning 4.
-            // True LHS skips all RHS effects and returns the LHS value, 1.
-            assertEquals("OR result and side effects for arg=" + arg,
-                (arg & 1) == 0 ? 44 : 1, r5.regs[riscv.A0]);
-        }
-    }
-
-    @Ignore
-    @Test
+    @Test @Ignore
     public void testJig() throws IOException {
-        String src =
-"""
-var apply = { i64 x, { i64 -> u32 } fcn ->
-    return fcn(x);
-}
-""";
+        //String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp"));
+        String src = Files.readString(Path.of("docs/examples/BubbleSort.smp"));
+        testCPU(src,"x86_64_v2", "win64"  ,-1,null);
+        testCPU(src,"riscv"    , "SystemV",-1,null);
+        testCPU(src,"arm"      , "SystemV",-1,null);
     }
 
 
     static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) {
         CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os);
-        SpillStats.record(code,"Chapter23",cpu,os);
-        SpillStats.checkSpills(spills,code._regAlloc._spillScaled);
+        int delta = spills>>3;
+        if( delta==0 ) delta = 1;
+        if( spills != -1 && !CodeGen.iterSeedOverridden() )
+            assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta);
         if( stop != null )
-            assertEquals(stop, code._stop.toString());
+            assertEquals(stop, code.print());
         return code;
     }
 
     @Test
     public void testOr() throws IOException {
-        String src =
-                """
-                int a = 1;
-                int b = 0;
-                
-                if(a++ || b++ ) {
-                    if(b == 0 && a == 2) {
-                        sys.io.p("Or");
-                    }
-                } else{
-                    sys.io.p("And");
-                }
-                return 0;
-                """;
-
-        TestC.runSF("or1", src, null, "Or", 0);
+        String src = """
+int a = 1;
+int b = 0;
+int rez = 2;
+
+if( a++ || b++ ) {
+    if( b == 0 && a == 2 )
+        rez = 0; // Expected answer
+} else {
+    rez = 1;
+}
+return rez;
+""";
+
+        TestC.runSF( src, "or1", "", 0);
 
         // Evaluate on RISC5 emulator
-        EvalRisc5 R5 = TestRisc5.build("or1", src, 0, 2, false);
+        EvalRisc5 R5 = TestRisc5.build( src, "or1", 0, 0, false);
         int trap = R5.step(100);
         assertEquals(0,trap);
         assertEquals(0,R5.regs[riscv.A0]);
-        assertEquals("Or",R5._stdout.toString());
 
         // Evaluate on ARM emulator
-        EvalArm64 arm = TestArm64.build("or1", src,0, 2, false);
+        EvalArm64 arm = TestArm64.build("or1", src,0, 0, false);
         trap = arm.step(100);
         assertEquals(0,trap);
         assertEquals(0,arm.regs[0]);
-        assertEquals("Or",arm._stdout.toString());
     }
 
     @Test
     public void testAnd() throws IOException {
-        String src =
-                """
-                int a = 1;
-                int b = 1;
-                
-                if(a && b) {
-                    sys.io.p("And");
-                } else {
-                    sys.io.p("Or");
-                }
-                return 0;
-                """;
-        TestC.runSF("and1", src, null, "And", 0);
+        String src = """
+int a = 1;
+int b = 1;
+return a && b ? 0 : 1;  // Expected answer 0
+""";
+        TestC.runSF( src, "and1", "", 0);
 
         // Evaluate on RISC5 emulator
-        EvalRisc5 R5 = TestRisc5.build("and1", src, 0, 2, false);
+        EvalRisc5 R5 = TestRisc5.build( src, "and1", 0, 0, false);
         int trap = R5.step(100);
         assertEquals(0,trap);
         assertEquals(0,R5.regs[riscv.A0]);
-        assertEquals("And",R5._stdout.toString());
 
         // Evaluate on ARM emulator
-        EvalArm64 arm = TestArm64.build("and1", src, 0, 2, false);
+        EvalArm64 arm = TestArm64.build("and1", src, 0, 0, false);
         trap = arm.step(100);
         assertEquals(0,trap);
         assertEquals(0,arm.regs[0]);
-        assertEquals("And",arm._stdout.toString());
+    }
+
+    @Test
+    public void testLogicalValueSemantics() {
+        assertEquals("42", Eval2.eval(new CodeGen("return 7 && 42;").parse().opto(), 0));
+        assertEquals("0",  Eval2.eval(new CodeGen("return 0 && 42;").parse().opto(), 0));
+        assertEquals("7",  Eval2.eval(new CodeGen("return 7 || 42;").parse().opto(), 0));
+        assertEquals("42", Eval2.eval(new CodeGen("return 0 || 42;").parse().opto(), 0));
+    }
+
+    @Test
+    public void testMixedScalarNotPhiPredicate() {
+        CodeGen code = new CodeGen("""
+struct S {};
+S? s = arg ? new S;
+return !(!s || !arg) ? 1 : 0;
+""");
+        code.parse().opto().typeCheck();
+        assertEquals("0", Eval2.eval(code, 0));
+        assertEquals("1", Eval2.eval(code, 1));
     }
 
     @Test
     public void testAndPtr() throws IOException {
         // Todo: have one src here
-        String src =
-                """
-                struct S { !S? !fld; };
-                val ptr = arg == 1 ? null : new S{fld = arg==1 ? null : new S{fld = null;};};
-                return ptr && ptr.fld ? "true" : "false";
-                """;
-        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;
-                """;
+        String src = """
+struct S { !S? !fld; new S = { !S? f -> fld=f; }; };
+val ptr = arg == 1 ? null : new S(arg==1 ? null : new S(null));
+return ptr && ptr.fld ? "true" : "false";
+""";
         CodeGen code = new CodeGen(src).parse().opto().typeCheck();
-        assertEquals("[97-117][ 116,114,117,101]", Eval2.eval(code, 0));
+        assertEquals("true", Eval2.eval(code, 0));
 
         // Evaluate on RISC5 emulator
-        EvalRisc5 R5 = TestRisc5.build("ptrand",src2, 1, 8, false);
+        EvalRisc5 R5 = TestRisc5.build( src, "class:Test.<clinit>", 1, 12, false);
         int trap = R5.step(100);
         assertEquals(0,trap);
-        assertEquals(0,R5.regs[riscv.A0]);
-        assertEquals("false",R5._stdout.toString());
+        int adr = (int)R5.regs[riscv.A0]; // Returns a Simple *u8[~] string
+        assertEquals(4,R5.ld4s(adr)); // String length
+        assertEquals(0x65757274,R5.ld4s(adr+4)); // "true"
 
         // Evaluate on ARM emulator
-        EvalArm64 arm = TestArm64.build("ptrand", src2, 1, 8, false);
+        EvalArm64 arm = TestArm64.build("class:Test.<clinit>", src, 1, 12, false);
         trap = arm.step(100);
         assertEquals(0,trap);
-        assertEquals(0,arm.regs[0]);
-        assertEquals("false",arm._stdout.toString());
+        int adr2 = (int)arm.regs[0]; // Returns a Simple *u8[~] string
+        assertEquals(4,arm.ld4s(adr2)); // String length
+        assertEquals(0x65757274,arm.ld4s(adr2+4)); // "true"
     }
 
     // conditional side effect
     @Test
     public void testCondSideEffAnd() throws IOException {
-        String src =
-                """
-                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 {
-                    sys.io.p("Not effected");
-                }
-                return 0;
-                """;
-
-        TestC.runSF("and2", src, null, "Effected", 0);
+        String src = """
+int x=1;
+int y=1;
+int z=0;
+
+int g = x++ && y++ && z++;
+return x == 2 && y == 2 && z == 1 && g == 0
+    ? 0  // Effected, Expected
+    : 1; // Error, not effected
+""";
+
+        TestC.runSF( src, "and2", "", 0);
 
         // Evaluate on RISC5 emulator
-        EvalRisc5 R5 = TestRisc5.build("and2", src, 0, 2, false);
+        EvalRisc5 R5 = TestRisc5.build( src, "and2", 0, 0, false);
         int trap = R5.step(100);
         assertEquals(0,trap);
         assertEquals(0,R5.regs[riscv.A0]);
-        assertEquals("Effected",R5._stdout.toString());
 
         // Evaluate on ARM emulator
-        EvalArm64 arm = TestArm64.build("and2", src, 0, 2, false);
+        EvalArm64 arm = TestArm64.build("and2", src, 0, 0, false);
         trap = arm.step(100);
         assertEquals(0,trap);
         assertEquals(0,arm.regs[0]);
-        assertEquals("Effected",arm._stdout.toString());
     }
 
     @Test
     public void testCondSideEffOr() throws IOException {
-        String src =
-                """
-                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;
-                } else {
-                    switch = 1;
-                }
-                int cd = 1;
-                if((x == 0 && y == 1 && z==-1) && switch && g) {
-                    sys.io.p("Effected");
-                } else {
-                    sys.io.p("Not effected");
-                }
-                return 0;
-                """;
-        TestC.runSF("or2", src, null, "Effected", 0);
+        String src = """
+int x = -1;
+int y =  1;
+int z = -1;
+int g = x++ || y++ || z++;
+int switch = (x == 4 || y == 4 || z == 4) ? -1 : 1;
+return (x == 0 && y == 1 && z==-1) && switch && g
+    ? 0   // Effected, expected
+    : 1;  // Error
+""";
+        TestC.runSF( src, "or2", "", 0);
 
         // Evaluate on RISC5 emulator
-        EvalRisc5 R5 = TestRisc5.build("or2", src, 0, 2, false);
+        EvalRisc5 R5 = TestRisc5.build( src, "or2", 0, 0, false);
         int trap = R5.step(100);
         assertEquals(0,trap);
         assertEquals(0,R5.regs[riscv.A0]);
-        assertEquals("Effected",R5._stdout.toString());
 
         // Evaluate on ARM emulator
-        EvalArm64 arm = TestArm64.build("or2", src, 0, 2, false);
+        EvalArm64 arm = TestArm64.build("or2", src, 0, 0, false);
         trap = arm.step(100);
         assertEquals(0,trap);
         assertEquals(0,arm.regs[0]);
-        assertEquals("Effected",arm._stdout.toString());
     }
 
     // test it with function calls
     @Test
     public void testFuncCall() throws IOException {
-        String src =
-                """
-                // -*- mode: java;  -*-
-                int a = 1;
-                int b = 1;
-                
-                var sq = { int x ->
-                    x*x;
-                };
-                
-                if(a && sq(0)) {
-                    sys.io.p("And");
-                } else {
-                    sys.io.p("Or");
-                }
-                return 0;
-                """;
-        TestC.runSF("and3", src, null, "Or", 0);
+        String src = """
+int a = 1;
+int b = 1;
+var sq_noInline = { int x ->
+    x*x;
+};
+return (a && sq_noInline(0))
+    ? 1  // Error
+    : 0; // Expected
+""";
+        TestC.runSF( src, "and3", "", 2);
 
         // Evaluate on RISC5 emulator
-        EvalRisc5 R5 = TestRisc5.build("and3", src, 0, 2, false);
+        EvalRisc5 R5 = TestRisc5.build( src, "and3", 0, 2, false);
         int trap = R5.step(100);
         assertEquals(0,trap);
         assertEquals(0,R5.regs[riscv.A0]);
-        assertEquals("Or",R5._stdout.toString());
 
         // Evaluate on ARM emulator
         EvalArm64 arm = TestArm64.build("and3", src, 0, 2, false);
         trap = arm.step(100);
         assertEquals(0,trap);
         assertEquals(0,arm.regs[0]);
-        assertEquals("Or",arm._stdout.toString());
     }
 
 
     @Test
     public void testFRefFields() {
-        String src =
-"""
+        String src = """
 // A hypothetical scanner class
-struct Scan {
+struct _Scan {
     int !x;
     u8[~] !buf;
+    new _Scan = { u8[~] b -> buf=b; };
     // Skip whitespace
-    val skip = { !Scan s ->
-        while( s.buf[s.x] <= ' ' )
-            s.x++;
+    val skip = { ->
+        while( buf[x] <= ' ' )
+            x++;
     };
     // Peek a character; if matched consume it, else false.
-    val peek = { !Scan !s, u8 c ->
-        skip(s);
-        if( s.buf[s.x] != c ) return false;
-        s.x++;
+    val peek = { u8 c ->
+        skip();
+        if( buf[x] != c ) return false;
+        x++;
         return true;
     };
 };
-!Scan !s = new Scan{ buf = "  q"; };
-return Scan.peek(s,'q');
-        """;
+!_Scan !_s = new _Scan("  q");
+return _s.peek('q');
+""";
 
         CodeGen code = new CodeGen(src).parse().opto().typeCheck();
-        assertEquals("return Phi(Region,0,1);", code._stop.toString());
+        assertEquals("return Phi(Region,0,1);", code.print());
         assertEquals("1", Eval2.eval(code, 0));
-        testCPU(src,"x86_64_v2", "Win64"  ,23,null);
+        testCPU(src,"x86_64_v2", "win64",23,null);
     };
 
     @Test
     public void testFRefFields2() {
-        String src =
-"""
+        String src ="""
 // A hypothetical scanner class
-struct Scan {
+struct _Scan {
     int !x;
     u8[~] !buf;
+    new _Scan = { u8[~] b -> buf=b; };
     // Skip whitespace
     val skip = { ->
         while( buf[x] <= ' ' )
@@ -381,23 +297,26 @@ struct Scan {
         return self;
     };
 };
-~Scan s = new Scan{ buf = "  q"; };
+~_Scan s = new _Scan("  q");
 return s.skip().x;
-        """;
+""";
 
         try { new CodeGen(src).parse().opto().typeCheck(); fail(); }
-        catch( Exception e ) { org.junit.Assert.assertTrue(e.getMessage().startsWith("Argument #0 isa")); }
+        catch( Exception e ) {
+            // Bad error message, but basically requires a mutable 'x' field.
+            org.junit.Assert.assertTrue(e.getMessage().startsWith("Argument #0 isa"));
+        }
     };
 
 
     @Test
     public void testMethod() {
-        String src =
-"""
+        String src = """
 // A hypothetical scanner class
-struct Scan {
+struct _Scan {
     int !x;
     u8[~] !buf;
+    new _Scan = { u8[~] b -> buf=b; };
     // Skip whitespace
     val skip = { ->
         while( buf[x] <= ' ' )
@@ -408,14 +327,14 @@ struct Scan {
         buf[x++]==ch;
     };
 };
-!Scan !s = new Scan{ buf = "  [1,2]"; };
-return s.require('[');
-        """;
+!_Scan !_s = new _Scan("  [1,2]");
+return _s.require('[');
+""";
 
         CodeGen code = new CodeGen(src).parse().opto().typeCheck();
-        assertEquals("return (.[]==91);", code._stop.toString());
+        assertEquals("return (.[]==91);", code.print());
         assertEquals("1", Eval2.eval(code, 0));
-        testCPU(src,"x86_64_v2", "Win64"  ,4,null);
+        testCPU(src,"x86_64_v2", "win64",4, null);
     };