[PGO] simple refactoring (NFC)
[oota-llvm.git] / lib / ProfileData / InstrProf.cpp
1 //=-- InstrProf.cpp - Instrumented profiling format support -----------------=//
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 clang's instrumentation based PGO and
11 // coverage.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "llvm/ProfileData/InstrProf.h"
16 #include "llvm/IR/Constants.h"
17 #include "llvm/IR/Function.h"
18 #include "llvm/IR/GlobalVariable.h"
19 #include "llvm/IR/Module.h"
20 #include "llvm/Support/Compression.h"
21 #include "llvm/Support/ErrorHandling.h"
22 #include "llvm/Support/LEB128.h"
23 #include "llvm/Support/ManagedStatic.h"
24
25 using namespace llvm;
26
27 namespace {
28 class InstrProfErrorCategoryType : public std::error_category {
29   const char *name() const LLVM_NOEXCEPT override { return "llvm.instrprof"; }
30   std::string message(int IE) const override {
31     instrprof_error E = static_cast<instrprof_error>(IE);
32     switch (E) {
33     case instrprof_error::success:
34       return "Success";
35     case instrprof_error::eof:
36       return "End of File";
37     case instrprof_error::unrecognized_format:
38       return "Unrecognized instrumentation profile encoding format";
39     case instrprof_error::bad_magic:
40       return "Invalid instrumentation profile data (bad magic)";
41     case instrprof_error::bad_header:
42       return "Invalid instrumentation profile data (file header is corrupt)";
43     case instrprof_error::unsupported_version:
44       return "Unsupported instrumentation profile format version";
45     case instrprof_error::unsupported_hash_type:
46       return "Unsupported instrumentation profile hash type";
47     case instrprof_error::too_large:
48       return "Too much profile data";
49     case instrprof_error::truncated:
50       return "Truncated profile data";
51     case instrprof_error::malformed:
52       return "Malformed instrumentation profile data";
53     case instrprof_error::unknown_function:
54       return "No profile data available for function";
55     case instrprof_error::hash_mismatch:
56       return "Function control flow change detected (hash mismatch)";
57     case instrprof_error::count_mismatch:
58       return "Function basic block count change detected (counter mismatch)";
59     case instrprof_error::counter_overflow:
60       return "Counter overflow";
61     case instrprof_error::value_site_count_mismatch:
62       return "Function value site count change detected (counter mismatch)";
63     }
64     llvm_unreachable("A value of instrprof_error has no message.");
65   }
66 };
67 }
68
69 static ManagedStatic<InstrProfErrorCategoryType> ErrorCategory;
70
71 const std::error_category &llvm::instrprof_category() {
72   return *ErrorCategory;
73 }
74
75 namespace llvm {
76
77 std::string getPGOFuncName(StringRef RawFuncName,
78                            GlobalValue::LinkageTypes Linkage,
79                            StringRef FileName,
80                            uint64_t Version LLVM_ATTRIBUTE_UNUSED) {
81
82   // Function names may be prefixed with a binary '1' to indicate
83   // that the backend should not modify the symbols due to any platform
84   // naming convention. Do not include that '1' in the PGO profile name.
85   if (RawFuncName[0] == '\1')
86     RawFuncName = RawFuncName.substr(1);
87
88   std::string FuncName = RawFuncName;
89   if (llvm::GlobalValue::isLocalLinkage(Linkage)) {
90     // For local symbols, prepend the main file name to distinguish them.
91     // Do not include the full path in the file name since there's no guarantee
92     // that it will stay the same, e.g., if the files are checked out from
93     // version control in different locations.
94     if (FileName.empty())
95       FuncName = FuncName.insert(0, "<unknown>:");
96     else
97       FuncName = FuncName.insert(0, FileName.str() + ":");
98   }
99   return FuncName;
100 }
101
102 std::string getPGOFuncName(const Function &F, uint64_t Version) {
103   return getPGOFuncName(F.getName(), F.getLinkage(), F.getParent()->getName(),
104                         Version);
105 }
106
107 StringRef getFuncNameWithoutPrefix(StringRef PGOFuncName, StringRef FileName) {
108   if (FileName.empty())
109     return PGOFuncName;
110   // Drop the file name including ':'. See also getPGOFuncName.
111   if (PGOFuncName.startswith(FileName))
112     PGOFuncName = PGOFuncName.drop_front(FileName.size() + 1);
113   return PGOFuncName;
114 }
115
116 // \p FuncName is the string used as profile lookup key for the function. A
117 // symbol is created to hold the name. Return the legalized symbol name.
118 static std::string getPGOFuncNameVarName(StringRef FuncName,
119                                          GlobalValue::LinkageTypes Linkage) {
120   std::string VarName = getInstrProfNameVarPrefix();
121   VarName += FuncName;
122
123   if (!GlobalValue::isLocalLinkage(Linkage))
124     return VarName;
125
126   // Now fix up illegal chars in local VarName that may upset the assembler.
127   const char *InvalidChars = "-:<>\"'";
128   size_t found = VarName.find_first_of(InvalidChars);
129   while (found != std::string::npos) {
130     VarName[found] = '_';
131     found = VarName.find_first_of(InvalidChars, found + 1);
132   }
133   return VarName;
134 }
135
136 GlobalVariable *createPGOFuncNameVar(Module &M,
137                                      GlobalValue::LinkageTypes Linkage,
138                                      StringRef FuncName) {
139
140   // We generally want to match the function's linkage, but available_externally
141   // and extern_weak both have the wrong semantics, and anything that doesn't
142   // need to link across compilation units doesn't need to be visible at all.
143   if (Linkage == GlobalValue::ExternalWeakLinkage)
144     Linkage = GlobalValue::LinkOnceAnyLinkage;
145   else if (Linkage == GlobalValue::AvailableExternallyLinkage)
146     Linkage = GlobalValue::LinkOnceODRLinkage;
147   else if (Linkage == GlobalValue::InternalLinkage ||
148            Linkage == GlobalValue::ExternalLinkage)
149     Linkage = GlobalValue::PrivateLinkage;
150
151   auto *Value = ConstantDataArray::getString(M.getContext(), FuncName, false);
152   auto FuncNameVar =
153       new GlobalVariable(M, Value->getType(), true, Linkage, Value,
154                          getPGOFuncNameVarName(FuncName, Linkage));
155
156   // Hide the symbol so that we correctly get a copy for each executable.
157   if (!GlobalValue::isLocalLinkage(FuncNameVar->getLinkage()))
158     FuncNameVar->setVisibility(GlobalValue::HiddenVisibility);
159
160   return FuncNameVar;
161 }
162
163 GlobalVariable *createPGOFuncNameVar(Function &F, StringRef FuncName) {
164   return createPGOFuncNameVar(*F.getParent(), F.getLinkage(), FuncName);
165 }
166
167 int collectPGOFuncNameStrings(const std::vector<std::string> &NameStrs,
168                               bool doCompression, std::string &Result) {
169   uint8_t Header[16], *P = Header;
170   std::string UncompressedNameStrings;
171
172   for (auto NameStr : NameStrs) {
173     UncompressedNameStrings += NameStr;
174     UncompressedNameStrings.append(" ");
175   }
176   unsigned EncLen = encodeULEB128(UncompressedNameStrings.length(), P);
177   P += EncLen;
178   if (!doCompression) {
179     EncLen = encodeULEB128(0, P);
180     P += EncLen;
181     Result.append(reinterpret_cast<char *>(&Header[0]), P - &Header[0]);
182     Result += UncompressedNameStrings;
183     return 0;
184   }
185   SmallVector<char, 128> CompressedNameStrings;
186   zlib::Status Success =
187       zlib::compress(StringRef(UncompressedNameStrings), CompressedNameStrings,
188                      zlib::BestSizeCompression);
189   assert(Success == zlib::StatusOK);
190   if (Success != zlib::StatusOK)
191     return 1;
192   EncLen = encodeULEB128(CompressedNameStrings.size(), P);
193   P += EncLen;
194   Result.append(reinterpret_cast<char *>(&Header[0]), P - &Header[0]);
195   Result +=
196       std::string(CompressedNameStrings.data(), CompressedNameStrings.size());
197   return 0;
198 }
199
200 StringRef getPGOFuncNameInitializer(GlobalVariable *NameVar) {
201   auto *Arr = cast<ConstantDataArray>(NameVar->getInitializer());
202   StringRef NameStr =
203       Arr->isCString() ? Arr->getAsCString() : Arr->getAsString();
204   return NameStr;
205 }
206
207 int collectPGOFuncNameStrings(const std::vector<GlobalVariable *> &NameVars,
208                               std::string &Result) {
209   std::vector<std::string> NameStrs;
210   for (auto *NameVar : NameVars) {
211     NameStrs.push_back(getPGOFuncNameInitializer(NameVar));
212   }
213   return collectPGOFuncNameStrings(NameStrs, zlib::isAvailable(), Result);
214 }
215
216 int readPGOFuncNameStrings(StringRef NameStrings, InstrProfSymtab &Symtab) {
217   const uint8_t *P = reinterpret_cast<const uint8_t *>(NameStrings.data());
218   const uint8_t *EndP = reinterpret_cast<const uint8_t *>(NameStrings.data() +
219                                                           NameStrings.size());
220   while (P < EndP) {
221     uint32_t N;
222     uint64_t UncompressedSize = decodeULEB128(P, &N);
223     P += N;
224     uint64_t CompressedSize = decodeULEB128(P, &N);
225     P += N;
226     bool isCompressed = (CompressedSize != 0);
227     SmallString<128> UncompressedNameStrings;
228     StringRef NameStrings;
229     if (isCompressed) {
230       StringRef CompressedNameStrings(reinterpret_cast<const char *>(P),
231                                       CompressedSize);
232       if (zlib::uncompress(CompressedNameStrings, UncompressedNameStrings,
233                            UncompressedSize) != zlib::StatusOK)
234         return 1;
235       P += CompressedSize;
236       NameStrings = StringRef(UncompressedNameStrings.data(),
237                               UncompressedNameStrings.size());
238     } else {
239       NameStrings =
240           StringRef(reinterpret_cast<const char *>(P), UncompressedSize);
241       P += UncompressedSize;
242     }
243     // Now parse the name strings.
244     size_t NameStart = 0;
245     bool isLast = false;
246     do {
247       size_t NameStop = NameStrings.find(' ', NameStart);
248       if (NameStop == StringRef::npos)
249         return 1;
250       if (NameStop == NameStrings.size() - 1)
251         isLast = true;
252       StringRef Name = NameStrings.substr(NameStart, NameStop - NameStart);
253       Symtab.addFuncName(Name);
254       if (isLast)
255         break;
256       NameStart = NameStop + 1;
257     } while (true);
258
259     while (P < EndP && *P == 0)
260       P++;
261   }
262   Symtab.finalizeSymtab();
263   return 0;
264 }
265
266 instrprof_error
267 InstrProfValueSiteRecord::mergeValueData(InstrProfValueSiteRecord &Input,
268                                          uint64_t Weight) {
269   this->sortByTargetValues();
270   Input.sortByTargetValues();
271   auto I = ValueData.begin();
272   auto IE = ValueData.end();
273   instrprof_error Result = instrprof_error::success;
274   for (auto J = Input.ValueData.begin(), JE = Input.ValueData.end(); J != JE;
275        ++J) {
276     while (I != IE && I->Value < J->Value)
277       ++I;
278     if (I != IE && I->Value == J->Value) {
279       uint64_t JCount = J->Count;
280       bool Overflowed;
281       if (Weight > 1) {
282         JCount = SaturatingMultiply(JCount, Weight, &Overflowed);
283         if (Overflowed)
284           Result = instrprof_error::counter_overflow;
285       }
286       I->Count = SaturatingAdd(I->Count, JCount, &Overflowed);
287       if (Overflowed)
288         Result = instrprof_error::counter_overflow;
289       ++I;
290       continue;
291     }
292     ValueData.insert(I, *J);
293   }
294   return Result;
295 }
296
297 // Merge Value Profile data from Src record to this record for ValueKind.
298 // Scale merged value counts by \p Weight.
299 instrprof_error InstrProfRecord::mergeValueProfData(uint32_t ValueKind,
300                                                     InstrProfRecord &Src,
301                                                     uint64_t Weight) {
302   uint32_t ThisNumValueSites = getNumValueSites(ValueKind);
303   uint32_t OtherNumValueSites = Src.getNumValueSites(ValueKind);
304   if (ThisNumValueSites != OtherNumValueSites)
305     return instrprof_error::value_site_count_mismatch;
306   std::vector<InstrProfValueSiteRecord> &ThisSiteRecords =
307       getValueSitesForKind(ValueKind);
308   std::vector<InstrProfValueSiteRecord> &OtherSiteRecords =
309       Src.getValueSitesForKind(ValueKind);
310   instrprof_error Result = instrprof_error::success;
311   for (uint32_t I = 0; I < ThisNumValueSites; I++)
312     MergeResult(Result,
313                 ThisSiteRecords[I].mergeValueData(OtherSiteRecords[I], Weight));
314   return Result;
315 }
316
317 instrprof_error InstrProfRecord::merge(InstrProfRecord &Other,
318                                        uint64_t Weight) {
319   // If the number of counters doesn't match we either have bad data
320   // or a hash collision.
321   if (Counts.size() != Other.Counts.size())
322     return instrprof_error::count_mismatch;
323
324   instrprof_error Result = instrprof_error::success;
325
326   for (size_t I = 0, E = Other.Counts.size(); I < E; ++I) {
327     bool Overflowed;
328     uint64_t OtherCount = Other.Counts[I];
329     if (Weight > 1) {
330       OtherCount = SaturatingMultiply(OtherCount, Weight, &Overflowed);
331       if (Overflowed)
332         Result = instrprof_error::counter_overflow;
333     }
334     Counts[I] = SaturatingAdd(Counts[I], OtherCount, &Overflowed);
335     if (Overflowed)
336       Result = instrprof_error::counter_overflow;
337   }
338
339   for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
340     MergeResult(Result, mergeValueProfData(Kind, Other, Weight));
341
342   return Result;
343 }
344
345 // Map indirect call target name hash to name string.
346 uint64_t InstrProfRecord::remapValue(uint64_t Value, uint32_t ValueKind,
347                                      ValueMapType *ValueMap) {
348   if (!ValueMap)
349     return Value;
350   switch (ValueKind) {
351   case IPVK_IndirectCallTarget: {
352     auto Result =
353         std::lower_bound(ValueMap->begin(), ValueMap->end(), Value,
354                          [](const std::pair<uint64_t, uint64_t> &LHS,
355                             uint64_t RHS) { return LHS.first < RHS; });
356     if (Result != ValueMap->end())
357       Value = (uint64_t)Result->second;
358     break;
359   }
360   }
361   return Value;
362 }
363
364 void InstrProfRecord::addValueData(uint32_t ValueKind, uint32_t Site,
365                                    InstrProfValueData *VData, uint32_t N,
366                                    ValueMapType *ValueMap) {
367   for (uint32_t I = 0; I < N; I++) {
368     VData[I].Value = remapValue(VData[I].Value, ValueKind, ValueMap);
369   }
370   std::vector<InstrProfValueSiteRecord> &ValueSites =
371       getValueSitesForKind(ValueKind);
372   if (N == 0)
373     ValueSites.push_back(InstrProfValueSiteRecord());
374   else
375     ValueSites.emplace_back(VData, VData + N);
376 }
377
378 #define INSTR_PROF_COMMON_API_IMPL
379 #include "llvm/ProfileData/InstrProfData.inc"
380
381 /*!
382  * \brief ValueProfRecordClosure Interface implementation for  InstrProfRecord
383  *  class. These C wrappers are used as adaptors so that C++ code can be
384  *  invoked as callbacks.
385  */
386 uint32_t getNumValueKindsInstrProf(const void *Record) {
387   return reinterpret_cast<const InstrProfRecord *>(Record)->getNumValueKinds();
388 }
389
390 uint32_t getNumValueSitesInstrProf(const void *Record, uint32_t VKind) {
391   return reinterpret_cast<const InstrProfRecord *>(Record)
392       ->getNumValueSites(VKind);
393 }
394
395 uint32_t getNumValueDataInstrProf(const void *Record, uint32_t VKind) {
396   return reinterpret_cast<const InstrProfRecord *>(Record)
397       ->getNumValueData(VKind);
398 }
399
400 uint32_t getNumValueDataForSiteInstrProf(const void *R, uint32_t VK,
401                                          uint32_t S) {
402   return reinterpret_cast<const InstrProfRecord *>(R)
403       ->getNumValueDataForSite(VK, S);
404 }
405
406 void getValueForSiteInstrProf(const void *R, InstrProfValueData *Dst,
407                               uint32_t K, uint32_t S,
408                               uint64_t (*Mapper)(uint32_t, uint64_t)) {
409   return reinterpret_cast<const InstrProfRecord *>(R)->getValueForSite(
410       Dst, K, S, Mapper);
411 }
412
413 ValueProfData *allocValueProfDataInstrProf(size_t TotalSizeInBytes) {
414   ValueProfData *VD =
415       (ValueProfData *)(new (::operator new(TotalSizeInBytes)) ValueProfData());
416   memset(VD, 0, TotalSizeInBytes);
417   return VD;
418 }
419
420 static ValueProfRecordClosure InstrProfRecordClosure = {
421     0,
422     getNumValueKindsInstrProf,
423     getNumValueSitesInstrProf,
424     getNumValueDataInstrProf,
425     getNumValueDataForSiteInstrProf,
426     0,
427     getValueForSiteInstrProf,
428     allocValueProfDataInstrProf};
429
430 // Wrapper implementation using the closure mechanism.
431 uint32_t ValueProfData::getSize(const InstrProfRecord &Record) {
432   InstrProfRecordClosure.Record = &Record;
433   return getValueProfDataSize(&InstrProfRecordClosure);
434 }
435
436 // Wrapper implementation using the closure mechanism.
437 std::unique_ptr<ValueProfData>
438 ValueProfData::serializeFrom(const InstrProfRecord &Record) {
439   InstrProfRecordClosure.Record = &Record;
440
441   std::unique_ptr<ValueProfData> VPD(
442       serializeValueProfDataFrom(&InstrProfRecordClosure, nullptr));
443   return VPD;
444 }
445
446 void ValueProfRecord::deserializeTo(InstrProfRecord &Record,
447                                     InstrProfRecord::ValueMapType *VMap) {
448   Record.reserveSites(Kind, NumValueSites);
449
450   InstrProfValueData *ValueData = getValueProfRecordValueData(this);
451   for (uint64_t VSite = 0; VSite < NumValueSites; ++VSite) {
452     uint8_t ValueDataCount = this->SiteCountArray[VSite];
453     Record.addValueData(Kind, VSite, ValueData, ValueDataCount, VMap);
454     ValueData += ValueDataCount;
455   }
456 }
457
458 // For writing/serializing,  Old is the host endianness, and  New is
459 // byte order intended on disk. For Reading/deserialization, Old
460 // is the on-disk source endianness, and New is the host endianness.
461 void ValueProfRecord::swapBytes(support::endianness Old,
462                                 support::endianness New) {
463   using namespace support;
464   if (Old == New)
465     return;
466
467   if (getHostEndianness() != Old) {
468     sys::swapByteOrder<uint32_t>(NumValueSites);
469     sys::swapByteOrder<uint32_t>(Kind);
470   }
471   uint32_t ND = getValueProfRecordNumValueData(this);
472   InstrProfValueData *VD = getValueProfRecordValueData(this);
473
474   // No need to swap byte array: SiteCountArrray.
475   for (uint32_t I = 0; I < ND; I++) {
476     sys::swapByteOrder<uint64_t>(VD[I].Value);
477     sys::swapByteOrder<uint64_t>(VD[I].Count);
478   }
479   if (getHostEndianness() == Old) {
480     sys::swapByteOrder<uint32_t>(NumValueSites);
481     sys::swapByteOrder<uint32_t>(Kind);
482   }
483 }
484
485 void ValueProfData::deserializeTo(InstrProfRecord &Record,
486                                   InstrProfRecord::ValueMapType *VMap) {
487   if (NumValueKinds == 0)
488     return;
489
490   ValueProfRecord *VR = getFirstValueProfRecord(this);
491   for (uint32_t K = 0; K < NumValueKinds; K++) {
492     VR->deserializeTo(Record, VMap);
493     VR = getValueProfRecordNext(VR);
494   }
495 }
496
497 template <class T>
498 static T swapToHostOrder(const unsigned char *&D, support::endianness Orig) {
499   using namespace support;
500   if (Orig == little)
501     return endian::readNext<T, little, unaligned>(D);
502   else
503     return endian::readNext<T, big, unaligned>(D);
504 }
505
506 static std::unique_ptr<ValueProfData> allocValueProfData(uint32_t TotalSize) {
507   return std::unique_ptr<ValueProfData>(new (::operator new(TotalSize))
508                                             ValueProfData());
509 }
510
511 instrprof_error ValueProfData::checkIntegrity() {
512   if (NumValueKinds > IPVK_Last + 1)
513     return instrprof_error::malformed;
514   // Total size needs to be mulltiple of quadword size.
515   if (TotalSize % sizeof(uint64_t))
516     return instrprof_error::malformed;
517
518   ValueProfRecord *VR = getFirstValueProfRecord(this);
519   for (uint32_t K = 0; K < this->NumValueKinds; K++) {
520     if (VR->Kind > IPVK_Last)
521       return instrprof_error::malformed;
522     VR = getValueProfRecordNext(VR);
523     if ((char *)VR - (char *)this > (ptrdiff_t)TotalSize)
524       return instrprof_error::malformed;
525   }
526   return instrprof_error::success;
527 }
528
529 ErrorOr<std::unique_ptr<ValueProfData>>
530 ValueProfData::getValueProfData(const unsigned char *D,
531                                 const unsigned char *const BufferEnd,
532                                 support::endianness Endianness) {
533   using namespace support;
534   if (D + sizeof(ValueProfData) > BufferEnd)
535     return instrprof_error::truncated;
536
537   const unsigned char *Header = D;
538   uint32_t TotalSize = swapToHostOrder<uint32_t>(Header, Endianness);
539   if (D + TotalSize > BufferEnd)
540     return instrprof_error::too_large;
541
542   std::unique_ptr<ValueProfData> VPD = allocValueProfData(TotalSize);
543   memcpy(VPD.get(), D, TotalSize);
544   // Byte swap.
545   VPD->swapBytesToHost(Endianness);
546
547   instrprof_error EC = VPD->checkIntegrity();
548   if (EC != instrprof_error::success)
549     return EC;
550
551   return std::move(VPD);
552 }
553
554 void ValueProfData::swapBytesToHost(support::endianness Endianness) {
555   using namespace support;
556   if (Endianness == getHostEndianness())
557     return;
558
559   sys::swapByteOrder<uint32_t>(TotalSize);
560   sys::swapByteOrder<uint32_t>(NumValueKinds);
561
562   ValueProfRecord *VR = getFirstValueProfRecord(this);
563   for (uint32_t K = 0; K < NumValueKinds; K++) {
564     VR->swapBytes(Endianness, getHostEndianness());
565     VR = getValueProfRecordNext(VR);
566   }
567 }
568
569 void ValueProfData::swapBytesFromHost(support::endianness Endianness) {
570   using namespace support;
571   if (Endianness == getHostEndianness())
572     return;
573
574   ValueProfRecord *VR = getFirstValueProfRecord(this);
575   for (uint32_t K = 0; K < NumValueKinds; K++) {
576     ValueProfRecord *NVR = getValueProfRecordNext(VR);
577     VR->swapBytes(getHostEndianness(), Endianness);
578     VR = NVR;
579   }
580   sys::swapByteOrder<uint32_t>(TotalSize);
581   sys::swapByteOrder<uint32_t>(NumValueKinds);
582 }
583
584 }