From 578ac96b3ee6b93b3220b554120a36bf9206cf6b Mon Sep 17 00:00:00 2001 From: Hels15 Date: Fri, 4 Oct 2024 22:00:47 +0100 Subject: dce init --- chapter04/README.md | 43 +++++++++++++++++++ chapter04/docs/04-dce1.svg | 100 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 143 insertions(+) create mode 100644 chapter04/docs/04-dce1.svg (limited to 'chapter04') diff --git a/chapter04/README.md b/chapter04/README.md index 4cbad1e4..8f44cdf5 100644 --- a/chapter04/README.md +++ b/chapter04/README.md @@ -352,6 +352,49 @@ The peephole method does following: `peephole()` calls `deadCodeElim()` which is shown below. +## Dead Code Elimination(DCE) +Dead Code Elimination +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. + + ### Delete unused nodes when popping the scope + A node is unused if it has no outputs(users). + + Consider the following example: + ``` + int a = 12; // the only output it has is the scope itself + return 1; + ``` + We clearly see `a` is unused. + This gives us the following graph(without DCE): + + ![Graph2](docs/04-dce1.svg) + + To remove `a` we introduce the following technique when popping the scope. + + ```java + var ret = (ReturnNode) parseBlock(); + _scope.pop(); + ``` + As of now the end of the program is hard-wired to return, after finishing parsing we pop the scope. + The state of the scope before popping it: + ``` + _scope = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]" + 1 = {ProjNode@1528} "arg" + 2 = {ConstantNode@1529} "12" + _inputs = {ArrayList@1523} size = 3 + ``` + The output(s) of `a` + ``` + _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`. + ```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-dce1.svg b/chapter04/docs/04-dce1.svg new file mode 100644 index 00000000..c63a85f7 --- /dev/null +++ b/chapter04/docs/04-dce1.svg @@ -0,0 +1,100 @@ + + + + + + +chapter04 + + +cluster_Nodes + + + +cluster_Scope1_0 + + + +cluster_Scope1_1 + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Con_5 + +12 + + + +Con_6 + +1 + + + +Return7 + +Return + + + +Return7->Start2:p0 + + +0 + + + +Return7->Con_6 + + +1 + + + +Scope1_0 + + +0 + +$ctrl + +arg + + + +Scope1_0:Scope1_0_arg->Start2:p1 + + + + + +Scope1_1 + + +1 + +a + + + +Scope1_1:Scope1_1_a->Con_5 + + + + + \ No newline at end of file -- cgit v1.2.3