Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/InlineCost.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- InlineCost.cpp - Cost analysis for inliner -------------------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file implements inline cost analysis.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/Analysis/InlineCost.h"
14
#include "llvm/ADT/STLExtras.h"
15
#include "llvm/ADT/SetVector.h"
16
#include "llvm/ADT/SmallPtrSet.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/ADT/Statistic.h"
19
#include "llvm/Analysis/AssumptionCache.h"
20
#include "llvm/Analysis/BlockFrequencyInfo.h"
21
#include "llvm/Analysis/CodeMetrics.h"
22
#include "llvm/Analysis/ConstantFolding.h"
23
#include "llvm/Analysis/CFG.h"
24
#include "llvm/Analysis/InstructionSimplify.h"
25
#include "llvm/Analysis/LoopInfo.h"
26
#include "llvm/Analysis/ProfileSummaryInfo.h"
27
#include "llvm/Analysis/TargetTransformInfo.h"
28
#include "llvm/Analysis/ValueTracking.h"
29
#include "llvm/Config/llvm-config.h"
30
#include "llvm/IR/CallingConv.h"
31
#include "llvm/IR/DataLayout.h"
32
#include "llvm/IR/Dominators.h"
33
#include "llvm/IR/GetElementPtrTypeIterator.h"
34
#include "llvm/IR/GlobalAlias.h"
35
#include "llvm/IR/InstVisitor.h"
36
#include "llvm/IR/IntrinsicInst.h"
37
#include "llvm/IR/Operator.h"
38
#include "llvm/IR/PatternMatch.h"
39
#include "llvm/Support/Debug.h"
40
#include "llvm/Support/raw_ostream.h"
41
42
using namespace llvm;
43
44
0
#define DEBUG_TYPE "inline-cost"
45
46
STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");
47
48
static cl::opt<int> InlineThreshold(
49
    "inline-threshold", cl::Hidden, cl::init(225), cl::ZeroOrMore,
50
    cl::desc("Control the amount of inlining to perform (default = 225)"));
51
52
static cl::opt<int> HintThreshold(
53
    "inlinehint-threshold", cl::Hidden, cl::init(325), cl::ZeroOrMore, 
54
    cl::desc("Threshold for inlining functions with inline hint"));
55
56
static cl::opt<int>
57
    ColdCallSiteThreshold("inline-cold-callsite-threshold", cl::Hidden,
58
                          cl::init(45), cl::ZeroOrMore,
59
                          cl::desc("Threshold for inlining cold callsites"));
60
61
// We introduce this threshold to help performance of instrumentation based
62
// PGO before we actually hook up inliner with analysis passes such as BPI and
63
// BFI.
64
static cl::opt<int> ColdThreshold(
65
    "inlinecold-threshold", cl::Hidden, cl::init(45), cl::ZeroOrMore, 
66
    cl::desc("Threshold for inlining functions with cold attribute"));
67
68
static cl::opt<int>
69
    HotCallSiteThreshold("hot-callsite-threshold", cl::Hidden, cl::init(3000),
70
                         cl::ZeroOrMore,
71
                         cl::desc("Threshold for hot callsites "));
72
73
static cl::opt<int> LocallyHotCallSiteThreshold(
74
    "locally-hot-callsite-threshold", cl::Hidden, cl::init(525), cl::ZeroOrMore,
75
    cl::desc("Threshold for locally hot callsites "));
76
77
static cl::opt<int> ColdCallSiteRelFreq(
78
    "cold-callsite-rel-freq", cl::Hidden, cl::init(2), cl::ZeroOrMore,
79
    cl::desc("Maximum block frequency, expressed as a percentage of caller's "
80
             "entry frequency, for a callsite to be cold in the absence of "
81
             "profile information."));
82
83
static cl::opt<int> HotCallSiteRelFreq(
84
    "hot-callsite-rel-freq", cl::Hidden, cl::init(60), cl::ZeroOrMore,
85
    cl::desc("Minimum block frequency, expressed as a multiple of caller's "
86
             "entry frequency, for a callsite to be hot in the absence of "
87
             "profile information."));
88
89
static cl::opt<bool> OptComputeFullInlineCost(
90
    "inline-cost-full", cl::Hidden, cl::init(false), cl::ZeroOrMore,
91
    cl::desc("Compute the full inline cost of a call site even when the cost "
92
             "exceeds the threshold."));
93
94
namespace {
95
96
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
97
  typedef InstVisitor<CallAnalyzer, bool> Base;
98
  friend class InstVisitor<CallAnalyzer, bool>;
99
100
  /// The TargetTransformInfo available for this compilation.
101
  const TargetTransformInfo &TTI;
102
103
  /// Getter for the cache of @llvm.assume intrinsics.
104
  std::function<AssumptionCache &(Function &)> &GetAssumptionCache;
105
106
  /// Getter for BlockFrequencyInfo
107
  Optional<function_ref<BlockFrequencyInfo &(Function &)>> &GetBFI;
108
109
  /// Profile summary information.
110
  ProfileSummaryInfo *PSI;
111
112
  /// The called function.
113
  Function &F;
114
115
  // Cache the DataLayout since we use it a lot.
116
  const DataLayout &DL;
117
118
  /// The OptimizationRemarkEmitter available for this compilation.
119
  OptimizationRemarkEmitter *ORE;
120
121
  /// The candidate callsite being analyzed. Please do not use this to do
122
  /// analysis in the caller function; we want the inline cost query to be
123
  /// easily cacheable. Instead, use the cover function paramHasAttr.
124
  CallBase &CandidateCall;
125
126
  /// Tunable parameters that control the analysis.
127
  const InlineParams &Params;
128
129
  /// Upper bound for the inlining cost. Bonuses are being applied to account
130
  /// for speculative "expected profit" of the inlining decision.
131
  int Threshold;
132
133
  /// Inlining cost measured in abstract units, accounts for all the
134
  /// instructions expected to be executed for a given function invocation.
135
  /// Instructions that are statically proven to be dead based on call-site
136
  /// arguments are not counted here.
137
  int Cost = 0;
138
139
  bool ComputeFullInlineCost;
140
141
  bool IsCallerRecursive = false;
142
  bool IsRecursiveCall = false;
143
  bool ExposesReturnsTwice = false;
144
  bool HasDynamicAlloca = false;
145
  bool ContainsNoDuplicateCall = false;
146
  bool HasReturn = false;
147
  bool HasIndirectBr = false;
148
  bool HasUninlineableIntrinsic = false;
149
  bool InitsVargArgs = false;
150
151
  /// Number of bytes allocated statically by the callee.
152
  uint64_t AllocatedSize = 0;
153
  unsigned NumInstructions = 0;
154
  unsigned NumVectorInstructions = 0;
155
156
  /// Bonus to be applied when percentage of vector instructions in callee is
157
  /// high (see more details in updateThreshold).
158
  int VectorBonus = 0;
159
  /// Bonus to be applied when the callee has only one reachable basic block.
160
  int SingleBBBonus = 0;
161
162
  /// While we walk the potentially-inlined instructions, we build up and
163
  /// maintain a mapping of simplified values specific to this callsite. The
164
  /// idea is to propagate any special information we have about arguments to
165
  /// this call through the inlinable section of the function, and account for
166
  /// likely simplifications post-inlining. The most important aspect we track
167
  /// is CFG altering simplifications -- when we prove a basic block dead, that
168
  /// can cause dramatic shifts in the cost of inlining a function.
169
  DenseMap<Value *, Constant *> SimplifiedValues;
170
171
  /// Keep track of the values which map back (through function arguments) to
172
  /// allocas on the caller stack which could be simplified through SROA.
173
  DenseMap<Value *, Value *> SROAArgValues;
174
175
  /// The mapping of caller Alloca values to their accumulated cost savings. If
176
  /// we have to disable SROA for one of the allocas, this tells us how much
177
  /// cost must be added.
178
  DenseMap<Value *, int> SROAArgCosts;
179
180
  /// Keep track of values which map to a pointer base and constant offset.
181
  DenseMap<Value *, std::pair<Value *, APInt>> ConstantOffsetPtrs;
182
183
  /// Keep track of dead blocks due to the constant arguments.
184
  SetVector<BasicBlock *> DeadBlocks;
185
186
  /// The mapping of the blocks to their known unique successors due to the
187
  /// constant arguments.
188
  DenseMap<BasicBlock *, BasicBlock *> KnownSuccessors;
189
190
  /// Model the elimination of repeated loads that is expected to happen
191
  /// whenever we simplify away the stores that would otherwise cause them to be
192
  /// loads.
193
  bool EnableLoadElimination;
194
  SmallPtrSet<Value *, 16> LoadAddrSet;
195
  int LoadEliminationCost = 0;
196
197
  // Custom simplification helper routines.
198
  bool isAllocaDerivedArg(Value *V);
199
  bool lookupSROAArgAndCost(Value *V, Value *&Arg,
200
                            DenseMap<Value *, int>::iterator &CostIt);
201
  void disableSROA(DenseMap<Value *, int>::iterator CostIt);
202
  void disableSROA(Value *V);
203
  void findDeadBlocks(BasicBlock *CurrBB, BasicBlock *NextBB);
204
  void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
205
                          int InstructionCost);
206
  void disableLoadElimination();
207
  bool isGEPFree(GetElementPtrInst &GEP);
208
  bool canFoldInboundsGEP(GetElementPtrInst &I);
209
  bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
210
  bool simplifyCallSite(Function *F, CallBase &Call);
211
  template <typename Callable>
212
  bool simplifyInstruction(Instruction &I, Callable Evaluate);
213
  ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V);
214
215
  /// Return true if the given argument to the function being considered for
216
  /// inlining has the given attribute set either at the call site or the
217
  /// function declaration.  Primarily used to inspect call site specific
218
  /// attributes since these can be more precise than the ones on the callee
219
  /// itself.
220
  bool paramHasAttr(Argument *A, Attribute::AttrKind Attr);
221
222
  /// Return true if the given value is known non null within the callee if
223
  /// inlined through this particular callsite.
224
  bool isKnownNonNullInCallee(Value *V);
225
226
  /// Update Threshold based on callsite properties such as callee
227
  /// attributes and callee hotness for PGO builds. The Callee is explicitly
228
  /// passed to support analyzing indirect calls whose target is inferred by
229
  /// analysis.
230
  void updateThreshold(CallBase &Call, Function &Callee);
231
232
  /// Return true if size growth is allowed when inlining the callee at \p Call.
233
  bool allowSizeGrowth(CallBase &Call);
234
235
  /// Return true if \p Call is a cold callsite.
236
  bool isColdCallSite(CallBase &Call, BlockFrequencyInfo *CallerBFI);
237
238
  /// Return a higher threshold if \p Call is a hot callsite.
239
  Optional<int> getHotCallSiteThreshold(CallBase &Call,
240
                                        BlockFrequencyInfo *CallerBFI);
241
242
  // Custom analysis routines.
243
  InlineResult analyzeBlock(BasicBlock *BB,
244
                            SmallPtrSetImpl<const Value *> &EphValues);
245
246
  /// Handle a capped 'int' increment for Cost.
247
23.2M
  void addCost(int64_t Inc, int64_t UpperBound = INT_MAX) {
248
23.2M
    assert(UpperBound > 0 && UpperBound <= INT_MAX && "invalid upper bound");
249
23.2M
    Cost = (int)std::min(UpperBound, Cost + Inc);
250
23.2M
  }
251
252
  // Disable several entry points to the visitor so we don't accidentally use
253
  // them by declaring but not defining them here.
254
  void visit(Module *);
255
  void visit(Module &);
256
  void visit(Function *);
257
  void visit(Function &);
258
  void visit(BasicBlock *);
259
  void visit(BasicBlock &);
260
261
  // Provide base case for our instruction visit.
262
  bool visitInstruction(Instruction &I);
263
264
  // Our visit overrides.
265
  bool visitAlloca(AllocaInst &I);
266
  bool visitPHI(PHINode &I);
267
  bool visitGetElementPtr(GetElementPtrInst &I);
268
  bool visitBitCast(BitCastInst &I);
269
  bool visitPtrToInt(PtrToIntInst &I);
270
  bool visitIntToPtr(IntToPtrInst &I);
271
  bool visitCastInst(CastInst &I);
272
  bool visitUnaryInstruction(UnaryInstruction &I);
273
  bool visitCmpInst(CmpInst &I);
274
  bool visitSub(BinaryOperator &I);
275
  bool visitBinaryOperator(BinaryOperator &I);
276
  bool visitFNeg(UnaryOperator &I);
277
  bool visitLoad(LoadInst &I);
278
  bool visitStore(StoreInst &I);
279
  bool visitExtractValue(ExtractValueInst &I);
280
  bool visitInsertValue(InsertValueInst &I);
281
  bool visitCallBase(CallBase &Call);
282
  bool visitReturnInst(ReturnInst &RI);
283
  bool visitBranchInst(BranchInst &BI);
284
  bool visitSelectInst(SelectInst &SI);
285
  bool visitSwitchInst(SwitchInst &SI);
286
  bool visitIndirectBrInst(IndirectBrInst &IBI);
287
  bool visitResumeInst(ResumeInst &RI);
288
  bool visitCleanupReturnInst(CleanupReturnInst &RI);
289
  bool visitCatchReturnInst(CatchReturnInst &RI);
290
  bool visitUnreachableInst(UnreachableInst &I);
291
292
public:
293
  CallAnalyzer(const TargetTransformInfo &TTI,
294
               std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
295
               Optional<function_ref<BlockFrequencyInfo &(Function &)>> &GetBFI,
296
               ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE,
297
               Function &Callee, CallBase &Call, const InlineParams &Params)
298
      : TTI(TTI), GetAssumptionCache(GetAssumptionCache), GetBFI(GetBFI),
299
        PSI(PSI), F(Callee), DL(F.getParent()->getDataLayout()), ORE(ORE),
300
        CandidateCall(Call), Params(Params), Threshold(Params.DefaultThreshold),
301
        ComputeFullInlineCost(OptComputeFullInlineCost ||
302
                              Params.ComputeFullInlineCost || ORE),
303
805k
        EnableLoadElimination(true) {}
304
305
  InlineResult analyzeCall(CallBase &Call);
306
307
1.59M
  int getThreshold() { return Threshold; }
308
1.59M
  int getCost() { return Cost; }
309
310
  // Keep a bunch of stats about the cost savings found so we can print them
311
  // out when debugging.
312
  unsigned NumConstantArgs = 0;
313
  unsigned NumConstantOffsetPtrArgs = 0;
314
  unsigned NumAllocaArgs = 0;
315
  unsigned NumConstantPtrCmps = 0;
316
  unsigned NumConstantPtrDiffs = 0;
317
  unsigned NumInstructionsSimplified = 0;
318
  unsigned SROACostSavings = 0;
319
  unsigned SROACostSavingsLost = 0;
320
321
  void dump();
