Home | History | Annotate | Line # | Download | only in Analysis 
      1 //=- llvm/Analysis/PostDominators.h - Post Dominator Calculation --*- C++ -*-=//
      2 //
      3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
      4 // See https://llvm.org/LICENSE.txt for license information.
      5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
      6 //
      7 //===----------------------------------------------------------------------===//
      8 //
      9 // This file exposes interfaces to post dominance information.
     10 //
     11 //===----------------------------------------------------------------------===//
     12 
     13 #ifndef LLVM_ANALYSIS_POSTDOMINATORS_H
     14 #define LLVM_ANALYSIS_POSTDOMINATORS_H
     15 
     16 #include "llvm/ADT/DepthFirstIterator.h"
     17 #include "llvm/IR/Dominators.h"
     18 #include "llvm/IR/PassManager.h"
     19 #include "llvm/Pass.h"
     20 
     21 namespace llvm {
     22 
     23 class Function;
     24 class raw_ostream;
     25 
     26 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
     27 /// compute the post-dominator tree.
     28 class PostDominatorTree : public PostDomTreeBase<BasicBlock> {
     29 public:
     30   using Base = PostDomTreeBase<BasicBlock>;
     31 
     32   PostDominatorTree() = default;
     33   explicit PostDominatorTree(Function &F) { recalculate(F); }
     34   /// Handle invalidation explicitly.
     35   bool invalidate(Function &F, const PreservedAnalyses &PA,
     36                   FunctionAnalysisManager::Invalidator &);
     37 
     38   // Ensure base-class overloads are visible.
     39   using Base::dominates;
     40 
     41   /// Return true if \p I1 dominates \p I2. This checks if \p I2 comes before
     42   /// \p I1 if they belongs to the same basic block.
     43   bool dominates(const Instruction *I1, const Instruction *I2) const;
     44 };
     45 
     46 /// Analysis pass which computes a \c PostDominatorTree.
     47 class PostDominatorTreeAnalysis
     48     : public AnalysisInfoMixin<PostDominatorTreeAnalysis> {
     49   friend AnalysisInfoMixin<PostDominatorTreeAnalysis>;
     50 
     51   static AnalysisKey Key;
     52 
     53 public:
     54   /// Provide the result type for this analysis pass.
     55   using Result = PostDominatorTree;
     56 
     57   /// Run the analysis pass over a function and produce a post dominator
     58   ///        tree.
     59   PostDominatorTree run(Function &F, FunctionAnalysisManager &);
     60 };
     61 
     62 /// Printer pass for the \c PostDominatorTree.
     63 class PostDominatorTreePrinterPass
     64     : public PassInfoMixin<PostDominatorTreePrinterPass> {
     65   raw_ostream &OS;
     66 
     67 public:
     68   explicit PostDominatorTreePrinterPass(raw_ostream &OS);
     69 
     70   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     71 };
     72 
     73 struct PostDominatorTreeWrapperPass : public FunctionPass {
     74   static char ID; // Pass identification, replacement for typeid
     75 
     76   PostDominatorTree DT;
     77 
     78   PostDominatorTreeWrapperPass();
     79 
     80   PostDominatorTree &getPostDomTree() { return DT; }
     81   const PostDominatorTree &getPostDomTree() const { return DT; }
     82 
     83   bool runOnFunction(Function &F) override;
     84 
     85   void verifyAnalysis() const override;
     86 
     87   void getAnalysisUsage(AnalysisUsage &AU) const override {
     88     AU.setPreservesAll();
     89   }
     90 
     91   void releaseMemory() override { DT.reset(); }
     92 
     93   void print(raw_ostream &OS, const Module*) const override;
     94 };
     95 
     96 FunctionPass* createPostDomTree();
     97 
     98 template <> struct GraphTraits<PostDominatorTree*>
     99   : public GraphTraits<DomTreeNode*> {
    100   static NodeRef getEntryNode(PostDominatorTree *DT) {
    101     return DT->getRootNode();
    102   }
    103 
    104   static nodes_iterator nodes_begin(PostDominatorTree *N) {
    105     if (getEntryNode(N))
    106       return df_begin(getEntryNode(N));
    107     else
    108       return df_end(getEntryNode(N));
    109   }
    110 
    111   static nodes_iterator nodes_end(PostDominatorTree *N) {
    112     return df_end(getEntryNode(N));
    113   }
    114 };
    115 
    116 } // end namespace llvm
    117 
    118 #endif // LLVM_ANALYSIS_POSTDOMINATORS_H
    119