LLVM  10.0.0svn
HotColdSplitting.cpp
Go to the documentation of this file.
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 
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/ADT/Statistic.h"
34 #include "llvm/Analysis/CFG.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"
59 #include "llvm/Support/Debug.h"
61 #include "llvm/Transforms/IPO.h"
63 #include "llvm/Transforms/Scalar.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;
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) {
171  }
172 
173  void getAnalysisUsage(AnalysisUsage &AU) const override {
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 {
188  return true;
189 
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.
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 +=
228 
229  return Benefit;
230 }
231 
232 /// Get the penalty score for outlining \p 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,
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.
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.
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 
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 
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 
718 
719  if (HotColdSplitting(PSI, GBFI, GTTI, &GetORE, LookupAC).run(M))
720  return PreservedAnalyses::none();
721  return PreservedAnalyses::all();
722 }
723 
725 INITIALIZE_PASS_BEGIN(HotColdSplittingLegacyPass, "hotcoldsplit",
726  "Hot Cold Splitting", false, false)
729 INITIALIZE_PASS_END(HotColdSplittingLegacyPass, "hotcoldsplit",
730  "Hot Cold Splitting", false, false)
731 
733  return new HotColdSplittingLegacyPass();
734 }
INITIALIZE_PASS_BEGIN(HotColdSplittingLegacyPass, "hotcoldsplit", "Hot Cold Splitting", false, false) INITIALIZE_PASS_END(HotColdSplittingLegacyPass
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:85
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:641
Diagnostic information for missed-optimization remarks.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
DiagnosticInfoOptimizationBase::Argument NV
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool hasOptNone() const
Do not optimize this function (-O0).
Definition: Function.h:616
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
void push_back(const T &Elt)
Definition: SmallVector.h:211
Hot Cold Splitting
bool useColdCCForColdCall(Function &F) const
Return true if the input function which is cold at all call sites, should use coldcc calling conventi...
Analysis providing profile information.
This class represents a function call, abstracting a target machine&#39;s calling convention.
static cl::opt< bool > EnableStaticAnalyis("hot-cold-static-analysis", cl::init(true), cl::Hidden)
This file contains the declarations for metadata subclasses.
An immutable pass that tracks lazily created AssumptionCache objects.
Metadata * getProfileSummary(bool IsCS)
Returns profile summary metadata.
Definition: Module.cpp:541
A cache of @llvm.assume calls within a function.
Analysis pass providing the TargetTransformInfo.
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:323
F(f)
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:144
This defines the Use class.
int getInstructionCost(const Instruction *I, enum TargetCostKind kind) const
Query the cost of a specified instruction.
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:4429
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
void setEntryCount(ProfileCount Count, const DenseSet< GlobalValue::GUID > *Imports=nullptr)
Set the entry count for this function.
Definition: Function.cpp:1529
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Legacy analysis pass which computes BlockFrequencyInfo.
bool empty() const
Definition: BasicBlock.h:284
STATISTIC(NumColdRegionsFound, "Number of cold regions found.")
static bool blockEndsInUnreachable(const MachineBasicBlock *MBB)
A no successor, non-return block probably ends in unreachable and is cold.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:156
idf_iterator< T > idf_begin(const T &G)
idf_iterator< T > idf_end(const T &G)
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
df_iterator< T > df_end(const T &G)
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug() const
Return a const iterator range over the instructions in the block, skipping any debug instructions...
Definition: BasicBlock.cpp:94
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
void setIsNoInline()
Definition: InstrTypes.h:1621
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
Diagnostic information for applied optimization remarks.
Represent the analysis usage information of a pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1172
A cache for the CodeExtractor analysis.
Definition: CodeExtractor.h:46
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:116
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1205
bool succ_empty(const Instruction *I)
Definition: CFG.h:253
iterator erase(const_iterator CI)
Definition: SmallVector.h:434
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1186
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:197
size_type size() const
Definition: SmallPtrSet.h:92
A function analysis which provides an AssumptionCache.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches, switches, etc.
Definition: BasicBlock.h:396
Analysis pass which computes BlockFrequencyInfo.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
std::pair< BasicBlock *, unsigned > BlockTy
A pair of (basic block, score).
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
void initializeHotColdSplittingLegacyPassPass(PassRegistry &)
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
static cl::opt< int > SplittingThreshold("hotcoldsplit-threshold", cl::init(2), cl::Hidden, cl::desc("Base penalty for splitting cold code (as a " "multiple of TCC_Basic)"))
CallingConv::ID getCallingConv() const
getCallingConv()/setCallingConv(CC) - These method get and set the calling convention of this functio...
Definition: Function.h:212
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:248
Module.h This file contains the declarations for the Module class.
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static int getOutliningBenefit(ArrayRef< BasicBlock *> Region, TargetTransformInfo &TTI)
Get the benefit score of outlining Region.
df_iterator< T > df_begin(const T &G)
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
iterator end()
Definition: Module.h:600
ModulePass * createHotColdSplittingPass()
createHotColdSplittingPass - This pass outlines cold blocks into a separate function(s).
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
static int getOutliningPenalty(ArrayRef< BasicBlock *> Region, unsigned NumInputs, unsigned NumOutputs)
Get the penalty score for outlining Region.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
#define I(x, y, z)
Definition: MD5.cpp:58
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
iterator begin()
Definition: Module.h:598
const std::string to_string(const T &Value)
Definition: ScopedPrinter.h:61
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:231
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:396
The cost of a typical &#39;add&#39; instruction.
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:411
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
#define DEBUG_TYPE
succ_range successors(Instruction *I)
Definition: CFG.h:259
hotcoldsplit
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
Definition: Function.h:229
A container for analyses that lazily runs them and caches their results.
This pass exposes codegen information to IR-level passes.
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
The optimization diagnostic interface.
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:1044