322
};
323
324
} // namespace
325
326
/// Test whether the given value is an Alloca-derived function argument.
327
451k
bool CallAnalyzer::isAllocaDerivedArg(Value *V) {
328
451k
  return SROAArgValues.count(V);
329
451k
}
330
331
/// Lookup the SROA-candidate argument and cost iterator which V maps to.
332
/// Returns false if V does not map to a SROA-candidate.
333
bool CallAnalyzer::lookupSROAArgAndCost(
334
30.6M
    Value *V, Value *&Arg, DenseMap<Value *, int>::iterator &CostIt) {
335
30.6M
  if (SROAArgValues.empty() || 
SROAArgCosts.empty()8.98M
)
336
23.6M
    return false;
337
6.98M
338
6.98M
  DenseMap<Value *, Value *>::iterator ArgIt = SROAArgValues.find(V);
339
6.98M
  if (ArgIt == SROAArgValues.end())
340
5.84M
    return false;
341
1.14M
342
1.14M
  Arg = ArgIt->second;
343
1.14M
  CostIt = SROAArgCosts.find(Arg);
344
1.14M
  return CostIt != SROAArgCosts.end();
345
1.14M
}
346
347
/// Disable SROA for the candidate marked by this cost iterator.
348
///
349
/// This marks the candidate as no longer viable for SROA, and adds the cost
350
/// savings associated with it back into the inline cost measurement.
351
88.2k
void CallAnalyzer::disableSROA(DenseMap<Value *, int>::iterator CostIt) {
352
88.2k
  // If we're no longer able to perform SROA we need to undo its cost savings
353
88.2k
  // and prevent subsequent analysis.
354
88.2k
  addCost(CostIt->second);
355
88.2k
  SROACostSavings -= CostIt->second;
356
88.2k
  SROACostSavingsLost += CostIt->second;
357
88.2k
  SROAArgCosts.erase(CostIt);
358
88.2k
  disableLoadElimination();
359
88.2k
}
360
361
/// If 'V' maps to a SROA candidate, disable SROA for it.
362
14.7M
void CallAnalyzer::disableSROA(Value *V) {
363
14.7M
  Value *SROAArg;
364
14.7M
  DenseMap<Value *, int>::iterator CostIt;
365
14.7M
  if (lookupSROAArgAndCost(V, SROAArg, CostIt))
366
85.3k
    disableSROA(CostIt);
367
14.7M
}
368
369
/// Accumulate the given cost for a particular SROA candidate.
370
void CallAnalyzer::accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
371
539k
                                      int InstructionCost) {
372
539k
  CostIt->second += InstructionCost;
373
539k
  SROACostSavings += InstructionCost;
374
539k
}
375
376
4.45M
void CallAnalyzer::disableLoadElimination() {
377
4.45M
  if (EnableLoadElimination) {
378
522k
    addCost(LoadEliminationCost);
379
522k
    LoadEliminationCost = 0;
380
522k
    EnableLoadElimination = false;
381
522k
  }
382
4.45M
}
383
384
/// Accumulate a constant GEP offset into an APInt if possible.
385
///
386
/// Returns false if unable to compute the offset for any reason. Respects any
387
/// simplified values known during the analysis of this callsite.
388
2.63M
bool CallAnalyzer::accumulateGEPOffset(GEPOperator &GEP, APInt &Offset) {
389
2.63M
  unsigned IntPtrWidth = DL.getIndexTypeSizeInBits(GEP.getType());
390
2.63M
  assert(IntPtrWidth == Offset.getBitWidth());
391
2.63M
392
2.63M
  for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
393
11.1M
       GTI != GTE; 
++GTI8.53M
) {
394
8.77M
    ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand());
395
8.77M
    if (!OpC)
396
248k
      if (Constant *SimpleOp = SimplifiedValues.lookup(GTI.getOperand()))
397
4.93k
        OpC = dyn_cast<ConstantInt>(SimpleOp);
398
8.77M
    if (!OpC)
399
243k
      return false;
400
8.53M
    if (OpC->isZero())
401
6.13M
      continue;
402
2.40M
403
2.40M
    // Handle a struct index, which adds its field offset to the pointer.
404
2.40M
    if (StructType *STy = GTI.getStructTypeOrNull()) {
405
1.91M
      unsigned ElementIdx = OpC->getZExtValue();
406
1.91M
      const StructLayout *SL = DL.getStructLayout(STy);
407
1.91M
      Offset += APInt(IntPtrWidth, SL->getElementOffset(ElementIdx));
408
1.91M
      continue;
409
1.91M
    }
410
490k
411
490k
    APInt TypeSize(IntPtrWidth, DL.getTypeAllocSize(GTI.getIndexedType()));
412
490k
    Offset += OpC->getValue().sextOrTrunc(IntPtrWidth) * TypeSize;
413
490k
  }
414
2.63M
  
return true2.39M
;
415
2.63M
}
416
417
/// Use TTI to check whether a GEP is free.
418
///
419
/// Respects any simplified values known during the analysis of this callsite.
420
648k
bool CallAnalyzer::isGEPFree(GetElementPtrInst &GEP) {
421
648k
  SmallVector<Value *, 4> Operands;
422
648k
  Operands.push_back(GEP.getOperand(0));
423
1.99M
  for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; 
++I1.34M
)
424
1.34M
    if (Constant *SimpleOp = SimplifiedValues.lookup(*I))
425
358
       Operands.push_back(SimpleOp);
426
1.34M
     else
427
1.34M
       Operands.push_back(*I);
428
648k
  return TargetTransformInfo::TCC_Free == TTI.getUserCost(&GEP, Operands);
429
648k
}
430
431
708k
bool CallAnalyzer::visitAlloca(AllocaInst &I) {
432
708k
  // Check whether inlining will turn a dynamic alloca into a static
433
708k
  // alloca and handle that case.
434
708k
  if (I.isArrayAllocation()) {
435
316
    Constant *Size = SimplifiedValues.lookup(I.getArraySize());
436
316
    if (auto *AllocSize = dyn_cast_or_null<ConstantInt>(Size)) {
437
20
      Type *Ty = I.getAllocatedType();
438
20
      AllocatedSize = SaturatingMultiplyAdd(
439
20
          AllocSize->getLimitedValue(), DL.getTypeAllocSize(Ty), AllocatedSize);
440
20
      return Base::visitAlloca(I);
441
20
    }
442
708k
  }
443
708k
444
708k
  // Accumulate the allocated size.
445
708k
  if (I.isStaticAlloca()) {
446
708k
    Type *Ty = I.getAllocatedType();
447
708k
    AllocatedSize = SaturatingAdd(DL.getTypeAllocSize(Ty), AllocatedSize);
448
708k
  }
449
708k
450
708k
  // We will happily inline static alloca instructions.
451
708k
  if (I.isStaticAlloca())
452
708k
    return Base::visitAlloca(I);
453
299
454
299
  // FIXME: This is overly conservative. Dynamic allocas are inefficient for
455
299
  // a variety of reasons, and so we would like to not inline them into
456
299
  // functions which don't currently have a dynamic alloca. This simply
457
299
  // disables inlining altogether in the presence of a dynamic alloca.
458
299
  HasDynamicAlloca = true;
459
299
  return false;
460
299
}
461
462
1.21M
bool CallAnalyzer::visitPHI(PHINode &I) {
463
1.21M
  // FIXME: We need to propagate SROA *disabling* through phi nodes, even
464
1.21M
  // though we don't want to propagate it's bonuses. The idea is to disable
465
1.21M
  // SROA if it *might* be used in an inappropriate manner.
466
1.21M
467
1.21M
  // Phi nodes are always zero-cost.
468
1.21M
  // FIXME: Pointer sizes may differ between different address spaces, so do we
469
1.21M
  // need to use correct address space in the call to getPointerSizeInBits here?
470
1.21M
  // Or could we skip the getPointerSizeInBits call completely? As far as I can
471
1.21M
  // see the ZeroOffset is used as a dummy value, so we can probably use any
472
1.21M
  // bit width for the ZeroOffset?
473
1.21M
  APInt ZeroOffset = APInt::getNullValue(DL.getPointerSizeInBits(0));
474
1.21M
  bool CheckSROA = I.getType()->isPointerTy();
475
1.21M
476
1.21M
  // Track the constant or pointer with constant offset we've seen so far.
477
1.21M
  Constant *FirstC = nullptr;
478
1.21M
  std::pair<Value *, APInt> FirstBaseAndOffset = {nullptr, ZeroOffset};
479
1.21M
  Value *FirstV = nullptr;
480
1.21M
481
1.71M
  for (unsigned i = 0, e = I.getNumIncomingValues(); i != e; 
++i498k
) {
482
1.68M
    BasicBlock *Pred = I.getIncomingBlock(i);
483
1.68M
    // If the incoming block is dead, skip the incoming block.
484
1.68M
    if (DeadBlocks.count(Pred))
485
81.9k
      continue;
486
1.59M
    // If the parent block of phi is not the known successor of the incoming
487
1.59M
    // block, skip the incoming block.
488
1.59M
    BasicBlock *KnownSuccessor = KnownSuccessors[Pred];
489
1.59M
    if (KnownSuccessor && 
KnownSuccessor != I.getParent()22.3k
)
490
9.17k
      continue;
491
1.58M
492
1.58M
    Value *V = I.getIncomingValue(i);
493
1.58M
    // If the incoming value is this phi itself, skip the incoming value.
494
1.58M
    if (&I == V)
495
273
      continue;
496
1.58M
497
1.58M
    Constant *C = dyn_cast<Constant>(V);
498
1.58M
    if (!C)
499
1.19M
      C = SimplifiedValues.lookup(V);
500
1.58M
501
1.58M
    std::pair<Value *, APInt> BaseAndOffset = {nullptr, ZeroOffset};
502
1.58M
    if (!C && 
CheckSROA1.17M
)
503
511k
      BaseAndOffset = ConstantOffsetPtrs.lookup(V);
504
1.58M
505
1.58M
    if (!C && 
!BaseAndOffset.first1.17M
)
506
1.11M
      // The incoming value is neither a constant nor a pointer with constant
507
1.11M
      // offset, exit early.
508
1.11M
      return true;
509
477k
510
477k
    if (FirstC) {
511
150k
      if (FirstC == C)
512
82.1k
        // If we've seen a constant incoming value before and it is the same
513
82.1k
        // constant we see this time, continue checking the next incoming value.
514
82.1k
        continue;
515
68.4k
      // Otherwise early exit because we either see a different constant or saw
516
68.4k
      // a constant before but we have a pointer with constant offset this time.
517
68.4k
      return true;
518
68.4k
    }
519
327k
520
327k
    if (FirstV) {
521
24.4k
      // The same logic as above, but check pointer with constant offset here.
522
24.4k
      if (FirstBaseAndOffset == BaseAndOffset)
523
22.7k
        continue;
524
1.65k
      return true;
525
1.65k
    }
526
302k
527
302k
    if (C) {
528
261k
      // This is the 1st time we've seen a constant, record it.
529
261k
      FirstC = C;
530
261k
      continue;
531
261k
    }
532
40.8k
533
40.8k
    // The remaining case is that this is the 1st time we've seen a pointer with
534
40.8k
    // constant offset, record it.
535
40.8k
    FirstV = V;
536
40.8k
    FirstBaseAndOffset = BaseAndOffset;
537
40.8k
  }
538
1.21M
539
1.21M
  // Check if we can map phi to a constant.
540
1.21M
  
if (33.7k
FirstC33.7k
) {
541
16.9k
    SimplifiedValues[&I] = FirstC;
542
16.9k
    return true;
543
16.9k
  }
544
16.7k
545
16.7k
  // Check if we can map phi to a pointer with constant offset.
546
16.7k
  if (FirstBaseAndOffset.first) {
547
16.7k
    ConstantOffsetPtrs[&I] = FirstBaseAndOffset;
548
16.7k
549
16.7k
    Value *SROAArg;
550
16.7k
    DenseMap<Value *, int>::iterator CostIt;
551
16.7k
    if (lookupSROAArgAndCost(FirstV, SROAArg, CostIt))
552
297
      SROAArgValues[&I] = SROAArg;
553
16.7k
  }
554
16.7k
555
16.7k
  return true;
556
16.7k
}
557
558
/// Check we can fold GEPs of constant-offset call site argument pointers.
559
/// This requires target data and inbounds GEPs.
560
///
561
/// \return true if the specified GEP can be folded.
562
4.80M
bool CallAnalyzer::canFoldInboundsGEP(GetElementPtrInst &I) {
563
4.80M
  // Check if we have a base + offset for the pointer.
564
4.80M
  std::pair<Value *, APInt> BaseAndOffset =
565
4.80M
      ConstantOffsetPtrs.lookup(I.getPointerOperand());
566
4.80M
  if (!BaseAndOffset.first)
567
2.49M
    return false;
568
2.31M
569
2.31M
  // Check if the offset of this GEP is constant, and if so accumulate it
570
2.31M
  // into Offset.
571
2.31M
  if (!accumulateGEPOffset(cast<GEPOperator>(I), BaseAndOffset.second))
572
214k
    return false;
573
2.10M
574
2.10M
  // Add the result as a new mapping to Base + Offset.
575
2.10M
  ConstantOffsetPtrs[&I] = BaseAndOffset;
576
2.10M
577
2.10M
  return true;
578
2.10M
}
579
580
4.95M
bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) {
581
4.95M
  Value *SROAArg;
582
4.95M
  DenseMap<Value *, int>::iterator CostIt;
583
4.95M
  bool SROACandidate =
584
4.95M
      lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt);
585
4.95M
586
4.95M
  // Lambda to check whether a GEP's indices are all constant.
587
4.95M
  auto IsGEPOffsetConstant = [&](GetElementPtrInst &GEP) {
588
9.37M
    for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; 
++I6.52M
)
589
7.17M
      if (!isa<Constant>(*I) && 
!SimplifiedValues.lookup(*I)660k
)
590
648k
        return false;
591
2.85M
    
return true2.20M
;
592
2.85M
  };
593
4.95M
594
4.95M
  if ((I.isInBounds() && 
canFoldInboundsGEP(I)4.80M
) ||
IsGEPOffsetConstant(I)2.85M
) {
595
4.30M
    if (SROACandidate)
596
385k
      SROAArgValues[&I] = SROAArg;
597
4.30M
598
4.30M
    // Constant GEPs are modeled as free.
599
4.30M
    return true;
600
4.30M
  }
601
648k
602
648k
  // Variable GEPs will require math and will disable SROA.
603
648k
  if (SROACandidate)
604
2.16k
    disableSROA(CostIt);
605
648k
  return isGEPFree(I);
