From 499906b94893cb808df96810d46441857ae432d4 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Thu, 7 Dec 2023 09:26:54 +0000 Subject: Backport some of the code refactoring to previous chapters (#50) * #44 Revise docs and comments * #44 Add starting scope to xScopes * #44 back some of the code refactoring port to previous chapters * #44 add_def should not be public * #44 add_def should not be public. Rename method names so that they are camelcase --- chapter03/README.md | 20 +-- .../main/java/com/seaofnodes/simple/Parser.java | 13 +- .../src/main/java/com/seaofnodes/simple/Utils.java | 39 ++++++ .../main/java/com/seaofnodes/simple/node/Node.java | 147 +++++++++++++-------- .../java/com/seaofnodes/simple/node/ScopeNode.java | 125 ++++++++++++------ .../main/java/com/seaofnodes/simple/type/Type.java | 2 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 4 +- 7 files changed, 227 insertions(+), 123 deletions(-) create mode 100644 chapter03/src/main/java/com/seaofnodes/simple/Utils.java (limited to 'chapter03') 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 del(ArrayList array, int i) { + if ( i >= 0 && i < array.size() ) { + E tmp = array.get(i); + E last = array.removeLast(); + if (i < array.size()) array.set(i, last); + return tmp; + } + return null; + } + + /** + * Search a list for an element by reference + * + * @param ary List to search in + * @param x Object to be searched + * @return >= 0 on success, -1 on failure + */ + public static int find( ArrayList ary, E x ) { + for( int i=0; i - *
  • if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}
    • - *
  • in a future chapter we will look for a - * Common Subexpression - * to eliminate.
    • - *
  • we ask the Node for a better replacement (again, none enabled in this chapter)
    • - * - */ - 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 def into a Node. Keeps the edges correct, by removing * the corresponding use->def edge. This may make the original * def go dead. This function is co-recursive with {@link #kill}. + *

    + + * This method is the normal path for altering a Node, because it does the + * proper default edge maintenance. It also immediately 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 addUse(Node n) { _outputs.add(n); return (N)this; } // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place. // Return true if the output list is empty afterward. // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { - ArrayList outs = _outputs; - int lidx = outs.size()-1; // Last index - // This 1-line hack compresses an element out of an ArrayList - // without having to copy the contents. The last element is - // stuffed over the deleted element, and then the size is reduced. - outs.set(outs.indexOf(use),outs.get(lidx)); - outs.remove(lidx); // Reduce ArrayList size without copying anything - return lidx==0; + Utils.del(_outputs, Utils.find(_outputs, use)); + return _outputs.size() == 0; } // Shortcut for "popping" n nodes. A "pop" is basically a // set_def(last,null) followed by lowering the nIns() count. - void pop_n(int n) { + void popN(int n) { for( int i=0; iuses, by setting all of its defs * to null. This may recursively kill more Nodes and is basically dead - * code elimination. This function is co-recursive with {@link #pop_n}. + * code elimination. This function is co-recursive with {@link #popN}. */ public void kill( ) { assert isUnused(); // Has no uses, so it is dead - pop_n(nIns()); // Set all inputs to null, recursively killing unused Nodes + popN(nIns()); // Set all inputs to null, recursively killing unused Nodes _type=null; // Flag as dead assert isDead(); // Really dead now } // Mostly used for asserts and printing. boolean isDead() { return isUnused() && nIns()==0 && _type==null; } + /** + * We allow disabling peephole opt so that we can observe the + * full graph, vs the optimized graph. + */ + public static boolean _disablePeephole = false; + + /** + * Try to peephole at this node and return a better replacement Node if + * possible. We compute a {@link Type} and then check and replace: + *

      + *
    • if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}
      • + *
    • in a future chapter we will look for a + * Common Subexpression + * to eliminate.
      • + *
    • we ask the Node for a better replacement (again, none enabled in this chapter)
      • + *
    + */ + 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> _scopes = new Stack<>(); + public final Stack> _scopes; - // Reverse lookup for nicer graph printing - private final ArrayList _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 push() { - return _scopes.push(new HashMap<>()); + /** + * Recover the names for all variable bindings. + * The result is an array of names that is aligned with the + * inputs to the Node. + * + * This is an expensive operation. + */ + public String[] reverseNames() { + String[] names = new String[nIns()]; + for( HashMap syms : _scopes ) + for( String name : syms.keySet() ) + names[syms.get(name)] = name; + return names; } + + @Override public Type compute() { return Type.BOTTOM; } - // Remove the current lexical scope, killing all unused nodes. - public void pop() { - HashMap scope = _scopes.pop(); - pop_n(scope.size()); - } + @Override public Node idealize() { return null; } - // 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 scope = _scopes.lastElement(); - if( scope.put(name,nIns()) != null ) + HashMap syms = _scopes.lastElement(); + if( syms.put(name,nIns()) != null ) return null; // Double define - _rlabels.add(name); - return add_def(n); + return addDef(n); } - - // Lookup a name in all scopes - public Node lookup(String name) { - for (int i = _scopes.size() - 1; i >= 0; i--) { - var idx = _scopes.get(i).get(name); - if (idx != null) return in(idx); - } - return null; + /** + * Lookup a name in all scopes starting from most deeply nested. + * + * @param name Name to be looked up + * @see #update(String, Node, int) + */ + public Node lookup( String name ) { return update(name,null,_scopes.size()-1); } + /** + * If the name is present in any scope, then redefine else null + * + * @param name Name being redefined + * @param n The node to bind to the name + */ + public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); } + /** + * Both recursive lookup and update. + * + * A shared implementation allows us to create lazy phis both during + * lookups and updates; the lazy phi creation is part of chapter 8. + * + * @param name Name whose binding is being updated or looked up + * @param n If null, do a lookup, else update binding + * @param nestingLevel The starting nesting level + * @return node being looked up, or the one that was updated + */ + private Node update( String name, Node n, int nestingLevel ) { + if( nestingLevel<0 ) return null; // Missed in all scopes, not found + var syms = _scopes.get(nestingLevel); // Get the symbol table for nesting level + var idx = syms.get(name); + if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope + Node old = in(idx); + // If n is null we are looking up rather than updating, hence return existing value + return n==null ? old : setDef(idx,n); } - - // If the name is present in any scope, then redefine - public Node update(String name, Node n) { - for (int i = _scopes.size() - 1; i >= 0; i--) { - HashMap scope = _scopes.get(i); - Integer idx = scope.get(name); - if (idx != null) // Found prior def - return set_def(idx,n); // Update def in scope - } - return null; - } + 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(); -- cgit v1.2.3