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 MergeResult(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