606
648k
}
607
608
/// Simplify \p I if its operands are constants and update SimplifiedValues.
609
/// \p Evaluate is a callable specific to instruction type that evaluates the
610
/// instruction when all the operands are constants.
611
template <typename Callable>
612
6.62M
bool CallAnalyzer::simplifyInstruction(Instruction &I, Callable Evaluate) {
613
6.62M
  SmallVector<Constant *, 2> COps;
614
6.73M
  for (Value *Op : I.operands()) {
615
6.73M
    Constant *COp = dyn_cast<Constant>(Op);
616
6.73M
    if (!COp)
617
5.92M
      COp = SimplifiedValues.lookup(Op);
618
6.73M
    if (!COp)
619
5.80M
      return false;
620
923k
    COps.push_back(COp);
621
923k
  }
622
6.62M
  auto *C = Evaluate(COps);
623
821k
  if (!C)
624
708k
    return false;
625
113k
  SimplifiedValues[&I] = C;
626
113k
  return true;
627
113k
}
InlineCost.cpp:bool (anonymous namespace)::CallAnalyzer::simplifyInstruction<(anonymous namespace)::CallAnalyzer::visitUnaryInstruction(llvm::UnaryInstruction&)::$_4>(llvm::Instruction&, (anonymous namespace)::CallAnalyzer::visitUnaryInstruction(llvm::UnaryInstruction&)::$_4)
Line
Count
Source
612
708k
bool CallAnalyzer::simplifyInstruction(Instruction &I, Callable Evaluate) {
613
708k
  SmallVector<Constant *, 2> COps;
614
708k
  for (Value *Op : I.operands()) {
615
708k
    Constant *COp = dyn_cast<Constant>(Op);
616
708k
    if (!COp)
617
101
      COp = SimplifiedValues.lookup(Op);
618
708k
    if (!COp)
619
81
      return false;
620
708k
    COps.push_back(COp);
621
708k
  }
622
708k
  auto *C = Evaluate(COps);
623
708k
  if (!C)
624
708k
    return false;
625
0
  SimplifiedValues[&I] = C;
626
0
  return true;
627
0
}
InlineCost.cpp:bool (anonymous namespace)::CallAnalyzer::simplifyInstruction<(anonymous namespace)::CallAnalyzer::visitCastInst(llvm::CastInst&)::$_3>(llvm::Instruction&, (anonymous namespace)::CallAnalyzer::visitCastInst(llvm::CastInst&)::$_3)
Line
Count
Source
612
772k
bool CallAnalyzer::simplifyInstruction(Instruction &I, Callable Evaluate) {
613
772k
  SmallVector<Constant *, 2> COps;
614
772k
  for (Value *Op : I.operands()) {
615
772k
    Constant *COp = dyn_cast<Constant>(Op);
616
772k
    if (!COp)
617
772k
      COp = SimplifiedValues.lookup(Op);
618
772k
    if (!COp)
619
737k
      return false;
620
35.0k
    COps.push_back(COp);
621
35.0k
  }
622
772k
  auto *C = Evaluate(COps);
623
35.0k
  if (!C)
624
0
    return false;
625
35.0k
  SimplifiedValues[&I] = C;
626
35.0k
  return true;
627
35.0k
}
InlineCost.cpp:bool (anonymous namespace)::CallAnalyzer::simplifyInstruction<(anonymous namespace)::CallAnalyzer::visitPtrToInt(llvm::PtrToIntInst&)::$_1>(llvm::Instruction&, (anonymous namespace)::CallAnalyzer::visitPtrToInt(llvm::PtrToIntInst&)::$_1)
Line
Count
Source
612
185k
bool CallAnalyzer::simplifyInstruction(Instruction &I, Callable Evaluate) {
613
185k
  SmallVector<Constant *, 2> COps;
614
185k
  for (Value *Op : I.operands()) {
615
185k
    Constant *COp = dyn_cast<Constant>(Op);
616
185k
    if (!COp)
617
185k
      COp = SimplifiedValues.lookup(Op);
618
185k
    if (!COp)
619
185k
      return false;
620
359
    COps.push_back(COp);
621
359
  }
622
185k
  auto *C = Evaluate(COps);
623
359
  if (!C)
624
0
    return false;
625
359
  SimplifiedValues[&I] = C;
626
359
  return true;
627
359
}
InlineCost.cpp:bool (anonymous namespace)::CallAnalyzer::simplifyInstruction<(anonymous namespace)::CallAnalyzer::visitIntToPtr(llvm::IntToPtrInst&)::$_2>(llvm::Instruction&, (anonymous namespace)::CallAnalyzer::visitIntToPtr(llvm::IntToPtrInst&)::$_2)
Line
Count
Source
612
170k
bool CallAnalyzer::simplifyInstruction(Instruction &I, Callable Evaluate) {
613
170k
  SmallVector<Constant *, 2> COps;
614
170k
  for (Value *Op : I.operands()) {
615
170k
    Constant *COp = dyn_cast<Constant>(Op);
616
170k
    if (!COp)
617
170k
      COp = SimplifiedValues.lookup(Op);
618
170k
    if (!COp)
619
170k
      return false;
620
130
    COps.push_back(COp);
621
130
  }
622
170k
  auto *C = Evaluate(COps);
623
130
  if (!C)
624
0
    return false;
625
130
  SimplifiedValues[&I] = C;
626
130
  return true;
627
130
}
InlineCost.cpp:bool (anonymous namespace)::CallAnalyzer::simplifyInstruction<(anonymous namespace)::CallAnalyzer::visitBitCast(llvm::BitCastInst&)::$_0>(llvm::Instruction&, (anonymous namespace)::CallAnalyzer::visitBitCast(llvm::BitCastInst&)::$_0)
Line
Count
Source
612
1.91M
bool CallAnalyzer::simplifyInstruction(Instruction &I, Callable Evaluate) {
613
1.91M
  SmallVector<Constant *, 2> COps;
614
1.91M
  for (Value *Op : I.operands()) {
615
1.91M
    Constant *COp = dyn_cast<Constant>(Op);
616
1.91M
    if (!COp)
617
1.91M
      COp = SimplifiedValues.lookup(Op);
618
1.91M
    if (!COp)
619
1.91M
      return false;
620
7.11k
    COps.push_back(COp);
621
7.11k
  }
622
1.91M
  auto *C = Evaluate(COps);
623
7.11k
  if (!C)
624
0
    return false;
625
7.11k
  SimplifiedValues[&I] = C;
626
7.11k
  return true;
627
7.11k
}
InlineCost.cpp:bool (anonymous namespace)::CallAnalyzer::simplifyInstruction<(anonymous namespace)::CallAnalyzer::visitCmpInst(llvm::CmpInst&)::$_5>(llvm::Instruction&, (anonymous namespace)::CallAnalyzer::visitCmpInst(llvm::CmpInst&)::$_5)
Line
Count
Source
612
2.59M
bool CallAnalyzer::simplifyInstruction(Instruction &I, Callable Evaluate) {
613
2.59M
  SmallVector<Constant *, 2> COps;
614
2.66M
  for (Value *Op : I.operands()) {
615
2.66M
    Constant *COp = dyn_cast<Constant>(Op);
616
2.66M
    if (!COp)
617
2.59M
      COp = SimplifiedValues.lookup(Op);
618
2.66M
    if (!COp)
619
2.52M
      return false;
620
143k
    COps.push_back(COp);
621
143k
  }
622
2.59M
  auto *C = Evaluate(COps);
623
70.7k
  if (!C)
624
0
    return false;
625
70.7k
  SimplifiedValues[&I] = C;
626
70.7k
  return true;
627
70.7k
}
InlineCost.cpp:bool (anonymous namespace)::CallAnalyzer::simplifyInstruction<(anonymous namespace)::CallAnalyzer::visitExtractValue(llvm::ExtractValueInst&)::$_6>(llvm::Instruction&, (anonymous namespace)::CallAnalyzer::visitExtractValue(llvm::ExtractValueInst&)::$_6)
Line
Count
Source
612
204k
bool CallAnalyzer::simplifyInstruction(Instruction &I, Callable Evaluate) {
613
204k
  SmallVector<Constant *, 2> COps;
614
204k
  for (Value *Op : I.operands()) {
615
204k
    Constant *COp = dyn_cast<Constant>(Op);
616
204k
    if (!COp)
617
204k
      COp = SimplifiedValues.lookup(Op);
618
204k
    if (!COp)
619
204k
      return false;
620
150
    COps.push_back(COp);
621
150
  }
622
204k
  auto *C = Evaluate(COps);
623
150
  if (!C)
624
0
    return false;
625
150
  SimplifiedValues[&I] = C;
626
150
  return true;
627
150
}
InlineCost.cpp:bool (anonymous namespace)::CallAnalyzer::simplifyInstruction<(anonymous namespace)::CallAnalyzer::visitInsertValue(llvm::InsertValueInst&)::$_7>(llvm::Instruction&, (anonymous namespace)::CallAnalyzer::visitInsertValue(llvm::InsertValueInst&)::$_7)
Line
Count
Source
612
72.6k
bool CallAnalyzer::simplifyInstruction(Instruction &I, Callable Evaluate) {
613
72.6k
  SmallVector<Constant *, 2> COps;
614
100k
  for (Value *Op : I.operands()) {
615
100k
    Constant *COp = dyn_cast<Constant>(Op);
616
100k
    if (!COp)
617
72.6k
      COp = SimplifiedValues.lookup(Op);
618
100k
    if (!COp)
619
72.6k
      return false;
620
28.3k
    COps.push_back(COp);
621
28.3k
  }
622
72.6k
  auto *C = Evaluate(COps);
623
1
  if (!C)
624
0
    return false;
625
1
  SimplifiedValues[&I] = C;
626
1
  return true;
627
1
}
628
629
1.91M
bool CallAnalyzer::visitBitCast(BitCastInst &I) {
630
1.91M
  // Propagate constants through bitcasts.
631
1.91M
  if (simplifyInstruction(I, [&](SmallVectorImpl<Constant *> &COps) {
632
7.11k
        return ConstantExpr::getBitCast(COps[0], I.getType());
633
7.11k
      }))
634
7.11k
    return true;
635
1.91M
636
1.91M
  // Track base/offsets through casts
637
1.91M
  std::pair<Value *, APInt> BaseAndOffset =
638
1.91M
      ConstantOffsetPtrs.lookup(I.getOperand(0));
639
1.91M
  // Casts don't change the offset, just wrap it up.
640
1.91M
  if (BaseAndOffset.first)
641
584k
    ConstantOffsetPtrs[&I] = BaseAndOffset;
642
1.91M
643
1.91M
  // Also look for SROA candidates here.
644
1.91M
  Value *SROAArg;
645
1.91M
  DenseMap<Value *, int>::iterator CostIt;
646
1.91M
  if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
647
99.4k
    SROAArgValues[&I] = SROAArg;
648
1.91M
649
1.91M
  // Bitcasts are always zero cost.
650
1.91M
  return true;
651
1.91M
}
652
653
185k
bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) {
654
185k
  // Propagate constants through ptrtoint.
655
185k
  if (simplifyInstruction(I, [&](SmallVectorImpl<Constant *> &COps) {
656
359
        return ConstantExpr::getPtrToInt(COps[0], I.getType());
657
359
      }))
658
359
    return true;
659
185k
660
185k
  // Track base/offset pairs when converted to a plain integer provided the
661
185k
  // integer is large enough to represent the pointer.
662
185k
  unsigned IntegerSize = I.getType()->getScalarSizeInBits();
663
185k
  unsigned AS = I.getOperand(0)->getType()->getPointerAddressSpace();
664
185k
  if (IntegerSize >= DL.getPointerSizeInBits(AS)) {
665
185k
    std::pair<Value *, APInt> BaseAndOffset =
666
185k
        ConstantOffsetPtrs.lookup(I.getOperand(0));
667
185k
    if (BaseAndOffset.first)
668
30.9k
      ConstantOffsetPtrs[&I] = BaseAndOffset;
669
185k
  }
670
185k
671
185k
  // This is really weird. Technically, ptrtoint will disable SROA. However,
672
185k
  // unless that ptrtoint is *used* somewhere in the live basic blocks after
673
185k
  // inlining, it will be nuked, and SROA should proceed. All of the uses which
674
185k
  // would block SROA would also block SROA if applied directly to a pointer,
675
185k
  // and so we can just add the integer in here. The only places where SROA is
676
185k
  // preserved either cannot fire on an integer, or won't in-and-of themselves
677
185k
  // disable SROA (ext) w/o some later use that we would see and disable.
678
185k
  Value *SROAArg;
679
185k
  DenseMap<Value *, int>::iterator CostIt;
680
185k
  if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
681
220
    SROAArgValues[&I] = SROAArg;
682
185k
683
185k
  return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
684
185k
}
685
686
170k
bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) {
687
170k
  // Propagate constants through ptrtoint.
688
170k
  if (simplifyInstruction(I, [&](SmallVectorImpl<Constant *> &COps) {
689
130
        return ConstantExpr::getIntToPtr(COps[0], I.getType());
690
130
      }))
691
130
    return true;
692
170k
693
170k
  // Track base/offset pairs when round-tripped through a pointer without
694
170k
  // modifications provided the integer is not too large.
695
170k
  Value *Op = I.getOperand(0);
696
170k
  unsigned IntegerSize = Op->getType()->getScalarSizeInBits();
697
170k
  if (IntegerSize <= DL.getPointerTypeSizeInBits(I.getType())) {
698
170k
    std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Op);
699
170k
    if (BaseAndOffset.first)
700
198
      ConstantOffsetPtrs[&I] = BaseAndOffset;
701
170k
  }
702
170k
703
170k
  // "Propagate" SROA here in the same manner as we do for ptrtoint above.
704
170k
  Value *SROAArg;
705
170k
  DenseMap<Value *, int>::iterator CostIt;
706
170k
  if (lookupSROAArgAndCost(Op, SROAArg, CostIt))
707
5
    SROAArgValues[&I] = SROAArg;
708
170k
709
170k
  return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
