lib/Analysis/InlineCost.cpp

   1 //===- InlineCost.cpp - Cost analysis for inliner -------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements inline cost analysis.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "inline-cost"
  15 #include "llvm/Analysis/InlineCost.h"
  16 #include "llvm/Analysis/ConstantFolding.h"
  17 #include "llvm/Analysis/InstructionSimplify.h"
  18 #include "llvm/Support/CallSite.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/Support/InstVisitor.h"
  21 #include "llvm/Support/GetElementPtrTypeIterator.h"
  22 #include "llvm/Support/raw_ostream.h"
  23 #include "llvm/CallingConv.h"
  24 #include "llvm/IntrinsicInst.h"
  25 #include "llvm/Operator.h"
  26 #include "llvm/GlobalAlias.h"
  27 #include "llvm/DataLayout.h"
  28 #include "llvm/ADT/STLExtras.h"
  29 #include "llvm/ADT/SetVector.h"
  30 #include "llvm/ADT/SmallVector.h"
  31 #include "llvm/ADT/SmallPtrSet.h"
  32 #include "llvm/ADT/Statistic.h"
  33
  34 using namespace llvm;
  35
  36 STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");
  37
  38 namespace {
  39
  40 class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
  41   typedef InstVisitor<CallAnalyzer, bool> Base;
  42   friend class InstVisitor<CallAnalyzer, bool>;
  43
  44   // DataLayout if available, or null.
  45   const DataLayout *const TD;
  46
  47   // The called function.
  48   Function &F;
  49
  50   int Threshold;
  51   int Cost;
  52   const bool AlwaysInline;
  53
  54   bool IsCallerRecursive;
  55   bool IsRecursiveCall;
  56   bool ExposesReturnsTwice;
  57   bool HasDynamicAlloca;
  58   /// Number of bytes allocated statically by the callee.
  59   uint64_t AllocatedSize;
  60   unsigned NumInstructions, NumVectorInstructions;
  61   int FiftyPercentVectorBonus, TenPercentVectorBonus;
  62   int VectorBonus;
  63
  64   // While we walk the potentially-inlined instructions, we build up and
  65   // maintain a mapping of simplified values specific to this callsite. The
  66   // idea is to propagate any special information we have about arguments to
  67   // this call through the inlinable section of the function, and account for
  68   // likely simplifications post-inlining. The most important aspect we track
  69   // is CFG altering simplifications -- when we prove a basic block dead, that
  70   // can cause dramatic shifts in the cost of inlining a function.
  71   DenseMap<Value *, Constant *> SimplifiedValues;
  72
  73   // Keep track of the values which map back (through function arguments) to
  74   // allocas on the caller stack which could be simplified through SROA.
  75   DenseMap<Value *, Value *> SROAArgValues;
  76
  77   // The mapping of caller Alloca values to their accumulated cost savings. If
  78   // we have to disable SROA for one of the allocas, this tells us how much
  79   // cost must be added.
  80   DenseMap<Value *, int> SROAArgCosts;
  81
  82   // Keep track of values which map to a pointer base and constant offset.
  83   DenseMap<Value *, std::pair<Value *, APInt> > ConstantOffsetPtrs;
  84
  85   // Custom simplification helper routines.
  86   bool isAllocaDerivedArg(Value *V);
  87   bool lookupSROAArgAndCost(Value *V, Value *&Arg,
  88                             DenseMap<Value *, int>::iterator &CostIt);
  89   void disableSROA(DenseMap<Value *, int>::iterator CostIt);
  90   void disableSROA(Value *V);
  91   void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
  92                           int InstructionCost);
  93   bool handleSROACandidate(bool IsSROAValid,
  94                            DenseMap<Value *, int>::iterator CostIt,
  95                            int InstructionCost);
  96   bool isGEPOffsetConstant(GetElementPtrInst &GEP);
  97   bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
  98   ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V);
  99
 100   // Custom analysis routines.
 101   bool analyzeBlock(BasicBlock *BB);
 102
 103   // Disable several entry points to the visitor so we don't accidentally use
 104   // them by declaring but not defining them here.
 105   void visit(Module *);     void visit(Module &);
 106   void visit(Function *);   void visit(Function &);
 107   void visit(BasicBlock *); void visit(BasicBlock &);
 108
 109   // Provide base case for our instruction visit.
 110   bool visitInstruction(Instruction &I);
 111
 112   // Our visit overrides.
 113   bool visitAlloca(AllocaInst &I);
 114   bool visitPHI(PHINode &I);
 115   bool visitGetElementPtr(GetElementPtrInst &I);
 116   bool visitBitCast(BitCastInst &I);
 117   bool visitPtrToInt(PtrToIntInst &I);
 118   bool visitIntToPtr(IntToPtrInst &I);
 119   bool visitCastInst(CastInst &I);
 120   bool visitUnaryInstruction(UnaryInstruction &I);
 121   bool visitICmp(ICmpInst &I);
 122   bool visitSub(BinaryOperator &I);
 123   bool visitBinaryOperator(BinaryOperator &I);
 124   bool visitLoad(LoadInst &I);
 125   bool visitStore(StoreInst &I);
 126   bool visitCallSite(CallSite CS);
 127
 128 public:
 129   CallAnalyzer(const DataLayout *TD, Function &Callee, int Threshold)
 130     : TD(TD), F(Callee), Threshold(Threshold), Cost(0),
 131       AlwaysInline(F.getFnAttributes().hasAttribute(Attributes::AlwaysInline)),
 132       IsCallerRecursive(false), IsRecursiveCall(false),
 133       ExposesReturnsTwice(false), HasDynamicAlloca(false), AllocatedSize(0),
 134       NumInstructions(0), NumVectorInstructions(0),
 135       FiftyPercentVectorBonus(0), TenPercentVectorBonus(0), VectorBonus(0),
 136       NumConstantArgs(0), NumConstantOffsetPtrArgs(0), NumAllocaArgs(0),
 137       NumConstantPtrCmps(0), NumConstantPtrDiffs(0),
 138       NumInstructionsSimplified(0), SROACostSavings(0), SROACostSavingsLost(0) {
 139   }
 140
 141   bool analyzeCall(CallSite CS);
 142
 143   int getThreshold() { return Threshold; }
 144   int getCost() { return Cost; }
 145   bool isAlwaysInline() { return AlwaysInline; }
 146
 147   // Keep a bunch of stats about the cost savings found so we can print them
 148   // out when debugging.
 149   unsigned NumConstantArgs;
 150   unsigned NumConstantOffsetPtrArgs;
 151   unsigned NumAllocaArgs;
 152   unsigned NumConstantPtrCmps;
 153   unsigned NumConstantPtrDiffs;
 154   unsigned NumInstructionsSimplified;
 155   unsigned SROACostSavings;
 156   unsigned SROACostSavingsLost;
 157
 158   void dump();
 159 };
 160
 161 } // namespace
 162
 163 /// \brief Test whether the given value is an Alloca-derived function argument.
 164 bool CallAnalyzer::isAllocaDerivedArg(Value *V) {
 165   return SROAArgValues.count(V);
 166 }
 167
 168 /// \brief Lookup the SROA-candidate argument and cost iterator which V maps to.
 169 /// Returns false if V does not map to a SROA-candidate.
 170 bool CallAnalyzer::lookupSROAArgAndCost(
 171     Value *V, Value *&Arg, DenseMap<Value *, int>::iterator &CostIt) {
 172   if (SROAArgValues.empty() || SROAArgCosts.empty())
 173     return false;
 174
 175   DenseMap<Value *, Value *>::iterator ArgIt = SROAArgValues.find(V);
 176   if (ArgIt == SROAArgValues.end())
 177     return false;
 178
 179   Arg = ArgIt->second;
 180   CostIt = SROAArgCosts.find(Arg);
 181   return CostIt != SROAArgCosts.end();
 182 }
 183
 184 /// \brief Disable SROA for the candidate marked by this cost iterator.
 185 ///
 186 /// This marks the candidate as no longer viable for SROA, and adds the cost
 187 /// savings associated with it back into the inline cost measurement.
 188 void CallAnalyzer::disableSROA(DenseMap<Value *, int>::iterator CostIt) {
 189   // If we're no longer able to perform SROA we need to undo its cost savings
 190   // and prevent subsequent analysis.
 191   Cost += CostIt->second;
 192   SROACostSavings -= CostIt->second;
 193   SROACostSavingsLost += CostIt->second;
 194   SROAArgCosts.erase(CostIt);
 195 }
 196
 197 /// \brief If 'V' maps to a SROA candidate, disable SROA for it.
 198 void CallAnalyzer::disableSROA(Value *V) {
 199   Value *SROAArg;
 200   DenseMap<Value *, int>::iterator CostIt;
 201   if (lookupSROAArgAndCost(V, SROAArg, CostIt))
 202     disableSROA(CostIt);
 203 }
 204
 205 /// \brief Accumulate the given cost for a particular SROA candidate.
 206 void CallAnalyzer::accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
 207                                       int InstructionCost) {
 208   CostIt->second += InstructionCost;
 209   SROACostSavings += InstructionCost;
 210 }
 211
 212 /// \brief Helper for the common pattern of handling a SROA candidate.
 213 /// Either accumulates the cost savings if the SROA remains valid, or disables
 214 /// SROA for the candidate.
 215 bool CallAnalyzer::handleSROACandidate(bool IsSROAValid,
 216                                        DenseMap<Value *, int>::iterator CostIt,
 217                                        int InstructionCost) {
 218   if (IsSROAValid) {
 219     accumulateSROACost(CostIt, InstructionCost);
 220     return true;
 221   }
 222
 223   disableSROA(CostIt);
 224   return false;
 225 }
 226
 227 /// \brief Check whether a GEP's indices are all constant.
 228 ///
 229 /// Respects any simplified values known during the analysis of this callsite.
 230 bool CallAnalyzer::isGEPOffsetConstant(GetElementPtrInst &GEP) {
 231   for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; ++I)
 232     if (!isa<Constant>(*I) && !SimplifiedValues.lookup(*I))
 233       return false;
 234
 235   return true;
 236 }
 237
 238 /// \brief Accumulate a constant GEP offset into an APInt if possible.
 239 ///
 240 /// Returns false if unable to compute the offset for any reason. Respects any
 241 /// simplified values known during the analysis of this callsite.
 242 bool CallAnalyzer::accumulateGEPOffset(GEPOperator &GEP, APInt &Offset) {
 243   if (!TD)
 244     return false;
 245
 246   unsigned IntPtrWidth = TD->getPointerSizeInBits();
 247   assert(IntPtrWidth == Offset.getBitWidth());
 248
 249   for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
 250        GTI != GTE; ++GTI) {
 251     ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand());
 252     if (!OpC)
 253       if (Constant *SimpleOp = SimplifiedValues.lookup(GTI.getOperand()))
 254         OpC = dyn_cast<ConstantInt>(SimpleOp);
 255     if (!OpC)
 256       return false;
 257     if (OpC->isZero()) continue;
 258
 259     // Handle a struct index, which adds its field offset to the pointer.
 260     if (StructType *STy = dyn_cast<StructType>(*GTI)) {
 261       unsigned ElementIdx = OpC->getZExtValue();
 262       const StructLayout *SL = TD->getStructLayout(STy);
 263       Offset += APInt(IntPtrWidth, SL->getElementOffset(ElementIdx));
 264       continue;
 265     }
 266
 267     APInt TypeSize(IntPtrWidth, TD->getTypeAllocSize(GTI.getIndexedType()));
 268     Offset += OpC->getValue().sextOrTrunc(IntPtrWidth) * TypeSize;
 269   }
 270   return true;
 271 }
 272
 273 bool CallAnalyzer::visitAlloca(AllocaInst &I) {
 274   // FIXME: Check whether inlining will turn a dynamic alloca into a static
 275   // alloca, and handle that case.
 276
 277   // Accumulate the allocated size.
 278   if (I.isStaticAlloca()) {
 279     Type *Ty = I.getAllocatedType();
 280     AllocatedSize += (TD ? TD->getTypeAllocSize(Ty) :
 281                       Ty->getPrimitiveSizeInBits());
 282   }
 283
 284   // We will happily inline static alloca instructions or dynamic alloca
 285   // instructions in always-inline situations.
 286   if (AlwaysInline || I.isStaticAlloca())
 287     return Base::visitAlloca(I);
 288
 289   // FIXME: This is overly conservative. Dynamic allocas are inefficient for
 290   // a variety of reasons, and so we would like to not inline them into
 291   // functions which don't currently have a dynamic alloca. This simply
 292   // disables inlining altogether in the presence of a dynamic alloca.
 293   HasDynamicAlloca = true;
 294   return false;
 295 }
 296
 297 bool CallAnalyzer::visitPHI(PHINode &I) {
 298   // FIXME: We should potentially be tracking values through phi nodes,
 299   // especially when they collapse to a single value due to deleted CFG edges
 300   // during inlining.
 301
 302   // FIXME: We need to propagate SROA *disabling* through phi nodes, even
 303   // though we don't want to propagate it's bonuses. The idea is to disable
 304   // SROA if it *might* be used in an inappropriate manner.
 305
 306   // Phi nodes are always zero-cost.
 307   return true;
 308 }
 309
 310 bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) {
 311   Value *SROAArg;
 312   DenseMap<Value *, int>::iterator CostIt;
 313   bool SROACandidate = lookupSROAArgAndCost(I.getPointerOperand(),
 314                                             SROAArg, CostIt);
 315
 316   // Try to fold GEPs of constant-offset call site argument pointers. This
 317   // requires target data and inbounds GEPs.
 318   if (TD && I.isInBounds()) {
 319     // Check if we have a base + offset for the pointer.
 320     Value *Ptr = I.getPointerOperand();
 321     std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Ptr);
 322     if (BaseAndOffset.first) {
 323       // Check if the offset of this GEP is constant, and if so accumulate it
 324       // into Offset.
 325       if (!accumulateGEPOffset(cast<GEPOperator>(I), BaseAndOffset.second)) {
 326         // Non-constant GEPs aren't folded, and disable SROA.
 327         if (SROACandidate)
 328           disableSROA(CostIt);
 329         return false;
 330       }
 331
 332       // Add the result as a new mapping to Base + Offset.
 333       ConstantOffsetPtrs[&I] = BaseAndOffset;
 334
 335       // Also handle SROA candidates here, we already know that the GEP is
 336       // all-constant indexed.
 337       if (SROACandidate)
 338         SROAArgValues[&I] = SROAArg;
 339
 340       return true;
 341     }
 342   }
 343
 344   if (isGEPOffsetConstant(I)) {
 345     if (SROACandidate)
 346       SROAArgValues[&I] = SROAArg;
 347
 348     // Constant GEPs are modeled as free.
 349     return true;
 350   }
 351
 352   // Variable GEPs will require math and will disable SROA.
 353   if (SROACandidate)
 354     disableSROA(CostIt);
 355   return false;
 356 }
 357
 358 bool CallAnalyzer::visitBitCast(BitCastInst &I) {
 359   // Propagate constants through bitcasts.
 360   if (Constant *COp = dyn_cast<Constant>(I.getOperand(0)))
 361     if (Constant *C = ConstantExpr::getBitCast(COp, I.getType())) {
 362       SimplifiedValues[&I] = C;
 363       return true;
 364     }
 365
 366   // Track base/offsets through casts
 367   std::pair<Value *, APInt> BaseAndOffset
 368     = ConstantOffsetPtrs.lookup(I.getOperand(0));
 369   // Casts don't change the offset, just wrap it up.
 370   if (BaseAndOffset.first)
 371     ConstantOffsetPtrs[&I] = BaseAndOffset;
 372
 373   // Also look for SROA candidates here.
 374   Value *SROAArg;
 375   DenseMap<Value *, int>::iterator CostIt;
 376   if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
 377     SROAArgValues[&I] = SROAArg;
 378
 379   // Bitcasts are always zero cost.
 380   return true;
 381 }
 382
 383 bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) {
 384   // Propagate constants through ptrtoint.
 385   if (Constant *COp = dyn_cast<Constant>(I.getOperand(0)))
 386     if (Constant *C = ConstantExpr::getPtrToInt(COp, I.getType())) {
 387       SimplifiedValues[&I] = C;
 388       return true;
 389     }
 390
 391   // Track base/offset pairs when converted to a plain integer provided the
 392   // integer is large enough to represent the pointer.
 393   unsigned IntegerSize = I.getType()->getScalarSizeInBits();
 394   if (TD && IntegerSize >= TD->getPointerSizeInBits()) {
 395     std::pair<Value *, APInt> BaseAndOffset
 396       = ConstantOffsetPtrs.lookup(I.getOperand(0));
 397     if (BaseAndOffset.first)
 398       ConstantOffsetPtrs[&I] = BaseAndOffset;
 399   }
 400
 401   // This is really weird. Technically, ptrtoint will disable SROA. However,
 402   // unless that ptrtoint is *used* somewhere in the live basic blocks after
 403   // inlining, it will be nuked, and SROA should proceed. All of the uses which
 404   // would block SROA would also block SROA if applied directly to a pointer,
 405   // and so we can just add the integer in here. The only places where SROA is
 406   // preserved either cannot fire on an integer, or won't in-and-of themselves
 407   // disable SROA (ext) w/o some later use that we would see and disable.
 408   Value *SROAArg;
 409   DenseMap<Value *, int>::iterator CostIt;
 410   if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
 411     SROAArgValues[&I] = SROAArg;
 412
 413   return isInstructionFree(&I, TD);
 414 }
 415
 416 bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) {
 417   // Propagate constants through ptrtoint.
 418   if (Constant *COp = dyn_cast<Constant>(I.getOperand(0)))
 419     if (Constant *C = ConstantExpr::getIntToPtr(COp, I.getType())) {
 420       SimplifiedValues[&I] = C;
 421       return true;
 422     }
 423
 424   // Track base/offset pairs when round-tripped through a pointer without
 425   // modifications provided the integer is not too large.
 426   Value *Op = I.getOperand(0);
 427   unsigned IntegerSize = Op->getType()->getScalarSizeInBits();
 428   if (TD && IntegerSize <= TD->getPointerSizeInBits()) {
 429     std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Op);
 430     if (BaseAndOffset.first)
 431       ConstantOffsetPtrs[&I] = BaseAndOffset;
 432   }
 433
 434   // "Propagate" SROA here in the same manner as we do for ptrtoint above.
 435   Value *SROAArg;
 436   DenseMap<Value *, int>::iterator CostIt;
 437   if (lookupSROAArgAndCost(Op, SROAArg, CostIt))
 438     SROAArgValues[&I] = SROAArg;
 439
 440   return isInstructionFree(&I, TD);
 441 }
 442
 443 bool CallAnalyzer::visitCastInst(CastInst &I) {
 444   // Propagate constants through ptrtoint.
 445   if (Constant *COp = dyn_cast<Constant>(I.getOperand(0)))
 446     if (Constant *C = ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
 447       SimplifiedValues[&I] = C;
 448       return true;
 449     }
 450
 451   // Disable SROA in the face of arbitrary casts we don't whitelist elsewhere.
 452   disableSROA(I.getOperand(0));
 453
 454   return isInstructionFree(&I, TD);
 455 }
 456
 457 bool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) {
 458   Value *Operand = I.getOperand(0);
 459   Constant *Ops[1] = { dyn_cast<Constant>(Operand) };
 460   if (Ops[0] || (Ops[0] = SimplifiedValues.lookup(Operand)))
 461     if (Constant *C = ConstantFoldInstOperands(I.getOpcode(), I.getType(),
 462                                                Ops, TD)) {
 463       SimplifiedValues[&I] = C;
 464       return true;
 465     }
 466
 467   // Disable any SROA on the argument to arbitrary unary operators.
 468   disableSROA(Operand);
 469
 470   return false;
 471 }
 472
 473 bool CallAnalyzer::visitICmp(ICmpInst &I) {
 474   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 475   // First try to handle simplified comparisons.
 476   if (!isa<Constant>(LHS))
 477     if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
 478       LHS = SimpleLHS;
 479   if (!isa<Constant>(RHS))
 480     if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
 481       RHS = SimpleRHS;
 482   if (Constant *CLHS = dyn_cast<Constant>(LHS))
 483     if (Constant *CRHS = dyn_cast<Constant>(RHS))
 484       if (Constant *C = ConstantExpr::getICmp(I.getPredicate(), CLHS, CRHS)) {
 485         SimplifiedValues[&I] = C;
 486         return true;
 487       }
 488
 489   // Otherwise look for a comparison between constant offset pointers with
 490   // a common base.
 491   Value *LHSBase, *RHSBase;
 492   APInt LHSOffset, RHSOffset;
 493   llvm::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
 494   if (LHSBase) {
 495     llvm::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
 496     if (RHSBase && LHSBase == RHSBase) {
 497       // We have common bases, fold the icmp to a constant based on the
 498       // offsets.
 499       Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
 500       Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
 501       if (Constant *C = ConstantExpr::getICmp(I.getPredicate(), CLHS, CRHS)) {
 502         SimplifiedValues[&I] = C;
 503         ++NumConstantPtrCmps;
 504         return true;
 505       }
 506     }
 507   }
 508
 509   // If the comparison is an equality comparison with null, we can simplify it
 510   // for any alloca-derived argument.
 511   if (I.isEquality() && isa<ConstantPointerNull>(I.getOperand(1)))
 512     if (isAllocaDerivedArg(I.getOperand(0))) {
 513       // We can actually predict the result of comparisons between an
 514       // alloca-derived value and null. Note that this fires regardless of
 515       // SROA firing.
 516       bool IsNotEqual = I.getPredicate() == CmpInst::ICMP_NE;
 517       SimplifiedValues[&I] = IsNotEqual ? ConstantInt::getTrue(I.getType())
 518                                         : ConstantInt::getFalse(I.getType());
 519       return true;
 520     }
 521
 522   // Finally check for SROA candidates in comparisons.
 523   Value *SROAArg;
 524   DenseMap<Value *, int>::iterator CostIt;
 525   if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
 526     if (isa<ConstantPointerNull>(I.getOperand(1))) {
 527       accumulateSROACost(CostIt, InlineConstants::InstrCost);
 528       return true;
 529     }
 530
 531     disableSROA(CostIt);
 532   }
 533
 534   return false;
 535 }
 536
 537 bool CallAnalyzer::visitSub(BinaryOperator &I) {
 538   // Try to handle a special case: we can fold computing the difference of two
 539   // constant-related pointers.
 540   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 541   Value *LHSBase, *RHSBase;
 542   APInt LHSOffset, RHSOffset;
 543   llvm::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
 544   if (LHSBase) {
 545     llvm::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
 546     if (RHSBase && LHSBase == RHSBase) {
 547       // We have common bases, fold the subtract to a constant based on the
 548       // offsets.
 549       Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
 550       Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
 551       if (Constant *C = ConstantExpr::getSub(CLHS, CRHS)) {
 552         SimplifiedValues[&I] = C;
 553         ++NumConstantPtrDiffs;
 554         return true;
 555       }
 556     }
 557   }
 558
 559   // Otherwise, fall back to the generic logic for simplifying and handling
 560   // instructions.
 561   return Base::visitSub(I);
 562 }
 563
 564 bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) {
 565   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 566   if (!isa<Constant>(LHS))
 567     if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
 568       LHS = SimpleLHS;
 569   if (!isa<Constant>(RHS))
 570     if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
 571       RHS = SimpleRHS;
 572   Value *SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, TD);
 573   if (Constant *C = dyn_cast_or_null<Constant>(SimpleV)) {
 574     SimplifiedValues[&I] = C;
 575     return true;
 576   }
 577
 578   // Disable any SROA on arguments to arbitrary, unsimplified binary operators.
 579   disableSROA(LHS);
 580   disableSROA(RHS);
 581
 582   return false;
 583 }
 584
 585 bool CallAnalyzer::visitLoad(LoadInst &I) {
 586   Value *SROAArg;
 587   DenseMap<Value *, int>::iterator CostIt;
 588   if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
 589     if (I.isSimple()) {
 590       accumulateSROACost(CostIt, InlineConstants::InstrCost);
 591       return true;
 592     }
 593
 594     disableSROA(CostIt);
 595   }
 596
 597   return false;
 598 }
 599
 600 bool CallAnalyzer::visitStore(StoreInst &I) {
 601   Value *SROAArg;
 602   DenseMap<Value *, int>::iterator CostIt;
 603   if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
 604     if (I.isSimple()) {
 605       accumulateSROACost(CostIt, InlineConstants::InstrCost);
 606       return true;
 607     }
 608
 609     disableSROA(CostIt);
 610   }
 611
 612   return false;
 613 }
 614
 615 bool CallAnalyzer::visitCallSite(CallSite CS) {
 616   if (CS.isCall() && cast<CallInst>(CS.getInstruction())->canReturnTwice() &&
 617       !F.getFnAttributes().hasAttribute(Attributes::ReturnsTwice)) {
 618     // This aborts the entire analysis.
 619     ExposesReturnsTwice = true;
 620     return false;
 621   }
 622
 623   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
 624     switch (II->getIntrinsicID()) {
 625     default:
 626       return Base::visitCallSite(CS);
 627
 628     case Intrinsic::memset:
 629     case Intrinsic::memcpy:
 630     case Intrinsic::memmove:
 631       // SROA can usually chew through these intrinsics, but they aren't free.
 632       return false;
 633     }
 634   }
 635
 636   if (Function *F = CS.getCalledFunction()) {
 637     if (F == CS.getInstruction()->getParent()->getParent()) {
 638       // This flag will fully abort the analysis, so don't bother with anything
 639       // else.
 640       IsRecursiveCall = true;
 641       return false;
 642     }
 643
 644     if (!callIsSmall(CS)) {
 645       // We account for the average 1 instruction per call argument setup
 646       // here.
 647       Cost += CS.arg_size() * InlineConstants::InstrCost;
 648
 649       // Everything other than inline ASM will also have a significant cost
 650       // merely from making the call.
 651       if (!isa<InlineAsm>(CS.getCalledValue()))
 652         Cost += InlineConstants::CallPenalty;
 653     }
 654
 655     return Base::visitCallSite(CS);
 656   }
 657
 658   // Otherwise we're in a very special case -- an indirect function call. See
 659   // if we can be particularly clever about this.
 660   Value *Callee = CS.getCalledValue();
 661
 662   // First, pay the price of the argument setup. We account for the average
 663   // 1 instruction per call argument setup here.
 664   Cost += CS.arg_size() * InlineConstants::InstrCost;
 665
 666   // Next, check if this happens to be an indirect function call to a known
 667   // function in this inline context. If not, we've done all we can.
 668   Function *F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee));
 669   if (!F)
 670     return Base::visitCallSite(CS);
 671
 672   // If we have a constant that we are calling as a function, we can peer
 673   // through it and see the function target. This happens not infrequently
 674   // during devirtualization and so we want to give it a hefty bonus for
 675   // inlining, but cap that bonus in the event that inlining wouldn't pan
 676   // out. Pretend to inline the function, with a custom threshold.
 677   CallAnalyzer CA(TD, *F, InlineConstants::IndirectCallThreshold);
 678   if (CA.analyzeCall(CS)) {
 679     // We were able to inline the indirect call! Subtract the cost from the
 680     // bonus we want to apply, but don't go below zero.
 681     Cost -= std::max(0, InlineConstants::IndirectCallThreshold - CA.getCost());
 682   }
 683
 684   return Base::visitCallSite(CS);
 685 }
 686
 687 bool CallAnalyzer::visitInstruction(Instruction &I) {
 688   // Some instructions are free. All of the free intrinsics can also be
 689   // handled by SROA, etc.
 690   if (isInstructionFree(&I, TD))
 691     return true;
 692
 693   // We found something we don't understand or can't handle. Mark any SROA-able
 694   // values in the operand list as no longer viable.
 695   for (User::op_iterator OI = I.op_begin(), OE = I.op_end(); OI != OE; ++OI)
 696     disableSROA(*OI);
 697
 698   return false;
 699 }
 700
 701
 702 /// \brief Analyze a basic block for its contribution to the inline cost.
 703 ///
 704 /// This method walks the analyzer over every instruction in the given basic
 705 /// block and accounts for their cost during inlining at this callsite. It
 706 /// aborts early if the threshold has been exceeded or an impossible to inline
 707 /// construct has been detected. It returns false if inlining is no longer
 708 /// viable, and true if inlining remains viable.
 709 bool CallAnalyzer::analyzeBlock(BasicBlock *BB) {
 710   for (BasicBlock::iterator I = BB->begin(), E = llvm::prior(BB->end());
 711        I != E; ++I) {
 712     ++NumInstructions;
 713     if (isa<ExtractElementInst>(I) || I->getType()->isVectorTy())
 714       ++NumVectorInstructions;
 715
 716     // If the instruction simplified to a constant, there is no cost to this
 717     // instruction. Visit the instructions using our InstVisitor to account for
 718     // all of the per-instruction logic. The visit tree returns true if we
 719     // consumed the instruction in any way, and false if the instruction's base
 720     // cost should count against inlining.
 721     if (Base::visit(I))
 722       ++NumInstructionsSimplified;
 723     else
 724       Cost += InlineConstants::InstrCost;
 725
 726     // If the visit this instruction detected an uninlinable pattern, abort.
 727     if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca)
 728       return false;
 729
 730     // If the caller is a recursive function then we don't want to inline
 731     // functions which allocate a lot of stack space because it would increase
 732     // the caller stack usage dramatically.
 733     if (IsCallerRecursive &&
 734         AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller)
 735       return false;
 736
 737     if (NumVectorInstructions > NumInstructions/2)
 738       VectorBonus = FiftyPercentVectorBonus;
 739     else if (NumVectorInstructions > NumInstructions/10)
 740       VectorBonus = TenPercentVectorBonus;
 741     else
 742       VectorBonus = 0;
 743
 744     // Check if we've past the threshold so we don't spin in huge basic
 745     // blocks that will never inline.
 746     if (!AlwaysInline && Cost > (Threshold + VectorBonus))
 747       return false;
 748   }
 749
 750   return true;
 751 }
 752
 753 /// \brief Compute the base pointer and cumulative constant offsets for V.
 754 ///
 755 /// This strips all constant offsets off of V, leaving it the base pointer, and
 756 /// accumulates the total constant offset applied in the returned constant. It
 757 /// returns 0 if V is not a pointer, and returns the constant '0' if there are
 758 /// no constant offsets applied.
 759 ConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) {
 760   if (!TD || !V->getType()->isPointerTy())
 761     return 0;
 762
 763   unsigned IntPtrWidth = TD->getPointerSizeInBits();
 764   APInt Offset = APInt::getNullValue(IntPtrWidth);
 765
 766   // Even though we don't look through PHI nodes, we could be called on an
 767   // instruction in an unreachable block, which may be on a cycle.
 768   SmallPtrSet<Value *, 4> Visited;
 769   Visited.insert(V);
 770   do {
 771     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
 772       if (!GEP->isInBounds() || !accumulateGEPOffset(*GEP, Offset))
 773         return 0;
 774       V = GEP->getPointerOperand();
 775     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
 776       V = cast<Operator>(V)->getOperand(0);
 777     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
 778       if (GA->mayBeOverridden())
 779         break;
 780       V = GA->getAliasee();
 781     } else {
 782       break;
 783     }
 784     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
 785   } while (Visited.insert(V));
 786
 787   Type *IntPtrTy = TD->getIntPtrType(V->getContext());
 788   return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset));
 789 }
 790
 791 /// \brief Analyze a call site for potential inlining.
 792 ///
 793 /// Returns true if inlining this call is viable, and false if it is not
 794 /// viable. It computes the cost and adjusts the threshold based on numerous
 795 /// factors and heuristics. If this method returns false but the computed cost
 796 /// is below the computed threshold, then inlining was forcibly disabled by
 797 /// some artifact of the rountine.
 798 bool CallAnalyzer::analyzeCall(CallSite CS) {
 799   ++NumCallsAnalyzed;
 800
 801   // Track whether the post-inlining function would have more than one basic
 802   // block. A single basic block is often intended for inlining. Balloon the
 803   // threshold by 50% until we pass the single-BB phase.
 804   bool SingleBB = true;
 805   int SingleBBBonus = Threshold / 2;
 806   Threshold += SingleBBBonus;
 807
 808   // Unless we are always-inlining, perform some tweaks to the cost and
 809   // threshold based on the direct callsite information.
 810   if (!AlwaysInline) {
 811     // We want to more aggressively inline vector-dense kernels, so up the
 812     // threshold, and we'll lower it if the % of vector instructions gets too
 813     // low.
 814     assert(NumInstructions == 0);
 815     assert(NumVectorInstructions == 0);
 816     FiftyPercentVectorBonus = Threshold;
 817     TenPercentVectorBonus = Threshold / 2;
 818
 819     // Give out bonuses per argument, as the instructions setting them up will
 820     // be gone after inlining.
 821     for (unsigned I = 0, E = CS.arg_size(); I != E; ++I) {
 822       if (TD && CS.isByValArgument(I)) {
 823         // We approximate the number of loads and stores needed by dividing the
 824         // size of the byval type by the target's pointer size.
 825         PointerType *PTy = cast<PointerType>(CS.getArgument(I)->getType());
 826         unsigned TypeSize = TD->getTypeSizeInBits(PTy->getElementType());
 827         unsigned PointerSize = TD->getPointerSizeInBits();
 828         // Ceiling division.
 829         unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize;
 830
 831         // If it generates more than 8 stores it is likely to be expanded as an
 832         // inline memcpy so we take that as an upper bound. Otherwise we assume
 833         // one load and one store per word copied.
 834         // FIXME: The maxStoresPerMemcpy setting from the target should be used
 835         // here instead of a magic number of 8, but it's not available via
 836         // DataLayout.
 837         NumStores = std::min(NumStores, 8U);
 838
 839         Cost -= 2 * NumStores * InlineConstants::InstrCost;
 840       } else {
 841         // For non-byval arguments subtract off one instruction per call
 842         // argument.
 843         Cost -= InlineConstants::InstrCost;
 844       }
 845     }
 846
 847     // If there is only one call of the function, and it has internal linkage,
 848     // the cost of inlining it drops dramatically.
 849     if (F.hasLocalLinkage() && F.hasOneUse() && &F == CS.getCalledFunction())
 850       Cost += InlineConstants::LastCallToStaticBonus;
 851
 852     // If the instruction after the call, or if the normal destination of the
 853     // invoke is an unreachable instruction, the function is noreturn. As such,
 854     // there is little point in inlining this unless there is literally zero
 855     // cost.
 856     Instruction *Instr = CS.getInstruction();
 857     if (InvokeInst *II = dyn_cast<InvokeInst>(Instr)) {
 858       if (isa<UnreachableInst>(II->getNormalDest()->begin()))
 859         Threshold = 1;
 860     } else if (isa<UnreachableInst>(++BasicBlock::iterator(Instr)))
 861       Threshold = 1;
 862
 863     // If this function uses the coldcc calling convention, prefer not to inline
 864     // it.
 865     if (F.getCallingConv() == CallingConv::Cold)
 866       Cost += InlineConstants::ColdccPenalty;
 867
 868     // Check if we're done. This can happen due to bonuses and penalties.
 869     if (Cost > Threshold)
 870       return false;
 871   }
 872
 873   if (F.empty())
 874     return true;
 875
 876   Function *Caller = CS.getInstruction()->getParent()->getParent();
 877   // Check if the caller function is recursive itself.
 878   for (Value::use_iterator U = Caller->use_begin(), E = Caller->use_end();
 879        U != E; ++U) {
 880     CallSite Site(cast<Value>(*U));
 881     if (!Site)
 882       continue;
 883     Instruction *I = Site.getInstruction();
 884     if (I->getParent()->getParent() == Caller) {
 885       IsCallerRecursive = true;
 886       break;
 887     }
 888   }
 889
 890   // Track whether we've seen a return instruction. The first return
 891   // instruction is free, as at least one will usually disappear in inlining.
 892   bool HasReturn = false;
 893
 894   // Populate our simplified values by mapping from function arguments to call
 895   // arguments with known important simplifications.
 896   CallSite::arg_iterator CAI = CS.arg_begin();
 897   for (Function::arg_iterator FAI = F.arg_begin(), FAE = F.arg_end();
 898        FAI != FAE; ++FAI, ++CAI) {
 899     assert(CAI != CS.arg_end());
 900     if (Constant *C = dyn_cast<Constant>(CAI))
 901       SimplifiedValues[FAI] = C;
 902
 903     Value *PtrArg = *CAI;
 904     if (ConstantInt *C = stripAndComputeInBoundsConstantOffsets(PtrArg)) {
 905       ConstantOffsetPtrs[FAI] = std::make_pair(PtrArg, C->getValue());
 906
 907       // We can SROA any pointer arguments derived from alloca instructions.
 908       if (isa<AllocaInst>(PtrArg)) {
 909         SROAArgValues[FAI] = PtrArg;
 910         SROAArgCosts[PtrArg] = 0;
 911       }
 912     }
 913   }
 914   NumConstantArgs = SimplifiedValues.size();
 915   NumConstantOffsetPtrArgs = ConstantOffsetPtrs.size();
 916   NumAllocaArgs = SROAArgValues.size();
 917
 918   // The worklist of live basic blocks in the callee *after* inlining. We avoid
 919   // adding basic blocks of the callee which can be proven to be dead for this
 920   // particular call site in order to get more accurate cost estimates. This
 921   // requires a somewhat heavyweight iteration pattern: we need to walk the
 922   // basic blocks in a breadth-first order as we insert live successors. To
 923   // accomplish this, prioritizing for small iterations because we exit after
 924   // crossing our threshold, we use a small-size optimized SetVector.
 925   typedef SetVector<BasicBlock *, SmallVector<BasicBlock *, 16>,
 926                                   SmallPtrSet<BasicBlock *, 16> > BBSetVector;
 927   BBSetVector BBWorklist;
 928   BBWorklist.insert(&F.getEntryBlock());
 929   // Note that we *must not* cache the size, this loop grows the worklist.
 930   for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
 931     // Bail out the moment we cross the threshold. This means we'll under-count
 932     // the cost, but only when undercounting doesn't matter.
 933     if (!AlwaysInline && Cost > (Threshold + VectorBonus))
 934       break;
 935
 936     BasicBlock *BB = BBWorklist[Idx];
 937     if (BB->empty())
 938       continue;
 939
 940     // Handle the terminator cost here where we can track returns and other
 941     // function-wide constructs.
 942     TerminatorInst *TI = BB->getTerminator();
 943
 944     // We never want to inline functions that contain an indirectbr.  This is
 945     // incorrect because all the blockaddress's (in static global initializers
 946     // for example) would be referring to the original function, and this
 947     // indirect jump would jump from the inlined copy of the function into the
 948     // original function which is extremely undefined behavior.
 949     // FIXME: This logic isn't really right; we can safely inline functions
 950     // with indirectbr's as long as no other function or global references the
 951     // blockaddress of a block within the current function.  And as a QOI issue,
 952     // if someone is using a blockaddress without an indirectbr, and that
 953     // reference somehow ends up in another function or global, we probably
 954     // don't want to inline this function.
 955     if (isa<IndirectBrInst>(TI))
 956       return false;
 957
 958     if (!HasReturn && isa<ReturnInst>(TI))
 959       HasReturn = true;
 960     else
 961       Cost += InlineConstants::InstrCost;
 962
 963     // Analyze the cost of this block. If we blow through the threshold, this
 964     // returns false, and we can bail on out.
 965     if (!analyzeBlock(BB)) {
 966       if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca)
 967         return false;
 968
 969       // If the caller is a recursive function then we don't want to inline
 970       // functions which allocate a lot of stack space because it would increase
 971       // the caller stack usage dramatically.
 972       if (IsCallerRecursive &&
 973           AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller)
 974         return false;
 975
 976       break;
 977     }
 978
 979     // Add in the live successors by first checking whether we have terminator
 980     // that may be simplified based on the values simplified by this call.
 981     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
 982       if (BI->isConditional()) {
 983         Value *Cond = BI->getCondition();
 984         if (ConstantInt *SimpleCond
 985               = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
 986           BBWorklist.insert(BI->getSuccessor(SimpleCond->isZero() ? 1 : 0));
 987           continue;
 988         }
 989       }
 990     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
 991       Value *Cond = SI->getCondition();
 992       if (ConstantInt *SimpleCond
 993             = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
 994         BBWorklist.insert(SI->findCaseValue(SimpleCond).getCaseSuccessor());
 995         continue;
 996       }
 997     }
 998
 999     // If we're unable to select a particular successor, just count all of
