1//===- BufferizableOpInterface.cpp - Bufferizable Ops ---=----------------===//
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/Bufferization/IR/BufferizableOpInterface.h"
10#include "mlir/Dialect/Arith/Utils/Utils.h"
11#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
12#include "mlir/Dialect/Func/IR/FuncOps.h"
13#include "mlir/Dialect/MemRef/IR/MemRef.h"
14#include "mlir/Dialect/Tensor/IR/Tensor.h"
15#include "mlir/IR/AsmState.h"
16#include "mlir/IR/Operation.h"
17#include "mlir/IR/TypeUtilities.h"
18#include "mlir/IR/Value.h"
19#include "mlir/Interfaces/ControlFlowInterfaces.h"
20#include "llvm/ADT/ScopeExit.h"
21#include "llvm/ADT/SmallVectorExtras.h"
22
23//===----------------------------------------------------------------------===//
24// BufferizableOpInterface
25//===----------------------------------------------------------------------===//
26
27namespace mlir {
28namespace bufferization {
29
30#include "mlir/Dialect/Bufferization/IR/BufferizableOpInterface.cpp.inc"
31
32} // namespace bufferization
33} // namespace mlir
34
35MLIR_DEFINE_EXPLICIT_TYPE_ID(mlir::bufferization::AnalysisState)
36
37#define DEBUG_TYPE "bufferizable-op-interface"
38
39using namespace mlir;
40using namespace bufferization;
41
42static bool isRepetitiveRegion(Region *region,
43 const BufferizationOptions &options) {
44 Operation *op = region->getParentOp();
45 if (auto bufferizableOp = options.dynCastBufferizableOp(op))
46 if (bufferizableOp.isRepetitiveRegion(index: region->getRegionNumber()))
47 return true;
48 return false;
49}
50
51Region *AnalysisState::getEnclosingRepetitiveRegion(
52 Operation *op, const BufferizationOptions &options) {
53 if (!op->getBlock())
54 return nullptr;
55 if (auto iter = enclosingRepetitiveRegionCache.find_as(Val: op);
56 iter != enclosingRepetitiveRegionCache.end())
57 return iter->second;
58 return enclosingRepetitiveRegionCache[op] =
59 getEnclosingRepetitiveRegion(block: op->getBlock(), options);
60}
61
62Region *AnalysisState::getEnclosingRepetitiveRegion(
63 Value value, const BufferizationOptions &options) {
64 if (auto iter = enclosingRepetitiveRegionCache.find_as(Val: value);
65 iter != enclosingRepetitiveRegionCache.end())
66 return iter->second;
67
68 Region *region = value.getParentRegion();
69 // Collect all visited regions since we only know the repetitive region we
70 // want to map it to later on
71 SmallVector<Region *> visitedRegions;
72 while (region) {
73 visitedRegions.push_back(Elt: region);
74 if (isRepetitiveRegion(region, options))
75 break;
76 region = region->getParentRegion();
77 }
78 enclosingRepetitiveRegionCache[value] = region;
79 for (Region *r : visitedRegions)
80 enclosingRepetitiveRegionCache[r] = region;
81 return region;
82}
83
84Region *AnalysisState::getEnclosingRepetitiveRegion(
85 Block *block, const BufferizationOptions &options) {
86 if (auto iter = enclosingRepetitiveRegionCache.find_as(Val: block);
87 iter != enclosingRepetitiveRegionCache.end())
88 return iter->second;
89
90 Region *region = block->getParent();
91 Operation *op = nullptr;
92 // Collect all visited regions since we only know the repetitive region we
93 // want to map it to later on
94 SmallVector<Region *> visitedRegions;
95 do {
96 op = region->getParentOp();
97 if (isRepetitiveRegion(region, options))
98 break;
99 } while ((region = op->getParentRegion()));
100
101 enclosingRepetitiveRegionCache[block] = region;
102 for (Region *r : visitedRegions)
103 enclosingRepetitiveRegionCache[r] = region;
104 return region;
105}
106
107bool AnalysisState::insideMutuallyExclusiveRegions(Operation *op0,
108 Operation *op1) {
109 auto key = std::make_pair(x&: op0, y&: op1);
110 if (auto iter = insideMutuallyExclusiveRegionsCache.find(Val: key);
111 iter != insideMutuallyExclusiveRegionsCache.end())
112 return iter->second;
113 bool result = ::mlir::insideMutuallyExclusiveRegions(a: op0, b: op1);
114 // Populate results for both orderings of the ops.
115 insideMutuallyExclusiveRegionsCache[key] = result;
116 insideMutuallyExclusiveRegionsCache[std::make_pair(x&: op1, y&: op0)] = result;
117 return result;
118}
119
120void AnalysisState::resetCache() {
121 enclosingRepetitiveRegionCache.clear();
122 insideMutuallyExclusiveRegionsCache.clear();
123}
124
125SymbolTableCollection &BufferizationState::getSymbolTables() {
126 return symbolTables;
127}
128
129SymbolTableCollection &BufferizationState::getSymbolTables() const {
130 return symbolTables;
131}
132
133Region *bufferization::getNextEnclosingRepetitiveRegion(
134 Region *region, const BufferizationOptions &options) {
135 assert(isRepetitiveRegion(region, options) && "expected repetitive region");
136 while ((region = region->getParentRegion())) {
137 if (isRepetitiveRegion(region, options))
138 break;
139 }
140 return region;
141}
142
143Region *bufferization::getParallelRegion(Region *region,
144 const BufferizationOptions &options) {
145 while (region) {
146 auto bufferizableOp = options.dynCastBufferizableOp(op: region->getParentOp());
147 if (bufferizableOp &&
148 bufferizableOp.isParallelRegion(index: region->getRegionNumber())) {
149 assert(isRepetitiveRegion(region, options) &&
150 "expected that all parallel regions are also repetitive regions");
151 return region;
152 }
153 region = region->getParentRegion();
154 }
155 return nullptr;
156}
157
158Operation *bufferization::getOwnerOfValue(Value value) {
159 if (auto opResult = llvm::dyn_cast<OpResult>(Val&: value))
160 return opResult.getDefiningOp();
161 return llvm::cast<BlockArgument>(Val&: value).getOwner()->getParentOp();
162}
163
164/// Create an AllocTensorOp for the given shaped value. If `copy` is set, the
165/// shaped value is copied. Otherwise, a tensor with undefined contents is
166/// allocated.
167FailureOr<Value> bufferization::allocateTensorForShapedValue(
168 OpBuilder &b, Location loc, Value shapedValue,
169 const BufferizationOptions &options, const BufferizationState &state,
170 bool copy) {
171 Value tensor = shapedValue;
172 if (llvm::isa<MemRefType>(Val: shapedValue.getType())) {
173 tensor = ToTensorOp::create(
174 builder&: b, location: loc, result: memref::getTensorTypeFromMemRefType(type: shapedValue.getType()),
175 buffer: shapedValue);
176 } else if (llvm::isa<UnrankedTensorType>(Val: shapedValue.getType()) ||
177 llvm::isa<UnrankedMemRefType>(Val: shapedValue.getType())) {
178 return getOwnerOfValue(value: shapedValue)
179 ->emitError(message: "copying of unranked tensors is not implemented");
180 }
181 auto tensorType = llvm::cast<TensorLikeType>(Val: tensor.getType());
182 SmallVector<Value> dynamicSizes;
183 // Only a ranked tensor result takes sizes; any other result has the shape of
184 // its buffer type.
185 auto rankedTensorType = dyn_cast<RankedTensorType>(Val&: tensorType);
186 if (!copy && rankedTensorType) {
187 // Compute the dynamic part of the shape.
188 // First try to query the shape via ReifyRankedShapedTypeOpInterface.
189 bool reifiedShapes = false;
190 if (llvm::isa<RankedTensorType>(Val: shapedValue.getType()) &&
191 llvm::isa<OpResult>(Val: shapedValue)) {
192 ReifiedRankedShapedTypeDims resultDims;
193 if (succeeded(
194 Result: reifyResultShapes(b, op: shapedValue.getDefiningOp(), reifiedReturnShapes&: resultDims))) {
195 reifiedShapes = true;
196 auto &shape =
197 resultDims[llvm::cast<OpResult>(Val&: shapedValue).getResultNumber()];
198 for (const auto &dim : enumerate(First: rankedTensorType.getShape())) {
199 if (ShapedType::isDynamic(dValue: dim.value())) {
200 dynamicSizes.push_back(
201 Elt: getValueOrCreateConstantIndexOp(b, loc, ofr: shape[dim.index()]));
202 }
203 }
204 }
205 }
206
207 // If the shape could not be reified, create DimOps.
208 if (!reifiedShapes)
209 populateDynamicDimSizes(b, loc, shapedValue: tensor, dynamicDims&: dynamicSizes);
210 }
211
212 // Create AllocTensorOp.
213 auto allocTensorOp = AllocTensorOp::create(builder&: b, location: loc, type: tensorType, dynamicSizes,
214 copy: copy ? tensor : Value());
215
216 // Add 'memory_space' attribute. Not needed if 'copy' operand is specified.
217 if (copy)
218 return allocTensorOp.getResult();
219 auto copyBufferType = getBufferType(value: tensor, options, state);
220 if (failed(Result: copyBufferType))
221 return failure();
222 // A buffer that is not a memref has no memory space to inherit.
223 std::optional<Attribute> memorySpace;
224 if (auto copyMemRefType = dyn_cast<BaseMemRefType>(Val&: *copyBufferType))
225 memorySpace = copyMemRefType.getMemorySpace();
226 if (!memorySpace)
227 memorySpace =
228 options.defaultMemorySpaceFn(cast<TensorLikeType>(Val&: tensorType));
229 if (memorySpace.has_value())
230 allocTensorOp.setMemorySpaceAttr(memorySpace.value());
231 return allocTensorOp.getResult();
232}
233
234LogicalResult BufferizableOpInterface::resolveTensorOpOperandConflicts(
235 RewriterBase &rewriter, const AnalysisState &analysisState,
236 const BufferizationState &bufferizationState) {
237 OpBuilder::InsertionGuard g(rewriter);
238 Operation *op = getOperation();
239 SmallVector<OpOperand *> outOfPlaceOpOperands;
240 DenseSet<OpOperand *> copiedOpOperands;
241 SmallVector<Value> outOfPlaceValues;
242 DenseSet<Value> copiedOpValues;
243
244 // Find all out-of-place OpOperands.
245 for (OpOperand &opOperand : op->getOpOperands()) {
246 Type operandType = opOperand.get().getType();
247 if (!llvm::isa<TensorLikeType>(Val: operandType))
248 continue;
249 if (analysisState.isInPlace(opOperand))
250 continue;
251 if (llvm::isa<UnrankedTensorType>(Val: operandType))
252 return op->emitError(message: "copying of unranked tensors is not implemented");
253
254 AliasingValueList aliasingValues =
255 analysisState.getAliasingValues(opOperand);
256 if (aliasingValues.getNumAliases() == 1 &&
257 isa<OpResult>(Val: aliasingValues.getAliases()[0].value) &&
258 !analysisState.bufferizesToMemoryWrite(opOperand) &&
259 analysisState
260 .getAliasingOpOperands(value: aliasingValues.getAliases()[0].value)
261 .getNumAliases() == 1 &&
262 !isa<UnrankedTensorType>(
263 Val: aliasingValues.getAliases()[0].value.getType())) {
264 // The op itself does not write but may create exactly one alias. Instead
265 // of copying the OpOperand, copy the OpResult. The OpResult can sometimes
266 // be smaller than the OpOperand (e.g., in the case of an extract_slice,
267 // where the result is usually a smaller part of the source). Do not apply
268 // this optimization if the OpResult is an unranked tensor (because those
269 // cannot be copied at the moment).
270 Value value = aliasingValues.getAliases()[0].value;
271 outOfPlaceValues.push_back(Elt: value);
272 if (!analysisState.canOmitTensorCopy(opOperand))
273 copiedOpValues.insert(V: value);
274 } else {
275 // In all other cases, make a copy of the OpOperand.
276 outOfPlaceOpOperands.push_back(Elt: &opOperand);
277 if (!analysisState.canOmitTensorCopy(opOperand))
278 copiedOpOperands.insert(V: &opOperand);
279 }
280 }
281
282 // Insert copies of OpOperands.
283 rewriter.setInsertionPoint(op);
284 for (OpOperand *opOperand : outOfPlaceOpOperands) {
285 FailureOr<Value> copy = allocateTensorForShapedValue(
286 b&: rewriter, loc: op->getLoc(), shapedValue: opOperand->get(), options: analysisState.getOptions(),
287 state: bufferizationState, copy: copiedOpOperands.contains(V: opOperand));
288 if (failed(Result: copy))
289 return failure();
290 rewriter.modifyOpInPlace(root: op, callable: [&]() { opOperand->set(*copy); });
291 }
292
293 // Insert copies of Values.
294 rewriter.setInsertionPointAfter(op);
295 for (Value value : outOfPlaceValues) {
296 FailureOr<Value> copy = allocateTensorForShapedValue(
297 b&: rewriter, loc: op->getLoc(), shapedValue: value, options: analysisState.getOptions(),
298 state: bufferizationState, copy: copiedOpValues.count(V: value));
299 if (failed(Result: copy))
300 return failure();
301 SmallVector<OpOperand *> uses = llvm::map_to_vector(
302 C: value.getUses(), F: [](OpOperand &use) { return &use; });
303 for (OpOperand *use : uses) {
304 // Do not update the alloc_tensor op that we just created.
305 if (use->getOwner() == copy->getDefiningOp())
306 continue;
307 // tensor.dim ops may have been created to be used as alloc_tensor op
308 // dynamic extents. Do not update these either.
309 if (isa<tensor::DimOp>(Val: use->getOwner()))
310 continue;
311 rewriter.modifyOpInPlace(root: use->getOwner(), callable: [&]() { use->set(*copy); });
312 }
313 }
314
315 return success();
316}
317
318//===----------------------------------------------------------------------===//
319// OpFilter
320//===----------------------------------------------------------------------===//
321
322bool OpFilter::isOpAllowed(Operation *op) const {
323 // All other ops: Allow/disallow according to filter.
324 bool isAllowed = !hasAllowRule();
325 for (const Entry &entry : entries) {
326 bool filterResult = entry.fn(op);
327 switch (entry.type) {
328 case Entry::ALLOW:
329 isAllowed |= filterResult;
330 break;
331 case Entry::DENY:
332 if (filterResult)
333 // DENY filter matches. This op is no allowed. (Even if other ALLOW
334 // filters may match.)
335 return false;
336 };
337 }
338 return isAllowed;
339}
340
341//===----------------------------------------------------------------------===//
342// BufferizationOptions
343//===----------------------------------------------------------------------===//
344
345namespace {
346
347// A helper overload for bufferization::getMemRefTypeWithFullyDynamicLayout().
348BaseMemRefType getMemRefTypeWithFullyDynamicLayout(ArrayRef<int64_t> shape,
349 mlir::Type elementType,
350 Attribute memorySpace) {
351 int64_t dynamicOffset = ShapedType::kDynamic;
352 SmallVector<int64_t> dynamicStrides(shape.size(), ShapedType::kDynamic);
353 auto stridedLayout = StridedLayoutAttr::get(context: elementType.getContext(),
354 offset: dynamicOffset, strides: dynamicStrides);
355 return MemRefType::get(shape, elementType, layout: stridedLayout, memorySpace);
356}
357
358/// Create a memref allocation with the given type and dynamic extents.
359FailureOr<Value> defaultCreateAlloc(OpBuilder &b, Location loc, MemRefType type,
360 ValueRange dynShape,
361 unsigned int bufferAlignment) {
362 // Default buffer allocation via AllocOp.
363 if (bufferAlignment != 0)
364 return memref::AllocOp::create(builder&: b, location: loc, memrefType: type, dynamicSizes: dynShape,
365 alignment: b.getI64IntegerAttr(value: bufferAlignment))
366 .getResult();
367 return memref::AllocOp::create(builder&: b, location: loc, memrefType: type, dynamicSizes: dynShape).getResult();
368}
369
370/// Create a memory copy between two memref buffers.
371LogicalResult defaultCreateMemCpy(OpBuilder &b, Location loc, Value from,
372 Value to) {
373 memref::CopyOp::create(builder&: b, location: loc, source: from, target: to);
374 return success();
375}
376
377FailureOr<Value> defaultCreateCast(OpBuilder &b, Location loc, Type dest,
378 Value value) {
379 assert(isa<BaseMemRefType>(dest) && "expected BaseMemRefType");
380 assert(isa<BaseMemRefType>(value.getType()) && "expected BaseMemRefType");
381 assert(memref::CastOp::areCastCompatible(value.getType(), dest) &&
382 "cast incompatible");
383 return memref::CastOp::create(builder&: b, location: loc, dest, source: value).getResult();
384}
385
386/// Default function arg type converter: Use a fully dynamic layout map.
387BufferLikeType
388defaultFunctionArgTypeConverter(TensorLikeType type, Attribute memorySpace,
389 func::FuncOp funcOp,
390 const BufferizationOptions &options) {
391 if (auto tensorType = mlir::dyn_cast<TensorType>(Val&: type)) {
392 return cast<BufferLikeType>(
393 Val: bufferization::getMemRefTypeWithFullyDynamicLayout(tensorType,
394 memorySpace));
395 }
396
397 // If not builtin, fallback to unknown type conversion.
398 return options.unknownTypeConverterFn(type, memorySpace, options);
399}
400/// Default unknown type converter: Use a fully dynamic layout map.
401BufferLikeType
402defaultUnknownTypeConverter(TensorLikeType tensorType, Attribute memorySpace,
403 const BufferizationOptions &options) {
404 return cast<BufferLikeType>(
405 Val: bufferization::getMemRefTypeWithFullyDynamicLayout(
406 tensorType: cast<TensorType>(Val&: tensorType), memorySpace));
407}
408
409/// Default reconcile hook: memory space mismatch is an error, layout mismatch
410/// is resolved by promoting to fully dynamic.
411FailureOr<BufferLikeType>
412defaultReconcileBufferTypeMismatch(BufferLikeType x, BufferLikeType y,
413 const BufferizationOptions &) {
414 const auto xMemRef = cast<BaseMemRefType>(Val&: x);
415 const auto yMemRef = cast<BaseMemRefType>(Val&: y);
416
417 if (xMemRef.getMemorySpace() != yMemRef.getMemorySpace())
418 return failure();
419
420 if (isa<UnrankedMemRefType>(Val: xMemRef)) {
421 // unranked memrefs have no layout.
422 return x;
423 }
424
425 return cast<BufferLikeType>(Val: ::getMemRefTypeWithFullyDynamicLayout(
426 shape: xMemRef.getShape(), elementType: xMemRef.getElementType(), memorySpace: xMemRef.getMemorySpace()));
427}
428
429} // namespace
430
431// Default constructor for BufferizationOptions.
432BufferizationOptions::BufferizationOptions()
433 : allocationFn(defaultCreateAlloc), memCpyFn(defaultCreateMemCpy),
434 castFn(defaultCreateCast),
435 functionArgTypeConverterFn(defaultFunctionArgTypeConverter),
436 unknownTypeConverterFn(defaultUnknownTypeConverter),
437 reconcileBufferTypeMismatchFn(defaultReconcileBufferTypeMismatch) {}
438
439bool BufferizationOptions::isOpAllowed(Operation *op) const {
440 // Special case: If function boundary bufferization is deactivated, do not
441 // allow ops that belong to the `func` dialect.
442 bool isFuncBoundaryOp = isa_and_nonnull<func::FuncDialect>(Val: op->getDialect());
443 if (!bufferizeFunctionBoundaries && isFuncBoundaryOp)
444 return false;
445
446 return opFilter.isOpAllowed(op);
447}
448
449BufferizableOpInterface
450BufferizationOptions::dynCastBufferizableOp(Operation *op) const {
451 if (!isOpAllowed(op))
452 return nullptr;
453 auto bufferizableOp = dyn_cast<BufferizableOpInterface>(Val: op);
454 if (!bufferizableOp)
455 return nullptr;
456 return bufferizableOp;
457}
458
459BufferizableOpInterface
460BufferizationOptions::dynCastBufferizableOp(Value value) const {
461 return dynCastBufferizableOp(op: getOwnerOfValue(value));
462}
463
464void BufferizationOptions::setFunctionBoundaryTypeConversion(
465 LayoutMapOption layoutMapOption) {
466 functionArgTypeConverterFn = [=](TensorLikeType type, Attribute memorySpace,
467 func::FuncOp funcOp,
468 const BufferizationOptions &options) {
469 if (auto tensorType = mlir::dyn_cast<TensorType>(Val&: type)) {
470 if (layoutMapOption == LayoutMapOption::IdentityLayoutMap)
471 return cast<BufferLikeType>(
472 Val: bufferization::getMemRefTypeWithStaticIdentityLayout(tensorType,
473 memorySpace));
474 return cast<BufferLikeType>(
475 Val: bufferization::getMemRefTypeWithFullyDynamicLayout(tensorType,
476 memorySpace));
477 }
478
479 // If not builtin, fallback to unknown type conversion.
480 return options.unknownTypeConverterFn(type, memorySpace, options);
481 };
482 inferFunctionResultLayout =
483 layoutMapOption == LayoutMapOption::InferLayoutMap;
484}
485
486//===----------------------------------------------------------------------===//
487// Helper functions for BufferizableOpInterface
488//===----------------------------------------------------------------------===//
489
490static void setInsertionPointAfter(OpBuilder &b, Value value) {
491 if (auto bbArg = llvm::dyn_cast<BlockArgument>(Val&: value)) {
492 b.setInsertionPointToStart(bbArg.getOwner());
493 } else {
494 b.setInsertionPointAfter(value.getDefiningOp());
495 }
496}
497
498/// Determine which OpOperand* will alias with `value` if the op is bufferized
499/// in place. Return all tensor OpOperand* if the op is not bufferizable.
500AliasingOpOperandList AnalysisState::getAliasingOpOperands(Value value) const {
501 if (Operation *op = getOwnerOfValue(value))
502 if (auto bufferizableOp = getOptions().dynCastBufferizableOp(op))
503 return bufferizableOp.getAliasingOpOperands(value, state: *this);
504
505 // The op is not bufferizable.
506 return detail::unknownGetAliasingOpOperands(value);
507}
508
509/// Determine which Values will alias with `opOperand` if the op is bufferized
510/// in place. Return all tensor Values if the op is not bufferizable.
511AliasingValueList AnalysisState::getAliasingValues(OpOperand &opOperand) const {
512 if (auto bufferizableOp =
513 getOptions().dynCastBufferizableOp(op: opOperand.getOwner()))
514 return bufferizableOp.getAliasingValues(opOperand, state: *this);
515
516 // The op is not bufferizable.
517 return detail::unknownGetAliasingValues(opOperand);
518}
519
520/// Return true if `opOperand` bufferizes to a memory read. Return `true` if the
521/// op is not bufferizable.
522bool AnalysisState::bufferizesToMemoryRead(OpOperand &opOperand) const {
523 if (auto bufferizableOp =
524 getOptions().dynCastBufferizableOp(op: opOperand.getOwner()))
525 return bufferizableOp.bufferizesToMemoryRead(opOperand, state: *this);
526
527 // Unknown op that returns a tensor. The inplace analysis does not support it.
528 // Conservatively return true.
529 return true;
530}
531
532/// Return true if `opOperand` bufferizes to a memory write. Return
533/// `true` if the op is not bufferizable.
534bool AnalysisState::bufferizesToMemoryWrite(OpOperand &opOperand) const {
535 if (auto bufferizableOp =
536 getOptions().dynCastBufferizableOp(op: opOperand.getOwner()))
537 return bufferizableOp.bufferizesToMemoryWrite(opOperand, state: *this);
538
539 // Unknown op that returns a tensor. The inplace analysis does not support it.
540 // Conservatively return true.
541 return true;
542}
543
544/// Return true if `opOperand` does neither read nor write but bufferizes to an
545/// alias. Return false if the op is not bufferizable.
546bool AnalysisState::bufferizesToAliasOnly(OpOperand &opOperand) const {
547 if (auto bufferizableOp =
548 getOptions().dynCastBufferizableOp(op: opOperand.getOwner()))
549 return bufferizableOp.bufferizesToAliasOnly(opOperand, state: *this);
550
551 // Unknown op that returns a tensor. The inplace analysis does not support it.
552 // Conservatively return false.
553 return false;
554}
555
556bool AnalysisState::bufferizesToMemoryWrite(Value value) const {
557 auto opResult = llvm::dyn_cast<OpResult>(Val&: value);
558 if (!opResult)
559 return true;
560 auto bufferizableOp = getOptions().dynCastBufferizableOp(value);
561 if (!bufferizableOp)
562 return true;
563 return bufferizableOp.resultBufferizesToMemoryWrite(opResult, state: *this);
564}
565
566/// Return true if the given value is read by an op that bufferizes to a memory
567/// read. Also takes into account ops that create an alias but do not read by
568/// themselves (e.g., ExtractSliceOp).
569bool AnalysisState::isValueRead(Value value) const {
570 assert(llvm::isa<TensorLikeType>(value.getType()) &&
571 "expected TensorLikeType");
572 SmallVector<OpOperand *> workingSet;
573 DenseSet<OpOperand *> visited;
574 for (OpOperand &use : value.getUses())
575 workingSet.push_back(Elt: &use);
576
577 while (!workingSet.empty()) {
578 OpOperand *uMaybeReading = workingSet.pop_back_val();
579 if (!visited.insert(V: uMaybeReading).second)
580 continue;
581
582 // Skip over all ops that neither read nor write (but create an alias).
583 if (bufferizesToAliasOnly(opOperand&: *uMaybeReading))
584 for (AliasingValue alias : getAliasingValues(opOperand&: *uMaybeReading))
585 for (OpOperand &use : alias.value.getUses())
586 workingSet.push_back(Elt: &use);
587 if (bufferizesToMemoryRead(opOperand&: *uMaybeReading))
588 return true;
589 }
590
591 return false;
592}
593
594// Starting from `opOperand`, follow the use-def chain in reverse, always
595// selecting the aliasing OpOperands. Find and return Values for which
596// `condition` evaluates to true. Uses of such matching Values are not
597// traversed any further, the visited aliasing opOperands will be preserved
598// through `visitedOpOperands`.
599llvm::SetVector<Value> AnalysisState::findValueInReverseUseDefChain(
600 OpOperand *opOperand, llvm::function_ref<bool(Value)> condition,
601 TraversalConfig config,
602 llvm::DenseSet<OpOperand *> *visitedOpOperands) const {
603 llvm::DenseSet<Value> visited;
604 llvm::SetVector<Value> result, workingSet;
605 workingSet.insert(X: opOperand->get());
606
607 if (visitedOpOperands)
608 visitedOpOperands->insert(V: opOperand);
609
610 while (!workingSet.empty()) {
611 Value value = workingSet.pop_back_val();
612
613 if (!config.revisitAlreadyVisitedValues && visited.contains(V: value)) {
614 // Stop traversal if value was already visited.
615 if (config.alwaysIncludeLeaves)
616 result.insert(X: value);
617 continue;
618 }
619 visited.insert(V: value);
620
621 if (condition(value)) {
622 result.insert(X: value);
623 continue;
624 }
625
626 if (!config.followUnknownOps && !options.dynCastBufferizableOp(value)) {
627 // Stop iterating if `followUnknownOps` is unset and the op is either
628 // not bufferizable or excluded in the OpFilter.
629 if (config.alwaysIncludeLeaves)
630 result.insert(X: value);
631 continue;
632 }
633
634 AliasingOpOperandList aliases = getAliasingOpOperands(value);
635 if (aliases.getNumAliases() == 0) {
636 // The traversal ends naturally if there are no more OpOperands that
637 // could be followed.
638 if (config.alwaysIncludeLeaves)
639 result.insert(X: value);
640 continue;
641 }
642
643 for (AliasingOpOperand a : aliases) {
644 if (config.followEquivalentOnly &&
645 a.relation != BufferRelation::Equivalent) {
646 // Stop iterating if `followEquivalentOnly` is set but the alias is not
647 // equivalent.
648 if (config.alwaysIncludeLeaves)
649 result.insert(X: value);
650 continue;
651 }
652
653 if (config.followInPlaceOnly && !isInPlace(opOperand&: *a.opOperand)) {
654 // Stop iterating if `followInPlaceOnly` is set but the alias is
655 // out-of-place.
656 if (config.alwaysIncludeLeaves)
657 result.insert(X: value);
658 continue;
659 }
660
661 if (config.followSameTypeOrCastsOnly &&
662 a.opOperand->get().getType() != value.getType() &&
663 !value.getDefiningOp<CastOpInterface>()) {
664 // Stop iterating if `followSameTypeOrCastsOnly` is set but the alias is
665 // has a different type and the op is not a cast.
666 if (config.alwaysIncludeLeaves)
667 result.insert(X: value);
668 continue;
669 }
670
671 workingSet.insert(X: a.opOperand->get());
672 if (visitedOpOperands)
673 visitedOpOperands->insert(V: a.opOperand);
674 }
675 }
676
677 return result;
678}
679
680// Find the values that define the contents of the given operand's value.
681llvm::SetVector<Value>
682AnalysisState::findDefinitions(OpOperand *opOperand) const {
683 TraversalConfig config;
684 config.alwaysIncludeLeaves = false;
685 return findValueInReverseUseDefChain(
686 opOperand, condition: [&](Value v) { return this->bufferizesToMemoryWrite(value: v); },
687 config);
688}
689
690AnalysisState::AnalysisState(const BufferizationOptions &options)
691 : AnalysisState(options, TypeID::get<AnalysisState>()) {}
692
693AnalysisState::AnalysisState(const BufferizationOptions &options, TypeID type)
694 : options(options), type(type) {
695 for (const BufferizationOptions::AnalysisStateInitFn &fn :
696 options.stateInitializers)
697 fn(*this);
698}
699
700bool AnalysisState::canOmitTensorCopy(OpOperand &opOperand) const {
701 // Do not copy if the tensor has undefined contents.
702 if (hasUndefinedContents(opOperand: &opOperand))
703 return true;
704
705 // Do not copy if the buffer of the tensor is entirely overwritten (with
706 // values that do not depend on the old tensor).
707 if (bufferizesToMemoryWrite(opOperand) && !bufferizesToMemoryRead(opOperand))
708 return true;
709
710 // Do not copy if the tensor is never read.
711 AliasingValueList aliases = getAliasingValues(opOperand);
712 if (!bufferizesToMemoryRead(opOperand) &&
713 llvm::none_of(Range&: aliases,
714 P: [&](AliasingValue a) { return isValueRead(value: a.value); }))
715 return true;
716
717 // Default: Cannot omit the copy.
718 return false;
719}
720
721bool AnalysisState::isInPlace(OpOperand &opOperand) const {
722 // ToBufferOps are always in-place.
723 if (isa<ToBufferOp>(Val: opOperand.getOwner()))
724 return true;
725
726 // In the absence of analysis information, OpOperands that bufferize to a
727 // memory write are out-of-place, i.e., an alloc and copy is inserted.
728 return !bufferizesToMemoryWrite(opOperand);
729}
730
731bool AnalysisState::areEquivalentBufferizedValues(Value v1, Value v2) const {
732 // In the absence of analysis information, we do not know if the values are
733 // equivalent. The conservative answer is "false".
734 return false;
735}
736
737bool AnalysisState::areAliasingBufferizedValues(Value v1, Value v2) const {
738 // In the absence of analysis information, we do not know if the values may be
739 // aliasing. The conservative answer is "true".
740 return true;
741}
742
743bool AnalysisState::hasUndefinedContents(OpOperand *opOperand) const {
744 // In the absence of analysis information, the conservative answer is "false".
745 return false;
746}
747
748FailureOr<Value> bufferization::getBuffer(RewriterBase &rewriter, Value value,
749 const BufferizationOptions &options,
750 const BufferizationState &state) {
751#ifndef NDEBUG
752 auto tensorType = llvm::dyn_cast<TensorLikeType>(value.getType());
753 assert(tensorType && "unexpected non-tensor type");
754#endif // NDEBUG
755
756 // Replace "%t = to_tensor %m" with %m.
757 if (auto toTensorOp = value.getDefiningOp<bufferization::ToTensorOp>())
758 return toTensorOp.getBuffer();
759
760 // Insert to_buffer op.
761 OpBuilder::InsertionGuard g(rewriter);
762 setInsertionPointAfter(b&: rewriter, value);
763 FailureOr<BufferLikeType> bufferType = getBufferType(value, options, state);
764 if (failed(Result: bufferType))
765 return failure();
766
767 return bufferization::ToBufferOp::create(builder&: rewriter, location: value.getLoc(),
768 buffer: *bufferType, tensor: value)
769 .getResult();
770}
771
772/// Return the buffer type for a given Value (tensor) after bufferization.
773FailureOr<BufferLikeType>
774bufferization::getBufferType(Value value, const BufferizationOptions &options,
775 const BufferizationState &state) {
776 SmallVector<Value> invocationStack;
777 return getBufferType(value, options, state, invocationStack);
778}
779
780/// Return the buffer type for a given Value (tensor) after bufferization.
781FailureOr<BufferLikeType>
782bufferization::getBufferType(Value value, const BufferizationOptions &options,
783 const BufferizationState &state,
784 SmallVector<Value> &invocationStack) {
785 assert(llvm::isa<TensorLikeType>(value.getType()) &&
786 "unexpected non-tensor type");
787 invocationStack.push_back(Elt: value);
788 llvm::scope_exit popFromStack([&]() { invocationStack.pop_back(); });
789
790 // Try querying BufferizableOpInterface.
791 Operation *op = getOwnerOfValue(value);
792 auto bufferizableOp = options.dynCastBufferizableOp(op);
793 if (bufferizableOp)
794 return bufferizableOp.getBufferType(value, options, state, invocationStack);
795
796 // Op is not bufferizable.
797 auto memSpace =
798 options.defaultMemorySpaceFn(cast<TensorLikeType>(Val: value.getType()));
799 if (!memSpace.has_value())
800 return op->emitError(message: "could not infer memory space");
801
802 return options.unknownTypeConverterFn(cast<TensorLikeType>(Val: value.getType()),
803 *memSpace, options);
804}
805
806bool bufferization::hasTensorSemantics(Operation *op) {
807 if (auto bufferizableOp = dyn_cast<BufferizableOpInterface>(Val: op))
808 return bufferizableOp.hasTensorSemantics();
809 return detail::defaultHasTensorSemantics(op);
810}
811
812void bufferization::replaceOpWithBufferizedValues(RewriterBase &rewriter,
813 Operation *op,
814 ValueRange values) {
815 assert(values.size() == op->getNumResults() &&
816 "expected one value per OpResult");
817 OpBuilder::InsertionGuard g(rewriter);
818
819 // Replace all OpResults with the given values.
820 SmallVector<Value> replacements;
821 for (OpResult opResult : op->getOpResults()) {
822 Value replacement = values[opResult.getResultNumber()];
823 if (llvm::isa<TensorLikeType>(Val: opResult.getType())) {
824 // The OpResult is a tensor. Such values are replaced with memrefs during
825 // bufferization.
826 assert(llvm::isa<BufferLikeType>(replacement.getType()) &&
827 "tensor op result should be replaced with a buffer value");
828 // The existing uses of the OpResult still expect a tensor. Insert a
829 // ToTensorOp. Throughout bufferization, this ToTensorOp will gradually
830 // loose all of its users and eventually DCE away.
831 rewriter.setInsertionPointAfter(op);
832 replacement = bufferization::ToTensorOp::create(
833 builder&: rewriter, location: replacement.getLoc(), result: opResult.getType(), buffer: replacement);
834 }
835 replacements.push_back(Elt: replacement);
836 }
837
838 rewriter.replaceOp(op, newValues: replacements);
839}
840
841//===----------------------------------------------------------------------===//
842// Bufferization-specific IRMapping support with debugging.
843//===----------------------------------------------------------------------===//
844
845BaseMemRefType
846bufferization::getMemRefTypeWithFullyDynamicLayout(TensorType tensorType,
847 Attribute memorySpace) {
848 // Case 1: Unranked memref type.
849 if (auto unrankedTensorType =
850 llvm::dyn_cast<UnrankedTensorType>(Val&: tensorType)) {
851 return UnrankedMemRefType::get(elementType: unrankedTensorType.getElementType(),
852 memorySpace);
853 }
854
855 // Case 2: Ranked memref type.
856 return ::getMemRefTypeWithFullyDynamicLayout(
857 shape: tensorType.getShape(), elementType: tensorType.getElementType(), memorySpace);
858}
859
860/// Return a MemRef type with a static identity layout (i.e., no layout map). If
861/// the given tensor type is unranked, return an unranked MemRef type.
862BaseMemRefType
863bufferization::getMemRefTypeWithStaticIdentityLayout(TensorType tensorType,
864 Attribute memorySpace) {
865 // Case 1: Unranked memref type.
866 if (auto unrankedTensorType =
867 llvm::dyn_cast<UnrankedTensorType>(Val&: tensorType)) {
868 return UnrankedMemRefType::get(elementType: unrankedTensorType.getElementType(),
869 memorySpace);
870 }
871
872 // Case 2: Ranked memref type.
873 auto rankedTensorType = llvm::cast<RankedTensorType>(Val&: tensorType);
874 MemRefLayoutAttrInterface layout = {};
875 return MemRefType::get(shape: rankedTensorType.getShape(),
876 elementType: rankedTensorType.getElementType(), layout,
877 memorySpace);
878}
879
880//===----------------------------------------------------------------------===//
881// Default implementations of interface methods
882//===----------------------------------------------------------------------===//
883
884bool bufferization::detail::defaultResultBufferizesToMemoryWrite(
885 OpResult opResult, const AnalysisState &state) {
886 auto bufferizableOp = cast<BufferizableOpInterface>(Val: opResult.getDefiningOp());
887 AliasingOpOperandList opOperands =
888 bufferizableOp.getAliasingOpOperands(value: opResult, state);
889
890 // Case 1: OpResults that have no aliasing OpOperand usually bufferize to
891 // memory writes.
892 if (opOperands.getAliases().empty())
893 return true;
894
895 // Case 2: If an aliasing OpOperand bufferizes to a memory write, the OpResult
896 // may bufferize to a memory write.
897 if (llvm::any_of(Range&: opOperands, P: [&](AliasingOpOperand alias) {
898 return state.bufferizesToMemoryWrite(opOperand&: *alias.opOperand);
899 }))
900 return true;
901
902 // Case 3: Check if a nested aliasing OpOperand value bufferizes to a memory
903 // write. (Or: The reverse SSA use-def chain ends inside the reigon.) In that
904 // case, the OpResult bufferizes to a memory write. E.g.:
905 //
906 // %0 = "some_writing_op" : tensor<?xf32>
907 // %r = scf.if ... -> tensor<?xf32> {
908 // scf.yield %0 : tensor<?xf32>
909 // } else {
910 // %1 = "another_writing_op"(%0) : tensor<?xf32>
911 // scf.yield %1 : tensor<?xf32>
912 // }
913 // "some_reading_op"(%r)
914 //
915 // %r bufferizes to a memory write because an aliasing OpOperand value (%1)
916 // bufferizes to a memory write and the defining op is inside the scf.if.
917 //
918 // Note: This treatment of surrouding ops is useful for ops that have a
919 // region but no OpOperand such as scf.if or scf.execute_region. It simplifies
920 // the analysis considerably.
921 //
922 // "another_writing_op" in the above example should be able to bufferize
923 // inplace in the absence of another read of %0. However, if the scf.if op
924 // would not be considered a "write", the analysis would detect the
925 // following conflict:
926 //
927 // * read = some_reading_op
928 // * lastWrite = %0 (Note: The last write of %r would be a set: {%0, %1}.)
929 // * conflictingWrite = %1
930 //
931 auto isMemoryWriteInsideOp = [&](Value v) {
932 Operation *op = getOwnerOfValue(value: v);
933 if (!opResult.getDefiningOp()->isAncestor(other: op))
934 return false;
935 return state.bufferizesToMemoryWrite(value: v);
936 };
937 TraversalConfig config;
938 config.alwaysIncludeLeaves = false;
939 for (AliasingOpOperand alias : opOperands) {
940 if (!state
941 .findValueInReverseUseDefChain(opOperand: alias.opOperand,
942 condition: isMemoryWriteInsideOp, config)
943 .empty())
944 return true;
945 }
946 return false;
947}
948
949// Compute the AliasingOpOperandList for a given Value based on
950// getAliasingValues.
951AliasingOpOperandList bufferization::detail::defaultGetAliasingOpOperands(
952 Value value, const AnalysisState &state) {
953 Operation *op = getOwnerOfValue(value);
954 SmallVector<AliasingOpOperand> result;
955 for (OpOperand &opOperand : op->getOpOperands()) {
956 if (!llvm::isa<TensorLikeType>(Val: opOperand.get().getType()))
957 continue;
958 AliasingValueList aliasingValues = state.getAliasingValues(opOperand);
959 for (const auto &it : aliasingValues)
960 if (it.value == value)
961 result.emplace_back(Args: &opOperand, Args: it.relation, Args: it.isDefinite);
962 }
963 return AliasingOpOperandList(std::move(result));
964}
965
966FailureOr<BufferLikeType> bufferization::detail::defaultGetBufferType(
967 Value value, const BufferizationOptions &options,
968 const BufferizationState &bufferizationState,
969 SmallVector<Value> &invocationStack) {
970 assert(llvm::isa<TensorType>(value.getType()) && "expected tensor type");
971 auto tensorType = cast<TensorType>(Val: value.getType());
972
973 auto elementType = tensorType.getElementType();
974
975 if (!BaseMemRefType::isValidElementType(type: elementType))
976 return getOwnerOfValue(value)->emitError()
977 << "cannot bufferize value of type " << tensorType
978 << ": element type " << elementType
979 << " is not a valid memref element type";
980
981 // No further analysis is possible for a block argument.
982 if (llvm::isa<BlockArgument>(Val: value)) {
983 return options.unknownTypeConverterFn(cast<TensorLikeType>(Val&: tensorType),
984 /*memorySpace=*/nullptr, options);
985 }
986
987 // Value is an OpResult.
988 Operation *op = getOwnerOfValue(value);
989 auto opResult = llvm::cast<OpResult>(Val&: value);
990 AnalysisState analysisState(options);
991 AliasingOpOperandList aliases = analysisState.getAliasingOpOperands(value: opResult);
992 if (aliases.getNumAliases() > 0 &&
993 aliases.getAliases()[0].relation == BufferRelation::Equivalent) {
994 // If the OpResult has an equivalent OpOperand, both OpResult and
995 // OpOperand bufferize to the exact same buffer type.
996 Value equivalentOperand = aliases.getAliases().front().opOperand->get();
997 return getBufferType(value: equivalentOperand, options, state: bufferizationState,
998 invocationStack);
999 }
1000
1001 // If we do not know the memory space and there is no default memory space,
1002 // report a failure.
1003 auto memSpace =
1004 options.defaultMemorySpaceFn(cast<TensorLikeType>(Val&: tensorType));
1005 if (!memSpace.has_value())
1006 return op->emitError(message: "could not infer memory space");
1007
1008 return options.unknownTypeConverterFn(cast<TensorLikeType>(Val&: tensorType),
1009 *memSpace, options);
1010}
1011
1012bool bufferization::detail::defaultIsRepetitiveRegion(
1013 BufferizableOpInterface bufferizableOp, unsigned index) {
1014 assert(index < bufferizableOp->getNumRegions() && "invalid region index");
1015 auto regionInterface =
1016 dyn_cast<RegionBranchOpInterface>(Val: bufferizableOp.getOperation());
1017 if (!regionInterface)
1018 return false;
1019 return regionInterface.isRepetitiveRegion(index);
1020}
1021
1022AliasingOpOperandList
1023bufferization::detail::unknownGetAliasingOpOperands(Value value) {
1024 // TODO: Take into account successor blocks.
1025 // No aliasing in case of non-entry blocks.
1026 if (auto bbArg = dyn_cast<BlockArgument>(Val&: value))
1027 if (bbArg.getOwner() != &bbArg.getOwner()->getParent()->getBlocks().front())
1028 return {};
1029
1030 // Unknown op: Conservatively assume that each OpResult may alias with every
1031 // OpOperand. In addition, each block argument of an entry block may alias
1032 // with every OpOperand.
1033 AliasingOpOperandList r;
1034 for (OpOperand &operand : value.getDefiningOp()->getOpOperands())
1035 if (isa<TensorLikeType>(Val: operand.get().getType()))
1036 r.addAlias(alias: {&operand, BufferRelation::Unknown, /*isDefinite=*/false});
1037 return r;
1038}
1039
1040AliasingValueList
1041bufferization::detail::unknownGetAliasingValues(OpOperand &opOperand) {
1042 // TODO: Take into account successor blocks.
1043 // Unknown op: Conservatively assume that each OpResult may alias with every
1044 // OpOperand. In addition, each block argument of an entry block may alias
1045 // with every OpOperand.
1046 AliasingValueList r;
1047 for (OpResult result : opOperand.getOwner()->getOpResults())
1048 if (llvm::isa<TensorLikeType>(Val: result.getType()))
1049 r.addAlias(alias: {result, BufferRelation::Unknown, /*isDefinite=*/false});
1050 for (Region &region : opOperand.getOwner()->getRegions())
1051 if (!region.getBlocks().empty())
1052 for (BlockArgument bbArg : region.getBlocks().front().getArguments())
1053 if (isa<TensorLikeType>(Val: bbArg.getType()))
1054 r.addAlias(alias: {bbArg, BufferRelation::Unknown, /*isDefinite=*/false});
1055 return r;
1056}
1057
1058bool bufferization::detail::defaultHasTensorSemantics(Operation *op) {
1059 auto isaTensor = [](Type t) { return isa<TensorLikeType>(Val: t); };
1060 bool hasTensorBlockArgument = any_of(Range: op->getRegions(), P: [&](Region &r) {
1061 return any_of(Range&: r.getBlocks(), P: [&](Block &b) {
1062 return any_of(Range: b.getArguments(), P: [&](BlockArgument bbArg) {
1063 return isaTensor(bbArg.getType());
1064 });
1065 });
1066 });
1067 if (hasTensorBlockArgument)
1068 return true;
1069
1070 if (any_of(Range: op->getResultTypes(), P: isaTensor))
1071 return true;
1072 return any_of(Range: op->getOperandTypes(), P: isaTensor);
1073}
1074
1075FailureOr<BaseMemRefType>
1076bufferization::detail::asMemRefType(FailureOr<BufferLikeType> bufferType) {
1077 if (failed(Result: bufferType))
1078 return failure();
1079 return cast<BaseMemRefType>(Val&: *bufferType);
1080}
1081
1082bool bufferization::detail::typesMatchAfterBufferization(Operation &op,
1083 Value tensor,
1084 Value buffer) {
1085 return mlir::succeeded(
1086 Result: cast<TensorLikeType>(Val: tensor.getType())
1087 .verifyCompatibleBufferType(bufferType: cast<BufferLikeType>(Val: buffer.getType()),
1088 emitError: [&]() { return op.emitError(); }));
1089}
1090