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