Bug Summary

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