LLVM  14.0.0git
LazyRandomTypeCollection.h
Go to the documentation of this file.
1 //===- LazyRandomTypeCollection.h -------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
10 #define LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
11 
12 #include "llvm/ADT/ArrayRef.h"
13 #include "llvm/ADT/Optional.h"
14 #include "llvm/ADT/StringRef.h"
17 #include "llvm/Support/Allocator.h"
19 #include "llvm/Support/Error.h"
21 #include <cstdint>
22 #include <vector>
23 
24 namespace llvm {
25 namespace codeview {
26 
27 /// Provides amortized O(1) random access to a CodeView type stream.
28 /// Normally to access a type from a type stream, you must know its byte
29 /// offset into the type stream, because type records are variable-lengthed.
30 /// However, this is not the way we prefer to access them. For example, given
31 /// a symbol record one of the fields may be the TypeIndex of the symbol's
32 /// type record. Or given a type record such as an array type, there might
33 /// be a TypeIndex for the element type. Sequential access is perfect when
34 /// we're just dumping every entry, but it's very poor for real world usage.
35 ///
36 /// Type streams in PDBs contain an additional field which is a list of pairs
37 /// containing indices and their corresponding offsets, roughly every ~8KB of
38 /// record data. This general idea need not be confined to PDBs though. By
39 /// supplying such an array, the producer of a type stream can allow the
40 /// consumer much better access time, because the consumer can find the nearest
41 /// index in this array, and do a linear scan forward only from there.
42 ///
43 /// LazyRandomTypeCollection implements this algorithm, but additionally goes
44 /// one step further by caching offsets of every record that has been visited at
45 /// least once. This way, even repeated visits of the same record will never
46 /// require more than one linear scan. For a type stream of N elements divided
47 /// into M chunks of roughly equal size, this yields a worst case lookup time
48 /// of O(N/M) and an amortized time of O(1).
51 
52  struct CacheEntry {
53  CVType Type;
56  };
57 
58 public:
59  explicit LazyRandomTypeCollection(uint32_t RecordCountHint);
62  LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint,
63  PartialOffsetArray PartialOffsets);
64  LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint);
65 
66  void reset(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
67  void reset(StringRef Data, uint32_t RecordCountHint);
68  void reset(BinaryStreamReader &Reader, uint32_t RecordCountHint);
69 
71 
73 
74  CVType getType(TypeIndex Index) override;
76  bool contains(TypeIndex Index) override;
77  uint32_t size() override;
78  uint32_t capacity() override;
79  Optional<TypeIndex> getFirst() override;
80  Optional<TypeIndex> getNext(TypeIndex Prev) override;
81  bool replaceType(TypeIndex &Index, CVType Data, bool Stabilize) override;
82 
83 private:
84  Error ensureTypeExists(TypeIndex Index);
85  void ensureCapacityFor(TypeIndex Index);
86 
87  Error visitRangeForType(TypeIndex TI);
88  Error fullScanForType(TypeIndex TI);
89  void visitRange(TypeIndex Begin, uint32_t BeginOffset, TypeIndex End);
90 
91  /// Number of actual records.
92  uint32_t Count = 0;
93 
94  /// The largest type index which we've visited.
95  TypeIndex LargestTypeIndex = TypeIndex::None();
96 
97  BumpPtrAllocator Allocator;
98  StringSaver NameStorage;
99 
100  /// The type array to allow random access visitation of.
101  CVTypeArray Types;
102 
103  std::vector<CacheEntry> Records;
104 
105  /// An array of index offsets for the given type stream, allowing log(N)
106  /// lookups of a type record by index. Similar to KnownOffsets but only
107  /// contains offsets for some type indices, some of which may not have
108  /// ever been visited.
109  PartialOffsetArray PartialOffsets;
110 };
111 
112 } // end namespace codeview
113 } // end namespace llvm
114 
115 #endif // LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
Optional.h
StringRef.h
llvm::codeview::LazyRandomTypeCollection::contains
bool contains(TypeIndex Index) override
Definition: LazyRandomTypeCollection.cpp:135
Allocator.h
Error.h
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::Optional
Definition: APInt.h:33
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::FixedStreamArray< TypeIndexOffset >
llvm::codeview::LazyRandomTypeCollection::capacity
uint32_t capacity() override
Definition: LazyRandomTypeCollection.cpp:148
llvm::Data
@ Data
Definition: SIMachineScheduler.h:55
llvm::codeview::TypeIndex::None
static TypeIndex None()
Definition: TypeIndex.h:148
llvm::codeview::LazyRandomTypeCollection::getTypeName
StringRef getTypeName(TypeIndex Index) override
Definition: LazyRandomTypeCollection.cpp:113
llvm::codeview::LazyRandomTypeCollection::getOffsetOfType
uint32_t getOffsetOfType(TypeIndex Index)
Definition: LazyRandomTypeCollection.cpp:83
llvm::VarStreamArray< CVType >
llvm::codeview::LazyRandomTypeCollection
Provides amortized O(1) random access to a CodeView type stream.
Definition: LazyRandomTypeCollection.h:49
llvm::codeview::TypeCollection
Definition: TypeCollection.h:18
llvm::BinaryStreamReader
Provides read only access to a subclass of BinaryStream.
Definition: BinaryStreamReader.h:31
StringSaver.h
llvm::codeview::LazyRandomTypeCollection::replaceType
bool replaceType(TypeIndex &Index, CVType Data, bool Stabilize) override
Definition: LazyRandomTypeCollection.cpp:281
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::codeview::LazyRandomTypeCollection::LazyRandomTypeCollection
LazyRandomTypeCollection(uint32_t RecordCountHint)
Definition: LazyRandomTypeCollection.cpp:34
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
ArrayRef.h
BinaryStreamArray.h
llvm::codeview::LazyRandomTypeCollection::reset
void reset(ArrayRef< uint8_t > Data, uint32_t RecordCountHint)
Definition: LazyRandomTypeCollection.cpp:77
llvm::StringSaver
Saves strings in the provided stable storage and returns a StringRef with a stable character pointer.
Definition: StringSaver.h:21
llvm::ArrayRef< uint8_t >
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::codeview::CVRecord< TypeLeafKind >
uint32_t
llvm::codeview::LazyRandomTypeCollection::getNext
Optional< TypeIndex > getNext(TypeIndex Prev) override
Definition: LazyRandomTypeCollection.cpp:213
llvm::codeview::LazyRandomTypeCollection::size
uint32_t size() override
Definition: LazyRandomTypeCollection.cpp:146
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::Error
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
llvm::codeview::LazyRandomTypeCollection::tryGetType
Optional< CVType > tryGetType(TypeIndex Index)
Definition: LazyRandomTypeCollection.cpp:100
TypeCollection.h
TypeIndex.h
llvm::codeview::TypeIndex
A 32-bit type reference.
Definition: TypeIndex.h:96
llvm::codeview::LazyRandomTypeCollection::getFirst
Optional< TypeIndex > getFirst() override
Definition: LazyRandomTypeCollection.cpp:204
llvm::codeview::LazyRandomTypeCollection::getType
CVType getType(TypeIndex Index) override
Definition: LazyRandomTypeCollection.cpp:90