1 //===- CallGraph.cpp - Build a Module's call graph ------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/Analysis/CallGraph.h" 10 #include "llvm/ADT/STLExtras.h" 11 #include "llvm/ADT/SmallVector.h" 12 #include "llvm/Config/llvm-config.h" 13 #include "llvm/IR/AbstractCallSite.h" 14 #include "llvm/IR/Function.h" 15 #include "llvm/IR/IntrinsicInst.h" 16 #include "llvm/IR/Intrinsics.h" 17 #include "llvm/IR/Module.h" 18 #include "llvm/IR/PassManager.h" 19 #include "llvm/InitializePasses.h" 20 #include "llvm/Pass.h" 21 #include "llvm/Support/Compiler.h" 22 #include "llvm/Support/Debug.h" 23 #include "llvm/Support/raw_ostream.h" 24 #include <algorithm> 25 #include <cassert> 26 27 using namespace llvm; 28 29 //===----------------------------------------------------------------------===// 30 // Implementations of the CallGraph class methods. 31 // 32 33 CallGraph::CallGraph(Module &M) 34 : M(M), ExternalCallingNode(getOrInsertFunction(nullptr)), 35 CallsExternalNode(std::make_unique<CallGraphNode>(this, nullptr)) { 36 // Add every interesting function to the call graph. 37 for (Function &F : M) 38 if (!isDbgInfoIntrinsic(F.getIntrinsicID())) 39 addToCallGraph(&F); 40 } 41 42 CallGraph::CallGraph(CallGraph &&Arg) 43 : M(Arg.M), FunctionMap(std::move(Arg.FunctionMap)), 44 ExternalCallingNode(Arg.ExternalCallingNode), 45 CallsExternalNode(std::move(Arg.CallsExternalNode)) { 46 Arg.FunctionMap.clear(); 47 Arg.ExternalCallingNode = nullptr; 48 49 // Update parent CG for all call graph's nodes. 50 CallsExternalNode->CG = this; 51 for (auto &P : FunctionMap) 52 P.second->CG = this; 53 } 54 55 CallGraph::~CallGraph() { 56 // CallsExternalNode is not in the function map, delete it explicitly. 57 if (CallsExternalNode) 58 CallsExternalNode->allReferencesDropped(); 59 60 // Reset all node's use counts to zero before deleting them to prevent an 61 // assertion from firing. 62 #ifndef NDEBUG 63 for (auto &I : FunctionMap) 64 I.second->allReferencesDropped(); 65 #endif 66 } 67 68 bool CallGraph::invalidate(Module &, const PreservedAnalyses &PA, 69 ModuleAnalysisManager::Invalidator &) { 70 // Check whether the analysis, all analyses on functions, or the function's 71 // CFG have been preserved. 72 auto PAC = PA.getChecker<CallGraphAnalysis>(); 73 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>() || 74 PAC.preservedSet<CFGAnalyses>()); 75 } 76 77 void CallGraph::addToCallGraph(Function *F) { 78 CallGraphNode *Node = getOrInsertFunction(F); 79 80 // If this function has external linkage or has its address taken and 81 // it is not a callback, then anything could call it. 82 if (!F->hasLocalLinkage() || 83 F->hasAddressTaken(nullptr, /*IgnoreCallbackUses=*/true)) 84 ExternalCallingNode->addCalledFunction(nullptr, Node); 85 86 populateCallGraphNode(Node); 87 } 88 89 void CallGraph::populateCallGraphNode(CallGraphNode *Node) { 90 Function *F = Node->getFunction(); 91 92 // If this function is not defined in this translation unit, it could call 93 // anything. 94 if (F->isDeclaration() && !F->isIntrinsic()) 95 Node->addCalledFunction(nullptr, CallsExternalNode.get()); 96 97 // Look for calls by this function. 98 for (BasicBlock &BB : *F) 99 for (Instruction &I : BB) { 100 if (auto *Call = dyn_cast<CallBase>(&I)) { 101 const Function *Callee = Call->getCalledFunction(); 102 if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID())) 103 // Indirect calls of intrinsics are not allowed so no need to check. 104 // We can be more precise here by using TargetArg returned by 105 // Intrinsic::isLeaf. 106 Node->addCalledFunction(Call, CallsExternalNode.get()); 107 else if (!Callee->isIntrinsic()) 108 Node->addCalledFunction(Call, getOrInsertFunction(Callee)); 109 110 // Add reference to callback functions. 111 forEachCallbackFunction(*Call, [=](Function *CB) { 112 Node->addCalledFunction(nullptr, getOrInsertFunction(CB)); 113 }); 114 } 115 } 116 } 117 118 void CallGraph::print(raw_ostream &OS) const { 119 // Print in a deterministic order by sorting CallGraphNodes by name. We do 120 // this here to avoid slowing down the non-printing fast path. 121 122 SmallVector<CallGraphNode *, 16> Nodes; 123 Nodes.reserve(FunctionMap.size()); 124 125 for (const auto &I : *this) 126 Nodes.push_back(I.second.get()); 127 128 llvm::sort(Nodes, [](CallGraphNode *LHS, CallGraphNode *RHS) { 129 if (Function *LF = LHS->getFunction()) 130 if (Function *RF = RHS->getFunction()) 131 return LF->getName() < RF->getName(); 132 133 return RHS->getFunction() != nullptr; 134 }); 135 136 for (CallGraphNode *CN : Nodes) 137 CN->print(OS); 138 } 139 140 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 141 LLVM_DUMP_METHOD void CallGraph::dump() const { print(dbgs()); } 142 #endif 143 144 void CallGraph::ReplaceExternalCallEdge(CallGraphNode *Old, 145 CallGraphNode *New) { 146 for (auto &CR : ExternalCallingNode->CalledFunctions) 147 if (CR.second == Old) { 148 CR.second->DropRef(); 149 CR.second = New; 150 CR.second->AddRef(); 151 } 152 } 153 154 // removeFunctionFromModule - Unlink the function from this module, returning 155 // it. Because this removes the function from the module, the call graph node 156 // is destroyed. This is only valid if the function does not call any other 157 // functions (ie, there are no edges in it's CGN). The easiest way to do this 158 // is to dropAllReferences before calling this. 159 // 160 Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 161 assert(CGN->empty() && "Cannot remove function from call " 162 "graph if it references other functions!"); 163 Function *F = CGN->getFunction(); // Get the function for the call graph node 164 FunctionMap.erase(F); // Remove the call graph node from the map 165 166 M.getFunctionList().remove(F); 167 return F; 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 auto &CGN = FunctionMap[F]; 175 if (CGN) 176 return CGN.get(); 177 178 assert((!F || F->getParent() == &M) && "Function not in current module!"); 179 CGN = std::make_unique<CallGraphNode>(this, const_cast<Function *>(F)); 180 return CGN.get(); 181 } 182 183 //===----------------------------------------------------------------------===// 184 // Implementations of the CallGraphNode class methods. 185 // 186 187 void CallGraphNode::print(raw_ostream &OS) const { 188 if (Function *F = getFunction()) 189 OS << "Call graph node for function: '" << F->getName() << "'"; 190 else 191 OS << "Call graph node <<null function>>"; 192 193 OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n'; 194 195 for (const auto &I : *this) { 196 OS << " CS<" << I.first << "> calls "; 197 if (Function *FI = I.second->getFunction()) 198 OS << "function '" << FI->getName() <<"'\n"; 199 else 200 OS << "external node\n"; 201 } 202 OS << '\n'; 203 } 204 205 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 206 LLVM_DUMP_METHOD void CallGraphNode::dump() const { print(dbgs()); } 207 #endif 208 209 /// removeCallEdgeFor - This method removes the edge in the node for the 210 /// specified call site. Note that this method takes linear time, so it 211 /// should be used sparingly. 212 void CallGraphNode::removeCallEdgeFor(CallBase &Call) { 213 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 214 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 215 if (I->first && *I->first == &Call) { 216 I->second->DropRef(); 217 *I = CalledFunctions.back(); 218 CalledFunctions.pop_back(); 219 220 // Remove all references to callback functions if there are any. 221 forEachCallbackFunction(Call, [=](Function *CB) { 222 removeOneAbstractEdgeTo(CG->getOrInsertFunction(CB)); 223 }); 224 return; 225 } 226 } 227 } 228 229 // removeAnyCallEdgeTo - This method removes any call edges from this node to 230 // the specified callee function. This takes more time to execute than 231 // removeCallEdgeTo, so it should not be used unless necessary. 232 void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 233 for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 234 if (CalledFunctions[i].second == Callee) { 235 Callee->DropRef(); 236 CalledFunctions[i] = CalledFunctions.back(); 237 CalledFunctions.pop_back(); 238 --i; --e; 239 } 240 } 241 242 /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite 243 /// from this node to the specified callee function. 244 void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) { 245 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 246 assert(I != CalledFunctions.end() && "Cannot find callee to remove!"); 247 CallRecord &CR = *I; 248 if (CR.second == Callee && !CR.first) { 249 Callee->DropRef(); 250 *I = CalledFunctions.back(); 251 CalledFunctions.pop_back(); 252 return; 253 } 254 } 255 } 256 257 /// replaceCallEdge - This method replaces the edge in the node for the 258 /// specified call site with a new one. Note that this method takes linear 259 /// time, so it should be used sparingly. 260 void CallGraphNode::replaceCallEdge(CallBase &Call, CallBase &NewCall, 261 CallGraphNode *NewNode) { 262 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 263 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 264 if (I->first && *I->first == &Call) { 265 I->second->DropRef(); 266 I->first = &NewCall; 267 I->second = NewNode; 268 NewNode->AddRef(); 269 270 // Refresh callback references. Do not resize CalledFunctions if the 271 // number of callbacks is the same for new and old call sites. 272 SmallVector<CallGraphNode *, 4u> OldCBs; 273 SmallVector<CallGraphNode *, 4u> NewCBs; 274 forEachCallbackFunction(Call, [this, &OldCBs](Function *CB) { 275 OldCBs.push_back(CG->getOrInsertFunction(CB)); 276 }); 277 forEachCallbackFunction(NewCall, [this, &NewCBs](Function *CB) { 278 NewCBs.push_back(CG->getOrInsertFunction(CB)); 279 }); 280 if (OldCBs.size() == NewCBs.size()) { 281 for (unsigned N = 0; N < OldCBs.size(); ++N) { 282 CallGraphNode *OldNode = OldCBs[N]; 283 CallGraphNode *NewNode = NewCBs[N]; 284 for (auto J = CalledFunctions.begin();; ++J) { 285 assert(J != CalledFunctions.end() && 286 "Cannot find callsite to update!"); 287 if (!J->first && J->second == OldNode) { 288 J->second = NewNode; 289 OldNode->DropRef(); 290 NewNode->AddRef(); 291 break; 292 } 293 } 294 } 295 } else { 296 for (auto *CGN : OldCBs) 297 removeOneAbstractEdgeTo(CGN); 298 for (auto *CGN : NewCBs) 299 addCalledFunction(nullptr, CGN); 300 } 301 return; 302 } 303 } 304 } 305 306 // Provide an explicit template instantiation for the static ID. 307 AnalysisKey CallGraphAnalysis::Key; 308 309 PreservedAnalyses CallGraphPrinterPass::run(Module &M, 310 ModuleAnalysisManager &AM) { 311 AM.getResult<CallGraphAnalysis>(M).print(OS); 312 return PreservedAnalyses::all(); 313 } 314 315 //===----------------------------------------------------------------------===// 316 // Out-of-line definitions of CallGraphAnalysis class members. 317 // 318 319 //===----------------------------------------------------------------------===// 320 // Implementations of the CallGraphWrapperPass class methods. 321 // 322 323 CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) { 324 initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry()); 325 } 326 327 CallGraphWrapperPass::~CallGraphWrapperPass() = default; 328 329 void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 330 AU.setPreservesAll(); 331 } 332 333 bool CallGraphWrapperPass::runOnModule(Module &M) { 334 // All the real work is done in the constructor for the CallGraph. 335 G.reset(new CallGraph(M)); 336 return false; 337 } 338 339 INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction", 340 false, true) 341 342 char CallGraphWrapperPass::ID = 0; 343 344 void CallGraphWrapperPass::releaseMemory() { G.reset(); } 345 346 void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const { 347 if (!G) { 348 OS << "No call graph has been built!\n"; 349 return; 350 } 351 352 // Just delegate. 353 G->print(OS); 354 } 355 356 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 357 LLVM_DUMP_METHOD 358 void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); } 359 #endif 360 361 namespace { 362 363 struct CallGraphPrinterLegacyPass : public ModulePass { 364 static char ID; // Pass ID, replacement for typeid 365 366 CallGraphPrinterLegacyPass() : ModulePass(ID) { 367 initializeCallGraphPrinterLegacyPassPass(*PassRegistry::getPassRegistry()); 368 } 369 370 void getAnalysisUsage(AnalysisUsage &AU) const override { 371 AU.setPreservesAll(); 372 AU.addRequiredTransitive<CallGraphWrapperPass>(); 373 } 374 375 bool runOnModule(Module &M) override { 376 getAnalysis<CallGraphWrapperPass>().print(errs(), &M); 377 return false; 378 } 379 }; 380 381 } // end anonymous namespace 382 383 char CallGraphPrinterLegacyPass::ID = 0; 384 385 INITIALIZE_PASS_BEGIN(CallGraphPrinterLegacyPass, "print-callgraph", 386 "Print a call graph", true, true) 387 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) 388 INITIALIZE_PASS_END(CallGraphPrinterLegacyPass, "print-callgraph", 389 "Print a call graph", true, true) 390