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