From fb42c39d0addebd86d7bd5c71427b8a65bae3a26 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sun, 1 Oct 2023 18:01:54 +0100 Subject: Chapter 3: Variable Declarations MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Cliff Click Co-authored-by: Yichen Yan Co-authored-by: Thalia Archibald Co-authored-by: Tamas Hadhazy Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com> Co-authored-by: RobertObkircher --- README.md | 2 +- docs/chapter03/03-grammar.md | 72 ++++++++ docs/chapter03/03-graph1.gv | 39 ++++ docs/chapter03/03-graph1.svg | 136 ++++++++++++++ docs/chapter03/03-graph2.gv | 35 ++++ docs/chapter03/03-graph2.svg | 137 ++++++++++++++ docs/chapter03/03-graph3.gv | 37 ++++ docs/chapter03/03-graph3.svg | 151 ++++++++++++++++ docs/chapter03/03-graph4.svg | 127 +++++++++++++ docs/chapter03/03-graph5.svg | 127 +++++++++++++ docs/chapter03/Makefile | 12 ++ docs/chapter03/README.md | 197 +++++++++++++++++++++ .../com/seaofnodes/simple/GraphVisualizer.java | 62 ++++++- src/main/java/com/seaofnodes/simple/Parser.java | 125 ++++++++++++- src/main/java/com/seaofnodes/simple/node/Node.java | 64 ++++++- .../java/com/seaofnodes/simple/node/ScopeNode.java | 128 +++++++++++++ .../java/com/seaofnodes/simple/Chapter01Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter02Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 77 ++++++++ 19 files changed, 1517 insertions(+), 17 deletions(-) create mode 100644 docs/chapter03/03-grammar.md create mode 100644 docs/chapter03/03-graph1.gv create mode 100644 docs/chapter03/03-graph1.svg create mode 100644 docs/chapter03/03-graph2.gv create mode 100644 docs/chapter03/03-graph2.svg create mode 100644 docs/chapter03/03-graph3.gv create mode 100644 docs/chapter03/03-graph3.svg create mode 100644 docs/chapter03/03-graph4.svg create mode 100644 docs/chapter03/03-graph5.svg create mode 100644 docs/chapter03/Makefile create mode 100644 docs/chapter03/README.md create mode 100644 src/main/java/com/seaofnodes/simple/node/ScopeNode.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter03Test.java diff --git a/README.md b/README.md index 364f3da4..4143f605 100644 --- a/README.md +++ b/README.md @@ -40,7 +40,7 @@ The Simple language is styled after a subset of C or Java. * [Chapter 1](docs/chapter01/README.md): Script that returns an integer literal, i.e., an empty function that takes no arguments and returns a single integer value. The `return` statement. * [Chapter 2](docs/chapter02/README.md): Simple binary arithmetic such as addition, subtraction, multiplication, division with constants. Peephole optimization / simple constant folding. -* Chapter 3: Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a +* [Chapter 3](docs/chapter03/README.md): Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a constant. * Chapter 4: A non-constant external variable input named `arg`. Binary and Comparison operators involving constants and `arg`. diff --git a/docs/chapter03/03-grammar.md b/docs/chapter03/03-grammar.md new file mode 100644 index 00000000..14a7d5fa --- /dev/null +++ b/docs/chapter03/03-grammar.md @@ -0,0 +1,72 @@ +# Grammar for Chapter 1 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | metaStatement + ; + +metaStatement + : '#showGraph' ';' + ; + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : additiveExpression + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter03/03-graph1.gv b/docs/chapter03/03-graph1.gv new file mode 100644 index 00000000..2bdca351 --- /dev/null +++ b/docs/chapter03/03-graph1.gv @@ -0,0 +1,39 @@ +digraph chapter03 { +/* +int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_3 [ label="#1" ]; + Con_4 [ label="#2" ]; + Con_6 [ label="#3" ]; + Add7 [ label="+" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + + +
0abc
>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + + +
1b
>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_3 -> Start2[taillabel=0 style=dotted]; + Con_4 -> Start2[taillabel=0 style=dotted]; + Con_6 -> Start2[taillabel=0 style=dotted]; + Add7 -> Con_3[taillabel=1]; + Add7 -> Con_6[taillabel=2]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_a" -> Con_3; + Scope1_0:"Scope1_0_b" -> Con_4; + Scope1_0:"Scope1_0_c" -> Add7; + Scope1_1:"Scope1_1_b" -> Con_6; +} diff --git a/docs/chapter03/03-graph1.svg b/docs/chapter03/03-graph1.svg new file mode 100644 index 00000000..ab6f9600 --- /dev/null +++ b/docs/chapter03/03-graph1.svg @@ -0,0 +1,136 @@ + + + + + + +chapter03 + + +cluster_Nodes + + + +cluster_Scope1_0 + + + +cluster_Scope1_1 + + + + +Start2 + +Start + + + +Con_3 + +#1 + + + +Con_3->Start2 + + +0 + + + +Con_4 + +#2 + + + +Con_4->Start2 + + +0 + + + +Con_6 + +#3 + + + +Con_6->Start2 + + +0 + + + +Add7 + ++ + + + +Add7->Con_3 + + +1 + + + +Add7->Con_6 + + +2 + + + +Scope1_0 + + +0 + +a + +b + +c + + + +Scope1_0:Scope1_0_a->Con_3 + + + + + +Scope1_0:Scope1_0_b->Con_4 + + + + + +Scope1_0:Scope1_0_c->Add7 + + + + + +Scope1_1 + + +1 + +b + + + +Scope1_1:Scope1_1_b->Con_6 + + + + + diff --git a/docs/chapter03/03-graph2.gv b/docs/chapter03/03-graph2.gv new file mode 100644 index 00000000..460b63c8 --- /dev/null +++ b/docs/chapter03/03-graph2.gv @@ -0,0 +1,35 @@ +digraph chapter03 { +/* +int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_3 [ label="#1" ]; + Con_4 [ label="#2" ]; + Con_6 [ label="#3" ]; + Add7 [ label="+" ]; + Return8 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + + +
0abc
>]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_3 -> Start2[taillabel=0 style=dotted]; + Con_4 -> Start2[taillabel=0 style=dotted]; + Con_6 -> Start2[taillabel=0 style=dotted]; + Add7 -> Con_3[taillabel=1]; + Add7 -> Con_6[taillabel=2]; + Return8 -> Start2[taillabel=0 color=red]; + Return8 -> Add7[taillabel=1]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_a" -> Con_3; + Scope1_0:"Scope1_0_b" -> Con_4; + Scope1_0:"Scope1_0_c" -> Add7; +} diff --git a/docs/chapter03/03-graph2.svg b/docs/chapter03/03-graph2.svg new file mode 100644 index 00000000..0a539c6a --- /dev/null +++ b/docs/chapter03/03-graph2.svg @@ -0,0 +1,137 @@ + + + + + + +chapter03 + + +cluster_Nodes + + + +cluster_Scope1_0 + + + + +Start2 + +Start + + + +Con_3 + +#1 + + + +Con_3->Start2 + + +0 + + + +Con_4 + +#2 + + + +Con_4->Start2 + + +0 + + + +Con_6 + +#3 + + + +Con_6->Start2 + + +0 + + + +Add7 + ++ + + + +Add7->Con_3 + + +1 + + + +Add7->Con_6 + + +2 + + + +Return8 + +Return + + + +Return8->Start2 + + +0 + + + +Return8->Add7 + + +1 + + + +Scope1_0 + + +0 + +a + +b + +c + + + +Scope1_0:Scope1_0_a->Con_3 + + + + + +Scope1_0:Scope1_0_b->Con_4 + + + + + +Scope1_0:Scope1_0_c->Add7 + + + + + diff --git a/docs/chapter03/03-graph3.gv b/docs/chapter03/03-graph3.gv new file mode 100644 index 00000000..50cb6d27 --- /dev/null +++ b/docs/chapter03/03-graph3.gv @@ -0,0 +1,37 @@ +digraph chapter03 { +/* +int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_3 [ label="#1" ]; + Con_4 [ label="#2" ]; + Con_20 [ label="#8" ]; + Con_5 [ label="#3" ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_6 [ label="#4" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + + +
0y0x0y1x1
>]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_3 -> Start2[taillabel=0 style=dotted]; + Con_4 -> Start2[taillabel=0 style=dotted]; + Con_20 -> Start2[taillabel=0 style=dotted]; + Con_5 -> Start2[taillabel=0 style=dotted]; + Return21 -> Start2[taillabel=0 color=red]; + Return21 -> Con_20[taillabel=1]; + Con_6 -> Start2[taillabel=0 style=dotted]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_y0" -> Con_4; + Scope1_0:"Scope1_0_x0" -> Con_3; + Scope1_0:"Scope1_0_y1" -> Con_6; + Scope1_0:"Scope1_0_x1" -> Con_5; +} diff --git a/docs/chapter03/03-graph3.svg b/docs/chapter03/03-graph3.svg new file mode 100644 index 00000000..623bd902 --- /dev/null +++ b/docs/chapter03/03-graph3.svg @@ -0,0 +1,151 @@ + + + + + + +chapter03 + + +cluster_Nodes + + + +cluster_Scope1_0 + + + + +Start2 + +Start + + + +Con_3 + +#1 + + + +Con_3->Start2 + + +0 + + + +Con_4 + +#2 + + + +Con_4->Start2 + + +0 + + + +Con_20 + +#8 + + + +Con_20->Start2 + + +0 + + + +Con_5 + +#3 + + + +Con_5->Start2 + + +0 + + + +Return21 + +Return + + + +Return21->Start2 + + +0 + + + +Return21->Con_20 + + +1 + + + +Con_6 + +#4 + + + +Con_6->Start2 + + +0 + + + +Scope1_0 + + +0 + +y0 + +x0 + +y1 + +x1 + + + +Scope1_0:Scope1_0_x0->Con_3 + + + + + +Scope1_0:Scope1_0_y0->Con_4 + + + + + +Scope1_0:Scope1_0_x1->Con_5 + + + + + +Scope1_0:Scope1_0_y1->Con_6 + + + + + diff --git a/docs/chapter03/03-graph4.svg b/docs/chapter03/03-graph4.svg new file mode 100644 index 00000000..6838e1d4 --- /dev/null +++ b/docs/chapter03/03-graph4.svg @@ -0,0 +1,127 @@ + + + + + + +chapter03 + + +cluster_Nodes + + + +cluster_Scope1_0 + + + +cluster_Scope1_1 + + + + +Start2 + +Start + + + +Con_3 + +#1 + + + +Con_3->Start2 + + +0 + + + +Con_4 + +#2 + + + +Con_4->Start2 + + +0 + + + +Con_6 + +#5 + + + +Con_6->Start2 + + +0 + + + +Con_8 + +#6 + + + +Con_8->Start2 + + +0 + + + +Scope1_0 + + +0 + +a + +b + +c + + + +Scope1_0:Scope1_0_a->Con_3 + + + + + +Scope1_0:Scope1_0_b->Con_4 + + + + + +Scope1_0:Scope1_0_c->Con_8 + + + + + +Scope1_1 + + +1 + +b + + + +Scope1_1:Scope1_1_b->Con_6 + + + + + \ No newline at end of file diff --git a/docs/chapter03/03-graph5.svg b/docs/chapter03/03-graph5.svg new file mode 100644 index 00000000..48e69cb7 --- /dev/null +++ b/docs/chapter03/03-graph5.svg @@ -0,0 +1,127 @@ + + + + + + +chapter03 + + +cluster_Nodes + + + +cluster_Scope1_0 + + + +cluster_Scope1_1 + + + + +Start2 + +Start + + + +Con_3 + +#1 + + + +Con_3->Start2 + + +0 + + + +Con_4 + +#2 + + + +Con_4->Start2 + + +0 + + + +Con_9 + +#6 + + + +Con_9->Start2 + + +0 + + + +Con_11 + +#7 + + + +Con_11->Start2 + + +0 + + + +Scope1_0 + + +0 + +a + +b + +c + + + +Scope1_0:Scope1_0_a->Con_3 + + + + + +Scope1_0:Scope1_0_b->Con_4 + + + + + +Scope1_0:Scope1_0_c->Con_11 + + + + + +Scope1_1 + + +1 + +e + + + +Scope1_1:Scope1_1_e->Con_9 + + + + + \ No newline at end of file diff --git a/docs/chapter03/Makefile b/docs/chapter03/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter03/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter03/README.md b/docs/chapter03/README.md new file mode 100644 index 00000000..d26b2462 --- /dev/null +++ b/docs/chapter03/README.md @@ -0,0 +1,197 @@ +# Chapter 3: Variable Declarations + +# Table of Contents + +1. [Extensions to Intermediate Representation](#extensions-to-intermediate-representation) +2. [Symbol Tables](#symbol-tables) +3. [ScopeNode](#scopenode) +4. [Demonstration](#demonstration) +5. [Identification of Basic Blocks in SoN graph](#identification-of-basic-blocks-in-son-graph) +6. [Enabling peephole optimizations](#enabling-peephole-optimizations) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter03) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter02...linear-chapter03) it to the previous chapter. + +In this chapter we extend the language grammar to allow variable declarations. This allows us to write: + +``` +int a=1; +int b=2; +int c=0; +{ + int b=3; + c=a+b; +} +return c; +``` + +Here is the [complete language grammar](03-grammar.md) for this chapter. + + +## Extensions to Intermediate Representation + +To recap, our list of Nodes are: + +| Node Name | Type | Description | Inputs | Value | +|-----------|---------|------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| +| Start | Control | Start of function | None | None for now as we do not have function arguments yet | +| Return | Control | End of function | Predecessor control node, Data node value | Return value of the function | +| Constant | Data | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | +| Add | Data | Add two values | Two data nodes, values are added, order not important | Result of the add operation | +| Sub | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters | Result of the subtract | +| 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 | +| Minus | 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 | Symbol Table | 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. A symbol table maps names to nodes. + +We maintain a *stack* of symbol tables. +When a new lexical scope is created we push a new symbol table to the stack; +when scope exits the topmost symbol table is popped from the stack. + +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, in lexical order. + +## ScopeNode + +A ScopeNode encapsulates the stack of symbol tables that are used to implement lexical scopes. + +* The nodes referenced by the names in a lexical scope become inputs to the ScopeNode; this makes ScopeNode a user of these values, thus keeping them alive while a particular lexical scope is alive. + When the lexical scope ends, those inputs are removed. This is crucial because peepholes will remove dead Nodes and every new Node is effectively dead at the instance of creation without such a reference. +* In [Chapter 5](../chapter05/README.md) when we implement branches, the ScopeNode gets duplicated at a branch point and then gets merged when the branch joins. This allows + the names to evolve in each branch independently. At the merge point names that have diverged require a Phi node. +* In [Chapter 7](../chapter07/README.md) additional logic is deployed for handling Phis from back edges. +* The ScopeNode is used to track some other values such as the Control token starting from [Chapter 4](../chapter04/README.md), and Aliases starting from [Chapter 10](../chapter10/README.md). Special name bindings are used + for these, and each name is tracked across branches and then merged at merge points. +* In [Chapter 10](../chapter10/README.md) the ScopeNode is enhanced to also maintain the declared type for each name. + +From an implementation standpoint, each symbol table is represented as a `HashMap`, where the `String` is the variable name, and the `Integer` is an index into the inputs of the +ScopeNode. To access the Node associated with a name, first the symbol table is consulted, and then the ScopeNode's inputs to find the required Node. +The stack of symbol tables is represented as `Stack>`. + +When a lexical scope is exited, we not only pop the symbol table representing the +scope from the stack, but also remove the relevant input nodes. If the variable's expression +only exists for the Scope mapping (e.g., "just in case" the Parser parses code +that uses the variable) this is when the expression dies: +``` + int a=1; + { + int b=a*a*a; + } // When this scope closes & ends, b (and the cube of a) dies + return a; +``` + + +In the visualization, we show the ScopeNode in a separate box running +underneath the main IR graph; 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. + +The ScopeNode is neither a Data Node nor a Control Node; it really is a utility for maintaining symbol tables, name lookups, plays a crucial role in deciding where Phi nodes are required. +Representing it as a Node allows us to leverage the Sea of Nodes def-use architecture to maintain liveness of values in scope. + +A ScopeNode has no outputs. + +## Demonstration + +We show the output from following code. + +``` +01 int a=1; +02 int b=2; +03 int c=0; +04 { +05 int b=3; +07 c=a+b; +08 } +09 return c; +``` + +* When we start parsing above, we start with a symbol table (at level 0). +The variables `a`, `b`, and `c` are registered in this table. +* On line 4, we start a nested scope. At this point, a new symbol table is pushed (at level 1). +* On line 5, a variable `b` is declared. `b` is registered in the symbol table at level 1. This then +hides the variable with the same name on line 2. +* On line 7, we update the variable `c`. Variable lookup will find it in the symbol table at level 0. +The node graph is shown below (note that peephole opts are switched off here so that we can +see the graph as its initially constructed). + +![Graph1](./03-graph1.svg) + +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. +* At line 9, our graph looks like this: + +![Graph2](./03-graph2.svg) + +As we see, only 1 symbol table is present at this point. + +We can also have multiple scopes at the same level during the execution of the program, +but only one will be active at a time because the symbol table can only hold one symbol table +for each scope level. + +For example: +``` +01 int a=1; +02 int b=2; +03 int c=0; +04 { +05 int b=5; +06 c=a+b; +08 } +09 { +10 int e=6; +11 c = a+e; +13 } +14 return c; +``` +Here both scopes starting from `(04-08)` and `(09-13)` are at the same level: +```java +public final Stack> _scopes; +``` +The `_scopes` stack holds nested scopes, with index 0 representing the highest (global) +scope and deeper indices representing more nested scopes. +Popping returns the current scope and moves to the outer one. +There is a direct one-to-one mapping between each index and its corresponding scope. + +The first nested scope(04-08): + +![Graph4](./03-graph4.svg) + +The second nested scope(09-13): + +![Graph5](./03-graph5.svg) + + - In both cases the index which represents the deepness of the scope is 1. +## Enabling peephole optimizations + +Once we enable peephole optimizations, the parser is able to reduce all the expressions down to a +constant. This is illustrated nicely below. + +``` +01 int x0=1; +02 int y0=2; +03 int x1=3; +04 int y1=4; +05 return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); +``` + +The graph for above, is displayed below. + +![Graph2](./03-graph3.svg) + +The return node has the constant `8` as its data value! When the parsing ends +and the scope at level 0 is removed, only the `return 8` remains. diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 4c625be1..9dfac52d 100644 --- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -17,7 +17,7 @@ public class GraphVisualizer { // nodes in the graph. Collection all = findAll(parser); StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter02 {\n"); + sb.append("digraph chapter03 {\n"); sb.append("/*\n"); sb.append(parser.src()); sb.append("\n*/\n"); @@ -39,9 +39,15 @@ public class GraphVisualizer { // Just the Nodes first, in a cluster no edges nodes(sb, all); + // Now the scopes, in a cluster no edges + scopes(sb, parser._scope); + // Walk the Node edges nodeEdges(sb, all); + // Walk the Scope edges + scopeEdges(sb, parser._scope); + sb.append("}\n"); return sb.toString(); } @@ -51,6 +57,8 @@ public class GraphVisualizer { // Just the Nodes first, in a cluster no edges sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name for( Node n : all ) { + if( n instanceof ScopeNode ) + continue; // Do not emit, rolled into Scope cluster already sb.append("\t\t").append(n.uniqueName()).append(" [ "); String lab = n.glabel(); // control nodes have box shape @@ -63,6 +71,30 @@ public class GraphVisualizer { sb.append("\t}\n"); // End Node cluster } + private void scopes( StringBuilder sb, ScopeNode scopenode) { + sb.append("\tnode [shape=plaintext];\n"); + int level=0; + for( HashMap scope : scopenode._scopes ) { + String scopeName = makeScopeName(scopenode, level); + sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name + sb.append("\t\t").append(scopeName).append(" [label=<\n"); + sb.append("\t\t\t\n"); + // Add the scope level + sb.append("\t\t\t"); + for( String name : scope.keySet() ) + sb.append(""); + sb.append("\n"); + sb.append("\t\t\t
").append(level).append("").append(name).append("
>];\n"); + level++; + } + // Scope clusters nest, so the graphics shows the nested scopes, so + // they are not closed as they are printed; so they just keep nesting. + // We close them all at once here. + sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters + } + + private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; } + private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; } // Walk the node edges private void nodeEdges(StringBuilder sb, Collection all) { @@ -70,6 +102,9 @@ public class GraphVisualizer { sb.append("\tedge [ fontname=Helvetica, fontsize=8 ];\n"); for( Node n : all ) { // In this chapter we do display the Constant->Start edge; + // ScopeNodes are done separately + if( n instanceof ScopeNode ) + continue; int i=0; for( Node def : n._inputs ) { if( def != null ) { @@ -90,6 +125,26 @@ public class GraphVisualizer { } } + // Walk the scope edges + private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) { + sb.append("\tedge [style=dashed color=cornflowerblue];\n"); + int level=0; + for( HashMap scope : scopenode._scopes ) { + String scopeName = makeScopeName(scopenode, 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(" -> "); + sb.append(def.uniqueName()); + sb.append(";\n"); + } + level++; + } + } + /** * Finds all nodes in the graph. */ @@ -98,6 +153,10 @@ public class GraphVisualizer { final HashMap all = new HashMap<>(); for( Node n : start._outputs ) walk(all, n); + // Scan symbol tables + for( HashMap scope : parser._scope._scopes ) + for (Integer i : scope.values()) + walk(all, parser._scope.in(i)); return all.values(); } @@ -105,6 +164,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/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 72da8eeb..fa1a852c 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import java.util.*; + /** * The Parser converts a Simple source program to the Sea of Nodes intermediate * representation directly in one pass. There is no intermediate Abstract @@ -24,32 +26,75 @@ public class Parser { // The Lexer. Thin wrapper over a byte[] buffer with a cursor. 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. + */ + public ScopeNode _scope; + + /** + * List of keywords disallowed as identifiers + */ + private final HashSet KEYWORDS = new HashSet<>(){{ + add("int"); + add("return"); + }}; + public Parser(String source) { _lexer = new Lexer(source); Node.reset(); + _scope = new ScopeNode(); START = new StartNode(); } String src() { return new String( _lexer._input ); } - public ReturnNode parse() { - var ret = (ReturnNode) parseStatement(); + public ReturnNode parse() { return parse(false); } + public ReturnNode parse(boolean show) { + var ret = (ReturnNode) parseBlock(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); + if( show ) showGraph(); return ret; } + /** + * Parses a block + * + * 
+     *     '{' statements '}'
+     *
+ * Does not parse the opening or closing '{}' + * @return a {@link Node} or {@code null} + */ + private Node parseBlock() { + // Enter a new scope + _scope.push(); + Node n = null; + while (!peek('}') && !_lexer.isEOF()) { + Node n0 = parseStatement(); + if (n0 != null) n = n0; // Allow null returns from eg showGraph + }; + // Exit scope + _scope.pop(); + return n; + } + /** * Parses a statement * * 
-     *     returnStatement
+     *     returnStatement | declStatement | blockStatement | expressionStatement
      *
* @return a {@link Node} or {@code null} */ private Node parseStatement() { - if (matchx("return")) return parseReturn(); - throw errorSyntax("a statement"); + if (matchx("return") ) return parseReturn(); + else if (matchx("int")) return parseDecl(); + else if (match ("{" )) return require(parseBlock(),"}"); + else if (matchx("#showGraph")) return require(showGraph(),";"); + else if (matchx(";")) return null; // Empty statement + else return parseExpressionStatement(); } /** @@ -65,6 +110,50 @@ public class Parser { return new ReturnNode(START, expr).peephole(); } + /** + * Dumps out the node graph + * @return {@code null} + */ + private Node showGraph() { + System.out.println(new GraphVisualizer().generateDotOutput(this)); + return null; + } + + /** + * Parses an expression statement + * + * 
+     *     name '=' expression ';'
+     *
+ * @return an expression {@link Node}, never {@code null} + */ + private Node parseExpressionStatement() { + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + if( _scope.update(name, expr)==null ) + throw error("Undefined name '" + name + "'"); + return expr; + } + + /** + * Parses a declStatement + * + * 
+     *     'int' name = expression ';'
+     *
+ * @return an expression {@link Node}, never {@code null} + */ + private Node parseDecl() { + // Type is 'int' for now + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + if( _scope.define(name,expr) == null ) + throw error("Redefining name '" + name + "'"); + return expr; + } + /** * Parse an expression of the form: * @@ -129,7 +218,11 @@ public class Parser { private Node parsePrimary() { if( _lexer.isNumber() ) return parseIntegerLiteral(); if( match("(") ) return require(parseExpression(), ")"); - throw errorSyntax("integer literal"); + String name = _lexer.matchId(); + if( name == null) throw errorSyntax("an identifier or expression"); + Node n = _scope.lookup(name); + if( n!=null ) return n; + throw error("Undefined name '" + name + "'"); } /** @@ -150,6 +243,15 @@ public class Parser { private boolean match (String syntax) { return _lexer.match (syntax); } // Match must be "exact", not be followed by more id letters private boolean matchx(String syntax) { return _lexer.matchx(syntax); } + // Return true and do NOT skip if 'ch' is next + private boolean peek(char ch) { return _lexer.peek(ch); } + + // Require and return an identifier + private String requireId() { + String id = _lexer.matchId(); + if (id != null && !KEYWORDS.contains(id) ) return id; + throw error("Expected an identifier, found '"+id+"'"); + } // Require an exact match private void require(String syntax) { require(null, syntax); } @@ -247,6 +349,17 @@ public class Parser { return false; } + private boolean peek(char ch) { + skipWhiteSpace(); + return peek()==ch; + } + + // Return an identifier or null + String matchId() { + skipWhiteSpace(); + return isIdStart(peek()) ? parseId() : null; + } + // Used for errors String getAnyNextToken() { if (isEOF()) return ""; diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index fd233108..6e4617ff 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 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}. + *

+ + * This method is the normal path for altering a Node, because it does the + * proper default edge maintenance. It also immediately 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 def->use 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 void addUse(N n) { _outputs.add(n); } @@ -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; 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 #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; iMonotonic @@ -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 chapter03/README.md + */ +public class ScopeNode extends Node { + + /** + * A Stack of symbol tables; a symbol table is a map from names to node indices. + */ + public final Stack> _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 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. + *

+ * This is an expensive operation. + */ + public String[] reverseNames() { + String[] names = new String[nIns()]; + for( HashMap 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 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. + *

+ * @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 + *

+ * @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. + *

+ * 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); } + +} diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 49edfb5b..311ca23b 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -40,7 +40,7 @@ public class Chapter01Test { new Parser("ret").parse(); fail(); } catch( RuntimeException e ) { - assertEquals("Syntax error, expected a statement: ret",e.getMessage()); + assertEquals("Syntax error, expected =: ",e.getMessage()); } } @@ -82,7 +82,7 @@ public class Chapter01Test { new Parser("return100").parse(); fail(); } catch( RuntimeException e ) { - assertEquals("Syntax error, expected a statement: return100",e.getMessage()); + assertEquals("Syntax error, expected =: ",e.getMessage()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 36e62f9b..60ee8874 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -10,8 +10,8 @@ public class Chapter02Test { @Test public void testParseGrammar() { - Node._disablePeephole = true; // disable peephole so we can observe full graph Parser parser = new Parser("return 1+2*3+-5;"); + Node._disablePeephole = true; // disable peephole so we can observe full graph ReturnNode ret = parser.parse(); assertEquals("return (1+((2*3)+(-5)));", ret.print()); GraphVisualizer gv = new GraphVisualizer(); diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..3b8b3449 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,77 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter03Test { + + @Test + public void testVarDecl() { + Parser parser = new Parser("int a=1; return a;"); + ReturnNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testVarAdd() { + Parser parser = new Parser("int a=1; int b=2; return a+b;"); + ReturnNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testVarScope() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + ReturnNode ret = parser.parse(); + assertEquals("return 4;", ret.print()); + } + + @Test + public void testVarScopeNoPeephole() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + Node._disablePeephole = true; + ReturnNode ret = parser.parse(); + Node._disablePeephole = false; + assertEquals("return (1+3);", ret.print()); + } + + @Test + public void testVarDist() { + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); + ReturnNode ret = parser.parse(); + assertEquals("return 8;", ret.print()); + } + + @Test + public void testSelfAssign() { + try { + new Parser("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } + } + + @Test + public void testRedeclareVar() { + try { + new Parser("int a=1; int b=2; int c=0; int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Redefining name 'b'",e.getMessage()); + } + } + + @Test + public void testBad1() { + try { + new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected }: ",e.getMessage()); + } + } + +} -- cgit v1.2.3