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