LLVM  7.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/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 {
100  return PMT_CallGraphPassManager;
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) {
127  if (!CallGraphUpToDate) {
128  DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
129  CallGraphUpToDate = true;
130  }
131 
132  {
133  TimeRegion PassTimer(getPassTimer(CGSP));
134  unsigned InstrCount = initSizeRemarkInfo(M);
135  Changed = CGSP->runOnSCC(CurSCC);
136 
137  // If the pass modified the module, it may have modified the instruction
138  // count of the module. Try emitting a remark.
139  emitInstrCountChangedRemark(P, M, InstrCount);
140  }
141 
142  // After the CGSCCPass is done, when assertions are enabled, use
143  // RefreshCallGraph to verify that the callgraph was correctly updated.
144 #ifndef NDEBUG
145  if (Changed)
146  RefreshCallGraph(CurSCC, CG, true);
147 #endif
148 
149  return Changed;
150  }
151 
153  "Invalid CGPassManager member");
154  FPPassManager *FPP = (FPPassManager*)P;
155 
156  // Run pass P on all functions in the current SCC.
157  for (CallGraphNode *CGN : CurSCC) {
158  if (Function *F = CGN->getFunction()) {
159  dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
160  {
161  TimeRegion PassTimer(getPassTimer(FPP));
162  Changed |= FPP->runOnFunction(*F);
163  }
164  F->getContext().yield();
165  }
166  }
167 
168  // The function pass(es) modified the IR, they may have clobbered the
169  // callgraph.
170  if (Changed && CallGraphUpToDate) {
171  LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: " << P->getPassName()
172  << '\n');
173  CallGraphUpToDate = false;
174  }
175  return Changed;
176 }
177 
178 /// Scan the functions in the specified CFG and resync the
179 /// callgraph with the call sites found in it. This is used after
180 /// FunctionPasses have potentially munged the callgraph, and can be used after
181 /// CallGraphSCC passes to verify that they correctly updated the callgraph.
182 ///
183 /// This function returns true if it devirtualized an existing function call,
184 /// meaning it turned an indirect call into a direct call. This happens when
185 /// a function pass like GVN optimizes away stuff feeding the indirect call.
186 /// This never happens in checking mode.
187 bool CGPassManager::RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
188  bool CheckingMode) {
190 
191  LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()
192  << " nodes:\n";
193  for (CallGraphNode *CGN
194  : CurSCC) CGN->dump(););
195 
196  bool MadeChange = false;
197  bool DevirtualizedCall = false;
198 
199  // Scan all functions in the SCC.
200  unsigned FunctionNo = 0;
201  for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end();
202  SCCIdx != E; ++SCCIdx, ++FunctionNo) {
203  CallGraphNode *CGN = *SCCIdx;
204  Function *F = CGN->getFunction();
205  if (!F || F->isDeclaration()) continue;
206 
207  // Walk the function body looking for call sites. Sync up the call sites in
208  // CGN with those actually in the function.
209 
210  // Keep track of the number of direct and indirect calls that were
211  // invalidated and removed.
212  unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
213 
214  // Get the set of call sites currently in the function.
215  for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) {
216  // If this call site is null, then the function pass deleted the call
217  // entirely and the WeakTrackingVH nulled it out.
218  if (!I->first ||
219  // If we've already seen this call site, then the FunctionPass RAUW'd
220  // one call with another, which resulted in two "uses" in the edge
221  // list of the same call.
222  CallSites.count(I->first) ||
223 
224  // If the call edge is not from a call or invoke, or it is a
225  // instrinsic call, then the function pass RAUW'd a call with
226  // another value. This can happen when constant folding happens
227  // of well known functions etc.
228  !CallSite(I->first) ||
229  (CallSite(I->first).getCalledFunction() &&
230  CallSite(I->first).getCalledFunction()->isIntrinsic() &&
232  CallSite(I->first).getCalledFunction()->getIntrinsicID()))) {
233  assert(!CheckingMode &&
234  "CallGraphSCCPass did not update the CallGraph correctly!");
235 
236  // If this was an indirect call site, count it.
237  if (!I->second->getFunction())
238  ++NumIndirectRemoved;
239  else
240  ++NumDirectRemoved;
241 
242  // Just remove the edge from the set of callees, keep track of whether
243  // I points to the last element of the vector.
244  bool WasLast = I + 1 == E;
245  CGN->removeCallEdge(I);
246 
247  // If I pointed to the last element of the vector, we have to bail out:
248  // iterator checking rejects comparisons of the resultant pointer with
249  // end.
250  if (WasLast)
251  break;
252  E = CGN->end();
253  continue;
254  }
255 
256  assert(!CallSites.count(I->first) &&
257  "Call site occurs in node multiple times");
258 
259  CallSite CS(I->first);
260  if (CS) {
261  Function *Callee = CS.getCalledFunction();
262  // Ignore intrinsics because they're not really function calls.
263  if (!Callee || !(Callee->isIntrinsic()))
264  CallSites.insert(std::make_pair(I->first, I->second));
265  }
266  ++I;
267  }
268 
269  // Loop over all of the instructions in the function, getting the callsites.
270  // Keep track of the number of direct/indirect calls added.
271  unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
272 
273  for (BasicBlock &BB : *F)
274  for (Instruction &I : BB) {
275  CallSite CS(&I);
276  if (!CS) continue;
277  Function *Callee = CS.getCalledFunction();
278  if (Callee && Callee->isIntrinsic()) continue;
279 
280  // If this call site already existed in the callgraph, just verify it
281  // matches up to expectations and remove it from CallSites.
283  CallSites.find(CS.getInstruction());
284  if (ExistingIt != CallSites.end()) {
285  CallGraphNode *ExistingNode = ExistingIt->second;
286 
287  // Remove from CallSites since we have now seen it.
288  CallSites.erase(ExistingIt);
289 
290  // Verify that the callee is right.
291  if (ExistingNode->getFunction() == CS.getCalledFunction())
292  continue;
293 
294  // If we are in checking mode, we are not allowed to actually mutate
295  // the callgraph. If this is a case where we can infer that the
296  // callgraph is less precise than it could be (e.g. an indirect call
297  // site could be turned direct), don't reject it in checking mode, and
298  // don't tweak it to be more precise.
299  if (CheckingMode && CS.getCalledFunction() &&
300  ExistingNode->getFunction() == nullptr)
301  continue;
302 
303  assert(!CheckingMode &&
304  "CallGraphSCCPass did not update the CallGraph correctly!");
305 
306  // If not, we either went from a direct call to indirect, indirect to
307  // direct, or direct to different direct.
308  CallGraphNode *CalleeNode;
309  if (Function *Callee = CS.getCalledFunction()) {
310  CalleeNode = CG.getOrInsertFunction(Callee);
311  // Keep track of whether we turned an indirect call into a direct
312  // one.
313  if (!ExistingNode->getFunction()) {
314  DevirtualizedCall = true;
315  LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Devirtualized call to '"
316  << Callee->getName() << "'\n");
317  }
318  } else {
319  CalleeNode = CG.getCallsExternalNode();
320  }
321 
322  // Update the edge target in CGN.
323  CGN->replaceCallEdge(CS, CS, CalleeNode);
324  MadeChange = true;
325  continue;
326  }
327 
328  assert(!CheckingMode &&
329  "CallGraphSCCPass did not update the CallGraph correctly!");
330 
331  // If the call site didn't exist in the CGN yet, add it.
332  CallGraphNode *CalleeNode;
333  if (Function *Callee = CS.getCalledFunction()) {
334  CalleeNode = CG.getOrInsertFunction(Callee);
335  ++NumDirectAdded;
336  } else {
337  CalleeNode = CG.getCallsExternalNode();
338  ++NumIndirectAdded;
339  }
340 
341  CGN->addCalledFunction(CS, CalleeNode);
342  MadeChange = true;
343  }
344 
345  // We scanned the old callgraph node, removing invalidated call sites and
346  // then added back newly found call sites. One thing that can happen is
347  // that an old indirect call site was deleted and replaced with a new direct
348  // call. In this case, we have devirtualized a call, and CGSCCPM would like
349  // to iteratively optimize the new code. Unfortunately, we don't really
350  // have a great way to detect when this happens. As an approximation, we
351  // just look at whether the number of indirect calls is reduced and the
352  // number of direct calls is increased. There are tons of ways to fool this
353  // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
354  // direct call) but this is close enough.
355  if (NumIndirectRemoved > NumIndirectAdded &&
356  NumDirectRemoved < NumDirectAdded)
357  DevirtualizedCall = true;
358 
359  // After scanning this function, if we still have entries in callsites, then
360  // they are dangling pointers. WeakTrackingVH should save us for this, so
361  // abort if
362  // this happens.
363  assert(CallSites.empty() && "Dangling pointers found in call sites map");
364 
365  // Periodically do an explicit clear to remove tombstones when processing
366  // large scc's.
367  if ((FunctionNo & 15) == 15)
368  CallSites.clear();
369  }
370 
371  LLVM_DEBUG(if (MadeChange) {
372  dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
373  for (CallGraphNode *CGN : CurSCC)
374  CGN->dump();
375  if (DevirtualizedCall)
376  dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
377  } else {
378  dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
379  });
380  (void)MadeChange;
381 
382  return DevirtualizedCall;
383 }
384 
385 /// Execute the body of the entire pass manager on the specified SCC.
386 /// This keeps track of whether a function pass devirtualizes
387 /// any calls and returns it in DevirtualizedCall.
388 bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
389  bool &DevirtualizedCall) {
390  bool Changed = false;
391 
392  // Keep track of whether the callgraph is known to be up-to-date or not.
393  // The CGSSC pass manager runs two types of passes:
394  // CallGraphSCC Passes and other random function passes. Because other
395  // random function passes are not CallGraph aware, they may clobber the
396  // call graph by introducing new calls or deleting other ones. This flag
397  // is set to false when we run a function pass so that we know to clean up
398  // the callgraph when we need to run a CGSCCPass again.
399  bool CallGraphUpToDate = true;
400 
401  // Run all passes on current SCC.
402  for (unsigned PassNo = 0, e = getNumContainedPasses();
403  PassNo != e; ++PassNo) {
404  Pass *P = getContainedPass(PassNo);
405 
406  // If we're in -debug-pass=Executions mode, construct the SCC node list,
407  // otherwise avoid constructing this string as it is expensive.
408  if (isPassDebuggingExecutionsOrMore()) {
409  std::string Functions;
410  #ifndef NDEBUG
411  raw_string_ostream OS(Functions);
412  for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
413  I != E; ++I) {
414  if (I != CurSCC.begin()) OS << ", ";
415  (*I)->print(OS);
416  }
417  OS.flush();
418  #endif
419  dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
420  }
421  dumpRequiredSet(P);
422 
423  initializeAnalysisImpl(P);
424 
425  // Actually run this pass on the current SCC.
426  Changed |= RunPassOnSCC(P, CurSCC, CG,
427  CallGraphUpToDate, DevirtualizedCall);
428 
429  if (Changed)
430  dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
431  dumpPreservedSet(P);
432 
433  verifyPreservedAnalysis(P);
434  removeNotPreservedAnalysis(P);
435  recordAvailableAnalysis(P);
436  removeDeadPasses(P, "", ON_CG_MSG);
437  }
438 
439  // If the callgraph was left out of date (because the last pass run was a
440  // functionpass), refresh it before we move on to the next SCC.
441  if (!CallGraphUpToDate)
442  DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
443  return Changed;
444 }
445 
446 /// Execute all of the passes scheduled for execution. Keep track of
447 /// whether any of the passes modifies the module, and if so, return true.
448 bool CGPassManager::runOnModule(Module &M) {
449  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
450  bool Changed = doInitialization(CG);
451 
452  // Walk the callgraph in bottom-up SCC order.
454 
455  CallGraphSCC CurSCC(CG, &CGI);
456  while (!CGI.isAtEnd()) {
457  // Copy the current SCC and increment past it so that the pass can hack
458  // on the SCC if it wants to without invalidating our iterator.
459  const std::vector<CallGraphNode *> &NodeVec = *CGI;
460  CurSCC.initialize(NodeVec);
461  ++CGI;
462 
463  // At the top level, we run all the passes in this pass manager on the
464  // functions in this SCC. However, we support iterative compilation in the
465  // case where a function pass devirtualizes a call to a function. For
466  // example, it is very common for a function pass (often GVN or instcombine)
467  // to eliminate the addressing that feeds into a call. With that improved
468  // information, we would like the call to be an inline candidate, infer
469  // mod-ref information etc.
470  //
471  // Because of this, we allow iteration up to a specified iteration count.
472  // This only happens in the case of a devirtualized call, so we only burn
473  // compile time in the case that we're making progress. We also have a hard
474  // iteration count limit in case there is crazy code.
475  unsigned Iteration = 0;
476  bool DevirtualizedCall = false;
477  do {
478  LLVM_DEBUG(if (Iteration) dbgs()
479  << " SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration
480  << '\n');
481  DevirtualizedCall = false;
482  Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
483  } while (Iteration++ < MaxIterations && DevirtualizedCall);
484 
485  if (DevirtualizedCall)
486  LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after "
487  << Iteration
488  << " times, due to -max-cg-scc-iterations\n");
489 
490  MaxSCCIterations.updateMax(Iteration);
491  }
492  Changed |= doFinalization(CG);
493  return Changed;
494 }
495 
496 /// Initialize CG
497 bool CGPassManager::doInitialization(CallGraph &CG) {
498  bool Changed = false;
499  for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
500  if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
502  "Invalid CGPassManager member");
503  Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
504  } else {
505  Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
506  }
507  }
508  return Changed;
509 }
510 
511 /// Finalize CG
512 bool CGPassManager::doFinalization(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)->doFinalization(CG.getModule());
519  } else {
520  Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
521  }
522  }
523  return Changed;
524 }
525 
526 //===----------------------------------------------------------------------===//
527 // CallGraphSCC Implementation
528 //===----------------------------------------------------------------------===//
529 
530 /// This informs the SCC and the pass manager that the specified
531 /// Old node has been deleted, and New is to be used in its place.
533  assert(Old != New && "Should not replace node with self");
534  for (unsigned i = 0; ; ++i) {
535  assert(i != Nodes.size() && "Node not in SCC");
536  if (Nodes[i] != Old) continue;
537  Nodes[i] = New;
538  break;
539  }
540 
541  // Update the active scc_iterator so that it doesn't contain dangling
542  // pointers to the old CallGraphNode.
544  CGI->ReplaceNode(Old, New);
545 }
546 
547 //===----------------------------------------------------------------------===//
548 // CallGraphSCCPass Implementation
549 //===----------------------------------------------------------------------===//
550 
551 /// Assign pass manager to manage this pass.
553  PassManagerType PreferredType) {
554  // Find CGPassManager
555  while (!PMS.empty() &&
557  PMS.pop();
558 
559  assert(!PMS.empty() && "Unable to handle Call Graph Pass");
560  CGPassManager *CGP;
561 
563  CGP = (CGPassManager*)PMS.top();
564  else {
565  // Create new Call Graph SCC Pass Manager if it does not exist.
566  assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");
567  PMDataManager *PMD = PMS.top();
568 
569  // [1] Create new Call Graph Pass Manager
570  CGP = new CGPassManager();
571 
572  // [2] Set up new manager's top level manager
573  PMTopLevelManager *TPM = PMD->getTopLevelManager();
574  TPM->addIndirectPassManager(CGP);
575 
576  // [3] Assign manager to manage this new manager. This may create
577  // and push new managers into PMS
578  Pass *P = CGP;
579  TPM->schedulePass(P);
580 
581  // [4] Push new manager into PMS
582  PMS.push(CGP);
583  }
584 
585  CGP->add(this);
586 }
587 
588 /// For this class, we declare that we require and preserve the call graph.
589 /// If the derived class implements this method, it should
590 /// always explicitly call the implementation here.
594 }
595 
596 //===----------------------------------------------------------------------===//
597 // PrintCallGraphPass Implementation
598 //===----------------------------------------------------------------------===//
599 
600 namespace {
601 
602  /// PrintCallGraphPass - Print a Module corresponding to a call graph.
603  ///
604  class PrintCallGraphPass : public CallGraphSCCPass {
605  std::string Banner;
606  raw_ostream &OS; // raw_ostream to print on.
607 
608  public:
609  static char ID;
610 
611  PrintCallGraphPass(const std::string &B, raw_ostream &OS)
612  : CallGraphSCCPass(ID), Banner(B), OS(OS) {}
613 
614  void getAnalysisUsage(AnalysisUsage &AU) const override {
615  AU.setPreservesAll();
616  }
617 
618  bool runOnSCC(CallGraphSCC &SCC) override {
619  bool BannerPrinted = false;
620  auto PrintBannerOnce = [&] () {
621  if (BannerPrinted)
622  return;
623  OS << Banner;
624  BannerPrinted = true;
625  };
626  for (CallGraphNode *CGN : SCC) {
627  if (Function *F = CGN->getFunction()) {
628  if (!F->isDeclaration() && isFunctionInPrintList(F->getName())) {
629  PrintBannerOnce();
630  F->print(OS);
631  }
632  } else if (isFunctionInPrintList("*")) {
633  PrintBannerOnce();
634  OS << "\nPrinting <null> Function\n";
635  }
636  }
637  return false;
638  }
639 
640  StringRef getPassName() const override { return "Print CallGraph IR"; }
641  };
642 
643 } // end anonymous namespace.
644 
645 char PrintCallGraphPass::ID = 0;
646 
648  const std::string &Banner) const {
649  return new PrintCallGraphPass(Banner, OS);
650 }
651 
653  return !SCC.getCallGraph().getModule()
654  .getContext()
655  .getOptPassGate()
656  .shouldRunPass(this, SCC);
657 }
658 
659 char DummyCGSCCPass::ID = 0;
660 
661 INITIALIZE_PASS(DummyCGSCCPass, "DummyCGSCCPass", "DummyCGSCCPass", false,
662  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:185
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 *)
If TimingInfo is enabled then start pass timer.
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
const CallGraph & getCallGraph()
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:984
CallGraphNode * getCallsExternalNode() const
Definition: CallGraph.h:139
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
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:180
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
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:201
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:477
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:119
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:43