ssa_phi_elimination.cc revision 1749e2cfb5c5ed4d6970a09aecf898ca9cdfcb75
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 19namespace art { 20 21void SsaDeadPhiElimination::Run() { 22 MarkDeadPhis(); 23 EliminateDeadPhis(); 24} 25 26void SsaDeadPhiElimination::MarkDeadPhis() { 27 // Add to the worklist phis referenced by non-phi instructions. 28 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 29 HBasicBlock* block = it.Current(); 30 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 31 HPhi* phi = inst_it.Current()->AsPhi(); 32 if (phi->IsDead()) { 33 // Phis are constructed live so this one was proven conflicting. 34 continue; 35 } 36 37 bool is_live = false; 38 if (graph_->IsDebuggable() && phi->HasEnvironmentUses()) { 39 is_live = true; 40 } else { 41 for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) { 42 if (!use_it.Current()->GetUser()->IsPhi()) { 43 is_live = true; 44 break; 45 } 46 } 47 } 48 49 if (is_live) { 50 worklist_.push_back(phi); 51 } else { 52 phi->SetDead(); 53 } 54 } 55 } 56 57 // Process the worklist by propagating liveness to phi inputs. 58 while (!worklist_.empty()) { 59 HPhi* phi = worklist_.back(); 60 worklist_.pop_back(); 61 for (HInputIterator it(phi); !it.Done(); it.Advance()) { 62 HInstruction* input = it.Current(); 63 if (input->IsPhi() && input->AsPhi()->IsDead()) { 64 // If we revive a phi it must have been live at the beginning of 65 // the pass but had no non-phi uses of its own. 66 input->AsPhi()->SetLive(); 67 worklist_.push_back(input->AsPhi()); 68 } 69 } 70 } 71} 72 73void SsaDeadPhiElimination::EliminateDeadPhis() { 74 // Remove phis that are not live. Visit in post order so that phis 75 // that are not inputs of loop phis can be removed when they have 76 // no users left (dead phis might use dead phis). 77 for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 78 HBasicBlock* block = it.Current(); 79 HInstruction* current = block->GetFirstPhi(); 80 HInstruction* next = nullptr; 81 HPhi* phi; 82 while (current != nullptr) { 83 phi = current->AsPhi(); 84 next = current->GetNext(); 85 if (phi->IsDead()) { 86 // Make sure the phi is only used by other dead phis. 87 if (kIsDebugBuild) { 88 for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); 89 use_it.Advance()) { 90 HInstruction* user = use_it.Current()->GetUser(); 91 DCHECK(user->IsPhi()); 92 DCHECK(user->AsPhi()->IsDead()); 93 } 94 } 95 // Remove the phi from use lists of its inputs. 96 for (size_t i = 0, e = phi->InputCount(); i < e; ++i) { 97 phi->RemoveAsUserOfInput(i); 98 } 99 // Remove the phi from environments that use it. 100 for (HUseIterator<HEnvironment*> use_it(phi->GetEnvUses()); !use_it.Done(); 101 use_it.Advance()) { 102 HUseListNode<HEnvironment*>* user_node = use_it.Current(); 103 HEnvironment* user = user_node->GetUser(); 104 user->SetRawEnvAt(user_node->GetIndex(), nullptr); 105 } 106 // Delete it from the instruction list. 107 block->RemovePhi(phi, /*ensure_safety=*/ false); 108 } 109 current = next; 110 } 111 } 112} 113 114void SsaRedundantPhiElimination::Run() { 115 // Add all phis in the worklist. Order does not matter for correctness, and 116 // neither will necessarily converge faster. 117 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 118 HBasicBlock* block = it.Current(); 119 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 120 worklist_.push_back(inst_it.Current()->AsPhi()); 121 } 122 } 123 124 while (!worklist_.empty()) { 125 HPhi* phi = worklist_.back(); 126 worklist_.pop_back(); 127 128 // If the phi has already been processed, continue. 129 if (!phi->IsInBlock()) { 130 continue; 131 } 132 133 if (phi->InputCount() == 0) { 134 DCHECK(phi->IsCatchPhi()); 135 DCHECK(phi->IsDead()); 136 continue; 137 } 138 139 // Find if the inputs of the phi are the same instruction. 140 HInstruction* candidate = phi->InputAt(0); 141 // A loop phi cannot have itself as the first phi. Note that this 142 // check relies on our simplification pass ensuring the pre-header 143 // block is first in the list of predecessors of the loop header. 144 DCHECK(!phi->IsLoopHeaderPhi() || phi->GetBlock()->IsLoopPreHeaderFirstPredecessor()); 145 DCHECK_NE(phi, candidate); 146 147 for (size_t i = 1; i < phi->InputCount(); ++i) { 148 HInstruction* input = phi->InputAt(i); 149 // For a loop phi, if the input is the phi, the phi is still candidate for 150 // elimination. 151 if (input != candidate && input != phi) { 152 candidate = nullptr; 153 break; 154 } 155 } 156 157 // If the inputs are not the same, continue. 158 if (candidate == nullptr) { 159 continue; 160 } 161 162 // The candidate may not dominate a phi in a catch block. 163 if (phi->IsCatchPhi() && !candidate->StrictlyDominates(phi)) { 164 continue; 165 } 166 167 // Because we're updating the users of this phi, we may have new candidates 168 // for elimination. Add phis that use this phi to the worklist. 169 for (HUseIterator<HInstruction*> it(phi->GetUses()); !it.Done(); it.Advance()) { 170 HUseListNode<HInstruction*>* current = it.Current(); 171 HInstruction* user = current->GetUser(); 172 if (user->IsPhi()) { 173 worklist_.push_back(user->AsPhi()); 174 } 175 } 176 177 phi->ReplaceWith(candidate); 178 phi->GetBlock()->RemovePhi(phi); 179 } 180} 181 182} // namespace art 183