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 namespace art { 20 21 void 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 it(block->GetPhis()); !it.Done(); it.Advance()) { 26 HPhi* phi = it.Current()->AsPhi(); 27 if (phi->HasEnvironmentUses()) { 28 // TODO: Do we want to keep that phi alive? 29 continue; 30 } 31 for (HUseIterator<HInstruction> it(phi->GetUses()); !it.Done(); it.Advance()) { 32 HUseListNode<HInstruction>* current = it.Current(); 33 HInstruction* user = current->GetUser(); 34 if (!user->IsPhi()) { 35 worklist_.Add(phi); 36 phi->SetLive(); 37 } else { 38 phi->SetDead(); 39 } 40 } 41 } 42 } 43 44 // Process the worklist by propagating liveness to phi inputs. 45 while (!worklist_.IsEmpty()) { 46 HPhi* phi = worklist_.Pop(); 47 for (HInputIterator it(phi); !it.Done(); it.Advance()) { 48 HInstruction* input = it.Current(); 49 if (input->IsPhi() && input->AsPhi()->IsDead()) { 50 worklist_.Add(input->AsPhi()); 51 input->AsPhi()->SetLive(); 52 } 53 } 54 } 55 56 // Remove phis that are not live. Visit in post order to ensure 57 // we only remove phis with no users (dead phis might use dead phis). 58 for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 59 HBasicBlock* block = it.Current(); 60 HInstruction* current = block->GetFirstPhi(); 61 HInstruction* next = nullptr; 62 while (current != nullptr) { 63 next = current->GetNext(); 64 if (current->AsPhi()->IsDead()) { 65 block->RemovePhi(current->AsPhi()); 66 } 67 current = next; 68 } 69 } 70 } 71 72 void SsaRedundantPhiElimination::Run() { 73 // Add all phis in the worklist. 74 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 75 HBasicBlock* block = it.Current(); 76 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 77 worklist_.Add(it.Current()->AsPhi()); 78 } 79 } 80 81 while (!worklist_.IsEmpty()) { 82 HPhi* phi = worklist_.Pop(); 83 84 // If the phi has already been processed, continue. 85 if (!phi->IsInBlock()) { 86 continue; 87 } 88 89 // Find if the inputs of the phi are the same instruction. 90 HInstruction* candidate = phi->InputAt(0); 91 // A loop phi cannot have itself as the first phi. 92 DCHECK_NE(phi, candidate); 93 94 for (size_t i = 1; i < phi->InputCount(); ++i) { 95 HInstruction* input = phi->InputAt(i); 96 // For a loop phi, If the input is the phi, the phi is still candidate for 97 // elimination. 98 if (input != candidate && input != phi) { 99 candidate = nullptr; 100 break; 101 } 102 } 103 104 // If the inputs are not the same, continue. 105 if (candidate == nullptr) { 106 continue; 107 } 108 109 if (phi->IsInLoop()) { 110 // Because we're updating the users of this phi, we may have new 111 // phis candidate for elimination if this phi is in a loop. Add phis that 112 // used this phi to the worklist. 113 for (HUseIterator<HInstruction> it(phi->GetUses()); !it.Done(); it.Advance()) { 114 HUseListNode<HInstruction>* current = it.Current(); 115 HInstruction* user = current->GetUser(); 116 if (user->IsPhi()) { 117 worklist_.Add(user->AsPhi()); 118 } 119 } 120 } 121 phi->ReplaceWith(candidate); 122 phi->GetBlock()->RemovePhi(phi); 123 } 124 } 125 126 } // namespace art 127