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 the specified block A properly dominates block B.
117 bool properlyDominates(Block *a, Block *b) const;
118
119 /// A mapping of regions to their base dominator tree and a cached
120 /// "hasSSADominance" bit. This map does not contain dominator trees for
121 /// single block CFG regions, but we do want to cache the "hasSSADominance"
122 /// bit for them. We may also not have computed the DomTree yet. In either
123 /// case, the DomTree is just null.
124 ///
125 mutable DenseMap<Region *, llvm::PointerIntPair<DomTree *, 1, bool>>
126 dominanceInfos;
127};
128
129extern template class DominanceInfoBase</*IsPostDom=*/true>;
130extern template class DominanceInfoBase</*IsPostDom=*/false>;
131} // namespace detail
132
133/// A class for computing basic dominance information. Note that this
134/// class is aware of different types of regions and returns a
135/// region-kind specific concept of dominance. See RegionKindInterface.
136class DominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/false> {
137public:
138 using super::super;
139
140 /// Return true if operation A properly dominates operation B, i.e. if A and B
141 /// are in the same block and A properly dominates B within the block, or if
142 /// the block that contains A properly dominates the block that contains B. In
143 /// an SSACFG region, Operation A dominates Operation B in the same block if A
144 /// preceeds B. In a Graph region, all operations in a block dominate all
145 /// other operations in the same block.
146 ///
147 /// The `enclosingOpOk` flag says whether we should return true if the B op
148 /// is enclosed by a region on A.
149 bool properlyDominates(Operation *a, Operation *b,
150 bool enclosingOpOk = true) const {
151 return properlyDominatesImpl(a, b, enclosingOpOk);
152 }
153
154 /// Return true if operation A dominates operation B, i.e. if A and B are the
155 /// same operation or A properly dominates B.
156 bool dominates(Operation *a, Operation *b) const {
157 return a == b || properlyDominates(a, b);
158 }
159
160 /// Return true if the `a` value properly dominates operation `b`, i.e if the
161 /// operation that defines `a` properlyDominates `b` and the operation that
162 /// defines `a` does not contain `b`.
163 bool properlyDominates(Value a, Operation *b) const;
164
165 /// Return true if the `a` value dominates operation `b`.
166 bool dominates(Value a, Operation *b) const {
167 return (Operation *)a.getDefiningOp() == b || properlyDominates(a, b);
168 }
169
170 /// Return true if the specified block A dominates block B, i.e. if block A
171 /// and block B are the same block or block A properly dominates block B.
172 bool dominates(Block *a, Block *b) const {
173 return a == b || properlyDominates(a, b);
174 }
175
176 /// Return true if the specified block A properly dominates block B, i.e.: if
177 /// block A contains block B, or if the region which contains block A also
178 /// contains block B or some parent of block B and block A dominates that
179 /// block in that kind of region. In an SSACFG region, block A dominates
180 /// block B if all control flow paths from the entry block to block B flow
181 /// through block A. In a Graph region, all blocks dominate all other blocks.
182 bool properlyDominates(Block *a, Block *b) const {
183 return super::properlyDominates(a, b);
184 }
185
186private:
187 // Return true if operation A properly dominates operation B. The
188 /// 'enclosingOpOk' flag says whether we should return true if the b op is
189 /// enclosed by a region on 'A'.
190 bool properlyDominatesImpl(Operation *a, Operation *b,
191 bool enclosingOpOk) const;
192};
193
194/// A class for computing basic postdominance information.
195class PostDominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/true> {
196public:
197 using super::super;
198
199 /// Return true if operation A properly postdominates operation B.
200 bool properlyPostDominates(Operation *a, Operation *b);
201
202 /// Return true if operation A postdominates operation B.
203 bool postDominates(Operation *a, Operation *b) {
204 return a == b || properlyPostDominates(a, b);
205 }
206
207 /// Return true if the specified block A properly postdominates block B.
208 bool properlyPostDominates(Block *a, Block *b) {
209 return super::properlyDominates(a, b);
210 }
211
212 /// Return true if the specified block A postdominates block B.
213 bool postDominates(Block *a, Block *b) {
214 return a == b || properlyPostDominates(a, b);
215 }
216};
217
218} // namespace mlir
219
220namespace llvm {
221
222/// DominatorTree GraphTraits specialization so the DominatorTree can be
223/// iterated by generic graph iterators.
224template <>
225struct GraphTraits<mlir::DominanceInfoNode *> {
226 using ChildIteratorType = mlir::DominanceInfoNode::const_iterator;
227 using NodeRef = mlir::DominanceInfoNode *;
228
229 static NodeRef getEntryNode(NodeRef N) { return N; }
230 static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
231 static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
232};
233
234template <>
235struct GraphTraits<const mlir::DominanceInfoNode *> {
236 using ChildIteratorType = mlir::DominanceInfoNode::const_iterator;
237 using NodeRef = const mlir::DominanceInfoNode *;
238
239 static NodeRef getEntryNode(NodeRef N) { return N; }
240 static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
241 static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
242};
243
244} // namespace llvm
245#endif
246

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