// Special handling for calls.
if (isa<CallInst>(II) || isa<InvokeInst>(II)) {
- if (isa<DbgInfoIntrinsic>(II))
- continue; // Debug intrinsics don't count as size.
+ if (const IntrinsicInst *IntrinsicI = dyn_cast<IntrinsicInst>(II)) {
+ switch (IntrinsicI->getIntrinsicID()) {
+ default: break;
+ case Intrinsic::dbg_declare:
+ case Intrinsic::dbg_value:
+ case Intrinsic::invariant_start:
+ case Intrinsic::invariant_end:
+ case Intrinsic::lifetime_start:
+ case Intrinsic::lifetime_end:
+ case Intrinsic::objectsize:
+ case Intrinsic::ptr_annotation:
+ case Intrinsic::var_annotation:
+ // These intrinsics don't count as size.
+ continue;
+ }
+ }
ImmutableCallSite CS(cast<Instruction>(II));
// If a function is both internal and has a single use, then it is
// extremely likely to get inlined in the future (it was probably
// exposed by an interleaved devirtualization pass).
- if (F->hasInternalLinkage() && F->hasOneUse())
+ if (!CS.isNoInline() && F->hasInternalLinkage() && F->hasOneUse())
++NumInlineCandidates;
// If this call is to function itself, then the function is recursive.
// for example) would be referring to the original function, and this indirect
// jump would jump from the inlined copy of the function into the original
// function which is extremely undefined behavior.
+ // FIXME: This logic isn't really right; we can safely inline functions
+ // with indirectbr's as long as no other function or global references the
+ // blockaddress of a block within the current function. And as a QOI issue,
+ // if someone is using a blockaddress without an indirectbr, and that
+ // reference somehow ends up in another function or global, we probably
+ // don't want to inline this function.
if (isa<IndirectBrInst>(BB->getTerminator()))
containsIndirectBr = true;
NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB;
}
-// CountCodeReductionForConstant - Figure out an approximation for how many
-// instructions will be constant folded if the specified value is constant.
-//
-unsigned CodeMetrics::CountCodeReductionForConstant(Value *V) {
+unsigned InlineCostAnalyzer::FunctionInfo::countCodeReductionForConstant(
+ const CodeMetrics &Metrics, Value *V) {
unsigned Reduction = 0;
- for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){
- User *U = *UI;
- if (isa<BranchInst>(U) || isa<SwitchInst>(U)) {
- // We will be able to eliminate all but one of the successors.
- const TerminatorInst &TI = cast<TerminatorInst>(*U);
- const unsigned NumSucc = TI.getNumSuccessors();
- unsigned Instrs = 0;
- for (unsigned I = 0; I != NumSucc; ++I)
- Instrs += NumBBInsts[TI.getSuccessor(I)];
- // We don't know which blocks will be eliminated, so use the average size.
- Reduction += InlineConstants::InstrCost*Instrs*(NumSucc-1)/NumSucc;
- } else {
+ SmallVector<Value *, 4> Worklist;
+ Worklist.push_back(V);
+ do {
+ Value *V = Worklist.pop_back_val();
+ for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){
+ User *U = *UI;
+ if (isa<BranchInst>(U) || isa<SwitchInst>(U)) {
+ // We will be able to eliminate all but one of the successors.
+ const TerminatorInst &TI = cast<TerminatorInst>(*U);
+ const unsigned NumSucc = TI.getNumSuccessors();
+ unsigned Instrs = 0;
+ for (unsigned I = 0; I != NumSucc; ++I)
+ Instrs += Metrics.NumBBInsts.lookup(TI.getSuccessor(I));
+ // We don't know which blocks will be eliminated, so use the average size.
+ Reduction += InlineConstants::InstrCost*Instrs*(NumSucc-1)/NumSucc;
+ continue;
+ }
+
// Figure out if this instruction will be removed due to simple constant
// propagation.
Instruction &Inst = cast<Instruction>(*U);
AllOperandsConstant = false;
break;
}
+ if (!AllOperandsConstant)
+ continue;
- if (AllOperandsConstant) {
- // We will get to remove this instruction...
- Reduction += InlineConstants::InstrCost;
+ // We will get to remove this instruction...
+ Reduction += InlineConstants::InstrCost;
- // And any other instructions that use it which become constants
- // themselves.
- Reduction += CountCodeReductionForConstant(&Inst);
+ // And any other instructions that use it which become constants
+ // themselves.
+ Worklist.push_back(&Inst);
+ }
+ } while (!Worklist.empty());
+ return Reduction;
+}
+
+static unsigned countCodeReductionForAllocaICmp(const CodeMetrics &Metrics,
+ ICmpInst *ICI) {
+ unsigned Reduction = 0;
+
+ // Bail if this is comparing against a non-constant; there is nothing we can
+ // do there.
+ if (!isa<Constant>(ICI->getOperand(1)))
+ return Reduction;
+
+ // An icmp pred (alloca, C) becomes true if the predicate is true when
+ // equal and false otherwise.
+ bool Result = ICI->isTrueWhenEqual();
+
+ SmallVector<Instruction *, 4> Worklist;
+ Worklist.push_back(ICI);
+ do {
+ Instruction *U = Worklist.pop_back_val();
+ Reduction += InlineConstants::InstrCost;
+ for (Value::use_iterator UI = U->use_begin(), UE = U->use_end();
+ UI != UE; ++UI) {
+ Instruction *I = dyn_cast<Instruction>(*UI);
+ if (!I || I->mayHaveSideEffects()) continue;
+ if (I->getNumOperands() == 1)
+ Worklist.push_back(I);
+ if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
+ // If BO produces the same value as U, then the other operand is
+ // irrelevant and we can put it into the Worklist to continue
+ // deleting dead instructions. If BO produces the same value as the
+ // other operand, we can delete BO but that's it.
+ if (Result == true) {
+ if (BO->getOpcode() == Instruction::Or)
+ Worklist.push_back(I);
+ if (BO->getOpcode() == Instruction::And)
+ Reduction += InlineConstants::InstrCost;
+ } else {
+ if (BO->getOpcode() == Instruction::Or ||
+ BO->getOpcode() == Instruction::Xor)
+ Reduction += InlineConstants::InstrCost;
+ if (BO->getOpcode() == Instruction::And)
+ Worklist.push_back(I);
+ }
+ }
+ if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
+ BasicBlock *BB = BI->getSuccessor(Result ? 0 : 1);
+ if (BB->getSinglePredecessor())
+ Reduction
+ += InlineConstants::InstrCost * Metrics.NumBBInsts.lookup(BB);
}
}
- }
+ } while (!Worklist.empty());
+
return Reduction;
}
-// CountCodeReductionForAlloca - Figure out an approximation of how much smaller
-// the function will be if it is inlined into a context where an argument
-// becomes an alloca.
-//
-unsigned CodeMetrics::CountCodeReductionForAlloca(Value *V) {
+/// \brief Compute the reduction possible for a given instruction if we are able
+/// to SROA an alloca.
+///
+/// The reduction for this instruction is added to the SROAReduction output
+/// parameter. Returns false if this instruction is expected to defeat SROA in
+/// general.
+static bool countCodeReductionForSROAInst(Instruction *I,
+ SmallVectorImpl<Value *> &Worklist,
+ unsigned &SROAReduction) {
+ if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
+ if (!LI->isSimple())
+ return false;
+ SROAReduction += InlineConstants::InstrCost;
+ return true;
+ }
+
+ if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
+ if (!SI->isSimple())
+ return false;
+ SROAReduction += InlineConstants::InstrCost;
+ return true;
+ }
+
+ if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
+ // If the GEP has variable indices, we won't be able to do much with it.
+ if (!GEP->hasAllConstantIndices())
+ return false;
+ // A non-zero GEP will likely become a mask operation after SROA.
+ if (GEP->hasAllZeroIndices())
+ SROAReduction += InlineConstants::InstrCost;
+ Worklist.push_back(GEP);
+ return true;
+ }
+
+ if (BitCastInst *BCI = dyn_cast<BitCastInst>(I)) {
+ // Track pointer through bitcasts.
+ Worklist.push_back(BCI);
+ SROAReduction += InlineConstants::InstrCost;
+ return true;
+ }
+
+ // We just look for non-constant operands to ICmp instructions as those will
+ // defeat SROA. The actual reduction for these happens even without SROA.
+ if (ICmpInst *ICI = dyn_cast<ICmpInst>(I))
+ return isa<Constant>(ICI->getOperand(1));
+
+ if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
+ // SROA can handle a select of alloca iff all uses of the alloca are
+ // loads, and dereferenceable. We assume it's dereferenceable since
+ // we're told the input is an alloca.
+ for (Value::use_iterator UI = SI->use_begin(), UE = SI->use_end();
+ UI != UE; ++UI) {
+ LoadInst *LI = dyn_cast<LoadInst>(*UI);
+ if (LI == 0 || !LI->isSimple())
+ return false;
+ }
+ // We don't know whether we'll be deleting the rest of the chain of
+ // instructions from the SelectInst on, because we don't know whether
+ // the other side of the select is also an alloca or not.
+ return true;
+ }
+
+ if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+ switch (II->getIntrinsicID()) {
+ default:
+ return false;
+ case Intrinsic::memset:
+ case Intrinsic::memcpy:
+ case Intrinsic::memmove:
+ case Intrinsic::lifetime_start:
+ case Intrinsic::lifetime_end:
+ // SROA can usually chew through these intrinsics.
+ SROAReduction += InlineConstants::InstrCost;
+ return true;
+ }
+ }
+
+ // If there is some other strange instruction, we're not going to be
+ // able to do much if we inline this.
+ return false;
+}
+
+unsigned InlineCostAnalyzer::FunctionInfo::countCodeReductionForAlloca(
+ const CodeMetrics &Metrics, Value *V) {
if (!V->getType()->isPointerTy()) return 0; // Not a pointer
unsigned Reduction = 0;
- for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){
- Instruction *I = cast<Instruction>(*UI);
- if (isa<LoadInst>(I) || isa<StoreInst>(I))
- Reduction += InlineConstants::InstrCost;
- else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
- // If the GEP has variable indices, we won't be able to do much with it.
- if (GEP->hasAllConstantIndices())
- Reduction += CountCodeReductionForAlloca(GEP);
- } else if (BitCastInst *BCI = dyn_cast<BitCastInst>(I)) {
- // Track pointer through bitcasts.
- Reduction += CountCodeReductionForAlloca(BCI);
- } else {
- // If there is some other strange instruction, we're not going to be able
- // to do much if we inline this.
- return 0;
+ unsigned SROAReduction = 0;
+ bool CanSROAAlloca = true;
+
+ SmallVector<Value *, 4> Worklist;
+ Worklist.push_back(V);
+ do {
+ Value *V = Worklist.pop_back_val();
+ for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
+ UI != E; ++UI){
+ Instruction *I = cast<Instruction>(*UI);
+
+ if (ICmpInst *ICI = dyn_cast<ICmpInst>(I))
+ Reduction += countCodeReductionForAllocaICmp(Metrics, ICI);
+
+ if (CanSROAAlloca)
+ CanSROAAlloca = countCodeReductionForSROAInst(I, Worklist,
+ SROAReduction);
}
- }
+ } while (!Worklist.empty());
- return Reduction;
+ return Reduction + (CanSROAAlloca ? SROAReduction : 0);
+}
+
+void InlineCostAnalyzer::FunctionInfo::countCodeReductionForPointerPair(
+ const CodeMetrics &Metrics, DenseMap<Value *, unsigned> &PointerArgs,
+ Value *V, unsigned ArgIdx) {
+ SmallVector<Value *, 4> Worklist;
+ Worklist.push_back(V);
+ do {
+ Value *V = Worklist.pop_back_val();
+ for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
+ UI != E; ++UI){
+ Instruction *I = cast<Instruction>(*UI);
+
+ if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
+ // If the GEP has variable indices, we won't be able to do much with it.
+ if (!GEP->hasAllConstantIndices())
+ continue;
+ // Unless the GEP is in-bounds, some comparisons will be non-constant.
+ // Fortunately, the real-world cases where this occurs uses in-bounds
+ // GEPs, and so we restrict the optimization to them here.
+ if (!GEP->isInBounds())
+ continue;
+
+ // Constant indices just change the constant offset. Add the resulting
+ // value both to our worklist for this argument, and to the set of
+ // viable paired values with future arguments.
+ PointerArgs[GEP] = ArgIdx;
+ Worklist.push_back(GEP);
+ continue;
+ }
+
+ // Track pointer through casts. Even when the result is not a pointer, it
+ // remains a constant relative to constants derived from other constant
+ // pointers.
+ if (CastInst *CI = dyn_cast<CastInst>(I)) {
+ PointerArgs[CI] = ArgIdx;
+ Worklist.push_back(CI);
+ continue;
+ }
+
+ // There are two instructions which produce a strict constant value when
+ // applied to two related pointer values. Ignore everything else.
+ if (!isa<ICmpInst>(I) && I->getOpcode() != Instruction::Sub)
+ continue;
+ assert(I->getNumOperands() == 2);
+
+ // Ensure that the two operands are in our set of potentially paired
+ // pointers (or are derived from them).
+ Value *OtherArg = I->getOperand(0);
+ if (OtherArg == V)
+ OtherArg = I->getOperand(1);
+ DenseMap<Value *, unsigned>::const_iterator ArgIt
+ = PointerArgs.find(OtherArg);
+ if (ArgIt == PointerArgs.end())
+ continue;
+ std::pair<unsigned, unsigned> ArgPair(ArgIt->second, ArgIdx);
+ if (ArgPair.first > ArgPair.second)
+ std::swap(ArgPair.first, ArgPair.second);
+
+ PointerArgPairWeights[ArgPair]
+ += countCodeReductionForConstant(Metrics, I);
+ }
+ } while (!Worklist.empty());
}
/// analyzeFunction - Fill in the current structure with information gleaned
/// from the specified function.
void CodeMetrics::analyzeFunction(Function *F, const TargetData *TD) {
- // If this function contains a call to setjmp or _setjmp, never inline
- // it. This is a hack because we depend on the user marking their local
- // variables as volatile if they are live across a setjmp call, and they
- // probably won't do this in callers.
- if (F->callsFunctionThatReturnsTwice())
- callsSetJmp = true;
+ // If this function contains a call that "returns twice" (e.g., setjmp or
+ // _setjmp) and it isn't marked with "returns twice" itself, never inline it.
+ // This is a hack because we depend on the user marking their local variables
+ // as volatile if they are live across a setjmp call, and they probably
+ // won't do this in callers.
+ exposesReturnsTwice = F->callsFunctionThatReturnsTwice() &&
+ !F->hasFnAttr(Attribute::ReturnsTwice);
// Look at the size of the callee.
for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
if (Metrics.NumRets==1)
--Metrics.NumInsts;
- // Check out all of the arguments to the function, figuring out how much
- // code can be eliminated if one of the arguments is a constant.
ArgumentWeights.reserve(F->arg_size());
- for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I)
- ArgumentWeights.push_back(ArgInfo(Metrics.CountCodeReductionForConstant(I),
- Metrics.CountCodeReductionForAlloca(I)));
+ DenseMap<Value *, unsigned> PointerArgs;
+ unsigned ArgIdx = 0;
+ for (Function::arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E;
+ ++I, ++ArgIdx) {
+ // Count how much code can be eliminated if one of the arguments is
+ // a constant or an alloca.
+ ArgumentWeights.push_back(ArgInfo(countCodeReductionForConstant(Metrics, I),
+ countCodeReductionForAlloca(Metrics, I)));
+
+ // If the argument is a pointer, also check for pairs of pointers where
+ // knowing a fixed offset between them allows simplification. This pattern
+ // arises mostly due to STL algorithm patterns where pointers are used as
+ // random access iterators.
+ if (!I->getType()->isPointerTy())
+ continue;
+ PointerArgs[I] = ArgIdx;
+ countCodeReductionForPointerPair(Metrics, PointerArgs, I, ArgIdx);
+ }
}
/// NeverInline - returns true if the function should never be inlined into
/// any caller
bool InlineCostAnalyzer::FunctionInfo::NeverInline() {
- return (Metrics.callsSetJmp || Metrics.isRecursive ||
+ return (Metrics.exposesReturnsTwice || Metrics.isRecursive ||
Metrics.containsIndirectBr);
}
-// getSpecializationBonus - The heuristic used to determine the per-call
-// performance boost for using a specialization of Callee with argument
-// specializedArgNo replaced by a constant.
-int InlineCostAnalyzer::getSpecializationBonus(Function *Callee,
- SmallVectorImpl<unsigned> &SpecializedArgNos)
-{
- if (Callee->mayBeOverridden())
- return 0;
-
- int Bonus = 0;
- // If this function uses the coldcc calling convention, prefer not to
- // specialize it.
- if (Callee->getCallingConv() == CallingConv::Cold)
- Bonus -= InlineConstants::ColdccPenalty;
-
- // Get information about the callee.
- FunctionInfo *CalleeFI = &CachedFunctionInfo[Callee];
-
- // If we haven't calculated this information yet, do so now.
- if (CalleeFI->Metrics.NumBlocks == 0)
- CalleeFI->analyzeFunction(Callee, TD);
-
- unsigned ArgNo = 0;
- unsigned i = 0;
- for (Function::arg_iterator I = Callee->arg_begin(), E = Callee->arg_end();
- I != E; ++I, ++ArgNo)
- if (ArgNo == SpecializedArgNos[i]) {
- ++i;
- Bonus += CountBonusForConstant(I);
- }
-
- // Calls usually take a long time, so they make the specialization gain
- // smaller.
- Bonus -= CalleeFI->Metrics.NumCalls * InlineConstants::CallPenalty;
-
- return Bonus;
-}
// ConstantFunctionBonus - Figure out how much of a bonus we can get for
// possibly devirtualizing a function. We'll subtract the size of the function
InlineCost -= CalleeFI->ArgumentWeights[ArgNo].ConstantWeight;
}
+ const DenseMap<std::pair<unsigned, unsigned>, unsigned> &ArgPairWeights
+ = CalleeFI->PointerArgPairWeights;
+ for (DenseMap<std::pair<unsigned, unsigned>, unsigned>::const_iterator I
+ = ArgPairWeights.begin(), E = ArgPairWeights.end();
+ I != E; ++I)
+ if (CS.getArgument(I->first.first)->stripInBoundsConstantOffsets() ==
+ CS.getArgument(I->first.second)->stripInBoundsConstantOffsets())
+ InlineCost -= I->second;
+
// Each argument passed in has a cost at both the caller and the callee
// sides. Measurements show that each argument costs about the same as an
// instruction.
InlineCost += CalleeFI->Metrics.NumCalls * InlineConstants::CallPenalty;
// Look at the size of the callee. Each instruction counts as 5.
- InlineCost += CalleeFI->Metrics.NumInsts*InlineConstants::InstrCost;
+ InlineCost += CalleeFI->Metrics.NumInsts * InlineConstants::InstrCost;
return InlineCost;
}
return llvm::InlineCost::get(InlineCost);
}
-// getSpecializationCost - The heuristic used to determine the code-size
-// impact of creating a specialized version of Callee with argument
-// SpecializedArgNo replaced by a constant.
-InlineCost InlineCostAnalyzer::getSpecializationCost(Function *Callee,
- SmallVectorImpl<unsigned> &SpecializedArgNos)
-{
- // Don't specialize functions which can be redefined at link-time to mean
- // something else.
- if (Callee->mayBeOverridden())
- return llvm::InlineCost::getNever();
-
- // Get information about the callee.
- FunctionInfo *CalleeFI = &CachedFunctionInfo[Callee];
-
- // If we haven't calculated this information yet, do so now.
- if (CalleeFI->Metrics.NumBlocks == 0)
- CalleeFI->analyzeFunction(Callee, TD);
-
- int Cost = 0;
-
- // Look at the original size of the callee. Each instruction counts as 5.
- Cost += CalleeFI->Metrics.NumInsts * InlineConstants::InstrCost;
-
- // Offset that with the amount of code that can be constant-folded
- // away with the given arguments replaced by constants.
- for (SmallVectorImpl<unsigned>::iterator an = SpecializedArgNos.begin(),
- ae = SpecializedArgNos.end(); an != ae; ++an)
- Cost -= CalleeFI->ArgumentWeights[*an].ConstantWeight;
-
- return llvm::InlineCost::get(Cost);
-}
-
// getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a
// higher threshold to determine if the function call should be inlined.
float InlineCostAnalyzer::getInlineFudgeFactor(CallSite CS) {
// FIXME: If any of these three are true for the callee, the callee was
// not inlined into the caller, so I think they're redundant here.
- CallerMetrics.callsSetJmp |= CalleeMetrics.callsSetJmp;
+ CallerMetrics.exposesReturnsTwice |= CalleeMetrics.exposesReturnsTwice;
CallerMetrics.isRecursive |= CalleeMetrics.isRecursive;
CallerMetrics.containsIndirectBr |= CalleeMetrics.containsIndirectBr;
projects / oota-llvm.git / blobdiff