Split out incomplete type analysis

7 files changed, 107 insertions, 24 deletions

diff --git a/chapter-interprocedural-sccp/README.ja.md b/chapter-interprocedural-sccp/README.ja.md
index 21a5a381..4dec73c7 100644
--- a/chapter-interprocedural-sccp/README.ja.md
+++ b/chapter-interprocedural-sccp/README.ja.md
@@ -3,6 +3,7 @@
 [English](README.md) | 日本語
 
 [前: 関数内の SCCP](../chapter-sccp/README.ja.md) |
+[次: 型が確定する前の SSA 構築](../chapter-incomplete-types/README.ja.md) |
 [章の分割案](../docs/chapter-split.md)
 
 前の章では関数ごとに保守的な呼び出し境界で解析しました。この章では
diff --git a/chapter-interprocedural-sccp/README.md b/chapter-interprocedural-sccp/README.md
index d3b740a9..7310de80 100644
--- a/chapter-interprocedural-sccp/README.md
+++ b/chapter-interprocedural-sccp/README.md
@@ -3,12 +3,11 @@
 English | [日本語](README.ja.md)
 
 [Previous: SCCP Within a Function](../chapter-sccp/README.md) |
-[Split outline](../docs/chapter-split.md)
+[Next: SSA Before Types Are Known](../chapter-incomplete-types/README.md) |
 
-The previous chapter solves each function with conservative call interfaces.
-This chapter lets the same worklist discover call edges and propagate values
-between functions. It is an independent snapshot of the interprocedural
-compiler previously taught in Chapter 24.
+The previous chapter runs SCCP with each function, and assumes very
+conservative typing across calls.  This chapter lets the same worklist
+discover call edges and propagate values between functions.  
 
 ## Discovering calls while solving types
 
@@ -20,9 +19,10 @@ Such edges make up a [Call Graph](https://en.wikipedia.org/wiki/Call_graph).
 
 We extend the normal SCCP algorithm to observe when a `Call`s function pointer
 input changes - when it picks up new function targets.  There are only a finite
-number so we represent them exactly with *function indices* as described in an
-earlier chapter.  (Separate compilation adds a special index for the infinite
-unknown functions that are called outside this compilation unit).
+number so we represent them exactly with *function indices*, or *fidx*
+internally, as described earlier chapters.  (Separate compilation adds a
+special index for the infinite unknown functions that are called outside this
+compilation unit).
 
 Once we observe a new *fidx* at a `Call`, we *link* the `Call` with the `Fun`,
 and the `Return` with the `CallEnd`.  Such linkage acts exactly as-if we added
@@ -42,24 +42,37 @@ e.g. not-null) on all calling paths.
 
 ## Recursion is a loop in disguise
 
-An argument can flow from a Parm through arithmetic into a recursive call,
-then back to the same Parm. A result has a separate cycle: Return -> CallEnd
--> arithmetic -> Phi -> Return. Widening at Parm alone cannot stop a return
-range from growing in `f(x-1)+1`.
+We use the notion of *widening* integer ranges at loop heads, see Chapter XXX.
+This allows us to have a sharper notion of integers over `BOTTOM` without also
+allowing the lattice to fall 2^32 times.  The same issue arises during
+recursive calls: an argument can flow from a Parm through arithmetic into a
+recursive call, then back to the same Parm.
 
-Loop Phis, Parms, and CallEnds therefore need widening points. Their comments
-cross-reference each other. Constants and above-center ranges remain narrow;
-the growing below-center ranges widen within their type bounds.
+```simple
+val fact = { int x -> x ? 0 : f(x-1)+1; };
+```
+
+Here if we pass in `f(999)` , parameter `x` will have the integer range
+`[999]`.  We'll then track the recursive call to `f(998)` via normal SCCP 
+and realize the parameter `x` has a range `[999-998]`.  Lather, rinse, repeat 
+and we're at `[999-997]`.  We need to *widen* integer parameters at `Parms`
+not just loop-head `Phis`.  
+
+The same issue arises during the recursive return: the first return will be
+with `0` when `x` is zero, then we return `0+1` or the range `[0-1]` then range
+`[0-2]`, etc.  `CallEnds` also need to widen.
+
+Loop Phis, Parms, and CallEnds get widening points, and since this same issue
+hits in 3 unrelated places, their comments all cross-reference each other.
 
-`SccpTest` uses the same two calls as the previous chapter and checks that the
-parameter now receives [1,2]. `Chapter24Test.testRecursiveWidening` exercises
-argument and return cycles at several worklist seeds and evaluates the results.
 
 ## Unknown callers
 
-A function address that survives outside a direct call may be called by code
-we cannot see. Preserve its unknown-caller input. Precise escape analysis is
-introduced later; this chapter does not infer exposure through memory.
+A `FunPtrNode` (function address) that survives outside a direct call may be
+called by code we cannot see.  We have to assume the address escapes into
+unknown code, which later calls it.  We preserve its unknown-caller input,
+since we cannot tell what that unknown caller will pass.  Precise escape
+analysis is introduced later exactly to inmprove this.
 
 ## Building and checking
 
