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, 137 insertions, 58 deletions

diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 414530b4..23a7e2c4 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -4,13 +4,11 @@ import com.seaofnodes.print.BaseNode;
 
 import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.Parser;
-import com.seaofnodes.simple.util.Ary;
-import com.seaofnodes.simple.util.Utils;
 import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.codegen.GlobalBits;
 import com.seaofnodes.simple.print.IRPrinter;
-import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeFloat;
-import com.seaofnodes.simple.type.TypeInteger;
+import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.util.*;
 import java.util.*;
 import java.util.function.Function;
 import static com.seaofnodes.simple.codegen.CodeGen.CODE;
@@ -70,8 +68,83 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
         _hash = 0;
     }
 
+    // Disk/serialized opcode tags
+    public enum Tag {
+        Add,And,EQ,NE,LT,LE,ULT,
+        CallEnd,Call,ConFldOff,Con,CProj,
+        Div,Escape,Extern,Fun,FunPtr,If,Load,Loop,
+        MemMerge,Minus,Mul,
+        New,Never,Not,Or,Parm,Phi,Proj,
+        ReadOnly,Return,Region,RoundF32,
+        Sar,Shl,Shr,Start,Stop,Store,Sub,ToFloat,
+        XCtrl,Xor,StartCU,StopCU,Guard,MemPhi,BulkMemPhi,PtrToInt,ExternOffset,ToInteger;
+        public static final Tag[] VALS = values();
+        public Node make( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) {
+            return switch(this) {
+            case Add    -> new   AddNode(null,null,(byte)bais.packed1());
+            case And    -> { int mode=bais.packed1(); assert mode==1; yield new AndNode(null,null,null); }
+            case Div    -> new   DivNode(null,null,(byte)bais.packed1());
+            case If     -> new    IfNode(null,null);
+            case Loop   -> new  LoopNode(null,null,null);
+            case Minus  -> new MinusNode(null,(byte)bais.packed1());
+            case Mul    -> new   MulNode(null,null,(byte)bais.packed1());
+            case Never  -> new NeverNode(1.2f, null);
+            case Not    -> new   NotNode(null);
+            case Or     -> { int mode=bais.packed1(); assert mode==1; yield new OrNode(null,null,null); }
+            case ReadOnly-> new ReadOnlyNode((Node)null);
+            case Return ->new ReturnNode(null,null,null,null,null);
+            case RoundF32-> new RoundF32Node(null);
+            case PtrToInt-> new PtrToIntNode((Node)null);
+            case Sar    -> { int mode=bais.packed1(); assert mode==1; yield new SarNode(null,null,null); }
+            case Shl    -> { int mode=bais.packed1(); assert mode==1; yield new ShlNode(null,null,null); }
+            case Shr    -> { int mode=bais.packed1(); assert mode==1; yield new ShrNode(null,null,null); }
+            case Start  -> new StartNode(null,null,TypeInteger.BOT);
+            case Sub    -> new   SubNode(null,null,(byte)bais.packed1());
+            case ToFloat-> new ToFloatNode(null);
+            case ToInteger-> new ToIntegerNode(null);
+            case XCtrl  -> new XCtrlNode();
+            case Xor    -> { int mode=bais.packed1(); assert mode==1; yield new XorNode(null,null,null); }
+            case Guard -> GuardNode.make(bais);
+
+            case EQ    -> new  BoolNode.EQ (null,null,(byte)bais.packed1());
+            case NE    -> new  BoolNode.NE (null,null,(byte)bais.packed1());
+            case LT    -> new  BoolNode.LT (null,null,(byte)bais.packed1());
+            case LE    -> new  BoolNode.LE (null,null,(byte)bais.packed1());
+            case ULT   -> new  BoolNode.ULT(null,null,(byte)bais.packed1());
+
+            case Call  ->      CallNode.make(bais);
+            case CallEnd->  CallEndNode.make(bais     ,types);
+            case CProj ->     CProjNode.make(bais,strs);
+            case Con   ->  ConstantNode.make(bais     ,types);
+            case Escape->    EscapeNode.make(bais     ,types);
+            case Extern->    ExternNode.make(bais,strs,types);
+            case ExternOffset-> new ExternOffsetNode(strs[bais.packed2()]);
+            case FunPtr->   FunPtrNode.make(bais,     types);
+            case Fun   ->       FunNode.make(bais,strs,types);
+            case Load  ->       new LoadNode(bais,strs,types,fileAliases,aliases);
+            case MemMerge->MemMergeNode.make(bais);
+            case MemPhi->  MemPhiNode.make(bais,strs,types,fileAliases,aliases);
+            case BulkMemPhi-> BulkMemPhiNode.make(bais,strs,types,fileAliases,aliases);
+            case New   ->       NewNode.make(bais     ,types);
+            case Parm  ->      ParmNode.make(bais,strs,types);
+            case Phi   ->       PhiNode.make(bais,strs,types);
+            case Proj  ->      ProjNode.make(bais,strs);
+            case Store ->      new StoreNode(bais,strs,types,fileAliases,aliases);
+            case Stop ->       StopNode.make(bais);
+            case StartCU->  StartCUNode.make(bais,strs,types);
+            case StopCU ->   StopCUNode.make(bais);
+            case Region->    RegionNode.make(bais);
+
+            default -> throw Utils.TODO("Should not reach here");
+            };
+        }
+    };
+    public Tag serialTag() { throw Utils.TODO(); }
+    // Serialize extra data, including input counts
+    public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) {}
+
     // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ"
