1//===- VectorContractMultiLevelUnroll.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#include "mlir/Dialect/SCF/IR/SCF.h"
10#include "mlir/Dialect/Utils/StaticValueUtils.h"
11#include "mlir/Dialect/Vector/IR/VectorOps.h"
12#include "mlir/Dialect/Vector/Transforms/VectorRewritePatterns.h"
13#include "mlir/Dialect/Vector/Utils/VectorUtils.h"
14#include "mlir/Dialect/X86/Transforms.h"
15#include "mlir/Dialect/X86/Utils/X86Utils.h"
16
17#include "mlir/IR/BuiltinAttributes.h"
18#include "mlir/IR/PatternMatch.h"
19#include "mlir/Transforms/LoopInvariantCodeMotionUtils.h"
20
21#define DEBUG_TYPE "x86-vector-contract-multi-level-unroll"
22
23using namespace mlir;
24
25using llvm::all_of;
26using llvm::drop_begin;
27
28// Discardable attribute to control vector unroll patterns.
29static constexpr auto nativeShapeAttrName = "x86_vcmlu_native_shape";
30
31namespace {
32// Shared state for the pattern match and IR transformation.
33struct MLUCandidate {
34 // Anchor operation.
35 vector::ContractionOp contract;
36 bool isInVnniLayout = false;
37
38 // Shape of the original contraction.
39 VectorType accType;
40 VectorType lhsType;
41 VectorType rhsType;
42 int64_t contractK;
43
44 // Shape of the register-tiled contraction. We'll insert a loop nest to cover
45 // the original shape.
46 VectorType accRegTileType;
47 VectorType lhsRegTileType;
48 VectorType rhsRegTileType;
49
50 // Shape of the native contraction (for the X86 nanokernel patterns). We'll
51 // unroll the register-tiled contraction to this shape.
52 VectorType accNativeType;
53 VectorType lhsNativeType;
54 VectorType rhsNativeType;
55 SmallVector<int64_t> contractNativeShape;
56
57 // Bookkeeping for the accumulation loop and operands.
58 scf::ForOp accLoop;
59 Value accInitVal;
60
61 bool accIsZeroInit = false;
62 vector::TransferReadOp lhsRead;
63 vector::TransferReadOp rhsRead;
64
65 // Memory backing the accumulator.
66 Value accMemIn;
67 Value accMemOut;
68
69 // Reconstructed accumulation loop(s) with native-shaped iter_args.
70 scf::ForOp slicedAccLoop;
71 scf::ForOp slicedInnerAccLoop;
72
73 // Keep track of operations that should be deleted after transformation
74 // (depending on which ops could be integrated into the new loop nest).
75 SmallVector<Operation *> opsToDelete;
76};
77
78// A target-specific function that inspects the given types and shape of a
79// candidate contraction, and tries to compute a decomposition strategy encoded
80// as the desired register-tiled and native shapes. If successful, the result is
81// filled into the `contractRegTileShape` and `contractNativeShape` containers.
82using MatchTypesAndShapeFn = std::function<LogicalResult(
83 Type inputElemType, Type accumulatorElemType, bool isInVnniLayout,
84 ArrayRef<int64_t> contractShape,
85 SmallVectorImpl<int64_t> &contractRegTileShape,
86 SmallVectorImpl<int64_t> &contractNativeShape)>;
87} // anonymous namespace
88
89//----------------------------------------------------------------------------//
90// Forward declarations //
91//----------------------------------------------------------------------------//
92
93static void buildMNLoopBody(MLUCandidate &candidate, OpBuilder &b, Location loc,
94 Value ivM, Value ivN);
95static SmallVector<Value> buildKLLoopBody(MLUCandidate &candidate, OpBuilder &b,
96 Location loc, Value ivM, Value ivN,
97 Value ivK, Value ivL,
98 ValueRange iterArgs);
99
100//----------------------------------------------------------------------------//
101// Utilities //
102//----------------------------------------------------------------------------//
103
104// Return true if the argument is an all-zero vector.
105static bool isZeroVector(Value v) {
106 auto constOp = v.getDefiningOp<arith::ConstantOp>();
107 if (!constOp)
108 return false;
109 auto denseAttr = dyn_cast<DenseElementsAttr>(Val: constOp.getValue());
110 if (!denseAttr || !denseAttr.isSplat())
111 return false;
112
113 return isZeroIntegerOrFloat(v: denseAttr.getSplatValue<Attribute>());
114}
115
116// Return true if given vector.transfer_read/write has a default permutation
117// map, no mask and no out-of-bounds check.
118static bool isSimpleTransferOp(VectorTransferOpInterface op) {
119 return op.getPermutationMap().isMinorIdentity() && !op.getMask() &&
120 !op.hasOutOfBoundsDim();
121}
122
123// Return true if start and end are in the same block and there are no ops with
124// memory effects between them.
125static bool noMemoryEffectsBetween(Operation *start, Operation *end) {
126 if (start->getBlock() != end->getBlock() || !start->isBeforeInBlock(other: end))
127 return false;
128
129 for (Operation *op = start->getNextNode(); op && op != end;
130 op = op->getNextNode()) {
131 if (!isMemoryEffectFree(op))
132 return false;
133 }
134 return true;
135}
136
137// Create a rank-reducing subview of a memref that matches the target vector
138// type, e.g. with targetType = vector<64x32xbf16>:
139//
140// memref.subview %A[%block_m, %block_k, 0, 0] [1, 1, 64, 32] [1, 1, 1, 1]
141// : memref<?x?x64x32xbf16> to
142// memref<64x32xbf16, strided<[32, 1], offset: ?>>
143static Value makeRankReducingSubview(OpBuilder &b, Location loc, Value base,
144 ValueRange indices,
145 VectorType targetType) {
146 auto *ctx = b.getContext();
147
148 auto baseType = dyn_cast<MemRefType>(Val: base.getType());
149 assert(baseType && "base must be a MemRefType");
150
151 int64_t baseRank = baseType.getRank();
152 int64_t targetRank = targetType.getRank();
153 assert(targetRank <= baseRank && "target shape's rank > memref's rank");
154
155 ArrayRef<int64_t> targetShape = targetType.getShape();
156
157 SmallVector<int64_t> sizesInt(baseType.getRank(), 1);
158 copy(Range&: targetShape, Out: sizesInt.begin() + baseRank - targetRank);
159 SmallVector<int64_t> stridesInt(baseRank, 1);
160
161 auto offsets = getAsOpFoldResult(values: indices);
162 auto sizes = getAsIndexOpFoldResult(ctx, values: sizesInt);
163 auto strides = getAsIndexOpFoldResult(ctx, values: stridesInt);
164
165 MemRefType rankReducedType = memref::SubViewOp::inferRankReducedResultType(
166 resultShape: targetShape, sourceMemRefType: baseType, staticOffsets: offsets, staticSizes: sizes, staticStrides: strides);
167 return memref::SubViewOp::create(builder&: b, location: loc, resultType: rankReducedType, source: base, offsets,
168 sizes, strides);
169}
170
171// Slice a 2D vector into smaller tiles of the given native type.
172static SmallVector<Value> slice(OpBuilder &b, Location loc, Value value,
173 VectorType nativeType) {
174 VectorType regTileType = dyn_cast<VectorType>(Val: value.getType());
175 assert(regTileType && "can only slice vector values");
176 ArrayRef<int64_t> regTileShape = regTileType.getShape();
177 ArrayRef<int64_t> nativeShape = nativeType.getShape();
178
179 assert(regTileShape.size() == 2 && nativeShape.size() == 2 &&
180 "Only 2D shapes are supported");
181
182 int64_t regTileM = regTileShape[0];
183 int64_t regTileN = regTileShape[1];
184 int64_t nativeM = nativeShape[0];
185 int64_t nativeN = nativeShape[1];
186
187 SmallVector<Value> result;
188 result.reserve(N: (regTileM / nativeM) * (regTileN / nativeN));
189
190 for (int64_t m = 0; m < regTileM; m += nativeM)
191 for (int64_t n = 0; n < regTileN; n += nativeN)
192 result.push_back(Elt: vector::ExtractStridedSliceOp::create(
193 builder&: b, location: loc, source: value, offsets: ArrayRef<int64_t>{m, n}, sizes: nativeShape,
194 strides: ArrayRef<int64_t>{1, 1}));
195
196 return result;
197}
198
199// Splice smaller tiles back into a 2D vector of the given register tile type.
200static Value splice(OpBuilder &b, Location loc, ValueRange values,
201 VectorType regTileType) {
202 auto types = values.getTypes();
203 assert(!types.empty() && all_equal(types) &&
204 "All values must have the same type");
205
206 VectorType nativeType = dyn_cast<VectorType>(Val: types.front());
207 assert(nativeType && "can only splice vector values");
208
209 ArrayRef<int64_t> nativeShape = nativeType.getShape();
210 ArrayRef<int64_t> regTileShape = regTileType.getShape();
211
212 assert(nativeShape.size() == 2 && regTileShape.size() == 2 &&
213 "Only 2D shapes are supported");
214
215 int64_t nativeM = nativeShape[0];
216 int64_t nativeN = nativeShape[1];
217 int64_t regTileM = regTileShape[0];
218 int64_t regTileN = regTileShape[1];
219
220 assert((regTileM / nativeM) * (regTileN / nativeN) ==
221 static_cast<int64_t>(values.size()) &&
222 "The number of values must match the number of slices");
223
224 Value result = ub::PoisonOp::create(builder&: b, location: loc, result: regTileType);
225
226 auto valueIt = values.begin();
227 for (int64_t m = 0; m < regTileM; m += nativeM)
228 for (int64_t n = 0; n < regTileN; n += nativeN) {
229 result = vector::InsertStridedSliceOp::create(builder&: b, location: loc, valueToStore: *valueIt, dest: result,
230 offsets: ArrayRef<int64_t>{m, n},
231 strides: ArrayRef<int64_t>{1, 1});
232 ++valueIt;
233 }
234
235 return result;
236}
237
238static std::optional<SmallVector<int64_t>>
239getFromNativeShapeAttr(Operation *op) {
240 auto attr = op->getAttrOfType<DenseI64ArrayAttr>(name: nativeShapeAttrName);
241 if (!attr)
242 return std::nullopt;
243 return SmallVector<int64_t>(attr.asArrayRef());
244}
245
246static void setNativeShapeAttr(VectorTransferOpInterface op,
247 VectorType nativeType) {
248 if (op.getVectorType() != nativeType)
249 op->setAttr(
250 name: nativeShapeAttrName,
251 value: DenseI64ArrayAttr::get(context: nativeType.getContext(), content: nativeType.getShape()));
252}
253
254//----------------------------------------------------------------------------//
255// Pattern match and target shape computation //
256//----------------------------------------------------------------------------//
257
258// Establish whether the candidate contraction is a canonical matrix
259// multiplication on flat or VNNI-packed vectors. If successful, the discovered
260// operand/accumulator types and the extent of the main reduction dimension are
261// recorded in the candidate struct.
262//
263// Example (flat):
264// vector.contract {
265// kind = #vector.kind<add>, indexing_maps = [
266// affine_map<(dm, dn, dk) -> (dm, dk)>,
267// affine_map<(dm, dn, dk) -> (dk, dn)>,
268// affine_map<(dm, dn, dk) -> (dm, dn)>],
269// iterator_types = ["parallel", "parallel", "reduction"],
270// } %lhs, %rhs, %acc : !lhsType, !rhsType into !accType
271//
272// Example (VNNI-packed):
273// vector.contract {
274// kind = #vector.kind<add>, indexing_maps = [
275// affine_map<(dm, dn, dk, dvnni) -> (dm, dk, dvnni)>,
276// affine_map<(dm, dn, dk, dvnni) -> (dk, dn, dvnni)>,
277// affine_map<(dm, dn, dk, dvnni) -> (dm, dn)>],
278// iterator_types = ["parallel", "parallel", "reduction", "reduction"],
279// } %lhs, %rhs, %acc : !lhsType, !rhsType into !accType
280static LogicalResult matchCanonicalMatmul(MLUCandidate &candidate,
281 PatternRewriter &rewriter) {
282 vector::ContractionOp contract = candidate.contract;
283 if (!contract.isAddKind())
284 return rewriter.notifyMatchFailure(arg&: contract,
285 msg: "not using ADD combining kind");
286
287 VectorType accType = dyn_cast<VectorType>(Val: contract.getAccType());
288 if (!accType || accType.getRank() != 2)
289 return rewriter.notifyMatchFailure(arg&: contract,
290 msg: "accumulator is not a 2D vector");
291
292 VectorType lhsType = contract.getLhsType();
293 VectorType rhsType = contract.getRhsType();
294 if (lhsType.getElementType() != rhsType.getElementType())
295 return rewriter.notifyMatchFailure(
296 arg&: contract, msg: "LHS and RHS element types do not match");
297
298 auto iteratorTypes = contract.getIteratorTypesArray();
299 auto indexingMaps = contract.getIndexingMapsArray();
300 assert(indexingMaps.size() == 3 && "expected 3 indexing maps");
301 bool isInVnniLayout = x86::isInVnniLayout(op: contract, indexingMaps);
302
303 auto par = vector::IteratorType::parallel;
304 auto red = vector::IteratorType::reduction;
305 auto m = rewriter.getAffineDimExpr(position: 0);
306 auto n = rewriter.getAffineDimExpr(position: 1);
307 auto k = rewriter.getAffineDimExpr(position: 2);
308 auto vnni = rewriter.getAffineDimExpr(position: 3);
309
310 if (!isInVnniLayout) {
311 if (!equal(LRange: indexingMaps[0].getResults(), RRange: ArrayRef{m, k}) ||
312 !equal(LRange: indexingMaps[1].getResults(), RRange: ArrayRef{k, n}) ||
313 !equal(LRange: indexingMaps[2].getResults(), RRange: ArrayRef{m, n}))
314 return rewriter.notifyMatchFailure(arg&: contract,
315 msg: "indexing maps are not canonical");
316
317 if (!equal(LRange&: iteratorTypes, RRange: ArrayRef{par, par, red}))
318 return rewriter.notifyMatchFailure(arg&: contract,
319 msg: "iterator types are not canonical");
320 } else {
321 if (!equal(LRange: indexingMaps[0].getResults(), RRange: ArrayRef{m, k, vnni}) ||
322 !equal(LRange: indexingMaps[1].getResults(), RRange: ArrayRef{k, n, vnni}) ||
323 !equal(LRange: indexingMaps[2].getResults(), RRange: ArrayRef{m, n}))
324 return rewriter.notifyMatchFailure(
325 arg&: contract, msg: "indexing maps are not canonical (VNNI)");
326
327 if (!equal(LRange&: iteratorTypes, RRange: ArrayRef{par, par, red, red}))
328 return rewriter.notifyMatchFailure(
329 arg&: contract, msg: "iterator types are not canonical (VNNI)");
330 }
331
332 candidate.isInVnniLayout = isInVnniLayout;
333 candidate.accType = accType;
334 candidate.lhsType = lhsType;
335 candidate.rhsType = rhsType;
336 candidate.contractK = lhsType.getShape()[1];
337
338 return success();
339}
340
341// Invoke the target-specific hook to compute a tiling and unrolling strategy
342// for the contraction, and check that it is consistent and compatible with the
343// current capabilities of this pattern. The result is recorded in the
344// `*regTileType`, `*nativeType`, and `nativeContractShape` fields of the
345// candidate struct.
346static LogicalResult
347matchTypesAndShape(MLUCandidate &candidate,
348 const MatchTypesAndShapeFn &matchTypesAndShapeForTarget,
349 PatternRewriter &rewriter) {
350 vector::ContractionOp contract = candidate.contract;
351
352 Type inpElemType = candidate.lhsType.getElementType();
353 Type accElemType = candidate.accType.getElementType();
354
355 // Contraction shape is {m, n, k} or {m, n, k, vnni}.
356 ArrayRef<int64_t> rhsShape = candidate.rhsType.getShape();
357 ArrayRef<int64_t> lhsShape = candidate.lhsType.getShape();
358 SmallVector<int64_t, 4> contractShape = {lhsShape[0], rhsShape[1],
359 lhsShape[1]};
360 if (candidate.isInVnniLayout)
361 contractShape.push_back(Elt: lhsShape[2]);
362
363 SmallVector<int64_t, 4> contractRegTileShape, contractNativeShape;
364 if (failed(Result: matchTypesAndShapeForTarget(
365 inpElemType, accElemType, candidate.isInVnniLayout, contractShape,
366 contractRegTileShape, contractNativeShape)) ||
367 contractRegTileShape.size() < contractShape.size() ||
368 contractNativeShape.size() < contractShape.size())
369 return rewriter.notifyMatchFailure(
370 arg&: contract, msg: "no tiling and unrolling strategy found");
371
372 auto maybeTileShapeRatio =
373 computeShapeRatio(shape: contractShape, subShape: contractRegTileShape);
374 auto maybeUnrollShapeRatio =
375 computeShapeRatio(shape: contractRegTileShape, subShape: contractNativeShape);
376
377 if (!maybeTileShapeRatio || !maybeUnrollShapeRatio)
378 return rewriter.notifyMatchFailure(
379 arg&: contract, msg: "incompatible or inconsistent tiling and unrolling strategy");
380
381 auto isOne = [](int64_t v) { return v == 1; };
382 if (all_of(Range&: *maybeTileShapeRatio, P: isOne) &&
383 all_of(Range&: *maybeUnrollShapeRatio, P: isOne))
384 return rewriter.notifyMatchFailure(
385 arg&: contract, msg: "contraction is already in native shape");
386
387 if (!all_of(Range: drop_begin(RangeOrContainer&: *maybeUnrollShapeRatio, N: 2), P: isOne))
388 return rewriter.notifyMatchFailure(
389 arg&: contract, msg: "cannot unroll in the reduction dimensions");
390
391 if (candidate.isInVnniLayout && (maybeTileShapeRatio->back() != 1))
392 return rewriter.notifyMatchFailure(arg&: contract,
393 msg: "cannot tile in the VNNI dimension");
394
395 int64_t regTileM = contractRegTileShape[0];
396 int64_t regTileN = contractRegTileShape[1];
397 int64_t regTileK = contractRegTileShape[2];
398
399 int64_t nativeM = contractNativeShape[0];
400 int64_t nativeN = contractNativeShape[1];
401 int64_t nativeK = contractNativeShape[2];
402
403 candidate.accRegTileType = VectorType::get(shape: {regTileM, regTileN}, elementType: accElemType);
404 candidate.accNativeType = VectorType::get(shape: {nativeM, nativeN}, elementType: accElemType);
405
406 auto getOperandType = [&](ArrayRef<int64_t> shape) {
407 if (candidate.isInVnniLayout) {
408 SmallVector<int64_t, 3> newShape(shape.begin(), shape.end());
409 newShape.push_back(Elt: contractNativeShape[3]);
410 return VectorType::get(shape: newShape, elementType: inpElemType);
411 }
412 return VectorType::get(shape, elementType: inpElemType);
413 };
414
415 candidate.lhsRegTileType = getOperandType({regTileM, regTileK});
416 candidate.rhsRegTileType = getOperandType({regTileK, regTileN});
417
418 candidate.lhsNativeType = getOperandType({nativeM, nativeK});
419 candidate.rhsNativeType = getOperandType({nativeK, nativeN});
420
421 candidate.contractNativeShape.append(in_start: contractNativeShape.begin(),
422 in_end: contractNativeShape.end());
423
424 return success();
425}
426
427// Check constraints on the accumulation loop. We're looking for an index-based
428// for-loop with a step of 1 or K, a single accumulator block argument. The body
429// shall only contain the transfer_reads for the operands, the contraction and
430// the yield operation. This restriction is in place because the pattern
431// rebuilds the accumulation loop from scratch with the known operations.
432//
433// For the operand reads, we require that they have a minor identity permutation
434// map, impose no bounds checks and don't carry a mask. In addition, they shall
435// use the induction variable as exactly one of their indices. This covers plain
436// 2D memrefs as well as block-based layouts.
437//
438// If all these conditions are met, the loop op, initial value of the
439// accumulator and the operand reads are recorded in the candidate struct.
440//
441// Example:
442// !accType = vector<64x128xf32>
443// !lhsType = vector<64x32xbf16>
444// !rhsType = vector<32x128xbf16>
445// ...
446// %res = scf.for %k = %k_start to %k_end step %c1 iter_args(%acc = %c)
447// -> (!accType) {
448// %a = vector.transfer_read %A[%m, %k, %c0, %c0], %c0_0
449// {in_bounds = [true, true]} : memref<?x?x64x32xbf16>, !lhsType
450// %b = vector.transfer_read %B[%n, %k, %c0, %c0], %c0_0
451// {in_bounds = [true, true]} : memref<?x?x32x128xbf16>, !rhsType
452// %d = vector.contract { ... } %a, %b, %acc
453// : !lhsType, !rhsType into !accType
454// scf.yield %d : !accType
455// }
456static LogicalResult matchAccumulationLoop(MLUCandidate &candidate,
457 PatternRewriter &rewriter) {
458 auto &contract = candidate.contract;
459
460 auto accLoop = dyn_cast_if_present<scf::ForOp>(Val: contract->getParentOp());
461 if (!accLoop || !accLoop.getInductionVar().getType().isIndex())
462 return rewriter.notifyMatchFailure(arg&: contract,
463 msg: "is not in an index-based for-loop");
464
465 if (auto step = getConstantIntValue(ofr: accLoop.getStep());
466 !step || (*step != 1 && *step != candidate.contractK))
467 return rewriter.notifyMatchFailure(arg&: contract,
468 msg: "accumulation loop step is not 1 or K");
469
470 BlockArgument accIterArg = dyn_cast<BlockArgument>(Val: contract.getAcc());
471 if (!accIterArg || accIterArg.getOwner() != accLoop.getBody())
472 return rewriter.notifyMatchFailure(arg&: contract,
473 msg: "accumulator is not a block argument");
474
475 if (accLoop.getNumRegionIterArgs() != 1 ||
476 accLoop.getBody()->getOperations().size() != 4)
477 return rewriter.notifyMatchFailure(
478 arg&: contract, msg: "accumulation loop has additional iter_args or operations");
479
480 if (!contract->getResult(idx: 0).hasOneUse())
481 return rewriter.notifyMatchFailure(arg&: contract,
482 msg: "result does not have exactly one use");
483
484 Operation *user = *contract->getResult(idx: 0).getUsers().begin();
485 if (!isa<scf::YieldOp>(Val: user))
486 return rewriter.notifyMatchFailure(arg&: contract,
487 msg: "accumulator is not loop-carried");
488
489 Value accInitVal = accLoop.getTiedLoopInit(bbArg: accIterArg)->get();
490 bool accIsZeroInit = isZeroVector(v: accInitVal);
491
492 auto lhsRead = contract.getLhs().getDefiningOp<vector::TransferReadOp>();
493 auto rhsRead = contract.getRhs().getDefiningOp<vector::TransferReadOp>();
494 if (!lhsRead || !rhsRead)
495 return rewriter.notifyMatchFailure(
496 arg&: contract, msg: "LHS/RHS are not vector.transfer_read ops");
497
498 auto checkOperandRead = [&](vector::TransferReadOp read, unsigned kVecDim) {
499 if (!isSimpleTransferOp(op: read))
500 return rewriter.notifyMatchFailure(
501 arg&: contract, msg: "operand read has non-identity permutation, mask, or "
502 "out-of-bounds check");
503
504 auto indices = read.getIndices();
505 if (candidate.isInVnniLayout && !isZeroInteger(v: indices.back()))
506 return rewriter.notifyMatchFailure(
507 arg&: contract, msg: "operand read VNNI dimension offset must be zero");
508
509 auto ivIt =
510 std::find(first: indices.begin(), last: indices.end(), val: accLoop.getInductionVar());
511 if (ivIt == indices.end())
512 return rewriter.notifyMatchFailure(
513 arg&: contract, msg: "operand read does not use loop index");
514 if (std::find(first: ivIt + 1, last: indices.end(), val: accLoop.getInductionVar()) !=
515 indices.end())
516 return rewriter.notifyMatchFailure(
517 arg&: contract, msg: "operand read uses loop index more than once");
518
519 // The following situation is a limitation in the implementation, so detect
520 // and bail out:
521 //
522 // If the loop index selects a block in a blocked layout, and tiling of the
523 // contraction dimension is required, we have to construct a new innermost
524 // tiling loop over the result vector's K dimension (called "L-loop" in the
525 // transformation later). Now if the operand read has a non-zero offset in
526 // that dimension, we would have to insert an addition into the new loop,
527 // which currently would prevent application of the nanokernel pattern.
528 //
529 // Sketch:
530 // non-zero offset in the vector's K dimension
531 // IV used in non-vector dimension, |
532 // selects a block |
533 // | |
534 // v v
535 // vector.transfer_read %A[%block_M, %IV, %c0, %offset_k] ...
536 // : memref<?x?x?x?xi8>, vector<64x64xi8>
537 unsigned firstVecDimPos = read.getLeadingShapedRank();
538 unsigned ivPos = std::distance(first: indices.begin(), last: ivIt);
539 if (ivPos < firstVecDimPos &&
540 candidate.contractK > candidate.contractNativeShape[2] &&
541 !isZeroInteger(v: indices[firstVecDimPos + kVecDim]))
542 return rewriter.notifyMatchFailure(arg&: contract,
543 msg: "operand read from blocked layout has "
544 "offset in vector's K dimension");
545
546 return success();
547 };
548
549 if (failed(Result: checkOperandRead(lhsRead, /*[m, k] -> kVecDim=*/1)) ||
550 failed(Result: checkOperandRead(rhsRead, /*[k, n] -> kVecDim=*/0)))
551 return failure();
552
553 candidate.accLoop = accLoop;
554 candidate.accInitVal = accInitVal;
555 candidate.accIsZeroInit = accIsZeroInit;
556 candidate.lhsRead = lhsRead;
557 candidate.rhsRead = rhsRead;
558
559 return success();
560}
561
562//----------------------------------------------------------------------------//
563// Transformation
564//----------------------------------------------------------------------------//
565
566// Ensure that the initial accumulator value can be sliced into register-tile
567// shaped vectors. Unless it is zero-initialized, we need it to be backed
568// by memory so that the slice can be loaded via a vector.transfer_read inside
569// the loop nest.
570//
571// If the initial value is produced by a simple vector.transfer_read, we can
572// simply derive a subview from its base and indices. Otherwise, we fall back to
573// allocating a new buffer on stack and store the initial value into it.
574static void makeAccInitializationBackedByMemory(MLUCandidate &candidate,
575 PatternRewriter &rewriter) {
576 if (candidate.accIsZeroInit)
577 return;
578
579 OpBuilder::InsertionGuard guard(rewriter);
580 rewriter.setInsertionPoint(candidate.accLoop);
581 auto loc = candidate.accLoop.getLoc();
582
583 if (auto accRead =
584 candidate.accInitVal.getDefiningOp<vector::TransferReadOp>();
585 accRead && isSimpleTransferOp(op: accRead) &&
586 noMemoryEffectsBetween(start: accRead, end: candidate.accLoop)) {
587 candidate.accMemIn =
588 makeRankReducingSubview(b&: rewriter, loc, base: accRead.getBase(),
589 indices: accRead.getIndices(), targetType: accRead.getVectorType());
590 return;
591 }
592
593 auto accBufferType = MemRefType::get(shape: candidate.accType.getShape(),
594 elementType: candidate.accType.getElementType());
595 candidate.accMemIn = memref::AllocaOp::create(builder&: rewriter, location: loc, memrefType: accBufferType);
596
597 Value c0 = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0);
598 SmallVector<Value, 2> zeroIndices(candidate.accType.getRank(), c0);
599 vector::TransferWriteOp::create(builder&: rewriter, location: loc, vector: candidate.accInitVal,
600 dest: candidate.accMemIn, indices: zeroIndices);
601}
602
603// Ensure that slices of the result of the accumulator loop can be stored, so
604// again we need it to be backed by memory.
605//
606// If the only user of the result is a simple vector.transfer_write, and its
607// base and indices are defined before the accumulator loop, we can derive a
608// subview. The transfer_write will be deleted after building the loop nest,
609// which at that point incorporates its effect.
610//
611// Otherwise, we fall back to buffering the result and rematerializing it after
612// the loop. If we already had a stack allocation for the initial value, we
613// reuse it.
614static void makeAccResultBackedByMemory(MLUCandidate &candidate,
615 PatternRewriter &rewriter) {
616 OpBuilder::InsertionGuard guard(rewriter);
617 rewriter.setInsertionPoint(candidate.accLoop);
618 auto loc = candidate.accLoop.getLoc();
619
620 auto accRes = candidate.accLoop.getResult(i: 0);
621 vector::TransferWriteOp accWrite;
622 if (accRes.hasOneUse())
623 accWrite = dyn_cast<vector::TransferWriteOp>(Val: *accRes.getUsers().begin());
624
625 Block *accLoopBlock = candidate.accLoop->getBlock();
626 if (accWrite && isSimpleTransferOp(op: accWrite) &&
627 noMemoryEffectsBetween(start: candidate.accLoop, end: accWrite)) {
628
629 Value accWriteBase = accWrite.getBase();
630 ValueRange accWriteIndices = accWrite.getIndices();
631
632 auto isSafeToUseView = [&]() {
633 // A single register tile reads all of its input before writing.
634 if (candidate.accIsZeroInit ||
635 candidate.accType == candidate.accRegTileType)
636 return true;
637 auto accMemInView = candidate.accMemIn.getDefiningOp<memref::SubViewOp>();
638 if (!accMemInView)
639 return true;
640
641 return accMemInView.getSource() == accWriteBase &&
642 isEqualConstantIntOrValueArray(ofrs1: accMemInView.getMixedOffsets(),
643 ofrs2: getAsOpFoldResult(values: accWriteIndices));
644 };
645
646 auto isDefinedBeforeAccLoop = [&](Value v) {
647 Operation *defOp = v.getDefiningOp();
648 // No need for full dominance check, as we already know that accLoop and
649 // accWrite are in the same block.
650 return !defOp || defOp->getBlock() != accLoopBlock ||
651 defOp->isBeforeInBlock(other: candidate.accLoop);
652 };
653
654 if (isSafeToUseView() && isDefinedBeforeAccLoop(accWriteBase) &&
655 all_of(Range&: accWriteIndices, P: isDefinedBeforeAccLoop)) {
656 candidate.accMemOut =
657 makeRankReducingSubview(b&: rewriter, loc, base: accWriteBase, indices: accWriteIndices,
658 targetType: accWrite.getVectorType());
659 candidate.opsToDelete.push_back(Elt: accWrite);
660 candidate.opsToDelete.push_back(Elt: candidate.accLoop);
661 return;
662 }
663 }
664
665 if (!candidate.accIsZeroInit &&
666 isa<memref::AllocaOp>(Val: candidate.accMemIn.getDefiningOp())) {
667 candidate.accMemOut = candidate.accMemIn;
668 } else {
669 auto accBufferType = MemRefType::get(shape: candidate.accType.getShape(),
670 elementType: candidate.accType.getElementType());
671 candidate.accMemOut =
672 memref::AllocaOp::create(builder&: rewriter, location: loc, memrefType: accBufferType);
673 }
674
675 rewriter.setInsertionPointAfter(candidate.accLoop);
676 Value c0 = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0);
677 SmallVector<Value, 2> zeroIndices(candidate.accType.getRank(), c0);
678 auto accRemat = vector::TransferReadOp::create(
679 builder&: rewriter, location: loc, vectorType: candidate.accType, source: candidate.accMemOut, indices: zeroIndices,
680 /*padding=*/std::nullopt);
681
682 rewriter.replaceAllUsesWith(from: candidate.accLoop.getResult(i: 0), to: accRemat);
683 candidate.opsToDelete.push_back(Elt: candidate.accLoop);
684}
685
686// Create the loop nest for iterating over the M and N dimensions of the
687// accumulator. Construction continues in buildMNLoopBody.
688static void buildLoopNestForCandidate(MLUCandidate &candidate,
689 PatternRewriter &rewriter) {
690 OpBuilder::InsertionGuard guard(rewriter);
691 rewriter.setInsertionPoint(candidate.accLoop);
692 auto loc = candidate.accLoop.getLoc();
693
694 ArrayRef<int64_t> accShape = candidate.accType.getShape();
695 ArrayRef<int64_t> accRegTileShape = candidate.accRegTileType.getShape();
696
697 auto makeIndexConst = [&](int64_t v) {
698 return arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: v);
699 };
700
701 Value c0 = makeIndexConst(0);
702 Value ubM = makeIndexConst(accShape[0]);
703 Value stepM = makeIndexConst(accRegTileShape[0]);
704 Value ubN = makeIndexConst(accShape[1]);
705 Value stepN = makeIndexConst(accRegTileShape[1]);
706
707 scf::ForOp::create(
708 builder&: rewriter, location: loc, lowerBound: c0, upperBound: ubM, step: stepM, initArgs: {},
709 odsArg4: [&](OpBuilder &b, Location loc, Value ivM, ValueRange iterArgs) {
710 scf::ForOp::create(
711 builder&: b, location: loc, lowerBound: c0, upperBound: ubN, step: stepN, initArgs: {},
712 odsArg4: [&](OpBuilder &b, Location loc, Value ivN, ValueRange iterArgs) {
713 buildMNLoopBody(candidate, b, loc, ivM, ivN);
714 scf::YieldOp::create(builder&: b, location: loc);
715 });
716 scf::YieldOp::create(builder&: b, location: loc);
717 });
718}
719
720// Create the body for M-N-loop nest according to the following scheme:
721//
722// 1. Load a accRegTileType-shaped slice of the accumulator from memory (or make
723// a zero constant).
724// 2. Split the initial value into accNativeType-shaped slices.
725// 3. Create the K-loop with the initial value slices as loop-carried arguments,
726// i.e. the iter_args have accNativeType. Tiling along the K-dimension
727// depends on the step:
728// K: Use the same bounds but smaller steps/more iterations.
729// 1: Nest an additional L-loop to traverse the block in smaller steps.
730// 4. -> buildKLLoopBody
731// 5. Splice the final value slices back into an accRegTileType-shaped value and
732// write it back to memory.
733//
734// The accRegTileType-shaped operations are annotated with an attribute in order
735// to unroll them with the vector-dialect's unroll patterns.
736static void buildMNLoopBody(MLUCandidate &candidate, OpBuilder &b, Location loc,
737 Value ivM, Value ivN) {
738 ArrayRef<int64_t> accRegTileShape = candidate.accRegTileType.getShape();
739
740 Value c0 = arith::ConstantIndexOp::create(builder&: b, location: loc, value: 0);
741
742 SmallVector<OpFoldResult, 2> accViewOffsets = {ivM, ivN};
743 SmallVector<OpFoldResult, 2> accViewSizes = {
744 b.getI64IntegerAttr(value: accRegTileShape[0]),
745 b.getI64IntegerAttr(value: accRegTileShape[1])};
746 SmallVector<OpFoldResult, 2> accViewStrides = {b.getI64IntegerAttr(value: 1),
747 b.getI64IntegerAttr(value: 1)};
748
749 Operation *accInit;
750 if (candidate.accIsZeroInit) {
751 accInit = arith::ConstantOp::create(
752 builder&: b, location: loc, value: b.getZeroAttr(type: candidate.accRegTileType));
753 } else {
754 Value accViewIn =
755 memref::SubViewOp::create(builder&: b, location: loc, source: candidate.accMemIn, offsets: accViewOffsets,
756 sizes: accViewSizes, strides: accViewStrides);
757 auto accInitRead = vector::TransferReadOp::create(
758 builder&: b, location: loc, vectorType: candidate.accRegTileType, source: accViewIn, indices: ValueRange{c0, c0},
759 /*padding=*/std::nullopt);
760 setNativeShapeAttr(op: accInitRead, nativeType: candidate.accNativeType);
761 accInit = accInitRead;
762 }
763
764 SmallVector<Value> accInitSliced =
765 slice(b, loc, value: accInit->getResult(idx: 0), nativeType: candidate.accNativeType);
766
767 // Iteration space for accumulation loop (nest).
768 Value lbK = candidate.accLoop.getLowerBound();
769 Value ubK = candidate.accLoop.getUpperBound();
770 Value stepK = candidate.accLoop.getStep();
771 Value lbL;
772 Value ubL;
773 Value stepL;
774
775 // If we need to tile the K dimension, the simplest way is to adjust the
776 // step to the native K extent. However, if the original accumulation loop
777 // uses unit steps, we have to insert an inner loop to handle the tiling
778 // explicitly.
779 //
780 // Note: Using _native_ shape here as we never unroll along the reduction
781 // dimension, so the K extents of the register-tile and native shapes match.
782 int64_t contractNativeK = candidate.contractNativeShape[2];
783 bool needToTileK = candidate.contractK > contractNativeK;
784 bool needLLoop = false;
785 if (needToTileK) {
786 needLLoop = *getConstantIntValue(ofr: stepK) % contractNativeK != 0;
787 Value cContractNativeK =
788 arith::ConstantIndexOp::create(builder&: b, location: loc, value: contractNativeK);
789 if (needLLoop) {
790 lbL = c0;
791 ubL = arith::ConstantIndexOp::create(builder&: b, location: loc, value: candidate.contractK);
792 stepL = cContractNativeK;
793 } else {
794 stepK = cContractNativeK;
795 }
796 }
797
798 candidate.slicedAccLoop = scf::ForOp::create(
799 builder&: b, location: loc, lowerBound: lbK, upperBound: ubK, step: stepK, initArgs: accInitSliced,
800 odsArg4: [&](OpBuilder &b, Location loc, Value ivK, ValueRange iterArgsK) {
801 if (!needLLoop) {
802 SmallVector<Value> newIterArgs = buildKLLoopBody(
803 candidate, b, loc, ivM, ivN, ivK, /*ivL=*/Value{}, iterArgs: iterArgsK);
804 scf::YieldOp::create(builder&: b, location: loc, results: newIterArgs);
805 return;
806 }
807
808 candidate.slicedInnerAccLoop = scf::ForOp::create(
809 builder&: b, location: loc, lowerBound: lbL, upperBound: ubL, step: stepL, initArgs: iterArgsK,
810 odsArg4: [&](OpBuilder &b, Location loc, Value ivL, ValueRange iterArgsL) {
811 SmallVector<Value> newIterArgs = buildKLLoopBody(
812 candidate, b, loc, ivM, ivN, ivK, ivL, iterArgs: iterArgsL);
813 scf::YieldOp::create(builder&: b, location: loc, results: newIterArgs);
814 });
815 scf::YieldOp::create(builder&: b, location: loc, results: candidate.slicedInnerAccLoop.getResults());
816 });
817
818 Value accSpliced = splice(b, loc, values: candidate.slicedAccLoop.getResults(),
819 regTileType: candidate.accRegTileType);
820 Value accViewOut =
821 memref::SubViewOp::create(builder&: b, location: loc, source: candidate.accMemOut, offsets: accViewOffsets,
822 sizes: accViewSizes, strides: accViewStrides);
823 auto accWrite = vector::TransferWriteOp::create(
824 builder&: b, location: loc, vector: accSpliced, dest: accViewOut, indices: ValueRange{c0, c0});
825
826 setNativeShapeAttr(op: accWrite, nativeType: candidate.accNativeType);
827}
828
829// Rebuild the accumulation loop with [lhs|rhs]RegTileType-shaped operations,
830// replacing the induction variable and taking the offsets from the
831// M-N-(L)-loop nest into account. The accumulator iter_args are spliced into a
832// accRegTileType-shaped value, and the contraction result is split into
833// accNativeType-shaped yield operands. Again, the operations are annotated with
834// an attribute for unrolling, after which the splice/split logic will fold away
835// completely.
836static SmallVector<Value> buildKLLoopBody(MLUCandidate &candidate, OpBuilder &b,
837 Location loc, Value ivM, Value ivN,
838 Value ivK, Value ivL,
839 ValueRange iterArgs) {
840 Value accSpliced = splice(b, loc, values: iterArgs, regTileType: candidate.accRegTileType);
841
842 SmallVector<Value, 4> lhsIndices = candidate.lhsRead.getIndices();
843 SmallVector<Value, 4> rhsIndices = candidate.rhsRead.getIndices();
844
845 Value accLoopIV = candidate.accLoop.getInductionVar();
846 replace(Range&: lhsIndices, OldValue: accLoopIV, NewValue: ivK);
847 replace(Range&: rhsIndices, OldValue: accLoopIV, NewValue: ivK);
848
849 unsigned mPos = lhsIndices.size() - 2 - candidate.isInVnniLayout;
850 unsigned nPos = rhsIndices.size() - 1 - candidate.isInVnniLayout;
851 lhsIndices[mPos] = arith::AddIOp::create(builder&: b, location: loc, lhs: lhsIndices[mPos], rhs: ivM);
852 rhsIndices[nPos] = arith::AddIOp::create(builder&: b, location: loc, lhs: rhsIndices[nPos], rhs: ivN);
853
854 if (ivL) {
855 unsigned lPosL = lhsIndices.size() - 1 - candidate.isInVnniLayout;
856 unsigned lPosR = rhsIndices.size() - 2 - candidate.isInVnniLayout;
857 // Checked in matchAccumulationLoop.
858 assert(isZeroInteger(lhsIndices[lPosL]) &&
859 isZeroInteger(rhsIndices[lPosR]) &&
860 "Expected zero offsets for L dimension");
861 lhsIndices[lPosL] = ivL;
862 rhsIndices[lPosR] = ivL;
863 }
864
865 Value lhsView = makeRankReducingSubview(b, loc, base: candidate.lhsRead.getBase(),
866 indices: lhsIndices, targetType: candidate.lhsRegTileType);
867 Value rhsView = makeRankReducingSubview(b, loc, base: candidate.rhsRead.getBase(),
868 indices: rhsIndices, targetType: candidate.rhsRegTileType);
869
870 SmallVector<Value, 3> zeroIndices(2 + candidate.isInVnniLayout,
871 arith::ConstantIndexOp::create(builder&: b, location: loc, value: 0));
872 auto lhsRead = vector::TransferReadOp::create(
873 builder&: b, location: candidate.lhsRead.getLoc(), vectorType: candidate.lhsRegTileType, source: lhsView,
874 indices: zeroIndices, /*padding=*/std::nullopt);
875 auto rhsRead = vector::TransferReadOp::create(
876 builder&: b, location: candidate.rhsRead.getLoc(), vectorType: candidate.rhsRegTileType, source: rhsView,
877 indices: zeroIndices, /*padding=*/std::nullopt);
878 auto contract = vector::ContractionOp::create(
879 builder&: b, location: candidate.contract.getLoc(), lhs: lhsRead, rhs: rhsRead, acc: accSpliced,
880 indexingMaps: candidate.contract.getIndexingMaps(),
881 iteratorTypes: candidate.contract.getIteratorTypes());
882
883 setNativeShapeAttr(op: lhsRead, nativeType: candidate.lhsNativeType);
884 setNativeShapeAttr(op: rhsRead, nativeType: candidate.rhsNativeType);
885 contract->setAttr(name: nativeShapeAttrName,
886 value: b.getDenseI64ArrayAttr(values: candidate.contractNativeShape));
887
888 SmallVector<Value> accSliced =
889 slice(b, loc, value: contract, nativeType: candidate.accNativeType);
890 return accSliced;
891}
892
893//----------------------------------------------------------------------------//
894// Pattern implementation //
895//----------------------------------------------------------------------------//
896
897namespace {
898// Prepares a contraction inside an accumulation loop for the nanokernel
899// lowerings.
900//
901// The pattern determines a register-tile shape for the contraction that can be
902// fully unrolled to a target-specific native shape without exceeding the
903// target's vector registers or AMX tile registers. It then introduces a loop
904// nest to iterate over such register tiles, and applies the vector dialect's
905// unroll patterns to produce native-shaped operations that the nanokernel
906// patterns can match.
907//
908// Currently, the match is deliberately strict (see the helpers above):
909// The contraction must be a canonical matrix multiplication, have
910// target-compatible types and shapes that can be tiled and unrolled cleanly,
911// and be embedded in an accumulation loop containing only the operand reads and
912// itself. This lets the rewrite regenerate the loop from scratch instead of
913// transforming it in place.
914struct VectorContractMultiLevelUnroll
915 : public OpRewritePattern<vector::ContractionOp> {
916 VectorContractMultiLevelUnroll(
917 MLIRContext *context,
918 const MatchTypesAndShapeFn &matchTypesAndShapeForTarget,
919 PatternBenefit benefit = 1)
920 : OpRewritePattern<vector::ContractionOp>(context, benefit),
921 matchTypesAndShapeForTarget(matchTypesAndShapeForTarget) {}
922
923 LogicalResult matchAndRewrite(vector::ContractionOp contract,
924 PatternRewriter &rewriter) const override {
925 // Bail out early if this op is the result of a previous application of the
926 // pattern.
927 if (contract->hasAttr(name: nativeShapeAttrName))
928 return failure();
929
930 MLUCandidate candidate;
931 candidate.contract = contract;
932 if (failed(Result: matchCanonicalMatmul(candidate, rewriter)) ||
933 failed(Result: matchTypesAndShape(candidate, matchTypesAndShapeForTarget,
934 rewriter)) ||
935 failed(Result: matchAccumulationLoop(candidate, rewriter)))
936 return failure();
937
938 makeAccInitializationBackedByMemory(candidate, rewriter);
939 makeAccResultBackedByMemory(candidate, rewriter);
940 buildLoopNestForCandidate(candidate, rewriter);
941 if (candidate.slicedInnerAccLoop)
942 moveLoopInvariantCode(loopLike: candidate.slicedInnerAccLoop);
943 moveLoopInvariantCode(loopLike: candidate.slicedAccLoop);
944 for (auto *op : candidate.opsToDelete)
945 rewriter.eraseOp(op);
946
947 return success();
948 }
949
950private:
951 MatchTypesAndShapeFn matchTypesAndShapeForTarget;
952};
953} // namespace
954
955//----------------------------------------------------------------------------//
956// Target-specific matchers //
957//----------------------------------------------------------------------------//
958
959// Tiling strategy for AMX tile dot-product: The preferred native layout is
960// to keep the accumulator on a 2x2 grid of tile registers, though 1x2 and
961// VNNI-prepacked 1x1 and 2x1 configurations are also supported (NB: online
962// packing requires two neighboring tiles in the N-dimension).
963static LogicalResult
964matchTypesAndShapeForAMX(Type inputElemType, Type accumulatorElemType,
965 bool isInVnniLayout, ArrayRef<int64_t> contractShape,
966 SmallVectorImpl<int64_t> &contractRegTileShape,
967 SmallVectorImpl<int64_t> &contractNativeShape) {
968
969 if (!((inputElemType.isBF16() && accumulatorElemType.isF32()) ||
970 (inputElemType.isInteger(width: 8) && accumulatorElemType.isInteger(width: 32))))
971 return failure();
972
973 int64_t origM = contractShape[0];
974 int64_t origN = contractShape[1];
975
976 int64_t regTileM, regTileN, regTileK;
977 int64_t nativeM, nativeN, nativeK, vnni;
978
979 vnni = 32 / inputElemType.getIntOrFloatBitWidth();
980 nativeM = nativeN = 16;
981 nativeK = isInVnniLayout ? 16 : 16 * vnni;
982
983 // Prefer 2x2 tiling if shapes allow. Online packing requires a contract pair
984 // in the N-dimension.
985 regTileM = origM % (2 * nativeM) == 0 ? 2 * nativeM : nativeM;
986 regTileN =
987 origN % (2 * nativeN) == 0 || !isInVnniLayout ? 2 * nativeN : nativeN;
988 regTileK = nativeK;
989
990 contractRegTileShape.append(IL: {regTileM, regTileN, regTileK});
991 contractNativeShape.append(IL: {nativeM, nativeN, nativeK});
992 if (isInVnniLayout) {
993 contractRegTileShape.push_back(Elt: vnni);
994 contractNativeShape.push_back(Elt: vnni);
995 }
996
997 return success();
998}
999
1000//----------------------------------------------------------------------------//
1001// Public interface //
1002//----------------------------------------------------------------------------//
1003
1004void x86::populateVectorContractMultiLevelUnrollForAMXPatterns(
1005 RewritePatternSet &patterns) {
1006 patterns.add<VectorContractMultiLevelUnroll>(arg: patterns.getContext(),
1007 args&: matchTypesAndShapeForAMX);
1008 vector::UnrollVectorOptions nativeUnrollOptions;
1009 nativeUnrollOptions.setNativeShapeFn(getFromNativeShapeAttr);
1010 vector::populateVectorUnrollPatterns(patterns, options: nativeUnrollOptions);
1011}
1012