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
21 namespace art {
22
MarkReachableBlocks(HBasicBlock * block,ArenaBitVector * visited)23 static 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
MarkLoopHeadersContaining(const HBasicBlock & block,ArenaBitVector * set)50 static 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
MaybeRecordDeadBlock(HBasicBlock * block)56 void HDeadCodeElimination::MaybeRecordDeadBlock(HBasicBlock* block) {
57 if (stats_ != nullptr) {
58 stats_->RecordStat(MethodCompilationStat::kRemovedDeadInstruction,
59 block->GetPhis().CountSize() + block->GetInstructions().CountSize());
60 }
61 }
62
RemoveDeadBlocks()63 void 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
RemoveDeadInstructions()116 void 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
Run()142 void HDeadCodeElimination::Run() {
143 RemoveDeadBlocks();
144 RemoveDeadInstructions();
145 }
146
147 } // namespace art
148