[CSSPGO] Minor tweak for inline candidate priority tie breaker

[wenlei]

Summary

When prioritize call site to consider for inlining in sample loader, use number of samples as a first tier breaker before using name/guid comparison. This would favor smaller functions when hotness is the same (from the same block). We could try to retrieve accurate function size if this turns out to be more important.

[wenlei]

update

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

329

Would it make sense to compare callee function size instead?

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

329

Called that out in the change description. :)

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

329

Actually let me expand on this. Currently we don't retrieve callee functions when collecting candidate, we retrieve callee function when evaluating inline decisions.

We could alternatively retrieve callee functions earlier, but then we could also just run inline cost on it earlier and use that as 1st tier breaker?

There're definitely ways to get to more accurate prioritization, but until we know it is actually helping visibly, I'm trying to keep it simple by making a local change to have a better tie breaker than using names.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

329

I see. Callees can be retrievable after indirect promotion is done. Might be a bit late. Using profile sample size sounds good for now.

[wmi]

LGTM.

[kosarev]

llvm/lib/Transforms/IPO/SampleProfile.cpp

326

It seems the debug version of libc++ is not fine with using this predicate for CandidateQueues. This assert fails on builds with expensive checks enabled (see https://github.com/llvm/llvm-project/issues/68594).

opt: /home/kosarev/labs/llvm-project/llvm/lib/Transforms/IPO/SampleProfile.cpp:420: bool {anonymous}::CandidateComparer::operator()(const {anonymous}::InlineCandidate&, const {anonymous}::InlineCandidate&): Assertion `LCS && RCS && "Expect non-null FunctionSamples"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/opt -passes=thinlto-pre-link<O2> -pgo-kind=pgo-sample-use-pipeline -sample-profile-file=/home/kosarev/labs/llvm-project/llvm/test/Transforms/SampleProfile/Inputs/csspgo-import-list-no-funca.prof -sample-profile-inline-replay=/home/kosarev/labs/llvm-project/llvm/test/Transforms/SampleProfile/Inputs/csspgo-import-list-replay.txt -sample-profile-inline-replay-scope=Module -profile-summary-hot-count=10000 --sample-profile-even-flow-distribution=0 -S
 #0 0x00007f07afb80b02 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /home/kosarev/labs/llvm-project/llvm/lib/Support/Unix/Signals.inc:723:22
 #1 0x00007f07afb80f1e PrintStackTraceSignalHandler(void*) /home/kosarev/labs/llvm-project/llvm/lib/Support/Unix/Signals.inc:798:1
 #2 0x00007f07afb7e363 llvm::sys::RunSignalHandlers() /home/kosarev/labs/llvm-project/llvm/lib/Support/Signals.cpp:105:20
 #3 0x00007f07afb8039a SignalHandler(int) /home/kosarev/labs/llvm-project/llvm/lib/Support/Unix/Signals.inc:413:1
 #4 0x00007f07af404520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #5 0x00007f07af4589fc __pthread_kill_implementation ./nptl/pthread_kill.c:44:76
 #6 0x00007f07af4589fc __pthread_kill_internal ./nptl/pthread_kill.c:78:10
 #7 0x00007f07af4589fc pthread_kill ./nptl/pthread_kill.c:89:10
 #8 0x00007f07af404476 gsignal ./signal/../sysdeps/posix/raise.c:27:6
 #9 0x00007f07af3ea7f3 abort ./stdlib/abort.c:81:7
#10 0x00007f07af3ea71b _nl_load_domain ./intl/loadmsgcat.c:1177:9
#11 0x00007f07af3fbe96 (/lib/x86_64-linux-gnu/libc.so.6+0x39e96)
#12 0x00007f07b60058d7 (anonymous namespace)::CandidateComparer::operator()((anonymous namespace)::InlineCandidate const&, (anonymous namespace)::InlineCandidate const&) /home/kosarev/labs/llvm-project/llvm/lib/Transforms/IPO/SampleProfile.cpp:423:28
#13 0x00007f07b6013bc4 void std::pop_heap<__gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<(anonymous namespace)::InlineCandidate*, std::__cxx1998::vector<(anonymous namespace)::InlineCandidate, std::allocator<(anonymous namespace)::InlineCandidate>>>, std::__debug::vector<(anonymous namespace)::InlineCandidate, std::allocator<(anonymous namespace)::InlineCandidate>>, std::random_access_iterator_tag>, (anonymous namespace)::CandidateComparer>(__gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<(anonymous namespace)::InlineCandidate*, std::__cxx1998::vector<(anonymous namespace)::InlineCandidate, std::allocator<(anonymous namespace)::InlineCandidate>>>, std::__debug::vector<(anonymous namespace)::InlineCandidate, std::allocator<(anonymous namespace)::InlineCandidate>>, std::random_access_iterator_tag>, __gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<(anonymous namespace)::InlineCandidate*, std::__cxx1998::vector<(anonymous namespace)::InlineCandidate, std::allocator<(anonymous namespace)::InlineCandidate>>>, std::__debug::vector<(anonymous namespace)::InlineCandidate, std::allocator<(anonymous namespace)::InlineCandidate>>, std::random_access_iterator_tag>, (anonymous namespace)::CandidateComparer) /usr/include/c++/11/bits/stl_heap.h:323:7
#14 0x00007f07b60124c4 std::priority_queue<(anonymous namespace)::InlineCandidate, std::__debug::vector<(anonymous namespace)::InlineCandidate, std::allocator<(anonymous namespace)::InlineCandidate>>, (anonymous namespace)::CandidateComparer>::pop() /usr/include/c++/11/bits/stl_queue.h:678:15
#15 0x00007f07b600a3f9 (anonymous namespace)::SampleProfileLoader::inlineHotFunctionsWithPriority(llvm::Function&, llvm::DenseSet<unsigned long, llvm::DenseMapInfo<unsigned long, void>>&) /home/kosarev/labs/llvm-project/llvm/lib/Transforms/IPO/SampleProfile.cpp:1494:29
#16 0x00007f07b600c7ce (anonymous namespace)::SampleProfileLoader::emitAnnotations(llvm::Function&) /home/kosarev/labs/llvm-project/llvm/lib/Transforms/IPO/SampleProfile.cpp:1847:13
#17 0x00007f07b60119b6 (anonymous namespace)::SampleProfileLoader::runOnFunction(llvm::Function&, llvm::AnalysisManager<llvm::Module>*) /home/kosarev/labs/llvm-project/llvm/lib/Transforms/IPO/SampleProfile.cpp:2669:27
#18 0x00007f07b60111ba (anonymous namespace)::SampleProfileLoader::runOnModule(llvm::Module&, llvm::AnalysisManager<llvm::Module>*, llvm::ProfileSummaryInfo*, llvm::LazyCallGraph&) /home/kosarev/labs/llvm-project/llvm/lib/Transforms/IPO/SampleProfile.cpp:2576:12
#19 0x00007f07b6011ee1 llvm::SampleProfileLoaderPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/kosarev/labs/llvm-project/llvm/lib/Transforms/IPO/SampleProfile.cpp:2707:7
#20 0x00007f07b6b243d5 llvm::detail::PassModel<llvm::Module, llvm::SampleProfileLoaderPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/kosarev/labs/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:90:3
#21 0x00007f07b0375a61 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/kosarev/labs/llvm-project/llvm/include/llvm/IR/PassManager.h:521:20
#22 0x0000555bb9d8a371 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool, bool) /home/kosarev/labs/llvm-project/llvm/tools/opt/NewPMDriver.cpp:527:10
#23 0x0000555bb9dbb385 main /home/kosarev/labs/llvm-project/llvm/tools/opt/opt.cpp:698:27
#24 0x00007f07af3ebd90 __libc_start_call_main ./csu/../sysdeps/nptl/libc_start_call_main.h:58:16
#25 0x00007f07af3ebe40 call_init ./csu/../csu/libc-start.c:128:20
#26 0x00007f07af3ebe40 __libc_start_main ./csu/../csu/libc-start.c:379:5
#27 0x0000555bb9d87605 _start (/home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/opt+0x1c605)
FileCheck error: '<stdin>' is empty.
FileCheck command line:  /home/kosarev/labs/llvm-project/build/debug+expensive_checks/bin/FileCheck /home/kosarev/labs/llvm-project/llvm/test/Transforms/SampleProfile/csspgo-import-list.ll --check-prefix=THRESHOLD-REPLAY-NO-FUNCA

--

********************
********************
Failed Tests (1):
  LLVM :: Transforms/SampleProfile/csspgo-import-list.ll


Testing Time: 6.35s
  Failed: 1

[kosarev]

llvm/lib/Transforms/IPO/SampleProfile.cpp

326

@wenlei @hoy @wmi Ping.

llvm/lib/Transforms/IPO/SampleProfile.cpp

 };
 
 // Inline candidate comparer using call site weight
 struct CandidateComparer {
   bool operator()(const InlineCandidate &LHS, const InlineCandidate &RHS) {
     if (LHS.CallsiteCount != RHS.CallsiteCount)
       return LHS.CallsiteCount < RHS.CallsiteCount;
 
+    const FunctionSamples *LCS = LHS.CalleeSamples;
+    const FunctionSamples *RCS = RHS.CalleeSamples;
+    assert(LCS && RCS && "Expect non-null FunctionSamples");
+
+    // Tie breaker using number of samples try to favor smaller functions first
+    if (LCS->getBodySamples().size() != RCS->getBodySamples().size())
+      return LCS->getBodySamples().size() > RCS->getBodySamples().size();
+
     // Tie breaker using GUID so we have stable/deterministic inlining order
-    assert(LHS.CalleeSamples && RHS.CalleeSamples &&
-           "Expect non-null FunctionSamples");
-    return LHS.CalleeSamples->getGUID(LHS.CalleeSamples->getName()) <
-           RHS.CalleeSamples->getGUID(RHS.CalleeSamples->getName());
+    return LCS->getGUID(LCS->getName()) < RCS->getGUID(RCS->getName());
   }
 };
 
 using CandidateQueue =
     PriorityQueue<InlineCandidate, std::vector<InlineCandidate>,
                   CandidateComparer>;
 
 /// Sample profile pass.