SamplePGO - Sort samples by source location when emitting as text.

When dumping function samples or writing them out as text format, it
helps if the samples are emitted sorted by source location. The sorting
of the maps is a bit slow, so we only do it on demand.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@253568 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/ProfileData/SampleProf.h b/include/llvm/ProfileData/SampleProf.h
index a8960cf7bc12032295c11da4a9574afde0f0f188..a7b22c73548087fe15996d2fe2323553cd4dd992 100644 (file)
--- a/include/llvm/ProfileData/SampleProf.h
+++ b/include/llvm/ProfileData/SampleProf.h
@@ -77,6 +77,10 @@ struct LineLocation {
   LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {}
   void print(raw_ostream &OS) const;
   void dump() const;
+  bool operator<(const LineLocation &O) const {
+    return LineOffset < O.LineOffset ||
+           (LineOffset == O.LineOffset && Discriminator < O.Discriminator);
+  }
 
   uint32_t LineOffset;
   uint32_t Discriminator;
@@ -335,6 +339,29 @@ private:
 
 raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS);
 
+/// Sort a LocationT->SampleT map by LocationT.
+///
+/// It produces a sorted list of <LocationT, SampleT> records by ascending
+/// order of LocationT.
+template <class LocationT, class SampleT> class SampleSorter {
+public:
+  typedef detail::DenseMapPair<LocationT, SampleT> SamplesWithLoc;
+  typedef SmallVector<const SamplesWithLoc *, 20> SamplesWithLocList;
+
+  SampleSorter(const DenseMap<LocationT, SampleT> &Samples) {
+    for (const auto &I : Samples)
+      V.push_back(&I);
+    std::stable_sort(V.begin(), V.end(),
+                     [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
+                       return A->first < B->first;
+                     });
+  }
+  const SamplesWithLocList &get() const { return V; }
+
+private:
+  SamplesWithLocList V;
+};
+
 } // end namespace sampleprof
 
 } // end namespace llvm

