LLVM  7.0.0svn
LazyRandomTypeCollection.cpp
Go to the documentation of this file.
1 //===- LazyRandomTypeCollection.cpp ---------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/None.h"
13 #include "llvm/ADT/StringExtras.h"
14 #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)
32  consumeError(std::move(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) {
74  BinaryStreamReader Reader(Data, support::little);
75  reset(Reader, RecordCountHint);
76 }
77 
79  uint32_t RecordCountHint) {
80  BinaryStreamReader Reader(Data, support::little);
81  reset(Reader, RecordCountHint);
82 }
83 
85  error(ensureTypeExists(Index));
86  assert(contains(Index));
87 
88  return Records[Index.toArrayIndex()].Offset;
89 }
90 
92  auto EC = ensureTypeExists(Index);
93  error(std::move(EC));
94  assert(contains(Index));
95 
96  return Records[Index.toArrayIndex()].Type;
97 }
98 
100  if (auto EC = ensureTypeExists(Index)) {
101  consumeError(std::move(EC));
102  return None;
103  }
104 
105  assert(contains(Index));
106  return Records[Index.toArrayIndex()].Type;
107 }
108 
110  if (Index.isNoneType() || Index.isSimple())
111  return TypeIndex::simpleTypeName(Index);
112 
113  // Try to make sure the type exists. Even if it doesn't though, it may be
114  // because we're dumping a symbol stream with no corresponding type stream
115  // present, in which case we still want to be able to print <unknown UDT>
116  // for the type names.
117  if (auto EC = ensureTypeExists(Index)) {
118  consumeError(std::move(EC));
119  return "<unknown UDT>";
120  }
121 
122  uint32_t I = Index.toArrayIndex();
123  ensureCapacityFor(Index);
124  if (Records[I].Name.data() == nullptr) {
125  StringRef Result = NameStorage.save(computeTypeName(*this, Index));
126  Records[I].Name = Result;
127  }
128  return Records[I].Name;
129 }
130 
132  if (Index.isSimple() || Index.isNoneType())
133  return false;
134 
135  if (Records.size() <= Index.toArrayIndex())
136  return false;
137  if (!Records[Index.toArrayIndex()].Type.valid())
138  return false;
139  return true;
140 }
141 
143 
144 uint32_t LazyRandomTypeCollection::capacity() { return Records.size(); }
145 
146 Error LazyRandomTypeCollection::ensureTypeExists(TypeIndex TI) {
147  if (contains(TI))
148  return Error::success();
149 
150  return visitRangeForType(TI);
151 }
152 
153 void LazyRandomTypeCollection::ensureCapacityFor(TypeIndex Index) {
154  uint32_t MinSize = Index.toArrayIndex() + 1;
155 
156  if (MinSize <= capacity())
157  return;
158 
159  uint32_t NewCapacity = MinSize * 3 / 2;
160 
161  assert(NewCapacity > capacity());
162  Records.resize(NewCapacity);
163 }
164 
165 Error LazyRandomTypeCollection::visitRangeForType(TypeIndex TI) {
166  if (PartialOffsets.empty())
167  return fullScanForType(TI);
168 
169  auto Next = std::upper_bound(PartialOffsets.begin(), PartialOffsets.end(), TI,
170  [](TypeIndex Value, const TypeIndexOffset &IO) {
171  return Value < IO.Type;
172  });
173 
174  assert(Next != PartialOffsets.begin());
175  auto Prev = std::prev(Next);
176 
177  TypeIndex TIB = Prev->Type;
178  if (contains(TIB)) {
179  // They've asked us to fetch a type index, but the entry we found in the
180  // partial offsets array has already been visited. Since we visit an entire
181  // block every time, that means this record should have been previously
182  // discovered. Ultimately, this means this is a request for a non-existant
183  // type index.
184  return make_error<CodeViewError>("Invalid type index");
185  }
186 
187  TypeIndex TIE;
188  if (Next == PartialOffsets.end()) {
190  } else {
191  TIE = Next->Type;
192  }
193 
194  visitRange(TIB, Prev->Offset, TIE);
195  return Error::success();
196 }
197 
200  if (auto EC = ensureTypeExists(TI)) {
201  consumeError(std::move(EC));
202  return None;
203  }
204  return TI;
205 }
206 
208  // We can't be sure how long this type stream is, given that the initial count
209  // given to the constructor is just a hint. So just try to make sure the next
210  // record exists, and if anything goes wrong, we must be at the end.
211  if (auto EC = ensureTypeExists(Prev + 1)) {
212  consumeError(std::move(EC));
213  return None;
214  }
215 
216  return Prev + 1;
217 }
218 
219 Error LazyRandomTypeCollection::fullScanForType(TypeIndex TI) {
220  assert(PartialOffsets.empty());
221 
222  TypeIndex CurrentTI = TypeIndex::fromArrayIndex(0);
223  auto Begin = Types.begin();
224 
225  if (Count > 0) {
226  // In the case of type streams which we don't know the number of records of,
227  // it's possible to search for a type index triggering a full scan, but then
228  // later additional records are added since we didn't know how many there
229  // would be until we did a full visitation, then you try to access the new
230  // type triggering another full scan. To avoid this, we assume that if the
231  // database has some records, this must be what's going on. We can also
232  // assume that this index must be larger than the largest type index we've
233  // visited, so we start from there and scan forward.
234  uint32_t Offset = Records[LargestTypeIndex.toArrayIndex()].Offset;
235  CurrentTI = LargestTypeIndex + 1;
236  Begin = Types.at(Offset);
237  ++Begin;
238  }
239 
240  auto End = Types.end();
241  while (Begin != End) {
242  ensureCapacityFor(CurrentTI);
243  LargestTypeIndex = std::max(LargestTypeIndex, CurrentTI);
244  auto Idx = CurrentTI.toArrayIndex();
245  Records[Idx].Type = *Begin;
246  Records[Idx].Offset = Begin.offset();
247  ++Count;
248  ++Begin;
249  ++CurrentTI;
250  }
251  if (CurrentTI <= TI) {
252  return make_error<CodeViewError>("Type Index does not exist!");
253  }
254  return Error::success();
255 }
256 
257 void LazyRandomTypeCollection::visitRange(TypeIndex Begin, uint32_t BeginOffset,
258  TypeIndex End) {
259  auto RI = Types.at(BeginOffset);
260  assert(RI != Types.end());
261 
262  ensureCapacityFor(End);
263  while (Begin != End) {
264  LargestTypeIndex = std::max(LargestTypeIndex, Begin);
265  auto Idx = Begin.toArrayIndex();
266  Records[Idx].Type = *RI;
267  Records[Idx].Offset = RI.offset();
268  ++Count;
269  ++Begin;
270  ++RI;
271  }
272 }
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Iterator end() const
std::string computeTypeName(TypeCollection &Types, TypeIndex Index)
Definition: RecordName.cpp:249
Optional< TypeIndex > getNext(TypeIndex Prev) override
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
bool isNoneType() const
Definition: TypeIndex.h:116
void reset(ArrayRef< uint8_t > Data, uint32_t RecordCountHint)
static void error(Error &&EC)
A 32-bit type reference.
Definition: TypeIndex.h:96
uint32_t toArrayIndex() const
Definition: TypeIndex.h:118
static TypeIndex fromArrayIndex(uint32_t Index)
Definition: TypeIndex.h:123
static StringRef simpleTypeName(TypeIndex TI)
Definition: TypeIndex.cpp:71
Optional< CVType > tryGetType(TypeIndex Index)
static const unsigned End
void consumeError(Error Err)
Consume a Error without doing anything.
Definition: Error.h:962
StringRef getTypeName(TypeIndex Index) override
static ErrorSuccess success()
Create a success value.
Definition: Error.h:313
StringRef save(const char *S)
Definition: StringSaver.h:26
#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
LLVM Value Representation.
Definition: Value.h:73
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
Provides read only access to a subclass of BinaryStream.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
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.