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