1//===- InlineCost.cpp - Cost analysis for inliner -------------------------===//
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 file implements inline cost analysis.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Analysis/InlineCost.h"
14#include "llvm/ADT/STLExtras.h"
15#include "llvm/ADT/SetVector.h"
16#include "llvm/ADT/SmallPtrSet.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/ADT/Statistic.h"
19#include "llvm/Analysis/AssumptionCache.h"
20#include "llvm/Analysis/BlockFrequencyInfo.h"
21#include "llvm/Analysis/CodeMetrics.h"
22#include "llvm/Analysis/ConstantFolding.h"
23#include "llvm/Analysis/DomConditionCache.h"
24#include "llvm/Analysis/EphemeralValuesCache.h"
25#include "llvm/Analysis/InstructionSimplify.h"
26#include "llvm/Analysis/LoopInfo.h"
27#include "llvm/Analysis/MemoryBuiltins.h"
28#include "llvm/Analysis/OptimizationRemarkEmitter.h"
29#include "llvm/Analysis/ProfileSummaryInfo.h"
30#include "llvm/Analysis/TargetLibraryInfo.h"
31#include "llvm/Analysis/TargetTransformInfo.h"
32#include "llvm/Analysis/ValueTracking.h"
33#include "llvm/Config/llvm-config.h"
34#include "llvm/IR/AssemblyAnnotationWriter.h"
35#include "llvm/IR/CallingConv.h"
36#include "llvm/IR/DataLayout.h"
37#include "llvm/IR/GetElementPtrTypeIterator.h"
38#include "llvm/IR/GlobalAlias.h"
39#include "llvm/IR/InlineAsm.h"
40#include "llvm/IR/InstVisitor.h"
41#include "llvm/IR/IntrinsicInst.h"
42#include "llvm/IR/Operator.h"
43#include "llvm/IR/PatternMatch.h"
44#include "llvm/Support/CommandLine.h"
45#include "llvm/Support/Debug.h"
46#include "llvm/Support/FormattedStream.h"
47#include "llvm/Support/raw_ostream.h"
48#include <climits>
49#include <limits>
50#include <optional>
51
52using namespace llvm;
53
54#define DEBUG_TYPE "inline-cost"
55
56STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");
57
58static cl::opt<int>
59 DefaultThreshold("inlinedefault-threshold", cl::Hidden, cl::init(Val: 225),
60 cl::desc("Default amount of inlining to perform"));
61
62// We introduce this option since there is a minor compile-time win by avoiding
63// addition of TTI attributes (target-features in particular) to inline
64// candidates when they are guaranteed to be the same as top level methods in
65// some use cases. If we avoid adding the attribute, we need an option to avoid
66// checking these attributes.
67static cl::opt<bool> IgnoreTTIInlineCompatible(
68 "ignore-tti-inline-compatible", cl::Hidden, cl::init(Val: false),
69 cl::desc("Ignore TTI attributes compatibility check between callee/caller "
70 "during inline cost calculation"));
71
72static cl::opt<bool> PrintInstructionComments(
73 "print-instruction-comments", cl::Hidden, cl::init(Val: false),
74 cl::desc("Prints comments for instruction based on inline cost analysis"));
75
76static cl::opt<int> InlineThreshold(
77 "inline-threshold", cl::Hidden, cl::init(Val: 225),
78 cl::desc("Control the amount of inlining to perform (default = 225)"));
79
80static cl::opt<int> HintThreshold(
81 "inlinehint-threshold", cl::Hidden, cl::init(Val: 325),
82 cl::desc("Threshold for inlining functions with inline hint"));
83
84static cl::opt<int>
85 ColdCallSiteThreshold("inline-cold-callsite-threshold", cl::Hidden,
86 cl::init(Val: 45),
87 cl::desc("Threshold for inlining cold callsites"));
88
89static cl::opt<bool> InlineEnableCostBenefitAnalysis(
90 "inline-enable-cost-benefit-analysis", cl::Hidden, cl::init(Val: false),
91 cl::desc("Enable the cost-benefit analysis for the inliner"));
92
93// InlineSavingsMultiplier overrides per TTI multipliers iff it is
94// specified explicitly in command line options. This option is exposed
95// for tuning and testing.
96static cl::opt<int> InlineSavingsMultiplier(
97 "inline-savings-multiplier", cl::Hidden, cl::init(Val: 8),
98 cl::desc("Multiplier to multiply cycle savings by during inlining"));
99
100// InlineSavingsProfitableMultiplier overrides per TTI multipliers iff it is
101// specified explicitly in command line options. This option is exposed
102// for tuning and testing.
103static cl::opt<int> InlineSavingsProfitableMultiplier(
104 "inline-savings-profitable-multiplier", cl::Hidden, cl::init(Val: 4),
105 cl::desc("A multiplier on top of cycle savings to decide whether the "
106 "savings won't justify the cost"));
107
108static cl::opt<int>
109 InlineSizeAllowance("inline-size-allowance", cl::Hidden, cl::init(Val: 100),
110 cl::desc("The maximum size of a callee that get's "
111 "inlined without sufficient cycle savings"));
112
113// We introduce this threshold to help performance of instrumentation based
114// PGO before we actually hook up inliner with analysis passes such as BPI and
115// BFI.
116static cl::opt<int> ColdThreshold(
117 "inlinecold-threshold", cl::Hidden, cl::init(Val: 45),
118 cl::desc("Threshold for inlining functions with cold attribute"));
119
120static cl::opt<int>
121 HotCallSiteThreshold("hot-callsite-threshold", cl::Hidden, cl::init(Val: 3000),
122 cl::desc("Threshold for hot callsites "));
123
124static cl::opt<int> LocallyHotCallSiteThreshold(
125 "locally-hot-callsite-threshold", cl::Hidden, cl::init(Val: 525),
126 cl::desc("Threshold for locally hot callsites "));
127
128static cl::opt<int> ColdCallSiteRelFreq(
129 "cold-callsite-rel-freq", cl::Hidden, cl::init(Val: 2),
130 cl::desc("Maximum block frequency, expressed as a percentage of caller's "
131 "entry frequency, for a callsite to be cold in the absence of "
132 "profile information."));
133
134static cl::opt<uint64_t> HotCallSiteRelFreq(
135 "hot-callsite-rel-freq", cl::Hidden, cl::init(Val: 60),
136 cl::desc("Minimum block frequency, expressed as a multiple of caller's "
137 "entry frequency, for a callsite to be hot in the absence of "
138 "profile information."));
139
140static cl::opt<int>
141 InstrCost("inline-instr-cost", cl::Hidden, cl::init(Val: 5),
142 cl::desc("Cost of a single instruction when inlining"));
143
144static cl::opt<int> InlineAsmInstrCost(
145 "inline-asm-instr-cost", cl::Hidden, cl::init(Val: 0),
146 cl::desc("Cost of a single inline asm instruction when inlining"));
147
148static cl::opt<int>
149 MemAccessCost("inline-memaccess-cost", cl::Hidden, cl::init(Val: 0),
150 cl::desc("Cost of load/store instruction when inlining"));
151
152static cl::opt<int> CallPenalty(
153 "inline-call-penalty", cl::Hidden, cl::init(Val: 25),
154 cl::desc("Call penalty that is applied per callsite when inlining"));
155
156static cl::opt<size_t>
157 StackSizeThreshold("inline-max-stacksize", cl::Hidden,
158 cl::init(Val: std::numeric_limits<size_t>::max()),
159 cl::desc("Do not inline functions with a stack size "
160 "that exceeds the specified limit"));
161
162static cl::opt<size_t> RecurStackSizeThreshold(
163 "recursive-inline-max-stacksize", cl::Hidden,
164 cl::init(Val: InlineConstants::TotalAllocaSizeRecursiveCaller),
165 cl::desc("Do not inline recursive functions with a stack "
166 "size that exceeds the specified limit"));
167
168static cl::opt<bool> OptComputeFullInlineCost(
169 "inline-cost-full", cl::Hidden,
170 cl::desc("Compute the full inline cost of a call site even when the cost "
171 "exceeds the threshold."));
172
173static cl::opt<bool> InlineCallerSupersetNoBuiltin(
174 "inline-caller-superset-nobuiltin", cl::Hidden, cl::init(Val: true),
175 cl::desc("Allow inlining when caller has a superset of callee's nobuiltin "
176 "attributes."));
177
178static cl::opt<bool> DisableGEPConstOperand(
179 "disable-gep-const-evaluation", cl::Hidden, cl::init(Val: false),
180 cl::desc("Disables evaluation of GetElementPtr with constant operands"));
181
182static cl::opt<bool> InlineAllViableCalls(
183 "inline-all-viable-calls", cl::Hidden, cl::init(Val: false),
184 cl::desc("Inline all viable calls, even if they exceed the inlining "
185 "threshold"));
186namespace llvm {
187std::optional<int> getStringFnAttrAsInt(const Attribute &Attr) {
188 if (Attr.isValid()) {
189 int AttrValue = 0;
190 if (!Attr.getValueAsString().getAsInteger(Radix: 10, Result&: AttrValue))
191 return AttrValue;
192 }
193 return std::nullopt;
194}
195
196std::optional<int> getStringFnAttrAsInt(CallBase &CB, StringRef AttrKind) {
197 return getStringFnAttrAsInt(Attr: CB.getFnAttr(Kind: AttrKind));
198}
199
200std::optional<int> getStringFnAttrAsInt(Function *F, StringRef AttrKind) {
201 return getStringFnAttrAsInt(Attr: F->getFnAttribute(Kind: AttrKind));
202}
203
204namespace InlineConstants {
205int getInstrCost() { return InstrCost; }
206
207} // namespace InlineConstants
208
209} // namespace llvm
210
211namespace {
212class InlineCostCallAnalyzer;
213
214// This struct is used to store information about inline cost of a
215// particular instruction
216struct InstructionCostDetail {
217 int CostBefore = 0;
218 int CostAfter = 0;
219 int ThresholdBefore = 0;
220 int ThresholdAfter = 0;
221
222 int getThresholdDelta() const { return ThresholdAfter - ThresholdBefore; }
223
224 int getCostDelta() const { return CostAfter - CostBefore; }
225
226 bool hasThresholdChanged() const { return ThresholdAfter != ThresholdBefore; }
227};
228
229class InlineCostAnnotationWriter : public AssemblyAnnotationWriter {
230private:
231 InlineCostCallAnalyzer *const ICCA;
232
233public:
234 InlineCostAnnotationWriter(InlineCostCallAnalyzer *ICCA) : ICCA(ICCA) {}
235 void emitInstructionAnnot(const Instruction *I,
236 formatted_raw_ostream &OS) override;
237};
238
239/// Carry out call site analysis, in order to evaluate inlinability.
240/// NOTE: the type is currently used as implementation detail of functions such
241/// as llvm::getInlineCost. Note the function_ref constructor parameters - the
242/// expectation is that they come from the outer scope, from the wrapper
243/// functions. If we want to support constructing CallAnalyzer objects where
244/// lambdas are provided inline at construction, or where the object needs to
245/// otherwise survive past the scope of the provided functions, we need to
246/// revisit the argument types.
247class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
248 typedef InstVisitor<CallAnalyzer, bool> Base;
249 friend class InstVisitor<CallAnalyzer, bool>;
250
251protected:
252 virtual ~CallAnalyzer() = default;
253 /// The TargetTransformInfo available for this compilation.
254 const TargetTransformInfo &TTI;
255
256 /// Getter for the cache of @llvm.assume intrinsics.
257 function_ref<AssumptionCache &(Function &)> GetAssumptionCache;
258
259 /// Getter for BlockFrequencyInfo
260 function_ref<BlockFrequencyInfo &(Function &)> GetBFI;
261
262 /// Getter for TargetLibraryInfo
263 function_ref<const TargetLibraryInfo &(Function &)> GetTLI;
264
265 /// Profile summary information.
266 ProfileSummaryInfo *PSI;
267
268 /// The called function.
269 Function &F;
270
271 // Cache the DataLayout since we use it a lot.
272 const DataLayout &DL;
273
274 /// The OptimizationRemarkEmitter available for this compilation.
275 OptimizationRemarkEmitter *ORE;
276
277 /// The candidate callsite being analyzed. Please do not use this to do
278 /// analysis in the caller function; we want the inline cost query to be
279 /// easily cacheable. Instead, use the cover function paramHasAttr.
280 CallBase &CandidateCall;
281
282 /// Getter for the cache of ephemeral values.
283 function_ref<EphemeralValuesCache &(Function &)> GetEphValuesCache = nullptr;
284
285 /// Extension points for handling callsite features.
286 // Called before a basic block was analyzed.
287 virtual void onBlockStart(const BasicBlock *BB) {}
288
289 /// Called after a basic block was analyzed.
290 virtual void onBlockAnalyzed(const BasicBlock *BB) {}
291
292 /// Called before an instruction was analyzed
293 virtual void onInstructionAnalysisStart(const Instruction *I) {}
294
295 /// Called after an instruction was analyzed
296 virtual void onInstructionAnalysisFinish(const Instruction *I) {}
297
298 /// Called at the end of the analysis of the callsite. Return the outcome of
299 /// the analysis, i.e. 'InlineResult(true)' if the inlining may happen, or
300 /// the reason it can't.
301 virtual InlineResult finalizeAnalysis() { return InlineResult::success(); }
302 /// Called when we're about to start processing a basic block, and every time
303 /// we are done processing an instruction. Return true if there is no point in
304 /// continuing the analysis (e.g. we've determined already the call site is
305 /// too expensive to inline)
306 virtual bool shouldStop() { return false; }
307
308 /// Called before the analysis of the callee body starts (with callsite
309 /// contexts propagated). It checks callsite-specific information. Return a
310 /// reason analysis can't continue if that's the case, or 'true' if it may
311 /// continue.
312 virtual InlineResult onAnalysisStart() { return InlineResult::success(); }
313 /// Called if the analysis engine decides SROA cannot be done for the given
314 /// alloca.
315 virtual void onDisableSROA(AllocaInst *Arg) {}
316
317 /// Called the analysis engine determines load elimination won't happen.
318 virtual void onDisableLoadElimination() {}
319
320 /// Called when we visit a CallBase, before the analysis starts. Return false
321 /// to stop further processing of the instruction.
322 virtual bool onCallBaseVisitStart(CallBase &Call) { return true; }
323
324 /// Called to account for a call.
325 virtual void onCallPenalty() {}
326
327 /// Called to account for a load or store.
328 virtual void onMemAccess(){};
329
330 /// Called to account for the expectation the inlining would result in a load
331 /// elimination.
332 virtual void onLoadEliminationOpportunity() {}
333
334 /// Called to account for the cost of argument setup for the Call in the
335 /// callee's body (not the callsite currently under analysis).
336 virtual void onCallArgumentSetup(const CallBase &Call) {}
337
338 /// Called to account for a load relative intrinsic.
339 virtual void onLoadRelativeIntrinsic() {}
340
341 /// Called to account for a lowered call.
342 virtual void onLoweredCall(Function *F, CallBase &Call, bool IsIndirectCall) {
343 }
344
345 /// Account for a jump table of given size. Return false to stop further
346 /// processing the switch instruction
347 virtual bool onJumpTable(unsigned JumpTableSize) { return true; }
348
349 /// Account for a case cluster of given size. Return false to stop further
350 /// processing of the instruction.
351 virtual bool onCaseCluster(unsigned NumCaseCluster) { return true; }
352
353 /// Called at the end of processing a switch instruction, with the given
354 /// number of case clusters.
355 virtual void onFinalizeSwitch(unsigned JumpTableSize, unsigned NumCaseCluster,
356 bool DefaultDestUnreachable) {}
357
358 /// Called to account for any other instruction not specifically accounted
359 /// for.
360 virtual void onMissedSimplification() {}
361
362 /// Account for inline assembly instructions.
363 virtual void onInlineAsm(const InlineAsm &Arg) {}
364
365 /// Start accounting potential benefits due to SROA for the given alloca.
366 virtual void onInitializeSROAArg(AllocaInst *Arg) {}
367
368 /// Account SROA savings for the AllocaInst value.
369 virtual void onAggregateSROAUse(AllocaInst *V) {}
370
371 bool handleSROA(Value *V, bool DoNotDisable) {
372 // Check for SROA candidates in comparisons.
373 if (auto *SROAArg = getSROAArgForValueOrNull(V)) {
374 if (DoNotDisable) {
375 onAggregateSROAUse(V: SROAArg);
376 return true;
377 }
378 disableSROAForArg(SROAArg);
379 }
380 return false;
381 }
382
383 bool IsCallerRecursive = false;
384 bool IsRecursiveCall = false;
385 bool ExposesReturnsTwice = false;
386 bool HasDynamicAlloca = false;
387 bool ContainsNoDuplicateCall = false;
388 bool HasReturn = false;
389 bool HasIndirectBr = false;
390 bool HasUninlineableIntrinsic = false;
391 bool InitsVargArgs = false;
392
393 /// Number of bytes allocated statically by the callee.
394 uint64_t AllocatedSize = 0;
395 unsigned NumInstructions = 0;
396 unsigned NumInlineAsmInstructions = 0;
397 unsigned NumVectorInstructions = 0;
398
399 /// While we walk the potentially-inlined instructions, we build up and
400 /// maintain a mapping of simplified values specific to this callsite. The
401 /// idea is to propagate any special information we have about arguments to
402 /// this call through the inlinable section of the function, and account for
403 /// likely simplifications post-inlining. The most important aspect we track
404 /// is CFG altering simplifications -- when we prove a basic block dead, that
405 /// can cause dramatic shifts in the cost of inlining a function.
406 /// Note: The simplified Value may be owned by the caller function.
407 DenseMap<Value *, Value *> SimplifiedValues;
408
409 /// Keep track of the values which map back (through function arguments) to
410 /// allocas on the caller stack which could be simplified through SROA.
411 DenseMap<Value *, AllocaInst *> SROAArgValues;
412
413 /// Keep track of Allocas for which we believe we may get SROA optimization.
414 DenseSet<AllocaInst *> EnabledSROAAllocas;
415
416 /// Keep track of values which map to a pointer base and constant offset.
417 DenseMap<Value *, std::pair<Value *, APInt>> ConstantOffsetPtrs;
418
419 /// Keep track of dead blocks due to the constant arguments.
420 SmallPtrSet<BasicBlock *, 16> DeadBlocks;
421
422 /// The mapping of the blocks to their known unique successors due to the
423 /// constant arguments.
424 DenseMap<BasicBlock *, BasicBlock *> KnownSuccessors;
425
426 /// Model the elimination of repeated loads that is expected to happen
427 /// whenever we simplify away the stores that would otherwise cause them to be
428 /// loads.
429 bool EnableLoadElimination = true;
430
431 /// Whether we allow inlining for recursive call.
432 bool AllowRecursiveCall = false;
433
434 SmallPtrSet<Value *, 16> LoadAddrSet;
435
436 AllocaInst *getSROAArgForValueOrNull(Value *V) const {
437 auto It = SROAArgValues.find(Val: V);
438 if (It == SROAArgValues.end() || EnabledSROAAllocas.count(V: It->second) == 0)
439 return nullptr;
440 return It->second;
441 }
442
443 /// Use a value in its given form directly if possible, otherwise try looking
444 /// for it in SimplifiedValues.
445 template <typename T> T *getDirectOrSimplifiedValue(Value *V) const {
446 if (auto *Direct = dyn_cast<T>(V))
447 return Direct;
448 return getSimplifiedValue<T>(V);
449 }
450
451 // Custom simplification helper routines.
452 bool isAllocaDerivedArg(Value *V);
453 void disableSROAForArg(AllocaInst *SROAArg);
454 void disableSROA(Value *V);
455 void findDeadBlocks(BasicBlock *CurrBB, BasicBlock *NextBB);
456 void disableLoadElimination();
457 bool isGEPFree(GetElementPtrInst &GEP);
458 bool canFoldInboundsGEP(GetElementPtrInst &I);
459 bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
460 bool simplifyCallSite(Function *F, CallBase &Call);
461 bool simplifyCmpInstForRecCall(CmpInst &Cmp);
462 bool simplifyInstruction(Instruction &I);
463 bool simplifyIntrinsicCallIsConstant(CallBase &CB);
464 bool simplifyIntrinsicCallObjectSize(CallBase &CB);
465 ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V);
466 bool isLoweredToCall(Function *F, CallBase &Call);
467
468 /// Return true if the given argument to the function being considered for
469 /// inlining has the given attribute set either at the call site or the
470 /// function declaration. Primarily used to inspect call site specific
471 /// attributes since these can be more precise than the ones on the callee
472 /// itself.
473 bool paramHasAttr(Argument *A, Attribute::AttrKind Attr);
474
475 /// Return true if the given value is known non null within the callee if
476 /// inlined through this particular callsite.
477 bool isKnownNonNullInCallee(Value *V);
478
479 /// Return true if size growth is allowed when inlining the callee at \p Call.
480 bool allowSizeGrowth(CallBase &Call);
481
482 // Custom analysis routines.
483 InlineResult analyzeBlock(BasicBlock *BB,
484 const SmallPtrSetImpl<const Value *> &EphValues);
485
486 // Disable several entry points to the visitor so we don't accidentally use
487 // them by declaring but not defining them here.
488 void visit(Module *);
489 void visit(Module &);
490 void visit(Function *);
491 void visit(Function &);
492 void visit(BasicBlock *);
493 void visit(BasicBlock &);
494
495 // Provide base case for our instruction visit.
496 bool visitInstruction(Instruction &I);
497
498 // Our visit overrides.
499 bool visitAlloca(AllocaInst &I);
500 bool visitPHI(PHINode &I);
501 bool visitGetElementPtr(GetElementPtrInst &I);
502 bool visitBitCast(BitCastInst &I);
503 bool visitPtrToInt(PtrToIntInst &I);
504 bool visitIntToPtr(IntToPtrInst &I);
505 bool visitCastInst(CastInst &I);
506 bool visitCmpInst(CmpInst &I);
507 bool visitSub(BinaryOperator &I);
508 bool visitBinaryOperator(BinaryOperator &I);
509 bool visitFNeg(UnaryOperator &I);
510 bool visitLoad(LoadInst &I);
511 bool visitStore(StoreInst &I);
512 bool visitExtractValue(ExtractValueInst &I);
513 bool visitInsertValue(InsertValueInst &I);
514 bool visitCallBase(CallBase &Call);
515 bool visitReturnInst(ReturnInst &RI);
516 bool visitUncondBrInst(UncondBrInst &BI);
517 bool visitCondBrInst(CondBrInst &BI);
518 bool visitSelectInst(SelectInst &SI);
519 bool visitSwitchInst(SwitchInst &SI);
520 bool visitIndirectBrInst(IndirectBrInst &IBI);
521 bool visitResumeInst(ResumeInst &RI);
522 bool visitCleanupReturnInst(CleanupReturnInst &RI);
523 bool visitCatchReturnInst(CatchReturnInst &RI);
524 bool visitUnreachableInst(UnreachableInst &I);
525
526public:
527 CallAnalyzer(
528 Function &Callee, CallBase &Call, const TargetTransformInfo &TTI,
529 function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
530 function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr,
531 function_ref<const TargetLibraryInfo &(Function &)> GetTLI = nullptr,
532 ProfileSummaryInfo *PSI = nullptr,
533 OptimizationRemarkEmitter *ORE = nullptr,
534 function_ref<EphemeralValuesCache &(Function &)> GetEphValuesCache =
535 nullptr)
536 : TTI(TTI), GetAssumptionCache(GetAssumptionCache), GetBFI(GetBFI),
537 GetTLI(GetTLI), PSI(PSI), F(Callee), DL(F.getDataLayout()), ORE(ORE),
538 CandidateCall(Call), GetEphValuesCache(GetEphValuesCache) {}
539
540 InlineResult analyze();
541
542 /// Lookup simplified Value. May return a value owned by the caller.
543 Value *getSimplifiedValueUnchecked(Value *V) const {
544 return SimplifiedValues.lookup(Val: V);
545 }
546
547 /// Lookup simplified Value, but return nullptr if the simplified value is
548 /// owned by the caller.
549 template <typename T> T *getSimplifiedValue(Value *V) const {
550 Value *SimpleV = SimplifiedValues.lookup(Val: V);
551 if (!SimpleV)
552 return nullptr;
553
554 // Skip checks if we know T is a global. This has a small, but measurable
555 // impact on compile-time.
556 if constexpr (std::is_base_of_v<Constant, T>)
557 return dyn_cast<T>(SimpleV);
558
559 // Make sure the simplified Value is owned by this function
560 if (auto *I = dyn_cast<Instruction>(Val: SimpleV)) {
561 if (I->getFunction() != &F)
562 return nullptr;
563 } else if (auto *Arg = dyn_cast<Argument>(Val: SimpleV)) {
564 if (Arg->getParent() != &F)
565 return nullptr;
566 } else if (!isa<Constant>(Val: SimpleV))
567 return nullptr;
568 return dyn_cast<T>(SimpleV);
569 }
570
571 // Keep a bunch of stats about the cost savings found so we can print them
572 // out when debugging.
573 unsigned NumConstantArgs = 0;
574 unsigned NumConstantOffsetPtrArgs = 0;
575 unsigned NumAllocaArgs = 0;
576 unsigned NumConstantPtrCmps = 0;
577 unsigned NumConstantPtrDiffs = 0;
578 unsigned NumInstructionsSimplified = 0;
579
580 void dump();
581};
582
583// Considering forming a binary search, we should find the number of nodes
584// which is same as the number of comparisons when lowered. For a given
585// number of clusters, n, we can define a recursive function, f(n), to find
586// the number of nodes in the tree. The recursion is :
587// f(n) = 1 + f(n/2) + f (n - n/2), when n > 3,
588// and f(n) = n, when n <= 3.
589// This will lead a binary tree where the leaf should be either f(2) or f(3)
590// when n > 3. So, the number of comparisons from leaves should be n, while
591// the number of non-leaf should be :
592// 2^(log2(n) - 1) - 1
593// = 2^log2(n) * 2^-1 - 1
594// = n / 2 - 1.
595// Considering comparisons from leaf and non-leaf nodes, we can estimate the
596// number of comparisons in a simple closed form :
597// n + n / 2 - 1 = n * 3 / 2 - 1
598int64_t getExpectedNumberOfCompare(int NumCaseCluster) {
599 return 3 * static_cast<int64_t>(NumCaseCluster) / 2 - 1;
600}
601
602/// FIXME: if it is necessary to derive from InlineCostCallAnalyzer, note
603/// the FIXME in onLoweredCall, when instantiating an InlineCostCallAnalyzer
604class InlineCostCallAnalyzer final : public CallAnalyzer {
605 const bool ComputeFullInlineCost;
606 int LoadEliminationCost = 0;
607 /// Bonus to be applied when percentage of vector instructions in callee is
608 /// high (see more details in updateThreshold).
609 int VectorBonus = 0;
610 /// Bonus to be applied when the callee has only one reachable basic block.
611 int SingleBBBonus = 0;
612
613 /// Tunable parameters that control the analysis.
614 const InlineParams &Params;
615
616 // This DenseMap stores the delta change in cost and threshold after
617 // accounting for the given instruction. The map is filled only with the
618 // flag PrintInstructionComments on.
619 DenseMap<const Instruction *, InstructionCostDetail> InstructionCostDetailMap;
620
621 /// Upper bound for the inlining cost. Bonuses are being applied to account
622 /// for speculative "expected profit" of the inlining decision.
623 int Threshold = 0;
624
625 /// The amount of StaticBonus applied.
626 int StaticBonusApplied = 0;
627
628 /// Attempt to evaluate indirect calls to boost its inline cost.
629 const bool BoostIndirectCalls;
630
631 /// Ignore the threshold when finalizing analysis.
632 const bool IgnoreThreshold;
633
634 // True if the cost-benefit-analysis-based inliner is enabled.
635 const bool CostBenefitAnalysisEnabled;
636
637 /// Inlining cost measured in abstract units, accounts for all the
638 /// instructions expected to be executed for a given function invocation.
639 /// Instructions that are statically proven to be dead based on call-site
640 /// arguments are not counted here.
641 int Cost = 0;
642
643 // The cumulative cost at the beginning of the basic block being analyzed. At
644 // the end of analyzing each basic block, "Cost - CostAtBBStart" represents
645 // the size of that basic block.
646 int CostAtBBStart = 0;
647
648 // The static size of live but cold basic blocks. This is "static" in the
649 // sense that it's not weighted by profile counts at all.
650 int ColdSize = 0;
651
652 // Whether inlining is decided by cost-threshold analysis.
653 bool DecidedByCostThreshold = false;
654
655 // Whether inlining is decided by cost-benefit analysis.
656 bool DecidedByCostBenefit = false;
657
658 // The cost-benefit pair computed by cost-benefit analysis.
659 std::optional<CostBenefitPair> CostBenefit;
660
661 bool SingleBB = true;
662
663 unsigned SROACostSavings = 0;
664 unsigned SROACostSavingsLost = 0;
665
666 /// The mapping of caller Alloca values to their accumulated cost savings. If
667 /// we have to disable SROA for one of the allocas, this tells us how much
668 /// cost must be added.
669 DenseMap<AllocaInst *, int> SROAArgCosts;
670
671 /// Return true if \p Call is a cold callsite.
672 bool isColdCallSite(CallBase &Call, BlockFrequencyInfo *CallerBFI);
673
674 /// Update Threshold based on callsite properties such as callee
675 /// attributes and callee hotness for PGO builds. The Callee is explicitly
676 /// passed to support analyzing indirect calls whose target is inferred by
677 /// analysis.
678 void updateThreshold(CallBase &Call, Function &Callee);
679 /// Return a higher threshold if \p Call is a hot callsite.
680 std::optional<int> getHotCallSiteThreshold(CallBase &Call,
681 BlockFrequencyInfo *CallerBFI);
682
683 /// Handle a capped 'int' increment for Cost.
684 void addCost(int64_t Inc) {
685 Inc = std::clamp<int64_t>(val: Inc, INT_MIN, INT_MAX);
686 Cost = std::clamp<int64_t>(val: Inc + Cost, INT_MIN, INT_MAX);
687 }
688
689 void onDisableSROA(AllocaInst *Arg) override {
690 auto CostIt = SROAArgCosts.find(Val: Arg);
691 if (CostIt == SROAArgCosts.end())
692 return;
693 addCost(Inc: CostIt->second);
694 SROACostSavings -= CostIt->second;
695 SROACostSavingsLost += CostIt->second;
696 SROAArgCosts.erase(I: CostIt);
697 }
698
699 void onDisableLoadElimination() override {
700 addCost(Inc: LoadEliminationCost);
701 LoadEliminationCost = 0;
702 }
703
704 bool onCallBaseVisitStart(CallBase &Call) override {
705 if (std::optional<int> AttrCallThresholdBonus =
706 getStringFnAttrAsInt(CB&: Call, AttrKind: "call-threshold-bonus"))
707 Threshold += *AttrCallThresholdBonus;
708
709 if (std::optional<int> AttrCallCost =
710 getStringFnAttrAsInt(CB&: Call, AttrKind: "call-inline-cost")) {
711 addCost(Inc: *AttrCallCost);
712 // Prevent further processing of the call since we want to override its
713 // inline cost, not just add to it.
714 return false;
715 }
716 return true;
717 }
718
719 void onCallPenalty() override { addCost(Inc: CallPenalty); }
720
721 void onMemAccess() override { addCost(Inc: MemAccessCost); }
722
723 void onCallArgumentSetup(const CallBase &Call) override {
724 // Pay the price of the argument setup. We account for the average 1
725 // instruction per call argument setup here.
726 addCost(Inc: Call.arg_size() * InstrCost);
727 }
728 void onLoadRelativeIntrinsic() override {
729 // This is normally lowered to 4 LLVM instructions.
730 addCost(Inc: 3 * InstrCost);
731 }
732 void onLoweredCall(Function *F, CallBase &Call,
733 bool IsIndirectCall) override {
734 // We account for the average 1 instruction per call argument setup here.
735 addCost(Inc: Call.arg_size() * InstrCost);
736
737 // If we have a constant that we are calling as a function, we can peer
738 // through it and see the function target. This happens not infrequently
739 // during devirtualization and so we want to give it a hefty bonus for
740 // inlining, but cap that bonus in the event that inlining wouldn't pan out.
741 // Pretend to inline the function, with a custom threshold.
742 if (IsIndirectCall && BoostIndirectCalls) {
743 auto IndirectCallParams = Params;
744 IndirectCallParams.DefaultThreshold =
745 InlineConstants::IndirectCallThreshold;
746 /// FIXME: if InlineCostCallAnalyzer is derived from, this may need
747 /// to instantiate the derived class.
748 InlineCostCallAnalyzer CA(*F, Call, IndirectCallParams, TTI,
749 GetAssumptionCache, GetBFI, GetTLI, PSI, ORE,
750 false);
751 if (CA.analyze().isSuccess()) {
752 // We were able to inline the indirect call! Subtract the cost from the
753 // threshold to get the bonus we want to apply, but don't go below zero.
754 addCost(Inc: -std::max(a: 0, b: CA.getThreshold() - CA.getCost()));
755 }
756 } else
757 // Otherwise simply add the cost for merely making the call.
758 addCost(Inc: TTI.getInlineCallPenalty(F: CandidateCall.getCaller(), Call,
759 DefaultCallPenalty: CallPenalty));
760 }
761
762 void onFinalizeSwitch(unsigned JumpTableSize, unsigned NumCaseCluster,
763 bool DefaultDestUnreachable) override {
764 // If suitable for a jump table, consider the cost for the table size and
765 // branch to destination.
766 // Maximum valid cost increased in this function.
767 if (JumpTableSize) {
768 // Suppose a default branch includes one compare and one conditional
769 // branch if it's reachable.
770 if (!DefaultDestUnreachable)
771 addCost(Inc: 2 * InstrCost);
772 // Suppose a jump table requires one load and one jump instruction.
773 int64_t JTCost =
774 static_cast<int64_t>(JumpTableSize) * InstrCost + 2 * InstrCost;
775 addCost(Inc: JTCost);
776 return;
777 }
778
779 if (NumCaseCluster <= 3) {
780 // Suppose a comparison includes one compare and one conditional branch.
781 // We can reduce a set of instructions if the default branch is
782 // undefined.
783 addCost(Inc: (NumCaseCluster - DefaultDestUnreachable) * 2 * InstrCost);
784 return;
785 }
786
787 int64_t ExpectedNumberOfCompare =
788 getExpectedNumberOfCompare(NumCaseCluster);
789 int64_t SwitchCost = ExpectedNumberOfCompare * 2 * InstrCost;
790
791 addCost(Inc: SwitchCost);
792 }
793
794 // Parses the inline assembly argument to account for its cost. Inline
795 // assembly instructions incur higher costs for inlining since they cannot be
796 // analyzed and optimized.
797 void onInlineAsm(const InlineAsm &Arg) override {
798 if (!InlineAsmInstrCost)
799 return;
800 SmallVector<StringRef, 4> AsmStrs;
801 Arg.collectAsmStrs(AsmStrs);
802 int SectionLevel = 0;
803 int InlineAsmInstrCount = 0;
804 for (StringRef AsmStr : AsmStrs) {
805 // Trim whitespaces and comments.
806 StringRef Trimmed = AsmStr.trim();
807 size_t hashPos = Trimmed.find(C: '#');
808 if (hashPos != StringRef::npos)
809 Trimmed = Trimmed.substr(Start: 0, N: hashPos);
810 // Ignore comments.
811 if (Trimmed.empty())
812 continue;
813 // Filter out the outlined assembly instructions from the cost by keeping
814 // track of the section level and only accounting for instrutions at
815 // section level of zero. Note there will be duplication in outlined
816 // sections too, but is not accounted in the inlining cost model.
817 if (Trimmed.starts_with(Prefix: ".pushsection")) {
818 ++SectionLevel;
819 continue;
820 }
821 if (Trimmed.starts_with(Prefix: ".popsection")) {
822 --SectionLevel;
823 continue;
824 }
825 // Ignore directives and labels.
826 if (Trimmed.starts_with(Prefix: ".") || Trimmed.contains(Other: ":"))
827 continue;
828 if (SectionLevel == 0)
829 ++InlineAsmInstrCount;
830 }
831 NumInlineAsmInstructions += InlineAsmInstrCount;
832 addCost(Inc: InlineAsmInstrCount * InlineAsmInstrCost);
833 }
834
835 void onMissedSimplification() override { addCost(Inc: InstrCost); }
836
837 void onInitializeSROAArg(AllocaInst *Arg) override {
838 assert(Arg != nullptr &&
839 "Should not initialize SROA costs for null value.");
840 auto SROAArgCost = TTI.getCallerAllocaCost(CB: &CandidateCall, AI: Arg);
841 SROACostSavings += SROAArgCost;
842 SROAArgCosts[Arg] = SROAArgCost;
843 }
844
845 void onAggregateSROAUse(AllocaInst *SROAArg) override {
846 auto CostIt = SROAArgCosts.find(Val: SROAArg);
847 assert(CostIt != SROAArgCosts.end() &&
848 "expected this argument to have a cost");
849 CostIt->second += InstrCost;
850 SROACostSavings += InstrCost;
851 }
852
853 void onBlockStart(const BasicBlock *BB) override { CostAtBBStart = Cost; }
854
855 void onBlockAnalyzed(const BasicBlock *BB) override {
856 if (CostBenefitAnalysisEnabled) {
857 // Keep track of the static size of live but cold basic blocks. For now,
858 // we define a cold basic block to be one that's never executed.
859 assert(GetBFI && "GetBFI must be available");
860 BlockFrequencyInfo *BFI = &(GetBFI(F));
861 assert(BFI && "BFI must be available");
862 auto ProfileCount = BFI->getBlockProfileCount(BB);
863 if (*ProfileCount == 0)
864 ColdSize += Cost - CostAtBBStart;
865 }
866
867 auto *TI = BB->getTerminator();
868 // If we had any successors at this point, than post-inlining is likely to
869 // have them as well. Note that we assume any basic blocks which existed
870 // due to branches or switches which folded above will also fold after
871 // inlining.
872 if (SingleBB && TI->getNumSuccessors() > 1) {
873 // Take off the bonus we applied to the threshold.
874 Threshold -= SingleBBBonus;
875 SingleBB = false;
876 }
877 }
878
879 void onInstructionAnalysisStart(const Instruction *I) override {
880 // This function is called to store the initial cost of inlining before
881 // the given instruction was assessed.
882 if (!PrintInstructionComments)
883 return;
884 auto &CostDetail = InstructionCostDetailMap[I];
885 CostDetail.CostBefore = Cost;
886 CostDetail.ThresholdBefore = Threshold;
887 }
888
889 void onInstructionAnalysisFinish(const Instruction *I) override {
890 // This function is called to find new values of cost and threshold after
891 // the instruction has been assessed.
892 if (!PrintInstructionComments)
893 return;
894 auto &CostDetail = InstructionCostDetailMap[I];
895 CostDetail.CostAfter = Cost;
896 CostDetail.ThresholdAfter = Threshold;
897 }
898
899 bool isCostBenefitAnalysisEnabled() {
900 if (!PSI || !PSI->hasProfileSummary())
901 return false;
902
903 if (!GetBFI)
904 return false;
905
906 if (InlineEnableCostBenefitAnalysis.getNumOccurrences()) {
907 // Honor the explicit request from the user.
908 if (!InlineEnableCostBenefitAnalysis)
909 return false;
910 } else {
911 // Otherwise, require instrumentation profile.
912 if (!PSI->hasInstrumentationProfile())
913 return false;
914 }
915
916 auto *Caller = CandidateCall.getParent()->getParent();
917 if (!Caller->getEntryCount())
918 return false;
919
920 BlockFrequencyInfo *CallerBFI = &(GetBFI(*Caller));
921 if (!CallerBFI)
922 return false;
923
924 // For now, limit to hot call site.
925 if (!PSI->isHotCallSite(CB: CandidateCall, BFI: CallerBFI))
926 return false;
927
928 // Make sure we have a nonzero entry count.
929 auto EntryCount = F.getEntryCount();
930 if (!EntryCount || *EntryCount == 0)
931 return false;
932
933 BlockFrequencyInfo *CalleeBFI = &(GetBFI(F));
934 if (!CalleeBFI)
935 return false;
936
937 return true;
938 }
939
940 // A helper function to choose between command line override and default.
941 unsigned getInliningCostBenefitAnalysisSavingsMultiplier() const {
942 if (InlineSavingsMultiplier.getNumOccurrences())
943 return InlineSavingsMultiplier;
944 return TTI.getInliningCostBenefitAnalysisSavingsMultiplier();
945 }
946
947 // A helper function to choose between command line override and default.
948 unsigned getInliningCostBenefitAnalysisProfitableMultiplier() const {
949 if (InlineSavingsProfitableMultiplier.getNumOccurrences())
950 return InlineSavingsProfitableMultiplier;
951 return TTI.getInliningCostBenefitAnalysisProfitableMultiplier();
952 }
953
954 void OverrideCycleSavingsAndSizeForTesting(APInt &CycleSavings, int &Size) {
955 if (std::optional<int> AttrCycleSavings = getStringFnAttrAsInt(
956 CB&: CandidateCall, AttrKind: "inline-cycle-savings-for-test")) {
957 CycleSavings = *AttrCycleSavings;
958 }
959
960 if (std::optional<int> AttrRuntimeCost = getStringFnAttrAsInt(
961 CB&: CandidateCall, AttrKind: "inline-runtime-cost-for-test")) {
962 Size = *AttrRuntimeCost;
963 }
964 }
965
966 // Determine whether we should inline the given call site, taking into account
967 // both the size cost and the cycle savings. Return std::nullopt if we don't
968 // have sufficient profiling information to determine.
969 std::optional<bool> costBenefitAnalysis() {
970 if (!CostBenefitAnalysisEnabled)
971 return std::nullopt;
972
973 // buildInlinerPipeline in the pass builder sets HotCallSiteThreshold to 0
974 // for the prelink phase of the AutoFDO + ThinLTO build. Honor the logic by
975 // falling back to the cost-based metric.
976 // TODO: Improve this hacky condition.
977 if (Threshold == 0)
978 return std::nullopt;
979
980 assert(GetBFI);
981 BlockFrequencyInfo *CalleeBFI = &(GetBFI(F));
982 assert(CalleeBFI);
983
984 // The cycle savings expressed as the sum of InstrCost
985 // multiplied by the estimated dynamic count of each instruction we can
986 // avoid. Savings come from the call site cost, such as argument setup and
987 // the call instruction, as well as the instructions that are folded.
988 //
989 // We use 128-bit APInt here to avoid potential overflow. This variable
990 // should stay well below 10^^24 (or 2^^80) in practice. This "worst" case
991 // assumes that we can avoid or fold a billion instructions, each with a
992 // profile count of 10^^15 -- roughly the number of cycles for a 24-hour
993 // period on a 4GHz machine.
994 APInt CycleSavings(128, 0);
995
996 for (auto &BB : F) {
997 APInt CurrentSavings(128, 0);
998 for (auto &I : BB) {
999 if (CondBrInst *BI = dyn_cast<CondBrInst>(Val: &I)) {
1000 // Count a conditional branch as savings if it becomes unconditional.
1001 if (getSimplifiedValue<ConstantInt>(V: BI->getCondition()))
1002 CurrentSavings += InstrCost;
1003 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: &I)) {
1004 if (getSimplifiedValue<ConstantInt>(V: SI->getCondition()))
1005 CurrentSavings += InstrCost;
1006 } else if (SimplifiedValues.count(Val: &I)) {
1007 // Count an instruction as savings if we can fold it.
1008 CurrentSavings += InstrCost;
1009 }
1010 }
1011
1012 auto ProfileCount = CalleeBFI->getBlockProfileCount(BB: &BB);
1013 CurrentSavings *= *ProfileCount;
1014 CycleSavings += CurrentSavings;
1015 }
1016
1017 // Compute the cycle savings per call.
1018 auto EntryProfileCount = F.getEntryCount();
1019 assert(EntryProfileCount && *EntryProfileCount);
1020 CycleSavings += *EntryProfileCount / 2;
1021 CycleSavings = CycleSavings.udiv(RHS: *EntryProfileCount);
1022
1023 // Compute the total savings for the call site.
1024 auto *CallerBB = CandidateCall.getParent();
1025 BlockFrequencyInfo *CallerBFI = &(GetBFI(*(CallerBB->getParent())));
1026 CycleSavings += getCallsiteCost(TTI, Call: this->CandidateCall, DL);
1027 CycleSavings *= *CallerBFI->getBlockProfileCount(BB: CallerBB);
1028
1029 // Remove the cost of the cold basic blocks to model the runtime cost more
1030 // accurately. Both machine block placement and function splitting could
1031 // place cold blocks further from hot blocks.
1032 int Size = Cost - ColdSize;
1033
1034 // Allow tiny callees to be inlined regardless of whether they meet the
1035 // savings threshold.
1036 Size = Size > InlineSizeAllowance ? Size - InlineSizeAllowance : 1;
1037
1038 OverrideCycleSavingsAndSizeForTesting(CycleSavings, Size);
1039 CostBenefit.emplace(args: APInt(128, Size), args&: CycleSavings);
1040
1041 // Let R be the ratio of CycleSavings to Size. We accept the inlining
1042 // opportunity if R is really high and reject if R is really low. If R is
1043 // somewhere in the middle, we fall back to the cost-based analysis.
1044 //
1045 // Specifically, let R = CycleSavings / Size, we accept the inlining
1046 // opportunity if:
1047 //
1048 // PSI->getOrCompHotCountThreshold()
1049 // R > -------------------------------------------------
1050 // getInliningCostBenefitAnalysisSavingsMultiplier()
1051 //
1052 // and reject the inlining opportunity if:
1053 //
1054 // PSI->getOrCompHotCountThreshold()
1055 // R <= ----------------------------------------------------
1056 // getInliningCostBenefitAnalysisProfitableMultiplier()
1057 //
1058 // Otherwise, we fall back to the cost-based analysis.
1059 //
1060 // Implementation-wise, use multiplication (CycleSavings * Multiplier,
1061 // HotCountThreshold * Size) rather than division to avoid precision loss.
1062 APInt Threshold(128, PSI->getOrCompHotCountThreshold());
1063 Threshold *= Size;
1064
1065 APInt UpperBoundCycleSavings = CycleSavings;
1066 UpperBoundCycleSavings *= getInliningCostBenefitAnalysisSavingsMultiplier();
1067 if (UpperBoundCycleSavings.uge(RHS: Threshold))
1068 return true;
1069
1070 APInt LowerBoundCycleSavings = CycleSavings;
1071 LowerBoundCycleSavings *=
1072 getInliningCostBenefitAnalysisProfitableMultiplier();
1073 if (LowerBoundCycleSavings.ult(RHS: Threshold))
1074 return false;
1075
1076 // Otherwise, fall back to the cost-based analysis.
1077 return std::nullopt;
1078 }
1079
1080 InlineResult finalizeAnalysis() override {
1081 // Loops generally act a lot like calls in that they act like barriers to
1082 // movement, require a certain amount of setup, etc. So when optimising for
1083 // size, we penalise any call sites that perform loops. We do this after all
1084 // other costs here, so will likely only be dealing with relatively small
1085 // functions (and hence LI will hopefully be cheap).
1086 auto *Caller = CandidateCall.getFunction();
1087 if (Caller->hasMinSize()) {
1088 LoopInfo LI;
1089 LI.analyze(F: &F);
1090 int NumLoops = 0;
1091 for (Loop *L : LI) {
1092 // Ignore loops that will not be executed
1093 if (DeadBlocks.count(Ptr: L->getHeader()))
1094 continue;
1095 NumLoops++;
1096 }
1097 addCost(Inc: NumLoops * InlineConstants::LoopPenalty);
1098 }
1099
1100 // We applied the maximum possible vector bonus at the beginning. Now,
1101 // subtract the excess bonus, if any, from the Threshold before
1102 // comparing against Cost.
1103 if (NumVectorInstructions <= NumInstructions / 10)
1104 Threshold -= VectorBonus;
1105 else if (NumVectorInstructions <= NumInstructions / 2)
1106 Threshold -= VectorBonus / 2;
1107
1108 if (std::optional<int> AttrCost =
1109 getStringFnAttrAsInt(CB&: CandidateCall, AttrKind: "function-inline-cost"))
1110 Cost = *AttrCost;
1111
1112 if (std::optional<int> AttrCostMult = getStringFnAttrAsInt(
1113 CB&: CandidateCall,
1114 AttrKind: InlineConstants::FunctionInlineCostMultiplierAttributeName))
1115 Cost *= *AttrCostMult;
1116
1117 if (std::optional<int> AttrThreshold =
1118 getStringFnAttrAsInt(CB&: CandidateCall, AttrKind: "function-inline-threshold"))
1119 Threshold = *AttrThreshold;
1120
1121 if (auto Result = costBenefitAnalysis()) {
1122 DecidedByCostBenefit = true;
1123 if (*Result)
1124 return InlineResult::success();
1125 else
1126 return InlineResult::failure(Reason: "Cost over threshold.");
1127 }
1128
1129 if (IgnoreThreshold)
1130 return InlineResult::success();
1131
1132 DecidedByCostThreshold = true;
1133 return Cost < std::max(a: 1, b: Threshold)
1134 ? InlineResult::success()
1135 : InlineResult::failure(Reason: "Cost over threshold.");
1136 }
1137
1138 bool shouldStop() override {
1139 if (IgnoreThreshold || ComputeFullInlineCost)
1140 return false;
1141 // Bail out the moment we cross the threshold. This means we'll under-count
1142 // the cost, but only when undercounting doesn't matter.
1143 if (Cost < Threshold)
1144 return false;
1145 DecidedByCostThreshold = true;
1146 return true;
1147 }
1148
1149 void onLoadEliminationOpportunity() override {
1150 LoadEliminationCost += InstrCost;
1151 }
1152
1153 InlineResult onAnalysisStart() override {
1154 // Perform some tweaks to the cost and threshold based on the direct
1155 // callsite information.
1156
1157 // We want to more aggressively inline vector-dense kernels, so up the
1158 // threshold, and we'll lower it if the % of vector instructions gets too
1159 // low. Note that these bonuses are some what arbitrary and evolved over
1160 // time by accident as much as because they are principled bonuses.
1161 //
1162 // FIXME: It would be nice to remove all such bonuses. At least it would be
1163 // nice to base the bonus values on something more scientific.
1164 assert(NumInstructions == 0);
1165 assert(NumVectorInstructions == 0);
1166
1167 // Update the threshold based on callsite properties
1168 updateThreshold(Call&: CandidateCall, Callee&: F);
1169
1170 // While Threshold depends on commandline options that can take negative
1171 // values, we want to enforce the invariant that the computed threshold and
1172 // bonuses are non-negative.
1173 assert(Threshold >= 0);
1174 assert(SingleBBBonus >= 0);
1175 assert(VectorBonus >= 0);
1176
1177 // Speculatively apply all possible bonuses to Threshold. If cost exceeds
1178 // this Threshold any time, and cost cannot decrease, we can stop processing
1179 // the rest of the function body.
1180 Threshold += (SingleBBBonus + VectorBonus);
1181
1182 // Give out bonuses for the callsite, as the instructions setting them up
1183 // will be gone after inlining.
1184 addCost(Inc: -getCallsiteCost(TTI, Call: this->CandidateCall, DL));
1185
1186 // If this function uses the coldcc calling convention, prefer not to inline
1187 // it.
1188 if (F.getCallingConv() == CallingConv::Cold)
1189 addCost(Inc: InlineConstants::ColdccPenalty);
1190
1191 LLVM_DEBUG(dbgs() << " Initial cost: " << Cost << "\n");
1192
1193 // Check if we're done. This can happen due to bonuses and penalties.
1194 if (Cost >= Threshold && !ComputeFullInlineCost)
1195 return InlineResult::failure(Reason: "high cost");
1196
1197 return InlineResult::success();
1198 }
1199
1200public:
1201 InlineCostCallAnalyzer(
1202 Function &Callee, CallBase &Call, const InlineParams &Params,
1203 const TargetTransformInfo &TTI,
1204 function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
1205 function_ref<BlockFrequencyInfo &(Function &)> GetBFI = nullptr,
1206 function_ref<const TargetLibraryInfo &(Function &)> GetTLI = nullptr,
1207 ProfileSummaryInfo *PSI = nullptr,
1208 OptimizationRemarkEmitter *ORE = nullptr, bool BoostIndirect = true,
1209 bool IgnoreThreshold = false,
1210 function_ref<EphemeralValuesCache &(Function &)> GetEphValuesCache =
1211 nullptr)
1212 : CallAnalyzer(Callee, Call, TTI, GetAssumptionCache, GetBFI, GetTLI, PSI,
1213 ORE, GetEphValuesCache),
1214 ComputeFullInlineCost(OptComputeFullInlineCost ||
1215 Params.ComputeFullInlineCost || ORE ||
1216 isCostBenefitAnalysisEnabled()),
1217 Params(Params), Threshold(Params.DefaultThreshold),
1218 BoostIndirectCalls(BoostIndirect), IgnoreThreshold(IgnoreThreshold),
1219 CostBenefitAnalysisEnabled(isCostBenefitAnalysisEnabled()),
1220 Writer(this) {
1221 AllowRecursiveCall = *Params.AllowRecursiveCall;
1222 }
1223
1224 /// Annotation Writer for instruction details
1225 InlineCostAnnotationWriter Writer;
1226
1227 void dump();
1228
1229 // Prints the same analysis as dump(), but its definition is not dependent
1230 // on the build.
1231 void print(raw_ostream &OS);
1232
1233 std::optional<InstructionCostDetail> getCostDetails(const Instruction *I) {
1234 auto It = InstructionCostDetailMap.find(Val: I);
1235 if (It != InstructionCostDetailMap.end())
1236 return It->second;
1237 return std::nullopt;
1238 }
1239
1240 ~InlineCostCallAnalyzer() override = default;
1241 int getThreshold() const { return Threshold; }
1242 int getCost() const { return Cost; }
1243 int getStaticBonusApplied() const { return StaticBonusApplied; }
1244 std::optional<CostBenefitPair> getCostBenefitPair() { return CostBenefit; }
1245 bool wasDecidedByCostBenefit() const { return DecidedByCostBenefit; }
1246 bool wasDecidedByCostThreshold() const { return DecidedByCostThreshold; }
1247};
1248
1249// Return true if CB is the sole call to local function Callee.
1250static bool isSoleCallToLocalFunction(const CallBase &CB,
1251 const Function &Callee) {
1252 return Callee.hasLocalLinkage() && Callee.hasOneLiveUse() &&
1253 &Callee == CB.getCalledFunction();
1254}
1255
1256class InlineCostFeaturesAnalyzer final : public CallAnalyzer {
1257private:
1258 InlineCostFeatures Cost = {};
1259
1260 // FIXME: These constants are taken from the heuristic-based cost visitor.
1261 // These should be removed entirely in a later revision to avoid reliance on
1262 // heuristics in the ML inliner.
1263 static constexpr int JTCostMultiplier = 2;
1264 static constexpr int CaseClusterCostMultiplier = 2;
1265 static constexpr int SwitchDefaultDestCostMultiplier = 2;
1266 static constexpr int SwitchCostMultiplier = 2;
1267
1268 // FIXME: These are taken from the heuristic-based cost visitor: we should
1269 // eventually abstract these to the CallAnalyzer to avoid duplication.
1270 unsigned SROACostSavingOpportunities = 0;
1271 int VectorBonus = 0;
1272 int SingleBBBonus = 0;
1273 int Threshold = 5;
1274
1275 DenseMap<AllocaInst *, unsigned> SROACosts;
1276
1277 void increment(InlineCostFeatureIndex Feature, int64_t Delta = 1) {
1278 Cost[static_cast<size_t>(Feature)] += Delta;
1279 }
1280
1281 void set(InlineCostFeatureIndex Feature, int64_t Value) {
1282 Cost[static_cast<size_t>(Feature)] = Value;
1283 }
1284
1285 void onDisableSROA(AllocaInst *Arg) override {
1286 auto CostIt = SROACosts.find(Val: Arg);
1287 if (CostIt == SROACosts.end())
1288 return;
1289
1290 increment(Feature: InlineCostFeatureIndex::sroa_losses, Delta: CostIt->second);
1291 SROACostSavingOpportunities -= CostIt->second;
1292 SROACosts.erase(I: CostIt);
1293 }
1294
1295 void onDisableLoadElimination() override {
1296 set(Feature: InlineCostFeatureIndex::load_elimination, Value: 1);
1297 }
1298
1299 void onCallPenalty() override {
1300 increment(Feature: InlineCostFeatureIndex::call_penalty, Delta: CallPenalty);
1301 }
1302
1303 void onCallArgumentSetup(const CallBase &Call) override {
1304 increment(Feature: InlineCostFeatureIndex::call_argument_setup,
1305 Delta: Call.arg_size() * InstrCost);
1306 }
1307
1308 void onLoadRelativeIntrinsic() override {
1309 increment(Feature: InlineCostFeatureIndex::load_relative_intrinsic, Delta: 3 * InstrCost);
1310 }
1311
1312 void onLoweredCall(Function *F, CallBase &Call,
1313 bool IsIndirectCall) override {
1314 increment(Feature: InlineCostFeatureIndex::lowered_call_arg_setup,
1315 Delta: Call.arg_size() * InstrCost);
1316
1317 if (IsIndirectCall) {
1318 InlineParams IndirectCallParams = {/* DefaultThreshold*/ 0,
1319 /*HintThreshold*/ {},
1320 /*OptSizeHintThreshold*/ {},
1321 /*ColdThreshold*/ {},
1322 /*OptSizeThreshold*/ {},
1323 /*OptMinSizeThreshold*/ {},
1324 /*HotCallSiteThreshold*/ {},
1325 /*LocallyHotCallSiteThreshold*/ {},
1326 /*ColdCallSiteThreshold*/ {},
1327 /*ComputeFullInlineCost*/ true,
1328 /*EnableDeferral*/ true};
1329 IndirectCallParams.DefaultThreshold =
1330 InlineConstants::IndirectCallThreshold;
1331
1332 InlineCostCallAnalyzer CA(*F, Call, IndirectCallParams, TTI,
1333 GetAssumptionCache, GetBFI, GetTLI, PSI, ORE,
1334 false, true);
1335 if (CA.analyze().isSuccess()) {
1336 increment(Feature: InlineCostFeatureIndex::nested_inline_cost_estimate,
1337 Delta: CA.getCost());
1338 increment(Feature: InlineCostFeatureIndex::nested_inlines, Delta: 1);
1339 }
1340 } else {
1341 onCallPenalty();
1342 }
1343 }
1344
1345 void onFinalizeSwitch(unsigned JumpTableSize, unsigned NumCaseCluster,
1346 bool DefaultDestUnreachable) override {
1347 if (JumpTableSize) {
1348 if (!DefaultDestUnreachable)
1349 increment(Feature: InlineCostFeatureIndex::switch_default_dest_penalty,
1350 Delta: SwitchDefaultDestCostMultiplier * InstrCost);
1351 int64_t JTCost = static_cast<int64_t>(JumpTableSize) * InstrCost +
1352 JTCostMultiplier * InstrCost;
1353 increment(Feature: InlineCostFeatureIndex::jump_table_penalty, Delta: JTCost);
1354 return;
1355 }
1356
1357 if (NumCaseCluster <= 3) {
1358 increment(Feature: InlineCostFeatureIndex::case_cluster_penalty,
1359 Delta: (NumCaseCluster - DefaultDestUnreachable) *
1360 CaseClusterCostMultiplier * InstrCost);
1361 return;
1362 }
1363
1364 int64_t ExpectedNumberOfCompare =
1365 getExpectedNumberOfCompare(NumCaseCluster);
1366
1367 int64_t SwitchCost =
1368 ExpectedNumberOfCompare * SwitchCostMultiplier * InstrCost;
1369 increment(Feature: InlineCostFeatureIndex::switch_penalty, Delta: SwitchCost);
1370 }
1371
1372 void onMissedSimplification() override {
1373 increment(Feature: InlineCostFeatureIndex::unsimplified_common_instructions,
1374 Delta: InstrCost);
1375 }
1376
1377 void onInitializeSROAArg(AllocaInst *Arg) override {
1378 auto SROAArgCost = TTI.getCallerAllocaCost(CB: &CandidateCall, AI: Arg);
1379 SROACosts[Arg] = SROAArgCost;
1380 SROACostSavingOpportunities += SROAArgCost;
1381 }
1382
1383 void onAggregateSROAUse(AllocaInst *Arg) override {
1384 SROACosts.find(Val: Arg)->second += InstrCost;
1385 SROACostSavingOpportunities += InstrCost;
1386 }
1387
1388 void onBlockAnalyzed(const BasicBlock *BB) override {
1389 if (BB->getTerminator()->getNumSuccessors() > 1)
1390 set(Feature: InlineCostFeatureIndex::is_multiple_blocks, Value: 1);
1391 Threshold -= SingleBBBonus;
1392 }
1393
1394 InlineResult finalizeAnalysis() override {
1395 auto *Caller = CandidateCall.getFunction();
1396 if (Caller->hasMinSize()) {
1397 LoopInfo LI;
1398 LI.analyze(F: &F);
1399 for (Loop *L : LI) {
1400 // Ignore loops that will not be executed
1401 if (DeadBlocks.count(Ptr: L->getHeader()))
1402 continue;
1403 increment(Feature: InlineCostFeatureIndex::num_loops,
1404 Delta: InlineConstants::LoopPenalty);
1405 }
1406 }
1407 set(Feature: InlineCostFeatureIndex::dead_blocks, Value: DeadBlocks.size());
1408 set(Feature: InlineCostFeatureIndex::simplified_instructions,
1409 Value: NumInstructionsSimplified);
1410 set(Feature: InlineCostFeatureIndex::constant_args, Value: NumConstantArgs);
1411 set(Feature: InlineCostFeatureIndex::constant_offset_ptr_args,
1412 Value: NumConstantOffsetPtrArgs);
1413 set(Feature: InlineCostFeatureIndex::sroa_savings, Value: SROACostSavingOpportunities);
1414
1415 if (NumVectorInstructions <= NumInstructions / 10)
1416 Threshold -= VectorBonus;
1417 else if (NumVectorInstructions <= NumInstructions / 2)
1418 Threshold -= VectorBonus / 2;
1419
1420 set(Feature: InlineCostFeatureIndex::threshold, Value: Threshold);
1421
1422 return InlineResult::success();
1423 }
1424
1425 bool shouldStop() override { return false; }
1426
1427 void onLoadEliminationOpportunity() override {
1428 increment(Feature: InlineCostFeatureIndex::load_elimination, Delta: 1);
1429 }
1430
1431 InlineResult onAnalysisStart() override {
1432 increment(Feature: InlineCostFeatureIndex::callsite_cost,
1433 Delta: -1 * getCallsiteCost(TTI, Call: this->CandidateCall, DL));
1434
1435 set(Feature: InlineCostFeatureIndex::cold_cc_penalty,
1436 Value: (F.getCallingConv() == CallingConv::Cold));
1437
1438 set(Feature: InlineCostFeatureIndex::last_call_to_static_bonus,
1439 Value: isSoleCallToLocalFunction(CB: CandidateCall, Callee: F));
1440
1441 // FIXME: we shouldn't repeat this logic in both the Features and Cost
1442 // analyzer - instead, we should abstract it to a common method in the
1443 // CallAnalyzer
1444 int SingleBBBonusPercent = 50;
1445 int VectorBonusPercent = TTI.getInlinerVectorBonusPercent();
1446 Threshold += TTI.adjustInliningThreshold(CB: &CandidateCall);
1447 Threshold *= TTI.getInliningThresholdMultiplier();
1448 SingleBBBonus = Threshold * SingleBBBonusPercent / 100;
1449 VectorBonus = Threshold * VectorBonusPercent / 100;
1450 Threshold += (SingleBBBonus + VectorBonus);
1451
1452 return InlineResult::success();
1453 }
1454
1455public:
1456 InlineCostFeaturesAnalyzer(
1457 const TargetTransformInfo &TTI,
1458 function_ref<AssumptionCache &(Function &)> &GetAssumptionCache,
1459 function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
1460 function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
1461 ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE, Function &Callee,
1462 CallBase &Call)
1463 : CallAnalyzer(Callee, Call, TTI, GetAssumptionCache, GetBFI, GetTLI,
1464 PSI) {}
1465
1466 const InlineCostFeatures &features() const { return Cost; }
1467};
1468
1469} // namespace
1470
1471/// Test whether the given value is an Alloca-derived function argument.
1472bool CallAnalyzer::isAllocaDerivedArg(Value *V) {
1473 return SROAArgValues.count(Val: V);
1474}
1475
1476void CallAnalyzer::disableSROAForArg(AllocaInst *SROAArg) {
1477 onDisableSROA(Arg: SROAArg);
1478 EnabledSROAAllocas.erase(V: SROAArg);
1479 disableLoadElimination();
1480}
1481
1482void InlineCostAnnotationWriter::emitInstructionAnnot(
1483 const Instruction *I, formatted_raw_ostream &OS) {
1484 // The cost of inlining of the given instruction is printed always.
1485 // The threshold delta is printed only when it is non-zero. It happens
1486 // when we decided to give a bonus at a particular instruction.
1487 std::optional<InstructionCostDetail> Record = ICCA->getCostDetails(I);
1488 if (!Record)
1489 OS << "; No analysis for the instruction";
1490 else {
1491 OS << "; cost before = " << Record->CostBefore
1492 << ", cost after = " << Record->CostAfter
1493 << ", threshold before = " << Record->ThresholdBefore
1494 << ", threshold after = " << Record->ThresholdAfter << ", ";
1495 OS << "cost delta = " << Record->getCostDelta();
1496 if (Record->hasThresholdChanged())
1497 OS << ", threshold delta = " << Record->getThresholdDelta();
1498 }
1499 auto *V = ICCA->getSimplifiedValueUnchecked(V: const_cast<Instruction *>(I));
1500 if (V) {
1501 OS << ", simplified to ";
1502 V->print(O&: OS, IsForDebug: true);
1503 if (auto *VI = dyn_cast<Instruction>(Val: V)) {
1504 if (VI->getFunction() != I->getFunction())
1505 OS << " (caller instruction)";
1506 } else if (auto *VArg = dyn_cast<Argument>(Val: V)) {
1507 if (VArg->getParent() != I->getFunction())
1508 OS << " (caller argument)";
1509 }
1510 }
1511 OS << "\n";
1512}
1513
1514/// If 'V' maps to a SROA candidate, disable SROA for it.
1515void CallAnalyzer::disableSROA(Value *V) {
1516 if (auto *SROAArg = getSROAArgForValueOrNull(V)) {
1517 disableSROAForArg(SROAArg);
1518 }
1519}
1520
1521void CallAnalyzer::disableLoadElimination() {
1522 if (EnableLoadElimination) {
1523 onDisableLoadElimination();
1524 EnableLoadElimination = false;
1525 }
1526}
1527
1528/// Accumulate a constant GEP offset into an APInt if possible.
1529///
1530/// Returns false if unable to compute the offset for any reason. Respects any
1531/// simplified values known during the analysis of this callsite.
1532bool CallAnalyzer::accumulateGEPOffset(GEPOperator &GEP, APInt &Offset) {
1533 unsigned IntPtrWidth = DL.getIndexTypeSizeInBits(Ty: GEP.getType());
1534 assert(IntPtrWidth == Offset.getBitWidth());
1535
1536 for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
1537 GTI != GTE; ++GTI) {
1538 ConstantInt *OpC =
1539 getDirectOrSimplifiedValue<ConstantInt>(V: GTI.getOperand());
1540 if (!OpC)
1541 return false;
1542 if (OpC->isZero())
1543 continue;
1544
1545 // Handle a struct index, which adds its field offset to the pointer.
1546 if (StructType *STy = GTI.getStructTypeOrNull()) {
1547 unsigned ElementIdx = OpC->getZExtValue();
1548 const StructLayout *SL = DL.getStructLayout(Ty: STy);
1549 Offset += APInt(IntPtrWidth, SL->getElementOffset(Idx: ElementIdx));
1550 continue;
1551 }
1552
1553 APInt TypeSize(IntPtrWidth, GTI.getSequentialElementStride(DL));
1554 Offset += OpC->getValue().sextOrTrunc(width: IntPtrWidth) * TypeSize;
1555 }
1556 return true;
1557}
1558
1559/// Use TTI to check whether a GEP is free.
1560///
1561/// Respects any simplified values known during the analysis of this callsite.
1562bool CallAnalyzer::isGEPFree(GetElementPtrInst &GEP) {
1563 SmallVector<Value *, 4> Operands;
1564 Operands.push_back(Elt: GEP.getOperand(i_nocapture: 0));
1565 for (const Use &Op : GEP.indices())
1566 if (Constant *SimpleOp = getSimplifiedValue<Constant>(V: Op))
1567 Operands.push_back(Elt: SimpleOp);
1568 else
1569 Operands.push_back(Elt: Op);
1570 return TTI.getInstructionCost(U: &GEP, Operands,
1571 CostKind: TargetTransformInfo::TCK_SizeAndLatency) ==
1572 TargetTransformInfo::TCC_Free;
1573}
1574
1575bool CallAnalyzer::visitAlloca(AllocaInst &I) {
1576 disableSROA(V: I.getOperand(i_nocapture: 0));
1577
1578 // Check whether inlining will turn a dynamic alloca into a static
1579 // alloca and handle that case.
1580 if (I.isArrayAllocation()) {
1581 Constant *Size = getSimplifiedValue<Constant>(V: I.getArraySize());
1582 if (auto *AllocSize = dyn_cast_or_null<ConstantInt>(Val: Size)) {
1583 // Sometimes a dynamic alloca could be converted into a static alloca
1584 // after this constant prop, and become a huge static alloca on an
1585 // unconditional CFG path. Avoid inlining if this is going to happen above
1586 // a threshold.
1587 // FIXME: If the threshold is removed or lowered too much, we could end up
1588 // being too pessimistic and prevent inlining non-problematic code. This
1589 // could result in unintended perf regressions. A better overall strategy
1590 // is needed to track stack usage during inlining.
1591 AllocatedSize = SaturatingMultiplyAdd(
1592 X: AllocSize->getLimitedValue(),
1593 Y: I.getAllocationBaseSize(DL).getKnownMinValue(), A: AllocatedSize);
1594 if (AllocatedSize > InlineConstants::MaxSimplifiedDynamicAllocaToInline)
1595 HasDynamicAlloca = true;
1596 return false;
1597 }
1598 }
1599
1600 if (I.isStaticAlloca()) {
1601 // Accumulate the allocated size if constant and executed once.
1602 // Note: if AllocSize is a vscale value, this is an underestimate of the
1603 // allocated size, and it also requires some of the cost of a dynamic
1604 // alloca, but is recorded here as a constant size alloca.
1605 TypeSize AllocSize = I.getAllocationSize(DL).value_or(u: TypeSize::getZero());
1606 AllocatedSize = SaturatingAdd(X: AllocSize.getKnownMinValue(), Y: AllocatedSize);
1607 } else {
1608 // FIXME: This is overly conservative. Dynamic allocas are inefficient for
1609 // a variety of reasons, and so we would like to not inline them into
1610 // functions which don't currently have a dynamic alloca. This simply
1611 // disables inlining altogether in the presence of a dynamic alloca.
1612 HasDynamicAlloca = true;
1613 }
1614
1615 return false;
1616}
1617
1618bool CallAnalyzer::visitPHI(PHINode &I) {
1619 // FIXME: We need to propagate SROA *disabling* through phi nodes, even
1620 // though we don't want to propagate it's bonuses. The idea is to disable
1621 // SROA if it *might* be used in an inappropriate manner.
1622
1623 // Phi nodes are always zero-cost.
1624 // FIXME: Pointer sizes may differ between different address spaces, so do we
1625 // need to use correct address space in the call to getPointerSizeInBits here?
1626 // Or could we skip the getPointerSizeInBits call completely? As far as I can
1627 // see the ZeroOffset is used as a dummy value, so we can probably use any
1628 // bit width for the ZeroOffset?
1629 APInt ZeroOffset = APInt::getZero(numBits: DL.getPointerSizeInBits(AS: 0));
1630 bool CheckSROA = I.getType()->isPointerTy();
1631
1632 // Track the constant or pointer with constant offset we've seen so far.
1633 Constant *FirstC = nullptr;
1634 std::pair<Value *, APInt> FirstBaseAndOffset = {nullptr, ZeroOffset};
1635 Value *FirstV = nullptr;
1636
1637 for (unsigned i = 0, e = I.getNumIncomingValues(); i != e; ++i) {
1638 BasicBlock *Pred = I.getIncomingBlock(i);
1639 // If the incoming block is dead, skip the incoming block.
1640 if (DeadBlocks.count(Ptr: Pred))
1641 continue;
1642 // If the parent block of phi is not the known successor of the incoming
1643 // block, skip the incoming block.
1644 BasicBlock *KnownSuccessor = KnownSuccessors[Pred];
1645 if (KnownSuccessor && KnownSuccessor != I.getParent())
1646 continue;
1647
1648 Value *V = I.getIncomingValue(i);
1649 // If the incoming value is this phi itself, skip the incoming value.
1650 if (&I == V)
1651 continue;
1652
1653 Constant *C = getDirectOrSimplifiedValue<Constant>(V);
1654
1655 std::pair<Value *, APInt> BaseAndOffset = {nullptr, ZeroOffset};
1656 if (!C && CheckSROA)
1657 BaseAndOffset = ConstantOffsetPtrs.lookup(Val: V);
1658
1659 if (!C && !BaseAndOffset.first)
1660 // The incoming value is neither a constant nor a pointer with constant
1661 // offset, exit early.
1662 return true;
1663
1664 if (FirstC) {
1665 if (FirstC == C)
1666 // If we've seen a constant incoming value before and it is the same
1667 // constant we see this time, continue checking the next incoming value.
1668 continue;
1669 // Otherwise early exit because we either see a different constant or saw
1670 // a constant before but we have a pointer with constant offset this time.
1671 return true;
1672 }
1673
1674 if (FirstV) {
1675 // The same logic as above, but check pointer with constant offset here.
1676 if (FirstBaseAndOffset == BaseAndOffset)
1677 continue;
1678 return true;
1679 }
1680
1681 if (C) {
1682 // This is the 1st time we've seen a constant, record it.
1683 FirstC = C;
1684 continue;
1685 }
1686
1687 // The remaining case is that this is the 1st time we've seen a pointer with
1688 // constant offset, record it.
1689 FirstV = V;
1690 FirstBaseAndOffset = BaseAndOffset;
1691 }
1692
1693 // Check if we can map phi to a constant.
1694 if (FirstC) {
1695 SimplifiedValues[&I] = FirstC;
1696 return true;
1697 }
1698
1699 // Check if we can map phi to a pointer with constant offset.
1700 if (FirstBaseAndOffset.first) {
1701 ConstantOffsetPtrs[&I] = std::move(FirstBaseAndOffset);
1702
1703 if (auto *SROAArg = getSROAArgForValueOrNull(V: FirstV))
1704 SROAArgValues[&I] = SROAArg;
1705 }
1706
1707 return true;
1708}
1709
1710/// Check we can fold GEPs of constant-offset call site argument pointers.
1711/// This requires target data and inbounds GEPs.
1712///
1713/// \return true if the specified GEP can be folded.
1714bool CallAnalyzer::canFoldInboundsGEP(GetElementPtrInst &I) {
1715 // Check if we have a base + offset for the pointer.
1716 std::pair<Value *, APInt> BaseAndOffset =
1717 ConstantOffsetPtrs.lookup(Val: I.getPointerOperand());
1718 if (!BaseAndOffset.first)
1719 return false;
1720
1721 // Check if the offset of this GEP is constant, and if so accumulate it
1722 // into Offset.
1723 if (!accumulateGEPOffset(GEP&: cast<GEPOperator>(Val&: I), Offset&: BaseAndOffset.second))
1724 return false;
1725
1726 // Add the result as a new mapping to Base + Offset.
1727 ConstantOffsetPtrs[&I] = std::move(BaseAndOffset);
1728
1729 return true;
1730}
1731
1732bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) {
1733 auto *SROAArg = getSROAArgForValueOrNull(V: I.getPointerOperand());
1734
1735 // Lambda to check whether a GEP's indices are all constant.
1736 auto IsGEPOffsetConstant = [&](GetElementPtrInst &GEP) {
1737 for (const Use &Op : GEP.indices())
1738 if (!getDirectOrSimplifiedValue<Constant>(V: Op))
1739 return false;
1740 return true;
1741 };
1742
1743 if (!DisableGEPConstOperand)
1744 if (simplifyInstruction(I))
1745 return true;
1746
1747 if ((I.isInBounds() && canFoldInboundsGEP(I)) || IsGEPOffsetConstant(I)) {
1748 if (SROAArg)
1749 SROAArgValues[&I] = SROAArg;
1750
1751 // Constant GEPs are modeled as free.
1752 return true;
1753 }
1754
1755 // Variable GEPs will require math and will disable SROA.
1756 if (SROAArg)
1757 disableSROAForArg(SROAArg);
1758 return isGEPFree(GEP&: I);
1759}
1760
1761// Simplify \p Cmp if RHS is const and we can ValueTrack LHS.
1762// This handles the case only when the Cmp instruction is guarding a recursive
1763// call that will cause the Cmp to fail/succeed for the recursive call.
1764bool CallAnalyzer::simplifyCmpInstForRecCall(CmpInst &Cmp) {
1765 // Bail out if LHS is not a function argument or RHS is NOT const:
1766 if (!isa<Argument>(Val: Cmp.getOperand(i_nocapture: 0)) || !isa<Constant>(Val: Cmp.getOperand(i_nocapture: 1)))
1767 return false;
1768 auto *CmpOp = Cmp.getOperand(i_nocapture: 0);
1769 // Make sure that the callsite is recursive:
1770 if (CandidateCall.getCaller() != &F)
1771 return false;
1772 // Only handle the case when the callsite has a single predecessor:
1773 auto *CallBB = CandidateCall.getParent();
1774 auto *Predecessor = CallBB->getSinglePredecessor();
1775 if (!Predecessor)
1776 return false;
1777 // Check if the callsite is guarded by the same Cmp instruction:
1778 auto *Br = dyn_cast<CondBrInst>(Val: Predecessor->getTerminator());
1779 if (!Br || Br->getCondition() != &Cmp)
1780 return false;
1781
1782 // Check if there is any arg of the recursive callsite is affecting the cmp
1783 // instr:
1784 bool ArgFound = false;
1785 Value *FuncArg = nullptr, *CallArg = nullptr;
1786 for (unsigned ArgNum = 0;
1787 ArgNum < F.arg_size() && ArgNum < CandidateCall.arg_size(); ArgNum++) {
1788 FuncArg = F.getArg(i: ArgNum);
1789 CallArg = CandidateCall.getArgOperand(i: ArgNum);
1790 if (FuncArg == CmpOp && CallArg != CmpOp) {
1791 ArgFound = true;
1792 break;
1793 }
1794 }
1795 if (!ArgFound)
1796 return false;
1797
1798 // Now we have a recursive call that is guarded by a cmp instruction.
1799 // Check if this cmp can be simplified:
1800 SimplifyQuery SQ(DL, dyn_cast<Instruction>(Val: CallArg));
1801 CondContext CC(&Cmp);
1802 CC.Invert = (CallBB != Br->getSuccessor(i: 0));
1803 SQ.CC = &CC;
1804 CC.AffectedValues.insert(Ptr: FuncArg);
1805 Value *SimplifiedInstruction = llvm::simplifyInstructionWithOperands(
1806 I: cast<CmpInst>(Val: &Cmp), NewOps: {CallArg, Cmp.getOperand(i_nocapture: 1)}, Q: SQ);
1807 if (auto *ConstVal = dyn_cast_or_null<ConstantInt>(Val: SimplifiedInstruction)) {
1808 // Make sure that the BB of the recursive call is NOT the true successor
1809 // of the icmp. In other words, make sure that the recursion depth is 1.
1810 if ((ConstVal->isOne() && CC.Invert) ||
1811 (ConstVal->isZero() && !CC.Invert)) {
1812 SimplifiedValues[&Cmp] = ConstVal;
1813 return true;
1814 }
1815 }
1816 return false;
1817}
1818
1819/// Simplify \p I if its operands are constants and update SimplifiedValues.
1820bool CallAnalyzer::simplifyInstruction(Instruction &I) {
1821 SmallVector<Constant *> COps;
1822 for (Value *Op : I.operands()) {
1823 Constant *COp = getDirectOrSimplifiedValue<Constant>(V: Op);
1824 if (!COp)
1825 return false;
1826 COps.push_back(Elt: COp);
1827 }
1828 auto *C = ConstantFoldInstOperands(I: &I, Ops: COps, DL);
1829 if (!C)
1830 return false;
1831 SimplifiedValues[&I] = C;
1832 return true;
1833}
1834
1835/// Try to simplify a call to llvm.is.constant.
1836///
1837/// Duplicate the argument checking from CallAnalyzer::simplifyCallSite since
1838/// we expect calls of this specific intrinsic to be infrequent.
1839///
1840/// FIXME: Given that we know CB's parent (F) caller
1841/// (CandidateCall->getParent()->getParent()), we might be able to determine
1842/// whether inlining F into F's caller would change how the call to
1843/// llvm.is.constant would evaluate.
1844bool CallAnalyzer::simplifyIntrinsicCallIsConstant(CallBase &CB) {
1845 Value *Arg = CB.getArgOperand(i: 0);
1846 auto *C = getDirectOrSimplifiedValue<Constant>(V: Arg);
1847
1848 Type *RT = CB.getFunctionType()->getReturnType();
1849 SimplifiedValues[&CB] = ConstantInt::get(Ty: RT, V: C ? 1 : 0);
1850 return true;
1851}
1852
1853bool CallAnalyzer::simplifyIntrinsicCallObjectSize(CallBase &CB) {
1854 // As per the langref, "The fourth argument to llvm.objectsize determines if
1855 // the value should be evaluated at runtime."
1856 if (cast<ConstantInt>(Val: CB.getArgOperand(i: 3))->isOne())
1857 return false;
1858
1859 Value *V = lowerObjectSizeCall(ObjectSize: &cast<IntrinsicInst>(Val&: CB), DL, TLI: nullptr,
1860 /*MustSucceed=*/true);
1861 Constant *C = dyn_cast_or_null<Constant>(Val: V);
1862 if (C)
1863 SimplifiedValues[&CB] = C;
1864 return C;
1865}
1866
1867bool CallAnalyzer::visitBitCast(BitCastInst &I) {
1868 // Propagate constants through bitcasts.
1869 if (simplifyInstruction(I))
1870 return true;
1871
1872 // Track base/offsets through casts
1873 std::pair<Value *, APInt> BaseAndOffset =
1874 ConstantOffsetPtrs.lookup(Val: I.getOperand(i_nocapture: 0));
1875 // Casts don't change the offset, just wrap it up.
1876 if (BaseAndOffset.first)
1877 ConstantOffsetPtrs[&I] = std::move(BaseAndOffset);
1878
1879 // Also look for SROA candidates here.
1880 if (auto *SROAArg = getSROAArgForValueOrNull(V: I.getOperand(i_nocapture: 0)))
1881 SROAArgValues[&I] = SROAArg;
1882
1883 // Bitcasts are always zero cost.
1884 return true;
1885}
1886
1887bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) {
1888 // Propagate constants through ptrtoint.
1889 if (simplifyInstruction(I))
1890 return true;
1891
1892 // Track base/offset pairs when converted to a plain integer provided the
1893 // integer is large enough to represent the pointer.
1894 unsigned IntegerSize = I.getType()->getScalarSizeInBits();
1895 unsigned AS = I.getOperand(i_nocapture: 0)->getType()->getPointerAddressSpace();
1896 if (IntegerSize == DL.getPointerSizeInBits(AS)) {
1897 std::pair<Value *, APInt> BaseAndOffset =
1898 ConstantOffsetPtrs.lookup(Val: I.getOperand(i_nocapture: 0));
1899 if (BaseAndOffset.first)
1900 ConstantOffsetPtrs[&I] = std::move(BaseAndOffset);
1901 }
1902
1903 // This is really weird. Technically, ptrtoint will disable SROA. However,
1904 // unless that ptrtoint is *used* somewhere in the live basic blocks after
1905 // inlining, it will be nuked, and SROA should proceed. All of the uses which
1906 // would block SROA would also block SROA if applied directly to a pointer,
1907 // and so we can just add the integer in here. The only places where SROA is
1908 // preserved either cannot fire on an integer, or won't in-and-of themselves
1909 // disable SROA (ext) w/o some later use that we would see and disable.
1910 if (auto *SROAArg = getSROAArgForValueOrNull(V: I.getOperand(i_nocapture: 0)))
1911 SROAArgValues[&I] = SROAArg;
1912
1913 return TTI.getInstructionCost(U: &I, CostKind: TargetTransformInfo::TCK_SizeAndLatency) ==
1914 TargetTransformInfo::TCC_Free;
1915}
1916
1917bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) {
1918 // Propagate constants through ptrtoint.
1919 if (simplifyInstruction(I))
1920 return true;
1921
1922 // Track base/offset pairs when round-tripped through a pointer without
1923 // modifications provided the integer is not too large.
1924 Value *Op = I.getOperand(i_nocapture: 0);
1925 unsigned IntegerSize = Op->getType()->getScalarSizeInBits();
1926 if (IntegerSize <= DL.getPointerTypeSizeInBits(I.getType())) {
1927 std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Val: Op);
1928 if (BaseAndOffset.first)
1929 ConstantOffsetPtrs[&I] = std::move(BaseAndOffset);
1930 }
1931
1932 // "Propagate" SROA here in the same manner as we do for ptrtoint above.
1933 if (auto *SROAArg = getSROAArgForValueOrNull(V: Op))
1934 SROAArgValues[&I] = SROAArg;
1935
1936 return TTI.getInstructionCost(U: &I, CostKind: TargetTransformInfo::TCK_SizeAndLatency) ==
1937 TargetTransformInfo::TCC_Free;
1938}
1939
1940bool CallAnalyzer::visitCastInst(CastInst &I) {
1941 // Propagate constants through casts.
1942 if (simplifyInstruction(I))
1943 return true;
1944
1945 // Disable SROA in the face of arbitrary casts we don't explicitly list
1946 // elsewhere.
1947 disableSROA(V: I.getOperand(i_nocapture: 0));
1948
1949 // If this is a floating-point cast, and the target says this operation
1950 // is expensive, this may eventually become a library call. Treat the cost
1951 // as such.
1952 switch (I.getOpcode()) {
1953 case Instruction::FPTrunc:
1954 case Instruction::FPExt:
1955 case Instruction::UIToFP:
1956 case Instruction::SIToFP:
1957 case Instruction::FPToUI:
1958 case Instruction::FPToSI:
1959 if (TTI.getFPOpCost(Ty: I.getType()) == TargetTransformInfo::TCC_Expensive)
1960 onCallPenalty();
1961 break;
1962 default:
1963 break;
1964 }
1965
1966 return TTI.getInstructionCost(U: &I, CostKind: TargetTransformInfo::TCK_SizeAndLatency) ==
1967 TargetTransformInfo::TCC_Free;
1968}
1969
1970bool CallAnalyzer::paramHasAttr(Argument *A, Attribute::AttrKind Attr) {
1971 return CandidateCall.paramHasAttr(ArgNo: A->getArgNo(), Kind: Attr);
1972}
1973
1974bool CallAnalyzer::isKnownNonNullInCallee(Value *V) {
1975 // Does the *call site* have the NonNull attribute set on an argument? We
1976 // use the attribute on the call site to memoize any analysis done in the
1977 // caller. This will also trip if the callee function has a non-null
1978 // parameter attribute, but that's a less interesting case because hopefully
1979 // the callee would already have been simplified based on that.
1980 if (Argument *A = dyn_cast<Argument>(Val: V))
1981 if (paramHasAttr(A, Attr: Attribute::NonNull))
1982 return true;
1983
1984 // Is this an alloca in the caller? This is distinct from the attribute case
1985 // above because attributes aren't updated within the inliner itself and we
1986 // always want to catch the alloca derived case.
1987 if (isAllocaDerivedArg(V))
1988 // We can actually predict the result of comparisons between an
1989 // alloca-derived value and null. Note that this fires regardless of
1990 // SROA firing.
1991 return true;
1992
1993 return false;
1994}
1995
1996bool CallAnalyzer::allowSizeGrowth(CallBase &Call) {
1997 // If the normal destination of the invoke or the parent block of the call
1998 // site is unreachable-terminated, there is little point in inlining this
1999 // unless there is literally zero cost.
2000 // FIXME: Note that it is possible that an unreachable-terminated block has a
2001 // hot entry. For example, in below scenario inlining hot_call_X() may be
2002 // beneficial :
2003 // main() {
2004 // hot_call_1();
2005 // ...
2006 // hot_call_N()
2007 // exit(0);
2008 // }
2009 // For now, we are not handling this corner case here as it is rare in real
2010 // code. In future, we should elaborate this based on BPI and BFI in more
2011 // general threshold adjusting heuristics in updateThreshold().
2012 if (InvokeInst *II = dyn_cast<InvokeInst>(Val: &Call)) {
2013 if (isa<UnreachableInst>(Val: II->getNormalDest()->getTerminator()))
2014 return false;
2015 } else if (isa<UnreachableInst>(Val: Call.getParent()->getTerminator()))
2016 return false;
2017
2018 return true;
2019}
2020
2021bool InlineCostCallAnalyzer::isColdCallSite(CallBase &Call,
2022 BlockFrequencyInfo *CallerBFI) {
2023 // If global profile summary is available, then callsite's coldness is
2024 // determined based on that.
2025 if (PSI && PSI->hasProfileSummary())
2026 return PSI->isColdCallSite(CB: Call, BFI: CallerBFI);
2027
2028 // Otherwise we need BFI to be available.
2029 if (!CallerBFI)
2030 return false;
2031
2032 // Determine if the callsite is cold relative to caller's entry. We could
2033 // potentially cache the computation of scaled entry frequency, but the added
2034 // complexity is not worth it unless this scaling shows up high in the
2035 // profiles.
2036 const BranchProbability ColdProb(ColdCallSiteRelFreq, 100);
2037 auto CallSiteBB = Call.getParent();
2038 auto CallSiteFreq = CallerBFI->getBlockFreq(BB: CallSiteBB);
2039 auto CallerEntryFreq =
2040 CallerBFI->getBlockFreq(BB: &(Call.getCaller()->getEntryBlock()));
2041 return CallSiteFreq < CallerEntryFreq * ColdProb;
2042}
2043
2044std::optional<int>
2045InlineCostCallAnalyzer::getHotCallSiteThreshold(CallBase &Call,
2046 BlockFrequencyInfo *CallerBFI) {
2047
2048 // If global profile summary is available, then callsite's hotness is
2049 // determined based on that.
2050 if (PSI && PSI->hasProfileSummary() && PSI->isHotCallSite(CB: Call, BFI: CallerBFI))
2051 return Params.HotCallSiteThreshold;
2052
2053 // Otherwise we need BFI to be available and to have a locally hot callsite
2054 // threshold.
2055 if (!CallerBFI || !Params.LocallyHotCallSiteThreshold)
2056 return std::nullopt;
2057
2058 // Determine if the callsite is hot relative to caller's entry. We could
2059 // potentially cache the computation of scaled entry frequency, but the added
2060 // complexity is not worth it unless this scaling shows up high in the
2061 // profiles.
2062 const BasicBlock *CallSiteBB = Call.getParent();
2063 BlockFrequency CallSiteFreq = CallerBFI->getBlockFreq(BB: CallSiteBB);
2064 BlockFrequency CallerEntryFreq = CallerBFI->getEntryFreq();
2065 std::optional<BlockFrequency> Limit = CallerEntryFreq.mul(Factor: HotCallSiteRelFreq);
2066 if (Limit && CallSiteFreq >= *Limit)
2067 return Params.LocallyHotCallSiteThreshold;
2068
2069 // Otherwise treat it normally.
2070 return std::nullopt;
2071}
2072
2073void InlineCostCallAnalyzer::updateThreshold(CallBase &Call, Function &Callee) {
2074 // If no size growth is allowed for this inlining, set Threshold to 0.
2075 if (!allowSizeGrowth(Call)) {
2076 Threshold = 0;
2077 return;
2078 }
2079
2080 Function *Caller = Call.getCaller();
2081
2082 // return min(A, B) if B is valid.
2083 auto MinIfValid = [](int A, std::optional<int> B) {
2084 return B ? std::min(a: A, b: *B) : A;
2085 };
2086
2087 // return max(A, B) if B is valid.
2088 auto MaxIfValid = [](int A, std::optional<int> B) {
2089 return B ? std::max(a: A, b: *B) : A;
2090 };
2091
2092 // Various bonus percentages. These are multiplied by Threshold to get the
2093 // bonus values.
2094 // SingleBBBonus: This bonus is applied if the callee has a single reachable
2095 // basic block at the given callsite context. This is speculatively applied
2096 // and withdrawn if more than one basic block is seen.
2097 //
2098 // LstCallToStaticBonus: This large bonus is applied to ensure the inlining
2099 // of the last call to a static function as inlining such functions is
2100 // guaranteed to reduce code size.
2101 //
2102 // These bonus percentages may be set to 0 based on properties of the caller
2103 // and the callsite.
2104 int SingleBBBonusPercent = 50;
2105 int VectorBonusPercent = TTI.getInlinerVectorBonusPercent();
2106 int LastCallToStaticBonus = TTI.getInliningLastCallToStaticBonus();
2107
2108 // Lambda to set all the above bonus and bonus percentages to 0.
2109 auto DisallowAllBonuses = [&]() {
2110 SingleBBBonusPercent = 0;
2111 VectorBonusPercent = 0;
2112 LastCallToStaticBonus = 0;
2113 };
2114
2115 // Use the OptMinSizeThreshold or OptSizeThreshold knob if they are available
2116 // and reduce the threshold if the caller has the necessary attribute.
2117 if (Caller->hasMinSize()) {
2118 Threshold = MinIfValid(Threshold, Params.OptMinSizeThreshold);
2119 // For minsize, we want to disable the single BB bonus and the vector
2120 // bonuses, but not the last-call-to-static bonus. Inlining the last call to
2121 // a static function will, at the minimum, eliminate the parameter setup and
2122 // call/return instructions.
2123 SingleBBBonusPercent = 0;
2124 VectorBonusPercent = 0;
2125 } else if (Caller->hasOptSize())
2126 Threshold = MinIfValid(Threshold, Params.OptSizeThreshold);
2127
2128 // Adjust the threshold based on inlinehint attribute and profile based
2129 // hotness information if the caller does not have MinSize attribute.
2130 if (!Caller->hasMinSize()) {
2131 std::optional<int> HintThreshold = Caller->hasOptSize()
2132 ? Params.OptSizeHintThreshold
2133 : Params.HintThreshold;
2134 if (Callee.hasFnAttribute(Kind: Attribute::InlineHint))
2135 Threshold = MaxIfValid(Threshold, HintThreshold);
2136
2137 // FIXME: After switching to the new passmanager, simplify the logic below
2138 // by checking only the callsite hotness/coldness as we will reliably
2139 // have local profile information.
2140 //
2141 // Callsite hotness and coldness can be determined if sample profile is
2142 // used (which adds hotness metadata to calls) or if caller's
2143 // BlockFrequencyInfo is available.
2144 BlockFrequencyInfo *CallerBFI = GetBFI ? &(GetBFI(*Caller)) : nullptr;
2145 auto HotCallSiteThreshold = getHotCallSiteThreshold(Call, CallerBFI);
2146 if (!Caller->hasOptSize() && HotCallSiteThreshold) {
2147 LLVM_DEBUG(dbgs() << "Hot callsite.\n");
2148 // FIXME: This should update the threshold only if it exceeds the
2149 // current threshold, but AutoFDO + ThinLTO currently relies on this
2150 // behavior to prevent inlining of hot callsites during ThinLTO
2151 // compile phase.
2152 Threshold = *HotCallSiteThreshold;
2153 } else if (isCallableCC(CC: Caller->getCallingConv()) &&
2154 isColdCallSite(Call, CallerBFI)) {
2155 // In a function that is a hardware entry point rather than something
2156 // callable, e.g. a GPU kernel, register allocation is whole-function and
2157 // occupancy is set by the worst case over it. A call left out of line
2158 // there costs the hot path too, however cold the call itself is, so the
2159 // reduced threshold does not apply.
2160 LLVM_DEBUG(dbgs() << "Cold callsite.\n");
2161 // Do not apply bonuses for a cold callsite including the
2162 // LastCallToStatic bonus. While this bonus might result in code size
2163 // reduction, it can cause the size of a non-cold caller to increase
2164 // preventing it from being inlined.
2165 DisallowAllBonuses();
2166 Threshold = MinIfValid(Threshold, Params.ColdCallSiteThreshold);
2167 } else if (PSI) {
2168 // Use callee's global profile information only if we have no way of
2169 // determining this via callsite information.
2170 if (PSI->isFunctionEntryHot(F: &Callee)) {
2171 LLVM_DEBUG(dbgs() << "Hot callee.\n");
2172 // If callsite hotness can not be determined, we may still know
2173 // that the callee is hot and treat it as a weaker hint for threshold
2174 // increase.
2175 Threshold = MaxIfValid(Threshold, HintThreshold);
2176 } else if (PSI->isFunctionEntryCold(F: &Callee)) {
2177 LLVM_DEBUG(dbgs() << "Cold callee.\n");
2178 // Do not apply bonuses for a cold callee including the
2179 // LastCallToStatic bonus. While this bonus might result in code size
2180 // reduction, it can cause the size of a non-cold caller to increase
2181 // preventing it from being inlined.
2182 DisallowAllBonuses();
2183 Threshold = MinIfValid(Threshold, Params.ColdThreshold);
2184 }
2185 }
2186 }
2187
2188 Threshold += TTI.adjustInliningThreshold(CB: &Call);
2189
2190 // Finally, take the target-specific inlining threshold multiplier into
2191 // account.
2192 Threshold *= TTI.getInliningThresholdMultiplier();
2193
2194 SingleBBBonus = Threshold * SingleBBBonusPercent / 100;
2195 VectorBonus = Threshold * VectorBonusPercent / 100;
2196
2197 // If there is only one call of the function, and it has internal linkage,
2198 // the cost of inlining it drops dramatically. It may seem odd to update
2199 // Cost in updateThreshold, but the bonus depends on the logic in this method.
2200 if (isSoleCallToLocalFunction(CB: Call, Callee: F)) {
2201 addCost(Inc: -LastCallToStaticBonus);
2202 StaticBonusApplied = LastCallToStaticBonus;
2203 }
2204}
2205
2206bool CallAnalyzer::visitCmpInst(CmpInst &I) {
2207 Value *LHS = I.getOperand(i_nocapture: 0), *RHS = I.getOperand(i_nocapture: 1);
2208 // First try to handle simplified comparisons.
2209 if (simplifyInstruction(I))
2210 return true;
2211
2212 // Try to handle comparison that can be simplified using ValueTracking.
2213 if (simplifyCmpInstForRecCall(Cmp&: I))
2214 return true;
2215
2216 if (I.getOpcode() == Instruction::FCmp)
2217 return false;
2218
2219 // Otherwise look for a comparison between constant offset pointers with
2220 // a common base.
2221 Value *LHSBase, *RHSBase;
2222 APInt LHSOffset, RHSOffset;
2223 std::tie(args&: LHSBase, args&: LHSOffset) = ConstantOffsetPtrs.lookup(Val: LHS);
2224 if (LHSBase) {
2225 std::tie(args&: RHSBase, args&: RHSOffset) = ConstantOffsetPtrs.lookup(Val: RHS);
2226 if (RHSBase && LHSBase == RHSBase) {
2227 // We have common bases, fold the icmp to a constant based on the
2228 // offsets.
2229 SimplifiedValues[&I] = ConstantInt::getBool(
2230 Ty: I.getType(),
2231 V: ICmpInst::compare(LHS: LHSOffset, RHS: RHSOffset, Pred: I.getPredicate()));
2232 ++NumConstantPtrCmps;
2233 return true;
2234 }
2235 }
2236
2237 auto isImplicitNullCheckCmp = [](const CmpInst &I) {
2238 for (auto *User : I.users())
2239 if (auto *Instr = dyn_cast<Instruction>(Val: User))
2240 if (!Instr->getMetadata(KindID: LLVMContext::MD_make_implicit))
2241 return false;
2242 return true;
2243 };
2244
2245 // If the comparison is an equality comparison with null, we can simplify it
2246 // if we know the value (argument) can't be null
2247 if (I.isEquality() && isa<ConstantPointerNull>(Val: I.getOperand(i_nocapture: 1))) {
2248 if (isKnownNonNullInCallee(V: I.getOperand(i_nocapture: 0))) {
2249 bool IsNotEqual = I.getPredicate() == CmpInst::ICMP_NE;
2250 SimplifiedValues[&I] = IsNotEqual ? ConstantInt::getTrue(Ty: I.getType())
2251 : ConstantInt::getFalse(Ty: I.getType());
2252 return true;
2253 }
2254 // Implicit null checks act as unconditional branches and their comparisons
2255 // should be treated as simplified and free of cost.
2256 if (isImplicitNullCheckCmp(I))
2257 return true;
2258 }
2259 return handleSROA(V: I.getOperand(i_nocapture: 0), DoNotDisable: isa<ConstantPointerNull>(Val: I.getOperand(i_nocapture: 1)));
2260}
2261
2262bool CallAnalyzer::visitSub(BinaryOperator &I) {
2263 // Try to handle a special case: we can fold computing the difference of two
2264 // constant-related pointers.
2265 Value *LHS = I.getOperand(i_nocapture: 0), *RHS = I.getOperand(i_nocapture: 1);
2266 Value *LHSBase, *RHSBase;
2267 APInt LHSOffset, RHSOffset;
2268 std::tie(args&: LHSBase, args&: LHSOffset) = ConstantOffsetPtrs.lookup(Val: LHS);
2269 if (LHSBase) {
2270 std::tie(args&: RHSBase, args&: RHSOffset) = ConstantOffsetPtrs.lookup(Val: RHS);
2271 if (RHSBase && LHSBase == RHSBase) {
2272 // We have common bases, fold the subtract to a constant based on the
2273 // offsets.
2274 Constant *CLHS = ConstantInt::get(Context&: LHS->getContext(), V: LHSOffset);
2275 Constant *CRHS = ConstantInt::get(Context&: RHS->getContext(), V: RHSOffset);
2276 if (Constant *C = ConstantExpr::getSub(C1: CLHS, C2: CRHS)) {
2277 SimplifiedValues[&I] = C;
2278 ++NumConstantPtrDiffs;
2279 return true;
2280 }
2281 }
2282 }
2283
2284 // Otherwise, fall back to the generic logic for simplifying and handling
2285 // instructions.
2286 return Base::visitSub(I);
2287}
2288
2289bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) {
2290 Value *LHS = I.getOperand(i_nocapture: 0), *RHS = I.getOperand(i_nocapture: 1);
2291 Constant *CLHS = getDirectOrSimplifiedValue<Constant>(V: LHS);
2292 Constant *CRHS = getDirectOrSimplifiedValue<Constant>(V: RHS);
2293
2294 Value *SimpleV = nullptr;
2295 if (auto FI = dyn_cast<FPMathOperator>(Val: &I))
2296 SimpleV = simplifyBinOp(Opcode: I.getOpcode(), LHS: CLHS ? CLHS : LHS, RHS: CRHS ? CRHS : RHS,
2297 FMF: FI->getFastMathFlags(), Q: DL);
2298 else
2299 SimpleV =
2300 simplifyBinOp(Opcode: I.getOpcode(), LHS: CLHS ? CLHS : LHS, RHS: CRHS ? CRHS : RHS, Q: DL);
2301
2302 if (Constant *C = dyn_cast_or_null<Constant>(Val: SimpleV))
2303 SimplifiedValues[&I] = C;
2304
2305 if (SimpleV)
2306 return true;
2307
2308 // Disable any SROA on arguments to arbitrary, unsimplified binary operators.
2309 disableSROA(V: LHS);
2310 disableSROA(V: RHS);
2311
2312 // If the instruction is floating point, and the target says this operation
2313 // is expensive, this may eventually become a library call. Treat the cost
2314 // as such. Unless it's fneg which can be implemented with an xor.
2315 using namespace llvm::PatternMatch;
2316 if (I.getType()->isFloatingPointTy() &&
2317 TTI.getFPOpCost(Ty: I.getType()) == TargetTransformInfo::TCC_Expensive &&
2318 !match(V: &I, P: m_FNeg(X: m_Value())))
2319 onCallPenalty();
2320
2321 return false;
2322}
2323
2324bool CallAnalyzer::visitFNeg(UnaryOperator &I) {
2325 Value *Op = I.getOperand(i_nocapture: 0);
2326 Constant *COp = getDirectOrSimplifiedValue<Constant>(V: Op);
2327
2328 Value *SimpleV = simplifyFNegInst(
2329 Op: COp ? COp : Op, FMF: cast<FPMathOperator>(Val&: I).getFastMathFlags(), Q: DL);
2330
2331 if (Constant *C = dyn_cast_or_null<Constant>(Val: SimpleV))
2332 SimplifiedValues[&I] = C;
2333
2334 if (SimpleV)
2335 return true;
2336
2337 // Disable any SROA on arguments to arbitrary, unsimplified fneg.
2338 disableSROA(V: Op);
2339
2340 return false;
2341}
2342
2343bool CallAnalyzer::visitLoad(LoadInst &I) {
2344 if (handleSROA(V: I.getPointerOperand(), DoNotDisable: I.isSimple()))
2345 return true;
2346
2347 // If the data is already loaded from this address and hasn't been clobbered
2348 // by any stores or calls, this load is likely to be redundant and can be
2349 // eliminated.
2350 if (EnableLoadElimination &&
2351 !LoadAddrSet.insert(Ptr: I.getPointerOperand()).second && I.isUnordered()) {
2352 onLoadEliminationOpportunity();
2353 return true;
2354 }
2355
2356 onMemAccess();
2357 return false;
2358}
2359
2360bool CallAnalyzer::visitStore(StoreInst &I) {
2361 if (handleSROA(V: I.getPointerOperand(), DoNotDisable: I.isSimple()))
2362 return true;
2363
2364 // The store can potentially clobber loads and prevent repeated loads from
2365 // being eliminated.
2366 // FIXME:
2367 // 1. We can probably keep an initial set of eliminatable loads substracted
2368 // from the cost even when we finally see a store. We just need to disable
2369 // *further* accumulation of elimination savings.
2370 // 2. We should probably at some point thread MemorySSA for the callee into
2371 // this and then use that to actually compute *really* precise savings.
2372 disableLoadElimination();
2373
2374 onMemAccess();
2375 return false;
2376}
2377
2378bool CallAnalyzer::visitExtractValue(ExtractValueInst &I) {
2379 Value *Op = I.getAggregateOperand();
2380
2381 // Special handling, because we want to simplify extractvalue with a
2382 // potential insertvalue from the caller.
2383 if (Value *SimpleOp = getSimplifiedValueUnchecked(V: Op)) {
2384 SimplifyQuery SQ(DL);
2385 Value *SimpleV = simplifyExtractValueInst(Agg: SimpleOp, Idxs: I.getIndices(), Q: SQ);
2386 if (SimpleV) {
2387 SimplifiedValues[&I] = SimpleV;
2388 return true;
2389 }
2390 }
2391
2392 // SROA can't look through these, but they may be free.
2393 return Base::visitExtractValue(I);
2394}
2395
2396bool CallAnalyzer::visitInsertValue(InsertValueInst &I) {
2397 // Constant folding for insert value is trivial.
2398 if (simplifyInstruction(I))
2399 return true;
2400
2401 // SROA can't look through these, but they may be free.
2402 return Base::visitInsertValue(I);
2403}
2404
2405/// Try to simplify a call site.
2406///
2407/// Takes a concrete function and callsite and tries to actually simplify it by
2408/// analyzing the arguments and call itself with instsimplify. Returns true if
2409/// it has simplified the callsite to some other entity (a constant), making it
2410/// free.
2411bool CallAnalyzer::simplifyCallSite(Function *F, CallBase &Call) {
2412 // FIXME: Using the instsimplify logic directly for this is inefficient
2413 // because we have to continually rebuild the argument list even when no
2414 // simplifications can be performed. Until that is fixed with remapping
2415 // inside of instsimplify, directly constant fold calls here.
2416 if (!canConstantFoldCallTo(Call: &Call, F))
2417 return false;
2418
2419 // Try to re-map the arguments to constants.
2420 SmallVector<Constant *, 4> ConstantArgs;
2421 ConstantArgs.reserve(N: Call.arg_size());
2422 for (Value *I : Call.args()) {
2423 Constant *C = getDirectOrSimplifiedValue<Constant>(V: I);
2424 if (!C)
2425 return false; // This argument doesn't map to a constant.
2426
2427 ConstantArgs.push_back(Elt: C);
2428 }
2429 if (Constant *C = ConstantFoldCall(Call: &Call, F, Operands: ConstantArgs)) {
2430 SimplifiedValues[&Call] = C;
2431 return true;
2432 }
2433
2434 return false;
2435}
2436
2437bool CallAnalyzer::isLoweredToCall(Function *F, CallBase &Call) {
2438 const TargetLibraryInfo *TLI = GetTLI ? &GetTLI(*F) : nullptr;
2439 if (!TLI)
2440 return TTI.isLoweredToCall(F);
2441
2442 LibFunc LF = TLI->getLibFunc(FDecl: *F);
2443 if (!TLI->has(F: LF))
2444 return TTI.isLoweredToCall(F);
2445
2446 switch (LF) {
2447 case LibFunc_memcpy_chk:
2448 case LibFunc_memmove_chk:
2449 case LibFunc_mempcpy_chk:
2450 case LibFunc_memset_chk: {
2451 // Calls to __memcpy_chk whose length is known to fit within the object
2452 // size will eventually be replaced by inline stores. Therefore, these
2453 // should not incur a call penalty. This is only really relevant on
2454 // platforms whose headers redirect memcpy to __memcpy_chk (e.g. Darwin), as
2455 // other platforms use memcpy intrinsics, which are already exempt from the
2456 // call penalty.
2457 auto *LenOp = getDirectOrSimplifiedValue<ConstantInt>(V: Call.getOperand(i_nocapture: 2));
2458 auto *ObjSizeOp =
2459 getDirectOrSimplifiedValue<ConstantInt>(V: Call.getOperand(i_nocapture: 3));
2460 if (LenOp && ObjSizeOp &&
2461 LenOp->getLimitedValue() <= ObjSizeOp->getLimitedValue()) {
2462 return false;
2463 }
2464 break;
2465 }
2466 default:
2467 break;
2468 }
2469
2470 return TTI.isLoweredToCall(F);
2471}
2472
2473bool CallAnalyzer::visitCallBase(CallBase &Call) {
2474 if (!onCallBaseVisitStart(Call))
2475 return true;
2476
2477 if (Call.hasFnAttr(Kind: Attribute::ReturnsTwice) &&
2478 !F.hasFnAttribute(Kind: Attribute::ReturnsTwice)) {
2479 // This aborts the entire analysis.
2480 ExposesReturnsTwice = true;
2481 return false;
2482 }
2483 if (isa<CallInst>(Val: Call) && cast<CallInst>(Val&: Call).cannotDuplicate())
2484 ContainsNoDuplicateCall = true;
2485
2486 if (InlineAsm *InlineAsmOp = dyn_cast<InlineAsm>(Val: Call.getCalledOperand()))
2487 onInlineAsm(Arg: *InlineAsmOp);
2488
2489 Function *F = Call.getCalledFunction();
2490 bool IsIndirectCall = !F;
2491 if (IsIndirectCall) {
2492 // Check if this happens to be an indirect function call to a known function
2493 // in this inline context. If not, we've done all we can.
2494 Value *Callee = Call.getCalledOperand();
2495 F = getSimplifiedValue<Function>(V: Callee);
2496 if (!F || F->getFunctionType() != Call.getFunctionType()) {
2497 onCallArgumentSetup(Call);
2498
2499 if (!Call.onlyReadsMemory())
2500 disableLoadElimination();
2501 return Base::visitCallBase(I&: Call);
2502 }
2503 }
2504
2505 assert(F && "Expected a call to a known function");
2506
2507 // When we have a concrete function, first try to simplify it directly.
2508 if (simplifyCallSite(F, Call))
2509 return true;
2510
2511 // Next check if it is an intrinsic we know about.
2512 // FIXME: Lift this into part of the InstVisitor.
2513 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: &Call)) {
2514 switch (II->getIntrinsicID()) {
2515 default:
2516 if (!Call.onlyReadsMemory() && !isAssumeLikeIntrinsic(I: II))
2517 disableLoadElimination();
2518 return Base::visitCallBase(I&: Call);
2519
2520 case Intrinsic::load_relative:
2521 onLoadRelativeIntrinsic();
2522 return false;
2523
2524 case Intrinsic::memset:
2525 case Intrinsic::memcpy:
2526 case Intrinsic::memmove:
2527 disableLoadElimination();
2528 // SROA can usually chew through these intrinsics, but they aren't free.
2529 return false;
2530 case Intrinsic::icall_branch_funnel:
2531 case Intrinsic::localescape:
2532 HasUninlineableIntrinsic = true;
2533 return false;
2534 case Intrinsic::vastart:
2535 InitsVargArgs = true;
2536 return false;
2537 case Intrinsic::launder_invariant_group:
2538 case Intrinsic::strip_invariant_group:
2539 if (auto *SROAArg = getSROAArgForValueOrNull(V: II->getOperand(i_nocapture: 0)))
2540 SROAArgValues[II] = SROAArg;
2541 return true;
2542 case Intrinsic::is_constant:
2543 return simplifyIntrinsicCallIsConstant(CB&: Call);
2544 case Intrinsic::objectsize:
2545 return simplifyIntrinsicCallObjectSize(CB&: Call);
2546 }
2547 }
2548
2549 if (F == Call.getFunction()) {
2550 // This flag will fully abort the analysis, so don't bother with anything
2551 // else.
2552 IsRecursiveCall = true;
2553 if (!AllowRecursiveCall)
2554 return false;
2555 }
2556
2557 if (isLoweredToCall(F, Call)) {
2558 onLoweredCall(F, Call, IsIndirectCall);
2559 }
2560
2561 if (!(Call.onlyReadsMemory() || (IsIndirectCall && F->onlyReadsMemory())))
2562 disableLoadElimination();
2563 return Base::visitCallBase(I&: Call);
2564}
2565
2566bool CallAnalyzer::visitReturnInst(ReturnInst &RI) {
2567 // At least one return instruction will be free after inlining.
2568 bool Free = !HasReturn;
2569 HasReturn = true;
2570 return Free;
2571}
2572
2573bool CallAnalyzer::visitUncondBrInst(UncondBrInst &BI) {
2574 // We model unconditional branches as essentially free -- they really
2575 // shouldn't exist at all, but handling them makes the behavior of the
2576 // inliner more regular and predictable.
2577 return true;
2578}
2579
2580bool CallAnalyzer::visitCondBrInst(CondBrInst &BI) {
2581 // Conditional branches which will fold away are free.
2582 return getDirectOrSimplifiedValue<ConstantInt>(V: BI.getCondition()) ||
2583 BI.getMetadata(KindID: LLVMContext::MD_make_implicit);
2584}
2585
2586bool CallAnalyzer::visitSelectInst(SelectInst &SI) {
2587 bool CheckSROA = SI.getType()->isPointerTy();
2588 Value *TrueVal = SI.getTrueValue();
2589 Value *FalseVal = SI.getFalseValue();
2590
2591 Constant *TrueC = getDirectOrSimplifiedValue<Constant>(V: TrueVal);
2592 Constant *FalseC = getDirectOrSimplifiedValue<Constant>(V: FalseVal);
2593 Constant *CondC = getSimplifiedValue<Constant>(V: SI.getCondition());
2594
2595 if (!CondC) {
2596 // Select C, X, X => X
2597 if (TrueC == FalseC && TrueC) {
2598 SimplifiedValues[&SI] = TrueC;
2599 return true;
2600 }
2601
2602 if (!CheckSROA)
2603 return Base::visitSelectInst(I&: SI);
2604
2605 std::pair<Value *, APInt> TrueBaseAndOffset =
2606 ConstantOffsetPtrs.lookup(Val: TrueVal);
2607 std::pair<Value *, APInt> FalseBaseAndOffset =
2608 ConstantOffsetPtrs.lookup(Val: FalseVal);
2609 if (TrueBaseAndOffset == FalseBaseAndOffset && TrueBaseAndOffset.first) {
2610 ConstantOffsetPtrs[&SI] = std::move(TrueBaseAndOffset);
2611
2612 if (auto *SROAArg = getSROAArgForValueOrNull(V: TrueVal))
2613 SROAArgValues[&SI] = SROAArg;
2614 return true;
2615 }
2616
2617 return Base::visitSelectInst(I&: SI);
2618 }
2619
2620 // Select condition is a constant.
2621 Value *SelectedV = CondC->isAllOnesValue() ? TrueVal
2622 : (CondC->isNullValue()) ? FalseVal
2623 : nullptr;
2624 if (!SelectedV) {
2625 // Condition is a vector constant that is not all 1s or all 0s. If all
2626 // operands are constants, ConstantFoldSelectInstruction() can handle the
2627 // cases such as select vectors.
2628 if (TrueC && FalseC) {
2629 if (auto *C = ConstantFoldSelectInstruction(Cond: CondC, V1: TrueC, V2: FalseC)) {
2630 SimplifiedValues[&SI] = C;
2631 return true;
2632 }
2633 }
2634 return Base::visitSelectInst(I&: SI);
2635 }
2636
2637 // Condition is either all 1s or all 0s. SI can be simplified.
2638 if (Constant *SelectedC = dyn_cast<Constant>(Val: SelectedV)) {
2639 SimplifiedValues[&SI] = SelectedC;
2640 return true;
2641 }
2642
2643 if (!CheckSROA)
2644 return true;
2645
2646 std::pair<Value *, APInt> BaseAndOffset =
2647 ConstantOffsetPtrs.lookup(Val: SelectedV);
2648 if (BaseAndOffset.first) {
2649 ConstantOffsetPtrs[&SI] = std::move(BaseAndOffset);
2650
2651 if (auto *SROAArg = getSROAArgForValueOrNull(V: SelectedV))
2652 SROAArgValues[&SI] = SROAArg;
2653 }
2654
2655 return true;
2656}
2657
2658bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
2659 // We model unconditional switches as free, see the comments on handling
2660 // branches.
2661 if (getDirectOrSimplifiedValue<ConstantInt>(V: SI.getCondition()))
2662 return true;
2663
2664 // Assume the most general case where the switch is lowered into
2665 // either a jump table, bit test, or a balanced binary tree consisting of
2666 // case clusters without merging adjacent clusters with the same
2667 // destination. We do not consider the switches that are lowered with a mix
2668 // of jump table/bit test/binary search tree. The cost of the switch is
2669 // proportional to the size of the tree or the size of jump table range.
2670 //
2671 // NB: We convert large switches which are just used to initialize large phi
2672 // nodes to lookup tables instead in simplifycfg, so this shouldn't prevent
2673 // inlining those. It will prevent inlining in cases where the optimization
2674 // does not (yet) fire.
2675
2676 unsigned JumpTableSize = 0;
2677 BlockFrequencyInfo *BFI = GetBFI ? &(GetBFI(F)) : nullptr;
2678 unsigned NumCaseCluster =
2679 TTI.getEstimatedNumberOfCaseClusters(SI, JTSize&: JumpTableSize, PSI, BFI);
2680
2681 onFinalizeSwitch(JumpTableSize, NumCaseCluster, DefaultDestUnreachable: SI.defaultDestUnreachable());
2682 return false;
2683}
2684
2685bool CallAnalyzer::visitIndirectBrInst(IndirectBrInst &IBI) {
2686 // We never want to inline functions that contain an indirectbr. This is
2687 // incorrect because all the blockaddress's (in static global initializers
2688 // for example) would be referring to the original function, and this
2689 // indirect jump would jump from the inlined copy of the function into the
2690 // original function which is extremely undefined behavior.
2691 // FIXME: This logic isn't really right; we can safely inline functions with
2692 // indirectbr's as long as no other function or global references the
2693 // blockaddress of a block within the current function.
2694 HasIndirectBr = true;
2695 return false;
2696}
2697
2698bool CallAnalyzer::visitResumeInst(ResumeInst &RI) {
2699 // FIXME: It's not clear that a single instruction is an accurate model for
2700 // the inline cost of a resume instruction.
2701 return false;
2702}
2703
2704bool CallAnalyzer::visitCleanupReturnInst(CleanupReturnInst &CRI) {
2705 // FIXME: It's not clear that a single instruction is an accurate model for
2706 // the inline cost of a cleanupret instruction.
2707 return false;
2708}
2709
2710bool CallAnalyzer::visitCatchReturnInst(CatchReturnInst &CRI) {
2711 // FIXME: It's not clear that a single instruction is an accurate model for
2712 // the inline cost of a catchret instruction.
2713 return false;
2714}
2715
2716bool CallAnalyzer::visitUnreachableInst(UnreachableInst &I) {
2717 // FIXME: It might be reasonably to discount the cost of instructions leading
2718 // to unreachable as they have the lowest possible impact on both runtime and
2719 // code size.
2720 return true; // No actual code is needed for unreachable.
2721}
2722
2723bool CallAnalyzer::visitInstruction(Instruction &I) {
2724 // Some instructions are free. All of the free intrinsics can also be
2725 // handled by SROA, etc.
2726 if (TTI.getInstructionCost(U: &I, CostKind: TargetTransformInfo::TCK_SizeAndLatency) ==
2727 TargetTransformInfo::TCC_Free)
2728 return true;
2729
2730 // We found something we don't understand or can't handle. Mark any SROA-able
2731 // values in the operand list as no longer viable.
2732 for (const Use &Op : I.operands())
2733 disableSROA(V: Op);
2734
2735 return false;
2736}
2737
2738/// Analyze a basic block for its contribution to the inline cost.
2739///
2740/// This method walks the analyzer over every instruction in the given basic
2741/// block and accounts for their cost during inlining at this callsite. It
2742/// aborts early if the threshold has been exceeded or an impossible to inline
2743/// construct has been detected. It returns false if inlining is no longer
2744/// viable, and true if inlining remains viable.
2745InlineResult
2746CallAnalyzer::analyzeBlock(BasicBlock *BB,
2747 const SmallPtrSetImpl<const Value *> &EphValues) {
2748 for (Instruction &I : *BB) {
2749 // FIXME: Currently, the number of instructions in a function regardless of
2750 // our ability to simplify them during inline to constants or dead code,
2751 // are actually used by the vector bonus heuristic. As long as that's true,
2752 // we have to special case debug intrinsics here to prevent differences in
2753 // inlining due to debug symbols. Eventually, the number of unsimplified
2754 // instructions shouldn't factor into the cost computation, but until then,
2755 // hack around it here.
2756 // Similarly, skip pseudo-probes.
2757 if (I.isDebugOrPseudoInst())
2758 continue;
2759
2760 // Skip ephemeral values.
2761 if (EphValues.count(Ptr: &I))
2762 continue;
2763
2764 ++NumInstructions;
2765 if (isa<ExtractElementInst>(Val: I) || I.getType()->isVectorTy())
2766 ++NumVectorInstructions;
2767
2768 // If the instruction simplified to a constant, there is no cost to this
2769 // instruction. Visit the instructions using our InstVisitor to account for
2770 // all of the per-instruction logic. The visit tree returns true if we
2771 // consumed the instruction in any way, and false if the instruction's base
2772 // cost should count against inlining.
2773 onInstructionAnalysisStart(I: &I);
2774
2775 if (Base::visit(I: &I))
2776 ++NumInstructionsSimplified;
2777 else
2778 onMissedSimplification();
2779
2780 onInstructionAnalysisFinish(I: &I);
2781 using namespace ore;
2782 // If the visit this instruction detected an uninlinable pattern, abort.
2783 InlineResult IR = InlineResult::success();
2784 if (IsRecursiveCall && !AllowRecursiveCall)
2785 IR = InlineResult::failure(Reason: "recursive");
2786 else if (ExposesReturnsTwice)
2787 IR = InlineResult::failure(Reason: "exposes returns twice");
2788 else if (HasDynamicAlloca)
2789 IR = InlineResult::failure(Reason: "dynamic alloca");
2790 else if (HasIndirectBr)
2791 IR = InlineResult::failure(Reason: "indirect branch");
2792 else if (HasUninlineableIntrinsic)
2793 IR = InlineResult::failure(Reason: "uninlinable intrinsic");
2794 else if (InitsVargArgs)
2795 IR = InlineResult::failure(Reason: "varargs");
2796 if (!IR.isSuccess()) {
2797 if (ORE)
2798 ORE->emit(RemarkBuilder: [&]() {
2799 return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline",
2800 &CandidateCall)
2801 << NV("Callee", &F) << " has uninlinable pattern ("
2802 << NV("InlineResult", IR.getFailureReason())
2803 << ") and cost is not fully computed";
2804 });
2805 return IR;
2806 }
2807
2808 // If the caller is a recursive function then we don't want to inline
2809 // functions which allocate a lot of stack space because it would increase
2810 // the caller stack usage dramatically.
2811 if (IsCallerRecursive && AllocatedSize > RecurStackSizeThreshold) {
2812 auto IR =
2813 InlineResult::failure(Reason: "recursive and allocates too much stack space");
2814 if (ORE)
2815 ORE->emit(RemarkBuilder: [&]() {
2816 return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline",
2817 &CandidateCall)
2818 << NV("Callee", &F) << " is "
2819 << NV("InlineResult", IR.getFailureReason())
2820 << ". Cost is not fully computed";
2821 });
2822 return IR;
2823 }
2824
2825 if (shouldStop())
2826 return InlineResult::failure(
2827 Reason: "Call site analysis is not favorable to inlining.");
2828 }
2829
2830 return InlineResult::success();
2831}
2832
2833/// Compute the base pointer and cumulative constant offsets for V.
2834///
2835/// This strips all constant offsets off of V, leaving it the base pointer, and
2836/// accumulates the total constant offset applied in the returned constant. It
2837/// returns 0 if V is not a pointer, and returns the constant '0' if there are
2838/// no constant offsets applied.
2839ConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) {
2840 if (!V->getType()->isPointerTy())
2841 return nullptr;
2842
2843 unsigned AS = V->getType()->getPointerAddressSpace();
2844 unsigned IntPtrWidth = DL.getIndexSizeInBits(AS);
2845 APInt Offset = APInt::getZero(numBits: IntPtrWidth);
2846
2847 // Even though we don't look through PHI nodes, we could be called on an
2848 // instruction in an unreachable block, which may be on a cycle.
2849 SmallPtrSet<Value *, 4> Visited;
2850 Visited.insert(Ptr: V);
2851 do {
2852 if (GEPOperator *GEP = dyn_cast<GEPOperator>(Val: V)) {
2853 if (!GEP->isInBounds() || !accumulateGEPOffset(GEP&: *GEP, Offset))
2854 return nullptr;
2855 V = GEP->getPointerOperand();
2856 } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(Val: V)) {
2857 if (GA->isInterposable())
2858 break;
2859 V = GA->getAliasee();
2860 } else {
2861 break;
2862 }
2863 assert(V->getType()->isPointerTy() && "Unexpected operand type!");
2864 } while (Visited.insert(Ptr: V).second);
2865
2866 Type *IdxPtrTy = DL.getIndexType(PtrTy: V->getType());
2867 return cast<ConstantInt>(Val: ConstantInt::get(Ty: IdxPtrTy, V: Offset));
2868}
2869
2870/// Find dead blocks due to deleted CFG edges during inlining.
2871///
2872/// If we know the successor of the current block, \p CurrBB, has to be \p
2873/// NextBB, the other successors of \p CurrBB are dead if these successors have
2874/// no live incoming CFG edges. If one block is found to be dead, we can
2875/// continue growing the dead block list by checking the successors of the dead
2876/// blocks to see if all their incoming edges are dead or not.
2877void CallAnalyzer::findDeadBlocks(BasicBlock *CurrBB, BasicBlock *NextBB) {
2878 auto IsEdgeDead = [&](BasicBlock *Pred, BasicBlock *Succ) {
2879 // A CFG edge is dead if the predecessor is dead or the predecessor has a
2880 // known successor which is not the one under exam.
2881 if (DeadBlocks.count(Ptr: Pred))
2882 return true;
2883 BasicBlock *KnownSucc = KnownSuccessors[Pred];
2884 return KnownSucc && KnownSucc != Succ;
2885 };
2886
2887 auto IsNewlyDead = [&](BasicBlock *BB) {
2888 // If all the edges to a block are dead, the block is also dead.
2889 return (!DeadBlocks.count(Ptr: BB) &&
2890 llvm::all_of(Range: predecessors(BB),
2891 P: [&](BasicBlock *P) { return IsEdgeDead(P, BB); }));
2892 };
2893
2894 for (BasicBlock *Succ : successors(BB: CurrBB)) {
2895 if (Succ == NextBB || !IsNewlyDead(Succ))
2896 continue;
2897 SmallVector<BasicBlock *, 4> NewDead;
2898 NewDead.push_back(Elt: Succ);
2899 while (!NewDead.empty()) {
2900 BasicBlock *Dead = NewDead.pop_back_val();
2901 if (DeadBlocks.insert(Ptr: Dead).second)
2902 // Continue growing the dead block lists.
2903 for (BasicBlock *S : successors(BB: Dead))
2904 if (IsNewlyDead(S))
2905 NewDead.push_back(Elt: S);
2906 }
2907 }
2908}
2909
2910/// Analyze a call site for potential inlining.
2911///
2912/// Returns true if inlining this call is viable, and false if it is not
2913/// viable. It computes the cost and adjusts the threshold based on numerous
2914/// factors and heuristics. If this method returns false but the computed cost
2915/// is below the computed threshold, then inlining was forcibly disabled by
2916/// some artifact of the routine.
2917InlineResult CallAnalyzer::analyze() {
2918 ++NumCallsAnalyzed;
2919
2920 auto Result = onAnalysisStart();
2921 if (!Result.isSuccess())
2922 return Result;
2923
2924 if (F.empty())
2925 return InlineResult::success();
2926
2927 Function *Caller = CandidateCall.getFunction();
2928 // Check if the caller function is recursive itself.
2929 for (User *U : Caller->users()) {
2930 CallBase *Call = dyn_cast<CallBase>(Val: U);
2931 if (Call && Call->getFunction() == Caller) {
2932 IsCallerRecursive = true;
2933 break;
2934 }
2935 }
2936
2937 // Populate our simplified values by mapping from function arguments to call
2938 // arguments with known important simplifications.
2939 auto CAI = CandidateCall.arg_begin();
2940 for (Argument &FAI : F.args()) {
2941 assert(CAI != CandidateCall.arg_end());
2942 SimplifiedValues[&FAI] = *CAI;
2943 if (isa<Constant>(Val: *CAI))
2944 ++NumConstantArgs;
2945
2946 Value *PtrArg = *CAI;
2947 if (ConstantInt *C = stripAndComputeInBoundsConstantOffsets(V&: PtrArg)) {
2948 ConstantOffsetPtrs[&FAI] = std::make_pair(x&: PtrArg, y: C->getValue());
2949
2950 // We can SROA any pointer arguments derived from alloca instructions.
2951 if (auto *SROAArg = dyn_cast<AllocaInst>(Val: PtrArg)) {
2952 SROAArgValues[&FAI] = SROAArg;
2953 onInitializeSROAArg(Arg: SROAArg);
2954 EnabledSROAAllocas.insert(V: SROAArg);
2955 }
2956 }
2957 ++CAI;
2958 }
2959 NumConstantOffsetPtrArgs = ConstantOffsetPtrs.size();
2960 NumAllocaArgs = SROAArgValues.size();
2961
2962 // Collecting the ephemeral values of `F` can be expensive, so use the
2963 // ephemeral values cache if available.
2964 SmallPtrSet<const Value *, 32> EphValuesStorage;
2965 const SmallPtrSetImpl<const Value *> *EphValues = &EphValuesStorage;
2966 if (GetEphValuesCache)
2967 EphValues = &GetEphValuesCache(F).ephValues();
2968 else
2969 CodeMetrics::collectEphemeralValues(L: &F, AC: &GetAssumptionCache(F),
2970 EphValues&: EphValuesStorage);
2971
2972 // The worklist of live basic blocks in the callee *after* inlining. We avoid
2973 // adding basic blocks of the callee which can be proven to be dead for this
2974 // particular call site in order to get more accurate cost estimates. This
2975 // requires a somewhat heavyweight iteration pattern: we need to walk the
2976 // basic blocks in a breadth-first order as we insert live successors. To
2977 // accomplish this, prioritizing for small iterations because we exit after
2978 // crossing our threshold, we use a small-size optimized SetVector.
2979 typedef SmallSetVector<BasicBlock *, 16> BBSetVector;
2980 BBSetVector BBWorklist;
2981 BBWorklist.insert(X: &F.getEntryBlock());
2982
2983 // Note that we *must not* cache the size, this loop grows the worklist.
2984 for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
2985 if (shouldStop())
2986 break;
2987
2988 BasicBlock *BB = BBWorklist[Idx];
2989 if (BB->empty())
2990 continue;
2991
2992 onBlockStart(BB);
2993
2994 // Disallow inlining a blockaddress.
2995 // A blockaddress only has defined behavior for an indirect branch in the
2996 // same function, and we do not currently support inlining indirect
2997 // branches. But, the inliner may not see an indirect branch that ends up
2998 // being dead code at a particular call site. If the blockaddress escapes
2999 // the function, e.g., via a global variable, inlining may lead to an
3000 // invalid cross-function reference.
3001 // FIXME: pr/39560: continue relaxing this overt restriction.
3002 if (BB->hasAddressTaken())
3003 return InlineResult::failure(Reason: "blockaddress used");
3004
3005 // Analyze the cost of this block. If we blow through the threshold, this
3006 // returns false, and we can bail on out.
3007 InlineResult IR = analyzeBlock(BB, EphValues: *EphValues);
3008 if (!IR.isSuccess())
3009 return IR;
3010
3011 Instruction *TI = BB->getTerminator();
3012
3013 // Add in the live successors by first checking whether we have terminator
3014 // that may be simplified based on the values simplified by this call.
3015 if (CondBrInst *BI = dyn_cast<CondBrInst>(Val: TI)) {
3016 Value *Cond = BI->getCondition();
3017 if (ConstantInt *SimpleCond = getSimplifiedValue<ConstantInt>(V: Cond)) {
3018 BasicBlock *NextBB = BI->getSuccessor(i: SimpleCond->isZero() ? 1 : 0);
3019 BBWorklist.insert(X: NextBB);
3020 KnownSuccessors[BB] = NextBB;
3021 findDeadBlocks(CurrBB: BB, NextBB);
3022 continue;
3023 }
3024 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Val: TI)) {
3025 Value *Cond = SI->getCondition();
3026 if (ConstantInt *SimpleCond = getSimplifiedValue<ConstantInt>(V: Cond)) {
3027 BasicBlock *NextBB = SI->findCaseValue(C: SimpleCond)->getCaseSuccessor();
3028 BBWorklist.insert(X: NextBB);
3029 KnownSuccessors[BB] = NextBB;
3030 findDeadBlocks(CurrBB: BB, NextBB);
3031 continue;
3032 }
3033 }
3034
3035 // If we're unable to select a particular successor, just count all of
3036 // them.
3037 BBWorklist.insert_range(R: successors(BB));
3038
3039 onBlockAnalyzed(BB);
3040 }
3041
3042 // If this is a noduplicate call, we can still inline as long as
3043 // inlining this would cause the removal of the caller (so the instruction
3044 // is not actually duplicated, just moved).
3045 if (!isSoleCallToLocalFunction(CB: CandidateCall, Callee: F) && ContainsNoDuplicateCall)
3046 return InlineResult::failure(Reason: "noduplicate");
3047
3048 // If the callee's stack size exceeds the user-specified threshold,
3049 // do not let it be inlined.
3050 // The command line option overrides a limit set in the function attributes.
3051 size_t FinalStackSizeThreshold = StackSizeThreshold;
3052 if (!StackSizeThreshold.getNumOccurrences())
3053 if (std::optional<int> AttrMaxStackSize = getStringFnAttrAsInt(
3054 F: Caller, AttrKind: InlineConstants::MaxInlineStackSizeAttributeName))
3055 FinalStackSizeThreshold = *AttrMaxStackSize;
3056 if (AllocatedSize > FinalStackSizeThreshold)
3057 return InlineResult::failure(Reason: "stacksize");
3058
3059 return finalizeAnalysis();
3060}
3061
3062void InlineCostCallAnalyzer::print(raw_ostream &OS) {
3063#define DEBUG_PRINT_STAT(x) OS << " " #x ": " << x << "\n"
3064 if (PrintInstructionComments)
3065 F.print(OS, AAW: &Writer);
3066 DEBUG_PRINT_STAT(NumConstantArgs);
3067 DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs);
3068 DEBUG_PRINT_STAT(NumAllocaArgs);
3069 DEBUG_PRINT_STAT(NumConstantPtrCmps);
3070 DEBUG_PRINT_STAT(NumConstantPtrDiffs);
3071 DEBUG_PRINT_STAT(NumInstructionsSimplified);
3072 DEBUG_PRINT_STAT(NumInstructions);
3073 DEBUG_PRINT_STAT(NumInlineAsmInstructions);
3074 DEBUG_PRINT_STAT(SROACostSavings);
3075 DEBUG_PRINT_STAT(SROACostSavingsLost);
3076 DEBUG_PRINT_STAT(LoadEliminationCost);
3077 DEBUG_PRINT_STAT(ContainsNoDuplicateCall);
3078 DEBUG_PRINT_STAT(Cost);
3079 DEBUG_PRINT_STAT(Threshold);
3080#undef DEBUG_PRINT_STAT
3081}
3082
3083#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3084/// Dump stats about this call's analysis.
3085LLVM_DUMP_METHOD void InlineCostCallAnalyzer::dump() { print(dbgs()); }
3086#endif
3087
3088/// Test that there are no attribute conflicts between Caller and Callee
3089/// that prevent inlining.
3090static bool functionsHaveCompatibleAttributes(
3091 Function *Caller, Function *Callee,
3092 function_ref<const TargetLibraryInfo &(Function &)> &GetTLI) {
3093 // Note that CalleeTLI must be a copy not a reference. The legacy pass manager
3094 // caches the most recently created TLI in the TargetLibraryInfoWrapperPass
3095 // object, and always returns the same object (which is overwritten on each
3096 // GetTLI call). Therefore we copy the first result.
3097 auto CalleeTLI = GetTLI(*Callee);
3098 return GetTLI(*Caller).areInlineCompatible(CalleeTLI,
3099 AllowCallerSuperset: InlineCallerSupersetNoBuiltin) &&
3100 AttributeFuncs::areInlineCompatible(Caller: *Caller, Callee: *Callee);
3101}
3102
3103int llvm::getCallsiteCost(const TargetTransformInfo &TTI, const CallBase &Call,
3104 const DataLayout &DL) {
3105 int64_t Cost = 0;
3106 for (unsigned I = 0, E = Call.arg_size(); I != E; ++I) {
3107 if (Call.isByValArgument(ArgNo: I)) {
3108 // We approximate the number of loads and stores needed by dividing the
3109 // size of the byval type by the target's pointer size.
3110 PointerType *PTy = cast<PointerType>(Val: Call.getArgOperand(i: I)->getType());
3111 unsigned TypeSize = DL.getTypeSizeInBits(Ty: Call.getParamByValType(ArgNo: I));
3112 unsigned AS = PTy->getAddressSpace();
3113 unsigned PointerSize = DL.getPointerSizeInBits(AS);
3114 // Ceiling division.
3115 unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize;
3116
3117 // If it generates more than 8 stores it is likely to be expanded as an
3118 // inline memcpy so we take that as an upper bound. Otherwise we assume
3119 // one load and one store per word copied.
3120 // FIXME: The maxStoresPerMemcpy setting from the target should be used
3121 // here instead of a magic number of 8, but it's not available via
3122 // DataLayout.
3123 NumStores = std::min(a: NumStores, b: 8U);
3124
3125 Cost += 2 * NumStores * InstrCost;
3126 } else {
3127 // For non-byval arguments subtract off one instruction per call
3128 // argument.
3129 Cost += InstrCost;
3130 }
3131 }
3132 // The call instruction also disappears after inlining.
3133 Cost += InstrCost;
3134 Cost += TTI.getInlineCallPenalty(F: Call.getCaller(), Call, DefaultCallPenalty: CallPenalty);
3135
3136 return std::min<int64_t>(a: Cost, INT_MAX);
3137}
3138
3139InlineCost llvm::getInlineCost(
3140 CallBase &Call, const InlineParams &Params, TargetTransformInfo &CalleeTTI,
3141 function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
3142 function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
3143 function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
3144 ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE,
3145 function_ref<EphemeralValuesCache &(Function &)> GetEphValuesCache) {
3146 return getInlineCost(Call, Callee: Call.getCalledFunction(), Params, CalleeTTI,
3147 GetAssumptionCache, GetTLI, GetBFI, PSI, ORE,
3148 GetEphValuesCache);
3149}
3150
3151std::optional<int> llvm::getInliningCostEstimate(
3152 CallBase &Call, TargetTransformInfo &CalleeTTI,
3153 function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
3154 function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
3155 function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
3156 ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE) {
3157 const InlineParams Params = {/* DefaultThreshold*/ 0,
3158 /*HintThreshold*/ {},
3159 /*OptSizeHintThreshold*/ {},
3160 /*ColdThreshold*/ {},
3161 /*OptSizeThreshold*/ {},
3162 /*OptMinSizeThreshold*/ {},
3163 /*HotCallSiteThreshold*/ {},
3164 /*LocallyHotCallSiteThreshold*/ {},
3165 /*ColdCallSiteThreshold*/ {},
3166 /*ComputeFullInlineCost*/ true,
3167 /*EnableDeferral*/ true};
3168
3169 InlineCostCallAnalyzer CA(*Call.getCalledFunction(), Call, Params, CalleeTTI,
3170 GetAssumptionCache, GetBFI, GetTLI, PSI, ORE, true,
3171 /*IgnoreThreshold*/ true);
3172 auto R = CA.analyze();
3173 if (!R.isSuccess())
3174 return std::nullopt;
3175 return CA.getCost();
3176}
3177
3178std::optional<InlineCostFeatures> llvm::getInliningCostFeatures(
3179 CallBase &Call, TargetTransformInfo &CalleeTTI,
3180 function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
3181 function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
3182 function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
3183 ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE) {
3184 InlineCostFeaturesAnalyzer CFA(CalleeTTI, GetAssumptionCache, GetBFI, GetTLI,
3185 PSI, ORE, *Call.getCalledFunction(), Call);
3186 auto R = CFA.analyze();
3187 if (!R.isSuccess())
3188 return std::nullopt;
3189 return CFA.features();
3190}
3191
3192std::optional<InlineResult> llvm::getAttributeBasedInliningDecision(
3193 CallBase &Call, Function *Callee, TargetTransformInfo &CalleeTTI,
3194 function_ref<const TargetLibraryInfo &(Function &)> GetTLI) {
3195
3196 // Cannot inline indirect calls.
3197 if (!Callee)
3198 return InlineResult::failure(Reason: "indirect call");
3199
3200 // When callee coroutine function is inlined into caller coroutine function
3201 // before coro-split pass,
3202 // coro-early pass can not handle this quiet well.
3203 // So we won't inline the coroutine function if it have not been unsplited
3204 if (Callee->isPresplitCoroutine())
3205 return InlineResult::failure(Reason: "unsplited coroutine call");
3206
3207 // Inlining into a function with less target features is unsound, so enforce
3208 // this even if alwaysinline is used.
3209 Function *Caller = Call.getCaller();
3210 if (!IgnoreTTIInlineCompatible &&
3211 !CalleeTTI.areInlineCompatible(Caller, Callee))
3212 return InlineResult::failure(Reason: "conflicting target features");
3213
3214 // Calls to functions with always-inline attributes should be inlined
3215 // whenever possible.
3216 if (Call.hasFnAttr(Kind: Attribute::AlwaysInline)) {
3217 if (Call.getAttributes().hasFnAttr(Kind: Attribute::NoInline))
3218 return InlineResult::failure(Reason: "noinline call site attribute");
3219
3220 if (!AttributeFuncs::isStrictFPInlineCompatible(Caller: *Caller, Callee: *Callee))
3221 return InlineResult::failure(Reason: "incompatible strictfp attributes");
3222
3223 auto IsViable = isInlineViable(Callee&: *Callee);
3224 if (IsViable.isSuccess())
3225 return InlineResult::success();
3226 return InlineResult::failure(Reason: IsViable.getFailureReason());
3227 }
3228
3229 // Never inline functions with conflicting attributes (unless callee has
3230 // always-inline attribute).
3231 if (!functionsHaveCompatibleAttributes(Caller, Callee, GetTLI))
3232 return InlineResult::failure(Reason: "conflicting attributes");
3233
3234 // Flatten: inline all viable calls from flatten functions regardless of cost.
3235 // Checked before optnone so that flatten takes priority.
3236 if (Caller->hasFnAttribute(Kind: Attribute::Flatten)) {
3237 auto IsViable = isInlineViable(Callee&: *Callee);
3238 if (IsViable.isSuccess())
3239 return InlineResult::success();
3240 return InlineResult::failure(Reason: IsViable.getFailureReason());
3241 }
3242
3243 // Don't inline this call if the caller has the optnone attribute.
3244 if (Caller->hasOptNone())
3245 return InlineResult::failure(Reason: "optnone attribute");
3246
3247 // Don't inline functions which can be interposed at link-time.
3248 if (Callee->isInterposable(/*CheckNoIPA=*/false))
3249 return InlineResult::failure(Reason: "interposable");
3250
3251 // Don't inline functions marked noinline.
3252 if (Callee->hasFnAttribute(Kind: Attribute::NoInline))
3253 return InlineResult::failure(Reason: "noinline function attribute");
3254
3255 // Don't inline call sites marked noinline.
3256 if (Call.isNoInline())
3257 return InlineResult::failure(Reason: "noinline call site attribute");
3258
3259 // Don't inline functions that are loader replaceable.
3260 if (Callee->hasFnAttribute(Kind: "loader-replaceable"))
3261 return InlineResult::failure(Reason: "loader replaceable function attribute");
3262
3263 return std::nullopt;
3264}
3265
3266InlineCost llvm::getInlineCost(
3267 CallBase &Call, Function *Callee, const InlineParams &Params,
3268 TargetTransformInfo &CalleeTTI,
3269 function_ref<AssumptionCache &(Function &)> GetAssumptionCache,
3270 function_ref<const TargetLibraryInfo &(Function &)> GetTLI,
3271 function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
3272 ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE,
3273 function_ref<EphemeralValuesCache &(Function &)> GetEphValuesCache) {
3274
3275 auto UserDecision =
3276 llvm::getAttributeBasedInliningDecision(Call, Callee, CalleeTTI, GetTLI);
3277
3278 if (UserDecision) {
3279 if (UserDecision->isSuccess())
3280 return llvm::InlineCost::getAlways(Reason: "always inline attribute");
3281 return llvm::InlineCost::getNever(Reason: UserDecision->getFailureReason());
3282 }
3283
3284 if (InlineAllViableCalls && isInlineViable(Callee&: *Callee).isSuccess())
3285 return llvm::InlineCost::getAlways(
3286 Reason: "Inlining forced by -inline-all-viable-calls");
3287
3288 LLVM_DEBUG(llvm::dbgs() << " Analyzing call of " << Callee->getName()
3289 << "... (caller:" << Call.getCaller()->getName()
3290 << ")\n");
3291
3292 InlineCostCallAnalyzer CA(*Callee, Call, Params, CalleeTTI,
3293 GetAssumptionCache, GetBFI, GetTLI, PSI, ORE,
3294 /*BoostIndirect=*/true, /*IgnoreThreshold=*/false,
3295 GetEphValuesCache);
3296 InlineResult ShouldInline = CA.analyze();
3297
3298 LLVM_DEBUG(CA.dump());
3299
3300 // Always make cost benefit based decision explicit.
3301 // We use always/never here since threshold is not meaningful,
3302 // as it's not what drives cost-benefit analysis.
3303 if (CA.wasDecidedByCostBenefit()) {
3304 if (ShouldInline.isSuccess())
3305 return InlineCost::getAlways(Reason: "benefit over cost",
3306 CostBenefit: CA.getCostBenefitPair());
3307 else
3308 return InlineCost::getNever(Reason: "cost over benefit", CostBenefit: CA.getCostBenefitPair());
3309 }
3310
3311 if (CA.wasDecidedByCostThreshold())
3312 return InlineCost::get(Cost: CA.getCost(), Threshold: CA.getThreshold(),
3313 StaticBonus: CA.getStaticBonusApplied());
3314
3315 // No details on how the decision was made, simply return always or never.
3316 return ShouldInline.isSuccess()
3317 ? InlineCost::getAlways(Reason: "empty function")
3318 : InlineCost::getNever(Reason: ShouldInline.getFailureReason());
3319}
3320
3321InlineResult llvm::isInlineViable(Function &F) {
3322 bool ReturnsTwice = F.hasFnAttribute(Kind: Attribute::ReturnsTwice);
3323 for (BasicBlock &BB : F) {
3324 // Disallow inlining of functions which contain indirect branches.
3325 if (isa<IndirectBrInst>(Val: BB.getTerminator()))
3326 return InlineResult::failure(Reason: "contains indirect branches");
3327
3328 // Disallow inlining of blockaddresses.
3329 if (BB.hasAddressTaken())
3330 return InlineResult::failure(Reason: "blockaddress used");
3331
3332 for (auto &II : BB) {
3333 CallBase *Call = dyn_cast<CallBase>(Val: &II);
3334 if (!Call)
3335 continue;
3336
3337 // Disallow recursive calls.
3338 Function *Callee = Call->getCalledFunction();
3339 if (&F == Callee)
3340 return InlineResult::failure(Reason: "recursive call");
3341
3342 // Disallow calls which expose returns-twice to a function not previously
3343 // attributed as such.
3344 if (!ReturnsTwice && isa<CallInst>(Val: Call) &&
3345 cast<CallInst>(Val: Call)->canReturnTwice())
3346 return InlineResult::failure(Reason: "exposes returns-twice attribute");
3347
3348 if (Callee)
3349 switch (Callee->getIntrinsicID()) {
3350 default:
3351 break;
3352 case llvm::Intrinsic::icall_branch_funnel:
3353 // Disallow inlining of @llvm.icall.branch.funnel because current
3354 // backend can't separate call targets from call arguments.
3355 return InlineResult::failure(
3356 Reason: "disallowed inlining of @llvm.icall.branch.funnel");
3357 case llvm::Intrinsic::localescape:
3358 // Disallow inlining functions that call @llvm.localescape. Doing this
3359 // correctly would require major changes to the inliner.
3360 return InlineResult::failure(
3361 Reason: "disallowed inlining of @llvm.localescape");
3362 case llvm::Intrinsic::vastart:
3363 // Disallow inlining of functions that initialize VarArgs with
3364 // va_start.
3365 return InlineResult::failure(
3366 Reason: "contains VarArgs initialized with va_start");
3367 }
3368 }
3369 }
3370
3371 return InlineResult::success();
3372}
3373
3374// APIs to create InlineParams based on command line flags and/or other
3375// parameters.
3376
3377InlineParams llvm::getInlineParams(int Threshold) {
3378 InlineParams Params;
3379
3380 // This field is the threshold to use for a callee by default. This is
3381 // derived from one or more of:
3382 // * optimization or size-optimization levels,
3383 // * a value passed to createFunctionInliningPass function, or
3384 // * the -inline-threshold flag.
3385 // If the -inline-threshold flag is explicitly specified, that is used
3386 // irrespective of anything else.
3387 if (InlineThreshold.getNumOccurrences() > 0)
3388 Params.DefaultThreshold = InlineThreshold;
3389 else
3390 Params.DefaultThreshold = Threshold;
3391
3392 // Set the HintThreshold knob from the -inlinehint-threshold.
3393 Params.HintThreshold = HintThreshold;
3394 // Use same threshold for optsize by default.
3395 Params.OptSizeHintThreshold = HintThreshold;
3396
3397 // Set the HotCallSiteThreshold knob from the -hot-callsite-threshold.
3398 Params.HotCallSiteThreshold = HotCallSiteThreshold;
3399
3400 // If the -locally-hot-callsite-threshold is explicitly specified, use it to
3401 // populate LocallyHotCallSiteThreshold. Later, we populate
3402 // Params.LocallyHotCallSiteThreshold from -locally-hot-callsite-threshold if
3403 // we know that optimization level is O3 (in the getInlineParams variant that
3404 // takes the opt and size levels).
3405 // FIXME: Remove this check (and make the assignment unconditional) after
3406 // addressing size regression issues at O2.
3407 if (LocallyHotCallSiteThreshold.getNumOccurrences() > 0)
3408 Params.LocallyHotCallSiteThreshold = LocallyHotCallSiteThreshold;
3409
3410 // Set the ColdCallSiteThreshold knob from the
3411 // -inline-cold-callsite-threshold.
3412 Params.ColdCallSiteThreshold = ColdCallSiteThreshold;
3413
3414 // Set the OptMinSizeThreshold and OptSizeThreshold params only if the
3415 // -inlinehint-threshold commandline option is not explicitly given. If that
3416 // option is present, then its value applies even for callees with size and
3417 // minsize attributes.
3418 // If the -inline-threshold is not specified, set the ColdThreshold from the
3419 // -inlinecold-threshold even if it is not explicitly passed. If
3420 // -inline-threshold is specified, then -inlinecold-threshold needs to be
3421 // explicitly specified to set the ColdThreshold knob
3422 if (InlineThreshold.getNumOccurrences() == 0) {
3423 Params.OptMinSizeThreshold = InlineConstants::OptMinSizeThreshold;
3424 Params.OptSizeThreshold = InlineConstants::OptSizeThreshold;
3425 Params.ColdThreshold = ColdThreshold;
3426 } else if (ColdThreshold.getNumOccurrences() > 0) {
3427 Params.ColdThreshold = ColdThreshold;
3428 }
3429 return Params;
3430}
3431
3432InlineParams llvm::getInlineParams() {
3433 return getInlineParams(Threshold: DefaultThreshold);
3434}
3435
3436InlineParams llvm::getInlineParamsFromOptLevel(unsigned OptLevel) {
3437 auto Params =
3438 getInlineParams(Threshold: OptLevel > 2 ? InlineConstants::OptAggressiveThreshold
3439 : DefaultThreshold);
3440 // At O3, use the value of -locally-hot-callsite-threshold option to populate
3441 // Params.LocallyHotCallSiteThreshold. Below O3, this flag has effect only
3442 // when it is specified explicitly.
3443 if (OptLevel > 2)
3444 Params.LocallyHotCallSiteThreshold = LocallyHotCallSiteThreshold;
3445 return Params;
3446}
3447
3448PreservedAnalyses
3449InlineCostAnnotationPrinterPass::run(Function &F,
3450 FunctionAnalysisManager &FAM) {
3451 PrintInstructionComments = true;
3452 std::function<AssumptionCache &(Function &)> GetAssumptionCache =
3453 [&](Function &F) -> AssumptionCache & {
3454 return FAM.getResult<AssumptionAnalysis>(IR&: F);
3455 };
3456
3457 auto &MAMProxy = FAM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F);
3458 ProfileSummaryInfo *PSI =
3459 MAMProxy.getCachedResult<ProfileSummaryAnalysis>(IR&: *F.getParent());
3460 const TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(IR&: F);
3461
3462 // FIXME: Redesign the usage of InlineParams to expand the scope of this pass.
3463 // In the current implementation, the type of InlineParams doesn't matter as
3464 // the pass serves only for verification of inliner's decisions.
3465 // We can add a flag which determines InlineParams for this run. Right now,
3466 // the default InlineParams are used.
3467 const InlineParams Params = llvm::getInlineParams();
3468 for (BasicBlock &BB : F) {
3469 for (Instruction &I : BB) {
3470 if (auto *CB = dyn_cast<CallBase>(Val: &I)) {
3471 Function *CalledFunction = CB->getCalledFunction();
3472 if (!CalledFunction || CalledFunction->isDeclaration())
3473 continue;
3474 OptimizationRemarkEmitter ORE(CalledFunction);
3475 InlineCostCallAnalyzer ICCA(*CalledFunction, *CB, Params, TTI,
3476 GetAssumptionCache, nullptr, nullptr, PSI,
3477 &ORE);
3478 ICCA.analyze();
3479 OS << " Analyzing call of " << CalledFunction->getName()
3480 << "... (caller:" << CB->getCaller()->getName() << ")\n";
3481 ICCA.print(OS);
3482 OS << "\n";
3483 }
3484 }
3485 }
3486 return PreservedAnalyses::all();
3487}
3488