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 // If `force_recomputation` is true, we will recompute the dominance information even when we 44 // didn't delete any blocks. `force_loop_recomputation` is similar but it also forces the loop 45 // information recomputation. 46 bool RemoveDeadBlocks(bool force_recomputation = false, bool force_loop_recomputation = false); 47 void RemoveDeadInstructions(); 48 bool SimplifyAlwaysThrows(); 49 // Simplify the pattern: 50 // 51 // B1 B2 ... 52 // goto goto goto 53 // \ | / 54 // \ | / 55 // B3 56 // i1 = phi(input, input) 57 // (i2 = condition on i1) 58 // if i1 (or i2) 59 // / \ 60 // / \ 61 // B4 B5 62 // 63 // Into: 64 // 65 // B1 B2 ... 66 // | | | 67 // B4 B5 B? 68 // 69 // Note that individual edges can be redirected (for example B2->B3 70 // can be redirected as B2->B5) without applying this optimization 71 // to other incoming edges. 72 // 73 // Note that we rely on the dead code elimination to get rid of B3. 74 bool SimplifyIfs(); 75 void ConnectSuccessiveBlocks(); 76 // Updates the graph flags related to instructions (e.g. HasSIMD()) since we may have eliminated 77 // the relevant instructions. There's no need to update `SetHasTryCatch` since we do that in 78 // `ComputeTryBlockInformation`. Similarly with `HasLoops` and `HasIrreducibleLoops`: They are 79 // cleared in `ClearLoopInformation` and then set as true as part of `HLoopInformation::Populate`, 80 // if needed. 81 void UpdateGraphFlags(); 82 83 // Helper struct to eliminate tries. 84 struct TryBelongingInformation; 85 // Disconnects `block`'s handlers and update its `TryBoundary` instruction to a `Goto`. 86 // Sets `any_block_in_loop` to true if any block is currently a loop to later update the loop 87 // information if needed. 88 void DisconnectHandlersAndUpdateTryBoundary(HBasicBlock* block, 89 /* out */ bool* any_block_in_loop); 90 // Returns true iff the try doesn't contain throwing instructions. 91 bool CanPerformTryRemoval(const TryBelongingInformation& try_belonging_info); 92 // Removes the try by disconnecting all try entries and exits from their handlers. Also updates 93 // the graph in the case that a `TryBoundary` instruction of kind `exit` has the Exit block as 94 // its successor. 95 void RemoveTry(HBasicBlock* try_entry, 96 const TryBelongingInformation& try_belonging_info, 97 bool* any_block_in_loop); 98 // Checks which tries (if any) are currently in the graph, coalesces the different try entries 99 // that are referencing the same try, and removes the tries which don't contain any throwing 100 // instructions. 101 bool RemoveUnneededTries(); 102 103 // Adds a phi in `block`, if `block` and its dominator have the same (or opposite) condition. 104 // For example it turns: 105 // if(cond) 106 // / \ 107 // B1 B2 108 // \ / 109 // if(cond) 110 // / \ 111 // B3 B4 112 // 113 // into: 114 // if(cond) 115 // / \ 116 // B1 B2 117 // \ / 118 // if(Phi(1, 0)) 119 // / \ 120 // B3 B4 121 // 122 // Following this, SimplifyIfs is able to connect B1->B3 and B2->B4 effectively skipping an if. 123 void MaybeAddPhi(HBasicBlock* block); 124 125 DISALLOW_COPY_AND_ASSIGN(HDeadCodeElimination); 126 }; 127 128 } // namespace art 129 130 #endif // ART_COMPILER_OPTIMIZING_DEAD_CODE_ELIMINATION_H_ 131