[BOLT] Fix sorting functions by execution count

[spupyrev]

Summary

I noticed that -reorder-functions=exec-count doesn't work as expected due to
a bug in the comparison function (which isn't symmetric). It is questionable
whether anyone would want to ever use the sorting method (as sorting by say
density is much better in all cases) but it is probably better to fix the bug.

[rafauler]

Can we have a small test case showing the bug?

[spupyrev]

Added a test. Without the change, the output is

...
BOLT-INFO: Starting pass: reorder-functions
BOLT-INFO: hot func main (400)
BOLT-INFO: hot func func1 (500)
BOLT-INFO: hot func func2 (1500)
BOLT-INFO: hot func func3 (100)
BOLT-INFO: hot func func4 (99)
BOLT-INFO: hot func func5 (110)
...

[spupyrev]

rebase & adjust logging

bolt/lib/Passes/ReorderFunctions.cpp

void ReorderFunctions::runOnFunctions(BinaryContext &BC) {
 
   std::vector<Cluster> Clusters;
 
   switch (opts::ReorderFunctions) {
   case RT_NONE:
     break;
   case RT_EXEC_COUNT: {
     std::vector<BinaryFunction *> SortedFunctions(BFs.size());
-    uint32_t Index = 0;
     llvm::transform(llvm::make_second_range(BFs), SortedFunctions.begin(),
                     [](BinaryFunction &BF) { return &BF; });
-    llvm::stable_sort(SortedFunctions, [&](const BinaryFunction *A,
-                                           const BinaryFunction *B) {
+    llvm::stable_sort(SortedFunctions,
+                      [&](const BinaryFunction *A, const BinaryFunction *B) {
                         if (A->isIgnored())
                           return false;
+                        if (B->isIgnored())
+                          return true;
                         const size_t PadA = opts::padFunction(*A);
                         const size_t PadB = opts::padFunction(*B);
                         if (!PadA || !PadB) {
                           if (PadA)
                             return true;
                           if (PadB)
                             return false;
                         }
-      return !A->hasProfile() && (B->hasProfile() || (A->getExecutionCount() >
-                                                      B->getExecutionCount()));
+                        if (!A->hasProfile())
+                          return false;
+                        if (!B->hasProfile())
+                          return true;
+                        return A->getExecutionCount() > B->getExecutionCount();
                       });
+    uint32_t Index = 0;
     for (BinaryFunction *BF : SortedFunctions)
-      if (BF->hasProfile())
+      if (BF->hasProfile()) {
         BF->setIndex(Index++);
+        LLVM_DEBUG(if (opts::Verbosity > 1) {
+          dbgs() << "BOLT-INFO: hot func " << BF->getPrintName() << " ("
+                 << BF->getExecutionCount() << ")\n";
+        });
+      }
   } break;
   case RT_HFSORT:
     Clusters = clusterize(Cg);
     break;
   case RT_HFSORT_PLUS:
     Clusters = hfsortPlus(Cg);
     break;
   case RT_CDS: {

bolt/test/X86/bug-function-layout-execount.s

+# Verifies that llvm-bolt correctly sorts functions by their execution counts.
+
+# RUN: llvm-mc -filetype=obj -triple x86_64-unknown-unknown %s -o %t.o
+# RUN: link_fdata %s %t.o %t.fdata
+# RUN: %clang %cflags %t.o -o %t.exe -Wl,-q
+# RUN: llvm-bolt %t.exe --data %t.fdata --lite --reorder-functions=exec-count \
+# RUN:   -v=2 --debug-only=hfsort -o /dev/null 2>&1 | FileCheck %s
+
+# CHECK: Starting pass: reorder-functions
+# CHECK-NEXT: hot func func2 (1500)
+# CHECK-NEXT: hot func func1 (500)
+# CHECK-NEXT: hot func main (400)
+# CHECK-NEXT: hot func func5 (110)
+# CHECK-NEXT: hot func func3 (100)
+# CHECK-NEXT: hot func func4 (99)
+
+  .text
+  .globl main
+  .type main, %function
+main:
+# FDATA: 0 [unknown] 0 1 main 0 1 400
+  .cfi_startproc
+  call func1
+  retq
+  .size _start, .-_start
+  .cfi_endproc
+
+  .globl  func1
+  .type func1,@function
+func1:
+# FDATA: 0 [unknown] 0 1 func1 0 1 500
+  .cfi_startproc
+  retq
+  .size func1, .-func1
+  .cfi_endproc
+
+  .globl  func2
+  .type func2,@function
+func2:
+# FDATA: 0 [unknown] 0 1 func2 0 1 1500
+  .cfi_startproc
+  retq
+  .size func2, .-func2
+  .cfi_endproc
+
+  .globl  func3
+  .type func3,@function
+func3:
+# FDATA: 0 [unknown] 0 1 func3 0 1 100
+  .cfi_startproc
+  retq
+  .size func3, .-func3
+  .cfi_endproc
+
+  .globl  func4
+  .type func4,@function
+func4:
+# FDATA: 0 [unknown] 0 1 func4 0 1 99
+  .cfi_startproc
+  retq
+  .size func4, .-func4
+  .cfi_endproc
+
+  .globl  func5
+  .type func5,@function
+func5:
+# FDATA: 0 [unknown] 0 1 func5 0 1 110
+  .cfi_startproc
+  retq
+  .size func5, .-func5
+  .cfi_endproc