#include "llvm/Analysis/InlineCost.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/CallingConv.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Operator.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
#define DEBUG_TYPE "inline-cost"
STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");
namespace {
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
typedef InstVisitor<CallAnalyzer, bool> Base;
friend class InstVisitor<CallAnalyzer, bool>;
const DataLayout *const DL;
const TargetTransformInfo &TTI;
Function &F;
int Threshold;
int Cost;
bool IsCallerRecursive;
bool IsRecursiveCall;
bool ExposesReturnsTwice;
bool HasDynamicAlloca;
bool ContainsNoDuplicateCall;
bool HasReturn;
bool HasIndirectBr;
uint64_t AllocatedSize;
unsigned NumInstructions, NumVectorInstructions;
int FiftyPercentVectorBonus, TenPercentVectorBonus;
int VectorBonus;
DenseMap<Value *, Constant *> SimplifiedValues;
DenseMap<Value *, Value *> SROAArgValues;
DenseMap<Value *, int> SROAArgCosts;
DenseMap<Value *, std::pair<Value *, APInt> > ConstantOffsetPtrs;
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 isGEPOffsetConstant(GetElementPtrInst &GEP);
bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
bool simplifyCallSite(Function *F, CallSite CS);
ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V);
bool analyzeBlock(BasicBlock *BB);
void visit(Module *); void visit(Module &);
void visit(Function *); void visit(Function &);
void visit(BasicBlock *); void visit(BasicBlock &);
bool visitInstruction(Instruction &I);
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);
bool visitUnaryInstruction(UnaryInstruction &I);
bool visitCmpInst(CmpInst &I);
bool visitSub(BinaryOperator &I);
bool visitBinaryOperator(BinaryOperator &I);
bool visitLoad(LoadInst &I);
bool visitStore(StoreInst &I);
bool visitExtractValue(ExtractValueInst &I);
bool visitInsertValue(InsertValueInst &I);
bool visitCallSite(CallSite CS);
bool visitReturnInst(ReturnInst &RI);
bool visitBranchInst(BranchInst &BI);
bool visitSwitchInst(SwitchInst &SI);
bool visitIndirectBrInst(IndirectBrInst &IBI);
bool visitResumeInst(ResumeInst &RI);
bool visitUnreachableInst(UnreachableInst &I);
public:
CallAnalyzer(const DataLayout *DL, const TargetTransformInfo &TTI,
Function &Callee, int Threshold)
: DL(DL), TTI(TTI), F(Callee), Threshold(Threshold), Cost(0),
IsCallerRecursive(false), IsRecursiveCall(false),
ExposesReturnsTwice(false), HasDynamicAlloca(false),
ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false),
AllocatedSize(0), NumInstructions(0), NumVectorInstructions(0),
FiftyPercentVectorBonus(0), TenPercentVectorBonus(0), VectorBonus(0),
NumConstantArgs(0), NumConstantOffsetPtrArgs(0), NumAllocaArgs(0),
NumConstantPtrCmps(0), NumConstantPtrDiffs(0),
NumInstructionsSimplified(0), SROACostSavings(0),
SROACostSavingsLost(0) {}
bool analyzeCall(CallSite CS);
int getThreshold() { return Threshold; }
int getCost() { return Cost; }
unsigned NumConstantArgs;
unsigned NumConstantOffsetPtrArgs;
unsigned NumAllocaArgs;
unsigned NumConstantPtrCmps;
unsigned NumConstantPtrDiffs;
unsigned NumInstructionsSimplified;
unsigned SROACostSavings;
unsigned SROACostSavingsLost;
void dump();
};
}
bool CallAnalyzer::isAllocaDerivedArg(Value *V) {
return SROAArgValues.count(V);
}
bool CallAnalyzer::lookupSROAArgAndCost(
Value *V, Value *&Arg, DenseMap<Value *, int>::iterator &CostIt) {
if (SROAArgValues.empty() || SROAArgCosts.empty())
return false;
DenseMap<Value *, Value *>::iterator ArgIt = SROAArgValues.find(V);
if (ArgIt == SROAArgValues.end())
return false;
Arg = ArgIt->second;
CostIt = SROAArgCosts.find(Arg);
return CostIt != SROAArgCosts.end();
}
void CallAnalyzer::disableSROA(DenseMap<Value *, int>::iterator CostIt) {
Cost += CostIt->second;
SROACostSavings -= CostIt->second;
SROACostSavingsLost += CostIt->second;
SROAArgCosts.erase(CostIt);
}
void CallAnalyzer::disableSROA(Value *V) {
Value *SROAArg;
DenseMap<Value *, int>::iterator CostIt;
if (lookupSROAArgAndCost(V, SROAArg, CostIt))
disableSROA(CostIt);
}
void CallAnalyzer::accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
int InstructionCost) {
CostIt->second += InstructionCost;
SROACostSavings += InstructionCost;
}
bool CallAnalyzer::isGEPOffsetConstant(GetElementPtrInst &GEP) {
for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; ++I)
if (!isa<Constant>(*I) && !SimplifiedValues.lookup(*I))
return false;
return true;
}
bool CallAnalyzer::accumulateGEPOffset(GEPOperator &GEP, APInt &Offset) {
if (!DL)
return false;
unsigned IntPtrWidth = DL->getPointerSizeInBits();
assert(IntPtrWidth == Offset.getBitWidth());
for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
GTI != GTE; ++GTI) {
ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand());
if (!OpC)
if (Constant *SimpleOp = SimplifiedValues.lookup(GTI.getOperand()))
OpC = dyn_cast<ConstantInt>(SimpleOp);
if (!OpC)
return false;
if (OpC->isZero()) continue;
if (StructType *STy = dyn_cast<StructType>(*GTI)) {
unsigned ElementIdx = OpC->getZExtValue();
const StructLayout *SL = DL->getStructLayout(STy);
Offset += APInt(IntPtrWidth, SL->getElementOffset(ElementIdx));
continue;
}
APInt TypeSize(IntPtrWidth, DL->getTypeAllocSize(GTI.getIndexedType()));
Offset += OpC->getValue().sextOrTrunc(IntPtrWidth) * TypeSize;
}
return true;
}
bool CallAnalyzer::visitAlloca(AllocaInst &I) {
if (I.isArrayAllocation()) {
if (Constant *Size = SimplifiedValues.lookup(I.getArraySize())) {
ConstantInt *AllocSize = dyn_cast<ConstantInt>(Size);
assert(AllocSize && "Allocation size not a constant int?");
Type *Ty = I.getAllocatedType();
AllocatedSize += Ty->getPrimitiveSizeInBits() * AllocSize->getZExtValue();
return Base::visitAlloca(I);
}
}
if (I.isStaticAlloca()) {
Type *Ty = I.getAllocatedType();
AllocatedSize += (DL ? DL->getTypeAllocSize(Ty) :
Ty->getPrimitiveSizeInBits());
}
if (I.isStaticAlloca())
return Base::visitAlloca(I);
HasDynamicAlloca = true;
return false;
}
bool CallAnalyzer::visitPHI(PHINode &I) {
return true;
}
bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) {
Value *SROAArg;
DenseMap<Value *, int>::iterator CostIt;
bool SROACandidate = lookupSROAArgAndCost(I.getPointerOperand(),
SROAArg, CostIt);
if (DL && I.isInBounds()) {
Value *Ptr = I.getPointerOperand();
std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Ptr);
if (BaseAndOffset.first) {
if (!accumulateGEPOffset(cast<GEPOperator>(I), BaseAndOffset.second)) {
if (SROACandidate)
disableSROA(CostIt);
return false;
}
ConstantOffsetPtrs[&I] = BaseAndOffset;
if (SROACandidate)
SROAArgValues[&I] = SROAArg;
return true;
}
}
if (isGEPOffsetConstant(I)) {
if (SROACandidate)
SROAArgValues[&I] = SROAArg;
return true;
}
if (SROACandidate)
disableSROA(CostIt);
return false;
}
bool CallAnalyzer::visitBitCast(BitCastInst &I) {
Constant *COp = dyn_cast<Constant>(I.getOperand(0));
if (!COp)
COp = SimplifiedValues.lookup(I.getOperand(0));
if (COp)
if (Constant *C = ConstantExpr::getBitCast(COp, I.getType())) {
SimplifiedValues[&I] = C;
return true;
}
std::pair<Value *, APInt> BaseAndOffset
= ConstantOffsetPtrs.lookup(I.getOperand(0));
if (BaseAndOffset.first)
ConstantOffsetPtrs[&I] = BaseAndOffset;
Value *SROAArg;
DenseMap<Value *, int>::iterator CostIt;
if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
SROAArgValues[&I] = SROAArg;
return true;
}
bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) {
const DataLayout *DL = I.getDataLayout();
Constant *COp = dyn_cast<Constant>(I.getOperand(0));
if (!COp)
COp = SimplifiedValues.lookup(I.getOperand(0));
if (COp)
if (Constant *C = ConstantExpr::getPtrToInt(COp, I.getType())) {
SimplifiedValues[&I] = C;
return true;
}
unsigned IntegerSize = I.getType()->getScalarSizeInBits();
if (DL && IntegerSize >= DL->getPointerSizeInBits()) {
std::pair<Value *, APInt> BaseAndOffset
= ConstantOffsetPtrs.lookup(I.getOperand(0));
if (BaseAndOffset.first)
ConstantOffsetPtrs[&I] = BaseAndOffset;
}
Value *SROAArg;
DenseMap<Value *, int>::iterator CostIt;
if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
SROAArgValues[&I] = SROAArg;
return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
}
bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) {
const DataLayout *DL = I.getDataLayout();
Constant *COp = dyn_cast<Constant>(I.getOperand(0));
if (!COp)
COp = SimplifiedValues.lookup(I.getOperand(0));
if (COp)
if (Constant *C = ConstantExpr::getIntToPtr(COp, I.getType())) {
SimplifiedValues[&I] = C;
return true;
}
Value *Op = I.getOperand(0);
unsigned IntegerSize = Op->getType()->getScalarSizeInBits();
if (DL && IntegerSize <= DL->getPointerSizeInBits()) {
std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Op);
if (BaseAndOffset.first)
ConstantOffsetPtrs[&I] = BaseAndOffset;
}
Value *SROAArg;
DenseMap<Value *, int>::iterator CostIt;
if (lookupSROAArgAndCost(Op, SROAArg, CostIt))
SROAArgValues[&I] = SROAArg;
return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
}
bool CallAnalyzer::visitCastInst(CastInst &I) {
Constant *COp = dyn_cast<Constant>(I.getOperand(0));
if (!COp)
COp = SimplifiedValues.lookup(I.getOperand(0));
if (COp)
if (Constant *C = ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
SimplifiedValues[&I] = C;
return true;
}
disableSROA(I.getOperand(0));
return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
}
bool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) {
Value *Operand = I.getOperand(0);
Constant *COp = dyn_cast<Constant>(Operand);
if (!COp)
COp = SimplifiedValues.lookup(Operand);
if (COp)
if (Constant *C = ConstantFoldInstOperands(I.getOpcode(), I.getType(),
COp, DL)) {
SimplifiedValues[&I] = C;
return true;
}
disableSROA(Operand);
return false;
}
bool CallAnalyzer::visitCmpInst(CmpInst &I) {
Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
if (!isa<Constant>(LHS))
if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
LHS = SimpleLHS;
if (!isa<Constant>(RHS))
if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
RHS = SimpleRHS;
if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
if (Constant *CRHS = dyn_cast<Constant>(RHS))
if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
SimplifiedValues[&I] = C;
return true;
}
}
if (I.getOpcode() == Instruction::FCmp)
return false;
Value *LHSBase, *RHSBase;
APInt LHSOffset, RHSOffset;
std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
if (LHSBase) {
std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
if (RHSBase && LHSBase == RHSBase) {
Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
if (Constant *C = ConstantExpr::getICmp(I.getPredicate(), CLHS, CRHS)) {
SimplifiedValues[&I] = C;
++NumConstantPtrCmps;
return true;
}
}
}
if (I.isEquality() && isa<ConstantPointerNull>(I.getOperand(1)))
if (isAllocaDerivedArg(I.getOperand(0))) {
bool IsNotEqual = I.getPredicate() == CmpInst::ICMP_NE;
SimplifiedValues[&I] = IsNotEqual ? ConstantInt::getTrue(I.getType())
: ConstantInt::getFalse(I.getType());
return true;
}
Value *SROAArg;
DenseMap<Value *, int>::iterator CostIt;
if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
if (isa<ConstantPointerNull>(I.getOperand(1))) {
accumulateSROACost(CostIt, InlineConstants::InstrCost);
return true;
}
disableSROA(CostIt);
}
return false;
}
bool CallAnalyzer::visitSub(BinaryOperator &I) {
Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
Value *LHSBase, *RHSBase;
APInt LHSOffset, RHSOffset;
std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
if (LHSBase) {
std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
if (RHSBase && LHSBase == RHSBase) {
Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
if (Constant *C = ConstantExpr::getSub(CLHS, CRHS)) {
SimplifiedValues[&I] = C;
++NumConstantPtrDiffs;
return true;
}
}
}
return Base::visitSub(I);
}
bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) {
Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
if (!isa<Constant>(LHS))
if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
LHS = SimpleLHS;
if (!isa<Constant>(RHS))
if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
RHS = SimpleRHS;
Value *SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
if (Constant *C = dyn_cast_or_null<Constant>(SimpleV)) {
SimplifiedValues[&I] = C;
return true;
}
disableSROA(LHS);
disableSROA(RHS);
return false;
}
bool CallAnalyzer::visitLoad(LoadInst &I) {
Value *SROAArg;
DenseMap<Value *, int>::iterator CostIt;
if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
if (I.isSimple()) {
accumulateSROACost(CostIt, InlineConstants::InstrCost);
return true;
}
disableSROA(CostIt);
}
return false;
}
bool CallAnalyzer::visitStore(StoreInst &I) {
Value *SROAArg;
DenseMap<Value *, int>::iterator CostIt;
if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
if (I.isSimple()) {
accumulateSROACost(CostIt, InlineConstants::InstrCost);
return true;
}
disableSROA(CostIt);
}
return false;
}
bool CallAnalyzer::visitExtractValue(ExtractValueInst &I) {
Constant *C = dyn_cast<Constant>(I.getAggregateOperand());
if (!C)
C = SimplifiedValues.lookup(I.getAggregateOperand());
if (C) {
SimplifiedValues[&I] = ConstantExpr::getExtractValue(C, I.getIndices());
return true;
}
return false;
}
bool CallAnalyzer::visitInsertValue(InsertValueInst &I) {
Constant *AggC = dyn_cast<Constant>(I.getAggregateOperand());
if (!AggC)
AggC = SimplifiedValues.lookup(I.getAggregateOperand());
Constant *InsertedC = dyn_cast<Constant>(I.getInsertedValueOperand());
if (!InsertedC)
InsertedC = SimplifiedValues.lookup(I.getInsertedValueOperand());
if (AggC && InsertedC) {
SimplifiedValues[&I] = ConstantExpr::getInsertValue(AggC, InsertedC,
I.getIndices());
return true;
}
return false;
}
bool CallAnalyzer::simplifyCallSite(Function *F, CallSite CS) {
if (!canConstantFoldCallTo(F))
return false;
SmallVector<Constant *, 4> ConstantArgs;
ConstantArgs.reserve(CS.arg_size());
for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
I != E; ++I) {
Constant *C = dyn_cast<Constant>(*I);
if (!C)
C = dyn_cast_or_null<Constant>(SimplifiedValues.lookup(*I));
if (!C)
return false;
ConstantArgs.push_back(C);
}
if (Constant *C = ConstantFoldCall(F, ConstantArgs)) {
SimplifiedValues[CS.getInstruction()] = C;
return true;
}
return false;
}
bool CallAnalyzer::visitCallSite(CallSite CS) {
if (CS.hasFnAttr(Attribute::ReturnsTwice) &&
!F.getAttributes().hasAttribute(AttributeSet::FunctionIndex,
Attribute::ReturnsTwice)) {
ExposesReturnsTwice = true;
return false;
}
if (CS.isCall() &&
cast<CallInst>(CS.getInstruction())->cannotDuplicate())
ContainsNoDuplicateCall = true;
if (Function *F = CS.getCalledFunction()) {
if (simplifyCallSite(F, CS))
return true;
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
switch (II->getIntrinsicID()) {
default:
return Base::visitCallSite(CS);
case Intrinsic::memset:
case Intrinsic::memcpy:
case Intrinsic::memmove:
return false;
}
}
if (F == CS.getInstruction()->getParent()->getParent()) {
IsRecursiveCall = true;
return false;
}
if (TTI.isLoweredToCall(F)) {
Cost += CS.arg_size() * InlineConstants::InstrCost;
if (!isa<InlineAsm>(CS.getCalledValue()))
Cost += InlineConstants::CallPenalty;
}
return Base::visitCallSite(CS);
}
Value *Callee = CS.getCalledValue();
Cost += CS.arg_size() * InlineConstants::InstrCost;
Function *F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee));
if (!F)
return Base::visitCallSite(CS);
CallAnalyzer CA(DL, TTI, *F, InlineConstants::IndirectCallThreshold);
if (CA.analyzeCall(CS)) {
Cost -= std::max(0, InlineConstants::IndirectCallThreshold - CA.getCost());
}
return Base::visitCallSite(CS);
}
bool CallAnalyzer::visitReturnInst(ReturnInst &RI) {
bool Free = !HasReturn;
HasReturn = true;
return Free;
}
bool CallAnalyzer::visitBranchInst(BranchInst &BI) {
return BI.isUnconditional() || isa<ConstantInt>(BI.getCondition()) ||
dyn_cast_or_null<ConstantInt>(
SimplifiedValues.lookup(BI.getCondition()));
}
bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
if (isa<ConstantInt>(SI.getCondition()))
return true;
if (Value *V = SimplifiedValues.lookup(SI.getCondition()))
if (isa<ConstantInt>(V))
return true;
SmallPtrSet<BasicBlock *, 8> SuccessorBlocks;
SuccessorBlocks.insert(SI.getDefaultDest());
for (auto I = SI.case_begin(), E = SI.case_end(); I != E; ++I)
SuccessorBlocks.insert(I.getCaseSuccessor());
Cost += (SuccessorBlocks.size() - 1) * InlineConstants::InstrCost;
return false;
}
bool CallAnalyzer::visitIndirectBrInst(IndirectBrInst &IBI) {
HasIndirectBr = true;
return false;
}
bool CallAnalyzer::visitResumeInst(ResumeInst &RI) {
return false;
}
bool CallAnalyzer::visitUnreachableInst(UnreachableInst &I) {
return true; }
bool CallAnalyzer::visitInstruction(Instruction &I) {
if (TargetTransformInfo::TCC_Free == TTI.getUserCost(&I))
return true;
for (User::op_iterator OI = I.op_begin(), OE = I.op_end(); OI != OE; ++OI)
disableSROA(*OI);
return false;
}
bool CallAnalyzer::analyzeBlock(BasicBlock *BB) {
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
if (isa<DbgInfoIntrinsic>(I))
continue;
++NumInstructions;
if (isa<ExtractElementInst>(I) || I->getType()->isVectorTy())
++NumVectorInstructions;
if (Base::visit(I))
++NumInstructionsSimplified;
else
Cost += InlineConstants::InstrCost;
if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca ||
HasIndirectBr)
return false;
if (IsCallerRecursive &&
AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller)
return false;
if (NumVectorInstructions > NumInstructions/2)
VectorBonus = FiftyPercentVectorBonus;
else if (NumVectorInstructions > NumInstructions/10)
VectorBonus = TenPercentVectorBonus;
else
VectorBonus = 0;
if (Cost > (Threshold + VectorBonus))
return false;
}
return true;
}
ConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) {
if (!DL || !V->getType()->isPointerTy())
return nullptr;
unsigned IntPtrWidth = DL->getPointerSizeInBits();
APInt Offset = APInt::getNullValue(IntPtrWidth);
SmallPtrSet<Value *, 4> Visited;
Visited.insert(V);
do {
if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
if (!GEP->isInBounds() || !accumulateGEPOffset(*GEP, Offset))
return nullptr;
V = GEP->getPointerOperand();
} else if (Operator::getOpcode(V) == Instruction::BitCast) {
V = cast<Operator>(V)->getOperand(0);
} else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
if (GA->mayBeOverridden())
break;
V = GA->getAliasee();
} else {
break;
}
assert(V->getType()->isPointerTy() && "Unexpected operand type!");
} while (Visited.insert(V));
Type *IntPtrTy = DL->getIntPtrType(V->getContext());
return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset));
}
bool CallAnalyzer::analyzeCall(CallSite CS) {
++NumCallsAnalyzed;
bool SingleBB = true;
int SingleBBBonus = Threshold / 2;
Threshold += SingleBBBonus;
assert(NumInstructions == 0);
assert(NumVectorInstructions == 0);
FiftyPercentVectorBonus = Threshold;
TenPercentVectorBonus = Threshold / 2;
for (unsigned I = 0, E = CS.arg_size(); I != E; ++I) {
if (DL && CS.isByValArgument(I)) {
PointerType *PTy = cast<PointerType>(CS.getArgument(I)->getType());
unsigned TypeSize = DL->getTypeSizeInBits(PTy->getElementType());
unsigned PointerSize = DL->getPointerSizeInBits();
unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize;
NumStores = std::min(NumStores, 8U);
Cost -= 2 * NumStores * InlineConstants::InstrCost;
} else {
Cost -= InlineConstants::InstrCost;
}
}
bool OnlyOneCallAndLocalLinkage = F.hasLocalLinkage() && F.hasOneUse() &&
&F == CS.getCalledFunction();
if (OnlyOneCallAndLocalLinkage)
Cost += InlineConstants::LastCallToStaticBonus;
Instruction *Instr = CS.getInstruction();
if (InvokeInst *II = dyn_cast<InvokeInst>(Instr)) {
if (isa<UnreachableInst>(II->getNormalDest()->begin()))
Threshold = 1;
} else if (isa<UnreachableInst>(++BasicBlock::iterator(Instr)))
Threshold = 1;
if (F.getCallingConv() == CallingConv::Cold)
Cost += InlineConstants::ColdccPenalty;
if (Cost > Threshold)
return false;
if (F.empty())
return true;
Function *Caller = CS.getInstruction()->getParent()->getParent();
for (User *U : Caller->users()) {
CallSite Site(U);
if (!Site)
continue;
Instruction *I = Site.getInstruction();
if (I->getParent()->getParent() == Caller) {
IsCallerRecursive = true;
break;
}
}
CallSite::arg_iterator CAI = CS.arg_begin();
for (Function::arg_iterator FAI = F.arg_begin(), FAE = F.arg_end();
FAI != FAE; ++FAI, ++CAI) {
assert(CAI != CS.arg_end());
if (Constant *C = dyn_cast<Constant>(CAI))
SimplifiedValues[FAI] = C;
Value *PtrArg = *CAI;
if (ConstantInt *C = stripAndComputeInBoundsConstantOffsets(PtrArg)) {
ConstantOffsetPtrs[FAI] = std::make_pair(PtrArg, C->getValue());
if (isa<AllocaInst>(PtrArg)) {
SROAArgValues[FAI] = PtrArg;
SROAArgCosts[PtrArg] = 0;
}
}
}
NumConstantArgs = SimplifiedValues.size();
NumConstantOffsetPtrArgs = ConstantOffsetPtrs.size();
NumAllocaArgs = SROAArgValues.size();
typedef SetVector<BasicBlock *, SmallVector<BasicBlock *, 16>,
SmallPtrSet<BasicBlock *, 16> > BBSetVector;
BBSetVector BBWorklist;
BBWorklist.insert(&F.getEntryBlock());
for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
if (Cost > (Threshold + VectorBonus))
break;
BasicBlock *BB = BBWorklist[Idx];
if (BB->empty())
continue;
if (BB->hasAddressTaken())
return false;
if (!analyzeBlock(BB)) {
if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca ||
HasIndirectBr)
return false;
if (IsCallerRecursive &&
AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller)
return false;
break;
}
TerminatorInst *TI = BB->getTerminator();
if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
if (BI->isConditional()) {
Value *Cond = BI->getCondition();
if (ConstantInt *SimpleCond
= dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
BBWorklist.insert(BI->getSuccessor(SimpleCond->isZero() ? 1 : 0));
continue;
}
}
} else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
Value *Cond = SI->getCondition();
if (ConstantInt *SimpleCond
= dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
BBWorklist.insert(SI->findCaseValue(SimpleCond).getCaseSuccessor());
continue;
}
}
for (unsigned TIdx = 0, TSize = TI->getNumSuccessors(); TIdx != TSize;
++TIdx)
BBWorklist.insert(TI->getSuccessor(TIdx));
if (SingleBB && TI->getNumSuccessors() > 1) {
Threshold -= SingleBBBonus;
SingleBB = false;
}
}
if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall)
return false;
Threshold += VectorBonus;
return Cost < Threshold;
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void CallAnalyzer::dump() {
#define DEBUG_PRINT_STAT(x) dbgs() << " " #x ": " << x << "\n"
DEBUG_PRINT_STAT(NumConstantArgs);
DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs);
DEBUG_PRINT_STAT(NumAllocaArgs);
DEBUG_PRINT_STAT(NumConstantPtrCmps);
DEBUG_PRINT_STAT(NumConstantPtrDiffs);
DEBUG_PRINT_STAT(NumInstructionsSimplified);
DEBUG_PRINT_STAT(SROACostSavings);
DEBUG_PRINT_STAT(SROACostSavingsLost);
DEBUG_PRINT_STAT(ContainsNoDuplicateCall);
DEBUG_PRINT_STAT(Cost);
DEBUG_PRINT_STAT(Threshold);
DEBUG_PRINT_STAT(VectorBonus);
#undef DEBUG_PRINT_STAT
}
#endif
INITIALIZE_PASS_BEGIN(InlineCostAnalysis, "inline-cost", "Inline Cost Analysis",
true, true)
INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
INITIALIZE_PASS_END(InlineCostAnalysis, "inline-cost", "Inline Cost Analysis",
true, true)
char InlineCostAnalysis::ID = 0;
InlineCostAnalysis::InlineCostAnalysis() : CallGraphSCCPass(ID) {}
InlineCostAnalysis::~InlineCostAnalysis() {}
void InlineCostAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<TargetTransformInfo>();
CallGraphSCCPass::getAnalysisUsage(AU);
}
bool InlineCostAnalysis::runOnSCC(CallGraphSCC &SCC) {
TTI = &getAnalysis<TargetTransformInfo>();
return false;
}
InlineCost InlineCostAnalysis::getInlineCost(CallSite CS, int Threshold) {
return getInlineCost(CS, CS.getCalledFunction(), Threshold);
}
static bool attributeMatches(Function *F1, Function *F2,
Attribute::AttrKind Attr) {
return F1->hasFnAttribute(Attr) == F2->hasFnAttribute(Attr);
}
static bool functionsHaveCompatibleAttributes(Function *Caller,
Function *Callee) {
return attributeMatches(Caller, Callee, Attribute::SanitizeAddress) &&
attributeMatches(Caller, Callee, Attribute::SanitizeMemory) &&
attributeMatches(Caller, Callee, Attribute::SanitizeThread);
}
InlineCost InlineCostAnalysis::getInlineCost(CallSite CS, Function *Callee,
int Threshold) {
if (!Callee)
return llvm::InlineCost::getNever();
if (CS.hasFnAttr(Attribute::AlwaysInline)) {
if (isInlineViable(*Callee))
return llvm::InlineCost::getAlways();
return llvm::InlineCost::getNever();
}
if (!functionsHaveCompatibleAttributes(CS.getCaller(), Callee))
return llvm::InlineCost::getNever();
if (CS.getCaller()->hasFnAttribute(Attribute::OptimizeNone))
return llvm::InlineCost::getNever();
if (Callee->mayBeOverridden() ||
Callee->hasFnAttribute(Attribute::NoInline) || CS.isNoInline())
return llvm::InlineCost::getNever();
DEBUG(llvm::dbgs() << " Analyzing call of " << Callee->getName()
<< "...\n");
CallAnalyzer CA(Callee->getDataLayout(), *TTI, *Callee, Threshold);
bool ShouldInline = CA.analyzeCall(CS);
DEBUG(CA.dump());
if (!ShouldInline && CA.getCost() < CA.getThreshold())
return InlineCost::getNever();
if (ShouldInline && CA.getCost() >= CA.getThreshold())
return InlineCost::getAlways();
return llvm::InlineCost::get(CA.getCost(), CA.getThreshold());
}
bool InlineCostAnalysis::isInlineViable(Function &F) {
bool ReturnsTwice =
F.getAttributes().hasAttribute(AttributeSet::FunctionIndex,
Attribute::ReturnsTwice);
for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
if (isa<IndirectBrInst>(BI->getTerminator()) || BI->hasAddressTaken())
return false;
for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;
++II) {
CallSite CS(II);
if (!CS)
continue;
if (&F == CS.getCalledFunction())
return false;
if (!ReturnsTwice && CS.isCall() &&
cast<CallInst>(CS.getInstruction())->canReturnTwice())
return false;
}
}
return true;
}