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