[BOLT] Add option to randomize function split point

[FPar]

Summary

For test purposes, we want to split functions at a random split point
to be able to test different layouts without relying on the profile.
This patch introduces an option, that randomly chooses a split point
to partition blocks of a function into hot and cold regions.

[Amir]

Thank you for working on this!

bolt/lib/Passes/SplitFunctions.cpp

147–150

As a matter of preference - I try to wrap LLVM_DEBUG body with curly braces to indent it just like a regular code block.

bolt/test/X86/split-random.s

6

The test looks good and very clean! There's just one concern with regards to our NFC testing - I think we should specify the seed as an option to ensure identical binaries between runs.

[FPar]

Fix seed for test

[FPar]

Thanks for your suggestions! @Amir

bolt/lib/Passes/SplitFunctions.cpp

147–150

I see your point. However, the majority of our code base seems to omit curly braces in this place. So if you don't mind, I'll keep it like that for now.

[Amir]

LGTM

[yota9]

bolt/lib/Passes/SplitFunctions.cpp

174

It seems that it could be moved under proper WorkFun

[FPar]

bolt/lib/Passes/SplitFunctions.cpp

174

If the generator is moved into the lambda and each function uses its own generator, all functions generate the same split point, depending on the seed. To get an actually random looking distribution of splits across functions, the work-function needs access to a shared random number generator.

[yota9]

Thanks @FPar !

