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/Analysis/CallGraph.h"
     25 #include "llvm/Pass.h"
     26 #include "llvm/PassSupport.h"
     27 
     28 namespace llvm {
     29 
     30 class CallGraphNode;
     31 class CallGraph;
     32 class PMStack;
     33 class CallGraphSCC;
     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 &O,
     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   ///
     61   virtual bool runOnSCC(CallGraphSCC &SCC) = 0;
     62 
     63   /// doFinalization - This method is called after the SCC's of the program has
     64   /// been processed, allowing the pass to do final cleanup as necessary.
     65   virtual bool doFinalization(CallGraph &CG) {
     66     return false;
     67   }
     68 
     69   /// Assign pass manager to manager this pass
     70   void assignPassManager(PMStack &PMS, PassManagerType PMT) override;
     71 
     72   ///  Return what kind of Pass Manager can manage this pass.
     73   PassManagerType getPotentialPassManagerType() const override {
     74     return PMT_CallGraphPassManager;
     75   }
     76 
     77   /// getAnalysisUsage - For this class, we declare that we require and preserve
     78   /// the call graph.  If the derived class implements this method, it should
     79   /// always explicitly call the implementation here.
     80   void getAnalysisUsage(AnalysisUsage &Info) const override;
     81 
     82 protected:
     83   /// Optional passes call this function to check whether the pass should be
     84   /// skipped. This is the case when optimization bisect is over the limit.
     85   bool skipSCC(CallGraphSCC &SCC) const;
     86 };
     87 
     88 /// CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
     89 class CallGraphSCC {
     90   const CallGraph &CG; // The call graph for this SCC.
     91   void *Context; // The CGPassManager object that is vending this.
     92   std::vector<CallGraphNode*> Nodes;
     93 
     94 public:
     95   CallGraphSCC(CallGraph &cg, void *context) : CG(cg), Context(context) {}
     96 
     97   void initialize(ArrayRef<CallGraphNode *> NewNodes) {
     98     Nodes.assign(NewNodes.begin(), NewNodes.end());
     99   }
    100 
    101   bool isSingular() const { return Nodes.size() == 1; }
    102   unsigned size() const { return Nodes.size(); }
    103 
    104   /// ReplaceNode - This informs the SCC and the pass manager that the specified
    105   /// Old node has been deleted, and New is to be used in its place.
    106   void ReplaceNode(CallGraphNode *Old, CallGraphNode *New);
    107 
    108   typedef std::vector<CallGraphNode *>::const_iterator iterator;
    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   DummyCGSCCPass() : CallGraphSCCPass(ID) {
    123     PassRegistry &Registry = *PassRegistry::getPassRegistry();
    124     initializeDummyCGSCCPassPass(Registry);
    125   };
    126   bool runOnSCC(CallGraphSCC &SCC) override { return false; }
    127   void getAnalysisUsage(AnalysisUsage &AU) const override {
    128     AU.setPreservesAll();
    129   }
    130 };
    131 
    132 } // End llvm namespace
    133 
    134 #endif
    135