| 1 | //===- ControlFlowInterfaces.cpp - ControlFlow Interfaces -----------------===// |
| 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 | #include <map> |
| 10 | #include <utility> |
| 11 | |
| 12 | #include "mlir/IR/BuiltinTypes.h" |
| 13 | #include "mlir/IR/Matchers.h" |
| 14 | #include "mlir/IR/Operation.h" |
| 15 | #include "mlir/IR/PatternMatch.h" |
| 16 | #include "mlir/Interfaces/ControlFlowInterfaces.h" |
| 17 | #include "llvm/ADT/EquivalenceClasses.h" |
| 18 | #include "llvm/ADT/PointerIntPair.h" |
| 19 | #include "llvm/Support/DebugLog.h" |
| 20 | |
| 21 | using namespace mlir; |
| 22 | |
| 23 | //===----------------------------------------------------------------------===// |
| 24 | // ControlFlowInterfaces |
| 25 | //===----------------------------------------------------------------------===// |
| 26 | |
| 27 | #include "mlir/Interfaces/ControlFlowInterfaces.cpp.inc" |
| 28 | |
| 29 | SuccessorOperands::SuccessorOperands(MutableOperandRange forwardedOperands) |
| 30 | : producedOperandCount(0), forwardedOperands(std::move(forwardedOperands)) { |
| 31 | } |
| 32 | |
| 33 | SuccessorOperands::SuccessorOperands(unsigned int producedOperandCount, |
| 34 | MutableOperandRange forwardedOperands) |
| 35 | : producedOperandCount(producedOperandCount), |
| 36 | forwardedOperands(std::move(forwardedOperands)) {} |
| 37 | |
| 38 | //===----------------------------------------------------------------------===// |
| 39 | // BranchOpInterface |
| 40 | //===----------------------------------------------------------------------===// |
| 41 | |
| 42 | /// Returns the `BlockArgument` corresponding to operand `operandIndex` in some |
| 43 | /// successor if 'operandIndex' is within the range of 'operands', or |
| 44 | /// std::nullopt if `operandIndex` isn't a successor operand index. |
| 45 | std::optional<BlockArgument> |
| 46 | detail::getBranchSuccessorArgument(const SuccessorOperands &operands, |
| 47 | unsigned operandIndex, Block *successor) { |
| 48 | LDBG() << "Getting branch successor argument for operand index " |
| 49 | << operandIndex << " in successor block" ; |
| 50 | |
| 51 | OperandRange forwardedOperands = operands.getForwardedOperands(); |
| 52 | // Check that the operands are valid. |
| 53 | if (forwardedOperands.empty()) { |
| 54 | LDBG() << "No forwarded operands, returning nullopt" ; |
| 55 | return std::nullopt; |
| 56 | } |
| 57 | |
| 58 | // Check to ensure that this operand is within the range. |
| 59 | unsigned operandsStart = forwardedOperands.getBeginOperandIndex(); |
| 60 | if (operandIndex < operandsStart || |
| 61 | operandIndex >= (operandsStart + forwardedOperands.size())) { |
| 62 | LDBG() << "Operand index " << operandIndex << " out of range [" |
| 63 | << operandsStart << ", " |
| 64 | << (operandsStart + forwardedOperands.size()) |
| 65 | << "), returning nullopt" ; |
| 66 | return std::nullopt; |
| 67 | } |
| 68 | |
| 69 | // Index the successor. |
| 70 | unsigned argIndex = |
| 71 | operands.getProducedOperandCount() + operandIndex - operandsStart; |
| 72 | LDBG() << "Computed argument index " << argIndex << " for successor block" ; |
| 73 | return successor->getArgument(i: argIndex); |
| 74 | } |
| 75 | |
| 76 | /// Verify that the given operands match those of the given successor block. |
| 77 | LogicalResult |
| 78 | detail::verifyBranchSuccessorOperands(Operation *op, unsigned succNo, |
| 79 | const SuccessorOperands &operands) { |
| 80 | LDBG() << "Verifying branch successor operands for successor #" << succNo |
| 81 | << " in operation " << op->getName(); |
| 82 | |
| 83 | // Check the count. |
| 84 | unsigned operandCount = operands.size(); |
| 85 | Block *destBB = op->getSuccessor(index: succNo); |
| 86 | LDBG() << "Branch has " << operandCount << " operands, target block has " |
| 87 | << destBB->getNumArguments() << " arguments" ; |
| 88 | |
| 89 | if (operandCount != destBB->getNumArguments()) |
| 90 | return op->emitError() << "branch has " << operandCount |
| 91 | << " operands for successor #" << succNo |
| 92 | << ", but target block has " |
| 93 | << destBB->getNumArguments(); |
| 94 | |
| 95 | // Check the types. |
| 96 | LDBG() << "Checking type compatibility for " |
| 97 | << (operandCount - operands.getProducedOperandCount()) |
| 98 | << " forwarded operands" ; |
| 99 | for (unsigned i = operands.getProducedOperandCount(); i != operandCount; |
| 100 | ++i) { |
| 101 | Type operandType = operands[i].getType(); |
| 102 | Type argType = destBB->getArgument(i).getType(); |
| 103 | LDBG() << "Checking type compatibility: operand type " << operandType |
| 104 | << " vs argument type " << argType; |
| 105 | |
| 106 | if (!cast<BranchOpInterface>(Val: op).areTypesCompatible(lhs: operandType, rhs: argType)) |
| 107 | return op->emitError() << "type mismatch for bb argument #" << i |
| 108 | << " of successor #" << succNo; |
| 109 | } |
| 110 | |
| 111 | LDBG() << "Branch successor operand verification successful" ; |
| 112 | return success(); |
| 113 | } |
| 114 | |
| 115 | //===----------------------------------------------------------------------===// |
| 116 | // WeightedBranchOpInterface |
| 117 | //===----------------------------------------------------------------------===// |
| 118 | |
| 119 | static LogicalResult verifyWeights(Operation *op, |
| 120 | llvm::ArrayRef<int32_t> weights, |
| 121 | std::size_t expectedWeightsNum, |
| 122 | llvm::StringRef weightAnchorName, |
| 123 | llvm::StringRef weightRefName) { |
| 124 | if (weights.empty()) |
| 125 | return success(); |
| 126 | |
| 127 | if (weights.size() != expectedWeightsNum) |
| 128 | return op->emitError() << "expects number of " << weightAnchorName |
| 129 | << " weights to match number of " << weightRefName |
| 130 | << ": " << weights.size() << " vs " |
| 131 | << expectedWeightsNum; |
| 132 | |
| 133 | if (llvm::all_of(Range&: weights, P: [](int32_t value) { return value == 0; })) |
| 134 | return op->emitError() << "branch weights cannot all be zero" ; |
| 135 | |
| 136 | return success(); |
| 137 | } |
| 138 | |
| 139 | LogicalResult detail::verifyBranchWeights(Operation *op) { |
| 140 | llvm::ArrayRef<int32_t> weights = |
| 141 | cast<WeightedBranchOpInterface>(Val: op).getWeights(); |
| 142 | return verifyWeights(op, weights, expectedWeightsNum: op->getNumSuccessors(), weightAnchorName: "branch" , |
| 143 | weightRefName: "successors" ); |
| 144 | } |
| 145 | |
| 146 | //===----------------------------------------------------------------------===// |
| 147 | // WeightedRegionBranchOpInterface |
| 148 | //===----------------------------------------------------------------------===// |
| 149 | |
| 150 | LogicalResult detail::verifyRegionBranchWeights(Operation *op) { |
| 151 | llvm::ArrayRef<int32_t> weights = |
| 152 | cast<WeightedRegionBranchOpInterface>(Val: op).getWeights(); |
| 153 | return verifyWeights(op, weights, expectedWeightsNum: op->getNumRegions(), weightAnchorName: "region" , weightRefName: "regions" ); |
| 154 | } |
| 155 | |
| 156 | //===----------------------------------------------------------------------===// |
| 157 | // RegionBranchOpInterface |
| 158 | //===----------------------------------------------------------------------===// |
| 159 | |
| 160 | /// Verify that types match along control flow edges described the given op. |
| 161 | LogicalResult detail::verifyRegionBranchOpInterface(Operation *op) { |
| 162 | auto regionInterface = cast<RegionBranchOpInterface>(Val: op); |
| 163 | |
| 164 | // Verify all control flow edges from region branch points to region |
| 165 | // successors. |
| 166 | SmallVector<RegionBranchPoint> regionBranchPoints = |
| 167 | regionInterface.getAllRegionBranchPoints(); |
| 168 | for (const RegionBranchPoint &branchPoint : regionBranchPoints) { |
| 169 | SmallVector<RegionSuccessor> successors; |
| 170 | regionInterface.getSuccessorRegions(point: branchPoint, regions&: successors); |
| 171 | for (const RegionSuccessor &successor : successors) { |
| 172 | // Helper function that print the region branch point and the region |
| 173 | // successor. |
| 174 | auto emitRegionEdgeError = [&]() { |
| 175 | InFlightDiagnostic diag = |
| 176 | regionInterface->emitOpError(message: "along control flow edge from " ); |
| 177 | if (branchPoint.isParent()) { |
| 178 | diag << "parent" ; |
| 179 | diag.attachNote(noteLoc: op->getLoc()) << "region branch point" ; |
| 180 | } else { |
| 181 | diag << "Operation " |
| 182 | << branchPoint.getTerminatorPredecessorOrNull()->getName(); |
| 183 | diag.attachNote( |
| 184 | noteLoc: branchPoint.getTerminatorPredecessorOrNull()->getLoc()) |
| 185 | << "region branch point" ; |
| 186 | } |
| 187 | diag << " to " ; |
| 188 | if (Region *region = successor.getSuccessor()) { |
| 189 | diag << "Region #" << region->getRegionNumber(); |
| 190 | } else { |
| 191 | diag << "Operation " << successor.getSuccessorOp()->getName(); |
| 192 | } |
| 193 | return diag; |
| 194 | }; |
| 195 | |
| 196 | // Verify number of successor operands and successor inputs. |
| 197 | OperandRange succOperands = |
| 198 | regionInterface.getSuccessorOperands(src: branchPoint, dest: successor); |
| 199 | ValueRange succInputs = regionInterface.getSuccessorInputs(successor); |
| 200 | if (succOperands.size() != succInputs.size()) { |
| 201 | return emitRegionEdgeError() |
| 202 | << ": region branch point has " << succOperands.size() |
| 203 | << " operands, but region successor needs " << succInputs.size() |
| 204 | << " inputs" ; |
| 205 | } |
| 206 | |
| 207 | // Verify that the types are compatible. |
| 208 | TypeRange succInputTypes = succInputs.getTypes(); |
| 209 | TypeRange succOperandTypes = succOperands.getTypes(); |
| 210 | for (const auto &typesIdx : |
| 211 | llvm::enumerate(First: llvm::zip(t&: succOperandTypes, u&: succInputTypes))) { |
| 212 | Type succOperandType = std::get<0>(t&: typesIdx.value()); |
| 213 | Type succInputType = std::get<1>(t&: typesIdx.value()); |
| 214 | if (!regionInterface.areTypesCompatible(lhs: succOperandType, rhs: succInputType)) |
| 215 | return emitRegionEdgeError() |
| 216 | << ": successor operand type #" << typesIdx.index() << " " |
| 217 | << succOperandType << " should match successor input type #" |
| 218 | << typesIdx.index() << " " << succInputType; |
| 219 | } |
| 220 | } |
| 221 | } |
| 222 | return success(); |
| 223 | } |
| 224 | |
| 225 | /// Return the regions in `successors`. Branches back to the parent op are left |
| 226 | /// out. |
| 227 | static SmallVector<Region *> |
| 228 | filterRegionSuccessors(ArrayRef<RegionSuccessor> successors) { |
| 229 | SmallVector<Region *> regions; |
| 230 | for (RegionSuccessor successor : successors) |
| 231 | if (successor.isRegion()) |
| 232 | regions.push_back(Elt: successor.getSuccessor()); |
| 233 | return regions; |
| 234 | } |
| 235 | |
| 236 | /// Return the regions that the terminators of `region` may branch to. |
| 237 | /// |
| 238 | /// This asks the parent op, not each terminator. A terminator's own |
| 239 | /// `getSuccessorRegions` can only narrow the parent's answer using constant |
| 240 | /// operands, and we know no operand values here. |
| 241 | static SmallVector<Region *> getSuccessorRegionsOf(Region *region) { |
| 242 | SmallVector<RegionSuccessor> successors; |
| 243 | cast<RegionBranchOpInterface>(Val: region->getParentOp()) |
| 244 | .getSuccessorRegions(region&: *region, regions&: successors); |
| 245 | LDBG() << "Region #" << region->getRegionNumber() << " has " |
| 246 | << successors.size() << " successors" ; |
| 247 | return filterRegionSuccessors(successors); |
| 248 | } |
| 249 | |
| 250 | /// Stop condition for `traverseRegionGraph`. The traversal is interrupted if |
| 251 | /// this function returns "true" for a successor region. |
| 252 | using StopConditionFn = function_ref<bool(Region *)>; |
| 253 | |
| 254 | /// Traverse the region graph starting at `begin`. The traversal is interrupted |
| 255 | /// if `stopCondition` evaluates to "true" for a successor region. In that case, |
| 256 | /// this function returns "true". Otherwise, if the traversal was not |
| 257 | /// interrupted, this function returns "false". |
| 258 | static bool traverseRegionGraph(Region *begin, |
| 259 | StopConditionFn stopConditionFn) { |
| 260 | auto op = cast<RegionBranchOpInterface>(Val: begin->getParentOp()); |
| 261 | LDBG() << "Starting region graph traversal from region #" |
| 262 | << begin->getRegionNumber() << " in operation " << op->getName(); |
| 263 | |
| 264 | SmallVector<bool> visited(op->getNumRegions(), false); |
| 265 | visited[begin->getRegionNumber()] = true; |
| 266 | LDBG() << "Initialized visited array with " << op->getNumRegions() |
| 267 | << " regions" ; |
| 268 | |
| 269 | SmallVector<Region *> worklist = getSuccessorRegionsOf(region: begin); |
| 270 | LDBG() << "Initial worklist size: " << worklist.size(); |
| 271 | |
| 272 | // Process all regions in the worklist via DFS. |
| 273 | while (!worklist.empty()) { |
| 274 | Region *nextRegion = worklist.pop_back_val(); |
| 275 | LDBG() << "Processing region #" << nextRegion->getRegionNumber() |
| 276 | << " from worklist (remaining: " << worklist.size() << ")" ; |
| 277 | |
| 278 | // Check the stop condition before the visited set. `begin` starts out |
| 279 | // visited, and reaching it again must still stop the traversal. |
| 280 | if (stopConditionFn(nextRegion)) { |
| 281 | LDBG() << "Stop condition met for region #" |
| 282 | << nextRegion->getRegionNumber() << ", returning true" ; |
| 283 | return true; |
| 284 | } |
| 285 | if (!nextRegion->getParentOp()) { |
| 286 | llvm::errs() << "Region " << *nextRegion << " has no parent op\n" ; |
| 287 | return false; |
| 288 | } |
| 289 | if (visited[nextRegion->getRegionNumber()]) { |
| 290 | LDBG() << "Region #" << nextRegion->getRegionNumber() |
| 291 | << " already visited, skipping" ; |
| 292 | continue; |
| 293 | } |
| 294 | visited[nextRegion->getRegionNumber()] = true; |
| 295 | LDBG() << "Marking region #" << nextRegion->getRegionNumber() |
| 296 | << " as visited" ; |
| 297 | llvm::append_range(C&: worklist, R: getSuccessorRegionsOf(region: nextRegion)); |
| 298 | } |
| 299 | |
| 300 | LDBG() << "Traversal completed, returning false" ; |
| 301 | return false; |
| 302 | } |
| 303 | |
| 304 | /// Return `true` if region `r` is reachable from region `begin` according to |
| 305 | /// the RegionBranchOpInterface (by taking a branch). |
| 306 | static bool isRegionReachable(Region *begin, Region *r) { |
| 307 | assert(begin->getParentOp() == r->getParentOp() && |
| 308 | "expected that both regions belong to the same op" ); |
| 309 | return traverseRegionGraph(begin, stopConditionFn: [&](Region *nextRegion) { |
| 310 | // Interrupt traversal if `r` was reached. |
| 311 | return nextRegion == r; |
| 312 | }); |
| 313 | } |
| 314 | |
| 315 | /// Return `true` if `a` and `b` are in mutually exclusive regions. |
| 316 | /// |
| 317 | /// 1. Find the first common of `a` and `b` (ancestor) that implements |
| 318 | /// RegionBranchOpInterface. |
| 319 | /// 2. Determine the regions `regionA` and `regionB` in which `a` and `b` are |
| 320 | /// contained. |
| 321 | /// 3. Check if `regionA` and `regionB` are mutually exclusive. They are |
| 322 | /// mutually exclusive if they are not reachable from each other as per |
| 323 | /// RegionBranchOpInterface::getSuccessorRegions. |
| 324 | bool mlir::insideMutuallyExclusiveRegions(Operation *a, Operation *b) { |
| 325 | LDBG() << "Checking if operations are in mutually exclusive regions: " |
| 326 | << a->getName() << " and " << b->getName(); |
| 327 | |
| 328 | assert(a && "expected non-empty operation" ); |
| 329 | assert(b && "expected non-empty operation" ); |
| 330 | |
| 331 | auto branchOp = a->getParentOfType<RegionBranchOpInterface>(); |
| 332 | while (branchOp) { |
| 333 | LDBG() << "Checking branch operation " << branchOp->getName(); |
| 334 | |
| 335 | // Check if b is inside branchOp. (We already know that a is.) |
| 336 | if (!branchOp->isProperAncestor(other: b)) { |
| 337 | LDBG() << "Operation b is not inside branchOp, checking next ancestor" ; |
| 338 | // Check next enclosing RegionBranchOpInterface. |
| 339 | branchOp = branchOp->getParentOfType<RegionBranchOpInterface>(); |
| 340 | continue; |
| 341 | } |
| 342 | |
| 343 | LDBG() << "Both operations are inside branchOp, finding their regions" ; |
| 344 | |
| 345 | // b is contained in branchOp. Retrieve the regions in which `a` and `b` |
| 346 | // are contained. |
| 347 | Region *regionA = nullptr, *regionB = nullptr; |
| 348 | for (Region &r : branchOp->getRegions()) { |
| 349 | if (r.findAncestorOpInRegion(op&: *a)) { |
| 350 | assert(!regionA && "already found a region for a" ); |
| 351 | regionA = &r; |
| 352 | LDBG() << "Found region #" << r.getRegionNumber() << " for operation a" ; |
| 353 | } |
| 354 | if (r.findAncestorOpInRegion(op&: *b)) { |
| 355 | assert(!regionB && "already found a region for b" ); |
| 356 | regionB = &r; |
| 357 | LDBG() << "Found region #" << r.getRegionNumber() << " for operation b" ; |
| 358 | } |
| 359 | } |
| 360 | assert(regionA && regionB && "could not find region of op" ); |
| 361 | |
| 362 | LDBG() << "Region A: #" << regionA->getRegionNumber() << ", Region B: #" |
| 363 | << regionB->getRegionNumber(); |
| 364 | |
| 365 | // `a` and `b` are in mutually exclusive regions if both regions are |
| 366 | // distinct and neither region is reachable from the other region. |
| 367 | bool regionsAreDistinct = (regionA != regionB); |
| 368 | bool aNotReachableFromB = !isRegionReachable(begin: regionA, r: regionB); |
| 369 | bool bNotReachableFromA = !isRegionReachable(begin: regionB, r: regionA); |
| 370 | |
| 371 | LDBG() << "Regions distinct: " << regionsAreDistinct |
| 372 | << ", A not reachable from B: " << aNotReachableFromB |
| 373 | << ", B not reachable from A: " << bNotReachableFromA; |
| 374 | |
| 375 | bool mutuallyExclusive = |
| 376 | regionsAreDistinct && aNotReachableFromB && bNotReachableFromA; |
| 377 | LDBG() << "Operations are mutually exclusive: " << mutuallyExclusive; |
| 378 | |
| 379 | return mutuallyExclusive; |
| 380 | } |
| 381 | |
| 382 | // Could not find a common RegionBranchOpInterface among a's and b's |
| 383 | // ancestors. |
| 384 | LDBG() << "No common RegionBranchOpInterface found, operations are not " |
| 385 | "mutually exclusive" ; |
| 386 | return false; |
| 387 | } |
| 388 | |
| 389 | bool RegionBranchOpInterface::isRepetitiveRegion(unsigned index) { |
| 390 | LDBG() << "Checking if region #" << index << " is repetitive in operation " |
| 391 | << getOperation()->getName(); |
| 392 | |
| 393 | Region *region = &getOperation()->getRegion(index); |
| 394 | bool isRepetitive = isRegionReachable(begin: region, r: region); |
| 395 | |
| 396 | LDBG() << "Region #" << index << " is repetitive: " << isRepetitive; |
| 397 | return isRepetitive; |
| 398 | } |
| 399 | |
| 400 | /// Return "true" if a cycle in the region graph is reachable from one of |
| 401 | /// `entryRegions`, which must belong to the same op. |
| 402 | /// |
| 403 | /// This is an iterative depth-first search. A region is on the DFS path from |
| 404 | /// the time the search enters it until every region reachable from it is |
| 405 | /// finished. Reaching a region on the path closes a cycle. Reaching a finished |
| 406 | /// region does not. That happens, for example, when two terminators branch to |
| 407 | /// the same successor region. |
| 408 | static bool canReachCycle(ArrayRef<Region *> entryRegions) { |
| 409 | // With no entry regions, nothing is reachable. `states` below also needs an |
| 410 | // entry region to get the op from. |
| 411 | if (entryRegions.empty()) |
| 412 | return false; |
| 413 | enum class State : uint8_t { Unvisited, OnPath, Finished }; |
| 414 | SmallVector<State> states( |
| 415 | entryRegions.front()->getParentOp()->getNumRegions(), State::Unvisited); |
| 416 | |
| 417 | // Each stack item enters its region, or leaves it if the flag is set. |
| 418 | // Entering a region pushes its leave item first and the enter items of its |
| 419 | // successors on top. The leave item pops only after all of those finish, so |
| 420 | // the region stays on the path until then. |
| 421 | using StackItem = llvm::PointerIntPair<Region *, 1, bool>; |
| 422 | SmallVector<StackItem> stack; |
| 423 | for (Region *region : entryRegions) |
| 424 | stack.push_back(Elt: StackItem(region, /*isLeave=*/false)); |
| 425 | while (!stack.empty()) { |
| 426 | StackItem item = stack.pop_back_val(); |
| 427 | Region *region = item.getPointer(); |
| 428 | bool isLeave = item.getInt(); |
| 429 | State &state = states[region->getRegionNumber()]; |
| 430 | if (isLeave) { |
| 431 | state = State::Finished; |
| 432 | continue; |
| 433 | } |
| 434 | if (state == State::OnPath) { |
| 435 | LDBG() << "Found loop through region #" << region->getRegionNumber(); |
| 436 | return true; |
| 437 | } |
| 438 | if (state == State::Finished) |
| 439 | continue; |
| 440 | |
| 441 | state = State::OnPath; |
| 442 | stack.push_back(Elt: StackItem(region, /*isLeave=*/true)); |
| 443 | for (Region *successor : getSuccessorRegionsOf(region)) |
| 444 | stack.push_back(Elt: StackItem(successor, /*isLeave=*/false)); |
| 445 | } |
| 446 | return false; |
| 447 | } |
| 448 | |
| 449 | bool RegionBranchOpInterface::hasLoop() { |
| 450 | LDBG() << "Checking if operation " << getOperation()->getName() |
| 451 | << " has loops" ; |
| 452 | |
| 453 | SmallVector<RegionSuccessor> entrySuccessors; |
| 454 | getSuccessorRegions(point: RegionBranchPoint::parent(), regions&: entrySuccessors); |
| 455 | SmallVector<Region *> entryRegions = filterRegionSuccessors(successors: entrySuccessors); |
| 456 | LDBG() << "Found " << entryRegions.size() << " entry regions" ; |
| 457 | |
| 458 | bool hasLoop = canReachCycle(entryRegions); |
| 459 | LDBG() << "Operation " << (hasLoop ? "has" : "has no" ) << " loops" ; |
| 460 | return hasLoop; |
| 461 | } |
| 462 | |
| 463 | OperandRange |
| 464 | RegionBranchOpInterface::getSuccessorOperands(RegionBranchPoint src, |
| 465 | RegionSuccessor dest) { |
| 466 | if (src.isParent()) |
| 467 | return getEntrySuccessorOperands(successor: dest); |
| 468 | return src.getTerminatorPredecessorOrNull().getSuccessorOperands(successor: dest); |
| 469 | } |
| 470 | |
| 471 | SmallVector<Value> |
| 472 | RegionBranchOpInterface::getNonSuccessorInputs(RegionSuccessor successor) { |
| 473 | SmallVector<Value> results = llvm::to_vector( |
| 474 | Range: successor.isOperation() |
| 475 | ? ValueRange(successor.getSuccessorOp()->getResults()) |
| 476 | : ValueRange(successor.getSuccessor()->getArguments())); |
| 477 | ValueRange successorInputs = getSuccessorInputs(successor); |
| 478 | if (!successorInputs.empty()) { |
| 479 | unsigned inputBegin = |
| 480 | successor.isOperation() |
| 481 | ? cast<OpResult>(Val: successorInputs.front()).getResultNumber() |
| 482 | : cast<BlockArgument>(Val: successorInputs.front()).getArgNumber(); |
| 483 | results.erase(CS: results.begin() + inputBegin, |
| 484 | CE: results.begin() + inputBegin + successorInputs.size()); |
| 485 | } |
| 486 | return results; |
| 487 | } |
| 488 | |
| 489 | static MutableArrayRef<OpOperand> operandsToOpOperands(OperandRange &operands) { |
| 490 | return MutableArrayRef<OpOperand>(operands.getBase(), operands.size()); |
| 491 | } |
| 492 | |
| 493 | static void |
| 494 | getSuccessorOperandInputMapping(RegionBranchOpInterface branchOp, |
| 495 | RegionBranchSuccessorMapping &mapping, |
| 496 | RegionBranchPoint src) { |
| 497 | SmallVector<RegionSuccessor> successors; |
| 498 | branchOp.getSuccessorRegions(point: src, regions&: successors); |
| 499 | for (RegionSuccessor dst : successors) { |
| 500 | OperandRange operands = branchOp.getSuccessorOperands(src, dest: dst); |
| 501 | assert(operands.size() == branchOp.getSuccessorInputs(dst).size() && |
| 502 | "expected the same number of operands and inputs" ); |
| 503 | for (const auto &[operand, input] : llvm::zip_equal( |
| 504 | t: operandsToOpOperands(operands), u: branchOp.getSuccessorInputs(successor: dst))) |
| 505 | mapping[&operand].push_back(Elt: input); |
| 506 | } |
| 507 | } |
| 508 | void RegionBranchOpInterface::getSuccessorOperandInputMapping( |
| 509 | RegionBranchSuccessorMapping &mapping, |
| 510 | std::optional<RegionBranchPoint> src) { |
| 511 | if (src.has_value()) { |
| 512 | ::getSuccessorOperandInputMapping(branchOp: *this, mapping, src: src.value()); |
| 513 | } else { |
| 514 | // No region branch point specified: populate the mapping for all possible |
| 515 | // region branch points. |
| 516 | for (RegionBranchPoint branchPoint : getAllRegionBranchPoints()) |
| 517 | ::getSuccessorOperandInputMapping(branchOp: *this, mapping, src: branchPoint); |
| 518 | } |
| 519 | } |
| 520 | |
| 521 | static RegionBranchInverseSuccessorMapping invertRegionBranchSuccessorMapping( |
| 522 | const RegionBranchSuccessorMapping &operandToInputs) { |
| 523 | RegionBranchInverseSuccessorMapping inputToOperands; |
| 524 | for (const auto &[operand, inputs] : operandToInputs) { |
| 525 | for (Value input : inputs) |
| 526 | inputToOperands[input].push_back(Elt: operand); |
| 527 | } |
| 528 | return inputToOperands; |
| 529 | } |
| 530 | |
| 531 | void RegionBranchOpInterface::getSuccessorInputOperandMapping( |
| 532 | RegionBranchInverseSuccessorMapping &mapping) { |
| 533 | RegionBranchSuccessorMapping operandToInputs; |
| 534 | getSuccessorOperandInputMapping(mapping&: operandToInputs); |
| 535 | mapping = invertRegionBranchSuccessorMapping(operandToInputs); |
| 536 | } |
| 537 | |
| 538 | SmallVector<RegionBranchPoint> |
| 539 | RegionBranchOpInterface::getAllRegionBranchPoints() { |
| 540 | SmallVector<RegionBranchPoint> branchPoints; |
| 541 | branchPoints.push_back(Elt: RegionBranchPoint::parent()); |
| 542 | for (Region ®ion : getOperation()->getRegions()) { |
| 543 | for (Block &block : region) { |
| 544 | if (block.empty()) |
| 545 | continue; |
| 546 | if (auto terminator = |
| 547 | dyn_cast<RegionBranchTerminatorOpInterface>(Val&: block.back())) |
| 548 | branchPoints.push_back(Elt: RegionBranchPoint(terminator)); |
| 549 | } |
| 550 | } |
| 551 | return branchPoints; |
| 552 | } |
| 553 | |
| 554 | Region *mlir::getEnclosingRepetitiveRegion(Operation *op) { |
| 555 | LDBG() << "Finding enclosing repetitive region for operation " |
| 556 | << op->getName(); |
| 557 | |
| 558 | while (Region *region = op->getParentRegion()) { |
| 559 | LDBG() << "Checking region #" << region->getRegionNumber() |
| 560 | << " in operation " << region->getParentOp()->getName(); |
| 561 | |
| 562 | op = region->getParentOp(); |
| 563 | if (auto branchOp = dyn_cast<RegionBranchOpInterface>(Val: op)) { |
| 564 | LDBG() |
| 565 | << "Found RegionBranchOpInterface, checking if region is repetitive" ; |
| 566 | if (branchOp.isRepetitiveRegion(index: region->getRegionNumber())) { |
| 567 | LDBG() << "Found repetitive region #" << region->getRegionNumber(); |
| 568 | return region; |
| 569 | } |
| 570 | } else { |
| 571 | LDBG() << "Parent operation does not implement RegionBranchOpInterface" ; |
| 572 | } |
| 573 | } |
| 574 | |
| 575 | LDBG() << "No enclosing repetitive region found" ; |
| 576 | return nullptr; |
| 577 | } |
| 578 | |
| 579 | Region *mlir::getEnclosingRepetitiveRegion(Value value) { |
| 580 | LDBG() << "Finding enclosing repetitive region for value" ; |
| 581 | |
| 582 | Region *region = value.getParentRegion(); |
| 583 | while (region) { |
| 584 | LDBG() << "Checking region #" << region->getRegionNumber() |
| 585 | << " in operation " << region->getParentOp()->getName(); |
| 586 | |
| 587 | Operation *op = region->getParentOp(); |
| 588 | if (auto branchOp = dyn_cast<RegionBranchOpInterface>(Val: op)) { |
| 589 | LDBG() |
| 590 | << "Found RegionBranchOpInterface, checking if region is repetitive" ; |
| 591 | if (branchOp.isRepetitiveRegion(index: region->getRegionNumber())) { |
| 592 | LDBG() << "Found repetitive region #" << region->getRegionNumber(); |
| 593 | return region; |
| 594 | } |
| 595 | } else { |
| 596 | LDBG() << "Parent operation does not implement RegionBranchOpInterface" ; |
| 597 | } |
| 598 | region = op->getParentRegion(); |
| 599 | } |
| 600 | |
| 601 | LDBG() << "No enclosing repetitive region found for value" ; |
| 602 | return nullptr; |
| 603 | } |
| 604 | |
| 605 | /// Return "true" if `a` can be used in lieu of `b`, where `b` is a region |
| 606 | /// successor input and `a` is a "reachable value" of `b`. Reachable values |
| 607 | /// are successor operand values that are (maybe transitively) forwarded to |
| 608 | /// `b`. |
| 609 | static bool isDefinedBefore(Operation *regionBranchOp, Value a, Value b) { |
| 610 | assert((b.getDefiningOp() == regionBranchOp || |
| 611 | b.getParentRegion()->getParentOp() == regionBranchOp) && |
| 612 | "b must be a region successor input" ); |
| 613 | |
| 614 | // Case 1: `a` is defined inside of the region branch op. `a` must be |
| 615 | // directly nested in the region branch op. Otherwise, it could not have |
| 616 | // been among the reachable values for a region successor input. |
| 617 | if (a.getParentRegion()->getParentOp() == regionBranchOp) { |
| 618 | // Case 1.1: If `b` is a result of the region branch op, `a` is not in |
| 619 | // scope for `b`. |
| 620 | // Example: |
| 621 | // %b = region_op({ |
| 622 | // ^bb0(%a1: ...): |
| 623 | // %a2 = ... |
| 624 | // }) |
| 625 | if (isa<OpResult>(Val: b)) |
| 626 | return false; |
| 627 | |
| 628 | // Case 1.2: `b` is an entry block argument of a region. `a` is in scope |
| 629 | // for `b` only if it is also an entry block argument of the same region. |
| 630 | // Example: |
| 631 | // region_op({ |
| 632 | // ^bb0(%b: ..., %a: ...): |
| 633 | // ... |
| 634 | // }) |
| 635 | assert(isa<BlockArgument>(b) && "b must be a block argument" ); |
| 636 | return isa<BlockArgument>(Val: a) && cast<BlockArgument>(Val&: a).getOwner() == |
| 637 | cast<BlockArgument>(Val&: b).getOwner(); |
| 638 | } |
| 639 | |
| 640 | // Case 2: `a` is defined outside of the region branch op. In that case, we |
| 641 | // can safely assume that `a` was defined before `b`. Otherwise, it could not |
| 642 | // be among the reachable values for a region successor input. |
| 643 | // Example: |
| 644 | // { <- %a1 parent region begins here. |
| 645 | // ^bb0(%a1: ...): |
| 646 | // %a2 = ... |
| 647 | // %b1 = reigon_op({ |
| 648 | // ^bb1(%b2: ...): |
| 649 | // ... |
| 650 | // }) |
| 651 | // } |
| 652 | return true; |
| 653 | } |
| 654 | |
| 655 | /// Compute all non-successor-input values that a successor input could have |
| 656 | /// based on the given successor input to successor operand mapping. |
| 657 | /// |
| 658 | /// Starting with the given value, trace back all predecessor values (i.e., |
| 659 | /// preceding successor operands) and add them to the set of reachable values. |
| 660 | /// If the successor operand is again a successor input, do not add it to the |
| 661 | /// result set, but instead continue the traversal. |
| 662 | /// |
| 663 | /// If `maxReachableValues` is set, the traversal is aborted early and |
| 664 | /// `failure` is returned as soon as the number of reachable values exceeds |
| 665 | /// the limit. Otherwise, `success` is returned and the result set contains |
| 666 | /// all reachable values. |
| 667 | /// |
| 668 | /// Example 1: |
| 669 | /// %r = scf.if ... { |
| 670 | /// scf.yield %a : ... |
| 671 | /// } else { |
| 672 | /// scf.yield %b : ... |
| 673 | /// } |
| 674 | /// reachableValues(%r) = {%a, %b} |
| 675 | /// |
| 676 | /// Example 2: |
| 677 | /// %r = scf.for ... iter_args(%arg0 = %0) -> ... { |
| 678 | /// scf.yield %arg0 : ... |
| 679 | /// } |
| 680 | /// reachableValues(%arg0) = {%0} |
| 681 | /// reachableValues(%r) = {%0} |
| 682 | /// |
| 683 | /// Example 3: |
| 684 | /// %r = scf.for ... iter_args(%arg0 = %0) -> ... { |
| 685 | /// ... |
| 686 | /// scf.yield %1 : ... |
| 687 | /// } |
| 688 | /// reachableValues(%arg0) = {%0, %1} |
| 689 | /// reachableValues(%r) = {%0, %1} |
| 690 | static LogicalResult computeReachableValuesFromSuccessorInput( |
| 691 | llvm::SmallDenseSet<Value> &result, Value value, |
| 692 | const RegionBranchInverseSuccessorMapping &inputToOperands, |
| 693 | std::optional<unsigned> maxReachableValues = std::nullopt) { |
| 694 | assert(inputToOperands.contains(value) && "value must be a successor input" ); |
| 695 | llvm::SmallDenseSet<Value> visited; |
| 696 | SmallVector<Value> worklist; |
| 697 | worklist.push_back(Elt: value); |
| 698 | while (!worklist.empty()) { |
| 699 | Value next = worklist.pop_back_val(); |
| 700 | auto it = inputToOperands.find(Val: next); |
| 701 | if (it == inputToOperands.end()) { |
| 702 | result.insert(V: next); |
| 703 | if (maxReachableValues && result.size() > *maxReachableValues) |
| 704 | return failure(); |
| 705 | continue; |
| 706 | } |
| 707 | for (OpOperand *operand : it->second) |
| 708 | if (visited.insert(V: operand->get()).second) |
| 709 | worklist.push_back(Elt: operand->get()); |
| 710 | } |
| 711 | // Note: The result does not contain any successor inputs. (Therefore, |
| 712 | // `value` is also guaranteed to be excluded.) |
| 713 | return success(); |
| 714 | } |
| 715 | |
| 716 | namespace { |
| 717 | /// Try to make successor inputs dead by replacing their uses with values that |
| 718 | /// are not successor inputs. This pattern enables additional canonicalization |
| 719 | /// opportunities for RemoveDeadRegionBranchOpSuccessorInputs. |
| 720 | /// |
| 721 | /// Example: |
| 722 | /// |
| 723 | /// %r0, %r1 = scf.for ... iter_args(%arg0 = %0, %arg1 = %1) -> ... { |
| 724 | /// scf.yield %arg1, %arg1 : ... |
| 725 | /// } |
| 726 | /// use(%r0, %r1) |
| 727 | /// |
| 728 | /// reachableValues(%r0) = {%0, %1} |
| 729 | /// reachableValues(%r1) = {%1} ==> replace uses of %r1 with %1. |
| 730 | /// reachableValues(%arg0) = {%0, %1} |
| 731 | /// reachableValues(%arg1) = {%1} ==> replace uses of %arg1 with %1. |
| 732 | /// |
| 733 | /// IR after pattern application: |
| 734 | /// |
| 735 | /// %r0, %r1 = scf.for ... iter_args(%arg0 = %0, %arg1 = %1) -> ... { |
| 736 | /// scf.yield %1, %1 : ... |
| 737 | /// } |
| 738 | /// use(%r0, %1) |
| 739 | /// |
| 740 | /// Note that %r1 and %arg1 are dead now. The IR can now be further |
| 741 | /// canonicalized by RemoveDeadRegionBranchOpSuccessorInputs. |
| 742 | struct MakeRegionBranchOpSuccessorInputsDead : public RewritePattern { |
| 743 | MakeRegionBranchOpSuccessorInputsDead(MLIRContext *context, StringRef name, |
| 744 | PatternBenefit benefit = 1) |
| 745 | : RewritePattern(name, benefit, context) {} |
| 746 | |
| 747 | LogicalResult matchAndRewrite(Operation *op, |
| 748 | PatternRewriter &rewriter) const override { |
| 749 | // Compute the mapping of successor inputs to successor operands. |
| 750 | auto regionBranchOp = cast<RegionBranchOpInterface>(Val: op); |
| 751 | RegionBranchInverseSuccessorMapping inputToOperands; |
| 752 | regionBranchOp.getSuccessorInputOperandMapping(mapping&: inputToOperands); |
| 753 | |
| 754 | // Try to replace the uses of each successor input one-by-one. |
| 755 | bool changed = false; |
| 756 | const bool isIsolated = op->hasTrait<OpTrait::IsIsolatedFromAbove>(); |
| 757 | for (Value value : inputToOperands.keys()) { |
| 758 | // Nothing to do for successor inputs that are already dead. |
| 759 | if (value.use_empty()) |
| 760 | continue; |
| 761 | // Nothing to do for successor inputs that may have multiple reachable |
| 762 | // values. |
| 763 | llvm::SmallDenseSet<Value> reachableValues; |
| 764 | if (failed(Result: computeReachableValuesFromSuccessorInput( |
| 765 | result&: reachableValues, value, inputToOperands, |
| 766 | /*maxReachableValues=*/1)) || |
| 767 | reachableValues.empty()) |
| 768 | continue; |
| 769 | Value replacement = *reachableValues.begin(); |
| 770 | assert(replacement != value && |
| 771 | "successor inputs are supposed to be excluded" ); |
| 772 | // A value inside an isolated region cannot be replaced with a value from |
| 773 | // another region, even if the replacement dominates its uses. Op results |
| 774 | // are in the parent region and do not cross this isolation boundary. |
| 775 | // Successor inputs are direct region arguments or results of this op. |
| 776 | // Valid input IR already prevents captures across nested isolation |
| 777 | // boundaries, so only this op's boundary needs an additional check. |
| 778 | // Example (isolated_op has IsolatedFromAbove): |
| 779 | // %r = isolated_op %x { |
| 780 | // ^bb0(%arg: ...): |
| 781 | // use(%arg) |
| 782 | // yield %arg |
| 783 | // } |
| 784 | // use(%r) |
| 785 | // Replacing %arg with %x would introduce a capture inside isolated_op. |
| 786 | // Replacing %r with %x changes only the outer use and is allowed. |
| 787 | Region *valueRegion = value.getParentRegion(); |
| 788 | if (isIsolated && valueRegion->getParentOp() == op && |
| 789 | replacement.getParentRegion() != valueRegion) |
| 790 | continue; |
| 791 | // Do not replace `value` with the found reachable value if doing so |
| 792 | // would violate dominance. Example: |
| 793 | // %r = scf.execute_region ... { |
| 794 | // %a = ... |
| 795 | // scf.yield %a : ... |
| 796 | // } |
| 797 | // use(%r) |
| 798 | // In the above example, reachableValues(%r) = {%a}, but %a cannot be |
| 799 | // used as a replacement for %r due to dominance / scope. |
| 800 | if (!isDefinedBefore(regionBranchOp, a: replacement, b: value)) |
| 801 | continue; |
| 802 | // Successor operands and successor inputs may have different (but |
| 803 | // compatible, per `areTypesCompatible`) types, so the reachable value |
| 804 | // cannot be substituted directly. Example: |
| 805 | // |
| 806 | // %r = some_op %x : wrapper<i32> { |
| 807 | // ^bb0(%arg0: i32): |
| 808 | // %0 = arith.addi %arg0, %arg0 : i32 |
| 809 | // yield %0 : i32 |
| 810 | // } -> wrapper<i32> |
| 811 | // |
| 812 | // In the above example, reachableValues(%arg0) = {%x}, but %x cannot be |
| 813 | // used as a replacement for %arg0 due to differing types. |
| 814 | if (replacement.getType() != value.getType()) |
| 815 | continue; |
| 816 | rewriter.replaceAllUsesWith(from: value, to: replacement); |
| 817 | changed = true; |
| 818 | } |
| 819 | return success(IsSuccess: changed); |
| 820 | } |
| 821 | }; |
| 822 | |
| 823 | /// Lookup a bit vector in the given mapping (DenseMap). If the key was not |
| 824 | /// found, create a new bit vector with the given size and initialize it with |
| 825 | /// false. |
| 826 | template <typename MappingTy, typename KeyTy> |
| 827 | static BitVector &lookupOrCreateBitVector(MappingTy &mapping, KeyTy key, |
| 828 | unsigned size) { |
| 829 | return mapping.try_emplace(key, size, false).first->second; |
| 830 | } |
| 831 | |
| 832 | /// Compute tied successor inputs. Tied successor inputs are successor inputs |
| 833 | /// that come as a set. If you erase one value from a set, you must erase all |
| 834 | /// values from the set. Otherwise, the op would become structurally invalid. |
| 835 | /// Each successor input appears in exactly one set. |
| 836 | /// |
| 837 | /// Example: |
| 838 | /// %r0, %r1 = scf.for ... iter_args(%arg0 = %0, %arg1 = %1) -> ... { |
| 839 | /// ... |
| 840 | /// } |
| 841 | /// There are two sets: {{%r0, %arg0}, {%r1, %arg1}}. |
| 842 | static llvm::EquivalenceClasses<Value> computeTiedSuccessorInputs( |
| 843 | const RegionBranchSuccessorMapping &operandToInputs) { |
| 844 | llvm::EquivalenceClasses<Value> tiedSuccessorInputs; |
| 845 | for (const auto &[operand, inputs] : operandToInputs) { |
| 846 | assert(!inputs.empty() && "expected non-empty inputs" ); |
| 847 | Value firstInput = inputs.front(); |
| 848 | tiedSuccessorInputs.insert(Data: firstInput); |
| 849 | for (Value nextInput : llvm::drop_begin(RangeOrContainer: inputs)) { |
| 850 | // As we explore more successor operand to successor input mappings, |
| 851 | // existing sets may get merged. |
| 852 | tiedSuccessorInputs.unionSets(V1: firstInput, V2: nextInput); |
| 853 | } |
| 854 | } |
| 855 | return tiedSuccessorInputs; |
| 856 | } |
| 857 | |
| 858 | /// Remove dead successor inputs from region branch ops. A successor input is |
| 859 | /// dead if it has no uses. Successor inputs come in sets of tied values: if |
| 860 | /// you remove one value from a set, you must remove all values from the set. |
| 861 | /// Furthermore, successor operands must also be removed. (Op operands are not |
| 862 | /// part of the set, but the set is built based on the successor operand to |
| 863 | /// successor input mapping.) |
| 864 | /// |
| 865 | /// Example 1: |
| 866 | /// %r0, %r1 = scf.for ... iter_args(%arg0 = %0, %arg1 = %1) -> ... { |
| 867 | /// scf.yield %0, %arg1 : ... |
| 868 | /// } |
| 869 | /// use(%0, %1) |
| 870 | /// |
| 871 | /// There are two sets: {{%r0, %arg0}, {%r1, %arg1}}. All values in the first |
| 872 | /// set are dead, so %arg0 and %r0 can be removed, but not %r1 and %arg1. The |
| 873 | /// resulting IR is as follows: |
| 874 | /// |
| 875 | /// %r1 = scf.for ... iter_args(%arg1 = %1) -> ... { |
| 876 | /// scf.yield %arg1 : ... |
| 877 | /// } |
| 878 | /// use(%0, %1) |
| 879 | /// |
| 880 | /// Example 2: |
| 881 | /// %r0, %r1 = scf.while (%arg0 = %0) { |
| 882 | /// scf.condition(...) %arg0, %arg0 : ... |
| 883 | /// } do { |
| 884 | /// ^bb0(%arg1: ..., %arg2: ...): |
| 885 | /// scf.yield %arg1 : ... |
| 886 | /// } |
| 887 | /// There are three sets: {{%r0, %arg1}, {%r1, %arg2}, {%r0}}. |
| 888 | /// |
| 889 | /// Example 3: |
| 890 | /// %r1, %r2 = scf.if ... { |
| 891 | /// scf.yield %0, %1 : ... |
| 892 | /// } else { |
| 893 | /// scf.yield %2, %3 : ... |
| 894 | /// } |
| 895 | /// There are two sets: {{%r1}, {%r2}}. Each set has one value, so there each |
| 896 | /// value can be removed independently of the other values. |
| 897 | struct RemoveDeadRegionBranchOpSuccessorInputs : public RewritePattern { |
| 898 | RemoveDeadRegionBranchOpSuccessorInputs(MLIRContext *context, StringRef name, |
| 899 | PatternBenefit benefit = 1) |
| 900 | : RewritePattern(name, benefit, context) {} |
| 901 | |
| 902 | LogicalResult matchAndRewrite(Operation *op, |
| 903 | PatternRewriter &rewriter) const override { |
| 904 | // Compute tied values: values that must come as a set. If you remove one, |
| 905 | // you must remove all. If a successor op operand is forwarded to two |
| 906 | // successor inputs %a and %b, both %a and %b are in the same set. |
| 907 | auto regionBranchOp = cast<RegionBranchOpInterface>(Val: op); |
| 908 | RegionBranchSuccessorMapping operandToInputs; |
| 909 | regionBranchOp.getSuccessorOperandInputMapping(mapping&: operandToInputs); |
| 910 | llvm::EquivalenceClasses<Value> tiedSuccessorInputs = |
| 911 | computeTiedSuccessorInputs(operandToInputs); |
| 912 | |
| 913 | // Determine which values to remove and group them by block and operation. |
| 914 | SmallVector<Value> valuesToRemove; |
| 915 | DenseMap<Block *, BitVector> blockArgsToRemove; |
| 916 | BitVector resultsToRemove(regionBranchOp->getNumResults(), false); |
| 917 | // Iterate over all sets of tied successor inputs. |
| 918 | for (auto it = tiedSuccessorInputs.begin(), e = tiedSuccessorInputs.end(); |
| 919 | it != e; ++it) { |
| 920 | if (!(*it)->isLeader()) |
| 921 | continue; |
| 922 | |
| 923 | // Value can be removed if it is dead and all other tied values are also |
| 924 | // dead. |
| 925 | bool allDead = true; |
| 926 | for (auto memberIt = tiedSuccessorInputs.member_begin(ECV: **it); |
| 927 | memberIt != tiedSuccessorInputs.member_end(); ++memberIt) { |
| 928 | // Iterate over all values in the set and check their liveness. |
| 929 | if (!memberIt->use_empty()) { |
| 930 | allDead = false; |
| 931 | break; |
| 932 | } |
| 933 | } |
| 934 | if (!allDead) |
| 935 | continue; |
| 936 | |
| 937 | // The entire set is dead. Group values by block and operation to |
| 938 | // simplify removal. |
| 939 | for (auto memberIt = tiedSuccessorInputs.member_begin(ECV: **it); |
| 940 | memberIt != tiedSuccessorInputs.member_end(); ++memberIt) { |
| 941 | if (auto arg = dyn_cast<BlockArgument>(Val: *memberIt)) { |
| 942 | // Set blockArgsToRemove[block][arg_number] = true. |
| 943 | BitVector &vector = |
| 944 | lookupOrCreateBitVector(mapping&: blockArgsToRemove, key: arg.getOwner(), |
| 945 | size: arg.getOwner()->getNumArguments()); |
| 946 | vector.set(arg.getArgNumber()); |
| 947 | } else { |
| 948 | // Set resultsToRemove[result_number] = true. |
| 949 | OpResult result = cast<OpResult>(Val: *memberIt); |
| 950 | assert(result.getDefiningOp() == regionBranchOp && |
| 951 | "result must be a region branch op result" ); |
| 952 | resultsToRemove.set(result.getResultNumber()); |
| 953 | } |
| 954 | valuesToRemove.push_back(Elt: *memberIt); |
| 955 | } |
| 956 | } |
| 957 | |
| 958 | if (valuesToRemove.empty()) |
| 959 | return rewriter.notifyMatchFailure(arg&: op, msg: "no values to remove" ); |
| 960 | |
| 961 | // Find operands that must be removed together with the values. |
| 962 | RegionBranchInverseSuccessorMapping inputsToOperands = |
| 963 | invertRegionBranchSuccessorMapping(operandToInputs); |
| 964 | DenseMap<Operation *, llvm::BitVector> operandsToRemove; |
| 965 | for (Value value : valuesToRemove) { |
| 966 | for (OpOperand *operand : inputsToOperands[value]) { |
| 967 | // Set operandsToRemove[op][operand_number] = true. |
| 968 | BitVector &vector = |
| 969 | lookupOrCreateBitVector(mapping&: operandsToRemove, key: operand->getOwner(), |
| 970 | size: operand->getOwner()->getNumOperands()); |
| 971 | vector.set(operand->getOperandNumber()); |
| 972 | } |
| 973 | } |
| 974 | |
| 975 | // Erase operands. |
| 976 | for (auto &pair : operandsToRemove) { |
| 977 | Operation *op = pair.first; |
| 978 | BitVector &operands = pair.second; |
| 979 | rewriter.eraseOperands(op, eraseIndices: operands); |
| 980 | } |
| 981 | |
| 982 | // Erase block arguments. |
| 983 | for (auto &pair : blockArgsToRemove) { |
| 984 | Block *block = pair.first; |
| 985 | BitVector &blockArg = pair.second; |
| 986 | rewriter.modifyOpInPlace(root: block->getParentOp(), |
| 987 | callable: [&]() { block->eraseArguments(eraseIndices: blockArg); }); |
| 988 | } |
| 989 | |
| 990 | // Erase op results. |
| 991 | if (resultsToRemove.any()) |
| 992 | rewriter.eraseOpResults(op: regionBranchOp, eraseIndices: resultsToRemove); |
| 993 | |
| 994 | return success(); |
| 995 | } |
| 996 | }; |
| 997 | |
| 998 | /// Return the "owner" of a value: the parent block for block arguments, the |
| 999 | /// defining op for op results. |
| 1000 | static void *getOwnerOfValue(Value value) { |
| 1001 | if (auto arg = dyn_cast<BlockArgument>(Val&: value)) |
| 1002 | return arg.getOwner(); |
| 1003 | return value.getDefiningOp(); |
| 1004 | } |
| 1005 | |
| 1006 | /// Get the block argument or op result number of the given value. |
| 1007 | static unsigned getArgOrResultNumber(Value value) { |
| 1008 | if (auto opResult = llvm::dyn_cast<OpResult>(Val&: value)) |
| 1009 | return opResult.getResultNumber(); |
| 1010 | return llvm::cast<BlockArgument>(Val&: value).getArgNumber(); |
| 1011 | } |
| 1012 | |
| 1013 | /// Find duplicate successor inputs and make all dead except for one. Two |
| 1014 | /// successor inputs are "duplicate" if their corresponding successor operands |
| 1015 | /// have the same values. This pattern enables additional canonicalization |
| 1016 | /// opportunities for RemoveDeadRegionBranchOpSuccessorInputs. |
| 1017 | /// |
| 1018 | /// Example: |
| 1019 | /// %r0, %r1 = scf.for ... iter_args(%arg0 = %0, %arg1 = %0) -> ... { |
| 1020 | /// use(%arg0, %arg1) |
| 1021 | /// ... |
| 1022 | /// scf.yield %x, %x : ... |
| 1023 | /// } |
| 1024 | /// use(%r0, %r1) |
| 1025 | /// |
| 1026 | /// Operands of successor input %r0: [%0, %x] |
| 1027 | /// Operands of successor input %r1: [%0, %x] ==> DUPLICATE! |
| 1028 | /// Replace %r1 with %r0. |
| 1029 | /// |
| 1030 | /// Operands of successor input %arg0: [%0, %x] |
| 1031 | /// Operands of successor input %arg1: [%0, %x] ==> DUPLICATE! |
| 1032 | /// Replace %arg1 with %arg0. (We have to make sure that we make same decision |
| 1033 | /// as for the other tied successor inputs above. Otherwise, a set of tied |
| 1034 | /// successor inputs may not become entirely dead.) |
| 1035 | /// |
| 1036 | /// The resulting IR is as follows: |
| 1037 | /// %r0, %r1 = scf.for ... iter_args(%arg0 = %0, %arg1 = %0) -> ... { |
| 1038 | /// use(%arg0, %arg0) |
| 1039 | /// ... |
| 1040 | /// scf.yield %x, %x : ... |
| 1041 | /// } |
| 1042 | /// use(%r0, %r0) // Note: We don't want use(%r1, %r1), which is also correct, |
| 1043 | /// // but does not help with further canonicalizations. |
| 1044 | struct RemoveDuplicateSuccessorInputUses : public RewritePattern { |
| 1045 | RemoveDuplicateSuccessorInputUses(MLIRContext *context, StringRef name, |
| 1046 | PatternBenefit benefit = 1) |
| 1047 | : RewritePattern(name, benefit, context) {} |
| 1048 | |
| 1049 | LogicalResult matchAndRewrite(Operation *op, |
| 1050 | PatternRewriter &rewriter) const override { |
| 1051 | // Collect all successor inputs and sort them. When dropping the uses of a |
| 1052 | // successor input, we'd like to also drop the uses of the same tied |
| 1053 | // successor inputs. Otherwise, a set of tied successor inputs may not |
| 1054 | // become entirely dead, which is required for |
| 1055 | // RemoveDeadRegionBranchOpSuccessorInputs to be able to erase them. |
| 1056 | // (Sorting is not required for correctness.) |
| 1057 | auto regionBranchOp = cast<RegionBranchOpInterface>(Val: op); |
| 1058 | RegionBranchInverseSuccessorMapping inputsToOperands; |
| 1059 | regionBranchOp.getSuccessorInputOperandMapping(mapping&: inputsToOperands); |
| 1060 | SmallVector<Value> inputs = llvm::to_vector(Range: inputsToOperands.keys()); |
| 1061 | llvm::sort(C&: inputs, Comp: [](Value a, Value b) { |
| 1062 | return getArgOrResultNumber(value: a) < getArgOrResultNumber(value: b); |
| 1063 | }); |
| 1064 | |
| 1065 | // Group inputs by their operand "signature" to find duplicates. Two |
| 1066 | // successor inputs are duplicates if each predecessor (region branch point) |
| 1067 | // forwards the same value for both. Let n = number of successor inputs and |
| 1068 | // k = number of predecessors per input. Instead of comparing every pair of |
| 1069 | // inputs (O(n² * k)), we build a signature for each input and group them |
| 1070 | // via a std::map. |
| 1071 | // |
| 1072 | // A signature is a sorted list of (predecessor, forwarded value) pairs. |
| 1073 | // Within each group, all but the first (canonical) input are replaced with |
| 1074 | // the canonical one. |
| 1075 | using SigEntry = std::pair<Operation *, Value>; |
| 1076 | using Signature = SmallVector<SigEntry>; |
| 1077 | auto sigEntryLess = [](const SigEntry &a, const SigEntry &b) { |
| 1078 | if (a.first != b.first) |
| 1079 | return a.first < b.first; |
| 1080 | return a.second.getAsOpaquePointer() < b.second.getAsOpaquePointer(); |
| 1081 | }; |
| 1082 | // The map key is (signature, owner, type). Two inputs are duplicates only |
| 1083 | // if they have the same signature, the same owner (block or defining op), |
| 1084 | // and the same type. Incorporating the type ensures that differently-typed |
| 1085 | // successor inputs (which may arise when `areTypesCompatible` is |
| 1086 | // overridden) are partitioned into separate equivalence classes, so a |
| 1087 | // duplicate can still find a same-typed canonical. |
| 1088 | using MapKey = std::tuple<Signature, void *, Type>; |
| 1089 | auto mapKeyLess = [&](const MapKey &a, const MapKey &b) { |
| 1090 | if (std::get<1>(t: a) != std::get<1>(t: b)) |
| 1091 | return std::get<1>(t: a) < std::get<1>(t: b); |
| 1092 | if (std::get<2>(t: a) != std::get<2>(t: b)) |
| 1093 | return std::get<2>(t: a).getAsOpaquePointer() < |
| 1094 | std::get<2>(t: b).getAsOpaquePointer(); |
| 1095 | return std::lexicographical_compare( |
| 1096 | first1: std::get<0>(t: a).begin(), last1: std::get<0>(t: a).end(), first2: std::get<0>(t: b).begin(), |
| 1097 | last2: std::get<0>(t: b).end(), comp: sigEntryLess); |
| 1098 | }; |
| 1099 | std::map<MapKey, Value, decltype(mapKeyLess)> signatureToCanonical( |
| 1100 | mapKeyLess); |
| 1101 | bool changed = false; |
| 1102 | // Total complexity: O(n * k * max(log k, log n)). For each input, sorting |
| 1103 | // the signature costs O(k log k) and the std::map lookup costs O(k log n). |
| 1104 | for (Value input : inputs) { |
| 1105 | // Gather the predecessor value for each predecessor (region branch |
| 1106 | // point) and sort them to form this input's signature. |
| 1107 | Signature sig; |
| 1108 | for (OpOperand *operand : inputsToOperands[input]) |
| 1109 | sig.emplace_back(Args: operand->getOwner(), Args: operand->get()); |
| 1110 | llvm::sort(C&: sig, Comp: sigEntryLess); |
| 1111 | |
| 1112 | void *owner = getOwnerOfValue(value: input); |
| 1113 | |
| 1114 | auto [it, inserted] = signatureToCanonical.try_emplace( |
| 1115 | k: MapKey{std::move(sig), owner, input.getType()}, args&: input); |
| 1116 | if (!inserted) { |
| 1117 | Value canonical = it->second; |
| 1118 | // Nothing to do if input is already dead. |
| 1119 | if (input.use_empty()) |
| 1120 | continue; |
| 1121 | rewriter.replaceAllUsesWith(from: input, to: canonical); |
| 1122 | changed = true; |
| 1123 | } |
| 1124 | } |
| 1125 | return success(IsSuccess: changed); |
| 1126 | } |
| 1127 | }; |
| 1128 | |
| 1129 | /// Given a range of values, return a vector of attributes of the same size, |
| 1130 | /// where the i-th attribute is the constant value of the i-th value. If a |
| 1131 | /// value is not constant, the corresponding attribute is null. |
| 1132 | static SmallVector<Attribute> (ValueRange values) { |
| 1133 | return llvm::map_to_vector(C&: values, F: [](Value value) { |
| 1134 | Attribute attr; |
| 1135 | matchPattern(value, pattern: m_Constant(bind_value: &attr)); |
| 1136 | return attr; |
| 1137 | }); |
| 1138 | } |
| 1139 | |
| 1140 | /// Return all successor regions when branching from the given region branch |
| 1141 | /// point. This helper functions extracts all constant operand values and |
| 1142 | /// passes them to the `RegionBranchOpInterface`. |
| 1143 | static SmallVector<RegionSuccessor> |
| 1144 | getSuccessorRegionsWithAttrs(RegionBranchOpInterface op, |
| 1145 | RegionBranchPoint point) { |
| 1146 | SmallVector<RegionSuccessor> successors; |
| 1147 | if (point.isParent()) { |
| 1148 | op.getEntrySuccessorRegions(operands: extractConstants(values: op->getOperands()), |
| 1149 | regions&: successors); |
| 1150 | return successors; |
| 1151 | } |
| 1152 | RegionBranchTerminatorOpInterface terminator = |
| 1153 | point.getTerminatorPredecessorOrNull(); |
| 1154 | terminator.getSuccessorRegions(operands: extractConstants(values: terminator->getOperands()), |
| 1155 | regions&: successors); |
| 1156 | return successors; |
| 1157 | } |
| 1158 | |
| 1159 | /// Find the single acyclic path through the given region branch op. Return an |
| 1160 | /// empty vector if no such path or multiple such paths exist. |
| 1161 | /// |
| 1162 | /// Example: "scf.if %true" has a single path: |
| 1163 | /// parent => then_region => op |
| 1164 | /// |
| 1165 | /// Example: "scf.if %cond" has multiple paths: |
| 1166 | /// (1) parent => then_region => ancestor op |
| 1167 | /// (2) parent => else_region => ancestor op |
| 1168 | /// |
| 1169 | /// Example: "scf.while with scf.condition(%false)" has a single path: |
| 1170 | /// parent => before_region => ancestor op |
| 1171 | /// |
| 1172 | /// Example: "scf.for with 0 iterations" has a single path: parent => op |
| 1173 | /// |
| 1174 | /// Note: Each path starts from the op. The initial parent branch point is |
| 1175 | /// omitted from the result. |
| 1176 | /// |
| 1177 | /// Note: This function also returns an "empty" path when a region with multiple |
| 1178 | /// blocks was found. |
| 1179 | static SmallVector<RegionSuccessor> |
| 1180 | computeSingleAcyclicRegionBranchPath(RegionBranchOpInterface op) { |
| 1181 | llvm::SmallDenseSet<Region *> visited; |
| 1182 | SmallVector<RegionSuccessor> path; |
| 1183 | |
| 1184 | // Path starts with "parent". |
| 1185 | RegionBranchPoint next = RegionBranchPoint::parent(); |
| 1186 | do { |
| 1187 | SmallVector<RegionSuccessor> successors = |
| 1188 | getSuccessorRegionsWithAttrs(op, point: next); |
| 1189 | if (successors.size() != 1) { |
| 1190 | // There are multiple region successors. I.e., there are multiple paths |
| 1191 | // through the region branch op. |
| 1192 | return {}; |
| 1193 | } |
| 1194 | path.push_back(Elt: successors.front()); |
| 1195 | if (successors.front().isOperation()) { |
| 1196 | // Found path that ends after an operation. |
| 1197 | return path; |
| 1198 | } |
| 1199 | Region *region = successors.front().getSuccessor(); |
| 1200 | if (!region->hasOneBlock()) { |
| 1201 | // Entering a region with multiple blocks. Such regions are not supported |
| 1202 | // at the moment. |
| 1203 | return {}; |
| 1204 | } |
| 1205 | if (!visited.insert(V: region).second) { |
| 1206 | // We have already visited this region. I.e., we have found a cycle. |
| 1207 | return {}; |
| 1208 | } |
| 1209 | auto terminator = |
| 1210 | dyn_cast<RegionBranchTerminatorOpInterface>(Val: ®ion->front().back()); |
| 1211 | if (!terminator) { |
| 1212 | // Region has no RegionBranchTerminatorOpInterface terminator. E.g., the |
| 1213 | // terminator could be a "ub.unreachable" op. Such IR is not supported. |
| 1214 | return {}; |
| 1215 | } |
| 1216 | next = RegionBranchPoint(terminator); |
| 1217 | } while (true); |
| 1218 | llvm_unreachable("expected to return from loop" ); |
| 1219 | } |
| 1220 | |
| 1221 | /// Inline the body of the matched region branch op into the enclosing block if |
| 1222 | /// there is exactly one acyclic path through the region branch op, starting |
| 1223 | /// from "parent", and if that path ends with "parent". |
| 1224 | /// |
| 1225 | /// Example: This pattern can inline "scf.for" operations that are guaranteed to |
| 1226 | /// have a single iteration, as indicated by the region branch path "parent => |
| 1227 | /// region => parent". "scf.for" operations have a non-successor-input: the loop |
| 1228 | /// induction variable. Non-successor-input values have op-specific semantics |
| 1229 | /// and cannot be reasoned about through the `RegionBranchOpInterface`. A |
| 1230 | /// replacement value for non-successor-inputs is injected by the user-specified |
| 1231 | /// lambda: in the case of the loop induction variable of an "scf.for", the |
| 1232 | /// lower bound of the loop is used as a replacement value. |
| 1233 | /// |
| 1234 | /// Before pattern application: |
| 1235 | /// %r = scf.for %iv = %c5 to %c6 step %c1 iter_args(%arg0 = %0) { |
| 1236 | /// %1 = "producer"(%arg0, %iv) |
| 1237 | /// scf.yield %1 |
| 1238 | /// } |
| 1239 | /// "user"(%r) |
| 1240 | /// |
| 1241 | /// After pattern application: |
| 1242 | /// %1 = "producer"(%0, %c5) |
| 1243 | /// "user"(%1) |
| 1244 | /// |
| 1245 | /// This pattern is limited to the following cases: |
| 1246 | /// - Only regions with a single block are supported. This could be generalized. |
| 1247 | /// - Region branch ops with side effects are not supported. (Recursive side |
| 1248 | /// effects are fine.) |
| 1249 | /// |
| 1250 | /// Note: This pattern queries the region dataflow from the |
| 1251 | /// `RegionBranchOpInterface`. Replacement values are for block arguments / op |
| 1252 | /// results are determined based on region dataflow. In case of |
| 1253 | /// non-successor-inputs (whose values are not modeled by the |
| 1254 | /// `RegionBranchOpInterface`), a user-specified lambda is queried. |
| 1255 | struct InlineRegionBranchOp : public RewritePattern { |
| 1256 | InlineRegionBranchOp(MLIRContext *context, StringRef name, |
| 1257 | NonSuccessorInputReplacementBuilderFn replBuilderFn, |
| 1258 | PatternMatcherFn matcherFn, PatternBenefit benefit = 1) |
| 1259 | : RewritePattern(name, benefit, context), replBuilderFn(replBuilderFn), |
| 1260 | matcherFn(matcherFn) {} |
| 1261 | |
| 1262 | LogicalResult matchAndRewrite(Operation *op, |
| 1263 | PatternRewriter &rewriter) const override { |
| 1264 | // Check if the pattern is applicable to the given operation. |
| 1265 | if (failed(Result: matcherFn(op))) |
| 1266 | return rewriter.notifyMatchFailure(arg&: op, msg: "pattern not applicable" ); |
| 1267 | |
| 1268 | // Patterns without recursive memory effects could have side effects, so |
| 1269 | // it is not safe to fold such ops away. |
| 1270 | if (!op->hasTrait<OpTrait::HasRecursiveMemoryEffects>()) |
| 1271 | return rewriter.notifyMatchFailure( |
| 1272 | arg&: op, msg: "pattern not applicable to ops without recursive memory effects" ); |
| 1273 | |
| 1274 | // Find the single acyclic path through the region branch op. |
| 1275 | auto regionBranchOp = cast<RegionBranchOpInterface>(Val: op); |
| 1276 | SmallVector<RegionSuccessor> path = |
| 1277 | computeSingleAcyclicRegionBranchPath(op: regionBranchOp); |
| 1278 | if (path.empty()) |
| 1279 | return rewriter.notifyMatchFailure( |
| 1280 | arg&: op, msg: "failed to find acyclic region branch path" ); |
| 1281 | |
| 1282 | // Inline all regions on the path into the enclosing block. |
| 1283 | rewriter.setInsertionPoint(op); |
| 1284 | ArrayRef remainingPath = path; |
| 1285 | SmallVector<Value> successorOperands = llvm::to_vector( |
| 1286 | Range: regionBranchOp.getEntrySuccessorOperands(successor: remainingPath.front())); |
| 1287 | while (!remainingPath.empty()) { |
| 1288 | RegionSuccessor nextSuccessor = remainingPath.consume_front(); |
| 1289 | ValueRange successorInputs = |
| 1290 | regionBranchOp.getSuccessorInputs(successor: nextSuccessor); |
| 1291 | assert(successorInputs.size() == successorOperands.size() && |
| 1292 | "size mismatch" ); |
| 1293 | // Find the index of the first block argument / op result that is a |
| 1294 | // succesor input. |
| 1295 | unsigned firstSuccessorInputIdx = 0; |
| 1296 | if (!successorInputs.empty()) |
| 1297 | firstSuccessorInputIdx = |
| 1298 | nextSuccessor.isOperation() |
| 1299 | ? cast<OpResult>(Val: successorInputs.front()).getResultNumber() |
| 1300 | : cast<BlockArgument>(Val: successorInputs.front()).getArgNumber(); |
| 1301 | // Query the total number of block arguments / op results. |
| 1302 | unsigned numValues = |
| 1303 | nextSuccessor.isOperation() |
| 1304 | ? nextSuccessor.getSuccessorOp()->getNumResults() |
| 1305 | : nextSuccessor.getSuccessor()->getNumArguments(); |
| 1306 | // Compute replacement values for all block arguments / op results. |
| 1307 | SmallVector<Value> replacements; |
| 1308 | // Helper function to get the i-th block argument / op result. |
| 1309 | auto getValue = [&](unsigned idx) { |
| 1310 | return nextSuccessor.isOperation() |
| 1311 | ? Value(nextSuccessor.getSuccessorOp()->getResult(idx)) |
| 1312 | : Value(nextSuccessor.getSuccessor()->getArgument(i: idx)); |
| 1313 | }; |
| 1314 | // Compute replacement values for all non-successor-input values that |
| 1315 | // precede the first successor input. |
| 1316 | for (unsigned i = 0; i < firstSuccessorInputIdx; ++i) |
| 1317 | replacements.push_back( |
| 1318 | Elt: replBuilderFn(rewriter, op->getLoc(), getValue(i))); |
| 1319 | // Use the successor operands of the predecessor as replacement values for |
| 1320 | // the successor inputs. |
| 1321 | llvm::append_range(C&: replacements, R&: successorOperands); |
| 1322 | // Compute replacement values for all block arguments / op results that |
| 1323 | // succeed the first successor input. |
| 1324 | for (unsigned i = replacements.size(); i < numValues; ++i) |
| 1325 | replacements.push_back( |
| 1326 | Elt: replBuilderFn(rewriter, op->getLoc(), getValue(i))); |
| 1327 | if (nextSuccessor.isOperation()) { |
| 1328 | // The path ends after the region branch op. Replace it with the |
| 1329 | // computed replacement values. |
| 1330 | if (nextSuccessor.getSuccessorOp() != op) |
| 1331 | return rewriter.notifyMatchFailure( |
| 1332 | arg&: op, msg: "path ends after a different operation" ); |
| 1333 | assert(remainingPath.empty() && "expected that the path ended" ); |
| 1334 | rewriter.replaceOp(op, newValues: replacements); |
| 1335 | return success(); |
| 1336 | } |
| 1337 | // We are inside of a region: query the successor operands from the |
| 1338 | // terminator, inline the region into the enclosing block, and erase the |
| 1339 | // terminator. |
| 1340 | auto terminator = cast<RegionBranchTerminatorOpInterface>( |
| 1341 | Val: &nextSuccessor.getSuccessor()->front().back()); |
| 1342 | rewriter.inlineBlockBefore(source: &nextSuccessor.getSuccessor()->front(), |
| 1343 | dest: op->getBlock(), before: op->getIterator(), |
| 1344 | argValues: replacements); |
| 1345 | successorOperands = llvm::to_vector( |
| 1346 | Range: terminator.getSuccessorOperands(successor: remainingPath.front())); |
| 1347 | rewriter.eraseOp(op: terminator); |
| 1348 | } |
| 1349 | |
| 1350 | llvm_unreachable("expected that path ends with an operation" ); |
| 1351 | } |
| 1352 | |
| 1353 | NonSuccessorInputReplacementBuilderFn replBuilderFn; |
| 1354 | PatternMatcherFn matcherFn; |
| 1355 | }; |
| 1356 | } // namespace |
| 1357 | |
| 1358 | void mlir::populateRegionBranchOpInterfaceCanonicalizationPatterns( |
| 1359 | RewritePatternSet &patterns, StringRef opName, PatternBenefit benefit) { |
| 1360 | patterns.add<MakeRegionBranchOpSuccessorInputsDead, |
| 1361 | RemoveDuplicateSuccessorInputUses, |
| 1362 | RemoveDeadRegionBranchOpSuccessorInputs>(arg: patterns.getContext(), |
| 1363 | args&: opName, args&: benefit); |
| 1364 | } |
| 1365 | |
| 1366 | void mlir::populateRegionBranchOpInterfaceInliningPattern( |
| 1367 | RewritePatternSet &patterns, StringRef opName, |
| 1368 | NonSuccessorInputReplacementBuilderFn replBuilderFn, |
| 1369 | PatternMatcherFn matcherFn, PatternBenefit benefit) { |
| 1370 | patterns.add<InlineRegionBranchOp>(arg: patterns.getContext(), args&: opName, |
| 1371 | args&: replBuilderFn, args&: matcherFn, args&: benefit); |
| 1372 | } |
| 1373 | |