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, 111 insertions, 31 deletions

diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index 6805c1ef..fe3382a6 100644
--- a/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -1,13 +1,11 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.type.*;
 import com.seaofnodes.simple.util.Ary;
-import com.seaofnodes.simple.util.Utils;
+
 import java.util.BitSet;
-import java.util.HashMap;
-import java.util.HashSet;
+import java.util.IdentityHashMap;
 
 /** Control Flow Graph Nodes
  * <p>
@@ -103,11 +101,78 @@ public abstract class CFGNode extends Node {
         return lhs;
     }
 
+    // Safe read of the control input of a data node.
+    public static CFGNode safeCFG(Node n) {
+        if( n==null ) return null;
+        if( !(n.in(0) instanceof CFGNode cfg) ) return null;
+        return cfg._safeCFG();
+    }
+    private CFGNode _safeCFG() {
+        return switch(this) {
+        case CallNode call when call.cend()._folding -> call.cfg0()._safeCFG();
+        case CallEndNode cend when cend._folding -> cend.cfg(1)._safeCFG();
+        case FunNode fun when fun._folding -> fun.cfg(1)._safeCFG();
+        case ReturnNode ret when ret.fun()._folding -> ret.cfg0()._safeCFG();
+        default -> this;
+        };
+    }
+
+    // True when this node dominates `sub` in the current idom tree.
+    public boolean dominates(CFGNode sub, Node dep) {
+        for( CFGNode cfg=sub; cfg!=null; cfg=cfg.idom() )
+            if( cfg == this )
+                return true;
+            else if( dep != null ) dep.addDep(cfg);
+        return false;
+    }
+
+    public static CFGNode deepest(CFGNode a, CFGNode b) {
+        if( a == null ) return b;
+        if( b == null ) return a;
+        return b.idepth() > a.idepth() ? b : a;
+    }
+
+    public static CFGNode earlyCFG(Node n) {
+        return earlyCFG(n,new IdentityHashMap<>(),new BitSet());
+    }
+
+    public static CFGNode earlyCFG(Node n, IdentityHashMap<Node,CFGNode> cache, BitSet active) {
+        if( n == null ) return null;
+        CFGNode cached = cache.get(n);
+        if( cached != null ) return cached;
+        if( active.get(n._nid) )
+            return safeCFG(n);
+        active.set(n._nid);
+        CFGNode early = null;
+        for( Node x : n._inputs )
+            early = deepest(early,defCFG(x,cache,active));
+        active.clear(n._nid);
+        cache.put(n,early);
+        return early;
+    }
+
+    private static CFGNode defCFG(Node n, IdentityHashMap<Node,CFGNode> cache, BitSet active) {
+        if( n == null || n.isConst() )  return null; // no impact on early cfg
+        return switch( n ) {
+        case PhiNode phi -> phi.region();
+        case CFGNode cfg -> cfg;
+        case ProjNode projNode -> safeCFG( n );
+        default -> earlyCFG( n, cache, active );
+        };
+    }
+
+    public boolean sameFun(CFGNode that) {
+        FunNode fun = fun();
+        return fun != null && fun == that.fun();
+    }
+
     // Find nearest enclosing FunNode
     public FunNode fun() {
         CFGNode cfg = this;
-        while( !(cfg instanceof FunNode fun) )
+        while( !(cfg instanceof FunNode fun) ) {
+            if( cfg==null ) return null;
             cfg = cfg.idom();
+        }
         return fun;
     }
 
@@ -118,13 +183,13 @@ public abstract class CFGNode extends Node {
 
     public LoopTree _ltree;
     public int _pre;            // Pre-order numbers for loop tree finding
-    static class LoopTree {
-        LoopTree _par;
-        final LoopNode _head;
-        int _depth;
+    public static class LoopTree {
+        public LoopTree _par;
+        public final LoopNode _head;
+        public int _depth;
         LoopTree(LoopNode head) { _head = head; }
-        @Override public String toString() { return "LOOP"+_head._nid; }
-        int depth() {
+        @Override public String toString() { return label(_head); }
+        public int depth() {
             return _depth==0 ? (_par==null ? 0 : (_depth = _par.depth()+1)) : _depth;
         }
     }
@@ -133,23 +198,29 @@ public abstract class CFGNode extends Node {
     // Tag all CFG Nodes with their containing LoopNode; LoopNodes themselves
     // also refer to *their* containing LoopNode, as well as have their depth.
     // Start contains the function bodies at depth 0; real loops add depth.
-    public void buildLoopTree(StartNode start, StopNode stop) {
-        // Unlink all linked calls.  This can remove RPC constants which
-        // shuffled the StartNode outputs so requires a while loop.
-        boolean done=false;
-        while(!done) {
-            done = true;
-            for( Node use : start._outputs )
-                if( use instanceof FunNode fun )
-                    for( Node c : fun._inputs )
-                        if( c instanceof CallNode call )
-                            { call.unlink_all(); done=false; }
+    public void buildLoopTree( Ary<FunNode> funs, StopNode stop) {
+        _ltree = stop._ltree = CodeGen.CODE.XCTRL._ltree = new LoopTree((StartNode)this);
+        Ary<FunNode> work = new Ary<>(FunNode.class);
+
+        BitSet post = new BitSet();
+        int pre = 1;
+        _pre = pre++;
+        for( FunNode fun : funs ) {
+            if( fun!=null && !fun.isDead() && !fun._type.isHigh() ) {
+                work.push(fun);
+                if(fun.in(1) instanceof StartCUNode start && start._pre==0 ) {
+                    start._pre = pre++;
+                    start._ltree = start.cfg(1)._ltree = _ltree;
+                    post.set(start._nid);
+                }
+            };
         }
 
-        _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this);
-        _bltWalk(2,null,stop, new BitSet());
+        for( int i=0; i<work._len; i++ )
+            pre = work.at(i)._bltWalk(pre,work.at(i),stop, post, work);
     }
-    int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) {
+
+    int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post, Ary<FunNode> work ) {
         // Pre-walked?
         if( _pre!=0 ) return pre;
         _pre = pre++;
@@ -163,8 +234,12 @@ public abstract class CFGNode extends Node {
         }
         // Pre-walk
         for( Node use : _outputs )
-            if( use instanceof CFGNode usecfg && !skip( usecfg ) )
-                pre = usecfg._bltWalk( pre, use instanceof FunNode fuse ? fuse : fun, stop, post );
+            if( use instanceof CFGNode usecfg ) {
+                if( skip( usecfg ) ) {
+                    if( usecfg._pre==0 && usecfg instanceof FunNode fun2 ) work.add( fun2 );
+                } else
+                    pre = usecfg._bltWalk( pre, use instanceof FunNode fuse ? fuse : fun, stop, post, work );
+            }
 
         // Post-order work: find innermost loop
         LoopTree inner = null, ltree;
@@ -207,7 +282,7 @@ public abstract class CFGNode extends Node {
         return pre;
     }
 
-    private boolean skip(CFGNode usecfg) {
+    public 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 ||
@@ -215,8 +290,13 @@ public abstract class CFGNode extends Node {
                 (this instanceof ReturnNode && usecfg instanceof CallEndNode);
     }
 
-
-    public String label( CFGNode target ) {
-        return (target instanceof LoopNode ? "LOOP" : "L")+target._nid;
+    public static String label( CFGNode target ) {
+        return switch(target) {
+        case StartNode start -> start.label();
+        case FunNode fun -> fun.label();
+        case LoopNode loop -> "LOOP"+target._nid;
+        default -> "L"+target._nid;
+        };
     }
+
 }