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" 22 using namespace llvm; 23 24 namespace { 25 26 //===----------------------------------------------------------------------===// 27 // BasicCallGraph class definition 28 // 29 class 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 43 public: 44 static char ID; // Class identification, replacement for typeinfo 45 BasicCallGraph() : ModulePass(ID), Root(0), 46 ExternalCallingNode(0), CallsExternalNode(0) { 47 initializeBasicCallGraphPass(*PassRegistry::getPassRegistry()); 48 } 49 50 // runOnModule - Compute the call graph for the specified module. 51 virtual bool runOnModule(Module &M) { 52 CallGraph::initialize(M); 53 54 ExternalCallingNode = getOrInsertFunction(0); 55 CallsExternalNode = new CallGraphNode(0); 56 Root = 0; 57 58 // Add every function to the call graph. 59 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 60 addToCallGraph(I); 61 62 // If we didn't find a main function, use the external call graph node 63 if (Root == 0) Root = ExternalCallingNode; 64 65 return false; 66 } 67 68 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 69 AU.setPreservesAll(); 70 } 71 72 virtual void print(raw_ostream &OS, const Module *) const { 73 OS << "CallGraph Root is: "; 74 if (Function *F = getRoot()->getFunction()) 75 OS << F->getName() << "\n"; 76 else { 77 OS << "<<null function: 0x" << getRoot() << ">>\n"; 78 } 79 80 CallGraph::print(OS, 0); 81 } 82 83 virtual void releaseMemory() { 84 destroy(); 85 } 86 87 /// getAdjustedAnalysisPointer - This method is used when a pass implements 88 /// an analysis interface through multiple inheritance. If needed, it should 89 /// override this to adjust the this pointer as needed for the specified pass 90 /// info. 91 virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { 92 if (PI == &CallGraph::ID) 93 return (CallGraph*)this; 94 return this; 95 } 96 97 CallGraphNode* getExternalCallingNode() const { return ExternalCallingNode; } 98 CallGraphNode* getCallsExternalNode() const { return CallsExternalNode; } 99 100 // getRoot - Return the root of the call graph, which is either main, or if 101 // main cannot be found, the external node. 102 // 103 CallGraphNode *getRoot() { return Root; } 104 const CallGraphNode *getRoot() const { return Root; } 105 106 private: 107 //===--------------------------------------------------------------------- 108 // Implementation of CallGraph construction 109 // 110 111 // addToCallGraph - Add a function to the call graph, and link the node to all 112 // of the functions that it calls. 113 // 114 void addToCallGraph(Function *F) { 115 CallGraphNode *Node = getOrInsertFunction(F); 116 117 // If this function has external linkage, anything could call it. 118 if (!F->hasLocalLinkage()) { 119 ExternalCallingNode->addCalledFunction(CallSite(), Node); 120 121 // Found the entry point? 122 if (F->getName() == "main") { 123 if (Root) // Found multiple external mains? Don't pick one. 124 Root = ExternalCallingNode; 125 else 126 Root = Node; // Found a main, keep track of it! 127 } 128 } 129 130 // If this function has its address taken, anything could call it. 131 if (F->hasAddressTaken()) 132 ExternalCallingNode->addCalledFunction(CallSite(), Node); 133 134 // If this function is not defined in this translation unit, it could call 135 // anything. 136 if (F->isDeclaration() && !F->isIntrinsic()) 137 Node->addCalledFunction(CallSite(), CallsExternalNode); 138 139 // Look for calls by this function. 140 for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) 141 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); 142 II != IE; ++II) { 143 CallSite CS(cast<Value>(II)); 144 if (CS && !isa<IntrinsicInst>(II)) { 145 const Function *Callee = CS.getCalledFunction(); 146 if (Callee) 147 Node->addCalledFunction(CS, getOrInsertFunction(Callee)); 148 else 149 Node->addCalledFunction(CS, CallsExternalNode); 150 } 151 } 152 } 153 154 // 155 // destroy - Release memory for the call graph 156 virtual void destroy() { 157 /// CallsExternalNode is not in the function map, delete it explicitly. 158 if (CallsExternalNode) { 159 CallsExternalNode->allReferencesDropped(); 160 delete CallsExternalNode; 161 CallsExternalNode = 0; 162 } 163 CallGraph::destroy(); 164 } 165 }; 166 167 } //End anonymous namespace 168 169 INITIALIZE_ANALYSIS_GROUP(CallGraph, "Call Graph", BasicCallGraph) 170 INITIALIZE_AG_PASS(BasicCallGraph, CallGraph, "basiccg", 171 "Basic CallGraph Construction", false, true, true) 172 173 char CallGraph::ID = 0; 174 char BasicCallGraph::ID = 0; 175 176 void CallGraph::initialize(Module &M) { 177 Mod = &M; 178 } 179 180 void CallGraph::destroy() { 181 if (FunctionMap.empty()) return; 182 183 // Reset all node's use counts to zero before deleting them to prevent an 184 // assertion from firing. 185 #ifndef NDEBUG 186 for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 187 I != E; ++I) 188 I->second->allReferencesDropped(); 189 #endif 190 191 for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 192 I != E; ++I) 193 delete I->second; 194 FunctionMap.clear(); 195 } 196 197 void CallGraph::print(raw_ostream &OS, Module*) const { 198 for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) 199 I->second->print(OS); 200 } 201 void CallGraph::dump() const { 202 print(dbgs(), 0); 203 } 204 205 //===----------------------------------------------------------------------===// 206 // Implementations of public modification methods 207 // 208 209 // removeFunctionFromModule - Unlink the function from this module, returning 210 // it. Because this removes the function from the module, the call graph node 211 // is destroyed. This is only valid if the function does not call any other 212 // functions (ie, there are no edges in it's CGN). The easiest way to do this 213 // is to dropAllReferences before calling this. 214 // 215 Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 216 assert(CGN->empty() && "Cannot remove function from call " 217 "graph if it references other functions!"); 218 Function *F = CGN->getFunction(); // Get the function for the call graph node 219 delete CGN; // Delete the call graph node for this func 220 FunctionMap.erase(F); // Remove the call graph node from the map 221 222 Mod->getFunctionList().remove(F); 223 return F; 224 } 225 226 /// spliceFunction - Replace the function represented by this node by another. 227 /// This does not rescan the body of the function, so it is suitable when 228 /// splicing the body of the old function to the new while also updating all 229 /// callers from old to new. 230 /// 231 void CallGraph::spliceFunction(const Function *From, const Function *To) { 232 assert(FunctionMap.count(From) && "No CallGraphNode for function!"); 233 assert(!FunctionMap.count(To) && 234 "Pointing CallGraphNode at a function that already exists"); 235 FunctionMapTy::iterator I = FunctionMap.find(From); 236 I->second->F = const_cast<Function*>(To); 237 FunctionMap[To] = I->second; 238 FunctionMap.erase(I); 239 } 240 241 // getOrInsertFunction - This method is identical to calling operator[], but 242 // it will insert a new CallGraphNode for the specified function if one does 243 // not already exist. 244 CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { 245 CallGraphNode *&CGN = FunctionMap[F]; 246 if (CGN) return CGN; 247 248 assert((!F || F->getParent() == Mod) && "Function not in current module!"); 249 return CGN = new CallGraphNode(const_cast<Function*>(F)); 250 } 251 252 void CallGraphNode::print(raw_ostream &OS) const { 253 if (Function *F = getFunction()) 254 OS << "Call graph node for function: '" << F->getName() << "'"; 255 else 256 OS << "Call graph node <<null function>>"; 257 258 OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n'; 259 260 for (const_iterator I = begin(), E = end(); I != E; ++I) { 261 OS << " CS<" << I->first << "> calls "; 262 if (Function *FI = I->second->getFunction()) 263 OS << "function '" << FI->getName() <<"'\n"; 264 else 265 OS << "external node\n"; 266 } 267 OS << '\n'; 268 } 269 270 void CallGraphNode::dump() const { print(dbgs()); } 271 272 /// removeCallEdgeFor - This method removes the edge in the node for the 273 /// specified call site. Note that this method takes linear time, so it 274 /// should be used sparingly. 275 void CallGraphNode::removeCallEdgeFor(CallSite CS) { 276 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 277 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 278 if (I->first == CS.getInstruction()) { 279 I->second->DropRef(); 280 *I = CalledFunctions.back(); 281 CalledFunctions.pop_back(); 282 return; 283 } 284 } 285 } 286 287 // removeAnyCallEdgeTo - This method removes any call edges from this node to 288 // the specified callee function. This takes more time to execute than 289 // removeCallEdgeTo, so it should not be used unless necessary. 290 void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 291 for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 292 if (CalledFunctions[i].second == Callee) { 293 Callee->DropRef(); 294 CalledFunctions[i] = CalledFunctions.back(); 295 CalledFunctions.pop_back(); 296 --i; --e; 297 } 298 } 299 300 /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite 301 /// from this node to the specified callee function. 302 void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) { 303 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 304 assert(I != CalledFunctions.end() && "Cannot find callee to remove!"); 305 CallRecord &CR = *I; 306 if (CR.second == Callee && CR.first == 0) { 307 Callee->DropRef(); 308 *I = CalledFunctions.back(); 309 CalledFunctions.pop_back(); 310 return; 311 } 312 } 313 } 314 315 /// replaceCallEdge - This method replaces the edge in the node for the 316 /// specified call site with a new one. Note that this method takes linear 317 /// time, so it should be used sparingly. 318 void CallGraphNode::replaceCallEdge(CallSite CS, 319 CallSite NewCS, CallGraphNode *NewNode){ 320 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 321 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 322 if (I->first == CS.getInstruction()) { 323 I->second->DropRef(); 324 I->first = NewCS.getInstruction(); 325 I->second = NewNode; 326 NewNode->AddRef(); 327 return; 328 } 329 } 330 } 331 332 // Enuse that users of CallGraph.h also link with this file 333 DEFINING_FILE_FOR(CallGraph) 334