[CSSPGO] Retire FlattenProfileForMatching

[wlei]

Summary

• Always use flattened profile to find the profile anchors. Since profile under different contexts may have different inlined callsites, to get more profile anchors, we use a merged profile from all the contexts(the flattened profile) to find callsite anchors.

• Compute the staleness metrics based on the original nested profile, as currently once a callsite is mismatched, all its children profile are dropped.(TODO: in future, we can improve to reuse the children valid profile)

[wenlei]

lgtm except nits, thanks.

llvm/lib/Transforms/IPO/SampleProfile.cpp

2379

nit: move this right before the use on line 2398?

2380–2382

nit: it may be useful to emphasize the benefit of use flattened profile for matching, i.e. it's not an arbitrary choice, but we actually see benefit from doing that.

[wlei]

Updating D158891: [CSSPGO] Retire FlattenProfileForMatching

llvm/lib/Transforms/IPO/SampleProfile.cpp

2379

done!

2380–2382

Refined the comments.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

2402

nit: profile -> profiles

once a callsite is mismatched, all its children profile are drooped

Why children profiles can be dropped? Counting happens before inlining right?

[wlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

2402

yeah, In the current findCalleeFunctionSamples implementation, if the mismatch happens, it would return null, but there is no extra process to reuse those samples, so it's "dropped".

I think as Wenlei has proposed a solution in other patch:

Maybe what we should actually do is to reuse the nested profile from those mismatched parent functions, something like run promoteMergeNotInlinedContextSamples on top level functions samples not used? We do reuse nested profile for not inlined callees from parent function.

That sounds reasonable, but as we talked offline, we could leave it in future.

[wlei]

addressing feedback, fix typo.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

2402

I'm a bit confused. FlattenedProfiles is immutable once initialized right? What do we lose when using FSFlattened for countProfileMismatches?

If we are not to count for external functions, the nested callees there will be skipped too? But using a flattened profile can keep them, if they are not external.

[wlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

2402

Let me show you with an example, say we have a profile like

A:102:1
 1:1
 2:B: 101:1
   1:1
   2:C:100:1
     1:1
      ...
     100:1

Say callsite B in A is changed to other location and the callsite is mismatched. Here like in this patch, it use the non-flattened profile.
the mismached Samples is 101, i,e, it not only count B's profile but also all the children profiles(C)

But if we use flattened profile:

A:2:1
 1:1
 1: B:1
B:2:1
 1:1
 1: C:1
C:100:1
 1:1
  ...
  100:1

The callsite of B in A is mismatched, but now the callsite count is 1, the mismatched Samples is 1.

I know it feels counter-intuitive, there is no mismatch in B and C, but that is the current implementation, we don't reuse the children profile. Once the parent callsite is mismatched, all the children profiles are dropped.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

2402

Thanks for the explanation. I have a better understanding now.

But I still have a question about how to count mismatched samples. In your examples, the 101 samples for B & C may still be used if B & C have no source changes. Yes, I get that the inlining won't happen, but even if it happens it only saves the cost of one call instruction and perhaps corresponding parameter passing cost? In other words, whether the 101 samples can be applied to inlined B&C depends on how well the matching works for B & C?

BTW, how much difference in terms of the staleness number did you see with switching to using nested profile?

[wlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

2402

Sorry I may not fully understand your question. Here the metrics is computed before the fuzzy matching, i,e. if it's a mismatch in the source code, even later the fuzzy matching recover to the right location, we still count that location is a mismatch. We haven't done the post fuzzy matching metrics.

In your examples, the 101 samples for B & C may still be used if B & C have no source changes.

This can't happen in the current implementation, if the mismatch happens, the 101 samples is never used no matter whether B&C is inlined/matched or not, because In A, when findCalleeFunctionSamples return null, it won't visit A's children profiles, the children B &C profile won't be merged into the base B & C profile.

BTW, how much difference in terms of the staleness number did you see with switching to using nested profile?

It should matter, I saw a case about 2 times differences, it depends on how hot the dropped children profile is.

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

2402

This can't happen in the current implementation, if the mismatch happens, the 101 samples is never used no matter whether B&C is inlined/matched or not, because In A, when findCalleeFunctionSamples return null, it won't visit A's children profiles, the children B &C profile won't be merged into the base B & C profile.

I see. It makes sense now. A callee profile can be returned only if it is discovered at some callsite in the caller. Thanks for the explanation!

[hoy]

llvm/lib/Transforms/IPO/SampleProfile.cpp

2402

Left a question in the other thread https://reviews.llvm.org/D156725, but I think it may also be relavant here.

The question is, when and where will the nested callee samples be counted if they are not inlined but its checksum is mismatched. In this case, the callee samples can be returned during inlining.

It sounds like we may need to selectively flatten a profile for more accurate counting, e.g, only flattening matched callsites. Maybe what Wenlei proposed in the other patch is something similar.

I feel that to be more accurate, the mismatch counter needs to more closely mimic what the sample inliner does, or the other way around, i.e, to fix the inliner to return samples for callsites that don't exist on the current IR.

Not sure how important the problem is though. But if we really want to be as accurate as enough, maybe combining the matcher and the inliner can get us there.

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

2402

It sounds like we may need to selectively flatten a profile for more accurate counting, e.g, only flattening matched callsites. Maybe what Wenlei proposed in the other patch is something similar.

Making mismatch counting and inliner's use of profile consistent will make the mismatch/stale metric more meaningful. However, I think there are still things to be improved in terms of how inliner uses profile - i.e. even if top level function mismatches, nested profile may still be reused.

My suggestion is to prioritize better use of profile first, before do everything we can to align mismatch counting.

[wlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

2402

Yeah, I agree there are two remaining issues:

1. The inliner. Currently we don't reused the mismatched callsite's children profile.

2. The mismatch metric. Yes, even with current fix, we only count the top-level profile's mismatched callsite, we don't count the nested inlined profile's mismatched callsite.

IMO, the solution for #1 is we can do the similar thing as promoteMergeNotInlinedContextSamples.

the solution for #2 is we can do the similar things as Compute checksum mismatch recursively on nested profile , also count the nested profile. another solution is to extend SampleCoverageTracker (https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/Transforms/Utils/SampleProfileLoaderBaseUtil.h#L35)

SampleCoverageTracker is the thing that count the coverage(mismatch) along the sample loader(inlining), however, it only support BodySamples, we can extend the to callsiteSamples.

llvm/lib/Transforms/IPO/SampleProfile.cpp

static cl::opt<bool> ReportProfileStaleness(
     "report-profile-staleness", cl::Hidden, cl::init(false),
     cl::desc("Compute and report stale profile statistical metrics."));
 
 static cl::opt<bool> PersistProfileStaleness(
     "persist-profile-staleness", cl::Hidden, cl::init(false),
     cl::desc("Compute stale profile statistical metrics and write it into the "
              "native object file(.llvm_stats section)."));
 
-static cl::opt<bool> FlattenProfileForMatching(
-    "flatten-profile-for-matching", cl::Hidden, cl::init(true),
-    cl::desc(
-        "Use flattened profile for stale profile detection and matching."));
-
 static cl::opt<bool> ProfileSampleAccurate(
     "profile-sample-accurate", cl::Hidden, cl::init(false),
     cl::desc("If the sample profile is accurate, we will mark all un-sampled "
              "callsite and function as having 0 samples. Otherwise, treat "
              "un-sampled callsites and functions conservatively as unknown. "));
 
 static cl::opt<bool> ProfileSampleBlockAccurate(
     "profile-sample-block-accurate", cl::Hidden, cl::init(false),
class SampleProfileMatcher {
   // A dummy name for unknown indirect callee, used to differentiate from a
   // non-call instruction that also has an empty callee name.
   static constexpr const char *UnknownIndirectCallee =
       "unknown.indirect.callee";
 
 public:
   SampleProfileMatcher(Module &M, SampleProfileReader &Reader,
                        const PseudoProbeManager *ProbeManager)
-      : M(M), Reader(Reader), ProbeManager(ProbeManager) {
-    if (FlattenProfileForMatching) {
-      ProfileConverter::flattenProfile(Reader.getProfiles(), FlattenedProfiles,
-                                       FunctionSamples::ProfileIsCS);
-    }
-  }
+      : M(M), Reader(Reader), ProbeManager(ProbeManager){};
   void runOnModule();
 
 private:
   FunctionSamples *getFlattenedSamplesFor(const Function &F) {
     StringRef CanonFName = FunctionSamples::getCanonicalFnName(F);
     auto It = FlattenedProfiles.find(CanonFName);
     if (It != FlattenedProfiles.end())
       return &It->second;
     return nullptr;
   }
-  void runOnFunction(const Function &F, const FunctionSamples &FS);
+  void runOnFunction(const Function &F);
   void findIRAnchors(const Function &F,
                      std::map<LineLocation, StringRef> &IRAnchors);
   void findProfileAnchors(const FunctionSamples &FS,
                           std::map<LineLocation, StringSet<>> &ProfileAnchors);
   void countProfileMismatches(
       const Function &F, const FunctionSamples &FS,
       const std::map<LineLocation, StringRef> &IRAnchors,
       const std::map<LineLocation, StringSet<>> &ProfileAnchors);
if (!IsMatchedAnchor) {
       InsertMatching(Loc, Candidate);
       LLVM_DEBUG(dbgs() << "Location is matched from " << Loc << " to "
                         << Candidate << "\n");
       LastMatchedNonAnchors.emplace_back(Loc);
     }
   }
 }
 
-void SampleProfileMatcher::runOnFunction(const Function &F,
-                                         const FunctionSamples &FS) {
+void SampleProfileMatcher::runOnFunction(const Function &F) {
+  // We need to use flattened function samples for matching.
+  // Unlike IR, which includes all callsites from the source code, the callsites
+  // in profile only show up when they are hit by samples, i,e. the profile
+  // callsites in one context may differ from those in another context. To get
+  // the maximum number of callsites, we merge the function profiles from all
+  // contexts, aka, the flattened profile to find profile anchors.
+  const auto *FSFlattened = getFlattenedSamplesFor(F);
+  if (!FSFlattened)
+    return;
+
   // Anchors for IR. It's a map from IR location to callee name, callee name is
   // empty for non-call instruction and use a dummy name(UnknownIndirectCallee)
   // for unknown indrect callee name.
   std::map<LineLocation, StringRef> IRAnchors;
   findIRAnchors(F, IRAnchors);
   // Anchors for profile. It's a map from callsite location to a set of callee
   // name.
   std::map<LineLocation, StringSet<>> ProfileAnchors;
-  findProfileAnchors(FS, ProfileAnchors);
+  findProfileAnchors(*FSFlattened, ProfileAnchors);
 
   // Detect profile mismatch for profile staleness metrics report.
   if (ReportProfileStaleness || PersistProfileStaleness) {
-    countProfileMismatches(F, FS, IRAnchors, ProfileAnchors);
+    // Use top-level nested FS for counting profile mismatch metrics since
+    // currently once a callsite is mismatched, all its children profiles are
+    // dropped.
+    if (const auto *FS = Reader.getSamplesFor(F))
+      countProfileMismatches(F, *FS, IRAnchors, ProfileAnchors);
   }
 
   // Run profile matching for checksum mismatched profile, currently only
   // support for pseudo-probe.
   if (SalvageStaleProfile && FunctionSamples::ProfileIsProbeBased &&
-      !ProbeManager->profileIsValid(F, FS)) {
+      !ProbeManager->profileIsValid(F, *FSFlattened)) {
     // The matching result will be saved to IRToProfileLocationMap, create a new
     // map for each function.
     runStaleProfileMatching(F, IRAnchors, ProfileAnchors,
                             getIRToProfileLocationMap(F));
   }
 }
 
 void SampleProfileMatcher::runOnModule() {
+  ProfileConverter::flattenProfile(Reader.getProfiles(), FlattenedProfiles,
+                                   FunctionSamples::ProfileIsCS);
   for (auto &F : M) {
     if (F.isDeclaration() || !F.hasFnAttribute("use-sample-profile"))
       continue;
-    FunctionSamples *FS = nullptr;
-    if (FlattenProfileForMatching)
-      FS = getFlattenedSamplesFor(F);
-    else
-      FS = Reader.getSamplesFor(F);
-    if (!FS)
-      continue;
-    runOnFunction(F, *FS);
+    runOnFunction(F);
   }
   if (SalvageStaleProfile)
     distributeIRToProfileLocationMap();
 
   if (ReportProfileStaleness) {
     if (FunctionSamples::ProfileIsProbeBased) {
       errs() << "(" << NumMismatchedFuncHash << "/" << TotalProfiledFunc << ")"
              << " of functions' profile are invalid and "

llvm/test/Transforms/SampleProfile/profile-mismatch-flattened-profile.ll

-; REQUIRES: x86_64-linux
-; RUN: opt < %S/profile-mismatch.ll -passes=sample-profile -sample-profile-file=%S/Inputs/profile-mismatch.prof -report-profile-staleness -persist-profile-staleness -flatten-profile-for-matching=1 -S 2>%t -o %t.ll
-; RUN: FileCheck %s --input-file %t
-; RUN: FileCheck %s --input-file %t.ll -check-prefix=CHECK-MD
-
-; RUN: opt < %S/profile-mismatch.ll -passes=sample-profile -sample-profile-file=%S/Inputs/profile-mismatch-cs.prof -report-profile-staleness -persist-profile-staleness -flatten-profile-for-matching=1 -S 2>%t -o %t.ll
-; RUN: FileCheck %s --input-file %t
-; RUN: FileCheck %s --input-file %t.ll -check-prefix=CHECK-MD
-
-
-; CHECK: (3/4) of callsites' profile are invalid and (20/30) of samples are discarded due to callsite location mismatch.
-
-; CHECK-MD: ![[#]] = !{!"NumMismatchedCallsites", i64 3, !"TotalProfiledCallsites", i64 4, !"MismatchedCallsiteSamples", i64 20, !"TotalCallsiteSamples", i64 30}

llvm/test/Transforms/SampleProfile/profile-mismatch.ll

 ; REQUIRES: x86_64-linux
-; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/profile-mismatch.prof -report-profile-staleness -persist-profile-staleness -flatten-profile-for-matching=0 -S 2>%t -o %t.ll
+; RUN: opt < %s -passes=sample-profile -sample-profile-file=%S/Inputs/profile-mismatch.prof -report-profile-staleness -persist-profile-staleness -S 2>%t -o %t.ll
 ; RUN: FileCheck %s --input-file %t
 ; RUN: FileCheck %s --input-file %t.ll -check-prefix=CHECK-MD
 ; RUN: llc < %t.ll -filetype=obj -o %t.obj
 ; RUN: llvm-objdump --section-headers %t.obj | FileCheck %s --check-prefix=CHECK-OBJ
 ; RUN: llc < %t.ll -filetype=asm -o - | FileCheck %s --check-prefix=CHECK-ASM
 
 ; CHECK: (2/3) of callsites' profile are invalid and (25/35) of samples are discarded due to callsite location mismatch.