diff options
Diffstat (limited to 'chapter05')
| -rw-r--r-- | chapter05/README.md | 68 | ||||
| -rw-r--r-- | chapter05/src/main/java/com/seaofnodes/simple/Parser.java | 10 | ||||
| -rw-r--r-- | chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java | 15 |
3 files changed, 63 insertions, 30 deletions
diff --git a/chapter05/README.md b/chapter05/README.md index bea9545b..8929dfad 100644 --- a/chapter05/README.md +++ b/chapter05/README.md @@ -31,47 +31,65 @@ Here is a recap of the nodes introduced in previous chapters: Following new nodes are introduced in this chapter: -| Node Name | Type | Chapter | Description | Inputs | Value | -|-----------|---------|---------|----------------------------------------------------------------------|------------------------------------------------------------------------------------------------|---------------------------------------------------------------| -| If | Control | 5 | Represents an `if` condition, sub type of `MultiNode` | A control node and a data predicate node | A tuple of two values, one for true branch, another for false | -| Region | Control | 5 | Represents a merge point from multiple control flow | An input for each control flow that is merging | Merged control | -| Phi | Data | 5 | Represents the phi function that picks a value based on control flow | A region control node, and multiple data nodes that provide values from multiple control flows | Result is the extracted value depending on control flow taken | -| Stop | Control | 5 | Represents termination of the program | One or more Return nodes | None | +| Node Name | Type | Chapter | Description | Inputs | Value | +|-----------|---------|---------|----------------------------------------------------|------------------------------------------------|----------------------------------------------------| +| If | Control | 5 | A branching test, sub type of `MultiNode` | A control node and a data predicate node | A tuple of two values: one for true, one for false | +| Region | Control | 5 | A merge point for multiple control flow | An input for each control flow that is merging | Merged control | +| Phi | Data | 5 | A phi function picks a value based on control flow | A Region, and data nodes for each control path | Depends on control flow path taken | +| Stop | Control | 5 | Termination of the program | One or more Return nodes | None | ## `If` Nodes -`If` node takes in both control and data (predicate expression) and routes the control token to one of the two control flows, represented by the `Proj` nodes. +`If` node takes in both control and data (predicate expression) and routes the +control token to one of the two control flows, represented by true and false +`Proj` nodes. ## `Phi` Nodes -The `Phi` reads in both data and control, and outputs a data value. The control input to the `Phi` points to a `Region` node. The data inputs to the `Phi` are one each for the control inputs to that `Region`. -The result computed by a `Phi` depends both on the data and the matching control input. At most one control input to the `Region` can be active at a time. The `Phi` passes through the data value from the matching input [[1]](#1). +A `Phi` reads in both data and control, and outputs a data value. The control +input to the `Phi` points to a `Region` node. The data inputs to the `Phi` are +one each for the control inputs to that `Region`. The result computed by a +`Phi` depends both on the data and the matching control input. At most one +control input to the `Region` can be active at a time, and the `Phi` passes +through the data value from the matching input [[1]](#1). ## `Region` Nodes -`Region` nodes were originally introduced to replace Basic Blocks in the IR [[3]](#3). However, we do not assign a `Region` to every node in the graph; we insert a `Region` node at a merge point where it takes control from each predecessor control edge, and produces -a merged control as output. Data flows via `Phi` nodes at these merge points. +`Region` nodes were originally introduced to replace Basic Blocks in the IR +[[3]](#3). However, we do not assign a `Region` to every node in the graph; we +insert a `Region` node at a merge point where it takes control from each +predecessor control edge, and produces a merged control as output. Data flows +via `Phi` nodes at these merge points. ## Parsing of `If` statement -When we parse an `if` statement, the control flow splits at that point. We must track the names being updated in each part of the `if` statement, and then merge them at the end. -The implementation follows the description in [[2]](#2). +When we parse an `if` statement, the control flow splits at that point. We +must track the names being updated in each part of the `if` statement, and then +merge them at the end. The implementation follows the description in +[[2]](#2). This involves following: -* We create an `IfNode` with the current control token, i.e. the node mapped to `$ctrl`, and the `if` predicate expression as inputs. -* We add two `ProjNodes` - one for the `True` branch (call if `ifT`), and the other for the `False` branch (call it `ifF`) - these extract values from the tuple result of the `IfNode`. -* We duplicate the current `ScopeNode`. The duplicated `ScopeNode` contains all the stack levels as the original, and moreover the new node is added as a user of all the names that are currently bound. -* The original `ScopeNode` is saved. -* We set the duplicate `ScopeNode` as current. -* We set control token to the `True` projection node `ifT`. -* We parse the true branch of the `if` statement. -* We reset the original `ScopeNode` as current. -* We set control token to the `False` projection node `ifF`. -* If there is an `else` statement we parse it. -* At this point we have two `ScopeNode`s; the original one, potentially updated by the `False` branch, and the duplicate one, potentially updated by the `True` branch. +* We create an `IfNode` with the current control token, i.e. the node mapped to + `$ctrl`, and the `if` predicate expression as inputs. +* We add two `ProjNodes` - one for the `True` branch (call if `ifT`), and the + other for the `False` branch (call it `ifF`) - these extract values from the + tuple result of the `IfNode`. +* We duplicate the current `ScopeNode`. The duplicated `ScopeNode` contains + all the same symbol tables as the original, and has the same edges. +* We set control token to the `True` projection node `ifT`, and parse the true + branch of the `if` statement. +* We reset the dupped `ScopeNode` as current. +* We set control token to the `False` projection node `ifF`, and if there is an + `else` statement we parse it. +* At this point we have two `ScopeNode`s; the original one, potentially updated + by the `True` branch, and the duplicate one, potentially updated by the + `False` branch. * We create a `Region` node to represent a merge point. -* We compare the two `ScopeNode`s. We create `Phi` nodes for any names whose bindings differ. The `Phi` nodes take the `Region` node as the control input and the two data nodes from each of the `ScopeNode`s. The name binding is updated to point to the `Phi` node. +* We *merge* the two `ScopeNode`s. We create `Phi` nodes for any names whose + bindings differ. The `Phi` nodes take the `Region` node as the control input + and the two data nodes from each of the `ScopeNode`s. The name binding is + updated to point to the `Phi` node. * Finally, we set the `Region` node as the control token, and discard the duplicated `ScopeNode`. ## Example diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java index 3e832610..a23f8d70 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java @@ -280,17 +280,19 @@ public class Parser { * Parse a primary expression: * * <pre> - * primaryExpr : integerLiteral | Identifier | '(' expression ')' + * primaryExpr : integerLiteral | Identifier | true | false | '(' expression ')' * </pre> */ private Node parsePrimary() { - if (_lexer.isNumber()) return parseIntegerLiteral(); - if (match("(")) return require(parseExpression(), ")"); + if( _lexer.isNumber() ) return parseIntegerLiteral(); + if( match("(") ) return require(parseExpression(), ")"); + if( match("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole(); + if( match("false") ) return new ConstantNode(TypeInteger.constant(0)).peephole(); String name = requireId(); Node id = _scope.lookup(name); if( id==null ) throw error("Undefined name '" + name + "'"); - return id.peephole(); + return id; } /** diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java index e59d1dbd..8f09620e 100644 --- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -62,7 +62,14 @@ return c; StopNode ret = parser.parse(); assertEquals("return (Phi(Region31,(arg+1),(arg+3))+Phi(Region31,((arg*2)+3),(arg+2)));", ret.toString()); } - + + @Test + public void testChapter5Merge3() { + Parser parser = new Parser("int a=1; if( arg==1 ) if( arg==2 ) a=2; else a=3; else if( arg==3 ) a=4; else a=5; return a; #showGraph;", TypeInteger.BOT); + StopNode stop = parser.parse(); + assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString()); + } + @Test public void testChapter5HalfDef() { try { @@ -82,6 +89,12 @@ return c; assertEquals("Undefined name 'b'",e.getMessage()); } } + + @Test + public void testChapter5True() { + StopNode stop = new Parser("return true;").parse(); + assertEquals("return 1;",stop.toString()); + } @Test public void testChapter4Peephole() { |