contrib/llvm/include/llvm/Analysis/DominanceFrontier.h

   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
 146 class DominanceFrontierWrapperPass : public FunctionPass {
 147   DominanceFrontier DF;
 148 public:
 149   static char ID; // Pass ID, replacement for typeid
 150
 151   DominanceFrontierWrapperPass();
 152
 153   DominanceFrontier &getDominanceFrontier() { return DF; }
 154   const DominanceFrontier &getDominanceFrontier() const { return DF;  }
 155
 156   void releaseMemory() override;
 157
 158   bool runOnFunction(Function &) override;
 159
 160   void getAnalysisUsage(AnalysisUsage &AU) const override;
 161
 162   void print(raw_ostream &OS, const Module * = nullptr) const override;
 163
 164   void dump() const;
 165 };
 166
 167 extern template class DominanceFrontierBase<BasicBlock>;
 168 extern template class ForwardDominanceFrontierBase<BasicBlock>;
 169
 170 /// \brief Analysis pass which computes a \c DominanceFrontier.
 171 class DominanceFrontierAnalysis
 172     : public AnalysisInfoMixin<DominanceFrontierAnalysis> {
 173   friend AnalysisInfoMixin<DominanceFrontierAnalysis>;
 174   static char PassID;
 175
 176 public:
 177   /// \brief Provide the result typedef for this analysis pass.
 178   typedef DominanceFrontier Result;
 179
 180   /// \brief Run the analysis pass over a function and produce a dominator tree.
 181   DominanceFrontier run(Function &F, AnalysisManager<Function> &AM);
 182 };
 183
 184 /// \brief Printer pass for the \c DominanceFrontier.
 185 class DominanceFrontierPrinterPass
 186     : public PassInfoMixin<DominanceFrontierPrinterPass> {
 187   raw_ostream &OS;
 188
 189 public:
 190   explicit DominanceFrontierPrinterPass(raw_ostream &OS);
 191   PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM);
 192 };
 193
 194 } // End llvm namespace
 195
 196 #endif