Backport FunPtr

Helps keep functions alive via ptr only (no calls).
A few RISC 5 TFP encoding fixes.

15 files changed, 133 insertions, 20 deletions

diff --git a/chapter24/src/main/java/com/seaofnodes/simple/Parser.java b/chapter24/src/main/java/com/seaofnodes/simple/Parser.java
index cd4d5afb..14af367d 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/Parser.java
@@ -1678,7 +1678,7 @@ public class Parser {
         // Make a concrete function type, with a fidx
         TypeFunPtr tfp = _code.makeFun(TypeFunPtr.make(false,false,ts.asAry(),Type.BOTTOM));
         ReturnNode ret = parseFunctionBody(tfp,loc,ids.asAry());
-        return con(ret._fun.sig());
+        return new FunPtrNode(ret._fun.sig(),ret).peephole();
     }
 
     /**
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index 274fb2c7..3ae22b68 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -321,6 +321,8 @@ public class CodeGen {
 
         // Produce a machine node from n; map it to flag as done so stops cycles.
         map.put(n, x=_mach.instSelect(n) );
+        // Stop retains the callable body. Its lifetime edge is not a machine operand.
+        if( n instanceof FunPtrNode ) x._inputs.pop();
         // Walk machine op and replace inputs with mapped inputs
         for( int i=0; i < x.nIns(); i++ )
             x._inputs.set(i, _instSelect(x.in(i),map) );
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
index 8f9e2981..b6267600 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
@@ -222,6 +222,7 @@ public class ElfFile {
                 i++;
             int end = _code._encoding._opStart[ret._nid] + _code._encoding._opLen[ret._nid];
 
+            if( fun._name==null ) continue; // Anonymous addresses are relocated within .text.
             Symbol func = new Symbol(fun._name, text._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC);
             func._value = _code._encoding._opStart[fun._nid];
             func._size = end - func._value;
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/Opto.java
index f8ce1e54..cd52aadd 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/Opto.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/Opto.java
@@ -117,11 +117,14 @@ abstract public class Opto {
 
     // Function is public (callable from Start directly).
     // - Always true for main
-    // - Never true for stdlib, or anonymous functions
+    // - True for function addresses used as values
+    // - Otherwise false for stdlib or anonymous functions
     // - Named functions use `!wholeWorld`
     private static boolean funIsPublic( CodeGen code, boolean wholeWorld, FunNode fun ) {
         // Always true for main
         if( fun.sig().fidx() == code._main.fidx() ) return true;
+        // No escape analysis yet: a surviving address may be called from outside.
+        if( fun.hasPtr() ) return true;
         // Never true for stdlib or anonymous functions
         if( fun._name == null || fun._name.startsWith("sys.") )
             return false;
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 89289cfc..d3fe328a 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -27,6 +27,10 @@ public class ConstantNode extends Node {
     public static Node make( Type type ) {
         if( type==Type. CONTROL ) return new CtrlNode();
         if( type==Type.XCONTROL ) return new XCtrlNode();
+        if( type instanceof TypeFunPtr tfp && tfp.isConstant() && tfp.notNull() ) {
+            FunNode fun = CodeGen.CODE.link(tfp);
+            if( fun!=null && !fun.isDead() ) return new FunPtrNode(tfp,fun.ret());
+        }
         return new ConstantNode(type);
     }
 
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/FunNode.java
index 508dc63d..70e1c200 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/node/FunNode.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/node/FunNode.java
@@ -61,6 +61,16 @@ public class FunNode extends RegionNode {
     public void setRet(ReturnNode ret) { _ret=ret; }
     public ReturnNode ret() { assert _ret!=null; return _ret; }
 
+    // Direct calls are known; any other use of an address may have unknown callers.
+    public boolean hasPtr() {
+        for( Node use : ret()._outputs )
+            if( use instanceof FunPtrNode )
+                for( Node user : use._outputs )
+                    if( !(user instanceof CallNode call) || call.fptr()!=use ||
+                        call._inputs.find(use)!=call.nIns()-1 ) return true;
+        return false;
+    }
+
     // Signature can improve over time
     public TypeFunPtr sig() { return _sig; }
     public void setSig( TypeFunPtr sig ) {
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java
new file mode 100644
index 00000000..7f32698e
--- /dev/null
+++ b/chapter24/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java
@@ -0,0 +1,13 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.TypeFunPtr;
+
+// A function address keeps its body alive, even without a linked Call.
+public class FunPtrNode extends ConstantNode {
+    public FunPtrNode(TypeFunPtr tfp, ReturnNode ret) {
+        super(tfp);
+        addDef(ret);
+    }
+    public ReturnNode ret() { return (ReturnNode)in(1); }
+    @Override public String uniqueName() { return "FunPtr_"+_nid; }
+}
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter24/src/main/java/com/seaofnodes/simple/node/Node.java
index 5583d3d6..c746d7d5 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -261,8 +261,11 @@ public abstract class Node implements Cloneable {
         while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes
             Node old_def = _inputs.removeLast();
             // Revisit neighbor because removed use
-            if( old_def != null && CODE.add(old_def).delUse(this) )
-                old_def.kill(); // If we removed the last use, the old def is now dead
+            if( old_def != null ) {
+                if( CODE.add(old_def).delUse(this) )
+                    old_def.kill(); // If we removed the last use, the old def is now dead
+                old_def.moveDepsToWorklist(); // Use-count changes can enable distant rewrites.
+            }
         }
         assert isDead();        // Really dead now
     }
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java
index 7e057507..db140304 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java
@@ -26,22 +26,15 @@ public class TFPRISC extends ConstantNode implements MachNode, RIPRelSize {
         enc.add4(riscv.i_type(riscv.OP_IMM, dst, 0, dst, 0));
     }
 
-    @Override public byte encSize(int delta) {
-        if( -(1L<<11) <= delta && delta < (1L<<11) ) return 4;
-        throw Utils.TODO();
-    }
+    @Override public byte encSize(int delta) { return 8; }
 
     // Delta is from opcode start
     @Override public void patch( Encoding enc, int opStart, int opLen, int delta ) {
         short rpc = enc.reg(this);
         if( opLen==8 ) {
-            // AUIPC (upper 20 bits)
-            // opstart of add
-            int next = opStart + opLen;
-            enc.patch4(opStart,riscv.u_type(riscv.OP_AUIPC, rpc, delta>>12));
-            // addi(low 12 bits)
-            enc.patch4(next,riscv.i_type(riscv.OP_IMM, rpc, 0, rpc, delta & 0xFFF));
-            // addi
+            // ADDI sign-extends its low 12 bits, so round the AUIPC high part.
+            enc.patch4(opStart  ,riscv.u_type(riscv.OP_AUIPC, rpc, (delta+0x800)>>12));
+            enc.patch4(opStart+4,riscv.i_type(riscv.OP_IMM, rpc, 0, rpc, delta & 0xFFF));
         } else {
              // should not happen as one instruction is 4 byte, and TFP arm encodes 2.
             throw Utils.TODO();
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java
index e6ff1196..479e9e62 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java
@@ -187,7 +187,7 @@ var fcn = arg ? { int x -> x*x; } : { int x -> x+x; };
 return fcn(3);
 """);
         code.parse().opto();
-        assertEquals("Stop[ return #2; return 9; return 6; ]", code._stop.toString());
+        assertEquals("Stop[ return #2; return (Parm_x($fun21,i64)*x); return (Parm_x($fun22,i64)<<1); ]", code._stop.toString());
         assertEquals("6", Eval2.eval(code, 0));
         assertEquals("9", Eval2.eval(code, 1));
     }
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java
index b9764607..df94e97c 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java
@@ -413,7 +413,7 @@ val fcn = arg ? { int x -> x*x; } : { int x -> x+x; };
 return fcn(2)*10 + fcn(3);
 """);
         code.driver(Phase.LocalSched,"x86_64_v2", "SystemV");
-        assertEquals("Stop[ return (add,#2,(muli,#2)); return (mul,Parm_x($fun21,[2-3]),x); return (shli,Parm_x($fun22,[2-3])); ]", code.print());
+        assertEquals("Stop[ return (add,#2,(muli,#2)); return (mul,Parm_x($fun21,i64),x); return (shli,Parm_x($fun22,i64)); ]", code.print());
     }
 
     @Test
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java
index 044ad4ed..4e7cb156 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java
@@ -205,9 +205,9 @@ s.cs[0] =  67; // C
 s.cs[1] = 108; // l
 hashCode(s);
 """;
-        testTarget(src,"x86_64_v2", "SystemV",9,null);
-        testTarget(src,"riscv"    , "SystemV",4,null);
-        testTarget(src,"arm"      , "SystemV",3,null);
+        testTarget(src,"x86_64_v2", "SystemV",0,null);
+        testTarget(src,"riscv"    , "SystemV",0,null);
+        testTarget(src,"arm"      , "SystemV",0,null);
     }
 
     @Test
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java
index 86fa016a..afa3ce6a 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java
@@ -13,6 +13,27 @@ import org.junit.Test;
 import static org.junit.Assert.*;
 
 public class Chapter21Test {
+    @Test public void testReturnedFunctionEncoding() throws IOException {
+        String src = "if(arg) return {->42;}; return {->43;};";
+        CodeGen code = new CodeGen(src).driver("riscv","SystemV",null);
+        for( int arg : new int[]{0,1} ) {
+            byte[] image = new byte[1<<16];
+            byte[] bits = code._encoding.bits();
+            System.arraycopy(bits,0,image,0,bits.length);
+            EvalRisc5 cpu = new EvalRisc5(image,1<<15);
+            cpu._pc = code._encoding._opStart[code.link(code._main)._nid];
+            cpu.regs[riscv.A0] = arg;
+            assertEquals(0,cpu.step(100));
+            assertEquals(0,cpu._pc);
+            cpu._pc = (int)cpu.regs[riscv.A0];
+            assertEquals(0,cpu.step(100));
+            assertEquals(0,cpu._pc);
+            assertEquals(arg==0 ? 43 : 42,cpu.regs[riscv.A0]);
+        }
+        // Anonymous bodies need code, but no exported ELF name.
+        new CodeGen(src).driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,"build/objs/anonymous.o");
+    }
+
     @Test public void testArmFloatMemory() throws IOException {
         for( String type : new String[]{"f32","f64"} ) {
             String src = type+"[] !a=new "+type+"[3]; a[arg]=1.25; return a[1];";
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java
index cf92f830..6571b4f9 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java
@@ -14,6 +14,54 @@ import static org.junit.Assert.*;
 
 public class Chapter22Test {
 
+    @Test public void testReturnedFunctions() throws IOException {
+        for( String src : new String[]{"return {->42;};", "val f={->42;}; return f;", "return sys.io.p;"} )
+            for( String target : new String[]{"riscv","arm"} ) {
+                CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,target,"SystemV").exportELF(null);
+                byte[] image = new byte[1<<16];
+                byte[] bits = code._encoding.bits();
+                System.arraycopy(bits,0,image,0,bits.length);
+                boolean library = src.contains("sys.io.p");
+                // u8[]: four-byte length followed by its bytes.
+                image[0x2000]=2; image[0x2004]='o'; image[0x2005]='k';
+                int entry = code._encoding._opStart[code.link(code._main)._nid];
+                if( target.equals("riscv") ) {
+                    EvalRisc5 cpu = new EvalRisc5(image,1<<15);
+                    cpu._pc = entry;
+                    assertEquals(0,cpu.step(1000));
+                    assertEquals(0,cpu._pc);
+                    cpu._pc = (int)cpu.regs[riscv.A0]; // Call the returned address.
+                    cpu.regs[library ? riscv.A1 : riscv.A0] = 0x2000; // Methods also receive self.
+                    assertEquals(0,cpu.step(1000));
+                    assertEquals(0,cpu._pc);
+                    if( library ) assertEquals("ok",cpu._stdout.toString());
+                    else assertEquals(42,cpu.regs[riscv.A0]);
+                } else {
+                    EvalArm64 cpu = new EvalArm64(image,1<<15);
+                    cpu._pc = entry;
+                    assertEquals(0,cpu.step(1000));
+                    assertEquals(0,cpu._pc);
+                    cpu._pc = (int)cpu.regs[0];
+                    cpu.regs[library ? 1 : 0] = 0x2000;
+                    assertEquals(0,cpu.step(1000));
+                    assertEquals(0,cpu._pc);
+                    if( library ) assertEquals("ok",cpu._stdout.toString());
+                    else assertEquals(42,cpu.regs[0]);
+                }
+            }
+        CodeGen unused = new CodeGen("({->42;}); return 0;").parse().opto();
+        assertEquals(1,unused._stop.nIns());
+    }
+
+    @Test public void testReturnedFunctionsNative() throws IOException {
+        String src = "val factory={int x -> if(x) return {->42;}; return {->43;};}; val printer={->return sys.io.p;};";
+        String obj = "build/objs/funptr.o";
+        new CheckedCodeGen(src).driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,obj);
+        assertEquals("ok",TestC.gcc(obj,"","src/test/java/com/seaofnodes/simple/progs/funptr.c",false,
+                                   "build/objs/funptr"+(TestC.OS.startsWith("Windows") ? ".exe" : "")));
+    }
+
+
     @Test public void testRiscvRightShifts() {
         // SRAI, SRLI, SRA, SRL: a0 = -32 shifted by 4.
         int[] ops = {0x40455513,0x00455513,0x40b55533,0x00b55533};
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/progs/funptr.c b/chapter24/src/test/java/com/seaofnodes/simple/progs/funptr.c
new file mode 100644
index 00000000..2abe6e74
--- /dev/null
+++ b/chapter24/src/test/java/com/seaofnodes/simple/progs/funptr.c
@@ -0,0 +1,15 @@
+#include <assert.h>
+#include <stdint.h>
+
+typedef int64_t (*Function)(void);
+typedef int64_t (*Printer)(void *, void *);
+extern Function factory(int64_t);
+extern Printer printer(void);
+
+int main(void) {
+    assert(factory(1)() == 42);
+    assert(factory(0)() == 43);
+    struct { uint32_t length; char data[2]; } text = {2, {'o','k'}};
+    printer()(0, &text); // Unused class receiver, then the byte array.
+    return 0;
+}