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