Chapter 25: Modules, Separate Compilation, and SSA Constructionlinear

Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

1 files changed, 159 insertions, 40 deletions

diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java
index a3b66e09..e65ef6d9 100644
--- a/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -1,12 +1,14 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.codegen.Opto;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 import com.seaofnodes.simple.util.Ary;
 import com.seaofnodes.simple.node.*;
 import java.util.Arrays;
 import java.util.BitSet;
+import java.util.IdentityHashMap;
 import java.util.Random;
 
 /**
@@ -38,7 +40,7 @@ import java.util.Random;
  * <li>Our strong invariant is that for all Nodes, either they are on the worklist
  *   OR no peephole applies.  This invariant is easy to check, although expensive.
  *   Basically the normal "iterate peepholes to a fixed point" is linear, and this
- *   check is linear at each peephole step... so quadratic overall.  Its a useful
+ *   check is linear at each peephole step... so quadratic overall.  It's a useful
  *   assert, but one we can disable once the overall algorithm is stable - and
  *   then turn it back on again when some new set of peepholes is misbehaving.
  *   The code for this is turned on in `IterPeeps.iterate` as `assert
@@ -48,11 +50,11 @@ import java.util.Random;
 public class IterPeeps {
 
     public final WorkList<Node> _work;
-
-    private final WorkList<CallEndNode> _workInline;
+    final WorkList<CallEndNode> _workInline;
+    private int _cnt;
 
     public IterPeeps( long seed ) {
-        _work = new WorkList<>(seed);
+        _work       = new WorkList<>(seed);
         _workInline = new WorkList<>(seed);
     }
 
@@ -62,36 +64,53 @@ public class IterPeeps {
     public void addAll( Ary<Node> ary ) { _work.addAll(ary); }
 
     /**
-     * Iterate peepholes to a fixed point
+     * Iterate peepholes and inlining to a fixed point
      */
     public void iterate( CodeGen code ) {
+        boolean didInline = false;
+        Ary<Node> defer = new Ary<>(Node.class);
         while( true ) {
+            // Clean up everything that does not grow the code
             iteratePeeps(code);
+
+            // Pick an inline candidate, no real heuristic, first come, first served
+            boolean inlined = false;
             CallEndNode cend;
-            while( (cend=_workInline.pop())!=null )
-                if( cend.inlineSmall() ) break;
-            if( cend==null ) return;
+            while( (cend=_workInline.pop()) != null) {
+                if( cend.isDead() ) continue;
+                byte inline = cend.maybeInline();
+                if( inline == -1 ) defer.add(cend);
+                if( inline > 0 ) {
+                    inlined = true;
+                    break;
+                }
+            }
+            // Inlined, run peeps until clean again
+            if( inlined ) { didInline = true; continue; }
+            // No more candidates, check the defer list
+            if( !didInline ) break; // No more progress, so all the "maybe inline after cleanup" do not progress
+            // Some inlining happened, retry all the "try again after cleanup" calls
+            didInline = false;
+            code.addAll(defer);
+            defer.clear();
         }
     }
 
