From 0049146baf2502809ed3f29b07cc5f90513cb747 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 26 Oct 2023 14:28:36 -0700 Subject: Replace Parser scopes with ScopeNode (#14) Fixes #12 * Replace Parser scopes with ScopeNode Basically move the Stack of HashMaps to a ScopeNode, with wrappers. The HashMap maps String names to Integer indices; inputs to the ScopeNode. This way, the ScopeNode keeps alive Nodes that are only alive because they are alive in the HashMap. Fix bug isDead -> isUnused in deadCodeElim. Support routines for adding/removing edges in ScopeNode. Set $ctrl to null after a Return; there is no control. Regression tests. * One more test case --- .../com/seaofnodes/simple/GraphVisualizer.java | 22 +++--- .../main/java/com/seaofnodes/simple/Parser.java | 71 +++++++---------- .../com/seaofnodes/simple/node/ConstantNode.java | 2 +- .../main/java/com/seaofnodes/simple/node/Node.java | 48 +++++++++--- .../java/com/seaofnodes/simple/node/ScopeNode.java | 88 ++++++++++++++++++++++ .../java/com/seaofnodes/simple/node/StartNode.java | 12 +-- .../java/com/seaofnodes/simple/Chapter04Test.java | 21 ++++++ 7 files changed, 191 insertions(+), 73 deletions(-) create mode 100644 chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java 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> scopes) { + private void scopes( StringBuilder sb, ScopeNode scopenode) { sb.append("\tnode [shape=plaintext];\n"); int level=0; - for( HashMap scope : scopes ) { + for( HashMap 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> scopes) { + private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); int level=0; - for( HashMap scope : scopes ) { + for( HashMap 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 scope : parser._scopes ) - for (Node n : scope.values()) - walk(all, n); + for( HashMap 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 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> _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 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. * * 
      *     '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 def->use 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; 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 #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> _scopes = new Stack<>();
+  
+    @Override
+    public String label() { return "Scope"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        for( HashMap 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 scope = _scopes.pop();
+        pop_n(scope.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 )
+            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 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
@@ -98,6 +98,20 @@ public class Chapter04Test {
         assertEquals("return 1;", ret.print());
     }
 
+    @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;");
@@ -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() {
-- 
cgit v1.2.3