diff options
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/node')
| -rw-r--r-- | src/main/java/com/seaofnodes/simple/node/Node.java | 64 | ||||
| -rw-r--r-- | src/main/java/com/seaofnodes/simple/node/ScopeNode.java | 128 |
2 files changed, 186 insertions, 6 deletions
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 6f47f9eb..82357f9b 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -126,10 +126,18 @@ public abstract class Node { 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}. + * <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 @@ -152,6 +160,22 @@ public abstract class Node { return new_def; } + /** + * Add a new def to an existing Node. Keep the edges correct by + * adding the corresponding <em>def->use</em> edge. + * + * @param new_def the new definition, appended to the end of existing definitions + * @return new_def for flow coding + */ + 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 + if( new_def != null ) + new_def.addUse(this); + return new_def; + } + // Breaks the edge invariants, used temporarily protected <N extends Node> N addUse(Node n) { _outputs.add(n); return (N)this; } @@ -163,16 +187,25 @@ public abstract class Node { 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 popN(int n) { + for( int i=0; i<n; i++ ) { + 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 + } + } + /** * 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}. + * code elimination. This function is co-recursive with {@link #popN}. */ 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(); + popN(nIns()); // Set all inputs to null, recursively killing unused Nodes _type=null; // Flag as dead assert isDead(); // Really dead now } @@ -218,7 +251,6 @@ public abstract class Node { return this; // No progress } - /** * This function needs to be * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a> @@ -243,5 +275,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/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java new file mode 100644 index 00000000..379ef033 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -0,0 +1,128 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +import java.util.*; + +/** + * The Scope node is purely a parser helper - it tracks names to nodes with a + * stack of scopes. + * @see <a href="file:../../../../../../../../chapter03/README.md">chapter03/README.md</a> + */ +public class ScopeNode extends Node { + + /** + * A Stack of symbol tables; a symbol table is a map from names to node indices. + */ + public final Stack<HashMap<String, Integer>> _scopes; + + + // A new ScopeNode + public ScopeNode() { + _scopes = new Stack<>(); + _type = Type.BOTTOM; + } + + + @Override public String label() { return "Scope"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + sb.append(label()); + for( HashMap<String,Integer> scope : _scopes ) { + sb.append("["); + boolean first=true; + for( String name : scope.keySet() ) { + if( !first ) sb.append(", "); + first=false; + sb.append(name).append(":"); + Node n = in(scope.get(name)); + if( n==null ) sb.append("null"); + else n._print0(sb); + } + sb.append("]"); + } + return sb; + } + + /** + * Recover the names for all variable bindings. + * The result is an array of names that is aligned with the + * inputs to the Node. + * <p> + * 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; } + + @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 + */ + public Node define( String name, Node n ) { + HashMap<String,Integer> syms = _scopes.lastElement(); + if( syms.put(name,nIns()) != null ) + return null; // Double define + return addDef(n); + } + /** + * Lookup a name in all scopes starting from most deeply nested. + * <p> + * @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 + * <p> + * @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. + * <p> + * 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() { 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); } + +} |