CallGraph.cpp revision 45d10470c972d6b0bc0eff6590bc1fb016c14fd3
1//===- CallGraph.cpp - Build a Module's call graph ------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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/Support/CallSite.h" 19#include <iostream> 20using namespace llvm; 21 22static bool isOnlyADirectCall(Function *F, CallSite CS) { 23 if (!CS.getInstruction()) return false; 24 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) 25 if (*I == F) return false; 26 return true; 27} 28 29namespace { 30 31//===----------------------------------------------------------------------===// 32// BasicCallGraph class definition 33// 34class BasicCallGraph : public CallGraph, public ModulePass { 35 // Root is root of the call graph, or the external node if a 'main' function 36 // couldn't be found. 37 // 38 CallGraphNode *Root; 39 40 // ExternalCallingNode - This node has edges to all external functions and 41 // those internal functions that have their address taken. 42 CallGraphNode *ExternalCallingNode; 43 44 // CallsExternalNode - This node has edges to it from all functions making 45 // indirect calls or calling an external function. 46 CallGraphNode *CallsExternalNode; 47 48public: 49 BasicCallGraph() : Root(0), ExternalCallingNode(0), CallsExternalNode(0) {} 50 ~BasicCallGraph() { destroy(); } 51 52 // runOnModule - Compute the call graph for the specified module. 53 virtual bool runOnModule(Module &M) { 54 destroy(); 55 CallGraph::initialize(M); 56 57 ExternalCallingNode = getOrInsertFunction(0); 58 CallsExternalNode = new CallGraphNode(0); 59 Root = 0; 60 61 // Add every function to the call graph... 62 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 63 addToCallGraph(I); 64 65 // If we didn't find a main function, use the external call graph node 66 if (Root == 0) Root = ExternalCallingNode; 67 68 return false; 69 } 70 71 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 72 AU.setPreservesAll(); 73 } 74 75 virtual void print(std::ostream &o, const Module *M) const { 76 o << "CallGraph Root is: "; 77 if (Function *F = getRoot()->getFunction()) 78 o << F->getName() << "\n"; 79 else 80 o << "<<null function: 0x" << getRoot() << ">>\n"; 81 82 CallGraph::print(o, M); 83 } 84 85 virtual void releaseMemory() { 86 destroy(); 87 } 88 89 /// dump - Print out this call graph. 90 /// 91 inline void dump() const { 92 print(std::cerr, Mod); 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->hasInternalLinkage()) { 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 // If this function is not defined in this translation unit, it could call 129 // anything. 130 if (F->isExternal() && !F->getIntrinsicID()) 131 Node->addCalledFunction(CallSite(), CallsExternalNode); 132 133 // Loop over all of the users of the function... looking for callers... 134 // 135 bool isUsedExternally = false; 136 for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I){ 137 if (Instruction *Inst = dyn_cast<Instruction>(*I)) { 138 CallSite CS = CallSite::get(Inst); 139 if (isOnlyADirectCall(F, CS)) 140 getOrInsertFunction(Inst->getParent()->getParent()) 141 ->addCalledFunction(CS, Node); 142 else 143 isUsedExternally = true; 144 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(*I)) { 145 for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); 146 I != E; ++I) 147 if (Instruction *Inst = dyn_cast<Instruction>(*I)) { 148 CallSite CS = CallSite::get(Inst); 149 if (isOnlyADirectCall(F, CS)) 150 getOrInsertFunction(Inst->getParent()->getParent()) 151 ->addCalledFunction(CS, Node); 152 else 153 isUsedExternally = true; 154 } else { 155 isUsedExternally = true; 156 } 157 } else { // Can't classify the user! 158 isUsedExternally = true; 159 } 160 } 161 if (isUsedExternally) 162 ExternalCallingNode->addCalledFunction(CallSite(), Node); 163 164 // Look for an indirect function call. 165 for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) 166 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); 167 II != IE; ++II) { 168 CallSite CS = CallSite::get(II); 169 if (CS.getInstruction() && !CS.getCalledFunction()) 170 Node->addCalledFunction(CS, CallsExternalNode); 171 } 172 } 173 174 // 175 // destroy - Release memory for the call graph 176 virtual void destroy() { 177 if (!CallsExternalNode) { 178 delete CallsExternalNode; 179 CallsExternalNode = 0; 180 } 181 } 182}; 183 184RegisterAnalysisGroup<CallGraph> X("Call Graph"); 185RegisterPass<BasicCallGraph> Y("basiccg", "Basic CallGraph Construction"); 186RegisterAnalysisGroup<CallGraph, true> Z(Y); 187 188} //End anonymous namespace 189 190void CallGraph::initialize(Module &M) { 191 destroy(); 192 Mod = &M; 193} 194 195void CallGraph::destroy() { 196 if (!FunctionMap.empty()) { 197 for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 198 I != E; ++I) 199 delete I->second; 200 FunctionMap.clear(); 201 } 202} 203 204void CallGraph::print(std::ostream &OS, const Module *M) const { 205 for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) 206 I->second->print(OS); 207} 208 209void CallGraph::dump() const { 210 print(std::cerr, 0); 211} 212 213//===----------------------------------------------------------------------===// 214// Implementations of public modification methods 215// 216 217// removeFunctionFromModule - Unlink the function from this module, returning 218// it. Because this removes the function from the module, the call graph node 219// is destroyed. This is only valid if the function does not call any other 220// functions (ie, there are no edges in it's CGN). The easiest way to do this 221// is to dropAllReferences before calling this. 222// 223Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 224 assert(CGN->CalledFunctions.empty() && "Cannot remove function from call " 225 "graph if it references other functions!"); 226 Function *F = CGN->getFunction(); // Get the function for the call graph node 227 delete CGN; // Delete the call graph node for this func 228 FunctionMap.erase(F); // Remove the call graph node from the map 229 230 Mod->getFunctionList().remove(F); 231 return F; 232} 233 234// changeFunction - This method changes the function associated with this 235// CallGraphNode, for use by transformations that need to change the prototype 236// of a Function (thus they must create a new Function and move the old code 237// over). 238void CallGraph::changeFunction(Function *OldF, Function *NewF) { 239 iterator I = FunctionMap.find(OldF); 240 CallGraphNode *&New = FunctionMap[NewF]; 241 assert(I != FunctionMap.end() && I->second && !New && 242 "OldF didn't exist in CG or NewF already does!"); 243 New = I->second; 244 New->F = NewF; 245 FunctionMap.erase(I); 246} 247 248// getOrInsertFunction - This method is identical to calling operator[], but 249// it will insert a new CallGraphNode for the specified function if one does 250// not already exist. 251CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { 252 CallGraphNode *&CGN = FunctionMap[F]; 253 if (CGN) return CGN; 254 255 assert((!F || F->getParent() == Mod) && "Function not in current module!"); 256 return CGN = new CallGraphNode(const_cast<Function*>(F)); 257} 258 259void CallGraphNode::print(std::ostream &OS) const { 260 if (Function *F = getFunction()) 261 OS << "Call graph node for function: '" << F->getName() <<"'\n"; 262 else 263 OS << "Call graph node <<null function: 0x" << this << ">>:\n"; 264 265 for (const_iterator I = begin(), E = end(); I != E; ++I) 266 if (I->second->getFunction()) 267 OS << " Calls function '" << I->second->getFunction()->getName() <<"'\n"; 268 else 269 OS << " Calls external node\n"; 270 OS << "\n"; 271} 272 273void CallGraphNode::dump() const { print(std::cerr); } 274 275void CallGraphNode::removeCallEdgeTo(CallGraphNode *Callee) { 276 for (unsigned i = CalledFunctions.size(); ; --i) { 277 assert(i && "Cannot find callee to remove!"); 278 if (CalledFunctions[i-1].second == Callee) { 279 CalledFunctions.erase(CalledFunctions.begin()+i-1); 280 return; 281 } 282 } 283} 284 285// removeAnyCallEdgeTo - This method removes any call edges from this node to 286// the specified callee function. This takes more time to execute than 287// removeCallEdgeTo, so it should not be used unless necessary. 288void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 289 for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 290 if (CalledFunctions[i].second == Callee) { 291 CalledFunctions[i] = CalledFunctions.back(); 292 CalledFunctions.pop_back(); 293 --i; --e; 294 } 295} 296 297// Enuse that users of CallGraph.h also link with this file 298DEFINING_FILE_FOR(CallGraph) 299