1//===- BufferizableOpInterfaceImpl.cpp - Impl. of BufferizableOpInterface -===//
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/Transforms/BufferizableOpInterfaceImpl.h"
10
11#include "mlir/Dialect/Bufferization/IR/BufferizableOpInterface.h"
12#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
13#include "mlir/Dialect/Bufferization/IR/UnstructuredControlFlow.h"
14#include "mlir/Dialect/Bufferization/Transforms/Bufferize.h"
15#include "mlir/Dialect/Bufferization/Transforms/OneShotAnalysis.h"
16#include "mlir/Dialect/MemRef/IR/MemRef.h"
17#include "mlir/Dialect/SCF/IR/SCF.h"
18#include "mlir/Dialect/Utils/StaticValueUtils.h"
19#include "mlir/IR/Dialect.h"
20#include "mlir/IR/Operation.h"
21#include "mlir/IR/PatternMatch.h"
22#include "llvm/ADT/SmallVectorExtras.h"
23
24using namespace mlir;
25using namespace mlir::bufferization;
26using namespace mlir::scf;
27
28namespace mlir {
29namespace scf {
30namespace {
31
32/// Helper function for loop bufferization. Cast the given buffer to the given
33/// memref type.
34static Value castBuffer(OpBuilder &b, Value buffer, Type type,
35 const BufferizationOptions &options) {
36 // If the buffer already has the correct type, no cast is needed.
37 if (buffer.getType() == type)
38 return buffer;
39
40 return *options.castFn(b, buffer.getLoc(), type, buffer);
41}
42
43/// Helper function for loop bufferization. Return "true" if the given value
44/// is guaranteed to not alias with an external tensor apart from values in
45/// `exceptions`. A value is external if it is defined outside of the given
46/// region or if it is an entry block argument of the region.
47static bool doesNotAliasExternalValue(Value value, Region *region,
48 ValueRange exceptions,
49 const OneShotAnalysisState &state) {
50 assert(region->hasOneBlock() && "expected region with single block");
51 bool result = true;
52 state.applyOnAliases(v: value, fun: [&](Value alias) {
53 if (llvm::is_contained(Range&: exceptions, Element: alias))
54 return;
55 Region *aliasRegion = alias.getParentRegion();
56 if (isa<BlockArgument>(Val: alias) && !region->isProperAncestor(other: aliasRegion))
57 result = false;
58 if (isa<OpResult>(Val: alias) && !region->isAncestor(other: aliasRegion))
59 result = false;
60 });
61 return result;
62}
63
64/// Bufferization of scf.condition.
65struct ConditionOpInterface
66 : public BufferizableOpInterface::ExternalModel<ConditionOpInterface,
67 scf::ConditionOp> {
68 bool bufferizesToMemoryRead(Operation *op, OpOperand &opOperand,
69 const AnalysisState &state) const {
70 return true;
71 }
72
73 bool bufferizesToMemoryWrite(Operation *op, OpOperand &opOperand,
74 const AnalysisState &state) const {
75 return false;
76 }
77
78 AliasingValueList getAliasingValues(Operation *op, OpOperand &opOperand,
79 const AnalysisState &state) const {
80 return {};
81 }
82
83 bool mustBufferizeInPlace(Operation *op, OpOperand &opOperand,
84 const AnalysisState &state) const {
85 // Condition operands always bufferize inplace. Otherwise, an alloc + copy
86 // may be generated inside the block. We should not return/yield allocations
87 // when possible.
88 return true;
89 }
90
91 LogicalResult bufferize(Operation *op, RewriterBase &rewriter,
92 const BufferizationOptions &options,
93 BufferizationState &state) const {
94 auto conditionOp = cast<scf::ConditionOp>(Val: op);
95 auto whileOp = cast<scf::WhileOp>(Val: conditionOp->getParentOp());
96
97 SmallVector<Value> newArgs;
98 for (const auto &it : llvm::enumerate(First: conditionOp.getArgs())) {
99 Value value = it.value();
100 if (isa<TensorLikeType>(Val: value.getType())) {
101 FailureOr<Value> maybeBuffer =
102 getBuffer(rewriter, value, options, state);
103 if (failed(Result: maybeBuffer))
104 return failure();
105 FailureOr<BufferLikeType> resultType = bufferization::getBufferType(
106 value: whileOp.getAfterArguments()[it.index()], options, state);
107 if (failed(Result: resultType))
108 return failure();
109 Value buffer = castBuffer(b&: rewriter, buffer: *maybeBuffer, type: *resultType, options);
110 newArgs.push_back(Elt: buffer);
111 } else {
112 newArgs.push_back(Elt: value);
113 }
114 }
115
116 replaceOpWithNewBufferizedOp<scf::ConditionOp>(
117 rewriter, op, args: conditionOp.getCondition(), args&: newArgs);
118 return success();
119 }
120};
121
122/// Return the unique scf.yield op. If there are multiple or no scf.yield ops,
123/// return an empty op.
124static scf::YieldOp getUniqueYieldOp(scf::ExecuteRegionOp executeRegionOp) {
125 scf::YieldOp result;
126 for (Block &block : executeRegionOp.getRegion()) {
127 if (auto yieldOp = dyn_cast<scf::YieldOp>(Val: block.getTerminator())) {
128 if (result)
129 return {};
130 result = yieldOp;
131 }
132 }
133 return result;
134}
135
136/// Bufferization of scf.execute_region. Can be analyzed, but bufferization not
137/// fully implemented at the moment.
138struct ExecuteRegionOpInterface
139 : public OpWithUnstructuredControlFlowBufferizableOpInterfaceExternalModel<
140 ExecuteRegionOpInterface, scf::ExecuteRegionOp> {
141
142 static bool supportsUnstructuredControlFlow() { return true; }
143
144 bool isWritable(Operation *op, Value value,
145 const AnalysisState &state) const {
146 return true;
147 }
148
149 LogicalResult verifyAnalysis(Operation *op,
150 const AnalysisState &state) const {
151 auto executeRegionOp = cast<scf::ExecuteRegionOp>(Val: op);
152 // TODO: scf.execute_region with multiple yields are not supported.
153 if (!getUniqueYieldOp(executeRegionOp))
154 return op->emitOpError(message: "op without unique scf.yield is not supported");
155 return success();
156 }
157
158 AliasingOpOperandList
159 getAliasingOpOperands(Operation *op, Value value,
160 const AnalysisState &state) const {
161 if (auto bbArg = dyn_cast<BlockArgument>(Val&: value))
162 return getAliasingBranchOpOperands(op, bbArg, state);
163
164 // ExecuteRegionOps do not have tensor OpOperands. The yielded value can be
165 // any SSA value that is in scope. To allow for use-def chain traversal
166 // through ExecuteRegionOps in the analysis, the corresponding yield value
167 // is considered to be aliasing with the result.
168 auto executeRegionOp = cast<scf::ExecuteRegionOp>(Val: op);
169 auto it = llvm::find(Range: op->getOpResults(), Val: value);
170 assert(it != op->getOpResults().end() && "invalid value");
171 size_t resultNum = std::distance(first: op->getOpResults().begin(), last: it);
172 auto yieldOp = getUniqueYieldOp(executeRegionOp);
173 // Note: If there is no unique scf.yield op, `verifyAnalysis` will fail.
174 if (!yieldOp)
175 return {};
176 return {{&yieldOp->getOpOperand(idx: resultNum), BufferRelation::Equivalent}};
177 }
178
179 LogicalResult bufferize(Operation *op, RewriterBase &rewriter,
180 const BufferizationOptions &options,
181 BufferizationState &state) const {
182 auto executeRegionOp = cast<scf::ExecuteRegionOp>(Val: op);
183 auto yieldOp = getUniqueYieldOp(executeRegionOp);
184 TypeRange newResultTypes(yieldOp.getResults());
185
186 // Create new op and move over region.
187 auto newOp = scf::ExecuteRegionOp::create(
188 builder&: rewriter, location: op->getLoc(), resultType0: newResultTypes, no_inline: executeRegionOp.getNoInline());
189 newOp.getRegion().takeBody(other&: executeRegionOp.getRegion());
190
191 // Bufferize every block.
192 for (Block &block : newOp.getRegion())
193 if (failed(Result: bufferization::bufferizeBlockSignature(block: &block, rewriter,
194 options, state)))
195 return failure();
196
197 // Update all uses of the old op.
198 rewriter.setInsertionPointAfter(newOp);
199 SmallVector<Value> newResults;
200 for (const auto &it : llvm::enumerate(First: executeRegionOp->getResultTypes())) {
201 if (isa<TensorLikeType>(Val: it.value())) {
202 newResults.push_back(Elt: bufferization::ToTensorOp::create(
203 builder&: rewriter, location: executeRegionOp.getLoc(), result: it.value(),
204 buffer: newOp->getResult(idx: it.index())));
205 } else {
206 newResults.push_back(Elt: newOp->getResult(idx: it.index()));
207 }
208 }
209
210 // Replace old op.
211 rewriter.replaceOp(op: executeRegionOp, newValues: newResults);
212
213 return success();
214 }
215};
216
217/// Bufferization of scf.if. Replace with a new scf.if that yields memrefs.
218struct IfOpInterface
219 : public BufferizableOpInterface::ExternalModel<IfOpInterface, scf::IfOp> {
220 AliasingOpOperandList
221 getAliasingOpOperands(Operation *op, Value value,
222 const AnalysisState &state) const {
223 // IfOps do not have tensor OpOperands. The yielded value can be any SSA
224 // value that is in scope. To allow for use-def chain traversal through
225 // IfOps in the analysis, both corresponding yield values from the then/else
226 // branches are considered to be aliasing with the result.
227 auto ifOp = cast<scf::IfOp>(Val: op);
228 size_t resultNum = std::distance(first: op->getOpResults().begin(),
229 last: llvm::find(Range: op->getOpResults(), Val: value));
230 OpOperand *thenOperand = &ifOp.thenYield()->getOpOperand(idx: resultNum);
231 OpOperand *elseOperand = &ifOp.elseYield()->getOpOperand(idx: resultNum);
232 return {{thenOperand, BufferRelation::Equivalent, /*isDefinite=*/false},
233 {elseOperand, BufferRelation::Equivalent, /*isDefinite=*/false}};
234 }
235
236 LogicalResult bufferize(Operation *op, RewriterBase &rewriter,
237 const BufferizationOptions &options,
238 BufferizationState &state) const {
239 OpBuilder::InsertionGuard g(rewriter);
240 auto ifOp = cast<scf::IfOp>(Val: op);
241
242 // Compute bufferized result types.
243 SmallVector<Type> newTypes;
244 for (Value result : ifOp.getResults()) {
245 if (!isa<TensorLikeType>(Val: result.getType())) {
246 newTypes.push_back(Elt: result.getType());
247 continue;
248 }
249 auto bufferType = bufferization::getBufferType(value: result, options, state);
250 if (failed(Result: bufferType))
251 return failure();
252 newTypes.push_back(Elt: *bufferType);
253 }
254
255 // Create new op.
256 rewriter.setInsertionPoint(ifOp);
257 auto newIfOp = scf::IfOp::create(builder&: rewriter, location: ifOp.getLoc(), resultTypes: newTypes,
258 cond: ifOp.getCondition(),
259 /*withElseRegion=*/true);
260
261 // Move over then/else blocks.
262 rewriter.mergeBlocks(source: ifOp.thenBlock(), dest: newIfOp.thenBlock());
263 rewriter.mergeBlocks(source: ifOp.elseBlock(), dest: newIfOp.elseBlock());
264
265 // Replace op results.
266 replaceOpWithBufferizedValues(rewriter, op, values: newIfOp->getResults());
267
268 return success();
269 }
270
271 FailureOr<BufferLikeType>
272 getBufferType(Operation *op, Value value, const BufferizationOptions &options,
273 const BufferizationState &state,
274 SmallVector<Value> &invocationStack) const {
275 auto ifOp = cast<scf::IfOp>(Val: op);
276 auto thenYieldOp = cast<scf::YieldOp>(Val: ifOp.thenBlock()->getTerminator());
277 auto elseYieldOp = cast<scf::YieldOp>(Val: ifOp.elseBlock()->getTerminator());
278 assert(value.getDefiningOp() == op && "invalid valid");
279
280 // Determine buffer types of the true/false branches.
281 auto opResult = cast<OpResult>(Val&: value);
282 auto thenValue = thenYieldOp.getOperand(i: opResult.getResultNumber());
283 auto elseValue = elseYieldOp.getOperand(i: opResult.getResultNumber());
284 BufferLikeType thenBufferType, elseBufferType;
285 if (isa<BufferLikeType>(Val: thenValue.getType())) {
286 // True branch was already bufferized.
287 thenBufferType = cast<BufferLikeType>(Val: thenValue.getType());
288 } else {
289 auto maybeBufferType = bufferization::getBufferType(
290 value: thenValue, options, state, invocationStack);
291 if (failed(Result: maybeBufferType))
292 return failure();
293 thenBufferType = *maybeBufferType;
294 }
295 if (isa<BufferLikeType>(Val: elseValue.getType())) {
296 // False branch was already bufferized.
297 elseBufferType = cast<BufferLikeType>(Val: elseValue.getType());
298 } else {
299 auto maybeBufferType = bufferization::getBufferType(
300 value: elseValue, options, state, invocationStack);
301 if (failed(Result: maybeBufferType))
302 return failure();
303 elseBufferType = *maybeBufferType;
304 }
305
306 // Best case: Both branches have the exact same buffer type.
307 if (thenBufferType == elseBufferType)
308 return cast<BufferLikeType>(Val&: thenBufferType);
309
310 auto reconciled = options.reconcileBufferTypeMismatchFn(
311 thenBufferType, elseBufferType, options);
312 if (failed(Result: reconciled))
313 return op->emitError(message: "incompatible buffer types on then/else branches");
314
315 return *reconciled;
316 }
317};
318
319/// Bufferization of scf.index_switch. Replace with a new scf.index_switch that
320/// yields memrefs.
321struct IndexSwitchOpInterface
322 : public BufferizableOpInterface::ExternalModel<IndexSwitchOpInterface,
323 scf::IndexSwitchOp> {
324 AliasingOpOperandList
325 getAliasingOpOperands(Operation *op, Value value,
326 const AnalysisState &state) const {
327 // IndexSwitchOps do not have tensor OpOperands. The yielded value can be
328 // any SSA. This is similar to IfOps.
329 auto switchOp = cast<scf::IndexSwitchOp>(Val: op);
330 int64_t resultNum = cast<OpResult>(Val&: value).getResultNumber();
331 AliasingOpOperandList result;
332 for (int64_t i = 0, numCases = switchOp.getNumCases(); i < numCases; ++i) {
333 auto yieldOp =
334 cast<scf::YieldOp>(Val: switchOp.getCaseBlock(idx: i).getTerminator());
335 result.addAlias(alias: AliasingOpOperand(&yieldOp->getOpOperand(idx: resultNum),
336 BufferRelation::Equivalent,
337 /*isDefinite=*/false));
338 }
339 auto defaultYieldOp =
340 cast<scf::YieldOp>(Val: switchOp.getDefaultBlock().getTerminator());
341 result.addAlias(alias: AliasingOpOperand(&defaultYieldOp->getOpOperand(idx: resultNum),
342 BufferRelation::Equivalent,
343 /*isDefinite=*/false));
344 return result;
345 }
346
347 LogicalResult bufferize(Operation *op, RewriterBase &rewriter,
348 const BufferizationOptions &options,
349 BufferizationState &state) const {
350 OpBuilder::InsertionGuard g(rewriter);
351 auto switchOp = cast<scf::IndexSwitchOp>(Val: op);
352
353 // Compute bufferized result types.
354 SmallVector<Type> newTypes;
355 for (Value result : switchOp.getResults()) {
356 if (!isa<TensorLikeType>(Val: result.getType())) {
357 newTypes.push_back(Elt: result.getType());
358 continue;
359 }
360 auto bufferType = bufferization::getBufferType(value: result, options, state);
361 if (failed(Result: bufferType))
362 return failure();
363 newTypes.push_back(Elt: *bufferType);
364 }
365
366 // Create new op.
367 rewriter.setInsertionPoint(switchOp);
368 auto newSwitchOp = scf::IndexSwitchOp::create(
369 builder&: rewriter, location: switchOp.getLoc(), results: newTypes, arg: switchOp.getArg(),
370 cases: switchOp.getCases(), caseRegionsCount: switchOp.getCases().size());
371
372 // Move over blocks.
373 for (auto [src, dest] :
374 llvm::zip(t: switchOp.getCaseRegions(), u: newSwitchOp.getCaseRegions()))
375 rewriter.inlineRegionBefore(region&: src, parent&: dest, before: dest.begin());
376 rewriter.inlineRegionBefore(region&: switchOp.getDefaultRegion(),
377 parent&: newSwitchOp.getDefaultRegion(),
378 before: newSwitchOp.getDefaultRegion().begin());
379
380 // Replace op results.
381 replaceOpWithBufferizedValues(rewriter, op, values: newSwitchOp->getResults());
382
383 return success();
384 }
385
386 FailureOr<BufferLikeType>
387 getBufferType(Operation *op, Value value, const BufferizationOptions &options,
388 const BufferizationState &state,
389 SmallVector<Value> &invocationStack) const {
390 auto switchOp = cast<scf::IndexSwitchOp>(Val: op);
391 assert(value.getDefiningOp() == op && "invalid value");
392 int64_t resultNum = cast<OpResult>(Val&: value).getResultNumber();
393
394 auto getYieldedBufferType = [&](Block &b) -> FailureOr<BufferLikeType> {
395 auto yieldOp = cast<scf::YieldOp>(Val: b.getTerminator());
396 Value yieldedValue = yieldOp->getOperand(idx: resultNum);
397 if (auto bufferType = dyn_cast<BufferLikeType>(Val: yieldedValue.getType()))
398 return bufferType;
399 return bufferization::getBufferType(value: yieldedValue, options, state,
400 invocationStack);
401 };
402
403 // Compute buffer type of the default case.
404 auto maybeBufferType = getYieldedBufferType(switchOp.getDefaultBlock());
405 if (failed(Result: maybeBufferType))
406 return failure();
407 BufferLikeType bufferType = *maybeBufferType;
408
409 // Compute buffer types of all other cases.
410 for (int64_t i = 0, numCases = switchOp.getNumCases(); i < numCases; ++i) {
411 auto yieldedBufferType = getYieldedBufferType(switchOp.getCaseBlock(idx: i));
412 if (failed(Result: yieldedBufferType))
413 return failure();
414
415 // Best case: Both branches have the exact same buffer type.
416 if (bufferType == *yieldedBufferType)
417 continue;
418
419 auto reconciled = options.reconcileBufferTypeMismatchFn(
420 bufferType, *yieldedBufferType, options);
421 if (failed(Result: reconciled))
422 return op->emitError(message: "incompatible buffer types on switch cases");
423 bufferType = *reconciled;
424 }
425
426 return cast<BufferLikeType>(Val&: bufferType);
427 }
428};
429
430/// Helper function for loop bufferization. Return the indices of all values
431/// that have a tensor type.
432static DenseSet<int64_t> getTensorIndices(ValueRange values) {
433 DenseSet<int64_t> result;
434 for (const auto &it : llvm::enumerate(First&: values))
435 if (isa<TensorLikeType>(Val: it.value().getType()))
436 result.insert(V: it.index());
437 return result;
438}
439
440/// Helper function for loop bufferization. Return the indices of all
441/// bbArg/yielded value pairs who's buffer relation is "Equivalent".
442DenseSet<int64_t> getEquivalentBuffers(Block::BlockArgListType bbArgs,
443 ValueRange yieldedValues,
444 const AnalysisState &state) {
445 unsigned int minSize = std::min(a: bbArgs.size(), b: yieldedValues.size());
446 DenseSet<int64_t> result;
447 for (unsigned int i = 0; i < minSize; ++i) {
448 if (!isa<TensorLikeType>(Val: bbArgs[i].getType()) ||
449 !isa<TensorLikeType>(Val: yieldedValues[i].getType()))
450 continue;
451 if (state.areEquivalentBufferizedValues(v1: bbArgs[i], v2: yieldedValues[i]))
452 result.insert(V: i);
453 }
454 return result;
455}
456
457/// Helper function for loop bufferization. Return the bufferized values of the
458/// given OpOperands. If an operand is not a tensor, return the original value.
459static FailureOr<SmallVector<Value>>
460getBuffers(RewriterBase &rewriter, const MutableOperandRange &operands,
461 const BufferizationOptions &options, BufferizationState &state) {
462 SmallVector<Value> result;
463 for (OpOperand &opOperand : operands) {
464 if (isa<TensorLikeType>(Val: opOperand.get().getType())) {
465 FailureOr<Value> resultBuffer =
466 getBuffer(rewriter, value: opOperand.get(), options, state);
467 if (failed(Result: resultBuffer))
468 return failure();
469 result.push_back(Elt: *resultBuffer);
470 } else {
471 result.push_back(Elt: opOperand.get());
472 }
473 }
474 return result;
475}
476
477/// Helper function for loop bufferization. Given a list of bbArgs of the new
478/// (bufferized) loop op, wrap the bufferized tensor args (now memrefs) into
479/// ToTensorOps, so that the block body can be moved over to the new op.
480static SmallVector<Value>
481getBbArgReplacements(RewriterBase &rewriter, Block::BlockArgListType bbArgs,
482 Block::BlockArgListType oldBbArgs,
483 const DenseSet<int64_t> &tensorIndices) {
484 SmallVector<Value> result;
485 for (const auto &it : llvm::enumerate(First&: bbArgs)) {
486 size_t idx = it.index();
487 Value val = it.value();
488 if (tensorIndices.contains(V: idx)) {
489 result.push_back(
490 Elt: bufferization::ToTensorOp::create(builder&: rewriter, location: val.getLoc(),
491 result: oldBbArgs[idx].getType(), buffer: val)
492 .getResult());
493 } else {
494 result.push_back(Elt: val);
495 }
496 }
497 return result;
498}
499
500/// Compute the bufferized type of a loop iter_arg. This type must be equal to
501/// the bufferized type of the corresponding init_arg and the bufferized type
502/// of the corresponding yielded value.
503///
504/// This function uses bufferization::getBufferType to compute the bufferized
505/// type of the init_arg and of the yielded value. (The computation of the
506/// bufferized yielded value type usually requires computing the bufferized type
507/// of the iter_arg again; the implementation of getBufferType traces back the
508/// use-def chain of the given value and computes a buffer type along the way.)
509/// If both buffer types are equal, no casts are needed the computed buffer type
510/// can be used directly. Otherwise, the buffer types can only differ in their
511/// layout map and a cast must be inserted.
512static FailureOr<BufferLikeType> computeLoopRegionIterArgBufferType(
513 Operation *loopOp, BlockArgument iterArg, Value initArg, Value yieldedValue,
514 const BufferizationOptions &options, const BufferizationState &state,
515 SmallVector<Value> &invocationStack) {
516 // Determine the buffer type of the init_arg.
517 auto initArgBufferType =
518 bufferization::getBufferType(value: initArg, options, state, invocationStack);
519 if (failed(Result: initArgBufferType))
520 return failure();
521
522 if (llvm::count(Range&: invocationStack, Element: iterArg) >= 2) {
523 // If the iter_arg is already twice on the invocation stack, just take the
524 // type of the init_arg. This is to avoid infinite loops when calculating
525 // the buffer type. This will most likely result in computing a memref type
526 // with a fully dynamic layout map.
527
528 // Note: For more precise layout map computation, a fixpoint iteration could
529 // be done (i.e., re-computing the yielded buffer type until the bufferized
530 // iter_arg type no longer changes). This current implementation immediately
531 // switches to a fully dynamic layout map when a mismatch between bufferized
532 // init_arg type and bufferized yield value type is detected.
533 return *initArgBufferType;
534 }
535
536 // Compute the buffer type of the yielded value.
537 BufferLikeType yieldedValueBufferType;
538 if (auto bufferType = dyn_cast<BufferLikeType>(Val: yieldedValue.getType())) {
539 // scf.yield was already bufferized.
540 yieldedValueBufferType = bufferType;
541 } else {
542 // Note: This typically triggers a recursive call for the buffer type of
543 // the iter_arg.
544 auto maybeBufferType = bufferization::getBufferType(value: yieldedValue, options,
545 state, invocationStack);
546 if (failed(Result: maybeBufferType))
547 return failure();
548 yieldedValueBufferType = *maybeBufferType;
549 }
550
551 // If yielded type and init_arg type are the same, use that type directly.
552 if (*initArgBufferType == yieldedValueBufferType)
553 return yieldedValueBufferType;
554
555 // If there is a mismatch between the yielded buffer type and the init_arg
556 // buffer type, the buffer type must be reconciled.
557#ifndef NDEBUG
558 if (auto iterTensorType = dyn_cast<TensorLikeType>(iterArg.getType())) {
559 const auto emitOpError = [&]() { return loopOp->emitOpError(); };
560 assert(succeeded(iterTensorType.verifyCompatibleBufferType(
561 yieldedValueBufferType, emitOpError)) &&
562 "incompatible yielded type");
563 assert(succeeded(iterTensorType.verifyCompatibleBufferType(
564 *initArgBufferType, emitOpError)) &&
565 "incompatible init_arg type");
566 }
567#endif // NDEBUG
568
569 auto reconciled = options.reconcileBufferTypeMismatchFn(
570 *initArgBufferType, yieldedValueBufferType, options);
571 if (failed(Result: reconciled)) {
572 return loopOp->emitError(
573 message: "init_arg and yielded value bufferize to incompatible buffer types");
574 }
575
576 return *reconciled;
577}
578
579/// Return `true` if the given loop may have 0 iterations.
580bool mayHaveZeroIterations(scf::ForOp forOp) {
581 std::optional<int64_t> lb = getConstantIntValue(ofr: forOp.getLowerBound());
582 std::optional<int64_t> ub = getConstantIntValue(ofr: forOp.getUpperBound());
583 if (!lb.has_value() || !ub.has_value())
584 return true;
585 return *ub <= *lb;
586}
587
588/// Bufferization of scf.for. Replace with a new scf.for that operates on
589/// memrefs.
590struct ForOpInterface
591 : public BufferizableOpInterface::ExternalModel<ForOpInterface,
592 scf::ForOp> {
593 bool bufferizesToMemoryRead(Operation *op, OpOperand &opOperand,
594 const AnalysisState &state) const {
595 auto forOp = cast<scf::ForOp>(Val: op);
596
597 // If the loop has zero iterations, the results of the op are their
598 // corresponding init_args, meaning that the init_args bufferize to a read.
599 if (mayHaveZeroIterations(forOp))
600 return true;
601
602 // scf::ForOp alone doesn't bufferize to a memory read, one of the uses of
603 // its matching bbArg may.
604 return state.isValueRead(value: forOp.getTiedLoopRegionIterArg(opOperand: &opOperand));
605 }
606
607 bool bufferizesToMemoryWrite(Operation *op, OpOperand &opOperand,
608 const AnalysisState &state) const {
609 // Tensor iter_args of scf::ForOps are always considered as a write.
610 return true;
611 }
612
613 AliasingValueList getAliasingValues(Operation *op, OpOperand &opOperand,
614 const AnalysisState &state) const {
615 auto forOp = cast<scf::ForOp>(Val: op);
616 OpResult opResult = forOp.getTiedLoopResult(opOperand: &opOperand);
617 BufferRelation relation = bufferRelation(op, opResult, state);
618 return {{opResult, relation,
619 /*isDefinite=*/relation == BufferRelation::Equivalent}};
620 }
621
622 BufferRelation bufferRelation(Operation *op, OpResult opResult,
623 const AnalysisState &state) const {
624 // ForOp results are equivalent to their corresponding init_args if the
625 // corresponding iter_args and yield values are equivalent.
626 auto forOp = cast<scf::ForOp>(Val: op);
627 BlockArgument bbArg = forOp.getTiedLoopRegionIterArg(opResult);
628 bool equivalentYield = state.areEquivalentBufferizedValues(
629 v1: bbArg, v2: forOp.getTiedLoopYieldedValue(bbArg)->get());
630 return equivalentYield ? BufferRelation::Equivalent
631 : BufferRelation::Unknown;
632 }
633
634 bool isWritable(Operation *op, Value value,
635 const AnalysisState &state) const {
636 // Interestingly, scf::ForOp's bbArg can **always** be viewed
637 // inplace from the perspective of ops nested under:
638 // 1. Either the matching iter operand is not bufferized inplace and an
639 // alloc + optional copy makes the bbArg itself inplaceable.
640 // 2. Or the matching iter operand is bufferized inplace and bbArg just
641 // bufferizes to that too.
642 return true;
643 }
644
645 LogicalResult
646 resolveConflicts(Operation *op, RewriterBase &rewriter,
647 const AnalysisState &analysisState,
648 const BufferizationState &bufferizationState) const {
649 auto bufferizableOp = cast<BufferizableOpInterface>(Val: op);
650 if (failed(Result: bufferizableOp.resolveTensorOpOperandConflicts(
651 rewriter, analysisState, bufferizationState)))
652 return failure();
653
654 if (analysisState.getOptions().copyBeforeWrite)
655 return success();
656
657 // According to the `getAliasing...` implementations, a bufferized OpResult
658 // may alias only with the corresponding bufferized init_arg (or with a
659 // newly allocated buffer) and not with other buffers defined outside of the
660 // loop. I.e., the i-th OpResult may alias with the i-th init_arg;
661 // but not with any other OpOperand.
662 auto forOp = cast<scf::ForOp>(Val: op);
663 auto yieldOp = cast<scf::YieldOp>(Val: forOp.getBody()->getTerminator());
664 OpBuilder::InsertionGuard g(rewriter);
665 rewriter.setInsertionPoint(yieldOp);
666
667 // Indices of all iter_args that have tensor type. These are the ones that
668 // are bufferized.
669 DenseSet<int64_t> indices = getTensorIndices(values: forOp.getInitArgs());
670 // For every yielded value, does it alias with something defined outside of
671 // the loop?
672 SmallVector<Value> yieldValues;
673 for (const auto it : llvm::enumerate(First: yieldOp.getResults())) {
674 // Note: `state` is guaranteed to be a `OneShotAnalysisState`, but this
675 // type cannot be used in the signature of `resolveConflicts` because the
676 // op interface is in the "IR" build unit and the `OneShotAnalysisState`
677 // is defined in the "Transforms" build unit.
678 if (!indices.contains(V: it.index()) ||
679 doesNotAliasExternalValue(
680 value: it.value(), region: &forOp.getRegion(),
681 /*exceptions=*/forOp.getRegionIterArg(index: it.index()),
682 state: static_cast<const OneShotAnalysisState &>(analysisState))) {
683 yieldValues.push_back(Elt: it.value());
684 continue;
685 }
686 FailureOr<Value> alloc = allocateTensorForShapedValue(
687 b&: rewriter, loc: yieldOp.getLoc(), shapedValue: it.value(), options: analysisState.getOptions(),
688 state: bufferizationState);
689 if (failed(Result: alloc))
690 return failure();
691 yieldValues.push_back(Elt: *alloc);
692 }
693
694 rewriter.modifyOpInPlace(
695 root: yieldOp, callable: [&]() { yieldOp.getResultsMutable().assign(values: yieldValues); });
696 return success();
697 }
698
699 FailureOr<BufferLikeType>
700 getBufferType(Operation *op, Value value, const BufferizationOptions &options,
701 const BufferizationState &state,
702 SmallVector<Value> &invocationStack) const {
703 auto forOp = cast<scf::ForOp>(Val: op);
704 assert(getOwnerOfValue(value) == op && "invalid value");
705 assert(isa<TensorLikeType>(value.getType()) && "expected tensor type");
706
707 if (auto opResult = dyn_cast<OpResult>(Val&: value)) {
708 // The type of an OpResult must match the corresponding iter_arg type.
709 BlockArgument bbArg = forOp.getTiedLoopRegionIterArg(opResult);
710 return bufferization::getBufferType(value: bbArg, options, state,
711 invocationStack);
712 }
713
714 // Compute result/argument number.
715 BlockArgument bbArg = cast<BlockArgument>(Val&: value);
716 unsigned resultNum = forOp.getTiedLoopResult(bbArg).getResultNumber();
717
718 // Compute the bufferized type.
719 auto yieldOp = cast<scf::YieldOp>(Val: forOp.getBody()->getTerminator());
720 Value yieldedValue = yieldOp.getOperand(i: resultNum);
721 BlockArgument iterArg = forOp.getRegionIterArgs()[resultNum];
722 Value initArg = forOp.getInitArgs()[resultNum];
723 return computeLoopRegionIterArgBufferType(
724 loopOp: op, iterArg, initArg, yieldedValue, options, state, invocationStack);
725 }
726
727 LogicalResult bufferize(Operation *op, RewriterBase &rewriter,
728 const BufferizationOptions &options,
729 BufferizationState &state) const {
730 auto forOp = cast<scf::ForOp>(Val: op);
731 Block *oldLoopBody = forOp.getBody();
732
733 // Indices of all iter_args that have tensor type. These are the ones that
734 // are bufferized.
735 DenseSet<int64_t> indices = getTensorIndices(values: forOp.getInitArgs());
736
737 // The new memref init_args of the loop.
738 FailureOr<SmallVector<Value>> maybeInitArgs =
739 getBuffers(rewriter, operands: forOp.getInitArgsMutable(), options, state);
740 if (failed(Result: maybeInitArgs))
741 return failure();
742 SmallVector<Value> initArgs = *maybeInitArgs;
743
744 // Cast init_args if necessary.
745 SmallVector<Value> castedInitArgs;
746 for (const auto &it : llvm::enumerate(First&: initArgs)) {
747 Value initArg = it.value();
748 Value result = forOp->getResult(idx: it.index());
749 // If the type is not a tensor, bufferization doesn't need to touch it.
750 if (!isa<TensorLikeType>(Val: result.getType())) {
751 castedInitArgs.push_back(Elt: initArg);
752 continue;
753 }
754 auto targetType = bufferization::getBufferType(value: result, options, state);
755 if (failed(Result: targetType))
756 return failure();
757 castedInitArgs.push_back(
758 Elt: castBuffer(b&: rewriter, buffer: initArg, type: *targetType, options));
759 }
760
761 // Construct a new scf.for op with memref instead of tensor values.
762 auto newForOp = scf::ForOp::create(
763 builder&: rewriter, location: forOp.getLoc(), lowerBound: forOp.getLowerBound(), upperBound: forOp.getUpperBound(),
764 step: forOp.getStep(), initArgs: castedInitArgs, /*bodyBuilder=*/odsArg4: nullptr,
765 unsignedCmp: forOp.getUnsignedCmp());
766 newForOp->setDiscardableAttrs(
767 forOp->getDiscardableAttrDictionary().getValue());
768 Block *loopBody = newForOp.getBody();
769
770 // Set up new iter_args. The loop body uses tensors, so wrap the (memref)
771 // iter_args of the new loop in ToTensorOps.
772 rewriter.setInsertionPointToStart(loopBody);
773 SmallVector<Value> iterArgs =
774 getBbArgReplacements(rewriter, bbArgs: newForOp.getRegionIterArgs(),
775 oldBbArgs: forOp.getRegionIterArgs(), tensorIndices: indices);
776 iterArgs.insert(I: iterArgs.begin(), Elt: newForOp.getInductionVar());
777
778 // Move loop body to new loop.
779 rewriter.mergeBlocks(source: oldLoopBody, dest: loopBody, argValues: iterArgs);
780
781 // Replace loop results.
782 replaceOpWithBufferizedValues(rewriter, op, values: newForOp->getResults());
783
784 return success();
785 }
786
787 /// Assert that yielded values of an scf.for op are equivalent to their
788 /// corresponding bbArgs. In that case, the buffer relations of the
789 /// corresponding OpResults are "Equivalent".
790 ///
791 /// If this is not the case, an allocs+copies are inserted and yielded from
792 /// the loop. This could be a performance problem, so it must be explicitly
793 /// activated with `alloc-return-allocs`.
794 LogicalResult verifyAnalysis(Operation *op,
795 const AnalysisState &state) const {
796 const auto &options =
797 static_cast<const OneShotBufferizationOptions &>(state.getOptions());
798 if (options.allowReturnAllocsFromLoops)
799 return success();
800
801 auto forOp = cast<scf::ForOp>(Val: op);
802 auto yieldOp = cast<scf::YieldOp>(Val: forOp.getBody()->getTerminator());
803 for (OpResult opResult : op->getOpResults()) {
804 if (!isa<TensorLikeType>(Val: opResult.getType()))
805 continue;
806 // Note: This is overly strict. We should check for aliasing bufferized
807 // values. But we don't have a "must-alias" analysis yet.
808 if (bufferRelation(op, opResult, state) != BufferRelation::Equivalent)
809 return yieldOp->emitError()
810 << "Yield operand #" << opResult.getResultNumber()
811 << " is not equivalent to the corresponding iter bbArg";
812 }
813
814 return success();
815 }
816};
817
818/// Bufferization of scf.while. Replace with a new scf.while that operates on
819/// memrefs.
820struct WhileOpInterface
821 : public BufferizableOpInterface::ExternalModel<WhileOpInterface,
822 scf::WhileOp> {
823 bool bufferizesToMemoryRead(Operation *op, OpOperand &opOperand,
824 const AnalysisState &state) const {
825 // Tensor iter_args of scf::WhileOps are always considered as a read.
826 return true;
827 }
828
829 bool bufferizesToMemoryWrite(Operation *op, OpOperand &opOperand,
830 const AnalysisState &state) const {
831 // Tensor iter_args of scf::WhileOps are always considered as a write.
832 return true;
833 }
834
835 AliasingValueList getAliasingValues(Operation *op, OpOperand &opOperand,
836 const AnalysisState &state) const {
837 auto whileOp = cast<scf::WhileOp>(Val: op);
838 unsigned int idx = opOperand.getOperandNumber();
839
840 // The OpResults and OpOperands may not match. They may not even have the
841 // same type. The number of OpResults and OpOperands can also differ.
842 if (idx >= op->getNumResults() ||
843 opOperand.get().getType() != op->getResult(idx).getType())
844 return {};
845
846 // The only aliasing OpResult may be the one at the same index.
847 OpResult opResult = whileOp->getResult(idx);
848 BufferRelation relation = bufferRelation(op, opResult, state);
849 return {{opResult, relation,
850 /*isDefinite=*/relation == BufferRelation::Equivalent}};
851 }
852
853 BufferRelation bufferRelation(Operation *op, OpResult opResult,
854 const AnalysisState &state) const {
855 // WhileOp results are equivalent to their corresponding init_args if the
856 // corresponding iter_args and yield values are equivalent (for both the
857 // "before" and the "after" block).
858 unsigned int resultNumber = opResult.getResultNumber();
859 auto whileOp = cast<scf::WhileOp>(Val: op);
860
861 // The "before" region bbArgs and the OpResults may not match.
862 if (resultNumber >= whileOp.getBeforeArguments().size())
863 return BufferRelation::Unknown;
864 if (opResult.getType() !=
865 whileOp.getBeforeArguments()[resultNumber].getType())
866 return BufferRelation::Unknown;
867
868 auto conditionOp = whileOp.getConditionOp();
869 BlockArgument conditionBbArg = whileOp.getBeforeArguments()[resultNumber];
870 Value conditionOperand = conditionOp.getArgs()[resultNumber];
871 bool equivCondition =
872 state.areEquivalentBufferizedValues(v1: conditionBbArg, v2: conditionOperand);
873
874 auto yieldOp = whileOp.getYieldOp();
875 BlockArgument bodyBbArg = whileOp.getAfterArguments()[resultNumber];
876 Value yieldOperand = yieldOp.getOperand(i: resultNumber);
877 bool equivYield =
878 state.areEquivalentBufferizedValues(v1: bodyBbArg, v2: yieldOperand);
879
880 return equivCondition && equivYield ? BufferRelation::Equivalent
881 : BufferRelation::Unknown;
882 }
883
884 bool isWritable(Operation *op, Value value,
885 const AnalysisState &state) const {
886 // Interestingly, scf::WhileOp's bbArg can **always** be viewed
887 // inplace from the perspective of ops nested under:
888 // 1. Either the matching iter operand is not bufferized inplace and an
889 // alloc + optional copy makes the bbArg itself inplaceable.
890 // 2. Or the matching iter operand is bufferized inplace and bbArg just
891 // bufferizes to that too.
892 return true;
893 }
894
895 LogicalResult
896 resolveConflicts(Operation *op, RewriterBase &rewriter,
897 const AnalysisState &analysisState,
898 const BufferizationState &bufferizationState) const {
899 auto bufferizableOp = cast<BufferizableOpInterface>(Val: op);
900 if (failed(Result: bufferizableOp.resolveTensorOpOperandConflicts(
901 rewriter, analysisState, bufferizationState)))
902 return failure();
903
904 if (analysisState.getOptions().copyBeforeWrite)
905 return success();
906
907 // According to the `getAliasing...` implementations, a bufferized OpResult
908 // may alias only with the corresponding bufferized init_arg and with no
909 // other buffers. I.e., the i-th OpResult may alias with the i-th init_arg;
910 // but not with any other OpOperand. If a corresponding OpResult/init_arg
911 // pair bufferizes to equivalent buffers, this aliasing requirement is
912 // satisfied. Otherwise, we cannot be sure and must yield a new buffer copy.
913 // (New buffer copies do not alias with any buffer.)
914 OpBuilder::InsertionGuard g(rewriter);
915 auto whileOp = cast<scf::WhileOp>(Val: op);
916 auto conditionOp = whileOp.getConditionOp();
917
918 // For every yielded value, is the value equivalent to its corresponding
919 // bbArg?
920 DenseSet<int64_t> equivalentYieldsBefore = getEquivalentBuffers(
921 bbArgs: whileOp.getBeforeArguments(), yieldedValues: conditionOp.getArgs(), state: analysisState);
922 DenseSet<int64_t> equivalentYieldsAfter =
923 getEquivalentBuffers(bbArgs: whileOp.getAfterArguments(),
924 yieldedValues: whileOp.getYieldOp().getResults(), state: analysisState);
925
926 // Update "before" region.
927 rewriter.setInsertionPoint(conditionOp);
928 SmallVector<Value> beforeYieldValues;
929 for (int64_t idx = 0;
930 idx < static_cast<int64_t>(conditionOp.getArgs().size()); ++idx) {
931 Value value = conditionOp.getArgs()[idx];
932 if (!isa<TensorLikeType>(Val: value.getType()) ||
933 (equivalentYieldsAfter.contains(V: idx) &&
934 equivalentYieldsBefore.contains(V: idx))) {
935 beforeYieldValues.push_back(Elt: value);
936 continue;
937 }
938 FailureOr<Value> alloc = allocateTensorForShapedValue(
939 b&: rewriter, loc: conditionOp.getLoc(), shapedValue: value, options: analysisState.getOptions(),
940 state: bufferizationState);
941 if (failed(Result: alloc))
942 return failure();
943 beforeYieldValues.push_back(Elt: *alloc);
944 }
945 rewriter.modifyOpInPlace(root: conditionOp, callable: [&]() {
946 conditionOp.getArgsMutable().assign(values: beforeYieldValues);
947 });
948
949 return success();
950 }
951
952 LogicalResult bufferize(Operation *op, RewriterBase &rewriter,
953 const BufferizationOptions &options,
954 BufferizationState &state) const {
955 auto whileOp = cast<scf::WhileOp>(Val: op);
956
957 // Indices of all bbArgs that have tensor type. These are the ones that
958 // are bufferized. The "before" and "after" regions may have different args.
959 DenseSet<int64_t> indicesBefore = getTensorIndices(values: whileOp.getInits());
960 DenseSet<int64_t> indicesAfter =
961 getTensorIndices(values: whileOp.getAfterArguments());
962
963 // The new memref init_args of the loop.
964 FailureOr<SmallVector<Value>> maybeInitArgs =
965 getBuffers(rewriter, operands: whileOp.getInitsMutable(), options, state);
966 if (failed(Result: maybeInitArgs))
967 return failure();
968 SmallVector<Value> initArgs = *maybeInitArgs;
969
970 // Cast init_args if necessary.
971 SmallVector<Value> castedInitArgs;
972 for (const auto &it : llvm::enumerate(First&: initArgs)) {
973 Value initArg = it.value();
974 Value beforeArg = whileOp.getBeforeArguments()[it.index()];
975 // If the type is not a tensor, bufferization doesn't need to touch it.
976 if (!isa<TensorLikeType>(Val: beforeArg.getType())) {
977 castedInitArgs.push_back(Elt: initArg);
978 continue;
979 }
980 auto targetType = bufferization::getBufferType(value: beforeArg, options, state);
981 if (failed(Result: targetType))
982 return failure();
983 castedInitArgs.push_back(
984 Elt: castBuffer(b&: rewriter, buffer: initArg, type: *targetType, options));
985 }
986
987 // The result types of a WhileOp are the same as the "after" bbArg types.
988 SmallVector<Type> argsTypesAfter = llvm::map_to_vector(
989 C: whileOp.getAfterArguments(), F: [&](BlockArgument bbArg) {
990 if (!isa<TensorLikeType>(Val: bbArg.getType()))
991 return bbArg.getType();
992 // TODO: error handling
993 return llvm::cast<Type>(
994 Val: *bufferization::getBufferType(value: bbArg, options, state));
995 });
996
997 // Construct a new scf.while op with memref instead of tensor values.
998 ValueRange argsRangeBefore(castedInitArgs);
999 TypeRange argsTypesBefore(argsRangeBefore);
1000 auto newWhileOp = scf::WhileOp::create(builder&: rewriter, location: whileOp.getLoc(),
1001 resultTypes: argsTypesAfter, operands: castedInitArgs);
1002
1003 // Add before/after regions to the new op.
1004 SmallVector<Location> bbArgLocsBefore(castedInitArgs.size(),
1005 whileOp.getLoc());
1006 SmallVector<Location> bbArgLocsAfter(argsTypesAfter.size(),
1007 whileOp.getLoc());
1008 Block *newBeforeBody = &newWhileOp.getBefore().emplaceBlock();
1009 newWhileOp.getBefore().addArguments(types: argsTypesBefore, locs: bbArgLocsBefore);
1010 Block *newAfterBody = &newWhileOp.getAfter().emplaceBlock();
1011 newWhileOp.getAfter().addArguments(types: argsTypesAfter, locs: bbArgLocsAfter);
1012
1013 // Set up new iter_args and move the loop condition block to the new op.
1014 // The old block uses tensors, so wrap the (memref) bbArgs of the new block
1015 // in ToTensorOps.
1016 rewriter.setInsertionPointToStart(newBeforeBody);
1017 SmallVector<Value> newBeforeArgs =
1018 getBbArgReplacements(rewriter, bbArgs: newWhileOp.getBeforeArguments(),
1019 oldBbArgs: whileOp.getBeforeArguments(), tensorIndices: indicesBefore);
1020 rewriter.mergeBlocks(source: whileOp.getBeforeBody(), dest: newBeforeBody, argValues: newBeforeArgs);
1021
1022 // Set up new iter_args and move the loop body block to the new op.
1023 // The old block uses tensors, so wrap the (memref) bbArgs of the new block
1024 // in ToTensorOps.
1025 rewriter.setInsertionPointToStart(newAfterBody);
1026 SmallVector<Value> newAfterArgs =
1027 getBbArgReplacements(rewriter, bbArgs: newWhileOp.getAfterArguments(),
1028 oldBbArgs: whileOp.getAfterArguments(), tensorIndices: indicesAfter);
1029 rewriter.mergeBlocks(source: whileOp.getAfterBody(), dest: newAfterBody, argValues: newAfterArgs);
1030
1031 // Replace loop results.
1032 replaceOpWithBufferizedValues(rewriter, op, values: newWhileOp->getResults());
1033
1034 return success();
1035 }
1036
1037 FailureOr<BufferLikeType>
1038 getBufferType(Operation *op, Value value, const BufferizationOptions &options,
1039 const BufferizationState &state,
1040 SmallVector<Value> &invocationStack) const {
1041 auto whileOp = cast<scf::WhileOp>(Val: op);
1042 assert(getOwnerOfValue(value) == op && "invalid value");
1043 assert(isa<TensorLikeType>(value.getType()) && "expected tensor type");
1044
1045 // Case 1: Block argument of the "before" region.
1046 if (auto bbArg = dyn_cast<BlockArgument>(Val&: value)) {
1047 if (bbArg.getOwner()->getParent() == &whileOp.getBefore()) {
1048 Value initArg = whileOp.getInits()[bbArg.getArgNumber()];
1049 auto yieldOp = whileOp.getYieldOp();
1050 Value yieldedValue = yieldOp.getOperand(i: bbArg.getArgNumber());
1051 return computeLoopRegionIterArgBufferType(
1052 loopOp: op, iterArg: bbArg, initArg, yieldedValue, options, state, invocationStack);
1053 }
1054 }
1055
1056 // Case 2: OpResult of the loop or block argument of the "after" region.
1057 // The bufferized "after" bbArg type can be directly computed from the
1058 // bufferized "before" bbArg type.
1059 unsigned resultNum;
1060 if (auto opResult = dyn_cast<OpResult>(Val&: value)) {
1061 resultNum = opResult.getResultNumber();
1062 } else if (cast<BlockArgument>(Val&: value).getOwner()->getParent() ==
1063 &whileOp.getAfter()) {
1064 resultNum = cast<BlockArgument>(Val&: value).getArgNumber();
1065 } else {
1066 llvm_unreachable("invalid value");
1067 }
1068 Value conditionYieldedVal = whileOp.getConditionOp().getArgs()[resultNum];
1069 if (!isa<TensorLikeType>(Val: conditionYieldedVal.getType())) {
1070 // scf.condition was already bufferized.
1071 return cast<BufferLikeType>(Val: conditionYieldedVal.getType());
1072 }
1073 return bufferization::getBufferType(value: conditionYieldedVal, options, state,
1074 invocationStack);
1075 }
1076
1077 /// Assert that yielded values of an scf.while op are equivalent to their
1078 /// corresponding bbArgs. In that case, the buffer relations of the
1079 /// corresponding OpResults are "Equivalent".
1080 ///
1081 /// If this is not the case, allocs+copies are inserted and yielded from
1082 /// the loop. This could be a performance problem, so it must be explicitly
1083 /// activated with `allow-return-allocs`.
1084 ///
1085 /// Not: In contrast to scf::ForOp, scf::WhileOp has two regions and the
1086 /// equivalence condition must be checked for both.
1087 LogicalResult verifyAnalysis(Operation *op,
1088 const AnalysisState &state) const {
1089 auto whileOp = cast<scf::WhileOp>(Val: op);
1090 const auto &options =
1091 static_cast<const OneShotBufferizationOptions &>(state.getOptions());
1092 if (options.allowReturnAllocsFromLoops)
1093 return success();
1094
1095 auto conditionOp = whileOp.getConditionOp();
1096 for (const auto &it : llvm::enumerate(First: conditionOp.getArgs())) {
1097 Block *block = conditionOp->getBlock();
1098 if (!isa<TensorLikeType>(Val: it.value().getType()))
1099 continue;
1100 if (it.index() >= block->getNumArguments() ||
1101 !state.areEquivalentBufferizedValues(v1: it.value(),
1102 v2: block->getArgument(i: it.index())))
1103 return conditionOp->emitError()
1104 << "Condition arg #" << it.index()
1105 << " is not equivalent to the corresponding iter bbArg";
1106 }
1107
1108 auto yieldOp = whileOp.getYieldOp();
1109 for (const auto &it : llvm::enumerate(First: yieldOp.getResults())) {
1110 Block *block = yieldOp->getBlock();
1111 if (!isa<TensorLikeType>(Val: it.value().getType()))
1112 continue;
1113 if (it.index() >= block->getNumArguments() ||
1114 !state.areEquivalentBufferizedValues(v1: it.value(),
1115 v2: block->getArgument(i: it.index())))
1116 return yieldOp->emitError()
1117 << "Yield operand #" << it.index()
1118 << " is not equivalent to the corresponding iter bbArg";
1119 }
1120
1121 return success();
1122 }
1123};
1124
1125/// Bufferization of scf.yield. Bufferized as part of their enclosing ops, so
1126/// this is for analysis only.
1127struct YieldOpInterface
1128 : public BufferizableOpInterface::ExternalModel<YieldOpInterface,
1129 scf::YieldOp> {
1130 bool bufferizesToMemoryRead(Operation *op, OpOperand &opOperand,
1131 const AnalysisState &state) const {
1132 return true;
1133 }
1134
1135 bool bufferizesToMemoryWrite(Operation *op, OpOperand &opOperand,
1136 const AnalysisState &state) const {
1137 return false;
1138 }
1139
1140 AliasingValueList getAliasingValues(Operation *op, OpOperand &opOperand,
1141 const AnalysisState &state) const {
1142 if (isa<scf::IfOp, scf::IndexSwitchOp>(Val: op->getParentOp()))
1143 return {{op->getParentOp()->getResult(idx: opOperand.getOperandNumber()),
1144 BufferRelation::Equivalent, /*isDefinite=*/false}};
1145 if (isa<scf::ExecuteRegionOp>(Val: op->getParentOp()))
1146 return {{op->getParentOp()->getResult(idx: opOperand.getOperandNumber()),
1147 BufferRelation::Equivalent}};
1148 return {};
1149 }
1150
1151 bool mustBufferizeInPlace(Operation *op, OpOperand &opOperand,
1152 const AnalysisState &state) const {
1153 // Yield operands always bufferize inplace. Otherwise, an alloc + copy
1154 // may be generated inside the block. We should not return/yield allocations
1155 // when possible.
1156 return true;
1157 }
1158
1159 LogicalResult bufferize(Operation *op, RewriterBase &rewriter,
1160 const BufferizationOptions &options,
1161 BufferizationState &state) const {
1162 auto yieldOp = cast<scf::YieldOp>(Val: op);
1163 if (!isa<scf::ExecuteRegionOp, scf::IfOp, scf::IndexSwitchOp, scf::ForOp,
1164 scf::WhileOp>(Val: yieldOp->getParentOp()))
1165 return yieldOp->emitError(message: "unsupported scf::YieldOp parent");
1166
1167 SmallVector<Value> newResults;
1168 for (const auto &it : llvm::enumerate(First: yieldOp.getResults())) {
1169 Value value = it.value();
1170 if (isa<TensorLikeType>(Val: value.getType())) {
1171 FailureOr<Value> maybeBuffer =
1172 getBuffer(rewriter, value, options, state);
1173 if (failed(Result: maybeBuffer))
1174 return failure();
1175 Value buffer = *maybeBuffer;
1176 // We may have to cast the value before yielding it.
1177 if (isa<scf::ForOp, scf::IfOp, scf::IndexSwitchOp>(
1178 Val: yieldOp->getParentOp())) {
1179 FailureOr<BufferLikeType> resultType = bufferization::getBufferType(
1180 value: yieldOp->getParentOp()->getResult(idx: it.index()), options, state);
1181 if (failed(Result: resultType))
1182 return failure();
1183 buffer = castBuffer(b&: rewriter, buffer, type: *resultType, options);
1184 } else if (auto whileOp =
1185 dyn_cast<scf::WhileOp>(Val: yieldOp->getParentOp())) {
1186 FailureOr<BufferLikeType> resultType = bufferization::getBufferType(
1187 value: whileOp.getBeforeArguments()[it.index()], options, state);
1188 if (failed(Result: resultType))
1189 return failure();
1190 buffer = castBuffer(b&: rewriter, buffer, type: *resultType, options);
1191 }
1192 newResults.push_back(Elt: buffer);
1193 } else {
1194 newResults.push_back(Elt: value);
1195 }
1196 }
1197
1198 replaceOpWithNewBufferizedOp<scf::YieldOp>(rewriter, op, args&: newResults);
1199 return success();
1200 }
1201};
1202
1203/// Bufferization of ForallOp. This also bufferizes the terminator of the
1204/// region. There are op interfaces for the terminators (InParallelOp
1205/// and ParallelInsertSliceOp), but these are only used during analysis. Not
1206/// for bufferization.
1207struct ForallOpInterface
1208 : public BufferizableOpInterface::ExternalModel<ForallOpInterface,
1209 ForallOp> {
1210 bool bufferizesToMemoryRead(Operation *op, OpOperand &opOperand,
1211 const AnalysisState &state) const {
1212 // All tensor operands to `scf.forall` are `shared_outs` and all
1213 // shared outs are assumed to be read by the loop. This does not
1214 // account for the case where the entire value is over-written,
1215 // but being conservative here.
1216 return true;
1217 }
1218
1219 bool bufferizesToMemoryWrite(Operation *op, OpOperand &opOperand,
1220 const AnalysisState &state) const {
1221 // Outputs of scf::ForallOps are always considered as a write.
1222 return true;
1223 }
1224
1225 AliasingValueList getAliasingValues(Operation *op, OpOperand &opOperand,
1226 const AnalysisState &state) const {
1227 auto forallOp = cast<ForallOp>(Val: op);
1228 return {
1229 {{forallOp.getTiedOpResult(opOperand: &opOperand), BufferRelation::Equivalent}}};
1230 }
1231
1232 AliasingOpOperandList
1233 getAliasingOpOperands(Operation *op, Value value,
1234 const AnalysisState &state) const {
1235 auto result = dyn_cast<OpResult>(Val&: value);
1236 if (!result)
1237 return {};
1238 auto forallOp = cast<ForallOp>(Val: op);
1239 return {{forallOp.getTiedOpOperand(opResult: result), BufferRelation::Equivalent}};
1240 }
1241
1242 bool isWritable(Operation *op, Value value,
1243 const AnalysisState &state) const {
1244 return true;
1245 }
1246
1247 LogicalResult bufferize(Operation *op, RewriterBase &rewriter,
1248 const BufferizationOptions &options,
1249 BufferizationState &state) const {
1250 OpBuilder::InsertionGuard guard(rewriter);
1251 auto forallOp = cast<ForallOp>(Val: op);
1252 int64_t rank = forallOp.getRank();
1253
1254 // Get buffers for all output operands.
1255 SmallVector<Value> buffers;
1256 for (Value out : forallOp.getOutputs()) {
1257 FailureOr<Value> buffer = getBuffer(rewriter, value: out, options, state);
1258 if (failed(Result: buffer))
1259 return failure();
1260 buffers.push_back(Elt: *buffer);
1261 }
1262
1263 // Use buffers instead of block arguments.
1264 rewriter.setInsertionPointToStart(forallOp.getBody());
1265 for (const auto &it : llvm::zip(
1266 t: forallOp.getBody()->getArguments().drop_front(N: rank), u&: buffers)) {
1267 BlockArgument bbArg = std::get<0>(t: it);
1268 Value buffer = std::get<1>(t: it);
1269 Value bufferAsTensor = ToTensorOp::create(builder&: rewriter, location: forallOp.getLoc(),
1270 result: bbArg.getType(), buffer);
1271 bbArg.replaceAllUsesWith(newValue: bufferAsTensor);
1272 }
1273
1274 // Create new ForallOp without any results and drop the automatically
1275 // introduced terminator.
1276 rewriter.setInsertionPoint(forallOp);
1277 ForallOp newForallOp;
1278 newForallOp = ForallOp::create(
1279 builder&: rewriter, location: forallOp.getLoc(), lbs: forallOp.getMixedLowerBound(),
1280 ubs: forallOp.getMixedUpperBound(), steps: forallOp.getMixedStep(),
1281 /*outputs=*/ValueRange(), mapping: forallOp.getMapping());
1282
1283 // Keep discardable attributes from the original op.
1284 newForallOp->setDiscardableAttrs(op->getDiscardableAttrDictionary());
1285
1286 rewriter.eraseOp(op: newForallOp.getBody()->getTerminator());
1287
1288 // Move over block contents of the old op.
1289 SmallVector<Value> replacementBbArgs;
1290 replacementBbArgs.append(in_start: newForallOp.getBody()->getArguments().begin(),
1291 in_end: newForallOp.getBody()->getArguments().end());
1292 replacementBbArgs.append(NumInputs: forallOp.getOutputs().size(), Elt: Value());
1293 rewriter.mergeBlocks(source: forallOp.getBody(), dest: newForallOp.getBody(),
1294 argValues: replacementBbArgs);
1295
1296 // Remove the old op and replace all of its uses.
1297 replaceOpWithBufferizedValues(rewriter, op, values: buffers);
1298
1299 return success();
1300 }
1301
1302 FailureOr<BufferLikeType>
1303 getBufferType(Operation *op, Value value, const BufferizationOptions &options,
1304 const BufferizationState &state,
1305 SmallVector<Value> &invocationStack) const {
1306 auto forallOp = cast<ForallOp>(Val: op);
1307
1308 if (auto bbArg = dyn_cast<BlockArgument>(Val&: value))
1309 // A tensor block argument has the same bufferized type as the
1310 // corresponding output operand.
1311 return bufferization::getBufferType(
1312 value: forallOp.getTiedOpOperand(bbArg)->get(), options, state,
1313 invocationStack);
1314
1315 // The bufferized result type is the same as the bufferized type of the
1316 // corresponding output operand.
1317 return bufferization::getBufferType(
1318 value: forallOp.getOutputs()[cast<OpResult>(Val&: value).getResultNumber()], options,
1319 state, invocationStack);
1320 }
1321
1322 bool isRepetitiveRegion(Operation *op, unsigned index) const {
1323 auto forallOp = cast<ForallOp>(Val: op);
1324
1325 // This op is repetitive if it has 1 or more steps.
1326 // If the control variables are dynamic, it is also considered so.
1327 for (auto [lb, ub, step] :
1328 llvm::zip(t: forallOp.getMixedLowerBound(), u: forallOp.getMixedUpperBound(),
1329 args: forallOp.getMixedStep())) {
1330 std::optional<int64_t> lbConstant = getConstantIntValue(ofr: lb);
1331 if (!lbConstant)
1332 return true;
1333
1334 std::optional<int64_t> ubConstant = getConstantIntValue(ofr: ub);
1335 if (!ubConstant)
1336 return true;
1337
1338 std::optional<int64_t> stepConstant = getConstantIntValue(ofr: step);
1339 if (!stepConstant)
1340 return true;
1341
1342 if (*lbConstant + *stepConstant < *ubConstant)
1343 return true;
1344 }
1345 return false;
1346 }
1347
1348 bool isParallelRegion(Operation *op, unsigned index) const {
1349 return isRepetitiveRegion(op, index);
1350 }
1351};
1352
1353/// Nothing to do for InParallelOp.
1354struct InParallelOpInterface
1355 : public BufferizableOpInterface::ExternalModel<InParallelOpInterface,
1356 InParallelOp> {
1357 LogicalResult bufferize(Operation *op, RewriterBase &b,
1358 const BufferizationOptions &options,
1359 BufferizationState &state) const {
1360 llvm_unreachable("op does not have any tensor OpOperands / OpResults");
1361 return failure();
1362 }
1363};
1364
1365} // namespace
1366} // namespace scf
1367} // namespace mlir
1368
1369void mlir::scf::registerBufferizableOpInterfaceExternalModels(
1370 DialectRegistry &registry) {
1371 registry.addExtension(extensionFn: +[](MLIRContext *ctx, scf::SCFDialect *dialect) {
1372 ConditionOp::attachInterface<ConditionOpInterface>(context&: *ctx);
1373 ExecuteRegionOp::attachInterface<ExecuteRegionOpInterface>(context&: *ctx);
1374 ForOp::attachInterface<ForOpInterface>(context&: *ctx);
1375 IfOp::attachInterface<IfOpInterface>(context&: *ctx);
1376 IndexSwitchOp::attachInterface<IndexSwitchOpInterface>(context&: *ctx);
1377 ForallOp::attachInterface<ForallOpInterface>(context&: *ctx);
1378 InParallelOp::attachInterface<InParallelOpInterface>(context&: *ctx);
1379 WhileOp::attachInterface<WhileOpInterface>(context&: *ctx);
1380 YieldOp::attachInterface<YieldOpInterface>(context&: *ctx);
1381 });
1382}
1383