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/Instructions.h"
12#include "llvm/IR/IntrinsicInst.h"
13#include "llvm/IR/Module.h"
14#include "llvm/Support/CallSite.h"
15#include "llvm/Support/Debug.h"
16#include "llvm/Support/raw_ostream.h"
17using namespace llvm;
18
19CallGraph::CallGraph()
20    : ModulePass(ID), Root(0), ExternalCallingNode(0), CallsExternalNode(0) {
21  initializeCallGraphPass(*PassRegistry::getPassRegistry());
22}
23
24void CallGraph::addToCallGraph(Function *F) {
25  CallGraphNode *Node = getOrInsertFunction(F);
26
27  // If this function has external linkage, anything could call it.
28  if (!F->hasLocalLinkage()) {
29    ExternalCallingNode->addCalledFunction(CallSite(), Node);
30
31    // Found the entry point?
32    if (F->getName() == "main") {
33      if (Root) // Found multiple external mains?  Don't pick one.
34        Root = ExternalCallingNode;
35      else
36        Root = Node; // Found a main, keep track of it!
37    }
38  }
39
40  // If this function has its address taken, anything could call it.
41  if (F->hasAddressTaken())
42    ExternalCallingNode->addCalledFunction(CallSite(), Node);
43
44  // If this function is not defined in this translation unit, it could call
45  // anything.
46  if (F->isDeclaration() && !F->isIntrinsic())
47    Node->addCalledFunction(CallSite(), CallsExternalNode);
48
49  // Look for calls by this function.
50  for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
51    for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;
52         ++II) {
53      CallSite CS(cast<Value>(II));
54      if (CS) {
55        const Function *Callee = CS.getCalledFunction();
56        if (!Callee)
57          // Indirect calls of intrinsics are not allowed so no need to check.
58          Node->addCalledFunction(CS, CallsExternalNode);
59        else if (!Callee->isIntrinsic())
60          Node->addCalledFunction(CS, getOrInsertFunction(Callee));
61      }
62    }
63}
64
65void CallGraph::getAnalysisUsage(AnalysisUsage &AU) const {
66  AU.setPreservesAll();
67}
68
69bool CallGraph::runOnModule(Module &M) {
70  Mod = &M;
71
72  ExternalCallingNode = getOrInsertFunction(0);
73  assert(!CallsExternalNode);
74  CallsExternalNode = new CallGraphNode(0);
75  Root = 0;
76
77  // Add every function to the call graph.
78  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
79    addToCallGraph(I);
80
81  // If we didn't find a main function, use the external call graph node
82  if (Root == 0)
83    Root = ExternalCallingNode;
84
85  return false;
86}
87
88INITIALIZE_PASS(CallGraph, "basiccg", "CallGraph Construction", false, true)
89
90char CallGraph::ID = 0;
91
92void CallGraph::releaseMemory() {
93  /// CallsExternalNode is not in the function map, delete it explicitly.
94  if (CallsExternalNode) {
95    CallsExternalNode->allReferencesDropped();
96    delete CallsExternalNode;
97    CallsExternalNode = 0;
98  }
99
100  if (FunctionMap.empty())
101    return;
102
103// Reset all node's use counts to zero before deleting them to prevent an
104// assertion from firing.
105#ifndef NDEBUG
106  for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
107       I != E; ++I)
108    I->second->allReferencesDropped();
109#endif
110
111  for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
112      I != E; ++I)
113    delete I->second;
114  FunctionMap.clear();
115}
116
117void CallGraph::print(raw_ostream &OS, const Module*) const {
118  OS << "CallGraph Root is: ";
119  if (Function *F = Root->getFunction())
120    OS << F->getName() << "\n";
121  else {
122    OS << "<<null function: 0x" << Root << ">>\n";
123  }
124
125  for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I)
126    I->second->print(OS);
127}
128#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
129void CallGraph::dump() const {
130  print(dbgs(), 0);
131}
132#endif
133
134//===----------------------------------------------------------------------===//
135// Implementations of public modification methods
136//
137
138// removeFunctionFromModule - Unlink the function from this module, returning
139// it.  Because this removes the function from the module, the call graph node
140// is destroyed.  This is only valid if the function does not call any other
141// functions (ie, there are no edges in it's CGN).  The easiest way to do this
142// is to dropAllReferences before calling this.
143//
144Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
145  assert(CGN->empty() && "Cannot remove function from call "
146         "graph if it references other functions!");
147  Function *F = CGN->getFunction(); // Get the function for the call graph node
148  delete CGN;                       // Delete the call graph node for this func
149  FunctionMap.erase(F);             // Remove the call graph node from the map
150
151  Mod->getFunctionList().remove(F);
152  return F;
153}
154
155/// spliceFunction - Replace the function represented by this node by another.
156/// This does not rescan the body of the function, so it is suitable when
157/// splicing the body of the old function to the new while also updating all
158/// callers from old to new.
159///
160void CallGraph::spliceFunction(const Function *From, const Function *To) {
161  assert(FunctionMap.count(From) && "No CallGraphNode for function!");
162  assert(!FunctionMap.count(To) &&
163         "Pointing CallGraphNode at a function that already exists");
164  FunctionMapTy::iterator I = FunctionMap.find(From);
165  I->second->F = const_cast<Function*>(To);
166  FunctionMap[To] = I->second;
167  FunctionMap.erase(I);
168}
169
170// getOrInsertFunction - This method is identical to calling operator[], but
171// it will insert a new CallGraphNode for the specified function if one does
172// not already exist.
173CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
174  CallGraphNode *&CGN = FunctionMap[F];
175  if (CGN) return CGN;
176
177  assert((!F || F->getParent() == Mod) && "Function not in current module!");
178  return CGN = new CallGraphNode(const_cast<Function*>(F));
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
199#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
200void CallGraphNode::dump() const { print(dbgs()); }
201#endif
202
203/// removeCallEdgeFor - This method removes the edge in the node for the
204/// specified call site.  Note that this method takes linear time, so it
205/// should be used sparingly.
206void CallGraphNode::removeCallEdgeFor(CallSite CS) {
207  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
208    assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
209    if (I->first == CS.getInstruction()) {
210      I->second->DropRef();
211      *I = CalledFunctions.back();
212      CalledFunctions.pop_back();
213      return;
214    }
215  }
216}
217
218// removeAnyCallEdgeTo - This method removes any call edges from this node to
219// the specified callee function.  This takes more time to execute than
220// removeCallEdgeTo, so it should not be used unless necessary.
221void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
222  for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
223    if (CalledFunctions[i].second == Callee) {
224      Callee->DropRef();
225      CalledFunctions[i] = CalledFunctions.back();
226      CalledFunctions.pop_back();
227      --i; --e;
228    }
229}
230
231/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
232/// from this node to the specified callee function.
233void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) {
234  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
235    assert(I != CalledFunctions.end() && "Cannot find callee to remove!");
236    CallRecord &CR = *I;
237    if (CR.second == Callee && CR.first == 0) {
238      Callee->DropRef();
239      *I = CalledFunctions.back();
240      CalledFunctions.pop_back();
241      return;
242    }
243  }
244}
245
246/// replaceCallEdge - This method replaces the edge in the node for the
247/// specified call site with a new one.  Note that this method takes linear
248/// time, so it should be used sparingly.
249void CallGraphNode::replaceCallEdge(CallSite CS,
250                                    CallSite NewCS, CallGraphNode *NewNode){
251  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
252    assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
253    if (I->first == CS.getInstruction()) {
254      I->second->DropRef();
255      I->first = NewCS.getInstruction();
256      I->second = NewNode;
257      NewNode->AddRef();
258      return;
259    }
260  }
261}
262
263// Enuse that users of CallGraph.h also link with this file
264DEFINING_FILE_FOR(CallGraph)
265