diff options
Diffstat (limited to 'chapter02')
| -rw-r--r-- | chapter02/README.md | 14 | ||||
| -rw-r--r-- | chapter02/src/main/java/com/seaofnodes/simple/Parser.java | 1 | ||||
| -rw-r--r-- | chapter02/src/main/java/com/seaofnodes/simple/Utils.java | 39 | ||||
| -rw-r--r-- | chapter02/src/main/java/com/seaofnodes/simple/node/Node.java | 117 | ||||
| -rw-r--r-- | chapter02/src/main/java/com/seaofnodes/simple/type/Type.java | 2 |
5 files changed, 113 insertions, 60 deletions
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 |