X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FInliner.cpp;h=ca8eec48b4a7b75e7a9ab741f057fae0de537c73;hp=8fca96812b0870a57a1bcf0eb97d677d3410a78c;hb=4ee451de366474b9c228b4e5fa573795a715216d;hpb=cf5933a716e7eb6bd5ff49aa62f3e76379ebaf51 diff --git a/lib/Transforms/IPO/Inliner.cpp b/lib/Transforms/IPO/Inliner.cpp index 8fca96812b0..ca8eec48b4a 100644 --- a/lib/Transforms/IPO/Inliner.cpp +++ b/lib/Transforms/IPO/Inliner.cpp @@ -1,10 +1,10 @@ //===- Inliner.cpp - Code common to all inliners --------------------------===// -// +// // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// //===----------------------------------------------------------------------===// // // This file implements the mechanics required to implement inlining without @@ -13,60 +13,59 @@ // //===----------------------------------------------------------------------===// -#include "Inliner.h" -#include "llvm/Constants.h" // ConstantPointerRef should die +#define DEBUG_TYPE "inline" #include "llvm/Module.h" -#include "llvm/iOther.h" -#include "llvm/iTerminators.h" +#include "llvm/Instructions.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Support/CallSite.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Transforms/IPO/InlinerPass.h" #include "llvm/Transforms/Utils/Cloning.h" -#include "Support/CommandLine.h" -#include "Support/Debug.h" -#include "Support/Statistic.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/ADT/Statistic.h" #include using namespace llvm; +STATISTIC(NumInlined, "Number of functions inlined"); +STATISTIC(NumDeleted, "Number of functions deleted because all callers found"); + namespace { - Statistic<> NumInlined("inline", "Number of functions inlined"); - Statistic<> NumDeleted("inline", "Number of functions deleted because all callers found"); cl::opt // FIXME: 200 is VERY conservative InlineLimit("inline-threshold", cl::Hidden, cl::init(200), - cl::desc("Control the amount of inlining to perform (default = 200)")); + cl::desc("Control the amount of inlining to perform (default = 200)")); } -Inliner::Inliner() : InlineThreshold(InlineLimit) {} +Inliner::Inliner(const void *ID) + : CallGraphSCCPass((intptr_t)ID), InlineThreshold(InlineLimit) {} + +/// 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. static bool InlineCallIfPossible(CallSite CS, CallGraph &CG, - const std::set &SCCFunctions) { - Function *Caller = CS.getInstruction()->getParent()->getParent(); + const std::set &SCCFunctions, + const TargetData &TD) { Function *Callee = CS.getCalledFunction(); - if (!InlineFunction(CS)) return false; - - // Update the call graph by deleting the edge from Callee to Caller - CallGraphNode *CalleeNode = CG[Callee]; - CallGraphNode *CallerNode = CG[Caller]; - CallerNode->removeCallEdgeTo(CalleeNode); - - // Since we inlined all uninlined call sites in the callee into the caller, - // add edges from the caller to all of the callees of the callee. - for (CallGraphNode::iterator I = CalleeNode->begin(), - E = CalleeNode->end(); I != E; ++I) - CallerNode->addCalledFunction(*I); - - // If we inlined the last possible call site to the function, - // delete the function body now. + if (!InlineFunction(CS, &CG, &TD)) return false; + + // If we inlined the last possible call site to the function, delete the + // function body now. if (Callee->use_empty() && Callee->hasInternalLinkage() && !SCCFunctions.count(Callee)) { - DEBUG(std::cerr << " -> Deleting dead function: " - << Callee->getName() << "\n"); - + DOUT << " -> Deleting dead function: " << Callee->getName() << "\n"; + // Remove any call graph edges from the callee to its callees. - while (CalleeNode->begin() != CalleeNode->end()) - CalleeNode->removeCallEdgeTo(*(CalleeNode->end()-1)); - + CallGraphNode *CalleeNode = CG[Callee]; + while (!CalleeNode->empty()) + CalleeNode->removeCallEdgeTo((CalleeNode->end()-1)->second); + // Removing the node for callee from the call graph and delete it. delete CG.removeFunctionFromModule(CalleeNode); ++NumDeleted; @@ -78,11 +77,11 @@ bool Inliner::runOnSCC(const std::vector &SCC) { CallGraph &CG = getAnalysis(); std::set SCCFunctions; - DEBUG(std::cerr << "Inliner visiting SCC:"); + DOUT << "Inliner visiting SCC:"; for (unsigned i = 0, e = SCC.size(); i != e; ++i) { Function *F = SCC[i]->getFunction(); if (F) SCCFunctions.insert(F); - DEBUG(std::cerr << " " << (F ? F->getName() : "INDIRECTNODE")); + DOUT << " " << (F ? F->getName() : "INDIRECTNODE"); } // Scan through and identify all call sites ahead of time so that we only @@ -96,12 +95,12 @@ bool Inliner::runOnSCC(const std::vector &SCC) { for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { CallSite CS = CallSite::get(I); if (CS.getInstruction() && (!CS.getCalledFunction() || - !CS.getCalledFunction()->isExternal())) + !CS.getCalledFunction()->isDeclaration())) CallSites.push_back(CS); } - DEBUG(std::cerr << ": " << CallSites.size() << " call sites.\n"); - + DOUT << ": " << CallSites.size() << " call sites.\n"; + // 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(); @@ -109,7 +108,7 @@ bool Inliner::runOnSCC(const std::vector &SCC) { if (Function *F = CallSites[i].getCalledFunction()) if (SCCFunctions.count(F)) std::swap(CallSites[i--], CallSites[--FirstCallInSCC]); - + // 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; @@ -121,10 +120,15 @@ bool Inliner::runOnSCC(const std::vector &SCC) { for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) if (Function *Callee = CallSites[CSi].getCalledFunction()) { // Calls to external functions are never inlinable. - if (Callee->isExternal() || + if (Callee->isDeclaration() || CallSites[CSi].getInstruction()->getParent()->getParent() ==Callee){ - std::swap(CallSites[CSi], CallSites.back()); - CallSites.pop_back(); + 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; continue; } @@ -134,19 +138,25 @@ bool Inliner::runOnSCC(const std::vector &SCC) { CallSite CS = CallSites[CSi]; int InlineCost = getInlineCost(CS); if (InlineCost >= (int)InlineThreshold) { - DEBUG(std::cerr << " NOT Inlining: cost=" << InlineCost - << ", Call: " << *CS.getInstruction()); + DOUT << " NOT Inlining: cost=" << InlineCost + << ", Call: " << *CS.getInstruction(); } else { - DEBUG(std::cerr << " Inlining: cost=" << InlineCost - << ", Call: " << *CS.getInstruction()); - - Function *Caller = CS.getInstruction()->getParent()->getParent(); + DOUT << " Inlining: cost=" << InlineCost + << ", Call: " << *CS.getInstruction(); // Attempt to inline the function... - if (InlineCallIfPossible(CS, CG, SCCFunctions)) { - // Remove this call site from the list. - std::swap(CallSites[CSi], CallSites.back()); - CallSites.pop_back(); + if (InlineCallIfPossible(CS, CG, SCCFunctions, + getAnalysis())) { + // 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; @@ -169,36 +179,26 @@ bool Inliner::doFinalization(CallGraph &CG) { // 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; - Function *F = CGN ? CGN->getFunction() : 0; - - // If the only remaining use of the function is a dead constant - // pointer ref, remove it. - if (F && F->hasOneUse()) - if (ConstantPointerRef *CPR = dyn_cast(F->use_back())) - if (CPR->use_empty()) { - CPR->destroyConstant(); - if (F->hasInternalLinkage()) { - // There *MAY* be an edge from the external call node to this - // function. If so, remove it. - CallGraphNode *EN = CG.getExternalCallingNode(); - CallGraphNode::iterator I = std::find(EN->begin(), EN->end(), CGN); - if (I != EN->end()) EN->removeCallEdgeTo(CGN); - } - } + if (Function *F = CGN ? CGN->getFunction() : 0) { + // If the only remaining users of the function are dead constants, remove + // them. + F->removeDeadConstantUsers(); + + if ((F->hasLinkOnceLinkage() || F->hasInternalLinkage()) && + F->use_empty()) { + + // Remove any call graph edges from the function to its callees. + while (!CGN->empty()) + CGN->removeCallEdgeTo((CGN->end()-1)->second); - if (F && (F->hasLinkOnceLinkage() || F->hasInternalLinkage()) && - F->use_empty()) { - // Remove any call graph edges from the function to its callees. - while (CGN->begin() != CGN->end()) - CGN->removeCallEdgeTo(*(CGN->end()-1)); - - // If the function has external linkage (basically if it's a linkonce - // function) remove the edge from the external node to the callee node. - if (!F->hasInternalLinkage()) - CG.getExternalCallingNode()->removeCallEdgeTo(CGN); - - // Removing the node for callee from the call graph and delete it. - FunctionsToRemove.insert(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); + } } }