ART: Change UnresolvedMergedType internal representation

Squashed cherry-picks:
* 067f1ed7816cf4eb5d6258ca31b387ddb2073ab7
* 750f7c2827318f6d07620f2ef0321218ea4d8670
* 2f90b3415aadc2587d26c767c6bfb235797119a8
* 2ea7b70b2347969f3735bd0ec1b462bd6d2ff1bd

Bug: 22881413

7 files changed, 144 insertions, 89 deletions

diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc
index 39ce0d2..cfd3d24 100644
--- a/runtime/base/bit_vector.cc
+++ b/runtime/base/bit_vector.cc
@@ -24,11 +24,7 @@
 
 namespace art {
 
-// TODO: replace excessive argument defaulting when we are at gcc 4.7
-// or later on host with delegating constructor support. Specifically,
-// starts_bits and storage_size/storage are mutually exclusive.
-BitVector::BitVector(uint32_t start_bits,
-                     bool expandable,
+BitVector::BitVector(bool expandable,
                      Allocator* allocator,
                      uint32_t storage_size,
                      uint32_t* storage)
@@ -36,12 +32,31 @@ BitVector::BitVector(uint32_t start_bits,
     storage_size_(storage_size),
     allocator_(allocator),
     expandable_(expandable) {
+  DCHECK(storage_ != nullptr);
+
   static_assert(sizeof(*storage_) == kWordBytes, "word bytes");
   static_assert(sizeof(*storage_) * 8u == kWordBits, "word bits");
-  if (storage_ == nullptr) {
-    storage_size_ = BitsToWords(start_bits);
-    storage_ = static_cast<uint32_t*>(allocator_->Alloc(storage_size_ * kWordBytes));
-  }
+}
+
+BitVector::BitVector(uint32_t start_bits,
+                     bool expandable,
+                     Allocator* allocator)
+  : BitVector(expandable,
+              allocator,
+              BitsToWords(start_bits),
+              static_cast<uint32_t*>(allocator->Alloc(BitsToWords(start_bits) * kWordBytes))) {
+}
+
+
+BitVector::BitVector(const BitVector& src,
+                     bool expandable,
+                     Allocator* allocator)
+  : BitVector(expandable,
+              allocator,
+              src.storage_size_,
+              static_cast<uint32_t*>(allocator->Alloc(src.storage_size_ * kWordBytes))) {
+  // Direct memcpy would be faster, but this should be fine too and is cleaner.
+  Copy(&src);
 }
 
 BitVector::~BitVector() {
@@ -357,4 +372,8 @@ void BitVector::EnsureSize(uint32_t idx) {
   }
 }
 
+Allocator* BitVector::GetAllocator() const {
+  return allocator_;
+}
+
 }  // namespace art
diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h
index 17835f5..237bc90 100644
--- a/runtime/base/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -112,9 +112,16 @@ class BitVector {
 
   BitVector(uint32_t start_bits,
             bool expandable,
+            Allocator* allocator);
+
+  BitVector(bool expandable,
             Allocator* allocator,
-            uint32_t storage_size = 0,
-            uint32_t* storage = nullptr);
+            uint32_t storage_size,
+            uint32_t* storage);
+
+  BitVector(const BitVector& src,
+            bool expandable,
+            Allocator* allocator);
 
   virtual ~BitVector();
 
@@ -231,6 +238,8 @@ class BitVector {
 
   void Dump(std::ostream& os, const char* prefix) const;
 
+  Allocator* GetAllocator() const;
+
  private:
   /**
    * @brief Dump the bitvector into buffer in a 00101..01 format.
diff --git a/runtime/base/bit_vector_test.cc b/runtime/base/bit_vector_test.cc
index c51b9b0..76095c2 100644
--- a/runtime/base/bit_vector_test.cc
+++ b/runtime/base/bit_vector_test.cc
@@ -71,7 +71,7 @@ TEST(BitVector, NoopAllocator) {
   uint32_t bits[kWords];
   memset(bits, 0, sizeof(bits));
 
-  BitVector bv(0U, false, Allocator::GetNoopAllocator(), kWords, bits);
+  BitVector bv(false, Allocator::GetNoopAllocator(), kWords, bits);
   EXPECT_EQ(kWords, bv.GetStorageSize());
   EXPECT_EQ(kWords * sizeof(uint32_t), bv.GetSizeOf());
   EXPECT_EQ(bits, bv.GetRawStorage());
@@ -128,7 +128,7 @@ TEST(BitVector, SetInitialBits) {
   uint32_t bits[kWords];
   memset(bits, 0, sizeof(bits));
 
-  BitVector bv(0U, false, Allocator::GetNoopAllocator(), kWords, bits);
+  BitVector bv(false, Allocator::GetNoopAllocator(), kWords, bits);
   bv.SetInitialBits(0u);
   EXPECT_EQ(0u, bv.NumSetBits());
   bv.SetInitialBits(1u);
diff --git a/runtime/verifier/reg_type.cc b/runtime/verifier/reg_type.cc
index 1435607..2cdb73d 100644
--- a/runtime/verifier/reg_type.cc
+++ b/runtime/verifier/reg_type.cc
@@ -16,6 +16,7 @@
 
 #include "reg_type-inl.h"
 
+#include "base/bit_vector-inl.h"
 #include "base/casts.h"
 #include "class_linker-inl.h"
 #include "dex_file-inl.h"
@@ -307,13 +308,17 @@ PreciseReferenceType::PreciseReferenceType(mirror::Class* klass, const std::stri
 
 std::string UnresolvedMergedType::Dump() const {
   std::stringstream result;
-  std::set<uint16_t> types = GetMergedTypes();
-  result << "UnresolvedMergedReferences(";
-  auto it = types.begin();
-  result << reg_type_cache_->GetFromId(*it).Dump();
-  for (++it; it != types.end(); ++it) {
-    result << ", ";
-    result << reg_type_cache_->GetFromId(*it).Dump();
+  result << "UnresolvedMergedReferences(" << GetResolvedPart().Dump() << " | ";
+  const BitVector& types = GetUnresolvedTypes();
+
+  bool first = true;
+  for (uint32_t idx : types.Indexes()) {
+    if (!first) {
+      result << ", ";
+    } else {
+      first = false;
+    }
+    result << reg_type_cache_->GetFromId(idx).Dump();
   }
   result << ")";
   return result.str();
@@ -490,32 +495,6 @@ bool UnresolvedType::IsNonZeroReferenceTypes() const {
   return true;
 }
 
-std::set<uint16_t> UnresolvedMergedType::GetMergedTypes() const {
-  std::pair<uint16_t, uint16_t> refs = GetTopMergedTypes();
-  const RegType& left = reg_type_cache_->GetFromId(refs.first);
-  const RegType& right = reg_type_cache_->GetFromId(refs.second);
-
-  std::set<uint16_t> types;
-  if (left.IsUnresolvedMergedReference()) {
-    types = down_cast<const UnresolvedMergedType*>(&left)->GetMergedTypes();
-  } else {
-    types.insert(refs.first);
-  }
-  if (right.IsUnresolvedMergedReference()) {
-    std::set<uint16_t> right_types =
-        down_cast<const UnresolvedMergedType*>(&right)->GetMergedTypes();
-    types.insert(right_types.begin(), right_types.end());
-  } else {
-    types.insert(refs.second);
-  }
-  if (kIsDebugBuild) {
-    for (const auto& type : types) {
-      CHECK(!reg_type_cache_->GetFromId(type).IsUnresolvedMergedReference());
-    }
-  }
-  return types;
-}
-
 const RegType& RegType::GetSuperClass(RegTypeCache* cache) const {
   if (!IsUnresolvedTypes()) {
     mirror::Class* super_klass = GetClass()->GetSuperClass();
@@ -805,12 +784,24 @@ void UnresolvedUninitializedRefType::CheckInvariants() const {
   CHECK(klass_.IsNull()) << *this;
 }
 
+UnresolvedMergedType::UnresolvedMergedType(const RegType& resolved,
+                                           const BitVector& unresolved,
+                                           const RegTypeCache* reg_type_cache,
+                                           uint16_t cache_id)
+    : UnresolvedType("", cache_id),
+      reg_type_cache_(reg_type_cache),
+      resolved_part_(resolved),
+      unresolved_types_(unresolved, false, unresolved.GetAllocator()) {
+  if (kIsDebugBuild) {
+    CheckInvariants();
+  }
+}
 void UnresolvedMergedType::CheckInvariants() const {
   // Unresolved merged types: merged types should be defined.
   CHECK(descriptor_.empty()) << *this;
   CHECK(klass_.IsNull()) << *this;
-  CHECK_NE(merged_types_.first, 0U) << *this;
-  CHECK_NE(merged_types_.second, 0U) << *this;
+  CHECK(resolved_part_.IsReferenceTypes());
+  CHECK(!resolved_part_.IsUnresolvedTypes());
 }
 
 void UnresolvedReferenceType::CheckInvariants() const {
diff --git a/runtime/verifier/reg_type.h b/runtime/verifier/reg_type.h
index d08c937..2af0ead 100644
--- a/runtime/verifier/reg_type.h
+++ b/runtime/verifier/reg_type.h
@@ -22,6 +22,7 @@
 #include <set>
 #include <string>
 
+#include "base/bit_vector.h"
 #include "base/macros.h"
 #include "base/mutex.h"
 #include "gc_root.h"
@@ -230,6 +231,14 @@ class RegType {
   // from another.
   const RegType& Merge(const RegType& incoming_type, RegTypeCache* reg_types) const
       SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
+  // Same as above, but also handles the case where incoming_type == this.
+  const RegType& SafeMerge(const RegType& incoming_type, RegTypeCache* reg_types) const
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
+    if (Equals(incoming_type)) {
+      return *this;
+    }
+    return Merge(incoming_type, reg_types);
+  }
 
   /*
    * A basic Join operation on classes. For a pair of types S and T the Join,
@@ -868,30 +877,23 @@ class UnresolvedSuperClass FINAL : public UnresolvedType {
   const RegTypeCache* const reg_type_cache_;
 };
 
-// A merge of two unresolved types. If the types were resolved this may be
-// Conflict or another
-// known ReferenceType.
+// A merge of unresolved (and resolved) types. If the types were resolved this may be
+// Conflict or another known ReferenceType.
 class UnresolvedMergedType FINAL : public UnresolvedType {
  public:
-  UnresolvedMergedType(uint16_t left_id, uint16_t right_id,
+  // Note: the constructor will copy the unresolved BitVector, not use it directly.
+  UnresolvedMergedType(const RegType& resolved, const BitVector& unresolved,
                        const RegTypeCache* reg_type_cache, uint16_t cache_id)
-      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
-      : UnresolvedType("", cache_id),
-        reg_type_cache_(reg_type_cache),
-        merged_types_(left_id, right_id) {
-    if (kIsDebugBuild) {
-      CheckInvariants();
-    }
-  }
+      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
-  // The top of a tree of merged types.
-  std::pair<uint16_t, uint16_t> GetTopMergedTypes() const {
-    DCHECK(IsUnresolvedMergedReference());
-    return merged_types_;
+  // The resolved part. See description below.
+  const RegType& GetResolvedPart() const {
+    return resolved_part_;
+  }
+  // The unresolved part.
+  const BitVector& GetUnresolvedTypes() const {
+    return unresolved_types_;
   }
-
-  // The complete set of merged types.
-  std::set<uint16_t> GetMergedTypes() const;
 
   bool IsUnresolvedMergedReference() const OVERRIDE { return true; }
 
@@ -903,7 +905,16 @@ class UnresolvedMergedType FINAL : public UnresolvedType {
   void CheckInvariants() const SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
 
   const RegTypeCache* const reg_type_cache_;
-  const std::pair<uint16_t, uint16_t> merged_types_;
+
+  // The original implementation of merged types was a binary tree. Collection of the flattened
+  // types ("leaves") can be expensive, so we store the expanded list now, as two components:
+  // 1) A resolved component. We use Zero when there is no resolved component, as that will be
+  //    an identity merge.
+  // 2) A bitvector of the unresolved reference types. A bitvector was chosen with the assumption
+  //    that there should not be too many types in flight in practice. (We also bias the index
+  //    against the index of Zero, which is one of the later default entries in any cache.)
+  const RegType& resolved_part_;
+  const BitVector unresolved_types_;
 };
 
 std::ostream& operator<<(std::ostream& os, const RegType& rhs)
diff --git a/runtime/verifier/reg_type_cache.cc b/runtime/verifier/reg_type_cache.cc
index b371d7e..a597c8f 100644
--- a/runtime/verifier/reg_type_cache.cc
+++ b/runtime/verifier/reg_type_cache.cc
@@ -317,39 +317,62 @@ void RegTypeCache::CreatePrimitiveAndSmallConstantTypes() {
 }
 
 const RegType& RegTypeCache::FromUnresolvedMerge(const RegType& left, const RegType& right) {
-  std::set<uint16_t> types;
+  BitVector types(1,                                    // Allocate at least a word.
+                  true,                                 // Is expandable.
+                  Allocator::GetMallocAllocator());     // TODO: Arenas in the verifier.
+  const RegType* left_resolved;
   if (left.IsUnresolvedMergedReference()) {
-    RegType& non_const(const_cast<RegType&>(left));
-    types = (down_cast<UnresolvedMergedType*>(&non_const))->GetMergedTypes();
+    const UnresolvedMergedType* left_merge = down_cast<const UnresolvedMergedType*>(&left);
+    types.Copy(&left_merge->GetUnresolvedTypes());
+    left_resolved = &left_merge->GetResolvedPart();
+  } else if (left.IsUnresolvedReference()) {
+    types.SetBit(left.GetId());
+    left_resolved = &Zero();
   } else {
-    types.insert(left.GetId());
+    left_resolved = &left;
   }
+
+  const RegType* right_resolved;
   if (right.IsUnresolvedMergedReference()) {
-    RegType& non_const(const_cast<RegType&>(right));
-    std::set<uint16_t> right_types = (down_cast<UnresolvedMergedType*>(&non_const))->GetMergedTypes();
-    types.insert(right_types.begin(), right_types.end());
+    const UnresolvedMergedType* right_merge = down_cast<const UnresolvedMergedType*>(&right);
+    types.Union(&right_merge->GetUnresolvedTypes());
+    right_resolved = &right_merge->GetResolvedPart();
+  } else if (right.IsUnresolvedReference()) {
+    types.SetBit(right.GetId());
+    right_resolved = &Zero();
   } else {
-    types.insert(right.GetId());
+    right_resolved = &right;
+  }
+
+  // Merge the resolved parts. Left and right might be equal, so use SafeMerge.
+  const RegType& resolved_parts_merged = left_resolved->SafeMerge(*right_resolved, this);
+  // If we get a conflict here, the merge result is a conflict, not an unresolved merge type.
+  if (resolved_parts_merged.IsConflict()) {
+    return Conflict();
   }
+
   // Check if entry already exists.
   for (size_t i = primitive_count_; i < entries_.size(); i++) {
     const RegType* cur_entry = entries_[i];
     if (cur_entry->IsUnresolvedMergedReference()) {
-      std::set<uint16_t> cur_entry_types =
-          (down_cast<const UnresolvedMergedType*>(cur_entry))->GetMergedTypes();
-      if (cur_entry_types == types) {
+      const UnresolvedMergedType* cmp_type = down_cast<const UnresolvedMergedType*>(cur_entry);
+      const RegType& resolved_part = cmp_type->GetResolvedPart();
+      const BitVector& unresolved_part = cmp_type->GetUnresolvedTypes();
+      // Use SameBitsSet. "types" is expandable to allow merging in the components, but the
+      // BitVector in the final RegType will be made non-expandable.
+      if (&resolved_part == &resolved_parts_merged &&
+              types.SameBitsSet(&unresolved_part)) {
         return *cur_entry;
       }
     }
   }
+
   // Create entry.
-  RegType* entry = new UnresolvedMergedType(left.GetId(), right.GetId(), this, entries_.size());
+  RegType* entry = new UnresolvedMergedType(resolved_parts_merged,
+                                            types,
+                                            this,
+                                            entries_.size());
   AddEntry(entry);
-  if (kIsDebugBuild) {
-    UnresolvedMergedType* tmp_entry = down_cast<UnresolvedMergedType*>(entry);
-    std::set<uint16_t> check_types = tmp_entry->GetMergedTypes();
-    CHECK(check_types == types);
-  }
   return *entry;
 }
 
diff --git a/runtime/verifier/reg_type_test.cc b/runtime/verifier/reg_type_test.cc
index 2fecc8b..971b1f5 100644
--- a/runtime/verifier/reg_type_test.cc
+++ b/runtime/verifier/reg_type_test.cc
@@ -18,6 +18,7 @@
 
 #include <set>
 
+#include "base/bit_vector.h"
 #include "base/casts.h"
 #include "common_runtime_test.h"
 #include "reg_type_cache-inl.h"
@@ -421,7 +422,7 @@ TEST_F(RegTypeReferenceTest, Dump) {
   EXPECT_EQ(expected, resolved_unintialiesd.Dump());
   expected = "Unresolved And Uninitialized Reference: java.lang.DoesNotExist Allocation PC: 12";
   EXPECT_EQ(expected, unresolved_unintialized.Dump());
-  expected = "UnresolvedMergedReferences(Unresolved Reference: java.lang.DoesNotExist, Unresolved Reference: java.lang.DoesNotExistEither)";
+  expected = "UnresolvedMergedReferences(Zero/null | Unresolved Reference: java.lang.DoesNotExist, Unresolved Reference: java.lang.DoesNotExistEither)";
   EXPECT_EQ(expected, unresolved_merged.Dump());
 }
 
@@ -477,9 +478,10 @@ TEST_F(RegTypeReferenceTest, Merging) {
   EXPECT_TRUE(merged.IsUnresolvedMergedReference());
   RegType& merged_nonconst = const_cast<RegType&>(merged);
 
-  std::set<uint16_t> merged_ids = (down_cast<UnresolvedMergedType*>(&merged_nonconst))->GetMergedTypes();
-  EXPECT_EQ(ref_type_0.GetId(), *(merged_ids.begin()));
-  EXPECT_EQ(ref_type_1.GetId(), *((++merged_ids.begin())));
+  const BitVector& unresolved_parts =
+      down_cast<UnresolvedMergedType*>(&merged_nonconst)->GetUnresolvedTypes();
+  EXPECT_TRUE(unresolved_parts.IsBitSet(ref_type_0.GetId()));
+  EXPECT_TRUE(unresolved_parts.IsBitSet(ref_type_1.GetId()));
 }
 
 TEST_F(RegTypeTest, MergingFloat) {