CallGraph.cpp revision 202878
1//===- CallGraph.cpp - Build a Module's call graph ------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the CallGraph class and provides the BasicCallGraph 11// default implementation. 12// 13//===----------------------------------------------------------------------===// 14 15#include "llvm/Analysis/CallGraph.h" 16#include "llvm/Module.h" 17#include "llvm/Instructions.h" 18#include "llvm/IntrinsicInst.h" 19#include "llvm/Support/CallSite.h" 20#include "llvm/Support/Debug.h" 21#include "llvm/Support/raw_ostream.h" 22using namespace llvm; 23 24namespace { 25 26//===----------------------------------------------------------------------===// 27// BasicCallGraph class definition 28// 29class BasicCallGraph : public ModulePass, public CallGraph { 30 // Root is root of the call graph, or the external node if a 'main' function 31 // couldn't be found. 32 // 33 CallGraphNode *Root; 34 35 // ExternalCallingNode - This node has edges to all external functions and 36 // those internal functions that have their address taken. 37 CallGraphNode *ExternalCallingNode; 38 39 // CallsExternalNode - This node has edges to it from all functions making 40 // indirect calls or calling an external function. 41 CallGraphNode *CallsExternalNode; 42 43public: 44 static char ID; // Class identification, replacement for typeinfo 45 BasicCallGraph() : ModulePass(&ID), Root(0), 46 ExternalCallingNode(0), CallsExternalNode(0) {} 47 48 // runOnModule - Compute the call graph for the specified module. 49 virtual bool runOnModule(Module &M) { 50 CallGraph::initialize(M); 51 52 ExternalCallingNode = getOrInsertFunction(0); 53 CallsExternalNode = new CallGraphNode(0); 54 Root = 0; 55 56 // Add every function to the call graph. 57 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 58 addToCallGraph(I); 59 60 // If we didn't find a main function, use the external call graph node 61 if (Root == 0) Root = ExternalCallingNode; 62 63 return false; 64 } 65 66 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 67 AU.setPreservesAll(); 68 } 69 70 virtual void print(raw_ostream &OS, const Module *) const { 71 OS << "CallGraph Root is: "; 72 if (Function *F = getRoot()->getFunction()) 73 OS << F->getName() << "\n"; 74 else { 75 OS << "<<null function: 0x" << getRoot() << ">>\n"; 76 } 77 78 CallGraph::print(OS, 0); 79 } 80 81 virtual void releaseMemory() { 82 destroy(); 83 } 84 85 /// getAdjustedAnalysisPointer - This method is used when a pass implements 86 /// an analysis interface through multiple inheritance. If needed, it should 87 /// override this to adjust the this pointer as needed for the specified pass 88 /// info. 89 virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) { 90 if (PI->isPassID(&CallGraph::ID)) 91 return (CallGraph*)this; 92 return this; 93 } 94 95 CallGraphNode* getExternalCallingNode() const { return ExternalCallingNode; } 96 CallGraphNode* getCallsExternalNode() const { return CallsExternalNode; } 97 98 // getRoot - Return the root of the call graph, which is either main, or if 99 // main cannot be found, the external node. 100 // 101 CallGraphNode *getRoot() { return Root; } 102 const CallGraphNode *getRoot() const { return Root; } 103 104private: 105 //===--------------------------------------------------------------------- 106 // Implementation of CallGraph construction 107 // 108 109 // addToCallGraph - Add a function to the call graph, and link the node to all 110 // of the functions that it calls. 111 // 112 void addToCallGraph(Function *F) { 113 CallGraphNode *Node = getOrInsertFunction(F); 114 115 // If this function has external linkage, anything could call it. 116 if (!F->hasLocalLinkage()) { 117 ExternalCallingNode->addCalledFunction(CallSite(), Node); 118 119 // Found the entry point? 120 if (F->getName() == "main") { 121 if (Root) // Found multiple external mains? Don't pick one. 122 Root = ExternalCallingNode; 123 else 124 Root = Node; // Found a main, keep track of it! 125 } 126 } 127 128 // Loop over all of the users of the function, looking for non-call uses. 129 for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I) 130 if ((!isa<CallInst>(I) && !isa<InvokeInst>(I)) 131 || !CallSite(cast<Instruction>(I)).isCallee(I)) { 132 // Not a call, or being used as a parameter rather than as the callee. 133 ExternalCallingNode->addCalledFunction(CallSite(), Node); 134 break; 135 } 136 137 // If this function is not defined in this translation unit, it could call 138 // anything. 139 if (F->isDeclaration() && !F->isIntrinsic()) 140 Node->addCalledFunction(CallSite(), CallsExternalNode); 141 142 // Look for calls by this function. 143 for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) 144 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); 145 II != IE; ++II) { 146 CallSite CS = CallSite::get(II); 147 if (CS.getInstruction() && !isa<DbgInfoIntrinsic>(II)) { 148 const Function *Callee = CS.getCalledFunction(); 149 if (Callee) 150 Node->addCalledFunction(CS, getOrInsertFunction(Callee)); 151 else 152 Node->addCalledFunction(CS, CallsExternalNode); 153 } 154 } 155 } 156 157 // 158 // destroy - Release memory for the call graph 159 virtual void destroy() { 160 /// CallsExternalNode is not in the function map, delete it explicitly. 161 delete CallsExternalNode; 162 CallsExternalNode = 0; 163 CallGraph::destroy(); 164 } 165}; 166 167} //End anonymous namespace 168 169static RegisterAnalysisGroup<CallGraph> X("Call Graph"); 170static RegisterPass<BasicCallGraph> 171Y("basiccg", "Basic CallGraph Construction", false, true); 172static RegisterAnalysisGroup<CallGraph, true> Z(Y); 173 174char CallGraph::ID = 0; 175char BasicCallGraph::ID = 0; 176 177void CallGraph::initialize(Module &M) { 178 Mod = &M; 179} 180 181void CallGraph::destroy() { 182 if (FunctionMap.empty()) return; 183 184 for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 185 I != E; ++I) 186 delete I->second; 187 FunctionMap.clear(); 188} 189 190void CallGraph::print(raw_ostream &OS, Module*) const { 191 for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) 192 I->second->print(OS); 193} 194void CallGraph::dump() const { 195 print(dbgs(), 0); 196} 197 198//===----------------------------------------------------------------------===// 199// Implementations of public modification methods 200// 201 202// removeFunctionFromModule - Unlink the function from this module, returning 203// it. Because this removes the function from the module, the call graph node 204// is destroyed. This is only valid if the function does not call any other 205// functions (ie, there are no edges in it's CGN). The easiest way to do this 206// is to dropAllReferences before calling this. 207// 208Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 209 assert(CGN->empty() && "Cannot remove function from call " 210 "graph if it references other functions!"); 211 Function *F = CGN->getFunction(); // Get the function for the call graph node 212 delete CGN; // Delete the call graph node for this func 213 FunctionMap.erase(F); // Remove the call graph node from the map 214 215 Mod->getFunctionList().remove(F); 216 return F; 217} 218 219// getOrInsertFunction - This method is identical to calling operator[], but 220// it will insert a new CallGraphNode for the specified function if one does 221// not already exist. 222CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { 223 CallGraphNode *&CGN = FunctionMap[F]; 224 if (CGN) return CGN; 225 226 assert((!F || F->getParent() == Mod) && "Function not in current module!"); 227 return CGN = new CallGraphNode(const_cast<Function*>(F)); 228} 229 230void CallGraphNode::print(raw_ostream &OS) const { 231 if (Function *F = getFunction()) 232 OS << "Call graph node for function: '" << F->getName() << "'"; 233 else 234 OS << "Call graph node <<null function>>"; 235 236 OS << "<<0x" << this << ">> #uses=" << getNumReferences() << '\n'; 237 238 for (const_iterator I = begin(), E = end(); I != E; ++I) 239 if (Function *FI = I->second->getFunction()) 240 OS << " Calls function '" << FI->getName() <<"'\n"; 241 else 242 OS << " Calls external node\n"; 243 OS << "\n"; 244} 245 246void CallGraphNode::dump() const { print(dbgs()); } 247 248/// removeCallEdgeFor - This method removes the edge in the node for the 249/// specified call site. Note that this method takes linear time, so it 250/// should be used sparingly. 251void CallGraphNode::removeCallEdgeFor(CallSite CS) { 252 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 253 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 254 if (I->first == CS.getInstruction()) { 255 I->second->DropRef(); 256 *I = CalledFunctions.back(); 257 CalledFunctions.pop_back(); 258 return; 259 } 260 } 261} 262 263 264// removeAnyCallEdgeTo - This method removes any call edges from this node to 265// the specified callee function. This takes more time to execute than 266// removeCallEdgeTo, so it should not be used unless necessary. 267void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 268 for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 269 if (CalledFunctions[i].second == Callee) { 270 Callee->DropRef(); 271 CalledFunctions[i] = CalledFunctions.back(); 272 CalledFunctions.pop_back(); 273 --i; --e; 274 } 275} 276 277/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite 278/// from this node to the specified callee function. 279void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) { 280 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 281 assert(I != CalledFunctions.end() && "Cannot find callee to remove!"); 282 CallRecord &CR = *I; 283 if (CR.second == Callee && CR.first == 0) { 284 Callee->DropRef(); 285 *I = CalledFunctions.back(); 286 CalledFunctions.pop_back(); 287 return; 288 } 289 } 290} 291 292/// replaceCallEdge - This method replaces the edge in the node for the 293/// specified call site with a new one. Note that this method takes linear 294/// time, so it should be used sparingly. 295void CallGraphNode::replaceCallEdge(CallSite CS, 296 CallSite NewCS, CallGraphNode *NewNode){ 297 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 298 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 299 if (I->first == CS.getInstruction()) { 300 I->second->DropRef(); 301 I->first = NewCS.getInstruction(); 302 I->second = NewNode; 303 NewNode->AddRef(); 304 return; 305 } 306 } 307} 308 309// Enuse that users of CallGraph.h also link with this file 310DEFINING_FILE_FOR(CallGraph) 311