[PGO] Value profiling support
[oota-llvm.git] / lib / ProfileData / InstrProfReader.cpp
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/STLExtras.h"
17 #include <cassert>
18
19 using namespace llvm;
20
21 static ErrorOr<std::unique_ptr<MemoryBuffer>>
22 setupMemoryBuffer(std::string Path) {
23   ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOrErr =
24       MemoryBuffer::getFileOrSTDIN(Path);
25   if (std::error_code EC = BufferOrErr.getError())
26     return EC;
27   return std::move(BufferOrErr.get());
28 }
29
30 static std::error_code initializeReader(InstrProfReader &Reader) {
31   return Reader.readHeader();
32 }
33
34 ErrorOr<std::unique_ptr<InstrProfReader>>
35 InstrProfReader::create(std::string Path) {
36   // Set up the buffer to read.
37   auto BufferOrError = setupMemoryBuffer(Path);
38   if (std::error_code EC = BufferOrError.getError())
39     return EC;
40   return InstrProfReader::create(std::move(BufferOrError.get()));
41 }
42
43 ErrorOr<std::unique_ptr<InstrProfReader>>
44 InstrProfReader::create(std::unique_ptr<MemoryBuffer> Buffer) {
45   // Sanity check the buffer.
46   if (Buffer->getBufferSize() > std::numeric_limits<unsigned>::max())
47     return instrprof_error::too_large;
48
49   std::unique_ptr<InstrProfReader> Result;
50   // Create the reader.
51   if (IndexedInstrProfReader::hasFormat(*Buffer))
52     Result.reset(new IndexedInstrProfReader(std::move(Buffer)));
53   else if (RawInstrProfReader64::hasFormat(*Buffer))
54     Result.reset(new RawInstrProfReader64(std::move(Buffer)));
55   else if (RawInstrProfReader32::hasFormat(*Buffer))
56     Result.reset(new RawInstrProfReader32(std::move(Buffer)));
57   else if (TextInstrProfReader::hasFormat(*Buffer))
58     Result.reset(new TextInstrProfReader(std::move(Buffer)));
59   else
60     return instrprof_error::unrecognized_format;
61
62   // Initialize the reader and return the result.
63   if (std::error_code EC = initializeReader(*Result))
64     return EC;
65
66   return std::move(Result);
67 }
68
69 ErrorOr<std::unique_ptr<IndexedInstrProfReader>>
70 IndexedInstrProfReader::create(std::string Path) {
71   // Set up the buffer to read.
72   auto BufferOrError = setupMemoryBuffer(Path);
73   if (std::error_code EC = BufferOrError.getError())
74     return EC;
75   return IndexedInstrProfReader::create(std::move(BufferOrError.get()));
76 }
77
78
79 ErrorOr<std::unique_ptr<IndexedInstrProfReader>>
80 IndexedInstrProfReader::create(std::unique_ptr<MemoryBuffer> Buffer) {
81   // Sanity check the buffer.
82   if (Buffer->getBufferSize() > std::numeric_limits<unsigned>::max())
83     return instrprof_error::too_large;
84
85   // Create the reader.
86   if (!IndexedInstrProfReader::hasFormat(*Buffer))
87     return instrprof_error::bad_magic;
88   auto Result = llvm::make_unique<IndexedInstrProfReader>(std::move(Buffer));
89
90   // Initialize the reader and return the result.
91   if (std::error_code EC = initializeReader(*Result))
92     return EC;
93
94   return std::move(Result);
95 }
96
97 void InstrProfIterator::Increment() {
98   if (Reader->readNextRecord(Record))
99     *this = InstrProfIterator();
100 }
101
102 bool TextInstrProfReader::hasFormat(const MemoryBuffer &Buffer) {
103   // Verify that this really looks like plain ASCII text by checking a
104   // 'reasonable' number of characters (up to profile magic size).
105   size_t count = std::min(Buffer.getBufferSize(), sizeof(uint64_t));
106   StringRef buffer = Buffer.getBufferStart();
107   return count == 0 || std::all_of(buffer.begin(), buffer.begin() + count,
108     [](char c) { return ::isprint(c) || ::isspace(c); });
109 }
110
111 std::error_code TextInstrProfReader::readNextRecord(InstrProfRecord &Record) {
112   // Skip empty lines and comments.
113   while (!Line.is_at_end() && (Line->empty() || Line->startswith("#")))
114     ++Line;
115   // If we hit EOF while looking for a name, we're done.
116   if (Line.is_at_end())
117     return error(instrprof_error::eof);
118
119   // Read the function name.
120   Record.Name = *Line++;
121
122   // Read the function hash.
123   if (Line.is_at_end())
124     return error(instrprof_error::truncated);
125   if ((Line++)->getAsInteger(0, Record.Hash))
126     return error(instrprof_error::malformed);
127
128   // Read the number of counters.
129   uint64_t NumCounters;
130   if (Line.is_at_end())
131     return error(instrprof_error::truncated);
132   if ((Line++)->getAsInteger(10, NumCounters))
133     return error(instrprof_error::malformed);
134   if (NumCounters == 0)
135     return error(instrprof_error::malformed);
136
137   // Read each counter and fill our internal storage with the values.
138   Record.Counts.clear();
139   Record.Counts.reserve(NumCounters);
140   for (uint64_t I = 0; I < NumCounters; ++I) {
141     if (Line.is_at_end())
142       return error(instrprof_error::truncated);
143     uint64_t Count;
144     if ((Line++)->getAsInteger(10, Count))
145       return error(instrprof_error::malformed);
146     Record.Counts.push_back(Count);
147   }
148
149   return success();
150 }
151
152 template <class IntPtrT>
153 bool RawInstrProfReader<IntPtrT>::hasFormat(const MemoryBuffer &DataBuffer) {
154   if (DataBuffer.getBufferSize() < sizeof(uint64_t))
155     return false;
156   uint64_t Magic =
157     *reinterpret_cast<const uint64_t *>(DataBuffer.getBufferStart());
158   return RawInstrProf::getMagic<IntPtrT>() == Magic ||
159          sys::getSwappedBytes(RawInstrProf::getMagic<IntPtrT>()) == Magic;
160 }
161
162 template <class IntPtrT>
163 std::error_code RawInstrProfReader<IntPtrT>::readHeader() {
164   if (!hasFormat(*DataBuffer))
165     return error(instrprof_error::bad_magic);
166   if (DataBuffer->getBufferSize() < sizeof(RawInstrProf::Header))
167     return error(instrprof_error::bad_header);
168   auto *Header = reinterpret_cast<const RawInstrProf::Header *>(
169       DataBuffer->getBufferStart());
170   ShouldSwapBytes = Header->Magic != RawInstrProf::getMagic<IntPtrT>();
171   return readHeader(*Header);
172 }
173
174 template <class IntPtrT>
175 std::error_code
176 RawInstrProfReader<IntPtrT>::readNextHeader(const char *CurrentPos) {
177   const char *End = DataBuffer->getBufferEnd();
178   // Skip zero padding between profiles.
179   while (CurrentPos != End && *CurrentPos == 0)
180     ++CurrentPos;
181   // If there's nothing left, we're done.
182   if (CurrentPos == End)
183     return instrprof_error::eof;
184   // If there isn't enough space for another header, this is probably just
185   // garbage at the end of the file.
186   if (CurrentPos + sizeof(RawInstrProf::Header) > End)
187     return instrprof_error::malformed;
188   // The writer ensures each profile is padded to start at an aligned address.
189   if (reinterpret_cast<size_t>(CurrentPos) % alignOf<uint64_t>())
190     return instrprof_error::malformed;
191   // The magic should have the same byte order as in the previous header.
192   uint64_t Magic = *reinterpret_cast<const uint64_t *>(CurrentPos);
193   if (Magic != swap(RawInstrProf::getMagic<IntPtrT>()))
194     return instrprof_error::bad_magic;
195
196   // There's another profile to read, so we need to process the header.
197   auto *Header = reinterpret_cast<const RawInstrProf::Header *>(CurrentPos);
198   return readHeader(*Header);
199 }
200
201 template <class IntPtrT>
202 std::error_code RawInstrProfReader<IntPtrT>::readHeader(
203     const RawInstrProf::Header &Header) {
204   if (swap(Header.Version) != RawInstrProf::Version)
205     return error(instrprof_error::unsupported_version);
206
207   CountersDelta = swap(Header.CountersDelta);
208   NamesDelta = swap(Header.NamesDelta);
209   ValueDataDelta = swap(Header.ValueDataDelta);
210   auto DataSize = swap(Header.DataSize);
211   auto CountersSize = swap(Header.CountersSize);
212   auto NamesSize = swap(Header.NamesSize);
213   auto ValueDataSize = swap(Header.ValueDataSize);
214   ValueKindLast = swap(Header.ValueKindLast);
215
216   auto DataSizeInBytes = DataSize * sizeof(RawInstrProf::ProfileData<IntPtrT>);
217   auto PaddingSize = getNumPaddingBytes(NamesSize);
218
219   ptrdiff_t DataOffset = sizeof(RawInstrProf::Header);
220   ptrdiff_t CountersOffset = DataOffset + DataSizeInBytes;
221   ptrdiff_t NamesOffset = CountersOffset + sizeof(uint64_t) * CountersSize;
222   ptrdiff_t ValueDataOffset = NamesOffset + NamesSize + PaddingSize;
223   size_t ProfileSize = ValueDataOffset + ValueDataSize;
224
225   auto *Start = reinterpret_cast<const char *>(&Header);
226   if (Start + ProfileSize > DataBuffer->getBufferEnd())
227     return error(instrprof_error::bad_header);
228
229   Data = reinterpret_cast<const RawInstrProf::ProfileData<IntPtrT> *>(
230       Start + DataOffset);
231   DataEnd = Data + DataSize;
232   CountersStart = reinterpret_cast<const uint64_t *>(Start + CountersOffset);
233   NamesStart = Start + NamesOffset;
234   ValueDataStart = reinterpret_cast<const uint8_t*>(Start + ValueDataOffset);
235   ProfileEnd = Start + ProfileSize;
236
237   FunctionPtrToNameMap.clear();
238   for (const RawInstrProf::ProfileData<IntPtrT> *I = Data; I != DataEnd; ++I) {
239     const IntPtrT FPtr = swap(I->FunctionPointer);
240     if (!FPtr)
241       continue;
242     StringRef FunctionName(getName(I->NamePtr), swap(I->NameSize));
243     const char* NameEntryPtr = StringTable.insertString(FunctionName);
244     FunctionPtrToNameMap.push_back(std::pair<const IntPtrT, const char*>
245                                    (FPtr, NameEntryPtr));
246   }
247   std::sort(FunctionPtrToNameMap.begin(), FunctionPtrToNameMap.end(), less_first());
248   FunctionPtrToNameMap.erase(std::unique(FunctionPtrToNameMap.begin(),
249                                          FunctionPtrToNameMap.end()),
250                                          FunctionPtrToNameMap.end());
251   return success();
252 }
253
254 template <class IntPtrT>
255 std::error_code RawInstrProfReader<IntPtrT>::readName(InstrProfRecord &Record) {
256   Record.Name = StringRef(getName(Data->NamePtr), swap(Data->NameSize));
257   if (Record.Name.data() < NamesStart ||
258       Record.Name.data() + Record.Name.size() > (char*)ValueDataStart)
259     return error(instrprof_error::malformed);
260   return success();
261 }
262
263 template <class IntPtrT>
264 std::error_code RawInstrProfReader<IntPtrT>::readFuncHash(
265     InstrProfRecord &Record) {
266   Record.Hash = swap(Data->FuncHash);
267   return success();
268 }
269
270 template <class IntPtrT>
271 std::error_code RawInstrProfReader<IntPtrT>::readRawCounts(
272     InstrProfRecord &Record) {
273   uint32_t NumCounters = swap(Data->NumCounters);
274   IntPtrT CounterPtr = Data->CounterPtr;
275   if (NumCounters == 0)
276     return error(instrprof_error::malformed);
277
278   auto RawCounts = makeArrayRef(getCounter(CounterPtr), NumCounters);
279   auto *NamesStartAsCounter = reinterpret_cast<const uint64_t *>(NamesStart);
280
281   // Check bounds.
282   if (RawCounts.data() < CountersStart ||
283       RawCounts.data() + RawCounts.size() > NamesStartAsCounter)
284     return error(instrprof_error::malformed);
285
286   if (ShouldSwapBytes) {
287     Record.Counts.clear();
288     Record.Counts.reserve(RawCounts.size());
289     for (uint64_t Count : RawCounts)
290       Record.Counts.push_back(swap(Count));
291   } else
292     Record.Counts = RawCounts;
293
294   return success();
295 }
296
297 template <class IntPtrT>
298 std::error_code RawInstrProfReader<IntPtrT>::readValueData(
299     InstrProfRecord &Record) {
300
301   Record.clearValueData();
302   if (!Data->Values || (ValueDataDelta == 0))
303     return success();
304
305   // Read value data.
306   uint64_t NumVSites = 0;
307   for (uint32_t Kind = IPVK_First; Kind <= ValueKindLast; ++Kind)
308     NumVSites += swap(Data->NumValueSites[Kind]);
309   NumVSites += getNumPaddingBytes(NumVSites);
310
311   auto VDataCounts = makeArrayRef(getValueDataCounts(Data->Values), NumVSites);
312   // Check bounds.
313   if (VDataCounts.data() < ValueDataStart ||
314       VDataCounts.data() + VDataCounts.size() > (const uint8_t *)ProfileEnd)
315     return error(instrprof_error::malformed);
316
317   const InstrProfValueData *VDataPtr =
318       getValueData(swap(Data->Values) + NumVSites);
319   for (uint32_t Kind = IPVK_First; Kind <= ValueKindLast; ++Kind) {
320     NumVSites = swap(Data->NumValueSites[Kind]);
321     Record.reserveSites(Kind, NumVSites);
322     for (uint32_t VSite = 0; VSite < NumVSites; ++VSite) {
323
324       uint32_t VDataCount = VDataCounts[VSite];
325       if ((const char *)(VDataPtr + VDataCount) > ProfileEnd)
326         return error(instrprof_error::malformed);
327
328       std::vector<InstrProfValueData> CurrentValues;
329       CurrentValues.reserve(VDataCount);
330       for (uint32_t VIndex = 0; VIndex < VDataCount; ++VIndex) {
331         uint64_t TargetValue = swap(VDataPtr->Value);
332         uint64_t Count = swap(VDataPtr->Count);
333         CurrentValues.push_back({TargetValue, Count});
334         ++VDataPtr;
335       }
336       Record.addValueData(Kind, VSite, CurrentValues.data(),
337                           VDataCount, &FunctionPtrToNameMap);
338     }
339   }
340   return success();
341 }
342
343 template <class IntPtrT>
344 std::error_code RawInstrProfReader<IntPtrT>::readNextRecord(
345     InstrProfRecord &Record) {
346   if (atEnd())
347     if (std::error_code EC = readNextHeader(ProfileEnd))
348       return EC;
349
350   // Read name ad set it in Record.
351   if (std::error_code EC = readName(Record))
352     return EC;
353
354   // Read FuncHash and set it in Record.
355   if (std::error_code EC = readFuncHash(Record))
356     return EC;
357
358   // Read raw counts and set Record.
359   if (std::error_code EC = readRawCounts(Record))
360     return EC;
361
362   // Read value data and set Record.
363   if (std::error_code EC = readValueData(Record)) return EC;
364
365   // Iterate.
366   advanceData();
367   return success();
368 }
369
370 namespace llvm {
371 template class RawInstrProfReader<uint32_t>;
372 template class RawInstrProfReader<uint64_t>;
373 }
374
375 InstrProfLookupTrait::hash_value_type
376 InstrProfLookupTrait::ComputeHash(StringRef K) {
377   return IndexedInstrProf::ComputeHash(HashType, K);
378 }
379
380 typedef InstrProfLookupTrait::data_type data_type;
381 typedef InstrProfLookupTrait::offset_type offset_type;
382
383 bool InstrProfLookupTrait::ReadValueProfilingData(
384     const unsigned char *&D, const unsigned char *const End) {
385   ErrorOr<std::unique_ptr<ValueProfData>> VDataPtrOrErr =
386       ValueProfData::getValueProfData(D, End, ValueProfDataEndianness);
387
388   if (VDataPtrOrErr.getError())
389     return false;
390
391   VDataPtrOrErr.get()->deserializeTo(DataBuffer.back(), &HashKeys);
392   D += VDataPtrOrErr.get()->TotalSize;
393
394   return true;
395 }
396
397 data_type InstrProfLookupTrait::ReadData(StringRef K, const unsigned char *D,
398                                          offset_type N) {
399   // Check if the data is corrupt. If so, don't try to read it.
400   if (N % sizeof(uint64_t))
401     return data_type();
402
403   DataBuffer.clear();
404   std::vector<uint64_t> CounterBuffer;
405
406   using namespace support;
407   const unsigned char *End = D + N;
408   while (D < End) {
409     // Read hash.
410     if (D + sizeof(uint64_t) >= End)
411       return data_type();
412     uint64_t Hash = endian::readNext<uint64_t, little, unaligned>(D);
413
414     // Initialize number of counters for FormatVersion == 1.
415     uint64_t CountsSize = N / sizeof(uint64_t) - 1;
416     // If format version is different then read the number of counters.
417     if (FormatVersion != 1) {
418       if (D + sizeof(uint64_t) > End)
419         return data_type();
420       CountsSize = endian::readNext<uint64_t, little, unaligned>(D);
421     }
422     // Read counter values.
423     if (D + CountsSize * sizeof(uint64_t) > End)
424       return data_type();
425
426     CounterBuffer.clear();
427     CounterBuffer.reserve(CountsSize);
428     for (uint64_t J = 0; J < CountsSize; ++J)
429       CounterBuffer.push_back(endian::readNext<uint64_t, little, unaligned>(D));
430
431     DataBuffer.emplace_back(K, Hash, std::move(CounterBuffer));
432
433     // Read value profiling data.
434     if (FormatVersion > 2 && !ReadValueProfilingData(D, End)) {
435       DataBuffer.clear();
436       return data_type();
437     }
438   }
439   return DataBuffer;
440 }
441
442 std::error_code
443 InstrProfReaderIndex::getRecords(StringRef FuncName,
444                                  ArrayRef<InstrProfRecord> &Data) {
445   auto Iter = Index->find(FuncName);
446   if (Iter == Index->end())
447     return instrprof_error::unknown_function;
448
449   Data = (*Iter);
450   if (Data.empty())
451     return instrprof_error::malformed;
452
453   return instrprof_error::success;
454 }
455
456 std::error_code InstrProfReaderIndex::getRecords(
457     ArrayRef<InstrProfRecord> &Data) {
458   if (atEnd()) return instrprof_error::eof;
459
460   Data = *RecordIterator;
461
462   if (Data.empty()) return instrprof_error::malformed;
463
464   return instrprof_error::success;
465 }
466
467 void InstrProfReaderIndex::Init(const unsigned char *Buckets,
468                                 const unsigned char *const Payload,
469                                 const unsigned char *const Base,
470                                 IndexedInstrProf::HashT HashType,
471                                 uint64_t Version) {
472   FormatVersion = Version;
473   Index.reset(IndexType::Create(Buckets, Payload, Base,
474                                 InstrProfLookupTrait(HashType, Version)));
475   // Form the map of hash values to const char* keys in profiling data.
476   std::vector<std::pair<uint64_t, const char *>> HashKeys;
477   for (auto Key : Index->keys()) {
478     const char *KeyTableRef = StringTable.insertString(Key);
479     HashKeys.push_back(std::make_pair(ComputeHash(HashType, Key), KeyTableRef));
480   }
481   std::sort(HashKeys.begin(), HashKeys.end(), less_first());
482   HashKeys.erase(std::unique(HashKeys.begin(), HashKeys.end()), HashKeys.end());
483   // Set the hash key map for the InstrLookupTrait
484   Index->getInfoObj().setHashKeys(std::move(HashKeys));
485   RecordIterator = Index->data_begin();
486 }
487
488 bool IndexedInstrProfReader::hasFormat(const MemoryBuffer &DataBuffer) {
489   if (DataBuffer.getBufferSize() < 8)
490     return false;
491   using namespace support;
492   uint64_t Magic =
493       endian::read<uint64_t, little, aligned>(DataBuffer.getBufferStart());
494   // Verify that it's magical.
495   return Magic == IndexedInstrProf::Magic;
496 }
497
498 std::error_code IndexedInstrProfReader::readHeader() {
499   const unsigned char *Start =
500       (const unsigned char *)DataBuffer->getBufferStart();
501   const unsigned char *Cur = Start;
502   if ((const unsigned char *)DataBuffer->getBufferEnd() - Cur < 24)
503     return error(instrprof_error::truncated);
504
505   using namespace support;
506
507   auto *Header = reinterpret_cast<const IndexedInstrProf::Header *>(Cur);
508   Cur += sizeof(IndexedInstrProf::Header);
509
510   // Check the magic number.
511   uint64_t Magic = endian::byte_swap<uint64_t, little>(Header->Magic);
512   if (Magic != IndexedInstrProf::Magic)
513     return error(instrprof_error::bad_magic);
514
515   // Read the version.
516   uint64_t FormatVersion = endian::byte_swap<uint64_t, little>(Header->Version);
517   if (FormatVersion > IndexedInstrProf::Version)
518     return error(instrprof_error::unsupported_version);
519
520   // Read the maximal function count.
521   MaxFunctionCount =
522       endian::byte_swap<uint64_t, little>(Header->MaxFunctionCount);
523
524   // Read the hash type and start offset.
525   IndexedInstrProf::HashT HashType = static_cast<IndexedInstrProf::HashT>(
526       endian::byte_swap<uint64_t, little>(Header->HashType));
527   if (HashType > IndexedInstrProf::HashT::Last)
528     return error(instrprof_error::unsupported_hash_type);
529
530   uint64_t HashOffset = endian::byte_swap<uint64_t, little>(Header->HashOffset);
531
532   // The rest of the file is an on disk hash table.
533   Index.Init(Start + HashOffset, Cur, Start, HashType, FormatVersion);
534
535   return success();
536 }
537
538 ErrorOr<InstrProfRecord>
539 IndexedInstrProfReader::getInstrProfRecord(StringRef FuncName,
540                                            uint64_t FuncHash) {
541   ArrayRef<InstrProfRecord> Data;
542   std::error_code EC = Index.getRecords(FuncName, Data);
543   if (EC != instrprof_error::success)
544     return EC;
545   // Found it. Look for counters with the right hash.
546   for (unsigned I = 0, E = Data.size(); I < E; ++I) {
547     // Check for a match and fill the vector if there is one.
548     if (Data[I].Hash == FuncHash) {
549       return std::move(Data[I]);
550     }
551   }
552   return error(instrprof_error::hash_mismatch);
553 }
554
555 std::error_code
556 IndexedInstrProfReader::getFunctionCounts(StringRef FuncName, uint64_t FuncHash,
557                                           std::vector<uint64_t> &Counts) {
558   ErrorOr<InstrProfRecord> Record = getInstrProfRecord(FuncName, FuncHash);
559   if (std::error_code EC = Record.getError())
560     return EC;
561
562   Counts = Record.get().Counts;
563   return success();
564 }
565
566 std::error_code IndexedInstrProfReader::readNextRecord(
567     InstrProfRecord &Record) {
568   static unsigned RecordIndex = 0;
569
570   ArrayRef<InstrProfRecord> Data;
571
572   std::error_code EC = Index.getRecords(Data);
573   if (EC != instrprof_error::success)
574     return error(EC);
575
576   Record = Data[RecordIndex++];
577   if (RecordIndex >= Data.size()) {
578     Index.advanceToNextKey();
579     RecordIndex = 0;
580   }
581   return success();
582 }