1//===- Dominance.cpp - Dominator analysis for CFGs ------------------------===//
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// Implementation of dominance related classes and instantiations of extern
10// templates.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/IR/Dominance.h"
15#include "mlir/IR/Operation.h"
16#include "mlir/IR/RegionKindInterface.h"
17#include "llvm/Support/GenericDomTreeConstruction.h"
18
19using namespace mlir;
20using namespace mlir::detail;
21
22template class llvm::DominatorTreeBase<Block, /*IsPostDom=*/false>;
23template class llvm::DominatorTreeBase<Block, /*IsPostDom=*/true>;
24template class llvm::DomTreeNodeBase<Block>;
25
26//===----------------------------------------------------------------------===//
27// DominanceInfoBase
28//===----------------------------------------------------------------------===//
29
30template <bool IsPostDom>
31DominanceInfoBase<IsPostDom>::~DominanceInfoBase() {
32 for (auto entry : dominanceInfos)
33 delete entry.second.getPointer();
34}
35
36template <bool IsPostDom>
37void DominanceInfoBase<IsPostDom>::invalidate() {
38 for (auto entry : dominanceInfos)
39 delete entry.second.getPointer();
40 dominanceInfos.clear();
41}
42
43template <bool IsPostDom>
44void DominanceInfoBase<IsPostDom>::invalidate(Region *region, bool recursive) {
45 auto invalidate = [&](Region *r) {
46 auto it = dominanceInfos.find(r);
47 if (it != dominanceInfos.end()) {
48 delete it->second.getPointer();
49 dominanceInfos.erase(it);
50 }
51 };
52 if (recursive)
53 region->walk([&](Region *r) { invalidate(r); });
54 else
55 invalidate(region);
56}
57
58/// Return the dom tree and "hasSSADominance" bit for the given region. The
59/// DomTree will be null for single-block regions. This lazily constructs the
60/// DomTree on demand when needsDomTree=true.
61template <bool IsPostDom>
62auto DominanceInfoBase<IsPostDom>::getDominanceInfo(Region *region,
63 bool needsDomTree) const
64 -> llvm::PointerIntPair<DomTree *, 1, bool> {
65 // Check to see if we already have this information.
66 auto itAndInserted = dominanceInfos.insert({region, {nullptr, true}});
67 auto &entry = itAndInserted.first->second;
68
69 // This method builds on knowledge that multi-block regions always have
70 // SSADominance. Graph regions are only allowed to be single-block regions,
71 // but of course single-block regions may also have SSA dominance.
72 if (!itAndInserted.second) {
73 // We do have it, so we know the 'hasSSADominance' bit is correct, but we
74 // may not have constructed a DominatorTree yet. If we need it, build it.
75 if (needsDomTree && !entry.getPointer() && !region->hasOneBlock()) {
76 auto *domTree = new DomTree();
77 domTree->recalculate(*region);
78 entry.setPointer(domTree);
79 }
80 return entry;
81 }
82
83 // Nope, lazily construct it. Create a DomTree if this is a multi-block
84 // region.
85 if (!region->hasOneBlock()) {
86 auto *domTree = new DomTree();
87 domTree->recalculate(*region);
88 entry.setPointer(domTree);
89 // Multiblock regions always have SSA dominance, leave `second` set to true.
90 return entry;
91 }
92
93 // Single block regions have a more complicated predicate.
94 if (Operation *parentOp = region->getParentOp()) {
95 if (!parentOp->isRegistered()) { // We don't know about unregistered ops.
96 entry.setInt(false);
97 } else if (auto regionKindItf = dyn_cast<RegionKindInterface>(Val: parentOp)) {
98 // Registered ops can opt-out of SSA dominance with
99 // RegionKindInterface.
100 entry.setInt(regionKindItf.hasSSADominance(index: region->getRegionNumber()));
101 }
102 }
103
104 return entry;
105}
106
107/// Return the ancestor block enclosing the specified block. This returns null
108/// if we reach the top of the hierarchy.
109static Block *getAncestorBlock(Block *block) {
110 if (Operation *ancestorOp = block->getParentOp())
111 return ancestorOp->getBlock();
112 return nullptr;
113}
114
115/// Walks up the list of containers of the given block and calls the
116/// user-defined traversal function for every pair of a region and block that
117/// could be found during traversal. If the user-defined function returns true
118/// for a given pair, traverseAncestors will return the current block. Nullptr
119/// otherwise.
120template <typename FuncT>
121static Block *traverseAncestors(Block *block, const FuncT &func) {
122 do {
123 // Invoke the user-defined traversal function for each block.
124 if (func(block))
125 return block;
126 } while ((block = getAncestorBlock(block)));
127 return nullptr;
128}
129
130/// Tries to update the given block references to live in the same region by
131/// exploring the relationship of both blocks with respect to their regions.
132static bool tryGetBlocksInSameRegion(Block *&a, Block *&b) {
133 // If both block do not live in the same region, we will have to check their
134 // parent operations.
135 Region *aRegion = a->getParent();
136 Region *bRegion = b->getParent();
137 if (aRegion == bRegion)
138 return true;
139
140 // Iterate over all ancestors of `a`, counting the depth of `a`. If one of
141 // `a`s ancestors are in the same region as `b`, then we stop early because we
142 // found our NCA.
143 size_t aRegionDepth = 0;
144 if (Block *aResult = traverseAncestors(block: a, func: [&](Block *block) {
145 ++aRegionDepth;
146 return block->getParent() == bRegion;
147 })) {
148 a = aResult;
149 return true;
150 }
151
152 // Iterate over all ancestors of `b`, counting the depth of `b`. If one of
153 // `b`s ancestors are in the same region as `a`, then we stop early because
154 // we found our NCA.
155 size_t bRegionDepth = 0;
156 if (Block *bResult = traverseAncestors(block: b, func: [&](Block *block) {
157 ++bRegionDepth;
158 return block->getParent() == aRegion;
159 })) {
160 b = bResult;
161 return true;
162 }
163
164 // Otherwise we found two blocks that are siblings at some level. Walk the
165 // deepest one up until we reach the top or find an NCA.
166 while (true) {
167 if (aRegionDepth > bRegionDepth) {
168 a = getAncestorBlock(block: a);
169 --aRegionDepth;
170 } else if (aRegionDepth < bRegionDepth) {
171 b = getAncestorBlock(block: b);
172 --bRegionDepth;
173 } else {
174 break;
175 }
176 }
177
178 // If we found something with the same level, then we can march both up at the
179 // same time from here on out.
180 while (a) {
181 // If they are at the same level, and have the same parent region then we
182 // succeeded.
183 if (a->getParent() == b->getParent())
184 return true;
185
186 a = getAncestorBlock(block: a);
187 b = getAncestorBlock(block: b);
188 }
189
190 // They don't share an NCA, perhaps they are in different modules or
191 // something.
192 return false;
193}
194
195template <bool IsPostDom>
196Block *
197DominanceInfoBase<IsPostDom>::findNearestCommonDominator(Block *a,
198 Block *b) const {
199 // If either a or b are null, then conservatively return nullptr.
200 if (!a || !b)
201 return nullptr;
202
203 // If they are the same block, then we are done.
204 if (a == b)
205 return a;
206
207 // Try to find blocks that are in the same region.
208 if (!tryGetBlocksInSameRegion(a, b))
209 return nullptr;
210
211 // If the common ancestor in a common region is the same block, then return
212 // it.
213 if (a == b)
214 return a;
215
216 // Otherwise, there must be multiple blocks in the region, check the
217 // DomTree.
218 return getDomTree(region: a->getParent()).findNearestCommonDominator(a, b);
219}
220
221/// Returns the given block iterator if it lies within the region region.
222/// Otherwise, otherwise finds the ancestor of the given block iterator that
223/// lies within the given region. Returns and "empty" iterator if the latter
224/// fails.
225///
226/// Note: This is a variant of Region::findAncestorOpInRegion that operates on
227/// block iterators instead of ops.
228static std::pair<Block *, Block::iterator>
229findAncestorIteratorInRegion(Region *r, Block *b, Block::iterator it) {
230 // Case 1: The iterator lies within the region region.
231 if (b->getParent() == r)
232 return std::make_pair(x&: b, y&: it);
233
234 // Otherwise: Find ancestor iterator. Bail if we run out of parent ops.
235 Operation *parentOp = b->getParentOp();
236 if (!parentOp)
237 return std::make_pair(x: static_cast<Block *>(nullptr), y: Block::iterator());
238 Operation *op = r->findAncestorOpInRegion(op&: *parentOp);
239 if (!op)
240 return std::make_pair(x: static_cast<Block *>(nullptr), y: Block::iterator());
241 return std::make_pair(x: op->getBlock(), y: op->getIterator());
242}
243
244/// Given two iterators into the same block, return "true" if `a` is before `b.
245/// Note: This is a variant of Operation::isBeforeInBlock that operates on
246/// block iterators instead of ops.
247static bool isBeforeInBlock(Block *block, Block::iterator a,
248 Block::iterator b) {
249 if (a == b)
250 return false;
251 if (a == block->end())
252 return false;
253 if (b == block->end())
254 return true;
255 return a->isBeforeInBlock(other: &*b);
256}
257
258template <bool IsPostDom>
259bool DominanceInfoBase<IsPostDom>::properlyDominatesImpl(
260 Block *aBlock, Block::iterator aIt, Block *bBlock, Block::iterator bIt,
261 bool enclosingOk) const {
262 assert(aBlock && bBlock && "expected non-null blocks");
263
264 // A block iterator (post)dominates, but does not properly (post)dominate,
265 // itself unless this is a graph region.
266 if (aBlock == bBlock && aIt == bIt)
267 return !hasSSADominance(aBlock);
268
269 // If the iterators are in different regions, then normalize one into the
270 // other.
271 Region *aRegion = aBlock->getParent();
272 if (aRegion != bBlock->getParent()) {
273 // Scoot up b's region tree until we find a location in A's region that
274 // encloses it. If this fails, then we know there is no (post)dom relation.
275 if (!aRegion) {
276 bBlock = nullptr;
277 bIt = Block::iterator();
278 } else {
279 std::tie(args&: bBlock, args&: bIt) =
280 findAncestorIteratorInRegion(r: aRegion, b: bBlock, it: bIt);
281 }
282 if (!bBlock)
283 return false;
284 assert(bBlock->getParent() == aRegion && "expected block in regionA");
285
286 // If 'a' encloses 'b', then we consider it to (post)dominate.
287 if (aBlock == bBlock && aIt == bIt && enclosingOk)
288 return true;
289 }
290
291 // Ok, they are in the same region now.
292 if (aBlock == bBlock) {
293 // Dominance changes based on the region type. In a region with SSA
294 // dominance, uses inside the same block must follow defs. In other
295 // regions kinds, uses and defs can come in any order inside a block.
296 if (!hasSSADominance(aBlock))
297 return true;
298 if constexpr (IsPostDom) {
299 return isBeforeInBlock(block: aBlock, a: bIt, b: aIt);
300 } else {
301 return isBeforeInBlock(block: aBlock, a: aIt, b: bIt);
302 }
303 }
304
305 // If the blocks are different, use DomTree to resolve the query.
306 return getDomTree(region: aRegion).properlyDominates(aBlock, bBlock);
307}
308
309/// Return true if the specified block is reachable from the entry block of
310/// its region.
311template <bool IsPostDom>
312bool DominanceInfoBase<IsPostDom>::isReachableFromEntry(Block *a) const {
313 // If this is the first block in its region, then it is obviously reachable.
314 Region *region = a->getParent();
315 if (&region->front() == a)
316 return true;
317
318 // Otherwise this is some block in a multi-block region. Check DomTree.
319 return getDomTree(region).isReachableFromEntry(a);
320}
321
322template class detail::DominanceInfoBase</*IsPostDom=*/true>;
323template class detail::DominanceInfoBase</*IsPostDom=*/false>;
324
325//===----------------------------------------------------------------------===//
326// DominanceInfo
327//===----------------------------------------------------------------------===//
328
329bool DominanceInfo::properlyDominates(Operation *a, Operation *b,
330 bool enclosingOpOk) const {
331 return super::properlyDominatesImpl(aBlock: a->getBlock(), aIt: a->getIterator(),
332 bBlock: b->getBlock(), bIt: b->getIterator(),
333 enclosingOk: enclosingOpOk);
334}
335
336bool DominanceInfo::properlyDominates(Block *a, Block *b) const {
337 return super::properlyDominatesImpl(aBlock: a, aIt: a->begin(), bBlock: b, bIt: b->begin(),
338 /*enclosingOk=*/true);
339}
340
341/// Return true if the `a` value properly dominates operation `b`, i.e if the
342/// operation that defines `a` properlyDominates `b` and the operation that
343/// defines `a` does not contain `b`.
344bool DominanceInfo::properlyDominates(Value a, Operation *b) const {
345 // block arguments properly dominate all operations in their own block, so
346 // we use a dominates check here, not a properlyDominates check.
347 if (auto blockArg = dyn_cast<BlockArgument>(Val&: a))
348 return dominates(a: blockArg.getOwner(), b: b->getBlock());
349
350 // `a` properlyDominates `b` if the operation defining `a` properlyDominates
351 // `b`, but `a` does not itself enclose `b` in one of its regions.
352 return properlyDominates(a: a.getDefiningOp(), b, /*enclosingOpOk=*/false);
353}
354
355//===----------------------------------------------------------------------===//
356// PostDominanceInfo
357//===----------------------------------------------------------------------===//
358
359bool PostDominanceInfo::properlyPostDominates(Operation *a, Operation *b,
360 bool enclosingOpOk) const {
361 return super::properlyDominatesImpl(aBlock: a->getBlock(), aIt: a->getIterator(),
362 bBlock: b->getBlock(), bIt: b->getIterator(),
363 enclosingOk: enclosingOpOk);
364}
365
366bool PostDominanceInfo::properlyPostDominates(Block *a, Block *b) const {
367 return super::properlyDominatesImpl(aBlock: a, aIt: a->end(), bBlock: b, bIt: b->end(),
368 /*enclosingOk=*/true);
369}
370