[SamplePGO] Stale profile matching(part 1)

[wlei]

Summary

AutoFDO/CSSPGO often has to deal with stale profiles collected on binaries built from several revisions behind release. It’s likely to get incorrect profile annotations using the stale profile, which results in unstable or low performing binaries. Currently for source location based profile, once a code change causes a profile mismatch, all the locations afterward are mismatched, the affected samples or inlining info are lost. If we can provide a matching framework to reuse parts of the mismatched profile - aka incremental PGO, it will make PGO more stable, also increase the optimization coverage and boost the performance of binary.

This patch is the part 1 of stale profile matching, summary of the implementation:

• Added a structure for the matching result:LocToLocMap, which is a location to location map meaning the location of current build is matched to the location of the previous build(to be used to query the “stale” profile).
• In order to use the matching results for sample query, we need to pass them to all the location queries. For code cleanliness, we added a new pointer field(IRToProfileLocationMap) to FunctionSamples.
• Added a wrapper(mapIRLocToProfileLoc) for the query to the location, the location from input IR will be remapped to the matched profile location.
• Added a new switch --salvage-stale-profile.
• Some refactoring for the staleness detection.

Test case is in part 2 with the matching algorithm.

[hoy]

llvm/include/llvm/ProfileData/SampleProf.h

1247

nit: "generated by" -> "used for"

llvm/lib/Transforms/IPO/SampleProfile.cpp

448

nit: For each function, the matcher generates a map, of which each entry is a mapping from the location
of current build to the location in the profile.

451

Where is this DS populated? Is it in a separate patch?

2197

Condition this under ReportProfileStaleness || PersistProfileStaleness ?

[wenlei]

Thanks for working on this. Looks good overall, except a few naming nits.

llvm/include/llvm/ProfileData/SampleProf.h

845

similarly, mapIRLocToProfileLoc?

1264

How about name it IRToProfileLocationMap to make it more explicit.

llvm/lib/Transforms/IPO/SampleProfile.cpp

134

nit: we always match profile regardless of staleness. how about something like salvage-stale-profile (or sample-profile-salvage-stale)

451

same question. I saw it being populated in the 2nd patch, but the split between the two patches is a bit weird if its population is left out. not a big deal though as long as the entire stack works..

2100

With the refactoring, this function is now narrower, and perhaps we could rename it to something like countProfileMismatches to reflect the narrowed scope.

[davidxl]

Nice.

Just browsed the patch, I don't seem to find how FUncToMatchingsMap is populated which is the core of the stale profile matching algorithm. Does algorithm use some anchor points to do the remapping?

By the way, another way is to offline remapping --- basically 'correcting' the stale profile by mapping the old locations to the new locations and produce a refreshed profile. This is what we plan to do internally.

[hoy]

In D147456#4246648, @davidxl wrote:

By the way, another way is to offline remapping --- basically 'correcting' the stale profile by mapping the old locations to the new locations and produce a refreshed profile. This is what we plan to do internally.

This sounds interesting. By offline do you mean the profile generation time? Wondering how to get the new locations without building the new binary.

[davidxl]

In D147456#4246695, @hoy wrote:

In D147456#4246648, @davidxl wrote:

By the way, another way is to offline remapping --- basically 'correcting' the stale profile by mapping the old locations to the new locations and produce a refreshed profile. This is what we plan to do internally.

This sounds interesting. By offline do you mean the profile generation time? Wondering how to get the new locations without building the new binary.

Right -- the source revision information is available for any target in the build environment.

llvm/lib/Transforms/IPO/SampleProfile.cpp

451

It is better make that part available to review at the same time for better context.

[mtrofin]

llvm/include/llvm/ProfileData/SampleProf.h

1061

drive-by nits:

• s/M/LTLM or basically anything that's not suggestive of "M == Module", which is seen everywhere else in the codebase
• can StaleProfileMappings be const LocToLocMap? (and same then for the parameter of this setter) - it would simplify the burden on a future reader/maintainer
• is StaleProfileMappings expected to be updated multiple times? if not, could you assert(StaleProfileMappings == null && "this should be set only once") - same maintainability argument.

llvm/lib/Transforms/IPO/SampleProfile.cpp

483

drive-by nit: could this be called distributeStaleProfileMappings?

484

do these need to be public?

[wenlei]

In D147456#4246749, @davidxl wrote:

In D147456#4246695, @hoy wrote:

