From d438edc542ae524c69cd0a5259c76313cf3abc76 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sat, 28 Oct 2023 12:13:35 +0100 Subject: Add writeup of if statement parsing --- chapter05/README.md | 36 +++- chapter05/docs/05-graph1.gv | 85 ++++++++ chapter05/docs/05-graph1.svg | 220 ++++++++++++++++++++ chapter05/docs/05-graph2.gv | 77 +++++++ chapter05/docs/05-graph2.svg | 228 +++++++++++++++++++++ .../main/java/com/seaofnodes/simple/Parser.java | 1 + 6 files changed, 644 insertions(+), 3 deletions(-) create mode 100644 chapter05/docs/05-graph1.gv create mode 100644 chapter05/docs/05-graph1.svg create mode 100644 chapter05/docs/05-graph2.gv create mode 100644 chapter05/docs/05-graph2.svg diff --git a/chapter05/README.md b/chapter05/README.md index d0f475fa..c25e6aef 100644 --- a/chapter05/README.md +++ b/chapter05/README.md @@ -44,7 +44,7 @@ When we parse an `if` statement, the control flow splits at that point. We must This involves following: -* The `IfNode` is created with the current control token, i.e. the node mapped to `$ctrl` and the predicate expression as inputs. +* The `IfNode` is created with the current control token, i.e. the node mapped to `$ctrl`, and the 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 now create a duplicate of the current `ScopeNode`. The duplicated `ScopeNode` must have all the stack levels as the original, and moreover the new node must be a user of all the names that are currently bound. * The original `ScopeNode` is saved. @@ -54,11 +54,41 @@ This involves following: * 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 update by the `False` branch, and the duplicate one, potentially updated by the `True` branch. +* 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 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. +* 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. * Finally, we set the `Region` node as the control token, and discard the duplicated `ScopeNode`. ## Example +We show the graph for the following code snippet: +```java +int a = 1; +if (arg == 1) + a = arg+2; +else + a = arg-3; +return a; +``` + +### Before merging + +Following shows the graph just before we merge the two branches of the `if` statement in a `Region` node. + +![Graph1](./docs/05-graph1.svg) + +* Note the two `ScopeNode`s in the graph. +* One has its `$ctrl` pointing to the `True` projection, while the other has `$ctrl` pointing to `False` projection. +* Note that the binding of `a` is to the `Sub` node in the `False` branch, whereas `a` is bound to the `Add` node in the `True` branch. +* Thus `a` needs a `Phi` node. + +### After merging + +Below is the graph after we created a `Region` node and merged the two definitions of `a` in a `Phi` node. + +![Graph2](./docs/05-graph2.svg) + +* Observe that the duplicate `ScopeNode` has been discarded. +* The binding of `a` is now bound to the `Phi` node. +* The `Phi` node's inputs are the `Region` node and the `Add` node from the `True` branch, and `Sub` node from the `False` branch. diff --git a/chapter05/docs/05-graph1.gv b/chapter05/docs/05-graph1.gv new file mode 100644 index 00000000..99993814 --- /dev/null +++ b/chapter05/docs/05-graph1.gv @@ -0,0 +1,85 @@ +digraph chapter05 { +/* +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + #showGraph; +} +return a; +#showGraph; + +*/ + rankdir=BT; + subgraph cluster_Nodes { + Start1 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Con_5 [ label="#1" ]; + EQNode6 [ label="EQNode" ]; + If7 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_11 [ label="#2" ]; + Add12 [ label="Add" ]; + Con_13 [ label="#3" ]; + Sub14 [ label="Sub" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope20_0 { + Scope20_0 [label=< + + +
0$ctrlarg
>]; + subgraph cluster_Scope20_1 { + Scope20_1 [label=< + + +
1a
>]; + } + } + node [shape=plaintext]; + subgraph cluster_Scope21_0 { + Scope21_0 [label=< + + +
0$ctrlarg
>]; + subgraph cluster_Scope21_1 { + Scope21_1 [label=< + + +
1a
>]; + } + } + EQNode6 -> Start1:p1; + EQNode6 -> Con_5; + If7 -> Start1:p0 [color=red]; + If7 -> EQNode6; + Add12 -> Start1:p1; + Add12 -> Con_11; + Sub14 -> Start1:p1; + Sub14 -> Con_13; + edge [style=dashed color=cornflowerblue]; + Scope20_0:"Scope20_0_$ctrl" -> If7:p1; + Scope20_0:"Scope20_0_arg" -> Start1:p1; + Scope20_1:"Scope20_1_a" -> Sub14; + edge [style=dashed color=cornflowerblue]; + Scope21_0:"Scope21_0_$ctrl" -> If7:p0; + Scope21_0:"Scope21_0_arg" -> Start1:p1; + Scope21_1:"Scope21_1_a" -> Add12; +} \ No newline at end of file diff --git a/chapter05/docs/05-graph1.svg b/chapter05/docs/05-graph1.svg new file mode 100644 index 00000000..488a71cb --- /dev/null +++ b/chapter05/docs/05-graph1.svg @@ -0,0 +1,220 @@ + + + + + + +chapter05 + + +cluster_Nodes + + + +cluster_Scope20_0 + + + +cluster_Scope20_1 + + + +cluster_Scope21_0 + + + +cluster_Scope21_1 + + + + +Start1 + + +Start + + + +$ctrl + +arg + + + +Con_5 + +#1 + + + +EQNode6 + +EQNode + + + +EQNode6->Start1:p1 + + + + + +EQNode6->Con_5 + + + + + +If7 + + +If + + + +True + + +False + + + +If7->Start1:p0 + + + + + +If7->EQNode6 + + + + + +Con_11 + +#2 + + + +Add12 + +Add + + + +Add12->Start1:p1 + + + + + +Add12->Con_11 + + + + + +Con_13 + +#3 + + + +Sub14 + +Sub + + + +Sub14->Start1:p1 + + + + + +Sub14->Con_13 + + + + + +Scope20_0 + + +0 + +$ctrl + +arg + + + +Scope20_0:Scope20_0_arg->Start1:p1 + + + + + +Scope20_0:Scope20_0_$ctrl->If7:p1 + + + + + +Scope20_1 + + +1 + +a + + + +Scope20_1:Scope20_1_a->Sub14 + + + + + +Scope21_0 + + +0 + +$ctrl + +arg + + + +Scope21_0:Scope21_0_arg->Start1:p1 + + + + + +Scope21_0:Scope21_0_$ctrl->If7:p0 + + + + + +Scope21_1 + + +1 + +a + + + +Scope21_1:Scope21_1_a->Add12 + + + + + diff --git a/chapter05/docs/05-graph2.gv b/chapter05/docs/05-graph2.gv new file mode 100644 index 00000000..d2c819a8 --- /dev/null +++ b/chapter05/docs/05-graph2.gv @@ -0,0 +1,77 @@ +digraph chapter05 { +/* +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + #showGraph; +} +return a; +#showGraph; + +*/ + rankdir=BT; + subgraph cluster_Nodes { + Start1 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Con_5 [ label="#1" ]; + EQNode6 [ label="EQNode" ]; + If7 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_11 [ label="#2" ]; + Add12 [ label="Add" ]; + Con_13 [ label="#3" ]; + Sub14 [ label="Sub" ]; + Region15 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi16 [ label="Phi" ]; + Return17 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope20_0 { + Scope20_0 [label=< + + +
0$ctrlarg
>]; + subgraph cluster_Scope20_1 { + Scope20_1 [label=< + + +
1a
>]; + } + } + EQNode6 -> Start1:p1; + EQNode6 -> Con_5; + If7 -> Start1:p0 [color=red]; + If7 -> EQNode6; + Add12 -> Start1:p1; + Add12 -> Con_11; + Sub14 -> Start1:p1; + Sub14 -> Con_13; + Region15 -> If7:p0 [color=red]; + Region15 -> If7:p1 [color=red]; + Phi16 -> Region15 [color=red]; + Phi16 -> Add12; + Phi16 -> Sub14; + Return17 -> Region15 [color=red]; + Return17 -> Phi16; + edge [style=dashed color=cornflowerblue]; + Scope20_0:"Scope20_0_arg" -> Start1:p1; + Scope20_1:"Scope20_1_a" -> Phi16; +} \ No newline at end of file diff --git a/chapter05/docs/05-graph2.svg b/chapter05/docs/05-graph2.svg new file mode 100644 index 00000000..70d1a8c5 --- /dev/null +++ b/chapter05/docs/05-graph2.svg @@ -0,0 +1,228 @@ + + + + + + +chapter05 + + +cluster_Nodes + + + +cluster_Scope20_0 + + + +cluster_Scope20_1 + + + + +Start1 + + +Start + + + +$ctrl + +arg + + + +Con_5 + +#1 + + + +EQNode6 + +EQNode + + + +EQNode6->Start1:p1 + + + + + +EQNode6->Con_5 + + + + + +If7 + + +If + + + +True + + +False + + + +If7->Start1:p0 + + + + + +If7->EQNode6 + + + + + +Con_11 + +#2 + + + +Add12 + +Add + + + +Add12->Start1:p1 + + + + + +Add12->Con_11 + + + + + +Con_13 + +#3 + + + +Sub14 + +Sub + + + +Sub14->Start1:p1 + + + + + +Sub14->Con_13 + + + + + +Region15 + +Region + + + +Region15->If7:p0 + + + + + +Region15->If7:p1 + + + + + +Phi16 + +Phi + + + +Phi16->Add12 + + + + + +Phi16->Sub14 + + + + + +Phi16->Region15 + + + + + +Return17 + +Return + + + +Return17->Region15 + + + + + +Return17->Phi16 + + + + + +Scope20_0 + + +0 + +$ctrl + +arg + + + +Scope20_0:Scope20_0_arg->Start1:p1 + + + + + +Scope20_1 + + +1 + +a + + + +Scope20_1:Scope20_1_a->Phi16 + + + + + diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java index 2953ec26..b141d7ac 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java @@ -146,6 +146,7 @@ public class Parser { // Create region node and merge scopes // If a var is in both scopes and has different binding then we need to create PhiNode for it // After merge _scope remains, and ifScope is discarded + System.out.println(new GraphVisualizer().generateDotOutput(this)); RegionNode region = mergeScopes(ifT, ifScope, ifF, _scope); updateCtrlToken(region); // Now region becomes the ctrl token ifScope.clear(); // Clean up ifScope -- cgit v1.2.3