From c2cec7cb7fef6df603dd10180de4d0bb715ad47e Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 28 Dec 2024 16:39:00 -0800 Subject: New evaluator, more Compiler Driver cleanup More compiler driver cleanup: Stop only has Return inputs, never an expr. Drop extra lexical scope. Linker table moves to CodeGen. Replace evaluator with a simpler design; I was unable to get the current design to work with the other changes. Updates to old eval; proper idoms; forced type checks; extensions for Fun, Return, Call, CallEnd. Accessor find next control to execute. Accessor for deciding when its ok to optimize a Function/Return, Call/CallEnd, Stop, ScopeMin (merge) Add local scheduling pass. IRPrinter uses SB instead of StringBuilder Spelling SubF comment --- .../main/java/com/seaofnodes/simple/CodeGen.java | 35 +++++-- .../com/seaofnodes/simple/GlobalCodeMotion.java | 4 +- .../main/java/com/seaofnodes/simple/IRPrinter.java | 62 ++++++------ .../main/java/com/seaofnodes/simple/IterPeeps.java | 1 + .../java/com/seaofnodes/simple/ListScheduler.java | 110 +++++++++++++++++++++ .../main/java/com/seaofnodes/simple/Parser.java | 104 ++++++++++--------- .../java/com/seaofnodes/simple/node/CFGNode.java | 14 ++- .../java/com/seaofnodes/simple/node/CallNode.java | 6 +- .../com/seaofnodes/simple/node/ConstantNode.java | 9 +- .../java/com/seaofnodes/simple/node/CtrlNode.java | 14 +++ .../java/com/seaofnodes/simple/node/FunNode.java | 36 ++++--- .../java/com/seaofnodes/simple/node/IfNode.java | 3 + .../java/com/seaofnodes/simple/node/LoopNode.java | 18 ++-- .../main/java/com/seaofnodes/simple/node/Node.java | 5 +- .../java/com/seaofnodes/simple/node/ParmNode.java | 4 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 10 +- .../com/seaofnodes/simple/node/ReturnNode.java | 12 +-- .../com/seaofnodes/simple/node/ScopeMinNode.java | 42 ++++---- .../java/com/seaofnodes/simple/node/ScopeNode.java | 8 +- .../java/com/seaofnodes/simple/node/StartNode.java | 14 ++- .../java/com/seaofnodes/simple/node/StopNode.java | 14 +-- .../java/com/seaofnodes/simple/node/SubFNode.java | 2 +- .../java/com/seaofnodes/simple/node/XCtrlNode.java | 4 +- 23 files changed, 366 insertions(+), 165 deletions(-) create mode 100644 chapter18/src/main/java/com/seaofnodes/simple/ListScheduler.java create mode 100644 chapter18/src/main/java/com/seaofnodes/simple/node/CtrlNode.java (limited to 'chapter18/src/main/java/com') diff --git a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java index 184b6f9c..79d817f8 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java @@ -1,14 +1,13 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import java.util.*; +import java.util.HashMap; public class CodeGen { public enum Phase { - Parse, Opto, TypeCheck, Schedule, RegAlloc; + Parse, Opto, TypeCheck, Schedule, LocalSched, RegAlloc; } public Phase _phase; @@ -20,6 +19,11 @@ public class CodeGen { public StartNode _start; public StopNode _stop ; + + // "Linker" mapping from constant TypeFunPtrs to heads of function + public final HashMap _linker = new HashMap<>(); + + // Last created CodeGen as a global, for easier debugging prints public static CodeGen CODE; @@ -30,6 +34,8 @@ public class CodeGen { public CodeGen parse(boolean disable) { assert _phase == null; _phase = Phase.Parse; + _linker.clear(); + P = new Parser(_src,_arg); Node._disablePeephole = disable; _stop = P.parse(); @@ -51,7 +57,7 @@ public class CodeGen { } public CodeGen typeCheck() { - assert _phase == Phase.Opto; + assert _phase == Phase.Opto || _phase == Phase.Parse; _phase = Phase.TypeCheck; // Type check @@ -62,8 +68,8 @@ public class CodeGen { } - public CodeGen codegen() { return codegen(false); } - public CodeGen codegen(boolean show) { + public CodeGen GCM() { return GCM(false); } + public CodeGen GCM( boolean show) { assert _phase == Phase.TypeCheck; _phase = Phase.Schedule; @@ -74,14 +80,23 @@ public class CodeGen { // TODO: // loop unroll, peel, RCE, etc - GlobalCodeMotion.buildCFG(_start,_stop); - - _phase = Phase.RegAlloc; - return this; } + public CodeGen localSched() { + assert _phase == Phase.Schedule; + _phase = Phase.LocalSched; + ListScheduler.sched(this); + return this; + } + + + // Testing shortcuts + Node ctrl() { return _stop.ret().ctrl(); } + Node expr() { return _stop.ret().expr(); } + String print() { return _stop.print(); } + // Debugging helper @Override public String toString() { return _stop.p(9999); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 7ce12091..6b0956ca 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -54,7 +54,7 @@ public abstract class GlobalCodeMotion { visit.set(n._nid); // Schedule not-pinned not-CFG inputs before self. Since skipping // Pinned, this never walks the backedge of Phis (and thus spins around - // a data-only loop, eventually attempting relying on some pre-visited- + // a data-only loop), eventually attempting relying on some pre-visited- // not-post-visited data op with no scheduled control. for( Node def : n._inputs ) if( def!=null && !(def instanceof PhiNode) ) @@ -65,7 +65,7 @@ public abstract class GlobalCodeMotion { CFGNode early = Parser.START; // Maximally early, lowest idepth if( n.in(0) instanceof CFGNode cfg ) early = cfg; for( int i=1; i early.idepth() ) + if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() ) early = n.in(i).cfg0(); // Latest/deepest input n.setDef(0,early); // First place this can go } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java index 4f422a25..adf67d8b 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; -import java.lang.StringBuilder; import java.util.ArrayList; import java.util.BitSet; import java.util.HashMap; @@ -11,33 +10,31 @@ public class IRPrinter { // Print a node on 1 line, columnar aligned, as: // NNID NNAME DDEF DDEF [[ UUSE UUSE ]] TYPE // 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt - public static void printLine( Node n, StringBuilder sb ) { - sb.append("%4d %-7.7s ".formatted(n._nid,n.label())); - if( n._inputs==null ) { - sb.append("DEAD\n"); - return; - } + public static SB printLine( Node n, SB sb ) { + sb.p("%4d %-7.7s ".formatted(n._nid,n.label())); + if( n._inputs==null ) + return sb.p("DEAD\n"); for( Node def : n._inputs ) - sb.append(def==null ? "____" : "%4d".formatted(def._nid)) + sb.p(def==null ? "____" : "%4d".formatted(def._nid)) // Lazy Phi indicator - .append(n instanceof ScopeMinNode && def instanceof ScopeMinNode ? "^" : " "); + .p(n instanceof ScopeMinNode && def instanceof ScopeMinNode ? "^" : " "); for( int i = n._inputs.size(); i<4; i++ ) - sb.append(" "); - sb.append(" [[ "); + sb.p(" "); + sb.p(" [[ "); for( Node use : n._outputs ) - sb.append(use==null ? "____ " : "%4d ".formatted(use._nid)); + sb.p(use==null ? "____ " : "%4d ".formatted(use._nid)); int lim = 6 - Math.max(n._inputs.size(),4); for( int i = n._outputs.size(); i=0; i-- ) { Node n = rpos.get(i); if( n instanceof CFGNode || n.isMultiHead() ) { - if( !gap ) sb.append("\n"); // Blank before multihead + if( !gap ) sb.p("\n"); // Blank before multihead printLine( n, sb ); // Print head while( --i >= 0 ) { Node t = rpos.get(i); if( !t.isMultiTail() ) { i++; break; } printLine( t, sb ); } - sb.append("\n"); // Blank after multitail + sb.p("\n"); // Blank after multitail gap = true; } else { printLine( n, sb ); @@ -180,7 +177,7 @@ public class IRPrinter { } } // Print by block with least idepth - StringBuilder sb = new StringBuilder(); + SB sb = new SB(); Ary bns = new Ary<>(Node.class); while( !ds.isEmpty() ) { CFGNode blk = null; @@ -193,16 +190,15 @@ public class IRPrinter { ns.remove(blk); // Print block header - sb.append("%-13.13s".formatted(label(blk)+":")); - sb.append( " ".repeat(4) ).append(" [[ "); + sb.p("%-13.13s".formatted(label(blk)+":")); + sb.p( " ".repeat(4) ).p(" [[ "); if( blk instanceof StartNode ) ; else if( blk instanceof RegionNode || blk instanceof StopNode ) for( int i=(blk instanceof StopNode ? 3 : 1); i ds, ArrayList ns, Node node, int d ) { Integer nd = ds.get(node._nid); - if( nd!=null && d >= nd ) return; // Been there, done that + if( nd!=null && d <= nd ) return; // Been there, done that Integer old = ds.put(node._nid,d) ; if( old == null ) ns.add(node); if( d == 0 ) return; // Depth cutoff for( Node def : node._inputs ) if( def != null && + !(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) ) @@ -258,12 +255,11 @@ public class IRPrinter { if( blk instanceof StartNode ) return "START"; return (blk instanceof LoopNode ? "LOOP" : "L")+blk._nid; } - static void label( StringBuilder sb, CFGNode blk ) { + static void label( SB sb, CFGNode blk ) { if( !blk.blockHead() ) blk = blk.cfg(0); - sb.append( "%-9.9s ".formatted( label( blk ) ) ); + sb.p( "%-9.9s ".formatted( label( blk ) ) ); } - static void printLine( Node n, StringBuilder sb, Ary bns, int i, HashMap ds, ArrayList ns ) { - sb.append(ds.get(n._nid)); + static void printLine( Node n, SB sb, Ary bns, int i, HashMap ds, ArrayList ns ) { printLine( n, sb ); if( i != -1 ) bns.del(i); ds.remove(n._nid); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java index a321b13e..998bd4f0 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -182,6 +182,7 @@ public abstract class IterPeeps { * True if Node is on the WorkList */ boolean on( E x ) { return _on.get(x._nid); } + boolean isEmpty() { return _len==0; } /** * Removes a random Node from the WorkList; null if WorkList is empty diff --git a/chapter18/src/main/java/com/seaofnodes/simple/ListScheduler.java b/chapter18/src/main/java/com/seaofnodes/simple/ListScheduler.java new file mode 100644 index 00000000..252a8f8e --- /dev/null +++ b/chapter18/src/main/java/com/seaofnodes/simple/ListScheduler.java @@ -0,0 +1,110 @@ + package com.seaofnodes.simple; + +import com.seaofnodes.simple.IterPeeps.WorkList; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import java.util.*; + +public abstract class ListScheduler { + + private static final BitSet VISIT = new BitSet(); + private static int[] BCNTS; + public static void sched( CodeGen code ) { + assert VISIT.isEmpty(); + BCNTS = new int[Node.UID()]; + walk(code._start,VISIT); + VISIT.clear(); + } + + // Visit all CFG nodes + static void walk( CFGNode cfg, BitSet visit ) { + if( visit.get(cfg._nid) ) return; + visit.set(cfg._nid); + local(cfg); + for( Node n : cfg._outputs ) + if( n instanceof CFGNode c ) + walk(c,visit); + } + + // Local schedule this one CFG + static void local( CFGNode bb ) { + if( !bb.blockHead() || bb instanceof StopNode ) return; + Node[] uses = bb._outputs._es; + int ulen = bb._outputs._len; + + // Count block-locals + for( int i=0; i 0; + + // Classic list scheduler. Behind sched is scheduled. Between sched + // and ready have zero counts and are ready to schedule. Ahead of + // ready is undefined. + // + // As nodes are scheduled, the nodes they use decrement their _bcnt. Once + // that gets to 0, all the nodes using it are scheduled, so it's ready. + int sched = 0; + while( sched < ulen ) { + assert sched < ready : "Scheduling nodes that are not ready. Probably due to duplicate nodes in the user list."; + int pick = best(uses, sched,ready); // Pick best + Node best = uses[pick]; // Swap best to head of ready + uses[pick] = uses[sched]; + uses[sched++] = best; // And move it into the scheduled set + // Lower ready count of users + for( Node use : best._outputs ) + if( use instanceof ProjNode ) { + for( Node useuse : use._outputs ) + ready = ready(bb,useuse,ready); + } else + ready = ready(bb, use,ready); + } + } + + private static int ready(CFGNode bb, Node use, int ready) { + if( use != null && use.in(0)==bb && !(use instanceof PhiNode) ) { + assert BCNTS[use._nid] >= 1; + if( --BCNTS[use._nid] == 0 ) + bb._outputs._es[ready++] = use; // Became ready, move into ready set + } + return ready; + } + + + // Pick best between sched and ready. + private static int best( Node[] uses, int sched, int ready ) { + int pick = sched; + int score = score(uses[pick]); + for( int i=sched+1; i score ) + { score = nscore; pick = i; } + } + return pick; + } + + // Highest score wins. Max at 1000, min at 10, except specials. + private static int score( Node n ) { + if( n.isMultiTail() ) return 1001; // Pinned just behind the multi-head + if( n instanceof CFGNode ) return n instanceof ReturnNode ? 2 : 1; // Pinned at block exit + + // Nothing special + return 500; + } + +} diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java index f6bf71a9..ac497fe8 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java @@ -98,16 +98,12 @@ public class Parser { // Mapping from a type name to the constructor for a Type. public final HashMap INITS; - // "Linker" mapping from constant TypeFunPtrs to heads of function - public static final HashMap LINKER = new HashMap<>(); - public Parser(String source) { this(source, TypeInteger.BOT); } public Parser(String source, TypeInteger arg) { Node.reset(); IterPeeps.reset(); - LINKER.clear(); _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; @@ -154,38 +150,38 @@ 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, ctrl); - _scope.define(ScopeNode.MEM0, TypeMem.BOT , false, mem ); - _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, arg ); - - // 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()); + //// 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()); // Parse whole program, as-if function header "{ int arg -> body }" ReturnNode ret = parseFunctionBody("main",TypeFunPtr.MAIN,"arg"); - LINKER.put(TypeFunPtr.MAIN,ret.fun()); - main.peephole(); - if( cend.peephole() != null ) - IterPeeps.addAll(cend._outputs); + CodeGen.CODE._linker.put(TypeFunPtr.MAIN,ret.fun()); + //main.peephole(); + //if( cend.peephole() != null ) + // IterPeeps.addAll(cend._outputs); if( !_lexer.isEOF() ) throw _errorSyntax("unexpected"); // Clean up and reset - _scope.kill(); _xScopes.pop(); + _scope.kill(); for( StructNode init : INITS.values() ) init.unkeep().kill(); INITS.clear(); @@ -208,6 +204,7 @@ public class Parser { PhiNode rmem = new PhiNode(ScopeNode.MEM0,TypeMem.BOT,r,null); PhiNode rrez = new PhiNode(ScopeNode.ARG0,Type.BOTTOM,r,null); ReturnNode ret = new ReturnNode(r, rmem, rrez, fun); + fun.setRet(ret); assert ret.inProgress(); STOP.addDef(ret); @@ -217,10 +214,9 @@ public class Parser { _scope.push(); ctrl(fun); // Scope control from function // Private mem alias tracking per function - ScopeMinNode startMem = _scope.mem(); - ScopeMinNode mem = new ScopeMinNode(); + ScopeMinNode mem = new ScopeMinNode(true); mem.addDef(null); // Alias#0 - mem.addDef(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,startMem).peephole()); // All aliases + mem.addDef(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).peephole()); // All aliases _scope.mem(mem); // All args, "as-if" called externally for( int i=0; i new AddNode(rvalue,null); - case '-' -> new SubNode(rvalue,null); - case '*' -> new MulNode(rvalue,null); - case '/' -> new DivNode(rvalue,null); - case 1 -> new AddNode(rvalue,con( 1)); - case (char)-1 -> new AddNode(rvalue,con(-1)); - default -> throw Utils.TODO(); + case 1, (char)-1, + '+' -> new AddNode(lhs,rhs); + case '-' -> new SubNode(lhs,rhs); + case '*' -> new MulNode(lhs,rhs); + case '/' -> new DivNode(lhs,rhs); + default -> throw Utils.TODO(); }; - // Return pre-value (x+=1) or post-value (x++) - boolean pre = op.in(2)==null; - // Parse RHS argument as needed - if( pre ) - { op.keep().setDef(2,parseAsgn()); op.unkeep(); } - else rvalue.keep(); // Keep post-value across peeps - op = zsMask(peep(op),n.type()); + + op = zsMask(peep(op.widen()),n.type()); _scope.update(n,op); - return pre ? op : rvalue.unkeep(); + // Return pre-value (x+=1) or post-value (x++) + lhs.unkeep(); + return (byte)ch== 1 || (byte)ch== -1 ? lhs : op; } ScopeMinNode.Var requireLookupId(String msg) { 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 bed4eb17..bacc1935 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -28,6 +28,17 @@ public abstract class CFGNode extends Node { // Block head is Start, Region, CProj, but not e.g. If, Return, Stop public boolean blockHead() { return false; } + // Get the one control following; error to call with more than one e.g. an + // IfNode or other multi-way branch. + public CFGNode uctrl() { + CFGNode c = null; + for( Node n : _outputs ) + if( n instanceof CFGNode cfg ) + { assert c==null; c = cfg; } + return c; + } + + // ------------------------------------------------------------------------ /** * Immediate dominator tree depth, used to approximate a real IDOM during @@ -90,13 +101,14 @@ public abstract class CFGNode extends Node { _pre = pre++; // Pre-walk for( Node use : _outputs ) - if( use instanceof CFGNode usecfg ) + if( use instanceof CFGNode usecfg && !(usecfg instanceof XCtrlNode) ) 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; // Child visited but not post-visited? if( !post.get(usecfg._nid) ) { // Must be a backedge to a LoopNode then 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 0839ad2c..3ec1cd0c 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFunPtr; @@ -21,7 +21,7 @@ public class CallNode extends CFGNode { String fname = null; Node fptr = fptr(); if( fptr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) - fname = Parser.LINKER.get(tfp)._name; + fname = CodeGen.CODE._linker.get(tfp)._name; if( fname==null ) fptr._print0(sb,visited); else sb.append(fname); sb.append("( "); @@ -62,7 +62,7 @@ public class CallNode extends CFGNode { for( ; fidxs!=0; fidxs = TypeFunPtr.nextFIDX(fidxs) ) { int fidx = Long.numberOfTrailingZeros(fidxs); TypeFunPtr tfp0 = tfp.makeFrom(fidx); - FunNode fun = Parser.LINKER.get(tfp0); + FunNode fun = CodeGen.CODE._linker.get(tfp0); if( fun!=null && !fun._folding && !linked(fun) ) link(fun); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 406b20ca..e54797a5 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -19,12 +19,18 @@ import java.util.BitSet; * The Constant's value is the value stored in it. */ public class ConstantNode extends Node { - Type _con; + public final Type _con; public ConstantNode( Type type ) { super(Parser.START); _con = type; } + public static Node make( Type type ) { + if( type==Type. CONTROL ) return new CtrlNode(); + if( type==Type.XCONTROL ) return new XCtrlNode(); + return new ConstantNode(type); + } + @Override public String label() { return "#"+_con; } @@ -37,6 +43,7 @@ public class ConstantNode extends Node { } @Override public boolean isMultiTail() { return true; } + @Override public boolean isConst() { return true; } @Override public Type compute() { return _con; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CtrlNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CtrlNode.java new file mode 100644 index 00000000..162417bb --- /dev/null +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CtrlNode.java @@ -0,0 +1,14 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + +public class CtrlNode extends CFGNode { + public CtrlNode() { super(Parser.START); } + @Override public String label() { return "Ctrl"; } + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Cctrl"); } + @Override public boolean isConst() { return true; } + @Override public Type compute() { return Type.CONTROL; } + @Override public Node idealize() { return null; } +} 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 9087926e..94d7eff7 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -9,24 +9,27 @@ public class FunNode extends RegionNode { // When set true, this Call/CallEnd/Fun/Return is being trivially inlined boolean _folding; - TypeFunPtr _sig; // Initial signature may be missing return - String _name; // Debug label, optional + public final TypeFunPtr _sig; // Initial signature + public String _name; // Debug label, optional + private ReturnNode _ret; // Return pointer public FunNode( StartNode start, TypeFunPtr sig, String name ) { super(null,start); _sig=sig; _name=name; } @Override public String label() { return _name; } - ReturnNode ret() { - ReturnNode ret=null; + // Find the one CFG user from Fun. It's not always the Return, but always + // the Return *is* a CFG user of Fun. + @Override public CFGNode uctrl() { for( Node n : _outputs ) - if( n instanceof ReturnNode ret0 ) { - assert ret==null || ret==ret0; // Found more than one return - ret=ret0; - } - return ret; + if( n instanceof CFGNode cfg && + (cfg instanceof RegionNode || cfg.cfg0()==this) ) + return cfg; + return null; } + public void setRet(ReturnNode ret) { _ret=ret; } + ReturnNode ret() { assert _ret!=null; return _ret; } @Override public Type compute() { @@ -36,12 +39,23 @@ public class FunNode extends RegionNode { @Override public Node idealize() { + // When can we assume no callers? Or no other callers (except main)? + // In a partial compilation, we assume Start gets access to any/all + // top-level public structures and recursively what they point to. + // This in turn is valid arguments to every callable function. + // + // In a total compilation, we can start from Start and keep things + // more contained. + + // If no default/unknown caller, use the normal RegionNode ideal rules // to collapse - if( inProgress() ) return null; + if( unknownCallers() ) return null; return super.idealize(); } // Always in-progress until we run out of unknown callers - @Override public boolean inProgress() { return in(1) instanceof StartNode; } + public boolean unknownCallers() { return in(1) instanceof StartNode; } + + @Override public boolean inProgress() { return unknownCallers(); } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java index dcd2d4c7..1e6b2878 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -26,6 +26,9 @@ public class IfNode extends CFGNode implements MultiNode { public Node ctrl() { return in(0); } public Node pred() { return in(1); } + // No one unique control follows + @Override public CFGNode uctrl() { return null; } + @Override public Type compute() { // If the If node is not reachable then neither is any following Proj diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 33420eb9..3f2ae149 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -58,17 +58,13 @@ public class LoopNode extends RegionNode { setDef(2,f); // Now fold control into the exit - if( fun!=null ) - throw Utils.TODO(); - - // If not in a function, look for a last-level merge point; - // make if not there. - RegionNode ctrl = stop.ctrl() instanceof RegionNode r ? r : new RegionNode(null,stop.ctrl()); - PhiNode mem = stop.mem () instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode("",stop.mem ()._type,ctrl,stop.mem ()); - PhiNode expr = stop.expr() instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode("",stop.expr()._type,ctrl,stop.expr()); - if( stop.ctrl()!=ctrl ) stop.setDef(0,ctrl); - if( stop.mem ()!=mem ) stop.setDef(1,mem ); - if( stop.expr()!=expr ) stop.setDef(2,expr); + ReturnNode ret = fun.ret(); + RegionNode ctrl = ret.ctrl() instanceof RegionNode r ? r : new RegionNode(null,ret.ctrl()); + PhiNode mem = ret.mem () instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode(ctrl,ret.mem ()); + PhiNode expr = ret.expr() instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode(ctrl,ret.expr()); + if( ret.ctrl()!=ctrl ) ret.setDef(0,ctrl); + if( ret.mem ()!=mem ) ret.setDef(1,mem ); + if( ret.expr()!=expr ) ret.setDef(2,expr); Node top = new ConstantNode(Type.TOP).peephole(); ctrl.addDef(t ); mem .addDef(top); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java index 6369fb01..cc7a1d13 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java @@ -114,6 +114,7 @@ public abstract class Node { public boolean isMultiHead() { return false; } public boolean isMultiTail() { return false; } + public boolean isConst () { return false; } // ------------------------------------------------------------------------ // Graph Node & Edge manipulation @@ -337,8 +338,8 @@ public abstract class Node { Type old = setType(compute()); // Replace constant computations from non-constants with a constant node - if( !(this instanceof ConstantNode) && !(this instanceof XCtrlNode) && _type.isHighOrConst() ) - return (_type==Type.XCONTROL ? new XCtrlNode() : new ConstantNode(_type)).peepholeOpt(); + if( _type.isHighOrConst() && !isConst() ) + return ConstantNode.make(_type).peepholeOpt(); // Global Value Numbering if( _hash==0 ) { 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 136494b5..f139e4ca 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -7,7 +7,7 @@ import java.util.BitSet; public class ParmNode extends PhiNode { // Argument indices are mapped one-to-one on CallNode inputs - final int _idx; // Argument index + public final int _idx; // Argument index public ParmNode(String label, int idx, Type declaredType, Node... inputs) { super(label,declaredType,inputs); @@ -18,7 +18,7 @@ public class ParmNode extends PhiNode { @Override public String glabel() { return _label; } - FunNode fun() { return (FunNode)in(0); } + public FunNode fun() { return (FunNode)in(0); } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 6dd4f57d..91334b6c 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -8,7 +8,7 @@ import java.util.BitSet; public class PhiNode extends Node { - final String _label; + public final String _label; // The Phi type we compute must stay within the domain of the Phi. // Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. @@ -16,6 +16,14 @@ public class PhiNode extends Node { public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } + public PhiNode(RegionNode r, Node sample) { + super(r); + _label = ""; + _declaredType = sample._type; + while( nIns() < r.nIns() ) + addDef(sample); + } + @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } @Override public String glabel() { return "φ_"+_label; } 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 b305a96e..35563d6e 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,8 +1,7 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.type.*; - import java.util.BitSet; /** @@ -16,14 +15,16 @@ import java.util.BitSet; */ public class ReturnNode extends CFGNode { + public final FunNode _fun; public ReturnNode(Node ctrl, Node mem, Node data, FunNode fun) { - super(ctrl, mem, data, fun); + super(ctrl, mem, data); + _fun = fun; } public Node ctrl() { return in(0); } public Node mem () { return in(1); } public Node expr() { return in(2); } - public FunNode fun() { return (FunNode)in(3); } + public FunNode fun() { return _fun; } @Override public String label() { return "Return"; } @@ -31,7 +32,6 @@ public class ReturnNode extends CFGNode { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("return "); - if( expr()==null ) return sb.append("INPROGRESS"); expr()._print0(sb, visited); return sb.append(";"); } @@ -45,7 +45,7 @@ public class ReturnNode extends CFGNode { @Override public Node idealize() { return null; } public boolean inProgress() { - return ctrl() instanceof RegionNode r && r.inProgress(); + return ctrl().getClass() == RegionNode.class && ((RegionNode)ctrl()).inProgress(); } // Add a return exit to the current parsing function 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 f5a33890..f29ed20b 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java @@ -11,6 +11,8 @@ import static com.seaofnodes.simple.Utils.TODO; /* */ public class ScopeMinNode extends Node { + public final boolean _inProgress; + /** The tracked fields are now complex enough to deserve a array-of-structs layout */ public static class Var { @@ -39,8 +41,12 @@ public class ScopeMinNode extends Node { } } - public ScopeMinNode() { _type = TypeMem.BOT; } + public ScopeMinNode(boolean inProgress) { _type = TypeMem.BOT; _inProgress = inProgress; } + + // If being used by a Scope, this is "in progress" from the Parser. + // Otherwise its a memory merge + boolean inProgress() { return _inProgress; } @Override public String label() { return "ALLMEM"; } @Override public boolean isMem() { return true; } @@ -63,6 +69,17 @@ public class ScopeMinNode extends Node { return sb.append("]"); } + // Make a memory merge: no longer a Scope really, tracking memory state but + // not related to the parser in any way. + public Node merge() { + // Force default memory to not be lazy + ScopeMinNode merge = new ScopeMinNode(false); + for( Node n : _inputs ) + merge.addDef(n); + merge._mem(1,null); + return merge.peephole(); + } + @Override public Type compute() { return TypeMem.BOT; } @@ -127,13 +144,13 @@ public class ScopeMinNode extends Node { // Fill in the backedge of any inserted Phis void _endLoopMem( ScopeNode scope, ScopeMinNode back, ScopeMinNode exit ) { - for( int i=2; i(Var .class); _lexSize= new Ary<>(Integer.class); _inCons = new Ary<>(Boolean.class); @@ -113,8 +113,8 @@ public class ScopeNode extends ScopeMinNode { * Create a new variable name in the current scope */ public boolean define( String name, Type declaredType, boolean xfinal, Node init ) { - assert name.charAt(0)!='$' || _lexSize.size()==1; // Later scopes do not define memory - if( _lexSize._len > 1 ) + assert _lexSize.isEmpty() || name.charAt(0)!='$' ; // Later scopes do not define memory + if( _lexSize._len > 0 ) for( int i=_vars.size()-1; i>=_lexSize.last(); i-- ) if( _vars.get(i)._name.equals(name) ) return false; // Double define @@ -203,7 +203,7 @@ public class ScopeNode extends ScopeMinNode { dup.addDef(ctrl()); // Control input is just copied // Memory input is a shallow copy - ScopeMinNode memdup = new ScopeMinNode(), mem = mem(); + ScopeMinNode memdup = new ScopeMinNode(true), mem = mem(); memdup.addDef(null); memdup.addDef(loop ? this : mem.in(1)); for( int i=2; i