ssa_phi_elimination.cc revision ed59619b370ef23ffbb25d1d01f615e60a9262b6
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 // Add to the worklist phis referenced by non-phi instructions. 23 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 24 HBasicBlock* block = it.Current(); 25 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 26 HPhi* phi = inst_it.Current()->AsPhi(); 27 // Set dead ahead of running through uses. The phi may have no use. 28 phi->SetDead(); 29 for (HUseIterator<HInstruction*> use_it(phi->GetUses()); !use_it.Done(); use_it.Advance()) { 30 HUseListNode<HInstruction*>* current = use_it.Current(); 31 HInstruction* user = current->GetUser(); 32 if (!user->IsPhi()) { 33 worklist_.Add(phi); 34 phi->SetLive(); 35 break; 36 } 37 } 38 } 39 } 40 41 // Process the worklist by propagating liveness to phi inputs. 42 while (!worklist_.IsEmpty()) { 43 HPhi* phi = worklist_.Pop(); 44 for (HInputIterator it(phi); !it.Done(); it.Advance()) { 45 HInstruction* input = it.Current(); 46 if (input->IsPhi() && input->AsPhi()->IsDead()) { 47 worklist_.Add(input->AsPhi()); 48 input->AsPhi()->SetLive(); 49 } 50 } 51 } 52 53 // Remove phis that are not live. Visit in post order so that phis 54 // that are not inputs of loop phis can be removed when they have 55 // no users left (dead phis might use dead phis). 56 for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 57 HBasicBlock* block = it.Current(); 58 HInstruction* current = block->GetFirstPhi(); 59 HInstruction* next = nullptr; 60 while (current != nullptr) { 61 next = current->GetNext(); 62 if (current->AsPhi()->IsDead()) { 63 if (current->HasUses()) { 64 for (HUseIterator<HInstruction*> use_it(current->GetUses()); !use_it.Done(); 65 use_it.Advance()) { 66 HUseListNode<HInstruction*>* user_node = use_it.Current(); 67 HInstruction* user = user_node->GetUser(); 68 DCHECK(user->IsLoopHeaderPhi()) << user->GetId(); 69 DCHECK(user->AsPhi()->IsDead()) << user->GetId(); 70 // Just put itself as an input. The phi will be removed in this loop anyway. 71 user->SetRawInputAt(user_node->GetIndex(), user); 72 current->RemoveUser(user, user_node->GetIndex()); 73 } 74 } 75 if (current->HasEnvironmentUses()) { 76 for (HUseIterator<HEnvironment*> use_it(current->GetEnvUses()); !use_it.Done(); 77 use_it.Advance()) { 78 HUseListNode<HEnvironment*>* user_node = use_it.Current(); 79 HEnvironment* user = user_node->GetUser(); 80 user->SetRawEnvAt(user_node->GetIndex(), nullptr); 81 current->RemoveEnvironmentUser(user_node); 82 } 83 } 84 block->RemovePhi(current->AsPhi()); 85 } 86 current = next; 87 } 88 } 89} 90 91void SsaRedundantPhiElimination::Run() { 92 // Add all phis in the worklist. 93 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 94 HBasicBlock* block = it.Current(); 95 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 96 worklist_.Add(inst_it.Current()->AsPhi()); 97 } 98 } 99 100 while (!worklist_.IsEmpty()) { 101 HPhi* phi = worklist_.Pop(); 102 103 // If the phi has already been processed, continue. 104 if (!phi->IsInBlock()) { 105 continue; 106 } 107 108 // Find if the inputs of the phi are the same instruction. 109 HInstruction* candidate = phi->InputAt(0); 110 // A loop phi cannot have itself as the first phi. Note that this 111 // check relies on our simplification pass ensuring the pre-header 112 // block is first in the list of predecessors of the loop header. 113 DCHECK(!phi->IsLoopHeaderPhi() || phi->GetBlock()->IsLoopPreHeaderFirstPredecessor()); 114 DCHECK_NE(phi, candidate); 115 116 for (size_t i = 1; i < phi->InputCount(); ++i) { 117 HInstruction* input = phi->InputAt(i); 118 // For a loop phi, if the input is the phi, the phi is still candidate for 119 // elimination. 120 if (input != candidate && input != phi) { 121 candidate = nullptr; 122 break; 123 } 124 } 125 126 // If the inputs are not the same, continue. 127 if (candidate == nullptr) { 128 continue; 129 } 130 131 if (phi->IsInLoop()) { 132 // Because we're updating the users of this phi, we may have new 133 // phis candidate for elimination if this phi is in a loop. Add phis that 134 // used this phi to the worklist. 135 for (HUseIterator<HInstruction*> it(phi->GetUses()); !it.Done(); it.Advance()) { 136 HUseListNode<HInstruction*>* current = it.Current(); 137 HInstruction* user = current->GetUser(); 138 if (user->IsPhi()) { 139 worklist_.Add(user->AsPhi()); 140 } 141 } 142 } 143 phi->ReplaceWith(candidate); 144 phi->GetBlock()->RemovePhi(phi); 145 } 146} 147 148} // namespace art 149