[BOLT] Add randomN split strategy

[FPar]

Summary

This adds a strategy to split functions into a random number of
fragments at randomly chosen split points.

[FPar]

Rebase

[FPar]

Rebase

[FPar]

Use fragments in loop inversion pass

[FPar]

Rebase

[ayermolo]

Now that we have multiple of these Spilt* structs, does it make sense to have a base abstract class that enforces interface?

[FPar]

In D130647#3727316, @ayermolo wrote:

Now that we have multiple of these Spilt* structs, does it make sense to have a base abstract class that enforces interface?

Yes. I do have that in a local commit already. Do you think I should insert that in front of D129827?

[ayermolo]

In D130647#3727323, @FPar wrote:

In D130647#3727316, @ayermolo wrote:

Now that we have multiple of these Spilt* structs, does it make sense to have a base abstract class that enforces interface?

Yes. I do have that in a local commit already. Do you think I should insert that in front of D129827?

I don't have a strong opinion one way or the other.

[FPar]

Rebase

[FPar]

In D130647#3727346, @ayermolo wrote:

In D130647#3727323, @FPar wrote:

In D130647#3727316, @ayermolo wrote:

Now that we have multiple of these Spilt* structs, does it make sense to have a base abstract class that enforces interface?

Yes. I do have that in a local commit already. Do you think I should insert that in front of D129827?

I don't have a strong opinion one way or the other.

See D132054.

[rafauler]

LGTM

