1 //===- SampleProf.h - Sampling profiling format support ---------*- C++ -*-===// 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 #ifndef LLVM_PROFILEDATA_SAMPLEPROF_H 15 #define LLVM_PROFILEDATA_SAMPLEPROF_H 16 17 #include "llvm/ADT/DenseSet.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/StringMap.h" 20 #include "llvm/ADT/StringRef.h" 21 #include "llvm/IR/Function.h" 22 #include "llvm/IR/GlobalValue.h" 23 #include "llvm/Support/Allocator.h" 24 #include "llvm/Support/Debug.h" 25 #include "llvm/Support/ErrorOr.h" 26 #include "llvm/Support/MathExtras.h" 27 #include <algorithm> 28 #include <cstdint> 29 #include <list> 30 #include <map> 31 #include <set> 32 #include <sstream> 33 #include <string> 34 #include <system_error> 35 #include <unordered_map> 36 #include <utility> 37 38 namespace llvm { 39 40 class DILocation; 41 class raw_ostream; 42 43 const std::error_category &sampleprof_category(); 44 45 enum class sampleprof_error { 46 success = 0, 47 bad_magic, 48 unsupported_version, 49 too_large, 50 truncated, 51 malformed, 52 unrecognized_format, 53 unsupported_writing_format, 54 truncated_name_table, 55 not_implemented, 56 counter_overflow, 57 ostream_seek_unsupported, 58 uncompress_failed, 59 zlib_unavailable, 60 hash_mismatch 61 }; 62 63 inline std::error_code make_error_code(sampleprof_error E) { 64 return std::error_code(static_cast<int>(E), sampleprof_category()); 65 } 66 67 inline sampleprof_error MergeResult(sampleprof_error &Accumulator, 68 sampleprof_error Result) { 69 // Prefer first error encountered as later errors may be secondary effects of 70 // the initial problem. 71 if (Accumulator == sampleprof_error::success && 72 Result != sampleprof_error::success) 73 Accumulator = Result; 74 return Accumulator; 75 } 76 77 } // end namespace llvm 78 79 namespace std { 80 81 template <> 82 struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {}; 83 84 } // end namespace std 85 86 namespace llvm { 87 namespace sampleprof { 88 89 enum SampleProfileFormat { 90 SPF_None = 0, 91 SPF_Text = 0x1, 92 SPF_Compact_Binary = 0x2, 93 SPF_GCC = 0x3, 94 SPF_Ext_Binary = 0x4, 95 SPF_Binary = 0xff 96 }; 97 98 static inline uint64_t SPMagic(SampleProfileFormat Format = SPF_Binary) { 99 return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) | 100 uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) | 101 uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) | 102 uint64_t('2') << (64 - 56) | uint64_t(Format); 103 } 104 105 /// Get the proper representation of a string according to whether the 106 /// current Format uses MD5 to represent the string. 107 static inline StringRef getRepInFormat(StringRef Name, bool UseMD5, 108 std::string &GUIDBuf) { 109 if (Name.empty() || !UseMD5) 110 return Name; 111 GUIDBuf = std::to_string(Function::getGUID(Name)); 112 return GUIDBuf; 113 } 114 115 static inline uint64_t SPVersion() { return 103; } 116 117 // Section Type used by SampleProfileExtBinaryBaseReader and 118 // SampleProfileExtBinaryBaseWriter. Never change the existing 119 // value of enum. Only append new ones. 120 enum SecType { 121 SecInValid = 0, 122 SecProfSummary = 1, 123 SecNameTable = 2, 124 SecProfileSymbolList = 3, 125 SecFuncOffsetTable = 4, 126 SecFuncMetadata = 5, 127 SecCSNameTable = 6, 128 // marker for the first type of profile. 129 SecFuncProfileFirst = 32, 130 SecLBRProfile = SecFuncProfileFirst 131 }; 132 133 static inline std::string getSecName(SecType Type) { 134 switch ((int)Type) { // Avoid -Wcovered-switch-default 135 case SecInValid: 136 return "InvalidSection"; 137 case SecProfSummary: 138 return "ProfileSummarySection"; 139 case SecNameTable: 140 return "NameTableSection"; 141 case SecProfileSymbolList: 142 return "ProfileSymbolListSection"; 143 case SecFuncOffsetTable: 144 return "FuncOffsetTableSection"; 145 case SecFuncMetadata: 146 return "FunctionMetadata"; 147 case SecCSNameTable: 148 return "CSNameTableSection"; 149 case SecLBRProfile: 150 return "LBRProfileSection"; 151 default: 152 return "UnknownSection"; 153 } 154 } 155 156 // Entry type of section header table used by SampleProfileExtBinaryBaseReader 157 // and SampleProfileExtBinaryBaseWriter. 158 struct SecHdrTableEntry { 159 SecType Type; 160 uint64_t Flags; 161 uint64_t Offset; 162 uint64_t Size; 163 // The index indicating the location of the current entry in 164 // SectionHdrLayout table. 165 uint32_t LayoutIndex; 166 }; 167 168 // Flags common for all sections are defined here. In SecHdrTableEntry::Flags, 169 // common flags will be saved in the lower 32bits and section specific flags 170 // will be saved in the higher 32 bits. 171 enum class SecCommonFlags : uint32_t { 172 SecFlagInValid = 0, 173 SecFlagCompress = (1 << 0), 174 // Indicate the section contains only profile without context. 175 SecFlagFlat = (1 << 1) 176 }; 177 178 // Section specific flags are defined here. 179 // !!!Note: Everytime a new enum class is created here, please add 180 // a new check in verifySecFlag. 181 enum class SecNameTableFlags : uint32_t { 182 SecFlagInValid = 0, 183 SecFlagMD5Name = (1 << 0), 184 // Store MD5 in fixed length instead of ULEB128 so NameTable can be 185 // accessed like an array. 186 SecFlagFixedLengthMD5 = (1 << 1), 187 // Profile contains ".__uniq." suffix name. Compiler shouldn't strip 188 // the suffix when doing profile matching when seeing the flag. 189 SecFlagUniqSuffix = (1 << 2) 190 }; 191 enum class SecProfSummaryFlags : uint32_t { 192 SecFlagInValid = 0, 193 /// SecFlagPartial means the profile is for common/shared code. 194 /// The common profile is usually merged from profiles collected 195 /// from running other targets. 196 SecFlagPartial = (1 << 0), 197 /// SecFlagContext means this is context-sensitive flat profile for 198 /// CSSPGO 199 SecFlagFullContext = (1 << 1), 200 /// SecFlagFSDiscriminator means this profile uses flow-sensitive 201 /// discriminators. 202 SecFlagFSDiscriminator = (1 << 2), 203 /// SecFlagIsPreInlined means this profile contains ShouldBeInlined 204 /// contexts thus this is CS preinliner computed. 205 SecFlagIsPreInlined = (1 << 4), 206 }; 207 208 enum class SecFuncMetadataFlags : uint32_t { 209 SecFlagInvalid = 0, 210 SecFlagIsProbeBased = (1 << 0), 211 SecFlagHasAttribute = (1 << 1), 212 }; 213 214 enum class SecFuncOffsetFlags : uint32_t { 215 SecFlagInvalid = 0, 216 // Store function offsets in an order of contexts. The order ensures that 217 // callee contexts of a given context laid out next to it. 218 SecFlagOrdered = (1 << 0), 219 }; 220 221 // Verify section specific flag is used for the correct section. 222 template <class SecFlagType> 223 static inline void verifySecFlag(SecType Type, SecFlagType Flag) { 224 // No verification is needed for common flags. 225 if (std::is_same<SecCommonFlags, SecFlagType>()) 226 return; 227 228 // Verification starts here for section specific flag. 229 bool IsFlagLegal = false; 230 switch (Type) { 231 case SecNameTable: 232 IsFlagLegal = std::is_same<SecNameTableFlags, SecFlagType>(); 233 break; 234 case SecProfSummary: 235 IsFlagLegal = std::is_same<SecProfSummaryFlags, SecFlagType>(); 236 break; 237 case SecFuncMetadata: 238 IsFlagLegal = std::is_same<SecFuncMetadataFlags, SecFlagType>(); 239 break; 240 default: 241 case SecFuncOffsetTable: 242 IsFlagLegal = std::is_same<SecFuncOffsetFlags, SecFlagType>(); 243 break; 244 } 245 if (!IsFlagLegal) 246 llvm_unreachable("Misuse of a flag in an incompatible section"); 247 } 248 249 template <class SecFlagType> 250 static inline void addSecFlag(SecHdrTableEntry &Entry, SecFlagType Flag) { 251 verifySecFlag(Entry.Type, Flag); 252 auto FVal = static_cast<uint64_t>(Flag); 253 bool IsCommon = std::is_same<SecCommonFlags, SecFlagType>(); 254 Entry.Flags |= IsCommon ? FVal : (FVal << 32); 255 } 256 257 template <class SecFlagType> 258 static inline void removeSecFlag(SecHdrTableEntry &Entry, SecFlagType Flag) { 259 verifySecFlag(Entry.Type, Flag); 260 auto FVal = static_cast<uint64_t>(Flag); 261 bool IsCommon = std::is_same<SecCommonFlags, SecFlagType>(); 262 Entry.Flags &= ~(IsCommon ? FVal : (FVal << 32)); 263 } 264 265 template <class SecFlagType> 266 static inline bool hasSecFlag(const SecHdrTableEntry &Entry, SecFlagType Flag) { 267 verifySecFlag(Entry.Type, Flag); 268 auto FVal = static_cast<uint64_t>(Flag); 269 bool IsCommon = std::is_same<SecCommonFlags, SecFlagType>(); 270 return Entry.Flags & (IsCommon ? FVal : (FVal << 32)); 271 } 272 273 /// Represents the relative location of an instruction. 274 /// 275 /// Instruction locations are specified by the line offset from the 276 /// beginning of the function (marked by the line where the function 277 /// header is) and the discriminator value within that line. 278 /// 279 /// The discriminator value is useful to distinguish instructions 280 /// that are on the same line but belong to different basic blocks 281 /// (e.g., the two post-increment instructions in "if (p) x++; else y++;"). 282 struct LineLocation { 283 LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {} 284 285 void print(raw_ostream &OS) const; 286 void dump() const; 287 288 bool operator<(const LineLocation &O) const { 289 return LineOffset < O.LineOffset || 290 (LineOffset == O.LineOffset && Discriminator < O.Discriminator); 291 } 292 293 bool operator==(const LineLocation &O) const { 294 return LineOffset == O.LineOffset && Discriminator == O.Discriminator; 295 } 296 297 bool operator!=(const LineLocation &O) const { 298 return LineOffset != O.LineOffset || Discriminator != O.Discriminator; 299 } 300 301 uint32_t LineOffset; 302 uint32_t Discriminator; 303 }; 304 305 raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc); 306 307 /// Representation of a single sample record. 308 /// 309 /// A sample record is represented by a positive integer value, which 310 /// indicates how frequently was the associated line location executed. 311 /// 312 /// Additionally, if the associated location contains a function call, 313 /// the record will hold a list of all the possible called targets. For 314 /// direct calls, this will be the exact function being invoked. For 315 /// indirect calls (function pointers, virtual table dispatch), this 316 /// will be a list of one or more functions. 317 class SampleRecord { 318 public: 319 using CallTarget = std::pair<StringRef, uint64_t>; 320 struct CallTargetComparator { 321 bool operator()(const CallTarget &LHS, const CallTarget &RHS) const { 322 if (LHS.second != RHS.second) 323 return LHS.second > RHS.second; 324 325 return LHS.first < RHS.first; 326 } 327 }; 328 329 using SortedCallTargetSet = std::set<CallTarget, CallTargetComparator>; 330 using CallTargetMap = StringMap<uint64_t>; 331 SampleRecord() = default; 332 333 /// Increment the number of samples for this record by \p S. 334 /// Optionally scale sample count \p S by \p Weight. 335 /// 336 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping 337 /// around unsigned integers. 338 sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) { 339 bool Overflowed; 340 NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed); 341 return Overflowed ? sampleprof_error::counter_overflow 342 : sampleprof_error::success; 343 } 344 345 /// Decrease the number of samples for this record by \p S. Return the amout 346 /// of samples actually decreased. 347 uint64_t removeSamples(uint64_t S) { 348 if (S > NumSamples) 349 S = NumSamples; 350 NumSamples -= S; 351 return S; 352 } 353 354 /// Add called function \p F with samples \p S. 355 /// Optionally scale sample count \p S by \p Weight. 356 /// 357 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping 358 /// around unsigned integers. 359 sampleprof_error addCalledTarget(StringRef F, uint64_t S, 360 uint64_t Weight = 1) { 361 uint64_t &TargetSamples = CallTargets[F]; 362 bool Overflowed; 363 TargetSamples = 364 SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed); 365 return Overflowed ? sampleprof_error::counter_overflow 366 : sampleprof_error::success; 367 } 368 369 /// Remove called function from the call target map. Return the target sample 370 /// count of the called function. 371 uint64_t removeCalledTarget(StringRef F) { 372 uint64_t Count = 0; 373 auto I = CallTargets.find(F); 374 if (I != CallTargets.end()) { 375 Count = I->second; 376 CallTargets.erase(I); 377 } 378 return Count; 379 } 380 381 /// Return true if this sample record contains function calls. 382 bool hasCalls() const { return !CallTargets.empty(); } 383 384 uint64_t getSamples() const { return NumSamples; } 385 const CallTargetMap &getCallTargets() const { return CallTargets; } 386 const SortedCallTargetSet getSortedCallTargets() const { 387 return SortCallTargets(CallTargets); 388 } 389 390 uint64_t getCallTargetSum() const { 391 uint64_t Sum = 0; 392 for (const auto &I : CallTargets) 393 Sum += I.second; 394 return Sum; 395 } 396 397 /// Sort call targets in descending order of call frequency. 398 static const SortedCallTargetSet SortCallTargets(const CallTargetMap &Targets) { 399 SortedCallTargetSet SortedTargets; 400 for (const auto &I : Targets) { 401 SortedTargets.emplace(I.first(), I.second); 402 } 403 return SortedTargets; 404 } 405 406 /// Prorate call targets by a distribution factor. 407 static const CallTargetMap adjustCallTargets(const CallTargetMap &Targets, 408 float DistributionFactor) { 409 CallTargetMap AdjustedTargets; 410 for (const auto &I : Targets) { 411 AdjustedTargets[I.first()] = I.second * DistributionFactor; 412 } 413 return AdjustedTargets; 414 } 415 416 /// Merge the samples in \p Other into this record. 417 /// Optionally scale sample counts by \p Weight. 418 sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1); 419 void print(raw_ostream &OS, unsigned Indent) const; 420 void dump() const; 421 422 private: 423 uint64_t NumSamples = 0; 424 CallTargetMap CallTargets; 425 }; 426 427 raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample); 428 429 // State of context associated with FunctionSamples 430 enum ContextStateMask { 431 UnknownContext = 0x0, // Profile without context 432 RawContext = 0x1, // Full context profile from input profile 433 SyntheticContext = 0x2, // Synthetic context created for context promotion 434 InlinedContext = 0x4, // Profile for context that is inlined into caller 435 MergedContext = 0x8 // Profile for context merged into base profile 436 }; 437 438 // Attribute of context associated with FunctionSamples 439 enum ContextAttributeMask { 440 ContextNone = 0x0, 441 ContextWasInlined = 0x1, // Leaf of context was inlined in previous build 442 ContextShouldBeInlined = 0x2, // Leaf of context should be inlined 443 ContextDuplicatedIntoBase = 444 0x4, // Leaf of context is duplicated into the base profile 445 }; 446 447 // Represents a context frame with function name and line location 448 struct SampleContextFrame { 449 StringRef FuncName; 450 LineLocation Location; 451 452 SampleContextFrame() : Location(0, 0) {} 453 454 SampleContextFrame(StringRef FuncName, LineLocation Location) 455 : FuncName(FuncName), Location(Location) {} 456 457 bool operator==(const SampleContextFrame &That) const { 458 return Location == That.Location && FuncName == That.FuncName; 459 } 460 461 bool operator!=(const SampleContextFrame &That) const { 462 return !(*this == That); 463 } 464 465 std::string toString(bool OutputLineLocation) const { 466 std::ostringstream OContextStr; 467 OContextStr << FuncName.str(); 468 if (OutputLineLocation) { 469 OContextStr << ":" << Location.LineOffset; 470 if (Location.Discriminator) 471 OContextStr << "." << Location.Discriminator; 472 } 473 return OContextStr.str(); 474 } 475 }; 476 477 static inline hash_code hash_value(const SampleContextFrame &arg) { 478 return hash_combine(arg.FuncName, arg.Location.LineOffset, 479 arg.Location.Discriminator); 480 } 481 482 using SampleContextFrameVector = SmallVector<SampleContextFrame, 1>; 483 using SampleContextFrames = ArrayRef<SampleContextFrame>; 484 485 struct SampleContextFrameHash { 486 uint64_t operator()(const SampleContextFrameVector &S) const { 487 return hash_combine_range(S.begin(), S.end()); 488 } 489 }; 490 491 // Sample context for FunctionSamples. It consists of the calling context, 492 // the function name and context state. Internally sample context is represented 493 // using ArrayRef, which is also the input for constructing a `SampleContext`. 494 // It can accept and represent both full context string as well as context-less 495 // function name. 496 // For a CS profile, a full context vector can look like: 497 // `main:3 _Z5funcAi:1 _Z8funcLeafi` 498 // For a base CS profile without calling context, the context vector should only 499 // contain the leaf frame name. 500 // For a non-CS profile, the context vector should be empty. 501 class SampleContext { 502 public: 503 SampleContext() : State(UnknownContext), Attributes(ContextNone) {} 504 505 SampleContext(StringRef Name) 506 : Name(Name), State(UnknownContext), Attributes(ContextNone) {} 507 508 SampleContext(SampleContextFrames Context, 509 ContextStateMask CState = RawContext) 510 : Attributes(ContextNone) { 511 assert(!Context.empty() && "Context is empty"); 512 setContext(Context, CState); 513 } 514 515 // Give a context string, decode and populate internal states like 516 // Function name, Calling context and context state. Example of input 517 // `ContextStr`: `[main:3 @ _Z5funcAi:1 @ _Z8funcLeafi]` 518 SampleContext(StringRef ContextStr, 519 std::list<SampleContextFrameVector> &CSNameTable, 520 ContextStateMask CState = RawContext) 521 : Attributes(ContextNone) { 522 assert(!ContextStr.empty()); 523 // Note that `[]` wrapped input indicates a full context string, otherwise 524 // it's treated as context-less function name only. 525 bool HasContext = ContextStr.startswith("["); 526 if (!HasContext) { 527 State = UnknownContext; 528 Name = ContextStr; 529 } else { 530 CSNameTable.emplace_back(); 531 SampleContextFrameVector &Context = CSNameTable.back(); 532 createCtxVectorFromStr(ContextStr, Context); 533 setContext(Context, CState); 534 } 535 } 536 537 /// Create a context vector from a given context string and save it in 538 /// `Context`. 539 static void createCtxVectorFromStr(StringRef ContextStr, 540 SampleContextFrameVector &Context) { 541 // Remove encapsulating '[' and ']' if any 542 ContextStr = ContextStr.substr(1, ContextStr.size() - 2); 543 StringRef ContextRemain = ContextStr; 544 StringRef ChildContext; 545 StringRef CalleeName; 546 while (!ContextRemain.empty()) { 547 auto ContextSplit = ContextRemain.split(" @ "); 548 ChildContext = ContextSplit.first; 549 ContextRemain = ContextSplit.second; 550 LineLocation CallSiteLoc(0, 0); 551 decodeContextString(ChildContext, CalleeName, CallSiteLoc); 552 Context.emplace_back(CalleeName, CallSiteLoc); 553 } 554 } 555 556 // Decode context string for a frame to get function name and location. 557 // `ContextStr` is in the form of `FuncName:StartLine.Discriminator`. 558 static void decodeContextString(StringRef ContextStr, StringRef &FName, 559 LineLocation &LineLoc) { 560 // Get function name 561 auto EntrySplit = ContextStr.split(':'); 562 FName = EntrySplit.first; 563 564 LineLoc = {0, 0}; 565 if (!EntrySplit.second.empty()) { 566 // Get line offset, use signed int for getAsInteger so string will 567 // be parsed as signed. 568 int LineOffset = 0; 569 auto LocSplit = EntrySplit.second.split('.'); 570 LocSplit.first.getAsInteger(10, LineOffset); 571 LineLoc.LineOffset = LineOffset; 572 573 // Get discriminator 574 if (!LocSplit.second.empty()) 575 LocSplit.second.getAsInteger(10, LineLoc.Discriminator); 576 } 577 } 578 579 operator SampleContextFrames() const { return FullContext; } 580 bool hasAttribute(ContextAttributeMask A) { return Attributes & (uint32_t)A; } 581 void setAttribute(ContextAttributeMask A) { Attributes |= (uint32_t)A; } 582 uint32_t getAllAttributes() { return Attributes; } 583 void setAllAttributes(uint32_t A) { Attributes = A; } 584 bool hasState(ContextStateMask S) { return State & (uint32_t)S; } 585 void setState(ContextStateMask S) { State |= (uint32_t)S; } 586 void clearState(ContextStateMask S) { State &= (uint32_t)~S; } 587 bool hasContext() const { return State != UnknownContext; } 588 bool isBaseContext() const { return FullContext.size() == 1; } 589 StringRef getName() const { return Name; } 590 SampleContextFrames getContextFrames() const { return FullContext; } 591 592 static std::string getContextString(SampleContextFrames Context, 593 bool IncludeLeafLineLocation = false) { 594 std::ostringstream OContextStr; 595 for (uint32_t I = 0; I < Context.size(); I++) { 596 if (OContextStr.str().size()) { 597 OContextStr << " @ "; 598 } 599 OContextStr << Context[I].toString(I != Context.size() - 1 || 600 IncludeLeafLineLocation); 601 } 602 return OContextStr.str(); 603 } 604 605 std::string toString() const { 606 if (!hasContext()) 607 return Name.str(); 608 return getContextString(FullContext, false); 609 } 610 611 uint64_t getHashCode() const { 612 return hasContext() ? hash_value(getContextFrames()) 613 : hash_value(getName()); 614 } 615 616 /// Set the name of the function and clear the current context. 617 void setName(StringRef FunctionName) { 618 Name = FunctionName; 619 FullContext = SampleContextFrames(); 620 State = UnknownContext; 621 } 622 623 void setContext(SampleContextFrames Context, 624 ContextStateMask CState = RawContext) { 625 assert(CState != UnknownContext); 626 FullContext = Context; 627 Name = Context.back().FuncName; 628 State = CState; 629 } 630 631 bool operator==(const SampleContext &That) const { 632 return State == That.State && Name == That.Name && 633 FullContext == That.FullContext; 634 } 635 636 bool operator!=(const SampleContext &That) const { return !(*this == That); } 637 638 bool operator<(const SampleContext &That) const { 639 if (State != That.State) 640 return State < That.State; 641 642 if (!hasContext()) { 643 return (Name.compare(That.Name)) == -1; 644 } 645 646 uint64_t I = 0; 647 while (I < std::min(FullContext.size(), That.FullContext.size())) { 648 auto &Context1 = FullContext[I]; 649 auto &Context2 = That.FullContext[I]; 650 auto V = Context1.FuncName.compare(Context2.FuncName); 651 if (V) 652 return V == -1; 653 if (Context1.Location != Context2.Location) 654 return Context1.Location < Context2.Location; 655 I++; 656 } 657 658 return FullContext.size() < That.FullContext.size(); 659 } 660 661 struct Hash { 662 uint64_t operator()(const SampleContext &Context) const { 663 return Context.getHashCode(); 664 } 665 }; 666 667 bool IsPrefixOf(const SampleContext &That) const { 668 auto ThisContext = FullContext; 669 auto ThatContext = That.FullContext; 670 if (ThatContext.size() < ThisContext.size()) 671 return false; 672 ThatContext = ThatContext.take_front(ThisContext.size()); 673 // Compare Leaf frame first 674 if (ThisContext.back().FuncName != ThatContext.back().FuncName) 675 return false; 676 // Compare leading context 677 return ThisContext.drop_back() == ThatContext.drop_back(); 678 } 679 680 private: 681 /// Mangled name of the function. 682 StringRef Name; 683 // Full context including calling context and leaf function name 684 SampleContextFrames FullContext; 685 // State of the associated sample profile 686 uint32_t State; 687 // Attribute of the associated sample profile 688 uint32_t Attributes; 689 }; 690 691 static inline hash_code hash_value(const SampleContext &arg) { 692 return arg.hasContext() ? hash_value(arg.getContextFrames()) 693 : hash_value(arg.getName()); 694 } 695 696 class FunctionSamples; 697 class SampleProfileReaderItaniumRemapper; 698 699 using BodySampleMap = std::map<LineLocation, SampleRecord>; 700 // NOTE: Using a StringMap here makes parsed profiles consume around 17% more 701 // memory, which is *very* significant for large profiles. 702 using FunctionSamplesMap = std::map<std::string, FunctionSamples, std::less<>>; 703 using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>; 704 705 /// Representation of the samples collected for a function. 706 /// 707 /// This data structure contains all the collected samples for the body 708 /// of a function. Each sample corresponds to a LineLocation instance 709 /// within the body of the function. 710 class FunctionSamples { 711 public: 712 FunctionSamples() = default; 713 714 void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const; 715 void dump() const; 716 717 sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) { 718 bool Overflowed; 719 TotalSamples = 720 SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed); 721 return Overflowed ? sampleprof_error::counter_overflow 722 : sampleprof_error::success; 723 } 724 725 void removeTotalSamples(uint64_t Num) { 726 if (TotalSamples < Num) 727 TotalSamples = 0; 728 else 729 TotalSamples -= Num; 730 } 731 732 void setTotalSamples(uint64_t Num) { TotalSamples = Num; } 733 734 sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) { 735 bool Overflowed; 736 TotalHeadSamples = 737 SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed); 738 return Overflowed ? sampleprof_error::counter_overflow 739 : sampleprof_error::success; 740 } 741 742 sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator, 743 uint64_t Num, uint64_t Weight = 1) { 744 return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples( 745 Num, Weight); 746 } 747 748 sampleprof_error addCalledTargetSamples(uint32_t LineOffset, 749 uint32_t Discriminator, 750 StringRef FName, uint64_t Num, 751 uint64_t Weight = 1) { 752 return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget( 753 FName, Num, Weight); 754 } 755 756 // Remove a call target and decrease the body sample correspondingly. Return 757 // the number of body samples actually decreased. 758 uint64_t removeCalledTargetAndBodySample(uint32_t LineOffset, 759 uint32_t Discriminator, 760 StringRef FName) { 761 uint64_t Count = 0; 762 auto I = BodySamples.find(LineLocation(LineOffset, Discriminator)); 763 if (I != BodySamples.end()) { 764 Count = I->second.removeCalledTarget(FName); 765 Count = I->second.removeSamples(Count); 766 if (!I->second.getSamples()) 767 BodySamples.erase(I); 768 } 769 return Count; 770 } 771 772 sampleprof_error addBodySamplesForProbe(uint32_t Index, uint64_t Num, 773 uint64_t Weight = 1) { 774 SampleRecord S; 775 S.addSamples(Num, Weight); 776 return BodySamples[LineLocation(Index, 0)].merge(S, Weight); 777 } 778 779 // Accumulate all call target samples to update the body samples. 780 void updateCallsiteSamples() { 781 for (auto &I : BodySamples) { 782 uint64_t TargetSamples = I.second.getCallTargetSum(); 783 // It's possible that the body sample count can be greater than the call 784 // target sum. E.g, if some call targets are external targets, they won't 785 // be considered valid call targets, but the body sample count which is 786 // from lbr ranges can actually include them. 787 if (TargetSamples > I.second.getSamples()) 788 I.second.addSamples(TargetSamples - I.second.getSamples()); 789 } 790 } 791 792 // Accumulate all body samples to set total samples. 793 void updateTotalSamples() { 794 setTotalSamples(0); 795 for (const auto &I : BodySamples) 796 addTotalSamples(I.second.getSamples()); 797 798 for (auto &I : CallsiteSamples) { 799 for (auto &CS : I.second) { 800 CS.second.updateTotalSamples(); 801 addTotalSamples(CS.second.getTotalSamples()); 802 } 803 } 804 } 805 806 // Set current context and all callee contexts to be synthetic. 807 void SetContextSynthetic() { 808 Context.setState(SyntheticContext); 809 for (auto &I : CallsiteSamples) { 810 for (auto &CS : I.second) { 811 CS.second.SetContextSynthetic(); 812 } 813 } 814 } 815 816 /// Return the number of samples collected at the given location. 817 /// Each location is specified by \p LineOffset and \p Discriminator. 818 /// If the location is not found in profile, return error. 819 ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset, 820 uint32_t Discriminator) const { 821 const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator)); 822 if (ret == BodySamples.end()) 823 return std::error_code(); 824 return ret->second.getSamples(); 825 } 826 827 /// Returns the call target map collected at a given location. 828 /// Each location is specified by \p LineOffset and \p Discriminator. 829 /// If the location is not found in profile, return error. 830 ErrorOr<SampleRecord::CallTargetMap> 831 findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const { 832 const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator)); 833 if (ret == BodySamples.end()) 834 return std::error_code(); 835 return ret->second.getCallTargets(); 836 } 837 838 /// Returns the call target map collected at a given location specified by \p 839 /// CallSite. If the location is not found in profile, return error. 840 ErrorOr<SampleRecord::CallTargetMap> 841 findCallTargetMapAt(const LineLocation &CallSite) const { 842 const auto &Ret = BodySamples.find(CallSite); 843 if (Ret == BodySamples.end()) 844 return std::error_code(); 845 return Ret->second.getCallTargets(); 846 } 847 848 /// Return the function samples at the given callsite location. 849 FunctionSamplesMap &functionSamplesAt(const LineLocation &Loc) { 850 return CallsiteSamples[Loc]; 851 } 852 853 /// Returns the FunctionSamplesMap at the given \p Loc. 854 const FunctionSamplesMap * 855 findFunctionSamplesMapAt(const LineLocation &Loc) const { 856 auto iter = CallsiteSamples.find(Loc); 857 if (iter == CallsiteSamples.end()) 858 return nullptr; 859 return &iter->second; 860 } 861 862 /// Returns a pointer to FunctionSamples at the given callsite location 863 /// \p Loc with callee \p CalleeName. If no callsite can be found, relax 864 /// the restriction to return the FunctionSamples at callsite location 865 /// \p Loc with the maximum total sample count. If \p Remapper is not 866 /// nullptr, use \p Remapper to find FunctionSamples with equivalent name 867 /// as \p CalleeName. 868 const FunctionSamples * 869 findFunctionSamplesAt(const LineLocation &Loc, StringRef CalleeName, 870 SampleProfileReaderItaniumRemapper *Remapper) const; 871 872 bool empty() const { return TotalSamples == 0; } 873 874 /// Return the total number of samples collected inside the function. 875 uint64_t getTotalSamples() const { return TotalSamples; } 876 877 /// Return the total number of branch samples that have the function as the 878 /// branch target. This should be equivalent to the sample of the first 879 /// instruction of the symbol. But as we directly get this info for raw 880 /// profile without referring to potentially inaccurate debug info, this 881 /// gives more accurate profile data and is preferred for standalone symbols. 882 uint64_t getHeadSamples() const { return TotalHeadSamples; } 883 884 /// Return the sample count of the first instruction of the function. 885 /// The function can be either a standalone symbol or an inlined function. 886 uint64_t getEntrySamples() const { 887 if (FunctionSamples::ProfileIsCS && getHeadSamples()) { 888 // For CS profile, if we already have more accurate head samples 889 // counted by branch sample from caller, use them as entry samples. 890 return getHeadSamples(); 891 } 892 uint64_t Count = 0; 893 // Use either BodySamples or CallsiteSamples which ever has the smaller 894 // lineno. 895 if (!BodySamples.empty() && 896 (CallsiteSamples.empty() || 897 BodySamples.begin()->first < CallsiteSamples.begin()->first)) 898 Count = BodySamples.begin()->second.getSamples(); 899 else if (!CallsiteSamples.empty()) { 900 // An indirect callsite may be promoted to several inlined direct calls. 901 // We need to get the sum of them. 902 for (const auto &N_FS : CallsiteSamples.begin()->second) 903 Count += N_FS.second.getEntrySamples(); 904 } 905 // Return at least 1 if total sample is not 0. 906 return Count ? Count : TotalSamples > 0; 907 } 908 909 /// Return all the samples collected in the body of the function. 910 const BodySampleMap &getBodySamples() const { return BodySamples; } 911 912 /// Return all the callsite samples collected in the body of the function. 913 const CallsiteSampleMap &getCallsiteSamples() const { 914 return CallsiteSamples; 915 } 916 917 /// Return the maximum of sample counts in a function body including functions 918 /// inlined in it. 919 uint64_t getMaxCountInside() const { 920 uint64_t MaxCount = 0; 921 for (const auto &L : getBodySamples()) 922 MaxCount = std::max(MaxCount, L.second.getSamples()); 923 for (const auto &C : getCallsiteSamples()) 924 for (const FunctionSamplesMap::value_type &F : C.second) 925 MaxCount = std::max(MaxCount, F.second.getMaxCountInside()); 926 return MaxCount; 927 } 928 929 /// Merge the samples in \p Other into this one. 930 /// Optionally scale samples by \p Weight. 931 sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) { 932 sampleprof_error Result = sampleprof_error::success; 933 if (!GUIDToFuncNameMap) 934 GUIDToFuncNameMap = Other.GUIDToFuncNameMap; 935 if (Context.getName().empty()) 936 Context = Other.getContext(); 937 if (FunctionHash == 0) { 938 // Set the function hash code for the target profile. 939 FunctionHash = Other.getFunctionHash(); 940 } else if (FunctionHash != Other.getFunctionHash()) { 941 // The two profiles coming with different valid hash codes indicates 942 // either: 943 // 1. They are same-named static functions from different compilation 944 // units (without using -unique-internal-linkage-names), or 945 // 2. They are really the same function but from different compilations. 946 // Let's bail out in either case for now, which means one profile is 947 // dropped. 948 return sampleprof_error::hash_mismatch; 949 } 950 951 MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight)); 952 MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight)); 953 for (const auto &I : Other.getBodySamples()) { 954 const LineLocation &Loc = I.first; 955 const SampleRecord &Rec = I.second; 956 MergeResult(Result, BodySamples[Loc].merge(Rec, Weight)); 957 } 958 for (const auto &I : Other.getCallsiteSamples()) { 959 const LineLocation &Loc = I.first; 960 FunctionSamplesMap &FSMap = functionSamplesAt(Loc); 961 for (const auto &Rec : I.second) 962 MergeResult(Result, FSMap[Rec.first].merge(Rec.second, Weight)); 963 } 964 return Result; 965 } 966 967 /// Recursively traverses all children, if the total sample count of the 968 /// corresponding function is no less than \p Threshold, add its corresponding 969 /// GUID to \p S. Also traverse the BodySamples to add hot CallTarget's GUID 970 /// to \p S. 971 void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S, 972 const StringMap<Function *> &SymbolMap, 973 uint64_t Threshold) const { 974 if (TotalSamples <= Threshold) 975 return; 976 auto isDeclaration = [](const Function *F) { 977 return !F || F->isDeclaration(); 978 }; 979 if (isDeclaration(SymbolMap.lookup(getFuncName()))) { 980 // Add to the import list only when it's defined out of module. 981 S.insert(getGUID(getName())); 982 } 983 // Import hot CallTargets, which may not be available in IR because full 984 // profile annotation cannot be done until backend compilation in ThinLTO. 985 for (const auto &BS : BodySamples) 986 for (const auto &TS : BS.second.getCallTargets()) 987 if (TS.getValue() > Threshold) { 988 const Function *Callee = SymbolMap.lookup(getFuncName(TS.getKey())); 989 if (isDeclaration(Callee)) 990 S.insert(getGUID(TS.getKey())); 991 } 992 for (const auto &CS : CallsiteSamples) 993 for (const auto &NameFS : CS.second) 994 NameFS.second.findInlinedFunctions(S, SymbolMap, Threshold); 995 } 996 997 /// Set the name of the function. 998 void setName(StringRef FunctionName) { Context.setName(FunctionName); } 999 1000 /// Return the function name. 1001 StringRef getName() const { return Context.getName(); } 1002 1003 /// Return the original function name. 1004 StringRef getFuncName() const { return getFuncName(getName()); } 1005 1006 void setFunctionHash(uint64_t Hash) { FunctionHash = Hash; } 1007 1008 uint64_t getFunctionHash() const { return FunctionHash; } 1009 1010 /// Return the canonical name for a function, taking into account 1011 /// suffix elision policy attributes. 1012 static StringRef getCanonicalFnName(const Function &F) { 1013 auto AttrName = "sample-profile-suffix-elision-policy"; 1014 auto Attr = F.getFnAttribute(AttrName).getValueAsString(); 1015 return getCanonicalFnName(F.getName(), Attr); 1016 } 1017 1018 /// Name suffixes which canonicalization should handle to avoid 1019 /// profile mismatch. 1020 static constexpr const char *LLVMSuffix = ".llvm."; 1021 static constexpr const char *PartSuffix = ".part."; 1022 static constexpr const char *UniqSuffix = ".__uniq."; 1023 1024 static StringRef getCanonicalFnName(StringRef FnName, 1025 StringRef Attr = "selected") { 1026 // Note the sequence of the suffixes in the knownSuffixes array matters. 1027 // If suffix "A" is appended after the suffix "B", "A" should be in front 1028 // of "B" in knownSuffixes. 1029 const char *knownSuffixes[] = {LLVMSuffix, PartSuffix, UniqSuffix}; 1030 if (Attr == "" || Attr == "all") { 1031 return FnName.split('.').first; 1032 } else if (Attr == "selected") { 1033 StringRef Cand(FnName); 1034 for (const auto &Suf : knownSuffixes) { 1035 StringRef Suffix(Suf); 1036 // If the profile contains ".__uniq." suffix, don't strip the 1037 // suffix for names in the IR. 1038 if (Suffix == UniqSuffix && FunctionSamples::HasUniqSuffix) 1039 continue; 1040 auto It = Cand.rfind(Suffix); 1041 if (It == StringRef::npos) 1042 continue; 1043 auto Dit = Cand.rfind('.'); 1044 if (Dit == It + Suffix.size() - 1) 1045 Cand = Cand.substr(0, It); 1046 } 1047 return Cand; 1048 } else if (Attr == "none") { 1049 return FnName; 1050 } else { 1051 assert(false && "internal error: unknown suffix elision policy"); 1052 } 1053 return FnName; 1054 } 1055 1056 /// Translate \p Name into its original name. 1057 /// When profile doesn't use MD5, \p Name needs no translation. 1058 /// When profile uses MD5, \p Name in current FunctionSamples 1059 /// is actually GUID of the original function name. getFuncName will 1060 /// translate \p Name in current FunctionSamples into its original name 1061 /// by looking up in the function map GUIDToFuncNameMap. 1062 /// If the original name doesn't exist in the map, return empty StringRef. 1063 StringRef getFuncName(StringRef Name) const { 1064 if (!UseMD5) 1065 return Name; 1066 1067 assert(GUIDToFuncNameMap && "GUIDToFuncNameMap needs to be populated first"); 1068 return GUIDToFuncNameMap->lookup(std::stoull(Name.data())); 1069 } 1070 1071 /// Returns the line offset to the start line of the subprogram. 1072 /// We assume that a single function will not exceed 65535 LOC. 1073 static unsigned getOffset(const DILocation *DIL); 1074 1075 /// Returns a unique call site identifier for a given debug location of a call 1076 /// instruction. This is wrapper of two scenarios, the probe-based profile and 1077 /// regular profile, to hide implementation details from the sample loader and 1078 /// the context tracker. 1079 static LineLocation getCallSiteIdentifier(const DILocation *DIL, 1080 bool ProfileIsFS = false); 1081 1082 /// Returns a unique hash code for a combination of a callsite location and 1083 /// the callee function name. 1084 static uint64_t getCallSiteHash(StringRef CalleeName, 1085 const LineLocation &Callsite); 1086 1087 /// Get the FunctionSamples of the inline instance where DIL originates 1088 /// from. 1089 /// 1090 /// The FunctionSamples of the instruction (Machine or IR) associated to 1091 /// \p DIL is the inlined instance in which that instruction is coming from. 1092 /// We traverse the inline stack of that instruction, and match it with the 1093 /// tree nodes in the profile. 1094 /// 1095 /// \returns the FunctionSamples pointer to the inlined instance. 1096 /// If \p Remapper is not nullptr, it will be used to find matching 1097 /// FunctionSamples with not exactly the same but equivalent name. 1098 const FunctionSamples *findFunctionSamples( 1099 const DILocation *DIL, 1100 SampleProfileReaderItaniumRemapper *Remapper = nullptr) const; 1101 1102 static bool ProfileIsProbeBased; 1103 1104 static bool ProfileIsCS; 1105 1106 static bool ProfileIsPreInlined; 1107 1108 SampleContext &getContext() const { return Context; } 1109 1110 void setContext(const SampleContext &FContext) { Context = FContext; } 1111 1112 /// Whether the profile uses MD5 to represent string. 1113 static bool UseMD5; 1114 1115 /// Whether the profile contains any ".__uniq." suffix in a name. 1116 static bool HasUniqSuffix; 1117 1118 /// If this profile uses flow sensitive discriminators. 1119 static bool ProfileIsFS; 1120 1121 /// GUIDToFuncNameMap saves the mapping from GUID to the symbol name, for 1122 /// all the function symbols defined or declared in current module. 1123 DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap = nullptr; 1124 1125 // Assume the input \p Name is a name coming from FunctionSamples itself. 1126 // If UseMD5 is true, the name is already a GUID and we 1127 // don't want to return the GUID of GUID. 1128 static uint64_t getGUID(StringRef Name) { 1129 return UseMD5 ? std::stoull(Name.data()) : Function::getGUID(Name); 1130 } 1131 1132 // Find all the names in the current FunctionSamples including names in 1133 // all the inline instances and names of call targets. 1134 void findAllNames(DenseSet<StringRef> &NameSet) const; 1135 1136 private: 1137 /// CFG hash value for the function. 1138 uint64_t FunctionHash = 0; 1139 1140 /// Calling context for function profile 1141 mutable SampleContext Context; 1142 1143 /// Total number of samples collected inside this function. 1144 /// 1145 /// Samples are cumulative, they include all the samples collected 1146 /// inside this function and all its inlined callees. 1147 uint64_t TotalSamples = 0; 1148 1149 /// Total number of samples collected at the head of the function. 1150 /// This is an approximation of the number of calls made to this function 1151 /// at runtime. 1152 uint64_t TotalHeadSamples = 0; 1153 1154 /// Map instruction locations to collected samples. 1155 /// 1156 /// Each entry in this map contains the number of samples 1157 /// collected at the corresponding line offset. All line locations 1158 /// are an offset from the start of the function. 1159 BodySampleMap BodySamples; 1160 1161 /// Map call sites to collected samples for the called function. 1162 /// 1163 /// Each entry in this map corresponds to all the samples 1164 /// collected for the inlined function call at the given 1165 /// location. For example, given: 1166 /// 1167 /// void foo() { 1168 /// 1 bar(); 1169 /// ... 1170 /// 8 baz(); 1171 /// } 1172 /// 1173 /// If the bar() and baz() calls were inlined inside foo(), this 1174 /// map will contain two entries. One for all the samples collected 1175 /// in the call to bar() at line offset 1, the other for all the samples 1176 /// collected in the call to baz() at line offset 8. 1177 CallsiteSampleMap CallsiteSamples; 1178 }; 1179 1180 raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS); 1181 1182 using SampleProfileMap = 1183 std::unordered_map<SampleContext, FunctionSamples, SampleContext::Hash>; 1184 1185 using NameFunctionSamples = std::pair<SampleContext, const FunctionSamples *>; 1186 1187 void sortFuncProfiles(const SampleProfileMap &ProfileMap, 1188 std::vector<NameFunctionSamples> &SortedProfiles); 1189 1190 /// Sort a LocationT->SampleT map by LocationT. 1191 /// 1192 /// It produces a sorted list of <LocationT, SampleT> records by ascending 1193 /// order of LocationT. 1194 template <class LocationT, class SampleT> class SampleSorter { 1195 public: 1196 using SamplesWithLoc = std::pair<const LocationT, SampleT>; 1197 using SamplesWithLocList = SmallVector<const SamplesWithLoc *, 20>; 1198 1199 SampleSorter(const std::map<LocationT, SampleT> &Samples) { 1200 for (const auto &I : Samples) 1201 V.push_back(&I); 1202 llvm::stable_sort(V, [](const SamplesWithLoc *A, const SamplesWithLoc *B) { 1203 return A->first < B->first; 1204 }); 1205 } 1206 1207 const SamplesWithLocList &get() const { return V; } 1208 1209 private: 1210 SamplesWithLocList V; 1211 }; 1212 1213 /// SampleContextTrimmer impelements helper functions to trim, merge cold 1214 /// context profiles. It also supports context profile canonicalization to make 1215 /// sure ProfileMap's key is consistent with FunctionSample's name/context. 1216 class SampleContextTrimmer { 1217 public: 1218 SampleContextTrimmer(SampleProfileMap &Profiles) : ProfileMap(Profiles){}; 1219 // Trim and merge cold context profile when requested. TrimBaseProfileOnly 1220 // should only be effective when TrimColdContext is true. On top of 1221 // TrimColdContext, TrimBaseProfileOnly can be used to specify to trim all 1222 // cold profiles or only cold base profiles. Trimming base profiles only is 1223 // mainly to honor the preinliner decsion. Note that when MergeColdContext is 1224 // true, preinliner decsion is not honored anyway so TrimBaseProfileOnly will 1225 // be ignored. 1226 void trimAndMergeColdContextProfiles(uint64_t ColdCountThreshold, 1227 bool TrimColdContext, 1228 bool MergeColdContext, 1229 uint32_t ColdContextFrameLength, 1230 bool TrimBaseProfileOnly); 1231 // Canonicalize context profile name and attributes. 1232 void canonicalizeContextProfiles(); 1233 1234 private: 1235 SampleProfileMap &ProfileMap; 1236 }; 1237 1238 // CSProfileConverter converts a full context-sensitive flat sample profile into 1239 // a nested context-sensitive sample profile. 1240 class CSProfileConverter { 1241 public: 1242 CSProfileConverter(SampleProfileMap &Profiles); 1243 void convertProfiles(); 1244 struct FrameNode { 1245 FrameNode(StringRef FName = StringRef(), 1246 FunctionSamples *FSamples = nullptr, 1247 LineLocation CallLoc = {0, 0}) 1248 : FuncName(FName), FuncSamples(FSamples), CallSiteLoc(CallLoc){}; 1249 1250 // Map line+discriminator location to child frame 1251 std::map<uint64_t, FrameNode> AllChildFrames; 1252 // Function name for current frame 1253 StringRef FuncName; 1254 // Function Samples for current frame 1255 FunctionSamples *FuncSamples; 1256 // Callsite location in parent context 1257 LineLocation CallSiteLoc; 1258 1259 FrameNode *getOrCreateChildFrame(const LineLocation &CallSite, 1260 StringRef CalleeName); 1261 }; 1262 1263 private: 1264 // Nest all children profiles into the profile of Node. 1265 void convertProfiles(FrameNode &Node); 1266 FrameNode *getOrCreateContextPath(const SampleContext &Context); 1267 1268 SampleProfileMap &ProfileMap; 1269 FrameNode RootFrame; 1270 }; 1271 1272 /// ProfileSymbolList records the list of function symbols shown up 1273 /// in the binary used to generate the profile. It is useful to 1274 /// to discriminate a function being so cold as not to shown up 1275 /// in the profile and a function newly added. 1276 class ProfileSymbolList { 1277 public: 1278 /// copy indicates whether we need to copy the underlying memory 1279 /// for the input Name. 1280 void add(StringRef Name, bool copy = false) { 1281 if (!copy) { 1282 Syms.insert(Name); 1283 return; 1284 } 1285 Syms.insert(Name.copy(Allocator)); 1286 } 1287 1288 bool contains(StringRef Name) { return Syms.count(Name); } 1289 1290 void merge(const ProfileSymbolList &List) { 1291 for (auto Sym : List.Syms) 1292 add(Sym, true); 1293 } 1294 1295 unsigned size() { return Syms.size(); } 1296 1297 void setToCompress(bool TC) { ToCompress = TC; } 1298 bool toCompress() { return ToCompress; } 1299 1300 std::error_code read(const uint8_t *Data, uint64_t ListSize); 1301 std::error_code write(raw_ostream &OS); 1302 void dump(raw_ostream &OS = dbgs()) const; 1303 1304 private: 1305 // Determine whether or not to compress the symbol list when 1306 // writing it into profile. The variable is unused when the symbol 1307 // list is read from an existing profile. 1308 bool ToCompress = false; 1309 DenseSet<StringRef> Syms; 1310 BumpPtrAllocator Allocator; 1311 }; 1312 1313 } // end namespace sampleprof 1314 1315 using namespace sampleprof; 1316 // Provide DenseMapInfo for SampleContext. 1317 template <> struct DenseMapInfo<SampleContext> { 1318 static inline SampleContext getEmptyKey() { return SampleContext(); } 1319 1320 static inline SampleContext getTombstoneKey() { return SampleContext("@"); } 1321 1322 static unsigned getHashValue(const SampleContext &Val) { 1323 return Val.getHashCode(); 1324 } 1325 1326 static bool isEqual(const SampleContext &LHS, const SampleContext &RHS) { 1327 return LHS == RHS; 1328 } 1329 }; 1330 } // end namespace llvm 1331 1332 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H 1333