710
170k
}
711
712
772k
bool CallAnalyzer::visitCastInst(CastInst &I) {
713
772k
  // Propagate constants through casts.
714
772k
  if (simplifyInstruction(I, [&](SmallVectorImpl<Constant *> &COps) {
715
35.0k
        return ConstantExpr::getCast(I.getOpcode(), COps[0], I.getType());
716
35.0k
      }))
717
35.0k
    return true;
718
737k
719
737k
  // Disable SROA in the face of arbitrary casts we don't whitelist elsewhere.
720
737k
  disableSROA(I.getOperand(0));
721
737k
722
737k
  // If this is a floating-point cast, and the target says this operation
723
737k
  // is expensive, this may eventually become a library call. Treat the cost
724
737k
  // as such.
725
737k
  switch (I.getOpcode()) {
726
737k
  case Instruction::FPTrunc:
727
43.8k
  case Instruction::FPExt:
728
43.8k
  case Instruction::UIToFP:
729
43.8k
  case Instruction::SIToFP:
730
43.8k
  case Instruction::FPToUI:
731
43.8k
  case Instruction::FPToSI:
732
43.8k
    if (TTI.getFPOpCost(I.getType()) == TargetTransformInfo::TCC_Expensive)
733
1.18k
      addCost(InlineConstants::CallPenalty);
734
43.8k
    break;
735
693k
  default:
736
693k
    break;
737
737k
  }
738
737k
739
737k
  return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
740
737k
}
741
742
708k
bool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) {
743
708k
  Value *Operand = I.getOperand(0);
744
708k
  if (simplifyInstruction(I, [&](SmallVectorImpl<Constant *> &COps) {
745
708k
        return ConstantFoldInstOperands(&I, COps[0], DL);
746
708k
      }))
747
0
    return true;
748
708k
749
708k
  // Disable any SROA on the argument to arbitrary unary instructions.
750
708k
  disableSROA(Operand);
751
708k
752
708k
  return false;
753
708k
}
754
755
78.4k
bool CallAnalyzer::paramHasAttr(Argument *A, Attribute::AttrKind Attr) {
756
78.4k
  return CandidateCall.paramHasAttr(A->getArgNo(), Attr);
757
78.4k
}
758
759
497k
bool CallAnalyzer::isKnownNonNullInCallee(Value *V) {
760
497k
  // Does the *call site* have the NonNull attribute set on an argument?  We
761
497k
  // use the attribute on the call site to memoize any analysis done in the
762
497k
  // caller. This will also trip if the callee function has a non-null
763
497k
  // parameter attribute, but that's a less interesting case because hopefully
764
497k
  // the callee would already have been simplified based on that.
765
497k
  if (Argument *A = dyn_cast<Argument>(V))
766
78.4k
    if (paramHasAttr(A, Attribute::NonNull))
767
45.9k
      return true;
768
451k
769
451k
  // Is this an alloca in the caller?  This is distinct from the attribute case
770
451k
  // above because attributes aren't updated within the inliner itself and we
771
451k
  // always want to catch the alloca derived case.
772
451k
  if (isAllocaDerivedArg(V))
773
216
    // We can actually predict the result of comparisons between an
774
216
    // alloca-derived value and null. Note that this fires regardless of
775
216
    // SROA firing.
776
216
    return true;
777
451k
778
451k
  return false;
779
451k
}
780
781
805k
bool CallAnalyzer::allowSizeGrowth(CallBase &Call) {
782
805k
  // If the normal destination of the invoke or the parent block of the call
783
805k
  // site is unreachable-terminated, there is little point in inlining this
784
805k
  // unless there is literally zero cost.
785
805k
  // FIXME: Note that it is possible that an unreachable-terminated block has a
786
805k
  // hot entry. For example, in below scenario inlining hot_call_X() may be
787
805k
  // beneficial :
788
805k
  // main() {
789
805k
  //   hot_call_1();
790
805k
  //   ...
791
805k
  //   hot_call_N()
792
805k
  //   exit(0);
793
805k
  // }
794
805k
  // For now, we are not handling this corner case here as it is rare in real
795
805k
  // code. In future, we should elaborate this based on BPI and BFI in more
796
805k
  // general threshold adjusting heuristics in updateThreshold().
797
805k
  if (InvokeInst *II = dyn_cast<InvokeInst>(&Call)) {
798
47.3k
    if (isa<UnreachableInst>(II->getNormalDest()->getTerminator()))
799
1.26k
      return false;
800
758k
  } else if (isa<UnreachableInst>(Call.getParent()->getTerminator()))
801
13.2k
    return false;
802
791k
803
791k
  return true;
804
791k
}
805
806
bool CallAnalyzer::isColdCallSite(CallBase &Call,
807
787k
                                  BlockFrequencyInfo *CallerBFI) {
808
787k
  // If global profile summary is available, then callsite's coldness is
809
787k
  // determined based on that.
810
787k
  if (PSI && 
PSI->hasProfileSummary()787k
)
811
46
    return PSI->isColdCallSite(CallSite(&Call), CallerBFI);
812
787k
813
787k
  // Otherwise we need BFI to be available.
814
787k
  if (!CallerBFI)
815
786k
    return false;
816
500
817
500
  // Determine if the callsite is cold relative to caller's entry. We could
818
500
  // potentially cache the computation of scaled entry frequency, but the added
819
500
  // complexity is not worth it unless this scaling shows up high in the
820
500
  // profiles.
821
500
  const BranchProbability ColdProb(ColdCallSiteRelFreq, 100);
822
500
  auto CallSiteBB = Call.getParent();
823
500
  auto CallSiteFreq = CallerBFI->getBlockFreq(CallSiteBB);
824
500
  auto CallerEntryFreq =
825
500
      CallerBFI->getBlockFreq(&(Call.getCaller()->getEntryBlock()));
826
500
  return CallSiteFreq < CallerEntryFreq * ColdProb;
827
500
}
828
829
Optional<int>
830
CallAnalyzer::getHotCallSiteThreshold(CallBase &Call,
831
787k
                                      BlockFrequencyInfo *CallerBFI) {
832
787k
833
787k
  // If global profile summary is available, then callsite's hotness is
834
787k
  // determined based on that.
835
787k
  if (PSI && 
PSI->hasProfileSummary()787k
&&
836
787k
      
PSI->isHotCallSite(CallSite(&Call), CallerBFI)59
)
837
13
    return Params.HotCallSiteThreshold;
838
787k
839
787k
  // Otherwise we need BFI to be available and to have a locally hot callsite
840
787k
  // threshold.
841
787k
  if (!CallerBFI || 
!Params.LocallyHotCallSiteThreshold513
)
842
787k
    return None;
843
7
844
7
  // Determine if the callsite is hot relative to caller's entry. We could
845
7
  // potentially cache the computation of scaled entry frequency, but the added
846
7
  // complexity is not worth it unless this scaling shows up high in the
847
7
  // profiles.
848
7
  auto CallSiteBB = Call.getParent();
849
7
  auto CallSiteFreq = CallerBFI->getBlockFreq(CallSiteBB).getFrequency();
850
7
  auto CallerEntryFreq = CallerBFI->getEntryFreq();
851
7
  if (CallSiteFreq >= CallerEntryFreq * HotCallSiteRelFreq)
852
0
    return Params.LocallyHotCallSiteThreshold;
853
7
854
7
  // Otherwise treat it normally.
855
7
  return None;
856
7
}
857
858
805k
void CallAnalyzer::updateThreshold(CallBase &Call, Function &Callee) {
859
805k
  // If no size growth is allowed for this inlining, set Threshold to 0.
860
805k
  if (!allowSizeGrowth(Call)) {
861
14.5k
    Threshold = 0;
862
14.5k
    return;
863
14.5k
  }
864
791k
865
791k
  Function *Caller = Call.getCaller();
866
791k
867
791k
  // return min(A, B) if B is valid.
868
791k
  auto MinIfValid = [](int A, Optional<int> B) {
869
3.70k
    return B ? 
std::min(A, B.getValue())3.70k
:
A4
;
870
3.70k
  };
871
791k
872
791k
  // return max(A, B) if B is valid.
873
791k
  auto MaxIfValid = [](int A, Optional<int> B) {
874
224k
    return B ? std::max(A, B.getValue()) : 
A0
;
875
224k
  };
876
791k
877
791k
  // Various bonus percentages. These are multiplied by Threshold to get the
878
791k
  // bonus values.
879
791k
  // SingleBBBonus: This bonus is applied if the callee has a single reachable
880
791k
  // basic block at the given callsite context. This is speculatively applied
881
791k
  // and withdrawn if more than one basic block is seen.
882
791k
  //
883
791k
  // LstCallToStaticBonus: This large bonus is applied to ensure the inlining
884
791k
  // of the last call to a static function as inlining such functions is
885
791k
  // guaranteed to reduce code size.
886
791k
  //
887
791k
  // These bonus percentages may be set to 0 based on properties of the caller
888
791k
  // and the callsite.
889
791k
  int SingleBBBonusPercent = 50;
890
791k
  int VectorBonusPercent = TTI.getInlinerVectorBonusPercent();
891
791k
  int LastCallToStaticBonus = InlineConstants::LastCallToStaticBonus;
892
791k
893
791k
  // Lambda to set all the above bonus and bonus percentages to 0.
894
791k
  auto DisallowAllBonuses = [&]() {
895
37
    SingleBBBonusPercent = 0;
896
37
    VectorBonusPercent = 0;
897
37
    LastCallToStaticBonus = 0;
898
37
  };
899
791k
900
791k
  // Use the OptMinSizeThreshold or OptSizeThreshold knob if they are available
901
791k
  // and reduce the threshold if the caller has the necessary attribute.
902
791k
  if (Caller->hasMinSize()) {
903
3.63k
    Threshold = MinIfValid(Threshold, Params.OptMinSizeThreshold);
904
3.63k
    // For minsize, we want to disable the single BB bonus and the vector
905
3.63k
    // bonuses, but not the last-call-to-static bonus. Inlining the last call to
906
3.63k
    // a static function will, at the minimum, eliminate the parameter setup and
907
3.63k
    // call/return instructions.
908
3.63k
    SingleBBBonusPercent = 0;
909
3.63k
    VectorBonusPercent = 0;
910
787k
  } else if (Caller->hasOptSize())
911
35
    Threshold = MinIfValid(Threshold, Params.OptSizeThreshold);
912
791k
913
791k
  // Adjust the threshold based on inlinehint attribute and profile based
914
791k
  // hotness information if the caller does not have MinSize attribute.
915
791k
  if (!Caller->hasMinSize()) {
916
787k
    if (Callee.hasFnAttribute(Attribute::InlineHint))
917
224k
      Threshold = MaxIfValid(Threshold, Params.HintThreshold);
918
787k
919
787k
    // FIXME: After switching to the new passmanager, simplify the logic below
920
787k
    // by checking only the callsite hotness/coldness as we will reliably
921
787k
    // have local profile information.
922
787k
    //
923
787k
    // Callsite hotness and coldness can be determined if sample profile is
924
787k
    // used (which adds hotness metadata to calls) or if caller's
925
787k
    // BlockFrequencyInfo is available.
926
787k
    BlockFrequencyInfo *CallerBFI = GetBFI ? 
&((*GetBFI)(*Caller))521
:
nullptr786k
;
927
787k
    auto HotCallSiteThreshold = getHotCallSiteThreshold(Call, CallerBFI);
928
787k
    if (!Caller->hasOptSize() && 
HotCallSiteThreshold787k
) {
929
13
      LLVM_DEBUG(dbgs() << "Hot callsite.\n");
930
13
      // FIXME: This should update the threshold only if it exceeds the
931
13
      // current threshold, but AutoFDO + ThinLTO currently relies on this
932
13
      // behavior to prevent inlining of hot callsites during ThinLTO
933
13
      // compile phase.
934
13
      Threshold = HotCallSiteThreshold.getValue();
935
787k
    } else if (isColdCallSite(Call, CallerBFI)) {
936
22
      LLVM_DEBUG(dbgs() << "Cold callsite.\n");
937
22
      // Do not apply bonuses for a cold callsite including the
938
22
      // LastCallToStatic bonus. While this bonus might result in code size
939
22
      // reduction, it can cause the size of a non-cold caller to increase
940
22
      // preventing it from being inlined.
941
22
      DisallowAllBonuses();
942
22
      Threshold = MinIfValid(Threshold, Params.ColdCallSiteThreshold);
943
787k
    } else if (PSI) {
944
787k
      // Use callee's global profile information only if we have no way of
945
787k
      // determining this via callsite information.
946
787k
      if (PSI->isFunctionEntryHot(&Callee)) {
947
12
        LLVM_DEBUG(dbgs() << "Hot callee.\n");
948
12
        // If callsite hotness can not be determined, we may still know
949
12
        // that the callee is hot and treat it as a weaker hint for threshold
950
12
        // increase.
951
12
        Threshold = MaxIfValid(Threshold, Params.HintThreshold);
952
786k
      } else if (PSI->isFunctionEntryCold(&Callee)) {
953
15
        LLVM_DEBUG(dbgs() << "Cold callee.\n");
954
15
        // Do not apply bonuses for a cold callee including the
955
15
        // LastCallToStatic bonus. While this bonus might result in code size
956
15
        // reduction, it can cause the size of a non-cold caller to increase
957
15
        // preventing it from being inlined.
958
15
        DisallowAllBonuses();
959
15
        Threshold = MinIfValid(Threshold, Params.ColdThreshold);
960
15
      }
961
787k
    }
962
787k
  }
963
791k
964
791k
  // Finally, take the target-specific inlining threshold multiplier into
965
791k
  // account.
966
791k
  Threshold *= TTI.getInliningThresholdMultiplier();
967
791k
968
791k
  SingleBBBonus = Threshold * SingleBBBonusPercent / 100;
969
791k
  VectorBonus = Threshold * VectorBonusPercent / 100;
970
791k
971
791k
  bool OnlyOneCallAndLocalLinkage =
972
791k
      F.hasLocalLinkage() && 
F.hasOneUse()149k
&&
&F == Call.getCalledFunction()26.3k
;
973
791k
  // If there is only one call of the function, and it has internal linkage,
974
791k
  // the cost of inlining it drops dramatically. It may seem odd to update
975
791k
  // Cost in updateThreshold, but the bonus depends on the logic in this method.
976
791k
  if (OnlyOneCallAndLocalLinkage)
977
26.1k
    Cost -= LastCallToStaticBonus;
978
791k
}
979
980
2.59M
bool CallAnalyzer::visitCmpInst(CmpInst &I) {
981
2.59M
  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
982
2.59M
  // First try to handle simplified comparisons.
983
2.59M
  if (simplifyInstruction(I, [&](SmallVectorImpl<Constant *> &COps) {
984
70.7k
        return ConstantExpr::getCompare(I.getPredicate(), COps[0], COps[1]);
985
70.7k
      }))
986
70.7k
    return true;
987
2.52M
988
2.52M
  if (I.getOpcode() == Instruction::FCmp)
989
24.8k
    return false;
990
2.50M
991
2.50M
  // Otherwise look for a comparison between constant offset pointers with
992
2.50M
  // a common base.
993
2.50M
  Value *LHSBase, *RHSBase;
994
2.50M
  APInt LHSOffset, RHSOffset;
995
2.50M
  std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
996
2.50M
  if (LHSBase) {
997
89.6k
    std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
998
89.6k
    if (RHSBase && 
LHSBase == RHSBase6.85k
) {
999
119
      // We have common bases, fold the icmp to a constant based on the
1000
119
      // offsets.
1001
119
      Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
1002
119
      Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
1003
119
      if (Constant *C = ConstantExpr::getICmp(I.getPredicate(), CLHS, CRHS)) {
1004
119
        SimplifiedValues[&I] = C;
1005
119
        ++NumConstantPtrCmps;
1006
119
        return true;
1007
119
      }
1008
2.50M
    }
1009
89.6k
  }
1010
2.50M
1011
2.50M
  // If the comparison is an equality comparison with null, we can simplify it
1012
2.50M
  // if we know the value (argument) can't be null
1013
2.50M
  if (I.isEquality() && 
isa<ConstantPointerNull>(I.getOperand(1))1.73M
&&
1014
2.50M
      
isKnownNonNullInCallee(I.getOperand(0))497k
) {
1015
46.1k
    bool IsNotEqual = I.getPredicate() == CmpInst::ICMP_NE;
1016
46.1k
    SimplifiedValues[&I] = IsNotEqual ? 
ConstantInt::getTrue(I.getType())914
1017
46.1k
                                      : 
ConstantInt::getFalse(I.getType())45.2k
;
1018
46.1k
    return true;
1019
46.1k
  }
1020
2.45M
  // Finally check for SROA candidates in comparisons.
1021
2.45M
  Value *SROAArg;
1022
2.45M
  DenseMap<Value *, int>::iterator CostIt;
1023
2.45M
  if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
1024
617
    if (isa<ConstantPointerNull>(I.getOperand(1))) {
1025
0
      accumulateSROACost(CostIt, InlineConstants::InstrCost);
1026
0
      return true;
1027
0
    }
1028
617
1029
617
    disableSROA(CostIt);
1030
617
  }
1031
2.45M
1032
2.45M
  return false;
