diff options
Diffstat (limited to 'chapter18')
15 files changed, 245 insertions, 186 deletions
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("<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\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("<TR>"); for( int m=2; m<n.nIns(); m++ ) @@ -276,7 +275,7 @@ public class JSViewer implements AutoCloseable { n instanceof CProjNode || // ScopeNodes are done separately n instanceof ScopeNode || - n instanceof ScopeMinNode + n instanceof MemMergeNode ) continue; if( n.isDead() ) @@ -351,7 +350,7 @@ public class JSViewer implements AutoCloseable { // Memory if( scope.nIns()>1 ) { - ScopeMinNode n = scope.mem(); + MemMergeNode n = scope.mem(); for( int i=2; i<n.nIns(); i++ ) { Node def = n.in(i); while( def instanceof ScopeNode lazy ) diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java index 9bce5a5c..e518d2a0 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java @@ -104,6 +104,7 @@ public class Parser { public Parser(String source, TypeInteger arg) { Node.reset(); IterPeeps.reset(); + Type.reset(); _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; @@ -155,10 +156,10 @@ public class Parser { _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, null, _lexer); ctrl(XCTRL); - _scope.mem(new ScopeMinNode(false)); + _scope.mem(new MemMergeNode(false)); // Parse whole program, as-if function header "{ int arg -> 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<varlen; i++ ) { s.addDef(_scope.in(i)); - ScopeMinNode.Var v = _scope._vars.at(i); + Var v = _scope._vars.at(i); fs[i-lexlen] = Field.make(v._name,v.type(),ALIAS++,v._final); } TypeStruct ts = s._ts = TypeStruct.make(typeName, fs); @@ -814,6 +814,8 @@ public class Parser { // Cannot check earlier, because cannot find required 'id' until after "[]?" syntax int old2 = pos(); String id = _lexer.matchId(); + if( !(peek(',') || peek(';')) ) + return posT(old1); pos(old2); // Reset lexer to reparse if( id==null || _scope.lookup(id)!=null ) return posT(old1); // Reset lexer to reparse @@ -1015,7 +1017,7 @@ public class Parser { int delta = _lexer.peek(-1)=='+' ? 1 : -1; // Pre vs post String name = _lexer.matchId(); if( name!=null ) { - ScopeMinNode.Var n = _scope.lookup(name); + Var n = _scope.lookup(name); if( n != null && !(n.type() instanceof TypeMemPtr) ) { if( n._final ) throw error("Cannot reassign final '"+n._name+"'"); @@ -1051,10 +1053,11 @@ public class Parser { if( matchx("new" ) ) return alloc(); if( match ("{" ) ) return require(func(),"}"); // Expect an identifier now - ScopeMinNode.Var n = requireLookupId(); + Var n = requireLookupId(); Node rvalue = _scope.in(n); if( rvalue._type == Type.BOTTOM ) - throw error("Cannot read uninitialized field '"+n._name+"'"); + if( rvalue instanceof FRefNode ) return rvalue; + else throw error("Cannot read uninitialized field '"+n._name+"'"); // Check for assign-update, x += e0; char ch = _lexer.matchOperAssign(); if( ch==0 ) return rvalue; @@ -1091,16 +1094,20 @@ public class Parser { } // Expect an ID here. If not found, assume a forward reference function - ScopeMinNode.Var requireLookupId() { + Var requireLookupId() { String id = _lexer.matchId(); if( id == null || KEYWORDS.contains(id) ) throw errorSyntax("an identifier or expression"); - ScopeMinNode.Var n = _scope.lookup(id); + Var n = _scope.lookup(id); // If missing, assume a forward reference if( n==null ) { - _scope.define(id, TypeFunPtr.BOT, false, XCTRL, loc()); + _scope.define(id, FRefNode.FREF_TYPE, true, XCTRL, loc()); n = _scope.lookup(id); - //throw error("Undefined name '" + id + "'"); + } else { + // Lookup worked on an out-of-function value. No closures, so this + // has to be a final constant. + if( _scope.outOfFunction(n) && !(n._final && _scope.in(n._idx)._type.isConstant()) ) + throw error("Variable '"+n._name+"' is out of function scope and must be a final constant"); } return n; } @@ -1138,13 +1145,12 @@ public class Parser { if( hasConstructor ) { idx = _scope.nIns(); // Push a scope, and pre-assign all struct fields. - _scope.push(); + _scope.push(ScopeNode.Kind.Block); Lexer loc = loc(); for( int i=0; i<fs.length; i++ ) _scope.define(fs[i]._fname, fs[i]._type, fs[i]._final, s.in(i)._type==Type.TOP ? con(Type.BOTTOM) : s.in(i), loc); // Parse the constructor body - parseBlock(true); - require("}"); + require(parseBlock(ScopeNode.Kind.Constructor),"}"); init = _scope._inputs; } // Check that all fields are initialized @@ -1261,7 +1267,7 @@ public class Parser { return val.unkeep(); // "obj.a = expr" returns the expression while updating memory } - Node load = new LoadNode(loc(),name, f._alias, tf.glb(), memAlias(f._alias), expr.keep(), off); + Node load = new LoadNode(loc(),name, f._alias, tf, memAlias(f._alias), expr.keep(), off); // Arrays include control, as a proxy for a safety range check // Structs don't need this; they only need a NPE check which is // done via the type system. @@ -1344,7 +1350,7 @@ public class Parser { private Node functionCall(Node expr) { if( expr._type == Type.NIL ) throw error("Calling a null function pointer"); - if( !(expr._type instanceof TypeFunPtr tfp) ) + if( !expr._type.isa(TypeFunPtr.BOT) ) throw error("Expected a function but got "+expr._type.glb().str()); expr.keep(); // Keep while parsing args @@ -1372,7 +1378,7 @@ public class Parser { // Control from CallEnd ctrl(new CProjNode(cend,0,ScopeNode.CTRL).peephole()); // Memory from CallEnd - ScopeMinNode mem = new ScopeMinNode(true); + MemMergeNode mem = new MemMergeNode(true); mem.addDef(null); // Alias#0 mem.addDef(new ProjNode(cend,1,ScopeNode.MEM0).peephole()); _scope.mem(mem); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Var.java b/chapter18/src/main/java/com/seaofnodes/simple/Var.java new file mode 100644 index 00000000..6a8fe86d --- /dev/null +++ b/chapter18/src/main/java/com/seaofnodes/simple/Var.java @@ -0,0 +1,51 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.FRefNode; +import com.seaofnodes.simple.type.*; + + +/** + * The tracked fields are now complex enough to deserve a array-of-structs layout + */ +public class Var { + + public final String _name; // Declared name + public int _idx; // index in containing scope + private Type _type; // Declared type + public boolean _final; // Final field + public Parser.Lexer _loc; // Source location + + public Var(int idx, String name, Type type, boolean xfinal, Parser.Lexer loc) { + _idx = idx; + _name = name; + _type = type; + _final = xfinal; + _loc = loc; + } + public Type type() { + if( !_type.isFRef() ) return _type; + // Update self to no longer use the forward ref type + Type def = Parser.TYPES.get(((TypeMemPtr)_type)._obj._name); + return (_type=_type.meet(def)); + } + public Type lazyGLB() { + Type t = type(); + return t instanceof TypeMemPtr ? t : t.glb(); + } + + // Forward reference variables (not types) can only be a bottom + // function pointer. + public boolean isFRef() { return type()== FRefNode.FREF_TYPE; } + + public boolean defFRef( Type type, boolean xfinal, Parser.Lexer loc ) { + assert isFRef() && xfinal; + _type = type; + _final = true; + _loc = loc; + return true; + } + + @Override public String toString() { + return _type.toString()+(_final ? " ": " !")+_name; + } +} diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/FRefNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/FRefNode.java index 5b46959e..beb14870 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/FRefNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/FRefNode.java @@ -1,35 +1,25 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Var; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeFunPtr; import java.util.BitSet; /** - * A Constant node represents a constant value. At present, the only constants - * that we allow are integer literals; therefore Constants contain an integer - * value. As we add other types of constants, we will refactor how we represent - * Constants. - * <p> - * 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 <em>solely</em> to allow visitation. - * <p> - * 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/ScopeMinNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 38c169fa..61d99ed1 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -2,61 +2,25 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.Var; import com.seaofnodes.simple.type.*; import java.util.*; - import static com.seaofnodes.simple.Utils.TODO; -/* */ -public class ScopeMinNode extends Node { - - public final boolean _inProgress; +/** + * 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 { - /** The tracked fields are now complex enough to deserve a array-of-structs layout + /* + * 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 static class Var { - public final String _name; // Declared name - public int _idx; // index in containing scope - private Type _type; // Declared type - public boolean _final; // Final field - public Parser.Lexer _loc; // Source location - public Var(int idx, String name, Type type, boolean xfinal, Parser.Lexer loc) { - _idx = idx; - _name = name; - _type = type; - _final = xfinal; - _loc = loc; - } - public Type type() { - if( !_type.isFRef() ) return _type; - // Update self to no longer use the forward ref type - Type def = Parser.TYPES.get(((TypeMemPtr)_type)._obj._name); - return (_type=_type.meet(def)); - } - public Type lazyGLB() { - Type t = type(); - return t instanceof TypeMemPtr ? t : t.glb(); - } - - // Forward reference variables (not types) can only be a bottom - // function pointer. - public boolean isFRef() { return type()==TypeFunPtr.BOT; } - - public boolean defFRef( Type type, boolean xfinal, Parser.Lexer loc ) { - assert isFRef(); - _type = type; - _final = xfinal; - _loc = loc; - return true; - } - - @Override public String toString() { - return _type.toString()+(_final ? " ": " !")+_name; - } - } + public final boolean _inProgress; - public ScopeMinNode(boolean inProgress) { _type = TypeMem.BOT; _inProgress = inProgress; } + public MemMergeNode( boolean inProgress) { _type = TypeMem.BOT; _inProgress = inProgress; } // If being used by a Scope, this is "in progress" from the Parser. @@ -88,7 +52,7 @@ public class ScopeMinNode extends Node { // not related to the parser in any way. public Node merge() { // Force default memory to not be lazy - ScopeMinNode merge = new ScopeMinNode(false); + MemMergeNode merge = new MemMergeNode(false); for( Node n : _inputs ) merge.addDef(n); merge._mem(1,null); @@ -127,7 +91,7 @@ public class ScopeMinNode extends Node { // then it must be START.proj(1) Node old = alias(alias); if( old instanceof ScopeNode loop ) { - ScopeMinNode loopmem = loop.mem(); + MemMergeNode loopmem = loop.mem(); Node memdef = loopmem.alias(alias); // Lazy phi! old = memdef instanceof PhiNode phi && loop.ctrl()==phi.region() @@ -144,7 +108,7 @@ public class ScopeMinNode extends Node { } - void _merge(ScopeMinNode that, RegionNode r) { + 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 @@ -158,7 +122,7 @@ public class ScopeMinNode extends Node { } // Fill in the backedge of any inserted Phis - void _endLoopMem( ScopeNode scope, ScopeMinNode back, ScopeMinNode exit ) { + void _endLoopMem( ScopeNode scope, MemMergeNode back, MemMergeNode exit ) { Node exit_def = exit.alias(1); for( int i=1; i<back.nIns(); i++ ) { if( in(i) instanceof PhiNode phi && phi.region()==scope.ctrl() ) { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 2ad6e5b7..727f7bbf 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -6,9 +6,9 @@ import java.util.*; /** * The Scope node is purely a parser helper - it tracks names to nodes with a - * stack of hashmaps. + * stack of variables. */ -public class ScopeNode extends ScopeMinNode { +public class ScopeNode extends MemMergeNode { /** * The control is a name that binds to the currently active control @@ -21,11 +21,12 @@ public class ScopeNode extends ScopeMinNode { // All active/live variables in all nested scopes, all run together public final Ary<Var> _vars; - // Since of each nested lexical scope + // Size of each nested lexical scope public final Ary<Integer> _lexSize; - // True if parsing inside of a constructor - public final Ary<Boolean> _inCons; + // Lexical scope is one of normal Block, constructor or function + public enum Kind { Block, Constructor, Function }; + public final Ary<Kind> _kinds; // Extra guards; tested predicates and casted results private final Ary<Node> _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 extends Node> 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<mem.nIns(); i++ ) @@ -285,7 +295,7 @@ public class ScopeNode extends ScopeMinNode { // Forward refs are copied to the other side, "as if" they were there all along. public void balanceIf( ScopeNode scope ) { for( int i = nIns(); i < scope.nIns(); i++ ) { - ScopeMinNode.Var n = scope._vars.at(i); + Var n = scope._vars.at(i); if( n.isFRef() ) { // RHS has forward refs _vars.add(n); // Copy to LHS addDef(scope.in(i)); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java index 009296e8..feb8347f 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -47,7 +47,7 @@ public class StopNode extends CFGNode { public Node idealize() { int len = nIns(); for( int i=0; i<nIns(); i++ ) - if( ((ReturnNode)in(i)).fun()==null ) + if( ((ReturnNode)in(i)).fun().isDead() ) delDef(i--); if( len != nIns() ) return this; return null; diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java index ac7d559d..95fdca74 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java @@ -229,4 +229,8 @@ public class Type { // This is used by error messages, and is a shorted print. public String str() { return STRS[_type]; } + + public static void reset() { + TypeFunPtr.reset(); + } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index ace85edc..f0dc36a7 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -124,4 +124,12 @@ public class TypeFunPtr extends TypeNil { // Usage: for( long fidxs=fidxs(); fidxs!=0; fidxs=nextFIDX(fidxs) { int fidxs = Long.numberOfTrailingZeros(fidxs); ... } public static long nextFIDX(long fidxs) { return fidxs & (fidxs-1); } + public static void reset() { + FIDXS.clear(); + FIDXS.put(MAIN._sig,1); + for( Type t : INTERN.keySet() ) + if( t instanceof TypeFunPtr tfp && tfp!=MAIN) + tfp._name = null; + } + } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 39da0c72..75ad301e 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -1,26 +1,27 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; import org.junit.Test; -import org.junit.Ignore; - import static org.junit.Assert.*; +import static org.junit.Assert.fail; +import org.junit.Ignore; public class Chapter18Test { @Test public void testJig() { - CodeGen code = new CodeGen(""" + CodeGen code = new CodeGen( +""" return 0; """); - code.parse(true).opto().typeCheck().GCM(); + code.parse(false).opto().typeCheck().GCM(); assertEquals("return 0;", code._stop.toString()); assertEquals("0", Eval2.eval(code, 0)); } @Test public void testPhiParalleAssign() { - CodeGen code = new CodeGen(""" + CodeGen code = new CodeGen( +""" int a = 1; int b = 2; while(arg--) { @@ -42,7 +43,8 @@ return a; // --------------------------------------------------------------- @Test public void testType0() { - CodeGen code = new CodeGen(""" + CodeGen code = new CodeGen( +""" {int -> int}? x2 = null; // null function ptr return x2; """); @@ -53,7 +55,8 @@ return x2; @Test public void testFcn0() { - CodeGen code = new CodeGen(""" + CodeGen code = new CodeGen( +""" {int -> int}? sq = { int x -> x*x; }; @@ -66,7 +69,8 @@ return sq; @Test public void testFcn1() { - CodeGen code = new CodeGen(""" + CodeGen code = new CodeGen( +""" var sq = { int x -> x*x; }; @@ -77,9 +81,48 @@ return sq(arg)+sq(3); assertEquals("13", Eval2.eval(code, 2)); } - // Recursive factorial test + // Function scope test @Test public void testFcn2() { + CodeGen code = new CodeGen( +""" +int cnt=1; +return { -> cnt; }; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Variable 'cnt' is out of function scope and must be a final constant",e.getMessage()); } + } + + // Function scope test + @Test + public void testFcn3() { + CodeGen code = new CodeGen( +""" +val cnt=2; +return { -> cnt; }(); +"""); + code.parse().opto(); + assertEquals("return 2;", code._stop.toString()); + assertEquals("2", Eval2.eval(code, 0)); + } + + // Function variables + @Test + public void testFcn4() { + CodeGen code = new CodeGen( +""" +var fcn = arg ? { int x -> x*x; } : { int x -> x+x; }; +return fcn(3); +"""); + code.parse().opto(); + assertEquals("Stop[ return Phi(Region,{ int -> int #1},{ int -> int #2})( 3); return (Parm_x(null,int)*x); return (Parm_x(null,int)*2); ]", code._stop.toString()); + assertEquals("6", Eval2.eval(code, 0)); + assertEquals("9", Eval2.eval(code, 1)); + } + + // Recursive factorial test + @Test + public void testFcn5() { CodeGen code = new CodeGen("val fact = { int x -> x <= 1 ? 1 : x*fact(x-1); }; return fact(arg);"); code.parse().opto(); assertEquals("Stop[ return fact( arg); return Phi(Region,1,(Parm_x(fact,int,arg,(x-1))*fact( Sub))); ]", code._stop.toString()); @@ -90,34 +133,21 @@ return sq(arg)+sq(3); assertEquals("24", Eval2.eval(code, 4)); } - - + // Mutual recursion. Fails without SCCP to lift the recursive return types. @Ignore @Test - public void testFcn3() { + public void testFcn6() { CodeGen code = new CodeGen( """ -val counter = { -> - int cnt; - val rez = new {int}?[2]; - rez[0] = { -> cnt; }; - rez[1] = { -> ++cnt; }; - return rez; -}; -val A = counter(); -val B = counter(); -int[] rez = new int[5]; -rez[0] = A[0](); // Value of counter A -rez[1] = A[1](); // Increment counter A -rez[2] = B[0](); // Value of counter B -B[1](); // Increment B -B[1](); // Increment B -rez[3] = B[0](); // Value of counter B -rez[4] = A[0]() * 10 + B[0](); -return rez; +val is_even = { int x -> x ? is_odd (x-1) : true ; }; +val is_odd = { int x -> x ? is_even(x-1) : false; }; +return is_even(arg); """); code.parse().opto(); - assertEquals("Stop[ return (const)[int]; return (const)[{ -> int #ALL}?]; return 0; return 1; ]", code._stop.toString()); - assertEquals("13", Eval2.eval(code, 0)); + assertEquals("Stop[ return is_even( arg); return Phi(Region,Phi(Region,is_even( ((Parm_x(is_even,int,arg,Sub)-1)-1)),0),1); ]", code._stop.toString()); + assertEquals("1", Eval2.eval(code, 0)); + assertEquals("0", Eval2.eval(code, 1)); + assertEquals("1", Eval2.eval(code, 2)); + assertEquals("0", Eval2.eval(code, 3)); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java index 757699e4..66b5c28b 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java @@ -132,18 +132,9 @@ public abstract class Eval2 { // Return from main hits Stop F.put(BB,new Closure(code._stop,F)); - // Set incoming arg into main - FunNode main = (FunNode)code._start.uctrl(); - assert main.sig().isa(TypeFunPtr.MAIN); - for( Node use : main._outputs ) - if( use instanceof ParmNode parm && parm._idx==2 ) { - parm.setDef(1,new ConstantNode( TypeInteger.constant( arg ) ).init() ); - F.put( parm.in(1), arg ); - } - // ------------ - // Evaluate until we exit or timeout. Each outer loop step computes + // Evaluate until exit or timeout. Each outer loop step computes // all data nodes under some new Control. while( true ) { traceCtrl(BB,trace); @@ -184,19 +175,26 @@ public abstract class Eval2 { // Compute input path on Phis for this Region int path = r._inputs.find( prior ); + // Parameters read from prior frame, Phis from local frame + Frame frame = (r instanceof FunNode ? F._prior : F); + boolean isMain = r instanceof FunNode fun && fun.sig().isa(TypeFunPtr.MAIN); // Parallel assign Phis. First parallel read and cache int i; - for( i = 0; i < r.nOuts(); i++ ) - if( r.out(i) instanceof PhiNode phi ) - // Parameters read from prior frame, Phis from local frame - PHICACHE[i] = (r instanceof FunNode ? F._prior : F) - .get( (phi instanceof ParmNode parm && parm._idx==0) - // RPC reads the Call directly - ? phi.region().in(path) - // Phis read from path input - : phi.in(path)); - else break; + for( i = 0; i < r.nOuts(); i++ ) { + if( !(r.out(i) instanceof PhiNode phi) ) break; + if( isMain && phi instanceof ParmNode parm && parm._idx==2 ) + PHICACHE[i] = arg; // Reading the initial arguments to main() + else { + Node n = phi instanceof ParmNode parm + // RPC reads the Call directly; + // Parms may not be linked, so read call args directly + ? (parm._idx==0 ? prior : prior.in(parm._idx)) + // Phis read from path input + : phi.in(path); + PHICACHE[i] = frame.get(n); + } + } // Parallel assign; might assign before read, so read from cache for( int j=0; j < i; j++ ) traceData(F.put0(r.out(j),PHICACHE[j]),trace); @@ -204,6 +202,7 @@ public abstract class Eval2 { return i; } + // Make a call. private static CFGNode call( CallNode call ) { // Set up the Return PC and return frame (which is just the current frame). @@ -271,7 +270,7 @@ public abstract class Eval2 { case ProjNode proj -> proj._type instanceof TypeMem ? "$mem" : val(proj.in(0)); case ReadOnlyNode read -> val(read.in(1)); case SarNode sar -> x(sar.in(1)) >> x(sar.in(2)); - case ScopeMinNode merge-> "$mem"; + case MemMergeNode merge-> "$mem"; case ShlNode shl -> x(shl.in(1)) << x(shl.in(2)); case ShrNode shr -> x(shr.in(1)) >>>x(shr.in(2)); case StoreNode st -> store(st); diff --git a/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 8e25b133..92b424df 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -4,8 +4,6 @@ import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import java.lang.invoke.MethodHandle; -import java.lang.invoke.MethodHandles; import java.util.*; public class Evaluator { @@ -307,7 +305,7 @@ public class Evaluator { case NewNode alloc -> alloc(alloc); case CProjNode cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx]; case ProjNode proj -> ((Object[])val( proj.in(0) ))[ proj._idx]; - case ScopeMinNode mem -> null; + case MemMergeNode mem -> null; case ReadOnlyNode ro -> val(ro.in(1)); case CallNode call -> Utils.TODO(); // should not reach here, go the IfNode route default -> throw new AssertionError("Unexpected node " + node); |