LLVM 19.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"
24#include "llvm/IR/Function.h"
25#include "llvm/IR/Intrinsics.h"
26#include "llvm/IR/LLVMContext.h"
28#include "llvm/IR/Module.h"
29#include "llvm/IR/OptBisect.h"
31#include "llvm/IR/PrintPasses.h"
32#include "llvm/Pass.h"
34#include "llvm/Support/Debug.h"
35#include "llvm/Support/Timer.h"
37#include <cassert>
38#include <string>
39#include <utility>
40#include <vector>
41
42using namespace llvm;
43
44#define DEBUG_TYPE "cgscc-passmgr"
45
46namespace llvm {
48 cl::init(4));
49}
50
51STATISTIC(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) {}
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
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);
95 }
96 }
97
98 Pass *getContainedPass(unsigned N) {
99 assert(N < PassVector.size() && "Pass number out of range!");
100 return static_cast<Pass *>(PassVector[N]);
101 }
102
103 PassManagerType getPassManagerType() const override {
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) {
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;
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 NDEBUG
163 if (Changed)
164 RefreshCallGraph(CurSCC, CG, true);
165#endif
166
167 return Changed;
168 }
169
171 "Invalid CGPassManager member");
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()
190 << '\n');
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) {
208
209 LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()
210 << " nodes:\n";
211 for (CallGraphNode *CGN
212 : CurSCC) CGN->dump(););
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 assert(!CheckingMode &&
273 "CallGraphSCCPass did not update the CallGraph correctly!");
274
275 // If this was an indirect call site, count it.
276 if (!I->second->getFunction())
277 ++NumIndirectRemoved;
278 else
279 ++NumDirectRemoved;
280
281 if (RemoveAndCheckForDone(I))
282 break;
283 continue;
284 }
285
286 assert(!Calls.count(Call) && "Call site occurs in node multiple times");
287
288 if (Call) {
289 Function *Callee = Call->getCalledFunction();
290 // Ignore intrinsics because they're not really function calls.
291 if (!Callee || !(Callee->isIntrinsic()))
292 Calls.insert(std::make_pair(Call, I->second));
293 }
294 ++I;
295 }
296
297 // Loop over all of the instructions in the function, getting the callsites.
298 // Keep track of the number of direct/indirect calls added.
299 unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
300
301 for (BasicBlock &BB : *F)
302 for (Instruction &I : BB) {
303 auto *Call = dyn_cast<CallBase>(&I);
304 if (!Call)
305 continue;
306 Function *Callee = Call->getCalledFunction();
307 if (Callee && Callee->isIntrinsic())
308 continue;
309
310 // If we are not in checking mode, insert potential callback calls as
311 // references. This is not a requirement but helps to iterate over the
312 // functions in the right order.
313 if (!CheckingMode) {
314 forEachCallbackFunction(*Call, [&](Function *CB) {
315 CGN->addCalledFunction(nullptr, CG.getOrInsertFunction(CB));
316 });
317 }
318
319 // If this call site already existed in the callgraph, just verify it
320 // matches up to expectations and remove it from Calls.
322 Calls.find(Call);
323 if (ExistingIt != Calls.end()) {
324 CallGraphNode *ExistingNode = ExistingIt->second;
325
326 // Remove from Calls since we have now seen it.
327 Calls.erase(ExistingIt);
328
329 // Verify that the callee is right.
330 if (ExistingNode->getFunction() == Call->getCalledFunction())
331 continue;
332
333 // If we are in checking mode, we are not allowed to actually mutate
334 // the callgraph. If this is a case where we can infer that the
335 // callgraph is less precise than it could be (e.g. an indirect call
336 // site could be turned direct), don't reject it in checking mode, and
337 // don't tweak it to be more precise.
338 if (CheckingMode && Call->getCalledFunction() &&
339 ExistingNode->getFunction() == nullptr)
340 continue;
341
342 assert(!CheckingMode &&
343 "CallGraphSCCPass did not update the CallGraph correctly!");
344
345 // If not, we either went from a direct call to indirect, indirect to
346 // direct, or direct to different direct.
347 CallGraphNode *CalleeNode;
348 if (Function *Callee = Call->getCalledFunction()) {
349 CalleeNode = CG.getOrInsertFunction(Callee);
350 // Keep track of whether we turned an indirect call into a direct
351 // one.
352 if (!ExistingNode->getFunction()) {
353 DevirtualizedCall = true;
354 LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Devirtualized call to '"
355 << Callee->getName() << "'\n");
356 }
357 } else {
358 CalleeNode = CG.getCallsExternalNode();
359 }
360
361 // Update the edge target in CGN.
362 CGN->replaceCallEdge(*Call, *Call, CalleeNode);
363 MadeChange = true;
364 continue;
365 }
366
367 assert(!CheckingMode &&
368 "CallGraphSCCPass did not update the CallGraph correctly!");
369
370 // If the call site didn't exist in the CGN yet, add it.
371 CallGraphNode *CalleeNode;
372 if (Function *Callee = Call->getCalledFunction()) {
373 CalleeNode = CG.getOrInsertFunction(Callee);
374 ++NumDirectAdded;
375 } else {
376 CalleeNode = CG.getCallsExternalNode();
377 ++NumIndirectAdded;
378 }
379
380 CGN->addCalledFunction(Call, CalleeNode);
381 MadeChange = true;
382 }
383
384 // We scanned the old callgraph node, removing invalidated call sites and
385 // then added back newly found call sites. One thing that can happen is
386 // that an old indirect call site was deleted and replaced with a new direct
387 // call. In this case, we have devirtualized a call, and CGSCCPM would like
388 // to iteratively optimize the new code. Unfortunately, we don't really
389 // have a great way to detect when this happens. As an approximation, we
390 // just look at whether the number of indirect calls is reduced and the
391 // number of direct calls is increased. There are tons of ways to fool this
392 // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
393 // direct call) but this is close enough.
394 if (NumIndirectRemoved > NumIndirectAdded &&
395 NumDirectRemoved < NumDirectAdded)
396 DevirtualizedCall = true;
397
398 // After scanning this function, if we still have entries in callsites, then
399 // they are dangling pointers. WeakTrackingVH should save us for this, so
400 // abort if
401 // this happens.
402 assert(Calls.empty() && "Dangling pointers found in call sites map");
403
404 // Periodically do an explicit clear to remove tombstones when processing
405 // large scc's.
406 if ((FunctionNo & 15) == 15)
407 Calls.clear();
408 }
409
410 LLVM_DEBUG(if (MadeChange) {
411 dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
412 for (CallGraphNode *CGN : CurSCC)
413 CGN->dump();
414 if (DevirtualizedCall)
415 dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
416 } else {
417 dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
418 });
419 (void)MadeChange;
420
421 return DevirtualizedCall;
422}
423
424/// Execute the body of the entire pass manager on the specified SCC.
425/// This keeps track of whether a function pass devirtualizes
426/// any calls and returns it in DevirtualizedCall.
427bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
428 bool &DevirtualizedCall) {
429 bool Changed = false;
430
431 // Keep track of whether the callgraph is known to be up-to-date or not.
432 // The CGSSC pass manager runs two types of passes:
433 // CallGraphSCC Passes and other random function passes. Because other
434 // random function passes are not CallGraph aware, they may clobber the
435 // call graph by introducing new calls or deleting other ones. This flag
436 // is set to false when we run a function pass so that we know to clean up
437 // the callgraph when we need to run a CGSCCPass again.
438 bool CallGraphUpToDate = true;
439
440 // Run all passes on current SCC.
441 for (unsigned PassNo = 0, e = getNumContainedPasses();
442 PassNo != e; ++PassNo) {
443 Pass *P = getContainedPass(PassNo);
444
445 // If we're in -debug-pass=Executions mode, construct the SCC node list,
446 // otherwise avoid constructing this string as it is expensive.
447 if (isPassDebuggingExecutionsOrMore()) {
448 std::string Functions;
449 #ifndef NDEBUG
450 raw_string_ostream OS(Functions);
451 ListSeparator LS;
452 for (const CallGraphNode *CGN : CurSCC) {
453 OS << LS;
454 CGN->print(OS);
455 }
456 OS.flush();
457 #endif
458 dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
459 }
460 dumpRequiredSet(P);
461
462 initializeAnalysisImpl(P);
463
464#ifdef EXPENSIVE_CHECKS
465 uint64_t RefHash = P->structuralHash(CG.getModule());
466#endif
467
468 // Actually run this pass on the current SCC.
469 bool LocalChanged =
470 RunPassOnSCC(P, CurSCC, CG, CallGraphUpToDate, DevirtualizedCall);
471
472 Changed |= LocalChanged;
473
474#ifdef EXPENSIVE_CHECKS
475 if (!LocalChanged && (RefHash != P->structuralHash(CG.getModule()))) {
476 llvm::errs() << "Pass modifies its input and doesn't report it: "
477 << P->getPassName() << "\n";
478 llvm_unreachable("Pass modifies its input and doesn't report it");
479 }
480#endif
481 if (LocalChanged)
482 dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
483 dumpPreservedSet(P);
484
485 verifyPreservedAnalysis(P);
486 if (LocalChanged)
487 removeNotPreservedAnalysis(P);
488 recordAvailableAnalysis(P);
489 removeDeadPasses(P, "", ON_CG_MSG);
490 }
491
492 // If the callgraph was left out of date (because the last pass run was a
493 // functionpass), refresh it before we move on to the next SCC.
494 if (!CallGraphUpToDate)
495 DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
496 return Changed;
497}
498
499/// Execute all of the passes scheduled for execution. Keep track of
500/// whether any of the passes modifies the module, and if so, return true.
501bool CGPassManager::runOnModule(Module &M) {
502 CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
503 bool Changed = doInitialization(CG);
504
505 // Walk the callgraph in bottom-up SCC order.
507
508 CallGraphSCC CurSCC(CG, &CGI);
509 while (!CGI.isAtEnd()) {
510 // Copy the current SCC and increment past it so that the pass can hack
511 // on the SCC if it wants to without invalidating our iterator.
512 const std::vector<CallGraphNode *> &NodeVec = *CGI;
513 CurSCC.initialize(NodeVec);
514 ++CGI;
515
516 // At the top level, we run all the passes in this pass manager on the
517 // functions in this SCC. However, we support iterative compilation in the
518 // case where a function pass devirtualizes a call to a function. For
519 // example, it is very common for a function pass (often GVN or instcombine)
520 // to eliminate the addressing that feeds into a call. With that improved
521 // information, we would like the call to be an inline candidate, infer
522 // mod-ref information etc.
523 //
524 // Because of this, we allow iteration up to a specified iteration count.
525 // This only happens in the case of a devirtualized call, so we only burn
526 // compile time in the case that we're making progress. We also have a hard
527 // iteration count limit in case there is crazy code.
528 unsigned Iteration = 0;
529 bool DevirtualizedCall = false;
530 do {
531 LLVM_DEBUG(if (Iteration) dbgs()
532 << " SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration
533 << '\n');
534 DevirtualizedCall = false;
535 Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
536 } while (Iteration++ < MaxDevirtIterations && DevirtualizedCall);
537
538 if (DevirtualizedCall)
539 LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after "
540 << Iteration
541 << " times, due to -max-devirt-iterations\n");
542
543 MaxSCCIterations.updateMax(Iteration);
544 }
545 Changed |= doFinalization(CG);
546 return Changed;
547}
548
549/// Initialize CG
550bool CGPassManager::doInitialization(CallGraph &CG) {
551 bool Changed = false;
552 for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
553 if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
555 "Invalid CGPassManager member");
556 Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
557 } else {
558 Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
559 }
560 }
561 return Changed;
562}
563
564/// Finalize CG
565bool CGPassManager::doFinalization(CallGraph &CG) {
566 bool Changed = false;
567 for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
568 if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
570 "Invalid CGPassManager member");
571 Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());
572 } else {
573 Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
574 }
575 }
576 return Changed;
577}
578
579//===----------------------------------------------------------------------===//
580// CallGraphSCC Implementation
581//===----------------------------------------------------------------------===//
582
583/// This informs the SCC and the pass manager that the specified
584/// Old node has been deleted, and New is to be used in its place.
586 assert(Old != New && "Should not replace node with self");
587 for (unsigned i = 0; ; ++i) {
588 assert(i != Nodes.size() && "Node not in SCC");
589 if (Nodes[i] != Old) continue;
590 if (New)
591 Nodes[i] = New;
592 else
593 Nodes.erase(Nodes.begin() + i);
594 break;
595 }
596
597 // Update the active scc_iterator so that it doesn't contain dangling
598 // pointers to the old CallGraphNode.
600 CGI->ReplaceNode(Old, New);
601}
602
604 ReplaceNode(Old, /*New=*/nullptr);
605}
606
607//===----------------------------------------------------------------------===//
608// CallGraphSCCPass Implementation
609//===----------------------------------------------------------------------===//
610
611/// Assign pass manager to manage this pass.
613 PassManagerType PreferredType) {
614 // Find CGPassManager
615 while (!PMS.empty() &&
617 PMS.pop();
618
619 assert(!PMS.empty() && "Unable to handle Call Graph Pass");
620 CGPassManager *CGP;
621
623 CGP = (CGPassManager*)PMS.top();
624 else {
625 // Create new Call Graph SCC Pass Manager if it does not exist.
626 assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");
627 PMDataManager *PMD = PMS.top();
628
629 // [1] Create new Call Graph Pass Manager
630 CGP = new CGPassManager();
631
632 // [2] Set up new manager's top level manager
634 TPM->addIndirectPassManager(CGP);
635
636 // [3] Assign manager to manage this new manager. This may create
637 // and push new managers into PMS
638 Pass *P = CGP;
639 TPM->schedulePass(P);
640
641 // [4] Push new manager into PMS
642 PMS.push(CGP);
643 }
644
645 CGP->add(this);
646}
647
648/// For this class, we declare that we require and preserve the call graph.
649/// If the derived class implements this method, it should
650/// always explicitly call the implementation here.
654}
655
656//===----------------------------------------------------------------------===//
657// PrintCallGraphPass Implementation
658//===----------------------------------------------------------------------===//
659
660namespace {
661
662 /// PrintCallGraphPass - Print a Module corresponding to a call graph.
663 ///
664 class PrintCallGraphPass : public CallGraphSCCPass {
665 std::string Banner;
666 raw_ostream &OS; // raw_ostream to print on.
667
668 public:
669 static char ID;
670
671 PrintCallGraphPass(const std::string &B, raw_ostream &OS)
672 : CallGraphSCCPass(ID), Banner(B), OS(OS) {}
673
674 void getAnalysisUsage(AnalysisUsage &AU) const override {
675 AU.setPreservesAll();
676 }
677
678 bool runOnSCC(CallGraphSCC &SCC) override {
679 bool BannerPrinted = false;
680 auto PrintBannerOnce = [&]() {
681 if (BannerPrinted)
682 return;
683 OS << Banner;
684 BannerPrinted = true;
685 };
686
687 bool NeedModule = llvm::forcePrintModuleIR();
688 if (isFunctionInPrintList("*") && NeedModule) {
689 PrintBannerOnce();
690 OS << "\n";
691 SCC.getCallGraph().getModule().print(OS, nullptr);
692 return false;
693 }
694 bool FoundFunction = false;
695 for (CallGraphNode *CGN : SCC) {
696 if (Function *F = CGN->getFunction()) {
697 if (!F->isDeclaration() && isFunctionInPrintList(F->getName())) {
698 FoundFunction = true;
699 if (!NeedModule) {
700 PrintBannerOnce();
701 F->print(OS);
702 }
703 }
704 } else if (isFunctionInPrintList("*")) {
705 PrintBannerOnce();
706 OS << "\nPrinting <null> Function\n";
707 }
708 }
709 if (NeedModule && FoundFunction) {
710 PrintBannerOnce();
711 OS << "\n";
712 SCC.getCallGraph().getModule().print(OS, nullptr);
713 }
714 return false;
715 }
716
717 StringRef getPassName() const override { return "Print CallGraph IR"; }
718 };
719
720} // end anonymous namespace.
721
722char PrintCallGraphPass::ID = 0;
723
725 const std::string &Banner) const {
726 return new PrintCallGraphPass(Banner, OS);
727}
728
729static std::string getDescription(const CallGraphSCC &SCC) {
730 std::string Desc = "SCC (";
731 ListSeparator LS;
732 for (CallGraphNode *CGN : SCC) {
733 Desc += LS;
734 Function *F = CGN->getFunction();
735 if (F)
736 Desc += F->getName();
737 else
738 Desc += "<<null function>>";
739 }
740 Desc += ")";
741 return Desc;
742}
743
745 OptPassGate &Gate =
746 SCC.getCallGraph().getModule().getContext().getOptPassGate();
747 return Gate.isEnabled() &&
748 !Gate.shouldRunPass(this->getPassName(), getDescription(SCC));
749}
750
751char DummyCGSCCPass::ID = 0;
752
753INITIALIZE_PASS(DummyCGSCCPass, "DummyCGSCCPass", "DummyCGSCCPass", false,
754 false)
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-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
This file contains some functions that are useful when dealing with strings.
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:60
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:349
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:345
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:24
virtual bool isEnabled() const
isEnabled() should return true before calling shouldRunPass().
Definition: OptBisect.h:36
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:30
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:128
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:661
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:450
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:456
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
Op::Description Desc
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
Description of the encoding of one expression Op.