Remove several instances of extra whole-graph walks

6 files changed, 266 insertions, 9 deletions

diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/CallEndTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/CallEndTest.java
new file mode 100644
index 00000000..a174bdf7
--- /dev/null
+++ b/chapter28b/src/test/java/com/seaofnodes/simple/CallEndTest.java
@@ -0,0 +1,85 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+public class CallEndTest {
+    @Test public void testReturnWideningMonotonicity() {
+        new CodeGen("return 0;").parse();
+        TypeFunPtr sig = TypeFunPtr.make1((byte)2,true,TypeFunPtr.TEMPTY,TypeInteger.I32,100);
+        FunNode fun = new FunNode(null,sig,"f",null);
+        Node value = ConstantNode.raw(Type.TOP);
+        ReturnNode ret = new ReturnNode(ConstantNode.raw(Type.CONTROL),
+            ConstantNode.raw(TypeMem.START),value,null,fun);
+        Type[] inputs = new Type[]{Type.TOP,TypeInteger.TOP,TypeInteger.I32.dual(),
+            TypeInteger.ZERO,TypeInteger.constant(Long.MAX_VALUE),
+            TypeInteger.make(-1,1,(byte)0),TypeInteger.make(-1,1,(byte)1),
+            TypeInteger.make(-1,1,(byte)2),TypeInteger.make(-1,1,(byte)3),
+            TypeInteger.I32,TypeInteger.BOT,TypeScalar.BOT,Type.BOTTOM};
+        Type[] outputs = new Type[inputs.length];
+        for( int i=0; i<inputs.length; i++ ) {
+            value._type = inputs[i];
+            outputs[i] = ret.compute();
+        }
+        for( int i=0; i<inputs.length; i++ )
+            for( int j=0; j<inputs.length; j++ )
+                if( inputs[i].isa(inputs[j]) )
+                    assertTrue(inputs[i]+" -> "+inputs[j],outputs[i].isa(outputs[j]));
+    }
+
+    // Growing the target set must not narrow the result, even when the linked
+    // return has exhausted its integer widening budget.
+    @Test public void testUnknownTargetMonotonicity() {
+        CodeGen code = new CodeGen("return 0;").parse();
+        TypeFunPtr sig = TypeFunPtr.make1((byte)2,true,TypeFunPtr.TEMPTY,TypeInteger.BOT,100);
+        FunNode fun = new FunNode(null,sig,"f",null);
+        code._linker.setX(100,fun);
+        Node ctrl = ConstantNode.raw(Type.CONTROL);
+        Node mem = ConstantNode.raw(TypeMem.START);
+        Node value = ConstantNode.raw(TypeInteger.I32);
+        ReturnNode ret = new ReturnNode(ctrl,mem,value,null,fun);
+        ret._type = ret.compute();
+        Node fptr = ConstantNode.raw(sig.makeFrom(TypeInteger.I32));
+        CallNode call = new CallNode(null,ctrl,mem,fptr).init();
+        CallEndNode end = new CallEndNode(call,TypeRPC.BOT);
+        end.addDef(ret);
+        Type linked = end.compute();
+        TypeFunPtr unknown = TypeFunPtr.make(false,TypeFunPtr.TEMPTY,TypeInteger.I32);
+        assertTrue(fptr._type.isa(unknown));
+        fptr._type = unknown;
+        assertTrue("Adding unknown targets must only lose precision",linked.isa(end.compute()));
+    }
+
+    @Test public void testUnlinkedCallIsPhaseIndependent() {
+        CodeGen code = new CodeGen("return 0;").parse();
+        TypeFunPtr sig = TypeFunPtr.make1((byte)2,true,TypeFunPtr.TEMPTY,TypeInteger.I32,100);
+        CallNode call = new CallNode(null,ConstantNode.raw(Type.CONTROL),
+            ConstantNode.raw(TypeMem.START),ConstantNode.raw(sig)).init();
+        CallEndNode end = new CallEndNode(call,TypeRPC.BOT);
+        Type expected = TypeTuple.make(Type.CONTROL,TypeMem.BOT,TypeInteger.I32);
+        for( CodeGen.Phase phase : new CodeGen.Phase[]{CodeGen.Phase.Parse,
+                CodeGen.Phase.Opto,CodeGen.Phase.IterPostOpto} ) {
+            code._phase = phase;
+            assertSame(phase.toString(),expected,end.compute());
+        }
+    }
+
+    @Test public void testExternalTargets() {
+        CodeGen code = new CodeGen("return 0;").parse();
+        code.externFunc(100,"first");
+        code.externFunc(101,"second");
+        TypeFunPtr sig = TypeFunPtr.make1((byte)2,true,TypeFunPtr.TEMPTY,TypeInteger.I32,100);
+        Node fptr = ConstantNode.raw(sig);
+        CallNode call = new CallNode(null,ConstantNode.raw(Type.CONTROL),
+            ConstantNode.raw(TypeMem.START),fptr).init();
+        CallEndNode end = new CallEndNode(call,TypeRPC.BOT);
+        Type first = end.compute();
+        fptr._type = sig.meet(sig.makeFrom(101));
+        assertTrue(first.isa(end.compute()));
+        assertSame(TypeInteger.I32,((TypeTuple)end.compute()).ret());
+        assertSame(Type.BOTTOM,((TypeMem)((TypeTuple)end.compute()).mem())._t);
+    }
+}
diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java
index cdfd16a7..1001e691 100644
--- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java
+++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter20Test.java
@@ -216,7 +216,7 @@ for( int i=0; i<ary#-1; i++ )
 return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6
 """;
         testCPU(src,"x86_64_v2", "SystemV",-1,"return mov(.[]);");
-        testCPU(src,"riscv"    , "SystemV", 7,"return (add,.[],(mul,.[],1000));");
+        testCPU(src,"riscv"    , "SystemV", 9,"return (add,.[],(mul,.[],1000));");
         testCPU(src,"arm"      , "SystemV", 5,"return (add,.[],(mul,.[],1000));");
     }
 
@@ -256,9 +256,10 @@ val _hashCodeString = { !String self ->
     return hash;
 };
 """;
-        testCPU(src,"x86_64_v2", "SystemV",12,null);
-        testCPU(src,"riscv"    , "SystemV",6,null);
-        testCPU(src,"arm"      , "SystemV",6,null);
+        // The implicit return exposes _hashCodeString, so retain its body too.
+        testCPU(src,"x86_64_v2", "SystemV",21,null);
+        testCPU(src,"riscv"    , "SystemV",9,null);
+        testCPU(src,"arm"      , "SystemV",7,null);
     }
 
     @Test
diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java
index 2fcf65e9..d5b41ac9 100644
--- a/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java
+++ b/chapter28b/src/test/java/com/seaofnodes/simple/Chapter21Test.java
@@ -324,7 +324,7 @@ for( int i=0; i<ary#-1; i++ )
 return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6
 """;
         testCPU(src,"x86_64_v2", "SystemV",-1,"return mov(.[]);");
-        testCPU(src,"riscv"    , "SystemV", 7,"return (add,.[],(mul,.[],1000));");
+        testCPU(src,"riscv"    , "SystemV", 9,"return (add,.[],(mul,.[],1000));");
         testCPU(src,"arm"      , "SystemV", 5,"return (add,.[],(mul,.[],1000));");
     }
 
@@ -383,9 +383,10 @@ val _hashCodeString = { !String self ->
     return hash;
 };
 """;
-        testCPU(src,"x86_64_v2", "SystemV",12,null);
-        testCPU(src,"riscv"    , "SystemV",6,null);
-        testCPU(src,"arm"      , "SystemV",6,null);
+        // The implicit return exposes _hashCodeString, so retain its body too.
+        testCPU(src,"x86_64_v2", "SystemV",21,null);
+        testCPU(src,"riscv"    , "SystemV",9,null);
+        testCPU(src,"arm"      , "SystemV",7,null);
     }
 
     @Test public void testStringExport() throws IOException {
@@ -422,7 +423,7 @@ val _hashCodeString = { !String self ->
     return hash;
 };
 """;
-        TestC.runC(src, "stringHash", "",12);
+        TestC.runC(src, "stringHash", "",21);
     }
 
     @Test public void testLoop2() {
diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java
index 7f5fcd38..09391e4f 100644
--- a/chapter28b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java
+++ b/chapter28b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java
@@ -25,6 +25,31 @@ import org.junit.runners.model.Statement;
 import static org.junit.Assert.*;
 
 public class ClassInitDependenciesTest {
+    @Test public void testPrivateInitializerCallEdges() throws Exception {
+        for( long seed : new long[]{1,123,987654321} ) {
+            Path root = tempDir("private-roots-");
+            Path classes = Files.createDirectories(root.resolve("Root"));
+            Files.writeString(root.resolve("Root.smp"),"val _dead = _Dead; val read = { -> _Live.value; }; return 0;");
+            Files.writeString(classes.resolve("_Live.smp"),"int value = 17+arg;");
+            Files.writeString(classes.resolve("_Dead.smp"),"val child = Child; int value = 99;");
+            Path children = Files.createDirectories(classes.resolve("_Dead"));
+            Files.writeString(children.resolve("Child.smp"),"int value = 42;");
+            CodeGen code = new CodeGen(root.toString(),root.resolve("obj").toString(),null,
+                "Root",null,seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck);
+            FunNode live = code.link(code._compunits.get("Root/_Live"));
+            assertNotNull(live);
+            assertFalse("A local init call is not an unknown caller",live.unknownCallers());
+            assertTrue(live.in(1) instanceof CProjNode call && call.in(0) instanceof CLInitNode);
+            for( FunNode fun : code._linker )
+                assertTrue(fun==null || fun.isDead() ||
+                    fun._compunit!=code._compunits.get("Root/_Dead") &&
+                    fun._compunit!=code._compunits.get("Root/_Dead/Child"));
+            assertEquals("0",Eval2.eval(code,99));
+            new CodeGen(root.toString(),root.resolve("obj").toString(),null,
+                "Root",null,seed,true,TypeInteger.BOT).driver(CodeGen.Phase.Encoding,"x86_64_v2","SystemV");
+        }
+    }
+
     private final ArrayList<Path> dirs = new ArrayList<>();
 
     @Rule public final TestRule cleanup = (test, description) -> new Statement() {
diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java
index 7d42f924..cfaa0456 100644
--- a/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java
+++ b/chapter28b/src/test/java/com/seaofnodes/simple/SelectiveLoadingTest.java
@@ -10,6 +10,137 @@ import org.junit.Test;
 import static org.junit.Assert.*;
 
 public class SelectiveLoadingTest {
+    @Test public void testUnreachableImportIsNotARoot() throws Exception {
+        Path root = library("dead-import-");
+        Ary<String> paths = new Ary<>(new String[]{root.toString()});
+        object(root,paths,"Unused","val run_noInline = { int n -> n+1; };");
+        for( long seed : new long[]{1,123,987654321} ) {
+            CodeGen code = new CodeGen(null,root.toString(),paths,"Main","""
+                val _false_noInline = { -> false; };
+                if( _false_noInline() ) return Unused.run_noInline(arg);
+                return 7;
+                """,seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck);
+            CompUnit unused = code._compunits.get("Unused");
+            assertNotNull("Parsing loaded the declaration",unused);
+            for( FunNode fun : code._linker )
+                assertTrue(fun==null || fun.isDead() || fun._compunit!=unused);
+            assertEquals("7",Eval2.eval(code,0));
+        }
+    }
+
+    private static Path library(String prefix) throws IOException {
+        Path base = Files.createDirectories(Path.of("build/objs/selective"));
+        return Files.createTempDirectory(base,prefix);
+    }
+
+    @Test public void testImportedCallbackChain() throws Exception {
+        Path root = library("callback-chain-");
+        Ary<String> paths = new Ary<>(new String[]{root.toString()});
+        object(root,paths,"L0","val relay_noInline = { {int->int} f -> f; };");
+        for( int i = 1; i<6; i++ )
+            object(root,paths,"L"+i,"val relay_noInline = { {int->int} f -> L"+(i-1)+".relay_noInline(f); };");
+        for( long seed : new long[]{1,123,987654321} ) {
+            CodeGen code = new CodeGen(null,root.toString(),paths,"Main","""
+                val _increment_noInline = { int n -> n+1; };
+                val _decrement_noInline = { int n -> n-1; };
+                val f = L5.relay_noInline(arg ? _increment_noInline : _decrement_noInline);
+                return f(41);
+                """,seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck);
+            assertNotNull(function(code,"relay_noInline").summary());
+            assertEquals("42",Eval2.eval(code,1));
+            assertEquals("40",Eval2.eval(code,0));
+        }
+    }
+
+    @Test public void testImportedCallbackReturn() throws Exception {
+        Path root = library("callback-return-");
+        Ary<String> paths = new Ary<>(new String[]{root.toString()});
+        object(root,paths,"Relay","val relay = { {int->int} f -> f; };");
+        for( long seed : new long[]{1,123,987654321} ) {
+            CodeGen code = new CodeGen(null,root.toString(),paths,"Main","""
+                val _increment_noInline = { int n -> n+1; };
+                val f = Relay.relay(_increment_noInline);
+                return f(arg);
+                """,seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck);
+            assertNull(function(code,"relay").summary());
+            assertEquals("42",Eval2.eval(code,41));
+            assertEquals("1",Eval2.eval(code,0));
+        }
+    }
+
+    @Test public void testImportedFunctionField() throws Exception {
+        Path root = library("function-field-");
+        Ary<String> paths = new Ary<>(new String[]{root.toString()});
+        object(root,paths,"Targets","var chosen = { int n -> n+1; };");
+        object(root,paths,"Apply","val run = { int n -> val f = Targets.chosen; return f(n); };");
+        for( long seed : new long[]{1,123,987654321} ) {
+            CodeGen code = new CodeGen(null,root.toString(),paths,"Main",
+                "return Apply.run(arg);",seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck);
+            assertNull(function(code,"run").summary());
+            assertEquals("42",Eval2.eval(code,41));
+            assertEquals("1",Eval2.eval(code,0));
+        }
+    }
+
+    @Test public void testImportedUnknownCallback() throws Exception {
+        Path root = library("unknown-callback-");
+        Ary<String> paths = new Ary<>(new String[]{root.toString()});
+        object(root,paths,"Apply","""
+            val apply = { {int->int} f,int n -> f(n); };
+            val apply_noInline = { {int->int} f,int n -> f(n); };
+            """);
+        for( String target : new String[]{"apply","apply_noInline","forward_noInline"} )
+            for( long seed : new long[]{1,123,987654321} ) {
+                CodeGen code = new CodeGen(null,root.toString(),paths,"Main",
+                    "val _increment_noInline = { int n -> n+1; }; "+
+                    "val forward_noInline = { {int->int} f,int n -> Apply.apply_noInline(f,n); }; return "+
+                    (target.equals("forward_noInline") ? target : "Apply."+target)+"(_increment_noInline,arg);",
+                    seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck);
+                assertEquals("42",Eval2.eval(code,41));
+                assertEquals("1",Eval2.eval(code,0));
+            }
+        CodeGen nativeCode = new CodeGen(null,root.toString(),paths,"NativeCallback","""
+            val _increment_noInline = { int n -> n+1; };
+            val run = { int n -> Apply.apply_noInline(_increment_noInline,n); };
+            """,123,true,TypeInteger.BOT).driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false);
+        Path driver = root.resolve("driver.c");
+        Files.writeString(driver,"""
+            __attribute__((CALL_CONV)) extern long long run(long long);
+            int main(void) { return run(41)==42 && run(0)==1 ? 0 : 1; }
+            """);
+        String exe = root.resolve(TestC.OS.startsWith("Windows") ? "test.exe" : "test").toString();
+        assertEquals("",TestC.gcc(nativeCode,
+            TestC.CALL_CONVENTION.equals("win64") ? "ms_abi" : "sysv_abi",driver.toString(),null,exe));
+    }
+
+    @Test public void testUnknownCallbackEncoding() {
+        for( String cpu : new String[]{"x86_64_v2","arm","riscv"} )
+            new CodeGen("val apply = { {int->int} f,int n -> f(n); };")
+                .driver(CodeGen.Phase.Encoding,cpu,"SystemV");
+    }
+
+    @Test public void testImportedCallbackInitCycle() throws Exception {
+        Path root = library("callback-cycle-");
+        Path src = Files.createDirectory(root.resolve("src"));
+        Ary<String> paths = new Ary<>(new String[]{root.toString()});
+        object(root,paths,"Apply","val apply_noInline = { {int->int} f,int n -> f(n); };");
+        write(src,"Root","val entry = A.value;");
+        write(src,"Root/A","val callback = { int n -> B.value; }; int value = Apply.apply_noInline(callback,1);");
+        write(src,"Root/B","int value = A.value;");
+        for( long seed : new long[]{1,123,987654321} ) {
+            try {
+                new CodeGen(src.toString(),root.toString(),paths,"Root",null,seed,true,TypeInteger.BOT)
+                    .driver(CodeGen.Phase.TypeCheck);
+                fail("The unknown callback can close an initialization cycle");
+            } catch( Parser.ParseException ex ) {
+                assertTrue(ex.getMessage(),ex.getMessage().startsWith("Cyclic class initialization:"));
+                assertTrue(ex.getMessage(),ex.getMessage().contains("Root.A"));
+                assertTrue(ex.getMessage(),ex.getMessage().contains("Root.B"));
+                assertTrue(ex.getMessage(),ex.getMessage().contains("unknown call"));
+            }
+        }
+    }
+
     @Test public void testCycleRefinementLoadsConditionHelper() throws Exception {
         Path base = Path.of("build/objs/selective");
         Files.createDirectories(base);
diff --git a/chapter28b/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter28b/src/test/java/com/seaofnodes/simple/TypeTest.java
index f6099607..113676ff 100644
--- a/chapter28b/src/test/java/com/seaofnodes/simple/TypeTest.java
+++ b/chapter28b/src/test/java/com/seaofnodes/simple/TypeTest.java
@@ -7,6 +7,20 @@ import static org.junit.Assert.assertSame;
 
 public class TypeTest {
 
+    @Test public void testBoundedBits() {
+        int[] sparse = XInt.make(XInt.make(2),65);
+        for( int[] bits : new int[][]{XInt.EMPTY,XInt.FULL,sparse,XInt.dual(sparse)} )
+            for( int limit : new int[]{0,1,32,65,66,100} ) {
+                int next = XInt.next(bits,-1,limit);
+                for( int bit=0; bit<limit; bit++ )
+                    if( XInt.bit(bits,bit) ) {
+                        Assert.assertEquals(bit,next);
+                        next = XInt.next(bits,next,limit);
+                    }
+                Assert.assertEquals(-1,next);
+            }
+    }
+
     // Removing zero must not reset the widening history of a remaining range.
     @Test public void testNonZeroWidening() {
         for( byte widen=0; widen<=3; widen++ ) {