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