X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FIPA%2FCallGraph.cpp;h=d9e7242695cffb4cf205a001e8512e1b71ae0584;hb=45d10470c972d6b0bc0eff6590bc1fb016c14fd3;hp=d5cbe3d02b43d10d5b7e0fce3276a51987e32936;hpb=f52d01bbc58c116f7c83f3320a0f2dff9ac1b3d6;p=oota-llvm.git diff --git a/lib/Analysis/IPA/CallGraph.cpp b/lib/Analysis/IPA/CallGraph.cpp index d5cbe3d02b4..d9e7242695c 100644 --- a/lib/Analysis/IPA/CallGraph.cpp +++ b/lib/Analysis/IPA/CallGraph.cpp @@ -1,177 +1,219 @@ //===- CallGraph.cpp - Build a Module's call graph ------------------------===// // -// This interface is used to build and manipulate a call graph, which is a very -// useful tool for interprocedural optimization. +// The LLVM Compiler Infrastructure // -// Every function in a module is represented as a node in the call graph. The -// callgraph node keeps track of which functions the are called by the function -// corresponding to the node. +// 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. // -// A call graph will contain nodes where the function that they correspond to is -// null. This 'external' node is used to represent control flow that is not -// represented (or analyzable) in the module. As such, the external node will -// have edges to functions with the following properties: -// 1. All functions in the module without internal linkage, since they could -// be called by functions outside of the our analysis capability. -// 2. All functions whose address is used for something more than a direct -// call, for example being stored into a memory location. Since they may -// be called by an unknown caller later, they must be tracked as such. -// -// Similarly, functions have a call edge to the external node iff: -// 1. The function is external, reflecting the fact that they could call -// anything without internal linkage or that has its address taken. -// 2. The function contains an indirect function call. -// -// As an extension in the future, there may be multiple nodes with a null -// function. These will be used when we can prove (through pointer analysis) -// that an indirect call site can call only a specific set of functions. -// -// Because of these properties, the CallGraph captures a conservative superset -// of all of the caller-callee relationships, which is useful for -// transformations. +//===----------------------------------------------------------------------===// // -// The CallGraph class also attempts to figure out what the root of the -// CallGraph is, which is currently does by looking for a function named 'main'. -// If no function named 'main' is found, the external node is used as the entry -// node, reflecting the fact that any function without internal linkage could -// be called into (which is common for libraries). +// This file implements the CallGraph class and provides the BasicCallGraph +// default implementation. // //===----------------------------------------------------------------------===// #include "llvm/Analysis/CallGraph.h" #include "llvm/Module.h" -#include "llvm/iOther.h" -#include "llvm/iTerminators.h" -#include "Support/STLExtras.h" -#include +#include "llvm/Instructions.h" +#include "llvm/Support/CallSite.h" +#include +using namespace llvm; + +static bool isOnlyADirectCall(Function *F, CallSite CS) { + if (!CS.getInstruction()) return false; + for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) + if (*I == F) return false; + return true; +} -static RegisterAnalysis X("callgraph", "Call Graph Construction"); +namespace { -// getNodeFor - Return the node for the specified function or create one if it -// does not already exist. +//===----------------------------------------------------------------------===// +// BasicCallGraph class definition // -CallGraphNode *CallGraph::getNodeFor(Function *F) { - CallGraphNode *&CGN = FunctionMap[F]; - if (CGN) return CGN; +class BasicCallGraph : public CallGraph, public ModulePass { + // Root is root of the call graph, or the external node if a 'main' function + // couldn't be found. + // + CallGraphNode *Root; - assert((!F || F->getParent() == Mod) && "Function not in current module!"); - return CGN = new CallGraphNode(F); -} + // ExternalCallingNode - This node has edges to all external functions and + // those internal functions that have their address taken. + CallGraphNode *ExternalCallingNode; -// addToCallGraph - Add a function to the call graph, and link the node to all -// of the functions that it calls. -// -void CallGraph::addToCallGraph(Function *F) { - CallGraphNode *Node = getNodeFor(F); - - // If this function has external linkage, anything could call it... - if (!F->hasInternalLinkage()) { - ExternalNode->addCalledFunction(Node); - - // Found the entry point? - if (F->getName() == "main") { - if (Root) - Root = ExternalNode; // Found multiple external mains? Don't pick one. - else - Root = Node; // Found a main, keep track of it! - } + // CallsExternalNode - This node has edges to it from all functions making + // indirect calls or calling an external function. + CallGraphNode *CallsExternalNode; + +public: + BasicCallGraph() : Root(0), ExternalCallingNode(0), CallsExternalNode(0) {} + ~BasicCallGraph() { destroy(); } + + // runOnModule - Compute the call graph for the specified module. + virtual bool runOnModule(Module &M) { + destroy(); + 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; + } + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + } + + virtual void print(std::ostream &o, const Module *M) const { + o << "CallGraph Root is: "; + if (Function *F = getRoot()->getFunction()) + o << F->getName() << "\n"; + else + o << "<>\n"; + + CallGraph::print(o, M); + } + + virtual void releaseMemory() { + destroy(); } - // If this function is not defined in this translation unit, it could call - // anything. - if (F->isExternal()) - Node->addCalledFunction(ExternalNode); + /// dump - Print out this call graph. + /// + inline void dump() const { + print(std::cerr, Mod); + } - // Loop over all of the users of the function... looking for callers... + 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. // - for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I) { - User *U = *I; - if (CallInst *CI = dyn_cast(U)) - getNodeFor(CI->getParent()->getParent())->addCalledFunction(Node); - else if (InvokeInst *II = dyn_cast(U)) - getNodeFor(II->getParent()->getParent())->addCalledFunction(Node); - else // Can't classify the user! - ExternalNode->addCalledFunction(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->hasInternalLinkage()) { + ExternalCallingNode->addCalledFunction(CallSite(), Node); - // Look for an indirect function call... - for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) - for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; ++II){ - Instruction &I = *II; - - if (CallInst *CI = dyn_cast(&I)) { - if (CI->getCalledFunction() == 0) - Node->addCalledFunction(ExternalNode); - } else if (InvokeInst *II = dyn_cast(&I)) { - if (II->getCalledFunction() == 0) - Node->addCalledFunction(ExternalNode); + // 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! } } -} -bool CallGraph::run(Module &M) { - destroy(); + // If this function is not defined in this translation unit, it could call + // anything. + if (F->isExternal() && !F->getIntrinsicID()) + Node->addCalledFunction(CallSite(), CallsExternalNode); - Mod = &M; - ExternalNode = getNodeFor(0); - Root = 0; + // Loop over all of the users of the function... looking for callers... + // + bool isUsedExternally = false; + for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I){ + if (Instruction *Inst = dyn_cast(*I)) { + CallSite CS = CallSite::get(Inst); + if (isOnlyADirectCall(F, CS)) + getOrInsertFunction(Inst->getParent()->getParent()) + ->addCalledFunction(CS, Node); + else + isUsedExternally = true; + } else if (GlobalValue *GV = dyn_cast(*I)) { + for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); + I != E; ++I) + if (Instruction *Inst = dyn_cast(*I)) { + CallSite CS = CallSite::get(Inst); + if (isOnlyADirectCall(F, CS)) + getOrInsertFunction(Inst->getParent()->getParent()) + ->addCalledFunction(CS, Node); + else + isUsedExternally = true; + } else { + isUsedExternally = true; + } + } else { // Can't classify the user! + isUsedExternally = true; + } + } + if (isUsedExternally) + ExternalCallingNode->addCalledFunction(CallSite(), Node); - // Add every function to the call graph... - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) - addToCallGraph(I); + // Look for an indirect function call. + 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 = CallSite::get(II); + if (CS.getInstruction() && !CS.getCalledFunction()) + Node->addCalledFunction(CS, CallsExternalNode); + } + } - // If we didn't find a main function, use the external call graph node - if (Root == 0) Root = ExternalNode; - - return false; -} + // + // destroy - Release memory for the call graph + virtual void destroy() { + if (!CallsExternalNode) { + delete CallsExternalNode; + CallsExternalNode = 0; + } + } +}; -void CallGraph::destroy() { - for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); - I != E; ++I) - delete I->second; - FunctionMap.clear(); -} +RegisterAnalysisGroup X("Call Graph"); +RegisterPass Y("basiccg", "Basic CallGraph Construction"); +RegisterAnalysisGroup Z(Y); -static void WriteToOutput(const CallGraphNode *CGN, std::ostream &o) { - if (CGN->getFunction()) - o << "Call graph node for function: '" - << CGN->getFunction()->getName() <<"'\n"; - else - o << "Call graph node <>:\n"; +} //End anonymous namespace - for (unsigned i = 0; i < CGN->size(); ++i) - if ((*CGN)[i]->getFunction()) - o << " Calls function '" << (*CGN)[i]->getFunction()->getName() << "'\n"; - else - o << " Calls external node\n"; - o << "\n"; +void CallGraph::initialize(Module &M) { + destroy(); + Mod = &M; } -void CallGraph::print(std::ostream &o, const Module *M) const { - o << "CallGraph Root is: "; - if (getRoot()->getFunction()) - o << getRoot()->getFunction()->getName() << "\n"; - else - o << "<>\n"; - +void CallGraph::destroy() { + if (!FunctionMap.empty()) { + for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); + I != E; ++I) + delete I->second; + FunctionMap.clear(); + } +} + +void CallGraph::print(std::ostream &OS, const Module *M) const { for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) - WriteToOutput(I->second, o); + I->second->print(OS); } +void CallGraph::dump() const { + print(std::cerr, 0); +} //===----------------------------------------------------------------------===// // Implementations of public modification methods // -// Functions to keep a call graph up to date with a function that has been -// modified -// -void CallGraph::addFunctionToModule(Function *Meth) { - assert(0 && "not implemented"); - abort(); -} - // removeFunctionFromModule - Unlink the function from this module, returning // it. Because this removes the function from the module, the call graph node // is destroyed. This is only valid if the function does not call any other @@ -189,3 +231,68 @@ Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { return F; } +// changeFunction - This method changes the function associated with this +// CallGraphNode, for use by transformations that need to change the prototype +// of a Function (thus they must create a new Function and move the old code +// over). +void CallGraph::changeFunction(Function *OldF, Function *NewF) { + iterator I = FunctionMap.find(OldF); + CallGraphNode *&New = FunctionMap[NewF]; + assert(I != FunctionMap.end() && I->second && !New && + "OldF didn't exist in CG or NewF already does!"); + New = I->second; + New->F = NewF; + 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. +CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { + CallGraphNode *&CGN = FunctionMap[F]; + if (CGN) return CGN; + + assert((!F || F->getParent() == Mod) && "Function not in current module!"); + return CGN = new CallGraphNode(const_cast(F)); +} + +void CallGraphNode::print(std::ostream &OS) const { + if (Function *F = getFunction()) + OS << "Call graph node for function: '" << F->getName() <<"'\n"; + else + OS << "Call graph node <>:\n"; + + for (const_iterator I = begin(), E = end(); I != E; ++I) + if (I->second->getFunction()) + OS << " Calls function '" << I->second->getFunction()->getName() <<"'\n"; + else + OS << " Calls external node\n"; + OS << "\n"; +} + +void CallGraphNode::dump() const { print(std::cerr); } + +void CallGraphNode::removeCallEdgeTo(CallGraphNode *Callee) { + for (unsigned i = CalledFunctions.size(); ; --i) { + assert(i && "Cannot find callee to remove!"); + if (CalledFunctions[i-1].second == Callee) { + CalledFunctions.erase(CalledFunctions.begin()+i-1); + return; + } + } +} + +// 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. +void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { + for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) + if (CalledFunctions[i].second == Callee) { + CalledFunctions[i] = CalledFunctions.back(); + CalledFunctions.pop_back(); + --i; --e; + } +} + +// Enuse that users of CallGraph.h also link with this file +DEFINING_FILE_FOR(CallGraph)