In D147456#4246648, @davidxl wrote:

By the way, another way is to offline remapping --- basically 'correcting' the stale profile by mapping the old locations to the new locations and produce a refreshed profile. This is what we plan to do internally.

This sounds interesting. By offline do you mean the profile generation time? Wondering how to get the new locations without building the new binary.

Right -- the source revision information is available for any target in the build environment.

By doing the mapping during profile generation outside of compiler, you would need a new profile for each target source version. That seems less flexible comparing to doing the mapping in the compiler where the mapping is naturally built for the current source being compiled.

[davidxl]

In D147456#4246802, @wenlei wrote:

In D147456#4246749, @davidxl wrote:

In D147456#4246695, @hoy wrote:

In D147456#4246648, @davidxl wrote:

By the way, another way is to offline remapping --- basically 'correcting' the stale profile by mapping the old locations to the new locations and produce a refreshed profile. This is what we plan to do internally.

This sounds interesting. By offline do you mean the profile generation time? Wondering how to get the new locations without building the new binary.

Right -- the source revision information is available for any target in the build environment.

By doing the mapping during profile generation outside of compiler, you would need a new profile for each target source version. That seems less flexible comparing to doing the mapping in the compiler where the mapping is naturally built for the current source being compiled.

In practice, it does not need to be -- aka many kinds of source changed don't need to trigger profile updating. Changes to cold source paths don't matter either. It is ok for the target source revision of the updated profile to be behind that of the actual build.

[wenlei]

In D147456#4246994, @davidxl wrote:

In D147456#4246802, @wenlei wrote:

In D147456#4246749, @davidxl wrote:

In D147456#4246695, @hoy wrote:

In D147456#4246648, @davidxl wrote:

By the way, another way is to offline remapping --- basically 'correcting' the stale profile by mapping the old locations to the new locations and produce a refreshed profile. This is what we plan to do internally.

This sounds interesting. By offline do you mean the profile generation time? Wondering how to get the new locations without building the new binary.

Right -- the source revision information is available for any target in the build environment.

By doing the mapping during profile generation outside of compiler, you would need a new profile for each target source version. That seems less flexible comparing to doing the mapping in the compiler where the mapping is naturally built for the current source being compiled.

In practice, it does not need to be -- aka many kinds of source changed don't need to trigger profile updating. Changes to cold source paths don't matter either. It is ok for the target source revision of the updated profile to be behind that of the actual build.

Sure, then you need to make sure the source version you are generating profile for doesn't diverge too much from the source version that you will actually compile. Often times we also can't predict the source version that will actually be used for compilation later, what if a last minute sizable hotfix is landed? What you described should be doable, but more work/complexity IMO. Isn't it easier if this is all handled at compile time transparently within the compiler, given the cost of doing that isn't really measurable.

[davidxl]

In D147456#4247011, @wenlei wrote:

In D147456#4246994, @davidxl wrote:

In D147456#4246802, @wenlei wrote:

In D147456#4246749, @davidxl wrote:

In D147456#4246695, @hoy wrote:

In D147456#4246648, @davidxl wrote:

By the way, another way is to offline remapping --- basically 'correcting' the stale profile by mapping the old locations to the new locations and produce a refreshed profile. This is what we plan to do internally.

This sounds interesting. By offline do you mean the profile generation time? Wondering how to get the new locations without building the new binary.

Right -- the source revision information is available for any target in the build environment.

By doing the mapping during profile generation outside of compiler, you would need a new profile for each target source version. That seems less flexible comparing to doing the mapping in the compiler where the mapping is naturally built for the current source being compiled.

In practice, it does not need to be -- aka many kinds of source changed don't need to trigger profile updating. Changes to cold source paths don't matter either. It is ok for the target source revision of the updated profile to be behind that of the actual build.

Sure, then you need to make sure the source version you are generating profile for doesn't diverge too much from the source version that you will actually compile. Often times we also can't predict the source version that will actually be used for compilation later, what if a last minute sizable hotfix is landed? What you described should be doable, but more work/complexity IMO. Isn't it easier if this is all handled at compile time transparently within the compiler, given the cost of doing that isn't really measurable.

The updating can be done on-demand based on triggers (source changes or direct user directive). Doing this offline can open up more expensive fuzzy algorithms (open ended). Having a layer in the compiler to do this is fine -- though would like to see how effective it is for our internal workloads).