bolt/include/bolt/Passes/SplitFunctions.h

 /// Strategy used to partition blocks into fragments.
 enum SplitFunctionsStrategy : char {
   /// Split each function into a hot and cold fragment using profiling
   /// information.
   Profile2 = 0,
   /// Split each function into a hot and cold fragment at a randomly chosen
   /// split point (ignoring any available profiling information).
   Random2,
+  /// Split each function into N fragments at a randomly chosen split points
+  /// (ignoring any available profiling information).
+  RandomN,
   /// Split all basic blocks of each function into fragments such that each
   /// fragment contains exactly a single basic block.
   All
 };
 
 /// Split function code in multiple parts.
 class SplitFunctions : public BinaryFunctionPass {
 private:

bolt/lib/Passes/SplitFunctions.cpp

 //===- bolt/Passes/SplitFunctions.cpp - Pass for splitting function code --===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the SplitFunctions pass.
 //
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Passes/SplitFunctions.h"
+#include "bolt/Core/BinaryBasicBlock.h"
 #include "bolt/Core/BinaryFunction.h"
 #include "bolt/Core/FunctionLayout.h"
 #include "bolt/Core/ParallelUtilities.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/Sequence.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FormatVariadic.h"
 #include <algorithm>
 #include <iterator>
+#include <numeric>
 #include <random>
 #include <vector>
 
 #define DEBUG_TYPE "bolt-opts"
 
 using namespace llvm;
 using namespace bolt;
 
static cl::opt<SplitFunctionsStrategy> SplitStrategy(
     cl::values(clEnumValN(SplitFunctionsStrategy::Profile2, "profile2",
                           "split each function into a hot and cold fragment "
                           "using profiling information")),
     cl::values(clEnumValN(
         SplitFunctionsStrategy::Random2, "random2",
         "split each function into a hot and cold fragment at a randomly chosen "
         "split point (ignoring any available profiling information)")),
     cl::values(clEnumValN(
+        SplitFunctionsStrategy::RandomN, "randomN",
+        "split each function into N fragments at a randomly chosen split "
+        "points (ignoring any available profiling information)")),
+    cl::values(clEnumValN(
         SplitFunctionsStrategy::All, "all",
         "split all basic blocks of each function into fragments such that each "
         "fragment contains exactly a single basic block")),
     cl::desc("strategy used to partition blocks into fragments"),
     cl::cat(BoltOptCategory));
 } // namespace opts
 
 namespace {
struct SplitRandom2 {
 
   bool canSplit(const BinaryFunction &BF) { return true; }
   bool canOutline(const BinaryBasicBlock &BB) { return true; }
 
   template <typename It> void partition(It Start, It End) const {
     using DiffT = typename std::iterator_traits<It>::difference_type;
     const DiffT NumOutlineableBlocks = End - Start;
 
-    // We want to split at least one block unless there are not blocks that can
+    // We want to split at least one block unless there are no blocks that can
     // be outlined
     const auto MinimumSplit = std::min<DiffT>(NumOutlineableBlocks, 1);
     std::uniform_int_distribution<DiffT> Dist(MinimumSplit,
                                               NumOutlineableBlocks);
     const DiffT NumColdBlocks = Dist(*Gen);
     std::for_each(End - NumColdBlocks, End, [](BinaryBasicBlock *BB) {
       BB->setFragmentNum(FragmentNum::cold());
     });
 
     LLVM_DEBUG(dbgs() << formatv("BOLT-DEBUG: randomly chose last {0} (out of "
                                  "{1} possible) blocks to split\n",
                                  NumColdBlocks, End - Start));
   }
 };
 
+struct SplitRandomN {
+  std::minstd_rand0 *Gen;
+
+  explicit SplitRandomN(std::minstd_rand0 &Gen) : Gen(&Gen) {}
+
+  bool canSplit(const BinaryFunction &BF) { return true; }
+  bool canOutline(const BinaryBasicBlock &BB) { return true; }
+
+  template <typename It> void partition(It Start, It End) const {
+    using DiffT = typename std::iterator_traits<It>::difference_type;
+    const DiffT NumOutlineableBlocks = End - Start;
+
+    // We want to split at least one fragment if possible
+    const auto MinimumSplits = std::min<DiffT>(NumOutlineableBlocks, 1);
+    std::uniform_int_distribution<DiffT> Dist(MinimumSplits,
+                                              NumOutlineableBlocks);
+    // Choose how many splits to perform
+    const DiffT NumSplits = Dist(*Gen);
+
+    // Draw split points from a lottery
+    SmallVector<unsigned, 0> Lottery(NumOutlineableBlocks);
+    std::iota(Lottery.begin(), Lottery.end(), 0u);
+    std::shuffle(Lottery.begin(), Lottery.end(), *Gen);
+    Lottery.resize(NumSplits);
+    llvm::sort(Lottery);
+
+    // Add one past the end entry to lottery
+    Lottery.push_back(NumOutlineableBlocks);
+
+    unsigned LotteryIndex = 0;
+    unsigned BBPos = 0;
+    for (BinaryBasicBlock *const BB : make_range(Start, End)) {
+      // Check whether to start new fragment
+      if (BBPos >= Lottery[LotteryIndex])
+        ++LotteryIndex;
+
+      // Because LotteryIndex is 0 based and cold fragments are 1 based, we can
+      // use the index to assign fragments.
+      BB->setFragmentNum(FragmentNum(LotteryIndex));
+
+      ++BBPos;
+    }
+  }
+};
+
 struct SplitAll {
   bool canSplit(const BinaryFunction &BF) { return true; }
   bool canOutline(const BinaryBasicBlock &BB) { return true; }
 
   template <typename It> void partition(It Start, It End) const {
     unsigned Fragment = 1;
     std::for_each(Start, End, [&](BinaryBasicBlock *const BB) {
       assert(BB->canOutline() &&
case SplitFunctionsStrategy::Random2:
     WorkFun = [&](BinaryFunction &BF) {
       splitFunction(BF, SplitRandom2(RandGen));
     };
     // 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.
     ForceSequential = true;
     break;
+  case SplitFunctionsStrategy::RandomN:
+    WorkFun = [&](BinaryFunction &BF) {
+      splitFunction(BF, SplitRandomN(RandGen));
+    };
+    ForceSequential = true;
+    break;
   case SplitFunctionsStrategy::All:
     WorkFun = [&](BinaryFunction &BF) { splitFunction<SplitAll>(BF); };
     break;
   }
 
   ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {
     return !shouldOptimize(BF);
   };

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 -Wl,-q
-# RUN: llvm-bolt %t.exe -o %t.out --split-functions --split-strategy=random2 \
-# RUN:     --print-finalized --print-only=two_block --bolt-seed=7 2>&1 | \
+# RUN: llvm-bolt %t.exe -o %t.random2 --split-functions \
+# RUN:         --split-strategy=random2 --print-finalized \
+# RUN:         --print-only=two_block --bolt-seed=7 2>&1 | \
+# RUN:     FileCheck %s
+# RUN: llvm-bolt %t.exe -o %t.randomN --split-functions \
+# RUN:         --split-strategy=randomN --print-finalized \
+# RUN:         --print-only=two_block --bolt-seed=7 2>&1 | \
 # RUN:     FileCheck %s
 
 # CHECK: Binary Function "two_block"
 # CHECK:   IsSplit     :
 # CHECK-SAME: {{ 1$}}
 
         .text
         .globl  single_block