CallGraph.cpp revision 202878
1193323Sed//===- CallGraph.cpp - Build a Module's call graph ------------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the CallGraph class and provides the BasicCallGraph 11193323Sed// default implementation. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#include "llvm/Analysis/CallGraph.h" 16193323Sed#include "llvm/Module.h" 17193323Sed#include "llvm/Instructions.h" 18193323Sed#include "llvm/IntrinsicInst.h" 19193323Sed#include "llvm/Support/CallSite.h" 20201360Srdivacky#include "llvm/Support/Debug.h" 21198090Srdivacky#include "llvm/Support/raw_ostream.h" 22193323Sedusing namespace llvm; 23193323Sed 24193323Sednamespace { 25193323Sed 26193323Sed//===----------------------------------------------------------------------===// 27193323Sed// BasicCallGraph class definition 28193323Sed// 29202878Srdivackyclass BasicCallGraph : public ModulePass, public CallGraph { 30193323Sed // Root is root of the call graph, or the external node if a 'main' function 31193323Sed // couldn't be found. 32193323Sed // 33193323Sed CallGraphNode *Root; 34193323Sed 35193323Sed // ExternalCallingNode - This node has edges to all external functions and 36193323Sed // those internal functions that have their address taken. 37193323Sed CallGraphNode *ExternalCallingNode; 38193323Sed 39193323Sed // CallsExternalNode - This node has edges to it from all functions making 40193323Sed // indirect calls or calling an external function. 41193323Sed CallGraphNode *CallsExternalNode; 42193323Sed 43193323Sedpublic: 44193323Sed static char ID; // Class identification, replacement for typeinfo 45193323Sed BasicCallGraph() : ModulePass(&ID), Root(0), 46193323Sed ExternalCallingNode(0), CallsExternalNode(0) {} 47193323Sed 48193323Sed // runOnModule - Compute the call graph for the specified module. 49193323Sed virtual bool runOnModule(Module &M) { 50193323Sed CallGraph::initialize(M); 51193323Sed 52193323Sed ExternalCallingNode = getOrInsertFunction(0); 53193323Sed CallsExternalNode = new CallGraphNode(0); 54193323Sed Root = 0; 55193323Sed 56198090Srdivacky // Add every function to the call graph. 57193323Sed for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 58193323Sed addToCallGraph(I); 59193323Sed 60193323Sed // If we didn't find a main function, use the external call graph node 61193323Sed if (Root == 0) Root = ExternalCallingNode; 62193323Sed 63193323Sed return false; 64193323Sed } 65193323Sed 66193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 67193323Sed AU.setPreservesAll(); 68193323Sed } 69193323Sed 70198090Srdivacky virtual void print(raw_ostream &OS, const Module *) const { 71198090Srdivacky OS << "CallGraph Root is: "; 72193323Sed if (Function *F = getRoot()->getFunction()) 73198090Srdivacky OS << F->getName() << "\n"; 74198090Srdivacky else { 75198090Srdivacky OS << "<<null function: 0x" << getRoot() << ">>\n"; 76198090Srdivacky } 77193323Sed 78198090Srdivacky CallGraph::print(OS, 0); 79193323Sed } 80193323Sed 81193323Sed virtual void releaseMemory() { 82193323Sed destroy(); 83193323Sed } 84193323Sed 85202878Srdivacky /// getAdjustedAnalysisPointer - This method is used when a pass implements 86202878Srdivacky /// an analysis interface through multiple inheritance. If needed, it should 87202878Srdivacky /// override this to adjust the this pointer as needed for the specified pass 88202878Srdivacky /// info. 89202878Srdivacky virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) { 90202878Srdivacky if (PI->isPassID(&CallGraph::ID)) 91202878Srdivacky return (CallGraph*)this; 92202878Srdivacky return this; 93202878Srdivacky } 94202878Srdivacky 95193323Sed CallGraphNode* getExternalCallingNode() const { return ExternalCallingNode; } 96193323Sed CallGraphNode* getCallsExternalNode() const { return CallsExternalNode; } 97193323Sed 98193323Sed // getRoot - Return the root of the call graph, which is either main, or if 99193323Sed // main cannot be found, the external node. 100193323Sed // 101193323Sed CallGraphNode *getRoot() { return Root; } 102193323Sed const CallGraphNode *getRoot() const { return Root; } 103193323Sed 104193323Sedprivate: 105193323Sed //===--------------------------------------------------------------------- 106193323Sed // Implementation of CallGraph construction 107193323Sed // 108193323Sed 109193323Sed // addToCallGraph - Add a function to the call graph, and link the node to all 110193323Sed // of the functions that it calls. 111193323Sed // 112193323Sed void addToCallGraph(Function *F) { 113193323Sed CallGraphNode *Node = getOrInsertFunction(F); 114193323Sed 115193323Sed // If this function has external linkage, anything could call it. 116193323Sed if (!F->hasLocalLinkage()) { 117193323Sed ExternalCallingNode->addCalledFunction(CallSite(), Node); 118193323Sed 119193323Sed // Found the entry point? 120193323Sed if (F->getName() == "main") { 121193323Sed if (Root) // Found multiple external mains? Don't pick one. 122193323Sed Root = ExternalCallingNode; 123193323Sed else 124193323Sed Root = Node; // Found a main, keep track of it! 125193323Sed } 126193323Sed } 127193323Sed 128193323Sed // Loop over all of the users of the function, looking for non-call uses. 129193323Sed for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I) 130193323Sed if ((!isa<CallInst>(I) && !isa<InvokeInst>(I)) 131193323Sed || !CallSite(cast<Instruction>(I)).isCallee(I)) { 132193323Sed // Not a call, or being used as a parameter rather than as the callee. 133193323Sed ExternalCallingNode->addCalledFunction(CallSite(), Node); 134193323Sed break; 135193323Sed } 136193323Sed 137193323Sed // If this function is not defined in this translation unit, it could call 138193323Sed // anything. 139193323Sed if (F->isDeclaration() && !F->isIntrinsic()) 140193323Sed Node->addCalledFunction(CallSite(), CallsExternalNode); 141193323Sed 142193323Sed // Look for calls by this function. 143193323Sed for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) 144193323Sed for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); 145193323Sed II != IE; ++II) { 146193323Sed CallSite CS = CallSite::get(II); 147193323Sed if (CS.getInstruction() && !isa<DbgInfoIntrinsic>(II)) { 148193323Sed const Function *Callee = CS.getCalledFunction(); 149193323Sed if (Callee) 150193323Sed Node->addCalledFunction(CS, getOrInsertFunction(Callee)); 151193323Sed else 152193323Sed Node->addCalledFunction(CS, CallsExternalNode); 153193323Sed } 154193323Sed } 155193323Sed } 156193323Sed 157193323Sed // 158193323Sed // destroy - Release memory for the call graph 159193323Sed virtual void destroy() { 160193323Sed /// CallsExternalNode is not in the function map, delete it explicitly. 161193323Sed delete CallsExternalNode; 162193323Sed CallsExternalNode = 0; 163193323Sed CallGraph::destroy(); 164193323Sed } 165193323Sed}; 166193323Sed 167193323Sed} //End anonymous namespace 168193323Sed 169193323Sedstatic RegisterAnalysisGroup<CallGraph> X("Call Graph"); 170193323Sedstatic RegisterPass<BasicCallGraph> 171193323SedY("basiccg", "Basic CallGraph Construction", false, true); 172193323Sedstatic RegisterAnalysisGroup<CallGraph, true> Z(Y); 173193323Sed 174193323Sedchar CallGraph::ID = 0; 175193323Sedchar BasicCallGraph::ID = 0; 176193323Sed 177193323Sedvoid CallGraph::initialize(Module &M) { 178193323Sed Mod = &M; 179193323Sed} 180193323Sed 181193323Sedvoid CallGraph::destroy() { 182198090Srdivacky if (FunctionMap.empty()) return; 183198090Srdivacky 184198090Srdivacky for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 185198090Srdivacky I != E; ++I) 186198090Srdivacky delete I->second; 187198090Srdivacky FunctionMap.clear(); 188193323Sed} 189193323Sed 190198090Srdivackyvoid CallGraph::print(raw_ostream &OS, Module*) const { 191193323Sed for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) 192193323Sed I->second->print(OS); 193193323Sed} 194193323Sedvoid CallGraph::dump() const { 195201360Srdivacky print(dbgs(), 0); 196193323Sed} 197193323Sed 198193323Sed//===----------------------------------------------------------------------===// 199193323Sed// Implementations of public modification methods 200193323Sed// 201193323Sed 202193323Sed// removeFunctionFromModule - Unlink the function from this module, returning 203193323Sed// it. Because this removes the function from the module, the call graph node 204193323Sed// is destroyed. This is only valid if the function does not call any other 205193323Sed// functions (ie, there are no edges in it's CGN). The easiest way to do this 206193323Sed// is to dropAllReferences before calling this. 207193323Sed// 208193323SedFunction *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 209198090Srdivacky assert(CGN->empty() && "Cannot remove function from call " 210193323Sed "graph if it references other functions!"); 211193323Sed Function *F = CGN->getFunction(); // Get the function for the call graph node 212193323Sed delete CGN; // Delete the call graph node for this func 213193323Sed FunctionMap.erase(F); // Remove the call graph node from the map 214193323Sed 215193323Sed Mod->getFunctionList().remove(F); 216193323Sed return F; 217193323Sed} 218193323Sed 219193323Sed// getOrInsertFunction - This method is identical to calling operator[], but 220193323Sed// it will insert a new CallGraphNode for the specified function if one does 221193323Sed// not already exist. 222193323SedCallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { 223193323Sed CallGraphNode *&CGN = FunctionMap[F]; 224193323Sed if (CGN) return CGN; 225193323Sed 226193323Sed assert((!F || F->getParent() == Mod) && "Function not in current module!"); 227193323Sed return CGN = new CallGraphNode(const_cast<Function*>(F)); 228193323Sed} 229193323Sed 230198090Srdivackyvoid CallGraphNode::print(raw_ostream &OS) const { 231193323Sed if (Function *F = getFunction()) 232198090Srdivacky OS << "Call graph node for function: '" << F->getName() << "'"; 233193323Sed else 234198090Srdivacky OS << "Call graph node <<null function>>"; 235198090Srdivacky 236198090Srdivacky OS << "<<0x" << this << ">> #uses=" << getNumReferences() << '\n'; 237193323Sed 238193323Sed for (const_iterator I = begin(), E = end(); I != E; ++I) 239193323Sed if (Function *FI = I->second->getFunction()) 240193323Sed OS << " Calls function '" << FI->getName() <<"'\n"; 241193323Sed else 242193323Sed OS << " Calls external node\n"; 243193323Sed OS << "\n"; 244193323Sed} 245193323Sed 246201360Srdivackyvoid CallGraphNode::dump() const { print(dbgs()); } 247193323Sed 248193323Sed/// removeCallEdgeFor - This method removes the edge in the node for the 249193323Sed/// specified call site. Note that this method takes linear time, so it 250193323Sed/// should be used sparingly. 251193323Sedvoid CallGraphNode::removeCallEdgeFor(CallSite CS) { 252193323Sed for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 253193323Sed assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 254198090Srdivacky if (I->first == CS.getInstruction()) { 255198090Srdivacky I->second->DropRef(); 256198090Srdivacky *I = CalledFunctions.back(); 257198090Srdivacky CalledFunctions.pop_back(); 258193323Sed return; 259193323Sed } 260193323Sed } 261193323Sed} 262193323Sed 263193323Sed 264193323Sed// removeAnyCallEdgeTo - This method removes any call edges from this node to 265193323Sed// the specified callee function. This takes more time to execute than 266193323Sed// removeCallEdgeTo, so it should not be used unless necessary. 267193323Sedvoid CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 268193323Sed for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 269193323Sed if (CalledFunctions[i].second == Callee) { 270198090Srdivacky Callee->DropRef(); 271193323Sed CalledFunctions[i] = CalledFunctions.back(); 272193323Sed CalledFunctions.pop_back(); 273193323Sed --i; --e; 274193323Sed } 275193323Sed} 276193323Sed 277193323Sed/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite 278193323Sed/// from this node to the specified callee function. 279193323Sedvoid CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) { 280193323Sed for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 281193323Sed assert(I != CalledFunctions.end() && "Cannot find callee to remove!"); 282193323Sed CallRecord &CR = *I; 283198090Srdivacky if (CR.second == Callee && CR.first == 0) { 284198090Srdivacky Callee->DropRef(); 285198090Srdivacky *I = CalledFunctions.back(); 286198090Srdivacky CalledFunctions.pop_back(); 287193323Sed return; 288193323Sed } 289193323Sed } 290193323Sed} 291193323Sed 292198090Srdivacky/// replaceCallEdge - This method replaces the edge in the node for the 293198090Srdivacky/// specified call site with a new one. Note that this method takes linear 294198090Srdivacky/// time, so it should be used sparingly. 295198090Srdivackyvoid CallGraphNode::replaceCallEdge(CallSite CS, 296198090Srdivacky CallSite NewCS, CallGraphNode *NewNode){ 297193323Sed for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 298198090Srdivacky assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 299198090Srdivacky if (I->first == CS.getInstruction()) { 300198090Srdivacky I->second->DropRef(); 301198090Srdivacky I->first = NewCS.getInstruction(); 302198090Srdivacky I->second = NewNode; 303198090Srdivacky NewNode->AddRef(); 304193323Sed return; 305193323Sed } 306193323Sed } 307193323Sed} 308193323Sed 309193323Sed// Enuse that users of CallGraph.h also link with this file 310193323SedDEFINING_FILE_FOR(CallGraph) 311