diff options
| -rw-r--r-- | chapter04/README.md | 94 | ||||
| -rw-r--r-- | chapter04/docs/04-dce2.svg | 59 | ||||
| -rw-r--r-- | chapter04/docs/04-dce3.svg | 116 |
3 files changed, 265 insertions, 4 deletions
diff --git a/chapter04/README.md b/chapter04/README.md index 8f44cdf5..e96457c8 100644 --- a/chapter04/README.md +++ b/chapter04/README.md @@ -353,12 +353,14 @@ The peephole method does following: `peephole()` calls `deadCodeElim()` which is shown below. ## Dead Code Elimination(DCE) -Dead Code Elimination +Dead Code Elimination is the process or removing nodes that are dead(unused). + There are two kinds of dead code eliminations present in this chapter. - Delete unused nodes when popping the scope. - Delete old nodes after finding a better replacement(after idealize call). -Both of the methods mentioned above delete the nodes recursively. +Both of the methods mentioned above delete the nodes recursively. However, the first case happens +regardless of whether `peephole` is called or not. ### Delete unused nodes when popping the scope A node is unused if it has no outputs(users). @@ -392,9 +394,93 @@ Both of the methods mentioned above delete the nodes recursively. _outputs = {ArrayList@1544} size = 1 0 = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]" ``` - Notice how the only output of `a`is `the scope itself`. When `a` is introduced we add it to the `scope`'s inputs as - as the scope to the outputs of `a`. + Notice how the only output of `a`is the scope itself. When `a` is introduced, it is added to the + inputs of the scope, and the scope is added to the outputs of `a`(recall use-def chains). + +Since `a` is not being returned - it is unused and can be killed. + +`_scope.pop`: +```java +public void pop() { popN(_scopes.pop().size()); } +``` +`_scope.popN`(responsible for killing the unused nodes *recursively*): +```java +void popN(int n) { + for (int i = 0; i < n; i++) { + Node old_def = _inputs.removeLast(); // start from the back + if (old_def != null && // If it exists and + old_def.delUse(this)) { // If we removed the last use, the old def is now dead + old_def.kill(); // Kill the old def + } + } +} +``` +First, we start off by looping through the inputs of the scope(*remember*: scope is just a node like any other, the symbols of the scope are the inputs). +If the node returned by `removeLast` is not null, and if the only user of `old_def` is the current Node then we can delete it. + +`old_def.delUse(this)` - delete *this* from 'old_def's output. +```java +protected boolean delUse( Node use ) { + Utils.del(_outputs, Utils.find(_outputs, use)); + return _outputs.isEmpty(); + } +``` +Returns true if `_outputs` becomes empty after deleting `use`. +`old_def.kill()` starts the killing process recursively. + +`old_def.kill()` +```java +public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + popN(nIns()); // Set all inputs to null, recursively killing unused Nodes + _type=null; // Flag as dead + assert isDead(); // Really dead now + } +``` +`popN` is called again, our goal is to look for nodes that might also get deleted once `a` is freed. +The only input `a` has is the constant node with value 12. As every other node a `ConstantNode` takes in the control node first(`Start`), once we +drop the `Start` node from the inputs of `ConstantNode`: +``` +Node old_def = _inputs.removeLast(); +``` +we also get rid of `ConstantNode`(`this`) from the outputs of `Start`: +``` +old_def.delUse(this) +``` + +*A constant node pointing to "Start"(ignored by the graph visualizer) but still maintains a connection:* + + +## Delete old nodes after finding a better replacement +Consider the following code: +``` +return (2+1)+3; +``` +Without DCE after the `idealize` call we would end up with: + +After identifying a more optimal replacement value (6) for the expression (2 + 1) + 3, +we created a constant node to store this value. +However, we did not remove the original expression, +resulting in dangling nodes in our structure. + +To fix this, we introduce an extra `deadCodeElim` call that is responsible for deleting unused nodes. +```java +public final Node peephole( ) { + ... + if (!(this instanceof ConstantNode) && type.isConstant()) + return new deadCodeElim(ConstantNode(type).peephole()); + + ... + + Node n = idealize(); + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); + + ... +} +``` ```java // m is the new Node, self is the old. // Return 'm', which may have zero uses but is alive nonetheless. diff --git a/chapter04/docs/04-dce2.svg b/chapter04/docs/04-dce2.svg new file mode 100644 index 00000000..e3719bcc --- /dev/null +++ b/chapter04/docs/04-dce2.svg @@ -0,0 +1,59 @@ +<?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.40.1 (20161225.0304) + --> +<!-- Title: chapter04 Pages: 1 --> +<svg width="114pt" height="250pt" viewBox="0.00 0.00 114.00 250.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 246)"> +<title>chapter04</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-246 110,-246 110,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="8,-8 8,-234 98,-234 98,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="#ffff00" stroke="transparent" points="33,-196 33,-222 74,-222 74,-196 33,-196"/> +<polygon fill="none" stroke="#000000" points="33,-196 33,-222 74,-222 74,-196 33,-196"/> +<text text-anchor="start" x="40.2805" y="-204.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +<polygon fill="none" stroke="#000000" points="33,-164 33,-196 74,-196 74,-164 33,-164"/> +<polygon fill="#ffff00" stroke="transparent" points="38,-169 38,-191 69,-191 69,-169 38,-169"/> +<polygon fill="none" stroke="#000000" points="38,-169 38,-191 69,-191 69,-169 38,-169"/> +<text text-anchor="start" x="40.6718" y="-175.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +</g> +<!-- Con_6 --> +<g id="node2" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="#000000" cx="43" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-101.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +<!-- Con_6->Start2 --> +<g id="edge1" class="edge"> +<title>Con_6->Start2</title> +<path fill="none" stroke="#ff0000" d="M45.072,-124.0265C45.9366,-131.5481 46.9815,-140.6387 48.0249,-149.7167"/> +<polygon fill="#ff0000" stroke="#ff0000" points="44.5736,-150.3415 49.1927,-159.8764 51.5278,-149.5421 44.5736,-150.3415"/> +<text text-anchor="middle" x="42.8484" y="-126.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return7 --> +<g id="node3" class="node"> +<title>Return7</title> +<polygon fill="#ffff00" stroke="#000000" points="80.1025,-52 25.8975,-52 25.8975,-16 80.1025,-16 80.1025,-52"/> +<text text-anchor="middle" x="53" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text> +</g> +<!-- Return7->Start2 --> +<g id="edge2" class="edge"> +<title>Return7->Start2:p0</title> +<path fill="none" stroke="#ff0000" d="M64.3196,-52.2322C69.9396,-62.3585 76.1294,-75.4211 79,-88 82.5597,-103.599 83.0135,-108.5115 79,-124 74.2474,-142.3411 60.2215,-145.475 55.5405,-159.004"/> +<polygon fill="#ff0000" stroke="#ff0000" points="52.0641,-158.5835 54,-169 58.9824,-159.6498 52.0641,-158.5835"/> +<text text-anchor="middle" x="62.096" y="-54.6322" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return7->Con_6 --> +<g id="edge3" class="edge"> +<title>Return7->Con_6</title> +<path fill="none" stroke="#000000" d="M50.4766,-52.1686C49.4071,-59.869 48.1353,-69.0257 46.9468,-77.5834"/> +<polygon fill="#000000" stroke="#000000" points="43.4664,-77.2003 45.5574,-87.5867 50.3999,-78.1633 43.4664,-77.2003"/> +<text text-anchor="middle" x="48.253" y="-54.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +</g> +</svg>
\ No newline at end of file diff --git a/chapter04/docs/04-dce3.svg b/chapter04/docs/04-dce3.svg new file mode 100644 index 00000000..86fa6f0d --- /dev/null +++ b/chapter04/docs/04-dce3.svg @@ -0,0 +1,116 @@ +<?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.40.1 (20161225.0304) + --> +<!-- Title: chapter04 Pages: 1 --> +<svg width="458pt" height="178pt" viewBox="0.00 0.00 458.00 178.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 174)"> +<title>chapter04</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-174 454,-174 454,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="8,-8 8,-162 442,-162 442,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="#ffff00" stroke="transparent" points="25,-124 25,-150 66,-150 66,-124 25,-124"/> +<polygon fill="none" stroke="#000000" points="25,-124 25,-150 66,-150 66,-124 25,-124"/> +<text text-anchor="start" x="32.2805" y="-132.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +<polygon fill="none" stroke="#000000" points="25,-92 25,-124 66,-124 66,-92 25,-92"/> +<polygon fill="#ffff00" stroke="transparent" points="30,-97 30,-119 61,-119 61,-97 30,-97"/> +<polygon fill="none" stroke="#000000" points="30,-97 30,-119 61,-119 61,-97 30,-97"/> +<text text-anchor="start" x="32.6718" y="-103.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +</g> +<!-- Con_5 --> +<g id="node2" class="node"> +<title>Con_5</title> +<ellipse fill="none" stroke="#000000" cx="335" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="335" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">2</text> +</g> +<!-- Con_6 --> +<g id="node3" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="#000000" cx="407" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="407" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +<!-- Add7 --> +<g id="node4" class="node"> +<title>Add7</title> +<ellipse fill="none" stroke="#000000" cx="371" cy="-34" rx="27" ry="18"/> +<text text-anchor="middle" x="371" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">+</text> +</g> +<!-- Add7->Con_5 --> +<g id="edge1" class="edge"> +<title>Add7->Con_5</title> +<path fill="none" stroke="#000000" d="M363.7149,-51.6057C358.6889,-63.7518 351.9107,-80.1326 346.2018,-93.9289"/> +<polygon fill="#000000" stroke="#000000" points="342.8638,-92.842 342.2743,-103.4204 349.3319,-95.5185 342.8638,-92.842"/> +<text text-anchor="middle" x="361.4913" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Add7->Con_6 --> +<g id="edge2" class="edge"> +<title>Add7->Con_6</title> +<path fill="none" stroke="#000000" d="M378.2851,-51.6057C383.3111,-63.7518 390.0893,-80.1326 395.7982,-93.9289"/> +<polygon fill="#000000" stroke="#000000" points="392.6681,-95.5185 399.7257,-103.4204 399.1362,-92.842 392.6681,-95.5185"/> +<text text-anchor="middle" x="376.0615" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- Con_8 --> +<g id="node5" class="node"> +<title>Con_8</title> +<ellipse fill="none" stroke="#000000" cx="191" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="191" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">3</text> +</g> +<!-- Con_9 --> +<g id="node6" class="node"> +<title>Con_9</title> +<ellipse fill="none" stroke="#000000" cx="263" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="263" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">3</text> +</g> +<!-- Add10 --> +<g id="node7" class="node"> +<title>Add10</title> +<ellipse fill="none" stroke="#000000" cx="227" cy="-34" rx="27" ry="18"/> +<text text-anchor="middle" x="227" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">+</text> +</g> +<!-- Add10->Con_8 --> +<g id="edge3" class="edge"> +<title>Add10->Con_8</title> +<path fill="none" stroke="#000000" d="M219.7149,-51.6057C214.6889,-63.7518 207.9107,-80.1326 202.2018,-93.9289"/> +<polygon fill="#000000" stroke="#000000" points="198.8638,-92.842 198.2743,-103.4204 205.3319,-95.5185 198.8638,-92.842"/> +<text text-anchor="middle" x="217.4913" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Add10->Con_9 --> +<g id="edge4" class="edge"> +<title>Add10->Con_9</title> +<path fill="none" stroke="#000000" d="M234.2851,-51.6057C239.3111,-63.7518 246.0893,-80.1326 251.7982,-93.9289"/> +<polygon fill="#000000" stroke="#000000" points="248.6681,-95.5185 255.7257,-103.4204 255.1362,-92.842 248.6681,-95.5185"/> +<text text-anchor="middle" x="232.0615" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- Con_11 --> +<g id="node8" class="node"> +<title>Con_11</title> +<ellipse fill="none" stroke="#000000" cx="119" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="119" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">6</text> +</g> +<!-- Return12 --> +<g id="node9" class="node"> +<title>Return12</title> +<polygon fill="#ffff00" stroke="#000000" points="109.1025,-52 54.8975,-52 54.8975,-16 109.1025,-16 109.1025,-52"/> +<text text-anchor="middle" x="82" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text> +</g> +<!-- Return12->Start2 --> +<g id="edge5" class="edge"> +<title>Return12->Start2:p0</title> +<path fill="none" stroke="#ff0000" d="M65.0542,-52.052C57.6135,-61.4899 49.9318,-73.7894 47.1181,-86.8747"/> +<polygon fill="#ff0000" stroke="#ff0000" points="43.6189,-86.6762 46,-97 50.5766,-87.4446 43.6189,-86.6762"/> +<text text-anchor="middle" x="62.8306" y="-54.452" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return12->Con_11 --> +<g id="edge6" class="edge"> +<title>Return12->Con_11</title> +<path fill="none" stroke="#000000" d="M89.6664,-52.0265C94.8444,-64.2017 101.7707,-80.4878 107.5926,-94.1772"/> +<polygon fill="#000000" stroke="#000000" points="104.4613,-95.7577 111.5959,-103.5903 110.903,-93.0181 104.4613,-95.7577"/> +<text text-anchor="middle" x="87.4428" y="-54.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +</g> +</svg>
\ No newline at end of file |