1033
2.45M
}
1034
1035
240k
bool CallAnalyzer::visitSub(BinaryOperator &I) {
1036
240k
  // Try to handle a special case: we can fold computing the difference of two
1037
240k
  // constant-related pointers.
1038
240k
  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1039
240k
  Value *LHSBase, *RHSBase;
1040
240k
  APInt LHSOffset, RHSOffset;
1041
240k
  std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
1042
240k
  if (LHSBase) {
1043
8.76k
    std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
1044
8.76k
    if (RHSBase && 
LHSBase == RHSBase4.16k
) {
1045
56
      // We have common bases, fold the subtract to a constant based on the
1046
56
      // offsets.
1047
56
      Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
1048
56
      Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
1049
56
      if (Constant *C = ConstantExpr::getSub(CLHS, CRHS)) {
1050
56
        SimplifiedValues[&I] = C;
1051
56
        ++NumConstantPtrDiffs;
1052
56
        return true;
1053
56
      }
1054
240k
    }
1055
8.76k
  }
1056
240k
1057
240k
  // Otherwise, fall back to the generic logic for simplifying and handling
1058
240k
  // instructions.
1059
240k
  return Base::visitSub(I);
1060
240k
}
1061
1062
2.87M
bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) {
1063
2.87M
  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
1064
2.87M
  Constant *CLHS = dyn_cast<Constant>(LHS);
1065
2.87M
  if (!CLHS)
1066
2.77M
    CLHS = SimplifiedValues.lookup(LHS);
1067
2.87M
  Constant *CRHS = dyn_cast<Constant>(RHS);
1068
2.87M
  if (!CRHS)
1069
1.22M
    CRHS = SimplifiedValues.lookup(RHS);
1070
2.87M
1071
2.87M
  Value *SimpleV = nullptr;
1072
2.87M
  if (auto FI = dyn_cast<FPMathOperator>(&I))
1073
340k
    SimpleV = SimplifyFPBinOp(I.getOpcode(), CLHS ? 
CLHS18.3k
:
LHS322k
,
1074
340k
                              CRHS ? 
CRHS130k
:
RHS210k
, FI->getFastMathFlags(), DL);
1075
2.53M
  else
1076
2.53M
    SimpleV =
1077
2.53M
        SimplifyBinOp(I.getOpcode(), CLHS ? 
CLHS137k
:
LHS2.39M
, CRHS ?
CRHS1.55M
:
RHS977k
, DL);
1078
2.87M
1079
2.87M
  if (Constant *C = dyn_cast_or_null<Constant>(SimpleV))
1080
42.7k
    SimplifiedValues[&I] = C;
1081
2.87M
1082
2.87M
  if (SimpleV)
1083
48.5k
    return true;
1084
2.82M
1085
2.82M
  // Disable any SROA on arguments to arbitrary, unsimplified binary operators.
1086
2.82M
  disableSROA(LHS);
1087
2.82M
  disableSROA(RHS);
1088
2.82M
1089
2.82M
  // If the instruction is floating point, and the target says this operation
1090
2.82M
  // is expensive, this may eventually become a library call. Treat the cost
1091
2.82M
  // as such. Unless it's fneg which can be implemented with an xor.
1092
2.82M
  using namespace llvm::PatternMatch;
1093
2.82M
  if (I.getType()->isFloatingPointTy() &&
1094
2.82M
      
TTI.getFPOpCost(I.getType()) == TargetTransformInfo::TCC_Expensive339k
&&
1095
2.82M
      
!match(&I, m_FNeg(m_Value()))90
)
1096
48
    addCost(InlineConstants::CallPenalty);
1097
2.82M
1098
2.82M
  return false;
1099
2.82M
}
1100
1101
2
bool CallAnalyzer::visitFNeg(UnaryOperator &I) {
1102
2
  Value *Op = I.getOperand(0);
1103
2
  Constant *COp = dyn_cast<Constant>(Op);
1104
2
  if (!COp)
1105
2
    COp = SimplifiedValues.lookup(Op);
1106
2
1107
2
  Value *SimpleV = SimplifyFNegInst(COp ? COp : 
Op0
,
1108
2
                                    cast<FPMathOperator>(I).getFastMathFlags(),
1109
2
                                    DL);
1110
2
1111
2
  if (Constant *C = dyn_cast_or_null<Constant>(SimpleV))
1112
2
    SimplifiedValues[&I] = C;
1113
2
1114
2
  if (SimpleV)
1115
2
    return true;
1116
0
1117
0
  // Disable any SROA on arguments to arbitrary, unsimplified fneg.
1118
0
  disableSROA(Op);
1119
0
1120
0
  return false;
1121
0
}
1122
1123
3.87M
bool CallAnalyzer::visitLoad(LoadInst &I) {
1124
3.87M
  Value *SROAArg;
1125
3.87M
  DenseMap<Value *, int>::iterator CostIt;
1126
3.87M
  if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {
1127
304k
    if (I.isSimple()) {
1128
304k
      accumulateSROACost(CostIt, InlineConstants::InstrCost);
1129
304k
      return true;
1130
304k
    }
1131
65
1132
65
    disableSROA(CostIt);
1133
65
  }
1134
3.87M
1135
3.87M
  // If the data is already loaded from this address and hasn't been clobbered
1136
3.87M
  // by any stores or calls, this load is likely to be redundant and can be
1137
3.87M
  // eliminated.
1138
3.87M
  
if (3.57M
EnableLoadElimination3.57M
&&
1139
3.57M
      
!LoadAddrSet.insert(I.getPointerOperand()).second904k
&&
I.isUnordered()35.1k
) {
1140
34.9k
    LoadEliminationCost += InlineConstants::InstrCost;
1141
34.9k
    return true;
1142
34.9k
  }
1143
3.53M
1144
3.53M
  return false;
1145
3.53M
}
1146
1147
2.36M
bool CallAnalyzer::visitStore(StoreInst &I) {
1148
2.36M
  Value *SROAArg;
1149
2.36M
  DenseMap<Value *, int>::iterator CostIt;
1150
2.36M
  if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {
1151
234k
    if (I.isSimple()) {
1152
234k
      accumulateSROACost(CostIt, InlineConstants::InstrCost);
1153
234k
      return true;
1154
234k
    }
1155
58
1156
58
    disableSROA(CostIt);
1157
58
  }
1158
2.36M
1159
2.36M
  // The store can potentially clobber loads and prevent repeated loads from
1160
2.36M
  // being eliminated.
1161
2.36M
  // FIXME:
1162
2.36M
  // 1. We can probably keep an initial set of eliminatable loads substracted
1163
2.36M
  // from the cost even when we finally see a store. We just need to disable
1164
2.36M
  // *further* accumulation of elimination savings.
1165
2.36M
  // 2. We should probably at some point thread MemorySSA for the callee into
1166
2.36M
  // this and then use that to actually compute *really* precise savings.
1167
2.36M
  disableLoadElimination();
1168
2.13M
  return false;
1169
2.36M
}
1170
1171
204k
bool CallAnalyzer::visitExtractValue(ExtractValueInst &I) {
1172
204k
  // Constant folding for extract value is trivial.
1173
204k
  if (simplifyInstruction(I, [&](SmallVectorImpl<Constant *> &COps) {
1174
150
        return ConstantExpr::getExtractValue(COps[0], I.getIndices());
1175
150
      }))
1176
150
    return true;
1177
204k
1178
204k
  // SROA can look through these but give them a cost.
1179
204k
  return false;
1180
204k
}
1181
1182
72.6k
bool CallAnalyzer::visitInsertValue(InsertValueInst &I) {
1183
72.6k
  // Constant folding for insert value is trivial.
1184
72.6k
  if (simplifyInstruction(I, [&](SmallVectorImpl<Constant *> &COps) {
1185
1
        return ConstantExpr::getInsertValue(/*AggregateOperand*/ COps[0],
1186
1
                                            /*InsertedValueOperand*/ COps[1],
1187
1
                                            I.getIndices());
1188
1
      }))
1189
1
    return true;
1190
72.6k
1191
72.6k
  // SROA can look through these but give them a cost.
1192
72.6k
  return false;
1193
72.6k
}
1194
1195
/// Try to simplify a call site.
1196
///
1197
/// Takes a concrete function and callsite and tries to actually simplify it by
1198
/// analyzing the arguments and call itself with instsimplify. Returns true if
1199
/// it has simplified the callsite to some other entity (a constant), making it
1200
/// free.
1201
2.84M
bool CallAnalyzer::simplifyCallSite(Function *F, CallBase &Call) {
1202
2.84M
  // FIXME: Using the instsimplify logic directly for this is inefficient
1203
2.84M
  // because we have to continually rebuild the argument list even when no
1204
2.84M
  // simplifications can be performed. Until that is fixed with remapping
1205
2.84M
  // inside of instsimplify, directly constant fold calls here.
1206
2.84M
  if (!canConstantFoldCallTo(&Call, F))
1207
2.79M
    return false;
1208
48.0k
1209
48.0k
  // Try to re-map the arguments to constants.
1210
48.0k
  SmallVector<Constant *, 4> ConstantArgs;
1211
48.0k
  ConstantArgs.reserve(Call.arg_size());
1212
49.5k
  for (Value *I : Call.args()) {
1213
49.5k
    Constant *C = dyn_cast<Constant>(I);
1214
49.5k
    if (!C)
1215
48.0k
      C = dyn_cast_or_null<Constant>(SimplifiedValues.lookup(I));
1216
49.5k
    if (!C)
1217
47.2k
      return false; // This argument doesn't map to a constant.
1218
2.36k
1219
2.36k
    ConstantArgs.push_back(C);
1220
2.36k
  }
1221
48.0k
  
if (Constant *817
C817
= ConstantFoldCall(&Call, F, ConstantArgs)) {
1222
817
    SimplifiedValues[&Call] = C;
1223
817
    return true;
1224
817
  }
1225
0
1226
0
  return false;
1227
0
}
1228
1229
2.97M
bool CallAnalyzer::visitCallBase(CallBase &Call) {
1230
2.97M
  if (Call.hasFnAttr(Attribute::ReturnsTwice) &&
1231
2.97M
      
!F.hasFnAttribute(Attribute::ReturnsTwice)18
) {
1232
14
    // This aborts the entire analysis.
1233
14
    ExposesReturnsTwice = true;
1234
14
    return false;
1235
14
  }
1236
2.97M
  if (isa<CallInst>(Call) && 
cast<CallInst>(Call).cannotDuplicate()2.76M
)
1237
11
    ContainsNoDuplicateCall = true;
1238
2.97M
1239
2.97M
  if (Function *F = Call.getCalledFunction()) {
1240
2.84M
    // When we have a concrete function, first try to simplify it directly.
1241
2.84M
    if (simplifyCallSite(F, Call))
1242
817
      return true;
1243
2.84M
1244
2.84M
    // Next check if it is an intrinsic we know about.
1245
2.84M
    // FIXME: Lift this into part of the InstVisitor.
1246
2.84M
    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&Call)) {
1247
751k
      switch (II->getIntrinsicID()) {
1248
751k
      default:
1249
586k
        if (!Call.onlyReadsMemory() && 
!isAssumeLikeIntrinsic(II)502k
)
1250
3.88k
          disableLoadElimination();
1251
586k
        return Base::visitCallBase(Call);
1252
751k
1253
751k
      case Intrinsic::load_relative:
1254
0
        // This is normally lowered to 4 LLVM instructions.
1255
0
        addCost(3 * InlineConstants::InstrCost);
1256
0
        return false;
1257
751k
1258
751k
      case Intrinsic::memset:
1259
163k
      case Intrinsic::memcpy:
1260
163k
      case Intrinsic::memmove:
1261
163k
        disableLoadElimination();
1262
163k
        // SROA can usually chew through these intrinsics, but they aren't free.
1263
163k
        return false;
1264
163k
      case Intrinsic::icall_branch_funnel:
1265
5
      case Intrinsic::localescape:
1266
5
        HasUninlineableIntrinsic = true;
1267
5
        return false;
1268
2.42k
      case Intrinsic::vastart:
1269
2.42k
        InitsVargArgs = true;
1270
2.42k
        return false;
1271
2.08M
      }
1272
2.08M
    }
1273
2.08M
1274
2.08M
    if (F == Call.getFunction()) {
1275
12.6k
      // This flag will fully abort the analysis, so don't bother with anything
1276
12.6k
      // else.
1277
12.6k
      IsRecursiveCall = true;
1278
12.6k
      return false;
1279
12.6k
    }
1280
2.07M
1281
2.07M
    if (TTI.isLoweredToCall(F)) {
1282
2.07M
      // We account for the average 1 instruction per call argument setup
1283
2.07M
      // here.
1284
2.07M
      addCost(Call.arg_size() * InlineConstants::InstrCost);
1285
2.07M
1286
2.07M
      // Everything other than inline ASM will also have a significant cost
1287
2.07M
      // merely from making the call.
1288
2.07M
      if (!isa<InlineAsm>(Call.getCalledValue()))
1289
2.07M
        addCost(InlineConstants::CallPenalty);
1290
2.07M
    }
1291
2.07M
1292
2.07M
    if (!Call.onlyReadsMemory())
1293
1.93M
      disableLoadElimination();
1294
2.07M
    return Base::visitCallBase(Call);
1295
2.07M
  }
1296
133k
1297
133k
  // Otherwise we're in a very special case -- an indirect function call. See
1298
133k
  // if we can be particularly clever about this.
1299
133k
  Value *Callee = Call.getCalledValue();
1300
133k
1301
133k
  // First, pay the price of the argument setup. We account for the average
1302
133k
  // 1 instruction per call argument setup here.
1303
133k
  addCost(Call.arg_size() * InlineConstants::InstrCost);
1304
133k
1305
133k
  // Next, check if this happens to be an indirect function call to a known
1306
133k
  // function in this inline context. If not, we've done all we can.
1307
133k
  Function *F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee));
1308
133k
  if (!F) {
1309
131k
    if (!Call.onlyReadsMemory())
1310
131k
      disableLoadElimination();
1311
131k
    return Base::visitCallBase(Call);
1312
131k
  }
1313
2.19k
1314
2.19k
  // If we have a constant that we are calling as a function, we can peer
1315
2.19k
  // through it and see the function target. This happens not infrequently
1316
2.19k
  // during devirtualization and so we want to give it a hefty bonus for
1317
2.19k
  // inlining, but cap that bonus in the event that inlining wouldn't pan
1318
2.19k
  // out. Pretend to inline the function, with a custom threshold.
1319
2.19k
  auto IndirectCallParams = Params;
1320
2.19k
  IndirectCallParams.DefaultThreshold = InlineConstants::IndirectCallThreshold;
1321
2.19k
  CallAnalyzer CA(TTI, GetAssumptionCache, GetBFI, PSI, ORE, *F, Call,
1322
2.19k
                  IndirectCallParams);
1323
2.19k
  if (CA.analyzeCall(Call)) {
1324
1.97k
    // We were able to inline the indirect call! Subtract the cost from the
1325
1.97k
    // threshold to get the bonus we want to apply, but don't go below zero.
1326
1.97k
    Cost -= std::max(0, CA.getThreshold() - CA.getCost());
1327
1.97k
  }
1328
2.19k
1329
2.19k
  if (!F->onlyReadsMemory())
1330
1.97k
    disableLoadElimination();
1331
2.19k
  return Base::visitCallBase(Call);
1332
2.19k
}
1333
1334
766k
bool CallAnalyzer::visitReturnInst(ReturnInst &RI) {
1335
766k
  // At least one return instruction will be free after inlining.
1336
766k
  bool Free = !HasReturn;
1337
766k
  HasReturn = true;
1338
766k
  return Free;
1339
766k
}
1340
1341
3.79M
bool CallAnalyzer::visitBranchInst(BranchInst &BI) {
1342
3.79M
  // We model unconditional branches as essentially free -- they really
1343
3.79M
  // shouldn't exist at all, but handling them makes the behavior of the
1344
3.79M
  // inliner more regular and predictable. Interestingly, conditional branches
1345
3.79M
  // which will fold away are also free.
1346
3.79M
  return BI.isUnconditional() || 
isa<ConstantInt>(BI.getCondition())2.35M
||
1347
3.79M
         dyn_cast_or_null<ConstantInt>(
1348
2.34M
             SimplifiedValues.lookup(BI.getCondition()));
1349
3.79M
}
1350
1351
164k
bool CallAnalyzer::visitSelectInst(SelectInst &SI) {
1352
164k
  bool CheckSROA = SI.getType()->isPointerTy();
1353
164k
  Value *TrueVal = SI.getTrueValue();
1354
164k
  Value *FalseVal = SI.getFalseValue();
1355
164k
1356
164k
  Constant *TrueC = dyn_cast<Constant>(TrueVal);
1357
164k
  if (!TrueC)
1358
100k
    TrueC = SimplifiedValues.lookup(TrueVal);
1359
164k
  Constant *FalseC = dyn_cast<Constant>(FalseVal);
1360
164k
  if (!FalseC)
1361
121k
    FalseC = SimplifiedValues.lookup(FalseVal);
1362
164k
  Constant *CondC =
1363
164k
      dyn_cast_or_null<Constant>(SimplifiedValues.lookup(SI.getCondition()));
1364
164k
1365
164k
  if (!CondC) {
1366
152k
    // Select C, X, X => X
1367
152k
    if (TrueC == FalseC && 
TrueC76.6k
) {
1368
8
      SimplifiedValues[&SI] = TrueC;
1369
8
      return true;
1370
8
    }
1371
152k
1372
152k
    if (!CheckSROA)
1373
112k
      return Base::visitSelectInst(SI);
1374
39.9k
1375
39.9k
    std::pair<Value *, APInt> TrueBaseAndOffset =
1376
39.9k
        ConstantOffsetPtrs.lookup(TrueVal);
1377
39.9k
    std::pair<Value *, APInt> FalseBaseAndOffset =
1378
39.9k
        ConstantOffsetPtrs.lookup(FalseVal);
1379
39.9k
    if (TrueBaseAndOffset == FalseBaseAndOffset && 
TrueBaseAndOffset.first20.8k
) {
1380
1
      ConstantOffsetPtrs[&SI] = TrueBaseAndOffset;
1381
1
1382
1
      Value *SROAArg;
1383
1
      DenseMap<Value *, int>::iterator CostIt;
1384
1
      if (lookupSROAArgAndCost(TrueVal, SROAArg, CostIt))
1385
1
        SROAArgValues[&SI] = SROAArg;
1386
1
      return true;
1387
1
    }
1388
39.9k
1389
39.9k
    return Base::visitSelectInst(SI);
1390
39.9k
  }
1391
11.6k
1392
11.6k
  // Select condition is a constant.
1393
11.6k
  Value *SelectedV = CondC->isAllOnesValue()
1394
11.6k
                         ? 
TrueVal2.46k
1395
11.6k
                         : 
(CondC->isNullValue()) 9.19k
?
FalseVal9.19k
:
nullptr2
;
1396
11.6k
  if (!SelectedV) {
1397
2
    // Condition is a vector constant that is not all 1s or all 0s.  If all
1398
2
    // operands are constants, ConstantExpr::getSelect() can handle the cases
1399
2
    // such as select vectors.
1400
2
    if (TrueC && 
FalseC1
) {
1401
1
      if (auto *C = ConstantExpr::getSelect(CondC, TrueC, FalseC)) {
1402
1
        SimplifiedValues[&SI] = C;
1403
1
        return true;
1404
1
      }
1405
1
    }
1406
1
    return Base::visitSelectInst(SI);
1407
1
  }
1408
11.6k
1409
11.6k
  // Condition is either all 1s or all 0s. SI can be simplified.
1410
11.6k
  if (Constant *SelectedC = dyn_cast<Constant>(SelectedV)) {
1411
3.09k
    SimplifiedValues[&SI] = SelectedC;
1412
3.09k
    return true;
1413
3.09k
  }
1414
8.56k
1415
8.56k
  if (!CheckSROA)
1416
8.10k
    return true;
1417
458
1418
458
  std::pair<Value *, APInt> BaseAndOffset =
1419
458
      ConstantOffsetPtrs.lookup(SelectedV);
1420
458
  if (BaseAndOffset.first) {
1421
216
    ConstantOffsetPtrs[&SI] = BaseAndOffset;
1422
216
1423
216
    Value *SROAArg;
1424
216
    DenseMap<Value *, int>::iterator CostIt;
1425
216
    if (lookupSROAArgAndCost(SelectedV, SROAArg, CostIt))
1426
19
      SROAArgValues[&SI] = SROAArg;
1427
216
  }
1428
458
1429
458
  return true;
1430
458
}
1431
1432
48.6k
bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
1433
48.6k
  // We model unconditional switches as free, see the comments on handling
