llvm-project

1
//=-- SampleProf.cpp - Sample profiling format support --------------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file contains common definitions used in the reading and writing of
10
// sample profile data.
11
//
12
//===----------------------------------------------------------------------===//
13

14
#include "llvm/ProfileData/SampleProf.h"
15
#include "llvm/Config/llvm-config.h"
16
#include "llvm/IR/DebugInfoMetadata.h"
17
#include "llvm/IR/PseudoProbe.h"
18
#include "llvm/ProfileData/SampleProfReader.h"
19
#include "llvm/Support/CommandLine.h"
20
#include "llvm/Support/Compiler.h"
21
#include "llvm/Support/Debug.h"
22
#include "llvm/Support/ErrorHandling.h"
23
#include "llvm/Support/raw_ostream.h"
24
#include <string>
25
#include <system_error>
26

27
using namespace llvm;
28
using namespace sampleprof;
29

30
static cl::opt<uint64_t> ProfileSymbolListCutOff(
31
    "profile-symbol-list-cutoff", cl::Hidden, cl::init(-1),
32
    cl::desc("Cutoff value about how many symbols in profile symbol list "
33
             "will be used. This is very useful for performance debugging"));
34

35
static cl::opt<bool> GenerateMergedBaseProfiles(
36
    "generate-merged-base-profiles",
37
    cl::desc("When generating nested context-sensitive profiles, always "
38
             "generate extra base profile for function with all its context "
39
             "profiles merged into it."));
40

41
namespace llvm {
42
namespace sampleprof {
43
bool FunctionSamples::ProfileIsProbeBased = false;
44
bool FunctionSamples::ProfileIsCS = false;
45
bool FunctionSamples::ProfileIsPreInlined = false;
46
bool FunctionSamples::UseMD5 = false;
47
bool FunctionSamples::HasUniqSuffix = true;
48
bool FunctionSamples::ProfileIsFS = false;
49
} // namespace sampleprof
50
} // namespace llvm
51

52
namespace {
53

54
// FIXME: This class is only here to support the transition to llvm::Error. It
55
// will be removed once this transition is complete. Clients should prefer to
56
// deal with the Error value directly, rather than converting to error_code.
57
class SampleProfErrorCategoryType : public std::error_category {
58
  const char *name() const noexcept override { return "llvm.sampleprof"; }
59

60
  std::string message(int IE) const override {
61
    sampleprof_error E = static_cast<sampleprof_error>(IE);
62
    switch (E) {
63
    case sampleprof_error::success:
64
      return "Success";
65
    case sampleprof_error::bad_magic:
66
      return "Invalid sample profile data (bad magic)";
67
    case sampleprof_error::unsupported_version:
68
      return "Unsupported sample profile format version";
69
    case sampleprof_error::too_large:
70
      return "Too much profile data";
71
    case sampleprof_error::truncated:
72
      return "Truncated profile data";
73
    case sampleprof_error::malformed:
74
      return "Malformed sample profile data";
75
    case sampleprof_error::unrecognized_format:
76
      return "Unrecognized sample profile encoding format";
77
    case sampleprof_error::unsupported_writing_format:
78
      return "Profile encoding format unsupported for writing operations";
79
    case sampleprof_error::truncated_name_table:
80
      return "Truncated function name table";
81
    case sampleprof_error::not_implemented:
82
      return "Unimplemented feature";
83
    case sampleprof_error::counter_overflow:
84
      return "Counter overflow";
85
    case sampleprof_error::ostream_seek_unsupported:
86
      return "Ostream does not support seek";
87
    case sampleprof_error::uncompress_failed:
88
      return "Uncompress failure";
89
    case sampleprof_error::zlib_unavailable:
90
      return "Zlib is unavailable";
91
    case sampleprof_error::hash_mismatch:
92
      return "Function hash mismatch";
93
    }
94
    llvm_unreachable("A value of sampleprof_error has no message.");
95
  }
96
};
97

98
} // end anonymous namespace
99

100
const std::error_category &llvm::sampleprof_category() {
101
  static SampleProfErrorCategoryType ErrorCategory;
102
  return ErrorCategory;
103
}
104

105
void LineLocation::print(raw_ostream &OS) const {
106
  OS << LineOffset;
107
  if (Discriminator > 0)
108
    OS << "." << Discriminator;
109
}
110

111
raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,
112
                                          const LineLocation &Loc) {
113
  Loc.print(OS);
114
  return OS;
115
}
116

