diff options
Diffstat (limited to 'chapter17/src/main/java/com')
8 files changed, 77 insertions, 96 deletions
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index fb6477d3..9698abd9 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -16,43 +16,6 @@ public abstract class GlobalCodeMotion { schedLate( stop); } - // ------------------------------------------------------------------------ - // Backwards walk on the CFG only, looking for unreachable code - which has - // to be an infinite loop. Insert a bogus never-taken exit to Stop, so the - // loop becomes reachable. Also, set loop nesting depth - public static void fixLoops(StopNode stop) { - // Backwards walk from Stop, looking for unreachable code - BitSet visit = new BitSet(); - HashSet<CFGNode> unreach = new HashSet<>(); - unreach.add(Parser.START); - for( Node ret : stop._inputs ) - ((ReturnNode)ret).walkUnreach(visit,unreach); - if( unreach.isEmpty() ) return; - - // Forwards walk from unreachable, looking for loops with no exit test. - visit.clear(); - for( CFGNode cfg : unreach ) - walkInfinite(cfg,visit,stop); - // Set loop depth on remaining graph - unreach.clear(); - visit.clear(); - for( Node ret : stop._inputs ) - ((ReturnNode)ret).walkUnreach(visit,unreach); - assert unreach.isEmpty(); - } - - - // Forwards walk over previously unreachable, looking for loops with no - // exit test. - static private void walkInfinite( CFGNode n, BitSet visit, StopNode stop ) { - if( visit.get(n._nid) ) return; // Been there, done that - visit.set(n._nid); - if( n instanceof LoopNode loop ) - loop.forceExit(stop); - for( Node use : n._outputs ) - if( use instanceof CFGNode cfg ) - walkInfinite(cfg,visit,stop); - } // ------------------------------------------------------------------------ // Visit all nodes in CFG Reverse Post-Order, essentially defs before uses @@ -210,7 +173,7 @@ public abstract class GlobalCodeMotion { // Least loop depth first, then largest idepth private static boolean better( CFGNode lca, CFGNode best ) { - return lca._loopDepth < best._loopDepth || + return lca.loopDepth() < best.loopDepth() || (lca.idepth() > best.idepth() || best instanceof IfNode); } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter17/src/main/java/com/seaofnodes/simple/IRPrinter.java index 418cda29..7ef55a3f 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -216,10 +216,11 @@ public class IRPrinter { // Print block header sb.append("%-13.13s".formatted(label(blk)+":")); sb.append( " ".repeat(4) ).append(" [[ "); - if( blk instanceof RegionNode || blk instanceof StopNode ) + if( blk instanceof StartNode ) ; + else if( blk instanceof RegionNode || blk instanceof StopNode ) for( int i=(blk instanceof StopNode ? 0 : 1); i<blk.nIns(); i++ ) label(sb,blk.cfg(i)); - else if( !(blk instanceof StartNode) ) + else label(sb,blk.cfg(0)); sb.append(" ]] \n"); diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 3513f265..052ad8fc 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -55,27 +55,78 @@ public abstract class CFGNode extends Node { return lhs; } - // Loop nesting depth - public int _loopDepth; - public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(0).loopDepth()) : _loopDepth; } - // Anti-dependence field support public int _anti; // Per-CFG field to help find anti-deps // ------------------------------------------------------------------------ - // Support routines for Global Code Motion + // Loop nesting + public LoopNode loop() { return _ltree._head; } + public int loopDepth() { return _ltree==null ? 0 : _ltree.depth(); } + + LoopTree _ltree; + int _pre; // Pre-order numbers for loop tree finding + private static class LoopTree { + LoopTree _par; + final LoopNode _head; + int _depth; + LoopTree(LoopNode head) { _head = head; } + @Override public String toString() { return "LOOP"+_head._nid; } + int depth() { + return _depth==0 ? (_par==null ? 0 : (_depth = _par.depth()+1)) : _depth; + } + } - // Tik-tok recursion pattern. This method is final, and every caller does - // this work. - public final void walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - if( visit.get(_nid) ) return; - visit.set(_nid); - _walkUnreach(visit,unreach); - unreach.remove(this); // Since we reached here... Node was not unreachable + // ------------------------------------------------------------------------ + // 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) { + _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); + _bltWalk(2,stop, new BitSet()); } + private int _bltWalk(int pre, StopNode stop, BitSet post) { + // Pre-walked? + if( _pre!=0 ) return pre; + _pre = pre++; + // Pre-walk + for( Node use : _outputs ) + if( use instanceof CFGNode usecfg ) + pre = usecfg._bltWalk(pre,stop,post); - // Tik-tok recursion pattern; not-final; callers override this. - void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - cfg(0).walkUnreach(visit,unreach); + // Post-order work: find innermost loop + LoopTree inner = null, ltree; + for( Node use : _outputs ) { + if( !(use instanceof CFGNode usecfg) ) continue; + // Child visited but not post-visited? + if( !post.get(usecfg._nid) ) { + // Must be a backedge to a LoopNode then + ltree = usecfg._ltree = new LoopTree((LoopNode)usecfg); + } else { + // Take child's loop choice, which must exist + ltree = usecfg._ltree; + // If falling into a loop, use the target loop's parent instead + if( ltree._head == usecfg ) { + if( ltree._par == null ) + // This loop never had an If test choose to take its + // exit, i.e. it is a no-exit infinite loop. + ltree._par = ltree._head.forceExit(stop)._ltree; + ltree = ltree._par; + } + } + // Sort inner loops. The decision point is some branch far removed + // from either loop head OR either backedge so requires pre-order + // numbers to figure out innermost. + if( inner == null ) { inner = ltree; continue; } + if( inner == ltree ) continue; // No change + LoopTree outer = ltree._head._pre > inner._head._pre ? inner : ltree; + inner = ltree._head._pre > inner._head._pre ? ltree : inner; + inner._par = outer; + } + // Set selected loop + if( inner!=null ) + _ltree = inner; + // Tag as post-walked + post.set(_nid); + return pre; } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/IfNode.java index 2f3798d7..513b4721 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -63,10 +63,4 @@ public class IfNode extends CFGNode implements MultiNode { return null; } - @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - for( Node proj : _outputs ) - if( ((CProjNode)proj)._loopDepth == 0 ) - unreach.add((CProjNode)proj); - super._walkUnreach(visit,unreach); - } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/LoopNode.java index e5f34833..ecda9c63 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -32,26 +32,9 @@ public class LoopNode extends RegionNode { // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } - @Override public int loopDepth() { - if( _loopDepth!=0 ) return _loopDepth; // Was already set - _loopDepth = entry().loopDepth()+1; // Entry depth plus one - // One-time tag loop exits - for( CFGNode idom = back(); idom!=this; idom = idom.idom() ) { - // Walk idom in loop, setting depth - idom._loopDepth = _loopDepth; - // Mark backedge loop depth. The loop exit hits the CProj before the - // If, instead of jumping from Region directly to If. The other - // arm is either a loop exit OR if this is a split tail the other - // arm leads to a inner loop. - if( idom instanceof CProjNode cproj ) - break; - } - return _loopDepth; - } - // If this is an unreachable loop, it may not have an exit. If it does not // (i.e., infinite loop), force an exit to make it reachable. - public void forceExit( StopNode stop ) { + public StopNode forceExit( StopNode stop ) { // Walk the backedge, then immediate dominator tree util we hit this // Loop again. If we ever hit a CProj from an If (as opposed to // directly on the If) we found our exit. @@ -60,7 +43,7 @@ public class LoopNode extends RegionNode { if( x instanceof CProjNode exit && exit.in(0) instanceof IfNode iff ) { CFGNode other = iff.cproj(1-exit._idx); if( other.loopDepth() < loopDepth() ) - return; // Found an exit, not an infinite loop + return stop; // Found an exit, not an infinite loop } x = x.idom(); } @@ -73,5 +56,6 @@ public class LoopNode extends RegionNode { CProjNode f = new CProjNode(iff,1,"False"); setDef(2,f); stop.addDef(new ReturnNode(t,Parser.ZERO,null)); + return stop; } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 9e0f46cb..fb39af17 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -108,13 +108,6 @@ public class RegionNode extends CFGNode { return lca; } - @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - for( int i=1; i<nIns(); i++ ) - cfg(i).walkUnreach(visit,unreach); - } - - @Override public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(1).loopDepth()) : _loopDepth; } - // True if last input is null public final boolean inProgress() { return nIns()>1 && in(nIns()-1) == null; diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java index d82030f8..ab6e4931 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -14,11 +14,11 @@ import static com.seaofnodes.simple.Utils.TODO; * In ch10 we also add mem aliases as structs get defined; each field in struct * adds a distinct alias to Start's tuple. */ -public class StartNode extends CFGNode implements MultiNode { +public class StartNode extends LoopNode implements MultiNode { final Type _arg; - public StartNode(Type arg) { super(); _arg = arg; _type = compute(); } + public StartNode(Type arg) { super(null); _arg = arg; _type = compute(); } @Override public String label() { return "Start"; } @@ -41,7 +41,4 @@ public class StartNode extends CFGNode implements MultiNode { @Override public int idepth() { return 0; } @Override public CFGNode idom(Node dep) { return null; } - @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { } - - @Override public int loopDepth() { return (_loopDepth=1); } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java index 5a02190a..867225cb 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.GlobalCodeMotion; import com.seaofnodes.simple.GraphVisualizer; @@ -63,8 +64,6 @@ public class StopNode extends CFGNode { } @Override public CFGNode idom(Node dep) { return null; } - @Override public int loopDepth() { return (_loopDepth=1); } - public Node addReturn(Node node) { return addDef(node); } @@ -77,8 +76,7 @@ public class StopNode extends CFGNode { return this; } StopNode GCM(boolean show) { - // Break infinite loops, forcing a Never-branch to exit - GlobalCodeMotion.fixLoops(this); + Parser.START.buildLoopTree(this); if( show ) System.out.println(new GraphVisualizer().generateDotOutput(this,null,null)); GlobalCodeMotion.buildCFG(this); |