1434
48.6k
  // branches.
1435
48.6k
  if (isa<ConstantInt>(SI.getCondition()))
1436
0
    return true;
1437
48.6k
  if (Value *V = SimplifiedValues.lookup(SI.getCondition()))
1438
16.9k
    if (isa<ConstantInt>(V))
1439
16.9k
      return true;
1440
31.6k
1441
31.6k
  // Assume the most general case where the switch is lowered into
1442
31.6k
  // either a jump table, bit test, or a balanced binary tree consisting of
1443
31.6k
  // case clusters without merging adjacent clusters with the same
1444
31.6k
  // destination. We do not consider the switches that are lowered with a mix
1445
31.6k
  // of jump table/bit test/binary search tree. The cost of the switch is
1446
31.6k
  // proportional to the size of the tree or the size of jump table range.
1447
31.6k
  //
1448
31.6k
  // NB: We convert large switches which are just used to initialize large phi
1449
31.6k
  // nodes to lookup tables instead in simplify-cfg, so this shouldn't prevent
1450
31.6k
  // inlining those. It will prevent inlining in cases where the optimization
1451
31.6k
  // does not (yet) fire.
1452
31.6k
1453
31.6k
  // Maximum valid cost increased in this function.
1454
31.6k
  int CostUpperBound = INT_MAX - InlineConstants::InstrCost - 1;
1455
31.6k
1456
31.6k
  // Exit early for a large switch, assuming one case needs at least one
1457
31.6k
  // instruction.
1458
31.6k
  // FIXME: This is not true for a bit test, but ignore such case for now to
1459
31.6k
  // save compile-time.
1460
31.6k
  int64_t CostLowerBound =
1461
31.6k
      std::min((int64_t)CostUpperBound,
1462
31.6k
               (int64_t)SI.getNumCases() * InlineConstants::InstrCost + Cost);
1463
31.6k
1464
31.6k
  if (CostLowerBound > Threshold && 
!ComputeFullInlineCost214
) {
1465
214
    addCost((int64_t)SI.getNumCases() * InlineConstants::InstrCost);
1466
214
    return false;
1467
214
  }
1468
31.4k
1469
31.4k
  unsigned JumpTableSize = 0;
1470
31.4k
  unsigned NumCaseCluster =
1471
31.4k
      TTI.getEstimatedNumberOfCaseClusters(SI, JumpTableSize);
1472
31.4k
1473
31.4k
  // If suitable for a jump table, consider the cost for the table size and
1474
31.4k
  // branch to destination.
1475
31.4k
  if (JumpTableSize) {
1476
8.59k
    int64_t JTCost = (int64_t)JumpTableSize * InlineConstants::InstrCost +
1477
8.59k
                     4 * InlineConstants::InstrCost;
1478
8.59k
1479
8.59k
    addCost(JTCost, (int64_t)CostUpperBound);
1480
8.59k
    return false;
1481
8.59k
  }
1482
22.8k
1483
22.8k
  // Considering forming a binary search, we should find the number of nodes
1484
22.8k
  // which is same as the number of comparisons when lowered. For a given
1485
22.8k
  // number of clusters, n, we can define a recursive function, f(n), to find
1486
22.8k
  // the number of nodes in the tree. The recursion is :
1487
22.8k
  // f(n) = 1 + f(n/2) + f (n - n/2), when n > 3,
1488
22.8k
  // and f(n) = n, when n <= 3.
1489
22.8k
  // This will lead a binary tree where the leaf should be either f(2) or f(3)
1490
22.8k
  // when n > 3.  So, the number of comparisons from leaves should be n, while
1491
22.8k
  // the number of non-leaf should be :
1492
22.8k
  //   2^(log2(n) - 1) - 1
1493
22.8k
  //   = 2^log2(n) * 2^-1 - 1
1494
22.8k
  //   = n / 2 - 1.
1495
22.8k
  // Considering comparisons from leaf and non-leaf nodes, we can estimate the
1496
22.8k
  // number of comparisons in a simple closed form :
1497
22.8k
  //   n + n / 2 - 1 = n * 3 / 2 - 1
1498
22.8k
  if (NumCaseCluster <= 3) {
1499
20.9k
    // Suppose a comparison includes one compare and one conditional branch.
1500
20.9k
    addCost(NumCaseCluster * 2 * InlineConstants::InstrCost);
1501
20.9k
    return false;
1502
20.9k
  }
1503
1.90k
1504
1.90k
  int64_t ExpectedNumberOfCompare = 3 * (int64_t)NumCaseCluster / 2 - 1;
1505
1.90k
  int64_t SwitchCost =
1506
1.90k
      ExpectedNumberOfCompare * 2 * InlineConstants::InstrCost;
1507
1.90k
1508
1.90k
  addCost(SwitchCost, (int64_t)CostUpperBound);
1509
1.90k
  return false;
1510
1.90k
}
1511
1512
0
bool CallAnalyzer::visitIndirectBrInst(IndirectBrInst &IBI) {
1513
0
  // We never want to inline functions that contain an indirectbr.  This is
1514
0
  // incorrect because all the blockaddress's (in static global initializers
1515
0
  // for example) would be referring to the original function, and this
1516
0
  // indirect jump would jump from the inlined copy of the function into the
1517
0
  // original function which is extremely undefined behavior.
1518
0
  // FIXME: This logic isn't really right; we can safely inline functions with
1519
0
  // indirectbr's as long as no other function or global references the
1520
0
  // blockaddress of a block within the current function.
1521
0
  HasIndirectBr = true;
1522
0
  return false;
1523
0
}
1524
1525
30.8k
bool CallAnalyzer::visitResumeInst(ResumeInst &RI) {
1526
30.8k
  // FIXME: It's not clear that a single instruction is an accurate model for
1527
30.8k
  // the inline cost of a resume instruction.
1528
30.8k
  return false;
1529
30.8k
}
1530
1531
4
bool CallAnalyzer::visitCleanupReturnInst(CleanupReturnInst &CRI) {
1532
4
  // FIXME: It's not clear that a single instruction is an accurate model for
1533
4
  // the inline cost of a cleanupret instruction.
1534
4
  return false;
1535
4
}
1536
1537
0
bool CallAnalyzer::visitCatchReturnInst(CatchReturnInst &CRI) {
1538
0
  // FIXME: It's not clear that a single instruction is an accurate model for
1539
0
  // the inline cost of a catchret instruction.
1540
0
  return false;
1541
0
}
1542
1543
184k
bool CallAnalyzer::visitUnreachableInst(UnreachableInst &I) {
1544
184k
  // FIXME: It might be reasonably to discount the cost of instructions leading
1545
184k
  // to unreachable as they have the lowest possible impact on both runtime and
1546
184k
  // code size.
1547
184k
  return true; // No actual code is needed for unreachable.
1548
184k
}
1549
1550
3.11M
bool CallAnalyzer::visitInstruction(Instruction &I) {
1551
3.11M
  // Some instructions are free. All of the free intrinsics can also be
1552
3.11M
  // handled by SROA, etc.
1553
3.11M
  if (TargetTransformInfo::TCC_Free == TTI.getUserCost(&I))
1554
515k
    return true;
1555
2.59M
1556
2.59M
  // We found something we don't understand or can't handle. Mark any SROA-able
1557
2.59M
  // values in the operand list as no longer viable.
1558
10.2M
  
for (User::op_iterator OI = I.op_begin(), OE = I.op_end(); 2.59M
OI != OE;
++OI7.65M
)
1559
7.65M
    disableSROA(*OI);
1560
2.59M
1561
2.59M
  return false;
1562
2.59M
}
1563
1564
/// Analyze a basic block for its contribution to the inline cost.
1565
///
1566
/// This method walks the analyzer over every instruction in the given basic
1567
/// block and accounts for their cost during inlining at this callsite. It
1568
/// aborts early if the threshold has been exceeded or an impossible to inline
1569
/// construct has been detected. It returns false if inlining is no longer
1570
/// viable, and true if inlining remains viable.
1571
InlineResult
1572
CallAnalyzer::analyzeBlock(BasicBlock *BB,
1573
5.12M
                           SmallPtrSetImpl<const Value *> &EphValues) {
1574
35.0M
  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; 
++I29.9M
) {
1575
30.0M
    // FIXME: Currently, the number of instructions in a function regardless of
1576
30.0M
    // our ability to simplify them during inline to constants or dead code,
1577
30.0M
    // are actually used by the vector bonus heuristic. As long as that's true,
1578
30.0M
    // we have to special case debug intrinsics here to prevent differences in
1579
30.0M
    // inlining due to debug symbols. Eventually, the number of unsimplified
1580
30.0M
    // instructions shouldn't factor into the cost computation, but until then,
1581
30.0M
    // hack around it here.
1582
30.0M
    if (isa<DbgInfoIntrinsic>(I))
1583
44
      continue;
1584
30.0M
1585
30.0M
    // Skip ephemeral values.
1586
30.0M
    if (EphValues.count(&*I))
1587
7
      continue;
1588
30.0M
1589
30.0M
    ++NumInstructions;
1590
30.0M
    if (isa<ExtractElementInst>(I) || 
I->getType()->isVectorTy()30.0M
)
1591
8.53k
      ++NumVectorInstructions;
1592
30.0M
1593
30.0M
    // If the instruction simplified to a constant, there is no cost to this
1594
30.0M
    // instruction. Visit the instructions using our InstVisitor to account for
1595
30.0M
    // all of the per-instruction logic. The visit tree returns true if we
1596
30.0M
    // consumed the instruction in any way, and false if the instruction's base
1597
30.0M
    // cost should count against inlining.
1598
30.0M
    if (Base::visit(&*I))
1599
12.5M
      ++NumInstructionsSimplified;
1600
17.5M
    else
1601
17.5M
      addCost(InlineConstants::InstrCost);
1602
30.0M
1603
30.0M
    using namespace ore;
1604
30.0M
    // If the visit this instruction detected an uninlinable pattern, abort.
1605
30.0M
    InlineResult IR;
1606
30.0M
    if (IsRecursiveCall)
1607
12.6k
      IR = "recursive";
1608
30.0M
    else if (ExposesReturnsTwice)
1609
14
      IR = "exposes returns twice";
1610
30.0M
    else if (HasDynamicAlloca)
1611
299
      IR = "dynamic alloca";
1612
30.0M
    else if (HasIndirectBr)
1613
0
      IR = "indirect branch";
1614
30.0M
    else if (HasUninlineableIntrinsic)
1615
5
      IR = "uninlinable intrinsic";
1616
30.0M
    else if (InitsVargArgs)
1617
2.42k
      IR = "varargs";
1618
30.0M
    if (!IR) {
1619
15.4k
      if (ORE)
1620
0
        ORE->emit([&]() {
1621
0
          return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline",
1622
0
                                          &CandidateCall)
1623
0
                 << NV("Callee", &F) << " has uninlinable pattern ("
1624
0
                 << NV("InlineResult", IR.message)
1625
0
                 << ") and cost is not fully computed";
1626
0
        });
1627
15.4k
      return IR;
1628
15.4k
    }
1629
30.0M
1630
30.0M
    // If the caller is a recursive function then we don't want to inline
1631
30.0M
    // functions which allocate a lot of stack space because it would increase
1632
30.0M
    // the caller stack usage dramatically.
1633
30.0M
    if (IsCallerRecursive &&
1634
30.0M
        
AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller1.07M
) {
1635
76
      InlineResult IR = "recursive and allocates too much stack space";
1636
76
      if (ORE)
1637
0
        ORE->emit([&]() {
1638
0
          return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline",
1639
0
                                          &CandidateCall)
1640
0
                 << NV("Callee", &F) << " is " << NV("InlineResult", IR.message)
1641
0
                 << ". Cost is not fully computed";
1642
0
        });
1643
76
      return IR;
1644
76
    }
1645
30.0M
1646
30.0M
    // Check if we've passed the maximum possible threshold so we don't spin in
1647
30.0M
    // huge basic blocks that will never inline.
1648
30.0M
    if (Cost >= Threshold && 
!ComputeFullInlineCost92.0k
)
1649
92.0k
      return false;
1650
30.0M
  }
1651
5.12M
1652
5.12M
  
return true5.02M
;
1653
5.12M
}
1654
1655
/// Compute the base pointer and cumulative constant offsets for V.
1656
///
1657
/// This strips all constant offsets off of V, leaving it the base pointer, and
1658
/// accumulates the total constant offset applied in the returned constant. It
1659
/// returns 0 if V is not a pointer, and returns the constant '0' if there are
1660
/// no constant offsets applied.
1661
1.61M
ConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) {
1662
1.61M
  if (!V->getType()->isPointerTy())
1663
443k
    return nullptr;
1664
1.17M
1665
1.17M
  unsigned AS = V->getType()->getPointerAddressSpace();
1666
1.17M
  unsigned IntPtrWidth = DL.getIndexSizeInBits(AS);
1667
1.17M
  APInt Offset = APInt::getNullValue(IntPtrWidth);
1668
1.17M
1669
1.17M
  // Even though we don't look through PHI nodes, we could be called on an
1670
1.17M
  // instruction in an unreachable block, which may be on a cycle.
1671
1.17M
  SmallPtrSet<Value *, 4> Visited;
1672
1.17M
  Visited.insert(V);
1673
1.51M
  do {
1674
1.51M
    if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
1675
317k
      if (!GEP->isInBounds() || 
!accumulateGEPOffset(*GEP, Offset)317k
)
1676
28.6k
        return nullptr;
1677
288k
      V = GEP->getPointerOperand();
1678
1.19M
    } else if (Operator::getOpcode(V) == Instruction::BitCast) {
1679
57.1k
      V = cast<Operator>(V)->getOperand(0);
1680
1.14M
    } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
1681
0
      if (GA->isInterposable())
1682
0
        break;
1683
0
      V = GA->getAliasee();
1684
1.14M
    } else {
1685
1.14M
      break;
1686
1.14M
    }
