diff options
Diffstat (limited to 'chapter22/src/main')
14 files changed, 81 insertions, 29 deletions
diff --git a/chapter22/src/main/java/com/seaofnodes/simple/Parser.java b/chapter22/src/main/java/com/seaofnodes/simple/Parser.java index ab2c775c..eae823eb 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/Parser.java @@ -196,7 +196,7 @@ public class Parser { ScopeNode breakScope = _breakScope; _breakScope = null; ScopeNode continueScope = _continueScope; _continueScope = null; - FunNode fun = _fun = (FunNode)peep(new FunNode(loc(),sig,null,_code._start)); + FunNode fun = _fun = (FunNode)peep(new FunNode(loc(),sig,_nestedType,null,_code._start)); // Once the function header is available, install in linker table - // allowing recursive functions. Linker matches on declared args and // exact fidx, and ignores the return (because the fidx will only match @@ -731,7 +731,7 @@ public class Parser { // expr is a constant function if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { if( expr instanceof ExternNode ) t = expr._type; // Upgrade declared type to exact function - else _code.link(tfp)._name = name; // Assign debug name to Simple function + else _code.link(tfp).setName(name); // Assign debug name to Simple function } } else { 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 26f2e522..8a28dacc 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -166,6 +166,22 @@ public class CodeGen { // Pessimistic peephole optimization on a worklist _iter.iterate(this); + + // Not really a true optimistic pass, but look for unlinked functions. + // This can be removed, which may trigger another round of pessimistic. + // This is the point where we flip from a virtual Call Graph (any call + // can call any function) to having a correct (but conservative) CG. + + FunNode main = link(_main); + for( Node use : _start._outputs ) + if( use instanceof FunNode fun && + fun.nIns()==2 && fun.in(1)==_start && fun != main && + (fun._name==null || fun._name.startsWith("sys.")) ) { + add(fun).setDef(1,Parser.XCTRL); + addAll(fun._outputs); + } + _iter.iterate(this); + _tOpto = (int)(System.currentTimeMillis() - t0); // TODO: @@ -203,7 +219,7 @@ public class CodeGen { _phase = Phase.LoopTree; long t0 = System.currentTimeMillis(); // Build the loop tree, fix never-exit loops - _start.buildLoopTree(_stop); + _start.buildLoopTree(_start,_stop); _tLoopTree = (int)(System.currentTimeMillis() - t0); return this; } @@ -262,7 +278,6 @@ public class CodeGen { _rpcMask = new RegMask(_mach.rpc()); _retMasks[3] = _rpcMask; - // Convert to machine ops long t0 = System.currentTimeMillis(); _uid = 1; // All new machine nodes reset numbering diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index c05cfe2e..78e2f75f 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -13,19 +13,6 @@ public abstract class GlobalCodeMotion { // Node.use(0) is always a block tail (either IfNode or head of the // following block). There are no unreachable infinite loops. public static void buildCFG( CodeGen code ) { - // Unlink all linked calls. This can remove RPC constants which - // shuffled the StartNode outputs so requires a while loop. - boolean done=false; - while(!done) { - done = true; - for( Node use : code._start._outputs ) - if( use instanceof FunNode fun ) - for( Node c : fun._inputs ) - if( c instanceof CallNode call ) - { call.unlink_all(); done=false; } - } - - Ary<CFGNode> rpo = new Ary<>(CFGNode.class); _rpo_cfg(null, code._start, code.visit(), rpo); // Reverse in-place diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 56a33a26..96597648 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -123,7 +123,19 @@ public abstract class CFGNode extends Node { // Tag all CFG Nodes with their containing LoopNode; LoopNodes themselves // also refer to *their* containing LoopNode, as well as have their depth. // Start is a LoopNode which contains all at depth 1. - public void buildLoopTree(StopNode stop) { + public void buildLoopTree(StartNode start, StopNode stop) { + // Unlink all linked calls. This can remove RPC constants which + // shuffled the StartNode outputs so requires a while loop. + boolean done=false; + while(!done) { + done = true; + for( Node use : start._outputs ) + if( use instanceof FunNode fun ) + for( Node c : fun._inputs ) + if( c instanceof CallNode call ) + { call.unlink_all(); done=false; } + } + _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); _bltWalk(2,null,stop, new BitSet()); } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/CallNode.java index 773716f7..8b243e87 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -32,8 +32,11 @@ public class CallNode extends CFGNode { return sb.append(")"); } public String name() { - if( fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() ) - return CodeGen.CODE.link(tfp)._name; + if( fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { + FunNode fun = CodeGen.CODE.link(tfp); + if( fun !=null ) return fun._name; + if( fptr() instanceof ExternNode ex ) return ex._extern; + } return null; } @@ -139,7 +142,7 @@ public class CallNode extends CFGNode { assert linked(fun); int idx = fun._inputs.find(this); for( Node use : fun._outputs ) - if( use instanceof ParmNode parm ) + if( use instanceof ParmNode ) use.delDef(idx); fun.delDef(idx); cend().delDef(cend()._inputs.find(fun.ret())); @@ -162,6 +165,9 @@ public class CallNode extends CFGNode { if( !arg(i+2)._type.isa(tfp.arg(i)) ) return Parser.error( "Argument #"+i+" isa "+arg(i+2)._type+", but must be a "+tfp.arg(i), _loc); + if( tfp.fidxs() < 0 ) + throw Utils.TODO(); // Infinite unknown TFPs? Should be fairly precise CG + return null; } 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 5a356185..c469fc96 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -21,7 +21,7 @@ public class FunNode extends RegionNode { public String _name; // Debug name - public FunNode( Parser.Lexer loc, TypeFunPtr sig, Node... nodes ) { super(loc,nodes); _sig = sig; } + public FunNode( Parser.Lexer loc, TypeFunPtr sig, String name, Node... nodes ) { super(loc,nodes); _name=name; _sig = sig; } public FunNode( FunNode fun ) { super( fun, fun==null ? null : fun._loc ); if( fun!=null ) { @@ -69,6 +69,11 @@ public class FunNode extends RegionNode { } } + public void setName( String name ) { + if( _name==null ) _name=name; + else _name += "."+name; + } + @Override public Type compute() { // Only dead if no callers after SCCP diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 9e11a129..32e41f54 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -45,4 +45,8 @@ public class ParmNode extends PhiNode { // Always in-progress until we run out of unknown callers @Override public boolean inProgress() { return fun().inProgress(); } + + @Override public boolean eq( Node n ) { + return ((ParmNode)n)._idx==_idx && super.eq(n); + } } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/StopNode.java index 9be08ad9..b65535f1 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -23,11 +23,15 @@ public class StopNode extends CFGNode { @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { // For the sake of many old tests, and single value prints as "return val" - if( ret()!=null ) return ret()._print0(sb,visited); + ReturnNode ret1 = ret(); + if( ret1!=null ) return ret1._print0(sb,visited); sb.append("Stop[ "); for( Node ret : _inputs ) - if( ret!=null ) - ret._print0(sb, visited).append(" "); + if( ret!=null ) { + String name = ((ReturnNode)ret).fun()._name; + if( name== null || !name.startsWith("sys.") ) + ret._print0(sb, visited).append(" "); + } return sb.append("]"); } @@ -37,7 +41,13 @@ public class StopNode extends CFGNode { // If a single Return, return it. // Otherwise, null because ambiguous. public ReturnNode ret() { - return nIns()==1 && in(0) instanceof ReturnNode ret ? ret : null; + Node ret1 = this; + for( Node ret : _inputs ) { + String name = ((ReturnNode)ret).fun()._name; + if( name==null || !name.startsWith("sys.") ) + ret1 = ret1==this ? ((ReturnNode)ret) : null; + } + return ret1==this ? null : (ReturnNode)ret1; } @Override @@ -49,7 +59,7 @@ public class StopNode extends CFGNode { public Node idealize() { int len = nIns(); for( int i=0; i<nIns(); i++ ) - if( ((ReturnNode)in(i)).fun().isDead() ) + if( addDep(((ReturnNode)in(i)).fun()).isDead() ) delDef(i--); if( len != nIns() ) return this; return null; diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java index 16b56553..76e23c30 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.*; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.ConstantNode; import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.cpus.riscv.riscv; import com.seaofnodes.simple.type.TypeFunPtr; @@ -50,4 +51,5 @@ public class TFPARM extends ConstantNode implements MachNode, RIPRelSize { String reg = code.reg(this); _con.print(sb.p(reg).p(" #")); } + @Override public boolean eq(Node n) { return this==n; } } 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 17613009..a69cfbe8 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 @@ -4,6 +4,7 @@ import com.seaofnodes.simple.*; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.ConstantNode; import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.type.TypeFunPtr; public class TFPRISC extends ConstantNode implements MachNode, RIPRelSize { @@ -51,5 +52,5 @@ public class TFPRISC extends ConstantNode implements MachNode, RIPRelSize { @Override public void asm(CodeGen code, SB sb) { _con.print(sb.p(code.reg(this)).p(" #")); } - + @Override public boolean eq(Node n) { return this==n; } } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java index be4d1a83..d7566f9e 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java @@ -63,4 +63,5 @@ public class TFPX86 extends ConstantNode implements MachNode, RIPRelSize { else _con.print(sb.p(reg).p(" = #")); } + @Override public boolean eq(Node n) { return this==n; } } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TMPX86.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TMPX86.java index 70b9dbb0..c44cf2f9 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TMPX86.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TMPX86.java @@ -31,4 +31,5 @@ public class TMPX86 extends ConstantNode implements MachNode, RIPRelSize{ @Override public void asm(CodeGen code, SB sb) { _con.print(sb.p(code.reg(this)).p(" = #")); } + @Override public boolean eq(Node n) { return this==n; } } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index 0751a612..bf51f2cb 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -189,6 +189,7 @@ public class x86_64_v2 extends Machine { static RegMask callInMask( TypeFunPtr tfp, int idx ) { if( idx==0 ) return RPC_MASK; if( idx==1 ) return null; + if( idx-2 >= tfp.nargs() ) return null; // Anti-dependence return switch( CodeGen.CODE._callingConv ) { case "SystemV" -> callSys5 (tfp,idx); case "Win64" -> callWin64(tfp,idx); diff --git a/chapter22/src/main/java/com/seaofnodes/simple/sys/sys.smp b/chapter22/src/main/java/com/seaofnodes/simple/sys/sys.smp index 67de77ef..50d9166e 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/sys/sys.smp +++ b/chapter22/src/main/java/com/seaofnodes/simple/sys/sys.smp @@ -5,7 +5,7 @@ struct sys { // libc bindings /** https://www.man7.org/linux/man-pages/man2/<libc call>.2.html */ struct libc { - // fd buf len -> len + // fd buf len -> len { i32 i64 i32 -> i32 } write = "C"; // addr len prot flags fd off -> void* { i64 i64 i32 i32 i32 i32 -> i64 } mmap = "C"; @@ -17,4 +17,11 @@ struct sys { i32 MAP_PRIVATE = 2; i32 MAP_ANON = 32; }; + struct io { + val p = { u8[~] str -> + i64 ptr = str; // cast array base to i64 + i32 len = str#; // cast length to signed + return sys.libc.write(1,ptr,len); + }; + }; }; |