1//===- PartialInlining.cpp - Inline parts of functions --------------------===//
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// This pass performs partial inlining, typically by inlining an if statement
10// that surrounds the body of the function.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Transforms/IPO/PartialInlining.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/DenseSet.h"
17#include "llvm/ADT/DepthFirstIterator.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/Analysis/BlockFrequencyInfo.h"
22#include "llvm/Analysis/BranchProbabilityInfo.h"
23#include "llvm/Analysis/InlineCost.h"
24#include "llvm/Analysis/LoopInfo.h"
25#include "llvm/Analysis/OptimizationRemarkEmitter.h"
26#include "llvm/Analysis/ProfileSummaryInfo.h"
27#include "llvm/Analysis/TargetLibraryInfo.h"
28#include "llvm/Analysis/TargetTransformInfo.h"
29#include "llvm/IR/Attributes.h"
30#include "llvm/IR/BasicBlock.h"
31#include "llvm/IR/CFG.h"
32#include "llvm/IR/CycleInfo.h"
33#include "llvm/IR/DebugLoc.h"
34#include "llvm/IR/DiagnosticInfo.h"
35#include "llvm/IR/Dominators.h"
36#include "llvm/IR/Function.h"
37#include "llvm/IR/InstrTypes.h"
38#include "llvm/IR/Instruction.h"
39#include "llvm/IR/Instructions.h"
40#include "llvm/IR/IntrinsicInst.h"
41#include "llvm/IR/Intrinsics.h"
42#include "llvm/IR/Module.h"
43#include "llvm/IR/Operator.h"
44#include "llvm/IR/ProfDataUtils.h"
45#include "llvm/IR/User.h"
46#include "llvm/Support/BlockFrequency.h"
47#include "llvm/Support/BranchProbability.h"
48#include "llvm/Support/Casting.h"
49#include "llvm/Support/CommandLine.h"
50#include "llvm/Support/ErrorHandling.h"
51#include "llvm/Transforms/IPO.h"
52#include "llvm/Transforms/Utils/Cloning.h"
53#include "llvm/Transforms/Utils/CodeExtractor.h"
54#include "llvm/Transforms/Utils/ValueMapper.h"
55#include <algorithm>
56#include <cassert>
57#include <cstdint>
58#include <memory>
59#include <tuple>
60#include <vector>
61
62using namespace llvm;
63
64#define DEBUG_TYPE "partial-inlining"
65
66STATISTIC(NumPartialInlined,
67 "Number of callsites functions partially inlined into.");
68STATISTIC(NumColdOutlinePartialInlined, "Number of times functions with "
69 "cold outlined regions were partially "
70 "inlined into its caller(s).");
71STATISTIC(NumColdRegionsFound,
72 "Number of cold single entry/exit regions found.");
73STATISTIC(NumColdRegionsOutlined,
74 "Number of cold single entry/exit regions outlined.");
75
76// Command line option to disable partial-inlining. The default is false:
77static cl::opt<bool>
78 DisablePartialInlining("disable-partial-inlining", cl::init(Val: false),
79 cl::Hidden, cl::desc("Disable partial inlining"));
80// Command line option to disable multi-region partial-inlining. The default is
81// false:
82static cl::opt<bool> DisableMultiRegionPartialInline(
83 "disable-mr-partial-inlining", cl::init(Val: false), cl::Hidden,
84 cl::desc("Disable multi-region partial inlining"));
85
86// Command line option to force outlining in regions with live exit variables.
87// The default is false:
88static cl::opt<bool>
89 ForceLiveExit("pi-force-live-exit-outline", cl::init(Val: false), cl::Hidden,
90 cl::desc("Force outline regions with live exits"));
91
92// Command line option to enable marking outline functions with Cold Calling
93// Convention. The default is false:
94static cl::opt<bool>
95 MarkOutlinedColdCC("pi-mark-coldcc", cl::init(Val: false), cl::Hidden,
96 cl::desc("Mark outline function calls with ColdCC"));
97
98// This is an option used by testing:
99static cl::opt<bool> SkipCostAnalysis("skip-partial-inlining-cost-analysis",
100
101 cl::ReallyHidden,
102 cl::desc("Skip Cost Analysis"));
103// Used to determine if a cold region is worth outlining based on
104// its inlining cost compared to the original function. Default is set at 10%.
105// ie. if the cold region reduces the inlining cost of the original function by
106// at least 10%.
107static cl::opt<float> MinRegionSizeRatio(
108 "min-region-size-ratio", cl::init(Val: 0.1), cl::Hidden,
109 cl::desc("Minimum ratio comparing relative sizes of each "
110 "outline candidate and original function"));
111// Used to tune the minimum number of execution counts needed in the predecessor
112// block to the cold edge. ie. confidence interval.
113cl::opt<unsigned>
114 MinBlockCounterExecution("min-block-execution", cl::init(Val: 100), cl::Hidden,
115 cl::desc("Minimum block executions to consider "
116 "its BranchProbabilityInfo valid"));
117// Used to determine when an edge is considered cold. Default is set to 10%. ie.
118// if the branch probability is 10% or less, then it is deemed as 'cold'.
119static cl::opt<float> ColdBranchRatio(
120 "cold-branch-ratio", cl::init(Val: 0.1), cl::Hidden,
121 cl::desc("Minimum BranchProbability to consider a region cold."));
122
123static cl::opt<unsigned> MaxNumInlineBlocks(
124 "max-num-inline-blocks", cl::init(Val: 5), cl::Hidden,
125 cl::desc("Max number of blocks to be partially inlined"));
126
127// Command line option to set the maximum number of partial inlining allowed
128// for the module. The default value of -1 means no limit.
129static cl::opt<int> MaxNumPartialInlining(
130 "max-partial-inlining", cl::init(Val: -1), cl::Hidden,
131 cl::desc("Max number of partial inlining. The default is unlimited"));
132
133// Used only when PGO or user annotated branch data is absent. It is
134// the least value that is used to weigh the outline region. If BFI
135// produces larger value, the BFI value will be used.
136static cl::opt<int>
137 OutlineRegionFreqPercent("outline-region-freq-percent", cl::init(Val: 75),
138 cl::Hidden,
139 cl::desc("Relative frequency of outline region to "
140 "the entry block"));
141
142static cl::opt<unsigned> ExtraOutliningPenalty(
143 "partial-inlining-extra-penalty", cl::init(Val: 0), cl::Hidden,
144 cl::desc("A debug option to add additional penalty to the computed one."));
145
146namespace {
147
148struct FunctionOutliningInfo {
149 FunctionOutliningInfo() = default;
150
151 // Returns the number of blocks to be inlined including all blocks
152 // in Entries and one return block.
153 unsigned getNumInlinedBlocks() const { return Entries.size() + 1; }
154
155 // A set of blocks including the function entry that guard
156 // the region to be outlined.
157 SmallVector<BasicBlock *, 4> Entries;
158
159 // The return block that is not included in the outlined region.
160 BasicBlock *ReturnBlock = nullptr;
161
162 // The dominating block of the region to be outlined.
163 BasicBlock *NonReturnBlock = nullptr;
164
165 // The set of blocks in Entries that are predecessors to ReturnBlock
166 SmallVector<BasicBlock *, 4> ReturnBlockPreds;
167};
168
169struct FunctionOutliningMultiRegionInfo {
170 FunctionOutliningMultiRegionInfo() = default;
171
172 // Container for outline regions
173 struct OutlineRegionInfo {
174 OutlineRegionInfo(ArrayRef<BasicBlock *> Region, BasicBlock *EntryBlock,
175 BasicBlock *ExitBlock, BasicBlock *ReturnBlock)
176 : Region(Region), EntryBlock(EntryBlock), ExitBlock(ExitBlock),
177 ReturnBlock(ReturnBlock) {}
178 SmallVector<BasicBlock *, 8> Region;
179 BasicBlock *EntryBlock;
180 BasicBlock *ExitBlock;
181 BasicBlock *ReturnBlock;
182 };
183
184 SmallVector<OutlineRegionInfo, 4> ORI;
185};
186
187struct PartialInlinerImpl {
188
189 PartialInlinerImpl(
190 function_ref<AssumptionCache &(Function &)> GetAC,
191 function_ref<AssumptionCache *(Function &)> LookupAC,
192 function_ref<TargetTransformInfo &(Function &)> GTTI,
193 function_ref<const TargetLibraryInfo &(Function &)> GTLI,
194 ProfileSummaryInfo &ProfSI,
195 function_ref<BlockFrequencyInfo &(Function &)> GBFI = nullptr)
196 : GetAssumptionCache(GetAC), LookupAssumptionCache(LookupAC),
197 GetTTI(GTTI), GetBFI(GBFI), GetTLI(GTLI), PSI(ProfSI) {}
198
199 bool run(Module &M);
200 // Main part of the transformation that calls helper functions to find
201 // outlining candidates, clone & outline the function, and attempt to
202 // partially inline the resulting function. Returns true if
203 // inlining was successful, false otherwise. Also returns the outline
204 // function (only if we partially inlined early returns) as there is a
205 // possibility to further "peel" early return statements that were left in the
206 // outline function due to code size.
207 std::pair<bool, Function *> unswitchFunction(Function &F);
208
209 // This class speculatively clones the function to be partial inlined.
210 // At the end of partial inlining, the remaining callsites to the cloned
211 // function that are not partially inlined will be fixed up to reference
212 // the original function, and the cloned function will be erased.
213 struct FunctionCloner {
214 // Two constructors, one for single region outlining, the other for
215 // multi-region outlining.
216 FunctionCloner(Function *F, FunctionOutliningInfo *OI,
217 OptimizationRemarkEmitter &ORE,
218 function_ref<AssumptionCache *(Function &)> LookupAC,
219 function_ref<TargetTransformInfo &(Function &)> GetTTI);
220 FunctionCloner(Function *F, FunctionOutliningMultiRegionInfo *OMRI,
221 OptimizationRemarkEmitter &ORE,
222 function_ref<AssumptionCache *(Function &)> LookupAC,
223 function_ref<TargetTransformInfo &(Function &)> GetTTI);
224
225 ~FunctionCloner();
226
227 // Prepare for function outlining: making sure there is only
228 // one incoming edge from the extracted/outlined region to
229 // the return block.
230 void normalizeReturnBlock() const;
231
232 // Do function outlining for cold regions.
233 bool doMultiRegionFunctionOutlining();
234 // Do function outlining for region after early return block(s).
235 // NOTE: For vararg functions that do the vararg handling in the outlined
236 // function, we temporarily generate IR that does not properly
237 // forward varargs to the outlined function. Calling InlineFunction
238 // will update calls to the outlined functions to properly forward
239 // the varargs.
240 Function *doSingleRegionFunctionOutlining();
241
242 Function *OrigFunc = nullptr;
243 Function *ClonedFunc = nullptr;
244
245 typedef std::pair<Function *, BasicBlock *> FuncBodyCallerPair;
246 // Keep track of Outlined Functions and the basic block they're called from.
247 SmallVector<FuncBodyCallerPair, 4> OutlinedFunctions;
248
249 // ClonedFunc is inlined in one of its callers after function
250 // outlining.
251 bool IsFunctionInlined = false;
252 // The cost of the region to be outlined.
253 InstructionCost OutlinedRegionCost = 0;
254 // ClonedOI is specific to outlining non-early return blocks.
255 std::unique_ptr<FunctionOutliningInfo> ClonedOI = nullptr;
256 // ClonedOMRI is specific to outlining cold regions.
257 std::unique_ptr<FunctionOutliningMultiRegionInfo> ClonedOMRI = nullptr;
258 std::unique_ptr<BlockFrequencyInfo> ClonedFuncBFI = nullptr;
259 OptimizationRemarkEmitter &ORE;
260 function_ref<AssumptionCache *(Function &)> LookupAC;
261 function_ref<TargetTransformInfo &(Function &)> GetTTI;
262 };
263
264private:
265 int NumPartialInlining = 0;
266 function_ref<AssumptionCache &(Function &)> GetAssumptionCache;
267 function_ref<AssumptionCache *(Function &)> LookupAssumptionCache;
268 function_ref<TargetTransformInfo &(Function &)> GetTTI;
269 function_ref<BlockFrequencyInfo &(Function &)> GetBFI;
270 function_ref<const TargetLibraryInfo &(Function &)> GetTLI;
271 ProfileSummaryInfo &PSI;
272
273 // Return the frequency of the OutlininingBB relative to F's entry point.
274 // The result is no larger than 1 and is represented using BP.
275 // (Note that the outlined region's 'head' block can only have incoming
276 // edges from the guarding entry blocks).
277 BranchProbability
278 getOutliningCallBBRelativeFreq(FunctionCloner &Cloner) const;
279
280 // Return true if the callee of CB should be partially inlined with
281 // profit.
282 bool shouldPartialInline(CallBase &CB, FunctionCloner &Cloner,
283 BlockFrequency WeightedOutliningRcost,
284 OptimizationRemarkEmitter &ORE) const;
285
286 // Try to inline DuplicateFunction (cloned from F with call to
287 // the OutlinedFunction into its callers. Return true
288 // if there is any successful inlining.
289 bool tryPartialInline(FunctionCloner &Cloner);
290
291 // Compute the mapping from use site of DuplicationFunction to the enclosing
292 // BB's profile count.
293 void
294 computeCallsiteToProfCountMap(Function *DuplicateFunction,
295 DenseMap<User *, uint64_t> &SiteCountMap) const;
296
297 bool isLimitReached() const {
298 return (MaxNumPartialInlining != -1 &&
299 NumPartialInlining >= MaxNumPartialInlining);
300 }
301
302 static CallBase *getSupportedCallBase(User *U) {
303 if (isa<CallInst>(Val: U) || isa<InvokeInst>(Val: U))
304 return cast<CallBase>(Val: U);
305 llvm_unreachable("All uses must be calls");
306 return nullptr;
307 }
308
309 static CallBase *getOneCallSiteTo(Function &F) {
310 User *User = *F.user_begin();
311 return getSupportedCallBase(U: User);
312 }
313
314 std::tuple<DebugLoc, BasicBlock *> getOneDebugLoc(Function &F) const {
315 CallBase *CB = getOneCallSiteTo(F);
316 DebugLoc DLoc = CB->getDebugLoc();
317 BasicBlock *Block = CB->getParent();
318 return std::make_tuple(args&: DLoc, args&: Block);
319 }
320
321 // Returns the costs associated with function outlining:
322 // - The first value is the non-weighted runtime cost for making the call
323 // to the outlined function, including the addtional setup cost in the
324 // outlined function itself;
325 // - The second value is the estimated size of the new call sequence in
326 // basic block Cloner.OutliningCallBB;
327 std::tuple<InstructionCost, InstructionCost>
328 computeOutliningCosts(FunctionCloner &Cloner) const;
329
330 // Compute the 'InlineCost' of block BB. InlineCost is a proxy used to
331 // approximate both the size and runtime cost (Note that in the current
332 // inline cost analysis, there is no clear distinction there either).
333 static InstructionCost computeBBInlineCost(BasicBlock *BB,
334 TargetTransformInfo *TTI);
335
336 std::unique_ptr<FunctionOutliningInfo>
337 computeOutliningInfo(Function &F) const;
338
339 std::unique_ptr<FunctionOutliningMultiRegionInfo>
340 computeOutliningColdRegionsInfo(Function &F,
341 OptimizationRemarkEmitter &ORE) const;
342};
343
344} // end anonymous namespace
345
346std::unique_ptr<FunctionOutliningMultiRegionInfo>
347PartialInlinerImpl::computeOutliningColdRegionsInfo(
348 Function &F, OptimizationRemarkEmitter &ORE) const {
349 BasicBlock *EntryBlock = &F.front();
350
351 DominatorTree DT(F);
352 CycleInfo CI;
353 CI.compute(F);
354 LoopInfo LI(DT);
355 BranchProbabilityInfo BPI(F, CI);
356 std::unique_ptr<BlockFrequencyInfo> ScopedBFI;
357 BlockFrequencyInfo *BFI;
358 if (!GetBFI) {
359 ScopedBFI.reset(p: new BlockFrequencyInfo(F, BPI, LI));
360 BFI = ScopedBFI.get();
361 } else
362 BFI = &(GetBFI(F));
363
364 // Return if we don't have profiling information.
365 if (!PSI.hasInstrumentationProfile())
366 return std::unique_ptr<FunctionOutliningMultiRegionInfo>();
367
368 std::unique_ptr<FunctionOutliningMultiRegionInfo> OutliningInfo =
369 std::make_unique<FunctionOutliningMultiRegionInfo>();
370
371 auto IsSingleExit =
372 [&ORE](SmallVectorImpl<BasicBlock *> &BlockList) -> BasicBlock * {
373 BasicBlock *ExitBlock = nullptr;
374 for (auto *Block : BlockList) {
375 for (BasicBlock *Succ : successors(BB: Block)) {
376 if (!is_contained(Range&: BlockList, Element: Succ)) {
377 if (ExitBlock) {
378 ORE.emit(RemarkBuilder: [&]() {
379 return OptimizationRemarkMissed(DEBUG_TYPE, "MultiExitRegion",
380 &Succ->front())
381 << "Region dominated by "
382 << ore::NV("Block", BlockList.front()->getName())
383 << " has more than one region exit edge.";
384 });
385 return nullptr;
386 }
387
388 ExitBlock = Block;
389 }
390 }
391 }
392 return ExitBlock;
393 };
394
395 auto BBProfileCount = [BFI](BasicBlock *BB) {
396 return BFI->getBlockProfileCount(BB).value_or(u: 0);
397 };
398
399 // Use the same computeBBInlineCost function to compute the cost savings of
400 // the outlining the candidate region.
401 TargetTransformInfo *FTTI = &GetTTI(F);
402 InstructionCost OverallFunctionCost = 0;
403 for (auto &BB : F)
404 OverallFunctionCost += computeBBInlineCost(BB: &BB, TTI: FTTI);
405
406 LLVM_DEBUG(dbgs() << "OverallFunctionCost = " << OverallFunctionCost
407 << "\n";);
408
409 InstructionCost MinOutlineRegionCost = OverallFunctionCost.map(
410 F: [&](auto Cost) { return Cost * MinRegionSizeRatio; });
411
412 BranchProbability MinBranchProbability(
413 static_cast<int>(ColdBranchRatio * MinBlockCounterExecution),
414 MinBlockCounterExecution);
415 bool ColdCandidateFound = false;
416 BasicBlock *CurrEntry = EntryBlock;
417 std::vector<BasicBlock *> DFS;
418 SmallPtrSet<BasicBlock *, 8> VisitedSet;
419 DFS.push_back(x: CurrEntry);
420 VisitedSet.insert(Ptr: CurrEntry);
421
422 // Use Depth First Search on the basic blocks to find CFG edges that are
423 // considered cold.
424 // Cold regions considered must also have its inline cost compared to the
425 // overall inline cost of the original function. The region is outlined only
426 // if it reduced the inline cost of the function by 'MinOutlineRegionCost' or
427 // more.
428 while (!DFS.empty()) {
429 auto *ThisBB = DFS.back();
430 DFS.pop_back();
431 // Only consider regions with predecessor blocks that are considered
432 // not-cold (default: part of the top 99.99% of all block counters)
433 // AND greater than our minimum block execution count (default: 100).
434 if (PSI.isColdBlock(BB: ThisBB, BFI) ||
435 BBProfileCount(ThisBB) < MinBlockCounterExecution)
436 continue;
437 for (auto SI = succ_begin(BB: ThisBB); SI != succ_end(BB: ThisBB); ++SI) {
438 if (!VisitedSet.insert(Ptr: *SI).second)
439 continue;
440 DFS.push_back(x: *SI);
441 // If branch isn't cold, we skip to the next one.
442 BranchProbability SuccProb = BPI.getEdgeProbability(Src: ThisBB, Dst: *SI);
443 if (SuccProb > MinBranchProbability)
444 continue;
445
446 LLVM_DEBUG(dbgs() << "Found cold edge: " << ThisBB->getName() << "->"
447 << SI->getName()
448 << "\nBranch Probability = " << SuccProb << "\n";);
449
450 SmallVector<BasicBlock *, 8> DominateVector;
451 DT.getDescendants(R: *SI, Result&: DominateVector);
452 assert(!DominateVector.empty() &&
453 "SI should be reachable and have at least itself as descendant");
454
455 // We can only outline single entry regions (for now).
456 if (!DominateVector.front()->hasNPredecessors(N: 1)) {
457 LLVM_DEBUG(dbgs() << "ABORT: Block " << SI->getName()
458 << " doesn't have a single predecessor in the "
459 "dominator tree\n";);
460 continue;
461 }
462
463 BasicBlock *ExitBlock = nullptr;
464 // We can only outline single exit regions (for now).
465 if (!(ExitBlock = IsSingleExit(DominateVector))) {
466 LLVM_DEBUG(dbgs() << "ABORT: Block " << SI->getName()
467 << " doesn't have a unique successor\n";);
468 continue;
469 }
470
471 InstructionCost OutlineRegionCost = 0;
472 for (auto *BB : DominateVector)
473 OutlineRegionCost += computeBBInlineCost(BB, TTI: &GetTTI(*BB->getParent()));
474
475 LLVM_DEBUG(dbgs() << "OutlineRegionCost = " << OutlineRegionCost
476 << "\n";);
477
478 if (!SkipCostAnalysis && OutlineRegionCost < MinOutlineRegionCost) {
479 ORE.emit(RemarkBuilder: [&]() {
480 return OptimizationRemarkAnalysis(DEBUG_TYPE, "TooCostly",
481 &SI->front())
482 << ore::NV("Callee", &F)
483 << " inline cost-savings smaller than "
484 << ore::NV("Cost", MinOutlineRegionCost);
485 });
486
487 LLVM_DEBUG(dbgs() << "ABORT: Outline region cost is smaller than "
488 << MinOutlineRegionCost << "\n";);
489 continue;
490 }
491
492 // For now, ignore blocks that belong to a SISE region that is a
493 // candidate for outlining. In the future, we may want to look
494 // at inner regions because the outer region may have live-exit
495 // variables.
496 VisitedSet.insert_range(R&: DominateVector);
497
498 // ReturnBlock here means the block after the outline call
499 BasicBlock *ReturnBlock = ExitBlock->getSingleSuccessor();
500 FunctionOutliningMultiRegionInfo::OutlineRegionInfo RegInfo(
501 DominateVector, DominateVector.front(), ExitBlock, ReturnBlock);
502 OutliningInfo->ORI.push_back(Elt: RegInfo);
503 LLVM_DEBUG(dbgs() << "Found Cold Candidate starting at block: "
504 << DominateVector.front()->getName() << "\n";);
505 ColdCandidateFound = true;
506 NumColdRegionsFound++;
507 }
508 }
509
510 if (ColdCandidateFound)
511 return OutliningInfo;
512
513 return std::unique_ptr<FunctionOutliningMultiRegionInfo>();
514}
515
516std::unique_ptr<FunctionOutliningInfo>
517PartialInlinerImpl::computeOutliningInfo(Function &F) const {
518 BasicBlock *EntryBlock = &F.front();
519 CondBrInst *BR = dyn_cast<CondBrInst>(Val: EntryBlock->getTerminator());
520 if (!BR)
521 return std::unique_ptr<FunctionOutliningInfo>();
522
523 // Returns true if Succ is BB's successor
524 auto IsSuccessor = [](BasicBlock *Succ, BasicBlock *BB) {
525 return is_contained(Range: successors(BB), Element: Succ);
526 };
527
528 auto IsReturnBlock = [](BasicBlock *BB) {
529 Instruction *TI = BB->getTerminator();
530 return isa<ReturnInst>(Val: TI);
531 };
532
533 auto GetReturnBlock = [&](BasicBlock *Succ1, BasicBlock *Succ2) {
534 if (IsReturnBlock(Succ1))
535 return std::make_tuple(args&: Succ1, args&: Succ2);
536 if (IsReturnBlock(Succ2))
537 return std::make_tuple(args&: Succ2, args&: Succ1);
538
539 return std::make_tuple<BasicBlock *, BasicBlock *>(args: nullptr, args: nullptr);
540 };
541
542 // Detect a triangular shape:
543 auto GetCommonSucc = [&](BasicBlock *Succ1, BasicBlock *Succ2) {
544 if (IsSuccessor(Succ1, Succ2))
545 return std::make_tuple(args&: Succ1, args&: Succ2);
546 if (IsSuccessor(Succ2, Succ1))
547 return std::make_tuple(args&: Succ2, args&: Succ1);
548
549 return std::make_tuple<BasicBlock *, BasicBlock *>(args: nullptr, args: nullptr);
550 };
551
552 std::unique_ptr<FunctionOutliningInfo> OutliningInfo =
553 std::make_unique<FunctionOutliningInfo>();
554
555 BasicBlock *CurrEntry = EntryBlock;
556 bool CandidateFound = false;
557 do {
558 // The number of blocks to be inlined has already reached
559 // the limit. When MaxNumInlineBlocks is set to 0 or 1, this
560 // disables partial inlining for the function.
561 if (OutliningInfo->getNumInlinedBlocks() >= MaxNumInlineBlocks)
562 break;
563
564 if (succ_size(BB: CurrEntry) != 2)
565 break;
566
567 BasicBlock *Succ1 = *succ_begin(BB: CurrEntry);
568 BasicBlock *Succ2 = *(succ_begin(BB: CurrEntry) + 1);
569
570 BasicBlock *ReturnBlock, *NonReturnBlock;
571 std::tie(args&: ReturnBlock, args&: NonReturnBlock) = GetReturnBlock(Succ1, Succ2);
572
573 if (ReturnBlock) {
574 OutliningInfo->Entries.push_back(Elt: CurrEntry);
575 OutliningInfo->ReturnBlock = ReturnBlock;
576 OutliningInfo->NonReturnBlock = NonReturnBlock;
577 CandidateFound = true;
578 break;
579 }
580
581 BasicBlock *CommSucc, *OtherSucc;
582 std::tie(args&: CommSucc, args&: OtherSucc) = GetCommonSucc(Succ1, Succ2);
583
584 if (!CommSucc)
585 break;
586
587 OutliningInfo->Entries.push_back(Elt: CurrEntry);
588 CurrEntry = OtherSucc;
589 } while (true);
590
591 if (!CandidateFound)
592 return std::unique_ptr<FunctionOutliningInfo>();
593
594 // There should not be any successors (not in the entry set) other than
595 // {ReturnBlock, NonReturnBlock}
596 assert(OutliningInfo->Entries[0] == &F.front() &&
597 "Function Entry must be the first in Entries vector");
598 DenseSet<BasicBlock *> Entries(llvm::from_range, OutliningInfo->Entries);
599
600 // Returns true of BB has Predecessor which is not
601 // in Entries set.
602 auto HasNonEntryPred = [Entries](BasicBlock *BB) {
603 for (auto *Pred : predecessors(BB)) {
604 if (!Entries.count(V: Pred))
605 return true;
606 }
607 return false;
608 };
609 auto CheckAndNormalizeCandidate =
610 [Entries, HasNonEntryPred](FunctionOutliningInfo *OutliningInfo) {
611 for (BasicBlock *E : OutliningInfo->Entries) {
612 for (auto *Succ : successors(BB: E)) {
613 if (Entries.count(V: Succ))
614 continue;
615 if (Succ == OutliningInfo->ReturnBlock)
616 OutliningInfo->ReturnBlockPreds.push_back(Elt: E);
617 else if (Succ != OutliningInfo->NonReturnBlock)
618 return false;
619 }
620 // There should not be any outside incoming edges either:
621 if (HasNonEntryPred(E))
622 return false;
623 }
624 return true;
625 };
626
627 if (!CheckAndNormalizeCandidate(OutliningInfo.get()))
628 return std::unique_ptr<FunctionOutliningInfo>();
629
630 // Now further growing the candidate's inlining region by
631 // peeling off dominating blocks from the outlining region:
632 while (OutliningInfo->getNumInlinedBlocks() < MaxNumInlineBlocks) {
633 BasicBlock *Cand = OutliningInfo->NonReturnBlock;
634 if (succ_size(BB: Cand) != 2)
635 break;
636
637 if (HasNonEntryPred(Cand))
638 break;
639
640 BasicBlock *Succ1 = *succ_begin(BB: Cand);
641 BasicBlock *Succ2 = *(succ_begin(BB: Cand) + 1);
642
643 BasicBlock *ReturnBlock, *NonReturnBlock;
644 std::tie(args&: ReturnBlock, args&: NonReturnBlock) = GetReturnBlock(Succ1, Succ2);
645 if (!ReturnBlock || ReturnBlock != OutliningInfo->ReturnBlock)
646 break;
647
648 if (NonReturnBlock->getSinglePredecessor() != Cand)
649 break;
650
651 // Now grow and update OutlininigInfo:
652 OutliningInfo->Entries.push_back(Elt: Cand);
653 OutliningInfo->NonReturnBlock = NonReturnBlock;
654 OutliningInfo->ReturnBlockPreds.push_back(Elt: Cand);
655 Entries.insert(V: Cand);
656 }
657
658 return OutliningInfo;
659}
660
661// Check if there is PGO data or user annotated branch data:
662static bool hasProfileData(const Function &F, const FunctionOutliningInfo &OI) {
663 if (F.hasProfileData())
664 return true;
665 // Now check if any of the entry block has MD_prof data:
666 for (auto *E : OI.Entries) {
667 CondBrInst *BR = dyn_cast<CondBrInst>(Val: E->getTerminator());
668 if (BR && hasBranchWeightMD(I: *BR))
669 return true;
670 }
671 return false;
672}
673
674BranchProbability PartialInlinerImpl::getOutliningCallBBRelativeFreq(
675 FunctionCloner &Cloner) const {
676 BasicBlock *OutliningCallBB = Cloner.OutlinedFunctions.back().second;
677 auto EntryFreq =
678 Cloner.ClonedFuncBFI->getBlockFreq(BB: &Cloner.ClonedFunc->getEntryBlock());
679 auto OutliningCallFreq =
680 Cloner.ClonedFuncBFI->getBlockFreq(BB: OutliningCallBB);
681 // FIXME Hackery needed because ClonedFuncBFI is based on the function BEFORE
682 // we outlined any regions, so we may encounter situations where the
683 // OutliningCallFreq is *slightly* bigger than the EntryFreq.
684 if (OutliningCallFreq.getFrequency() > EntryFreq.getFrequency())
685 OutliningCallFreq = EntryFreq;
686
687 auto OutlineRegionRelFreq = BranchProbability::getBranchProbability(
688 Numerator: OutliningCallFreq.getFrequency(), Denominator: EntryFreq.getFrequency());
689
690 if (hasProfileData(F: *Cloner.OrigFunc, OI: *Cloner.ClonedOI))
691 return OutlineRegionRelFreq;
692
693 // When profile data is not available, we need to be conservative in
694 // estimating the overall savings. Static branch prediction can usually
695 // guess the branch direction right (taken/non-taken), but the guessed
696 // branch probability is usually not biased enough. In case when the
697 // outlined region is predicted to be likely, its probability needs
698 // to be made higher (more biased) to not under-estimate the cost of
699 // function outlining. On the other hand, if the outlined region
700 // is predicted to be less likely, the predicted probablity is usually
701 // higher than the actual. For instance, the actual probability of the
702 // less likely target is only 5%, but the guessed probablity can be
703 // 40%. In the latter case, there is no need for further adjustment.
704 // FIXME: add an option for this.
705 if (OutlineRegionRelFreq < BranchProbability(45, 100))
706 return OutlineRegionRelFreq;
707
708 OutlineRegionRelFreq = std::max(
709 a: OutlineRegionRelFreq, b: BranchProbability(OutlineRegionFreqPercent, 100));
710
711 return OutlineRegionRelFreq;
712}
713
714bool PartialInlinerImpl::shouldPartialInline(
715 CallBase &CB, FunctionCloner &Cloner, BlockFrequency WeightedOutliningRcost,
716 OptimizationRemarkEmitter &ORE) const {
717 using namespace ore;
718
719 Function *Callee = CB.getCalledFunction();
720 assert(Callee == Cloner.ClonedFunc);
721
722 if (SkipCostAnalysis)
723 return isInlineViable(Callee&: *Callee).isSuccess();
724
725 Function *Caller = CB.getCaller();
726 auto &CalleeTTI = GetTTI(*Callee);
727 bool RemarksEnabled =
728 Callee->getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
729 DEBUG_TYPE);
730 InlineCost IC =
731 getInlineCost(Call&: CB, Params: getInlineParams(), CalleeTTI, GetAssumptionCache,
732 GetTLI, GetBFI, PSI: &PSI, ORE: RemarksEnabled ? &ORE : nullptr);
733
734 if (IC.isAlways()) {
735 ORE.emit(RemarkBuilder: [&]() {
736 return OptimizationRemarkAnalysis(DEBUG_TYPE, "AlwaysInline", &CB)
737 << NV("Callee", Cloner.OrigFunc)
738 << " should always be fully inlined, not partially";
739 });
740 return false;
741 }
742
743 if (IC.isNever()) {
744 ORE.emit(RemarkBuilder: [&]() {
745 return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline", &CB)
746 << NV("Callee", Cloner.OrigFunc) << " not partially inlined into "
747 << NV("Caller", Caller)
748 << " because it should never be inlined (cost=never)";
749 });
750 return false;
751 }
752
753 if (!IC) {
754 ORE.emit(RemarkBuilder: [&]() {
755 return OptimizationRemarkAnalysis(DEBUG_TYPE, "TooCostly", &CB)
756 << NV("Callee", Cloner.OrigFunc) << " not partially inlined into "
757 << NV("Caller", Caller) << " because too costly to inline (cost="
758 << NV("Cost", IC.getCost()) << ", threshold="
759 << NV("Threshold", IC.getCostDelta() + IC.getCost()) << ")";
760 });
761 return false;
762 }
763 const DataLayout &DL = Caller->getDataLayout();
764
765 // The savings of eliminating the call:
766 int NonWeightedSavings = getCallsiteCost(TTI: CalleeTTI, Call: CB, DL);
767 BlockFrequency NormWeightedSavings(NonWeightedSavings);
768
769 // Weighted saving is smaller than weighted cost, return false
770 if (NormWeightedSavings < WeightedOutliningRcost) {
771 ORE.emit(RemarkBuilder: [&]() {
772 return OptimizationRemarkAnalysis(DEBUG_TYPE, "OutliningCallcostTooHigh",
773 &CB)
774 << NV("Callee", Cloner.OrigFunc) << " not partially inlined into "
775 << NV("Caller", Caller) << " runtime overhead (overhead="
776 << NV("Overhead", (unsigned)WeightedOutliningRcost.getFrequency())
777 << ", savings="
778 << NV("Savings", (unsigned)NormWeightedSavings.getFrequency())
779 << ")"
780 << " of making the outlined call is too high";
781 });
782
783 return false;
784 }
785
786 ORE.emit(RemarkBuilder: [&]() {
787 return OptimizationRemarkAnalysis(DEBUG_TYPE, "CanBePartiallyInlined", &CB)
788 << NV("Callee", Cloner.OrigFunc) << " can be partially inlined into "
789 << NV("Caller", Caller) << " with cost=" << NV("Cost", IC.getCost())
790 << " (threshold="
791 << NV("Threshold", IC.getCostDelta() + IC.getCost()) << ")";
792 });
793 return true;
794}
795
796// TODO: Ideally we should share Inliner's InlineCost Analysis code.
797// For now use a simplified version. The returned 'InlineCost' will be used
798// to esimate the size cost as well as runtime cost of the BB.
799InstructionCost
800PartialInlinerImpl::computeBBInlineCost(BasicBlock *BB,
801 TargetTransformInfo *TTI) {
802 InstructionCost InlineCost = 0;
803 const DataLayout &DL = BB->getDataLayout();
804 int InstrCost = InlineConstants::getInstrCost();
805 for (Instruction &I : *BB) {
806 // Skip free instructions.
807 switch (I.getOpcode()) {
808 case Instruction::BitCast:
809 case Instruction::PtrToInt:
810 case Instruction::IntToPtr:
811 case Instruction::Alloca:
812 case Instruction::PHI:
813 continue;
814 case Instruction::GetElementPtr:
815 if (cast<GetElementPtrInst>(Val: &I)->hasAllZeroIndices())
816 continue;
817 break;
818 default:
819 break;
820 }
821
822 if (I.isLifetimeStartOrEnd())
823 continue;
824
825 if (auto *II = dyn_cast<IntrinsicInst>(Val: &I)) {
826 Intrinsic::ID IID = II->getIntrinsicID();
827 SmallVector<Type *, 4> Tys;
828 FastMathFlags FMF;
829 for (Value *Val : II->args())
830 Tys.push_back(Elt: Val->getType());
831
832 if (auto *FPMO = dyn_cast<FPMathOperator>(Val: II))
833 FMF = FPMO->getFastMathFlags();
834
835 IntrinsicCostAttributes ICA(IID, II->getType(), Tys, FMF);
836 InlineCost += TTI->getIntrinsicInstrCost(ICA, CostKind: TTI::TCK_SizeAndLatency);
837 continue;
838 }
839
840 if (CallInst *CI = dyn_cast<CallInst>(Val: &I)) {
841 InlineCost += getCallsiteCost(TTI: *TTI, Call: *CI, DL);
842 continue;
843 }
844
845 if (InvokeInst *II = dyn_cast<InvokeInst>(Val: &I)) {
846 InlineCost += getCallsiteCost(TTI: *TTI, Call: *II, DL);
847 continue;
848 }
849
850 if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: &I)) {
851 InlineCost += (SI->getNumCases() + 1) * InstrCost;
852 continue;
853 }
854 InlineCost += InstrCost;
855 }
856
857 return InlineCost;
858}
859
860std::tuple<InstructionCost, InstructionCost>
861PartialInlinerImpl::computeOutliningCosts(FunctionCloner &Cloner) const {
862 InstructionCost OutliningFuncCallCost = 0, OutlinedFunctionCost = 0;
863 for (auto FuncBBPair : Cloner.OutlinedFunctions) {
864 Function *OutlinedFunc = FuncBBPair.first;
865 BasicBlock* OutliningCallBB = FuncBBPair.second;
866 // Now compute the cost of the call sequence to the outlined function
867 // 'OutlinedFunction' in BB 'OutliningCallBB':
868 auto *OutlinedFuncTTI = &GetTTI(*OutlinedFunc);
869 OutliningFuncCallCost +=
870 computeBBInlineCost(BB: OutliningCallBB, TTI: OutlinedFuncTTI);
871
872 // Now compute the cost of the extracted/outlined function itself:
873 for (BasicBlock &BB : *OutlinedFunc)
874 OutlinedFunctionCost += computeBBInlineCost(BB: &BB, TTI: OutlinedFuncTTI);
875 }
876 assert(OutlinedFunctionCost >= Cloner.OutlinedRegionCost &&
877 "Outlined function cost should be no less than the outlined region");
878
879 // The code extractor introduces a new root and exit stub blocks with
880 // additional unconditional branches. Those branches will be eliminated
881 // later with bb layout. The cost should be adjusted accordingly:
882 OutlinedFunctionCost -=
883 2 * InlineConstants::getInstrCost() * Cloner.OutlinedFunctions.size();
884
885 InstructionCost OutliningRuntimeOverhead =
886 OutliningFuncCallCost +
887 (OutlinedFunctionCost - Cloner.OutlinedRegionCost) +
888 ExtraOutliningPenalty.getValue();
889
890 return std::make_tuple(args&: OutliningFuncCallCost, args&: OutliningRuntimeOverhead);
891}
892
893// Create the callsite to profile count map which is
894// used to update the original function's entry count,
895// after the function is partially inlined into the callsite.
896void PartialInlinerImpl::computeCallsiteToProfCountMap(
897 Function *DuplicateFunction,
898 DenseMap<User *, uint64_t> &CallSiteToProfCountMap) const {
899 std::vector<User *> Users(DuplicateFunction->user_begin(),
900 DuplicateFunction->user_end());
901 Function *CurrentCaller = nullptr;
902 std::unique_ptr<BlockFrequencyInfo> TempBFI;
903 BlockFrequencyInfo *CurrentCallerBFI = nullptr;
904
905 auto ComputeCurrBFI = [&,this](Function *Caller) {
906 // For the old pass manager:
907 if (!GetBFI) {
908 DominatorTree DT(*Caller);
909 CycleInfo CI;
910 CI.compute(F&: *Caller);
911 LoopInfo LI(DT);
912 BranchProbabilityInfo BPI(*Caller, CI);
913 TempBFI.reset(p: new BlockFrequencyInfo(*Caller, BPI, LI));
914 CurrentCallerBFI = TempBFI.get();
915 } else {
916 // New pass manager:
917 CurrentCallerBFI = &(GetBFI(*Caller));
918 }
919 };
920
921 for (User *User : Users) {
922 CallBase *CB = getSupportedCallBase(U: User);
923 Function *Caller = CB->getCaller();
924 if (CurrentCaller != Caller) {
925 CurrentCaller = Caller;
926 ComputeCurrBFI(Caller);
927 } else {
928 assert(CurrentCallerBFI && "CallerBFI is not set");
929 }
930 BasicBlock *CallBB = CB->getParent();
931 auto Count = CurrentCallerBFI->getBlockProfileCount(BB: CallBB);
932 if (Count)
933 CallSiteToProfCountMap[User] = *Count;
934 else
935 CallSiteToProfCountMap[User] = 0;
936 }
937}
938
939PartialInlinerImpl::FunctionCloner::FunctionCloner(
940 Function *F, FunctionOutliningInfo *OI, OptimizationRemarkEmitter &ORE,
941 function_ref<AssumptionCache *(Function &)> LookupAC,
942 function_ref<TargetTransformInfo &(Function &)> GetTTI)
943 : OrigFunc(F), ORE(ORE), LookupAC(LookupAC), GetTTI(GetTTI) {
944 ClonedOI = std::make_unique<FunctionOutliningInfo>();
945
946 // Clone the function, so that we can hack away on it.
947 ValueToValueMapTy VMap;
948 ClonedFunc = CloneFunction(F, VMap);
949
950 ClonedOI->ReturnBlock = cast<BasicBlock>(Val&: VMap[OI->ReturnBlock]);
951 ClonedOI->NonReturnBlock = cast<BasicBlock>(Val&: VMap[OI->NonReturnBlock]);
952 for (BasicBlock *BB : OI->Entries)
953 ClonedOI->Entries.push_back(Elt: cast<BasicBlock>(Val&: VMap[BB]));
954
955 for (BasicBlock *E : OI->ReturnBlockPreds) {
956 BasicBlock *NewE = cast<BasicBlock>(Val&: VMap[E]);
957 ClonedOI->ReturnBlockPreds.push_back(Elt: NewE);
958 }
959 // Go ahead and update all uses to the duplicate, so that we can just
960 // use the inliner functionality when we're done hacking.
961 F->replaceAllUsesWith(V: ClonedFunc);
962}
963
964PartialInlinerImpl::FunctionCloner::FunctionCloner(
965 Function *F, FunctionOutliningMultiRegionInfo *OI,
966 OptimizationRemarkEmitter &ORE,
967 function_ref<AssumptionCache *(Function &)> LookupAC,
968 function_ref<TargetTransformInfo &(Function &)> GetTTI)
969 : OrigFunc(F), ORE(ORE), LookupAC(LookupAC), GetTTI(GetTTI) {
970 ClonedOMRI = std::make_unique<FunctionOutliningMultiRegionInfo>();
971
972 // Clone the function, so that we can hack away on it.
973 ValueToValueMapTy VMap;
974 ClonedFunc = CloneFunction(F, VMap);
975
976 // Go through all Outline Candidate Regions and update all BasicBlock
977 // information.
978 for (const FunctionOutliningMultiRegionInfo::OutlineRegionInfo &RegionInfo :
979 OI->ORI) {
980 SmallVector<BasicBlock *, 8> Region;
981 for (BasicBlock *BB : RegionInfo.Region)
982 Region.push_back(Elt: cast<BasicBlock>(Val&: VMap[BB]));
983
984 BasicBlock *NewEntryBlock = cast<BasicBlock>(Val&: VMap[RegionInfo.EntryBlock]);
985 BasicBlock *NewExitBlock = cast<BasicBlock>(Val&: VMap[RegionInfo.ExitBlock]);
986 BasicBlock *NewReturnBlock = nullptr;
987 if (RegionInfo.ReturnBlock)
988 NewReturnBlock = cast<BasicBlock>(Val&: VMap[RegionInfo.ReturnBlock]);
989 FunctionOutliningMultiRegionInfo::OutlineRegionInfo MappedRegionInfo(
990 Region, NewEntryBlock, NewExitBlock, NewReturnBlock);
991 ClonedOMRI->ORI.push_back(Elt: MappedRegionInfo);
992 }
993 // Go ahead and update all uses to the duplicate, so that we can just
994 // use the inliner functionality when we're done hacking.
995 F->replaceAllUsesWith(V: ClonedFunc);
996}
997
998void PartialInlinerImpl::FunctionCloner::normalizeReturnBlock() const {
999 auto GetFirstPHI = [](BasicBlock *BB) {
1000 BasicBlock::iterator I = BB->begin();
1001 PHINode *FirstPhi = nullptr;
1002 while (I != BB->end()) {
1003 PHINode *Phi = dyn_cast<PHINode>(Val&: I);
1004 if (!Phi)
1005 break;
1006 if (!FirstPhi) {
1007 FirstPhi = Phi;
1008 break;
1009 }
1010 }
1011 return FirstPhi;
1012 };
1013
1014 // Shouldn't need to normalize PHIs if we're not outlining non-early return
1015 // blocks.
1016 if (!ClonedOI)
1017 return;
1018
1019 // Special hackery is needed with PHI nodes that have inputs from more than
1020 // one extracted block. For simplicity, just split the PHIs into a two-level
1021 // sequence of PHIs, some of which will go in the extracted region, and some
1022 // of which will go outside.
1023 BasicBlock *PreReturn = ClonedOI->ReturnBlock;
1024 // only split block when necessary:
1025 PHINode *FirstPhi = GetFirstPHI(PreReturn);
1026 unsigned NumPredsFromEntries = ClonedOI->ReturnBlockPreds.size();
1027
1028 if (!FirstPhi || FirstPhi->getNumIncomingValues() <= NumPredsFromEntries + 1)
1029 return;
1030
1031 auto IsTrivialPhi = [](PHINode *PN) -> Value * {
1032 if (llvm::all_equal(Range: PN->incoming_values()))
1033 return PN->getIncomingValue(i: 0);
1034 return nullptr;
1035 };
1036
1037 ClonedOI->ReturnBlock = ClonedOI->ReturnBlock->splitBasicBlock(
1038 I: ClonedOI->ReturnBlock->getFirstNonPHIIt());
1039 BasicBlock::iterator I = PreReturn->begin();
1040 BasicBlock::iterator Ins = ClonedOI->ReturnBlock->begin();
1041 SmallVector<Instruction *, 4> DeadPhis;
1042 while (I != PreReturn->end()) {
1043 PHINode *OldPhi = dyn_cast<PHINode>(Val&: I);
1044 if (!OldPhi)
1045 break;
1046
1047 PHINode *RetPhi =
1048 PHINode::Create(Ty: OldPhi->getType(), NumReservedValues: NumPredsFromEntries + 1, NameStr: "");
1049 RetPhi->insertBefore(InsertPos: Ins);
1050 OldPhi->replaceAllUsesWith(V: RetPhi);
1051 Ins = ClonedOI->ReturnBlock->getFirstNonPHIIt();
1052
1053 RetPhi->addIncoming(V: &*I, BB: PreReturn);
1054 for (BasicBlock *E : ClonedOI->ReturnBlockPreds) {
1055 RetPhi->addIncoming(V: OldPhi->getIncomingValueForBlock(BB: E), BB: E);
1056 OldPhi->removeIncomingValue(BB: E);
1057 }
1058
1059 // After incoming values splitting, the old phi may become trivial.
1060 // Keeping the trivial phi can introduce definition inside the outline
1061 // region which is live-out, causing necessary overhead (load, store
1062 // arg passing etc).
1063 if (auto *OldPhiVal = IsTrivialPhi(OldPhi)) {
1064 OldPhi->replaceAllUsesWith(V: OldPhiVal);
1065 DeadPhis.push_back(Elt: OldPhi);
1066 }
1067 ++I;
1068 }
1069 for (auto *DP : DeadPhis)
1070 DP->eraseFromParent();
1071
1072 for (auto *E : ClonedOI->ReturnBlockPreds)
1073 E->getTerminator()->replaceUsesOfWith(From: PreReturn, To: ClonedOI->ReturnBlock);
1074}
1075
1076bool PartialInlinerImpl::FunctionCloner::doMultiRegionFunctionOutlining() {
1077
1078 auto ComputeRegionCost =
1079 [&](SmallVectorImpl<BasicBlock *> &Region) -> InstructionCost {
1080 InstructionCost Cost = 0;
1081 for (BasicBlock* BB : Region)
1082 Cost += computeBBInlineCost(BB, TTI: &GetTTI(*BB->getParent()));
1083 return Cost;
1084 };
1085
1086 assert(ClonedOMRI && "Expecting OutlineInfo for multi region outline");
1087
1088 if (ClonedOMRI->ORI.empty())
1089 return false;
1090
1091 // The CodeExtractor needs a dominator tree.
1092 DominatorTree DT;
1093 DT.recalculate(Func&: *ClonedFunc);
1094
1095 // Manually calculate a BlockFrequencyInfo and BranchProbabilityInfo.
1096 CycleInfo CI;
1097 CI.compute(F&: *ClonedFunc);
1098 LoopInfo LI(DT);
1099 BranchProbabilityInfo BPI(*ClonedFunc, CI);
1100 ClonedFuncBFI.reset(p: new BlockFrequencyInfo(*ClonedFunc, BPI, LI));
1101
1102 // Cache and recycle the CodeExtractor analysis to avoid O(n^2) compile-time.
1103 CodeExtractorAnalysisCache CEAC(*ClonedFunc);
1104
1105 SetVector<Value *> Inputs, Outputs, Sinks;
1106 for (FunctionOutliningMultiRegionInfo::OutlineRegionInfo RegionInfo :
1107 ClonedOMRI->ORI) {
1108 InstructionCost CurrentOutlinedRegionCost =
1109 ComputeRegionCost(RegionInfo.Region);
1110
1111 CodeExtractor CE(RegionInfo.Region, &DT, /*AggregateArgs*/ false,
1112 ClonedFuncBFI.get(), &BPI,
1113 LookupAC(*RegionInfo.EntryBlock->getParent()),
1114 /* AllowVarargs */ false, /* AllowAlloca */ false,
1115 /* AllocaBlock */ nullptr, /* DeallocationBlocks */ {},
1116 /* Suffix */ "", /* ArgsInZeroAddressSpace */ false,
1117 /* VoidReturnWithSingleOutput */ false);
1118
1119 CE.findInputsOutputs(Inputs, Outputs, Allocas: Sinks);
1120
1121 LLVM_DEBUG({
1122 dbgs() << "inputs: " << Inputs.size() << "\n";
1123 dbgs() << "outputs: " << Outputs.size() << "\n";
1124 for (Value *value : Inputs)
1125 dbgs() << "value used in func: " << *value << "\n";
1126 for (Value *output : Outputs)
1127 dbgs() << "instr used in func: " << *output << "\n";
1128 });
1129
1130 // Do not extract regions that have live exit variables.
1131 if (Outputs.size() > 0 && !ForceLiveExit)
1132 continue;
1133
1134 if (Function *OutlinedFunc = CE.extractCodeRegion(CEAC)) {
1135 CallBase *OCS = PartialInlinerImpl::getOneCallSiteTo(F&: *OutlinedFunc);
1136 BasicBlock *OutliningCallBB = OCS->getParent();
1137 assert(OutliningCallBB->getParent() == ClonedFunc);
1138 OutlinedFunctions.push_back(Elt: std::make_pair(x&: OutlinedFunc,y&: OutliningCallBB));
1139 NumColdRegionsOutlined++;
1140 OutlinedRegionCost += CurrentOutlinedRegionCost;
1141
1142 if (MarkOutlinedColdCC) {
1143 OutlinedFunc->setCallingConv(CallingConv::Cold);
1144 OCS->setCallingConv(CallingConv::Cold);
1145 }
1146 } else
1147 ORE.emit(RemarkBuilder: [&]() {
1148 return OptimizationRemarkMissed(DEBUG_TYPE, "ExtractFailed",
1149 &RegionInfo.Region.front()->front())
1150 << "Failed to extract region at block "
1151 << ore::NV("Block", RegionInfo.Region.front());
1152 });
1153 }
1154
1155 return !OutlinedFunctions.empty();
1156}
1157
1158Function *
1159PartialInlinerImpl::FunctionCloner::doSingleRegionFunctionOutlining() {
1160 // Returns true if the block is to be partial inlined into the caller
1161 // (i.e. not to be extracted to the out of line function)
1162 auto ToBeInlined = [&, this](BasicBlock *BB) {
1163 return BB == ClonedOI->ReturnBlock ||
1164 llvm::is_contained(Range&: ClonedOI->Entries, Element: BB);
1165 };
1166
1167 assert(ClonedOI && "Expecting OutlineInfo for single region outline");
1168 // The CodeExtractor needs a dominator tree.
1169 DominatorTree DT;
1170 DT.recalculate(Func&: *ClonedFunc);
1171
1172 // Manually calculate a BlockFrequencyInfo and BranchProbabilityInfo.
1173 CycleInfo CI;
1174 CI.compute(F&: *ClonedFunc);
1175 LoopInfo LI(DT);
1176 BranchProbabilityInfo BPI(*ClonedFunc, CI);
1177 ClonedFuncBFI.reset(p: new BlockFrequencyInfo(*ClonedFunc, BPI, LI));
1178
1179 // Gather up the blocks that we're going to extract.
1180 std::vector<BasicBlock *> ToExtract;
1181 auto *ClonedFuncTTI = &GetTTI(*ClonedFunc);
1182 ToExtract.push_back(x: ClonedOI->NonReturnBlock);
1183 OutlinedRegionCost += PartialInlinerImpl::computeBBInlineCost(
1184 BB: ClonedOI->NonReturnBlock, TTI: ClonedFuncTTI);
1185 for (BasicBlock *BB : depth_first(G: &ClonedFunc->getEntryBlock()))
1186 if (!ToBeInlined(BB) && BB != ClonedOI->NonReturnBlock) {
1187 ToExtract.push_back(x: BB);
1188 // FIXME: the code extractor may hoist/sink more code
1189 // into the outlined function which may make the outlining
1190 // overhead (the difference of the outlined function cost
1191 // and OutliningRegionCost) look larger.
1192 OutlinedRegionCost += computeBBInlineCost(BB, TTI: ClonedFuncTTI);
1193 }
1194
1195 // Extract the body of the if.
1196 CodeExtractorAnalysisCache CEAC(*ClonedFunc);
1197 Function *OutlinedFunc =
1198 CodeExtractor(ToExtract, &DT, /*AggregateArgs*/ false,
1199 ClonedFuncBFI.get(), &BPI, LookupAC(*ClonedFunc),
1200 /* AllowVarargs */ true, /* AllowAlloca */ false,
1201 /* AllocaBlock */ nullptr, /* DeallocationBlocks */ {},
1202 /* Suffix */ "", /* ArgsInZeroAddressSpace */ false,
1203 /* VoidReturnWithSingleOutput */ false)
1204 .extractCodeRegion(CEAC);
1205
1206 if (OutlinedFunc) {
1207 BasicBlock *OutliningCallBB =
1208 PartialInlinerImpl::getOneCallSiteTo(F&: *OutlinedFunc)->getParent();
1209 assert(OutliningCallBB->getParent() == ClonedFunc);
1210 OutlinedFunctions.push_back(Elt: std::make_pair(x&: OutlinedFunc, y&: OutliningCallBB));
1211 } else
1212 ORE.emit(RemarkBuilder: [&]() {
1213 return OptimizationRemarkMissed(DEBUG_TYPE, "ExtractFailed",
1214 &ToExtract.front()->front())
1215 << "Failed to extract region at block "
1216 << ore::NV("Block", ToExtract.front());
1217 });
1218
1219 return OutlinedFunc;
1220}
1221
1222PartialInlinerImpl::FunctionCloner::~FunctionCloner() {
1223 // Ditch the duplicate, since we're done with it, and rewrite all remaining
1224 // users (function pointers, etc.) back to the original function.
1225 ClonedFunc->replaceAllUsesWith(V: OrigFunc);
1226 ClonedFunc->eraseFromParent();
1227 if (!IsFunctionInlined) {
1228 // Remove each function that was speculatively created if there is no
1229 // reference.
1230 for (auto FuncBBPair : OutlinedFunctions) {
1231 Function *Func = FuncBBPair.first;
1232 Func->eraseFromParent();
1233 }
1234 }
1235}
1236
1237std::pair<bool, Function *> PartialInlinerImpl::unswitchFunction(Function &F) {
1238 if (F.hasAddressTaken())
1239 return {false, nullptr};
1240
1241 // Let inliner handle it
1242 if (F.hasFnAttribute(Kind: Attribute::AlwaysInline))
1243 return {false, nullptr};
1244
1245 if (F.hasFnAttribute(Kind: Attribute::NoInline))
1246 return {false, nullptr};
1247
1248 if (PSI.isFunctionEntryCold(F: &F))
1249 return {false, nullptr};
1250
1251 if (F.users().empty())
1252 return {false, nullptr};
1253
1254 OptimizationRemarkEmitter ORE(&F);
1255
1256 // Only try to outline cold regions if we have a profile summary, which
1257 // implies we have profiling information.
1258 if (PSI.hasProfileSummary() && F.hasProfileData() &&
1259 !DisableMultiRegionPartialInline) {
1260 std::unique_ptr<FunctionOutliningMultiRegionInfo> OMRI =
1261 computeOutliningColdRegionsInfo(F, ORE);
1262 if (OMRI) {
1263 FunctionCloner Cloner(&F, OMRI.get(), ORE, LookupAssumptionCache, GetTTI);
1264
1265 LLVM_DEBUG({
1266 dbgs() << "HotCountThreshold = " << PSI.getHotCountThreshold() << "\n";
1267 dbgs() << "ColdCountThreshold = " << PSI.getColdCountThreshold()
1268 << "\n";
1269 });
1270
1271 bool DidOutline = Cloner.doMultiRegionFunctionOutlining();
1272
1273 if (DidOutline) {
1274 LLVM_DEBUG({
1275 dbgs() << ">>>>>> Outlined (Cloned) Function >>>>>>\n";
1276 Cloner.ClonedFunc->print(dbgs());
1277 dbgs() << "<<<<<< Outlined (Cloned) Function <<<<<<\n";
1278 });
1279
1280 if (tryPartialInline(Cloner))
1281 return {true, nullptr};
1282 }
1283 }
1284 }
1285
1286 // Fall-thru to regular partial inlining if we:
1287 // i) can't find any cold regions to outline, or
1288 // ii) can't inline the outlined function anywhere.
1289 std::unique_ptr<FunctionOutliningInfo> OI = computeOutliningInfo(F);
1290 if (!OI)
1291 return {false, nullptr};
1292
1293 FunctionCloner Cloner(&F, OI.get(), ORE, LookupAssumptionCache, GetTTI);
1294 Cloner.normalizeReturnBlock();
1295
1296 Function *OutlinedFunction = Cloner.doSingleRegionFunctionOutlining();
1297
1298 if (!OutlinedFunction)
1299 return {false, nullptr};
1300
1301 if (tryPartialInline(Cloner))
1302 return {true, OutlinedFunction};
1303
1304 return {false, nullptr};
1305}
1306
1307bool PartialInlinerImpl::tryPartialInline(FunctionCloner &Cloner) {
1308 if (Cloner.OutlinedFunctions.empty())
1309 return false;
1310
1311 auto OutliningCosts = computeOutliningCosts(Cloner);
1312
1313 InstructionCost SizeCost = std::get<0>(t&: OutliningCosts);
1314 InstructionCost NonWeightedRcost = std::get<1>(t&: OutliningCosts);
1315
1316 assert(SizeCost.isValid() && NonWeightedRcost.isValid() &&
1317 "Expected valid costs");
1318
1319 // Only calculate RelativeToEntryFreq when we are doing single region
1320 // outlining.
1321 BranchProbability RelativeToEntryFreq;
1322 if (Cloner.ClonedOI)
1323 RelativeToEntryFreq = getOutliningCallBBRelativeFreq(Cloner);
1324 else
1325 // RelativeToEntryFreq doesn't make sense when we have more than one
1326 // outlined call because each call will have a different relative frequency
1327 // to the entry block. We can consider using the average, but the
1328 // usefulness of that information is questionable. For now, assume we never
1329 // execute the calls to outlined functions.
1330 RelativeToEntryFreq = BranchProbability(0, 1);
1331
1332 BlockFrequency WeightedRcost =
1333 BlockFrequency(NonWeightedRcost.getValue()) * RelativeToEntryFreq;
1334
1335 // The call sequence(s) to the outlined function(s) are larger than the sum of
1336 // the original outlined region size(s), it does not increase the chances of
1337 // inlining the function with outlining (The inliner uses the size increase to
1338 // model the cost of inlining a callee).
1339 if (!SkipCostAnalysis && Cloner.OutlinedRegionCost < SizeCost) {
1340 OptimizationRemarkEmitter OrigFuncORE(Cloner.OrigFunc);
1341 DebugLoc DLoc;
1342 BasicBlock *Block;
1343 std::tie(args&: DLoc, args&: Block) = getOneDebugLoc(F&: *Cloner.ClonedFunc);
1344 OrigFuncORE.emit(RemarkBuilder: [&]() {
1345 return OptimizationRemarkAnalysis(DEBUG_TYPE, "OutlineRegionTooSmall",
1346 DLoc, Block)
1347 << ore::NV("Function", Cloner.OrigFunc)
1348 << " not partially inlined into callers (Original Size = "
1349 << ore::NV("OutlinedRegionOriginalSize", Cloner.OutlinedRegionCost)
1350 << ", Size of call sequence to outlined function = "
1351 << ore::NV("NewSize", SizeCost) << ")";
1352 });
1353 return false;
1354 }
1355
1356 assert(Cloner.OrigFunc->users().empty() &&
1357 "F's users should all be replaced!");
1358
1359 std::vector<User *> Users(Cloner.ClonedFunc->user_begin(),
1360 Cloner.ClonedFunc->user_end());
1361
1362 DenseMap<User *, uint64_t> CallSiteToProfCountMap;
1363 auto CalleeEntryCount = Cloner.OrigFunc->getEntryCount();
1364 if (CalleeEntryCount)
1365 computeCallsiteToProfCountMap(DuplicateFunction: Cloner.ClonedFunc, CallSiteToProfCountMap);
1366
1367 uint64_t CalleeEntryCountV = (CalleeEntryCount ? *CalleeEntryCount : 0);
1368
1369 bool AnyInline = false;
1370 for (User *User : Users) {
1371 CallBase *CB = getSupportedCallBase(U: User);
1372
1373 if (isLimitReached())
1374 continue;
1375
1376 OptimizationRemarkEmitter CallerORE(CB->getCaller());
1377 if (!shouldPartialInline(CB&: *CB, Cloner, WeightedOutliningRcost: WeightedRcost, ORE&: CallerORE))
1378 continue;
1379
1380 // Construct remark before doing the inlining, as after successful inlining
1381 // the callsite is removed.
1382 OptimizationRemark OR(DEBUG_TYPE, "PartiallyInlined", CB);
1383 OR << ore::NV("Callee", Cloner.OrigFunc) << " partially inlined into "
1384 << ore::NV("Caller", CB->getCaller());
1385
1386 InlineFunctionInfo IFI(GetAssumptionCache, &PSI);
1387 // We can only forward varargs when we outlined a single region, else we
1388 // bail on vararg functions.
1389 if (!InlineFunction(CB&: *CB, IFI, /*MergeAttributes=*/false, CalleeAAR: nullptr,
1390 /*InsertLifetime=*/true, /*TrackInlineHistory=*/true,
1391 ForwardVarArgsTo: (Cloner.ClonedOI ? Cloner.OutlinedFunctions.back().first
1392 : nullptr))
1393 .isSuccess())
1394 continue;
1395
1396 CallerORE.emit(OptDiag&: OR);
1397
1398 // Now update the entry count:
1399 if (CalleeEntryCountV) {
1400 if (auto It = CallSiteToProfCountMap.find(Val: User);
1401 It != CallSiteToProfCountMap.end()) {
1402 uint64_t CallSiteCount = It->second;
1403 CalleeEntryCountV -= std::min(a: CalleeEntryCountV, b: CallSiteCount);
1404 }
1405 }
1406
1407 AnyInline = true;
1408 NumPartialInlining++;
1409 // Update the stats
1410 if (Cloner.ClonedOI)
1411 NumPartialInlined++;
1412 else
1413 NumColdOutlinePartialInlined++;
1414 }
1415
1416 if (AnyInline) {
1417 Cloner.IsFunctionInlined = true;
1418 if (CalleeEntryCount)
1419 Cloner.OrigFunc->setEntryCount(Count: CalleeEntryCountV);
1420 OptimizationRemarkEmitter OrigFuncORE(Cloner.OrigFunc);
1421 OrigFuncORE.emit(RemarkBuilder: [&]() {
1422 return OptimizationRemark(DEBUG_TYPE, "PartiallyInlined", Cloner.OrigFunc)
1423 << "Partially inlined into at least one caller";
1424 });
1425 }
1426
1427 return AnyInline;
1428}
1429
1430bool PartialInlinerImpl::run(Module &M) {
1431 if (DisablePartialInlining)
1432 return false;
1433
1434 std::vector<Function *> Worklist;
1435 Worklist.reserve(n: M.size());
1436 for (Function &F : M)
1437 if (!F.use_empty() && !F.isDeclaration())
1438 Worklist.push_back(x: &F);
1439
1440 bool Changed = false;
1441 while (!Worklist.empty()) {
1442 Function *CurrFunc = Worklist.back();
1443 Worklist.pop_back();
1444
1445 if (CurrFunc->use_empty())
1446 continue;
1447
1448 std::pair<bool, Function *> Result = unswitchFunction(F&: *CurrFunc);
1449 if (Result.second)
1450 Worklist.push_back(x: Result.second);
1451 Changed |= Result.first;
1452 }
1453
1454 return Changed;
1455}
1456
1457PreservedAnalyses PartialInlinerPass::run(Module &M,
1458 ModuleAnalysisManager &AM) {
1459 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
1460
1461 auto GetAssumptionCache = [&FAM](Function &F) -> AssumptionCache & {
1462 return FAM.getResult<AssumptionAnalysis>(IR&: F);
1463 };
1464
1465 auto LookupAssumptionCache = [&FAM](Function &F) -> AssumptionCache * {
1466 return FAM.getCachedResult<AssumptionAnalysis>(IR&: F);
1467 };
1468
1469 auto GetBFI = [&FAM](Function &F) -> BlockFrequencyInfo & {
1470 return FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
1471 };
1472
1473 auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & {
1474 return FAM.getResult<TargetIRAnalysis>(IR&: F);
1475 };
1476
1477 auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
1478 return FAM.getResult<TargetLibraryAnalysis>(IR&: F);
1479 };
1480
1481 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(IR&: M);
1482
1483 if (PartialInlinerImpl(GetAssumptionCache, LookupAssumptionCache, GetTTI,
1484 GetTLI, PSI, GetBFI)
1485 .run(M))
1486 return PreservedAnalyses::none();
1487 return PreservedAnalyses::all();
1488}
1489