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