diff options
Diffstat (limited to 'chapter22')
13 files changed, 123 insertions, 17 deletions
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; +} |