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

source code of mlir/lib/IR/Dominance.cpp