From e31c37890a86aedfb209cf543baf05b1b60a27d2 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Mon, 29 Apr 2024 00:11:36 +0100 Subject: Ch10update (#75) * Store-after-Store peep * Load-after-Store peephole * Fix graph viz mem edge color bug * Scalar replace loop carried dependence * #67 Dead Not node hanging around - if we add a Not in the upcast then add it to the IterPeeps worklist to ensure it gets cleaned up. We don't see the Not node in the parser hence we cannot do a peep on it there. * #67 Update visuals. Add description of Store-Store and Store-Load peeps. Add examples. * #67 Undo the change that wasn't supposed to be committed! * #67 Update description of the Store-Store and Store-Load peepholes --------- Co-authored-by: Cliff Click --- chapter10/docs/build-graphs.sh | 3 + chapter10/docs/example1.drawio | 234 ---------------------- chapter10/docs/example1.gv | 72 ++++--- chapter10/docs/example1.svg | 435 +++++++++++++++++++---------------------- chapter10/docs/example2a.gv | 65 ++++++ chapter10/docs/example2a.svg | 249 +++++++++++++++++++++++ chapter10/docs/example2b.gv | 56 ++++++ chapter10/docs/example2b.svg | 189 ++++++++++++++++++ chapter10/docs/example2c.gv | 53 +++++ chapter10/docs/example2c.svg | 168 ++++++++++++++++ 10 files changed, 1020 insertions(+), 504 deletions(-) delete mode 100644 chapter10/docs/example1.drawio create mode 100644 chapter10/docs/example2a.gv create mode 100644 chapter10/docs/example2a.svg create mode 100644 chapter10/docs/example2b.gv create mode 100644 chapter10/docs/example2b.svg create mode 100644 chapter10/docs/example2c.gv create mode 100644 chapter10/docs/example2c.svg (limited to 'chapter10/docs') diff --git a/chapter10/docs/build-graphs.sh b/chapter10/docs/build-graphs.sh index 853f50f7..8f6afed7 100644 --- a/chapter10/docs/build-graphs.sh +++ b/chapter10/docs/build-graphs.sh @@ -1,3 +1,6 @@ dot -Tsvg example1.gv > example1.svg +dot -Tsvg example2a.gv > example2a.svg +dot -Tsvg example2b.gv > example2b.svg +dot -Tsvg example2c.gv > example2c.svg dot -Tsvg lattice.gv > lattice.svg diff --git a/chapter10/docs/example1.drawio b/chapter10/docs/example1.drawio deleted file mode 100644 index b3b408c5..00000000 --- a/chapter10/docs/example1.drawio +++ /dev/null @@ -1,234 +0,0 @@ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - \ No newline at end of file diff --git a/chapter10/docs/example1.gv b/chapter10/docs/example1.gv index fcc24154..cbb12cb5 100644 --- a/chapter10/docs/example1.gv +++ b/chapter10/docs/example1.gv @@ -1,8 +1,7 @@ digraph chapter10 { /* -struct Vec2D { int x; int y; } - -Vec2D v = new Vec2D; +struct Vector2D { int x; int y; } +Vector2D v = new Vector2D; v.x = 1; if (arg) v.y = 2; @@ -12,7 +11,6 @@ return v; */ rankdir=BT; - ordering="in"; concentrate="true"; compound="true"; subgraph cluster_Nodes { @@ -21,18 +19,17 @@ return v; Start - +
$ctrlarg$Vec2D_x$Vec2D_y
$ctrlarg$2$3
> ]; Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; - New8 [ label="new Vec2D" ]; + new8 [ label="new Vector2D" ]; Con_9 [ label="#0" ]; - Store10 [ label="Store" ]; - Store11 [ label="Store" ]; + Store11 [ label=".y =" ]; Con_12 [ label="#1" ]; - Store13 [ label="Store" ]; + Store13 [ label=".x =" ]; If14 [ shape=plaintext label=< @@ -44,41 +41,38 @@ return v;
If
> ]; Con_18 [ label="#2" ]; - Store19 [ label="Store" ]; - Con_20 [ label="#3" ]; - Store21 [ label="Store" ]; - Region22 [ shape=box style=filled fillcolor=yellow label="Region" ]; - Phi_Vec2D_y23 [ style=filled fillcolor=lightyellow label="φ_$Vec2D_y" ]; - Return24 [ shape=box style=filled fillcolor=yellow label="Return" ]; - { rank=same; Region22;Phi_Vec2D_y23;} + Store19 [ label=".y =" ]; + Con_22 [ label="#3" ]; + Store23 [ label=".y =" ]; + Region24 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_326 [ style=filled fillcolor=lightyellow label="φ_$3" ]; + Return27 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region24;Phi_326;} } edge [ fontname=Helvetica, fontsize=8 ]; - Stop3 -> Return24[taillabel=0 color=red]; - New8 -> Start2:p0[taillabel=0 color=green]; - Store10 -> Start2:p2[taillabel=1]; - Store10 -> New8[taillabel=2]; - Store10 -> Con_9[taillabel=3]; - Store11 -> Start2:p3[taillabel=1]; - Store11 -> New8[taillabel=2]; + Stop3 -> Return27[taillabel=0 color=red]; + new8 -> Start2:p0[taillabel=0 color=green]; + Store11 -> Start2:p3[taillabel=1 color=blue]; + Store11 -> new8[taillabel=2]; Store11 -> Con_9[taillabel=3]; - Store13 -> Store10[taillabel=1]; - Store13 -> New8[taillabel=2]; + Store13 -> Start2:p2[taillabel=1 color=blue]; + Store13 -> new8[taillabel=2]; Store13 -> Con_12[taillabel=3]; If14 -> Start2:p0[taillabel=0 color=red]; If14 -> Start2:p1[taillabel=1]; - Store19 -> Store11[taillabel=1]; - Store19 -> New8[taillabel=2]; + Store19 -> Store11[taillabel=1 color=blue]; + Store19 -> new8[taillabel=2]; Store19 -> Con_18[taillabel=3]; - Store21 -> Store11[taillabel=1]; - Store21 -> New8[taillabel=2]; - Store21 -> Con_20[taillabel=3]; - Region22 -> If14:p0[taillabel=1 color=red]; - Region22 -> If14:p1[taillabel=2 color=red]; - Phi_Vec2D_y23 -> Region22 [style=dotted taillabel=0]; - Phi_Vec2D_y23 -> Store19[taillabel=1]; - Phi_Vec2D_y23 -> Store21[taillabel=2 constraint=false]; - Return24 -> Region22[taillabel=0 color=red]; - Return24 -> New8[taillabel=1]; - Return24 -> Store13[taillabel=2]; - Return24 -> Phi_Vec2D_y23[taillabel=3]; + Store23 -> Store11[taillabel=1 color=blue]; + Store23 -> new8[taillabel=2]; + Store23 -> Con_22[taillabel=3]; + Region24 -> If14:p0[taillabel=1 color=red]; + Region24 -> If14:p1[taillabel=2 color=red]; + Phi_326 -> Region24 [style=dotted taillabel=0]; + Phi_326 -> Store19[taillabel=1 color=blue]; + Phi_326 -> Store23[taillabel=2 color=blue constraint=false]; + Return27 -> Region24[taillabel=0 color=red]; + Return27 -> new8[taillabel=1]; + Return27 -> Store13[taillabel=2 color=blue]; + Return27 -> Phi_326[taillabel=3 color=blue]; } diff --git a/chapter10/docs/example1.svg b/chapter10/docs/example1.svg index 0c2dfa4d..6f493e7e 100644 --- a/chapter10/docs/example1.svg +++ b/chapter10/docs/example1.svg @@ -4,318 +4,291 @@ - + chapter10 - + cluster_Nodes - + Start2 - - -Start - - - -$ctrl - -arg - -$Vector2D_x - -$Vector2D_y + + +Start + + + +$ctrl + +arg + +$2 + +$3 Stop3 - -Stop + +Stop - - -Return24 - -Return + + +Return27 + +Return - + -Stop3->Return24 - - -0 +Stop3->Return27 + + +0 - + -New8 - -New Ptr(Vector2D) +new8 + +new Vector2D - + -New8->Start2:p0 - - -0 +new8->Start2:p0 + + +0 Con_9 - -#0 - - - -Store10 - -Store - - - -Store10->Start2:p2 - - -1 - - - -Store10->New8 - - -2 - - - -Store10->Con_9 - - -3 + +#0 - + Store11 - -Store + +.y = - + Store11->Start2:p3 - - -1 + + +1 - - -Store11->New8 - - -2 + + +Store11->new8 + + +2 - + Store11->Con_9 - - -3 + + +3 - + Con_12 - -#1 + +#1 - + Store13 - -Store + +.x = - - -Store13->New8 - - -2 + + +Store13->Start2:p2 + + +1 - - -Store13->Store10 - - -1 + + +Store13->new8 + + +2 - + Store13->Con_12 - - -3 + + +3 - + If14 - - -If - - - -True - - -False + + +If + + + +True + + +False - + If14->Start2:p0 - - -0 - - - -If14->Start2:p1 - - -1 + + +0 - + Con_18 - -#2 + +#2 - + Store19 - -Store + +.y = - - -Store19->New8 - - -2 + + +Store19->new8 + + + +2 - + Store19->Store11 - - -1 + + +1 - + Store19->Con_18 - - -3 + + +3 + + + +Con_22 + +#3 - + -Con_20 - -#3 +Store23 + +.y = - - -Store21 - -Store + + +Store23->new8 + +2 - - -Store21->New8 - - -2 + + +Store23->Store11 + + +1 + + + +Store23->Con_22 + + +3 + + + +Region24 + +Region - + -Store21->Store11 - - -1 +Region24->If14:p0 + + +1 - - -Store21->Con_20 - - -3 + + +Region24->If14:p1 + + +2 - + -Region22 - -Region +Phi_326 + +φ_$3 - + -Region22->If14:p0 - - -1 - - - -Phi_Vector2D_y23 - -φ_$Vector2D_y +Phi_326->Store19 + + +1 + + + +Phi_326->Store23 + + +2 + + + +Phi_326->Region24 + + +0 - + -Phi_Vector2D_y23->Store19 - - -1 +Return27->new8 + + +1 - + -Phi_Vector2D_y23->Store21 - - -2 +Return27->Store13 + + +2 - + -Phi_Vector2D_y23->Region22 - - -0 - - - -Return24->New8 - - -1 - - - -Return24->Store13 - - -2 - - +Return27->Region24 + + +0 + + -Return24->Region22 - - -0 - - - -Return24->Phi_Vector2D_y23 - - -3 +Return27->Phi_326 + + +3 diff --git a/chapter10/docs/example2a.gv b/chapter10/docs/example2a.gv new file mode 100644 index 00000000..23f31bf8 --- /dev/null +++ b/chapter10/docs/example2a.gv @@ -0,0 +1,65 @@ +digraph chapter10 { +/* +struct Bar { + int a; + int b; +} +struct Foo { + int x; +} +Foo? foo = null; +Bar bar = new Bar; +bar.a = 1; +bar.a = 2; +return bar.a; + +*/ + rankdir=BT; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl$2$3$4
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + new10 [ label="new Bar" ]; + Con_11 [ label="#0" ]; + Store12 [ label=".a =" ]; + Store13 [ label=".b =" ]; + Con_14 [ label="#1" ]; + Store15 [ label=".a =" ]; + Con_16 [ label="#2" ]; + Store17 [ label=".a =" ]; + Load18 [ label=".a" ]; + Return19 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return19[taillabel=0 color=red]; + new10 -> Start2:p0[taillabel=0 color=green]; + Store12 -> Start2:p2[taillabel=1 color=blue]; + Store12 -> new10[taillabel=2]; + Store12 -> Con_11[taillabel=3]; + Store13 -> Start2:p3[taillabel=1 color=blue]; + Store13 -> new10[taillabel=2]; + Store13 -> Con_11[taillabel=3]; + Store15 -> Store12[taillabel=1 color=blue]; + Store15 -> new10[taillabel=2]; + Store15 -> Con_14[taillabel=3]; + Store17 -> Store15[taillabel=1 color=blue]; + Store17 -> new10[taillabel=2]; + Store17 -> Con_16[taillabel=3]; + Load18 -> Store17[taillabel=1 color=blue]; + Load18 -> new10[taillabel=2]; + Return19 -> Start2:p0[taillabel=0 color=red]; + Return19 -> Load18[taillabel=1]; + Return19 -> Store17[taillabel=2 color=blue]; + Return19 -> Store13[taillabel=3 color=blue]; + Return19 -> Start2:p4[taillabel=4 color=blue]; +} diff --git a/chapter10/docs/example2a.svg b/chapter10/docs/example2a.svg new file mode 100644 index 00000000..9f069ad4 --- /dev/null +++ b/chapter10/docs/example2a.svg @@ -0,0 +1,249 @@ + + + + + + +chapter10 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +$2 + +$3 + +$4 + + + +Stop3 + +Stop + + + +Return19 + +Return + + + +Stop3->Return19 + + +0 + + + +new10 + +new Bar + + + +new10->Start2:p0 + + +0 + + + +Con_11 + +#0 + + + +Store12 + +.a = + + + +Store12->Start2:p2 + + +1 + + + +Store12->new10 + + +2 + + + +Store12->Con_11 + + +3 + + + +Store13 + +.b = + + + +Store13->Start2:p3 + + +1 + + + +Store13->new10 + + +2 + + + +Store13->Con_11 + + +3 + + + +Con_14 + +#1 + + + +Store15 + +.a = + + + +Store15->new10 + + +2 + + + +Store15->Store12 + + +1 + + + +Store15->Con_14 + + +3 + + + +Con_16 + +#2 + + + +Store17 + +.a = + + + +Store17->new10 + +2 + + + +Store17->Store15 + + +1 + + + +Store17->Con_16 + + +3 + + + +Load18 + +.a + + + +Load18->new10 + + + +2 + + + +Load18->Store17 + + +1 + + + +Return19->Start2:p0 + + +0 + + + +Return19->Start2:p4 + + +4 + + + +Return19->Store13 + + + +3 + + + +Return19->Store17 + + + +2 + + + +Return19->Load18 + + +1 + + + diff --git a/chapter10/docs/example2b.gv b/chapter10/docs/example2b.gv new file mode 100644 index 00000000..a7d4ac62 --- /dev/null +++ b/chapter10/docs/example2b.gv @@ -0,0 +1,56 @@ +digraph chapter10 { +/* +struct Bar { + int a; + int b; +} +struct Foo { + int x; +} +Foo? foo = null; +Bar bar = new Bar; +bar.a = 1; +bar.a = 2; +return bar.a; + +*/ + rankdir=BT; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl$2$3$4
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + new10 [ label="new Bar" ]; + Con_11 [ label="#0" ]; + Store13 [ label=".b =" ]; + Con_16 [ label="#2" ]; + Store17 [ label=".a =" ]; + Load18 [ label=".a" ]; + Return19 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return19[taillabel=0 color=red]; + new10 -> Start2:p0[taillabel=0 color=green]; + Store13 -> Start2:p3[taillabel=1 color=blue]; + Store13 -> new10[taillabel=2]; + Store13 -> Con_11[taillabel=3]; + Store17 -> Start2:p2[taillabel=1 color=blue]; + Store17 -> new10[taillabel=2]; + Store17 -> Con_16[taillabel=3]; + Load18 -> Store17[taillabel=1 color=blue]; + Load18 -> new10[taillabel=2]; + Return19 -> Start2:p0[taillabel=0 color=red]; + Return19 -> Load18[taillabel=1]; + Return19 -> Store17[taillabel=2 color=blue]; + Return19 -> Store13[taillabel=3 color=blue]; + Return19 -> Start2:p4[taillabel=4 color=blue]; +} \ No newline at end of file diff --git a/chapter10/docs/example2b.svg b/chapter10/docs/example2b.svg new file mode 100644 index 00000000..1ecf4de7 --- /dev/null +++ b/chapter10/docs/example2b.svg @@ -0,0 +1,189 @@ + + + + + + +chapter10 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +$2 + +$3 + +$4 + + + +Stop3 + +Stop + + + +Return19 + +Return + + + +Stop3->Return19 + + +0 + + + +new10 + +new Bar + + + +new10->Start2:p0 + + +0 + + + +Con_11 + +#0 + + + +Store13 + +.b = + + + +Store13->Start2:p3 + + +1 + + + +Store13->new10 + + +2 + + + +Store13->Con_11 + + +3 + + + +Con_16 + +#2 + + + +Store17 + +.a = + + + +Store17->Start2:p2 + + +1 + + + +Store17->new10 + + +2 + + + +Store17->Con_16 + + +3 + + + +Load18 + +.a + + + +Load18->new10 + + +2 + + + +Load18->Store17 + + +1 + + + +Return19->Start2:p0 + + + +0 + + + +Return19->Start2:p4 + + +4 + + + +Return19->Store13 + + + +3 + + + +Return19->Store17 + + +2 + + + +Return19->Load18 + + +1 + + + diff --git a/chapter10/docs/example2c.gv b/chapter10/docs/example2c.gv new file mode 100644 index 00000000..7bd21542 --- /dev/null +++ b/chapter10/docs/example2c.gv @@ -0,0 +1,53 @@ +digraph chapter10 { +/* +struct Bar { + int a; + int b; +} +struct Foo { + int x; +} +Foo? foo = null; +Bar bar = new Bar; +bar.a = 1; +bar.a = 2; +return bar.a; + +*/ + rankdir=BT; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Con_16 [ label="#2" ]; + Store17 [ label=".a =" ]; + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl$2$3$4
+
> + ]; + Return19 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + new10 [ label="new Bar" ]; + Con_11 [ label="#0" ]; + Store13 [ label=".b =" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Store17 -> Start2:p2[taillabel=1 color=blue]; + Store17 -> new10[taillabel=2]; + Store17 -> Con_16[taillabel=3]; + Return19 -> Start2:p0[taillabel=0 color=red]; + Return19 -> Con_16[taillabel=1]; + Return19 -> Store17[taillabel=2 color=blue]; + Return19 -> Store13[taillabel=3 color=blue]; + Return19 -> Start2:p4[taillabel=4 color=blue]; + Stop3 -> Return19[taillabel=0 color=red]; + new10 -> Start2:p0[taillabel=0 color=green]; + Store13 -> Start2:p3[taillabel=1 color=blue]; + Store13 -> new10[taillabel=2]; + Store13 -> Con_11[taillabel=3]; +} \ No newline at end of file diff --git a/chapter10/docs/example2c.svg b/chapter10/docs/example2c.svg new file mode 100644 index 00000000..d70660a2 --- /dev/null +++ b/chapter10/docs/example2c.svg @@ -0,0 +1,168 @@ + + + + + + +chapter10 + + +cluster_Nodes + + + + +Con_16 + +#2 + + + +Store17 + +.a = + + + +Store17->Con_16 + + +3 + + + +Start2 + + +Start + + + +$ctrl + +$2 + +$3 + +$4 + + + +Store17->Start2:p2 + + +1 + + + +new10 + +new Bar + + + +Store17->new10 + + +2 + + + +Return19 + +Return + + + +Return19->Con_16 + + +1 + + + +Return19->Store17 + + +2 + + + +Return19->Start2:p0 + + + +0 + + + +Return19->Start2:p4 + + +4 + + + +Store13 + +.b = + + + +Return19->Store13 + + +3 + + + +Stop3 + +Stop + + + +Stop3->Return19 + + +0 + + + +new10->Start2:p0 + + +0 + + + +Con_11 + +#0 + + + +Store13->Start2:p3 + + +1 + + + +Store13->new10 + + +2 + + + +Store13->Con_11 + + +3 + + + -- cgit v1.2.3