X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FIPA%2FCallGraph.cpp;h=f042964c21d918eebc66c2d41dfd2ca2b0dd9593;hb=c143c7573bfd0d55cf283cc2676dbd852f939c87;hp=d3d3af3fdf983d57ee775545f9d1b0af9b37fdbc;hpb=e9ef41a47d2ee637b6aed5d018c4d90019d987ac;p=oota-llvm.git diff --git a/lib/Analysis/IPA/CallGraph.cpp b/lib/Analysis/IPA/CallGraph.cpp index d3d3af3fdf9..f042964c21d 100644 --- a/lib/Analysis/IPA/CallGraph.cpp +++ b/lib/Analysis/IPA/CallGraph.cpp @@ -6,187 +6,102 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -// -// This file implements the CallGraph class and provides the BasicCallGraph -// default implementation. -// -//===----------------------------------------------------------------------===// #include "llvm/Analysis/CallGraph.h" -#include "llvm/Module.h" -#include "llvm/Instructions.h" -#include "llvm/IntrinsicInst.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" #include "llvm/Support/CallSite.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; -namespace { +CallGraph::CallGraph() + : ModulePass(ID), Root(0), ExternalCallingNode(0), CallsExternalNode(0) { + initializeCallGraphPass(*PassRegistry::getPassRegistry()); +} -//===----------------------------------------------------------------------===// -// BasicCallGraph class definition -// -class BasicCallGraph : public ModulePass, public CallGraph { - // Root is root of the call graph, or the external node if a 'main' function - // couldn't be found. - // - CallGraphNode *Root; - - // ExternalCallingNode - This node has edges to all external functions and - // those internal functions that have their address taken. - CallGraphNode *ExternalCallingNode; - - // CallsExternalNode - This node has edges to it from all functions making - // indirect calls or calling an external function. - CallGraphNode *CallsExternalNode; - -public: - static char ID; // Class identification, replacement for typeinfo - BasicCallGraph() : ModulePass(ID), Root(0), - ExternalCallingNode(0), CallsExternalNode(0) {} - - // runOnModule - Compute the call graph for the specified module. - virtual bool runOnModule(Module &M) { - CallGraph::initialize(M); - - ExternalCallingNode = getOrInsertFunction(0); - CallsExternalNode = new CallGraphNode(0); - Root = 0; - - // Add every function to the call graph. - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) - addToCallGraph(I); - - // If we didn't find a main function, use the external call graph node - if (Root == 0) Root = ExternalCallingNode; - - return false; - } +void CallGraph::addToCallGraph(Function *F) { + CallGraphNode *Node = getOrInsertFunction(F); - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - } + // If this function has external linkage, anything could call it. + if (!F->hasLocalLinkage()) { + ExternalCallingNode->addCalledFunction(CallSite(), Node); - virtual void print(raw_ostream &OS, const Module *) const { - OS << "CallGraph Root is: "; - if (Function *F = getRoot()->getFunction()) - OS << F->getName() << "\n"; - else { - OS << "<>\n"; + // Found the entry point? + if (F->getName() == "main") { + if (Root) // Found multiple external mains? Don't pick one. + Root = ExternalCallingNode; + else + Root = Node; // Found a main, keep track of it! } - - CallGraph::print(OS, 0); } - virtual void releaseMemory() { - destroy(); - } - - /// getAdjustedAnalysisPointer - This method is used when a pass implements - /// an analysis interface through multiple inheritance. If needed, it should - /// override this to adjust the this pointer as needed for the specified pass - /// info. - virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { - if (PI == &CallGraph::ID) - return (CallGraph*)this; - return this; - } - - CallGraphNode* getExternalCallingNode() const { return ExternalCallingNode; } - CallGraphNode* getCallsExternalNode() const { return CallsExternalNode; } - - // getRoot - Return the root of the call graph, which is either main, or if - // main cannot be found, the external node. - // - CallGraphNode *getRoot() { return Root; } - const CallGraphNode *getRoot() const { return Root; } - -private: - //===--------------------------------------------------------------------- - // Implementation of CallGraph construction - // - - // addToCallGraph - Add a function to the call graph, and link the node to all - // of the functions that it calls. - // - void addToCallGraph(Function *F) { - CallGraphNode *Node = getOrInsertFunction(F); - - // If this function has external linkage, anything could call it. - if (!F->hasLocalLinkage()) { - ExternalCallingNode->addCalledFunction(CallSite(), Node); - - // Found the entry point? - if (F->getName() == "main") { - if (Root) // Found multiple external mains? Don't pick one. - Root = ExternalCallingNode; - else - Root = Node; // Found a main, keep track of it! + // If this function has its address taken, anything could call it. + if (F->hasAddressTaken()) + ExternalCallingNode->addCalledFunction(CallSite(), Node); + + // If this function is not defined in this translation unit, it could call + // anything. + if (F->isDeclaration() && !F->isIntrinsic()) + Node->addCalledFunction(CallSite(), CallsExternalNode); + + // Look for calls by this function. + for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) + for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; + ++II) { + CallSite CS(cast(II)); + if (CS) { + const Function *Callee = CS.getCalledFunction(); + if (!Callee) + // Indirect calls of intrinsics are not allowed so no need to check. + Node->addCalledFunction(CS, CallsExternalNode); + else if (!Callee->isIntrinsic()) + Node->addCalledFunction(CS, getOrInsertFunction(Callee)); } } +} - // Loop over all of the users of the function, looking for non-call uses. - for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I){ - User *U = *I; - if ((!isa(U) && !isa(U)) - || !CallSite(cast(U)).isCallee(I)) { - // Not a call, or being used as a parameter rather than as the callee. - ExternalCallingNode->addCalledFunction(CallSite(), Node); - break; - } - } +void CallGraph::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); +} - // If this function is not defined in this translation unit, it could call - // anything. - if (F->isDeclaration() && !F->isIntrinsic()) - Node->addCalledFunction(CallSite(), CallsExternalNode); - - // Look for calls by this function. - for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) - for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); - II != IE; ++II) { - CallSite CS(cast(II)); - if (CS && !isa(II)) { - const Function *Callee = CS.getCalledFunction(); - if (Callee) - Node->addCalledFunction(CS, getOrInsertFunction(Callee)); - else - Node->addCalledFunction(CS, CallsExternalNode); - } - } - } +bool CallGraph::runOnModule(Module &M) { + Mod = &M; - // - // destroy - Release memory for the call graph - virtual void destroy() { - /// CallsExternalNode is not in the function map, delete it explicitly. - if (CallsExternalNode) { - CallsExternalNode->allReferencesDropped(); - delete CallsExternalNode; - CallsExternalNode = 0; - } - CallGraph::destroy(); - } -}; + ExternalCallingNode = getOrInsertFunction(0); + assert(!CallsExternalNode); + CallsExternalNode = new CallGraphNode(0); + Root = 0; + + // Add every function to the call graph. + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + addToCallGraph(I); -} //End anonymous namespace + // If we didn't find a main function, use the external call graph node + if (Root == 0) + Root = ExternalCallingNode; -INITIALIZE_ANALYSIS_GROUP(CallGraph, "Call Graph"); -INITIALIZE_AG_PASS(BasicCallGraph, CallGraph, "basiccg", - "Basic CallGraph Construction", false, true, true); + return false; +} + +INITIALIZE_PASS(CallGraph, "basiccg", "CallGraph Construction", false, true) char CallGraph::ID = 0; -char BasicCallGraph::ID = 0; -void CallGraph::initialize(Module &M) { - Mod = &M; -} +void CallGraph::releaseMemory() { + /// CallsExternalNode is not in the function map, delete it explicitly. + if (CallsExternalNode) { + CallsExternalNode->allReferencesDropped(); + delete CallsExternalNode; + CallsExternalNode = 0; + } -void CallGraph::destroy() { - if (FunctionMap.empty()) return; - - // Reset all node's use counts to zero before deleting them to prevent an - // assertion from firing. + if (FunctionMap.empty()) + return; + +// Reset all node's use counts to zero before deleting them to prevent an +// assertion from firing. #ifndef NDEBUG for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); I != E; ++I) @@ -199,13 +114,22 @@ void CallGraph::destroy() { FunctionMap.clear(); } -void CallGraph::print(raw_ostream &OS, Module*) const { +void CallGraph::print(raw_ostream &OS, const Module*) const { + OS << "CallGraph Root is: "; + if (Function *F = Root->getFunction()) + OS << F->getName() << "\n"; + else { + OS << "<>\n"; + } + for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) I->second->print(OS); } +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void CallGraph::dump() const { print(dbgs(), 0); } +#endif //===----------------------------------------------------------------------===// // Implementations of public modification methods @@ -228,6 +152,21 @@ Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { return F; } +/// spliceFunction - Replace the function represented by this node by another. +/// This does not rescan the body of the function, so it is suitable when +/// splicing the body of the old function to the new while also updating all +/// callers from old to new. +/// +void CallGraph::spliceFunction(const Function *From, const Function *To) { + assert(FunctionMap.count(From) && "No CallGraphNode for function!"); + assert(!FunctionMap.count(To) && + "Pointing CallGraphNode at a function that already exists"); + FunctionMapTy::iterator I = FunctionMap.find(From); + I->second->F = const_cast(To); + FunctionMap[To] = I->second; + FunctionMap.erase(I); +} + // getOrInsertFunction - This method is identical to calling operator[], but // it will insert a new CallGraphNode for the specified function if one does // not already exist. @@ -257,7 +196,9 @@ void CallGraphNode::print(raw_ostream &OS) const { OS << '\n'; } +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void CallGraphNode::dump() const { print(dbgs()); } +#endif /// removeCallEdgeFor - This method removes the edge in the node for the /// specified call site. Note that this method takes linear time, so it @@ -274,7 +215,6 @@ void CallGraphNode::removeCallEdgeFor(CallSite CS) { } } - // removeAnyCallEdgeTo - This method removes any call edges from this node to // the specified callee function. This takes more time to execute than // removeCallEdgeTo, so it should not be used unless necessary.