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