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 "primitive_type_propagation.h"
18
19#include "nodes.h"
20#include "ssa_builder.h"
21
22namespace art {
23
24static Primitive::Type MergeTypes(Primitive::Type existing, Primitive::Type new_type) {
25  // We trust the verifier has already done the necessary checking.
26  switch (existing) {
27    case Primitive::kPrimFloat:
28    case Primitive::kPrimDouble:
29    case Primitive::kPrimNot:
30      return existing;
31    default:
32      // Phis are initialized with a void type, so if we are asked
33      // to merge with a void type, we should use the existing one.
34      return new_type == Primitive::kPrimVoid
35          ? existing
36          : HPhi::ToPhiType(new_type);
37  }
38}
39
40// Re-compute and update the type of the instruction. Returns
41// whether or not the type was changed.
42bool PrimitiveTypePropagation::UpdateType(HPhi* phi) {
43  DCHECK(phi->IsLive());
44  Primitive::Type existing = phi->GetType();
45
46  Primitive::Type new_type = existing;
47  for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
48    Primitive::Type input_type = phi->InputAt(i)->GetType();
49    new_type = MergeTypes(new_type, input_type);
50  }
51  phi->SetType(new_type);
52
53  if (new_type == Primitive::kPrimDouble
54      || new_type == Primitive::kPrimFloat
55      || new_type == Primitive::kPrimNot) {
56    // If the phi is of floating point type, we need to update its inputs to that
57    // type. For inputs that are phis, we need to recompute their types.
58    for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
59      HInstruction* input = phi->InputAt(i);
60      if (input->GetType() != new_type) {
61        HInstruction* equivalent = (new_type == Primitive::kPrimNot)
62            ? SsaBuilder::GetReferenceTypeEquivalent(input)
63            : SsaBuilder::GetFloatOrDoubleEquivalent(phi, input, new_type);
64        phi->ReplaceInput(equivalent, i);
65        if (equivalent->IsPhi()) {
66          equivalent->AsPhi()->SetLive();
67          AddToWorklist(equivalent->AsPhi());
68        } else if (equivalent == input) {
69          // The input has changed its type. It can be an input of other phis,
70          // so we need to put phi users in the work list.
71          AddDependentInstructionsToWorklist(equivalent);
72        }
73      }
74    }
75  }
76
77  return existing != new_type;
78}
79
80void PrimitiveTypePropagation::Run() {
81  for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
82    VisitBasicBlock(it.Current());
83  }
84  ProcessWorklist();
85}
86
87void PrimitiveTypePropagation::VisitBasicBlock(HBasicBlock* block) {
88  if (block->IsLoopHeader()) {
89    for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
90      HPhi* phi = it.Current()->AsPhi();
91      if (phi->IsLive()) {
92        AddToWorklist(phi);
93      }
94    }
95  } else {
96    for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
97      // Eagerly compute the type of the phi, for quicker convergence. Note
98      // that we don't need to add users to the worklist because we are
99      // doing a reverse post-order visit, therefore either the phi users are
100      // non-loop phi and will be visited later in the visit, or are loop-phis,
101      // and they are already in the work list.
102      HPhi* phi = it.Current()->AsPhi();
103      if (phi->IsLive()) {
104        UpdateType(phi);
105      }
106    }
107  }
108}
109
110void PrimitiveTypePropagation::ProcessWorklist() {
111  while (!worklist_.IsEmpty()) {
112    HPhi* instruction = worklist_.Pop();
113    if (UpdateType(instruction)) {
114      AddDependentInstructionsToWorklist(instruction);
115    }
116  }
117}
118
119void PrimitiveTypePropagation::AddToWorklist(HPhi* instruction) {
120  DCHECK(instruction->IsLive());
121  worklist_.Add(instruction);
122}
123
124void PrimitiveTypePropagation::AddDependentInstructionsToWorklist(HInstruction* instruction) {
125  for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) {
126    HPhi* phi = it.Current()->GetUser()->AsPhi();
127    if (phi != nullptr && phi->IsLive() && phi->GetType() != instruction->GetType()) {
128      AddToWorklist(phi);
129    }
130  }
131}
132
133}  // namespace art
134