diff options
Diffstat (limited to 'include/llvm/DebugInfo')
17 files changed, 243 insertions, 31 deletions
diff --git a/include/llvm/DebugInfo/CodeView/CVTypeVisitor.h b/include/llvm/DebugInfo/CodeView/CVTypeVisitor.h index e9012db7602d2..f3122f0bf7f0f 100644 --- a/include/llvm/DebugInfo/CodeView/CVTypeVisitor.h +++ b/include/llvm/DebugInfo/CodeView/CVTypeVisitor.h @@ -26,6 +26,7 @@ public: void addTypeServerHandler(TypeServerHandler &Handler); + Error visitTypeRecord(CVType &Record, TypeIndex Index); Error visitTypeRecord(CVType &Record); Error visitMemberRecord(CVMemberRecord &Record); @@ -37,6 +38,9 @@ public: Error visitFieldListMemberStream(BinaryStreamReader Reader); private: + Expected<bool> handleTypeServer(CVType &Record); + Error finishVisitation(CVType &Record); + /// The interface to the class that gets notified of each visitation. TypeVisitorCallbacks &Callbacks; diff --git a/include/llvm/DebugInfo/CodeView/RandomAccessTypeVisitor.h b/include/llvm/DebugInfo/CodeView/RandomAccessTypeVisitor.h new file mode 100644 index 0000000000000..35a8010f1163b --- /dev/null +++ b/include/llvm/DebugInfo/CodeView/RandomAccessTypeVisitor.h @@ -0,0 +1,103 @@ +//===- RandomAccessTypeVisitor.h ------------------------------ *- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_DEBUGINFO_CODEVIEW_RANDOMACCESSTYPEVISITOR_H +#define LLVM_DEBUGINFO_CODEVIEW_RANDOMACCESSTYPEVISITOR_H + +#include "llvm/ADT/TinyPtrVector.h" +#include "llvm/DebugInfo/CodeView/CVTypeVisitor.h" +#include "llvm/DebugInfo/CodeView/TypeDatabase.h" +#include "llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h" +#include "llvm/DebugInfo/CodeView/TypeDeserializer.h" +#include "llvm/DebugInfo/CodeView/TypeIndex.h" +#include "llvm/DebugInfo/CodeView/TypeRecord.h" +#include "llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h" +#include "llvm/Support/Error.h" + +namespace llvm { +namespace codeview { + +class TypeDatabase; +class TypeServerHandler; +class TypeVisitorCallbacks; + +/// \brief Provides amortized O(1) random access to a CodeView type stream. +/// Normally to access a type from a type stream, you must know its byte +/// offset into the type stream, because type records are variable-lengthed. +/// However, this is not the way we prefer to access them. For example, given +/// a symbol record one of the fields may be the TypeIndex of the symbol's +/// type record. Or given a type record such as an array type, there might +/// be a TypeIndex for the element type. Sequential access is perfect when +/// we're just dumping every entry, but it's very poor for real world usage. +/// +/// Type streams in PDBs contain an additional field which is a list of pairs +/// containing indices and their corresponding offsets, roughly every ~8KB of +/// record data. This general idea need not be confined to PDBs though. By +/// supplying such an array, the producer of a type stream can allow the +/// consumer much better access time, because the consumer can find the nearest +/// index in this array, and do a linear scan forward only from there. +/// +/// RandomAccessTypeVisitor implements this algorithm, but additionally goes one +/// step further by caching offsets of every record that has been visited at +/// least once. This way, even repeated visits of the same record will never +/// require more than one linear scan. For a type stream of N elements divided +/// into M chunks of roughly equal size, this yields a worst case lookup time +/// of O(N/M) and an amortized time of O(1). +class RandomAccessTypeVisitor { + typedef FixedStreamArray<TypeIndexOffset> PartialOffsetArray; + +public: + RandomAccessTypeVisitor(const CVTypeArray &Types, uint32_t NumRecords, + PartialOffsetArray PartialOffsets); + + Error visitTypeIndex(TypeIndex Index, TypeVisitorCallbacks &Callbacks); + + const TypeDatabase &database() const { return Database; } + +private: + Error visitRangeForType(TypeIndex TI); + Error visitRange(TypeIndex Begin, uint32_t BeginOffset, TypeIndex End); + + /// Visited records get automatically added to the type database. + TypeDatabase Database; + + /// The type array to allow random access visitation of. + const CVTypeArray &Types; + + /// The database visitor which adds new records to the database. + TypeDatabaseVisitor DatabaseVisitor; + + /// The deserializer which deserializes new records. + TypeDeserializer Deserializer; + + /// The visitation callback pipeline to use. By default this contains a + /// deserializer and a type database visitor. But the callback specified + /// in the constructor is also added. + TypeVisitorCallbackPipeline Pipeline; + + /// The visitor used to visit the internal pipeline for deserialization and + /// database maintenance. + CVTypeVisitor InternalVisitor; + + /// A vector mapping type indices to type offset. For every record that has + /// been visited, contains the absolute offset of that record in the record + /// array. + std::vector<uint32_t> KnownOffsets; + + /// An array of index offsets for the given type stream, allowing log(N) + /// lookups of a type record by index. Similar to KnownOffsets but only + /// contains offsets for some type indices, some of which may not have + /// ever been visited. + PartialOffsetArray PartialOffsets; +}; + +} // end namespace codeview +} // end namespace llvm + +#endif // LLVM_DEBUGINFO_CODEVIEW_RANDOMACCESSTYPEVISITOR_H diff --git a/include/llvm/DebugInfo/CodeView/TypeDatabase.h b/include/llvm/DebugInfo/CodeView/TypeDatabase.h index be7b19e7df0c5..92c15ebd8b2b2 100644 --- a/include/llvm/DebugInfo/CodeView/TypeDatabase.h +++ b/include/llvm/DebugInfo/CodeView/TypeDatabase.h @@ -10,6 +10,7 @@ #ifndef LLVM_DEBUGINFO_CODEVIEW_TYPEDATABASE_H #define LLVM_DEBUGINFO_CODEVIEW_TYPEDATABASE_H +#include "llvm/ADT/BitVector.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" #include "llvm/DebugInfo/CodeView/TypeIndex.h" @@ -20,14 +21,16 @@ namespace llvm { namespace codeview { class TypeDatabase { + friend class RandomAccessTypeVisitor; + public: - explicit TypeDatabase(uint32_t ExpectedSize); + explicit TypeDatabase(uint32_t Capacity); - /// Gets the type index for the next type record. - TypeIndex getNextTypeIndex() const; + /// Records the name of a type, and reserves its type index. + TypeIndex appendType(StringRef Name, const CVType &Data); /// Records the name of a type, and reserves its type index. - void recordType(StringRef Name, const CVType &Data); + void recordType(StringRef Name, TypeIndex Index, const CVType &Data); /// Saves the name in a StringSet and creates a stable StringRef. StringRef saveTypeName(StringRef TypeName); @@ -37,13 +40,21 @@ public: const CVType &getTypeRecord(TypeIndex Index) const; CVType &getTypeRecord(TypeIndex Index); - bool containsTypeIndex(TypeIndex Index) const; + bool contains(TypeIndex Index) const; uint32_t size() const; + uint32_t capacity() const; + bool empty() const; + + TypeIndex getAppendIndex() const; private: + void grow(); + BumpPtrAllocator Allocator; + uint32_t Count = 0; + /// All user defined type records in .debug$T live in here. Type indices /// greater than 0x1000 are user defined. Subtract 0x1000 from the index to /// index into this vector. @@ -51,6 +62,8 @@ private: SmallVector<CVType, 10> TypeRecords; StringSaver TypeNameStorage; + + BitVector ValidRecords; }; } } diff --git a/include/llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h b/include/llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h index 39d234cf9814d..c064e19a7e90a 100644 --- a/include/llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h +++ b/include/llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h @@ -10,6 +10,8 @@ #ifndef LLVM_DEBUGINFO_CODEVIEW_TYPEDATABASEVISITOR_H #define LLVM_DEBUGINFO_CODEVIEW_TYPEDATABASEVISITOR_H +#include "llvm/ADT/PointerUnion.h" + #include "llvm/DebugInfo/CodeView/TypeDatabase.h" #include "llvm/DebugInfo/CodeView/TypeIndex.h" #include "llvm/DebugInfo/CodeView/TypeRecord.h" @@ -21,11 +23,12 @@ namespace codeview { /// Dumper for CodeView type streams found in COFF object files and PDB files. class TypeDatabaseVisitor : public TypeVisitorCallbacks { public: - explicit TypeDatabaseVisitor(TypeDatabase &TypeDB) : TypeDB(TypeDB) {} + explicit TypeDatabaseVisitor(TypeDatabase &TypeDB) : TypeDB(&TypeDB) {} /// Paired begin/end actions for all types. Receives all record data, /// including the fixed-length record prefix. Error visitTypeBegin(CVType &Record) override; + Error visitTypeBegin(CVType &Record, TypeIndex Index) override; Error visitTypeEnd(CVType &Record) override; Error visitMemberBegin(CVMemberRecord &Record) override; Error visitMemberEnd(CVMemberRecord &Record) override; @@ -39,12 +42,18 @@ public: #include "TypeRecords.def" private: + StringRef getTypeName(TypeIndex Index) const; + StringRef saveTypeName(StringRef Name); + bool IsInFieldList = false; /// Name of the current type. Only valid before visitTypeEnd. StringRef Name; + /// Current type index. Only valid before visitTypeEnd, and if we are + /// visiting a random access type database. + Optional<TypeIndex> CurrentTypeIndex; - TypeDatabase &TypeDB; + TypeDatabase *TypeDB; }; } // end namespace codeview diff --git a/include/llvm/DebugInfo/CodeView/TypeDeserializer.h b/include/llvm/DebugInfo/CodeView/TypeDeserializer.h index 0e34437891702..2142d4a2dec70 100644 --- a/include/llvm/DebugInfo/CodeView/TypeDeserializer.h +++ b/include/llvm/DebugInfo/CodeView/TypeDeserializer.h @@ -46,6 +46,10 @@ public: return Mapping->Mapping.visitTypeBegin(Record); } + Error visitTypeBegin(CVType &Record, TypeIndex Index) override { + return visitTypeBegin(Record); + } + Error visitTypeEnd(CVType &Record) override { assert(Mapping && "Not in a type mapping!"); auto EC = Mapping->Mapping.visitTypeEnd(Record); diff --git a/include/llvm/DebugInfo/CodeView/TypeDumpVisitor.h b/include/llvm/DebugInfo/CodeView/TypeDumpVisitor.h index 00bb09137e488..6f10afb30d606 100644 --- a/include/llvm/DebugInfo/CodeView/TypeDumpVisitor.h +++ b/include/llvm/DebugInfo/CodeView/TypeDumpVisitor.h @@ -45,6 +45,7 @@ public: /// Paired begin/end actions for all types. Receives all record data, /// including the fixed-length record prefix. Error visitTypeBegin(CVType &Record) override; + Error visitTypeBegin(CVType &Record, TypeIndex Index) override; Error visitTypeEnd(CVType &Record) override; Error visitMemberBegin(CVMemberRecord &Record) override; Error visitMemberEnd(CVMemberRecord &Record) override; diff --git a/include/llvm/DebugInfo/CodeView/TypeIndex.h b/include/llvm/DebugInfo/CodeView/TypeIndex.h index 3c11d248fa721..b5d695fc49d5b 100644 --- a/include/llvm/DebugInfo/CodeView/TypeIndex.h +++ b/include/llvm/DebugInfo/CodeView/TypeIndex.h @@ -106,6 +106,15 @@ public: bool isNoneType() const { return *this == None(); } + uint32_t toArrayIndex() const { + assert(!isSimple()); + return getIndex() - FirstNonSimpleIndex; + } + + static TypeIndex fromArrayIndex(uint32_t Index) { + return TypeIndex(Index + FirstNonSimpleIndex); + } + SimpleTypeKind getSimpleKind() const { assert(isSimple()); return static_cast<SimpleTypeKind>(Index & SimpleKindMask); @@ -159,6 +168,39 @@ public: static TypeIndex Float32() { return TypeIndex(SimpleTypeKind::Float32); } static TypeIndex Float64() { return TypeIndex(SimpleTypeKind::Float64); } + TypeIndex &operator+=(unsigned N) { + Index += N; + return *this; + } + + TypeIndex &operator++() { + Index += 1; + return *this; + } + + TypeIndex operator++(int) { + TypeIndex Copy = *this; + operator++(); + return Copy; + } + + TypeIndex &operator-=(unsigned N) { + assert(Index >= N); + Index -= N; + return *this; + } + + TypeIndex &operator--() { + Index -= 1; + return *this; + } + + TypeIndex operator--(int) { + TypeIndex Copy = *this; + operator--(); + return Copy; + } + friend inline bool operator==(const TypeIndex &A, const TypeIndex &B) { return A.getIndex() == B.getIndex(); } @@ -183,10 +225,30 @@ public: return A.getIndex() >= B.getIndex(); } + friend inline TypeIndex operator+(const TypeIndex &A, uint32_t N) { + TypeIndex Result(A); + Result += N; + return Result; + } + + friend inline TypeIndex operator-(const TypeIndex &A, uint32_t N) { + assert(A.getIndex() >= N); + TypeIndex Result(A); + Result -= N; + return Result; + } + private: support::ulittle32_t Index; }; +// Used for pseudo-indexing an array of type records. An array of such records +// sorted by TypeIndex can allow log(N) lookups even though such a type record +// stream does not provide random access. +struct TypeIndexOffset { + TypeIndex Type; + support::ulittle32_t Offset; +}; } } diff --git a/include/llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h b/include/llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h index f251296910411..ed48df33249f4 100644 --- a/include/llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h +++ b/include/llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h @@ -47,6 +47,14 @@ public: return Error::success(); } + Error visitTypeBegin(CVType &Record, TypeIndex Index) override { + for (auto Visitor : Pipeline) { + if (auto EC = Visitor->visitTypeBegin(Record, Index)) + return EC; + } + return Error::success(); + } + Error visitTypeEnd(CVType &Record) override { for (auto Visitor : Pipeline) { if (auto EC = Visitor->visitTypeEnd(Record)) diff --git a/include/llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h b/include/llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h index 5e27df346b003..2950c7d27cb68 100644 --- a/include/llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h +++ b/include/llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h @@ -26,8 +26,15 @@ public: virtual Error visitUnknownType(CVType &Record) { return Error::success(); } /// Paired begin/end actions for all types. Receives all record data, /// including the fixed-length record prefix. visitTypeBegin() should return - /// the type of the Record, or an error if it cannot be determined. + /// the type of the Record, or an error if it cannot be determined. Exactly + /// one of the two visitTypeBegin methods will be called, depending on whether + /// records are being visited sequentially or randomly. An implementation + /// should be prepared to handle both (or assert if it can't handle random + /// access visitation). virtual Error visitTypeBegin(CVType &Record) { return Error::success(); } + virtual Error visitTypeBegin(CVType &Record, TypeIndex Index) { + return Error::success(); + } virtual Error visitTypeEnd(CVType &Record) { return Error::success(); } virtual Error visitUnknownMember(CVMemberRecord &Record) { diff --git a/include/llvm/DebugInfo/DWARF/DWARFContext.h b/include/llvm/DebugInfo/DWARF/DWARFContext.h index 3fae8b4414394..ca82a68ead31a 100644 --- a/include/llvm/DebugInfo/DWARF/DWARFContext.h +++ b/include/llvm/DebugInfo/DWARF/DWARFContext.h @@ -43,13 +43,6 @@ namespace llvm { class MemoryBuffer; class raw_ostream; -// In place of applying the relocations to the data we've read from disk we use -// a separate mapping table to the side and checking that at locations in the -// dwarf where we expect relocated values. This adds a bit of complexity to the -// dwarf parsing/extraction at the benefit of not allocating memory for the -// entire size of the debug info sections. -typedef DenseMap<uint64_t, std::pair<uint8_t, int64_t>> RelocAddrMap; - /// Reads a value from data extractor and applies a relocation to the result if /// one exists for the given offset. uint64_t getRelocatedValue(const DataExtractor &Data, uint32_t Size, diff --git a/include/llvm/DebugInfo/DWARF/DWARFDebugLine.h b/include/llvm/DebugInfo/DWARF/DWARFDebugLine.h index e21245b97b730..39a7ef71de97d 100644 --- a/include/llvm/DebugInfo/DWARF/DWARFDebugLine.h +++ b/include/llvm/DebugInfo/DWARF/DWARFDebugLine.h @@ -30,7 +30,7 @@ public: struct FileNameEntry { FileNameEntry() = default; - StringRef Name = StringRef(); + StringRef Name; uint64_t DirIdx = 0; uint64_t ModTime = 0; uint64_t Length = 0; diff --git a/include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h b/include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h index 9172df5bfac6f..23a573b7a9fa0 100644 --- a/include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h +++ b/include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h @@ -22,8 +22,13 @@ namespace llvm { class raw_ostream; +struct DWARFAddressRange { + uint64_t LowPC; + uint64_t HighPC; +}; + /// DWARFAddressRangesVector - represents a set of absolute address ranges. -typedef std::vector<std::pair<uint64_t, uint64_t>> DWARFAddressRangesVector; +typedef std::vector<DWARFAddressRange> DWARFAddressRangesVector; class DWARFDebugRangeList { public: diff --git a/include/llvm/DebugInfo/DWARF/DWARFRelocMap.h b/include/llvm/DebugInfo/DWARF/DWARFRelocMap.h index af01bddeed153..f1e03bb4c2e18 100644 --- a/include/llvm/DebugInfo/DWARF/DWARFRelocMap.h +++ b/include/llvm/DebugInfo/DWARF/DWARFRelocMap.h @@ -16,7 +16,17 @@ namespace llvm { -typedef DenseMap<uint64_t, std::pair<uint8_t, int64_t>> RelocAddrMap; +struct RelocAddrEntry { + uint8_t Width; + int64_t Value; +}; + +// In place of applying the relocations to the data we've read from disk we use +// a separate mapping table to the side and checking that at locations in the +// dwarf where we expect relocated values. This adds a bit of complexity to the +// dwarf parsing/extraction at the benefit of not allocating memory for the +// entire size of the debug info sections. +typedef DenseMap<uint64_t, RelocAddrEntry> RelocAddrMap; } // end namespace llvm diff --git a/include/llvm/DebugInfo/DWARF/DWARFVerifier.h b/include/llvm/DebugInfo/DWARF/DWARFVerifier.h index 8e12bcd2c8e27..b9f14be859268 100644 --- a/include/llvm/DebugInfo/DWARF/DWARFVerifier.h +++ b/include/llvm/DebugInfo/DWARF/DWARFVerifier.h @@ -40,7 +40,7 @@ class DWARFVerifier { /// /// @param Die The DWARF DIE that owns the attribute value /// @param AttrValue The DWARF attribute value to check - void verifyDebugInfoAttribute(DWARFDie &Die, DWARFAttribute &AttrValue); + void verifyDebugInfoAttribute(const DWARFDie &Die, DWARFAttribute &AttrValue); /// Verifies the attribute's DWARF form. /// @@ -51,7 +51,7 @@ class DWARFVerifier { /// /// @param Die The DWARF DIE that owns the attribute value /// @param AttrValue The DWARF attribute value to check - void verifyDebugInfoForm(DWARFDie &Die, DWARFAttribute &AttrValue); + void verifyDebugInfoForm(const DWARFDie &Die, DWARFAttribute &AttrValue); /// Verifies the all valid references that were found when iterating through /// all of the DIE attributes. @@ -60,7 +60,7 @@ class DWARFVerifier { /// offset matches. This helps to ensure if a DWARF link phase moved things /// around, that it doesn't create invalid references by failing to relocate /// CU relative and absolute references. - void veifyDebugInfoReferences(); + void verifyDebugInfoReferences(); /// Verify the the DW_AT_stmt_list encoding and value and ensure that no /// compile units that have the same DW_AT_stmt_list value. diff --git a/include/llvm/DebugInfo/PDB/Native/RawTypes.h b/include/llvm/DebugInfo/PDB/Native/RawTypes.h index 979b8454dd5ec..771272d6a47d1 100644 --- a/include/llvm/DebugInfo/PDB/Native/RawTypes.h +++ b/include/llvm/DebugInfo/PDB/Native/RawTypes.h @@ -73,13 +73,6 @@ struct SecMapEntry { support::ulittle32_t SecByteLength; // Byte count of the segment or group. }; -// Used for serialized hash table in TPI stream. -// In the reference, it is an array of TI and cbOff pair. -struct TypeIndexOffset { - codeview::TypeIndex Type; - support::ulittle32_t Offset; -}; - /// Some of the values are stored in bitfields. Since this needs to be portable /// across compilers and architectures (big / little endian in particular) we /// can't use the actual structures below, but must instead do the shifting diff --git a/include/llvm/DebugInfo/PDB/Native/TpiStream.h b/include/llvm/DebugInfo/PDB/Native/TpiStream.h index 9fef9bee5e1a4..4579cbf4227b7 100644 --- a/include/llvm/DebugInfo/PDB/Native/TpiStream.h +++ b/include/llvm/DebugInfo/PDB/Native/TpiStream.h @@ -47,7 +47,7 @@ public: uint32_t getHashKeySize() const; uint32_t getNumHashBuckets() const; FixedStreamArray<support::ulittle32_t> getHashValues() const; - FixedStreamArray<TypeIndexOffset> getTypeIndexOffsets() const; + FixedStreamArray<codeview::TypeIndexOffset> getTypeIndexOffsets() const; HashTable &getHashAdjusters(); codeview::CVTypeRange types(bool *HadError) const; @@ -62,7 +62,7 @@ private: std::unique_ptr<BinaryStream> HashStream; FixedStreamArray<support::ulittle32_t> HashValues; - FixedStreamArray<TypeIndexOffset> TypeIndexOffsets; + FixedStreamArray<codeview::TypeIndexOffset> TypeIndexOffsets; HashTable HashAdjusters; const TpiStreamHeader *Header; diff --git a/include/llvm/DebugInfo/PDB/Native/TpiStreamBuilder.h b/include/llvm/DebugInfo/PDB/Native/TpiStreamBuilder.h index a29ed0b610d36..6c609c34665ca 100644 --- a/include/llvm/DebugInfo/PDB/Native/TpiStreamBuilder.h +++ b/include/llvm/DebugInfo/PDB/Native/TpiStreamBuilder.h @@ -75,7 +75,7 @@ private: Optional<PdbRaw_TpiVer> VerHeader; std::vector<ArrayRef<uint8_t>> TypeRecords; std::vector<uint32_t> TypeHashes; - std::vector<TypeIndexOffset> TypeIndexOffsets; + std::vector<codeview::TypeIndexOffset> TypeIndexOffsets; uint32_t HashStreamIndex = kInvalidStreamIndex; std::unique_ptr<BinaryByteStream> HashValueStream; |