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