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" 17 using namespace llvm; 18 19 CallGraph::CallGraph() 20 : ModulePass(ID), Root(0), ExternalCallingNode(0), CallsExternalNode(0) { 21 initializeCallGraphPass(*PassRegistry::getPassRegistry()); 22 } 23 24 void 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 65 void CallGraph::getAnalysisUsage(AnalysisUsage &AU) const { 66 AU.setPreservesAll(); 67 } 68 69 bool 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 88 INITIALIZE_PASS(CallGraph, "basiccg", "CallGraph Construction", false, true) 89 90 char CallGraph::ID = 0; 91 92 void 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 117 void 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) 129 void 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 // 144 Function *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 /// 160 void 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. 173 CallGraphNode *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 181 void 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) 200 void 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. 206 void 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. 221 void 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. 233 void 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. 249 void 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 264 DEFINING_FILE_FOR(CallGraph) 265