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