[wlei]

Thank you for all the feedback, I will try to address it later. I saw you all are curious the algorithm part, here it is: https://reviews.llvm.org/D147545.

Just browsed the patch, I don't seem to find how FUncToMatchingsMap is populated which is the core of the stale profile matching algorithm. Does algorithm use some anchor points to do the remapping?

Yes, here is the algorithm part : https://reviews.llvm.org/D147545, it leverages the callee name/ calltarget name as anchor which doesn't need any other additional info.

[davidxl]

In D147456#4247075, @wlei wrote:

Thank you for all the feedback, I will try to address it later. I saw you all are curious the algorithm part, here it is: https://reviews.llvm.org/D147545.

Just browsed the patch, I don't seem to find how FUncToMatchingsMap is populated which is the core of the stale profile matching algorithm. Does algorithm use some anchor points to do the remapping?

Yes, here is the algorithm part : https://reviews.llvm.org/D147545, it leverages the callee name/ calltarget name as anchor which doesn't need any other additional info.

thanks. The anchor based remapping can be effective to formatting changes, NFC changes such as adding new comments in the source .

[mingmingl]

In D147456#4247075, @wlei wrote:

Thank you for all the feedback, I will try to address it later. I saw you all are curious the algorithm part, here it is: https://reviews.llvm.org/D147545.

Just browsed the patch, I don't seem to find how FUncToMatchingsMap is populated which is the core of the stale profile matching algorithm. Does algorithm use some anchor points to do the remapping?

Yes, here is the algorithm part : https://reviews.llvm.org/D147545, it leverages the callee name/ calltarget name as anchor which doesn't need any other additional info.

Just curious, I wonder if there happens to be a measurement of the percentage of samples recovered (that would have been dropped) for csspgo. I guess I'm trying see how much headroom remains with D147545 :)

[wenlei]

In D147456#4247035, @davidxl wrote:

In D147456#4247011, @wenlei wrote:

In D147456#4246994, @davidxl wrote:

In D147456#4246802, @wenlei wrote:

In D147456#4246749, @davidxl wrote:

In D147456#4246695, @hoy wrote:

In D147456#4246648, @davidxl wrote:

By the way, another way is to offline remapping --- basically 'correcting' the stale profile by mapping the old locations to the new locations and produce a refreshed profile. This is what we plan to do internally.

This sounds interesting. By offline do you mean the profile generation time? Wondering how to get the new locations without building the new binary.

Right -- the source revision information is available for any target in the build environment.

By doing the mapping during profile generation outside of compiler, you would need a new profile for each target source version. That seems less flexible comparing to doing the mapping in the compiler where the mapping is naturally built for the current source being compiled.

In practice, it does not need to be -- aka many kinds of source changed don't need to trigger profile updating. Changes to cold source paths don't matter either. It is ok for the target source revision of the updated profile to be behind that of the actual build.

Sure, then you need to make sure the source version you are generating profile for doesn't diverge too much from the source version that you will actually compile. Often times we also can't predict the source version that will actually be used for compilation later, what if a last minute sizable hotfix is landed? What you described should be doable, but more work/complexity IMO. Isn't it easier if this is all handled at compile time transparently within the compiler, given the cost of doing that isn't really measurable.

The updating can be done on-demand based on triggers (source changes or direct user directive). Doing this offline can open up more expensive fuzzy algorithms (open ended). Having a layer in the compiler to do this is fine -- though would like to see how effective it is for our internal workloads).

Ok. Full disclosure though, we started with ideas around more sophisticated fuzzy graph matching for CSSPGO (we even emit cfg info into profile for some experiments), but settled on simpler algorithm since that worked good enough. We will upstream additional "breaking change" for probe Id assignment later that pushes this to be more effective for CSSPGO.

[wlei]

In D147456#4247167, @mingmingl wrote:

In D147456#4247075, @wlei wrote:

Thank you for all the feedback, I will try to address it later. I saw you all are curious the algorithm part, here it is: https://reviews.llvm.org/D147545.

Just browsed the patch, I don't seem to find how FUncToMatchingsMap is populated which is the core of the stale profile matching algorithm. Does algorithm use some anchor points to do the remapping?

Yes, here is the algorithm part : https://reviews.llvm.org/D147545, it leverages the callee name/ calltarget name as anchor which doesn't need any other additional info.

