1056 lines · cpp
1//===- bolt/Passes/SplitFunctions.cpp - Pass for splitting function code --===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the SplitFunctions pass.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Passes/SplitFunctions.h"14#include "bolt/Core/BinaryBasicBlock.h"15#include "bolt/Core/BinaryFunction.h"16#include "bolt/Core/FunctionLayout.h"17#include "bolt/Core/ParallelUtilities.h"18#include "bolt/Utils/CommandLineOpts.h"19#include "llvm/ADT/STLExtras.h"20#include "llvm/ADT/SmallVector.h"21#include "llvm/ADT/iterator_range.h"22#include "llvm/Support/CommandLine.h"23#include "llvm/Support/FormatVariadic.h"24#include <algorithm>25#include <iterator>26#include <memory>27#include <numeric>28#include <random>29#include <vector>30 31#define DEBUG_TYPE "bolt-opts"32 33using namespace llvm;34using namespace bolt;35 36namespace {37class DeprecatedSplitFunctionOptionParser : public cl::parser<bool> {38public:39 explicit DeprecatedSplitFunctionOptionParser(cl::Option &O)40 : cl::parser<bool>(O) {}41 42 bool parse(cl::Option &O, StringRef ArgName, StringRef Arg, bool &Value) {43 if (Arg == "2" || Arg == "3") {44 Value = true;45 errs() << formatv("BOLT-WARNING: specifying non-boolean value \"{0}\" "46 "for option -{1} is deprecated\n",47 Arg, ArgName);48 return false;49 }50 return cl::parser<bool>::parse(O, ArgName, Arg, Value);51 }52};53} // namespace54 55namespace opts {56 57extern cl::OptionCategory BoltOptCategory;58 59extern cl::opt<bool> SplitEH;60extern cl::opt<unsigned> ExecutionCountThreshold;61extern cl::opt<uint32_t> RandomSeed;62 63static cl::opt<bool> AggressiveSplitting(64 "split-all-cold", cl::desc("outline as many cold basic blocks as possible"),65 cl::cat(BoltOptCategory));66 67static cl::opt<unsigned> SplitAlignThreshold(68 "split-align-threshold",69 cl::desc("when deciding to split a function, apply this alignment "70 "while doing the size comparison (see -split-threshold). "71 "Default value: 2."),72 cl::init(2),73 74 cl::Hidden, cl::cat(BoltOptCategory));75 76static cl::opt<bool, false, DeprecatedSplitFunctionOptionParser>77 SplitFunctions("split-functions",78 cl::desc("split functions into fragments"),79 cl::cat(BoltOptCategory));80 81static cl::opt<unsigned> SplitThreshold(82 "split-threshold",83 cl::desc("split function only if its main size is reduced by more than "84 "given amount of bytes. Default value: 0, i.e. split iff the "85 "size is reduced. Note that on some architectures the size can "86 "increase after splitting."),87 cl::init(0), cl::Hidden, cl::cat(BoltOptCategory));88 89static cl::opt<double> CallScale(90 "call-scale",91 cl::desc("Call score scale coefficient (when --split-strategy=cdsplit)"),92 cl::init(0.95), cl::ReallyHidden, cl::cat(BoltOptCategory));93 94static cl::opt<double>95 CallPower("call-power",96 cl::desc("Call score power (when --split-strategy=cdsplit)"),97 cl::init(0.05), cl::ReallyHidden, cl::cat(BoltOptCategory));98 99static cl::opt<double>100 JumpPower("jump-power",101 cl::desc("Jump score power (when --split-strategy=cdsplit)"),102 cl::init(0.15), cl::ReallyHidden, cl::cat(BoltOptCategory));103} // namespace opts104 105namespace {106bool hasFullProfile(const BinaryFunction &BF) {107 return llvm::all_of(BF.blocks(), [](const BinaryBasicBlock &BB) {108 return BB.getExecutionCount() != BinaryBasicBlock::COUNT_NO_PROFILE;109 });110}111 112bool allBlocksCold(const BinaryFunction &BF) {113 return llvm::all_of(BF.blocks(), [](const BinaryBasicBlock &BB) {114 return BB.getExecutionCount() == 0;115 });116}117 118struct SplitProfile2 final : public SplitStrategy {119 bool canSplit(const BinaryFunction &BF) override {120 return BF.hasValidProfile() && hasFullProfile(BF) && !allBlocksCold(BF);121 }122 123 bool compactFragments() override { return true; }124 125 void fragment(const BlockIt Start, const BlockIt End) override {126 for (BinaryBasicBlock *const BB : llvm::make_range(Start, End)) {127 if (BB->getExecutionCount() == 0)128 BB->setFragmentNum(FragmentNum::cold());129 }130 }131};132 133struct SplitCacheDirected final : public SplitStrategy {134 BinaryContext &BC;135 using BasicBlockOrder = BinaryFunction::BasicBlockOrderType;136 137 bool canSplit(const BinaryFunction &BF) override {138 return BF.hasValidProfile() && hasFullProfile(BF) && !allBlocksCold(BF);139 }140 141 explicit SplitCacheDirected(BinaryContext &BC) : BC(BC) {142 initializeAuxiliaryVariables();143 buildCallGraph();144 }145 146 // When some functions are hot-warm split and others are hot-warm-cold split,147 // we do not want to change the fragment numbers of the blocks in the hot-warm148 // split functions.149 bool compactFragments() override { return false; }150 151 void fragment(const BlockIt Start, const BlockIt End) override {152 BasicBlockOrder BlockOrder(Start, End);153 BinaryFunction &BF = *BlockOrder.front()->getFunction();154 // No need to re-split small functions.155 if (BlockOrder.size() <= 2)156 return;157 158 size_t BestSplitIndex = findSplitIndex(BF, BlockOrder);159 assert(BestSplitIndex < BlockOrder.size());160 161 // Assign fragments based on the computed best split index.162 // All basic blocks with index up to the best split index become hot.163 // All remaining blocks are warm / cold depending on if count is164 // greater than zero or not.165 for (size_t Index = 0; Index < BlockOrder.size(); Index++) {166 BinaryBasicBlock *BB = BlockOrder[Index];167 if (Index <= BestSplitIndex)168 BB->setFragmentNum(FragmentNum::main());169 else170 BB->setFragmentNum(BB->getKnownExecutionCount() > 0171 ? FragmentNum::warm()172 : FragmentNum::cold());173 }174 }175 176private:177 struct CallInfo {178 size_t Length;179 size_t Count;180 };181 182 struct SplitScore {183 size_t SplitIndex = size_t(-1);184 size_t HotSizeReduction = 0;185 double LocalScore = 0;186 double CoverCallScore = 0;187 188 double sum() const { return LocalScore + CoverCallScore; }189 };190 191 // Auxiliary variables used by the algorithm.192 size_t TotalNumBlocks{0};193 size_t OrigHotSectionSize{0};194 DenseMap<const BinaryBasicBlock *, size_t> GlobalIndices;195 DenseMap<const BinaryBasicBlock *, size_t> BBSizes;196 DenseMap<const BinaryBasicBlock *, size_t> BBOffsets;197 198 // Call graph.199 std::vector<SmallVector<const BinaryBasicBlock *, 0>> Callers;200 std::vector<SmallVector<const BinaryBasicBlock *, 0>> Callees;201 202 bool shouldConsiderForCallGraph(const BinaryFunction &BF) {203 // Only a subset of the functions in the binary will be considered204 // for initializing auxiliary variables and building call graph.205 return BF.hasValidIndex() && BF.hasValidProfile() && !BF.empty();206 }207 208 void initializeAuxiliaryVariables() {209 for (BinaryFunction *BF : BC.getSortedFunctions()) {210 if (!shouldConsiderForCallGraph(*BF))211 continue;212 213 // Calculate the size of each BB after hot-cold splitting.214 // This populates BinaryBasicBlock::OutputAddressRange which215 // can be used to compute the size of each BB.216 BC.calculateEmittedSize(*BF, /*FixBranches=*/true);217 218 for (BinaryBasicBlock *BB : BF->getLayout().blocks()) {219 // Unique global index.220 GlobalIndices[BB] = TotalNumBlocks;221 TotalNumBlocks++;222 223 // Block size after hot-cold splitting.224 BBSizes[BB] = BB->getOutputSize();225 226 // Hot block offset after hot-cold splitting.227 BBOffsets[BB] = OrigHotSectionSize;228 if (!BB->isSplit())229 OrigHotSectionSize += BBSizes[BB];230 }231 }232 }233 234 void buildCallGraph() {235 Callers.resize(TotalNumBlocks);236 Callees.resize(TotalNumBlocks);237 for (const BinaryFunction *SrcFunction : BC.getSortedFunctions()) {238 if (!shouldConsiderForCallGraph(*SrcFunction))239 continue;240 241 for (BinaryBasicBlock &SrcBB : SrcFunction->blocks()) {242 // Skip blocks that are not executed243 if (SrcBB.getKnownExecutionCount() == 0)244 continue;245 246 // Find call instructions and extract target symbols from each one247 for (const MCInst &Inst : SrcBB) {248 if (!BC.MIB->isCall(Inst))249 continue;250 251 // Call info252 const MCSymbol *DstSym = BC.MIB->getTargetSymbol(Inst);253 // Ignore calls w/o information254 if (!DstSym)255 continue;256 257 const BinaryFunction *DstFunction = BC.getFunctionForSymbol(DstSym);258 // Ignore calls that do not have a valid target, but do not ignore259 // recursive calls, because caller block could be moved to warm.260 if (!DstFunction || DstFunction->getLayout().block_empty())261 continue;262 263 const BinaryBasicBlock *DstBB = &(DstFunction->front());264 265 // Record the call only if DstBB is also in functions to consider for266 // call graph.267 if (GlobalIndices.contains(DstBB)) {268 Callers[GlobalIndices[DstBB]].push_back(&SrcBB);269 Callees[GlobalIndices[&SrcBB]].push_back(DstBB);270 }271 }272 }273 }274 }275 276 /// Populate BinaryBasicBlock::OutputAddressRange with estimated basic block277 /// start and end addresses for hot and warm basic blocks, assuming hot-warm278 /// splitting happens at \p SplitIndex. Also return estimated end addresses279 /// of the hot fragment before and after splitting.280 /// The estimations take into account the potential addition of branch281 /// instructions due to split fall through branches as well as the need to282 /// use longer branch instructions for split (un)conditional branches.283 std::pair<size_t, size_t>284 estimatePostSplitBBAddress(const BasicBlockOrder &BlockOrder,285 const size_t SplitIndex) {286 assert(SplitIndex < BlockOrder.size() && "Invalid split index");287 288 // Update function layout assuming hot-warm splitting at SplitIndex.289 for (size_t Index = 0; Index < BlockOrder.size(); Index++) {290 BinaryBasicBlock *BB = BlockOrder[Index];291 if (BB->getFragmentNum() == FragmentNum::cold())292 break;293 BB->setFragmentNum(Index <= SplitIndex ? FragmentNum::main()294 : FragmentNum::warm());295 }296 BinaryFunction *BF = BlockOrder[0]->getFunction();297 BF->getLayout().update(BlockOrder);298 // Populate BB.OutputAddressRange under the updated layout.299 BC.calculateEmittedSize(*BF);300 301 // Populate BB.OutputAddressRange with estimated new start and end addresses302 // and compute the old end address of the hot section and the new end303 // address of the hot section.304 size_t OldHotEndAddr{0};305 size_t NewHotEndAddr{0};306 size_t CurrentAddr = BBOffsets[BlockOrder[0]];307 for (BinaryBasicBlock *BB : BlockOrder) {308 // We only care about new addresses of blocks in hot/warm.309 if (BB->getFragmentNum() == FragmentNum::cold())310 break;311 const size_t NewSize = BB->getOutputSize();312 BB->setOutputStartAddress(CurrentAddr);313 CurrentAddr += NewSize;314 BB->setOutputEndAddress(CurrentAddr);315 if (BB->getLayoutIndex() == SplitIndex) {316 NewHotEndAddr = CurrentAddr;317 // Approximate the start address of the warm fragment of the current318 // function using the original hot section size.319 CurrentAddr = OrigHotSectionSize;320 }321 OldHotEndAddr = BBOffsets[BB] + BBSizes[BB];322 }323 return std::make_pair(OldHotEndAddr, NewHotEndAddr);324 }325 326 /// Get a collection of "shortenable" calls, that is, calls of type X->Y327 /// when the function order is [... X ... BF ... Y ...].328 /// If the hot fragment size of BF is reduced, then such calls are guaranteed329 /// to get shorter by the reduced hot fragment size.330 std::vector<CallInfo> extractCoverCalls(const BinaryFunction &BF) {331 // Record the length and the count of the calls that can be shortened332 std::vector<CallInfo> CoverCalls;333 if (opts::CallScale == 0)334 return CoverCalls;335 336 const BinaryFunction *ThisBF = &BF;337 const BinaryBasicBlock *ThisBB = &(ThisBF->front());338 const size_t ThisGI = GlobalIndices[ThisBB];339 340 for (const BinaryFunction *DstBF : BC.getSortedFunctions()) {341 if (!shouldConsiderForCallGraph(*DstBF))342 continue;343 344 const BinaryBasicBlock *DstBB = &(DstBF->front());345 if (DstBB->getKnownExecutionCount() == 0)346 continue;347 348 const size_t DstGI = GlobalIndices[DstBB];349 for (const BinaryBasicBlock *SrcBB : Callers[DstGI]) {350 const BinaryFunction *SrcBF = SrcBB->getFunction();351 if (ThisBF == SrcBF)352 continue;353 354 const size_t CallCount = SrcBB->getKnownExecutionCount();355 356 const size_t SrcGI = GlobalIndices[SrcBB];357 358 const bool IsCoverCall = (SrcGI < ThisGI && ThisGI < DstGI) ||359 (DstGI <= ThisGI && ThisGI < SrcGI);360 if (!IsCoverCall)361 continue;362 363 const size_t SrcBBEndAddr = BBOffsets[SrcBB] + BBSizes[SrcBB];364 const size_t DstBBStartAddr = BBOffsets[DstBB];365 const size_t CallLength =366 AbsoluteDifference(SrcBBEndAddr, DstBBStartAddr);367 const CallInfo CI{CallLength, CallCount};368 CoverCalls.emplace_back(CI);369 }370 }371 return CoverCalls;372 }373 374 /// Compute the edge score of a call edge.375 double computeCallScore(uint64_t CallCount, size_t CallLength) {376 // Increase call lengths by 1 to avoid raising 0 to a negative power.377 return opts::CallScale * static_cast<double>(CallCount) /378 std::pow(static_cast<double>(CallLength + 1), opts::CallPower);379 }380 381 /// Compute the edge score of a jump (branch) edge.382 double computeJumpScore(uint64_t JumpCount, size_t JumpLength) {383 // Increase jump lengths by 1 to avoid raising 0 to a negative power.384 return static_cast<double>(JumpCount) /385 std::pow(static_cast<double>(JumpLength + 1), opts::JumpPower);386 }387 388 /// Compute sum of scores over jumps within \p BlockOrder given \p SplitIndex.389 /// Increment Score.LocalScore in place by the sum.390 void computeJumpScore(const BasicBlockOrder &BlockOrder,391 const size_t SplitIndex, SplitScore &Score) {392 393 for (const BinaryBasicBlock *SrcBB : BlockOrder) {394 if (SrcBB->getKnownExecutionCount() == 0)395 continue;396 397 const size_t SrcBBEndAddr = SrcBB->getOutputAddressRange().second;398 399 for (const auto Pair : zip(SrcBB->successors(), SrcBB->branch_info())) {400 const BinaryBasicBlock *DstBB = std::get<0>(Pair);401 const BinaryBasicBlock::BinaryBranchInfo &Branch = std::get<1>(Pair);402 const size_t JumpCount = Branch.Count;403 404 if (JumpCount == 0)405 continue;406 407 const size_t DstBBStartAddr = DstBB->getOutputAddressRange().first;408 const size_t NewJumpLength =409 AbsoluteDifference(SrcBBEndAddr, DstBBStartAddr);410 Score.LocalScore += computeJumpScore(JumpCount, NewJumpLength);411 }412 }413 }414 415 /// Compute sum of scores over calls originated in the current function416 /// given \p SplitIndex. Increment Score.LocalScore in place by the sum.417 void computeLocalCallScore(const BasicBlockOrder &BlockOrder,418 const size_t SplitIndex, SplitScore &Score) {419 if (opts::CallScale == 0)420 return;421 422 // Global index of the last block in the current function.423 // This is later used to determine whether a call originated in the current424 // function is to a function that comes after the current function.425 const size_t LastGlobalIndex = GlobalIndices[BlockOrder.back()];426 427 // The length of calls originated in the input function can increase /428 // decrease depending on the splitting decision.429 for (const BinaryBasicBlock *SrcBB : BlockOrder) {430 const size_t CallCount = SrcBB->getKnownExecutionCount();431 // If SrcBB does not call any functions, skip it.432 if (CallCount == 0)433 continue;434 435 // Obtain an estimate on the end address of the src basic block436 // after splitting at SplitIndex.437 const size_t SrcBBEndAddr = SrcBB->getOutputAddressRange().second;438 439 for (const BinaryBasicBlock *DstBB : Callees[GlobalIndices[SrcBB]]) {440 // Obtain an estimate on the start address of the dst basic block441 // after splitting at SplitIndex. If DstBB is in a function before442 // the current function, then its start address remains unchanged.443 size_t DstBBStartAddr = BBOffsets[DstBB];444 // If DstBB is in a function after the current function, then its445 // start address should be adjusted based on the reduction in hot size.446 if (GlobalIndices[DstBB] > LastGlobalIndex) {447 assert(DstBBStartAddr >= Score.HotSizeReduction);448 DstBBStartAddr -= Score.HotSizeReduction;449 }450 const size_t NewCallLength =451 AbsoluteDifference(SrcBBEndAddr, DstBBStartAddr);452 Score.LocalScore += computeCallScore(CallCount, NewCallLength);453 }454 }455 }456 457 /// Compute sum of splitting scores for cover calls of the input function.458 /// Increment Score.CoverCallScore in place by the sum.459 void computeCoverCallScore(const BasicBlockOrder &BlockOrder,460 const size_t SplitIndex,461 const std::vector<CallInfo> &CoverCalls,462 SplitScore &Score) {463 if (opts::CallScale == 0)464 return;465 466 for (const CallInfo CI : CoverCalls) {467 assert(CI.Length >= Score.HotSizeReduction &&468 "Length of cover calls must exceed reduced size of hot fragment.");469 // Compute the new length of the call, which is shorter than the original470 // one by the size of the split fragment minus the total size increase.471 const size_t NewCallLength = CI.Length - Score.HotSizeReduction;472 Score.CoverCallScore += computeCallScore(CI.Count, NewCallLength);473 }474 }475 476 /// Compute the split score of splitting a function at a given index.477 /// The split score consists of local score and cover score. This function478 /// returns \p Score of SplitScore type. It contains the local score and479 /// cover score of the current splitting index. For easier book keeping and480 /// comparison, it also stores the split index and the resulting reduction481 /// in hot fragment size.482 SplitScore computeSplitScore(const BinaryFunction &BF,483 const BasicBlockOrder &BlockOrder,484 const size_t SplitIndex,485 const std::vector<CallInfo> &CoverCalls) {486 // Populate BinaryBasicBlock::OutputAddressRange with estimated487 // new start and end addresses after hot-warm splitting at SplitIndex.488 size_t OldHotEnd;489 size_t NewHotEnd;490 std::tie(OldHotEnd, NewHotEnd) =491 estimatePostSplitBBAddress(BlockOrder, SplitIndex);492 493 SplitScore Score;494 Score.SplitIndex = SplitIndex;495 496 // It's not worth splitting if OldHotEnd < NewHotEnd.497 if (OldHotEnd < NewHotEnd)498 return Score;499 500 // Hot fragment size reduction due to splitting.501 Score.HotSizeReduction = OldHotEnd - NewHotEnd;502 503 // First part of LocalScore is the sum over call edges originated in the504 // input function. These edges can get shorter or longer depending on505 // SplitIndex. Score.LocalScore is incremented in place.506 computeLocalCallScore(BlockOrder, SplitIndex, Score);507 508 // Second part of LocalScore is the sum over jump edges with src basic block509 // and dst basic block in the current function. Score.LocalScore is510 // incremented in place.511 computeJumpScore(BlockOrder, SplitIndex, Score);512 513 // Compute CoverCallScore and store in Score in place.514 computeCoverCallScore(BlockOrder, SplitIndex, CoverCalls, Score);515 return Score;516 }517 518 /// Find the most likely successor of a basic block when it has one or two519 /// successors. Return nullptr otherwise.520 const BinaryBasicBlock *getMostLikelySuccessor(const BinaryBasicBlock *BB) {521 if (BB->succ_size() == 1)522 return BB->getSuccessor();523 if (BB->succ_size() == 2) {524 uint64_t TakenCount = BB->getTakenBranchInfo().Count;525 assert(TakenCount != BinaryBasicBlock::COUNT_NO_PROFILE);526 uint64_t NonTakenCount = BB->getFallthroughBranchInfo().Count;527 assert(NonTakenCount != BinaryBasicBlock::COUNT_NO_PROFILE);528 if (TakenCount > NonTakenCount)529 return BB->getConditionalSuccessor(true);530 else if (TakenCount < NonTakenCount)531 return BB->getConditionalSuccessor(false);532 }533 return nullptr;534 }535 536 /// Find the best index for splitting. The returned value is the index of the537 /// last hot basic block. Hence, "no splitting" is equivalent to returning the538 /// value which is one less than the size of the function.539 size_t findSplitIndex(const BinaryFunction &BF,540 const BasicBlockOrder &BlockOrder) {541 assert(BlockOrder.size() > 2);542 // Find all function calls that can be shortened if we move blocks of the543 // current function to warm/cold544 const std::vector<CallInfo> CoverCalls = extractCoverCalls(BF);545 546 // Find the existing hot-cold splitting index.547 size_t HotColdIndex = 0;548 while (HotColdIndex + 1 < BlockOrder.size()) {549 if (BlockOrder[HotColdIndex + 1]->getFragmentNum() == FragmentNum::cold())550 break;551 HotColdIndex++;552 }553 assert(HotColdIndex + 1 == BlockOrder.size() ||554 (BlockOrder[HotColdIndex]->getFragmentNum() == FragmentNum::main() &&555 BlockOrder[HotColdIndex + 1]->getFragmentNum() ==556 FragmentNum::cold()));557 558 // Try all possible split indices up to HotColdIndex (blocks that have559 // Index <= SplitIndex are in hot) and find the one maximizing the560 // splitting score.561 SplitScore BestScore;562 for (size_t Index = 0; Index <= HotColdIndex; Index++) {563 const BinaryBasicBlock *LastHotBB = BlockOrder[Index];564 assert(LastHotBB->getFragmentNum() != FragmentNum::cold());565 566 // Do not break jump to the most likely successor.567 if (Index + 1 < BlockOrder.size() &&568 BlockOrder[Index + 1] == getMostLikelySuccessor(LastHotBB))569 continue;570 571 const SplitScore Score =572 computeSplitScore(BF, BlockOrder, Index, CoverCalls);573 if (Score.sum() > BestScore.sum())574 BestScore = Score;575 }576 577 // If we don't find a good splitting point, fallback to the original one.578 if (BestScore.SplitIndex == size_t(-1))579 return HotColdIndex;580 581 return BestScore.SplitIndex;582 }583};584 585struct SplitRandom2 final : public SplitStrategy {586 std::minstd_rand0 Gen;587 588 SplitRandom2() : Gen(opts::RandomSeed.getValue()) {}589 590 bool canSplit(const BinaryFunction &BF) override { return true; }591 592 bool compactFragments() override { return true; }593 594 void fragment(const BlockIt Start, const BlockIt End) override {595 using DiffT = typename std::iterator_traits<BlockIt>::difference_type;596 const DiffT NumBlocks = End - Start;597 assert(NumBlocks > 0 && "Cannot fragment empty function");598 599 // We want to split at least one block600 const auto LastSplitPoint = std::max<DiffT>(NumBlocks - 1, 1);601 std::uniform_int_distribution<DiffT> Dist(1, LastSplitPoint);602 const DiffT SplitPoint = Dist(Gen);603 for (BinaryBasicBlock *BB : llvm::make_range(Start + SplitPoint, End))604 BB->setFragmentNum(FragmentNum::cold());605 606 LLVM_DEBUG(dbgs() << formatv("BOLT-DEBUG: randomly chose last {0} (out of "607 "{1} possible) blocks to split\n",608 NumBlocks - SplitPoint, End - Start));609 }610};611 612struct SplitRandomN final : public SplitStrategy {613 std::minstd_rand0 Gen;614 615 SplitRandomN() : Gen(opts::RandomSeed.getValue()) {}616 617 bool canSplit(const BinaryFunction &BF) override { return true; }618 619 bool compactFragments() override { return true; }620 621 void fragment(const BlockIt Start, const BlockIt End) override {622 using DiffT = typename std::iterator_traits<BlockIt>::difference_type;623 const DiffT NumBlocks = End - Start;624 assert(NumBlocks > 0 && "Cannot fragment empty function");625 626 // With n blocks, there are n-1 places to split them.627 const DiffT MaximumSplits = NumBlocks - 1;628 // We want to generate at least two fragment if possible, but if there is629 // only one block, no splits are possible.630 const auto MinimumSplits = std::min<DiffT>(MaximumSplits, 1);631 std::uniform_int_distribution<DiffT> Dist(MinimumSplits, MaximumSplits);632 // Choose how many splits to perform633 const DiffT NumSplits = Dist(Gen);634 635 // Draw split points from a lottery636 SmallVector<unsigned, 0> Lottery(MaximumSplits);637 // Start lottery at 1, because there is no meaningful splitpoint before the638 // first block.639 std::iota(Lottery.begin(), Lottery.end(), 1u);640 std::shuffle(Lottery.begin(), Lottery.end(), Gen);641 Lottery.resize(NumSplits);642 llvm::sort(Lottery);643 644 // Add one past the end entry to lottery645 Lottery.push_back(NumBlocks);646 647 unsigned LotteryIndex = 0;648 unsigned BBPos = 0;649 for (BinaryBasicBlock *const BB : make_range(Start, End)) {650 // Check whether to start new fragment651 if (BBPos >= Lottery[LotteryIndex])652 ++LotteryIndex;653 654 // Because LotteryIndex is 0 based and cold fragments are 1 based, we can655 // use the index to assign fragments.656 BB->setFragmentNum(FragmentNum(LotteryIndex));657 658 ++BBPos;659 }660 }661};662 663struct SplitAll final : public SplitStrategy {664 bool canSplit(const BinaryFunction &BF) override { return true; }665 666 bool compactFragments() override {667 // Keeping empty fragments allows us to test, that empty fragments do not668 // generate symbols.669 return false;670 }671 672 void fragment(const BlockIt Start, const BlockIt End) override {673 unsigned Fragment = 0;674 for (BinaryBasicBlock *const BB : llvm::make_range(Start, End))675 BB->setFragmentNum(FragmentNum(Fragment++));676 }677};678} // namespace679 680namespace llvm {681namespace bolt {682 683bool SplitFunctions::shouldOptimize(const BinaryFunction &BF) const {684 // Apply execution count threshold685 if (BF.getKnownExecutionCount() < opts::ExecutionCountThreshold)686 return false;687 688 return BinaryFunctionPass::shouldOptimize(BF);689}690 691Error SplitFunctions::runOnFunctions(BinaryContext &BC) {692 if (!opts::SplitFunctions)693 return Error::success();694 695 if (BC.IsLinuxKernel && BC.BOLTReserved.empty()) {696 BC.errs() << "BOLT-ERROR: split functions require reserved space in the "697 "Linux kernel binary\n";698 exit(1);699 }700 701 // If split strategy is not CDSplit, then a second run of the pass is not702 // needed after function reordering.703 if (BC.HasFinalizedFunctionOrder &&704 opts::SplitStrategy != opts::SplitFunctionsStrategy::CDSplit)705 return Error::success();706 707 std::unique_ptr<SplitStrategy> Strategy;708 bool ForceSequential = false;709 710 switch (opts::SplitStrategy) {711 case opts::SplitFunctionsStrategy::CDSplit:712 // CDSplit runs two splitting passes: hot-cold splitting (SplitPrfoile2)713 // before function reordering and hot-warm-cold splitting714 // (SplitCacheDirected) after function reordering.715 if (BC.HasFinalizedFunctionOrder)716 Strategy = std::make_unique<SplitCacheDirected>(BC);717 else718 Strategy = std::make_unique<SplitProfile2>();719 opts::AggressiveSplitting = true;720 BC.HasWarmSection = true;721 break;722 case opts::SplitFunctionsStrategy::Profile2:723 Strategy = std::make_unique<SplitProfile2>();724 break;725 case opts::SplitFunctionsStrategy::Random2:726 Strategy = std::make_unique<SplitRandom2>();727 // If we split functions randomly, we need to ensure that across runs with728 // the same input, we generate random numbers for each function in the same729 // order.730 ForceSequential = true;731 break;732 case opts::SplitFunctionsStrategy::RandomN:733 Strategy = std::make_unique<SplitRandomN>();734 ForceSequential = true;735 break;736 case opts::SplitFunctionsStrategy::All:737 Strategy = std::make_unique<SplitAll>();738 break;739 }740 741 ParallelUtilities::PredicateTy SkipFunc = [&](const BinaryFunction &BF) {742 return !shouldOptimize(BF);743 };744 745 ParallelUtilities::runOnEachFunction(746 BC, ParallelUtilities::SchedulingPolicy::SP_BB_LINEAR,747 [&](BinaryFunction &BF) { splitFunction(BF, *Strategy); }, SkipFunc,748 "SplitFunctions", ForceSequential);749 750 if (SplitBytesHot + SplitBytesCold > 0)751 BC.outs() << "BOLT-INFO: splitting separates " << SplitBytesHot752 << " hot bytes from " << SplitBytesCold << " cold bytes "753 << format("(%.2lf%% of split functions is hot).\n",754 100.0 * SplitBytesHot /755 (SplitBytesHot + SplitBytesCold));756 return Error::success();757}758 759void SplitFunctions::splitFunction(BinaryFunction &BF, SplitStrategy &S) {760 if (BF.empty())761 return;762 763 if (!S.canSplit(BF))764 return;765 766 FunctionLayout &Layout = BF.getLayout();767 BinaryFunction::BasicBlockOrderType PreSplitLayout(Layout.block_begin(),768 Layout.block_end());769 770 BinaryContext &BC = BF.getBinaryContext();771 size_t OriginalHotSize;772 size_t HotSize;773 size_t ColdSize;774 if (BC.isX86()) {775 std::tie(OriginalHotSize, ColdSize) = BC.calculateEmittedSize(BF);776 LLVM_DEBUG(dbgs() << "Estimated size for function " << BF777 << " pre-split is <0x"778 << Twine::utohexstr(OriginalHotSize) << ", 0x"779 << Twine::utohexstr(ColdSize) << ">\n");780 }781 782 BinaryFunction::BasicBlockOrderType NewLayout(Layout.block_begin(),783 Layout.block_end());784 // Never outline the first basic block.785 NewLayout.front()->setCanOutline(false);786 for (BinaryBasicBlock *const BB : NewLayout) {787 if (!BB->canOutline())788 continue;789 790 // Do not split extra entry points in aarch64. They can be referred by791 // using ADRs and when this happens, these blocks cannot be placed far792 // away due to the limited range in ADR instruction.793 if (BC.isAArch64() && BB->isEntryPoint()) {794 BB->setCanOutline(false);795 continue;796 }797 798 if (BF.hasEHRanges() && !opts::SplitEH) {799 // We cannot move landing pads (or rather entry points for landing pads).800 if (BB->isLandingPad()) {801 BB->setCanOutline(false);802 continue;803 }804 // We cannot move a block that can throw since exception-handling805 // runtime cannot deal with split functions. However, if we can guarantee806 // that the block never throws, it is safe to move the block to807 // decrease the size of the function.808 for (MCInst &Instr : *BB) {809 if (BC.MIB->isInvoke(Instr)) {810 BB->setCanOutline(false);811 break;812 }813 }814 }815 816 // Outlining blocks with dynamic branches is not supported yet.817 if (BC.IsLinuxKernel) {818 if (llvm::any_of(819 *BB, [&](MCInst &Inst) { return BC.MIB->isDynamicBranch(Inst); }))820 BB->setCanOutline(false);821 }822 }823 824 BF.getLayout().updateLayoutIndices();825 S.fragment(NewLayout.begin(), NewLayout.end());826 827 // Make sure all non-outlineable blocks are in the main-fragment.828 for (BinaryBasicBlock *const BB : NewLayout) {829 if (!BB->canOutline())830 BB->setFragmentNum(FragmentNum::main());831 }832 833 if (opts::AggressiveSplitting) {834 // All blocks with 0 count that we can move go to the end of the function.835 // Even if they were natural to cluster formation and were seen in-between836 // hot basic blocks.837 llvm::stable_sort(NewLayout, [&](const BinaryBasicBlock *const A,838 const BinaryBasicBlock *const B) {839 return A->getFragmentNum() < B->getFragmentNum();840 });841 } else if (BF.hasEHRanges() && !opts::SplitEH) {842 // Typically functions with exception handling have landing pads at the end.843 // We cannot move beginning of landing pads, but we can move 0-count blocks844 // comprising landing pads to the end and thus facilitate splitting.845 auto FirstLP = NewLayout.begin();846 while ((*FirstLP)->isLandingPad())847 ++FirstLP;848 849 std::stable_sort(FirstLP, NewLayout.end(),850 [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {851 return A->getFragmentNum() < B->getFragmentNum();852 });853 }854 855 // Make sure that fragments are increasing.856 FragmentNum CurrentFragment = NewLayout.back()->getFragmentNum();857 for (BinaryBasicBlock *const BB : reverse(NewLayout)) {858 if (BB->getFragmentNum() > CurrentFragment)859 BB->setFragmentNum(CurrentFragment);860 CurrentFragment = BB->getFragmentNum();861 }862 863 if (S.compactFragments()) {864 FragmentNum CurrentFragment = FragmentNum::main();865 FragmentNum NewFragment = FragmentNum::main();866 for (BinaryBasicBlock *const BB : NewLayout) {867 if (BB->getFragmentNum() > CurrentFragment) {868 CurrentFragment = BB->getFragmentNum();869 NewFragment = FragmentNum(NewFragment.get() + 1);870 }871 BB->setFragmentNum(NewFragment);872 }873 }874 875 const bool LayoutUpdated = BF.getLayout().update(NewLayout);876 877 // For shared objects, invoke instructions and corresponding landing pads878 // have to be placed in the same fragment. When we split them, create879 // trampoline landing pads that will redirect the execution to real LPs.880 TrampolineSetType Trampolines;881 if (BF.hasEHRanges() && BF.isSplit()) {882 // If all landing pads for this fragment are grouped in one (potentially883 // different) fragment, we can set LPStart to the start of that fragment884 // and avoid trampoline code.885 bool NeedsTrampolines = false;886 for (FunctionFragment &FF : BF.getLayout().fragments()) {887 // Vector of fragments that contain landing pads for this fragment.888 SmallVector<FragmentNum, 4> LandingPadFragments;889 for (const BinaryBasicBlock *BB : FF)890 for (const BinaryBasicBlock *LPB : BB->landing_pads())891 LandingPadFragments.push_back(LPB->getFragmentNum());892 893 // Eliminate duplicate entries from the vector.894 llvm::sort(LandingPadFragments);895 auto Last = llvm::unique(LandingPadFragments);896 LandingPadFragments.erase(Last, LandingPadFragments.end());897 898 if (LandingPadFragments.size() == 0) {899 // If the fragment has no landing pads, we can safely set itself as its900 // landing pad fragment.901 BF.setLPFragment(FF.getFragmentNum(), FF.getFragmentNum());902 } else if (LandingPadFragments.size() == 1) {903 BF.setLPFragment(FF.getFragmentNum(), LandingPadFragments.front());904 } else {905 if (!BC.HasFixedLoadAddress) {906 NeedsTrampolines = true;907 break;908 } else {909 BF.setLPFragment(FF.getFragmentNum(), std::nullopt);910 }911 }912 }913 914 // Trampolines guarantee that all landing pads for any given fragment will915 // be contained in the same fragment.916 if (NeedsTrampolines) {917 for (FunctionFragment &FF : BF.getLayout().fragments())918 BF.setLPFragment(FF.getFragmentNum(), FF.getFragmentNum());919 Trampolines = createEHTrampolines(BF);920 }921 }922 923 // Check the new size to see if it's worth splitting the function.924 if (BC.isX86() && LayoutUpdated) {925 std::tie(HotSize, ColdSize) = BC.calculateEmittedSize(BF);926 LLVM_DEBUG(dbgs() << "Estimated size for function " << BF927 << " post-split is <0x" << Twine::utohexstr(HotSize)928 << ", 0x" << Twine::utohexstr(ColdSize) << ">\n");929 if (alignTo(OriginalHotSize, opts::SplitAlignThreshold) <=930 alignTo(HotSize, opts::SplitAlignThreshold) + opts::SplitThreshold) {931 if (opts::Verbosity >= 2) {932 BC.outs() << "BOLT-INFO: Reversing splitting of function "933 << formatv("{0}:\n {1:x}, {2:x} -> {3:x}\n", BF, HotSize,934 ColdSize, OriginalHotSize);935 }936 937 // Reverse the action of createEHTrampolines(). The trampolines will be938 // placed immediately before the matching destination resulting in no939 // extra code.940 if (PreSplitLayout.size() != BF.size())941 PreSplitLayout = mergeEHTrampolines(BF, PreSplitLayout, Trampolines);942 943 for (BinaryBasicBlock &BB : BF)944 BB.setFragmentNum(FragmentNum::main());945 BF.getLayout().update(PreSplitLayout);946 } else {947 SplitBytesHot += HotSize;948 SplitBytesCold += ColdSize;949 }950 }951 952 // Restore LP fragment for the main fragment if the splitting was undone.953 if (BF.hasEHRanges() && !BF.isSplit())954 BF.setLPFragment(FragmentNum::main(), FragmentNum::main());955 956 // Fix branches if the splitting decision of the pass after function957 // reordering is different from that of the pass before function reordering.958 if (LayoutUpdated && BC.HasFinalizedFunctionOrder)959 BF.fixBranches();960}961 962SplitFunctions::TrampolineSetType963SplitFunctions::createEHTrampolines(BinaryFunction &BF) const {964 const auto &MIB = BF.getBinaryContext().MIB;965 966 // Map real landing pads to the corresponding trampolines.967 TrampolineSetType LPTrampolines;968 969 // Iterate over the copy of basic blocks since we are adding new blocks to the970 // function which will invalidate its iterators.971 std::vector<BinaryBasicBlock *> Blocks(BF.pbegin(), BF.pend());972 for (BinaryBasicBlock *BB : Blocks) {973 for (MCInst &Instr : *BB) {974 const std::optional<MCPlus::MCLandingPad> EHInfo = MIB->getEHInfo(Instr);975 if (!EHInfo || !EHInfo->first)976 continue;977 978 const MCSymbol *LPLabel = EHInfo->first;979 BinaryBasicBlock *LPBlock = BF.getBasicBlockForLabel(LPLabel);980 if (BB->getFragmentNum() == LPBlock->getFragmentNum())981 continue;982 983 const MCSymbol *TrampolineLabel = nullptr;984 const TrampolineKey Key(BB->getFragmentNum(), LPLabel);985 auto Iter = LPTrampolines.find(Key);986 if (Iter != LPTrampolines.end()) {987 TrampolineLabel = Iter->second;988 } else {989 // Create a trampoline basic block in the same fragment as the thrower.990 // Note: there's no need to insert the jump instruction, it will be991 // added by fixBranches().992 BinaryBasicBlock *TrampolineBB = BF.addBasicBlock();993 TrampolineBB->setFragmentNum(BB->getFragmentNum());994 TrampolineBB->setExecutionCount(LPBlock->getExecutionCount());995 TrampolineBB->addSuccessor(LPBlock, TrampolineBB->getExecutionCount());996 TrampolineBB->setCFIState(LPBlock->getCFIState());997 TrampolineLabel = TrampolineBB->getLabel();998 LPTrampolines.insert(std::make_pair(Key, TrampolineLabel));999 }1000 1001 // Substitute the landing pad with the trampoline.1002 MIB->updateEHInfo(Instr,1003 MCPlus::MCLandingPad(TrampolineLabel, EHInfo->second));1004 }1005 }1006 1007 if (LPTrampolines.empty())1008 return LPTrampolines;1009 1010 // All trampoline blocks were added to the end of the function. Place them at1011 // the end of corresponding fragments.1012 BinaryFunction::BasicBlockOrderType NewLayout(BF.getLayout().block_begin(),1013 BF.getLayout().block_end());1014 stable_sort(NewLayout, [&](BinaryBasicBlock *A, BinaryBasicBlock *B) {1015 return A->getFragmentNum() < B->getFragmentNum();1016 });1017 BF.getLayout().update(NewLayout);1018 1019 // Conservatively introduce branch instructions.1020 BF.fixBranches();1021 1022 // Update exception-handling CFG for the function.1023 BF.recomputeLandingPads();1024 1025 return LPTrampolines;1026}1027 1028SplitFunctions::BasicBlockOrderType SplitFunctions::mergeEHTrampolines(1029 BinaryFunction &BF, SplitFunctions::BasicBlockOrderType &Layout,1030 const SplitFunctions::TrampolineSetType &Trampolines) const {1031 DenseMap<const MCSymbol *, SmallVector<const MCSymbol *, 0>>1032 IncomingTrampolines;1033 for (const auto &Entry : Trampolines) {1034 IncomingTrampolines[Entry.getFirst().Target].emplace_back(1035 Entry.getSecond());1036 }1037 1038 BasicBlockOrderType MergedLayout;1039 for (BinaryBasicBlock *BB : Layout) {1040 auto Iter = IncomingTrampolines.find(BB->getLabel());1041 if (Iter != IncomingTrampolines.end()) {1042 for (const MCSymbol *const Trampoline : Iter->getSecond()) {1043 BinaryBasicBlock *LPBlock = BF.getBasicBlockForLabel(Trampoline);1044 assert(LPBlock && "Could not find matching landing pad block.");1045 MergedLayout.push_back(LPBlock);1046 }1047 }1048 MergedLayout.push_back(BB);1049 }1050 1051 return MergedLayout;1052}1053 1054} // namespace bolt1055} // namespace llvm1056