From 1f675fd160ef331574b998ec9691673abcfb7c70 Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Mon, 30 Oct 2023 21:55:01 +0000 Subject: Update the description of Region node Update visuals Update chapter list --- README.md | 12 +- chapter05/README.md | 35 ++++- chapter05/docs/05-graph1.gv | 77 +++++----- chapter05/docs/05-graph1.svg | 274 ++++++++++++++++++------------------ chapter05/docs/05-graph2.gv | 80 +++++------ chapter05/docs/05-graph2.svg | 326 ++++++++++++++++++++----------------------- 6 files changed, 395 insertions(+), 409 deletions(-) diff --git a/README.md b/README.md index 1f57c4e8..d8f99553 100644 --- a/README.md +++ b/README.md @@ -33,12 +33,12 @@ The simple language will be a small subset of C. * [Chapter 3](chapter03/README.md): Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a constant. * [Chapter 4](chapter04/README.md): A non-constant external variable input named `arg`. Binary and Comparison operators involving constants and `arg`. Non-zero values will be truthy. Peephole optimizations involving algebraic simplifications. -* [Chapter 5](chapter05/README.md): `if` statement. CFG construction, peephole optimization around dead control flow. -* Chapter 6: `while` statement. -* Chapter 7: Global Value Numbering. -* Chapter 8: Functions and calls. -* Chapter 9: Boolean operators `&&`, `||` and `!` including short circuit. -* Chapter 10: `float` type. +* [Chapter 5](chapter05/README.md): `if` statement. CFG construction. +* Chapter 6: Peephole optimization around dead control flow. +* Chapter 7: `while` statement. +* Chapter 8: Global Value Numbering. +* Chapter 9: Functions and calls. +* Chapter 10: Boolean operators `&&`, `||` and `!` including short circuit. * Chapter 11: Memory effects: general memory edges in SSA. Peephole optimization around load-after-store/store-after-store. * Chapter 12: Equivalence class aliasing, fine grained peephole optimizations. Free ptr-to analysis in SoN; but does not diff --git a/chapter05/README.md b/chapter05/README.md index 8929dfad..32f57fea 100644 --- a/chapter05/README.md +++ b/chapter05/README.md @@ -55,9 +55,30 @@ 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 +> Every instruction has a control input from a basic block. If the control input is an edge +> in our abstract graph, then the basic block must be a node in the abstract graph. So we +> define a REGION instruction to replace a basic block. A REGION instruction takes +> control from each predecessor block as input and produces a merged control as an output [[3]](#3). + +However: + +> We can remove the control dependence for any given Node simply by replacing the +> pointer value with the special value NULL. This operation only makes sense for Nodes +> that represent data computations. PHI, IF, JUMP and STOP Nodes all require the control +> input for semantic correctness. REGION Nodes require several control inputs (one per +> CFG input to the basic block they represent). Almost all other Nodes can live without a +> control dependence. A data computation without a control dependence does not exactly +> reside in any particular basic block. Its correct behavior depends solely on the remaining +> data dependences. It, and the Nodes that depend on it or on which it depends, exists in a +> “sea” of Nodes, with little control structure. + +> The “sea” of Nodes is useful for optimization, but does not represent any traditional +> intermediate representation such as a CFG. We need a way to serialize the graph and get +> back the control dependences. We do this with a simple global code motion algorithm [[4]](#4). + +Thus, we do not associate a control edge on every data 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. @@ -135,6 +156,10 @@ Combining Analyses, Combining Optimizations, 132. Click, C. (1995). Combining Analyses, Combining Optimizations, 102-103. -[3] +[3] Click, C. (1995). -Combining Analyses, Combining Optimizations, 129. \ No newline at end of file +Combining Analyses, Combining Optimizations, 129. + +[4] +Click, C. (1995). +Combining Analyses, Combining Optimizations, 86. \ No newline at end of file diff --git a/chapter05/docs/05-graph1.gv b/chapter05/docs/05-graph1.gv index 99993814..6b2a5788 100644 --- a/chapter05/docs/05-graph1.gv +++ b/chapter05/docs/05-graph1.gv @@ -2,18 +2,19 @@ digraph chapter05 { /* int a = 1; if (arg == 1) - a = arg+2; + a = arg+2; else { - a = arg-3; - #showGraph; + a = arg-3; + #showGraph; } return a; -#showGraph; */ rankdir=BT; + ordering="in"; + concentrate="true"; subgraph cluster_Nodes { - Start1 [ shape=plaintext label=< + Start2 [ shape=plaintext label=<
Start
@@ -23,9 +24,9 @@ return a;
> ]; - Con_5 [ label="#1" ]; - EQNode6 [ label="EQNode" ]; - If7 [ shape=plaintext label=< + Con_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + If9 [ shape=plaintext label=<
If
@@ -35,51 +36,51 @@ return a;
> ]; - Con_11 [ label="#2" ]; - Add12 [ label="Add" ]; - Con_13 [ label="#3" ]; - Sub14 [ label="Sub" ]; + Con_13 [ label="#2" ]; + Add14 [ label="+" ]; + Con_15 [ label="#3" ]; + Sub16 [ label="-" ]; } node [shape=plaintext]; - subgraph cluster_Scope20_0 { - Scope20_0 [label=< + subgraph cluster_Scope1_0 { + Scope1_0 [label=< - +
0$ctrlarg
0$ctrlarg
>]; - subgraph cluster_Scope20_1 { - Scope20_1 [label=< + subgraph cluster_Scope1_1 { + Scope1_1 [label=< - +
1a
1a
>]; } } node [shape=plaintext]; - subgraph cluster_Scope21_0 { - Scope21_0 [label=< + subgraph cluster_Scope12_0 { + Scope12_0 [label=< - +
0$ctrlarg
0$ctrlarg
>]; - subgraph cluster_Scope21_1 { - Scope21_1 [label=< + subgraph cluster_Scope12_1 { + Scope12_1 [label=< - +
1a
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; + EQNode8 -> Start2:p1; + EQNode8 -> Con_7; + If9 -> Start2:p0 [color=red]; + If9 -> EQNode8; + Add14 -> Start2:p1; + Add14 -> Con_13; + Sub16 -> Start2:p1; + Sub16 -> Con_15; 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; + Scope1_0:"Scope1_0_$ctrl" -> If9:p0; + Scope1_0:"Scope1_0_arg" -> Start2:p1; + Scope1_1:"Scope1_1_a" -> Add14; 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; + Scope12_0:"Scope12_0_$ctrl" -> If9:p1; + Scope12_0:"Scope12_0_arg" -> Start2:p1; + Scope12_1:"Scope12_1_a" -> Sub16; } \ No newline at end of file diff --git a/chapter05/docs/05-graph1.svg b/chapter05/docs/05-graph1.svg index 488a71cb..ac1f91fc 100644 --- a/chapter05/docs/05-graph1.svg +++ b/chapter05/docs/05-graph1.svg @@ -4,145 +4,145 @@ - + chapter05 - + cluster_Nodes - + -cluster_Scope20_0 +cluster_Scope1_0 -cluster_Scope20_1 +cluster_Scope1_1 -cluster_Scope21_0 - +cluster_Scope12_0 + -cluster_Scope21_1 - +cluster_Scope12_1 + - + -Start1 - - -Start - - - -$ctrl - -arg - - +Start2 + + +Start + + + +$ctrl + +arg + + -Con_5 - -#1 +Con_7 + +#1 - + -EQNode6 - -EQNode +EQNode8 + +== - + -EQNode6->Start1:p1 - - +EQNode8->Start2:p1 + + - + -EQNode6->Con_5 - - +EQNode8->Con_7 + + - + -If7 - - -If - - - -True - - -False - - +If9 + + +If + + + +True + + +False + + -If7->Start1:p0 - - +If9->Start2:p0 + + - + -If7->EQNode6 - - +If9->EQNode8 + + - + -Con_11 - -#2 +Con_13 + +#2 - + -Add12 - -Add +Add14 + ++ - + -Add12->Start1:p1 - - +Add14->Start2:p1 + + - + -Add12->Con_11 - - +Add14->Con_13 + + - + -Con_13 - -#3 +Con_15 + +#3 - + -Sub14 - -Sub +Sub16 + +- - + -Sub14->Start1:p1 - - +Sub16->Start2:p1 + + - + -Sub14->Con_13 - - +Sub16->Con_15 + + - + -Scope20_0 +Scope1_0 0 @@ -151,70 +151,70 @@ arg - + -Scope20_0:Scope20_0_arg->Start1:p1 - - +Scope1_0:Scope1_0_arg->Start2:p1 + + - + -Scope20_0:Scope20_0_$ctrl->If7:p1 - - +Scope1_0:Scope1_0_$ctrl->If9:p0 + + - + -Scope20_1 +Scope1_1 1 a - + -Scope20_1:Scope20_1_a->Sub14 - - +Scope1_1:Scope1_1_a->Add14 + + - + -Scope21_0 - - -0 - -$ctrl - -arg - - +Scope12_0 + + +0 + +$ctrl + +arg + + -Scope21_0:Scope21_0_arg->Start1:p1 - - +Scope12_0:Scope12_0_arg->Start2:p1 + + - + -Scope21_0:Scope21_0_$ctrl->If7:p0 - - +Scope12_0:Scope12_0_$ctrl->If9:p1 + + - + -Scope21_1 - - -1 - -a - - +Scope12_1 + + +1 + +a + + -Scope21_1:Scope21_1_a->Add12 - - +Scope12_1:Scope12_1_a->Sub16 + + diff --git a/chapter05/docs/05-graph2.gv b/chapter05/docs/05-graph2.gv index d2c819a8..55702eea 100644 --- a/chapter05/docs/05-graph2.gv +++ b/chapter05/docs/05-graph2.gv @@ -2,18 +2,19 @@ digraph chapter05 { /* int a = 1; if (arg == 1) - a = arg+2; + a = arg+2; else { - a = arg-3; - #showGraph; + a = arg-3; + #showGraph; } return a; -#showGraph; */ rankdir=BT; + ordering="in"; + concentrate="true"; subgraph cluster_Nodes { - Start1 [ shape=plaintext label=< + Start2 [ shape=plaintext label=<
Start
@@ -23,9 +24,10 @@ return a;
> ]; - Con_5 [ label="#1" ]; - EQNode6 [ label="EQNode" ]; - If7 [ shape=plaintext label=< + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + If9 [ shape=plaintext label=<
If
@@ -35,43 +37,29 @@ return a;
> ]; - 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" ]; + Con_13 [ label="#2" ]; + Add14 [ label="+" ]; + Con_15 [ label="#3" ]; + Sub16 [ label="-" ]; + Region17 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a18 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Return19 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Phi_a18;} } - 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; + Stop3 -> Return19 [color=red]; + EQNode8 -> Start2:p1; + EQNode8 -> Con_7; + If9 -> Start2:p0 [color=red]; + If9 -> EQNode8; + Add14 -> Start2:p1; + Add14 -> Con_13; + Sub16 -> Start2:p1; + Sub16 -> Con_15; + Region17 -> If9:p0 [color=red]; + Region17 -> If9:p1 [color=red]; + Phi_a18 -> Region17 [color=red]; + Phi_a18 -> Add14; + Phi_a18 -> Sub16; + Return19 -> Region17 [color=red]; + Return19 -> Phi_a18; } \ No newline at end of file diff --git a/chapter05/docs/05-graph2.svg b/chapter05/docs/05-graph2.svg index 70d1a8c5..07a07ced 100644 --- a/chapter05/docs/05-graph2.svg +++ b/chapter05/docs/05-graph2.svg @@ -4,225 +4,197 @@ - - + + chapter05 - + cluster_Nodes - + - -cluster_Scope20_0 - - - -cluster_Scope20_1 - - - + -Start1 - - -Start - - - -$ctrl - -arg - - +Start2 + + +Start + + + +$ctrl + +arg + + -Con_5 - -#1 +Stop3 + +Stop - - -EQNode6 - -EQNode + + +Return19 + +Return - + -EQNode6->Start1:p1 - - +Stop3->Return19 + + - - -EQNode6->Con_5 - - + + +Con_7 + +#1 - + -If7 - - -If - - - -True - - -False - - +EQNode8 + +== + + + +EQNode8->Start2:p1 + + + + -If7->Start1:p0 - - +EQNode8->Con_7 + + - + + +If9 + + +If + + + +True + + +False + + -If7->EQNode6 - - +If9->Start2:p0 + + - - -Con_11 - -#2 + + +If9->EQNode8 + + - + -Add12 - -Add +Con_13 + +#2 - - -Add12->Start1:p1 - - + + +Add14 + ++ - + -Add12->Con_11 - - +Add14->Start2:p1 + + + - - -Con_13 - -#3 + + +Add14->Con_13 + + - + -Sub14 - -Sub +Con_15 + +#3 - - -Sub14->Start1:p1 - - + + +Sub16 + +- - + -Sub14->Con_13 - - +Sub16->Start2:p1 + - - -Region15 - -Region - - + -Region15->If7:p0 - - - - - -Region15->If7:p1 - - +Sub16->Con_15 + + - + -Phi16 - -Phi +Region17 + +Region - - -Phi16->Add12 - - - - - -Phi16->Sub14 - - + + +Region17->If9:p0 + + - + -Phi16->Region15 - - +Region17->If9:p1 + + - + -Return17 - -Return +Phi_a18 + +φ_a + + + +Phi_a18->Add14 + + - + -Return17->Region15 - - +Phi_a18->Sub16 + + + + + +Phi_a18->Region17 + + - + -Return17->Phi16 - - +Return19->Region17 + + - - -Scope20_0 - - -0 - -$ctrl - -arg - - + -Scope20_0:Scope20_0_arg->Start1:p1 - - - - - -Scope20_1 - - -1 - -a - - - -Scope20_1:Scope20_1_a->Phi16 - - +Return19->Phi_a18 + + -- cgit v1.2.3