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/SCCIterator.h" 11 #include "llvm/ADT/STLExtras.h" 12 #include "llvm/ADT/SmallVector.h" 13 #include "llvm/Config/llvm-config.h" 14 #include "llvm/IR/AbstractCallSite.h" 15 #include "llvm/IR/Function.h" 16 #include "llvm/IR/Module.h" 17 #include "llvm/IR/PassManager.h" 18 #include "llvm/InitializePasses.h" 19 #include "llvm/Pass.h" 20 #include "llvm/Support/Compiler.h" 21 #include "llvm/Support/Debug.h" 22 #include "llvm/Support/raw_ostream.h" 23 #include <cassert> 24 25 using namespace llvm; 26 27 //===----------------------------------------------------------------------===// 28 // Implementations of the CallGraph class methods. 29 // 30 31 CallGraph::CallGraph(Module &M) 32 : M(M), ExternalCallingNode(getOrInsertFunction(nullptr)), 33 CallsExternalNode(std::make_unique<CallGraphNode>(this, nullptr)) { 34 // Add every interesting function to the call graph. 35 for (Function &F : M) 36 addToCallGraph(&F); 37 } 38 39 CallGraph::CallGraph(CallGraph &&Arg) 40 : M(Arg.M), FunctionMap(std::move(Arg.FunctionMap)), 41 ExternalCallingNode(Arg.ExternalCallingNode), 42 CallsExternalNode(std::move(Arg.CallsExternalNode)) { 43 Arg.FunctionMap.clear(); 44 Arg.ExternalCallingNode = nullptr; 45 46 // Update parent CG for all call graph's nodes. 47 CallsExternalNode->CG = this; 48 for (auto &P : FunctionMap) 49 P.second->CG = this; 50 } 51 52 CallGraph::~CallGraph() { 53 // CallsExternalNode is not in the function map, delete it explicitly. 54 if (CallsExternalNode) 55 CallsExternalNode->allReferencesDropped(); 56 57 // Reset all node's use counts to zero before deleting them to prevent an 58 // assertion from firing. 59 #ifndef NDEBUG 60 for (auto &I : FunctionMap) 61 I.second->allReferencesDropped(); 62 #endif 63 } 64 65 bool CallGraph::invalidate(Module &, const PreservedAnalyses &PA, 66 ModuleAnalysisManager::Invalidator &) { 67 // Check whether the analysis, all analyses on functions, or the function's 68 // CFG have been preserved. 69 auto PAC = PA.getChecker<CallGraphAnalysis>(); 70 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>()); 71 } 72 73 void CallGraph::addToCallGraph(Function *F) { 74 CallGraphNode *Node = getOrInsertFunction(F); 75 76 // If this function has external linkage or has its address taken and 77 // it is not a callback, then anything could call it. 78 if (!F->hasLocalLinkage() || 79 F->hasAddressTaken(nullptr, /*IgnoreCallbackUses=*/true, 80 /* IgnoreAssumeLikeCalls */ true, 81 /* IgnoreLLVMUsed */ false)) 82 ExternalCallingNode->addCalledFunction(nullptr, Node); 83 84 populateCallGraphNode(Node); 85 } 86 87 void CallGraph::populateCallGraphNode(CallGraphNode *Node) { 88 Function *F = Node->getFunction(); 89 90 // If this function is not defined in this translation unit, it could call 91 // anything. 92 if (F->isDeclaration() && !F->hasFnAttribute(Attribute::NoCallback)) 93 Node->addCalledFunction(nullptr, CallsExternalNode.get()); 94 95 // Look for calls by this function. 96 for (BasicBlock &BB : *F) 97 for (Instruction &I : BB) { 98 if (auto *Call = dyn_cast<CallBase>(&I)) { 99 const Function *Callee = Call->getCalledFunction(); 100 if (!Callee) 101 Node->addCalledFunction(Call, CallsExternalNode.get()); 102 else 103 Node->addCalledFunction(Call, getOrInsertFunction(Callee)); 104 105 // Add reference to callback functions. 106 forEachCallbackFunction(*Call, [=](Function *CB) { 107 Node->addCalledFunction(nullptr, getOrInsertFunction(CB)); 108 }); 109 } 110 } 111 } 112 113 void CallGraph::print(raw_ostream &OS) const { 114 // Print in a deterministic order by sorting CallGraphNodes by name. We do 115 // this here to avoid slowing down the non-printing fast path. 116 117 SmallVector<CallGraphNode *, 16> Nodes; 118 Nodes.reserve(FunctionMap.size()); 119 120 for (const auto &I : *this) 121 Nodes.push_back(I.second.get()); 122 123 llvm::sort(Nodes, [](CallGraphNode *LHS, CallGraphNode *RHS) { 124 if (Function *LF = LHS->getFunction()) 125 if (Function *RF = RHS->getFunction()) 126 return LF->getName() < RF->getName(); 127 128 return RHS->getFunction() != nullptr; 129 }); 130 131 for (CallGraphNode *CN : Nodes) 132 CN->print(OS); 133 } 134 135 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 136 LLVM_DUMP_METHOD void CallGraph::dump() const { print(dbgs()); } 137 #endif 138 139 // removeFunctionFromModule - Unlink the function from this module, returning 140 // it. Because this removes the function from the module, the call graph node 141 // is destroyed. This is only valid if the function does not call any other 142 // functions (ie, there are no edges in it's CGN). The easiest way to do this 143 // is to dropAllReferences before calling this. 144 // 145 Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 146 assert(CGN->empty() && "Cannot remove function from call " 147 "graph if it references other functions!"); 148 Function *F = CGN->getFunction(); // Get the function for the call graph node 149 FunctionMap.erase(F); // Remove the call graph node from the map 150 151 M.getFunctionList().remove(F); 152 return F; 153 } 154 155 // getOrInsertFunction - This method is identical to calling operator[], but 156 // it will insert a new CallGraphNode for the specified function if one does 157 // not already exist. 158 CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { 159 auto &CGN = FunctionMap[F]; 160 if (CGN) 161 return CGN.get(); 162 163 assert((!F || F->getParent() == &M) && "Function not in current module!"); 164 CGN = std::make_unique<CallGraphNode>(this, const_cast<Function *>(F)); 165 return CGN.get(); 166 } 167 168 //===----------------------------------------------------------------------===// 169 // Implementations of the CallGraphNode class methods. 170 // 171 172 void CallGraphNode::print(raw_ostream &OS) const { 173 if (Function *F = getFunction()) 174 OS << "Call graph node for function: '" << F->getName() << "'"; 175 else 176 OS << "Call graph node <<null function>>"; 177 178 OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n'; 179 180 for (const auto &I : *this) { 181 OS << " CS<" << I.first << "> calls "; 182 if (Function *FI = I.second->getFunction()) 183 OS << "function '" << FI->getName() <<"'\n"; 184 else 185 OS << "external node\n"; 186 } 187 OS << '\n'; 188 } 189 190 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 191 LLVM_DUMP_METHOD void CallGraphNode::dump() const { print(dbgs()); } 192 #endif 193 194 /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite 195 /// from this node to the specified callee function. 196 void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) { 197 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 198 assert(I != CalledFunctions.end() && "Cannot find callee to remove!"); 199 CallRecord &CR = *I; 200 if (CR.second == Callee && !CR.first) { 201 Callee->DropRef(); 202 *I = CalledFunctions.back(); 203 CalledFunctions.pop_back(); 204 return; 205 } 206 } 207 } 208 209 /// replaceCallEdge - This method replaces the edge in the node for the 210 /// specified call site with a new one. Note that this method takes linear 211 /// time, so it should be used sparingly. 212 void CallGraphNode::replaceCallEdge(CallBase &Call, CallBase &NewCall, 213 CallGraphNode *NewNode) { 214 for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 215 assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 216 if (I->first && *I->first == &Call) { 217 I->second->DropRef(); 218 I->first = &NewCall; 219 I->second = NewNode; 220 NewNode->AddRef(); 221 222 // Refresh callback references. Do not resize CalledFunctions if the 223 // number of callbacks is the same for new and old call sites. 224 SmallVector<CallGraphNode *, 4u> OldCBs; 225 SmallVector<CallGraphNode *, 4u> NewCBs; 226 forEachCallbackFunction(Call, [this, &OldCBs](Function *CB) { 227 OldCBs.push_back(CG->getOrInsertFunction(CB)); 228 }); 229 forEachCallbackFunction(NewCall, [this, &NewCBs](Function *CB) { 230 NewCBs.push_back(CG->getOrInsertFunction(CB)); 231 }); 232 if (OldCBs.size() == NewCBs.size()) { 233 for (unsigned N = 0; N < OldCBs.size(); ++N) { 234 CallGraphNode *OldNode = OldCBs[N]; 235 CallGraphNode *NewNode = NewCBs[N]; 236 for (auto J = CalledFunctions.begin();; ++J) { 237 assert(J != CalledFunctions.end() && 238 "Cannot find callsite to update!"); 239 if (!J->first && J->second == OldNode) { 240 J->second = NewNode; 241 OldNode->DropRef(); 242 NewNode->AddRef(); 243 break; 244 } 245 } 246 } 247 } else { 248 for (auto *CGN : OldCBs) 249 removeOneAbstractEdgeTo(CGN); 250 for (auto *CGN : NewCBs) 251 addCalledFunction(nullptr, CGN); 252 } 253 return; 254 } 255 } 256 } 257 258 // Provide an explicit template instantiation for the static ID. 259 AnalysisKey CallGraphAnalysis::Key; 260 261 PreservedAnalyses CallGraphPrinterPass::run(Module &M, 262 ModuleAnalysisManager &AM) { 263 AM.getResult<CallGraphAnalysis>(M).print(OS); 264 return PreservedAnalyses::all(); 265 } 266 267 PreservedAnalyses CallGraphSCCsPrinterPass::run(Module &M, 268 ModuleAnalysisManager &AM) { 269 auto &CG = AM.getResult<CallGraphAnalysis>(M); 270 unsigned sccNum = 0; 271 OS << "SCCs for the program in PostOrder:"; 272 for (scc_iterator<CallGraph *> SCCI = scc_begin(&CG); !SCCI.isAtEnd(); 273 ++SCCI) { 274 const std::vector<CallGraphNode *> &nextSCC = *SCCI; 275 OS << "\nSCC #" << ++sccNum << ": "; 276 bool First = true; 277 for (CallGraphNode *CGN : nextSCC) { 278 if (First) 279 First = false; 280 else 281 OS << ", "; 282 OS << (CGN->getFunction() ? CGN->getFunction()->getName() 283 : "external node"); 284 } 285 286 if (nextSCC.size() == 1 && SCCI.hasCycle()) 287 OS << " (Has self-loop)."; 288 } 289 OS << "\n"; 290 return PreservedAnalyses::all(); 291 } 292 293 //===----------------------------------------------------------------------===// 294 // Out-of-line definitions of CallGraphAnalysis class members. 295 // 296 297 //===----------------------------------------------------------------------===// 298 // Implementations of the CallGraphWrapperPass class methods. 299 // 300 301 CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {} 302 303 CallGraphWrapperPass::~CallGraphWrapperPass() = default; 304 305 void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 306 AU.setPreservesAll(); 307 } 308 309 bool CallGraphWrapperPass::runOnModule(Module &M) { 310 // All the real work is done in the constructor for the CallGraph. 311 G.reset(new CallGraph(M)); 312 return false; 313 } 314 315 INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction", 316 false, true) 317 318 char CallGraphWrapperPass::ID = 0; 319 320 void CallGraphWrapperPass::releaseMemory() { G.reset(); } 321 322 void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const { 323 if (!G) { 324 OS << "No call graph has been built!\n"; 325 return; 326 } 327 328 // Just delegate. 329 G->print(OS); 330 } 331 332 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 333 LLVM_DUMP_METHOD 334 void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); } 335 #endif 336