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" 16249423Sdim#include "llvm/IR/Instructions.h" 17249423Sdim#include "llvm/IR/IntrinsicInst.h" 18249423Sdim#include "llvm/IR/Module.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 130234353Sdim // If this function has its address taken, anything could call it. 131234353Sdim if (F->hasAddressTaken()) 132234353Sdim ExternalCallingNode->addCalledFunction(CallSite(), Node); 133193323Sed 134193323Sed // If this function is not defined in this translation unit, it could call 135193323Sed // anything. 136193323Sed if (F->isDeclaration() && !F->isIntrinsic()) 137193323Sed Node->addCalledFunction(CallSite(), CallsExternalNode); 138193323Sed 139193323Sed // Look for calls by this function. 140193323Sed for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) 141193323Sed for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); 142193323Sed II != IE; ++II) { 143212904Sdim CallSite CS(cast<Value>(II)); 144243830Sdim if (CS) { 145193323Sed const Function *Callee = CS.getCalledFunction(); 146243830Sdim if (!Callee) 147243830Sdim // Indirect calls of intrinsics are not allowed so no need to check. 148243830Sdim Node->addCalledFunction(CS, CallsExternalNode); 149243830Sdim else if (!Callee->isIntrinsic()) 150193323Sed Node->addCalledFunction(CS, getOrInsertFunction(Callee)); 151193323Sed } 152193323Sed } 153193323Sed } 154193323Sed 155193323Sed // 156193323Sed // destroy - Release memory for the call graph 157193323Sed virtual void destroy() { 158193323Sed /// CallsExternalNode is not in the function map, delete it explicitly. 159207618Srdivacky if (CallsExternalNode) { 160207618Srdivacky CallsExternalNode->allReferencesDropped(); 161207618Srdivacky delete CallsExternalNode; 162207618Srdivacky CallsExternalNode = 0; 163207618Srdivacky } 164193323Sed CallGraph::destroy(); 165193323Sed } 166193323Sed}; 167193323Sed 168193323Sed} //End anonymous namespace 169193323Sed 170218893SdimINITIALIZE_ANALYSIS_GROUP(CallGraph, "Call Graph", BasicCallGraph) 171212904SdimINITIALIZE_AG_PASS(BasicCallGraph, CallGraph, "basiccg", 172218893Sdim "Basic CallGraph Construction", false, true, true) 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 184207618Srdivacky // Reset all node's use counts to zero before deleting them to prevent an 185207618Srdivacky // assertion from firing. 186207618Srdivacky#ifndef NDEBUG 187198090Srdivacky for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 188207618Srdivacky I != E; ++I) 189207618Srdivacky I->second->allReferencesDropped(); 190207618Srdivacky#endif 191207618Srdivacky 192207618Srdivacky for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 193198090Srdivacky I != E; ++I) 194198090Srdivacky delete I->second; 195198090Srdivacky FunctionMap.clear(); 196193323Sed} 197193323Sed 198198090Srdivackyvoid CallGraph::print(raw_ostream &OS, Module*) const { 199193323Sed for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) 200193323Sed I->second->print(OS); 201193323Sed} 202243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 203193323Sedvoid CallGraph::dump() const { 204201360Srdivacky print(dbgs(), 0); 205193323Sed} 206243830Sdim#endif 207193323Sed 208193323Sed//===----------------------------------------------------------------------===// 209193323Sed// Implementations of public modification methods 210193323Sed// 211193323Sed 212193323Sed// removeFunctionFromModule - Unlink the function from this module, returning 213193323Sed// it. Because this removes the function from the module, the call graph node 214193323Sed// is destroyed. This is only valid if the function does not call any other 215193323Sed// functions (ie, there are no edges in it's CGN). The easiest way to do this 216193323Sed// is to dropAllReferences before calling this. 217193323Sed// 218193323SedFunction *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 219198090Srdivacky assert(CGN->empty() && "Cannot remove function from call " 220193323Sed "graph if it references other functions!"); 221193323Sed Function *F = CGN->getFunction(); // Get the function for the call graph node 222193323Sed delete CGN; // Delete the call graph node for this func 223193323Sed FunctionMap.erase(F); // Remove the call graph node from the map 224193323Sed 225193323Sed Mod->getFunctionList().remove(F); 226193323Sed return F; 227193323Sed} 228193323Sed 229218893Sdim/// spliceFunction - Replace the function represented by this node by another. 230218893Sdim/// This does not rescan the body of the function, so it is suitable when 231218893Sdim/// splicing the body of the old function to the new while also updating all 232218893Sdim/// callers from old to new. 233218893Sdim/// 234218893Sdimvoid CallGraph::spliceFunction(const Function *From, const Function *To) { 235218893Sdim assert(FunctionMap.count(From) && "No CallGraphNode for function!"); 236218893Sdim assert(!FunctionMap.count(To) && 237218893Sdim "Pointing CallGraphNode at a function that already exists"); 238218893Sdim FunctionMapTy::iterator I = FunctionMap.find(From); 239218893Sdim I->second->F = const_cast<Function*>(To); 240218893Sdim FunctionMap[To] = I->second; 241218893Sdim FunctionMap.erase(I); 242218893Sdim} 243218893Sdim 244193323Sed// getOrInsertFunction - This method is identical to calling operator[], but 245193323Sed// it will insert a new CallGraphNode for the specified function if one does 246193323Sed// not already exist. 247193323SedCallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { 248193323Sed CallGraphNode *&CGN = FunctionMap[F]; 249193323Sed if (CGN) return CGN; 250193323Sed 251193323Sed assert((!F || F->getParent() == Mod) && "Function not in current module!"); 252193323Sed return CGN = new CallGraphNode(const_cast<Function*>(F)); 253193323Sed} 254193323Sed 255198090Srdivackyvoid CallGraphNode::print(raw_ostream &OS) const { 256193323Sed if (Function *F = getFunction()) 257198090Srdivacky OS << "Call graph node for function: '" << F->getName() << "'"; 258193323Sed else 259198090Srdivacky OS << "Call graph node <<null function>>"; 260198090Srdivacky 261207618Srdivacky OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n'; 262193323Sed 263207618Srdivacky for (const_iterator I = begin(), E = end(); I != E; ++I) { 264207618Srdivacky OS << " CS<" << I->first << "> calls "; 265193323Sed if (Function *FI = I->second->getFunction()) 266207618Srdivacky OS << "function '" << FI->getName() <<"'\n"; 267207618Srdivacky else 268207618Srdivacky OS << "external node\n"; 269207618Srdivacky } 270207618Srdivacky OS << '\n'; 271193323Sed} 272193323Sed 273243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 274201360Srdivackyvoid CallGraphNode::dump() const { print(dbgs()); } 275243830Sdim#endif 276193323Sed 277193323Sed/// removeCallEdgeFor - This method removes the edge in the node for the 278193323Sed/// specified call site. Note that this method takes linear time, so it 279193323Sed/// should be used sparingly. 280193323Sedvoid CallGraphNode::removeCallEdgeFor(CallSite CS) { 281193323Sed for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 282193323Sed assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 283198090Srdivacky if (I->first == CS.getInstruction()) { 284198090Srdivacky I->second->DropRef(); 285198090Srdivacky *I = CalledFunctions.back(); 286198090Srdivacky CalledFunctions.pop_back(); 287193323Sed return; 288193323Sed } 289193323Sed } 290193323Sed} 291193323Sed 292193323Sed// removeAnyCallEdgeTo - This method removes any call edges from this node to 293193323Sed// the specified callee function. This takes more time to execute than 294193323Sed// removeCallEdgeTo, so it should not be used unless necessary. 295193323Sedvoid CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 296193323Sed for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 297193323Sed if (CalledFunctions[i].second == Callee) { 298198090Srdivacky Callee->DropRef(); 299193323Sed CalledFunctions[i] = CalledFunctions.back(); 300193323Sed CalledFunctions.pop_back(); 301193323Sed --i; --e; 302193323Sed } 303193323Sed} 304193323Sed 305193323Sed/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite 306193323Sed/// from this node to the specified callee function. 307193323Sedvoid CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) { 308193323Sed for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 309193323Sed assert(I != CalledFunctions.end() && "Cannot find callee to remove!"); 310193323Sed CallRecord &CR = *I; 311198090Srdivacky if (CR.second == Callee && CR.first == 0) { 312198090Srdivacky Callee->DropRef(); 313198090Srdivacky *I = CalledFunctions.back(); 314198090Srdivacky CalledFunctions.pop_back(); 315193323Sed return; 316193323Sed } 317193323Sed } 318193323Sed} 319193323Sed 320198090Srdivacky/// replaceCallEdge - This method replaces the edge in the node for the 321198090Srdivacky/// specified call site with a new one. Note that this method takes linear 322198090Srdivacky/// time, so it should be used sparingly. 323198090Srdivackyvoid CallGraphNode::replaceCallEdge(CallSite CS, 324198090Srdivacky CallSite NewCS, CallGraphNode *NewNode){ 325193323Sed for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 326198090Srdivacky assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 327198090Srdivacky if (I->first == CS.getInstruction()) { 328198090Srdivacky I->second->DropRef(); 329198090Srdivacky I->first = NewCS.getInstruction(); 330198090Srdivacky I->second = NewNode; 331198090Srdivacky NewNode->AddRef(); 332193323Sed return; 333193323Sed } 334193323Sed } 335193323Sed} 336193323Sed 337193323Sed// Enuse that users of CallGraph.h also link with this file 338193323SedDEFINING_FILE_FOR(CallGraph) 339