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