1000     // them.
1001     for (unsigned TIdx = 0, TSize = TI->getNumSuccessors(); TIdx != TSize;
1002          ++TIdx)
1003       BBWorklist.insert(TI->getSuccessor(TIdx));
1004
1005     // If we had any successors at this point, than post-inlining is likely to
1006     // have them as well. Note that we assume any basic blocks which existed
1007     // due to branches or switches which folded above will also fold after
1008     // inlining.
1009     if (SingleBB && TI->getNumSuccessors() > 1) {
1010       // Take off the bonus we applied to the threshold.
1011       Threshold -= SingleBBBonus;
1012       SingleBB = false;
1013     }
1014   }
1015
1016   Threshold += VectorBonus;
1017
1018   return AlwaysInline || Cost < Threshold;
1019 }
1020
1021 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1022 /// \brief Dump stats about this call's analysis.
1023 void CallAnalyzer::dump() {
1024 #define DEBUG_PRINT_STAT(x) llvm::dbgs() << "      " #x ": " << x << "\n"
1025   DEBUG_PRINT_STAT(NumConstantArgs);
1026   DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs);
1027   DEBUG_PRINT_STAT(NumAllocaArgs);
1028   DEBUG_PRINT_STAT(NumConstantPtrCmps);
1029   DEBUG_PRINT_STAT(NumConstantPtrDiffs);
1030   DEBUG_PRINT_STAT(NumInstructionsSimplified);
1031   DEBUG_PRINT_STAT(SROACostSavings);
1032   DEBUG_PRINT_STAT(SROACostSavingsLost);
1033 #undef DEBUG_PRINT_STAT
1034 }
1035 #endif
1036
1037 InlineCost InlineCostAnalyzer::getInlineCost(CallSite CS, int Threshold) {
1038   return getInlineCost(CS, CS.getCalledFunction(), Threshold);
1039 }
1040
1041 InlineCost InlineCostAnalyzer::getInlineCost(CallSite CS, Function *Callee,
1042                                              int Threshold) {
1043   // Don't inline functions which can be redefined at link-time to mean
1044   // something else.  Don't inline functions marked noinline or call sites
1045   // marked noinline.
1046   if (!Callee || Callee->mayBeOverridden() ||
1047       Callee->getFnAttributes().hasAttribute(Attributes::NoInline) ||
1048       CS.isNoInline())
1049     return llvm::InlineCost::getNever();
1050
1051   DEBUG(llvm::dbgs() << "      Analyzing call of " << Callee->getName()
1052         << "...\n");
1053
1054   CallAnalyzer CA(TD, *Callee, Threshold);
1055   bool ShouldInline = CA.analyzeCall(CS);
1056
1057   DEBUG(CA.dump());
1058
1059   // Check if there was a reason to force inlining or no inlining.
1060   if (!ShouldInline && CA.getCost() < CA.getThreshold())
1061     return InlineCost::getNever();
1062   if (ShouldInline && (CA.isAlwaysInline() ||
1063                        CA.getCost() >= CA.getThreshold()))
1064     return InlineCost::getAlways();
1065
1066   return llvm::InlineCost::get(CA.getCost(), CA.getThreshold());
1067 }