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 void llvm::BasicCallGraphStub() {} 00023 00024 static bool isOnlyADirectCall(Function *F, CallSite CS) { 00025 if (!CS.getInstruction()) return false; 00026 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) 00027 if (*I == F) return false; 00028 return true; 00029 } 00030 00031 namespace { 00032 00033 //===----------------------------------------------------------------------===// 00034 // BasicCallGraph class definition 00035 // 00036 class BasicCallGraph : public CallGraph, public ModulePass { 00037 // Root is root of the call graph, or the external node if a 'main' function 00038 // couldn't be found. 00039 // 00040 CallGraphNode *Root; 00041 00042 // ExternalCallingNode - This node has edges to all external functions and 00043 // those internal functions that have their address taken. 00044 CallGraphNode *ExternalCallingNode; 00045 00046 // CallsExternalNode - This node has edges to it from all functions making 00047 // indirect calls or calling an external function. 00048 CallGraphNode *CallsExternalNode; 00049 00050 public: 00051 BasicCallGraph() : Root(0), ExternalCallingNode(0), CallsExternalNode(0) {} 00052 ~BasicCallGraph() { destroy(); } 00053 00054 // runOnModule - Compute the call graph for the specified module. 00055 virtual bool runOnModule(Module &M) { 00056 destroy(); 00057 CallGraph::initialize(M); 00058 00059 ExternalCallingNode = getOrInsertFunction(0); 00060 CallsExternalNode = new CallGraphNode(0); 00061 Root = 0; 00062 00063 // Add every function to the call graph... 00064 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 00065 addToCallGraph(I); 00066 00067 // If we didn't find a main function, use the external call graph node 00068 if (Root == 0) Root = ExternalCallingNode; 00069 00070 return false; 00071 } 00072 00073 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00074 AU.setPreservesAll(); 00075 } 00076 00077 virtual void print(std::ostream &o, const Module *M) const { 00078 o << "CallGraph Root is: "; 00079 if (Function *F = getRoot()->getFunction()) 00080 o << F->getName() << "\n"; 00081 else 00082 o << "<<null function: 0x" << getRoot() << ">>\n"; 00083 00084 CallGraph::print(o, M); 00085 } 00086 00087 virtual void releaseMemory() { 00088 destroy(); 00089 } 00090 00091 /// dump - Print out this call graph. 00092 /// 00093 inline void dump() const { 00094 print(std::cerr, Mod); 00095 } 00096 00097 CallGraphNode* getExternalCallingNode() const { return ExternalCallingNode; } 00098 CallGraphNode* getCallsExternalNode() const { return CallsExternalNode; } 00099 00100 // getRoot - Return the root of the call graph, which is either main, or if 00101 // main cannot be found, the external node. 00102 // 00103 CallGraphNode *getRoot() { return Root; } 00104 const CallGraphNode *getRoot() const { return Root; } 00105 00106 private: 00107 //===--------------------------------------------------------------------- 00108 // Implementation of CallGraph construction 00109 // 00110 00111 // addToCallGraph - Add a function to the call graph, and link the node to all 00112 // of the functions that it calls. 00113 // 00114 void addToCallGraph(Function *F) { 00115 CallGraphNode *Node = getOrInsertFunction(F); 00116 00117 // If this function has external linkage, anything could call it... 00118 if (!F->hasInternalLinkage()) { 00119 ExternalCallingNode->addCalledFunction(Node); 00120 00121 // Found the entry point? 00122 if (F->getName() == "main") { 00123 if (Root) // Found multiple external mains? Don't pick one. 00124 Root = ExternalCallingNode; 00125 else 00126 Root = Node; // Found a main, keep track of it! 00127 } 00128 } 00129 00130 // If this function is not defined in this translation unit, it could call 00131 // anything. 00132 if (F->isExternal() && !F->getIntrinsicID()) 00133 Node->addCalledFunction(CallsExternalNode); 00134 00135 // Loop over all of the users of the function... looking for callers... 00136 // 00137 bool isUsedExternally = false; 00138 for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I){ 00139 if (Instruction *Inst = dyn_cast<Instruction>(*I)) { 00140 if (isOnlyADirectCall(F, CallSite::get(Inst))) 00141 getOrInsertFunction(Inst->getParent()->getParent()) 00142 ->addCalledFunction(Node); 00143 else 00144 isUsedExternally = true; 00145 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(*I)) { 00146 for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); 00147 I != E; ++I) 00148 if (Instruction *Inst = dyn_cast<Instruction>(*I)) { 00149 if (isOnlyADirectCall(F, CallSite::get(Inst))) 00150 getOrInsertFunction(Inst->getParent()->getParent()) 00151 ->addCalledFunction(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(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(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 00260 00261 void CallGraph::stub() {} 00262 00263 void CallGraphNode::print(std::ostream &OS) const { 00264 if (Function *F = getFunction()) 00265 OS << "Call graph node for function: '" << F->getName() <<"'\n"; 00266 else 00267 OS << "Call graph node <<null function: 0x" << this << ">>:\n"; 00268 00269 for (const_iterator I = begin(), E = end(); I != E; ++I) 00270 if ((*I)->getFunction()) 00271 OS << " Calls function '" << (*I)->getFunction()->getName() << "'\n"; 00272 else 00273 OS << " Calls external node\n"; 00274 OS << "\n"; 00275 } 00276 00277 void CallGraphNode::dump() const { print(std::cerr); } 00278 00279 void CallGraphNode::removeCallEdgeTo(CallGraphNode *Callee) { 00280 for (unsigned i = CalledFunctions.size(); ; --i) { 00281 assert(i && "Cannot find callee to remove!"); 00282 if (CalledFunctions[i-1] == Callee) { 00283 CalledFunctions.erase(CalledFunctions.begin()+i-1); 00284 return; 00285 } 00286 } 00287 } 00288 00289 // removeAnyCallEdgeTo - This method removes any call edges from this node to 00290 // the specified callee function. This takes more time to execute than 00291 // removeCallEdgeTo, so it should not be used unless necessary. 00292 void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 00293 for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 00294 if (CalledFunctions[i] == Callee) { 00295 CalledFunctions[i] = CalledFunctions.back(); 00296 CalledFunctions.pop_back(); 00297 --i; --e; 00298 } 00299 }