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*/ 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(region: 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=*/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=*/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 the specified block A properly dominates block B. |
117 | bool properlyDominates(Block *a, Block *b) const; |
118 | |
119 | /// A mapping of regions to their base dominator tree and a cached |
120 | /// "hasSSADominance" bit. This map does not contain dominator trees for |
121 | /// single block CFG regions, but we do want to cache the "hasSSADominance" |
122 | /// bit for them. We may also not have computed the DomTree yet. In either |
123 | /// case, the DomTree is just null. |
124 | /// |
125 | mutable DenseMap<Region *, llvm::PointerIntPair<DomTree *, 1, bool>> |
126 | dominanceInfos; |
127 | }; |
128 | |
129 | extern template class DominanceInfoBase</*IsPostDom=*/true>; |
130 | extern template class DominanceInfoBase</*IsPostDom=*/false>; |
131 | } // namespace detail |
132 | |
133 | /// A class for computing basic dominance information. Note that this |
134 | /// class is aware of different types of regions and returns a |
135 | /// region-kind specific concept of dominance. See RegionKindInterface. |
136 | class DominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/false> { |
137 | public: |
138 | using super::super; |
139 | |
140 | /// Return true if operation A properly dominates operation B, i.e. if A and B |
141 | /// are in the same block and A properly dominates B within the block, or if |
142 | /// the block that contains A properly dominates the block that contains B. In |
143 | /// an SSACFG region, Operation A dominates Operation B in the same block if A |
144 | /// preceeds B. In a Graph region, all operations in a block dominate all |
145 | /// other operations in the same block. |
146 | /// |
147 | /// The `enclosingOpOk` flag says whether we should return true if the B op |
148 | /// is enclosed by a region on A. |
149 | bool properlyDominates(Operation *a, Operation *b, |
150 | bool enclosingOpOk = true) const { |
151 | return properlyDominatesImpl(a, b, enclosingOpOk); |
152 | } |
153 | |
154 | /// Return true if operation A dominates operation B, i.e. if A and B are the |
155 | /// same operation or A properly dominates B. |
156 | bool dominates(Operation *a, Operation *b) const { |
157 | return a == b || properlyDominates(a, b); |
158 | } |
159 | |
160 | /// Return true if the `a` value properly dominates operation `b`, i.e if the |
161 | /// operation that defines `a` properlyDominates `b` and the operation that |
162 | /// defines `a` does not contain `b`. |
163 | bool properlyDominates(Value a, Operation *b) const; |
164 | |
165 | /// Return true if the `a` value dominates operation `b`. |
166 | bool dominates(Value a, Operation *b) const { |
167 | return (Operation *)a.getDefiningOp() == b || properlyDominates(a, b); |
168 | } |
169 | |
170 | /// Return true if the specified block A dominates block B, i.e. if block A |
171 | /// and block B are the same block or block A properly dominates block B. |
172 | bool dominates(Block *a, Block *b) const { |
173 | return a == b || properlyDominates(a, b); |
174 | } |
175 | |
176 | /// Return true if the specified block A properly dominates block B, i.e.: if |
177 | /// block A contains block B, or if the region which contains block A also |
178 | /// contains block B or some parent of block B and block A dominates that |
179 | /// block in that kind of region. In an SSACFG region, block A dominates |
180 | /// block B if all control flow paths from the entry block to block B flow |
181 | /// through block A. In a Graph region, all blocks dominate all other blocks. |
182 | bool properlyDominates(Block *a, Block *b) const { |
183 | return super::properlyDominates(a, b); |
184 | } |
185 | |
186 | private: |
187 | // Return true if operation A properly dominates operation B. The |
188 | /// 'enclosingOpOk' flag says whether we should return true if the b op is |
189 | /// enclosed by a region on 'A'. |
190 | bool properlyDominatesImpl(Operation *a, Operation *b, |
191 | bool enclosingOpOk) const; |
192 | }; |
193 | |
194 | /// A class for computing basic postdominance information. |
195 | class PostDominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/true> { |
196 | public: |
197 | using super::super; |
198 | |
199 | /// Return true if operation A properly postdominates operation B. |
200 | bool properlyPostDominates(Operation *a, Operation *b); |
201 | |
202 | /// Return true if operation A postdominates operation B. |
203 | bool postDominates(Operation *a, Operation *b) { |
204 | return a == b || properlyPostDominates(a, b); |
205 | } |
206 | |
207 | /// Return true if the specified block A properly postdominates block B. |
208 | bool properlyPostDominates(Block *a, Block *b) { |
209 | return super::properlyDominates(a, b); |
210 | } |
211 | |
212 | /// Return true if the specified block A postdominates block B. |
213 | bool postDominates(Block *a, Block *b) { |
214 | return a == b || properlyPostDominates(a, b); |
215 | } |
216 | }; |
217 | |
218 | } // namespace mlir |
219 | |
220 | namespace llvm { |
221 | |
222 | /// DominatorTree GraphTraits specialization so the DominatorTree can be |
223 | /// iterated by generic graph iterators. |
224 | template <> |
225 | struct GraphTraits<mlir::DominanceInfoNode *> { |
226 | using ChildIteratorType = mlir::DominanceInfoNode::const_iterator; |
227 | using NodeRef = mlir::DominanceInfoNode *; |
228 | |
229 | static NodeRef getEntryNode(NodeRef N) { return N; } |
230 | static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
231 | static inline ChildIteratorType child_end(NodeRef N) { return N->end(); } |
232 | }; |
233 | |
234 | template <> |
235 | struct GraphTraits<const mlir::DominanceInfoNode *> { |
236 | using ChildIteratorType = mlir::DominanceInfoNode::const_iterator; |
237 | using NodeRef = const mlir::DominanceInfoNode *; |
238 | |
239 | static NodeRef getEntryNode(NodeRef N) { return N; } |
240 | static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
241 | static inline ChildIteratorType child_end(NodeRef N) { return N->end(); } |
242 | }; |
243 | |
244 | } // namespace llvm |
245 | #endif |
246 | |