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 --- .../main/java/com/seaofnodes/simple/Parser.java | 1 - .../src/main/java/com/seaofnodes/simple/Utils.java | 39 +++++++ .../main/java/com/seaofnodes/simple/node/Node.java | 117 ++++++++++++--------- .../main/java/com/seaofnodes/simple/type/Type.java | 2 +- 4 files changed, 106 insertions(+), 53 deletions(-) create mode 100644 chapter02/src/main/java/com/seaofnodes/simple/Utils.java (limited to 'chapter02/src/main/java/com/seaofnodes') 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 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(); 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 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}. + * + * @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 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 uses, 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 #setDef}. + */ + public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + for( int i=0; idef 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}. - * - * @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 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 uses, 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 #set_def}. - */ - public void kill( ) { - assert isUnused(); // Has no uses, so it is dead - for( int i=0; i