From 499906b94893cb808df96810d46441857ae432d4 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Thu, 7 Dec 2023 09:26:54 +0000 Subject: Backport some of the code refactoring to previous chapters (#50) * #44 Revise docs and comments * #44 Add starting scope to xScopes * #44 back some of the code refactoring port to previous chapters * #44 add_def should not be public * #44 add_def should not be public. Rename method names so that they are camelcase --- .../com/seaofnodes/simple/GraphVisualizer.java | 4 +- .../main/java/com/seaofnodes/simple/Parser.java | 76 ++++---- .../src/main/java/com/seaofnodes/simple/Utils.java | 39 +++++ .../java/com/seaofnodes/simple/node/AddNode.java | 8 +- .../java/com/seaofnodes/simple/node/BoolNode.java | 9 +- .../com/seaofnodes/simple/node/ConstantNode.java | 3 +- .../java/com/seaofnodes/simple/node/IfNode.java | 5 +- .../java/com/seaofnodes/simple/node/MultiNode.java | 2 - .../main/java/com/seaofnodes/simple/node/Node.java | 195 ++++++++++++--------- .../java/com/seaofnodes/simple/node/NotNode.java | 28 +++ .../java/com/seaofnodes/simple/node/PhiNode.java | 2 + .../java/com/seaofnodes/simple/node/ProjNode.java | 4 - .../com/seaofnodes/simple/node/RegionNode.java | 2 +- .../com/seaofnodes/simple/node/ReturnNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 161 ++++++++++------- .../java/com/seaofnodes/simple/node/StartNode.java | 1 + .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- .../main/java/com/seaofnodes/simple/type/Type.java | 2 +- .../com/seaofnodes/simple/type/TypeInteger.java | 5 - .../java/com/seaofnodes/simple/type/TypeTuple.java | 2 +- 20 files changed, 338 insertions(+), 214 deletions(-) create mode 100644 chapter05/src/main/java/com/seaofnodes/simple/Utils.java create mode 100644 chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java (limited to 'chapter05/src/main/java') diff --git a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 01b5aeeb..1c3e314c 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -40,14 +40,14 @@ public class GraphVisualizer { nodes(sb, all); // Now the scopes, in a cluster no edges - for (ScopeNode sn: parser._allScopes) + for (ScopeNode sn: parser._xScopes) scopes(sb, sn); // Walk the Node edges nodeEdges(sb, all); // Walk the Scope edges - for (ScopeNode sn: parser._allScopes) + for (ScopeNode sn: parser._xScopes) scopeEdges(sb, sn); sb.append("}\n"); diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java index 0461dc69..3de0e9b8 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java @@ -14,11 +14,6 @@ import java.util.*; */ public class Parser { - /** - * The control is a name that binds to the currently active control - * node in the graph - */ - public static final String CTRL = "$ctrl"; /** * A Global Static, unique to each compilation. This is a public, so we @@ -44,7 +39,7 @@ public class Parser { *

* We keep a list of all ScopeNodes so that we can show them in graphs. * @see #parseIf() - * @see #_allScopes + * @see #_xScopes */ public ScopeNode _scope; @@ -65,14 +60,13 @@ public class Parser { * We clone ScopeNodes when control flows branch; it is useful to have * a list of all active ScopeNodes for purposes of visualization of the SoN graph */ - public final Stack _allScopes = new Stack<>(); + public final Stack _xScopes = new Stack<>(); public Parser(String source, TypeInteger arg) { - _lexer = new Lexer(source); Node.reset(); + _lexer = new Lexer(source); _scope = new ScopeNode(); START = new StartNode(new Type[]{ Type.CONTROL, arg }); - START.peephole(); STOP = new StopNode(); } @@ -80,30 +74,35 @@ public class Parser { this(source, TypeInteger.BOT); } + @Override + public String toString() { return _lexer.toString(); } + String src() { return new String( _lexer._input ); } + // Debugging utility to find a Node by index + public static Node find(int nid) { return START.find(nid); } + private Node ctrl() { return _scope.ctrl(); } private Node ctrl(Node n) { return _scope.ctrl(n); } public StopNode parse() { return parse(false); } public StopNode parse(boolean show) { - _allScopes.push(_scope); + _xScopes.push(_scope); + // Enter a new scope for the initial control and arguments _scope.push(); - try { - _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole()); - _scope.define("arg", new ProjNode(START, 1, "arg").peephole()); - parseBlock(); - if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); - return STOP; - } - finally { - _scope.pop(); - _allScopes.pop(); - if( show ) showGraph(); - } + _scope.define(ScopeNode.CTRL, new ProjNode(START, 0, ScopeNode.CTRL).peephole()); + _scope.define(ScopeNode.ARG0, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); + parseBlock(); + _scope.pop(); + _xScopes.pop(); + if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); + STOP.peephole(); + if( show ) showGraph(); + return STOP; } + /** * Parses a block * @@ -116,14 +115,11 @@ public class Parser { private Node parseBlock() { // Enter a new scope _scope.push(); - Node n = null; - while (!peek('}') && !_lexer.isEOF()) { - Node n0 = parseStatement(); - if (n0 != null) n = n0; // Allow null returns from eg showGraph - }; + while (!peek('}') && !_lexer.isEOF()) + parseStatement(); // Exit scope _scope.pop(); - return n; + return null; } /** @@ -164,7 +160,7 @@ public class Parser { // But first clone the scope and set it as current int ndefs = _scope.nIns(); ScopeNode fScope = _scope.dup(); // Duplicate current scope - _allScopes.push(fScope); // For graph visualization we need all scopes + _xScopes.push(fScope); // For graph visualization we need all scopes // Parse the true side ctrl(ifT); // set ctrl token to ifTrue projection @@ -174,14 +170,17 @@ public class Parser { // Parse the false side _scope = fScope; // Restore scope, then parse else block if any ctrl(ifF); // Ctrl token is now set to ifFalse projection - if (matchx("else")) parseStatement(); + if (matchx("else")) { + parseStatement(); + fScope = _scope; + } if( tScope.nIns() != ndefs || fScope.nIns() != ndefs ) throw error("Cannot define a new name on one arm of an if"); // Merge results _scope = tScope; - _allScopes.pop(); // Discard pushed from graph display + _xScopes.pop(); // Discard pushed from graph display return ctrl(tScope.mergeScopes(fScope)); } @@ -267,12 +266,12 @@ public class Parser { */ private Node parseComparison() { var lhs = parseAddition(); - if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole(); - if (match("!=")) return new BoolNode.NENode(lhs, parseComparison()).peephole(); - if (match("<" )) return new BoolNode.LTNode(lhs, parseComparison()).peephole(); - if (match("<=")) return new BoolNode.LENode(lhs, parseComparison()).peephole(); - if (match(">" )) return new BoolNode.GTNode(lhs, parseComparison()).peephole(); - if (match(">=")) return new BoolNode.GENode(lhs, parseComparison()).peephole(); + if (match("==")) return new BoolNode.EQ(lhs, parseComparison()).peephole(); + if (match("!=")) return new NotNode(new BoolNode.EQ(lhs, parseComparison()).peephole()).peephole(); + if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole(); + if (match("<=")) return new BoolNode.LE(lhs, parseComparison()).peephole(); + if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole(); + if (match(">=")) return new BoolNode.LE(parseComparison(), lhs).peephole(); return lhs; } @@ -520,7 +519,4 @@ public class Parser { return new String(_input, start, 1); } } - - public static RuntimeException TODO() { return TODO("Not yet implemented"); } - public static RuntimeException TODO(String msg) { return new RuntimeException(msg); } } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Utils.java b/chapter05/src/main/java/com/seaofnodes/simple/Utils.java new file mode 100644 index 00000000..4d663c25 --- /dev/null +++ b/chapter05/src/main/java/com/seaofnodes/simple/Utils.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple; + +import java.util.ArrayList; + +public class Utils { + public static RuntimeException TODO() { return TODO("Not yet implemented"); } + public static RuntimeException TODO(String msg) { return new RuntimeException(msg); } + + /** + * Fast, constant-time, element removal. Does not preserve order + * + * @param array ArrayList to modify + * @param i element to be removed + * @return element removed + */ + public static E del(ArrayList array, int i) { + if ( i >= 0 && i < array.size() ) { + E tmp = array.get(i); + E last = array.removeLast(); + if (i < array.size()) array.set(i, last); + return tmp; + } + return null; + } + + /** + * Search a list for an element by reference + * + * @param ary List to search in + * @param x Object to be searched + * @return >= 0 on success, -1 on failure + */ + public static int find( ArrayList ary, E x ) { + for( int i=0; i" ; } boolean doOp(long lhs, long rhs) { return lhs > rhs; } Node copy(Node lhs, Node rhs) { return new GTNode(lhs,rhs); } } - public static class GENode extends BoolNode { public GENode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return ">="; } boolean doOp(long lhs, long rhs) { return lhs >= rhs; } Node copy(Node lhs, Node rhs) { return new GENode(lhs,rhs); } } + public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } } + public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } } + public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } } } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index ec85bf1f..ba6f55d7 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -23,7 +23,7 @@ public class ConstantNode extends Node { } @Override - public String label() { return "#"+_con; } + public String label() { return ""+_con; } @Override public String uniqueName() { return "Con_" + _nid; } @@ -38,5 +38,4 @@ public class ConstantNode extends Node { @Override public Node idealize() { return null; } - } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java index b46d37db..6124b893 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -20,7 +20,10 @@ public class IfNode extends MultiNode { } @Override public boolean isCFG() { return true; } - + + public Node ctrl() { return in(0); } + public Node pred() { return in(1); } + @Override public Type compute() { return TypeTuple.IF; diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java index fe3fddf8..81c90f68 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -1,7 +1,5 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Type; - public abstract class MultiNode extends Node { public MultiNode(Node... inputs) { super(inputs); } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java index 65151acb..3b841d8c 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import java.util.*; @@ -71,7 +71,15 @@ public abstract class Node { // Graphical label, e.g. "+" or "Region" or "==" public String glabel() { return label(); } + + + // ------------------------------------------------------------------------ + // Debugger Printing. + + // {@code toString} is what you get in the debugger. It has to print 1 + // line (because this is what a debugger typically displays by default) and + // has to be robust with broken graph/nodes. @Override public final String toString() { // TODO: This needs a lot of work @@ -105,71 +113,14 @@ public abstract class Node { public int nIns() { return _inputs.size(); } + public Node out(int i) { return _outputs.get(i); } + public int nOuts() { return _outputs.size(); } public boolean isUnused() { return nOuts() == 0; } public boolean isCFG() { return false; } - /** - * We allow disabling peephole opt so that we can observe the - * full graph, vs the optimized graph. - */ - public static boolean _disablePeephole = false; - - /** - * Try to peephole at this node and return a better replacement Node if - * possible. We compute a {@link Type} and then check and replace: - *

- */ - public final Node peephole( ) { - // Compute initial or improved Type - Type type = _type = compute(); - - if (_disablePeephole) - return this; // Peephole optimizations turned off - - // Replace constant computations from non-constants with a constant node - if (!(this instanceof ConstantNode) && type.isConstant()) - return deadCodeElim(new ConstantNode(type).peephole()); - - // Future chapter: Global Value Numbering goes here - - // Ask each node for a better replacement - Node n = idealize(); - if( n != null ) // Something changed - // Recursively optimize - return deadCodeElim(n.peephole()); - - return this; // No progress - } - - // m is the new Node, self is the old. - // Return 'm', which may have zero uses but is alive nonetheless. - // If self has zero uses (and is not 'm'), {@link #kill} self. - private Node deadCodeElim(Node m) { - // If self is going dead and not being returned here (Nodes returned - // from peephole commonly have no uses (yet)), then kill self. - if( m != this && isUnused() ) { - // Killing self - and since self recursively kills self's inputs we - // might end up killing 'm', which we are returning as a live Node. - // So we add a bogus extra null output edge to stop kill(). - m.addUse(null); // Add bogus null use to keep m alive - kill(); // Kill self because replacing with 'm' - m.delUse(null); // Remove bogus null. - } - return m; - } /** @@ -186,9 +137,9 @@ public abstract class Node { * * @param idx which def to set * @param new_def the new definition - * @return this for flow coding + * @return new_def for flow coding */ - Node set_def(int idx, Node new_def ) { + Node setDef(int idx, Node new_def ) { Node old_def = in(idx); if( old_def == new_def ) return this; // No change // If new def is not null, add the corresponding def->use edge @@ -202,7 +153,7 @@ public abstract class Node { // Set the new_def over the old (killed) edge _inputs.set(idx,new_def); // Return self for easy flow-coding - return this; + return new_def; } /** @@ -212,7 +163,7 @@ public abstract class Node { * @param new_def the new definition, appended to the end of existing definitions * @return new_def for flow coding */ - Node add_def(Node new_def) { + Node addDef(Node new_def) { // Add use->def edge _inputs.add(new_def); // If new def is not null, add the corresponding def->use edge @@ -222,27 +173,21 @@ public abstract class Node { } // Breaks the edge invariants, used temporarily - private void addUse(Node n) { _outputs.add(n); } + protected 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. // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { - ArrayList outs = _outputs; - int lidx = outs.size()-1; // Last index - // This 1-line hack compresses an element out of an ArrayList - // without having to copy the contents. The last element is - // stuffed over the deleted element, and then the size is reduced. - outs.set(outs.indexOf(use),outs.get(lidx)); - outs.remove(lidx); // Reduce ArrayList size without copying anything - return lidx==0; + Utils.del(_outputs, Utils.find(_outputs, use)); + return _outputs.size() == 0; } // Shortcut for "popping" n nodes. A "pop" is basically a // set_def(last,null) followed by lowering the nIns() count. - void pop_n(int n) { + void popN(int n) { for( int i=0; iuses, by setting all of its defs * to null. This may recursively kill more Nodes and is basically dead - * code elimination. This function is co-recursive with {@link #pop_n}. + * code elimination. This function is co-recursive with {@link #popN}. */ public void kill( ) { assert isUnused(); // Has no uses, so it is dead - pop_n(nIns()); // Set all inputs to null, recursively killing unused Nodes + popN(nIns()); // Set all inputs to null, recursively killing unused Nodes _type=null; // Flag as dead assert isDead(); // Really dead now } // Mostly used for asserts and printing. boolean isDead() { return isUnused() && nIns()==0 && _type==null; } + + // Shortcuts to stop DCE mid-parse + // Add bogus null use to keep node alive + public N keep() { return addUse(null); } + // Remove bogus null. + public N unkeep() { delUse(null); return (N)this; } + // ------------------------------------------------------------------------ + // Graph-based optimizations + + /** + * We allow disabling peephole opt so that we can observe the + * full graph, vs the optimized graph. + */ + public static boolean _disablePeephole = false; + + /** + * Try to peephole at this node and return a better replacement Node if + * possible. We compute a {@link Type} and then check and replace: + *
    + *
  • if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}
    • + *
  • in a future chapter we will look for a + * Common Subexpression + * to eliminate.
    • + *
  • we ask the Node for a better replacement. The "better replacement" + * is things like {@code (1+2)} becomes {@code 3} and {@code (1+(x+2))} becomes + * {@code (x+(1+2))}. By canonicalizing expressions we fold common addressing + * math constants, remove algebraic identities and generally simplify the + * code.
    • + *
+ */ + public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); + + if (_disablePeephole) + return this; // Peephole optimizations turned off + + // Replace constant computations from non-constants with a constant node + if (!(this instanceof ConstantNode) && type.isConstant()) + return deadCodeElim(new ConstantNode(type).peephole()); + + // Future chapter: Global Value Numbering goes here + + // Ask each node for a better replacement + Node n = idealize(); + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); + + return this; // No progress + } + + // m is the new Node, self is the old. + // Return 'm', which may have zero uses but is alive nonetheless. + // If self has zero uses (and is not 'm'), {@link #kill} self. + private Node deadCodeElim(Node m) { + // If self is going dead and not being returned here (Nodes returned + // from peephole commonly have no uses (yet)), then kill self. + if( m != this && isUnused() ) { + // Killing self - and since self recursively kills self's inputs we + // might end up killing 'm', which we are returning as a live Node. + // So we add a bogus extra null output edge to stop kill(). + m.keep(); // Keep m alive + kill(); // Kill self because replacing with 'm' + m.unkeep(); // Okay to peephole m + } + return m; + } /** * This function needs to be @@ -330,7 +343,7 @@ public abstract class Node { public abstract Node idealize(); - // ----------------------- + // ------------------------------------------------------------------------ // Peephole utilities // Swap inputs without letting either input go dead during the swap. @@ -343,7 +356,7 @@ public abstract class Node { // does this node contain all constants? // Ignores in(0), as is usually control. - boolean all_cons() { + boolean allCons() { for( int i=1; i> _scopes = new Stack<>(); + public static final String CTRL = "$ctrl"; + public static final String ARG0 = "arg"; - // Reverse lookup for nicer graph printing - private final ArrayList _rlabels = new ArrayList<>(); + /** + * Names for every input edge + */ + public final Stack> _scopes; + + + // A new ScopeNode + public ScopeNode() { + _scopes = new Stack<>(); + _type = Type.BOTTOM; + } + @Override public String label() { return "Scope"; } @@ -41,60 +50,86 @@ public class ScopeNode extends Node { } return sb; } - - @Override - public Type compute() { return Type.BOTTOM; } - - @Override public Node idealize() { return null; } - // Add an empty lexical scope - public HashMap push() { - return _scopes.push(new HashMap<>()); + /** + * Recover the names for all variable bindings. + * The result is an array of names that is aligned with the + * inputs to the Node. + * + * This is an expensive operation. + */ + public String[] reverseNames() { + String[] names = new String[nIns()]; + for( HashMap syms : _scopes ) + for( String name : syms.keySet() ) + names[syms.get(name)] = name; + return names; } + + @Override public Type compute() { return Type.BOTTOM; } - // Remove the current lexical scope, killing all unused nodes. - public void pop() { - HashMap scope = _scopes.pop(); - pop_n(scope.size()); - } + @Override public Node idealize() { return null; } + + public void push() { _scopes.push(new HashMap<>()); } + public void pop() { popN(_scopes.pop().size()); } - // Create a new name in the current scope + /** + * Create a new name in the current scope + */ public Node define( String name, Node n ) { - HashMap scope = _scopes.lastElement(); - if( scope.put(name,nIns()) != null ) + HashMap syms = _scopes.lastElement(); + if( syms.put(name,nIns()) != null ) return null; // Double define - _rlabels.add(name); - return add_def(n); + return addDef(n); } - - // Lookup a name in all scopes - public Node lookup(String name) { - for (int i = _scopes.size() - 1; i >= 0; i--) { - var idx = _scopes.get(i).get(name); - if (idx != null) return in(idx); - } - return null; + /** + * Lookup a name in all scopes starting from most deeply nested. + * + * @param name Name to be looked up + * @see #update(String, Node, int) + */ + public Node lookup( String name ) { return update(name,null,_scopes.size()-1); } + /** + * If the name is present in any scope, then redefine else null + * + * @param name Name being redefined + * @param n The node to bind to the name + */ + public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); } + /** + * Both recursive lookup and update. + * + * A shared implementation allows us to create lazy phis both during + * lookups and updates; the lazy phi creation is part of chapter 8. + * + * @param name Name whose binding is being updated or looked up + * @param n If null, do a lookup, else update binding + * @param nestingLevel The starting nesting level + * @return node being looked up, or the one that was updated + */ + private Node update( String name, Node n, int nestingLevel ) { + if( nestingLevel<0 ) return null; // Missed in all scopes, not found + var syms = _scopes.get(nestingLevel); // Get the symbol table for nesting level + var idx = syms.get(name); + if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope + Node old = in(idx); + // If n is null we are looking up rather than updating, hence return existing value + return n==null ? old : setDef(idx,n); } - public Node ctrl() { assert lookup(Parser.CTRL)==in(0); return in(0); } - - public Node ctrl(Node n) { - assert lookup(Parser.CTRL)==in(0); - set_def(0,n); - return n; - } + public Node ctrl() { return in(0); } - - // If the name is present in any scope, then redefine - public Node update(String name, Node n) { - for (int i = _scopes.size() - 1; i >= 0; i--) { - HashMap scope = _scopes.get(i); - Integer idx = scope.get(name); - if (idx != null) // Found prior def - return set_def(idx,n); // Update def in scope - } - return null; - } + /** + * The ctrl of a ScopeNode is always bound to the currently active + * control node in the graph, via a special name '$ctrl' that is not + * a valid identifier in the language grammar and hence cannot be + * referenced in Simple code. + * + * @param n The node to be bound to '$ctrl' + * + * @return Node that was bound + */ + public Node ctrl(Node n) { return setDef(0,n); } /** * Duplicate a ScopeNode; including all levels, up to Nodes. So this is @@ -105,19 +140,19 @@ public class ScopeNode extends Node { * The new Scope is a full-fledged Node with proper use<->def edges. */ public ScopeNode dup() { + ScopeNode dup = new ScopeNode(); // Our goals are: // 1) duplicate the name bindings of the ScopeNode across all stack levels // 2) Make the new ScopeNode a user of all the nodes bound // 3) Ensure that the order of defs is the same to allow easy merging - ScopeNode dup = new ScopeNode(); - for( HashMap tab : _scopes ) - dup._scopes.push(new HashMap<>(tab)); - for( int i=0; i syms : _scopes ) + dup._scopes.push(new HashMap<>(syms)); + dup.addDef(ctrl()); // Control input is just copied + for( int i=1; i