Bug Summary

File:lib/Analysis/CallGraphSCCPass.cpp
Warning:line 153, column 11
Value stored to 'InstrCount' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name CallGraphSCCPass.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/lib/Analysis -I /build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis -I /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn345461/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/8.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-8~svn345461/build-llvm/lib/Analysis -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-10-27-211344-32123-1 -x c++ /build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp -faddrsig
1//===- CallGraphSCCPass.cpp - Pass that operates BU on 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// This file implements the CallGraphSCCPass class, which is used for passes
11// which are implemented as bottom-up traversals on the call graph. Because
12// there may be cycles in the call graph, passes of this type operate on the
13// call-graph in SCC order: that is, they process function bottom-up, except for
14// recursive functions, which they process all at once.
15//
16//===----------------------------------------------------------------------===//
17
18#include "llvm/Analysis/CallGraphSCCPass.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/SCCIterator.h"
21#include "llvm/ADT/Statistic.h"
22#include "llvm/Analysis/CallGraph.h"
23#include "llvm/IR/CallSite.h"
24#include "llvm/IR/Function.h"
25#include "llvm/IR/IRPrintingPasses.h"
26#include "llvm/IR/Intrinsics.h"
27#include "llvm/IR/LLVMContext.h"
28#include "llvm/IR/LegacyPassManagers.h"
29#include "llvm/IR/Module.h"
30#include "llvm/IR/OptBisect.h"
31#include "llvm/IR/PassTimingInfo.h"
32#include "llvm/Pass.h"
33#include "llvm/Support/CommandLine.h"
34#include "llvm/Support/Debug.h"
35#include "llvm/Support/Timer.h"
36#include "llvm/Support/raw_ostream.h"
37#include <cassert>
38#include <string>
39#include <utility>
40#include <vector>
41
42using namespace llvm;
43
44#define DEBUG_TYPE"cgscc-passmgr" "cgscc-passmgr"
45
46static cl::opt<unsigned>
47MaxIterations("max-cg-scc-iterations", cl::ReallyHidden, cl::init(4));
48
49STATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC")static llvm::Statistic MaxSCCIterations = {"cgscc-passmgr", "MaxSCCIterations"
, "Maximum CGSCCPassMgr iterations on one SCC", {0}, {false}}
;
50
51//===----------------------------------------------------------------------===//
52// CGPassManager
53//
54/// CGPassManager manages FPPassManagers and CallGraphSCCPasses.
55
56namespace {
57
58class CGPassManager : public ModulePass, public PMDataManager {
59public:
60 static char ID;
61
62 explicit CGPassManager() : ModulePass(ID), PMDataManager() {}
63
64 /// Execute all of the passes scheduled for execution. Keep track of
65 /// whether any of the passes modifies the module, and if so, return true.
66 bool runOnModule(Module &M) override;
67
68 using ModulePass::doInitialization;
69 using ModulePass::doFinalization;
70
71 bool doInitialization(CallGraph &CG);
72 bool doFinalization(CallGraph &CG);
73
74 /// Pass Manager itself does not invalidate any analysis info.
75 void getAnalysisUsage(AnalysisUsage &Info) const override {
76 // CGPassManager walks SCC and it needs CallGraph.
77 Info.addRequired<CallGraphWrapperPass>();
78 Info.setPreservesAll();
79 }
80
81 StringRef getPassName() const override { return "CallGraph Pass Manager"; }
82
83 PMDataManager *getAsPMDataManager() override { return this; }
84 Pass *getAsPass() override { return this; }
85
86 // Print passes managed by this manager
87 void dumpPassStructure(unsigned Offset) override {
88 errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n";
89 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
90 Pass *P = getContainedPass(Index);
91 P->dumpPassStructure(Offset + 1);
92 dumpLastUses(P, Offset+1);
93 }
94 }
95
96 Pass *getContainedPass(unsigned N) {
97 assert(N < PassVector.size() && "Pass number out of range!")((N < PassVector.size() && "Pass number out of range!"
) ? static_cast<void> (0) : __assert_fail ("N < PassVector.size() && \"Pass number out of range!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 97, __PRETTY_FUNCTION__))
;
98 return static_cast<Pass *>(PassVector[N]);
99 }
100
101 PassManagerType getPassManagerType() const override {
102 return PMT_CallGraphPassManager;
103 }
104
105private:
106 bool RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
107 bool &DevirtualizedCall);
108
109 bool RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
110 CallGraph &CG, bool &CallGraphUpToDate,
111 bool &DevirtualizedCall);
112 bool RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
113 bool IsCheckingMode);
114};
115
116} // end anonymous namespace.
117
118char CGPassManager::ID = 0;
119
120bool CGPassManager::RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
121 CallGraph &CG, bool &CallGraphUpToDate,
122 bool &DevirtualizedCall) {
123 bool Changed = false;
124 PMDataManager *PM = P->getAsPMDataManager();
125 Module &M = CG.getModule();
126
127 if (!PM) {
128 CallGraphSCCPass *CGSP = (CallGraphSCCPass *)P;
129 if (!CallGraphUpToDate) {
130 DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
131 CallGraphUpToDate = true;
132 }
133
134 {
135 unsigned InstrCount, SCCCount = 0;
136 StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
137 bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
138 TimeRegion PassTimer(getPassTimer(CGSP));
139 if (EmitICRemark)
140 InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
141 Changed = CGSP->runOnSCC(CurSCC);
142
143 if (EmitICRemark) {
144 // FIXME: Add getInstructionCount to CallGraphSCC.
145 SCCCount = M.getInstructionCount();
146 // Is there a difference in the number of instructions in the module?
147 if (SCCCount != InstrCount) {
148 // Yep. Emit a remark and update InstrCount.
149 int64_t Delta =
150 static_cast<int64_t>(SCCCount) - static_cast<int64_t>(InstrCount);
151 emitInstrCountChangedRemark(P, M, Delta, InstrCount,
152 FunctionToInstrCount);
153 InstrCount = SCCCount;
Value stored to 'InstrCount' is never read
154 }
155 }
156 }
157
158 // After the CGSCCPass is done, when assertions are enabled, use
159 // RefreshCallGraph to verify that the callgraph was correctly updated.
160#ifndef NDEBUG
161 if (Changed)
162 RefreshCallGraph(CurSCC, CG, true);
163#endif
164
165 return Changed;
166 }
167
168 assert(PM->getPassManagerType() == PMT_FunctionPassManager &&((PM->getPassManagerType() == PMT_FunctionPassManager &&
"Invalid CGPassManager member") ? static_cast<void> (0
) : __assert_fail ("PM->getPassManagerType() == PMT_FunctionPassManager && \"Invalid CGPassManager member\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 169, __PRETTY_FUNCTION__))
169 "Invalid CGPassManager member")((PM->getPassManagerType() == PMT_FunctionPassManager &&
"Invalid CGPassManager member") ? static_cast<void> (0
) : __assert_fail ("PM->getPassManagerType() == PMT_FunctionPassManager && \"Invalid CGPassManager member\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 169, __PRETTY_FUNCTION__))
;
170 FPPassManager *FPP = (FPPassManager*)P;
171
172 // Run pass P on all functions in the current SCC.
173 for (CallGraphNode *CGN : CurSCC) {
174 if (Function *F = CGN->getFunction()) {
175 dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
176 {
177 TimeRegion PassTimer(getPassTimer(FPP));
178 Changed |= FPP->runOnFunction(*F);
179 }
180 F->getContext().yield();
181 }
182 }
183
184 // The function pass(es) modified the IR, they may have clobbered the
185 // callgraph.
186 if (Changed && CallGraphUpToDate) {
187 LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: " << P->getPassName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: "
<< P->getPassName() << '\n'; } } while (false
)
188 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: "
<< P->getPassName() << '\n'; } } while (false
)
;
189 CallGraphUpToDate = false;
190 }
191 return Changed;
192}
193
194/// Scan the functions in the specified CFG and resync the
195/// callgraph with the call sites found in it. This is used after
196/// FunctionPasses have potentially munged the callgraph, and can be used after
197/// CallGraphSCC passes to verify that they correctly updated the callgraph.
198///
199/// This function returns true if it devirtualized an existing function call,
200/// meaning it turned an indirect call into a direct call. This happens when
201/// a function pass like GVN optimizes away stuff feeding the indirect call.
202/// This never happens in checking mode.
203bool CGPassManager::RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
204 bool CheckingMode) {
205 DenseMap<Value*, CallGraphNode*> CallSites;
206
207 LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { dbgs() << "CGSCCPASSMGR: Refreshing SCC with "
<< CurSCC.size() << " nodes:\n"; for (CallGraphNode
*CGN : CurSCC) CGN->dump();; } } while (false)
208 << " nodes:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { dbgs() << "CGSCCPASSMGR: Refreshing SCC with "
<< CurSCC.size() << " nodes:\n"; for (CallGraphNode
*CGN : CurSCC) CGN->dump();; } } while (false)
209 for (CallGraphNode *CGNdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { dbgs() << "CGSCCPASSMGR: Refreshing SCC with "
<< CurSCC.size() << " nodes:\n"; for (CallGraphNode
*CGN : CurSCC) CGN->dump();; } } while (false)
210 : CurSCC) CGN->dump();)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { dbgs() << "CGSCCPASSMGR: Refreshing SCC with "
<< CurSCC.size() << " nodes:\n"; for (CallGraphNode
*CGN : CurSCC) CGN->dump();; } } while (false)
;
211
212 bool MadeChange = false;
213 bool DevirtualizedCall = false;
214
215 // Scan all functions in the SCC.
216 unsigned FunctionNo = 0;
217 for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end();
218 SCCIdx != E; ++SCCIdx, ++FunctionNo) {
219 CallGraphNode *CGN = *SCCIdx;
220 Function *F = CGN->getFunction();
221 if (!F || F->isDeclaration()) continue;
222
223 // Walk the function body looking for call sites. Sync up the call sites in
224 // CGN with those actually in the function.
225
226 // Keep track of the number of direct and indirect calls that were
227 // invalidated and removed.
228 unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
229
230 // Get the set of call sites currently in the function.
231 for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) {
232 // If this call site is null, then the function pass deleted the call
233 // entirely and the WeakTrackingVH nulled it out.
234 if (!I->first ||
235 // If we've already seen this call site, then the FunctionPass RAUW'd
236 // one call with another, which resulted in two "uses" in the edge
237 // list of the same call.
238 CallSites.count(I->first) ||
239
240 // If the call edge is not from a call or invoke, or it is a
241 // instrinsic call, then the function pass RAUW'd a call with
242 // another value. This can happen when constant folding happens
243 // of well known functions etc.
244 !CallSite(I->first) ||
245 (CallSite(I->first).getCalledFunction() &&
246 CallSite(I->first).getCalledFunction()->isIntrinsic() &&
247 Intrinsic::isLeaf(
248 CallSite(I->first).getCalledFunction()->getIntrinsicID()))) {
249 assert(!CheckingMode &&((!CheckingMode && "CallGraphSCCPass did not update the CallGraph correctly!"
) ? static_cast<void> (0) : __assert_fail ("!CheckingMode && \"CallGraphSCCPass did not update the CallGraph correctly!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 250, __PRETTY_FUNCTION__))
250 "CallGraphSCCPass did not update the CallGraph correctly!")((!CheckingMode && "CallGraphSCCPass did not update the CallGraph correctly!"
) ? static_cast<void> (0) : __assert_fail ("!CheckingMode && \"CallGraphSCCPass did not update the CallGraph correctly!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 250, __PRETTY_FUNCTION__))
;
251
252 // If this was an indirect call site, count it.
253 if (!I->second->getFunction())
254 ++NumIndirectRemoved;
255 else
256 ++NumDirectRemoved;
257
258 // Just remove the edge from the set of callees, keep track of whether
259 // I points to the last element of the vector.
260 bool WasLast = I + 1 == E;
261 CGN->removeCallEdge(I);
262
263 // If I pointed to the last element of the vector, we have to bail out:
264 // iterator checking rejects comparisons of the resultant pointer with
265 // end.
266 if (WasLast)
267 break;
268 E = CGN->end();
269 continue;
270 }
271
272 assert(!CallSites.count(I->first) &&((!CallSites.count(I->first) && "Call site occurs in node multiple times"
) ? static_cast<void> (0) : __assert_fail ("!CallSites.count(I->first) && \"Call site occurs in node multiple times\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 273, __PRETTY_FUNCTION__))
273 "Call site occurs in node multiple times")((!CallSites.count(I->first) && "Call site occurs in node multiple times"
) ? static_cast<void> (0) : __assert_fail ("!CallSites.count(I->first) && \"Call site occurs in node multiple times\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 273, __PRETTY_FUNCTION__))
;
274
275 CallSite CS(I->first);
276 if (CS) {
277 Function *Callee = CS.getCalledFunction();
278 // Ignore intrinsics because they're not really function calls.
279 if (!Callee || !(Callee->isIntrinsic()))
280 CallSites.insert(std::make_pair(I->first, I->second));
281 }
282 ++I;
283 }
284
285 // Loop over all of the instructions in the function, getting the callsites.
286 // Keep track of the number of direct/indirect calls added.
287 unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
288
289 for (BasicBlock &BB : *F)
290 for (Instruction &I : BB) {
291 CallSite CS(&I);
292 if (!CS) continue;
293 Function *Callee = CS.getCalledFunction();
294 if (Callee && Callee->isIntrinsic()) continue;
295
296 // If this call site already existed in the callgraph, just verify it
297 // matches up to expectations and remove it from CallSites.
298 DenseMap<Value*, CallGraphNode*>::iterator ExistingIt =
299 CallSites.find(CS.getInstruction());
300 if (ExistingIt != CallSites.end()) {
301 CallGraphNode *ExistingNode = ExistingIt->second;
302
303 // Remove from CallSites since we have now seen it.
304 CallSites.erase(ExistingIt);
305
306 // Verify that the callee is right.
307 if (ExistingNode->getFunction() == CS.getCalledFunction())
308 continue;
309
310 // If we are in checking mode, we are not allowed to actually mutate
311 // the callgraph. If this is a case where we can infer that the
312 // callgraph is less precise than it could be (e.g. an indirect call
313 // site could be turned direct), don't reject it in checking mode, and
314 // don't tweak it to be more precise.
315 if (CheckingMode && CS.getCalledFunction() &&
316 ExistingNode->getFunction() == nullptr)
317 continue;
318
319 assert(!CheckingMode &&((!CheckingMode && "CallGraphSCCPass did not update the CallGraph correctly!"
) ? static_cast<void> (0) : __assert_fail ("!CheckingMode && \"CallGraphSCCPass did not update the CallGraph correctly!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 320, __PRETTY_FUNCTION__))
320 "CallGraphSCCPass did not update the CallGraph correctly!")((!CheckingMode && "CallGraphSCCPass did not update the CallGraph correctly!"
) ? static_cast<void> (0) : __assert_fail ("!CheckingMode && \"CallGraphSCCPass did not update the CallGraph correctly!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 320, __PRETTY_FUNCTION__))
;
321
322 // If not, we either went from a direct call to indirect, indirect to
323 // direct, or direct to different direct.
324 CallGraphNode *CalleeNode;
325 if (Function *Callee = CS.getCalledFunction()) {
326 CalleeNode = CG.getOrInsertFunction(Callee);
327 // Keep track of whether we turned an indirect call into a direct
328 // one.
329 if (!ExistingNode->getFunction()) {
330 DevirtualizedCall = true;
331 LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Devirtualized call to '"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { dbgs() << " CGSCCPASSMGR: Devirtualized call to '"
<< Callee->getName() << "'\n"; } } while (false
)
332 << Callee->getName() << "'\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { dbgs() << " CGSCCPASSMGR: Devirtualized call to '"
<< Callee->getName() << "'\n"; } } while (false
)
;
333 }
334 } else {
335 CalleeNode = CG.getCallsExternalNode();
336 }
337
338 // Update the edge target in CGN.
339 CGN->replaceCallEdge(CS, CS, CalleeNode);
340 MadeChange = true;
341 continue;
342 }
343
344 assert(!CheckingMode &&((!CheckingMode && "CallGraphSCCPass did not update the CallGraph correctly!"
) ? static_cast<void> (0) : __assert_fail ("!CheckingMode && \"CallGraphSCCPass did not update the CallGraph correctly!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 345, __PRETTY_FUNCTION__))
345 "CallGraphSCCPass did not update the CallGraph correctly!")((!CheckingMode && "CallGraphSCCPass did not update the CallGraph correctly!"
) ? static_cast<void> (0) : __assert_fail ("!CheckingMode && \"CallGraphSCCPass did not update the CallGraph correctly!\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 345, __PRETTY_FUNCTION__))
;
346
347 // If the call site didn't exist in the CGN yet, add it.
348 CallGraphNode *CalleeNode;
349 if (Function *Callee = CS.getCalledFunction()) {
350 CalleeNode = CG.getOrInsertFunction(Callee);
351 ++NumDirectAdded;
352 } else {
353 CalleeNode = CG.getCallsExternalNode();
354 ++NumIndirectAdded;
355 }
356
357 CGN->addCalledFunction(CS, CalleeNode);
358 MadeChange = true;
359 }
360
361 // We scanned the old callgraph node, removing invalidated call sites and
362 // then added back newly found call sites. One thing that can happen is
363 // that an old indirect call site was deleted and replaced with a new direct
364 // call. In this case, we have devirtualized a call, and CGSCCPM would like
365 // to iteratively optimize the new code. Unfortunately, we don't really
366 // have a great way to detect when this happens. As an approximation, we
367 // just look at whether the number of indirect calls is reduced and the
368 // number of direct calls is increased. There are tons of ways to fool this
369 // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
370 // direct call) but this is close enough.
371 if (NumIndirectRemoved > NumIndirectAdded &&
372 NumDirectRemoved < NumDirectAdded)
373 DevirtualizedCall = true;
374
375 // After scanning this function, if we still have entries in callsites, then
376 // they are dangling pointers. WeakTrackingVH should save us for this, so
377 // abort if
378 // this happens.
379 assert(CallSites.empty() && "Dangling pointers found in call sites map")((CallSites.empty() && "Dangling pointers found in call sites map"
) ? static_cast<void> (0) : __assert_fail ("CallSites.empty() && \"Dangling pointers found in call sites map\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 379, __PRETTY_FUNCTION__))
;
380
381 // Periodically do an explicit clear to remove tombstones when processing
382 // large scc's.
383 if ((FunctionNo & 15) == 15)
384 CallSites.clear();
385 }
386
387 LLVM_DEBUG(if (MadeChange) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { if (MadeChange) { dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n"
; for (CallGraphNode *CGN : CurSCC) CGN->dump(); if (DevirtualizedCall
) dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n"
; } else { dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n"
; }; } } while (false)
388 dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { if (MadeChange) { dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n"
; for (CallGraphNode *CGN : CurSCC) CGN->dump(); if (DevirtualizedCall
) dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n"
; } else { dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n"
; }; } } while (false)
389 for (CallGraphNode *CGN : CurSCC)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { if (MadeChange) { dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n"
; for (CallGraphNode *CGN : CurSCC) CGN->dump(); if (DevirtualizedCall
) dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n"
; } else { dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n"
; }; } } while (false)
390 CGN->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { if (MadeChange) { dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n"
; for (CallGraphNode *CGN : CurSCC) CGN->dump(); if (DevirtualizedCall
) dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n"
; } else { dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n"
; }; } } while (false)
391 if (DevirtualizedCall)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { if (MadeChange) { dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n"
; for (CallGraphNode *CGN : CurSCC) CGN->dump(); if (DevirtualizedCall
) dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n"
; } else { dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n"
; }; } } while (false)
392 dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { if (MadeChange) { dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n"
; for (CallGraphNode *CGN : CurSCC) CGN->dump(); if (DevirtualizedCall
) dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n"
; } else { dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n"
; }; } } while (false)
393 } else {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { if (MadeChange) { dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n"
; for (CallGraphNode *CGN : CurSCC) CGN->dump(); if (DevirtualizedCall
) dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n"
; } else { dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n"
; }; } } while (false)
394 dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { if (MadeChange) { dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n"
; for (CallGraphNode *CGN : CurSCC) CGN->dump(); if (DevirtualizedCall
) dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n"
; } else { dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n"
; }; } } while (false)
395 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { if (MadeChange) { dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n"
; for (CallGraphNode *CGN : CurSCC) CGN->dump(); if (DevirtualizedCall
) dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n"
; } else { dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n"
; }; } } while (false)
;
396 (void)MadeChange;
397
398 return DevirtualizedCall;
399}
400
401/// Execute the body of the entire pass manager on the specified SCC.
402/// This keeps track of whether a function pass devirtualizes
403/// any calls and returns it in DevirtualizedCall.
404bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
405 bool &DevirtualizedCall) {
406 bool Changed = false;
407
408 // Keep track of whether the callgraph is known to be up-to-date or not.
409 // The CGSSC pass manager runs two types of passes:
410 // CallGraphSCC Passes and other random function passes. Because other
411 // random function passes are not CallGraph aware, they may clobber the
412 // call graph by introducing new calls or deleting other ones. This flag
413 // is set to false when we run a function pass so that we know to clean up
414 // the callgraph when we need to run a CGSCCPass again.
415 bool CallGraphUpToDate = true;
416
417 // Run all passes on current SCC.
418 for (unsigned PassNo = 0, e = getNumContainedPasses();
419 PassNo != e; ++PassNo) {
420 Pass *P = getContainedPass(PassNo);
421
422 // If we're in -debug-pass=Executions mode, construct the SCC node list,
423 // otherwise avoid constructing this string as it is expensive.
424 if (isPassDebuggingExecutionsOrMore()) {
425 std::string Functions;
426 #ifndef NDEBUG
427 raw_string_ostream OS(Functions);
428 for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
429 I != E; ++I) {
430 if (I != CurSCC.begin()) OS << ", ";
431 (*I)->print(OS);
432 }
433 OS.flush();
434 #endif
435 dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
436 }
437 dumpRequiredSet(P);
438
439 initializeAnalysisImpl(P);
440
441 // Actually run this pass on the current SCC.
442 Changed |= RunPassOnSCC(P, CurSCC, CG,
443 CallGraphUpToDate, DevirtualizedCall);
444
445 if (Changed)
446 dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
447 dumpPreservedSet(P);
448
449 verifyPreservedAnalysis(P);
450 removeNotPreservedAnalysis(P);
451 recordAvailableAnalysis(P);
452 removeDeadPasses(P, "", ON_CG_MSG);
453 }
454
455 // If the callgraph was left out of date (because the last pass run was a
456 // functionpass), refresh it before we move on to the next SCC.
457 if (!CallGraphUpToDate)
458 DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
459 return Changed;
460}
461
462/// Execute all of the passes scheduled for execution. Keep track of
463/// whether any of the passes modifies the module, and if so, return true.
464bool CGPassManager::runOnModule(Module &M) {
465 CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
466 bool Changed = doInitialization(CG);
467
468 // Walk the callgraph in bottom-up SCC order.
469 scc_iterator<CallGraph*> CGI = scc_begin(&CG);
470
471 CallGraphSCC CurSCC(CG, &CGI);
472 while (!CGI.isAtEnd()) {
473 // Copy the current SCC and increment past it so that the pass can hack
474 // on the SCC if it wants to without invalidating our iterator.
475 const std::vector<CallGraphNode *> &NodeVec = *CGI;
476 CurSCC.initialize(NodeVec);
477 ++CGI;
478
479 // At the top level, we run all the passes in this pass manager on the
480 // functions in this SCC. However, we support iterative compilation in the
481 // case where a function pass devirtualizes a call to a function. For
482 // example, it is very common for a function pass (often GVN or instcombine)
483 // to eliminate the addressing that feeds into a call. With that improved
484 // information, we would like the call to be an inline candidate, infer
485 // mod-ref information etc.
486 //
487 // Because of this, we allow iteration up to a specified iteration count.
488 // This only happens in the case of a devirtualized call, so we only burn
489 // compile time in the case that we're making progress. We also have a hard
490 // iteration count limit in case there is crazy code.
491 unsigned Iteration = 0;
492 bool DevirtualizedCall = false;
493 do {
494 LLVM_DEBUG(if (Iteration) dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { if (Iteration) dbgs() << " SCCPASSMGR: Re-visiting SCC, iteration #"
<< Iteration << '\n'; } } while (false)
495 << " SCCPASSMGR: Re-visiting SCC, iteration #" << Iterationdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { if (Iteration) dbgs() << " SCCPASSMGR: Re-visiting SCC, iteration #"
<< Iteration << '\n'; } } while (false)
496 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { if (Iteration) dbgs() << " SCCPASSMGR: Re-visiting SCC, iteration #"
<< Iteration << '\n'; } } while (false)
;
497 DevirtualizedCall = false;
498 Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
499 } while (Iteration++ < MaxIterations && DevirtualizedCall);
500
501 if (DevirtualizedCall)
502 LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { dbgs() << " CGSCCPASSMGR: Stopped iteration after "
<< Iteration << " times, due to -max-cg-scc-iterations\n"
; } } while (false)
503 << Iterationdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { dbgs() << " CGSCCPASSMGR: Stopped iteration after "
<< Iteration << " times, due to -max-cg-scc-iterations\n"
; } } while (false)
504 << " times, due to -max-cg-scc-iterations\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("cgscc-passmgr")) { dbgs() << " CGSCCPASSMGR: Stopped iteration after "
<< Iteration << " times, due to -max-cg-scc-iterations\n"
; } } while (false)
;
505
506 MaxSCCIterations.updateMax(Iteration);
507 }
508 Changed |= doFinalization(CG);
509 return Changed;
510}
511
512/// Initialize CG
513bool CGPassManager::doInitialization(CallGraph &CG) {
514 bool Changed = false;
515 for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
516 if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
517 assert(PM->getPassManagerType() == PMT_FunctionPassManager &&((PM->getPassManagerType() == PMT_FunctionPassManager &&
"Invalid CGPassManager member") ? static_cast<void> (0
) : __assert_fail ("PM->getPassManagerType() == PMT_FunctionPassManager && \"Invalid CGPassManager member\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 518, __PRETTY_FUNCTION__))
518 "Invalid CGPassManager member")((PM->getPassManagerType() == PMT_FunctionPassManager &&
"Invalid CGPassManager member") ? static_cast<void> (0
) : __assert_fail ("PM->getPassManagerType() == PMT_FunctionPassManager && \"Invalid CGPassManager member\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 518, __PRETTY_FUNCTION__))
;
519 Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
520 } else {
521 Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
522 }
523 }
524 return Changed;
525}
526
527/// Finalize CG
528bool CGPassManager::doFinalization(CallGraph &CG) {
529 bool Changed = false;
530 for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
531 if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
532 assert(PM->getPassManagerType() == PMT_FunctionPassManager &&((PM->getPassManagerType() == PMT_FunctionPassManager &&
"Invalid CGPassManager member") ? static_cast<void> (0
) : __assert_fail ("PM->getPassManagerType() == PMT_FunctionPassManager && \"Invalid CGPassManager member\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 533, __PRETTY_FUNCTION__))
533 "Invalid CGPassManager member")((PM->getPassManagerType() == PMT_FunctionPassManager &&
"Invalid CGPassManager member") ? static_cast<void> (0
) : __assert_fail ("PM->getPassManagerType() == PMT_FunctionPassManager && \"Invalid CGPassManager member\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 533, __PRETTY_FUNCTION__))
;
534 Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());
535 } else {
536 Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
537 }
538 }
539 return Changed;
540}
541
542//===----------------------------------------------------------------------===//
543// CallGraphSCC Implementation
544//===----------------------------------------------------------------------===//
545
546/// This informs the SCC and the pass manager that the specified
547/// Old node has been deleted, and New is to be used in its place.
548void CallGraphSCC::ReplaceNode(CallGraphNode *Old, CallGraphNode *New) {
549 assert(Old != New && "Should not replace node with self")((Old != New && "Should not replace node with self") ?
static_cast<void> (0) : __assert_fail ("Old != New && \"Should not replace node with self\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 549, __PRETTY_FUNCTION__))
;
550 for (unsigned i = 0; ; ++i) {
551 assert(i != Nodes.size() && "Node not in SCC")((i != Nodes.size() && "Node not in SCC") ? static_cast
<void> (0) : __assert_fail ("i != Nodes.size() && \"Node not in SCC\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 551, __PRETTY_FUNCTION__))
;
552 if (Nodes[i] != Old) continue;
553 Nodes[i] = New;
554 break;
555 }
556
557 // Update the active scc_iterator so that it doesn't contain dangling
558 // pointers to the old CallGraphNode.
559 scc_iterator<CallGraph*> *CGI = (scc_iterator<CallGraph*>*)Context;
560 CGI->ReplaceNode(Old, New);
561}
562
563//===----------------------------------------------------------------------===//
564// CallGraphSCCPass Implementation
565//===----------------------------------------------------------------------===//
566
567/// Assign pass manager to manage this pass.
568void CallGraphSCCPass::assignPassManager(PMStack &PMS,
569 PassManagerType PreferredType) {
570 // Find CGPassManager
571 while (!PMS.empty() &&
572 PMS.top()->getPassManagerType() > PMT_CallGraphPassManager)
573 PMS.pop();
574
575 assert(!PMS.empty() && "Unable to handle Call Graph Pass")((!PMS.empty() && "Unable to handle Call Graph Pass")
? static_cast<void> (0) : __assert_fail ("!PMS.empty() && \"Unable to handle Call Graph Pass\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 575, __PRETTY_FUNCTION__))
;
576 CGPassManager *CGP;
577
578 if (PMS.top()->getPassManagerType() == PMT_CallGraphPassManager)
579 CGP = (CGPassManager*)PMS.top();
580 else {
581 // Create new Call Graph SCC Pass Manager if it does not exist.
582 assert(!PMS.empty() && "Unable to create Call Graph Pass Manager")((!PMS.empty() && "Unable to create Call Graph Pass Manager"
) ? static_cast<void> (0) : __assert_fail ("!PMS.empty() && \"Unable to create Call Graph Pass Manager\""
, "/build/llvm-toolchain-snapshot-8~svn345461/lib/Analysis/CallGraphSCCPass.cpp"
, 582, __PRETTY_FUNCTION__))
;
583 PMDataManager *PMD = PMS.top();
584
585 // [1] Create new Call Graph Pass Manager
586 CGP = new CGPassManager();
587
588 // [2] Set up new manager's top level manager
589 PMTopLevelManager *TPM = PMD->getTopLevelManager();
590 TPM->addIndirectPassManager(CGP);
591
592 // [3] Assign manager to manage this new manager. This may create
593 // and push new managers into PMS
594 Pass *P = CGP;
595 TPM->schedulePass(P);
596
597 // [4] Push new manager into PMS
598 PMS.push(CGP);
599 }
600
601 CGP->add(this);
602}
603
604/// For this class, we declare that we require and preserve the call graph.
605/// If the derived class implements this method, it should
606/// always explicitly call the implementation here.
607void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const {
608 AU.addRequired<CallGraphWrapperPass>();
609 AU.addPreserved<CallGraphWrapperPass>();
610}
611
612//===----------------------------------------------------------------------===//
613// PrintCallGraphPass Implementation
614//===----------------------------------------------------------------------===//
615
616namespace {
617
618 /// PrintCallGraphPass - Print a Module corresponding to a call graph.
619 ///
620 class PrintCallGraphPass : public CallGraphSCCPass {
621 std::string Banner;
622 raw_ostream &OS; // raw_ostream to print on.
623
624 public:
625 static char ID;
626
627 PrintCallGraphPass(const std::string &B, raw_ostream &OS)
628 : CallGraphSCCPass(ID), Banner(B), OS(OS) {}
629
630 void getAnalysisUsage(AnalysisUsage &AU) const override {
631 AU.setPreservesAll();
632 }
633
634 bool runOnSCC(CallGraphSCC &SCC) override {
635 bool BannerPrinted = false;
636 auto PrintBannerOnce = [&] () {
637 if (BannerPrinted)
638 return;
639 OS << Banner;
640 BannerPrinted = true;
641 };
642 for (CallGraphNode *CGN : SCC) {
643 if (Function *F = CGN->getFunction()) {
644 if (!F->isDeclaration() && isFunctionInPrintList(F->getName())) {
645 PrintBannerOnce();
646 F->print(OS);
647 }
648 } else if (isFunctionInPrintList("*")) {
649 PrintBannerOnce();
650 OS << "\nPrinting <null> Function\n";
651 }
652 }
653 return false;
654 }
655
656 StringRef getPassName() const override { return "Print CallGraph IR"; }
657 };
658
659} // end anonymous namespace.
660
661char PrintCallGraphPass::ID = 0;
662
663Pass *CallGraphSCCPass::createPrinterPass(raw_ostream &OS,
664 const std::string &Banner) const {
665 return new PrintCallGraphPass(Banner, OS);
666}
667
668bool CallGraphSCCPass::skipSCC(CallGraphSCC &SCC) const {
669 return !SCC.getCallGraph().getModule()
670 .getContext()
671 .getOptPassGate()
672 .shouldRunPass(this, SCC);
673}
674
675char DummyCGSCCPass::ID = 0;
676
677INITIALIZE_PASS(DummyCGSCCPass, "DummyCGSCCPass", "DummyCGSCCPass", false,static void *initializeDummyCGSCCPassPassOnce(PassRegistry &
Registry) { PassInfo *PI = new PassInfo( "DummyCGSCCPass", "DummyCGSCCPass"
, &DummyCGSCCPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<DummyCGSCCPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeDummyCGSCCPassPassFlag
; void llvm::initializeDummyCGSCCPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeDummyCGSCCPassPassFlag, initializeDummyCGSCCPassPassOnce
, std::ref(Registry)); }
678 false)static void *initializeDummyCGSCCPassPassOnce(PassRegistry &
Registry) { PassInfo *PI = new PassInfo( "DummyCGSCCPass", "DummyCGSCCPass"
, &DummyCGSCCPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<DummyCGSCCPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeDummyCGSCCPassPassFlag
; void llvm::initializeDummyCGSCCPassPass(PassRegistry &Registry
) { llvm::call_once(InitializeDummyCGSCCPassPassFlag, initializeDummyCGSCCPassPassOnce
, std::ref(Registry)); }