blob: 5d989a40f65f2058485aac8d98b10ed3ab34cc8f [file] [log] [blame]
Aditya Kumar801394a2018-09-07 15:03:49 +00001//===- HotColdSplitting.cpp -- Outline Cold Regions -------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Outline cold regions to a separate function.
11// TODO: Update BFI and BPI
12// TODO: Add all the outlined functions to a separate section.
13//
14//===----------------------------------------------------------------------===//
15
Vedant Kumar03aaa3e2018-12-07 20:23:52 +000016#include "llvm/ADT/PostOrderIterator.h"
Aditya Kumar801394a2018-09-07 15:03:49 +000017#include "llvm/ADT/SmallVector.h"
18#include "llvm/ADT/Statistic.h"
19#include "llvm/Analysis/AliasAnalysis.h"
20#include "llvm/Analysis/BlockFrequencyInfo.h"
21#include "llvm/Analysis/BranchProbabilityInfo.h"
22#include "llvm/Analysis/CFG.h"
23#include "llvm/Analysis/OptimizationRemarkEmitter.h"
24#include "llvm/Analysis/PostDominators.h"
25#include "llvm/Analysis/ProfileSummaryInfo.h"
Sebastian Popa1f20fc2018-09-10 15:08:02 +000026#include "llvm/Analysis/TargetTransformInfo.h"
Aditya Kumar801394a2018-09-07 15:03:49 +000027#include "llvm/IR/BasicBlock.h"
28#include "llvm/IR/CFG.h"
Vedant Kumar03f9f152018-12-07 20:24:04 +000029#include "llvm/IR/CallSite.h"
Aditya Kumar801394a2018-09-07 15:03:49 +000030#include "llvm/IR/DataLayout.h"
31#include "llvm/IR/DiagnosticInfo.h"
32#include "llvm/IR/Dominators.h"
33#include "llvm/IR/Function.h"
34#include "llvm/IR/Instruction.h"
35#include "llvm/IR/Instructions.h"
Vedant Kumardd4be532018-10-29 19:15:39 +000036#include "llvm/IR/IntrinsicInst.h"
Aditya Kumar801394a2018-09-07 15:03:49 +000037#include "llvm/IR/Metadata.h"
38#include "llvm/IR/Module.h"
39#include "llvm/IR/PassManager.h"
40#include "llvm/IR/Type.h"
41#include "llvm/IR/Use.h"
42#include "llvm/IR/User.h"
43#include "llvm/IR/Value.h"
44#include "llvm/Pass.h"
45#include "llvm/Support/BlockFrequency.h"
46#include "llvm/Support/BranchProbability.h"
47#include "llvm/Support/Debug.h"
48#include "llvm/Support/raw_ostream.h"
49#include "llvm/Transforms/IPO.h"
Aditya Kumar9e20ade2018-10-03 05:55:20 +000050#include "llvm/Transforms/IPO/HotColdSplitting.h"
Aditya Kumar801394a2018-09-07 15:03:49 +000051#include "llvm/Transforms/Scalar.h"
52#include "llvm/Transforms/Utils/BasicBlockUtils.h"
53#include "llvm/Transforms/Utils/Cloning.h"
54#include "llvm/Transforms/Utils/CodeExtractor.h"
55#include "llvm/Transforms/Utils/Local.h"
56#include "llvm/Transforms/Utils/SSAUpdater.h"
57#include "llvm/Transforms/Utils/ValueMapper.h"
58#include <algorithm>
59#include <cassert>
60
61#define DEBUG_TYPE "hotcoldsplit"
62
Vedant Kumarc2990062018-10-24 22:15:41 +000063STATISTIC(NumColdRegionsFound, "Number of cold regions found.");
64STATISTIC(NumColdRegionsOutlined, "Number of cold regions outlined.");
Aditya Kumar801394a2018-09-07 15:03:49 +000065
66using namespace llvm;
67
68static cl::opt<bool> EnableStaticAnalyis("hot-cold-static-analysis",
69 cl::init(true), cl::Hidden);
70
Vedant Kumard2a895a2018-11-04 23:11:57 +000071static cl::opt<int>
72 MinOutliningThreshold("min-outlining-thresh", cl::init(3), cl::Hidden,
73 cl::desc("Code size threshold for outlining within a "
74 "single BB (as a multiple of TCC_Basic)"));
Aditya Kumar801394a2018-09-07 15:03:49 +000075
76namespace {
77
78struct PostDomTree : PostDomTreeBase<BasicBlock> {
79 PostDomTree(Function &F) { recalculate(F); }
80};
81
Vedant Kumarc2990062018-10-24 22:15:41 +000082/// A sequence of basic blocks.
83///
84/// A 0-sized SmallVector is slightly cheaper to move than a std::vector.
85using BlockSequence = SmallVector<BasicBlock *, 0>;
Aditya Kumar801394a2018-09-07 15:03:49 +000086
Sebastian Pop542e5222018-10-15 21:43:11 +000087// Same as blockEndsInUnreachable in CodeGen/BranchFolding.cpp. Do not modify
88// this function unless you modify the MBB version as well.
89//
90/// A no successor, non-return block probably ends in unreachable and is cold.
91/// Also consider a block that ends in an indirect branch to be a return block,
92/// since many targets use plain indirect branches to return.
Aditya Kumar801394a2018-09-07 15:03:49 +000093bool blockEndsInUnreachable(const BasicBlock &BB) {
Sebastian Pop542e5222018-10-15 21:43:11 +000094 if (!succ_empty(&BB))
95 return false;
Aditya Kumar801394a2018-09-07 15:03:49 +000096 if (BB.empty())
97 return true;
Chandler Carruthedb12a82018-10-15 10:04:59 +000098 const Instruction *I = BB.getTerminator();
Sebastian Pop542e5222018-10-15 21:43:11 +000099 return !(isa<ReturnInst>(I) || isa<IndirectBrInst>(I));
Aditya Kumar801394a2018-09-07 15:03:49 +0000100}
101
Vedant Kumar03f9f152018-12-07 20:24:04 +0000102bool unlikelyExecuted(BasicBlock &BB) {
Aditya Kumar801394a2018-09-07 15:03:49 +0000103 // Exception handling blocks are unlikely executed.
104 if (BB.isEHPad())
105 return true;
Vedant Kumar03f9f152018-12-07 20:24:04 +0000106
107 // The block is cold if it calls/invokes a cold function.
108 for (Instruction &I : BB)
109 if (auto CS = CallSite(&I))
110 if (CS.hasFnAttr(Attribute::Cold))
Aditya Kumar801394a2018-09-07 15:03:49 +0000111 return true;
112
Vedant Kumar03f9f152018-12-07 20:24:04 +0000113 // The block is cold if it has an unreachable terminator, unless it's
114 // preceded by a call to a (possibly warm) noreturn call (e.g. longjmp).
115 if (blockEndsInUnreachable(BB)) {
116 if (auto *CI =
117 dyn_cast_or_null<CallInst>(BB.getTerminator()->getPrevNode()))
118 if (CI->hasFnAttr(Attribute::NoReturn))
Aditya Kumar801394a2018-09-07 15:03:49 +0000119 return false;
Vedant Kumar03f9f152018-12-07 20:24:04 +0000120 return true;
121 }
122
Aditya Kumar801394a2018-09-07 15:03:49 +0000123 return false;
124}
125
Vedant Kumarc2990062018-10-24 22:15:41 +0000126/// Check whether it's safe to outline \p BB.
127static bool mayExtractBlock(const BasicBlock &BB) {
Vedant Kumarb3a7cae2018-12-11 18:05:31 +0000128 return !BB.hasAddressTaken() && !BB.isEHPad();
Sebastian Pop542e5222018-10-15 21:43:11 +0000129}
130
Vedant Kumar03aaa3e2018-12-07 20:23:52 +0000131/// Check whether \p Region is profitable to outline.
132static bool isProfitableToOutline(const BlockSequence &Region,
Vedant Kumard2a895a2018-11-04 23:11:57 +0000133 TargetTransformInfo &TTI) {
Vedant Kumar03aaa3e2018-12-07 20:23:52 +0000134 if (Region.size() > 1)
135 return true;
136
Vedant Kumard2a895a2018-11-04 23:11:57 +0000137 int Cost = 0;
Vedant Kumar03aaa3e2018-12-07 20:23:52 +0000138 const BasicBlock &BB = *Region[0];
Vedant Kumardd4be532018-10-29 19:15:39 +0000139 for (const Instruction &I : BB) {
140 if (isa<DbgInfoIntrinsic>(&I) || &I == BB.getTerminator())
141 continue;
Vedant Kumard2a895a2018-11-04 23:11:57 +0000142
143 Cost += TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize);
144
145 if (Cost >= (MinOutliningThreshold * TargetTransformInfo::TCC_Basic))
Vedant Kumardd4be532018-10-29 19:15:39 +0000146 return true;
147 }
148 return false;
149}
150
Vedant Kumar03aaa3e2018-12-07 20:23:52 +0000151/// Mark \p F cold. Return true if it's changed.
152static bool markEntireFunctionCold(Function &F) {
153 assert(!F.hasFnAttribute(Attribute::OptimizeNone) && "Can't mark this cold");
154 bool Changed = false;
155 if (!F.hasFnAttribute(Attribute::MinSize)) {
156 F.addFnAttr(Attribute::MinSize);
157 Changed = true;
Aditya Kumar801394a2018-09-07 15:03:49 +0000158 }
Vedant Kumar03aaa3e2018-12-07 20:23:52 +0000159 // TODO: Move this function into a cold section.
160 return Changed;
Aditya Kumar801394a2018-09-07 15:03:49 +0000161}
162
163class HotColdSplitting {
164public:
165 HotColdSplitting(ProfileSummaryInfo *ProfSI,
166 function_ref<BlockFrequencyInfo *(Function &)> GBFI,
Sebastian Popa1f20fc2018-09-10 15:08:02 +0000167 function_ref<TargetTransformInfo &(Function &)> GTTI,
Aditya Kumar801394a2018-09-07 15:03:49 +0000168 std::function<OptimizationRemarkEmitter &(Function &)> *GORE)
Sebastian Popa1f20fc2018-09-10 15:08:02 +0000169 : PSI(ProfSI), GetBFI(GBFI), GetTTI(GTTI), GetORE(GORE) {}
Aditya Kumar801394a2018-09-07 15:03:49 +0000170 bool run(Module &M);
171
172private:
173 bool shouldOutlineFrom(const Function &F) const;
Vedant Kumar03aaa3e2018-12-07 20:23:52 +0000174 bool outlineColdRegions(Function &F, ProfileSummaryInfo &PSI,
175 BlockFrequencyInfo *BFI, TargetTransformInfo &TTI,
176 DominatorTree &DT, PostDomTree &PDT,
177 OptimizationRemarkEmitter &ORE);
Vedant Kumarc2990062018-10-24 22:15:41 +0000178 Function *extractColdRegion(const BlockSequence &Region, DominatorTree &DT,
Vedant Kumard2a895a2018-11-04 23:11:57 +0000179 BlockFrequencyInfo *BFI, TargetTransformInfo &TTI,
Teresa Johnsonc8dba682018-10-24 18:53:47 +0000180 OptimizationRemarkEmitter &ORE, unsigned Count);
Aditya Kumar801394a2018-09-07 15:03:49 +0000181 SmallPtrSet<const Function *, 2> OutlinedFunctions;
182 ProfileSummaryInfo *PSI;
183 function_ref<BlockFrequencyInfo *(Function &)> GetBFI;
Sebastian Popa1f20fc2018-09-10 15:08:02 +0000184 function_ref<TargetTransformInfo &(Function &)> GetTTI;
Aditya Kumar801394a2018-09-07 15:03:49 +0000185 std::function<OptimizationRemarkEmitter &(Function &)> *GetORE;
186};
187
188class HotColdSplittingLegacyPass : public ModulePass {
189public:
190 static char ID;
191 HotColdSplittingLegacyPass() : ModulePass(ID) {
192 initializeHotColdSplittingLegacyPassPass(*PassRegistry::getPassRegistry());
193 }
194
195 void getAnalysisUsage(AnalysisUsage &AU) const override {
196 AU.addRequired<AssumptionCacheTracker>();
197 AU.addRequired<BlockFrequencyInfoWrapperPass>();
198 AU.addRequired<ProfileSummaryInfoWrapperPass>();
Sebastian Popa1f20fc2018-09-10 15:08:02 +0000199 AU.addRequired<TargetTransformInfoWrapperPass>();
Aditya Kumar801394a2018-09-07 15:03:49 +0000200 }
201
202 bool runOnModule(Module &M) override;
203};
204
205} // end anonymous namespace
206
207// Returns false if the function should not be considered for hot-cold split
Sebastian Pop0f30f082018-09-14 20:36:19 +0000208// optimization.
Aditya Kumar801394a2018-09-07 15:03:49 +0000209bool HotColdSplitting::shouldOutlineFrom(const Function &F) const {
Sebastian Pop0f30f082018-09-14 20:36:19 +0000210 // Do not try to outline again from an already outlined cold function.
211 if (OutlinedFunctions.count(&F))
212 return false;
213
Aditya Kumar801394a2018-09-07 15:03:49 +0000214 if (F.size() <= 2)
215 return false;
216
Vedant Kumarc2990062018-10-24 22:15:41 +0000217 // TODO: Consider only skipping functions marked `optnone` or `cold`.
218
Aditya Kumar801394a2018-09-07 15:03:49 +0000219 if (F.hasAddressTaken())
220 return false;
221
222 if (F.hasFnAttribute(Attribute::AlwaysInline))
223 return false;
224
225 if (F.hasFnAttribute(Attribute::NoInline))
226 return false;
227
228 if (F.getCallingConv() == CallingConv::Cold)
229 return false;
230
231 if (PSI->isFunctionEntryCold(&F))
232 return false;
233 return true;
234}
235
Vedant Kumarc2990062018-10-24 22:15:41 +0000236Function *HotColdSplitting::extractColdRegion(const BlockSequence &Region,
237 DominatorTree &DT,
238 BlockFrequencyInfo *BFI,
Vedant Kumard2a895a2018-11-04 23:11:57 +0000239 TargetTransformInfo &TTI,
Vedant Kumarc2990062018-10-24 22:15:41 +0000240 OptimizationRemarkEmitter &ORE,
241 unsigned Count) {
Teresa Johnsonf431a2f2018-10-22 19:06:42 +0000242 assert(!Region.empty());
Sebastian Pop12171602018-09-14 20:36:10 +0000243
Aditya Kumar801394a2018-09-07 15:03:49 +0000244 // TODO: Pass BFI and BPI to update profile information.
Vedant Kumarc2990062018-10-24 22:15:41 +0000245 CodeExtractor CE(Region, &DT, /* AggregateArgs */ false, /* BFI */ nullptr,
Teresa Johnsonc8dba682018-10-24 18:53:47 +0000246 /* BPI */ nullptr, /* AllowVarArgs */ false,
247 /* AllowAlloca */ false,
248 /* Suffix */ "cold." + std::to_string(Count));
Aditya Kumar801394a2018-09-07 15:03:49 +0000249
250 SetVector<Value *> Inputs, Outputs, Sinks;
251 CE.findInputsOutputs(Inputs, Outputs, Sinks);
252
253 // Do not extract regions that have live exit variables.
Vedant Kumarc2990062018-10-24 22:15:41 +0000254 if (Outputs.size() > 0) {
255 LLVM_DEBUG(llvm::dbgs() << "Not outlining; live outputs\n");
Aditya Kumar801394a2018-09-07 15:03:49 +0000256 return nullptr;
Vedant Kumarc2990062018-10-24 22:15:41 +0000257 }
Aditya Kumar801394a2018-09-07 15:03:49 +0000258
Vedant Kumarc2990062018-10-24 22:15:41 +0000259 // TODO: Run MergeBasicBlockIntoOnlyPred on the outlined function.
Teresa Johnsonf431a2f2018-10-22 19:06:42 +0000260 Function *OrigF = Region[0]->getParent();
Aditya Kumar801394a2018-09-07 15:03:49 +0000261 if (Function *OutF = CE.extractCodeRegion()) {
262 User *U = *OutF->user_begin();
263 CallInst *CI = cast<CallInst>(U);
264 CallSite CS(CI);
Vedant Kumarc2990062018-10-24 22:15:41 +0000265 NumColdRegionsOutlined++;
Vedant Kumard2a895a2018-11-04 23:11:57 +0000266 if (TTI.useColdCCForColdCall(*OutF)) {
Sebastian Popa1f20fc2018-09-10 15:08:02 +0000267 OutF->setCallingConv(CallingConv::Cold);
268 CS.setCallingConv(CallingConv::Cold);
269 }
Aditya Kumar801394a2018-09-07 15:03:49 +0000270 CI->setIsNoInline();
Vedant Kumar50315462018-10-23 19:41:12 +0000271
272 // Try to make the outlined code as small as possible on the assumption
273 // that it's cold.
Vedant Kumar03aaa3e2018-12-07 20:23:52 +0000274 markEntireFunctionCold(*OutF);
Vedant Kumar50315462018-10-23 19:41:12 +0000275
Sebastian Pop0f30f082018-09-14 20:36:19 +0000276 LLVM_DEBUG(llvm::dbgs() << "Outlined Region: " << *OutF);
Teresa Johnsonf431a2f2018-10-22 19:06:42 +0000277 ORE.emit([&]() {
278 return OptimizationRemark(DEBUG_TYPE, "HotColdSplit",
279 &*Region[0]->begin())
280 << ore::NV("Original", OrigF) << " split cold code into "
281 << ore::NV("Split", OutF);
282 });
Aditya Kumar801394a2018-09-07 15:03:49 +0000283 return OutF;
284 }
285
286 ORE.emit([&]() {
287 return OptimizationRemarkMissed(DEBUG_TYPE, "ExtractFailed",
288 &*Region[0]->begin())
289 << "Failed to extract region at block "
290 << ore::NV("Block", Region.front());
291 });
292 return nullptr;
293}
294
Vedant Kumar03aaa3e2018-12-07 20:23:52 +0000295/// A pair of (basic block, score).
296using BlockTy = std::pair<BasicBlock *, unsigned>;
297
298/// A maximal outlining region. This contains all blocks post-dominated by a
299/// sink block, the sink block itself, and all blocks dominated by the sink.
300class OutliningRegion {
301 /// A list of (block, score) pairs. A block's score is non-zero iff it's a
302 /// viable sub-region entry point. Blocks with higher scores are better entry
303 /// points (i.e. they are more distant ancestors of the sink block).
304 SmallVector<BlockTy, 0> Blocks = {};
305
306 /// The suggested entry point into the region. If the region has multiple
307 /// entry points, all blocks within the region may not be reachable from this
308 /// entry point.
309 BasicBlock *SuggestedEntryPoint = nullptr;
310
311 /// Whether the entire function is cold.
312 bool EntireFunctionCold = false;
313
314 /// Whether or not \p BB could be the entry point of an extracted region.
315 static bool isViableEntryPoint(BasicBlock &BB) { return !BB.isEHPad(); }
316
317 /// If \p BB is a viable entry point, return \p Score. Return 0 otherwise.
318 static unsigned getEntryPointScore(BasicBlock &BB, unsigned Score) {
319 return isViableEntryPoint(BB) ? Score : 0;
320 }
321
322 /// These scores should be lower than the score for predecessor blocks,
323 /// because regions starting at predecessor blocks are typically larger.
324 static constexpr unsigned ScoreForSuccBlock = 1;
325 static constexpr unsigned ScoreForSinkBlock = 1;
326
327 OutliningRegion(const OutliningRegion &) = delete;
328 OutliningRegion &operator=(const OutliningRegion &) = delete;
329
330public:
331 OutliningRegion() = default;
332 OutliningRegion(OutliningRegion &&) = default;
333 OutliningRegion &operator=(OutliningRegion &&) = default;
334
335 static OutliningRegion create(BasicBlock &SinkBB, const DominatorTree &DT,
336 const PostDomTree &PDT) {
337 OutliningRegion ColdRegion;
338
339 SmallPtrSet<BasicBlock *, 4> RegionBlocks;
340
341 auto addBlockToRegion = [&](BasicBlock *BB, unsigned Score) {
342 RegionBlocks.insert(BB);
343 ColdRegion.Blocks.emplace_back(BB, Score);
344 assert(RegionBlocks.size() == ColdRegion.Blocks.size() && "Duplicate BB");
345 };
346
347 // The ancestor farthest-away from SinkBB, and also post-dominated by it.
348 unsigned SinkScore = getEntryPointScore(SinkBB, ScoreForSinkBlock);
349 ColdRegion.SuggestedEntryPoint = (SinkScore > 0) ? &SinkBB : nullptr;
350 unsigned BestScore = SinkScore;
351
352 // Visit SinkBB's ancestors using inverse DFS.
353 auto PredIt = ++idf_begin(&SinkBB);
354 auto PredEnd = idf_end(&SinkBB);
355 while (PredIt != PredEnd) {
356 BasicBlock &PredBB = **PredIt;
357 bool SinkPostDom = PDT.dominates(&SinkBB, &PredBB);
358
359 // If the predecessor is cold and has no predecessors, the entire
360 // function must be cold.
361 if (SinkPostDom && pred_empty(&PredBB)) {
362 ColdRegion.EntireFunctionCold = true;
363 return ColdRegion;
364 }
365
366 // If SinkBB does not post-dominate a predecessor, do not mark the
367 // predecessor (or any of its predecessors) cold.
368 if (!SinkPostDom || !mayExtractBlock(PredBB)) {
369 PredIt.skipChildren();
370 continue;
371 }
372
373 // Keep track of the post-dominated ancestor farthest away from the sink.
374 // The path length is always >= 2, ensuring that predecessor blocks are
375 // considered as entry points before the sink block.
376 unsigned PredScore = getEntryPointScore(PredBB, PredIt.getPathLength());
377 if (PredScore > BestScore) {
378 ColdRegion.SuggestedEntryPoint = &PredBB;
379 BestScore = PredScore;
380 }
381
382 addBlockToRegion(&PredBB, PredScore);
383 ++PredIt;
Vedant Kumarc2990062018-10-24 22:15:41 +0000384 }
385
Vedant Kumar03aaa3e2018-12-07 20:23:52 +0000386 // Add SinkBB to the cold region. It's considered as an entry point before
387 // any sink-successor blocks.
388 addBlockToRegion(&SinkBB, SinkScore);
389
390 // Find all successors of SinkBB dominated by SinkBB using DFS.
391 auto SuccIt = ++df_begin(&SinkBB);
392 auto SuccEnd = df_end(&SinkBB);
393 while (SuccIt != SuccEnd) {
394 BasicBlock &SuccBB = **SuccIt;
395 bool SinkDom = DT.dominates(&SinkBB, &SuccBB);
396
397 // Don't allow the backwards & forwards DFSes to mark the same block.
398 bool DuplicateBlock = RegionBlocks.count(&SuccBB);
399
400 // If SinkBB does not dominate a successor, do not mark the successor (or
401 // any of its successors) cold.
402 if (DuplicateBlock || !SinkDom || !mayExtractBlock(SuccBB)) {
403 SuccIt.skipChildren();
404 continue;
405 }
406
407 unsigned SuccScore = getEntryPointScore(SuccBB, ScoreForSuccBlock);
408 if (SuccScore > BestScore) {
409 ColdRegion.SuggestedEntryPoint = &SuccBB;
410 BestScore = SuccScore;
411 }
412
413 addBlockToRegion(&SuccBB, SuccScore);
414 ++SuccIt;
415 }
416
417 return ColdRegion;
418 }
419
420 /// Whether this region has nothing to extract.
421 bool empty() const { return !SuggestedEntryPoint; }
422
423 /// The blocks in this region.
424 ArrayRef<std::pair<BasicBlock *, unsigned>> blocks() const { return Blocks; }
425
426 /// Whether the entire function containing this region is cold.
427 bool isEntireFunctionCold() const { return EntireFunctionCold; }
428
429 /// Remove a sub-region from this region and return it as a block sequence.
430 BlockSequence takeSingleEntrySubRegion(DominatorTree &DT) {
431 assert(!empty() && !isEntireFunctionCold() && "Nothing to extract");
432
433 // Remove blocks dominated by the suggested entry point from this region.
434 // During the removal, identify the next best entry point into the region.
435 // Ensure that the first extracted block is the suggested entry point.
436 BlockSequence SubRegion = {SuggestedEntryPoint};
437 BasicBlock *NextEntryPoint = nullptr;
438 unsigned NextScore = 0;
439 auto RegionEndIt = Blocks.end();
440 auto RegionStartIt = remove_if(Blocks, [&](const BlockTy &Block) {
441 BasicBlock *BB = Block.first;
442 unsigned Score = Block.second;
443 bool InSubRegion =
444 BB == SuggestedEntryPoint || DT.dominates(SuggestedEntryPoint, BB);
445 if (!InSubRegion && Score > NextScore) {
446 NextEntryPoint = BB;
447 NextScore = Score;
448 }
449 if (InSubRegion && BB != SuggestedEntryPoint)
450 SubRegion.push_back(BB);
451 return InSubRegion;
452 });
453 Blocks.erase(RegionStartIt, RegionEndIt);
454
455 // Update the suggested entry point.
456 SuggestedEntryPoint = NextEntryPoint;
457
458 return SubRegion;
459 }
460};
461
462bool HotColdSplitting::outlineColdRegions(Function &F, ProfileSummaryInfo &PSI,
463 BlockFrequencyInfo *BFI,
464 TargetTransformInfo &TTI,
465 DominatorTree &DT, PostDomTree &PDT,
466 OptimizationRemarkEmitter &ORE) {
467 bool Changed = false;
468
469 // The set of cold blocks.
470 SmallPtrSet<BasicBlock *, 4> ColdBlocks;
471
472 // The worklist of non-intersecting regions left to outline.
473 SmallVector<OutliningRegion, 2> OutliningWorklist;
474
475 // Set up an RPO traversal. Experimentally, this performs better (outlines
476 // more) than a PO traversal, because we prevent region overlap by keeping
477 // the first region to contain a block.
478 ReversePostOrderTraversal<Function *> RPOT(&F);
479
480 // Find all cold regions.
481 for (BasicBlock *BB : RPOT) {
482 // Skip blocks which can't be outlined.
483 if (!mayExtractBlock(*BB))
484 continue;
485
486 // This block is already part of some outlining region.
487 if (ColdBlocks.count(BB))
488 continue;
489
490 bool Cold = PSI.isColdBlock(BB, BFI) ||
491 (EnableStaticAnalyis && unlikelyExecuted(*BB));
492 if (!Cold)
493 continue;
494
495 LLVM_DEBUG({
496 dbgs() << "Found a cold block:\n";
497 BB->dump();
498 });
499
500 auto Region = OutliningRegion::create(*BB, DT, PDT);
501 if (Region.empty())
502 continue;
503
504 if (Region.isEntireFunctionCold()) {
505 LLVM_DEBUG(dbgs() << "Entire function is cold\n");
506 return markEntireFunctionCold(F);
507 }
508
509 // If this outlining region intersects with another, drop the new region.
510 //
511 // TODO: It's theoretically possible to outline more by only keeping the
512 // largest region which contains a block, but the extra bookkeeping to do
513 // this is tricky/expensive.
514 bool RegionsOverlap = any_of(Region.blocks(), [&](const BlockTy &Block) {
515 return !ColdBlocks.insert(Block.first).second;
516 });
517 if (RegionsOverlap)
518 continue;
519
520 OutliningWorklist.emplace_back(std::move(Region));
521 ++NumColdRegionsFound;
522 }
523
524 // Outline single-entry cold regions, splitting up larger regions as needed.
525 unsigned OutlinedFunctionID = 1;
526 while (!OutliningWorklist.empty()) {
527 OutliningRegion Region = OutliningWorklist.pop_back_val();
528 assert(!Region.empty() && "Empty outlining region in worklist");
529 do {
530 BlockSequence SubRegion = Region.takeSingleEntrySubRegion(DT);
531 if (!isProfitableToOutline(SubRegion, TTI)) {
532 LLVM_DEBUG({
533 dbgs() << "Skipping outlining; not profitable to outline\n";
534 SubRegion[0]->dump();
535 });
536 continue;
537 }
538
539 LLVM_DEBUG({
540 dbgs() << "Hot/cold splitting attempting to outline these blocks:\n";
541 for (BasicBlock *BB : SubRegion)
542 BB->dump();
543 });
544
545 Function *Outlined =
546 extractColdRegion(SubRegion, DT, BFI, TTI, ORE, OutlinedFunctionID);
547 if (Outlined) {
548 ++OutlinedFunctionID;
549 OutlinedFunctions.insert(Outlined);
550 Changed = true;
551 }
552 } while (!Region.empty());
553 }
554
555 return Changed;
556}
557
558bool HotColdSplitting::run(Module &M) {
559 bool Changed = false;
560 OutlinedFunctions.clear();
561 for (auto &F : M) {
562 if (!shouldOutlineFrom(F)) {
563 LLVM_DEBUG(llvm::dbgs() << "Skipping " << F.getName() << "\n");
564 continue;
565 }
Vedant Kumarc2990062018-10-24 22:15:41 +0000566 LLVM_DEBUG(llvm::dbgs() << "Outlining in " << F.getName() << "\n");
Aditya Kumar801394a2018-09-07 15:03:49 +0000567 DominatorTree DT(F);
568 PostDomTree PDT(F);
569 PDT.recalculate(F);
Vedant Kumarc2990062018-10-24 22:15:41 +0000570 BlockFrequencyInfo *BFI = GetBFI(F);
Vedant Kumard2a895a2018-11-04 23:11:57 +0000571 TargetTransformInfo &TTI = GetTTI(F);
Vedant Kumarc2990062018-10-24 22:15:41 +0000572 OptimizationRemarkEmitter &ORE = (*GetORE)(F);
Vedant Kumar03aaa3e2018-12-07 20:23:52 +0000573 Changed |= outlineColdRegions(F, *PSI, BFI, TTI, DT, PDT, ORE);
Aditya Kumar801394a2018-09-07 15:03:49 +0000574 }
Vedant Kumarc2990062018-10-24 22:15:41 +0000575 return Changed;
Aditya Kumar801394a2018-09-07 15:03:49 +0000576}
577
578bool HotColdSplittingLegacyPass::runOnModule(Module &M) {
579 if (skipModule(M))
580 return false;
581 ProfileSummaryInfo *PSI =
Vedant Kumare7b789b2018-11-19 05:23:16 +0000582 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
Sebastian Popa1f20fc2018-09-10 15:08:02 +0000583 auto GTTI = [this](Function &F) -> TargetTransformInfo & {
584 return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
585 };
Aditya Kumar801394a2018-09-07 15:03:49 +0000586 auto GBFI = [this](Function &F) {
587 return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
588 };
589 std::unique_ptr<OptimizationRemarkEmitter> ORE;
590 std::function<OptimizationRemarkEmitter &(Function &)> GetORE =
591 [&ORE](Function &F) -> OptimizationRemarkEmitter & {
592 ORE.reset(new OptimizationRemarkEmitter(&F));
593 return *ORE.get();
594 };
595
Sebastian Popa1f20fc2018-09-10 15:08:02 +0000596 return HotColdSplitting(PSI, GBFI, GTTI, &GetORE).run(M);
Aditya Kumar801394a2018-09-07 15:03:49 +0000597}
598
Aditya Kumar9e20ade2018-10-03 05:55:20 +0000599PreservedAnalyses
600HotColdSplittingPass::run(Module &M, ModuleAnalysisManager &AM) {
601 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
602
603 std::function<AssumptionCache &(Function &)> GetAssumptionCache =
604 [&FAM](Function &F) -> AssumptionCache & {
605 return FAM.getResult<AssumptionAnalysis>(F);
606 };
607
608 auto GBFI = [&FAM](Function &F) {
609 return &FAM.getResult<BlockFrequencyAnalysis>(F);
610 };
611
612 std::function<TargetTransformInfo &(Function &)> GTTI =
613 [&FAM](Function &F) -> TargetTransformInfo & {
614 return FAM.getResult<TargetIRAnalysis>(F);
615 };
616
617 std::unique_ptr<OptimizationRemarkEmitter> ORE;
618 std::function<OptimizationRemarkEmitter &(Function &)> GetORE =
619 [&ORE](Function &F) -> OptimizationRemarkEmitter & {
620 ORE.reset(new OptimizationRemarkEmitter(&F));
621 return *ORE.get();
622 };
623
624 ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(M);
625
626 if (HotColdSplitting(PSI, GBFI, GTTI, &GetORE).run(M))
627 return PreservedAnalyses::none();
628 return PreservedAnalyses::all();
629}
630
Aditya Kumar801394a2018-09-07 15:03:49 +0000631char HotColdSplittingLegacyPass::ID = 0;
632INITIALIZE_PASS_BEGIN(HotColdSplittingLegacyPass, "hotcoldsplit",
633 "Hot Cold Splitting", false, false)
634INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
635INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
636INITIALIZE_PASS_END(HotColdSplittingLegacyPass, "hotcoldsplit",
637 "Hot Cold Splitting", false, false)
638
639ModulePass *llvm::createHotColdSplittingPass() {
640 return new HotColdSplittingLegacyPass();
641}