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