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