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. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "llvm/Analysis/CallGraph.h" 00015 #include "llvm/Module.h" 00016 #include "llvm/Instructions.h" 00017 #include "llvm/Support/CallSite.h" 00018 #include "llvm/ADT/STLExtras.h" 00019 #include <iostream> 00020 using namespace llvm; 00021 00022 static RegisterAnalysis<CallGraph> X("callgraph", "Call Graph Construction"); 00023 00024 // getNodeFor - Return the node for the specified function or create one if it 00025 // does not already exist. 00026 // 00027 CallGraphNode *CallGraph::getNodeFor(Function *F) { 00028 CallGraphNode *&CGN = FunctionMap[F]; 00029 if (CGN) return CGN; 00030 00031 assert((!F || F->getParent() == Mod) && "Function not in current module!"); 00032 return CGN = new CallGraphNode(F); 00033 } 00034 00035 static bool isOnlyADirectCall(Function *F, CallSite CS) { 00036 if (!CS.getInstruction()) return false; 00037 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) 00038 if (*I == F) return false; 00039 return true; 00040 } 00041 00042 // addToCallGraph - Add a function to the call graph, and link the node to all 00043 // of the functions that it calls. 00044 // 00045 void CallGraph::addToCallGraph(Function *F) { 00046 CallGraphNode *Node = getNodeFor(F); 00047 00048 // If this function has external linkage, anything could call it... 00049 if (!F->hasInternalLinkage()) { 00050 ExternalCallingNode->addCalledFunction(Node); 00051 00052 // Found the entry point? 00053 if (F->getName() == "main") { 00054 if (Root) // Found multiple external mains? Don't pick one. 00055 Root = ExternalCallingNode; 00056 else 00057 Root = Node; // Found a main, keep track of it! 00058 } 00059 } 00060 00061 // If this function is not defined in this translation unit, it could call 00062 // anything. 00063 if (F->isExternal() && !F->getIntrinsicID()) 00064 Node->addCalledFunction(CallsExternalNode); 00065 00066 // Loop over all of the users of the function... looking for callers... 00067 // 00068 bool isUsedExternally = false; 00069 for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I) { 00070 if (Instruction *Inst = dyn_cast<Instruction>(*I)) { 00071 if (isOnlyADirectCall(F, CallSite::get(Inst))) 00072 getNodeFor(Inst->getParent()->getParent())->addCalledFunction(Node); 00073 else 00074 isUsedExternally = true; 00075 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(*I)) { 00076 for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); 00077 I != E; ++I) 00078 if (Instruction *Inst = dyn_cast<Instruction>(*I)) { 00079 if (isOnlyADirectCall(F, CallSite::get(Inst))) 00080 getNodeFor(Inst->getParent()->getParent())->addCalledFunction(Node); 00081 else 00082 isUsedExternally = true; 00083 } else { 00084 isUsedExternally = true; 00085 } 00086 } else { // Can't classify the user! 00087 isUsedExternally = true; 00088 } 00089 } 00090 if (isUsedExternally) 00091 ExternalCallingNode->addCalledFunction(Node); 00092 00093 // Look for an indirect function call... 00094 for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) 00095 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; ++II){ 00096 CallSite CS = CallSite::get(II); 00097 if (CS.getInstruction() && !CS.getCalledFunction()) 00098 Node->addCalledFunction(CallsExternalNode); 00099 } 00100 } 00101 00102 bool CallGraph::runOnModule(Module &M) { 00103 destroy(); 00104 00105 Mod = &M; 00106 ExternalCallingNode = getNodeFor(0); 00107 CallsExternalNode = new CallGraphNode(0); 00108 Root = 0; 00109 00110 // Add every function to the call graph... 00111 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 00112 addToCallGraph(I); 00113 00114 // If we didn't find a main function, use the external call graph node 00115 if (Root == 0) Root = ExternalCallingNode; 00116 00117 return false; 00118 } 00119 00120 void CallGraph::destroy() { 00121 for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 00122 I != E; ++I) 00123 delete I->second; 00124 FunctionMap.clear(); 00125 delete CallsExternalNode; 00126 CallsExternalNode = 0; 00127 } 00128 00129 void CallGraphNode::print(std::ostream &OS) const { 00130 if (Function *F = getFunction()) 00131 OS << "Call graph node for function: '" << F->getName() <<"'\n"; 00132 else 00133 OS << "Call graph node <<null function: 0x" << this << ">>:\n"; 00134 00135 for (const_iterator I = begin(), E = end(); I != E; ++I) 00136 if ((*I)->getFunction()) 00137 OS << " Calls function '" << (*I)->getFunction()->getName() << "'\n"; 00138 else 00139 OS << " Calls external node\n"; 00140 OS << "\n"; 00141 } 00142 00143 void CallGraphNode::dump() const { print(std::cerr); } 00144 00145 void CallGraph::print(std::ostream &OS, const Module *M) const { 00146 OS << "CallGraph Root is: "; 00147 if (Function *F = getRoot()->getFunction()) 00148 OS << F->getName() << "\n"; 00149 else 00150 OS << "<<null function: 0x" << getRoot() << ">>\n"; 00151 00152 for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) 00153 I->second->print(OS); 00154 } 00155 00156 void CallGraph::dump() const { 00157 print(std::cerr, 0); 00158 } 00159 00160 00161 //===----------------------------------------------------------------------===// 00162 // Implementations of public modification methods 00163 // 00164 00165 // removeFunctionFromModule - Unlink the function from this module, returning 00166 // it. Because this removes the function from the module, the call graph node 00167 // is destroyed. This is only valid if the function does not call any other 00168 // functions (ie, there are no edges in it's CGN). The easiest way to do this 00169 // is to dropAllReferences before calling this. 00170 // 00171 Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 00172 assert(CGN->CalledFunctions.empty() && "Cannot remove function from call " 00173 "graph if it references other functions!"); 00174 Function *F = CGN->getFunction(); // Get the function for the call graph node 00175 delete CGN; // Delete the call graph node for this func 00176 FunctionMap.erase(F); // Remove the call graph node from the map 00177 00178 Mod->getFunctionList().remove(F); 00179 return F; 00180 } 00181 00182 // changeFunction - This method changes the function associated with this 00183 // CallGraphNode, for use by transformations that need to change the prototype 00184 // of a Function (thus they must create a new Function and move the old code 00185 // over). 00186 void CallGraph::changeFunction(Function *OldF, Function *NewF) { 00187 iterator I = FunctionMap.find(OldF); 00188 CallGraphNode *&New = FunctionMap[NewF]; 00189 assert(I != FunctionMap.end() && I->second && !New && 00190 "OldF didn't exist in CG or NewF already does!"); 00191 New = I->second; 00192 New->F = NewF; 00193 FunctionMap.erase(I); 00194 } 00195 00196 00197 void CallGraph::stub() {} 00198 00199 void CallGraphNode::removeCallEdgeTo(CallGraphNode *Callee) { 00200 for (unsigned i = CalledFunctions.size(); ; --i) { 00201 assert(i && "Cannot find callee to remove!"); 00202 if (CalledFunctions[i-1] == Callee) { 00203 CalledFunctions.erase(CalledFunctions.begin()+i-1); 00204 return; 00205 } 00206 } 00207 } 00208 00209 // removeAnyCallEdgeTo - This method removes any call edges from this node to 00210 // the specified callee function. This takes more time to execute than 00211 // removeCallEdgeTo, so it should not be used unless necessary. 00212 void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 00213 for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 00214 if (CalledFunctions[i] == Callee) { 00215 CalledFunctions[i] = CalledFunctions.back(); 00216 CalledFunctions.pop_back(); 00217 --i; --e; 00218 } 00219 }