LLVM  7.0.0svn
LazyRandomTypeCollection.h
Go to the documentation of this file.
1 //===- LazyRandomTypeCollection.h -------------------------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #ifndef LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
11 #define LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
12 
13 #include "llvm/ADT/ArrayRef.h"
14 #include "llvm/ADT/Optional.h"
15 #include "llvm/ADT/StringRef.h"
19 #include "llvm/Support/Allocator.h"
21 #include "llvm/Support/Error.h"
23 #include <cstdint>
24 #include <vector>
25 
26 namespace llvm {
27 namespace codeview {
28 
29 /// \brief Provides amortized O(1) random access to a CodeView type stream.
30 /// Normally to access a type from a type stream, you must know its byte
31 /// offset into the type stream, because type records are variable-lengthed.
32 /// However, this is not the way we prefer to access them. For example, given
33 /// a symbol record one of the fields may be the TypeIndex of the symbol's
34 /// type record. Or given a type record such as an array type, there might
35 /// be a TypeIndex for the element type. Sequential access is perfect when
36 /// we're just dumping every entry, but it's very poor for real world usage.
37 ///
38 /// Type streams in PDBs contain an additional field which is a list of pairs
39 /// containing indices and their corresponding offsets, roughly every ~8KB of
40 /// record data. This general idea need not be confined to PDBs though. By
41 /// supplying such an array, the producer of a type stream can allow the
42 /// consumer much better access time, because the consumer can find the nearest
43 /// index in this array, and do a linear scan forward only from there.
44 ///
45 /// LazyRandomTypeCollection implements this algorithm, but additionally goes
46 /// one step further by caching offsets of every record that has been visited at
47 /// least once. This way, even repeated visits of the same record will never
48 /// require more than one linear scan. For a type stream of N elements divided
49 /// into M chunks of roughly equal size, this yields a worst case lookup time
50 /// of O(N/M) and an amortized time of O(1).
53 
54  struct CacheEntry {
55  CVType Type;
58  };
59 
60 public:
61  explicit LazyRandomTypeCollection(uint32_t RecordCountHint);
64  LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint,
65  PartialOffsetArray PartialOffsets);
66  LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint);
67 
68  void reset(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
69  void reset(StringRef Data, uint32_t RecordCountHint);
70  void reset(BinaryStreamReader &Reader, uint32_t RecordCountHint);
71 
73 
75 
76  CVType getType(TypeIndex Index) override;
77  StringRef getTypeName(TypeIndex Index) override;
78  bool contains(TypeIndex Index) override;
79  uint32_t size() override;
80  uint32_t capacity() override;
81  Optional<TypeIndex> getFirst() override;
82  Optional<TypeIndex> getNext(TypeIndex Prev) override;
83 
84 private:
85  Error ensureTypeExists(TypeIndex Index);
86  void ensureCapacityFor(TypeIndex Index);
87 
88  Error visitRangeForType(TypeIndex TI);
89  Error fullScanForType(TypeIndex TI);
90  void visitRange(TypeIndex Begin, uint32_t BeginOffset, TypeIndex End);
91 
92  /// Number of actual records.
93  uint32_t Count = 0;
94 
95  /// The largest type index which we've visited.
96  TypeIndex LargestTypeIndex = TypeIndex::None();
97 
99  StringSaver NameStorage;
100 
101  /// The type array to allow random access visitation of.
102  CVTypeArray Types;
103 
104  std::vector<CacheEntry> Records;
105 
106  /// An array of index offsets for the given type stream, allowing log(N)
107  /// lookups of a type record by index. Similar to KnownOffsets but only
108  /// contains offsets for some type indices, some of which may not have
109  /// ever been visited.
110  PartialOffsetArray PartialOffsets;
111 };
112 
113 } // end namespace codeview
114 } // end namespace llvm
115 
116 #endif // LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
Optional< TypeIndex > getNext(TypeIndex Prev) override
void reset(ArrayRef< uint8_t > Data, uint32_t RecordCountHint)
A 32-bit type reference.
Definition: TypeIndex.h:96
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:138
Optional< CVType > tryGetType(TypeIndex Index)
static const unsigned End
StringRef getTypeName(TypeIndex Index) override
Basic Register Allocator
Saves strings in the inheritor&#39;s stable storage and returns a StringRef with a stable character point...
Definition: StringSaver.h:21
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
Provides read only access to a subclass of BinaryStream.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
static TypeIndex None()
Definition: TypeIndex.h:137
Provides amortized O(1) random access to a CodeView type stream.