-    // Only try growing inlines once the shrinking peepholes reach a fixed point.
+    // Run all the code-reduction and type-lifting peeps as possible
     private void iteratePeeps( CodeGen code ) {
-        assert progressOnList(code, _work, true);
-        int cnt=0;
+        assert !CodeGen.expensiveAssert(0) || (progressOnList(code, _work) && schedulableUses(code));
 
         Node n;
         while( (n=_work.pop()) != null ) {
             if( n.isDead() )  continue;
-            if( n instanceof CallEndNode cend ) _workInline.push(cend);
-            cnt++;              // Useful for debugging, searching which peephole broke things
-            var obs = CodeGen.CODE._obs;
+            _cnt++;              // Useful for debugging, searching which peephole broke things
+            var obs = code._obs; // Collect peephole neighbors for graph display
             if( obs != null ) obs.before(n);
             Node x = n.peepholeOpt();
+            if( n instanceof CallEndNode cend )
+                _workInline.push(cend);
             if( x != null ) {
-                if( x.isDead() ) {
-                    if( obs != null ) obs.after(n, x, true);
-                    continue;
-                }
+                assert !x.isDead(); // Peepholes return alive answers
                 // peepholeOpt can return brand-new nodes, needing an initial type set
                 if( x._type==null ) x.setType(x.compute());
                 // Changes require neighbors onto the worklist
@@ -101,22 +120,31 @@ public class IterPeeps {
                     // Everybody gets a free "go again" in case they didn't get
                     // made in their final form.
                     _work.push(x);
+                    // A self-returning peephole can have rewritten its input
+                    // edges.  The new defs gained a user and may have
+                    // backwards, user-sensitive peepholes of their own.
+                    for( Node z : x._inputs ) _work.push(z);
                     // If the result is not self, revisit all inputs (because
                     // there's a new user), and replace in the graph.
                     if( x != n ) {
-                        for( Node z : n. _inputs ) _work.push(z);
+                        //for( Node z : n. _inputs ) _work.push(z);
                         for( Node z : x._outputs ) _work.push(z);
                         n.subsume(x);
                     }
                 }
                 // If there are distant neighbors, move to worklist
                 n.moveDepsToWorklist();
-                assert progressOnList(code, _work, true); // Very expensive assert
+                // Very expensive assert.
+                assert !CodeGen.expensiveAssert(_cnt) || (progressOnList(code, _work) && schedulableUses(code));
             }
-            if( n.isUnused() && !(n instanceof StopNode) )
+            boolean unused = n.isUnused();
+            if( unused ) {
+                assert !(n instanceof StopNode); // StopNodes can die if all code in the compunit dies
                 n.kill();       // Just plain dead
-            if( obs != null ) obs.after(n, x, true);
+            }
+            if( obs != null ) obs.after(n, x!=null ? x : unused ? n : null, true);
         }
+        assert !CodeGen.expensiveAssert(0) || schedulableUses(code);
 
     }
 
