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