diff --git a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index ad48dd5d..af670bda 100644
--- a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -189,6 +189,12 @@ public class CodeGen {
     // the return is not part of the match).
     final Ary<FunNode> _linker = new Ary<>(FunNode.class);
 
+    // Native symbols belong to function identities, not to one ExternNode.
+    // Selection and spill copies can turn that node into an ordinary constant.
+    private final HashMap<TypeFunPtr,String> _externs = new HashMap<>();
+    public void externFunc(TypeFunPtr tfp, String name) { _externs.put(tfp.makeFrom(Type.BOTTOM),name); }
+    public String externFunc(TypeFunPtr tfp) { return _externs.get(tfp.makeFrom(Type.BOTTOM)); }
+
     // Parser object
     public final Parser P;
 
diff --git a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
index b5a8e148..019e3892 100644
--- a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
+++ b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
@@ -138,6 +138,10 @@ public class Encoding implements com.seaofnodes.isa.CodeSink {
     }
     public Encoding relo( ConstantNode con ) {
         TypeFunPtr tfp = (TypeFunPtr)con._con;
+        // A native address has no local FunNode. Keep its symbol even after
+        // selection or a spill copy has replaced the original ExternNode.
+        String name = _code.externFunc(tfp);
+        if( name!=null ) return external(con,name);
         _internals.put(con,_code.link(tfp));
         return this;
     }
diff --git a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/ExternNode.java b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/ExternNode.java
index ccbcfc66..7a26e2e9 100644
--- a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/ExternNode.java
+++ b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/ExternNode.java
@@ -13,7 +13,11 @@ import java.util.BitSet;
 
 public class ExternNode extends ConstantNode {
     public final String _extern;
-    public ExternNode(Type t, String ex) { super(t); _extern = ex; }
+    public ExternNode(Type t, String ex) {
+        super(t);
+        _extern = ex;
+        if( t instanceof TypeFunPtr tfp ) CodeGen.CODE.externFunc(tfp,ex);
+    }
 
     @Override public String  label() { return "#"+_con+":"+_extern; }
 
diff --git a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java
index 98a56089..2c41dc57 100644
--- a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java
+++ b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java
@@ -39,8 +39,9 @@ public class TFPARM extends ConstantNode implements MachNode, RIPRelSize {
             int base = opStart & ~0xFFF;
             delta = target-base;
             int adrp_delta = delta >> 12;
-            // patch upper 20 bits via adrp
-            enc.patch4(opStart, Arm64.adrp(1, adrp_delta & 0b11, 0b10000, adrp_delta >> 2, rpc));
+            // ADRP splits a signed page offset into two unsigned bit fields.
+            // Mask the high field too, including for an address below this PC.
+            enc.patch4(opStart, Arm64.adrp(1, adrp_delta & 0b11, 0b10000, (adrp_delta >> 2) & 0x7FFFF, rpc));
             // low 12 bits via add
             enc.patch4(opStart+4, Arm64.imm_inst_l(Arm64.OPI_ADD, delta & 0xfff, rpc));
         } else {
diff --git a/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/NativeAddressTest.java b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/NativeAddressTest.java
new file mode 100644
index 00000000..6d21ca5f
--- /dev/null
+++ b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/NativeAddressTest.java
@@ -0,0 +1,54 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.codegen.Encoding;
+import com.seaofnodes.isa.eval.EvalArm64;
+import com.seaofnodes.isa.eval.EvalRisc5;
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+public class NativeAddressTest {
+    @Test public void testReturnedNativeAddress() throws IOException {
+        Path dir = Path.of("build/objs");
+        Files.createDirectories(dir);
+        Files.writeString(dir.resolve("nativeAddress.smp"), """
+            val getAbs = { ->
+                { i32 -> i32 } abs = "C";
+                return abs;
+            };
+            """);
+        Files.writeString(dir.resolve("nativeAddress.c"), """
+            typedef int (*func)(int);
+            extern func getAbs(void);
+            int main(void) {
+                func f = getAbs();
+                return f(-7) != 7 || f(9) != 9;
+            }
+            """);
+        TestC.run("build/objs", "nativeAddress", "", -1);
+    }
+
+    @Test public void testEmulatedNativeAddress() throws IOException {
+        // No native call: return the address itself, patched to the emulator's
+        // known write entry. Both ports share Encoding's symbol lookup.
+        String src = "{ int -> int } write = \"C\"; return write;";
+        for( String cpu : new String[]{"arm","riscv"} ) {
+            CodeGen code = new CodeGen(src).driver(cpu,"SystemV",null);
+            byte[] bits = code._encoding.bits();
+            byte[] image = new byte[1<<20];
+            System.arraycopy(bits,0,image,0,bits.length);
+            if( cpu.equals("arm") ) {
+                EvalArm64 eval = new EvalArm64(image,1<<16);
+                assertEquals(0,eval.step(100));
+                assertEquals(Encoding.SENTINEL_WRITE,eval.regs[0]);
+            } else {
+                EvalRisc5 eval = new EvalRisc5(image,1<<16);
+                assertEquals(0,eval.step(100));
+                assertEquals(Encoding.SENTINEL_WRITE,eval.regs[10]);
+            }
+        }
+    }
+}