117
/// Merge the samples in \p Other into this record.
118
/// Optionally scale sample counts by \p Weight.
119
sampleprof_error SampleRecord::merge(const SampleRecord &Other,
120
                                     uint64_t Weight) {
121
  sampleprof_error Result;
122
  Result = addSamples(Other.getSamples(), Weight);
123
  for (const auto &I : Other.getCallTargets()) {
124
    mergeSampleProfErrors(Result, addCalledTarget(I.first, I.second, Weight));
125
  }
126
  return Result;
127
}
128

129
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
130
LLVM_DUMP_METHOD void LineLocation::dump() const { print(dbgs()); }
131
#endif
132

133
/// Print the sample record to the stream \p OS indented by \p Indent.
134
void SampleRecord::print(raw_ostream &OS, unsigned Indent) const {
135
  OS << NumSamples;
136
  if (hasCalls()) {
137
    OS << ", calls:";
138
    for (const auto &I : getSortedCallTargets())
139
      OS << " " << I.first << ":" << I.second;
140
  }
141
  OS << "\n";
142
}
143

144
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
145
LLVM_DUMP_METHOD void SampleRecord::dump() const { print(dbgs(), 0); }
146
#endif
147

148
raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,
149
                                          const SampleRecord &Sample) {
150
  Sample.print(OS, 0);
151
  return OS;
152
}
153

154
/// Print the samples collected for a function on stream \p OS.
155
void FunctionSamples::print(raw_ostream &OS, unsigned Indent) const {
156
  if (getFunctionHash())
157
    OS << "CFG checksum " << getFunctionHash() << "\n";
158

159
  OS << TotalSamples << ", " << TotalHeadSamples << ", " << BodySamples.size()
160
     << " sampled lines\n";
161

162
  OS.indent(Indent);
163
  if (!BodySamples.empty()) {
164
    OS << "Samples collected in the function's body {\n";
165
    SampleSorter<LineLocation, SampleRecord> SortedBodySamples(BodySamples);
166
    for (const auto &SI : SortedBodySamples.get()) {
167
      OS.indent(Indent + 2);
168
      OS << SI->first << ": " << SI->second;
169
    }
170
    OS.indent(Indent);
171
    OS << "}\n";
172
  } else {
173
    OS << "No samples collected in the function's body\n";
174
  }
175

176
  OS.indent(Indent);
177
  if (!CallsiteSamples.empty()) {
178
    OS << "Samples collected in inlined callsites {\n";
179
    SampleSorter<LineLocation, FunctionSamplesMap> SortedCallsiteSamples(
180
        CallsiteSamples);
181
    for (const auto &CS : SortedCallsiteSamples.get()) {
182
      for (const auto &FS : CS->second) {
183
        OS.indent(Indent + 2);
184
        OS << CS->first << ": inlined callee: " << FS.second.getFunction()
185
           << ": ";
186
        FS.second.print(OS, Indent + 4);
187
      }
188
    }
189
    OS.indent(Indent);
190
    OS << "}\n";
191
  } else {
192
    OS << "No inlined callsites in this function\n";
193
  }
194
}
195

196
raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,
197
                                          const FunctionSamples &FS) {
198
  FS.print(OS);
199
  return OS;
200
}
201

202
void sampleprof::sortFuncProfiles(
203
    const SampleProfileMap &ProfileMap,
204
    std::vector<NameFunctionSamples> &SortedProfiles) {
205
  for (const auto &I : ProfileMap) {
206
    SortedProfiles.push_back(std::make_pair(I.first, &I.second));
207
  }
208
  llvm::stable_sort(SortedProfiles, [](const NameFunctionSamples &A,
209
                                       const NameFunctionSamples &B) {
210
    if (A.second->getTotalSamples() == B.second->getTotalSamples())
211
      return A.second->getContext() < B.second->getContext();
212
    return A.second->getTotalSamples() > B.second->getTotalSamples();
213
  });
214
}
215

216
unsigned FunctionSamples::getOffset(const DILocation *DIL) {
217
  return (DIL->getLine() - DIL->getScope()->getSubprogram()->getLine()) &
218
      0xffff;
219
}
220

