diff options
Diffstat (limited to 'chapter04/README.md')
| -rw-r--r-- | chapter04/README.md | 94 |
1 files changed, 90 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. |