1//===- BlockPackMatmul.cpp - Linalg matmul block packing ------------------===//
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/Linalg/Passes.h"
10
11#include "mlir/Dialect/Arith/IR/Arith.h"
12#include "mlir/Dialect/Linalg/IR/Linalg.h"
13#include "mlir/Dialect/Linalg/Transforms/Transforms.h"
14#include "mlir/Dialect/Linalg/Utils/Utils.h"
15#include "mlir/Dialect/Vector/IR/VectorOps.h"
16#include "mlir/IR/PatternMatch.h"
17#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
18#include "llvm/ADT/SmallVector.h"
19
20#include <optional>
21
22namespace mlir {
23#define GEN_PASS_DEF_LINALGBLOCKPACKMATMUL
24#include "mlir/Dialect/Linalg/Passes.h.inc"
25} // namespace mlir
26
27using namespace mlir;
28using namespace mlir::linalg;
29
30/// Return constant range span or nullopt, otherwise.
31static std::optional<int64_t> getConstantRange(const Range &range) {
32 std::optional<int64_t> stride = getConstantIntValue(ofr: range.stride);
33 if (!stride || *stride != 1)
34 return std::nullopt;
35 std::optional<int64_t> offset = getConstantIntValue(ofr: range.offset);
36 if (!offset)
37 return std::nullopt;
38 std::optional<int64_t> size = getConstantIntValue(ofr: range.size);
39 if (!size)
40 return std::nullopt;
41 return (*size - *offset);
42}
43
44/// Return true if all dimensions are fully divisible by the respective tiles.
45static bool validateFullTilesOnDims(linalg::LinalgOp linalgOp,
46 ArrayRef<OpFoldResult> tiles,
47 ArrayRef<int64_t> dims) {
48 if (dims.size() != tiles.size() || tiles.empty())
49 return false;
50
51 FailureOr<ContractionDimensions> contractDims =
52 inferContractionDims(linalgOp);
53 if (failed(Result: contractDims))
54 return false;
55 unsigned batchDimsOffset = contractDims->batch.size();
56
57 // Skip the batch dimension if present.
58 // Offset all dimensions accordingly.
59 SmallVector<int64_t, 3> offsetDims(dims);
60 for (int64_t &offsetDim : offsetDims)
61 offsetDim += batchDimsOffset;
62
63 auto tileOp = cast<TilingInterface>(Val: linalgOp.getOperation());
64 OpBuilder builder(tileOp);
65 OpBuilder::InsertionGuard guard(builder);
66 SmallVector<Range> iterationDomain = tileOp.getIterationDomain(b&: builder);
67
68 for (auto dim : llvm::enumerate(First&: offsetDims)) {
69 if (dim.value() >= static_cast<int64_t>(iterationDomain.size()))
70 return false;
71
72 std::optional<int64_t> tileSize = getConstantIntValue(ofr: tiles[dim.index()]);
73 std::optional<int64_t> rangeOnDim =
74 getConstantRange(range: iterationDomain[dim.value()]);
75
76 // If the tile factor or the range are non-constant, the tile size is
77 // considered to be invalid.
78 if (!tileSize || !rangeOnDim)
79 return false;
80
81 // The dimension must be fully divisible by the tile.
82 if (*rangeOnDim % *tileSize != 0)
83 return false;
84 }
85
86 return true;
87}
88
89/// Return failure or packed matmul with one of its operands transposed.
90static FailureOr<PackTransposeResult>
91transposePackedMatmul(RewriterBase &rewriter, linalg::LinalgOp linalgOp,
92 linalg::PackOp packOp, AffineMap operandMap,
93 ArrayRef<unsigned> blocksStartDimPos,
94 bool transposeOuterBlocks, bool transposeInnerBlocks) {
95 // Pack/unpack memref transformations are unsupported. The memref forms
96 // are mainly for bufferization and scalar lowering. Other uses are not
97 // recommended, see #225650 for details.
98 if (!packOp.hasPureTensorSemantics())
99 return failure();
100
101 assert(operandMap.getNumDims() >= 4 &&
102 "expected at least 4D prepacked matmul");
103 assert(blocksStartDimPos.size() >= 2 &&
104 "expected starting outer and inner block positions");
105
106 // Bias toward innermost dimensions.
107 unsigned outerBlockPos = operandMap.getNumResults() - 4;
108 unsigned innerBlockPos = operandMap.getNumResults() - 2;
109
110 // Transpose control options define the desired block and element layout.
111 // Block transposition (outer dimensions) or element transposition (inner
112 // dimensions) may not be necessary depending on the original matmul data
113 // layout.
114 bool isOuterTransposed =
115 operandMap.getDimPosition(idx: outerBlockPos) != blocksStartDimPos.end()[-2];
116 bool isInnerTransposed =
117 operandMap.getDimPosition(idx: innerBlockPos) != blocksStartDimPos.back();
118
119 // Transpose only the dimensions that need that to conform to the provided
120 // transpotion settings.
121 SmallVector<int64_t> innerPerm = {0, 1};
122 if (isInnerTransposed != transposeInnerBlocks)
123 innerPerm = {1, 0};
124 SmallVector<int64_t> outerPerm = {0, 1};
125 if (isOuterTransposed != transposeOuterBlocks)
126 outerPerm = {1, 0};
127
128 // Leave the outer dimensions, like batch, unchanged by offsetting all
129 // outer dimensions permutations.
130 SmallVector<int64_t> offsetPerms;
131 for (auto i : llvm::seq(Begin: 0u, End: outerBlockPos))
132 offsetPerms.push_back(Elt: i);
133 for (auto perm : outerPerm)
134 offsetPerms.push_back(Elt: perm + outerBlockPos);
135 outerPerm = offsetPerms;
136
137 FailureOr<PackTransposeResult> packTransposedMatmul =
138 packTranspose(rewriter, packOp, linalgOp,
139 /*maybeUnPackOp=*/nullptr, outerPerm, innerPerm);
140
141 return packTransposedMatmul;
142}
143
144/// Pack a matmul operation into blocked 4D layout.
145FailureOr<PackResult>
146linalg::blockPackMatmul(RewriterBase &rewriter, linalg::LinalgOp linalgOp,
147 const ControlBlockPackMatmulFn &controlPackMatmul) {
148 // Check to not let go the batch_matmul with extended semantic, through this
149 // transform.
150 if (auto *batchMatmulOp = dyn_cast<linalg::BatchMatmulOp>(Val: &linalgOp)) {
151 if (batchMatmulOp->hasUserDefinedMaps()) {
152 return rewriter.notifyMatchFailure(
153 arg&: *batchMatmulOp,
154 msg: "only batch_matmul ops with non-extended semantics are supported");
155 }
156 }
157
158 if (linalgOp.hasPureBufferSemantics())
159 return rewriter.notifyMatchFailure(arg&: linalgOp, msg: "require tensor semantics");
160
161 std::optional<BlockPackMatmulOptions> options = controlPackMatmul(linalgOp);
162 if (!options)
163 return rewriter.notifyMatchFailure(arg&: linalgOp, msg: "invalid packing options");
164
165 if (options->blockFactors.size() != 3)
166 return rewriter.notifyMatchFailure(arg&: linalgOp, msg: "require 3 tile factors");
167
168 bool hasScalable = !options->scalableBlockFactors.empty();
169 if (hasScalable && options->scalableBlockFactors.size() != 3)
170 return rewriter.notifyMatchFailure(
171 arg&: linalgOp, msg: "scalableBlockFactors must be empty or have 3 elements");
172
173 // Scalable tile sizes are non-constant at compile time, so they can never
174 // satisfy the full-tile divisibility check. Reject early before creating
175 // any ops to avoid modifying IR before returning notifyMatchFailure.
176 if (!options->allowPadding && hasScalable)
177 return rewriter.notifyMatchFailure(
178 arg&: linalgOp, msg: "scalable block factors require padding");
179
180 SmallVector<OpFoldResult> mnkTiles;
181 for (auto [idx, factor] : llvm::enumerate(First&: options->blockFactors)) {
182 bool isScalable = hasScalable && options->scalableBlockFactors[idx];
183 if (!isScalable) {
184 mnkTiles.push_back(Elt: rewriter.getIndexAttr(value: factor));
185 continue;
186 }
187 Value cst =
188 arith::ConstantIndexOp::create(builder&: rewriter, location: linalgOp.getLoc(), value: factor);
189 Value vscale = vector::VectorScaleOp::create(builder&: rewriter, location: linalgOp.getLoc(),
190 result: rewriter.getIndexType());
191 mnkTiles.push_back(
192 Elt: arith::MulIOp::create(builder&: rewriter, location: linalgOp.getLoc(), lhs: cst, rhs: vscale)
193 .getResult());
194 }
195
196 // If padding is disabled, make sure that dimensions can be packed cleanly.
197 if (!options->allowPadding &&
198 !validateFullTilesOnDims(linalgOp, tiles: mnkTiles, dims: options->mnkOrder)) {
199 return rewriter.notifyMatchFailure(arg&: linalgOp,
200 msg: "expect packing full tiles only");
201 }
202
203 OpBuilder::InsertionGuard guard(rewriter);
204 // The op is replaced, we need to set the insertion point after it.
205 rewriter.setInsertionPointAfter(linalgOp);
206
207 // Pack the matmul operation into blocked layout with two levels of
208 // subdivision:
209 // - major 2D blocks - outer dimensions, consist of minor blocks
210 // - minor 2D blocks - inner dimensions, consist of scalar elements
211 FailureOr<PackResult> packedMatmul = packMatmulGreedily(
212 rewriter, linalgOp, mnkPackedSizes: mnkTiles, mnkPaddedSizesNextMultipleOf: options->mnkPaddedSizesNextMultipleOf,
213 mnkOrder: options->mnkOrder);
214 if (failed(Result: packedMatmul))
215 return failure();
216
217 assert(packedMatmul->packOps.size() == 3 &&
218 "invalid number of pack ops after matmul packing");
219 assert(packedMatmul->unPackOps.size() == 1 &&
220 "invalid number of unpack ops after matmul packing");
221
222 FailureOr<ContractionDimensions> contractDims =
223 inferContractionDims(linalgOp: packedMatmul->packedLinalgOp);
224 if (failed(Result: contractDims))
225 return failure();
226
227 auto genericOp =
228 dyn_cast<linalg::GenericOp>(Val: packedMatmul->packedLinalgOp.getOperation());
229 SmallVector<AffineMap> maps = genericOp.getIndexingMapsArray();
230
231 // Transpose LHS matrix according to the options.
232 FailureOr<PackTransposeResult> packedLhs = transposePackedMatmul(
233 rewriter, linalgOp: packedMatmul->packedLinalgOp, packOp: packedMatmul->packOps[0], operandMap: maps[0],
234 blocksStartDimPos: contractDims->m, transposeOuterBlocks: options->lhsTransposeOuterBlocks,
235 transposeInnerBlocks: options->lhsTransposeInnerBlocks);
236 if (failed(Result: packedLhs))
237 return failure();
238
239 // Update results.
240 packedMatmul->packOps[0] = packedLhs->transposedPackOp;
241 packedMatmul->packedLinalgOp = packedLhs->transposedLinalgOp;
242
243 // Transpose RHS matrix according to the options.
244 FailureOr<PackTransposeResult> packedRhs = transposePackedMatmul(
245 rewriter, linalgOp: packedMatmul->packedLinalgOp, packOp: packedMatmul->packOps[1], operandMap: maps[1],
246 blocksStartDimPos: contractDims->k, transposeOuterBlocks: options->rhsTransposeOuterBlocks,
247 transposeInnerBlocks: options->rhsTransposeInnerBlocks);
248 if (failed(Result: packedRhs))
249 return failure();
250
251 // Update results.
252 packedMatmul->packOps[1] = packedRhs->transposedPackOp;
253 packedMatmul->packedLinalgOp = packedRhs->transposedLinalgOp;
254
255 return packedMatmul;
256}
257
258namespace {
259template <typename OpTy>
260struct BlockPackMatmul : public OpRewritePattern<OpTy> {
261 BlockPackMatmul(MLIRContext *context, ControlBlockPackMatmulFn fun,
262 PatternBenefit benefit = 1)
263 : OpRewritePattern<OpTy>(context, benefit), controlFn(std::move(fun)) {}
264
265 LogicalResult matchAndRewrite(OpTy linalgOp,
266 PatternRewriter &rewriter) const override {
267 FailureOr<PackResult> packedMatmul =
268 blockPackMatmul(rewriter, linalgOp, controlFn);
269 if (failed(Result: packedMatmul))
270 return failure();
271 return success();
272 }
273
274private:
275 ControlBlockPackMatmulFn controlFn;
276};
277
278template <>
279struct BlockPackMatmul<linalg::GenericOp>
280 : public OpRewritePattern<linalg::GenericOp> {
281 BlockPackMatmul(MLIRContext *context, ControlBlockPackMatmulFn fun,
282 PatternBenefit benefit = 1)
283 : OpRewritePattern<linalg::GenericOp>(context, benefit),
284 controlFn(std::move(fun)) {}
285
286 LogicalResult matchAndRewrite(linalg::GenericOp linalgOp,
287 PatternRewriter &rewriter) const override {
288 // Match suitable generics.
289 if (!linalg::isaContractionOpInterface(linalgOp)) {
290 return rewriter.notifyMatchFailure(arg&: linalgOp, msg: "not a contraction");
291 }
292
293 using MapList = ArrayRef<ArrayRef<AffineExpr>>;
294 auto infer = [&](MapList m) {
295 return AffineMap::inferFromExprList(exprsList: m, context: linalgOp.getContext());
296 };
297
298 AffineExpr i, j, k;
299 bindDims(ctx: linalgOp->getContext(), exprs&: i, exprs&: j, exprs&: k);
300 SmallVector<AffineMap> maps = linalgOp.getIndexingMapsArray();
301
302 // For now, only match simple matmuls.
303 if (!(maps == infer({{i, k}, {k, j}, {i, j}}) ||
304 maps == infer({{k, i}, {k, j}, {i, j}}) ||
305 maps == infer({{i, k}, {j, k}, {i, j}}))) {
306 return rewriter.notifyMatchFailure(arg&: linalgOp, msg: "not a suitable matmul");
307 }
308
309 FailureOr<PackResult> packedMatmul =
310 blockPackMatmul(rewriter, linalgOp, controlPackMatmul: controlFn);
311 if (failed(Result: packedMatmul))
312 return failure();
313 return success();
314 }
315
316private:
317 ControlBlockPackMatmulFn controlFn;
318};
319
320/// Convert linalg matmul ops to block layout and back.
321struct LinalgBlockPackMatmul
322 : public impl::LinalgBlockPackMatmulBase<LinalgBlockPackMatmul> {
323 using LinalgBlockPackMatmulBase::LinalgBlockPackMatmulBase;
324
325 void runOnOperation() override {
326 Operation *op = getOperation();
327 RewritePatternSet patterns(&getContext());
328
329 ControlBlockPackMatmulFn controlFn =
330 [&](linalg::LinalgOp op) -> BlockPackMatmulOptions {
331 BlockPackMatmulOptions options;
332
333 // Parse block-factors strings. Each element is either "N" (static) or
334 // "[N]" (scalable, i.e. N * vscale at runtime).
335 for (const std::string &blockFactor : *blockFactors) {
336 StringRef factor(blockFactor);
337 if (factor.starts_with(Prefix: "[") && factor.ends_with(Suffix: "]")) {
338 int64_t val = 0;
339 factor.drop_front().drop_back().getAsInteger(Radix: 10, Result&: val);
340 options.blockFactors.push_back(Elt: val);
341 options.scalableBlockFactors.push_back(Elt: true);
342 } else {
343 int64_t val = 0;
344 factor.getAsInteger(Radix: 10, Result&: val);
345 options.blockFactors.push_back(Elt: val);
346 options.scalableBlockFactors.push_back(Elt: false);
347 }
348 }
349 // If all flags are false, clear the vector so blockPackMatmul can take
350 // the cheaper static path.
351 if (llvm::none_of(Range&: options.scalableBlockFactors, P: [](bool b) { return b; }))
352 options.scalableBlockFactors.clear();
353
354 options.allowPadding = allowPadding;
355 options.mnkPaddedSizesNextMultipleOf =
356 SmallVector<int64_t>{*mnkPaddedSizesNextMultipleOf};
357 if (!mnkOrder.empty())
358 options.mnkOrder = SmallVector<int64_t>{*mnkOrder};
359 options.lhsTransposeOuterBlocks = lhsTransposeOuterBlocks;
360 options.lhsTransposeInnerBlocks = lhsTransposeInnerBlocks;
361 options.rhsTransposeOuterBlocks = rhsTransposeOuterBlocks;
362 options.rhsTransposeInnerBlocks = rhsTransposeInnerBlocks;
363 return options;
364 };
365
366 linalg::populateBlockPackMatmulPatterns(patterns, controlFn);
367 if (failed(Result: applyPatternsGreedily(op, patterns: std::move(patterns))))
368 return signalPassFailure();
369 }
370};
371} // namespace
372
373void linalg::populateBlockPackMatmulPatterns(
374 RewritePatternSet &patterns, const ControlBlockPackMatmulFn &controlFn) {
375 patterns.add<BlockPackMatmul<linalg::GenericOp>,
376 BlockPackMatmul<linalg::MatmulOp>,
377 BlockPackMatmul<linalg::BatchMatmulOp>>(arg: patterns.getContext(),
378 args: controlFn);
379}
380