Line data    Source code

       1             : //===- CallGraphSCCPass.h - Pass that operates BU on call graph -*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file defines the CallGraphSCCPass class, which is used for passes which
      11             : // are implemented as bottom-up traversals on the call graph.  Because there may
      12             : // be cycles in the call graph, passes of this type operate on the call-graph in
      13             : // SCC order: that is, they process function bottom-up, except for recursive
      14             : // functions, which they process all at once.
      15             : //
      16             : // These passes are inherently interprocedural, and are required to keep the
      17             : // call graph up-to-date if they do anything which could modify it.
      18             : //
      19             : //===----------------------------------------------------------------------===//
      20             : 
      21             : #ifndef LLVM_ANALYSIS_CALLGRAPHSCCPASS_H
      22             : #define LLVM_ANALYSIS_CALLGRAPHSCCPASS_H
      23             : 
      24             : #include "llvm/ADT/ArrayRef.h"
      25             : #include "llvm/Pass.h"
      26             : #include <vector>
      27             : 
      28             : namespace llvm {
      29             : 
      30             : class CallGraph;
      31             : class CallGraphNode;
      32             : class CallGraphSCC;
      33             : class PMStack;
      34             : 
      35             : class CallGraphSCCPass : public Pass {
      36             : public:
      37             :   explicit CallGraphSCCPass(char &pid) : Pass(PT_CallGraphSCC, pid) {}
      38             : 
      39             :   /// createPrinterPass - Get a pass that prints the Module
      40             :   /// corresponding to a CallGraph.
      41             :   Pass *createPrinterPass(raw_ostream &OS,
      42             :                           const std::string &Banner) const override;
      43             : 
      44             :   using llvm::Pass::doInitialization;
      45             :   using llvm::Pass::doFinalization;
      46             : 
      47             :   /// doInitialization - This method is called before the SCC's of the program
      48             :   /// has been processed, allowing the pass to do initialization as necessary.
      49        5870 :   virtual bool doInitialization(CallGraph &CG) {
      50        5870 :     return false;
      51             :   }
      52             : 
      53             :   /// runOnSCC - This method should be implemented by the subclass to perform
      54             :   /// whatever action is necessary for the specified SCC.  Note that
      55             :   /// non-recursive (or only self-recursive) functions will have an SCC size of
      56             :   /// 1, where recursive portions of the call graph will have SCC size > 1.
      57             :   ///
      58             :   /// SCC passes that add or delete functions to the SCC are required to update
      59             :   /// the SCC list, otherwise stale pointers may be dereferenced.
      60             :   virtual bool runOnSCC(CallGraphSCC &SCC) = 0;
      61             : 
      62             :   /// doFinalization - This method is called after the SCC's of the program has
      63             :   /// been processed, allowing the pass to do final cleanup as necessary.
      64        8591 :   virtual bool doFinalization(CallGraph &CG) {
      65        8591 :     return false;
      66             :   }
      67             : 
      68             :   /// Assign pass manager to manager this pass
      69             :   void assignPassManager(PMStack &PMS, PassManagerType PMT) override;
      70             : 
      71             :   ///  Return what kind of Pass Manager can manage this pass.
      72      106610 :   PassManagerType getPotentialPassManagerType() const override {
      73      106610 :     return PMT_CallGraphPassManager;
      74             :   }
      75             : 
      76             :   /// getAnalysisUsage - For this class, we declare that we require and preserve
      77             :   /// the call graph.  If the derived class implements this method, it should
      78             :   /// always explicitly call the implementation here.
      79             :   void getAnalysisUsage(AnalysisUsage &Info) const override;
      80             : 
      81             : protected:
      82             :   /// Optional passes call this function to check whether the pass should be
      83             :   /// skipped. This is the case when optimization bisect is over the limit.
      84             :   bool skipSCC(CallGraphSCC &SCC) const;
      85             : };
      86             : 
      87             : /// CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
      88       21283 : class CallGraphSCC {
      89             :   const CallGraph &CG; // The call graph for this SCC.
      90             :   void *Context; // The CGPassManager object that is vending this.
      91             :   std::vector<CallGraphNode *> Nodes;
      92             : 
      93             : public:
      94       21292 :   CallGraphSCC(CallGraph &cg, void *context) : CG(cg), Context(context) {}
      95             : 
      96             :   void initialize(ArrayRef<CallGraphNode *> NewNodes) {
      97          86 :     Nodes.assign(NewNodes.begin(), NewNodes.end());
      98             :   }
      99             : 
     100     1399010 :   bool isSingular() const { return Nodes.size() == 1; }
     101          24 :   unsigned size() const { return Nodes.size(); }
     102             : 
     103             :   /// ReplaceNode - This informs the SCC and the pass manager that the specified
     104             :   /// Old node has been deleted, and New is to be used in its place.
     105             :   void ReplaceNode(CallGraphNode *Old, CallGraphNode *New);
     106             : 
     107             :   using iterator = std::vector<CallGraphNode *>::const_iterator;
     108             : 
     109     2509193 :   iterator begin() const { return Nodes.begin(); }
     110     2509193 :   iterator end() const { return Nodes.end(); }
     111             : 
     112           0 :   const CallGraph &getCallGraph() { return CG; }
     113             : };
     114             : 
     115             : void initializeDummyCGSCCPassPass(PassRegistry &);
     116             : 
     117             : /// This pass is required by interprocedural register allocation. It forces
     118             : /// codegen to follow bottom up order on call graph.
     119             : class DummyCGSCCPass : public CallGraphSCCPass {
     120             : public:
     121             :   static char ID;
     122             : 
     123        1970 :   DummyCGSCCPass() : CallGraphSCCPass(ID) {
     124        1970 :     PassRegistry &Registry = *PassRegistry::getPassRegistry();
     125        1970 :     initializeDummyCGSCCPassPass(Registry);
     126             :   }
     127             : 
     128       27585 :   bool runOnSCC(CallGraphSCC &SCC) override { return false; }
     129             : 
     130        1960 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
     131             :     AU.setPreservesAll();
     132        1960 :   }
     133             : };
     134             : 
     135             : } // end namespace llvm
     136             : 
     137             : #endif // LLVM_ANALYSIS_CALLGRAPHSCCPASS_H