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