Chapter6 Part 2 - Add further peephole based on dominator calc (#42)

* #37 Add a Utils class to hold some useful functions. (#39)

Move the name '$ctrl' to the ScopeNode

* Fix maven pom

Missing an explicit compiler target, so IntelliJ/Maven defaulted to version 5 ???
Remove explict ver 17 from Makefile.

* Add immediate dominator peephole

* A little more robust & simpler idom search

* #40 Revise chapter 6 writeup to include a description of dominators

* #40 Revise chapter 6 writeup to include a description of dominators

---------

Co-authored-by: Cliff Click <cliffc@acm.org>

3 files changed, 207 insertions, 0 deletions

diff --git a/chapter06/docs/06-graph3-nonconst-peephole.gv b/chapter06/docs/06-graph3-nonconst-peephole.gv
new file mode 100644
index 00000000..f8e3e5fa
--- /dev/null
+++ b/chapter06/docs/06-graph3-nonconst-peephole.gv
@@ -0,0 +1,56 @@
+digraph chapter06 {
+/*
+int a = 0;
+int b = 1;
+if( arg ) {
+    a = 2;
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b;
+
+*/
+	rankdir=BT;
+	ordering="in";
+	concentrate="true";
+	subgraph cluster_Nodes {
+		Start2 [ shape=plaintext label=<
+			<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4">
+			<TR><TD BGCOLOR="yellow">Start</TD></TR>
+			<TR><TD>
+				<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+				<TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR>
+				</TABLE>
+			</TD></TR>
+			</TABLE>>
+		];
+		Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ];
+		Region22 [ shape=box style=filled fillcolor=yellow label="Region" ];
+		If8 [ shape=plaintext label=<
+			<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4">
+			<TR><TD BGCOLOR="yellow">If</TD></TR>
+			<TR><TD>
+				<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+				<TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR>
+				</TABLE>
+			</TD></TR>
+			</TABLE>>
+		];
+		Con_27 [ label="#4" ];
+		Con_29 [ label="#1" ];
+		Phi_ab30 [ style=filled fillcolor=lightyellow label="&phi;_ab" ];
+		Return31 [ shape=box style=filled fillcolor=yellow label="Return" ];
+		{ rank=same; Region22;Phi_ab30;}
+	}
+	edge [ fontname=Helvetica, fontsize=8 ];
+	Stop3 -> Return31[taillabel=0 color=red];
+	Region22 -> If8:p0[taillabel=1 color=red];
+	Region22 -> If8:p1[taillabel=2 color=red];
+	If8 -> Start2:p0[taillabel=0 color=red];
+	If8 -> Start2:p1[taillabel=1];
+	Phi_ab30 -> Region22 [style=dotted taillabel=0];
+	Phi_ab30 -> Con_27[taillabel=1];
+	Phi_ab30 -> Con_29[taillabel=2];
+	Return31 -> Region22[taillabel=0 color=red];
+	Return31 -> Phi_ab30[taillabel=1];
+}
diff --git a/chapter06/docs/06-graph3-nonconst-peephole.svg b/chapter06/docs/06-graph3-nonconst-peephole.svg
new file mode 100644
index 00000000..c312ffc5
--- /dev/null
+++ b/chapter06/docs/06-graph3-nonconst-peephole.svg
@@ -0,0 +1,150 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 2.43.0 (0)
+ -->
+<!-- Title: chapter06 Pages: 1 -->
+<svg width="294pt" height="420pt"
+ viewBox="0.00 0.00 294.00 420.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 416)">
+<title>chapter06</title>
+<polygon fill="white" stroke="transparent" points="-4,4 -4,-416 290,-416 290,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="black" points="8,-8 8,-404 278,-404 278,-8 8,-8"/>
+</g>
+<!-- Start2 -->
+<g id="node1" class="node">
+<title>Start2</title>
+<polygon fill="yellow" stroke="transparent" points="168,-367 168,-392 249,-392 249,-367 168,-367"/>
+<polygon fill="none" stroke="black" points="168,-367 168,-392 249,-392 249,-367 168,-367"/>
+<text text-anchor="start" x="190" y="-375.8" font-family="Times,serif" font-size="14.00">Start</text>
+<polygon fill="none" stroke="black" points="168,-336 168,-367 249,-367 249,-336 168,-336"/>
+<polygon fill="yellow" stroke="transparent" points="173,-341 173,-362 213,-362 213,-341 173,-341"/>
+<polygon fill="none" stroke="black" points="173,-341 173,-362 213,-362 213,-341 173,-341"/>
+<text text-anchor="start" x="176" y="-347.8" font-family="Times,serif" font-size="14.00">$ctrl</text>
+<polygon fill="none" stroke="black" points="213,-341 213,-362 244,-362 244,-341 213,-341"/>
+<text text-anchor="start" x="216" y="-347.8" font-family="Times,serif" font-size="14.00">arg</text>
+</g>
+<!-- Stop3 -->
+<g id="node2" class="node">
+<title>Stop3</title>
+<polygon fill="yellow" stroke="black" points="180,-52 126,-52 126,-16 180,-16 180,-52"/>
+<text text-anchor="middle" x="153" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text>
+</g>
+<!-- Return31 -->
+<g id="node8" class="node">
+<title>Return31</title>
+<polygon fill="yellow" stroke="black" points="186,-124 120,-124 120,-88 186,-88 186,-124"/>
+<text text-anchor="middle" x="153" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text>
+</g>
+<!-- Stop3&#45;&gt;Return31 -->
+<g id="edge1" class="edge">
+<title>Stop3&#45;&gt;Return31</title>
+<path fill="none" stroke="red" d="M153,-52.3C153,-60.02 153,-69.29 153,-77.89"/>
+<polygon fill="red" stroke="red" points="149.5,-77.9 153,-87.9 156.5,-77.9 149.5,-77.9"/>
+<text text-anchor="middle" x="150" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Region22 -->
+<g id="node3" class="node">
+<title>Region22</title>
+<polygon fill="yellow" stroke="black" points="228,-196 162,-196 162,-160 228,-160 228,-196"/>
+<text text-anchor="middle" x="195" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text>
+</g>
+<!-- If8 -->
+<g id="node4" class="node">
+<title>If8</title>
+<polygon fill="yellow" stroke="transparent" points="168,-267 168,-292 262,-292 262,-267 168,-267"/>
+<polygon fill="none" stroke="black" points="168,-267 168,-292 262,-292 262,-267 168,-267"/>
+<text text-anchor="start" x="209.5" y="-275.8" font-family="Times,serif" font-size="14.00">If</text>
+<polygon fill="none" stroke="black" points="168,-236 168,-267 262,-267 262,-236 168,-236"/>
+<polygon fill="yellow" stroke="transparent" points="173,-241 173,-262 213,-262 213,-241 173,-241"/>
+<polygon fill="none" stroke="black" points="173,-241 173,-262 213,-262 213,-241 173,-241"/>
+<text text-anchor="start" x="176" y="-247.8" font-family="Times,serif" font-size="14.00">True</text>
+<polygon fill="yellow" stroke="transparent" points="213,-241 213,-262 257,-262 257,-241 213,-241"/>
+<polygon fill="none" stroke="black" points="213,-241 213,-262 257,-262 257,-241 213,-241"/>
+<text text-anchor="start" x="216" y="-247.8" font-family="Times,serif" font-size="14.00">False</text>
+</g>
+<!-- Region22&#45;&gt;If8 -->
+<g id="edge2" class="edge">
+<title>Region22&#45;&gt;If8:p0</title>
+<path fill="none" stroke="red" d="M194.14,-196.09C193.72,-205.54 193.27,-217.77 193.08,-229.68"/>
+<polygon fill="red" stroke="red" points="189.58,-229.97 193,-240 196.58,-230.03 189.58,-229.97"/>
+<text text-anchor="middle" x="191.14" y="-198.69" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Region22&#45;&gt;If8 -->
+<g id="edge3" class="edge">
+<title>Region22&#45;&gt;If8:p1</title>
+<path fill="none" stroke="red" d="M213.83,-196.05C222.1,-205.05 230.63,-216.92 233.76,-229.89"/>
+<polygon fill="red" stroke="red" points="230.31,-230.5 235,-240 237.25,-229.65 230.31,-230.5"/>
+<text text-anchor="middle" x="210.83" y="-198.65" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- If8&#45;&gt;Start2 -->
+<g id="edge4" class="edge">
+<title>If8&#45;&gt;Start2:p0</title>
+<path fill="none" stroke="red" d="M201.57,-296.16C198.03,-306.41 194.84,-318.18 193.57,-329.83"/>
+<polygon fill="red" stroke="red" points="190.07,-329.82 193,-340 197.06,-330.21 190.07,-329.82"/>
+<text text-anchor="middle" x="198.57" y="-298.76" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- If8&#45;&gt;Start2 -->
+<g id="edge5" class="edge">
+<title>If8&#45;&gt;Start2:p1</title>
+<path fill="none" stroke="black" d="M223.47,-296.14C225.75,-306.5 227.81,-318.36 228.63,-329.94"/>
+<polygon fill="black" stroke="black" points="225.13,-330.14 229,-340 232.13,-329.88 225.13,-330.14"/>
+<text text-anchor="middle" x="220.47" y="-298.74" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Con_27 -->
+<g id="node5" class="node">
+<title>Con_27</title>
+<ellipse fill="none" stroke="black" cx="43" cy="-264" rx="27" ry="18"/>
+<text text-anchor="middle" x="43" y="-260.3" font-family="Times,serif" font-size="14.00">#4</text>
+</g>
+<!-- Con_29 -->
+<g id="node6" class="node">
+<title>Con_29</title>
+<ellipse fill="none" stroke="black" cx="115" cy="-264" rx="27" ry="18"/>
+<text text-anchor="middle" x="115" y="-260.3" font-family="Times,serif" font-size="14.00">#1</text>
+</g>
+<!-- Phi_ab30 -->
+<g id="node7" class="node">
+<title>Phi_ab30</title>
+<ellipse fill="lightyellow" stroke="black" cx="112" cy="-178" rx="32.49" ry="18"/>
+<text text-anchor="middle" x="112" y="-174.3" font-family="Times,serif" font-size="14.00">φ_ab</text>
+</g>
+<!-- Phi_ab30&#45;&gt;Region22 -->
+<g id="edge6" class="edge">
+<title>Phi_ab30&#45;&gt;Region22</title>
+<path fill="none" stroke="black" stroke-dasharray="1,5" d="M144.75,-178C147.03,-178 149.32,-178 151.6,-178"/>
+<polygon fill="black" stroke="black" points="151.63,-181.5 161.63,-178 151.63,-174.5 151.63,-181.5"/>
+<text text-anchor="middle" x="147.75" y="-171.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Phi_ab30&#45;&gt;Con_27 -->
+<g id="edge7" class="edge">
+<title>Phi_ab30&#45;&gt;Con_27</title>
+<path fill="none" stroke="black" d="M99.02,-194.8C88.58,-207.51 73.76,-225.56 61.98,-239.89"/>
+<polygon fill="black" stroke="black" points="59.1,-237.89 55.46,-247.84 64.51,-242.33 59.1,-237.89"/>
+<text text-anchor="middle" x="96.02" y="-197.4" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Phi_ab30&#45;&gt;Con_29 -->
+<g id="edge8" class="edge">
+<title>Phi_ab30&#45;&gt;Con_29</title>
+<path fill="none" stroke="black" d="M112.61,-196C113.01,-207.31 113.55,-222.42 114.02,-235.43"/>
+<polygon fill="black" stroke="black" points="110.53,-235.87 114.38,-245.74 117.52,-235.62 110.53,-235.87"/>
+<text text-anchor="middle" x="109.61" y="-198.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Return31&#45;&gt;Region22 -->
+<g id="edge9" class="edge">
+<title>Return31&#45;&gt;Region22</title>
+<path fill="none" stroke="red" d="M163.38,-124.3C168.26,-132.44 174.19,-142.31 179.58,-151.3"/>
+<polygon fill="red" stroke="red" points="176.59,-153.12 184.74,-159.9 182.59,-149.52 176.59,-153.12"/>
+<text text-anchor="middle" x="160.38" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Return31&#45;&gt;Phi_ab30 -->
+<g id="edge10" class="edge">
+<title>Return31&#45;&gt;Phi_ab30</title>
+<path fill="none" stroke="black" d="M142.87,-124.3C138.03,-132.56 132.15,-142.61 126.82,-151.7"/>
+<polygon fill="black" stroke="black" points="123.77,-149.98 121.74,-160.38 129.81,-153.52 123.77,-149.98"/>
+<text text-anchor="middle" x="139.87" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+</g>
+</svg>
diff --git a/chapter06/docs/build-graphs.sh b/chapter06/docs/build-graphs.sh
index d65826f4..5238dbfc 100644
--- a/chapter06/docs/build-graphs.sh
+++ b/chapter06/docs/build-graphs.sh
@@ -3,6 +3,7 @@ dot -Tsvg  06-graph1-post.gv > 06-graph1-post.svg
 dot -Tsvg  06-graph2-pre.gv > 06-graph2-pre.svg
 dot -Tsvg  06-graph2-post.gv > 06-graph2-post.svg
 dot -Tsvg  06-graph3-nonconst.gv > 06-graph3-nonconst.svg
+dot -Tsvg  06-graph3-nonconst-peephole.gv > 06-graph3-nonconst-peephole.svg
 dot -Tsvg  06-graph3-true.gv > 06-graph3-true.svg
 dot -Tsvg  06-graph3-false.gv > 06-graph3-false.svg
 dot -Tsvg  06-graph4-nonconst.gv > 06-graph4-nonconst.svg