[AutoFDO] Make call targets order deterministic for sample profil

[wenlei]

Summary

StringMap is used for storing call target to frequency map for AutoFDO. However the iterating order of StringMap is non-deterministic, which leads to non-determinism in AutoFDO profile output. Now StringMap is changed to std::map for deterministic ordering and output.

Roundtrip test for text profile and binary profile is added.

[wenlei]

update description

[wenlei]

rebase

[wmi]

Thanks for working on it.

llvm/include/llvm/ProfileData/SampleProf.h

146

StringMap is more effient than std::map, but I assume the call targets list won't be very long so using std::map may not be an issue for compile time.

A problem of map is that if we want to sort CallTargetMap, I like to see the targets are sorted in count order (high to low) instead of alphabet order, so the dump will be more meaningful and we don't need sort the targets again using SortCallTargets in SampleProfile.cpp. But map cannot be internally sorted in its value_type.

How about leave CallTargetMap as a StringMap and make SortCallTargets a member function of SampleRecord and sort CallTargetMap before dumping and file writing?

[wenlei]

llvm/include/llvm/ProfileData/SampleProf.h

146

Thanks for review. Yeah, I think the number of targets is so small that efficiency benefit of StringMap is not important.

I would actually prefer the targets to be in alphabetical order - that makes the textual profile more 'stable' thus easy to compare (line by line) for count difference.

Besides, having to sort before dump moves the sorting responsibility to SampleProfileWriter for all difference formats, that's kind of duplicated, and doesn't prevent adding future writer without sorting before dumping.

SortCallTargets currently converts StringMap<uint64_t> to SmallVector<InstrProfValueData> first, then sort in place, if we extract a common Sort helper, we would need an extra copy to hold sorted result before converting to InstrProfValueData. The overhead won't be visible, but just feel it's not that clean either.

I don't have strong opinion, but do prefer to leave it as. Let me know if that is ok. Thanks.

[wmi]

llvm/include/llvm/ProfileData/SampleProf.h

146

I would actually prefer the targets to be in alphabetical order - that makes the textual profile more 'stable' thus easy to compare (line by line) for count difference.

Even you order the targets in alphabetical order, there may be some targets showing up in one profile and disappearing in another profile -- causing a lot of churn for profile comparison. Usually the top call targets are what you concern the most. If the top call targets are scattered in a long list and their changes are amid some other targets's changes, it is easy to miss some of them.

[wenlei]

Add getSortedCallTargets and SortCallTargets, per review feedback.

[wenlei]

rebase

[wmi]

LGTM. Thanks!

llvm/lib/Transforms/IPO/SampleProfile.cpp

1306

Nit: emplace may be better.

[wenlei]

address review feedback

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1306

Thanks for review. Now changed to emplace_back.

llvm/include/llvm/ProfileData/SampleProf.h

 ///
 /// Additionally, if the associated location contains a function call,
 /// the record will hold a list of all the possible called targets. For
 /// direct calls, this will be the exact function being invoked. For
 /// indirect calls (function pointers, virtual table dispatch), this
 /// will be a list of one or more functions.
 class SampleRecord {
 public:
-  using CallTargetMap = StringMap<uint64_t>;
+  using CallTargetMap = std::map<StringRef,uint64_t>;
 
   SampleRecord() = default;
 
   /// Increment the number of samples for this record by \p S.
   /// Optionally scale sample count \p S by \p Weight.
   ///
   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
   /// around unsigned integers.
public:
   uint64_t getSamples() const { return NumSamples; }
   const CallTargetMap &getCallTargets() const { return CallTargets; }
 
   /// Merge the samples in \p Other into this record.
   /// Optionally scale sample counts by \p Weight.
   sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1) {
     sampleprof_error Result = addSamples(Other.getSamples(), Weight);
     for (const auto &I : Other.getCallTargets()) {
-      MergeResult(Result, addCalledTarget(I.first(), I.second, Weight));
+      MergeResult(Result, addCalledTarget(I.first, I.second, Weight));
     }
     return Result;
   }
 
   void print(raw_ostream &OS, unsigned Indent) const;
   void dump() const;
 
 private:
