LLVM  16.0.0git
LazyRandomTypeCollection.cpp
Go to the documentation of this file.
1 //===- LazyRandomTypeCollection.cpp ---------------------------------------===//
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 
10 #include "llvm/ADT/ArrayRef.h"
11 #include "llvm/ADT/None.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/ADT/StringRef.h"
19 #include "llvm/Support/Endian.h"
20 #include "llvm/Support/Error.h"
21 #include <algorithm>
22 #include <cassert>
23 #include <cstdint>
24 #include <iterator>
25 
26 using namespace llvm;
27 using namespace llvm::codeview;
28 
29 static void error(Error &&EC) {
30  assert(!static_cast<bool>(EC));
31  if (EC)
33 }
34 
36  : LazyRandomTypeCollection(CVTypeArray(), RecordCountHint,
37  PartialOffsetArray()) {}
38 
40  const CVTypeArray &Types, uint32_t RecordCountHint,
41  PartialOffsetArray PartialOffsets)
42  : NameStorage(Allocator), Types(Types), PartialOffsets(PartialOffsets) {
43  Records.resize(RecordCountHint);
44 }
45 
47  uint32_t RecordCountHint)
48  : LazyRandomTypeCollection(RecordCountHint) {
49 }
50 
52  uint32_t RecordCountHint)
54  makeArrayRef(Data.bytes_begin(), Data.bytes_end()), RecordCountHint) {
55 }
56 
58  uint32_t NumRecords)
59  : LazyRandomTypeCollection(Types, NumRecords, PartialOffsetArray()) {}
60 
62  uint32_t RecordCountHint) {
63  Count = 0;
64  PartialOffsets = PartialOffsetArray();
65 
66  error(Reader.readArray(Types, Reader.bytesRemaining()));
67 
68  // Clear and then resize, to make sure existing data gets destroyed.
69  Records.clear();
70  Records.resize(RecordCountHint);
71 }
72 
73 void LazyRandomTypeCollection::reset(StringRef Data, uint32_t RecordCountHint) {
75  reset(Reader, RecordCountHint);
76 }
77 
79  uint32_t RecordCountHint) {
81  reset(Reader, RecordCountHint);
82 }
83 
85  error(ensureTypeExists(Index));
87 
88  return Records[Index.toArrayIndex()].Offset;
89 }
90 
92  assert(!Index.isSimple());
93 
94  auto EC = ensureTypeExists(Index);
95  error(std::move(EC));
97 
98  return Records[Index.toArrayIndex()].Type;
99 }
100 
102  if (Index.isSimple())
103  return std::nullopt;
104 
105  if (auto EC = ensureTypeExists(Index)) {
107  return std::nullopt;
108  }
109 
111  return Records[Index.toArrayIndex()].Type;
112 }
113 
115  if (Index.isNoneType() || Index.isSimple())
117 
118  // Try to make sure the type exists. Even if it doesn't though, it may be
119  // because we're dumping a symbol stream with no corresponding type stream
120  // present, in which case we still want to be able to print <unknown UDT>
121  // for the type names.
122  if (auto EC = ensureTypeExists(Index)) {
124  return "<unknown UDT>";
125  }
126 
127  uint32_t I = Index.toArrayIndex();
128  ensureCapacityFor(Index);
129  if (Records[I].Name.data() == nullptr) {
130  StringRef Result = NameStorage.save(computeTypeName(*this, Index));
131  Records[I].Name = Result;
132  }
133  return Records[I].Name;
134 }
135 
137  if (Index.isSimple() || Index.isNoneType())
138  return false;
139 
140  if (Records.size() <= Index.toArrayIndex())
141  return false;
142  if (!Records[Index.toArrayIndex()].Type.valid())
143  return false;
144  return true;
145 }
146 
148 
149 uint32_t LazyRandomTypeCollection::capacity() { return Records.size(); }
150 
151 Error LazyRandomTypeCollection::ensureTypeExists(TypeIndex TI) {
152  if (contains(TI))
153  return Error::success();
154 
155  return visitRangeForType(TI);
156 }
157 
158 void LazyRandomTypeCollection::ensureCapacityFor(TypeIndex Index) {
159  assert(!Index.isSimple());
160  uint32_t MinSize = Index.toArrayIndex() + 1;
161 
162  if (MinSize <= capacity())
163  return;
164 
165  uint32_t NewCapacity = MinSize * 3 / 2;
166 
167  assert(NewCapacity > capacity());
168  Records.resize(NewCapacity);
169 }
170 
171 Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
172  assert(!TI.isSimple());
173  if (PartialOffsets.empty())
174  return fullScanForType(TI);
175 
176  auto Next = llvm::upper_bound(PartialOffsets, TI,
177  [](TypeIndex Value, const TypeIndexOffset &IO) {
178  return Value < IO.Type;
179  });
180 
181  assert(Next != PartialOffsets.begin());
182  auto Prev = std::prev(Next);
183 
184  TypeIndex TIB = Prev->Type;
185  if (contains(TIB)) {
186  // They've asked us to fetch a type index, but the entry we found in the
187  // partial offsets array has already been visited. Since we visit an entire
188  // block every time, that means this record should have been previously
189  // discovered. Ultimately, this means this is a request for a non-existent
190  // type index.
191  return make_error<CodeViewError>("Invalid type index");
192  }
193 
194  TypeIndex TIE;
195  if (Next == PartialOffsets.end()) {
197  } else {
198  TIE = Next->Type;
199  }
200 
201  visitRange(TIB, Prev->Offset, TIE);
202  return Error::success();
203 }
204 
205 std::optional<TypeIndex> LazyRandomTypeCollection::getFirst() {
207  if (auto EC = ensureTypeExists(TI)) {
209  return std::nullopt;
210  }
211  return TI;
212 }
213 
214 std::optional<TypeIndex> LazyRandomTypeCollection::getNext(TypeIndex Prev) {
215  // We can't be sure how long this type stream is, given that the initial count
216  // given to the constructor is just a hint. So just try to make sure the next
217  // record exists, and if anything goes wrong, we must be at the end.
218  if (auto EC = ensureTypeExists(Prev + 1)) {
220  return std::nullopt;
221  }
222 
223  return Prev + 1;
224 }
225 
226 Error LazyRandomTypeCollection::fullScanForType(TypeIndex TI) {
227  assert(!TI.isSimple());
228  assert(PartialOffsets.empty());
229 
230  TypeIndex CurrentTI = TypeIndex::fromArrayIndex(0);
231  auto Begin = Types.begin();
232 
233  if (Count > 0) {
234  // In the case of type streams which we don't know the number of records of,
235  // it's possible to search for a type index triggering a full scan, but then
236  // later additional records are added since we didn't know how many there
237  // would be until we did a full visitation, then you try to access the new
238  // type triggering another full scan. To avoid this, we assume that if the
239  // database has some records, this must be what's going on. We can also
240  // assume that this index must be larger than the largest type index we've
241  // visited, so we start from there and scan forward.
242  uint32_t Offset = Records[LargestTypeIndex.toArrayIndex()].Offset;
243  CurrentTI = LargestTypeIndex + 1;
244  Begin = Types.at(Offset);
245  ++Begin;
246  }
247 
248  auto End = Types.end();
249  while (Begin != End) {
250  ensureCapacityFor(CurrentTI);
251  LargestTypeIndex = std::max(LargestTypeIndex, CurrentTI);
252  auto Idx = CurrentTI.toArrayIndex();
253  Records[Idx].Type = *Begin;
254  Records[Idx].Offset = Begin.offset();
255  ++Count;
256  ++Begin;
257  ++CurrentTI;
258  }
259  if (CurrentTI <= TI) {
260  return make_error<CodeViewError>("Type Index does not exist!");
261  }
262  return Error::success();
263 }
264 
265 void LazyRandomTypeCollection::visitRange(TypeIndex Begin, uint32_t BeginOffset,
266  TypeIndex End) {
267  auto RI = Types.at(BeginOffset);
268  assert(RI != Types.end());
269 
270  ensureCapacityFor(End);
271  while (Begin != End) {
272  LargestTypeIndex = std::max(LargestTypeIndex, Begin);
273  auto Idx = Begin.toArrayIndex();
274  Records[Idx].Type = *RI;
275  Records[Idx].Offset = RI.offset();
276  ++Count;
277  ++Begin;
278  ++RI;
279  }
280 }
281 
283  bool Stabilize) {
284  llvm_unreachable("Method cannot be called");
285 }
BinaryStreamReader.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::upper_bound
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1935
llvm::codeview::computeTypeName
std::string computeTypeName(TypeCollection &Types, TypeIndex Index)
Definition: RecordName.cpp:254
llvm::FixedStreamArray::empty
bool empty() const
Definition: BinaryStreamArray.h:297
RecordSerialization.h
StringRef.h
llvm::codeview::TypeIndex::fromArrayIndex
static TypeIndex fromArrayIndex(uint32_t Index)
Definition: TypeIndex.h:123
llvm::codeview::LazyRandomTypeCollection::contains
bool contains(TypeIndex Index) override
Definition: LazyRandomTypeCollection.cpp:136
llvm::Error::success
static ErrorSuccess success()
Create a success value.
Definition: Error.h:329
llvm::codeview::LazyRandomTypeCollection::getNext
std::optional< TypeIndex > getNext(TypeIndex Prev) override
Definition: LazyRandomTypeCollection.cpp:214
Error.h
llvm::codeview::LazyRandomTypeCollection::getFirst
std::optional< TypeIndex > getFirst() override
Definition: LazyRandomTypeCollection.cpp:205
llvm::BinaryStreamReader::bytesRemaining
uint64_t bytesRemaining() const
Definition: BinaryStreamReader.h:250
RecordName.h
llvm::VarStreamArray::end
Iterator end() const
Definition: BinaryStreamArray.h:117
error
static void error(Error &&EC)
Definition: LazyRandomTypeCollection.cpp:29
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
STLExtras.h
llvm::FixedStreamArray< TypeIndexOffset >
llvm::codeview::LazyRandomTypeCollection::capacity
uint32_t capacity() override
Definition: LazyRandomTypeCollection.cpp:149
llvm::consumeError
void consumeError(Error Err)
Consume a Error without doing anything.
Definition: Error.h:1042
llvm::Data
@ Data
Definition: SIMachineScheduler.h:55
llvm::codeview::LazyRandomTypeCollection::getTypeName
StringRef getTypeName(TypeIndex Index) override
Definition: LazyRandomTypeCollection.cpp:114
llvm::support::little
@ little
Definition: Endian.h:27
llvm::codeview::LazyRandomTypeCollection::getOffsetOfType
uint32_t getOffsetOfType(TypeIndex Index)
Definition: LazyRandomTypeCollection.cpp:84
llvm::codeview::LazyRandomTypeCollection::tryGetType
std::optional< CVType > tryGetType(TypeIndex Index)
Definition: LazyRandomTypeCollection.cpp:101
LazyRandomTypeCollection.h
llvm::VarStreamArray< CVType >
llvm::codeview::LazyRandomTypeCollection
Provides amortized O(1) random access to a CodeView type stream.
Definition: LazyRandomTypeCollection.h:48
llvm::dwarf::Index
Index
Definition: Dwarf.h:490
llvm::FixedStreamArray::begin
FixedStreamArrayIterator< T > begin() const
Definition: BinaryStreamArray.h:299
CodeView.h
llvm::BinaryStreamReader
Provides read only access to a subclass of BinaryStream.
Definition: BinaryStreamReader.h:29
llvm::codeview::LazyRandomTypeCollection::replaceType
bool replaceType(TypeIndex &Index, CVType Data, bool Stabilize) override
Definition: LazyRandomTypeCollection.cpp:282
llvm::codeview::LazyRandomTypeCollection::LazyRandomTypeCollection
LazyRandomTypeCollection(uint32_t RecordCountHint)
Definition: LazyRandomTypeCollection.cpp:35
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
I
#define I(x, y, z)
Definition: MD5.cpp:58
ArrayRef.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::FixedStreamArray::end
FixedStreamArrayIterator< T > end() const
Definition: BinaryStreamArray.h:303
llvm::codeview::CompileSym2Flags::EC
@ EC
llvm::codeview::LazyRandomTypeCollection::reset
void reset(ArrayRef< uint8_t > Data, uint32_t RecordCountHint)
Definition: LazyRandomTypeCollection.cpp:78
llvm::codeview::TypeIndexOffset::Type
TypeIndex Type
Definition: TypeIndex.h:283
llvm::ArrayRef< uint8_t >
None.h
llvm::codeview::TypeIndex::simpleTypeName
static StringRef simpleTypeName(TypeIndex TI)
Definition: TypeIndex.cpp:71
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::codeview::TypeIndex::toArrayIndex
uint32_t toArrayIndex() const
Definition: TypeIndex.h:118
llvm::codeview::CVRecord< TypeLeafKind >
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
uint32_t
llvm::VarStreamArray::begin
Iterator begin(bool *HadError=nullptr) const
Definition: BinaryStreamArray.h:108
llvm::codeview::LazyRandomTypeCollection::size
uint32_t size() override
Definition: LazyRandomTypeCollection.cpp:147
llvm::Error
Lightweight error class with error context and mandatory checking.
Definition: Error.h:155
llvm::codeview
Definition: AppendingTypeTableBuilder.h:22
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:475
llvm::codeview::TypeIndex::isSimple
bool isSimple() const
Definition: TypeIndex.h:113
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:143
llvm::StringSaver::save
StringRef save(const char *S)
Definition: StringSaver.h:30
llvm::VarStreamArray::at
Iterator at(uint32_t Offset) const
given an offset into the array's underlying stream, return an iterator to the record at that offset.
Definition: BinaryStreamArray.h:134
llvm::codeview::TypeIndex
A 32-bit type reference.
Definition: TypeIndex.h:96
CodeViewError.h
llvm::codeview::TypeIndexOffset
Definition: TypeIndex.h:282
llvm::codeview::LazyRandomTypeCollection::getType
CVType getType(TypeIndex Index) override
Definition: LazyRandomTypeCollection.cpp:91
Endian.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::BinaryStreamReader::readArray
Error readArray(ArrayRef< T > &Array, uint32_t NumElements)
Get a reference to a NumElements element array of objects of type T from the underlying stream as if ...
Definition: BinaryStreamReader.h:180