ART: Change UnresolvedMergedType internal representation
Use a BitVector instead of the tree representation. This
avoids flattening the components and other instances.
Bug: 22881413
Change-Id: Ibf7cfb54443affeb1753bf114c0f306125391c62
diff --git a/runtime/verifier/reg_type.cc b/runtime/verifier/reg_type.cc
index 7fe8bb9..b86a4c8 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"
@@ -309,13 +310,17 @@
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();
@@ -492,32 +497,6 @@
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();
@@ -803,12 +782,24 @@
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 4893088..2834a9a 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 @@
// from another.
const RegType& Merge(const RegType& incoming_type, RegTypeCache* reg_types) const
SHARED_REQUIRES(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_REQUIRES(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 @@
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_REQUIRES(Locks::mutator_lock_)
- : UnresolvedType("", cache_id),
- reg_type_cache_(reg_type_cache),
- merged_types_(left_id, right_id) {
- if (kIsDebugBuild) {
- CheckInvariants();
- }
- }
+ SHARED_REQUIRES(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 complete set of merged types.
- std::set<uint16_t> GetMergedTypes() const;
+ // The unresolved part.
+ const BitVector& GetUnresolvedTypes() const {
+ return unresolved_types_;
+ }
bool IsUnresolvedMergedReference() const OVERRIDE { return true; }
@@ -903,7 +905,16 @@
void CheckInvariants() const SHARED_REQUIRES(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 4469e64..5e1feb8 100644
--- a/runtime/verifier/reg_type_cache.cc
+++ b/runtime/verifier/reg_type_cache.cc
@@ -317,39 +317,62 @@
}
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;
}
