File: | lib/ProfileData/InstrProfReader.cpp |
Warning: | line 717, column 7 Potential leak of memory pointed to by field '_M_head_impl' |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- InstrProfReader.cpp - Instrumented profiling reader ----------------===// | |||
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 | // | |||
10 | // This file contains support for reading profiling data for clang's | |||
11 | // instrumentation based PGO and coverage. | |||
12 | // | |||
13 | //===----------------------------------------------------------------------===// | |||
14 | ||||
15 | #include "llvm/ProfileData/InstrProfReader.h" | |||
16 | #include "llvm/ADT/ArrayRef.h" | |||
17 | #include "llvm/ADT/STLExtras.h" | |||
18 | #include "llvm/ADT/StringRef.h" | |||
19 | #include "llvm/IR/ProfileSummary.h" | |||
20 | #include "llvm/ProfileData/InstrProf.h" | |||
21 | #include "llvm/ProfileData/ProfileCommon.h" | |||
22 | #include "llvm/Support/Endian.h" | |||
23 | #include "llvm/Support/Error.h" | |||
24 | #include "llvm/Support/ErrorOr.h" | |||
25 | #include "llvm/Support/MemoryBuffer.h" | |||
26 | #include "llvm/Support/SwapByteOrder.h" | |||
27 | #include <algorithm> | |||
28 | #include <cctype> | |||
29 | #include <cstddef> | |||
30 | #include <cstdint> | |||
31 | #include <limits> | |||
32 | #include <memory> | |||
33 | #include <system_error> | |||
34 | #include <utility> | |||
35 | #include <vector> | |||
36 | ||||
37 | using namespace llvm; | |||
38 | ||||
39 | static Expected<std::unique_ptr<MemoryBuffer>> | |||
40 | setupMemoryBuffer(const Twine &Path) { | |||
41 | ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOrErr = | |||
42 | MemoryBuffer::getFileOrSTDIN(Path); | |||
43 | if (std::error_code EC = BufferOrErr.getError()) | |||
44 | return errorCodeToError(EC); | |||
45 | return std::move(BufferOrErr.get()); | |||
46 | } | |||
47 | ||||
48 | static Error initializeReader(InstrProfReader &Reader) { | |||
49 | return Reader.readHeader(); | |||
50 | } | |||
51 | ||||
52 | Expected<std::unique_ptr<InstrProfReader>> | |||
53 | InstrProfReader::create(const Twine &Path) { | |||
54 | // Set up the buffer to read. | |||
55 | auto BufferOrError = setupMemoryBuffer(Path); | |||
56 | if (Error E = BufferOrError.takeError()) | |||
57 | return std::move(E); | |||
58 | return InstrProfReader::create(std::move(BufferOrError.get())); | |||
59 | } | |||
60 | ||||
61 | Expected<std::unique_ptr<InstrProfReader>> | |||
62 | InstrProfReader::create(std::unique_ptr<MemoryBuffer> Buffer) { | |||
63 | // Sanity check the buffer. | |||
64 | if (uint64_t(Buffer->getBufferSize()) > std::numeric_limits<unsigned>::max()) | |||
65 | return make_error<InstrProfError>(instrprof_error::too_large); | |||
66 | ||||
67 | if (Buffer->getBufferSize() == 0) | |||
68 | return make_error<InstrProfError>(instrprof_error::empty_raw_profile); | |||
69 | ||||
70 | std::unique_ptr<InstrProfReader> Result; | |||
71 | // Create the reader. | |||
72 | if (IndexedInstrProfReader::hasFormat(*Buffer)) | |||
73 | Result.reset(new IndexedInstrProfReader(std::move(Buffer))); | |||
74 | else if (RawInstrProfReader64::hasFormat(*Buffer)) | |||
75 | Result.reset(new RawInstrProfReader64(std::move(Buffer))); | |||
76 | else if (RawInstrProfReader32::hasFormat(*Buffer)) | |||
77 | Result.reset(new RawInstrProfReader32(std::move(Buffer))); | |||
78 | else if (TextInstrProfReader::hasFormat(*Buffer)) | |||
79 | Result.reset(new TextInstrProfReader(std::move(Buffer))); | |||
80 | else | |||
81 | return make_error<InstrProfError>(instrprof_error::unrecognized_format); | |||
82 | ||||
83 | // Initialize the reader and return the result. | |||
84 | if (Error E = initializeReader(*Result)) | |||
85 | return std::move(E); | |||
86 | ||||
87 | return std::move(Result); | |||
88 | } | |||
89 | ||||
90 | Expected<std::unique_ptr<IndexedInstrProfReader>> | |||
91 | IndexedInstrProfReader::create(const Twine &Path) { | |||
92 | // Set up the buffer to read. | |||
93 | auto BufferOrError = setupMemoryBuffer(Path); | |||
94 | if (Error E = BufferOrError.takeError()) | |||
95 | return std::move(E); | |||
96 | return IndexedInstrProfReader::create(std::move(BufferOrError.get())); | |||
97 | } | |||
98 | ||||
99 | Expected<std::unique_ptr<IndexedInstrProfReader>> | |||
100 | IndexedInstrProfReader::create(std::unique_ptr<MemoryBuffer> Buffer) { | |||
101 | // Sanity check the buffer. | |||
102 | if (uint64_t(Buffer->getBufferSize()) > std::numeric_limits<unsigned>::max()) | |||
103 | return make_error<InstrProfError>(instrprof_error::too_large); | |||
104 | ||||
105 | // Create the reader. | |||
106 | if (!IndexedInstrProfReader::hasFormat(*Buffer)) | |||
107 | return make_error<InstrProfError>(instrprof_error::bad_magic); | |||
108 | auto Result = llvm::make_unique<IndexedInstrProfReader>(std::move(Buffer)); | |||
109 | ||||
110 | // Initialize the reader and return the result. | |||
111 | if (Error E = initializeReader(*Result)) | |||
112 | return std::move(E); | |||
113 | ||||
114 | return std::move(Result); | |||
115 | } | |||
116 | ||||
117 | void InstrProfIterator::Increment() { | |||
118 | if (auto E = Reader->readNextRecord(Record)) { | |||
119 | // Handle errors in the reader. | |||
120 | InstrProfError::take(std::move(E)); | |||
121 | *this = InstrProfIterator(); | |||
122 | } | |||
123 | } | |||
124 | ||||
125 | bool TextInstrProfReader::hasFormat(const MemoryBuffer &Buffer) { | |||
126 | // Verify that this really looks like plain ASCII text by checking a | |||
127 | // 'reasonable' number of characters (up to profile magic size). | |||
128 | size_t count = std::min(Buffer.getBufferSize(), sizeof(uint64_t)); | |||
129 | StringRef buffer = Buffer.getBufferStart(); | |||
130 | return count == 0 || | |||
131 | std::all_of(buffer.begin(), buffer.begin() + count, | |||
132 | [](char c) { return ::isprint(c) || ::isspace(c); }); | |||
133 | } | |||
134 | ||||
135 | // Read the profile variant flag from the header: ":FE" means this is a FE | |||
136 | // generated profile. ":IR" means this is an IR level profile. Other strings | |||
137 | // with a leading ':' will be reported an error format. | |||
138 | Error TextInstrProfReader::readHeader() { | |||
139 | Symtab.reset(new InstrProfSymtab()); | |||
140 | bool IsIRInstr = false; | |||
141 | if (!Line->startswith(":")) { | |||
142 | IsIRLevelProfile = false; | |||
143 | return success(); | |||
144 | } | |||
145 | StringRef Str = (Line)->substr(1); | |||
146 | if (Str.equals_lower("ir")) | |||
147 | IsIRInstr = true; | |||
148 | else if (Str.equals_lower("fe")) | |||
149 | IsIRInstr = false; | |||
150 | else | |||
151 | return error(instrprof_error::bad_header); | |||
152 | ||||
153 | ++Line; | |||
154 | IsIRLevelProfile = IsIRInstr; | |||
155 | return success(); | |||
156 | } | |||
157 | ||||
158 | Error | |||
159 | TextInstrProfReader::readValueProfileData(InstrProfRecord &Record) { | |||
160 | ||||
161 | #define CHECK_LINE_END(Line) \ | |||
162 | if (Line.is_at_end()) \ | |||
163 | return error(instrprof_error::truncated); | |||
164 | #define READ_NUM(Str, Dst) \ | |||
165 | if ((Str).getAsInteger(10, (Dst))) \ | |||
166 | return error(instrprof_error::malformed); | |||
167 | #define VP_READ_ADVANCE(Val) \ | |||
168 | CHECK_LINE_END(Line); \ | |||
169 | uint32_t Val; \ | |||
170 | READ_NUM((*Line), (Val)); \ | |||
171 | Line++; | |||
172 | ||||
173 | if (Line.is_at_end()) | |||
174 | return success(); | |||
175 | ||||
176 | uint32_t NumValueKinds; | |||
177 | if (Line->getAsInteger(10, NumValueKinds)) { | |||
178 | // No value profile data | |||
179 | return success(); | |||
180 | } | |||
181 | if (NumValueKinds == 0 || NumValueKinds > IPVK_Last + 1) | |||
182 | return error(instrprof_error::malformed); | |||
183 | Line++; | |||
184 | ||||
185 | for (uint32_t VK = 0; VK < NumValueKinds; VK++) { | |||
186 | VP_READ_ADVANCE(ValueKind); | |||
187 | if (ValueKind > IPVK_Last) | |||
188 | return error(instrprof_error::malformed); | |||
189 | VP_READ_ADVANCE(NumValueSites); | |||
190 | if (!NumValueSites) | |||
191 | continue; | |||
192 | ||||
193 | Record.reserveSites(VK, NumValueSites); | |||
194 | for (uint32_t S = 0; S < NumValueSites; S++) { | |||
195 | VP_READ_ADVANCE(NumValueData); | |||
196 | ||||
197 | std::vector<InstrProfValueData> CurrentValues; | |||
198 | for (uint32_t V = 0; V < NumValueData; V++) { | |||
199 | CHECK_LINE_END(Line); | |||
200 | std::pair<StringRef, StringRef> VD = Line->rsplit(':'); | |||
201 | uint64_t TakenCount, Value; | |||
202 | if (ValueKind == IPVK_IndirectCallTarget) { | |||
203 | if (InstrProfSymtab::isExternalSymbol(VD.first)) { | |||
204 | Value = 0; | |||
205 | } else { | |||
206 | if (Error E = Symtab->addFuncName(VD.first)) | |||
207 | return E; | |||
208 | Value = IndexedInstrProf::ComputeHash(VD.first); | |||
209 | } | |||
210 | } else { | |||
211 | READ_NUM(VD.first, Value); | |||
212 | } | |||
213 | READ_NUM(VD.second, TakenCount); | |||
214 | CurrentValues.push_back({Value, TakenCount}); | |||
215 | Line++; | |||
216 | } | |||
217 | Record.addValueData(ValueKind, S, CurrentValues.data(), NumValueData, | |||
218 | nullptr); | |||
219 | } | |||
220 | } | |||
221 | return success(); | |||
222 | ||||
223 | #undef CHECK_LINE_END | |||
224 | #undef READ_NUM | |||
225 | #undef VP_READ_ADVANCE | |||
226 | } | |||
227 | ||||
228 | Error TextInstrProfReader::readNextRecord(NamedInstrProfRecord &Record) { | |||
229 | // Skip empty lines and comments. | |||
230 | while (!Line.is_at_end() && (Line->empty() || Line->startswith("#"))) | |||
231 | ++Line; | |||
232 | // If we hit EOF while looking for a name, we're done. | |||
233 | if (Line.is_at_end()) { | |||
234 | return error(instrprof_error::eof); | |||
235 | } | |||
236 | ||||
237 | // Read the function name. | |||
238 | Record.Name = *Line++; | |||
239 | if (Error E = Symtab->addFuncName(Record.Name)) | |||
240 | return error(std::move(E)); | |||
241 | ||||
242 | // Read the function hash. | |||
243 | if (Line.is_at_end()) | |||
244 | return error(instrprof_error::truncated); | |||
245 | if ((Line++)->getAsInteger(0, Record.Hash)) | |||
246 | return error(instrprof_error::malformed); | |||
247 | ||||
248 | // Read the number of counters. | |||
249 | uint64_t NumCounters; | |||
250 | if (Line.is_at_end()) | |||
251 | return error(instrprof_error::truncated); | |||
252 | if ((Line++)->getAsInteger(10, NumCounters)) | |||
253 | return error(instrprof_error::malformed); | |||
254 | if (NumCounters == 0) | |||
255 | return error(instrprof_error::malformed); | |||
256 | ||||
257 | // Read each counter and fill our internal storage with the values. | |||
258 | Record.Clear(); | |||
259 | Record.Counts.reserve(NumCounters); | |||
260 | for (uint64_t I = 0; I < NumCounters; ++I) { | |||
261 | if (Line.is_at_end()) | |||
262 | return error(instrprof_error::truncated); | |||
263 | uint64_t Count; | |||
264 | if ((Line++)->getAsInteger(10, Count)) | |||
265 | return error(instrprof_error::malformed); | |||
266 | Record.Counts.push_back(Count); | |||
267 | } | |||
268 | ||||
269 | // Check if value profile data exists and read it if so. | |||
270 | if (Error E = readValueProfileData(Record)) | |||
271 | return error(std::move(E)); | |||
272 | ||||
273 | return success(); | |||
274 | } | |||
275 | ||||
276 | template <class IntPtrT> | |||
277 | bool RawInstrProfReader<IntPtrT>::hasFormat(const MemoryBuffer &DataBuffer) { | |||
278 | if (DataBuffer.getBufferSize() < sizeof(uint64_t)) | |||
279 | return false; | |||
280 | uint64_t Magic = | |||
281 | *reinterpret_cast<const uint64_t *>(DataBuffer.getBufferStart()); | |||
282 | return RawInstrProf::getMagic<IntPtrT>() == Magic || | |||
283 | sys::getSwappedBytes(RawInstrProf::getMagic<IntPtrT>()) == Magic; | |||
284 | } | |||
285 | ||||
286 | template <class IntPtrT> | |||
287 | Error RawInstrProfReader<IntPtrT>::readHeader() { | |||
288 | if (!hasFormat(*DataBuffer)) | |||
289 | return error(instrprof_error::bad_magic); | |||
290 | if (DataBuffer->getBufferSize() < sizeof(RawInstrProf::Header)) | |||
291 | return error(instrprof_error::bad_header); | |||
292 | auto *Header = reinterpret_cast<const RawInstrProf::Header *>( | |||
293 | DataBuffer->getBufferStart()); | |||
294 | ShouldSwapBytes = Header->Magic != RawInstrProf::getMagic<IntPtrT>(); | |||
295 | return readHeader(*Header); | |||
296 | } | |||
297 | ||||
298 | template <class IntPtrT> | |||
299 | Error RawInstrProfReader<IntPtrT>::readNextHeader(const char *CurrentPos) { | |||
300 | const char *End = DataBuffer->getBufferEnd(); | |||
301 | // Skip zero padding between profiles. | |||
302 | while (CurrentPos != End && *CurrentPos == 0) | |||
303 | ++CurrentPos; | |||
304 | // If there's nothing left, we're done. | |||
305 | if (CurrentPos == End) | |||
306 | return make_error<InstrProfError>(instrprof_error::eof); | |||
307 | // If there isn't enough space for another header, this is probably just | |||
308 | // garbage at the end of the file. | |||
309 | if (CurrentPos + sizeof(RawInstrProf::Header) > End) | |||
310 | return make_error<InstrProfError>(instrprof_error::malformed); | |||
311 | // The writer ensures each profile is padded to start at an aligned address. | |||
312 | if (reinterpret_cast<size_t>(CurrentPos) % alignof(uint64_t)) | |||
313 | return make_error<InstrProfError>(instrprof_error::malformed); | |||
314 | // The magic should have the same byte order as in the previous header. | |||
315 | uint64_t Magic = *reinterpret_cast<const uint64_t *>(CurrentPos); | |||
316 | if (Magic != swap(RawInstrProf::getMagic<IntPtrT>())) | |||
317 | return make_error<InstrProfError>(instrprof_error::bad_magic); | |||
318 | ||||
319 | // There's another profile to read, so we need to process the header. | |||
320 | auto *Header = reinterpret_cast<const RawInstrProf::Header *>(CurrentPos); | |||
321 | return readHeader(*Header); | |||
322 | } | |||
323 | ||||
324 | template <class IntPtrT> | |||
325 | Error RawInstrProfReader<IntPtrT>::createSymtab(InstrProfSymtab &Symtab) { | |||
326 | if (Error E = Symtab.create(StringRef(NamesStart, NamesSize))) | |||
327 | return error(std::move(E)); | |||
328 | for (const RawInstrProf::ProfileData<IntPtrT> *I = Data; I != DataEnd; ++I) { | |||
329 | const IntPtrT FPtr = swap(I->FunctionPointer); | |||
330 | if (!FPtr) | |||
331 | continue; | |||
332 | Symtab.mapAddress(FPtr, I->NameRef); | |||
333 | } | |||
334 | return success(); | |||
335 | } | |||
336 | ||||
337 | template <class IntPtrT> | |||
338 | Error RawInstrProfReader<IntPtrT>::readHeader( | |||
339 | const RawInstrProf::Header &Header) { | |||
340 | Version = swap(Header.Version); | |||
341 | if (GET_VERSION(Version)((Version) & ~0xff00000000000000ULL) != RawInstrProf::Version) | |||
342 | return error(instrprof_error::unsupported_version); | |||
343 | ||||
344 | CountersDelta = swap(Header.CountersDelta); | |||
345 | NamesDelta = swap(Header.NamesDelta); | |||
346 | auto DataSize = swap(Header.DataSize); | |||
347 | auto CountersSize = swap(Header.CountersSize); | |||
348 | NamesSize = swap(Header.NamesSize); | |||
349 | ValueKindLast = swap(Header.ValueKindLast); | |||
350 | ||||
351 | auto DataSizeInBytes = DataSize * sizeof(RawInstrProf::ProfileData<IntPtrT>); | |||
352 | auto PaddingSize = getNumPaddingBytes(NamesSize); | |||
353 | ||||
354 | ptrdiff_t DataOffset = sizeof(RawInstrProf::Header); | |||
355 | ptrdiff_t CountersOffset = DataOffset + DataSizeInBytes; | |||
356 | ptrdiff_t NamesOffset = CountersOffset + sizeof(uint64_t) * CountersSize; | |||
357 | ptrdiff_t ValueDataOffset = NamesOffset + NamesSize + PaddingSize; | |||
358 | ||||
359 | auto *Start = reinterpret_cast<const char *>(&Header); | |||
360 | if (Start + ValueDataOffset > DataBuffer->getBufferEnd()) | |||
361 | return error(instrprof_error::bad_header); | |||
362 | ||||
363 | Data = reinterpret_cast<const RawInstrProf::ProfileData<IntPtrT> *>( | |||
364 | Start + DataOffset); | |||
365 | DataEnd = Data + DataSize; | |||
366 | CountersStart = reinterpret_cast<const uint64_t *>(Start + CountersOffset); | |||
367 | NamesStart = Start + NamesOffset; | |||
368 | ValueDataStart = reinterpret_cast<const uint8_t *>(Start + ValueDataOffset); | |||
369 | ||||
370 | std::unique_ptr<InstrProfSymtab> NewSymtab = make_unique<InstrProfSymtab>(); | |||
371 | if (Error E = createSymtab(*NewSymtab.get())) | |||
372 | return E; | |||
373 | ||||
374 | Symtab = std::move(NewSymtab); | |||
375 | return success(); | |||
376 | } | |||
377 | ||||
378 | template <class IntPtrT> | |||
379 | Error RawInstrProfReader<IntPtrT>::readName(NamedInstrProfRecord &Record) { | |||
380 | Record.Name = getName(Data->NameRef); | |||
381 | return success(); | |||
382 | } | |||
383 | ||||
384 | template <class IntPtrT> | |||
385 | Error RawInstrProfReader<IntPtrT>::readFuncHash(NamedInstrProfRecord &Record) { | |||
386 | Record.Hash = swap(Data->FuncHash); | |||
387 | return success(); | |||
388 | } | |||
389 | ||||
390 | template <class IntPtrT> | |||
391 | Error RawInstrProfReader<IntPtrT>::readRawCounts( | |||
392 | InstrProfRecord &Record) { | |||
393 | uint32_t NumCounters = swap(Data->NumCounters); | |||
394 | IntPtrT CounterPtr = Data->CounterPtr; | |||
395 | if (NumCounters == 0) | |||
396 | return error(instrprof_error::malformed); | |||
397 | ||||
398 | auto RawCounts = makeArrayRef(getCounter(CounterPtr), NumCounters); | |||
399 | auto *NamesStartAsCounter = reinterpret_cast<const uint64_t *>(NamesStart); | |||
400 | ||||
401 | // Check bounds. | |||
402 | if (RawCounts.data() < CountersStart || | |||
403 | RawCounts.data() + RawCounts.size() > NamesStartAsCounter) | |||
404 | return error(instrprof_error::malformed); | |||
405 | ||||
406 | if (ShouldSwapBytes) { | |||
407 | Record.Counts.clear(); | |||
408 | Record.Counts.reserve(RawCounts.size()); | |||
409 | for (uint64_t Count : RawCounts) | |||
410 | Record.Counts.push_back(swap(Count)); | |||
411 | } else | |||
412 | Record.Counts = RawCounts; | |||
413 | ||||
414 | return success(); | |||
415 | } | |||
416 | ||||
417 | template <class IntPtrT> | |||
418 | Error RawInstrProfReader<IntPtrT>::readValueProfilingData( | |||
419 | InstrProfRecord &Record) { | |||
420 | Record.clearValueData(); | |||
421 | CurValueDataSize = 0; | |||
422 | // Need to match the logic in value profile dumper code in compiler-rt: | |||
423 | uint32_t NumValueKinds = 0; | |||
424 | for (uint32_t I = 0; I < IPVK_Last + 1; I++) | |||
425 | NumValueKinds += (Data->NumValueSites[I] != 0); | |||
426 | ||||
427 | if (!NumValueKinds) | |||
428 | return success(); | |||
429 | ||||
430 | Expected<std::unique_ptr<ValueProfData>> VDataPtrOrErr = | |||
431 | ValueProfData::getValueProfData( | |||
432 | ValueDataStart, (const unsigned char *)DataBuffer->getBufferEnd(), | |||
433 | getDataEndianness()); | |||
434 | ||||
435 | if (Error E = VDataPtrOrErr.takeError()) | |||
436 | return E; | |||
437 | ||||
438 | // Note that besides deserialization, this also performs the conversion for | |||
439 | // indirect call targets. The function pointers from the raw profile are | |||
440 | // remapped into function name hashes. | |||
441 | VDataPtrOrErr.get()->deserializeTo(Record, Symtab.get()); | |||
442 | CurValueDataSize = VDataPtrOrErr.get()->getSize(); | |||
443 | return success(); | |||
444 | } | |||
445 | ||||
446 | template <class IntPtrT> | |||
447 | Error RawInstrProfReader<IntPtrT>::readNextRecord(NamedInstrProfRecord &Record) { | |||
448 | if (atEnd()) | |||
449 | // At this point, ValueDataStart field points to the next header. | |||
450 | if (Error E = readNextHeader(getNextHeaderPos())) | |||
451 | return E; | |||
452 | ||||
453 | // Read name ad set it in Record. | |||
454 | if (Error E = readName(Record)) | |||
455 | return E; | |||
456 | ||||
457 | // Read FuncHash and set it in Record. | |||
458 | if (Error E = readFuncHash(Record)) | |||
459 | return E; | |||
460 | ||||
461 | // Read raw counts and set Record. | |||
462 | if (Error E = readRawCounts(Record)) | |||
463 | return E; | |||
464 | ||||
465 | // Read value data and set Record. | |||
466 | if (Error E = readValueProfilingData(Record)) | |||
467 | return E; | |||
468 | ||||
469 | // Iterate. | |||
470 | advanceData(); | |||
471 | return success(); | |||
472 | } | |||
473 | ||||
474 | namespace llvm { | |||
475 | ||||
476 | template class RawInstrProfReader<uint32_t>; | |||
477 | template class RawInstrProfReader<uint64_t>; | |||
478 | ||||
479 | } // end namespace llvm | |||
480 | ||||
481 | InstrProfLookupTrait::hash_value_type | |||
482 | InstrProfLookupTrait::ComputeHash(StringRef K) { | |||
483 | return IndexedInstrProf::ComputeHash(HashType, K); | |||
484 | } | |||
485 | ||||
486 | using data_type = InstrProfLookupTrait::data_type; | |||
487 | using offset_type = InstrProfLookupTrait::offset_type; | |||
488 | ||||
489 | bool InstrProfLookupTrait::readValueProfilingData( | |||
490 | const unsigned char *&D, const unsigned char *const End) { | |||
491 | Expected<std::unique_ptr<ValueProfData>> VDataPtrOrErr = | |||
492 | ValueProfData::getValueProfData(D, End, ValueProfDataEndianness); | |||
493 | ||||
494 | if (VDataPtrOrErr.takeError()) | |||
495 | return false; | |||
496 | ||||
497 | VDataPtrOrErr.get()->deserializeTo(DataBuffer.back(), nullptr); | |||
498 | D += VDataPtrOrErr.get()->TotalSize; | |||
499 | ||||
500 | return true; | |||
501 | } | |||
502 | ||||
503 | data_type InstrProfLookupTrait::ReadData(StringRef K, const unsigned char *D, | |||
504 | offset_type N) { | |||
505 | using namespace support; | |||
506 | ||||
507 | // Check if the data is corrupt. If so, don't try to read it. | |||
508 | if (N % sizeof(uint64_t)) | |||
509 | return data_type(); | |||
510 | ||||
511 | DataBuffer.clear(); | |||
512 | std::vector<uint64_t> CounterBuffer; | |||
513 | ||||
514 | const unsigned char *End = D + N; | |||
515 | while (D < End) { | |||
516 | // Read hash. | |||
517 | if (D + sizeof(uint64_t) >= End) | |||
518 | return data_type(); | |||
519 | uint64_t Hash = endian::readNext<uint64_t, little, unaligned>(D); | |||
520 | ||||
521 | // Initialize number of counters for GET_VERSION(FormatVersion) == 1. | |||
522 | uint64_t CountsSize = N / sizeof(uint64_t) - 1; | |||
523 | // If format version is different then read the number of counters. | |||
524 | if (GET_VERSION(FormatVersion)((FormatVersion) & ~0xff00000000000000ULL) != IndexedInstrProf::ProfVersion::Version1) { | |||
525 | if (D + sizeof(uint64_t) > End) | |||
526 | return data_type(); | |||
527 | CountsSize = endian::readNext<uint64_t, little, unaligned>(D); | |||
528 | } | |||
529 | // Read counter values. | |||
530 | if (D + CountsSize * sizeof(uint64_t) > End) | |||
531 | return data_type(); | |||
532 | ||||
533 | CounterBuffer.clear(); | |||
534 | CounterBuffer.reserve(CountsSize); | |||
535 | for (uint64_t J = 0; J < CountsSize; ++J) | |||
536 | CounterBuffer.push_back(endian::readNext<uint64_t, little, unaligned>(D)); | |||
537 | ||||
538 | DataBuffer.emplace_back(K, Hash, std::move(CounterBuffer)); | |||
539 | ||||
540 | // Read value profiling data. | |||
541 | if (GET_VERSION(FormatVersion)((FormatVersion) & ~0xff00000000000000ULL) > IndexedInstrProf::ProfVersion::Version2 && | |||
542 | !readValueProfilingData(D, End)) { | |||
543 | DataBuffer.clear(); | |||
544 | return data_type(); | |||
545 | } | |||
546 | } | |||
547 | return DataBuffer; | |||
548 | } | |||
549 | ||||
550 | template <typename HashTableImpl> | |||
551 | Error InstrProfReaderIndex<HashTableImpl>::getRecords( | |||
552 | StringRef FuncName, ArrayRef<NamedInstrProfRecord> &Data) { | |||
553 | auto Iter = HashTable->find(FuncName); | |||
554 | if (Iter == HashTable->end()) | |||
555 | return make_error<InstrProfError>(instrprof_error::unknown_function); | |||
556 | ||||
557 | Data = (*Iter); | |||
558 | if (Data.empty()) | |||
559 | return make_error<InstrProfError>(instrprof_error::malformed); | |||
560 | ||||
561 | return Error::success(); | |||
562 | } | |||
563 | ||||
564 | template <typename HashTableImpl> | |||
565 | Error InstrProfReaderIndex<HashTableImpl>::getRecords( | |||
566 | ArrayRef<NamedInstrProfRecord> &Data) { | |||
567 | if (atEnd()) | |||
568 | return make_error<InstrProfError>(instrprof_error::eof); | |||
569 | ||||
570 | Data = *RecordIterator; | |||
571 | ||||
572 | if (Data.empty()) | |||
573 | return make_error<InstrProfError>(instrprof_error::malformed); | |||
574 | ||||
575 | return Error::success(); | |||
576 | } | |||
577 | ||||
578 | template <typename HashTableImpl> | |||
579 | InstrProfReaderIndex<HashTableImpl>::InstrProfReaderIndex( | |||
580 | const unsigned char *Buckets, const unsigned char *const Payload, | |||
581 | const unsigned char *const Base, IndexedInstrProf::HashT HashType, | |||
582 | uint64_t Version) { | |||
583 | FormatVersion = Version; | |||
584 | HashTable.reset(HashTableImpl::Create( | |||
585 | Buckets, Payload, Base, | |||
586 | typename HashTableImpl::InfoType(HashType, Version))); | |||
587 | RecordIterator = HashTable->data_begin(); | |||
588 | } | |||
589 | ||||
590 | bool IndexedInstrProfReader::hasFormat(const MemoryBuffer &DataBuffer) { | |||
591 | using namespace support; | |||
592 | ||||
593 | if (DataBuffer.getBufferSize() < 8) | |||
594 | return false; | |||
595 | uint64_t Magic = | |||
596 | endian::read<uint64_t, little, aligned>(DataBuffer.getBufferStart()); | |||
597 | // Verify that it's magical. | |||
598 | return Magic == IndexedInstrProf::Magic; | |||
599 | } | |||
600 | ||||
601 | const unsigned char * | |||
602 | IndexedInstrProfReader::readSummary(IndexedInstrProf::ProfVersion Version, | |||
603 | const unsigned char *Cur) { | |||
604 | using namespace IndexedInstrProf; | |||
605 | using namespace support; | |||
606 | ||||
607 | if (Version >= IndexedInstrProf::Version4) { | |||
608 | const IndexedInstrProf::Summary *SummaryInLE = | |||
609 | reinterpret_cast<const IndexedInstrProf::Summary *>(Cur); | |||
610 | uint64_t NFields = | |||
611 | endian::byte_swap<uint64_t, little>(SummaryInLE->NumSummaryFields); | |||
612 | uint64_t NEntries = | |||
613 | endian::byte_swap<uint64_t, little>(SummaryInLE->NumCutoffEntries); | |||
614 | uint32_t SummarySize = | |||
615 | IndexedInstrProf::Summary::getSize(NFields, NEntries); | |||
616 | std::unique_ptr<IndexedInstrProf::Summary> SummaryData = | |||
617 | IndexedInstrProf::allocSummary(SummarySize); | |||
618 | ||||
619 | const uint64_t *Src = reinterpret_cast<const uint64_t *>(SummaryInLE); | |||
620 | uint64_t *Dst = reinterpret_cast<uint64_t *>(SummaryData.get()); | |||
621 | for (unsigned I = 0; I < SummarySize / sizeof(uint64_t); I++) | |||
622 | Dst[I] = endian::byte_swap<uint64_t, little>(Src[I]); | |||
623 | ||||
624 | SummaryEntryVector DetailedSummary; | |||
625 | for (unsigned I = 0; I < SummaryData->NumCutoffEntries; I++) { | |||
626 | const IndexedInstrProf::Summary::Entry &Ent = SummaryData->getEntry(I); | |||
627 | DetailedSummary.emplace_back((uint32_t)Ent.Cutoff, Ent.MinBlockCount, | |||
628 | Ent.NumBlocks); | |||
629 | } | |||
630 | // initialize InstrProfSummary using the SummaryData from disk. | |||
631 | this->Summary = llvm::make_unique<ProfileSummary>( | |||
632 | ProfileSummary::PSK_Instr, DetailedSummary, | |||
633 | SummaryData->get(Summary::TotalBlockCount), | |||
634 | SummaryData->get(Summary::MaxBlockCount), | |||
635 | SummaryData->get(Summary::MaxInternalBlockCount), | |||
636 | SummaryData->get(Summary::MaxFunctionCount), | |||
637 | SummaryData->get(Summary::TotalNumBlocks), | |||
638 | SummaryData->get(Summary::TotalNumFunctions)); | |||
639 | return Cur + SummarySize; | |||
640 | } else { | |||
641 | // For older version of profile data, we need to compute on the fly: | |||
642 | using namespace IndexedInstrProf; | |||
643 | ||||
644 | InstrProfSummaryBuilder Builder(ProfileSummaryBuilder::DefaultCutoffs); | |||
645 | // FIXME: This only computes an empty summary. Need to call addRecord for | |||
646 | // all NamedInstrProfRecords to get the correct summary. | |||
647 | this->Summary = Builder.getSummary(); | |||
648 | return Cur; | |||
649 | } | |||
650 | } | |||
651 | ||||
652 | Error IndexedInstrProfReader::readHeader() { | |||
653 | using namespace support; | |||
654 | ||||
655 | const unsigned char *Start = | |||
656 | (const unsigned char *)DataBuffer->getBufferStart(); | |||
657 | const unsigned char *Cur = Start; | |||
658 | if ((const unsigned char *)DataBuffer->getBufferEnd() - Cur < 24) | |||
659 | return error(instrprof_error::truncated); | |||
660 | ||||
661 | auto *Header = reinterpret_cast<const IndexedInstrProf::Header *>(Cur); | |||
662 | Cur += sizeof(IndexedInstrProf::Header); | |||
663 | ||||
664 | // Check the magic number. | |||
665 | uint64_t Magic = endian::byte_swap<uint64_t, little>(Header->Magic); | |||
666 | if (Magic != IndexedInstrProf::Magic) | |||
667 | return error(instrprof_error::bad_magic); | |||
668 | ||||
669 | // Read the version. | |||
670 | uint64_t FormatVersion = endian::byte_swap<uint64_t, little>(Header->Version); | |||
671 | if (GET_VERSION(FormatVersion)((FormatVersion) & ~0xff00000000000000ULL) > | |||
672 | IndexedInstrProf::ProfVersion::CurrentVersion) | |||
673 | return error(instrprof_error::unsupported_version); | |||
674 | ||||
675 | Cur = readSummary((IndexedInstrProf::ProfVersion)FormatVersion, Cur); | |||
676 | ||||
677 | // Read the hash type and start offset. | |||
678 | IndexedInstrProf::HashT HashType = static_cast<IndexedInstrProf::HashT>( | |||
679 | endian::byte_swap<uint64_t, little>(Header->HashType)); | |||
680 | if (HashType > IndexedInstrProf::HashT::Last) | |||
681 | return error(instrprof_error::unsupported_hash_type); | |||
682 | ||||
683 | uint64_t HashOffset = endian::byte_swap<uint64_t, little>(Header->HashOffset); | |||
684 | ||||
685 | // The rest of the file is an on disk hash table. | |||
686 | InstrProfReaderIndexBase *IndexPtr = nullptr; | |||
687 | IndexPtr = new InstrProfReaderIndex<OnDiskHashTableImplV3>( | |||
688 | Start + HashOffset, Cur, Start, HashType, FormatVersion); | |||
689 | Index.reset(IndexPtr); | |||
690 | return success(); | |||
691 | } | |||
692 | ||||
693 | InstrProfSymtab &IndexedInstrProfReader::getSymtab() { | |||
694 | if (Symtab.get()) | |||
695 | return *Symtab.get(); | |||
696 | ||||
697 | std::unique_ptr<InstrProfSymtab> NewSymtab = make_unique<InstrProfSymtab>(); | |||
698 | if (Error E = Index->populateSymtab(*NewSymtab.get())) { | |||
699 | consumeError(error(InstrProfError::take(std::move(E)))); | |||
700 | } | |||
701 | ||||
702 | Symtab = std::move(NewSymtab); | |||
703 | return *Symtab.get(); | |||
704 | } | |||
705 | ||||
706 | Expected<InstrProfRecord> | |||
707 | IndexedInstrProfReader::getInstrProfRecord(StringRef FuncName, | |||
708 | uint64_t FuncHash) { | |||
709 | ArrayRef<NamedInstrProfRecord> Data; | |||
710 | Error Err = Index->getRecords(FuncName, Data); | |||
711 | if (Err) | |||
712 | return std::move(Err); | |||
713 | // Found it. Look for counters with the right hash. | |||
714 | for (unsigned I = 0, E = Data.size(); I < E; ++I) { | |||
715 | // Check for a match and fill the vector if there is one. | |||
716 | if (Data[I].Hash == FuncHash) { | |||
717 | return std::move(Data[I]); | |||
| ||||
718 | } | |||
719 | } | |||
720 | return error(instrprof_error::hash_mismatch); | |||
721 | } | |||
722 | ||||
723 | Error IndexedInstrProfReader::getFunctionCounts(StringRef FuncName, | |||
724 | uint64_t FuncHash, | |||
725 | std::vector<uint64_t> &Counts) { | |||
726 | Expected<InstrProfRecord> Record = getInstrProfRecord(FuncName, FuncHash); | |||
| ||||
727 | if (Error E = Record.takeError()) | |||
728 | return error(std::move(E)); | |||
729 | ||||
730 | Counts = Record.get().Counts; | |||
731 | return success(); | |||
732 | } | |||
733 | ||||
734 | Error IndexedInstrProfReader::readNextRecord(NamedInstrProfRecord &Record) { | |||
735 | ArrayRef<NamedInstrProfRecord> Data; | |||
736 | ||||
737 | Error E = Index->getRecords(Data); | |||
738 | if (E) | |||
739 | return error(std::move(E)); | |||
740 | ||||
741 | Record = Data[RecordIndex++]; | |||
742 | if (RecordIndex >= Data.size()) { | |||
743 | Index->advanceToNextKey(); | |||
744 | RecordIndex = 0; | |||
745 | } | |||
746 | return success(); | |||
747 | } |
1 | //===- llvm/Support/Error.h - Recoverable error handling --------*- C++ -*-===// |
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 | // |
10 | // This file defines an API used to report recoverable errors. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_SUPPORT_ERROR_H |
15 | #define LLVM_SUPPORT_ERROR_H |
16 | |
17 | #include "llvm/ADT/SmallVector.h" |
18 | #include "llvm/ADT/STLExtras.h" |
19 | #include "llvm/ADT/StringExtras.h" |
20 | #include "llvm/ADT/Twine.h" |
21 | #include "llvm/Config/abi-breaking.h" |
22 | #include "llvm/Support/AlignOf.h" |
23 | #include "llvm/Support/Compiler.h" |
24 | #include "llvm/Support/Debug.h" |
25 | #include "llvm/Support/ErrorHandling.h" |
26 | #include "llvm/Support/ErrorOr.h" |
27 | #include "llvm/Support/raw_ostream.h" |
28 | #include <algorithm> |
29 | #include <cassert> |
30 | #include <cstdint> |
31 | #include <cstdlib> |
32 | #include <functional> |
33 | #include <memory> |
34 | #include <new> |
35 | #include <string> |
36 | #include <system_error> |
37 | #include <type_traits> |
38 | #include <utility> |
39 | #include <vector> |
40 | |
41 | namespace llvm { |
42 | |
43 | class ErrorSuccess; |
44 | |
45 | /// Base class for error info classes. Do not extend this directly: Extend |
46 | /// the ErrorInfo template subclass instead. |
47 | class ErrorInfoBase { |
48 | public: |
49 | virtual ~ErrorInfoBase() = default; |
50 | |
51 | /// Print an error message to an output stream. |
52 | virtual void log(raw_ostream &OS) const = 0; |
53 | |
54 | /// Return the error message as a string. |
55 | virtual std::string message() const { |
56 | std::string Msg; |
57 | raw_string_ostream OS(Msg); |
58 | log(OS); |
59 | return OS.str(); |
60 | } |
61 | |
62 | /// Convert this error to a std::error_code. |
63 | /// |
64 | /// This is a temporary crutch to enable interaction with code still |
65 | /// using std::error_code. It will be removed in the future. |
66 | virtual std::error_code convertToErrorCode() const = 0; |
67 | |
68 | // Returns the class ID for this type. |
69 | static const void *classID() { return &ID; } |
70 | |
71 | // Returns the class ID for the dynamic type of this ErrorInfoBase instance. |
72 | virtual const void *dynamicClassID() const = 0; |
73 | |
74 | // Check whether this instance is a subclass of the class identified by |
75 | // ClassID. |
76 | virtual bool isA(const void *const ClassID) const { |
77 | return ClassID == classID(); |
78 | } |
79 | |
80 | // Check whether this instance is a subclass of ErrorInfoT. |
81 | template <typename ErrorInfoT> bool isA() const { |
82 | return isA(ErrorInfoT::classID()); |
83 | } |
84 | |
85 | private: |
86 | virtual void anchor(); |
87 | |
88 | static char ID; |
89 | }; |
90 | |
91 | /// Lightweight error class with error context and mandatory checking. |
92 | /// |
93 | /// Instances of this class wrap a ErrorInfoBase pointer. Failure states |
94 | /// are represented by setting the pointer to a ErrorInfoBase subclass |
95 | /// instance containing information describing the failure. Success is |
96 | /// represented by a null pointer value. |
97 | /// |
98 | /// Instances of Error also contains a 'Checked' flag, which must be set |
99 | /// before the destructor is called, otherwise the destructor will trigger a |
100 | /// runtime error. This enforces at runtime the requirement that all Error |
101 | /// instances be checked or returned to the caller. |
102 | /// |
103 | /// There are two ways to set the checked flag, depending on what state the |
104 | /// Error instance is in. For Error instances indicating success, it |
105 | /// is sufficient to invoke the boolean conversion operator. E.g.: |
106 | /// |
107 | /// @code{.cpp} |
108 | /// Error foo(<...>); |
109 | /// |
110 | /// if (auto E = foo(<...>)) |
111 | /// return E; // <- Return E if it is in the error state. |
112 | /// // We have verified that E was in the success state. It can now be safely |
113 | /// // destroyed. |
114 | /// @endcode |
115 | /// |
116 | /// A success value *can not* be dropped. For example, just calling 'foo(<...>)' |
117 | /// without testing the return value will raise a runtime error, even if foo |
118 | /// returns success. |
119 | /// |
120 | /// For Error instances representing failure, you must use either the |
121 | /// handleErrors or handleAllErrors function with a typed handler. E.g.: |
122 | /// |
123 | /// @code{.cpp} |
124 | /// class MyErrorInfo : public ErrorInfo<MyErrorInfo> { |
125 | /// // Custom error info. |
126 | /// }; |
127 | /// |
128 | /// Error foo(<...>) { return make_error<MyErrorInfo>(...); } |
129 | /// |
130 | /// auto E = foo(<...>); // <- foo returns failure with MyErrorInfo. |
131 | /// auto NewE = |
132 | /// handleErrors(E, |
133 | /// [](const MyErrorInfo &M) { |
134 | /// // Deal with the error. |
135 | /// }, |
136 | /// [](std::unique_ptr<OtherError> M) -> Error { |
137 | /// if (canHandle(*M)) { |
138 | /// // handle error. |
139 | /// return Error::success(); |
140 | /// } |
141 | /// // Couldn't handle this error instance. Pass it up the stack. |
142 | /// return Error(std::move(M)); |
143 | /// ); |
144 | /// // Note - we must check or return NewE in case any of the handlers |
145 | /// // returned a new error. |
146 | /// @endcode |
147 | /// |
148 | /// The handleAllErrors function is identical to handleErrors, except |
149 | /// that it has a void return type, and requires all errors to be handled and |
150 | /// no new errors be returned. It prevents errors (assuming they can all be |
151 | /// handled) from having to be bubbled all the way to the top-level. |
152 | /// |
153 | /// *All* Error instances must be checked before destruction, even if |
154 | /// they're moved-assigned or constructed from Success values that have already |
155 | /// been checked. This enforces checking through all levels of the call stack. |
156 | class LLVM_NODISCARD[[clang::warn_unused_result]] Error { |
157 | // ErrorList needs to be able to yank ErrorInfoBase pointers out of this |
158 | // class to add to the error list. |
159 | friend class ErrorList; |
160 | |
161 | // handleErrors needs to be able to set the Checked flag. |
162 | template <typename... HandlerTs> |
163 | friend Error handleErrors(Error E, HandlerTs &&... Handlers); |
164 | |
165 | // Expected<T> needs to be able to steal the payload when constructed from an |
166 | // error. |
167 | template <typename T> friend class Expected; |
168 | |
169 | protected: |
170 | /// Create a success value. Prefer using 'Error::success()' for readability |
171 | Error() { |
172 | setPtr(nullptr); |
173 | setChecked(false); |
174 | } |
175 | |
176 | public: |
177 | /// Create a success value. |
178 | static ErrorSuccess success(); |
179 | |
180 | // Errors are not copy-constructable. |
181 | Error(const Error &Other) = delete; |
182 | |
183 | /// Move-construct an error value. The newly constructed error is considered |
184 | /// unchecked, even if the source error had been checked. The original error |
185 | /// becomes a checked Success value, regardless of its original state. |
186 | Error(Error &&Other) { |
187 | setChecked(true); |
188 | *this = std::move(Other); |
189 | } |
190 | |
191 | /// Create an error value. Prefer using the 'make_error' function, but |
192 | /// this constructor can be useful when "re-throwing" errors from handlers. |
193 | Error(std::unique_ptr<ErrorInfoBase> Payload) { |
194 | setPtr(Payload.release()); |
195 | setChecked(false); |
196 | } |
197 | |
198 | // Errors are not copy-assignable. |
199 | Error &operator=(const Error &Other) = delete; |
200 | |
201 | /// Move-assign an error value. The current error must represent success, you |
202 | /// you cannot overwrite an unhandled error. The current error is then |
203 | /// considered unchecked. The source error becomes a checked success value, |
204 | /// regardless of its original state. |
205 | Error &operator=(Error &&Other) { |
206 | // Don't allow overwriting of unchecked values. |
207 | assertIsChecked(); |
208 | setPtr(Other.getPtr()); |
209 | |
210 | // This Error is unchecked, even if the source error was checked. |
211 | setChecked(false); |
212 | |
213 | // Null out Other's payload and set its checked bit. |
214 | Other.setPtr(nullptr); |
215 | Other.setChecked(true); |
216 | |
217 | return *this; |
218 | } |
219 | |
220 | /// Destroy a Error. Fails with a call to abort() if the error is |
221 | /// unchecked. |
222 | ~Error() { |
223 | assertIsChecked(); |
224 | delete getPtr(); |
225 | } |
226 | |
227 | /// Bool conversion. Returns true if this Error is in a failure state, |
228 | /// and false if it is in an accept state. If the error is in a Success state |
229 | /// it will be considered checked. |
230 | explicit operator bool() { |
231 | setChecked(getPtr() == nullptr); |
232 | return getPtr() != nullptr; |
233 | } |
234 | |
235 | /// Check whether one error is a subclass of another. |
236 | template <typename ErrT> bool isA() const { |
237 | return getPtr() && getPtr()->isA(ErrT::classID()); |
238 | } |
239 | |
240 | /// Returns the dynamic class id of this error, or null if this is a success |
241 | /// value. |
242 | const void* dynamicClassID() const { |
243 | if (!getPtr()) |
244 | return nullptr; |
245 | return getPtr()->dynamicClassID(); |
246 | } |
247 | |
248 | private: |
249 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 |
250 | // assertIsChecked() happens very frequently, but under normal circumstances |
251 | // is supposed to be a no-op. So we want it to be inlined, but having a bunch |
252 | // of debug prints can cause the function to be too large for inlining. So |
253 | // it's important that we define this function out of line so that it can't be |
254 | // inlined. |
255 | LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) |
256 | void fatalUncheckedError() const; |
257 | #endif |
258 | |
259 | void assertIsChecked() { |
260 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 |
261 | if (LLVM_UNLIKELY(!getChecked() || getPtr())__builtin_expect((bool)(!getChecked() || getPtr()), false)) |
262 | fatalUncheckedError(); |
263 | #endif |
264 | } |
265 | |
266 | ErrorInfoBase *getPtr() const { |
267 | return reinterpret_cast<ErrorInfoBase*>( |
268 | reinterpret_cast<uintptr_t>(Payload) & |
269 | ~static_cast<uintptr_t>(0x1)); |
270 | } |
271 | |
272 | void setPtr(ErrorInfoBase *EI) { |
273 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 |
274 | Payload = reinterpret_cast<ErrorInfoBase*>( |
275 | (reinterpret_cast<uintptr_t>(EI) & |
276 | ~static_cast<uintptr_t>(0x1)) | |
277 | (reinterpret_cast<uintptr_t>(Payload) & 0x1)); |
278 | #else |
279 | Payload = EI; |
280 | #endif |
281 | } |
282 | |
283 | bool getChecked() const { |
284 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 |
285 | return (reinterpret_cast<uintptr_t>(Payload) & 0x1) == 0; |
286 | #else |
287 | return true; |
288 | #endif |
289 | } |
290 | |
291 | void setChecked(bool V) { |
292 | Payload = reinterpret_cast<ErrorInfoBase*>( |
293 | (reinterpret_cast<uintptr_t>(Payload) & |
294 | ~static_cast<uintptr_t>(0x1)) | |
295 | (V ? 0 : 1)); |
296 | } |
297 | |
298 | std::unique_ptr<ErrorInfoBase> takePayload() { |
299 | std::unique_ptr<ErrorInfoBase> Tmp(getPtr()); |
300 | setPtr(nullptr); |
301 | setChecked(true); |
302 | return Tmp; |
303 | } |
304 | |
305 | ErrorInfoBase *Payload = nullptr; |
306 | }; |
307 | |
308 | /// Subclass of Error for the sole purpose of identifying the success path in |
309 | /// the type system. This allows to catch invalid conversion to Expected<T> at |
310 | /// compile time. |
311 | class ErrorSuccess : public Error {}; |
312 | |
313 | inline ErrorSuccess Error::success() { return ErrorSuccess(); } |
314 | |
315 | /// Make a Error instance representing failure using the given error info |
316 | /// type. |
317 | template <typename ErrT, typename... ArgTs> Error make_error(ArgTs &&... Args) { |
318 | return Error(llvm::make_unique<ErrT>(std::forward<ArgTs>(Args)...)); |
319 | } |
320 | |
321 | /// Base class for user error types. Users should declare their error types |
322 | /// like: |
323 | /// |
324 | /// class MyError : public ErrorInfo<MyError> { |
325 | /// .... |
326 | /// }; |
327 | /// |
328 | /// This class provides an implementation of the ErrorInfoBase::kind |
329 | /// method, which is used by the Error RTTI system. |
330 | template <typename ThisErrT, typename ParentErrT = ErrorInfoBase> |
331 | class ErrorInfo : public ParentErrT { |
332 | public: |
333 | static const void *classID() { return &ThisErrT::ID; } |
334 | |
335 | const void *dynamicClassID() const override { return &ThisErrT::ID; } |
336 | |
337 | bool isA(const void *const ClassID) const override { |
338 | return ClassID == classID() || ParentErrT::isA(ClassID); |
339 | } |
340 | }; |
341 | |
342 | /// Special ErrorInfo subclass representing a list of ErrorInfos. |
343 | /// Instances of this class are constructed by joinError. |
344 | class ErrorList final : public ErrorInfo<ErrorList> { |
345 | // handleErrors needs to be able to iterate the payload list of an |
346 | // ErrorList. |
347 | template <typename... HandlerTs> |
348 | friend Error handleErrors(Error E, HandlerTs &&... Handlers); |
349 | |
350 | // joinErrors is implemented in terms of join. |
351 | friend Error joinErrors(Error, Error); |
352 | |
353 | public: |
354 | void log(raw_ostream &OS) const override { |
355 | OS << "Multiple errors:\n"; |
356 | for (auto &ErrPayload : Payloads) { |
357 | ErrPayload->log(OS); |
358 | OS << "\n"; |
359 | } |
360 | } |
361 | |
362 | std::error_code convertToErrorCode() const override; |
363 | |
364 | // Used by ErrorInfo::classID. |
365 | static char ID; |
366 | |
367 | private: |
368 | ErrorList(std::unique_ptr<ErrorInfoBase> Payload1, |
369 | std::unique_ptr<ErrorInfoBase> Payload2) { |
370 | assert(!Payload1->isA<ErrorList>() && !Payload2->isA<ErrorList>() &&(static_cast <bool> (!Payload1->isA<ErrorList> () && !Payload2->isA<ErrorList>() && "ErrorList constructor payloads should be singleton errors") ? void (0) : __assert_fail ("!Payload1->isA<ErrorList>() && !Payload2->isA<ErrorList>() && \"ErrorList constructor payloads should be singleton errors\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 371, __extension__ __PRETTY_FUNCTION__)) |
371 | "ErrorList constructor payloads should be singleton errors")(static_cast <bool> (!Payload1->isA<ErrorList> () && !Payload2->isA<ErrorList>() && "ErrorList constructor payloads should be singleton errors") ? void (0) : __assert_fail ("!Payload1->isA<ErrorList>() && !Payload2->isA<ErrorList>() && \"ErrorList constructor payloads should be singleton errors\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 371, __extension__ __PRETTY_FUNCTION__)); |
372 | Payloads.push_back(std::move(Payload1)); |
373 | Payloads.push_back(std::move(Payload2)); |
374 | } |
375 | |
376 | static Error join(Error E1, Error E2) { |
377 | if (!E1) |
378 | return E2; |
379 | if (!E2) |
380 | return E1; |
381 | if (E1.isA<ErrorList>()) { |
382 | auto &E1List = static_cast<ErrorList &>(*E1.getPtr()); |
383 | if (E2.isA<ErrorList>()) { |
384 | auto E2Payload = E2.takePayload(); |
385 | auto &E2List = static_cast<ErrorList &>(*E2Payload); |
386 | for (auto &Payload : E2List.Payloads) |
387 | E1List.Payloads.push_back(std::move(Payload)); |
388 | } else |
389 | E1List.Payloads.push_back(E2.takePayload()); |
390 | |
391 | return E1; |
392 | } |
393 | if (E2.isA<ErrorList>()) { |
394 | auto &E2List = static_cast<ErrorList &>(*E2.getPtr()); |
395 | E2List.Payloads.insert(E2List.Payloads.begin(), E1.takePayload()); |
396 | return E2; |
397 | } |
398 | return Error(std::unique_ptr<ErrorList>( |
399 | new ErrorList(E1.takePayload(), E2.takePayload()))); |
400 | } |
401 | |
402 | std::vector<std::unique_ptr<ErrorInfoBase>> Payloads; |
403 | }; |
404 | |
405 | /// Concatenate errors. The resulting Error is unchecked, and contains the |
406 | /// ErrorInfo(s), if any, contained in E1, followed by the |
407 | /// ErrorInfo(s), if any, contained in E2. |
408 | inline Error joinErrors(Error E1, Error E2) { |
409 | return ErrorList::join(std::move(E1), std::move(E2)); |
410 | } |
411 | |
412 | /// Tagged union holding either a T or a Error. |
413 | /// |
414 | /// This class parallels ErrorOr, but replaces error_code with Error. Since |
415 | /// Error cannot be copied, this class replaces getError() with |
416 | /// takeError(). It also adds an bool errorIsA<ErrT>() method for testing the |
417 | /// error class type. |
418 | template <class T> class LLVM_NODISCARD[[clang::warn_unused_result]] Expected { |
419 | template <class T1> friend class ExpectedAsOutParameter; |
420 | template <class OtherT> friend class Expected; |
421 | |
422 | static const bool isRef = std::is_reference<T>::value; |
423 | |
424 | using wrap = ReferenceStorage<typename std::remove_reference<T>::type>; |
425 | |
426 | using error_type = std::unique_ptr<ErrorInfoBase>; |
427 | |
428 | public: |
429 | using storage_type = typename std::conditional<isRef, wrap, T>::type; |
430 | using value_type = T; |
431 | |
432 | private: |
433 | using reference = typename std::remove_reference<T>::type &; |
434 | using const_reference = const typename std::remove_reference<T>::type &; |
435 | using pointer = typename std::remove_reference<T>::type *; |
436 | using const_pointer = const typename std::remove_reference<T>::type *; |
437 | |
438 | public: |
439 | /// Create an Expected<T> error value from the given Error. |
440 | Expected(Error Err) |
441 | : HasError(true) |
442 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 |
443 | // Expected is unchecked upon construction in Debug builds. |
444 | , Unchecked(true) |
445 | #endif |
446 | { |
447 | assert(Err && "Cannot create Expected<T> from Error success value.")(static_cast <bool> (Err && "Cannot create Expected<T> from Error success value." ) ? void (0) : __assert_fail ("Err && \"Cannot create Expected<T> from Error success value.\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 447, __extension__ __PRETTY_FUNCTION__)); |
448 | new (getErrorStorage()) error_type(Err.takePayload()); |
449 | } |
450 | |
451 | /// Forbid to convert from Error::success() implicitly, this avoids having |
452 | /// Expected<T> foo() { return Error::success(); } which compiles otherwise |
453 | /// but triggers the assertion above. |
454 | Expected(ErrorSuccess) = delete; |
455 | |
456 | /// Create an Expected<T> success value from the given OtherT value, which |
457 | /// must be convertible to T. |
458 | template <typename OtherT> |
459 | Expected(OtherT &&Val, |
460 | typename std::enable_if<std::is_convertible<OtherT, T>::value>::type |
461 | * = nullptr) |
462 | : HasError(false) |
463 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 |
464 | // Expected is unchecked upon construction in Debug builds. |
465 | , Unchecked(true) |
466 | #endif |
467 | { |
468 | new (getStorage()) storage_type(std::forward<OtherT>(Val)); |
469 | } |
470 | |
471 | /// Move construct an Expected<T> value. |
472 | Expected(Expected &&Other) { moveConstruct(std::move(Other)); } |
473 | |
474 | /// Move construct an Expected<T> value from an Expected<OtherT>, where OtherT |
475 | /// must be convertible to T. |
476 | template <class OtherT> |
477 | Expected(Expected<OtherT> &&Other, |
478 | typename std::enable_if<std::is_convertible<OtherT, T>::value>::type |
479 | * = nullptr) { |
480 | moveConstruct(std::move(Other)); |
481 | } |
482 | |
483 | /// Move construct an Expected<T> value from an Expected<OtherT>, where OtherT |
484 | /// isn't convertible to T. |
485 | template <class OtherT> |
486 | explicit Expected( |
487 | Expected<OtherT> &&Other, |
488 | typename std::enable_if<!std::is_convertible<OtherT, T>::value>::type * = |
489 | nullptr) { |
490 | moveConstruct(std::move(Other)); |
491 | } |
492 | |
493 | /// Move-assign from another Expected<T>. |
494 | Expected &operator=(Expected &&Other) { |
495 | moveAssign(std::move(Other)); |
496 | return *this; |
497 | } |
498 | |
499 | /// Destroy an Expected<T>. |
500 | ~Expected() { |
501 | assertIsChecked(); |
502 | if (!HasError) |
503 | getStorage()->~storage_type(); |
504 | else |
505 | getErrorStorage()->~error_type(); |
506 | } |
507 | |
508 | /// \brief Return false if there is an error. |
509 | explicit operator bool() { |
510 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 |
511 | Unchecked = HasError; |
512 | #endif |
513 | return !HasError; |
514 | } |
515 | |
516 | /// \brief Returns a reference to the stored T value. |
517 | reference get() { |
518 | assertIsChecked(); |
519 | return *getStorage(); |
520 | } |
521 | |
522 | /// \brief Returns a const reference to the stored T value. |
523 | const_reference get() const { |
524 | assertIsChecked(); |
525 | return const_cast<Expected<T> *>(this)->get(); |
526 | } |
527 | |
528 | /// \brief Check that this Expected<T> is an error of type ErrT. |
529 | template <typename ErrT> bool errorIsA() const { |
530 | return HasError && (*getErrorStorage())->template isA<ErrT>(); |
531 | } |
532 | |
533 | /// \brief Take ownership of the stored error. |
534 | /// After calling this the Expected<T> is in an indeterminate state that can |
535 | /// only be safely destructed. No further calls (beside the destructor) should |
536 | /// be made on the Expected<T> vaule. |
537 | Error takeError() { |
538 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 |
539 | Unchecked = false; |
540 | #endif |
541 | return HasError ? Error(std::move(*getErrorStorage())) : Error::success(); |
542 | } |
543 | |
544 | /// \brief Returns a pointer to the stored T value. |
545 | pointer operator->() { |
546 | assertIsChecked(); |
547 | return toPointer(getStorage()); |
548 | } |
549 | |
550 | /// \brief Returns a const pointer to the stored T value. |
551 | const_pointer operator->() const { |
552 | assertIsChecked(); |
553 | return toPointer(getStorage()); |
554 | } |
555 | |
556 | /// \brief Returns a reference to the stored T value. |
557 | reference operator*() { |
558 | assertIsChecked(); |
559 | return *getStorage(); |
560 | } |
561 | |
562 | /// \brief Returns a const reference to the stored T value. |
563 | const_reference operator*() const { |
564 | assertIsChecked(); |
565 | return *getStorage(); |
566 | } |
567 | |
568 | private: |
569 | template <class T1> |
570 | static bool compareThisIfSameType(const T1 &a, const T1 &b) { |
571 | return &a == &b; |
572 | } |
573 | |
574 | template <class T1, class T2> |
575 | static bool compareThisIfSameType(const T1 &a, const T2 &b) { |
576 | return false; |
577 | } |
578 | |
579 | template <class OtherT> void moveConstruct(Expected<OtherT> &&Other) { |
580 | HasError = Other.HasError; |
581 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 |
582 | Unchecked = true; |
583 | Other.Unchecked = false; |
584 | #endif |
585 | |
586 | if (!HasError) |
587 | new (getStorage()) storage_type(std::move(*Other.getStorage())); |
588 | else |
589 | new (getErrorStorage()) error_type(std::move(*Other.getErrorStorage())); |
590 | } |
591 | |
592 | template <class OtherT> void moveAssign(Expected<OtherT> &&Other) { |
593 | assertIsChecked(); |
594 | |
595 | if (compareThisIfSameType(*this, Other)) |
596 | return; |
597 | |
598 | this->~Expected(); |
599 | new (this) Expected(std::move(Other)); |
600 | } |
601 | |
602 | pointer toPointer(pointer Val) { return Val; } |
603 | |
604 | const_pointer toPointer(const_pointer Val) const { return Val; } |
605 | |
606 | pointer toPointer(wrap *Val) { return &Val->get(); } |
607 | |
608 | const_pointer toPointer(const wrap *Val) const { return &Val->get(); } |
609 | |
610 | storage_type *getStorage() { |
611 | assert(!HasError && "Cannot get value when an error exists!")(static_cast <bool> (!HasError && "Cannot get value when an error exists!" ) ? void (0) : __assert_fail ("!HasError && \"Cannot get value when an error exists!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 611, __extension__ __PRETTY_FUNCTION__)); |
612 | return reinterpret_cast<storage_type *>(TStorage.buffer); |
613 | } |
614 | |
615 | const storage_type *getStorage() const { |
616 | assert(!HasError && "Cannot get value when an error exists!")(static_cast <bool> (!HasError && "Cannot get value when an error exists!" ) ? void (0) : __assert_fail ("!HasError && \"Cannot get value when an error exists!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 616, __extension__ __PRETTY_FUNCTION__)); |
617 | return reinterpret_cast<const storage_type *>(TStorage.buffer); |
618 | } |
619 | |
620 | error_type *getErrorStorage() { |
621 | assert(HasError && "Cannot get error when a value exists!")(static_cast <bool> (HasError && "Cannot get error when a value exists!" ) ? void (0) : __assert_fail ("HasError && \"Cannot get error when a value exists!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 621, __extension__ __PRETTY_FUNCTION__)); |
622 | return reinterpret_cast<error_type *>(ErrorStorage.buffer); |
623 | } |
624 | |
625 | const error_type *getErrorStorage() const { |
626 | assert(HasError && "Cannot get error when a value exists!")(static_cast <bool> (HasError && "Cannot get error when a value exists!" ) ? void (0) : __assert_fail ("HasError && \"Cannot get error when a value exists!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 626, __extension__ __PRETTY_FUNCTION__)); |
627 | return reinterpret_cast<const error_type *>(ErrorStorage.buffer); |
628 | } |
629 | |
630 | // Used by ExpectedAsOutParameter to reset the checked flag. |
631 | void setUnchecked() { |
632 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 |
633 | Unchecked = true; |
634 | #endif |
635 | } |
636 | |
637 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 |
638 | LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) |
639 | LLVM_ATTRIBUTE_NOINLINE__attribute__((noinline)) |
640 | void fatalUncheckedExpected() const { |
641 | dbgs() << "Expected<T> must be checked before access or destruction.\n"; |
642 | if (HasError) { |
643 | dbgs() << "Unchecked Expected<T> contained error:\n"; |
644 | (*getErrorStorage())->log(dbgs()); |
645 | } else |
646 | dbgs() << "Expected<T> value was in success state. (Note: Expected<T> " |
647 | "values in success mode must still be checked prior to being " |
648 | "destroyed).\n"; |
649 | abort(); |
650 | } |
651 | #endif |
652 | |
653 | void assertIsChecked() { |
654 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 |
655 | if (LLVM_UNLIKELY(Unchecked)__builtin_expect((bool)(Unchecked), false)) |
656 | fatalUncheckedExpected(); |
657 | #endif |
658 | } |
659 | |
660 | union { |
661 | AlignedCharArrayUnion<storage_type> TStorage; |
662 | AlignedCharArrayUnion<error_type> ErrorStorage; |
663 | }; |
664 | bool HasError : 1; |
665 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS1 |
666 | bool Unchecked : 1; |
667 | #endif |
668 | }; |
669 | |
670 | /// Report a serious error, calling any installed error handler. See |
671 | /// ErrorHandling.h. |
672 | LLVM_ATTRIBUTE_NORETURN__attribute__((noreturn)) void report_fatal_error(Error Err, |
673 | bool gen_crash_diag = true); |
674 | |
675 | /// Report a fatal error if Err is a failure value. |
676 | /// |
677 | /// This function can be used to wrap calls to fallible functions ONLY when it |
678 | /// is known that the Error will always be a success value. E.g. |
679 | /// |
680 | /// @code{.cpp} |
681 | /// // foo only attempts the fallible operation if DoFallibleOperation is |
682 | /// // true. If DoFallibleOperation is false then foo always returns |
683 | /// // Error::success(). |
684 | /// Error foo(bool DoFallibleOperation); |
685 | /// |
686 | /// cantFail(foo(false)); |
687 | /// @endcode |
688 | inline void cantFail(Error Err, const char *Msg = nullptr) { |
689 | if (Err) { |
690 | if (!Msg) |
691 | Msg = "Failure value returned from cantFail wrapped call"; |
692 | llvm_unreachable(Msg)::llvm::llvm_unreachable_internal(Msg, "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 692); |
693 | } |
694 | } |
695 | |
696 | /// Report a fatal error if ValOrErr is a failure value, otherwise unwraps and |
697 | /// returns the contained value. |
698 | /// |
699 | /// This function can be used to wrap calls to fallible functions ONLY when it |
700 | /// is known that the Error will always be a success value. E.g. |
701 | /// |
702 | /// @code{.cpp} |
703 | /// // foo only attempts the fallible operation if DoFallibleOperation is |
704 | /// // true. If DoFallibleOperation is false then foo always returns an int. |
705 | /// Expected<int> foo(bool DoFallibleOperation); |
706 | /// |
707 | /// int X = cantFail(foo(false)); |
708 | /// @endcode |
709 | template <typename T> |
710 | T cantFail(Expected<T> ValOrErr, const char *Msg = nullptr) { |
711 | if (ValOrErr) |
712 | return std::move(*ValOrErr); |
713 | else { |
714 | if (!Msg) |
715 | Msg = "Failure value returned from cantFail wrapped call"; |
716 | llvm_unreachable(Msg)::llvm::llvm_unreachable_internal(Msg, "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 716); |
717 | } |
718 | } |
719 | |
720 | /// Report a fatal error if ValOrErr is a failure value, otherwise unwraps and |
721 | /// returns the contained reference. |
722 | /// |
723 | /// This function can be used to wrap calls to fallible functions ONLY when it |
724 | /// is known that the Error will always be a success value. E.g. |
725 | /// |
726 | /// @code{.cpp} |
727 | /// // foo only attempts the fallible operation if DoFallibleOperation is |
728 | /// // true. If DoFallibleOperation is false then foo always returns a Bar&. |
729 | /// Expected<Bar&> foo(bool DoFallibleOperation); |
730 | /// |
731 | /// Bar &X = cantFail(foo(false)); |
732 | /// @endcode |
733 | template <typename T> |
734 | T& cantFail(Expected<T&> ValOrErr, const char *Msg = nullptr) { |
735 | if (ValOrErr) |
736 | return *ValOrErr; |
737 | else { |
738 | if (!Msg) |
739 | Msg = "Failure value returned from cantFail wrapped call"; |
740 | llvm_unreachable(Msg)::llvm::llvm_unreachable_internal(Msg, "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 740); |
741 | } |
742 | } |
743 | |
744 | /// Helper for testing applicability of, and applying, handlers for |
745 | /// ErrorInfo types. |
746 | template <typename HandlerT> |
747 | class ErrorHandlerTraits |
748 | : public ErrorHandlerTraits<decltype( |
749 | &std::remove_reference<HandlerT>::type::operator())> {}; |
750 | |
751 | // Specialization functions of the form 'Error (const ErrT&)'. |
752 | template <typename ErrT> class ErrorHandlerTraits<Error (&)(ErrT &)> { |
753 | public: |
754 | static bool appliesTo(const ErrorInfoBase &E) { |
755 | return E.template isA<ErrT>(); |
756 | } |
757 | |
758 | template <typename HandlerT> |
759 | static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) { |
760 | assert(appliesTo(*E) && "Applying incorrect handler")(static_cast <bool> (appliesTo(*E) && "Applying incorrect handler" ) ? void (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 760, __extension__ __PRETTY_FUNCTION__)); |
761 | return H(static_cast<ErrT &>(*E)); |
762 | } |
763 | }; |
764 | |
765 | // Specialization functions of the form 'void (const ErrT&)'. |
766 | template <typename ErrT> class ErrorHandlerTraits<void (&)(ErrT &)> { |
767 | public: |
768 | static bool appliesTo(const ErrorInfoBase &E) { |
769 | return E.template isA<ErrT>(); |
770 | } |
771 | |
772 | template <typename HandlerT> |
773 | static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) { |
774 | assert(appliesTo(*E) && "Applying incorrect handler")(static_cast <bool> (appliesTo(*E) && "Applying incorrect handler" ) ? void (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 774, __extension__ __PRETTY_FUNCTION__)); |
775 | H(static_cast<ErrT &>(*E)); |
776 | return Error::success(); |
777 | } |
778 | }; |
779 | |
780 | /// Specialization for functions of the form 'Error (std::unique_ptr<ErrT>)'. |
781 | template <typename ErrT> |
782 | class ErrorHandlerTraits<Error (&)(std::unique_ptr<ErrT>)> { |
783 | public: |
784 | static bool appliesTo(const ErrorInfoBase &E) { |
785 | return E.template isA<ErrT>(); |
786 | } |
787 | |
788 | template <typename HandlerT> |
789 | static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) { |
790 | assert(appliesTo(*E) && "Applying incorrect handler")(static_cast <bool> (appliesTo(*E) && "Applying incorrect handler" ) ? void (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 790, __extension__ __PRETTY_FUNCTION__)); |
791 | std::unique_ptr<ErrT> SubE(static_cast<ErrT *>(E.release())); |
792 | return H(std::move(SubE)); |
793 | } |
794 | }; |
795 | |
796 | /// Specialization for functions of the form 'void (std::unique_ptr<ErrT>)'. |
797 | template <typename ErrT> |
798 | class ErrorHandlerTraits<void (&)(std::unique_ptr<ErrT>)> { |
799 | public: |
800 | static bool appliesTo(const ErrorInfoBase &E) { |
801 | return E.template isA<ErrT>(); |
802 | } |
803 | |
804 | template <typename HandlerT> |
805 | static Error apply(HandlerT &&H, std::unique_ptr<ErrorInfoBase> E) { |
806 | assert(appliesTo(*E) && "Applying incorrect handler")(static_cast <bool> (appliesTo(*E) && "Applying incorrect handler" ) ? void (0) : __assert_fail ("appliesTo(*E) && \"Applying incorrect handler\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/Support/Error.h" , 806, __extension__ __PRETTY_FUNCTION__)); |
807 | std::unique_ptr<ErrT> SubE(static_cast<ErrT *>(E.release())); |
808 | H(std::move(SubE)); |
809 | return Error::success(); |
810 | } |
811 | }; |
812 | |
813 | // Specialization for member functions of the form 'RetT (const ErrT&)'. |
814 | template <typename C, typename RetT, typename ErrT> |
815 | class ErrorHandlerTraits<RetT (C::*)(ErrT &)> |
816 | : public ErrorHandlerTraits<RetT (&)(ErrT &)> {}; |
817 | |
818 | // Specialization for member functions of the form 'RetT (const ErrT&) const'. |
819 | template <typename C, typename RetT, typename ErrT> |
820 | class ErrorHandlerTraits<RetT (C::*)(ErrT &) const> |
821 | : public ErrorHandlerTraits<RetT (&)(ErrT &)> {}; |
822 | |
823 | // Specialization for member functions of the form 'RetT (const ErrT&)'. |
824 | template <typename C, typename RetT, typename ErrT> |
825 | class ErrorHandlerTraits<RetT (C::*)(const ErrT &)> |
826 | : public ErrorHandlerTraits<RetT (&)(ErrT &)> {}; |
827 | |
828 | // Specialization for member functions of the form 'RetT (const ErrT&) const'. |
829 | template <typename C, typename RetT, typename ErrT> |
830 | class ErrorHandlerTraits<RetT (C::*)(const ErrT &) const> |
831 | : public ErrorHandlerTraits<RetT (&)(ErrT &)> {}; |
832 | |
833 | /// Specialization for member functions of the form |
834 | /// 'RetT (std::unique_ptr<ErrT>)'. |
835 | template <typename C, typename RetT, typename ErrT> |
836 | class ErrorHandlerTraits<RetT (C::*)(std::unique_ptr<ErrT>)> |
837 | : public ErrorHandlerTraits<RetT (&)(std::unique_ptr<ErrT>)> {}; |
838 | |
839 | /// Specialization for member functions of the form |
840 | /// 'RetT (std::unique_ptr<ErrT>) const'. |
841 | template <typename C, typename RetT, typename ErrT> |
842 | class ErrorHandlerTraits<RetT (C::*)(std::unique_ptr<ErrT>) const> |
843 | : public ErrorHandlerTraits<RetT (&)(std::unique_ptr<ErrT>)> {}; |
844 | |
845 | inline Error handleErrorImpl(std::unique_ptr<ErrorInfoBase> Payload) { |
846 | return Error(std::move(Payload)); |
847 | } |
848 | |
849 | template <typename HandlerT, typename... HandlerTs> |
850 | Error handleErrorImpl(std::unique_ptr<ErrorInfoBase> Payload, |
851 | HandlerT &&Handler, HandlerTs &&... Handlers) { |
852 | if (ErrorHandlerTraits<HandlerT>::appliesTo(*Payload)) |
853 | return ErrorHandlerTraits<HandlerT>::apply(std::forward<HandlerT>(Handler), |
854 | std::move(Payload)); |
855 | return handleErrorImpl(std::move(Payload), |
856 | std::forward<HandlerTs>(Handlers)...); |
857 | } |
858 | |
859 | /// Pass the ErrorInfo(s) contained in E to their respective handlers. Any |
860 | /// unhandled errors (or Errors returned by handlers) are re-concatenated and |
861 | /// returned. |
862 | /// Because this function returns an error, its result must also be checked |
863 | /// or returned. If you intend to handle all errors use handleAllErrors |
864 | /// (which returns void, and will abort() on unhandled errors) instead. |
865 | template <typename... HandlerTs> |
866 | Error handleErrors(Error E, HandlerTs &&... Hs) { |
867 | if (!E) |
868 | return Error::success(); |
869 | |
870 | std::unique_ptr<ErrorInfoBase> Payload = E.takePayload(); |
871 | |
872 | if (Payload->isA<ErrorList>()) { |
873 | ErrorList &List = static_cast<ErrorList &>(*Payload); |
874 | Error R; |
875 | for (auto &P : List.Payloads) |
876 | R = ErrorList::join( |
877 | std::move(R), |
878 | handleErrorImpl(std::move(P), std::forward<HandlerTs>(Hs)...)); |
879 | return R; |
880 | } |
881 | |
882 | return handleErrorImpl(std::move(Payload), std::forward<HandlerTs>(Hs)...); |
883 | } |
884 | |
885 | /// Behaves the same as handleErrors, except that by contract all errors |
886 | /// *must* be handled by the given handlers (i.e. there must be no remaining |
887 | /// errors after running the handlers, or llvm_unreachable is called). |
888 | template <typename... HandlerTs> |
889 | void handleAllErrors(Error E, HandlerTs &&... Handlers) { |
890 | cantFail(handleErrors(std::move(E), std::forward<HandlerTs>(Handlers)...)); |
891 | } |
892 | |
893 | /// Check that E is a non-error, then drop it. |
894 | /// If E is an error, llvm_unreachable will be called. |
895 | inline void handleAllErrors(Error E) { |
896 | cantFail(std::move(E)); |
897 | } |
898 | |
899 | /// Handle any errors (if present) in an Expected<T>, then try a recovery path. |
900 | /// |
901 | /// If the incoming value is a success value it is returned unmodified. If it |
902 | /// is a failure value then it the contained error is passed to handleErrors. |
903 | /// If handleErrors is able to handle the error then the RecoveryPath functor |
904 | /// is called to supply the final result. If handleErrors is not able to |
905 | /// handle all errors then the unhandled errors are returned. |
906 | /// |
907 | /// This utility enables the follow pattern: |
908 | /// |
909 | /// @code{.cpp} |
910 | /// enum FooStrategy { Aggressive, Conservative }; |
911 | /// Expected<Foo> foo(FooStrategy S); |
912 | /// |
913 | /// auto ResultOrErr = |
914 | /// handleExpected( |
915 | /// foo(Aggressive), |
916 | /// []() { return foo(Conservative); }, |
917 | /// [](AggressiveStrategyError&) { |
918 | /// // Implicitly conusme this - we'll recover by using a conservative |
919 | /// // strategy. |
920 | /// }); |
921 | /// |
922 | /// @endcode |
923 | template <typename T, typename RecoveryFtor, typename... HandlerTs> |
924 | Expected<T> handleExpected(Expected<T> ValOrErr, RecoveryFtor &&RecoveryPath, |
925 | HandlerTs &&... Handlers) { |
926 | if (ValOrErr) |
927 | return ValOrErr; |
928 | |
929 | if (auto Err = handleErrors(ValOrErr.takeError(), |
930 | std::forward<HandlerTs>(Handlers)...)) |
931 | return std::move(Err); |
932 | |
933 | return RecoveryPath(); |
934 | } |
935 | |
936 | /// Log all errors (if any) in E to OS. If there are any errors, ErrorBanner |
937 | /// will be printed before the first one is logged. A newline will be printed |
938 | /// after each error. |
939 | /// |
940 | /// This is useful in the base level of your program to allow clean termination |
941 | /// (allowing clean deallocation of resources, etc.), while reporting error |
942 | /// information to the user. |
943 | void logAllUnhandledErrors(Error E, raw_ostream &OS, Twine ErrorBanner); |
944 | |
945 | /// Write all error messages (if any) in E to a string. The newline character |
946 | /// is used to separate error messages. |
947 | inline std::string toString(Error E) { |
948 | SmallVector<std::string, 2> Errors; |
949 | handleAllErrors(std::move(E), [&Errors](const ErrorInfoBase &EI) { |
950 | Errors.push_back(EI.message()); |
951 | }); |
952 | return join(Errors.begin(), Errors.end(), "\n"); |
953 | } |
954 | |
955 | /// Consume a Error without doing anything. This method should be used |
956 | /// only where an error can be considered a reasonable and expected return |
957 | /// value. |
958 | /// |
959 | /// Uses of this method are potentially indicative of design problems: If it's |
960 | /// legitimate to do nothing while processing an "error", the error-producer |
961 | /// might be more clearly refactored to return an Optional<T>. |
962 | inline void consumeError(Error Err) { |
963 | handleAllErrors(std::move(Err), [](const ErrorInfoBase &) {}); |
964 | } |
965 | |
966 | /// Helper for converting an Error to a bool. |
967 | /// |
968 | /// This method returns true if Err is in an error state, or false if it is |
969 | /// in a success state. Puts Err in a checked state in both cases (unlike |
970 | /// Error::operator bool(), which only does this for success states). |
971 | inline bool errorToBool(Error Err) { |
972 | bool IsError = static_cast<bool>(Err); |
973 | if (IsError) |
974 | consumeError(std::move(Err)); |
975 | return IsError; |
976 | } |
977 | |
978 | /// Helper for Errors used as out-parameters. |
979 | /// |
980 | /// This helper is for use with the Error-as-out-parameter idiom, where an error |
981 | /// is passed to a function or method by reference, rather than being returned. |
982 | /// In such cases it is helpful to set the checked bit on entry to the function |
983 | /// so that the error can be written to (unchecked Errors abort on assignment) |
984 | /// and clear the checked bit on exit so that clients cannot accidentally forget |
985 | /// to check the result. This helper performs these actions automatically using |
986 | /// RAII: |
987 | /// |
988 | /// @code{.cpp} |
989 | /// Result foo(Error &Err) { |
990 | /// ErrorAsOutParameter ErrAsOutParam(&Err); // 'Checked' flag set |
991 | /// // <body of foo> |
992 | /// // <- 'Checked' flag auto-cleared when ErrAsOutParam is destructed. |
993 | /// } |
994 | /// @endcode |
995 | /// |
996 | /// ErrorAsOutParameter takes an Error* rather than Error& so that it can be |
997 | /// used with optional Errors (Error pointers that are allowed to be null). If |
998 | /// ErrorAsOutParameter took an Error reference, an instance would have to be |
999 | /// created inside every condition that verified that Error was non-null. By |
1000 | /// taking an Error pointer we can just create one instance at the top of the |
1001 | /// function. |
1002 | class ErrorAsOutParameter { |
1003 | public: |
1004 | ErrorAsOutParameter(Error *Err) : Err(Err) { |
1005 | // Raise the checked bit if Err is success. |
1006 | if (Err) |
1007 | (void)!!*Err; |
1008 | } |
1009 | |
1010 | ~ErrorAsOutParameter() { |
1011 | // Clear the checked bit. |
1012 | if (Err && !*Err) |
1013 | *Err = Error::success(); |
1014 | } |
1015 | |
1016 | private: |
1017 | Error *Err; |
1018 | }; |
1019 | |
1020 | /// Helper for Expected<T>s used as out-parameters. |
1021 | /// |
1022 | /// See ErrorAsOutParameter. |
1023 | template <typename T> |
1024 | class ExpectedAsOutParameter { |
1025 | public: |
1026 | ExpectedAsOutParameter(Expected<T> *ValOrErr) |
1027 | : ValOrErr(ValOrErr) { |
1028 | if (ValOrErr) |
1029 | (void)!!*ValOrErr; |
1030 | } |
1031 | |
1032 | ~ExpectedAsOutParameter() { |
1033 | if (ValOrErr) |
1034 | ValOrErr->setUnchecked(); |
1035 | } |
1036 | |
1037 | private: |
1038 | Expected<T> *ValOrErr; |
1039 | }; |
1040 | |
1041 | /// This class wraps a std::error_code in a Error. |
1042 | /// |
1043 | /// This is useful if you're writing an interface that returns a Error |
1044 | /// (or Expected) and you want to call code that still returns |
1045 | /// std::error_codes. |
1046 | class ECError : public ErrorInfo<ECError> { |
1047 | friend Error errorCodeToError(std::error_code); |
1048 | |
1049 | public: |
1050 | void setErrorCode(std::error_code EC) { this->EC = EC; } |
1051 | std::error_code convertToErrorCode() const override { return EC; } |
1052 | void log(raw_ostream &OS) const override { OS << EC.message(); } |
1053 | |
1054 | // Used by ErrorInfo::classID. |
1055 | static char ID; |
1056 | |
1057 | protected: |
1058 | ECError() = default; |
1059 | ECError(std::error_code EC) : EC(EC) {} |
1060 | |
1061 | std::error_code EC; |
1062 | }; |
1063 | |
1064 | /// The value returned by this function can be returned from convertToErrorCode |
1065 | /// for Error values where no sensible translation to std::error_code exists. |
1066 | /// It should only be used in this situation, and should never be used where a |
1067 | /// sensible conversion to std::error_code is available, as attempts to convert |
1068 | /// to/from this error will result in a fatal error. (i.e. it is a programmatic |
1069 | ///error to try to convert such a value). |
1070 | std::error_code inconvertibleErrorCode(); |
1071 | |
1072 | /// Helper for converting an std::error_code to a Error. |
1073 | Error errorCodeToError(std::error_code EC); |
1074 | |
1075 | /// Helper for converting an ECError to a std::error_code. |
1076 | /// |
1077 | /// This method requires that Err be Error() or an ECError, otherwise it |
1078 | /// will trigger a call to abort(). |
1079 | std::error_code errorToErrorCode(Error Err); |
1080 | |
1081 | /// Convert an ErrorOr<T> to an Expected<T>. |
1082 | template <typename T> Expected<T> errorOrToExpected(ErrorOr<T> &&EO) { |
1083 | if (auto EC = EO.getError()) |
1084 | return errorCodeToError(EC); |
1085 | return std::move(*EO); |
1086 | } |
1087 | |
1088 | /// Convert an Expected<T> to an ErrorOr<T>. |
1089 | template <typename T> ErrorOr<T> expectedToErrorOr(Expected<T> &&E) { |
1090 | if (auto Err = E.takeError()) |
1091 | return errorToErrorCode(std::move(Err)); |
1092 | return std::move(*E); |
1093 | } |
1094 | |
1095 | /// This class wraps a string in an Error. |
1096 | /// |
1097 | /// StringError is useful in cases where the client is not expected to be able |
1098 | /// to consume the specific error message programmatically (for example, if the |
1099 | /// error message is to be presented to the user). |
1100 | class StringError : public ErrorInfo<StringError> { |
1101 | public: |
1102 | static char ID; |
1103 | |
1104 | StringError(const Twine &S, std::error_code EC); |
1105 | |
1106 | void log(raw_ostream &OS) const override; |
1107 | std::error_code convertToErrorCode() const override; |
1108 | |
1109 | const std::string &getMessage() const { return Msg; } |
1110 | |
1111 | private: |
1112 | std::string Msg; |
1113 | std::error_code EC; |
1114 | }; |
1115 | |
1116 | /// Helper for check-and-exit error handling. |
1117 | /// |
1118 | /// For tool use only. NOT FOR USE IN LIBRARY CODE. |
1119 | /// |
1120 | class ExitOnError { |
1121 | public: |
1122 | /// Create an error on exit helper. |
1123 | ExitOnError(std::string Banner = "", int DefaultErrorExitCode = 1) |
1124 | : Banner(std::move(Banner)), |
1125 | GetExitCode([=](const Error &) { return DefaultErrorExitCode; }) {} |
1126 | |
1127 | /// Set the banner string for any errors caught by operator(). |
1128 | void setBanner(std::string Banner) { this->Banner = std::move(Banner); } |
1129 | |
1130 | /// Set the exit-code mapper function. |
1131 | void setExitCodeMapper(std::function<int(const Error &)> GetExitCode) { |
1132 | this->GetExitCode = std::move(GetExitCode); |
1133 | } |
1134 | |
1135 | /// Check Err. If it's in a failure state log the error(s) and exit. |
1136 | void operator()(Error Err) const { checkError(std::move(Err)); } |
1137 | |
1138 | /// Check E. If it's in a success state then return the contained value. If |
1139 | /// it's in a failure state log the error(s) and exit. |
1140 | template <typename T> T operator()(Expected<T> &&E) const { |
1141 | checkError(E.takeError()); |
1142 | return std::move(*E); |
1143 | } |
1144 | |
1145 | /// Check E. If it's in a success state then return the contained reference. If |
1146 | /// it's in a failure state log the error(s) and exit. |
1147 | template <typename T> T& operator()(Expected<T&> &&E) const { |
1148 | checkError(E.takeError()); |
1149 | return *E; |
1150 | } |
1151 | |
1152 | private: |
1153 | void checkError(Error Err) const { |
1154 | if (Err) { |
1155 | int ExitCode = GetExitCode(Err); |
1156 | logAllUnhandledErrors(std::move(Err), errs(), Banner); |
1157 | exit(ExitCode); |
1158 | } |
1159 | } |
1160 | |
1161 | std::string Banner; |
1162 | std::function<int(const Error &)> GetExitCode; |
1163 | }; |
1164 | |
1165 | } // end namespace llvm |
1166 | |
1167 | #endif // LLVM_SUPPORT_ERROR_H |
1 | //===- InstrProf.h - Instrumented profiling format support ------*- C++ -*-===// |
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 | // |
10 | // Instrumentation-based profiling data is generated by instrumented |
11 | // binaries through library functions in compiler-rt, and read by the clang |
12 | // frontend to feed PGO. |
13 | // |
14 | //===----------------------------------------------------------------------===// |
15 | |
16 | #ifndef LLVM_PROFILEDATA_INSTRPROF_H |
17 | #define LLVM_PROFILEDATA_INSTRPROF_H |
18 | |
19 | #include "llvm/ADT/ArrayRef.h" |
20 | #include "llvm/ADT/STLExtras.h" |
21 | #include "llvm/ADT/StringRef.h" |
22 | #include "llvm/ADT/StringSet.h" |
23 | #include "llvm/ADT/Triple.h" |
24 | #include "llvm/IR/GlobalValue.h" |
25 | #include "llvm/IR/ProfileSummary.h" |
26 | #include "llvm/ProfileData/InstrProfData.inc" |
27 | #include "llvm/Support/Compiler.h" |
28 | #include "llvm/Support/Endian.h" |
29 | #include "llvm/Support/Error.h" |
30 | #include "llvm/Support/ErrorHandling.h" |
31 | #include "llvm/Support/Host.h" |
32 | #include "llvm/Support/MD5.h" |
33 | #include "llvm/Support/MathExtras.h" |
34 | #include "llvm/Support/raw_ostream.h" |
35 | #include <algorithm> |
36 | #include <cassert> |
37 | #include <cstddef> |
38 | #include <cstdint> |
39 | #include <cstring> |
40 | #include <list> |
41 | #include <memory> |
42 | #include <string> |
43 | #include <system_error> |
44 | #include <utility> |
45 | #include <vector> |
46 | |
47 | namespace llvm { |
48 | |
49 | class Function; |
50 | class GlobalVariable; |
51 | struct InstrProfRecord; |
52 | class InstrProfSymtab; |
53 | class Instruction; |
54 | class MDNode; |
55 | class Module; |
56 | |
57 | enum InstrProfSectKind { |
58 | #define INSTR_PROF_SECT_ENTRY(Kind, SectNameCommon, SectNameCoff, Prefix) Kind, |
59 | #include "llvm/ProfileData/InstrProfData.inc" |
60 | }; |
61 | |
62 | /// Return the name of the profile section corresponding to \p IPSK. |
63 | /// |
64 | /// The name of the section depends on the object format type \p OF. If |
65 | /// \p AddSegmentInfo is true, a segment prefix and additional linker hints may |
66 | /// be added to the section name (this is the default). |
67 | std::string getInstrProfSectionName(InstrProfSectKind IPSK, |
68 | Triple::ObjectFormatType OF, |
69 | bool AddSegmentInfo = true); |
70 | |
71 | /// Return the name profile runtime entry point to do value profiling |
72 | /// for a given site. |
73 | inline StringRef getInstrProfValueProfFuncName() { |
74 | return INSTR_PROF_VALUE_PROF_FUNC_STR"__llvm_profile_instrument_target"; |
75 | } |
76 | |
77 | /// Return the name profile runtime entry point to do value range profiling. |
78 | inline StringRef getInstrProfValueRangeProfFuncName() { |
79 | return INSTR_PROF_VALUE_RANGE_PROF_FUNC_STR"__llvm_profile_instrument_range"; |
80 | } |
81 | |
82 | /// Return the name prefix of variables containing instrumented function names. |
83 | inline StringRef getInstrProfNameVarPrefix() { return "__profn_"; } |
84 | |
85 | /// Return the name prefix of variables containing per-function control data. |
86 | inline StringRef getInstrProfDataVarPrefix() { return "__profd_"; } |
87 | |
88 | /// Return the name prefix of profile counter variables. |
89 | inline StringRef getInstrProfCountersVarPrefix() { return "__profc_"; } |
90 | |
91 | /// Return the name prefix of value profile variables. |
92 | inline StringRef getInstrProfValuesVarPrefix() { return "__profvp_"; } |
93 | |
94 | /// Return the name of value profile node array variables: |
95 | inline StringRef getInstrProfVNodesVarName() { return "__llvm_prf_vnodes"; } |
96 | |
97 | /// Return the name prefix of the COMDAT group for instrumentation variables |
98 | /// associated with a COMDAT function. |
99 | inline StringRef getInstrProfComdatPrefix() { return "__profv_"; } |
100 | |
101 | /// Return the name of the variable holding the strings (possibly compressed) |
102 | /// of all function's PGO names. |
103 | inline StringRef getInstrProfNamesVarName() { |
104 | return "__llvm_prf_nm"; |
105 | } |
106 | |
107 | /// Return the name of a covarage mapping variable (internal linkage) |
108 | /// for each instrumented source module. Such variables are allocated |
109 | /// in the __llvm_covmap section. |
110 | inline StringRef getCoverageMappingVarName() { |
111 | return "__llvm_coverage_mapping"; |
112 | } |
113 | |
114 | /// Return the name of the internal variable recording the array |
115 | /// of PGO name vars referenced by the coverage mapping. The owning |
116 | /// functions of those names are not emitted by FE (e.g, unused inline |
117 | /// functions.) |
118 | inline StringRef getCoverageUnusedNamesVarName() { |
119 | return "__llvm_coverage_names"; |
120 | } |
121 | |
122 | /// Return the name of function that registers all the per-function control |
123 | /// data at program startup time by calling __llvm_register_function. This |
124 | /// function has internal linkage and is called by __llvm_profile_init |
125 | /// runtime method. This function is not generated for these platforms: |
126 | /// Darwin, Linux, and FreeBSD. |
127 | inline StringRef getInstrProfRegFuncsName() { |
128 | return "__llvm_profile_register_functions"; |
129 | } |
130 | |
131 | /// Return the name of the runtime interface that registers per-function control |
132 | /// data for one instrumented function. |
133 | inline StringRef getInstrProfRegFuncName() { |
134 | return "__llvm_profile_register_function"; |
135 | } |
136 | |
137 | /// Return the name of the runtime interface that registers the PGO name strings. |
138 | inline StringRef getInstrProfNamesRegFuncName() { |
139 | return "__llvm_profile_register_names_function"; |
140 | } |
141 | |
142 | /// Return the name of the runtime initialization method that is generated by |
143 | /// the compiler. The function calls __llvm_profile_register_functions and |
144 | /// __llvm_profile_override_default_filename functions if needed. This function |
145 | /// has internal linkage and invoked at startup time via init_array. |
146 | inline StringRef getInstrProfInitFuncName() { return "__llvm_profile_init"; } |
147 | |
148 | /// Return the name of the hook variable defined in profile runtime library. |
149 | /// A reference to the variable causes the linker to link in the runtime |
150 | /// initialization module (which defines the hook variable). |
151 | inline StringRef getInstrProfRuntimeHookVarName() { |
152 | return INSTR_PROF_QUOTE(INSTR_PROF_PROFILE_RUNTIME_VAR)"__llvm_profile_runtime"; |
153 | } |
154 | |
155 | /// Return the name of the compiler generated function that references the |
156 | /// runtime hook variable. The function is a weak global. |
157 | inline StringRef getInstrProfRuntimeHookVarUseFuncName() { |
158 | return "__llvm_profile_runtime_user"; |
159 | } |
160 | |
161 | /// Return the marker used to separate PGO names during serialization. |
162 | inline StringRef getInstrProfNameSeparator() { return "\01"; } |
163 | |
164 | /// Return the modified name for function \c F suitable to be |
165 | /// used the key for profile lookup. Variable \c InLTO indicates if this |
166 | /// is called in LTO optimization passes. |
167 | std::string getPGOFuncName(const Function &F, bool InLTO = false, |
168 | uint64_t Version = INSTR_PROF_INDEX_VERSION5); |
169 | |
170 | /// Return the modified name for a function suitable to be |
171 | /// used the key for profile lookup. The function's original |
172 | /// name is \c RawFuncName and has linkage of type \c Linkage. |
173 | /// The function is defined in module \c FileName. |
174 | std::string getPGOFuncName(StringRef RawFuncName, |
175 | GlobalValue::LinkageTypes Linkage, |
176 | StringRef FileName, |
177 | uint64_t Version = INSTR_PROF_INDEX_VERSION5); |
178 | |
179 | /// Return the name of the global variable used to store a function |
180 | /// name in PGO instrumentation. \c FuncName is the name of the function |
181 | /// returned by the \c getPGOFuncName call. |
182 | std::string getPGOFuncNameVarName(StringRef FuncName, |
183 | GlobalValue::LinkageTypes Linkage); |
184 | |
185 | /// Create and return the global variable for function name used in PGO |
186 | /// instrumentation. \c FuncName is the name of the function returned |
187 | /// by \c getPGOFuncName call. |
188 | GlobalVariable *createPGOFuncNameVar(Function &F, StringRef PGOFuncName); |
189 | |
190 | /// Create and return the global variable for function name used in PGO |
191 | /// instrumentation. /// \c FuncName is the name of the function |
192 | /// returned by \c getPGOFuncName call, \c M is the owning module, |
193 | /// and \c Linkage is the linkage of the instrumented function. |
194 | GlobalVariable *createPGOFuncNameVar(Module &M, |
195 | GlobalValue::LinkageTypes Linkage, |
196 | StringRef PGOFuncName); |
197 | |
198 | /// Return the initializer in string of the PGO name var \c NameVar. |
199 | StringRef getPGOFuncNameVarInitializer(GlobalVariable *NameVar); |
200 | |
201 | /// Given a PGO function name, remove the filename prefix and return |
202 | /// the original (static) function name. |
203 | StringRef getFuncNameWithoutPrefix(StringRef PGOFuncName, |
204 | StringRef FileName = "<unknown>"); |
205 | |
206 | /// Given a vector of strings (function PGO names) \c NameStrs, the |
207 | /// method generates a combined string \c Result thatis ready to be |
208 | /// serialized. The \c Result string is comprised of three fields: |
209 | /// The first field is the legnth of the uncompressed strings, and the |
210 | /// the second field is the length of the zlib-compressed string. |
211 | /// Both fields are encoded in ULEB128. If \c doCompress is false, the |
212 | /// third field is the uncompressed strings; otherwise it is the |
213 | /// compressed string. When the string compression is off, the |
214 | /// second field will have value zero. |
215 | Error collectPGOFuncNameStrings(ArrayRef<std::string> NameStrs, |
216 | bool doCompression, std::string &Result); |
217 | |
218 | /// Produce \c Result string with the same format described above. The input |
219 | /// is vector of PGO function name variables that are referenced. |
220 | Error collectPGOFuncNameStrings(ArrayRef<GlobalVariable *> NameVars, |
221 | std::string &Result, bool doCompression = true); |
222 | |
223 | /// \c NameStrings is a string composed of one of more sub-strings encoded in |
224 | /// the format described above. The substrings are separated by 0 or more zero |
225 | /// bytes. This method decodes the string and populates the \c Symtab. |
226 | Error readPGOFuncNameStrings(StringRef NameStrings, InstrProfSymtab &Symtab); |
227 | |
228 | /// Check if INSTR_PROF_RAW_VERSION_VAR is defined. This global is only being |
229 | /// set in IR PGO compilation. |
230 | bool isIRPGOFlagSet(const Module *M); |
231 | |
232 | /// Check if we can safely rename this Comdat function. Instances of the same |
233 | /// comdat function may have different control flows thus can not share the |
234 | /// same counter variable. |
235 | bool canRenameComdatFunc(const Function &F, bool CheckAddressTaken = false); |
236 | |
237 | enum InstrProfValueKind : uint32_t { |
238 | #define VALUE_PROF_KIND(Enumerator, Value) Enumerator = Value, |
239 | #include "llvm/ProfileData/InstrProfData.inc" |
240 | }; |
241 | |
242 | /// Get the value profile data for value site \p SiteIdx from \p InstrProfR |
243 | /// and annotate the instruction \p Inst with the value profile meta data. |
244 | /// Annotate up to \p MaxMDCount (default 3) number of records per value site. |
245 | void annotateValueSite(Module &M, Instruction &Inst, |
246 | const InstrProfRecord &InstrProfR, |
247 | InstrProfValueKind ValueKind, uint32_t SiteIndx, |
248 | uint32_t MaxMDCount = 3); |
249 | |
250 | /// Same as the above interface but using an ArrayRef, as well as \p Sum. |
251 | void annotateValueSite(Module &M, Instruction &Inst, |
252 | ArrayRef<InstrProfValueData> VDs, uint64_t Sum, |
253 | InstrProfValueKind ValueKind, uint32_t MaxMDCount); |
254 | |
255 | /// Extract the value profile data from \p Inst which is annotated with |
256 | /// value profile meta data. Return false if there is no value data annotated, |
257 | /// otherwise return true. |
258 | bool getValueProfDataFromInst(const Instruction &Inst, |
259 | InstrProfValueKind ValueKind, |
260 | uint32_t MaxNumValueData, |
261 | InstrProfValueData ValueData[], |
262 | uint32_t &ActualNumValueData, uint64_t &TotalC); |
263 | |
264 | inline StringRef getPGOFuncNameMetadataName() { return "PGOFuncName"; } |
265 | |
266 | /// Return the PGOFuncName meta data associated with a function. |
267 | MDNode *getPGOFuncNameMetadata(const Function &F); |
268 | |
269 | /// Create the PGOFuncName meta data if PGOFuncName is different from |
270 | /// function's raw name. This should only apply to internal linkage functions |
271 | /// declared by users only. |
272 | void createPGOFuncNameMetadata(Function &F, StringRef PGOFuncName); |
273 | |
274 | /// Check if we can use Comdat for profile variables. This will eliminate |
275 | /// the duplicated profile variables for Comdat functions. |
276 | bool needsComdatForCounter(const Function &F, const Module &M); |
277 | |
278 | const std::error_category &instrprof_category(); |
279 | |
280 | enum class instrprof_error { |
281 | success = 0, |
282 | eof, |
283 | unrecognized_format, |
284 | bad_magic, |
285 | bad_header, |
286 | unsupported_version, |
287 | unsupported_hash_type, |
288 | too_large, |
289 | truncated, |
290 | malformed, |
291 | unknown_function, |
292 | hash_mismatch, |
293 | count_mismatch, |
294 | counter_overflow, |
295 | value_site_count_mismatch, |
296 | compress_failed, |
297 | uncompress_failed, |
298 | empty_raw_profile, |
299 | zlib_unavailable |
300 | }; |
301 | |
302 | inline std::error_code make_error_code(instrprof_error E) { |
303 | return std::error_code(static_cast<int>(E), instrprof_category()); |
304 | } |
305 | |
306 | class InstrProfError : public ErrorInfo<InstrProfError> { |
307 | public: |
308 | InstrProfError(instrprof_error Err) : Err(Err) { |
309 | assert(Err != instrprof_error::success && "Not an error")(static_cast <bool> (Err != instrprof_error::success && "Not an error") ? void (0) : __assert_fail ("Err != instrprof_error::success && \"Not an error\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ProfileData/InstrProf.h" , 309, __extension__ __PRETTY_FUNCTION__)); |
310 | } |
311 | |
312 | std::string message() const override; |
313 | |
314 | void log(raw_ostream &OS) const override { OS << message(); } |
315 | |
316 | std::error_code convertToErrorCode() const override { |
317 | return make_error_code(Err); |
318 | } |
319 | |
320 | instrprof_error get() const { return Err; } |
321 | |
322 | /// Consume an Error and return the raw enum value contained within it. The |
323 | /// Error must either be a success value, or contain a single InstrProfError. |
324 | static instrprof_error take(Error E) { |
325 | auto Err = instrprof_error::success; |
326 | handleAllErrors(std::move(E), [&Err](const InstrProfError &IPE) { |
327 | assert(Err == instrprof_error::success && "Multiple errors encountered")(static_cast <bool> (Err == instrprof_error::success && "Multiple errors encountered") ? void (0) : __assert_fail ("Err == instrprof_error::success && \"Multiple errors encountered\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ProfileData/InstrProf.h" , 327, __extension__ __PRETTY_FUNCTION__)); |
328 | Err = IPE.get(); |
329 | }); |
330 | return Err; |
331 | } |
332 | |
333 | static char ID; |
334 | |
335 | private: |
336 | instrprof_error Err; |
337 | }; |
338 | |
339 | class SoftInstrProfErrors { |
340 | /// Count the number of soft instrprof_errors encountered and keep track of |
341 | /// the first such error for reporting purposes. |
342 | |
343 | /// The first soft error encountered. |
344 | instrprof_error FirstError = instrprof_error::success; |
345 | |
346 | /// The number of hash mismatches. |
347 | unsigned NumHashMismatches = 0; |
348 | |
349 | /// The number of count mismatches. |
350 | unsigned NumCountMismatches = 0; |
351 | |
352 | /// The number of counter overflows. |
353 | unsigned NumCounterOverflows = 0; |
354 | |
355 | /// The number of value site count mismatches. |
356 | unsigned NumValueSiteCountMismatches = 0; |
357 | |
358 | public: |
359 | SoftInstrProfErrors() = default; |
360 | |
361 | ~SoftInstrProfErrors() { |
362 | assert(FirstError == instrprof_error::success &&(static_cast <bool> (FirstError == instrprof_error::success && "Unchecked soft error encountered") ? void (0) : __assert_fail ("FirstError == instrprof_error::success && \"Unchecked soft error encountered\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ProfileData/InstrProf.h" , 363, __extension__ __PRETTY_FUNCTION__)) |
363 | "Unchecked soft error encountered")(static_cast <bool> (FirstError == instrprof_error::success && "Unchecked soft error encountered") ? void (0) : __assert_fail ("FirstError == instrprof_error::success && \"Unchecked soft error encountered\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ProfileData/InstrProf.h" , 363, __extension__ __PRETTY_FUNCTION__)); |
364 | } |
365 | |
366 | /// Track a soft error (\p IE) and increment its associated counter. |
367 | void addError(instrprof_error IE); |
368 | |
369 | /// Get the number of hash mismatches. |
370 | unsigned getNumHashMismatches() const { return NumHashMismatches; } |
371 | |
372 | /// Get the number of count mismatches. |
373 | unsigned getNumCountMismatches() const { return NumCountMismatches; } |
374 | |
375 | /// Get the number of counter overflows. |
376 | unsigned getNumCounterOverflows() const { return NumCounterOverflows; } |
377 | |
378 | /// Get the number of value site count mismatches. |
379 | unsigned getNumValueSiteCountMismatches() const { |
380 | return NumValueSiteCountMismatches; |
381 | } |
382 | |
383 | /// Return the first encountered error and reset FirstError to a success |
384 | /// value. |
385 | Error takeError() { |
386 | if (FirstError == instrprof_error::success) |
387 | return Error::success(); |
388 | auto E = make_error<InstrProfError>(FirstError); |
389 | FirstError = instrprof_error::success; |
390 | return E; |
391 | } |
392 | }; |
393 | |
394 | namespace object { |
395 | |
396 | class SectionRef; |
397 | |
398 | } // end namespace object |
399 | |
400 | namespace IndexedInstrProf { |
401 | |
402 | uint64_t ComputeHash(StringRef K); |
403 | |
404 | } // end namespace IndexedInstrProf |
405 | |
406 | /// A symbol table used for function PGO name look-up with keys |
407 | /// (such as pointers, md5hash values) to the function. A function's |
408 | /// PGO name or name's md5hash are used in retrieving the profile |
409 | /// data of the function. See \c getPGOFuncName() method for details |
410 | /// on how PGO name is formed. |
411 | class InstrProfSymtab { |
412 | public: |
413 | using AddrHashMap = std::vector<std::pair<uint64_t, uint64_t>>; |
414 | |
415 | private: |
416 | StringRef Data; |
417 | uint64_t Address = 0; |
418 | // Unique name strings. |
419 | StringSet<> NameTab; |
420 | // A map from MD5 keys to function name strings. |
421 | std::vector<std::pair<uint64_t, StringRef>> MD5NameMap; |
422 | // A map from MD5 keys to function define. We only populate this map |
423 | // when build the Symtab from a Module. |
424 | std::vector<std::pair<uint64_t, Function *>> MD5FuncMap; |
425 | // A map from function runtime address to function name MD5 hash. |
426 | // This map is only populated and used by raw instr profile reader. |
427 | AddrHashMap AddrToMD5Map; |
428 | bool Sorted = false; |
429 | |
430 | static StringRef getExternalSymbol() { |
431 | return "** External Symbol **"; |
432 | } |
433 | |
434 | // If the symtab is created by a series of calls to \c addFuncName, \c |
435 | // finalizeSymtab needs to be called before looking up function names. |
436 | // This is required because the underlying map is a vector (for space |
437 | // efficiency) which needs to be sorted. |
438 | inline void finalizeSymtab(); |
439 | |
440 | public: |
441 | InstrProfSymtab() = default; |
442 | |
443 | /// Create InstrProfSymtab from an object file section which |
444 | /// contains function PGO names. When section may contain raw |
445 | /// string data or string data in compressed form. This method |
446 | /// only initialize the symtab with reference to the data and |
447 | /// the section base address. The decompression will be delayed |
448 | /// until before it is used. See also \c create(StringRef) method. |
449 | Error create(object::SectionRef &Section); |
450 | |
451 | /// This interface is used by reader of CoverageMapping test |
452 | /// format. |
453 | inline Error create(StringRef D, uint64_t BaseAddr); |
454 | |
455 | /// \c NameStrings is a string composed of one of more sub-strings |
456 | /// encoded in the format described in \c collectPGOFuncNameStrings. |
457 | /// This method is a wrapper to \c readPGOFuncNameStrings method. |
458 | inline Error create(StringRef NameStrings); |
459 | |
460 | /// A wrapper interface to populate the PGO symtab with functions |
461 | /// decls from module \c M. This interface is used by transformation |
462 | /// passes such as indirect function call promotion. Variable \c InLTO |
463 | /// indicates if this is called from LTO optimization passes. |
464 | Error create(Module &M, bool InLTO = false); |
465 | |
466 | /// Create InstrProfSymtab from a set of names iteratable from |
467 | /// \p IterRange. This interface is used by IndexedProfReader. |
468 | template <typename NameIterRange> Error create(const NameIterRange &IterRange); |
469 | |
470 | /// Update the symtab by adding \p FuncName to the table. This interface |
471 | /// is used by the raw and text profile readers. |
472 | Error addFuncName(StringRef FuncName) { |
473 | if (FuncName.empty()) |
474 | return make_error<InstrProfError>(instrprof_error::malformed); |
475 | auto Ins = NameTab.insert(FuncName); |
476 | if (Ins.second) { |
477 | MD5NameMap.push_back(std::make_pair( |
478 | IndexedInstrProf::ComputeHash(FuncName), Ins.first->getKey())); |
479 | Sorted = false; |
480 | } |
481 | return Error::success(); |
482 | } |
483 | |
484 | /// Map a function address to its name's MD5 hash. This interface |
485 | /// is only used by the raw profiler reader. |
486 | void mapAddress(uint64_t Addr, uint64_t MD5Val) { |
487 | AddrToMD5Map.push_back(std::make_pair(Addr, MD5Val)); |
488 | } |
489 | |
490 | /// Return a function's hash, or 0, if the function isn't in this SymTab. |
491 | uint64_t getFunctionHashFromAddress(uint64_t Address); |
492 | |
493 | /// Return function's PGO name from the function name's symbol |
494 | /// address in the object file. If an error occurs, return |
495 | /// an empty string. |
496 | StringRef getFuncName(uint64_t FuncNameAddress, size_t NameSize); |
497 | |
498 | /// Return function's PGO name from the name's md5 hash value. |
499 | /// If not found, return an empty string. |
500 | inline StringRef getFuncName(uint64_t FuncMD5Hash); |
501 | |
502 | /// Just like getFuncName, except that it will return a non-empty StringRef |
503 | /// if the function is external to this symbol table. All such cases |
504 | /// will be represented using the same StringRef value. |
505 | inline StringRef getFuncNameOrExternalSymbol(uint64_t FuncMD5Hash); |
506 | |
507 | /// True if Symbol is the value used to represent external symbols. |
508 | static bool isExternalSymbol(const StringRef &Symbol) { |
509 | return Symbol == InstrProfSymtab::getExternalSymbol(); |
510 | } |
511 | |
512 | /// Return function from the name's md5 hash. Return nullptr if not found. |
513 | inline Function *getFunction(uint64_t FuncMD5Hash); |
514 | |
515 | /// Return the function's original assembly name by stripping off |
516 | /// the prefix attached (to symbols with priviate linkage). For |
517 | /// global functions, it returns the same string as getFuncName. |
518 | inline StringRef getOrigFuncName(uint64_t FuncMD5Hash); |
519 | |
520 | /// Return the name section data. |
521 | inline StringRef getNameData() const { return Data; } |
522 | }; |
523 | |
524 | Error InstrProfSymtab::create(StringRef D, uint64_t BaseAddr) { |
525 | Data = D; |
526 | Address = BaseAddr; |
527 | return Error::success(); |
528 | } |
529 | |
530 | Error InstrProfSymtab::create(StringRef NameStrings) { |
531 | return readPGOFuncNameStrings(NameStrings, *this); |
532 | } |
533 | |
534 | template <typename NameIterRange> |
535 | Error InstrProfSymtab::create(const NameIterRange &IterRange) { |
536 | for (auto Name : IterRange) |
537 | if (Error E = addFuncName(Name)) |
538 | return E; |
539 | |
540 | finalizeSymtab(); |
541 | return Error::success(); |
542 | } |
543 | |
544 | void InstrProfSymtab::finalizeSymtab() { |
545 | if (Sorted) |
546 | return; |
547 | llvm::sort(MD5NameMap.begin(), MD5NameMap.end(), less_first()); |
548 | llvm::sort(MD5FuncMap.begin(), MD5FuncMap.end(), less_first()); |
549 | llvm::sort(AddrToMD5Map.begin(), AddrToMD5Map.end(), less_first()); |
550 | AddrToMD5Map.erase(std::unique(AddrToMD5Map.begin(), AddrToMD5Map.end()), |
551 | AddrToMD5Map.end()); |
552 | Sorted = true; |
553 | } |
554 | |
555 | StringRef InstrProfSymtab::getFuncNameOrExternalSymbol(uint64_t FuncMD5Hash) { |
556 | StringRef ret = getFuncName(FuncMD5Hash); |
557 | if (ret.empty()) |
558 | return InstrProfSymtab::getExternalSymbol(); |
559 | return ret; |
560 | } |
561 | |
562 | StringRef InstrProfSymtab::getFuncName(uint64_t FuncMD5Hash) { |
563 | finalizeSymtab(); |
564 | auto Result = |
565 | std::lower_bound(MD5NameMap.begin(), MD5NameMap.end(), FuncMD5Hash, |
566 | [](const std::pair<uint64_t, std::string> &LHS, |
567 | uint64_t RHS) { return LHS.first < RHS; }); |
568 | if (Result != MD5NameMap.end() && Result->first == FuncMD5Hash) |
569 | return Result->second; |
570 | return StringRef(); |
571 | } |
572 | |
573 | Function* InstrProfSymtab::getFunction(uint64_t FuncMD5Hash) { |
574 | finalizeSymtab(); |
575 | auto Result = |
576 | std::lower_bound(MD5FuncMap.begin(), MD5FuncMap.end(), FuncMD5Hash, |
577 | [](const std::pair<uint64_t, Function*> &LHS, |
578 | uint64_t RHS) { return LHS.first < RHS; }); |
579 | if (Result != MD5FuncMap.end() && Result->first == FuncMD5Hash) |
580 | return Result->second; |
581 | return nullptr; |
582 | } |
583 | |
584 | // See also getPGOFuncName implementation. These two need to be |
585 | // matched. |
586 | StringRef InstrProfSymtab::getOrigFuncName(uint64_t FuncMD5Hash) { |
587 | StringRef PGOName = getFuncName(FuncMD5Hash); |
588 | size_t S = PGOName.find_first_of(':'); |
589 | if (S == StringRef::npos) |
590 | return PGOName; |
591 | return PGOName.drop_front(S + 1); |
592 | } |
593 | |
594 | struct InstrProfValueSiteRecord { |
595 | /// Value profiling data pairs at a given value site. |
596 | std::list<InstrProfValueData> ValueData; |
597 | |
598 | InstrProfValueSiteRecord() { ValueData.clear(); } |
599 | template <class InputIterator> |
600 | InstrProfValueSiteRecord(InputIterator F, InputIterator L) |
601 | : ValueData(F, L) {} |
602 | |
603 | /// Sort ValueData ascending by Value |
604 | void sortByTargetValues() { |
605 | ValueData.sort( |
606 | [](const InstrProfValueData &left, const InstrProfValueData &right) { |
607 | return left.Value < right.Value; |
608 | }); |
609 | } |
610 | /// Sort ValueData Descending by Count |
611 | inline void sortByCount(); |
612 | |
613 | /// Merge data from another InstrProfValueSiteRecord |
614 | /// Optionally scale merged counts by \p Weight. |
615 | void merge(InstrProfValueSiteRecord &Input, uint64_t Weight, |
616 | function_ref<void(instrprof_error)> Warn); |
617 | /// Scale up value profile data counts. |
618 | void scale(uint64_t Weight, function_ref<void(instrprof_error)> Warn); |
619 | }; |
620 | |
621 | /// Profiling information for a single function. |
622 | struct InstrProfRecord { |
623 | std::vector<uint64_t> Counts; |
624 | |
625 | InstrProfRecord() = default; |
626 | InstrProfRecord(std::vector<uint64_t> Counts) : Counts(std::move(Counts)) {} |
627 | InstrProfRecord(InstrProfRecord &&) = default; |
628 | InstrProfRecord(const InstrProfRecord &RHS) |
629 | : Counts(RHS.Counts), |
630 | ValueData(RHS.ValueData |
631 | ? llvm::make_unique<ValueProfData>(*RHS.ValueData) |
632 | : nullptr) {} |
633 | InstrProfRecord &operator=(InstrProfRecord &&) = default; |
634 | InstrProfRecord &operator=(const InstrProfRecord &RHS) { |
635 | Counts = RHS.Counts; |
636 | if (!RHS.ValueData) { |
637 | ValueData = nullptr; |
638 | return *this; |
639 | } |
640 | if (!ValueData) |
641 | ValueData = llvm::make_unique<ValueProfData>(*RHS.ValueData); |
642 | else |
643 | *ValueData = *RHS.ValueData; |
644 | return *this; |
645 | } |
646 | |
647 | /// Return the number of value profile kinds with non-zero number |
648 | /// of profile sites. |
649 | inline uint32_t getNumValueKinds() const; |
650 | /// Return the number of instrumented sites for ValueKind. |
651 | inline uint32_t getNumValueSites(uint32_t ValueKind) const; |
652 | |
653 | /// Return the total number of ValueData for ValueKind. |
654 | inline uint32_t getNumValueData(uint32_t ValueKind) const; |
655 | |
656 | /// Return the number of value data collected for ValueKind at profiling |
657 | /// site: Site. |
658 | inline uint32_t getNumValueDataForSite(uint32_t ValueKind, |
659 | uint32_t Site) const; |
660 | |
661 | /// Return the array of profiled values at \p Site. If \p TotalC |
662 | /// is not null, the total count of all target values at this site |
663 | /// will be stored in \c *TotalC. |
664 | inline std::unique_ptr<InstrProfValueData[]> |
665 | getValueForSite(uint32_t ValueKind, uint32_t Site, |
666 | uint64_t *TotalC = nullptr) const; |
667 | |
668 | /// Get the target value/counts of kind \p ValueKind collected at site |
669 | /// \p Site and store the result in array \p Dest. Return the total |
670 | /// counts of all target values at this site. |
671 | inline uint64_t getValueForSite(InstrProfValueData Dest[], uint32_t ValueKind, |
672 | uint32_t Site) const; |
673 | |
674 | /// Reserve space for NumValueSites sites. |
675 | inline void reserveSites(uint32_t ValueKind, uint32_t NumValueSites); |
676 | |
677 | /// Add ValueData for ValueKind at value Site. |
678 | void addValueData(uint32_t ValueKind, uint32_t Site, |
679 | InstrProfValueData *VData, uint32_t N, |
680 | InstrProfSymtab *SymTab); |
681 | |
682 | /// Merge the counts in \p Other into this one. |
683 | /// Optionally scale merged counts by \p Weight. |
684 | void merge(InstrProfRecord &Other, uint64_t Weight, |
685 | function_ref<void(instrprof_error)> Warn); |
686 | |
687 | /// Scale up profile counts (including value profile data) by |
688 | /// \p Weight. |
689 | void scale(uint64_t Weight, function_ref<void(instrprof_error)> Warn); |
690 | |
691 | /// Sort value profile data (per site) by count. |
692 | void sortValueData() { |
693 | for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) |
694 | for (auto &SR : getValueSitesForKind(Kind)) |
695 | SR.sortByCount(); |
696 | } |
697 | |
698 | /// Clear value data entries and edge counters. |
699 | void Clear() { |
700 | Counts.clear(); |
701 | clearValueData(); |
702 | } |
703 | |
704 | /// Clear value data entries |
705 | void clearValueData() { ValueData = nullptr; } |
706 | |
707 | private: |
708 | struct ValueProfData { |
709 | std::vector<InstrProfValueSiteRecord> IndirectCallSites; |
710 | std::vector<InstrProfValueSiteRecord> MemOPSizes; |
711 | }; |
712 | std::unique_ptr<ValueProfData> ValueData; |
713 | |
714 | MutableArrayRef<InstrProfValueSiteRecord> |
715 | getValueSitesForKind(uint32_t ValueKind) { |
716 | // Cast to /add/ const (should be an implicit_cast, ideally, if that's ever |
717 | // implemented in LLVM) to call the const overload of this function, then |
718 | // cast away the constness from the result. |
719 | auto AR = const_cast<const InstrProfRecord *>(this)->getValueSitesForKind( |
720 | ValueKind); |
721 | return makeMutableArrayRef( |
722 | const_cast<InstrProfValueSiteRecord *>(AR.data()), AR.size()); |
723 | } |
724 | ArrayRef<InstrProfValueSiteRecord> |
725 | getValueSitesForKind(uint32_t ValueKind) const { |
726 | if (!ValueData) |
727 | return None; |
728 | switch (ValueKind) { |
729 | case IPVK_IndirectCallTarget: |
730 | return ValueData->IndirectCallSites; |
731 | case IPVK_MemOPSize: |
732 | return ValueData->MemOPSizes; |
733 | default: |
734 | llvm_unreachable("Unknown value kind!")::llvm::llvm_unreachable_internal("Unknown value kind!", "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ProfileData/InstrProf.h" , 734); |
735 | } |
736 | } |
737 | |
738 | std::vector<InstrProfValueSiteRecord> & |
739 | getOrCreateValueSitesForKind(uint32_t ValueKind) { |
740 | if (!ValueData) |
741 | ValueData = llvm::make_unique<ValueProfData>(); |
742 | switch (ValueKind) { |
743 | case IPVK_IndirectCallTarget: |
744 | return ValueData->IndirectCallSites; |
745 | case IPVK_MemOPSize: |
746 | return ValueData->MemOPSizes; |
747 | default: |
748 | llvm_unreachable("Unknown value kind!")::llvm::llvm_unreachable_internal("Unknown value kind!", "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ProfileData/InstrProf.h" , 748); |
749 | } |
750 | } |
751 | |
752 | // Map indirect call target name hash to name string. |
753 | uint64_t remapValue(uint64_t Value, uint32_t ValueKind, |
754 | InstrProfSymtab *SymTab); |
755 | |
756 | // Merge Value Profile data from Src record to this record for ValueKind. |
757 | // Scale merged value counts by \p Weight. |
758 | void mergeValueProfData(uint32_t ValkeKind, InstrProfRecord &Src, |
759 | uint64_t Weight, |
760 | function_ref<void(instrprof_error)> Warn); |
761 | |
762 | // Scale up value profile data count. |
763 | void scaleValueProfData(uint32_t ValueKind, uint64_t Weight, |
764 | function_ref<void(instrprof_error)> Warn); |
765 | }; |
766 | |
767 | struct NamedInstrProfRecord : InstrProfRecord { |
768 | StringRef Name; |
769 | uint64_t Hash; |
770 | |
771 | NamedInstrProfRecord() = default; |
772 | NamedInstrProfRecord(StringRef Name, uint64_t Hash, |
773 | std::vector<uint64_t> Counts) |
774 | : InstrProfRecord(std::move(Counts)), Name(Name), Hash(Hash) {} |
775 | }; |
776 | |
777 | uint32_t InstrProfRecord::getNumValueKinds() const { |
778 | uint32_t NumValueKinds = 0; |
779 | for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) |
780 | NumValueKinds += !(getValueSitesForKind(Kind).empty()); |
781 | return NumValueKinds; |
782 | } |
783 | |
784 | uint32_t InstrProfRecord::getNumValueData(uint32_t ValueKind) const { |
785 | uint32_t N = 0; |
786 | for (auto &SR : getValueSitesForKind(ValueKind)) |
787 | N += SR.ValueData.size(); |
788 | return N; |
789 | } |
790 | |
791 | uint32_t InstrProfRecord::getNumValueSites(uint32_t ValueKind) const { |
792 | return getValueSitesForKind(ValueKind).size(); |
793 | } |
794 | |
795 | uint32_t InstrProfRecord::getNumValueDataForSite(uint32_t ValueKind, |
796 | uint32_t Site) const { |
797 | return getValueSitesForKind(ValueKind)[Site].ValueData.size(); |
798 | } |
799 | |
800 | std::unique_ptr<InstrProfValueData[]> |
801 | InstrProfRecord::getValueForSite(uint32_t ValueKind, uint32_t Site, |
802 | uint64_t *TotalC) const { |
803 | uint64_t Dummy; |
804 | uint64_t &TotalCount = (TotalC == nullptr ? Dummy : *TotalC); |
805 | uint32_t N = getNumValueDataForSite(ValueKind, Site); |
806 | if (N == 0) { |
807 | TotalCount = 0; |
808 | return std::unique_ptr<InstrProfValueData[]>(nullptr); |
809 | } |
810 | |
811 | auto VD = llvm::make_unique<InstrProfValueData[]>(N); |
812 | TotalCount = getValueForSite(VD.get(), ValueKind, Site); |
813 | |
814 | return VD; |
815 | } |
816 | |
817 | uint64_t InstrProfRecord::getValueForSite(InstrProfValueData Dest[], |
818 | uint32_t ValueKind, |
819 | uint32_t Site) const { |
820 | uint32_t I = 0; |
821 | uint64_t TotalCount = 0; |
822 | for (auto V : getValueSitesForKind(ValueKind)[Site].ValueData) { |
823 | Dest[I].Value = V.Value; |
824 | Dest[I].Count = V.Count; |
825 | TotalCount = SaturatingAdd(TotalCount, V.Count); |
826 | I++; |
827 | } |
828 | return TotalCount; |
829 | } |
830 | |
831 | void InstrProfRecord::reserveSites(uint32_t ValueKind, uint32_t NumValueSites) { |
832 | if (!NumValueSites) |
833 | return; |
834 | getOrCreateValueSitesForKind(ValueKind).reserve(NumValueSites); |
835 | } |
836 | |
837 | inline support::endianness getHostEndianness() { |
838 | return sys::IsLittleEndianHost ? support::little : support::big; |
839 | } |
840 | |
841 | // Include definitions for value profile data |
842 | #define INSTR_PROF_VALUE_PROF_DATA |
843 | #include "llvm/ProfileData/InstrProfData.inc" |
844 | |
845 | void InstrProfValueSiteRecord::sortByCount() { |
846 | ValueData.sort( |
847 | [](const InstrProfValueData &left, const InstrProfValueData &right) { |
848 | return left.Count > right.Count; |
849 | }); |
850 | // Now truncate |
851 | size_t max_s = INSTR_PROF_MAX_NUM_VAL_PER_SITE255; |
852 | if (ValueData.size() > max_s) |
853 | ValueData.resize(max_s); |
854 | } |
855 | |
856 | namespace IndexedInstrProf { |
857 | |
858 | enum class HashT : uint32_t { |
859 | MD5, |
860 | Last = MD5 |
861 | }; |
862 | |
863 | inline uint64_t ComputeHash(HashT Type, StringRef K) { |
864 | switch (Type) { |
865 | case HashT::MD5: |
866 | return MD5Hash(K); |
867 | } |
868 | llvm_unreachable("Unhandled hash type")::llvm::llvm_unreachable_internal("Unhandled hash type", "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ProfileData/InstrProf.h" , 868); |
869 | } |
870 | |
871 | const uint64_t Magic = 0x8169666f72706cff; // "\xfflprofi\x81" |
872 | |
873 | enum ProfVersion { |
874 | // Version 1 is the first version. In this version, the value of |
875 | // a key/value pair can only include profile data of a single function. |
876 | // Due to this restriction, the number of block counters for a given |
877 | // function is not recorded but derived from the length of the value. |
878 | Version1 = 1, |
879 | // The version 2 format supports recording profile data of multiple |
880 | // functions which share the same key in one value field. To support this, |
881 | // the number block counters is recorded as an uint64_t field right after the |
882 | // function structural hash. |
883 | Version2 = 2, |
884 | // Version 3 supports value profile data. The value profile data is expected |
885 | // to follow the block counter profile data. |
886 | Version3 = 3, |
887 | // In this version, profile summary data \c IndexedInstrProf::Summary is |
888 | // stored after the profile header. |
889 | Version4 = 4, |
890 | // In this version, the frontend PGO stable hash algorithm defaults to V2. |
891 | Version5 = 5, |
892 | // The current version is 5. |
893 | CurrentVersion = INSTR_PROF_INDEX_VERSION5 |
894 | }; |
895 | const uint64_t Version = ProfVersion::CurrentVersion; |
896 | |
897 | const HashT HashType = HashT::MD5; |
898 | |
899 | inline uint64_t ComputeHash(StringRef K) { return ComputeHash(HashType, K); } |
900 | |
901 | // This structure defines the file header of the LLVM profile |
902 | // data file in indexed-format. |
903 | struct Header { |
904 | uint64_t Magic; |
905 | uint64_t Version; |
906 | uint64_t Unused; // Becomes unused since version 4 |
907 | uint64_t HashType; |
908 | uint64_t HashOffset; |
909 | }; |
910 | |
911 | // Profile summary data recorded in the profile data file in indexed |
912 | // format. It is introduced in version 4. The summary data follows |
913 | // right after the profile file header. |
914 | struct Summary { |
915 | struct Entry { |
916 | uint64_t Cutoff; ///< The required percentile of total execution count. |
917 | uint64_t |
918 | MinBlockCount; ///< The minimum execution count for this percentile. |
919 | uint64_t NumBlocks; ///< Number of blocks >= the minumum execution count. |
920 | }; |
921 | // The field kind enumerator to assigned value mapping should remain |
922 | // unchanged when a new kind is added or an old kind gets deleted in |
923 | // the future. |
924 | enum SummaryFieldKind { |
925 | /// The total number of functions instrumented. |
926 | TotalNumFunctions = 0, |
927 | /// Total number of instrumented blocks/edges. |
928 | TotalNumBlocks = 1, |
929 | /// The maximal execution count among all functions. |
930 | /// This field does not exist for profile data from IR based |
931 | /// instrumentation. |
932 | MaxFunctionCount = 2, |
933 | /// Max block count of the program. |
934 | MaxBlockCount = 3, |
935 | /// Max internal block count of the program (excluding entry blocks). |
936 | MaxInternalBlockCount = 4, |
937 | /// The sum of all instrumented block counts. |
938 | TotalBlockCount = 5, |
939 | NumKinds = TotalBlockCount + 1 |
940 | }; |
941 | |
942 | // The number of summmary fields following the summary header. |
943 | uint64_t NumSummaryFields; |
944 | // The number of Cutoff Entries (Summary::Entry) following summary fields. |
945 | uint64_t NumCutoffEntries; |
946 | |
947 | Summary() = delete; |
948 | Summary(uint32_t Size) { memset(this, 0, Size); } |
949 | |
950 | void operator delete(void *ptr) { ::operator delete(ptr); } |
951 | |
952 | static uint32_t getSize(uint32_t NumSumFields, uint32_t NumCutoffEntries) { |
953 | return sizeof(Summary) + NumCutoffEntries * sizeof(Entry) + |
954 | NumSumFields * sizeof(uint64_t); |
955 | } |
956 | |
957 | const uint64_t *getSummaryDataBase() const { |
958 | return reinterpret_cast<const uint64_t *>(this + 1); |
959 | } |
960 | |
961 | uint64_t *getSummaryDataBase() { |
962 | return reinterpret_cast<uint64_t *>(this + 1); |
963 | } |
964 | |
965 | const Entry *getCutoffEntryBase() const { |
966 | return reinterpret_cast<const Entry *>( |
967 | &getSummaryDataBase()[NumSummaryFields]); |
968 | } |
969 | |
970 | Entry *getCutoffEntryBase() { |
971 | return reinterpret_cast<Entry *>(&getSummaryDataBase()[NumSummaryFields]); |
972 | } |
973 | |
974 | uint64_t get(SummaryFieldKind K) const { |
975 | return getSummaryDataBase()[K]; |
976 | } |
977 | |
978 | void set(SummaryFieldKind K, uint64_t V) { |
979 | getSummaryDataBase()[K] = V; |
980 | } |
981 | |
982 | const Entry &getEntry(uint32_t I) const { return getCutoffEntryBase()[I]; } |
983 | |
984 | void setEntry(uint32_t I, const ProfileSummaryEntry &E) { |
985 | Entry &ER = getCutoffEntryBase()[I]; |
986 | ER.Cutoff = E.Cutoff; |
987 | ER.MinBlockCount = E.MinCount; |
988 | ER.NumBlocks = E.NumCounts; |
989 | } |
990 | }; |
991 | |
992 | inline std::unique_ptr<Summary> allocSummary(uint32_t TotalSize) { |
993 | return std::unique_ptr<Summary>(new (::operator new(TotalSize)) |
994 | Summary(TotalSize)); |
995 | } |
996 | |
997 | } // end namespace IndexedInstrProf |
998 | |
999 | namespace RawInstrProf { |
1000 | |
1001 | // Version 1: First version |
1002 | // Version 2: Added value profile data section. Per-function control data |
1003 | // struct has more fields to describe value profile information. |
1004 | // Version 3: Compressed name section support. Function PGO name reference |
1005 | // from control data struct is changed from raw pointer to Name's MD5 value. |
1006 | // Version 4: ValueDataBegin and ValueDataSizes fields are removed from the |
1007 | // raw header. |
1008 | const uint64_t Version = INSTR_PROF_RAW_VERSION4; |
1009 | |
1010 | template <class IntPtrT> inline uint64_t getMagic(); |
1011 | template <> inline uint64_t getMagic<uint64_t>() { |
1012 | return INSTR_PROF_RAW_MAGIC_64(uint64_t)255 << 56 | (uint64_t)'l' << 48 | (uint64_t )'p' << 40 | (uint64_t)'r' << 32 | (uint64_t)'o' << 24 | (uint64_t)'f' << 16 | (uint64_t)'r' << 8 | ( uint64_t)129; |
1013 | } |
1014 | |
1015 | template <> inline uint64_t getMagic<uint32_t>() { |
1016 | return INSTR_PROF_RAW_MAGIC_32(uint64_t)255 << 56 | (uint64_t)'l' << 48 | (uint64_t )'p' << 40 | (uint64_t)'r' << 32 | (uint64_t)'o' << 24 | (uint64_t)'f' << 16 | (uint64_t)'R' << 8 | ( uint64_t)129; |
1017 | } |
1018 | |
1019 | // Per-function profile data header/control structure. |
1020 | // The definition should match the structure defined in |
1021 | // compiler-rt/lib/profile/InstrProfiling.h. |
1022 | // It should also match the synthesized type in |
1023 | // Transforms/Instrumentation/InstrProfiling.cpp:getOrCreateRegionCounters. |
1024 | template <class IntPtrT> struct LLVM_ALIGNAS(8)alignas(8) ProfileData { |
1025 | #define INSTR_PROF_DATA(Type, LLVMType, Name, Init) Type Name; |
1026 | #include "llvm/ProfileData/InstrProfData.inc" |
1027 | }; |
1028 | |
1029 | // File header structure of the LLVM profile data in raw format. |
1030 | // The definition should match the header referenced in |
1031 | // compiler-rt/lib/profile/InstrProfilingFile.c and |
1032 | // InstrProfilingBuffer.c. |
1033 | struct Header { |
1034 | #define INSTR_PROF_RAW_HEADER(Type, Name, Init) const Type Name; |
1035 | #include "llvm/ProfileData/InstrProfData.inc" |
1036 | }; |
1037 | |
1038 | } // end namespace RawInstrProf |
1039 | |
1040 | // Parse MemOP Size range option. |
1041 | void getMemOPSizeRangeFromOption(StringRef Str, int64_t &RangeStart, |
1042 | int64_t &RangeLast); |
1043 | |
1044 | } // end namespace llvm |
1045 | |
1046 | #endif // LLVM_PROFILEDATA_INSTRPROF_H |
1 | //===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===// |
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 | // |
10 | // This file contains some templates that are useful if you are working with the |
11 | // STL at all. |
12 | // |
13 | // No library is required when using these functions. |
14 | // |
15 | //===----------------------------------------------------------------------===// |
16 | |
17 | #ifndef LLVM_ADT_STLEXTRAS_H |
18 | #define LLVM_ADT_STLEXTRAS_H |
19 | |
20 | #include "llvm/ADT/Optional.h" |
21 | #include "llvm/ADT/SmallVector.h" |
22 | #include "llvm/ADT/iterator.h" |
23 | #include "llvm/ADT/iterator_range.h" |
24 | #include "llvm/Support/ErrorHandling.h" |
25 | #include <algorithm> |
26 | #include <cassert> |
27 | #include <cstddef> |
28 | #include <cstdint> |
29 | #include <cstdlib> |
30 | #include <functional> |
31 | #include <initializer_list> |
32 | #include <iterator> |
33 | #include <limits> |
34 | #include <memory> |
35 | #include <tuple> |
36 | #include <type_traits> |
37 | #include <utility> |
38 | |
39 | #ifdef EXPENSIVE_CHECKS |
40 | #include <random> // for std::mt19937 |
41 | #endif |
42 | |
43 | namespace llvm { |
44 | |
45 | // Only used by compiler if both template types are the same. Useful when |
46 | // using SFINAE to test for the existence of member functions. |
47 | template <typename T, T> struct SameType; |
48 | |
49 | namespace detail { |
50 | |
51 | template <typename RangeT> |
52 | using IterOfRange = decltype(std::begin(std::declval<RangeT &>())); |
53 | |
54 | template <typename RangeT> |
55 | using ValueOfRange = typename std::remove_reference<decltype( |
56 | *std::begin(std::declval<RangeT &>()))>::type; |
57 | |
58 | } // end namespace detail |
59 | |
60 | //===----------------------------------------------------------------------===// |
61 | // Extra additions to <functional> |
62 | //===----------------------------------------------------------------------===// |
63 | |
64 | template <class Ty> struct identity { |
65 | using argument_type = Ty; |
66 | |
67 | Ty &operator()(Ty &self) const { |
68 | return self; |
69 | } |
70 | const Ty &operator()(const Ty &self) const { |
71 | return self; |
72 | } |
73 | }; |
74 | |
75 | template <class Ty> struct less_ptr { |
76 | bool operator()(const Ty* left, const Ty* right) const { |
77 | return *left < *right; |
78 | } |
79 | }; |
80 | |
81 | template <class Ty> struct greater_ptr { |
82 | bool operator()(const Ty* left, const Ty* right) const { |
83 | return *right < *left; |
84 | } |
85 | }; |
86 | |
87 | /// An efficient, type-erasing, non-owning reference to a callable. This is |
88 | /// intended for use as the type of a function parameter that is not used |
89 | /// after the function in question returns. |
90 | /// |
91 | /// This class does not own the callable, so it is not in general safe to store |
92 | /// a function_ref. |
93 | template<typename Fn> class function_ref; |
94 | |
95 | template<typename Ret, typename ...Params> |
96 | class function_ref<Ret(Params...)> { |
97 | Ret (*callback)(intptr_t callable, Params ...params) = nullptr; |
98 | intptr_t callable; |
99 | |
100 | template<typename Callable> |
101 | static Ret callback_fn(intptr_t callable, Params ...params) { |
102 | return (*reinterpret_cast<Callable*>(callable))( |
103 | std::forward<Params>(params)...); |
104 | } |
105 | |
106 | public: |
107 | function_ref() = default; |
108 | function_ref(std::nullptr_t) {} |
109 | |
110 | template <typename Callable> |
111 | function_ref(Callable &&callable, |
112 | typename std::enable_if< |
113 | !std::is_same<typename std::remove_reference<Callable>::type, |
114 | function_ref>::value>::type * = nullptr) |
115 | : callback(callback_fn<typename std::remove_reference<Callable>::type>), |
116 | callable(reinterpret_cast<intptr_t>(&callable)) {} |
117 | |
118 | Ret operator()(Params ...params) const { |
119 | return callback(callable, std::forward<Params>(params)...); |
120 | } |
121 | |
122 | operator bool() const { return callback; } |
123 | }; |
124 | |
125 | // deleter - Very very very simple method that is used to invoke operator |
126 | // delete on something. It is used like this: |
127 | // |
128 | // for_each(V.begin(), B.end(), deleter<Interval>); |
129 | template <class T> |
130 | inline void deleter(T *Ptr) { |
131 | delete Ptr; |
132 | } |
133 | |
134 | //===----------------------------------------------------------------------===// |
135 | // Extra additions to <iterator> |
136 | //===----------------------------------------------------------------------===// |
137 | |
138 | namespace adl_detail { |
139 | |
140 | using std::begin; |
141 | |
142 | template <typename ContainerTy> |
143 | auto adl_begin(ContainerTy &&container) |
144 | -> decltype(begin(std::forward<ContainerTy>(container))) { |
145 | return begin(std::forward<ContainerTy>(container)); |
146 | } |
147 | |
148 | using std::end; |
149 | |
150 | template <typename ContainerTy> |
151 | auto adl_end(ContainerTy &&container) |
152 | -> decltype(end(std::forward<ContainerTy>(container))) { |
153 | return end(std::forward<ContainerTy>(container)); |
154 | } |
155 | |
156 | using std::swap; |
157 | |
158 | template <typename T> |
159 | void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(), |
160 | std::declval<T>()))) { |
161 | swap(std::forward<T>(lhs), std::forward<T>(rhs)); |
162 | } |
163 | |
164 | } // end namespace adl_detail |
165 | |
166 | template <typename ContainerTy> |
167 | auto adl_begin(ContainerTy &&container) |
168 | -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) { |
169 | return adl_detail::adl_begin(std::forward<ContainerTy>(container)); |
170 | } |
171 | |
172 | template <typename ContainerTy> |
173 | auto adl_end(ContainerTy &&container) |
174 | -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) { |
175 | return adl_detail::adl_end(std::forward<ContainerTy>(container)); |
176 | } |
177 | |
178 | template <typename T> |
179 | void adl_swap(T &&lhs, T &&rhs) noexcept( |
180 | noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) { |
181 | adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs)); |
182 | } |
183 | |
184 | // mapped_iterator - This is a simple iterator adapter that causes a function to |
185 | // be applied whenever operator* is invoked on the iterator. |
186 | |
187 | template <typename ItTy, typename FuncTy, |
188 | typename FuncReturnTy = |
189 | decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))> |
190 | class mapped_iterator |
191 | : public iterator_adaptor_base< |
192 | mapped_iterator<ItTy, FuncTy>, ItTy, |
193 | typename std::iterator_traits<ItTy>::iterator_category, |
194 | typename std::remove_reference<FuncReturnTy>::type> { |
195 | public: |
196 | mapped_iterator(ItTy U, FuncTy F) |
197 | : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {} |
198 | |
199 | ItTy getCurrent() { return this->I; } |
200 | |
201 | FuncReturnTy operator*() { return F(*this->I); } |
202 | |
203 | private: |
204 | FuncTy F; |
205 | }; |
206 | |
207 | // map_iterator - Provide a convenient way to create mapped_iterators, just like |
208 | // make_pair is useful for creating pairs... |
209 | template <class ItTy, class FuncTy> |
210 | inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) { |
211 | return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F)); |
212 | } |
213 | |
214 | /// Helper to determine if type T has a member called rbegin(). |
215 | template <typename Ty> class has_rbegin_impl { |
216 | using yes = char[1]; |
217 | using no = char[2]; |
218 | |
219 | template <typename Inner> |
220 | static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr); |
221 | |
222 | template <typename> |
223 | static no& test(...); |
224 | |
225 | public: |
226 | static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes); |
227 | }; |
228 | |
229 | /// Metafunction to determine if T& or T has a member called rbegin(). |
230 | template <typename Ty> |
231 | struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> { |
232 | }; |
233 | |
234 | // Returns an iterator_range over the given container which iterates in reverse. |
235 | // Note that the container must have rbegin()/rend() methods for this to work. |
236 | template <typename ContainerTy> |
237 | auto reverse(ContainerTy &&C, |
238 | typename std::enable_if<has_rbegin<ContainerTy>::value>::type * = |
239 | nullptr) -> decltype(make_range(C.rbegin(), C.rend())) { |
240 | return make_range(C.rbegin(), C.rend()); |
241 | } |
242 | |
243 | // Returns a std::reverse_iterator wrapped around the given iterator. |
244 | template <typename IteratorTy> |
245 | std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) { |
246 | return std::reverse_iterator<IteratorTy>(It); |
247 | } |
248 | |
249 | // Returns an iterator_range over the given container which iterates in reverse. |
250 | // Note that the container must have begin()/end() methods which return |
251 | // bidirectional iterators for this to work. |
252 | template <typename ContainerTy> |
253 | auto reverse( |
254 | ContainerTy &&C, |
255 | typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr) |
256 | -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)), |
257 | llvm::make_reverse_iterator(std::begin(C)))) { |
258 | return make_range(llvm::make_reverse_iterator(std::end(C)), |
259 | llvm::make_reverse_iterator(std::begin(C))); |
260 | } |
261 | |
262 | /// An iterator adaptor that filters the elements of given inner iterators. |
263 | /// |
264 | /// The predicate parameter should be a callable object that accepts the wrapped |
265 | /// iterator's reference type and returns a bool. When incrementing or |
266 | /// decrementing the iterator, it will call the predicate on each element and |
267 | /// skip any where it returns false. |
268 | /// |
269 | /// \code |
270 | /// int A[] = { 1, 2, 3, 4 }; |
271 | /// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; }); |
272 | /// // R contains { 1, 3 }. |
273 | /// \endcode |
274 | template <typename WrappedIteratorT, typename PredicateT> |
275 | class filter_iterator |
276 | : public iterator_adaptor_base< |
277 | filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT, |
278 | typename std::common_type< |
279 | std::forward_iterator_tag, |
280 | typename std::iterator_traits< |
281 | WrappedIteratorT>::iterator_category>::type> { |
282 | using BaseT = iterator_adaptor_base< |
283 | filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT, |
284 | typename std::common_type< |
285 | std::forward_iterator_tag, |
286 | typename std::iterator_traits<WrappedIteratorT>::iterator_category>:: |
287 | type>; |
288 | |
289 | struct PayloadType { |
290 | WrappedIteratorT End; |
291 | PredicateT Pred; |
292 | }; |
293 | |
294 | Optional<PayloadType> Payload; |
295 | |
296 | void findNextValid() { |
297 | assert(Payload && "Payload should be engaged when findNextValid is called")(static_cast <bool> (Payload && "Payload should be engaged when findNextValid is called" ) ? void (0) : __assert_fail ("Payload && \"Payload should be engaged when findNextValid is called\"" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/STLExtras.h" , 297, __extension__ __PRETTY_FUNCTION__)); |
298 | while (this->I != Payload->End && !Payload->Pred(*this->I)) |
299 | BaseT::operator++(); |
300 | } |
301 | |
302 | // Construct the begin iterator. The begin iterator requires to know where end |
303 | // is, so that it can properly stop when it hits end. |
304 | filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred) |
305 | : BaseT(std::move(Begin)), |
306 | Payload(PayloadType{std::move(End), std::move(Pred)}) { |
307 | findNextValid(); |
308 | } |
309 | |
310 | // Construct the end iterator. It's not incrementable, so Payload doesn't |
311 | // have to be engaged. |
312 | filter_iterator(WrappedIteratorT End) : BaseT(End) {} |
313 | |
314 | public: |
315 | using BaseT::operator++; |
316 | |
317 | filter_iterator &operator++() { |
318 | BaseT::operator++(); |
319 | findNextValid(); |
320 | return *this; |
321 | } |
322 | |
323 | template <typename RT, typename PT> |
324 | friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>> |
325 | make_filter_range(RT &&, PT); |
326 | }; |
327 | |
328 | /// Convenience function that takes a range of elements and a predicate, |
329 | /// and return a new filter_iterator range. |
330 | /// |
331 | /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the |
332 | /// lifetime of that temporary is not kept by the returned range object, and the |
333 | /// temporary is going to be dropped on the floor after the make_iterator_range |
334 | /// full expression that contains this function call. |
335 | template <typename RangeT, typename PredicateT> |
336 | iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> |
337 | make_filter_range(RangeT &&Range, PredicateT Pred) { |
338 | using FilterIteratorT = |
339 | filter_iterator<detail::IterOfRange<RangeT>, PredicateT>; |
340 | return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)), |
341 | std::end(std::forward<RangeT>(Range)), |
342 | std::move(Pred)), |
343 | FilterIteratorT(std::end(std::forward<RangeT>(Range)))); |
344 | } |
345 | |
346 | // forward declarations required by zip_shortest/zip_first |
347 | template <typename R, typename UnaryPredicate> |
348 | bool all_of(R &&range, UnaryPredicate P); |
349 | |
350 | template <size_t... I> struct index_sequence; |
351 | |
352 | template <class... Ts> struct index_sequence_for; |
353 | |
354 | namespace detail { |
355 | |
356 | using std::declval; |
357 | |
358 | // We have to alias this since inlining the actual type at the usage site |
359 | // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017. |
360 | template<typename... Iters> struct ZipTupleType { |
361 | using type = std::tuple<decltype(*declval<Iters>())...>; |
362 | }; |
363 | |
364 | template <typename ZipType, typename... Iters> |
365 | using zip_traits = iterator_facade_base< |
366 | ZipType, typename std::common_type<std::bidirectional_iterator_tag, |
367 | typename std::iterator_traits< |
368 | Iters>::iterator_category...>::type, |
369 | // ^ TODO: Implement random access methods. |
370 | typename ZipTupleType<Iters...>::type, |
371 | typename std::iterator_traits<typename std::tuple_element< |
372 | 0, std::tuple<Iters...>>::type>::difference_type, |
373 | // ^ FIXME: This follows boost::make_zip_iterator's assumption that all |
374 | // inner iterators have the same difference_type. It would fail if, for |
375 | // instance, the second field's difference_type were non-numeric while the |
376 | // first is. |
377 | typename ZipTupleType<Iters...>::type *, |
378 | typename ZipTupleType<Iters...>::type>; |
379 | |
380 | template <typename ZipType, typename... Iters> |
381 | struct zip_common : public zip_traits<ZipType, Iters...> { |
382 | using Base = zip_traits<ZipType, Iters...>; |
383 | using value_type = typename Base::value_type; |
384 | |
385 | std::tuple<Iters...> iterators; |
386 | |
387 | protected: |
388 | template <size_t... Ns> value_type deref(index_sequence<Ns...>) const { |
389 | return value_type(*std::get<Ns>(iterators)...); |
390 | } |
391 | |
392 | template <size_t... Ns> |
393 | decltype(iterators) tup_inc(index_sequence<Ns...>) const { |
394 | return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...); |
395 | } |
396 | |
397 | template <size_t... Ns> |
398 | decltype(iterators) tup_dec(index_sequence<Ns...>) const { |
399 | return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...); |
400 | } |
401 | |
402 | public: |
403 | zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {} |
404 | |
405 | value_type operator*() { return deref(index_sequence_for<Iters...>{}); } |
406 | |
407 | const value_type operator*() const { |
408 | return deref(index_sequence_for<Iters...>{}); |
409 | } |
410 | |
411 | ZipType &operator++() { |
412 | iterators = tup_inc(index_sequence_for<Iters...>{}); |
413 | return *reinterpret_cast<ZipType *>(this); |
414 | } |
415 | |
416 | ZipType &operator--() { |
417 | static_assert(Base::IsBidirectional, |
418 | "All inner iterators must be at least bidirectional."); |
419 | iterators = tup_dec(index_sequence_for<Iters...>{}); |
420 | return *reinterpret_cast<ZipType *>(this); |
421 | } |
422 | }; |
423 | |
424 | template <typename... Iters> |
425 | struct zip_first : public zip_common<zip_first<Iters...>, Iters...> { |
426 | using Base = zip_common<zip_first<Iters...>, Iters...>; |
427 | |
428 | bool operator==(const zip_first<Iters...> &other) const { |
429 | return std::get<0>(this->iterators) == std::get<0>(other.iterators); |
430 | } |
431 | |
432 | zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {} |
433 | }; |
434 | |
435 | template <typename... Iters> |
436 | class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> { |
437 | template <size_t... Ns> |
438 | bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const { |
439 | return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) != |
440 | std::get<Ns>(other.iterators)...}, |
441 | identity<bool>{}); |
442 | } |
443 | |
444 | public: |
445 | using Base = zip_common<zip_shortest<Iters...>, Iters...>; |
446 | |
447 | zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {} |
448 | |
449 | bool operator==(const zip_shortest<Iters...> &other) const { |
450 | return !test(other, index_sequence_for<Iters...>{}); |
451 | } |
452 | }; |
453 | |
454 | template <template <typename...> class ItType, typename... Args> class zippy { |
455 | public: |
456 | using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>; |
457 | using iterator_category = typename iterator::iterator_category; |
458 | using value_type = typename iterator::value_type; |
459 | using difference_type = typename iterator::difference_type; |
460 | using pointer = typename iterator::pointer; |
461 | using reference = typename iterator::reference; |
462 | |
463 | private: |
464 | std::tuple<Args...> ts; |
465 | |
466 | template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const { |
467 | return iterator(std::begin(std::get<Ns>(ts))...); |
468 | } |
469 | template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const { |
470 | return iterator(std::end(std::get<Ns>(ts))...); |
471 | } |
472 | |
473 | public: |
474 | zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {} |
475 | |
476 | iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); } |
477 | iterator end() const { return end_impl(index_sequence_for<Args...>{}); } |
478 | }; |
479 | |
480 | } // end namespace detail |
481 | |
482 | /// zip iterator for two or more iteratable types. |
483 | template <typename T, typename U, typename... Args> |
484 | detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u, |
485 | Args &&... args) { |
486 | return detail::zippy<detail::zip_shortest, T, U, Args...>( |
487 | std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); |
488 | } |
489 | |
490 | /// zip iterator that, for the sake of efficiency, assumes the first iteratee to |
491 | /// be the shortest. |
492 | template <typename T, typename U, typename... Args> |
493 | detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u, |
494 | Args &&... args) { |
495 | return detail::zippy<detail::zip_first, T, U, Args...>( |
496 | std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); |
497 | } |
498 | |
499 | /// Iterator wrapper that concatenates sequences together. |
500 | /// |
501 | /// This can concatenate different iterators, even with different types, into |
502 | /// a single iterator provided the value types of all the concatenated |
503 | /// iterators expose `reference` and `pointer` types that can be converted to |
504 | /// `ValueT &` and `ValueT *` respectively. It doesn't support more |
505 | /// interesting/customized pointer or reference types. |
506 | /// |
507 | /// Currently this only supports forward or higher iterator categories as |
508 | /// inputs and always exposes a forward iterator interface. |
509 | template <typename ValueT, typename... IterTs> |
510 | class concat_iterator |
511 | : public iterator_facade_base<concat_iterator<ValueT, IterTs...>, |
512 | std::forward_iterator_tag, ValueT> { |
513 | using BaseT = typename concat_iterator::iterator_facade_base; |
514 | |
515 | /// We store both the current and end iterators for each concatenated |
516 | /// sequence in a tuple of pairs. |
517 | /// |
518 | /// Note that something like iterator_range seems nice at first here, but the |
519 | /// range properties are of little benefit and end up getting in the way |
520 | /// because we need to do mutation on the current iterators. |
521 | std::tuple<std::pair<IterTs, IterTs>...> IterPairs; |
522 | |
523 | /// Attempts to increment a specific iterator. |
524 | /// |
525 | /// Returns true if it was able to increment the iterator. Returns false if |
526 | /// the iterator is already at the end iterator. |
527 | template <size_t Index> bool incrementHelper() { |
528 | auto &IterPair = std::get<Index>(IterPairs); |
529 | if (IterPair.first == IterPair.second) |
530 | return false; |
531 | |
532 | ++IterPair.first; |
533 | return true; |
534 | } |
535 | |
536 | /// Increments the first non-end iterator. |
537 | /// |
538 | /// It is an error to call this with all iterators at the end. |
539 | template <size_t... Ns> void increment(index_sequence<Ns...>) { |
540 | // Build a sequence of functions to increment each iterator if possible. |
541 | bool (concat_iterator::*IncrementHelperFns[])() = { |
542 | &concat_iterator::incrementHelper<Ns>...}; |
543 | |
544 | // Loop over them, and stop as soon as we succeed at incrementing one. |
545 | for (auto &IncrementHelperFn : IncrementHelperFns) |
546 | if ((this->*IncrementHelperFn)()) |
547 | return; |
548 | |
549 | llvm_unreachable("Attempted to increment an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to increment an end concat iterator!" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/STLExtras.h" , 549); |
550 | } |
551 | |
552 | /// Returns null if the specified iterator is at the end. Otherwise, |
553 | /// dereferences the iterator and returns the address of the resulting |
554 | /// reference. |
555 | template <size_t Index> ValueT *getHelper() const { |
556 | auto &IterPair = std::get<Index>(IterPairs); |
557 | if (IterPair.first == IterPair.second) |
558 | return nullptr; |
559 | |
560 | return &*IterPair.first; |
561 | } |
562 | |
563 | /// Finds the first non-end iterator, dereferences, and returns the resulting |
564 | /// reference. |
565 | /// |
566 | /// It is an error to call this with all iterators at the end. |
567 | template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const { |
568 | // Build a sequence of functions to get from iterator if possible. |
569 | ValueT *(concat_iterator::*GetHelperFns[])() const = { |
570 | &concat_iterator::getHelper<Ns>...}; |
571 | |
572 | // Loop over them, and return the first result we find. |
573 | for (auto &GetHelperFn : GetHelperFns) |
574 | if (ValueT *P = (this->*GetHelperFn)()) |
575 | return *P; |
576 | |
577 | llvm_unreachable("Attempted to get a pointer from an end concat iterator!")::llvm::llvm_unreachable_internal("Attempted to get a pointer from an end concat iterator!" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/STLExtras.h" , 577); |
578 | } |
579 | |
580 | public: |
581 | /// Constructs an iterator from a squence of ranges. |
582 | /// |
583 | /// We need the full range to know how to switch between each of the |
584 | /// iterators. |
585 | template <typename... RangeTs> |
586 | explicit concat_iterator(RangeTs &&... Ranges) |
587 | : IterPairs({std::begin(Ranges), std::end(Ranges)}...) {} |
588 | |
589 | using BaseT::operator++; |
590 | |
591 | concat_iterator &operator++() { |
592 | increment(index_sequence_for<IterTs...>()); |
593 | return *this; |
594 | } |
595 | |
596 | ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); } |
597 | |
598 | bool operator==(const concat_iterator &RHS) const { |
599 | return IterPairs == RHS.IterPairs; |
600 | } |
601 | }; |
602 | |
603 | namespace detail { |
604 | |
605 | /// Helper to store a sequence of ranges being concatenated and access them. |
606 | /// |
607 | /// This is designed to facilitate providing actual storage when temporaries |
608 | /// are passed into the constructor such that we can use it as part of range |
609 | /// based for loops. |
610 | template <typename ValueT, typename... RangeTs> class concat_range { |
611 | public: |
612 | using iterator = |
613 | concat_iterator<ValueT, |
614 | decltype(std::begin(std::declval<RangeTs &>()))...>; |
615 | |
616 | private: |
617 | std::tuple<RangeTs...> Ranges; |
618 | |
619 | template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) { |
620 | return iterator(std::get<Ns>(Ranges)...); |
621 | } |
622 | template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) { |
623 | return iterator(make_range(std::end(std::get<Ns>(Ranges)), |
624 | std::end(std::get<Ns>(Ranges)))...); |
625 | } |
626 | |
627 | public: |
628 | concat_range(RangeTs &&... Ranges) |
629 | : Ranges(std::forward<RangeTs>(Ranges)...) {} |
630 | |
631 | iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); } |
632 | iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); } |
633 | }; |
634 | |
635 | } // end namespace detail |
636 | |
637 | /// Concatenated range across two or more ranges. |
638 | /// |
639 | /// The desired value type must be explicitly specified. |
640 | template <typename ValueT, typename... RangeTs> |
641 | detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) { |
642 | static_assert(sizeof...(RangeTs) > 1, |
643 | "Need more than one range to concatenate!"); |
644 | return detail::concat_range<ValueT, RangeTs...>( |
645 | std::forward<RangeTs>(Ranges)...); |
646 | } |
647 | |
648 | //===----------------------------------------------------------------------===// |
649 | // Extra additions to <utility> |
650 | //===----------------------------------------------------------------------===// |
651 | |
652 | /// \brief Function object to check whether the first component of a std::pair |
653 | /// compares less than the first component of another std::pair. |
654 | struct less_first { |
655 | template <typename T> bool operator()(const T &lhs, const T &rhs) const { |
656 | return lhs.first < rhs.first; |
657 | } |
658 | }; |
659 | |
660 | /// \brief Function object to check whether the second component of a std::pair |
661 | /// compares less than the second component of another std::pair. |
662 | struct less_second { |
663 | template <typename T> bool operator()(const T &lhs, const T &rhs) const { |
664 | return lhs.second < rhs.second; |
665 | } |
666 | }; |
667 | |
668 | // A subset of N3658. More stuff can be added as-needed. |
669 | |
670 | /// \brief Represents a compile-time sequence of integers. |
671 | template <class T, T... I> struct integer_sequence { |
672 | using value_type = T; |
673 | |
674 | static constexpr size_t size() { return sizeof...(I); } |
675 | }; |
676 | |
677 | /// \brief Alias for the common case of a sequence of size_ts. |
678 | template <size_t... I> |
679 | struct index_sequence : integer_sequence<std::size_t, I...> {}; |
680 | |
681 | template <std::size_t N, std::size_t... I> |
682 | struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; |
683 | template <std::size_t... I> |
684 | struct build_index_impl<0, I...> : index_sequence<I...> {}; |
685 | |
686 | /// \brief Creates a compile-time integer sequence for a parameter pack. |
687 | template <class... Ts> |
688 | struct index_sequence_for : build_index_impl<sizeof...(Ts)> {}; |
689 | |
690 | /// Utility type to build an inheritance chain that makes it easy to rank |
691 | /// overload candidates. |
692 | template <int N> struct rank : rank<N - 1> {}; |
693 | template <> struct rank<0> {}; |
694 | |
695 | /// \brief traits class for checking whether type T is one of any of the given |
696 | /// types in the variadic list. |
697 | template <typename T, typename... Ts> struct is_one_of { |
698 | static const bool value = false; |
699 | }; |
700 | |
701 | template <typename T, typename U, typename... Ts> |
702 | struct is_one_of<T, U, Ts...> { |
703 | static const bool value = |
704 | std::is_same<T, U>::value || is_one_of<T, Ts...>::value; |
705 | }; |
706 | |
707 | /// \brief traits class for checking whether type T is a base class for all |
708 | /// the given types in the variadic list. |
709 | template <typename T, typename... Ts> struct are_base_of { |
710 | static const bool value = true; |
711 | }; |
712 | |
713 | template <typename T, typename U, typename... Ts> |
714 | struct are_base_of<T, U, Ts...> { |
715 | static const bool value = |
716 | std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value; |
717 | }; |
718 | |
719 | //===----------------------------------------------------------------------===// |
720 | // Extra additions for arrays |
721 | //===----------------------------------------------------------------------===// |
722 | |
723 | /// Find the length of an array. |
724 | template <class T, std::size_t N> |
725 | constexpr inline size_t array_lengthof(T (&)[N]) { |
726 | return N; |
727 | } |
728 | |
729 | /// Adapt std::less<T> for array_pod_sort. |
730 | template<typename T> |
731 | inline int array_pod_sort_comparator(const void *P1, const void *P2) { |
732 | if (std::less<T>()(*reinterpret_cast<const T*>(P1), |
733 | *reinterpret_cast<const T*>(P2))) |
734 | return -1; |
735 | if (std::less<T>()(*reinterpret_cast<const T*>(P2), |
736 | *reinterpret_cast<const T*>(P1))) |
737 | return 1; |
738 | return 0; |
739 | } |
740 | |
741 | /// get_array_pod_sort_comparator - This is an internal helper function used to |
742 | /// get type deduction of T right. |
743 | template<typename T> |
744 | inline int (*get_array_pod_sort_comparator(const T &)) |
745 | (const void*, const void*) { |
746 | return array_pod_sort_comparator<T>; |
747 | } |
748 | |
749 | /// array_pod_sort - This sorts an array with the specified start and end |
750 | /// extent. This is just like std::sort, except that it calls qsort instead of |
751 | /// using an inlined template. qsort is slightly slower than std::sort, but |
752 | /// most sorts are not performance critical in LLVM and std::sort has to be |
753 | /// template instantiated for each type, leading to significant measured code |
754 | /// bloat. This function should generally be used instead of std::sort where |
755 | /// possible. |
756 | /// |
757 | /// This function assumes that you have simple POD-like types that can be |
758 | /// compared with std::less and can be moved with memcpy. If this isn't true, |
759 | /// you should use std::sort. |
760 | /// |
761 | /// NOTE: If qsort_r were portable, we could allow a custom comparator and |
762 | /// default to std::less. |
763 | template<class IteratorTy> |
764 | inline void array_pod_sort(IteratorTy Start, IteratorTy End) { |
765 | // Don't inefficiently call qsort with one element or trigger undefined |
766 | // behavior with an empty sequence. |
767 | auto NElts = End - Start; |
768 | if (NElts <= 1) return; |
769 | #ifdef EXPENSIVE_CHECKS |
770 | std::mt19937 Generator(std::random_device{}()); |
771 | std::shuffle(Start, End, Generator); |
772 | #endif |
773 | qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start)); |
774 | } |
775 | |
776 | template <class IteratorTy> |
777 | inline void array_pod_sort( |
778 | IteratorTy Start, IteratorTy End, |
779 | int (*Compare)( |
780 | const typename std::iterator_traits<IteratorTy>::value_type *, |
781 | const typename std::iterator_traits<IteratorTy>::value_type *)) { |
782 | // Don't inefficiently call qsort with one element or trigger undefined |
783 | // behavior with an empty sequence. |
784 | auto NElts = End - Start; |
785 | if (NElts <= 1) return; |
786 | #ifdef EXPENSIVE_CHECKS |
787 | std::mt19937 Generator(std::random_device{}()); |
788 | std::shuffle(Start, End, Generator); |
789 | #endif |
790 | qsort(&*Start, NElts, sizeof(*Start), |
791 | reinterpret_cast<int (*)(const void *, const void *)>(Compare)); |
792 | } |
793 | |
794 | // Provide wrappers to std::sort which shuffle the elements before sorting |
795 | // to help uncover non-deterministic behavior (PR35135). |
796 | template <typename IteratorTy> |
797 | inline void sort(IteratorTy Start, IteratorTy End) { |
798 | #ifdef EXPENSIVE_CHECKS |
799 | std::mt19937 Generator(std::random_device{}()); |
800 | std::shuffle(Start, End, Generator); |
801 | #endif |
802 | std::sort(Start, End); |
803 | } |
804 | |
805 | template <typename IteratorTy, typename Compare> |
806 | inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) { |
807 | #ifdef EXPENSIVE_CHECKS |
808 | std::mt19937 Generator(std::random_device{}()); |
809 | std::shuffle(Start, End, Generator); |
810 | #endif |
811 | std::sort(Start, End, Comp); |
812 | } |
813 | |
814 | //===----------------------------------------------------------------------===// |
815 | // Extra additions to <algorithm> |
816 | //===----------------------------------------------------------------------===// |
817 | |
818 | /// For a container of pointers, deletes the pointers and then clears the |
819 | /// container. |
820 | template<typename Container> |
821 | void DeleteContainerPointers(Container &C) { |
822 | for (auto V : C) |
823 | delete V; |
824 | C.clear(); |
825 | } |
826 | |
827 | /// In a container of pairs (usually a map) whose second element is a pointer, |
828 | /// deletes the second elements and then clears the container. |
829 | template<typename Container> |
830 | void DeleteContainerSeconds(Container &C) { |
831 | for (auto &V : C) |
832 | delete V.second; |
833 | C.clear(); |
834 | } |
835 | |
836 | /// Provide wrappers to std::for_each which take ranges instead of having to |
837 | /// pass begin/end explicitly. |
838 | template <typename R, typename UnaryPredicate> |
839 | UnaryPredicate for_each(R &&Range, UnaryPredicate P) { |
840 | return std::for_each(adl_begin(Range), adl_end(Range), P); |
841 | } |
842 | |
843 | /// Provide wrappers to std::all_of which take ranges instead of having to pass |
844 | /// begin/end explicitly. |
845 | template <typename R, typename UnaryPredicate> |
846 | bool all_of(R &&Range, UnaryPredicate P) { |
847 | return std::all_of(adl_begin(Range), adl_end(Range), P); |
848 | } |
849 | |
850 | /// Provide wrappers to std::any_of which take ranges instead of having to pass |
851 | /// begin/end explicitly. |
852 | template <typename R, typename UnaryPredicate> |
853 | bool any_of(R &&Range, UnaryPredicate P) { |
854 | return std::any_of(adl_begin(Range), adl_end(Range), P); |
855 | } |
856 | |
857 | /// Provide wrappers to std::none_of which take ranges instead of having to pass |
858 | /// begin/end explicitly. |
859 | template <typename R, typename UnaryPredicate> |
860 | bool none_of(R &&Range, UnaryPredicate P) { |
861 | return std::none_of(adl_begin(Range), adl_end(Range), P); |
862 | } |
863 | |
864 | /// Provide wrappers to std::find which take ranges instead of having to pass |
865 | /// begin/end explicitly. |
866 | template <typename R, typename T> |
867 | auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) { |
868 | return std::find(adl_begin(Range), adl_end(Range), Val); |
869 | } |
870 | |
871 | /// Provide wrappers to std::find_if which take ranges instead of having to pass |
872 | /// begin/end explicitly. |
873 | template <typename R, typename UnaryPredicate> |
874 | auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) { |
875 | return std::find_if(adl_begin(Range), adl_end(Range), P); |
876 | } |
877 | |
878 | template <typename R, typename UnaryPredicate> |
879 | auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) { |
880 | return std::find_if_not(adl_begin(Range), adl_end(Range), P); |
881 | } |
882 | |
883 | /// Provide wrappers to std::remove_if which take ranges instead of having to |
884 | /// pass begin/end explicitly. |
885 | template <typename R, typename UnaryPredicate> |
886 | auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) { |
887 | return std::remove_if(adl_begin(Range), adl_end(Range), P); |
888 | } |
889 | |
890 | /// Provide wrappers to std::copy_if which take ranges instead of having to |
891 | /// pass begin/end explicitly. |
892 | template <typename R, typename OutputIt, typename UnaryPredicate> |
893 | OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) { |
894 | return std::copy_if(adl_begin(Range), adl_end(Range), Out, P); |
895 | } |
896 | |
897 | template <typename R, typename OutputIt> |
898 | OutputIt copy(R &&Range, OutputIt Out) { |
899 | return std::copy(adl_begin(Range), adl_end(Range), Out); |
900 | } |
901 | |
902 | /// Wrapper function around std::find to detect if an element exists |
903 | /// in a container. |
904 | template <typename R, typename E> |
905 | bool is_contained(R &&Range, const E &Element) { |
906 | return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range); |
907 | } |
908 | |
909 | /// Wrapper function around std::count to count the number of times an element |
910 | /// \p Element occurs in the given range \p Range. |
911 | template <typename R, typename E> |
912 | auto count(R &&Range, const E &Element) -> |
913 | typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type { |
914 | return std::count(adl_begin(Range), adl_end(Range), Element); |
915 | } |
916 | |
917 | /// Wrapper function around std::count_if to count the number of times an |
918 | /// element satisfying a given predicate occurs in a range. |
919 | template <typename R, typename UnaryPredicate> |
920 | auto count_if(R &&Range, UnaryPredicate P) -> |
921 | typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type { |
922 | return std::count_if(adl_begin(Range), adl_end(Range), P); |
923 | } |
924 | |
925 | /// Wrapper function around std::transform to apply a function to a range and |
926 | /// store the result elsewhere. |
927 | template <typename R, typename OutputIt, typename UnaryPredicate> |
928 | OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) { |
929 | return std::transform(adl_begin(Range), adl_end(Range), d_first, P); |
930 | } |
931 | |
932 | /// Provide wrappers to std::partition which take ranges instead of having to |
933 | /// pass begin/end explicitly. |
934 | template <typename R, typename UnaryPredicate> |
935 | auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) { |
936 | return std::partition(adl_begin(Range), adl_end(Range), P); |
937 | } |
938 | |
939 | /// Provide wrappers to std::lower_bound which take ranges instead of having to |
940 | /// pass begin/end explicitly. |
941 | template <typename R, typename ForwardIt> |
942 | auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) { |
943 | return std::lower_bound(adl_begin(Range), adl_end(Range), I); |
944 | } |
945 | |
946 | /// \brief Given a range of type R, iterate the entire range and return a |
947 | /// SmallVector with elements of the vector. This is useful, for example, |
948 | /// when you want to iterate a range and then sort the results. |
949 | template <unsigned Size, typename R> |
950 | SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size> |
951 | to_vector(R &&Range) { |
952 | return {adl_begin(Range), adl_end(Range)}; |
953 | } |
954 | |
955 | /// Provide a container algorithm similar to C++ Library Fundamentals v2's |
956 | /// `erase_if` which is equivalent to: |
957 | /// |
958 | /// C.erase(remove_if(C, pred), C.end()); |
959 | /// |
960 | /// This version works for any container with an erase method call accepting |
961 | /// two iterators. |
962 | template <typename Container, typename UnaryPredicate> |
963 | void erase_if(Container &C, UnaryPredicate P) { |
964 | C.erase(remove_if(C, P), C.end()); |
965 | } |
966 | |
967 | //===----------------------------------------------------------------------===// |
968 | // Extra additions to <memory> |
969 | //===----------------------------------------------------------------------===// |
970 | |
971 | // Implement make_unique according to N3656. |
972 | |
973 | /// \brief Constructs a `new T()` with the given args and returns a |
974 | /// `unique_ptr<T>` which owns the object. |
975 | /// |
976 | /// Example: |
977 | /// |
978 | /// auto p = make_unique<int>(); |
979 | /// auto p = make_unique<std::tuple<int, int>>(0, 1); |
980 | template <class T, class... Args> |
981 | typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type |
982 | make_unique(Args &&... args) { |
983 | return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); |
984 | } |
985 | |
986 | /// \brief Constructs a `new T[n]` with the given args and returns a |
987 | /// `unique_ptr<T[]>` which owns the object. |
988 | /// |
989 | /// \param n size of the new array. |
990 | /// |
991 | /// Example: |
992 | /// |
993 | /// auto p = make_unique<int[]>(2); // value-initializes the array with 0's. |
994 | template <class T> |
995 | typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, |
996 | std::unique_ptr<T>>::type |
997 | make_unique(size_t n) { |
998 | return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]()); |
999 | } |
1000 | |
1001 | /// This function isn't used and is only here to provide better compile errors. |
1002 | template <class T, class... Args> |
1003 | typename std::enable_if<std::extent<T>::value != 0>::type |
1004 | make_unique(Args &&...) = delete; |
1005 | |
1006 | struct FreeDeleter { |
1007 | void operator()(void* v) { |
1008 | ::free(v); |
1009 | } |
1010 | }; |
1011 | |
1012 | template<typename First, typename Second> |
1013 | struct pair_hash { |
1014 | size_t operator()(const std::pair<First, Second> &P) const { |
1015 | return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second); |
1016 | } |
1017 | }; |
1018 | |
1019 | /// A functor like C++14's std::less<void> in its absence. |
1020 | struct less { |
1021 | template <typename A, typename B> bool operator()(A &&a, B &&b) const { |
1022 | return std::forward<A>(a) < std::forward<B>(b); |
1023 | } |
1024 | }; |
1025 | |
1026 | /// A functor like C++14's std::equal<void> in its absence. |
1027 | struct equal { |
1028 | template <typename A, typename B> bool operator()(A &&a, B &&b) const { |
1029 | return std::forward<A>(a) == std::forward<B>(b); |
1030 | } |
1031 | }; |
1032 | |
1033 | /// Binary functor that adapts to any other binary functor after dereferencing |
1034 | /// operands. |
1035 | template <typename T> struct deref { |
1036 | T func; |
1037 | |
1038 | // Could be further improved to cope with non-derivable functors and |
1039 | // non-binary functors (should be a variadic template member function |
1040 | // operator()). |
1041 | template <typename A, typename B> |
1042 | auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) { |
1043 | assert(lhs)(static_cast <bool> (lhs) ? void (0) : __assert_fail ("lhs" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/STLExtras.h" , 1043, __extension__ __PRETTY_FUNCTION__)); |
1044 | assert(rhs)(static_cast <bool> (rhs) ? void (0) : __assert_fail ("rhs" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/STLExtras.h" , 1044, __extension__ __PRETTY_FUNCTION__)); |
1045 | return func(*lhs, *rhs); |
1046 | } |
1047 | }; |
1048 | |
1049 | namespace detail { |
1050 | |
1051 | template <typename R> class enumerator_iter; |
1052 | |
1053 | template <typename R> struct result_pair { |
1054 | friend class enumerator_iter<R>; |
1055 | |
1056 | result_pair() = default; |
1057 | result_pair(std::size_t Index, IterOfRange<R> Iter) |
1058 | : Index(Index), Iter(Iter) {} |
1059 | |
1060 | result_pair<R> &operator=(const result_pair<R> &Other) { |
1061 | Index = Other.Index; |
1062 | Iter = Other.Iter; |
1063 | return *this; |
1064 | } |
1065 | |
1066 | std::size_t index() const { return Index; } |
1067 | const ValueOfRange<R> &value() const { return *Iter; } |
1068 | ValueOfRange<R> &value() { return *Iter; } |
1069 | |
1070 | private: |
1071 | std::size_t Index = std::numeric_limits<std::size_t>::max(); |
1072 | IterOfRange<R> Iter; |
1073 | }; |
1074 | |
1075 | template <typename R> |
1076 | class enumerator_iter |
1077 | : public iterator_facade_base< |
1078 | enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>, |
1079 | typename std::iterator_traits<IterOfRange<R>>::difference_type, |
1080 | typename std::iterator_traits<IterOfRange<R>>::pointer, |
1081 | typename std::iterator_traits<IterOfRange<R>>::reference> { |
1082 | using result_type = result_pair<R>; |
1083 | |
1084 | public: |
1085 | explicit enumerator_iter(IterOfRange<R> EndIter) |
1086 | : Result(std::numeric_limits<size_t>::max(), EndIter) {} |
1087 | |
1088 | enumerator_iter(std::size_t Index, IterOfRange<R> Iter) |
1089 | : Result(Index, Iter) {} |
1090 | |
1091 | result_type &operator*() { return Result; } |
1092 | const result_type &operator*() const { return Result; } |
1093 | |
1094 | enumerator_iter<R> &operator++() { |
1095 | assert(Result.Index != std::numeric_limits<size_t>::max())(static_cast <bool> (Result.Index != std::numeric_limits <size_t>::max()) ? void (0) : __assert_fail ("Result.Index != std::numeric_limits<size_t>::max()" , "/build/llvm-toolchain-snapshot-7~svn329677/include/llvm/ADT/STLExtras.h" , 1095, __extension__ __PRETTY_FUNCTION__)); |
1096 | ++Result.Iter; |
1097 | ++Result.Index; |
1098 | return *this; |
1099 | } |
1100 | |
1101 | bool operator==(const enumerator_iter<R> &RHS) const { |
1102 | // Don't compare indices here, only iterators. It's possible for an end |
1103 | // iterator to have different indices depending on whether it was created |
1104 | // by calling std::end() versus incrementing a valid iterator. |
1105 | return Result.Iter == RHS.Result.Iter; |
1106 | } |
1107 | |
1108 | enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) { |
1109 | Result = Other.Result; |
1110 | return *this; |
1111 | } |
1112 | |
1113 | private: |
1114 | result_type Result; |
1115 | }; |
1116 | |
1117 | template <typename R> class enumerator { |
1118 | public: |
1119 | explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {} |
1120 | |
1121 | enumerator_iter<R> begin() { |
1122 | return enumerator_iter<R>(0, std::begin(TheRange)); |
1123 | } |
1124 | |
1125 | enumerator_iter<R> end() { |
1126 | return enumerator_iter<R>(std::end(TheRange)); |
1127 | } |
1128 | |
1129 | private: |
1130 | R TheRange; |
1131 | }; |
1132 | |
1133 | } // end namespace detail |
1134 | |
1135 | /// Given an input range, returns a new range whose values are are pair (A,B) |
1136 | /// such that A is the 0-based index of the item in the sequence, and B is |
1137 | /// the value from the original sequence. Example: |
1138 | /// |
1139 | /// std::vector<char> Items = {'A', 'B', 'C', 'D'}; |
1140 | /// for (auto X : enumerate(Items)) { |
1141 | /// printf("Item %d - %c\n", X.index(), X.value()); |
1142 | /// } |
1143 | /// |
1144 | /// Output: |
1145 | /// Item 0 - A |
1146 | /// Item 1 - B |
1147 | /// Item 2 - C |
1148 | /// Item 3 - D |
1149 | /// |
1150 | template <typename R> detail::enumerator<R> enumerate(R &&TheRange) { |
1151 | return detail::enumerator<R>(std::forward<R>(TheRange)); |
1152 | } |
1153 | |
1154 | namespace detail { |
1155 | |
1156 | template <typename F, typename Tuple, std::size_t... I> |
1157 | auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>) |
1158 | -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) { |
1159 | return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...); |
1160 | } |
1161 | |
1162 | } // end namespace detail |
1163 | |
1164 | /// Given an input tuple (a1, a2, ..., an), pass the arguments of the |
1165 | /// tuple variadically to f as if by calling f(a1, a2, ..., an) and |
1166 | /// return the result. |
1167 | template <typename F, typename Tuple> |
1168 | auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl( |
1169 | std::forward<F>(f), std::forward<Tuple>(t), |
1170 | build_index_impl< |
1171 | std::tuple_size<typename std::decay<Tuple>::type>::value>{})) { |
1172 | using Indices = build_index_impl< |
1173 | std::tuple_size<typename std::decay<Tuple>::type>::value>; |
1174 | |
1175 | return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t), |
1176 | Indices{}); |
1177 | } |
1178 | |
1179 | } // end namespace llvm |
1180 | |
1181 | #endif // LLVM_ADT_STLEXTRAS_H |