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