MLIR  20.0.0git
Dominance.h
Go to the documentation of this file.
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 
23 #include "llvm/Support/GenericDomTree.h"
24 
25 extern template class llvm::DominatorTreeBase<mlir::Block, false>;
26 extern template class llvm::DominatorTreeBase<mlir::Block, true>;
27 extern template class llvm::DomTreeNodeBase<mlir::Block>;
28 
29 namespace mlir {
30 using DominanceInfoNode = llvm::DomTreeNodeBase<Block>;
31 class Operation;
32 
33 namespace detail {
34 template <bool IsPostDom>
36  using DomTree = llvm::DominatorTreeBase<Block, IsPostDom>;
37 
38 public:
39  DominanceInfoBase(Operation *op = nullptr) {}
43 
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!
75  auto domInfo = getDominanceInfo(region, /*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.
83  return getDomTree(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=*/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=*/true).getPointer();
105  }
106 
107 protected:
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  ///
127 };
128 
129 extern template class DominanceInfoBase</*IsPostDom=*/true>;
130 extern 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.
136 class DominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/false> {
137 public:
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.
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 
186 private:
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.
195 class PostDominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/true> {
196 public:
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.
204  return a == b || properlyPostDominates(a, b);
205  }
206 
207  /// Return true if the specified block A properly postdominates 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 
220 namespace llvm {
221 
222 /// DominatorTree GraphTraits specialization so the DominatorTree can be
223 /// iterated by generic graph iterators.
224 template <>
225 struct GraphTraits<mlir::DominanceInfoNode *> {
226  using ChildIteratorType = mlir::DominanceInfoNode::const_iterator;
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 
234 template <>
235 struct GraphTraits<const mlir::DominanceInfoNode *> {
236  using ChildIteratorType = mlir::DominanceInfoNode::const_iterator;
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
Block represents an ordered list of Operations.
Definition: Block.h:31
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
Definition: Block.cpp:26
iterator begin()
Definition: Block.h:141
A class for computing basic dominance information.
Definition: Dominance.h:136
bool dominates(Block *a, Block *b) const
Return true if the specified block A dominates block B, i.e.
Definition: Dominance.h:172
bool dominates(Value a, Operation *b) const
Return true if the a value dominates operation b.
Definition: Dominance.h:166
bool properlyDominates(Operation *a, Operation *b, bool enclosingOpOk=true) const
Return true if operation A properly dominates operation B, i.e.
Definition: Dominance.h:149
bool properlyDominates(Block *a, Block *b) const
Return true if the specified block A properly dominates block B, i.e.
Definition: Dominance.h:182
bool dominates(Operation *a, Operation *b) const
Return true if operation A dominates operation B, i.e.
Definition: Dominance.h:156
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
A class for computing basic postdominance information.
Definition: Dominance.h:195
bool properlyPostDominates(Block *a, Block *b)
Return true if the specified block A properly postdominates block B.
Definition: Dominance.h:208
bool postDominates(Block *a, Block *b)
Return true if the specified block A postdominates block B.
Definition: Dominance.h:213
bool postDominates(Operation *a, Operation *b)
Return true if operation A postdominates operation B.
Definition: Dominance.h:203
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
bool hasOneBlock()
Return true if this region has exactly one block.
Definition: Region.h:68
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
Block * findNearestCommonDominator(BlockRangeT &&blocks) const
Finds the nearest common dominator block for the given range of blocks.
Definition: Dominance.h:60
DenseMap< Region *, llvm::PointerIntPair< DomTree *, 1, bool > > dominanceInfos
A mapping of regions to their base dominator tree and a cached "hasSSADominance" bit.
Definition: Dominance.h:126
bool hasSSADominance(Region *region) const
Return true if operations in the specified block are known to obey SSA dominance requirements.
Definition: Dominance.h:97
DominanceInfoNode * getNode(Block *a)
Return the dominance node from the Region containing block A.
Definition: Dominance.h:82
DominanceInfoBase(const DominanceInfoBase &)=delete
DominanceInfoBase & operator=(DominanceInfoBase &&)=default
DominanceInfoBase(DominanceInfoBase &&)=default
DominanceInfoBase & operator=(const DominanceInfoBase &)=delete
DominanceInfoBase(Operation *op=nullptr)
Definition: Dominance.h:39
DominanceInfoNode * getRootNode(Region *region)
Get the root dominance node of the given region.
Definition: Dominance.h:74
bool hasSSADominance(Block *block) const
Return true if operations in the specified block are known to obey SSA dominance requirements.
Definition: Dominance.h:92
DomTree & getDomTree(Region *region) const
Definition: Dominance.h:101
The OpAsmOpInterface, see OpAsmInterface.td for more details.
Definition: CallGraph.h:229
Include the generated interface declarations.
llvm::DomTreeNodeBase< Block > DominanceInfoNode
Definition: Dominance.h:30
const mlir::DominanceInfoNode * NodeRef
Definition: Dominance.h:237
mlir::DominanceInfoNode::const_iterator ChildIteratorType
Definition: Dominance.h:236
static ChildIteratorType child_end(NodeRef N)
Definition: Dominance.h:241
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominance.h:240
static ChildIteratorType child_end(NodeRef N)
Definition: Dominance.h:231
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominance.h:230
mlir::DominanceInfoNode::const_iterator ChildIteratorType
Definition: Dominance.h:226
static NodeRef getEntryNode(NodeRef N)
Definition: Dominance.h:229