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 | |
Andreas Gampe | e2abbc6 | 2017-09-15 11:59:26 -0700 | [diff] [blame] | 19 | #include "dex_file_types.h" |
Nicolas Geoffray | 5d37c15 | 2017-01-12 13:25:19 +0000 | [diff] [blame] | 20 | #include "jni_internal.h" |
Igor Murashkin | 6ef4567 | 2017-08-08 13:59:55 -0700 | [diff] [blame] | 21 | #include "optimizing_compiler_stats.h" |
Nicolas Geoffray | 5d37c15 | 2017-01-12 13:25:19 +0000 | [diff] [blame] | 22 | #include "well_known_classes.h" |
| 23 | |
Nicolas Geoffray | 26a25ef | 2014-09-30 13:54:09 +0100 | [diff] [blame] | 24 | namespace art { |
| 25 | |
| 26 | void PrepareForRegisterAllocation::Run() { |
| 27 | // Order does not matter. |
Vladimir Marko | 2c45bc9 | 2016-10-25 16:54:12 +0100 | [diff] [blame] | 28 | for (HBasicBlock* block : GetGraph()->GetReversePostOrder()) { |
Nicolas Geoffray | 26a25ef | 2014-09-30 13:54:09 +0100 | [diff] [blame] | 29 | // No need to visit the phis. |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 30 | for (HInstructionIterator inst_it(block->GetInstructions()); !inst_it.Done(); |
| 31 | inst_it.Advance()) { |
| 32 | inst_it.Current()->Accept(this); |
Nicolas Geoffray | 26a25ef | 2014-09-30 13:54:09 +0100 | [diff] [blame] | 33 | } |
| 34 | } |
| 35 | } |
| 36 | |
| 37 | void PrepareForRegisterAllocation::VisitNullCheck(HNullCheck* check) { |
| 38 | check->ReplaceWith(check->InputAt(0)); |
| 39 | } |
| 40 | |
Calin Juravle | d0d4852 | 2014-11-04 16:40:20 +0000 | [diff] [blame] | 41 | void PrepareForRegisterAllocation::VisitDivZeroCheck(HDivZeroCheck* check) { |
| 42 | check->ReplaceWith(check->InputAt(0)); |
| 43 | } |
| 44 | |
Nicolas Geoffray | 6f8e2c9 | 2017-03-23 14:37:26 +0000 | [diff] [blame] | 45 | void PrepareForRegisterAllocation::VisitDeoptimize(HDeoptimize* deoptimize) { |
| 46 | if (deoptimize->GuardsAnInput()) { |
| 47 | // Replace the uses with the actual guarded instruction. |
| 48 | deoptimize->ReplaceWith(deoptimize->GuardedInput()); |
| 49 | deoptimize->RemoveGuard(); |
| 50 | } |
| 51 | } |
| 52 | |
Nicolas Geoffray | 26a25ef | 2014-09-30 13:54:09 +0100 | [diff] [blame] | 53 | void PrepareForRegisterAllocation::VisitBoundsCheck(HBoundsCheck* check) { |
| 54 | check->ReplaceWith(check->InputAt(0)); |
Vladimir Marko | 87f3fcb | 2016-04-28 15:52:11 +0100 | [diff] [blame] | 55 | if (check->IsStringCharAt()) { |
| 56 | // Add a fake environment for String.charAt() inline info as we want |
| 57 | // the exception to appear as being thrown from there. |
Nicolas Geoffray | 5d37c15 | 2017-01-12 13:25:19 +0000 | [diff] [blame] | 58 | ArtMethod* char_at_method = jni::DecodeArtMethod(WellKnownClasses::java_lang_String_charAt); |
Vladimir Marko | 87f3fcb | 2016-04-28 15:52:11 +0100 | [diff] [blame] | 59 | ArenaAllocator* arena = GetGraph()->GetArena(); |
| 60 | HEnvironment* environment = new (arena) HEnvironment(arena, |
| 61 | /* number_of_vregs */ 0u, |
Nicolas Geoffray | 5d37c15 | 2017-01-12 13:25:19 +0000 | [diff] [blame] | 62 | char_at_method, |
Andreas Gampe | e2abbc6 | 2017-09-15 11:59:26 -0700 | [diff] [blame] | 63 | /* dex_pc */ dex::kDexNoIndex, |
Vladimir Marko | 87f3fcb | 2016-04-28 15:52:11 +0100 | [diff] [blame] | 64 | check); |
| 65 | check->InsertRawEnvironment(environment); |
| 66 | } |
Nicolas Geoffray | 26a25ef | 2014-09-30 13:54:09 +0100 | [diff] [blame] | 67 | } |
| 68 | |
Calin Juravle | b1498f6 | 2015-02-16 13:13:29 +0000 | [diff] [blame] | 69 | void PrepareForRegisterAllocation::VisitBoundType(HBoundType* bound_type) { |
| 70 | bound_type->ReplaceWith(bound_type->InputAt(0)); |
| 71 | bound_type->GetBlock()->RemoveInstruction(bound_type); |
| 72 | } |
| 73 | |
Roland Levillain | b133ec6 | 2016-03-23 12:40:35 +0000 | [diff] [blame] | 74 | void PrepareForRegisterAllocation::VisitArraySet(HArraySet* instruction) { |
| 75 | HInstruction* value = instruction->GetValue(); |
| 76 | // PrepareForRegisterAllocation::VisitBoundType may have replaced a |
| 77 | // BoundType (as value input of this ArraySet) with a NullConstant. |
| 78 | // If so, this ArraySet no longer needs a type check. |
| 79 | if (value->IsNullConstant()) { |
Vladimir Marko | 0ebe0d8 | 2017-09-21 22:50:39 +0100 | [diff] [blame] | 80 | DCHECK_EQ(value->GetType(), DataType::Type::kReference); |
Roland Levillain | b133ec6 | 2016-03-23 12:40:35 +0000 | [diff] [blame] | 81 | if (instruction->NeedsTypeCheck()) { |
| 82 | instruction->ClearNeedsTypeCheck(); |
| 83 | } |
| 84 | } |
| 85 | } |
| 86 | |
Nicolas Geoffray | 19a19cf | 2014-10-22 16:07:05 +0100 | [diff] [blame] | 87 | void PrepareForRegisterAllocation::VisitClinitCheck(HClinitCheck* check) { |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 88 | // Try to find a static invoke or a new-instance from which this check originated. |
| 89 | HInstruction* implicit_clinit = nullptr; |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 90 | for (const HUseListNode<HInstruction*>& use : check->GetUses()) { |
| 91 | HInstruction* user = use.GetUser(); |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 92 | if ((user->IsInvokeStaticOrDirect() || user->IsNewInstance()) && |
| 93 | CanMoveClinitCheck(check, user)) { |
| 94 | implicit_clinit = user; |
| 95 | if (user->IsInvokeStaticOrDirect()) { |
| 96 | DCHECK(user->AsInvokeStaticOrDirect()->IsStaticWithExplicitClinitCheck()); |
| 97 | user->AsInvokeStaticOrDirect()->RemoveExplicitClinitCheck( |
| 98 | HInvokeStaticOrDirect::ClinitCheckRequirement::kImplicit); |
| 99 | } else { |
| 100 | DCHECK(user->IsNewInstance()); |
| 101 | // We delegate the initialization duty to the allocation. |
| 102 | if (user->AsNewInstance()->GetEntrypoint() == kQuickAllocObjectInitialized) { |
| 103 | user->AsNewInstance()->SetEntrypoint(kQuickAllocObjectResolved); |
| 104 | } |
| 105 | } |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 106 | break; |
| 107 | } |
| 108 | } |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 109 | // If we found a static invoke or new-instance for merging, remove the check |
| 110 | // from dominated static invokes. |
| 111 | if (implicit_clinit != nullptr) { |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 112 | const HUseList<HInstruction*>& uses = check->GetUses(); |
| 113 | for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) { |
| 114 | HInstruction* user = it->GetUser(); |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 115 | // All other uses must be dominated. |
| 116 | DCHECK(implicit_clinit->StrictlyDominates(user) || (implicit_clinit == user)); |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 117 | ++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] | 118 | if (user->IsInvokeStaticOrDirect()) { |
| 119 | user->AsInvokeStaticOrDirect()->RemoveExplicitClinitCheck( |
| 120 | HInvokeStaticOrDirect::ClinitCheckRequirement::kNone); |
| 121 | } |
| 122 | } |
| 123 | } |
| 124 | |
| 125 | HLoadClass* load_class = check->GetLoadClass(); |
| 126 | bool can_merge_with_load_class = CanMoveClinitCheck(load_class, check); |
| 127 | |
| 128 | check->ReplaceWith(load_class); |
| 129 | |
Nicolas Geoffray | 729645a | 2015-11-19 13:29:02 +0000 | [diff] [blame] | 130 | if (implicit_clinit != nullptr) { |
| 131 | // 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] | 132 | check->GetBlock()->RemoveInstruction(check); |
| 133 | // Check if we can merge the load class as well. |
| 134 | if (can_merge_with_load_class && !load_class->HasUses()) { |
| 135 | load_class->GetBlock()->RemoveInstruction(load_class); |
| 136 | } |
Nicolas Geoffray | 0580d96 | 2016-01-06 17:40:20 +0000 | [diff] [blame] | 137 | } else if (can_merge_with_load_class && !load_class->NeedsAccessCheck()) { |
Nicolas Geoffray | 424f676 | 2014-11-03 14:51:25 +0000 | [diff] [blame] | 138 | // Pass the initialization duty to the `HLoadClass` instruction, |
| 139 | // and remove the instruction from the graph. |
Mathieu Chartier | 1ceb37c | 2016-08-30 10:23:01 -0700 | [diff] [blame] | 140 | DCHECK(load_class->HasEnvironment()); |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 141 | load_class->SetMustGenerateClinitCheck(true); |
Nicolas Geoffray | 424f676 | 2014-11-03 14:51:25 +0000 | [diff] [blame] | 142 | check->GetBlock()->RemoveInstruction(check); |
| 143 | } |
Nicolas Geoffray | 19a19cf | 2014-10-22 16:07:05 +0100 | [diff] [blame] | 144 | } |
| 145 | |
David Brazdil | b3e773e | 2016-01-26 11:28:37 +0000 | [diff] [blame] | 146 | bool PrepareForRegisterAllocation::CanEmitConditionAt(HCondition* condition, |
| 147 | HInstruction* user) const { |
| 148 | if (condition->GetNext() != user) { |
| 149 | return false; |
Nicolas Geoffray | 360231a | 2014-10-08 21:07:48 +0100 | [diff] [blame] | 150 | } |
David Brazdil | b3e773e | 2016-01-26 11:28:37 +0000 | [diff] [blame] | 151 | |
| 152 | if (user->IsIf() || user->IsDeoptimize()) { |
| 153 | return true; |
| 154 | } |
| 155 | |
David Brazdil | 74eb1b2 | 2015-12-14 11:44:01 +0000 | [diff] [blame] | 156 | if (user->IsSelect() && user->AsSelect()->GetCondition() == condition) { |
Mark Mendell | 0c5b18e | 2016-02-06 13:58:35 -0500 | [diff] [blame] | 157 | return true; |
David Brazdil | 74eb1b2 | 2015-12-14 11:44:01 +0000 | [diff] [blame] | 158 | } |
| 159 | |
David Brazdil | b3e773e | 2016-01-26 11:28:37 +0000 | [diff] [blame] | 160 | return false; |
| 161 | } |
| 162 | |
| 163 | void PrepareForRegisterAllocation::VisitCondition(HCondition* condition) { |
| 164 | if (condition->HasOnlyOneNonEnvironmentUse()) { |
Vladimir Marko | 46817b8 | 2016-03-29 12:21:58 +0100 | [diff] [blame] | 165 | HInstruction* user = condition->GetUses().front().GetUser(); |
David Brazdil | b3e773e | 2016-01-26 11:28:37 +0000 | [diff] [blame] | 166 | if (CanEmitConditionAt(condition, user)) { |
| 167 | condition->MarkEmittedAtUseSite(); |
| 168 | } |
Nicolas Geoffray | 360231a | 2014-10-08 21:07:48 +0100 | [diff] [blame] | 169 | } |
| 170 | } |
| 171 | |
Igor Murashkin | d01745e | 2017-04-05 16:40:31 -0700 | [diff] [blame] | 172 | void PrepareForRegisterAllocation::VisitConstructorFence(HConstructorFence* constructor_fence) { |
Igor Murashkin | 79d8fa7 | 2017-04-18 09:37:23 -0700 | [diff] [blame] | 173 | // Trivially remove redundant HConstructorFence when it immediately follows an HNewInstance |
| 174 | // to an uninitialized class. In this special case, the art_quick_alloc_object_resolved |
| 175 | // will already have the 'dmb' which is strictly stronger than an HConstructorFence. |
| 176 | // |
| 177 | // The instruction builder always emits "x = HNewInstance; HConstructorFence(x)" so this |
| 178 | // is effectively pattern-matching that particular case and undoing the redundancy the builder |
| 179 | // had introduced. |
| 180 | // |
| 181 | // TODO: Move this to a separate pass. |
| 182 | HInstruction* allocation_inst = constructor_fence->GetAssociatedAllocation(); |
| 183 | if (allocation_inst != nullptr && allocation_inst->IsNewInstance()) { |
| 184 | HNewInstance* new_inst = allocation_inst->AsNewInstance(); |
| 185 | // This relies on the entrypoint already being set to the more optimized version; |
| 186 | // as that happens in this pass, this redundancy removal also cannot happen any earlier. |
| 187 | if (new_inst != nullptr && new_inst->GetEntrypoint() == kQuickAllocObjectResolved) { |
| 188 | // If this was done in an earlier pass, we would want to match that `previous` was an input |
| 189 | // to the `constructor_fence`. However, since this pass removes the inputs to the fence, |
| 190 | // we can ignore the inputs and just remove the instruction from its block. |
| 191 | DCHECK_EQ(1u, constructor_fence->InputCount()); |
| 192 | // TODO: GetAssociatedAllocation should not care about multiple inputs |
| 193 | // if we are in prepare_for_register_allocation pass only. |
| 194 | constructor_fence->GetBlock()->RemoveInstruction(constructor_fence); |
Igor Murashkin | 6ef4567 | 2017-08-08 13:59:55 -0700 | [diff] [blame] | 195 | MaybeRecordStat(stats_, |
| 196 | MethodCompilationStat::kConstructorFenceRemovedPFRA); |
Igor Murashkin | 79d8fa7 | 2017-04-18 09:37:23 -0700 | [diff] [blame] | 197 | return; |
Igor Murashkin | 79d8fa7 | 2017-04-18 09:37:23 -0700 | [diff] [blame] | 198 | } |
| 199 | |
| 200 | // HNewArray does not need this check because the art_quick_alloc_array does not itself |
| 201 | // have a dmb in any normal situation (i.e. the array class is never exactly in the |
| 202 | // "resolved" state). If the array class is not yet loaded, it will always go from |
| 203 | // Unloaded->Initialized state. |
| 204 | } |
| 205 | |
| 206 | // Remove all the inputs to the constructor fence; |
Igor Murashkin | d01745e | 2017-04-05 16:40:31 -0700 | [diff] [blame] | 207 | // they aren't used by the InstructionCodeGenerator and this lets us avoid creating a |
| 208 | // LocationSummary in the LocationsBuilder. |
| 209 | constructor_fence->RemoveAllInputs(); |
| 210 | } |
| 211 | |
Roland Levillain | 4c0eb42 | 2015-04-24 16:43:49 +0100 | [diff] [blame] | 212 | void PrepareForRegisterAllocation::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { |
| 213 | if (invoke->IsStaticWithExplicitClinitCheck()) { |
Nicolas Geoffray | e829831 | 2017-08-03 09:51:25 +0100 | [diff] [blame] | 214 | HInstruction* last_input = invoke->GetInputs().back(); |
| 215 | DCHECK(last_input->IsLoadClass()) |
Calin Juravle | 0ba218d | 2015-05-19 18:46:01 +0100 | [diff] [blame] | 216 | << "Last input is not HLoadClass. It is " << last_input->DebugName(); |
| 217 | |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 218 | // Detach the explicit class initialization check from the invoke. |
| 219 | // Keeping track of the initializing instruction is no longer required |
| 220 | // at this stage (i.e., after inlining has been performed). |
| 221 | invoke->RemoveExplicitClinitCheck(HInvokeStaticOrDirect::ClinitCheckRequirement::kNone); |
Roland Levillain | 4c0eb42 | 2015-04-24 16:43:49 +0100 | [diff] [blame] | 222 | |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 223 | // Merging with load class should have happened in VisitClinitCheck(). |
| 224 | DCHECK(!CanMoveClinitCheck(last_input, invoke)); |
| 225 | } |
| 226 | } |
Nicolas Geoffray | 78f4fa7 | 2015-06-12 09:35:05 +0100 | [diff] [blame] | 227 | |
David Brazdil | b3e773e | 2016-01-26 11:28:37 +0000 | [diff] [blame] | 228 | bool PrepareForRegisterAllocation::CanMoveClinitCheck(HInstruction* input, |
| 229 | HInstruction* user) const { |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 230 | // Determine if input and user come from the same dex instruction, so that we can move |
| 231 | // 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] | 232 | // to HLoadClass (input), or from HClinitCheck (input) to HInvokeStaticOrDirect (user), |
| 233 | // or from HLoadClass (input) to HNewInstance (user). |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 234 | |
| 235 | // Start with a quick dex pc check. |
| 236 | if (user->GetDexPc() != input->GetDexPc()) { |
| 237 | return false; |
| 238 | } |
| 239 | |
| 240 | // Now do a thorough environment check that this is really coming from the same instruction in |
| 241 | // the same inlined graph. Unfortunately, we have to go through the whole environment chain. |
| 242 | HEnvironment* user_environment = user->GetEnvironment(); |
| 243 | HEnvironment* input_environment = input->GetEnvironment(); |
| 244 | while (user_environment != nullptr || input_environment != nullptr) { |
| 245 | if (user_environment == nullptr || input_environment == nullptr) { |
| 246 | // Different environment chain length. This happens when a method is called |
| 247 | // once directly and once indirectly through another inlined method. |
| 248 | return false; |
| 249 | } |
| 250 | if (user_environment->GetDexPc() != input_environment->GetDexPc() || |
Nicolas Geoffray | 5d37c15 | 2017-01-12 13:25:19 +0000 | [diff] [blame] | 251 | user_environment->GetMethod() != input_environment->GetMethod()) { |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 252 | return false; |
| 253 | } |
| 254 | user_environment = user_environment->GetParent(); |
| 255 | input_environment = input_environment->GetParent(); |
| 256 | } |
| 257 | |
| 258 | // Check for code motion taking the input to a different block. |
| 259 | if (user->GetBlock() != input->GetBlock()) { |
| 260 | return false; |
| 261 | } |
| 262 | |
| 263 | // In debug mode, check that we have not inserted a throwing instruction |
| 264 | // or an instruction with side effects between input and user. |
| 265 | if (kIsDebugBuild) { |
| 266 | for (HInstruction* between = input->GetNext(); between != user; between = between->GetNext()) { |
| 267 | CHECK(between != nullptr); // User must be after input in the same block. |
| 268 | CHECK(!between->CanThrow()); |
| 269 | CHECK(!between->HasSideEffects()); |
Roland Levillain | 4c0eb42 | 2015-04-24 16:43:49 +0100 | [diff] [blame] | 270 | } |
| 271 | } |
Vladimir Marko | fbb184a | 2015-11-13 14:47:00 +0000 | [diff] [blame] | 272 | return true; |
Roland Levillain | 4c0eb42 | 2015-04-24 16:43:49 +0100 | [diff] [blame] | 273 | } |
| 274 | |
Nicolas Geoffray | 26a25ef | 2014-09-30 13:54:09 +0100 | [diff] [blame] | 275 | } // namespace art |