221
LineLocation FunctionSamples::getCallSiteIdentifier(const DILocation *DIL,
222
                                                    bool ProfileIsFS) {
223
  if (FunctionSamples::ProfileIsProbeBased) {
224
    // In a pseudo-probe based profile, a callsite is simply represented by the
225
    // ID of the probe associated with the call instruction. The probe ID is
226
    // encoded in the Discriminator field of the call instruction's debug
227
    // metadata.
228
    return LineLocation(PseudoProbeDwarfDiscriminator::extractProbeIndex(
229
                            DIL->getDiscriminator()),
230
                        0);
231
  } else {
232
    unsigned Discriminator =
233
        ProfileIsFS ? DIL->getDiscriminator() : DIL->getBaseDiscriminator();
234
    return LineLocation(FunctionSamples::getOffset(DIL), Discriminator);
235
  }
236
}
237

238
const FunctionSamples *FunctionSamples::findFunctionSamples(
239
    const DILocation *DIL, SampleProfileReaderItaniumRemapper *Remapper) const {
240
  assert(DIL);
241
  SmallVector<std::pair<LineLocation, StringRef>, 10> S;
242

243
  const DILocation *PrevDIL = DIL;
244
  for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {
245
    // Use C++ linkage name if possible.
246
    StringRef Name = PrevDIL->getScope()->getSubprogram()->getLinkageName();
247
    if (Name.empty())
248
      Name = PrevDIL->getScope()->getSubprogram()->getName();
249
    S.emplace_back(FunctionSamples::getCallSiteIdentifier(
250
                       DIL, FunctionSamples::ProfileIsFS),
251
                   Name);
252
    PrevDIL = DIL;
253
  }
254

255
  if (S.size() == 0)
256
    return this;
257
  const FunctionSamples *FS = this;
258
  for (int i = S.size() - 1; i >= 0 && FS != nullptr; i--) {
259
    FS = FS->findFunctionSamplesAt(S[i].first, S[i].second, Remapper);
260
  }
261
  return FS;
262
}
263

264
void FunctionSamples::findAllNames(DenseSet<FunctionId> &NameSet) const {
265
  NameSet.insert(getFunction());
266
  for (const auto &BS : BodySamples)
267
    for (const auto &TS : BS.second.getCallTargets())
268
      NameSet.insert(TS.first);
269

270
  for (const auto &CS : CallsiteSamples) {
271
    for (const auto &NameFS : CS.second) {
272
      NameSet.insert(NameFS.first);
273
      NameFS.second.findAllNames(NameSet);
274
    }
275
  }
276
}
277

278
const FunctionSamples *FunctionSamples::findFunctionSamplesAt(
279
    const LineLocation &Loc, StringRef CalleeName,
280
    SampleProfileReaderItaniumRemapper *Remapper) const {
281
  CalleeName = getCanonicalFnName(CalleeName);
282

283
  auto iter = CallsiteSamples.find(mapIRLocToProfileLoc(Loc));
284
  if (iter == CallsiteSamples.end())
285
    return nullptr;
286
  auto FS = iter->second.find(getRepInFormat(CalleeName));
287
  if (FS != iter->second.end())
288
    return &FS->second;
289
  if (Remapper) {
290
    if (auto NameInProfile = Remapper->lookUpNameInProfile(CalleeName)) {
291
      auto FS = iter->second.find(getRepInFormat(*NameInProfile));
292
      if (FS != iter->second.end())
293
        return &FS->second;
294
    }
295
  }
296
  // If we cannot find exact match of the callee name, return the FS with
297
  // the max total count. Only do this when CalleeName is not provided,
298
  // i.e., only for indirect calls.
299
  if (!CalleeName.empty())
300
    return nullptr;
301
  uint64_t MaxTotalSamples = 0;
302
  const FunctionSamples *R = nullptr;
303
  for (const auto &NameFS : iter->second)
304
    if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
305
      MaxTotalSamples = NameFS.second.getTotalSamples();
306
      R = &NameFS.second;
307
    }
308
  return R;
309
}
310

311
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
312
LLVM_DUMP_METHOD void FunctionSamples::dump() const { print(dbgs(), 0); }
313
#endif
314

315
std::error_code ProfileSymbolList::read(const uint8_t *Data,
316
                                        uint64_t ListSize) {
317
  const char *ListStart = reinterpret_cast<const char *>(Data);
318
  uint64_t Size = 0;
319
  uint64_t StrNum = 0;
320
  while (Size < ListSize && StrNum < ProfileSymbolListCutOff) {
321
    StringRef Str(ListStart + Size);
322
    add(Str);
323
    Size += Str.size() + 1;
324
    StrNum++;
325
  }
326
  if (Size != ListSize && StrNum != ProfileSymbolListCutOff)
327
    return sampleprof_error::malformed;
328
  return sampleprof_error::success;
329
}
330

