LLVM  17.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  assert(!CheckingMode &&
272  "CallGraphSCCPass did not update the CallGraph correctly!");
273 
274  // If this was an indirect call site, count it.
275  if (!I->second->getFunction())
276  ++NumIndirectRemoved;
277  else
278  ++NumDirectRemoved;
279 
280  if (RemoveAndCheckForDone(I))
281  break;
282  continue;
283  }
284 
285  assert(!Calls.count(Call) && "Call site occurs in node multiple times");
286 
287  if (Call) {
288  Function *Callee = Call->getCalledFunction();
289  // Ignore intrinsics because they're not really function calls.
290  if (!Callee || !(Callee->isIntrinsic()))
291  Calls.insert(std::make_pair(Call, I->second));
292  }
293  ++I;
294  }
295 
296  // Loop over all of the instructions in the function, getting the callsites.
297  // Keep track of the number of direct/indirect calls added.
298  unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
299 
300  for (BasicBlock &BB : *F)
301  for (Instruction &I : BB) {
302  auto *Call = dyn_cast<CallBase>(&I);
303  if (!Call)
304  continue;
305  Function *Callee = Call->getCalledFunction();
306  if (Callee && Callee->isIntrinsic())
307  continue;
308 
309  // If we are not in checking mode, insert potential callback calls as
310  // references. This is not a requirement but helps to iterate over the
311  // functions in the right order.
312  if (!CheckingMode) {
313  forEachCallbackFunction(*Call, [&](Function *CB) {
314  CGN->addCalledFunction(nullptr, CG.getOrInsertFunction(CB));
315  });
316  }
317 
318  // If this call site already existed in the callgraph, just verify it
319  // matches up to expectations and remove it from Calls.
321  Calls.find(Call);
322  if (ExistingIt != Calls.end()) {
323  CallGraphNode *ExistingNode = ExistingIt->second;
324 
325  // Remove from Calls since we have now seen it.
326  Calls.erase(ExistingIt);
327 
328  // Verify that the callee is right.
329  if (ExistingNode->getFunction() == Call->getCalledFunction())
330  continue;
331 
332  // If we are in checking mode, we are not allowed to actually mutate
333  // the callgraph. If this is a case where we can infer that the
334  // callgraph is less precise than it could be (e.g. an indirect call
335  // site could be turned direct), don't reject it in checking mode, and
336  // don't tweak it to be more precise.
337  if (CheckingMode && Call->getCalledFunction() &&
338  ExistingNode->getFunction() == nullptr)
339  continue;
340 
341  assert(!CheckingMode &&
342  "CallGraphSCCPass did not update the CallGraph correctly!");
343 
344  // If not, we either went from a direct call to indirect, indirect to
345  // direct, or direct to different direct.
346  CallGraphNode *CalleeNode;
347  if (Function *Callee = Call->getCalledFunction()) {
348  CalleeNode = CG.getOrInsertFunction(Callee);
349  // Keep track of whether we turned an indirect call into a direct
350  // one.
351  if (!ExistingNode->getFunction()) {
352  DevirtualizedCall = true;
353  LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Devirtualized call to '"
354  << Callee->getName() << "'\n");
355  }
356  } else {
357  CalleeNode = CG.getCallsExternalNode();
358  }
359 
360  // Update the edge target in CGN.
361  CGN->replaceCallEdge(*Call, *Call, CalleeNode);
362  MadeChange = true;
363  continue;
364  }
365 
366  assert(!CheckingMode &&
367  "CallGraphSCCPass did not update the CallGraph correctly!");
368 
369  // If the call site didn't exist in the CGN yet, add it.
370  CallGraphNode *CalleeNode;
371  if (Function *Callee = Call->getCalledFunction()) {
372  CalleeNode = CG.getOrInsertFunction(Callee);
373  ++NumDirectAdded;
374  } else {
375  CalleeNode = CG.getCallsExternalNode();
376  ++NumIndirectAdded;
377  }
378 
379  CGN->addCalledFunction(Call, CalleeNode);
380  MadeChange = true;
381  }
382 
383  // We scanned the old callgraph node, removing invalidated call sites and
384  // then added back newly found call sites. One thing that can happen is
385  // that an old indirect call site was deleted and replaced with a new direct
386  // call. In this case, we have devirtualized a call, and CGSCCPM would like
387  // to iteratively optimize the new code. Unfortunately, we don't really
388  // have a great way to detect when this happens. As an approximation, we
389  // just look at whether the number of indirect calls is reduced and the
390  // number of direct calls is increased. There are tons of ways to fool this
391  // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
392  // direct call) but this is close enough.
393  if (NumIndirectRemoved > NumIndirectAdded &&
394  NumDirectRemoved < NumDirectAdded)
395  DevirtualizedCall = true;
396 
397  // After scanning this function, if we still have entries in callsites, then
398  // they are dangling pointers. WeakTrackingVH should save us for this, so
399  // abort if
400  // this happens.
401  assert(Calls.empty() && "Dangling pointers found in call sites map");
402 
403  // Periodically do an explicit clear to remove tombstones when processing
404  // large scc's.
405  if ((FunctionNo & 15) == 15)
406  Calls.clear();
407  }
408 
409  LLVM_DEBUG(if (MadeChange) {
410  dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
411  for (CallGraphNode *CGN : CurSCC)
412  CGN->dump();
413  if (DevirtualizedCall)
414  dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
415  } else {
416  dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
417  });
418  (void)MadeChange;
419 
420  return DevirtualizedCall;
421 }
422 
423 /// Execute the body of the entire pass manager on the specified SCC.
424 /// This keeps track of whether a function pass devirtualizes
425 /// any calls and returns it in DevirtualizedCall.
426 bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
427  bool &DevirtualizedCall) {
428  bool Changed = false;
429 
430  // Keep track of whether the callgraph is known to be up-to-date or not.
431  // The CGSSC pass manager runs two types of passes:
432  // CallGraphSCC Passes and other random function passes. Because other
433  // random function passes are not CallGraph aware, they may clobber the
434  // call graph by introducing new calls or deleting other ones. This flag
435  // is set to false when we run a function pass so that we know to clean up
436  // the callgraph when we need to run a CGSCCPass again.
437  bool CallGraphUpToDate = true;
438 
439  // Run all passes on current SCC.
440  for (unsigned PassNo = 0, e = getNumContainedPasses();
441  PassNo != e; ++PassNo) {
442  Pass *P = getContainedPass(PassNo);
443 
444  // If we're in -debug-pass=Executions mode, construct the SCC node list,
445  // otherwise avoid constructing this string as it is expensive.
446  if (isPassDebuggingExecutionsOrMore()) {
447  std::string Functions;
448  #ifndef NDEBUG
449  raw_string_ostream OS(Functions);
450  ListSeparator LS;
451  for (const CallGraphNode *CGN : CurSCC) {
452  OS << LS;
453  CGN->print(OS);
454  }
455  OS.flush();
456  #endif
457  dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
458  }
459  dumpRequiredSet(P);
460 
461  initializeAnalysisImpl(P);
462 
463 #ifdef EXPENSIVE_CHECKS
464  uint64_t RefHash = P->structuralHash(CG.getModule());
465 #endif
466 
467  // Actually run this pass on the current SCC.
468  bool LocalChanged =
469  RunPassOnSCC(P, CurSCC, CG, CallGraphUpToDate, DevirtualizedCall);
470 
471  Changed |= LocalChanged;
472 
473 #ifdef EXPENSIVE_CHECKS
474  if (!LocalChanged && (RefHash != P->structuralHash(CG.getModule()))) {
475  llvm::errs() << "Pass modifies its input and doesn't report it: "
476  << P->getPassName() << "\n";
477  llvm_unreachable("Pass modifies its input and doesn't report it");
478  }
479 #endif
480  if (LocalChanged)
481  dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
482  dumpPreservedSet(P);
483 
484  verifyPreservedAnalysis(P);
485  if (LocalChanged)
486  removeNotPreservedAnalysis(P);
487  recordAvailableAnalysis(P);
488  removeDeadPasses(P, "", ON_CG_MSG);
489  }
490 
491  // If the callgraph was left out of date (because the last pass run was a
492  // functionpass), refresh it before we move on to the next SCC.
493  if (!CallGraphUpToDate)
494  DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
495  return Changed;
496 }
497 
498 /// Execute all of the passes scheduled for execution. Keep track of
499 /// whether any of the passes modifies the module, and if so, return true.
500 bool CGPassManager::runOnModule(Module &M) {
501  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
502  bool Changed = doInitialization(CG);
503 
504  // Walk the callgraph in bottom-up SCC order.
506 
507  CallGraphSCC CurSCC(CG, &CGI);
508  while (!CGI.isAtEnd()) {
509  // Copy the current SCC and increment past it so that the pass can hack
510  // on the SCC if it wants to without invalidating our iterator.
511  const std::vector<CallGraphNode *> &NodeVec = *CGI;
512  CurSCC.initialize(NodeVec);
513  ++CGI;
514 
515  // At the top level, we run all the passes in this pass manager on the
516  // functions in this SCC. However, we support iterative compilation in the
517  // case where a function pass devirtualizes a call to a function. For
518  // example, it is very common for a function pass (often GVN or instcombine)
519  // to eliminate the addressing that feeds into a call. With that improved
520  // information, we would like the call to be an inline candidate, infer
521  // mod-ref information etc.
522  //
523  // Because of this, we allow iteration up to a specified iteration count.
524  // This only happens in the case of a devirtualized call, so we only burn
525  // compile time in the case that we're making progress. We also have a hard
526  // iteration count limit in case there is crazy code.
527  unsigned Iteration = 0;
528  bool DevirtualizedCall = false;
529  do {
530  LLVM_DEBUG(if (Iteration) dbgs()
531  << " SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration
532  << '\n');
533  DevirtualizedCall = false;
534  Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
535  } while (Iteration++ < MaxDevirtIterations && DevirtualizedCall);
536 
537  if (DevirtualizedCall)
538  LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after "
539  << Iteration
540  << " times, due to -max-devirt-iterations\n");
541 
542  MaxSCCIterations.updateMax(Iteration);
543  }
544  Changed |= doFinalization(CG);
545  return Changed;
546 }
547 
548 /// Initialize CG
549 bool CGPassManager::doInitialization(CallGraph &CG) {
550  bool Changed = false;
551  for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
552  if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
554  "Invalid CGPassManager member");
555  Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
556  } else {
557  Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
558  }
559  }
560  return Changed;
561 }
562 
563 /// Finalize CG
564 bool CGPassManager::doFinalization(CallGraph &CG) {
565  bool Changed = false;
566  for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
567  if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
569  "Invalid CGPassManager member");
570  Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());
571  } else {
572  Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
573  }
574  }
575  return Changed;
576 }
577 
578 //===----------------------------------------------------------------------===//
579 // CallGraphSCC Implementation
580 //===----------------------------------------------------------------------===//
581 
582 /// This informs the SCC and the pass manager that the specified
583 /// Old node has been deleted, and New is to be used in its place.
585  assert(Old != New && "Should not replace node with self");
586  for (unsigned i = 0; ; ++i) {
587  assert(i != Nodes.size() && "Node not in SCC");
588  if (Nodes[i] != Old) continue;
589  if (New)
590  Nodes[i] = New;
591  else
592  Nodes.erase(Nodes.begin() + i);
593  break;
594  }
595 
596  // Update the active scc_iterator so that it doesn't contain dangling
597  // pointers to the old CallGraphNode.
599  CGI->ReplaceNode(Old, New);
600 }
601 
603  ReplaceNode(Old, /*New=*/nullptr);
604 }
605 
606 //===----------------------------------------------------------------------===//
607 // CallGraphSCCPass Implementation
608 //===----------------------------------------------------------------------===//
609 
610 /// Assign pass manager to manage this pass.
612  PassManagerType PreferredType) {
613  // Find CGPassManager
614  while (!PMS.empty() &&
616  PMS.pop();
617 
618  assert(!PMS.empty() && "Unable to handle Call Graph Pass");
619  CGPassManager *CGP;
620 
622  CGP = (CGPassManager*)PMS.top();
623  else {
624  // Create new Call Graph SCC Pass Manager if it does not exist.
625  assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");
626  PMDataManager *PMD = PMS.top();
627 
628  // [1] Create new Call Graph Pass Manager
629  CGP = new CGPassManager();
630 
631  // [2] Set up new manager's top level manager
633  TPM->addIndirectPassManager(CGP);
634 
635  // [3] Assign manager to manage this new manager. This may create
636  // and push new managers into PMS
637  Pass *P = CGP;
638  TPM->schedulePass(P);
639 
640  // [4] Push new manager into PMS
641  PMS.push(CGP);
642  }
643 
644  CGP->add(this);
645 }
646 
647 /// For this class, we declare that we require and preserve the call graph.
648 /// If the derived class implements this method, it should
649 /// always explicitly call the implementation here.
653 }
654 
655 //===----------------------------------------------------------------------===//
656 // PrintCallGraphPass Implementation
657 //===----------------------------------------------------------------------===//
658 
659 namespace {
660 
661  /// PrintCallGraphPass - Print a Module corresponding to a call graph.
662  ///
663  class PrintCallGraphPass : public CallGraphSCCPass {
664  std::string Banner;
665  raw_ostream &OS; // raw_ostream to print on.
666 
667  public:
668  static char ID;
669 
670  PrintCallGraphPass(const std::string &B, raw_ostream &OS)
671  : CallGraphSCCPass(ID), Banner(B), OS(OS) {}
672 
673  void getAnalysisUsage(AnalysisUsage &AU) const override {
674  AU.setPreservesAll();
675  }
676 
677  bool runOnSCC(CallGraphSCC &SCC) override {
678  bool BannerPrinted = false;
679  auto PrintBannerOnce = [&]() {
680  if (BannerPrinted)
681  return;
682  OS << Banner;
683  BannerPrinted = true;
684  };
685 
686  bool NeedModule = llvm::forcePrintModuleIR();
687  if (isFunctionInPrintList("*") && NeedModule) {
688  PrintBannerOnce();
689  OS << "\n";
690  SCC.getCallGraph().getModule().print(OS, nullptr);
691  return false;
692  }
693  bool FoundFunction = false;
694  for (CallGraphNode *CGN : SCC) {
695  if (Function *F = CGN->getFunction()) {
696  if (!F->isDeclaration() && isFunctionInPrintList(F->getName())) {
697  FoundFunction = true;
698  if (!NeedModule) {
699  PrintBannerOnce();
700  F->print(OS);
701  }
702  }
703  } else if (isFunctionInPrintList("*")) {
704  PrintBannerOnce();
705  OS << "\nPrinting <null> Function\n";
706  }
707  }
708  if (NeedModule && FoundFunction) {
709  PrintBannerOnce();
710  OS << "\n";
711  SCC.getCallGraph().getModule().print(OS, nullptr);
712  }
713  return false;
714  }
715 
716  StringRef getPassName() const override { return "Print CallGraph IR"; }
717  };
718 
719 } // end anonymous namespace.
720 
721 char PrintCallGraphPass::ID = 0;
722 
724  const std::string &Banner) const {
725  return new PrintCallGraphPass(Banner, OS);
726 }
727 
728 static std::string getDescription(const CallGraphSCC &SCC) {
729  std::string Desc = "SCC (";
730  ListSeparator LS;
731  for (CallGraphNode *CGN : SCC) {
732  Desc += LS;
733  Function *F = CGN->getFunction();
734  if (F)
735  Desc += F->getName();
736  else
737  Desc += "<<null function>>";
738  }
739  Desc += ")";
740  return Desc;
741 }
742 
744  OptPassGate &Gate =
745  SCC.getCallGraph().getModule().getContext().getOptPassGate();
746  return Gate.isEnabled() &&
747  !Gate.shouldRunPass(this->getPassName(), getDescription(SCC));
748 }
749 
750 char DummyCGSCCPass::ID = 0;
751 
752 INITIALIZE_PASS(DummyCGSCCPass, "DummyCGSCCPass", "DummyCGSCCPass", false,
753  false)
i
i
Definition: README.txt:29
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:824
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:59
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:642
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: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
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:891
llvm::CallGraphNode::removeCallEdge
void removeCallEdge(iterator I)
Definition: CallGraph.h:249
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:139
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:170
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:203
INITIALIZE_PASS
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
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:584
llvm::dwarf::Index
Index
Definition: Dwarf.h:550
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:743
llvm::Instruction
Definition: Instruction.h:41
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:52
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:156
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:1410
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:110
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:650
llvm::ON_FUNCTION_MSG
@ ON_FUNCTION_MSG
Definition: LegacyPassManagers.h:100
Index
uint32_t Index
Definition: ELFObjHandler.cpp:83
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:602
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:31
llvm::DenseMap
Definition: DenseMap.h:714
llvm::CallGraphWrapperPass
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:345
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:723
llvm::getPassTimer
Timer * getPassTimer(Pass *)
Request the timer for this legacy-pass-manager's pass instance.
Definition: PassTimingInfo.cpp:152
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
llvm::isFunctionInPrintList
bool isFunctionInPrintList(StringRef FunctionName)
Definition: PrintPasses.cpp:152
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:65
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
bool empty() const
Definition: DenseMap.h:98
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:313
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::OptPassGate::shouldRunPass
virtual bool shouldRunPass(const StringRef PassName, StringRef IRDescription)
IRDescription is a textual description of the IR unit the pass is running over.
Definition: OptBisect.h:32
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:50
llvm::Pass::getPassName
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
llvm::PMT_FunctionPassManager
@ PMT_FunctionPassManager
FPPassManager.
Definition: Pass.h:56
llvm::Offset
@ Offset
Definition: DWP.cpp:406
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:136
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:1682
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:187
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:728
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:611
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:184
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:494
N
#define N
llvm::forcePrintModuleIR
bool forcePrintModuleIR()
Definition: PrintPasses.cpp:142
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::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:297
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::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:257