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"
25 #include "llvm/IR/Intrinsics.h"
26 #include "llvm/IR/LLVMContext.h"
28 #include "llvm/IR/Module.h"
29 #include "llvm/IR/OptBisect.h"
30 #include "llvm/IR/PassTimingInfo.h"
31 #include "llvm/Pass.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/Timer.h"
36 #include <cassert>
37 #include <string>
38 #include <utility>
39 #include <vector>
40 
41 using namespace llvm;
42 
43 #define DEBUG_TYPE "cgscc-passmgr"
44 
45 static cl::opt<unsigned>
46 MaxIterations("max-cg-scc-iterations", cl::ReallyHidden, cl::init(4));
47 
48 STATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC");
49 
50 //===----------------------------------------------------------------------===//
51 // CGPassManager
52 //
53 /// CGPassManager manages FPPassManagers and CallGraphSCCPasses.
54 
55 namespace {
56 
57 class CGPassManager : public ModulePass, public PMDataManager {
58 public:
59  static char ID;
60 
61  explicit CGPassManager() : ModulePass(ID), PMDataManager() {}
62 
63  /// Execute all of the passes scheduled for execution. Keep track of
64  /// whether any of the passes modifies the module, and if so, return true.
65  bool runOnModule(Module &M) override;
66 
69 
70  bool doInitialization(CallGraph &CG);
71  bool doFinalization(CallGraph &CG);
72 
73  /// Pass Manager itself does not invalidate any analysis info.
74  void getAnalysisUsage(AnalysisUsage &Info) const override {
75  // CGPassManager walks SCC and it needs CallGraph.
77  Info.setPreservesAll();
78  }
79 
80  StringRef getPassName() const override { return "CallGraph Pass Manager"; }
81 
82  PMDataManager *getAsPMDataManager() override { return this; }
83  Pass *getAsPass() override { return this; }
84 
85  // Print passes managed by this manager
86  void dumpPassStructure(unsigned Offset) override {
87  errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n";
88  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
89  Pass *P = getContainedPass(Index);
90  P->dumpPassStructure(Offset + 1);
91  dumpLastUses(P, Offset+1);
92  }
93  }
94 
95  Pass *getContainedPass(unsigned N) {
96  assert(N < PassVector.size() && "Pass number out of range!");
97  return static_cast<Pass *>(PassVector[N]);
98  }
99 
100  PassManagerType getPassManagerType() const override {
102  }
103 
104 private:
105  bool RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
106  bool &DevirtualizedCall);
107 
108  bool RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
109  CallGraph &CG, bool &CallGraphUpToDate,
110  bool &DevirtualizedCall);
111  bool RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
112  bool IsCheckingMode);
113 };
114 
115 } // end anonymous namespace.
116 
117 char CGPassManager::ID = 0;
118 
119 bool CGPassManager::RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
120  CallGraph &CG, bool &CallGraphUpToDate,
121  bool &DevirtualizedCall) {
122  bool Changed = false;
124  Module &M = CG.getModule();
125 
126  if (!PM) {
127  CallGraphSCCPass *CGSP = (CallGraphSCCPass *)P;
128  if (!CallGraphUpToDate) {
129  DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
130  CallGraphUpToDate = true;
131  }
132 
133  {
134  unsigned InstrCount, SCCCount = 0;
135  StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
136  bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
137  TimeRegion PassTimer(getPassTimer(CGSP));
138  if (EmitICRemark)
139  InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
140  Changed = CGSP->runOnSCC(CurSCC);
141 
142  if (EmitICRemark) {
143  // FIXME: Add getInstructionCount to CallGraphSCC.
144  SCCCount = M.getInstructionCount();
145  // Is there a difference in the number of instructions in the module?
146  if (SCCCount != InstrCount) {
147  // Yep. Emit a remark and update InstrCount.
148  int64_t Delta =
149  static_cast<int64_t>(SCCCount) - static_cast<int64_t>(InstrCount);
150  emitInstrCountChangedRemark(P, M, Delta, InstrCount,
151  FunctionToInstrCount);
152  InstrCount = SCCCount;
153  }
154  }
155  }
156 
157  // After the CGSCCPass is done, when assertions are enabled, use
158  // RefreshCallGraph to verify that the callgraph was correctly updated.
159 #ifndef NDEBUG
160  if (Changed)
161  RefreshCallGraph(CurSCC, CG, true);
162 #endif
163 
164  return Changed;
165  }
166 
168  "Invalid CGPassManager member");
169  FPPassManager *FPP = (FPPassManager*)P;
170 
171  // Run pass P on all functions in the current SCC.
172  for (CallGraphNode *CGN : CurSCC) {
173  if (Function *F = CGN->getFunction()) {
174  dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
175  {
176  TimeRegion PassTimer(getPassTimer(FPP));
177  Changed |= FPP->runOnFunction(*F);
178  }
179  F->getContext().yield();
180  }
181  }
182 
183  // The function pass(es) modified the IR, they may have clobbered the
184  // callgraph.
185  if (Changed && CallGraphUpToDate) {
186  LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: " << P->getPassName()
187  << '\n');
188  CallGraphUpToDate = false;
189  }
190  return Changed;
191 }
192 
193 /// Scan the functions in the specified CFG and resync the
194 /// callgraph with the call sites found in it. This is used after
195 /// FunctionPasses have potentially munged the callgraph, and can be used after
196 /// CallGraphSCC passes to verify that they correctly updated the callgraph.
197 ///
198 /// This function returns true if it devirtualized an existing function call,
199 /// meaning it turned an indirect call into a direct call. This happens when
200 /// a function pass like GVN optimizes away stuff feeding the indirect call.
201 /// This never happens in checking mode.
202 bool CGPassManager::RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
203  bool CheckingMode) {
205 
206  LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()
207  << " nodes:\n";
208  for (CallGraphNode *CGN
209  : CurSCC) CGN->dump(););
210 
211  bool MadeChange = false;
212  bool DevirtualizedCall = false;
213 
214  // Scan all functions in the SCC.
215  unsigned FunctionNo = 0;
216  for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end();
217  SCCIdx != E; ++SCCIdx, ++FunctionNo) {
218  CallGraphNode *CGN = *SCCIdx;
219  Function *F = CGN->getFunction();
220  if (!F || F->isDeclaration()) continue;
221 
222  // Walk the function body looking for call sites. Sync up the call sites in
223  // CGN with those actually in the function.
224 
225  // Keep track of the number of direct and indirect calls that were
226  // invalidated and removed.
227  unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
228 
229  // Get the set of call sites currently in the function.
230  for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) {
231  // If this call site is null, then the function pass deleted the call
232  // entirely and the WeakTrackingVH nulled it out.
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  CallSites.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  !CallSite(I->first) ||
244  (CallSite(I->first).getCalledFunction() &&
245  CallSite(I->first).getCalledFunction()->isIntrinsic() &&
247  CallSite(I->first).getCalledFunction()->getIntrinsicID()))) {
248  assert(!CheckingMode &&
249  "CallGraphSCCPass did not update the CallGraph correctly!");
250 
251  // If this was an indirect call site, count it.
252  if (!I->second->getFunction())
253  ++NumIndirectRemoved;
254  else
255  ++NumDirectRemoved;
256 
257  // Just remove the edge from the set of callees, keep track of whether
258  // I points to the last element of the vector.
259  bool WasLast = I + 1 == E;
260  CGN->removeCallEdge(I);
261 
262  // If I pointed to the last element of the vector, we have to bail out:
263  // iterator checking rejects comparisons of the resultant pointer with
264  // end.
265  if (WasLast)
266  break;
267  E = CGN->end();
268  continue;
269  }
270 
271  assert(!CallSites.count(I->first) &&
272  "Call site occurs in node multiple times");
273 
274  CallSite CS(I->first);
275  if (CS) {
276  Function *Callee = CS.getCalledFunction();
277  // Ignore intrinsics because they're not really function calls.
278  if (!Callee || !(Callee->isIntrinsic()))
279  CallSites.insert(std::make_pair(I->first, I->second));
280  }
281  ++I;
282  }
283 
284  // Loop over all of the instructions in the function, getting the callsites.
285  // Keep track of the number of direct/indirect calls added.
286  unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
287 
288  for (BasicBlock &BB : *F)
289  for (Instruction &I : BB) {
290  CallSite CS(&I);
291  if (!CS) continue;
292  Function *Callee = CS.getCalledFunction();
293  if (Callee && Callee->isIntrinsic()) continue;
294 
295  // If this call site already existed in the callgraph, just verify it
296  // matches up to expectations and remove it from CallSites.
298  CallSites.find(CS.getInstruction());
299  if (ExistingIt != CallSites.end()) {
300  CallGraphNode *ExistingNode = ExistingIt->second;
301 
302  // Remove from CallSites since we have now seen it.
303  CallSites.erase(ExistingIt);
304 
305  // Verify that the callee is right.
306  if (ExistingNode->getFunction() == CS.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 && CS.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 = CS.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(CS, CS, 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 = CS.getCalledFunction()) {
349  CalleeNode = CG.getOrInsertFunction(Callee);
350  ++NumDirectAdded;
351  } else {
352  CalleeNode = CG.getCallsExternalNode();
353  ++NumIndirectAdded;
354  }
355 
356  CGN->addCalledFunction(CS, 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(CallSites.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  CallSites.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  for (CallGraphNode *CGN : SCC) {
642  if (Function *F = CGN->getFunction()) {
643  if (!F->isDeclaration() && isFunctionInPrintList(F->getName())) {
644  PrintBannerOnce();
645  F->print(OS);
646  }
647  } else if (isFunctionInPrintList("*")) {
648  PrintBannerOnce();
649  OS << "\nPrinting <null> Function\n";
650  }
651  }
652  return false;
653  }
654 
655  StringRef getPassName() const override { return "Print CallGraph IR"; }
656  };
657 
658 } // end anonymous namespace.
659 
660 char PrintCallGraphPass::ID = 0;
661 
663  const std::string &Banner) const {
664  return new PrintCallGraphPass(Banner, OS);
665 }
666 
668  return !SCC.getCallGraph().getModule()
669  .getContext()
670  .getOptPassGate()
671  .shouldRunPass(this, SCC);
672 }
673 
674 char DummyCGSCCPass::ID = 0;
675 
676 INITIALIZE_PASS(DummyCGSCCPass, "DummyCGSCCPass", "DummyCGSCCPass", false,
677  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
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
Compute iterated dominance frontiers using a linear time algorithm.
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:63
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 *)
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:191
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:242
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:232
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:469
const CallGraph & getCallGraph()
This header defines classes/functions to handle pass execution timing information with an interface s...
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:183
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:410
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:59
bool shouldEmitInstrCountChangedRemark()
Return true if size-info optimization remark is enabled, false otherwise.
Definition: Module.h:261
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
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:224
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:141
void push(PMDataManager *PM)
PMDataManager provides the common place to manage the analysis data used by pass managers.
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:150
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