LLVM API Documentation
00001 //===- CallGraph.cpp - Build a Module's call graph ------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the CallGraph class and provides the BasicCallGraph 00011 // default implementation. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/Analysis/CallGraph.h" 00016 #include "llvm/Module.h" 00017 #include "llvm/Instructions.h" 00018 #include "llvm/Support/CallSite.h" 00019 #include <iostream> 00020 using namespace llvm; 00021 00022 static bool isOnlyADirectCall(Function *F, CallSite CS) { 00023 if (!CS.getInstruction()) return false; 00024 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) 00025 if (*I == F) return false; 00026 return true; 00027 } 00028 00029 namespace { 00030 00031 //===----------------------------------------------------------------------===// 00032 // BasicCallGraph class definition 00033 // 00034 class BasicCallGraph : public CallGraph, public ModulePass { 00035 // Root is root of the call graph, or the external node if a 'main' function 00036 // couldn't be found. 00037 // 00038 CallGraphNode *Root; 00039 00040 // ExternalCallingNode - This node has edges to all external functions and 00041 // those internal functions that have their address taken. 00042 CallGraphNode *ExternalCallingNode; 00043 00044 // CallsExternalNode - This node has edges to it from all functions making 00045 // indirect calls or calling an external function. 00046 CallGraphNode *CallsExternalNode; 00047 00048 public: 00049 BasicCallGraph() : Root(0), ExternalCallingNode(0), CallsExternalNode(0) {} 00050 ~BasicCallGraph() { destroy(); } 00051 00052 // runOnModule - Compute the call graph for the specified module. 00053 virtual bool runOnModule(Module &M) { 00054 destroy(); 00055 CallGraph::initialize(M); 00056 00057 ExternalCallingNode = getOrInsertFunction(0); 00058 CallsExternalNode = new CallGraphNode(0); 00059 Root = 0; 00060 00061 // Add every function to the call graph... 00062 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 00063 addToCallGraph(I); 00064 00065 // If we didn't find a main function, use the external call graph node 00066 if (Root == 0) Root = ExternalCallingNode; 00067 00068 return false; 00069 } 00070 00071 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00072 AU.setPreservesAll(); 00073 } 00074 00075 virtual void print(std::ostream &o, const Module *M) const { 00076 o << "CallGraph Root is: "; 00077 if (Function *F = getRoot()->getFunction()) 00078 o << F->getName() << "\n"; 00079 else 00080 o << "<<null function: 0x" << getRoot() << ">>\n"; 00081 00082 CallGraph::print(o, M); 00083 } 00084 00085 virtual void releaseMemory() { 00086 destroy(); 00087 } 00088 00089 /// dump - Print out this call graph. 00090 /// 00091 inline void dump() const { 00092 print(std::cerr, Mod); 00093 } 00094 00095 CallGraphNode* getExternalCallingNode() const { return ExternalCallingNode; } 00096 CallGraphNode* getCallsExternalNode() const { return CallsExternalNode; } 00097 00098 // getRoot - Return the root of the call graph, which is either main, or if 00099 // main cannot be found, the external node. 00100 // 00101 CallGraphNode *getRoot() { return Root; } 00102 const CallGraphNode *getRoot() const { return Root; } 00103 00104 private: 00105 //===--------------------------------------------------------------------- 00106 // Implementation of CallGraph construction 00107 // 00108 00109 // addToCallGraph - Add a function to the call graph, and link the node to all 00110 // of the functions that it calls. 00111 // 00112 void addToCallGraph(Function *F) { 00113 CallGraphNode *Node = getOrInsertFunction(F); 00114 00115 // If this function has external linkage, anything could call it. 00116 if (!F->hasInternalLinkage()) { 00117 ExternalCallingNode->addCalledFunction(CallSite(), Node); 00118 00119 // Found the entry point? 00120 if (F->getName() == "main") { 00121 if (Root) // Found multiple external mains? Don't pick one. 00122 Root = ExternalCallingNode; 00123 else 00124 Root = Node; // Found a main, keep track of it! 00125 } 00126 } 00127 00128 // If this function is not defined in this translation unit, it could call 00129 // anything. 00130 if (F->isExternal() && !F->getIntrinsicID()) 00131 Node->addCalledFunction(CallSite(), CallsExternalNode); 00132 00133 // Loop over all of the users of the function... looking for callers... 00134 // 00135 bool isUsedExternally = false; 00136 for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I){ 00137 if (Instruction *Inst = dyn_cast<Instruction>(*I)) { 00138 CallSite CS = CallSite::get(Inst); 00139 if (isOnlyADirectCall(F, CS)) 00140 getOrInsertFunction(Inst->getParent()->getParent()) 00141 ->addCalledFunction(CS, Node); 00142 else 00143 isUsedExternally = true; 00144 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(*I)) { 00145 for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); 00146 I != E; ++I) 00147 if (Instruction *Inst = dyn_cast<Instruction>(*I)) { 00148 CallSite CS = CallSite::get(Inst); 00149 if (isOnlyADirectCall(F, CS)) 00150 getOrInsertFunction(Inst->getParent()->getParent()) 00151 ->addCalledFunction(CS, Node); 00152 else 00153 isUsedExternally = true; 00154 } else { 00155 isUsedExternally = true; 00156 } 00157 } else { // Can't classify the user! 00158 isUsedExternally = true; 00159 } 00160 } 00161 if (isUsedExternally) 00162 ExternalCallingNode->addCalledFunction(CallSite(), Node); 00163 00164 // Look for an indirect function call. 00165 for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) 00166 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); 00167 II != IE; ++II) { 00168 CallSite CS = CallSite::get(II); 00169 if (CS.getInstruction() && !CS.getCalledFunction()) 00170 Node->addCalledFunction(CS, CallsExternalNode); 00171 } 00172 } 00173 00174 // 00175 // destroy - Release memory for the call graph 00176 virtual void destroy() { 00177 if (!CallsExternalNode) { 00178 delete CallsExternalNode; 00179 CallsExternalNode = 0; 00180 } 00181 } 00182 }; 00183 00184 RegisterAnalysisGroup<CallGraph> X("Call Graph"); 00185 RegisterOpt<BasicCallGraph> Y("basiccg", "Basic CallGraph Construction"); 00186 RegisterAnalysisGroup<CallGraph, BasicCallGraph, true> Z; 00187 00188 } //End anonymous namespace 00189 00190 void CallGraph::initialize(Module &M) { 00191 destroy(); 00192 Mod = &M; 00193 } 00194 00195 void CallGraph::destroy() { 00196 if(!FunctionMap.size()) { 00197 for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 00198 I != E; ++I) 00199 delete I->second; 00200 FunctionMap.clear(); 00201 } 00202 } 00203 00204 void CallGraph::print(std::ostream &OS, const Module *M) const { 00205 for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) 00206 I->second->print(OS); 00207 } 00208 00209 void CallGraph::dump() const { 00210 print(std::cerr, 0); 00211 } 00212 00213 //===----------------------------------------------------------------------===// 00214 // Implementations of public modification methods 00215 // 00216 00217 // removeFunctionFromModule - Unlink the function from this module, returning 00218 // it. Because this removes the function from the module, the call graph node 00219 // is destroyed. This is only valid if the function does not call any other 00220 // functions (ie, there are no edges in it's CGN). The easiest way to do this 00221 // is to dropAllReferences before calling this. 00222 // 00223 Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 00224 assert(CGN->CalledFunctions.empty() && "Cannot remove function from call " 00225 "graph if it references other functions!"); 00226 Function *F = CGN->getFunction(); // Get the function for the call graph node 00227 delete CGN; // Delete the call graph node for this func 00228 FunctionMap.erase(F); // Remove the call graph node from the map 00229 00230 Mod->getFunctionList().remove(F); 00231 return F; 00232 } 00233 00234 // changeFunction - This method changes the function associated with this 00235 // CallGraphNode, for use by transformations that need to change the prototype 00236 // of a Function (thus they must create a new Function and move the old code 00237 // over). 00238 void CallGraph::changeFunction(Function *OldF, Function *NewF) { 00239 iterator I = FunctionMap.find(OldF); 00240 CallGraphNode *&New = FunctionMap[NewF]; 00241 assert(I != FunctionMap.end() && I->second && !New && 00242 "OldF didn't exist in CG or NewF already does!"); 00243 New = I->second; 00244 New->F = NewF; 00245 FunctionMap.erase(I); 00246 } 00247 00248 // getOrInsertFunction - This method is identical to calling operator[], but 00249 // it will insert a new CallGraphNode for the specified function if one does 00250 // not already exist. 00251 CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { 00252 CallGraphNode *&CGN = FunctionMap[F]; 00253 if (CGN) return CGN; 00254 00255 assert((!F || F->getParent() == Mod) && "Function not in current module!"); 00256 return CGN = new CallGraphNode(const_cast<Function*>(F)); 00257 } 00258 00259 void CallGraphNode::print(std::ostream &OS) const { 00260 if (Function *F = getFunction()) 00261 OS << "Call graph node for function: '" << F->getName() <<"'\n"; 00262 else 00263 OS << "Call graph node <<null function: 0x" << this << ">>:\n"; 00264 00265 for (const_iterator I = begin(), E = end(); I != E; ++I) 00266 if (I->second->getFunction()) 00267 OS << " Calls function '" << I->second->getFunction()->getName() <<"'\n"; 00268 else 00269 OS << " Calls external node\n"; 00270 OS << "\n"; 00271 } 00272 00273 void CallGraphNode::dump() const { print(std::cerr); } 00274 00275 void CallGraphNode::removeCallEdgeTo(CallGraphNode *Callee) { 00276 for (unsigned i = CalledFunctions.size(); ; --i) { 00277 assert(i && "Cannot find callee to remove!"); 00278 if (CalledFunctions[i-1].second == Callee) { 00279 CalledFunctions.erase(CalledFunctions.begin()+i-1); 00280 return; 00281 } 00282 } 00283 } 00284 00285 // removeAnyCallEdgeTo - This method removes any call edges from this node to 00286 // the specified callee function. This takes more time to execute than 00287 // removeCallEdgeTo, so it should not be used unless necessary. 00288 void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 00289 for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 00290 if (CalledFunctions[i].second == Callee) { 00291 CalledFunctions[i] = CalledFunctions.back(); 00292 CalledFunctions.pop_back(); 00293 --i; --e; 00294 } 00295 } 00296 00297 // Enuse that users of CallGraph.h also link with this file 00298 DEFINING_FILE_FOR(CallGraph)