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