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   void dump() const;
 106 };
 107
 108 //===-------------------------------------
 109 /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
 110 /// used to compute a forward dominator frontiers.
 111 ///
 112 template <class BlockT>
 113 class ForwardDominanceFrontierBase : public DominanceFrontierBase<BlockT> {
 114 private:
 115   typedef GraphTraits<BlockT *> BlockTraits;
 116
 117 public:
 118   typedef DominatorTreeBase<BlockT> DomTreeT;
 119   typedef DomTreeNodeBase<BlockT> DomTreeNodeT;
 120   typedef typename DominanceFrontierBase<BlockT>::DomSetType DomSetType;
 121
 122   ForwardDominanceFrontierBase() : DominanceFrontierBase<BlockT>(false) {}
 123
 124   void analyze(DomTreeT &DT) {
 125     this->Roots = DT.getRoots();
 126     assert(this->Roots.size() == 1 &&
 127            "Only one entry block for forward domfronts!");
 128     calculate(DT, DT[this->Roots[0]]);
 129   }
 130
 131   const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node);
 132 };
 133
 134 class DominanceFrontier : public FunctionPass {
 135   ForwardDominanceFrontierBase<BasicBlock> Base;
 136
 137 public:
 138   typedef DominatorTreeBase<BasicBlock> DomTreeT;
 139   typedef DomTreeNodeBase<BasicBlock> DomTreeNodeT;
 140   typedef DominanceFrontierBase<BasicBlock>::DomSetType DomSetType;
 141   typedef DominanceFrontierBase<BasicBlock>::iterator iterator;
 142   typedef DominanceFrontierBase<BasicBlock>::const_iterator const_iterator;
 143
 144   static char ID; // Pass ID, replacement for typeid
 145
 146   DominanceFrontier();
 147
 148   ForwardDominanceFrontierBase<BasicBlock> &getBase() { return Base; }
 149
 150   inline const std::vector<BasicBlock *> &getRoots() const {
 151     return Base.getRoots();
 152   }
 153
 154   BasicBlock *getRoot() const { return Base.getRoot(); }
 155
 156   bool isPostDominator() const { return Base.isPostDominator(); }
 157
 158   iterator begin() { return Base.begin(); }
 159
 160   const_iterator begin() const { return Base.begin(); }
 161
 162   iterator end() { return Base.end(); }
 163
 164   const_iterator end() const { return Base.end(); }
 165
 166   iterator find(BasicBlock *B) { return Base.find(B); }
 167
 168   const_iterator find(BasicBlock *B) const { return Base.find(B); }
 169
 170   iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
 171     return Base.addBasicBlock(BB, frontier);
 172   }
 173
 174   void removeBlock(BasicBlock *BB) { return Base.removeBlock(BB); }
 175
 176   void addToFrontier(iterator I, BasicBlock *Node) {
 177     return Base.addToFrontier(I, Node);
 178   }
 179
 180   void removeFromFrontier(iterator I, BasicBlock *Node) {
 181     return Base.removeFromFrontier(I, Node);
 182   }
 183
 184   bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const {
 185     return Base.compareDomSet(DS1, DS2);
 186   }
 187
 188   bool compare(DominanceFrontierBase<BasicBlock> &Other) const {
 189     return Base.compare(Other);
 190   }
 191
 192   void releaseMemory() override;
 193
 194   bool runOnFunction(Function &) override;
 195
 196   void getAnalysisUsage(AnalysisUsage &AU) const override;
 197
 198   void print(raw_ostream &OS, const Module * = nullptr) const override;
 199
 200   void dump() const;
 201 };
 202
 203 EXTERN_TEMPLATE_INSTANTIATION(class DominanceFrontierBase<BasicBlock>);
 204 EXTERN_TEMPLATE_INSTANTIATION(class ForwardDominanceFrontierBase<BasicBlock>);
 205
 206 } // End llvm namespace
 207
 208 #endif