Just curious, I wonder if there happens to be a measurement of the percentage of samples recovered (that would have been dropped) for csspgo. I guess I'm trying see how much headroom remains with D147545 :)

Good point, so far no, it's doable, we have the https://reviews.llvm.org/D136627 to compute how many samples are dropped due to the CSSPGO's checksum mismatch, which is what this stale profile matching want to reuse. Similarly, after the matching in D147545, we can compute how many samples/callsites in profile still remains mismatched.

[wlei]

llvm/include/llvm/ProfileData/SampleProf.h

1061

Thanks for the feedback, all make sense, done.

1247

This is the output of the matching algorithm, not to be used for the matching:)

1264

Sounds good, done.

llvm/lib/Transforms/IPO/SampleProfile.cpp

134

Sounds good.

451

Ok, sorry for the confusing. I will move it to the second part.

483

Sounds good.

484

Will move to private.

2100

Done.

2197

Done. Note: this is also going to be used for matching work for classic AutoFDO. For matching, it need this mismatch metrics to suggest whether to use the matching, for pseudo probe, there is the checksum but doesn't apply to AutoFDO. Will leave when we worked on AutoFDO.

[wlei]

addressing feedback

[wenlei]

lgtm (change description needs updating to reflect new switch name)

[davidxl]

llvm/include/llvm/ProfileData/SampleProf.h

848

NewLoc can be confusing. Perhaps name it "OrigLoc" or "ProfileLoc".

[wlei]

Updating D147456: [AutoFDO] Stale profile matching(part 1)

llvm/include/llvm/ProfileData/SampleProf.h

848

Changed to ProfileLoc , thanks!

[mysterymath]

It looks like this change or its followup is causing test failures on the Fuchsia toolchain builders:

https://luci-milo.appspot.com/ui/p/fuchsia/builders/toolchain.ci/clang-linux-x64/b8782540257332498033/test-results?sortby=&groupby=

Script:
--
: 'RUN: at line 3';   /b/s/w/ir/x/w/staging/llvm_build/bin/opt < /b/s/w/ir/x/w/llvm-llvm-project/llvm/test/Transforms/SampleProfile/pseudo-probe-stale-profile-matching.ll -passes=sample-profile -sample-profile-file=/b/s/w/ir/x/w/llvm-llvm-project/llvm/test/Transforms/SampleProfile/Inputs/pseudo-probe-stale-profile-matching.prof --salvage-stale-profile -S --debug-only=sample-profile 2>&1 | /b/s/w/ir/x/w/staging/llvm_build/bin/FileCheck /b/s/w/ir/x/w/llvm-llvm-project/llvm/test/Transforms/SampleProfile/pseudo-probe-stale-profile-matching.ll
--
Exit Code: 1

Command Output (stderr):
--
/b/s/w/ir/x/w/llvm-llvm-project/llvm/test/Transforms/SampleProfile/pseudo-probe-stale-profile-matching.ll:66:10: error: CHECK: expected string not found in input
; CHECK: Callsite with callee:foo is matched from 13 to 6
         ^
<stdin>:12:34: note: scanning from here
Location is matched from 11 to 11
                                 ^
<stdin>:13:1: note: possible intended match here
Callsite with callee:foo is matched from 13 to 0
^

[wlei]

In D147456#4306762, @mysterymath wrote:

It looks like this change or its followup is causing test failures on the Fuchsia toolchain builders:

https://luci-milo.appspot.com/ui/p/fuchsia/builders/toolchain.ci/clang-linux-x64/b8782540257332498033/test-results?sortby=&groupby=

Script:
--
: 'RUN: at line 3';   /b/s/w/ir/x/w/staging/llvm_build/bin/opt < /b/s/w/ir/x/w/llvm-llvm-project/llvm/test/Transforms/SampleProfile/pseudo-probe-stale-profile-matching.ll -passes=sample-profile -sample-profile-file=/b/s/w/ir/x/w/llvm-llvm-project/llvm/test/Transforms/SampleProfile/Inputs/pseudo-probe-stale-profile-matching.prof --salvage-stale-profile -S --debug-only=sample-profile 2>&1 | /b/s/w/ir/x/w/staging/llvm_build/bin/FileCheck /b/s/w/ir/x/w/llvm-llvm-project/llvm/test/Transforms/SampleProfile/pseudo-probe-stale-profile-matching.ll
--
Exit Code: 1

