1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
# Chapter 3: Variable Declarations
English | [日本語](README.ja.md)
[Previous: Chapter 2](../chapter02/README.md) |
[Next: Chapter 4](../chapter04/README.md)
# Table of Contents
1. [Extensions to Intermediate Representation](#extensions-to-intermediate-representation)
2. [Symbol Tables](#symbol-tables)
3. [ScopeNode](#scopenode)
4. [Demonstration](#demonstration)
5. [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](docs/03-grammar.md) for this chapter.
## Extensions to Intermediate Representation
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 |
and keep all nodes from prior chapters.
## 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 instant of creation.
* 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 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<String,Integer>`, 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<HashMap<String,Integer>>`.
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 and ends, b (and the cube of a) dies
return a;
```
In the visualization, we show the ScopeNode in a separate purple box. Each
binding is labelled with its lexical scope level. 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 the 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 the example 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;`.
The diagram shows the ScopeNode's bindings with their scope levels. The two
bindings for `b` belong to different lexical scopes.
* 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:
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<HashMap<String, Integer>> _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):
The second nested scope (09-13):
- In both cases the index which represents the depth 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 the example above is displayed below.
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.
|
