Coverage Report

Created: 2019-07-24 05:18

/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)