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