bolt/include/bolt/Passes/SplitFunctions.h

 
 namespace llvm {
 namespace bolt {
 
 /// Split function code in multiple parts.
 class SplitFunctions : public BinaryFunctionPass {
 private:
   /// Split function body into fragments.
-  void splitFunction(BinaryFunction &Function);
+  template <typename SplitStrategy>
+  void splitFunction(BinaryFunction &Function, SplitStrategy Strategy = {});
 
   /// Create trampoline landing pads for exception handling code to guarantee
   /// that every landing pad is placed in the same function fragment as the
   /// corresponding thrower block. The trampoline landing pad, when created,
   /// will redirect the execution to the real landing pad in a different
   /// fragment.
   void createEHTrampolines(BinaryFunction &Function) const;
 

bolt/lib/Passes/SplitFunctions.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Passes/SplitFunctions.h"
 #include "bolt/Core/BinaryFunction.h"
 #include "bolt/Core/ParallelUtilities.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FormatVariadic.h"
-
+#include <algorithm>
+#include <random>
 #include <vector>
 
 #define DEBUG_TYPE "bolt-opts"
 
 using namespace llvm;
 using namespace bolt;
 
 namespace {

 } // namespace
 
 namespace opts {
 
 extern cl::OptionCategory BoltOptCategory;
 
 extern cl::opt<bool> SplitEH;
 extern cl::opt<unsigned> ExecutionCountThreshold;
+extern cl::opt<uint32_t> RandomSeed;
 
 static cl::opt<bool> AggressiveSplitting(
     "split-all-cold", cl::desc("outline as many cold basic blocks as possible"),
     cl::cat(BoltOptCategory));
 
 static cl::opt<unsigned> SplitAlignThreshold(
     "split-align-threshold",
     cl::desc("when deciding to split a function, apply this alignment "

 static cl::opt<unsigned> SplitThreshold(
     "split-threshold",
     cl::desc("split function only if its main size is reduced by more than "
              "given amount of bytes. Default value: 0, i.e. split iff the "
              "size is reduced. Note that on some architectures the size can "
              "increase after splitting."),
     cl::init(0), cl::Hidden, cl::cat(BoltOptCategory));
 
+static cl::opt<bool>
+    RandomSplit("split-random",
+                cl::desc("split functions randomly into hot/cold regions"),
+                cl::Hidden);
 } // namespace opts
 
+namespace {
+struct SplitCold {
+  bool canSplit(const BinaryFunction &BF) {
+    if (!BF.hasValidProfile())
+      return false;
+
+    bool AllCold = true;
+    for (BinaryBasicBlock *BB : BF.layout()) {
+      const uint64_t ExecCount = BB->getExecutionCount();
+      if (ExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)
+        return false;
+      if (ExecCount != 0)
+        AllCold = false;
+    }
+
+    return !AllCold;
+  }
+
+  bool canOutline(const BinaryBasicBlock &BB) {
+    return BB.getExecutionCount() == 0;
+  }
+
+  void partition(BinaryFunction::reverse_order_iterator Start,
+                 BinaryFunction::reverse_order_iterator End) const {
+    for (auto I = Start; I != End; ++I) {
+      BinaryBasicBlock *BB = *I;
+      if (!BB->canOutline())
+        break;
+      BB->setIsCold(true);
+    }
+  }
+};
+
+struct SplitRandom {
+  std::minstd_rand0 *Gen;
+
+  explicit SplitRandom(std::minstd_rand0 &Gen) : Gen(&Gen) {}
+
+  bool canSplit(const BinaryFunction &BF) { return true; }
+  bool canOutline(const BinaryBasicBlock &BB) { return true; }
+
+  void partition(BinaryFunction::reverse_order_iterator Start,
+                 BinaryFunction::reverse_order_iterator End) const {
+    using It = decltype(Start);
+
+    const It OutlineableBegin = Start;
+    const It OutlineableEnd =
+        std::find_if(OutlineableBegin, End,
+                     [](BinaryBasicBlock *BB) { return !BB->canOutline(); });
+    const It::difference_type NumOutlineableBlocks =
+        OutlineableEnd - OutlineableBegin;
+
+    // We want to split at least one block unless there are not blocks that can
+    // be outlined
+    const auto MinimumSplit =
+        std::min<It::difference_type>(NumOutlineableBlocks, 1);
+    std::uniform_int_distribution<It::difference_type> Dist(
+        MinimumSplit, NumOutlineableBlocks);
+    const It::difference_type NumColdBlocks = Dist(*Gen);
+    const It ColdEnd = OutlineableBegin + NumColdBlocks;
+
+    LLVM_DEBUG(dbgs() << formatv("BOLT-DEBUG: randomly chose last {0} (out of "
+                                 "{1} possible) blocks to split\n",
+                                 ColdEnd - OutlineableBegin,
+                                 OutlineableEnd - OutlineableBegin));
+
+    std::for_each(OutlineableBegin, ColdEnd,
+                  [](BinaryBasicBlock *BB) { BB->setIsCold(true); });
+  }
+};
+} // namespace
+
 namespace llvm {
 namespace bolt {
 
 bool SplitFunctions::shouldOptimize(const BinaryFunction &BF) const {
   // Apply execution count threshold
   if (BF.getKnownExecutionCount() < opts::ExecutionCountThreshold)
     return false;
 
   return BinaryFunctionPass::shouldOptimize(BF);
 }
 
 void SplitFunctions::runOnFunctions(BinaryContext &BC) {
   if (!opts::SplitFunctions)
     return;
 
-  ParallelUtilities::WorkFuncTy WorkFun = [&](BinaryFunction &BF) {
-    splitFunction(BF);
+  ParallelUtilities::WorkFuncTy WorkFun;
+  std::minstd_rand0 RandGen(opts::RandomSeed.getValue());
+  if (opts::RandomSplit)
+    WorkFun = [&](BinaryFunction &BF) {
+      splitFunction(BF, SplitRandom(RandGen));
     };
+  else
+    WorkFun = [&](BinaryFunction &BF) { splitFunction<SplitCold>(BF); };
 
   ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {
     return !shouldOptimize(BF);
   };
 
+  // If we split functions randomly, we need to ensure that across runs with the
+  // same input, we generate random numbers for each function in the same order.
+  const bool ForceSequential = opts::RandomSplit;
+
   ParallelUtilities::runOnEachFunction(
       BC, ParallelUtilities::SchedulingPolicy::SP_BB_LINEAR, WorkFun, SkipFunc,
-      "SplitFunctions");
+      "SplitFunctions", ForceSequential);
 
   if (SplitBytesHot + SplitBytesCold > 0)
     outs() << "BOLT-INFO: splitting separates " << SplitBytesHot
            << " hot bytes from " << SplitBytesCold << " cold bytes "
            << format("(%.2lf%% of split functions is hot).\n",
                      100.0 * SplitBytesHot / (SplitBytesHot + SplitBytesCold));
 }
 
-void SplitFunctions::splitFunction(BinaryFunction &BF) {
-  if (!BF.size())
-    return;
-
-  if (!BF.hasValidProfile())
-    return;
-
-  bool AllCold = true;
-  for (BinaryBasicBlock *BB : BF.layout()) {
-    const uint64_t ExecCount = BB->getExecutionCount();
-    if (ExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)
-      return;
-    if (ExecCount != 0)
-      AllCold = false;
-  }
+template <typename SplitStrategy>
+void SplitFunctions::splitFunction(BinaryFunction &BF, SplitStrategy Strategy) {
+  if (BF.empty())
 
-  if (AllCold)
+  if (!Strategy.canSplit(BF))
     return;
 
   BinaryFunction::BasicBlockOrderType PreSplitLayout = BF.getLayout();
 
   BinaryContext &BC = BF.getBinaryContext();
   size_t OriginalHotSize;
   size_t HotSize;
   size_t ColdSize;
   if (BC.isX86()) {
     std::tie(OriginalHotSize, ColdSize) = BC.calculateEmittedSize(BF);
     LLVM_DEBUG(dbgs() << "Estimated size for function " << BF
                       << " pre-split is <0x"
                       << Twine::utohexstr(OriginalHotSize) << ", 0x"
                       << Twine::utohexstr(ColdSize) << ">\n");
   }
 
   // Never outline the first basic block.
   BF.layout_front()->setCanOutline(false);
   for (BinaryBasicBlock *BB : BF.layout()) {
     if (!BB->canOutline())
       continue;
-    if (BB->getExecutionCount() != 0) {
+    if (!Strategy.canOutline(*BB)) {
       BB->setCanOutline(false);
       continue;
     }
     // Do not split extra entry points in aarch64. They can be referred by
     // using ADRs and when this happens, these blocks cannot be placed far
     // away due to the limited range in ADR instruction.
     if (BC.isAArch64() && BB->isEntryPoint()) {
       BB->setCanOutline(false);
if (opts::AggressiveSplitting) {
 
     std::stable_sort(FirstLP, BF.layout_end(),
                      [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {
                        return A->canOutline() < B->canOutline();
                      });
   }
 
   // Separate hot from cold starting from the bottom.
-  for (auto I = BF.layout_rbegin(), E = BF.layout_rend(); I != E; ++I) {
-    BinaryBasicBlock *BB = *I;
-    if (!BB->canOutline())
-      break;
-    BB->setIsCold(true);
-  }
+  Strategy.partition(BF.layout_rbegin(), BF.layout_rend());
 
   // For shared objects, place invoke instructions and corresponding landing
   // pads in the same fragment. To reduce hot code size, create trampoline
   // landing pads that will redirect the execution to the real LP.
   if (!BC.HasFixedLoadAddress && BF.hasEHRanges() && BF.isSplit())
     createEHTrampolines(BF);
 
   // Check the new size to see if it's worth splitting the function.

bolt/test/X86/split-random.s

+# Test random function splitting option
+
+# RUN: llvm-mc --filetype=obj --triple x86_64-unknown-unknown %s -o %t.o
+# RUN: %clang %cflags %t.o -o %t.exe
+# RUN: llvm-bolt %t.exe -o %t.out --split-functions --split-random \
+# RUN:     --print-finalized --print-only=two_block 2>&1 | FileCheck %s
+
+# CHECK: Binary Function "two_block"
+# CHECK:   IsSplit     :
+# CHECK-SAME: {{ 1$}}
+
+        .text
+        .globl  single_block
+        .type   single_block, @function
+single_block:
+        ret
+        .size   single_block, .-single_block
+
+
+        .globl  two_block
+        .type   two_block, @function
+two_block:
+.L3:
+        subl    $1, %edi
+        testl   %edi, %edi
+        jg      .L3
+        jmp     .L4
+.L4:
+        subl    $1, %edi
+        subl    $1, %edi
+        subl    $1, %edi
+        subl    $1, %edi
+        ret
+        .size   two_block, .-two_block
+
+
+        .globl  main
+        .type   main, @function
+main:
+        call    single_block
+        movl    $10, %edi
+        call    two_block
+        ret
+        .size   main, .-main