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