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

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