| 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 | |
| 27 | using 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. |
| 34 | static 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. |
| 49 | static 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. |
| 143 | FailureOr<memref::AllocOp> |
| 144 | mlir::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 | |
| 291 | FailureOr<memref::AllocOp> |
| 292 | mlir::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 | |