Home | History | Annotate | Download | only in Analysis 
      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   virtual bool doInitialization(CallGraph &CG) {
     50     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   virtual bool doFinalization(CallGraph &CG) {
     65     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   PassManagerType getPotentialPassManagerType() const override {
     73     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 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   CallGraphSCC(CallGraph &cg, void *context) : CG(cg), Context(context) {}
     95 
     96   void initialize(ArrayRef<CallGraphNode *> NewNodes) {
     97     Nodes.assign(NewNodes.begin(), NewNodes.end());
     98   }
     99 
    100   bool isSingular() const { return Nodes.size() == 1; }
    101   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   iterator begin() const { return Nodes.begin(); }
    110   iterator end() const { return Nodes.end(); }
    111 
    112   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   DummyCGSCCPass() : CallGraphSCCPass(ID) {
    124     PassRegistry &Registry = *PassRegistry::getPassRegistry();
    125     initializeDummyCGSCCPassPass(Registry);
    126   }
    127 
    128   bool runOnSCC(CallGraphSCC &SCC) override { return false; }
    129 
    130   void getAnalysisUsage(AnalysisUsage &AU) const override {
    131     AU.setPreservesAll();
    132   }
    133 };
    134 
    135 } // end namespace llvm
    136 
    137 #endif // LLVM_ANALYSIS_CALLGRAPHSCCPASS_H
    138