[BOLT] Introduce SplitStrategy ABC

[FPar]

Summary

This introduces an abstract base class for splitting strategies to
document the interface a strategy needs to implement, and also to avoid
code bloat of the splitFunction method.

[FPar]

Move earlier in stack

[FPar]

Rebase

[maksfb]

Looks good to me. Please fix grammar in "Summary" before committing.

[FPar]

Thanks for pointing that out. That was a rough one.

bolt/include/bolt/Passes/SplitFunctions.h

enum SplitFunctionsStrategy : char {
   /// 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
 };
 
+class SplitStrategy {
+public:
+  using BlockIt = BinaryFunction::BasicBlockOrderType::iterator;
+
+  virtual ~SplitStrategy() = default;
+  virtual bool canSplit(const BinaryFunction &BF) = 0;
+  virtual bool canOutline(const BinaryBasicBlock &BB) { return true; }
+  virtual void fragment(const BlockIt Start, const BlockIt End) = 0;
+};
+
 /// Split function code in multiple parts.
 class SplitFunctions : public BinaryFunctionPass {
 private:
   /// Split function body into fragments.
-  template <typename Strategy>
-  void splitFunction(BinaryFunction &Function, Strategy S = {});
+  void splitFunction(BinaryFunction &Function, SplitStrategy &Strategy);
 
   struct TrampolineKey {
     FragmentNum SourceFN = FragmentNum::main();
     const MCSymbol *Target = nullptr;
 
     TrampolineKey() = default;
     TrampolineKey(const FragmentNum SourceFN, const MCSymbol *const Target)
         : SourceFN(SourceFN), Target(Target) {}

bolt/lib/Passes/SplitFunctions.cpp

 #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 <memory>
 #include <numeric>
 #include <random>
 #include <vector>
 
 #define DEBUG_TYPE "bolt-opts"
 
 using namespace llvm;
 using namespace bolt;
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 SplitProfile2 {
-  bool canSplit(const BinaryFunction &BF) {
-    if (!BF.hasValidProfile())
-      return false;
+bool hasFullProfile(const BinaryFunction &BF) {
+  return llvm::all_of(BF.blocks(), [](const BinaryBasicBlock &BB) {
+    return BB.getExecutionCount() != BinaryBasicBlock::COUNT_NO_PROFILE;
+  });
+}
 
-    bool AllCold = true;
-    for (const BinaryBasicBlock &BB : BF) {
-      const uint64_t ExecCount = BB.getExecutionCount();
-      if (ExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)
-        return false;
-      if (ExecCount != 0)
-        AllCold = false;
-    }
+bool allBlocksCold(const BinaryFunction &BF) {
+  return llvm::all_of(BF.blocks(), [](const BinaryBasicBlock &BB) {
+    return BB.getExecutionCount() == 0;
+  });
 
-    return !AllCold;
+struct SplitProfile2 final : public SplitStrategy {
+  bool canSplit(const BinaryFunction &BF) override {
+    return BF.hasValidProfile() && hasFullProfile(BF) && !allBlocksCold(BF);
   }
 
-  bool canOutline(const BinaryBasicBlock &BB) {
+  bool canOutline(const BinaryBasicBlock &BB) override {
     return BB.getExecutionCount() == 0;
   }
 
-  template <typename It> void partition(const It Start, const It End) const {
+  void fragment(const BlockIt Start, const BlockIt End) override {
     for (BinaryBasicBlock *const BB : llvm::make_range(Start, End)) {
       assert(BB->canOutline() &&
              "Moving a block that is not outlineable to cold fragment");
       BB->setFragmentNum(FragmentNum::cold());
     }
   }
 };
 
-struct SplitRandom2 {
-  std::minstd_rand0 *Gen;
+struct SplitRandom2 final : public SplitStrategy {
+  std::minstd_rand0 Gen;
 
-  explicit SplitRandom2(std::minstd_rand0 &Gen) : Gen(&Gen) {}
+  SplitRandom2() : Gen(opts::RandomSeed.getValue()) {}
 
-  bool canSplit(const BinaryFunction &BF) { return true; }
-  bool canOutline(const BinaryBasicBlock &BB) { return true; }
+  bool canSplit(const BinaryFunction &BF) override { return true; }
 
-  template <typename It> void partition(It Start, It End) const {
-    using DiffT = typename std::iterator_traits<It>::difference_type;
+  void fragment(const BlockIt Start, const BlockIt End) override {
+    using DiffT = typename std::iterator_traits<BlockIt>::difference_type;
     const DiffT NumOutlineableBlocks = End - Start;
 
     // 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);
+    const DiffT NumColdBlocks = Dist(Gen);
     for (BinaryBasicBlock *BB : llvm::make_range(End - NumColdBlocks, End))
       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;
+struct SplitRandomN final : public SplitStrategy {
+  std::minstd_rand0 Gen;
 
-  explicit SplitRandomN(std::minstd_rand0 &Gen) : Gen(&Gen) {}
+  SplitRandomN() : Gen(opts::RandomSeed.getValue()) {}
 
-  bool canSplit(const BinaryFunction &BF) { return true; }
-  bool canOutline(const BinaryBasicBlock &BB) { return true; }
+  bool canSplit(const BinaryFunction &BF) override { return true; }
 
-  template <typename It> void partition(It Start, It End) const {
-    using DiffT = typename std::iterator_traits<It>::difference_type;
+  void fragment(const BlockIt Start, const BlockIt End) override {
+    using DiffT = typename std::iterator_traits<BlockIt>::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);
+    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);
+    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; }
+struct SplitAll final : public SplitStrategy {
+  bool canSplit(const BinaryFunction &BF) override { return true; }
 
-  template <typename It> void partition(It Start, It End) const {
+  void fragment(const BlockIt Start, const BlockIt End) override {
     unsigned Fragment = 1;
     for (BinaryBasicBlock *const BB : llvm::make_range(Start, End)) {
       assert(BB->canOutline() &&
              "Moving a block that is not outlineable to cold fragment");
       BB->setFragmentNum(FragmentNum(Fragment++));
     }
   }
 };
bool SplitFunctions::shouldOptimize(const BinaryFunction &BF) const {
 
   return BinaryFunctionPass::shouldOptimize(BF);
 }
 
 void SplitFunctions::runOnFunctions(BinaryContext &BC) {
   if (!opts::SplitFunctions)
     return;
 
-  std::minstd_rand0 RandGen(opts::RandomSeed.getValue());
-
-  ParallelUtilities::WorkFuncTy WorkFun;
+  std::unique_ptr<SplitStrategy> Strategy;
   bool ForceSequential = false;
 
   switch (opts::SplitStrategy) {
   case SplitFunctionsStrategy::Profile2:
-    WorkFun = [&](BinaryFunction &BF) { splitFunction<SplitProfile2>(BF); };
+    Strategy = std::make_unique<SplitProfile2>();
     break;
   case SplitFunctionsStrategy::Random2:
-    WorkFun = [&](BinaryFunction &BF) {
-      splitFunction(BF, SplitRandom2(RandGen));
-    };
+    Strategy = std::make_unique<SplitRandom2>();
     // 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));
-    };
+    Strategy = std::make_unique<SplitRandomN>();
     ForceSequential = true;
     break;
   case SplitFunctionsStrategy::All:
-    WorkFun = [&](BinaryFunction &BF) { splitFunction<SplitAll>(BF); };
+    Strategy = std::make_unique<SplitAll>();
     break;
   }
 
   ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {
     return !shouldOptimize(BF);
   };
 
   ParallelUtilities::runOnEachFunction(
-      BC, ParallelUtilities::SchedulingPolicy::SP_BB_LINEAR, WorkFun, SkipFunc,
+      BC, ParallelUtilities::SchedulingPolicy::SP_BB_LINEAR,
+      [&](BinaryFunction &BF) { splitFunction(BF, *Strategy); }, SkipFunc,
       "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));
 }
 
-template <typename Strategy>
-void SplitFunctions::splitFunction(BinaryFunction &BF, Strategy S) {
+void SplitFunctions::splitFunction(BinaryFunction &BF, SplitStrategy &S) {
   if (BF.empty())
     return;
 
   if (!S.canSplit(BF))
     return;
 
   FunctionLayout &Layout = BF.getLayout();
   BinaryFunction::BasicBlockOrderType PreSplitLayout(Layout.block_begin(),
void SplitFunctions::splitFunction(BinaryFunction &BF, SplitStrategy &S) {
   // after this block can be split. Note that when the iterator points to the
   // block that cannot be outlined, then reverse_iterator::base() points to the
   // block after it.
   const BinaryFunction::BasicBlockOrderType::reverse_iterator FirstOutlineable =
       llvm::find_if(reverse(NewLayout), [](const BinaryBasicBlock *const BB) {
         return !BB->canOutline();
       });
 
-  S.partition(FirstOutlineable.base(), NewLayout.end());
+  S.fragment(FirstOutlineable.base(), NewLayout.end());
   BF.getLayout().update(NewLayout);
 
   // For shared objects, invoke instructions and corresponding landing pads
   // have to be placed in the same fragment. When we split them, create
   // trampoline landing pads that will redirect the execution to real LPs.
   TrampolineSetType Trampolines;
   if (!BC.HasFixedLoadAddress && BF.hasEHRanges() && BF.isSplit())
     Trampolines = createEHTrampolines(BF);