]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/Analysis/IPA/CallGraph.cpp
1 //===- CallGraph.cpp - Build a Module's call graph ------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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"
19 //===----------------------------------------------------------------------===//
20 // Implementations of the CallGraph class methods.
23 CallGraph::CallGraph(Module
&M
)
24 : M(M
), Root(nullptr), ExternalCallingNode(getOrInsertFunction(nullptr)),
25 CallsExternalNode(new CallGraphNode(nullptr)) {
26 // Add every function to the call graph.
27 for (Module::iterator I
= M
.begin(), E
= M
.end(); I
!= E
; ++I
)
30 // If we didn't find a main function, use the external call graph node
32 Root
= ExternalCallingNode
;
35 CallGraph::~CallGraph() {
36 // CallsExternalNode is not in the function map, delete it explicitly.
37 CallsExternalNode
->allReferencesDropped();
38 delete CallsExternalNode
;
40 // Reset all node's use counts to zero before deleting them to prevent an
41 // assertion from firing.
43 for (FunctionMapTy::iterator I
= FunctionMap
.begin(), E
= FunctionMap
.end();
45 I
->second
->allReferencesDropped();
47 for (FunctionMapTy::iterator I
= FunctionMap
.begin(), E
= FunctionMap
.end();
52 void CallGraph::addToCallGraph(Function
*F
) {
53 CallGraphNode
*Node
= getOrInsertFunction(F
);
55 // If this function has external linkage, anything could call it.
56 if (!F
->hasLocalLinkage()) {
57 ExternalCallingNode
->addCalledFunction(CallSite(), Node
);
59 // Found the entry point?
60 if (F
->getName() == "main") {
61 if (Root
) // Found multiple external mains? Don't pick one.
62 Root
= ExternalCallingNode
;
64 Root
= Node
; // Found a main, keep track of it!
68 // If this function has its address taken, anything could call it.
69 if (F
->hasAddressTaken())
70 ExternalCallingNode
->addCalledFunction(CallSite(), Node
);
72 // If this function is not defined in this translation unit, it could call
74 if (F
->isDeclaration() && !F
->isIntrinsic())
75 Node
->addCalledFunction(CallSite(), CallsExternalNode
);
77 // Look for calls by this function.
78 for (Function::iterator BB
= F
->begin(), BBE
= F
->end(); BB
!= BBE
; ++BB
)
79 for (BasicBlock::iterator II
= BB
->begin(), IE
= BB
->end(); II
!= IE
;
81 CallSite
CS(cast
<Value
>(II
));
83 const Function
*Callee
= CS
.getCalledFunction();
85 // Indirect calls of intrinsics are not allowed so no need to check.
86 Node
->addCalledFunction(CS
, CallsExternalNode
);
87 else if (!Callee
->isIntrinsic())
88 Node
->addCalledFunction(CS
, getOrInsertFunction(Callee
));
93 void CallGraph::print(raw_ostream
&OS
) const {
94 OS
<< "CallGraph Root is: ";
95 if (Function
*F
= Root
->getFunction())
96 OS
<< F
->getName() << "\n";
98 OS
<< "<<null function: 0x" << Root
<< ">>\n";
101 for (CallGraph::const_iterator I
= begin(), E
= end(); I
!= E
; ++I
)
102 I
->second
->print(OS
);
105 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
106 void CallGraph::dump() const { print(dbgs()); }
109 // removeFunctionFromModule - Unlink the function from this module, returning
110 // it. Because this removes the function from the module, the call graph node
111 // is destroyed. This is only valid if the function does not call any other
112 // functions (ie, there are no edges in it's CGN). The easiest way to do this
113 // is to dropAllReferences before calling this.
115 Function
*CallGraph::removeFunctionFromModule(CallGraphNode
*CGN
) {
116 assert(CGN
->empty() && "Cannot remove function from call "
117 "graph if it references other functions!");
118 Function
*F
= CGN
->getFunction(); // Get the function for the call graph node
119 delete CGN
; // Delete the call graph node for this func
120 FunctionMap
.erase(F
); // Remove the call graph node from the map
122 M
.getFunctionList().remove(F
);
126 /// spliceFunction - Replace the function represented by this node by another.
127 /// This does not rescan the body of the function, so it is suitable when
128 /// splicing the body of the old function to the new while also updating all
129 /// callers from old to new.
131 void CallGraph::spliceFunction(const Function
*From
, const Function
*To
) {
132 assert(FunctionMap
.count(From
) && "No CallGraphNode for function!");
133 assert(!FunctionMap
.count(To
) &&
134 "Pointing CallGraphNode at a function that already exists");
135 FunctionMapTy::iterator I
= FunctionMap
.find(From
);
136 I
->second
->F
= const_cast<Function
*>(To
);
137 FunctionMap
[To
] = I
->second
;
138 FunctionMap
.erase(I
);
141 // getOrInsertFunction - This method is identical to calling operator[], but
142 // it will insert a new CallGraphNode for the specified function if one does
143 // not already exist.
144 CallGraphNode
*CallGraph::getOrInsertFunction(const Function
*F
) {
145 CallGraphNode
*&CGN
= FunctionMap
[F
];
149 assert((!F
|| F
->getParent() == &M
) && "Function not in current module!");
150 return CGN
= new CallGraphNode(const_cast<Function
*>(F
));
153 //===----------------------------------------------------------------------===//
154 // Implementations of the CallGraphNode class methods.
157 void CallGraphNode::print(raw_ostream
&OS
) const {
158 if (Function
*F
= getFunction())
159 OS
<< "Call graph node for function: '" << F
->getName() << "'";
161 OS
<< "Call graph node <<null function>>";
163 OS
<< "<<" << this << ">> #uses=" << getNumReferences() << '\n';
165 for (const_iterator I
= begin(), E
= end(); I
!= E
; ++I
) {
166 OS
<< " CS<" << I
->first
<< "> calls ";
167 if (Function
*FI
= I
->second
->getFunction())
168 OS
<< "function '" << FI
->getName() <<"'\n";
170 OS
<< "external node\n";
175 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
176 void CallGraphNode::dump() const { print(dbgs()); }
179 /// removeCallEdgeFor - This method removes the edge in the node for the
180 /// specified call site. Note that this method takes linear time, so it
181 /// should be used sparingly.
182 void CallGraphNode::removeCallEdgeFor(CallSite CS
) {
183 for (CalledFunctionsVector::iterator I
= CalledFunctions
.begin(); ; ++I
) {
184 assert(I
!= CalledFunctions
.end() && "Cannot find callsite to remove!");
185 if (I
->first
== CS
.getInstruction()) {
186 I
->second
->DropRef();
187 *I
= CalledFunctions
.back();
188 CalledFunctions
.pop_back();
194 // removeAnyCallEdgeTo - This method removes any call edges from this node to
195 // the specified callee function. This takes more time to execute than
196 // removeCallEdgeTo, so it should not be used unless necessary.
197 void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode
*Callee
) {
198 for (unsigned i
= 0, e
= CalledFunctions
.size(); i
!= e
; ++i
)
199 if (CalledFunctions
[i
].second
== Callee
) {
201 CalledFunctions
[i
] = CalledFunctions
.back();
202 CalledFunctions
.pop_back();
207 /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
208 /// from this node to the specified callee function.
209 void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode
*Callee
) {
210 for (CalledFunctionsVector::iterator I
= CalledFunctions
.begin(); ; ++I
) {
211 assert(I
!= CalledFunctions
.end() && "Cannot find callee to remove!");
213 if (CR
.second
== Callee
&& CR
.first
== nullptr) {
215 *I
= CalledFunctions
.back();
216 CalledFunctions
.pop_back();
222 /// replaceCallEdge - This method replaces the edge in the node for the
223 /// specified call site with a new one. Note that this method takes linear
224 /// time, so it should be used sparingly.
225 void CallGraphNode::replaceCallEdge(CallSite CS
,
226 CallSite NewCS
, CallGraphNode
*NewNode
){
227 for (CalledFunctionsVector::iterator I
= CalledFunctions
.begin(); ; ++I
) {
228 assert(I
!= CalledFunctions
.end() && "Cannot find callsite to remove!");
229 if (I
->first
== CS
.getInstruction()) {
230 I
->second
->DropRef();
231 I
->first
= NewCS
.getInstruction();
239 //===----------------------------------------------------------------------===//
240 // Out-of-line definitions of CallGraphAnalysis class members.
243 char CallGraphAnalysis::PassID
;
245 //===----------------------------------------------------------------------===//
246 // Implementations of the CallGraphWrapperPass class methods.
249 CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID
) {
250 initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
253 CallGraphWrapperPass::~CallGraphWrapperPass() {}
255 void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage
&AU
) const {
256 AU
.setPreservesAll();
259 bool CallGraphWrapperPass::runOnModule(Module
&M
) {
260 // All the real work is done in the constructor for the CallGraph.
261 G
.reset(new CallGraph(M
));
265 INITIALIZE_PASS(CallGraphWrapperPass
, "basiccg", "CallGraph Construction",
268 char CallGraphWrapperPass::ID
= 0;
270 void CallGraphWrapperPass::releaseMemory() { G
.reset(); }
272 void CallGraphWrapperPass::print(raw_ostream
&OS
, const Module
*) const {
274 OS
<< "No call graph has been built!\n";
282 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
283 void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); }