ssa_phi_elimination.cc revision 3ac17fcce8773388512ce72cb491b202872ca1c1 
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 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 so that phis
57  // that are not inputs of loop phis can be removed when they have
58  // no users left (dead phis might use dead phis).
59  for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
60    HBasicBlock* block = it.Current();
61    HInstruction* current = block->GetFirstPhi();
62    HInstruction* next = nullptr;
63    while (current != nullptr) {
64      next = current->GetNext();
65      if (current->AsPhi()->IsDead()) {
66        if (current->HasUses()) {
67          for (HUseIterator<HInstruction> it(current->GetUses()); !it.Done(); it.Advance()) {
68            HUseListNode<HInstruction>* user_node = it.Current();
69            HInstruction* user = user_node->GetUser();
70            DCHECK(user->IsLoopHeaderPhi());
71            DCHECK(user->AsPhi()->IsDead());
72            // Just put itself as an input. The phi will be removed in this loop anyway.
73            user->SetRawInputAt(user_node->GetIndex(), user);
74            current->RemoveUser(user, user_node->GetIndex());
75          }
76        }
77        block->RemovePhi(current->AsPhi());
78      }
79      current = next;
80    }
81  }
82}
83
84void SsaRedundantPhiElimination::Run() {
85  // Add all phis in the worklist.
86  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
87    HBasicBlock* block = it.Current();
88    for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
89      worklist_.Add(it.Current()->AsPhi());
90    }
91  }
92
93  while (!worklist_.IsEmpty()) {
94    HPhi* phi = worklist_.Pop();
95
96    // If the phi has already been processed, continue.
97    if (!phi->IsInBlock()) {
98      continue;
99    }
100
101    // Find if the inputs of the phi are the same instruction.
102    HInstruction* candidate = phi->InputAt(0);
103    // A loop phi cannot have itself as the first phi.
104    DCHECK_NE(phi, candidate);
105
106    for (size_t i = 1; i < phi->InputCount(); ++i) {
107      HInstruction* input = phi->InputAt(i);
108      // For a loop phi, If the input is the phi, the phi is still candidate for
109      // elimination.
110      if (input != candidate && input != phi) {
111        candidate = nullptr;
112        break;
113      }
114    }
115
116    // If the inputs are not the same, continue.
117    if (candidate == nullptr) {
118      continue;
119    }
120
121    if (phi->IsInLoop()) {
122      // Because we're updating the users of this phi, we may have new
123      // phis candidate for elimination if this phi is in a loop. Add phis that
124      // used this phi to the worklist.
125      for (HUseIterator<HInstruction> it(phi->GetUses()); !it.Done(); it.Advance()) {
126        HUseListNode<HInstruction>* current = it.Current();
127        HInstruction* user = current->GetUser();
128        if (user->IsPhi()) {
129          worklist_.Add(user->AsPhi());
130        }
131      }
132    }
133    phi->ReplaceWith(candidate);
134    phi->GetBlock()->RemovePhi(phi);
135  }
136}
137
138}  // namespace art
139