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
21using namespace mlir;
22
23//===----------------------------------------------------------------------===//
24// ControlFlowInterfaces
25//===----------------------------------------------------------------------===//
26
27#include "mlir/Interfaces/ControlFlowInterfaces.cpp.inc"
28
29SuccessorOperands::SuccessorOperands(MutableOperandRange forwardedOperands)
30 : producedOperandCount(0), forwardedOperands(std::move(forwardedOperands)) {
31}
32
33SuccessorOperands::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.
45std::optional<BlockArgument>
46detail::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.
77LogicalResult
78detail::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
119static 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
139LogicalResult 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
150LogicalResult 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.
161LogicalResult 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.
227static SmallVector<Region *>
228filterRegionSuccessors(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.
241static 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.
252using 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".
258static 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).
306static 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.
324bool 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
389bool 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.
408static 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
449bool 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
463OperandRange
464RegionBranchOpInterface::getSuccessorOperands(RegionBranchPoint src,
465 RegionSuccessor dest) {
466 if (src.isParent())
467 return getEntrySuccessorOperands(successor: dest);
468 return src.getTerminatorPredecessorOrNull().getSuccessorOperands(successor: dest);
469}
470
471SmallVector<Value>
472RegionBranchOpInterface::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
489static MutableArrayRef<OpOperand> operandsToOpOperands(OperandRange &operands) {
490 return MutableArrayRef<OpOperand>(operands.getBase(), operands.size());
491}
492
493static void
494getSuccessorOperandInputMapping(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}
508void 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
521static 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
531void RegionBranchOpInterface::getSuccessorInputOperandMapping(
532 RegionBranchInverseSuccessorMapping &mapping) {
533 RegionBranchSuccessorMapping operandToInputs;
534 getSuccessorOperandInputMapping(mapping&: operandToInputs);
535 mapping = invertRegionBranchSuccessorMapping(operandToInputs);
536}
537
538SmallVector<RegionBranchPoint>
539RegionBranchOpInterface::getAllRegionBranchPoints() {
540 SmallVector<RegionBranchPoint> branchPoints;
541 branchPoints.push_back(Elt: RegionBranchPoint::parent());
542 for (Region &region : 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
554Region *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
579Region *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`.
609static 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}
690static 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
716namespace {
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.
742struct 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.
826template <typename MappingTy, typename KeyTy>
827static 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}}.
842static 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.
897struct 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.
1000static 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.
1007static 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.
1044struct 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.
1132static SmallVector<Attribute> extractConstants(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`.
1143static SmallVector<RegionSuccessor>
1144getSuccessorRegionsWithAttrs(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.
1179static SmallVector<RegionSuccessor>
1180computeSingleAcyclicRegionBranchPath(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: &region->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.
1255struct 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
1358void 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
1366void 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