diff --git a/lib/ProfileData/SampleProf.cpp b/lib/ProfileData/SampleProf.cpp
index 3d75d230fb6f0ee65a7d1e9ccb575f8201d354bf..c376a8bbd98d06ae68ef3a6f47e2299753245045 100644 (file)
--- a/lib/ProfileData/SampleProf.cpp
+++ b/lib/ProfileData/SampleProf.cpp
@@ -108,15 +108,18 @@ void FunctionSamples::print(raw_ostream &OS, unsigned Indent) const {
   OS << TotalSamples << ", " << TotalHeadSamples << ", " << BodySamples.size()
      << " sampled lines\n";
 
-  for (const auto &SI : BodySamples) {
+  SampleSorter<LineLocation, SampleRecord> SortedBodySamples(BodySamples);
+  for (const auto &SI : SortedBodySamples.get()) {
     OS.indent(Indent);
-    OS << SI.first << ": " << SI.second;
+    OS << SI->first << ": " << SI->second;
   }
 
-  for (const auto &CS : CallsiteSamples) {
+  SampleSorter<CallsiteLocation, FunctionSamples> SortedCallsiteSamples(
+      CallsiteSamples);
+  for (const auto &CS : SortedCallsiteSamples.get()) {
     OS.indent(Indent);
-    OS << CS.first << ": ";
-    CS.second.print(OS, Indent + 2);
+    OS << CS->first << ": ";
+    CS->second.print(OS, Indent + 2);
   }
 }
 

diff --git a/lib/ProfileData/SampleProfWriter.cpp b/lib/ProfileData/SampleProfWriter.cpp
index b7f6db5eb3354e3bfe54f42dadf08926535410ea..c9f8923346863b8190ad246d82507eabe26d2ad1 100644 (file)
--- a/lib/ProfileData/SampleProfWriter.cpp
+++ b/lib/ProfileData/SampleProfWriter.cpp
@@ -32,7 +32,7 @@ using namespace llvm;
 /// \brief Write samples to a text file.
 ///
 /// Note: it may be tempting to implement this in terms of
-/// FunctionSamples::dump().  Please don't.  The dump functionality is intended
+/// FunctionSamples::print().  Please don't.  The dump functionality is intended
 /// for debugging and has no specified form.
 ///
 /// The format used here is more structured and deliberate because
@@ -44,9 +44,10 @@ std::error_code SampleProfileWriterText::write(StringRef FName,
     OS << ":" << S.getHeadSamples();
   OS << "\n";
 
-  for (const auto &I : S.getBodySamples()) {
-    LineLocation Loc = I.first;
-    const SampleRecord &Sample = I.second;
+  SampleSorter<LineLocation, SampleRecord> SortedSamples(S.getBodySamples());
+  for (const auto &I : SortedSamples.get()) {
+    LineLocation Loc = I->first;
+    const SampleRecord &Sample = I->second;
     OS.indent(Indent + 1);
     if (Loc.Discriminator == 0)
       OS << Loc.LineOffset << ": ";
@@ -60,10 +61,12 @@ std::error_code SampleProfileWriterText::write(StringRef FName,
     OS << "\n";
   }
 
+  SampleSorter<CallsiteLocation, FunctionSamples> SortedCallsiteSamples(
+      S.getCallsiteSamples());
   Indent += 1;
-  for (const auto &I : S.getCallsiteSamples()) {
-    CallsiteLocation Loc = I.first;
-    const FunctionSamples &CalleeSamples = I.second;
+  for (const auto &I : SortedCallsiteSamples.get()) {
+    CallsiteLocation Loc = I->first;
+    const FunctionSamples &CalleeSamples = I->second;
     OS.indent(Indent);
     if (Loc.Discriminator == 0)
       OS << Loc.LineOffset << ": ";

diff --git a/test/tools/llvm-profdata/gcc-gcov-sample-profile.test b/test/tools/llvm-profdata/gcc-gcov-sample-profile.test
index 609569a8fe151609a2d0d0a86fd9be96338bbc39..dbcc74e1284f992ffefba2e7d8b90de7da015ddd 100644 (file)
--- a/test/tools/llvm-profdata/gcc-gcov-sample-profile.test
+++ b/test/tools/llvm-profdata/gcc-gcov-sample-profile.test
@@ -11,8 +11,8 @@ RUN: llvm-profdata show --sample %p/Inputs/gcc-sample-profile.gcov | FileCheck %
 SHOW1: Function: main: 364084, 0, 6 sampled lines
 SHOW1: 2.3: inlined callee: _Z3fool: 243786, 0, 3 sampled lines
 SHOW1:   1.3: inlined callee: _Z3bari: 0, 0, 2 sampled lines
-SHOW1:   1.8: inlined callee: _Z3bari: 0, 0, 2 sampled lines
 SHOW1:   1.7: inlined callee: _Z3bari: 98558, 0, 2 sampled lines
+SHOW1:   1.8: inlined callee: _Z3bari: 0, 0, 2 sampled lines
 
 2- Convert the profile to text encoding and check that they are both
    identical.

diff --git a/test/tools/llvm-profdata/inline-samples.test b/test/tools/llvm-profdata/inline-samples.test
index 156dc15aeefe825ffba0ccc026e3092eca576098..421f002da9f98ef0ae5a76b6f30bd8c4c4f5acfa 100644 (file)
--- a/test/tools/llvm-profdata/inline-samples.test
+++ b/test/tools/llvm-profdata/inline-samples.test
@@ -10,9 +10,9 @@ RUN: llvm-profdata show --sample %t.profbin | FileCheck %s --check-prefix=SHOW1
 SHOW1: Function: main: 366846, 0, 6 sampled lines
 SHOW1: 2.3: inlined callee: _Z3fool: 246044, 0, 3 sampled lines
 SHOW1:   1.3: inlined callee: _Z3bari: 0, 0, 2 sampled lines
-SHOW1:   1.8: inlined callee: _Z3bari: 0, 0, 2 sampled lines
 SHOW1:   1.7: inlined callee: _Z3bari: 99492, 0, 2 sampled lines
 SHOW1:     1.2: 46732
+SHOW1:   1.8: inlined callee: _Z3bari: 0, 0, 2 sampled lines
 
 3- Convert the binary profile to text encoding and check that they are both
    identical.