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
Run()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
Run()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