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