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