1//===- SCF.cpp - Structured Control Flow Operations -----------------------===//
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 "mlir/Dialect/SCF/IR/SCF.h"
10#include "mlir/Conversion/ConvertToEmitC/ToEmitCInterface.h"
11#include "mlir/Dialect/Arith/IR/Arith.h"
12#include "mlir/Dialect/Arith/Utils/Utils.h"
13#include "mlir/Dialect/Bufferization/IR/BufferDeallocationOpInterface.h"
14#include "mlir/Dialect/Bufferization/IR/BufferizableOpInterface.h"
15#include "mlir/Dialect/ControlFlow/IR/ControlFlowOps.h"
16#include "mlir/Dialect/MemRef/IR/MemRef.h"
17#include "mlir/Dialect/SCF/IR/DeviceMappingInterface.h"
18#include "mlir/Dialect/Tensor/IR/Tensor.h"
19#include "mlir/Dialect/Utils/StructuredOpsUtils.h"
20#include "mlir/IR/BuiltinAttributes.h"
21#include "mlir/IR/IRMapping.h"
22#include "mlir/IR/Matchers.h"
23#include "mlir/IR/Operation.h"
24#include "mlir/IR/OperationSupport.h"
25#include "mlir/IR/PatternMatch.h"
26#include "mlir/Interfaces/FunctionInterfaces.h"
27#include "mlir/Interfaces/ParallelCombiningOpInterface.h"
28#include "mlir/Interfaces/ValueBoundsOpInterface.h"
29#include "mlir/Transforms/InliningUtils.h"
30#include "mlir/Transforms/RegionUtils.h"
31#include "llvm/ADT/MapVector.h"
32#include "llvm/ADT/STLExtras.h"
33#include "llvm/ADT/SmallPtrSet.h"
34#include "llvm/ADT/SmallVectorExtras.h"
35#include "llvm/ADT/TypeSwitch.h"
36#include "llvm/Support/Casting.h"
37#include "llvm/Support/DebugLog.h"
38#include <optional>
39
40using namespace mlir;
41using namespace mlir::scf;
42
43#include "mlir/Dialect/SCF/IR/SCFOpsDialect.cpp.inc"
44
45//===----------------------------------------------------------------------===//
46// SCFDialect Dialect Interfaces
47//===----------------------------------------------------------------------===//
48
49namespace {
50struct SCFInlinerInterface : public DialectInlinerInterface {
51 using DialectInlinerInterface::DialectInlinerInterface;
52 // We don't have any special restrictions on what can be inlined into
53 // destination regions (e.g. while/conditional bodies). Always allow it.
54 bool isLegalToInline(Region *dest, Region *src, bool wouldBeCloned,
55 IRMapping &valueMapping) const final {
56 return true;
57 }
58 // Operations in scf dialect are always legal to inline since they are
59 // pure.
60 bool isLegalToInline(Operation *, Region *, bool, IRMapping &) const final {
61 return true;
62 }
63 // Handle the given inlined terminator by replacing it with a new operation
64 // as necessary. Required when the region has only one block.
65 void handleTerminator(Operation *op, ValueRange valuesToRepl) const final {
66 auto retValOp = dyn_cast<scf::YieldOp>(Val: op);
67 if (!retValOp)
68 return;
69
70 for (auto retValue : llvm::zip(t&: valuesToRepl, u: retValOp.getOperands())) {
71 std::get<0>(t&: retValue).replaceAllUsesWith(newValue: std::get<1>(t&: retValue));
72 }
73 }
74};
75} // namespace
76
77//===----------------------------------------------------------------------===//
78// SCFDialect
79//===----------------------------------------------------------------------===//
80
81void SCFDialect::initialize() {
82 addOperations<
83#define GET_OP_LIST
84#include "mlir/Dialect/SCF/IR/SCFOps.cpp.inc"
85 >();
86 addInterfaces<SCFInlinerInterface>();
87 declarePromisedInterface<ConvertToEmitCPatternInterface, SCFDialect>();
88 declarePromisedInterfaces<bufferization::BufferDeallocationOpInterface,
89 InParallelOp, ReduceReturnOp>();
90 declarePromisedInterfaces<bufferization::BufferizableOpInterface, ConditionOp,
91 ExecuteRegionOp, ForOp, IfOp, IndexSwitchOp,
92 ForallOp, InParallelOp, WhileOp, YieldOp>();
93 declarePromisedInterface<ValueBoundsOpInterface, ForOp>();
94}
95
96/// Default callback for IfOp builders. Inserts a yield without arguments.
97void mlir::scf::buildTerminatedBody(OpBuilder &builder, Location loc) {
98 scf::YieldOp::create(builder, location: loc);
99}
100
101/// Verifies that the first block of the given `region` is terminated by a
102/// TerminatorTy. Reports errors on the given operation if it is not the case.
103template <typename TerminatorTy>
104static TerminatorTy verifyAndGetTerminator(Operation *op, Region &region,
105 StringRef errorMessage) {
106 Operation *terminatorOperation = nullptr;
107 if (!region.empty() && !region.front().empty()) {
108 terminatorOperation = &region.front().back();
109 if (auto yield = dyn_cast_or_null<TerminatorTy>(terminatorOperation))
110 return yield;
111 }
112 auto diag = op->emitOpError(message: errorMessage);
113 if (terminatorOperation)
114 diag.attachNote(noteLoc: terminatorOperation->getLoc()) << "terminator here";
115 return nullptr;
116}
117
118std::optional<llvm::APSInt> mlir::scf::computeUbMinusLb(Value lb, Value ub,
119 bool isSigned) {
120 llvm::APSInt diff;
121 auto addOp = ub.getDefiningOp<arith::AddIOp>();
122 if (!addOp)
123 return std::nullopt;
124 if ((isSigned && !addOp.hasNoSignedWrap()) ||
125 (!isSigned && !addOp.hasNoUnsignedWrap()))
126 return std::nullopt;
127
128 if (addOp.getLhs() != lb ||
129 !matchPattern(value: addOp.getRhs(), pattern: m_ConstantInt(bind_value: &diff)))
130 return std::nullopt;
131 return diff;
132}
133
134//===----------------------------------------------------------------------===//
135// ExecuteRegionOp
136//===----------------------------------------------------------------------===//
137
138///
139/// (ssa-id `=`)? `execute_region` `->` function-result-type `{`
140/// block+
141/// `}`
142///
143/// Example:
144/// scf.execute_region -> i32 {
145/// %idx = load %rI[%i] : memref<128xi32>
146/// return %idx : i32
147/// }
148///
149ParseResult ExecuteRegionOp::parse(OpAsmParser &parser,
150 OperationState &result) {
151 if (parser.parseOptionalArrowTypeList(result&: result.types))
152 return failure();
153
154 if (succeeded(Result: parser.parseOptionalKeyword(keyword: "no_inline")))
155 result.addAttribute(name: "no_inline", attr: parser.getBuilder().getUnitAttr());
156
157 // Introduce the body region and parse it.
158 Region *body = result.addRegion();
159 if (parser.parseRegion(region&: *body, /*arguments=*/{}, /*argTypes=*/enableNameShadowing: {}) ||
160 parser.parseOptionalAttrDict(result&: result.attributes))
161 return failure();
162
163 return success();
164}
165
166void ExecuteRegionOp::print(OpAsmPrinter &p) {
167 p.printOptionalArrowTypeList(types: getResultTypes());
168 p << ' ';
169 if (getNoInline())
170 p << "no_inline ";
171 p.printRegion(blocks&: getRegion(),
172 /*printEntryBlockArgs=*/false,
173 /*printBlockTerminators=*/true);
174 p.printOptionalAttrDict(attrs: (*this)->getDiscardableAttrDictionary().getValue());
175}
176
177LogicalResult ExecuteRegionOp::verify() {
178 if (getRegion().empty())
179 return emitOpError(message: "region needs to have at least one block");
180 if (getRegion().front().getNumArguments() > 0)
181 return emitOpError(message: "region cannot have any arguments");
182 return success();
183}
184
185// Inline an ExecuteRegionOp if its parent can contain multiple blocks.
186// TODO generalize the conditions for operations which can be inlined into.
187// func @func_execute_region_elim() {
188// "test.foo"() : () -> ()
189// %v = scf.execute_region -> i64 {
190// %c = "test.cmp"() : () -> i1
191// cf.cond_br %c, ^bb2, ^bb3
192// ^bb2:
193// %x = "test.val1"() : () -> i64
194// cf.br ^bb4(%x : i64)
195// ^bb3:
196// %y = "test.val2"() : () -> i64
197// cf.br ^bb4(%y : i64)
198// ^bb4(%z : i64):
199// scf.yield %z : i64
200// }
201// "test.bar"(%v) : (i64) -> ()
202// return
203// }
204//
205// becomes
206//
207// func @func_execute_region_elim() {
208// "test.foo"() : () -> ()
209// %c = "test.cmp"() : () -> i1
210// cf.cond_br %c, ^bb1, ^bb2
211// ^bb1: // pred: ^bb0
212// %x = "test.val1"() : () -> i64
213// cf.br ^bb3(%x : i64)
214// ^bb2: // pred: ^bb0
215// %y = "test.val2"() : () -> i64
216// cf.br ^bb3(%y : i64)
217// ^bb3(%z: i64): // 2 preds: ^bb1, ^bb2
218// "test.bar"(%z) : (i64) -> ()
219// return
220// }
221//
222struct MultiBlockExecuteInliner : public OpRewritePattern<ExecuteRegionOp> {
223 using OpRewritePattern<ExecuteRegionOp>::OpRewritePattern;
224
225 LogicalResult matchAndRewrite(ExecuteRegionOp op,
226 PatternRewriter &rewriter) const override {
227 if (op.getNoInline())
228 return failure();
229 if (!isa<FunctionOpInterface, ExecuteRegionOp>(Val: op->getParentOp()))
230 return failure();
231
232 Block *prevBlock = op->getBlock();
233 Block *postBlock = rewriter.splitBlock(block: prevBlock, before: op->getIterator());
234 rewriter.setInsertionPointToEnd(prevBlock);
235
236 cf::BranchOp::create(builder&: rewriter, location: op.getLoc(), dest: &op.getRegion().front());
237
238 for (Block &blk : op.getRegion()) {
239 if (YieldOp yieldOp = dyn_cast<YieldOp>(Val: blk.getTerminator())) {
240 rewriter.setInsertionPoint(yieldOp);
241 cf::BranchOp::create(builder&: rewriter, location: yieldOp.getLoc(), dest: postBlock,
242 destOperands: yieldOp.getResults());
243 rewriter.eraseOp(op: yieldOp);
244 }
245 }
246
247 rewriter.inlineRegionBefore(region&: op.getRegion(), before: postBlock);
248 SmallVector<Value> blockArgs;
249
250 for (auto res : op.getResults())
251 blockArgs.push_back(Elt: postBlock->addArgument(type: res.getType(), loc: res.getLoc()));
252
253 rewriter.replaceOp(op, newValues: blockArgs);
254 return success();
255 }
256};
257
258void ExecuteRegionOp::getCanonicalizationPatterns(RewritePatternSet &results,
259 MLIRContext *context) {
260 results.add<MultiBlockExecuteInliner>(arg&: context);
261 populateRegionBranchOpInterfaceCanonicalizationPatterns(
262 patterns&: results, opName: ExecuteRegionOp::getOperationName());
263 // Inline ops with a single block that are not marked as "no_inline".
264 populateRegionBranchOpInterfaceInliningPattern(
265 patterns&: results, opName: ExecuteRegionOp::getOperationName(),
266 replBuilderFn: mlir::detail::defaultReplBuilderFn, matcherFn: [](Operation *op) {
267 return failure(IsFailure: cast<ExecuteRegionOp>(Val: op).getNoInline());
268 });
269}
270
271void ExecuteRegionOp::getSuccessorRegions(
272 RegionBranchPoint point, SmallVectorImpl<RegionSuccessor> &regions) {
273 // If the predecessor is the ExecuteRegionOp, branch into the body.
274 if (point.isParent()) {
275 regions.push_back(Elt: RegionSuccessor(&getRegion()));
276 return;
277 }
278
279 // Otherwise, the region branches back to the parent operation.
280 regions.push_back(Elt: RegionSuccessor(getOperation()));
281}
282
283void ExecuteRegionOp::getRegionInvocationBounds(
284 ArrayRef<Attribute>, SmallVectorImpl<InvocationBounds> &bounds) {
285 bounds.emplace_back(/*lb=*/Args: 1, /*ub=*/Args: 1);
286}
287
288ValueRange ExecuteRegionOp::getSuccessorInputs(RegionSuccessor successor) {
289 return successor.isOperation() ? ValueRange(getOperation()->getResults())
290 : ValueRange();
291}
292
293//===----------------------------------------------------------------------===//
294// ConditionOp
295//===----------------------------------------------------------------------===//
296
297MutableOperandRange
298ConditionOp::getMutableSuccessorOperands(RegionSuccessor point) {
299 assert((point.isOperation() ||
300 point.getSuccessor() == &getParentOp().getAfter()) &&
301 "condition op can only exit the loop or branch to the after"
302 "region");
303 // Pass all operands except the condition to the successor region.
304 return getArgsMutable();
305}
306
307void ConditionOp::getSuccessorRegions(
308 ArrayRef<Attribute> operands, SmallVectorImpl<RegionSuccessor> &regions) {
309 FoldAdaptor adaptor(operands, *this);
310
311 WhileOp whileOp = getParentOp();
312
313 // Condition can either lead to the after region or back to the parent op
314 // depending on whether the condition is true or not.
315 auto boolAttr = dyn_cast_or_null<BoolAttr>(Val: adaptor.getCondition());
316 if (!boolAttr || boolAttr.getValue())
317 regions.emplace_back(Args: &whileOp.getAfter());
318 if (!boolAttr || !boolAttr.getValue())
319 regions.push_back(Elt: RegionSuccessor(whileOp.getOperation()));
320}
321
322//===----------------------------------------------------------------------===//
323// ForOp
324//===----------------------------------------------------------------------===//
325
326void ForOp::build(OpBuilder &builder, OperationState &result, Value lb,
327 Value ub, Value step, ValueRange initArgs,
328 BodyBuilderFn bodyBuilder, bool unsignedCmp) {
329 OpBuilder::InsertionGuard guard(builder);
330
331 if (unsignedCmp)
332 result.addAttribute(name: getUnsignedCmpAttrName(name: result.name),
333 attr: builder.getUnitAttr());
334 result.addOperands(newOperands: {lb, ub, step});
335 result.addOperands(newOperands: initArgs);
336 for (Value v : initArgs)
337 result.addTypes(newTypes: v.getType());
338 Type t = lb.getType();
339 Region *bodyRegion = result.addRegion();
340 Block *bodyBlock = builder.createBlock(parent: bodyRegion);
341 bodyBlock->addArgument(type: t, loc: result.location);
342 for (Value v : initArgs)
343 bodyBlock->addArgument(type: v.getType(), loc: v.getLoc());
344
345 // Create the default terminator if the builder is not provided and if the
346 // iteration arguments are not provided. Otherwise, leave this to the caller
347 // because we don't know which values to return from the loop.
348 if (initArgs.empty() && !bodyBuilder) {
349 ForOp::ensureTerminator(region&: *bodyRegion, builder, loc: result.location);
350 } else if (bodyBuilder) {
351 OpBuilder::InsertionGuard guard(builder);
352 builder.setInsertionPointToStart(bodyBlock);
353 bodyBuilder(builder, result.location, bodyBlock->getArgument(i: 0),
354 bodyBlock->getArguments().drop_front());
355 }
356}
357
358LogicalResult ForOp::verify() {
359 // Check that the body block has at least the induction variable argument.
360 // This must be checked before verifyRegions() and before any region trait
361 // verifiers (e.g. LoopLikeOpInterface) that call getRegionIterArgs(), to
362 // avoid crashing with an out-of-bounds drop_front on an empty arg list.
363 if (getBody()->getNumArguments() < getNumInductionVars())
364 return emitOpError(message: "expected body to have at least ")
365 << getNumInductionVars()
366 << " argument(s) for the induction variable, but got "
367 << getBody()->getNumArguments();
368
369 // Check that the number of init args and op results is the same.
370 if (getInitArgs().size() != getNumResults())
371 return emitOpError(
372 message: "mismatch in number of loop-carried values and defined values");
373
374 return success();
375}
376
377LogicalResult ForOp::verifyRegions() {
378 // Check that the body block has at least the induction variable argument.
379 if (getBody()->getNumArguments() < getNumInductionVars())
380 return emitOpError(message: "expected body to have at least ")
381 << getNumInductionVars() << " argument(s) for the induction "
382 << "variable, but got " << getBody()->getNumArguments();
383
384 // Check that the body defines as single block argument for the induction
385 // variable.
386 if (getInductionVar().getType() != getLowerBound().getType())
387 return emitOpError(
388 message: "expected induction variable to be same type as bounds and step");
389
390 if (getNumRegionIterArgs() != getNumResults())
391 return emitOpError(
392 message: "mismatch in number of basic block args and defined values");
393
394 auto initArgs = getInitArgs();
395 auto iterArgs = getRegionIterArgs();
396 auto opResults = getResults();
397 unsigned i = 0;
398 for (auto e : llvm::zip(t&: initArgs, u&: iterArgs, args&: opResults)) {
399 if (std::get<0>(t&: e).getType() != std::get<2>(t&: e).getType())
400 return emitOpError() << "types mismatch between " << i
401 << "th iter operand and defined value";
402 if (std::get<1>(t&: e).getType() != std::get<2>(t&: e).getType())
403 return emitOpError() << "types mismatch between " << i
404 << "th iter region arg and defined value";
405
406 ++i;
407 }
408 return success();
409}
410
411std::optional<SmallVector<Value>> ForOp::getLoopInductionVars() {
412 return SmallVector<Value>{getInductionVar()};
413}
414
415std::optional<SmallVector<OpFoldResult>> ForOp::getLoopLowerBounds() {
416 return SmallVector<OpFoldResult>{OpFoldResult(getLowerBound())};
417}
418
419std::optional<SmallVector<OpFoldResult>> ForOp::getLoopSteps() {
420 return SmallVector<OpFoldResult>{OpFoldResult(getStep())};
421}
422
423std::optional<SmallVector<OpFoldResult>> ForOp::getLoopUpperBounds() {
424 return SmallVector<OpFoldResult>{OpFoldResult(getUpperBound())};
425}
426
427bool ForOp::isValidInductionVarType(Type type) {
428 return type.isIndex() || type.isSignlessInteger();
429}
430
431LogicalResult ForOp::setLoopLowerBounds(ArrayRef<OpFoldResult> bounds) {
432 if (bounds.size() != 1)
433 return failure();
434 if (auto val = dyn_cast<Value>(Val: bounds[0])) {
435 setLowerBound(val);
436 return success();
437 }
438 return failure();
439}
440
441LogicalResult ForOp::setLoopUpperBounds(ArrayRef<OpFoldResult> bounds) {
442 if (bounds.size() != 1)
443 return failure();
444 if (auto val = dyn_cast<Value>(Val: bounds[0])) {
445 setUpperBound(val);
446 return success();
447 }
448 return failure();
449}
450
451LogicalResult ForOp::setLoopSteps(ArrayRef<OpFoldResult> steps) {
452 if (steps.size() != 1)
453 return failure();
454 if (auto val = dyn_cast<Value>(Val: steps[0])) {
455 setStep(val);
456 return success();
457 }
458 return failure();
459}
460
461std::optional<ResultRange> ForOp::getLoopResults() { return getResults(); }
462
463/// Promotes the loop body of a forOp to its containing block if the forOp
464/// it can be determined that the loop has a single iteration.
465LogicalResult ForOp::promoteIfSingleIteration(RewriterBase &rewriter) {
466 std::optional<APInt> tripCount = getStaticTripCount();
467 LDBG() << "promoteIfSingleIteration tripCount is " << tripCount
468 << " for loop "
469 << OpWithFlags(getOperation(), OpPrintingFlags().skipRegions());
470 if (!tripCount.has_value() || tripCount->getZExtValue() > 1)
471 return failure();
472
473 if (*tripCount == 0) {
474 rewriter.replaceAllUsesWith(from: getResults(), to: getInitArgs());
475 rewriter.eraseOp(op: *this);
476 return success();
477 }
478
479 // Replace all results with the yielded values.
480 auto yieldOp = cast<scf::YieldOp>(Val: getBody()->getTerminator());
481 rewriter.replaceAllUsesWith(from: getResults(), to: getYieldedValues());
482
483 // Replace block arguments with lower bound (replacement for IV) and
484 // iter_args.
485 SmallVector<Value> bbArgReplacements;
486 bbArgReplacements.push_back(Elt: getLowerBound());
487 llvm::append_range(C&: bbArgReplacements, R: getInitArgs());
488
489 // Move the loop body operations to the loop's containing block.
490 rewriter.inlineBlockBefore(source: getBody(), dest: getOperation()->getBlock(),
491 before: getOperation()->getIterator(), argValues: bbArgReplacements);
492
493 // Erase the old terminator and the loop.
494 rewriter.eraseOp(op: yieldOp);
495 rewriter.eraseOp(op: *this);
496
497 return success();
498}
499
500/// Prints the initialization list in the form of
501/// <prefix>(%inner = %outer, %inner2 = %outer2, <...>)
502/// where 'inner' values are assumed to be region arguments and 'outer' values
503/// are regular SSA values.
504static void printInitializationList(OpAsmPrinter &p,
505 Block::BlockArgListType blocksArgs,
506 ValueRange initializers,
507 StringRef prefix = "") {
508 assert(blocksArgs.size() == initializers.size() &&
509 "expected same length of arguments and initializers");
510 if (initializers.empty())
511 return;
512
513 p << prefix << '(';
514 llvm::interleaveComma(c: llvm::zip(t&: blocksArgs, u&: initializers), os&: p, each_fn: [&](auto it) {
515 p << std::get<0>(it) << " = " << std::get<1>(it);
516 });
517 p << ")";
518}
519
520void ForOp::print(OpAsmPrinter &p) {
521 if (getUnsignedCmp())
522 p << " unsigned";
523
524 p << " " << getInductionVar() << " = " << getLowerBound() << " to "
525 << getUpperBound() << " step " << getStep();
526
527 printInitializationList(p, blocksArgs: getRegionIterArgs(), initializers: getInitArgs(), prefix: " iter_args");
528 if (!getInitArgs().empty())
529 p << " -> (" << getInitArgs().getTypes() << ')';
530 p << ' ';
531 if (Type t = getInductionVar().getType(); !t.isIndex())
532 p << " : " << t << ' ';
533 p.printRegion(blocks&: getRegion(),
534 /*printEntryBlockArgs=*/false,
535 /*printBlockTerminators=*/!getInitArgs().empty());
536 p.printOptionalAttrDict(attrs: (*this)->getDiscardableAttrDictionary().getValue());
537}
538
539ParseResult ForOp::parse(OpAsmParser &parser, OperationState &result) {
540 auto &builder = parser.getBuilder();
541 Type type;
542
543 OpAsmParser::Argument inductionVariable;
544 OpAsmParser::UnresolvedOperand lb, ub, step;
545
546 if (succeeded(Result: parser.parseOptionalKeyword(keyword: "unsigned")))
547 result.addAttribute(name: getUnsignedCmpAttrName(name: result.name),
548 attr: builder.getUnitAttr());
549
550 // Parse the induction variable followed by '='.
551 if (parser.parseOperand(result&: inductionVariable.ssaName) || parser.parseEqual() ||
552 // Parse loop bounds.
553 parser.parseOperand(result&: lb) || parser.parseKeyword(keyword: "to") ||
554 parser.parseOperand(result&: ub) || parser.parseKeyword(keyword: "step") ||
555 parser.parseOperand(result&: step))
556 return failure();
557
558 // Parse the optional initial iteration arguments.
559 SmallVector<OpAsmParser::Argument, 4> regionArgs;
560 SmallVector<OpAsmParser::UnresolvedOperand, 4> operands;
561 regionArgs.push_back(Elt: inductionVariable);
562
563 bool hasIterArgs = succeeded(Result: parser.parseOptionalKeyword(keyword: "iter_args"));
564 if (hasIterArgs) {
565 // Parse assignment list and results type list.
566 if (parser.parseAssignmentList(lhs&: regionArgs, rhs&: operands) ||
567 parser.parseArrowTypeList(result&: result.types))
568 return failure();
569 }
570
571 if (regionArgs.size() != result.types.size() + 1)
572 return parser.emitError(
573 loc: parser.getNameLoc(),
574 message: "mismatch in number of loop-carried values and defined values");
575
576 // Parse optional type, else assume Index.
577 if (parser.parseOptionalColon())
578 type = builder.getIndexType();
579 else if (parser.parseType(result&: type))
580 return failure();
581
582 // Set block argument types, so that they are known when parsing the region.
583 regionArgs.front().type = type;
584 for (auto [iterArg, type] :
585 llvm::zip_equal(t: llvm::drop_begin(RangeOrContainer&: regionArgs), u&: result.types))
586 iterArg.type = type;
587
588 // Parse the body region.
589 Region *body = result.addRegion();
590 if (parser.parseRegion(region&: *body, arguments: regionArgs))
591 return failure();
592 ForOp::ensureTerminator(region&: *body, builder, loc: result.location);
593
594 // Resolve input operands. This should be done after parsing the region to
595 // catch invalid IR where operands were defined inside of the region.
596 if (parser.resolveOperand(operand: lb, type, result&: result.operands) ||
597 parser.resolveOperand(operand: ub, type, result&: result.operands) ||
598 parser.resolveOperand(operand: step, type, result&: result.operands))
599 return failure();
600 if (hasIterArgs) {
601 for (auto argOperandType : llvm::zip_equal(t: llvm::drop_begin(RangeOrContainer&: regionArgs),
602 u&: operands, args&: result.types)) {
603 Type type = std::get<2>(t&: argOperandType);
604 std::get<0>(t&: argOperandType).type = type;
605 if (parser.resolveOperand(operand: std::get<1>(t&: argOperandType), type,
606 result&: result.operands))
607 return failure();
608 }
609 }
610
611 // Parse the optional attribute list.
612 if (parser.parseOptionalAttrDict(result&: result.attributes))
613 return failure();
614
615 return success();
616}
617
618SmallVector<Region *> ForOp::getLoopRegions() { return {&getRegion()}; }
619
620Block::BlockArgListType ForOp::getRegionIterArgs() {
621 return getBody()->getArguments().drop_front(N: getNumInductionVars());
622}
623
624MutableArrayRef<OpOperand> ForOp::getInitsMutable() {
625 return getInitArgsMutable();
626}
627
628FailureOr<LoopLikeOpInterface>
629ForOp::replaceWithAdditionalYields(RewriterBase &rewriter,
630 ValueRange newInitOperands,
631 bool replaceInitOperandUsesInLoop,
632 const NewYieldValuesFn &newYieldValuesFn) {
633 // Create a new loop before the existing one, with the extra operands.
634 OpBuilder::InsertionGuard g(rewriter);
635 rewriter.setInsertionPoint(getOperation());
636 auto inits = llvm::to_vector(Range: getInitArgs());
637 inits.append(in_start: newInitOperands.begin(), in_end: newInitOperands.end());
638 scf::ForOp newLoop = scf::ForOp::create(
639 builder&: rewriter, location: getLoc(), lowerBound: getLowerBound(), upperBound: getUpperBound(), step: getStep(), initArgs: inits,
640 odsArg4: [](OpBuilder &, Location, Value, ValueRange) {}, unsignedCmp: getUnsignedCmp());
641 newLoop->setDiscardableAttrs(getOperation()->getDiscardableAttrDictionary());
642
643 // Generate the new yield values and append them to the scf.yield operation.
644 auto yieldOp = cast<scf::YieldOp>(Val: getBody()->getTerminator());
645 ArrayRef<BlockArgument> newIterArgs =
646 newLoop.getBody()->getArguments().take_back(N: newInitOperands.size());
647 {
648 OpBuilder::InsertionGuard g(rewriter);
649 rewriter.setInsertionPoint(yieldOp);
650 SmallVector<Value> newYieldedValues =
651 newYieldValuesFn(rewriter, getLoc(), newIterArgs);
652 assert(newInitOperands.size() == newYieldedValues.size() &&
653 "expected as many new yield values as new iter operands");
654 rewriter.modifyOpInPlace(root: yieldOp, callable: [&]() {
655 yieldOp.getResultsMutable().append(values: newYieldedValues);
656 });
657 }
658
659 // Move the loop body to the new op.
660 rewriter.mergeBlocks(source: getBody(), dest: newLoop.getBody(),
661 argValues: newLoop.getBody()->getArguments().take_front(
662 N: getBody()->getNumArguments()));
663
664 if (replaceInitOperandUsesInLoop) {
665 // Replace all uses of `newInitOperands` with the corresponding basic block
666 // arguments.
667 for (auto it : llvm::zip(t&: newInitOperands, u&: newIterArgs)) {
668 rewriter.replaceUsesWithIf(from: std::get<0>(t&: it), to: std::get<1>(t&: it),
669 functor: [&](OpOperand &use) {
670 Operation *user = use.getOwner();
671 return newLoop->isProperAncestor(other: user);
672 });
673 }
674 }
675
676 // Replace the old loop.
677 rewriter.replaceOp(op: getOperation(),
678 newValues: newLoop->getResults().take_front(n: getNumResults()));
679 return cast<LoopLikeOpInterface>(Val: newLoop.getOperation());
680}
681
682ForOp mlir::scf::getForInductionVarOwner(Value val) {
683 auto ivArg = llvm::dyn_cast<BlockArgument>(Val&: val);
684 if (!ivArg)
685 return ForOp();
686 assert(ivArg.getOwner() && "unlinked block argument");
687 auto *containingOp = ivArg.getOwner()->getParentOp();
688 return dyn_cast_or_null<ForOp>(Val: containingOp);
689}
690
691OperandRange ForOp::getEntrySuccessorOperands(RegionSuccessor successor) {
692 return getInitArgs();
693}
694
695void ForOp::getSuccessorRegions(RegionBranchPoint point,
696 SmallVectorImpl<RegionSuccessor> &regions) {
697 if (std::optional<APInt> tripCount = getStaticTripCount()) {
698 // The loop has a known static trip count.
699 if (point.isParent()) {
700 if (*tripCount == 0) {
701 // The loop has zero iterations. It branches directly back to the
702 // parent.
703 regions.push_back(Elt: RegionSuccessor(getOperation()));
704 } else {
705 // The loop has at least one iteration. It branches into the body.
706 regions.push_back(Elt: RegionSuccessor(&getRegion()));
707 }
708 return;
709 } else if (*tripCount == 1) {
710 // The loop has exactly 1 iteration. Therefore, it branches from the
711 // region to the parent. (No further iteration.)
712 regions.push_back(Elt: RegionSuccessor(getOperation()));
713 return;
714 }
715 }
716
717 // Both the operation itself and the region may be branching into the body or
718 // back into the operation itself. It is possible for loop not to enter the
719 // body.
720 regions.push_back(Elt: RegionSuccessor(&getRegion()));
721 regions.push_back(Elt: RegionSuccessor(getOperation()));
722}
723
724ValueRange ForOp::getSuccessorInputs(RegionSuccessor successor) {
725 return successor.isOperation() ? ValueRange(getResults())
726 : ValueRange(getRegionIterArgs());
727}
728
729SmallVector<Region *> ForallOp::getLoopRegions() { return {&getRegion()}; }
730
731/// Promotes the loop body of a forallOp to its containing block if it can be
732/// determined that the loop has a single iteration.
733LogicalResult scf::ForallOp::promoteIfSingleIteration(RewriterBase &rewriter) {
734 for (auto [lb, ub, step] :
735 llvm::zip(t: getMixedLowerBound(), u: getMixedUpperBound(), args: getMixedStep())) {
736 auto tripCount =
737 constantTripCount(lb, ub, step, /*isSigned=*/true, computeUbMinusLb);
738 if (!tripCount.has_value() || *tripCount != 1)
739 return failure();
740 }
741
742 return promote(rewriter, forallOp: *this);
743}
744
745Block::BlockArgListType ForallOp::getRegionIterArgs() {
746 return getBody()->getArguments().drop_front(N: getRank());
747}
748
749MutableArrayRef<OpOperand> ForallOp::getInitsMutable() {
750 return getOutputsMutable();
751}
752
753/// Promotes the loop body of a scf::ForallOp to its containing block.
754LogicalResult mlir::scf::promote(RewriterBase &rewriter,
755 scf::ForallOp forallOp) {
756 OpBuilder::InsertionGuard g(rewriter);
757 scf::InParallelOp terminator = forallOp.getTerminator();
758
759 // Check that all combining ops can be promoted before modifying the IR,
760 // including materializing the lower bounds below.
761 for (Operation &op : terminator.getYieldingOps()) {
762 if (!isa<tensor::ParallelInsertSliceOp>(Val: op))
763 return rewriter.notifyMatchFailure(op: forallOp, reasonCallback: [&](Diagnostic &diag) {
764 diag << "unsupported parallel combining op: " << op.getName();
765 });
766 }
767
768 // Replace block arguments with lower bounds (replacements for IVs) and
769 // outputs.
770 SmallVector<Value> bbArgReplacements = forallOp.getLowerBound(b&: rewriter);
771 bbArgReplacements.append(in_start: forallOp.getOutputs().begin(),
772 in_end: forallOp.getOutputs().end());
773
774 // Collect combining ops in shared output order before inlining replaces the
775 // output block arguments. Keep a separate list for each output.
776 SmallVector<SmallVector<ParallelCombiningOpInterface, 1>> yieldingOps;
777 yieldingOps.reserve(N: forallOp.getNumResults());
778
779 for (BlockArgument outputArg : forallOp.getRegionIterArgs()) {
780 auto &outputOps = yieldingOps.emplace_back();
781
782 for (Operation *op : forallOp.getCombiningOps(bbArg: outputArg)) {
783 auto combiningOp = cast<ParallelCombiningOpInterface>(Val: op);
784 // Supported tensor.parallel_insert_slice ops have a single destination.
785 if (combiningOp->getParentOp() != terminator.getOperation() ||
786 combiningOp.getUpdatedDestinations()[0].get() != outputArg)
787 continue;
788
789 outputOps.push_back(Elt: combiningOp);
790 }
791 }
792
793 // Move the loop body operations to the loop's containing block.
794 rewriter.inlineBlockBefore(source: forallOp.getBody(), dest: forallOp->getBlock(),
795 before: forallOp->getIterator(), argValues: bbArgReplacements);
796
797 // Replace the terminator with tensor.insert_slice ops.
798 rewriter.setInsertionPointAfter(forallOp);
799 SmallVector<Value> results;
800 results.reserve(N: forallOp.getResults().size());
801 for (auto [output, combiningOps] :
802 llvm::zip_equal(t: forallOp.getOutputs(), u&: yieldingOps)) {
803 Value result = output;
804
805 for (ParallelCombiningOpInterface combiningOp : combiningOps) {
806 auto insertOp = cast<tensor::ParallelInsertSliceOp>(Val&: combiningOp);
807 result = tensor::InsertSliceOp::create(
808 builder&: rewriter, location: forallOp.getLoc(), result: result.getType(), source: insertOp.getSource(),
809 dest: result, offsets: insertOp.getOffsets(), sizes: insertOp.getSizes(),
810 strides: insertOp.getStrides(), static_offsets: insertOp.getStaticOffsets(),
811 static_sizes: insertOp.getStaticSizes(), static_strides: insertOp.getStaticStrides());
812 }
813
814 results.push_back(Elt: result);
815 }
816
817 rewriter.replaceAllUsesWith(from: forallOp.getResults(), to: results);
818
819 // Erase the old terminator and the loop.
820 rewriter.eraseOp(op: terminator);
821 rewriter.eraseOp(op: forallOp);
822 return success();
823}
824
825LoopNest mlir::scf::buildLoopNest(
826 OpBuilder &builder, Location loc, ValueRange lbs, ValueRange ubs,
827 ValueRange steps, ValueRange iterArgs,
828 function_ref<ValueVector(OpBuilder &, Location, ValueRange, ValueRange)>
829 bodyBuilder) {
830 assert(lbs.size() == ubs.size() &&
831 "expected the same number of lower and upper bounds");
832 assert(lbs.size() == steps.size() &&
833 "expected the same number of lower bounds and steps");
834
835 // If there are no bounds, call the body-building function and return early.
836 if (lbs.empty()) {
837 ValueVector results =
838 bodyBuilder ? bodyBuilder(builder, loc, ValueRange(), iterArgs)
839 : ValueVector();
840 assert(results.size() == iterArgs.size() &&
841 "loop nest body must return as many values as loop has iteration "
842 "arguments");
843 return LoopNest{.loops: {}, .results: std::move(results)};
844 }
845
846 // First, create the loop structure iteratively using the body-builder
847 // callback of `ForOp::build`. Do not create `YieldOp`s yet.
848 OpBuilder::InsertionGuard guard(builder);
849 SmallVector<scf::ForOp, 4> loops;
850 SmallVector<Value, 4> ivs;
851 loops.reserve(N: lbs.size());
852 ivs.reserve(N: lbs.size());
853 ValueRange currentIterArgs = iterArgs;
854 Location currentLoc = loc;
855 for (unsigned i = 0, e = lbs.size(); i < e; ++i) {
856 auto loop = scf::ForOp::create(
857 builder, location: currentLoc, lowerBound: lbs[i], upperBound: ubs[i], step: steps[i], initArgs: currentIterArgs,
858 odsArg4: [&](OpBuilder &nestedBuilder, Location nestedLoc, Value iv,
859 ValueRange args) {
860 ivs.push_back(Elt: iv);
861 // It is safe to store ValueRange args because it points to block
862 // arguments of a loop operation that we also own.
863 currentIterArgs = args;
864 currentLoc = nestedLoc;
865 });
866 // Set the builder to point to the body of the newly created loop. We don't
867 // do this in the callback because the builder is reset when the callback
868 // returns.
869 builder.setInsertionPointToStart(loop.getBody());
870 loops.push_back(Elt: loop);
871 }
872
873 // For all loops but the innermost, yield the results of the nested loop.
874 for (unsigned i = 0, e = loops.size() - 1; i < e; ++i) {
875 builder.setInsertionPointToEnd(loops[i].getBody());
876 scf::YieldOp::create(builder, location: loc, results: loops[i + 1].getResults());
877 }
878
879 // In the body of the innermost loop, call the body building function if any
880 // and yield its results.
881 builder.setInsertionPointToStart(loops.back().getBody());
882 ValueVector results = bodyBuilder
883 ? bodyBuilder(builder, currentLoc, ivs,
884 loops.back().getRegionIterArgs())
885 : ValueVector();
886 assert(results.size() == iterArgs.size() &&
887 "loop nest body must return as many values as loop has iteration "
888 "arguments");
889 builder.setInsertionPointToEnd(loops.back().getBody());
890 scf::YieldOp::create(builder, location: loc, results);
891
892 // Return the loops.
893 ValueVector nestResults;
894 llvm::append_range(C&: nestResults, R: loops.front().getResults());
895 return LoopNest{.loops: std::move(loops), .results: std::move(nestResults)};
896}
897
898LoopNest mlir::scf::buildLoopNest(
899 OpBuilder &builder, Location loc, ValueRange lbs, ValueRange ubs,
900 ValueRange steps,
901 function_ref<void(OpBuilder &, Location, ValueRange)> bodyBuilder) {
902 // Delegate to the main function by wrapping the body builder.
903 return buildLoopNest(builder, loc, lbs, ubs, steps, iterArgs: {},
904 bodyBuilder: [&bodyBuilder](OpBuilder &nestedBuilder,
905 Location nestedLoc, ValueRange ivs,
906 ValueRange) -> ValueVector {
907 if (bodyBuilder)
908 bodyBuilder(nestedBuilder, nestedLoc, ivs);
909 return {};
910 });
911}
912
913SmallVector<Value>
914mlir::scf::replaceAndCastForOpIterArg(RewriterBase &rewriter, scf::ForOp forOp,
915 OpOperand &operand, Value replacement,
916 const ValueTypeCastFnTy &castFn) {
917 assert(operand.getOwner() == forOp);
918 Type oldType = operand.get().getType(), newType = replacement.getType();
919
920 // 1. Create new iter operands, exactly 1 is replaced.
921 assert(operand.getOperandNumber() >= forOp.getNumControlOperands() &&
922 "expected an iter OpOperand");
923 assert(operand.get().getType() != replacement.getType() &&
924 "Expected a different type");
925 SmallVector<Value> newIterOperands;
926 for (OpOperand &opOperand : forOp.getInitArgsMutable()) {
927 if (opOperand.getOperandNumber() == operand.getOperandNumber()) {
928 newIterOperands.push_back(Elt: replacement);
929 continue;
930 }
931 newIterOperands.push_back(Elt: opOperand.get());
932 }
933
934 // 2. Create the new forOp shell.
935 scf::ForOp newForOp = scf::ForOp::create(
936 builder&: rewriter, location: forOp.getLoc(), lowerBound: forOp.getLowerBound(), upperBound: forOp.getUpperBound(),
937 step: forOp.getStep(), initArgs: newIterOperands, /*bodyBuilder=*/odsArg4: nullptr,
938 unsignedCmp: forOp.getUnsignedCmp());
939 newForOp->setDiscardableAttrs(
940 forOp->getDiscardableAttrDictionary().getValue());
941 Block &newBlock = newForOp.getRegion().front();
942 SmallVector<Value, 4> newBlockTransferArgs(newBlock.getArguments().begin(),
943 newBlock.getArguments().end());
944
945 // 3. Inject an incoming cast op at the beginning of the block for the bbArg
946 // corresponding to the `replacement` value.
947 OpBuilder::InsertionGuard g(rewriter);
948 rewriter.setInsertionPointToStart(&newBlock);
949 BlockArgument newRegionIterArg = newForOp.getTiedLoopRegionIterArg(
950 opOperand: &newForOp->getOpOperand(idx: operand.getOperandNumber()));
951 Value castIn = castFn(rewriter, newForOp.getLoc(), oldType, newRegionIterArg);
952 newBlockTransferArgs[newRegionIterArg.getArgNumber()] = castIn;
953
954 // 4. Steal the old block ops, mapping to the newBlockTransferArgs.
955 Block &oldBlock = forOp.getRegion().front();
956 rewriter.mergeBlocks(source: &oldBlock, dest: &newBlock, argValues: newBlockTransferArgs);
957
958 // 5. Inject an outgoing cast op at the end of the block and yield it instead.
959 auto clonedYieldOp = cast<scf::YieldOp>(Val: newBlock.getTerminator());
960 rewriter.setInsertionPoint(clonedYieldOp);
961 unsigned yieldIdx =
962 newRegionIterArg.getArgNumber() - forOp.getNumInductionVars();
963 Value castOut = castFn(rewriter, newForOp.getLoc(), newType,
964 clonedYieldOp.getOperand(i: yieldIdx));
965 SmallVector<Value> newYieldOperands = clonedYieldOp.getOperands();
966 newYieldOperands[yieldIdx] = castOut;
967 scf::YieldOp::create(builder&: rewriter, location: newForOp.getLoc(), results: newYieldOperands);
968 rewriter.eraseOp(op: clonedYieldOp);
969
970 // 6. Inject an outgoing cast op after the forOp.
971 rewriter.setInsertionPointAfter(newForOp);
972 SmallVector<Value> newResults = newForOp.getResults();
973 newResults[yieldIdx] =
974 castFn(rewriter, newForOp.getLoc(), oldType, newResults[yieldIdx]);
975
976 return newResults;
977}
978
979bool mlir::scf::isShapePreserving(ForOp forOp, int64_t arg) {
980 assert(arg < static_cast<int64_t>(forOp.getNumResults()) &&
981 "arg is out of bounds");
982 Value value = forOp.getYieldedValues()[arg];
983 while (value) {
984 if (value == forOp.getRegionIterArgs()[arg])
985 return true;
986 OpResult opResult = dyn_cast<OpResult>(Val&: value);
987 if (!opResult)
988 return false;
989
990 value = llvm::TypeSwitch<Operation *, Value>(opResult.getOwner())
991 .Case(caseFn: [&](DestinationStyleOpInterface op) {
992 return op.getTiedOpOperand(opResult)->get();
993 })
994 .Case(caseFn: [&](ForOp forOp) {
995 return isShapePreserving(forOp, arg: opResult.getResultNumber())
996 ? forOp.getInitArgs()[opResult.getResultNumber()]
997 : Value();
998 })
999 .Default(nullptr);
1000 }
1001 return false;
1002}
1003
1004namespace {
1005/// Fold scf.for iter_arg/result pairs that go through incoming/ougoing
1006/// a tensor.cast op pair so as to pull the tensor.cast inside the scf.for:
1007///
1008/// ```
1009/// %0 = tensor.cast %t0 : tensor<32x1024xf32> to tensor<?x?xf32>
1010/// %1 = scf.for %i = %c0 to %c1024 step %c32 iter_args(%iter_t0 = %0)
1011/// -> (tensor<?x?xf32>) {
1012/// %2 = call @do(%iter_t0) : (tensor<?x?xf32>) -> tensor<32x1024xf32>
1013/// %3 = tensor.cast %2 : tensor<32x1024xf32> to tensor<?x?xf32>
1014/// scf.yield %3 : tensor<?x?xf32>
1015/// }
1016/// use_of(%1)
1017/// ```
1018///
1019/// folds into:
1020///
1021/// ```
1022/// %0 = scf.for %arg2 = %c0 to %c1024 step %c32 iter_args(%arg3 = %arg0)
1023/// -> (tensor<32x1024xf32>) {
1024/// %2 = tensor.cast %arg3 : tensor<32x1024xf32> to tensor<?x?xf32>
1025/// %3 = call @do(%2) : (tensor<?x?xf32>) -> tensor<32x1024xf32>
1026/// scf.yield %3 : tensor<32x1024xf32>
1027/// }
1028/// %1 = tensor.cast %0 : tensor<32x1024xf32> to tensor<?x?xf32>
1029/// use_of(%1)
1030/// ```
1031struct ForOpTensorCastFolder : public OpRewritePattern<ForOp> {
1032 using OpRewritePattern<ForOp>::OpRewritePattern;
1033
1034 LogicalResult matchAndRewrite(ForOp op,
1035 PatternRewriter &rewriter) const override {
1036 for (auto it : llvm::zip(t: op.getInitArgsMutable(), u: op.getResults())) {
1037 OpOperand &iterOpOperand = std::get<0>(t&: it);
1038 auto incomingCast = iterOpOperand.get().getDefiningOp<tensor::CastOp>();
1039 if (!incomingCast ||
1040 incomingCast.getSource().getType() == incomingCast.getType())
1041 continue;
1042 // If the dest type of the cast does not preserve static information in
1043 // the source type.
1044 if (!tensor::preservesStaticInformation(
1045 source: incomingCast.getDest().getType(),
1046 target: incomingCast.getSource().getType()))
1047 continue;
1048 if (!std::get<1>(t&: it).hasOneUse())
1049 continue;
1050 // The fold casts the yielded value to the cast's source type, which is
1051 // only valid if every iteration yields a value of that type. A dynamic
1052 // dimension of that type stays dynamic, so its size may still change
1053 // between iterations; only the static sizes are asserted.
1054 int64_t resultNumber = std::get<1>(t&: it).getResultNumber();
1055 auto yieldedCast =
1056 op.getYieldedValues()[resultNumber].getDefiningOp<tensor::CastOp>();
1057 bool yieldsStaticType =
1058 yieldedCast && yieldedCast.getSource().getType() ==
1059 incomingCast.getSource().getType();
1060 if (!yieldsStaticType && !isShapePreserving(forOp: op, arg: resultNumber))
1061 continue;
1062
1063 // Create a new ForOp with that iter operand replaced.
1064 rewriter.replaceOp(
1065 op, newValues: replaceAndCastForOpIterArg(
1066 rewriter, forOp: op, operand&: iterOpOperand, replacement: incomingCast.getSource(),
1067 castFn: [](OpBuilder &b, Location loc, Type type, Value source) {
1068 return tensor::CastOp::create(builder&: b, location: loc, dest: type, source);
1069 }));
1070 return success();
1071 }
1072 return failure();
1073 }
1074};
1075} // namespace
1076
1077void ForOp::getCanonicalizationPatterns(RewritePatternSet &results,
1078 MLIRContext *context) {
1079 results.add<ForOpTensorCastFolder>(arg&: context);
1080 populateRegionBranchOpInterfaceCanonicalizationPatterns(
1081 patterns&: results, opName: ForOp::getOperationName());
1082 // Inline single-iteration loops before applying the generic region branch op
1083 // canonicalizations, which may otherwise remove tied iter_args and results
1084 // independently.
1085 populateRegionBranchOpInterfaceInliningPattern(
1086 patterns&: results, opName: ForOp::getOperationName(),
1087 /*replBuilderFn=*/
1088 [](OpBuilder &builder, Location loc, Value value) {
1089 // scf.for has only one non-successor input value: the loop induction
1090 // variable. In case of a single acyclic path through the op, the IV can
1091 // be safely replaced with the lower bound.
1092 auto blockArg = cast<BlockArgument>(Val&: value);
1093 assert(blockArg.getArgNumber() == 0 && "expected induction variable");
1094 auto forOp = cast<ForOp>(Val: blockArg.getOwner()->getParentOp());
1095 return forOp.getLowerBound();
1096 },
1097 /*matcherFn=*/::mlir::detail::defaultMatcherFn,
1098 /*benefit=*/2);
1099}
1100
1101std::optional<APInt> ForOp::getConstantStep() {
1102 IntegerAttr step;
1103 if (matchPattern(value: getStep(), pattern: m_Constant(bind_value: &step)))
1104 return step.getValue();
1105 return {};
1106}
1107
1108std::optional<MutableArrayRef<OpOperand>> ForOp::getYieldedValuesMutable() {
1109 return cast<scf::YieldOp>(Val: getBody()->getTerminator()).getResultsMutable();
1110}
1111
1112Speculation::Speculatability ForOp::getSpeculatability() {
1113 // `scf.for (I = Start; I < End; I += 1)` terminates for all values of Start
1114 // and End.
1115 if (auto constantStep = getConstantStep())
1116 if (*constantStep == 1)
1117 return Speculation::RecursivelySpeculatable;
1118
1119 // For Step != 1, the loop may not terminate. We can add more smarts here if
1120 // needed.
1121 return Speculation::NotSpeculatable;
1122}
1123
1124std::optional<APInt> ForOp::getStaticTripCount() {
1125 return constantTripCount(lb: getLowerBound(), ub: getUpperBound(), step: getStep(),
1126 /*isSigned=*/!getUnsignedCmp(), computeUbMinusLb);
1127}
1128
1129//===----------------------------------------------------------------------===//
1130// ForallOp
1131//===----------------------------------------------------------------------===//
1132
1133LogicalResult ForallOp::verify() {
1134 unsigned numLoops = getRank();
1135 // Check number of outputs.
1136 if (getNumResults() != getOutputs().size())
1137 return emitOpError(message: "produces ")
1138 << getNumResults() << " results, but has only "
1139 << getOutputs().size() << " outputs";
1140
1141 // Check that the body defines block arguments for thread indices and outputs.
1142 auto *body = getBody();
1143 if (body->getNumArguments() != numLoops + getOutputs().size())
1144 return emitOpError(message: "region expects ") << numLoops << " arguments";
1145 for (int64_t i = 0; i < numLoops; ++i)
1146 if (!body->getArgument(i).getType().isIndex())
1147 return emitOpError(message: "expects ")
1148 << i << "-th block argument to be an index";
1149 for (unsigned i = 0; i < getOutputs().size(); ++i)
1150 if (body->getArgument(i: i + numLoops).getType() != getOutputs()[i].getType())
1151 return emitOpError(message: "type mismatch between ")
1152 << i << "-th output and corresponding block argument";
1153 if (getMapping().has_value() && !getMapping()->empty()) {
1154 if (getDeviceMappingAttrs().size() != numLoops)
1155 return emitOpError() << "mapping attribute size must match op rank";
1156 if (failed(Result: getDeviceMaskingAttr()))
1157 return emitOpError() << getMappingAttrName()
1158 << " supports at most one device masking attribute";
1159 }
1160
1161 // Verify mixed static/dynamic control variables.
1162 Operation *op = getOperation();
1163 if (failed(Result: verifyListOfOperandsOrIntegers(op, name: "lower bound", expectedNumElements: numLoops,
1164 attr: getStaticLowerBound(),
1165 values: getDynamicLowerBound())))
1166 return failure();
1167 if (failed(Result: verifyListOfOperandsOrIntegers(op, name: "upper bound", expectedNumElements: numLoops,
1168 attr: getStaticUpperBound(),
1169 values: getDynamicUpperBound())))
1170 return failure();
1171 if (failed(Result: verifyListOfOperandsOrIntegers(op, name: "step", expectedNumElements: numLoops,
1172 attr: getStaticStep(), values: getDynamicStep())))
1173 return failure();
1174
1175 return success();
1176}
1177
1178void ForallOp::print(OpAsmPrinter &p) {
1179 Operation *op = getOperation();
1180 p << " (" << getInductionVars();
1181 if (isNormalized()) {
1182 p << ") in ";
1183 printDynamicIndexList(printer&: p, op, values: getDynamicUpperBound(), integers: getStaticUpperBound(),
1184 /*valueTypes=*/scalableFlags: {}, /*scalables=*/valueTypes: {},
1185 delimiter: OpAsmParser::Delimiter::Paren);
1186 } else {
1187 p << ") = ";
1188 printDynamicIndexList(printer&: p, op, values: getDynamicLowerBound(), integers: getStaticLowerBound(),
1189 /*valueTypes=*/scalableFlags: {}, /*scalables=*/valueTypes: {},
1190 delimiter: OpAsmParser::Delimiter::Paren);
1191 p << " to ";
1192 printDynamicIndexList(printer&: p, op, values: getDynamicUpperBound(), integers: getStaticUpperBound(),
1193 /*valueTypes=*/scalableFlags: {}, /*scalables=*/valueTypes: {},
1194 delimiter: OpAsmParser::Delimiter::Paren);
1195 p << " step ";
1196 printDynamicIndexList(printer&: p, op, values: getDynamicStep(), integers: getStaticStep(),
1197 /*valueTypes=*/scalableFlags: {}, /*scalables=*/valueTypes: {},
1198 delimiter: OpAsmParser::Delimiter::Paren);
1199 }
1200 printInitializationList(p, blocksArgs: getRegionOutArgs(), initializers: getOutputs(), prefix: " shared_outs");
1201 p << " ";
1202 if (!getRegionOutArgs().empty())
1203 p << "-> (" << getResultTypes() << ") ";
1204 p.printRegion(blocks&: getRegion(),
1205 /*printEntryBlockArgs=*/false,
1206 /*printBlockTerminators=*/getNumResults() > 0);
1207 SmallVector<NamedAttribute> attrs(op->getDiscardableAttrs());
1208 if (ArrayAttr mapping = getMappingAttr())
1209 attrs.emplace_back(Args: getMappingAttrName(), Args&: mapping);
1210 llvm::sort(C&: attrs);
1211 p.printOptionalAttrDict(attrs);
1212}
1213
1214ParseResult ForallOp::parse(OpAsmParser &parser, OperationState &result) {
1215 OpBuilder b(parser.getContext());
1216 auto indexType = b.getIndexType();
1217
1218 // Parse an opening `(` followed by thread index variables followed by `)`
1219 // TODO: when we can refer to such "induction variable"-like handles from the
1220 // declarative assembly format, we can implement the parser as a custom hook.
1221 SmallVector<OpAsmParser::Argument, 4> ivs;
1222 if (parser.parseArgumentList(result&: ivs, delimiter: OpAsmParser::Delimiter::Paren))
1223 return failure();
1224
1225 DenseI64ArrayAttr staticLbs, staticUbs, staticSteps;
1226 SmallVector<OpAsmParser::UnresolvedOperand> dynamicLbs, dynamicUbs,
1227 dynamicSteps;
1228 if (succeeded(Result: parser.parseOptionalKeyword(keyword: "in"))) {
1229 // Parse upper bounds.
1230 if (parseDynamicIndexList(parser, values&: dynamicUbs, integers&: staticUbs,
1231 /*valueTypes=*/nullptr,
1232 delimiter: OpAsmParser::Delimiter::Paren) ||
1233 parser.resolveOperands(operands&: dynamicUbs, type: indexType, result&: result.operands))
1234 return failure();
1235
1236 unsigned numLoops = ivs.size();
1237 staticLbs = b.getDenseI64ArrayAttr(values: SmallVector<int64_t>(numLoops, 0));
1238 staticSteps = b.getDenseI64ArrayAttr(values: SmallVector<int64_t>(numLoops, 1));
1239 } else {
1240 // Parse lower bounds.
1241 if (parser.parseEqual() ||
1242 parseDynamicIndexList(parser, values&: dynamicLbs, integers&: staticLbs,
1243 /*valueTypes=*/nullptr,
1244 delimiter: OpAsmParser::Delimiter::Paren) ||
1245
1246 parser.resolveOperands(operands&: dynamicLbs, type: indexType, result&: result.operands))
1247 return failure();
1248
1249 // Parse upper bounds.
1250 if (parser.parseKeyword(keyword: "to") ||
1251 parseDynamicIndexList(parser, values&: dynamicUbs, integers&: staticUbs,
1252 /*valueTypes=*/nullptr,
1253 delimiter: OpAsmParser::Delimiter::Paren) ||
1254 parser.resolveOperands(operands&: dynamicUbs, type: indexType, result&: result.operands))
1255 return failure();
1256
1257 // Parse step values.
1258 if (parser.parseKeyword(keyword: "step") ||
1259 parseDynamicIndexList(parser, values&: dynamicSteps, integers&: staticSteps,
1260 /*valueTypes=*/nullptr,
1261 delimiter: OpAsmParser::Delimiter::Paren) ||
1262 parser.resolveOperands(operands&: dynamicSteps, type: indexType, result&: result.operands))
1263 return failure();
1264 }
1265
1266 // Parse out operands and results.
1267 SmallVector<OpAsmParser::Argument, 4> regionOutArgs;
1268 SmallVector<OpAsmParser::UnresolvedOperand, 4> outOperands;
1269 SMLoc outOperandsLoc = parser.getCurrentLocation();
1270 if (succeeded(Result: parser.parseOptionalKeyword(keyword: "shared_outs"))) {
1271 if (outOperands.size() != result.types.size())
1272 return parser.emitError(loc: outOperandsLoc,
1273 message: "mismatch between out operands and types");
1274 if (parser.parseAssignmentList(lhs&: regionOutArgs, rhs&: outOperands) ||
1275 parser.parseOptionalArrowTypeList(result&: result.types) ||
1276 parser.resolveOperands(operands&: outOperands, types&: result.types, loc: outOperandsLoc,
1277 result&: result.operands))
1278 return failure();
1279 }
1280
1281 // Parse region.
1282 SmallVector<OpAsmParser::Argument, 4> regionArgs;
1283 std::unique_ptr<Region> region = std::make_unique<Region>();
1284 for (auto &iv : ivs) {
1285 iv.type = b.getIndexType();
1286 regionArgs.push_back(Elt: iv);
1287 }
1288 for (const auto &it : llvm::enumerate(First&: regionOutArgs)) {
1289 auto &out = it.value();
1290 out.type = result.types[it.index()];
1291 regionArgs.push_back(Elt: out);
1292 }
1293 if (parser.parseRegion(region&: *region, arguments: regionArgs))
1294 return failure();
1295
1296 // Ensure terminator and move region.
1297 ForallOp::ensureTerminator(region&: *region, builder&: b, loc: result.location);
1298 result.addRegion(region: std::move(region));
1299
1300 // Parse the optional attribute list.
1301 if (parser.parseOptionalAttrDict(result&: result.attributes))
1302 return failure();
1303
1304 result.addAttribute(name: "staticLowerBound", attr: staticLbs);
1305 result.addAttribute(name: "staticUpperBound", attr: staticUbs);
1306 result.addAttribute(name: "staticStep", attr: staticSteps);
1307 result.addAttribute(name: "operandSegmentSizes",
1308 attr: parser.getBuilder().getDenseI32ArrayAttr(
1309 values: {static_cast<int32_t>(dynamicLbs.size()),
1310 static_cast<int32_t>(dynamicUbs.size()),
1311 static_cast<int32_t>(dynamicSteps.size()),
1312 static_cast<int32_t>(outOperands.size())}));
1313 return success();
1314}
1315
1316// Builder that takes loop bounds.
1317void ForallOp::build(
1318 mlir::OpBuilder &b, mlir::OperationState &result,
1319 ArrayRef<OpFoldResult> lbs, ArrayRef<OpFoldResult> ubs,
1320 ArrayRef<OpFoldResult> steps, ValueRange outputs,
1321 std::optional<ArrayAttr> mapping,
1322 function_ref<void(OpBuilder &, Location, ValueRange)> bodyBuilderFn) {
1323 SmallVector<int64_t> staticLbs, staticUbs, staticSteps;
1324 SmallVector<Value> dynamicLbs, dynamicUbs, dynamicSteps;
1325 dispatchIndexOpFoldResults(ofrs: lbs, dynamicVec&: dynamicLbs, staticVec&: staticLbs);
1326 dispatchIndexOpFoldResults(ofrs: ubs, dynamicVec&: dynamicUbs, staticVec&: staticUbs);
1327 dispatchIndexOpFoldResults(ofrs: steps, dynamicVec&: dynamicSteps, staticVec&: staticSteps);
1328
1329 result.addOperands(newOperands: dynamicLbs);
1330 result.addOperands(newOperands: dynamicUbs);
1331 result.addOperands(newOperands: dynamicSteps);
1332 result.addOperands(newOperands: outputs);
1333 result.addTypes(newTypes: TypeRange(outputs));
1334
1335 result.addAttribute(name: getStaticLowerBoundAttrName(name: result.name),
1336 attr: b.getDenseI64ArrayAttr(values: staticLbs));
1337 result.addAttribute(name: getStaticUpperBoundAttrName(name: result.name),
1338 attr: b.getDenseI64ArrayAttr(values: staticUbs));
1339 result.addAttribute(name: getStaticStepAttrName(name: result.name),
1340 attr: b.getDenseI64ArrayAttr(values: staticSteps));
1341 result.addAttribute(
1342 name: "operandSegmentSizes",
1343 attr: b.getDenseI32ArrayAttr(values: {static_cast<int32_t>(dynamicLbs.size()),
1344 static_cast<int32_t>(dynamicUbs.size()),
1345 static_cast<int32_t>(dynamicSteps.size()),
1346 static_cast<int32_t>(outputs.size())}));
1347 if (mapping.has_value()) {
1348 result.addAttribute(name: ForallOp::getMappingAttrName(name: result.name),
1349 attr: mapping.value());
1350 }
1351
1352 Region *bodyRegion = result.addRegion();
1353 OpBuilder::InsertionGuard g(b);
1354 b.createBlock(parent: bodyRegion);
1355 Block &bodyBlock = bodyRegion->front();
1356
1357 // Add block arguments for indices and outputs.
1358 bodyBlock.addArguments(
1359 types: SmallVector<Type>(lbs.size(), b.getIndexType()),
1360 locs: SmallVector<Location>(staticLbs.size(), result.location));
1361 bodyBlock.addArguments(
1362 types: TypeRange(outputs),
1363 locs: SmallVector<Location>(outputs.size(), result.location));
1364
1365 b.setInsertionPointToStart(&bodyBlock);
1366 if (!bodyBuilderFn) {
1367 ForallOp::ensureTerminator(region&: *bodyRegion, builder&: b, loc: result.location);
1368 return;
1369 }
1370 bodyBuilderFn(b, result.location, bodyBlock.getArguments());
1371}
1372
1373// Builder that takes loop bounds.
1374void ForallOp::build(
1375 mlir::OpBuilder &b, mlir::OperationState &result,
1376 ArrayRef<OpFoldResult> ubs, ValueRange outputs,
1377 std::optional<ArrayAttr> mapping,
1378 function_ref<void(OpBuilder &, Location, ValueRange)> bodyBuilderFn) {
1379 unsigned numLoops = ubs.size();
1380 SmallVector<OpFoldResult> lbs(numLoops, b.getIndexAttr(value: 0));
1381 SmallVector<OpFoldResult> steps(numLoops, b.getIndexAttr(value: 1));
1382 build(b, result, lbs, ubs, steps, outputs, mapping, bodyBuilderFn);
1383}
1384
1385// Checks if the lbs are zeros and steps are ones.
1386bool ForallOp::isNormalized() {
1387 auto allEqual = [](ArrayRef<OpFoldResult> results, int64_t val) {
1388 return llvm::all_of(Range&: results, P: [&](OpFoldResult ofr) {
1389 auto intValue = getConstantIntValue(ofr);
1390 return intValue.has_value() && intValue == val;
1391 });
1392 };
1393 return allEqual(getMixedLowerBound(), 0) && allEqual(getMixedStep(), 1);
1394}
1395
1396InParallelOp ForallOp::getTerminator() {
1397 return cast<InParallelOp>(Val: getBody()->getTerminator());
1398}
1399
1400SmallVector<Operation *> ForallOp::getCombiningOps(BlockArgument bbArg) {
1401 SmallVector<Operation *> storeOps;
1402 for (Operation *user : bbArg.getUsers()) {
1403 if (auto parallelOp = dyn_cast<ParallelCombiningOpInterface>(Val: user)) {
1404 storeOps.push_back(Elt: parallelOp);
1405 }
1406 }
1407 return storeOps;
1408}
1409
1410SmallVector<DeviceMappingAttrInterface> ForallOp::getDeviceMappingAttrs() {
1411 SmallVector<DeviceMappingAttrInterface> res;
1412 if (!getMapping())
1413 return res;
1414 for (auto attr : getMapping()->getValue()) {
1415 auto m = dyn_cast<DeviceMappingAttrInterface>(Val&: attr);
1416 if (m)
1417 res.push_back(Elt: m);
1418 }
1419 return res;
1420}
1421
1422FailureOr<DeviceMaskingAttrInterface> ForallOp::getDeviceMaskingAttr() {
1423 DeviceMaskingAttrInterface res;
1424 if (!getMapping())
1425 return res;
1426 for (auto attr : getMapping()->getValue()) {
1427 auto m = dyn_cast<DeviceMaskingAttrInterface>(Val&: attr);
1428 if (m && res)
1429 return failure();
1430 if (m)
1431 res = m;
1432 }
1433 return res;
1434}
1435
1436bool ForallOp::usesLinearMapping() {
1437 SmallVector<DeviceMappingAttrInterface> ifaces = getDeviceMappingAttrs();
1438 if (ifaces.empty())
1439 return false;
1440 return ifaces.front().isLinearMapping();
1441}
1442
1443std::optional<SmallVector<Value>> ForallOp::getLoopInductionVars() {
1444 return SmallVector<Value>{getBody()->getArguments().take_front(N: getRank())};
1445}
1446
1447// Get lower bounds as OpFoldResult.
1448std::optional<SmallVector<OpFoldResult>> ForallOp::getLoopLowerBounds() {
1449 Builder b(getOperation()->getContext());
1450 return getMixedValues(staticValues: getStaticLowerBound(), dynamicValues: getDynamicLowerBound(), b);
1451}
1452
1453// Get upper bounds as OpFoldResult.
1454std::optional<SmallVector<OpFoldResult>> ForallOp::getLoopUpperBounds() {
1455 Builder b(getOperation()->getContext());
1456 return getMixedValues(staticValues: getStaticUpperBound(), dynamicValues: getDynamicUpperBound(), b);
1457}
1458
1459// Get steps as OpFoldResult.
1460std::optional<SmallVector<OpFoldResult>> ForallOp::getLoopSteps() {
1461 Builder b(getOperation()->getContext());
1462 return getMixedValues(staticValues: getStaticStep(), dynamicValues: getDynamicStep(), b);
1463}
1464
1465ForallOp mlir::scf::getForallOpThreadIndexOwner(Value val) {
1466 auto tidxArg = llvm::dyn_cast<BlockArgument>(Val&: val);
1467 if (!tidxArg)
1468 return ForallOp();
1469 assert(tidxArg.getOwner() && "unlinked block argument");
1470 auto *containingOp = tidxArg.getOwner()->getParentOp();
1471 return dyn_cast<ForallOp>(Val: containingOp);
1472}
1473
1474namespace {
1475/// Fold tensor.dim(forall shared_outs(... = %t)) to tensor.dim(%t).
1476struct DimOfForallOp : public OpRewritePattern<tensor::DimOp> {
1477 using OpRewritePattern<tensor::DimOp>::OpRewritePattern;
1478
1479 LogicalResult matchAndRewrite(tensor::DimOp dimOp,
1480 PatternRewriter &rewriter) const final {
1481 auto forallOp = dimOp.getSource().getDefiningOp<ForallOp>();
1482 if (!forallOp)
1483 return failure();
1484 Value sharedOut =
1485 forallOp.getTiedOpOperand(opResult: llvm::cast<OpResult>(Val: dimOp.getSource()))
1486 ->get();
1487 rewriter.modifyOpInPlace(
1488 root: dimOp, callable: [&]() { dimOp.getSourceMutable().assign(value: sharedOut); });
1489 return success();
1490 }
1491};
1492
1493class ForallOpControlOperandsFolder : public OpRewritePattern<ForallOp> {
1494public:
1495 using OpRewritePattern<ForallOp>::OpRewritePattern;
1496
1497 LogicalResult matchAndRewrite(ForallOp op,
1498 PatternRewriter &rewriter) const override {
1499 SmallVector<OpFoldResult> mixedLowerBound(op.getMixedLowerBound());
1500 SmallVector<OpFoldResult> mixedUpperBound(op.getMixedUpperBound());
1501 SmallVector<OpFoldResult> mixedStep(op.getMixedStep());
1502 if (failed(Result: foldDynamicIndexList(ofrs&: mixedLowerBound)) &&
1503 failed(Result: foldDynamicIndexList(ofrs&: mixedUpperBound)) &&
1504 failed(Result: foldDynamicIndexList(ofrs&: mixedStep)))
1505 return failure();
1506
1507 rewriter.modifyOpInPlace(root: op, callable: [&]() {
1508 SmallVector<Value> dynamicLowerBound, dynamicUpperBound, dynamicStep;
1509 SmallVector<int64_t> staticLowerBound, staticUpperBound, staticStep;
1510 dispatchIndexOpFoldResults(ofrs: mixedLowerBound, dynamicVec&: dynamicLowerBound,
1511 staticVec&: staticLowerBound);
1512 op.getDynamicLowerBoundMutable().assign(values: dynamicLowerBound);
1513 op.setStaticLowerBound(staticLowerBound);
1514
1515 dispatchIndexOpFoldResults(ofrs: mixedUpperBound, dynamicVec&: dynamicUpperBound,
1516 staticVec&: staticUpperBound);
1517 op.getDynamicUpperBoundMutable().assign(values: dynamicUpperBound);
1518 op.setStaticUpperBound(staticUpperBound);
1519
1520 dispatchIndexOpFoldResults(ofrs: mixedStep, dynamicVec&: dynamicStep, staticVec&: staticStep);
1521 op.getDynamicStepMutable().assign(values: dynamicStep);
1522 op.setStaticStep(staticStep);
1523
1524 op->setInherentAttr(
1525 name: rewriter.getStringAttr(bytes: ForallOp::getOperandSegmentSizeAttr()),
1526 value: rewriter.getDenseI32ArrayAttr(
1527 values: {static_cast<int32_t>(dynamicLowerBound.size()),
1528 static_cast<int32_t>(dynamicUpperBound.size()),
1529 static_cast<int32_t>(dynamicStep.size()),
1530 static_cast<int32_t>(op.getNumResults())}));
1531 });
1532 return success();
1533 }
1534};
1535
1536/// The following canonicalization pattern folds the iter arguments of
1537/// scf.forall op if :-
1538/// 1. The corresponding result has zero uses.
1539/// 2. The iter argument is NOT being modified within the loop body.
1540/// uses.
1541///
1542/// Example of first case :-
1543/// INPUT:
1544/// %res:3 = scf.forall ... shared_outs(%arg0 = %a, %arg1 = %b, %arg2 = %c)
1545/// {
1546/// ...
1547/// <SOME USE OF %arg0>
1548/// <SOME USE OF %arg1>
1549/// <SOME USE OF %arg2>
1550/// ...
1551/// scf.forall.in_parallel {
1552/// <STORE OP WITH DESTINATION %arg1>
1553/// <STORE OP WITH DESTINATION %arg0>
1554/// <STORE OP WITH DESTINATION %arg2>
1555/// }
1556/// }
1557/// return %res#1
1558///
1559/// OUTPUT:
1560/// %res:3 = scf.forall ... shared_outs(%new_arg0 = %b)
1561/// {
1562/// ...
1563/// <SOME USE OF %a>
1564/// <SOME USE OF %new_arg0>
1565/// <SOME USE OF %c>
1566/// ...
1567/// scf.forall.in_parallel {
1568/// <STORE OP WITH DESTINATION %new_arg0>
1569/// }
1570/// }
1571/// return %res
1572///
1573/// NOTE: 1. All uses of the folded shared_outs (iter argument) within the
1574/// scf.forall is replaced by their corresponding operands.
1575/// 2. Even if there are <STORE OP WITH DESTINATION *> ops within the body
1576/// of the scf.forall besides within scf.forall.in_parallel terminator,
1577/// this canonicalization remains valid. For more details, please refer
1578/// to :
1579/// https://github.com/llvm/llvm-project/pull/90189#discussion_r1589011124
1580/// 3. TODO(avarma): Generalize it for other store ops. Currently it
1581/// handles tensor.parallel_insert_slice ops only.
1582///
1583/// Example of second case :-
1584/// INPUT:
1585/// %res:2 = scf.forall ... shared_outs(%arg0 = %a, %arg1 = %b)
1586/// {
1587/// ...
1588/// <SOME USE OF %arg0>
1589/// <SOME USE OF %arg1>
1590/// ...
1591/// scf.forall.in_parallel {
1592/// <STORE OP WITH DESTINATION %arg1>
1593/// }
1594/// }
1595/// return %res#0, %res#1
1596///
1597/// OUTPUT:
1598/// %res = scf.forall ... shared_outs(%new_arg0 = %b)
1599/// {
1600/// ...
1601/// <SOME USE OF %a>
1602/// <SOME USE OF %new_arg0>
1603/// ...
1604/// scf.forall.in_parallel {
1605/// <STORE OP WITH DESTINATION %new_arg0>
1606/// }
1607/// }
1608/// return %a, %res
1609struct ForallOpIterArgsFolder : public OpRewritePattern<ForallOp> {
1610 using OpRewritePattern<ForallOp>::OpRewritePattern;
1611
1612 LogicalResult matchAndRewrite(ForallOp forallOp,
1613 PatternRewriter &rewriter) const final {
1614 // Step 1: For a given i-th result of scf.forall, check the following :-
1615 // a. If it has any use.
1616 // b. If the corresponding iter argument is being modified within
1617 // the loop, i.e. has at least one store op with the iter arg as
1618 // its destination operand. For this we use
1619 // ForallOp::getCombiningOps(iter_arg).
1620 //
1621 // Based on the check we maintain the following :-
1622 // a. op results, block arguments, outputs to delete
1623 // b. new outputs (i.e., outputs to retain)
1624 SmallVector<Value> resultsToDelete;
1625 SmallVector<Value> outsToDelete;
1626 SmallVector<BlockArgument> blockArgsToDelete;
1627 SmallVector<Value> newOuts;
1628 BitVector resultIndicesToDelete(forallOp.getNumResults(), false);
1629 BitVector blockIndicesToDelete(forallOp.getBody()->getNumArguments(),
1630 false);
1631 for (OpResult result : forallOp.getResults()) {
1632 OpOperand *opOperand = forallOp.getTiedOpOperand(opResult: result);
1633 BlockArgument blockArg = forallOp.getTiedBlockArgument(opOperand);
1634 if (result.use_empty() || forallOp.getCombiningOps(bbArg: blockArg).empty()) {
1635 resultsToDelete.push_back(Elt: result);
1636 outsToDelete.push_back(Elt: opOperand->get());
1637 blockArgsToDelete.push_back(Elt: blockArg);
1638 resultIndicesToDelete[result.getResultNumber()] = true;
1639 blockIndicesToDelete[blockArg.getArgNumber()] = true;
1640 } else {
1641 newOuts.push_back(Elt: opOperand->get());
1642 }
1643 }
1644
1645 // Return early if all results of scf.forall have at least one use and being
1646 // modified within the loop.
1647 if (resultsToDelete.empty())
1648 return failure();
1649
1650 // Step 2: Erase combining ops and replace uses of deleted results and
1651 // block arguments with the corresponding outputs.
1652 for (auto blockArg : blockArgsToDelete) {
1653 SmallVector<Operation *> combiningOps =
1654 forallOp.getCombiningOps(bbArg: blockArg);
1655 for (Operation *combiningOp : combiningOps)
1656 rewriter.eraseOp(op: combiningOp);
1657 }
1658 for (auto [blockArg, result, out] :
1659 llvm::zip_equal(t&: blockArgsToDelete, u&: resultsToDelete, args&: outsToDelete)) {
1660 rewriter.replaceAllUsesWith(from: blockArg, to: out);
1661 rewriter.replaceAllUsesWith(from: result, to: out);
1662 }
1663 // TODO: There is no rewriter API for erasing block arguments.
1664 rewriter.modifyOpInPlace(root: forallOp, callable: [&]() {
1665 forallOp.getBody()->eraseArguments(eraseIndices: blockIndicesToDelete);
1666 });
1667
1668 // Step 3. Create a new scf.forall op with only the shared_outs/results
1669 // that should be retained.
1670 auto newForallOp = cast<scf::ForallOp>(
1671 Val: rewriter.eraseOpResults(op: forallOp, eraseIndices: resultIndicesToDelete));
1672 newForallOp.getOutputsMutable().assign(values: newOuts);
1673
1674 return success();
1675 }
1676};
1677
1678struct ForallOpSingleOrZeroIterationDimsFolder
1679 : public OpRewritePattern<ForallOp> {
1680 using OpRewritePattern<ForallOp>::OpRewritePattern;
1681
1682 LogicalResult matchAndRewrite(ForallOp op,
1683 PatternRewriter &rewriter) const override {
1684 // Do not fold dimensions if they are mapped to processing units.
1685 if (op.getMapping().has_value() && !op.getMapping()->empty())
1686 return failure();
1687 Location loc = op.getLoc();
1688
1689 // Compute new loop bounds that omit all single-iteration loop dimensions.
1690 SmallVector<OpFoldResult> newMixedLowerBounds, newMixedUpperBounds,
1691 newMixedSteps;
1692 SmallVector<std::pair<Value, OpFoldResult>> singleIterationIVs;
1693 for (auto [lb, ub, step, iv] :
1694 llvm::zip(t: op.getMixedLowerBound(), u: op.getMixedUpperBound(),
1695 args: op.getMixedStep(), args: op.getInductionVars())) {
1696 auto numIterations =
1697 constantTripCount(lb, ub, step, /*isSigned=*/true, computeUbMinusLb);
1698 if (numIterations.has_value()) {
1699 // Remove the loop if it performs zero iterations.
1700 if (*numIterations == 0) {
1701 rewriter.replaceOp(op, newValues: op.getOutputs());
1702 return success();
1703 }
1704 // Replace the loop induction variable by the lower bound if the loop
1705 // performs a single iteration. Otherwise, copy the loop bounds.
1706 if (*numIterations == 1) {
1707 singleIterationIVs.emplace_back(Args&: iv, Args&: lb);
1708 continue;
1709 }
1710 }
1711 newMixedLowerBounds.push_back(Elt: lb);
1712 newMixedUpperBounds.push_back(Elt: ub);
1713 newMixedSteps.push_back(Elt: step);
1714 }
1715
1716 // All of the loop dimensions perform a single iteration. Inline loop body.
1717 if (newMixedLowerBounds.empty())
1718 return promote(rewriter, forallOp: op);
1719
1720 // Exit if none of the loop dimensions perform a single iteration.
1721 if (newMixedLowerBounds.size() == static_cast<unsigned>(op.getRank())) {
1722 return rewriter.notifyMatchFailure(
1723 arg&: op, msg: "no dimensions have 0 or 1 iterations");
1724 }
1725
1726 // Materialize lower bounds only after all failure paths, including
1727 // promotion above, so that failed rewrites leave the IR unchanged.
1728 IRMapping mapping;
1729 for (auto [iv, lb] : singleIterationIVs)
1730 mapping.map(from: iv, to: getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: lb));
1731
1732 // Replace the loop by a lower-dimensional loop.
1733 ForallOp newOp;
1734 newOp = ForallOp::create(builder&: rewriter, location: loc, lbs: newMixedLowerBounds,
1735 ubs: newMixedUpperBounds, steps: newMixedSteps,
1736 outputs: op.getOutputs(), mapping: std::nullopt, bodyBuilderFn: nullptr);
1737 newOp.getBodyRegion().getBlocks().clear();
1738 newOp.setMappingAttr(op.getMappingAttr());
1739 newOp->setDiscardableAttrs(op->getDiscardableAttrDictionary());
1740 rewriter.cloneRegionBefore(region&: op.getRegion(), parent&: newOp.getRegion(),
1741 before: newOp.getRegion().begin(), mapping);
1742 rewriter.replaceOp(op, newValues: newOp.getResults());
1743 return success();
1744 }
1745};
1746
1747/// Replace all induction vars with a single trip count with their lower bound.
1748struct ForallOpReplaceConstantInductionVar : public OpRewritePattern<ForallOp> {
1749 using OpRewritePattern<ForallOp>::OpRewritePattern;
1750
1751 LogicalResult matchAndRewrite(ForallOp op,
1752 PatternRewriter &rewriter) const override {
1753 Location loc = op.getLoc();
1754 bool changed = false;
1755 for (auto [lb, ub, step, iv] :
1756 llvm::zip(t: op.getMixedLowerBound(), u: op.getMixedUpperBound(),
1757 args: op.getMixedStep(), args: op.getInductionVars())) {
1758 if (iv.hasNUses(n: 0))
1759 continue;
1760 auto numIterations =
1761 constantTripCount(lb, ub, step, /*isSigned=*/true, computeUbMinusLb);
1762 if (!numIterations.has_value() || numIterations.value() != 1) {
1763 continue;
1764 }
1765 rewriter.replaceAllUsesWith(
1766 from: iv, to: getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: lb));
1767 changed = true;
1768 }
1769 return success(IsSuccess: changed);
1770 }
1771};
1772
1773/// Replace a read of the init value of a shared_outs in the body with a read of
1774/// the tied block argument, when the read is a tensor.extract_slice of a tile
1775/// that the iteration also writes with a tensor.parallel_insert_slice. This
1776/// lets bufferization read and write the tile in place, without copying the
1777/// whole tensor.
1778///
1779/// Reads of other tiles are left alone, because other iterations may update
1780/// them in the block argument but not in the init value.
1781///
1782/// Example:
1783/// INPUT:
1784/// scf.forall (%i) ... shared_outs(%arg1 = %a) {
1785/// tensor.extract_slice %a[%i] [1]
1786/// ...
1787/// scf.forall.in_parallel {
1788/// tensor.parallel_insert_slice ... into %arg1[%i] [1]
1789/// }
1790/// }
1791///
1792/// OUTPUT:
1793/// scf.forall (%i) ... shared_outs(%arg1 = %a) {
1794/// tensor.extract_slice %arg1[%i] [1]
1795/// ...
1796/// scf.forall.in_parallel {
1797/// tensor.parallel_insert_slice ... into %arg1[%i] [1]
1798/// }
1799/// }
1800struct ForallOpReplaceInitUsesWithBlockArg : public OpRewritePattern<ForallOp> {
1801 using OpRewritePattern<ForallOp>::OpRewritePattern;
1802
1803 /// Whether `slice` is provably equivalent to one of `candidates`.
1804 static bool isEquivalentToAny(MLIRContext *ctx,
1805 const HyperrectangularSlice &slice,
1806 ArrayRef<HyperrectangularSlice> candidates) {
1807 return llvm::any_of(Range&: candidates, P: [&](const HyperrectangularSlice &other) {
1808 FailureOr<bool> equivalent =
1809 ValueBoundsConstraintSet::areEquivalentSlices(ctx, slice1: slice, slice2: other);
1810 return succeeded(Result: equivalent) && *equivalent;
1811 });
1812 }
1813
1814 LogicalResult matchAndRewrite(ForallOp op,
1815 PatternRewriter &rewriter) const override {
1816 bool changed = false;
1817 for (OpResult result : op.getResults()) {
1818 OpOperand *init = op.getTiedOpOperand(opResult: result);
1819 BlockArgument blockArg = op.getTiedBlockArgument(opOperand: init);
1820 // The tiles of the shared_outs that the iteration writes.
1821 SmallVector<HyperrectangularSlice> written = llvm::map_to_vector(
1822 C: llvm::make_filter_range(Range: op.getCombiningOps(bbArg: blockArg),
1823 Pred: llvm::IsaPred<tensor::ParallelInsertSliceOp>),
1824 F: [](Operation *combiningOp) {
1825 return HyperrectangularSlice(
1826 cast<tensor::ParallelInsertSliceOp>(Val: combiningOp));
1827 });
1828
1829 // Whether `use` of the init reads, inside the body, one of those tiles.
1830 auto isReadOfWrittenTile = [&](OpOperand &use) {
1831 auto extractOp = dyn_cast<tensor::ExtractSliceOp>(Val: use.getOwner());
1832 return extractOp && op->isProperAncestor(other: extractOp) &&
1833 isEquivalentToAny(ctx: op.getContext(),
1834 slice: HyperrectangularSlice(extractOp), candidates: written);
1835 };
1836 for (OpOperand &use : llvm::make_early_inc_range(Range: llvm::make_filter_range(
1837 Range: init->get().getUses(), Pred: isReadOfWrittenTile))) {
1838 // Read the block argument instead. Both are the same tensor here, and
1839 // for the block argument bufferization can tell that the tile is read
1840 // and written in place, with no copy.
1841 rewriter.modifyOpInPlace(root: use.getOwner(), callable: [&] { use.set(blockArg); });
1842 changed = true;
1843 }
1844 }
1845 return success(IsSuccess: changed);
1846 }
1847};
1848
1849struct FoldTensorCastOfOutputIntoForallOp
1850 : public OpRewritePattern<scf::ForallOp> {
1851 using OpRewritePattern<scf::ForallOp>::OpRewritePattern;
1852
1853 struct TypeCast {
1854 Type srcType;
1855 Type dstType;
1856 };
1857
1858 LogicalResult matchAndRewrite(scf::ForallOp forallOp,
1859 PatternRewriter &rewriter) const final {
1860 llvm::SmallMapVector<unsigned, TypeCast, 2> tensorCastProducers;
1861 llvm::SmallVector<Value> newOutputTensors = forallOp.getOutputs();
1862 for (auto en : llvm::enumerate(First&: newOutputTensors)) {
1863 auto castOp = en.value().getDefiningOp<tensor::CastOp>();
1864 if (!castOp)
1865 continue;
1866
1867 // Only casts that that preserve static information, i.e. will make the
1868 // loop result type "more" static than before, will be folded.
1869 if (!tensor::preservesStaticInformation(source: castOp.getDest().getType(),
1870 target: castOp.getSource().getType())) {
1871 continue;
1872 }
1873
1874 tensorCastProducers[en.index()] =
1875 TypeCast{.srcType: castOp.getSource().getType(), .dstType: castOp.getType()};
1876 newOutputTensors[en.index()] = castOp.getSource();
1877 }
1878
1879 if (tensorCastProducers.empty())
1880 return failure();
1881
1882 // Create new loop.
1883 Location loc = forallOp.getLoc();
1884 auto newForallOp = ForallOp::create(
1885 builder&: rewriter, location: loc, lbs: forallOp.getMixedLowerBound(),
1886 ubs: forallOp.getMixedUpperBound(), steps: forallOp.getMixedStep(),
1887 outputs: newOutputTensors, mapping: forallOp.getMapping(),
1888 bodyBuilderFn: [&](OpBuilder nestedBuilder, Location nestedLoc, ValueRange bbArgs) {
1889 auto castBlockArgs =
1890 llvm::to_vector(Range: bbArgs.take_back(n: forallOp->getNumResults()));
1891 for (auto [index, cast] : tensorCastProducers) {
1892 Value &oldTypeBBArg = castBlockArgs[index];
1893 oldTypeBBArg = tensor::CastOp::create(builder&: nestedBuilder, location: nestedLoc,
1894 dest: cast.dstType, source: oldTypeBBArg);
1895 }
1896
1897 // Move old body into new parallel loop.
1898 SmallVector<Value> ivsBlockArgs =
1899 llvm::to_vector(Range: bbArgs.take_front(n: forallOp.getRank()));
1900 ivsBlockArgs.append(RHS: castBlockArgs);
1901 rewriter.mergeBlocks(source: forallOp.getBody(),
1902 dest: bbArgs.front().getParentBlock(), argValues: ivsBlockArgs);
1903 });
1904
1905 // After `mergeBlocks` happened, the destinations in the terminator may be
1906 // mapped to tensor.cast values wrapping the new output bbArgs (introduced
1907 // for indices in `tensorCastProducers`). Update those destinations to
1908 // point directly to the output bbArgs, bypassing the casts.
1909 //
1910 // Note: we cannot zip yieldingOps with regionIterArgs by position because
1911 // a parallel_insert_slice inside in_parallel may write to any shared
1912 // output, not necessarily the one at the same position.
1913 llvm::SmallDenseSet<Value> newIterArgSet(
1914 newForallOp.getRegionIterArgs().begin(),
1915 newForallOp.getRegionIterArgs().end());
1916 auto terminator = newForallOp.getTerminator();
1917 for (auto &yieldingOp : terminator.getYieldingOps()) {
1918 auto parallelCombiningOp =
1919 dyn_cast<ParallelCombiningOpInterface>(Val: &yieldingOp);
1920 if (!parallelCombiningOp)
1921 continue;
1922 for (OpOperand &dest : parallelCombiningOp.getUpdatedDestinations()) {
1923 auto castOp = dest.get().getDefiningOp<tensor::CastOp>();
1924 if (castOp && newIterArgSet.contains(V: castOp.getSource()))
1925 dest.set(castOp.getSource());
1926 }
1927 }
1928
1929 // Cast results back to the original types.
1930 rewriter.setInsertionPointAfter(newForallOp);
1931 SmallVector<Value> castResults = newForallOp.getResults();
1932 for (auto &item : tensorCastProducers) {
1933 Value &oldTypeResult = castResults[item.first];
1934 oldTypeResult = tensor::CastOp::create(builder&: rewriter, location: loc, dest: item.second.dstType,
1935 source: oldTypeResult);
1936 }
1937 rewriter.replaceOp(op: forallOp, newValues: castResults);
1938 return success();
1939 }
1940};
1941
1942} // namespace
1943
1944void ForallOp::getCanonicalizationPatterns(RewritePatternSet &results,
1945 MLIRContext *context) {
1946 results.add<DimOfForallOp, FoldTensorCastOfOutputIntoForallOp,
1947 ForallOpControlOperandsFolder, ForallOpIterArgsFolder,
1948 ForallOpSingleOrZeroIterationDimsFolder,
1949 ForallOpReplaceConstantInductionVar,
1950 ForallOpReplaceInitUsesWithBlockArg>(arg&: context);
1951}
1952
1953void ForallOp::getSuccessorRegions(RegionBranchPoint point,
1954 SmallVectorImpl<RegionSuccessor> &regions) {
1955 // There are two region branch points:
1956 // 1. "parent": entering the forall op for the first time.
1957 // 2. scf.in_parallel terminator
1958 if (point.isParent()) {
1959 // When first entering the forall op, the control flow typically branches
1960 // into the forall body. (In parallel for multiple threads.)
1961 regions.push_back(Elt: RegionSuccessor(&getRegion()));
1962 // However, when there are 0 threads, the control flow may branch back to
1963 // the parent immediately.
1964 regions.push_back(Elt: RegionSuccessor(getOperation()));
1965 } else {
1966 // In accordance with the semantics of forall, its body is executed in
1967 // parallel by multiple threads. We should not expect to branch back into
1968 // the forall body after the region's execution is complete.
1969 regions.push_back(Elt: RegionSuccessor(getOperation()));
1970 }
1971}
1972
1973//===----------------------------------------------------------------------===//
1974// InParallelOp
1975//===----------------------------------------------------------------------===//
1976
1977// Build a InParallelOp with mixed static and dynamic entries.
1978void InParallelOp::build(OpBuilder &b, OperationState &result) {
1979 OpBuilder::InsertionGuard g(b);
1980 Region *bodyRegion = result.addRegion();
1981 b.createBlock(parent: bodyRegion);
1982}
1983
1984LogicalResult InParallelOp::verify() {
1985 scf::ForallOp forallOp =
1986 dyn_cast<scf::ForallOp>(Val: getOperation()->getParentOp());
1987 if (!forallOp)
1988 return this->emitOpError(message: "expected forall op parent");
1989
1990 for (Operation &op : getRegion().front().getOperations()) {
1991 auto parallelCombiningOp = dyn_cast<ParallelCombiningOpInterface>(Val: &op);
1992 if (!parallelCombiningOp) {
1993 return this->emitOpError(message: "expected only ParallelCombiningOpInterface")
1994 << " ops";
1995 }
1996
1997 // Verify that inserts are into out block arguments.
1998 MutableOperandRange dests = parallelCombiningOp.getUpdatedDestinations();
1999 ArrayRef<BlockArgument> regionOutArgs = forallOp.getRegionOutArgs();
2000 for (OpOperand &dest : dests) {
2001 if (!llvm::is_contained(Range&: regionOutArgs, Element: dest.get()))
2002 return op.emitOpError(message: "may only insert into an output block argument");
2003 }
2004 }
2005
2006 return success();
2007}
2008
2009void InParallelOp::print(OpAsmPrinter &p) {
2010 p << " ";
2011 p.printRegion(blocks&: getRegion(),
2012 /*printEntryBlockArgs=*/false,
2013 /*printBlockTerminators=*/false);
2014 p.printOptionalAttrDict(
2015 attrs: getOperation()->getDiscardableAttrDictionary().getValue());
2016}
2017
2018ParseResult InParallelOp::parse(OpAsmParser &parser, OperationState &result) {
2019 auto &builder = parser.getBuilder();
2020
2021 SmallVector<OpAsmParser::Argument, 8> regionOperands;
2022 std::unique_ptr<Region> region = std::make_unique<Region>();
2023 if (parser.parseRegion(region&: *region, arguments: regionOperands))
2024 return failure();
2025
2026 if (region->empty())
2027 OpBuilder(builder.getContext()).createBlock(parent: region.get());
2028 result.addRegion(region: std::move(region));
2029
2030 // Parse the optional attribute list.
2031 if (parser.parseOptionalAttrDict(result&: result.attributes))
2032 return failure();
2033 return success();
2034}
2035
2036OpResult InParallelOp::getParentResult(int64_t idx) {
2037 return getOperation()->getParentOp()->getResult(idx);
2038}
2039
2040SmallVector<BlockArgument> InParallelOp::getDests() {
2041 SmallVector<BlockArgument> updatedDests;
2042 for (Operation &yieldingOp : getYieldingOps()) {
2043 auto parallelCombiningOp =
2044 dyn_cast<ParallelCombiningOpInterface>(Val: &yieldingOp);
2045 if (!parallelCombiningOp)
2046 continue;
2047 for (OpOperand &updatedOperand :
2048 parallelCombiningOp.getUpdatedDestinations())
2049 updatedDests.push_back(Elt: cast<BlockArgument>(Val: updatedOperand.get()));
2050 }
2051 return updatedDests;
2052}
2053
2054llvm::iterator_range<Block::iterator> InParallelOp::getYieldingOps() {
2055 return getRegion().front().getOperations();
2056}
2057
2058//===----------------------------------------------------------------------===//
2059// IfOp
2060//===----------------------------------------------------------------------===//
2061
2062bool mlir::scf::insideMutuallyExclusiveBranches(Operation *a, Operation *b) {
2063 assert(a && "expected non-empty operation");
2064 assert(b && "expected non-empty operation");
2065
2066 IfOp ifOp = a->getParentOfType<IfOp>();
2067 while (ifOp) {
2068 // Check if b is inside ifOp. (We already know that a is.)
2069 if (ifOp->isProperAncestor(other: b))
2070 // b is contained in ifOp. a and b are in mutually exclusive branches if
2071 // they are in different blocks of ifOp.
2072 return static_cast<bool>(ifOp.thenBlock()->findAncestorOpInBlock(op&: *a)) !=
2073 static_cast<bool>(ifOp.thenBlock()->findAncestorOpInBlock(op&: *b));
2074 // Check next enclosing IfOp.
2075 ifOp = ifOp->getParentOfType<IfOp>();
2076 }
2077
2078 // Could not find a common IfOp among a's and b's ancestors.
2079 return false;
2080}
2081
2082LogicalResult
2083IfOp::inferReturnTypes(MLIRContext *ctx, std::optional<Location> loc,
2084 IfOp::Adaptor adaptor,
2085 SmallVectorImpl<Type> &inferredReturnTypes) {
2086 if (adaptor.getRegions().empty())
2087 return failure();
2088 Region *r = &adaptor.getThenRegion();
2089 if (r->empty())
2090 return failure();
2091 Block &b = r->front();
2092 if (b.empty())
2093 return failure();
2094 auto yieldOp = llvm::dyn_cast<YieldOp>(Val&: b.back());
2095 if (!yieldOp)
2096 return failure();
2097 TypeRange types = yieldOp.getOperandTypes();
2098 llvm::append_range(C&: inferredReturnTypes, R&: types);
2099 return success();
2100}
2101
2102void IfOp::build(OpBuilder &builder, OperationState &result,
2103 TypeRange resultTypes, Value cond) {
2104 return build(odsBuilder&: builder, odsState&: result, resultTypes, cond, /*addThenBlock=*/false,
2105 /*addElseBlock=*/false);
2106}
2107
2108void IfOp::build(OpBuilder &builder, OperationState &result,
2109 TypeRange resultTypes, Value cond, bool addThenBlock,
2110 bool addElseBlock) {
2111 assert((!addElseBlock || addThenBlock) &&
2112 "must not create else block w/o then block");
2113 result.addTypes(newTypes&: resultTypes);
2114 result.addOperands(newOperands: cond);
2115
2116 // Add regions and blocks.
2117 OpBuilder::InsertionGuard guard(builder);
2118 Region *thenRegion = result.addRegion();
2119 if (addThenBlock)
2120 builder.createBlock(parent: thenRegion);
2121 Region *elseRegion = result.addRegion();
2122 if (addElseBlock)
2123 builder.createBlock(parent: elseRegion);
2124}
2125
2126void IfOp::build(OpBuilder &builder, OperationState &result, Value cond,
2127 bool withElseRegion) {
2128 build(odsBuilder&: builder, odsState&: result, resultTypes: TypeRange{}, cond, withElseRegion);
2129}
2130
2131void IfOp::build(OpBuilder &builder, OperationState &result,
2132 TypeRange resultTypes, Value cond, bool withElseRegion) {
2133 result.addTypes(newTypes&: resultTypes);
2134 result.addOperands(newOperands: cond);
2135
2136 // Build then region.
2137 OpBuilder::InsertionGuard guard(builder);
2138 Region *thenRegion = result.addRegion();
2139 builder.createBlock(parent: thenRegion);
2140 if (resultTypes.empty())
2141 IfOp::ensureTerminator(region&: *thenRegion, builder, loc: result.location);
2142
2143 // Build else region.
2144 Region *elseRegion = result.addRegion();
2145 if (withElseRegion) {
2146 builder.createBlock(parent: elseRegion);
2147 if (resultTypes.empty())
2148 IfOp::ensureTerminator(region&: *elseRegion, builder, loc: result.location);
2149 }
2150}
2151
2152void IfOp::build(OpBuilder &builder, OperationState &result, Value cond,
2153 function_ref<void(OpBuilder &, Location)> thenBuilder,
2154 function_ref<void(OpBuilder &, Location)> elseBuilder) {
2155 assert(thenBuilder && "the builder callback for 'then' must be present");
2156 result.addOperands(newOperands: cond);
2157
2158 // Build then region.
2159 OpBuilder::InsertionGuard guard(builder);
2160 Region *thenRegion = result.addRegion();
2161 builder.createBlock(parent: thenRegion);
2162 thenBuilder(builder, result.location);
2163
2164 // Build else region.
2165 Region *elseRegion = result.addRegion();
2166 if (elseBuilder) {
2167 builder.createBlock(parent: elseRegion);
2168 elseBuilder(builder, result.location);
2169 }
2170
2171 // Infer result types.
2172 SmallVector<Type> inferredReturnTypes;
2173 MLIRContext *ctx = builder.getContext();
2174 auto attrDict = DictionaryAttr::get(context: ctx, value: result.attributes);
2175 if (succeeded(Result: inferReturnTypes(context: ctx, location: std::nullopt, operands: result.operands, attributes: attrDict,
2176 /*properties=*/PropertyRef{}, regions: result.regions,
2177 inferredReturnTypes))) {
2178 result.addTypes(newTypes: inferredReturnTypes);
2179 }
2180}
2181
2182LogicalResult IfOp::verify() {
2183 if (getNumResults() != 0 && getElseRegion().empty())
2184 return emitOpError(message: "must have an else block if defining values");
2185 return success();
2186}
2187
2188ParseResult IfOp::parse(OpAsmParser &parser, OperationState &result) {
2189 // Create the regions for 'then'.
2190 result.regions.reserve(N: 2);
2191 Region *thenRegion = result.addRegion();
2192 Region *elseRegion = result.addRegion();
2193
2194 auto &builder = parser.getBuilder();
2195 OpAsmParser::UnresolvedOperand cond;
2196 Type i1Type = builder.getIntegerType(width: 1);
2197 if (parser.parseOperand(result&: cond) ||
2198 parser.resolveOperand(operand: cond, type: i1Type, result&: result.operands))
2199 return failure();
2200 // Parse optional results type list.
2201 if (parser.parseOptionalArrowTypeList(result&: result.types))
2202 return failure();
2203 // Parse the 'then' region.
2204 if (parser.parseRegion(region&: *thenRegion, /*arguments=*/{}, /*argTypes=*/enableNameShadowing: {}))
2205 return failure();
2206 IfOp::ensureTerminator(region&: *thenRegion, builder&: parser.getBuilder(), loc: result.location);
2207
2208 // If we find an 'else' keyword then parse the 'else' region.
2209 if (!parser.parseOptionalKeyword(keyword: "else")) {
2210 if (parser.parseRegion(region&: *elseRegion, /*arguments=*/{}, /*argTypes=*/enableNameShadowing: {}))
2211 return failure();
2212 IfOp::ensureTerminator(region&: *elseRegion, builder&: parser.getBuilder(), loc: result.location);
2213 }
2214
2215 // Parse the optional attribute list.
2216 if (parser.parseOptionalAttrDict(result&: result.attributes))
2217 return failure();
2218 return success();
2219}
2220
2221void IfOp::print(OpAsmPrinter &p) {
2222 bool printBlockTerminators = false;
2223
2224 p << " " << getCondition();
2225 if (!getResults().empty()) {
2226 p << " -> (" << getResultTypes() << ")";
2227 // Print yield explicitly if the op defines values.
2228 printBlockTerminators = true;
2229 }
2230 p << ' ';
2231 p.printRegion(blocks&: getThenRegion(),
2232 /*printEntryBlockArgs=*/false,
2233 /*printBlockTerminators=*/printBlockTerminators);
2234
2235 // Print the 'else' regions if it exists and has a block.
2236 auto &elseRegion = getElseRegion();
2237 if (!elseRegion.empty()) {
2238 p << " else ";
2239 p.printRegion(blocks&: elseRegion,
2240 /*printEntryBlockArgs=*/false,
2241 /*printBlockTerminators=*/printBlockTerminators);
2242 }
2243
2244 p.printOptionalAttrDict(attrs: (*this)->getDiscardableAttrDictionary().getValue());
2245}
2246
2247void IfOp::getSuccessorRegions(RegionBranchPoint point,
2248 SmallVectorImpl<RegionSuccessor> &regions) {
2249 // The `then` and the `else` region branch back to the parent operation or one
2250 // of the recursive parent operations (early exit case).
2251 if (!point.isParent()) {
2252 regions.push_back(Elt: RegionSuccessor(getOperation()));
2253 return;
2254 }
2255
2256 regions.push_back(Elt: RegionSuccessor(&getThenRegion()));
2257
2258 // Don't consider the else region if it is empty.
2259 Region *elseRegion = &this->getElseRegion();
2260 if (elseRegion->empty())
2261 regions.push_back(Elt: RegionSuccessor(getOperation()));
2262 else
2263 regions.push_back(Elt: RegionSuccessor(elseRegion));
2264}
2265
2266ValueRange IfOp::getSuccessorInputs(RegionSuccessor successor) {
2267 return successor.isOperation() ? ValueRange(getOperation()->getResults())
2268 : ValueRange();
2269}
2270
2271void IfOp::getEntrySuccessorRegions(ArrayRef<Attribute> operands,
2272 SmallVectorImpl<RegionSuccessor> &regions) {
2273 FoldAdaptor adaptor(operands, *this);
2274 auto boolAttr = dyn_cast_or_null<BoolAttr>(Val: adaptor.getCondition());
2275 if (!boolAttr || boolAttr.getValue())
2276 regions.emplace_back(Args: &getThenRegion());
2277
2278 // If the else region is empty, execution continues after the parent op.
2279 if (!boolAttr || !boolAttr.getValue()) {
2280 if (!getElseRegion().empty())
2281 regions.emplace_back(Args: &getElseRegion());
2282 else
2283 regions.emplace_back(Args: RegionSuccessor(getOperation()));
2284 }
2285}
2286
2287LogicalResult IfOp::fold(FoldAdaptor adaptor,
2288 SmallVectorImpl<OpFoldResult> &results) {
2289 // if (!c) then A() else B() -> if c then B() else A()
2290 if (getElseRegion().empty())
2291 return failure();
2292
2293 arith::XOrIOp xorStmt = getCondition().getDefiningOp<arith::XOrIOp>();
2294 if (!xorStmt)
2295 return failure();
2296
2297 if (!matchPattern(value: xorStmt.getRhs(), pattern: m_One()))
2298 return failure();
2299
2300 getConditionMutable().assign(value: xorStmt.getLhs());
2301 Block *thenBlock = &getThenRegion().front();
2302 // It would be nicer to use iplist::swap, but that has no implemented
2303 // callbacks See: https://llvm.org/doxygen/ilist_8h_source.html#l00224
2304 getThenRegion().getBlocks().splice(where: getThenRegion().getBlocks().begin(),
2305 L2&: getElseRegion().getBlocks());
2306 getElseRegion().getBlocks().splice(where: getElseRegion().getBlocks().begin(),
2307 L2&: getThenRegion().getBlocks(), N: thenBlock);
2308 return success();
2309}
2310
2311void IfOp::getRegionInvocationBounds(
2312 ArrayRef<Attribute> operands,
2313 SmallVectorImpl<InvocationBounds> &invocationBounds) {
2314 if (auto cond = llvm::dyn_cast_or_null<BoolAttr>(Val: operands[0])) {
2315 // If the condition is known, then one region is known to be executed once
2316 // and the other zero times.
2317 invocationBounds.emplace_back(Args: 0, Args: cond.getValue() ? 1 : 0);
2318 invocationBounds.emplace_back(Args: 0, Args: cond.getValue() ? 0 : 1);
2319 } else {
2320 // Non-constant condition. Each region may be executed 0 or 1 times.
2321 invocationBounds.assign(NumElts: 2, Elt: {0, 1});
2322 }
2323}
2324
2325namespace {
2326/// Hoist any yielded results whose operands are defined outside
2327/// the if, to a select instruction.
2328struct ConvertTrivialIfToSelect : public OpRewritePattern<IfOp> {
2329 using OpRewritePattern<IfOp>::OpRewritePattern;
2330
2331 LogicalResult matchAndRewrite(IfOp op,
2332 PatternRewriter &rewriter) const override {
2333 if (op->getNumResults() == 0)
2334 return failure();
2335
2336 auto cond = op.getCondition();
2337 auto thenYieldArgs = op.thenYield().getOperands();
2338 auto elseYieldArgs = op.elseYield().getOperands();
2339
2340 SmallVector<Type> nonHoistable;
2341 for (auto [trueVal, falseVal] : llvm::zip(t&: thenYieldArgs, u&: elseYieldArgs)) {
2342 if (&op.getThenRegion() == trueVal.getParentRegion() ||
2343 &op.getElseRegion() == falseVal.getParentRegion())
2344 nonHoistable.push_back(Elt: trueVal.getType());
2345 }
2346 // Early exit if there aren't any yielded values we can
2347 // hoist outside the if.
2348 if (nonHoistable.size() == op->getNumResults())
2349 return failure();
2350
2351 IfOp replacement = IfOp::create(builder&: rewriter, location: op.getLoc(), resultTypes: nonHoistable, cond,
2352 /*withElseRegion=*/false);
2353 if (replacement.thenBlock())
2354 rewriter.eraseBlock(block: replacement.thenBlock());
2355 replacement.getThenRegion().takeBody(other&: op.getThenRegion());
2356 replacement.getElseRegion().takeBody(other&: op.getElseRegion());
2357
2358 SmallVector<Value> results(op->getNumResults());
2359 assert(thenYieldArgs.size() == results.size());
2360 assert(elseYieldArgs.size() == results.size());
2361
2362 SmallVector<Value> trueYields;
2363 SmallVector<Value> falseYields;
2364 rewriter.setInsertionPoint(replacement);
2365 for (const auto &it :
2366 llvm::enumerate(First: llvm::zip(t&: thenYieldArgs, u&: elseYieldArgs))) {
2367 Value trueVal = std::get<0>(t&: it.value());
2368 Value falseVal = std::get<1>(t&: it.value());
2369 if (&replacement.getThenRegion() == trueVal.getParentRegion() ||
2370 &replacement.getElseRegion() == falseVal.getParentRegion()) {
2371 results[it.index()] = replacement.getResult(i: trueYields.size());
2372 trueYields.push_back(Elt: trueVal);
2373 falseYields.push_back(Elt: falseVal);
2374 } else if (trueVal == falseVal)
2375 results[it.index()] = trueVal;
2376 else
2377 results[it.index()] = arith::SelectOp::create(builder&: rewriter, location: op.getLoc(),
2378 condition: cond, true_value: trueVal, false_value: falseVal);
2379 }
2380
2381 rewriter.setInsertionPointToEnd(replacement.thenBlock());
2382 rewriter.replaceOpWithNewOp<YieldOp>(op: replacement.thenYield(), args&: trueYields);
2383
2384 rewriter.setInsertionPointToEnd(replacement.elseBlock());
2385 rewriter.replaceOpWithNewOp<YieldOp>(op: replacement.elseYield(), args&: falseYields);
2386
2387 rewriter.replaceOp(op, newValues: results);
2388 return success();
2389 }
2390};
2391
2392/// Allow the true region of an if to assume the condition is true
2393/// and vice versa. For example:
2394///
2395/// scf.if %cmp {
2396/// print(%cmp)
2397/// }
2398///
2399/// becomes
2400///
2401/// scf.if %cmp {
2402/// print(true)
2403/// }
2404///
2405struct ConditionPropagation : public OpRewritePattern<IfOp> {
2406 using OpRewritePattern<IfOp>::OpRewritePattern;
2407
2408 /// Kind of parent region in the ancestor cache.
2409 enum class Parent { Then, Else, None };
2410
2411 /// Returns the kind of region ("then", "else", or "none") of the
2412 /// IfOp that the given region is transitively nested in. Updates
2413 /// the cache accordingly.
2414 static Parent getParentType(Region *toCheck, IfOp op,
2415 DenseMap<Region *, Parent> &cache,
2416 Region *endRegion) {
2417 SmallVector<Region *> seen;
2418 while (toCheck != endRegion) {
2419 auto found = cache.find(Val: toCheck);
2420 if (found != cache.end())
2421 return found->second;
2422 seen.push_back(Elt: toCheck);
2423 if (&op.getThenRegion() == toCheck) {
2424 for (Region *region : seen)
2425 cache[region] = Parent::Then;
2426 return Parent::Then;
2427 }
2428 if (&op.getElseRegion() == toCheck) {
2429 for (Region *region : seen)
2430 cache[region] = Parent::Else;
2431 return Parent::Else;
2432 }
2433 toCheck = toCheck->getParentRegion();
2434 }
2435
2436 for (Region *region : seen)
2437 cache[region] = Parent::None;
2438 return Parent::None;
2439 }
2440
2441 LogicalResult matchAndRewrite(IfOp op,
2442 PatternRewriter &rewriter) const override {
2443 // Early exit if the condition is constant since replacing a constant
2444 // in the body with another constant isn't a simplification.
2445 if (matchPattern(value: op.getCondition(), pattern: m_Constant()))
2446 return failure();
2447
2448 bool changed = false;
2449 mlir::Type i1Ty = rewriter.getI1Type();
2450
2451 // These variables serve to prevent creating duplicate constants
2452 // and hold constant true or false values.
2453 Value constantTrue = nullptr;
2454 Value constantFalse = nullptr;
2455
2456 DenseMap<Region *, Parent> cache;
2457 for (OpOperand &use :
2458 llvm::make_early_inc_range(Range: op.getCondition().getUses())) {
2459 switch (getParentType(toCheck: use.getOwner()->getParentRegion(), op, cache,
2460 endRegion: op.getCondition().getParentRegion())) {
2461 case Parent::Then: {
2462 changed = true;
2463
2464 if (!constantTrue)
2465 constantTrue = arith::ConstantOp::create(
2466 builder&: rewriter, location: op.getLoc(), result: i1Ty, value: rewriter.getIntegerAttr(type: i1Ty, value: 1));
2467
2468 rewriter.modifyOpInPlace(root: use.getOwner(),
2469 callable: [&]() { use.set(constantTrue); });
2470 break;
2471 }
2472 case Parent::Else: {
2473 changed = true;
2474
2475 if (!constantFalse)
2476 constantFalse = arith::ConstantOp::create(
2477 builder&: rewriter, location: op.getLoc(), result: i1Ty, value: rewriter.getIntegerAttr(type: i1Ty, value: 0));
2478
2479 rewriter.modifyOpInPlace(root: use.getOwner(),
2480 callable: [&]() { use.set(constantFalse); });
2481 break;
2482 }
2483 case Parent::None: {
2484 auto selectOp = dyn_cast<arith::SelectOp>(Val: use.getOwner());
2485 if (!selectOp || use.getOperandNumber() != 0)
2486 break;
2487
2488 // Refine captured select results only at uses in the matching branch.
2489 // Uses outside the if must retain the select result.
2490 changed |= rewriter.replaceUsesWithIf(
2491 from: selectOp.getResult(), to: selectOp.getTrueValue(),
2492 functor: [&](OpOperand &selectUse) {
2493 return getParentType(
2494 toCheck: selectUse.getOwner()->getParentRegion(), op, cache,
2495 endRegion: op.getCondition().getParentRegion()) == Parent::Then;
2496 });
2497 changed |= rewriter.replaceUsesWithIf(
2498 from: selectOp.getResult(), to: selectOp.getFalseValue(),
2499 functor: [&](OpOperand &selectUse) {
2500 return getParentType(
2501 toCheck: selectUse.getOwner()->getParentRegion(), op, cache,
2502 endRegion: op.getCondition().getParentRegion()) == Parent::Else;
2503 });
2504 break;
2505 }
2506 }
2507 }
2508
2509 return success(IsSuccess: changed);
2510 }
2511};
2512
2513/// Remove any statements from an if that are equivalent to the condition
2514/// or its negation. For example:
2515///
2516/// %res:2 = scf.if %cmp {
2517/// yield something(), true
2518/// } else {
2519/// yield something2(), false
2520/// }
2521/// print(%res#1)
2522///
2523/// becomes
2524/// %res = scf.if %cmp {
2525/// yield something()
2526/// } else {
2527/// yield something2()
2528/// }
2529/// print(%cmp)
2530///
2531/// Additionally if both branches yield the same value, replace all uses
2532/// of the result with the yielded value.
2533///
2534/// %res:2 = scf.if %cmp {
2535/// yield something(), %arg1
2536/// } else {
2537/// yield something2(), %arg1
2538/// }
2539/// print(%res#1)
2540///
2541/// becomes
2542/// %res = scf.if %cmp {
2543/// yield something()
2544/// } else {
2545/// yield something2()
2546/// }
2547/// print(%arg1)
2548///
2549struct ReplaceIfYieldWithConditionOrValue : public OpRewritePattern<IfOp> {
2550 using OpRewritePattern<IfOp>::OpRewritePattern;
2551
2552 LogicalResult matchAndRewrite(IfOp op,
2553 PatternRewriter &rewriter) const override {
2554 // Early exit if there are no results that could be replaced.
2555 if (op.getNumResults() == 0)
2556 return failure();
2557
2558 auto trueYield =
2559 cast<scf::YieldOp>(Val: op.getThenRegion().back().getTerminator());
2560 auto falseYield =
2561 cast<scf::YieldOp>(Val: op.getElseRegion().back().getTerminator());
2562
2563 rewriter.setInsertionPoint(block: op->getBlock(),
2564 insertPoint: op.getOperation()->getIterator());
2565 bool changed = false;
2566 Type i1Ty = rewriter.getI1Type();
2567 for (auto [trueResult, falseResult, opResult] :
2568 llvm::zip(t: trueYield.getResults(), u: falseYield.getResults(),
2569 args: op.getResults())) {
2570 if (trueResult == falseResult) {
2571 if (!opResult.use_empty()) {
2572 opResult.replaceAllUsesWith(newValue: trueResult);
2573 changed = true;
2574 }
2575 continue;
2576 }
2577
2578 BoolAttr trueYield, falseYield;
2579 if (!matchPattern(value: trueResult, pattern: m_Constant(bind_value: &trueYield)) ||
2580 !matchPattern(value: falseResult, pattern: m_Constant(bind_value: &falseYield)))
2581 continue;
2582
2583 bool trueVal = trueYield.getValue();
2584 bool falseVal = falseYield.getValue();
2585 if (!trueVal && falseVal) {
2586 if (!opResult.use_empty()) {
2587 Dialect *constDialect = trueResult.getDefiningOp()->getDialect();
2588 Value notCond = arith::XOrIOp::create(
2589 builder&: rewriter, location: op.getLoc(), lhs: op.getCondition(),
2590 rhs: constDialect
2591 ->materializeConstant(builder&: rewriter,
2592 value: rewriter.getIntegerAttr(type: i1Ty, value: 1), type: i1Ty,
2593 loc: op.getLoc())
2594 ->getResult(idx: 0));
2595 opResult.replaceAllUsesWith(newValue: notCond);
2596 changed = true;
2597 }
2598 }
2599 if (trueVal && !falseVal) {
2600 if (!opResult.use_empty()) {
2601 opResult.replaceAllUsesWith(newValue: op.getCondition());
2602 changed = true;
2603 }
2604 }
2605 }
2606 return success(IsSuccess: changed);
2607 }
2608};
2609
2610/// Merge any consecutive scf.if's with the same condition.
2611///
2612/// scf.if %cond {
2613/// firstCodeTrue();...
2614/// } else {
2615/// firstCodeFalse();...
2616/// }
2617/// %res = scf.if %cond {
2618/// secondCodeTrue();...
2619/// } else {
2620/// secondCodeFalse();...
2621/// }
2622///
2623/// becomes
2624/// %res = scf.if %cmp {
2625/// firstCodeTrue();...
2626/// secondCodeTrue();...
2627/// } else {
2628/// firstCodeFalse();...
2629/// secondCodeFalse();...
2630/// }
2631struct CombineIfs : public OpRewritePattern<IfOp> {
2632 using OpRewritePattern<IfOp>::OpRewritePattern;
2633
2634 LogicalResult matchAndRewrite(IfOp nextIf,
2635 PatternRewriter &rewriter) const override {
2636 Block *parent = nextIf->getBlock();
2637 if (nextIf == &parent->front())
2638 return failure();
2639
2640 auto prevIf = dyn_cast<IfOp>(Val: nextIf->getPrevNode());
2641 if (!prevIf)
2642 return failure();
2643
2644 // Determine the logical then/else blocks when prevIf's
2645 // condition is used. Null means the block does not exist
2646 // in that case (e.g. empty else). If neither of these
2647 // are set, the two conditions cannot be compared.
2648 Block *nextThen = nullptr;
2649 Block *nextElse = nullptr;
2650 if (nextIf.getCondition() == prevIf.getCondition()) {
2651 nextThen = nextIf.thenBlock();
2652 if (!nextIf.getElseRegion().empty())
2653 nextElse = nextIf.elseBlock();
2654 }
2655 if (arith::XOrIOp notv =
2656 nextIf.getCondition().getDefiningOp<arith::XOrIOp>()) {
2657 if (notv.getLhs() == prevIf.getCondition() &&
2658 matchPattern(value: notv.getRhs(), pattern: m_One())) {
2659 nextElse = nextIf.thenBlock();
2660 if (!nextIf.getElseRegion().empty())
2661 nextThen = nextIf.elseBlock();
2662 }
2663 }
2664 if (arith::XOrIOp notv =
2665 prevIf.getCondition().getDefiningOp<arith::XOrIOp>()) {
2666 if (notv.getLhs() == nextIf.getCondition() &&
2667 matchPattern(value: notv.getRhs(), pattern: m_One())) {
2668 nextElse = nextIf.thenBlock();
2669 if (!nextIf.getElseRegion().empty())
2670 nextThen = nextIf.elseBlock();
2671 }
2672 }
2673
2674 if (!nextThen && !nextElse)
2675 return failure();
2676
2677 SmallVector<Value> prevElseYielded;
2678 if (!prevIf.getElseRegion().empty())
2679 prevElseYielded = prevIf.elseYield().getOperands();
2680 // Replace all uses of return values of op within nextIf with the
2681 // corresponding yields
2682 for (auto it : llvm::zip(t: prevIf.getResults(),
2683 u: prevIf.thenYield().getOperands(), args&: prevElseYielded))
2684 for (OpOperand &use :
2685 llvm::make_early_inc_range(Range: std::get<0>(t&: it).getUses())) {
2686 if (nextThen && nextThen->getParent()->isAncestor(
2687 other: use.getOwner()->getParentRegion())) {
2688 rewriter.startOpModification(op: use.getOwner());
2689 use.set(std::get<1>(t&: it));
2690 rewriter.finalizeOpModification(op: use.getOwner());
2691 } else if (nextElse && nextElse->getParent()->isAncestor(
2692 other: use.getOwner()->getParentRegion())) {
2693 rewriter.startOpModification(op: use.getOwner());
2694 use.set(std::get<2>(t&: it));
2695 rewriter.finalizeOpModification(op: use.getOwner());
2696 }
2697 }
2698
2699 SmallVector<Type> mergedTypes(prevIf.getResultTypes());
2700 llvm::append_range(C&: mergedTypes, R: nextIf.getResultTypes());
2701
2702 IfOp combinedIf = IfOp::create(builder&: rewriter, location: nextIf.getLoc(), resultTypes: mergedTypes,
2703 cond: prevIf.getCondition(), /*hasElse=*/withElseRegion: false);
2704 rewriter.eraseBlock(block: &combinedIf.getThenRegion().back());
2705
2706 rewriter.inlineRegionBefore(region&: prevIf.getThenRegion(),
2707 parent&: combinedIf.getThenRegion(),
2708 before: combinedIf.getThenRegion().begin());
2709
2710 if (nextThen) {
2711 YieldOp thenYield = combinedIf.thenYield();
2712 YieldOp thenYield2 = cast<YieldOp>(Val: nextThen->getTerminator());
2713 rewriter.mergeBlocks(source: nextThen, dest: combinedIf.thenBlock());
2714 rewriter.setInsertionPointToEnd(combinedIf.thenBlock());
2715
2716 SmallVector<Value> mergedYields(thenYield.getOperands());
2717 llvm::append_range(C&: mergedYields, R: thenYield2.getOperands());
2718 YieldOp::create(builder&: rewriter, location: thenYield2.getLoc(), results: mergedYields);
2719 rewriter.eraseOp(op: thenYield);
2720 rewriter.eraseOp(op: thenYield2);
2721 }
2722
2723 rewriter.inlineRegionBefore(region&: prevIf.getElseRegion(),
2724 parent&: combinedIf.getElseRegion(),
2725 before: combinedIf.getElseRegion().begin());
2726
2727 if (nextElse) {
2728 if (combinedIf.getElseRegion().empty()) {
2729 rewriter.inlineRegionBefore(region&: *nextElse->getParent(),
2730 parent&: combinedIf.getElseRegion(),
2731 before: combinedIf.getElseRegion().begin());
2732 } else {
2733 YieldOp elseYield = combinedIf.elseYield();
2734 YieldOp elseYield2 = cast<YieldOp>(Val: nextElse->getTerminator());
2735 rewriter.mergeBlocks(source: nextElse, dest: combinedIf.elseBlock());
2736
2737 rewriter.setInsertionPointToEnd(combinedIf.elseBlock());
2738
2739 SmallVector<Value> mergedElseYields(elseYield.getOperands());
2740 llvm::append_range(C&: mergedElseYields, R: elseYield2.getOperands());
2741
2742 YieldOp::create(builder&: rewriter, location: elseYield2.getLoc(), results: mergedElseYields);
2743 rewriter.eraseOp(op: elseYield);
2744 rewriter.eraseOp(op: elseYield2);
2745 }
2746 }
2747
2748 SmallVector<Value> prevValues;
2749 SmallVector<Value> nextValues;
2750 for (const auto &pair : llvm::enumerate(First: combinedIf.getResults())) {
2751 if (pair.index() < prevIf.getNumResults())
2752 prevValues.push_back(Elt: pair.value());
2753 else
2754 nextValues.push_back(Elt: pair.value());
2755 }
2756 rewriter.replaceOp(op: prevIf, newValues: prevValues);
2757 rewriter.replaceOp(op: nextIf, newValues: nextValues);
2758 return success();
2759 }
2760};
2761
2762/// Pattern to remove an empty else branch.
2763struct RemoveEmptyElseBranch : public OpRewritePattern<IfOp> {
2764 using OpRewritePattern<IfOp>::OpRewritePattern;
2765
2766 LogicalResult matchAndRewrite(IfOp ifOp,
2767 PatternRewriter &rewriter) const override {
2768 // Cannot remove else region when there are operation results.
2769 if (ifOp.getNumResults())
2770 return failure();
2771 Block *elseBlock = ifOp.elseBlock();
2772 if (!elseBlock || !llvm::hasSingleElement(C&: *elseBlock))
2773 return failure();
2774 auto newIfOp = rewriter.cloneWithoutRegions(op: ifOp);
2775 rewriter.inlineRegionBefore(region&: ifOp.getThenRegion(), parent&: newIfOp.getThenRegion(),
2776 before: newIfOp.getThenRegion().begin());
2777 rewriter.eraseOp(op: ifOp);
2778 return success();
2779 }
2780};
2781
2782/// Convert nested `if`s into `arith.andi` + single `if`.
2783///
2784/// scf.if %arg0 {
2785/// scf.if %arg1 {
2786/// ...
2787/// scf.yield
2788/// }
2789/// scf.yield
2790/// }
2791/// becomes
2792///
2793/// %0 = arith.andi %arg0, %arg1
2794/// scf.if %0 {
2795/// ...
2796/// scf.yield
2797/// }
2798struct CombineNestedIfs : public OpRewritePattern<IfOp> {
2799 using OpRewritePattern<IfOp>::OpRewritePattern;
2800
2801 LogicalResult matchAndRewrite(IfOp op,
2802 PatternRewriter &rewriter) const override {
2803 auto nestedOps = op.thenBlock()->without_terminator();
2804 // Nested `if` must be the only op in block.
2805 if (!llvm::hasSingleElement(C&: nestedOps))
2806 return failure();
2807
2808 // If there is an else block, it can only yield
2809 if (op.elseBlock() && !llvm::hasSingleElement(C&: *op.elseBlock()))
2810 return failure();
2811
2812 auto nestedIf = dyn_cast<IfOp>(Val&: *nestedOps.begin());
2813 if (!nestedIf)
2814 return failure();
2815
2816 if (nestedIf.elseBlock() && !llvm::hasSingleElement(C&: *nestedIf.elseBlock()))
2817 return failure();
2818
2819 SmallVector<Value> thenYield(op.thenYield().getOperands());
2820 SmallVector<Value> elseYield;
2821 if (op.elseBlock())
2822 llvm::append_range(C&: elseYield, R: op.elseYield().getOperands());
2823
2824 // A list of indices for which we should upgrade the value yielded
2825 // in the else to a select.
2826 SmallVector<unsigned> elseYieldsToUpgradeToSelect;
2827
2828 // If the outer scf.if yields a value produced by the inner scf.if,
2829 // only permit combining if the value yielded when the condition
2830 // is false in the outer scf.if is the same value yielded when the
2831 // inner scf.if condition is false.
2832 // Note that the array access to elseYield will not go out of bounds
2833 // since it must have the same length as thenYield, since they both
2834 // come from the same scf.if.
2835 for (const auto &tup : llvm::enumerate(First&: thenYield)) {
2836 if (tup.value().getDefiningOp() == nestedIf) {
2837 auto nestedIdx = llvm::cast<OpResult>(Val&: tup.value()).getResultNumber();
2838 if (nestedIf.elseYield().getOperand(i: nestedIdx) !=
2839 elseYield[tup.index()]) {
2840 return failure();
2841 }
2842 // If the correctness test passes, we will yield
2843 // corresponding value from the inner scf.if
2844 thenYield[tup.index()] = nestedIf.thenYield().getOperand(i: nestedIdx);
2845 continue;
2846 }
2847
2848 // Otherwise, we need to ensure the else block of the combined
2849 // condition still returns the same value when the outer condition is
2850 // true and the inner condition is false. This can be accomplished if
2851 // the then value is defined outside the outer scf.if and we replace the
2852 // value with a select that considers just the outer condition. Since
2853 // the else region contains just the yield, its yielded value is
2854 // defined outside the scf.if, by definition.
2855
2856 // If the then value is defined within the scf.if, bail.
2857 if (tup.value().getParentRegion() == &op.getThenRegion()) {
2858 return failure();
2859 }
2860 elseYieldsToUpgradeToSelect.push_back(Elt: tup.index());
2861 }
2862
2863 Location loc = op.getLoc();
2864 Value newCondition = arith::AndIOp::create(builder&: rewriter, location: loc, lhs: op.getCondition(),
2865 rhs: nestedIf.getCondition());
2866 auto newIf = IfOp::create(builder&: rewriter, location: loc, resultTypes: op.getResultTypes(), cond: newCondition);
2867 Block *newIfBlock = rewriter.createBlock(parent: &newIf.getThenRegion());
2868
2869 SmallVector<Value> results;
2870 llvm::append_range(C&: results, R: newIf.getResults());
2871 rewriter.setInsertionPoint(newIf);
2872
2873 for (auto idx : elseYieldsToUpgradeToSelect)
2874 results[idx] =
2875 arith::SelectOp::create(builder&: rewriter, location: op.getLoc(), condition: op.getCondition(),
2876 true_value: thenYield[idx], false_value: elseYield[idx]);
2877
2878 rewriter.mergeBlocks(source: nestedIf.thenBlock(), dest: newIfBlock);
2879 rewriter.setInsertionPointToEnd(newIf.thenBlock());
2880 rewriter.replaceOpWithNewOp<YieldOp>(op: newIf.thenYield(), args&: thenYield);
2881 if (!elseYield.empty()) {
2882 rewriter.createBlock(parent: &newIf.getElseRegion());
2883 rewriter.setInsertionPointToEnd(newIf.elseBlock());
2884 YieldOp::create(builder&: rewriter, location: loc, results: elseYield);
2885 }
2886 rewriter.replaceOp(op, newValues: results);
2887 return success();
2888 }
2889};
2890
2891} // namespace
2892
2893void IfOp::getCanonicalizationPatterns(RewritePatternSet &results,
2894 MLIRContext *context) {
2895 results.add<CombineIfs, CombineNestedIfs, ConditionPropagation,
2896 ConvertTrivialIfToSelect, RemoveEmptyElseBranch,
2897 ReplaceIfYieldWithConditionOrValue>(arg&: context);
2898 populateRegionBranchOpInterfaceCanonicalizationPatterns(
2899 patterns&: results, opName: IfOp::getOperationName());
2900 populateRegionBranchOpInterfaceInliningPattern(patterns&: results,
2901 opName: IfOp::getOperationName());
2902}
2903
2904Block *IfOp::thenBlock() { return &getThenRegion().back(); }
2905YieldOp IfOp::thenYield() { return cast<YieldOp>(Val: &thenBlock()->back()); }
2906Block *IfOp::elseBlock() {
2907 Region &r = getElseRegion();
2908 if (r.empty())
2909 return nullptr;
2910 return &r.back();
2911}
2912YieldOp IfOp::elseYield() { return cast<YieldOp>(Val: &elseBlock()->back()); }
2913
2914//===----------------------------------------------------------------------===//
2915// ParallelOp
2916//===----------------------------------------------------------------------===//
2917
2918void ParallelOp::build(
2919 OpBuilder &builder, OperationState &result, ValueRange lowerBounds,
2920 ValueRange upperBounds, ValueRange steps, ValueRange initVals,
2921 function_ref<void(OpBuilder &, Location, ValueRange, ValueRange)>
2922 bodyBuilderFn,
2923 bool unsignedCmp) {
2924 result.addOperands(newOperands: lowerBounds);
2925 result.addOperands(newOperands: upperBounds);
2926 result.addOperands(newOperands: steps);
2927 result.addOperands(newOperands: initVals);
2928 if (unsignedCmp)
2929 result.addAttribute(name: getUnsignedCmpAttrName(name: result.name),
2930 attr: builder.getUnitAttr());
2931 result.addAttribute(
2932 name: ParallelOp::getOperandSegmentSizeAttr(),
2933 attr: builder.getDenseI32ArrayAttr(values: {static_cast<int32_t>(lowerBounds.size()),
2934 static_cast<int32_t>(upperBounds.size()),
2935 static_cast<int32_t>(steps.size()),
2936 static_cast<int32_t>(initVals.size())}));
2937 result.addTypes(newTypes: initVals.getTypes());
2938
2939 OpBuilder::InsertionGuard guard(builder);
2940 unsigned numIVs = steps.size();
2941 SmallVector<Type, 8> argTypes(numIVs, builder.getIndexType());
2942 SmallVector<Location, 8> argLocs(numIVs, result.location);
2943 Region *bodyRegion = result.addRegion();
2944 Block *bodyBlock = builder.createBlock(parent: bodyRegion, insertPt: {}, argTypes, locs: argLocs);
2945
2946 if (bodyBuilderFn) {
2947 builder.setInsertionPointToStart(bodyBlock);
2948 bodyBuilderFn(builder, result.location,
2949 bodyBlock->getArguments().take_front(N: numIVs),
2950 bodyBlock->getArguments().drop_front(N: numIVs));
2951 }
2952 // Add terminator only if there are no reductions.
2953 if (initVals.empty())
2954 ParallelOp::ensureTerminator(region&: *bodyRegion, builder, loc: result.location);
2955}
2956
2957void ParallelOp::build(
2958 OpBuilder &builder, OperationState &result, ValueRange lowerBounds,
2959 ValueRange upperBounds, ValueRange steps,
2960 function_ref<void(OpBuilder &, Location, ValueRange)> bodyBuilderFn,
2961 bool unsignedCmp) {
2962 // Only pass a non-null wrapper if bodyBuilderFn is non-null itself. Make sure
2963 // we don't capture a reference to a temporary by constructing the lambda at
2964 // function level.
2965 auto wrappedBuilderFn = [&bodyBuilderFn](OpBuilder &nestedBuilder,
2966 Location nestedLoc, ValueRange ivs,
2967 ValueRange) {
2968 bodyBuilderFn(nestedBuilder, nestedLoc, ivs);
2969 };
2970 function_ref<void(OpBuilder &, Location, ValueRange, ValueRange)> wrapper;
2971 if (bodyBuilderFn)
2972 wrapper = wrappedBuilderFn;
2973
2974 build(builder, result, lowerBounds, upperBounds, steps, initVals: ValueRange(), bodyBuilderFn: wrapper,
2975 unsignedCmp);
2976}
2977
2978LogicalResult ParallelOp::verify() {
2979 // Check that there is at least one value in lowerBound, upperBound and step.
2980 // It is sufficient to test only step, because it is ensured already that the
2981 // number of elements in lowerBound, upperBound and step are the same.
2982 Operation::operand_range stepValues = getStep();
2983 if (stepValues.empty())
2984 return emitOpError(
2985 message: "needs at least one tuple element for lowerBound, upperBound and step");
2986
2987 // Check whether all constant step values are positive.
2988 for (Value stepValue : stepValues)
2989 if (auto cst = getConstantIntValue(ofr: stepValue))
2990 if (*cst <= 0)
2991 return emitOpError(message: "constant step operand must be positive");
2992
2993 // Check that the body defines the same number of block arguments as the
2994 // number of tuple elements in step.
2995 Block *body = getBody();
2996 if (body->getNumArguments() != stepValues.size())
2997 return emitOpError() << "expects the same number of induction variables: "
2998 << body->getNumArguments()
2999 << " as bound and step values: " << stepValues.size();
3000 for (auto arg : body->getArguments())
3001 if (!arg.getType().isIndex())
3002 return emitOpError(
3003 message: "expects arguments for the induction variable to be of index type");
3004
3005 // Check that the terminator is an scf.reduce op.
3006 auto reduceOp = verifyAndGetTerminator<scf::ReduceOp>(
3007 op: *this, region&: getRegion(), errorMessage: "expects body to terminate with 'scf.reduce'");
3008 if (!reduceOp)
3009 return failure();
3010
3011 // Check that the number of results is the same as the number of reductions.
3012 auto resultsSize = getResults().size();
3013 auto reductionsSize = reduceOp.getReductions().size();
3014 auto initValsSize = getInitVals().size();
3015 if (resultsSize != reductionsSize)
3016 return emitOpError() << "expects number of results: " << resultsSize
3017 << " to be the same as number of reductions: "
3018 << reductionsSize;
3019 if (resultsSize != initValsSize)
3020 return emitOpError() << "expects number of results: " << resultsSize
3021 << " to be the same as number of initial values: "
3022 << initValsSize;
3023 if (reduceOp.getNumOperands() != initValsSize)
3024 // Delegate error reporting to ReduceOp
3025 return success();
3026
3027 // Check that the types of the results and reductions are the same.
3028 for (int64_t i = 0; i < static_cast<int64_t>(reductionsSize); ++i) {
3029 auto resultType = getOperation()->getResult(idx: i).getType();
3030 auto reductionOperandType = reduceOp.getOperands()[i].getType();
3031 if (resultType != reductionOperandType)
3032 return reduceOp.emitOpError()
3033 << "expects type of " << i
3034 << "-th reduction operand: " << reductionOperandType
3035 << " to be the same as the " << i
3036 << "-th result type: " << resultType;
3037 }
3038 return success();
3039}
3040
3041ParseResult ParallelOp::parse(OpAsmParser &parser, OperationState &result) {
3042 auto &builder = parser.getBuilder();
3043 if (succeeded(Result: parser.parseOptionalKeyword(keyword: "unsigned")))
3044 result.addAttribute(name: getUnsignedCmpAttrName(name: result.name),
3045 attr: builder.getUnitAttr());
3046
3047 // Parse an opening `(` followed by induction variables followed by `)`
3048 SmallVector<OpAsmParser::Argument, 4> ivs;
3049 if (parser.parseArgumentList(result&: ivs, delimiter: OpAsmParser::Delimiter::Paren))
3050 return failure();
3051
3052 // Parse loop bounds.
3053 SmallVector<OpAsmParser::UnresolvedOperand, 4> lower;
3054 if (parser.parseEqual() ||
3055 parser.parseOperandList(result&: lower, requiredOperandCount: ivs.size(),
3056 delimiter: OpAsmParser::Delimiter::Paren) ||
3057 parser.resolveOperands(operands&: lower, type: builder.getIndexType(), result&: result.operands))
3058 return failure();
3059
3060 SmallVector<OpAsmParser::UnresolvedOperand, 4> upper;
3061 if (parser.parseKeyword(keyword: "to") ||
3062 parser.parseOperandList(result&: upper, requiredOperandCount: ivs.size(),
3063 delimiter: OpAsmParser::Delimiter::Paren) ||
3064 parser.resolveOperands(operands&: upper, type: builder.getIndexType(), result&: result.operands))
3065 return failure();
3066
3067 // Parse step values.
3068 SmallVector<OpAsmParser::UnresolvedOperand, 4> steps;
3069 if (parser.parseKeyword(keyword: "step") ||
3070 parser.parseOperandList(result&: steps, requiredOperandCount: ivs.size(),
3071 delimiter: OpAsmParser::Delimiter::Paren) ||
3072 parser.resolveOperands(operands&: steps, type: builder.getIndexType(), result&: result.operands))
3073 return failure();
3074
3075 // Parse init values.
3076 SmallVector<OpAsmParser::UnresolvedOperand, 4> initVals;
3077 if (succeeded(Result: parser.parseOptionalKeyword(keyword: "init"))) {
3078 if (parser.parseOperandList(result&: initVals, delimiter: OpAsmParser::Delimiter::Paren))
3079 return failure();
3080 }
3081
3082 // Parse optional results in case there is a reduce.
3083 if (parser.parseOptionalArrowTypeList(result&: result.types))
3084 return failure();
3085
3086 // Now parse the body.
3087 Region *body = result.addRegion();
3088 for (auto &iv : ivs)
3089 iv.type = builder.getIndexType();
3090 if (parser.parseRegion(region&: *body, arguments: ivs))
3091 return failure();
3092
3093 // Set `operandSegmentSizes` attribute.
3094 result.addAttribute(
3095 name: ParallelOp::getOperandSegmentSizeAttr(),
3096 attr: builder.getDenseI32ArrayAttr(values: {static_cast<int32_t>(lower.size()),
3097 static_cast<int32_t>(upper.size()),
3098 static_cast<int32_t>(steps.size()),
3099 static_cast<int32_t>(initVals.size())}));
3100
3101 // Parse attributes.
3102 if (parser.parseOptionalAttrDict(result&: result.attributes) ||
3103 parser.resolveOperands(operands&: initVals, types&: result.types, loc: parser.getNameLoc(),
3104 result&: result.operands))
3105 return failure();
3106
3107 // Add a terminator if none was parsed.
3108 ParallelOp::ensureTerminator(region&: *body, builder, loc: result.location);
3109 return success();
3110}
3111
3112void ParallelOp::print(OpAsmPrinter &p) {
3113 if (getUnsignedCmp())
3114 p << " unsigned";
3115 p << " (" << getBody()->getArguments() << ") = (" << getLowerBound()
3116 << ") to (" << getUpperBound() << ") step (" << getStep() << ")";
3117 if (!getInitVals().empty())
3118 p << " init (" << getInitVals() << ")";
3119 p.printOptionalArrowTypeList(types: getResultTypes());
3120 p << ' ';
3121 p.printRegion(blocks&: getRegion(), /*printEntryBlockArgs=*/false);
3122 p.printOptionalAttrDict(attrs: (*this)->getDiscardableAttrDictionary().getValue());
3123}
3124
3125SmallVector<Region *> ParallelOp::getLoopRegions() { return {&getRegion()}; }
3126
3127std::optional<SmallVector<Value>> ParallelOp::getLoopInductionVars() {
3128 return SmallVector<Value>{getBody()->getArguments()};
3129}
3130
3131std::optional<SmallVector<OpFoldResult>> ParallelOp::getLoopLowerBounds() {
3132 return getLowerBound();
3133}
3134
3135std::optional<SmallVector<OpFoldResult>> ParallelOp::getLoopUpperBounds() {
3136 return getUpperBound();
3137}
3138
3139std::optional<SmallVector<OpFoldResult>> ParallelOp::getLoopSteps() {
3140 return getStep();
3141}
3142
3143ParallelOp mlir::scf::getParallelForInductionVarOwner(Value val) {
3144 auto ivArg = llvm::dyn_cast<BlockArgument>(Val&: val);
3145 if (!ivArg)
3146 return ParallelOp();
3147 assert(ivArg.getOwner() && "unlinked block argument");
3148 auto *containingOp = ivArg.getOwner()->getParentOp();
3149 return dyn_cast<ParallelOp>(Val: containingOp);
3150}
3151
3152namespace {
3153// Collapse loop dimensions that perform a single iteration.
3154struct ParallelOpSingleOrZeroIterationDimsFolder
3155 : public OpRewritePattern<ParallelOp> {
3156 using OpRewritePattern<ParallelOp>::OpRewritePattern;
3157
3158 LogicalResult matchAndRewrite(ParallelOp op,
3159 PatternRewriter &rewriter) const override {
3160 Location loc = op.getLoc();
3161
3162 // Compute new loop bounds that omit all single-iteration loop dimensions.
3163 SmallVector<Value> newLowerBounds, newUpperBounds, newSteps;
3164 IRMapping mapping;
3165 for (auto [lb, ub, step, iv] :
3166 llvm::zip(t: op.getLowerBound(), u: op.getUpperBound(), args: op.getStep(),
3167 args: op.getInductionVars())) {
3168 auto numIterations = constantTripCount(lb, ub, step, isSigned: !op.getUnsignedCmp(),
3169 computeUbMinusLb);
3170 if (numIterations.has_value()) {
3171 // Remove the loop if it performs zero iterations.
3172 if (*numIterations == 0) {
3173 rewriter.replaceOp(op, newValues: op.getInitVals());
3174 return success();
3175 }
3176 // Replace the loop induction variable by the lower bound if the loop
3177 // performs a single iteration. Otherwise, copy the loop bounds.
3178 if (*numIterations == 1) {
3179 mapping.map(from: iv, to: getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: lb));
3180 continue;
3181 }
3182 }
3183 newLowerBounds.push_back(Elt: lb);
3184 newUpperBounds.push_back(Elt: ub);
3185 newSteps.push_back(Elt: step);
3186 }
3187 // Exit if none of the loop dimensions perform a single iteration.
3188 if (newLowerBounds.size() == op.getLowerBound().size())
3189 return failure();
3190
3191 if (newLowerBounds.empty()) {
3192 // All of the loop dimensions perform a single iteration. Inline
3193 // loop body and nested ReduceOp's
3194 SmallVector<Value> results;
3195 results.reserve(N: op.getInitVals().size());
3196 for (auto &bodyOp : op.getBody()->without_terminator())
3197 rewriter.clone(op&: bodyOp, mapper&: mapping);
3198 auto reduceOp = cast<ReduceOp>(Val: op.getBody()->getTerminator());
3199 for (int64_t i = 0, e = reduceOp.getReductions().size(); i < e; ++i) {
3200 Block &reduceBlock = reduceOp.getReductions()[i].front();
3201 auto initValIndex = results.size();
3202 mapping.map(from: reduceBlock.getArgument(i: 0), to: op.getInitVals()[initValIndex]);
3203 mapping.map(from: reduceBlock.getArgument(i: 1),
3204 to: mapping.lookupOrDefault(from: reduceOp.getOperands()[i]));
3205 for (auto &reduceBodyOp : reduceBlock.without_terminator())
3206 rewriter.clone(op&: reduceBodyOp, mapper&: mapping);
3207
3208 auto result = mapping.lookupOrDefault(
3209 from: cast<ReduceReturnOp>(Val: reduceBlock.getTerminator()).getResult());
3210 results.push_back(Elt: result);
3211 }
3212
3213 rewriter.replaceOp(op, newValues: results);
3214 return success();
3215 }
3216 // Replace the parallel loop by lower-dimensional parallel loop.
3217 auto newOp = ParallelOp::create(builder&: rewriter, location: op.getLoc(), lowerBounds: newLowerBounds,
3218 upperBounds: newUpperBounds, steps: newSteps, initVals: op.getInitVals(),
3219 bodyBuilderFn: nullptr, unsignedCmp: op.getUnsignedCmp());
3220 // Erase the empty block that was inserted by the builder.
3221 rewriter.eraseBlock(block: newOp.getBody());
3222 // Clone the loop body and remap the block arguments of the collapsed loops
3223 // (inlining does not support a cancellable block argument mapping).
3224 rewriter.cloneRegionBefore(region&: op.getRegion(), parent&: newOp.getRegion(),
3225 before: newOp.getRegion().begin(), mapping);
3226 rewriter.replaceOp(op, newValues: newOp.getResults());
3227 return success();
3228 }
3229};
3230
3231struct MergeNestedParallelLoops : public OpRewritePattern<ParallelOp> {
3232 using OpRewritePattern<ParallelOp>::OpRewritePattern;
3233
3234 LogicalResult matchAndRewrite(ParallelOp op,
3235 PatternRewriter &rewriter) const override {
3236 Block &outerBody = *op.getBody();
3237 if (!llvm::hasSingleElement(C: outerBody.without_terminator()))
3238 return failure();
3239
3240 auto innerOp = dyn_cast<ParallelOp>(Val&: outerBody.front());
3241 if (!innerOp)
3242 return failure();
3243
3244 if (op.getUnsignedCmp() != innerOp.getUnsignedCmp())
3245 return failure();
3246
3247 for (auto val : outerBody.getArguments())
3248 if (llvm::is_contained(Range: innerOp.getLowerBound(), Element: val) ||
3249 llvm::is_contained(Range: innerOp.getUpperBound(), Element: val) ||
3250 llvm::is_contained(Range: innerOp.getStep(), Element: val))
3251 return failure();
3252
3253 // Reductions are not supported yet.
3254 if (!op.getInitVals().empty() || !innerOp.getInitVals().empty())
3255 return failure();
3256
3257 auto bodyBuilder = [&](OpBuilder &builder, Location /*loc*/,
3258 ValueRange iterVals, ValueRange) {
3259 Block &innerBody = *innerOp.getBody();
3260 assert(iterVals.size() ==
3261 (outerBody.getNumArguments() + innerBody.getNumArguments()));
3262 IRMapping mapping;
3263 mapping.map(from: outerBody.getArguments(),
3264 to: iterVals.take_front(n: outerBody.getNumArguments()));
3265 mapping.map(from: innerBody.getArguments(),
3266 to: iterVals.take_back(n: innerBody.getNumArguments()));
3267 for (Operation &op : innerBody.without_terminator())
3268 builder.clone(op, mapper&: mapping);
3269 };
3270
3271 auto concatValues = [](const auto &first, const auto &second) {
3272 SmallVector<Value> ret;
3273 ret.reserve(N: first.size() + second.size());
3274 ret.assign(first.begin(), first.end());
3275 ret.append(second.begin(), second.end());
3276 return ret;
3277 };
3278
3279 auto newLowerBounds =
3280 concatValues(op.getLowerBound(), innerOp.getLowerBound());
3281 auto newUpperBounds =
3282 concatValues(op.getUpperBound(), innerOp.getUpperBound());
3283 auto newSteps = concatValues(op.getStep(), innerOp.getStep());
3284
3285 rewriter.replaceOpWithNewOp<ParallelOp>(op, args&: newLowerBounds, args&: newUpperBounds,
3286 args&: newSteps, args: ValueRange(),
3287 args&: bodyBuilder);
3288 return success();
3289 }
3290};
3291
3292} // namespace
3293
3294void ParallelOp::getCanonicalizationPatterns(RewritePatternSet &results,
3295 MLIRContext *context) {
3296 results
3297 .add<ParallelOpSingleOrZeroIterationDimsFolder, MergeNestedParallelLoops>(
3298 arg&: context);
3299}
3300
3301/// Given the region at `index`, or the parent operation if `index` is None,
3302/// return the successor regions. These are the regions that may be selected
3303/// during the flow of control. `operands` is a set of optional attributes that
3304/// correspond to a constant value for each operand, or null if that operand is
3305/// not a constant.
3306void ParallelOp::getSuccessorRegions(
3307 RegionBranchPoint point, SmallVectorImpl<RegionSuccessor> &regions) {
3308 // Both the operation itself and the region may be branching into the body or
3309 // back into the operation itself. It is possible for loop not to enter the
3310 // body.
3311 regions.push_back(Elt: RegionSuccessor(&getRegion()));
3312 regions.push_back(Elt: RegionSuccessor(getOperation()));
3313}
3314
3315//===----------------------------------------------------------------------===//
3316// ReduceOp
3317//===----------------------------------------------------------------------===//
3318
3319void ReduceOp::build(OpBuilder &builder, OperationState &result) {}
3320
3321void ReduceOp::build(OpBuilder &builder, OperationState &result,
3322 ValueRange operands) {
3323 result.addOperands(newOperands: operands);
3324 for (Value v : operands) {
3325 OpBuilder::InsertionGuard guard(builder);
3326 Region *bodyRegion = result.addRegion();
3327 builder.createBlock(parent: bodyRegion, insertPt: {},
3328 argTypes: ArrayRef<Type>{v.getType(), v.getType()},
3329 locs: {result.location, result.location});
3330 }
3331}
3332
3333LogicalResult ReduceOp::verifyRegions() {
3334 if (getReductions().size() != getOperands().size())
3335 return emitOpError() << "expects number of reduction regions: "
3336 << getReductions().size()
3337 << " to be the same as number of reduction operands: "
3338 << getOperands().size();
3339 // The region of a ReduceOp has two arguments of the same type as its
3340 // corresponding operand.
3341 for (int64_t i = 0, e = getReductions().size(); i < e; ++i) {
3342 auto type = getOperands()[i].getType();
3343 Block &block = getReductions()[i].front();
3344 if (block.empty())
3345 return emitOpError() << i << "-th reduction has an empty body";
3346 if (block.getNumArguments() != 2 ||
3347 llvm::any_of(Range: block.getArguments(), P: [&](const BlockArgument &arg) {
3348 return arg.getType() != type;
3349 }))
3350 return emitOpError() << "expected two block arguments with type " << type
3351 << " in the " << i << "-th reduction region";
3352
3353 // Check that the block is terminated by a ReduceReturnOp.
3354 if (!isa<ReduceReturnOp>(Val: block.getTerminator()))
3355 return emitOpError(message: "reduction bodies must be terminated with an "
3356 "'scf.reduce.return' op");
3357 }
3358
3359 return success();
3360}
3361
3362MutableOperandRange
3363ReduceOp::getMutableSuccessorOperands(RegionSuccessor point) {
3364 // No operands are forwarded to the next iteration.
3365 return MutableOperandRange(getOperation(), /*start=*/0, /*length=*/0);
3366}
3367
3368//===----------------------------------------------------------------------===//
3369// ReduceReturnOp
3370//===----------------------------------------------------------------------===//
3371
3372LogicalResult ReduceReturnOp::verify() {
3373 // The type of the return value should be the same type as the types of the
3374 // block arguments of the reduction body.
3375 Block *reductionBody = getOperation()->getBlock();
3376 // Should already be verified by an op trait.
3377 assert(isa<ReduceOp>(reductionBody->getParentOp()) && "expected scf.reduce");
3378 Type expectedResultType = reductionBody->getArgument(i: 0).getType();
3379 if (expectedResultType != getResult().getType())
3380 return emitOpError() << "must have type " << expectedResultType
3381 << " (the type of the reduction inputs)";
3382 return success();
3383}
3384
3385//===----------------------------------------------------------------------===//
3386// WhileOp
3387//===----------------------------------------------------------------------===//
3388
3389void WhileOp::build(::mlir::OpBuilder &odsBuilder,
3390 ::mlir::OperationState &odsState, TypeRange resultTypes,
3391 ValueRange inits, BodyBuilderFn beforeBuilder,
3392 BodyBuilderFn afterBuilder) {
3393 odsState.addOperands(newOperands: inits);
3394 odsState.addTypes(newTypes&: resultTypes);
3395
3396 OpBuilder::InsertionGuard guard(odsBuilder);
3397
3398 // Build before region.
3399 SmallVector<Location, 4> beforeArgLocs;
3400 beforeArgLocs.reserve(N: inits.size());
3401 for (Value operand : inits) {
3402 beforeArgLocs.push_back(Elt: operand.getLoc());
3403 }
3404
3405 Region *beforeRegion = odsState.addRegion();
3406 Block *beforeBlock = odsBuilder.createBlock(parent: beforeRegion, /*insertPt=*/{},
3407 argTypes: inits.getTypes(), locs: beforeArgLocs);
3408 if (beforeBuilder)
3409 beforeBuilder(odsBuilder, odsState.location, beforeBlock->getArguments());
3410
3411 // Build after region.
3412 SmallVector<Location, 4> afterArgLocs(resultTypes.size(), odsState.location);
3413
3414 Region *afterRegion = odsState.addRegion();
3415 Block *afterBlock = odsBuilder.createBlock(parent: afterRegion, /*insertPt=*/{},
3416 argTypes: resultTypes, locs: afterArgLocs);
3417
3418 if (afterBuilder)
3419 afterBuilder(odsBuilder, odsState.location, afterBlock->getArguments());
3420}
3421
3422ConditionOp WhileOp::getConditionOp() {
3423 return cast<ConditionOp>(Val: getBeforeBody()->getTerminator());
3424}
3425
3426YieldOp WhileOp::getYieldOp() {
3427 return cast<YieldOp>(Val: getAfterBody()->getTerminator());
3428}
3429
3430std::optional<MutableArrayRef<OpOperand>> WhileOp::getYieldedValuesMutable() {
3431 return getYieldOp().getResultsMutable();
3432}
3433
3434Block::BlockArgListType WhileOp::getBeforeArguments() {
3435 return getBeforeBody()->getArguments();
3436}
3437
3438Block::BlockArgListType WhileOp::getAfterArguments() {
3439 return getAfterBody()->getArguments();
3440}
3441
3442Block::BlockArgListType WhileOp::getRegionIterArgs() {
3443 return getBeforeArguments();
3444}
3445
3446OperandRange WhileOp::getEntrySuccessorOperands(RegionSuccessor successor) {
3447 assert(successor.getSuccessor() == &getBefore() &&
3448 "WhileOp is expected to branch only to the first region");
3449 return getInits();
3450}
3451
3452void WhileOp::getSuccessorRegions(RegionBranchPoint point,
3453 SmallVectorImpl<RegionSuccessor> &regions) {
3454 // The parent op always branches to the condition region.
3455 if (point.isParent()) {
3456 regions.emplace_back(Args: &getBefore());
3457 return;
3458 }
3459
3460 assert(llvm::is_contained(
3461 {&getAfter(), &getBefore()},
3462 point.getTerminatorPredecessorOrNull()->getParentRegion()) &&
3463 "there are only two regions in a WhileOp");
3464 // The body region always branches back to the condition region.
3465 if (point.getTerminatorPredecessorOrNull()->getParentRegion() ==
3466 &getAfter()) {
3467 regions.emplace_back(Args: &getBefore());
3468 return;
3469 }
3470
3471 regions.push_back(Elt: RegionSuccessor(getOperation()));
3472 regions.emplace_back(Args: &getAfter());
3473}
3474
3475ValueRange WhileOp::getSuccessorInputs(RegionSuccessor successor) {
3476 if (successor.isOperation())
3477 return getOperation()->getResults();
3478 if (successor == &getBefore())
3479 return getBefore().getArguments();
3480 if (successor == &getAfter())
3481 return getAfter().getArguments();
3482 llvm_unreachable("invalid region successor");
3483}
3484
3485SmallVector<Region *> WhileOp::getLoopRegions() {
3486 return {&getBefore(), &getAfter()};
3487}
3488
3489/// Parses a `while` op.
3490///
3491/// op ::= `scf.while` assignments `:` function-type region `do` region
3492/// `attributes` attribute-dict
3493/// initializer ::= /* empty */ | `(` assignment-list `)`
3494/// assignment-list ::= assignment | assignment `,` assignment-list
3495/// assignment ::= ssa-value `=` ssa-value
3496ParseResult scf::WhileOp::parse(OpAsmParser &parser, OperationState &result) {
3497 SmallVector<OpAsmParser::Argument, 4> regionArgs;
3498 SmallVector<OpAsmParser::UnresolvedOperand, 4> operands;
3499 Region *before = result.addRegion();
3500 Region *after = result.addRegion();
3501
3502 OptionalParseResult listResult =
3503 parser.parseOptionalAssignmentList(lhs&: regionArgs, rhs&: operands);
3504 if (listResult.has_value() && failed(Result: listResult.value()))
3505 return failure();
3506
3507 FunctionType functionType;
3508 SMLoc typeLoc = parser.getCurrentLocation();
3509 if (failed(Result: parser.parseColonType(result&: functionType)))
3510 return failure();
3511
3512 result.addTypes(newTypes: functionType.getResults());
3513
3514 if (functionType.getNumInputs() != operands.size()) {
3515 return parser.emitError(loc: typeLoc)
3516 << "expected as many input types as operands " << "(expected "
3517 << operands.size() << " got " << functionType.getNumInputs() << ")";
3518 }
3519
3520 // Resolve input operands.
3521 if (failed(Result: parser.resolveOperands(operands, types: functionType.getInputs(),
3522 loc: parser.getCurrentLocation(),
3523 result&: result.operands)))
3524 return failure();
3525
3526 // Propagate the types into the region arguments.
3527 for (size_t i = 0, e = regionArgs.size(); i != e; ++i)
3528 regionArgs[i].type = functionType.getInput(i);
3529
3530 return failure(IsFailure: parser.parseRegion(region&: *before, arguments: regionArgs) ||
3531 parser.parseKeyword(keyword: "do") || parser.parseRegion(region&: *after) ||
3532 parser.parseOptionalAttrDictWithKeyword(result&: result.attributes));
3533}
3534
3535/// Prints a `while` op.
3536void scf::WhileOp::print(OpAsmPrinter &p) {
3537 printInitializationList(p, blocksArgs: getBeforeArguments(), initializers: getInits(), prefix: " ");
3538 p << " : ";
3539 p.printFunctionalType(inputs: getInits().getTypes(), results: getResults().getTypes());
3540 p << ' ';
3541 p.printRegion(blocks&: getBefore(), /*printEntryBlockArgs=*/false);
3542 p << " do ";
3543 p.printRegion(blocks&: getAfter());
3544 p.printOptionalAttrDictWithKeyword(
3545 attrs: (*this)->getDiscardableAttrDictionary().getValue());
3546}
3547
3548LogicalResult scf::WhileOp::verify() {
3549 auto beforeTerminator = verifyAndGetTerminator<scf::ConditionOp>(
3550 op: *this, region&: getBefore(),
3551 errorMessage: "expects the 'before' region to terminate with 'scf.condition'");
3552 if (!beforeTerminator)
3553 return failure();
3554
3555 auto afterTerminator = verifyAndGetTerminator<scf::YieldOp>(
3556 op: *this, region&: getAfter(),
3557 errorMessage: "expects the 'after' region to terminate with 'scf.yield'");
3558 return success(IsSuccess: afterTerminator != nullptr);
3559}
3560
3561namespace {
3562/// Move a scf.if op that is directly before the scf.condition op in the while
3563/// before region, and whose condition matches the condition of the
3564/// scf.condition op, down into the while after region.
3565///
3566/// scf.while (..) : (...) -> ... {
3567/// %additional_used_values = ...
3568/// %cond = ...
3569/// ...
3570/// %res = scf.if %cond -> (...) {
3571/// use(%additional_used_values)
3572/// ... // then block
3573/// scf.yield %then_value
3574/// } else {
3575/// scf.yield %else_value
3576/// }
3577/// scf.condition(%cond) %res, ...
3578/// } do {
3579/// ^bb0(%res_arg, ...):
3580/// use(%res_arg)
3581/// ...
3582///
3583/// becomes
3584/// scf.while (..) : (...) -> ... {
3585/// %additional_used_values = ...
3586/// %cond = ...
3587/// ...
3588/// scf.condition(%cond) %else_value, ..., %additional_used_values
3589/// } do {
3590/// ^bb0(%res_arg ..., %additional_args): :
3591/// use(%additional_args)
3592/// ... // if then block
3593/// use(%then_value)
3594/// ...
3595struct WhileMoveIfDown : public OpRewritePattern<scf::WhileOp> {
3596 using OpRewritePattern<scf::WhileOp>::OpRewritePattern;
3597
3598 LogicalResult matchAndRewrite(scf::WhileOp op,
3599 PatternRewriter &rewriter) const override {
3600 auto conditionOp = op.getConditionOp();
3601
3602 // Only support ifOp right before the condition at the moment. Relaxing this
3603 // would require to:
3604 // - check that the body does not have side-effects conflicting with
3605 // operations between the if and the condition.
3606 // - check that results of the if operation are only used as arguments to
3607 // the condition.
3608 auto ifOp = dyn_cast_or_null<scf::IfOp>(Val: conditionOp->getPrevNode());
3609
3610 // Check that the ifOp is directly before the conditionOp and that it
3611 // matches the condition of the conditionOp. Also ensure that the ifOp has
3612 // no else block with content, as that would complicate the transformation.
3613 // TODO: support else blocks with content.
3614 if (!ifOp || ifOp.getCondition() != conditionOp.getCondition() ||
3615 (ifOp.elseBlock() && !ifOp.elseBlock()->without_terminator().empty()))
3616 return failure();
3617
3618 assert((ifOp->use_empty() || (llvm::all_equal(ifOp->getUsers()) &&
3619 *ifOp->user_begin() == conditionOp)) &&
3620 "ifOp has unexpected uses");
3621
3622 Location loc = op.getLoc();
3623
3624 // Replace uses of ifOp results in the conditionOp with the yielded values
3625 // from the ifOp branches: the after-region argument takes the `then` value,
3626 // while the condition operand -- which becomes a while result once the
3627 // condition is false -- takes the `else` value.
3628 //
3629 // The same ifOp result may be forwarded to several condition operands, so
3630 // assign into the specific operand instead of replacing all uses of the
3631 // ifOp result, which would also rewrite the operands not yet visited.
3632 for (auto [idx, arg] : llvm::enumerate(First: conditionOp.getArgs())) {
3633 auto it = llvm::find(Range: ifOp->getResults(), Val: arg);
3634 if (it == ifOp->getResults().end())
3635 continue;
3636 size_t ifOpIdx = it.getIndex();
3637 rewriter.replaceAllUsesWith(from: op.getAfterArguments()[idx],
3638 to: ifOp.thenYield()->getOperand(idx: ifOpIdx));
3639 unsigned argIdx = idx;
3640 Value elseValue = ifOp.elseYield()->getOperand(idx: ifOpIdx);
3641 rewriter.modifyOpInPlace(root: conditionOp, callable: [&] {
3642 conditionOp.getArgsMutable()[argIdx].assign(value: elseValue);
3643 });
3644 }
3645
3646 // Collect additional used values from before region.
3647 SetVector<Value> additionalUsedValuesSet;
3648 visitUsedValuesDefinedAbove(regions: ifOp.getThenRegion(), callback: [&](OpOperand *operand) {
3649 if (&op.getBefore() == operand->get().getParentRegion())
3650 additionalUsedValuesSet.insert(X: operand->get());
3651 });
3652
3653 // Create new whileOp with additional used values as results.
3654 auto additionalUsedValues = additionalUsedValuesSet.getArrayRef();
3655 auto additionalValueTypes = llvm::map_to_vector(
3656 C&: additionalUsedValues, F: [](Value val) { return val.getType(); });
3657 size_t additionalValueSize = additionalUsedValues.size();
3658 SmallVector<Type> newResultTypes(op.getResultTypes());
3659 newResultTypes.append(RHS: additionalValueTypes);
3660
3661 auto newWhileOp =
3662 scf::WhileOp::create(builder&: rewriter, location: loc, resultTypes: newResultTypes, operands: op.getInits());
3663
3664 rewriter.modifyOpInPlace(root: newWhileOp, callable: [&] {
3665 newWhileOp.getBefore().takeBody(other&: op.getBefore());
3666 newWhileOp.getAfter().takeBody(other&: op.getAfter());
3667 newWhileOp.getAfter().addArguments(
3668 types: additionalValueTypes,
3669 locs: SmallVector<Location>(additionalValueSize, loc));
3670 });
3671
3672 rewriter.modifyOpInPlace(root: conditionOp, callable: [&] {
3673 conditionOp.getArgsMutable().append(values: additionalUsedValues);
3674 });
3675
3676 // Replace uses of additional used values inside the ifOp then region with
3677 // the whileOp after region arguments.
3678 rewriter.replaceUsesWithIf(
3679 from: additionalUsedValues,
3680 to: newWhileOp.getAfterArguments().take_back(N: additionalValueSize),
3681 functor: [&](OpOperand &use) {
3682 return ifOp.getThenRegion().isAncestor(
3683 other: use.getOwner()->getParentRegion());
3684 });
3685
3686 // Inline ifOp then region into new whileOp after region.
3687 rewriter.eraseOp(op: ifOp.thenYield());
3688 rewriter.inlineBlockBefore(source: ifOp.thenBlock(), dest: newWhileOp.getAfterBody(),
3689 before: newWhileOp.getAfterBody()->begin());
3690 rewriter.eraseOp(op: ifOp);
3691 rewriter.replaceOp(op,
3692 newValues: newWhileOp->getResults().drop_back(n: additionalValueSize));
3693 return success();
3694 }
3695};
3696
3697/// Replace uses of the condition within the do block with true, since otherwise
3698/// the block would not be evaluated.
3699///
3700/// scf.while (..) : (i1, ...) -> ... {
3701/// %condition = call @evaluate_condition() : () -> i1
3702/// scf.condition(%condition) %condition : i1, ...
3703/// } do {
3704/// ^bb0(%arg0: i1, ...):
3705/// use(%arg0)
3706/// ...
3707///
3708/// becomes
3709/// scf.while (..) : (i1, ...) -> ... {
3710/// %condition = call @evaluate_condition() : () -> i1
3711/// scf.condition(%condition) %condition : i1, ...
3712/// } do {
3713/// ^bb0(%arg0: i1, ...):
3714/// use(%true)
3715/// ...
3716struct WhileConditionTruth : public OpRewritePattern<WhileOp> {
3717 using OpRewritePattern<WhileOp>::OpRewritePattern;
3718
3719 LogicalResult matchAndRewrite(WhileOp op,
3720 PatternRewriter &rewriter) const override {
3721 auto term = op.getConditionOp();
3722
3723 // These variables serve to prevent creating duplicate constants
3724 // and hold constant true or false values.
3725 Value constantTrue = nullptr;
3726
3727 bool replaced = false;
3728 for (auto yieldedAndBlockArgs :
3729 llvm::zip(t: term.getArgs(), u: op.getAfterArguments())) {
3730 if (std::get<0>(t&: yieldedAndBlockArgs) == term.getCondition()) {
3731 if (!std::get<1>(t&: yieldedAndBlockArgs).use_empty()) {
3732 if (!constantTrue)
3733 constantTrue = arith::ConstantOp::create(
3734 builder&: rewriter, location: op.getLoc(), result: term.getCondition().getType(),
3735 value: rewriter.getBoolAttr(value: true));
3736
3737 rewriter.replaceAllUsesWith(from: std::get<1>(t&: yieldedAndBlockArgs),
3738 to: constantTrue);
3739 replaced = true;
3740 }
3741 }
3742 }
3743 return success(IsSuccess: replaced);
3744 }
3745};
3746
3747/// Replace operations equivalent to the condition in the do block with true,
3748/// since otherwise the block would not be evaluated.
3749///
3750/// scf.while (..) : (i32, ...) -> ... {
3751/// %z = ... : i32
3752/// %condition = cmpi pred %z, %a
3753/// scf.condition(%condition) %z : i32, ...
3754/// } do {
3755/// ^bb0(%arg0: i32, ...):
3756/// %condition2 = cmpi pred %arg0, %a
3757/// use(%condition2)
3758/// ...
3759///
3760/// becomes
3761/// scf.while (..) : (i32, ...) -> ... {
3762/// %z = ... : i32
3763/// %condition = cmpi pred %z, %a
3764/// scf.condition(%condition) %z : i32, ...
3765/// } do {
3766/// ^bb0(%arg0: i32, ...):
3767/// use(%true)
3768/// ...
3769struct WhileCmpCond : public OpRewritePattern<scf::WhileOp> {
3770 using OpRewritePattern<scf::WhileOp>::OpRewritePattern;
3771
3772 LogicalResult matchAndRewrite(scf::WhileOp op,
3773 PatternRewriter &rewriter) const override {
3774 using namespace scf;
3775 auto cond = op.getConditionOp();
3776 auto cmp = cond.getCondition().getDefiningOp<arith::CmpIOp>();
3777 if (!cmp)
3778 return failure();
3779 bool changed = false;
3780 for (auto tup : llvm::zip(t: cond.getArgs(), u: op.getAfterArguments())) {
3781 for (size_t opIdx = 0; opIdx < 2; opIdx++) {
3782 if (std::get<0>(t&: tup) != cmp.getOperand(i: opIdx))
3783 continue;
3784 for (OpOperand &u :
3785 llvm::make_early_inc_range(Range: std::get<1>(t&: tup).getUses())) {
3786 auto cmp2 = dyn_cast<arith::CmpIOp>(Val: u.getOwner());
3787 if (!cmp2)
3788 continue;
3789 // For a binary operator 1-opIdx gets the other side.
3790 if (cmp2.getOperand(i: 1 - opIdx) != cmp.getOperand(i: 1 - opIdx))
3791 continue;
3792 bool samePredicate;
3793 if (cmp2.getPredicate() == cmp.getPredicate())
3794 samePredicate = true;
3795 else if (cmp2.getPredicate() ==
3796 arith::invertPredicate(pred: cmp.getPredicate()))
3797 samePredicate = false;
3798 else
3799 continue;
3800
3801 rewriter.replaceOpWithNewOp<arith::ConstantIntOp>(op: cmp2, args&: samePredicate,
3802 args: 1);
3803 changed = true;
3804 }
3805 }
3806 }
3807 return success(IsSuccess: changed);
3808 }
3809};
3810
3811/// If both ranges contain same values return mappping indices from args2 to
3812/// args1. Otherwise return std::nullopt.
3813static std::optional<SmallVector<unsigned>> getArgsMapping(ValueRange args1,
3814 ValueRange args2) {
3815 if (args1.size() != args2.size())
3816 return std::nullopt;
3817
3818 SmallVector<unsigned> ret(args1.size());
3819 for (auto &&[i, arg1] : llvm::enumerate(First&: args1)) {
3820 auto it = llvm::find(Range&: args2, Val: arg1);
3821 if (it == args2.end())
3822 return std::nullopt;
3823
3824 ret[std::distance(first: args2.begin(), last: it)] = static_cast<unsigned>(i);
3825 }
3826
3827 return ret;
3828}
3829
3830static bool hasDuplicates(ValueRange args) {
3831 llvm::SmallDenseSet<Value> set;
3832 for (Value arg : args) {
3833 if (!set.insert(V: arg).second)
3834 return true;
3835 }
3836 return false;
3837}
3838
3839/// If `before` block args are directly forwarded to `scf.condition`, rearrange
3840/// `scf.condition` args into same order as block args. Update `after` block
3841/// args and op result values accordingly.
3842/// Needed to simplify `scf.while` -> `scf.for` uplifting.
3843struct WhileOpAlignBeforeArgs : public OpRewritePattern<WhileOp> {
3844 using Base::Base;
3845
3846 LogicalResult matchAndRewrite(WhileOp loop,
3847 PatternRewriter &rewriter) const override {
3848 auto *oldBefore = loop.getBeforeBody();
3849 ConditionOp oldTerm = loop.getConditionOp();
3850 ValueRange beforeArgs = oldBefore->getArguments();
3851 ValueRange termArgs = oldTerm.getArgs();
3852 if (beforeArgs == termArgs)
3853 return failure();
3854
3855 if (hasDuplicates(args: termArgs))
3856 return failure();
3857
3858 auto mapping = getArgsMapping(args1: beforeArgs, args2: termArgs);
3859 if (!mapping)
3860 return failure();
3861
3862 {
3863 OpBuilder::InsertionGuard g(rewriter);
3864 rewriter.setInsertionPoint(oldTerm);
3865 rewriter.replaceOpWithNewOp<ConditionOp>(op: oldTerm, args: oldTerm.getCondition(),
3866 args&: beforeArgs);
3867 }
3868
3869 auto *oldAfter = loop.getAfterBody();
3870
3871 SmallVector<Type> newResultTypes(beforeArgs.size());
3872 for (auto &&[i, j] : llvm::enumerate(First&: *mapping))
3873 newResultTypes[j] = loop.getResult(i).getType();
3874
3875 auto newLoop = WhileOp::create(
3876 builder&: rewriter, location: loop.getLoc(), resultTypes: newResultTypes, inits: loop.getInits(),
3877 /*beforeBuilder=*/nullptr, /*afterBuilder=*/nullptr);
3878 auto *newBefore = newLoop.getBeforeBody();
3879 auto *newAfter = newLoop.getAfterBody();
3880
3881 SmallVector<Value> newResults(beforeArgs.size());
3882 SmallVector<Value> newAfterArgs(beforeArgs.size());
3883 for (auto &&[i, j] : llvm::enumerate(First&: *mapping)) {
3884 newResults[i] = newLoop.getResult(i: j);
3885 newAfterArgs[i] = newAfter->getArgument(i: j);
3886 }
3887
3888 rewriter.inlineBlockBefore(source: oldBefore, dest: newBefore, before: newBefore->begin(),
3889 argValues: newBefore->getArguments());
3890 rewriter.inlineBlockBefore(source: oldAfter, dest: newAfter, before: newAfter->begin(),
3891 argValues: newAfterArgs);
3892
3893 rewriter.replaceOp(op: loop, newValues: newResults);
3894 return success();
3895 }
3896};
3897} // namespace
3898
3899void WhileOp::getCanonicalizationPatterns(RewritePatternSet &results,
3900 MLIRContext *context) {
3901 results.add<WhileConditionTruth, WhileCmpCond, WhileOpAlignBeforeArgs,
3902 WhileMoveIfDown>(arg&: context);
3903 populateRegionBranchOpInterfaceCanonicalizationPatterns(
3904 patterns&: results, opName: WhileOp::getOperationName());
3905 populateRegionBranchOpInterfaceInliningPattern(patterns&: results,
3906 opName: WhileOp::getOperationName());
3907}
3908
3909//===----------------------------------------------------------------------===//
3910// IndexSwitchOp
3911//===----------------------------------------------------------------------===//
3912
3913/// Parse the case regions and values.
3914static ParseResult
3915parseSwitchCases(OpAsmParser &p, DenseI64ArrayAttr &cases,
3916 SmallVectorImpl<std::unique_ptr<Region>> &caseRegions) {
3917 SmallVector<int64_t> caseValues;
3918 while (succeeded(Result: p.parseOptionalKeyword(keyword: "case"))) {
3919 int64_t value;
3920 Region &region = *caseRegions.emplace_back(Args: std::make_unique<Region>());
3921 if (p.parseInteger(result&: value) || p.parseRegion(region, /*arguments=*/{}))
3922 return failure();
3923 caseValues.push_back(Elt: value);
3924 }
3925 cases = p.getBuilder().getDenseI64ArrayAttr(values: caseValues);
3926 return success();
3927}
3928
3929/// Print the case regions and values.
3930static void printSwitchCases(OpAsmPrinter &p, Operation *op,
3931 DenseI64ArrayAttr cases, RegionRange caseRegions) {
3932 for (auto [value, region] : llvm::zip(t: cases.asArrayRef(), u&: caseRegions)) {
3933 p.printNewline();
3934 p << "case " << value << ' ';
3935 p.printRegion(blocks&: *region, /*printEntryBlockArgs=*/false);
3936 }
3937}
3938
3939LogicalResult scf::IndexSwitchOp::verify() {
3940 if (getCases().size() != getCaseRegions().size()) {
3941 return emitOpError(message: "has ")
3942 << getCaseRegions().size() << " case regions but "
3943 << getCases().size() << " case values";
3944 }
3945
3946 DenseSet<int64_t> valueSet;
3947 for (int64_t value : getCases())
3948 if (!valueSet.insert(V: value).second)
3949 return emitOpError(message: "has duplicate case value: ") << value;
3950 auto verifyRegion = [&](Region &region, const Twine &name) -> LogicalResult {
3951 auto yield = dyn_cast<YieldOp>(Val&: region.front().back());
3952 if (!yield)
3953 return emitOpError(message: "expected region to end with scf.yield, but got ")
3954 << region.front().back().getName();
3955
3956 if (yield.getNumOperands() != getNumResults()) {
3957 return (emitOpError(message: "expected each region to return ")
3958 << getNumResults() << " values, but " << name << " returns "
3959 << yield.getNumOperands())
3960 .attachNote(noteLoc: yield.getLoc())
3961 << "see yield operation here";
3962 }
3963 for (auto [idx, result, operand] :
3964 llvm::enumerate(First: getResultTypes(), Rest: yield.getOperands())) {
3965 if (!operand)
3966 return yield.emitOpError() << "operand " << idx << " is null\n";
3967 if (result == operand.getType())
3968 continue;
3969 return (emitOpError(message: "expected result #")
3970 << idx << " of each region to be " << result)
3971 .attachNote(noteLoc: yield.getLoc())
3972 << name << " returns " << operand.getType() << " here";
3973 }
3974 return success();
3975 };
3976
3977 if (failed(Result: verifyRegion(getDefaultRegion(), "default region")))
3978 return failure();
3979 for (auto [idx, caseRegion] : llvm::enumerate(First: getCaseRegions()))
3980 if (failed(Result: verifyRegion(caseRegion, "case region #" + Twine(idx))))
3981 return failure();
3982
3983 return success();
3984}
3985
3986unsigned scf::IndexSwitchOp::getNumCases() { return getCases().size(); }
3987
3988Block &scf::IndexSwitchOp::getDefaultBlock() {
3989 return getDefaultRegion().front();
3990}
3991
3992Block &scf::IndexSwitchOp::getCaseBlock(unsigned idx) {
3993 assert(idx < getNumCases() && "case index out-of-bounds");
3994 return getCaseRegions()[idx].front();
3995}
3996
3997void IndexSwitchOp::getSuccessorRegions(
3998 RegionBranchPoint point, SmallVectorImpl<RegionSuccessor> &successors) {
3999 // All regions branch back to the parent op.
4000 if (!point.isParent()) {
4001 successors.push_back(Elt: RegionSuccessor(getOperation()));
4002 return;
4003 }
4004
4005 llvm::append_range(C&: successors, R: getRegions());
4006}
4007
4008ValueRange IndexSwitchOp::getSuccessorInputs(RegionSuccessor successor) {
4009 return successor.isOperation() ? ValueRange(getOperation()->getResults())
4010 : ValueRange();
4011}
4012
4013void IndexSwitchOp::getEntrySuccessorRegions(
4014 ArrayRef<Attribute> operands,
4015 SmallVectorImpl<RegionSuccessor> &successors) {
4016 FoldAdaptor adaptor(operands, *this);
4017
4018 // If a constant was not provided, all regions are possible successors.
4019 auto arg = dyn_cast_or_null<IntegerAttr>(Val: adaptor.getArg());
4020 if (!arg) {
4021 llvm::append_range(C&: successors, R: getRegions());
4022 return;
4023 }
4024
4025 // Otherwise, try to find a case with a matching value. If not, the
4026 // default region is the only successor.
4027 for (auto [caseValue, caseRegion] : llvm::zip(t: getCases(), u: getCaseRegions())) {
4028 if (caseValue == arg.getInt()) {
4029 successors.emplace_back(Args: &caseRegion);
4030 return;
4031 }
4032 }
4033 successors.emplace_back(Args: &getDefaultRegion());
4034}
4035
4036void IndexSwitchOp::getRegionInvocationBounds(
4037 ArrayRef<Attribute> operands, SmallVectorImpl<InvocationBounds> &bounds) {
4038 auto operandValue = llvm::dyn_cast_or_null<IntegerAttr>(Val: operands.front());
4039 if (!operandValue) {
4040 // All regions are invoked at most once.
4041 bounds.append(NumInputs: getNumRegions(), Elt: InvocationBounds(/*lb=*/0, /*ub=*/1));
4042 return;
4043 }
4044
4045 unsigned liveIndex = getNumRegions() - 1;
4046 const auto *it = llvm::find(Range: getCases(), Val: operandValue.getInt());
4047 if (it != getCases().end())
4048 liveIndex = std::distance(first: getCases().begin(), last: it);
4049 for (unsigned i = 0, e = getNumRegions(); i < e; ++i)
4050 bounds.emplace_back(/*lb=*/Args: 0, /*ub=*/Args: i == liveIndex);
4051}
4052
4053void IndexSwitchOp::getCanonicalizationPatterns(RewritePatternSet &results,
4054 MLIRContext *context) {
4055 populateRegionBranchOpInterfaceCanonicalizationPatterns(
4056 patterns&: results, opName: IndexSwitchOp::getOperationName());
4057 populateRegionBranchOpInterfaceInliningPattern(
4058 patterns&: results, opName: IndexSwitchOp::getOperationName());
4059}
4060
4061//===----------------------------------------------------------------------===//
4062// TableGen'd op method definitions
4063//===----------------------------------------------------------------------===//
4064
4065#define GET_OP_CLASSES
4066#include "mlir/Dialect/SCF/IR/SCFOps.cpp.inc"
4067