LLVM 22.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/StringRef.h"
19#include "llvm/Support/Error.h"
21#include <cstdint>
22#include <vector>
23
24namespace llvm {
25namespace 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 {
56 };
57
58public:
59 explicit LazyRandomTypeCollection(uint32_t RecordCountHint);
60 LazyRandomTypeCollection(StringRef Data, 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
70 uint32_t getOffsetOfType(TypeIndex Index);
71
72 std::optional<CVType> tryGetType(TypeIndex Index);
73
74 CVType getType(TypeIndex Index) override;
76 bool contains(TypeIndex Index) override;
77 uint32_t size() override;
78 uint32_t capacity() override;
79 std::optional<TypeIndex> getFirst() override;
80 std::optional<TypeIndex> getNext(TypeIndex Prev) override;
81 bool replaceType(TypeIndex &Index, CVType Data, bool Stabilize) override;
82
83private:
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
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
This file defines the BumpPtrAllocator interface.
Lightweight arrays that are backed by an arbitrary BinaryStream.
RelocType Type
Definition: COFFYAML.cpp:410
#define LLVM_ABI
Definition: Compiler.h:213
static std::string getTypeName(OverloadKind Kind, Type *Ty)
std::string Name
uint32_t Index
bool End
Definition: ELF_riscv.cpp:480
uint64_t Offset
Definition: ELF_riscv.cpp:478
Basic Register Allocator
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Definition: Value.cpp:480
static SymbolRef::Type getType(const Symbol *Sym)
Definition: TapiFile.cpp:39
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Provides read only access to a subclass of BinaryStream.
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
Lightweight error class with error context and mandatory checking.
Definition: Error.h:159
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:55
Saves strings in the provided stable storage and returns a StringRef with a stable character pointer.
Definition: StringSaver.h:22
Provides amortized O(1) random access to a CodeView type stream.
A 32-bit type reference.
Definition: TypeIndex.h:97
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1702