1 //===- SampleProfile.cpp - Incorporate sample profiles into the IR --------===// 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 implements the SampleProfileLoader transformation. This pass 10 // reads a profile file generated by a sampling profiler (e.g. Linux Perf - 11 // http://perf.wiki.kernel.org/) and generates IR metadata to reflect the 12 // profile information in the given profile. 13 // 14 // This pass generates branch weight annotations on the IR: 15 // 16 // - prof: Represents branch weights. This annotation is added to branches 17 // to indicate the weights of each edge coming out of the branch. 18 // The weight of each edge is the weight of the target block for 19 // that edge. The weight of a block B is computed as the maximum 20 // number of samples found in B. 21 // 22 //===----------------------------------------------------------------------===// 23 24 #include "llvm/Transforms/IPO/SampleProfile.h" 25 #include "llvm/ADT/ArrayRef.h" 26 #include "llvm/ADT/DenseMap.h" 27 #include "llvm/ADT/DenseSet.h" 28 #include "llvm/ADT/PriorityQueue.h" 29 #include "llvm/ADT/SCCIterator.h" 30 #include "llvm/ADT/SmallVector.h" 31 #include "llvm/ADT/Statistic.h" 32 #include "llvm/ADT/StringMap.h" 33 #include "llvm/ADT/StringRef.h" 34 #include "llvm/ADT/Twine.h" 35 #include "llvm/Analysis/AssumptionCache.h" 36 #include "llvm/Analysis/BlockFrequencyInfoImpl.h" 37 #include "llvm/Analysis/CallGraph.h" 38 #include "llvm/Analysis/InlineAdvisor.h" 39 #include "llvm/Analysis/InlineCost.h" 40 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 41 #include "llvm/Analysis/ProfileSummaryInfo.h" 42 #include "llvm/Analysis/ReplayInlineAdvisor.h" 43 #include "llvm/Analysis/TargetLibraryInfo.h" 44 #include "llvm/Analysis/TargetTransformInfo.h" 45 #include "llvm/IR/BasicBlock.h" 46 #include "llvm/IR/DebugLoc.h" 47 #include "llvm/IR/DiagnosticInfo.h" 48 #include "llvm/IR/Function.h" 49 #include "llvm/IR/GlobalValue.h" 50 #include "llvm/IR/InstrTypes.h" 51 #include "llvm/IR/Instruction.h" 52 #include "llvm/IR/Instructions.h" 53 #include "llvm/IR/IntrinsicInst.h" 54 #include "llvm/IR/LLVMContext.h" 55 #include "llvm/IR/MDBuilder.h" 56 #include "llvm/IR/Module.h" 57 #include "llvm/IR/PassManager.h" 58 #include "llvm/IR/PseudoProbe.h" 59 #include "llvm/IR/ValueSymbolTable.h" 60 #include "llvm/InitializePasses.h" 61 #include "llvm/Pass.h" 62 #include "llvm/ProfileData/InstrProf.h" 63 #include "llvm/ProfileData/SampleProf.h" 64 #include "llvm/ProfileData/SampleProfReader.h" 65 #include "llvm/Support/Casting.h" 66 #include "llvm/Support/CommandLine.h" 67 #include "llvm/Support/Debug.h" 68 #include "llvm/Support/ErrorOr.h" 69 #include "llvm/Support/raw_ostream.h" 70 #include "llvm/Transforms/IPO.h" 71 #include "llvm/Transforms/IPO/ProfiledCallGraph.h" 72 #include "llvm/Transforms/IPO/SampleContextTracker.h" 73 #include "llvm/Transforms/IPO/SampleProfileProbe.h" 74 #include "llvm/Transforms/Instrumentation.h" 75 #include "llvm/Transforms/Utils/CallPromotionUtils.h" 76 #include "llvm/Transforms/Utils/Cloning.h" 77 #include "llvm/Transforms/Utils/SampleProfileLoaderBaseImpl.h" 78 #include "llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h" 79 #include <algorithm> 80 #include <cassert> 81 #include <cstdint> 82 #include <functional> 83 #include <limits> 84 #include <map> 85 #include <memory> 86 #include <queue> 87 #include <string> 88 #include <system_error> 89 #include <utility> 90 #include <vector> 91 92 using namespace llvm; 93 using namespace sampleprof; 94 using namespace llvm::sampleprofutil; 95 using ProfileCount = Function::ProfileCount; 96 #define DEBUG_TYPE "sample-profile" 97 #define CSINLINE_DEBUG DEBUG_TYPE "-inline" 98 99 STATISTIC(NumCSInlined, 100 "Number of functions inlined with context sensitive profile"); 101 STATISTIC(NumCSNotInlined, 102 "Number of functions not inlined with context sensitive profile"); 103 STATISTIC(NumMismatchedProfile, 104 "Number of functions with CFG mismatched profile"); 105 STATISTIC(NumMatchedProfile, "Number of functions with CFG matched profile"); 106 STATISTIC(NumDuplicatedInlinesite, 107 "Number of inlined callsites with a partial distribution factor"); 108 109 STATISTIC(NumCSInlinedHitMinLimit, 110 "Number of functions with FDO inline stopped due to min size limit"); 111 STATISTIC(NumCSInlinedHitMaxLimit, 112 "Number of functions with FDO inline stopped due to max size limit"); 113 STATISTIC( 114 NumCSInlinedHitGrowthLimit, 115 "Number of functions with FDO inline stopped due to growth size limit"); 116 117 // Command line option to specify the file to read samples from. This is 118 // mainly used for debugging. 119 static cl::opt<std::string> SampleProfileFile( 120 "sample-profile-file", cl::init(""), cl::value_desc("filename"), 121 cl::desc("Profile file loaded by -sample-profile"), cl::Hidden); 122 123 // The named file contains a set of transformations that may have been applied 124 // to the symbol names between the program from which the sample data was 125 // collected and the current program's symbols. 126 static cl::opt<std::string> SampleProfileRemappingFile( 127 "sample-profile-remapping-file", cl::init(""), cl::value_desc("filename"), 128 cl::desc("Profile remapping file loaded by -sample-profile"), cl::Hidden); 129 130 static cl::opt<bool> ProfileSampleAccurate( 131 "profile-sample-accurate", cl::Hidden, cl::init(false), 132 cl::desc("If the sample profile is accurate, we will mark all un-sampled " 133 "callsite and function as having 0 samples. Otherwise, treat " 134 "un-sampled callsites and functions conservatively as unknown. ")); 135 136 static cl::opt<bool> ProfileSampleBlockAccurate( 137 "profile-sample-block-accurate", cl::Hidden, cl::init(false), 138 cl::desc("If the sample profile is accurate, we will mark all un-sampled " 139 "branches and calls as having 0 samples. Otherwise, treat " 140 "them conservatively as unknown. ")); 141 142 static cl::opt<bool> ProfileAccurateForSymsInList( 143 "profile-accurate-for-symsinlist", cl::Hidden, cl::init(true), 144 cl::desc("For symbols in profile symbol list, regard their profiles to " 145 "be accurate. It may be overriden by profile-sample-accurate. ")); 146 147 static cl::opt<bool> ProfileMergeInlinee( 148 "sample-profile-merge-inlinee", cl::Hidden, cl::init(true), 149 cl::desc("Merge past inlinee's profile to outline version if sample " 150 "profile loader decided not to inline a call site. It will " 151 "only be enabled when top-down order of profile loading is " 152 "enabled. ")); 153 154 static cl::opt<bool> ProfileTopDownLoad( 155 "sample-profile-top-down-load", cl::Hidden, cl::init(true), 156 cl::desc("Do profile annotation and inlining for functions in top-down " 157 "order of call graph during sample profile loading. It only " 158 "works for new pass manager. ")); 159 160 static cl::opt<bool> 161 UseProfiledCallGraph("use-profiled-call-graph", cl::init(true), cl::Hidden, 162 cl::desc("Process functions in a top-down order " 163 "defined by the profiled call graph when " 164 "-sample-profile-top-down-load is on.")); 165 cl::opt<bool> 166 SortProfiledSCC("sort-profiled-scc-member", cl::init(true), cl::Hidden, 167 cl::desc("Sort profiled recursion by edge weights.")); 168 169 static cl::opt<bool> ProfileSizeInline( 170 "sample-profile-inline-size", cl::Hidden, cl::init(false), 171 cl::desc("Inline cold call sites in profile loader if it's beneficial " 172 "for code size.")); 173 174 // Since profiles are consumed by many passes, turning on this option has 175 // side effects. For instance, pre-link SCC inliner would see merged profiles 176 // and inline the hot functions (that are skipped in this pass). 177 static cl::opt<bool> DisableSampleLoaderInlining( 178 "disable-sample-loader-inlining", cl::Hidden, cl::init(false), 179 cl::desc("If true, artifically skip inline transformation in sample-loader " 180 "pass, and merge (or scale) profiles (as configured by " 181 "--sample-profile-merge-inlinee).")); 182 183 cl::opt<int> ProfileInlineGrowthLimit( 184 "sample-profile-inline-growth-limit", cl::Hidden, cl::init(12), 185 cl::desc("The size growth ratio limit for proirity-based sample profile " 186 "loader inlining.")); 187 188 cl::opt<int> ProfileInlineLimitMin( 189 "sample-profile-inline-limit-min", cl::Hidden, cl::init(100), 190 cl::desc("The lower bound of size growth limit for " 191 "proirity-based sample profile loader inlining.")); 192 193 cl::opt<int> ProfileInlineLimitMax( 194 "sample-profile-inline-limit-max", cl::Hidden, cl::init(10000), 195 cl::desc("The upper bound of size growth limit for " 196 "proirity-based sample profile loader inlining.")); 197 198 cl::opt<int> SampleHotCallSiteThreshold( 199 "sample-profile-hot-inline-threshold", cl::Hidden, cl::init(3000), 200 cl::desc("Hot callsite threshold for proirity-based sample profile loader " 201 "inlining.")); 202 203 cl::opt<int> SampleColdCallSiteThreshold( 204 "sample-profile-cold-inline-threshold", cl::Hidden, cl::init(45), 205 cl::desc("Threshold for inlining cold callsites")); 206 207 static cl::opt<unsigned> ProfileICPRelativeHotness( 208 "sample-profile-icp-relative-hotness", cl::Hidden, cl::init(25), 209 cl::desc( 210 "Relative hotness percentage threshold for indirect " 211 "call promotion in proirity-based sample profile loader inlining.")); 212 213 static cl::opt<unsigned> ProfileICPRelativeHotnessSkip( 214 "sample-profile-icp-relative-hotness-skip", cl::Hidden, cl::init(1), 215 cl::desc( 216 "Skip relative hotness check for ICP up to given number of targets.")); 217 218 static cl::opt<bool> CallsitePrioritizedInline( 219 "sample-profile-prioritized-inline", cl::Hidden, 220 221 cl::desc("Use call site prioritized inlining for sample profile loader." 222 "Currently only CSSPGO is supported.")); 223 224 static cl::opt<bool> UsePreInlinerDecision( 225 "sample-profile-use-preinliner", cl::Hidden, 226 227 cl::desc("Use the preinliner decisions stored in profile context.")); 228 229 static cl::opt<bool> AllowRecursiveInline( 230 "sample-profile-recursive-inline", cl::Hidden, 231 232 cl::desc("Allow sample loader inliner to inline recursive calls.")); 233 234 static cl::opt<std::string> ProfileInlineReplayFile( 235 "sample-profile-inline-replay", cl::init(""), cl::value_desc("filename"), 236 cl::desc( 237 "Optimization remarks file containing inline remarks to be replayed " 238 "by inlining from sample profile loader."), 239 cl::Hidden); 240 241 static cl::opt<ReplayInlinerSettings::Scope> ProfileInlineReplayScope( 242 "sample-profile-inline-replay-scope", 243 cl::init(ReplayInlinerSettings::Scope::Function), 244 cl::values(clEnumValN(ReplayInlinerSettings::Scope::Function, "Function", 245 "Replay on functions that have remarks associated " 246 "with them (default)"), 247 clEnumValN(ReplayInlinerSettings::Scope::Module, "Module", 248 "Replay on the entire module")), 249 cl::desc("Whether inline replay should be applied to the entire " 250 "Module or just the Functions (default) that are present as " 251 "callers in remarks during sample profile inlining."), 252 cl::Hidden); 253 254 static cl::opt<ReplayInlinerSettings::Fallback> ProfileInlineReplayFallback( 255 "sample-profile-inline-replay-fallback", 256 cl::init(ReplayInlinerSettings::Fallback::Original), 257 cl::values( 258 clEnumValN( 259 ReplayInlinerSettings::Fallback::Original, "Original", 260 "All decisions not in replay send to original advisor (default)"), 261 clEnumValN(ReplayInlinerSettings::Fallback::AlwaysInline, 262 "AlwaysInline", "All decisions not in replay are inlined"), 263 clEnumValN(ReplayInlinerSettings::Fallback::NeverInline, "NeverInline", 264 "All decisions not in replay are not inlined")), 265 cl::desc("How sample profile inline replay treats sites that don't come " 266 "from the replay. Original: defers to original advisor, " 267 "AlwaysInline: inline all sites not in replay, NeverInline: " 268 "inline no sites not in replay"), 269 cl::Hidden); 270 271 static cl::opt<CallSiteFormat::Format> ProfileInlineReplayFormat( 272 "sample-profile-inline-replay-format", 273 cl::init(CallSiteFormat::Format::LineColumnDiscriminator), 274 cl::values( 275 clEnumValN(CallSiteFormat::Format::Line, "Line", "<Line Number>"), 276 clEnumValN(CallSiteFormat::Format::LineColumn, "LineColumn", 277 "<Line Number>:<Column Number>"), 278 clEnumValN(CallSiteFormat::Format::LineDiscriminator, 279 "LineDiscriminator", "<Line Number>.<Discriminator>"), 280 clEnumValN(CallSiteFormat::Format::LineColumnDiscriminator, 281 "LineColumnDiscriminator", 282 "<Line Number>:<Column Number>.<Discriminator> (default)")), 283 cl::desc("How sample profile inline replay file is formatted"), cl::Hidden); 284 285 static cl::opt<unsigned> 286 MaxNumPromotions("sample-profile-icp-max-prom", cl::init(3), cl::Hidden, 287 cl::desc("Max number of promotions for a single indirect " 288 "call callsite in sample profile loader")); 289 290 static cl::opt<bool> OverwriteExistingWeights( 291 "overwrite-existing-weights", cl::Hidden, cl::init(false), 292 cl::desc("Ignore existing branch weights on IR and always overwrite.")); 293 294 static cl::opt<bool> AnnotateSampleProfileInlinePhase( 295 "annotate-sample-profile-inline-phase", cl::Hidden, cl::init(false), 296 cl::desc("Annotate LTO phase (prelink / postlink), or main (no LTO) for " 297 "sample-profile inline pass name.")); 298 299 extern cl::opt<bool> EnableExtTspBlockPlacement; 300 301 namespace { 302 303 using BlockWeightMap = DenseMap<const BasicBlock *, uint64_t>; 304 using EquivalenceClassMap = DenseMap<const BasicBlock *, const BasicBlock *>; 305 using Edge = std::pair<const BasicBlock *, const BasicBlock *>; 306 using EdgeWeightMap = DenseMap<Edge, uint64_t>; 307 using BlockEdgeMap = 308 DenseMap<const BasicBlock *, SmallVector<const BasicBlock *, 8>>; 309 310 class GUIDToFuncNameMapper { 311 public: 312 GUIDToFuncNameMapper(Module &M, SampleProfileReader &Reader, 313 DenseMap<uint64_t, StringRef> &GUIDToFuncNameMap) 314 : CurrentReader(Reader), CurrentModule(M), 315 CurrentGUIDToFuncNameMap(GUIDToFuncNameMap) { 316 if (!CurrentReader.useMD5()) 317 return; 318 319 for (const auto &F : CurrentModule) { 320 StringRef OrigName = F.getName(); 321 CurrentGUIDToFuncNameMap.insert( 322 {Function::getGUID(OrigName), OrigName}); 323 324 // Local to global var promotion used by optimization like thinlto 325 // will rename the var and add suffix like ".llvm.xxx" to the 326 // original local name. In sample profile, the suffixes of function 327 // names are all stripped. Since it is possible that the mapper is 328 // built in post-thin-link phase and var promotion has been done, 329 // we need to add the substring of function name without the suffix 330 // into the GUIDToFuncNameMap. 331 StringRef CanonName = FunctionSamples::getCanonicalFnName(F); 332 if (CanonName != OrigName) 333 CurrentGUIDToFuncNameMap.insert( 334 {Function::getGUID(CanonName), CanonName}); 335 } 336 337 // Update GUIDToFuncNameMap for each function including inlinees. 338 SetGUIDToFuncNameMapForAll(&CurrentGUIDToFuncNameMap); 339 } 340 341 ~GUIDToFuncNameMapper() { 342 if (!CurrentReader.useMD5()) 343 return; 344 345 CurrentGUIDToFuncNameMap.clear(); 346 347 // Reset GUIDToFuncNameMap for of each function as they're no 348 // longer valid at this point. 349 SetGUIDToFuncNameMapForAll(nullptr); 350 } 351 352 private: 353 void SetGUIDToFuncNameMapForAll(DenseMap<uint64_t, StringRef> *Map) { 354 std::queue<FunctionSamples *> FSToUpdate; 355 for (auto &IFS : CurrentReader.getProfiles()) { 356 FSToUpdate.push(&IFS.second); 357 } 358 359 while (!FSToUpdate.empty()) { 360 FunctionSamples *FS = FSToUpdate.front(); 361 FSToUpdate.pop(); 362 FS->GUIDToFuncNameMap = Map; 363 for (const auto &ICS : FS->getCallsiteSamples()) { 364 const FunctionSamplesMap &FSMap = ICS.second; 365 for (auto &IFS : FSMap) { 366 FunctionSamples &FS = const_cast<FunctionSamples &>(IFS.second); 367 FSToUpdate.push(&FS); 368 } 369 } 370 } 371 } 372 373 SampleProfileReader &CurrentReader; 374 Module &CurrentModule; 375 DenseMap<uint64_t, StringRef> &CurrentGUIDToFuncNameMap; 376 }; 377 378 // Inline candidate used by iterative callsite prioritized inliner 379 struct InlineCandidate { 380 CallBase *CallInstr; 381 const FunctionSamples *CalleeSamples; 382 // Prorated callsite count, which will be used to guide inlining. For example, 383 // if a callsite is duplicated in LTO prelink, then in LTO postlink the two 384 // copies will get their own distribution factors and their prorated counts 385 // will be used to decide if they should be inlined independently. 386 uint64_t CallsiteCount; 387 // Call site distribution factor to prorate the profile samples for a 388 // duplicated callsite. Default value is 1.0. 389 float CallsiteDistribution; 390 }; 391 392 // Inline candidate comparer using call site weight 393 struct CandidateComparer { 394 bool operator()(const InlineCandidate &LHS, const InlineCandidate &RHS) { 395 if (LHS.CallsiteCount != RHS.CallsiteCount) 396 return LHS.CallsiteCount < RHS.CallsiteCount; 397 398 const FunctionSamples *LCS = LHS.CalleeSamples; 399 const FunctionSamples *RCS = RHS.CalleeSamples; 400 assert(LCS && RCS && "Expect non-null FunctionSamples"); 401 402 // Tie breaker using number of samples try to favor smaller functions first 403 if (LCS->getBodySamples().size() != RCS->getBodySamples().size()) 404 return LCS->getBodySamples().size() > RCS->getBodySamples().size(); 405 406 // Tie breaker using GUID so we have stable/deterministic inlining order 407 return LCS->getGUID(LCS->getName()) < RCS->getGUID(RCS->getName()); 408 } 409 }; 410 411 using CandidateQueue = 412 PriorityQueue<InlineCandidate, std::vector<InlineCandidate>, 413 CandidateComparer>; 414 415 /// Sample profile pass. 416 /// 417 /// This pass reads profile data from the file specified by 418 /// -sample-profile-file and annotates every affected function with the 419 /// profile information found in that file. 420 class SampleProfileLoader final 421 : public SampleProfileLoaderBaseImpl<BasicBlock> { 422 public: 423 SampleProfileLoader( 424 StringRef Name, StringRef RemapName, ThinOrFullLTOPhase LTOPhase, 425 std::function<AssumptionCache &(Function &)> GetAssumptionCache, 426 std::function<TargetTransformInfo &(Function &)> GetTargetTransformInfo, 427 std::function<const TargetLibraryInfo &(Function &)> GetTLI) 428 : SampleProfileLoaderBaseImpl(std::string(Name), std::string(RemapName)), 429 GetAC(std::move(GetAssumptionCache)), 430 GetTTI(std::move(GetTargetTransformInfo)), GetTLI(std::move(GetTLI)), 431 LTOPhase(LTOPhase), 432 AnnotatedPassName(AnnotateSampleProfileInlinePhase 433 ? llvm::AnnotateInlinePassName(InlineContext{ 434 LTOPhase, InlinePass::SampleProfileInliner}) 435 : CSINLINE_DEBUG) {} 436 437 bool doInitialization(Module &M, FunctionAnalysisManager *FAM = nullptr); 438 bool runOnModule(Module &M, ModuleAnalysisManager *AM, 439 ProfileSummaryInfo *_PSI, CallGraph *CG); 440 441 protected: 442 bool runOnFunction(Function &F, ModuleAnalysisManager *AM); 443 bool emitAnnotations(Function &F); 444 ErrorOr<uint64_t> getInstWeight(const Instruction &I) override; 445 ErrorOr<uint64_t> getProbeWeight(const Instruction &I); 446 const FunctionSamples *findCalleeFunctionSamples(const CallBase &I) const; 447 const FunctionSamples * 448 findFunctionSamples(const Instruction &I) const override; 449 std::vector<const FunctionSamples *> 450 findIndirectCallFunctionSamples(const Instruction &I, uint64_t &Sum) const; 451 void findExternalInlineCandidate(CallBase *CB, const FunctionSamples *Samples, 452 DenseSet<GlobalValue::GUID> &InlinedGUIDs, 453 const StringMap<Function *> &SymbolMap, 454 uint64_t Threshold); 455 // Attempt to promote indirect call and also inline the promoted call 456 bool tryPromoteAndInlineCandidate( 457 Function &F, InlineCandidate &Candidate, uint64_t SumOrigin, 458 uint64_t &Sum, SmallVector<CallBase *, 8> *InlinedCallSites = nullptr); 459 460 bool inlineHotFunctions(Function &F, 461 DenseSet<GlobalValue::GUID> &InlinedGUIDs); 462 Optional<InlineCost> getExternalInlineAdvisorCost(CallBase &CB); 463 bool getExternalInlineAdvisorShouldInline(CallBase &CB); 464 InlineCost shouldInlineCandidate(InlineCandidate &Candidate); 465 bool getInlineCandidate(InlineCandidate *NewCandidate, CallBase *CB); 466 bool 467 tryInlineCandidate(InlineCandidate &Candidate, 468 SmallVector<CallBase *, 8> *InlinedCallSites = nullptr); 469 bool 470 inlineHotFunctionsWithPriority(Function &F, 471 DenseSet<GlobalValue::GUID> &InlinedGUIDs); 472 // Inline cold/small functions in addition to hot ones 473 bool shouldInlineColdCallee(CallBase &CallInst); 474 void emitOptimizationRemarksForInlineCandidates( 475 const SmallVectorImpl<CallBase *> &Candidates, const Function &F, 476 bool Hot); 477 void promoteMergeNotInlinedContextSamples( 478 DenseMap<CallBase *, const FunctionSamples *> NonInlinedCallSites, 479 const Function &F); 480 std::vector<Function *> buildFunctionOrder(Module &M, CallGraph *CG); 481 std::unique_ptr<ProfiledCallGraph> buildProfiledCallGraph(CallGraph &CG); 482 void generateMDProfMetadata(Function &F); 483 484 /// Map from function name to Function *. Used to find the function from 485 /// the function name. If the function name contains suffix, additional 486 /// entry is added to map from the stripped name to the function if there 487 /// is one-to-one mapping. 488 StringMap<Function *> SymbolMap; 489 490 std::function<AssumptionCache &(Function &)> GetAC; 491 std::function<TargetTransformInfo &(Function &)> GetTTI; 492 std::function<const TargetLibraryInfo &(Function &)> GetTLI; 493 494 /// Profile tracker for different context. 495 std::unique_ptr<SampleContextTracker> ContextTracker; 496 497 /// Flag indicating which LTO/ThinLTO phase the pass is invoked in. 498 /// 499 /// We need to know the LTO phase because for example in ThinLTOPrelink 500 /// phase, in annotation, we should not promote indirect calls. Instead, 501 /// we will mark GUIDs that needs to be annotated to the function. 502 const ThinOrFullLTOPhase LTOPhase; 503 const std::string AnnotatedPassName; 504 505 /// Profle Symbol list tells whether a function name appears in the binary 506 /// used to generate the current profile. 507 std::unique_ptr<ProfileSymbolList> PSL; 508 509 /// Total number of samples collected in this profile. 510 /// 511 /// This is the sum of all the samples collected in all the functions executed 512 /// at runtime. 513 uint64_t TotalCollectedSamples = 0; 514 515 // Information recorded when we declined to inline a call site 516 // because we have determined it is too cold is accumulated for 517 // each callee function. Initially this is just the entry count. 518 struct NotInlinedProfileInfo { 519 uint64_t entryCount; 520 }; 521 DenseMap<Function *, NotInlinedProfileInfo> notInlinedCallInfo; 522 523 // GUIDToFuncNameMap saves the mapping from GUID to the symbol name, for 524 // all the function symbols defined or declared in current module. 525 DenseMap<uint64_t, StringRef> GUIDToFuncNameMap; 526 527 // All the Names used in FunctionSamples including outline function 528 // names, inline instance names and call target names. 529 StringSet<> NamesInProfile; 530 531 // For symbol in profile symbol list, whether to regard their profiles 532 // to be accurate. It is mainly decided by existance of profile symbol 533 // list and -profile-accurate-for-symsinlist flag, but it can be 534 // overriden by -profile-sample-accurate or profile-sample-accurate 535 // attribute. 536 bool ProfAccForSymsInList; 537 538 // External inline advisor used to replay inline decision from remarks. 539 std::unique_ptr<InlineAdvisor> ExternalInlineAdvisor; 540 541 // A pseudo probe helper to correlate the imported sample counts. 542 std::unique_ptr<PseudoProbeManager> ProbeManager; 543 544 private: 545 const char *getAnnotatedRemarkPassName() const { 546 return AnnotatedPassName.c_str(); 547 } 548 }; 549 550 class SampleProfileLoaderLegacyPass : public ModulePass { 551 public: 552 // Class identification, replacement for typeinfo 553 static char ID; 554 555 SampleProfileLoaderLegacyPass( 556 StringRef Name = SampleProfileFile, 557 ThinOrFullLTOPhase LTOPhase = ThinOrFullLTOPhase::None) 558 : ModulePass(ID), SampleLoader( 559 Name, SampleProfileRemappingFile, LTOPhase, 560 [&](Function &F) -> AssumptionCache & { 561 return ACT->getAssumptionCache(F); 562 }, 563 [&](Function &F) -> TargetTransformInfo & { 564 return TTIWP->getTTI(F); 565 }, 566 [&](Function &F) -> TargetLibraryInfo & { 567 return TLIWP->getTLI(F); 568 }) { 569 initializeSampleProfileLoaderLegacyPassPass( 570 *PassRegistry::getPassRegistry()); 571 } 572 573 void dump() { SampleLoader.dump(); } 574 575 bool doInitialization(Module &M) override { 576 return SampleLoader.doInitialization(M); 577 } 578 579 StringRef getPassName() const override { return "Sample profile pass"; } 580 bool runOnModule(Module &M) override; 581 582 void getAnalysisUsage(AnalysisUsage &AU) const override { 583 AU.addRequired<AssumptionCacheTracker>(); 584 AU.addRequired<TargetTransformInfoWrapperPass>(); 585 AU.addRequired<TargetLibraryInfoWrapperPass>(); 586 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 587 } 588 589 private: 590 SampleProfileLoader SampleLoader; 591 AssumptionCacheTracker *ACT = nullptr; 592 TargetTransformInfoWrapperPass *TTIWP = nullptr; 593 TargetLibraryInfoWrapperPass *TLIWP = nullptr; 594 }; 595 596 } // end anonymous namespace 597 598 ErrorOr<uint64_t> SampleProfileLoader::getInstWeight(const Instruction &Inst) { 599 if (FunctionSamples::ProfileIsProbeBased) 600 return getProbeWeight(Inst); 601 602 const DebugLoc &DLoc = Inst.getDebugLoc(); 603 if (!DLoc) 604 return std::error_code(); 605 606 // Ignore all intrinsics, phinodes and branch instructions. 607 // Branch and phinodes instruction usually contains debug info from sources 608 // outside of the residing basic block, thus we ignore them during annotation. 609 if (isa<BranchInst>(Inst) || isa<IntrinsicInst>(Inst) || isa<PHINode>(Inst)) 610 return std::error_code(); 611 612 // For non-CS profile, if a direct call/invoke instruction is inlined in 613 // profile (findCalleeFunctionSamples returns non-empty result), but not 614 // inlined here, it means that the inlined callsite has no sample, thus the 615 // call instruction should have 0 count. 616 // For CS profile, the callsite count of previously inlined callees is 617 // populated with the entry count of the callees. 618 if (!FunctionSamples::ProfileIsCS) 619 if (const auto *CB = dyn_cast<CallBase>(&Inst)) 620 if (!CB->isIndirectCall() && findCalleeFunctionSamples(*CB)) 621 return 0; 622 623 return getInstWeightImpl(Inst); 624 } 625 626 // Here use error_code to represent: 1) The dangling probe. 2) Ignore the weight 627 // of non-probe instruction. So if all instructions of the BB give error_code, 628 // tell the inference algorithm to infer the BB weight. 629 ErrorOr<uint64_t> SampleProfileLoader::getProbeWeight(const Instruction &Inst) { 630 assert(FunctionSamples::ProfileIsProbeBased && 631 "Profile is not pseudo probe based"); 632 Optional<PseudoProbe> Probe = extractProbe(Inst); 633 // Ignore the non-probe instruction. If none of the instruction in the BB is 634 // probe, we choose to infer the BB's weight. 635 if (!Probe) 636 return std::error_code(); 637 638 const FunctionSamples *FS = findFunctionSamples(Inst); 639 // If none of the instruction has FunctionSample, we choose to return zero 640 // value sample to indicate the BB is cold. This could happen when the 641 // instruction is from inlinee and no profile data is found. 642 // FIXME: This should not be affected by the source drift issue as 1) if the 643 // newly added function is top-level inliner, it won't match the CFG checksum 644 // in the function profile or 2) if it's the inlinee, the inlinee should have 645 // a profile, otherwise it wouldn't be inlined. For non-probe based profile, 646 // we can improve it by adding a switch for profile-sample-block-accurate for 647 // block level counts in the future. 648 if (!FS) 649 return 0; 650 651 // For non-CS profile, If a direct call/invoke instruction is inlined in 652 // profile (findCalleeFunctionSamples returns non-empty result), but not 653 // inlined here, it means that the inlined callsite has no sample, thus the 654 // call instruction should have 0 count. 655 // For CS profile, the callsite count of previously inlined callees is 656 // populated with the entry count of the callees. 657 if (!FunctionSamples::ProfileIsCS) 658 if (const auto *CB = dyn_cast<CallBase>(&Inst)) 659 if (!CB->isIndirectCall() && findCalleeFunctionSamples(*CB)) 660 return 0; 661 662 const ErrorOr<uint64_t> &R = FS->findSamplesAt(Probe->Id, 0); 663 if (R) { 664 uint64_t Samples = R.get() * Probe->Factor; 665 bool FirstMark = CoverageTracker.markSamplesUsed(FS, Probe->Id, 0, Samples); 666 if (FirstMark) { 667 ORE->emit([&]() { 668 OptimizationRemarkAnalysis Remark(DEBUG_TYPE, "AppliedSamples", &Inst); 669 Remark << "Applied " << ore::NV("NumSamples", Samples); 670 Remark << " samples from profile (ProbeId="; 671 Remark << ore::NV("ProbeId", Probe->Id); 672 Remark << ", Factor="; 673 Remark << ore::NV("Factor", Probe->Factor); 674 Remark << ", OriginalSamples="; 675 Remark << ore::NV("OriginalSamples", R.get()); 676 Remark << ")"; 677 return Remark; 678 }); 679 } 680 LLVM_DEBUG(dbgs() << " " << Probe->Id << ":" << Inst 681 << " - weight: " << R.get() << " - factor: " 682 << format("%0.2f", Probe->Factor) << ")\n"); 683 return Samples; 684 } 685 return R; 686 } 687 688 /// Get the FunctionSamples for a call instruction. 689 /// 690 /// The FunctionSamples of a call/invoke instruction \p Inst is the inlined 691 /// instance in which that call instruction is calling to. It contains 692 /// all samples that resides in the inlined instance. We first find the 693 /// inlined instance in which the call instruction is from, then we 694 /// traverse its children to find the callsite with the matching 695 /// location. 696 /// 697 /// \param Inst Call/Invoke instruction to query. 698 /// 699 /// \returns The FunctionSamples pointer to the inlined instance. 700 const FunctionSamples * 701 SampleProfileLoader::findCalleeFunctionSamples(const CallBase &Inst) const { 702 const DILocation *DIL = Inst.getDebugLoc(); 703 if (!DIL) { 704 return nullptr; 705 } 706 707 StringRef CalleeName; 708 if (Function *Callee = Inst.getCalledFunction()) 709 CalleeName = Callee->getName(); 710 711 if (FunctionSamples::ProfileIsCS) 712 return ContextTracker->getCalleeContextSamplesFor(Inst, CalleeName); 713 714 const FunctionSamples *FS = findFunctionSamples(Inst); 715 if (FS == nullptr) 716 return nullptr; 717 718 return FS->findFunctionSamplesAt(FunctionSamples::getCallSiteIdentifier(DIL), 719 CalleeName, Reader->getRemapper()); 720 } 721 722 /// Returns a vector of FunctionSamples that are the indirect call targets 723 /// of \p Inst. The vector is sorted by the total number of samples. Stores 724 /// the total call count of the indirect call in \p Sum. 725 std::vector<const FunctionSamples *> 726 SampleProfileLoader::findIndirectCallFunctionSamples( 727 const Instruction &Inst, uint64_t &Sum) const { 728 const DILocation *DIL = Inst.getDebugLoc(); 729 std::vector<const FunctionSamples *> R; 730 731 if (!DIL) { 732 return R; 733 } 734 735 auto FSCompare = [](const FunctionSamples *L, const FunctionSamples *R) { 736 assert(L && R && "Expect non-null FunctionSamples"); 737 if (L->getEntrySamples() != R->getEntrySamples()) 738 return L->getEntrySamples() > R->getEntrySamples(); 739 return FunctionSamples::getGUID(L->getName()) < 740 FunctionSamples::getGUID(R->getName()); 741 }; 742 743 if (FunctionSamples::ProfileIsCS) { 744 auto CalleeSamples = 745 ContextTracker->getIndirectCalleeContextSamplesFor(DIL); 746 if (CalleeSamples.empty()) 747 return R; 748 749 // For CSSPGO, we only use target context profile's entry count 750 // as that already includes both inlined callee and non-inlined ones.. 751 Sum = 0; 752 for (const auto *const FS : CalleeSamples) { 753 Sum += FS->getEntrySamples(); 754 R.push_back(FS); 755 } 756 llvm::sort(R, FSCompare); 757 return R; 758 } 759 760 const FunctionSamples *FS = findFunctionSamples(Inst); 761 if (FS == nullptr) 762 return R; 763 764 auto CallSite = FunctionSamples::getCallSiteIdentifier(DIL); 765 auto T = FS->findCallTargetMapAt(CallSite); 766 Sum = 0; 767 if (T) 768 for (const auto &T_C : T.get()) 769 Sum += T_C.second; 770 if (const FunctionSamplesMap *M = FS->findFunctionSamplesMapAt(CallSite)) { 771 if (M->empty()) 772 return R; 773 for (const auto &NameFS : *M) { 774 Sum += NameFS.second.getEntrySamples(); 775 R.push_back(&NameFS.second); 776 } 777 llvm::sort(R, FSCompare); 778 } 779 return R; 780 } 781 782 const FunctionSamples * 783 SampleProfileLoader::findFunctionSamples(const Instruction &Inst) const { 784 if (FunctionSamples::ProfileIsProbeBased) { 785 Optional<PseudoProbe> Probe = extractProbe(Inst); 786 if (!Probe) 787 return nullptr; 788 } 789 790 const DILocation *DIL = Inst.getDebugLoc(); 791 if (!DIL) 792 return Samples; 793 794 auto it = DILocation2SampleMap.try_emplace(DIL,nullptr); 795 if (it.second) { 796 if (FunctionSamples::ProfileIsCS) 797 it.first->second = ContextTracker->getContextSamplesFor(DIL); 798 else 799 it.first->second = 800 Samples->findFunctionSamples(DIL, Reader->getRemapper()); 801 } 802 return it.first->second; 803 } 804 805 /// Check whether the indirect call promotion history of \p Inst allows 806 /// the promotion for \p Candidate. 807 /// If the profile count for the promotion candidate \p Candidate is 808 /// NOMORE_ICP_MAGICNUM, it means \p Candidate has already been promoted 809 /// for \p Inst. If we already have at least MaxNumPromotions 810 /// NOMORE_ICP_MAGICNUM count values in the value profile of \p Inst, we 811 /// cannot promote for \p Inst anymore. 812 static bool doesHistoryAllowICP(const Instruction &Inst, StringRef Candidate) { 813 uint32_t NumVals = 0; 814 uint64_t TotalCount = 0; 815 std::unique_ptr<InstrProfValueData[]> ValueData = 816 std::make_unique<InstrProfValueData[]>(MaxNumPromotions); 817 bool Valid = 818 getValueProfDataFromInst(Inst, IPVK_IndirectCallTarget, MaxNumPromotions, 819 ValueData.get(), NumVals, TotalCount, true); 820 // No valid value profile so no promoted targets have been recorded 821 // before. Ok to do ICP. 822 if (!Valid) 823 return true; 824 825 unsigned NumPromoted = 0; 826 for (uint32_t I = 0; I < NumVals; I++) { 827 if (ValueData[I].Count != NOMORE_ICP_MAGICNUM) 828 continue; 829 830 // If the promotion candidate has NOMORE_ICP_MAGICNUM count in the 831 // metadata, it means the candidate has been promoted for this 832 // indirect call. 833 if (ValueData[I].Value == Function::getGUID(Candidate)) 834 return false; 835 NumPromoted++; 836 // If already have MaxNumPromotions promotion, don't do it anymore. 837 if (NumPromoted == MaxNumPromotions) 838 return false; 839 } 840 return true; 841 } 842 843 /// Update indirect call target profile metadata for \p Inst. 844 /// Usually \p Sum is the sum of counts of all the targets for \p Inst. 845 /// If it is 0, it means updateIDTMetaData is used to mark a 846 /// certain target to be promoted already. If it is not zero, 847 /// we expect to use it to update the total count in the value profile. 848 static void 849 updateIDTMetaData(Instruction &Inst, 850 const SmallVectorImpl<InstrProfValueData> &CallTargets, 851 uint64_t Sum) { 852 // Bail out early if MaxNumPromotions is zero. 853 // This prevents allocating an array of zero length below. 854 // 855 // Note `updateIDTMetaData` is called in two places so check 856 // `MaxNumPromotions` inside it. 857 if (MaxNumPromotions == 0) 858 return; 859 uint32_t NumVals = 0; 860 // OldSum is the existing total count in the value profile data. 861 uint64_t OldSum = 0; 862 std::unique_ptr<InstrProfValueData[]> ValueData = 863 std::make_unique<InstrProfValueData[]>(MaxNumPromotions); 864 bool Valid = 865 getValueProfDataFromInst(Inst, IPVK_IndirectCallTarget, MaxNumPromotions, 866 ValueData.get(), NumVals, OldSum, true); 867 868 DenseMap<uint64_t, uint64_t> ValueCountMap; 869 if (Sum == 0) { 870 assert((CallTargets.size() == 1 && 871 CallTargets[0].Count == NOMORE_ICP_MAGICNUM) && 872 "If sum is 0, assume only one element in CallTargets " 873 "with count being NOMORE_ICP_MAGICNUM"); 874 // Initialize ValueCountMap with existing value profile data. 875 if (Valid) { 876 for (uint32_t I = 0; I < NumVals; I++) 877 ValueCountMap[ValueData[I].Value] = ValueData[I].Count; 878 } 879 auto Pair = 880 ValueCountMap.try_emplace(CallTargets[0].Value, CallTargets[0].Count); 881 // If the target already exists in value profile, decrease the total 882 // count OldSum and reset the target's count to NOMORE_ICP_MAGICNUM. 883 if (!Pair.second) { 884 OldSum -= Pair.first->second; 885 Pair.first->second = NOMORE_ICP_MAGICNUM; 886 } 887 Sum = OldSum; 888 } else { 889 // Initialize ValueCountMap with existing NOMORE_ICP_MAGICNUM 890 // counts in the value profile. 891 if (Valid) { 892 for (uint32_t I = 0; I < NumVals; I++) { 893 if (ValueData[I].Count == NOMORE_ICP_MAGICNUM) 894 ValueCountMap[ValueData[I].Value] = ValueData[I].Count; 895 } 896 } 897 898 for (const auto &Data : CallTargets) { 899 auto Pair = ValueCountMap.try_emplace(Data.Value, Data.Count); 900 if (Pair.second) 901 continue; 902 // The target represented by Data.Value has already been promoted. 903 // Keep the count as NOMORE_ICP_MAGICNUM in the profile and decrease 904 // Sum by Data.Count. 905 assert(Sum >= Data.Count && "Sum should never be less than Data.Count"); 906 Sum -= Data.Count; 907 } 908 } 909 910 SmallVector<InstrProfValueData, 8> NewCallTargets; 911 for (const auto &ValueCount : ValueCountMap) { 912 NewCallTargets.emplace_back( 913 InstrProfValueData{ValueCount.first, ValueCount.second}); 914 } 915 916 llvm::sort(NewCallTargets, 917 [](const InstrProfValueData &L, const InstrProfValueData &R) { 918 if (L.Count != R.Count) 919 return L.Count > R.Count; 920 return L.Value > R.Value; 921 }); 922 923 uint32_t MaxMDCount = 924 std::min(NewCallTargets.size(), static_cast<size_t>(MaxNumPromotions)); 925 annotateValueSite(*Inst.getParent()->getParent()->getParent(), Inst, 926 NewCallTargets, Sum, IPVK_IndirectCallTarget, MaxMDCount); 927 } 928 929 /// Attempt to promote indirect call and also inline the promoted call. 930 /// 931 /// \param F Caller function. 932 /// \param Candidate ICP and inline candidate. 933 /// \param SumOrigin Original sum of target counts for indirect call before 934 /// promoting given candidate. 935 /// \param Sum Prorated sum of remaining target counts for indirect call 936 /// after promoting given candidate. 937 /// \param InlinedCallSite Output vector for new call sites exposed after 938 /// inlining. 939 bool SampleProfileLoader::tryPromoteAndInlineCandidate( 940 Function &F, InlineCandidate &Candidate, uint64_t SumOrigin, uint64_t &Sum, 941 SmallVector<CallBase *, 8> *InlinedCallSite) { 942 // Bail out early if sample-loader inliner is disabled. 943 if (DisableSampleLoaderInlining) 944 return false; 945 946 // Bail out early if MaxNumPromotions is zero. 947 // This prevents allocating an array of zero length in callees below. 948 if (MaxNumPromotions == 0) 949 return false; 950 auto CalleeFunctionName = Candidate.CalleeSamples->getFuncName(); 951 auto R = SymbolMap.find(CalleeFunctionName); 952 if (R == SymbolMap.end() || !R->getValue()) 953 return false; 954 955 auto &CI = *Candidate.CallInstr; 956 if (!doesHistoryAllowICP(CI, R->getValue()->getName())) 957 return false; 958 959 const char *Reason = "Callee function not available"; 960 // R->getValue() != &F is to prevent promoting a recursive call. 961 // If it is a recursive call, we do not inline it as it could bloat 962 // the code exponentially. There is way to better handle this, e.g. 963 // clone the caller first, and inline the cloned caller if it is 964 // recursive. As llvm does not inline recursive calls, we will 965 // simply ignore it instead of handling it explicitly. 966 if (!R->getValue()->isDeclaration() && R->getValue()->getSubprogram() && 967 R->getValue()->hasFnAttribute("use-sample-profile") && 968 R->getValue() != &F && isLegalToPromote(CI, R->getValue(), &Reason)) { 969 // For promoted target, set its value with NOMORE_ICP_MAGICNUM count 970 // in the value profile metadata so the target won't be promoted again. 971 SmallVector<InstrProfValueData, 1> SortedCallTargets = {InstrProfValueData{ 972 Function::getGUID(R->getValue()->getName()), NOMORE_ICP_MAGICNUM}}; 973 updateIDTMetaData(CI, SortedCallTargets, 0); 974 975 auto *DI = &pgo::promoteIndirectCall( 976 CI, R->getValue(), Candidate.CallsiteCount, Sum, false, ORE); 977 if (DI) { 978 Sum -= Candidate.CallsiteCount; 979 // Do not prorate the indirect callsite distribution since the original 980 // distribution will be used to scale down non-promoted profile target 981 // counts later. By doing this we lose track of the real callsite count 982 // for the leftover indirect callsite as a trade off for accurate call 983 // target counts. 984 // TODO: Ideally we would have two separate factors, one for call site 985 // counts and one is used to prorate call target counts. 986 // Do not update the promoted direct callsite distribution at this 987 // point since the original distribution combined with the callee profile 988 // will be used to prorate callsites from the callee if inlined. Once not 989 // inlined, the direct callsite distribution should be prorated so that 990 // the it will reflect the real callsite counts. 991 Candidate.CallInstr = DI; 992 if (isa<CallInst>(DI) || isa<InvokeInst>(DI)) { 993 bool Inlined = tryInlineCandidate(Candidate, InlinedCallSite); 994 if (!Inlined) { 995 // Prorate the direct callsite distribution so that it reflects real 996 // callsite counts. 997 setProbeDistributionFactor( 998 *DI, static_cast<float>(Candidate.CallsiteCount) / SumOrigin); 999 } 1000 return Inlined; 1001 } 1002 } 1003 } else { 1004 LLVM_DEBUG(dbgs() << "\nFailed to promote indirect call to " 1005 << Candidate.CalleeSamples->getFuncName() << " because " 1006 << Reason << "\n"); 1007 } 1008 return false; 1009 } 1010 1011 bool SampleProfileLoader::shouldInlineColdCallee(CallBase &CallInst) { 1012 if (!ProfileSizeInline) 1013 return false; 1014 1015 Function *Callee = CallInst.getCalledFunction(); 1016 if (Callee == nullptr) 1017 return false; 1018 1019 InlineCost Cost = getInlineCost(CallInst, getInlineParams(), GetTTI(*Callee), 1020 GetAC, GetTLI); 1021 1022 if (Cost.isNever()) 1023 return false; 1024 1025 if (Cost.isAlways()) 1026 return true; 1027 1028 return Cost.getCost() <= SampleColdCallSiteThreshold; 1029 } 1030 1031 void SampleProfileLoader::emitOptimizationRemarksForInlineCandidates( 1032 const SmallVectorImpl<CallBase *> &Candidates, const Function &F, 1033 bool Hot) { 1034 for (auto I : Candidates) { 1035 Function *CalledFunction = I->getCalledFunction(); 1036 if (CalledFunction) { 1037 ORE->emit(OptimizationRemarkAnalysis(getAnnotatedRemarkPassName(), 1038 "InlineAttempt", I->getDebugLoc(), 1039 I->getParent()) 1040 << "previous inlining reattempted for " 1041 << (Hot ? "hotness: '" : "size: '") 1042 << ore::NV("Callee", CalledFunction) << "' into '" 1043 << ore::NV("Caller", &F) << "'"); 1044 } 1045 } 1046 } 1047 1048 void SampleProfileLoader::findExternalInlineCandidate( 1049 CallBase *CB, const FunctionSamples *Samples, 1050 DenseSet<GlobalValue::GUID> &InlinedGUIDs, 1051 const StringMap<Function *> &SymbolMap, uint64_t Threshold) { 1052 1053 // If ExternalInlineAdvisor wants to inline an external function 1054 // make sure it's imported 1055 if (CB && getExternalInlineAdvisorShouldInline(*CB)) { 1056 // Samples may not exist for replayed function, if so 1057 // just add the direct GUID and move on 1058 if (!Samples) { 1059 InlinedGUIDs.insert( 1060 FunctionSamples::getGUID(CB->getCalledFunction()->getName())); 1061 return; 1062 } 1063 // Otherwise, drop the threshold to import everything that we can 1064 Threshold = 0; 1065 } 1066 1067 assert(Samples && "expect non-null caller profile"); 1068 1069 // For AutoFDO profile, retrieve candidate profiles by walking over 1070 // the nested inlinee profiles. 1071 if (!FunctionSamples::ProfileIsCS) { 1072 Samples->findInlinedFunctions(InlinedGUIDs, SymbolMap, Threshold); 1073 return; 1074 } 1075 1076 ContextTrieNode *Caller = ContextTracker->getContextNodeForProfile(Samples); 1077 std::queue<ContextTrieNode *> CalleeList; 1078 CalleeList.push(Caller); 1079 while (!CalleeList.empty()) { 1080 ContextTrieNode *Node = CalleeList.front(); 1081 CalleeList.pop(); 1082 FunctionSamples *CalleeSample = Node->getFunctionSamples(); 1083 // For CSSPGO profile, retrieve candidate profile by walking over the 1084 // trie built for context profile. Note that also take call targets 1085 // even if callee doesn't have a corresponding context profile. 1086 if (!CalleeSample) 1087 continue; 1088 1089 // If pre-inliner decision is used, honor that for importing as well. 1090 bool PreInline = 1091 UsePreInlinerDecision && 1092 CalleeSample->getContext().hasAttribute(ContextShouldBeInlined); 1093 if (!PreInline && CalleeSample->getEntrySamples() < Threshold) 1094 continue; 1095 1096 StringRef Name = CalleeSample->getFuncName(); 1097 Function *Func = SymbolMap.lookup(Name); 1098 // Add to the import list only when it's defined out of module. 1099 if (!Func || Func->isDeclaration()) 1100 InlinedGUIDs.insert(FunctionSamples::getGUID(CalleeSample->getName())); 1101 1102 // Import hot CallTargets, which may not be available in IR because full 1103 // profile annotation cannot be done until backend compilation in ThinLTO. 1104 for (const auto &BS : CalleeSample->getBodySamples()) 1105 for (const auto &TS : BS.second.getCallTargets()) 1106 if (TS.getValue() > Threshold) { 1107 StringRef CalleeName = CalleeSample->getFuncName(TS.getKey()); 1108 const Function *Callee = SymbolMap.lookup(CalleeName); 1109 if (!Callee || Callee->isDeclaration()) 1110 InlinedGUIDs.insert(FunctionSamples::getGUID(TS.getKey())); 1111 } 1112 1113 // Import hot child context profile associted with callees. Note that this 1114 // may have some overlap with the call target loop above, but doing this 1115 // based child context profile again effectively allow us to use the max of 1116 // entry count and call target count to determine importing. 1117 for (auto &Child : Node->getAllChildContext()) { 1118 ContextTrieNode *CalleeNode = &Child.second; 1119 CalleeList.push(CalleeNode); 1120 } 1121 } 1122 } 1123 1124 /// Iteratively inline hot callsites of a function. 1125 /// 1126 /// Iteratively traverse all callsites of the function \p F, so as to 1127 /// find out callsites with corresponding inline instances. 1128 /// 1129 /// For such callsites, 1130 /// - If it is hot enough, inline the callsites and adds callsites of the callee 1131 /// into the caller. If the call is an indirect call, first promote 1132 /// it to direct call. Each indirect call is limited with a single target. 1133 /// 1134 /// - If a callsite is not inlined, merge the its profile to the outline 1135 /// version (if --sample-profile-merge-inlinee is true), or scale the 1136 /// counters of standalone function based on the profile of inlined 1137 /// instances (if --sample-profile-merge-inlinee is false). 1138 /// 1139 /// Later passes may consume the updated profiles. 1140 /// 1141 /// \param F function to perform iterative inlining. 1142 /// \param InlinedGUIDs a set to be updated to include all GUIDs that are 1143 /// inlined in the profiled binary. 1144 /// 1145 /// \returns True if there is any inline happened. 1146 bool SampleProfileLoader::inlineHotFunctions( 1147 Function &F, DenseSet<GlobalValue::GUID> &InlinedGUIDs) { 1148 // ProfAccForSymsInList is used in callsiteIsHot. The assertion makes sure 1149 // Profile symbol list is ignored when profile-sample-accurate is on. 1150 assert((!ProfAccForSymsInList || 1151 (!ProfileSampleAccurate && 1152 !F.hasFnAttribute("profile-sample-accurate"))) && 1153 "ProfAccForSymsInList should be false when profile-sample-accurate " 1154 "is enabled"); 1155 1156 DenseMap<CallBase *, const FunctionSamples *> LocalNotInlinedCallSites; 1157 bool Changed = false; 1158 bool LocalChanged = true; 1159 while (LocalChanged) { 1160 LocalChanged = false; 1161 SmallVector<CallBase *, 10> CIS; 1162 for (auto &BB : F) { 1163 bool Hot = false; 1164 SmallVector<CallBase *, 10> AllCandidates; 1165 SmallVector<CallBase *, 10> ColdCandidates; 1166 for (auto &I : BB.getInstList()) { 1167 const FunctionSamples *FS = nullptr; 1168 if (auto *CB = dyn_cast<CallBase>(&I)) { 1169 if (!isa<IntrinsicInst>(I)) { 1170 if ((FS = findCalleeFunctionSamples(*CB))) { 1171 assert((!FunctionSamples::UseMD5 || FS->GUIDToFuncNameMap) && 1172 "GUIDToFuncNameMap has to be populated"); 1173 AllCandidates.push_back(CB); 1174 if (FS->getEntrySamples() > 0 || FunctionSamples::ProfileIsCS) 1175 LocalNotInlinedCallSites.try_emplace(CB, FS); 1176 if (callsiteIsHot(FS, PSI, ProfAccForSymsInList)) 1177 Hot = true; 1178 else if (shouldInlineColdCallee(*CB)) 1179 ColdCandidates.push_back(CB); 1180 } else if (getExternalInlineAdvisorShouldInline(*CB)) { 1181 AllCandidates.push_back(CB); 1182 } 1183 } 1184 } 1185 } 1186 if (Hot || ExternalInlineAdvisor) { 1187 CIS.insert(CIS.begin(), AllCandidates.begin(), AllCandidates.end()); 1188 emitOptimizationRemarksForInlineCandidates(AllCandidates, F, true); 1189 } else { 1190 CIS.insert(CIS.begin(), ColdCandidates.begin(), ColdCandidates.end()); 1191 emitOptimizationRemarksForInlineCandidates(ColdCandidates, F, false); 1192 } 1193 } 1194 for (CallBase *I : CIS) { 1195 Function *CalledFunction = I->getCalledFunction(); 1196 InlineCandidate Candidate = {I, LocalNotInlinedCallSites.lookup(I), 1197 0 /* dummy count */, 1198 1.0 /* dummy distribution factor */}; 1199 // Do not inline recursive calls. 1200 if (CalledFunction == &F) 1201 continue; 1202 if (I->isIndirectCall()) { 1203 uint64_t Sum; 1204 for (const auto *FS : findIndirectCallFunctionSamples(*I, Sum)) { 1205 uint64_t SumOrigin = Sum; 1206 if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) { 1207 findExternalInlineCandidate(I, FS, InlinedGUIDs, SymbolMap, 1208 PSI->getOrCompHotCountThreshold()); 1209 continue; 1210 } 1211 if (!callsiteIsHot(FS, PSI, ProfAccForSymsInList)) 1212 continue; 1213 1214 Candidate = {I, FS, FS->getEntrySamples(), 1.0}; 1215 if (tryPromoteAndInlineCandidate(F, Candidate, SumOrigin, Sum)) { 1216 LocalNotInlinedCallSites.erase(I); 1217 LocalChanged = true; 1218 } 1219 } 1220 } else if (CalledFunction && CalledFunction->getSubprogram() && 1221 !CalledFunction->isDeclaration()) { 1222 if (tryInlineCandidate(Candidate)) { 1223 LocalNotInlinedCallSites.erase(I); 1224 LocalChanged = true; 1225 } 1226 } else if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) { 1227 findExternalInlineCandidate(I, findCalleeFunctionSamples(*I), 1228 InlinedGUIDs, SymbolMap, 1229 PSI->getOrCompHotCountThreshold()); 1230 } 1231 } 1232 Changed |= LocalChanged; 1233 } 1234 1235 // For CS profile, profile for not inlined context will be merged when 1236 // base profile is being retrieved. 1237 if (!FunctionSamples::ProfileIsCS) 1238 promoteMergeNotInlinedContextSamples(LocalNotInlinedCallSites, F); 1239 return Changed; 1240 } 1241 1242 bool SampleProfileLoader::tryInlineCandidate( 1243 InlineCandidate &Candidate, SmallVector<CallBase *, 8> *InlinedCallSites) { 1244 // Do not attempt to inline a candidate if 1245 // --disable-sample-loader-inlining is true. 1246 if (DisableSampleLoaderInlining) 1247 return false; 1248 1249 CallBase &CB = *Candidate.CallInstr; 1250 Function *CalledFunction = CB.getCalledFunction(); 1251 assert(CalledFunction && "Expect a callee with definition"); 1252 DebugLoc DLoc = CB.getDebugLoc(); 1253 BasicBlock *BB = CB.getParent(); 1254 1255 InlineCost Cost = shouldInlineCandidate(Candidate); 1256 if (Cost.isNever()) { 1257 ORE->emit(OptimizationRemarkAnalysis(getAnnotatedRemarkPassName(), 1258 "InlineFail", DLoc, BB) 1259 << "incompatible inlining"); 1260 return false; 1261 } 1262 1263 if (!Cost) 1264 return false; 1265 1266 InlineFunctionInfo IFI(nullptr, GetAC); 1267 IFI.UpdateProfile = false; 1268 if (!InlineFunction(CB, IFI).isSuccess()) 1269 return false; 1270 1271 // Merge the attributes based on the inlining. 1272 AttributeFuncs::mergeAttributesForInlining(*BB->getParent(), 1273 *CalledFunction); 1274 1275 // The call to InlineFunction erases I, so we can't pass it here. 1276 emitInlinedIntoBasedOnCost(*ORE, DLoc, BB, *CalledFunction, *BB->getParent(), 1277 Cost, true, getAnnotatedRemarkPassName()); 1278 1279 // Now populate the list of newly exposed call sites. 1280 if (InlinedCallSites) { 1281 InlinedCallSites->clear(); 1282 for (auto &I : IFI.InlinedCallSites) 1283 InlinedCallSites->push_back(I); 1284 } 1285 1286 if (FunctionSamples::ProfileIsCS) 1287 ContextTracker->markContextSamplesInlined(Candidate.CalleeSamples); 1288 ++NumCSInlined; 1289 1290 // Prorate inlined probes for a duplicated inlining callsite which probably 1291 // has a distribution less than 100%. Samples for an inlinee should be 1292 // distributed among the copies of the original callsite based on each 1293 // callsite's distribution factor for counts accuracy. Note that an inlined 1294 // probe may come with its own distribution factor if it has been duplicated 1295 // in the inlinee body. The two factor are multiplied to reflect the 1296 // aggregation of duplication. 1297 if (Candidate.CallsiteDistribution < 1) { 1298 for (auto &I : IFI.InlinedCallSites) { 1299 if (Optional<PseudoProbe> Probe = extractProbe(*I)) 1300 setProbeDistributionFactor(*I, Probe->Factor * 1301 Candidate.CallsiteDistribution); 1302 } 1303 NumDuplicatedInlinesite++; 1304 } 1305 1306 return true; 1307 } 1308 1309 bool SampleProfileLoader::getInlineCandidate(InlineCandidate *NewCandidate, 1310 CallBase *CB) { 1311 assert(CB && "Expect non-null call instruction"); 1312 1313 if (isa<IntrinsicInst>(CB)) 1314 return false; 1315 1316 // Find the callee's profile. For indirect call, find hottest target profile. 1317 const FunctionSamples *CalleeSamples = findCalleeFunctionSamples(*CB); 1318 // If ExternalInlineAdvisor wants to inline this site, do so even 1319 // if Samples are not present. 1320 if (!CalleeSamples && !getExternalInlineAdvisorShouldInline(*CB)) 1321 return false; 1322 1323 float Factor = 1.0; 1324 if (Optional<PseudoProbe> Probe = extractProbe(*CB)) 1325 Factor = Probe->Factor; 1326 1327 uint64_t CallsiteCount = 1328 CalleeSamples ? CalleeSamples->getEntrySamples() * Factor : 0; 1329 *NewCandidate = {CB, CalleeSamples, CallsiteCount, Factor}; 1330 return true; 1331 } 1332 1333 Optional<InlineCost> 1334 SampleProfileLoader::getExternalInlineAdvisorCost(CallBase &CB) { 1335 std::unique_ptr<InlineAdvice> Advice = nullptr; 1336 if (ExternalInlineAdvisor) { 1337 Advice = ExternalInlineAdvisor->getAdvice(CB); 1338 if (Advice) { 1339 if (!Advice->isInliningRecommended()) { 1340 Advice->recordUnattemptedInlining(); 1341 return InlineCost::getNever("not previously inlined"); 1342 } 1343 Advice->recordInlining(); 1344 return InlineCost::getAlways("previously inlined"); 1345 } 1346 } 1347 1348 return {}; 1349 } 1350 1351 bool SampleProfileLoader::getExternalInlineAdvisorShouldInline(CallBase &CB) { 1352 Optional<InlineCost> Cost = getExternalInlineAdvisorCost(CB); 1353 return Cost ? !!Cost.getValue() : false; 1354 } 1355 1356 InlineCost 1357 SampleProfileLoader::shouldInlineCandidate(InlineCandidate &Candidate) { 1358 if (Optional<InlineCost> ReplayCost = 1359 getExternalInlineAdvisorCost(*Candidate.CallInstr)) 1360 return ReplayCost.getValue(); 1361 // Adjust threshold based on call site hotness, only do this for callsite 1362 // prioritized inliner because otherwise cost-benefit check is done earlier. 1363 int SampleThreshold = SampleColdCallSiteThreshold; 1364 if (CallsitePrioritizedInline) { 1365 if (Candidate.CallsiteCount > PSI->getHotCountThreshold()) 1366 SampleThreshold = SampleHotCallSiteThreshold; 1367 else if (!ProfileSizeInline) 1368 return InlineCost::getNever("cold callsite"); 1369 } 1370 1371 Function *Callee = Candidate.CallInstr->getCalledFunction(); 1372 assert(Callee && "Expect a definition for inline candidate of direct call"); 1373 1374 InlineParams Params = getInlineParams(); 1375 // We will ignore the threshold from inline cost, so always get full cost. 1376 Params.ComputeFullInlineCost = true; 1377 Params.AllowRecursiveCall = AllowRecursiveInline; 1378 // Checks if there is anything in the reachable portion of the callee at 1379 // this callsite that makes this inlining potentially illegal. Need to 1380 // set ComputeFullInlineCost, otherwise getInlineCost may return early 1381 // when cost exceeds threshold without checking all IRs in the callee. 1382 // The acutal cost does not matter because we only checks isNever() to 1383 // see if it is legal to inline the callsite. 1384 InlineCost Cost = getInlineCost(*Candidate.CallInstr, Callee, Params, 1385 GetTTI(*Callee), GetAC, GetTLI); 1386 1387 // Honor always inline and never inline from call analyzer 1388 if (Cost.isNever() || Cost.isAlways()) 1389 return Cost; 1390 1391 // With CSSPGO, the preinliner in llvm-profgen can estimate global inline 1392 // decisions based on hotness as well as accurate function byte sizes for 1393 // given context using function/inlinee sizes from previous build. It 1394 // stores the decision in profile, and also adjust/merge context profile 1395 // aiming at better context-sensitive post-inline profile quality, assuming 1396 // all inline decision estimates are going to be honored by compiler. Here 1397 // we replay that inline decision under `sample-profile-use-preinliner`. 1398 // Note that we don't need to handle negative decision from preinliner as 1399 // context profile for not inlined calls are merged by preinliner already. 1400 if (UsePreInlinerDecision && Candidate.CalleeSamples) { 1401 // Once two node are merged due to promotion, we're losing some context 1402 // so the original context-sensitive preinliner decision should be ignored 1403 // for SyntheticContext. 1404 SampleContext &Context = Candidate.CalleeSamples->getContext(); 1405 if (!Context.hasState(SyntheticContext) && 1406 Context.hasAttribute(ContextShouldBeInlined)) 1407 return InlineCost::getAlways("preinliner"); 1408 } 1409 1410 // For old FDO inliner, we inline the call site as long as cost is not 1411 // "Never". The cost-benefit check is done earlier. 1412 if (!CallsitePrioritizedInline) { 1413 return InlineCost::get(Cost.getCost(), INT_MAX); 1414 } 1415 1416 // Otherwise only use the cost from call analyzer, but overwite threshold with 1417 // Sample PGO threshold. 1418 return InlineCost::get(Cost.getCost(), SampleThreshold); 1419 } 1420 1421 bool SampleProfileLoader::inlineHotFunctionsWithPriority( 1422 Function &F, DenseSet<GlobalValue::GUID> &InlinedGUIDs) { 1423 // ProfAccForSymsInList is used in callsiteIsHot. The assertion makes sure 1424 // Profile symbol list is ignored when profile-sample-accurate is on. 1425 assert((!ProfAccForSymsInList || 1426 (!ProfileSampleAccurate && 1427 !F.hasFnAttribute("profile-sample-accurate"))) && 1428 "ProfAccForSymsInList should be false when profile-sample-accurate " 1429 "is enabled"); 1430 1431 // Populating worklist with initial call sites from root inliner, along 1432 // with call site weights. 1433 CandidateQueue CQueue; 1434 InlineCandidate NewCandidate; 1435 for (auto &BB : F) { 1436 for (auto &I : BB.getInstList()) { 1437 auto *CB = dyn_cast<CallBase>(&I); 1438 if (!CB) 1439 continue; 1440 if (getInlineCandidate(&NewCandidate, CB)) 1441 CQueue.push(NewCandidate); 1442 } 1443 } 1444 1445 // Cap the size growth from profile guided inlining. This is needed even 1446 // though cost of each inline candidate already accounts for callee size, 1447 // because with top-down inlining, we can grow inliner size significantly 1448 // with large number of smaller inlinees each pass the cost check. 1449 assert(ProfileInlineLimitMax >= ProfileInlineLimitMin && 1450 "Max inline size limit should not be smaller than min inline size " 1451 "limit."); 1452 unsigned SizeLimit = F.getInstructionCount() * ProfileInlineGrowthLimit; 1453 SizeLimit = std::min(SizeLimit, (unsigned)ProfileInlineLimitMax); 1454 SizeLimit = std::max(SizeLimit, (unsigned)ProfileInlineLimitMin); 1455 if (ExternalInlineAdvisor) 1456 SizeLimit = std::numeric_limits<unsigned>::max(); 1457 1458 DenseMap<CallBase *, const FunctionSamples *> LocalNotInlinedCallSites; 1459 1460 // Perform iterative BFS call site prioritized inlining 1461 bool Changed = false; 1462 while (!CQueue.empty() && F.getInstructionCount() < SizeLimit) { 1463 InlineCandidate Candidate = CQueue.top(); 1464 CQueue.pop(); 1465 CallBase *I = Candidate.CallInstr; 1466 Function *CalledFunction = I->getCalledFunction(); 1467 1468 if (CalledFunction == &F) 1469 continue; 1470 if (I->isIndirectCall()) { 1471 uint64_t Sum = 0; 1472 auto CalleeSamples = findIndirectCallFunctionSamples(*I, Sum); 1473 uint64_t SumOrigin = Sum; 1474 Sum *= Candidate.CallsiteDistribution; 1475 unsigned ICPCount = 0; 1476 for (const auto *FS : CalleeSamples) { 1477 // TODO: Consider disable pre-lTO ICP for MonoLTO as well 1478 if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) { 1479 findExternalInlineCandidate(I, FS, InlinedGUIDs, SymbolMap, 1480 PSI->getOrCompHotCountThreshold()); 1481 continue; 1482 } 1483 uint64_t EntryCountDistributed = 1484 FS->getEntrySamples() * Candidate.CallsiteDistribution; 1485 // In addition to regular inline cost check, we also need to make sure 1486 // ICP isn't introducing excessive speculative checks even if individual 1487 // target looks beneficial to promote and inline. That means we should 1488 // only do ICP when there's a small number dominant targets. 1489 if (ICPCount >= ProfileICPRelativeHotnessSkip && 1490 EntryCountDistributed * 100 < SumOrigin * ProfileICPRelativeHotness) 1491 break; 1492 // TODO: Fix CallAnalyzer to handle all indirect calls. 1493 // For indirect call, we don't run CallAnalyzer to get InlineCost 1494 // before actual inlining. This is because we could see two different 1495 // types from the same definition, which makes CallAnalyzer choke as 1496 // it's expecting matching parameter type on both caller and callee 1497 // side. See example from PR18962 for the triggering cases (the bug was 1498 // fixed, but we generate different types). 1499 if (!PSI->isHotCount(EntryCountDistributed)) 1500 break; 1501 SmallVector<CallBase *, 8> InlinedCallSites; 1502 // Attach function profile for promoted indirect callee, and update 1503 // call site count for the promoted inline candidate too. 1504 Candidate = {I, FS, EntryCountDistributed, 1505 Candidate.CallsiteDistribution}; 1506 if (tryPromoteAndInlineCandidate(F, Candidate, SumOrigin, Sum, 1507 &InlinedCallSites)) { 1508 for (auto *CB : InlinedCallSites) { 1509 if (getInlineCandidate(&NewCandidate, CB)) 1510 CQueue.emplace(NewCandidate); 1511 } 1512 ICPCount++; 1513 Changed = true; 1514 } else if (!ContextTracker) { 1515 LocalNotInlinedCallSites.try_emplace(I, FS); 1516 } 1517 } 1518 } else if (CalledFunction && CalledFunction->getSubprogram() && 1519 !CalledFunction->isDeclaration()) { 1520 SmallVector<CallBase *, 8> InlinedCallSites; 1521 if (tryInlineCandidate(Candidate, &InlinedCallSites)) { 1522 for (auto *CB : InlinedCallSites) { 1523 if (getInlineCandidate(&NewCandidate, CB)) 1524 CQueue.emplace(NewCandidate); 1525 } 1526 Changed = true; 1527 } else if (!ContextTracker) { 1528 LocalNotInlinedCallSites.try_emplace(I, Candidate.CalleeSamples); 1529 } 1530 } else if (LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink) { 1531 findExternalInlineCandidate(I, findCalleeFunctionSamples(*I), 1532 InlinedGUIDs, SymbolMap, 1533 PSI->getOrCompHotCountThreshold()); 1534 } 1535 } 1536 1537 if (!CQueue.empty()) { 1538 if (SizeLimit == (unsigned)ProfileInlineLimitMax) 1539 ++NumCSInlinedHitMaxLimit; 1540 else if (SizeLimit == (unsigned)ProfileInlineLimitMin) 1541 ++NumCSInlinedHitMinLimit; 1542 else 1543 ++NumCSInlinedHitGrowthLimit; 1544 } 1545 1546 // For CS profile, profile for not inlined context will be merged when 1547 // base profile is being retrieved. 1548 if (!FunctionSamples::ProfileIsCS) 1549 promoteMergeNotInlinedContextSamples(LocalNotInlinedCallSites, F); 1550 return Changed; 1551 } 1552 1553 void SampleProfileLoader::promoteMergeNotInlinedContextSamples( 1554 DenseMap<CallBase *, const FunctionSamples *> NonInlinedCallSites, 1555 const Function &F) { 1556 // Accumulate not inlined callsite information into notInlinedSamples 1557 for (const auto &Pair : NonInlinedCallSites) { 1558 CallBase *I = Pair.getFirst(); 1559 Function *Callee = I->getCalledFunction(); 1560 if (!Callee || Callee->isDeclaration()) 1561 continue; 1562 1563 ORE->emit( 1564 OptimizationRemarkAnalysis(getAnnotatedRemarkPassName(), "NotInline", 1565 I->getDebugLoc(), I->getParent()) 1566 << "previous inlining not repeated: '" << ore::NV("Callee", Callee) 1567 << "' into '" << ore::NV("Caller", &F) << "'"); 1568 1569 ++NumCSNotInlined; 1570 const FunctionSamples *FS = Pair.getSecond(); 1571 if (FS->getTotalSamples() == 0 && FS->getEntrySamples() == 0) { 1572 continue; 1573 } 1574 1575 // Do not merge a context that is already duplicated into the base profile. 1576 if (FS->getContext().hasAttribute(sampleprof::ContextDuplicatedIntoBase)) 1577 continue; 1578 1579 if (ProfileMergeInlinee) { 1580 // A function call can be replicated by optimizations like callsite 1581 // splitting or jump threading and the replicates end up sharing the 1582 // sample nested callee profile instead of slicing the original 1583 // inlinee's profile. We want to do merge exactly once by filtering out 1584 // callee profiles with a non-zero head sample count. 1585 if (FS->getHeadSamples() == 0) { 1586 // Use entry samples as head samples during the merge, as inlinees 1587 // don't have head samples. 1588 const_cast<FunctionSamples *>(FS)->addHeadSamples( 1589 FS->getEntrySamples()); 1590 1591 // Note that we have to do the merge right after processing function. 1592 // This allows OutlineFS's profile to be used for annotation during 1593 // top-down processing of functions' annotation. 1594 FunctionSamples *OutlineFS = Reader->getOrCreateSamplesFor(*Callee); 1595 OutlineFS->merge(*FS, 1); 1596 // Set outlined profile to be synthetic to not bias the inliner. 1597 OutlineFS->SetContextSynthetic(); 1598 } 1599 } else { 1600 auto pair = 1601 notInlinedCallInfo.try_emplace(Callee, NotInlinedProfileInfo{0}); 1602 pair.first->second.entryCount += FS->getEntrySamples(); 1603 } 1604 } 1605 } 1606 1607 /// Returns the sorted CallTargetMap \p M by count in descending order. 1608 static SmallVector<InstrProfValueData, 2> 1609 GetSortedValueDataFromCallTargets(const SampleRecord::CallTargetMap &M) { 1610 SmallVector<InstrProfValueData, 2> R; 1611 for (const auto &I : SampleRecord::SortCallTargets(M)) { 1612 R.emplace_back( 1613 InstrProfValueData{FunctionSamples::getGUID(I.first), I.second}); 1614 } 1615 return R; 1616 } 1617 1618 // Generate MD_prof metadata for every branch instruction using the 1619 // edge weights computed during propagation. 1620 void SampleProfileLoader::generateMDProfMetadata(Function &F) { 1621 // Generate MD_prof metadata for every branch instruction using the 1622 // edge weights computed during propagation. 1623 LLVM_DEBUG(dbgs() << "\nPropagation complete. Setting branch weights\n"); 1624 LLVMContext &Ctx = F.getContext(); 1625 MDBuilder MDB(Ctx); 1626 for (auto &BI : F) { 1627 BasicBlock *BB = &BI; 1628 1629 if (BlockWeights[BB]) { 1630 for (auto &I : BB->getInstList()) { 1631 if (!isa<CallInst>(I) && !isa<InvokeInst>(I)) 1632 continue; 1633 if (!cast<CallBase>(I).getCalledFunction()) { 1634 const DebugLoc &DLoc = I.getDebugLoc(); 1635 if (!DLoc) 1636 continue; 1637 const DILocation *DIL = DLoc; 1638 const FunctionSamples *FS = findFunctionSamples(I); 1639 if (!FS) 1640 continue; 1641 auto CallSite = FunctionSamples::getCallSiteIdentifier(DIL); 1642 auto T = FS->findCallTargetMapAt(CallSite); 1643 if (!T || T.get().empty()) 1644 continue; 1645 if (FunctionSamples::ProfileIsProbeBased) { 1646 // Prorate the callsite counts based on the pre-ICP distribution 1647 // factor to reflect what is already done to the callsite before 1648 // ICP, such as calliste cloning. 1649 if (Optional<PseudoProbe> Probe = extractProbe(I)) { 1650 if (Probe->Factor < 1) 1651 T = SampleRecord::adjustCallTargets(T.get(), Probe->Factor); 1652 } 1653 } 1654 SmallVector<InstrProfValueData, 2> SortedCallTargets = 1655 GetSortedValueDataFromCallTargets(T.get()); 1656 uint64_t Sum = 0; 1657 for (const auto &C : T.get()) 1658 Sum += C.second; 1659 // With CSSPGO all indirect call targets are counted torwards the 1660 // original indirect call site in the profile, including both 1661 // inlined and non-inlined targets. 1662 if (!FunctionSamples::ProfileIsCS) { 1663 if (const FunctionSamplesMap *M = 1664 FS->findFunctionSamplesMapAt(CallSite)) { 1665 for (const auto &NameFS : *M) 1666 Sum += NameFS.second.getEntrySamples(); 1667 } 1668 } 1669 if (Sum) 1670 updateIDTMetaData(I, SortedCallTargets, Sum); 1671 else if (OverwriteExistingWeights) 1672 I.setMetadata(LLVMContext::MD_prof, nullptr); 1673 } else if (!isa<IntrinsicInst>(&I)) { 1674 I.setMetadata(LLVMContext::MD_prof, 1675 MDB.createBranchWeights( 1676 {static_cast<uint32_t>(BlockWeights[BB])})); 1677 } 1678 } 1679 } else if (OverwriteExistingWeights || ProfileSampleBlockAccurate) { 1680 // Set profile metadata (possibly annotated by LTO prelink) to zero or 1681 // clear it for cold code. 1682 for (auto &I : BB->getInstList()) { 1683 if (isa<CallInst>(I) || isa<InvokeInst>(I)) { 1684 if (cast<CallBase>(I).isIndirectCall()) 1685 I.setMetadata(LLVMContext::MD_prof, nullptr); 1686 else 1687 I.setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(0)); 1688 } 1689 } 1690 } 1691 1692 Instruction *TI = BB->getTerminator(); 1693 if (TI->getNumSuccessors() == 1) 1694 continue; 1695 if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI) && 1696 !isa<IndirectBrInst>(TI)) 1697 continue; 1698 1699 DebugLoc BranchLoc = TI->getDebugLoc(); 1700 LLVM_DEBUG(dbgs() << "\nGetting weights for branch at line " 1701 << ((BranchLoc) ? Twine(BranchLoc.getLine()) 1702 : Twine("<UNKNOWN LOCATION>")) 1703 << ".\n"); 1704 SmallVector<uint32_t, 4> Weights; 1705 uint32_t MaxWeight = 0; 1706 Instruction *MaxDestInst; 1707 // Since profi treats multiple edges (multiway branches) as a single edge, 1708 // we need to distribute the computed weight among the branches. We do 1709 // this by evenly splitting the edge weight among destinations. 1710 DenseMap<const BasicBlock *, uint64_t> EdgeMultiplicity; 1711 std::vector<uint64_t> EdgeIndex; 1712 if (SampleProfileUseProfi) { 1713 EdgeIndex.resize(TI->getNumSuccessors()); 1714 for (unsigned I = 0; I < TI->getNumSuccessors(); ++I) { 1715 const BasicBlock *Succ = TI->getSuccessor(I); 1716 EdgeIndex[I] = EdgeMultiplicity[Succ]; 1717 EdgeMultiplicity[Succ]++; 1718 } 1719 } 1720 for (unsigned I = 0; I < TI->getNumSuccessors(); ++I) { 1721 BasicBlock *Succ = TI->getSuccessor(I); 1722 Edge E = std::make_pair(BB, Succ); 1723 uint64_t Weight = EdgeWeights[E]; 1724 LLVM_DEBUG(dbgs() << "\t"; printEdgeWeight(dbgs(), E)); 1725 // Use uint32_t saturated arithmetic to adjust the incoming weights, 1726 // if needed. Sample counts in profiles are 64-bit unsigned values, 1727 // but internally branch weights are expressed as 32-bit values. 1728 if (Weight > std::numeric_limits<uint32_t>::max()) { 1729 LLVM_DEBUG(dbgs() << " (saturated due to uint32_t overflow)"); 1730 Weight = std::numeric_limits<uint32_t>::max(); 1731 } 1732 if (!SampleProfileUseProfi) { 1733 // Weight is added by one to avoid propagation errors introduced by 1734 // 0 weights. 1735 Weights.push_back(static_cast<uint32_t>(Weight + 1)); 1736 } else { 1737 // Profi creates proper weights that do not require "+1" adjustments but 1738 // we evenly split the weight among branches with the same destination. 1739 uint64_t W = Weight / EdgeMultiplicity[Succ]; 1740 // Rounding up, if needed, so that first branches are hotter. 1741 if (EdgeIndex[I] < Weight % EdgeMultiplicity[Succ]) 1742 W++; 1743 Weights.push_back(static_cast<uint32_t>(W)); 1744 } 1745 if (Weight != 0) { 1746 if (Weight > MaxWeight) { 1747 MaxWeight = Weight; 1748 MaxDestInst = Succ->getFirstNonPHIOrDbgOrLifetime(); 1749 } 1750 } 1751 } 1752 1753 // FIXME: Re-enable for sample profiling after investigating why the sum 1754 // of branch weights can be 0 1755 // 1756 // misexpect::checkExpectAnnotations(*TI, Weights, /*IsFrontend=*/false); 1757 1758 uint64_t TempWeight; 1759 // Only set weights if there is at least one non-zero weight. 1760 // In any other case, let the analyzer set weights. 1761 // Do not set weights if the weights are present unless under 1762 // OverwriteExistingWeights. In ThinLTO, the profile annotation is done 1763 // twice. If the first annotation already set the weights, the second pass 1764 // does not need to set it. With OverwriteExistingWeights, Blocks with zero 1765 // weight should have their existing metadata (possibly annotated by LTO 1766 // prelink) cleared. 1767 if (MaxWeight > 0 && 1768 (!TI->extractProfTotalWeight(TempWeight) || OverwriteExistingWeights)) { 1769 LLVM_DEBUG(dbgs() << "SUCCESS. Found non-zero weights.\n"); 1770 TI->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights)); 1771 ORE->emit([&]() { 1772 return OptimizationRemark(DEBUG_TYPE, "PopularDest", MaxDestInst) 1773 << "most popular destination for conditional branches at " 1774 << ore::NV("CondBranchesLoc", BranchLoc); 1775 }); 1776 } else { 1777 if (OverwriteExistingWeights) { 1778 TI->setMetadata(LLVMContext::MD_prof, nullptr); 1779 LLVM_DEBUG(dbgs() << "CLEARED. All branch weights are zero.\n"); 1780 } else { 1781 LLVM_DEBUG(dbgs() << "SKIPPED. All branch weights are zero.\n"); 1782 } 1783 } 1784 } 1785 } 1786 1787 /// Once all the branch weights are computed, we emit the MD_prof 1788 /// metadata on BB using the computed values for each of its branches. 1789 /// 1790 /// \param F The function to query. 1791 /// 1792 /// \returns true if \p F was modified. Returns false, otherwise. 1793 bool SampleProfileLoader::emitAnnotations(Function &F) { 1794 bool Changed = false; 1795 1796 if (FunctionSamples::ProfileIsProbeBased) { 1797 if (!ProbeManager->profileIsValid(F, *Samples)) { 1798 LLVM_DEBUG( 1799 dbgs() << "Profile is invalid due to CFG mismatch for Function " 1800 << F.getName()); 1801 ++NumMismatchedProfile; 1802 return false; 1803 } 1804 ++NumMatchedProfile; 1805 } else { 1806 if (getFunctionLoc(F) == 0) 1807 return false; 1808 1809 LLVM_DEBUG(dbgs() << "Line number for the first instruction in " 1810 << F.getName() << ": " << getFunctionLoc(F) << "\n"); 1811 } 1812 1813 DenseSet<GlobalValue::GUID> InlinedGUIDs; 1814 if (CallsitePrioritizedInline) 1815 Changed |= inlineHotFunctionsWithPriority(F, InlinedGUIDs); 1816 else 1817 Changed |= inlineHotFunctions(F, InlinedGUIDs); 1818 1819 Changed |= computeAndPropagateWeights(F, InlinedGUIDs); 1820 1821 if (Changed) 1822 generateMDProfMetadata(F); 1823 1824 emitCoverageRemarks(F); 1825 return Changed; 1826 } 1827 1828 char SampleProfileLoaderLegacyPass::ID = 0; 1829 1830 INITIALIZE_PASS_BEGIN(SampleProfileLoaderLegacyPass, "sample-profile", 1831 "Sample Profile loader", false, false) 1832 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 1833 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 1834 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 1835 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) 1836 INITIALIZE_PASS_END(SampleProfileLoaderLegacyPass, "sample-profile", 1837 "Sample Profile loader", false, false) 1838 1839 std::unique_ptr<ProfiledCallGraph> 1840 SampleProfileLoader::buildProfiledCallGraph(CallGraph &CG) { 1841 std::unique_ptr<ProfiledCallGraph> ProfiledCG; 1842 if (FunctionSamples::ProfileIsCS) 1843 ProfiledCG = std::make_unique<ProfiledCallGraph>(*ContextTracker); 1844 else 1845 ProfiledCG = std::make_unique<ProfiledCallGraph>(Reader->getProfiles()); 1846 1847 // Add all functions into the profiled call graph even if they are not in 1848 // the profile. This makes sure functions missing from the profile still 1849 // gets a chance to be processed. 1850 for (auto &Node : CG) { 1851 const auto *F = Node.first; 1852 if (!F || F->isDeclaration() || !F->hasFnAttribute("use-sample-profile")) 1853 continue; 1854 ProfiledCG->addProfiledFunction(FunctionSamples::getCanonicalFnName(*F)); 1855 } 1856 1857 return ProfiledCG; 1858 } 1859 1860 std::vector<Function *> 1861 SampleProfileLoader::buildFunctionOrder(Module &M, CallGraph *CG) { 1862 std::vector<Function *> FunctionOrderList; 1863 FunctionOrderList.reserve(M.size()); 1864 1865 if (!ProfileTopDownLoad && UseProfiledCallGraph) 1866 errs() << "WARNING: -use-profiled-call-graph ignored, should be used " 1867 "together with -sample-profile-top-down-load.\n"; 1868 1869 if (!ProfileTopDownLoad || CG == nullptr) { 1870 if (ProfileMergeInlinee) { 1871 // Disable ProfileMergeInlinee if profile is not loaded in top down order, 1872 // because the profile for a function may be used for the profile 1873 // annotation of its outline copy before the profile merging of its 1874 // non-inlined inline instances, and that is not the way how 1875 // ProfileMergeInlinee is supposed to work. 1876 ProfileMergeInlinee = false; 1877 } 1878 1879 for (Function &F : M) 1880 if (!F.isDeclaration() && F.hasFnAttribute("use-sample-profile")) 1881 FunctionOrderList.push_back(&F); 1882 return FunctionOrderList; 1883 } 1884 1885 assert(&CG->getModule() == &M); 1886 1887 if (UseProfiledCallGraph || (FunctionSamples::ProfileIsCS && 1888 !UseProfiledCallGraph.getNumOccurrences())) { 1889 // Use profiled call edges to augment the top-down order. There are cases 1890 // that the top-down order computed based on the static call graph doesn't 1891 // reflect real execution order. For example 1892 // 1893 // 1. Incomplete static call graph due to unknown indirect call targets. 1894 // Adjusting the order by considering indirect call edges from the 1895 // profile can enable the inlining of indirect call targets by allowing 1896 // the caller processed before them. 1897 // 2. Mutual call edges in an SCC. The static processing order computed for 1898 // an SCC may not reflect the call contexts in the context-sensitive 1899 // profile, thus may cause potential inlining to be overlooked. The 1900 // function order in one SCC is being adjusted to a top-down order based 1901 // on the profile to favor more inlining. This is only a problem with CS 1902 // profile. 1903 // 3. Transitive indirect call edges due to inlining. When a callee function 1904 // (say B) is inlined into into a caller function (say A) in LTO prelink, 1905 // every call edge originated from the callee B will be transferred to 1906 // the caller A. If any transferred edge (say A->C) is indirect, the 1907 // original profiled indirect edge B->C, even if considered, would not 1908 // enforce a top-down order from the caller A to the potential indirect 1909 // call target C in LTO postlink since the inlined callee B is gone from 1910 // the static call graph. 1911 // 4. #3 can happen even for direct call targets, due to functions defined 1912 // in header files. A header function (say A), when included into source 1913 // files, is defined multiple times but only one definition survives due 1914 // to ODR. Therefore, the LTO prelink inlining done on those dropped 1915 // definitions can be useless based on a local file scope. More 1916 // importantly, the inlinee (say B), once fully inlined to a 1917 // to-be-dropped A, will have no profile to consume when its outlined 1918 // version is compiled. This can lead to a profile-less prelink 1919 // compilation for the outlined version of B which may be called from 1920 // external modules. while this isn't easy to fix, we rely on the 1921 // postlink AutoFDO pipeline to optimize B. Since the survived copy of 1922 // the A can be inlined in its local scope in prelink, it may not exist 1923 // in the merged IR in postlink, and we'll need the profiled call edges 1924 // to enforce a top-down order for the rest of the functions. 1925 // 1926 // Considering those cases, a profiled call graph completely independent of 1927 // the static call graph is constructed based on profile data, where 1928 // function objects are not even needed to handle case #3 and case 4. 1929 // 1930 // Note that static callgraph edges are completely ignored since they 1931 // can be conflicting with profiled edges for cyclic SCCs and may result in 1932 // an SCC order incompatible with profile-defined one. Using strictly 1933 // profile order ensures a maximum inlining experience. On the other hand, 1934 // static call edges are not so important when they don't correspond to a 1935 // context in the profile. 1936 1937 std::unique_ptr<ProfiledCallGraph> ProfiledCG = buildProfiledCallGraph(*CG); 1938 scc_iterator<ProfiledCallGraph *> CGI = scc_begin(ProfiledCG.get()); 1939 while (!CGI.isAtEnd()) { 1940 auto Range = *CGI; 1941 if (SortProfiledSCC) { 1942 // Sort nodes in one SCC based on callsite hotness. 1943 scc_member_iterator<ProfiledCallGraph *> SI(*CGI); 1944 Range = *SI; 1945 } 1946 for (auto *Node : Range) { 1947 Function *F = SymbolMap.lookup(Node->Name); 1948 if (F && !F->isDeclaration() && F->hasFnAttribute("use-sample-profile")) 1949 FunctionOrderList.push_back(F); 1950 } 1951 ++CGI; 1952 } 1953 } else { 1954 scc_iterator<CallGraph *> CGI = scc_begin(CG); 1955 while (!CGI.isAtEnd()) { 1956 for (CallGraphNode *Node : *CGI) { 1957 auto *F = Node->getFunction(); 1958 if (F && !F->isDeclaration() && F->hasFnAttribute("use-sample-profile")) 1959 FunctionOrderList.push_back(F); 1960 } 1961 ++CGI; 1962 } 1963 } 1964 1965 LLVM_DEBUG({ 1966 dbgs() << "Function processing order:\n"; 1967 for (auto F : reverse(FunctionOrderList)) { 1968 dbgs() << F->getName() << "\n"; 1969 } 1970 }); 1971 1972 std::reverse(FunctionOrderList.begin(), FunctionOrderList.end()); 1973 return FunctionOrderList; 1974 } 1975 1976 bool SampleProfileLoader::doInitialization(Module &M, 1977 FunctionAnalysisManager *FAM) { 1978 auto &Ctx = M.getContext(); 1979 1980 auto ReaderOrErr = SampleProfileReader::create( 1981 Filename, Ctx, FSDiscriminatorPass::Base, RemappingFilename); 1982 if (std::error_code EC = ReaderOrErr.getError()) { 1983 std::string Msg = "Could not open profile: " + EC.message(); 1984 Ctx.diagnose(DiagnosticInfoSampleProfile(Filename, Msg)); 1985 return false; 1986 } 1987 Reader = std::move(ReaderOrErr.get()); 1988 Reader->setSkipFlatProf(LTOPhase == ThinOrFullLTOPhase::ThinLTOPostLink); 1989 // set module before reading the profile so reader may be able to only 1990 // read the function profiles which are used by the current module. 1991 Reader->setModule(&M); 1992 if (std::error_code EC = Reader->read()) { 1993 std::string Msg = "profile reading failed: " + EC.message(); 1994 Ctx.diagnose(DiagnosticInfoSampleProfile(Filename, Msg)); 1995 return false; 1996 } 1997 1998 PSL = Reader->getProfileSymbolList(); 1999 2000 // While profile-sample-accurate is on, ignore symbol list. 2001 ProfAccForSymsInList = 2002 ProfileAccurateForSymsInList && PSL && !ProfileSampleAccurate; 2003 if (ProfAccForSymsInList) { 2004 NamesInProfile.clear(); 2005 if (auto NameTable = Reader->getNameTable()) 2006 NamesInProfile.insert(NameTable->begin(), NameTable->end()); 2007 CoverageTracker.setProfAccForSymsInList(true); 2008 } 2009 2010 if (FAM && !ProfileInlineReplayFile.empty()) { 2011 ExternalInlineAdvisor = getReplayInlineAdvisor( 2012 M, *FAM, Ctx, /*OriginalAdvisor=*/nullptr, 2013 ReplayInlinerSettings{ProfileInlineReplayFile, 2014 ProfileInlineReplayScope, 2015 ProfileInlineReplayFallback, 2016 {ProfileInlineReplayFormat}}, 2017 /*EmitRemarks=*/false, InlineContext{LTOPhase, InlinePass::ReplaySampleProfileInliner}); 2018 } 2019 2020 // Apply tweaks if context-sensitive or probe-based profile is available. 2021 if (Reader->profileIsCS() || Reader->profileIsPreInlined() || 2022 Reader->profileIsProbeBased()) { 2023 if (!UseIterativeBFIInference.getNumOccurrences()) 2024 UseIterativeBFIInference = true; 2025 if (!SampleProfileUseProfi.getNumOccurrences()) 2026 SampleProfileUseProfi = true; 2027 if (!EnableExtTspBlockPlacement.getNumOccurrences()) 2028 EnableExtTspBlockPlacement = true; 2029 // Enable priority-base inliner and size inline by default for CSSPGO. 2030 if (!ProfileSizeInline.getNumOccurrences()) 2031 ProfileSizeInline = true; 2032 if (!CallsitePrioritizedInline.getNumOccurrences()) 2033 CallsitePrioritizedInline = true; 2034 // For CSSPGO, we also allow recursive inline to best use context profile. 2035 if (!AllowRecursiveInline.getNumOccurrences()) 2036 AllowRecursiveInline = true; 2037 2038 if (Reader->profileIsPreInlined()) { 2039 if (!UsePreInlinerDecision.getNumOccurrences()) 2040 UsePreInlinerDecision = true; 2041 } 2042 2043 if (!Reader->profileIsCS()) { 2044 // Non-CS profile should be fine without a function size budget for the 2045 // inliner since the contexts in the profile are either all from inlining 2046 // in the prevoius build or pre-computed by the preinliner with a size 2047 // cap, thus they are bounded. 2048 if (!ProfileInlineLimitMin.getNumOccurrences()) 2049 ProfileInlineLimitMin = std::numeric_limits<unsigned>::max(); 2050 if (!ProfileInlineLimitMax.getNumOccurrences()) 2051 ProfileInlineLimitMax = std::numeric_limits<unsigned>::max(); 2052 } 2053 } 2054 2055 if (Reader->profileIsCS()) { 2056 // Tracker for profiles under different context 2057 ContextTracker = std::make_unique<SampleContextTracker>( 2058 Reader->getProfiles(), &GUIDToFuncNameMap); 2059 } 2060 2061 // Load pseudo probe descriptors for probe-based function samples. 2062 if (Reader->profileIsProbeBased()) { 2063 ProbeManager = std::make_unique<PseudoProbeManager>(M); 2064 if (!ProbeManager->moduleIsProbed(M)) { 2065 const char *Msg = 2066 "Pseudo-probe-based profile requires SampleProfileProbePass"; 2067 Ctx.diagnose(DiagnosticInfoSampleProfile(M.getModuleIdentifier(), Msg, 2068 DS_Warning)); 2069 return false; 2070 } 2071 } 2072 2073 return true; 2074 } 2075 2076 ModulePass *llvm::createSampleProfileLoaderPass() { 2077 return new SampleProfileLoaderLegacyPass(); 2078 } 2079 2080 ModulePass *llvm::createSampleProfileLoaderPass(StringRef Name) { 2081 return new SampleProfileLoaderLegacyPass(Name); 2082 } 2083 2084 bool SampleProfileLoader::runOnModule(Module &M, ModuleAnalysisManager *AM, 2085 ProfileSummaryInfo *_PSI, CallGraph *CG) { 2086 GUIDToFuncNameMapper Mapper(M, *Reader, GUIDToFuncNameMap); 2087 2088 PSI = _PSI; 2089 if (M.getProfileSummary(/* IsCS */ false) == nullptr) { 2090 M.setProfileSummary(Reader->getSummary().getMD(M.getContext()), 2091 ProfileSummary::PSK_Sample); 2092 PSI->refresh(); 2093 } 2094 // Compute the total number of samples collected in this profile. 2095 for (const auto &I : Reader->getProfiles()) 2096 TotalCollectedSamples += I.second.getTotalSamples(); 2097 2098 auto Remapper = Reader->getRemapper(); 2099 // Populate the symbol map. 2100 for (const auto &N_F : M.getValueSymbolTable()) { 2101 StringRef OrigName = N_F.getKey(); 2102 Function *F = dyn_cast<Function>(N_F.getValue()); 2103 if (F == nullptr || OrigName.empty()) 2104 continue; 2105 SymbolMap[OrigName] = F; 2106 StringRef NewName = FunctionSamples::getCanonicalFnName(*F); 2107 if (OrigName != NewName && !NewName.empty()) { 2108 auto r = SymbolMap.insert(std::make_pair(NewName, F)); 2109 // Failiing to insert means there is already an entry in SymbolMap, 2110 // thus there are multiple functions that are mapped to the same 2111 // stripped name. In this case of name conflicting, set the value 2112 // to nullptr to avoid confusion. 2113 if (!r.second) 2114 r.first->second = nullptr; 2115 OrigName = NewName; 2116 } 2117 // Insert the remapped names into SymbolMap. 2118 if (Remapper) { 2119 if (auto MapName = Remapper->lookUpNameInProfile(OrigName)) { 2120 if (*MapName != OrigName && !MapName->empty()) 2121 SymbolMap.insert(std::make_pair(*MapName, F)); 2122 } 2123 } 2124 } 2125 assert(SymbolMap.count(StringRef()) == 0 && 2126 "No empty StringRef should be added in SymbolMap"); 2127 2128 bool retval = false; 2129 for (auto F : buildFunctionOrder(M, CG)) { 2130 assert(!F->isDeclaration()); 2131 clearFunctionData(); 2132 retval |= runOnFunction(*F, AM); 2133 } 2134 2135 // Account for cold calls not inlined.... 2136 if (!FunctionSamples::ProfileIsCS) 2137 for (const std::pair<Function *, NotInlinedProfileInfo> &pair : 2138 notInlinedCallInfo) 2139 updateProfileCallee(pair.first, pair.second.entryCount); 2140 2141 return retval; 2142 } 2143 2144 bool SampleProfileLoaderLegacyPass::runOnModule(Module &M) { 2145 ACT = &getAnalysis<AssumptionCacheTracker>(); 2146 TTIWP = &getAnalysis<TargetTransformInfoWrapperPass>(); 2147 TLIWP = &getAnalysis<TargetLibraryInfoWrapperPass>(); 2148 ProfileSummaryInfo *PSI = 2149 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 2150 return SampleLoader.runOnModule(M, nullptr, PSI, nullptr); 2151 } 2152 2153 bool SampleProfileLoader::runOnFunction(Function &F, ModuleAnalysisManager *AM) { 2154 LLVM_DEBUG(dbgs() << "\n\nProcessing Function " << F.getName() << "\n"); 2155 DILocation2SampleMap.clear(); 2156 // By default the entry count is initialized to -1, which will be treated 2157 // conservatively by getEntryCount as the same as unknown (None). This is 2158 // to avoid newly added code to be treated as cold. If we have samples 2159 // this will be overwritten in emitAnnotations. 2160 uint64_t initialEntryCount = -1; 2161 2162 ProfAccForSymsInList = ProfileAccurateForSymsInList && PSL; 2163 if (ProfileSampleAccurate || F.hasFnAttribute("profile-sample-accurate")) { 2164 // initialize all the function entry counts to 0. It means all the 2165 // functions without profile will be regarded as cold. 2166 initialEntryCount = 0; 2167 // profile-sample-accurate is a user assertion which has a higher precedence 2168 // than symbol list. When profile-sample-accurate is on, ignore symbol list. 2169 ProfAccForSymsInList = false; 2170 } 2171 CoverageTracker.setProfAccForSymsInList(ProfAccForSymsInList); 2172 2173 // PSL -- profile symbol list include all the symbols in sampled binary. 2174 // If ProfileAccurateForSymsInList is enabled, PSL is used to treat 2175 // old functions without samples being cold, without having to worry 2176 // about new and hot functions being mistakenly treated as cold. 2177 if (ProfAccForSymsInList) { 2178 // Initialize the entry count to 0 for functions in the list. 2179 if (PSL->contains(F.getName())) 2180 initialEntryCount = 0; 2181 2182 // Function in the symbol list but without sample will be regarded as 2183 // cold. To minimize the potential negative performance impact it could 2184 // have, we want to be a little conservative here saying if a function 2185 // shows up in the profile, no matter as outline function, inline instance 2186 // or call targets, treat the function as not being cold. This will handle 2187 // the cases such as most callsites of a function are inlined in sampled 2188 // binary but not inlined in current build (because of source code drift, 2189 // imprecise debug information, or the callsites are all cold individually 2190 // but not cold accumulatively...), so the outline function showing up as 2191 // cold in sampled binary will actually not be cold after current build. 2192 StringRef CanonName = FunctionSamples::getCanonicalFnName(F); 2193 if (NamesInProfile.count(CanonName)) 2194 initialEntryCount = -1; 2195 } 2196 2197 // Initialize entry count when the function has no existing entry 2198 // count value. 2199 if (!F.getEntryCount()) 2200 F.setEntryCount(ProfileCount(initialEntryCount, Function::PCT_Real)); 2201 std::unique_ptr<OptimizationRemarkEmitter> OwnedORE; 2202 if (AM) { 2203 auto &FAM = 2204 AM->getResult<FunctionAnalysisManagerModuleProxy>(*F.getParent()) 2205 .getManager(); 2206 ORE = &FAM.getResult<OptimizationRemarkEmitterAnalysis>(F); 2207 } else { 2208 OwnedORE = std::make_unique<OptimizationRemarkEmitter>(&F); 2209 ORE = OwnedORE.get(); 2210 } 2211 2212 if (FunctionSamples::ProfileIsCS) 2213 Samples = ContextTracker->getBaseSamplesFor(F); 2214 else 2215 Samples = Reader->getSamplesFor(F); 2216 2217 if (Samples && !Samples->empty()) 2218 return emitAnnotations(F); 2219 return false; 2220 } 2221 2222 PreservedAnalyses SampleProfileLoaderPass::run(Module &M, 2223 ModuleAnalysisManager &AM) { 2224 FunctionAnalysisManager &FAM = 2225 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 2226 2227 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & { 2228 return FAM.getResult<AssumptionAnalysis>(F); 2229 }; 2230 auto GetTTI = [&](Function &F) -> TargetTransformInfo & { 2231 return FAM.getResult<TargetIRAnalysis>(F); 2232 }; 2233 auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & { 2234 return FAM.getResult<TargetLibraryAnalysis>(F); 2235 }; 2236 2237 SampleProfileLoader SampleLoader( 2238 ProfileFileName.empty() ? SampleProfileFile : ProfileFileName, 2239 ProfileRemappingFileName.empty() ? SampleProfileRemappingFile 2240 : ProfileRemappingFileName, 2241 LTOPhase, GetAssumptionCache, GetTTI, GetTLI); 2242 2243 if (!SampleLoader.doInitialization(M, &FAM)) 2244 return PreservedAnalyses::all(); 2245 2246 ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(M); 2247 CallGraph &CG = AM.getResult<CallGraphAnalysis>(M); 2248 if (!SampleLoader.runOnModule(M, &AM, PSI, &CG)) 2249 return PreservedAnalyses::all(); 2250 2251 return PreservedAnalyses::none(); 2252 } 2253