diff options
45 files changed, 446 insertions, 96 deletions
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java index 746ecfed..d1d20919 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java @@ -221,6 +221,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/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java index 17613009..a4355e17 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java +++ b/chapter21/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(addi); } - @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)); - // 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/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 0cabcfbc..72041bd7 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -11,6 +11,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/chapter22/src/main/java/com/seaofnodes/simple/Parser.java b/chapter22/src/main/java/com/seaofnodes/simple/Parser.java index 087fd1fd..8132f782 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/Parser.java @@ -1457,7 +1457,7 @@ public class Parser { // Make a concrete function type, with a fidx TypeFunPtr tfp = _code.makeFun(TypeTuple.make(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/chapter22/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 0c00b9c6..7c884b49 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -188,7 +188,7 @@ public class CodeGen { for( int i=0; i<_start.nOuts(); i++ ) { Node use = _start.out(i); if( use instanceof FunNode fun && - fun.nIns()==2 && fun.in(1)==_start && fun != main && + fun.nIns()==2 && fun.in(1)==_start && fun != main && !fun.hasPtr() && (fun._name==null || fun._name.startsWith("sys.")) ) { add(fun).setDef(1,Parser.XCTRL); addAll(fun._outputs); @@ -331,6 +331,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/chapter22/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java index 0eaaae7b..88af3f27 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java @@ -221,6 +221,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/chapter22/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 1b4b619a..f37da4f3 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -75,10 +75,10 @@ public class CallEndNode extends CFGNode implements MultiNode { assert fun.in(1) instanceof StartNode && fun.in(2)==call; // Disallow self-recursive inlining (loop unrolling by another name) CFGNode idom = call; - while( !(idom instanceof FunNode) ) + while( idom!=null && !(idom instanceof FunNode) ) idom = idom.idom(); // Inline? - if( idom != fun ) { + if( idom != null && idom != fun ) { // Trivial inline: rewrite _folding = true; // Rewrite Fun so the normal RegionNode ideal collapses diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 9785855b..60aa40c4 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -32,6 +32,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/chapter22/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/FunNode.java index 9afbf77e..5f67f859 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -60,6 +60,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/chapter22/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java new file mode 100644 index 00000000..7f32698e --- /dev/null +++ b/chapter22/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/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java index 15be82bc..1d1f30e9 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java @@ -25,22 +25,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/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 7863237e..7cd2831a 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter22/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 (Parm_x($fun2,int,3)<<1); return (Parm_x($fun1,int,3)*x); return #2; ]", code._stop.toString()); + assertEquals("Stop[ return (Parm_x($fun2,int,3)<<1); return #2; return (Parm_x($fun1,int,3)*x); ]", code._stop.toString()); assertEquals("6", Eval2.eval(code, 0)); assertEquals("9", Eval2.eval(code, 1)); } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 007e50b4..7ae094ad 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -47,7 +47,7 @@ return 0; public void testString() throws IOException { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); CodeGen code = new CodeGen(src).parse().opto().typeCheck().GCM().localSched(); - assertEquals("Stop[ return Phi(Region,1,0,0,1); return Phi(Region,._hashCode,Phi(Region,123456789,Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code._stop.toString()); + assertEquals("Stop[ return Phi(Region,._hashCode,Phi(Region,123456789,Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); return Phi(Region,1,0,0,1); ]", code._stop.toString()); //assertEquals("-4898613127354160978", Eval2.eval(code, 2)); } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 9f680807..9f901dc2 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -12,6 +12,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/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java index 60917773..b61e972f 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -14,6 +14,53 @@ 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[riscv.A0] = 0x2000; + 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[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/chapter22/src/test/java/com/seaofnodes/simple/progs/funptr.c b/chapter22/src/test/java/com/seaofnodes/simple/progs/funptr.c new file mode 100644 index 00000000..7545992d --- /dev/null +++ b/chapter22/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 *); +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()(&text); + return 0; +} diff --git a/chapter23/src/main/java/com/seaofnodes/simple/Parser.java b/chapter23/src/main/java/com/seaofnodes/simple/Parser.java index be5c8932..5b3f4d1a 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/Parser.java @@ -1618,7 +1618,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/chapter23/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index adfefae5..50490689 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -194,7 +194,7 @@ public class CodeGen { for( int i=0; i<_start.nOuts(); i++ ) { Node use = _start.out(i); if( use instanceof FunNode fun && - fun.nIns()==2 && fun.in(1)==_start && fun != main && + fun.nIns()==2 && fun.in(1)==_start && fun != main && !fun.hasPtr() && (fun._name==null || fun._name.startsWith("sys.")) ) { add(fun).setDef(1,Parser.XCTRL); addAll(fun._outputs); @@ -353,6 +353,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/chapter23/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java index 8f9e2981..b6267600 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java +++ b/chapter23/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/chapter23/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 8fd0e61e..0d7c0964 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter23/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/chapter23/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/FunNode.java index 88f5dc18..e7d6c3a6 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter23/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/chapter23/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java new file mode 100644 index 00000000..7f32698e --- /dev/null +++ b/chapter23/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/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java index 7e057507..db140304 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java +++ b/chapter23/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/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java index a0de3736..2665215c 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter23/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/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java index 6f488c85..386565a2 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter23/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/chapter23/src/test/java/com/seaofnodes/simple/progs/funptr.c b/chapter23/src/test/java/com/seaofnodes/simple/progs/funptr.c new file mode 100644 index 00000000..2abe6e74 --- /dev/null +++ b/chapter23/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; +} diff --git a/chapter24/README.md b/chapter24/README.md index 93f54a0d..a1fb6ded 100644 --- a/chapter24/README.md +++ b/chapter24/README.md @@ -298,16 +298,17 @@ both the cheaper first attempt and the mandatory fallback. Run `make spill-stats`. All rows use **Chapter 24's compiler**, optimizer seed 123, and the same source/target combinations as the earlier cohort tables. -These Windows results combine x86 SystemV/Win64 and RISC-V/ARM SystemV. +These Windows results combine x86 SystemV/Win64 and RISC-V/ARM SystemV, +remeasured on 2026-09-28 after the function-pointer lifetime backport. | Program cohort | Compilations | Split/move count | Loop-weighted count | |---|---:|---:|---:| -| Chapter 20 | 39 | 331 | 457 | +| Chapter 20 | 39 | 323 | 442 | | Chapter 21 | 52 | 436 | 975 | | Chapter 22 | 24 | 67 | 67 | -| Chapter 23 | 30 | 66 | 115 | -| Chapter 24 | 67 | 432 | 1,342 | -| **Total** | **212** | **1,332** | **2,956** | +| Chapter 23 | 30 | 84 | 231 | +| Chapter 24 | 67 | 441 | 1,400 | +| **Total** | **212** | **1,351** | **3,115** | `_spills` counts retained SplitNodes, including register moves. `_spillScaled` weights those moves by `8^loopDepth`; it is a cost estimate, not measured memory @@ -315,13 +316,15 @@ traffic. Diagnostic machine graphs contribute no allocations to this table. The reporter checks allocation legality and native/emulated results even when spill expectations differ, and exits unsuccessfully for either kind of failure. -With only the cold-first rule disabled, the same compiler and programs produce +In the original 2026-09-20 allocator audit, before subsequent compiler fixes, +the table totaled 1,332 / 2,956. With only the cold-first rule disabled, that +compiler and the same programs produced **1,338 moves / 2,962 weighted moves**. The rule saves six of each. A RISC-V MergeSort case adds one move, offset by improvements in other MergeSort cases, Sieve, and an ARM loop case. Aggregate measurements justify accepting that local regression; the improvement here is modest, not universal. -On cohorts 20-23 alone, Chapter 23 produced 933 / 1,745; Chapter 24 produces +On cohorts 20-23 alone in that audit, Chapter 23 produced 933 / 1,745; Chapter 24 produced 900 / 1,614. Only six of each reduction comes from this allocator change. The rest comes from other compiler changes, including SCCP; comparing chapters alone would overstate the heuristic's benefit. @@ -332,3 +335,10 @@ to cohort 24 alongside this chapter's existing tests. The frozen String workload also exposed a missing null check in the inlining dominator walk; that correctness fix is included on both sides of the heuristic comparison. Area/cost spill ranking remains for Chapter 25. + +The current function-pointer rule keeps unknown callers whenever an address is +used as a value rather than only as a direct call target. This preserves callable +bodies without escape analysis, but Phi-selected functions retain general +parameter types. The no-return String case now drops its unused hash bodies and +needs no splits. Source/target membership remains unchanged; these graph changes +are separate from the cold-first allocator comparison above. 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; +} diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java index 8ca4662b..59c9f8e3 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java @@ -340,8 +340,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/docs/chapter-backports.md b/docs/chapter-backports.md index 6e74572b..bef83637 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -9,7 +9,8 @@ Introduce independent fixes in the earliest applicable chapter and propagate them through every affected snapshot. Testing Chapter 25's inherited tests does not validate the compilers in the earlier chapter directories. Keep building SSA with incomplete types in Chapter 25 for now; moving that architecture or -renumbering chapters is deferred. +renumbering chapters is deferred. Cliff wants to revisit splitting Chapter 25 +into smaller chapters; escape analysis remains in 25 until that larger review. ## Pending corrections @@ -62,21 +63,6 @@ renumbering chapters is deferred. known-null regression is already rejected during parsing in 10-24. Keep this separate from the constructor/memory fixes. -- **FunPtrNode lifetime backport, now next after the allocator review.** - `return {->42;};` and `return sys.io.p;` fail during relocation in Chapter 22 - on all three targets at seed 123. Opto's name-based pruning equates no linked - calls with no callers and deletes anonymous/library function bodies. A plain - function-address ConstantNode keeps the pointer, but has no edge to keep the - Return alive. Instruction selection resets NIDs; the linker retains an ideal - target and `patchLocalRelocations` indexes outside the machine graph. - - Backport Chapter 25's FunPtrNode/Return retention rules together with pointer - creation, unknown-caller pruning, instruction selection, constant cloning, and - relocation. Determine the earliest applicable home; 21 lacks this pruning - pass. `val f={->42;}; return f;` surviving is not a fix for anonymous/library - addresses. Do not enlarge relocation arrays or add an interim address scan. - Validate returned pointers by calling them, including library pointers, while - still deleting genuinely unused helpers. Keep module/escape machinery in 25. - **Chapter 25 narrow C return values need ABI extension.** During the direct data-binding checks, `sys.libc.close(-1)==-1` evaluated false on x86/Cygwin. Disassembly compares the full RAX to -1 immediately after `close`, without @@ -238,6 +224,8 @@ and its separate validation are recorded independently. | Completed work | Scope and evidence retained | |---|---| +| FunPtr lifetime and callable entries | On 2026-09-28, introduced Return-linked FunPtrNode in 22-24, including semantic constant folding. Direct call targets retain existing call-graph treatment; all other address uses conservatively retain unknown callers, without escape analysis. Stop retains each callable Return through instruction selection; machine operands omit the lifetime edge. Anonymous/library returns failed relocation on all three targets before the change; 24 also failed named returns. New tests call returned anonymous/named/library pointers on ARM/RISC-V and from native C, and check discarded anonymous bodies disappear. Full Make suites passed: 21 (411), 22 (430), 23 (452), 24 (482), each plus its fuzzer wrapper. Baselines passed at 410/427/449/479. Chapter 24's Phi-selected functions retain general parameter types; graph expectations reflect that conservative rule. | +| Function-address backend and worklist corrections | RISC-V TFPRISC now patches ADDI at opStart+4, rounds AUIPC for signed low bits, and reports its actual eight-byte size (21-24). ELF export emits anonymous bodies without exported names (21-24). Actual invocation exposed both bugs after retention was repaired; Chapter 21's reduced conditional-return probe trapped before the encoding fix. Chapter 22 gains the later inlining dominator null guard. In 24, killing Call#618 reduced FunPtr#540 to one use without waking dependent CallEnd#560; Node.kill now wakes the remaining definition's dependencies after removing a use (24-25). The no-return String workload loses unused hash bodies; its spill expectations become zero on all targets. Chapter 24 spill-stats passes all 212 original compilation entries at 1,351 moves / 3,115 weighted moves; its README separates this measurement from the original allocator ablation. Full Chapter 25 Make validation also passed: 476 ordinary tests plus its 17-seed fuzzer wrapper, with sys.o rebuilt. | | Chapter 25 direct C data bindings | On 2026-09-28, full `make tests` passed after the Field/ExternOffset refactor: 476 ordinary tests plus the fuzzer wrapper (17 seeds). Coverage checks zero layout space for external fields, native shared integer/float storage across C calls, compound updates, source/precompiled imports sharing aliases and preserving storage metadata, ARM/RISC-V emulated address relocation and signed loads, and the errno accessor after a failed native call. Direct bindings remain in 25: 22-24 have different singleton-pointer constant and instruction-selection contracts. Serialization retains magic C0DE; the changed layout requires rebuilding all objects. Only the independent RISC-V fixes below were selected for backport. | | RISC-V right shifts and pointer relocation | Backported from 25 to 22-24 on 2026-09-28. EvalRisc5 selects arithmetic/logical right shifts correctly; TMPRISC rounds the AUIPC high part to account for signed ADDI low bits. New regressions cover immediate/register shifts and forward/backward relocation boundaries. Both fail before the Chapter 22 fixes (arithmetic shift becomes logical; delta 0x800 lands 4 KB low). Full Make suites passed: 22 (427), 23 (449), 24 (479), each plus its fuzzer wrapper. Baseline suites also passed (425/447/477). | | Chapter 25 Load fuzzer recheck | At `8212a66f`, seed `-4628356252269023530` passes its direct fuzzPeepsRegression replay (`build/load-seed-recheck.log`). The complete `make fuzzer` wrapper also passes all 17 seeds on 2026-09-28 (one JUnit wrapper test). The seed remains a regression; OPEN_FAILING_SEEDS is empty. No new compiler fix was needed. The older Load TODO report is superseded. | diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index ec2242dd..1f75814c 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -429,16 +429,24 @@ Consequences: whether an error exists. Earlier snapshots keep separate Return nodes; they already accept dead mixed-type exits and do not enforce one common return type. -- Chapters 22-23's post-Opto name-based function pruning is not escape analysis: - no linked calls does not mean no callers when a function address survives. - In 22, `return {->42;};` and `return sys.io.p;` lose their bodies but retain - pointer constants and stale ideal linker targets, then fail in relocation after - machine NIDs reset. Diagnose retention before resizing relocation tables. A - named-function workaround or keeping only anonymous functions is insufficient - for the library-pointer case. Cliff wants Chapter 25's FunPtrNode investigated - as the backport, including the Return edge and callable-function retention - rules, after register allocation work is complete. Keep the Chapter 22 examples - as documented known failures until then; do not add an interim address scan. +- Chapters 22-24 use Return-linked FunPtrNode constants. No linked calls does + not mean no callers when a function address survives. Direct call targets use + the existing call graph; any other address use conservatively preserves the + unknown-caller Start input. Phi-selected functions therefore keep general + parameter types. Escape propagation stays in 25; Cliff may split 25 into + smaller chapters later. Stop retains callable Returns through instruction + selection, which removes the lifetime edge from machine operands before + scheduling and cloning. Never substitute relocation-array growth or a linker + address scan for correct retention. +- Validate returned addresses by calling them. Include anonymous and library + functions, plus unused-body removal. Methods gain a receiver argument in 23; + native/emulator probes must honor it even when the body does not use self. +- Function-address encoding begins in 21. RISC-V AUIPC/ADDI occupies eight bytes; + patch the second instruction at opStart+4 and round the high part for signed + low bits. Anonymous bodies need emitted code, but no exported ELF symbol. +- Removing a use can enable a distant rewrite without changing the definition's + type. Node.kill in 24-25 wakes that definition's dependencies immediately; only + queueing the definition missed single-call inlining after another call died. - A constant Simple function address must be a `FunPtrNode`, not an ordinary `ConstantNode`, so the pointer retains an edge to the function Return. - Before Opto, a live FunPtr keeps its function callable even if no Call is |