Home | History | Annotate | Download | only in verifier 
      1 /*
      2  * Copyright (C) 2012 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 "reg_type.h"
     18 
     19 
     20 #include "base/casts.h"
     21 #include "class_linker-inl.h"
     22 #include "dex_file-inl.h"
     23 #include "mirror/class.h"
     24 #include "mirror/class-inl.h"
     25 #include "mirror/object-inl.h"
     26 #include "mirror/object_array-inl.h"
     27 #include "reg_type_cache-inl.h"
     28 #include "scoped_thread_state_change.h"
     29 
     30 #include <limits>
     31 #include <sstream>
     32 
     33 namespace art {
     34 namespace verifier {
     35 
     36 UndefinedType* UndefinedType::instance_ = NULL;
     37 ConflictType* ConflictType::instance_ = NULL;
     38 BooleanType* BooleanType::instance = NULL;
     39 ByteType* ByteType::instance_ = NULL;
     40 ShortType* ShortType::instance_ = NULL;
     41 CharType* CharType::instance_ = NULL;
     42 FloatType* FloatType::instance_ = NULL;
     43 LongLoType* LongLoType::instance_ = NULL;
     44 LongHiType* LongHiType::instance_ = NULL;
     45 DoubleLoType* DoubleLoType::instance_ = NULL;
     46 DoubleHiType* DoubleHiType::instance_ = NULL;
     47 IntegerType* IntegerType::instance_ = NULL;
     48 
     49 int32_t RegType::ConstantValue() const {
     50   ScopedObjectAccess soa(Thread::Current());
     51   LOG(FATAL) << "Unexpected call to ConstantValue: " << *this;
     52   return 0;
     53 }
     54 
     55 int32_t RegType::ConstantValueLo() const {
     56   ScopedObjectAccess soa(Thread::Current());
     57   LOG(FATAL) << "Unexpected call to ConstantValueLo: " << *this;
     58   return 0;
     59 }
     60 
     61 int32_t RegType::ConstantValueHi() const {
     62   ScopedObjectAccess soa(Thread::Current());
     63   LOG(FATAL) << "Unexpected call to ConstantValueHi: " << *this;
     64   return 0;
     65 }
     66 
     67 PrimitiveType::PrimitiveType(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
     68     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
     69     : RegType(klass, descriptor, cache_id) {
     70   CHECK(klass != NULL);
     71   CHECK(!descriptor.empty());
     72 }
     73 
     74 Cat1Type::Cat1Type(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
     75     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
     76     : PrimitiveType(klass, descriptor, cache_id) {
     77 }
     78 
     79 Cat2Type::Cat2Type(mirror::Class* klass, const std::string& descriptor, uint16_t cache_id)
     80     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
     81     : PrimitiveType(klass, descriptor, cache_id) {
     82 }
     83 
     84 std::string PreciseConstType::Dump() {
     85   std::stringstream result;
     86   uint32_t val = ConstantValue();
     87   if (val == 0) {
     88     CHECK(IsPreciseConstant());
     89     result << "Zero/null";
     90   } else {
     91     result << "Precise ";
     92     if (IsConstantShort()) {
     93       result << StringPrintf("Constant: %d", val);
     94     } else {
     95       result << StringPrintf("Constant: 0x%x", val);
     96     }
     97   }
     98   return result.str();
     99 }
    100 
    101 std::string BooleanType::Dump() {
    102   return "Boolean";
    103 }
    104 
    105 std::string ConflictType::Dump() {
    106     return "Conflict";
    107 }
    108 
    109 std::string ByteType::Dump() {
    110   return "Byte";
    111 }
    112 
    113 std::string ShortType::Dump() {
    114   return "Short";
    115 }
    116 
    117 std::string CharType::Dump() {
    118   return "Char";
    119 }
    120 
    121 std::string FloatType::Dump() {
    122   return "Float";
    123 }
    124 
    125 std::string LongLoType::Dump() {
    126   return "Long (Low Half)";
    127 }
    128 
    129 std::string LongHiType::Dump() {
    130   return "Long (High Half)";
    131 }
    132 
    133 std::string DoubleLoType::Dump() {
    134   return "Double (Low Half)";
    135 }
    136 
    137 std::string DoubleHiType::Dump() {
    138   return "Double (High Half)";
    139 }
    140 
    141 std::string IntegerType::Dump() {
    142     return "Integer";
    143 }
    144 
    145 DoubleHiType* DoubleHiType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
    146                                            uint16_t cache_id) {
    147   if (instance_ == NULL) {
    148     instance_ = new DoubleHiType(klass, descriptor, cache_id);
    149   }
    150   return instance_;
    151 }
    152 
    153 DoubleHiType* DoubleHiType::GetInstance() {
    154   CHECK(instance_ != NULL);
    155   return instance_;
    156 }
    157 
    158 void DoubleHiType::Destroy() {
    159   if (instance_ != NULL) {
    160     delete instance_;
    161     instance_ = NULL;
    162   }
    163 }
    164 
    165 DoubleLoType* DoubleLoType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
    166                                            uint16_t cache_id) {
    167   if (instance_ == NULL) {
    168     instance_ = new DoubleLoType(klass, descriptor, cache_id);
    169   }
    170   return instance_;
    171 }
    172 
    173 DoubleLoType* DoubleLoType::GetInstance() {
    174   CHECK(instance_ != NULL);
    175   return instance_;
    176 }
    177 
    178 void DoubleLoType::Destroy() {
    179   if (instance_ != NULL) {
    180     delete instance_;
    181     instance_ = NULL;
    182   }
    183 }
    184 
    185 LongLoType* LongLoType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
    186                                        uint16_t cache_id) {
    187   if (instance_ == NULL) {
    188     instance_ = new LongLoType(klass, descriptor, cache_id);
    189   }
    190   return instance_;
    191 }
    192 
    193 LongHiType* LongHiType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
    194                                        uint16_t cache_id) {
    195   if (instance_ == NULL) {
    196     instance_ = new LongHiType(klass, descriptor, cache_id);
    197   }
    198   return instance_;
    199 }
    200 
    201 LongHiType* LongHiType::GetInstance() {
    202   CHECK(instance_ != NULL);
    203   return instance_;
    204 }
    205 
    206 void LongHiType::Destroy() {
    207   if (instance_ != NULL) {
    208     delete instance_;
    209     instance_ = NULL;
    210   }
    211 }
    212 
    213 LongLoType* LongLoType::GetInstance() {
    214   CHECK(instance_ != NULL);
    215   return instance_;
    216 }
    217 
    218 void LongLoType::Destroy() {
    219   if (instance_ != NULL) {
    220     delete instance_;
    221     instance_ = NULL;
    222   }
    223 }
    224 
    225 FloatType* FloatType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
    226                                      uint16_t cache_id) {
    227   if (instance_ == NULL) {
    228     instance_ = new FloatType(klass, descriptor, cache_id);
    229   }
    230   return instance_;
    231 }
    232 FloatType* FloatType::GetInstance() {
    233   CHECK(instance_ != NULL);
    234   return instance_;
    235 }
    236 
    237 void FloatType::Destroy() {
    238   if (instance_ != NULL) {
    239     delete instance_;
    240     instance_ = NULL;
    241   }
    242 }
    243 
    244 CharType* CharType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
    245                                    uint16_t cache_id) {
    246   if (instance_ == NULL) {
    247     instance_ = new CharType(klass, descriptor, cache_id);
    248   }
    249   return instance_;
    250 }
    251 
    252 CharType* CharType::GetInstance() {
    253   CHECK(instance_ != NULL);
    254   return instance_;
    255 }
    256 
    257 void CharType::Destroy() {
    258   if (instance_ != NULL) {
    259     delete instance_;
    260     instance_ = NULL;
    261   }
    262 }
    263 
    264 ShortType* ShortType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
    265                                      uint16_t cache_id) {
    266   if (instance_ == NULL) {
    267     instance_ = new ShortType(klass, descriptor, cache_id);
    268   }
    269   return instance_;
    270 }
    271 
    272 ShortType* ShortType::GetInstance() {
    273   CHECK(instance_ != NULL);
    274   return instance_;
    275 }
    276 
    277 void ShortType::Destroy() {
    278   if (instance_ != NULL) {
    279     delete instance_;
    280     instance_ = NULL;
    281   }
    282 }
    283 
    284 ByteType* ByteType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
    285                                    uint16_t cache_id) {
    286   if (instance_ == NULL) {
    287     instance_ = new ByteType(klass, descriptor, cache_id);
    288   }
    289   return instance_;
    290 }
    291 
    292 ByteType* ByteType::GetInstance() {
    293   CHECK(instance_ != NULL);
    294   return instance_;
    295 }
    296 
    297 void ByteType::Destroy() {
    298   if (instance_ != NULL) {
    299     delete instance_;
    300     instance_ = NULL;
    301   }
    302 }
    303 
    304 IntegerType* IntegerType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
    305                                          uint16_t cache_id) {
    306   if (instance_ == NULL) {
    307     instance_ = new IntegerType(klass, descriptor, cache_id);
    308   }
    309   return instance_;
    310 }
    311 
    312 IntegerType* IntegerType::GetInstance() {
    313   CHECK(instance_ != NULL);
    314   return instance_;
    315 }
    316 
    317 void IntegerType::Destroy() {
    318   if (instance_ != NULL) {
    319     delete instance_;
    320     instance_ = NULL;
    321   }
    322 }
    323 
    324 ConflictType* ConflictType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
    325                                            uint16_t cache_id) {
    326   if (instance_ == NULL) {
    327     instance_ = new ConflictType(klass, descriptor, cache_id);
    328   }
    329   return instance_;
    330 }
    331 
    332 ConflictType* ConflictType::GetInstance() {
    333   CHECK(instance_ != NULL);
    334   return instance_;
    335 }
    336 
    337 void ConflictType::Destroy() {
    338   if (instance_ != NULL) {
    339     delete instance_;
    340     instance_ = NULL;
    341   }
    342 }
    343 
    344 BooleanType* BooleanType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
    345                                          uint16_t cache_id) {
    346   if (BooleanType::instance == NULL) {
    347     instance = new BooleanType(klass, descriptor, cache_id);
    348   }
    349   return BooleanType::instance;
    350 }
    351 
    352 BooleanType* BooleanType::GetInstance() {
    353   CHECK(BooleanType::instance != NULL);
    354   return BooleanType::instance;
    355 }
    356 
    357 void BooleanType::Destroy() {
    358   if (BooleanType::instance != NULL) {
    359     delete instance;
    360     instance = NULL;
    361   }
    362 }
    363 
    364 std::string UndefinedType::Dump() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
    365   return "Undefined";
    366 }
    367 
    368 UndefinedType* UndefinedType::CreateInstance(mirror::Class* klass, const std::string& descriptor,
    369                                              uint16_t cache_id) {
    370   if (instance_ == NULL) {
    371     instance_ = new UndefinedType(klass, descriptor, cache_id);
    372   }
    373   return instance_;
    374 }
    375 
    376 UndefinedType* UndefinedType::GetInstance() {
    377   CHECK(instance_ != NULL);
    378   return instance_;
    379 }
    380 
    381 void UndefinedType::Destroy() {
    382   if (instance_ != NULL) {
    383     delete instance_;
    384     instance_ = NULL;
    385   }
    386 }
    387 
    388 PreciseReferenceType::PreciseReferenceType(mirror::Class* klass, const std::string& descriptor,
    389                                            uint16_t cache_id)
    390     : RegType(klass, descriptor, cache_id) {
    391   DCHECK(klass->IsInstantiable());
    392 }
    393 
    394 std::string UnresolvedMergedType::Dump() {
    395   std::stringstream result;
    396   std::set<uint16_t> types = GetMergedTypes();
    397   result << "UnresolvedMergedReferences(";
    398   auto it = types.begin();
    399   result << reg_type_cache_->GetFromId(*it).Dump();
    400   for (++it; it != types.end(); ++it) {
    401     result << ", ";
    402     result << reg_type_cache_->GetFromId(*it).Dump();
    403   }
    404   result << ")";
    405   return result.str();
    406 }
    407 
    408 std::string UnresolvedSuperClass::Dump() {
    409   std::stringstream result;
    410   uint16_t super_type_id = GetUnresolvedSuperClassChildId();
    411   result << "UnresolvedSuperClass(" << reg_type_cache_->GetFromId(super_type_id).Dump() << ")";
    412   return result.str();
    413 }
    414 
    415 std::string UnresolvedReferenceType::Dump() {
    416   std::stringstream result;
    417   result << "Unresolved Reference" << ": " << PrettyDescriptor(GetDescriptor().c_str());
    418   return result.str();
    419 }
    420 
    421 std::string UnresolvedUninitializedRefType::Dump() {
    422   std::stringstream result;
    423   result << "Unresolved And Uninitialized Reference" << ": "
    424       << PrettyDescriptor(GetDescriptor().c_str())
    425       << " Allocation PC: " << GetAllocationPc();
    426   return result.str();
    427 }
    428 
    429 std::string UnresolvedUninitializedThisRefType::Dump() {
    430   std::stringstream result;
    431   result << "Unresolved And Uninitialized This Reference"
    432       << PrettyDescriptor(GetDescriptor().c_str());
    433   return result.str();
    434 }
    435 
    436 std::string ReferenceType::Dump() {
    437   std::stringstream result;
    438   result << "Reference" << ": " << PrettyDescriptor(GetClass());
    439   return result.str();
    440 }
    441 
    442 std::string PreciseReferenceType::Dump() {
    443   std::stringstream result;
    444   result << "Precise Reference" << ": "<< PrettyDescriptor(GetClass());
    445   return result.str();
    446 }
    447 
    448 std::string UninitializedReferenceType::Dump() {
    449   std::stringstream result;
    450   result << "Uninitialized Reference" << ": " << PrettyDescriptor(GetClass());
    451   result << " Allocation PC: " << GetAllocationPc();
    452   return result.str();
    453 }
    454 
    455 std::string UninitializedThisReferenceType::Dump() {
    456   std::stringstream result;
    457   result << "Uninitialized This Reference" << ": " << PrettyDescriptor(GetClass());
    458   result << "Allocation PC: " << GetAllocationPc();
    459   return result.str();
    460 }
    461 
    462 std::string ImpreciseConstType::Dump() {
    463   std::stringstream result;
    464   uint32_t val = ConstantValue();
    465   if (val == 0) {
    466     result << "Zero/null";
    467   } else {
    468     result << "Imprecise ";
    469     if (IsConstantShort()) {
    470       result << StringPrintf("Constant: %d", val);
    471     } else {
    472       result << StringPrintf("Constant: 0x%x", val);
    473     }
    474   }
    475   return result.str();
    476 }
    477 std::string PreciseConstLoType::Dump() {
    478   std::stringstream result;
    479 
    480   int32_t val = ConstantValueLo();
    481   result << "Precise ";
    482   if (val >= std::numeric_limits<jshort>::min() &&
    483       val <= std::numeric_limits<jshort>::max()) {
    484     result << StringPrintf("Low-half Constant: %d", val);
    485   } else {
    486     result << StringPrintf("Low-half Constant: 0x%x", val);
    487   }
    488   return result.str();
    489 }
    490 
    491 std::string ImpreciseConstLoType::Dump() {
    492   std::stringstream result;
    493 
    494   int32_t val = ConstantValueLo();
    495   result << "Imprecise ";
    496   if (val >= std::numeric_limits<jshort>::min() &&
    497       val <= std::numeric_limits<jshort>::max()) {
    498     result << StringPrintf("Low-half Constant: %d", val);
    499   } else {
    500     result << StringPrintf("Low-half Constant: 0x%x", val);
    501   }
    502   return result.str();
    503 }
    504 
    505 std::string PreciseConstHiType::Dump() {
    506   std::stringstream result;
    507   int32_t val = ConstantValueHi();
    508   result << "Precise ";
    509   if (val >= std::numeric_limits<jshort>::min() &&
    510       val <= std::numeric_limits<jshort>::max()) {
    511     result << StringPrintf("High-half Constant: %d", val);
    512   } else {
    513     result << StringPrintf("High-half Constant: 0x%x", val);
    514   }
    515   return result.str();
    516 }
    517 
    518 std::string ImpreciseConstHiType::Dump() {
    519   std::stringstream result;
    520   int32_t val = ConstantValueHi();
    521   result << "Imprecise ";
    522   if (val >= std::numeric_limits<jshort>::min() &&
    523       val <= std::numeric_limits<jshort>::max()) {
    524     result << StringPrintf("High-half Constant: %d", val);
    525   } else {
    526     result << StringPrintf("High-half Constant: 0x%x", val);
    527   }
    528   return result.str();
    529 }
    530 
    531 ConstantType::ConstantType(uint32_t constant, uint16_t cache_id)
    532     : RegType(NULL, "", cache_id), constant_(constant) {
    533 }
    534 
    535 RegType& UndefinedType::Merge(RegType& incoming_type, RegTypeCache* reg_types)
    536     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
    537   if (incoming_type.IsUndefined()) {
    538     return *this;  // Undefined MERGE Undefined => Undefined
    539   }
    540   return reg_types->Conflict();
    541 }
    542 
    543 RegType& RegType::HighHalf(RegTypeCache* cache) const {
    544   DCHECK(IsLowHalf());
    545   if (IsLongLo()) {
    546     return cache->LongHi();
    547   } else if (IsDoubleLo()) {
    548     return cache->DoubleHi();
    549   } else {
    550     DCHECK(IsImpreciseConstantLo());
    551     return cache->FromCat2ConstHi(ConstantValue(), false);
    552   }
    553 }
    554 
    555 Primitive::Type RegType::GetPrimitiveType() const {
    556   if (IsNonZeroReferenceTypes()) {
    557     return Primitive::kPrimNot;
    558   } else if (IsBooleanTypes()) {
    559     return Primitive::kPrimBoolean;
    560   } else if (IsByteTypes()) {
    561     return Primitive::kPrimByte;
    562   } else if (IsShortTypes()) {
    563     return Primitive::kPrimShort;
    564   } else if (IsCharTypes()) {
    565     return Primitive::kPrimChar;
    566   } else if (IsFloat()) {
    567     return Primitive::kPrimFloat;
    568   } else if (IsIntegralTypes()) {
    569     return Primitive::kPrimInt;
    570   } else if (IsDoubleLo()) {
    571     return Primitive::kPrimDouble;
    572   } else {
    573     DCHECK(IsLongTypes());
    574     return Primitive::kPrimLong;
    575   }
    576 }
    577 
    578 bool UninitializedType::IsUninitializedTypes() const {
    579   return true;
    580 }
    581 
    582 bool UninitializedType::IsNonZeroReferenceTypes() const {
    583   return true;
    584 }
    585 
    586 bool UnresolvedType::IsNonZeroReferenceTypes() const {
    587   return true;
    588 }
    589 std::set<uint16_t> UnresolvedMergedType::GetMergedTypes() const {
    590   std::pair<uint16_t, uint16_t> refs = GetTopMergedTypes();
    591   RegType& _left(reg_type_cache_->GetFromId(refs.first));
    592   UnresolvedMergedType* left = down_cast<UnresolvedMergedType*>(&_left);
    593 
    594   RegType& _right(reg_type_cache_->GetFromId(refs.second));
    595   UnresolvedMergedType* right = down_cast<UnresolvedMergedType*>(&_right);
    596 
    597   std::set<uint16_t> types;
    598   if (left->IsUnresolvedMergedReference()) {
    599     types = left->GetMergedTypes();
    600   } else {
    601     types.insert(refs.first);
    602   }
    603   if (right->IsUnresolvedMergedReference()) {
    604     std::set<uint16_t> right_types = right->GetMergedTypes();
    605     types.insert(right_types.begin(), right_types.end());
    606   } else {
    607     types.insert(refs.second);
    608   }
    609   if (kIsDebugBuild) {
    610     for (const auto& type : types) {
    611       CHECK(!reg_type_cache_->GetFromId(type).IsUnresolvedMergedReference());
    612     }
    613   }
    614   return types;
    615 }
    616 
    617 RegType& RegType::GetSuperClass(RegTypeCache* cache) {
    618   if (!IsUnresolvedTypes()) {
    619     mirror::Class* super_klass = GetClass()->GetSuperClass();
    620     if (super_klass != NULL) {
    621       // A super class of a precise type isn't precise as a precise type indicates the register
    622       // holds exactly that type.
    623       std::string temp;
    624       return cache->FromClass(super_klass->GetDescriptor(&temp), super_klass, false);
    625     } else {
    626       return cache->Zero();
    627     }
    628   } else {
    629     if (!IsUnresolvedMergedReference() && !IsUnresolvedSuperClass() &&
    630         GetDescriptor()[0] == '[') {
    631       // Super class of all arrays is Object.
    632       return cache->JavaLangObject(true);
    633     } else {
    634       return cache->FromUnresolvedSuperClass(*this);
    635     }
    636   }
    637 }
    638 
    639 bool RegType::CanAccess(RegType& other) {
    640   if (Equals(other)) {
    641     return true;  // Trivial accessibility.
    642   } else {
    643     bool this_unresolved = IsUnresolvedTypes();
    644     bool other_unresolved = other.IsUnresolvedTypes();
    645     if (!this_unresolved && !other_unresolved) {
    646       return GetClass()->CanAccess(other.GetClass());
    647     } else if (!other_unresolved) {
    648       return other.GetClass()->IsPublic();  // Be conservative, only allow if other is public.
    649     } else {
    650       return false;  // More complicated test not possible on unresolved types, be conservative.
    651     }
    652   }
    653 }
    654 
    655 bool RegType::CanAccessMember(mirror::Class* klass, uint32_t access_flags) {
    656   if ((access_flags & kAccPublic) != 0) {
    657     return true;
    658   }
    659   if (!IsUnresolvedTypes()) {
    660     return GetClass()->CanAccessMember(klass, access_flags);
    661   } else {
    662     return false;  // More complicated test not possible on unresolved types, be conservative.
    663   }
    664 }
    665 
    666 bool RegType::IsObjectArrayTypes() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
    667   if (IsUnresolvedTypes() && !IsUnresolvedMergedReference() && !IsUnresolvedSuperClass()) {
    668     // Primitive arrays will always resolve
    669     DCHECK(descriptor_[1] == 'L' || descriptor_[1] == '[');
    670     return descriptor_[0] == '[';
    671   } else if (HasClass()) {
    672     mirror::Class* type = GetClass();
    673     return type->IsArrayClass() && !type->GetComponentType()->IsPrimitive();
    674   } else {
    675     return false;
    676   }
    677 }
    678 
    679 bool RegType::IsJavaLangObject() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
    680   return IsReference() && GetClass()->IsObjectClass();
    681 }
    682 
    683 bool RegType::IsArrayTypes() SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
    684   if (IsUnresolvedTypes() && !IsUnresolvedMergedReference() && !IsUnresolvedSuperClass()) {
    685     return descriptor_[0] == '[';
    686   } else if (HasClass()) {
    687     return GetClass()->IsArrayClass();
    688   } else {
    689     return false;
    690   }
    691 }
    692 
    693 bool RegType::IsJavaLangObjectArray() {
    694   if (HasClass()) {
    695     mirror::Class* type = GetClass();
    696     return type->IsArrayClass() && type->GetComponentType()->IsObjectClass();
    697   }
    698   return false;
    699 }
    700 
    701 bool RegType::IsInstantiableTypes() {
    702   return IsUnresolvedTypes() || (IsNonZeroReferenceTypes() && GetClass()->IsInstantiable());
    703 }
    704 
    705 ImpreciseConstType::ImpreciseConstType(uint32_t constat, uint16_t cache_id)
    706   : ConstantType(constat, cache_id) {
    707 }
    708 
    709 static bool AssignableFrom(RegType& lhs, RegType& rhs, bool strict)
    710     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
    711   if (lhs.Equals(rhs)) {
    712     return true;
    713   } else {
    714     if (lhs.IsBoolean()) {
    715       return rhs.IsBooleanTypes();
    716     } else if (lhs.IsByte()) {
    717       return rhs.IsByteTypes();
    718     } else if (lhs.IsShort()) {
    719       return rhs.IsShortTypes();
    720     } else if (lhs.IsChar()) {
    721       return rhs.IsCharTypes();
    722     } else if (lhs.IsInteger()) {
    723       return rhs.IsIntegralTypes();
    724     } else if (lhs.IsFloat()) {
    725       return rhs.IsFloatTypes();
    726     } else if (lhs.IsLongLo()) {
    727       return rhs.IsLongTypes();
    728     } else if (lhs.IsDoubleLo()) {
    729       return rhs.IsDoubleTypes();
    730     } else {
    731       CHECK(lhs.IsReferenceTypes())
    732           << "Unexpected register type in IsAssignableFrom: '"
    733           << lhs << "' := '" << rhs << "'";
    734       if (rhs.IsZero()) {
    735         return true;  // All reference types can be assigned null.
    736       } else if (!rhs.IsReferenceTypes()) {
    737         return false;  // Expect rhs to be a reference type.
    738       } else if (lhs.IsJavaLangObject()) {
    739         return true;  // All reference types can be assigned to Object.
    740       } else if (!strict && !lhs.IsUnresolvedTypes() && lhs.GetClass()->IsInterface()) {
    741         // If we're not strict allow assignment to any interface, see comment in ClassJoin.
    742         return true;
    743       } else if (lhs.IsJavaLangObjectArray()) {
    744         return rhs.IsObjectArrayTypes();  // All reference arrays may be assigned to Object[]
    745       } else if (lhs.HasClass() && rhs.HasClass() &&
    746                  lhs.GetClass()->IsAssignableFrom(rhs.GetClass())) {
    747         // We're assignable from the Class point-of-view.
    748         return true;
    749       } else {
    750         // Unresolved types are only assignable for null and equality.
    751         return false;
    752       }
    753     }
    754   }
    755 }
    756 
    757 bool RegType::IsAssignableFrom(RegType& src) {
    758   return AssignableFrom(*this, src, false);
    759 }
    760 
    761 bool RegType::IsStrictlyAssignableFrom(RegType& src) {
    762   return AssignableFrom(*this, src, true);
    763 }
    764 
    765 int32_t ConstantType::ConstantValueLo() const {
    766   DCHECK(IsConstantLo());
    767   return constant_;
    768 }
    769 
    770 int32_t ConstantType::ConstantValueHi() const {
    771   if (IsConstantHi() || IsPreciseConstantHi() || IsImpreciseConstantHi()) {
    772     return constant_;
    773   } else {
    774     DCHECK(false);
    775     return 0;
    776   }
    777 }
    778 
    779 static RegType& SelectNonConstant(RegType& a, RegType& b) {
    780   return a.IsConstantTypes() ? b : a;
    781 }
    782 
    783 RegType& RegType::Merge(RegType& incoming_type, RegTypeCache* reg_types) {
    784   DCHECK(!Equals(incoming_type));  // Trivial equality handled by caller
    785   if (IsConflict()) {
    786     return *this;  // Conflict MERGE * => Conflict
    787   } else if (incoming_type.IsConflict()) {
    788     return incoming_type;  // * MERGE Conflict => Conflict
    789   } else if (IsUndefined() || incoming_type.IsUndefined()) {
    790     return reg_types->Conflict();  // Unknown MERGE * => Conflict
    791   } else if (IsConstant() && incoming_type.IsConstant()) {
    792     int32_t val1 = ConstantValue();
    793     int32_t val2 = incoming_type.ConstantValue();
    794     if (val1 >= 0 && val2 >= 0) {
    795       // +ve1 MERGE +ve2 => MAX(+ve1, +ve2)
    796       if (val1 >= val2) {
    797         if (!IsPreciseConstant()) {
    798           return *this;
    799         } else {
    800           return reg_types->FromCat1Const(val1, false);
    801         }
    802       } else {
    803         if (!incoming_type.IsPreciseConstant()) {
    804           return incoming_type;
    805         } else {
    806           return reg_types->FromCat1Const(val2, false);
    807         }
    808       }
    809     } else if (val1 < 0 && val2 < 0) {
    810       // -ve1 MERGE -ve2 => MIN(-ve1, -ve2)
    811       if (val1 <= val2) {
    812         if (!IsPreciseConstant()) {
    813           return *this;
    814         } else {
    815           return reg_types->FromCat1Const(val1, false);
    816         }
    817       } else {
    818         if (!incoming_type.IsPreciseConstant()) {
    819           return incoming_type;
    820         } else {
    821           return reg_types->FromCat1Const(val2, false);
    822         }
    823       }
    824     } else {
    825       // Values are +ve and -ve, choose smallest signed type in which they both fit
    826       if (IsConstantByte()) {
    827         if (incoming_type.IsConstantByte()) {
    828           return reg_types->ByteConstant();
    829         } else if (incoming_type.IsConstantShort()) {
    830           return reg_types->ShortConstant();
    831         } else {
    832           return reg_types->IntConstant();
    833         }
    834       } else if (IsConstantShort()) {
    835         if (incoming_type.IsConstantShort()) {
    836           return reg_types->ShortConstant();
    837         } else {
    838           return reg_types->IntConstant();
    839         }
    840       } else {
    841         return reg_types->IntConstant();
    842       }
    843     }
    844   } else if (IsConstantLo() && incoming_type.IsConstantLo()) {
    845     int32_t val1 = ConstantValueLo();
    846     int32_t val2 = incoming_type.ConstantValueLo();
    847     return reg_types->FromCat2ConstLo(val1 | val2, false);
    848   } else if (IsConstantHi() && incoming_type.IsConstantHi()) {
    849     int32_t val1 = ConstantValueHi();
    850     int32_t val2 = incoming_type.ConstantValueHi();
    851     return reg_types->FromCat2ConstHi(val1 | val2, false);
    852   } else if (IsIntegralTypes() && incoming_type.IsIntegralTypes()) {
    853     if (IsBooleanTypes() && incoming_type.IsBooleanTypes()) {
    854       return reg_types->Boolean();  // boolean MERGE boolean => boolean
    855     }
    856     if (IsByteTypes() && incoming_type.IsByteTypes()) {
    857       return reg_types->Byte();  // byte MERGE byte => byte
    858     }
    859     if (IsShortTypes() && incoming_type.IsShortTypes()) {
    860       return reg_types->Short();  // short MERGE short => short
    861     }
    862     if (IsCharTypes() && incoming_type.IsCharTypes()) {
    863       return reg_types->Char();  // char MERGE char => char
    864     }
    865     return reg_types->Integer();  // int MERGE * => int
    866   } else if ((IsFloatTypes() && incoming_type.IsFloatTypes()) ||
    867              (IsLongTypes() && incoming_type.IsLongTypes()) ||
    868              (IsLongHighTypes() && incoming_type.IsLongHighTypes()) ||
    869              (IsDoubleTypes() && incoming_type.IsDoubleTypes()) ||
    870              (IsDoubleHighTypes() && incoming_type.IsDoubleHighTypes())) {
    871     // check constant case was handled prior to entry
    872     DCHECK(!IsConstant() || !incoming_type.IsConstant());
    873     // float/long/double MERGE float/long/double_constant => float/long/double
    874     return SelectNonConstant(*this, incoming_type);
    875   } else if (IsReferenceTypes() && incoming_type.IsReferenceTypes()) {
    876     if (IsZero() || incoming_type.IsZero()) {
    877       return SelectNonConstant(*this, incoming_type);  // 0 MERGE ref => ref
    878     } else if (IsJavaLangObject() || incoming_type.IsJavaLangObject()) {
    879       return reg_types->JavaLangObject(false);  // Object MERGE ref => Object
    880     } else if (IsUnresolvedTypes() || incoming_type.IsUnresolvedTypes()) {
    881       // We know how to merge an unresolved type with itself, 0 or Object. In this case we
    882       // have two sub-classes and don't know how to merge. Create a new string-based unresolved
    883       // type that reflects our lack of knowledge and that allows the rest of the unresolved
    884       // mechanics to continue.
    885       return reg_types->FromUnresolvedMerge(*this, incoming_type);
    886     } else if (IsUninitializedTypes() || incoming_type.IsUninitializedTypes()) {
    887       // Something that is uninitialized hasn't had its constructor called. Mark any merge
    888       // of this type with something that is initialized as conflicting. The cases of a merge
    889       // with itself, 0 or Object are handled above.
    890       return reg_types->Conflict();
    891     } else {  // Two reference types, compute Join
    892       mirror::Class* c1 = GetClass();
    893       mirror::Class* c2 = incoming_type.GetClass();
    894       DCHECK(c1 != NULL && !c1->IsPrimitive());
    895       DCHECK(c2 != NULL && !c2->IsPrimitive());
    896       mirror::Class* join_class = ClassJoin(c1, c2);
    897       if (c1 == join_class && !IsPreciseReference()) {
    898         return *this;
    899       } else if (c2 == join_class && !incoming_type.IsPreciseReference()) {
    900         return incoming_type;
    901       } else {
    902         std::string temp;
    903         return reg_types->FromClass(join_class->GetDescriptor(&temp), join_class, false);
    904       }
    905     }
    906   } else {
    907     return reg_types->Conflict();  // Unexpected types => Conflict
    908   }
    909 }
    910 
    911 // See comment in reg_type.h
    912 mirror::Class* RegType::ClassJoin(mirror::Class* s, mirror::Class* t) {
    913   DCHECK(!s->IsPrimitive()) << PrettyClass(s);
    914   DCHECK(!t->IsPrimitive()) << PrettyClass(t);
    915   if (s == t) {
    916     return s;
    917   } else if (s->IsAssignableFrom(t)) {
    918     return s;
    919   } else if (t->IsAssignableFrom(s)) {
    920     return t;
    921   } else if (s->IsArrayClass() && t->IsArrayClass()) {
    922     mirror::Class* s_ct = s->GetComponentType();
    923     mirror::Class* t_ct = t->GetComponentType();
    924     if (s_ct->IsPrimitive() || t_ct->IsPrimitive()) {
    925       // Given the types aren't the same, if either array is of primitive types then the only
    926       // common parent is java.lang.Object
    927       mirror::Class* result = s->GetSuperClass();  // short-cut to java.lang.Object
    928       DCHECK(result->IsObjectClass());
    929       return result;
    930     }
    931     mirror::Class* common_elem = ClassJoin(s_ct, t_ct);
    932     ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
    933     mirror::Class* array_class = class_linker->FindArrayClass(Thread::Current(), &common_elem);
    934     DCHECK(array_class != NULL);
    935     return array_class;
    936   } else {
    937     size_t s_depth = s->Depth();
    938     size_t t_depth = t->Depth();
    939     // Get s and t to the same depth in the hierarchy
    940     if (s_depth > t_depth) {
    941       while (s_depth > t_depth) {
    942         s = s->GetSuperClass();
    943         s_depth--;
    944       }
    945     } else {
    946       while (t_depth > s_depth) {
    947         t = t->GetSuperClass();
    948         t_depth--;
    949       }
    950     }
    951     // Go up the hierarchy until we get to the common parent
    952     while (s != t) {
    953       s = s->GetSuperClass();
    954       t = t->GetSuperClass();
    955     }
    956     return s;
    957   }
    958 }
    959 
    960 void RegType::CheckInvariants() const {
    961   if (IsConstant() || IsConstantLo() || IsConstantHi()) {
    962     CHECK(descriptor_.empty()) << *this;
    963     CHECK(klass_.IsNull()) << *this;
    964   }
    965   if (!klass_.IsNull()) {
    966     CHECK(!descriptor_.empty()) << *this;
    967   }
    968 }
    969 
    970 void RegType::VisitRoots(RootCallback* callback, void* arg) {
    971   klass_.VisitRootIfNonNull(callback, arg, RootInfo(kRootUnknown));
    972 }
    973 
    974 void UninitializedThisReferenceType::CheckInvariants() const {
    975   CHECK_EQ(GetAllocationPc(), 0U) << *this;
    976 }
    977 
    978 void UnresolvedUninitializedThisRefType::CheckInvariants() const {
    979   CHECK_EQ(GetAllocationPc(), 0U) << *this;
    980   CHECK(!descriptor_.empty()) << *this;
    981   CHECK(klass_.IsNull()) << *this;
    982 }
    983 
    984 void UnresolvedUninitializedRefType::CheckInvariants() const {
    985   CHECK(!descriptor_.empty()) << *this;
    986   CHECK(klass_.IsNull()) << *this;
    987 }
    988 
    989 void UnresolvedMergedType::CheckInvariants() const {
    990   // Unresolved merged types: merged types should be defined.
    991   CHECK(descriptor_.empty()) << *this;
    992   CHECK(klass_.IsNull()) << *this;
    993   CHECK_NE(merged_types_.first, 0U) << *this;
    994   CHECK_NE(merged_types_.second, 0U) << *this;
    995 }
    996 
    997 void UnresolvedReferenceType::CheckInvariants() const {
    998   CHECK(!descriptor_.empty()) << *this;
    999   CHECK(klass_.IsNull()) << *this;
   1000 }
   1001 
   1002 void UnresolvedSuperClass::CheckInvariants() const {
   1003   // Unresolved merged types: merged types should be defined.
   1004   CHECK(descriptor_.empty()) << *this;
   1005   CHECK(klass_.IsNull()) << *this;
   1006   CHECK_NE(unresolved_child_id_, 0U) << *this;
   1007 }
   1008 
   1009 std::ostream& operator<<(std::ostream& os, const RegType& rhs) {
   1010   RegType& rhs_non_const = const_cast<RegType&>(rhs);
   1011   os << rhs_non_const.Dump();
   1012   return os;
   1013 }
   1014 
   1015 }  // namespace verifier
   1016 }  // namespace art
   1017