diff options
Diffstat (limited to 'chapter24')
16 files changed, 150 insertions, 27 deletions
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; +} |