Home | History | Annotate | Download | only in optimizing 
      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