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