1//===- HotColdSplitting.cpp -- Outline Cold Regions -------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// The goal of hot/cold splitting is to improve the memory locality of code.
11/// The splitting pass does this by identifying cold blocks and moving them into
12/// separate functions.
13///
14/// When the splitting pass finds a cold block (referred to as "the sink"), it
15/// grows a maximal cold region around that block. The maximal region contains
16/// all blocks (post-)dominated by the sink [*]. In theory, these blocks are as
17/// cold as the sink. Once a region is found, it's split out of the original
18/// function provided it's profitable to do so.
19///
20/// [*] In practice, there is some added complexity because some blocks are not
21/// safe to extract.
22///
23/// TODO: Use the PM to get domtrees, and preserve BFI/BPI.
24/// TODO: Reorder outlined functions.
25///
26//===----------------------------------------------------------------------===//
27
28#include "llvm/Transforms/IPO/HotColdSplitting.h"
29#include "llvm/ADT/PostOrderIterator.h"
30#include "llvm/ADT/SmallVector.h"
31#include "llvm/ADT/Statistic.h"
32#include "llvm/Analysis/AssumptionCache.h"
33#include "llvm/Analysis/BlockFrequencyInfo.h"
34#include "llvm/Analysis/OptimizationRemarkEmitter.h"
35#include "llvm/Analysis/PostDominators.h"
36#include "llvm/Analysis/ProfileSummaryInfo.h"
37#include "llvm/Analysis/TargetTransformInfo.h"
38#include "llvm/IR/BasicBlock.h"
39#include "llvm/IR/CFG.h"
40#include "llvm/IR/DiagnosticInfo.h"
41#include "llvm/IR/Dominators.h"
42#include "llvm/IR/EHPersonalities.h"
43#include "llvm/IR/Function.h"
44#include "llvm/IR/Instruction.h"
45#include "llvm/IR/Instructions.h"
46#include "llvm/IR/Module.h"
47#include "llvm/IR/PassManager.h"
48#include "llvm/IR/ProfDataUtils.h"
49#include "llvm/IR/User.h"
50#include "llvm/IR/Value.h"
51#include "llvm/Support/CommandLine.h"
52#include "llvm/Support/Debug.h"
53#include "llvm/Support/raw_ostream.h"
54#include "llvm/Transforms/IPO.h"
55#include "llvm/Transforms/Utils/CodeExtractor.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(Val: true), cl::Hidden);
70
71static cl::opt<int>
72 SplittingThreshold("hotcoldsplit-threshold", cl::init(Val: 2), cl::Hidden,
73 cl::desc("Base penalty for splitting cold code (as a "
74 "multiple of TCC_Basic)"));
75
76static cl::opt<bool> EnableColdSection(
77 "enable-cold-section", cl::init(Val: false), cl::Hidden,
78 cl::desc("Enable placement of extracted cold functions"
79 " into a separate section after hot-cold splitting."));
80
81static cl::opt<std::string>
82 ColdSectionName("hotcoldsplit-cold-section-name", cl::init(Val: "__llvm_cold"),
83 cl::Hidden,
84 cl::desc("Name for the section containing cold functions "
85 "extracted by hot-cold splitting."));
86
87static cl::opt<int> MaxParametersForSplit(
88 "hotcoldsplit-max-params", cl::init(Val: 4), cl::Hidden,
89 cl::desc("Maximum number of parameters for a split function"));
90
91static cl::opt<int> ColdBranchProbDenom(
92 "hotcoldsplit-cold-probability-denom", cl::init(Val: 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: &BB))
105 return false;
106 if (BB.empty())
107 return true;
108 const Instruction *I = BB.getTerminator();
109 return !(isa<ReturnInst>(Val: I) || isa<IndirectBrInst>(Val: 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>(Val: BB->getTerminator());
117 if (!CondBr)
118 return;
119
120 uint64_t TrueWt, FalseWt;
121 if (!extractBranchWeights(I: *CondBr, TrueVal&: TrueWt, FalseVal&: FalseWt))
122 return;
123
124 auto SumWt = TrueWt + FalseWt;
125 if (SumWt == 0)
126 return;
127
128 auto TrueProb = BranchProbability::getBranchProbability(Numerator: TrueWt, Denominator: SumWt);
129 auto FalseProb = BranchProbability::getBranchProbability(Numerator: FalseWt, Denominator: SumWt);
130
131 if (TrueProb <= ColdProbThresh)
132 AnnotatedColdBlocks.insert(Ptr: CondBr->getSuccessor(i: 0));
133
134 if (FalseProb <= ColdProbThresh)
135 AnnotatedColdBlocks.insert(Ptr: CondBr->getSuccessor(i: 1));
136}
137
138bool unlikelyExecuted(BasicBlock &BB) {
139 // Exception handling blocks are unlikely executed.
140 if (BB.isEHPad() || isa<ResumeInst>(Val: 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>(Val: &I))
147 if (CB->hasFnAttr(Kind: Attribute::Cold) &&
148 !CB->getMetadata(KindID: 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>(Val: BB.getTerminator()->getPrevNode()))
156 if (CI->hasFnAttr(Kind: 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>(Val: Term) || isa<ResumeInst>(Val: 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 Range: BB, P: [](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(Kind: Attribute::Cold)) {
200 F.addFnAttr(Kind: Attribute::Cold);
201 Changed = true;
202 }
203 if (!F.hasFnAttribute(Kind: Attribute::MinSize)) {
204 F.addFnAttr(Kind: 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(Count: 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(Kind: Attribute::Cold))
222 return true;
223
224 if (F.getCallingConv() == CallingConv::Cold)
225 return true;
226
227 if (PSI->isFunctionEntryCold(F: &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(Ptr: BB))
247 return true;
248 }
249
250 if (EnableStaticAnalysis && unlikelyExecuted(BB&: *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(Kind: Attribute::AlwaysInline))
260 return false;
261
262 if (F.hasFnAttribute(Kind: 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(Kind: Attribute::NoReturn))
268 return false;
269
270 if (F.hasFnAttribute(Kind: Attribute::SanitizeAddress) ||
271 F.hasFnAttribute(Kind: Attribute::SanitizeHWAddress) ||
272 F.hasFnAttribute(Kind: Attribute::SanitizeThread) ||
273 F.hasFnAttribute(Kind: Attribute::SanitizeMemory))
274 return false;
275
276 // Do not outline scoped EH personality functions.
277 if (F.hasPersonalityFn())
278 if (isScopedEHPersonality(Pers: classifyEHPersonality(Pers: F.getPersonalityFn())))
279 return false;
280
281 return true;
282}
283
284/// Get the benefit score of outlining \p Region.
285static InstructionCost getOutliningBenefit(ArrayRef<BasicBlock *> Region,
286 TargetTransformInfo &TTI) {
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)
291 for (Instruction &I : BB->instructionsWithoutDebug())
292 if (&I != BB->getTerminator())
293 Benefit +=
294 TTI.getInstructionCost(U: &I, CostKind: TargetTransformInfo::TCK_CodeSize);
295
296 return Benefit;
297}
298
299/// Get the penalty score for outlining \p Region.
300static int getOutliningPenalty(ArrayRef<BasicBlock *> 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>(Val: BB->getTerminator());
319 continue;
320 }
321
322 for (BasicBlock *SuccBB : successors(BB)) {
323 if (!is_contained(Range&: Region, Element: SuccBB)) {
324 NoBlocksReturn = false;
325 SuccsOutsideRegion.insert(Ptr: 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(Range&: Region, Element: 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,
393 TargetTransformInfo &TTI) {
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, Allocas: Sinks);
400 InstructionCost OutliningBenefit = getOutliningBenefit(Region, TTI);
401 int OutliningPenalty =
402 getOutliningPenalty(Region, NumInputs: Inputs.size(), NumOutputs: 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,
415 const CodeExtractorAnalysisCache &CEAC, BlockFrequencyInfo *BFI,
416 TargetTransformInfo &TTI, OptimizationRemarkEmitter &ORE) {
417 Function *OrigF = EntryPoint.getParent();
418 if (Function *OutF = CE.extractCodeRegion(CEAC)) {
419 User *U = *OutF->user_begin();
420 CallInst *CI = cast<CallInst>(Val: U);
421 NumColdRegionsOutlined++;
422 if (TTI.useColdCCForColdCall(F&: *OutF)) {
423 OutF->setCallingConv(CallingConv::Cold);
424 CI->setCallingConv(CallingConv::Cold);
425 }
426 CI->setIsNoInline();
427
428 if (EnableColdSection)
429 OutF->setSection(ColdSectionName);
430 else {
431 if (OrigF->hasSection())
432 OutF->setSection(OrigF->getSection());
433 }
434
435 markFunctionCold(F&: *OutF, UpdateEntryCount: BFI != nullptr);
436
437 LLVM_DEBUG(llvm::dbgs() << "Outlined Region: " << *OutF);
438 ORE.emit(RemarkBuilder: [&]() {
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(RemarkBuilder: [&]() {
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).
468 SmallVector<BlockTy, 0> Blocks = {};
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(Ptr: BB);
507 ColdRegion->Blocks.emplace_back(Args&: BB, Args&: Score);
508 };
509
510 // The ancestor farthest-away from SinkBB, and also post-dominated by it.
511 unsigned SinkScore = getEntryPointScore(BB&: SinkBB, Score: 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(G: &SinkBB);
517 auto PredEnd = idf_end(G: &SinkBB);
518 while (PredIt != PredEnd) {
519 BasicBlock &PredBB = **PredIt;
520 bool SinkPostDom = PDT.dominates(A: &SinkBB, B: &PredBB);
521
522 // If the predecessor is cold and has no predecessors, the entire
523 // function must be cold.
524 if (SinkPostDom && pred_empty(BB: &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(BB: 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(BB&: PredBB, Score: 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(BB: SinkBB)) {
556 addBlockToRegion(&SinkBB, SinkScore);
557 if (pred_empty(BB: &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(G: &SinkBB);
569 auto SuccEnd = df_end(G: &SinkBB);
570 while (SuccIt != SuccEnd) {
571 BasicBlock &SuccBB = **SuccIt;
572 bool SinkDom = DT.dominates(A: &SinkBB, B: &SuccBB);
573
574 // Don't allow the backwards & forwards DFSes to mark the same block.
575 bool DuplicateBlock = RegionBlocks.count(Ptr: &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(BB: SuccBB)) {
580 SuccIt.skipChildren();
581 continue;
582 }
583
584 unsigned SuccScore = getEntryPointScore(BB&: SuccBB, Score: 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.
601 ArrayRef<std::pair<BasicBlock *, unsigned>> blocks() const { return Blocks; }
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(Range&: Blocks, P: [&](const BlockTy &Block) {
618 BasicBlock *BB = Block.first;
619 unsigned Score = Block.second;
620 bool InSubRegion =
621 BB == SuggestedEntryPoint || DT.dominates(A: SuggestedEntryPoint, B: BB);
622 if (!InSubRegion && Score > NextScore) {
623 NextEntryPoint = BB;
624 NextScore = Score;
625 }
626 if (InSubRegion && BB != SuggestedEntryPoint)
627 SubRegion.push_back(Elt: BB);
628 return InSubRegion;
629 });
630 Blocks.erase(CS: RegionStartIt, CE: 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.
642 SmallPtrSet<BasicBlock *, 4> ColdBlocks;
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.
652 SmallVector<std::pair<BasicBlock *, CodeExtractor>, 2> OutliningWorklist;
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.
657 ReversePostOrderTraversal<Function *> RPOT(&F);
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(Ptr: BB))
683 continue;
684
685 // This block is already part of some region cannot be outlined.
686 if (CannotBeOutlinedColdBlocks.count(Ptr: 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>(args&: F);
699 if (!PDT)
700 PDT = std::make_unique<PostDominatorTree>(args&: F);
701
702 auto Regions = OutliningRegion::create(SinkBB&: *BB, DT: *DT, PDT: *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&: *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.
721 CodeExtractor CE(
722 SubRegion, &*DT, /* AggregateArgs */ false, /* BFI */ nullptr,
723 /* BPI */ nullptr, AC, /* AllowVarArgs */ false,
724 /* AllowAlloca */ false, /* AllocaBlock */ nullptr,
725 /* Suffix */ "cold." + std::to_string(val: OutlinedFunctionID));
726
727 if (CE.isEligible() && isSplittingBeneficial(CE, Region: 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(Range&: SubRegion, P: [&](BasicBlock *Block) {
735 return ColdBlocks.contains(Ptr: Block);
736 })) {
737 ColdBlocks.insert(I: SubRegion.begin(), E: 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 Args: std::make_pair(x&: SubRegion[0], y: std::move(CE)));
746 ++OutlinedFunctionID;
747 } else {
748 // The cold block region cannot be outlined.
749 for (auto *Block : SubRegion)
750 if ((DT->dominates(A: BB, B: Block) && PDT->dominates(A: Block, B: BB)) ||
751 (PDT->dominates(A: BB, B: Block) && DT->dominates(A: Block, B: BB)))
752 // Will skip this cold block in the loop to save the compile time
753 CannotBeOutlinedColdBlocks.insert(Ptr: 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.
766 CodeExtractorAnalysisCache CEAC(F);
767 for (auto &BCE : OutliningWorklist) {
768 Function *Outlined =
769 extractColdRegion(EntryPoint&: *BCE.first, CE&: BCE.second, CEAC, BFI, TTI, ORE);
770 assert(Outlined && "Should be outlined");
771 (void)Outlined;
772 }
773
774 return true;
775}
776
777bool HotColdSplitting::run(Module &M) {
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
806PreservedAnalyses
807HotColdSplittingPass::run(Module &M, ModuleAnalysisManager &AM) {
808 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
809
810 auto LookupAC = [&FAM](Function &F) -> AssumptionCache * {
811 return FAM.getCachedResult<AssumptionAnalysis>(IR&: F);
812 };
813
814 auto GBFI = [&FAM](Function &F) {
815 return &FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
816 };
817
818 std::function<TargetTransformInfo &(Function &)> GTTI =
819 [&FAM](Function &F) -> TargetTransformInfo & {
820 return FAM.getResult<TargetIRAnalysis>(IR&: F);
821 };
822
823 std::unique_ptr<OptimizationRemarkEmitter> ORE;
824 std::function<OptimizationRemarkEmitter &(Function &)> GetORE =
825 [&ORE](Function &F) -> OptimizationRemarkEmitter & {
826 ORE.reset(p: new OptimizationRemarkEmitter(&F));
827 return *ORE;
828 };
829
830 ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(IR&: M);
831
832 if (HotColdSplitting(PSI, GBFI, GTTI, &GetORE, LookupAC).run(M))
833 return PreservedAnalyses::none();
834 return PreservedAnalyses::all();
835}
836