From b5b972aec72eeafe9e044704b3b6741a7362bb9b Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 5 Jan 2025 12:53:52 -0800 Subject: Finalize function semantics Rename ScopeMin to MergeMem. Move Var to its own file. Allow out-of-scope id lookups in functions, as long as its a final constant. This allows e.g. factorial to find "fact" as an out-of-scope final constant function. --- .../com/seaofnodes/simple/GlobalCodeMotion.java | 2 +- .../com/seaofnodes/simple/GraphVisualizer.java | 4 +- .../main/java/com/seaofnodes/simple/IRPrinter.java | 2 +- .../main/java/com/seaofnodes/simple/JSViewer.java | 9 +- .../main/java/com/seaofnodes/simple/Parser.java | 62 ++++--- .../src/main/java/com/seaofnodes/simple/Var.java | 51 ++++++ .../java/com/seaofnodes/simple/node/FRefNode.java | 30 ++-- .../com/seaofnodes/simple/node/MemMergeNode.java | 157 +++++++++++++++++ .../com/seaofnodes/simple/node/ScopeMinNode.java | 193 --------------------- .../java/com/seaofnodes/simple/node/ScopeNode.java | 48 +++-- .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- .../main/java/com/seaofnodes/simple/type/Type.java | 4 + .../com/seaofnodes/simple/type/TypeFunPtr.java | 8 + 13 files changed, 302 insertions(+), 270 deletions(-) create mode 100644 chapter18/src/main/java/com/seaofnodes/simple/Var.java create mode 100644 chapter18/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java delete mode 100644 chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java (limited to 'chapter18/src/main/java/com') diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 69434472..d3ee62c3 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -206,7 +206,7 @@ public abstract class GlobalCodeMotion { case NewNode st: break; case LoadNode ld: break; // Loads do not cause anti-deps on other loads case ReturnNode ret: break; // Load must already be ahead of Return - case ScopeMinNode ret: break; // Mem uses now on ScopeMin + case MemMergeNode ret: break; // Mem uses now on ScopeMin case NeverNode never: break; default: throw Utils.TODO(); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter18/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index bd778696..5d6d3328 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -81,7 +81,7 @@ public class GraphVisualizer { // Just the Nodes first, in a cluster no edges sb.append(doCtrl ? "\tsubgraph cluster_Controls {\n" : "\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name for (Node n : all) { - if (n instanceof ProjNode || n instanceof CProjNode || n instanceof ScopeMinNode || n==Parser.XCTRL) + if (n instanceof ProjNode || n instanceof CProjNode || n instanceof MemMergeNode || n==Parser.XCTRL) continue; // Do not emit, rolled into MultiNode or Scope cluster already if( _separateControlCluster && doCtrl && !(n instanceof CFGNode) ) continue; if( _separateControlCluster && !doCtrl && (n instanceof CFGNode) ) continue; @@ -163,7 +163,7 @@ public class GraphVisualizer { sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name // Special for memory ScopeMinNode if( level==0 ) { - ScopeMinNode n = scope.mem(); + MemMergeNode n = scope.mem(); sb.append("\t\t").append(n.uniqueName()).append(" [label=\"").append(n.glabel()).append("\"];\n"); } sb.append("\t\t").append(scopeName).append(" [label=<\n"); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java index 870a890b..aa498b16 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -18,7 +18,7 @@ public class IRPrinter { for( Node def : n._inputs ) sb.p(def==null ? "____" : "%4d".formatted(def._nid)) // Lazy Phi indicator - .p(n instanceof ScopeMinNode && def instanceof ScopeMinNode ? "^" : " "); + .p(n instanceof MemMergeNode && def instanceof MemMergeNode ? "^" : " "); for( int i = n._inputs.size(); i<4; i++ ) sb.p(" "); sb.p(" [[ "); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/JSViewer.java b/chapter18/src/main/java/com/seaofnodes/simple/JSViewer.java index 869448fa..adbe9f30 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/JSViewer.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/JSViewer.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import java.io.IOException; @@ -132,7 +131,7 @@ public class JSViewer implements AutoCloseable { // Just the Nodes first, in a cluster no edges sb.i().p("subgraph cluster_Nodes {\n").ii(); // Magic "cluster_" in the subgraph name for (Node n : all) { - if( n instanceof ProjNode || n instanceof CProjNode || n instanceof ScopeMinNode || n==Parser.XCTRL ) + if( n instanceof ProjNode || n instanceof CProjNode || n instanceof MemMergeNode || n==Parser.XCTRL ) continue; // Do not emit, rolled into MultiNode or Scope cluster already sb.i().p(n.uniqueName()).p(" [ "); if( n instanceof MultiNode ) { @@ -194,7 +193,7 @@ public class JSViewer implements AutoCloseable { sb.i().p("\n"); int lexStart=scope._lexSize.at(level); // Special for memory ScopeMinNode - ScopeMinNode n = scope.nIns()>1 ? scope.mem() : null; + MemMergeNode n = scope.nIns()>1 ? scope.mem() : null; if( level==0 && n!=null && n.nIns()>2 ) { sb.i().p(""); for( int m=2; m1 ) { - ScopeMinNode n = scope.mem(); + MemMergeNode n = scope.mem(); for( int i=2; i body }" - ReturnNode ret = parseFunctionBody(TypeFunPtr.MAIN,loc(),"arg"); + parseFunctionBody(TypeFunPtr.MAIN,loc(),"arg"); if( !_lexer.isEOF() ) throw _errorSyntax("unexpected"); @@ -205,10 +206,10 @@ public class Parser { // Pre-call the function from Start, with worse-case arguments. This // represents all the future, yet-to-be-parsed functions calls and // external calls. - _scope.push(); + _scope.push(ScopeNode.Kind.Function); ctrl(fun); // Scope control from function // Private mem alias tracking per function - ScopeMinNode mem = new ScopeMinNode(true); + MemMergeNode mem = new MemMergeNode(true); mem.addDef(null); // Alias#0 mem.addDef(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).peephole()); // All aliases _scope.mem(mem); @@ -261,9 +262,9 @@ public class Parser { * Does not parse the opening or closing '{}' * @return a {@link Node} or {@code null} */ - private Node parseBlock(boolean inCon) { + private Node parseBlock(ScopeNode.Kind kind) { // Enter a new scope - _scope.push(inCon); + _scope.push(kind); Node last = ZERO; while (!peek('}') && !_lexer.isEOF()) last = parseStatement(); @@ -295,7 +296,7 @@ public class Parser { // Break ambiguity around leading function types and starting a block else if (peek('{') && !isTypeFun() ) { match("{"); - return require(parseBlock(false),"}"); + return require(parseBlock(ScopeNode.Kind.Block),"}"); } // Declaration or normal assignment/expression else return parseDeclarationStatement(); @@ -331,7 +332,7 @@ public class Parser { // } // } require("("); - _scope.push(); // Scope for the index variables + _scope.push(ScopeNode.Kind.Block); // Scope for the index variables if( !match(";") ) // Can be empty init "for(;test;next) body" parseDeclarationStatement(); // Non-empty init Node rez = parseLooping(true); @@ -614,7 +615,7 @@ public class Parser { Node expr = parseAsgn(); // Final variable to update - ScopeMinNode.Var def = _scope.lookup(name); + Var def = _scope.lookup(name); if( def==null ) throw error("Undefined name '" + name + "'"); @@ -647,9 +648,7 @@ public class Parser { expr = zsMask(expr,t); // Type is sane if( !expr._type.isa(t) ) - throw expr instanceof FRefNode fref - ? fref.err() - : error("Type " + expr._type.str() + " is not of declared type " + t.str()); + throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); return expr; } @@ -720,10 +719,11 @@ public class Parser { // Lift expression, based on type Node lift = liftExpr(expr, t, xfinal); + if( xfinal && t instanceof TypeMemPtr tmp ) t = tmp.makeRO(); - // Define a new name, + // Define a new name if( !_scope.define(name,t,xfinal,lift, loc) ) throw error("Redefining name '" + name + "'", loc); return lift; @@ -746,7 +746,7 @@ public class Parser { throw error("struct '" + typeName + "' cannot be redefined"); // A Block scope parse, and inspect the scope afterward for fields. - _scope.push(true); + _scope.push(ScopeNode.Kind.Constructor); require("{"); while (!peek('}') && !_lexer.isEOF()) parseStatement(); @@ -758,7 +758,7 @@ public class Parser { Field[] fs = new Field[varlen-lexlen]; for( int i=lexlen; i - * Constants have no semantic inputs. However, we set Start as an input to - * Constants to enable a forward graph walk. This edge carries no semantic - * meaning, and it is present solely to allow visitation. - *

- * The Constant's value is the value stored in it. + * A Forward Reference. Its any final constant, including functions. When + * the Def finally appears its plugged into the forward reference, which then + * peepholes to the Def. */ public class FRefNode extends ConstantNode { - public final ScopeMinNode.Var _n; - public FRefNode(ScopeMinNode.Var n) { super(TypeFunPtr.BOT); _n = n; } + public static final Type FREF_TYPE = Type.TOP; + public final Var _n; + public FRefNode( Var n ) { super(FREF_TYPE); _n = n; } - @Override - public String label() { return "FRef"+_n; } + @Override public String label() { return "FRef"+_n; } - @Override - public String uniqueName() { return "FRef_" + _nid; } + @Override public String uniqueName() { return "FRef_" + _nid; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("FRef_").append(_n); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java new file mode 100644 index 00000000..61d99ed1 --- /dev/null +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -0,0 +1,157 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Var; +import com.seaofnodes.simple.type.*; +import java.util.*; +import static com.seaofnodes.simple.Utils.TODO; + +/** + * Memory Merge - a merge of many aliases into a "fat memory". All aliases + * are here, but most will be lazy - take the default fat memory. + */ +public class MemMergeNode extends Node { + + /* + * In-Progress means this is being used by the Parser to track memory + * aliases. No optimizations are allowed. When no longer "in progress" + * normal peeps work. + */ + public final boolean _inProgress; + + public MemMergeNode( boolean inProgress) { _type = TypeMem.BOT; _inProgress = inProgress; } + + + // If being used by a Scope, this is "in progress" from the Parser. + // Otherwise, it's a memory merge + boolean inProgress() { return _inProgress; } + + @Override public String label() { return "ALLMEM"; } + @Override public boolean isMem() { return true; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append(_inProgress ? "Merge[" : "MEM[ "); + for( int j=2; j= nIns() ) addDef(null); + return setDef(alias,st); + } + + // Read or update from memory. + // A shared implementation allows us to create lazy phis both during + // lookups and updates; the lazy phi creation is part of chapter 8. + Node _mem( int alias, Node st ) { + // Memory projections are made lazily; if one does not exist + // then it must be START.proj(1) + Node old = alias(alias); + if( old instanceof ScopeNode loop ) { + MemMergeNode loopmem = loop.mem(); + Node memdef = loopmem.alias(alias); + // Lazy phi! + old = memdef instanceof PhiNode phi && loop.ctrl()==phi.region() + // Loop already has a real Phi, use it + ? memdef + // 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. + : loopmem.alias(alias, new PhiNode(Parser.memName(alias), TypeMem.BOT,loop.ctrl(),loopmem._mem(alias,null),null).peephole() ); + alias(alias,old); + } + // Memory projections are made lazily; expand as needed + return st==null ? old : alias(alias,st); // Not lazy, so this is the answer + } + + + void _merge( MemMergeNode that, RegionNode r) { + int len = Math.max(nIns(),that.nIns()); + for( int i = 2; i < len; i++) + if( alias(i) != that.alias(i) ) { // No need for redundant Phis + // If we are in lazy phi mode we need to a lookup + // by name as it will trigger a phi creation + //Var v = _vars.at(i); + Node lhs = this._mem(i,null); + Node rhs = that._mem(i,null); + alias(i, new PhiNode(Parser.memName(i), lhs._type.glb().meet(rhs._type.glb()), r, lhs, rhs).peephole()); + } + } + + // Fill in the backedge of any inserted Phis + void _endLoopMem( ScopeNode scope, MemMergeNode back, MemMergeNode exit ) { + Node exit_def = exit.alias(1); + for( int i=1; i= nIns() ) addDef(null); - return setDef(alias,st); - } - - // Read or update from memory. - // A shared implementation allows us to create lazy phis both during - // lookups and updates; the lazy phi creation is part of chapter 8. - Node _mem( int alias, Node st ) { - // Memory projections are made lazily; if one does not exist - // then it must be START.proj(1) - Node old = alias(alias); - if( old instanceof ScopeNode loop ) { - ScopeMinNode loopmem = loop.mem(); - Node memdef = loopmem.alias(alias); - // Lazy phi! - old = memdef instanceof PhiNode phi && loop.ctrl()==phi.region() - // Loop already has a real Phi, use it - ? memdef - // 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. - : loopmem.alias(alias, new PhiNode(Parser.memName(alias), TypeMem.BOT,loop.ctrl(),loopmem._mem(alias,null),null).peephole() ); - alias(alias,old); - } - // Memory projections are made lazily; expand as needed - return st==null ? old : alias(alias,st); // Not lazy, so this is the answer - } - - - void _merge(ScopeMinNode that, RegionNode r) { - int len = Math.max(nIns(),that.nIns()); - for( int i = 2; i < len; i++) - if( alias(i) != that.alias(i) ) { // No need for redundant Phis - // If we are in lazy phi mode we need to a lookup - // by name as it will trigger a phi creation - //Var v = _vars.at(i); - Node lhs = this._mem(i,null); - Node rhs = that._mem(i,null); - alias(i, new PhiNode(Parser.memName(i), lhs._type.glb().meet(rhs._type.glb()), r, lhs, rhs).peephole()); - } - } - - // Fill in the backedge of any inserted Phis - void _endLoopMem( ScopeNode scope, ScopeMinNode back, ScopeMinNode exit ) { - Node exit_def = exit.alias(1); - for( int i=1; i _vars; - // Since of each nested lexical scope + // Size of each nested lexical scope public final Ary _lexSize; - // True if parsing inside of a constructor - public final Ary _inCons; + // Lexical scope is one of normal Block, constructor or function + public enum Kind { Block, Constructor, Function }; + public final Ary _kinds; // Extra guards; tested predicates and casted results private final Ary _guards; @@ -35,7 +36,7 @@ public class ScopeNode extends ScopeMinNode { super(true); _vars = new Ary<>(Var .class); _lexSize= new Ary<>(Integer.class); - _inCons = new Ary<>(Boolean.class); + _kinds = new Ary<>(Kind .class); _guards = new Ary<>(Node .class); } @@ -68,7 +69,7 @@ public class ScopeNode extends ScopeMinNode { public Node ctrl() { return in(0); } - public ScopeMinNode mem() { return (ScopeMinNode)in(1); } + public MemMergeNode mem() { return (MemMergeNode)in(1); } /** * The ctrl of a ScopeNode is always bound to the currently active @@ -83,19 +84,18 @@ public class ScopeNode extends ScopeMinNode { public N ctrl(N n) { return setDef(0,n); } public Node mem(Node n) { return setDef(1,n); } - public void push() { push(false); } - public void push(boolean inCon) { - assert _lexSize._len==_inCons._len; + public void push(Kind kind) { + assert _lexSize._len==_kinds._len; _lexSize.push(_vars.size()); - _inCons.push(inCon); + _kinds .push(kind); } // Pop a lexical scope public void pop() { - assert _lexSize._len==_inCons._len; + assert _lexSize._len==_kinds._len; promote(); int n = _lexSize.pop(); - _inCons.pop(); + _kinds.pop(); popUntil(n); _vars.setLen(n); } @@ -119,7 +119,16 @@ public class ScopeNode extends ScopeMinNode { } - public boolean inCon() { return _inCons.last(); } + public boolean inCon() { return _kinds.last() == Kind.Constructor; } + + // Is v outside any current function scope? + public boolean outOfFunction( Var v ) { + for( int i=_lexSize._len-1; i>=0 && v._idx<_lexSize.at(i); i-- ) + if( _kinds.at(i)==Kind.Function ) + return true; + return false; + } + // Find name in reverse, return an index into _vars or -1. Linear scan // instead of hashtable, but probably doesn't matter until the scan @@ -141,8 +150,9 @@ public class ScopeNode extends ScopeMinNode { Var n = _vars.at(i); if( n._name.equals(name) ) { if( !n.isFRef() ) return false; // Double define - n.defFRef(declaredType,xfinal,loc); // Declare full correct type, final, source location FRefNode fref = (FRefNode)in(n._idx); // Get forward ref + 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 } } @@ -185,7 +195,7 @@ public class ScopeNode extends ScopeMinNode { update(_vars.at(idx),n); } - public Var update( ScopeNode.Var v, Node st ) { + public Var update( Var v, Node st ) { Node old = in(v._idx); if( old instanceof ScopeNode loop ) { // Lazy Phi! @@ -225,7 +235,7 @@ public class ScopeNode extends ScopeMinNode { // 3) Ensure that the order of defs is the same to allow easy merging dup._vars .addAll(_vars ); dup._lexSize.addAll(_lexSize); - dup._inCons .addAll(_inCons ); + dup._kinds .addAll(_kinds ); dup._guards .addAll(_guards ); // The dup'd guards all need dup'd keepers, to keep proper accounting // when later removing all guards @@ -235,7 +245,7 @@ public class ScopeNode extends ScopeMinNode { dup.addDef(ctrl()); // Control input is just copied // Memory input is a shallow copy - ScopeMinNode memdup = new ScopeMinNode(true), mem = mem(); + MemMergeNode memdup = new MemMergeNode(true), mem = mem(); memdup.addDef(null); memdup.addDef(loop ? this : mem.in(1)); for( int i=2; i