Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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