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