Command Output (stderr):
--
/b/s/w/ir/x/w/llvm-llvm-project/llvm/test/Transforms/SampleProfile/pseudo-probe-stale-profile-matching.ll:66:10: error: CHECK: expected string not found in input
; CHECK: Callsite with callee:foo is matched from 13 to 6
         ^
<stdin>:12:34: note: scanning from here
Location is matched from 11 to 11
                                 ^
<stdin>:13:1: note: possible intended match here
Callsite with callee:foo is matched from 13 to 0
^

Sorry for the break, push an attempt to fix https://reviews.llvm.org/rGba3cbc7aadf9, let me know if it doesn't work.

llvm/include/llvm/ProfileData/SampleProf.h

 class FunctionSamples;
 class SampleProfileReaderItaniumRemapper;
 
 using BodySampleMap = std::map<LineLocation, SampleRecord>;
 // NOTE: Using a StringMap here makes parsed profiles consume around 17% more
 // memory, which is *very* significant for large profiles.
 using FunctionSamplesMap = std::map<std::string, FunctionSamples, std::less<>>;
 using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>;
+using LocToLocMap =
+    std::unordered_map<LineLocation, LineLocation, LineLocationHash>;
 
 /// Representation of the samples collected for a function.
 ///
 /// This data structure contains all the collected samples for the body
 /// of a function. Each sample corresponds to a LineLocation instance
 /// within the body of the function.
 class FunctionSamples {
 public:
void SetContextSynthetic() {
     Context.setState(SyntheticContext);
     for (auto &I : CallsiteSamples) {
       for (auto &CS : I.second) {
         CS.second.SetContextSynthetic();
       }
     }
   }
 
+  // Query the stale profile matching results and remap the location.
+  // There is no remapping if the profile is not stale or the matching gives the
+  // same location.
+  const LineLocation &remapLoc(const LineLocation &Loc) const {
+    if (!StaleProfileMappings)
+      return Loc;
+    auto NewLoc = StaleProfileMappings->find(Loc);
+    if (NewLoc != StaleProfileMappings->end())
+      return NewLoc->second;
+    else
+      return Loc;
+  }
+
   /// Return the number of samples collected at the given location.
   /// Each location is specified by \p LineOffset and \p Discriminator.
   /// If the location is not found in profile, return error.
   ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset,
                                   uint32_t Discriminator) const {
-    const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
+    const auto &ret =
+        BodySamples.find(remapLoc(LineLocation(LineOffset, Discriminator)));
     if (ret == BodySamples.end())
       return std::error_code();
     return ret->second.getSamples();
   }
 
   /// Returns the call target map collected at a given location.
   /// Each location is specified by \p LineOffset and \p Discriminator.
   /// If the location is not found in profile, return error.
   ErrorOr<SampleRecord::CallTargetMap>
   findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const {
-    const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
+    const auto &ret =
+        BodySamples.find(remapLoc(LineLocation(LineOffset, Discriminator)));
     if (ret == BodySamples.end())
       return std::error_code();
     return ret->second.getCallTargets();
   }
 
   /// Returns the call target map collected at a given location specified by \p
   /// CallSite. If the location is not found in profile, return error.
   ErrorOr<SampleRecord::CallTargetMap>
   findCallTargetMapAt(const LineLocation &CallSite) const {
-    const auto &Ret = BodySamples.find(CallSite);
+    const auto &Ret = BodySamples.find(remapLoc(CallSite));
     if (Ret == BodySamples.end())
       return std::error_code();
     return Ret->second.getCallTargets();
   }
 
   /// Return the function samples at the given callsite location.
   FunctionSamplesMap &functionSamplesAt(const LineLocation &Loc) {
-    return CallsiteSamples[Loc];
+    return CallsiteSamples[remapLoc(Loc)];
   }
 
   /// Returns the FunctionSamplesMap at the given \p Loc.
   const FunctionSamplesMap *
   findFunctionSamplesMapAt(const LineLocation &Loc) const {
-    auto iter = CallsiteSamples.find(Loc);
+    auto iter = CallsiteSamples.find(remapLoc(Loc));
     if (iter == CallsiteSamples.end())
       return nullptr;
     return &iter->second;
   }
 
   /// Returns a pointer to FunctionSamples at the given callsite location
   /// \p Loc with callee \p CalleeName. If no callsite can be found, relax
   /// the restriction to return the FunctionSamples at callsite location
