Home | History | Annotate | Download | only in Analysis 
      1 //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- 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 DominanceFrontier class, which calculate and holds the
     11 // dominance frontier for a function.
     12 //
     13 // This should be considered deprecated, don't add any more uses of this data
     14 // structure.
     15 //
     16 //===----------------------------------------------------------------------===//
     17 
     18 #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H
     19 #define LLVM_ANALYSIS_DOMINANCEFRONTIER_H
     20 
     21 #include "llvm/IR/Dominators.h"
     22 #include "llvm/IR/PassManager.h"
     23 #include <map>
     24 #include <set>
     25 
     26 namespace llvm {
     27 
     28 //===----------------------------------------------------------------------===//
     29 /// DominanceFrontierBase - Common base class for computing forward and inverse
     30 /// dominance frontiers for a function.
     31 ///
     32 template <class BlockT>
     33 class DominanceFrontierBase {
     34 public:
     35   typedef std::set<BlockT *> DomSetType;                // Dom set for a bb
     36   typedef std::map<BlockT *, DomSetType> DomSetMapType; // Dom set map
     37 
     38 protected:
     39   typedef GraphTraits<BlockT *> BlockTraits;
     40 
     41   DomSetMapType Frontiers;
     42   std::vector<BlockT *> Roots;
     43   const bool IsPostDominators;
     44 
     45 public:
     46   DominanceFrontierBase(bool isPostDom) : IsPostDominators(isPostDom) {}
     47 
     48   /// getRoots - Return the root blocks of the current CFG.  This may include
     49   /// multiple blocks if we are computing post dominators.  For forward
     50   /// dominators, this will always be a single block (the entry node).
     51   ///
     52   inline const std::vector<BlockT *> &getRoots() const {
     53     return Roots;
     54   }
     55 
     56   BlockT *getRoot() const {
     57     assert(Roots.size() == 1 && "Should always have entry node!");
     58     return Roots[0];
     59   }
     60 
     61   /// isPostDominator - Returns true if analysis based of postdoms
     62   ///
     63   bool isPostDominator() const {
     64     return IsPostDominators;
     65   }
     66 
     67   void releaseMemory() {
     68     Frontiers.clear();
     69   }
     70 
     71   // Accessor interface:
     72   typedef typename DomSetMapType::iterator iterator;
     73   typedef typename DomSetMapType::const_iterator const_iterator;
     74   iterator begin() { return Frontiers.begin(); }
     75   const_iterator begin() const { return Frontiers.begin(); }
     76   iterator end() { return Frontiers.end(); }
     77   const_iterator end() const { return Frontiers.end(); }
     78   iterator find(BlockT *B) { return Frontiers.find(B); }
     79   const_iterator find(BlockT *B) const { return Frontiers.find(B); }
     80 
     81   iterator addBasicBlock(BlockT *BB, const DomSetType &frontier) {
     82     assert(find(BB) == end() && "Block already in DominanceFrontier!");
     83     return Frontiers.insert(std::make_pair(BB, frontier)).first;
     84   }
     85 
     86   /// removeBlock - Remove basic block BB's frontier.
     87   void removeBlock(BlockT *BB);
     88 
     89   void addToFrontier(iterator I, BlockT *Node);
     90 
     91   void removeFromFrontier(iterator I, BlockT *Node);
     92 
     93   /// compareDomSet - Return false if two domsets match. Otherwise
     94   /// return true;
     95   bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const;
     96 
     97   /// compare - Return true if the other dominance frontier base matches
     98   /// this dominance frontier base. Otherwise return false.
     99   bool compare(DominanceFrontierBase<BlockT> &Other) const;
    100 
    101   /// print - Convert to human readable form
    102   ///
    103   void print(raw_ostream &OS) const;
    104 
    105   /// dump - Dump the dominance frontier to dbgs().
    106 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    107   void dump() const;
    108 #endif
    109 };
    110 
    111 //===-------------------------------------
    112 /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
    113 /// used to compute a forward dominator frontiers.
    114 ///
    115 template <class BlockT>
    116 class ForwardDominanceFrontierBase : public DominanceFrontierBase<BlockT> {
    117 private:
    118   typedef GraphTraits<BlockT *> BlockTraits;
    119 
    120 public:
    121   typedef DominatorTreeBase<BlockT> DomTreeT;
    122   typedef DomTreeNodeBase<BlockT> DomTreeNodeT;
    123   typedef typename DominanceFrontierBase<BlockT>::DomSetType DomSetType;
    124 
    125   ForwardDominanceFrontierBase() : DominanceFrontierBase<BlockT>(false) {}
    126 
    127   void analyze(DomTreeT &DT) {
    128     this->Roots = DT.getRoots();
    129     assert(this->Roots.size() == 1 &&
    130            "Only one entry block for forward domfronts!");
    131     calculate(DT, DT[this->Roots[0]]);
    132   }
    133 
    134   const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node);
    135 };
    136 
    137 class DominanceFrontier : public ForwardDominanceFrontierBase<BasicBlock> {
    138 public:
    139   typedef DominatorTreeBase<BasicBlock> DomTreeT;
    140   typedef DomTreeNodeBase<BasicBlock> DomTreeNodeT;
    141   typedef DominanceFrontierBase<BasicBlock>::DomSetType DomSetType;
    142   typedef DominanceFrontierBase<BasicBlock>::iterator iterator;
    143   typedef DominanceFrontierBase<BasicBlock>::const_iterator const_iterator;
    144 
    145   /// Handle invalidation explicitly.
    146   bool invalidate(Function &F, const PreservedAnalyses &PA,
    147                   FunctionAnalysisManager::Invalidator &);
    148 };
    149 
    150 class DominanceFrontierWrapperPass : public FunctionPass {
    151   DominanceFrontier DF;
    152 public:
    153   static char ID; // Pass ID, replacement for typeid
    154 
    155   DominanceFrontierWrapperPass();
    156 
    157   DominanceFrontier &getDominanceFrontier() { return DF; }
    158   const DominanceFrontier &getDominanceFrontier() const { return DF;  }
    159 
    160   void releaseMemory() override;
    161 
    162   bool runOnFunction(Function &) override;
    163 
    164   void getAnalysisUsage(AnalysisUsage &AU) const override;
    165 
    166   void print(raw_ostream &OS, const Module * = nullptr) const override;
    167 
    168   void dump() const;
    169 };
    170 
    171 extern template class DominanceFrontierBase<BasicBlock>;
    172 extern template class ForwardDominanceFrontierBase<BasicBlock>;
    173 
    174 /// \brief Analysis pass which computes a \c DominanceFrontier.
    175 class DominanceFrontierAnalysis
    176     : public AnalysisInfoMixin<DominanceFrontierAnalysis> {
    177   friend AnalysisInfoMixin<DominanceFrontierAnalysis>;
    178   static AnalysisKey Key;
    179 
    180 public:
    181   /// \brief Provide the result typedef for this analysis pass.
    182   typedef DominanceFrontier Result;
    183 
    184   /// \brief Run the analysis pass over a function and produce a dominator tree.
    185   DominanceFrontier run(Function &F, FunctionAnalysisManager &AM);
    186 };
    187 
    188 /// \brief Printer pass for the \c DominanceFrontier.
    189 class DominanceFrontierPrinterPass
    190     : public PassInfoMixin<DominanceFrontierPrinterPass> {
    191   raw_ostream &OS;
    192 
    193 public:
    194   explicit DominanceFrontierPrinterPass(raw_ostream &OS);
    195   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
    196 };
    197 
    198 } // End llvm namespace
    199 
    200 #endif
    201