1//===- Bufferize.cpp - Bufferization utilities ----------------------------===//
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/Transforms/Passes.h"
10
11#include "mlir/Dialect/Bufferization/IR/BufferizableOpInterface.h"
12#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
13#include "mlir/Dialect/Bufferization/Transforms/Bufferize.h"
14#include "mlir/Dialect/Bufferization/Transforms/OneShotAnalysis.h"
15#include "mlir/Dialect/Bufferization/Transforms/OneShotModuleBufferize.h"
16#include "mlir/Dialect/Bufferization/Transforms/Transforms.h"
17#include "mlir/Dialect/MemRef/IR/MemRef.h"
18#include "mlir/IR/Diagnostics.h"
19#include "mlir/IR/Operation.h"
20#include "mlir/Interfaces/ControlFlowInterfaces.h"
21#include "mlir/Interfaces/SideEffectInterfaces.h"
22#include "mlir/Pass/PassManager.h"
23#include "llvm/Support/DebugLog.h"
24#include <optional>
25
26namespace mlir {
27namespace bufferization {
28#define GEN_PASS_DEF_ONESHOTBUFFERIZEPASS
29#include "mlir/Dialect/Bufferization/Transforms/Passes.h.inc"
30} // namespace bufferization
31} // namespace mlir
32
33#define DEBUG_TYPE "bufferize"
34
35using namespace mlir;
36using namespace mlir::bufferization;
37
38namespace {
39
40static OneShotBufferizationOptions::AnalysisHeuristic
41parseHeuristicOption(const std::string &s) {
42 if (s == "bottom-up")
43 return OneShotBufferizationOptions::AnalysisHeuristic::BottomUp;
44 if (s == "top-down")
45 return OneShotBufferizationOptions::AnalysisHeuristic::TopDown;
46 if (s == "bottom-up-from-terminators")
47 return OneShotBufferizationOptions::AnalysisHeuristic::
48 BottomUpFromTerminators;
49 if (s == "fuzzer")
50 return OneShotBufferizationOptions::AnalysisHeuristic::Fuzzer;
51 llvm_unreachable("invalid analysisheuristic option");
52}
53
54struct OneShotBufferizePass
55 : public bufferization::impl::OneShotBufferizePassBase<
56 OneShotBufferizePass> {
57 using Base::Base;
58
59 void runOnOperation() override {
60 OneShotBufferizationOptions opt;
61 if (!options) {
62 // Make new bufferization options if none were provided when creating the
63 // pass.
64 opt.allowReturnAllocsFromLoops = allowReturnAllocsFromLoops;
65 opt.allowUnknownOps = allowUnknownOps;
66 opt.analysisFuzzerSeed = analysisFuzzerSeed;
67 opt.analysisHeuristic = parseHeuristicOption(s: analysisHeuristic);
68 opt.copyBeforeWrite = copyBeforeWrite;
69 opt.dumpAliasSets = dumpAliasSets;
70 opt.setFunctionBoundaryTypeConversion(functionBoundaryTypeConversion);
71
72 if (mustInferMemorySpace && useEncodingForMemorySpace) {
73 emitError(loc: getOperation()->getLoc())
74 << "only one of 'must-infer-memory-space' and "
75 "'use-encoding-for-memory-space' are allowed in "
76 << getArgument();
77 return signalPassFailure();
78 }
79
80 if (mustInferMemorySpace) {
81 opt.defaultMemorySpaceFn =
82 [](TensorLikeType t) -> std::optional<Attribute> {
83 return std::nullopt;
84 };
85 }
86
87 if (useEncodingForMemorySpace) {
88 opt.defaultMemorySpaceFn =
89 [](TensorLikeType t) -> std::optional<Attribute> {
90 if (auto rtt = dyn_cast<RankedTensorType>(Val&: t))
91 return rtt.getEncoding();
92 return std::nullopt;
93 };
94 }
95
96 opt.printConflicts = printConflicts;
97 opt.bufferAlignment = bufferAlignment;
98 opt.testAnalysisOnly = testAnalysisOnly;
99 opt.bufferizeFunctionBoundaries = bufferizeFunctionBoundaries;
100 if (!mayHaveParallelRegions)
101 opt.mayHaveParallelRegions = false;
102 opt.noAnalysisFuncFilter = noAnalysisFuncFilter;
103
104 // Configure type converter.
105 LayoutMapOption unknownTypeConversionOption = unknownTypeConversion;
106 if (unknownTypeConversionOption == LayoutMapOption::InferLayoutMap) {
107 emitError(loc: UnknownLoc::get(context: &getContext()),
108 message: "Invalid option: 'infer-layout-map' is not a valid value for "
109 "'unknown-type-conversion'");
110 return signalPassFailure();
111 }
112 opt.unknownTypeConverterFn = [=](TensorLikeType type,
113 Attribute memorySpace,
114 const BufferizationOptions &options) {
115 const auto tensorType = cast<TensorType>(Val&: type);
116 if (unknownTypeConversionOption == LayoutMapOption::IdentityLayoutMap)
117 return cast<bufferization::BufferLikeType>(
118 Val: bufferization::getMemRefTypeWithStaticIdentityLayout(
119 tensorType, memorySpace));
120 assert(unknownTypeConversionOption ==
121 LayoutMapOption::FullyDynamicLayoutMap &&
122 "invalid layout map option");
123 return cast<bufferization::BufferLikeType>(
124 Val: bufferization::getMemRefTypeWithFullyDynamicLayout(tensorType,
125 memorySpace));
126 };
127
128 // Configure op filter.
129 OpFilter::Entry::FilterFn filterFn = [&](Operation *op) {
130 // Filter may be specified via options.
131 if (this->dialectFilter.hasValue() && !(*this->dialectFilter).empty())
132 return llvm::is_contained(Range&: this->dialectFilter,
133 Element: op->getDialect()->getNamespace());
134 // No filter specified: All other ops are allowed.
135 return true;
136 };
137 opt.opFilter.allowOperation(fn: filterFn);
138 } else {
139 opt = *options;
140 }
141
142 if (opt.copyBeforeWrite && opt.testAnalysisOnly) {
143 // These two flags do not make sense together: "copy-before-write"
144 // indicates that copies should be inserted before every memory write,
145 // but "test-analysis-only" indicates that only the analysis should be
146 // tested. (I.e., no IR is bufferized.)
147 emitError(loc: UnknownLoc::get(context: &getContext()),
148 message: "Invalid option: 'copy-before-write' cannot be used with "
149 "'test-analysis-only'");
150 return signalPassFailure();
151 }
152
153 if (opt.printConflicts && !opt.testAnalysisOnly) {
154 emitError(
155 loc: UnknownLoc::get(context: &getContext()),
156 message: "Invalid option: 'print-conflicts' requires 'test-analysis-only'");
157 return signalPassFailure();
158 }
159
160 if (opt.dumpAliasSets && !opt.testAnalysisOnly) {
161 emitError(
162 loc: UnknownLoc::get(context: &getContext()),
163 message: "Invalid option: 'dump-alias-sets' requires 'test-analysis-only'");
164 return signalPassFailure();
165 }
166
167 BufferizationState state;
168 BufferizationStatistics statistics;
169 ModuleOp moduleOp = getOperation();
170 if (opt.bufferizeFunctionBoundaries) {
171 if (failed(
172 Result: runOneShotModuleBufferize(moduleOp, options: opt, state, statistics: &statistics))) {
173 signalPassFailure();
174 return;
175 }
176 } else {
177 if (!opt.noAnalysisFuncFilter.empty()) {
178 emitError(loc: UnknownLoc::get(context: &getContext()),
179 message: "Invalid option: 'no-analysis-func-filter' requires "
180 "'bufferize-function-boundaries'");
181 return signalPassFailure();
182 }
183 if (failed(Result: runOneShotBufferize(op: moduleOp, options: opt, state, statistics: &statistics))) {
184 signalPassFailure();
185 return;
186 }
187 }
188
189 // Set pass statistics.
190 this->numBufferAlloc = statistics.numBufferAlloc;
191 this->numTensorInPlace = statistics.numTensorInPlace;
192 this->numTensorOutOfPlace = statistics.numTensorOutOfPlace;
193 }
194
195private:
196 std::optional<OneShotBufferizationOptions> options;
197};
198} // namespace
199
200//===----------------------------------------------------------------------===//
201// BufferizableOpInterface-based Bufferization
202//===----------------------------------------------------------------------===//
203
204namespace {
205/// A rewriter that keeps track of extra information during bufferization.
206class BufferizationRewriter : public IRRewriter, public RewriterBase::Listener {
207public:
208 BufferizationRewriter(MLIRContext *ctx, DenseSet<Operation *> &erasedOps,
209 DenseSet<Operation *> &toBufferOps,
210 SmallVector<Operation *> &worklist,
211 const BufferizationOptions &options,
212 BufferizationStatistics *statistics)
213 : IRRewriter(ctx), erasedOps(erasedOps), toBufferOps(toBufferOps),
214 worklist(worklist), analysisState(options), statistics(statistics) {
215 setListener(this);
216 }
217
218protected:
219 void notifyOperationErased(Operation *op) override {
220 erasedOps.insert(V: op);
221 // Erase if present.
222 toBufferOps.erase(V: op);
223 }
224
225 void notifyOperationInserted(Operation *op, InsertPoint previous) override {
226 // We only care about newly created ops.
227 if (previous.isSet())
228 return;
229
230 erasedOps.erase(V: op);
231
232 // Gather statistics about allocs.
233 if (statistics) {
234 if (auto sideEffectingOp = dyn_cast<MemoryEffectOpInterface>(Val: op))
235 statistics->numBufferAlloc += static_cast<int64_t>(
236 sideEffectingOp.hasEffect<MemoryEffects::Allocate>());
237 }
238
239 // Keep track of to_buffer ops.
240 if (isa<ToBufferOp>(Val: op)) {
241 toBufferOps.insert(V: op);
242 return;
243 }
244
245 // Skip to_tensor ops.
246 if (isa<ToTensorOp>(Val: op))
247 return;
248
249 // Skip non-tensor ops.
250 if (!hasTensorSemantics(op))
251 return;
252
253 // Skip ops that are not allowed to be bufferized.
254 auto const &options = analysisState.getOptions();
255 if (!options.isOpAllowed(op))
256 return;
257
258 // Add op to worklist.
259 worklist.push_back(Elt: op);
260 }
261
262private:
263 /// A set of all erased ops.
264 DenseSet<Operation *> &erasedOps;
265
266 /// A set of all to_buffer ops.
267 DenseSet<Operation *> &toBufferOps;
268
269 /// The worklist of ops to be bufferized.
270 SmallVector<Operation *> &worklist;
271
272 /// The analysis state. Used for debug assertions and access to the
273 /// bufferization options.
274 const AnalysisState analysisState;
275
276 /// Bufferization statistics for debugging.
277 BufferizationStatistics *statistics;
278};
279} // namespace
280
281LogicalResult bufferization::bufferizeOp(Operation *op,
282 const BufferizationOptions &options,
283 BufferizationState &bufferizationState,
284 BufferizationStatistics *statistics) {
285 if (options.copyBeforeWrite) {
286 AnalysisState analysisState(options);
287 if (failed(Result: insertTensorCopies(op, analysisState, bufferizationState)))
288 return failure();
289 }
290
291 // Keep track of to_buffer ops.
292 DenseSet<Operation *> toBufferOps;
293 op->walk(callback: [&](ToBufferOp toBufferOp) { toBufferOps.insert(V: toBufferOp); });
294
295 // Gather all bufferizable ops in top-to-bottom order.
296 //
297 // We should ideally know the exact memref type of all operands when
298 // bufferizing an op. (This is the case when bufferizing top-to-bottom.)
299 // Otherwise, we have to use a memref type with a fully dynamic layout map to
300 // avoid copies. We are currently missing patterns for layout maps to
301 // canonicalize away (or canonicalize to more precise layouts).
302 SmallVector<Operation *> worklist;
303 op->walk<WalkOrder::PostOrder>(callback: [&](Operation *op) {
304 if (options.isOpAllowed(op) && hasTensorSemantics(op))
305 worklist.push_back(Elt: op);
306 });
307
308 // Keep track of all erased ops.
309 DenseSet<Operation *> erasedOps;
310
311 // Bufferize all ops.
312 BufferizationRewriter rewriter(op->getContext(), erasedOps, toBufferOps,
313 worklist, options, statistics);
314 for (unsigned i = 0; i < worklist.size(); ++i) {
315 Operation *nextOp = worklist[i];
316 // Skip ops that were erased.
317 if (erasedOps.contains(V: nextOp))
318 continue;
319 // Skip ops that are not bufferizable or not allowed.
320 auto bufferizableOp = options.dynCastBufferizableOp(op: nextOp);
321 if (!bufferizableOp)
322 continue;
323 // Skip ops that no longer have tensor semantics.
324 if (!hasTensorSemantics(op: nextOp))
325 continue;
326 // Check for unsupported unstructured control flow.
327 if (!bufferizableOp.supportsUnstructuredControlFlow())
328 for (Region &r : nextOp->getRegions())
329 if (r.getBlocks().size() > 1)
330 return nextOp->emitOpError(
331 message: "op or BufferizableOpInterface implementation does not support "
332 "unstructured control flow, but at least one region has multiple "
333 "blocks");
334
335 // Bufferize the op.
336 LDBG(3) << "//===-------------------------------------------===//\n"
337 << "IR after bufferizing: " << nextOp->getName();
338 rewriter.setInsertionPoint(nextOp);
339 if (failed(
340 Result: bufferizableOp.bufferize(rewriter, options, state&: bufferizationState))) {
341 LDBG(2) << "failed to bufferize\n"
342 << "//===-------------------------------------------===//";
343 return nextOp->emitError(message: "failed to bufferize op");
344 }
345 LDBG(3) << *op << "\n//===-------------------------------------------===//";
346 }
347
348 // Return early if the top-level op is entirely gone.
349 if (erasedOps.contains(V: op))
350 return success();
351
352 // Fold all to_buffer(to_tensor(x)) pairs. Snapshot the set first:
353 // `foldToBufferToTensorPair` can erase ops, and the rewriter listener
354 // mutates `toBufferOps` from inside that call, which would invalidate
355 // any DenseSet iterator held across it.
356 SmallVector<Operation *> toBufferOpsSnapshot = llvm::to_vector(Range&: toBufferOps);
357 for (Operation *op : toBufferOpsSnapshot) {
358 if (erasedOps.contains(V: op))
359 continue;
360 rewriter.setInsertionPoint(op);
361 (void)bufferization::foldToBufferToTensorPair(
362 rewriter, toBuffer: cast<ToBufferOp>(Val: op), options);
363 }
364
365 // Remove all dead to_tensor ops.
366 op->walk<WalkOrder::PostOrder>(callback: [&](ToTensorOp toTensorOp) {
367 if (toTensorOp->getUses().empty()) {
368 rewriter.eraseOp(op: toTensorOp);
369 return WalkResult::skip();
370 }
371 return WalkResult::advance();
372 });
373
374 /// Check the result of bufferization. Return an error if an op was not
375 /// bufferized, unless partial bufferization is allowed.
376 if (options.allowUnknownOps)
377 return success();
378
379 for (Operation *op : worklist) {
380 // Skip ops that are entirely gone.
381 if (erasedOps.contains(V: op))
382 continue;
383 // Ops that no longer have tensor semantics (because they were updated
384 // in-place) are allowed.
385 if (!hasTensorSemantics(op))
386 continue;
387 // Continue ops that are not allowed.
388 if (!options.isOpAllowed(op))
389 continue;
390 // Ops without any uses and no side effects will fold away.
391 if (op->getUses().empty() && isMemoryEffectFree(op))
392 continue;
393 // ToTensorOps/ToBufferOps are allowed in the output.
394 if (isa<ToTensorOp, ToBufferOp>(Val: op))
395 continue;
396 return op->emitError(message: "op was not bufferized");
397 }
398
399 return success();
400}
401
402LogicalResult
403bufferization::bufferizeBlockSignature(Block *block, RewriterBase &rewriter,
404 const BufferizationOptions &options,
405 BufferizationState &state) {
406 OpBuilder::InsertionGuard g(rewriter);
407 auto bufferizableOp = options.dynCastBufferizableOp(op: block->getParentOp());
408 if (!bufferizableOp)
409 return failure();
410
411 // Compute the new signature.
412 SmallVector<Type> newTypes;
413 for (BlockArgument &bbArg : block->getArguments()) {
414 auto tensorType = dyn_cast<TensorLikeType>(Val: bbArg.getType());
415 if (!tensorType) {
416 newTypes.push_back(Elt: bbArg.getType());
417 continue;
418 }
419
420 FailureOr<BufferLikeType> bufferType =
421 bufferization::getBufferType(value: bbArg, options, state);
422 if (failed(Result: bufferType))
423 return failure();
424 newTypes.push_back(Elt: *bufferType);
425 }
426
427 // Change the type of all block arguments.
428 for (auto [bbArg, type] : llvm::zip(t: block->getArguments(), u&: newTypes)) {
429 if (bbArg.getType() == type)
430 continue;
431
432 // Collect all uses of the bbArg.
433 SmallVector<OpOperand *> bbArgUses;
434 for (OpOperand &use : bbArg.getUses())
435 bbArgUses.push_back(Elt: &use);
436
437 Type tensorType = bbArg.getType();
438 // Change the bbArg type to memref.
439 bbArg.setType(type);
440
441 // Replace all uses of the original tensor bbArg.
442 rewriter.setInsertionPointToStart(block);
443 if (!bbArgUses.empty()) {
444 Value toTensorOp = bufferization::ToTensorOp::create(
445 builder&: rewriter, location: bbArg.getLoc(), result: tensorType, buffer: bbArg);
446 for (OpOperand *use : bbArgUses)
447 use->set(toTensorOp);
448 }
449 }
450
451 // Bufferize callers of the block. Iterate BlockOperands so each successor
452 // edge is handled once, including when one branch op targets this block more
453 // than once.
454 for (BlockOperand &blockOperand : block->getUses()) {
455 Operation *op = blockOperand.getOwner();
456 auto branchOp = dyn_cast<BranchOpInterface>(Val: op);
457 if (!branchOp)
458 return op->emitOpError(message: "cannot bufferize ops with block references that "
459 "do not implement BranchOpInterface");
460
461 SuccessorOperands operands =
462 branchOp.getSuccessorOperands(index: blockOperand.getOperandNumber());
463 SmallVector<Value> newOperands;
464 for (auto [operand, type] :
465 llvm::zip(t: operands.getForwardedOperands(), u&: newTypes)) {
466 if (operand.getType() == type) {
467 // Not a tensor type. Nothing to do for this operand.
468 newOperands.push_back(Elt: operand);
469 continue;
470 }
471 FailureOr<BufferLikeType> operandBufferType =
472 bufferization::getBufferType(value: operand, options, state);
473 if (failed(Result: operandBufferType))
474 return failure();
475 rewriter.setInsertionPointAfterValue(operand);
476 Value bufferizedOperand = bufferization::ToBufferOp::create(
477 builder&: rewriter, location: operand.getLoc(), buffer: *operandBufferType, tensor: operand);
478 // A cast is needed if the operand and the block argument have different
479 // bufferized types.
480 if (type != *operandBufferType) {
481 bufferizedOperand = *options.castFn(rewriter, operand.getLoc(), type,
482 bufferizedOperand);
483 }
484 newOperands.push_back(Elt: bufferizedOperand);
485 }
486 operands.getMutableForwardedOperands().assign(values: newOperands);
487 }
488
489 return success();
490}
491