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