331
void SampleContextTrimmer::trimAndMergeColdContextProfiles(
332
    uint64_t ColdCountThreshold, bool TrimColdContext, bool MergeColdContext,
333
    uint32_t ColdContextFrameLength, bool TrimBaseProfileOnly) {
334
  if (!TrimColdContext && !MergeColdContext)
335
    return;
336

337
  // Nothing to merge if sample threshold is zero
338
  if (ColdCountThreshold == 0)
339
    return;
340

341
  // Trimming base profiles only is mainly to honor the preinliner decsion. When
342
  // MergeColdContext is true preinliner decsion is not honored anyway so turn
343
  // off TrimBaseProfileOnly.
344
  if (MergeColdContext)
345
    TrimBaseProfileOnly = false;
346

347
  // Filter the cold profiles from ProfileMap and move them into a tmp
348
  // container
349
  std::vector<std::pair<hash_code, const FunctionSamples *>> ColdProfiles;
350
  for (const auto &I : ProfileMap) {
351
    const SampleContext &Context = I.second.getContext();
352
    const FunctionSamples &FunctionProfile = I.second;
353
    if (FunctionProfile.getTotalSamples() < ColdCountThreshold &&
354
        (!TrimBaseProfileOnly || Context.isBaseContext()))
355
      ColdProfiles.emplace_back(I.first, &I.second);
356
  }
357

358
  // Remove the cold profile from ProfileMap and merge them into
359
  // MergedProfileMap by the last K frames of context
360
  SampleProfileMap MergedProfileMap;
361
  for (const auto &I : ColdProfiles) {
362
    if (MergeColdContext) {
363
      auto MergedContext = I.second->getContext().getContextFrames();
364
      if (ColdContextFrameLength < MergedContext.size())
365
        MergedContext = MergedContext.take_back(ColdContextFrameLength);
366
      // Need to set MergedProfile's context here otherwise it will be lost.
367
      FunctionSamples &MergedProfile = MergedProfileMap.create(MergedContext);
368
      MergedProfile.merge(*I.second);
369
    }
370
    ProfileMap.erase(I.first);
371
  }
372

373
  // Move the merged profiles into ProfileMap;
374
  for (const auto &I : MergedProfileMap) {
375
    // Filter the cold merged profile
376
    if (TrimColdContext && I.second.getTotalSamples() < ColdCountThreshold &&
377
        ProfileMap.find(I.second.getContext()) == ProfileMap.end())
378
      continue;
379
    // Merge the profile if the original profile exists, otherwise just insert
380
    // as a new profile. If inserted as a new profile from MergedProfileMap, it
381
    // already has the right context.
382
    auto Ret = ProfileMap.emplace(I.second.getContext(), FunctionSamples());
383
    FunctionSamples &OrigProfile = Ret.first->second;
384
    OrigProfile.merge(I.second);
385
  }
386
}
387

388
std::error_code ProfileSymbolList::write(raw_ostream &OS) {
389
  // Sort the symbols before output. If doing compression.
390
  // It will make the compression much more effective.
391
  std::vector<StringRef> SortedList(Syms.begin(), Syms.end());
392
  llvm::sort(SortedList);
393

394
  std::string OutputString;
395
  for (auto &Sym : SortedList) {
396
    OutputString.append(Sym.str());
397
    OutputString.append(1, '\0');
398
  }
399

400
  OS << OutputString;
401
  return sampleprof_error::success;
402
}
403

404
void ProfileSymbolList::dump(raw_ostream &OS) const {
405
  OS << "======== Dump profile symbol list ========\n";
406
  std::vector<StringRef> SortedList(Syms.begin(), Syms.end());
407
  llvm::sort(SortedList);
408

409
  for (auto &Sym : SortedList)
410
    OS << Sym << "\n";
411
}
412

413
ProfileConverter::FrameNode *
414
ProfileConverter::FrameNode::getOrCreateChildFrame(const LineLocation &CallSite,
415
                                                   FunctionId CalleeName) {
416
  uint64_t Hash = FunctionSamples::getCallSiteHash(CalleeName, CallSite);
417
  auto It = AllChildFrames.find(Hash);
418
  if (It != AllChildFrames.end()) {
419
    assert(It->second.FuncName == CalleeName &&
420
           "Hash collision for child context node");
421
    return &It->second;
422
  }
423

424
  AllChildFrames[Hash] = FrameNode(CalleeName, nullptr, CallSite);
425
  return &AllChildFrames[Hash];
426
}
427

