ssa_builder.cc revision 184d640d2a3ac86d871dab58386a50cc9bb973f9 
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
22namespace art {
23
24void 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
60HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) {
61  return GetLocalsFor(block)->Get(local);
62}
63
64void 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
132void SsaBuilder::VisitLoadLocal(HLoadLocal* load) {
133  load->ReplaceWith(current_locals_->Get(load->GetLocal()->GetRegNumber()));
134  load->GetBlock()->RemoveInstruction(load);
135}
136
137void SsaBuilder::VisitStoreLocal(HStoreLocal* store) {
138  current_locals_->Put(store->GetLocal()->GetRegNumber(), store->InputAt(1));
139  store->GetBlock()->RemoveInstruction(store);
140}
141
142void 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