1 /*
2  * Copyright (C) 2014 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ART_COMPILER_OPTIMIZING_DEAD_CODE_ELIMINATION_H_
18 #define ART_COMPILER_OPTIMIZING_DEAD_CODE_ELIMINATION_H_
19 
20 #include "base/macros.h"
21 #include "nodes.h"
22 #include "optimization.h"
23 #include "optimizing_compiler_stats.h"
24 
25 namespace art HIDDEN {
26 
27 /**
28  * Optimization pass performing dead code elimination (removal of
29  * unused variables/instructions) on the SSA form.
30  */
31 class HDeadCodeElimination : public HOptimization {
32  public:
HDeadCodeElimination(HGraph * graph,OptimizingCompilerStats * stats,const char * name)33   HDeadCodeElimination(HGraph* graph, OptimizingCompilerStats* stats, const char* name)
34       : HOptimization(graph, name, stats) {}
35 
36   bool Run() override;
37 
38   static constexpr const char* kDeadCodeEliminationPassName = "dead_code_elimination";
39 
40  private:
41   void MaybeRecordDeadBlock(HBasicBlock* block);
42   void MaybeRecordSimplifyIf();
43   // Detects and remove ifs that are empty e.g. it turns
44   //     1
45   //    / \
46   //   2   3
47   //   \  /
48   //    4
49   // where 2 and 3 are single goto blocks and 4 doesn't contain a Phi into:
50   //    1
51   //    |
52   //    4
53   bool RemoveEmptyIfs();
54   // If `force_recomputation` is true, we will recompute the dominance information even when we
55   // didn't delete any blocks. `force_loop_recomputation` is similar but it also forces the loop
56   // information recomputation.
57   bool RemoveDeadBlocks(bool force_recomputation = false, bool force_loop_recomputation = false);
58   void RemoveDeadInstructions();
59   bool SimplifyAlwaysThrows();
60   // Simplify the pattern:
61   //
62   //        B1    B2    ...
63   //       goto  goto  goto
64   //         \    |    /
65   //          \   |   /
66   //             B3
67   //     i1 = phi(input, input)
68   //     (i2 = condition on i1)
69   //        if i1 (or i2)
70   //          /     \
71   //         /       \
72   //        B4       B5
73   //
74   // Into:
75   //
76   //       B1      B2    ...
77   //        |      |      |
78   //       B4      B5    B?
79   //
80   // Note that individual edges can be redirected (for example B2->B3
81   // can be redirected as B2->B5) without applying this optimization
82   // to other incoming edges.
83   //
84   // Note that we rely on the dead code elimination to get rid of B3.
85   bool SimplifyIfs();
86   void ConnectSuccessiveBlocks();
87   // Updates the graph flags related to instructions (e.g. HasSIMD()) since we may have eliminated
88   // the relevant instructions. There's no need to update `SetHasTryCatch` since we do that in
89   // `ComputeTryBlockInformation`. Similarly with `HasLoops` and `HasIrreducibleLoops`: They are
90   // cleared in `ClearLoopInformation` and then set as true as part of `HLoopInformation::Populate`,
91   // if needed.
92   void UpdateGraphFlags();
93 
94   // Helper struct to eliminate tries.
95   struct TryBelongingInformation;
96   // Disconnects `block`'s handlers and update its `TryBoundary` instruction to a `Goto`.
97   // Sets `any_block_in_loop` to true if any block is currently a loop to later update the loop
98   // information if needed.
99   void DisconnectHandlersAndUpdateTryBoundary(HBasicBlock* block,
100                                               /* out */ bool* any_block_in_loop);
101   // Returns true iff the try doesn't contain throwing instructions.
102   bool CanPerformTryRemoval(const TryBelongingInformation& try_belonging_info);
103   // Removes the try by disconnecting all try entries and exits from their handlers. Also updates
104   // the graph in the case that a `TryBoundary` instruction of kind `exit` has the Exit block as
105   // its successor.
106   void RemoveTry(HBasicBlock* try_entry,
107                  const TryBelongingInformation& try_belonging_info,
108                  bool* any_block_in_loop);
109   // Checks which tries (if any) are currently in the graph, coalesces the different try entries
110   // that are referencing the same try, and removes the tries which don't contain any throwing
111   // instructions.
112   bool RemoveUnneededTries();
113 
114   // Adds a phi in `block`, if `block` and its dominator have the same (or opposite) condition.
115   // For example it turns:
116   // if(cond)
117   //   /  \
118   //  B1  B2
119   //   \ /
120   // if(cond)
121   //   /  \
122   //  B3  B4
123   //
124   // into:
125   // if(cond)
126   //   /  \
127   //  B1  B2
128   //   \ /
129   // if(Phi(1, 0))
130   //   /  \
131   //  B3  B4
132   //
133   // Following this, SimplifyIfs is able to connect B1->B3 and B2->B4 effectively skipping an if.
134   void MaybeAddPhi(HBasicBlock* block);
135 
136   DISALLOW_COPY_AND_ASSIGN(HDeadCodeElimination);
137 };
138 
139 }  // namespace art
140 
141 #endif  // ART_COMPILER_OPTIMIZING_DEAD_CODE_ELIMINATION_H_
142