diff options
Diffstat (limited to 'chapter06')
15 files changed, 364 insertions, 55 deletions
diff --git a/chapter06/Makefile b/chapter06/Makefile index f2839f15..56f69e12 100644 --- a/chapter06/Makefile +++ b/chapter06/Makefile @@ -25,7 +25,7 @@ endif # Fun Args to javac. Mostly limit to java8 source definitions, and fairly # aggressive lint warnings. -JAVAC_ARGS = -g -source 17 -target 17 +JAVAC_ARGS = -g # Source code SIMPLE := com/seaofnodes/simple diff --git a/chapter06/README.md b/chapter06/README.md index dd08aff5..d3fe6ed9 100644 --- a/chapter06/README.md +++ b/chapter06/README.md @@ -51,7 +51,7 @@ As before we denote "top" by T and "bottom" by ⊥. * Finally, at the end, when the `Region` node is peepholed, we see that it has only one live input and no Phi uses and can be replaced with its one live input. -## Discussion of `Region` and `Phi` +## `Region` and `Phi` One of the invariants we maintain is that the for each control input to a `Region` every `Phi` has a 1-to-1 relationship with a data input. Thus, if a @@ -63,11 +63,12 @@ When processing `If` we do not remove control inputs to a `Region`, instead the dead control input is simply set to `Constant(~ctrl)`. The peephole logic in a `Phi` notices this and replaces itself with the live input. -## Examples +## Discussion -We show a number of examples of peephole in action. +With the changes above, our peephol optimization is able to fold dead code when +an `if` statement has a condition that evaluates to `true` or `false` at compile time. -### Example 1 +Let's look at a simple example below: ```java if( true ) return 2; @@ -82,7 +83,7 @@ After peephole:  -### Example 2 +Another example: ```java int a=1; @@ -101,7 +102,10 @@ After peephole:  -### Example 3 +## Expanding Peephole Beyond Constant Expressions + +While our peephole of the `CFG` collapses dead code when the expression is +a compile time constant. it does not do as well as it could with following example: ```java int a = 0; @@ -114,41 +118,66 @@ if( arg ) { return a+b; ``` -In this example, `arg` is defined externally. If `arg` is given a non-constant value, then the graph looks like this: - - - -If we set `arg` to a non-zero constant such as `1` we get: - - +In this example, `arg` is defined externally, and we have to assume it is not a constant. +However, the code repeats the `if( arg )` condition in the inner `if` statement. +We know that if the outer `if( arg )` is true, then the *inner `if` must also evaluate to true*. -If we set `arg` to `0` which means false, then: +Our peephole at present cannot see this: - + -### Example 4 +What we would like is for our peephole to see that the inner `if` is fully determined by the +outer `if` and thus, the code can be simplified as follows: ```java int a = 0; int b = 1; -int c = 0; -if( arg ) { - a = 1; - if( arg==2 ) { c=2; } else { c=3; } - if( arg ) { b = 2; } - else b = 3; +if ( arg ) { + a = 2; + b = 2; } -return a+b+c; +return a+b; ``` -In this example, `arg` is defined externally. If `arg` is given a non-constant value, then the graph looks like this: +That is, the final outcome is either `4` if `arg` happens to be true, or `1` if `arg` happens to be false. + +## Dominators + +The key to implementing this peephole is the observation that the inner `if` is completely determined by the +outer `if`. In compiler parlance, we say that the outer `if` dominates the inner `if`. + +There is a generic way to determine this type of domination; it involves constructing a dominator +tree. For details of how to do this, please refer to the paper `A Simple, Fast Dominance Algorithm`.[^1] + +However, constructing a dominator tree is an expensive operation; one that we would not like to +do in the middle of parsing. Fortunately, since we do not have loops yet, we do not +have back edges in our control flow graph. Our control flow graph is essentially hierarchical, tree like. +Thus, a simple form of dominator identification is possible. + +The main idea is that we can assign a `depth` to each control node, this represents the node's depth +in the hierarchy. We can compute this depth incrementally as we need to. The nodes that are deeper in the hierarchy +have a greater depth than the ones above. + +Secondly we know that for our control nodes, except for `Region`s, there is only one incoming control edge, +which means that most control nodes have a single immediate dominating control node. `Region` nodes are different +as they can have one or more control edges; but, we know that for `if` statements, a `Region` node has exactly two +control inputs, one from each branch of the `if`. To find the immediate dominator of a `Region` node in the +limited scenario of an `if`, we can follow the immediate dominator of each branch until we find the common ancestor +node that dominates both the branches. + +If this ancestor node is also an `if` and its predicate is the same as the current `if`, then we know that +the outcome of the present `if` is fully determined. + +The code that does this check is in the [`compute` method of the `if`](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java#L38-L45). - +The `idom` method in `Node` provides a default implementation of the depth based immediate dominator calculation. +`Region`'s [override this](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java#L57-L74) to implement the more complex search described above. -If we set `arg` to `1` we get: +It turns out that to simplify the example above, we need a [further peephole in our `Add` node](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java#L64-L67). - +With all these changes, the outcome of the peephole is just what we would like to see! -If we set `arg` to `2`, then: + - +[^1]: Cooper, K. D. Cooper, Harvey, T. J., and Kennedy, K. (2001). + A Simple, Fast Dominance Algorithm.
\ No newline at end of file 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="φ_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->Return31 --> +<g id="edge1" class="edge"> +<title>Stop3->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->If8 --> +<g id="edge2" class="edge"> +<title>Region22->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->If8 --> +<g id="edge3" class="edge"> +<title>Region22->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->Start2 --> +<g id="edge4" class="edge"> +<title>If8->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->Start2 --> +<g id="edge5" class="edge"> +<title>If8->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->Region22 --> +<g id="edge6" class="edge"> +<title>Phi_ab30->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->Con_27 --> +<g id="edge7" class="edge"> +<title>Phi_ab30->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->Con_29 --> +<g id="edge8" class="edge"> +<title>Phi_ab30->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->Region22 --> +<g id="edge9" class="edge"> +<title>Return31->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->Phi_ab30 --> +<g id="edge10" class="edge"> +<title>Return31->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 diff --git a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java index b08c3c56..1bfe5b0d 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java @@ -14,11 +14,6 @@ import java.util.*; */ public class Parser { - /** - * The control is a name that binds to the currently active control - * node in the graph - */ - public static final String CTRL = "$ctrl"; /** * A Global Static, unique to each compilation. This is a public, so we @@ -80,6 +75,9 @@ public class Parser { this(source, TypeInteger.BOT); } + @Override + public String toString() { return _lexer.toString(); } + String src() { return new String( _lexer._input ); } private Node ctrl() { return _scope.ctrl(); } @@ -91,7 +89,7 @@ public class Parser { _allScopes.push(_scope); _scope.push(); try { - _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole()); + _scope.ctrl(new ProjNode(START, 0, ScopeNode.CTRL).peephole()); _scope.define("arg", new ProjNode(START, 1, "arg").peephole()); parseBlock(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); @@ -522,7 +520,4 @@ public class Parser { return new String(_input, start, 1); } } - - public static RuntimeException TODO() { return TODO("Not yet implemented"); } - public static RuntimeException TODO(String msg) { return new RuntimeException(msg); } } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/Utils.java b/chapter06/src/main/java/com/seaofnodes/simple/Utils.java new file mode 100644 index 00000000..c79d96f0 --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/Utils.java @@ -0,0 +1,6 @@ +package com.seaofnodes.simple; + +public class Utils { + public static RuntimeException TODO() { return TODO("Not yet implemented"); } + public static RuntimeException TODO(String msg) { return new RuntimeException(msg); } +}
\ No newline at end of file diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java index 61359d64..b29fb92c 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; public class AddNode extends Node { @@ -64,7 +63,8 @@ public class AddNode extends Node { // Now we might see (add add non) or (add non non) but never (add non add) nor (add add add) if( !(lhs instanceof AddNode) ) - return spline_cmp(lhs,rhs) ? swap12() : null; + // Rotate; look for (add (phi cons) con/(phi cons)) + return spline_cmp(lhs,rhs) ? swap12() : phiCon(this,true); // Now we only see (add add non) diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java index 9e88710c..1b0fdac7 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -31,9 +31,19 @@ public class IfNode extends MultiNode { // If constant is 0 then false branch is reachable // Else true branch is reachable if (pred()._type instanceof TypeInteger ti && ti.isConstant()) { - if (ti.value() == 0) return TypeTuple.IF_FALSE; - else return TypeTuple.IF_TRUE; + if (ti.value() == 0) return TypeTuple.IF_FALSE; + else return TypeTuple.IF_TRUE; } + + // Hunt up the immediate dominator tree. If we find an identical if + // test on either the true or false branch, then this test matches. + for( Node dom = idom(), prior=this; dom!=null; prior=dom, dom = dom.idom() ) + if( dom instanceof IfNode iff && iff.pred()==pred() ) + return prior instanceof ProjNode proj + // Repeated test, dominated on one side. Test result is the same. + ? (proj._idx==0 ? TypeTuple.IF_TRUE : TypeTuple.IF_FALSE) + : null; // Repeated test not dominated on one side + return TypeTuple.IF_BOTH; } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java index fe3fddf8..81c90f68 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -1,7 +1,5 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Type; - public abstract class MultiNode extends Node { public MultiNode(Node... inputs) { super(inputs); } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java index fd1b870c..36e4896d 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import java.util.*; @@ -46,6 +46,16 @@ public abstract class Node { */ public Type _type; + + /** + * Immediate dominator tree depth, used to approximate a real IDOM during + * parsing where we do not have the whole program, and also peepholes + * change the CFG incrementally. + * <p> + * See {@link https://en.wikipedia.org/wiki/Dominator_(graph_theory)} + */ + int _idepth; + /** * A private Global Static mutable counter, for unique node id generation. * To make the compiler multithreaded, this field will have to move into a TLS. @@ -367,10 +377,18 @@ public abstract class Node { return true; } + // Return the immediate dominator of this Node and compute dom tree depth. + Node idom() { + Node idom = in(0); + if( idom._idepth==0 ) idom.idom(); // Recursively set _idepth + if( _idepth==0 ) _idepth = idom._idepth+1; + return idom; + } + // Make a shallow copy (same class) of this Node, with given inputs and // empty outputs and a new Node ID. The original inputs are ignored. // Does not need to be implemented in isCFG() nodes. - Node copy(Node lhs, Node rhs) { throw Parser.TODO("Binary ops need to implement copy"); } + Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } /** * Used to allow repeating tests in the same JVM. This just resets the diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 1ddf520b..d3fd7745 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; public class RegionNode extends Node { @@ -39,7 +39,7 @@ public class RegionNode extends Node { for( Node phi : _outputs ) if( phi instanceof PhiNode ) // Currently does not happen, because no loops - throw Parser.TODO(); + throw Utils.TODO(); return in(1); } return this; @@ -53,4 +53,23 @@ public class RegionNode extends Node { return i; return 0; // All inputs alive } + + // Immediate dominator of Region is a little more complicated. + private Node _idom; // Immediate dominator cache + @Override Node idom() { + if( _idom != null ) return _idom; // Return cached copy + if( nIns()!=3 ) return null; // Fails for anything other than 2-inputs + // Walk the LHS & RHS idom trees in parallel until they match, or either fails + Node lhs = in(1).idom(); + Node rhs = in(2).idom(); + while( lhs != rhs ) { + if( lhs==null || rhs==null ) return null; + var comp = lhs._idepth - rhs._idepth; + if( comp >= 0 ) lhs = lhs.idom(); + if( comp <= 0 ) rhs = rhs.idom(); + } + if( lhs==null ) return null; + _idepth = lhs._idepth+1; + return (_idom=lhs); + } } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index eecab9f9..96564f3b 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import java.util.*; @@ -12,6 +11,12 @@ import java.util.*; public class ScopeNode extends Node { /** + * The control is a name that binds to the currently active control + * node in the graph + */ + public static final String CTRL = "$ctrl"; + + /** * Stack of lexical scopes, each scope is a symbol table * that binds variable names to Nodes. * The top of this stack represents current scope. @@ -76,10 +81,26 @@ public class ScopeNode extends Node { return null; } - public Node ctrl() { assert lookup(Parser.CTRL)==in(0); return in(0); } - + public Node ctrl() { assert lookup(CTRL)==in(0); return in(0); } + + /** + * The ctrl of a ScopeNode is always bound to the currently active + * control node in the graph, via a special name '$ctrl' that is not + * a valid identifier in the language grammar and hence cannot be + * referenced in Simple code. + * + * @param n The node to be bound to '$ctrl' + * + * @return Node that was bound + */ public Node ctrl(Node n) { - assert lookup(Parser.CTRL)==in(0); + if (nIns() == 0) { + // The first time a scope is created we do not have the name binding + // for '$ctrl' but after that we expect to find the name already bound + assert lookup(CTRL) == null; + define(CTRL, n); + } + else assert lookup(CTRL) == in(0); set_def(0,n); return n; } @@ -128,6 +149,7 @@ public class ScopeNode extends Node { */ public Node mergeScopes(ScopeNode that) { RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); + // Note that we skip i==0, which is bound to '$ctrl' for (int i = 1; i < nIns(); i++) if (in(i) != that.in(i)) // No need for redundant Phis set_def(i, new PhiNode(_rlabels.get(i), r, in(i), that.in(i)).peephole()); diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java index 85c6cd34..8cff25bd 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -34,4 +34,9 @@ public class StartNode extends MultiNode { @Override public Node idealize() { return null; } + + // No immediate dominator, and idepth==0 + @Override + Node idom() { return null; } + } diff --git a/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 801f8d3f..7767b203 100644 --- a/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -200,7 +200,7 @@ if( arg ) { return a+b; """); StopNode ret = parser.parse(true); - assertEquals("return (Phi(Region21,Phi(Region19,2,3),1)+Phi(Region21,2,0));", ret.toString()); + assertEquals("return Phi(Region22,4,1);", ret.toString()); } @@ -251,7 +251,7 @@ if( arg ) { return a+b+c; """); StopNode ret = parser.parse(true); - assertEquals("return ((Phi(Region32,Phi(Region22,2,3),0)+Phi(Region32,Phi(Region30,2,3),1))+Phi(Region32,1,0));", ret.toString()); + assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region33,3,1));", ret.toString()); } |