public:
 
   /// Return the original function name.
   StringRef getFuncName() const { return getFuncName(getName()); }
 
   void setFunctionHash(uint64_t Hash) { FunctionHash = Hash; }
 
   uint64_t getFunctionHash() const { return FunctionHash; }
 
+  void setStaleProfileMappings(LocToLocMap *M) { StaleProfileMappings = M; }
+
   /// Return the canonical name for a function, taking into account
   /// suffix elision policy attributes.
   static StringRef getCanonicalFnName(const Function &F) {
     auto AttrName = "sample-profile-suffix-elision-policy";
     auto Attr = F.getFnAttribute(AttrName).getValueAsString();
     return getCanonicalFnName(F.getName(), Attr);
   }
 
private:
   ///  8    baz();
   ///     }
   ///
   /// If the bar() and baz() calls were inlined inside foo(), this
   /// map will contain two entries.  One for all the samples collected
   /// in the call to bar() at line offset 1, the other for all the samples
   /// collected in the call to baz() at line offset 8.
   CallsiteSampleMap CallsiteSamples;
+
+  /// Location mappings generated by stale profile matching.
+  ///
+  /// Each entry is a mapping from the location on current build to the matched
+  /// location in the "stale" profile. For example:
+  ///   Profiled source code:
+  ///      void foo() {
+  ///   1    bar();
+  ///      }
+  ///
+  ///   Current source code:
+  ///      void foo() {
+  ///   1    // Code change
+  ///   2    bar();
+  ///      }
+  /// Supposing the stale profile matching algorithm generated the mapping [2 ->
+  /// 1], the profile query using the location of bar on the IR which is 2 will
+  /// be remapped to 1 and find the location of bar in the profile.
+  LocToLocMap *StaleProfileMappings = nullptr;
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS);
 
 using SampleProfileMap =
     std::unordered_map<SampleContext, FunctionSamples, SampleContext::Hash>;
 
 using NameFunctionSamples = std::pair<SampleContext, const FunctionSamples *>;

