diff --git a/bolt/lib/Passes/ReorderFunctions.cpp b/bolt/lib/Passes/ReorderFunctions.cpp
--- a/bolt/lib/Passes/ReorderFunctions.cpp
+++ b/bolt/lib/Passes/ReorderFunctions.cpp
@@ -284,27 +284,37 @@
     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) {
-      if (A->isIgnored())
-        return false;
-      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()));
-    });
+    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;
+                        }
+                        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);
diff --git a/bolt/test/X86/bug-function-layout-execount.s b/bolt/test/X86/bug-function-layout-execount.s
new file mode 100644
--- /dev/null
+++ b/bolt/test/X86/bug-function-layout-execount.s
@@ -0,0 +1,71 @@
+# 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