Home | History | Annotate | Download | only in Analysis 
      1 //=- llvm/Analysis/PostDominators.h - Post Dominator Calculation --*- 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 exposes interfaces to post dominance information.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #ifndef LLVM_ANALYSIS_POSTDOMINATORS_H
     15 #define LLVM_ANALYSIS_POSTDOMINATORS_H
     16 
     17 #include "llvm/ADT/DepthFirstIterator.h"
     18 #include "llvm/IR/Dominators.h"
     19 #include "llvm/IR/PassManager.h"
     20 #include "llvm/Pass.h"
     21 
     22 namespace llvm {
     23 
     24 class Function;
     25 class raw_ostream;
     26 
     27 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
     28 /// compute the post-dominator tree.
     29 struct PostDominatorTree : public PostDomTreeBase<BasicBlock> {
     30   using Base = PostDomTreeBase<BasicBlock>;
     31 
     32   /// Handle invalidation explicitly.
     33   bool invalidate(Function &F, const PreservedAnalyses &PA,
     34                   FunctionAnalysisManager::Invalidator &);
     35 };
     36 
     37 /// \brief Analysis pass which computes a \c PostDominatorTree.
     38 class PostDominatorTreeAnalysis
     39     : public AnalysisInfoMixin<PostDominatorTreeAnalysis> {
     40   friend AnalysisInfoMixin<PostDominatorTreeAnalysis>;
     41 
     42   static AnalysisKey Key;
     43 
     44 public:
     45   /// \brief Provide the result type for this analysis pass.
     46   using Result = PostDominatorTree;
     47 
     48   /// \brief Run the analysis pass over a function and produce a post dominator
     49   ///        tree.
     50   PostDominatorTree run(Function &F, FunctionAnalysisManager &);
     51 };
     52 
     53 /// \brief Printer pass for the \c PostDominatorTree.
     54 class PostDominatorTreePrinterPass
     55     : public PassInfoMixin<PostDominatorTreePrinterPass> {
     56   raw_ostream &OS;
     57 
     58 public:
     59   explicit PostDominatorTreePrinterPass(raw_ostream &OS);
     60 
     61   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     62 };
     63 
     64 struct PostDominatorTreeWrapperPass : public FunctionPass {
     65   static char ID; // Pass identification, replacement for typeid
     66 
     67   PostDominatorTree DT;
     68 
     69   PostDominatorTreeWrapperPass() : FunctionPass(ID) {
     70     initializePostDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
     71   }
     72 
     73   PostDominatorTree &getPostDomTree() { return DT; }
     74   const PostDominatorTree &getPostDomTree() const { return DT; }
     75 
     76   bool runOnFunction(Function &F) override;
     77 
     78   void getAnalysisUsage(AnalysisUsage &AU) const override {
     79     AU.setPreservesAll();
     80   }
     81 
     82   void releaseMemory() override {
     83     DT.releaseMemory();
     84   }
     85 
     86   void print(raw_ostream &OS, const Module*) const override;
     87 };
     88 
     89 FunctionPass* createPostDomTree();
     90 
     91 template <> struct GraphTraits<PostDominatorTree*>
     92   : public GraphTraits<DomTreeNode*> {
     93   static NodeRef getEntryNode(PostDominatorTree *DT) {
     94     return DT->getRootNode();
     95   }
     96 
     97   static nodes_iterator nodes_begin(PostDominatorTree *N) {
     98     if (getEntryNode(N))
     99       return df_begin(getEntryNode(N));
    100     else
    101       return df_end(getEntryNode(N));
    102   }
    103 
    104   static nodes_iterator nodes_end(PostDominatorTree *N) {
    105     return df_end(getEntryNode(N));
    106   }
    107 };
    108 
    109 } // end namespace llvm
    110 
    111 #endif // LLVM_ANALYSIS_POSTDOMINATORS_H
    112