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_builder.h"
18
19 #include "nodes.h"
20 #include "ssa_type_propagation.h"
21
22 namespace art {
23
BuildSsa()24 void SsaBuilder::BuildSsa() {
25 // 1) Visit in reverse post order. We need to have all predecessors of a block visited
26 // (with the exception of loops) in order to create the right environment for that
27 // block. For loops, we create phis whose inputs will be set in 2).
28 for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
29 VisitBasicBlock(it.Current());
30 }
31
32 // 2) Set inputs of loop phis.
33 for (size_t i = 0; i < loop_headers_.Size(); i++) {
34 HBasicBlock* block = loop_headers_.Get(i);
35 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
36 HPhi* phi = it.Current()->AsPhi();
37 for (size_t pred = 0; pred < block->GetPredecessors().Size(); pred++) {
38 HInstruction* input = ValueOfLocal(block->GetPredecessors().Get(pred), phi->GetRegNumber());
39 phi->AddInput(input);
40 }
41 }
42 }
43
44 // 3) Propagate types of phis.
45 SsaTypePropagation type_propagation(GetGraph());
46 type_propagation.Run();
47
48 // 4) Clear locals.
49 // TODO: Move this to a dead code eliminator phase.
50 for (HInstructionIterator it(GetGraph()->GetEntryBlock()->GetInstructions());
51 !it.Done();
52 it.Advance()) {
53 HInstruction* current = it.Current();
54 if (current->AsLocal() != nullptr) {
55 current->GetBlock()->RemoveInstruction(current);
56 }
57 }
58 }
59
ValueOfLocal(HBasicBlock * block,size_t local)60 HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) {
61 return GetLocalsFor(block)->Get(local);
62 }
63
VisitBasicBlock(HBasicBlock * block)64 void SsaBuilder::VisitBasicBlock(HBasicBlock* block) {
65 current_locals_ = GetLocalsFor(block);
66
67 if (block->IsLoopHeader()) {
68 // If the block is a loop header, we know we only have visited the pre header
69 // because we are visiting in reverse post order. We create phis for all initialized
70 // locals from the pre header. Their inputs will be populated at the end of
71 // the analysis.
72 for (size_t local = 0; local < current_locals_->Size(); local++) {
73 HInstruction* incoming = ValueOfLocal(block->GetLoopInformation()->GetPreHeader(), local);
74 if (incoming != nullptr) {
75 HPhi* phi = new (GetGraph()->GetArena()) HPhi(
76 GetGraph()->GetArena(), local, 0, Primitive::kPrimVoid);
77 block->AddPhi(phi);
78 current_locals_->Put(local, phi);
79 }
80 }
81 // Save the loop header so that the last phase of the analysis knows which
82 // blocks need to be updated.
83 loop_headers_.Add(block);
84 } else if (block->GetPredecessors().Size() > 0) {
85 // All predecessors have already been visited because we are visiting in reverse post order.
86 // We merge the values of all locals, creating phis if those values differ.
87 for (size_t local = 0; local < current_locals_->Size(); local++) {
88 bool one_predecessor_has_no_value = false;
89 bool is_different = false;
90 HInstruction* value = ValueOfLocal(block->GetPredecessors().Get(0), local);
91
92 for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) {
93 HInstruction* current = ValueOfLocal(block->GetPredecessors().Get(i), local);
94 if (current == nullptr) {
95 one_predecessor_has_no_value = true;
96 break;
97 } else if (current != value) {
98 is_different = true;
99 }
100 }
101
102 if (one_predecessor_has_no_value) {
103 // If one predecessor has no value for this local, we trust the verifier has
104 // successfully checked that there is a store dominating any read after this block.
105 continue;
106 }
107
108 if (is_different) {
109 HPhi* phi = new (GetGraph()->GetArena()) HPhi(
110 GetGraph()->GetArena(), local, block->GetPredecessors().Size(), Primitive::kPrimVoid);
111 for (size_t i = 0; i < block->GetPredecessors().Size(); i++) {
112 HInstruction* value = ValueOfLocal(block->GetPredecessors().Get(i), local);
113 phi->SetRawInputAt(i, value);
114 }
115 block->AddPhi(phi);
116 value = phi;
117 }
118 current_locals_->Put(local, value);
119 }
120 }
121
122 // Visit all instructions. The instructions of interest are:
123 // - HLoadLocal: replace them with the current value of the local.
124 // - HStoreLocal: update current value of the local and remove the instruction.
125 // - Instructions that require an environment: populate their environment
126 // with the current values of the locals.
127 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
128 it.Current()->Accept(this);
129 }
130 }
131
VisitLoadLocal(HLoadLocal * load)132 void SsaBuilder::VisitLoadLocal(HLoadLocal* load) {
133 load->ReplaceWith(current_locals_->Get(load->GetLocal()->GetRegNumber()));
134 load->GetBlock()->RemoveInstruction(load);
135 }
136
VisitStoreLocal(HStoreLocal * store)137 void SsaBuilder::VisitStoreLocal(HStoreLocal* store) {
138 current_locals_->Put(store->GetLocal()->GetRegNumber(), store->InputAt(1));
139 store->GetBlock()->RemoveInstruction(store);
140 }
141
VisitInstruction(HInstruction * instruction)142 void SsaBuilder::VisitInstruction(HInstruction* instruction) {
143 if (!instruction->NeedsEnvironment()) {
144 return;
145 }
146 HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment(
147 GetGraph()->GetArena(), current_locals_->Size());
148 environment->Populate(*current_locals_);
149 instruction->SetEnvironment(environment);
150 }
151
152 } // namespace art
153