LLVM  10.0.0svn
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/StringExtras.h"
13 #include "llvm/ADT/StringRef.h"
18 #include "llvm/Support/Endian.h"
19 #include "llvm/Support/Error.h"
20 #include <algorithm>
21 #include <cassert>
22 #include <cstdint>
23 #include <iterator>
24 
25 using namespace llvm;
26 using namespace llvm::codeview;
27 
28 static void error(Error &&EC) {
29  assert(!static_cast<bool>(EC));
30  if (EC)
31  consumeError(std::move(EC));
32 }
33 
35  : LazyRandomTypeCollection(CVTypeArray(), RecordCountHint,
36  PartialOffsetArray()) {}
37 
39  const CVTypeArray &Types, uint32_t RecordCountHint,
40  PartialOffsetArray PartialOffsets)
41  : NameStorage(Allocator), Types(Types), PartialOffsets(PartialOffsets) {
42  Records.resize(RecordCountHint);
43 }
44 
46  uint32_t RecordCountHint)
47  : LazyRandomTypeCollection(RecordCountHint) {
48 }
49 
51  uint32_t RecordCountHint)
53  makeArrayRef(Data.bytes_begin(), Data.bytes_end()), RecordCountHint) {
54 }
55 
57  uint32_t NumRecords)
58  : LazyRandomTypeCollection(Types, NumRecords, PartialOffsetArray()) {}
59 
61  uint32_t RecordCountHint) {
62  Count = 0;
63  PartialOffsets = PartialOffsetArray();
64 
65  error(Reader.readArray(Types, Reader.bytesRemaining()));
66 
67  // Clear and then resize, to make sure existing data gets destroyed.
68  Records.clear();
69  Records.resize(RecordCountHint);
70 }
71 
72 void LazyRandomTypeCollection::reset(StringRef Data, uint32_t RecordCountHint) {
73  BinaryStreamReader Reader(Data, support::little);
74  reset(Reader, RecordCountHint);
75 }
76 
78  uint32_t RecordCountHint) {
79  BinaryStreamReader Reader(Data, support::little);
80  reset(Reader, RecordCountHint);
81 }
82 
84  error(ensureTypeExists(Index));
85  assert(contains(Index));
86 
87  return Records[Index.toArrayIndex()].Offset;
88 }
89 
91  assert(!Index.isSimple());
92 
93  auto EC = ensureTypeExists(Index);
94  error(std::move(EC));
95  assert(contains(Index));
96 
97  return Records[Index.toArrayIndex()].Type;
98 }
99 
101  if (Index.isSimple())
102  return None;
103 
104  if (auto EC = ensureTypeExists(Index)) {
105  consumeError(std::move(EC));
106  return None;
107  }
108 
109  assert(contains(Index));
110  return Records[Index.toArrayIndex()].Type;
111 }
112 
114  if (Index.isNoneType() || Index.isSimple())
115  return TypeIndex::simpleTypeName(Index);
116 
117  // Try to make sure the type exists. Even if it doesn't though, it may be
118  // because we're dumping a symbol stream with no corresponding type stream
119  // present, in which case we still want to be able to print <unknown UDT>
120  // for the type names.
121  if (auto EC = ensureTypeExists(Index)) {
122  consumeError(std::move(EC));
123  return "<unknown UDT>";
124  }
125 
126  uint32_t I = Index.toArrayIndex();
127  ensureCapacityFor(Index);
128  if (Records[I].Name.data() == nullptr) {
129  StringRef Result = NameStorage.save(computeTypeName(*this, Index));
130  Records[I].Name = Result;
131  }
132  return Records[I].Name;
133 }
134 
136  if (Index.isSimple() || Index.isNoneType())
137  return false;
138 
139  if (Records.size() <= Index.toArrayIndex())
140  return false;
141  if (!Records[Index.toArrayIndex()].Type.valid())
142  return false;
143  return true;
144 }
145 
147 
148 uint32_t LazyRandomTypeCollection::capacity() { return Records.size(); }
149 
150 Error LazyRandomTypeCollection::ensureTypeExists(TypeIndex TI) {
151  if (contains(TI))
152  return Error::success();
153 
154  return visitRangeForType(TI);
155 }
156 
157 void LazyRandomTypeCollection::ensureCapacityFor(TypeIndex Index) {
158  assert(!Index.isSimple());
159  uint32_t MinSize = Index.toArrayIndex() + 1;
160 
161  if (MinSize <= capacity())
162  return;
163 
164  uint32_t NewCapacity = MinSize * 3 / 2;
165 
166  assert(NewCapacity > capacity());
167  Records.resize(NewCapacity);
168 }
169 
170 Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
171  assert(!TI.isSimple());
172  if (PartialOffsets.empty())
173  return fullScanForType(TI);
174 
175  auto Next = std::upper_bound(PartialOffsets.begin(), PartialOffsets.end(), TI,
176  [](TypeIndex Value, const TypeIndexOffset &IO) {
177  return Value < IO.Type;
178  });
179 
180  assert(Next != PartialOffsets.begin());
181  auto Prev = std::prev(Next);
182 
183  TypeIndex TIB = Prev->Type;
184  if (contains(TIB)) {
185  // They've asked us to fetch a type index, but the entry we found in the
186  // partial offsets array has already been visited. Since we visit an entire
187  // block every time, that means this record should have been previously
188  // discovered. Ultimately, this means this is a request for a non-existant
189  // type index.
190  return make_error<CodeViewError>("Invalid type index");
191  }
192 
193  TypeIndex TIE;
194  if (Next == PartialOffsets.end()) {
196  } else {
197  TIE = Next->Type;
198  }
199 
200  visitRange(TIB, Prev->Offset, TIE);
201  return Error::success();
202 }
203 
206  if (auto EC = ensureTypeExists(TI)) {
207  consumeError(std::move(EC));
208  return None;
209  }
210  return TI;
211 }
212 
214  // We can't be sure how long this type stream is, given that the initial count
215  // given to the constructor is just a hint. So just try to make sure the next
216  // record exists, and if anything goes wrong, we must be at the end.
217  if (auto EC = ensureTypeExists(Prev + 1)) {
218  consumeError(std::move(EC));
219  return None;
220  }
221 
222  return Prev + 1;
223 }
224 
225 Error LazyRandomTypeCollection::fullScanForType(TypeIndex TI) {
226  assert(!TI.isSimple());
227  assert(PartialOffsets.empty());
228 
229  TypeIndex CurrentTI = TypeIndex::fromArrayIndex(0);
230  auto Begin = Types.begin();
231 
232  if (Count > 0) {
233  // In the case of type streams which we don't know the number of records of,
234  // it's possible to search for a type index triggering a full scan, but then
235  // later additional records are added since we didn't know how many there
236  // would be until we did a full visitation, then you try to access the new
237  // type triggering another full scan. To avoid this, we assume that if the
238  // database has some records, this must be what's going on. We can also
239  // assume that this index must be larger than the largest type index we've
240  // visited, so we start from there and scan forward.
241  uint32_t Offset = Records[LargestTypeIndex.toArrayIndex()].Offset;
242  CurrentTI = LargestTypeIndex + 1;
243  Begin = Types.at(Offset);
244  ++Begin;
245  }
246 
247  auto End = Types.end();
248  while (Begin != End) {
249  ensureCapacityFor(CurrentTI);
250  LargestTypeIndex = std::max(LargestTypeIndex, CurrentTI);
251  auto Idx = CurrentTI.toArrayIndex();
252  Records[Idx].Type = *Begin;
253  Records[Idx].Offset = Begin.offset();
254  ++Count;
255  ++Begin;
256  ++CurrentTI;
257  }
258  if (CurrentTI <= TI) {
259  return make_error<CodeViewError>("Type Index does not exist!");
260  }
261  return Error::success();
262 }
263 
264 void LazyRandomTypeCollection::visitRange(TypeIndex Begin, uint32_t BeginOffset,
265  TypeIndex End) {
266  auto RI = Types.at(BeginOffset);
267  assert(RI != Types.end());
268 
269  ensureCapacityFor(End);
270  while (Begin != End) {
271  LargestTypeIndex = std::max(LargestTypeIndex, Begin);
272  auto Idx = Begin.toArrayIndex();
273  Records[Idx].Type = *RI;
274  Records[Idx].Offset = RI.offset();
275  ++Count;
276  ++Begin;
277  ++RI;
278  }
279 }
This class represents lattice values for constants.
Definition: AllocatorList.h:23
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
Iterator end() const
std::string computeTypeName(TypeCollection &Types, TypeIndex Index)
Definition: RecordName.cpp:248
Optional< TypeIndex > getNext(TypeIndex Prev) override
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:450
bool isNoneType() const
Definition: TypeIndex.h:115
void reset(ArrayRef< uint8_t > Data, uint32_t RecordCountHint)
static void error(Error &&EC)
A 32-bit type reference.
Definition: TypeIndex.h:95
uint32_t toArrayIndex() const
Definition: TypeIndex.h:117
static TypeIndex fromArrayIndex(uint32_t Index)
Definition: TypeIndex.h:122
static StringRef simpleTypeName(TypeIndex TI)
Definition: TypeIndex.cpp:70
Optional< CVType > tryGetType(TypeIndex Index)
void consumeError(Error Err)
Consume a Error without doing anything.
Definition: Error.h:981
StringRef getTypeName(TypeIndex Index) override
static ErrorSuccess success()
Create a success value.
Definition: Error.h:326
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:389
StringRef save(const char *S)
Definition: StringSaver.h:28
#define I(x, y, z)
Definition: MD5.cpp:58
uint32_t bytesRemaining() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
FixedStreamArrayIterator< T > end() const
Iterator at(uint32_t Offset) const
given an offset into the array&#39;s underlying stream, return an iterator to the record at that offset...
Iterator begin(bool *HadError=nullptr) const
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
Provides read only access to a subclass of BinaryStream.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
FixedStreamArrayIterator< T > begin() const
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 ...
Provides amortized O(1) random access to a CodeView type stream.
auto upper_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range))
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1276