1 /* 2 * Copyright (C) 2015 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 "reference_type_propagation.h" 18 19 #include "art_field-inl.h" 20 #include "art_method-inl.h" 21 #include "base/scoped_arena_allocator.h" 22 #include "base/scoped_arena_containers.h" 23 #include "base/enums.h" 24 #include "class_linker-inl.h" 25 #include "handle_scope-inl.h" 26 #include "mirror/class-inl.h" 27 #include "mirror/dex_cache.h" 28 #include "scoped_thread_state_change-inl.h" 29 30 namespace art { 31 32 static inline ObjPtr<mirror::DexCache> FindDexCacheWithHint( 33 Thread* self, const DexFile& dex_file, Handle<mirror::DexCache> hint_dex_cache) 34 REQUIRES_SHARED(Locks::mutator_lock_) { 35 if (LIKELY(hint_dex_cache->GetDexFile() == &dex_file)) { 36 return hint_dex_cache.Get(); 37 } else { 38 return Runtime::Current()->GetClassLinker()->FindDexCache(self, dex_file); 39 } 40 } 41 42 static inline ReferenceTypeInfo::TypeHandle GetRootHandle(VariableSizedHandleScope* handles, 43 ClassLinker::ClassRoot class_root, 44 ReferenceTypeInfo::TypeHandle* cache) { 45 if (!ReferenceTypeInfo::IsValidHandle(*cache)) { 46 // Mutator lock is required for NewHandle. 47 ClassLinker* linker = Runtime::Current()->GetClassLinker(); 48 ScopedObjectAccess soa(Thread::Current()); 49 *cache = handles->NewHandle(linker->GetClassRoot(class_root)); 50 } 51 return *cache; 52 } 53 54 ReferenceTypeInfo::TypeHandle ReferenceTypePropagation::HandleCache::GetObjectClassHandle() { 55 return GetRootHandle(handles_, ClassLinker::kJavaLangObject, &object_class_handle_); 56 } 57 58 ReferenceTypeInfo::TypeHandle ReferenceTypePropagation::HandleCache::GetClassClassHandle() { 59 return GetRootHandle(handles_, ClassLinker::kJavaLangClass, &class_class_handle_); 60 } 61 62 ReferenceTypeInfo::TypeHandle ReferenceTypePropagation::HandleCache::GetStringClassHandle() { 63 return GetRootHandle(handles_, ClassLinker::kJavaLangString, &string_class_handle_); 64 } 65 66 ReferenceTypeInfo::TypeHandle ReferenceTypePropagation::HandleCache::GetThrowableClassHandle() { 67 return GetRootHandle(handles_, ClassLinker::kJavaLangThrowable, &throwable_class_handle_); 68 } 69 70 class ReferenceTypePropagation::RTPVisitor : public HGraphDelegateVisitor { 71 public: 72 RTPVisitor(HGraph* graph, 73 Handle<mirror::ClassLoader> class_loader, 74 Handle<mirror::DexCache> hint_dex_cache, 75 HandleCache* handle_cache, 76 bool is_first_run) 77 : HGraphDelegateVisitor(graph), 78 class_loader_(class_loader), 79 hint_dex_cache_(hint_dex_cache), 80 handle_cache_(handle_cache), 81 allocator_(graph->GetArenaStack()), 82 worklist_(allocator_.Adapter(kArenaAllocReferenceTypePropagation)), 83 is_first_run_(is_first_run) { 84 worklist_.reserve(kDefaultWorklistSize); 85 } 86 87 void VisitDeoptimize(HDeoptimize* deopt) OVERRIDE; 88 void VisitNewInstance(HNewInstance* new_instance) OVERRIDE; 89 void VisitLoadClass(HLoadClass* load_class) OVERRIDE; 90 void VisitClinitCheck(HClinitCheck* clinit_check) OVERRIDE; 91 void VisitLoadString(HLoadString* instr) OVERRIDE; 92 void VisitLoadException(HLoadException* instr) OVERRIDE; 93 void VisitNewArray(HNewArray* instr) OVERRIDE; 94 void VisitParameterValue(HParameterValue* instr) OVERRIDE; 95 void VisitInstanceFieldGet(HInstanceFieldGet* instr) OVERRIDE; 96 void VisitStaticFieldGet(HStaticFieldGet* instr) OVERRIDE; 97 void VisitUnresolvedInstanceFieldGet(HUnresolvedInstanceFieldGet* instr) OVERRIDE; 98 void VisitUnresolvedStaticFieldGet(HUnresolvedStaticFieldGet* instr) OVERRIDE; 99 void VisitInvoke(HInvoke* instr) OVERRIDE; 100 void VisitArrayGet(HArrayGet* instr) OVERRIDE; 101 void VisitCheckCast(HCheckCast* instr) OVERRIDE; 102 void VisitBoundType(HBoundType* instr) OVERRIDE; 103 void VisitNullCheck(HNullCheck* instr) OVERRIDE; 104 void VisitPhi(HPhi* phi); 105 106 void VisitBasicBlock(HBasicBlock* block); 107 void ProcessWorklist(); 108 109 private: 110 void UpdateFieldAccessTypeInfo(HInstruction* instr, const FieldInfo& info); 111 void SetClassAsTypeInfo(HInstruction* instr, ObjPtr<mirror::Class> klass, bool is_exact) 112 REQUIRES_SHARED(Locks::mutator_lock_); 113 void BoundTypeForIfNotNull(HBasicBlock* block); 114 static void BoundTypeForIfInstanceOf(HBasicBlock* block); 115 static bool UpdateNullability(HInstruction* instr); 116 static void UpdateBoundType(HBoundType* bound_type) REQUIRES_SHARED(Locks::mutator_lock_); 117 void UpdateArrayGet(HArrayGet* instr) REQUIRES_SHARED(Locks::mutator_lock_); 118 void UpdatePhi(HPhi* phi) REQUIRES_SHARED(Locks::mutator_lock_); 119 bool UpdateReferenceTypeInfo(HInstruction* instr); 120 void UpdateReferenceTypeInfo(HInstruction* instr, 121 dex::TypeIndex type_idx, 122 const DexFile& dex_file, 123 bool is_exact); 124 125 void AddToWorklist(HInstruction* instruction); 126 void AddDependentInstructionsToWorklist(HInstruction* instruction); 127 128 static constexpr size_t kDefaultWorklistSize = 8; 129 130 Handle<mirror::ClassLoader> class_loader_; 131 Handle<mirror::DexCache> hint_dex_cache_; 132 HandleCache* const handle_cache_; 133 134 // Use local allocator for allocating memory. 135 ScopedArenaAllocator allocator_; 136 ScopedArenaVector<HInstruction*> worklist_; 137 const bool is_first_run_; 138 }; 139 140 ReferenceTypePropagation::ReferenceTypePropagation(HGraph* graph, 141 Handle<mirror::ClassLoader> class_loader, 142 Handle<mirror::DexCache> hint_dex_cache, 143 VariableSizedHandleScope* handles, 144 bool is_first_run, 145 const char* name) 146 : HOptimization(graph, name), 147 class_loader_(class_loader), 148 hint_dex_cache_(hint_dex_cache), 149 handle_cache_(handles), 150 is_first_run_(is_first_run) { 151 } 152 153 void ReferenceTypePropagation::ValidateTypes() { 154 // TODO: move this to the graph checker. 155 if (kIsDebugBuild) { 156 ScopedObjectAccess soa(Thread::Current()); 157 for (HBasicBlock* block : graph_->GetReversePostOrder()) { 158 for (HInstructionIterator iti(block->GetInstructions()); !iti.Done(); iti.Advance()) { 159 HInstruction* instr = iti.Current(); 160 if (instr->GetType() == DataType::Type::kReference) { 161 DCHECK(instr->GetReferenceTypeInfo().IsValid()) 162 << "Invalid RTI for instruction: " << instr->DebugName(); 163 if (instr->IsBoundType()) { 164 DCHECK(instr->AsBoundType()->GetUpperBound().IsValid()); 165 } else if (instr->IsLoadClass()) { 166 HLoadClass* cls = instr->AsLoadClass(); 167 DCHECK(cls->GetReferenceTypeInfo().IsExact()); 168 DCHECK(!cls->GetLoadedClassRTI().IsValid() || cls->GetLoadedClassRTI().IsExact()); 169 } else if (instr->IsNullCheck()) { 170 DCHECK(instr->GetReferenceTypeInfo().IsEqual(instr->InputAt(0)->GetReferenceTypeInfo())) 171 << "NullCheck " << instr->GetReferenceTypeInfo() 172 << "Input(0) " << instr->InputAt(0)->GetReferenceTypeInfo(); 173 } 174 } 175 } 176 } 177 } 178 } 179 180 void ReferenceTypePropagation::Visit(HInstruction* instruction) { 181 RTPVisitor visitor(graph_, 182 class_loader_, 183 hint_dex_cache_, 184 &handle_cache_, 185 is_first_run_); 186 instruction->Accept(&visitor); 187 } 188 189 // Check if we should create a bound type for the given object at the specified 190 // position. Because of inlining and the fact we run RTP more than once and we 191 // might have a HBoundType already. If we do, we should not create a new one. 192 // In this case we also assert that there are no other uses of the object (except 193 // the bound type) dominated by the specified dominator_instr or dominator_block. 194 static bool ShouldCreateBoundType(HInstruction* position, 195 HInstruction* obj, 196 ReferenceTypeInfo upper_bound, 197 HInstruction* dominator_instr, 198 HBasicBlock* dominator_block) 199 REQUIRES_SHARED(Locks::mutator_lock_) { 200 // If the position where we should insert the bound type is not already a 201 // a bound type then we need to create one. 202 if (position == nullptr || !position->IsBoundType()) { 203 return true; 204 } 205 206 HBoundType* existing_bound_type = position->AsBoundType(); 207 if (existing_bound_type->GetUpperBound().IsSupertypeOf(upper_bound)) { 208 if (kIsDebugBuild) { 209 // Check that the existing HBoundType dominates all the uses. 210 for (const HUseListNode<HInstruction*>& use : obj->GetUses()) { 211 HInstruction* user = use.GetUser(); 212 if (dominator_instr != nullptr) { 213 DCHECK(!dominator_instr->StrictlyDominates(user) 214 || user == existing_bound_type 215 || existing_bound_type->StrictlyDominates(user)); 216 } else if (dominator_block != nullptr) { 217 DCHECK(!dominator_block->Dominates(user->GetBlock()) 218 || user == existing_bound_type 219 || existing_bound_type->StrictlyDominates(user)); 220 } 221 } 222 } 223 } else { 224 // TODO: if the current bound type is a refinement we could update the 225 // existing_bound_type with the a new upper limit. However, we also need to 226 // update its users and have access to the work list. 227 } 228 return false; 229 } 230 231 // Helper method to bound the type of `receiver` for all instructions dominated 232 // by `start_block`, or `start_instruction` if `start_block` is null. The new 233 // bound type will have its upper bound be `class_rti`. 234 static void BoundTypeIn(HInstruction* receiver, 235 HBasicBlock* start_block, 236 HInstruction* start_instruction, 237 const ReferenceTypeInfo& class_rti) { 238 // We only need to bound the type if we have uses in the relevant block. 239 // So start with null and create the HBoundType lazily, only if it's needed. 240 HBoundType* bound_type = nullptr; 241 DCHECK(!receiver->IsLoadClass()) << "We should not replace HLoadClass instructions"; 242 const HUseList<HInstruction*>& uses = receiver->GetUses(); 243 for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) { 244 HInstruction* user = it->GetUser(); 245 size_t index = it->GetIndex(); 246 // Increment `it` now because `*it` may disappear thanks to user->ReplaceInput(). 247 ++it; 248 bool dominates = (start_instruction != nullptr) 249 ? start_instruction->StrictlyDominates(user) 250 : start_block->Dominates(user->GetBlock()); 251 if (!dominates) { 252 continue; 253 } 254 if (bound_type == nullptr) { 255 ScopedObjectAccess soa(Thread::Current()); 256 HInstruction* insert_point = (start_instruction != nullptr) 257 ? start_instruction->GetNext() 258 : start_block->GetFirstInstruction(); 259 if (ShouldCreateBoundType( 260 insert_point, receiver, class_rti, start_instruction, start_block)) { 261 bound_type = new (receiver->GetBlock()->GetGraph()->GetAllocator()) HBoundType(receiver); 262 bound_type->SetUpperBound(class_rti, /* bound_can_be_null */ false); 263 start_block->InsertInstructionBefore(bound_type, insert_point); 264 // To comply with the RTP algorithm, don't type the bound type just yet, it will 265 // be handled in RTPVisitor::VisitBoundType. 266 } else { 267 // We already have a bound type on the position we would need to insert 268 // the new one. The existing bound type should dominate all the users 269 // (dchecked) so there's no need to continue. 270 break; 271 } 272 } 273 user->ReplaceInput(bound_type, index); 274 } 275 // If the receiver is a null check, also bound the type of the actual 276 // receiver. 277 if (receiver->IsNullCheck()) { 278 BoundTypeIn(receiver->InputAt(0), start_block, start_instruction, class_rti); 279 } 280 } 281 282 // Recognize the patterns: 283 // if (obj.shadow$_klass_ == Foo.class) ... 284 // deoptimize if (obj.shadow$_klass_ == Foo.class) 285 static void BoundTypeForClassCheck(HInstruction* check) { 286 if (!check->IsIf() && !check->IsDeoptimize()) { 287 return; 288 } 289 HInstruction* compare = check->InputAt(0); 290 if (!compare->IsEqual() && !compare->IsNotEqual()) { 291 return; 292 } 293 HInstruction* input_one = compare->InputAt(0); 294 HInstruction* input_two = compare->InputAt(1); 295 HLoadClass* load_class = input_one->IsLoadClass() 296 ? input_one->AsLoadClass() 297 : input_two->AsLoadClass(); 298 if (load_class == nullptr) { 299 return; 300 } 301 302 ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); 303 if (!class_rti.IsValid()) { 304 // We have loaded an unresolved class. Don't bother bounding the type. 305 return; 306 } 307 308 HInstanceFieldGet* field_get = (load_class == input_one) 309 ? input_two->AsInstanceFieldGet() 310 : input_one->AsInstanceFieldGet(); 311 if (field_get == nullptr) { 312 return; 313 } 314 HInstruction* receiver = field_get->InputAt(0); 315 ReferenceTypeInfo receiver_type = receiver->GetReferenceTypeInfo(); 316 if (receiver_type.IsExact()) { 317 // If we already know the receiver type, don't bother updating its users. 318 return; 319 } 320 321 { 322 ScopedObjectAccess soa(Thread::Current()); 323 ClassLinker* class_linker = Runtime::Current()->GetClassLinker(); 324 ArtField* field = class_linker->GetClassRoot(ClassLinker::kJavaLangObject)->GetInstanceField(0); 325 DCHECK_EQ(std::string(field->GetName()), "shadow$_klass_"); 326 if (field_get->GetFieldInfo().GetField() != field) { 327 return; 328 } 329 } 330 331 if (check->IsIf()) { 332 HBasicBlock* trueBlock = compare->IsEqual() 333 ? check->AsIf()->IfTrueSuccessor() 334 : check->AsIf()->IfFalseSuccessor(); 335 BoundTypeIn(receiver, trueBlock, /* start_instruction */ nullptr, class_rti); 336 } else { 337 DCHECK(check->IsDeoptimize()); 338 if (compare->IsEqual() && check->AsDeoptimize()->GuardsAnInput()) { 339 check->SetReferenceTypeInfo(class_rti); 340 } 341 } 342 } 343 344 void ReferenceTypePropagation::Run() { 345 RTPVisitor visitor(graph_, class_loader_, hint_dex_cache_, &handle_cache_, is_first_run_); 346 347 // To properly propagate type info we need to visit in the dominator-based order. 348 // Reverse post order guarantees a node's dominators are visited first. 349 // We take advantage of this order in `VisitBasicBlock`. 350 for (HBasicBlock* block : graph_->GetReversePostOrder()) { 351 visitor.VisitBasicBlock(block); 352 } 353 354 visitor.ProcessWorklist(); 355 ValidateTypes(); 356 } 357 358 void ReferenceTypePropagation::RTPVisitor::VisitBasicBlock(HBasicBlock* block) { 359 // Handle Phis first as there might be instructions in the same block who depend on them. 360 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 361 VisitPhi(it.Current()->AsPhi()); 362 } 363 364 // Handle instructions. Since RTP may add HBoundType instructions just after the 365 // last visited instruction, use `HInstructionIteratorHandleChanges` iterator. 366 for (HInstructionIteratorHandleChanges it(block->GetInstructions()); !it.Done(); it.Advance()) { 367 HInstruction* instr = it.Current(); 368 instr->Accept(this); 369 } 370 371 // Add extra nodes to bound types. 372 BoundTypeForIfNotNull(block); 373 BoundTypeForIfInstanceOf(block); 374 BoundTypeForClassCheck(block->GetLastInstruction()); 375 } 376 377 void ReferenceTypePropagation::RTPVisitor::BoundTypeForIfNotNull(HBasicBlock* block) { 378 HIf* ifInstruction = block->GetLastInstruction()->AsIf(); 379 if (ifInstruction == nullptr) { 380 return; 381 } 382 HInstruction* ifInput = ifInstruction->InputAt(0); 383 if (!ifInput->IsNotEqual() && !ifInput->IsEqual()) { 384 return; 385 } 386 HInstruction* input0 = ifInput->InputAt(0); 387 HInstruction* input1 = ifInput->InputAt(1); 388 HInstruction* obj = nullptr; 389 390 if (input1->IsNullConstant()) { 391 obj = input0; 392 } else if (input0->IsNullConstant()) { 393 obj = input1; 394 } else { 395 return; 396 } 397 398 if (!obj->CanBeNull() || obj->IsNullConstant()) { 399 // Null check is dead code and will be removed by DCE. 400 return; 401 } 402 DCHECK(!obj->IsLoadClass()) << "We should not replace HLoadClass instructions"; 403 404 // We only need to bound the type if we have uses in the relevant block. 405 // So start with null and create the HBoundType lazily, only if it's needed. 406 HBasicBlock* notNullBlock = ifInput->IsNotEqual() 407 ? ifInstruction->IfTrueSuccessor() 408 : ifInstruction->IfFalseSuccessor(); 409 410 ReferenceTypeInfo object_rti = ReferenceTypeInfo::Create( 411 handle_cache_->GetObjectClassHandle(), /* is_exact */ false); 412 413 BoundTypeIn(obj, notNullBlock, /* start_instruction */ nullptr, object_rti); 414 } 415 416 // Returns true if one of the patterns below has been recognized. If so, the 417 // InstanceOf instruction together with the true branch of `ifInstruction` will 418 // be returned using the out parameters. 419 // Recognized patterns: 420 // (1) patterns equivalent to `if (obj instanceof X)` 421 // (a) InstanceOf -> Equal to 1 -> If 422 // (b) InstanceOf -> NotEqual to 0 -> If 423 // (c) InstanceOf -> If 424 // (2) patterns equivalent to `if (!(obj instanceof X))` 425 // (a) InstanceOf -> Equal to 0 -> If 426 // (b) InstanceOf -> NotEqual to 1 -> If 427 // (c) InstanceOf -> BooleanNot -> If 428 static bool MatchIfInstanceOf(HIf* ifInstruction, 429 /* out */ HInstanceOf** instanceOf, 430 /* out */ HBasicBlock** trueBranch) { 431 HInstruction* input = ifInstruction->InputAt(0); 432 433 if (input->IsEqual()) { 434 HInstruction* rhs = input->AsEqual()->GetConstantRight(); 435 if (rhs != nullptr) { 436 HInstruction* lhs = input->AsEqual()->GetLeastConstantLeft(); 437 if (lhs->IsInstanceOf() && rhs->IsIntConstant()) { 438 if (rhs->AsIntConstant()->IsTrue()) { 439 // Case (1a) 440 *trueBranch = ifInstruction->IfTrueSuccessor(); 441 } else { 442 // Case (2a) 443 DCHECK(rhs->AsIntConstant()->IsFalse()) << rhs->AsIntConstant()->GetValue(); 444 *trueBranch = ifInstruction->IfFalseSuccessor(); 445 } 446 *instanceOf = lhs->AsInstanceOf(); 447 return true; 448 } 449 } 450 } else if (input->IsNotEqual()) { 451 HInstruction* rhs = input->AsNotEqual()->GetConstantRight(); 452 if (rhs != nullptr) { 453 HInstruction* lhs = input->AsNotEqual()->GetLeastConstantLeft(); 454 if (lhs->IsInstanceOf() && rhs->IsIntConstant()) { 455 if (rhs->AsIntConstant()->IsFalse()) { 456 // Case (1b) 457 *trueBranch = ifInstruction->IfTrueSuccessor(); 458 } else { 459 // Case (2b) 460 DCHECK(rhs->AsIntConstant()->IsTrue()) << rhs->AsIntConstant()->GetValue(); 461 *trueBranch = ifInstruction->IfFalseSuccessor(); 462 } 463 *instanceOf = lhs->AsInstanceOf(); 464 return true; 465 } 466 } 467 } else if (input->IsInstanceOf()) { 468 // Case (1c) 469 *instanceOf = input->AsInstanceOf(); 470 *trueBranch = ifInstruction->IfTrueSuccessor(); 471 return true; 472 } else if (input->IsBooleanNot()) { 473 HInstruction* not_input = input->InputAt(0); 474 if (not_input->IsInstanceOf()) { 475 // Case (2c) 476 *instanceOf = not_input->AsInstanceOf(); 477 *trueBranch = ifInstruction->IfFalseSuccessor(); 478 return true; 479 } 480 } 481 482 return false; 483 } 484 485 // Detects if `block` is the True block for the pattern 486 // `if (x instanceof ClassX) { }` 487 // If that's the case insert an HBoundType instruction to bound the type of `x` 488 // to `ClassX` in the scope of the dominated blocks. 489 void ReferenceTypePropagation::RTPVisitor::BoundTypeForIfInstanceOf(HBasicBlock* block) { 490 HIf* ifInstruction = block->GetLastInstruction()->AsIf(); 491 if (ifInstruction == nullptr) { 492 return; 493 } 494 495 // Try to recognize common `if (instanceof)` and `if (!instanceof)` patterns. 496 HInstanceOf* instanceOf = nullptr; 497 HBasicBlock* instanceOfTrueBlock = nullptr; 498 if (!MatchIfInstanceOf(ifInstruction, &instanceOf, &instanceOfTrueBlock)) { 499 return; 500 } 501 502 HLoadClass* load_class = instanceOf->InputAt(1)->AsLoadClass(); 503 ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); 504 if (!class_rti.IsValid()) { 505 // He have loaded an unresolved class. Don't bother bounding the type. 506 return; 507 } 508 509 HInstruction* obj = instanceOf->InputAt(0); 510 if (obj->GetReferenceTypeInfo().IsExact() && !obj->IsPhi()) { 511 // This method is being called while doing a fixed-point calculation 512 // over phis. Non-phis instruction whose type is already known do 513 // not need to be bound to another type. 514 // Not that this also prevents replacing `HLoadClass` with a `HBoundType`. 515 // `HCheckCast` and `HInstanceOf` expect a `HLoadClass` as a second 516 // input. 517 return; 518 } 519 520 { 521 ScopedObjectAccess soa(Thread::Current()); 522 if (!class_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes()) { 523 class_rti = ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false); 524 } 525 } 526 BoundTypeIn(obj, instanceOfTrueBlock, /* start_instruction */ nullptr, class_rti); 527 } 528 529 void ReferenceTypePropagation::RTPVisitor::SetClassAsTypeInfo(HInstruction* instr, 530 ObjPtr<mirror::Class> klass, 531 bool is_exact) { 532 if (instr->IsInvokeStaticOrDirect() && instr->AsInvokeStaticOrDirect()->IsStringInit()) { 533 // Calls to String.<init> are replaced with a StringFactory. 534 if (kIsDebugBuild) { 535 HInvokeStaticOrDirect* invoke = instr->AsInvokeStaticOrDirect(); 536 ClassLinker* cl = Runtime::Current()->GetClassLinker(); 537 Thread* self = Thread::Current(); 538 StackHandleScope<2> hs(self); 539 const DexFile& dex_file = *invoke->GetTargetMethod().dex_file; 540 uint32_t dex_method_index = invoke->GetTargetMethod().index; 541 Handle<mirror::DexCache> dex_cache( 542 hs.NewHandle(FindDexCacheWithHint(self, dex_file, hint_dex_cache_))); 543 // Use a null loader, the target method is in a boot classpath dex file. 544 Handle<mirror::ClassLoader> loader(hs.NewHandle<mirror::ClassLoader>(nullptr)); 545 ArtMethod* method = cl->ResolveMethod<ClassLinker::ResolveMode::kNoChecks>( 546 dex_method_index, dex_cache, loader, /* referrer */ nullptr, kDirect); 547 DCHECK(method != nullptr); 548 mirror::Class* declaring_class = method->GetDeclaringClass(); 549 DCHECK(declaring_class != nullptr); 550 DCHECK(declaring_class->IsStringClass()) 551 << "Expected String class: " << declaring_class->PrettyDescriptor(); 552 DCHECK(method->IsConstructor()) 553 << "Expected String.<init>: " << method->PrettyMethod(); 554 } 555 instr->SetReferenceTypeInfo( 556 ReferenceTypeInfo::Create(handle_cache_->GetStringClassHandle(), /* is_exact */ true)); 557 } else if (IsAdmissible(klass.Ptr())) { 558 ReferenceTypeInfo::TypeHandle handle = handle_cache_->NewHandle(klass); 559 is_exact = is_exact || handle->CannotBeAssignedFromOtherTypes(); 560 instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(handle, is_exact)); 561 } else { 562 instr->SetReferenceTypeInfo(instr->GetBlock()->GetGraph()->GetInexactObjectRti()); 563 } 564 } 565 566 void ReferenceTypePropagation::RTPVisitor::VisitDeoptimize(HDeoptimize* instr) { 567 BoundTypeForClassCheck(instr); 568 } 569 570 void ReferenceTypePropagation::RTPVisitor::UpdateReferenceTypeInfo(HInstruction* instr, 571 dex::TypeIndex type_idx, 572 const DexFile& dex_file, 573 bool is_exact) { 574 DCHECK_EQ(instr->GetType(), DataType::Type::kReference); 575 576 ScopedObjectAccess soa(Thread::Current()); 577 ObjPtr<mirror::DexCache> dex_cache = FindDexCacheWithHint(soa.Self(), dex_file, hint_dex_cache_); 578 ObjPtr<mirror::Class> klass = Runtime::Current()->GetClassLinker()->LookupResolvedType( 579 type_idx, dex_cache, class_loader_.Get()); 580 SetClassAsTypeInfo(instr, klass, is_exact); 581 } 582 583 void ReferenceTypePropagation::RTPVisitor::VisitNewInstance(HNewInstance* instr) { 584 ScopedObjectAccess soa(Thread::Current()); 585 SetClassAsTypeInfo(instr, instr->GetLoadClass()->GetClass().Get(), /* is_exact */ true); 586 } 587 588 void ReferenceTypePropagation::RTPVisitor::VisitNewArray(HNewArray* instr) { 589 ScopedObjectAccess soa(Thread::Current()); 590 SetClassAsTypeInfo(instr, instr->GetLoadClass()->GetClass().Get(), /* is_exact */ true); 591 } 592 593 void ReferenceTypePropagation::RTPVisitor::VisitParameterValue(HParameterValue* instr) { 594 // We check if the existing type is valid: the inliner may have set it. 595 if (instr->GetType() == DataType::Type::kReference && !instr->GetReferenceTypeInfo().IsValid()) { 596 UpdateReferenceTypeInfo(instr, 597 instr->GetTypeIndex(), 598 instr->GetDexFile(), 599 /* is_exact */ false); 600 } 601 } 602 603 void ReferenceTypePropagation::RTPVisitor::UpdateFieldAccessTypeInfo(HInstruction* instr, 604 const FieldInfo& info) { 605 if (instr->GetType() != DataType::Type::kReference) { 606 return; 607 } 608 609 ScopedObjectAccess soa(Thread::Current()); 610 ObjPtr<mirror::Class> klass; 611 612 // The field is unknown only during tests. 613 if (info.GetField() != nullptr) { 614 klass = info.GetField()->LookupResolvedType(); 615 } 616 617 SetClassAsTypeInfo(instr, klass, /* is_exact */ false); 618 } 619 620 void ReferenceTypePropagation::RTPVisitor::VisitInstanceFieldGet(HInstanceFieldGet* instr) { 621 UpdateFieldAccessTypeInfo(instr, instr->GetFieldInfo()); 622 } 623 624 void ReferenceTypePropagation::RTPVisitor::VisitStaticFieldGet(HStaticFieldGet* instr) { 625 UpdateFieldAccessTypeInfo(instr, instr->GetFieldInfo()); 626 } 627 628 void ReferenceTypePropagation::RTPVisitor::VisitUnresolvedInstanceFieldGet( 629 HUnresolvedInstanceFieldGet* instr) { 630 // TODO: Use descriptor to get the actual type. 631 if (instr->GetFieldType() == DataType::Type::kReference) { 632 instr->SetReferenceTypeInfo(instr->GetBlock()->GetGraph()->GetInexactObjectRti()); 633 } 634 } 635 636 void ReferenceTypePropagation::RTPVisitor::VisitUnresolvedStaticFieldGet( 637 HUnresolvedStaticFieldGet* instr) { 638 // TODO: Use descriptor to get the actual type. 639 if (instr->GetFieldType() == DataType::Type::kReference) { 640 instr->SetReferenceTypeInfo(instr->GetBlock()->GetGraph()->GetInexactObjectRti()); 641 } 642 } 643 644 void ReferenceTypePropagation::RTPVisitor::VisitLoadClass(HLoadClass* instr) { 645 ScopedObjectAccess soa(Thread::Current()); 646 Handle<mirror::Class> resolved_class = instr->GetClass(); 647 if (IsAdmissible(resolved_class.Get())) { 648 instr->SetLoadedClassRTI(ReferenceTypeInfo::Create( 649 resolved_class, /* is_exact */ true)); 650 } 651 instr->SetReferenceTypeInfo( 652 ReferenceTypeInfo::Create(handle_cache_->GetClassClassHandle(), /* is_exact */ true)); 653 } 654 655 void ReferenceTypePropagation::RTPVisitor::VisitClinitCheck(HClinitCheck* instr) { 656 instr->SetReferenceTypeInfo(instr->InputAt(0)->GetReferenceTypeInfo()); 657 } 658 659 void ReferenceTypePropagation::RTPVisitor::VisitLoadString(HLoadString* instr) { 660 instr->SetReferenceTypeInfo( 661 ReferenceTypeInfo::Create(handle_cache_->GetStringClassHandle(), /* is_exact */ true)); 662 } 663 664 void ReferenceTypePropagation::RTPVisitor::VisitLoadException(HLoadException* instr) { 665 DCHECK(instr->GetBlock()->IsCatchBlock()); 666 TryCatchInformation* catch_info = instr->GetBlock()->GetTryCatchInformation(); 667 668 if (catch_info->IsCatchAllTypeIndex()) { 669 instr->SetReferenceTypeInfo( 670 ReferenceTypeInfo::Create(handle_cache_->GetThrowableClassHandle(), /* is_exact */ false)); 671 } else { 672 UpdateReferenceTypeInfo(instr, 673 catch_info->GetCatchTypeIndex(), 674 catch_info->GetCatchDexFile(), 675 /* is_exact */ false); 676 } 677 } 678 679 void ReferenceTypePropagation::RTPVisitor::VisitNullCheck(HNullCheck* instr) { 680 ReferenceTypeInfo parent_rti = instr->InputAt(0)->GetReferenceTypeInfo(); 681 if (parent_rti.IsValid()) { 682 instr->SetReferenceTypeInfo(parent_rti); 683 } 684 } 685 686 void ReferenceTypePropagation::RTPVisitor::VisitBoundType(HBoundType* instr) { 687 ReferenceTypeInfo class_rti = instr->GetUpperBound(); 688 if (class_rti.IsValid()) { 689 ScopedObjectAccess soa(Thread::Current()); 690 // Narrow the type as much as possible. 691 HInstruction* obj = instr->InputAt(0); 692 ReferenceTypeInfo obj_rti = obj->GetReferenceTypeInfo(); 693 if (class_rti.IsExact()) { 694 instr->SetReferenceTypeInfo(class_rti); 695 } else if (obj_rti.IsValid()) { 696 if (class_rti.IsSupertypeOf(obj_rti)) { 697 // Object type is more specific. 698 instr->SetReferenceTypeInfo(obj_rti); 699 } else { 700 // Upper bound is more specific, or unrelated to the object's type. 701 // Note that the object might then be exact, and we know the code dominated by this 702 // bound type is dead. To not confuse potential other optimizations, we mark 703 // the bound as non-exact. 704 instr->SetReferenceTypeInfo( 705 ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), /* is_exact */ false)); 706 } 707 } else { 708 // Object not typed yet. Leave BoundType untyped for now rather than 709 // assign the type conservatively. 710 } 711 instr->SetCanBeNull(obj->CanBeNull() && instr->GetUpperCanBeNull()); 712 } else { 713 // The owner of the BoundType was already visited. If the class is unresolved, 714 // the BoundType should have been removed from the data flow and this method 715 // should remove it from the graph. 716 DCHECK(!instr->HasUses()); 717 instr->GetBlock()->RemoveInstruction(instr); 718 } 719 } 720 721 void ReferenceTypePropagation::RTPVisitor::VisitCheckCast(HCheckCast* check_cast) { 722 HLoadClass* load_class = check_cast->InputAt(1)->AsLoadClass(); 723 ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); 724 HBoundType* bound_type = check_cast->GetNext()->AsBoundType(); 725 if (bound_type == nullptr || bound_type->GetUpperBound().IsValid()) { 726 // The next instruction is not an uninitialized BoundType. This must be 727 // an RTP pass after SsaBuilder and we do not need to do anything. 728 return; 729 } 730 DCHECK_EQ(bound_type->InputAt(0), check_cast->InputAt(0)); 731 732 if (class_rti.IsValid()) { 733 DCHECK(is_first_run_); 734 ScopedObjectAccess soa(Thread::Current()); 735 // This is the first run of RTP and class is resolved. 736 bool is_exact = class_rti.GetTypeHandle()->CannotBeAssignedFromOtherTypes(); 737 bound_type->SetUpperBound(ReferenceTypeInfo::Create(class_rti.GetTypeHandle(), is_exact), 738 /* CheckCast succeeds for nulls. */ true); 739 } else { 740 // This is the first run of RTP and class is unresolved. Remove the binding. 741 // The instruction itself is removed in VisitBoundType so as to not 742 // invalidate HInstructionIterator. 743 bound_type->ReplaceWith(bound_type->InputAt(0)); 744 } 745 } 746 747 void ReferenceTypePropagation::RTPVisitor::VisitPhi(HPhi* phi) { 748 if (phi->IsDead() || phi->GetType() != DataType::Type::kReference) { 749 return; 750 } 751 752 if (phi->GetBlock()->IsLoopHeader()) { 753 // Set the initial type for the phi. Use the non back edge input for reaching 754 // a fixed point faster. 755 HInstruction* first_input = phi->InputAt(0); 756 ReferenceTypeInfo first_input_rti = first_input->GetReferenceTypeInfo(); 757 if (first_input_rti.IsValid() && !first_input->IsNullConstant()) { 758 phi->SetCanBeNull(first_input->CanBeNull()); 759 phi->SetReferenceTypeInfo(first_input_rti); 760 } 761 AddToWorklist(phi); 762 } else { 763 // Eagerly compute the type of the phi, for quicker convergence. Note 764 // that we don't need to add users to the worklist because we are 765 // doing a reverse post-order visit, therefore either the phi users are 766 // non-loop phi and will be visited later in the visit, or are loop-phis, 767 // and they are already in the work list. 768 UpdateNullability(phi); 769 UpdateReferenceTypeInfo(phi); 770 } 771 } 772 773 void ReferenceTypePropagation::FixUpInstructionType(HInstruction* instruction, 774 VariableSizedHandleScope* handle_scope) { 775 if (instruction->IsSelect()) { 776 ScopedObjectAccess soa(Thread::Current()); 777 HandleCache handle_cache(handle_scope); 778 HSelect* select = instruction->AsSelect(); 779 ReferenceTypeInfo false_rti = select->GetFalseValue()->GetReferenceTypeInfo(); 780 ReferenceTypeInfo true_rti = select->GetTrueValue()->GetReferenceTypeInfo(); 781 select->SetReferenceTypeInfo(MergeTypes(false_rti, true_rti, &handle_cache)); 782 } else { 783 LOG(FATAL) << "Invalid instruction in FixUpInstructionType"; 784 } 785 } 786 787 ReferenceTypeInfo ReferenceTypePropagation::MergeTypes(const ReferenceTypeInfo& a, 788 const ReferenceTypeInfo& b, 789 HandleCache* handle_cache) { 790 if (!b.IsValid()) { 791 return a; 792 } 793 if (!a.IsValid()) { 794 return b; 795 } 796 797 bool is_exact = a.IsExact() && b.IsExact(); 798 ReferenceTypeInfo::TypeHandle result_type_handle; 799 ReferenceTypeInfo::TypeHandle a_type_handle = a.GetTypeHandle(); 800 ReferenceTypeInfo::TypeHandle b_type_handle = b.GetTypeHandle(); 801 bool a_is_interface = a_type_handle->IsInterface(); 802 bool b_is_interface = b_type_handle->IsInterface(); 803 804 if (a.GetTypeHandle().Get() == b.GetTypeHandle().Get()) { 805 result_type_handle = a_type_handle; 806 } else if (a.IsSupertypeOf(b)) { 807 result_type_handle = a_type_handle; 808 is_exact = false; 809 } else if (b.IsSupertypeOf(a)) { 810 result_type_handle = b_type_handle; 811 is_exact = false; 812 } else if (!a_is_interface && !b_is_interface) { 813 result_type_handle = 814 handle_cache->NewHandle(a_type_handle->GetCommonSuperClass(b_type_handle)); 815 is_exact = false; 816 } else { 817 // This can happen if: 818 // - both types are interfaces. TODO(calin): implement 819 // - one is an interface, the other a class, and the type does not implement the interface 820 // e.g: 821 // void foo(Interface i, boolean cond) { 822 // Object o = cond ? i : new Object(); 823 // } 824 result_type_handle = handle_cache->GetObjectClassHandle(); 825 is_exact = false; 826 } 827 828 return ReferenceTypeInfo::Create(result_type_handle, is_exact); 829 } 830 831 void ReferenceTypePropagation::RTPVisitor::UpdateArrayGet(HArrayGet* instr) { 832 DCHECK_EQ(DataType::Type::kReference, instr->GetType()); 833 834 ReferenceTypeInfo parent_rti = instr->InputAt(0)->GetReferenceTypeInfo(); 835 if (!parent_rti.IsValid()) { 836 return; 837 } 838 839 Handle<mirror::Class> handle = parent_rti.GetTypeHandle(); 840 if (handle->IsObjectArrayClass() && IsAdmissible(handle->GetComponentType())) { 841 ReferenceTypeInfo::TypeHandle component_handle = 842 handle_cache_->NewHandle(handle->GetComponentType()); 843 bool is_exact = component_handle->CannotBeAssignedFromOtherTypes(); 844 instr->SetReferenceTypeInfo(ReferenceTypeInfo::Create(component_handle, is_exact)); 845 } else { 846 // We don't know what the parent actually is, so we fallback to object. 847 instr->SetReferenceTypeInfo(instr->GetBlock()->GetGraph()->GetInexactObjectRti()); 848 } 849 } 850 851 bool ReferenceTypePropagation::RTPVisitor::UpdateReferenceTypeInfo(HInstruction* instr) { 852 ScopedObjectAccess soa(Thread::Current()); 853 854 ReferenceTypeInfo previous_rti = instr->GetReferenceTypeInfo(); 855 if (instr->IsBoundType()) { 856 UpdateBoundType(instr->AsBoundType()); 857 } else if (instr->IsPhi()) { 858 UpdatePhi(instr->AsPhi()); 859 } else if (instr->IsNullCheck()) { 860 ReferenceTypeInfo parent_rti = instr->InputAt(0)->GetReferenceTypeInfo(); 861 if (parent_rti.IsValid()) { 862 instr->SetReferenceTypeInfo(parent_rti); 863 } 864 } else if (instr->IsArrayGet()) { 865 // TODO: consider if it's worth "looking back" and binding the input object 866 // to an array type. 867 UpdateArrayGet(instr->AsArrayGet()); 868 } else { 869 LOG(FATAL) << "Invalid instruction (should not get here)"; 870 } 871 872 return !previous_rti.IsEqual(instr->GetReferenceTypeInfo()); 873 } 874 875 void ReferenceTypePropagation::RTPVisitor::VisitInvoke(HInvoke* instr) { 876 if (instr->GetType() != DataType::Type::kReference) { 877 return; 878 } 879 880 ScopedObjectAccess soa(Thread::Current()); 881 ArtMethod* method = instr->GetResolvedMethod(); 882 ObjPtr<mirror::Class> klass = (method == nullptr) ? nullptr : method->LookupResolvedReturnType(); 883 SetClassAsTypeInfo(instr, klass, /* is_exact */ false); 884 } 885 886 void ReferenceTypePropagation::RTPVisitor::VisitArrayGet(HArrayGet* instr) { 887 if (instr->GetType() != DataType::Type::kReference) { 888 return; 889 } 890 891 ScopedObjectAccess soa(Thread::Current()); 892 UpdateArrayGet(instr); 893 if (!instr->GetReferenceTypeInfo().IsValid()) { 894 worklist_.push_back(instr); 895 } 896 } 897 898 void ReferenceTypePropagation::RTPVisitor::UpdateBoundType(HBoundType* instr) { 899 ReferenceTypeInfo input_rti = instr->InputAt(0)->GetReferenceTypeInfo(); 900 if (!input_rti.IsValid()) { 901 return; // No new info yet. 902 } 903 904 ReferenceTypeInfo upper_bound_rti = instr->GetUpperBound(); 905 if (upper_bound_rti.IsExact()) { 906 instr->SetReferenceTypeInfo(upper_bound_rti); 907 } else if (upper_bound_rti.IsSupertypeOf(input_rti)) { 908 // input is more specific. 909 instr->SetReferenceTypeInfo(input_rti); 910 } else { 911 // upper_bound is more specific or unrelated. 912 // Note that the object might then be exact, and we know the code dominated by this 913 // bound type is dead. To not confuse potential other optimizations, we mark 914 // the bound as non-exact. 915 instr->SetReferenceTypeInfo( 916 ReferenceTypeInfo::Create(upper_bound_rti.GetTypeHandle(), /* is_exact */ false)); 917 } 918 } 919 920 // NullConstant inputs are ignored during merging as they do not provide any useful information. 921 // If all the inputs are NullConstants then the type of the phi will be set to Object. 922 void ReferenceTypePropagation::RTPVisitor::UpdatePhi(HPhi* instr) { 923 DCHECK(instr->IsLive()); 924 925 HInputsRef inputs = instr->GetInputs(); 926 size_t first_input_index_not_null = 0; 927 while (first_input_index_not_null < inputs.size() && 928 inputs[first_input_index_not_null]->IsNullConstant()) { 929 first_input_index_not_null++; 930 } 931 if (first_input_index_not_null == inputs.size()) { 932 // All inputs are NullConstants, set the type to object. 933 // This may happen in the presence of inlining. 934 instr->SetReferenceTypeInfo(instr->GetBlock()->GetGraph()->GetInexactObjectRti()); 935 return; 936 } 937 938 ReferenceTypeInfo new_rti = instr->InputAt(first_input_index_not_null)->GetReferenceTypeInfo(); 939 940 if (new_rti.IsValid() && new_rti.IsObjectClass() && !new_rti.IsExact()) { 941 // Early return if we are Object and inexact. 942 instr->SetReferenceTypeInfo(new_rti); 943 return; 944 } 945 946 for (size_t i = first_input_index_not_null + 1; i < inputs.size(); i++) { 947 if (inputs[i]->IsNullConstant()) { 948 continue; 949 } 950 new_rti = MergeTypes(new_rti, inputs[i]->GetReferenceTypeInfo(), handle_cache_); 951 if (new_rti.IsValid() && new_rti.IsObjectClass()) { 952 if (!new_rti.IsExact()) { 953 break; 954 } else { 955 continue; 956 } 957 } 958 } 959 960 if (new_rti.IsValid()) { 961 instr->SetReferenceTypeInfo(new_rti); 962 } 963 } 964 965 // Re-computes and updates the nullability of the instruction. Returns whether or 966 // not the nullability was changed. 967 bool ReferenceTypePropagation::RTPVisitor::UpdateNullability(HInstruction* instr) { 968 DCHECK((instr->IsPhi() && instr->AsPhi()->IsLive()) 969 || instr->IsBoundType() 970 || instr->IsNullCheck() 971 || instr->IsArrayGet()); 972 973 if (!instr->IsPhi() && !instr->IsBoundType()) { 974 return false; 975 } 976 977 bool existing_can_be_null = instr->CanBeNull(); 978 if (instr->IsPhi()) { 979 HPhi* phi = instr->AsPhi(); 980 bool new_can_be_null = false; 981 for (HInstruction* input : phi->GetInputs()) { 982 if (input->CanBeNull()) { 983 new_can_be_null = true; 984 break; 985 } 986 } 987 phi->SetCanBeNull(new_can_be_null); 988 } else if (instr->IsBoundType()) { 989 HBoundType* bound_type = instr->AsBoundType(); 990 bound_type->SetCanBeNull(instr->InputAt(0)->CanBeNull() && bound_type->GetUpperCanBeNull()); 991 } 992 return existing_can_be_null != instr->CanBeNull(); 993 } 994 995 void ReferenceTypePropagation::RTPVisitor::ProcessWorklist() { 996 while (!worklist_.empty()) { 997 HInstruction* instruction = worklist_.back(); 998 worklist_.pop_back(); 999 bool updated_nullability = UpdateNullability(instruction); 1000 bool updated_reference_type = UpdateReferenceTypeInfo(instruction); 1001 if (updated_nullability || updated_reference_type) { 1002 AddDependentInstructionsToWorklist(instruction); 1003 } 1004 } 1005 } 1006 1007 void ReferenceTypePropagation::RTPVisitor::AddToWorklist(HInstruction* instruction) { 1008 DCHECK_EQ(instruction->GetType(), DataType::Type::kReference) 1009 << instruction->DebugName() << ":" << instruction->GetType(); 1010 worklist_.push_back(instruction); 1011 } 1012 1013 void ReferenceTypePropagation::RTPVisitor::AddDependentInstructionsToWorklist( 1014 HInstruction* instruction) { 1015 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) { 1016 HInstruction* user = use.GetUser(); 1017 if ((user->IsPhi() && user->AsPhi()->IsLive()) 1018 || user->IsBoundType() 1019 || user->IsNullCheck() 1020 || (user->IsArrayGet() && (user->GetType() == DataType::Type::kReference))) { 1021 AddToWorklist(user); 1022 } 1023 } 1024 } 1025 1026 } // namespace art 1027
