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#include "mlir/IR/Operation.h"
19#include "mlir/IR/PatternMatch.h"
20#include "llvm/ADT/PointerUnion.h"
21#include "llvm/ADT/STLExtras.h"
22#include "llvm/Support/raw_ostream.h"
23
24namespace mlir {
25class BranchOpInterface;
26class RegionBranchOpInterface;
27class RegionBranchTerminatorOpInterface;
28
29/// This class models how operands are forwarded to block arguments in control
30/// flow. It consists of a number, denoting how many of the successors block
31/// arguments are produced by the operation, followed by a range of operands
32/// that are forwarded. The produced operands are passed to the first few
33/// block arguments of the successor, followed by the forwarded operands.
34/// It is unsupported to pass them in a different order.
35///
36/// An example operation with both of these concepts would be a branch-on-error
37/// operation, that internally produces an error object on the error path:
38///
39/// invoke %function(%0)
40/// label ^success ^error(%1 : i32)
41///
42/// ^error(%e: !error, %arg0 : i32):
43/// ...
44///
45/// This operation would return an instance of SuccessorOperands with a produced
46/// operand count of 1 (mapped to %e in the successor) and a forwarded
47/// operands range consisting of %1 in the example above (mapped to %arg0 in the
48/// successor).
49class SuccessorOperands {
50public:
51 /// Constructs a SuccessorOperands with no produced operands that simply
52 /// forwards operands to the successor.
53 explicit SuccessorOperands(MutableOperandRange forwardedOperands);
54
55 /// Constructs a SuccessorOperands with the given amount of produced operands
56 /// and forwarded operands.
57 SuccessorOperands(unsigned producedOperandCount,
58 MutableOperandRange forwardedOperands);
59
60 /// Returns the amount of operands passed to the successor. This consists both
61 /// of produced operands by the operation as well as forwarded ones.
62 unsigned size() const {
63 return producedOperandCount + forwardedOperands.size();
64 }
65
66 /// Returns true if there are no successor operands.
67 bool empty() const { return size() == 0; }
68
69 /// Returns the amount of operands that are produced internally by the
70 /// operation. These are passed to the first few block arguments.
71 unsigned getProducedOperandCount() const { return producedOperandCount; }
72
73 /// Returns true if the successor operand denoted by `index` is produced by
74 /// the operation.
75 bool isOperandProduced(unsigned index) const {
76 return index < producedOperandCount;
77 }
78
79 /// Returns the Value that is passed to the successors block argument denoted
80 /// by `index`. If it is produced by the operation, no such value exists and
81 /// a null Value is returned.
82 Value operator[](unsigned index) const {
83 if (isOperandProduced(index))
84 return Value();
85 return forwardedOperands[index - producedOperandCount].get();
86 }
87
88 /// Get the range of operands that are simply forwarded to the successor.
89 OperandRange getForwardedOperands() const { return forwardedOperands; }
90
91 /// Get the range of operands that are simply forwarded to the successor.
92 MutableOperandRange getMutableForwardedOperands() const {
93 return forwardedOperands;
94 }
95
96 /// Get a slice of the operands forwarded to the successor. The given range
97 /// must not contain any operands produced by the operation.
98 MutableOperandRange slice(unsigned subStart, unsigned subLen) const {
99 assert(!isOperandProduced(subStart) &&
100 "can't slice operands produced by the operation");
101 return forwardedOperands.slice(subStart: subStart - producedOperandCount, subLen);
102 }
103
104 /// Erase operands forwarded to the successor. The given range must
105 /// not contain any operands produced by the operation.
106 void erase(unsigned subStart, unsigned subLen = 1) {
107 assert(!isOperandProduced(subStart) &&
108 "can't erase operands produced by the operation");
109 forwardedOperands.erase(subStart: subStart - producedOperandCount, subLen);
110 }
111
112 /// Add new operands that are forwarded to the successor.
113 void append(ValueRange valueRange) { forwardedOperands.append(values: valueRange); }
114
115 /// Gets the index of the forwarded operand within the operation which maps
116 /// to the block argument denoted by `blockArgumentIndex`. The block argument
117 /// must be mapped to a forwarded operand.
118 unsigned getOperandIndex(unsigned blockArgumentIndex) const {
119 assert(!isOperandProduced(blockArgumentIndex) &&
120 "can't map operand produced by the operation");
121 OperandRange operands = forwardedOperands;
122 return operands.getBeginOperandIndex() +
123 (blockArgumentIndex - producedOperandCount);
124 }
125
126private:
127 /// Amount of operands that are produced internally within the operation and
128 /// passed to the first few block arguments.
129 unsigned producedOperandCount;
130 /// Range of operands that are forwarded to the remaining block arguments.
131 MutableOperandRange forwardedOperands;
132};
133
134//===----------------------------------------------------------------------===//
135// BranchOpInterface
136//===----------------------------------------------------------------------===//
137
138namespace detail {
139/// Return the `BlockArgument` corresponding to operand `operandIndex` in some
140/// successor if `operandIndex` is within the range of `operands`, or
141/// std::nullopt if `operandIndex` isn't a successor operand index.
142std::optional<BlockArgument>
143getBranchSuccessorArgument(const SuccessorOperands &operands,
144 unsigned operandIndex, Block *successor);
145
146/// Verify that the given operands match those of the given successor block.
147LogicalResult verifyBranchSuccessorOperands(Operation *op, unsigned succNo,
148 const SuccessorOperands &operands);
149} // namespace detail
150
151//===----------------------------------------------------------------------===//
152// WeightedBranchOpInterface
153//===----------------------------------------------------------------------===//
154
155namespace detail {
156/// Verify that the branch weights attached to an operation
157/// implementing WeightedBranchOpInterface are correct.
158LogicalResult verifyBranchWeights(Operation *op);
159} // namespace detail
160
161//===----------------------------------------------------------------------===//
162// WeightedRegiobBranchOpInterface
163//===----------------------------------------------------------------------===//
164
165namespace detail {
166/// Verify that the region weights attached to an operation
167/// implementing WeightedRegiobBranchOpInterface are correct.
168LogicalResult verifyRegionBranchWeights(Operation *op);
169} // namespace detail
170
171//===----------------------------------------------------------------------===//
172// RegionBranchOpInterface
173//===----------------------------------------------------------------------===//
174
175namespace detail {
176/// Verify that types match along control flow edges described the given op.
177LogicalResult verifyRegionBranchOpInterface(Operation *op);
178} // namespace detail
179
180/// A mapping from successor operands to successor inputs.
181///
182/// * A successor operand is an operand of a region branch op or region
183/// branch terminator, that is forwarded to a successor input.
184/// * A successor input is a block argument of a region or a result of the
185/// region branch op, that is populated by a successor operand.
186///
187/// The mapping is 1:N. Each successor operand may be forwarded to multiple
188/// successor inputs. (Because the control flow can dispatch to multiple
189/// possible successors.) Operands that not forwarded at all are not present in
190/// the mapping.
191using RegionBranchSuccessorMapping = DenseMap<OpOperand *, SmallVector<Value>>;
192using RegionBranchInverseSuccessorMapping =
193 DenseMap<Value, SmallVector<OpOperand *>>;
194
195/// This class represents a successor of a region. A region successor can either
196/// target another region or target an ancestor operation (at the moment,
197/// limited to the immediate parent operation). In the latter case, the control
198/// flow branches after/out of the target operation.
199class RegionSuccessor {
200public:
201 /// Initialize a successor that branches to a region of the parent operation.
202 RegionSuccessor(Region *region) : successor(region) {
203 assert(region && "Region must not be null");
204 }
205
206 /// Initialize a successor that branches after/out of an operation.
207 RegionSuccessor(Operation *operation) : successor(operation) {
208 assert(operation && "Operation must not be null");
209 }
210
211 /// Return the given region successor. Returns nullptr if the successor is an
212 /// operation.
213 Region *getSuccessor() const {
214 return dyn_cast_if_present<Region *>(Val: successor);
215 }
216
217 /// Return the given operation successor. Returns nullptr if the successor is
218 /// a region.
219 Operation *getSuccessorOp() const {
220 return dyn_cast_if_present<Operation *>(Val: successor);
221 }
222
223 /// Return true if the successor is a region.
224 bool isRegion() const { return isa<Region *>(Val: successor); }
225
226 /// Return true if the successor is an operation.
227 bool isOperation() const { return isa<Operation *>(Val: successor); }
228
229 bool operator==(RegionSuccessor rhs) const {
230 return successor == rhs.successor;
231 }
232
233 bool operator==(const Region *region) const {
234 return getSuccessor() == region;
235 }
236
237 bool operator==(const Operation *operation) const {
238 return getSuccessorOp() == operation;
239 }
240
241 friend bool operator!=(RegionSuccessor lhs, RegionSuccessor rhs) {
242 return !(lhs == rhs);
243 }
244
245private:
246 llvm::PointerUnion<Region *, Operation *> successor;
247};
248
249/// This class represents a point being branched from in the methods of the
250/// `RegionBranchOpInterface`.
251/// One can branch from one of two kinds of places:
252/// * The parent operation (aka the `RegionBranchOpInterface` implementation)
253/// * A RegionBranchTerminatorOpInterface inside a region within the parent
254// operation.
255class RegionBranchPoint {
256public:
257 /// Returns an instance of `RegionBranchPoint` representing the parent
258 /// operation.
259 static constexpr RegionBranchPoint parent() { return RegionBranchPoint(); }
260
261 /// Creates a `RegionBranchPoint` that branches from the given terminator.
262 inline RegionBranchPoint(RegionBranchTerminatorOpInterface predecessor);
263
264 /// Explicitly stops users from constructing with `nullptr`.
265 RegionBranchPoint(std::nullptr_t) = delete;
266
267 /// Returns true if branching from the parent op.
268 bool isParent() const { return predecessor == nullptr; }
269
270 /// Returns the terminator if branching from a region.
271 /// A "null" operation otherwise.
272 inline RegionBranchTerminatorOpInterface
273 getTerminatorPredecessorOrNull() const;
274
275 /// Returns true if the two branch points are equal.
276 friend bool operator==(RegionBranchPoint lhs, RegionBranchPoint rhs) {
277 return lhs.predecessor == rhs.predecessor;
278 }
279
280private:
281 // Private constructor to encourage the use of `RegionBranchPoint::parent`.
282 constexpr RegionBranchPoint() = default;
283
284 /// Internal encoding. Uses nullptr for representing branching from the parent
285 /// op and the region terminator being branched from otherwise.
286 Operation *predecessor = nullptr;
287};
288
289/// This class represents upper and lower bounds on the number of times a region
290/// of a `RegionBranchOpInterface` can be invoked. The lower bound is at least
291/// zero, but the upper bound may not be known.
292class InvocationBounds {
293public:
294 /// Create invocation bounds. The lower bound must be at least 0 and only the
295 /// upper bound can be unknown.
296 InvocationBounds(unsigned lb, std::optional<unsigned> ub)
297 : lower(lb), upper(ub) {
298 assert((!ub || ub >= lb) && "upper bound cannot be less than lower bound");
299 }
300
301 /// Return the lower bound.
302 unsigned getLowerBound() const { return lower; }
303
304 /// Return the upper bound.
305 std::optional<unsigned> getUpperBound() const { return upper; }
306
307 /// Returns the unknown invocation bounds, i.e., there is no information on
308 /// how many times a region may be invoked.
309 static InvocationBounds getUnknown() { return {0, std::nullopt}; }
310
311private:
312 /// The minimum number of times the successor region will be invoked.
313 unsigned lower;
314 /// The maximum number of times the successor region will be invoked or
315 /// `std::nullopt` if an upper bound is not known.
316 std::optional<unsigned> upper;
317};
318
319/// Return `true` if `a` and `b` are in mutually exclusive regions as per
320/// RegionBranchOpInterface.
321bool insideMutuallyExclusiveRegions(Operation *a, Operation *b);
322
323/// Return the first enclosing region of the given op that may be executed
324/// repetitively as per RegionBranchOpInterface or `nullptr` if no such region
325/// exists.
326Region *getEnclosingRepetitiveRegion(Operation *op);
327
328/// Return the first enclosing region of the given Value that may be executed
329/// repetitively as per RegionBranchOpInterface or `nullptr` if no such region
330/// exists.
331Region *getEnclosingRepetitiveRegion(Value value);
332
333/// Populate canonicalization patterns that simplify successor operands/inputs
334/// of region branch operations. Only operations with the given name are
335/// matched.
336void populateRegionBranchOpInterfaceCanonicalizationPatterns(
337 RewritePatternSet &patterns, StringRef opName, PatternBenefit benefit = 1);
338
339/// Helper function for the region branch op inlining pattern that builds
340/// replacement values for non-successor-input values.
341using NonSuccessorInputReplacementBuilderFn =
342 std::function<Value(OpBuilder &, Location, Value)>;
343/// Helper function for the region branch op inlining pattern that checks if the
344/// pattern is applicable to the given operation.
345using PatternMatcherFn = std::function<LogicalResult(Operation *)>;
346
347namespace detail {
348/// Default implementation of the non-successor-input replacement builder
349/// function. This default implemention assumes that all block arguments and
350/// op results are successor inputs.
351static inline Value defaultReplBuilderFn(OpBuilder &builder, Location loc,
352 Value value) {
353 llvm_unreachable("defaultReplBuilderFn not implemented");
354}
355
356/// Default implementation of the pattern matcher function.
357static inline LogicalResult defaultMatcherFn(Operation *op) {
358 return success();
359}
360} // namespace detail
361
362/// Populate a pattern that inlines the body of region branch ops when there is
363/// a single acyclic path through the region branch op, starting from "parent"
364/// and ending at "parent". For details, refer to the documentation of the
365/// pattern.
366///
367/// `replBuilderFn` is a function that builds replacement values for
368/// non-successor-input values of the region branch op. `matcherFn` is a
369/// function that checks if the pattern is applicable to the given operation.
370/// Both functions are optional.
371void populateRegionBranchOpInterfaceInliningPattern(
372 RewritePatternSet &patterns, StringRef opName,
373 NonSuccessorInputReplacementBuilderFn replBuilderFn =
374 detail::defaultReplBuilderFn,
375 PatternMatcherFn matcherFn = detail::defaultMatcherFn,
376 PatternBenefit benefit = 1);
377
378//===----------------------------------------------------------------------===//
379// ControlFlow Traits
380//===----------------------------------------------------------------------===//
381
382namespace OpTrait {
383/// This trait indicates that a terminator operation is "return-like". This
384/// means that it exits its current region and forwards its operands as "exit"
385/// values to the parent region. Operations with this trait are not permitted to
386/// contain successors or produce results.
387template <typename ConcreteType>
388struct ReturnLike : public TraitBase<ConcreteType, ReturnLike> {
389 static LogicalResult verifyTrait(Operation *op) {
390 static_assert(ConcreteType::template hasTrait<IsTerminator>(),
391 "expected operation to be a terminator");
392 static_assert(ConcreteType::template hasTrait<ZeroResults>(),
393 "expected operation to have zero results");
394 static_assert(ConcreteType::template hasTrait<ZeroSuccessors>(),
395 "expected operation to have zero successors");
396 return success();
397 }
398};
399} // namespace OpTrait
400
401} // namespace mlir
402
403//===----------------------------------------------------------------------===//
404// ControlFlow Interfaces
405//===----------------------------------------------------------------------===//
406
407/// Include the generated interface declarations.
408#include "mlir/Interfaces/ControlFlowInterfaces.h.inc"
409
410namespace mlir {
411inline RegionBranchPoint::RegionBranchPoint(
412 RegionBranchTerminatorOpInterface predecessor)
413 : predecessor(predecessor.getOperation()) {}
414
415inline RegionBranchTerminatorOpInterface
416RegionBranchPoint::getTerminatorPredecessorOrNull() const {
417 if (!predecessor)
418 return nullptr;
419 return cast<RegionBranchTerminatorOpInterface>(Val: predecessor);
420}
421
422inline bool operator!=(RegionBranchPoint lhs, RegionBranchPoint rhs) {
423 return !(lhs == rhs);
424}
425
426inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os,
427 RegionBranchPoint point) {
428 if (point.isParent())
429 return os << "<from parent>";
430 return os << "<region #"
431 << point.getTerminatorPredecessorOrNull()
432 ->getParentRegion()
433 ->getRegionNumber()
434 << ", terminator "
435 << OpWithFlags(point.getTerminatorPredecessorOrNull(),
436 OpPrintingFlags().skipRegions())
437 << ">";
438}
439
440inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os,
441 RegionSuccessor successor) {
442 if (Region *region = successor.getSuccessor())
443 return os << "<to region #" << region->getRegionNumber() << ">";
444 return os << "<to operation "
445 << OpWithFlags(successor.getSuccessorOp(),
446 OpPrintingFlags().skipRegions())
447 << ">";
448}
449} // namespace mlir
450
451#endif // MLIR_INTERFACES_CONTROLFLOWINTERFACES_H
452