Coverage Report

Created: 2017-10-03 07:32

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