@@ -133,27 +161,112 @@ public class IterPeeps {
     // {@link #Node.addDep} which is a side effect in an assert.  The {@link
     // #midAssert} is used to stop this side effect.
     // Pessimistic solver assert
-    public static boolean progressOnList(CodeGen code, WorkList<Node> list, boolean dir ) {
+    public static boolean progressOnList(CodeGen code, WorkList<Node> list ) {
         code._midAssert = true;
         Node changed = code._stop.walk( n -> {
-            Node m = n;
+            // Ignore most in-progress things
+            if( n.iskeep() ) return null;
+            // Types must be forwards, even if on the worklist.
             Type nval = n.compute();
-            if( (!n.iskeep() || n._nid<=8) &&  // Types must be forwards, even if on worklist
-                ( dir
-                  ? nval.isa(n._type) // Pesi: new value lifts over old
-                  : n._type.isa(nval) // Opto: new value falls over old
-                  ) ) {
-                if( list.on(n) ) return null;
-                m = n.peepholeOpt();
-                if( m==null ) return null;
+            assert nval.isa(n._type) : "Non-monotonic peep: "+n+"#"+n._nid+" old="+n._type+" new="+nval+" inputs="+inputTypes(n)+" peep="+n;
+            if( list.on(n) )
+                return null;    // On worklist is ok!
+            if( n instanceof CallEndNode cend ) {
+                if( code._iter._workInline.on(cend) )
+                    return null; // On inline worklist is ok!
+                assert cend.maybeInline() <= 0 : "Inline fired and not on worklist, CallEndNode#"+cend._nid;
             }
-            System.err.println("BREAK HERE FOR BUG");
+            // Off list: must be live, in GVN table, and no peeps.
+            assert n.nOuts() > 0 : "Unused live node: "+n;
+            assert code._gvn.get(n)==n : "Not in GVN table: "+n;
+            Node m = n.peepholeOpt();
+            assert m==null : "Peep fired and not on worklist, "+n.getClass().getSimpleName()+"#"+n._nid+" -> "+m;
             return m;
         });
         code._midAssert = false;
         return changed==null;
     }
 
+    private static String inputTypes(Node n) {
+        StringBuilder sb = new StringBuilder("[");
+        for( Node in : n._inputs )
+            sb.append(in==null ? "null" : in.getClass().getSimpleName()+"#"+in._nid+"="+in+":"+in._type+":keep="+in.iskeep()).append(',');
+        return sb.append(']').toString();
+    }
+
+    // GCM assumes every movable node can be placed no earlier than its inputs
+    // and no later than the LCA of its uses.  Catch graphs where a use escapes
+    // above an input-defined branch before the later scheduling pass walks off
+    // the top of the idom tree.
+    private static final IdentityHashMap<Node,CFGNode> earlyCache = new IdentityHashMap<>();
+    private static final BitSet VISIT = new BitSet();
+    public static boolean schedulableUses(CodeGen code) {
+        earlyCache.clear();
+        Node bad = code._stop.walk( n -> {
+            if( n.iskeep() || n.isDead() || n.isConst() ||
+                n instanceof CFGNode || n instanceof PhiNode || n instanceof ProjNode )
+                return null;
+            assert VISIT.isEmpty();
+            CFGNode early = CFGNode.earlyCFG(n,earlyCache,VISIT);
+            VISIT.clear();
+            if( early == null ) return null;
+            CFGNode lca = null;
+            for( Node use : n._outputs ) {
+                CFGNode ublk = useBlock(n,use);
+                if( ublk != null )
+                    lca = ublk.domLCA(lca,null);
+            }
+            if( lca == null ) return null;
+            if( !early.sameFun(lca) )  return null;
+            assert early.dominates(lca,null) : badSchedule(n,early,lca);
+            return null;
+        });
+        return bad == null;
+    }
+
+    private static CFGNode useBlock(Node n, Node use) {
+        if( use == null )
+            return null;
+        if( use instanceof PhiNode phi ) {
+            CFGNode found = null;
+            for( int i=1; i<phi.nIns(); i++ )
+                if( phi.in(i)==n ) {
+                    if( i >= phi.region().nIns() )
+                        return null;
+                    found = phi.region().cfg(i).domLCA(found,null);
+                }
+            return found;
+        }
+        return CFGNode.safeCFG(use);
+    }
+
+    private static String badSchedule(Node n, CFGNode early, CFGNode lca) {
+        StringBuilder sb = new StringBuilder("Unschedulable data node ")
+            .append(n.getClass().getSimpleName()).append('#').append(n._nid)
+            .append(" early=").append(cfg(early))
+            .append(" use-lca=").append(cfg(lca))
+            .append(" node=").append(n).append("\ninputs:");
+        for( int i=0; i<n.nIns(); i++ ) {
+            Node in = n.in(i);
+            sb.append("\n  in").append(i).append(": ").append(node(in))
+              .append(" cfg=").append(cfg(CFGNode.safeCFG(in)));
+        }
+        sb.append("\noutputs:");
+        for( Node use : n._outputs )
+            if( use != null )
+                sb.append("\n  use ").append(node(use))
+                  .append(" block=").append(cfg(useBlock(n,use)));
+        return sb.toString();
+    }
+
+    private static String node(Node n) {
+        return n==null ? "null" : n.getClass().getSimpleName()+"#"+n._nid+" "+n;
+    }
+
+    private static String cfg(CFGNode cfg) {
+        return cfg==null ? "null" : cfg.getClass().getSimpleName()+"#"+cfg._nid+" "+cfg;
+    }
+
     /**
      * Classic WorkList, with a fast add/remove, dup removal, random pull.
      * The Node's nid is used to check membership in the worklist.
@@ -201,12 +314,16 @@ public class IterPeeps {
             for( E n : ary )
                 push(n);
         }
+        public void addAll( E[] es ) {
+            for( E n : es )
+                push(n);
+        }
+
 
         /**
          * True if Node is on the WorkList
          */
         public 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
@@ -220,11 +337,13 @@ public class IterPeeps {
             return x;
         }
 
-        public void clear() {
-            _len = 0;
-            _on.clear();
-            _R.setSeed(_seed);
-            _totalWork = 0;
-        }
+        public boolean isEmpty() { return _len==0; }
+        //Node[] asAry() { return Arrays.copyOf(_es,_len); }
+        //public void clear() {
+        //    _len = 0;
+        //    _on.clear();
+        //    _R.setSeed(_seed);
+        //    _totalWork = 0;
+        //}
     }
 }