[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

147–155

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

147–155

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

147–155

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

1299

Nit: emplace may be better.

[wenlei]

address review feedback

[wenlei]

llvm/lib/Transforms/IPO/SampleProfile.cpp

1299

Thanks for review. Now changed to emplace_back.

llvm/include/llvm/ProfileData/SampleProf.h

 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <cstdint>
 #include <map>
+#include <set>
 #include <string>
 #include <system_error>
 #include <utility>
 
 namespace llvm {
 
 class raw_ostream;
 

 ///
 /// 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 CallTarget = std::pair<StringRef, uint64_t>;
+  struct CallTargetComparator {
+    bool operator() (const CallTarget &LHS, const CallTarget &RHS) {
+      if (LHS.second != RHS.second)
+        return LHS.second > RHS.second;
 
+      return LHS.first < RHS.first;
+    }
+  };
+
+  using SortedCallTargetSet = std::set<CallTarget, CallTargetComparator>;
+  using CallTargetMap = StringMap<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.
   sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) {
return Overflowed ? sampleprof_error::counter_overflow
                       : sampleprof_error::success;
   }
 
   /// Return true if this sample record contains function calls.
   bool hasCalls() const { return !CallTargets.empty(); }
 
   uint64_t getSamples() const { return NumSamples; }
   const CallTargetMap &getCallTargets() const { return CallTargets; }
+  const SortedCallTargetSet getSortedCallTargets() const {
+    return SortCallTargets(CallTargets);
+  }
+
+  /// Sort call targets in descending order of call frequency.
+  static const SortedCallTargetSet SortCallTargets(const CallTargetMap &Targets) {
+    SortedCallTargetSet SortedTargets;
+    for (const auto &I : Targets) {
+      SortedTargets.emplace(I.first(), I.second);
+    }
+    return SortedTargets;
+  }
 
   /// 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));
     }

llvm/lib/ProfileData/SampleProf.cpp

 LLVM_DUMP_METHOD void LineLocation::dump() const { print(dbgs()); }
 #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;
+    for (const auto &I : getSortedCallTargets())
+      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()) {
     OS.indent(Indent + 1);
     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;
+    for (const auto &J : Sample.getSortedCallTargets())
+      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) {
std::error_code SampleProfileWriterBinary::writeBody(const FunctionSamples &S) {
   encodeULEB128(S.getBodySamples().size(), OS);
   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();
+    for (const auto &J : Sample.getSortedCallTargets()) {
+      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/Transforms/IPO/SampleProfile.cpp

for (succ_iterator SI = succ_begin(B1), SE = succ_end(B1); SI != SE; ++SI) {
       BasicBlock *B2 = *SI;
       if (Visited.insert(B2).second)
         Successors[B1].push_back(B2);
     }
   }
 }
 
 /// Returns the sorted CallTargetMap \p M by count in descending order.
-static SmallVector<InstrProfValueData, 2> SortCallTargets(
-    const SampleRecord::CallTargetMap &M) {
+static SmallVector<InstrProfValueData, 2> GetSortedValueDataFromCallTargets(
+    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()});
-  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;
-  });
+  for (const auto &I : SampleRecord::SortCallTargets(M)) {
+    R.push_back({FunctionSamples::getGUID(I.first), I.second});
+  }
   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
if (BlockWeights[BB]) {
 
           const FunctionSamples *FS = findFunctionSamples(I);
           if (!FS)
             continue;
           auto T = FS->findCallTargetMapAt(LineOffset, Discriminator);
           if (!T || T.get().empty())
             continue;
           SmallVector<InstrProfValueData, 2> SortedCallTargets =
-              SortCallTargets(T.get());
+              GetSortedValueDataFromCallTargets(T.get());
           uint64_t Sum;
           findIndirectCallFunctionSamples(I, Sum);
           annotateValueSite(*I.getParent()->getParent()->getParent(), I,
                             SortedCallTargets, Sum, IPVK_IndirectCallTarget,
                             SortedCallTargets.size());
         } else if (!isa<IntrinsicInst>(&I)) {
           I.setMetadata(LLVMContext::MD_prof,
                         MDB.createBranchWeights(

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