LLVM 19.0.0git
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
31#include "llvm/ADT/Statistic.h"
38#include "llvm/IR/BasicBlock.h"
39#include "llvm/IR/CFG.h"
41#include "llvm/IR/Dominators.h"
42#include "llvm/IR/Function.h"
43#include "llvm/IR/Instruction.h"
45#include "llvm/IR/Module.h"
46#include "llvm/IR/PassManager.h"
48#include "llvm/IR/User.h"
49#include "llvm/IR/Value.h"
51#include "llvm/Support/Debug.h"
53#include "llvm/Transforms/IPO.h"
55#include <algorithm>
56#include <cassert>
57#include <limits>
58#include <string>
59
60#define DEBUG_TYPE "hotcoldsplit"
61
62STATISTIC(NumColdRegionsFound, "Number of cold regions found.");
63STATISTIC(NumColdRegionsOutlined, "Number of cold regions outlined.");
64
65using namespace llvm;
66
67static cl::opt<bool> EnableStaticAnalysis("hot-cold-static-analysis",
68 cl::init(true), cl::Hidden);
69
70static cl::opt<int>
71 SplittingThreshold("hotcoldsplit-threshold", cl::init(2), cl::Hidden,
72 cl::desc("Base penalty for splitting cold code (as a "
73 "multiple of TCC_Basic)"));
74
76 "enable-cold-section", cl::init(false), cl::Hidden,
77 cl::desc("Enable placement of extracted cold functions"
78 " into a separate section after hot-cold splitting."));
79
81 ColdSectionName("hotcoldsplit-cold-section-name", cl::init("__llvm_cold"),
83 cl::desc("Name for the section containing cold functions "
84 "extracted by hot-cold splitting."));
85
87 "hotcoldsplit-max-params", cl::init(4), cl::Hidden,
88 cl::desc("Maximum number of parameters for a split function"));
89
91 "hotcoldsplit-cold-probability-denom", cl::init(100), cl::Hidden,
92 cl::desc("Divisor of cold branch probability."
93 "BranchProbability = 1/ColdBranchProbDenom"));
94
95namespace {
96// Same as blockEndsInUnreachable in CodeGen/BranchFolding.cpp. Do not modify
97// this function unless you modify the MBB version as well.
98//
99/// A no successor, non-return block probably ends in unreachable and is cold.
100/// Also consider a block that ends in an indirect branch to be a return block,
101/// since many targets use plain indirect branches to return.
102bool blockEndsInUnreachable(const BasicBlock &BB) {
103 if (!succ_empty(&BB))
104 return false;
105 if (BB.empty())
106 return true;
107 const Instruction *I = BB.getTerminator();
108 return !(isa<ReturnInst>(I) || isa<IndirectBrInst>(I));
109}
110
111void analyzeProfMetadata(BasicBlock *BB,
112 BranchProbability ColdProbThresh,
113 SmallPtrSetImpl<BasicBlock *> &AnnotatedColdBlocks) {
114 // TODO: Handle branches with > 2 successors.
115 BranchInst *CondBr = dyn_cast<BranchInst>(BB->getTerminator());
116 if (!CondBr)
117 return;
118
119 uint64_t TrueWt, FalseWt;
120 if (!extractBranchWeights(*CondBr, TrueWt, FalseWt))
121 return;
122
123 auto SumWt = TrueWt + FalseWt;
124 if (SumWt == 0)
125 return;
126
127 auto TrueProb = BranchProbability::getBranchProbability(TrueWt, SumWt);
128 auto FalseProb = BranchProbability::getBranchProbability(FalseWt, SumWt);
129
130 if (TrueProb <= ColdProbThresh)
131 AnnotatedColdBlocks.insert(CondBr->getSuccessor(0));
132
133 if (FalseProb <= ColdProbThresh)
134 AnnotatedColdBlocks.insert(CondBr->getSuccessor(1));
135}
136
137bool unlikelyExecuted(BasicBlock &BB) {
138 // Exception handling blocks are unlikely executed.
139 if (BB.isEHPad() || isa<ResumeInst>(BB.getTerminator()))
140 return true;
141
142 // The block is cold if it calls/invokes a cold function. However, do not
143 // mark sanitizer traps as cold.
144 for (Instruction &I : BB)
145 if (auto *CB = dyn_cast<CallBase>(&I))
146 if (CB->hasFnAttr(Attribute::Cold) &&
147 !CB->getMetadata(LLVMContext::MD_nosanitize))
148 return true;
149
150 // The block is cold if it has an unreachable terminator, unless it's
151 // preceded by a call to a (possibly warm) noreturn call (e.g. longjmp).
152 if (blockEndsInUnreachable(BB)) {
153 if (auto *CI =
154 dyn_cast_or_null<CallInst>(BB.getTerminator()->getPrevNode()))
155 if (CI->hasFnAttr(Attribute::NoReturn))
156 return false;
157 return true;
158 }
159
160 return false;
161}
162
163/// Check whether it's safe to outline \p BB.
164static bool mayExtractBlock(const BasicBlock &BB) {
165 // EH pads are unsafe to outline because doing so breaks EH type tables. It
166 // follows that invoke instructions cannot be extracted, because CodeExtractor
167 // requires unwind destinations to be within the extraction region.
168 //
169 // Resumes that are not reachable from a cleanup landing pad are considered to
170 // be unreachable. It’s not safe to split them out either.
171 if (BB.hasAddressTaken() || BB.isEHPad())
172 return false;
173 auto Term = BB.getTerminator();
174 return !isa<InvokeInst>(Term) && !isa<ResumeInst>(Term);
175}
176
177/// Mark \p F cold. Based on this assumption, also optimize it for minimum size.
178/// If \p UpdateEntryCount is true (set when this is a new split function and
179/// module has profile data), set entry count to 0 to ensure treated as cold.
180/// Return true if the function is changed.
181static bool markFunctionCold(Function &F, bool UpdateEntryCount = false) {
182 assert(!F.hasOptNone() && "Can't mark this cold");
183 bool Changed = false;
184 if (!F.hasFnAttribute(Attribute::Cold)) {
185 F.addFnAttr(Attribute::Cold);
186 Changed = true;
187 }
188 if (!F.hasFnAttribute(Attribute::MinSize)) {
189 F.addFnAttr(Attribute::MinSize);
190 Changed = true;
191 }
192 if (UpdateEntryCount) {
193 // Set the entry count to 0 to ensure it is placed in the unlikely text
194 // section when function sections are enabled.
195 F.setEntryCount(0);
196 Changed = true;
197 }
198
199 return Changed;
200}
201
202} // end anonymous namespace
203
204/// Check whether \p F is inherently cold.
205bool HotColdSplitting::isFunctionCold(const Function &F) const {
206 if (F.hasFnAttribute(Attribute::Cold))
207 return true;
208
209 if (F.getCallingConv() == CallingConv::Cold)
210 return true;
211
212 if (PSI->isFunctionEntryCold(&F))
213 return true;
214
215 return false;
216}
217
218bool HotColdSplitting::isBasicBlockCold(
219 BasicBlock *BB, BranchProbability ColdProbThresh,
220 SmallPtrSetImpl<BasicBlock *> &AnnotatedColdBlocks,
221 BlockFrequencyInfo *BFI) const {
222 if (BFI) {
223 if (PSI->isColdBlock(BB, BFI))
224 return true;
225 } else {
226 // Find cold blocks of successors of BB during a reverse postorder traversal.
227 analyzeProfMetadata(BB, ColdProbThresh, AnnotatedColdBlocks);
228
229 // A statically cold BB would be known before it is visited
230 // because the prof-data of incoming edges are 'analyzed' as part of RPOT.
231 if (AnnotatedColdBlocks.count(BB))
232 return true;
233 }
234
235 if (EnableStaticAnalysis && unlikelyExecuted(*BB))
236 return true;
237
238 return false;
239}
240
241// Returns false if the function should not be considered for hot-cold split
242// optimization.
243bool HotColdSplitting::shouldOutlineFrom(const Function &F) const {
244 if (F.hasFnAttribute(Attribute::AlwaysInline))
245 return false;
246
247 if (F.hasFnAttribute(Attribute::NoInline))
248 return false;
249
250 // A function marked `noreturn` may contain unreachable terminators: these
251 // should not be considered cold, as the function may be a trampoline.
252 if (F.hasFnAttribute(Attribute::NoReturn))
253 return false;
254
255 if (F.hasFnAttribute(Attribute::SanitizeAddress) ||
256 F.hasFnAttribute(Attribute::SanitizeHWAddress) ||
257 F.hasFnAttribute(Attribute::SanitizeThread) ||
258 F.hasFnAttribute(Attribute::SanitizeMemory))
259 return false;
260
261 return true;
262}
263
264/// Get the benefit score of outlining \p Region.
267 // Sum up the code size costs of non-terminator instructions. Tight coupling
268 // with \ref getOutliningPenalty is needed to model the costs of terminators.
269 InstructionCost Benefit = 0;
270 for (BasicBlock *BB : Region)
272 if (&I != BB->getTerminator())
273 Benefit +=
275
276 return Benefit;
277}
278
279/// Get the penalty score for outlining \p Region.
281 unsigned NumInputs, unsigned NumOutputs) {
282 int Penalty = SplittingThreshold;
283 LLVM_DEBUG(dbgs() << "Applying penalty for splitting: " << Penalty << "\n");
284
285 // If the splitting threshold is set at or below zero, skip the usual
286 // profitability check.
287 if (SplittingThreshold <= 0)
288 return Penalty;
289
290 // Find the number of distinct exit blocks for the region. Use a conservative
291 // check to determine whether control returns from the region.
292 bool NoBlocksReturn = true;
293 SmallPtrSet<BasicBlock *, 2> SuccsOutsideRegion;
294 for (BasicBlock *BB : Region) {
295 // If a block has no successors, only assume it does not return if it's
296 // unreachable.
297 if (succ_empty(BB)) {
298 NoBlocksReturn &= isa<UnreachableInst>(BB->getTerminator());
299 continue;
300 }
301
302 for (BasicBlock *SuccBB : successors(BB)) {
303 if (!is_contained(Region, SuccBB)) {
304 NoBlocksReturn = false;
305 SuccsOutsideRegion.insert(SuccBB);
306 }
307 }
308 }
309
310 // Count the number of phis in exit blocks with >= 2 incoming values from the
311 // outlining region. These phis are split (\ref severSplitPHINodesOfExits),
312 // and new outputs are created to supply the split phis. CodeExtractor can't
313 // report these new outputs until extraction begins, but it's important to
314 // factor the cost of the outputs into the cost calculation.
315 unsigned NumSplitExitPhis = 0;
316 for (BasicBlock *ExitBB : SuccsOutsideRegion) {
317 for (PHINode &PN : ExitBB->phis()) {
318 // Find all incoming values from the outlining region.
319 int NumIncomingVals = 0;
320 for (unsigned i = 0; i < PN.getNumIncomingValues(); ++i)
321 if (llvm::is_contained(Region, PN.getIncomingBlock(i))) {
322 ++NumIncomingVals;
323 if (NumIncomingVals > 1) {
324 ++NumSplitExitPhis;
325 break;
326 }
327 }
328 }
329 }
330
331 // Apply a penalty for calling the split function. Factor in the cost of
332 // materializing all of the parameters.
333 int NumOutputsAndSplitPhis = NumOutputs + NumSplitExitPhis;
334 int NumParams = NumInputs + NumOutputsAndSplitPhis;
335 if (NumParams > MaxParametersForSplit) {
336 LLVM_DEBUG(dbgs() << NumInputs << " inputs and " << NumOutputsAndSplitPhis
337 << " outputs exceeds parameter limit ("
338 << MaxParametersForSplit << ")\n");
339 return std::numeric_limits<int>::max();
340 }
341 const int CostForArgMaterialization = 2 * TargetTransformInfo::TCC_Basic;
342 LLVM_DEBUG(dbgs() << "Applying penalty for: " << NumParams << " params\n");
343 Penalty += CostForArgMaterialization * NumParams;
344
345 // Apply the typical code size cost for an output alloca and its associated
346 // reload in the caller. Also penalize the associated store in the callee.
347 LLVM_DEBUG(dbgs() << "Applying penalty for: " << NumOutputsAndSplitPhis
348 << " outputs/split phis\n");
349 const int CostForRegionOutput = 3 * TargetTransformInfo::TCC_Basic;
350 Penalty += CostForRegionOutput * NumOutputsAndSplitPhis;
351
352 // Apply a `noreturn` bonus.
353 if (NoBlocksReturn) {
354 LLVM_DEBUG(dbgs() << "Applying bonus for: " << Region.size()
355 << " non-returning terminators\n");
356 Penalty -= Region.size();
357 }
358
359 // Apply a penalty for having more than one successor outside of the region.
360 // This penalty accounts for the switch needed in the caller.
361 if (SuccsOutsideRegion.size() > 1) {
362 LLVM_DEBUG(dbgs() << "Applying penalty for: " << SuccsOutsideRegion.size()
363 << " non-region successors\n");
364 Penalty += (SuccsOutsideRegion.size() - 1) * TargetTransformInfo::TCC_Basic;
365 }
366
367 return Penalty;
368}
369
370// Determine if it is beneficial to split the \p Region.
371bool HotColdSplitting::isSplittingBeneficial(CodeExtractor &CE,
372 const BlockSequence &Region,
374 assert(!Region.empty());
375
376 // Perform a simple cost/benefit analysis to decide whether or not to permit
377 // splitting.
378 SetVector<Value *> Inputs, Outputs, Sinks;
379 CE.findInputsOutputs(Inputs, Outputs, Sinks);
380 InstructionCost OutliningBenefit = getOutliningBenefit(Region, TTI);
381 int OutliningPenalty =
382 getOutliningPenalty(Region, Inputs.size(), Outputs.size());
383 LLVM_DEBUG(dbgs() << "Split profitability: benefit = " << OutliningBenefit
384 << ", penalty = " << OutliningPenalty << "\n");
385 if (!OutliningBenefit.isValid() || OutliningBenefit <= OutliningPenalty)
386 return false;
387
388 return true;
389}
390
391// Split the single \p EntryPoint cold region. \p CE is the region code
392// extractor.
393Function *HotColdSplitting::extractColdRegion(
394 BasicBlock &EntryPoint, CodeExtractor &CE,
397 Function *OrigF = EntryPoint.getParent();
398 if (Function *OutF = CE.extractCodeRegion(CEAC)) {
399 User *U = *OutF->user_begin();
400 CallInst *CI = cast<CallInst>(U);
401 NumColdRegionsOutlined++;
402 if (TTI.useColdCCForColdCall(*OutF)) {
403 OutF->setCallingConv(CallingConv::Cold);
405 }
406 CI->setIsNoInline();
407
409 OutF->setSection(ColdSectionName);
410 else {
411 if (OrigF->hasSection())
412 OutF->setSection(OrigF->getSection());
413 }
414
415 markFunctionCold(*OutF, BFI != nullptr);
416
417 LLVM_DEBUG(llvm::dbgs() << "Outlined Region: " << *OutF);
418 ORE.emit([&]() {
419 return OptimizationRemark(DEBUG_TYPE, "HotColdSplit",
420 &*EntryPoint.begin())
421 << ore::NV("Original", OrigF) << " split cold code into "
422 << ore::NV("Split", OutF);
423 });
424 return OutF;
425 }
426
427 ORE.emit([&]() {
428 return OptimizationRemarkMissed(DEBUG_TYPE, "ExtractFailed",
429 &*EntryPoint.begin())
430 << "Failed to extract region at block "
431 << ore::NV("Block", &EntryPoint);
432 });
433 return nullptr;
434}
435
436/// A pair of (basic block, score).
437using BlockTy = std::pair<BasicBlock *, unsigned>;
438
439namespace {
440/// A maximal outlining region. This contains all blocks post-dominated by a
441/// sink block, the sink block itself, and all blocks dominated by the sink.
442/// If sink-predecessors and sink-successors cannot be extracted in one region,
443/// the static constructor returns a list of suitable extraction regions.
444class OutliningRegion {
445 /// A list of (block, score) pairs. A block's score is non-zero iff it's a
446 /// viable sub-region entry point. Blocks with higher scores are better entry
447 /// points (i.e. they are more distant ancestors of the sink block).
449
450 /// The suggested entry point into the region. If the region has multiple
451 /// entry points, all blocks within the region may not be reachable from this
452 /// entry point.
453 BasicBlock *SuggestedEntryPoint = nullptr;
454
455 /// Whether the entire function is cold.
456 bool EntireFunctionCold = false;
457
458 /// If \p BB is a viable entry point, return \p Score. Return 0 otherwise.
459 static unsigned getEntryPointScore(BasicBlock &BB, unsigned Score) {
460 return mayExtractBlock(BB) ? Score : 0;
461 }
462
463 /// These scores should be lower than the score for predecessor blocks,
464 /// because regions starting at predecessor blocks are typically larger.
465 static constexpr unsigned ScoreForSuccBlock = 1;
466 static constexpr unsigned ScoreForSinkBlock = 1;
467
468 OutliningRegion(const OutliningRegion &) = delete;
469 OutliningRegion &operator=(const OutliningRegion &) = delete;
470
471public:
472 OutliningRegion() = default;
473 OutliningRegion(OutliningRegion &&) = default;
474 OutliningRegion &operator=(OutliningRegion &&) = default;
475
476 static std::vector<OutliningRegion> create(BasicBlock &SinkBB,
477 const DominatorTree &DT,
478 const PostDominatorTree &PDT) {
479 std::vector<OutliningRegion> Regions;
480 SmallPtrSet<BasicBlock *, 4> RegionBlocks;
481
482 Regions.emplace_back();
483 OutliningRegion *ColdRegion = &Regions.back();
484
485 auto addBlockToRegion = [&](BasicBlock *BB, unsigned Score) {
486 RegionBlocks.insert(BB);
487 ColdRegion->Blocks.emplace_back(BB, Score);
488 };
489
490 // The ancestor farthest-away from SinkBB, and also post-dominated by it.
491 unsigned SinkScore = getEntryPointScore(SinkBB, ScoreForSinkBlock);
492 ColdRegion->SuggestedEntryPoint = (SinkScore > 0) ? &SinkBB : nullptr;
493 unsigned BestScore = SinkScore;
494
495 // Visit SinkBB's ancestors using inverse DFS.
496 auto PredIt = ++idf_begin(&SinkBB);
497 auto PredEnd = idf_end(&SinkBB);
498 while (PredIt != PredEnd) {
499 BasicBlock &PredBB = **PredIt;
500 bool SinkPostDom = PDT.dominates(&SinkBB, &PredBB);
501
502 // If the predecessor is cold and has no predecessors, the entire
503 // function must be cold.
504 if (SinkPostDom && pred_empty(&PredBB)) {
505 ColdRegion->EntireFunctionCold = true;
506 return Regions;
507 }
508
509 // If SinkBB does not post-dominate a predecessor, do not mark the
510 // predecessor (or any of its predecessors) cold.
511 if (!SinkPostDom || !mayExtractBlock(PredBB)) {
512 PredIt.skipChildren();
513 continue;
514 }
515
516 // Keep track of the post-dominated ancestor farthest away from the sink.
517 // The path length is always >= 2, ensuring that predecessor blocks are
518 // considered as entry points before the sink block.
519 unsigned PredScore = getEntryPointScore(PredBB, PredIt.getPathLength());
520 if (PredScore > BestScore) {
521 ColdRegion->SuggestedEntryPoint = &PredBB;
522 BestScore = PredScore;
523 }
524
525 addBlockToRegion(&PredBB, PredScore);
526 ++PredIt;
527 }
528
529 // If the sink can be added to the cold region, do so. It's considered as
530 // an entry point before any sink-successor blocks.
531 //
532 // Otherwise, split cold sink-successor blocks using a separate region.
533 // This satisfies the requirement that all extraction blocks other than the
534 // first have predecessors within the extraction region.
535 if (mayExtractBlock(SinkBB)) {
536 addBlockToRegion(&SinkBB, SinkScore);
537 if (pred_empty(&SinkBB)) {
538 ColdRegion->EntireFunctionCold = true;
539 return Regions;
540 }
541 } else {
542 Regions.emplace_back();
543 ColdRegion = &Regions.back();
544 BestScore = 0;
545 }
546
547 // Find all successors of SinkBB dominated by SinkBB using DFS.
548 auto SuccIt = ++df_begin(&SinkBB);
549 auto SuccEnd = df_end(&SinkBB);
550 while (SuccIt != SuccEnd) {
551 BasicBlock &SuccBB = **SuccIt;
552 bool SinkDom = DT.dominates(&SinkBB, &SuccBB);
553
554 // Don't allow the backwards & forwards DFSes to mark the same block.
555 bool DuplicateBlock = RegionBlocks.count(&SuccBB);
556
557 // If SinkBB does not dominate a successor, do not mark the successor (or
558 // any of its successors) cold.
559 if (DuplicateBlock || !SinkDom || !mayExtractBlock(SuccBB)) {
560 SuccIt.skipChildren();
561 continue;
562 }
563
564 unsigned SuccScore = getEntryPointScore(SuccBB, ScoreForSuccBlock);
565 if (SuccScore > BestScore) {
566 ColdRegion->SuggestedEntryPoint = &SuccBB;
567 BestScore = SuccScore;
568 }
569
570 addBlockToRegion(&SuccBB, SuccScore);
571 ++SuccIt;
572 }
573
574 return Regions;
575 }
576
577 /// Whether this region has nothing to extract.
578 bool empty() const { return !SuggestedEntryPoint; }
579
580 /// The blocks in this region.
582
583 /// Whether the entire function containing this region is cold.
584 bool isEntireFunctionCold() const { return EntireFunctionCold; }
585
586 /// Remove a sub-region from this region and return it as a block sequence.
587 BlockSequence takeSingleEntrySubRegion(DominatorTree &DT) {
588 assert(!empty() && !isEntireFunctionCold() && "Nothing to extract");
589
590 // Remove blocks dominated by the suggested entry point from this region.
591 // During the removal, identify the next best entry point into the region.
592 // Ensure that the first extracted block is the suggested entry point.
593 BlockSequence SubRegion = {SuggestedEntryPoint};
594 BasicBlock *NextEntryPoint = nullptr;
595 unsigned NextScore = 0;
596 auto RegionEndIt = Blocks.end();
597 auto RegionStartIt = remove_if(Blocks, [&](const BlockTy &Block) {
598 BasicBlock *BB = Block.first;
599 unsigned Score = Block.second;
600 bool InSubRegion =
601 BB == SuggestedEntryPoint || DT.dominates(SuggestedEntryPoint, BB);
602 if (!InSubRegion && Score > NextScore) {
603 NextEntryPoint = BB;
604 NextScore = Score;
605 }
606 if (InSubRegion && BB != SuggestedEntryPoint)
607 SubRegion.push_back(BB);
608 return InSubRegion;
609 });
610 Blocks.erase(RegionStartIt, RegionEndIt);
611
612 // Update the suggested entry point.
613 SuggestedEntryPoint = NextEntryPoint;
614
615 return SubRegion;
616 }
617};
618} // namespace
619
620bool HotColdSplitting::outlineColdRegions(Function &F, bool HasProfileSummary) {
621 // The set of cold blocks outlined.
623
624 // The set of cold blocks cannot be outlined.
625 SmallPtrSet<BasicBlock *, 4> CannotBeOutlinedColdBlocks;
626
627 // Set of cold blocks obtained with RPOT.
628 SmallPtrSet<BasicBlock *, 4> AnnotatedColdBlocks;
629
630 // The worklist of non-intersecting regions left to outline. The first member
631 // of the pair is the entry point into the region to be outlined.
633
634 // Set up an RPO traversal. Experimentally, this performs better (outlines
635 // more) than a PO traversal, because we prevent region overlap by keeping
636 // the first region to contain a block.
638
639 // Calculate domtrees lazily. This reduces compile-time significantly.
640 std::unique_ptr<DominatorTree> DT;
641 std::unique_ptr<PostDominatorTree> PDT;
642
643 // Calculate BFI lazily (it's only used to query ProfileSummaryInfo). This
644 // reduces compile-time significantly. TODO: When we *do* use BFI, we should
645 // be able to salvage its domtrees instead of recomputing them.
646 BlockFrequencyInfo *BFI = nullptr;
647 if (HasProfileSummary)
648 BFI = GetBFI(F);
649
650 TargetTransformInfo &TTI = GetTTI(F);
651 OptimizationRemarkEmitter &ORE = (*GetORE)(F);
652 AssumptionCache *AC = LookupAC(F);
653 auto ColdProbThresh = TTI.getPredictableBranchThreshold().getCompl();
654
655 if (ColdBranchProbDenom.getNumOccurrences())
656 ColdProbThresh = BranchProbability(1, ColdBranchProbDenom.getValue());
657
658 unsigned OutlinedFunctionID = 1;
659 // Find all cold regions.
660 for (BasicBlock *BB : RPOT) {
661 // This block is already part of some outlining region.
662 if (ColdBlocks.count(BB))
663 continue;
664
665 // This block is already part of some region cannot be outlined.
666 if (CannotBeOutlinedColdBlocks.count(BB))
667 continue;
668
669 if (!isBasicBlockCold(BB, ColdProbThresh, AnnotatedColdBlocks, BFI))
670 continue;
671
672 LLVM_DEBUG({
673 dbgs() << "Found a cold block:\n";
674 BB->dump();
675 });
676
677 if (!DT)
678 DT = std::make_unique<DominatorTree>(F);
679 if (!PDT)
680 PDT = std::make_unique<PostDominatorTree>(F);
681
682 auto Regions = OutliningRegion::create(*BB, *DT, *PDT);
683 for (OutliningRegion &Region : Regions) {
684 if (Region.empty())
685 continue;
686
687 if (Region.isEntireFunctionCold()) {
688 LLVM_DEBUG(dbgs() << "Entire function is cold\n");
689 return markFunctionCold(F);
690 }
691
692 do {
693 BlockSequence SubRegion = Region.takeSingleEntrySubRegion(*DT);
694 LLVM_DEBUG({
695 dbgs() << "Hot/cold splitting attempting to outline these blocks:\n";
696 for (BasicBlock *BB : SubRegion)
697 BB->dump();
698 });
699
700 // TODO: Pass BFI and BPI to update profile information.
702 SubRegion, &*DT, /* AggregateArgs */ false, /* BFI */ nullptr,
703 /* BPI */ nullptr, AC, /* AllowVarArgs */ false,
704 /* AllowAlloca */ false, /* AllocaBlock */ nullptr,
705 /* Suffix */ "cold." + std::to_string(OutlinedFunctionID));
706
707 if (CE.isEligible() && isSplittingBeneficial(CE, SubRegion, TTI) &&
708 // If this outlining region intersects with another, drop the new
709 // region.
710 //
711 // TODO: It's theoretically possible to outline more by only keeping
712 // the largest region which contains a block, but the extra
713 // bookkeeping to do this is tricky/expensive.
714 none_of(SubRegion, [&](BasicBlock *Block) {
715 return ColdBlocks.contains(Block);
716 })) {
717 ColdBlocks.insert(SubRegion.begin(), SubRegion.end());
718
719 LLVM_DEBUG({
720 for (auto *Block : SubRegion)
721 dbgs() << " contains cold block:" << Block->getName() << "\n";
722 });
723
724 OutliningWorklist.emplace_back(
725 std::make_pair(SubRegion[0], std::move(CE)));
726 ++OutlinedFunctionID;
727 } else {
728 // The cold block region cannot be outlined.
729 for (auto *Block : SubRegion)
730 if ((DT->dominates(BB, Block) && PDT->dominates(Block, BB)) ||
731 (PDT->dominates(BB, Block) && DT->dominates(Block, BB)))
732 // Will skip this cold block in the loop to save the compile time
733 CannotBeOutlinedColdBlocks.insert(Block);
734 }
735 } while (!Region.empty());
736
737 ++NumColdRegionsFound;
738 }
739 }
740
741 if (OutliningWorklist.empty())
742 return false;
743
744 // Outline single-entry cold regions, splitting up larger regions as needed.
745 // Cache and recycle the CodeExtractor analysis to avoid O(n^2) compile-time.
747 for (auto &BCE : OutliningWorklist) {
748 Function *Outlined =
749 extractColdRegion(*BCE.first, BCE.second, CEAC, BFI, TTI, ORE);
750 assert(Outlined && "Should be outlined");
751 (void)Outlined;
752 }
753
754 return true;
755}
756
758 bool Changed = false;
759 bool HasProfileSummary = (M.getProfileSummary(/* IsCS */ false) != nullptr);
760 for (Function &F : M) {
761 // Do not touch declarations.
762 if (F.isDeclaration())
763 continue;
764
765 // Do not modify `optnone` functions.
766 if (F.hasOptNone())
767 continue;
768
769 // Detect inherently cold functions and mark them as such.
770 if (isFunctionCold(F)) {
771 Changed |= markFunctionCold(F);
772 continue;
773 }
774
775 if (!shouldOutlineFrom(F)) {
776 LLVM_DEBUG(llvm::dbgs() << "Skipping " << F.getName() << "\n");
777 continue;
778 }
779
780 LLVM_DEBUG(llvm::dbgs() << "Outlining in " << F.getName() << "\n");
781 Changed |= outlineColdRegions(F, HasProfileSummary);
782 }
783 return Changed;
784}
785
788 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
789
790 auto LookupAC = [&FAM](Function &F) -> AssumptionCache * {
792 };
793
794 auto GBFI = [&FAM](Function &F) {
796 };
797
798 std::function<TargetTransformInfo &(Function &)> GTTI =
801 };
802
803 std::unique_ptr<OptimizationRemarkEmitter> ORE;
804 std::function<OptimizationRemarkEmitter &(Function &)> GetORE =
805 [&ORE](Function &F) -> OptimizationRemarkEmitter & {
806 ORE.reset(new OptimizationRemarkEmitter(&F));
807 return *ORE;
808 };
809
811
812 if (HotColdSplitting(PSI, GBFI, GTTI, &GetORE, LookupAC).run(M))
814 return PreservedAnalyses::all();
815}
bbsections Prepares for basic block by splitting functions into clusters of basic blocks
static bool blockEndsInUnreachable(const MachineBasicBlock *MBB)
A no successor, non-return block probably ends in unreachable and is cold.
#define LLVM_DEBUG(X)
Definition: Debug.h:101
DenseMap< Block *, BlockRelaxAux > Blocks
Definition: ELF_riscv.cpp:507
#define DEBUG_TYPE
std::pair< BasicBlock *, unsigned > BlockTy
A pair of (basic block, score).
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)"))
static cl::opt< std::string > ColdSectionName("hotcoldsplit-cold-section-name", cl::init("__llvm_cold"), cl::Hidden, cl::desc("Name for the section containing cold functions " "extracted by hot-cold splitting."))
static cl::opt< int > ColdBranchProbDenom("hotcoldsplit-cold-probability-denom", cl::init(100), cl::Hidden, cl::desc("Divisor of cold branch probability." "BranchProbability = 1/ColdBranchProbDenom"))
static cl::opt< int > MaxParametersForSplit("hotcoldsplit-max-params", cl::init(4), cl::Hidden, cl::desc("Maximum number of parameters for a split function"))
static InstructionCost getOutliningBenefit(ArrayRef< BasicBlock * > Region, TargetTransformInfo &TTI)
Get the benefit score of outlining Region.
static cl::opt< bool > EnableColdSection("enable-cold-section", cl::init(false), cl::Hidden, cl::desc("Enable placement of extracted cold functions" " into a separate section after hot-cold splitting."))
static cl::opt< bool > EnableStaticAnalysis("hot-cold-static-analysis", cl::init(true), cl::Hidden)
static int getOutliningPenalty(ArrayRef< BasicBlock * > Region, unsigned NumInputs, unsigned NumOutputs)
Get the penalty score for outlining Region.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file contains the declarations for profiling metadata utility functions.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
This pass exposes codegen information to IR-level passes.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:519
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:438
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
Definition: BasicBlock.cpp:294
bool empty() const
Definition: BasicBlock.h:460
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
Definition: BasicBlock.h:648
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:214
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:665
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.h:229
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
BasicBlock * getSuccessor(unsigned i) const
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
BranchProbability getCompl() const
void setCallingConv(CallingConv::ID CC)
Definition: InstrTypes.h:1758
void setIsNoInline()
Definition: InstrTypes.h:2170
This class represents a function call, abstracting a target machine's calling convention.
A cache for the CodeExtractor analysis.
Definition: CodeExtractor.h:46
Utility class for extracting code into a new function.
Definition: CodeExtractor.h:85
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
StringRef getSection() const
Get the custom section of this global if it has one.
Definition: GlobalObject.h:118
bool hasSection() const
Check if this global has a custom object file section.
Definition: GlobalObject.h:110
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:658
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
The optimization diagnostic interface.
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Diagnostic information for missed-optimization remarks.
Diagnostic information for applied optimization remarks.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Analysis providing profile information.
bool isColdBlock(const BBType *BB, BFIT *BFI) const
Returns true if BasicBlock BB is considered cold.
bool isFunctionEntryCold(const Function *F) const
Returns true if F has cold function entry.
A vector that has set insertion semantics.
Definition: SetVector.h:57
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:98
size_type size() const
Definition: SmallPtrSet.h:94
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:321
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
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:342
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:950
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Analysis pass providing the TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
@ TCK_CodeSize
Instruction code size.
BranchProbability getPredictableBranchThreshold() const
If a branch or a select condition is skewed in one direction by more than this factor,...
@ TCC_Basic
The cost of a typical 'add' instruction.
InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
bool useColdCCForColdCall(Function &F) const
Return true if the input function which is cold at all call sites, should use coldcc calling conventi...
void dump() const
Support for debugging, callable in GDB: V->dump()
Definition: AsmWriter.cpp:5212
@ Cold
Attempts to make code in the caller as efficient as possible under the assumption that the call is no...
Definition: CallingConv.h:47
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool succ_empty(const Instruction *I)
Definition: CFG.h:255
auto successors(const MachineBasicBlock *BB)
df_iterator< T > df_begin(const T &G)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1745
idf_iterator< T > idf_end(const T &G)
auto remove_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1770
idf_iterator< T > idf_begin(const T &G)
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1888
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
df_iterator< T > df_end(const T &G)