[BOLT] Fragment all blocks (not just outlineable blocks)

[FPar]

Summary

To enable split strategies that require view of the entire CFG (e.g. to
estimate cost of path from entry block), with this patch, all blocks of
a function are passed to SplitStrategy::fragment. Because this might
move non-outlineable blocks into a split fragment, these blocks are
moved back into the main fragment after fragmenting. This also gives
strategies the option to specify whether empty fragments should be
kept or removed.

[FPar]

Rebase

[maksfb]

LGTM

bolt/include/bolt/Passes/SplitFunctions.h

 };
 
 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 bool keepEmpty() = 0;
   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.
   void splitFunction(BinaryFunction &Function, SplitStrategy &Strategy);

bolt/lib/Passes/SplitFunctions.cpp

bool allBlocksCold(const BinaryFunction &BF) {
   });
 }
 
 struct SplitProfile2 final : public SplitStrategy {
   bool canSplit(const BinaryFunction &BF) override {
     return BF.hasValidProfile() && hasFullProfile(BF) && !allBlocksCold(BF);
   }
 
-  bool canOutline(const BinaryBasicBlock &BB) override {
-    return BB.getExecutionCount() == 0;
-  }
+  bool keepEmpty() override { return false; }
 
   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");
+      if (BB->getExecutionCount() == 0)
         BB->setFragmentNum(FragmentNum::cold());
     }
   }
 };
 
 struct SplitRandom2 final : public SplitStrategy {
   std::minstd_rand0 Gen;
 
   SplitRandom2() : Gen(opts::RandomSeed.getValue()) {}
 
   bool canSplit(const BinaryFunction &BF) override { return true; }
 
+  bool keepEmpty() override { return false; }
+
   void fragment(const BlockIt Start, const BlockIt End) override {
     using DiffT = typename std::iterator_traits<BlockIt>::difference_type;
-    const DiffT NumOutlineableBlocks = End - Start;
+    const DiffT NumBlocks = End - Start;
+    assert(NumBlocks > 0 && "Cannot fragment empty function");
 
-    // 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);
-    for (BinaryBasicBlock *BB : llvm::make_range(End - NumColdBlocks, End))
+    // We want to split at least one block
+    const auto LastSplitPoint = std::max<DiffT>(NumBlocks - 1, 1);
+    std::uniform_int_distribution<DiffT> Dist(1, LastSplitPoint);
+    const DiffT SplitPoint = Dist(Gen);
+    for (BinaryBasicBlock *BB : llvm::make_range(Start + SplitPoint, 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));
+                                 NumBlocks - SplitPoint, End - Start));
   }
 };
 
 struct SplitRandomN final : public SplitStrategy {
   std::minstd_rand0 Gen;
 
   SplitRandomN() : Gen(opts::RandomSeed.getValue()) {}
 
   bool canSplit(const BinaryFunction &BF) override { return true; }
 
+  bool keepEmpty() override { return false; }
+
   void fragment(const BlockIt Start, const BlockIt End) override {
     using DiffT = typename std::iterator_traits<BlockIt>::difference_type;
-    const DiffT NumOutlineableBlocks = End - Start;
+    const DiffT NumBlocks = End - Start;
+    assert(NumBlocks > 0 && "Cannot fragment empty function");
 
-    // 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);
+    // With n blocks, there are n-1 places to split them.
+    const DiffT MaximumSplits = NumBlocks - 1;
+    // We want to generate at least two fragment if possible, but if there is
+    // only one block, no splits are possible.
+    const auto MinimumSplits = std::min<DiffT>(MaximumSplits, 1);
+    std::uniform_int_distribution<DiffT> Dist(MinimumSplits, MaximumSplits);
     // 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);
+    SmallVector<unsigned, 0> Lottery(MaximumSplits);
+    // Start lottery at 1, because there is no meaningful splitpoint before the
+    // first block.
+    std::iota(Lottery.begin(), Lottery.end(), 1u);
     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);
+    Lottery.push_back(NumBlocks);
 
     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 final : public SplitStrategy {
   bool canSplit(const BinaryFunction &BF) override { return true; }
 
+  bool keepEmpty() override { return false; }
+
   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");
+    unsigned Fragment = 0;
+    for (BinaryBasicBlock *const BB : llvm::make_range(Start, End))
       BB->setFragmentNum(FragmentNum(Fragment++));
-    }
-  }
 };
 } // namespace
 
 namespace llvm {
 namespace bolt {
 
 bool SplitFunctions::shouldOptimize(const BinaryFunction &BF) const {
   // Apply execution count threshold
void SplitFunctions::splitFunction(BinaryFunction &BF, SplitStrategy &S) {
 
   BinaryFunction::BasicBlockOrderType NewLayout(Layout.block_begin(),
                                                 Layout.block_end());
   // Never outline the first basic block.
   NewLayout.front()->setCanOutline(false);
   for (BinaryBasicBlock *const BB : NewLayout) {
     if (!BB->canOutline())
       continue;
-    if (!S.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);
       continue;
     }
 
if (BF.hasEHRanges() && !opts::SplitEH) {
         if (BC.MIB->isInvoke(Instr)) {
           BB->setCanOutline(false);
           break;
         }
       }
     }
   }
 
+  BF.getLayout().updateLayoutIndices();
+  S.fragment(NewLayout.begin(), NewLayout.end());
+
+  // Make sure all non-outlineable blocks are in the main-fragment.
+  for (BinaryBasicBlock *const BB : NewLayout) {
+    if (!BB->canOutline())
+      BB->setFragmentNum(FragmentNum::main());
+  }
+
   if (opts::AggressiveSplitting) {
     // All blocks with 0 count that we can move go to the end of the function.
     // Even if they were natural to cluster formation and were seen in-between
     // hot basic blocks.
-    stable_sort(NewLayout, [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {
-      return A->canOutline() < B->canOutline();
+    llvm::stable_sort(NewLayout, [&](const BinaryBasicBlock *const A,
+                                     const BinaryBasicBlock *const B) {
+      return A->getFragmentNum() < B->getFragmentNum();
     });
   } else if (BF.hasEHRanges() && !opts::SplitEH) {
     // Typically functions with exception handling have landing pads at the end.
     // We cannot move beginning of landing pads, but we can move 0-count blocks
     // comprising landing pads to the end and thus facilitate splitting.
     auto FirstLP = NewLayout.begin();
     while ((*FirstLP)->isLandingPad())
       ++FirstLP;
 
     std::stable_sort(FirstLP, NewLayout.end(),
                      [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {
-                       return A->canOutline() < B->canOutline();
+                       return A->getFragmentNum() < B->getFragmentNum();
                      });
   }
 
-  // Identify the last block that must not be split into a fragment. Every block
-  // 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();
-      });
+  // Make sure that fragments are increasing.
+  FragmentNum CurrentFragment = NewLayout.back()->getFragmentNum();
+  for (BinaryBasicBlock *const BB : reverse(NewLayout)) {
+    if (BB->getFragmentNum() > CurrentFragment)
+      BB->setFragmentNum(CurrentFragment);
+    CurrentFragment = BB->getFragmentNum();
+  }
+
+  if (!S.keepEmpty()) {
+    FragmentNum CurrentFragment = FragmentNum::main();
+    FragmentNum NewFragment = FragmentNum::main();
+    for (BinaryBasicBlock *const BB : NewLayout) {
+      if (BB->getFragmentNum() > CurrentFragment) {
+        CurrentFragment = BB->getFragmentNum();
+        NewFragment = FragmentNum(NewFragment.get() + 1);
+      }
+      BB->setFragmentNum(NewFragment);
+    }
+  }
 
-  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);