From fcc6da8be593ea4cc0cb3848d4509bd626ebbe1e Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 15 Aug 2024 12:13:46 -0700 Subject: Scope docs (#99) * More scope docs * readme updates --- chapter03/README.md | 64 ++++++++++++++-------- .../java/com/seaofnodes/simple/node/ScopeNode.java | 11 ++-- .../java/com/seaofnodes/simple/Chapter03Test.java | 1 - 3 files changed, 48 insertions(+), 28 deletions(-) diff --git a/chapter03/README.md b/chapter03/README.md index 0fb08e9a..b0472619 100644 --- a/chapter03/README.md +++ b/chapter03/README.md @@ -7,8 +7,8 @@ int a=1; int b=2; int c=0; { - int b=3; - c=a+b; + int b=3; + c=a+b; } return c; ``` @@ -39,28 +39,47 @@ In this chapter we introduce: ## 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 scope is created, we push a new symbol table to the stack, when scope exits, the topmost symbol table is popped -from the stack. +To support variable declarations and lexical scopes, we introduce symbol tables +in the parser. A symbol table maps names to nodes via a `HashMap` +where the `String` is the variable name, and the `Integer` is an index into a +`ArrayList`. -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. +We maintain a *stack* of symbol tables, `Stack>`. +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 -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. +We wrap the stack of symbol tables in a `ScopeNode`, and the symbol table's +`Integer` is just an index in the `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 - +crucial, because the normal peepholes will remove dead Nodes and every new Node +is effectively dead at the instance of creation. + +When a scope is exited, we not only pop the symbol table representing the +scope, 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; +``` -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 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. -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 @@ -71,15 +90,15 @@ We show the output from following code. 02 int b=2; 03 int c=0; 04 { -05 int b=3; -07 c=a+b; +05 int b=3; +07 c=a+b; 08 } 09 return c; ``` -* When we start parsing above, we start with a symbol table (level 0). +* 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 (level 1). +* 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. @@ -115,4 +134,5 @@ The graph for above, is displayed below. ![Graph2](./docs/03-graph3.svg) -The return node has the constant `8` as its data value! +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. \ No newline at end of file diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index e9ff0f44..379ef033 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -7,11 +7,12 @@ 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 { /** - * Names for every input edge + * A Stack of symbol tables; a symbol table is a map from names to node indices. */ public final Stack> _scopes; @@ -48,7 +49,7 @@ public class ScopeNode extends Node { * 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() { @@ -77,21 +78,21 @@ public class ScopeNode extends Node { } /** * 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. * diff --git a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 950d87fe..bdb1d9ea 100644 --- a/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/chapter03/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; import static org.junit.Assert.*; -- cgit v1.2.3