From 1c2965adcdfa8d732998bf154dd341ad8fe3032d Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Fri, 27 Oct 2023 19:22:24 +0100 Subject: Applied fix for #12 to chapter 3 (#15) ScopeNode added to chapter 3 Revised the description for Chapter 3 and 4 to include ScopeNode. --- chapter03/README.md | 24 +++- chapter03/docs/03-graph3.gv | 10 +- chapter03/docs/03-graph3.svg | 146 ++++++++++++--------- .../com/seaofnodes/simple/GraphVisualizer.java | 25 ++-- .../main/java/com/seaofnodes/simple/Parser.java | 56 +++----- .../main/java/com/seaofnodes/simple/node/Node.java | 66 ++++++++-- .../java/com/seaofnodes/simple/node/ScopeNode.java | 89 +++++++++++++ chapter04/README.md | 3 +- .../main/java/com/seaofnodes/simple/Parser.java | 2 + 9 files changed, 287 insertions(+), 134 deletions(-) create mode 100644 chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java diff --git a/chapter03/README.md b/chapter03/README.md index 31f3d46a..3e6cebfe 100644 --- a/chapter03/README.md +++ b/chapter03/README.md @@ -17,7 +17,7 @@ Here is the [complete language grammar](docs/03-grammar.md) for this chapter. ## Extensions to Intermediate Representation -In this chapter we do not add new nodes. To recap, our list of Nodes are: +To recap, our list of Nodes are: | Node Name | Type | Description | Inputs | Value | |------------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| @@ -30,6 +30,13 @@ In this chapter we do not add new nodes. To recap, our list of Nodes are: | 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 | +In this chapter we introduce: + +| Node Name | Type | Description | Inputs | Value | +|-----------|------|--------------------------------|---------------------------------|-------| +| Scope | ? | Represents scopes in the graph | All nodes that define variables | None | + + ## Symbol Tables To support variable declarations and lexical scopes, we introduce symbol tables in the parser. @@ -42,6 +49,19 @@ Declaring a name adds it to the current symbol table. If a name is assigned to, then its mapping in the most recent symbol table is updated. If a name is accessed, its mapping is looked up in the symbol tables. The lookup goes up the stack of symbol tables. +## ScopeNode + +We wrap the stack of symbol tables in a `ScopeNode`. When a name binding is added to a symbol table, +we also make the newly added node an input in the `ScopeNode`. This means that the `ScopeNode` is a user of +all nodes that define new names. + +From an implementation point of view, the symbol table maps names to offsets in the ScopeNode's inputs. + +When a scope is exited, we not only pop the symbol table representing the scope, but also remove the relevant input nodes. + +In the visualization, we show the ScopeNode in a separate box; the stack of symbol tables is shown inside +the box. We show the edge from each variable in the symbol table to the defining Node in the graph. + ## Demonstration We show the output from following code. @@ -68,7 +88,7 @@ see the graph as its initially constructed). ![Graph1](./docs/03-graph1.svg) -The diagram shows the symbol tables in the bottom cluster. +The diagram shows the ScopeNode and the symbol tables in the bottom cluster. Each table is annotated by its scope level, and shows the variables defined in that scope. * When we exit the nested scope on line 8, the symbol table at level 1 is popped. diff --git a/chapter03/docs/03-graph3.gv b/chapter03/docs/03-graph3.gv index da30744b..717024e3 100644 --- a/chapter03/docs/03-graph3.gv +++ b/chapter03/docs/03-graph3.gv @@ -3,22 +3,26 @@ digraph chapter03 { subgraph cluster_Nodes { Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; Con_2 [ label="#1" ]; - Con_19 [ label="#8" ]; Con_3 [ label="#2" ]; - Return20 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_19 [ label="#8" ]; Con_4 [ label="#3" ]; + Return20 [ shape=box style=filled fillcolor=yellow label="Return" ]; Con_5 [ label="#4" ]; } node [shape=plaintext]; subgraph cluster_0 { scope0 [label=< - +
0y0x0y1x1
0y0x0y1x1
>]; } + Con_2 -> Start1 [style=dotted]; + Con_3 -> Start1 [style=dotted]; Con_19 -> Start1 [style=dotted]; + Con_4 -> Start1 [style=dotted]; Return20 -> Start1 [color=red]; Return20 -> Con_19; + Con_5 -> Start1 [style=dotted]; edge [style=dashed color=cornflowerblue]; scope0:scope0_y0 -> Con_3; scope0:scope0_x0 -> Con_2; diff --git a/chapter03/docs/03-graph3.svg b/chapter03/docs/03-graph3.svg index 3900b93d..3b720323 100644 --- a/chapter03/docs/03-graph3.svg +++ b/chapter03/docs/03-graph3.svg @@ -4,117 +4,141 @@ - - + + chapter03 - + cluster_Nodes - + cluster_0 - + Start1 - -Start + +Start Con_2 - -#1 + +#1 - + + +Con_2->Start1 + + + + +Con_3 + +#2 + + + +Con_3->Start1 + + + + + Con_19 - -#8 + +#8 - + Con_19->Start1 - - + + - - -Con_3 - -#2 + + +Con_4 + +#3 + + + +Con_4->Start1 + + - + Return20 - -Return + +Return - + Return20->Start1 - - + + - + Return20->Con_19 - - - - - -Con_4 - -#3 + + Con_5 - -#4 + +#4 + + + +Con_5->Start1 + + scope0 - - -0 - -y0 - -x0 - -y1 - -x1 + + +0 + +y0 + +x0 + +y1 + +x1 - + scope0:scope0_x0->Con_2 - - + + - + scope0:scope0_y0->Con_3 - - + + - + scope0:scope0_x1->Con_4 - - + + - + scope0:scope0_y1->Con_5 - - + + diff --git a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 5f3f52d0..dc5358f4 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -1,9 +1,6 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.node.ConstantNode; -import com.seaofnodes.simple.node.Control; -import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.node.StartNode; +import com.seaofnodes.simple.node.*; import java.util.*; @@ -33,13 +30,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(); @@ -61,10 +58,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"); @@ -102,13 +99,13 @@ 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() ) - sb.append("\t").append(scopeName).append(":").append(makePortName(scopeName, name)).append(" -> ").append(scope.get(name).uniqueName()).append(";\n"); + sb.append("\t").append(scopeName).append(":").append(makePortName(scopeName, name)).append(" -> ").append(scopenode.in(scope.get(name)).uniqueName()).append(";\n"); level++; } } @@ -126,9 +123,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(); } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java index 13b25e60..12e156ed 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter03/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) { _lexer = new Lexer(source); - _scopes = new Stack<>(); + _scope = new ScopeNode(); Node.reset(); START = new StartNode(); } @@ -43,35 +42,6 @@ public class Parser { return (ReturnNode) parseBlock(); } - // Create a new name in current scope - private Node define(String name, Node n) { - // new name - _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 @@ -82,14 +52,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; } @@ -140,7 +110,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; } /** @@ -155,7 +127,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; } /** @@ -217,7 +191,11 @@ public class Parser { private Node parsePrimary() { if (_lexer.isNumber()) return parseIntegerLiteral(); if (match("(")) return require(parseExpression(), ")"); - return lookup(requireId()); + String name = requireId(); + Node id = _scope.lookup(name); + if( id==null ) + throw error("Undefined name '" + name + "'"); + return id; } /** diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java index 5528f296..6b7d673a 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java @@ -152,27 +152,65 @@ public abstract class Node { * @param idx which def to set * @param new_def the new definition */ - void set_def(int idx, Node new_def ) { + 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 - 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 + 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); } + + // 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. + private boolean delUse( Node use ) { + ArrayList outs = _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(use),outs.get(lidx)); + outs.remove(lidx); // Reduce ArrayList size without copying anything + 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> _scopes = new Stack<>(); + + @Override + public String label() { return "Scope"; } + + @Override + StringBuilder _print(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._print(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/README.md b/chapter04/README.md index 7e8a8eea..45d054de 100644 --- a/chapter04/README.md +++ b/chapter04/README.md @@ -33,6 +33,7 @@ Below is our list of Nodes from [Chapter 3](../chapter03/README.md): | 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 | +| Scope | ? | Represents scopes in the graph | All nodes that define variables | None | ## Projection Nodes @@ -228,7 +229,7 @@ The peephole method does following: 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(). diff --git a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java index a6872106..147515f6 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java @@ -45,6 +45,8 @@ public class Parser { String src() { return new String( _lexer._input ); } + + public ReturnNode parse() { _scope.push(); try { -- cgit v1.2.3