MLIR  18.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  /// Get the root dominance node of the given region. Note that this operation
58  /// is only defined for multi-block regions!
60  auto domInfo = getDominanceInfo(region, /*needsDomTree*/ true).getPointer();
61  assert(domInfo && "Region isn't multiblock");
62  return domInfo->getRootNode();
63  }
64 
65  /// Return the dominance node from the Region containing block A. This only
66  /// works for multi-block regions.
68  return getDomTree(a->getParent()).getNode(a);
69  }
70 
71  /// Return true if the specified block is reachable from the entry
72  /// block of its region.
73  bool isReachableFromEntry(Block *a) const;
74 
75  /// Return true if operations in the specified block are known to obey SSA
76  /// dominance requirements. False if the block is a graph region or unknown.
77  bool hasSSADominance(Block *block) const {
78  return hasSSADominance(block->getParent());
79  }
80  /// Return true if operations in the specified block are known to obey SSA
81  /// dominance requirements. False if the block is a graph region or unknown.
82  bool hasSSADominance(Region *region) const {
83  return getDominanceInfo(region, /*needsDomTree=*/false).getInt();
84  }
85 
86  DomTree &getDomTree(Region *region) const {
87  assert(!region->hasOneBlock() &&
88  "Can't get DomTree for single block regions");
89  return *getDominanceInfo(region, /*needsDomTree=*/true).getPointer();
90  }
91 
92 protected:
94 
95  /// Return the dom tree and "hasSSADominance" bit for the given region. The
96  /// DomTree will be null for single-block regions. This lazily constructs the
97  /// DomTree on demand when needsDomTree=true.
98  llvm::PointerIntPair<DomTree *, 1, bool>
99  getDominanceInfo(Region *region, bool needsDomTree) const;
100 
101  /// Return true if the specified block A properly dominates block B.
102  bool properlyDominates(Block *a, Block *b) const;
103 
104  /// A mapping of regions to their base dominator tree and a cached
105  /// "hasSSADominance" bit. This map does not contain dominator trees for
106  /// single block CFG regions, but we do want to cache the "hasSSADominance"
107  /// bit for them. We may also not have computed the DomTree yet. In either
108  /// case, the DomTree is just null.
109  ///
112 };
113 
114 extern template class DominanceInfoBase</*IsPostDom=*/true>;
115 extern template class DominanceInfoBase</*IsPostDom=*/false>;
116 } // namespace detail
117 
118 /// A class for computing basic dominance information. Note that this
119 /// class is aware of different types of regions and returns a
120 /// region-kind specific concept of dominance. See RegionKindInterface.
121 class DominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/false> {
122 public:
123  using super::super;
124 
125  /// Return true if operation A properly dominates operation B, i.e. if A and B
126  /// are in the same block and A properly dominates B within the block, or if
127  /// the block that contains A properly dominates the block that contains B. In
128  /// an SSACFG region, Operation A dominates Operation B in the same block if A
129  /// preceeds B. In a Graph region, all operations in a block dominate all
130  /// other operations in the same block.
131  ///
132  /// The `enclosingOpOk` flag says whether we should return true if the B op
133  /// is enclosed by a region on A.
135  bool enclosingOpOk = true) const {
136  return properlyDominatesImpl(a, b, enclosingOpOk);
137  }
138 
139  /// Return true if operation A dominates operation B, i.e. if A and B are the
140  /// same operation or A properly dominates B.
141  bool dominates(Operation *a, Operation *b) const {
142  return a == b || properlyDominates(a, b);
143  }
144 
145  /// Return true if the `a` value properly dominates operation `b`, i.e if the
146  /// operation that defines `a` properlyDominates `b` and the operation that
147  /// defines `a` does not contain `b`.
148  bool properlyDominates(Value a, Operation *b) const;
149 
150  /// Return true if the `a` value dominates operation `b`.
151  bool dominates(Value a, Operation *b) const {
152  return (Operation *)a.getDefiningOp() == b || properlyDominates(a, b);
153  }
154 
155  /// Return true if the specified block A dominates block B, i.e. if block A
156  /// and block B are the same block or block A properly dominates block B.
157  bool dominates(Block *a, Block *b) const {
158  return a == b || properlyDominates(a, b);
159  }
160 
161  /// Return true if the specified block A properly dominates block B, i.e.: if
162  /// block A contains block B, or if the region which contains block A also
163  /// contains block B or some parent of block B and block A dominates that
164  /// block in that kind of region. In an SSACFG region, block A dominates
165  /// block B if all control flow paths from the entry block to block B flow
166  /// through block A. In a Graph region, all blocks dominate all other blocks.
167  bool properlyDominates(Block *a, Block *b) const {
168  return super::properlyDominates(a, b);
169  }
170 
171 private:
172  // Return true if operation A properly dominates operation B. The
173  /// 'enclosingOpOk' flag says whether we should return true if the b op is
174  /// enclosed by a region on 'A'.
175  bool properlyDominatesImpl(Operation *a, Operation *b,
176  bool enclosingOpOk) const;
177 };
178 
179 /// A class for computing basic postdominance information.
180 class PostDominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/true> {
181 public:
182  using super::super;
183 
184  /// Return true if operation A properly postdominates operation B.
185  bool properlyPostDominates(Operation *a, Operation *b);
186 
187  /// Return true if operation A postdominates operation B.
189  return a == b || properlyPostDominates(a, b);
190  }
191 
192  /// Return true if the specified block A properly postdominates block B.
194  return super::properlyDominates(a, b);
195  }
196 
197  /// Return true if the specified block A postdominates block B.
198  bool postDominates(Block *a, Block *b) {
199  return a == b || properlyPostDominates(a, b);
200  }
201 };
202 
203 } // namespace mlir
204 
205 namespace llvm {
206 
207 /// DominatorTree GraphTraits specialization so the DominatorTree can be
208 /// iterated by generic graph iterators.
209 template <>
210 struct GraphTraits<mlir::DominanceInfoNode *> {
211  using ChildIteratorType = mlir::DominanceInfoNode::const_iterator;
213 
214  static NodeRef getEntryNode(NodeRef N) { return N; }
215  static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
216  static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
217 };
218 
219 template <>
220 struct GraphTraits<const mlir::DominanceInfoNode *> {
221  using ChildIteratorType = mlir::DominanceInfoNode::const_iterator;
223 
224  static NodeRef getEntryNode(NodeRef N) { return N; }
225  static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
226  static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
227 };
228 
229 } // namespace llvm
230 #endif
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
A class for computing basic dominance information.
Definition: Dominance.h:121
bool dominates(Block *a, Block *b) const
Return true if the specified block A dominates block B, i.e.
Definition: Dominance.h:157
bool dominates(Value a, Operation *b) const
Return true if the a value dominates operation b.
Definition: Dominance.h:151
bool properlyDominates(Operation *a, Operation *b, bool enclosingOpOk=true) const
Return true if operation A properly dominates operation B, i.e.
Definition: Dominance.h:134
bool properlyDominates(Block *a, Block *b) const
Return true if the specified block A properly dominates block B, i.e.
Definition: Dominance.h:167
bool dominates(Operation *a, Operation *b) const
Return true if operation A dominates operation B, i.e.
Definition: Dominance.h:141
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
A class for computing basic postdominance information.
Definition: Dominance.h:180
bool properlyPostDominates(Block *a, Block *b)
Return true if the specified block A properly postdominates block B.
Definition: Dominance.h:193
bool postDominates(Block *a, Block *b)
Return true if the specified block A postdominates block B.
Definition: Dominance.h:198
bool postDominates(Operation *a, Operation *b)
Return true if operation A postdominates operation B.
Definition: Dominance.h:188
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:93
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
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:111
bool hasSSADominance(Region *region) const
Return true if operations in the specified block are known to obey SSA dominance requirements.
Definition: Dominance.h:82
DominanceInfoNode * getNode(Block *a)
Return the dominance node from the Region containing block A.
Definition: Dominance.h:67
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:59
bool hasSSADominance(Block *block) const
Return true if operations in the specified block are known to obey SSA dominance requirements.
Definition: Dominance.h:77
DomTree & getDomTree(Region *region) const
Definition: Dominance.h:86
Include the generated interface declarations.
Definition: CallGraph.h:229
This header declares functions that assist transformations in the MemRef dialect.
llvm::DomTreeNodeBase< Block > DominanceInfoNode
Definition: Dominance.h:30
const mlir::DominanceInfoNode * NodeRef
Definition: Dominance.h:222
mlir::DominanceInfoNode::const_iterator ChildIteratorType
Definition: Dominance.h:221
static ChildIteratorType child_end(NodeRef N)
Definition: Dominance.h:226
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominance.h:225
static ChildIteratorType child_end(NodeRef N)
Definition: Dominance.h:216
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominance.h:215
mlir::DominanceInfoNode::const_iterator ChildIteratorType
Definition: Dominance.h:211
static NodeRef getEntryNode(NodeRef N)
Definition: Dominance.h:214