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: DominanceFrontierBase(bool isPostDom)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 /// getRoots()51 inline const std::vector<BlockT *> &getRoots() const { 52 return Roots; 53 } 54 getRoot()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 /// isPostDominator()62 bool isPostDominator() const { 63 return IsPostDominators; 64 } 65 releaseMemory()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; begin()73 iterator begin() { return Frontiers.begin(); } begin()74 const_iterator begin() const { return Frontiers.begin(); } end()75 iterator end() { return Frontiers.end(); } end()76 const_iterator end() const { return Frontiers.end(); } find(BlockT * B)77 iterator find(BlockT *B) { return Frontiers.find(B); } find(BlockT * B)78 const_iterator find(BlockT *B) const { return Frontiers.find(B); } 79 addBasicBlock(BlockT * BB,const DomSetType & frontier)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 ForwardDominanceFrontierBase()124 ForwardDominanceFrontierBase() : DominanceFrontierBase<BlockT>(false) {} 125 analyze(DomTreeT & DT)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 getBase()150 ForwardDominanceFrontierBase<BasicBlock> &getBase() { return Base; } 151 getRoots()152 inline const std::vector<BasicBlock *> &getRoots() const { 153 return Base.getRoots(); 154 } 155 getRoot()156 BasicBlock *getRoot() const { return Base.getRoot(); } 157 isPostDominator()158 bool isPostDominator() const { return Base.isPostDominator(); } 159 begin()160 iterator begin() { return Base.begin(); } 161 begin()162 const_iterator begin() const { return Base.begin(); } 163 end()164 iterator end() { return Base.end(); } 165 end()166 const_iterator end() const { return Base.end(); } 167 find(BasicBlock * B)168 iterator find(BasicBlock *B) { return Base.find(B); } 169 find(BasicBlock * B)170 const_iterator find(BasicBlock *B) const { return Base.find(B); } 171 addBasicBlock(BasicBlock * BB,const DomSetType & frontier)172 iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { 173 return Base.addBasicBlock(BB, frontier); 174 } 175 removeBlock(BasicBlock * BB)176 void removeBlock(BasicBlock *BB) { return Base.removeBlock(BB); } 177 addToFrontier(iterator I,BasicBlock * Node)178 void addToFrontier(iterator I, BasicBlock *Node) { 179 return Base.addToFrontier(I, Node); 180 } 181 removeFromFrontier(iterator I,BasicBlock * Node)182 void removeFromFrontier(iterator I, BasicBlock *Node) { 183 return Base.removeFromFrontier(I, Node); 184 } 185 compareDomSet(DomSetType & DS1,const DomSetType & DS2)186 bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const { 187 return Base.compareDomSet(DS1, DS2); 188 } 189 compare(DominanceFrontierBase<BasicBlock> & Other)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 211