1//===- Dominance.h - Dominator analysis for regions -------------*- C++ -*-===//
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// The DominanceInfo and PostDominanceInfo class provide routines for performimg
10// simple dominance checks, and expose dominator trees for advanced clients.
11// These classes provide fully region-aware functionality, lazily constructing
12// dominator information for any multi-block regions that need it.
13//
14// For more information about the theory behind dominance in graphs algorithms,
15// see: https://en.wikipedia.org/wiki/Dominator_(graph_theory)
16//
17//===----------------------------------------------------------------------===//
18
19#ifndef MLIR_IR_DOMINANCE_H
20#define MLIR_IR_DOMINANCE_H
21
22#include "mlir/IR/RegionGraphTraits.h"
23#include "llvm/Support/GenericDomTree.h"
24
25extern template class llvm::DominatorTreeBase<mlir::Block, false>;
26extern template class llvm::DominatorTreeBase<mlir::Block, true>;
27extern template class llvm::DomTreeNodeBase<mlir::Block>;
28
29namespace mlir {
30using DominanceInfoNode = llvm::DomTreeNodeBase<Block>;
31class Operation;
32
33namespace detail {
34template <bool IsPostDom>
35class DominanceInfoBase {
36 using DomTree = llvm::DominatorTreeBase<Block, IsPostDom>;
37
38public:
39 DominanceInfoBase(Operation *op = nullptr) {}
40 DominanceInfoBase(DominanceInfoBase &&) = default;
41 DominanceInfoBase &operator=(DominanceInfoBase &&) = default;
42 ~DominanceInfoBase();
43
44 DominanceInfoBase(const DominanceInfoBase &) = delete;
45 DominanceInfoBase &operator=(const DominanceInfoBase &) = delete;
46
47 /// Invalidate dominance info. This can be used by clients that make major
48 /// changes to the CFG and don't have a good way to update it.
49 void invalidate();
50 void invalidate(Region *region);
51
52 /// Finds the nearest common dominator block for the two given blocks a
53 /// and b. If no common dominator can be found, this function will return
54 /// nullptr.
55 Block *findNearestCommonDominator(Block *a, Block *b) const;
56
57 /// Finds the nearest common dominator block for the given range of blocks.
58 /// If no common dominator can be found, this function will return nullptr.
59 template <typename BlockRangeT>
60 Block *findNearestCommonDominator(BlockRangeT &&blocks) const {
61 if (blocks.begin() == blocks.end())
62 return nullptr;
63 Block *dom = *blocks.begin();
64 for (auto it = ++blocks.begin(); it != blocks.end(); ++it) {
65 dom = findNearestCommonDominator(dom, *it);
66 if (!dom)
67 return nullptr;
68 }
69 return dom;
70 }
71
72 /// Get the root dominance node of the given region. Note that this operation
73 /// is only defined for multi-block regions!
74 DominanceInfoNode *getRootNode(Region *region) {
75 auto domInfo = getDominanceInfo(region, /*needsDomTree*/ needsDomTree: true).getPointer();
76 assert(domInfo && "Region isn't multiblock");
77 return domInfo->getRootNode();
78 }
79
80 /// Return the dominance node from the Region containing block A. This only
81 /// works for multi-block regions.
82 DominanceInfoNode *getNode(Block *a) {
83 return getDomTree(region: a->getParent()).getNode(a);
84 }
85
86 /// Return true if the specified block is reachable from the entry
87 /// block of its region.
88 bool isReachableFromEntry(Block *a) const;
89
90 /// Return true if operations in the specified block are known to obey SSA
91 /// dominance requirements. False if the block is a graph region or unknown.
92 bool hasSSADominance(Block *block) const {
93 return hasSSADominance(block->getParent());
94 }
95 /// Return true if operations in the specified block are known to obey SSA
96 /// dominance requirements. False if the block is a graph region or unknown.
97 bool hasSSADominance(Region *region) const {
98 return getDominanceInfo(region, /*needsDomTree=*/needsDomTree: false).getInt();
99 }
100
101 DomTree &getDomTree(Region *region) const {
102 assert(!region->hasOneBlock() &&
103 "Can't get DomTree for single block regions");
104 return *getDominanceInfo(region, /*needsDomTree=*/needsDomTree: true).getPointer();
105 }
106
107protected:
108 using super = DominanceInfoBase<IsPostDom>;
109
110 /// Return the dom tree and "hasSSADominance" bit for the given region. The
111 /// DomTree will be null for single-block regions. This lazily constructs the
112 /// DomTree on demand when needsDomTree=true.
113 llvm::PointerIntPair<DomTree *, 1, bool>
114 getDominanceInfo(Region *region, bool needsDomTree) const;
115
116 /// Return "true" if block iterator A properly (post)dominates block iterator
117 /// B. If `enclosingOk` is set, A is considered to (post)dominate B if A
118 /// encloses B.
119 bool properlyDominatesImpl(Block *aBlock, Block::iterator aIt, Block *bBlock,
120 Block::iterator bIt,
121 bool enclosingOk = true) const;
122
123 /// A mapping of regions to their base dominator tree and a cached
124 /// "hasSSADominance" bit. This map does not contain dominator trees for
125 /// single block CFG regions, but we do want to cache the "hasSSADominance"
126 /// bit for them. We may also not have computed the DomTree yet. In either
127 /// case, the DomTree is just null.
128 ///
129 mutable DenseMap<Region *, llvm::PointerIntPair<DomTree *, 1, bool>>
130 dominanceInfos;
131};
132
133extern template class DominanceInfoBase</*IsPostDom=*/true>;
134extern template class DominanceInfoBase</*IsPostDom=*/false>;
135} // namespace detail
136
137/// A class for computing basic dominance information. Note that this
138/// class is aware of different types of regions and returns a
139/// region-kind specific concept of dominance. See RegionKindInterface.
140class DominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/false> {
141public:
142 using super::super;
143
144 /// Return true if operation A properly dominates operation B, i.e. if A and B
145 /// are in the same block and A properly dominates B within the block, or if
146 /// the block that contains A properly dominates the block that contains B. In
147 /// an SSACFG region, Operation A dominates Operation B in the same block if A
148 /// preceeds B. In a Graph region, all operations in a block properly dominate
149 /// all operations in the same block.
150 ///
151 /// The `enclosingOpOk` flag says whether we should return true if the B op
152 /// is enclosed by a region on A.
153 bool properlyDominates(Operation *a, Operation *b,
154 bool enclosingOpOk = true) const;
155
156 /// Return true if operation A dominates operation B, i.e. if A and B are the
157 /// same operation or A properly dominates B.
158 bool dominates(Operation *a, Operation *b) const {
159 return a == b || properlyDominates(a, b);
160 }
161
162 /// Return true if the `a` value properly dominates operation `b`, i.e if the
163 /// operation that defines `a` properlyDominates `b` and the operation that
164 /// defines `a` does not contain `b`.
165 bool properlyDominates(Value a, Operation *b) const;
166
167 /// Return true if the `a` value dominates operation `b`.
168 bool dominates(Value a, Operation *b) const {
169 return (Operation *)a.getDefiningOp() == b || properlyDominates(a, b);
170 }
171
172 /// Return true if the specified block A dominates block B, i.e. if block A
173 /// and block B are the same block or block A properly dominates block B.
174 bool dominates(Block *a, Block *b) const {
175 return a == b || properlyDominates(a, b);
176 }
177
178 /// Return true if the specified block A properly dominates block B, i.e.: if
179 /// block A contains block B, or if the region which contains block A also
180 /// contains block B or some parent of block B and block A dominates that
181 /// block in that kind of region.
182 ///
183 /// In an SSACFG region, block A dominates block B if all control flow paths
184 /// from the entry block to block B flow through block A.
185 ///
186 /// Graph regions have only a single block. To be consistent with "proper
187 /// dominance" of ops, the single block is considered to properly dominate
188 /// itself in a graph region.
189 bool properlyDominates(Block *a, Block *b) const;
190
191 bool properlyDominates(Block *aBlock, Block::iterator aIt, Block *bBlock,
192 Block::iterator bIt, bool enclosingOk = true) const {
193 return super::properlyDominatesImpl(aBlock, aIt, bBlock, bIt, enclosingOk);
194 }
195
196 bool dominates(Block *aBlock, Block::iterator aIt, Block *bBlock,
197 Block::iterator bIt, bool enclosingOk = true) const {
198 return (aBlock == bBlock && aIt == bIt) ||
199 super::properlyDominatesImpl(aBlock, aIt, bBlock, bIt, enclosingOk);
200 }
201};
202
203/// A class for computing basic postdominance information.
204class PostDominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/true> {
205public:
206 using super::super;
207
208 /// Return true if operation A properly postdominates operation B.
209 bool properlyPostDominates(Operation *a, Operation *b,
210 bool enclosingOpOk = true) const;
211
212 /// Return true if operation A postdominates operation B.
213 bool postDominates(Operation *a, Operation *b) const {
214 return a == b || properlyPostDominates(a, b);
215 }
216
217 /// Return true if the specified block A properly postdominates block B.
218 bool properlyPostDominates(Block *a, Block *b) const;
219
220 /// Return true if the specified block A postdominates block B.
221 bool postDominates(Block *a, Block *b) const {
222 return a == b || properlyPostDominates(a, b);
223 }
224
225 bool properlyPostDominates(Block *aBlock, Block::iterator aIt, Block *bBlock,
226 Block::iterator bIt,
227 bool enclosingOk = true) const {
228 return super::properlyDominatesImpl(aBlock, aIt, bBlock, bIt, enclosingOk);
229 }
230
231 bool postDominates(Block *aBlock, Block::iterator aIt, Block *bBlock,
232 Block::iterator bIt, bool enclosingOk = true) const {
233 return (aBlock == bBlock && aIt == bIt) ||
234 super::properlyDominatesImpl(aBlock, aIt, bBlock, bIt, enclosingOk);
235 }
236};
237
238} // namespace mlir
239
240namespace llvm {
241
242/// DominatorTree GraphTraits specialization so the DominatorTree can be
243/// iterated by generic graph iterators.
244template <>
245struct GraphTraits<mlir::DominanceInfoNode *> {
246 using ChildIteratorType = mlir::DominanceInfoNode::const_iterator;
247 using NodeRef = mlir::DominanceInfoNode *;
248
249 static NodeRef getEntryNode(NodeRef N) { return N; }
250 static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
251 static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
252};
253
254template <>
255struct GraphTraits<const mlir::DominanceInfoNode *> {
256 using ChildIteratorType = mlir::DominanceInfoNode::const_iterator;
257 using NodeRef = const mlir::DominanceInfoNode *;
258
259 static NodeRef getEntryNode(NodeRef N) { return N; }
260 static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
261 static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
262};
263
264} // namespace llvm
265#endif
266

Provided by KDAB

Privacy Policy
Learn to use CMake with our Intro Training
Find out more

source code of mlir/include/mlir/IR/Dominance.h