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