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