LLVM  13.0.0git
CallGraphSCCPass.cpp
Go to the documentation of this file.
1 //===- CallGraphSCCPass.cpp - Pass that operates BU on call graph ---------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the CallGraphSCCPass class, which is used for passes
10 // which are implemented as bottom-up traversals on the call graph. Because
11 // there may be cycles in the call graph, passes of this type operate on the
12 // call-graph in SCC order: that is, they process function bottom-up, except for
13 // recursive functions, which they process all at once.
14 //
15 //===----------------------------------------------------------------------===//
16 
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/SCCIterator.h"
20 #include "llvm/ADT/Statistic.h"
23 #include "llvm/IR/Function.h"
24 #include "llvm/IR/Intrinsics.h"
25 #include "llvm/IR/LLVMContext.h"
27 #include "llvm/IR/Module.h"
28 #include "llvm/IR/OptBisect.h"
29 #include "llvm/IR/PassTimingInfo.h"
30 #include "llvm/IR/PrintPasses.h"
31 #include "llvm/IR/StructuralHash.h"
32 #include "llvm/Pass.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/Timer.h"
37 #include <cassert>
38 #include <string>
39 #include <utility>
40 #include <vector>
41 
42 using namespace llvm;
43 
44 #define DEBUG_TYPE "cgscc-passmgr"
45 
47  cl::init(4));
48 
49 STATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC");
50 
51 //===----------------------------------------------------------------------===//
52 // CGPassManager
53 //
54 /// CGPassManager manages FPPassManagers and CallGraphSCCPasses.
55 
56 namespace {
57 
58 class CGPassManager : public ModulePass, public PMDataManager {
59 public:
60  static char ID;
61 
62  explicit CGPassManager() : ModulePass(ID), PMDataManager() {}
63 
64  /// Execute all of the passes scheduled for execution. Keep track of
65  /// whether any of the passes modifies the module, and if so, return true.
66  bool runOnModule(Module &M) override;
67 
70 
71  bool doInitialization(CallGraph &CG);
72  bool doFinalization(CallGraph &CG);
73 
74  /// Pass Manager itself does not invalidate any analysis info.
75  void getAnalysisUsage(AnalysisUsage &Info) const override {
76  // CGPassManager walks SCC and it needs CallGraph.
77  Info.addRequired<CallGraphWrapperPass>();
78  Info.setPreservesAll();
79  }
80 
81  StringRef getPassName() const override { return "CallGraph Pass Manager"; }
82 
83  PMDataManager *getAsPMDataManager() override { return this; }
84  Pass *getAsPass() override { return this; }
85 
86  // Print passes managed by this manager
87  void dumpPassStructure(unsigned Offset) override {
88  errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n";
89  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
90  Pass *P = getContainedPass(Index);
91  P->dumpPassStructure(Offset + 1);
92  dumpLastUses(P, Offset+1);
93  }
94  }
95 
96  Pass *getContainedPass(unsigned N) {
97  assert(N < PassVector.size() && "Pass number out of range!");
98  return static_cast<Pass *>(PassVector[N]);
99  }
100 
101  PassManagerType getPassManagerType() const override {
103  }
104 
105 private:
106  bool RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
107  bool &DevirtualizedCall);
108 
109  bool RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
110  CallGraph &CG, bool &CallGraphUpToDate,
111  bool &DevirtualizedCall);
112  bool RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
113  bool IsCheckingMode);
114 };
115 
116 } // end anonymous namespace.
117 
118 char CGPassManager::ID = 0;
119 
120 bool CGPassManager::RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
121  CallGraph &CG, bool &CallGraphUpToDate,
122  bool &DevirtualizedCall) {
123  bool Changed = false;
124  PMDataManager *PM = P->getAsPMDataManager();
125  Module &M = CG.getModule();
126 
127  if (!PM) {
129  if (!CallGraphUpToDate) {
130  DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
131  CallGraphUpToDate = true;
132  }
133 
134  {
135  unsigned InstrCount, SCCCount = 0;
136  StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
137  bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
138  TimeRegion PassTimer(getPassTimer(CGSP));
139  if (EmitICRemark)
140  InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
141  Changed = CGSP->runOnSCC(CurSCC);
142 
143  if (EmitICRemark) {
144  // FIXME: Add getInstructionCount to CallGraphSCC.
145  SCCCount = M.getInstructionCount();
146  // Is there a difference in the number of instructions in the module?
147  if (SCCCount != InstrCount) {
148  // Yep. Emit a remark and update InstrCount.
149  int64_t Delta =
150  static_cast<int64_t>(SCCCount) - static_cast<int64_t>(InstrCount);
151  emitInstrCountChangedRemark(P, M, Delta, InstrCount,
152  FunctionToInstrCount);
153  InstrCount = SCCCount;
154  }
155  }
156  }
157 
158  // After the CGSCCPass is done, when assertions are enabled, use
159  // RefreshCallGraph to verify that the callgraph was correctly updated.
160 #ifndef NDEBUG
161  if (Changed)
162  RefreshCallGraph(CurSCC, CG, true);
163 #endif
164 
165  return Changed;
166  }
167 
169  "Invalid CGPassManager member");
170  FPPassManager *FPP = (FPPassManager*)P;
171 
172  // Run pass P on all functions in the current SCC.
173  for (CallGraphNode *CGN : CurSCC) {
174  if (Function *F = CGN->getFunction()) {
175  dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
176  {
177  TimeRegion PassTimer(getPassTimer(FPP));
178  Changed |= FPP->runOnFunction(*F);
179  }
180  F->getContext().yield();
181  }
182  }
183 
184  // The function pass(es) modified the IR, they may have clobbered the
185  // callgraph.
186  if (Changed && CallGraphUpToDate) {
187  LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: " << P->getPassName()
188  << '\n');
189  CallGraphUpToDate = false;
190  }
191  return Changed;
192 }
193 
194 /// Scan the functions in the specified CFG and resync the
195 /// callgraph with the call sites found in it. This is used after
196 /// FunctionPasses have potentially munged the callgraph, and can be used after
197 /// CallGraphSCC passes to verify that they correctly updated the callgraph.
198 ///
199 /// This function returns true if it devirtualized an existing function call,
200 /// meaning it turned an indirect call into a direct call. This happens when
201 /// a function pass like GVN optimizes away stuff feeding the indirect call.
202 /// This never happens in checking mode.
203 bool CGPassManager::RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG,
204  bool CheckingMode) {
206 
207  LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()
208  << " nodes:\n";
209  for (CallGraphNode *CGN
210  : CurSCC) CGN->dump(););
211 
212  bool MadeChange = false;
213  bool DevirtualizedCall = false;
214 
215  // Scan all functions in the SCC.
216  unsigned FunctionNo = 0;
217  for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end();
218  SCCIdx != E; ++SCCIdx, ++FunctionNo) {
219  CallGraphNode *CGN = *SCCIdx;
220  Function *F = CGN->getFunction();
221  if (!F || F->isDeclaration()) continue;
222 
223  // Walk the function body looking for call sites. Sync up the call sites in
224  // CGN with those actually in the function.
225 
226  // Keep track of the number of direct and indirect calls that were
227  // invalidated and removed.
228  unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
229 
230  CallGraphNode::iterator CGNEnd = CGN->end();
231 
232  auto RemoveAndCheckForDone = [&](CallGraphNode::iterator I) {
233  // Just remove the edge from the set of callees, keep track of whether
234  // I points to the last element of the vector.
235  bool WasLast = I + 1 == CGNEnd;
236  CGN->removeCallEdge(I);
237 
238  // If I pointed to the last element of the vector, we have to bail out:
239  // iterator checking rejects comparisons of the resultant pointer with
240  // end.
241  if (WasLast)
242  return true;
243 
244  CGNEnd = CGN->end();
245  return false;
246  };
247 
248  // Get the set of call sites currently in the function.
249  for (CallGraphNode::iterator I = CGN->begin(); I != CGNEnd;) {
250  // Delete "reference" call records that do not have call instruction. We
251  // reinsert them as needed later. However, keep them in checking mode.
252  if (!I->first) {
253  if (CheckingMode) {
254  ++I;
255  continue;
256  }
257  if (RemoveAndCheckForDone(I))
258  break;
259  continue;
260  }
261 
262  // If this call site is null, then the function pass deleted the call
263  // entirely and the WeakTrackingVH nulled it out.
264  auto *Call = dyn_cast_or_null<CallBase>(*I->first);
265  if (!Call ||
266  // If we've already seen this call site, then the FunctionPass RAUW'd
267  // one call with another, which resulted in two "uses" in the edge
268  // list of the same call.
269  Calls.count(Call) ||
270 
271  // If the call edge is not from a call or invoke, or it is a
272  // instrinsic call, then the function pass RAUW'd a call with
273  // another value. This can happen when constant folding happens
274  // of well known functions etc.
275  (Call->getCalledFunction() &&
276  Call->getCalledFunction()->isIntrinsic() &&
277  Intrinsic::isLeaf(Call->getCalledFunction()->getIntrinsicID()))) {
278  assert(!CheckingMode &&
279  "CallGraphSCCPass did not update the CallGraph correctly!");
280 
281  // If this was an indirect call site, count it.
282  if (!I->second->getFunction())
283  ++NumIndirectRemoved;
284  else
285  ++NumDirectRemoved;
286 
287  if (RemoveAndCheckForDone(I))
288  break;
289  continue;
290  }
291 
292  assert(!Calls.count(Call) && "Call site occurs in node multiple times");
293 
294  if (Call) {
295  Function *Callee = Call->getCalledFunction();
296  // Ignore intrinsics because they're not really function calls.
297  if (!Callee || !(Callee->isIntrinsic()))
298  Calls.insert(std::make_pair(Call, I->second));
299  }
300  ++I;
301  }
302 
303  // Loop over all of the instructions in the function, getting the callsites.
304  // Keep track of the number of direct/indirect calls added.
305  unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
306 
307  for (BasicBlock &BB : *F)
308  for (Instruction &I : BB) {
309  auto *Call = dyn_cast<CallBase>(&I);
310  if (!Call)
311  continue;
312  Function *Callee = Call->getCalledFunction();
313  if (Callee && Callee->isIntrinsic())
314  continue;
315 
316  // If we are not in checking mode, insert potential callback calls as
317  // references. This is not a requirement but helps to iterate over the
318  // functions in the right order.
319  if (!CheckingMode) {
320  forEachCallbackFunction(*Call, [&](Function *CB) {
321  CGN->addCalledFunction(nullptr, CG.getOrInsertFunction(CB));
322  });
323  }
324 
325  // If this call site already existed in the callgraph, just verify it
326  // matches up to expectations and remove it from Calls.
328  Calls.find(Call);
329  if (ExistingIt != Calls.end()) {
330  CallGraphNode *ExistingNode = ExistingIt->second;
331 
332  // Remove from Calls since we have now seen it.
333  Calls.erase(ExistingIt);
334 
335  // Verify that the callee is right.
336  if (ExistingNode->getFunction() == Call->getCalledFunction())
337  continue;
338 
339  // If we are in checking mode, we are not allowed to actually mutate
340  // the callgraph. If this is a case where we can infer that the
341  // callgraph is less precise than it could be (e.g. an indirect call
342  // site could be turned direct), don't reject it in checking mode, and
343  // don't tweak it to be more precise.
344  if (CheckingMode && Call->getCalledFunction() &&
345  ExistingNode->getFunction() == nullptr)
346  continue;
347 
348  assert(!CheckingMode &&
349  "CallGraphSCCPass did not update the CallGraph correctly!");
350 
351  // If not, we either went from a direct call to indirect, indirect to
352  // direct, or direct to different direct.
353  CallGraphNode *CalleeNode;
354  if (Function *Callee = Call->getCalledFunction()) {
355  CalleeNode = CG.getOrInsertFunction(Callee);
356  // Keep track of whether we turned an indirect call into a direct
357  // one.
358  if (!ExistingNode->getFunction()) {
359  DevirtualizedCall = true;
360  LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Devirtualized call to '"
361  << Callee->getName() << "'\n");
362  }
363  } else {
364  CalleeNode = CG.getCallsExternalNode();
365  }
366 
367  // Update the edge target in CGN.
368  CGN->replaceCallEdge(*Call, *Call, CalleeNode);
369  MadeChange = true;
370  continue;
371  }
372 
373  assert(!CheckingMode &&
374  "CallGraphSCCPass did not update the CallGraph correctly!");
375 
376  // If the call site didn't exist in the CGN yet, add it.
377  CallGraphNode *CalleeNode;
378  if (Function *Callee = Call->getCalledFunction()) {
379  CalleeNode = CG.getOrInsertFunction(Callee);
380  ++NumDirectAdded;
381  } else {
382  CalleeNode = CG.getCallsExternalNode();
383  ++NumIndirectAdded;
384  }
385 
386  CGN->addCalledFunction(Call, CalleeNode);
387  MadeChange = true;
388  }
389 
390  // We scanned the old callgraph node, removing invalidated call sites and
391  // then added back newly found call sites. One thing that can happen is
392  // that an old indirect call site was deleted and replaced with a new direct
393  // call. In this case, we have devirtualized a call, and CGSCCPM would like
394  // to iteratively optimize the new code. Unfortunately, we don't really
395  // have a great way to detect when this happens. As an approximation, we
396  // just look at whether the number of indirect calls is reduced and the
397  // number of direct calls is increased. There are tons of ways to fool this
398  // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
399  // direct call) but this is close enough.
400  if (NumIndirectRemoved > NumIndirectAdded &&
401  NumDirectRemoved < NumDirectAdded)
402  DevirtualizedCall = true;
403 
404  // After scanning this function, if we still have entries in callsites, then
405  // they are dangling pointers. WeakTrackingVH should save us for this, so
406  // abort if
407  // this happens.
408  assert(Calls.empty() && "Dangling pointers found in call sites map");
409 
410  // Periodically do an explicit clear to remove tombstones when processing
411  // large scc's.
412  if ((FunctionNo & 15) == 15)
413  Calls.clear();
414  }
415 
416  LLVM_DEBUG(if (MadeChange) {
417  dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
418  for (CallGraphNode *CGN : CurSCC)
419  CGN->dump();
420  if (DevirtualizedCall)
421  dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
422  } else {
423  dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
424  });
425  (void)MadeChange;
426 
427  return DevirtualizedCall;
428 }
429 
430 /// Execute the body of the entire pass manager on the specified SCC.
431 /// This keeps track of whether a function pass devirtualizes
432 /// any calls and returns it in DevirtualizedCall.
433 bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
434  bool &DevirtualizedCall) {
435  bool Changed = false;
436 
437  // Keep track of whether the callgraph is known to be up-to-date or not.
438  // The CGSSC pass manager runs two types of passes:
439  // CallGraphSCC Passes and other random function passes. Because other
440  // random function passes are not CallGraph aware, they may clobber the
441  // call graph by introducing new calls or deleting other ones. This flag
442  // is set to false when we run a function pass so that we know to clean up
443  // the callgraph when we need to run a CGSCCPass again.
444  bool CallGraphUpToDate = true;
445 
446  // Run all passes on current SCC.
447  for (unsigned PassNo = 0, e = getNumContainedPasses();
448  PassNo != e; ++PassNo) {
449  Pass *P = getContainedPass(PassNo);
450 
451  // If we're in -debug-pass=Executions mode, construct the SCC node list,
452  // otherwise avoid constructing this string as it is expensive.
453  if (isPassDebuggingExecutionsOrMore()) {
454  std::string Functions;
455  #ifndef NDEBUG
456  raw_string_ostream OS(Functions);
457  ListSeparator LS;
458  for (const CallGraphNode *CGN : CurSCC) {
459  OS << LS;
460  CGN->print(OS);
461  }
462  OS.flush();
463  #endif
464  dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
465  }
466  dumpRequiredSet(P);
467 
468  initializeAnalysisImpl(P);
469 
470 #ifdef EXPENSIVE_CHECKS
471  uint64_t RefHash = StructuralHash(CG.getModule());
472 #endif
473 
474  // Actually run this pass on the current SCC.
475  bool LocalChanged =
476  RunPassOnSCC(P, CurSCC, CG, CallGraphUpToDate, DevirtualizedCall);
477 
478  Changed |= LocalChanged;
479 
480 #ifdef EXPENSIVE_CHECKS
481  if (!LocalChanged && (RefHash != StructuralHash(CG.getModule()))) {
482  llvm::errs() << "Pass modifies its input and doesn't report it: "
483  << P->getPassName() << "\n";
484  llvm_unreachable("Pass modifies its input and doesn't report it");
485  }
486 #endif
487  if (LocalChanged)
488  dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
489  dumpPreservedSet(P);
490 
491  verifyPreservedAnalysis(P);
492  if (LocalChanged)
493  removeNotPreservedAnalysis(P);
494  recordAvailableAnalysis(P);
495  removeDeadPasses(P, "", ON_CG_MSG);
496  }
497 
498  // If the callgraph was left out of date (because the last pass run was a
499  // functionpass), refresh it before we move on to the next SCC.
500  if (!CallGraphUpToDate)
501  DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
502  return Changed;
503 }
504 
505 /// Execute all of the passes scheduled for execution. Keep track of
506 /// whether any of the passes modifies the module, and if so, return true.
507 bool CGPassManager::runOnModule(Module &M) {
508  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
509  bool Changed = doInitialization(CG);
510 
511  // Walk the callgraph in bottom-up SCC order.
513 
514  CallGraphSCC CurSCC(CG, &CGI);
515  while (!CGI.isAtEnd()) {
516  // Copy the current SCC and increment past it so that the pass can hack
517  // on the SCC if it wants to without invalidating our iterator.
518  const std::vector<CallGraphNode *> &NodeVec = *CGI;
519  CurSCC.initialize(NodeVec);
520  ++CGI;
521 
522  // At the top level, we run all the passes in this pass manager on the
523  // functions in this SCC. However, we support iterative compilation in the
524  // case where a function pass devirtualizes a call to a function. For
525  // example, it is very common for a function pass (often GVN or instcombine)
526  // to eliminate the addressing that feeds into a call. With that improved
527  // information, we would like the call to be an inline candidate, infer
528  // mod-ref information etc.
529  //
530  // Because of this, we allow iteration up to a specified iteration count.
531  // This only happens in the case of a devirtualized call, so we only burn
532  // compile time in the case that we're making progress. We also have a hard
533  // iteration count limit in case there is crazy code.
534  unsigned Iteration = 0;
535  bool DevirtualizedCall = false;
536  do {
537  LLVM_DEBUG(if (Iteration) dbgs()
538  << " SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration
539  << '\n');
540  DevirtualizedCall = false;
541  Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
542  } while (Iteration++ < MaxDevirtIterations && DevirtualizedCall);
543 
544  if (DevirtualizedCall)
545  LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after "
546  << Iteration
547  << " times, due to -max-devirt-iterations\n");
548 
549  MaxSCCIterations.updateMax(Iteration);
550  }
551  Changed |= doFinalization(CG);
552  return Changed;
553 }
554 
555 /// Initialize CG
556 bool CGPassManager::doInitialization(CallGraph &CG) {
557  bool Changed = false;
558  for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
559  if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
561  "Invalid CGPassManager member");
562  Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
563  } else {
564  Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
565  }
566  }
567  return Changed;
568 }
569 
570 /// Finalize CG
571 bool CGPassManager::doFinalization(CallGraph &CG) {
572  bool Changed = false;
573  for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
574  if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
576  "Invalid CGPassManager member");
577  Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());
578  } else {
579  Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
580  }
581  }
582  return Changed;
583 }
584 
585 //===----------------------------------------------------------------------===//
586 // CallGraphSCC Implementation
587 //===----------------------------------------------------------------------===//
588 
589 /// This informs the SCC and the pass manager that the specified
590 /// Old node has been deleted, and New is to be used in its place.
592  assert(Old != New && "Should not replace node with self");
593  for (unsigned i = 0; ; ++i) {
594  assert(i != Nodes.size() && "Node not in SCC");
595  if (Nodes[i] != Old) continue;
596  if (New)
597  Nodes[i] = New;
598  else
599  Nodes.erase(Nodes.begin() + i);
600  break;
601  }
602 
603  // Update the active scc_iterator so that it doesn't contain dangling
604  // pointers to the old CallGraphNode.
606  CGI->ReplaceNode(Old, New);
607 }
608 
610  ReplaceNode(Old, /*New=*/nullptr);
611 }
612 
613 //===----------------------------------------------------------------------===//
614 // CallGraphSCCPass Implementation
615 //===----------------------------------------------------------------------===//
616 
617 /// Assign pass manager to manage this pass.
619  PassManagerType PreferredType) {
620  // Find CGPassManager
621  while (!PMS.empty() &&
623  PMS.pop();
624 
625  assert(!PMS.empty() && "Unable to handle Call Graph Pass");
626  CGPassManager *CGP;
627 
629  CGP = (CGPassManager*)PMS.top();
630  else {
631  // Create new Call Graph SCC Pass Manager if it does not exist.
632  assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");
633  PMDataManager *PMD = PMS.top();
634 
635  // [1] Create new Call Graph Pass Manager
636  CGP = new CGPassManager();
637 
638  // [2] Set up new manager's top level manager
640  TPM->addIndirectPassManager(CGP);
641 
642  // [3] Assign manager to manage this new manager. This may create
643  // and push new managers into PMS
644  Pass *P = CGP;
645  TPM->schedulePass(P);
646 
647  // [4] Push new manager into PMS
648  PMS.push(CGP);
649  }
650 
651  CGP->add(this);
652 }
653 
654 /// For this class, we declare that we require and preserve the call graph.
655 /// If the derived class implements this method, it should
656 /// always explicitly call the implementation here.
660 }
661 
662 //===----------------------------------------------------------------------===//
663 // PrintCallGraphPass Implementation
664 //===----------------------------------------------------------------------===//
665 
666 namespace {
667 
668  /// PrintCallGraphPass - Print a Module corresponding to a call graph.
669  ///
670  class PrintCallGraphPass : public CallGraphSCCPass {
671  std::string Banner;
672  raw_ostream &OS; // raw_ostream to print on.
673 
674  public:
675  static char ID;
676 
677  PrintCallGraphPass(const std::string &B, raw_ostream &OS)
678  : CallGraphSCCPass(ID), Banner(B), OS(OS) {}
679 
680  void getAnalysisUsage(AnalysisUsage &AU) const override {
681  AU.setPreservesAll();
682  }
683 
684  bool runOnSCC(CallGraphSCC &SCC) override {
685  bool BannerPrinted = false;
686  auto PrintBannerOnce = [&]() {
687  if (BannerPrinted)
688  return;
689  OS << Banner;
690  BannerPrinted = true;
691  };
692 
693  bool NeedModule = llvm::forcePrintModuleIR();
694  if (isFunctionInPrintList("*") && NeedModule) {
695  PrintBannerOnce();
696  OS << "\n";
697  SCC.getCallGraph().getModule().print(OS, nullptr);
698  return false;
699  }
700  bool FoundFunction = false;
701  for (CallGraphNode *CGN : SCC) {
702  if (Function *F = CGN->getFunction()) {
703  if (!F->isDeclaration() && isFunctionInPrintList(F->getName())) {
704  FoundFunction = true;
705  if (!NeedModule) {
706  PrintBannerOnce();
707  F->print(OS);
708  }
709  }
710  } else if (isFunctionInPrintList("*")) {
711  PrintBannerOnce();
712  OS << "\nPrinting <null> Function\n";
713  }
714  }
715  if (NeedModule && FoundFunction) {
716  PrintBannerOnce();
717  OS << "\n";
718  SCC.getCallGraph().getModule().print(OS, nullptr);
719  }
720  return false;
721  }
722 
723  StringRef getPassName() const override { return "Print CallGraph IR"; }
724  };
725 
726 } // end anonymous namespace.
727 
728 char PrintCallGraphPass::ID = 0;
729 
731  const std::string &Banner) const {
732  return new PrintCallGraphPass(Banner, OS);
733 }
734 
735 static std::string getDescription(const CallGraphSCC &SCC) {
736  std::string Desc = "SCC (";
737  ListSeparator LS;
738  for (CallGraphNode *CGN : SCC) {
739  Desc += LS;
740  Function *F = CGN->getFunction();
741  if (F)
742  Desc += F->getName();
743  else
744  Desc += "<<null function>>";
745  }
746  Desc += ")";
747  return Desc;
748 }
749 
751  OptPassGate &Gate =
753  return Gate.isEnabled() && !Gate.shouldRunPass(this, getDescription(SCC));
754 }
755 
756 char DummyCGSCCPass::ID = 0;
757 
758 INITIALIZE_PASS(DummyCGSCCPass, "DummyCGSCCPass", "DummyCGSCCPass", false,
759  false)
i
i
Definition: README.txt:29
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
llvm::FPPassManager::runOnFunction
bool runOnFunction(Function &F)
run - Execute all of the passes scheduled for execution.
Definition: LegacyPassManager.cpp:1402
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::CallGraphNode::iterator
std::vector< CallRecord >::iterator iterator
Definition: CallGraph.h:194
llvm::PMT_CallGraphPassManager
@ PMT_CallGraphPassManager
CGPassManager.
Definition: Pass.h:55
llvm::ModulePass
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:238
SCCIterator.h
llvm::Function
Definition: Function.h:61
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
llvm::PMTopLevelManager::schedulePass
void schedulePass(Pass *P)
Schedule pass P for execution.
Definition: LegacyPassManager.cpp:664
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:614
Statistic.h
llvm::OptPassGate::isEnabled
virtual bool isEnabled() const
isEnabled() should return true before calling shouldRunPass().
Definition: OptBisect.h:37
llvm::CallGraph
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:73
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
llvm::PassManagerType
PassManagerType
Different types of internal pass managers.
Definition: Pass.h:52
InstrCount
static unsigned InstrCount
Definition: DFAPacketizer.cpp:53
DenseMap.h
Module.h
OptBisect.h
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
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:145
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::PMStack::push
void push(PMDataManager *PM)
Definition: LegacyPassManager.cpp:1700
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:894
llvm::CallGraphNode::removeCallEdge
void removeCallEdge(iterator I)
Definition: CallGraph.h:252
llvm::scc_iterator::ReplaceNode
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:135
MaxDevirtIterations
cl::opt< unsigned > MaxDevirtIterations("max-devirt-iterations", cl::ReallyHidden, cl::init(4))
llvm::cl::ReallyHidden
@ ReallyHidden
Definition: CommandLine.h:141
llvm::CallGraphNode::addCalledFunction
void addCalledFunction(CallBase *Call, CallGraphNode *M)
Adds a function to the list of functions called by this one.
Definition: CallGraph.h:243
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::CallGraph::getOrInsertFunction
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:175
PassTimingInfo.h
CommandLine.h
llvm::PMDataManager
PMDataManager provides the common place to manage the analysis data used by pass managers.
Definition: LegacyPassManagers.h:296
llvm::CallGraphNode::end
iterator end()
Definition: CallGraph.h:201
llvm::CallGraphSCC
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
Definition: CallGraphSCCPass.h:87
llvm::TimeRegion
The TimeRegion class is used as a helper class to call the startTimer() and stopTimer() methods of th...
Definition: Timer.h:146
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Intrinsics.h
llvm::CallGraphNode::dump
void dump() const
Print out this call graph node.
Definition: CallGraph.cpp:208
INITIALIZE_PASS
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:37
llvm::OptPassGate
Extensions to this class implement mechanisms to disable passes and individual optimizations at compi...
Definition: OptBisect.h:26
LegacyPassManagers.h
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::CallGraphSCC::size
unsigned size() const
Definition: CallGraphSCCPass.h:100
llvm::CallGraphSCC::ReplaceNode
void ReplaceNode(CallGraphNode *Old, CallGraphNode *New)
ReplaceNode - This informs the SCC and the pass manager that the specified Old node has been deleted,...
Definition: CallGraphSCCPass.cpp:591
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::CallGraphSCCPass::skipSCC
bool skipSCC(CallGraphSCC &SCC) const
Optional passes call this function to check whether the pass should be skipped.
Definition: CallGraphSCCPass.cpp:750
llvm::Instruction
Definition: Instruction.h:45
llvm::DummyCGSCCPass::ID
static char ID
Definition: CallGraphSCCPass.h:124
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::MODIFICATION_MSG
@ MODIFICATION_MSG
Definition: LegacyPassManagers.h:99
llvm::CallGraphNode
A node in the call graph for a module.
Definition: CallGraph.h:167
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:26
llvm::ON_CG_MSG
@ ON_CG_MSG
Definition: LegacyPassManagers.h:105
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:154
PrintPasses.h
llvm::PMStack::top
PMDataManager * top() const
Definition: LegacyPassManagers.h:144
llvm::LLVMContext::getOptPassGate
OptPassGate & getOptPassGate() const
Access the object which can disable optional passes and individual optimizations at compile time.
Definition: LLVMContext.cpp:335
llvm::StringMap
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition: StringMap.h:108
llvm::PMStack::empty
bool empty() const
Definition: LegacyPassManagers.h:146
llvm::scc_begin
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:228
StructuralHash.h
Timer.h
llvm::cl::opt
Definition: CommandLine.h:1419
llvm::CallGraphSCC::iterator
std::vector< CallGraphNode * >::const_iterator iterator
Definition: CallGraphSCCPass.h:110
llvm::PMDataManager::getTopLevelManager
PMTopLevelManager * getTopLevelManager()
Definition: LegacyPassManagers.h:364
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:111
llvm::CallGraphSCCPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph.
Definition: CallGraphSCCPass.cpp:657
llvm::ON_FUNCTION_MSG
@ ON_FUNCTION_MSG
Definition: LegacyPassManagers.h:101
Index
uint32_t Index
Definition: ELFObjHandler.cpp:84
llvm::CallGraphSCC::DeleteNode
void DeleteNode(CallGraphNode *Old)
DeleteNode - This informs the SCC and the pass manager that the specified Old node has been deleted.
Definition: CallGraphSCCPass.cpp:609
llvm::scc_iterator
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:42
llvm::CallGraphSCC::begin
iterator begin() const
Definition: CallGraphSCCPass.h:112
llvm::CallGraphSCC::getCallGraph
const CallGraph & getCallGraph()
Definition: CallGraphSCCPass.h:115
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:58
llvm::DenseMap
Definition: DenseMap.h:714
llvm::CallGraphWrapperPass
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:337
llvm::CallGraphSCCPass::createPrinterPass
Pass * createPrinterPass(raw_ostream &OS, const std::string &Banner) const override
createPrinterPass - Get a pass that prints the Module corresponding to a CallGraph.
Definition: CallGraphSCCPass.cpp:730
llvm::getPassTimer
Timer * getPassTimer(Pass *)
Request the timer for this legacy-pass-manager's pass instance.
Definition: PassTimingInfo.cpp:153
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:440
llvm::isFunctionInPrintList
bool isFunctionInPrintList(StringRef FunctionName)
Definition: PrintPasses.cpp:83
llvm::Intrinsic::isLeaf
bool isLeaf(ID id)
Returns true if the intrinsic is a leaf, i.e.
Definition: Function.cpp:1237
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DummyCGSCCPass
This pass is required by interprocedural register allocation.
Definition: CallGraphSCCPass.h:122
llvm::CallGraphSCC::end
iterator end() const
Definition: CallGraphSCCPass.h:113
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::Module::print
void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW, bool ShouldPreserveUseListOrder=false, bool IsForDebug=false) const
Print the module to an output stream with an optional AssemblyAnnotationWriter.
Definition: AsmWriter.cpp:4527
llvm::Pass::doFinalization
virtual bool doFinalization(Module &)
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
Definition: Pass.h:120
llvm::Pass::doInitialization
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: Pass.h:116
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::PMT_FunctionPassManager
@ PMT_FunctionPassManager
FPPassManager.
Definition: Pass.h:56
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::EXECUTION_MSG
@ EXECUTION_MSG
Definition: LegacyPassManagers.h:98
llvm::PMDataManager::getPassManagerType
virtual PassManagerType getPassManagerType() const
Definition: LegacyPassManagers.h:383
llvm::Pass::dump
void dump() const
Definition: Pass.cpp:131
CallGraphSCCPass.h
for
this could be done in SelectionDAGISel along with other special for
Definition: README.txt:104
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::PMStack::pop
void pop()
Definition: LegacyPassManager.cpp:1691
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:97
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:205
llvm::CallGraphNode::getFunction
Function * getFunction() const
Returns the function that this call graph node represents.
Definition: CallGraph.h:198
llvm::FPPassManager
FPPassManager manages BBPassManagers and FunctionPasses.
Definition: LegacyPassManagers.h:460
llvm::PMStack
PMStack - This class implements a stack data structure of PMDataManager pointers.
Definition: LegacyPassManagers.h:137
getDescription
static std::string getDescription(const CallGraphSCC &SCC)
Definition: CallGraphSCCPass.cpp:735
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::AArch64CC::LS
@ LS
Definition: AArch64BaseInfo.h:245
llvm::Module::getContext
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:253
Function.h
llvm::CallGraphSCCPass
Definition: CallGraphSCCPass.h:34
llvm::forEachCallbackFunction
void forEachCallbackFunction(const CallBase &CB, UnaryFunction Func)
Apply function Func to each CB's callback function.
Definition: AbstractCallSite.h:238
llvm::CallGraphSCCPass::assignPassManager
void assignPassManager(PMStack &PMS, PassManagerType PMT) override
Assign pass manager to manager this pass.
Definition: CallGraphSCCPass.cpp:618
llvm::PMTopLevelManager::addIndirectPassManager
void addIndirectPassManager(PMDataManager *Manager)
Definition: LegacyPassManagers.h:211
llvm::CallGraph::getModule
Module & getModule() const
Returns the module the call graph corresponds to.
Definition: CallGraph.h:102
llvm::scc_iterator::isAtEnd
bool isAtEnd() const
Direct loop termination test which is more efficient than comparison with end().
Definition: SCCIterator.h:108
CallGraph.h
llvm::CallGraphNode::print
void print(raw_ostream &OS) const
Definition: CallGraph.cpp:189
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
llvm::raw_ostream::indent
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Definition: raw_ostream.cpp:497
N
#define N
llvm::forcePrintModuleIR
bool forcePrintModuleIR()
Definition: PrintPasses.cpp:81
llvm::PMTopLevelManager
PMTopLevelManager manages LastUser info and collects common APIs used by top level pass managers.
Definition: LegacyPassManagers.h:159
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
LLVMContext.h
AbstractCallSite.h
raw_ostream.h
llvm::OptPassGate::shouldRunPass
virtual bool shouldRunPass(const Pass *P, StringRef IRDescription)
IRDescription is a textual description of the IR unit the pass is running over.
Definition: OptBisect.h:32
llvm::CallGraph::getCallsExternalNode
CallGraphNode * getCallsExternalNode() const
Definition: CallGraph.h:130
Debug.h
llvm::CallGraphSCCPass::runOnSCC
virtual bool runOnSCC(CallGraphSCC &SCC)=0
runOnSCC - This method should be implemented by the subclass to perform whatever action is necessary ...
llvm::CallGraphNode::begin
iterator begin()
Definition: CallGraph.h:200
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::CallGraphNode::replaceCallEdge
void replaceCallEdge(CallBase &Call, CallBase &NewCall, CallGraphNode *NewNode)
Replaces the edge in the node for the specified call site with a new one.
Definition: CallGraph.cpp:262