From ae2b4da16664a684341aa611309cfd302afe5ffa Mon Sep 17 00:00:00 2001 From: Fabian Parzefall Date: Thu, 8 Sep 2022 17:10:11 -0700 Subject: [PATCH] [BOLT] Fragment all blocks (not just outlineable blocks) 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. Reviewed By: maksfb Differential Revision: https://reviews.llvm.org/D132423 --- bolt/include/bolt/Passes/SplitFunctions.h | 2 +- bolt/lib/Passes/SplitFunctions.cpp | 113 ++++++++++++++++++------------ 2 files changed, 68 insertions(+), 47 deletions(-) diff --git a/bolt/include/bolt/Passes/SplitFunctions.h b/bolt/include/bolt/Passes/SplitFunctions.h index 98657dc..4058f33 100644 --- a/bolt/include/bolt/Passes/SplitFunctions.h +++ b/bolt/include/bolt/Passes/SplitFunctions.h @@ -40,7 +40,7 @@ public: 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; }; diff --git a/bolt/lib/Passes/SplitFunctions.cpp b/bolt/lib/Passes/SplitFunctions.cpp index 789e060..e98681e 100644 --- a/bolt/lib/Passes/SplitFunctions.cpp +++ b/bolt/lib/Passes/SplitFunctions.cpp @@ -125,15 +125,12 @@ struct SplitProfile2 final : public SplitStrategy { 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"); - BB->setFragmentNum(FragmentNum::cold()); + if (BB->getExecutionCount() == 0) + BB->setFragmentNum(FragmentNum::cold()); } } }; @@ -145,22 +142,23 @@ struct SplitRandom2 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 { using DiffT = typename std::iterator_traits::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(NumOutlineableBlocks, 1); - std::uniform_int_distribution Dist(MinimumSplit, - NumOutlineableBlocks); - const DiffT NumColdBlocks = Dist(Gen); - for (BinaryBasicBlock *BB : llvm::make_range(End - NumColdBlocks, End)) + const DiffT NumBlocks = End - Start; + assert(NumBlocks > 0 && "Cannot fragment empty function"); + + // We want to split at least one block + const auto LastSplitPoint = std::max(NumBlocks - 1, 1); + std::uniform_int_distribution 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)); } }; @@ -171,26 +169,33 @@ struct SplitRandomN 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 { using DiffT = typename std::iterator_traits::difference_type; - const DiffT NumOutlineableBlocks = End - Start; - - // We want to split at least one fragment if possible - const auto MinimumSplits = std::min(NumOutlineableBlocks, 1); - std::uniform_int_distribution Dist(MinimumSplits, - NumOutlineableBlocks); + const DiffT NumBlocks = End - Start; + assert(NumBlocks > 0 && "Cannot fragment empty function"); + + // 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(MaximumSplits, 1); + std::uniform_int_distribution Dist(MinimumSplits, MaximumSplits); // Choose how many splits to perform const DiffT NumSplits = Dist(Gen); // Draw split points from a lottery - SmallVector Lottery(NumOutlineableBlocks); - std::iota(Lottery.begin(), Lottery.end(), 0u); + SmallVector 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; @@ -211,13 +216,12 @@ struct SplitRandomN final : public SplitStrategy { 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 @@ -306,10 +310,7 @@ void SplitFunctions::splitFunction(BinaryFunction &BF, SplitStrategy &S) { 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. @@ -337,12 +338,22 @@ void SplitFunctions::splitFunction(BinaryFunction &BF, SplitStrategy &S) { } } + 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. @@ -354,20 +365,30 @@ void SplitFunctions::splitFunction(BinaryFunction &BF, SplitStrategy &S) { 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 -- 2.7.4