428
ProfileConverter::ProfileConverter(SampleProfileMap &Profiles)
429
    : ProfileMap(Profiles) {
430
  for (auto &FuncSample : Profiles) {
431
    FunctionSamples *FSamples = &FuncSample.second;
432
    auto *NewNode = getOrCreateContextPath(FSamples->getContext());
433
    assert(!NewNode->FuncSamples && "New node cannot have sample profile");
434
    NewNode->FuncSamples = FSamples;
435
  }
436
}
437

438
ProfileConverter::FrameNode *
439
ProfileConverter::getOrCreateContextPath(const SampleContext &Context) {
440
  auto Node = &RootFrame;
441
  LineLocation CallSiteLoc(0, 0);
442
  for (auto &Callsite : Context.getContextFrames()) {
443
    Node = Node->getOrCreateChildFrame(CallSiteLoc, Callsite.Func);
444
    CallSiteLoc = Callsite.Location;
445
  }
446
  return Node;
447
}
448

449
void ProfileConverter::convertCSProfiles(ProfileConverter::FrameNode &Node) {
450
  // Process each child profile. Add each child profile to callsite profile map
451
  // of the current node `Node` if `Node` comes with a profile. Otherwise
452
  // promote the child profile to a standalone profile.
453
  auto *NodeProfile = Node.FuncSamples;
454
  for (auto &It : Node.AllChildFrames) {
455
    auto &ChildNode = It.second;
456
    convertCSProfiles(ChildNode);
457
    auto *ChildProfile = ChildNode.FuncSamples;
458
    if (!ChildProfile)
459
      continue;
460
    SampleContext OrigChildContext = ChildProfile->getContext();
461
    uint64_t OrigChildContextHash = OrigChildContext.getHashCode();
462
    // Reset the child context to be contextless.
463
    ChildProfile->getContext().setFunction(OrigChildContext.getFunction());
464
    if (NodeProfile) {
465
      // Add child profile to the callsite profile map.
466
      auto &SamplesMap = NodeProfile->functionSamplesAt(ChildNode.CallSiteLoc);
467
      SamplesMap.emplace(OrigChildContext.getFunction(), *ChildProfile);
468
      NodeProfile->addTotalSamples(ChildProfile->getTotalSamples());
469
      // Remove the corresponding body sample for the callsite and update the
470
      // total weight.
471
      auto Count = NodeProfile->removeCalledTargetAndBodySample(
472
          ChildNode.CallSiteLoc.LineOffset, ChildNode.CallSiteLoc.Discriminator,
473
          OrigChildContext.getFunction());
474
      NodeProfile->removeTotalSamples(Count);
475
    }
476

477
    uint64_t NewChildProfileHash = 0;
478
    // Separate child profile to be a standalone profile, if the current parent
479
    // profile doesn't exist. This is a duplicating operation when the child
480
    // profile is already incorporated into the parent which is still useful and
481
    // thus done optionally. It is seen that duplicating context profiles into
482
    // base profiles improves the code quality for thinlto build by allowing a
483
    // profile in the prelink phase for to-be-fully-inlined functions.
484
    if (!NodeProfile) {
485
      ProfileMap[ChildProfile->getContext()].merge(*ChildProfile);
486
      NewChildProfileHash = ChildProfile->getContext().getHashCode();
487
    } else if (GenerateMergedBaseProfiles) {
488
      ProfileMap[ChildProfile->getContext()].merge(*ChildProfile);
489
      NewChildProfileHash = ChildProfile->getContext().getHashCode();
490
      auto &SamplesMap = NodeProfile->functionSamplesAt(ChildNode.CallSiteLoc);
491
      SamplesMap[ChildProfile->getFunction()].getContext().setAttribute(
492
          ContextDuplicatedIntoBase);
493
    }
494

495
    // Remove the original child profile. Check if MD5 of new child profile
496
    // collides with old profile, in this case the [] operator already
497
    // overwritten it without the need of erase.
498
    if (NewChildProfileHash != OrigChildContextHash)
499
      ProfileMap.erase(OrigChildContextHash);
500
  }
501
}
502

503
void ProfileConverter::convertCSProfiles() { convertCSProfiles(RootFrame); }
504