From d32f97238c903765dec4e9a9f3cbfa5fd12cded6 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 10 Aug 2026 11:11:18 -0700 Subject: Chapter 25: Modules, Separate Compilation, and SSA Construction 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 Co-authored-by: Claude Opus 5 --- .../java/com/seaofnodes/simple/node/ScopeNode.java | 471 ++++++++++++++------- 1 file changed, 322 insertions(+), 149 deletions(-) (limited to 'src/main/java/com/seaofnodes/simple/node/ScopeNode.java') diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 307fc0f9..92cad745 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -5,18 +5,18 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Var; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.ParseAll; +import com.seaofnodes.simple.codegen.CompUnit; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; -import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.Utils; - import java.util.*; /** * The Scope node is purely a parser helper - it tracks names to nodes with a - * stack of variable records. + * stack of variables. */ -public class ScopeNode extends Node { +public class ScopeNode extends MemMergeNode { /** * The control is a name that binds to the currently active control @@ -26,40 +26,38 @@ public class ScopeNode extends Node { public static final String ARG0 = "arg"; public static final String MEM0 = "$mem"; - public Node in(Var v) { return in(v._idx); } - - @Override public Type compute() { return Type.BOTTOM; } - @Override public Node idealize() { return null; } - - // All active/live variables in all nested scopes, all run together + // All active/live variables in all nested scopes, all run together. + // Maps 1-to-1 to the _inputs array. public final Ary _vars; // Lexical scope is typed: public static class Kind { // Basic block scoping - public static class Block extends Kind { } + public static class Block extends Kind { } + // Constructor/initializer block for an allocated struct. + public static class Constructor extends Block { + public Constructor(TypeStruct self) { _self = self; } + public final TypeStruct _self; + } // Function scope - public static class Func extends Kind { } - // Struct definition, mapping types to fields - public static class Define extends Kind { public Define(TypeMemPtr tmp) { _tmp=tmp; } public final TypeMemPtr _tmp; } - // Struct allocation, mapping values to fields - public static class Alloc extends Kind { public Alloc (TypeMemPtr tmp) { _tmp=tmp; } public final TypeMemPtr _tmp; } + public static class Func extends Kind { public Func(String name) { _name=name;} public final String _name; } public int _lexSize; // Number of Vars in this scope } public final Ary _kinds; // Lexical scope nesting depth public int depth() { return _kinds._len; } + public Kind klast() { return _kinds.last(); } - // Extra guards; tested predicates and casted results + // Extra guards; tested predicates and cast results private final Ary _guards; // A new ScopeNode public ScopeNode() { - _type = Type.BOTTOM; - _vars = new Ary<>(Var .class); - _kinds = new Ary<>(Kind .class); - _guards = new Ary<>(Node .class); + super(); + _vars = new Ary<>(Var .class); + _kinds = new Ary<>(Kind.class); + _guards = new Ary<>(Node.class); } @Override public String label() { return "Scope"; } @@ -70,7 +68,7 @@ public class ScopeNode extends Node { int j=1; for( int i=0; i N ctrl(N n) { return setDef(0,n); } - public Node mem(Node n) { update(MEM0,n); return n; } + public Node mem(Node n) { return setDef(1,n); } public void push( Kind kind ) { kind._lexSize = _vars.size(); @@ -112,7 +110,11 @@ public class ScopeNode extends Node { // Pop a lexical scope public void pop() { - promote(); // Promote forward references to the next outer scope + promote(null); // Promote forward references to the next outer scope + _pop(); + } + // Pop a scope, no promote FRefs + public void _pop() { int n = _kinds.pop()._lexSize; popUntil(n); // Pop off inputs going out of scope _vars.setLen(n); // Pop off variables going out of scope @@ -121,68 +123,85 @@ public class ScopeNode extends Node { // Look for forward references in the last lexical scope and promote to the // next outer lexical scope. At the last scope declare them an error. - public void promote() { - Kind kind = _kinds.last(); + public void promote(CodeGen code) { + Kind kind = klast(); int n = kind._lexSize; for( int i=n; i0; i-- ) - if( _kinds.at(i) instanceof Kind.Alloc ) - return v._idx >= _kinds.at(i-1)._lexSize && v._idx < _kinds.at(i)._lexSize; - return false; + public boolean inFunction () { return klast() instanceof Kind.Func; } + // Is any enclosing scope a constructor? + public boolean inConstructor() { return constructorSelf() != null; } + // Nearest constructor self type, if any. + public TypeStruct constructorSelf() { + for( int i=depth()-1; i>=0; i-- ) + if( _kinds.at(i) instanceof Kind.Constructor ctor ) + return ctor._self; + else if( _kinds.at(i) instanceof Kind.Func func && FunNode.isInstance(func._name) ) + return ((TypeMemPtr)var(_kinds.at(i)._lexSize).type())._obj; + return null; } - public boolean inConstructor() { return _kinds.last() instanceof Kind.Define; } - public boolean inAllocation () { return _kinds.last() instanceof Kind.Alloc ; } - public boolean inFunction () { return _kinds.last() instanceof Kind.Func ; } - - public Kind kind( Var v ) { + // Find nearest enclosing function scope + public int enclosingFunction() { for( int i=depth()-1; i>=0; i-- ) - if( v._idx >= _kinds.at(i)._lexSize ) - return _kinds.at(i); - throw Utils.TODO(); + if( _kinds.at(i) instanceof Kind.Func func && !FunNode.isInstance(func._name) ) + return i; + throw Utils.TODO("Should not reach here"); } - // Return the kind for the defining scope, or a function scope if found - // first. Block scopes means the variable can be r/w directly in the - // scope, Function scopes require final constants (no capture), and - // Constructor scopes mean an instance variable reference. - - // Walk up-lexical scope looking for defining lexical Kind. - // - Skip any amount of nested block scopes - // - Walking out of a function requires v be a final constant (for now) - - // and we can stop walking. - - // - Walking out of a method and (skipping Blocks) into the matching struct - // is OK, and this is a instance var load. + // Find nearest enclosing function or declaration scope + public int enclosingFuncOrDecl() { + for( int i=depth()-1; i>=0; i-- ) + if( _kinds.at(i) instanceof Kind.Func func ) + return i; + throw Utils.TODO("Should not reach here"); + } - // - Walking out of a method and into the wrong struct is an error; - // including nested structs containing (no nested classes yet) + // Which lexical scope contains this Var? + public int kindx( Var v ) { + for( int i=depth()-1; i>=0; i-- ) + if( v._idx >= _kinds.at(i)._lexSize ) + return i; + return -1; + } - // Returns error, forward-ref, ok containing struct, ok containing function/block. + // Which lexical scope contains this Var? + public Kind kind( Var v ) { + int kx = kindx(v); + return kx == -1 ? null : _kinds.at(kx); + } - public String outOfFunction( Var v ) { - //if( v==null ) return null; // Prolly forward reference - //int i; for( i=_lexSize._len-1; i>=0 && v._idx<_lexSize.at(i); i-- ) - // if( _kinds.at(i)=="{->}" ) return "{->}"; - //return _kinds.at(i); - throw Utils.TODO(); + public int kindFcnx( Var v ) { + for( int i=depth()-1; i>=0; i-- ) + if( v._idx >= _kinds.at(i)._lexSize && _kinds.at(i) instanceof Kind.Func ) + return i; + throw Utils.TODO("Should not reach here"); } + // Which function scope contains this Var? + public Kind kindFcn( Var v ) { + int kx = kindFcnx(v); + return kx == -1 ? null : _kinds.at(kx); + } // Find name in reverse, return an index into _vars or -1. Linear scan // instead of hashtable, but probably doesn't matter until the scan @@ -198,9 +217,9 @@ public class ScopeNode extends Node { * Create a new variable name in the current scope */ public boolean define( String name, Type declaredType, boolean xfinal, Node init, Parser.Lexer loc ) { - assert _kinds.isEmpty() || name.charAt(0)!='$' ; // Later scopes do not define memory + assert _kinds.isEmpty() || name!=MEM0 ; // Later scopes do not define memory if( depth() > 0 ) - for( int i=_vars.size()-1; i>=_kinds.last()._lexSize; i-- ) { + for( int i=_vars.size()-1; i>=klast()._lexSize; i-- ) { Var n = var(i); if( n._name.equals(name) ) { if( !n.isFRef() ) return false; // Double define @@ -208,17 +227,45 @@ public class ScopeNode extends Node { if( !xfinal || !declaredType.isConstant() ) throw fref.err(); // Must be a final constant n.defFRef(declaredType,xfinal,loc); // Declare full correct type, final, source location setDef(n._idx,fref.addDef(init)); // Set FRef to defined; tell parser also + return true; } } - Var v = new Var(nIns(),name,declaredType,xfinal,loc,init==Parser.XCTRL); + Var v = new Var(nIns(),name,declaredType,xfinal,loc,init==CodeGen.CODE.XCTRL); _vars.add(v); // Creating a forward reference - if( init==Parser.XCTRL ) - init = new FRefNode(v).init(); + if( init==CodeGen.CODE.XCTRL ) + //init = new FRefNode(v).init(); + throw Utils.TODO(); addDef(init); return true; } + // Normal lookup was tried and failed. Append a forward ref in the current + // lexical scope. Scope pops promote it outwards "as if" the final constant + // had been declared before the using scope. + + public Var defineFRef( String id, Type t, boolean xfinal, Parser.Lexer loc ) { + Var var = new Var(nIns(),id,t,xfinal,loc,true); + FRefNode fref = new FRefNode(id,loc).init(); + fref._type = fref._con = t; + _vars.add(var); + addDef(fref); + return var; + } + + + // Parser state carries one complete, conservative memory value. Precise + // alias partitions belong to the graph and are introduced by peepholes. + public Node mem( int alias ) { + assert alias == 1; + return in(update(var(1),null)); + } + public void mem( int alias, Node st ) { + assert alias == 1; + update(var(1),st); + } + + /** * Lookup a name in all scopes starting from most deeply nested. * @@ -254,7 +301,7 @@ public class ScopeNode extends Node { // Set real Phi in the loop head // The phi takes its one input (no backedge yet) from a recursive // lookup, which might have insert a Phi in every loop nest. - : loop.setDef(v._idx,PhiNode.make(v._name, v.type(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).peephole()); + : loop.setDef(v._idx,PhiNode.make(v._name, v.type(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).init()); setDef(v._idx,old); } //assert !v._final || st==null; @@ -292,9 +339,15 @@ public class ScopeNode extends Node { n.keep(); dup.addDef(ctrl()); // Control input is just copied - // Memory is one binding, with the same lazy loop Phi as scalar names. - for( int i=1; i