[PGO]: Implement Func PGO name string compression
[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 int collectPGOFuncNameStrings(const std::vector<GlobalVariable *> &NameVars,
201                               std::string &Result) {
202   std::vector<std::string> NameStrs;
203   for (auto *NameVar : NameVars) {
204     auto *Arr = cast<ConstantDataArray>(NameVar->getInitializer());
205     StringRef NameStr =
206         Arr->isCString() ? Arr->getAsCString() : Arr->getAsString();
207     NameStrs.push_back(NameStr.str());
208   }
209   return collectPGOFuncNameStrings(NameStrs, zlib::isAvailable(), Result);
210 }
211
212 int readPGOFuncNameStrings(StringRef NameStrings, InstrProfSymtab &Symtab) {
213   const uint8_t *P = reinterpret_cast<const uint8_t *>(NameStrings.data());
214   const uint8_t *EndP = reinterpret_cast<const uint8_t *>(NameStrings.data() +
215                                                           NameStrings.size());
216   while (P < EndP) {
217     uint32_t N;
218     uint64_t UncompressedSize = decodeULEB128(P, &N);
219     P += N;
220     uint64_t CompressedSize = decodeULEB128(P, &N);
221     P += N;
222     bool isCompressed = (CompressedSize != 0);
223     SmallString<128> UncompressedNameStrings;
224     StringRef NameStrings;
225     if (isCompressed) {
226       StringRef CompressedNameStrings(reinterpret_cast<const char *>(P),
227                                       CompressedSize);
228       if (zlib::uncompress(CompressedNameStrings, UncompressedNameStrings,
229                            UncompressedSize) != zlib::StatusOK)
230         return 1;
231       P += CompressedSize;
232       NameStrings = StringRef(UncompressedNameStrings.data(),
233                               UncompressedNameStrings.size());
234     } else {
235       NameStrings =
236           StringRef(reinterpret_cast<const char *>(P), UncompressedSize);
237       P += UncompressedSize;
238     }
239     // Now parse the name strings.
240     size_t NameStart = 0;
241     bool isLast = false;
242     do {
243       size_t NameStop = NameStrings.find(' ', NameStart);
244       if (NameStop == StringRef::npos)
245         return 1;
246       if (NameStop == NameStrings.size() - 1)
247         isLast = true;
248       StringRef Name = NameStrings.substr(NameStart, NameStop - NameStart);
249       Symtab.addFuncName(Name);
250       if (isLast)
251         break;
252       NameStart = NameStop + 1;
253     } while (true);
254
255     while (P < EndP && *P == 0)
256       P++;
257   }
258   Symtab.finalizeSymtab();
259   return 0;
260 }
261
262 instrprof_error
263 InstrProfValueSiteRecord::mergeValueData(InstrProfValueSiteRecord &Input,
264                                          uint64_t Weight) {
265   this->sortByTargetValues();
266   Input.sortByTargetValues();
267   auto I = ValueData.begin();
268   auto IE = ValueData.end();
269   instrprof_error Result = instrprof_error::success;
270   for (auto J = Input.ValueData.begin(), JE = Input.ValueData.end(); J != JE;
271        ++J) {
272     while (I != IE && I->Value < J->Value)
273       ++I;
274     if (I != IE && I->Value == J->Value) {
275       uint64_t JCount = J->Count;
276       bool Overflowed;
277       if (Weight > 1) {
278         JCount = SaturatingMultiply(JCount, Weight, &Overflowed);
279         if (Overflowed)
280           Result = instrprof_error::counter_overflow;
281       }
282       I->Count = SaturatingAdd(I->Count, JCount, &Overflowed);
283       if (Overflowed)
284         Result = instrprof_error::counter_overflow;
285       ++I;
286       continue;
287     }
288     ValueData.insert(I, *J);
289   }
290   return Result;
291 }
292
293 // Merge Value Profile data from Src record to this record for ValueKind.
294 // Scale merged value counts by \p Weight.
295 instrprof_error InstrProfRecord::mergeValueProfData(uint32_t ValueKind,
296                                                     InstrProfRecord &Src,
297                                                     uint64_t Weight) {
298   uint32_t ThisNumValueSites = getNumValueSites(ValueKind);
299   uint32_t OtherNumValueSites = Src.getNumValueSites(ValueKind);
300   if (ThisNumValueSites != OtherNumValueSites)
301     return instrprof_error::value_site_count_mismatch;
302   std::vector<InstrProfValueSiteRecord> &ThisSiteRecords =
303       getValueSitesForKind(ValueKind);
304   std::vector<InstrProfValueSiteRecord> &OtherSiteRecords =
305       Src.getValueSitesForKind(ValueKind);
306   instrprof_error Result = instrprof_error::success;
307   for (uint32_t I = 0; I < ThisNumValueSites; I++)
308     MergeResult(Result,
309                 ThisSiteRecords[I].mergeValueData(OtherSiteRecords[I], Weight));
310   return Result;
311 }
312
313 instrprof_error InstrProfRecord::merge(InstrProfRecord &Other,
314                                        uint64_t Weight) {
315   // If the number of counters doesn't match we either have bad data
316   // or a hash collision.
317   if (Counts.size() != Other.Counts.size())
318     return instrprof_error::count_mismatch;
319
320   instrprof_error Result = instrprof_error::success;
321
322   for (size_t I = 0, E = Other.Counts.size(); I < E; ++I) {
323     bool Overflowed;
324     uint64_t OtherCount = Other.Counts[I];
325     if (Weight > 1) {
326       OtherCount = SaturatingMultiply(OtherCount, Weight, &Overflowed);
327       if (Overflowed)
328         Result = instrprof_error::counter_overflow;
329     }
330     Counts[I] = SaturatingAdd(Counts[I], OtherCount, &Overflowed);
331     if (Overflowed)
332       Result = instrprof_error::counter_overflow;
333   }
334
335   for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
336     MergeResult(Result, mergeValueProfData(Kind, Other, Weight));
337
338   return Result;
339 }
340
341 // Map indirect call target name hash to name string.
342 uint64_t InstrProfRecord::remapValue(uint64_t Value, uint32_t ValueKind,
343                                      ValueMapType *ValueMap) {
344   if (!ValueMap)
345     return Value;
346   switch (ValueKind) {
347   case IPVK_IndirectCallTarget: {
348     auto Result =
349         std::lower_bound(ValueMap->begin(), ValueMap->end(), Value,
350                          [](const std::pair<uint64_t, uint64_t> &LHS,
351                             uint64_t RHS) { return LHS.first < RHS; });
352     if (Result != ValueMap->end())
353       Value = (uint64_t)Result->second;
354     break;
355   }
356   }
357   return Value;
358 }
359
360 void InstrProfRecord::addValueData(uint32_t ValueKind, uint32_t Site,
361                                    InstrProfValueData *VData, uint32_t N,
362                                    ValueMapType *ValueMap) {
363   for (uint32_t I = 0; I < N; I++) {
364     VData[I].Value = remapValue(VData[I].Value, ValueKind, ValueMap);
365   }
366   std::vector<InstrProfValueSiteRecord> &ValueSites =
367       getValueSitesForKind(ValueKind);
368   if (N == 0)
369     ValueSites.push_back(InstrProfValueSiteRecord());
370   else
371     ValueSites.emplace_back(VData, VData + N);
372 }
373
374 #define INSTR_PROF_COMMON_API_IMPL
375 #include "llvm/ProfileData/InstrProfData.inc"
376
377 /*!
378  * \brief ValueProfRecordClosure Interface implementation for  InstrProfRecord
379  *  class. These C wrappers are used as adaptors so that C++ code can be
380  *  invoked as callbacks.
381  */
382 uint32_t getNumValueKindsInstrProf(const void *Record) {
383   return reinterpret_cast<const InstrProfRecord *>(Record)->getNumValueKinds();
384 }
385
386 uint32_t getNumValueSitesInstrProf(const void *Record, uint32_t VKind) {
387   return reinterpret_cast<const InstrProfRecord *>(Record)
388       ->getNumValueSites(VKind);
389 }
390
391 uint32_t getNumValueDataInstrProf(const void *Record, uint32_t VKind) {
392   return reinterpret_cast<const InstrProfRecord *>(Record)
393       ->getNumValueData(VKind);
394 }
395
396 uint32_t getNumValueDataForSiteInstrProf(const void *R, uint32_t VK,
397                                          uint32_t S) {
398   return reinterpret_cast<const InstrProfRecord *>(R)
399       ->getNumValueDataForSite(VK, S);
400 }
401
402 void getValueForSiteInstrProf(const void *R, InstrProfValueData *Dst,
403                               uint32_t K, uint32_t S,
404                               uint64_t (*Mapper)(uint32_t, uint64_t)) {
405   return reinterpret_cast<const InstrProfRecord *>(R)->getValueForSite(
406       Dst, K, S, Mapper);
407 }
408
409 ValueProfData *allocValueProfDataInstrProf(size_t TotalSizeInBytes) {
410   ValueProfData *VD =
411       (ValueProfData *)(new (::operator new(TotalSizeInBytes)) ValueProfData());
412   memset(VD, 0, TotalSizeInBytes);
413   return VD;
414 }
415
416 static ValueProfRecordClosure InstrProfRecordClosure = {
417     0,
418     getNumValueKindsInstrProf,
419     getNumValueSitesInstrProf,
420     getNumValueDataInstrProf,
421     getNumValueDataForSiteInstrProf,
422     0,
423     getValueForSiteInstrProf,
424     allocValueProfDataInstrProf};
425
426 // Wrapper implementation using the closure mechanism.
427 uint32_t ValueProfData::getSize(const InstrProfRecord &Record) {
428   InstrProfRecordClosure.Record = &Record;
429   return getValueProfDataSize(&InstrProfRecordClosure);
430 }
431
432 // Wrapper implementation using the closure mechanism.
433 std::unique_ptr<ValueProfData>
434 ValueProfData::serializeFrom(const InstrProfRecord &Record) {
435   InstrProfRecordClosure.Record = &Record;
436
437   std::unique_ptr<ValueProfData> VPD(
438       serializeValueProfDataFrom(&InstrProfRecordClosure, nullptr));
439   return VPD;
440 }
441
442 void ValueProfRecord::deserializeTo(InstrProfRecord &Record,
443                                     InstrProfRecord::ValueMapType *VMap) {
444   Record.reserveSites(Kind, NumValueSites);
445
446   InstrProfValueData *ValueData = getValueProfRecordValueData(this);
447   for (uint64_t VSite = 0; VSite < NumValueSites; ++VSite) {
448     uint8_t ValueDataCount = this->SiteCountArray[VSite];
449     Record.addValueData(Kind, VSite, ValueData, ValueDataCount, VMap);
450     ValueData += ValueDataCount;
451   }
452 }
453
454 // For writing/serializing,  Old is the host endianness, and  New is
455 // byte order intended on disk. For Reading/deserialization, Old
456 // is the on-disk source endianness, and New is the host endianness.
457 void ValueProfRecord::swapBytes(support::endianness Old,
458                                 support::endianness New) {
459   using namespace support;
460   if (Old == New)
461     return;
462
463   if (getHostEndianness() != Old) {
464     sys::swapByteOrder<uint32_t>(NumValueSites);
465     sys::swapByteOrder<uint32_t>(Kind);
466   }
467   uint32_t ND = getValueProfRecordNumValueData(this);
468   InstrProfValueData *VD = getValueProfRecordValueData(this);
469
470   // No need to swap byte array: SiteCountArrray.
471   for (uint32_t I = 0; I < ND; I++) {
472     sys::swapByteOrder<uint64_t>(VD[I].Value);
473     sys::swapByteOrder<uint64_t>(VD[I].Count);
474   }
475   if (getHostEndianness() == Old) {
476     sys::swapByteOrder<uint32_t>(NumValueSites);
477     sys::swapByteOrder<uint32_t>(Kind);
478   }
479 }
480
481 void ValueProfData::deserializeTo(InstrProfRecord &Record,
482                                   InstrProfRecord::ValueMapType *VMap) {
483   if (NumValueKinds == 0)
484     return;
485
486   ValueProfRecord *VR = getFirstValueProfRecord(this);
487   for (uint32_t K = 0; K < NumValueKinds; K++) {
488     VR->deserializeTo(Record, VMap);
489     VR = getValueProfRecordNext(VR);
490   }
491 }
492
493 template <class T>
494 static T swapToHostOrder(const unsigned char *&D, support::endianness Orig) {
495   using namespace support;
496   if (Orig == little)
497     return endian::readNext<T, little, unaligned>(D);
498   else
499     return endian::readNext<T, big, unaligned>(D);
500 }
501
502 static std::unique_ptr<ValueProfData> allocValueProfData(uint32_t TotalSize) {
503   return std::unique_ptr<ValueProfData>(new (::operator new(TotalSize))
504                                             ValueProfData());
505 }
506
507 instrprof_error ValueProfData::checkIntegrity() {
508   if (NumValueKinds > IPVK_Last + 1)
509     return instrprof_error::malformed;
510   // Total size needs to be mulltiple of quadword size.
511   if (TotalSize % sizeof(uint64_t))
512     return instrprof_error::malformed;
513
514   ValueProfRecord *VR = getFirstValueProfRecord(this);
515   for (uint32_t K = 0; K < this->NumValueKinds; K++) {
516     if (VR->Kind > IPVK_Last)
517       return instrprof_error::malformed;
518     VR = getValueProfRecordNext(VR);
519     if ((char *)VR - (char *)this > (ptrdiff_t)TotalSize)
520       return instrprof_error::malformed;
521   }
522   return instrprof_error::success;
523 }
524
525 ErrorOr<std::unique_ptr<ValueProfData>>
526 ValueProfData::getValueProfData(const unsigned char *D,
527                                 const unsigned char *const BufferEnd,
528                                 support::endianness Endianness) {
529   using namespace support;
530   if (D + sizeof(ValueProfData) > BufferEnd)
531     return instrprof_error::truncated;
532
533   const unsigned char *Header = D;
534   uint32_t TotalSize = swapToHostOrder<uint32_t>(Header, Endianness);
535   if (D + TotalSize > BufferEnd)
536     return instrprof_error::too_large;
537
538   std::unique_ptr<ValueProfData> VPD = allocValueProfData(TotalSize);
539   memcpy(VPD.get(), D, TotalSize);
540   // Byte swap.
541   VPD->swapBytesToHost(Endianness);
542
543   instrprof_error EC = VPD->checkIntegrity();
544   if (EC != instrprof_error::success)
545     return EC;
546
547   return std::move(VPD);
548 }
549
550 void ValueProfData::swapBytesToHost(support::endianness Endianness) {
551   using namespace support;
552   if (Endianness == getHostEndianness())
553     return;
554
555   sys::swapByteOrder<uint32_t>(TotalSize);
556   sys::swapByteOrder<uint32_t>(NumValueKinds);
557
558   ValueProfRecord *VR = getFirstValueProfRecord(this);
559   for (uint32_t K = 0; K < NumValueKinds; K++) {
560     VR->swapBytes(Endianness, getHostEndianness());
561     VR = getValueProfRecordNext(VR);
562   }
563 }
564
565 void ValueProfData::swapBytesFromHost(support::endianness Endianness) {
566   using namespace support;
567   if (Endianness == getHostEndianness())
568     return;
569
570   ValueProfRecord *VR = getFirstValueProfRecord(this);
571   for (uint32_t K = 0; K < NumValueKinds; K++) {
572     ValueProfRecord *NVR = getValueProfRecordNext(VR);
573     VR->swapBytes(getHostEndianness(), Endianness);
574     VR = NVR;
575   }
576   sys::swapByteOrder<uint32_t>(TotalSize);
577   sys::swapByteOrder<uint32_t>(NumValueKinds);
578 }
579
580 }