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 "base/bit_vector-inl.h" 20 21namespace art { 22 23static void MarkReachableBlocks(HBasicBlock* block, ArenaBitVector* visited) { 24 int block_id = block->GetBlockId(); 25 if (visited->IsBitSet(block_id)) { 26 return; 27 } 28 visited->SetBit(block_id); 29 30 HInstruction* last_instruction = block->GetLastInstruction(); 31 if (last_instruction->IsIf()) { 32 HIf* if_instruction = last_instruction->AsIf(); 33 HInstruction* condition = if_instruction->InputAt(0); 34 if (!condition->IsIntConstant()) { 35 MarkReachableBlocks(if_instruction->IfTrueSuccessor(), visited); 36 MarkReachableBlocks(if_instruction->IfFalseSuccessor(), visited); 37 } else if (condition->AsIntConstant()->IsOne()) { 38 MarkReachableBlocks(if_instruction->IfTrueSuccessor(), visited); 39 } else { 40 DCHECK(condition->AsIntConstant()->IsZero()); 41 MarkReachableBlocks(if_instruction->IfFalseSuccessor(), visited); 42 } 43 } else { 44 for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) { 45 MarkReachableBlocks(block->GetSuccessors().Get(i), visited); 46 } 47 } 48} 49 50static void MarkLoopHeadersContaining(const HBasicBlock& block, ArenaBitVector* set) { 51 for (HLoopInformationOutwardIterator it(block); !it.Done(); it.Advance()) { 52 set->SetBit(it.Current()->GetHeader()->GetBlockId()); 53 } 54} 55 56void HDeadCodeElimination::MaybeRecordDeadBlock(HBasicBlock* block) { 57 if (stats_ != nullptr) { 58 stats_->RecordStat(MethodCompilationStat::kRemovedDeadInstruction, 59 block->GetPhis().CountSize() + block->GetInstructions().CountSize()); 60 } 61} 62 63void HDeadCodeElimination::RemoveDeadBlocks() { 64 // Classify blocks as reachable/unreachable. 65 ArenaAllocator* allocator = graph_->GetArena(); 66 ArenaBitVector live_blocks(allocator, graph_->GetBlocks().Size(), false); 67 ArenaBitVector affected_loops(allocator, graph_->GetBlocks().Size(), false); 68 69 MarkReachableBlocks(graph_->GetEntryBlock(), &live_blocks); 70 bool removed_one_or_more_blocks = false; 71 72 // Remove all dead blocks. Iterate in post order because removal needs the 73 // block's chain of dominators and nested loops need to be updated from the 74 // inside out. 75 for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 76 HBasicBlock* block = it.Current(); 77 int id = block->GetBlockId(); 78 if (live_blocks.IsBitSet(id)) { 79 if (affected_loops.IsBitSet(id)) { 80 DCHECK(block->IsLoopHeader()); 81 block->GetLoopInformation()->Update(); 82 } 83 } else { 84 MaybeRecordDeadBlock(block); 85 MarkLoopHeadersContaining(*block, &affected_loops); 86 block->DisconnectAndDelete(); 87 removed_one_or_more_blocks = true; 88 } 89 } 90 91 // If we removed at least one block, we need to recompute the full 92 // dominator tree. 93 if (removed_one_or_more_blocks) { 94 graph_->ClearDominanceInformation(); 95 graph_->ComputeDominanceInformation(); 96 } 97 98 // Connect successive blocks created by dead branches. Order does not matter. 99 for (HReversePostOrderIterator it(*graph_); !it.Done();) { 100 HBasicBlock* block = it.Current(); 101 if (block->IsEntryBlock() || block->GetSuccessors().Size() != 1u) { 102 it.Advance(); 103 continue; 104 } 105 HBasicBlock* successor = block->GetSuccessors().Get(0); 106 if (successor->IsExitBlock() || successor->GetPredecessors().Size() != 1u) { 107 it.Advance(); 108 continue; 109 } 110 block->MergeWith(successor); 111 112 // Reiterate on this block in case it can be merged with its new successor. 113 } 114} 115 116void HDeadCodeElimination::RemoveDeadInstructions() { 117 // Process basic blocks in post-order in the dominator tree, so that 118 // a dead instruction depending on another dead instruction is removed. 119 for (HPostOrderIterator b(*graph_); !b.Done(); b.Advance()) { 120 HBasicBlock* block = b.Current(); 121 // Traverse this block's instructions in backward order and remove 122 // the unused ones. 123 HBackwardInstructionIterator i(block->GetInstructions()); 124 // Skip the first iteration, as the last instruction of a block is 125 // a branching instruction. 126 DCHECK(i.Current()->IsControlFlow()); 127 for (i.Advance(); !i.Done(); i.Advance()) { 128 HInstruction* inst = i.Current(); 129 DCHECK(!inst->IsControlFlow()); 130 if (!inst->HasSideEffects() 131 && !inst->CanThrow() 132 && !inst->IsSuspendCheck() 133 && !inst->IsMemoryBarrier() // If we added an explicit barrier then we should keep it. 134 && !inst->HasUses()) { 135 block->RemoveInstruction(inst); 136 MaybeRecordStat(MethodCompilationStat::kRemovedDeadInstruction); 137 } 138 } 139 } 140} 141 142void HDeadCodeElimination::Run() { 143 RemoveDeadBlocks(); 144 RemoveDeadInstructions(); 145} 146 147} // namespace art 148