From bac24802e16c93b9f6295f2dea04a6223c211738 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 31 Dec 2024 16:25:28 -0800 Subject: Compile pipeline deals with functions Pretty-print functions. GCM deals with functions. Tighten linker API. CallEnd asserts harder proper graph. Eval2 makes (non recursive) function calls Peeps infer sharper function return sigs. --- .../main/java/com/seaofnodes/simple/CodeGen.java | 18 ++- .../com/seaofnodes/simple/GlobalCodeMotion.java | 12 +- .../main/java/com/seaofnodes/simple/IRPrinter.java | 39 ++++--- .../main/java/com/seaofnodes/simple/Parser.java | 129 +++++++++++++-------- .../java/com/seaofnodes/simple/node/CFGNode.java | 18 ++- .../com/seaofnodes/simple/node/CallEndNode.java | 10 +- .../java/com/seaofnodes/simple/node/CallNode.java | 32 ++++- .../java/com/seaofnodes/simple/node/FunNode.java | 24 +++- .../java/com/seaofnodes/simple/node/ParmNode.java | 4 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 7 +- .../com/seaofnodes/simple/node/ReturnNode.java | 15 ++- .../com/seaofnodes/simple/node/ScopeMinNode.java | 2 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/node/StopNode.java | 8 -- .../com/seaofnodes/simple/type/TypeFunPtr.java | 23 ++-- 15 files changed, 230 insertions(+), 113 deletions(-) (limited to 'chapter18/src/main/java/com/seaofnodes') diff --git a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java index 51a6e78e..9588fb01 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java @@ -20,8 +20,10 @@ public class CodeGen { public StopNode _stop ; - // "Linker" mapping from constant TypeFunPtrs to heads of function - public final HashMap _linker = new HashMap<>(); + // "Linker" mapping from constant TypeFunPtrs to heads of function. These + // TFPs all have exact single fidxs and their return is wiped to BOTTOM (so + // the return is not part of the match). + private final HashMap _linker = new HashMap<>(); // Last created CodeGen as a global, for easier debugging prints @@ -87,13 +89,23 @@ public class CodeGen { return this; } - public CodeGen localSched() { + // Local (basic block) scheduler phase, a classic list scheduler + public CodeGen localSched() { assert _phase == Phase.Schedule; _phase = Phase.LocalSched; ListScheduler.sched(this); return this; } + // Reverse from a constant function pointer to the IR function being called + public FunNode link( TypeFunPtr tfp ) { + assert tfp.isConstant(); + return _linker.get(tfp.makeFrom(Type.BOTTOM)); + } + + public void link(FunNode fun) { + _linker.put(fun.sig().makeFrom(Type.BOTTOM),fun); + } // Testing shortcuts Node ctrl() { return _stop.ret().ctrl(); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index f1593a81..bacbd538 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -24,7 +24,7 @@ public abstract class GlobalCodeMotion { private static void schedEarly(StartNode start) { ArrayList rpo = new ArrayList<>(); BitSet visit = new BitSet(); - _rpo_cfg(start, visit, rpo); + _rpo_cfg(null, start, visit, rpo); // Reverse Post-Order on CFG for( int j=rpo.size()-1; j>=0; j-- ) { CFGNode cfg = rpo.get(j); @@ -39,12 +39,14 @@ public abstract class GlobalCodeMotion { } // Post-Order of CFG - private static void _rpo_cfg(Node n, BitSet visit, ArrayList rpo) { - if( !(n instanceof CFGNode cfg) || visit.get(cfg._nid) ) + private static void _rpo_cfg(CFGNode def, Node use, BitSet visit, ArrayList rpo) { + if( !(use instanceof CFGNode cfg) || visit.get(cfg._nid) ) return; // Been there, done that + if( def instanceof CallNode && cfg instanceof FunNode ) + return; // Ignore linked function calls visit.set(cfg._nid); - for( Node use : cfg._outputs ) - _rpo_cfg(use,visit,rpo); + for( Node useuse : cfg._outputs ) + _rpo_cfg(cfg,useuse,visit,rpo); rpo.add(cfg); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java index adf67d8b..870a890b 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeFunPtr; import java.util.ArrayList; import java.util.BitSet; import java.util.HashMap; @@ -31,13 +32,6 @@ public class IRPrinter { return sb.p("\n"); } - private static SB nodeId(SB sb, Node n) { - sb.p("%%%d".formatted(n._nid)); - if (n instanceof ProjNode proj) { - sb.p(".").p(proj._idx); - } - return sb; - } public static String prettyPrint(Node node, int depth) { return CodeGen.CODE._phase.ordinal() > CodeGen.Phase.Schedule.ordinal() @@ -61,14 +55,24 @@ public class IRPrinter { Node n = rpos.get(i); if( n instanceof CFGNode || n.isMultiHead() ) { if( !gap ) sb.p("\n"); // Blank before multihead + if( n instanceof FunNode fun ) { + TypeFunPtr sig = fun.sig(); + sig.print(sb.p("--- ").p(sig._name==null ? "" : sig._name).p(" "),false).p("----------------------\n"); + } printLine( n, sb ); // Print head while( --i >= 0 ) { Node t = rpos.get(i); if( !t.isMultiTail() ) { i++; break; } printLine( t, sb ); } - sb.p("\n"); // Blank after multitail - gap = true; + if( n instanceof ReturnNode ret ) { + TypeFunPtr sig = ret.fun().sig(); + sig.print(sb.p("--- ").p(sig._name==null ? "" : sig._name).p(" "),false).p("----------------------\n"); + } + if( !(n instanceof CallNode) ) { + sb.p("\n"); // Blank after multitail + gap = true; + } } else { printLine( n, sb ); gap = false; @@ -87,15 +91,20 @@ public class IRPrinter { // First walk the CFG, then everything if( n instanceof CFGNode ) { for( Node use : n._outputs ) - if( use instanceof CFGNode && use.nOuts() >= 1 && - !(use._outputs.get( 0 ) instanceof LoopNode) ) + // Follow CFG, not across call/function borders, and not around backedges + if( use instanceof CFGNode && !(n instanceof CallNode && use instanceof FunNode) && + use.nOuts() >= 1 && !(use._outputs.get(0) instanceof LoopNode) ) postOrd(use, n, rpos,visit,bfs); for( Node use : n._outputs ) - if( use instanceof CFGNode ) + // Follow CFG, not across call/function borders + if( use instanceof CFGNode && !(n instanceof CallNode && use instanceof FunNode) ) postOrd(use,n,rpos,visit,bfs); } + // Follow all outputs for( Node use : n._outputs ) - if( use != null ) + if( use != null && + !(n instanceof CallNode && use instanceof FunNode) && + (n instanceof FunNode || !(use instanceof ParmNode)) ) postOrd(use, n, rpos,visit,bfs); // Post-order rpos.add(n); @@ -247,7 +256,9 @@ public class IRPrinter { !(node instanceof LoopNode loop && loop.back()==def) && // Don't walk into or out of functions !(node instanceof CallEndNode && def instanceof ReturnNode) && - !(node instanceof FunNode && def instanceof CallNode) ) + !(node instanceof FunNode && def instanceof CallNode) && + !(node instanceof ParmNode && !(def instanceof FunNode)) + ) _walk(ds,ns,def,d-1); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java index 79d5ce4a..49667ecc 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java @@ -150,32 +150,15 @@ public class Parser { public StopNode parse() { return parse(false); } public StopNode parse(boolean show) { _xScopes.push(_scope); - //// Enter a new scope for the initial control and arguments - //_scope.push(); - //Node ctrl = new CProjNode(START, 0, ScopeNode.CTRL).peephole(); - //Node pmem = new ProjNode(START, 1, ScopeNode.MEM0).peephole(); - //Node arg = new ProjNode(START, 2, ScopeNode.ARG0).peephole(); - //ScopeMinNode mem = new ScopeMinNode(); - //mem.addDef(null); - //mem.addDef(pmem); _scope.define(ScopeNode.CTRL, Type.CONTROL , false, null); _scope.define(ScopeNode.MEM0, TypeMem.BOT , false, null); _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, null); - // - //// Call main - //CallNode main = (CallNode)new CallNode(ctrl,pmem,arg,con(TypeFunPtr.MAIN)).peephole(); - //// Call End - //CallEndNode cend = (CallEndNode)new CallEndNode(main).peephole(); - //STOP.addDef(new CProjNode(cend,0,ScopeNode.CTRL).peephole()); - //STOP.addDef(new ProjNode(cend,1,ScopeNode.MEM0).peephole()); - //STOP.addDef(new ProjNode(cend,2,ScopeNode.ARG0).peephole()); + + ctrl(XCTRL); + _scope.mem(new ScopeMinNode(false)); // Parse whole program, as-if function header "{ int arg -> body }" - ReturnNode ret = parseFunctionBody("main",TypeFunPtr.MAIN,"arg"); - CodeGen.CODE._linker.put(TypeFunPtr.MAIN,ret.fun()); - //main.peephole(); - //if( cend.peephole() != null ) - // IterPeeps.addAll(cend._outputs); + ReturnNode ret = parseFunctionBody(TypeFunPtr.MAIN,"arg"); if( !_lexer.isEOF() ) throw _errorSyntax("unexpected"); @@ -194,9 +177,12 @@ public class Parser { /** * Parses a function body, assuming the header is parsed. */ - private ReturnNode parseFunctionBody(String name, TypeFunPtr sig, String... ids) { - sig.setName(name); - FunNode fun = _fun = (FunNode)peep(new FunNode(START,sig,name)); + private ReturnNode parseFunctionBody(TypeFunPtr sig, String... ids) { + Node oldctrl = ctrl().keep(); + Node oldmem = _scope.mem().keep(); + FunNode oldfun = _fun; + + FunNode fun = _fun = (FunNode)peep(new FunNode(START,sig)); // Build a multi-exit return point for all function returns RegionNode r = new RegionNode(null,null); @@ -232,11 +218,7 @@ public class Parser { // Last expression is the return if( ctrl()._type==Type.CONTROL ) - STOP.addReturn(ctrl(), _scope.mem().merge(), last, fun); - - // Function scope ends - _scope.pop(); - _fun = null; + fun.addReturn(ctrl(), _scope.mem().merge(), last); // Pop off the inProgress node on the multi-exit Region merge assert r.inProgress(); @@ -249,7 +231,23 @@ public class Parser { ret.setDef(1,rmem.peephole()); ret.setDef(2,rrez.peephole()); ret.setDef(0,r.peephole()); - return (ReturnNode)ret.peephole(); + ret = (ReturnNode)ret.peephole(); + + // Function scope ends + _scope.pop(); + _fun = oldfun; + // Reset control and memory to pre-function parsing days + ctrl(oldctrl.unkeep()); + _scope.mem(oldmem.unkeep()); + + // Once function body is complete, install in linker table. Linker + // matches on declared args and exact fidx, and ignores the return + // (because the fidx will only match the exact single function). The + // normal TFP interning ALSO matches on return, so wipe out the return + // for this arg+fidx only match. + CodeGen.CODE.link(fun); + + return ret; } /** @@ -582,7 +580,7 @@ public class Parser { var expr = require(parseAsgn(), ";"); // Need default memory, since it can be lazy, need to force // a non-lazy Phi - STOP.addReturn(ctrl(), _scope.mem().merge(), expr, _fun); + _fun.addReturn(ctrl(), _scope.mem().merge(), expr); ctrl(XCTRL); // Kill control return expr; } @@ -694,6 +692,8 @@ public class Parser { throw error("a not-null/non-zero expression"); t = expr._type.glb(); } + if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) + tfp.setName(name); } else { if( inferType && !_scope.inCon() ) @@ -1039,7 +1039,7 @@ public class Parser { if( matchx("null" ) ) return NIL; if( match ("(" ) ) return require(parseAsgn(), ")"); if( matchx("new" ) ) return alloc(); - if( match ("{" ) ) return func(); + if( match ("{" ) ) return require(func(),"}"); // Expect an identifier now ScopeMinNode.Var n = requireLookupId("an identifier or expression"); Node rvalue = _scope.in(n); @@ -1191,25 +1191,17 @@ public class Parser { * expr ('.' IDENTIFIER)* [ = expr ] * expr # * expr ('[' expr ']')* = [ = expr ] + * expr '(' [args,]* ')' * */ private Node parsePostfix(Node expr) { - String name = null; + String name; if( match(".") ) name = requireId(); else if( match("#") ) name = "#"; else if( match("[") ) name = "[]"; + else if( match("(") ) return require(functionCall(expr),")"); else return expr; // No postfix - // Happens when parsing known dead code, which often has other typing - // issues. Since the code is dead, possibly due to inlining, lets not - // spoil the user experience with error messages. - //if( ctrl()._type==Type.XCONTROL ) { - // if( expr.isUnused() ) expr.kill(); // Losing last use of expr - // // Exit out via parsing the trailing expression - // return matchOpx( '=', '=' ) ? parseAsgn() : parsePostfix( con( Type.TOP ) ); - //} - - // if( expr._type==Type.NIL ) throw error("Accessing unknown field '" + name + "' from 'null'"); @@ -1298,7 +1290,7 @@ public class Parser { } /** - * Parse a function; the leading '{' is already parsed. + * Parse a function body; the caller will parse the surrounding "{}" * * 
      *     { [type arg,]* -> expr }
@@ -1306,7 +1298,6 @@ public class Parser {
      *
*/ private Node func() { - int old = pos(); // Record lexer position Ary ts = new Ary<>(Type.class); Ary ids = new Ary<>(String.class); while( true ) { @@ -1320,7 +1311,53 @@ public class Parser { require("->"); // Make a concrete function type, with a fidx TypeFunPtr tfp = TypeFunPtr.makeFun(TypeTuple.make(ts.asAry()),Type.BOTTOM); - return parseFunctionBody(null,tfp,ids.asAry()); + ReturnNode ret = parseFunctionBody(tfp,ids.asAry()); + return con(ret._fun.sig()); + } + + /** + * Parse function call arguments; caller will parse the surrounding "()" + * 
+     *   ( arg* )
+     *
+ */ + private Node functionCall(Node expr) { + if( expr._type == Type.NIL ) + throw error("Calling a null function pointer"); + if( !(expr._type instanceof TypeFunPtr tfp) ) + throw error("Expected a function but got "+expr._type.str()); + expr.keep(); // Keep while parsing args + + Ary args = new Ary(Node.class); + args.push(null); // Space for ctrl,mem + args.push(null); + while( !peek(')') ) { + Node arg = parseAsgn(); + if( arg==null ) break; + args.push(arg.keep()); + if( !match(",") ) break; + } + // Control & memory after parsing args + args.set(0,ctrl().keep()); + args.set(1,_scope.mem().merge().keep()); + args.push(expr); // Function pointer + // Unkeep them all + for( Node arg : args ) + arg.unkeep(); + // Into the call + CallNode call = (CallNode)new CallNode(args.asAry()).peephole(); + + // Post-call setup + CallEndNode cend = (CallEndNode)new CallEndNode(call).peephole(); + // Control from CallEnd + ctrl(new CProjNode(cend,0,ScopeNode.CTRL).peephole()); + // Memory from CallEnd + ScopeMinNode mem = new ScopeMinNode(true); + mem.addDef(null); // Alias#0 + mem.addDef(new ProjNode(cend,1,ScopeNode.MEM0).peephole()); + _scope.mem(mem); + // Call result + return new ProjNode(cend,2,null).peephole(); } /** diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 78071920..a3bb1ae9 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -95,22 +95,23 @@ public abstract class CFGNode extends Node { _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); _bltWalk(2,null,stop, new BitSet()); } - private int _bltWalk(int pre, FunNode fun, StopNode stop, BitSet post) { + int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) { // Pre-walked? if( _pre!=0 ) return pre; _pre = pre++; // Pre-walk for( Node use : _outputs ) - if( use instanceof CFGNode usecfg && !(usecfg instanceof XCtrlNode) ) + if( use instanceof CFGNode usecfg && !skip(usecfg) ) pre = usecfg._bltWalk(pre,use instanceof FunNode fuse ? fuse : fun,stop,post); // Post-order work: find innermost loop LoopTree inner = null, ltree; for( Node use : _outputs ) { if( !(use instanceof CFGNode usecfg) ) continue; - if( usecfg instanceof XCtrlNode ) continue; - if( usecfg._type == Type.XCONTROL ) continue; // Dead, only possible if peeps disabled - if( usecfg._type == TypeTuple.IF_NEITHER ) continue; // Dead again + if( skip(usecfg) ) continue; + if( usecfg._type == Type.XCONTROL || // Do not walk dead control + usecfg._type == TypeTuple.IF_NEITHER ) // Nor dead IFs + continue; // Child visited but not post-visited? if( !post.get(usecfg._nid) ) { // Must be a backedge to a LoopNode then @@ -143,4 +144,11 @@ public abstract class CFGNode extends Node { post.set(_nid); return pre; } + + boolean skip(CFGNode usecfg) { + // Only walk control users that are alive. + // Do not walk from a Call to linked Fun's. + return usecfg instanceof XCtrlNode || (this instanceof CallNode && usecfg instanceof FunNode); + } + } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 31c245f9..578d7f87 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -3,8 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeFunPtr; +import com.seaofnodes.simple.type.*; import java.util.BitSet; /** @@ -19,6 +18,7 @@ public class CallEndNode extends CFGNode implements MultiNode { @Override public String label() { return "CallEnd"; } + @Override public boolean isMultiHead() { return true; } @Override public boolean blockHead() { return true; } CallNode call() { return (CallNode)in(0); } @@ -36,10 +36,8 @@ public class CallEndNode extends CFGNode implements MultiNode { @Override public Type compute() { - for( Node n : _inputs ) - if( n!=null && n._type==Type.CONTROL ) - return Type.CONTROL; - return Type.XCONTROL; + Type ret = call().fptr()._type instanceof TypeFunPtr tfp ? tfp.ret() : Type.BOTTOM; + return TypeTuple.make(call()._type,TypeMem.BOT,ret); } @Override diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java index 3ec1cd0c..b836188c 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -21,7 +21,7 @@ public class CallNode extends CFGNode { String fname = null; Node fptr = fptr(); if( fptr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) - fname = CodeGen.CODE._linker.get(tfp)._name; + fname = tfp._name; if( fname==null ) fptr._print0(sb,visited); else sb.append(fname); sb.append("( "); @@ -36,14 +36,32 @@ public class CallNode extends CFGNode { // Args mapped 1-to-1 on inputs Node arg(int idx) { return in(idx); } // args from input 2 to last - Node fptr() { return _inputs.last(); } + public Node fptr() { return _inputs.last(); } // Find the Call End from the Call - CallEndNode cend() { + public CallEndNode cend() { // Always in use slot 0 - return (CallEndNode)out(0); + if( nOuts()>0 && out(0) instanceof CallEndNode cend ) { + assert _cend()==cend; + return cend; + } else { + assert _cend()==null; + return null; + } + } + private CallEndNode _cend() { + CallEndNode cend=null; + for( Node n : _outputs ) + if( n instanceof CallEndNode cend0 ) + { assert cend == null; cend = cend0; } + return cend; } + // Get the one control following; error to call with more than one e.g. an + // IfNode or other multi-way branch. + @Override public CFGNode uctrl() { return cend(); } + + @Override public Type compute() { return ctrl()._type; @@ -51,6 +69,9 @@ public class CallNode extends CFGNode { @Override public Node idealize() { + CallEndNode cend = cend(); + if( cend==null ) return null; // Still building + // Link: call calls target function. Linking makes the target FunNode // point to this Call, and all his Parms point to the call arguments; // also the CallEnd points to the Return. @@ -58,11 +79,12 @@ public class CallNode extends CFGNode { // If fidxs is negative, then infinite unknown functions long fidxs = tfp.fidxs(); if( fidxs > 0 ) { + // Wipe out the return which matching in the linker table // Walk the (63 max) bits and link for( ; fidxs!=0; fidxs = TypeFunPtr.nextFIDX(fidxs) ) { int fidx = Long.numberOfTrailingZeros(fidxs); TypeFunPtr tfp0 = tfp.makeFrom(fidx); - FunNode fun = CodeGen.CODE._linker.get(tfp0); + FunNode fun = CodeGen.CODE.link(tfp0); if( fun!=null && !fun._folding && !linked(fun) ) link(fun); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java index 94d7eff7..c6d318bd 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFunPtr; @@ -9,14 +10,13 @@ public class FunNode extends RegionNode { // When set true, this Call/CallEnd/Fun/Return is being trivially inlined boolean _folding; - public final TypeFunPtr _sig; // Initial signature - public String _name; // Debug label, optional - private ReturnNode _ret; // Return pointer + private TypeFunPtr _sig; // Initial signature + private ReturnNode _ret; // Return pointer - public FunNode( StartNode start, TypeFunPtr sig, String name ) { super(null,start); _sig=sig; _name=name; } + public FunNode( StartNode start, TypeFunPtr sig ) { super(null,start); _sig=sig; } @Override - public String label() { return _name; } + public String label() { return _sig._name; } // Find the one CFG user from Fun. It's not always the Return, but always // the Return *is* a CFG user of Fun. @@ -28,9 +28,20 @@ public class FunNode extends RegionNode { return null; } + // Cannot create the Return and Fun at the same time; one has to be first. + // So setting the return requires a second step. public void setRet(ReturnNode ret) { _ret=ret; } ReturnNode ret() { assert _ret!=null; return _ret; } + // Signature can improve over time + public TypeFunPtr sig() { return _sig; } + void setSig( TypeFunPtr sig ) { + assert sig.isa(_sig); + if( _sig != sig ) + IterPeeps.add(this); + _sig = sig; + } + @Override public Type compute() { // Only dead if no callers after SCCP @@ -58,4 +69,7 @@ public class FunNode extends RegionNode { public boolean unknownCallers() { return in(1) instanceof StartNode; } @Override public boolean inProgress() { return unknownCallers(); } + + // Add a new function exit point. + public void addReturn(Node ctrl, Node mem, Node rez) { _ret.addReturn(ctrl,mem,rez); } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java index f139e4ca..784b9146 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -22,9 +22,9 @@ public class ParmNode extends PhiNode { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - if( fun()._name.equals("main") && _label.equals("arg") ) + if( "main".equals(fun().sig()._name) && _label.equals("arg") ) return sb.append("arg"); - sb.append(_label).append("("); + sb.append("Parm_").append(_label).append("("); for( Node in : _inputs ) { if (in == null) sb.append("____"); else in._print0(sb, visited); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 9519f5ec..ea211dd2 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -24,7 +24,12 @@ public class ProjNode extends Node implements MultiUse { @Override public int idx() { return _idx; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } + StringBuilder _print1(StringBuilder sb, BitSet visited) { + if( _label != null ) return sb.append(_label); + if( in(0) instanceof CallEndNode cend && cend.call()!=null ) + return cend.call()._print0(sb,visited); + return sb.append("LONELY PROJ"); + } @Override public CFGNode cfg0() { return in(0) instanceof CFGNode cfg ? cfg : in(0).cfg0(); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 5232cfbb..adff7a89 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -38,6 +38,9 @@ public class ReturnNode extends CFGNode { return sb.append(";"); } + // No one unique control follows; can be many call end sites + @Override public CFGNode uctrl() { return null; } + @Override public Type compute() { if( inProgress() ) return TypeTuple.RET; // In progress @@ -46,6 +49,14 @@ public class ReturnNode extends CFGNode { @Override public Node idealize() { if( inProgress() ) return null; + + // Upgrade signature based on return type + Type ret = expr()._type; + TypeFunPtr fcn = _fun.sig(); + assert ret.isa(fcn.ret()); + if( ret != fcn.ret() ) + _fun.setSig(fcn.makeFrom(ret)); + // If dead (cant be reached; infinite loop), kill the exit values if( ctrl()._type==Type.XCONTROL && !(mem() instanceof ConstantNode && expr() instanceof ConstantNode) ) { @@ -54,6 +65,7 @@ public class ReturnNode extends CFGNode { setDef(2,top); return this; } + return null; } @@ -104,8 +116,7 @@ public class ReturnNode extends CFGNode { SB sb = new SB().p("No common type amongst "); if( ti ) sb.p("int and "); if( tf ) sb.p("f64 and "); - if( tp ) sb.p("reference and "); - if( !tp && tn ) sb.p("nil and "); + if( tp || tn ) sb.p("reference and "); return sb.unchar(5).toString(); } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java index ebf650fc..8482b003 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java @@ -53,7 +53,7 @@ public class ScopeMinNode extends Node { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - sb.append("MEM[ "); + sb.append(_inProgress ? "Merge[" : "MEM[ "); for( int j=2; j FIDXS = new HashMap<>(); @@ -56,7 +57,7 @@ public class TypeFunPtr extends TypeNil { public static TypeFunPtr BOT = make((byte)3,TypeTuple.BOT,Type.BOTTOM,-1); public static TypeFunPtr TEST = make((byte)2,TypeTuple.TEST,TypeInteger.BOT,1); public static TypeFunPtr TEST0 = make((byte)3,TypeTuple.TEST,TypeInteger.BOT,3); - public static TypeFunPtr MAIN = makeFun(TypeTuple.MAIN,Type.BOTTOM); + public static TypeFunPtr MAIN = makeFun(TypeTuple.MAIN,Type.BOTTOM).setName("main"); public static void gather(ArrayList ts) { ts.add(TEST); ts.add(TEST0); ts.add(BOT); ts.add(MAIN); } @Override @@ -71,7 +72,7 @@ public class TypeFunPtr extends TypeNil { // RHS is NIL @Override public Type meet0() { return _nil==3 ? this : make((byte)3,_sig,_ret,_fidxs); } - @Override public TypeFunPtr glb() { throw Utils.TODO(); } + @Override public TypeFunPtr glb() { return make(_nil,_sig,_ret,-1); } @Override public boolean isConstant() { return _nil==2 && Long.bitCount(_fidxs)==1; } @@ -79,6 +80,7 @@ public class TypeFunPtr extends TypeNil { public Type arg(int i) { return _sig._types[i]; } public long fidxs() { return _fidxs; } + public Type ret() { return _ret; } @Override int hash() { return Utils.fold(_sig.hashCode() ^ _ret.hashCode() ^ _fidxs ^ super.hash()); } @@ -89,19 +91,22 @@ public class TypeFunPtr extends TypeNil { return _sig == ptr._sig && _ret == ptr._ret && _fidxs == ptr._fidxs && super.eq(ptr); } - public void setName(String name) { + public TypeFunPtr setName(String name) { + if( name==null ) return this; assert _name==null || _name.equals(name); assert _fidxs > 0 && Long.bitCount(_fidxs) == 1; _name = name; + return this; } @Override public String str() { return print(new SB()).toString(); } - @Override public SB print(SB sb) { return _print(sb,false); } - @Override public SB gprint(SB sb) { return _print(sb,true ); } + @Override public SB print(SB sb) { return _print(sb,false,true); } + public SB print(SB sb, boolean n) { return _print(sb,false,n); } + @Override public SB gprint(SB sb) { return _print(sb,true ,true); } private static SB _print(SB sb, boolean g, Type t) { return g ? t.gprint(sb) : t.print(sb); } - private SB _print(SB sb, boolean g) { + private SB _print(SB sb, boolean g, boolean n) { sb.p(x()).p("{ "); - if( _name!=null ) sb.p(_name); + if( n && _name!=null ) sb.p(_name); else { for( Type t : _sig._types ) _print(sb,g,t).p(" "); -- cgit v1.2.3