X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FInliner.cpp;h=57f3e772b5698fa416e51f38a8dfb19ae63a6123;hb=98a42b2fc39f3fc46905fb98078cce4ce4e0a827;hp=b589792022a709780be0e39f84768f908692cfa8;hpb=16581bf931c0ccf2f8993397acfa4e1d509a68dc;p=oota-llvm.git diff --git a/lib/Transforms/IPO/Inliner.cpp b/lib/Transforms/IPO/Inliner.cpp index b589792022a..57f3e772b56 100644 --- a/lib/Transforms/IPO/Inliner.cpp +++ b/lib/Transforms/IPO/Inliner.cpp @@ -18,46 +18,71 @@ #include "llvm/Instructions.h" #include "llvm/IntrinsicInst.h" #include "llvm/Analysis/CallGraph.h" -#include "llvm/Support/CallSite.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" -#include 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 +InlineLimit("inline-threshold", cl::Hidden, cl::init(225), cl::ZeroOrMore, + cl::desc("Control the amount of inlining to perform (default = 225)")); static cl::opt -InlineLimit("inline-threshold", cl::Hidden, cl::init(200), - cl::desc("Control the amount of inlining to perform (default = 200)")); +HintThreshold("inlinehint-threshold", cl::Hidden, cl::init(325), + cl::desc("Threshold for inlining functions with inline hint")); + +// Threshold to use when optsize is specified (and there is no -inline-limit). +const int OptSizeThreshold = 75; -Inliner::Inliner(void *ID) +Inliner::Inliner(char &ID) : CallGraphSCCPass(ID), InlineThreshold(InlineLimit) {} -Inliner::Inliner(void *ID, int Threshold) - : CallGraphSCCPass(ID), InlineThreshold(Threshold) {} +Inliner::Inliner(char &ID, int Threshold) + : CallGraphSCCPass(ID), InlineThreshold(InlineLimit.getNumOccurrences() > 0 ? + InlineLimit : Threshold) {} /// getAnalysisUsage - For this class, we declare that we require and preserve /// the call graph. If the derived class implements this method, it should /// always explicitly call the implementation here. void Inliner::getAnalysisUsage(AnalysisUsage &Info) const { - Info.addRequired(); CallGraphSCCPass::getAnalysisUsage(Info); } -// InlineCallIfPossible - If it is possible to inline the specified call site, -// do so and update the CallGraph for this operation. -bool Inliner::InlineCallIfPossible(CallSite CS, CallGraph &CG, - const SmallPtrSet &SCCFunctions, - const TargetData &TD) { + +typedef DenseMap > +InlinedArrayAllocasTy; + +/// InlineCallIfPossible - If it is possible to inline the specified call site, +/// do so and update the CallGraph for this operation. +/// +/// This function also does some basic book-keeping to update the IR. The +/// InlinedArrayAllocas map keeps track of any allocas that are already +/// available from other functions inlined into the caller. If we are able to +/// inline this call site we attempt to reuse already available allocas or add +/// any new allocas to the set if not possible. +static bool InlineCallIfPossible(CallSite CS, InlineFunctionInfo &IFI, + InlinedArrayAllocasTy &InlinedArrayAllocas, + int InlineHistory) { Function *Callee = CS.getCalledFunction(); Function *Caller = CS.getCaller(); - if (!InlineFunction(CS, &CG, &TD)) return false; + // Try to inline the function. Get the list of static allocas that were + // inlined. + if (!InlineFunction(CS, IFI)) + return false; // If the inlined function had a higher stack protection level than the // calling function, then bump up the caller's stack protection level. @@ -67,101 +92,304 @@ bool Inliner::InlineCallIfPossible(CallSite CS, CallGraph &CG, !Caller->hasFnAttr(Attribute::StackProtectReq)) Caller->addFnAttr(Attribute::StackProtect); - // If we inlined the last possible call site to the function, delete the - // function body now. - if (Callee->use_empty() && Callee->hasLocalLinkage() && - !SCCFunctions.count(Callee)) { - DOUT << " -> Deleting dead function: " << Callee->getName() << "\n"; - CallGraphNode *CalleeNode = CG[Callee]; - - // Remove any call graph edges from the callee to its callees. - CalleeNode->removeAllCalledFunctions(); - - resetCachedCostInfo(CalleeNode->getFunction()); + // Look at all of the allocas that we inlined through this call site. If we + // have already inlined other allocas through other calls into this function, + // then we know that they have disjoint lifetimes and that we can merge them. + // + // There are many heuristics possible for merging these allocas, and the + // different options have different tradeoffs. One thing that we *really* + // don't want to hurt is SRoA: once inlining happens, often allocas are no + // longer address taken and so they can be promoted. + // + // Our "solution" for that is to only merge allocas whose outermost type is an + // array type. These are usually not promoted because someone is using a + // variable index into them. These are also often the most important ones to + // merge. + // + // A better solution would be to have real memory lifetime markers in the IR + // and not have the inliner do any merging of allocas at all. This would + // allow the backend to do proper stack slot coloring of all allocas that + // *actually make it to the backend*, which is really what we want. + // + // Because we don't have this information, we do this simple and useful hack. + // + SmallPtrSet UsedAllocas; + + // When processing our SCC, check to see if CS was inlined from some other + // call site. For example, if we're processing "A" in this code: + // A() { B() } + // B() { x = alloca ... C() } + // C() { y = alloca ... } + // Assume that C was not inlined into B initially, and so we're processing A + // and decide to inline B into A. Doing this makes an alloca available for + // reuse and makes a callsite (C) available for inlining. When we process + // the C call site we don't want to do any alloca merging between X and Y + // because their scopes are not disjoint. We could make this smarter by + // keeping track of the inline history for each alloca in the + // InlinedArrayAllocas but this isn't likely to be a significant win. + if (InlineHistory != -1) // Only do merging for top-level call sites in SCC. + return true; + + // Loop over all the allocas we have so far and see if they can be merged with + // a previously inlined alloca. If not, remember that we had it. + for (unsigned AllocaNo = 0, e = IFI.StaticAllocas.size(); + AllocaNo != e; ++AllocaNo) { + AllocaInst *AI = IFI.StaticAllocas[AllocaNo]; + + // Don't bother trying to merge array allocations (they will usually be + // canonicalized to be an allocation *of* an array), or allocations whose + // type is not itself an array (because we're afraid of pessimizing SRoA). + const ArrayType *ATy = dyn_cast(AI->getAllocatedType()); + if (ATy == 0 || AI->isArrayAllocation()) + continue; + + // Get the list of all available allocas for this array type. + std::vector &AllocasForType = InlinedArrayAllocas[ATy]; + + // Loop over the allocas in AllocasForType to see if we can reuse one. Note + // that we have to be careful not to reuse the same "available" alloca for + // multiple different allocas that we just inlined, we use the 'UsedAllocas' + // set to keep track of which "available" allocas are being used by this + // function. Also, AllocasForType can be empty of course! + bool MergedAwayAlloca = false; + for (unsigned i = 0, e = AllocasForType.size(); i != e; ++i) { + AllocaInst *AvailableAlloca = AllocasForType[i]; + + // The available alloca has to be in the right function, not in some other + // function in this SCC. + if (AvailableAlloca->getParent() != AI->getParent()) + continue; + + // If the inlined function already uses this alloca then we can't reuse + // it. + if (!UsedAllocas.insert(AvailableAlloca)) + continue; + + // Otherwise, we *can* reuse it, RAUW AI into AvailableAlloca and declare + // success! + DEBUG(dbgs() << " ***MERGED ALLOCA: " << *AI << "\n\t\tINTO: " + << *AvailableAlloca << '\n'); + + AI->replaceAllUsesWith(AvailableAlloca); + AI->eraseFromParent(); + MergedAwayAlloca = true; + ++NumMergedAllocas; + IFI.StaticAllocas[AllocaNo] = 0; + break; + } - // Removing the node for callee from the call graph and delete it. - delete CG.removeFunctionFromModule(CalleeNode); - ++NumDeleted; + // If we already nuked the alloca, we're done with it. + if (MergedAwayAlloca) + continue; + + // If we were unable to merge away the alloca either because there are no + // allocas of the right type available or because we reused them all + // already, remember that this alloca came from an inlined function and mark + // it used so we don't reuse it for other allocas from this inline + // operation. + AllocasForType.push_back(AI); + UsedAllocas.insert(AI); } + return true; } - + +unsigned Inliner::getInlineThreshold(CallSite CS) const { + int thres = InlineThreshold; + + // Listen to optsize when -inline-limit is not given. + Function *Caller = CS.getCaller(); + if (Caller && !Caller->isDeclaration() && + Caller->hasFnAttr(Attribute::OptimizeForSize) && + InlineLimit.getNumOccurrences() == 0) + thres = OptSizeThreshold; + + // Listen to inlinehint when it would increase the threshold. + Function *Callee = CS.getCalledFunction(); + if (HintThreshold > thres && Callee && !Callee->isDeclaration() && + Callee->hasFnAttr(Attribute::InlineHint)) + thres = HintThreshold; + + return thres; +} + /// shouldInline - Return true if the inliner should attempt to inline /// at the given CallSite. bool Inliner::shouldInline(CallSite CS) { InlineCost IC = getInlineCost(CS); - float FudgeFactor = getInlineFudgeFactor(CS); if (IC.isAlways()) { - DOUT << " Inlining: cost=always" - << ", Call: " << *CS.getInstruction(); + DEBUG(dbgs() << " Inlining: cost=always" + << ", Call: " << *CS.getInstruction() << "\n"); return true; } if (IC.isNever()) { - DOUT << " NOT Inlining: cost=never" - << ", Call: " << *CS.getInstruction(); + DEBUG(dbgs() << " NOT Inlining: cost=never" + << ", Call: " << *CS.getInstruction() << "\n"); return false; } int Cost = IC.getValue(); - int CurrentThreshold = InlineThreshold; - Function *Fn = CS.getCaller(); - if (Fn && !Fn->isDeclaration() - && Fn->hasFnAttr(Attribute::OptimizeForSize) - && InlineThreshold != 50) { - CurrentThreshold = 50; + 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 (Cost >= (int)(CurrentThreshold * FudgeFactor)) { - DOUT << " NOT Inlining: cost=" << Cost - << ", Call: " << *CS.getInstruction(); - return false; - } else { - DOUT << " Inlining: cost=" << Cost - << ", Call: " << *CS.getInstruction(); - return true; + // Try to detect the case where the current inlining candidate caller + // (call it B) is a static function and is an inlining candidate elsewhere, + // and the current candidate callee (call it C) is large enough that + // inlining it into B would make B too big to inline later. In these + // circumstances it may be best not to inline C into B, but to inline B + // into its callers. + if (Caller->hasLocalLinkage()) { + int TotalSecondaryCost = 0; + bool outerCallsFound = false; + // This bool tracks what happens if we do NOT inline C into B. + bool callerWillBeRemoved = true; + // This bool tracks what happens if we DO inline C into B. + bool inliningPreventsSomeOuterInline = false; + for (Value::use_iterator I = Caller->use_begin(), E =Caller->use_end(); + I != E; ++I) { + CallSite CS2(*I); + + // If this isn't a call to Caller (it could be some other sort + // of reference) skip it. Such references will prevent the caller + // from being removed. + 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; + + // See if we have this case. We subtract off the penalty + // for the call instruction, which we would be deleting. + if (Cost2 < (int)(CurrentThreshold2 * FudgeFactor2) && + Cost2 + Cost - (InlineConstants::CallPenalty + 1) >= + (int)(CurrentThreshold2 * FudgeFactor2)) { + inliningPreventsSomeOuterInline = true; + TotalSecondaryCost += Cost2; + } + } + // If all outer calls to Caller would get inlined, the cost for the last + // one is set very low by getInlineCost, in anticipation that Caller will + // be removed entirely. We did not account for this above unless there + // is only one caller of Caller. + 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; } -bool Inliner::runOnSCC(const std::vector &SCC) { +/// InlineHistoryIncludes - Return true if the specified inline history ID +/// indicates an inline history that includes the specified function. +static bool InlineHistoryIncludes(Function *F, int InlineHistoryID, + const SmallVectorImpl > &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(); - TargetData &TD = getAnalysis(); + const TargetData *TD = getAnalysisIfAvailable(); SmallPtrSet SCCFunctions; - DOUT << "Inliner visiting SCC:"; - for (unsigned i = 0, e = SCC.size(); i != e; ++i) { - Function *F = SCC[i]->getFunction(); + 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); - DOUT << " " << (F ? F->getName() : "INDIRECTNODE"); + DEBUG(dbgs() << " " << (F ? F->getName() : "INDIRECTNODE")); } // Scan through and identify all call sites ahead of time so that we only // inline call sites in the original functions, not call sites that result // from inlining other functions. - std::vector CallSites; - - for (unsigned i = 0, e = SCC.size(); i != e; ++i) - if (Function *F = SCC[i]->getFunction()) - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) - for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { - CallSite CS = CallSite::get(I); - if (CS.getInstruction() && !isa(I) && - (!CS.getCalledFunction() || - !CS.getCalledFunction()->isDeclaration())) - CallSites.push_back(CS); - } + SmallVector, 16> CallSites; + + // When inlining a callee produces new call sites, we want to keep track of + // the fact that they were inlined from the callee. This allows us to avoid + // infinite inlining in some obscure cases. To represent this, we use an + // index into the InlineHistory vector. + SmallVector, 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(I)); + // If this isn't a call, or it is a call to an intrinsic, it can + // never be inlined. + if (!CS || isa(I)) + continue; + + // If this is a direct call to an external function, we can never inline + // it. If it is an indirect call, inlining may resolve it to be a + // direct call, so we keep it. + if (CS.getCalledFunction() && CS.getCalledFunction()->isDeclaration()) + continue; + + CallSites.push_back(std::make_pair(CS, -1)); + } + } - DOUT << ": " << CallSites.size() << " call sites.\n"; + DEBUG(dbgs() << ": " << CallSites.size() << " call sites.\n"); + // If there are no calls in this function, exit early. + if (CallSites.empty()) + return false; + // Now that we have all of the call sites, move the ones to functions in the // current SCC to the end of the list. unsigned FirstCallInSCC = CallSites.size(); for (unsigned i = 0; i < FirstCallInSCC; ++i) - if (Function *F = CallSites[i].getCalledFunction()) + if (Function *F = CallSites[i].first.getCalledFunction()) if (SCCFunctions.count(F)) std::swap(CallSites[i--], CallSites[--FirstCallInSCC]); + + InlinedArrayAllocasTy InlinedArrayAllocas; + InlineFunctionInfo InlineInfo(&CG, TD); + // Now that we have all of the call sites, loop over them and inline them if // it looks profitable to do so. bool Changed = false; @@ -170,51 +398,109 @@ bool Inliner::runOnSCC(const std::vector &SCC) { LocalChange = false; // Iterate over the outer loop because inlining functions can cause indirect // calls to become direct calls. - for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) - if (Function *Callee = CallSites[CSi].getCalledFunction()) { - // Calls to external functions are never inlinable. - if (Callee->isDeclaration()) { - if (SCC.size() == 1) { - std::swap(CallSites[CSi], CallSites.back()); - CallSites.pop_back(); - } else { - // Keep the 'in SCC / not in SCC' boundary correct. - CallSites.erase(CallSites.begin()+CSi); - } - --CSi; + for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) { + CallSite CS = CallSites[CSi].first; + + Function *Caller = CS.getCaller(); + Function *Callee = CS.getCalledFunction(); + + // If this call site is dead and it is to a readonly function, we should + // just delete the call instead of trying to inline it, regardless of + // size. This happens because IPSCCP propagates the result out of the + // call and then we're left with the dead call. + if (isInstructionTriviallyDead(CS.getInstruction())) { + DEBUG(dbgs() << " -> Deleting dead call: " + << *CS.getInstruction() << "\n"); + // Update the call graph by deleting the edge from Callee to Caller. + CG[Caller]->removeCallEdgeFor(CS); + CS.getInstruction()->eraseFromParent(); + ++NumCallsDeleted; + // Update the cached cost info with the missing call + growCachedCostInfo(Caller, NULL); + } else { + // We can only inline direct calls to non-declarations. + if (Callee == 0 || Callee->isDeclaration()) continue; + + // If this call site was obtained by inlining another function, verify + // that the include path for the function did not include the callee + // itself. If so, we'd be recursively inlining the same function, + // which would provide the same callsites, which would cause us to + // infinitely inline. + int InlineHistoryID = CallSites[CSi].second; + if (InlineHistoryID != -1 && + InlineHistoryIncludes(Callee, InlineHistoryID, InlineHistory)) continue; - } - + + // If the policy determines that we should inline this function, // try to do so. - CallSite CS = CallSites[CSi]; - if (shouldInline(CS)) { - Function *Caller = CS.getCaller(); - // Attempt to inline the function... - if (InlineCallIfPossible(CS, CG, SCCFunctions, TD)) { - // Remove any cached cost info for this caller, as inlining the - // callee has increased the size of the caller (which may be the - // same as the callee). - resetCachedCostInfo(Caller); - - // Remove this call site from the list. If possible, use - // swap/pop_back for efficiency, but do not use it if doing so would - // move a call site to a function in this SCC before the - // 'FirstCallInSCC' barrier. - if (SCC.size() == 1) { - std::swap(CallSites[CSi], CallSites.back()); - CallSites.pop_back(); - } else { - CallSites.erase(CallSites.begin()+CSi); - } - --CSi; - - ++NumInlined; - Changed = true; - LocalChange = true; + if (!shouldInline(CS)) + continue; + + // Attempt to inline the function. + if (!InlineCallIfPossible(CS, InlineInfo, InlinedArrayAllocas, + InlineHistoryID)) + continue; + ++NumInlined; + + // If inlining this function gave us any new call sites, throw them + // onto our worklist to process. They are useful inline candidates. + if (!InlineInfo.InlinedCalls.empty()) { + // Create a new inline history entry for this, so that we remember + // that these new callsites came about due to inlining Callee. + 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)); } } + + // Update the cached cost info with the inlined call. + growCachedCostInfo(Caller, Callee); } + + // If we inlined or deleted the last possible call site to the function, + // delete the function body now. + if (Callee && Callee->use_empty() && Callee->hasLocalLinkage() && + // TODO: Can remove if in SCC now. + !SCCFunctions.count(Callee) && + + // The function may be apparently dead, but if there are indirect + // callgraph references to the node, we cannot delete it yet, this + // could invalidate the CGSCC iterator. + CG[Callee]->getNumReferences() == 0) { + DEBUG(dbgs() << " -> Deleting dead function: " + << Callee->getName() << "\n"); + CallGraphNode *CalleeNode = CG[Callee]; + + // Remove any call graph edges from the callee to its callees. + CalleeNode->removeAllCalledFunctions(); + + resetCachedCostInfo(Callee); + + // Removing the node for callee from the call graph and delete it. + delete CG.removeFunctionFromModule(CalleeNode); + ++NumDeleted; + } + + // Remove this call site from the list. If possible, use + // swap/pop_back for efficiency, but do not use it if doing so would + // move a call site to a function in this SCC before the + // 'FirstCallInSCC' barrier. + 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; @@ -226,47 +512,55 @@ bool Inliner::doFinalization(CallGraph &CG) { return removeDeadFunctions(CG); } - /// removeDeadFunctions - Remove dead functions that are not included in - /// DNR (Do Not Remove) list. +/// removeDeadFunctions - Remove dead functions that are not included in +/// DNR (Do Not Remove) list. bool Inliner::removeDeadFunctions(CallGraph &CG, - SmallPtrSet *DNR) { - std::set FunctionsToRemove; + SmallPtrSet *DNR) { + SmallPtrSet FunctionsToRemove; // Scan for all of the functions, looking for ones that should now be removed // from the program. Insert the dead ones in the FunctionsToRemove set. for (CallGraph::iterator I = CG.begin(), E = CG.end(); I != E; ++I) { CallGraphNode *CGN = I->second; - if (Function *F = CGN ? CGN->getFunction() : 0) { - // If the only remaining users of the function are dead constants, remove - // them. - F->removeDeadConstantUsers(); - - if (DNR && DNR->count(F)) - continue; - - if ((F->hasLinkOnceLinkage() || F->hasLocalLinkage()) && - F->use_empty()) { - - // Remove any call graph edges from the function to its callees. - CGN->removeAllCalledFunctions(); + if (CGN->getFunction() == 0) + continue; + + Function *F = CGN->getFunction(); + + // If the only remaining users of the function are dead constants, remove + // them. + F->removeDeadConstantUsers(); + + if (DNR && DNR->count(F)) + continue; + if (!F->hasLinkOnceLinkage() && !F->hasLocalLinkage() && + !F->hasAvailableExternallyLinkage()) + continue; + if (!F->use_empty()) + continue; + + // Remove any call graph edges from the function to its callees. + CGN->removeAllCalledFunctions(); + + // Remove any edges from the external node to the function's call graph + // node. These edges might have been made irrelegant due to + // optimization of the program. + CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN); - // Remove any edges from the external node to the function's call graph - // node. These edges might have been made irrelegant due to - // optimization of the program. - CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN); - - // Removing the node for callee from the call graph and delete it. - FunctionsToRemove.insert(CGN); - } - } + // Removing the node for callee from the call graph and delete it. + FunctionsToRemove.insert(CGN); } // Now that we know which functions to delete, do so. We didn't want to do // this inline, because that would invalidate our CallGraph::iterator // objects. :( + // + // Note that it doesn't matter that we are iterating over a non-stable set + // here to do this, it doesn't matter which order the functions are deleted + // in. bool Changed = false; - for (std::set::iterator I = FunctionsToRemove.begin(), - E = FunctionsToRemove.end(); I != E; ++I) { + for (SmallPtrSet::iterator I = FunctionsToRemove.begin(), + E = FunctionsToRemove.end(); I != E; ++I) { resetCachedCostInfo((*I)->getFunction()); delete CG.removeFunctionFromModule(*I); ++NumDeleted;