336 lines · cpp
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-exception6//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 25using namespace llvm;26 27//===----------------------------------------------------------------------===//28// Implementations of the CallGraph class methods.29//30 31CallGraph::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 39CallGraph::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 52CallGraph::~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 an58// assertion from firing.59#ifndef NDEBUG60 for (auto &I : FunctionMap)61 I.second->allReferencesDropped();62#endif63}64 65bool CallGraph::invalidate(Module &, const PreservedAnalyses &PA,66 ModuleAnalysisManager::Invalidator &) {67 // Check whether the analysis, all analyses on functions, or the function's68 // CFG have been preserved.69 auto PAC = PA.getChecker<CallGraphAnalysis>();70 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>());71}72 73void CallGraph::addToCallGraph(Function *F) {74 CallGraphNode *Node = getOrInsertFunction(F);75 76 // If this function has external linkage or has its address taken and77 // 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 87void CallGraph::populateCallGraphNode(CallGraphNode *Node) {88 Function *F = Node->getFunction();89 90 // If this function is not defined in this translation unit, it could call91 // 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 else103 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 113void CallGraph::print(raw_ostream &OS) const {114 // Print in a deterministic order by sorting CallGraphNodes by name. We do115 // 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)136LLVM_DUMP_METHOD void CallGraph::dump() const { print(dbgs()); }137#endif138 139// removeFunctionFromModule - Unlink the function from this module, returning140// it. Because this removes the function from the module, the call graph node141// is destroyed. This is only valid if the function does not call any other142// functions (ie, there are no edges in it's CGN). The easiest way to do this143// is to dropAllReferences before calling this.144//145Function *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 node149 FunctionMap.erase(F); // Remove the call graph node from the map150 151 M.getFunctionList().remove(F);152 return F;153}154 155// getOrInsertFunction - This method is identical to calling operator[], but156// it will insert a new CallGraphNode for the specified function if one does157// not already exist.158CallGraphNode *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 172void CallGraphNode::print(raw_ostream &OS) const {173 if (Function *F = getFunction())174 OS << "Call graph node for function: '" << F->getName() << "'";175 else176 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 else185 OS << "external node\n";186 }187 OS << '\n';188}189 190#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)191LLVM_DUMP_METHOD void CallGraphNode::dump() const { print(dbgs()); }192#endif193 194/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite195/// from this node to the specified callee function.196void 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 the210/// specified call site with a new one. Note that this method takes linear211/// time, so it should be used sparingly.212void 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 the223 // 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.259AnalysisKey CallGraphAnalysis::Key;260 261PreservedAnalyses CallGraphPrinterPass::run(Module &M,262 ModuleAnalysisManager &AM) {263 AM.getResult<CallGraphAnalysis>(M).print(OS);264 return PreservedAnalyses::all();265}266 267PreservedAnalyses 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 else281 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 301CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {}302 303CallGraphWrapperPass::~CallGraphWrapperPass() = default;304 305void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {306 AU.setPreservesAll();307}308 309bool 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 315INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",316 false, true)317 318char CallGraphWrapperPass::ID = 0;319 320void CallGraphWrapperPass::releaseMemory() { G.reset(); }321 322void 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)333LLVM_DUMP_METHOD334void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); }335#endif336