1//===----------- MultiBuffering.cpp ---------------------------------------===//
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// This file implements multi buffering transformation.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/Affine/IR/AffineOps.h"
14#include "mlir/Dialect/Arith/Utils/Utils.h"
15#include "mlir/Dialect/MemRef/IR/MemRef.h"
16#include "mlir/Dialect/MemRef/Transforms/Transforms.h"
17#include "mlir/IR/AffineExpr.h"
18#include "mlir/IR/BuiltinAttributes.h"
19#include "mlir/IR/Dominance.h"
20#include "mlir/IR/PatternMatch.h"
21#include "mlir/IR/ValueRange.h"
22#include "mlir/Interfaces/LoopLikeInterface.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/ADT/TypeSwitch.h"
25#include "llvm/Support/Debug.h"
26
27using namespace mlir;
28
29#define DEBUG_TYPE "memref-transforms"
30#define DBGS() (llvm::dbgs() << "[" DEBUG_TYPE "]: ")
31#define DBGSNL() (llvm::dbgs() << "\n")
32
33/// Return true if the op fully overwrite the given `buffer` value.
34static bool overrideBuffer(Operation *op, Value buffer) {
35 auto copyOp = dyn_cast<memref::CopyOp>(Val: op);
36 if (!copyOp)
37 return false;
38 return copyOp.getTarget() == buffer;
39}
40
41/// Replace the uses of `oldOp` with the given `val` and for view-like uses
42/// propagate the type change. Changing the memref type may require propagating
43/// it through view-like ops (subview, expand_shape, collapse_shape, cast) so
44/// we need to propagate the type change and erase old view ops.
45///
46/// Only view-like ops whose result type can be recomputed from the new source
47/// type and existing op attributes are handled here. Other ops fall back to
48/// operand replacement without type propagation.
49static LogicalResult replaceUsesAndPropagateType(RewriterBase &rewriter,
50 Operation *oldOp, Value val) {
51 SmallVector<Operation *> opsToErase;
52 // Iterate with early_inc to erase current user inside the loop.
53 for (OpOperand &use : llvm::make_early_inc_range(Range: oldOp->getUses())) {
54 Operation *user = use.getOwner();
55 OpBuilder::InsertionGuard g(rewriter);
56 rewriter.setInsertionPoint(user);
57 MemRefType srcType = cast<MemRefType>(Val: val.getType());
58
59 // Try to create a new view-like op with updated result type.
60 // Each view-like op has its own method to compute the result type.
61 bool typeInferenceFailed = false;
62 Value replacement =
63 llvm::TypeSwitch<Operation *, Value>(user)
64 .Case(caseFn: [&](memref::SubViewOp subview) -> Value {
65 MemRefType newType =
66 memref::SubViewOp::inferRankReducedResultType(
67 resultShape: subview.getType().getShape(), sourceMemRefType: srcType,
68 staticOffsets: subview.getStaticOffsets(), staticSizes: subview.getStaticSizes(),
69 staticStrides: subview.getStaticStrides());
70 return memref::SubViewOp::create(
71 builder&: rewriter, location: subview->getLoc(), resultType: newType, source: val,
72 offsets: subview.getMixedOffsets(), sizes: subview.getMixedSizes(),
73 strides: subview.getMixedStrides());
74 })
75 .Case(caseFn: [&](memref::ExpandShapeOp expand) -> Value {
76 FailureOr<MemRefType> newType =
77 memref::ExpandShapeOp::computeExpandedType(
78 srcType, resultShape: expand.getResultType().getShape(),
79 reassociation: expand.getReassociationIndices());
80 if (failed(Result: newType)) {
81 typeInferenceFailed = true;
82 return Value();
83 }
84 return memref::ExpandShapeOp::create(
85 builder&: rewriter, location: expand->getLoc(), resultType: *newType, src: val,
86 reassociation: expand.getReassociationIndices(),
87 outputShape: expand.getMixedOutputShape());
88 })
89 .Case(caseFn: [&](memref::CollapseShapeOp collapse) -> Value {
90 FailureOr<MemRefType> newType =
91 memref::CollapseShapeOp::computeCollapsedType(
92 srcType, reassociation: collapse.getReassociationIndices());
93 if (failed(Result: newType)) {
94 typeInferenceFailed = true;
95 return Value();
96 }
97 return memref::CollapseShapeOp::create(
98 builder&: rewriter, location: collapse->getLoc(), resultType: *newType, src: val,
99 reassociation: collapse.getReassociationIndices());
100 })
101 .Case(caseFn: [&](memref::CastOp cast) -> Value {
102 if (!memref::CastOp::areCastCompatible(inputs: srcType, outputs: cast.getType())) {
103 typeInferenceFailed = true;
104 return Value();
105 }
106 return memref::CastOp::create(builder&: rewriter, location: cast->getLoc(),
107 dest: cast.getType(), source: val);
108 })
109 .Default(defaultFn: [&](Operation *) -> Value { return Value(); });
110
111 if (typeInferenceFailed) {
112 user->emitOpError(
113 message: "failed to compute view-like result type after multi-buffering");
114 return failure();
115 }
116
117 if (replacement) {
118 // Recursively propagate through view-like ops and mark old op for
119 // erasure.
120 if (failed(Result: replaceUsesAndPropagateType(rewriter, oldOp: user, val: replacement)))
121 return failure();
122 opsToErase.push_back(Elt: user);
123 } else {
124 // Not a view-like op: just replace operand.
125 rewriter.startOpModification(op: user);
126 use.set(val);
127 rewriter.finalizeOpModification(op: user);
128 }
129 }
130
131 for (Operation *op : opsToErase) {
132 rewriter.eraseOp(op);
133 }
134
135 return success();
136}
137
138// Transformation to do multi-buffering/array expansion to remove dependencies
139// on the temporary allocation between consecutive loop iterations.
140// Returns success if the transformation happened and failure otherwise.
141// This is not a pattern as it requires propagating the new memref type to its
142// uses and requires updating subview ops.
143FailureOr<memref::AllocOp>
144mlir::memref::multiBuffer(RewriterBase &rewriter, memref::AllocOp allocOp,
145 unsigned multiBufferingFactor,
146 bool skipOverrideAnalysis) {
147 LLVM_DEBUG(DBGS() << "Start multibuffering: " << allocOp << "\n");
148 DominanceInfo dom(allocOp->getParentOp());
149 LoopLikeOpInterface candidateLoop;
150 for (Operation *user : allocOp->getUsers()) {
151 auto parentLoop = user->getParentOfType<LoopLikeOpInterface>();
152 if (!parentLoop) {
153 if (isa<memref::DeallocOp>(Val: user)) {
154 // Allow dealloc outside of any loop.
155 // TODO: The whole precondition function here is very brittle and will
156 // need to rethought an isolated into a cleaner analysis.
157 continue;
158 }
159 LLVM_DEBUG(DBGS() << "--no parent loop -> fail\n");
160 LLVM_DEBUG(DBGS() << "----due to user: " << *user << "\n");
161 return failure();
162 }
163 if (!skipOverrideAnalysis) {
164 /// Make sure there is no loop-carried dependency on the allocation.
165 if (!overrideBuffer(op: user, buffer: allocOp.getResult())) {
166 LLVM_DEBUG(DBGS() << "--Skip user: found loop-carried dependence\n");
167 continue;
168 }
169 // If this user doesn't dominate all the other users keep looking.
170 if (llvm::any_of(Range: allocOp->getUsers(), P: [&](Operation *otherUser) {
171 return !dom.dominates(a: user, b: otherUser);
172 })) {
173 LLVM_DEBUG(
174 DBGS() << "--Skip user: does not dominate all other users\n");
175 continue;
176 }
177 } else {
178 if (llvm::any_of(Range: allocOp->getUsers(), P: [&](Operation *otherUser) {
179 return !isa<memref::DeallocOp>(Val: otherUser) &&
180 !parentLoop->isProperAncestor(other: otherUser);
181 })) {
182 LLVM_DEBUG(
183 DBGS()
184 << "--Skip user: not all other users are in the parent loop\n");
185 continue;
186 }
187 }
188 candidateLoop = parentLoop;
189 break;
190 }
191
192 if (!candidateLoop) {
193 LLVM_DEBUG(DBGS() << "Skip alloc: no candidate loop\n");
194 return failure();
195 }
196
197 std::optional<Value> inductionVar = candidateLoop.getSingleInductionVar();
198 std::optional<OpFoldResult> lowerBound = candidateLoop.getSingleLowerBound();
199 std::optional<OpFoldResult> singleStep = candidateLoop.getSingleStep();
200 if (!inductionVar || !lowerBound || !singleStep ||
201 !llvm::hasSingleElement(C: candidateLoop.getLoopRegions())) {
202 LLVM_DEBUG(DBGS() << "Skip alloc: no single iv, lb, step or region\n");
203 return failure();
204 }
205
206 if (!dom.dominates(a: allocOp.getOperation(), b: candidateLoop)) {
207 LLVM_DEBUG(DBGS() << "Skip alloc: does not dominate candidate loop\n");
208 return failure();
209 }
210
211 LLVM_DEBUG(DBGS() << "Start multibuffering loop: " << candidateLoop << "\n");
212
213 // 1. Construct the multi-buffered memref type.
214 ArrayRef<int64_t> originalShape = allocOp.getType().getShape();
215 SmallVector<int64_t, 4> multiBufferedShape{multiBufferingFactor};
216 llvm::append_range(C&: multiBufferedShape, R&: originalShape);
217 LLVM_DEBUG(DBGS() << "--original type: " << allocOp.getType() << "\n");
218 MemRefType mbMemRefType = MemRefType::Builder(allocOp.getType())
219 .setShape(multiBufferedShape)
220 .setLayout(MemRefLayoutAttrInterface());
221 LLVM_DEBUG(DBGS() << "--multi-buffered type: " << mbMemRefType << "\n");
222
223 // 2. Create the multi-buffered alloc.
224 Location loc = allocOp->getLoc();
225 OpBuilder::InsertionGuard g(rewriter);
226 rewriter.setInsertionPoint(allocOp);
227 auto mbAlloc = memref::AllocOp::create(
228 builder&: rewriter, location: loc, memrefType: mbMemRefType, dynamicSizes: ValueRange{}, alignment: allocOp.getAlignmentAttr());
229 mbAlloc->setDiscardableAttrs(allocOp->getDiscardableAttrDictionary());
230 LLVM_DEBUG(DBGS() << "--multi-buffered alloc: " << mbAlloc << "\n");
231
232 // 3. Within the loop, build the modular leading index (i.e. each loop
233 // iteration %iv accesses slice ((%iv - %lb) / %step) % %mb_factor).
234 rewriter.setInsertionPointToStart(
235 &candidateLoop.getLoopRegions().front()->front());
236 Value ivVal = *inductionVar;
237 Value lbVal = getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: *lowerBound);
238 Value stepVal = getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: *singleStep);
239 AffineExpr iv, lb, step;
240 bindDims(ctx: rewriter.getContext(), exprs&: iv, exprs&: lb, exprs&: step);
241 Value bufferIndex = affine::makeComposedAffineApply(
242 b&: rewriter, loc, e: ((iv - lb).floorDiv(other: step)) % multiBufferingFactor,
243 operands: {ivVal, lbVal, stepVal});
244 LLVM_DEBUG(DBGS() << "--multi-buffered indexing: " << bufferIndex << "\n");
245
246 // 4. Build the subview accessing the particular slice, taking modular
247 // rotation into account.
248 int64_t mbMemRefTypeRank = mbMemRefType.getRank();
249 IntegerAttr zero = rewriter.getIndexAttr(value: 0);
250 IntegerAttr one = rewriter.getIndexAttr(value: 1);
251 SmallVector<OpFoldResult> offsets(mbMemRefTypeRank, zero);
252 SmallVector<OpFoldResult> sizes(mbMemRefTypeRank, one);
253 SmallVector<OpFoldResult> strides(mbMemRefTypeRank, one);
254 // Offset is [bufferIndex, 0 ... 0 ].
255 offsets.front() = bufferIndex;
256 // Sizes is [1, original_size_0 ... original_size_n ].
257 for (int64_t i = 0, e = originalShape.size(); i != e; ++i)
258 sizes[1 + i] = rewriter.getIndexAttr(value: originalShape[i]);
259 // Strides is [1, 1 ... 1 ].
260 MemRefType dstMemref = memref::SubViewOp::inferRankReducedResultType(
261 resultShape: originalShape, sourceMemRefType: mbMemRefType, staticOffsets: offsets, staticSizes: sizes, staticStrides: strides);
262 Value subview = memref::SubViewOp::create(builder&: rewriter, location: loc, resultType: dstMemref, source: mbAlloc,
263 offsets, sizes, strides);
264 LLVM_DEBUG(DBGS() << "--multi-buffered slice: " << subview << "\n");
265
266 // 5. Due to the recursive nature of replaceUsesAndPropagateType , we need
267 // to handle dealloc uses separately..
268 for (OpOperand &use : llvm::make_early_inc_range(Range: allocOp->getUses())) {
269 auto deallocOp = dyn_cast<memref::DeallocOp>(Val: use.getOwner());
270 if (!deallocOp)
271 continue;
272 OpBuilder::InsertionGuard g(rewriter);
273 rewriter.setInsertionPoint(deallocOp);
274 auto newDeallocOp =
275 memref::DeallocOp::create(builder&: rewriter, location: deallocOp->getLoc(), memref: mbAlloc);
276 (void)newDeallocOp;
277 LLVM_DEBUG(DBGS() << "----Created dealloc: " << newDeallocOp << "\n");
278 rewriter.eraseOp(op: deallocOp);
279 }
280
281 // 6. RAUW with the particular slice, taking modular rotation into account.
282 if (failed(Result: replaceUsesAndPropagateType(rewriter, oldOp: allocOp, val: subview)))
283 return failure();
284
285 // 7. Finally, erase the old allocOp.
286 rewriter.eraseOp(op: allocOp);
287
288 return mbAlloc;
289}
290
291FailureOr<memref::AllocOp>
292mlir::memref::multiBuffer(memref::AllocOp allocOp,
293 unsigned multiBufferingFactor,
294 bool skipOverrideAnalysis) {
295 IRRewriter rewriter(allocOp->getContext());
296 return multiBuffer(rewriter, allocOp, multiBufferingFactor,
297 skipOverrideAnalysis);
298}
299