1687
346k
    assert(V->getType()->isPointerTy() && "Unexpected operand type!");
1688
346k
  } while (Visited.insert(V).second);
1689
1.17M
1690
1.17M
  Type *IntPtrTy = DL.getIntPtrType(V->getContext(), AS);
1691
1.14M
  return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset));
1692
1.17M
}
1693
1694
/// Find dead blocks due to deleted CFG edges during inlining.
1695
///
1696
/// If we know the successor of the current block, \p CurrBB, has to be \p
1697
/// NextBB, the other successors of \p CurrBB are dead if these successors have
1698
/// no live incoming CFG edges.  If one block is found to be dead, we can
1699
/// continue growing the dead block list by checking the successors of the dead
1700
/// blocks to see if all their incoming edges are dead or not.
1701
126k
void CallAnalyzer::findDeadBlocks(BasicBlock *CurrBB, BasicBlock *NextBB) {
1702
675k
  auto IsEdgeDead = [&](BasicBlock *Pred, BasicBlock *Succ) {
1703
675k
    // A CFG edge is dead if the predecessor is dead or the predecessor has a
1704
675k
    // known successor which is not the one under exam.
1705
675k
    return (DeadBlocks.count(Pred) ||
1706
675k
            
(382k
KnownSuccessors[Pred]382k
&&
KnownSuccessors[Pred] != Succ164k
));
1707
675k
  };
1708
126k
1709
433k
  auto IsNewlyDead = [&](BasicBlock *BB) {
1710
433k
    // If all the edges to a block are dead, the block is also dead.
1711
433k
    return (!DeadBlocks.count(BB) &&
1712
433k
            llvm::all_of(predecessors(BB),
1713
675k
                         [&](BasicBlock *P) { return IsEdgeDead(P, BB); }));
1714
433k
  };
1715
126k
1716
298k
  for (BasicBlock *Succ : successors(CurrBB)) {
1717
298k
    if (Succ == NextBB || 
!IsNewlyDead(Succ)171k
)
1718
185k
      continue;
1719
112k
    SmallVector<BasicBlock *, 4> NewDead;
1720
112k
    NewDead.push_back(Succ);
1721
314k
    while (!NewDead.empty()) {
1722
201k
      BasicBlock *Dead = NewDead.pop_back_val();
1723
201k
      if (DeadBlocks.insert(Dead))
1724
201k
        // Continue growing the dead block lists.
1725
201k
        for (BasicBlock *S : successors(Dead))
1726
261k
          if (IsNewlyDead(S))
1727
88.8k
            NewDead.push_back(S);
1728
201k
    }
1729
112k
  }
1730
126k
}
1731
1732
/// Analyze a call site for potential inlining.
1733
///
1734
/// Returns true if inlining this call is viable, and false if it is not
1735
/// viable. It computes the cost and adjusts the threshold based on numerous
1736
/// factors and heuristics. If this method returns false but the computed cost
1737
/// is below the computed threshold, then inlining was forcibly disabled by
1738
/// some artifact of the routine.
1739
805k
InlineResult CallAnalyzer::analyzeCall(CallBase &Call) {
1740
805k
  ++NumCallsAnalyzed;
1741
805k
1742
805k
  // Perform some tweaks to the cost and threshold based on the direct
1743
805k
  // callsite information.
1744
805k
1745
805k
  // We want to more aggressively inline vector-dense kernels, so up the
1746
805k
  // threshold, and we'll lower it if the % of vector instructions gets too
1747
805k
  // low. Note that these bonuses are some what arbitrary and evolved over time
1748
805k
  // by accident as much as because they are principled bonuses.
1749
805k
  //
1750
805k
  // FIXME: It would be nice to remove all such bonuses. At least it would be
1751
805k
  // nice to base the bonus values on something more scientific.
1752
805k
  assert(NumInstructions == 0);
1753
805k
  assert(NumVectorInstructions == 0);
1754
805k
1755
805k
  // Update the threshold based on callsite properties
1756
805k
  updateThreshold(Call, F);
1757
805k
1758
805k
  // While Threshold depends on commandline options that can take negative
1759
805k
  // values, we want to enforce the invariant that the computed threshold and
1760
805k
  // bonuses are non-negative.
1761
805k
  assert(Threshold >= 0);
1762
805k
  assert(SingleBBBonus >= 0);
1763
805k
  assert(VectorBonus >= 0);
1764
805k
1765
805k
  // Speculatively apply all possible bonuses to Threshold. If cost exceeds
1766
805k
  // this Threshold any time, and cost cannot decrease, we can stop processing
1767
805k
  // the rest of the function body.
1768
805k
  Threshold += (SingleBBBonus + VectorBonus);
1769
805k
1770
805k
  // Give out bonuses for the callsite, as the instructions setting them up
1771
805k
  // will be gone after inlining.
1772
805k
  addCost(-getCallsiteCost(Call, DL));
1773
805k
1774
805k
  // If this function uses the coldcc calling convention, prefer not to inline
1775
805k
  // it.
1776
805k
  if (F.getCallingConv() == CallingConv::Cold)
1777
11
    Cost += InlineConstants::ColdccPenalty;
1778
805k
1779
805k
  // Check if we're done. This can happen due to bonuses and penalties.
1780
805k
  if (Cost >= Threshold && 
!ComputeFullInlineCost3
)
1781
3
    return "high cost";
1782
805k
1783
805k
  if (F.empty())
1784
60
    return true;
1785
805k
1786
805k
  Function *Caller = Call.getFunction();
1787
805k
  // Check if the caller function is recursive itself.
1788
1.40M
  for (User *U : Caller->users()) {
1789
1.40M
    CallBase *Call = dyn_cast<CallBase>(U);
1790
1.40M
    if (Call && 
Call->getFunction() == Caller1.31M
) {
1791
19.4k
      IsCallerRecursive = true;
1792
19.4k
      break;
1793
19.4k
    }
1794
1.40M
  }
1795
805k
1796
805k
  // Populate our simplified values by mapping from function arguments to call
1797
805k
  // arguments with known important simplifications.
1798
805k
  auto CAI = Call.arg_begin();
1799
805k
  for (Function::arg_iterator FAI = F.arg_begin(), FAE = F.arg_end();
1800
2.41M
       FAI != FAE; 
++FAI, ++CAI1.61M
) {
1801
1.61M
    assert(CAI != Call.arg_end());
1802
1.61M
    if (Constant *C = dyn_cast<Constant>(CAI))
1803
254k
      SimplifiedValues[&*FAI] = C;
1804
1.61M
1805
1.61M
    Value *PtrArg = *CAI;
1806
1.61M
    if (ConstantInt *C = stripAndComputeInBoundsConstantOffsets(PtrArg)) {
1807
1.14M
      ConstantOffsetPtrs[&*FAI] = std::make_pair(PtrArg, C->getValue());
1808
1.14M
1809
1.14M
      // We can SROA any pointer arguments derived from alloca instructions.
1810
1.14M
      if (isa<AllocaInst>(PtrArg)) {
1811
237k
        SROAArgValues[&*FAI] = PtrArg;
1812
237k
        SROAArgCosts[PtrArg] = 0;
1813
237k
      }
1814
1.14M
    }
1815
1.61M
  }
1816
805k
  NumConstantArgs = SimplifiedValues.size();
1817
805k
  NumConstantOffsetPtrArgs = ConstantOffsetPtrs.size();
1818
805k
  NumAllocaArgs = SROAArgValues.size();
1819
805k
1820
805k
  // FIXME: If a caller has multiple calls to a callee, we end up recomputing
1821
805k
  // the ephemeral values multiple times (and they're completely determined by
1822
805k
  // the callee, so this is purely duplicate work).
1823
805k
  SmallPtrSet<const Value *, 32> EphValues;
1824
805k
  CodeMetrics::collectEphemeralValues(&F, &GetAssumptionCache(F), EphValues);
1825
805k
1826
805k
  // The worklist of live basic blocks in the callee *after* inlining. We avoid
1827
805k
  // adding basic blocks of the callee which can be proven to be dead for this
1828
805k
  // particular call site in order to get more accurate cost estimates. This
1829
805k
  // requires a somewhat heavyweight iteration pattern: we need to walk the
1830
805k
  // basic blocks in a breadth-first order as we insert live successors. To
1831
805k
  // accomplish this, prioritizing for small iterations because we exit after
1832
805k
  // crossing our threshold, we use a small-size optimized SetVector.
1833
805k
  typedef SetVector<BasicBlock *, SmallVector<BasicBlock *, 16>,
1834
805k
                    SmallPtrSet<BasicBlock *, 16>>
1835
805k
      BBSetVector;
1836
805k
  BBSetVector BBWorklist;
1837
805k
  BBWorklist.insert(&F.getEntryBlock());
1838
805k
  bool SingleBB = true;
1839
805k
  // Note that we *must not* cache the size, this loop grows the worklist.
1840
5.82M
  for (unsigned Idx = 0; Idx != BBWorklist.size(); 
++Idx5.02M
) {
1841
5.12M
    // Bail out the moment we cross the threshold. This means we'll under-count
1842
5.12M
    // the cost, but only when undercounting doesn't matter.
1843
5.12M
    if (Cost >= Threshold && 
!ComputeFullInlineCost341
)
1844
341
      break;
1845
5.12M
1846
5.12M
    BasicBlock *BB = BBWorklist[Idx];
1847
5.12M
    if (BB->empty())
1848
0
      continue;
1849
5.12M
1850
5.12M
    // Disallow inlining a blockaddress with uses other than strictly callbr.
1851
5.12M
    // A blockaddress only has defined behavior for an indirect branch in the
1852
5.12M
    // same function, and we do not currently support inlining indirect
1853
5.12M
    // branches.  But, the inliner may not see an indirect branch that ends up
1854
5.12M
    // being dead code at a particular call site. If the blockaddress escapes
1855
5.12M
    // the function, e.g., via a global variable, inlining may lead to an
1856
5.12M
    // invalid cross-function reference.
1857
5.12M
    // FIXME: pr/39560: continue relaxing this overt restriction.
1858
5.12M
    if (BB->hasAddressTaken())
1859
10
      for (User *U : BlockAddress::get(&*BB)->users())
1860
14
        if (!isa<CallBrInst>(*U))
1861
6
          return "blockaddress used outside of callbr";
1862
5.12M
1863
5.12M
    // Analyze the cost of this block. If we blow through the threshold, this
1864
5.12M
    // returns false, and we can bail on out.
1865
5.12M
    InlineResult IR = analyzeBlock(BB, EphValues);
1866
5.12M
    if (!IR)
1867
107k
      return IR;
1868
5.02M
1869
5.02M
    Instruction *TI = BB->getTerminator();
1870
5.02M
1871
5.02M
    // Add in the live successors by first checking whether we have terminator
1872
5.02M
    // that may be simplified based on the values simplified by this call.
1873
5.02M
    if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1874
3.79M
      if (BI->isConditional()) {
1875
2.34M
        Value *Cond = BI->getCondition();
1876
2.34M
        if (ConstantInt *SimpleCond =
1877
109k
                dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
1878
109k
          BasicBlock *NextBB = BI->getSuccessor(SimpleCond->isZero() ? 
178.0k
:
031.6k
);
1879
109k
          BBWorklist.insert(NextBB);
1880
109k
          KnownSuccessors[BB] = NextBB;
1881
109k
          findDeadBlocks(BB, NextBB);
1882
109k
          continue;
1883
109k
        }
1884
1.23M
      }
1885
1.23M
    } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
1886
46.4k
      Value *Cond = SI->getCondition();
1887
46.4k
      if (ConstantInt *SimpleCond =
1888
16.9k
              dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
1889
16.9k
        BasicBlock *NextBB = SI->findCaseValue(SimpleCond)->getCaseSuccessor();
1890
16.9k
        BBWorklist.insert(NextBB);
1891
16.9k
        KnownSuccessors[BB] = NextBB;
1892
16.9k
        findDeadBlocks(BB, NextBB);
1893
16.9k
        continue;
1894
16.9k
      }
1895
4.89M
    }
1896
4.89M
1897
4.89M
    // If we're unable to select a particular successor, just count all of
1898
4.89M
    // them.
1899
11.4M
    
for (unsigned TIdx = 0, TSize = TI->getNumSuccessors(); 4.89M
TIdx != TSize;
1900
6.58M
         ++TIdx)
1901
6.58M
      BBWorklist.insert(TI->getSuccessor(TIdx));
1902
4.89M
1903
4.89M
    // If we had any successors at this point, than post-inlining is likely to
1904
4.89M
    // have them as well. Note that we assume any basic blocks which existed
1905
4.89M
    // due to branches or switches which folded above will also fold after
1906
4.89M
    // inlining.
1907
4.89M
    if (SingleBB && 
TI->getNumSuccessors() > 1836k
) {
1908
380k
      // Take off the bonus we applied to the threshold.
1909
380k
      Threshold -= SingleBBBonus;
1910
380k
      SingleBB = false;
1911
380k
    }
1912
4.89M
  }
1913
805k
1914
805k
  bool OnlyOneCallAndLocalLinkage =
1915
697k
      F.hasLocalLinkage() && 
F.hasOneUse()110k
&&
&F == Call.getCalledFunction()25.9k
;
1916
697k
  // If this is a noduplicate call, we can still inline as long as
1917
697k
  // inlining this would cause the removal of the caller (so the instruction
1918
697k
  // is not actually duplicated, just moved).
1919
697k
  if (!OnlyOneCallAndLocalLinkage && 
ContainsNoDuplicateCall672k
)
1920
9
    return "noduplicate";
1921
697k
1922
697k
  // Loops generally act a lot like calls in that they act like barriers to
1923
697k
  // movement, require a certain amount of setup, etc. So when optimising for
1924
697k
  // size, we penalise any call sites that perform loops. We do this after all
1925
697k
  // other costs here, so will likely only be dealing with relatively small
1926
697k
  // functions (and hence DT and LI will hopefully be cheap).
1927
697k
  if (Caller->hasMinSize()) {
1928
3.34k
    DominatorTree DT(F);
1929
3.34k
    LoopInfo LI(DT);
1930
3.34k
    int NumLoops = 0;
1931
3.34k
    for (Loop *L : LI) {
1932
12
      // Ignore loops that will not be executed
1933
12
      if (DeadBlocks.count(L->getHeader()))
1934
0
        continue;
1935
12
      NumLoops++;
1936
12
    }
1937
3.34k
    addCost(NumLoops * InlineConstants::CallPenalty);
1938
3.34k
  }
1939
697k
1940
697k
  // We applied the maximum possible vector bonus at the beginning. Now,
1941
697k
  // subtract the excess bonus, if any, from the Threshold before
1942
697k
  // comparing against Cost.
1943
697k
  if (NumVectorInstructions <= NumInstructions / 10)
1944
697k
    Threshold -= VectorBonus;
1945
804
  else if (NumVectorInstructions <= NumInstructions / 2)
1946
765
    Threshold -= VectorBonus/2;
1947
697k
1948
697k
  return Cost < std::max(1, Threshold);
1949
697k
}
1950
1951
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1952
/// Dump stats about this call's analysis.
1953
LLVM_DUMP_METHOD void CallAnalyzer::dump() {
1954
#define DEBUG_PRINT_STAT(x) dbgs() << "      " #x ": " << x << "\n"
1955
  DEBUG_PRINT_STAT(NumConstantArgs);
1956
  DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs);
1957
  DEBUG_PRINT_STAT(NumAllocaArgs);
1958
  DEBUG_PRINT_STAT(NumConstantPtrCmps);
1959
  DEBUG_PRINT_STAT(NumConstantPtrDiffs);
1960
  DEBUG_PRINT_STAT(NumInstructionsSimplified);
1961
  DEBUG_PRINT_STAT(NumInstructions);
1962
  DEBUG_PRINT_STAT(SROACostSavings);
1963
  DEBUG_PRINT_STAT(SROACostSavingsLost);
