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 27using namespace llvm; 28 29//===----------------------------------------------------------------------===// 30// Implementations of the CallGraph class methods. 31// 32 33CallGraph::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 42CallGraph::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 55CallGraph::~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 68bool 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 77void 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 89void 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 118void 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) 141LLVM_DUMP_METHOD void CallGraph::dump() const { print(dbgs()); } 142#endif 143 144void 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// 160Function *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/// spliceFunction - Replace the function represented by this node by another. 171/// This does not rescan the body of the function, so it is suitable when 172/// splicing the body of the old function to the new while also updating all 173/// callers from old to new. 174void CallGraph::spliceFunction(const Function *From, const Function *To) { 175 assert(FunctionMap.count(From) && "No CallGraphNode for function!"); 176 assert(!FunctionMap.count(To) && 177 "Pointing CallGraphNode at a function that already exists"); 178 FunctionMapTy::iterator I = FunctionMap.find(From); 179 I->second->F = const_cast<Function*>(To); 180 FunctionMap[To] = std::move(I->second); 181 FunctionMap.erase(I); 182} 183 184// getOrInsertFunction - This method is identical to calling operator[], but 185// it will insert a new CallGraphNode for the specified function if one does 186// not already exist. 187CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { 188 auto &CGN = FunctionMap[F]; 189 if (CGN) 190 return CGN.get(); 191 192 assert((!F || F->getParent() == &M) && "Function not in current module!"); 193 CGN = std::make_unique<CallGraphNode>(this, const_cast<Function *>(F)); 194 return CGN.get(); 195} 196 197//===----------------------------------------------------------------------===// 198// Implementations of the CallGraphNode class methods. 199// 200 201void CallGraphNode::print(raw_ostream &OS) const { 202 if (Function *F = getFunction()) 203 OS << "Call graph node for function: '" << F->getName() << "'"; 204 else 205 OS << "Call graph node <<null function>>"; 206 207 OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n'; 208 209 for (const auto &I : *this) { 210 OS << " CS<" << I.first << "> calls "; 211 if (Function *FI = I.second->getFunction()) 212 OS << "function '" << FI->getName() <<"'\n"; 213 else 214 OS << "external node\n"; 215 } 216 OS << '\n'; 217} 218 219#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 220LLVM_DUMP_METHOD void CallGraphNode::dump() const { print(dbgs()); } 221#endif 222 223/// removeCallEdgeFor - This method removes the edge in the node for the 224/// specified call site. Note that this method takes linear time, so it 225/// should be used sparingly. 226void CallGraphNode::removeCallEdgeFor(CallBase &Call) { 227 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 228 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 229 if (I->first && *I->first == &Call) { 230 I->second->DropRef(); 231 *I = CalledFunctions.back(); 232 CalledFunctions.pop_back(); 233 234 // Remove all references to callback functions if there are any. 235 forEachCallbackFunction(Call, [=](Function *CB) { 236 removeOneAbstractEdgeTo(CG->getOrInsertFunction(CB)); 237 }); 238 return; 239 } 240 } 241} 242 243// removeAnyCallEdgeTo - This method removes any call edges from this node to 244// the specified callee function. This takes more time to execute than 245// removeCallEdgeTo, so it should not be used unless necessary. 246void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 247 for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 248 if (CalledFunctions[i].second == Callee) { 249 Callee->DropRef(); 250 CalledFunctions[i] = CalledFunctions.back(); 251 CalledFunctions.pop_back(); 252 --i; --e; 253 } 254} 255 256/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite 257/// from this node to the specified callee function. 258void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) { 259 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 260 assert(I != CalledFunctions.end() && "Cannot find callee to remove!"); 261 CallRecord &CR = *I; 262 if (CR.second == Callee && !CR.first) { 263 Callee->DropRef(); 264 *I = CalledFunctions.back(); 265 CalledFunctions.pop_back(); 266 return; 267 } 268 } 269} 270 271/// replaceCallEdge - This method replaces the edge in the node for the 272/// specified call site with a new one. Note that this method takes linear 273/// time, so it should be used sparingly. 274void CallGraphNode::replaceCallEdge(CallBase &Call, CallBase &NewCall, 275 CallGraphNode *NewNode) { 276 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 277 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 278 if (I->first && *I->first == &Call) { 279 I->second->DropRef(); 280 I->first = &NewCall; 281 I->second = NewNode; 282 NewNode->AddRef(); 283 284 // Refresh callback references. 285 forEachCallbackFunction(Call, [=](Function *CB) { 286 removeOneAbstractEdgeTo(CG->getOrInsertFunction(CB)); 287 }); 288 forEachCallbackFunction(NewCall, [=](Function *CB) { 289 addCalledFunction(nullptr, CG->getOrInsertFunction(CB)); 290 }); 291 return; 292 } 293 } 294} 295 296// Provide an explicit template instantiation for the static ID. 297AnalysisKey CallGraphAnalysis::Key; 298 299PreservedAnalyses CallGraphPrinterPass::run(Module &M, 300 ModuleAnalysisManager &AM) { 301 AM.getResult<CallGraphAnalysis>(M).print(OS); 302 return PreservedAnalyses::all(); 303} 304 305//===----------------------------------------------------------------------===// 306// Out-of-line definitions of CallGraphAnalysis class members. 307// 308 309//===----------------------------------------------------------------------===// 310// Implementations of the CallGraphWrapperPass class methods. 311// 312 313CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) { 314 initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry()); 315} 316 317CallGraphWrapperPass::~CallGraphWrapperPass() = default; 318 319void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 320 AU.setPreservesAll(); 321} 322 323bool CallGraphWrapperPass::runOnModule(Module &M) { 324 // All the real work is done in the constructor for the CallGraph. 325 G.reset(new CallGraph(M)); 326 return false; 327} 328 329INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction", 330 false, true) 331 332char CallGraphWrapperPass::ID = 0; 333 334void CallGraphWrapperPass::releaseMemory() { G.reset(); } 335 336void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const { 337 if (!G) { 338 OS << "No call graph has been built!\n"; 339 return; 340 } 341 342 // Just delegate. 343 G->print(OS); 344} 345 346#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 347LLVM_DUMP_METHOD 348void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); } 349#endif 350 351namespace { 352 353struct CallGraphPrinterLegacyPass : public ModulePass { 354 static char ID; // Pass ID, replacement for typeid 355 356 CallGraphPrinterLegacyPass() : ModulePass(ID) { 357 initializeCallGraphPrinterLegacyPassPass(*PassRegistry::getPassRegistry()); 358 } 359 360 void getAnalysisUsage(AnalysisUsage &AU) const override { 361 AU.setPreservesAll(); 362 AU.addRequiredTransitive<CallGraphWrapperPass>(); 363 } 364 365 bool runOnModule(Module &M) override { 366 getAnalysis<CallGraphWrapperPass>().print(errs(), &M); 367 return false; 368 } 369}; 370 371} // end anonymous namespace 372 373char CallGraphPrinterLegacyPass::ID = 0; 374 375INITIALIZE_PASS_BEGIN(CallGraphPrinterLegacyPass, "print-callgraph", 376 "Print a call graph", true, true) 377INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) 378INITIALIZE_PASS_END(CallGraphPrinterLegacyPass, "print-callgraph", 379 "Print a call graph", true, true) 380