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