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 #ifndef ART_RUNTIME_VERIFIER_REG_TYPE_H_
     18 #define ART_RUNTIME_VERIFIER_REG_TYPE_H_
     19 
     20 #include <stdint.h>
     21 #include <limits>
     22 #include <set>
     23 #include <string>
     24 
     25 #include "base/arena_object.h"
     26 #include "base/bit_vector.h"
     27 #include "base/macros.h"
     28 #include "base/mutex.h"
     29 #include "base/stringpiece.h"
     30 #include "dex/primitive.h"
     31 #include "gc_root.h"
     32 #include "handle_scope.h"
     33 #include "obj_ptr.h"
     34 
     35 namespace art {
     36 namespace mirror {
     37 class Class;
     38 class ClassLoader;
     39 }  // namespace mirror
     40 
     41 class ArenaBitVector;
     42 class ScopedArenaAllocator;
     43 
     44 namespace verifier {
     45 
     46 class MethodVerifier;
     47 class RegTypeCache;
     48 
     49 /*
     50  * RegType holds information about the "type" of data held in a register.
     51  */
     52 class RegType {
     53  public:
     54   virtual bool IsUndefined() const { return false; }
     55   virtual bool IsConflict() const { return false; }
     56   virtual bool IsBoolean() const { return false; }
     57   virtual bool IsByte() const { return false; }
     58   virtual bool IsChar() const { return false; }
     59   virtual bool IsShort() const { return false; }
     60   virtual bool IsInteger() const { return false; }
     61   virtual bool IsLongLo() const { return false; }
     62   virtual bool IsLongHi() const { return false; }
     63   virtual bool IsFloat() const { return false; }
     64   virtual bool IsDouble() const { return false; }
     65   virtual bool IsDoubleLo() const { return false; }
     66   virtual bool IsDoubleHi() const { return false; }
     67   virtual bool IsUnresolvedReference() const { return false; }
     68   virtual bool IsUninitializedReference() const { return false; }
     69   virtual bool IsUninitializedThisReference() const { return false; }
     70   virtual bool IsUnresolvedAndUninitializedReference() const { return false; }
     71   virtual bool IsUnresolvedAndUninitializedThisReference() const {
     72     return false;
     73   }
     74   virtual bool IsUnresolvedMergedReference() const { return false; }
     75   virtual bool IsUnresolvedSuperClass() const { return false; }
     76   virtual bool IsReference() const { return false; }
     77   virtual bool IsPreciseReference() const { return false; }
     78   virtual bool IsPreciseConstant() const { return false; }
     79   virtual bool IsPreciseConstantLo() const { return false; }
     80   virtual bool IsPreciseConstantHi() const { return false; }
     81   virtual bool IsImpreciseConstantLo() const { return false; }
     82   virtual bool IsImpreciseConstantHi() const { return false; }
     83   virtual bool IsImpreciseConstant() const { return false; }
     84   virtual bool IsConstantTypes() const { return false; }
     85   bool IsConstant() const {
     86     return IsImpreciseConstant() || IsPreciseConstant();
     87   }
     88   bool IsConstantLo() const {
     89     return IsImpreciseConstantLo() || IsPreciseConstantLo();
     90   }
     91   bool IsPrecise() const {
     92     return IsPreciseConstantLo() || IsPreciseConstant() ||
     93            IsPreciseConstantHi();
     94   }
     95   bool IsLongConstant() const { return IsConstantLo(); }
     96   bool IsConstantHi() const {
     97     return (IsPreciseConstantHi() || IsImpreciseConstantHi());
     98   }
     99   bool IsLongConstantHigh() const { return IsConstantHi(); }
    100   virtual bool IsUninitializedTypes() const { return false; }
    101   virtual bool IsUnresolvedTypes() const { return false; }
    102 
    103   bool IsLowHalf() const {
    104     return (IsLongLo() || IsDoubleLo() || IsPreciseConstantLo() || IsImpreciseConstantLo());
    105   }
    106   bool IsHighHalf() const {
    107     return (IsLongHi() || IsDoubleHi() || IsPreciseConstantHi() || IsImpreciseConstantHi());
    108   }
    109   bool IsLongOrDoubleTypes() const { return IsLowHalf(); }
    110   // Check this is the low half, and that type_h is its matching high-half.
    111   inline bool CheckWidePair(const RegType& type_h) const {
    112     if (IsLowHalf()) {
    113       return ((IsImpreciseConstantLo() && type_h.IsPreciseConstantHi()) ||
    114               (IsImpreciseConstantLo() && type_h.IsImpreciseConstantHi()) ||
    115               (IsPreciseConstantLo() && type_h.IsPreciseConstantHi()) ||
    116               (IsPreciseConstantLo() && type_h.IsImpreciseConstantHi()) ||
    117               (IsDoubleLo() && type_h.IsDoubleHi()) ||
    118               (IsLongLo() && type_h.IsLongHi()));
    119     }
    120     return false;
    121   }
    122   // The high half that corresponds to this low half
    123   const RegType& HighHalf(RegTypeCache* cache) const
    124       REQUIRES_SHARED(Locks::mutator_lock_);
    125 
    126   bool IsConstantBoolean() const;
    127   virtual bool IsConstantChar() const { return false; }
    128   virtual bool IsConstantByte() const { return false; }
    129   virtual bool IsConstantShort() const { return false; }
    130   virtual bool IsOne() const { return false; }
    131   virtual bool IsZero() const { return false; }
    132   virtual bool IsNull() const { return false; }
    133   bool IsReferenceTypes() const {
    134     return IsNonZeroReferenceTypes() || IsZero() || IsNull();
    135   }
    136   bool IsZeroOrNull() const {
    137     return IsZero() || IsNull();
    138   }
    139   virtual bool IsNonZeroReferenceTypes() const { return false; }
    140   bool IsCategory1Types() const {
    141     return IsChar() || IsInteger() || IsFloat() || IsConstant() || IsByte() ||
    142            IsShort() || IsBoolean();
    143   }
    144   bool IsCategory2Types() const {
    145     return IsLowHalf();  // Don't expect explicit testing of high halves
    146   }
    147   bool IsBooleanTypes() const { return IsBoolean() || IsConstantBoolean(); }
    148   bool IsByteTypes() const {
    149     return IsConstantByte() || IsByte() || IsBoolean();
    150   }
    151   bool IsShortTypes() const {
    152     return IsShort() || IsByte() || IsBoolean() || IsConstantShort();
    153   }
    154   bool IsCharTypes() const {
    155     return IsChar() || IsBooleanTypes() || IsConstantChar();
    156   }
    157   bool IsIntegralTypes() const {
    158     return IsInteger() || IsConstant() || IsByte() || IsShort() || IsChar() ||
    159            IsBoolean();
    160   }
    161   // Give the constant value encoded, but this shouldn't be called in the
    162   // general case.
    163   bool IsArrayIndexTypes() const { return IsIntegralTypes(); }
    164   // Float type may be derived from any constant type
    165   bool IsFloatTypes() const { return IsFloat() || IsConstant(); }
    166   bool IsLongTypes() const { return IsLongLo() || IsLongConstant(); }
    167   bool IsLongHighTypes() const {
    168     return (IsLongHi() || IsPreciseConstantHi() || IsImpreciseConstantHi());
    169   }
    170   bool IsDoubleTypes() const { return IsDoubleLo() || IsLongConstant(); }
    171   bool IsDoubleHighTypes() const {
    172     return (IsDoubleHi() || IsPreciseConstantHi() || IsImpreciseConstantHi());
    173   }
    174   virtual bool IsLong() const { return false; }
    175   bool HasClass() const {
    176     bool result = !klass_.IsNull();
    177     DCHECK_EQ(result, HasClassVirtual());
    178     return result;
    179   }
    180   virtual bool HasClassVirtual() const { return false; }
    181   bool IsJavaLangObject() const REQUIRES_SHARED(Locks::mutator_lock_);
    182   virtual bool IsArrayTypes() const REQUIRES_SHARED(Locks::mutator_lock_);
    183   virtual bool IsObjectArrayTypes() const REQUIRES_SHARED(Locks::mutator_lock_);
    184   Primitive::Type GetPrimitiveType() const;
    185   bool IsJavaLangObjectArray() const
    186       REQUIRES_SHARED(Locks::mutator_lock_);
    187   bool IsInstantiableTypes() const REQUIRES_SHARED(Locks::mutator_lock_);
    188   const StringPiece& GetDescriptor() const {
    189     DCHECK(HasClass() ||
    190            (IsUnresolvedTypes() && !IsUnresolvedMergedReference() &&
    191             !IsUnresolvedSuperClass()));
    192     return descriptor_;
    193   }
    194   mirror::Class* GetClass() const REQUIRES_SHARED(Locks::mutator_lock_) {
    195     DCHECK(!IsUnresolvedReference());
    196     DCHECK(!klass_.IsNull()) << Dump();
    197     DCHECK(HasClass());
    198     return klass_.Read();
    199   }
    200   uint16_t GetId() const { return cache_id_; }
    201   const RegType& GetSuperClass(RegTypeCache* cache) const
    202       REQUIRES_SHARED(Locks::mutator_lock_);
    203 
    204   virtual std::string Dump() const
    205       REQUIRES_SHARED(Locks::mutator_lock_) = 0;
    206 
    207   // Can this type access other?
    208   bool CanAccess(const RegType& other) const
    209       REQUIRES_SHARED(Locks::mutator_lock_);
    210 
    211   // Can this type access a member with the given properties?
    212   bool CanAccessMember(ObjPtr<mirror::Class> klass, uint32_t access_flags) const
    213       REQUIRES_SHARED(Locks::mutator_lock_);
    214 
    215   // Can this type be assigned by src?
    216   // Note: Object and interface types may always be assigned to one another, see
    217   // comment on
    218   // ClassJoin.
    219   bool IsAssignableFrom(const RegType& src, MethodVerifier* verifier) const
    220       REQUIRES_SHARED(Locks::mutator_lock_);
    221 
    222   // Can this array type potentially be assigned by src.
    223   // This function is necessary as array types are valid even if their components types are not,
    224   // e.g., when they component type could not be resolved. The function will return true iff the
    225   // types are assignable. It will return false otherwise. In case of return=false, soft_error
    226   // will be set to true iff the assignment test failure should be treated as a soft-error, i.e.,
    227   // when both array types have the same 'depth' and the 'final' component types may be assignable
    228   // (both are reference types).
    229   bool CanAssignArray(const RegType& src,
    230                       RegTypeCache& reg_types,
    231                       Handle<mirror::ClassLoader> class_loader,
    232                       MethodVerifier* verifier,
    233                       bool* soft_error) const
    234       REQUIRES_SHARED(Locks::mutator_lock_);
    235 
    236   // Can this type be assigned by src? Variant of IsAssignableFrom that doesn't
    237   // allow assignment to
    238   // an interface from an Object.
    239   bool IsStrictlyAssignableFrom(const RegType& src, MethodVerifier* verifier) const
    240       REQUIRES_SHARED(Locks::mutator_lock_);
    241 
    242   // Are these RegTypes the same?
    243   bool Equals(const RegType& other) const { return GetId() == other.GetId(); }
    244 
    245   // Compute the merge of this register from one edge (path) with incoming_type
    246   // from another.
    247   const RegType& Merge(const RegType& incoming_type,
    248                        RegTypeCache* reg_types,
    249                        MethodVerifier* verifier) const
    250       REQUIRES_SHARED(Locks::mutator_lock_);
    251   // Same as above, but also handles the case where incoming_type == this.
    252   const RegType& SafeMerge(const RegType& incoming_type,
    253                            RegTypeCache* reg_types,
    254                            MethodVerifier* verifier) const
    255       REQUIRES_SHARED(Locks::mutator_lock_) {
    256     if (Equals(incoming_type)) {
    257       return *this;
    258     }
    259     return Merge(incoming_type, reg_types, verifier);
    260   }
    261 
    262   virtual ~RegType() {}
    263 
    264   void VisitRoots(RootVisitor* visitor, const RootInfo& root_info) const
    265       REQUIRES_SHARED(Locks::mutator_lock_);
    266 
    267   static void* operator new(size_t size) noexcept {
    268     return ::operator new(size);
    269   }
    270 
    271   static void* operator new(size_t size, ArenaAllocator* allocator) = delete;
    272   static void* operator new(size_t size, ScopedArenaAllocator* allocator);
    273 
    274   enum class AssignmentType {
    275     kBoolean,
    276     kByte,
    277     kShort,
    278     kChar,
    279     kInteger,
    280     kFloat,
    281     kLongLo,
    282     kDoubleLo,
    283     kConflict,
    284     kReference,
    285     kNotAssignable,
    286   };
    287 
    288   ALWAYS_INLINE
    289   inline AssignmentType GetAssignmentType() const {
    290     AssignmentType t = GetAssignmentTypeImpl();
    291     if (kIsDebugBuild) {
    292       if (IsBoolean()) {
    293         CHECK(AssignmentType::kBoolean == t);
    294       } else if (IsByte()) {
    295         CHECK(AssignmentType::kByte == t);
    296       } else if (IsShort()) {
    297         CHECK(AssignmentType::kShort == t);
    298       } else if (IsChar()) {
    299         CHECK(AssignmentType::kChar == t);
    300       } else if (IsInteger()) {
    301         CHECK(AssignmentType::kInteger == t);
    302       } else if (IsFloat()) {
    303         CHECK(AssignmentType::kFloat == t);
    304       } else if (IsLongLo()) {
    305         CHECK(AssignmentType::kLongLo == t);
    306       } else if (IsDoubleLo()) {
    307         CHECK(AssignmentType::kDoubleLo == t);
    308       } else if (IsConflict()) {
    309         CHECK(AssignmentType::kConflict == t);
    310       } else if (IsReferenceTypes()) {
    311         CHECK(AssignmentType::kReference == t);
    312       } else {
    313         LOG(FATAL) << "Unreachable";
    314         UNREACHABLE();
    315       }
    316     }
    317     return t;
    318   }
    319 
    320  protected:
    321   RegType(mirror::Class* klass,
    322           const StringPiece& descriptor,
    323           uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    324       : descriptor_(descriptor),
    325         klass_(klass),
    326         cache_id_(cache_id) {}
    327 
    328   template <typename Class>
    329   void CheckConstructorInvariants(Class* this_ ATTRIBUTE_UNUSED) const
    330       REQUIRES_SHARED(Locks::mutator_lock_) {
    331     static_assert(std::is_final<Class>::value, "Class must be final.");
    332     if (kIsDebugBuild) {
    333       CheckInvariants();
    334     }
    335   }
    336 
    337   virtual AssignmentType GetAssignmentTypeImpl() const = 0;
    338 
    339   const StringPiece descriptor_;
    340   mutable GcRoot<mirror::Class> klass_;  // Non-const only due to moving classes.
    341   const uint16_t cache_id_;
    342 
    343   friend class RegTypeCache;
    344 
    345  private:
    346   virtual void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_);
    347 
    348   /*
    349    * A basic Join operation on classes. For a pair of types S and T the Join, written S v T = J, is
    350    * S <: J, T <: J and for-all U such that S <: U, T <: U then J <: U. That is J is the parent of
    351    * S and T such that there isn't a parent of both S and T that isn't also the parent of J (ie J
    352    * is the deepest (lowest upper bound) parent of S and T).
    353    *
    354    * This operation applies for regular classes and arrays, however, for interface types there
    355    * needn't be a partial ordering on the types. We could solve the problem of a lack of a partial
    356    * order by introducing sets of types, however, the only operation permissible on an interface is
    357    * invoke-interface. In the tradition of Java verifiers [1] we defer the verification of interface
    358    * types until an invoke-interface call on the interface typed reference at runtime and allow
    359    * the perversion of Object being assignable to an interface type (note, however, that we don't
    360    * allow assignment of Object or Interface to any concrete class and are therefore type safe).
    361    *
    362    * Note: This may return null in case of internal errors, e.g., OOME when a new class would have
    363    *       to be created but there is no heap space. The exception will stay pending, and it is
    364    *       the job of the caller to handle it.
    365    *
    366    * [1] Java bytecode verification: algorithms and formalizations, Xavier Leroy
    367    */
    368   static mirror::Class* ClassJoin(mirror::Class* s, mirror::Class* t)
    369       REQUIRES_SHARED(Locks::mutator_lock_);
    370 
    371   static bool AssignableFrom(const RegType& lhs,
    372                              const RegType& rhs,
    373                              bool strict,
    374                              MethodVerifier* verifier)
    375       REQUIRES_SHARED(Locks::mutator_lock_);
    376 
    377   DISALLOW_COPY_AND_ASSIGN(RegType);
    378 };
    379 
    380 // Bottom type.
    381 class ConflictType FINAL : public RegType {
    382  public:
    383   bool IsConflict() const OVERRIDE { return true; }
    384 
    385   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    386 
    387   // Get the singleton Conflict instance.
    388   static const ConflictType* GetInstance() PURE;
    389 
    390   // Create the singleton instance.
    391   static const ConflictType* CreateInstance(mirror::Class* klass,
    392                                             const StringPiece& descriptor,
    393                                             uint16_t cache_id)
    394       REQUIRES_SHARED(Locks::mutator_lock_);
    395 
    396   // Destroy the singleton instance.
    397   static void Destroy();
    398 
    399   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    400     return AssignmentType::kConflict;
    401   }
    402 
    403  private:
    404   ConflictType(mirror::Class* klass, const StringPiece& descriptor,
    405                uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    406       : RegType(klass, descriptor, cache_id) {
    407     CheckConstructorInvariants(this);
    408   }
    409 
    410   static const ConflictType* instance_;
    411 };
    412 
    413 // A variant of the bottom type used to specify an undefined value in the
    414 // incoming registers.
    415 // Merging with UndefinedType yields ConflictType which is the true bottom.
    416 class UndefinedType FINAL : public RegType {
    417  public:
    418   bool IsUndefined() const OVERRIDE { return true; }
    419 
    420   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    421 
    422   // Get the singleton Undefined instance.
    423   static const UndefinedType* GetInstance() PURE;
    424 
    425   // Create the singleton instance.
    426   static const UndefinedType* CreateInstance(mirror::Class* klass,
    427                                              const StringPiece& descriptor,
    428                                              uint16_t cache_id)
    429       REQUIRES_SHARED(Locks::mutator_lock_);
    430 
    431   // Destroy the singleton instance.
    432   static void Destroy();
    433 
    434   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    435     return AssignmentType::kNotAssignable;
    436   }
    437 
    438  private:
    439   UndefinedType(mirror::Class* klass, const StringPiece& descriptor,
    440                 uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    441       : RegType(klass, descriptor, cache_id) {
    442     CheckConstructorInvariants(this);
    443   }
    444 
    445   static const UndefinedType* instance_;
    446 };
    447 
    448 class PrimitiveType : public RegType {
    449  public:
    450   PrimitiveType(mirror::Class* klass, const StringPiece& descriptor,
    451                 uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_);
    452 
    453   bool HasClassVirtual() const OVERRIDE { return true; }
    454 };
    455 
    456 class Cat1Type : public PrimitiveType {
    457  public:
    458   Cat1Type(mirror::Class* klass, const StringPiece& descriptor,
    459            uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_);
    460 };
    461 
    462 class IntegerType FINAL : public Cat1Type {
    463  public:
    464   bool IsInteger() const OVERRIDE { return true; }
    465   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    466   static const IntegerType* CreateInstance(mirror::Class* klass,
    467                                            const StringPiece& descriptor,
    468                                            uint16_t cache_id)
    469       REQUIRES_SHARED(Locks::mutator_lock_);
    470   static const IntegerType* GetInstance() PURE;
    471   static void Destroy();
    472 
    473   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    474     return AssignmentType::kInteger;
    475   }
    476 
    477  private:
    478   IntegerType(mirror::Class* klass, const StringPiece& descriptor,
    479               uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    480       : Cat1Type(klass, descriptor, cache_id) {
    481     CheckConstructorInvariants(this);
    482   }
    483   static const IntegerType* instance_;
    484 };
    485 
    486 class BooleanType FINAL : public Cat1Type {
    487  public:
    488   bool IsBoolean() const OVERRIDE { return true; }
    489   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    490   static const BooleanType* CreateInstance(mirror::Class* klass,
    491                                            const StringPiece& descriptor,
    492                                            uint16_t cache_id)
    493       REQUIRES_SHARED(Locks::mutator_lock_);
    494   static const BooleanType* GetInstance() PURE;
    495   static void Destroy();
    496 
    497   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    498     return AssignmentType::kBoolean;
    499   }
    500 
    501  private:
    502   BooleanType(mirror::Class* klass, const StringPiece& descriptor,
    503               uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    504       : Cat1Type(klass, descriptor, cache_id) {
    505     CheckConstructorInvariants(this);
    506   }
    507 
    508   static const BooleanType* instance_;
    509 };
    510 
    511 class ByteType FINAL : public Cat1Type {
    512  public:
    513   bool IsByte() const OVERRIDE { return true; }
    514   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    515   static const ByteType* CreateInstance(mirror::Class* klass,
    516                                         const StringPiece& descriptor,
    517                                         uint16_t cache_id)
    518       REQUIRES_SHARED(Locks::mutator_lock_);
    519   static const ByteType* GetInstance() PURE;
    520   static void Destroy();
    521 
    522   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    523     return AssignmentType::kByte;
    524   }
    525 
    526  private:
    527   ByteType(mirror::Class* klass, const StringPiece& descriptor,
    528            uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    529       : Cat1Type(klass, descriptor, cache_id) {
    530     CheckConstructorInvariants(this);
    531   }
    532   static const ByteType* instance_;
    533 };
    534 
    535 class ShortType FINAL : public Cat1Type {
    536  public:
    537   bool IsShort() const OVERRIDE { return true; }
    538   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    539   static const ShortType* CreateInstance(mirror::Class* klass,
    540                                          const StringPiece& descriptor,
    541                                          uint16_t cache_id)
    542       REQUIRES_SHARED(Locks::mutator_lock_);
    543   static const ShortType* GetInstance() PURE;
    544   static void Destroy();
    545 
    546   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    547     return AssignmentType::kShort;
    548   }
    549 
    550  private:
    551   ShortType(mirror::Class* klass, const StringPiece& descriptor,
    552             uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    553       : Cat1Type(klass, descriptor, cache_id) {
    554     CheckConstructorInvariants(this);
    555   }
    556   static const ShortType* instance_;
    557 };
    558 
    559 class CharType FINAL : public Cat1Type {
    560  public:
    561   bool IsChar() const OVERRIDE { return true; }
    562   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    563   static const CharType* CreateInstance(mirror::Class* klass,
    564                                         const StringPiece& descriptor,
    565                                         uint16_t cache_id)
    566       REQUIRES_SHARED(Locks::mutator_lock_);
    567   static const CharType* GetInstance() PURE;
    568   static void Destroy();
    569 
    570   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    571     return AssignmentType::kChar;
    572   }
    573 
    574  private:
    575   CharType(mirror::Class* klass, const StringPiece& descriptor,
    576            uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    577       : Cat1Type(klass, descriptor, cache_id) {
    578     CheckConstructorInvariants(this);
    579   }
    580   static const CharType* instance_;
    581 };
    582 
    583 class FloatType FINAL : public Cat1Type {
    584  public:
    585   bool IsFloat() const OVERRIDE { return true; }
    586   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    587   static const FloatType* CreateInstance(mirror::Class* klass,
    588                                          const StringPiece& descriptor,
    589                                          uint16_t cache_id)
    590       REQUIRES_SHARED(Locks::mutator_lock_);
    591   static const FloatType* GetInstance() PURE;
    592   static void Destroy();
    593 
    594   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    595     return AssignmentType::kFloat;
    596   }
    597 
    598  private:
    599   FloatType(mirror::Class* klass, const StringPiece& descriptor,
    600             uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    601       : Cat1Type(klass, descriptor, cache_id) {
    602     CheckConstructorInvariants(this);
    603   }
    604   static const FloatType* instance_;
    605 };
    606 
    607 class Cat2Type : public PrimitiveType {
    608  public:
    609   Cat2Type(mirror::Class* klass, const StringPiece& descriptor,
    610            uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_);
    611 };
    612 
    613 class LongLoType FINAL : public Cat2Type {
    614  public:
    615   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    616   bool IsLongLo() const OVERRIDE { return true; }
    617   bool IsLong() const OVERRIDE { return true; }
    618   static const LongLoType* CreateInstance(mirror::Class* klass,
    619                                           const StringPiece& descriptor,
    620                                           uint16_t cache_id)
    621       REQUIRES_SHARED(Locks::mutator_lock_);
    622   static const LongLoType* GetInstance() PURE;
    623   static void Destroy();
    624 
    625   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    626     return AssignmentType::kLongLo;
    627   }
    628 
    629  private:
    630   LongLoType(mirror::Class* klass, const StringPiece& descriptor,
    631              uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    632       : Cat2Type(klass, descriptor, cache_id) {
    633     CheckConstructorInvariants(this);
    634   }
    635   static const LongLoType* instance_;
    636 };
    637 
    638 class LongHiType FINAL : public Cat2Type {
    639  public:
    640   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    641   bool IsLongHi() const OVERRIDE { return true; }
    642   static const LongHiType* CreateInstance(mirror::Class* klass,
    643                                           const StringPiece& descriptor,
    644                                           uint16_t cache_id)
    645       REQUIRES_SHARED(Locks::mutator_lock_);
    646   static const LongHiType* GetInstance() PURE;
    647   static void Destroy();
    648 
    649   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    650     return AssignmentType::kNotAssignable;
    651   }
    652 
    653  private:
    654   LongHiType(mirror::Class* klass, const StringPiece& descriptor,
    655              uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    656       : Cat2Type(klass, descriptor, cache_id) {
    657     CheckConstructorInvariants(this);
    658   }
    659   static const LongHiType* instance_;
    660 };
    661 
    662 class DoubleLoType FINAL : public Cat2Type {
    663  public:
    664   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    665   bool IsDoubleLo() const OVERRIDE { return true; }
    666   bool IsDouble() const OVERRIDE { return true; }
    667   static const DoubleLoType* CreateInstance(mirror::Class* klass,
    668                                             const StringPiece& descriptor,
    669                                             uint16_t cache_id)
    670       REQUIRES_SHARED(Locks::mutator_lock_);
    671   static const DoubleLoType* GetInstance() PURE;
    672   static void Destroy();
    673 
    674   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    675     return AssignmentType::kDoubleLo;
    676   }
    677 
    678  private:
    679   DoubleLoType(mirror::Class* klass, const StringPiece& descriptor,
    680                uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    681       : Cat2Type(klass, descriptor, cache_id) {
    682     CheckConstructorInvariants(this);
    683   }
    684   static const DoubleLoType* instance_;
    685 };
    686 
    687 class DoubleHiType FINAL : public Cat2Type {
    688  public:
    689   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    690   virtual bool IsDoubleHi() const OVERRIDE { return true; }
    691   static const DoubleHiType* CreateInstance(mirror::Class* klass,
    692                                       const StringPiece& descriptor,
    693                                       uint16_t cache_id)
    694       REQUIRES_SHARED(Locks::mutator_lock_);
    695   static const DoubleHiType* GetInstance() PURE;
    696   static void Destroy();
    697 
    698   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    699     return AssignmentType::kNotAssignable;
    700   }
    701 
    702  private:
    703   DoubleHiType(mirror::Class* klass, const StringPiece& descriptor,
    704                uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    705       : Cat2Type(klass, descriptor, cache_id) {
    706     CheckConstructorInvariants(this);
    707   }
    708   static const DoubleHiType* instance_;
    709 };
    710 
    711 class ConstantType : public RegType {
    712  public:
    713   ConstantType(uint32_t constant, uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
    714       : RegType(nullptr, "", cache_id), constant_(constant) {
    715   }
    716 
    717 
    718   // If this is a 32-bit constant, what is the value? This value may be
    719   // imprecise in which case
    720   // the value represents part of the integer range of values that may be held
    721   // in the register.
    722   int32_t ConstantValue() const {
    723     DCHECK(IsConstantTypes());
    724     return constant_;
    725   }
    726 
    727   int32_t ConstantValueLo() const {
    728     DCHECK(IsConstantLo());
    729     return constant_;
    730   }
    731 
    732   int32_t ConstantValueHi() const {
    733     if (IsConstantHi() || IsPreciseConstantHi() || IsImpreciseConstantHi()) {
    734       return constant_;
    735     } else {
    736       DCHECK(false);
    737       return 0;
    738     }
    739   }
    740 
    741   bool IsZero() const OVERRIDE {
    742     return IsPreciseConstant() && ConstantValue() == 0;
    743   }
    744   bool IsOne() const OVERRIDE {
    745     return IsPreciseConstant() && ConstantValue() == 1;
    746   }
    747 
    748   bool IsConstantChar() const OVERRIDE {
    749     return IsConstant() && ConstantValue() >= 0 &&
    750            ConstantValue() <= std::numeric_limits<uint16_t>::max();
    751   }
    752   bool IsConstantByte() const OVERRIDE {
    753     return IsConstant() &&
    754            ConstantValue() >= std::numeric_limits<int8_t>::min() &&
    755            ConstantValue() <= std::numeric_limits<int8_t>::max();
    756   }
    757   bool IsConstantShort() const OVERRIDE {
    758     return IsConstant() &&
    759            ConstantValue() >= std::numeric_limits<int16_t>::min() &&
    760            ConstantValue() <= std::numeric_limits<int16_t>::max();
    761   }
    762   virtual bool IsConstantTypes() const OVERRIDE { return true; }
    763 
    764   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    765     return AssignmentType::kNotAssignable;
    766   }
    767 
    768  private:
    769   const uint32_t constant_;
    770 };
    771 
    772 class PreciseConstType FINAL : public ConstantType {
    773  public:
    774   PreciseConstType(uint32_t constant, uint16_t cache_id)
    775       REQUIRES_SHARED(Locks::mutator_lock_)
    776       : ConstantType(constant, cache_id) {
    777     CheckConstructorInvariants(this);
    778   }
    779 
    780   bool IsPreciseConstant() const OVERRIDE { return true; }
    781 
    782   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    783 
    784   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    785     return AssignmentType::kNotAssignable;
    786   }
    787 };
    788 
    789 class PreciseConstLoType FINAL : public ConstantType {
    790  public:
    791   PreciseConstLoType(uint32_t constant, uint16_t cache_id)
    792       REQUIRES_SHARED(Locks::mutator_lock_)
    793       : ConstantType(constant, cache_id) {
    794     CheckConstructorInvariants(this);
    795   }
    796   bool IsPreciseConstantLo() const OVERRIDE { return true; }
    797   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    798 
    799   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    800     return AssignmentType::kNotAssignable;
    801   }
    802 };
    803 
    804 class PreciseConstHiType FINAL : public ConstantType {
    805  public:
    806   PreciseConstHiType(uint32_t constant, uint16_t cache_id)
    807       REQUIRES_SHARED(Locks::mutator_lock_)
    808       : ConstantType(constant, cache_id) {
    809     CheckConstructorInvariants(this);
    810   }
    811   bool IsPreciseConstantHi() const OVERRIDE { return true; }
    812   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    813 
    814   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    815     return AssignmentType::kNotAssignable;
    816   }
    817 };
    818 
    819 class ImpreciseConstType FINAL : public ConstantType {
    820  public:
    821   ImpreciseConstType(uint32_t constat, uint16_t cache_id)
    822        REQUIRES_SHARED(Locks::mutator_lock_)
    823        : ConstantType(constat, cache_id) {
    824     CheckConstructorInvariants(this);
    825   }
    826   bool IsImpreciseConstant() const OVERRIDE { return true; }
    827   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    828 
    829   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    830     return AssignmentType::kNotAssignable;
    831   }
    832 };
    833 
    834 class ImpreciseConstLoType FINAL : public ConstantType {
    835  public:
    836   ImpreciseConstLoType(uint32_t constant, uint16_t cache_id)
    837       REQUIRES_SHARED(Locks::mutator_lock_)
    838       : ConstantType(constant, cache_id) {
    839     CheckConstructorInvariants(this);
    840   }
    841   bool IsImpreciseConstantLo() const OVERRIDE { return true; }
    842   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    843 
    844   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    845     return AssignmentType::kNotAssignable;
    846   }
    847 };
    848 
    849 class ImpreciseConstHiType FINAL : public ConstantType {
    850  public:
    851   ImpreciseConstHiType(uint32_t constant, uint16_t cache_id)
    852       REQUIRES_SHARED(Locks::mutator_lock_)
    853       : ConstantType(constant, cache_id) {
    854     CheckConstructorInvariants(this);
    855   }
    856   bool IsImpreciseConstantHi() const OVERRIDE { return true; }
    857   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    858 
    859   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    860     return AssignmentType::kNotAssignable;
    861   }
    862 };
    863 
    864 // Special "null" type that captures the semantics of null / bottom.
    865 class NullType FINAL : public RegType {
    866  public:
    867   bool IsNull() const OVERRIDE {
    868     return true;
    869   }
    870 
    871   // Get the singleton Null instance.
    872   static const NullType* GetInstance() PURE;
    873 
    874   // Create the singleton instance.
    875   static const NullType* CreateInstance(mirror::Class* klass,
    876                                         const StringPiece& descriptor,
    877                                         uint16_t cache_id)
    878       REQUIRES_SHARED(Locks::mutator_lock_);
    879 
    880   static void Destroy();
    881 
    882   std::string Dump() const OVERRIDE {
    883     return "null";
    884   }
    885 
    886   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    887     return AssignmentType::kReference;
    888   }
    889 
    890   bool IsConstantTypes() const OVERRIDE {
    891     return true;
    892   }
    893 
    894  private:
    895   NullType(mirror::Class* klass, const StringPiece& descriptor, uint16_t cache_id)
    896       REQUIRES_SHARED(Locks::mutator_lock_)
    897       : RegType(klass, descriptor, cache_id) {
    898     CheckConstructorInvariants(this);
    899   }
    900 
    901   static const NullType* instance_;
    902 };
    903 
    904 // Common parent of all uninitialized types. Uninitialized types are created by
    905 // "new" dex
    906 // instructions and must be passed to a constructor.
    907 class UninitializedType : public RegType {
    908  public:
    909   UninitializedType(mirror::Class* klass, const StringPiece& descriptor,
    910                     uint32_t allocation_pc, uint16_t cache_id)
    911       : RegType(klass, descriptor, cache_id), allocation_pc_(allocation_pc) {}
    912 
    913   bool IsUninitializedTypes() const OVERRIDE;
    914   bool IsNonZeroReferenceTypes() const OVERRIDE;
    915 
    916   uint32_t GetAllocationPc() const {
    917     DCHECK(IsUninitializedTypes());
    918     return allocation_pc_;
    919   }
    920 
    921   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
    922     return AssignmentType::kReference;
    923   }
    924 
    925  private:
    926   const uint32_t allocation_pc_;
    927 };
    928 
    929 // Similar to ReferenceType but not yet having been passed to a constructor.
    930 class UninitializedReferenceType FINAL : public UninitializedType {
    931  public:
    932   UninitializedReferenceType(mirror::Class* klass,
    933                              const StringPiece& descriptor,
    934                              uint32_t allocation_pc, uint16_t cache_id)
    935       REQUIRES_SHARED(Locks::mutator_lock_)
    936       : UninitializedType(klass, descriptor, allocation_pc, cache_id) {
    937     CheckConstructorInvariants(this);
    938   }
    939 
    940   bool IsUninitializedReference() const OVERRIDE { return true; }
    941 
    942   bool HasClassVirtual() const OVERRIDE { return true; }
    943 
    944   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    945 };
    946 
    947 // Similar to UnresolvedReferenceType but not yet having been passed to a
    948 // constructor.
    949 class UnresolvedUninitializedRefType FINAL : public UninitializedType {
    950  public:
    951   UnresolvedUninitializedRefType(const StringPiece& descriptor,
    952                                  uint32_t allocation_pc, uint16_t cache_id)
    953       REQUIRES_SHARED(Locks::mutator_lock_)
    954       : UninitializedType(nullptr, descriptor, allocation_pc, cache_id) {
    955     CheckConstructorInvariants(this);
    956   }
    957 
    958   bool IsUnresolvedAndUninitializedReference() const OVERRIDE { return true; }
    959 
    960   bool IsUnresolvedTypes() const OVERRIDE { return true; }
    961 
    962   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    963 
    964  private:
    965   void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_) OVERRIDE;
    966 };
    967 
    968 // Similar to UninitializedReferenceType but special case for the this argument
    969 // of a constructor.
    970 class UninitializedThisReferenceType FINAL : public UninitializedType {
    971  public:
    972   UninitializedThisReferenceType(mirror::Class* klass,
    973                                  const StringPiece& descriptor,
    974                                  uint16_t cache_id)
    975       REQUIRES_SHARED(Locks::mutator_lock_)
    976       : UninitializedType(klass, descriptor, 0, cache_id) {
    977     CheckConstructorInvariants(this);
    978   }
    979 
    980   virtual bool IsUninitializedThisReference() const OVERRIDE { return true; }
    981 
    982   bool HasClassVirtual() const OVERRIDE { return true; }
    983 
    984   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
    985 
    986  private:
    987   void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_) OVERRIDE;
    988 };
    989 
    990 class UnresolvedUninitializedThisRefType FINAL : public UninitializedType {
    991  public:
    992   UnresolvedUninitializedThisRefType(const StringPiece& descriptor,
    993                                      uint16_t cache_id)
    994       REQUIRES_SHARED(Locks::mutator_lock_)
    995       : UninitializedType(nullptr, descriptor, 0, cache_id) {
    996     CheckConstructorInvariants(this);
    997   }
    998 
    999   bool IsUnresolvedAndUninitializedThisReference() const OVERRIDE { return true; }
   1000 
   1001   bool IsUnresolvedTypes() const OVERRIDE { return true; }
   1002 
   1003   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
   1004 
   1005  private:
   1006   void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_) OVERRIDE;
   1007 };
   1008 
   1009 // A type of register holding a reference to an Object of type GetClass or a
   1010 // sub-class.
   1011 class ReferenceType FINAL : public RegType {
   1012  public:
   1013   ReferenceType(mirror::Class* klass, const StringPiece& descriptor,
   1014                 uint16_t cache_id) REQUIRES_SHARED(Locks::mutator_lock_)
   1015       : RegType(klass, descriptor, cache_id) {
   1016     CheckConstructorInvariants(this);
   1017   }
   1018 
   1019   bool IsReference() const OVERRIDE { return true; }
   1020 
   1021   bool IsNonZeroReferenceTypes() const OVERRIDE { return true; }
   1022 
   1023   bool HasClassVirtual() const OVERRIDE { return true; }
   1024 
   1025   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
   1026 
   1027   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
   1028     return AssignmentType::kReference;
   1029   }
   1030 };
   1031 
   1032 // A type of register holding a reference to an Object of type GetClass and only
   1033 // an object of that
   1034 // type.
   1035 class PreciseReferenceType FINAL : public RegType {
   1036  public:
   1037   PreciseReferenceType(mirror::Class* klass, const StringPiece& descriptor,
   1038                        uint16_t cache_id)
   1039       REQUIRES_SHARED(Locks::mutator_lock_);
   1040 
   1041   bool IsPreciseReference() const OVERRIDE { return true; }
   1042 
   1043   bool IsNonZeroReferenceTypes() const OVERRIDE { return true; }
   1044 
   1045   bool HasClassVirtual() const OVERRIDE { return true; }
   1046 
   1047   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
   1048 
   1049   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
   1050     return AssignmentType::kReference;
   1051   }
   1052 };
   1053 
   1054 // Common parent of unresolved types.
   1055 class UnresolvedType : public RegType {
   1056  public:
   1057   UnresolvedType(const StringPiece& descriptor, uint16_t cache_id)
   1058       REQUIRES_SHARED(Locks::mutator_lock_)
   1059       : RegType(nullptr, descriptor, cache_id) {}
   1060 
   1061   bool IsNonZeroReferenceTypes() const OVERRIDE;
   1062 
   1063   AssignmentType GetAssignmentTypeImpl() const OVERRIDE {
   1064     return AssignmentType::kReference;
   1065   }
   1066 };
   1067 
   1068 // Similar to ReferenceType except the Class couldn't be loaded. Assignability
   1069 // and other tests made
   1070 // of this type must be conservative.
   1071 class UnresolvedReferenceType FINAL : public UnresolvedType {
   1072  public:
   1073   UnresolvedReferenceType(const StringPiece& descriptor, uint16_t cache_id)
   1074       REQUIRES_SHARED(Locks::mutator_lock_)
   1075       : UnresolvedType(descriptor, cache_id) {
   1076     CheckConstructorInvariants(this);
   1077   }
   1078 
   1079   bool IsUnresolvedReference() const OVERRIDE { return true; }
   1080 
   1081   bool IsUnresolvedTypes() const OVERRIDE { return true; }
   1082 
   1083   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
   1084 
   1085  private:
   1086   void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_) OVERRIDE;
   1087 };
   1088 
   1089 // Type representing the super-class of an unresolved type.
   1090 class UnresolvedSuperClass FINAL : public UnresolvedType {
   1091  public:
   1092   UnresolvedSuperClass(uint16_t child_id, RegTypeCache* reg_type_cache,
   1093                        uint16_t cache_id)
   1094       REQUIRES_SHARED(Locks::mutator_lock_)
   1095       : UnresolvedType("", cache_id),
   1096         unresolved_child_id_(child_id),
   1097         reg_type_cache_(reg_type_cache) {
   1098     CheckConstructorInvariants(this);
   1099   }
   1100 
   1101   bool IsUnresolvedSuperClass() const OVERRIDE { return true; }
   1102 
   1103   bool IsUnresolvedTypes() const OVERRIDE { return true; }
   1104 
   1105   uint16_t GetUnresolvedSuperClassChildId() const {
   1106     DCHECK(IsUnresolvedSuperClass());
   1107     return static_cast<uint16_t>(unresolved_child_id_ & 0xFFFF);
   1108   }
   1109 
   1110   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
   1111 
   1112  private:
   1113   void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_) OVERRIDE;
   1114 
   1115   const uint16_t unresolved_child_id_;
   1116   const RegTypeCache* const reg_type_cache_;
   1117 };
   1118 
   1119 // A merge of unresolved (and resolved) types. If the types were resolved this may be
   1120 // Conflict or another known ReferenceType.
   1121 class UnresolvedMergedType FINAL : public UnresolvedType {
   1122  public:
   1123   // Note: the constructor will copy the unresolved BitVector, not use it directly.
   1124   UnresolvedMergedType(const RegType& resolved,
   1125                        const BitVector& unresolved,
   1126                        const RegTypeCache* reg_type_cache,
   1127                        uint16_t cache_id)
   1128       REQUIRES_SHARED(Locks::mutator_lock_);
   1129 
   1130   // The resolved part. See description below.
   1131   const RegType& GetResolvedPart() const {
   1132     return resolved_part_;
   1133   }
   1134   // The unresolved part.
   1135   const BitVector& GetUnresolvedTypes() const {
   1136     return unresolved_types_;
   1137   }
   1138 
   1139   bool IsUnresolvedMergedReference() const OVERRIDE { return true; }
   1140 
   1141   bool IsUnresolvedTypes() const OVERRIDE { return true; }
   1142 
   1143   bool IsArrayTypes() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
   1144   bool IsObjectArrayTypes() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
   1145 
   1146   std::string Dump() const OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_);
   1147 
   1148  private:
   1149   void CheckInvariants() const REQUIRES_SHARED(Locks::mutator_lock_) OVERRIDE;
   1150 
   1151   const RegTypeCache* const reg_type_cache_;
   1152 
   1153   // The original implementation of merged types was a binary tree. Collection of the flattened
   1154   // types ("leaves") can be expensive, so we store the expanded list now, as two components:
   1155   // 1) A resolved component. We use Zero when there is no resolved component, as that will be
   1156   //    an identity merge.
   1157   // 2) A bitvector of the unresolved reference types. A bitvector was chosen with the assumption
   1158   //    that there should not be too many types in flight in practice. (We also bias the index
   1159   //    against the index of Zero, which is one of the later default entries in any cache.)
   1160   const RegType& resolved_part_;
   1161   const BitVector unresolved_types_;
   1162 };
   1163 
   1164 std::ostream& operator<<(std::ostream& os, const RegType& rhs)
   1165     REQUIRES_SHARED(Locks::mutator_lock_);
   1166 
   1167 }  // namespace verifier
   1168 }  // namespace art
   1169 
   1170 #endif  // ART_RUNTIME_VERIFIER_REG_TYPE_H_
   1171