#define DEBUG_TYPE "inline"
#include "llvm/Module.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Analysis/InlineCost.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/IPO/InlinerPass.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;
STATISTIC(NumInlined, "Number of functions inlined");
STATISTIC(NumCallsDeleted, "Number of call sites deleted, not inlined");
STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
STATISTIC(NumMergedAllocas, "Number of allocas merged together");
static cl::opt<int>
InlineLimit("inline-threshold", cl::Hidden, cl::init(225), cl::ZeroOrMore,
cl::desc("Control the amount of inlining to perform (default = 225)"));
static cl::opt<int>
HintThreshold("inlinehint-threshold", cl::Hidden, cl::init(325),
cl::desc("Threshold for inlining functions with inline hint"));
const int OptSizeThreshold = 75;
Inliner::Inliner(char &ID)
: CallGraphSCCPass(ID), InlineThreshold(InlineLimit), InsertLifetime(true) {}
Inliner::Inliner(char &ID, int Threshold, bool InsertLifetime)
: CallGraphSCCPass(ID), InlineThreshold(InlineLimit.getNumOccurrences() > 0 ?
InlineLimit : Threshold),
InsertLifetime(InsertLifetime) {}
void Inliner::getAnalysisUsage(AnalysisUsage &Info) const {
CallGraphSCCPass::getAnalysisUsage(Info);
}
typedef DenseMap<ArrayType*, std::vector<AllocaInst*> >
InlinedArrayAllocasTy;
static bool InlineCallIfPossible(CallSite CS, InlineFunctionInfo &IFI,
InlinedArrayAllocasTy &InlinedArrayAllocas,
int InlineHistory, bool InsertLifetime) {
Function *Callee = CS.getCalledFunction();
Function *Caller = CS.getCaller();
if (!InlineFunction(CS, IFI, InsertLifetime))
return false;
if (Callee->hasFnAttr(Attribute::StackProtectReq))
Caller->addFnAttr(Attribute::StackProtectReq);
else if (Callee->hasFnAttr(Attribute::StackProtect) &&
!Caller->hasFnAttr(Attribute::StackProtectReq))
Caller->addFnAttr(Attribute::StackProtect);
SmallPtrSet<AllocaInst*, 16> UsedAllocas;
if (InlineHistory != -1) return true;
for (unsigned AllocaNo = 0, e = IFI.StaticAllocas.size();
AllocaNo != e; ++AllocaNo) {
AllocaInst *AI = IFI.StaticAllocas[AllocaNo];
ArrayType *ATy = dyn_cast<ArrayType>(AI->getAllocatedType());
if (ATy == 0 || AI->isArrayAllocation())
continue;
std::vector<AllocaInst*> &AllocasForType = InlinedArrayAllocas[ATy];
bool MergedAwayAlloca = false;
for (unsigned i = 0, e = AllocasForType.size(); i != e; ++i) {
AllocaInst *AvailableAlloca = AllocasForType[i];
if (AvailableAlloca->getParent() != AI->getParent())
continue;
if (!UsedAllocas.insert(AvailableAlloca))
continue;
DEBUG(dbgs() << " ***MERGED ALLOCA: " << *AI << "\n\t\tINTO: "
<< *AvailableAlloca << '\n');
AI->replaceAllUsesWith(AvailableAlloca);
AI->eraseFromParent();
MergedAwayAlloca = true;
++NumMergedAllocas;
IFI.StaticAllocas[AllocaNo] = 0;
break;
}
if (MergedAwayAlloca)
continue;
AllocasForType.push_back(AI);
UsedAllocas.insert(AI);
}
return true;
}
unsigned Inliner::getInlineThreshold(CallSite CS) const {
int thres = InlineThreshold;
Function *Caller = CS.getCaller();
if (Caller && !Caller->isDeclaration() &&
Caller->hasFnAttr(Attribute::OptimizeForSize) &&
InlineLimit.getNumOccurrences() == 0)
thres = OptSizeThreshold;
Function *Callee = CS.getCalledFunction();
if (HintThreshold > thres && Callee && !Callee->isDeclaration() &&
Callee->hasFnAttr(Attribute::InlineHint))
thres = HintThreshold;
return thres;
}
bool Inliner::shouldInline(CallSite CS) {
InlineCost IC = getInlineCost(CS);
if (IC.isAlways()) {
DEBUG(dbgs() << " Inlining: cost=always"
<< ", Call: " << *CS.getInstruction() << "\n");
return true;
}
if (IC.isNever()) {
DEBUG(dbgs() << " NOT Inlining: cost=never"
<< ", Call: " << *CS.getInstruction() << "\n");
return false;
}
int Cost = IC.getValue();
Function *Caller = CS.getCaller();
int CurrentThreshold = getInlineThreshold(CS);
float FudgeFactor = getInlineFudgeFactor(CS);
int AdjThreshold = (int)(CurrentThreshold * FudgeFactor);
if (Cost >= AdjThreshold) {
DEBUG(dbgs() << " NOT Inlining: cost=" << Cost
<< ", thres=" << AdjThreshold
<< ", Call: " << *CS.getInstruction() << "\n");
return false;
}
if (Caller->hasLocalLinkage()) {
int TotalSecondaryCost = 0;
bool outerCallsFound = false;
bool callerWillBeRemoved = true;
bool inliningPreventsSomeOuterInline = false;
for (Value::use_iterator I = Caller->use_begin(), E =Caller->use_end();
I != E; ++I) {
CallSite CS2(*I);
if (!CS2 || CS2.getCalledFunction() != Caller) {
callerWillBeRemoved = false;
continue;
}
InlineCost IC2 = getInlineCost(CS2);
if (IC2.isNever())
callerWillBeRemoved = false;
if (IC2.isAlways() || IC2.isNever())
continue;
outerCallsFound = true;
int Cost2 = IC2.getValue();
int CurrentThreshold2 = getInlineThreshold(CS2);
float FudgeFactor2 = getInlineFudgeFactor(CS2);
if (Cost2 >= (int)(CurrentThreshold2 * FudgeFactor2))
callerWillBeRemoved = false;
if (Cost2 < (int)(CurrentThreshold2 * FudgeFactor2) &&
Cost2 + Cost - (InlineConstants::CallPenalty + 1) >=
(int)(CurrentThreshold2 * FudgeFactor2)) {
inliningPreventsSomeOuterInline = true;
TotalSecondaryCost += Cost2;
}
}
if (callerWillBeRemoved && Caller->use_begin() != Caller->use_end())
TotalSecondaryCost += InlineConstants::LastCallToStaticBonus;
if (outerCallsFound && inliningPreventsSomeOuterInline &&
TotalSecondaryCost < Cost) {
DEBUG(dbgs() << " NOT Inlining: " << *CS.getInstruction() <<
" Cost = " << Cost <<
", outer Cost = " << TotalSecondaryCost << '\n');
return false;
}
}
DEBUG(dbgs() << " Inlining: cost=" << Cost
<< ", thres=" << AdjThreshold
<< ", Call: " << *CS.getInstruction() << '\n');
return true;
}
static bool InlineHistoryIncludes(Function *F, int InlineHistoryID,
const SmallVectorImpl<std::pair<Function*, int> > &InlineHistory) {
while (InlineHistoryID != -1) {
assert(unsigned(InlineHistoryID) < InlineHistory.size() &&
"Invalid inline history ID");
if (InlineHistory[InlineHistoryID].first == F)
return true;
InlineHistoryID = InlineHistory[InlineHistoryID].second;
}
return false;
}
bool Inliner::runOnSCC(CallGraphSCC &SCC) {
CallGraph &CG = getAnalysis<CallGraph>();
const TargetData *TD = getAnalysisIfAvailable<TargetData>();
SmallPtrSet<Function*, 8> SCCFunctions;
DEBUG(dbgs() << "Inliner visiting SCC:");
for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
Function *F = (*I)->getFunction();
if (F) SCCFunctions.insert(F);
DEBUG(dbgs() << " " << (F ? F->getName() : "INDIRECTNODE"));
}
SmallVector<std::pair<CallSite, int>, 16> CallSites;
SmallVector<std::pair<Function*, int>, 8> InlineHistory;
for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
Function *F = (*I)->getFunction();
if (!F) continue;
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
CallSite CS(cast<Value>(I));
if (!CS || isa<IntrinsicInst>(I))
continue;
if (CS.getCalledFunction() && CS.getCalledFunction()->isDeclaration())
continue;
CallSites.push_back(std::make_pair(CS, -1));
}
}
DEBUG(dbgs() << ": " << CallSites.size() << " call sites.\n");
if (CallSites.empty())
return false;
unsigned FirstCallInSCC = CallSites.size();
for (unsigned i = 0; i < FirstCallInSCC; ++i)
if (Function *F = CallSites[i].first.getCalledFunction())
if (SCCFunctions.count(F))
std::swap(CallSites[i--], CallSites[--FirstCallInSCC]);
InlinedArrayAllocasTy InlinedArrayAllocas;
InlineFunctionInfo InlineInfo(&CG, TD);
bool Changed = false;
bool LocalChange;
do {
LocalChange = false;
for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
CallSite CS = CallSites[CSi].first;
Function *Caller = CS.getCaller();
Function *Callee = CS.getCalledFunction();
if (isInstructionTriviallyDead(CS.getInstruction())) {
DEBUG(dbgs() << " -> Deleting dead call: "
<< *CS.getInstruction() << "\n");
CG[Caller]->removeCallEdgeFor(CS);
CS.getInstruction()->eraseFromParent();
++NumCallsDeleted;
growCachedCostInfo(Caller, NULL);
} else {
if (Callee == 0 || Callee->isDeclaration()) continue;
int InlineHistoryID = CallSites[CSi].second;
if (InlineHistoryID != -1 &&
InlineHistoryIncludes(Callee, InlineHistoryID, InlineHistory))
continue;
if (!shouldInline(CS))
continue;
if (!InlineCallIfPossible(CS, InlineInfo, InlinedArrayAllocas,
InlineHistoryID, InsertLifetime))
continue;
++NumInlined;
if (!InlineInfo.InlinedCalls.empty()) {
int NewHistoryID = InlineHistory.size();
InlineHistory.push_back(std::make_pair(Callee, InlineHistoryID));
for (unsigned i = 0, e = InlineInfo.InlinedCalls.size();
i != e; ++i) {
Value *Ptr = InlineInfo.InlinedCalls[i];
CallSites.push_back(std::make_pair(CallSite(Ptr), NewHistoryID));
}
}
growCachedCostInfo(Caller, Callee);
}
if (Callee && Callee->use_empty() && Callee->hasLocalLinkage() &&
!SCCFunctions.count(Callee) &&
CG[Callee]->getNumReferences() == 0) {
DEBUG(dbgs() << " -> Deleting dead function: "
<< Callee->getName() << "\n");
CallGraphNode *CalleeNode = CG[Callee];
CalleeNode->removeAllCalledFunctions();
resetCachedCostInfo(Callee);
delete CG.removeFunctionFromModule(CalleeNode);
++NumDeleted;
}
if (SCC.isSingular()) {
CallSites[CSi] = CallSites.back();
CallSites.pop_back();
} else {
CallSites.erase(CallSites.begin()+CSi);
}
--CSi;
Changed = true;
LocalChange = true;
}
} while (LocalChange);
return Changed;
}
bool Inliner::doFinalization(CallGraph &CG) {
return removeDeadFunctions(CG);
}
bool Inliner::removeDeadFunctions(CallGraph &CG,
SmallPtrSet<const Function *, 16> *DNR) {
SmallPtrSet<CallGraphNode*, 16> FunctionsToRemove;
for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) {
CallGraphNode *CGN = I->second;
if (CGN->getFunction() == 0)
continue;
Function *F = CGN->getFunction();
F->removeDeadConstantUsers();
if (DNR && DNR->count(F))
continue;
if (!F->isDefTriviallyDead())
continue;
CGN->removeAllCalledFunctions();
CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN);
FunctionsToRemove.insert(CGN);
}
bool Changed = false;
for (SmallPtrSet<CallGraphNode*, 16>::iterator I = FunctionsToRemove.begin(),
E = FunctionsToRemove.end(); I != E; ++I) {
resetCachedCostInfo((*I)->getFunction());
delete CG.removeFunctionFromModule(*I);
++NumDeleted;
Changed = true;
}
return Changed;
}