Add CallGraphNode::removeAnyCallEdgeTo method
[oota-llvm.git] / lib / Analysis / IPA / CallGraph.cpp
1 //===- CallGraph.cpp - Build a Module's call graph ------------------------===//
2 // 
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
7 // 
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file implements the CallGraph class.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/Analysis/CallGraph.h"
15 #include "llvm/Constants.h"     // Remove when ConstantPointerRefs are gone
16 #include "llvm/Module.h"
17 #include "llvm/Instructions.h"
18 #include "llvm/Support/CallSite.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include <iostream>
21 using namespace llvm;
22
23 static RegisterAnalysis<CallGraph> X("callgraph", "Call Graph Construction");
24
25 // getNodeFor - Return the node for the specified function or create one if it
26 // does not already exist.
27 //
28 CallGraphNode *CallGraph::getNodeFor(Function *F) {
29   CallGraphNode *&CGN = FunctionMap[F];
30   if (CGN) return CGN;
31
32   assert((!F || F->getParent() == Mod) && "Function not in current module!");
33   return CGN = new CallGraphNode(F);
34 }
35
36 static bool isOnlyADirectCall(Function *F, CallSite CS) {
37   if (!CS.getInstruction()) return false;
38   for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I)
39     if (*I == F) return false;
40   return true;
41 }
42
43 // addToCallGraph - Add a function to the call graph, and link the node to all
44 // of the functions that it calls.
45 //
46 void CallGraph::addToCallGraph(Function *F) {
47   CallGraphNode *Node = getNodeFor(F);
48
49   // If this function has external linkage, anything could call it...
50   if (!F->hasInternalLinkage()) {
51     ExternalCallingNode->addCalledFunction(Node);
52
53     // Found the entry point?
54     if (F->getName() == "main") {
55       if (Root)    // Found multiple external mains?  Don't pick one.
56         Root = ExternalCallingNode;
57       else
58         Root = Node;          // Found a main, keep track of it!
59     }
60   }
61   
62   // If this function is not defined in this translation unit, it could call
63   // anything.
64   if (F->isExternal() && !F->getIntrinsicID())
65     Node->addCalledFunction(CallsExternalNode);
66
67   // Loop over all of the users of the function... looking for callers...
68   //
69   bool isUsedExternally = false;
70   for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I) {
71     if (Instruction *Inst = dyn_cast<Instruction>(*I)) {
72       if (isOnlyADirectCall(F, CallSite::get(Inst)))
73         getNodeFor(Inst->getParent()->getParent())->addCalledFunction(Node);
74       else
75         isUsedExternally = true;
76     } else if (GlobalValue *GV = dyn_cast<GlobalValue>(*I)) {
77       for (Value::use_iterator I = GV->use_begin(), E = GV->use_end();
78            I != E; ++I)
79         if (Instruction *Inst = dyn_cast<Instruction>(*I)) {
80           if (isOnlyADirectCall(F, CallSite::get(Inst)))
81             getNodeFor(Inst->getParent()->getParent())->addCalledFunction(Node);
82           else
83             isUsedExternally = true;
84         } else {
85           isUsedExternally = true;
86         }
87     } else {                        // Can't classify the user!
88       isUsedExternally = true;
89     }
90   }
91   if (isUsedExternally)
92     ExternalCallingNode->addCalledFunction(Node);
93
94   // Look for an indirect function call...
95   for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
96     for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; ++II){
97       CallSite CS = CallSite::get(II);
98       if (CS.getInstruction() && !CS.getCalledFunction())
99         Node->addCalledFunction(CallsExternalNode);
100     }
101 }
102
103 bool CallGraph::run(Module &M) {
104   destroy();
105
106   Mod = &M;
107   ExternalCallingNode = getNodeFor(0);
108   CallsExternalNode = new CallGraphNode(0);
109   Root = 0;
110
111   // Add every function to the call graph...
112   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
113     addToCallGraph(I);
114
115   // If we didn't find a main function, use the external call graph node
116   if (Root == 0) Root = ExternalCallingNode;
117   
118   return false;
119 }
120
121 void CallGraph::destroy() {
122   for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end();
123        I != E; ++I)
124     delete I->second;
125   FunctionMap.clear();
126   delete CallsExternalNode;
127   CallsExternalNode = 0;
128 }
129
130 void CallGraphNode::print(std::ostream &OS) const {
131   if (Function *F = getFunction())
132     OS << "Call graph node for function: '" << F->getName() <<"'\n";
133   else
134     OS << "Call graph node <<null function: 0x" << this << ">>:\n";
135
136   for (const_iterator I = begin(), E = end(); I != E; ++I)
137     if ((*I)->getFunction())
138       OS << "  Calls function '" << (*I)->getFunction()->getName() << "'\n";
139     else
140       OS << "  Calls external node\n";
141   OS << "\n";
142 }
143
144 void CallGraphNode::dump() const { print(std::cerr); }
145
146 void CallGraph::print(std::ostream &OS, const Module *M) const {
147   OS << "CallGraph Root is: ";
148   if (Function *F = getRoot()->getFunction())
149     OS << F->getName() << "\n";
150   else
151     OS << "<<null function: 0x" << getRoot() << ">>\n";
152   
153   for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I)
154     I->second->print(OS);
155 }
156
157 void CallGraph::dump() const {
158   print(std::cerr, 0);
159 }
160
161
162 //===----------------------------------------------------------------------===//
163 // Implementations of public modification methods
164 //
165
166 // removeFunctionFromModule - Unlink the function from this module, returning
167 // it.  Because this removes the function from the module, the call graph node
168 // is destroyed.  This is only valid if the function does not call any other
169 // functions (ie, there are no edges in it's CGN).  The easiest way to do this
170 // is to dropAllReferences before calling this.
171 //
172 Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
173   assert(CGN->CalledFunctions.empty() && "Cannot remove function from call "
174          "graph if it references other functions!");
175   Function *F = CGN->getFunction(); // Get the function for the call graph node
176   delete CGN;                       // Delete the call graph node for this func
177   FunctionMap.erase(F);             // Remove the call graph node from the map
178
179   Mod->getFunctionList().remove(F);
180   return F;
181 }
182
183 // changeFunction - This method changes the function associated with this
184 // CallGraphNode, for use by transformations that need to change the prototype
185 // of a Function (thus they must create a new Function and move the old code
186 // over).
187 void CallGraph::changeFunction(Function *OldF, Function *NewF) {
188   iterator I = FunctionMap.find(OldF);
189   CallGraphNode *&New = FunctionMap[NewF];
190   assert(I != FunctionMap.end() && I->second && !New &&
191          "OldF didn't exist in CG or NewF already does!");
192   New = I->second;
193   New->F = NewF;
194   FunctionMap.erase(I);
195 }
196
197
198 void CallGraph::stub() {}
199
200 void CallGraphNode::removeCallEdgeTo(CallGraphNode *Callee) {
201   for (unsigned i = CalledFunctions.size(); ; --i) {
202     assert(i && "Cannot find callee to remove!");
203     if (CalledFunctions[i-1] == Callee) {
204       CalledFunctions.erase(CalledFunctions.begin()+i-1);
205       return;
206     }
207   }
208 }
209
210 // removeAnyCallEdgeTo - This method removes any call edges from this node to
211 // the specified callee function.  This takes more time to execute than
212 // removeCallEdgeTo, so it should not be used unless necessary.
213 void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
214   for (std::vector<CallGraphNode*>::iterator I = CalledFunctions.begin(),
215          E = CalledFunctions.end(); I != E; ++I)
216     if (*I == Callee) {
217       CalledFunctions.erase(I);
218       E = CalledFunctions.end();
219     }
220 }