summaryrefslogtreecommitdiff
path: root/include/llvm/DebugInfo/CodeView
diff options
context:
space:
mode:
authorDimitry Andric <dim@FreeBSD.org>2017-05-16 19:46:52 +0000
committerDimitry Andric <dim@FreeBSD.org>2017-05-16 19:46:52 +0000
commit6b3f41ed88e8e440e11a4fbf20b6600529f80049 (patch)
tree928b056f24a634d628c80238dbbf10d41b1a71d5 /include/llvm/DebugInfo/CodeView
parentc46e6a5940c50058e00c0c5f9123fd82e338d29a (diff)
Diffstat (limited to 'include/llvm/DebugInfo/CodeView')
-rw-r--r--include/llvm/DebugInfo/CodeView/CVTypeVisitor.h4
-rw-r--r--include/llvm/DebugInfo/CodeView/RandomAccessTypeVisitor.h103
-rw-r--r--include/llvm/DebugInfo/CodeView/TypeDatabase.h23
-rw-r--r--include/llvm/DebugInfo/CodeView/TypeDatabaseVisitor.h13
-rw-r--r--include/llvm/DebugInfo/CodeView/TypeDeserializer.h4
-rw-r--r--include/llvm/DebugInfo/CodeView/TypeDumpVisitor.h1
-rw-r--r--include/llvm/DebugInfo/CodeView/TypeIndex.h62
-rw-r--r--include/llvm/DebugInfo/CodeView/TypeVisitorCallbackPipeline.h8
-rw-r--r--include/llvm/DebugInfo/CodeView/TypeVisitorCallbacks.h9
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) {