diff options
author | Zachary Turner <zturner@google.com> | 2017-11-30 23:00:30 +0000 |
---|---|---|
committer | Zachary Turner <zturner@google.com> | 2017-11-30 23:00:30 +0000 |
commit | 50d97d4026888af76fd1b7e7da56f4dc40247ad0 (patch) | |
tree | b8008d387b71ed70f161c825f6cb2a1a2e74065e /lib/DebugInfo | |
parent | 421983a9de53bfbfe1e9fc528cf2e96ea41f2463 (diff) |
Simplify the DenseSet used for hashing CodeView records.
This was storing the hash alongside the key so that the hash
doesn't need to be re-computed every time, but in doing so it
was allocating a structure to keep the key size small in the
DenseMap. This is a noble goal, but it also leads to a pointer
indirection on every probe, and this cost of this pointer
indirection ends up being higher than the cost of having a
slightly larger entry in the hash table. Removing this not only
simplifies the code, but yields a small but noticeable
performance improvement in the type merging algorithm.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@319493 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/DebugInfo')
-rw-r--r-- | lib/DebugInfo/CodeView/MergingTypeTableBuilder.cpp | 140 |
1 files changed, 44 insertions, 96 deletions
diff --git a/lib/DebugInfo/CodeView/MergingTypeTableBuilder.cpp b/lib/DebugInfo/CodeView/MergingTypeTableBuilder.cpp index 6513f1fd739..514d55aed0b 100644 --- a/lib/DebugInfo/CodeView/MergingTypeTableBuilder.cpp +++ b/lib/DebugInfo/CodeView/MergingTypeTableBuilder.cpp @@ -28,115 +28,35 @@ using namespace llvm; using namespace llvm::codeview; -namespace { - -struct HashedType { - hash_code Hash; - ArrayRef<uint8_t> Data; - TypeIndex Index; -}; - -/// Wrapper around a poitner to a HashedType. Hash and equality operations are -/// based on data in the pointee. -struct HashedTypePtr { - HashedTypePtr() = default; - HashedTypePtr(HashedType *Ptr) : Ptr(Ptr) {} - - HashedType *Ptr = nullptr; -}; - -} // end anonymous namespace +static HashedType Empty{0, {}, TypeIndex::None()}; +static HashedType Tombstone{hash_code(-1), {}, TypeIndex::None()}; namespace llvm { -template <> struct DenseMapInfo<HashedTypePtr> { - static inline HashedTypePtr getEmptyKey() { return HashedTypePtr(nullptr); } +template <> struct DenseMapInfo<HashedType> { + static inline HashedType getEmptyKey() { return Empty; } - static inline HashedTypePtr getTombstoneKey() { - return HashedTypePtr(reinterpret_cast<HashedType *>(1)); - } + static inline HashedType getTombstoneKey() { return Tombstone; } - static unsigned getHashValue(HashedTypePtr Val) { - assert(Val.Ptr != getEmptyKey().Ptr && Val.Ptr != getTombstoneKey().Ptr); - return Val.Ptr->Hash; - } + static unsigned getHashValue(HashedType Val) { return Val.Hash; } - static bool isEqual(HashedTypePtr LHSP, HashedTypePtr RHSP) { - HashedType *LHS = LHSP.Ptr; - HashedType *RHS = RHSP.Ptr; - if (RHS == getEmptyKey().Ptr || RHS == getTombstoneKey().Ptr) - return LHS == RHS; - if (LHS->Hash != RHS->Hash) + static bool isEqual(HashedType LHS, HashedType RHS) { + if (RHS.Hash != LHS.Hash) return false; - return LHS->Data == RHS->Data; + return RHS.Data == LHS.Data; } }; } // end namespace llvm -/// Private implementation so that we don't leak our DenseMap instantiations to -/// users. -class llvm::codeview::TypeHasher { -private: - /// Storage for type record provided by the caller. Records will outlive the - /// hasher object, so they should be allocated here. - BumpPtrAllocator &RecordStorage; - - /// Storage for hash keys. These only need to live as long as the hashing - /// operation. - BumpPtrAllocator KeyStorage; - - /// Hash table. We really want a DenseMap<ArrayRef<uint8_t>, TypeIndex> here, - /// but DenseMap is inefficient when the keys are long (like type records) - /// because it recomputes the hash value of every key when it grows. This - /// value type stores the hash out of line in KeyStorage, so that table - /// entries are small and easy to rehash. - DenseSet<HashedTypePtr> HashedRecords; - -public: - TypeHasher(BumpPtrAllocator &RecordStorage) : RecordStorage(RecordStorage) {} - - void reset() { HashedRecords.clear(); } - - /// Takes the bytes of type record, inserts them into the hash table, saves - /// them, and returns a pointer to an identical stable type record along with - /// its type index in the destination stream. - TypeIndex getOrCreateRecord(ArrayRef<uint8_t> &Record, TypeIndex TI); -}; - -TypeIndex TypeHasher::getOrCreateRecord(ArrayRef<uint8_t> &Record, - TypeIndex TI) { - assert(Record.size() < UINT32_MAX && "Record too big"); - assert(Record.size() % 4 == 0 && "Record is not aligned to 4 bytes!"); - - // Compute the hash up front so we can store it in the key. - HashedType TempHashedType = {hash_value(Record), Record, TI}; - auto Result = HashedRecords.insert(HashedTypePtr(&TempHashedType)); - HashedType *&Hashed = Result.first->Ptr; - - if (Result.second) { - // This was a new type record. We need stable storage for both the key and - // the record. The record should outlive the hashing operation. - Hashed = KeyStorage.Allocate<HashedType>(); - *Hashed = TempHashedType; - - uint8_t *Stable = RecordStorage.Allocate<uint8_t>(Record.size()); - memcpy(Stable, Record.data(), Record.size()); - Hashed->Data = makeArrayRef(Stable, Record.size()); - } - - // Update the caller's copy of Record to point a stable copy. - Record = Hashed->Data; - return Hashed->Index; -} - TypeIndex MergingTypeTableBuilder::nextTypeIndex() const { return TypeIndex::fromArrayIndex(SeenRecords.size()); } MergingTypeTableBuilder::MergingTypeTableBuilder(BumpPtrAllocator &Storage) : RecordStorage(Storage) { - Hasher = llvm::make_unique<TypeHasher>(Storage); + SeenRecords.reserve(4096); + SeenHashes.reserve(4096); } MergingTypeTableBuilder::~MergingTypeTableBuilder() = default; @@ -182,17 +102,45 @@ ArrayRef<ArrayRef<uint8_t>> MergingTypeTableBuilder::records() const { return SeenRecords; } +ArrayRef<hash_code> MergingTypeTableBuilder::hashes() const { + return SeenHashes; +} + void MergingTypeTableBuilder::reset() { - Hasher->reset(); + HashedRecords.clear(); + SeenHashes.clear(); SeenRecords.clear(); } +static inline ArrayRef<uint8_t> stabilize(BumpPtrAllocator &Alloc, + ArrayRef<uint8_t> Data) { + uint8_t *Stable = Alloc.Allocate<uint8_t>(Data.size()); + memcpy(Stable, Data.data(), Data.size()); + return makeArrayRef(Stable, Data.size()); +} + +TypeIndex MergingTypeTableBuilder::insertRecordAs(hash_code Hash, + ArrayRef<uint8_t> &Record) { + assert(Record.size() < UINT32_MAX && "Record too big"); + assert(Record.size() % 4 == 0 && "Record is not aligned to 4 bytes!"); + + HashedType TempHashedType = {Hash, Record, nextTypeIndex()}; + auto Result = HashedRecords.insert(TempHashedType); + + if (Result.second) { + Result.first->Data = stabilize(RecordStorage, Record); + SeenRecords.push_back(Result.first->Data); + SeenHashes.push_back(Result.first->Hash); + } + + // Update the caller's copy of Record to point a stable copy. + Record = Result.first->Data; + return Result.first->Index; +} + TypeIndex MergingTypeTableBuilder::insertRecordBytes(ArrayRef<uint8_t> &Record) { - TypeIndex ActualTI = Hasher->getOrCreateRecord(Record, nextTypeIndex()); - if (nextTypeIndex() == ActualTI) - SeenRecords.push_back(Record); - return ActualTI; + return insertRecordAs(hash_value(Record), Record); } TypeIndex |