1 //===- Dominance.h - Dominator analysis for CFGs ----------------*- 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 #ifndef MLIR_IR_DOMINANCE_H 10 #define MLIR_IR_DOMINANCE_H 11 12 #include "mlir/IR/RegionGraphTraits.h" 13 #include "llvm/Support/GenericDomTree.h" 14 15 extern template class llvm::DominatorTreeBase<mlir::Block, false>; 16 extern template class llvm::DominatorTreeBase<mlir::Block, true>; 17 18 namespace mlir { 19 using DominanceInfoNode = llvm::DomTreeNodeBase<Block>; 20 class Operation; 21 22 namespace detail { 23 template <bool IsPostDom> class DominanceInfoBase { 24 using base = llvm::DominatorTreeBase<Block, IsPostDom>; 25 26 public: DominanceInfoBase(Operation * op)27 DominanceInfoBase(Operation *op) { recalculate(op); } 28 DominanceInfoBase(DominanceInfoBase &&) = default; 29 DominanceInfoBase &operator=(DominanceInfoBase &&) = default; 30 31 DominanceInfoBase(const DominanceInfoBase &) = delete; 32 DominanceInfoBase &operator=(const DominanceInfoBase &) = delete; 33 34 /// Recalculate the dominance info. 35 void recalculate(Operation *op); 36 37 /// Finds the nearest common dominator block for the two given blocks a 38 /// and b. If no common dominator can be found, this function will return 39 /// nullptr. 40 Block *findNearestCommonDominator(Block *a, Block *b) const; 41 42 /// Return true if there is dominanceInfo for the given region. hasDominanceInfo(Region * region)43 bool hasDominanceInfo(Region *region) { 44 return dominanceInfos.count(region) != 0; 45 } 46 47 /// Get the root dominance node of the given region. getRootNode(Region * region)48 DominanceInfoNode *getRootNode(Region *region) { 49 assert(dominanceInfos.count(region) != 0); 50 return dominanceInfos[region]->getRootNode(); 51 } 52 53 /// Return the dominance node from the Region containing block A. 54 DominanceInfoNode *getNode(Block *a); 55 56 protected: 57 using super = DominanceInfoBase<IsPostDom>; 58 59 /// Return true if the specified block A properly dominates block B. 60 bool properlyDominates(Block *a, Block *b) const; 61 62 /// Return true if the specified block is reachable from the entry 63 /// block of its region. 64 bool isReachableFromEntry(Block *a) const; 65 66 /// A mapping of regions to their base dominator tree. 67 DenseMap<Region *, std::unique_ptr<base>> dominanceInfos; 68 }; 69 } // end namespace detail 70 71 /// A class for computing basic dominance information. Note that this 72 /// class is aware of different types of regions and returns a 73 /// region-kind specific concept of dominance. See RegionKindInterface. 74 class DominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/false> { 75 public: 76 using super::super; 77 78 /// Return true if the specified block is reachable from the entry block of 79 /// its region. In an SSACFG region, a block is reachable from the entry block 80 /// if it is the successor of the entry block or another reachable block. In a 81 /// Graph region, all blocks are reachable. isReachableFromEntry(Block * a)82 bool isReachableFromEntry(Block *a) const { 83 return super::isReachableFromEntry(a); 84 } 85 86 /// Return true if operation A properly dominates operation B, i.e. if A and B 87 /// are in the same block and A properly dominates B within the block, or if 88 /// the block that contains A properly dominates the block that contains B. In 89 /// an SSACFG region, Operation A dominates Operation B in the same block if A 90 /// preceeds B. In a Graph region, all operations in a block dominate all 91 /// other operations in the same block. 92 bool properlyDominates(Operation *a, Operation *b) const; 93 94 /// Return true if operation A dominates operation B, i.e. if A and B are the 95 /// same operation or A properly dominates B. dominates(Operation * a,Operation * b)96 bool dominates(Operation *a, Operation *b) const { 97 return a == b || properlyDominates(a, b); 98 } 99 100 /// Return true if value A properly dominates operation B, i.e if the 101 /// operation that defines A properlyDominates B and the operation that 102 /// defines A does not contain B. 103 bool properlyDominates(Value a, Operation *b) const; 104 105 /// Return true if operation A dominates operation B, i.e if the operation 106 /// that defines A dominates B. dominates(Value a,Operation * b)107 bool dominates(Value a, Operation *b) const { 108 return (Operation *)a.getDefiningOp() == b || properlyDominates(a, b); 109 } 110 111 /// Return true if the specified block A dominates block B, i.e. if block A 112 /// and block B are the same block or block A properly dominates block B. dominates(Block * a,Block * b)113 bool dominates(Block *a, Block *b) const { 114 return a == b || properlyDominates(a, b); 115 } 116 117 /// Return true if the specified block A properly dominates block B, i.e.: if 118 /// block A contains block B, or if the region which contains block A also 119 /// contains block B or some parent of block B and block A dominates that 120 /// block in that kind of region. In an SSACFG region, block A dominates 121 /// block B if all control flow paths from the entry block to block B flow 122 /// through block A. In a Graph region, all blocks dominate all other blocks. properlyDominates(Block * a,Block * b)123 bool properlyDominates(Block *a, Block *b) const { 124 return super::properlyDominates(a, b); 125 } 126 127 /// Update the internal DFS numbers for the dominance nodes. 128 void updateDFSNumbers(); 129 }; 130 131 /// A class for computing basic postdominance information. 132 class PostDominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/true> { 133 public: 134 using super::super; 135 136 /// Return true if the specified block is reachable from the entry 137 /// block of its region. isReachableFromEntry(Block * a)138 bool isReachableFromEntry(Block *a) const { 139 return super::isReachableFromEntry(a); 140 } 141 142 /// Return true if operation A properly postdominates operation B. 143 bool properlyPostDominates(Operation *a, Operation *b); 144 145 /// Return true if operation A postdominates operation B. postDominates(Operation * a,Operation * b)146 bool postDominates(Operation *a, Operation *b) { 147 return a == b || properlyPostDominates(a, b); 148 } 149 150 /// Return true if the specified block A properly postdominates block B. properlyPostDominates(Block * a,Block * b)151 bool properlyPostDominates(Block *a, Block *b) { 152 return super::properlyDominates(a, b); 153 } 154 155 /// Return true if the specified block A postdominates block B. postDominates(Block * a,Block * b)156 bool postDominates(Block *a, Block *b) { 157 return a == b || properlyPostDominates(a, b); 158 } 159 }; 160 161 } // end namespace mlir 162 163 namespace llvm { 164 165 /// DominatorTree GraphTraits specialization so the DominatorTree can be 166 /// iterated by generic graph iterators. 167 template <> struct GraphTraits<mlir::DominanceInfoNode *> { 168 using ChildIteratorType = mlir::DominanceInfoNode::const_iterator; 169 using NodeRef = mlir::DominanceInfoNode *; 170 171 static NodeRef getEntryNode(NodeRef N) { return N; } 172 static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 173 static inline ChildIteratorType child_end(NodeRef N) { return N->end(); } 174 }; 175 176 template <> struct GraphTraits<const mlir::DominanceInfoNode *> { 177 using ChildIteratorType = mlir::DominanceInfoNode::const_iterator; 178 using NodeRef = const mlir::DominanceInfoNode *; 179 180 static NodeRef getEntryNode(NodeRef N) { return N; } 181 static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); } 182 static inline ChildIteratorType child_end(NodeRef N) { return N->end(); } 183 }; 184 185 } // end namespace llvm 186 #endif 187