void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
                             uint64_t Threshold) const {
     if (TotalSamples <= Threshold)
       return;
     S.insert(getGUID(Name));
     // Import hot CallTargets, which may not be available in IR because full
     // profile annotation cannot be done until backend compilation in ThinLTO.
     for (const auto &BS : BodySamples)
       for (const auto &TS : BS.second.getCallTargets())
-        if (TS.getValue() > Threshold) {
+        if (TS.second > Threshold) {
           const Function *Callee =
-              M->getFunction(getNameInModule(TS.getKey(), M));
+              M->getFunction(getNameInModule(TS.first, M));
           if (!Callee || !Callee->getSubprogram())
-            S.insert(getGUID(TS.getKey()));
+            S.insert(getGUID(TS.first));
         }
     for (const auto &CS : CallsiteSamples)
       for (const auto &NameFS : CS.second)
         NameFS.second.findInlinedFunctions(S, M, Threshold);
   }
 
   /// Set the name of the function.
   void setName(StringRef FunctionName) { Name = FunctionName; }

llvm/lib/ProfileData/SampleProf.cpp

 #endif
 
 /// Print the sample record to the stream \p OS indented by \p Indent.
 void SampleRecord::print(raw_ostream &OS, unsigned Indent) const {
   OS << NumSamples;
   if (hasCalls()) {
     OS << ", calls:";
     for (const auto &I : getCallTargets())
-      OS << " " << I.first() << ":" << I.second;
+      OS << " " << I.first << ":" << I.second;
   }
   OS << "\n";
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void SampleRecord::dump() const { print(dbgs(), 0); }
 #endif
 

llvm/lib/ProfileData/SampleProfWriter.cpp

for (const auto &I : SortedSamples.get()) {
     if (Loc.Discriminator == 0)
       OS << Loc.LineOffset << ": ";
     else
       OS << Loc.LineOffset << "." << Loc.Discriminator << ": ";
 
     OS << Sample.getSamples();
 
     for (const auto &J : Sample.getCallTargets())
-      OS << " " << J.first() << ":" << J.second;
+      OS << " " << J.first << ":" << J.second;
     OS << "\n";
   }
 
   SampleSorter<LineLocation, FunctionSamplesMap> SortedCallsiteSamples(
       S.getCallsiteSamples());
   Indent += 1;
   for (const auto &I : SortedCallsiteSamples.get())
     for (const auto &FS : I->second) {
void SampleProfileWriterBinary::addName(StringRef FName) {
   NameTable.insert(std::make_pair(FName, 0));
 }
 
 void SampleProfileWriterBinary::addNames(const FunctionSamples &S) {
   // Add all the names in indirect call targets.
   for (const auto &I : S.getBodySamples()) {
     const SampleRecord &Sample = I.second;
     for (const auto &J : Sample.getCallTargets())
-      addName(J.first());
+      addName(J.first);
   }
 
   // Recursively add all the names for inlined callsites.
   for (const auto &J : S.getCallsiteSamples())
     for (const auto &FS : J.second) {
       const FunctionSamples &CalleeSamples = FS.second;
       addName(CalleeSamples.getName());
       addNames(CalleeSamples);
std::error_code SampleProfileWriterBinary::writeBody(const FunctionSamples &S) {
   for (const auto &I : S.getBodySamples()) {
     LineLocation Loc = I.first;
     const SampleRecord &Sample = I.second;
     encodeULEB128(Loc.LineOffset, OS);
     encodeULEB128(Loc.Discriminator, OS);
     encodeULEB128(Sample.getSamples(), OS);
     encodeULEB128(Sample.getCallTargets().size(), OS);
     for (const auto &J : Sample.getCallTargets()) {
-      StringRef Callee = J.first();
+      StringRef Callee = J.first;
       uint64_t CalleeSamples = J.second;
       if (std::error_code EC = writeNameIdx(Callee))
         return EC;
       encodeULEB128(CalleeSamples, OS);
     }
   }
 
   // Recursively emit all the callsite samples.

llvm/lib/Target/X86/X86InsertPrefetch.cpp

bool X86InsertPrefetch::findPrefetchInfo(const FunctionSamples *TopSamples,
 
   const ErrorOr<PrefetchHints> T = getPrefetchHints(TopSamples, MI);
   if (!T)
     return false;
   int16_t max_index = -1;
   // Convert serialized prefetch hints into PrefetchInfo objects, and populate
   // the Prefetches vector.
   for (const auto &S_V : *T) {
-    StringRef Name = S_V.getKey();
+    StringRef Name = S_V.first;
     if (Name.consume_front(SerializedPrefetchPrefix)) {
       int64_t D = static_cast<int64_t>(S_V.second);
       unsigned IID = 0;
       for (const auto &HintType : HintTypes) {
         if (Name.startswith(HintType.first)) {
           Name = Name.drop_front(HintType.first.size());
           IID = HintType.second;
           break;

llvm/lib/Transforms/IPO/SampleProfile.cpp

void SampleProfileLoader::buildEdges(Function &F) {
   }
 }
 
 /// Returns the sorted CallTargetMap \p M by count in descending order.
 static SmallVector<InstrProfValueData, 2> SortCallTargets(
     const SampleRecord::CallTargetMap &M) {
   SmallVector<InstrProfValueData, 2> R;
   for (auto I = M.begin(); I != M.end(); ++I)
-    R.push_back({FunctionSamples::getGUID(I->getKey()), I->getValue()});
+    R.push_back({FunctionSamples::getGUID(I->first), I->second});
   llvm::sort(R, [](const InstrProfValueData &L, const InstrProfValueData &R) {
     if (L.Count == R.Count)
       return L.Value > R.Value;
     else
       return L.Count > R.Count;
   });
   return R;
 }
 
 /// Propagate weights into edges
 ///
 /// The following rules are applied to every block BB in the CFG:
 ///
 /// - If BB has a single predecessor/successor, then the weight
 ///   of that edge is the weight of the block.

llvm/test/tools/llvm-profdata/Inputs/sample-profile.proftext

-_Z3bari:20301:1437
- 1: 1437
-_Z3fooi:7711:610
- 1: 610
 main:184019:0
  4: 534
  4.2: 534
  5: 1075
  5.1: 1075
  6: 2080
  7: 534
  9: 2064 _Z3bari:1471 _Z3fooi:631
  10: inline1:1000
   1: 1000
  10: inline2:2000
   1: 2000
+_Z3bari:20301:1437
+ 1: 1437
+_Z3fooi:7711:610
+ 1: 610

llvm/test/tools/llvm-profdata/roundtrip.test

 RUN: llvm-profdata merge -o %t.0.profdata %S/Inputs/IR_profile.proftext
 RUN: llvm-profdata show -o %t.0.proftext -all-functions -text %t.0.profdata 
 RUN: diff %t.0.proftext %S/Inputs/IR_profile.proftext
 RUN: llvm-profdata merge -o %t.1.profdata %t.0.proftext
 RUN: llvm-profdata show -o %t.1.proftext -all-functions -text %t.1.profdata 
 RUN: diff %t.1.proftext %S/Inputs/IR_profile.proftext
+RUN: llvm-profdata merge --sample --binary -output=%t.2.profdata %S/Inputs/sample-profile.proftext
+RUN: llvm-profdata merge --sample --text -output=%t.2.proftext %t.2.profdata
+RUN: diff %t.2.proftext %S/Inputs/sample-profile.proftext
 No newline at end of file

llvm/test/tools/llvm-profdata/sample-profile-basic.test

 Basic tests for sample profiles.
 
 1- Show all functions
 RUN: llvm-profdata show --sample %p/Inputs/sample-profile.proftext | FileCheck %s --check-prefix=SHOW1
 SHOW1-DAG: Function: main: 184019, 0, 7 sampled lines
-SHOW1-DAG: 9: 2064, calls: _Z3fooi:631 _Z3bari:1471
+SHOW1-DAG: 9: 2064, calls: _Z3bari:1471 _Z3fooi:631
 SHOW1-DAG: Function: _Z3fooi: 7711, 610, 1 sampled lines
 SHOW1-DAG: Function: _Z3bari: 20301, 1437, 1 sampled lines
 SHOW1-DAG: 1: 1437
 
 2- Show only bar
 RUN: llvm-profdata show --sample --function=_Z3bari %p/Inputs/sample-profile.proftext | FileCheck %s --check-prefix=SHOW2
 SHOW2: Function: _Z3bari: 20301, 1437, 1 sampled lines
 SHOW2: 1: 1437
 SHOW2-NOT: Function: main: 184019, 0, 7 sampled lines
 SHOW2-NOT: Function: _Z3fooi: 7711, 610, 1 sampled lines
 
 3- Convert the profile to binary encoding and check that they are both
    identical.
 RUN: llvm-profdata merge --sample %p/Inputs/sample-profile.proftext --binary -o - | llvm-profdata show --sample - -o %t-binary
 RUN: llvm-profdata show --sample %p/Inputs/sample-profile.proftext -o %t-text
 RUN: diff %t-binary %t-text
 
 4- Merge the binary and text encodings of the profile and check that the
    counters have doubled.
 RUN: llvm-profdata merge --sample %p/Inputs/sample-profile.proftext -o %t-binprof
 RUN: llvm-profdata merge --sample --text %p/Inputs/sample-profile.proftext %t-binprof -o - | FileCheck %s --check-prefix=MERGE1
 MERGE1: main:368038:0
-MERGE1: 9: 4128 _Z3fooi:1262 _Z3bari:2942
+MERGE1: 9: 4128 _Z3bari:2942 _Z3fooi:1262
 MERGE1: _Z3bari:40602:2874
 MERGE1: _Z3fooi:15422:1220
 
 5- Detect invalid text encoding (e.g. instrumentation profile text format).
 RUN: not llvm-profdata show --sample %p/Inputs/foo3bar3-1.proftext 2>&1 | FileCheck %s --check-prefix=BADTEXT
 BADTEXT: error: {{.+}}: Unrecognized sample profile encoding format

llvm/tools/llvm-profdata/llvm-profdata.cpp

remapSamples(const sampleprof::FunctionSamples &Samples,
   Result.addHeadSamples(Samples.getHeadSamples());
   for (const auto &BodySample : Samples.getBodySamples()) {
     Result.addBodySamples(BodySample.first.LineOffset,
                           BodySample.first.Discriminator,
                           BodySample.second.getSamples());
     for (const auto &Target : BodySample.second.getCallTargets()) {
       Result.addCalledTargetSamples(BodySample.first.LineOffset,
                                     BodySample.first.Discriminator,
-                                    Remapper(Target.first()), Target.second);
+                                    Remapper(Target.first), Target.second);
     }
   }
   for (const auto &CallsiteSamples : Samples.getCallsiteSamples()) {
     sampleprof::FunctionSamplesMap &Target =
         Result.functionSamplesAt(CallsiteSamples.first);
     for (const auto &Callsite : CallsiteSamples.second) {
       sampleprof::FunctionSamples Remapped =
           remapSamples(Callsite.second, Remapper, Error);