path: root/lib/Analysis/InlineCost.cpp

//===- InlineCost.cpp - Cost analysis for inliner -------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements inline cost analysis.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "inline-cost"
#include "llvm/Analysis/InlineCost.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/CallingConv.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Operator.h"
#include "llvm/GlobalAlias.h"
#include "llvm/DataLayout.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"

using namespace llvm;

STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");

namespace {

class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
  typedef InstVisitor<CallAnalyzer, bool> Base;
  friend class InstVisitor<CallAnalyzer, bool>;

  // DataLayout if available, or null.
  const DataLayout *const TD;

  // The called function.
  Function &F;

  int Threshold;
  int Cost;
  const bool AlwaysInline;

  bool IsCallerRecursive;
  bool IsRecursiveCall;
  bool ExposesReturnsTwice;
  bool HasDynamicAlloca;
  /// Number of bytes allocated statically by the callee.
  uint64_t AllocatedSize;
  unsigned NumInstructions, NumVectorInstructions;
  int FiftyPercentVectorBonus, TenPercentVectorBonus;
  int VectorBonus;

  // While we walk the potentially-inlined instructions, we build up and
  // maintain a mapping of simplified values specific to this callsite. The
  // idea is to propagate any special information we have about arguments to
  // this call through the inlinable section of the function, and account for
  // likely simplifications post-inlining. The most important aspect we track
  // is CFG altering simplifications -- when we prove a basic block dead, that
  // can cause dramatic shifts in the cost of inlining a function.
  DenseMap<Value *, Constant *> SimplifiedValues;

  // Keep track of the values which map back (through function arguments) to
  // allocas on the caller stack which could be simplified through SROA.
  DenseMap<Value *, Value *> SROAArgValues;

  // The mapping of caller Alloca values to their accumulated cost savings. If
  // we have to disable SROA for one of the allocas, this tells us how much
  // cost must be added.
  DenseMap<Value *, int> SROAArgCosts;

  // Keep track of values which map to a pointer base and constant offset.
  DenseMap<Value *, std::pair<Value *, APInt> > ConstantOffsetPtrs;

  // Custom simplification helper routines.
  bool isAllocaDerivedArg(Value *V);
  bool lookupSROAArgAndCost(Value *V, Value *&Arg,
                            DenseMap<Value *, int>::iterator &CostIt);
  void disableSROA(DenseMap<Value *, int>::iterator CostIt);
  void disableSROA(Value *V);
  void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
                          int InstructionCost);
  bool handleSROACandidate(bool IsSROAValid,
                           DenseMap<Value *, int>::iterator CostIt,
                           int InstructionCost);
  bool isGEPOffsetConstant(GetElementPtrInst &GEP);
  bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
  ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V);

  // Custom analysis routines.
  bool analyzeBlock(BasicBlock *BB);

  // Disable several entry points to the visitor so we don't accidentally use
  // them by declaring but not defining them here.
  void visit(Module *);     void visit(Module &);
  void visit(Function *);   void visit(Function &);
  void visit(BasicBlock *); void visit(BasicBlock &);

  // Provide base case for our instruction visit.
  bool visitInstruction(Instruction &I);

  // Our visit overrides.
  bool visitAlloca(AllocaInst &I);
  bool visitPHI(PHINode &I);
  bool visitGetElementPtr(GetElementPtrInst &I);
  bool visitBitCast(BitCastInst &I);
  bool visitPtrToInt(PtrToIntInst &I);
  bool visitIntToPtr(IntToPtrInst &I);
  bool visitCastInst(CastInst &I