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