MLIR  16.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 
28 namespace mlir {
29 using DominanceInfoNode = llvm::DomTreeNodeBase<Block>;
30 class Operation;
31 
32 namespace detail {
33 template <bool IsPostDom>
35  using DomTree = llvm::DominatorTreeBase<Block, IsPostDom>;
36 
37 public:
38  DominanceInfoBase(Operation *op = nullptr) {}
40  DominanceInfoBase &operator=(DominanceInfoBase &&) = default;
42 
43  DominanceInfoBase(const DominanceInfoBase &) = delete;
44  DominanceInfoBase &operator=(const DominanceInfoBase &) = delete;
45 
46  /// Invalidate dominance info. This can be used by clients that make major
47  /// changes to the CFG and don't have a good way to update it.
48  void invalidate() { dominanceInfos.clear(); }
49  void invalidate(Region *region) { dominanceInfos.erase(region); }
50 
51  /// Finds the nearest common dominator block for the two given blocks a
52  /// and b. If no common dominator can be found, this function will return
53  /// nullptr.
54  Block *findNearestCommonDominator(Block *a, Block *b) const;
55 
56  /// Get the root dominance node of the given region. Note that this operation
57  /// is only defined for multi-block regions!
59  auto domInfo = getDominanceInfo(region, /*needsDomTree*/ true).getPointer();
60  assert(domInfo && "Region isn't multiblock");
61  return domInfo->getRootNode();
62  }
63 
64  /// Return the dominance node from the Region containing block A. This only
65  /// works for multi-block regions.
67  return getDomTree(a->getParent()).getNode(a);
68  }
69 
70  /// Return true if the specified block is reachable from the entry
71  /// block of its region.
72  bool isReachableFromEntry(Block *a) const;
73 
74  /// Return true if operations in the specified block are known to obey SSA
75  /// dominance requirements. False if the block is a graph region or unknown.
76  bool hasSSADominance(Block *block) const {
77  return hasSSADominance(block->getParent());
78  }
79  /// Return true if operations in the specified block are known to obey SSA
80  /// dominance requirements. False if the block is a graph region or unknown.
81  bool hasSSADominance(Region *region) const {
82  return getDominanceInfo(region, /*needsDomTree=*/false).getInt();
83  }
84 
85  DomTree &getDomTree(Region *region) const {
86  assert(!region->hasOneBlock() &&
87  "Can't get DomTree for single block regions");
88  return *getDominanceInfo(region, /*needsDomTree=*/true).getPointer();
89  }
90 
91 protected:
93 
94  /// Return the dom tree and "hasSSADominance" bit for the given region. The
95  /// DomTree will be null for single-block regions. This lazily constructs the
96  /// DomTree on demand when needsDomTree=true.
97  llvm::PointerIntPair<DomTree *, 1, bool>
98  getDominanceInfo(Region *region, bool needsDomTree) const;
99 
100  /// Return true if the specified block A properly dominates block B.
101  bool properlyDominates(Block *a, Block *b) const;
102 
103  /// A mapping of regions to their base dominator tree and a cached
104  /// "hasSSADominance" bit. This map does not contain dominator trees for
105  /// single block CFG regions, but we do want to cache the "hasSSADominance"
106  /// bit for them. We may also not have computed the DomTree yet. In either
107  /// case, the DomTree is just null.
108  ///
111 };
112 } // namespace detail
113 
114 /// A class for computing basic dominance information. Note that this
115 /// class is aware of different types of regions and returns a
116 /// region-kind specific concept of dominance. See RegionKindInterface.
117 class DominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/false> {
118 public:
119  using super::super;
120 
121  /// Return true if operation A properly dominates operation B, i.e. if A and B
122  /// are in the same block and A properly dominates B within the block, or if
123  /// the block that contains A properly dominates the block that contains B. In
124  /// an SSACFG region, Operation A dominates Operation B in the same block if A
125  /// preceeds B. In a Graph region, all operations in a block dominate all
126  /// other operations in the same block.
127  ///
128  /// The `enclosingOpOk` flag says whether we should return true if the B op
129  /// is enclosed by a region on A.
131  bool enclosingOpOk = true) const {
132  return properlyDominatesImpl(a, b, enclosingOpOk);
133  }
134 
135  /// Return true if operation A dominates operation B, i.e. if A and B are the
136  /// same operation or A properly dominates B.
137  bool dominates(Operation *a, Operation *b) const {
138  return a == b || properlyDominates(a, b);
139  }
140 
141  /// Return true if the `a` value properly dominates operation `b`, i.e if the
142  /// operation that defines `a` properlyDominates `b` and the operation that
143  /// defines `a` does not contain `b`.
144  bool properlyDominates(Value a, Operation *b) const;
145 
146  /// Return true if the `a` value dominates operation `b`.
147  bool dominates(Value a, Operation *b) const {
148  return (Operation *)a.getDefiningOp() == b || properlyDominates(a, b);
149  }
150 
151  /// Return true if the specified block A dominates block B, i.e. if block A
152  /// and block B are the same block or block A properly dominates block B.
153  bool dominates(Block *a, Block *b) const {
154  return a == b || properlyDominates(a, b);
155  }
156 
157  /// Return true if the specified block A properly dominates block B, i.e.: if
158  /// block A contains block B, or if the region which contains block A also
159  /// contains block B or some parent of block B and block A dominates that
160  /// block in that kind of region. In an SSACFG region, block A dominates
161  /// block B if all control flow paths from the entry block to block B flow
162  /// through block A. In a Graph region, all blocks dominate all other blocks.
163  bool properlyDominates(Block *a, Block *b) const {
164  return super::properlyDominates(a, b);
165  }
166 
167 private:
168  // Return true if operation A properly dominates operation B. The
169  /// 'enclosingOpOk' flag says whether we should return true if the b op is
170  /// enclosed by a region on 'A'.
171  bool properlyDominatesImpl(Operation *a, Operation *b,
172  bool enclosingOpOk) const;
173 };
174 
175 /// A class for computing basic postdominance information.
176 class PostDominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/true> {
177 public:
178  using super::super;
179 
180  /// Return true if operation A properly postdominates operation B.
181  bool properlyPostDominates(Operation *a, Operation *b);
182 
183  /// Return true if operation A postdominates operation B.
185  return a == b || properlyPostDominates(a, b);
186  }
187 
188  /// Return true if the specified block A properly postdominates block B.
190  return super::properlyDominates(a, b);
191  }
192 
193  /// Return true if the specified block A postdominates block B.
194  bool postDominates(Block *a, Block *b) {
195  return a == b || properlyPostDominates(a, b);
196  }
197 };
198 
199 } // namespace mlir
200 
201 namespace llvm {
202 
203 /// DominatorTree GraphTraits specialization so the DominatorTree can be
204 /// iterated by generic graph iterators.
205 template <>
207  using ChildIteratorType = mlir::DominanceInfoNode::const_iterator;
209 
210  static NodeRef getEntryNode(NodeRef N) { return N; }
211  static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
212  static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
213 };
214 
215 template <>
217  using ChildIteratorType = mlir::DominanceInfoNode::const_iterator;
219 
220  static NodeRef getEntryNode(NodeRef N) { return N; }
221  static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
222  static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
223 };
224 
225 } // namespace llvm
226 #endif
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
static ChildIteratorType child_end(NodeRef N)
Definition: Dominance.h:212
Include the generated interface declarations.
This class contains a list of basic blocks and a link to the parent operation it is attached to...
Definition: Region.h:26
static NodeRef getEntryNode(NodeRef N)
Definition: Dominance.h:210
mlir::DominanceInfoNode::const_iterator ChildIteratorType
Definition: Dominance.h:207
bool dominates(Value a, Operation *b) const
Return true if the a value dominates operation b.
Definition: Dominance.h:147
The OpAsmOpInterface, see OpAsmInterface.td for more details.
Definition: CallGraph.h:221
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:28
Block represents an ordered list of Operations.
Definition: Block.h:29
DomTree & getDomTree(Region *region) const
Definition: Dominance.h:85
bool dominates(Block *a, Block *b) const
Return true if the specified block A dominates block B, i.e.
Definition: Dominance.h:153
A class for computing basic dominance information.
Definition: Dominance.h:117
const mlir::DominanceInfoNode * NodeRef
Definition: Dominance.h:218
DominanceInfoBase(Operation *op=nullptr)
Definition: Dominance.h:38
bool properlyPostDominates(Block *a, Block *b)
Return true if the specified block A properly postdominates block B.
Definition: Dominance.h:189
bool properlyDominates(Block *a, Block *b) const
Return true if the specified block A properly dominates block B, i.e.
Definition: Dominance.h:163
Region * getParent() const
Provide a &#39;getParent&#39; method for ilist_node_with_parent methods.
Definition: Block.cpp:26
bool hasOneBlock()
Return true if this region has exactly one block.
Definition: Region.h:68
bool hasSSADominance(Region *region) const
Return true if operations in the specified block are known to obey SSA dominance requirements.
Definition: Dominance.h:81
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominance.h:211
mlir::DominanceInfoNode::const_iterator ChildIteratorType
Definition: Dominance.h:217
void invalidate()
Invalidate dominance info.
Definition: Dominance.h:48
bool hasSSADominance(Block *block) const
Return true if operations in the specified block are known to obey SSA dominance requirements.
Definition: Dominance.h:76
DominanceInfoNode * getRootNode(Region *region)
Get the root dominance node of the given region.
Definition: Dominance.h:58
DominanceInfoNode * getNode(Block *a)
Return the dominance node from the Region containing block A.
Definition: Dominance.h:66
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:110
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
bool postDominates(Block *a, Block *b)
Return true if the specified block A postdominates block B.
Definition: Dominance.h:194
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
bool dominates(Operation *a, Operation *b) const
Return true if operation A dominates operation B, i.e.
Definition: Dominance.h:137
void invalidate(Region *region)
Definition: Dominance.h:49
bool postDominates(Operation *a, Operation *b)
Return true if operation A postdominates operation B.
Definition: Dominance.h:184
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominance.h:221
static ChildIteratorType child_end(NodeRef N)
Definition: Dominance.h:222
A class for computing basic postdominance information.
Definition: Dominance.h:176
llvm::DomTreeNodeBase< Block > DominanceInfoNode
Definition: Dominance.h:29