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