1//===- CallGraph.cpp - Build a Module's call graph ------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "llvm/Analysis/CallGraph.h"
11#include "llvm/IR/CallSite.h"
12#include "llvm/IR/Instructions.h"
13#include "llvm/IR/IntrinsicInst.h"
14#include "llvm/IR/Module.h"
15#include "llvm/Support/Debug.h"
16#include "llvm/Support/raw_ostream.h"
17using namespace llvm;
18
19//===----------------------------------------------------------------------===//
20// Implementations of the CallGraph class methods.
21//
22
23CallGraph::CallGraph(Module &M)
24    : M(M), Root(nullptr), ExternalCallingNode(getOrInsertFunction(nullptr)),
25      CallsExternalNode(llvm::make_unique<CallGraphNode>(nullptr)) {
26  // Add every function to the call graph.
27  for (Function &F : M)
28    addToCallGraph(&F);
29
30  // If we didn't find a main function, use the external call graph node
31  if (!Root)
32    Root = ExternalCallingNode;
33}
34
35CallGraph::CallGraph(CallGraph &&Arg)
36    : M(Arg.M), FunctionMap(std::move(Arg.FunctionMap)), Root(Arg.Root),
37      ExternalCallingNode(Arg.ExternalCallingNode),
38      CallsExternalNode(std::move(Arg.CallsExternalNode)) {
39  Arg.FunctionMap.clear();
40  Arg.Root = nullptr;
41  Arg.ExternalCallingNode = nullptr;
42}
43
44CallGraph::~CallGraph() {
45  // CallsExternalNode is not in the function map, delete it explicitly.
46  if (CallsExternalNode)
47    CallsExternalNode->allReferencesDropped();
48
49// Reset all node's use counts to zero before deleting them to prevent an
50// assertion from firing.
51#ifndef NDEBUG
52  for (auto &I : FunctionMap)
53    I.second->allReferencesDropped();
54#endif
55}
56
57void CallGraph::addToCallGraph(Function *F) {
58  CallGraphNode *Node = getOrInsertFunction(F);
59
60  // If this function has external linkage, anything could call it.
61  if (!F->hasLocalLinkage()) {
62    ExternalCallingNode->addCalledFunction(CallSite(), Node);
63
64    // Found the entry point?
65    if (F->getName() == "main") {
66      if (Root) // Found multiple external mains?  Don't pick one.
67        Root = ExternalCallingNode;
68      else
69        Root = Node; // Found a main, keep track of it!
70    }
71  }
72
73  // If this function has its address taken, anything could call it.
74  if (F->hasAddressTaken())
75    ExternalCallingNode->addCalledFunction(CallSite(), Node);
76
77  // If this function is not defined in this translation unit, it could call
78  // anything.
79  if (F->isDeclaration() && !F->isIntrinsic())
80    Node->addCalledFunction(CallSite(), CallsExternalNode.get());
81
82  // Look for calls by this function.
83  for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
84    for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;
85         ++II) {
86      CallSite CS(cast<Value>(II));
87      if (CS) {
88        const Function *Callee = CS.getCalledFunction();
89        if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
90          // Indirect calls of intrinsics are not allowed so no need to check.
91          // We can be more precise here by using TargetArg returned by
92          // Intrinsic::isLeaf.
93          Node->addCalledFunction(CS, CallsExternalNode.get());
94        else if (!Callee->isIntrinsic())
95          Node->addCalledFunction(CS, getOrInsertFunction(Callee));
96      }
97    }
98}
99
100void CallGraph::print(raw_ostream &OS) const {
101  OS << "CallGraph Root is: ";
102  if (Function *F = Root->getFunction())
103    OS << F->getName() << "\n";
104  else {
105    OS << "<<null function: 0x" << Root << ">>\n";
106  }
107
108  // Print in a deterministic order by sorting CallGraphNodes by name.  We do
109  // this here to avoid slowing down the non-printing fast path.
110
111  SmallVector<CallGraphNode *, 16> Nodes;
112  Nodes.reserve(FunctionMap.size());
113
114  for (auto I = begin(), E = end(); I != E; ++I)
115    Nodes.push_back(I->second.get());
116
117  std::sort(Nodes.begin(), Nodes.end(),
118            [](CallGraphNode *LHS, CallGraphNode *RHS) {
119    if (Function *LF = LHS->getFunction())
120      if (Function *RF = RHS->getFunction())
121        return LF->getName() < RF->getName();
122
123    return RHS->getFunction() != nullptr;
124  });
125
126  for (CallGraphNode *CN : Nodes)
127    CN->print(OS);
128}
129
130LLVM_DUMP_METHOD
131void CallGraph::dump() const { print(dbgs()); }
132
133// removeFunctionFromModule - Unlink the function from this module, returning
134// it.  Because this removes the function from the module, the call graph node
135// is destroyed.  This is only valid if the function does not call any other
136// functions (ie, there are no edges in it's CGN).  The easiest way to do this
137// is to dropAllReferences before calling this.
138//
139Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
140  assert(CGN->empty() && "Cannot remove function from call "
141         "graph if it references other functions!");
142  Function *F = CGN->getFunction(); // Get the function for the call graph node
143  FunctionMap.erase(F);             // Remove the call graph node from the map
144
145  M.getFunctionList().remove(F);
146  return F;
147}
148
149/// spliceFunction - Replace the function represented by this node by another.
150/// This does not rescan the body of the function, so it is suitable when
151/// splicing the body of the old function to the new while also updating all
152/// callers from old to new.
153///
154void CallGraph::spliceFunction(const Function *From, const Function *To) {
155  assert(FunctionMap.count(From) && "No CallGraphNode for function!");
156  assert(!FunctionMap.count(To) &&
157         "Pointing CallGraphNode at a function that already exists");
158  FunctionMapTy::iterator I = FunctionMap.find(From);
159  I->second->F = const_cast<Function*>(To);
160  FunctionMap[To] = std::move(I->second);
161  FunctionMap.erase(I);
162}
163
164// getOrInsertFunction - This method is identical to calling operator[], but
165// it will insert a new CallGraphNode for the specified function if one does
166// not already exist.
167CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
168  auto &CGN = FunctionMap[F];
169  if (CGN)
170    return CGN.get();
171
172  assert((!F || F->getParent() == &M) && "Function not in current module!");
173  CGN = llvm::make_unique<CallGraphNode>(const_cast<Function *>(F));
174  return CGN.get();
175}
176
177//===----------------------------------------------------------------------===//
178// Implementations of the CallGraphNode class methods.
179//
180
181void CallGraphNode::print(raw_ostream &OS) const {
182  if (Function *F = getFunction())
183    OS << "Call graph node for function: '" << F->getName() << "'";
184  else
185    OS << "Call graph node <<null function>>";
186
187  OS << "<<" << this << ">>  #uses=" << getNumReferences() << '\n';
188
189  for (const_iterator I = begin(), E = end(); I != E; ++I) {
190    OS << "  CS<" << I->first << "> calls ";
191    if (Function *FI = I->second->getFunction())
192      OS << "function '" << FI->getName() <<"'\n";
193    else
194      OS << "external node\n";
195  }
196  OS << '\n';
197}
198
199LLVM_DUMP_METHOD
200void CallGraphNode::dump() const { print(dbgs()); }
201
202/// removeCallEdgeFor - This method removes the edge in the node for the
203/// specified call site.  Note that this method takes linear time, so it
204/// should be used sparingly.
205void CallGraphNode::removeCallEdgeFor(CallSite CS) {
206  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
207    assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
208    if (I->first == CS.getInstruction()) {
209      I->second->DropRef();
210      *I = CalledFunctions.back();
211      CalledFunctions.pop_back();
212      return;
213    }
214  }
215}
216
217// removeAnyCallEdgeTo - This method removes any call edges from this node to
218// the specified callee function.  This takes more time to execute than
219// removeCallEdgeTo, so it should not be used unless necessary.
220void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
221  for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
222    if (CalledFunctions[i].second == Callee) {
223      Callee->DropRef();
224      CalledFunctions[i] = CalledFunctions.back();
225      CalledFunctions.pop_back();
226      --i; --e;
227    }
228}
229
230/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
231/// from this node to the specified callee function.
232void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) {
233  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
234    assert(I != CalledFunctions.end() && "Cannot find callee to remove!");
235    CallRecord &CR = *I;
236    if (CR.second == Callee && CR.first == nullptr) {
237      Callee->DropRef();
238      *I = CalledFunctions.back();
239      CalledFunctions.pop_back();
240      return;
241    }
242  }
243}
244
245/// replaceCallEdge - This method replaces the edge in the node for the
246/// specified call site with a new one.  Note that this method takes linear
247/// time, so it should be used sparingly.
248void CallGraphNode::replaceCallEdge(CallSite CS,
249                                    CallSite NewCS, CallGraphNode *NewNode){
250  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
251    assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
252    if (I->first == CS.getInstruction()) {
253      I->second->DropRef();
254      I->first = NewCS.getInstruction();
255      I->second = NewNode;
256      NewNode->AddRef();
257      return;
258    }
259  }
260}
261
262//===----------------------------------------------------------------------===//
263// Out-of-line definitions of CallGraphAnalysis class members.
264//
265
266char CallGraphAnalysis::PassID;
267
268//===----------------------------------------------------------------------===//
269// Implementations of the CallGraphWrapperPass class methods.
270//
271
272CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {
273  initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
274}
275
276CallGraphWrapperPass::~CallGraphWrapperPass() {}
277
278void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
279  AU.setPreservesAll();
280}
281
282bool CallGraphWrapperPass::runOnModule(Module &M) {
283  // All the real work is done in the constructor for the CallGraph.
284  G.reset(new CallGraph(M));
285  return false;
286}
287
288INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
289                false, true)
290
291char CallGraphWrapperPass::ID = 0;
292
293void CallGraphWrapperPass::releaseMemory() { G.reset(); }
294
295void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const {
296  if (!G) {
297    OS << "No call graph has been built!\n";
298    return;
299  }
300
301  // Just delegate.
302  G->print(OS);
303}
304
305LLVM_DUMP_METHOD
306void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); }
307