LLVM 20.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"
18#include "llvm/Support/Error.h"
20#include <cstdint>
21#include <vector>
22
23namespace llvm {
24namespace codeview {
25
26/// Provides amortized O(1) random access to a CodeView type stream.
27/// Normally to access a type from a type stream, you must know its byte
28/// offset into the type stream, because type records are variable-lengthed.
29/// However, this is not the way we prefer to access them. For example, given
30/// a symbol record one of the fields may be the TypeIndex of the symbol's
31/// type record. Or given a type record such as an array type, there might
32/// be a TypeIndex for the element type. Sequential access is perfect when
33/// we're just dumping every entry, but it's very poor for real world usage.
34///
35/// Type streams in PDBs contain an additional field which is a list of pairs
36/// containing indices and their corresponding offsets, roughly every ~8KB of
37/// record data. This general idea need not be confined to PDBs though. By
38/// supplying such an array, the producer of a type stream can allow the
39/// consumer much better access time, because the consumer can find the nearest
40/// index in this array, and do a linear scan forward only from there.
41///
42/// LazyRandomTypeCollection implements this algorithm, but additionally goes
43/// one step further by caching offsets of every record that has been visited at
44/// least once. This way, even repeated visits of the same record will never
45/// require more than one linear scan. For a type stream of N elements divided
46/// into M chunks of roughly equal size, this yields a worst case lookup time
47/// of O(N/M) and an amortized time of O(1).
50
51 struct CacheEntry {
53 uint32_t Offset;
54 StringRef Name;
55 };
56
57public:
58 explicit LazyRandomTypeCollection(uint32_t RecordCountHint);
61 LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint,
62 PartialOffsetArray PartialOffsets);
63 LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint);
64
65 void reset(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
66 void reset(StringRef Data, uint32_t RecordCountHint);
67 void reset(BinaryStreamReader &Reader, uint32_t RecordCountHint);
68
70
71 std::optional<CVType> tryGetType(TypeIndex Index);
72
73 CVType getType(TypeIndex Index) override;
75 bool contains(TypeIndex Index) override;
76 uint32_t size() override;
77 uint32_t capacity() override;
78 std::optional<TypeIndex> getFirst() override;
79 std::optional<TypeIndex> getNext(TypeIndex Prev) override;
80 bool replaceType(TypeIndex &Index, CVType Data, bool Stabilize) override;
81
82private:
83 Error ensureTypeExists(TypeIndex Index);
84 void ensureCapacityFor(TypeIndex Index);
85
86 Error visitRangeForType(TypeIndex TI);
87 Error fullScanForType(TypeIndex TI);
88 void visitRange(TypeIndex Begin, uint32_t BeginOffset, TypeIndex End);
89
90 /// Number of actual records.
91 uint32_t Count = 0;
92
93 /// The largest type index which we've visited.
94 TypeIndex LargestTypeIndex = TypeIndex::None();
95
96 BumpPtrAllocator Allocator;
97 StringSaver NameStorage;
98
99 /// The type array to allow random access visitation of.
100 CVTypeArray Types;
101
102 std::vector<CacheEntry> Records;
103
104 /// An array of index offsets for the given type stream, allowing log(N)
105 /// lookups of a type record by index. Similar to KnownOffsets but only
106 /// contains offsets for some type indices, some of which may not have
107 /// ever been visited.
108 PartialOffsetArray PartialOffsets;
109};
110
111} // end namespace codeview
112} // end namespace llvm
113
114#endif // LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
This file defines the BumpPtrAllocator interface.
Lightweight arrays that are backed by an arbitrary BinaryStream.
bool End
Definition: ELF_riscv.cpp:480
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:66
Lightweight error class with error context and mandatory checking.
Definition: Error.h:160
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Saves strings in the provided stable storage and returns a StringRef with a stable character pointer.
Definition: StringSaver.h:21
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Provides amortized O(1) random access to a CodeView type stream.
std::optional< TypeIndex > getNext(TypeIndex Prev) override
std::optional< CVType > tryGetType(TypeIndex Index)
bool replaceType(TypeIndex &Index, CVType Data, bool Stabilize) override
std::optional< TypeIndex > getFirst() override
void reset(ArrayRef< uint8_t > Data, uint32_t RecordCountHint)
A 32-bit type reference.
Definition: TypeIndex.h:96
static TypeIndex None()
Definition: TypeIndex.h:148
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
StringRef getTypeName()
We provide a function which tries to compute the (demangled) name of a type statically.
Definition: TypeName.h:27