-    public abstract String label();
+    public String label() { return serialTag().toString(); }
 
     public String p(int depth) { return IRPrinter.prettyPrint(this,depth); }
 
@@ -178,7 +251,8 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
     }
 
     // Breaks the edge invariants, used temporarily
-    protected <N extends Node> void addUse(N n) { _outputs.add(n); }
+    @SuppressWarnings("unchecked")
+    protected <N extends Node> N addUse(Node n) { _outputs.add(n); return (N)this; }
 
     // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place.
     // Return true if the output list is empty afterward.
@@ -200,6 +274,12 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
                 old_def.kill();        // Kill old def
         }
     }
+    public Node removeLast() {
+        Node old_def = _inputs.pop();
+        if( old_def != null )
+            old_def.delUse(this);
+        return old_def;
+    }
 
     /**
      * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em>
@@ -236,11 +316,13 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
 
     // Shortcuts to stop DCE mid-parse
     // Add bogus null use to keep node alive
-    @SuppressWarnings("unchecked")
-    public <N extends Node> N keep() { addUse(null); return (N)this; }
+    public <N extends Node> N keep() { return addUse(null); }
     // Remove bogus null.
     @SuppressWarnings("unchecked")
-    public <N extends Node> N unkeep() { delUse(null); return (N)this; }
+    public <N extends Node> N unkeep() {
+        delUse(null);
+        return (N)this;
+    }
     // Test "keep" status
     public boolean iskeep() { return _outputs.find(null) != -1; }
     public void unkill() {
@@ -260,7 +342,6 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
             n.unlock();
             int idx = n._inputs.find(this);
             n._inputs.set(idx,nnn);
-            n.moveDepsToWorklist(); // Rewiring can change a dependent query without changing type.
             nnn.addUse(n);
             CODE.add(n);
             CODE.addAll(n._outputs);
@@ -331,13 +412,13 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
      * Try to peephole at this node and return a better replacement Node.
      * Always returns some not-null Node (often this).
      */
