| 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 | |
| 24 | namespace mlir { |
| 25 | class BranchOpInterface; |
| 26 | class RegionBranchOpInterface; |
| 27 | class 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). |
| 49 | class SuccessorOperands { |
| 50 | public: |
| 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 | |
| 126 | private: |
| 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 | |
| 138 | namespace 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. |
| 142 | std::optional<BlockArgument> |
| 143 | getBranchSuccessorArgument(const SuccessorOperands &operands, |
| 144 | unsigned operandIndex, Block *successor); |
| 145 | |
| 146 | /// Verify that the given operands match those of the given successor block. |
| 147 | LogicalResult verifyBranchSuccessorOperands(Operation *op, unsigned succNo, |
| 148 | const SuccessorOperands &operands); |
| 149 | } // namespace detail |
| 150 | |
| 151 | //===----------------------------------------------------------------------===// |
| 152 | // WeightedBranchOpInterface |
| 153 | //===----------------------------------------------------------------------===// |
| 154 | |
| 155 | namespace detail { |
| 156 | /// Verify that the branch weights attached to an operation |
| 157 | /// implementing WeightedBranchOpInterface are correct. |
| 158 | LogicalResult verifyBranchWeights(Operation *op); |
| 159 | } // namespace detail |
| 160 | |
| 161 | //===----------------------------------------------------------------------===// |
| 162 | // WeightedRegiobBranchOpInterface |
| 163 | //===----------------------------------------------------------------------===// |
| 164 | |
| 165 | namespace detail { |
| 166 | /// Verify that the region weights attached to an operation |
| 167 | /// implementing WeightedRegiobBranchOpInterface are correct. |
| 168 | LogicalResult verifyRegionBranchWeights(Operation *op); |
| 169 | } // namespace detail |
| 170 | |
| 171 | //===----------------------------------------------------------------------===// |
| 172 | // RegionBranchOpInterface |
| 173 | //===----------------------------------------------------------------------===// |
| 174 | |
| 175 | namespace detail { |
| 176 | /// Verify that types match along control flow edges described the given op. |
| 177 | LogicalResult 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. |
| 191 | using RegionBranchSuccessorMapping = DenseMap<OpOperand *, SmallVector<Value>>; |
| 192 | using 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. |
| 199 | class RegionSuccessor { |
| 200 | public: |
| 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 | |
| 245 | private: |
| 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. |
| 255 | class RegionBranchPoint { |
| 256 | public: |
| 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 | |
| 280 | private: |
| 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. |
| 292 | class InvocationBounds { |
| 293 | public: |
| 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 | |
| 311 | private: |
| 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. |
| 321 | bool 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. |
| 326 | Region *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. |
| 331 | Region *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. |
| 336 | void 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. |
| 341 | using 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. |
| 345 | using PatternMatcherFn = std::function<LogicalResult(Operation *)>; |
| 346 | |
| 347 | namespace 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. |
| 351 | static 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. |
| 357 | static 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. |
| 371 | void 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 | |
| 382 | namespace 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. |
| 387 | template <typename ConcreteType> |
| 388 | struct 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 | |
| 410 | namespace mlir { |
| 411 | inline RegionBranchPoint::RegionBranchPoint( |
| 412 | RegionBranchTerminatorOpInterface predecessor) |
| 413 | : predecessor(predecessor.getOperation()) {} |
| 414 | |
| 415 | inline RegionBranchTerminatorOpInterface |
| 416 | RegionBranchPoint::getTerminatorPredecessorOrNull() const { |
| 417 | if (!predecessor) |
| 418 | return nullptr; |
| 419 | return cast<RegionBranchTerminatorOpInterface>(Val: predecessor); |
| 420 | } |
| 421 | |
| 422 | inline bool operator!=(RegionBranchPoint lhs, RegionBranchPoint rhs) { |
| 423 | return !(lhs == rhs); |
| 424 | } |
| 425 | |
| 426 | inline 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 | |
| 440 | inline 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 | |