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 "prepare_for_register_allocation.h"
18
19namespace art {
20
21void PrepareForRegisterAllocation::Run() {
22  // Order does not matter.
23  for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) {
24    HBasicBlock* block = it.Current();
25    // No need to visit the phis.
26    for (HInstructionIterator inst_it(block->GetInstructions()); !inst_it.Done();
27         inst_it.Advance()) {
28      inst_it.Current()->Accept(this);
29    }
30  }
31}
32
33void PrepareForRegisterAllocation::VisitNullCheck(HNullCheck* check) {
34  check->ReplaceWith(check->InputAt(0));
35}
36
37void PrepareForRegisterAllocation::VisitDivZeroCheck(HDivZeroCheck* check) {
38  check->ReplaceWith(check->InputAt(0));
39}
40
41void PrepareForRegisterAllocation::VisitBoundsCheck(HBoundsCheck* check) {
42  check->ReplaceWith(check->InputAt(0));
43}
44
45void PrepareForRegisterAllocation::VisitBoundType(HBoundType* bound_type) {
46  bound_type->ReplaceWith(bound_type->InputAt(0));
47  bound_type->GetBlock()->RemoveInstruction(bound_type);
48}
49
50void PrepareForRegisterAllocation::VisitArraySet(HArraySet* instruction) {
51  HInstruction* value = instruction->GetValue();
52  // PrepareForRegisterAllocation::VisitBoundType may have replaced a
53  // BoundType (as value input of this ArraySet) with a NullConstant.
54  // If so, this ArraySet no longer needs a type check.
55  if (value->IsNullConstant()) {
56    DCHECK_EQ(value->GetType(), Primitive::kPrimNot);
57    if (instruction->NeedsTypeCheck()) {
58      instruction->ClearNeedsTypeCheck();
59    }
60  }
61}
62
63void PrepareForRegisterAllocation::VisitClinitCheck(HClinitCheck* check) {
64  // Try to find a static invoke or a new-instance from which this check originated.
65  HInstruction* implicit_clinit = nullptr;
66  for (const HUseListNode<HInstruction*>& use : check->GetUses()) {
67    HInstruction* user = use.GetUser();
68    if ((user->IsInvokeStaticOrDirect() || user->IsNewInstance()) &&
69        CanMoveClinitCheck(check, user)) {
70      implicit_clinit = user;
71      if (user->IsInvokeStaticOrDirect()) {
72        DCHECK(user->AsInvokeStaticOrDirect()->IsStaticWithExplicitClinitCheck());
73        user->AsInvokeStaticOrDirect()->RemoveExplicitClinitCheck(
74            HInvokeStaticOrDirect::ClinitCheckRequirement::kImplicit);
75      } else {
76        DCHECK(user->IsNewInstance());
77        // We delegate the initialization duty to the allocation.
78        if (user->AsNewInstance()->GetEntrypoint() == kQuickAllocObjectInitialized) {
79          user->AsNewInstance()->SetEntrypoint(kQuickAllocObjectResolved);
80        }
81      }
82      break;
83    }
84  }
85  // If we found a static invoke or new-instance for merging, remove the check
86  // from dominated static invokes.
87  if (implicit_clinit != nullptr) {
88    const HUseList<HInstruction*>& uses = check->GetUses();
89    for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
90      HInstruction* user = it->GetUser();
91      // All other uses must be dominated.
92      DCHECK(implicit_clinit->StrictlyDominates(user) || (implicit_clinit == user));
93      ++it;  // Advance before we remove the node, reference to the next node is preserved.
94      if (user->IsInvokeStaticOrDirect()) {
95        user->AsInvokeStaticOrDirect()->RemoveExplicitClinitCheck(
96            HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
97      }
98    }
99  }
100
101  HLoadClass* load_class = check->GetLoadClass();
102  bool can_merge_with_load_class = CanMoveClinitCheck(load_class, check);
103
104  check->ReplaceWith(load_class);
105
106  if (implicit_clinit != nullptr) {
107    // Remove the check from the graph. It has been merged into the invoke or new-instance.
108    check->GetBlock()->RemoveInstruction(check);
109    // Check if we can merge the load class as well.
110    if (can_merge_with_load_class && !load_class->HasUses()) {
111      load_class->GetBlock()->RemoveInstruction(load_class);
112    }
113  } else if (can_merge_with_load_class && !load_class->NeedsAccessCheck()) {
114    // Pass the initialization duty to the `HLoadClass` instruction,
115    // and remove the instruction from the graph.
116    load_class->SetMustGenerateClinitCheck(true);
117    check->GetBlock()->RemoveInstruction(check);
118  }
119}
120
121void PrepareForRegisterAllocation::VisitNewInstance(HNewInstance* instruction) {
122  HLoadClass* load_class = instruction->InputAt(0)->AsLoadClass();
123  bool has_only_one_use = load_class->HasOnlyOneNonEnvironmentUse();
124  // Change the entrypoint to kQuickAllocObject if either:
125  // - the class is finalizable (only kQuickAllocObject handles finalizable classes),
126  // - the class needs access checks (we do not know if it's finalizable),
127  // - or the load class has only one use.
128  if (instruction->IsFinalizable() || has_only_one_use || load_class->NeedsAccessCheck()) {
129    instruction->SetEntrypoint(kQuickAllocObject);
130    instruction->ReplaceInput(GetGraph()->GetIntConstant(load_class->GetTypeIndex()), 0);
131    // The allocation entry point that deals with access checks does not work with inlined
132    // methods, so we need to check whether this allocation comes from an inlined method.
133    // We also need to make the same check as for moving clinit check, whether the HLoadClass
134    // has the clinit check responsibility or not (HLoadClass can throw anyway).
135    if (has_only_one_use &&
136        !instruction->GetEnvironment()->IsFromInlinedInvoke() &&
137        CanMoveClinitCheck(load_class, instruction)) {
138      // We can remove the load class from the graph. If it needed access checks, we delegate
139      // the access check to the allocation.
140      if (load_class->NeedsAccessCheck()) {
141        instruction->SetEntrypoint(kQuickAllocObjectWithAccessCheck);
142      }
143      load_class->GetBlock()->RemoveInstruction(load_class);
144    }
145  }
146}
147
148bool PrepareForRegisterAllocation::CanEmitConditionAt(HCondition* condition,
149                                                      HInstruction* user) const {
150  if (condition->GetNext() != user) {
151    return false;
152  }
153
154  if (user->IsIf() || user->IsDeoptimize()) {
155    return true;
156  }
157
158  if (user->IsSelect() && user->AsSelect()->GetCondition() == condition) {
159    return true;
160  }
161
162  return false;
163}
164
165void PrepareForRegisterAllocation::VisitCondition(HCondition* condition) {
166  if (condition->HasOnlyOneNonEnvironmentUse()) {
167    HInstruction* user = condition->GetUses().front().GetUser();
168    if (CanEmitConditionAt(condition, user)) {
169      condition->MarkEmittedAtUseSite();
170    }
171  }
172}
173
174void PrepareForRegisterAllocation::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) {
175  if (invoke->IsStaticWithExplicitClinitCheck()) {
176    size_t last_input_index = invoke->InputCount() - 1;
177    HLoadClass* last_input = invoke->InputAt(last_input_index)->AsLoadClass();
178    DCHECK(last_input != nullptr)
179        << "Last input is not HLoadClass. It is " << last_input->DebugName();
180
181    // Detach the explicit class initialization check from the invoke.
182    // Keeping track of the initializing instruction is no longer required
183    // at this stage (i.e., after inlining has been performed).
184    invoke->RemoveExplicitClinitCheck(HInvokeStaticOrDirect::ClinitCheckRequirement::kNone);
185
186    // Merging with load class should have happened in VisitClinitCheck().
187    DCHECK(!CanMoveClinitCheck(last_input, invoke));
188  }
189}
190
191bool PrepareForRegisterAllocation::CanMoveClinitCheck(HInstruction* input,
192                                                      HInstruction* user) const {
193  // Determine if input and user come from the same dex instruction, so that we can move
194  // the clinit check responsibility from one to the other, i.e. from HClinitCheck (user)
195  // to HLoadClass (input), or from HClinitCheck (input) to HInvokeStaticOrDirect (user),
196  // or from HLoadClass (input) to HNewInstance (user).
197
198  // Start with a quick dex pc check.
199  if (user->GetDexPc() != input->GetDexPc()) {
200    return false;
201  }
202
203  // Now do a thorough environment check that this is really coming from the same instruction in
204  // the same inlined graph. Unfortunately, we have to go through the whole environment chain.
205  HEnvironment* user_environment = user->GetEnvironment();
206  HEnvironment* input_environment = input->GetEnvironment();
207  while (user_environment != nullptr || input_environment != nullptr) {
208    if (user_environment == nullptr || input_environment == nullptr) {
209      // Different environment chain length. This happens when a method is called
210      // once directly and once indirectly through another inlined method.
211      return false;
212    }
213    if (user_environment->GetDexPc() != input_environment->GetDexPc() ||
214        user_environment->GetMethodIdx() != input_environment->GetMethodIdx() ||
215        !IsSameDexFile(user_environment->GetDexFile(), input_environment->GetDexFile())) {
216      return false;
217    }
218    user_environment = user_environment->GetParent();
219    input_environment = input_environment->GetParent();
220  }
221
222  // Check for code motion taking the input to a different block.
223  if (user->GetBlock() != input->GetBlock()) {
224    return false;
225  }
226
227  // In debug mode, check that we have not inserted a throwing instruction
228  // or an instruction with side effects between input and user.
229  if (kIsDebugBuild) {
230    for (HInstruction* between = input->GetNext(); between != user; between = between->GetNext()) {
231      CHECK(between != nullptr);  // User must be after input in the same block.
232      CHECK(!between->CanThrow());
233      CHECK(!between->HasSideEffects());
234    }
235  }
236  return true;
237}
238
239}  // namespace art
240