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 #include "dead_code_elimination.h" 18 19 #include "utils/array_ref.h" 20 #include "base/bit_vector-inl.h" 21 #include "ssa_phi_elimination.h" 22 23 namespace art { 24 25 static void MarkReachableBlocks(HGraph* graph, ArenaBitVector* visited) { 26 ArenaVector<HBasicBlock*> worklist(graph->GetArena()->Adapter(kArenaAllocDCE)); 27 constexpr size_t kDefaultWorlistSize = 8; 28 worklist.reserve(kDefaultWorlistSize); 29 visited->SetBit(graph->GetEntryBlock()->GetBlockId()); 30 worklist.push_back(graph->GetEntryBlock()); 31 32 while (!worklist.empty()) { 33 HBasicBlock* block = worklist.back(); 34 worklist.pop_back(); 35 int block_id = block->GetBlockId(); 36 DCHECK(visited->IsBitSet(block_id)); 37 38 ArrayRef<HBasicBlock* const> live_successors(block->GetSuccessors()); 39 HInstruction* last_instruction = block->GetLastInstruction(); 40 if (last_instruction->IsIf()) { 41 HIf* if_instruction = last_instruction->AsIf(); 42 HInstruction* condition = if_instruction->InputAt(0); 43 if (condition->IsIntConstant()) { 44 if (condition->AsIntConstant()->IsTrue()) { 45 live_successors = live_successors.SubArray(0u, 1u); 46 DCHECK_EQ(live_successors[0], if_instruction->IfTrueSuccessor()); 47 } else { 48 DCHECK(condition->AsIntConstant()->IsFalse()) << condition->AsIntConstant()->GetValue(); 49 live_successors = live_successors.SubArray(1u, 1u); 50 DCHECK_EQ(live_successors[0], if_instruction->IfFalseSuccessor()); 51 } 52 } 53 } else if (last_instruction->IsPackedSwitch()) { 54 HPackedSwitch* switch_instruction = last_instruction->AsPackedSwitch(); 55 HInstruction* switch_input = switch_instruction->InputAt(0); 56 if (switch_input->IsIntConstant()) { 57 int32_t switch_value = switch_input->AsIntConstant()->GetValue(); 58 int32_t start_value = switch_instruction->GetStartValue(); 59 // Note: Though the spec forbids packed-switch values to wrap around, we leave 60 // that task to the verifier and use unsigned arithmetic with it's "modulo 2^32" 61 // semantics to check if the value is in range, wrapped or not. 62 uint32_t switch_index = 63 static_cast<uint32_t>(switch_value) - static_cast<uint32_t>(start_value); 64 if (switch_index < switch_instruction->GetNumEntries()) { 65 live_successors = live_successors.SubArray(switch_index, 1u); 66 DCHECK_EQ(live_successors[0], block->GetSuccessors()[switch_index]); 67 } else { 68 live_successors = live_successors.SubArray(switch_instruction->GetNumEntries(), 1u); 69 DCHECK_EQ(live_successors[0], switch_instruction->GetDefaultBlock()); 70 } 71 } 72 } 73 74 for (HBasicBlock* successor : live_successors) { 75 // Add only those successors that have not been visited yet. 76 if (!visited->IsBitSet(successor->GetBlockId())) { 77 visited->SetBit(successor->GetBlockId()); 78 worklist.push_back(successor); 79 } 80 } 81 } 82 } 83 84 void HDeadCodeElimination::MaybeRecordDeadBlock(HBasicBlock* block) { 85 if (stats_ != nullptr) { 86 stats_->RecordStat(MethodCompilationStat::kRemovedDeadInstruction, 87 block->GetPhis().CountSize() + block->GetInstructions().CountSize()); 88 } 89 } 90 91 void HDeadCodeElimination::RemoveDeadBlocks() { 92 if (graph_->HasIrreducibleLoops()) { 93 // Do not eliminate dead blocks if the graph has irreducible loops. We could 94 // support it, but that would require changes in our loop representation to handle 95 // multiple entry points. We decided it was not worth the complexity. 96 return; 97 } 98 // Classify blocks as reachable/unreachable. 99 ArenaAllocator* allocator = graph_->GetArena(); 100 ArenaBitVector live_blocks(allocator, graph_->GetBlocks().size(), false, kArenaAllocDCE); 101 102 MarkReachableBlocks(graph_, &live_blocks); 103 bool removed_one_or_more_blocks = false; 104 bool rerun_dominance_and_loop_analysis = false; 105 106 // Remove all dead blocks. Iterate in post order because removal needs the 107 // block's chain of dominators and nested loops need to be updated from the 108 // inside out. 109 for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 110 HBasicBlock* block = it.Current(); 111 int id = block->GetBlockId(); 112 if (!live_blocks.IsBitSet(id)) { 113 MaybeRecordDeadBlock(block); 114 block->DisconnectAndDelete(); 115 removed_one_or_more_blocks = true; 116 if (block->IsInLoop()) { 117 rerun_dominance_and_loop_analysis = true; 118 } 119 } 120 } 121 122 // If we removed at least one block, we need to recompute the full 123 // dominator tree and try block membership. 124 if (removed_one_or_more_blocks) { 125 if (rerun_dominance_and_loop_analysis) { 126 graph_->ClearLoopInformation(); 127 graph_->ClearDominanceInformation(); 128 graph_->BuildDominatorTree(); 129 } else { 130 graph_->ClearDominanceInformation(); 131 graph_->ComputeDominanceInformation(); 132 graph_->ComputeTryBlockInformation(); 133 } 134 } 135 136 // Connect successive blocks created by dead branches. Order does not matter. 137 for (HReversePostOrderIterator it(*graph_); !it.Done();) { 138 HBasicBlock* block = it.Current(); 139 if (block->IsEntryBlock() || !block->GetLastInstruction()->IsGoto()) { 140 it.Advance(); 141 continue; 142 } 143 HBasicBlock* successor = block->GetSingleSuccessor(); 144 if (successor->IsExitBlock() || successor->GetPredecessors().size() != 1u) { 145 it.Advance(); 146 continue; 147 } 148 block->MergeWith(successor); 149 150 // Reiterate on this block in case it can be merged with its new successor. 151 } 152 } 153 154 void HDeadCodeElimination::RemoveDeadInstructions() { 155 // Process basic blocks in post-order in the dominator tree, so that 156 // a dead instruction depending on another dead instruction is removed. 157 for (HPostOrderIterator b(*graph_); !b.Done(); b.Advance()) { 158 HBasicBlock* block = b.Current(); 159 // Traverse this block's instructions in backward order and remove 160 // the unused ones. 161 HBackwardInstructionIterator i(block->GetInstructions()); 162 // Skip the first iteration, as the last instruction of a block is 163 // a branching instruction. 164 DCHECK(i.Current()->IsControlFlow()); 165 for (i.Advance(); !i.Done(); i.Advance()) { 166 HInstruction* inst = i.Current(); 167 DCHECK(!inst->IsControlFlow()); 168 if (!inst->HasSideEffects() 169 && !inst->CanThrow() 170 && !inst->IsSuspendCheck() 171 && !inst->IsNativeDebugInfo() 172 // If we added an explicit barrier then we should keep it. 173 && !inst->IsMemoryBarrier() 174 && !inst->IsParameterValue() 175 && !inst->HasUses()) { 176 block->RemoveInstruction(inst); 177 MaybeRecordStat(MethodCompilationStat::kRemovedDeadInstruction); 178 } 179 } 180 } 181 } 182 183 void HDeadCodeElimination::Run() { 184 RemoveDeadBlocks(); 185 SsaRedundantPhiElimination(graph_).Run(); 186 RemoveDeadInstructions(); 187 } 188 189 } // namespace art 190
