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#include "llvm/Analysis/CallGraph.h" 11#include "llvm/IR/Instructions.h" 12#include "llvm/IR/IntrinsicInst.h" 13#include "llvm/IR/Module.h" 14#include "llvm/Support/CallSite.h" 15#include "llvm/Support/Debug.h" 16#include "llvm/Support/raw_ostream.h" 17using namespace llvm; 18 19CallGraph::CallGraph() 20 : ModulePass(ID), Root(0), ExternalCallingNode(0), CallsExternalNode(0) { 21 initializeCallGraphPass(*PassRegistry::getPassRegistry()); 22} 23 24void CallGraph::addToCallGraph(Function *F) { 25 CallGraphNode *Node = getOrInsertFunction(F); 26 27 // If this function has external linkage, anything could call it. 28 if (!F->hasLocalLinkage()) { 29 ExternalCallingNode->addCalledFunction(CallSite(), Node); 30 31 // Found the entry point? 32 if (F->getName() == "main") { 33 if (Root) // Found multiple external mains? Don't pick one. 34 Root = ExternalCallingNode; 35 else 36 Root = Node; // Found a main, keep track of it! 37 } 38 } 39 40 // If this function has its address taken, anything could call it. 41 if (F->hasAddressTaken()) 42 ExternalCallingNode->addCalledFunction(CallSite(), Node); 43 44 // If this function is not defined in this translation unit, it could call 45 // anything. 46 if (F->isDeclaration() && !F->isIntrinsic()) 47 Node->addCalledFunction(CallSite(), CallsExternalNode); 48 49 // Look for calls by this function. 50 for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) 51 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; 52 ++II) { 53 CallSite CS(cast<Value>(II)); 54 if (CS) { 55 const Function *Callee = CS.getCalledFunction(); 56 if (!Callee) 57 // Indirect calls of intrinsics are not allowed so no need to check. 58 Node->addCalledFunction(CS, CallsExternalNode); 59 else if (!Callee->isIntrinsic()) 60 Node->addCalledFunction(CS, getOrInsertFunction(Callee)); 61 } 62 } 63} 64 65void CallGraph::getAnalysisUsage(AnalysisUsage &AU) const { 66 AU.setPreservesAll(); 67} 68 69bool CallGraph::runOnModule(Module &M) { 70 Mod = &M; 71 72 ExternalCallingNode = getOrInsertFunction(0); 73 assert(!CallsExternalNode); 74 CallsExternalNode = new CallGraphNode(0); 75 Root = 0; 76 77 // Add every function to the call graph. 78 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 79 addToCallGraph(I); 80 81 // If we didn't find a main function, use the external call graph node 82 if (Root == 0) 83 Root = ExternalCallingNode; 84 85 return false; 86} 87 88INITIALIZE_PASS(CallGraph, "basiccg", "CallGraph Construction", false, true) 89 90char CallGraph::ID = 0; 91 92void CallGraph::releaseMemory() { 93 /// CallsExternalNode is not in the function map, delete it explicitly. 94 if (CallsExternalNode) { 95 CallsExternalNode->allReferencesDropped(); 96 delete CallsExternalNode; 97 CallsExternalNode = 0; 98 } 99 100 if (FunctionMap.empty()) 101 return; 102 103// Reset all node's use counts to zero before deleting them to prevent an 104// assertion from firing. 105#ifndef NDEBUG 106 for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 107 I != E; ++I) 108 I->second->allReferencesDropped(); 109#endif 110 111 for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 112 I != E; ++I) 113 delete I->second; 114 FunctionMap.clear(); 115} 116 117void CallGraph::print(raw_ostream &OS, const Module*) const { 118 OS << "CallGraph Root is: "; 119 if (Function *F = Root->getFunction()) 120 OS << F->getName() << "\n"; 121 else { 122 OS << "<<null function: 0x" << Root << ">>\n"; 123 } 124 125 for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) 126 I->second->print(OS); 127} 128#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 129void CallGraph::dump() const { 130 print(dbgs(), 0); 131} 132#endif 133 134//===----------------------------------------------------------------------===// 135// Implementations of public modification methods 136// 137 138// removeFunctionFromModule - Unlink the function from this module, returning 139// it. Because this removes the function from the module, the call graph node 140// is destroyed. This is only valid if the function does not call any other 141// functions (ie, there are no edges in it's CGN). The easiest way to do this 142// is to dropAllReferences before calling this. 143// 144Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 145 assert(CGN->empty() && "Cannot remove function from call " 146 "graph if it references other functions!"); 147 Function *F = CGN->getFunction(); // Get the function for the call graph node 148 delete CGN; // Delete the call graph node for this func 149 FunctionMap.erase(F); // Remove the call graph node from the map 150 151 Mod->getFunctionList().remove(F); 152 return F; 153} 154 155/// spliceFunction - Replace the function represented by this node by another. 156/// This does not rescan the body of the function, so it is suitable when 157/// splicing the body of the old function to the new while also updating all 158/// callers from old to new. 159/// 160void CallGraph::spliceFunction(const Function *From, const Function *To) { 161 assert(FunctionMap.count(From) && "No CallGraphNode for function!"); 162 assert(!FunctionMap.count(To) && 163 "Pointing CallGraphNode at a function that already exists"); 164 FunctionMapTy::iterator I = FunctionMap.find(From); 165 I->second->F = const_cast<Function*>(To); 166 FunctionMap[To] = I->second; 167 FunctionMap.erase(I); 168} 169 170// getOrInsertFunction - This method is identical to calling operator[], but 171// it will insert a new CallGraphNode for the specified function if one does 172// not already exist. 173CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { 174 CallGraphNode *&CGN = FunctionMap[F]; 175 if (CGN) return CGN; 176 177 assert((!F || F->getParent() == Mod) && "Function not in current module!"); 178 return CGN = new CallGraphNode(const_cast<Function*>(F)); 179} 180 181void CallGraphNode::print(raw_ostream &OS) const { 182 if (Function *F = getFunction()) 183 OS << "Call graph node for function: '" << F->getName() << "'"; 184 else 185 OS << "Call graph node <<null function>>"; 186 187 OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n'; 188 189 for (const_iterator I = begin(), E = end(); I != E; ++I) { 190 OS << " CS<" << I->first << "> calls "; 191 if (Function *FI = I->second->getFunction()) 192 OS << "function '" << FI->getName() <<"'\n"; 193 else 194 OS << "external node\n"; 195 } 196 OS << '\n'; 197} 198 199#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 200void CallGraphNode::dump() const { print(dbgs()); } 201#endif 202 203/// removeCallEdgeFor - This method removes the edge in the node for the 204/// specified call site. Note that this method takes linear time, so it 205/// should be used sparingly. 206void CallGraphNode::removeCallEdgeFor(CallSite CS) { 207 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 208 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 209 if (I->first == CS.getInstruction()) { 210 I->second->DropRef(); 211 *I = CalledFunctions.back(); 212 CalledFunctions.pop_back(); 213 return; 214 } 215 } 216} 217 218// removeAnyCallEdgeTo - This method removes any call edges from this node to 219// the specified callee function. This takes more time to execute than 220// removeCallEdgeTo, so it should not be used unless necessary. 221void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 222 for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 223 if (CalledFunctions[i].second == Callee) { 224 Callee->DropRef(); 225 CalledFunctions[i] = CalledFunctions.back(); 226 CalledFunctions.pop_back(); 227 --i; --e; 228 } 229} 230 231/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite 232/// from this node to the specified callee function. 233void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) { 234 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 235 assert(I != CalledFunctions.end() && "Cannot find callee to remove!"); 236 CallRecord &CR = *I; 237 if (CR.second == Callee && CR.first == 0) { 238 Callee->DropRef(); 239 *I = CalledFunctions.back(); 240 CalledFunctions.pop_back(); 241 return; 242 } 243 } 244} 245 246/// replaceCallEdge - This method replaces the edge in the node for the 247/// specified call site with a new one. Note that this method takes linear 248/// time, so it should be used sparingly. 249void CallGraphNode::replaceCallEdge(CallSite CS, 250 CallSite NewCS, CallGraphNode *NewNode){ 251 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 252 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 253 if (I->first == CS.getInstruction()) { 254 I->second->DropRef(); 255 I->first = NewCS.getInstruction(); 256 I->second = NewNode; 257 NewNode->AddRef(); 258 return; 259 } 260 } 261} 262 263// Enuse that users of CallGraph.h also link with this file 264DEFINING_FILE_FOR(CallGraph) 265