ssa_phi_elimination.cc revision f5f64efda943000168d34bfe44ccbbadd284e55f
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/bit_vector-inl.h" 21 22namespace art { 23 24void SsaDeadPhiElimination::Run() { 25 MarkDeadPhis(); 26 EliminateDeadPhis(); 27} 28 29void SsaDeadPhiElimination::MarkDeadPhis() { 30 // Phis are constructed live and should not be revived if previously marked 31 // dead. This algorithm temporarily breaks that invariant but we DCHECK that 32 // only phis which were initially live are revived. 33 ArenaSet<HPhi*> initially_live(graph_->GetArena()->Adapter()); 34 35 // Add to the worklist phis referenced by non-phi instructions. 36 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 37 HBasicBlock* block = it.Current(); 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 (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) { 47 if (!use_it.Current()->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 (HInputIterator it(phi); !it.Done(); it.Advance()) { 70 HPhi* input = it.Current()->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 82void 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 (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 87 HBasicBlock* block = it.Current(); 88 HInstruction* current = block->GetFirstPhi(); 89 HInstruction* next = nullptr; 90 HPhi* phi; 91 while (current != nullptr) { 92 phi = current->AsPhi(); 93 next = current->GetNext(); 94 if (phi->IsDead()) { 95 // Make sure the phi is only used by other dead phis. 96 if (kIsDebugBuild) { 97 for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); 98 use_it.Advance()) { 99 HInstruction* user = use_it.Current()->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 (HUseIterator<HEnvironment*> use_it(phi->GetEnvUses()); !use_it.Done(); 110 use_it.Advance()) { 111 HUseListNode<HEnvironment*>* user_node = use_it.Current(); 112 HEnvironment* user = user_node->GetUser(); 113 user->SetRawEnvAt(user_node->GetIndex(), nullptr); 114 } 115 // Delete it from the instruction list. 116 block->RemovePhi(phi, /*ensure_safety=*/ false); 117 } 118 current = next; 119 } 120 } 121} 122 123void SsaRedundantPhiElimination::Run() { 124 // Add all phis in the worklist. Order does not matter for correctness, and 125 // neither will necessarily converge faster. 126 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 127 HBasicBlock* block = it.Current(); 128 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 129 worklist_.push_back(inst_it.Current()->AsPhi()); 130 } 131 } 132 133 ArenaSet<uint32_t> visited_phis_in_cycle(graph_->GetArena()->Adapter()); 134 ArenaVector<HPhi*> cycle_worklist(graph_->GetArena()->Adapter()); 135 136 while (!worklist_.empty()) { 137 HPhi* phi = worklist_.back(); 138 worklist_.pop_back(); 139 140 // If the phi has already been processed, continue. 141 if (!phi->IsInBlock()) { 142 continue; 143 } 144 145 if (phi->InputCount() == 0) { 146 DCHECK(phi->IsDead()); 147 continue; 148 } 149 150 HInstruction* candidate = nullptr; 151 visited_phis_in_cycle.clear(); 152 cycle_worklist.clear(); 153 154 cycle_worklist.push_back(phi); 155 visited_phis_in_cycle.insert(phi->GetId()); 156 bool catch_phi_in_cycle = phi->IsCatchPhi(); 157 158 // First do a simple loop over inputs and check if they are all the same. 159 for (size_t j = 0; j < phi->InputCount(); ++j) { 160 HInstruction* input = phi->InputAt(j); 161 if (input == phi) { 162 continue; 163 } else if (candidate == nullptr) { 164 candidate = input; 165 } else if (candidate != input) { 166 candidate = nullptr; 167 break; 168 } 169 } 170 171 // If we haven't found a candidate, check for a phi cycle. Note that we need to detect 172 // such cycles to avoid having reference and non-reference equivalents. We check this 173 // invariant in the graph checker. 174 if (candidate == nullptr) { 175 // We iterate over the array as long as it grows. 176 for (size_t i = 0; i < cycle_worklist.size(); ++i) { 177 HPhi* current = cycle_worklist[i]; 178 DCHECK(!current->IsLoopHeaderPhi() || 179 current->GetBlock()->IsLoopPreHeaderFirstPredecessor()); 180 181 for (size_t j = 0; j < current->InputCount(); ++j) { 182 HInstruction* input = current->InputAt(j); 183 if (input == current) { 184 continue; 185 } else if (input->IsPhi()) { 186 if (!ContainsElement(visited_phis_in_cycle, input->GetId())) { 187 cycle_worklist.push_back(input->AsPhi()); 188 visited_phis_in_cycle.insert(input->GetId()); 189 catch_phi_in_cycle |= input->AsPhi()->IsCatchPhi(); 190 } else { 191 // Already visited, nothing to do. 192 } 193 } else if (candidate == nullptr) { 194 candidate = input; 195 } else if (candidate != input) { 196 candidate = nullptr; 197 // Clear the cycle worklist to break out of the outer loop. 198 cycle_worklist.clear(); 199 break; 200 } 201 } 202 } 203 } 204 205 if (candidate == nullptr) { 206 continue; 207 } 208 209 for (HPhi* current : cycle_worklist) { 210 // The candidate may not dominate a phi in a catch block: there may be non-throwing 211 // instructions at the beginning of a try range, that may be the first input of 212 // catch phis. 213 // TODO(dbrazdil): Remove this situation by moving those non-throwing instructions 214 // before the try entry. 215 if (catch_phi_in_cycle) { 216 if (!candidate->StrictlyDominates(current)) { 217 continue; 218 } 219 } else { 220 DCHECK(candidate->StrictlyDominates(current)); 221 } 222 223 // Because we're updating the users of this phi, we may have new candidates 224 // for elimination. Add phis that use this phi to the worklist. 225 for (HUseIterator<HInstruction*> it(current->GetUses()); !it.Done(); it.Advance()) { 226 HUseListNode<HInstruction*>* use = it.Current(); 227 HInstruction* user = use->GetUser(); 228 if (user->IsPhi() && !ContainsElement(visited_phis_in_cycle, user->GetId())) { 229 worklist_.push_back(user->AsPhi()); 230 } 231 } 232 DCHECK(candidate->StrictlyDominates(current)); 233 current->ReplaceWith(candidate); 234 current->GetBlock()->RemovePhi(current); 235 } 236 } 237} 238 239} // namespace art 240