MLIR  21.0.0git
ControlFlowInterfaces.h
Go to the documentation of this file.
1 //===- ControlFlowInterfaces.h - ControlFlow Interfaces ---------*- 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 // This file contains the definitions of the branch interfaces defined in
10 // `ControlFlowInterfaces.td`.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef MLIR_INTERFACES_CONTROLFLOWINTERFACES_H
15 #define MLIR_INTERFACES_CONTROLFLOWINTERFACES_H
16 
17 #include "mlir/IR/OpDefinition.h"
18 
19 namespace mlir {
20 class BranchOpInterface;
21 class RegionBranchOpInterface;
22 
23 /// This class models how operands are forwarded to block arguments in control
24 /// flow. It consists of a number, denoting how many of the successors block
25 /// arguments are produced by the operation, followed by a range of operands
26 /// that are forwarded. The produced operands are passed to the first few
27 /// block arguments of the successor, followed by the forwarded operands.
28 /// It is unsupported to pass them in a different order.
29 ///
30 /// An example operation with both of these concepts would be a branch-on-error
31 /// operation, that internally produces an error object on the error path:
32 ///
33 /// invoke %function(%0)
34 /// label ^success ^error(%1 : i32)
35 ///
36 /// ^error(%e: !error, %arg0 : i32):
37 /// ...
38 ///
39 /// This operation would return an instance of SuccessorOperands with a produced
40 /// operand count of 1 (mapped to %e in the successor) and a forwarded
41 /// operands range consisting of %1 in the example above (mapped to %arg0 in the
42 /// successor).
44 public:
45  /// Constructs a SuccessorOperands with no produced operands that simply
46  /// forwards operands to the successor.
47  explicit SuccessorOperands(MutableOperandRange forwardedOperands);
48 
49  /// Constructs a SuccessorOperands with the given amount of produced operands
50  /// and forwarded operands.
51  SuccessorOperands(unsigned producedOperandCount,
52  MutableOperandRange forwardedOperands);
53 
54  /// Returns the amount of operands passed to the successor. This consists both
55  /// of produced operands by the operation as well as forwarded ones.
56  unsigned size() const {
57  return producedOperandCount + forwardedOperands.size();
58  }
59 
60  /// Returns true if there are no successor operands.
61  bool empty() const { return size() == 0; }
62 
63  /// Returns the amount of operands that are produced internally by the
64  /// operation. These are passed to the first few block arguments.
65  unsigned getProducedOperandCount() const { return producedOperandCount; }
66 
67  /// Returns true if the successor operand denoted by `index` is produced by
68  /// the operation.
69  bool isOperandProduced(unsigned index) const {
70  return index < producedOperandCount;
71  }
72 
73  /// Returns the Value that is passed to the successors block argument denoted
74  /// by `index`. If it is produced by the operation, no such value exists and
75  /// a null Value is returned.
76  Value operator[](unsigned index) const {
77  if (isOperandProduced(index))
78  return Value();
79  return forwardedOperands[index - producedOperandCount].get();
80  }
81 
82  /// Get the range of operands that are simply forwarded to the successor.
83  OperandRange getForwardedOperands() const { return forwardedOperands; }
84 
85  /// Get the range of operands that are simply forwarded to the successor.
87  return forwardedOperands;
88  }
89 
90  /// Get a slice of the operands forwarded to the successor. The given range
91  /// must not contain any operands produced by the operation.
92  MutableOperandRange slice(unsigned subStart, unsigned subLen) const {
93  assert(!isOperandProduced(subStart) &&
94  "can't slice operands produced by the operation");
95  return forwardedOperands.slice(subStart - producedOperandCount, subLen);
96  }
97 
98  /// Erase operands forwarded to the successor. The given range must
99  /// not contain any operands produced by the operation.
100  void erase(unsigned subStart, unsigned subLen = 1) {
101  assert(!isOperandProduced(subStart) &&
102  "can't erase operands produced by the operation");
103  forwardedOperands.erase(subStart - producedOperandCount, subLen);
104  }
105 
106  /// Add new operands that are forwarded to the successor.
107  void append(ValueRange valueRange) { forwardedOperands.append(valueRange); }
108 
109  /// Gets the index of the forwarded operand within the operation which maps
110  /// to the block argument denoted by `blockArgumentIndex`. The block argument
111  /// must be mapped to a forwarded operand.
112  unsigned getOperandIndex(unsigned blockArgumentIndex) const {
113  assert(!isOperandProduced(blockArgumentIndex) &&
114  "can't map operand produced by the operation");
115  OperandRange operands = forwardedOperands;
116  return operands.getBeginOperandIndex() +
117  (blockArgumentIndex - producedOperandCount);
118  }
119 
120 private:
121  /// Amount of operands that are produced internally within the operation and
122  /// passed to the first few block arguments.
123  unsigned producedOperandCount;
124  /// Range of operands that are forwarded to the remaining block arguments.
125  MutableOperandRange forwardedOperands;
126 };
127 
128 //===----------------------------------------------------------------------===//
129 // BranchOpInterface
130 //===----------------------------------------------------------------------===//
131 
132 namespace detail {
133 /// Return the `BlockArgument` corresponding to operand `operandIndex` in some
134 /// successor if `operandIndex` is within the range of `operands`, or
135 /// std::nullopt if `operandIndex` isn't a successor operand index.
136 std::optional<BlockArgument>
137 getBranchSuccessorArgument(const SuccessorOperands &operands,
138  unsigned operandIndex, Block *successor);
139 
140 /// Verify that the given operands match those of the given successor block.
141 LogicalResult verifyBranchSuccessorOperands(Operation *op, unsigned succNo,
142  const SuccessorOperands &operands);
143 } // namespace detail
144 
145 //===----------------------------------------------------------------------===//
146 // WeightedBranchOpInterface
147 //===----------------------------------------------------------------------===//
148 
149 namespace detail {
150 /// Verify that the branch weights attached to an operation
151 /// implementing WeightedBranchOpInterface are correct.
152 LogicalResult verifyBranchWeights(Operation *op);
153 } // namespace detail
154 
155 //===----------------------------------------------------------------------===//
156 // WeightedRegiobBranchOpInterface
157 //===----------------------------------------------------------------------===//
158 
159 namespace detail {
160 /// Verify that the region weights attached to an operation
161 /// implementing WeightedRegiobBranchOpInterface are correct.
162 LogicalResult verifyRegionBranchWeights(Operation *op);
163 } // namespace detail
164 
165 //===----------------------------------------------------------------------===//
166 // RegionBranchOpInterface
167 //===----------------------------------------------------------------------===//
168 
169 namespace detail {
170 /// Verify that types match along control flow edges described the given op.
171 LogicalResult verifyTypesAlongControlFlowEdges(Operation *op);
172 } // namespace detail
173 
174 /// This class represents a successor of a region. A region successor can either
175 /// be another region, or the parent operation. If the successor is a region,
176 /// this class represents the destination region, as well as a set of arguments
177 /// from that region that will be populated when control flows into the region.
178 /// If the successor is the parent operation, this class represents an optional
179 /// set of results that will be populated when control returns to the parent
180 /// operation.
181 ///
182 /// This interface assumes that the values from the current region that are used
183 /// to populate the successor inputs are the operands of the return-like
184 /// terminator operations in the blocks within this region.
186 public:
187  /// Initialize a successor that branches to another region of the parent
188  /// operation.
189  RegionSuccessor(Region *region, Block::BlockArgListType regionInputs = {})
190  : region(region), inputs(regionInputs) {}
191  /// Initialize a successor that branches back to/out of the parent operation.
193  : inputs(ValueRange(results)) {}
194  /// Constructor with no arguments.
195  RegionSuccessor() : inputs(ValueRange()) {}
196 
197  /// Return the given region successor. Returns nullptr if the successor is the
198  /// parent operation.
199  Region *getSuccessor() const { return region; }
200 
201  /// Return true if the successor is the parent operation.
202  bool isParent() const { return region == nullptr; }
203 
204  /// Return the inputs to the successor that are remapped by the exit values of
205  /// the current region.
206  ValueRange getSuccessorInputs() const { return inputs; }
207 
208 private:
209  Region *region{nullptr};
210  ValueRange inputs;
211 };
212 
213 /// This class represents a point being branched from in the methods of the
214 /// `RegionBranchOpInterface`.
215 /// One can branch from one of two kinds of places:
216 /// * The parent operation (aka the `RegionBranchOpInterface` implementation)
217 /// * A region within the parent operation.
219 public:
220  /// Returns an instance of `RegionBranchPoint` representing the parent
221  /// operation.
222  static constexpr RegionBranchPoint parent() { return RegionBranchPoint(); }
223 
224  /// Creates a `RegionBranchPoint` that branches from the given region.
225  /// The pointer must not be null.
226  RegionBranchPoint(Region *region) : maybeRegion(region) {
227  assert(region && "Region must not be null");
228  }
229 
231 
232  /// Explicitly stops users from constructing with `nullptr`.
233  RegionBranchPoint(std::nullptr_t) = delete;
234 
235  /// Constructs a `RegionBranchPoint` from the the target of a
236  /// `RegionSuccessor` instance.
238  if (successor.isParent())
239  maybeRegion = nullptr;
240  else
241  maybeRegion = successor.getSuccessor();
242  }
243 
244  /// Assigns a region being branched from.
246  maybeRegion = &region;
247  return *this;
248  }
249 
250  /// Returns true if branching from the parent op.
251  bool isParent() const { return maybeRegion == nullptr; }
252 
253  /// Returns the region if branching from a region.
254  /// A null pointer otherwise.
255  Region *getRegionOrNull() const { return maybeRegion; }
256 
257  /// Returns true if the two branch points are equal.
259  return lhs.maybeRegion == rhs.maybeRegion;
260  }
261 
262 private:
263  // Private constructor to encourage the use of `RegionBranchPoint::parent`.
264  constexpr RegionBranchPoint() : maybeRegion(nullptr) {}
265 
266  /// Internal encoding. Uses nullptr for representing branching from the parent
267  /// op and the region being branched from otherwise.
268  Region *maybeRegion;
269 };
270 
272  return !(lhs == rhs);
273 }
274 
275 /// This class represents upper and lower bounds on the number of times a region
276 /// of a `RegionBranchOpInterface` can be invoked. The lower bound is at least
277 /// zero, but the upper bound may not be known.
279 public:
280  /// Create invocation bounds. The lower bound must be at least 0 and only the
281  /// upper bound can be unknown.
282  InvocationBounds(unsigned lb, std::optional<unsigned> ub)
283  : lower(lb), upper(ub) {
284  assert((!ub || ub >= lb) && "upper bound cannot be less than lower bound");
285  }
286 
287  /// Return the lower bound.
288  unsigned getLowerBound() const { return lower; }
289 
290  /// Return the upper bound.
291  std::optional<unsigned> getUpperBound() const { return upper; }
292 
293  /// Returns the unknown invocation bounds, i.e., there is no information on
294  /// how many times a region may be invoked.
295  static InvocationBounds getUnknown() { return {0, std::nullopt}; }
296 
297 private:
298  /// The minimum number of times the successor region will be invoked.
299  unsigned lower;
300  /// The maximum number of times the successor region will be invoked or
301  /// `std::nullopt` if an upper bound is not known.
302  std::optional<unsigned> upper;
303 };
304 
305 /// Return `true` if `a` and `b` are in mutually exclusive regions as per
306 /// RegionBranchOpInterface.
307 bool insideMutuallyExclusiveRegions(Operation *a, Operation *b);
308 
309 /// Return the first enclosing region of the given op that may be executed
310 /// repetitively as per RegionBranchOpInterface or `nullptr` if no such region
311 /// exists.
312 Region *getEnclosingRepetitiveRegion(Operation *op);
313 
314 /// Return the first enclosing region of the given Value that may be executed
315 /// repetitively as per RegionBranchOpInterface or `nullptr` if no such region
316 /// exists.
317 Region *getEnclosingRepetitiveRegion(Value value);
318 
319 //===----------------------------------------------------------------------===//
320 // ControlFlow Traits
321 //===----------------------------------------------------------------------===//
322 
323 namespace OpTrait {
324 /// This trait indicates that a terminator operation is "return-like". This
325 /// means that it exits its current region and forwards its operands as "exit"
326 /// values to the parent region. Operations with this trait are not permitted to
327 /// contain successors or produce results.
328 template <typename ConcreteType>
329 struct ReturnLike : public TraitBase<ConcreteType, ReturnLike> {
330  static LogicalResult verifyTrait(Operation *op) {
331  static_assert(ConcreteType::template hasTrait<IsTerminator>(),
332  "expected operation to be a terminator");
333  static_assert(ConcreteType::template hasTrait<ZeroResults>(),
334  "expected operation to have zero results");
335  static_assert(ConcreteType::template hasTrait<ZeroSuccessors>(),
336  "expected operation to have zero successors");
337  return success();
338  }
339 };
340 } // namespace OpTrait
341 
342 } // namespace mlir
343 
344 //===----------------------------------------------------------------------===//
345 // ControlFlow Interfaces
346 //===----------------------------------------------------------------------===//
347 
348 /// Include the generated interface declarations.
349 #include "mlir/Interfaces/ControlFlowInterfaces.h.inc"
350 
351 #endif // MLIR_INTERFACES_CONTROLFLOWINTERFACES_H
MutableArrayRef< BlockArgument > BlockArgListType
Definition: Block.h:85
This class represents upper and lower bounds on the number of times a region of a RegionBranchOpInter...
static InvocationBounds getUnknown()
Returns the unknown invocation bounds, i.e., there is no information on how many times a region may b...
std::optional< unsigned > getUpperBound() const
Return the upper bound.
InvocationBounds(unsigned lb, std::optional< unsigned > ub)
Create invocation bounds.
unsigned getLowerBound() const
Return the lower bound.
This class provides a mutable adaptor for a range of operands.
Definition: ValueRange.h:118
unsigned size() const
Returns the current size of the range.
Definition: ValueRange.h:156
MutableOperandRange slice(unsigned subStart, unsigned subLen, std::optional< OperandSegment > segment=std::nullopt) const
Slice this range into a sub range, with the additional operand segment.
void erase(unsigned subStart, unsigned subLen=1)
Erase the operands within the given sub-range.
void append(ValueRange values)
Append the given values to the range.
Helper class for implementing traits.
Definition: OpDefinition.h:377
This class implements the operand iterators for the Operation class.
Definition: ValueRange.h:43
unsigned getBeginOperandIndex() const
Return the operand index of the first element of this range.
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
This class represents a point being branched from in the methods of the RegionBranchOpInterface.
RegionBranchPoint(std::nullptr_t)=delete
Explicitly stops users from constructing with nullptr.
RegionBranchPoint(RegionSuccessor successor)
Constructs a RegionBranchPoint from the the target of a RegionSuccessor instance.
bool isParent() const
Returns true if branching from the parent op.
RegionBranchPoint & operator=(Region &region)
Assigns a region being branched from.
static constexpr RegionBranchPoint parent()
Returns an instance of RegionBranchPoint representing the parent operation.
RegionBranchPoint(Region *region)
Creates a RegionBranchPoint that branches from the given region.
friend bool operator==(RegionBranchPoint lhs, RegionBranchPoint rhs)
Returns true if the two branch points are equal.
Region * getRegionOrNull() const
Returns the region if branching from a region.
This class represents a successor of a region.
RegionSuccessor(Region *region, Block::BlockArgListType regionInputs={})
Initialize a successor that branches to another region of the parent operation.
ValueRange getSuccessorInputs() const
Return the inputs to the successor that are remapped by the exit values of the current region.
RegionSuccessor()
Constructor with no arguments.
bool isParent() const
Return true if the successor is the parent operation.
Region * getSuccessor() const
Return the given region successor.
RegionSuccessor(Operation::result_range results)
Initialize a successor that branches back to/out of the parent operation.
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
This class implements the result iterators for the Operation class.
Definition: ValueRange.h:247
This class models how operands are forwarded to block arguments in control flow.
SuccessorOperands(unsigned producedOperandCount, MutableOperandRange forwardedOperands)
Constructs a SuccessorOperands with the given amount of produced operands and forwarded operands.
MutableOperandRange slice(unsigned subStart, unsigned subLen) const
Get a slice of the operands forwarded to the successor.
void erase(unsigned subStart, unsigned subLen=1)
Erase operands forwarded to the successor.
MutableOperandRange getMutableForwardedOperands() const
Get the range of operands that are simply forwarded to the successor.
SuccessorOperands(MutableOperandRange forwardedOperands)
Constructs a SuccessorOperands with no produced operands that simply forwards operands to the success...
Value operator[](unsigned index) const
Returns the Value that is passed to the successors block argument denoted by index.
unsigned getOperandIndex(unsigned blockArgumentIndex) const
Gets the index of the forwarded operand within the operation which maps to the block argument denoted...
bool isOperandProduced(unsigned index) const
Returns true if the successor operand denoted by index is produced by the operation.
unsigned getProducedOperandCount() const
Returns the amount of operands that are produced internally by the operation.
bool empty() const
Returns true if there are no successor operands.
void append(ValueRange valueRange)
Add new operands that are forwarded to the successor.
unsigned size() const
Returns the amount of operands passed to the successor.
OperandRange getForwardedOperands() const
Get the range of operands that are simply forwarded to the successor.
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:387
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
std::optional< BlockArgument > getBranchSuccessorArgument(const SuccessorOperands &operands, unsigned operandIndex, Block *successor)
Return the BlockArgument corresponding to operand operandIndex in some successor if operandIndex is w...
LogicalResult verifyRegionBranchWeights(Operation *op)
Verify that the region weights attached to an operation implementing WeightedRegiobBranchOpInterface ...
LogicalResult verifyBranchSuccessorOperands(Operation *op, unsigned succNo, const SuccessorOperands &operands)
Verify that the given operands match those of the given successor block.
LogicalResult verifyTypesAlongControlFlowEdges(Operation *op)
Verify that types match along control flow edges described the given op.
LogicalResult verifyBranchWeights(Operation *op)
Verify that the branch weights attached to an operation implementing WeightedBranchOpInterface are co...
Include the generated interface declarations.
bool insideMutuallyExclusiveRegions(Operation *a, Operation *b)
Return true if a and b are in mutually exclusive regions as per RegionBranchOpInterface.
Region * getEnclosingRepetitiveRegion(Operation *op)
Return the first enclosing region of the given op that may be executed repetitively as per RegionBran...
bool operator!=(RegionBranchPoint lhs, RegionBranchPoint rhs)
This trait indicates that a terminator operation is "return-like".
static LogicalResult verifyTrait(Operation *op)