diff options
74 files changed, 1414 insertions, 905 deletions
diff --git a/chapter01/README.md b/chapter01/README.md index f5f31f82..62f142e6 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -112,8 +112,6 @@ The following control and data nodes appear in this chapter. | Return | Control | Represents the termination of a function | Predecessor control node, Data node value | Return value of the function | | Constant | Data | Represents constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | -All control nodes implement a marker interface named `Control`. - Within a traditional basic block, instructions are executed in sequence. In the Sea of Nodes model, the correct sequence of instructions is determined by a scheduling algorithm that depends only on dependencies between nodes (including control dependencies) that are explicit as edges in the graph. This enables a number of optimizations at very little cost (nearly always small constant time) because all dependencies are always available. @@ -123,7 +121,7 @@ at very little cost (nearly always small constant time) because all dependencies Each node is assigned a unique dense integer Node ID when created. This ID is useful for debugging, efficiently computing equality and e.g. as an index into a bit vector, which in turn is used to efficiently visit a (possibly cyclic) -graph. We discuss Node equality in Chapter 8 Global Value Numbering. +graph. We discuss Node equality in Chapter 9 Global Value Numbering. ### Start Node diff --git a/chapter02/README.md b/chapter02/README.md index e1ee19aa..585f6ffc 100644 --- a/chapter02/README.md +++ b/chapter02/README.md @@ -21,13 +21,13 @@ In [Chapter 1](../chapter01/README.md) we introduced following nodes. We extend the set of nodes by adding following additional node types. -| Node Name | Type | Description | Inputs | Value | -|------------|------|-------------------------------|------------------------------------------------------------|-----------------------------| -| Add | Data | Add two values | Two data nodes, values are added, order not important | Result of the add operation | -| Sub | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters | Result of the subtract | -| Mul | Data | Multiply two values | Two data nodes, values are multiplied, order not important | Result of the multiply | -| Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | -| UnaryMinus | Data | Negate a value | One data node, value is negated | Result of the unary minus | +| Node Name | Type | Description | Inputs | Value | +|-----------|------|-------------------------------|------------------------------------------------------------|-----------------------------| +| Add | Data | Add two values | Two data nodes, values are added, order not important | Result of the add operation | +| Sub | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters | Result of the subtract | +| Mul | Data | Multiply two values | Two data nodes, values are multiplied, order not important | Result of the multiply | +| Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | +| Minus | Data | Negate a value | One data node, value is negated | Result of the unary minus | ## Peephole Optimizations diff --git a/chapter02/src/main/java/com/seaofnodes/simple/Parser.java b/chapter02/src/main/java/com/seaofnodes/simple/Parser.java index 5422ea66..f5aca5ba 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/Parser.java @@ -270,5 +270,4 @@ public class Parser { return new String(_input, start, 1); } } - } diff --git a/chapter02/src/main/java/com/seaofnodes/simple/Utils.java b/chapter02/src/main/java/com/seaofnodes/simple/Utils.java new file mode 100644 index 00000000..4d663c25 --- /dev/null +++ b/chapter02/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> E del(ArrayList<E> 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 <E> int find( ArrayList<E> ary, E x ) { + for( int i=0; i<ary.size(); i++ ) + if( ary.get(i)==x ) + return i; + return -1; + } +}
\ No newline at end of file diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java index dbef984e..960742e8 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import java.util.*; @@ -59,7 +60,7 @@ public abstract class Node { _outputs = new ArrayList<>(); for( Node n : _inputs ) if( n != null ) - n._outputs.add( this ); + n.addUse( this ); } // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" @@ -70,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 @@ -104,12 +113,68 @@ 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; } + + /** + * Change a <em>def</em> into a Node. Keeps the edges correct, by removing + * the corresponding <em>use->def</em> edge. This may make the original + * <em>def</em> go dead. This function is co-recursive with {@link #kill}. + * + * @param idx which def to set + * @param new_def the new definition + * @return new_def for flow coding + */ + 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 + // This needs to happen before removing the old node's def->use edge as + // the new_def might get killed if the old node kills it recursively. + if( new_def != null ) + new_def.addUse(this); + if( old_def != null && // If the old def exists, remove a def->use edge + old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + // Set the new_def over the old (killed) edge + _inputs.set(idx,new_def); + // Return self for easy flow-coding + return new_def; + } + + // Breaks the edge invariants, used temporarily + protected <N extends Node> 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 ) { + Utils.del(_outputs, Utils.find(_outputs, use)); + return _outputs.size() == 0; + } + + /** + * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> + * to null. This may recursively kill more Nodes and is basically dead + * code elimination. This function is co-recursive with {@link #setDef}. + */ + public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + for( int i=0; i<nIns(); i++ ) + setDef(i,null); // Set all inputs to null, recursively killing unused Nodes + _inputs.clear(); + _type=null; // Flag as dead + assert isDead(); // Really dead now + } + + // Mostly used for asserts and printing. + boolean isDead() { return isUnused() && nIns()==0 && _type==null; } /** * We allow disabling peephole opt so that we can observe the * full graph, vs the optimized graph. @@ -149,56 +214,6 @@ public abstract class Node { return this; // No progress } - /** - * Change a <em>def</em> into a Node. Keeps the edges correct, by removing - * the corresponding <em>use->def</em> edge. This may make the original - * <em>def</em> go dead. This function is co-recursive with {@link #kill}. - * - * @param idx which def to set - * @param new_def the new definition - * @return this for flow coding - */ - Node set_def(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 - // This needs to happen before removing the old node's def->use edge as - // the new_def might get killed if the old node kills it recursively. - if( new_def != null ) - new_def._outputs.add(this); - if( old_def != null ) { // If the old def exists, remove a use->def edge - ArrayList<Node> outs = old_def._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(this),outs.get(lidx)); - outs.remove(lidx); // Reduce ArrayList size without copying anything - if( lidx == 0 ) // If we removed the last use, the old def is now dead - old_def.kill(); // Kill old def - } - // Set the new_def over the old (killed) edge - _inputs.set(idx,new_def); - // Return self for easy flow-coding - return this; - } - /** - * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> - * to null. This may recursively kill more Nodes and is basically dead - * code elimination. This function is co-recursive with {@link #set_def}. - */ - public void kill( ) { - assert isUnused(); // Has no uses, so it is dead - for( int i=0; i<nIns(); i++ ) - set_def(i,null); // Set all inputs to null, recursively killing unused Nodes - _inputs.clear(); - _type=null; // Flag as dead - assert isDead(); // Really dead now - } - - // Mostly used for asserts and printing. - boolean isDead() { return isUnused() && nIns()==0 && _type==null; } /** * This function needs to be diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java index 172cc632..5bd51611 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java @@ -29,7 +29,7 @@ public class Type { public final byte _type; public boolean is_simple() { return _type < TSIMPLE; } - private static final String[] STRS = new String[]{"BOTTOM","TOP"}; + private static final String[] STRS = new String[]{"Bot","Top"}; protected Type(byte type) { _type = type; } public static final Type BOTTOM = new Type( TBOT ); // ALL diff --git a/chapter03/README.md b/chapter03/README.md index 3e6cebfe..07d8fe3e 100644 --- a/chapter03/README.md +++ b/chapter03/README.md @@ -19,16 +19,16 @@ Here is the [complete language grammar](docs/03-grammar.md) for this chapter. To recap, our list of Nodes are: -| Node Name | Type | Description | Inputs | Value | -|------------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| -| Start | Control | Start of function | None | None for now as we do not have function arguments yet | -| Return | Control | End of function | Predecessor control node, Data node value | Return value of the function | -| Constant | Data | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | -| Add | Data | Add two values | Two data nodes, values are added, order not important | Result of the add operation | -| Sub | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters | Result of the subtract | -| Mul | Data | Multiply two values | Two data nodes, values are multiplied, order not important | Result of the multiply | -| Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | -| UnaryMinus | Data | Negate a value | One data node, value is negated | Result of the unary minus | +| Node Name | Type | Description | Inputs | Value | +|-----------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| +| Start | Control | Start of function | None | None for now as we do not have function arguments yet | +| Return | Control | End of function | Predecessor control node, Data node value | Return value of the function | +| Constant | Data | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | +| Add | Data | Add two values | Two data nodes, values are added, order not important | Result of the add operation | +| Sub | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters | Result of the subtract | +| Mul | Data | Multiply two values | Two data nodes, values are multiplied, order not important | Result of the multiply | +| Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | +| Minus | Data | Negate a value | One data node, value is negated | Result of the unary minus | In this chapter we introduce: diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java index c8195882..60761f04 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java @@ -52,14 +52,10 @@ public class Parser { public ReturnNode parse() { return parse(false); } public ReturnNode parse(boolean show) { - try { - var ret = (ReturnNode) parseBlock(); - if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); - return ret; - } - finally { - if( show ) showGraph(); - } + var ret = (ReturnNode) parseBlock(); + if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); + if( show ) showGraph(); + return ret; } /** @@ -409,5 +405,4 @@ public class Parser { return new String(_input, start, 1); } } - } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Utils.java b/chapter03/src/main/java/com/seaofnodes/simple/Utils.java new file mode 100644 index 00000000..4d663c25 --- /dev/null +++ b/chapter03/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> E del(ArrayList<E> 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 <E> int find( ArrayList<E> ary, E x ) { + for( int i=0; i<ary.size(); i++ ) + if( ary.get(i)==x ) + return i; + return -1; + } +}
\ No newline at end of file diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java index 43dc6fa5..91bde29d 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import java.util.*; @@ -47,7 +48,7 @@ public abstract class Node { /** * A private Global Static mutable counter, for unique node id generation. - * To make the compiler multithreaded, this field will have to move into a TLS. + * To make the compiler multi-threaded, this field will have to move into a TLS. * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. * */ private static int UNIQUE_ID = 1; @@ -70,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 @@ -104,61 +113,33 @@ 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: - * <ul> - * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li> - * <li>in a future chapter we will look for a - * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a> - * to eliminate.</li> - * <li>we ask the Node for a better replacement (again, none enabled in this chapter)</li> - * </ul> - */ - 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()) { - kill(); // Kill `this` because replacing with a Constant - return new ConstantNode(type).peephole(); - } - - // Future chapter: Global Value Numbering goes here - - // Ask each node for a better replacement - Node n = idealize(); - if( n != null ) return n; - - return this; // No progress - } + /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing * the corresponding <em>use->def</em> edge. This may make the original * <em>def</em> go dead. This function is co-recursive with {@link #kill}. + * <p> + + * This method is the normal path for altering a Node, because it does the + * proper default edge maintenance. It also <em>immediately</em> kills + * Nodes that lose their last use; at times care must be taken to avoid + * killing Nodes that are being used without having an output Node. This + * definitely happens in the middle of recursive {@link #peephole} calls. * * @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 @@ -172,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; } /** @@ -182,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 @@ -192,27 +173,21 @@ public abstract class Node { } // Breaks the edge invariants, used temporarily - private void addUse(Node n) { _outputs.add(n); } + protected <N extends Node> 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<Node> 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; i<n; i++ ) { - Node old_def = _inputs.remove(_inputs.size()-1); + Node old_def = _inputs.removeLast(); if( old_def != null && // If it exists and old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def @@ -222,17 +197,55 @@ public abstract class Node { /** * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> * 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; } + /** + * 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: + * <ul> + * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li> + * <li>in a future chapter we will look for a + * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a> + * to eliminate.</li> + * <li>we ask the Node for a better replacement (again, none enabled in this chapter)</li> + * </ul> + */ + 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()) { + kill(); // Kill `this` because replacing with a Constant + return new ConstantNode(type).peephole(); + } + + // Future chapter: Global Value Numbering goes here + + // Ask each node for a better replacement + Node n = idealize(); + if( n != null ) return n; + + return this; // No progress + } /** * This function needs to be @@ -258,5 +271,25 @@ public abstract class Node { * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. */ - public static void reset() { UNIQUE_ID = 1; } + public static void reset() { UNIQUE_ID = 1; _disablePeephole=false; } + + /** + * Debugging utility to find a Node by index + */ + public Node find(int nid) { return _find(new BitSet(),nid); } + private Node _find(BitSet visit, int nid) { + if( _nid==nid ) return this; + if( visit.get(_nid) ) return null; + visit.set(_nid); + for( Node def : _inputs ) + if( def!=null ) { + Node rez = def._find(visit,nid); + if( rez != null ) return rez; + } + for( Node use : _outputs ) { + Node rez = use._find(visit,nid); + if( rez != null ) return rez; + } + return null; + } } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 49857533..7b42a2d0 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -5,20 +5,23 @@ import com.seaofnodes.simple.type.Type; import java.util.*; /** - * The Scope node is a purely parser helper - it tracks names to nodes with a + * The Scope node is purely a parser helper - it tracks names to nodes with a * stack of scopes. */ public class ScopeNode extends Node { /** - * Stack of lexical scopes, each scope is a symbol table - * that binds variable names to Nodes. - * The top of this stack represents current scope. + * Names for every input edge */ - public final Stack<HashMap<String, Integer>> _scopes = new Stack<>(); + public final Stack<HashMap<String, Integer>> _scopes; - // Reverse lookup for nicer graph printing - private final ArrayList<String> _rlabels = new ArrayList<>(); + + // A new ScopeNode + public ScopeNode() { + _scopes = new Stack<>(); + _type = Type.BOTTOM; + } + @Override public String label() { return "Scope"; } @@ -40,51 +43,85 @@ 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<String, Integer> 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<String,Integer> 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<String,Integer> scope = _scopes.pop(); - pop_n(scope.size()); - } + @Override public Node idealize() { return null; } - // Create a new name in the current scope + public void push() { _scopes.push(new HashMap<>()); } + public void pop() { popN(_scopes.pop().size()); } + + /** + * Create a new name in the current scope + */ public Node define( String name, Node n ) { - HashMap<String,Integer> scope = _scopes.lastElement(); - if( scope.put(name,nIns()) != null ) + HashMap<String,Integer> 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); } - - // 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<String, Integer> 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; - } + public Node ctrl() { return in(0); } + + /** + * 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); } } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java index 172cc632..5bd51611 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java @@ -29,7 +29,7 @@ public class Type { public final byte _type; public boolean is_simple() { return _type < TSIMPLE; } - private static final String[] STRS = new String[]{"BOTTOM","TOP"}; + private static final String[] STRS = new String[]{"Bot","Top"}; protected Type(byte type) { _type = type; } public static final Type BOTTOM = new Type( TBOT ); // ALL diff --git a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java index d86b978f..5847fed4 100644 --- a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -36,8 +36,8 @@ public class Chapter03Test { @Test public void testVarScopeNoPeephole() { - Node._disablePeephole = true; Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + Node._disablePeephole = true; ReturnNode ret = parser.parse(); Node._disablePeephole = false; assertEquals("return (1+3);", ret.print()); @@ -62,8 +62,8 @@ public class Chapter03Test { @Test public void testChapter2ParseGrammar() { - Node._disablePeephole = true; // disable peephole so we can observe full graph Parser parser = new Parser("return 1+2*3+-5;"); + Node._disablePeephole = true; // disable peephole so we can observe full graph ReturnNode ret = parser.parse(); assertEquals("return (1+((2*3)+(-5)));", ret.print()); GraphVisualizer gv = new GraphVisualizer(); diff --git a/chapter04/README.md b/chapter04/README.md index 350b08b5..25b7747e 100644 --- a/chapter04/README.md +++ b/chapter04/README.md @@ -21,19 +21,20 @@ Following are revised or new nodes | Start | Control | Start of function, now a MultiNode | | A tuple with a ctrl token and an `arg` data node | | Proj | ? | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index | | Bool | Data | Represents results of a comparison operator | Two data nodes | Result is a comparison, represented as integer value where 1=true, 0=false | +| Not | Data | Logical not | One data node | Result converts 0 to 1 and vice versa | Below is our list of Nodes from [Chapter 3](../chapter03/README.md): -| Node Name | Type | Description | Inputs | Value | -|------------|---------|------------------------------------|------------------------------------------------------------------|------------------------------| -| Return | Control | End of function | Predecessor control node, Data node value | Return value of the function | -| Constant | Data | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | -| Add | Data | Add two values | Two data nodes, values are added, order not important | Result of the add operation | -| Sub | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters | Result of the subtract | -| Mul | Data | Multiply two values | Two data nodes, values are multiplied, order not important | Result of the multiply | -| Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | -| UnaryMinus | Data | Negate a value | One data node, value is negated | Result of the unary minus | -| Scope | ? | Represents scopes in the graph | All nodes that define variables | None | +| Node Name | Type | Description | Inputs | Value | +|-----------|---------|------------------------------------|------------------------------------------------------------------|------------------------------| +| Return | Control | End of function | Predecessor control node, Data node value | Return value of the function | +| Constant | Data | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | +| Add | Data | Add two values | Two data nodes, values are added, order not important | Result of the add operation | +| Sub | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters | Result of the subtract | +| Mul | Data | Multiply two values | Two data nodes, values are multiplied, order not important | Result of the multiply | +| Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | +| Minus | Data | Negate a value | One data node, value is negated | Result of the unary minus | +| Scope | ? | Represents scopes in the graph | All nodes that define variables | None | ## Projection Nodes diff --git a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java index b505c2c5..8daaed73 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter04/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 @@ -33,7 +28,7 @@ public class Parser { private final Lexer _lexer; /** - * Stack of lexical scopes, each scope is a symbol table that binds + * A ScopeNode contains a stack of lexical scopes, each scope is a symbol table that binds * variable names to Nodes. The top of this stack represents current scope. */ public ScopeNode _scope; @@ -48,8 +43,8 @@ public class Parser { 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(); @@ -59,26 +54,29 @@ 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 ReturnNode parse() { return parse(false); } public ReturnNode parse(boolean show) { + // 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()); - var ret = (ReturnNode) parseBlock(); - if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); - return ret; - } - finally { - _scope.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()); + var ret = (ReturnNode) parseBlock(); + _scope.pop(); + if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); + if( show ) showGraph(); + return ret; } /** @@ -199,12 +197,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; } @@ -450,5 +448,4 @@ public class Parser { return new String(_input, start, 1); } } - } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/Utils.java b/chapter04/src/main/java/com/seaofnodes/simple/Utils.java new file mode 100644 index 00000000..4d663c25 --- /dev/null +++ b/chapter04/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> E del(ArrayList<E> 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 <E> int find( ArrayList<E> ary, E x ) { + for( int i=0; i<ary.size(); i++ ) + if( ary.get(i)==x ) + return i; + return -1; + } +}
\ No newline at end of file diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 06be0b75..be3ee46c 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -46,10 +46,7 @@ abstract public class BoolNode extends Node { return null; } - public static class EQNode extends BoolNode { public EQNode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } } - public static class NENode extends BoolNode { public NENode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "!="; } boolean doOp(long lhs, long rhs) { return lhs != rhs; } } - public static class LTNode extends BoolNode { public LTNode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } } - public static class LENode extends BoolNode { public LENode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } } - public static class GTNode extends BoolNode { public GTNode(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return ">" ; } boolean doOp(long lhs, long rhs) { return 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; } } + 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; } } + 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; } } + 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; } } } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index ec85bf1f..ba6f55d7 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java index fe3fddf8..81c90f68 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java index b8a7bbd6..2b293193 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import java.util.*; @@ -70,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 @@ -104,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: - * <ul> - * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li> - * <li>in a future chapter we will look for a - * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a> - * to eliminate.</li> - * <li>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. </li> - * </ul> - */ - 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; - } /** @@ -185,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 @@ -201,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; } /** @@ -211,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 @@ -221,27 +173,21 @@ public abstract class Node { } // Breaks the edge invariants, used temporarily - private void addUse(Node n) { _outputs.add(n); } + protected <N extends Node> 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<Node> 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; i<n; i++ ) { - Node old_def = _inputs.remove(_inputs.size()-1); + Node old_def = _inputs.removeLast(); if( old_def != null && // If it exists and old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def @@ -251,17 +197,85 @@ public abstract class Node { /** * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> * 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 extends Node> N keep() { return addUse(null); } + // Remove bogus null. + public <N extends Node> 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: + * <ul> + * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li> + * <li>in a future chapter we will look for a + * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a> + * to eliminate.</li> + * <li>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. </li> + * </ul> + */ + 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 @@ -329,7 +343,7 @@ public abstract class Node { public abstract Node idealize(); - // ----------------------- + // ------------------------------------------------------------------------ // Peephole utilities // Swap inputs without letting either input go dead during the swap. @@ -344,5 +358,25 @@ public abstract class Node { * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. */ - public static void reset() { UNIQUE_ID = 1; } + public static void reset() { UNIQUE_ID = 1; _disablePeephole=false; } + + /** + * Debugging utility to find a Node by index + */ + public Node find(int nid) { return _find(new BitSet(),nid); } + private Node _find(BitSet visit, int nid) { + if( _nid==nid ) return this; + if( visit.get(_nid) ) return null; + visit.set(_nid); + for( Node def : _inputs ) + if( def!=null ) { + Node rez = def._find(visit,nid); + if( rez != null ) return rez; + } + for( Node use : _outputs ) { + Node rez = use._find(visit,nid); + if( rez != null ) return rez; + } + return null; + } } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/NotNode.java new file mode 100644 index 00000000..5dd6a86e --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -0,0 +1,28 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +public class NotNode extends Node { + public NotNode(Node in) { super(null, in); } + + @Override public String label() { return "Not"; } + + @Override public String glabel() { return "!"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(!")); + return sb.append(")"); + } + + @Override + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 ) + return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0; + return Type.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 6f36226b..5dd7a2f0 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -30,10 +30,6 @@ public class ProjNode extends Node { @Override public Type compute() { Type t = ctrl()._type; - return getType(t); - } - - private Type getType(Type t) { return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 73594d2a..d0d3eb06 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -32,7 +32,7 @@ public class ReturnNode extends Node { @Override public Type compute() { - return new TypeTuple(Type.CONTROL,expr()._type); + return new TypeTuple(ctrl()._type,expr()._type); } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 17ea561a..c930fc65 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,25 +1,34 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import java.util.*; /** - * The Scope node is a purely parser helper - it tracks names to nodes with a + * The Scope node is purely a parser helper - it tracks names to nodes with a * stack of scopes. */ public class ScopeNode extends Node { /** - * Stack of lexical scopes, each scope is a symbol table - * that binds variable names to Nodes. - * The top of this stack represents current scope. + * The control is a name that binds to the currently active control + * node in the graph */ - public final Stack<HashMap<String, Integer>> _scopes = new Stack<>(); + public static final String CTRL = "$ctrl"; + public static final String ARG0 = "arg"; - // Reverse lookup for nicer graph printing - private final ArrayList<String> _rlabels = new ArrayList<>(); + /** + * Names for every input edge + */ + public final Stack<HashMap<String, Integer>> _scopes; + + + // A new ScopeNode + public ScopeNode() { + _scopes = new Stack<>(); + _type = Type.BOTTOM; + } + @Override public String label() { return "Scope"; } @@ -41,59 +50,85 @@ 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<String, Integer> 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<String,Integer> 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<String,Integer> scope = _scopes.pop(); - pop_n(scope.size()); - } + @Override public Node idealize() { return null; } - // Create a new name in the current scope + public void push() { _scopes.push(new HashMap<>()); } + public void pop() { popN(_scopes.pop().size()); } + + /** + * Create a new name in the current scope + */ public Node define( String name, Node n ) { - HashMap<String,Integer> scope = _scopes.lastElement(); - if( scope.put(name,nIns()) != null ) + HashMap<String,Integer> 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<String, Integer> 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); } } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java index 85c6cd34..e94c24e0 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -17,6 +17,7 @@ public class StartNode extends MultiNode { public StartNode(Type[] args) { super(); _args = new TypeTuple(args); + _type = _args; } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java index a063e28e..170325f0 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java @@ -32,7 +32,7 @@ public class Type { public final byte _type; public boolean is_simple() { return _type < TSIMPLE; } - private static final String[] STRS = new String[]{"BOTTOM","TOP","CONTROL"}; + private static final String[] STRS = new String[]{"Bot","Top","Ctrl"}; protected Type(byte type) { _type = type; } public static final Type BOTTOM = new Type( TBOT ); // ALL diff --git a/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java index ebfe1399..299399d2 100644 --- a/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -152,8 +152,8 @@ public class Chapter04Test { @Test public void testVarScopeNoPeephole() { - Node._disablePeephole = true; Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + Node._disablePeephole = true; ReturnNode ret = parser.parse(); Node._disablePeephole = false; assertEquals("return (1+3);", ret.print()); @@ -178,8 +178,8 @@ public class Chapter04Test { @Test public void testChapter2ParseGrammar() { - Node._disablePeephole = true; // disable peephole so we can observe full graph Parser parser = new Parser("return 1+2*3+-5;"); + Node._disablePeephole = true; // disable peephole so we can observe full graph ReturnNode ret = parser.parse(); assertEquals("return (1+((2*3)+(-5)));", ret.print()); GraphVisualizer gv = new GraphVisualizer(); diff --git a/chapter05/README.md b/chapter05/README.md index f0a59fa0..b71597a0 100644 --- a/chapter05/README.md +++ b/chapter05/README.md @@ -29,6 +29,7 @@ Here is a recap of the nodes introduced in previous chapters: | Start | Control | 1 | Start of function, now a MultiNode | | A tuple with a ctrl token and an `arg` data node | | Proj | ? | 4 | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index | | Bool | Data | 4 | Represents results of a comparison operator | Two data nodes | Result is a comparison, represented as integer value where 1=true, 0=false | +| Not | Data | 4 | Logical not | One data node | Result converts 0 to 1 and vice versa | | Return | Control | 1 | End of function | Predecessor control node and a data node for the return value of the function | Return value of the function | | Constant | Data | 1 | Represents constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | | Add | Data | 2 | Add two values | Two data nodes without restrictions on the order | Result of the add operation | 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 { * <p> * 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<ScopeNode> _allScopes = new Stack<>(); + public final Stack<ScopeNode> _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> E del(ArrayList<E> 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 <E> int find( ArrayList<E> ary, E x ) { + for( int i=0; i<ary.size(); i++ ) + if( ary.get(i)==x ) + return i; + return -1; + } +}
\ No newline at end of file diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java index f6c49abf..87304f28 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -72,7 +72,7 @@ public class AddNode extends Node { if( lhs.in(2)._type.isConstant() && t2.isConstant() ) return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); - if( lhs.in(2) instanceof PhiNode phi && phi.all_cons() && + if( lhs.in(2) instanceof PhiNode phi && phi.allCons() && // Do we have ((x + (phi cons)) + con) ? // Do we have ((x + (phi cons)) + (phi cons)) ? // Push constant up through the phi: x + (phi con0+con0 con1+con1...) @@ -80,7 +80,7 @@ public class AddNode extends Node { // Note that this is the exact reverse of Phi pulling a common op // down to reduce total op-count. We don't get in an endless push- // up push-down peephole cycle because the constants all fold first. - (t2.isConstant() || (rhs instanceof PhiNode && phi.in(0) == rhs.in(0) && rhs.all_cons()) ) ) { + (t2.isConstant() || (rhs instanceof PhiNode && phi.in(0) == rhs.in(0) && rhs.allCons()) ) ) { Node[] ns = new Node[phi.nIns()]; ns[0] = phi.in(0); // Push constant up through the phi: x + (phi con0+con0 con1+con1...) @@ -109,8 +109,8 @@ public class AddNode extends Node { if( lo._type.isConstant() ) return false; if( hi._type.isConstant() ) return true ; - if( lo instanceof PhiNode && lo.all_cons() ) return false; - if( hi instanceof PhiNode && hi.all_cons() ) return true ; + if( lo instanceof PhiNode && lo.allCons() ) return false; + if( hi instanceof PhiNode && hi.allCons() ) return true ; if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true; if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false; diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 0ba5e7b0..61259d2c 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -46,10 +46,7 @@ abstract public class BoolNode extends Node { return null; } - public static class EQNode extends BoolNode { public EQNode(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 EQNode(lhs,rhs); } } - public static class NENode extends BoolNode { public NENode(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 NENode(lhs,rhs); } } - public static class LTNode extends BoolNode { public LTNode(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 LTNode(lhs,rhs); } } - public static class LENode extends BoolNode { public LENode(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 LENode(lhs,rhs); } } - public static class GTNode extends BoolNode { public GTNode(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 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: - * <ul> - * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li> - * <li>in a future chapter we will look for a - * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a> - * to eliminate.</li> - * <li>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. </li> - * </ul> - */ - 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 extends Node> 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<Node> 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; i<n; i++ ) { - Node old_def = _inputs.remove(_inputs.size()-1); + Node old_def = _inputs.removeLast(); if( old_def != null && // If it exists and old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def @@ -252,17 +197,85 @@ public abstract class Node { /** * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> * 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 extends Node> N keep() { return addUse(null); } + // Remove bogus null. + public <N extends Node> 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: + * <ul> + * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li> + * <li>in a future chapter we will look for a + * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a> + * to eliminate.</li> + * <li>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. </li> + * </ul> + */ + 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<nIns(); i++ ) if( !(in(i)._type.isConstant()) ) return false; @@ -353,11 +366,31 @@ public abstract class Node { // Make a shallow copy (same class) of this Node, with given inputs and // empty outputs and a new Node ID. The original inputs are ignored. // Does not need to be implemented in isCFG() nodes. - Node copy(Node lhs, Node rhs) { throw Parser.TODO("Binary ops need to implement copy"); } + Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } /** * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. */ - public static void reset() { UNIQUE_ID = 1; } + public static void reset() { UNIQUE_ID = 1; _disablePeephole=false; } + + /** + * Debugging utility to find a Node by index + */ + public Node find(int nid) { return _find(new BitSet(),nid); } + private Node _find(BitSet visit, int nid) { + if( _nid==nid ) return this; + if( visit.get(_nid) ) return null; + visit.set(_nid); + for( Node def : _inputs ) + if( def!=null ) { + Node rez = def._find(visit,nid); + if( rez != null ) return rez; + } + for( Node use : _outputs ) { + Node rez = use._find(visit,nid); + if( rez != null ) return rez; + } + return null; + } } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java new file mode 100644 index 00000000..5dd6a86e --- /dev/null +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -0,0 +1,28 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +public class NotNode extends Node { + public NotNode(Node in) { super(null, in); } + + @Override public String label() { return "Not"; } + + @Override public String glabel() { return "!"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(!")); + return sb.append(")"); + } + + @Override + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 ) + return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0; + return Type.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 87c84453..716d03d9 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -22,6 +22,8 @@ public class PhiNode extends Node { return sb; } + Node region() { return in(0); } + @Override public Type compute() { return Type.BOTTOM; diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 86e3b144..b78a3e28 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -30,10 +30,6 @@ public class ProjNode extends Node { @Override public Type compute() { Type t = ctrl()._type; - return getType(t); - } - - private Type getType(Type t) { return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 354a8f8b..5d520d65 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -10,7 +10,7 @@ public class RegionNode extends Node { @Override StringBuilder _print1(StringBuilder sb) { - return sb.append("Region").append(_nid); + return sb.append(label()).append(_nid); } @Override public boolean isCFG() { return true; } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 73594d2a..d0d3eb06 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -32,7 +32,7 @@ public class ReturnNode extends Node { @Override public Type compute() { - return new TypeTuple(Type.CONTROL,expr()._type); + return new TypeTuple(ctrl()._type,expr()._type); } @Override diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 93ef54f6..543d0f83 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,25 +1,34 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import java.util.*; /** - * The Scope node is a purely parser helper - it tracks names to nodes with a + * The Scope node is purely a parser helper - it tracks names to nodes with a * stack of scopes. */ public class ScopeNode extends Node { /** - * Stack of lexical scopes, each scope is a symbol table - * that binds variable names to Nodes. - * The top of this stack represents current scope. + * The control is a name that binds to the currently active control + * node in the graph */ - public final Stack<HashMap<String, Integer>> _scopes = new Stack<>(); + public static final String CTRL = "$ctrl"; + public static final String ARG0 = "arg"; - // Reverse lookup for nicer graph printing - private final ArrayList<String> _rlabels = new ArrayList<>(); + /** + * Names for every input edge + */ + public final Stack<HashMap<String, Integer>> _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<String, Integer> 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<String,Integer> 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<String,Integer> 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<String,Integer> scope = _scopes.lastElement(); - if( scope.put(name,nIns()) != null ) + HashMap<String,Integer> 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<String, Integer> 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<String, Integer> tab : _scopes ) - dup._scopes.push(new HashMap<>(tab)); - for( int i=0; i<nIns(); i++ ) - dup.add_def(in(i)); - dup._rlabels.addAll(_rlabels); + for( HashMap<String,Integer> syms : _scopes ) + dup._scopes.push(new HashMap<>(syms)); + dup.addDef(ctrl()); // Control input is just copied + for( int i=1; i<nIns(); i++ ) + dup.addDef(in(i)); return dup; } - + /** * Merges the names whose node bindings differ, by creating Phi node for such names * The names could occur at all stack levels, but a given name can only differ in the @@ -127,10 +162,12 @@ public class ScopeNode extends Node { * @return A new node representing the merge point */ public Node mergeScopes(ScopeNode that) { - RegionNode r = (RegionNode)ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole()); - for( int i=1; i<nIns(); i++ ) + RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole()); + String[] ns = reverseNames(); + // Note that we skip i==0, which is bound to '$ctrl' + for (int i = 1; i < nIns(); i++) if( in(i) != that.in(i) ) // No need for redundant Phis - set_def(i,new PhiNode(_rlabels.get(i), r, in(i), that.in(i)).peephole()); + setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); that.kill(); // Kill merged scope return r; } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java index 85c6cd34..e94c24e0 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -17,6 +17,7 @@ public class StartNode extends MultiNode { public StartNode(Type[] args) { super(); _args = new TypeTuple(args); + _type = _args; } @Override diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java index 9898de88..9ec39373 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -40,7 +40,7 @@ public class StopNode extends Node { } public Node addReturn(Node node) { - return add_def(node); + return addDef(node); } } diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java index d8cb690b..4cee0d3c 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java @@ -32,7 +32,7 @@ public class Type { public final byte _type; public boolean is_simple() { return _type < TSIMPLE; } - private static final String[] STRS = new String[]{"BOTTOM","TOP","CONTROL"}; + private static final String[] STRS = new String[]{"Bot","Top","Ctrl"}; protected Type(byte type) { _type = type; } public static final Type BOTTOM = new Type( TBOT ); // ALL diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 5c8c7049..3037e45f 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -28,11 +28,6 @@ public class TypeInteger extends Type { public boolean isTop() { return !_is_con && _con==0; } public boolean isBot() { return !_is_con && _con==1; } - @Override - public String toString() { - return _print(new StringBuilder()).toString(); - } - @Override public StringBuilder _print(StringBuilder sb) { if (isTop()) return sb.append("IntTop"); diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index a991a856..3db639cf 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -16,7 +16,7 @@ public class TypeTuple extends Type { @Override public StringBuilder _print(StringBuilder sb) { - sb.append("[ "); + sb.append("["); for( Type t : _types ) t._print(sb).append(","); sb.setLength(sb.length()-1); diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java index e40136bd..e914f7c5 100644 --- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -12,7 +12,8 @@ public class Chapter05Test { @Test public void testChapter5IfStmt() { - Parser parser = new Parser(""" + Parser parser = new Parser( +""" int a = 1; if (arg == 1) a = arg+2; @@ -28,7 +29,8 @@ return a;"""); @Test public void testChapter5Test() { - Parser parser = new Parser(""" + Parser parser = new Parser( +""" int c = 3; int b = 2; if (arg == 1) { @@ -42,7 +44,8 @@ return c;""", TypeInteger.BOT); @Test public void testChapter5Return2() { - Parser parser = new Parser(""" + Parser parser = new Parser( +""" if( arg==1 ) return 3; else @@ -54,7 +57,8 @@ else @Test public void testChapter5IfMergeB() { - Parser parser = new Parser(""" + Parser parser = new Parser( +""" int a=arg+1; int b=0; if( arg==1 ) @@ -68,7 +72,8 @@ return a+b;"""); @Test public void testChapter5IfMerge2() { - Parser parser = new Parser(""" + Parser parser = new Parser( +""" int a=arg+1; int b=arg+2; if( arg==1 ) @@ -82,7 +87,8 @@ return a+b;"""); @Test public void testChapter5Merge3() { - Parser parser = new Parser(""" + Parser parser = new Parser( +""" int a=1; if( arg==1 ) if( arg==2 ) @@ -101,7 +107,8 @@ return a; @Test public void testChapter5Merge4() { - Parser parser = new Parser(""" + Parser parser = new Parser( +""" int a=0; int b=0; if( arg ) @@ -116,7 +123,8 @@ return arg+a+b; @Test public void testChapter5Merge5() { - Parser parser = new Parser(""" + Parser parser = new Parser( +""" int a=arg==2; if( arg==1 ) { @@ -333,8 +341,8 @@ return a;"""); @Test public void testVarScopeNoPeephole() { - Node._disablePeephole = true; Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + Node._disablePeephole = true; StopNode ret = parser.parse(); Node._disablePeephole = false; assertEquals("return (1+3);", ret.print()); @@ -359,8 +367,8 @@ return a;"""); @Test public void testChapter2ParseGrammar() { - Node._disablePeephole = true; // disable peephole so we can observe full graph Parser parser = new Parser("return 1+2*3+-5;"); + Node._disablePeephole = true; // disable peephole so we can observe full graph StopNode ret = parser.parse(); assertEquals("return (1+((2*3)+(-5)));", ret.print()); GraphVisualizer gv = new GraphVisualizer(); diff --git a/chapter06/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter06/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index c1c1c4c9..704d4802 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter06/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"); @@ -207,29 +207,24 @@ public class GraphVisualizer { * Finds all nodes in the graph. */ private Collection<Node> findAll(Parser parser) { - final StartNode start = Parser.START; final HashMap<Integer, Node> all = new HashMap<>(); - for( Node n : start._outputs ) + for( Node n : Parser.START._outputs ) + walk(all, n); + for( Node n : parser._scope._inputs ) walk(all, n); - // Scan symbol tables - for( HashMap<String,Integer> scope : parser._scope._scopes ) - for (Integer i : scope.values()) - walk(all, parser._scope.in(i)); return all.values(); } /** * Walk a subgraph and populate distinct nodes in the all list. */ - private void walk(HashMap<Integer, Node> all, Node n) { + private void walk(HashMap<Integer,Node> all, Node n) { if(n == null ) return; if (all.get(n._nid) != null) return; // Been there, done that all.put(n._nid, n); for (Node c : n._inputs) - if (c != null) - walk(all, c); - for (Node c : n._outputs) - if (c != null) - walk(all, c); + walk(all, c); + for( Node c : n._outputs ) + walk(all, c); } } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java index 1bfe5b0d..81cb9e57 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java @@ -39,7 +39,7 @@ public class Parser { * <p> * We keep a list of all ScopeNodes so that we can show them in graphs. * @see #parseIf() - * @see #_allScopes + * @see #_xScopes */ public ScopeNode _scope; @@ -60,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<ScopeNode> _allScopes = new Stack<>(); + public final Stack<ScopeNode> _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,29 +79,30 @@ public class Parser { 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.ctrl(new ProjNode(START, 0, ScopeNode.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(); - STOP.peephole(); - 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 * @@ -115,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 +161,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 +171,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 +267,12 @@ public class Parser { */ private Node parseComparison() { var lhs = parseAddition(); - if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole(); - if (match("!=")) return new NotNode(new BoolNode.EQNode(lhs, parseComparison()).peephole()).peephole(); - if (match("<" )) return new BoolNode.LTNode(lhs, parseComparison()).peephole(); - if (match("<=")) return new BoolNode.LENode(lhs, parseComparison()).peephole(); - if (match(">" )) return new BoolNode.LTNode(parseComparison(), lhs).peephole(); - if (match(">=")) return new BoolNode.LENode(parseComparison(), lhs).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; } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/Utils.java b/chapter06/src/main/java/com/seaofnodes/simple/Utils.java index c79d96f0..4d663c25 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/Utils.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/Utils.java @@ -1,6 +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> E del(ArrayList<E> 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 <E> int find( ArrayList<E> ary, E x ) { + for( int i=0; i<ary.size(); i++ ) + if( ary.get(i)==x ) + return i; + return -1; + } }
\ No newline at end of file diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java index b29fb92c..5ef9c94a 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -128,7 +128,7 @@ public class AddNode extends Node { } static PhiNode pcon(Node op) { - return op instanceof PhiNode phi && phi.all_cons() ? phi : null; + return op instanceof PhiNode phi && phi.allCons() ? phi : null; } // Compare two off-spline nodes and decide what order they should be in. @@ -140,8 +140,8 @@ public class AddNode extends Node { if( lo._type.isConstant() ) return false; if( hi._type.isConstant() ) return true ; - if( lo instanceof PhiNode && lo.all_cons() ) return false; - if( hi instanceof PhiNode && hi.all_cons() ) return true ; + if( lo instanceof PhiNode && lo.allCons() ) return false; + if( hi instanceof PhiNode && hi.allCons() ) return true ; if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true; if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false; diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java index bbcc742d..4eeef873 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -52,7 +52,7 @@ abstract public class BoolNode extends Node { return null; } - public static class EQNode extends BoolNode { public EQNode(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 EQNode(lhs,rhs); } } - public static class LTNode extends BoolNode { public LTNode(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 LTNode(lhs,rhs); } } - public static class LENode extends BoolNode { public LENode(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 LENode(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/chapter06/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index bc92b540..ba6f55d7 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter06/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; } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java index 36e4896d..f5e58284 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java @@ -52,7 +52,7 @@ public abstract class Node { * parsing where we do not have the whole program, and also peepholes * change the CFG incrementally. * <p> - * See {@link https://en.wikipedia.org/wiki/Dominator_(graph_theory)} + * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ int _idepth; @@ -81,7 +81,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 @@ -115,6 +123,8 @@ 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; } @@ -122,67 +132,6 @@ public abstract class Node { 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: - * <ul> - * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li> - * <li>in a future chapter we will look for a - * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a> - * to eliminate.</li> - * <li>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. </li> - * </ul> - */ - 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; - } - - - /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing * the corresponding <em>use->def</em> edge. This may make the original * <em>def</em> go dead. This function is co-recursive with {@link #kill}. @@ -196,9 +145,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 @@ -212,7 +161,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; } // Remove the numbered input, compressing the inputs in-place. This @@ -223,10 +172,7 @@ public abstract class Node { if( old_def != null && // If the old def exists, remove a def->use edge old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def - // Set the new_def over the old (killed) edge - int last = nIns()-1; - _inputs.set(idx,in(last)); - _inputs.remove(last); + Utils.del(_inputs, idx); } /** @@ -236,7 +182,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 @@ -247,29 +193,20 @@ public abstract class Node { // Breaks the edge invariants, used temporarily protected <N extends Node> N addUse(Node n) { _outputs.add(n); return (N)this; } - // Shortcuts to stop DCE mid-parse - public <N extends Node> N keep() { return addUse(null); } - public Node unkeep() { delUse(null); return 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<Node> 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; i<n; i++ ) { - Node old_def = _inputs.remove(_inputs.size()-1); + Node old_def = _inputs.removeLast(); if( old_def != null && // If it exists and old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def @@ -279,17 +216,85 @@ public abstract class Node { /** * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> * 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 extends Node> N keep() { return addUse(null); } + // Remove bogus null. + public <N extends Node> 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: + * <ul> + * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li> + * <li>in a future chapter we will look for a + * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a> + * to eliminate.</li> + * <li>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. </li> + * </ul> + */ + 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 @@ -357,7 +362,7 @@ public abstract class Node { public abstract Node idealize(); - // ----------------------- + // ------------------------------------------------------------------------ // Peephole utilities // Swap inputs without letting either input go dead during the swap. @@ -370,7 +375,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<nIns(); i++ ) if( !(in(i)._type.isConstant()) ) return false; @@ -394,5 +399,25 @@ public abstract class Node { * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. */ - public static void reset() { UNIQUE_ID = 1; } + public static void reset() { UNIQUE_ID = 1; _disablePeephole=false; } + + /** + * Debugging utility to find a Node by index + */ + public Node find(int nid) { return _find(new BitSet(),nid); } + private Node _find(BitSet visit, int nid) { + if( _nid==nid ) return this; + if( visit.get(_nid) ) return null; + visit.set(_nid); + for( Node def : _inputs ) + if( def!=null ) { + Node rez = def._find(visit,nid); + if( rez != null ) return rez; + } + for( Node use : _outputs ) { + Node rez = use._find(visit,nid); + if( rez != null ) return rez; + } + return null; + } } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java index a5750922..d435ea01 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -34,13 +34,8 @@ public class PhiNode extends Node { @Override public Node idealize() { - // Remove a "junk" Phi: Phi(x,x) is just x - if( same_inputs() ) - return in(1); - - // If only 1 of our input values have live control - // then return that as phi is dead - Node live = singleLiveInput(); + // If we have only a single unique input, become it. + Node live = singleUniqueInput(); if (live != null) return live; @@ -72,25 +67,15 @@ public class PhiNode extends Node { return true; } - private boolean same_inputs() { - for( int i=2; i<nIns(); i++ ) - if( in(1) != in(i) ) - return false; - return true; - } - /** - * If only 1 of the inputs is live then return it + * If only single unique input, return it */ - private Node singleLiveInput() { + private Node singleUniqueInput() { Node live = null; - for( int i=1; i<nIns(); i++ ) - // The control type is in the region - if( region().in(i)._type != Type.XCONTROL ) - if (live == null) - live = in(i); - else - return null; + for( int i=1; i<nIns(); i++ ) + if( region().in(i)._type != Type.XCONTROL && in(i) != this ) + if( live == null || live == in(i) ) live = in(i); + else return null; return live; } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 424a1e9b..ef957507 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -30,10 +30,6 @@ public class ProjNode extends Node { @Override public Type compute() { Type t = ctrl()._type; - return getType(t); - } - - private Type getType(Type t) { return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java index d3fd7745..104735d5 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -11,7 +11,7 @@ public class RegionNode extends Node { @Override StringBuilder _print1(StringBuilder sb) { - return sb.append("Region").append(_nid); + return sb.append(label()).append(_nid); } @Override public boolean isCFG() { return true; } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 96564f3b..76fe98b9 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -5,7 +5,7 @@ import com.seaofnodes.simple.type.Type; import java.util.*; /** - * The Scope node is a purely parser helper - it tracks names to nodes with a + * The Scope node is purely a parser helper - it tracks names to nodes with a * stack of scopes. */ public class ScopeNode extends Node { @@ -15,16 +15,20 @@ public class ScopeNode extends Node { * node in the graph */ public static final String CTRL = "$ctrl"; + public static final String ARG0 = "arg"; /** - * Stack of lexical scopes, each scope is a symbol table - * that binds variable names to Nodes. - * The top of this stack represents current scope. + * Names for every input edge */ - public final Stack<HashMap<String, Integer>> _scopes = new Stack<>(); + public final Stack<HashMap<String, Integer>> _scopes; - // Reverse lookup for nicer graph printing - private final ArrayList<String> _rlabels = new ArrayList<>(); + + // A new ScopeNode + public ScopeNode() { + _scopes = new Stack<>(); + _type = Type.BOTTOM; + } + @Override public String label() { return "Scope"; } @@ -46,42 +50,74 @@ 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<String, Integer> 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<String,Integer> 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<String,Integer> scope = _scopes.pop(); - pop_n(scope.size()); - } + @Override public Node idealize() { return null; } - // Create a new name in the current scope + public void push() { _scopes.push(new HashMap<>()); } + public void pop() { popN(_scopes.pop().size()); } + + /** + * Create a new name in the current scope + */ public Node define( String name, Node n ) { - HashMap<String,Integer> scope = _scopes.lastElement(); - if( scope.put(name,nIns()) != null ) + HashMap<String,Integer> 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(CTRL)==in(0); return in(0); } + public Node ctrl() { return in(0); } /** * The ctrl of a ScopeNode is always bound to the currently active @@ -93,29 +129,7 @@ public class ScopeNode extends Node { * * @return Node that was bound */ - public Node ctrl(Node n) { - if (nIns() == 0) { - // The first time a scope is created we do not have the name binding - // for '$ctrl' but after that we expect to find the name already bound - assert lookup(CTRL) == null; - define(CTRL, n); - } - else assert lookup(CTRL) == in(0); - set_def(0,n); - return n; - } - - - // 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<String, Integer> 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; - } + public Node ctrl(Node n) { return setDef(0,n); } /** * Duplicate a ScopeNode; including all levels, up to Nodes. So this is @@ -126,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<String, Integer> tab : _scopes ) - dup._scopes.push(new HashMap<>(tab)); - for( int i=0; i<nIns(); i++ ) - dup.add_def(in(i)); - dup._rlabels.addAll(_rlabels); + for( HashMap<String,Integer> syms : _scopes ) + dup._scopes.push(new HashMap<>(syms)); + dup.addDef(ctrl()); // Control input is just copied + for( int i=1; i<nIns(); i++ ) + dup.addDef(in(i)); return dup; } - + /** * Merges the names whose node bindings differ, by creating Phi node for such names * The names could occur at all stack levels, but a given name can only differ in the @@ -149,10 +163,11 @@ public class ScopeNode extends Node { */ public Node mergeScopes(ScopeNode that) { RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); + String[] ns = reverseNames(); // Note that we skip i==0, which is bound to '$ctrl' for (int i = 1; i < nIns(); i++) - if (in(i) != that.in(i)) // No need for redundant Phis - set_def(i, new PhiNode(_rlabels.get(i), r, in(i), that.in(i)).peephole()); + if( in(i) != that.in(i) ) // No need for redundant Phis + setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); that.kill(); // Kill merged scope return r.unkeep().peephole(); } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java index 8cff25bd..fd0f6c18 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -17,6 +17,7 @@ public class StartNode extends MultiNode { public StartNode(Type[] args) { super(); _args = new TypeTuple(args); + _type = _args; } @Override diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/StopNode.java index f17c7ec7..c8056fbe 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -45,7 +45,7 @@ public class StopNode extends Node { } public Node addReturn(Node node) { - return add_def(node); + return addDef(node); } } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter06/src/main/java/com/seaofnodes/simple/type/Type.java index 78908375..f88403a5 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/type/Type.java @@ -33,7 +33,7 @@ public class Type { public final byte _type; public boolean is_simple() { return _type < TSIMPLE; } - private static final String[] STRS = new String[]{"BOTTOM","TOP","CONTROL","~CONTROL"}; + private static final String[] STRS = new String[]{"Bot","Top","Ctrl","~Ctrl"}; protected Type(byte type) { _type = type; } public static final Type BOTTOM = new Type( TBOT ); // ALL diff --git a/chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 2e6152a8..f8c3b3c8 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -16,7 +16,7 @@ public class TypeTuple extends Type { @Override public StringBuilder _print(StringBuilder sb) { - sb.append("[ "); + sb.append("["); for( Type t : _types ) t._print(sb).append(","); sb.setLength(sb.length()-1); diff --git a/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 7767b203..d0e55cc7 100644 --- a/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -624,8 +624,8 @@ return a;"""); @Test public void testVarScopeNoPeephole() { - Node._disablePeephole = true; Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + Node._disablePeephole = true; StopNode ret = parser.parse(); Node._disablePeephole = false; assertEquals("return (1+3);", ret.print()); @@ -650,8 +650,8 @@ return a;"""); @Test public void testChapter2ParseGrammar() { - Node._disablePeephole = true; // disable peephole so we can observe full graph Parser parser = new Parser("return 1+2*3+-5;"); + Node._disablePeephole = true; // disable peephole so we can observe full graph StopNode ret = parser.parse(); assertEquals("return (1+((2*3)+(-5)));", ret.print()); GraphVisualizer gv = new GraphVisualizer(); diff --git a/chapter07/README.md b/chapter07/README.md index c6bcdee4..3e6a7692 100644 --- a/chapter07/README.md +++ b/chapter07/README.md @@ -70,7 +70,7 @@ created until we complete parsing the loop body. This is because our phis are no ## Detailed Steps 1. We start by creating a new subclass of `Region`, the `Loop`. The `Loop` gets two control inputs, - the first one is the entry point, i.e. the current binding to `$ctrl`, and second one (`null`) is a placeholder for the back edge that is + the first is the entry point, i.e. the current binding to `$ctrl`, and second (`null`) is a placeholder for the back edge that is set after loop is parsed. The absence of a back edge is used as an indicator to switch off peepholes of the region and associated phis. @@ -94,7 +94,7 @@ created until we complete parsing the loop body. This is because our phis are no ```java // boolean loop=true if this is a loop region - String[] reverse = reverse_names(); + String[] names = reverseNames(); // Get the variable names dup.add_def(ctrl()); // Control input is just copied for( int i=1; i<nIns(); i++ ) { if ( !loop ) { dup.add_def(in(i)); } @@ -102,7 +102,7 @@ created until we complete parsing the loop body. This is because our phis are no // Loop region // Create a phi node with second input as null - to be filled in // by endLoop() below - dup.add_def(new PhiNode(reverse[i], ctrl(), in(i), null).peephole()); + dup.add_def(new PhiNode(names[i], ctrl(), in(i), null).peephole()); // Ensure our node has the same phi in case we created one set_def(i, dup.in(i)); } @@ -124,8 +124,9 @@ created until we complete parsing the loop body. This is because our phis are no Node ifF = new ProjNode(ifNode, 1, "False").peephole(); ``` -4. We set the control token to the `True` projection node `ifT`, but before that we make another clone of - the current scope. +4. We make another clone of the current scope. This will be the exit scope that will live after the loop ends, + therefore `$ctrl` in the exit scope is set to the `False` projection. + The exit scope captures any side effects of the loop's predicate. ```java // The exit scope, accounting for any side effects in the predicate @@ -133,9 +134,6 @@ created until we complete parsing the loop body. This is because our phis are no exit.ctrl(ifF); ``` - The new scope is saved as the exit scope that will live after the loop ends, therefore `$ctrl` in the exit scope is - set to the `False` projection. The exit scope captures any side effects of the loop's predicate. - 5. We now set the control to the `True` projection and parse the loop body. ```java @@ -171,7 +169,13 @@ created until we complete parsing the loop body. This is because our phis are no ``` 7. Finally, both the original scope (head) we started with, and the duplicate created for the body are killed. - At exit the false control is the current control, and exit scope is set as the current scope. + At exit the false control is the current control (step 4), and exit scope is set as the current scope. + + ```java + // At exit the false control is the current control, and + // the scope is the exit scope after the exit test. + return (_scope = exit); + ``` ### Visualization diff --git a/chapter07/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter07/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index ce3522bc..64ffc771 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -52,7 +52,6 @@ public class GraphVisualizer { nodes(sb, all); // Now the scopes, in a cluster no edges - scope(sb,parser._scope ); for( ScopeNode scope : parser._xScopes ) scope( sb, scope ); @@ -60,7 +59,6 @@ public class GraphVisualizer { nodeEdges(sb, all); // Walk the active Scope edges - scopeEdges( sb, parser._scope ); for( ScopeNode scope : parser._xScopes ) scopeEdges( sb, scope ); diff --git a/chapter07/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter07/src/main/java/com/seaofnodes/simple/IRPrinter.java index dc6d9f4f..2a6dbefd 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -24,16 +24,16 @@ public class IRPrinter { Node n = rpos.get(i); if( n.isCFG() || n.isMultiHead() ) { if( !gap ) sb.append("\n"); // Blank before multihead - n._print_line(sb); // Print head + n._printLine(sb); // Print head while( --i >= 0 ) { Node t = rpos.get(i); if( !t.isMultiTail() ) { i++; break; } - t._print_line(sb); + t._printLine(sb); } sb.append("\n"); // Blank after multitail gap = true; } else { - n._print_line( sb ); + n._printLine( sb ); gap = false; } } diff --git a/chapter07/src/main/java/com/seaofnodes/simple/Parser.java b/chapter07/src/main/java/com/seaofnodes/simple/Parser.java index 99594c95..c3972be9 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/Parser.java @@ -87,12 +87,14 @@ public class Parser { public StopNode parse() { return parse(false); } public StopNode parse(boolean show) { + _xScopes.push(_scope); // Enter a new scope for the initial control and arguments _scope.push(); _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(); @@ -148,16 +150,23 @@ public class Parser { private Node parseWhile() { require("("); - // Loop region has two control inputs, the first one is the entry - // point, and second one is back edge that is set after loop is parsed + // Loop region has two control inputs, the first is the entry + // point, and second is back edge that is set after loop is parsed // (see end_loop() call below). Note that the absence of back edge is // used as an indicator to switch off peepholes of the region and // associated phis. - - ctrl(new LoopNode(ctrl(),null).peephole()); - ScopeNode head = _xScopes.push(_scope).keep(); // Save the current scope as the loop head - // Make a new Scope for the body. - _scope = _scope.dup(true); + + ctrl(new LoopNode(ctrl(),null).peephole()); // Note we set back edge to null here + + // At loop head, we clone the current Scope (this includes all + // names in every nesting level within the Scope). + // We create phis eagerly for all the names we find, see dup(). + + // Save the current scope as the loop head + ScopeNode head = _xScopes.push(_scope).keep(); + // Clone the head Scope to create a new Scope for the body. + // Create phis eagerly as part of cloning + _scope = _scope.dup(true); // The true argument triggers creating phis // Parse predicate var pred = require(parseExpression(), ")"); @@ -167,21 +176,31 @@ public class Parser { Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); ifNode.unkeep(); Node ifF = new ProjNode(ifNode, 1, "False").peephole(); - // The exit scope, accounting for any side effects in the predicate + + // Clone the body Scope to create the exit Scope + // which accounts for any side effects in the predicate + // The exit Scope will be the final scope after the loop, + // And its control input is the False branch of the loop predicate + // Note that body Scope is still our current scope var exit = _scope.dup(); _xScopes.push(exit); exit.ctrl(ifF); // Parse the true side, which corresponds to loop body + // Our current scope is the body Scope ctrl(ifT); // set ctrl token to ifTrue projection parseStatement(); // Parse loop body - // The true branch loops back, so whatever is current control gets - // added to head loop as input + // The true branch loops back, so whatever is current control (_scope.ctrl) gets + // added to head loop as input. endLoop() updates the head scope, + // and goes through all the phis that were created earlier. For each + // phi, it sets the second input to the corresponding input from the back edge. + // If the phi is redundant, it is replaced by its sole input. head.endLoop(_scope, exit); head.unkeep().kill(); - _xScopes.pop(); - _xScopes.pop(); // Discard pushed from graph display + + _xScopes.pop(); // Cleanup + _xScopes.pop(); // Cleanup // At exit the false control is the current control, and // the scope is the exit scope after the exit test. diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/AddNode.java index 85d7b20e..d23fa7c5 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -5,9 +5,7 @@ import com.seaofnodes.simple.type.*; import java.util.BitSet; public class AddNode extends Node { - public AddNode(Node lhs, Node rhs) { - super(null, lhs, rhs); - } + public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @Override public String label() { return "Add"; } @@ -132,7 +130,7 @@ public class AddNode extends Node { } static PhiNode pcon(Node op) { - return op instanceof PhiNode phi && phi.all_cons() ? phi : null; + return op instanceof PhiNode phi && phi.allCons() ? phi : null; } // Compare two off-spline nodes and decide what order they should be in. @@ -144,8 +142,8 @@ public class AddNode extends Node { if( lo._type.isConstant() ) return false; if( hi._type.isConstant() ) return true ; - if( lo instanceof PhiNode && lo.all_cons() ) return false; - if( hi instanceof PhiNode && hi.all_cons() ) return true ; + if( lo instanceof PhiNode && lo.allCons() ) return false; + if( hi instanceof PhiNode && hi.allCons() ) return true ; if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true; if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false; diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java index fcc8df85..4cd1b3d2 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java @@ -117,7 +117,7 @@ public abstract class Node { // Print a node on 1 line, columnar aligned, as: // NNID NNAME DDEF DDEF [[ UUSE UUSE ]] TYPE // 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt - public void _print_line( StringBuilder sb ) { + public void _printLine(StringBuilder sb ) { sb.append("%4d %-7.7s ".formatted(_nid,label())); if( _inputs==null ) { sb.append("DEAD\n"); @@ -177,7 +177,7 @@ public abstract class Node { * @param new_def the new definition * @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 @@ -212,7 +212,7 @@ public abstract class Node { * @param new_def the new definition, appended to the end of existing definitions * @return new_def for flow coding */ - public 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 @@ -234,7 +234,7 @@ public abstract class Node { // 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; i<n; i++ ) { Node old_def = _inputs.removeLast(); if( old_def != null && // If it exists and @@ -246,11 +246,11 @@ public abstract class Node { /** * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> * 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 } @@ -419,7 +419,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<nIns(); i++ ) if( !(in(i)._type.isConstant()) ) return false; diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 202dbe37..e6cf338b 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -93,9 +93,9 @@ public class PhiNode extends Node { } @Override - boolean all_cons() { + boolean allCons() { if( !(region() instanceof RegionNode r) || r.inProgress() ) return false; - return super.all_cons(); + return super.allCons(); } } diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index cc6af152..b5ce997b 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -35,7 +35,7 @@ public class ScopeNode extends Node { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("Scope[ "); - String[] names = reverse_names(); + String[] names = reverseNames(); for( int j=0; j<nIns(); j++ ) { sb.append(names[j]).append(":"); Node n = in(j); @@ -45,8 +45,14 @@ public class ScopeNode extends Node { return sb.append("]"); } - // Expensive... - public String[] reverse_names() { + /** + * 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<String,Integer> syms : _scopes ) for( String name : syms.keySet() ) @@ -59,29 +65,50 @@ public class ScopeNode extends Node { @Override public Node idealize() { return null; } public void push() { _scopes.push(new HashMap<>()); } - public void pop() { pop_n(_scopes.pop().size()); } - - // Create a new name in the current scope + public void pop() { popN(_scopes.pop().size()); } + + /** + * Create a new name in the current scope + */ public Node define( String name, Node n ) { HashMap<String,Integer> syms = _scopes.lastElement(); if( syms.put(name,nIns()) != null ) return null; // Double define - return add_def(n); + return addDef(n); } - - // Lookup a name. It is recursive to support lazy Phis on loops (coming in chapter 8). - public Node lookup(String name) { return update(name,null,_scopes.size()-1); } - // If the name is present in any scope, then redefine else null - public Node update(String name, Node n) { return update(name,n,_scopes.size()-1); } - // Both recursive lookup and update. - private Node update( String name, Node n, int i ) { - if( i<0 ) return null; // Missed in all scopes, not found - var syms = _scopes.get(i); + /** + * 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,i-1); // Missed in this scope, recursively look + 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 - return n==null ? old : set_def(idx,n); + // 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() { return in(0); } @@ -96,7 +123,7 @@ public class ScopeNode extends Node { * * @return Node that was bound */ - public Node ctrl(Node n) { return set_def(0,n); } + public Node ctrl(Node n) { return setDef(0,n); } /** * Duplicate a ScopeNode; including all levels, up to Nodes. So this is @@ -115,16 +142,16 @@ public class ScopeNode extends Node { // 3) Ensure that the order of defs is the same to allow easy merging for( HashMap<String,Integer> syms : _scopes ) dup._scopes.push(new HashMap<>(syms)); - String[] reverse = reverse_names(); - dup.add_def(ctrl()); // Control input is just copied + String[] names = reverseNames(); // Get the variable names + dup.addDef(ctrl()); // Control input is just copied for( int i=1; i<nIns(); i++ ) { - if ( !loop ) { dup.add_def(in(i)); } + if ( !loop ) { dup.addDef(in(i)); } else { // Create a phi node with second input as null - to be filled in // by endLoop() below - dup.add_def(new PhiNode(reverse[i], ctrl(), in(i), null).peephole()); + dup.addDef(new PhiNode(names[i], ctrl(), in(i), null).peephole()); // Ensure our node has the same phi in case we created one - set_def(i, dup.in(i)); + setDef(i, dup.in(i)); } } return dup; @@ -140,11 +167,11 @@ public class ScopeNode extends Node { */ public Node mergeScopes(ScopeNode that) { RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); - String[] ns = reverse_names(); + String[] ns = reverseNames(); // Note that we skip i==0, which is bound to '$ctrl' for (int i = 1; i < nIns(); i++) if( in(i) != that.in(i) ) // No need for redundant Phis - set_def(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); + setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); that.kill(); // Kill merged scope return r.unkeep().peephole(); } @@ -154,11 +181,11 @@ public class ScopeNode extends Node { public void endLoop(ScopeNode back, ScopeNode exit ) { Node ctrl = ctrl(); assert ctrl instanceof LoopNode loop && loop.inProgress(); - ctrl.set_def(2,back.ctrl()); + ctrl.setDef(2,back.ctrl()); for( int i=1; i<nIns(); i++ ) { PhiNode phi = (PhiNode)in(i); assert phi.region()==ctrl && phi.in(2)==null; - phi.set_def(2,back.in(i)); + phi.setDef(2,back.in(i)); // Do an eager useless-phi removal Node in = phi.peephole(); if( in != phi ) diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/StopNode.java index c4375771..a0aacf2b 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -47,7 +47,7 @@ public class StopNode extends Node { } public Node addReturn(Node node) { - return add_def(node); + return addDef(node); } } |