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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// 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 into 12 /// separate functions. 13 /// 14 /// When the splitting pass finds a cold block (referred to as "the sink"), it 15 /// grows a maximal cold region around that block. The maximal region contains 16 /// all blocks (post-)dominated by the sink [*]. In theory, these blocks are as 17 /// cold as the sink. Once a region is found, it's split out of the original 18 /// function provided it's profitable to do so. 19 /// 20 /// [*] In practice, there is some added complexity because some blocks are not 21 /// 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/AliasAnalysis.h" 33 #include "llvm/Analysis/BlockFrequencyInfo.h" 34 #include "llvm/Analysis/BranchProbabilityInfo.h" 35 #include "llvm/Analysis/CFG.h" 36 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 37 #include "llvm/Analysis/PostDominators.h" 38 #include "llvm/Analysis/ProfileSummaryInfo.h" 39 #include "llvm/Analysis/TargetTransformInfo.h" 40 #include "llvm/IR/BasicBlock.h" 41 #include "llvm/IR/CFG.h" 42 #include "llvm/IR/DataLayout.h" 43 #include "llvm/IR/DiagnosticInfo.h" 44 #include "llvm/IR/Dominators.h" 45 #include "llvm/IR/Function.h" 46 #include "llvm/IR/Instruction.h" 47 #include "llvm/IR/Instructions.h" 48 #include "llvm/IR/IntrinsicInst.h" 49 #include "llvm/IR/Metadata.h" 50 #include "llvm/IR/Module.h" 51 #include "llvm/IR/PassManager.h" 52 #include "llvm/IR/Type.h" 53 #include "llvm/IR/Use.h" 54 #include "llvm/IR/User.h" 55 #include "llvm/IR/Value.h" 56 #include "llvm/InitializePasses.h" 57 #include "llvm/Pass.h" 58 #include "llvm/Support/BlockFrequency.h" 59 #include "llvm/Support/BranchProbability.h" 60 #include "llvm/Support/CommandLine.h" 61 #include "llvm/Support/Debug.h" 62 #include "llvm/Support/raw_ostream.h" 63 #include "llvm/Transforms/IPO.h" 64 #include "llvm/Transforms/Scalar.h" 65 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 66 #include "llvm/Transforms/Utils/Cloning.h" 67 #include "llvm/Transforms/Utils/CodeExtractor.h" 68 #include "llvm/Transforms/Utils/Local.h" 69 #include "llvm/Transforms/Utils/ValueMapper.h" 70 #include <algorithm> 71 #include <cassert> 72 73 #define DEBUG_TYPE "hotcoldsplit" 74 75 STATISTIC(NumColdRegionsFound, "Number of cold regions found."); 76 STATISTIC(NumColdRegionsOutlined, "Number of cold regions outlined."); 77 78 using namespace llvm; 79 80 static cl::opt<bool> EnableStaticAnalyis("hot-cold-static-analysis", 81 cl::init(true), cl::Hidden); 82 83 static cl::opt<int> 84 SplittingThreshold("hotcoldsplit-threshold", cl::init(2), cl::Hidden, 85 cl::desc("Base penalty for splitting cold code (as a " 86 "multiple of TCC_Basic)")); 87 88 namespace { 89 // Same as blockEndsInUnreachable in CodeGen/BranchFolding.cpp. Do not modify 90 // this function unless you modify the MBB version as well. 91 // 92 /// A no successor, non-return block probably ends in unreachable and is cold. 93 /// Also consider a block that ends in an indirect branch to be a return block, 94 /// since many targets use plain indirect branches to return. 95 bool blockEndsInUnreachable(const BasicBlock &BB) { 96 if (!succ_empty(&BB)) 97 return false; 98 if (BB.empty()) 99 return true; 100 const Instruction *I = BB.getTerminator(); 101 return !(isa<ReturnInst>(I) || isa<IndirectBrInst>(I)); 102 } 103 104 bool unlikelyExecuted(BasicBlock &BB) { 105 // Exception handling blocks are unlikely executed. 106 if (BB.isEHPad() || isa<ResumeInst>(BB.getTerminator())) 107 return true; 108 109 // The block is cold if it calls/invokes a cold function. However, do not 110 // mark sanitizer traps as cold. 111 for (Instruction &I : BB) 112 if (auto *CB = dyn_cast<CallBase>(&I)) 113 if (CB->hasFnAttr(Attribute::Cold) && !CB->getMetadata("nosanitize")) 114 return true; 115 116 // The block is cold if it has an unreachable terminator, unless it's 117 // preceded by a call to a (possibly warm) noreturn call (e.g. longjmp). 118 if (blockEndsInUnreachable(BB)) { 119 if (auto *CI = 120 dyn_cast_or_null<CallInst>(BB.getTerminator()->getPrevNode())) 121 if (CI->hasFnAttr(Attribute::NoReturn)) 122 return false; 123 return true; 124 } 125 126 return false; 127 } 128 129 /// Check whether it's safe to outline \p BB. 130 static bool mayExtractBlock(const BasicBlock &BB) { 131 // EH pads are unsafe to outline because doing so breaks EH type tables. It 132 // follows that invoke instructions cannot be extracted, because CodeExtractor 133 // requires unwind destinations to be within the extraction region. 134 // 135 // Resumes that are not reachable from a cleanup landing pad are considered to 136 // be unreachable. It’s not safe to split them out either. 137 auto Term = BB.getTerminator(); 138 return !BB.hasAddressTaken() && !BB.isEHPad() && !isa<InvokeInst>(Term) && 139 !isa<ResumeInst>(Term); 140 } 141 142 /// Mark \p F cold. Based on this assumption, also optimize it for minimum size. 143 /// If \p UpdateEntryCount is true (set when this is a new split function and 144 /// module has profile data), set entry count to 0 to ensure treated as cold. 145 /// Return true if the function is changed. 146 static bool markFunctionCold(Function &F, bool UpdateEntryCount = false) { 147 assert(!F.hasOptNone() && "Can't mark this cold"); 148 bool Changed = false; 149 if (!F.hasFnAttribute(Attribute::Cold)) { 150 F.addFnAttr(Attribute::Cold); 151 Changed = true; 152 } 153 if (!F.hasFnAttribute(Attribute::MinSize)) { 154 F.addFnAttr(Attribute::MinSize); 155 Changed = true; 156 } 157 if (UpdateEntryCount) { 158 // Set the entry count to 0 to ensure it is placed in the unlikely text 159 // section when function sections are enabled. 160 F.setEntryCount(0); 161 Changed = true; 162 } 163 164 return Changed; 165 } 166 167 class HotColdSplittingLegacyPass : public ModulePass { 168 public: 169 static char ID; 170 HotColdSplittingLegacyPass() : ModulePass(ID) { 171 initializeHotColdSplittingLegacyPassPass(*PassRegistry::getPassRegistry()); 172 } 173 174 void getAnalysisUsage(AnalysisUsage &AU) const override { 175 AU.addRequired<BlockFrequencyInfoWrapperPass>(); 176 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 177 AU.addRequired<TargetTransformInfoWrapperPass>(); 178 AU.addUsedIfAvailable<AssumptionCacheTracker>(); 179 } 180 181 bool runOnModule(Module &M) override; 182 }; 183 184 } // end anonymous namespace 185 186 /// Check whether \p F is inherently cold. 187 bool HotColdSplitting::isFunctionCold(const Function &F) const { 188 if (F.hasFnAttribute(Attribute::Cold)) 189 return true; 190 191 if (F.getCallingConv() == CallingConv::Cold) 192 return true; 193 194 if (PSI->isFunctionEntryCold(&F)) 195 return true; 196 197 return false; 198 } 199 200 // Returns false if the function should not be considered for hot-cold split 201 // optimization. 202 bool HotColdSplitting::shouldOutlineFrom(const Function &F) const { 203 if (F.hasFnAttribute(Attribute::AlwaysInline)) 204 return false; 205 206 if (F.hasFnAttribute(Attribute::NoInline)) 207 return false; 208 209 // A function marked `noreturn` may contain unreachable terminators: these 210 // should not be considered cold, as the function may be a trampoline. 211 if (F.hasFnAttribute(Attribute::NoReturn)) 212 return false; 213 214 if (F.hasFnAttribute(Attribute::SanitizeAddress) || 215 F.hasFnAttribute(Attribute::SanitizeHWAddress) || 216 F.hasFnAttribute(Attribute::SanitizeThread) || 217 F.hasFnAttribute(Attribute::SanitizeMemory)) 218 return false; 219 220 return true; 221 } 222 223 /// Get the benefit score of outlining \p Region. 224 static int getOutliningBenefit(ArrayRef<BasicBlock *> Region, 225 TargetTransformInfo &TTI) { 226 // Sum up the code size costs of non-terminator instructions. Tight coupling 227 // with \ref getOutliningPenalty is needed to model the costs of terminators. 228 int Benefit = 0; 229 for (BasicBlock *BB : Region) 230 for (Instruction &I : BB->instructionsWithoutDebug()) 231 if (&I != BB->getTerminator()) 232 Benefit += 233 TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize); 234 235 return Benefit; 236 } 237 238 /// Get the penalty score for outlining \p Region. 239 static int getOutliningPenalty(ArrayRef<BasicBlock *> Region, 240 unsigned NumInputs, unsigned NumOutputs) { 241 int Penalty = SplittingThreshold; 242 LLVM_DEBUG(dbgs() << "Applying penalty for splitting: " << Penalty << "\n"); 243 244 // If the splitting threshold is set at or below zero, skip the usual 245 // profitability check. 246 if (SplittingThreshold <= 0) 247 return Penalty; 248 249 // The typical code size cost for materializing an argument for the outlined 250 // call. 251 LLVM_DEBUG(dbgs() << "Applying penalty for: " << NumInputs << " inputs\n"); 252 const int CostForArgMaterialization = TargetTransformInfo::TCC_Basic; 253 Penalty += CostForArgMaterialization * NumInputs; 254 255 // The typical code size cost for an output alloca, its associated store, and 256 // its associated reload. 257 LLVM_DEBUG(dbgs() << "Applying penalty for: " << NumOutputs << " outputs\n"); 258 const int CostForRegionOutput = 3 * TargetTransformInfo::TCC_Basic; 259 Penalty += CostForRegionOutput * NumOutputs; 260 261 // Find the number of distinct exit blocks for the region. Use a conservative 262 // check to determine whether control returns from the region. 263 bool NoBlocksReturn = true; 264 SmallPtrSet<BasicBlock *, 2> SuccsOutsideRegion; 265 for (BasicBlock *BB : Region) { 266 // If a block has no successors, only assume it does not return if it's 267 // unreachable. 268 if (succ_empty(BB)) { 269 NoBlocksReturn &= isa<UnreachableInst>(BB->getTerminator()); 270 continue; 271 } 272 273 for (BasicBlock *SuccBB : successors(BB)) { 274 if (find(Region, SuccBB) == Region.end()) { 275 NoBlocksReturn = false; 276 SuccsOutsideRegion.insert(SuccBB); 277 } 278 } 279 } 280 281 // Apply a `noreturn` bonus. 282 if (NoBlocksReturn) { 283 LLVM_DEBUG(dbgs() << "Applying bonus for: " << Region.size() 284 << " non-returning terminators\n"); 285 Penalty -= Region.size(); 286 } 287 288 // Apply a penalty for having more than one successor outside of the region. 289 // This penalty accounts for the switch needed in the caller. 290 if (!SuccsOutsideRegion.empty()) { 291 LLVM_DEBUG(dbgs() << "Applying penalty for: " << SuccsOutsideRegion.size() 292 << " non-region successors\n"); 293 Penalty += (SuccsOutsideRegion.size() - 1) * TargetTransformInfo::TCC_Basic; 294 } 295 296 return Penalty; 297 } 298 299 Function *HotColdSplitting::extractColdRegion( 300 const BlockSequence &Region, const CodeExtractorAnalysisCache &CEAC, 301 DominatorTree &DT, BlockFrequencyInfo *BFI, TargetTransformInfo &TTI, 302 OptimizationRemarkEmitter &ORE, AssumptionCache *AC, unsigned Count) { 303 assert(!Region.empty()); 304 305 // TODO: Pass BFI and BPI to update profile information. 306 CodeExtractor CE(Region, &DT, /* AggregateArgs */ false, /* BFI */ nullptr, 307 /* BPI */ nullptr, AC, /* AllowVarArgs */ false, 308 /* AllowAlloca */ false, 309 /* Suffix */ "cold." + std::to_string(Count)); 310 311 // Perform a simple cost/benefit analysis to decide whether or not to permit 312 // splitting. 313 SetVector<Value *> Inputs, Outputs, Sinks; 314 CE.findInputsOutputs(Inputs, Outputs, Sinks); 315 int OutliningBenefit = getOutliningBenefit(Region, TTI); 316 int OutliningPenalty = 317 getOutliningPenalty(Region, Inputs.size(), Outputs.size()); 318 LLVM_DEBUG(dbgs() << "Split profitability: benefit = " << OutliningBenefit 319 << ", penalty = " << OutliningPenalty << "\n"); 320 if (OutliningBenefit <= OutliningPenalty) 321 return nullptr; 322 323 Function *OrigF = Region[0]->getParent(); 324 if (Function *OutF = CE.extractCodeRegion(CEAC)) { 325 User *U = *OutF->user_begin(); 326 CallInst *CI = cast<CallInst>(U); 327 NumColdRegionsOutlined++; 328 if (TTI.useColdCCForColdCall(*OutF)) { 329 OutF->setCallingConv(CallingConv::Cold); 330 CI->setCallingConv(CallingConv::Cold); 331 } 332 CI->setIsNoInline(); 333 334 if (OrigF->hasSection()) 335 OutF->setSection(OrigF->getSection()); 336 337 markFunctionCold(*OutF, BFI != nullptr); 338 339 LLVM_DEBUG(llvm::dbgs() << "Outlined Region: " << *OutF); 340 ORE.emit([&]() { 341 return OptimizationRemark(DEBUG_TYPE, "HotColdSplit", 342 &*Region[0]->begin()) 343 << ore::NV("Original", OrigF) << " split cold code into " 344 << ore::NV("Split", OutF); 345 }); 346 return OutF; 347 } 348 349 ORE.emit([&]() { 350 return OptimizationRemarkMissed(DEBUG_TYPE, "ExtractFailed", 351 &*Region[0]->begin()) 352 << "Failed to extract region at block " 353 << ore::NV("Block", Region.front()); 354 }); 355 return nullptr; 356 } 357 358 /// A pair of (basic block, score). 359 using BlockTy = std::pair<BasicBlock *, unsigned>; 360 361 namespace { 362 /// A maximal outlining region. This contains all blocks post-dominated by a 363 /// sink block, the sink block itself, and all blocks dominated by the sink. 364 /// If sink-predecessors and sink-successors cannot be extracted in one region, 365 /// the static constructor returns a list of suitable extraction regions. 366 class OutliningRegion { 367 /// A list of (block, score) pairs. A block's score is non-zero iff it's a 368 /// viable sub-region entry point. Blocks with higher scores are better entry 369 /// points (i.e. they are more distant ancestors of the sink block). 370 SmallVector<BlockTy, 0> Blocks = {}; 371 372 /// The suggested entry point into the region. If the region has multiple 373 /// entry points, all blocks within the region may not be reachable from this 374 /// entry point. 375 BasicBlock *SuggestedEntryPoint = nullptr; 376 377 /// Whether the entire function is cold. 378 bool EntireFunctionCold = false; 379 380 /// If \p BB is a viable entry point, return \p Score. Return 0 otherwise. 381 static unsigned getEntryPointScore(BasicBlock &BB, unsigned Score) { 382 return mayExtractBlock(BB) ? Score : 0; 383 } 384 385 /// These scores should be lower than the score for predecessor blocks, 386 /// because regions starting at predecessor blocks are typically larger. 387 static constexpr unsigned ScoreForSuccBlock = 1; 388 static constexpr unsigned ScoreForSinkBlock = 1; 389 390 OutliningRegion(const OutliningRegion &) = delete; 391 OutliningRegion &operator=(const OutliningRegion &) = delete; 392 393 public: 394 OutliningRegion() = default; 395 OutliningRegion(OutliningRegion &&) = default; 396 OutliningRegion &operator=(OutliningRegion &&) = default; 397 398 static std::vector<OutliningRegion> create(BasicBlock &SinkBB, 399 const DominatorTree &DT, 400 const PostDominatorTree &PDT) { 401 std::vector<OutliningRegion> Regions; 402 SmallPtrSet<BasicBlock *, 4> RegionBlocks; 403 404 Regions.emplace_back(); 405 OutliningRegion *ColdRegion = &Regions.back(); 406 407 auto addBlockToRegion = [&](BasicBlock *BB, unsigned Score) { 408 RegionBlocks.insert(BB); 409 ColdRegion->Blocks.emplace_back(BB, Score); 410 }; 411 412 // The ancestor farthest-away from SinkBB, and also post-dominated by it. 413 unsigned SinkScore = getEntryPointScore(SinkBB, ScoreForSinkBlock); 414 ColdRegion->SuggestedEntryPoint = (SinkScore > 0) ? &SinkBB : nullptr; 415 unsigned BestScore = SinkScore; 416 417 // Visit SinkBB's ancestors using inverse DFS. 418 auto PredIt = ++idf_begin(&SinkBB); 419 auto PredEnd = idf_end(&SinkBB); 420 while (PredIt != PredEnd) { 421 BasicBlock &PredBB = **PredIt; 422 bool SinkPostDom = PDT.dominates(&SinkBB, &PredBB); 423 424 // If the predecessor is cold and has no predecessors, the entire 425 // function must be cold. 426 if (SinkPostDom && pred_empty(&PredBB)) { 427 ColdRegion->EntireFunctionCold = true; 428 return Regions; 429 } 430 431 // If SinkBB does not post-dominate a predecessor, do not mark the 432 // predecessor (or any of its predecessors) cold. 433 if (!SinkPostDom || !mayExtractBlock(PredBB)) { 434 PredIt.skipChildren(); 435 continue; 436 } 437 438 // Keep track of the post-dominated ancestor farthest away from the sink. 439 // The path length is always >= 2, ensuring that predecessor blocks are 440 // considered as entry points before the sink block. 441 unsigned PredScore = getEntryPointScore(PredBB, PredIt.getPathLength()); 442 if (PredScore > BestScore) { 443 ColdRegion->SuggestedEntryPoint = &PredBB; 444 BestScore = PredScore; 445 } 446 447 addBlockToRegion(&PredBB, PredScore); 448 ++PredIt; 449 } 450 451 // If the sink can be added to the cold region, do so. It's considered as 452 // an entry point before any sink-successor blocks. 453 // 454 // Otherwise, split cold sink-successor blocks using a separate region. 455 // This satisfies the requirement that all extraction blocks other than the 456 // first have predecessors within the extraction region. 457 if (mayExtractBlock(SinkBB)) { 458 addBlockToRegion(&SinkBB, SinkScore); 459 if (pred_empty(&SinkBB)) { 460 ColdRegion->EntireFunctionCold = true; 461 return Regions; 462 } 463 } else { 464 Regions.emplace_back(); 465 ColdRegion = &Regions.back(); 466 BestScore = 0; 467 } 468 469 // Find all successors of SinkBB dominated by SinkBB using DFS. 470 auto SuccIt = ++df_begin(&SinkBB); 471 auto SuccEnd = df_end(&SinkBB); 472 while (SuccIt != SuccEnd) { 473 BasicBlock &SuccBB = **SuccIt; 474 bool SinkDom = DT.dominates(&SinkBB, &SuccBB); 475 476 // Don't allow the backwards & forwards DFSes to mark the same block. 477 bool DuplicateBlock = RegionBlocks.count(&SuccBB); 478 479 // If SinkBB does not dominate a successor, do not mark the successor (or 480 // any of its successors) cold. 481 if (DuplicateBlock || !SinkDom || !mayExtractBlock(SuccBB)) { 482 SuccIt.skipChildren(); 483 continue; 484 } 485 486 unsigned SuccScore = getEntryPointScore(SuccBB, ScoreForSuccBlock); 487 if (SuccScore > BestScore) { 488 ColdRegion->SuggestedEntryPoint = &SuccBB; 489 BestScore = SuccScore; 490 } 491 492 addBlockToRegion(&SuccBB, SuccScore); 493 ++SuccIt; 494 } 495 496 return Regions; 497 } 498 499 /// Whether this region has nothing to extract. 500 bool empty() const { return !SuggestedEntryPoint; } 501 502 /// The blocks in this region. 503 ArrayRef<std::pair<BasicBlock *, unsigned>> blocks() const { return Blocks; } 504 505 /// Whether the entire function containing this region is cold. 506 bool isEntireFunctionCold() const { return EntireFunctionCold; } 507 508 /// Remove a sub-region from this region and return it as a block sequence. 509 BlockSequence takeSingleEntrySubRegion(DominatorTree &DT) { 510 assert(!empty() && !isEntireFunctionCold() && "Nothing to extract"); 511 512 // Remove blocks dominated by the suggested entry point from this region. 513 // During the removal, identify the next best entry point into the region. 514 // Ensure that the first extracted block is the suggested entry point. 515 BlockSequence SubRegion = {SuggestedEntryPoint}; 516 BasicBlock *NextEntryPoint = nullptr; 517 unsigned NextScore = 0; 518 auto RegionEndIt = Blocks.end(); 519 auto RegionStartIt = remove_if(Blocks, [&](const BlockTy &Block) { 520 BasicBlock *BB = Block.first; 521 unsigned Score = Block.second; 522 bool InSubRegion = 523 BB == SuggestedEntryPoint || DT.dominates(SuggestedEntryPoint, BB); 524 if (!InSubRegion && Score > NextScore) { 525 NextEntryPoint = BB; 526 NextScore = Score; 527 } 528 if (InSubRegion && BB != SuggestedEntryPoint) 529 SubRegion.push_back(BB); 530 return InSubRegion; 531 }); 532 Blocks.erase(RegionStartIt, RegionEndIt); 533 534 // Update the suggested entry point. 535 SuggestedEntryPoint = NextEntryPoint; 536 537 return SubRegion; 538 } 539 }; 540 } // namespace 541 542 bool HotColdSplitting::outlineColdRegions(Function &F, bool HasProfileSummary) { 543 bool Changed = false; 544 545 // The set of cold blocks. 546 SmallPtrSet<BasicBlock *, 4> ColdBlocks; 547 548 // The worklist of non-intersecting regions left to outline. 549 SmallVector<OutliningRegion, 2> OutliningWorklist; 550 551 // Set up an RPO traversal. Experimentally, this performs better (outlines 552 // more) than a PO traversal, because we prevent region overlap by keeping 553 // the first region to contain a block. 554 ReversePostOrderTraversal<Function *> RPOT(&F); 555 556 // Calculate domtrees lazily. This reduces compile-time significantly. 557 std::unique_ptr<DominatorTree> DT; 558 std::unique_ptr<PostDominatorTree> PDT; 559 560 // Calculate BFI lazily (it's only used to query ProfileSummaryInfo). This 561 // reduces compile-time significantly. TODO: When we *do* use BFI, we should 562 // be able to salvage its domtrees instead of recomputing them. 563 BlockFrequencyInfo *BFI = nullptr; 564 if (HasProfileSummary) 565 BFI = GetBFI(F); 566 567 TargetTransformInfo &TTI = GetTTI(F); 568 OptimizationRemarkEmitter &ORE = (*GetORE)(F); 569 AssumptionCache *AC = LookupAC(F); 570 571 // Find all cold regions. 572 for (BasicBlock *BB : RPOT) { 573 // This block is already part of some outlining region. 574 if (ColdBlocks.count(BB)) 575 continue; 576 577 bool Cold = (BFI && PSI->isColdBlock(BB, BFI)) || 578 (EnableStaticAnalyis && unlikelyExecuted(*BB)); 579 if (!Cold) 580 continue; 581 582 LLVM_DEBUG({ 583 dbgs() << "Found a cold block:\n"; 584 BB->dump(); 585 }); 586 587 if (!DT) 588 DT = std::make_unique<DominatorTree>(F); 589 if (!PDT) 590 PDT = std::make_unique<PostDominatorTree>(F); 591 592 auto Regions = OutliningRegion::create(*BB, *DT, *PDT); 593 for (OutliningRegion &Region : Regions) { 594 if (Region.empty()) 595 continue; 596 597 if (Region.isEntireFunctionCold()) { 598 LLVM_DEBUG(dbgs() << "Entire function is cold\n"); 599 return markFunctionCold(F); 600 } 601 602 // If this outlining region intersects with another, drop the new region. 603 // 604 // TODO: It's theoretically possible to outline more by only keeping the 605 // largest region which contains a block, but the extra bookkeeping to do 606 // this is tricky/expensive. 607 bool RegionsOverlap = any_of(Region.blocks(), [&](const BlockTy &Block) { 608 return !ColdBlocks.insert(Block.first).second; 609 }); 610 if (RegionsOverlap) 611 continue; 612 613 OutliningWorklist.emplace_back(std::move(Region)); 614 ++NumColdRegionsFound; 615 } 616 } 617 618 if (OutliningWorklist.empty()) 619 return Changed; 620 621 // Outline single-entry cold regions, splitting up larger regions as needed. 622 unsigned OutlinedFunctionID = 1; 623 // Cache and recycle the CodeExtractor analysis to avoid O(n^2) compile-time. 624 CodeExtractorAnalysisCache CEAC(F); 625 do { 626 OutliningRegion Region = OutliningWorklist.pop_back_val(); 627 assert(!Region.empty() && "Empty outlining region in worklist"); 628 do { 629 BlockSequence SubRegion = Region.takeSingleEntrySubRegion(*DT); 630 LLVM_DEBUG({ 631 dbgs() << "Hot/cold splitting attempting to outline these blocks:\n"; 632 for (BasicBlock *BB : SubRegion) 633 BB->dump(); 634 }); 635 636 Function *Outlined = extractColdRegion(SubRegion, CEAC, *DT, BFI, TTI, 637 ORE, AC, OutlinedFunctionID); 638 if (Outlined) { 639 ++OutlinedFunctionID; 640 Changed = true; 641 } 642 } while (!Region.empty()); 643 } while (!OutliningWorklist.empty()); 644 645 return Changed; 646 } 647 648 bool HotColdSplitting::run(Module &M) { 649 bool Changed = false; 650 bool HasProfileSummary = (M.getProfileSummary(/* IsCS */ false) != nullptr); 651 for (auto It = M.begin(), End = M.end(); It != End; ++It) { 652 Function &F = *It; 653 654 // Do not touch declarations. 655 if (F.isDeclaration()) 656 continue; 657 658 // Do not modify `optnone` functions. 659 if (F.hasOptNone()) 660 continue; 661 662 // Detect inherently cold functions and mark them as such. 663 if (isFunctionCold(F)) { 664 Changed |= markFunctionCold(F); 665 continue; 666 } 667 668 if (!shouldOutlineFrom(F)) { 669 LLVM_DEBUG(llvm::dbgs() << "Skipping " << F.getName() << "\n"); 670 continue; 671 } 672 673 LLVM_DEBUG(llvm::dbgs() << "Outlining in " << F.getName() << "\n"); 674 Changed |= outlineColdRegions(F, HasProfileSummary); 675 } 676 return Changed; 677 } 678 679 bool HotColdSplittingLegacyPass::runOnModule(Module &M) { 680 if (skipModule(M)) 681 return false; 682 ProfileSummaryInfo *PSI = 683 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 684 auto GTTI = [this](Function &F) -> TargetTransformInfo & { 685 return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 686 }; 687 auto GBFI = [this](Function &F) { 688 return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI(); 689 }; 690 std::unique_ptr<OptimizationRemarkEmitter> ORE; 691 std::function<OptimizationRemarkEmitter &(Function &)> GetORE = 692 [&ORE](Function &F) -> OptimizationRemarkEmitter & { 693 ORE.reset(new OptimizationRemarkEmitter(&F)); 694 return *ORE.get(); 695 }; 696 auto LookupAC = [this](Function &F) -> AssumptionCache * { 697 if (auto *ACT = getAnalysisIfAvailable<AssumptionCacheTracker>()) 698 return ACT->lookupAssumptionCache(F); 699 return nullptr; 700 }; 701 702 return HotColdSplitting(PSI, GBFI, GTTI, &GetORE, LookupAC).run(M); 703 } 704 705 PreservedAnalyses 706 HotColdSplittingPass::run(Module &M, ModuleAnalysisManager &AM) { 707 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 708 709 auto LookupAC = [&FAM](Function &F) -> AssumptionCache * { 710 return FAM.getCachedResult<AssumptionAnalysis>(F); 711 }; 712 713 auto GBFI = [&FAM](Function &F) { 714 return &FAM.getResult<BlockFrequencyAnalysis>(F); 715 }; 716 717 std::function<TargetTransformInfo &(Function &)> GTTI = 718 [&FAM](Function &F) -> TargetTransformInfo & { 719 return FAM.getResult<TargetIRAnalysis>(F); 720 }; 721 722 std::unique_ptr<OptimizationRemarkEmitter> ORE; 723 std::function<OptimizationRemarkEmitter &(Function &)> GetORE = 724 [&ORE](Function &F) -> OptimizationRemarkEmitter & { 725 ORE.reset(new OptimizationRemarkEmitter(&F)); 726 return *ORE.get(); 727 }; 728 729 ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(M); 730 731 if (HotColdSplitting(PSI, GBFI, GTTI, &GetORE, LookupAC).run(M)) 732 return PreservedAnalyses::none(); 733 return PreservedAnalyses::all(); 734 } 735 736 char HotColdSplittingLegacyPass::ID = 0; 737 INITIALIZE_PASS_BEGIN(HotColdSplittingLegacyPass, "hotcoldsplit", 738 "Hot Cold Splitting", false, false) 739 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) 740 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 741 INITIALIZE_PASS_END(HotColdSplittingLegacyPass, "hotcoldsplit", 742 "Hot Cold Splitting", false, false) 743 744 ModulePass *llvm::createHotColdSplittingPass() { 745 return new HotColdSplittingLegacyPass(); 746 } 747