LLVM 17.0.0git
CallGraphSCCPass.cpp
Go to the documentation of this file.
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
18#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/Statistic.h"
23#include "llvm/IR/Function.h"
24#include "llvm/IR/Intrinsics.h"
25#include "llvm/IR/LLVMContext.h"
27#include "llvm/IR/Module.h"
28#include "llvm/IR/OptBisect.h"
30#include "llvm/IR/PrintPasses.h"
31#include "llvm/Pass.h"
33#include "llvm/Support/Debug.h"
34#include "llvm/Support/Timer.h"
36#include <cassert>
37#include <string>
38#include <utility>
39#include <vector>
40
41using namespace llvm;
42
43#define DEBUG_TYPE "cgscc-passmgr"
44
45namespace llvm {
47 cl::init(4));
48}
49
50STATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC");
51
52//===----------------------------------------------------------------------===//
53// CGPassManager
54//
55/// CGPassManager manages FPPassManagers and CallGraphSCCPasses.
56
57namespace {
58
59class CGPassManager : public ModulePass, public PMDataManager {
60public:
61 static char ID;
62
63 explicit CGPassManager() : ModulePass(ID) {}
64
65 /// Execute all of the passes scheduled for execution. Keep track of
66 /// whether any of the passes modifies the module, and if so, return true.
67 bool runOnModule(Module &M) override;
68
69 using ModulePass::doInitialization;
70 using ModulePass::doFinalization;
71
73 bool doFinalization(CallGraph &CG);
74
75 /// Pass Manager itself does not invalidate any analysis info.
76 void getAnalysisUsage(AnalysisUsage &Info) const override {
77 // CGPassManager walks SCC and it needs CallGraph.
78 Info.addRequired<CallGraphWrapperPass>();
79 Info.setPreservesAll();
80 }
81
82 StringRef getPassName() const override { return "CallGraph Pass Manager"; }
83
84 PMDataManager *getAsPMDataManager() override { return this; }
85 Pass *getAsPass() override { return this; }
86
87 // Print passes managed by this manager
88 void dumpPassStructure(unsigned Offset) override {
89 errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n";
90 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
91 Pass *P = getContainedPass(Index);
92 P->dumpPassStructure(Offset + 1);
94 }
95 }
96
97 Pass *getContainedPass(unsigned N) {
98 assert(N < PassVector.size() && "Pass number out of range!");
99 return static_cast<Pass *>(PassVector[N]);
100 }
101
102 PassManagerType getPassManagerType() const override {
104 }
105
106private:
107 bool RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
108 bool &DevirtualizedCall);
109
110 bool RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
111 CallGraph &CG, bool &CallGraphUpToDate,
112 bool &DevirtualizedCall);
113 bool RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
114 bool IsCheckingMode);
115};
116
117} // end anonymous namespace.
118
119char CGPassManager::ID = 0;
120
121bool CGPassManager::RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
122 CallGraph &CG, bool &CallGraphUpToDate,
123 bool &DevirtualizedCall) {
124 bool Changed = false;
125 PMDataManager *PM = P->getAsPMDataManager();
126 Module &M = CG.getModule();
127
128 if (!PM) {
130 if (!CallGraphUpToDate) {
131 DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
132 CallGraphUpToDate = true;
133 }
134
135 {
136 unsigned InstrCount, SCCCount = 0;
137 StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
138 bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
139 TimeRegion PassTimer(getPassTimer(CGSP));
140 if (EmitICRemark)
141 InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
142 Changed = CGSP->runOnSCC(CurSCC);
143
144 if (EmitICRemark) {
145 // FIXME: Add getInstructionCount to CallGraphSCC.
146 SCCCount = M.getInstructionCount();
147 // Is there a difference in the number of instructions in the module?
148 if (SCCCount != InstrCount) {
149 // Yep. Emit a remark and update InstrCount.
150 int64_t Delta =
151 static_cast<int64_t>(SCCCount) - static_cast<int64_t>(InstrCount);
152 emitInstrCountChangedRemark(P, M, Delta, InstrCount,
153 FunctionToInstrCount);
154 InstrCount = SCCCount;
155 }
156 }
157 }
158
159 // After the CGSCCPass is done, when assertions are enabled, use
160 // RefreshCallGraph to verify that the callgraph was correctly updated.
161#ifndef NDEBUG
162 if (Changed)
163 RefreshCallGraph(CurSCC, CG, true);
164#endif
165
166 return Changed;
167 }
168
170 "Invalid CGPassManager member");
172
173 // Run pass P on all functions in the current SCC.
174 for (CallGraphNode *CGN : CurSCC) {
175 if (Function *F = CGN->getFunction()) {
176 dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
177 {
178 TimeRegion PassTimer(getPassTimer(FPP));
179 Changed |= FPP->runOnFunction(*F);
180 }
181 F->getContext().yield();
182 }
183 }
184
185 // The function pass(es) modified the IR, they may have clobbered the
186 // callgraph.
187 if (Changed && CallGraphUpToDate) {
188 LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: " << P->getPassName()
189 << '\n');
190 CallGraphUpToDate = false;
191 }
192 return Changed;
193}
194
195/// Scan the functions in the specified CFG and resync the
196/// callgraph with the call sites found in it. This is used after
197/// FunctionPasses have potentially munged the callgraph, and can be used after
198/// CallGraphSCC passes to verify that they correctly updated the callgraph.
199///
200/// This function returns true if it devirtualized an existing function call,
201/// meaning it turned an indirect call into a direct call. This happens when
202/// a function pass like GVN optimizes away stuff feeding the indirect call.
203/// This never happens in checking mode.
204bool CGPassManager::RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
205 bool CheckingMode) {
207
208 LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()
209 << " nodes:\n";
210 for (CallGraphNode *CGN
211 : CurSCC) CGN->dump(););
212
213 bool MadeChange = false;
214 bool DevirtualizedCall = false;
215
216 // Scan all functions in the SCC.
217 unsigned FunctionNo = 0;
218 for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end();
219 SCCIdx != E; ++SCCIdx, ++FunctionNo) {
220 CallGraphNode *CGN = *SCCIdx;
221 Function *F = CGN->getFunction();
222 if (!F || F->isDeclaration()) continue;
223
224 // Walk the function body looking for call sites. Sync up the call sites in
225 // CGN with those actually in the function.
226
227 // Keep track of the number of direct and indirect calls that were
228 // invalidated and removed.
229 unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
230
231 CallGraphNode::iterator CGNEnd = CGN->end();
232
233 auto RemoveAndCheckForDone = [&](CallGraphNode::iterator I) {
234 // Just remove the edge from the set of callees, keep track of whether
235 // I points to the last element of the vector.
236 bool WasLast = I + 1 == CGNEnd;
237 CGN->removeCallEdge(I);
238
239 // If I pointed to the last element of the vector, we have to bail out:
240 // iterator checking rejects comparisons of the resultant pointer with
241 // end.
242 if (WasLast)
243 return true;
244
245 CGNEnd = CGN->end();
246 return false;
247 };
248
249 // Get the set of call sites currently in the function.
250 for (CallGraphNode::iterator I = CGN->begin(); I != CGNEnd;) {
251 // Delete "reference" call records that do not have call instruction. We
252 // reinsert them as needed later. However, keep them in checking mode.
253 if (!I->first) {
254 if (CheckingMode) {
255 ++I;
256 continue;
257 }
258 if (RemoveAndCheckForDone(I))
259 break;
260 continue;
261 }
262
263 // If this call site is null, then the function pass deleted the call
264 // entirely and the WeakTrackingVH nulled it out.
265 auto *Call = dyn_cast_or_null<CallBase>(*I->first);
266 if (!Call ||
267 // If we've already seen this call site, then the FunctionPass RAUW'd
268 // one call with another, which resulted in two "uses" in the edge
269 // list of the same call.
270 Calls.count(Call)) {
271 assert(!CheckingMode &&
272 "CallGraphSCCPass did not update the CallGraph correctly!");
273
274 // If this was an indirect call site, count it.
275 if (!I->second->getFunction())
276 ++NumIndirectRemoved;
277 else
278 ++NumDirectRemoved;
279
280 if (RemoveAndCheckForDone(I))
281 break;
282 continue;
283 }
284
285 assert(!Calls.count(Call) && "Call site occurs in node multiple times");
286
287 if (Call) {
288 Function *Callee = Call->getCalledFunction();
289 // Ignore intrinsics because they're not really function calls.
290 if (!Callee || !(Callee->isIntrinsic()))
291 Calls.insert(std::make_pair(Call, I->second));
292 }
293 ++I;
294 }
295
296 // Loop over all of the instructions in the function, getting the callsites.
297 // Keep track of the number of direct/indirect calls added.
298 unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
299
300 for (BasicBlock &BB : *F)
301 for (Instruction &I : BB) {
302 auto *Call = dyn_cast<CallBase>(&I);
303 if (!Call)
304 continue;
305 Function *Callee = Call->getCalledFunction();
306 if (Callee && Callee->isIntrinsic())
307 continue;
308
309 // If we are not in checking mode, insert potential callback calls as
310 // references. This is not a requirement but helps to iterate over the
311 // functions in the right order.
312 if (!CheckingMode) {
313 forEachCallbackFunction(*Call, [&](Function *CB) {
314 CGN->addCalledFunction(nullptr, CG.getOrInsertFunction(CB));
315 });
316 }
317
318 // If this call site already existed in the callgraph, just verify it
319 // matches up to expectations and remove it from Calls.
321 Calls.find(Call);
322 if (ExistingIt != Calls.end()) {
323 CallGraphNode *ExistingNode = ExistingIt->second;
324
325 // Remove from Calls since we have now seen it.
326 Calls.erase(ExistingIt);
327
328 // Verify that the callee is right.
329 if (ExistingNode->getFunction() == Call->getCalledFunction())
330 continue;
331
332 // If we are in checking mode, we are not allowed to actually mutate
333 // the callgraph. If this is a case where we can infer that the
334 // callgraph is less precise than it could be (e.g. an indirect call
335 // site could be turned direct), don't reject it in checking mode, and
336 // don't tweak it to be more precise.
337 if (CheckingMode && Call->getCalledFunction() &&
338 ExistingNode->getFunction() == nullptr)
339 continue;
340
341 assert(!CheckingMode &&
342 "CallGraphSCCPass did not update the CallGraph correctly!");
343
344 // If not, we either went from a direct call to indirect, indirect to
345 // direct, or direct to different direct.
346 CallGraphNode *CalleeNode;
347 if (Function *Callee = Call->getCalledFunction()) {
348 CalleeNode = CG.getOrInsertFunction(Callee);
349 // Keep track of whether we turned an indirect call into a direct
350 // one.
351 if (!ExistingNode->getFunction()) {
352 DevirtualizedCall = true;
353 LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Devirtualized call to '"
354 << Callee->getName() << "'\n");
355 }
356 } else {
357 CalleeNode = CG.getCallsExternalNode();
358 }
359
360 // Update the edge target in CGN.
361 CGN->replaceCallEdge(*Call, *Call, CalleeNode);
362 MadeChange = true;
363 continue;
364 }
365
366 assert(!CheckingMode &&
367 "CallGraphSCCPass did not update the CallGraph correctly!");
368
369 // If the call site didn't exist in the CGN yet, add it.
370 CallGraphNode *CalleeNode;
371 if (Function *Callee = Call->getCalledFunction()) {
372 CalleeNode = CG.getOrInsertFunction(Callee);
373 ++NumDirectAdded;
374 } else {
375 CalleeNode = CG.getCallsExternalNode();
376 ++NumIndirectAdded;
377 }
378
379 CGN->addCalledFunction(Call, CalleeNode);
380 MadeChange = true;
381 }
382
383 // We scanned the old callgraph node, removing invalidated call sites and
384 // then added back newly found call sites. One thing that can happen is
385 // that an old indirect call site was deleted and replaced with a new direct
386 // call. In this case, we have devirtualized a call, and CGSCCPM would like
387 // to iteratively optimize the new code. Unfortunately, we don't really
388 // have a great way to detect when this happens. As an approximation, we
389 // just look at whether the number of indirect calls is reduced and the
390 // number of direct calls is increased. There are tons of ways to fool this
391 // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
392 // direct call) but this is close enough.
393 if (NumIndirectRemoved > NumIndirectAdded &&
394 NumDirectRemoved < NumDirectAdded)
395 DevirtualizedCall = true;
396
397 // After scanning this function, if we still have entries in callsites, then
398 // they are dangling pointers. WeakTrackingVH should save us for this, so
399 // abort if
400 // this happens.
401 assert(Calls.empty() && "Dangling pointers found in call sites map");
402
403 // Periodically do an explicit clear to remove tombstones when processing
404 // large scc's.
405 if ((FunctionNo & 15) == 15)
406 Calls.clear();
407 }
408
409 LLVM_DEBUG(if (MadeChange) {
410 dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
411 for (CallGraphNode *CGN : CurSCC)
412 CGN->dump();
413 if (DevirtualizedCall)
414 dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
415 } else {
416 dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
417 });
418 (void)MadeChange;
419
420 return DevirtualizedCall;
421}
422
423/// Execute the body of the entire pass manager on the specified SCC.
424/// This keeps track of whether a function pass devirtualizes
425/// any calls and returns it in DevirtualizedCall.
426bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
427 bool &DevirtualizedCall) {
428 bool Changed = false;
429
430 // Keep track of whether the callgraph is known to be up-to-date or not.
431 // The CGSSC pass manager runs two types of passes:
432 // CallGraphSCC Passes and other random function passes. Because other
433 // random function passes are not CallGraph aware, they may clobber the
434 // call graph by introducing new calls or deleting other ones. This flag
435 // is set to false when we run a function pass so that we know to clean up
436 // the callgraph when we need to run a CGSCCPass again.
437 bool CallGraphUpToDate = true;
438
439 // Run all passes on current SCC.
440 for (unsigned PassNo = 0, e = getNumContainedPasses();
441 PassNo != e; ++PassNo) {
442 Pass *P = getContainedPass(PassNo);
443
444 // If we're in -debug-pass=Executions mode, construct the SCC node list,
445 // otherwise avoid constructing this string as it is expensive.
446 if (isPassDebuggingExecutionsOrMore()) {
447 std::string Functions;
448 #ifndef NDEBUG
449 raw_string_ostream OS(Functions);
450 ListSeparator LS;
451 for (const CallGraphNode *CGN : CurSCC) {
452 OS << LS;
453 CGN->print(OS);
454 }
455 OS.flush();
456 #endif
457 dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
458 }
459 dumpRequiredSet(P);
460
461 initializeAnalysisImpl(P);
462
463#ifdef EXPENSIVE_CHECKS
464 uint64_t RefHash = P->structuralHash(CG.getModule());
465#endif
466
467 // Actually run this pass on the current SCC.
468 bool LocalChanged =
469 RunPassOnSCC(P, CurSCC, CG, CallGraphUpToDate, DevirtualizedCall);
470
471 Changed |= LocalChanged;
472
473#ifdef EXPENSIVE_CHECKS
474 if (!LocalChanged && (RefHash != P->structuralHash(CG.getModule()))) {
475 llvm::errs() << "Pass modifies its input and doesn't report it: "
476 << P->getPassName() << "\n";
477 llvm_unreachable("Pass modifies its input and doesn't report it");
478 }
479#endif
480 if (LocalChanged)
481 dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
482 dumpPreservedSet(P);
483
484 verifyPreservedAnalysis(P);
485 if (LocalChanged)
486 removeNotPreservedAnalysis(P);
487 recordAvailableAnalysis(P);
488 removeDeadPasses(P, "", ON_CG_MSG);
489 }
490
491 // If the callgraph was left out of date (because the last pass run was a
492 // functionpass), refresh it before we move on to the next SCC.
493 if (!CallGraphUpToDate)
494 DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
495 return Changed;
496}
497
498/// Execute all of the passes scheduled for execution. Keep track of
499/// whether any of the passes modifies the module, and if so, return true.
500bool CGPassManager::runOnModule(Module &M) {
501 CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
502 bool Changed = doInitialization(CG);
503
504 // Walk the callgraph in bottom-up SCC order.
506
507 CallGraphSCC CurSCC(CG, &CGI);
508 while (!CGI.isAtEnd()) {
509 // Copy the current SCC and increment past it so that the pass can hack
510 // on the SCC if it wants to without invalidating our iterator.
511 const std::vector<CallGraphNode *> &NodeVec = *CGI;
512 CurSCC.initialize(NodeVec);
513 ++CGI;
514
515 // At the top level, we run all the passes in this pass manager on the
516 // functions in this SCC. However, we support iterative compilation in the
517 // case where a function pass devirtualizes a call to a function. For
518 // example, it is very common for a function pass (often GVN or instcombine)
519 // to eliminate the addressing that feeds into a call. With that improved
520 // information, we would like the call to be an inline candidate, infer
521 // mod-ref information etc.
522 //
523 // Because of this, we allow iteration up to a specified iteration count.
524 // This only happens in the case of a devirtualized call, so we only burn
525 // compile time in the case that we're making progress. We also have a hard
526 // iteration count limit in case there is crazy code.
527 unsigned Iteration = 0;
528 bool DevirtualizedCall = false;
529 do {
530 LLVM_DEBUG(if (Iteration) dbgs()
531 << " SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration
532 << '\n');
533 DevirtualizedCall = false;
534 Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
535 } while (Iteration++ < MaxDevirtIterations && DevirtualizedCall);
536
537 if (DevirtualizedCall)
538 LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after "
539 << Iteration
540 << " times, due to -max-devirt-iterations\n");
541
542 MaxSCCIterations.updateMax(Iteration);
543 }
544 Changed |= doFinalization(CG);
545 return Changed;
546}
547
548/// Initialize CG
549bool CGPassManager::doInitialization(CallGraph &CG) {
550 bool Changed = false;
551 for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
552 if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
554 "Invalid CGPassManager member");
555 Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
556 } else {
557 Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
558 }
559 }
560 return Changed;
561}
562
563/// Finalize CG
564bool CGPassManager::doFinalization(CallGraph &CG) {
565 bool Changed = false;
566 for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
567 if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
569 "Invalid CGPassManager member");
570 Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());
571 } else {
572 Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
573 }
574 }
575 return Changed;
576}
577
578//===----------------------------------------------------------------------===//
579// CallGraphSCC Implementation
580//===----------------------------------------------------------------------===//
581
582/// This informs the SCC and the pass manager that the specified
583/// Old node has been deleted, and New is to be used in its place.
585 assert(Old != New && "Should not replace node with self");
586 for (unsigned i = 0; ; ++i) {
587 assert(i != Nodes.size() && "Node not in SCC");
588 if (Nodes[i] != Old) continue;
589 if (New)
590 Nodes[i] = New;
591 else
592 Nodes.erase(Nodes.begin() + i);
593 break;
594 }
595
596 // Update the active scc_iterator so that it doesn't contain dangling
597 // pointers to the old CallGraphNode.
599 CGI->ReplaceNode(Old, New);
600}
601
603 ReplaceNode(Old, /*New=*/nullptr);
604}
605
606//===----------------------------------------------------------------------===//
607// CallGraphSCCPass Implementation
608//===----------------------------------------------------------------------===//
609
610/// Assign pass manager to manage this pass.
612 PassManagerType PreferredType) {
613 // Find CGPassManager
614 while (!PMS.empty() &&
616 PMS.pop();
617
618 assert(!PMS.empty() && "Unable to handle Call Graph Pass");
619 CGPassManager *CGP;
620
622 CGP = (CGPassManager*)PMS.top();
623 else {
624 // Create new Call Graph SCC Pass Manager if it does not exist.
625 assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");
626 PMDataManager *PMD = PMS.top();
627
628 // [1] Create new Call Graph Pass Manager
629 CGP = new CGPassManager();
630
631 // [2] Set up new manager's top level manager
633 TPM->addIndirectPassManager(CGP);
634
635 // [3] Assign manager to manage this new manager. This may create
636 // and push new managers into PMS
637 Pass *P = CGP;
638 TPM->schedulePass(P);
639
640 // [4] Push new manager into PMS
641 PMS.push(CGP);
642 }
643
644 CGP->add(this);
645}
646
647/// For this class, we declare that we require and preserve the call graph.
648/// If the derived class implements this method, it should
649/// always explicitly call the implementation here.
653}
654
655//===----------------------------------------------------------------------===//
656// PrintCallGraphPass Implementation
657//===----------------------------------------------------------------------===//
658
659namespace {
660
661 /// PrintCallGraphPass - Print a Module corresponding to a call graph.
662 ///
663 class PrintCallGraphPass : public CallGraphSCCPass {
664 std::string Banner;
665 raw_ostream &OS; // raw_ostream to print on.
666
667 public:
668 static char ID;
669
670 PrintCallGraphPass(const std::string &B, raw_ostream &OS)
671 : CallGraphSCCPass(ID), Banner(B), OS(OS) {}
672
673 void getAnalysisUsage(AnalysisUsage &AU) const override {
674 AU.setPreservesAll();
675 }
676
677 bool runOnSCC(CallGraphSCC &SCC) override {
678 bool BannerPrinted = false;
679 auto PrintBannerOnce = [&]() {
680 if (BannerPrinted)
681 return;
682 OS << Banner;
683 BannerPrinted = true;
684 };
685
686 bool NeedModule = llvm::forcePrintModuleIR();
687 if (isFunctionInPrintList("*") && NeedModule) {
688 PrintBannerOnce();
689 OS << "\n";
690 SCC.getCallGraph().getModule().print(OS, nullptr);
691 return false;
692 }
693 bool FoundFunction = false;
694 for (CallGraphNode *CGN : SCC) {
695 if (Function *F = CGN->getFunction()) {
696 if (!F->isDeclaration() && isFunctionInPrintList(F->getName())) {
697 FoundFunction = true;
698 if (!NeedModule) {
699 PrintBannerOnce();
700 F->print(OS);
701 }
702 }
703 } else if (isFunctionInPrintList("*")) {
704 PrintBannerOnce();
705 OS << "\nPrinting <null> Function\n";
706 }
707 }
708 if (NeedModule && FoundFunction) {
709 PrintBannerOnce();
710 OS << "\n";
711 SCC.getCallGraph().getModule().print(OS, nullptr);
712 }
713 return false;
714 }
715
716 StringRef getPassName() const override { return "Print CallGraph IR"; }
717 };
718
719} // end anonymous namespace.
720
721char PrintCallGraphPass::ID = 0;
722
724 const std::string &Banner) const {
725 return new PrintCallGraphPass(Banner, OS);
726}
727
728static std::string getDescription(const CallGraphSCC &SCC) {
729 std::string Desc = "SCC (";
730 ListSeparator LS;
731 for (CallGraphNode *CGN : SCC) {
732 Desc += LS;
733 Function *F = CGN->getFunction();
734 if (F)
735 Desc += F->getName();
736 else
737 Desc += "<<null function>>";
738 }
739 Desc += ")";
740 return Desc;
741}
742
744 OptPassGate &Gate =
745 SCC.getCallGraph().getModule().getContext().getOptPassGate();
746 return Gate.isEnabled() &&
747 !Gate.shouldRunPass(this->getPassName(), getDescription(SCC));
748}
749
750char DummyCGSCCPass::ID = 0;
751
752INITIALIZE_PASS(DummyCGSCCPass, "DummyCGSCCPass", "DummyCGSCCPass", false,
753 false)
amdgpu Simplify well known AMD library false FunctionCallee Callee
for(auto &MBB :MF)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
static std::string getDescription(const CallGraphSCC &SCC)
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
static unsigned InstrCount
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
This file declares the interface for bisecting optimizations.
#define P(N)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
This header defines classes/functions to handle pass execution timing information with interfaces for...
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
A node in the call graph for a module.
Definition: CallGraph.h:166
void print(raw_ostream &OS) const
Definition: CallGraph.cpp:184
iterator begin()
Definition: CallGraph.h:199
void addCalledFunction(CallBase *Call, CallGraphNode *M)
Adds a function to the list of functions called by this one.
Definition: CallGraph.h:242
void replaceCallEdge(CallBase &Call, CallBase &NewCall, CallGraphNode *NewNode)
Replaces the edge in the node for the specified call site with a new one.
Definition: CallGraph.cpp:257
void dump() const
Print out this call graph node.
Definition: CallGraph.cpp:203
iterator end()
Definition: CallGraph.h:200
Function * getFunction() const
Returns the function that this call graph node represents.
Definition: CallGraph.h:197
std::vector< CallRecord >::iterator iterator
Definition: CallGraph.h:193
void removeCallEdge(iterator I)
Definition: CallGraph.h:249
Pass * createPrinterPass(raw_ostream &OS, const std::string &Banner) const override
createPrinterPass - Get a pass that prints the Module corresponding to a CallGraph.
virtual bool runOnSCC(CallGraphSCC &SCC)=0
runOnSCC - This method should be implemented by the subclass to perform whatever action is necessary ...
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph.
bool skipSCC(CallGraphSCC &SCC) const
Optional passes call this function to check whether the pass should be skipped.
void assignPassManager(PMStack &PMS, PassManagerType PMT) override
Assign pass manager to manager this pass.
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
std::vector< CallGraphNode * >::const_iterator iterator
void ReplaceNode(CallGraphNode *Old, CallGraphNode *New)
ReplaceNode - This informs the SCC and the pass manager that the specified Old node has been deleted,...
void DeleteNode(CallGraphNode *Old)
DeleteNode - This informs the SCC and the pass manager that the specified Old node has been deleted.
unsigned size() const
iterator begin() const
iterator end() const
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:345
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:72
CallGraphNode * getOrInsertFunction(const Function *F)
Similar to operator[], but this will insert a new CallGraphNode for F if one does not already exist.
Definition: CallGraph.cpp:170
CallGraphNode * getCallsExternalNode() const
Definition: CallGraph.h:129
Module & getModule() const
Returns the module the call graph corresponds to.
Definition: CallGraph.h:101
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
bool erase(const KeyT &Val)
Definition: DenseMap.h:329
bool empty() const
Definition: DenseMap.h:98
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:151
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
This pass is required by interprocedural register allocation.
FPPassManager manages BBPassManagers and FunctionPasses.
bool runOnFunction(Function &F)
run - Execute all of the passes scheduled for execution.
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:251
virtual bool runOnModule(Module &M)=0
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
Extensions to this class implement mechanisms to disable passes and individual optimizations at compi...
Definition: OptBisect.h:26
virtual bool isEnabled() const
isEnabled() should return true before calling shouldRunPass().
Definition: OptBisect.h:38
virtual bool shouldRunPass(const StringRef PassName, StringRef IRDescription)
IRDescription is a textual description of the IR unit the pass is running over.
Definition: OptBisect.h:32
PMDataManager provides the common place to manage the analysis data used by pass managers.
void dumpLastUses(Pass *P, unsigned Offset) const
virtual Pass * getAsPass()=0
PMTopLevelManager * getTopLevelManager()
unsigned getNumContainedPasses() const
virtual PassManagerType getPassManagerType() const
PMStack - This class implements a stack data structure of PMDataManager pointers.
PMDataManager * top() const
bool empty() const
void push(PMDataManager *PM)
PMTopLevelManager manages LastUser info and collects common APIs used by top level pass managers.
void addIndirectPassManager(PMDataManager *Manager)
void schedulePass(Pass *P)
Schedule pass P for execution.
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
virtual PMDataManager * getAsPMDataManager()
Definition: Pass.cpp:118
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: Pass.h:119
virtual bool doFinalization(Module &)
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
Definition: Pass.h:123
virtual void dumpPassStructure(unsigned Offset=0)
Definition: Pass.cpp:74
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition: StringMap.h:111
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
The TimeRegion class is used as a helper class to call the startTimer() and stopTimer() methods of th...
Definition: Timer.h:143
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:642
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:49
bool isAtEnd() const
Direct loop termination test which is more efficient than comparison with end().
Definition: SCCIterator.h:113
void ReplaceNode(NodeRef Old, NodeRef New)
This informs the scc_iterator that the specified Old node has been deleted, and New is to be used in ...
Definition: SCCIterator.h:140
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ ReallyHidden
Definition: CommandLine.h:139
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
constexpr double e
Definition: MathExtras.h:31
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:406
bool forcePrintModuleIR()
PassManagerType
Different types of internal pass managers.
Definition: Pass.h:55
@ PMT_CallGraphPassManager
CGPassManager.
Definition: Pass.h:58
@ PMT_FunctionPassManager
FPPassManager.
Definition: Pass.h:59
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:233
Timer * getPassTimer(Pass *)
Request the timer for this legacy-pass-manager's pass instance.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool isFunctionInPrintList(StringRef FunctionName)
@ MODIFICATION_MSG
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void forEachCallbackFunction(const CallBase &CB, UnaryFunction Func)
Apply function Func to each CB's callback function.
cl::opt< unsigned > MaxDevirtIterations("max-devirt-iterations", cl::ReallyHidden, cl::init(4))
#define N