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