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 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
72void 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