diff options
Diffstat (limited to 'chapter04')
7 files changed, 191 insertions, 73 deletions
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 38bc1356..f73bfd3c 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -34,13 +34,13 @@ public class GraphVisualizer { nodes(sb, all); // Now the scopes, in a cluster no edges - scopes(sb, parser._scopes); + scopes(sb, parser._scope); // Walk the Node edges nodeEdges(sb, all); // Walk the Scope edges - scopeEdges(sb, parser._scopes); + scopeEdges(sb, parser._scope); sb.append("}\n"); return sb.toString(); @@ -95,10 +95,10 @@ public class GraphVisualizer { sb.append("\t}\n"); // End Node cluster } - private void scopes( StringBuilder sb, Stack<HashMap<String,Node>> scopes) { + private void scopes( StringBuilder sb, ScopeNode scopenode) { sb.append("\tnode [shape=plaintext];\n"); int level=0; - for( HashMap<String,Node> scope : scopes ) { + for( HashMap<String,Integer> scope : scopenode._scopes ) { sb.append("\tsubgraph cluster_").append(level).append(" {\n"); // Magic "cluster_" in the subgraph name String scopeName = makeScopeName(level); sb.append("\t\t").append(scopeName).append(" [label=<\n"); @@ -145,17 +145,18 @@ public class GraphVisualizer { } // Walk the scope edges - private void scopeEdges( StringBuilder sb, Stack<HashMap<String,Node>> scopes) { + private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); int level=0; - for( HashMap<String,Node> scope : scopes ) { + for( HashMap<String,Integer> scope : scopenode._scopes ) { String scopeName = makeScopeName(level); for( String name : scope.keySet() ) { + Node def = scopenode.in(scope.get(name)); + if( def==null ) continue; sb.append("\t") .append(scopeName).append(":") .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted .append(" -> "); - Node def = scope.get(name); if( def instanceof ProjNode proj ) { String mname = proj.ctrl().uniqueName(); sb.append(mname).append(":p").append(proj._idx); @@ -175,9 +176,9 @@ public class GraphVisualizer { for( Node n : start._outputs ) walk(all, n); // Scan symbol tables - for( HashMap<String,Node> scope : parser._scopes ) - for (Node n : scope.values()) - walk(all, n); + for( HashMap<String,Integer> scope : parser._scope._scopes ) + for (Integer i : scope.values()) + walk(all, parser._scope.in(i)); return all.values(); } @@ -185,6 +186,7 @@ public class GraphVisualizer { * Walk a subgraph and populate distinct nodes in the all list. */ 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) diff --git a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java index 36fec5d5..a6872106 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java @@ -26,15 +26,14 @@ public class Parser { private final Lexer _lexer; /** - * Stack of lexical scopes, each scope is a symbol table - * that binds variable names to Nodes. - * The top of this stack represents current scope. + * 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 Stack<HashMap<String, Node>> _scopes; + public ScopeNode _scope; public Parser(String source, TypeInteger arg) { _lexer = new Lexer(source); - _scopes = new Stack<>(); + _scope = new ScopeNode(); Node.reset(); START = new StartNode(new Type[]{ Type.CONTROL, arg }); START.peephole(); @@ -47,46 +46,17 @@ public class Parser { String src() { return new String( _lexer._input ); } public ReturnNode parse() { - _scopes.push(new HashMap<>()); + _scope.push(); try { - define("$ctrl", new ProjNode(START, 0, "$ctrl").peephole()); - define("arg" , new ProjNode(START, 1, "arg" ).peephole()); + _scope.define("$ctrl", new ProjNode(START, 0, "$ctrl").peephole()); + _scope.define("arg" , new ProjNode(START, 1, "arg" ).peephole()); return (ReturnNode) parseBlock(); } finally { - _scopes.pop(); + _scope.pop(); } } - // Create a new name in current scope - private Node define(String name, Node n) { - _scopes.lastElement().put(name, n); - return n; - } - - // If the name is present in any scope, then redefine - private Node update(String name, Node n) { - for (int i = _scopes.size() - 1; i >= 0; i--) { - HashMap<String, Node> scope = _scopes.get(i); - Node old = scope.get(name); - if (old != null) { // Found prior def - if (old.nOuts() == 0) old.kill(); // Delete old ref - scope.put(name, n); // Update existing ref - return n; - } - } - throw error("Undefined name '" + name + "'"); - } - - // Lookup a name in all scopes - private Node lookup(String name) { - for (int i = _scopes.size() - 1; i >= 0; i--) { - var n = _scopes.get(i).get(name); - if (n != null) return n; - } - throw error("Undefined name '" + name + "'"); - } - /** * Parses a block * @@ -96,14 +66,14 @@ public class Parser { */ private Node parseBlock() { // Enter a new scope - _scopes.push(new HashMap<>()); + _scope.push(); Node n = null; while (!match("}") && !_lexer.isEOF()) { Node n0 = parseStatement(); if (n0 != null) n = n0; // Allow null returns from eg showGraph } // Exit scope - _scopes.pop(); + _scope.pop(); return n; } @@ -123,7 +93,8 @@ public class Parser { } /** - * Parses returnStatement; "return" already parsed + * Parses a return statement; "return" already parsed. + * The $ctrl edge is killed. * * <pre> * 'return' expr ; @@ -131,7 +102,9 @@ public class Parser { */ private Node parseReturn() { var expr = require(parseExpression(), ";"); - return new ReturnNode(lookup("$ctrl"), expr); + Node ret = new ReturnNode(_scope.lookup("$ctrl"), expr); + _scope.update("$ctrl",null); + return ret; } /** @@ -154,7 +127,9 @@ public class Parser { var name = requireId(); require("="); var expr = require(parseExpression(), ";"); - return update(name, expr); + if( _scope.update(name, expr)==null ) + throw error("Undefined name '" + name + "'"); + return expr; } /** @@ -169,7 +144,9 @@ public class Parser { var name = requireId(); require("="); var expr = require(parseExpression(), ";"); - return define(name, expr); + if( _scope.define(name,expr) == null ) + throw error("Redefining name '" + name + "'"); + return expr; } /** @@ -242,7 +219,11 @@ public class Parser { private Node parsePrimary() { if (_lexer.isNumber()) return parseIntegerLiteral(); if (match("(")) return require(parseExpression(), ")"); - return lookup(requireId()).peephole(); + String name = requireId(); + Node id = _scope.lookup(name); + if( id==null ) + throw error("Undefined name '" + name + "'"); + return id.peephole(); } /** 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 5b4f8af9..ec85bf1f 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -30,7 +30,7 @@ public class ConstantNode extends Node { @Override StringBuilder _print1(StringBuilder sb) { - return _type._print(sb); + return _con._print(sb); } @Override 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 45c4e11a..8d698d1b 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java @@ -162,7 +162,7 @@ public abstract class Node { 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 && isDead() ) { + 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(). @@ -192,18 +192,36 @@ public abstract class Node { */ Node set_def(int idx, Node new_def ) { Node old_def = in(idx); - if( old_def != null && // If the old def exists, remove a use->def edge + if( old_def == new_def ) return this; // No change + 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); - // If new def is not null, add the corresponding use->def edge + // If new def is not null, add the corresponding def->use edge if( new_def != null ) new_def._outputs.add(this); // Return self for easy flow-coding return this; } + /** + * 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 add_def(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._outputs.add(this); + return new_def; + } + + // Breaks the edge invariants, used temporarily private void addUse(Node n) { _outputs.add(n); } @@ -221,19 +239,27 @@ public abstract class Node { return lidx==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) { + for( int i=0; i<n; i++ ) { + Node old_def = _inputs.remove(_inputs.size()-1); + 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 #set_def}. + * code elimination. This function is co-recursive with {@link #pop_n}. */ 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(); // Flag as dead - _outputs.clear(); // Flag as dead - _type=null; // Flag as dead - assert isDead(); // Really dead now + assert isUnused(); // Has no uses, so it is dead + pop_n(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. diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java new file mode 100644 index 00000000..8bd81e82 --- /dev/null +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -0,0 +1,88 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.TypeBot; + +import java.util.*; + +/** + * The Scope node is a purely 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. + */ + public final Stack<HashMap<String, Integer>> _scopes = new Stack<>(); + + @Override + public String label() { return "Scope"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + 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; + } + + @Override + public TypeBot compute() { return TypeBot.BOTTOM; } + + @Override + public Node idealize() { return null; } + + // Add an empty lexical scope + public void push() { + _scopes.push(new HashMap<>()); + } + + // Remove the current lexical scope, killing all unused nodes. + public void pop() { + HashMap<String,Integer> scope = _scopes.pop(); + pop_n(scope.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 ) + return null; // Double define + return add_def(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; + } + + + // 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; + } + + +} 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 0618a42f..b59e3375 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -5,9 +5,11 @@ import com.seaofnodes.simple.type.TypeBot; import com.seaofnodes.simple.type.TypeTuple; /** - * The Start node represents the start of the function. For now, we do not have any inputs to Start because our function does not - * yet accept parameters. When we add parameters the value of Start will be a tuple, and will require Projections to extract the values. - * We discuss this in detail in Chapter 9: Functions and Calls. + * The Start node represents the start of the function. For now, we do not + * have any inputs to Start because our function does not yet accept + * parameters. When we add parameters the value of Start will be a tuple, and + * will require Projections to extract the values. We discuss this in detail + * in Chapter 9: Functions and Calls. */ public class StartNode extends MultiNode implements Control { @@ -27,9 +29,7 @@ public class StartNode extends MultiNode implements Control { } @Override - public TypeTuple compute() { - return _args; - } + public TypeTuple compute() { return _args; } @Override public Node idealize() { return null; } diff --git a/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 988e3608..8cc78af0 100644 --- a/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter04/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -99,6 +99,20 @@ public class Chapter04Test { } @Test + public void testChapter4Bug1() { + Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + assertEquals("return (Proj_3+3);", ret.print()); + } + + @Test + public void testChapter4Bug2() { + Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;", TypeInteger.BOT); + ReturnNode ret = parser.parse(); + assertEquals("return (Proj_3+1);", ret.print()); + } + + @Test public void testVarDecl() { Parser parser = new Parser("int a=1; return a;"); ReturnNode ret = parser.parse(); @@ -135,6 +149,13 @@ public class Chapter04Test { assertEquals("return 8;", ret.print()); } + @Test + public void testSelfAssign() { + exceptionRule.expect(RuntimeException.class); + exceptionRule.expectMessage("Undefined name 'a'"); + new Parser("int a=a; return a;").parse(); + } + @Test public void testChapter2ParseGrammar() { |