1 //===- Dominance.h - Dominator analysis for regions -------------*- 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 // The DominanceInfo and PostDominanceInfo class provide routines for performimg 10 // simple dominance checks, and expose dominator trees for advanced clients. 11 // These classes provide fully region-aware functionality, lazily constructing 12 // dominator information for any multi-block regions that need it. 13 // 14 // For more information about the theory behind dominance in graphs algorithms, 15 // see: https://en.wikipedia.org/wiki/Dominator_(graph_theory) 16 // 17 //===----------------------------------------------------------------------===// 18 19 #ifndef MLIR_IR_DOMINANCE_H 20 #define MLIR_IR_DOMINANCE_H 21 22 #include "mlir/IR/RegionGraphTraits.h" 23 #include "llvm/Support/GenericDomTree.h" 24 25 extern template class llvm::DominatorTreeBase<mlir::Block, false>; 26 extern template class llvm::DominatorTreeBase<mlir::Block, true>; 27 extern template class llvm::DomTreeNodeBase<mlir::Block>; 28 29 namespace mlir { 30 using DominanceInfoNode = llvm::DomTreeNodeBase<Block>; 31 class Operation; 32 33 namespace detail { 34 template <bool IsPostDom> 35 class DominanceInfoBase { 36 using DomTree = llvm::DominatorTreeBase<Block, IsPostDom>; 37 38 public: 39 DominanceInfoBase(Operation *op = nullptr) {} 40 DominanceInfoBase(DominanceInfoBase &&) = default; 41 DominanceInfoBase &operator=(DominanceInfoBase &&) = default; 42 ~DominanceInfoBase(); 43 44 DominanceInfoBase(const DominanceInfoBase &) = delete; 45 DominanceInfoBase &operator=(const DominanceInfoBase &) = delete; 46 47 /// Invalidate dominance info. This can be used by clients that make major 48 /// changes to the CFG and don't have a good way to update it. 49 void invalidate(); 50 void invalidate(Region *region); 51 52 /// Finds the nearest common dominator block for the two given blocks a 53 /// and b. If no common dominator can be found, this function will return 54 /// nullptr. 55 Block *findNearestCommonDominator(Block *a, Block *b) const; 56 57 /// Finds the nearest common dominator block for the given range of blocks. 58 /// If no common dominator can be found, this function will return nullptr. 59 template <typename BlockRangeT> 60 Block *findNearestCommonDominator(BlockRangeT &&blocks) const { 61 if (blocks.begin() == blocks.end()) 62 return nullptr; 63 Block *dom = *blocks.begin(); 64 for (auto it = ++blocks.begin(); it != blocks.end(); ++it) { 65 dom = findNearestCommonDominator(dom, *it); 66 if (!dom) 67 return nullptr; 68 } 69 return dom; 70 } 71 72 /// Get the root dominance node of the given region. Note that this operation 73 /// is only defined for multi-block regions! 74 DominanceInfoNode *getRootNode(Region *region) { 75 auto domInfo = getDominanceInfo(region, /*needsDomTree*/ true).getPointer(); 76 assert(domInfo && "Region isn't multiblock"); 77 return domInfo->getRootNode(); 78 } 79 80 /// Return the dominance node from the Region containing block A. This only 81 /// works for multi-block regions. 82 DominanceInfoNode *getNode(Block *a) { 83 return getDomTree(a->getParent()).getNode(a); 84 } 85 86 /// Return true if the specified block is reachable from the entry 87 /// block of its region. 88 bool isReachableFromEntry(Block *a) const; 89 90 /// Return true if operations in the specified block are known to obey SSA 91 /// dominance requirements. False if the block is a graph region or unknown. 92 bool hasSSADominance(Block *block) const { 93 return hasSSADominance(block->getParent()); 94 } 95 /// Return true if operations in the specified block are known to obey SSA 96 /// dominance requirements. False if the block is a graph region or unknown. 97 bool hasSSADominance(Region *region) const { 98 return getDominanceInfo(region, /*needsDomTree=*/false).getInt(); 99 } 100 101 DomTree &getDomTree(Region *region) const { 102 assert(!region->hasOneBlock() && 103 "Can't get DomTree for single block regions"); 104 return *getDominanceInfo(region, /*needsDomTree=*/true).getPointer(); 105 } 106 107 protected: 108 using super = DominanceInfoBase<IsPostDom>; 109 110 /// Return the dom tree and "hasSSADominance" bit for the given region. The 111 /// DomTree will be null for single-block regions. This lazily constructs the 112 /// DomTree on demand when needsDomTree=true. 113 llvm::PointerIntPair<DomTree *, 1, bool> 114 getDominanceInfo(Region *region, bool needsDomTree) const; 115 116 /// Return "true" if block iterator A properly (post)dominates block iterator 117 /// B. If `enclosingOk` is set, A is considered to (post)dominate B if A 118 /// encloses B. 119 bool properlyDominatesImpl(Block *aBlock, Block::iterator aIt, Block *bBlock, 120 Block::iterator bIt, 121 bool enclosingOk = true) const; 122 123 /// A mapping of regions to their base dominator tree and a cached 124 /// "hasSSADominance" bit. This map does not contain dominator trees for 125 /// single block CFG regions, but we do want to cache the "hasSSADominance" 126 /// bit for them. We may also not have computed the DomTree yet. In either 127 /// case, the DomTree is just null. 128 /// 129 mutable DenseMap<Region *, llvm::PointerIntPair<DomTree *, 1, bool>> 130 dominanceInfos; 131 }; 132 133 extern template class DominanceInfoBase</*IsPostDom=*/true>; 134 extern template class DominanceInfoBase</*IsPostDom=*/false>; 135 } // namespace detail 136 137 /// A class for computing basic dominance information. Note that this 138 /// class is aware of different types of regions and returns a 139 /// region-kind specific concept of dominance. See RegionKindInterface. 140 class DominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/false> { 141 public: 142 using super::super; 143 144 /// Return true if operation A properly dominates operation B, i.e. if A and B 145 /// are in the same block and A properly dominates B within the block, or if 146 /// the block that contains A properly dominates the block that contains B. In 147 /// an SSACFG region, Operation A dominates Operation B in the same block if A 148 /// preceeds B. In a Graph region, all operations in a block properly dominate 149 /// all operations in the same block. 150 /// 151 /// The `enclosingOpOk` flag says whether we should return true if the B op 152 /// is enclosed by a region on A. 153 bool properlyDominates(Operation *a, Operation *b, 154 bool enclosingOpOk = true) const; 155 156 /// Return true if operation A dominates operation B, i.e. if A and B are the 157 /// same operation or A properly dominates B. 158 bool dominates(Operation *a, Operation *b) const { 159 return a == b || properlyDominates(a, b); 160 } 161 162 /// Return true if the `a` value properly dominates operation `b`, i.e if the 163 /// operation that defines `a` properlyDominates `b` and the operation that 164 /// defines `a` does not contain `b`. 165 bool properlyDominates(Value a, Operation *b) const; 166 167 /// Return true if the `a` value dominates operation `b`. 168 bool dominates(Value a, Operation *b) const { 169 return (Operation *)a.getDefiningOp() == b || properlyDominates(a, b); 170 } 171 172 /// Return true if the specified block A dominates block B, i.e. if block A 173 /// and block B are the same block or block A properly dominates block B. 174 bool dominates(Block *a, Block *b) const { 175 return a == b || properlyDominates(a, b); 176 } 177 178 /// Return true if the specified block A properly dominates block B, i.e.: if 179 /// block A contains block B, or if the region which contains block A also 180 /// contains block B or some parent of block B and block A dominates that 181 /// block in that kind of region. 182 /// 183 /// In an SSACFG region, block A dominates block B if all control flow paths 184 /// from the entry block to block B flow through block A. 185 /// 186 /// Graph regions have only a single block. To be consistent with "proper 187 /// dominance" of ops, the single block is considered to properly dominate 188 /// itself in a graph region. 189 bool properlyDominates(Block *a, Block *b) const; 190 191 bool properlyDominates(Block *aBlock, Block::iterator aIt, Block *bBlock, 192 Block::iterator bIt, bool enclosingOk = true) const { 193 return super::properlyDominatesImpl(aBlock, aIt, bBlock, bIt, enclosingOk); 194 } 195 196 bool dominates(Block *aBlock, Block::iterator aIt, Block *bBlock, 197 Block::iterator bIt, bool enclosingOk = true) const { 198 return (aBlock == bBlock && aIt == bIt) || 199 super::properlyDominatesImpl(aBlock, aIt, bBlock, bIt, enclosingOk); 200 } 201 }; 202 203 /// A class for computing basic postdominance information. 204 class PostDominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/true> { 205 public: 206 using super::super; 207 208 /// Return true if operation A properly postdominates operation B. 209 bool properlyPostDominates(Operation *a, Operation *b, 210 bool enclosingOpOk = true) const; 211 212 /// Return true if operation A postdominates operation B. 213 bool postDominates(Operation *a, Operation *b) const { 214 return a == b || properlyPostDominates(a, b); 215 } 216 217 /// Return true if the specified block A properly postdominates block B. 218 bool properlyPostDominates(Block *a, Block *b) const; 219 220 /// Return true if the specified block A postdominates block B. 221 bool postDominates(Block *a, Block *b) const { 222 return a == b || properlyPostDominates(a, b); 223 } 224 225 bool properlyPostDominates(Block *aBlock, Block::iterator aIt, Block *bBlock, 226 Block::iterator bIt, 227 bool enclosingOk = true) const { 228 return super::properlyDominatesImpl(aBlock, aIt, bBlock, bIt, enclosingOk); 229 } 230 231 bool postDominates(Block *aBlock, Block::iterator aIt, Block *bBlock, 232 Block::iterator bIt, bool enclosingOk = true) const { 233 return (aBlock == bBlock && aIt == bIt) || 234 super::properlyDominatesImpl(aBlock, aIt, bBlock, bIt, enclosingOk); 235 } 236 }; 237 238 } // namespace mlir 239 240 namespace llvm { 241 242 /// DominatorTree GraphTraits specialization so the DominatorTree can be 243 /// iterated by generic graph iterators. 244 template <> 245 struct GraphTraits<mlir::DominanceInfoNode *> { 246 using ChildIteratorType = mlir::DominanceInfoNode::const_iterator; 247 using NodeRef = mlir::DominanceInfoNode *; 248 249 static NodeRef getEntryNode(NodeRef N) { return N; } 250 static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 251 static inline ChildIteratorType child_end(NodeRef N) { return N->end(); } 252 }; 253 254 template <> 255 struct GraphTraits<const mlir::DominanceInfoNode *> { 256 using ChildIteratorType = mlir::DominanceInfoNode::const_iterator; 257 using NodeRef = const mlir::DominanceInfoNode *; 258 259 static NodeRef getEntryNode(NodeRef N) { return N; } 260 static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 261 static inline ChildIteratorType child_end(NodeRef N) { return N->end(); } 262 }; 263 264 } // namespace llvm 265 #endif 266