From d9ec7e41f48575d4368794f60c99b16ac8a0bdc5 Mon Sep 17 00:00:00 2001 From: Cliff Click 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: Dibyendu Majumdar Co-authored-by: Yichen Yan Co-authored-by: Thalia Archibald Co-authored-by: Tamas Hadhazy Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> 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: 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 | 68 +++++++ 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 | 198 +++++++++++++++++++++ src/main/java/com/seaofnodes/simple/Parser.java | 113 +++++++++++- src/main/java/com/seaofnodes/simple/node/Node.java | 62 ++++++- .../java/com/seaofnodes/simple/node/ScopeNode.java | 128 +++++++++++++ .../simple/print/SimpleGraphAdapter.java | 8 +- .../simple/print/SimpleGraphObserver.java | 3 +- .../java/com/seaofnodes/simple/Chapter01Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 68 +++++++ 19 files changed, 1438 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 9f85aa24..7966f04b 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..1d36b532 --- /dev/null +++ b/docs/chapter03/03-grammar.md @@ -0,0 +1,68 @@ +# Grammar for Chapter 1 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + ; + + +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..7008a44e --- /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; } return c; +*/ + 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..cafa7f25 --- /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; } return c; +*/ + 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..791a7dc1 --- /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); +*/ + 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..0f57774b --- /dev/null +++ b/docs/chapter03/README.md @@ -0,0 +1,198 @@ +# 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 whole memory starting from [Chapter 10a](../chapter10a/README.md). Special name bindings are used + for these, and each name is tracked across branches and then merged at merge points. +* In [Chapter 10a](../chapter10a/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 schematic below shows the variable bindings and arithmetic before constant +folding. The compiler applies peepholes as it builds the graph, so the actual +result of this example is `return 4;`. + +![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/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index f59b0f25..e6cb84f8 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -5,6 +5,8 @@ import com.seaofnodes.graph.GraphObserver; 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 @@ -32,33 +34,73 @@ 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); PARSER = this; Node.reset(); + _scope = new ScopeNode(); START = new StartNode(); } String src() { return new String( _lexer._input ); } public ReturnNode parse() { - var ret = (ReturnNode) parseStatement(); + var ret = (ReturnNode) parseBlock(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); 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; // Empty statements can return null + }; + // 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(";")) return null; // Empty statement + else return parseExpressionStatement(); } /** @@ -74,6 +116,43 @@ public class Parser { return new ReturnNode(START, expr).peephole(); } + + + /** + * 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: * @@ -138,7 +217,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 + "'"); } /** @@ -159,6 +242,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); } @@ -256,6 +348,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 acf6b236..3fa0fd1e 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -124,10 +124,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 @@ -150,6 +158,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); } @@ -161,16 +185,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,4 +275,24 @@ public abstract class Node { * Node unique id generator, and is done as part of making a new Parser. */ public static void reset() { UNIQUE_ID = 1; } + + /** + * 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/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 502a2a8e..a615741d 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import java.util.ArrayList; -/** Chapter 2's view of the IR; browser, transport and layout are shared. */ +/** Chapter 3's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter { @Override protected boolean dead(Node n) { return n.isDead(); } @Override protected int id(Node n) { return n._nid; } @@ -18,8 +18,9 @@ public class SimpleGraphAdapter extends GraphAdapter { private ArrayList edges(Node n) { var edges = new ArrayList(); + String[] names = n instanceof ScopeNode scope && n.nIns() != 0 ? scope.reverseNames() : null; for( int i = 0; i < n.nIns(); i++ ) { - String name = null; + String name = names == null || i >= names.length ? null : names[i]; edges.add(new Edge(i, ref(n.in(i)), role(n, i), name)); } return edges; @@ -33,12 +34,13 @@ public class SimpleGraphAdapter extends GraphAdapter { } private Kind kind(Node n) { + if( n instanceof ScopeNode ) return Kind.SCOPE; if( n instanceof StartNode ) return Kind.CTRL; return n.isCFG() ? Kind.CTRL : Kind.DATA; } private Role role(Node n, int i) { - if( n instanceof ConstantNode ) return Role.ASSOC; + if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC; if( i == 0 ) return Role.CTRL; return Role.DATA; } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index a17bf796..2dc5d844 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 2's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 3's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; @@ -30,6 +30,7 @@ public class SimpleGraphObserver extends GraphCapture { _parser = null; _ret = null; } + @Override protected Node scope() { return _parser._scope; } @Override protected void roots(ArrayList roots) { roots.add(Parser.START); roots.add(_ret); 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/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..9a7dda5d --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,68 @@ +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 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);"); + 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