LLVM  10.0.0svn
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  // If this call site is null, then the function pass deleted the call
231  // entirely and the WeakTrackingVH nulled it out.
232  auto *Call = dyn_cast_or_null<CallBase>(I->first);
233  if (!I->first ||
234  // If we've already seen this call site, then the FunctionPass RAUW'd
235  // one call with another, which resulted in two "uses" in the edge
236  // list of the same call.
237  Calls.count(I->first) ||
238 
239  // If the call edge is not from a call or invoke, or it is a
240  // instrinsic call, then the function pass RAUW'd a call with
241  // another value. This can happen when constant folding happens
242  // of well known functions etc.
243  !Call ||
244  (Call->getCalledFunction() &&
245  Call->getCalledFunction()->isIntrinsic() &&
246  Intrinsic::isLeaf(Call->getCalledFunction()->getIntrinsicID()))) {
247  assert(!CheckingMode &&
248  "CallGraphSCCPass did not update the CallGraph correctly!");
249 
250  // If this was an indirect call site, count it.
251  if (!I->second->getFunction())
252  ++NumIndirectRemoved;
253  else
254  ++NumDirectRemoved;
255 
256  // Just remove the edge from the set of callees, keep track of whether
257  // I points to the last element of the vector.
258  bool WasLast = I + 1 == E;
259  CGN->removeCallEdge(I);
260 
261  // If I pointed to the last element of the vector, we have to bail out:
262  // iterator checking rejects comparisons of the resultant pointer with
263  // end.
264  if (WasLast)
265  break;
266  E = CGN->end();
267  continue;
268  }
269 
270  assert(!Calls.count(I->first) &&
271  "Call site occurs in node multiple times");
272 
273  if (Call) {
274  Function *Callee = Call->getCalledFunction();
275  // Ignore intrinsics because they're not really function calls.
276  if (!Callee || !(Callee->isIntrinsic()))
277  Calls.insert(std::make_pair(I->first, I->second));
278  }
279  ++I;
280  }
281 
282  // Loop over all of the instructions in the function, getting the callsites.
283  // Keep track of the number of direct/indirect calls added.
284  unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
285 
286  for (BasicBlock &BB : *F)
287  for (Instruction &I : BB) {
288  auto *Call = dyn_cast<CallBase>(&I);
289  if (!Call)
290  continue;
291  Function *Callee = Call->getCalledFunction();
292  if (Callee && Callee->isIntrinsic())
293  continue;
294 
295  // If this call site already existed in the callgraph, just verify it
296  // matches up to expectations and remove it from Calls.
298  Calls.find(Call);
299  if (ExistingIt != Calls.end()) {
300  CallGraphNode *ExistingNode = ExistingIt->second;
301 
302  // Remove from Calls since we have now seen it.
303  Calls.erase(ExistingIt);
304 
305  // Verify that the callee is right.
306  if (ExistingNode->getFunction() == Call->getCalledFunction())
307  continue;
308 
309  // If we are in checking mode, we are not allowed to actually mutate
310  // the callgraph. If this is a case where we can infer that the
311  // callgraph is less precise than it could be (e.g. an indirect call
312  // site could be turned direct), don't reject it in checking mode, and
313  // don't tweak it to be more precise.
314  if (CheckingMode && Call->getCalledFunction() &&
315  ExistingNode->getFunction() == nullptr)
316  continue;
317 
318  assert(!CheckingMode &&
319  "CallGraphSCCPass did not update the CallGraph correctly!");
320 
321  // If not, we either went from a direct call to indirect, indirect to
322  // direct, or direct to different direct.
323  CallGraphNode *CalleeNode;
324  if (Function *Callee = Call->getCalledFunction()) {
325  CalleeNode = CG.getOrInsertFunction(Callee);
326  // Keep track of whether we turned an indirect call into a direct
327  // one.
328  if (!ExistingNode->getFunction()) {
329  DevirtualizedCall = true;
330  LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Devirtualized call to '"
331  << Callee->getName() << "'\n");
332  }
333  } else {
334  CalleeNode = CG.getCallsExternalNode();
335  }
336 
337  // Update the edge target in CGN.
338  CGN->replaceCallEdge(*Call, *Call, CalleeNode);
339  MadeChange = true;
340  continue;
341  }
342 
343  assert(!CheckingMode &&
344  "CallGraphSCCPass did not update the CallGraph correctly!");
345 
346  // If the call site didn't exist in the CGN yet, add it.
347  CallGraphNode *CalleeNode;
348  if (Function *Callee = Call->getCalledFunction()) {
349  CalleeNode = CG.getOrInsertFunction(Callee);
350  ++NumDirectAdded;
351  } else {
352  CalleeNode = CG.getCallsExternalNode();
353  ++NumIndirectAdded;
354  }
355 
356  CGN->addCalledFunction(Call, CalleeNode);
357  MadeChange = true;
358  }
359 
360  // We scanned the old callgraph node, removing invalidated call sites and
361  // then added back newly found call sites. One thing that can happen is
362  // that an old indirect call site was deleted and replaced with a new direct
363  // call. In this case, we have devirtualized a call, and CGSCCPM would like
364  // to iteratively optimize the new code. Unfortunately, we don't really
365  // have a great way to detect when this happens. As an approximation, we
366  // just look at whether the number of indirect calls is reduced and the
367  // number of direct calls is increased. There are tons of ways to fool this
368  // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
369  // direct call) but this is close enough.
370  if (NumIndirectRemoved > NumIndirectAdded &&
371  NumDirectRemoved < NumDirectAdded)
372  DevirtualizedCall = true;
373 
374  // After scanning this function, if we still have entries in callsites, then
375  // they are dangling pointers. WeakTrackingVH should save us for this, so
376  // abort if
377  // this happens.
378  assert(Calls.empty() && "Dangling pointers found in call sites map");
379 
380  // Periodically do an explicit clear to remove tombstones when processing
381  // large scc's.
382  if ((FunctionNo & 15) == 15)
383  Calls.clear();
384  }
385 
386  LLVM_DEBUG(if (MadeChange) {
387  dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
388  for (CallGraphNode *CGN : CurSCC)
389  CGN->dump();
390  if (DevirtualizedCall)
391  dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
392  } else {
393  dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
394  });
395  (void)MadeChange;
396 
397  return DevirtualizedCall;
398 }
399 
400 /// Execute the body of the entire pass manager on the specified SCC.
401 /// This keeps track of whether a function pass devirtualizes
402 /// any calls and returns it in DevirtualizedCall.
403 bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
404  bool &DevirtualizedCall) {
405  bool Changed = false;
406 
407  // Keep track of whether the callgraph is known to be up-to-date or not.
408  // The CGSSC pass manager runs two types of passes:
409  // CallGraphSCC Passes and other random function passes. Because other
410  // random function passes are not CallGraph aware, they may clobber the
411  // call graph by introducing new calls or deleting other ones. This flag
412  // is set to false when we run a function pass so that we know to clean up
413  // the callgraph when we need to run a CGSCCPass again.
414  bool CallGraphUpToDate = true;
415 
416  // Run all passes on current SCC.
417  for (unsigned PassNo = 0, e = getNumContainedPasses();
418  PassNo != e; ++PassNo) {
419  Pass *P = getContainedPass(PassNo);
420 
421  // If we're in -debug-pass=Executions mode, construct the SCC node list,
422  // otherwise avoid constructing this string as it is expensive.
423  if (isPassDebuggingExecutionsOrMore()) {
424  std::string Functions;
425  #ifndef NDEBUG
426  raw_string_ostream OS(Functions);
427  for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
428  I != E; ++I) {
429  if (I != CurSCC.begin()) OS << ", ";
430  (*I)->print(OS);
431  }
432  OS.flush();
433  #endif
434  dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
435  }
436  dumpRequiredSet(P);
437 
438  initializeAnalysisImpl(P);
439 
440  // Actually run this pass on the current SCC.
441  Changed |= RunPassOnSCC(P, CurSCC, CG,
442  CallGraphUpToDate, DevirtualizedCall);
443 
444  if (Changed)
445  dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
446  dumpPreservedSet(P);
447 
448  verifyPreservedAnalysis(P);
449  removeNotPreservedAnalysis(P);
450  recordAvailableAnalysis(P);
451  removeDeadPasses(P, "", ON_CG_MSG);
452  }
453 
454  // If the callgraph was left out of date (because the last pass run was a
455  // functionpass), refresh it before we move on to the next SCC.
456  if (!CallGraphUpToDate)
457  DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
458  return Changed;
459 }
460 
461 /// Execute all of the passes scheduled for execution. Keep track of
462 /// whether any of the passes modifies the module, and if so, return true.
463 bool CGPassManager::runOnModule(Module &M) {
464  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
465  bool Changed = doInitialization(CG);
466 
467  // Walk the callgraph in bottom-up SCC order.
469 
470  CallGraphSCC CurSCC(CG, &CGI);
471  while (!CGI.isAtEnd()) {
472  // Copy the current SCC and increment past it so that the pass can hack
473  // on the SCC if it wants to without invalidating our iterator.
474  const std::vector<CallGraphNode *> &NodeVec = *CGI;
475  CurSCC.initialize(NodeVec);
476  ++CGI;
477 
478  // At the top level, we run all the passes in this pass manager on the
479  // functions in this SCC. However, we support iterative compilation in the
480  // case where a function pass devirtualizes a call to a function. For
481  // example, it is very common for a function pass (often GVN or instcombine)
482  // to eliminate the addressing that feeds into a call. With that improved
483  // information, we would like the call to be an inline candidate, infer
484  // mod-ref information etc.
485  //
486  // Because of this, we allow iteration up to a specified iteration count.
487  // This only happens in the case of a devirtualized call, so we only burn
488  // compile time in the case that we're making progress. We also have a hard
489  // iteration count limit in case there is crazy code.
490  unsigned Iteration = 0;
491  bool DevirtualizedCall = false;
492  do {
493  LLVM_DEBUG(if (Iteration) dbgs()
494  << " SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration
495  << '\n');
496  DevirtualizedCall = false;
497  Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
498  } while (Iteration++ < MaxIterations && DevirtualizedCall);
499 
500  if (DevirtualizedCall)
501  LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after "
502  << Iteration
503  << " times, due to -max-cg-scc-iterations\n");
504 
505  MaxSCCIterations.updateMax(Iteration);
506  }
507  Changed |= doFinalization(CG);
508  return Changed;
509 }
510 
511 /// Initialize CG
512 bool CGPassManager::doInitialization(CallGraph &CG) {
513  bool Changed = false;
514  for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
515  if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
517  "Invalid CGPassManager member");
518  Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
519  } else {
520  Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
521  }
522  }
523  return Changed;
524 }
525 
526 /// Finalize CG
527 bool CGPassManager::doFinalization(CallGraph &CG) {
528  bool Changed = false;
529  for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
530  if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
532  "Invalid CGPassManager member");
533  Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());
534  } else {
535  Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
536  }
537  }
538  return Changed;
539 }
540 
541 //===----------------------------------------------------------------------===//
542 // CallGraphSCC Implementation
543 //===----------------------------------------------------------------------===//
544 
545 /// This informs the SCC and the pass manager that the specified
546 /// Old node has been deleted, and New is to be used in its place.
548  assert(Old != New && "Should not replace node with self");
549  for (unsigned i = 0; ; ++i) {
550  assert(i != Nodes.size() && "Node not in SCC");
551  if (Nodes[i] != Old) continue;
552  Nodes[i] = New;
553  break;
554  }
555 
556  // Update the active scc_iterator so that it doesn't contain dangling
557  // pointers to the old CallGraphNode.
559  CGI->ReplaceNode(Old, New);
560 }
561 
562 //===----------------------------------------------------------------------===//
563 // CallGraphSCCPass Implementation
564 //===----------------------------------------------------------------------===//
565 
566 /// Assign pass manager to manage this pass.
568  PassManagerType PreferredType) {
569  // Find CGPassManager
570  while (!PMS.empty() &&
572  PMS.pop();
573 
574  assert(!PMS.empty() && "Unable to handle Call Graph Pass");
575  CGPassManager *CGP;
576 
578  CGP = (CGPassManager*)PMS.top();
579  else {
580  // Create new Call Graph SCC Pass Manager if it does not exist.
581  assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");
582  PMDataManager *PMD = PMS.top();
583 
584  // [1] Create new Call Graph Pass Manager
585  CGP = new CGPassManager();
586 
587  // [2] Set up new manager's top level manager
588  PMTopLevelManager *TPM = PMD->getTopLevelManager();
589  TPM->addIndirectPassManager(CGP);
590 
591  // [3] Assign manager to manage this new manager. This may create
592  // and push new managers into PMS
593  Pass *P = CGP;
594  TPM->schedulePass(P);
595 
596  // [4] Push new manager into PMS
597  PMS.push(CGP);
598  }
599 
600  CGP->add(this);
601 }
602 
603 /// For this class, we declare that we require and preserve the call graph.
604 /// If the derived class implements this method, it should
605 /// always explicitly call the implementation here.
609 }
610 
611 //===----------------------------------------------------------------------===//
612 // PrintCallGraphPass Implementation
613 //===----------------------------------------------------------------------===//
614 
615 namespace {
616 
617  /// PrintCallGraphPass - Print a Module corresponding to a call graph.
618  ///
619  class PrintCallGraphPass : public CallGraphSCCPass {
620  std::string Banner;
621  raw_ostream &OS; // raw_ostream to print on.
622 
623  public:
624  static char ID;
625 
626  PrintCallGraphPass(const std::string &B, raw_ostream &OS)
627  : CallGraphSCCPass(ID), Banner(B), OS(OS) {}
628 
629  void getAnalysisUsage(AnalysisUsage &AU) const override {
630  AU.setPreservesAll();
631  }
632 
633  bool runOnSCC(CallGraphSCC &SCC) override {
634  bool BannerPrinted = false;
635  auto PrintBannerOnce = [&]() {
636  if (BannerPrinted)
637  return;
638  OS << Banner;
639  BannerPrinted = true;
640  };
641 
642  bool NeedModule = llvm::forcePrintModuleIR();
643  if (isFunctionInPrintList("*") && NeedModule) {
644  PrintBannerOnce();
645  OS << "\n";
646  SCC.getCallGraph().getModule().print(OS, nullptr);
647  return false;
648  }
649  bool FoundFunction = false;
650  for (CallGraphNode *CGN : SCC) {
651  if (Function *F = CGN->getFunction()) {
652  if (!F->isDeclaration() && isFunctionInPrintList(F->getName())) {
653  FoundFunction = true;
654  if (!NeedModule) {
655  PrintBannerOnce();
656  F->print(OS);
657  }
658  }
659  } else if (isFunctionInPrintList("*")) {
660  PrintBannerOnce();
661  OS << "\nPrinting <null> Function\n";
662  }
663  }
664  if (NeedModule && FoundFunction) {
665  PrintBannerOnce();
666  OS << "\n";
667  SCC.getCallGraph().getModule().print(OS, nullptr);
668  }
669  return false;
670  }
671 
672  StringRef getPassName() const override { return "Print CallGraph IR"; }
673  };
674 
675 } // end anonymous namespace.
676 
677 char PrintCallGraphPass::ID = 0;
678 
680  const std::string &Banner) const {
681  return new PrintCallGraphPass(Banner, OS);
682 }
683 
684 static std::string getDescription(const CallGraphSCC &SCC) {
685  std::string Desc = "SCC (";
686  bool First = true;
687  for (CallGraphNode *CGN : SCC) {
688  if (First)
689  First = false;
690  else
691  Desc += ", ";
692  Function *F = CGN->getFunction();
693  if (F)
694  Desc += F->getName();
695  else
696  Desc += "<<null function>>";
697  }
698  Desc += ")";
699  return Desc;
700 }
701 
703  OptPassGate &Gate =
705  return Gate.isEnabled() && !Gate.shouldRunPass(this, getDescription(SCC));
706 }
707 
708 char DummyCGSCCPass::ID = 0;
709 
710 INITIALIZE_PASS(DummyCGSCCPass, "DummyCGSCCPass", "DummyCGSCCPass", false,
711  false)
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
bool isIntrinsic() const
isIntrinsic - Returns true if the function&#39;s name starts with "llvm.".
Definition: Function.h:198
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:53
bool forcePrintModuleIR()
forcePrintModuleIR - returns true if IR printing passes should
CGPassManager.
Definition: Pass.h:56
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
LLVMContext & Context
This class represents lattice values for constants.
Definition: AllocatorList.h:23
virtual PMDataManager * getAsPMDataManager()
Definition: Pass.cpp:116
virtual void dumpPassStructure(unsigned Offset=0)
Definition: Pass.cpp:72
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:66
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:79
A node in the call graph for a module.
Definition: CallGraph.h:164
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:113
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:195
void schedulePass(Pass *P)
Schedule pass P for execution.
AnalysisUsage & addRequired()
iterator end()
Definition: CallGraph.h:190
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:245
virtual bool doFinalization(Module &)
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
Definition: Pass.h:109
unsigned getInstructionCount()
Returns the number of non-debug IR instructions in the module.
Definition: Module.cpp:475
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:225
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:180
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:20
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: Pass.h:105
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:432
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:324
bool isLeaf(ID id)
Returns true if the intrinsic is a leaf, i.e.
Definition: Function.cpp:1076
CallGraphNode * getCallsExternalNode() const
Definition: CallGraph.h:138
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
bool shouldEmitInstrCountChangedRemark()
Return true if size-info optimization remark is enabled, false otherwise.
Definition: Module.h:264
void addIndirectPassManager(PMDataManager *Manager)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
virtual PassManagerType getPassManagerType() const
Represent the analysis usage information of a pass.
constexpr double e
Definition: MathExtras.h:57
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:33
Function * getFunction() const
Returns the function that this call graph node represents.
Definition: CallGraph.h:187
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:4196
FPPassManager.
Definition: Pass.h:57
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:242
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:240
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:229
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
std::vector< CallGraphNode * >::const_iterator iterator
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
std::vector< CallRecord >::iterator iterator
Definition: CallGraph.h:183
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:231
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:503
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:147
bool empty() const
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
iterator begin()
Definition: CallGraph.h:189
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
#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:232
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:42