From a728e57ad819dad9281d690f22cebb8e2b3ca003 Mon Sep 17 00:00:00 2001 From: Tamas Hadhazy Date: Sat, 5 Oct 2024 14:43:30 +0100 Subject: ch4 extend DCE --- chapter04/README.md | 94 ++++++++++++++++++++++++++++++++++-- chapter04/docs/04-dce2.svg | 59 +++++++++++++++++++++++ chapter04/docs/04-dce3.svg | 116 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 265 insertions(+), 4 deletions(-) create mode 100644 chapter04/docs/04-dce2.svg create mode 100644 chapter04/docs/04-dce3.svg 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:* + +![Graph3](docs/04-dce2.svg) +## 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: +![Graph3](docs/04-dce3.svg) +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 @@ + + + + + + +chapter04 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Con_6 + +1 + + + +Con_6->Start2 + + +0 + + + +Return7 + +Return + + + +Return7->Start2:p0 + + +0 + + + +Return7->Con_6 + + +1 + + + \ 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 @@ + + + + + + +chapter04 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Con_5 + +2 + + + +Con_6 + +1 + + + +Add7 + ++ + + + +Add7->Con_5 + + +1 + + + +Add7->Con_6 + + +2 + + + +Con_8 + +3 + + + +Con_9 + +3 + + + +Add10 + ++ + + + +Add10->Con_8 + + +1 + + + +Add10->Con_9 + + +2 + + + +Con_11 + +6 + + + +Return12 + +Return + + + +Return12->Start2:p0 + + +0 + + + +Return12->Con_11 + + +1 + + + \ No newline at end of file -- cgit v1.2.3