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