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/ADT/DenseMap.h"
18#include "llvm/Support/GenericDomTreeConstruction.h"
19
20using namespace mlir;
21using namespace mlir::detail;
22
23template class llvm::DominatorTreeBase<Block, /*IsPostDom=*/false>;
24template class llvm::DominatorTreeBase<Block, /*IsPostDom=*/true>;
25template class llvm::DomTreeNodeBase<Block>;
26
27//===----------------------------------------------------------------------===//
28// DominanceInfoBase
29//===----------------------------------------------------------------------===//
30
31template <bool IsPostDom>
32DominanceInfoBase<IsPostDom>::~DominanceInfoBase() {
33 for (auto entry : dominanceInfos)
34 delete entry.second.getPointer();
35}
36
37template <bool IsPostDom> void 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>(parentOp)) {
92 // Registered ops can opt-out of SSA dominance with
93 // RegionKindInterface.
94 entry.setInt(regionKindItf.hasSSADominance(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/// Return true if the specified block A properly dominates block B.
216template <bool IsPostDom>
217bool DominanceInfoBase<IsPostDom>::properlyDominates(Block *a, Block *b) const {
218 assert(a && b && "null blocks not allowed");
219
220 // A block dominates itself but does not properly dominate itself.
221 if (a == b)
222 return false;
223
224 // If both blocks are not in the same region, `a` properly dominates `b` if
225 // `b` is defined in an operation region that (recursively) ends up being
226 // dominated by `a`. Walk up the list of containers enclosing B.
227 Region *regionA = a->getParent();
228 if (regionA != b->getParent()) {
229 b = regionA ? regionA->findAncestorBlockInRegion(block&: *b) : nullptr;
230 // If we could not find a valid block b then it is a not a dominator.
231 if (b == nullptr)
232 return false;
233
234 // Check to see if the ancestor of `b` is the same block as `a`. A properly
235 // dominates B if it contains an op that contains the B block.
236 if (a == b)
237 return true;
238 }
239
240 // Otherwise, they are two different blocks in the same region, use DomTree.
241 return getDomTree(region: regionA).properlyDominates(a, b);
242}
243
244/// Return true if the specified block is reachable from the entry block of
245/// its region.
246template <bool IsPostDom>
247bool DominanceInfoBase<IsPostDom>::isReachableFromEntry(Block *a) const {
248 // If this is the first block in its region, then it is obviously reachable.
249 Region *region = a->getParent();
250 if (&region->front() == a)
251 return true;
252
253 // Otherwise this is some block in a multi-block region. Check DomTree.
254 return getDomTree(region).isReachableFromEntry(a);
255}
256
257template class detail::DominanceInfoBase</*IsPostDom=*/true>;
258template class detail::DominanceInfoBase</*IsPostDom=*/false>;
259
260//===----------------------------------------------------------------------===//
261// DominanceInfo
262//===----------------------------------------------------------------------===//
263
264/// Return true if operation `a` properly dominates operation `b`. The
265/// 'enclosingOpOk' flag says whether we should return true if the `b` op is
266/// enclosed by a region on 'a'.
267bool DominanceInfo::properlyDominatesImpl(Operation *a, Operation *b,
268 bool enclosingOpOk) const {
269 Block *aBlock = a->getBlock(), *bBlock = b->getBlock();
270 assert(aBlock && bBlock && "operations must be in a block");
271
272 // An instruction dominates, but does not properlyDominate, itself unless this
273 // is a graph region.
274 if (a == b)
275 return !hasSSADominance(block: aBlock);
276
277 // If these ops are in different regions, then normalize one into the other.
278 Region *aRegion = aBlock->getParent();
279 if (aRegion != bBlock->getParent()) {
280 // Scoot up b's region tree until we find an operation in A's region that
281 // encloses it. If this fails, then we know there is no post-dom relation.
282 b = aRegion ? aRegion->findAncestorOpInRegion(op&: *b) : nullptr;
283 if (!b)
284 return false;
285 bBlock = b->getBlock();
286 assert(bBlock->getParent() == aRegion);
287
288 // If 'a' encloses 'b', then we consider it to dominate.
289 if (a == b && enclosingOpOk)
290 return true;
291 }
292
293 // Ok, they are in the same region now.
294 if (aBlock == bBlock) {
295 // Dominance changes based on the region type. In a region with SSA
296 // dominance, uses inside the same block must follow defs. In other
297 // regions kinds, uses and defs can come in any order inside a block.
298 if (hasSSADominance(block: aBlock)) {
299 // If the blocks are the same, then check if b is before a in the block.
300 return a->isBeforeInBlock(other: b);
301 }
302 return true;
303 }
304
305 // If the blocks are different, use DomTree to resolve the query.
306 return getDomTree(region: aRegion).properlyDominates(A: aBlock, B: bBlock);
307}
308
309/// Return true if the `a` value properly dominates operation `b`, i.e if the
310/// operation that defines `a` properlyDominates `b` and the operation that
311/// defines `a` does not contain `b`.
312bool DominanceInfo::properlyDominates(Value a, Operation *b) const {
313 // block arguments properly dominate all operations in their own block, so
314 // we use a dominates check here, not a properlyDominates check.
315 if (auto blockArg = dyn_cast<BlockArgument>(Val&: a))
316 return dominates(a: blockArg.getOwner(), b: b->getBlock());
317
318 // `a` properlyDominates `b` if the operation defining `a` properlyDominates
319 // `b`, but `a` does not itself enclose `b` in one of its regions.
320 return properlyDominatesImpl(a: a.getDefiningOp(), b, /*enclosingOpOk=*/false);
321}
322
323//===----------------------------------------------------------------------===//
324// PostDominanceInfo
325//===----------------------------------------------------------------------===//
326
327/// Returns true if statement 'a' properly postdominates statement b.
328bool PostDominanceInfo::properlyPostDominates(Operation *a, Operation *b) {
329 auto *aBlock = a->getBlock(), *bBlock = b->getBlock();
330 assert(aBlock && bBlock && "operations must be in a block");
331
332 // An instruction postDominates, but does not properlyPostDominate, itself
333 // unless this is a graph region.
334 if (a == b)
335 return !hasSSADominance(block: aBlock);
336
337 // If these ops are in different regions, then normalize one into the other.
338 Region *aRegion = aBlock->getParent();
339 if (aRegion != bBlock->getParent()) {
340 // Scoot up b's region tree until we find an operation in A's region that
341 // encloses it. If this fails, then we know there is no post-dom relation.
342 b = aRegion ? aRegion->findAncestorOpInRegion(op&: *b) : nullptr;
343 if (!b)
344 return false;
345 bBlock = b->getBlock();
346 assert(bBlock->getParent() == aRegion);
347
348 // If 'a' encloses 'b', then we consider it to postdominate.
349 if (a == b)
350 return true;
351 }
352
353 // Ok, they are in the same region. If they are in the same block, check if b
354 // is before a in the block.
355 if (aBlock == bBlock) {
356 // Dominance changes based on the region type.
357 if (hasSSADominance(block: aBlock)) {
358 // If the blocks are the same, then check if b is before a in the block.
359 return b->isBeforeInBlock(other: a);
360 }
361 return true;
362 }
363
364 // If the blocks are different, check if a's block post dominates b's.
365 return getDomTree(region: aRegion).properlyDominates(A: aBlock, B: bBlock);
366}
367

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