From f695a009725c8c840d916d01c14998f5c5f816d2 Mon Sep 17 00:00:00 2001 From: Andreas Gampe Date: Fri, 7 Aug 2015 08:29:13 -0700 Subject: ART: Change UnresolvedMergedType internal representation Squashed cherry-picks: * 067f1ed7816cf4eb5d6258ca31b387ddb2073ab7 * 750f7c2827318f6d07620f2ef0321218ea4d8670 * 2f90b3415aadc2587d26c767c6bfb235797119a8 * 2ea7b70b2347969f3735bd0ec1b462bd6d2ff1bd Bug: 22881413 --- runtime/base/bit_vector.cc | 37 +++++++++++++++++------ runtime/base/bit_vector.h | 13 ++++++-- runtime/base/bit_vector_test.cc | 4 +-- runtime/verifier/reg_type.cc | 61 ++++++++++++++++---------------------- runtime/verifier/reg_type.h | 51 ++++++++++++++++++------------- runtime/verifier/reg_type_cache.cc | 57 ++++++++++++++++++++++++----------- runtime/verifier/reg_type_test.cc | 10 ++++--- 7 files changed, 144 insertions(+), 89 deletions(-) (limited to 'runtime') 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(allocator_->Alloc(storage_size_ * kWordBytes)); - } +} + +BitVector::BitVector(uint32_t start_bits, + bool expandable, + Allocator* allocator) + : BitVector(expandable, + allocator, + BitsToWords(start_bits), + static_cast(allocator->Alloc(BitsToWords(start_bits) * kWordBytes))) { +} + + +BitVector::BitVector(const BitVector& src, + bool expandable, + Allocator* allocator) + : BitVector(expandable, + allocator, + src.storage_size_, + static_cast(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 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 UnresolvedMergedType::GetMergedTypes() const { - std::pair refs = GetTopMergedTypes(); - const RegType& left = reg_type_cache_->GetFromId(refs.first); - const RegType& right = reg_type_cache_->GetFromId(refs.second); - - std::set types; - if (left.IsUnresolvedMergedReference()) { - types = down_cast(&left)->GetMergedTypes(); - } else { - types.insert(refs.first); - } - if (right.IsUnresolvedMergedReference()) { - std::set right_types = - down_cast(&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 #include +#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 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 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 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 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(left)); - types = (down_cast(&non_const))->GetMergedTypes(); + const UnresolvedMergedType* left_merge = down_cast(&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(right)); - std::set right_types = (down_cast(&non_const))->GetMergedTypes(); - types.insert(right_types.begin(), right_types.end()); + const UnresolvedMergedType* right_merge = down_cast(&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 cur_entry_types = - (down_cast(cur_entry))->GetMergedTypes(); - if (cur_entry_types == types) { + const UnresolvedMergedType* cmp_type = down_cast(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(entry); - std::set 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 +#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(merged); - std::set merged_ids = (down_cast(&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(&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) { -- cgit v1.1