diff options
author | Dimitry Andric <dim@FreeBSD.org> | 2017-05-16 19:46:52 +0000 |
---|---|---|
committer | Dimitry Andric <dim@FreeBSD.org> | 2017-05-16 19:46:52 +0000 |
commit | 6b3f41ed88e8e440e11a4fbf20b6600529f80049 (patch) | |
tree | 928b056f24a634d628c80238dbbf10d41b1a71d5 /include/llvm/DebugInfo/CodeView | |
parent | c46e6a5940c50058e00c0c5f9123fd82e338d29a (diff) |
Diffstat (limited to 'include/llvm/DebugInfo/CodeView')
9 files changed, 219 insertions, 8 deletions
diff --git a/include/llvm/DebugInfo/CodeView/CVTypeVisitor.h b/include/llvm/DebugInfo/CodeView/CVTypeVisitor.h index e9012db7602d..f3122f0bf7f0 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 000000000000..35a8010f1163 --- /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 be7b19e7df0c..92c15ebd8b2b 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 39d234cf9814..c064e19a7e90 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 0e3443789170..2142d4a2dec7 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 00bb09137e48..6f10afb30d60 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 3c11d248fa72..b5d695fc49d5 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 f25129691041..ed48df33249f 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 5e27df346b00..2950c7d27cb6 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) { |