From cfa1d499f92d52c2ac2443c52fb77ad2fc64591d Mon Sep 17 00:00:00 2001 From: Zachary Turner Date: Thu, 20 Sep 2018 15:50:13 +0000 Subject: [PDB] Add the ability to map forward references to full decls. Some records point to an LF_CLASS, LF_UNION, LF_STRUCTURE, or LF_ENUM which is a forward reference and doesn't contain complete debug information. In these cases, we'd like to be able to quickly locate the full record. The TPI stream stores an array of pre-computed record hash values, one for each type record. If we pre-process this on startup, we can build a mapping from hash value -> {list of possible matching type indices}. Since hashes of full records are only based on the name and or unique name and not the full record contents, we can then use forward ref record to compute the hash of what *would* be the full record by just hashing the name, use this to get the list of possible matches, and iterate those looking for a match on name or unique name. llvm-pdbutil is updated to resolve forward references for the purposes of testing (plus it's just useful). Differential Revision: https://reviews.llvm.org/D52283 llvm-svn: 342656 --- llvm/lib/DebugInfo/PDB/Native/TpiHashing.cpp | 43 +++++++++++++ llvm/lib/DebugInfo/PDB/Native/TpiStream.cpp | 90 ++++++++++++++++++++++++++++ 2 files changed, 133 insertions(+) (limited to 'llvm/lib') diff --git a/llvm/lib/DebugInfo/PDB/Native/TpiHashing.cpp b/llvm/lib/DebugInfo/PDB/Native/TpiHashing.cpp index 77a2d57a836..18708826ffc 100644 --- a/llvm/lib/DebugInfo/PDB/Native/TpiHashing.cpp +++ b/llvm/lib/DebugInfo/PDB/Native/TpiHashing.cpp @@ -49,6 +49,32 @@ static Expected getHashForUdt(const CVType &Rec) { return getHashForUdt(Deserialized, Rec.data()); } +template +static Expected getTagRecordHashForUdt(const CVType &Rec) { + T Deserialized; + if (auto E = TypeDeserializer::deserializeAs(const_cast(Rec), + Deserialized)) + return std::move(E); + + ClassOptions Opts = Deserialized.getOptions(); + + bool ForwardRef = bool(Opts & ClassOptions::ForwardReference); + + uint32_t ThisRecordHash = getHashForUdt(Deserialized, Rec.data()); + + // If we don't have a forward ref we can't compute the hash of it from the + // full record because it requires hashing the entire buffer. + if (!ForwardRef) + return TagRecordHash{std::move(Deserialized), ThisRecordHash, 0}; + + bool Scoped = bool(Opts & ClassOptions::Scoped); + + StringRef NameToHash = + Scoped ? Deserialized.getUniqueName() : Deserialized.getName(); + uint32_t FullHash = hashStringV1(NameToHash); + return TagRecordHash{std::move(Deserialized), FullHash, ThisRecordHash}; +} + template static Expected getSourceLineHash(const CVType &Rec) { T Deserialized; @@ -60,6 +86,23 @@ static Expected getSourceLineHash(const CVType &Rec) { return hashStringV1(StringRef(Buf, 4)); } +Expected llvm::pdb::hashTagRecord(const codeview::CVType &Type) { + switch (Type.kind()) { + case LF_CLASS: + case LF_STRUCTURE: + case LF_INTERFACE: + return getTagRecordHashForUdt(Type); + case LF_UNION: + return getTagRecordHashForUdt(Type); + case LF_ENUM: + return getTagRecordHashForUdt(Type); + default: + assert(false && "Type is not a tag record!"); + } + return make_error("Invalid record type", + inconvertibleErrorCode()); +} + Expected llvm::pdb::hashTypeRecord(const CVType &Rec) { switch (Rec.kind()) { case LF_CLASS: diff --git a/llvm/lib/DebugInfo/PDB/Native/TpiStream.cpp b/llvm/lib/DebugInfo/PDB/Native/TpiStream.cpp index 0680b673380..de0f888137f 100644 --- a/llvm/lib/DebugInfo/PDB/Native/TpiStream.cpp +++ b/llvm/lib/DebugInfo/PDB/Native/TpiStream.cpp @@ -11,8 +11,11 @@ #include "llvm/ADT/iterator_range.h" #include "llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h" +#include "llvm/DebugInfo/CodeView/TypeDeserializer.h" +#include "llvm/DebugInfo/CodeView/TypeIndexDiscovery.h" #include "llvm/DebugInfo/CodeView/TypeRecord.h" #include "llvm/DebugInfo/MSF/MappedBlockStream.h" +#include "llvm/DebugInfo/PDB/Native/Hash.h" #include "llvm/DebugInfo/PDB/Native/PDBFile.h" #include "llvm/DebugInfo/PDB/Native/RawConstants.h" #include "llvm/DebugInfo/PDB/Native/RawError.h" @@ -140,6 +143,93 @@ uint16_t TpiStream::getTypeHashStreamAuxIndex() const { uint32_t TpiStream::getNumHashBuckets() const { return Header->NumHashBuckets; } uint32_t TpiStream::getHashKeySize() const { return Header->HashKeySize; } +void TpiStream::buildHashMap() { + if (!HashMap.empty()) + return; + if (HashValues.empty()) + return; + + HashMap.resize(Header->NumHashBuckets); + + TypeIndex TIB{Header->TypeIndexBegin}; + TypeIndex TIE{Header->TypeIndexEnd}; + while (TIB < TIE) { + uint32_t HV = HashValues[TIB.toArrayIndex()]; + HashMap[HV].push_back(TIB++); + } +} + +bool TpiStream::supportsTypeLookup() const { return !HashMap.empty(); } + +template static ClassOptions getUdtOptions(CVType CVT) { + RecordT Record; + if (auto EC = TypeDeserializer::deserializeAs(CVT, Record)) { + consumeError(std::move(EC)); + return ClassOptions::None; + } + return Record.getOptions(); +} + +static bool isUdtForwardRef(CVType CVT) { + ClassOptions UdtOptions = ClassOptions::None; + switch (CVT.kind()) { + case LF_STRUCTURE: + case LF_CLASS: + case LF_INTERFACE: + UdtOptions = getUdtOptions(std::move(CVT)); + break; + case LF_ENUM: + UdtOptions = getUdtOptions(std::move(CVT)); + break; + case LF_UNION: + UdtOptions = getUdtOptions(std::move(CVT)); + break; + default: + return false; + } + return (UdtOptions & ClassOptions::ForwardReference) != ClassOptions::None; +} + +Expected +TpiStream::findFullDeclForForwardRef(TypeIndex ForwardRefTI) const { + CVType F = Types->getType(ForwardRefTI); + if (!isUdtForwardRef(F)) + return ForwardRefTI; + + Expected ForwardTRH = hashTagRecord(F); + if (!ForwardTRH) + return ForwardTRH.takeError(); + + TagRecordHash Copy = std::move(*ForwardTRH); + uint32_t BucketIdx = ForwardTRH->FullRecordHash % Header->NumHashBuckets; + + for (TypeIndex TI : HashMap[BucketIdx]) { + CVType CVT = Types->getType(TI); + if (CVT.kind() != F.kind()) + continue; + + Expected FullTRH = hashTagRecord(CVT); + if (!FullTRH) + return FullTRH.takeError(); + if (ForwardTRH->FullRecordHash != FullTRH->FullRecordHash) + continue; + TagRecord &ForwardTR = ForwardTRH->getRecord(); + TagRecord &FullTR = FullTRH->getRecord(); + + if (!ForwardTR.hasUniqueName()) { + if (ForwardTR.getName() == FullTR.getName()) + return TI; + continue; + } + + if (!FullTR.hasUniqueName()) + continue; + if (ForwardTR.getUniqueName() == FullTR.getUniqueName()) + return TI; + } + return ForwardRefTI; +} + BinarySubstreamRef TpiStream::getTypeRecordsSubstream() const { return TypeRecordsSubstream; } -- cgit v1.2.3