Nicolas Geoffray | 26a25ef | 2014-09-30 13:54:09 +0100 | [diff] [blame] | 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 | |
| 19 | namespace art { |
| 20 | |
| 21 | void PrepareForRegisterAllocation::Run() { |
| 22 | // Order does not matter. |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 23 | for (HBasicBlock* block : GetGraph()->GetReversePostOrder()) { |
Nicolas Geoffray | 26a25ef | 2014-09-30 13:54:09 +0100 | [diff] [blame] | 24 | // No need to visit the phis. |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 25 | for (HInstructionIterator inst_it(block->GetInstructions()); !inst_it.Done(); |
| 26 | inst_it.Advance()) { |
| 27 | inst_it.Current()->Accept(this); |
Nicolas Geoffray | 26a25ef | 2014-09-30 13:54:09 +0100 | [diff] [blame] | 28 | } |
| 29 | } |
| 30 | } |
| 31 | |
| 32 | void PrepareForRegisterAllocation::VisitNullCheck(HNullCheck* check) { |
| 33 | check->ReplaceWith(check->InputAt(0)); |
| 34 | } |
| 35 | |
Calin Juravle | d0d4852 | 2014-11-04 16:40:20 +0000 | [diff] [blame] | 36 | void PrepareForRegisterAllocation::VisitDivZeroCheck(HDivZeroCheck* check) { |
| 37 | check->ReplaceWith(check->InputAt(0)); |
| 38 | } |
| 39 | |
Nicolas Geoffray | 26a25ef | 2014-09-30 13:54:09 +0100 | [diff] [blame] | 40 | void PrepareForRegisterAllocation::VisitBoundsCheck(HBoundsCheck* check) { |
| 41 | check->ReplaceWith(check->InputAt(0)); |
Vladimir Marko | 87f3fcb | 2016-04-28 15:52:11 +0100 | [diff] [blame] | 42 | if (check->IsStringCharAt()) { |
| 43 | // Add a fake environment for String.charAt() inline info as we want |
| 44 | // the exception to appear as being thrown from there. |
| 45 | const DexFile& dex_file = check->GetEnvironment()->GetDexFile(); |
David Sehr | 709b070 | 2016-10-13 09:12:37 -0700 | [diff] [blame] | 46 | DCHECK_STREQ(dex_file.PrettyMethod(check->GetStringCharAtMethodIndex()).c_str(), |
Vladimir Marko | 87f3fcb | 2016-04-28 15:52:11 +0100 | [diff] [blame] | 47 | "char java.lang.String.charAt(int)"); |
| 48 | ArenaAllocator* arena = GetGraph()->GetArena(); |
| 49 | HEnvironment* environment = new (arena) HEnvironment(arena, |
| 50 | /* number_of_vregs */ 0u, |
| 51 | dex_file, |
| 52 | check->GetStringCharAtMethodIndex(), |
| 53 | /* dex_pc */ DexFile::kDexNoIndex, |
| 54 | kVirtual, |
| 55 | check); |
| 56 | check->InsertRawEnvironment(environment); |
| 57 | } |
Nicolas Geoffray | 26a25ef | 2014-09-30 13:54:09 +0100 | [diff] [blame] | 58 | } |
| 59 | |
Calin Juravle | b1498f6 | 2015-02-16 13:13:29 +0000 | [diff] [blame] | 60 | void PrepareForRegisterAllocation::VisitBoundType(HBoundType* bound_type) { |
| 61 | bound_type->ReplaceWith(bound_type->InputAt(0)); |
| 62 | bound_type->GetBlock()->RemoveInstruction(bound_type); |
| 63 | } |
| 64 | |
Roland Levillain | b133ec6 | 2016-03-23 12:40:35 +0000 | [diff] [blame] | 65 | void PrepareForRegisterAllocation::VisitArraySet(HArraySet* instruction) { |
| 66 | HInstruction* value = instruction->GetValue(); |
| 67 | // PrepareForRegisterAllocation::VisitBoundType may have replaced a |
| 68 | // BoundType (as value input of this ArraySet) with a NullConstant. |
| 69 | // If so, this ArraySet no longer needs a type check. |
| 70 | if (value->IsNullConstant()) { |
| 71 | DCHECK_EQ(value->GetType(), Primitive::kPrimNot); |
| 72 | if (instruction->NeedsTypeCheck()) { |
| 73 | instruction->ClearNeedsTypeCheck(); |
| 74 | } |
| 75 | } |
| 76 | } |
| 77 | |
Nicolas Geoffray | 19a19cf | 2014-10-22 16:07:05 +0100 | [diff] [blame] | 78 | void PrepareForRegisterAllocation::VisitClinitCheck(HClinitCheck* check) { |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 79 | // Try to find a static invoke or a new-instance from which this check originated. |
| 80 | HInstruction* implicit_clinit = nullptr; |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 81 | for (const HUseListNode<HInstruction*>& use : check->GetUses()) { |
| 82 | HInstruction* user = use.GetUser(); |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 83 | if ((user->IsInvokeStaticOrDirect() || user->IsNewInstance()) && |
| 84 | CanMoveClinitCheck(check, user)) { |
| 85 | implicit_clinit = user; |
| 86 | if (user->IsInvokeStaticOrDirect()) { |
| 87 | DCHECK(user->AsInvokeStaticOrDirect()->IsStaticWithExplicitClinitCheck()); |
| 88 | user->AsInvokeStaticOrDirect()->RemoveExplicitClinitCheck( |
| 89 | HInvokeStaticOrDirect::ClinitCheckRequirement::kImplicit); |
| 90 | } else { |
| 91 | DCHECK(user->IsNewInstance()); |
| 92 | // We delegate the initialization duty to the allocation. |
| 93 | if (user->AsNewInstance()->GetEntrypoint() == kQuickAllocObjectInitialized) { |
| 94 | user->AsNewInstance()->SetEntrypoint(kQuickAllocObjectResolved); |
| 95 | } |
| 96 | } |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 97 | break; |
| 98 | } |
| 99 | } |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 100 | // If we found a static invoke or new-instance for merging, remove the check |
| 101 | // from dominated static invokes. |
| 102 | if (implicit_clinit != nullptr) { |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 103 | const HUseList<HInstruction*>& uses = check->GetUses(); |
| 104 | for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) { |
| 105 | HInstruction* user = it->GetUser(); |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 106 | // All other uses must be dominated. |
| 107 | DCHECK(implicit_clinit->StrictlyDominates(user) || (implicit_clinit == user)); |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 108 | ++it; // Advance before we remove the node, reference to the next node is preserved. |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 109 | if (user->IsInvokeStaticOrDirect()) { |
| 110 | user->AsInvokeStaticOrDirect()->RemoveExplicitClinitCheck( |
| 111 | HInvokeStaticOrDirect::ClinitCheckRequirement::kNone); |
| 112 | } |
| 113 | } |
| 114 | } |
| 115 | |
| 116 | HLoadClass* load_class = check->GetLoadClass(); |
| 117 | bool can_merge_with_load_class = CanMoveClinitCheck(load_class, check); |
| 118 | |
| 119 | check->ReplaceWith(load_class); |
| 120 | |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 121 | if (implicit_clinit != nullptr) { |
| 122 | // Remove the check from the graph. It has been merged into the invoke or new-instance. |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 123 | check->GetBlock()->RemoveInstruction(check); |
| 124 | // Check if we can merge the load class as well. |
| 125 | if (can_merge_with_load_class && !load_class->HasUses()) { |
| 126 | load_class->GetBlock()->RemoveInstruction(load_class); |
| 127 | } |
Nicolas Geoffray | 0580d96 | 2016-01-06 17:40:20 +0000 | [diff] [blame] | 128 | } else if (can_merge_with_load_class && !load_class->NeedsAccessCheck()) { |
Nicolas Geoffray | 424f676 | 2014-11-03 14:51:25 +0000 | [diff] [blame] | 129 | // Pass the initialization duty to the `HLoadClass` instruction, |
| 130 | // and remove the instruction from the graph. |
Mathieu Chartier | 1ceb37c | 2016-08-30 10:23:01 -0700 | [diff] [blame] | 131 | DCHECK(load_class->HasEnvironment()); |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 132 | load_class->SetMustGenerateClinitCheck(true); |
Nicolas Geoffray | 424f676 | 2014-11-03 14:51:25 +0000 | [diff] [blame] | 133 | check->GetBlock()->RemoveInstruction(check); |
| 134 | } |
Nicolas Geoffray | 19a19cf | 2014-10-22 16:07:05 +0100 | [diff] [blame] | 135 | } |
| 136 | |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 137 | void PrepareForRegisterAllocation::VisitNewInstance(HNewInstance* instruction) { |
| 138 | HLoadClass* load_class = instruction->InputAt(0)->AsLoadClass(); |
Mathieu Chartier | 1ceb37c | 2016-08-30 10:23:01 -0700 | [diff] [blame] | 139 | const bool has_only_one_use = load_class->HasOnlyOneNonEnvironmentUse(); |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 140 | // Change the entrypoint to kQuickAllocObject if either: |
| 141 | // - the class is finalizable (only kQuickAllocObject handles finalizable classes), |
| 142 | // - the class needs access checks (we do not know if it's finalizable), |
| 143 | // - or the load class has only one use. |
| 144 | if (instruction->IsFinalizable() || has_only_one_use || load_class->NeedsAccessCheck()) { |
| 145 | instruction->SetEntrypoint(kQuickAllocObject); |
Andreas Gampe | a5b09a6 | 2016-11-17 15:21:22 -0800 | [diff] [blame] | 146 | instruction->ReplaceInput(GetGraph()->GetIntConstant(load_class->GetTypeIndex().index_), 0); |
Mathieu Chartier | 1ceb37c | 2016-08-30 10:23:01 -0700 | [diff] [blame] | 147 | if (has_only_one_use) { |
| 148 | // We've just removed the only use of the HLoadClass. Since we don't run DCE after this pass, |
| 149 | // do it manually if possible. |
| 150 | if (!load_class->CanThrow()) { |
| 151 | // If the load class can not throw, it has no side effects and can be removed if there is |
| 152 | // only one use. |
| 153 | load_class->GetBlock()->RemoveInstruction(load_class); |
| 154 | } else if (!instruction->GetEnvironment()->IsFromInlinedInvoke() && |
| 155 | CanMoveClinitCheck(load_class, instruction)) { |
| 156 | // The allocation entry point that deals with access checks does not work with inlined |
| 157 | // methods, so we need to check whether this allocation comes from an inlined method. |
| 158 | // We also need to make the same check as for moving clinit check, whether the HLoadClass |
| 159 | // has the clinit check responsibility or not (HLoadClass can throw anyway). |
| 160 | // If it needed access checks, we delegate the access check to the allocation. |
| 161 | if (load_class->NeedsAccessCheck()) { |
| 162 | instruction->SetEntrypoint(kQuickAllocObjectWithAccessCheck); |
| 163 | } |
| 164 | load_class->GetBlock()->RemoveInstruction(load_class); |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 165 | } |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 166 | } |
| 167 | } |
| 168 | } |
| 169 | |
David Brazdil | b3e773e | 2016-01-26 11:28:37 +0000 | [diff] [blame] | 170 | bool PrepareForRegisterAllocation::CanEmitConditionAt(HCondition* condition, |
| 171 | HInstruction* user) const { |
| 172 | if (condition->GetNext() != user) { |
| 173 | return false; |
Nicolas Geoffray | 360231a | 2014-10-08 21:07:48 +0100 | [diff] [blame] | 174 | } |
David Brazdil | b3e773e | 2016-01-26 11:28:37 +0000 | [diff] [blame] | 175 | |
| 176 | if (user->IsIf() || user->IsDeoptimize()) { |
| 177 | return true; |
| 178 | } |
| 179 | |
David Brazdil | 74eb1b2 | 2015-12-14 11:44:01 +0000 | [diff] [blame] | 180 | if (user->IsSelect() && user->AsSelect()->GetCondition() == condition) { |
Mark Mendell | 0c5b18e | 2016-02-06 13:58:35 -0500 | [diff] [blame] | 181 | return true; |
David Brazdil | 74eb1b2 | 2015-12-14 11:44:01 +0000 | [diff] [blame] | 182 | } |
| 183 | |
David Brazdil | b3e773e | 2016-01-26 11:28:37 +0000 | [diff] [blame] | 184 | return false; |
| 185 | } |
| 186 | |
| 187 | void PrepareForRegisterAllocation::VisitCondition(HCondition* condition) { |
| 188 | if (condition->HasOnlyOneNonEnvironmentUse()) { |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 189 | HInstruction* user = condition->GetUses().front().GetUser(); |
David Brazdil | b3e773e | 2016-01-26 11:28:37 +0000 | [diff] [blame] | 190 | if (CanEmitConditionAt(condition, user)) { |
| 191 | condition->MarkEmittedAtUseSite(); |
| 192 | } |
Nicolas Geoffray | 360231a | 2014-10-08 21:07:48 +0100 | [diff] [blame] | 193 | } |
| 194 | } |
| 195 | |
Roland Levillain | 4c0eb42 | 2015-04-24 16:43:49 +0100 | [diff] [blame] | 196 | void PrepareForRegisterAllocation::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { |
| 197 | if (invoke->IsStaticWithExplicitClinitCheck()) { |
Vladimir Marko | 372f10e | 2016-05-17 16:30:10 +0100 | [diff] [blame] | 198 | HLoadClass* last_input = invoke->GetInputs().back()->AsLoadClass(); |
Calin Juravle | 0ba218d | 2015-05-19 18:46:01 +0100 | [diff] [blame] | 199 | DCHECK(last_input != nullptr) |
| 200 | << "Last input is not HLoadClass. It is " << last_input->DebugName(); |
| 201 | |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 202 | // Detach the explicit class initialization check from the invoke. |
| 203 | // Keeping track of the initializing instruction is no longer required |
| 204 | // at this stage (i.e., after inlining has been performed). |
| 205 | invoke->RemoveExplicitClinitCheck(HInvokeStaticOrDirect::ClinitCheckRequirement::kNone); |
Roland Levillain | 4c0eb42 | 2015-04-24 16:43:49 +0100 | [diff] [blame] | 206 | |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 207 | // Merging with load class should have happened in VisitClinitCheck(). |
| 208 | DCHECK(!CanMoveClinitCheck(last_input, invoke)); |
| 209 | } |
| 210 | } |
Nicolas Geoffray | 78f4fa7 | 2015-06-12 09:35:05 +0100 | [diff] [blame] | 211 | |
David Brazdil | b3e773e | 2016-01-26 11:28:37 +0000 | [diff] [blame] | 212 | bool PrepareForRegisterAllocation::CanMoveClinitCheck(HInstruction* input, |
| 213 | HInstruction* user) const { |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 214 | // Determine if input and user come from the same dex instruction, so that we can move |
| 215 | // the clinit check responsibility from one to the other, i.e. from HClinitCheck (user) |
Vladimir Marko | c7591b4 | 2016-06-29 14:59:07 +0100 | [diff] [blame] | 216 | // to HLoadClass (input), or from HClinitCheck (input) to HInvokeStaticOrDirect (user), |
| 217 | // or from HLoadClass (input) to HNewInstance (user). |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 218 | |
| 219 | // Start with a quick dex pc check. |
| 220 | if (user->GetDexPc() != input->GetDexPc()) { |
| 221 | return false; |
| 222 | } |
| 223 | |
| 224 | // Now do a thorough environment check that this is really coming from the same instruction in |
| 225 | // the same inlined graph. Unfortunately, we have to go through the whole environment chain. |
| 226 | HEnvironment* user_environment = user->GetEnvironment(); |
| 227 | HEnvironment* input_environment = input->GetEnvironment(); |
| 228 | while (user_environment != nullptr || input_environment != nullptr) { |
| 229 | if (user_environment == nullptr || input_environment == nullptr) { |
| 230 | // Different environment chain length. This happens when a method is called |
| 231 | // once directly and once indirectly through another inlined method. |
| 232 | return false; |
| 233 | } |
| 234 | if (user_environment->GetDexPc() != input_environment->GetDexPc() || |
| 235 | user_environment->GetMethodIdx() != input_environment->GetMethodIdx() || |
| 236 | !IsSameDexFile(user_environment->GetDexFile(), input_environment->GetDexFile())) { |
| 237 | return false; |
| 238 | } |
| 239 | user_environment = user_environment->GetParent(); |
| 240 | input_environment = input_environment->GetParent(); |
| 241 | } |
| 242 | |
| 243 | // Check for code motion taking the input to a different block. |
| 244 | if (user->GetBlock() != input->GetBlock()) { |
| 245 | return false; |
| 246 | } |
| 247 | |
| 248 | // In debug mode, check that we have not inserted a throwing instruction |
| 249 | // or an instruction with side effects between input and user. |
| 250 | if (kIsDebugBuild) { |
| 251 | for (HInstruction* between = input->GetNext(); between != user; between = between->GetNext()) { |
| 252 | CHECK(between != nullptr); // User must be after input in the same block. |
| 253 | CHECK(!between->CanThrow()); |
| 254 | CHECK(!between->HasSideEffects()); |
Roland Levillain | 4c0eb42 | 2015-04-24 16:43:49 +0100 | [diff] [blame] | 255 | } |
| 256 | } |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 257 | return true; |
Roland Levillain | 4c0eb42 | 2015-04-24 16:43:49 +0100 | [diff] [blame] | 258 | } |
| 259 | |
Nicolas Geoffray | 26a25ef | 2014-09-30 13:54:09 +0100 | [diff] [blame] | 260 | } // namespace art |