Replace loop finding with official algo

Remove old fixLoops, walkInfinite.

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);