1964
  DEBUG_PRINT_STAT(LoadEliminationCost);
1965
  DEBUG_PRINT_STAT(ContainsNoDuplicateCall);
1966
  DEBUG_PRINT_STAT(Cost);
1967
  DEBUG_PRINT_STAT(Threshold);
1968
#undef DEBUG_PRINT_STAT
1969
}
1970
#endif
1971
1972
/// Test that there are no attribute conflicts between Caller and Callee
1973
///        that prevent inlining.
1974
static bool functionsHaveCompatibleAttributes(Function *Caller,
1975
                                              Function *Callee,
1976
1.57M
                                              TargetTransformInfo &TTI) {
1977
1.57M
  return TTI.areInlineCompatible(Caller, Callee) &&
1978
1.57M
         
AttributeFuncs::areInlineCompatible(*Caller, *Callee)1.57M
;
1979
1.57M
}
1980
1981
806k
int llvm::getCallsiteCost(CallBase &Call, const DataLayout &DL) {
1982
806k
  int Cost = 0;
1983
2.42M
  for (unsigned I = 0, E = Call.arg_size(); I != E; 
++I1.61M
) {
1984
1.61M
    if (Call.isByValArgument(I)) {
1985
1.42k
      // We approximate the number of loads and stores needed by dividing the
1986
1.42k
      // size of the byval type by the target's pointer size.
1987
1.42k
      PointerType *PTy = cast<PointerType>(Call.getArgOperand(I)->getType());
1988
1.42k
      unsigned TypeSize = DL.getTypeSizeInBits(PTy->getElementType());
1989
1.42k
      unsigned AS = PTy->getAddressSpace();
1990
1.42k
      unsigned PointerSize = DL.getPointerSizeInBits(AS);
1991
1.42k
      // Ceiling division.
1992
1.42k
      unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize;
1993
1.42k
1994
1.42k
      // If it generates more than 8 stores it is likely to be expanded as an
1995
1.42k
      // inline memcpy so we take that as an upper bound. Otherwise we assume
1996
1.42k
      // one load and one store per word copied.
1997
1.42k
      // FIXME: The maxStoresPerMemcpy setting from the target should be used
1998
1.42k
      // here instead of a magic number of 8, but it's not available via
1999
1.42k
      // DataLayout.
2000
1.42k
      NumStores = std::min(NumStores, 8U);
2001
1.42k
2002
1.42k
      Cost += 2 * NumStores * InlineConstants::InstrCost;
2003
1.61M
    } else {
2004
1.61M
      // For non-byval arguments subtract off one instruction per call
2005
1.61M
      // argument.
2006
1.61M
      Cost += InlineConstants::InstrCost;
2007
1.61M
    }
2008
1.61M
  }
2009
806k
  // The call instruction also disappears after inlining.
2010
806k
  Cost += InlineConstants::InstrCost + InlineConstants::CallPenalty;
2011
806k
  return Cost;
2012
806k
}
2013
2014
InlineCost llvm::getInlineCost(
2015
    CallBase &Call, const InlineParams &Params, TargetTransformInfo &CalleeTTI,
2016
    std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
2017
    Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI,
2018
1.60M
    ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE) {
2019
1.60M
  return getInlineCost(Call, Call.getCalledFunction(), Params, CalleeTTI,
2020
1.60M
                       GetAssumptionCache, GetBFI, PSI, ORE);
2021
1.60M
}
2022
2023
InlineCost llvm::getInlineCost(
2024
    CallBase &Call, Function *Callee, const InlineParams &Params,
2025
    TargetTransformInfo &CalleeTTI,
2026
    std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
2027
    Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI,
2028
1.60M
    ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE) {
2029
1.60M
2030
1.60M
  // Cannot inline indirect calls.
2031
1.60M
  if (!Callee)
2032
0
    return llvm::InlineCost::getNever("indirect call");
2033
1.60M
2034
1.60M
  // Never inline calls with byval arguments that does not have the alloca
2035
1.60M
  // address space. Since byval arguments can be replaced with a copy to an
2036
1.60M
  // alloca, the inlined code would need to be adjusted to handle that the
2037
1.60M
  // argument is in the alloca address space (so it is a little bit complicated
2038
1.60M
  // to solve).
2039
1.60M
  unsigned AllocaAS = Callee->getParent()->getDataLayout().getAllocaAddrSpace();
2040
5.06M
  for (unsigned I = 0, E = Call.arg_size(); I != E; 
++I3.46M
)
2041
3.46M
    if (Call.isByValArgument(I)) {
2042
1.48k
      PointerType *PTy = cast<PointerType>(Call.getArgOperand(I)->getType());
2043
1.48k
      if (PTy->getAddressSpace() != AllocaAS)
2044
3
        return llvm::InlineCost::getNever("byval arguments without alloca"
2045
3
                                          " address space");
2046
1.48k
    }
2047
1.60M
2048
1.60M
  // Calls to functions with always-inline attributes should be inlined
2049
1.60M
  // whenever possible.
2050
1.60M
  
if (1.60M
Call.hasFnAttr(Attribute::AlwaysInline)1.60M
) {
2051
30.7k
    auto IsViable = isInlineViable(*Callee);
2052
30.7k
    if (IsViable)
2053
30.7k
      return llvm::InlineCost::getAlways("always inline attribute");
2054
6
    return llvm::InlineCost::getNever(IsViable.message);
2055
6
  }
2056
1.57M
2057
1.57M
  // Never inline functions with conflicting attributes (unless callee has
2058
1.57M
  // always-inline attribute).
2059
1.57M
  Function *Caller = Call.getCaller();
2060
1.57M
  if (!functionsHaveCompatibleAttributes(Caller, Callee, CalleeTTI))
2061
81
    return llvm::InlineCost::getNever("conflicting attributes");
2062
1.57M
2063
1.57M
  // Don't inline this call if the caller has the optnone attribute.
2064
1.57M
  if (Caller->hasOptNone())
2065
3
    return llvm::InlineCost::getNever("optnone attribute");
2066
1.57M
2067
1.57M
  // Don't inline a function that treats null pointer as valid into a caller
2068
1.57M
  // that does not have this attribute.
2069
1.57M
  if (!Caller->nullPointerIsDefined() && 
Callee->nullPointerIsDefined()1.57M
)
2070
2
    return llvm::InlineCost::getNever("nullptr definitions incompatible");
2071
1.57M
2072
1.57M
  // Don't inline functions which can be interposed at link-time.
2073
1.57M
  if (Callee->isInterposable())
2074
718k
    return llvm::InlineCost::getNever("interposable");
2075
853k
2076
853k
  // Don't inline functions marked noinline.
2077
853k
  if (Callee->hasFnAttribute(Attribute::NoInline))
2078
47.2k
    return llvm::InlineCost::getNever("noinline function attribute");
2079
806k
2080
806k
  // Don't inline call sites marked noinline.
2081
806k
  if (Call.isNoInline())
2082
2.79k
    return llvm::InlineCost::getNever("noinline call site attribute");
2083
803k
2084
803k
  LLVM_DEBUG(llvm::dbgs() << "      Analyzing call of " << Callee->getName()
2085
803k
                          << "... (caller:" << Caller->getName() << ")\n");
2086
803k
2087
803k
  CallAnalyzer CA(CalleeTTI, GetAssumptionCache, GetBFI, PSI, ORE, *Callee,
2088
803k
                  Call, Params);
2089
803k
  InlineResult ShouldInline = CA.analyzeCall(Call);
2090
803k
2091
803k
  LLVM_DEBUG(CA.dump());
2092
803k
2093
803k
  // Check if there was a reason to force inlining or no inlining.
2094
803k
  if (!ShouldInline && 
CA.getCost() < CA.getThreshold()224k
)
2095
15.4k
    return InlineCost::getNever(ShouldInline.message);
2096
787k
  if (ShouldInline && 
CA.getCost() >= CA.getThreshold()578k
)
2097
0
    return InlineCost::getAlways("empty function");
2098
787k
2099
787k
  return llvm::InlineCost::get(CA.getCost(), CA.getThreshold());
2100
787k
}
2101
2102
58.0k
InlineResult llvm::isInlineViable(Function &F) {
2103
58.0k
  bool ReturnsTwice = F.hasFnAttribute(Attribute::ReturnsTwice);
2104
147k
  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; 
++BI89.5k
) {
2105
89.5k
    // Disallow inlining of functions which contain indirect branches.
2106
89.5k
    if (isa<IndirectBrInst>(BI->getTerminator()))
2107
4
      return "contains indirect branches";
2108
89.5k
2109
89.5k
    // Disallow inlining of blockaddresses which are used by non-callbr
2110
89.5k
    // instructions.
2111
89.5k
    if (BI->hasAddressTaken())
2112
0
      for (User *U : BlockAddress::get(&*BI)->users())
2113
0
        if (!isa<CallBrInst>(*U))
2114
0
          return "blockaddress used outside of callbr";
2115
89.5k
2116
712k
    
for (auto &II : *BI)89.5k
{
2117
712k
      CallBase *Call = dyn_cast<CallBase>(&II);
2118
712k
      if (!Call)
2119
676k
        continue;
2120
36.3k
2121
36.3k
      // Disallow recursive calls.
2122
36.3k
      if (&F == Call->getCalledFunction())
2123
8
        return "recursive call";
2124
36.3k
2125
36.3k
      // Disallow calls which expose returns-twice to a function not previously
2126
36.3k
      // attributed as such.
2127
36.3k
      if (!ReturnsTwice && 
isa<CallInst>(Call)36.3k
&&
2128
36.3k
          
cast<CallInst>(Call)->canReturnTwice()36.2k
)
2129
4
        return "exposes returns-twice attribute";
2130
36.3k
2131
36.3k
      if (Call->getCalledFunction())
2132
35.7k
        switch (Call->getCalledFunction()->getIntrinsicID()) {
2133
35.7k
        default:
2134
35.7k
          break;
2135
35.7k
        // Disallow inlining of @llvm.icall.branch.funnel because current
2136
35.7k
        // backend can't separate call targets from call arguments.
2137
35.7k
        case llvm::Intrinsic::icall_branch_funnel:
2138
1
          return "disallowed inlining of @llvm.icall.branch.funnel";
2139
35.7k
        // Disallow inlining functions that call @llvm.localescape. Doing this
2140
35.7k
        // correctly would require major changes to the inliner.
2141
35.7k
        case llvm::Intrinsic::localescape:
2142
3
          return "disallowed inlining of @llvm.localescape";
2143
35.7k
        // Disallow inlining of functions that initialize VarArgs with va_start.
2144
35.7k
        case llvm::Intrinsic::vastart:
2145
2
          return "contains VarArgs initialized with va_start";
2146
35.7k
        }
2147
36.3k
    }
2148
89.5k
  }
2149
58.0k
2150
58.0k
  
return true58.0k
;
2151
58.0k
}
2152
2153
// APIs to create InlineParams based on command line flags and/or other
2154
// parameters.
2155
2156
13.9k
InlineParams llvm::getInlineParams(int Threshold) {
2157
13.9k
  InlineParams Params;
2158
13.9k
2159
13.9k
  // This field is the threshold to use for a callee by default. This is
2160
13.9k
  // derived from one or more of:
2161
13.9k
  //  * optimization or size-optimization levels,
2162
13.9k
  //  * a value passed to createFunctionInliningPass function, or
2163
13.9k
  //  * the -inline-threshold flag.
2164
13.9k
  //  If the -inline-threshold flag is explicitly specified, that is used
2165
13.9k
  //  irrespective of anything else.
2166
13.9k
  if (InlineThreshold.getNumOccurrences() > 0)
2167
63
    Params.DefaultThreshold = InlineThreshold;
2168
13.9k
  else
2169
13.9k
    Params.DefaultThreshold = Threshold;
2170
13.9k
2171
13.9k
  // Set the HintThreshold knob from the -inlinehint-threshold.
2172
13.9k
  Params.HintThreshold = HintThreshold;
2173
13.9k
2174
13.9k
  // Set the HotCallSiteThreshold knob from the -hot-callsite-threshold.
2175
13.9k
  Params.HotCallSiteThreshold = HotCallSiteThreshold;
2176
13.9k
2177
13.9k
  // If the -locally-hot-callsite-threshold is explicitly specified, use it to
2178
13.9k
  // populate LocallyHotCallSiteThreshold. Later, we populate
2179
13.9k
  // Params.LocallyHotCallSiteThreshold from -locally-hot-callsite-threshold if
2180
13.9k
  // we know that optimization level is O3 (in the getInlineParams variant that
2181
13.9k
  // takes the opt and size levels).
2182
13.9k
  // FIXME: Remove this check (and make the assignment unconditional) after
2183
13.9k
  // addressing size regression issues at O2.
2184
13.9k
  if (LocallyHotCallSiteThreshold.getNumOccurrences() > 0)
2185
0
    Params.LocallyHotCallSiteThreshold = LocallyHotCallSiteThreshold;
2186
13.9k
2187
13.9k
  // Set the ColdCallSiteThreshold knob from the -inline-cold-callsite-threshold.
2188
13.9k
  Params.ColdCallSiteThreshold = ColdCallSiteThreshold;
2189
13.9k
2190
13.9k
  // Set the OptMinSizeThreshold and OptSizeThreshold params only if the
2191
13.9k
  // -inlinehint-threshold commandline option is not explicitly given. If that
2192
13.9k
  // option is present, then its value applies even for callees with size and
2193
13.9k
  // minsize attributes.
2194
13.9k
  // If the -inline-threshold is not specified, set the ColdThreshold from the
2195
13.9k
  // -inlinecold-threshold even if it is not explicitly passed. If
2196
13.9k
  // -inline-threshold is specified, then -inlinecold-threshold needs to be
2197
13.9k
  // explicitly specified to set the ColdThreshold knob
2198
13.9k
  if (InlineThreshold.getNumOccurrences() == 0) {
2199
13.9k
    Params.OptMinSizeThreshold = InlineConstants::OptMinSizeThreshold;
2200
13.9k
    Params.OptSizeThreshold = InlineConstants::OptSizeThreshold;
2201
13.9k
    Params.ColdThreshold = ColdThreshold;
2202
13.9k
  } else 
if (69
ColdThreshold.getNumOccurrences() > 069
) {
2203
0
    Params.ColdThreshold = ColdThreshold;
2204
0
  }
2205
13.9k
  return Params;
2206
13.9k
}
2207
2208
1.35k
InlineParams llvm::getInlineParams() {
2209
1.35k
  return getInlineParams(InlineThreshold);
2210
1.35k
}
2211
2212
// Compute the default threshold for inlining based on the opt level and the
2213
// size opt level.
2214
static int computeThresholdFromOptLevels(unsigned OptLevel,
2215
12.6k
                                         unsigned SizeOptLevel) {
2216
12.6k
  if (OptLevel > 2)
2217
10.8k
    return InlineConstants::OptAggressiveThreshold;
2218
1.81k
  if (SizeOptLevel == 1) // -Os
2219
55
    return InlineConstants::OptSizeThreshold;
2220
1.76k
  if (SizeOptLevel == 2) // -Oz
2221
1.26k
    return InlineConstants::OptMinSizeThreshold;
2222
496
  return InlineThreshold;
2223
496
}
2224
2225
12.6k
InlineParams llvm::getInlineParams(unsigned OptLevel, unsigned SizeOptLevel) {
2226
12.6k
  auto Params =
2227
12.6k
      getInlineParams(computeThresholdFromOptLevels(OptLevel, SizeOptLevel));
2228
12.6k
  // At O3, use the value of -locally-hot-callsite-threshold option to populate
2229
12.6k
  // Params.LocallyHotCallSiteThreshold. Below O3, this flag has effect only
2230
12.6k
  // when it is specified explicitly.
2231
12.6k
  if (OptLevel > 2)
2232
10.8k
    Params.LocallyHotCallSiteThreshold = LocallyHotCallSiteThreshold;
2233
12.6k
  return Params;
2234
12.6k
}