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