ssa_phi_elimination.cc revision d59f3b1b7f5c1ab9f0731ff9dc60611e8d9a6ede
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 (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 (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 (const HUseListNode<HInstruction*>& use : phi->GetUses()) { 98 HInstruction* user = use.GetUser(); 99 DCHECK(user->IsLoopHeaderPhi()); 100 DCHECK(user->AsPhi()->IsDead()); 101 } 102 } 103 // Remove the phi from use lists of its inputs. 104 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 105 phi->RemoveAsUserOfInput(i); 106 } 107 // Remove the phi from environments that use it. 108 for (const HUseListNode<HEnvironment*>& use : phi->GetEnvUses()) { 109 HEnvironment* user = use.GetUser(); 110 user->SetRawEnvAt(use.GetIndex(), nullptr); 111 } 112 // Delete it from the instruction list. 113 block->RemovePhi(phi, /*ensure_safety=*/ false); 114 } 115 current = next; 116 } 117 } 118} 119 120void SsaRedundantPhiElimination::Run() { 121 // Add all phis in the worklist. Order does not matter for correctness, and 122 // neither will necessarily converge faster. 123 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 124 HBasicBlock* block = it.Current(); 125 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 126 worklist_.push_back(inst_it.Current()->AsPhi()); 127 } 128 } 129 130 ArenaSet<uint32_t> visited_phis_in_cycle(graph_->GetArena()->Adapter()); 131 ArenaVector<HPhi*> cycle_worklist(graph_->GetArena()->Adapter()); 132 133 while (!worklist_.empty()) { 134 HPhi* phi = worklist_.back(); 135 worklist_.pop_back(); 136 137 // If the phi has already been processed, continue. 138 if (!phi->IsInBlock()) { 139 continue; 140 } 141 142 if (phi->InputCount() == 0) { 143 DCHECK(phi->IsDead()); 144 continue; 145 } 146 147 HInstruction* candidate = nullptr; 148 visited_phis_in_cycle.clear(); 149 cycle_worklist.clear(); 150 151 cycle_worklist.push_back(phi); 152 visited_phis_in_cycle.insert(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 (size_t j = 0; j < phi->InputCount(); ++j) { 158 HInstruction* input = phi->InputAt(j); 159 if (input == phi) { 160 continue; 161 } else if (candidate == nullptr) { 162 candidate = input; 163 } else if (candidate != input) { 164 candidate = nullptr; 165 break; 166 } 167 } 168 169 // If we haven't found a candidate, check for a phi cycle. Note that we need to detect 170 // such cycles to avoid having reference and non-reference equivalents. We check this 171 // invariant in the graph checker. 172 if (candidate == nullptr) { 173 // We iterate over the array as long as it grows. 174 for (size_t i = 0; i < cycle_worklist.size(); ++i) { 175 HPhi* current = cycle_worklist[i]; 176 DCHECK(!current->IsLoopHeaderPhi() || 177 current->GetBlock()->IsLoopPreHeaderFirstPredecessor()); 178 179 for (size_t j = 0; j < current->InputCount(); ++j) { 180 HInstruction* input = current->InputAt(j); 181 if (input == current) { 182 continue; 183 } else if (input->IsPhi()) { 184 if (!ContainsElement(visited_phis_in_cycle, input->GetId())) { 185 cycle_worklist.push_back(input->AsPhi()); 186 visited_phis_in_cycle.insert(input->GetId()); 187 catch_phi_in_cycle |= input->AsPhi()->IsCatchPhi(); 188 irreducible_loop_phi_in_cycle |= input->IsIrreducibleLoopHeaderPhi(); 189 } else { 190 // Already visited, nothing to do. 191 } 192 } else if (candidate == nullptr) { 193 candidate = input; 194 } else if (candidate != input) { 195 candidate = nullptr; 196 // Clear the cycle worklist to break out of the outer loop. 197 cycle_worklist.clear(); 198 break; 199 } 200 } 201 } 202 } 203 204 if (candidate == nullptr) { 205 continue; 206 } 207 208 if (irreducible_loop_phi_in_cycle && !candidate->IsConstant()) { 209 // For irreducible loops, we need to keep the phis to satisfy our linear scan 210 // algorithm. 211 // There is one exception for constants, as the type propagation requires redundant 212 // cyclic phis of a constant to be removed. This is ok for the linear scan as it 213 // has to deal with constants anyway, and they can trivially be rematerialized. 214 continue; 215 } 216 217 for (HPhi* current : cycle_worklist) { 218 // The candidate may not dominate a phi in a catch block: there may be non-throwing 219 // instructions at the beginning of a try range, that may be the first input of 220 // catch phis. 221 // TODO(dbrazdil): Remove this situation by moving those non-throwing instructions 222 // before the try entry. 223 if (catch_phi_in_cycle) { 224 if (!candidate->StrictlyDominates(current)) { 225 continue; 226 } 227 } else { 228 DCHECK(candidate->StrictlyDominates(current)); 229 } 230 231 // Because we're updating the users of this phi, we may have new candidates 232 // for elimination. Add phis that use this phi to the worklist. 233 for (const HUseListNode<HInstruction*>& use : current->GetUses()) { 234 HInstruction* user = use.GetUser(); 235 if (user->IsPhi() && !ContainsElement(visited_phis_in_cycle, user->GetId())) { 236 worklist_.push_back(user->AsPhi()); 237 } 238 } 239 DCHECK(candidate->StrictlyDominates(current)); 240 current->ReplaceWith(candidate); 241 current->GetBlock()->RemovePhi(current); 242 } 243 } 244} 245 246} // namespace art 247