llvm/lib/ProfileData/SampleProf.cpp

 const FunctionSamples *FunctionSamples::findFunctionSamplesAt(
     const LineLocation &Loc, StringRef CalleeName,
     SampleProfileReaderItaniumRemapper *Remapper) const {
   CalleeName = getCanonicalFnName(CalleeName);
 
   std::string CalleeGUID;
   CalleeName = getRepInFormat(CalleeName, UseMD5, CalleeGUID);
 
-  auto iter = CallsiteSamples.find(Loc);
+  auto iter = CallsiteSamples.find(remapLoc(Loc));
   if (iter == CallsiteSamples.end())
     return nullptr;
   auto FS = iter->second.find(CalleeName);
   if (FS != iter->second.end())
     return &FS->second;
   if (Remapper) {
     if (auto NameInProfile = Remapper->lookUpNameInProfile(CalleeName)) {
       auto FS = iter->second.find(*NameInProfile);

llvm/lib/Transforms/IPO/SampleProfile.cpp

 
 // The named file contains a set of transformations that may have been applied
 // to the symbol names between the program from which the sample data was
 // collected and the current program's symbols.
 static cl::opt<std::string> SampleProfileRemappingFile(
     "sample-profile-remapping-file", cl::init(""), cl::value_desc("filename"),
     cl::desc("Profile remapping file loaded by -sample-profile"), cl::Hidden);
 
+static cl::opt<bool> SampleProfileMatching(
+    "sample-profile-matching", cl::Hidden, cl::init(false),
+    cl::desc("Run stale profile matching algorithm and use the remapped "
+             "location for sample profile query."));
+
 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)."));
PriorityQueue<InlineCandidate, std::vector<InlineCandidate>,
                   CandidateComparer>;
 
 // Sample profile matching - fuzzy match.
 class SampleProfileMatcher {
   Module &M;
   SampleProfileReader &Reader;
   const PseudoProbeManager *ProbeManager;
   SampleProfileMap FlattenedProfiles;
+  // The output of stale profile matching. For each function, the matching
+  // algorithm generates a map, each entry is a mapping meaning the location
+  // of current build is matched to the location in the profile.
+  StringMap<LocToLocMap> FuncToMatchingsMap;
 
   // Profile mismatching statstics.
   uint64_t TotalProfiledCallsites = 0;
   uint64_t NumMismatchedCallsites = 0;
   uint64_t MismatchedCallsiteSamples = 0;
   uint64_t TotalCallsiteSamples = 0;
   uint64_t TotalProfiledFunc = 0;
   uint64_t NumMismatchedFuncHash = 0;
public:
   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 detectProfileMismatch();
-  void detectProfileMismatch(const Function &F, const FunctionSamples &FS);
+  void runOnModule();
+  void runOnFunction(const Function &F, const FunctionSamples &FS);
+  void setStaleProfileMappings();
+  void setStaleProfileMappings(FunctionSamples &FS);
+  void
+  detectProfileMismatch(const FunctionSamples &FS,
+                        const std::unordered_set<LineLocation, LineLocationHash>
+                            &MatchedCallsiteLocs);
 };
 
 /// Sample profile pass.
 ///
 /// This pass reads profile data from the file specified by
 /// -sample-profile-file and annotates every affected function with the
 /// profile information found in that file.
 class SampleProfileLoader final
if (!ProbeManager->moduleIsProbed(M)) {
       const char *Msg =
           "Pseudo-probe-based profile requires SampleProfileProbePass";
       Ctx.diagnose(DiagnosticInfoSampleProfile(M.getModuleIdentifier(), Msg,
                                                DS_Warning));
       return false;
     }
   }
 
-  if (ReportProfileStaleness || PersistProfileStaleness) {
+  if (ReportProfileStaleness || PersistProfileStaleness ||
+      SampleProfileMatching) {
     MatchingManager =
         std::make_unique<SampleProfileMatcher>(M, *Reader, ProbeManager.get());
   }
 
   return true;
 }
 
-void SampleProfileMatcher::detectProfileMismatch(const Function &F,
-                                                 const FunctionSamples &FS) {
+void SampleProfileMatcher::detectProfileMismatch(
+    const FunctionSamples &FS,
+    const std::unordered_set<LineLocation, LineLocationHash>
+        &MatchedCallsiteLocs) {
+
+  auto isInvalidLineOffset = [](uint32_t LineOffset) {
+    return LineOffset & 0x8000;
+  };
+
+  // Check if there are any callsites in the profile that does not match to any
+  // IR callsites, those callsite samples will be discarded.
+  for (auto &I : FS.getBodySamples()) {
+    const LineLocation &Loc = I.first;
+    if (isInvalidLineOffset(Loc.LineOffset))
+      continue;
+
+    uint64_t Count = I.second.getSamples();
+    if (!I.second.getCallTargets().empty()) {
+      TotalCallsiteSamples += Count;
+      TotalProfiledCallsites++;
+      if (!MatchedCallsiteLocs.count(Loc)) {
+        MismatchedCallsiteSamples += Count;
+        NumMismatchedCallsites++;
+      }
+    }
+  }
+
+  for (auto &I : FS.getCallsiteSamples()) {
+    const LineLocation &Loc = I.first;
+    if (isInvalidLineOffset(Loc.LineOffset))
+      continue;
+
+    uint64_t Count = 0;
+    for (auto &FM : I.second) {
+      Count += FM.second.getHeadSamplesEstimate();
+    }
+    TotalCallsiteSamples += Count;
+    TotalProfiledCallsites++;
+    if (!MatchedCallsiteLocs.count(Loc)) {
+      MismatchedCallsiteSamples += Count;
+      NumMismatchedCallsites++;
+    }
+  }
+}
+
+void SampleProfileMatcher::runOnFunction(const Function &F,
   if (FunctionSamples::ProfileIsProbeBased) {
     uint64_t Count = FS.getTotalSamples();
     TotalFuncHashSamples += Count;
     TotalProfiledFunc++;
     if (!ProbeManager->profileIsValid(F, FS)) {
       MismatchedFuncHashSamples += Count;
       NumMismatchedFuncHash++;
       return;
for (auto &I : BB) {
           if ((CTM && CTM->count(CalleeName)) ||
               (CallsiteFS && CallsiteFS->count(CalleeName)))
             MatchedCallsiteLocs.insert(IRCallsite);
         }
       }
     }
   }
 
-  auto isInvalidLineOffset = [](uint32_t LineOffset) {
-    return LineOffset & 0x8000;
-  };
-
-  // Check if there are any callsites in the profile that does not match to any
-  // IR callsites, those callsite samples will be discarded.
-  for (auto &I : FS.getBodySamples()) {
-    const LineLocation &Loc = I.first;
-    if (isInvalidLineOffset(Loc.LineOffset))
-      continue;
-
-    uint64_t Count = I.second.getSamples();
-    if (!I.second.getCallTargets().empty()) {
-      TotalCallsiteSamples += Count;
-      TotalProfiledCallsites++;
-      if (!MatchedCallsiteLocs.count(Loc)) {
-        MismatchedCallsiteSamples += Count;
-        NumMismatchedCallsites++;
-      }
-    }
-  }
+  // Detect profile mismatch for profile staleness metrics report.
+  detectProfileMismatch(FS, MatchedCallsiteLocs);
 
-  for (auto &I : FS.getCallsiteSamples()) {
-    const LineLocation &Loc = I.first;
-    if (isInvalidLineOffset(Loc.LineOffset))
-      continue;
-
-    uint64_t Count = 0;
-    for (auto &FM : I.second) {
-      Count += FM.second.getHeadSamplesEstimate();
-    }
-    TotalCallsiteSamples += Count;
-    TotalProfiledCallsites++;
-    if (!MatchedCallsiteLocs.count(Loc)) {
-      MismatchedCallsiteSamples += Count;
-      NumMismatchedCallsites++;
-    }
-  }
-}
-
-void SampleProfileMatcher::detectProfileMismatch() {
+void SampleProfileMatcher::runOnModule() {
   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;
-    detectProfileMismatch(F, *FS);
+    runOnFunction(F, *FS);
   }
 
+  if (SampleProfileMatching)
+    setStaleProfileMappings();
+
   if (ReportProfileStaleness) {
     if (FunctionSamples::ProfileIsProbeBased) {
       errs() << "(" << NumMismatchedFuncHash << "/" << TotalProfiledFunc << ")"
              << " of functions' profile are invalid and "
              << " (" << MismatchedFuncHashSamples << "/" << TotalFuncHashSamples
              << ")"
              << " of samples are discarded due to function hash mismatch.\n";
     }
if (PersistProfileStaleness) {
     ProfStatsVec.emplace_back("TotalCallsiteSamples", TotalCallsiteSamples);
 
     auto *MD = MDB.createLLVMStats(ProfStatsVec);
     auto *NMD = M.getOrInsertNamedMetadata("llvm.stats");
     NMD->addOperand(MD);
   }
 }
 
+void SampleProfileMatcher::setStaleProfileMappings(FunctionSamples &FS) {
+  const auto ProfileMappings = FuncToMatchingsMap.find(FS.getName());
+  if (ProfileMappings != FuncToMatchingsMap.end()) {
+    FS.setStaleProfileMappings(&(ProfileMappings->second));
+  }
+
+  for (auto &Inlinees : FS.getCallsiteSamples()) {
+    for (auto FS : Inlinees.second) {
+      setStaleProfileMappings(FS.second);
+    }
+  }
+}
+
+// Use a central place to distribute the matching results. Outlined and inlined
+// profile with the function name will be set to the same pointer.
+void SampleProfileMatcher::setStaleProfileMappings() {
+  for (auto &I : Reader.getProfiles()) {
+    setStaleProfileMappings(I.second);
+  }
+}
+
 bool SampleProfileLoader::runOnModule(Module &M, ModuleAnalysisManager *AM,
                                       ProfileSummaryInfo *_PSI,
                                       LazyCallGraph &CG) {
   GUIDToFuncNameMapper Mapper(M, *Reader, GUIDToFuncNameMap);
 
   PSI = _PSI;
   if (M.getProfileSummary(/* IsCS */ false) == nullptr) {
     M.setProfileSummary(Reader->getSummary().getMD(M.getContext()),
if (Remapper) {
         if (*MapName != OrigName && !MapName->empty())
           SymbolMap.insert(std::make_pair(*MapName, F));
       }
     }
   }
   assert(SymbolMap.count(StringRef()) == 0 &&
          "No empty StringRef should be added in SymbolMap");
 
-  if (ReportProfileStaleness || PersistProfileStaleness)
-    MatchingManager->detectProfileMismatch();
+  if (ReportProfileStaleness || PersistProfileStaleness ||
+      SampleProfileMatching) {
+    MatchingManager->runOnModule();
+  }
 
   bool retval = false;
   for (auto *F : buildFunctionOrder(M, CG)) {
     assert(!F->isDeclaration());
     clearFunctionData();
     retval |= runOnFunction(*F, AM);
   }