-    public final Node peephole() {
-        var obs = CodeGen.CODE._midAssert ? null : CodeGen.CODE._obs;
+    public final Node peephole( ) {
+        var obs = CODE._midAssert ? null : CODE._obs;
         if( obs != null ) obs.before(this);
         Node n = peepholeOpt();
-        Node rez = n == null ? this : deadCodeElim(n._nid >= _nid ? n.peephole() : n);
-        if( obs != null ) obs.after(this, n == null ? null : rez, false);
-        return rez;
+        Node rez = n==null ? this : deadCodeElim(n._nid >= _nid ? n.peephole() : n);
+        if( obs != null ) obs.after(this, n==null ? null : rez, false);
+        return rez;             // Cannot return null for no-progress
     }
 
     /**
@@ -363,11 +444,9 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
         // Compute initial or improved Type
         Type old = setType(compute());
 
-        // Replace constant computations from non-constants with a constant
-        // node.  If peeps are disabled, still allow high Phis to collapse;
-        // they typically come from dead Regions, and we want the Region to
-        // collapse, which requires the Phis to die first.
-        if( !isConst() && _type.isHighOrConst() )
+        // Replace constant computations from non-constants with a constant node.
+        if( !isConst() && !(this instanceof ParmNode parm && parm.inProgress()) &&
+            _type.isHighOrConst() )
             return ConstantNode.make(_type).peephole();
 
         // Global Value Numbering
@@ -435,7 +514,8 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
     // If changing, add users to worklist.
     public Type setType(Type type) {
         Type old = _type;
-        assert old == null || type.isa(old) : "Monotonicity test failed";
+        assert old == null || type.isa(old) : "Monotonicity test failed: "+this+"#"+_nid+" old="+old+" new="+type;
+        //assert !type.hasClosedBuilder0(); // New types should not have closed builders
         if( old == type ) return old;
         _type = type;       // Set _type late for easier assert debugging
         CODE.addAll(_outputs);
@@ -500,28 +580,33 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
     // revisit them if `this` changes.
     Ary<Node> _deps;
     public int nDeps() { return _deps == null ? 0 : _deps.size(); }
-    public Node dep(int idx) { return _deps.get(idx); }
+    public Node dep(int idx) { return _deps.at(idx); }
+
+    private boolean addDepImpl( Node dep ) {
+        // Running peepholes during the big assert cannot have side effects
+        // like adding dependencies.
+        if( CODE._midAssert ) return false;
+        if( CODE._obs != null ) CODE._obs.dep(this, dep);
+        if( dep._deps==null ) dep._deps = new Ary<>(Node.class);
+        if( dep._deps   .find(this) != -1 ) return false; // Already on list
+        if( dep._outputs.find(this) != -1 ) return false;
+        return true;
+    }
 
     /**
      * Add a node to the list of dependencies.  Only add it if it's not an input
      * or output of this node, that is, it is at least one step away.  The node
      * being added must benefit from this node being peepholed.
      */
-    <N extends Node> N addDep( N dep ) { return addDep(dep,false); }
-
-    // Keep an explicit dependency when inspecting an immediate user's shape.
-    <N extends Node> N addDepForwards(N dep) { return addDep(dep,true); }
+    public <N extends Node> N addDep( N dep ) {
+        if( !addDepImpl(dep) ) return dep;
+        if( dep._inputs .find(this) != -1 ) return dep; // No need for deps on immediate neighbors
+        dep._deps.add(this);
+        return dep;
+    }
 
-    private <N extends Node> N addDep(N dep, boolean forwards) {
-        // Running peepholes during the big assert cannot have side effects
-        // like adding dependencies.
-        if( CODE._midAssert ) return dep;
-        var obs = CodeGen.CODE._midAssert ? null : CodeGen.CODE._obs;
-        if( obs != null ) obs.dep(this, dep);
-        if( dep._deps==null ) dep._deps = new Ary<>(Node.class);
-        if( dep._deps   .find(this) != -1 ) return dep; // Already on list
-        if( !forwards && dep._inputs .find(this) != -1 ) return dep; // No need for deps on immediate neighbors
-        if( !forwards && dep._outputs.find(this) != -1 ) return dep;
+    public <N extends Node> N addDepForwards( N dep ) {
+        if( !addDepImpl(dep) ) return dep;
         dep._deps.add(this);
         return dep;
     }
@@ -585,26 +670,6 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
     /** Is this Node Memory related */
     public boolean isMem() { return false; }
 
-    // Semantic change to the graph (so NOT a peephole), used by the Parser.
-    // If any input is a float, flip to a float-flavored opcode and widen any
-    // non-float input.
-    public final Node widen() {
-        if( !hasFloatInput() ) return this;
-        Node flt = copyF();
-        if( flt==null ) return this;
-        for( int i=1; i<nIns(); i++ )
-            flt.setDef(i, in(i)._type instanceof TypeFloat ? in(i) : new ToFloatNode(in(i)).peephole());
-        kill();
-        return flt;
-    }
-    private boolean hasFloatInput() {
-        for( int i=1; i<nIns(); i++ )
-            if( in(i)._type instanceof TypeFloat )
-                return true;
-        return false;
-    }
-    Node copyF() { return null; }
-
     // ------------------------------------------------------------------------
     // Peephole utilities
 
@@ -656,7 +721,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
     public Parser.ParseException err() { return null; }
 
     // Common integer constants
-    public static ConstantNode con(long x) { return (ConstantNode)(new ConstantNode(TypeInteger.constant(x)).peephole()); }
+    public static ConstantNode con(long x) { return (ConstantNode)ConstantNode.make(TypeInteger.constant(x)).peephole(); }
 
     // Utility to walk the entire graph applying a function; return the first
     // not-null result.
@@ -677,6 +742,20 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
         return null;
     }
 
+    public void gather(HashMap<String,Integer> strs ) { }
+
+    // If a Type upgrade happens, put on worklist
+    boolean _upgradeType( HashMap<String,Type> TYPES ) { return false; }
+    public final void upgradeType( HashMap<String,Type> TYPES ) {
+        Type old = _type;  _type = _type.upgradeType(TYPES);
+        boolean progress = _upgradeType(TYPES);
+        if( progress || old != _type ) {
+            CODE.add(this);
+            CODE.addAll(_outputs);
+            if( _deps!=null ) CODE.addAll(_deps);
+        }
+    }
+
     /**
      * Debugging utility to find a Node by index
      */