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). |
43 | class SuccessorOperands { |
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. |
86 | MutableOperandRange getMutableForwardedOperands() const { |
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: 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: subStart - producedOperandCount, subLen); |
104 | } |
105 | |
106 | /// Add new operands that are forwarded to the successor. |
107 | void append(ValueRange valueRange) { forwardedOperands.append(values: 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 | // RegionBranchOpInterface |
147 | //===----------------------------------------------------------------------===// |
148 | |
149 | namespace detail { |
150 | /// Verify that types match along control flow edges described the given op. |
151 | LogicalResult verifyTypesAlongControlFlowEdges(Operation *op); |
152 | } // namespace detail |
153 | |
154 | /// This class represents a successor of a region. A region successor can either |
155 | /// be another region, or the parent operation. If the successor is a region, |
156 | /// this class represents the destination region, as well as a set of arguments |
157 | /// from that region that will be populated when control flows into the region. |
158 | /// If the successor is the parent operation, this class represents an optional |
159 | /// set of results that will be populated when control returns to the parent |
160 | /// operation. |
161 | /// |
162 | /// This interface assumes that the values from the current region that are used |
163 | /// to populate the successor inputs are the operands of the return-like |
164 | /// terminator operations in the blocks within this region. |
165 | class RegionSuccessor { |
166 | public: |
167 | /// Initialize a successor that branches to another region of the parent |
168 | /// operation. |
169 | RegionSuccessor(Region *region, Block::BlockArgListType regionInputs = {}) |
170 | : region(region), inputs(regionInputs) {} |
171 | /// Initialize a successor that branches back to/out of the parent operation. |
172 | RegionSuccessor(Operation::result_range results) |
173 | : inputs(ValueRange(results)) {} |
174 | /// Constructor with no arguments. |
175 | RegionSuccessor() : inputs(ValueRange()) {} |
176 | |
177 | /// Return the given region successor. Returns nullptr if the successor is the |
178 | /// parent operation. |
179 | Region *getSuccessor() const { return region; } |
180 | |
181 | /// Return true if the successor is the parent operation. |
182 | bool isParent() const { return region == nullptr; } |
183 | |
184 | /// Return the inputs to the successor that are remapped by the exit values of |
185 | /// the current region. |
186 | ValueRange getSuccessorInputs() const { return inputs; } |
187 | |
188 | private: |
189 | Region *region{nullptr}; |
190 | ValueRange inputs; |
191 | }; |
192 | |
193 | /// This class represents a point being branched from in the methods of the |
194 | /// `RegionBranchOpInterface`. |
195 | /// One can branch from one of two kinds of places: |
196 | /// * The parent operation (aka the `RegionBranchOpInterface` implementation) |
197 | /// * A region within the parent operation. |
198 | class RegionBranchPoint { |
199 | public: |
200 | /// Returns an instance of `RegionBranchPoint` representing the parent |
201 | /// operation. |
202 | static constexpr RegionBranchPoint parent() { return RegionBranchPoint(); } |
203 | |
204 | /// Creates a `RegionBranchPoint` that branches from the given region. |
205 | /// The pointer must not be null. |
206 | RegionBranchPoint(Region *region) : maybeRegion(region) { |
207 | assert(region && "Region must not be null" ); |
208 | } |
209 | |
210 | RegionBranchPoint(Region ®ion) : RegionBranchPoint(®ion) {} |
211 | |
212 | /// Explicitly stops users from constructing with `nullptr`. |
213 | RegionBranchPoint(std::nullptr_t) = delete; |
214 | |
215 | /// Constructs a `RegionBranchPoint` from the the target of a |
216 | /// `RegionSuccessor` instance. |
217 | RegionBranchPoint(RegionSuccessor successor) { |
218 | if (successor.isParent()) |
219 | maybeRegion = nullptr; |
220 | else |
221 | maybeRegion = successor.getSuccessor(); |
222 | } |
223 | |
224 | /// Assigns a region being branched from. |
225 | RegionBranchPoint &operator=(Region ®ion) { |
226 | maybeRegion = ®ion; |
227 | return *this; |
228 | } |
229 | |
230 | /// Returns true if branching from the parent op. |
231 | bool isParent() const { return maybeRegion == nullptr; } |
232 | |
233 | /// Returns the region if branching from a region. |
234 | /// A null pointer otherwise. |
235 | Region *getRegionOrNull() const { return maybeRegion; } |
236 | |
237 | /// Returns true if the two branch points are equal. |
238 | friend bool operator==(RegionBranchPoint lhs, RegionBranchPoint rhs) { |
239 | return lhs.maybeRegion == rhs.maybeRegion; |
240 | } |
241 | |
242 | private: |
243 | // Private constructor to encourage the use of `RegionBranchPoint::parent`. |
244 | constexpr RegionBranchPoint() : maybeRegion(nullptr) {} |
245 | |
246 | /// Internal encoding. Uses nullptr for representing branching from the parent |
247 | /// op and the region being branched from otherwise. |
248 | Region *maybeRegion; |
249 | }; |
250 | |
251 | inline bool operator!=(RegionBranchPoint lhs, RegionBranchPoint rhs) { |
252 | return !(lhs == rhs); |
253 | } |
254 | |
255 | /// This class represents upper and lower bounds on the number of times a region |
256 | /// of a `RegionBranchOpInterface` can be invoked. The lower bound is at least |
257 | /// zero, but the upper bound may not be known. |
258 | class InvocationBounds { |
259 | public: |
260 | /// Create invocation bounds. The lower bound must be at least 0 and only the |
261 | /// upper bound can be unknown. |
262 | InvocationBounds(unsigned lb, std::optional<unsigned> ub) |
263 | : lower(lb), upper(ub) { |
264 | assert((!ub || ub >= lb) && "upper bound cannot be less than lower bound" ); |
265 | } |
266 | |
267 | /// Return the lower bound. |
268 | unsigned getLowerBound() const { return lower; } |
269 | |
270 | /// Return the upper bound. |
271 | std::optional<unsigned> getUpperBound() const { return upper; } |
272 | |
273 | /// Returns the unknown invocation bounds, i.e., there is no information on |
274 | /// how many times a region may be invoked. |
275 | static InvocationBounds getUnknown() { return {0, std::nullopt}; } |
276 | |
277 | private: |
278 | /// The minimum number of times the successor region will be invoked. |
279 | unsigned lower; |
280 | /// The maximum number of times the successor region will be invoked or |
281 | /// `std::nullopt` if an upper bound is not known. |
282 | std::optional<unsigned> upper; |
283 | }; |
284 | |
285 | /// Return `true` if `a` and `b` are in mutually exclusive regions as per |
286 | /// RegionBranchOpInterface. |
287 | bool insideMutuallyExclusiveRegions(Operation *a, Operation *b); |
288 | |
289 | /// Return the first enclosing region of the given op that may be executed |
290 | /// repetitively as per RegionBranchOpInterface or `nullptr` if no such region |
291 | /// exists. |
292 | Region *getEnclosingRepetitiveRegion(Operation *op); |
293 | |
294 | /// Return the first enclosing region of the given Value that may be executed |
295 | /// repetitively as per RegionBranchOpInterface or `nullptr` if no such region |
296 | /// exists. |
297 | Region *getEnclosingRepetitiveRegion(Value value); |
298 | |
299 | //===----------------------------------------------------------------------===// |
300 | // ControlFlow Traits |
301 | //===----------------------------------------------------------------------===// |
302 | |
303 | namespace OpTrait { |
304 | /// This trait indicates that a terminator operation is "return-like". This |
305 | /// means that it exits its current region and forwards its operands as "exit" |
306 | /// values to the parent region. Operations with this trait are not permitted to |
307 | /// contain successors or produce results. |
308 | template <typename ConcreteType> |
309 | struct ReturnLike : public TraitBase<ConcreteType, ReturnLike> { |
310 | static LogicalResult verifyTrait(Operation *op) { |
311 | static_assert(ConcreteType::template hasTrait<IsTerminator>(), |
312 | "expected operation to be a terminator" ); |
313 | static_assert(ConcreteType::template hasTrait<ZeroResults>(), |
314 | "expected operation to have zero results" ); |
315 | static_assert(ConcreteType::template hasTrait<ZeroSuccessors>(), |
316 | "expected operation to have zero successors" ); |
317 | return success(); |
318 | } |
319 | }; |
320 | } // namespace OpTrait |
321 | |
322 | } // namespace mlir |
323 | |
324 | //===----------------------------------------------------------------------===// |
325 | // ControlFlow Interfaces |
326 | //===----------------------------------------------------------------------===// |
327 | |
328 | /// Include the generated interface declarations. |
329 | #include "mlir/Interfaces/ControlFlowInterfaces.h.inc" |
330 | |
331 | #endif // MLIR_INTERFACES_CONTROLFLOWINTERFACES_H |
332 | |