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