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, 126 insertions, 56 deletions

diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index b3204cff..a557f97c 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -2,9 +2,11 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.print.ExprPrinter;
 
-import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.codegen.GlobalBits;
 import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.util.BAOS;
 import com.seaofnodes.simple.util.Utils;
 import java.util.BitSet;
 
@@ -22,9 +24,14 @@ public class LoadNode extends MemOpNode {
      * @param ptr   The ptr to the struct base from where we load a field
      * @param off   The offset inside the struct base
      */
-    public LoadNode(Parser.Lexer loc, String name, int alias, Type glb, Node mem, Node ptr, Node off) {
-        super(loc, name, alias, true, glb, mem, ptr, off);
+    public LoadNode(Parser.Lexer loc, String name, int alias, Node ctrl, Node mem, Node ptr, Node off) {
+        super(loc, name, alias, true, Type.BOTTOM, ctrl, mem, ptr, off);
     }
+    LoadNode( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) {
+        super(bais,strs,types,fileAliases,aliases,true);
+        _con = Type.BOTTOM;      // Serialized slot retained while MemOps share TypeNode
+    }
+    @Override public Tag serialTag() { return Tag.Load; }
 
     @Override boolean canDrop(MemOpNode other, Node dep) {
         return super.canDrop(other,dep) && !clobbered(dep);
@@ -40,7 +47,7 @@ public class LoadNode extends MemOpNode {
             dep.addDepForwards(use);
             if( use instanceof StoreNode || use instanceof PhiNode ||
                 use instanceof MemMergeNode ||
-                use instanceof NewNode || use instanceof CallNode ) return true;
+                use instanceof NewNode || use instanceof EscapeNode || use instanceof CallNode ) return true;
         }
         return false;
     }
@@ -52,58 +59,102 @@ public class LoadNode extends MemOpNode {
 
     @Override
     public Type compute() {
-        Type tmem = mem()._type;
-        if( !(tmem instanceof TypeMem mem) )
-            return tmem; // No memory yet?  Assume TOP/BOT
-        assert !_declaredType.isFRef();
-        // No lifting if ptr might null-check
-        Type tptr = ptr()._type;
-        if( err() != null )
-            return _declaredType;
-        if( !(tptr instanceof TypeMemPtr tmp) )
-            return tptr; // No pointer yet?  Assume TOP/BOT
+        Type mem0 = mem()._type;
+        Type ptr0 = ptr()._type;
+        // Validate argument types
+        if( ptr0.isHigh() )
+            return TypeScalar.TOP;
+        if( !(mem0 instanceof TypeMem mem) )
+            return mem0.isHigh() ? TypeScalar.TOP : TypeScalar.BOT;
+        if( mem._t == Type.TOP )
+            return TypeScalar.TOP;
+        if( ptr0 == Type.NIL )
+            return Type.BOTTOM; // Load from nil is error
+        if( ptr0 == Type.BOTTOM )
+            return Type.BOTTOM; // Error in is error out
+        if( !(ptr0 instanceof TypeMemPtr tmp) )
+            return scalar(mem._t);
+        if( tmp.nullable() )
+            return Type.BOTTOM; // Load from nil-able is error
+
         // Load field from object
-        Field f = tmp._obj.field(_name);
+        Field pfld = tmp._obj.field(_name);
         // No field?  Open objects might yet get the field when falling;
         // closed objects with missing field are an error.
-        if( f == null )
-            return tmp.isHigh() ? Type.TOP : _declaredType;
-        Type t = f._t;
+        if( pfld == null )
+            return tmp.isHigh() || tmp._obj.isHigh() ? TypeScalar.TOP : TypeScalar.BOT;
+
+        Type t = pfld._t;
+        boolean readonly = t instanceof TypeMemPtr view && view._ro;
         // Load member of constant array
         if( t instanceof TypeConAry ary )
             t = ary.elem();     // TODO: if offset is known, can peek the constant
-        // Lift from declared type and memory input
-        t = t.join(MemMergeNode.contents(mem(),_alias,this));
-        if( ptr()._type.isFinal() || _declaredType.isFinal() )
-            t = t.makeRO(); // Deep final applied
-        // Pinch between declared type
-        t = t.join(_declaredType);
-        return t;
+        if( mem._alias==_alias )
+            t = t.join(mem._t);
+
+        // A deeply read-only base produces a deeply read-only value.  The
+        // generic declared field type must not cast this information away.
+        if( ptr0.isFinal() || readonly )
+            t = t.makeRO();
+        return scalar(t);
+    }
+
+    // Loads produce ordinary scalar values.  Field/memory joins can still
+    // expose the enclosing global lattice bounds through an uninitialized
+    // Type.TOP/BOTTOM field; keep those results inside the scalar envelope.
+    private static Type scalar(Type t) {
+        return t==Type.TOP ? TypeScalar.TOP : t==Type.BOTTOM ? TypeScalar.BOT : t;
     }
 
     @Override
     public Node idealize() {
-        if( mem() instanceof CastNode cast ) {
-            setDef(1,cast.in(1));
+        Node mem = mem();
+        Node ptr = ptr();
+
+        // Null checks are handled by types. Array elements retain control for
+        // range checks, but reading an array's length has no index to check.
+        if( in(0)!=null && ptr._type instanceof TypeMemPtr tmp &&
+            (!tmp._obj.isAry() || _name.equals("#")) ) {
+            setDef(0,null);
             return this;
         }
-        if( mem() instanceof MemMergeNode merge ) {
-            setDef(1,CodeGen.CODE.add(merge.alias(_alias)));
+
+        // Forward-ref loads eventually sharpen to a declared type
+        Field fld;
+        if( ptr._type instanceof TypeMemPtr tmp &&
+            (fld=tmp._obj.field(_name)) != null &&
+            _alias != fld._alias) {
+            assert _alias==1 || _alias == fld._alias;
+            assert !tmp._obj._open && !tmp._obj._fref;
+            unlock();           // Alias participates in GVN semantics
+            _alias = fld._alias;
             return this;
         }
-        Node ptr = ptr();
-        Node mem = mem();
+        // Must sharpen alias first
+        if( _alias == 1 )
+            return null;
 
-        Node win = find(mem,ptr,null,null);
-        if( win!=null ) return folded(win);
+        if( mem instanceof MemMergeNode merge ) {
+            setDef(1,merge.alias(_alias));
+            // In support of uplifting control to a prior dominating load, if
+            // we move our memory, recheck other loads to see if they can hoist.
+            for( Node use : in(1).outs() )
+                if( use instanceof LoadNode ld && use != this && ptr == ld.ptr() )
+                    CodeGen.CODE.add(ld);
+
+            return this;
+        }
 
         // Uplift control to a prior dominating load.
         for( Node memuse : mem._outputs )
             // Find a prior load, has same mem,ptr,off but higher ctrl
             if( memuse != this && memuse instanceof LoadNode ld && ptr==ld.ptr() && off()==ld.off() &&
-                cfg0()!=null && cfg0().domLCA(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier
+                cfg0()!=null && cfg0().domLCA(ld.cfg0(),this) == ld.cfg0() && // Higher control means load is legal earlier
+                addDep(ld)._type.isa(_type) ) // and not rolling backwards
                 return ld;
 
+        Node win = find(mem,ptr,null,null);
+        if( win!=null ) return folded(win);
         if( ptr instanceof ReadOnlyNode ro ) ptr=ro.in(1);
 
         // Push a Load up through a Phi, as long as it collapses on at least
@@ -127,13 +178,17 @@ public class LoadNode extends MemOpNode {
                 !(ptr instanceof PhiNode p && p.region()==memphi.region()) ? memphi : null;
             if( find(memphi.in(2),ptr,stop,new BitSet())!=null ||
                 (!(memphi.region() instanceof LoopNode) && find(memphi.in(1),ptr,null,new BitSet())!=null) ) {
-                PhiNode phi = new PhiNode(_name,_declaredType,memphi.region()).keep();
-                phi.setType(_type); // Backedge searches may return this value Phi.
+                // Integer loop Phis widen to i64. Keep the load's declared
+                // width at the result, as for ordinary typed loop variables.
+                if( _type instanceof TypeInteger && !declaredType().isa(_type) ) return null;
+                PhiNode phi = new PhiNode(_name,memphi.region()).keep();
+                phi.setType(_type instanceof TypeInteger ? TypeInteger.BOT : _type);
                 for( int i=1; i<memphi.nIns(); i++ ) {
                     Node p = ptr instanceof PhiNode pp && pp.region()==memphi.region() ? pp.in(i) : ptr;
                     phi.addDef(load(memphi.in(i),p,stop,phi));
                 }
-                return CodeGen.CODE.add(phi.unkeep());
+                CodeGen.CODE.add(phi.unkeep());
+                return _type instanceof TypeInteger ? new ConvertNode(declaredType(),phi) : phi;
             }
         }
 
@@ -142,8 +197,7 @@ public class LoadNode extends MemOpNode {
 
     // Load a flavored zero from a New
     private Node zero(NewNode nnn) {
-        TypeStruct ts = nnn._ptr._obj;
-        Type zero = ts._fields[ts.findAlias(_alias)]._t.makeZero();
+        Type zero = declaredType().makeZero();
         assert zero.isa(_type); // Catch an uninitialized non-null field
         return castRO(new ConstantNode(zero).peephole());
     }
@@ -153,25 +207,39 @@ public class LoadNode extends MemOpNode {
     // Register dependencies so a later pointer/offset rewrite retries the query.
     private Node find(Node mem, Node ptr, Node stop, BitSet visit) {
         if( ptr instanceof ReadOnlyNode ro ) ptr=ro.in(1);
+        Field fld;
+        boolean external = ptr._type instanceof TypeMemPtr tmp &&
+            (fld=tmp._obj.field(_name))!=null && fld._extern;
         while( mem!=null ) {
             addDep(mem);
             if( mem==stop ) return mem;
             switch( mem ) {
             case MemMergeNode merge: mem=merge.alias(_alias); break;
-            case CastNode cast: mem=cast.in(1); break;
             case StoreNode st:
+                // Alias 1 is still unresolved, not a proven different field.
+                if( st._alias==1 ) return null;
                 addDep(st.ptr());
-                if( _alias==st._alias && ptr==st.ptr() && off()==st.off() ) return st;
-                if( _alias==st._alias && !neverAlias(ptr,st.ptr()) &&
+                if( _alias==st._alias && (ptr==st.ptr() || ptr==st.nnptr()) && off()==st.off() ) {
+                    // A full-width load cannot narrow the forwarded value.
+                    if( declaredType() instanceof TypeInteger ti && ti.log_size()==3 &&
+                        !addDep(st.val())._type.isa(_type) ) return null;
+                    return st;
+                }
+                if( (external || _alias==st._alias) && (external || !neverAlias(ptr,st.ptr())) &&
                     !addDep(off())._type.join(addDep(st.off())._type).isHigh() ) return null;
                 mem=st.mem();
                 break;
             case ProjNode proj:
-                if( !(proj.in(0) instanceof NewNode nnn) ) return null;
-                if( ptr instanceof ProjNode p && p.in(0)==nnn ) return nnn;
-                if( !(ptr instanceof ProjNode p && p.in(0) instanceof NewNode) ) return null;
-                mem=nnn.mem(); // Distinct allocations cannot overlap.
-                break;
+                // New's memory is private; public memory is joined at Escape.
+                if( external || !(proj.in(0) instanceof NewNode nnn) ) return null;
+                if( declaredType()==Type.BOTTOM ) return null;
+                return nnn;
+            case EscapeNode esc:
+                if( external ) return null;
+                addDep(esc.self());
+                if( esc.self()==ptr ) { mem=esc.priv(); break; }
+                if( neverAlias(ptr,esc.self()) ) { mem=esc.pub(); break; }
+                return null;
             case MemPhiNode phi:
                 addDep(phi.region());
                 // Only the original loop closes a successful cycle. Another
@@ -200,14 +268,14 @@ public class LoadNode extends MemOpNode {
         if( win!=null ) {
             if( win==stop ) return value;
             if( win instanceof MemPhiNode mp ) {
-                PhiNode phi=new PhiNode(_name,_declaredType,mp.region()).keep();
+                PhiNode phi=new PhiNode(_name,mp.region()).keep();
                 for( int i=1; i<mp.nIns(); i++ ) phi.addDef(load(mp.in(i),ptr,stop,value));
-                return phi.unkeep().peephole();
+                return CodeGen.CODE.add(phi.unkeep().peephole());
             }
-            return folded(win).peephole();
+            Node fold=folded(win);
+            if( fold!=null ) return fold.peephole();
         }
-        LoadNode ld=new LoadNode(_loc,_name,_alias,_declaredType,mem,ptr,off());
-        ld.setDef(0,in(0));
+        LoadNode ld=new LoadNode(_loc,_name,_alias,in(0),mem,ptr,off());
         return ld.peephole();
     }
 
@@ -239,7 +307,7 @@ public class LoadNode extends MemOpNode {
 
     // Read-Only is a deep property, and cannot be cast-away
     private Node castRO(Node rez) {
-        if( (ptr()._type.isFinal() || _declaredType.isFinal()) && !rez._type.isFinal() )
+        if( (ptr()._type.isFinal() || declaredType().isFinal()) && !rez._type.isFinal() )
             return new ReadOnlyNode(rez).peephole();
         return rez;
     }
@@ -247,16 +315,18 @@ public class LoadNode extends MemOpNode {
     // When a load bypasses a store, the store might truncate bits - and the
     // load will need to zero/sign-extend.
     private Node extend(Node val) {
-        if( !(_declaredType instanceof TypeInteger ti) ) return val;
+        if( !(declaredType() instanceof TypeInteger ti) ) return val;
         if( ti._min==0 )        // Unsigned
             return new AndNode(null,val,con(ti._max));
         // Signed extension
         int shift = Long.numberOfLeadingZeros(ti._max)-1;
         Node shf = con(shift);
-        if( shf._type==TypeInteger.ZERO )
+        if( shift==0 ) {
+            if( !val._type.isa(_type) )
+                { addDep(val); return null; }
             return val;
+        }
         Node shl = new ShlNode(null,val,shf.keep()).peephole();
         return new SarNode(null,shl,shf.unkeep());
     }
-
 }