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 "ssa_phi_elimination.h"
18
19 #include "base/arena_containers.h"
20 #include "base/arena_bit_vector.h"
21 #include "base/bit_vector-inl.h"
22
23 namespace art {
24
Run()25 void SsaDeadPhiElimination::Run() {
26 MarkDeadPhis();
27 EliminateDeadPhis();
28 }
29
MarkDeadPhis()30 void SsaDeadPhiElimination::MarkDeadPhis() {
31 // Phis are constructed live and should not be revived if previously marked
32 // dead. This algorithm temporarily breaks that invariant but we DCHECK that
33 // only phis which were initially live are revived.
34 ArenaSet<HPhi*> initially_live(graph_->GetArena()->Adapter(kArenaAllocSsaPhiElimination));
35
36 // Add to the worklist phis referenced by non-phi instructions.
37 for (HBasicBlock* block : graph_->GetReversePostOrder()) {
38 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
39 HPhi* phi = inst_it.Current()->AsPhi();
40 if (phi->IsDead()) {
41 continue;
42 }
43
44 bool keep_alive = (graph_->IsDebuggable() && phi->HasEnvironmentUses());
45 if (!keep_alive) {
46 for (const HUseListNode<HInstruction*>& use : phi->GetUses()) {
47 if (!use.GetUser()->IsPhi()) {
48 keep_alive = true;
49 break;
50 }
51 }
52 }
53
54 if (keep_alive) {
55 worklist_.push_back(phi);
56 } else {
57 phi->SetDead();
58 if (kIsDebugBuild) {
59 initially_live.insert(phi);
60 }
61 }
62 }
63 }
64
65 // Process the worklist by propagating liveness to phi inputs.
66 while (!worklist_.empty()) {
67 HPhi* phi = worklist_.back();
68 worklist_.pop_back();
69 for (HInstruction* raw_input : phi->GetInputs()) {
70 HPhi* input = raw_input->AsPhi();
71 if (input != nullptr && input->IsDead()) {
72 // Input is a dead phi. Revive it and add to the worklist. We make sure
73 // that the phi was not dead initially (see definition of `initially_live`).
74 DCHECK(ContainsElement(initially_live, input));
75 input->SetLive();
76 worklist_.push_back(input);
77 }
78 }
79 }
80 }
81
EliminateDeadPhis()82 void SsaDeadPhiElimination::EliminateDeadPhis() {
83 // Remove phis that are not live. Visit in post order so that phis
84 // that are not inputs of loop phis can be removed when they have
85 // no users left (dead phis might use dead phis).
86 for (HBasicBlock* block : graph_->GetPostOrder()) {
87 HInstruction* current = block->GetFirstPhi();
88 HInstruction* next = nullptr;
89 HPhi* phi;
90 while (current != nullptr) {
91 phi = current->AsPhi();
92 next = current->GetNext();
93 if (phi->IsDead()) {
94 // Make sure the phi is only used by other dead phis.
95 if (kIsDebugBuild) {
96 for (const HUseListNode<HInstruction*>& use : phi->GetUses()) {
97 HInstruction* user = use.GetUser();
98 DCHECK(user->IsLoopHeaderPhi());
99 DCHECK(user->AsPhi()->IsDead());
100 }
101 }
102 // Remove the phi from use lists of its inputs.
103 phi->RemoveAsUserOfAllInputs();
104 // Remove the phi from environments that use it.
105 for (const HUseListNode<HEnvironment*>& use : phi->GetEnvUses()) {
106 HEnvironment* user = use.GetUser();
107 user->SetRawEnvAt(use.GetIndex(), nullptr);
108 }
109 // Delete it from the instruction list.
110 block->RemovePhi(phi, /*ensure_safety=*/ false);
111 }
112 current = next;
113 }
114 }
115 }
116
Run()117 void SsaRedundantPhiElimination::Run() {
118 // Add all phis in the worklist. Order does not matter for correctness, and
119 // neither will necessarily converge faster.
120 for (HBasicBlock* block : graph_->GetReversePostOrder()) {
121 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
122 worklist_.push_back(inst_it.Current()->AsPhi());
123 }
124 }
125
126 ArenaBitVector visited_phis_in_cycle(graph_->GetArena(),
127 graph_->GetCurrentInstructionId(),
128 /* expandable */ false,
129 kArenaAllocSsaPhiElimination);
130 ArenaVector<HPhi*> cycle_worklist(graph_->GetArena()->Adapter(kArenaAllocSsaPhiElimination));
131
132 while (!worklist_.empty()) {
133 HPhi* phi = worklist_.back();
134 worklist_.pop_back();
135
136 // If the phi has already been processed, continue.
137 if (!phi->IsInBlock()) {
138 continue;
139 }
140
141 // If the phi is dead, we know we won't revive it and it will be removed,
142 // so don't process it.
143 if (phi->IsDead()) {
144 continue;
145 }
146
147 HInstruction* candidate = nullptr;
148 visited_phis_in_cycle.ClearAllBits();
149 cycle_worklist.clear();
150
151 cycle_worklist.push_back(phi);
152 visited_phis_in_cycle.SetBit(phi->GetId());
153 bool catch_phi_in_cycle = phi->IsCatchPhi();
154 bool irreducible_loop_phi_in_cycle = phi->IsIrreducibleLoopHeaderPhi();
155
156 // First do a simple loop over inputs and check if they are all the same.
157 for (HInstruction* input : phi->GetInputs()) {
158 if (input == phi) {
159 continue;
160 } else if (candidate == nullptr) {
161 candidate = input;
162 } else if (candidate != input) {
163 candidate = nullptr;
164 break;
165 }
166 }
167
168 // If we haven't found a candidate, check for a phi cycle. Note that we need to detect
169 // such cycles to avoid having reference and non-reference equivalents. We check this
170 // invariant in the graph checker.
171 if (candidate == nullptr) {
172 // We iterate over the array as long as it grows.
173 for (size_t i = 0; i < cycle_worklist.size(); ++i) {
174 HPhi* current = cycle_worklist[i];
175 DCHECK(!current->IsLoopHeaderPhi() ||
176 current->GetBlock()->IsLoopPreHeaderFirstPredecessor());
177
178 for (HInstruction* input : current->GetInputs()) {
179 if (input == current) {
180 continue;
181 } else if (input->IsPhi()) {
182 if (!visited_phis_in_cycle.IsBitSet(input->GetId())) {
183 cycle_worklist.push_back(input->AsPhi());
184 visited_phis_in_cycle.SetBit(input->GetId());
185 catch_phi_in_cycle |= input->AsPhi()->IsCatchPhi();
186 irreducible_loop_phi_in_cycle |= input->IsIrreducibleLoopHeaderPhi();
187 } else {
188 // Already visited, nothing to do.
189 }
190 } else if (candidate == nullptr) {
191 candidate = input;
192 } else if (candidate != input) {
193 candidate = nullptr;
194 // Clear the cycle worklist to break out of the outer loop.
195 cycle_worklist.clear();
196 break;
197 }
198 }
199 }
200 }
201
202 if (candidate == nullptr) {
203 continue;
204 }
205
206 if (irreducible_loop_phi_in_cycle && !candidate->IsConstant()) {
207 // For irreducible loops, we need to keep the phis to satisfy our linear scan
208 // algorithm.
209 // There is one exception for constants, as the type propagation requires redundant
210 // cyclic phis of a constant to be removed. This is ok for the linear scan as it
211 // has to deal with constants anyway, and they can trivially be rematerialized.
212 continue;
213 }
214
215 for (HPhi* current : cycle_worklist) {
216 // The candidate may not dominate a phi in a catch block: there may be non-throwing
217 // instructions at the beginning of a try range, that may be the first input of
218 // catch phis.
219 // TODO(dbrazdil): Remove this situation by moving those non-throwing instructions
220 // before the try entry.
221 if (catch_phi_in_cycle) {
222 if (!candidate->StrictlyDominates(current)) {
223 continue;
224 }
225 } else {
226 DCHECK(candidate->StrictlyDominates(current));
227 }
228
229 // Because we're updating the users of this phi, we may have new candidates
230 // for elimination. Add phis that use this phi to the worklist.
231 for (const HUseListNode<HInstruction*>& use : current->GetUses()) {
232 HInstruction* user = use.GetUser();
233 if (user->IsPhi() && !visited_phis_in_cycle.IsBitSet(user->GetId())) {
234 worklist_.push_back(user->AsPhi());
235 }
236 }
237 DCHECK(candidate->StrictlyDominates(current));
238 current->ReplaceWith(candidate);
239 current->GetBlock()->RemovePhi(current);
240 }
241 }
242 }
243
244 } // namespace art
245