835 lines · cpp
1//===- HotColdSplitting.cpp -- Outline Cold Regions -------------*- C++ -*-===//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/// \file10/// The goal of hot/cold splitting is to improve the memory locality of code.11/// The splitting pass does this by identifying cold blocks and moving them into12/// separate functions.13///14/// When the splitting pass finds a cold block (referred to as "the sink"), it15/// grows a maximal cold region around that block. The maximal region contains16/// all blocks (post-)dominated by the sink [*]. In theory, these blocks are as17/// cold as the sink. Once a region is found, it's split out of the original18/// function provided it's profitable to do so.19///20/// [*] In practice, there is some added complexity because some blocks are not21/// safe to extract.22///23/// TODO: Use the PM to get domtrees, and preserve BFI/BPI.24/// TODO: Reorder outlined functions.25///26//===----------------------------------------------------------------------===//27 28#include "llvm/Transforms/IPO/HotColdSplitting.h"29#include "llvm/ADT/PostOrderIterator.h"30#include "llvm/ADT/SmallVector.h"31#include "llvm/ADT/Statistic.h"32#include "llvm/Analysis/AssumptionCache.h"33#include "llvm/Analysis/BlockFrequencyInfo.h"34#include "llvm/Analysis/OptimizationRemarkEmitter.h"35#include "llvm/Analysis/PostDominators.h"36#include "llvm/Analysis/ProfileSummaryInfo.h"37#include "llvm/Analysis/TargetTransformInfo.h"38#include "llvm/IR/BasicBlock.h"39#include "llvm/IR/CFG.h"40#include "llvm/IR/DiagnosticInfo.h"41#include "llvm/IR/Dominators.h"42#include "llvm/IR/EHPersonalities.h"43#include "llvm/IR/Function.h"44#include "llvm/IR/Instruction.h"45#include "llvm/IR/Instructions.h"46#include "llvm/IR/Module.h"47#include "llvm/IR/PassManager.h"48#include "llvm/IR/ProfDataUtils.h"49#include "llvm/IR/User.h"50#include "llvm/IR/Value.h"51#include "llvm/Support/CommandLine.h"52#include "llvm/Support/Debug.h"53#include "llvm/Support/raw_ostream.h"54#include "llvm/Transforms/IPO.h"55#include "llvm/Transforms/Utils/CodeExtractor.h"56#include <cassert>57#include <limits>58#include <string>59 60#define DEBUG_TYPE "hotcoldsplit"61 62STATISTIC(NumColdRegionsFound, "Number of cold regions found.");63STATISTIC(NumColdRegionsOutlined, "Number of cold regions outlined.");64 65using namespace llvm;66 67static cl::opt<bool> EnableStaticAnalysis("hot-cold-static-analysis",68 cl::init(true), cl::Hidden);69 70static cl::opt<int>71 SplittingThreshold("hotcoldsplit-threshold", cl::init(2), cl::Hidden,72 cl::desc("Base penalty for splitting cold code (as a "73 "multiple of TCC_Basic)"));74 75static cl::opt<bool> EnableColdSection(76 "enable-cold-section", cl::init(false), cl::Hidden,77 cl::desc("Enable placement of extracted cold functions"78 " into a separate section after hot-cold splitting."));79 80static cl::opt<std::string>81 ColdSectionName("hotcoldsplit-cold-section-name", cl::init("__llvm_cold"),82 cl::Hidden,83 cl::desc("Name for the section containing cold functions "84 "extracted by hot-cold splitting."));85 86static cl::opt<int> MaxParametersForSplit(87 "hotcoldsplit-max-params", cl::init(4), cl::Hidden,88 cl::desc("Maximum number of parameters for a split function"));89 90static cl::opt<int> ColdBranchProbDenom(91 "hotcoldsplit-cold-probability-denom", cl::init(100), cl::Hidden,92 cl::desc("Divisor of cold branch probability."93 "BranchProbability = 1/ColdBranchProbDenom"));94 95namespace {96// Same as blockEndsInUnreachable in CodeGen/BranchFolding.cpp. Do not modify97// this function unless you modify the MBB version as well.98//99/// A no successor, non-return block probably ends in unreachable and is cold.100/// Also consider a block that ends in an indirect branch to be a return block,101/// since many targets use plain indirect branches to return.102bool blockEndsInUnreachable(const BasicBlock &BB) {103 if (!succ_empty(&BB))104 return false;105 if (BB.empty())106 return true;107 const Instruction *I = BB.getTerminator();108 return !(isa<ReturnInst>(I) || isa<IndirectBrInst>(I));109}110 111void analyzeProfMetadata(BasicBlock *BB,112 BranchProbability ColdProbThresh,113 SmallPtrSetImpl<BasicBlock *> &AnnotatedColdBlocks) {114 // TODO: Handle branches with > 2 successors.115 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());116 if (!CondBr)117 return;118 119 uint64_t TrueWt, FalseWt;120 if (!extractBranchWeights(*CondBr, TrueWt, FalseWt))121 return;122 123 auto SumWt = TrueWt + FalseWt;124 if (SumWt == 0)125 return;126 127 auto TrueProb = BranchProbability::getBranchProbability(TrueWt, SumWt);128 auto FalseProb = BranchProbability::getBranchProbability(FalseWt, SumWt);129 130 if (TrueProb <= ColdProbThresh)131 AnnotatedColdBlocks.insert(CondBr->getSuccessor(0));132 133 if (FalseProb <= ColdProbThresh)134 AnnotatedColdBlocks.insert(CondBr->getSuccessor(1));135}136 137bool unlikelyExecuted(BasicBlock &BB) {138 // Exception handling blocks are unlikely executed.139 if (BB.isEHPad() || isa<ResumeInst>(BB.getTerminator()))140 return true;141 142 // The block is cold if it calls/invokes a cold function. However, do not143 // mark sanitizer traps as cold.144 for (Instruction &I : BB)145 if (auto *CB = dyn_cast<CallBase>(&I))146 if (CB->hasFnAttr(Attribute::Cold) &&147 !CB->getMetadata(LLVMContext::MD_nosanitize))148 return true;149 150 // The block is cold if it has an unreachable terminator, unless it's151 // preceded by a call to a (possibly warm) noreturn call (e.g. longjmp).152 if (blockEndsInUnreachable(BB)) {153 if (auto *CI =154 dyn_cast_or_null<CallInst>(BB.getTerminator()->getPrevNode()))155 if (CI->hasFnAttr(Attribute::NoReturn))156 return false;157 return true;158 }159 160 return false;161}162 163/// Check whether it's safe to outline \p BB.164static bool mayExtractBlock(const BasicBlock &BB) {165 // EH pads are unsafe to outline because doing so breaks EH type tables. It166 // follows that invoke instructions cannot be extracted, because CodeExtractor167 // requires unwind destinations to be within the extraction region.168 //169 // Resumes that are not reachable from a cleanup landing pad are considered to170 // be unreachable. It’s not safe to split them out either.171 172 if (BB.hasAddressTaken() || BB.isEHPad())173 return false;174 auto Term = BB.getTerminator();175 if (isa<InvokeInst>(Term) || isa<ResumeInst>(Term))176 return false;177 178 // Do not outline basic blocks that have token type instructions. e.g.,179 // exception:180 // %0 = cleanuppad within none []181 // call void @"?terminate@@YAXXZ"() [ "funclet"(token %0) ]182 // br label %continue-exception183 if (llvm::any_of(184 BB, [](const Instruction &I) { return I.getType()->isTokenTy(); })) {185 return false;186 }187 188 return true;189}190 191/// Mark \p F cold. Based on this assumption, also optimize it for minimum size.192/// If \p UpdateEntryCount is true (set when this is a new split function and193/// module has profile data), set entry count to 0 to ensure treated as cold.194/// Return true if the function is changed.195static bool markFunctionCold(Function &F, bool UpdateEntryCount = false) {196 assert(!F.hasOptNone() && "Can't mark this cold");197 bool Changed = false;198 if (!F.hasFnAttribute(Attribute::Cold)) {199 F.addFnAttr(Attribute::Cold);200 Changed = true;201 }202 if (!F.hasMinSize()) {203 F.addFnAttr(Attribute::MinSize);204 Changed = true;205 }206 if (UpdateEntryCount) {207 // Set the entry count to 0 to ensure it is placed in the unlikely text208 // section when function sections are enabled.209 F.setEntryCount(0);210 Changed = true;211 }212 213 return Changed;214}215 216} // end anonymous namespace217 218/// Check whether \p F is inherently cold.219bool HotColdSplitting::isFunctionCold(const Function &F) const {220 if (F.hasFnAttribute(Attribute::Cold))221 return true;222 223 if (F.getCallingConv() == CallingConv::Cold)224 return true;225 226 if (PSI->isFunctionEntryCold(&F))227 return true;228 229 return false;230}231 232bool HotColdSplitting::isBasicBlockCold(233 BasicBlock *BB, BranchProbability ColdProbThresh,234 SmallPtrSetImpl<BasicBlock *> &AnnotatedColdBlocks,235 BlockFrequencyInfo *BFI) const {236 if (BFI) {237 if (PSI->isColdBlock(BB, BFI))238 return true;239 } else {240 // Find cold blocks of successors of BB during a reverse postorder traversal.241 analyzeProfMetadata(BB, ColdProbThresh, AnnotatedColdBlocks);242 243 // A statically cold BB would be known before it is visited244 // because the prof-data of incoming edges are 'analyzed' as part of RPOT.245 if (AnnotatedColdBlocks.count(BB))246 return true;247 }248 249 if (EnableStaticAnalysis && unlikelyExecuted(*BB))250 return true;251 252 return false;253}254 255// Returns false if the function should not be considered for hot-cold split256// optimization.257bool HotColdSplitting::shouldOutlineFrom(const Function &F) const {258 if (F.hasFnAttribute(Attribute::AlwaysInline))259 return false;260 261 if (F.hasFnAttribute(Attribute::NoInline))262 return false;263 264 // A function marked `noreturn` may contain unreachable terminators: these265 // should not be considered cold, as the function may be a trampoline.266 if (F.hasFnAttribute(Attribute::NoReturn))267 return false;268 269 if (F.hasFnAttribute(Attribute::SanitizeAddress) ||270 F.hasFnAttribute(Attribute::SanitizeHWAddress) ||271 F.hasFnAttribute(Attribute::SanitizeThread) ||272 F.hasFnAttribute(Attribute::SanitizeMemory))273 return false;274 275 // Do not outline scoped EH personality functions.276 if (F.hasPersonalityFn())277 if (isScopedEHPersonality(classifyEHPersonality(F.getPersonalityFn())))278 return false;279 280 return true;281}282 283/// Get the benefit score of outlining \p Region.284static InstructionCost getOutliningBenefit(ArrayRef<BasicBlock *> Region,285 TargetTransformInfo &TTI) {286 // Sum up the code size costs of non-terminator instructions. Tight coupling287 // with \ref getOutliningPenalty is needed to model the costs of terminators.288 InstructionCost Benefit = 0;289 for (BasicBlock *BB : Region)290 for (Instruction &I : BB->instructionsWithoutDebug())291 if (&I != BB->getTerminator())292 Benefit +=293 TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize);294 295 return Benefit;296}297 298/// Get the penalty score for outlining \p Region.299static int getOutliningPenalty(ArrayRef<BasicBlock *> Region,300 unsigned NumInputs, unsigned NumOutputs) {301 int Penalty = SplittingThreshold;302 LLVM_DEBUG(dbgs() << "Applying penalty for splitting: " << Penalty << "\n");303 304 // If the splitting threshold is set at or below zero, skip the usual305 // profitability check.306 if (SplittingThreshold <= 0)307 return Penalty;308 309 // Find the number of distinct exit blocks for the region. Use a conservative310 // check to determine whether control returns from the region.311 bool NoBlocksReturn = true;312 SmallPtrSet<BasicBlock *, 2> SuccsOutsideRegion;313 for (BasicBlock *BB : Region) {314 // If a block has no successors, only assume it does not return if it's315 // unreachable.316 if (succ_empty(BB)) {317 NoBlocksReturn &= isa<UnreachableInst>(BB->getTerminator());318 continue;319 }320 321 for (BasicBlock *SuccBB : successors(BB)) {322 if (!is_contained(Region, SuccBB)) {323 NoBlocksReturn = false;324 SuccsOutsideRegion.insert(SuccBB);325 }326 }327 }328 329 // Count the number of phis in exit blocks with >= 2 incoming values from the330 // outlining region. These phis are split (\ref severSplitPHINodesOfExits),331 // and new outputs are created to supply the split phis. CodeExtractor can't332 // report these new outputs until extraction begins, but it's important to333 // factor the cost of the outputs into the cost calculation.334 unsigned NumSplitExitPhis = 0;335 for (BasicBlock *ExitBB : SuccsOutsideRegion) {336 for (PHINode &PN : ExitBB->phis()) {337 // Find all incoming values from the outlining region.338 int NumIncomingVals = 0;339 for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i)340 if (llvm::is_contained(Region, PN.getIncomingBlock(i))) {341 ++NumIncomingVals;342 if (NumIncomingVals > 1) {343 ++NumSplitExitPhis;344 break;345 }346 }347 }348 }349 350 // Apply a penalty for calling the split function. Factor in the cost of351 // materializing all of the parameters.352 int NumOutputsAndSplitPhis = NumOutputs + NumSplitExitPhis;353 int NumParams = NumInputs + NumOutputsAndSplitPhis;354 if (NumParams > MaxParametersForSplit) {355 LLVM_DEBUG(dbgs() << NumInputs << " inputs and " << NumOutputsAndSplitPhis356 << " outputs exceeds parameter limit ("357 << MaxParametersForSplit << ")\n");358 return std::numeric_limits<int>::max();359 }360 const int CostForArgMaterialization = 2 * TargetTransformInfo::TCC_Basic;361 LLVM_DEBUG(dbgs() << "Applying penalty for: " << NumParams << " params\n");362 Penalty += CostForArgMaterialization * NumParams;363 364 // Apply the typical code size cost for an output alloca and its associated365 // reload in the caller. Also penalize the associated store in the callee.366 LLVM_DEBUG(dbgs() << "Applying penalty for: " << NumOutputsAndSplitPhis367 << " outputs/split phis\n");368 const int CostForRegionOutput = 3 * TargetTransformInfo::TCC_Basic;369 Penalty += CostForRegionOutput * NumOutputsAndSplitPhis;370 371 // Apply a `noreturn` bonus.372 if (NoBlocksReturn) {373 LLVM_DEBUG(dbgs() << "Applying bonus for: " << Region.size()374 << " non-returning terminators\n");375 Penalty -= Region.size();376 }377 378 // Apply a penalty for having more than one successor outside of the region.379 // This penalty accounts for the switch needed in the caller.380 if (SuccsOutsideRegion.size() > 1) {381 LLVM_DEBUG(dbgs() << "Applying penalty for: " << SuccsOutsideRegion.size()382 << " non-region successors\n");383 Penalty += (SuccsOutsideRegion.size() - 1) * TargetTransformInfo::TCC_Basic;384 }385 386 return Penalty;387}388 389// Determine if it is beneficial to split the \p Region.390bool HotColdSplitting::isSplittingBeneficial(CodeExtractor &CE,391 const BlockSequence &Region,392 TargetTransformInfo &TTI) {393 assert(!Region.empty());394 395 // Perform a simple cost/benefit analysis to decide whether or not to permit396 // splitting.397 SetVector<Value *> Inputs, Outputs, Sinks;398 CE.findInputsOutputs(Inputs, Outputs, Sinks);399 InstructionCost OutliningBenefit = getOutliningBenefit(Region, TTI);400 int OutliningPenalty =401 getOutliningPenalty(Region, Inputs.size(), Outputs.size());402 LLVM_DEBUG(dbgs() << "Split profitability: benefit = " << OutliningBenefit403 << ", penalty = " << OutliningPenalty << "\n");404 if (!OutliningBenefit.isValid() || OutliningBenefit <= OutliningPenalty)405 return false;406 407 return true;408}409 410// Split the single \p EntryPoint cold region. \p CE is the region code411// extractor.412Function *HotColdSplitting::extractColdRegion(413 BasicBlock &EntryPoint, CodeExtractor &CE,414 const CodeExtractorAnalysisCache &CEAC, BlockFrequencyInfo *BFI,415 TargetTransformInfo &TTI, OptimizationRemarkEmitter &ORE) {416 Function *OrigF = EntryPoint.getParent();417 if (Function *OutF = CE.extractCodeRegion(CEAC)) {418 User *U = *OutF->user_begin();419 CallInst *CI = cast<CallInst>(U);420 NumColdRegionsOutlined++;421 if (TTI.useColdCCForColdCall(*OutF)) {422 OutF->setCallingConv(CallingConv::Cold);423 CI->setCallingConv(CallingConv::Cold);424 }425 CI->setIsNoInline();426 427 if (EnableColdSection)428 OutF->setSection(ColdSectionName);429 else {430 if (OrigF->hasSection())431 OutF->setSection(OrigF->getSection());432 }433 434 markFunctionCold(*OutF, BFI != nullptr);435 436 LLVM_DEBUG(llvm::dbgs() << "Outlined Region: " << *OutF);437 ORE.emit([&]() {438 return OptimizationRemark(DEBUG_TYPE, "HotColdSplit",439 &*EntryPoint.begin())440 << ore::NV("Original", OrigF) << " split cold code into "441 << ore::NV("Split", OutF);442 });443 return OutF;444 }445 446 ORE.emit([&]() {447 return OptimizationRemarkMissed(DEBUG_TYPE, "ExtractFailed",448 &*EntryPoint.begin())449 << "Failed to extract region at block "450 << ore::NV("Block", &EntryPoint);451 });452 return nullptr;453}454 455/// A pair of (basic block, score).456using BlockTy = std::pair<BasicBlock *, unsigned>;457 458namespace {459/// A maximal outlining region. This contains all blocks post-dominated by a460/// sink block, the sink block itself, and all blocks dominated by the sink.461/// If sink-predecessors and sink-successors cannot be extracted in one region,462/// the static constructor returns a list of suitable extraction regions.463class OutliningRegion {464 /// A list of (block, score) pairs. A block's score is non-zero iff it's a465 /// viable sub-region entry point. Blocks with higher scores are better entry466 /// points (i.e. they are more distant ancestors of the sink block).467 SmallVector<BlockTy, 0> Blocks = {};468 469 /// The suggested entry point into the region. If the region has multiple470 /// entry points, all blocks within the region may not be reachable from this471 /// entry point.472 BasicBlock *SuggestedEntryPoint = nullptr;473 474 /// Whether the entire function is cold.475 bool EntireFunctionCold = false;476 477 /// If \p BB is a viable entry point, return \p Score. Return 0 otherwise.478 static unsigned getEntryPointScore(BasicBlock &BB, unsigned Score) {479 return mayExtractBlock(BB) ? Score : 0;480 }481 482 /// These scores should be lower than the score for predecessor blocks,483 /// because regions starting at predecessor blocks are typically larger.484 static constexpr unsigned ScoreForSuccBlock = 1;485 static constexpr unsigned ScoreForSinkBlock = 1;486 487 OutliningRegion(const OutliningRegion &) = delete;488 OutliningRegion &operator=(const OutliningRegion &) = delete;489 490public:491 OutliningRegion() = default;492 OutliningRegion(OutliningRegion &&) = default;493 OutliningRegion &operator=(OutliningRegion &&) = default;494 495 static std::vector<OutliningRegion> create(BasicBlock &SinkBB,496 const DominatorTree &DT,497 const PostDominatorTree &PDT) {498 std::vector<OutliningRegion> Regions;499 SmallPtrSet<BasicBlock *, 4> RegionBlocks;500 501 Regions.emplace_back();502 OutliningRegion *ColdRegion = &Regions.back();503 504 auto addBlockToRegion = [&](BasicBlock *BB, unsigned Score) {505 RegionBlocks.insert(BB);506 ColdRegion->Blocks.emplace_back(BB, Score);507 };508 509 // The ancestor farthest-away from SinkBB, and also post-dominated by it.510 unsigned SinkScore = getEntryPointScore(SinkBB, ScoreForSinkBlock);511 ColdRegion->SuggestedEntryPoint = (SinkScore > 0) ? &SinkBB : nullptr;512 unsigned BestScore = SinkScore;513 514 // Visit SinkBB's ancestors using inverse DFS.515 auto PredIt = ++idf_begin(&SinkBB);516 auto PredEnd = idf_end(&SinkBB);517 while (PredIt != PredEnd) {518 BasicBlock &PredBB = **PredIt;519 bool SinkPostDom = PDT.dominates(&SinkBB, &PredBB);520 521 // If the predecessor is cold and has no predecessors, the entire522 // function must be cold.523 if (SinkPostDom && pred_empty(&PredBB)) {524 ColdRegion->EntireFunctionCold = true;525 return Regions;526 }527 528 // If SinkBB does not post-dominate a predecessor, do not mark the529 // predecessor (or any of its predecessors) cold.530 if (!SinkPostDom || !mayExtractBlock(PredBB)) {531 PredIt.skipChildren();532 continue;533 }534 535 // Keep track of the post-dominated ancestor farthest away from the sink.536 // The path length is always >= 2, ensuring that predecessor blocks are537 // considered as entry points before the sink block.538 unsigned PredScore = getEntryPointScore(PredBB, PredIt.getPathLength());539 if (PredScore > BestScore) {540 ColdRegion->SuggestedEntryPoint = &PredBB;541 BestScore = PredScore;542 }543 544 addBlockToRegion(&PredBB, PredScore);545 ++PredIt;546 }547 548 // If the sink can be added to the cold region, do so. It's considered as549 // an entry point before any sink-successor blocks.550 //551 // Otherwise, split cold sink-successor blocks using a separate region.552 // This satisfies the requirement that all extraction blocks other than the553 // first have predecessors within the extraction region.554 if (mayExtractBlock(SinkBB)) {555 addBlockToRegion(&SinkBB, SinkScore);556 if (pred_empty(&SinkBB)) {557 ColdRegion->EntireFunctionCold = true;558 return Regions;559 }560 } else {561 Regions.emplace_back();562 ColdRegion = &Regions.back();563 BestScore = 0;564 }565 566 // Find all successors of SinkBB dominated by SinkBB using DFS.567 auto SuccIt = ++df_begin(&SinkBB);568 auto SuccEnd = df_end(&SinkBB);569 while (SuccIt != SuccEnd) {570 BasicBlock &SuccBB = **SuccIt;571 bool SinkDom = DT.dominates(&SinkBB, &SuccBB);572 573 // Don't allow the backwards & forwards DFSes to mark the same block.574 bool DuplicateBlock = RegionBlocks.count(&SuccBB);575 576 // If SinkBB does not dominate a successor, do not mark the successor (or577 // any of its successors) cold.578 if (DuplicateBlock || !SinkDom || !mayExtractBlock(SuccBB)) {579 SuccIt.skipChildren();580 continue;581 }582 583 unsigned SuccScore = getEntryPointScore(SuccBB, ScoreForSuccBlock);584 if (SuccScore > BestScore) {585 ColdRegion->SuggestedEntryPoint = &SuccBB;586 BestScore = SuccScore;587 }588 589 addBlockToRegion(&SuccBB, SuccScore);590 ++SuccIt;591 }592 593 return Regions;594 }595 596 /// Whether this region has nothing to extract.597 bool empty() const { return !SuggestedEntryPoint; }598 599 /// The blocks in this region.600 ArrayRef<std::pair<BasicBlock *, unsigned>> blocks() const { return Blocks; }601 602 /// Whether the entire function containing this region is cold.603 bool isEntireFunctionCold() const { return EntireFunctionCold; }604 605 /// Remove a sub-region from this region and return it as a block sequence.606 BlockSequence takeSingleEntrySubRegion(DominatorTree &DT) {607 assert(!empty() && !isEntireFunctionCold() && "Nothing to extract");608 609 // Remove blocks dominated by the suggested entry point from this region.610 // During the removal, identify the next best entry point into the region.611 // Ensure that the first extracted block is the suggested entry point.612 BlockSequence SubRegion = {SuggestedEntryPoint};613 BasicBlock *NextEntryPoint = nullptr;614 unsigned NextScore = 0;615 auto RegionEndIt = Blocks.end();616 auto RegionStartIt = remove_if(Blocks, [&](const BlockTy &Block) {617 BasicBlock *BB = Block.first;618 unsigned Score = Block.second;619 bool InSubRegion =620 BB == SuggestedEntryPoint || DT.dominates(SuggestedEntryPoint, BB);621 if (!InSubRegion && Score > NextScore) {622 NextEntryPoint = BB;623 NextScore = Score;624 }625 if (InSubRegion && BB != SuggestedEntryPoint)626 SubRegion.push_back(BB);627 return InSubRegion;628 });629 Blocks.erase(RegionStartIt, RegionEndIt);630 631 // Update the suggested entry point.632 SuggestedEntryPoint = NextEntryPoint;633 634 return SubRegion;635 }636};637} // namespace638 639bool HotColdSplitting::outlineColdRegions(Function &F, bool HasProfileSummary) {640 // The set of cold blocks outlined.641 SmallPtrSet<BasicBlock *, 4> ColdBlocks;642 643 // The set of cold blocks cannot be outlined.644 SmallPtrSet<BasicBlock *, 4> CannotBeOutlinedColdBlocks;645 646 // Set of cold blocks obtained with RPOT.647 SmallPtrSet<BasicBlock *, 4> AnnotatedColdBlocks;648 649 // The worklist of non-intersecting regions left to outline. The first member650 // of the pair is the entry point into the region to be outlined.651 SmallVector<std::pair<BasicBlock *, CodeExtractor>, 2> OutliningWorklist;652 653 // Set up an RPO traversal. Experimentally, this performs better (outlines654 // more) than a PO traversal, because we prevent region overlap by keeping655 // the first region to contain a block.656 ReversePostOrderTraversal<Function *> RPOT(&F);657 658 // Calculate domtrees lazily. This reduces compile-time significantly.659 std::unique_ptr<DominatorTree> DT;660 std::unique_ptr<PostDominatorTree> PDT;661 662 // Calculate BFI lazily (it's only used to query ProfileSummaryInfo). This663 // reduces compile-time significantly. TODO: When we *do* use BFI, we should664 // be able to salvage its domtrees instead of recomputing them.665 BlockFrequencyInfo *BFI = nullptr;666 if (HasProfileSummary)667 BFI = GetBFI(F);668 669 TargetTransformInfo &TTI = GetTTI(F);670 OptimizationRemarkEmitter &ORE = (*GetORE)(F);671 AssumptionCache *AC = LookupAC(F);672 auto ColdProbThresh = TTI.getPredictableBranchThreshold().getCompl();673 674 if (ColdBranchProbDenom.getNumOccurrences())675 ColdProbThresh = BranchProbability(1, ColdBranchProbDenom.getValue());676 677 unsigned OutlinedFunctionID = 1;678 // Find all cold regions.679 for (BasicBlock *BB : RPOT) {680 // This block is already part of some outlining region.681 if (ColdBlocks.count(BB))682 continue;683 684 // This block is already part of some region cannot be outlined.685 if (CannotBeOutlinedColdBlocks.count(BB))686 continue;687 688 if (!isBasicBlockCold(BB, ColdProbThresh, AnnotatedColdBlocks, BFI))689 continue;690 691 LLVM_DEBUG({692 dbgs() << "Found a cold block:\n";693 BB->dump();694 });695 696 if (!DT)697 DT = std::make_unique<DominatorTree>(F);698 if (!PDT)699 PDT = std::make_unique<PostDominatorTree>(F);700 701 auto Regions = OutliningRegion::create(*BB, *DT, *PDT);702 for (OutliningRegion &Region : Regions) {703 if (Region.empty())704 continue;705 706 if (Region.isEntireFunctionCold()) {707 LLVM_DEBUG(dbgs() << "Entire function is cold\n");708 return markFunctionCold(F);709 }710 711 do {712 BlockSequence SubRegion = Region.takeSingleEntrySubRegion(*DT);713 LLVM_DEBUG({714 dbgs() << "Hot/cold splitting attempting to outline these blocks:\n";715 for (BasicBlock *BB : SubRegion)716 BB->dump();717 });718 719 // TODO: Pass BFI and BPI to update profile information.720 CodeExtractor CE(721 SubRegion, &*DT, /* AggregateArgs */ false, /* BFI */ nullptr,722 /* BPI */ nullptr, AC, /* AllowVarArgs */ false,723 /* AllowAlloca */ false, /* AllocaBlock */ nullptr,724 /* Suffix */ "cold." + std::to_string(OutlinedFunctionID));725 726 if (CE.isEligible() && isSplittingBeneficial(CE, SubRegion, TTI) &&727 // If this outlining region intersects with another, drop the new728 // region.729 //730 // TODO: It's theoretically possible to outline more by only keeping731 // the largest region which contains a block, but the extra732 // bookkeeping to do this is tricky/expensive.733 none_of(SubRegion, [&](BasicBlock *Block) {734 return ColdBlocks.contains(Block);735 })) {736 ColdBlocks.insert_range(SubRegion);737 738 LLVM_DEBUG({739 for (auto *Block : SubRegion)740 dbgs() << " contains cold block:" << Block->getName() << "\n";741 });742 743 OutliningWorklist.emplace_back(744 std::make_pair(SubRegion[0], std::move(CE)));745 ++OutlinedFunctionID;746 } else {747 // The cold block region cannot be outlined.748 for (auto *Block : SubRegion)749 if ((DT->dominates(BB, Block) && PDT->dominates(Block, BB)) ||750 (PDT->dominates(BB, Block) && DT->dominates(Block, BB)))751 // Will skip this cold block in the loop to save the compile time752 CannotBeOutlinedColdBlocks.insert(Block);753 }754 } while (!Region.empty());755 756 ++NumColdRegionsFound;757 }758 }759 760 if (OutliningWorklist.empty())761 return false;762 763 // Outline single-entry cold regions, splitting up larger regions as needed.764 // Cache and recycle the CodeExtractor analysis to avoid O(n^2) compile-time.765 CodeExtractorAnalysisCache CEAC(F);766 for (auto &BCE : OutliningWorklist) {767 Function *Outlined =768 extractColdRegion(*BCE.first, BCE.second, CEAC, BFI, TTI, ORE);769 assert(Outlined && "Should be outlined");770 (void)Outlined;771 }772 773 return true;774}775 776bool HotColdSplitting::run(Module &M) {777 bool Changed = false;778 bool HasProfileSummary = (M.getProfileSummary(/* IsCS */ false) != nullptr);779 for (Function &F : M) {780 // Do not touch declarations.781 if (F.isDeclaration())782 continue;783 784 // Do not modify `optnone` functions.785 if (F.hasOptNone())786 continue;787 788 // Detect inherently cold functions and mark them as such.789 if (isFunctionCold(F)) {790 Changed |= markFunctionCold(F);791 continue;792 }793 794 if (!shouldOutlineFrom(F)) {795 LLVM_DEBUG(llvm::dbgs() << "Skipping " << F.getName() << "\n");796 continue;797 }798 799 LLVM_DEBUG(llvm::dbgs() << "Outlining in " << F.getName() << "\n");800 Changed |= outlineColdRegions(F, HasProfileSummary);801 }802 return Changed;803}804 805PreservedAnalyses806HotColdSplittingPass::run(Module &M, ModuleAnalysisManager &AM) {807 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();808 809 auto LookupAC = [&FAM](Function &F) -> AssumptionCache * {810 return FAM.getCachedResult<AssumptionAnalysis>(F);811 };812 813 auto GBFI = [&FAM](Function &F) {814 return &FAM.getResult<BlockFrequencyAnalysis>(F);815 };816 817 std::function<TargetTransformInfo &(Function &)> GTTI =818 [&FAM](Function &F) -> TargetTransformInfo & {819 return FAM.getResult<TargetIRAnalysis>(F);820 };821 822 std::unique_ptr<OptimizationRemarkEmitter> ORE;823 std::function<OptimizationRemarkEmitter &(Function &)> GetORE =824 [&ORE](Function &F) -> OptimizationRemarkEmitter & {825 ORE.reset(new OptimizationRemarkEmitter(&F));826 return *ORE;827 };828 829 ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(M);830 831 if (HotColdSplitting(PSI, GBFI, GTTI, &GetORE, LookupAC).run(M))832 return PreservedAnalyses::none();833 return PreservedAnalyses::all();834}835