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