CallGraph.cpp revision 218893
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 45212904Sdim BasicCallGraph() : ModulePass(ID), Root(0), 46218893Sdim ExternalCallingNode(0), CallsExternalNode(0) { 47218893Sdim initializeBasicCallGraphPass(*PassRegistry::getPassRegistry()); 48218893Sdim } 49193323Sed 50193323Sed // runOnModule - Compute the call graph for the specified module. 51193323Sed virtual bool runOnModule(Module &M) { 52193323Sed CallGraph::initialize(M); 53193323Sed 54193323Sed ExternalCallingNode = getOrInsertFunction(0); 55193323Sed CallsExternalNode = new CallGraphNode(0); 56193323Sed Root = 0; 57193323Sed 58198090Srdivacky // Add every function to the call graph. 59193323Sed for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 60193323Sed addToCallGraph(I); 61193323Sed 62193323Sed // If we didn't find a main function, use the external call graph node 63193323Sed if (Root == 0) Root = ExternalCallingNode; 64193323Sed 65193323Sed return false; 66193323Sed } 67193323Sed 68193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 69193323Sed AU.setPreservesAll(); 70193323Sed } 71193323Sed 72198090Srdivacky virtual void print(raw_ostream &OS, const Module *) const { 73198090Srdivacky OS << "CallGraph Root is: "; 74193323Sed if (Function *F = getRoot()->getFunction()) 75198090Srdivacky OS << F->getName() << "\n"; 76198090Srdivacky else { 77198090Srdivacky OS << "<<null function: 0x" << getRoot() << ">>\n"; 78198090Srdivacky } 79193323Sed 80198090Srdivacky CallGraph::print(OS, 0); 81193323Sed } 82193323Sed 83193323Sed virtual void releaseMemory() { 84193323Sed destroy(); 85193323Sed } 86193323Sed 87202878Srdivacky /// getAdjustedAnalysisPointer - This method is used when a pass implements 88202878Srdivacky /// an analysis interface through multiple inheritance. If needed, it should 89202878Srdivacky /// override this to adjust the this pointer as needed for the specified pass 90202878Srdivacky /// info. 91212904Sdim virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { 92212904Sdim if (PI == &CallGraph::ID) 93202878Srdivacky return (CallGraph*)this; 94202878Srdivacky return this; 95202878Srdivacky } 96202878Srdivacky 97193323Sed CallGraphNode* getExternalCallingNode() const { return ExternalCallingNode; } 98193323Sed CallGraphNode* getCallsExternalNode() const { return CallsExternalNode; } 99193323Sed 100193323Sed // getRoot - Return the root of the call graph, which is either main, or if 101193323Sed // main cannot be found, the external node. 102193323Sed // 103193323Sed CallGraphNode *getRoot() { return Root; } 104193323Sed const CallGraphNode *getRoot() const { return Root; } 105193323Sed 106193323Sedprivate: 107193323Sed //===--------------------------------------------------------------------- 108193323Sed // Implementation of CallGraph construction 109193323Sed // 110193323Sed 111193323Sed // addToCallGraph - Add a function to the call graph, and link the node to all 112193323Sed // of the functions that it calls. 113193323Sed // 114193323Sed void addToCallGraph(Function *F) { 115193323Sed CallGraphNode *Node = getOrInsertFunction(F); 116193323Sed 117193323Sed // If this function has external linkage, anything could call it. 118193323Sed if (!F->hasLocalLinkage()) { 119193323Sed ExternalCallingNode->addCalledFunction(CallSite(), Node); 120193323Sed 121193323Sed // Found the entry point? 122193323Sed if (F->getName() == "main") { 123193323Sed if (Root) // Found multiple external mains? Don't pick one. 124193323Sed Root = ExternalCallingNode; 125193323Sed else 126193323Sed Root = Node; // Found a main, keep track of it! 127193323Sed } 128193323Sed } 129193323Sed 130193323Sed // Loop over all of the users of the function, looking for non-call uses. 131210299Sed for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I){ 132210299Sed User *U = *I; 133210299Sed if ((!isa<CallInst>(U) && !isa<InvokeInst>(U)) 134210299Sed || !CallSite(cast<Instruction>(U)).isCallee(I)) { 135193323Sed // Not a call, or being used as a parameter rather than as the callee. 136193323Sed ExternalCallingNode->addCalledFunction(CallSite(), Node); 137193323Sed break; 138193323Sed } 139210299Sed } 140193323Sed 141193323Sed // If this function is not defined in this translation unit, it could call 142193323Sed // anything. 143193323Sed if (F->isDeclaration() && !F->isIntrinsic()) 144193323Sed Node->addCalledFunction(CallSite(), CallsExternalNode); 145193323Sed 146193323Sed // Look for calls by this function. 147193323Sed for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) 148193323Sed for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); 149193323Sed II != IE; ++II) { 150212904Sdim CallSite CS(cast<Value>(II)); 151212904Sdim if (CS && !isa<DbgInfoIntrinsic>(II)) { 152193323Sed const Function *Callee = CS.getCalledFunction(); 153193323Sed if (Callee) 154193323Sed Node->addCalledFunction(CS, getOrInsertFunction(Callee)); 155193323Sed else 156193323Sed Node->addCalledFunction(CS, CallsExternalNode); 157193323Sed } 158193323Sed } 159193323Sed } 160193323Sed 161193323Sed // 162193323Sed // destroy - Release memory for the call graph 163193323Sed virtual void destroy() { 164193323Sed /// CallsExternalNode is not in the function map, delete it explicitly. 165207618Srdivacky if (CallsExternalNode) { 166207618Srdivacky CallsExternalNode->allReferencesDropped(); 167207618Srdivacky delete CallsExternalNode; 168207618Srdivacky CallsExternalNode = 0; 169207618Srdivacky } 170193323Sed CallGraph::destroy(); 171193323Sed } 172193323Sed}; 173193323Sed 174193323Sed} //End anonymous namespace 175193323Sed 176218893SdimINITIALIZE_ANALYSIS_GROUP(CallGraph, "Call Graph", BasicCallGraph) 177212904SdimINITIALIZE_AG_PASS(BasicCallGraph, CallGraph, "basiccg", 178218893Sdim "Basic CallGraph Construction", false, true, true) 179193323Sed 180193323Sedchar CallGraph::ID = 0; 181193323Sedchar BasicCallGraph::ID = 0; 182193323Sed 183193323Sedvoid CallGraph::initialize(Module &M) { 184193323Sed Mod = &M; 185193323Sed} 186193323Sed 187193323Sedvoid CallGraph::destroy() { 188198090Srdivacky if (FunctionMap.empty()) return; 189198090Srdivacky 190207618Srdivacky // Reset all node's use counts to zero before deleting them to prevent an 191207618Srdivacky // assertion from firing. 192207618Srdivacky#ifndef NDEBUG 193198090Srdivacky for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 194207618Srdivacky I != E; ++I) 195207618Srdivacky I->second->allReferencesDropped(); 196207618Srdivacky#endif 197207618Srdivacky 198207618Srdivacky for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 199198090Srdivacky I != E; ++I) 200198090Srdivacky delete I->second; 201198090Srdivacky FunctionMap.clear(); 202193323Sed} 203193323Sed 204198090Srdivackyvoid CallGraph::print(raw_ostream &OS, Module*) const { 205193323Sed for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) 206193323Sed I->second->print(OS); 207193323Sed} 208193323Sedvoid CallGraph::dump() const { 209201360Srdivacky print(dbgs(), 0); 210193323Sed} 211193323Sed 212193323Sed//===----------------------------------------------------------------------===// 213193323Sed// Implementations of public modification methods 214193323Sed// 215193323Sed 216193323Sed// removeFunctionFromModule - Unlink the function from this module, returning 217193323Sed// it. Because this removes the function from the module, the call graph node 218193323Sed// is destroyed. This is only valid if the function does not call any other 219193323Sed// functions (ie, there are no edges in it's CGN). The easiest way to do this 220193323Sed// is to dropAllReferences before calling this. 221193323Sed// 222193323SedFunction *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 223198090Srdivacky assert(CGN->empty() && "Cannot remove function from call " 224193323Sed "graph if it references other functions!"); 225193323Sed Function *F = CGN->getFunction(); // Get the function for the call graph node 226193323Sed delete CGN; // Delete the call graph node for this func 227193323Sed FunctionMap.erase(F); // Remove the call graph node from the map 228193323Sed 229193323Sed Mod->getFunctionList().remove(F); 230193323Sed return F; 231193323Sed} 232193323Sed 233218893Sdim/// spliceFunction - Replace the function represented by this node by another. 234218893Sdim/// This does not rescan the body of the function, so it is suitable when 235218893Sdim/// splicing the body of the old function to the new while also updating all 236218893Sdim/// callers from old to new. 237218893Sdim/// 238218893Sdimvoid CallGraph::spliceFunction(const Function *From, const Function *To) { 239218893Sdim assert(FunctionMap.count(From) && "No CallGraphNode for function!"); 240218893Sdim assert(!FunctionMap.count(To) && 241218893Sdim "Pointing CallGraphNode at a function that already exists"); 242218893Sdim FunctionMapTy::iterator I = FunctionMap.find(From); 243218893Sdim I->second->F = const_cast<Function*>(To); 244218893Sdim FunctionMap[To] = I->second; 245218893Sdim FunctionMap.erase(I); 246218893Sdim} 247218893Sdim 248193323Sed// getOrInsertFunction - This method is identical to calling operator[], but 249193323Sed// it will insert a new CallGraphNode for the specified function if one does 250193323Sed// not already exist. 251193323SedCallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { 252193323Sed CallGraphNode *&CGN = FunctionMap[F]; 253193323Sed if (CGN) return CGN; 254193323Sed 255193323Sed assert((!F || F->getParent() == Mod) && "Function not in current module!"); 256193323Sed return CGN = new CallGraphNode(const_cast<Function*>(F)); 257193323Sed} 258193323Sed 259198090Srdivackyvoid CallGraphNode::print(raw_ostream &OS) const { 260193323Sed if (Function *F = getFunction()) 261198090Srdivacky OS << "Call graph node for function: '" << F->getName() << "'"; 262193323Sed else 263198090Srdivacky OS << "Call graph node <<null function>>"; 264198090Srdivacky 265207618Srdivacky OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n'; 266193323Sed 267207618Srdivacky for (const_iterator I = begin(), E = end(); I != E; ++I) { 268207618Srdivacky OS << " CS<" << I->first << "> calls "; 269193323Sed if (Function *FI = I->second->getFunction()) 270207618Srdivacky OS << "function '" << FI->getName() <<"'\n"; 271207618Srdivacky else 272207618Srdivacky OS << "external node\n"; 273207618Srdivacky } 274207618Srdivacky OS << '\n'; 275193323Sed} 276193323Sed 277201360Srdivackyvoid CallGraphNode::dump() const { print(dbgs()); } 278193323Sed 279193323Sed/// removeCallEdgeFor - This method removes the edge in the node for the 280193323Sed/// specified call site. Note that this method takes linear time, so it 281193323Sed/// should be used sparingly. 282193323Sedvoid CallGraphNode::removeCallEdgeFor(CallSite CS) { 283193323Sed for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 284193323Sed assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 285198090Srdivacky if (I->first == CS.getInstruction()) { 286198090Srdivacky I->second->DropRef(); 287198090Srdivacky *I = CalledFunctions.back(); 288198090Srdivacky CalledFunctions.pop_back(); 289193323Sed return; 290193323Sed } 291193323Sed } 292193323Sed} 293193323Sed 294193323Sed// removeAnyCallEdgeTo - This method removes any call edges from this node to 295193323Sed// the specified callee function. This takes more time to execute than 296193323Sed// removeCallEdgeTo, so it should not be used unless necessary. 297193323Sedvoid CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 298193323Sed for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 299193323Sed if (CalledFunctions[i].second == Callee) { 300198090Srdivacky Callee->DropRef(); 301193323Sed CalledFunctions[i] = CalledFunctions.back(); 302193323Sed CalledFunctions.pop_back(); 303193323Sed --i; --e; 304193323Sed } 305193323Sed} 306193323Sed 307193323Sed/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite 308193323Sed/// from this node to the specified callee function. 309193323Sedvoid CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) { 310193323Sed for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 311193323Sed assert(I != CalledFunctions.end() && "Cannot find callee to remove!"); 312193323Sed CallRecord &CR = *I; 313198090Srdivacky if (CR.second == Callee && CR.first == 0) { 314198090Srdivacky Callee->DropRef(); 315198090Srdivacky *I = CalledFunctions.back(); 316198090Srdivacky CalledFunctions.pop_back(); 317193323Sed return; 318193323Sed } 319193323Sed } 320193323Sed} 321193323Sed 322198090Srdivacky/// replaceCallEdge - This method replaces the edge in the node for the 323198090Srdivacky/// specified call site with a new one. Note that this method takes linear 324198090Srdivacky/// time, so it should be used sparingly. 325198090Srdivackyvoid CallGraphNode::replaceCallEdge(CallSite CS, 326198090Srdivacky CallSite NewCS, CallGraphNode *NewNode){ 327193323Sed for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 328198090Srdivacky assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 329198090Srdivacky if (I->first == CS.getInstruction()) { 330198090Srdivacky I->second->DropRef(); 331198090Srdivacky I->first = NewCS.getInstruction(); 332198090Srdivacky I->second = NewNode; 333198090Srdivacky NewNode->AddRef(); 334193323Sed return; 335193323Sed } 336193323Sed } 337193323Sed} 338193323Sed 339193323Sed// Enuse that users of CallGraph.h also link with this file 340193323SedDEFINING_FILE_FOR(CallGraph) 341