ssa_phi_elimination.cc revision 809d70f5b268227dbd59432dc038c74d8351be29
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 21namespace art { 22 23void SsaDeadPhiElimination::Run() { 24 MarkDeadPhis(); 25 EliminateDeadPhis(); 26} 27 28void SsaDeadPhiElimination::MarkDeadPhis() { 29 // Phis are constructed live and should not be revived if previously marked 30 // dead. This algorithm temporarily breaks that invariant but we DCHECK that 31 // only phis which were initially live are revived. 32 ArenaSet<HPhi*> initially_live(graph_->GetArena()->Adapter()); 33 34 // Add to the worklist phis referenced by non-phi instructions. 35 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 36 HBasicBlock* block = it.Current(); 37 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 38 HPhi* phi = inst_it.Current()->AsPhi(); 39 if (phi->IsDead()) { 40 continue; 41 } 42 43 bool has_non_phi_use = false; 44 for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) { 45 if (!use_it.Current()->GetUser()->IsPhi()) { 46 has_non_phi_use = true; 47 break; 48 } 49 } 50 51 if (has_non_phi_use) { 52 worklist_.push_back(phi); 53 } else { 54 phi->SetDead(); 55 if (kIsDebugBuild) { 56 initially_live.insert(phi); 57 } 58 } 59 } 60 } 61 62 // Process the worklist by propagating liveness to phi inputs. 63 while (!worklist_.empty()) { 64 HPhi* phi = worklist_.back(); 65 worklist_.pop_back(); 66 for (HInputIterator it(phi); !it.Done(); it.Advance()) { 67 HPhi* input = it.Current()->AsPhi(); 68 if (input != nullptr && input->IsDead()) { 69 // Input is a dead phi. Revive it and add to the worklist. We make sure 70 // that the phi was not dead initially (see definition of `initially_live`). 71 DCHECK(ContainsElement(initially_live, input)); 72 input->SetLive(); 73 worklist_.push_back(input); 74 } 75 } 76 } 77} 78 79void SsaDeadPhiElimination::EliminateDeadPhis() { 80 // Remove phis that are not live. Visit in post order so that phis 81 // that are not inputs of loop phis can be removed when they have 82 // no users left (dead phis might use dead phis). 83 for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 84 HBasicBlock* block = it.Current(); 85 HInstruction* current = block->GetFirstPhi(); 86 HInstruction* next = nullptr; 87 HPhi* phi; 88 while (current != nullptr) { 89 phi = current->AsPhi(); 90 next = current->GetNext(); 91 if (phi->IsDead()) { 92 // Make sure the phi is only used by other dead phis. 93 if (kIsDebugBuild) { 94 for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); 95 use_it.Advance()) { 96 HInstruction* user = use_it.Current()->GetUser(); 97 DCHECK(user->IsLoopHeaderPhi()) << user->GetId(); 98 DCHECK(user->AsPhi()->IsDead()) << user->GetId(); 99 } 100 } 101 // Remove the phi from use lists of its inputs. 102 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 103 phi->RemoveAsUserOfInput(i); 104 } 105 // Remove the phi from environments that use it. 106 for (HUseIterator<HEnvironment*> use_it(phi->GetEnvUses()); !use_it.Done(); 107 use_it.Advance()) { 108 HUseListNode<HEnvironment*>* user_node = use_it.Current(); 109 HEnvironment* user = user_node->GetUser(); 110 user->SetRawEnvAt(user_node->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 while (!worklist_.empty()) { 131 HPhi* phi = worklist_.back(); 132 worklist_.pop_back(); 133 134 // If the phi has already been processed, continue. 135 if (!phi->IsInBlock()) { 136 continue; 137 } 138 139 if (phi->InputCount() == 0) { 140 DCHECK(phi->IsDead()); 141 continue; 142 } 143 144 // Find if the inputs of the phi are the same instruction. 145 HInstruction* candidate = phi->InputAt(0); 146 // A loop phi cannot have itself as the first phi. Note that this 147 // check relies on our simplification pass ensuring the pre-header 148 // block is first in the list of predecessors of the loop header. 149 DCHECK(!phi->IsLoopHeaderPhi() || phi->GetBlock()->IsLoopPreHeaderFirstPredecessor()); 150 DCHECK_NE(phi, candidate); 151 152 for (size_t i = 1; i < phi->InputCount(); ++i) { 153 HInstruction* input = phi->InputAt(i); 154 // For a loop phi, if the input is the phi, the phi is still candidate for 155 // elimination. 156 if (input != candidate && input != phi) { 157 candidate = nullptr; 158 break; 159 } 160 } 161 162 // If the inputs are not the same, continue. 163 if (candidate == nullptr) { 164 continue; 165 } 166 167 // The candidate may not dominate a phi in a catch block. 168 if (phi->IsCatchPhi() && !candidate->StrictlyDominates(phi)) { 169 continue; 170 } 171 172 // Because we're updating the users of this phi, we may have new candidates 173 // for elimination. Add phis that use this phi to the worklist. 174 for (HUseIterator<HInstruction*> it(phi->GetUses()); !it.Done(); it.Advance()) { 175 HUseListNode<HInstruction*>* current = it.Current(); 176 HInstruction* user = current->GetUser(); 177 if (user->IsPhi()) { 178 worklist_.push_back(user->AsPhi()); 179 } 180 } 181 182 phi->ReplaceWith(candidate); 183 phi->GetBlock()->RemovePhi(phi); 184 } 185} 186 187} // namespace art 188