1//===- DropUnitDims.cpp - Pass to drop use of unit-extent for broadcasting ===//
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 patterns/pass to remove usage of unit-extent dimensions
10// to specify broadcasting in favor of more canonical representation of the
11// computation
12//
13//===----------------------------------------------------------------------===//
14
15#include "mlir/Dialect/Linalg/Passes.h"
16
17#include "mlir/Dialect/Affine/IR/AffineOps.h"
18#include "mlir/Dialect/Arith/IR/Arith.h"
19#include "mlir/Dialect/Arith/Utils/Utils.h"
20#include "mlir/Dialect/Linalg/IR/Linalg.h"
21#include "mlir/Dialect/Linalg/Transforms/Transforms.h"
22#include "mlir/Dialect/Linalg/Utils/Utils.h"
23#include "mlir/Dialect/MemRef/Transforms/Transforms.h"
24#include "mlir/Dialect/Tensor/IR/Tensor.h"
25#include "mlir/Dialect/Tensor/Transforms/Transforms.h"
26#include "mlir/Dialect/Utils/ReshapeOpsUtils.h"
27#include "mlir/IR/AffineExpr.h"
28#include "mlir/IR/AffineMap.h"
29#include "mlir/IR/BuiltinTypes.h"
30#include "mlir/Transforms/FoldUtils.h"
31#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
32#include "mlir/Transforms/WalkPatternRewriteDriver.h"
33#include "llvm/ADT/SmallBitVector.h"
34#include "llvm/Support/Debug.h"
35
36namespace mlir {
37#define GEN_PASS_DEF_LINALGFOLDUNITEXTENTDIMSPASS
38#include "mlir/Dialect/Linalg/Passes.h.inc"
39} // namespace mlir
40
41#define DEBUG_TYPE "linalg-drop-unit-dims"
42
43using namespace mlir;
44using namespace mlir::linalg;
45
46namespace {
47/// Pattern to move init operands to ins when all the loops are parallel and
48/// blockArgument corresponding to init is used in the region. This is a fix-up
49/// when unit reduction dimensions are all folded away. In this context, it
50/// becomes a elementwise generic op. E.g., it converts
51///
52/// %0 = tensor.empty() : tensor<1x1xf32>
53/// %1 = linalg.fill
54/// ins(%cst : f32)
55/// outs(%0 : tensor<1x1xf32>) -> tensor<1x1xf32>
56/// %2 = linalg.generic {indexing_maps = [affine_map<(d0) -> (0, d0, 0, 0)>,
57/// affine_map<(d0) -> (0, d0)>],
58/// iterator_types = ["parallel"]}
59/// ins(%arg0 : tensor<1x?x1x1xf32>)
60/// outs(%1 : tensor<1x1xf32>) {
61/// ^bb0(%in: f32, %out: f32):
62/// %3 = arith.addf %in, %out : f32
63/// linalg.yield %3 : f32
64/// } -> tensor<1x1xf32>
65///
66/// into
67///
68/// %0 = tensor.empty() : tensor<1x1xf32>
69/// %1 = linalg.fill
70/// ins(%cst : f32)
71/// outs(%0 : tensor<1x1xf32>) -> tensor<1x1xf32>
72/// %2 = tensor.empty() : tensor<1x1xf32>
73/// %3 = linalg.generic {indexing_maps = [affine_map<(d0) -> (0, d0, 0, 0)>,
74/// affine_map<(d0) -> (0, d0)>,
75/// affine_map<(d0) -> (0, d0)>],
76/// iterator_types = ["parallel"]}
77/// ins(%arg0, %1 : tensor<1x?x1x1xf32>, tensor<1x1xf32>)
78/// outs(%2 : tensor<1x1xf32>) {
79/// ^bb0(%in: f32, %in_0: f32, %out: f32):
80/// %4 = arith.addf %in, %in_0 : f32
81/// linalg.yield %4 : f32
82/// } -> tensor<1x1xf32>
83struct MoveInitOperandsToInput : public OpRewritePattern<GenericOp> {
84 using OpRewritePattern<GenericOp>::OpRewritePattern;
85 LogicalResult matchAndRewrite(GenericOp genericOp,
86 PatternRewriter &rewriter) const override {
87 if (!genericOp.hasPureTensorSemantics())
88 return failure();
89 if (genericOp.getNumParallelLoops() != genericOp.getNumLoops())
90 return failure();
91
92 auto outputOperands = genericOp.getDpsInitsMutable();
93 SetVector<OpOperand *> candidates;
94 for (OpOperand &op : outputOperands) {
95 if (genericOp.getMatchingBlockArgument(opOperand: &op).use_empty())
96 continue;
97 candidates.insert(X: &op);
98 }
99
100 if (candidates.empty())
101 return failure();
102
103 // Compute the modified indexing maps.
104 int64_t origNumInput = genericOp.getNumDpsInputs();
105 SmallVector<Value> newInputOperands = genericOp.getDpsInputs();
106 SmallVector<AffineMap> indexingMaps = genericOp.getIndexingMapsArray();
107 SmallVector<AffineMap> newIndexingMaps;
108 newIndexingMaps.append(in_start: indexingMaps.begin(),
109 in_end: std::next(x: indexingMaps.begin(), n: origNumInput));
110 for (OpOperand *op : candidates) {
111 newInputOperands.push_back(Elt: op->get());
112 newIndexingMaps.push_back(Elt: genericOp.getMatchingIndexingMap(opOperand: op));
113 }
114 newIndexingMaps.append(in_start: std::next(x: indexingMaps.begin(), n: origNumInput),
115 in_end: indexingMaps.end());
116
117 Location loc = genericOp.getLoc();
118 SmallVector<Value> newOutputOperands =
119 llvm::to_vector(Range: genericOp.getDpsInits());
120 for (OpOperand *op : candidates) {
121 OpBuilder::InsertionGuard guard(rewriter);
122 rewriter.setInsertionPointAfterValue(op->get());
123 auto elemType = cast<ShapedType>(Val: op->get().getType()).getElementType();
124 auto empty = tensor::EmptyOp::create(
125 builder&: rewriter, location: loc, sizes: tensor::getMixedSizes(builder&: rewriter, loc, value: op->get()),
126 elementType: elemType);
127
128 unsigned start = genericOp.getDpsInits().getBeginOperandIndex();
129 newOutputOperands[op->getOperandNumber() - start] = empty.getResult();
130 }
131
132 auto newOp = GenericOp::create(
133 builder&: rewriter, location: loc, resultTensorTypes: genericOp.getResultTypes(), inputs: newInputOperands,
134 outputs: newOutputOperands, indexingMaps: newIndexingMaps, iteratorTypes: genericOp.getIteratorTypesArray(),
135 /*bodyBuild=*/odsArg5: nullptr, attributes: linalg::getPrunedAttributeList(op: genericOp));
136
137 OpBuilder::InsertionGuard guard(rewriter);
138 Region &region = newOp.getRegion();
139 Block *block = rewriter.createBlock(parent: &region);
140 IRMapping mapper;
141 for (auto bbarg : genericOp.getRegionInputArgs())
142 mapper.map(from: bbarg, to: block->addArgument(type: bbarg.getType(), loc));
143
144 for (OpOperand *op : candidates) {
145 BlockArgument bbarg = genericOp.getMatchingBlockArgument(opOperand: op);
146 mapper.map(from: bbarg, to: block->addArgument(type: bbarg.getType(), loc));
147 }
148
149 for (OpOperand &op : outputOperands) {
150 BlockArgument bbarg = genericOp.getMatchingBlockArgument(opOperand: &op);
151 if (candidates.count(key: &op))
152 block->addArgument(type: bbarg.getType(), loc);
153 else
154 mapper.map(from: bbarg, to: block->addArgument(type: bbarg.getType(), loc));
155 }
156
157 for (auto &op : genericOp.getBody()->getOperations()) {
158 rewriter.clone(op, mapper);
159 }
160 rewriter.replaceOp(op: genericOp, newValues: newOp.getResults());
161
162 return success();
163 }
164};
165} // namespace
166
167//===---------------------------------------------------------------------===//
168// Drop loops that are unit-extents within Linalg operations.
169//===---------------------------------------------------------------------===//
170
171/// Implements a pass that canonicalizes the uses of unit-extent dimensions for
172/// broadcasting. For example,
173///
174/// ```mlir
175/// #accesses = [
176/// affine_map<(d0, d1) -> (0, d1)>,
177/// affine_map<(d0, d1) -> (d0, 0)>,
178/// affine_map<(d0, d1) -> (d0, d1)>
179/// ]
180///
181/// #trait = {
182/// indexing_maps = #accesses,
183/// iterator_types = ["parallel", "parallel"],
184/// library_call = "some_external_fn"
185/// }
186///
187/// func @broadcast_test(%arg0 : tensor<5xf32>, %arg1 : tensor<5xf32>) ->
188/// tensor<5x5xf32>
189/// {
190/// %0 = linalg.tensor_reshape %arg0 [affine_map<(d0, d1) -> (d0, d1)>] :
191/// tensor<5xf32> into tensor<1x5xf32>
192/// %1 = linalg.tensor_reshape %arg1 [affine_map<(d0, d1) -> (d0, d1)>] :
193/// tensor<5xf32> into tensor<5x1xf32>
194/// %2 = linalg.generic #trait %0, %1 {
195/// ^bb0(%arg2: f32, %arg3: f32):
196/// %3 = arith.addf %arg2, %arg3 : f32
197/// linalg.yield %3 : f32
198/// } : tensor<1x5xf32>, tensor<5x1xf32> -> tensor<5x5xf32>
199/// return %2 : tensor<5x5xf32>
200/// }
201///
202/// would canonicalize to
203///
204/// ```mlir
205/// #accesses = [
206/// affine_map<(d0, d1) -> (d1)>,
207/// affine_map<(d0, d1) -> (d0)>,
208/// affine_map<(d0, d1) -> (d0, d1)>
209/// ]
210///
211/// #trait = {
212/// indexing_maps = #accesses,
213/// iterator_types = ["parallel", "parallel"],
214/// library_call = "some_external_fn"
215/// }
216///
217/// func @broadcast_test(%arg0 : tensor<5xf32>, %arg1 : tensor<5xf32>) ->
218/// tensor<5x5xf32>
219/// {
220/// %0 = linalg.generic #trait %arg0, %arg1 {
221/// ^bb0(%arg2: f32, %arg3: f32):
222/// %3 = arith.addf %arg2, %arg3 : f32
223/// linalg.yield %3 : f32
224/// } : tensor<5xf32>, tensor<5xf32> -> tensor<5x5xf32>
225/// return %0 : tensor<5x5xf32>
226/// }
227
228/// Update the index accesses of linalg operations having index semantics.
229static void
230replaceUnitDimIndexOps(GenericOp genericOp,
231 const llvm::SmallDenseSet<unsigned> &unitDims,
232 RewriterBase &rewriter) {
233 for (IndexOp indexOp :
234 llvm::make_early_inc_range(Range: genericOp.getBody()->getOps<IndexOp>())) {
235 OpBuilder::InsertionGuard guard(rewriter);
236 rewriter.setInsertionPoint(indexOp);
237 if (unitDims.count(V: indexOp.getDim()) != 0) {
238 rewriter.replaceOpWithNewOp<arith::ConstantIndexOp>(op: indexOp, args: 0);
239 } else {
240 // Update the dimension of the index operation if needed.
241 unsigned droppedDims = llvm::count_if(
242 Range: unitDims, P: [&](unsigned dim) { return dim < indexOp.getDim(); });
243 if (droppedDims != 0)
244 rewriter.replaceOpWithNewOp<IndexOp>(op: indexOp,
245 args: indexOp.getDim() - droppedDims);
246 }
247 }
248}
249
250FailureOr<Value>
251ControlDropUnitDims::expandValue(RewriterBase &rewriter, Location loc,
252 Value result, Value origDest,
253 ArrayRef<ReassociationIndices> reassociation,
254 const ControlDropUnitDims &control) {
255 // There are no results for memref outputs.
256 auto origResultType = cast<RankedTensorType>(Val: origDest.getType());
257 if (origResultType.getEncoding() != nullptr) {
258 // Do not expand tensors with encoding.
259 return failure();
260 }
261 if (control.rankReductionStrategy ==
262 ControlDropUnitDims::RankReductionStrategy::ExtractInsertSlice) {
263 unsigned rank = origResultType.getRank();
264 SmallVector<OpFoldResult> offsets(rank, rewriter.getIndexAttr(value: 0));
265 SmallVector<OpFoldResult> sizes =
266 tensor::getMixedSizes(builder&: rewriter, loc, value: origDest);
267 SmallVector<OpFoldResult> strides(rank, rewriter.getIndexAttr(value: 1));
268 return rewriter.createOrFold<tensor::InsertSliceOp>(
269 location: loc, args&: result, args&: origDest, args&: offsets, args&: sizes, args&: strides);
270 }
271
272 assert(control.rankReductionStrategy ==
273 ControlDropUnitDims::RankReductionStrategy::ReassociativeReshape &&
274 "unknown rank reduction strategy");
275 return tensor::ExpandShapeOp::create(builder&: rewriter, location: loc, resultType: origResultType, src: result,
276 reassociation)
277 .getResult();
278}
279
280FailureOr<Value>
281ControlDropUnitDims::collapseValue(RewriterBase &rewriter, Location loc,
282 Value operand, ArrayRef<int64_t> targetShape,
283 ArrayRef<ReassociationIndices> reassociation,
284 const ControlDropUnitDims &control) {
285 if (auto memrefType = dyn_cast<MemRefType>(Val: operand.getType())) {
286 if (!memrefType.getLayout().isIdentity()) {
287 // Do not collapse memrefs with a non-identity layout.
288 return failure();
289 }
290 if (control.rankReductionStrategy ==
291 ControlDropUnitDims::RankReductionStrategy::ExtractInsertSlice) {
292 FailureOr<Value> rankReducingExtract =
293 memref::SubViewOp::rankReduceIfNeeded(b&: rewriter, loc, value: operand,
294 desiredShape: targetShape);
295 assert(succeeded(rankReducingExtract) && "not a unit-extent collapse");
296 return *rankReducingExtract;
297 }
298
299 assert(
300 control.rankReductionStrategy ==
301 ControlDropUnitDims::RankReductionStrategy::ReassociativeReshape &&
302 "unknown rank reduction strategy");
303 MemRefLayoutAttrInterface layout;
304 auto targetType = MemRefType::get(shape: targetShape, elementType: memrefType.getElementType(),
305 layout, memorySpace: memrefType.getMemorySpace());
306 return memref::CollapseShapeOp::create(builder&: rewriter, location: loc, resultType: targetType, src: operand,
307 reassociation)
308 .getResult();
309 }
310 if (auto tensorType = dyn_cast<RankedTensorType>(Val: operand.getType())) {
311 if (tensorType.getEncoding() != nullptr) {
312 // Do not collapse tensors with an encoding.
313 return failure();
314 }
315 if (control.rankReductionStrategy ==
316 ControlDropUnitDims::RankReductionStrategy::ExtractInsertSlice) {
317 FailureOr<Value> rankReducingExtract =
318 tensor::ExtractSliceOp::rankReduceIfNeeded(b&: rewriter, loc, value: operand,
319 desiredShape: targetShape);
320 assert(succeeded(rankReducingExtract) && "not a unit-extent collapse");
321 return *rankReducingExtract;
322 }
323
324 assert(
325 control.rankReductionStrategy ==
326 ControlDropUnitDims::RankReductionStrategy::ReassociativeReshape &&
327 "unknown rank reduction strategy");
328 auto targetType =
329 RankedTensorType::get(shape: targetShape, elementType: tensorType.getElementType());
330 return tensor::CollapseShapeOp::create(builder&: rewriter, location: loc, resultType: targetType, src: operand,
331 reassociation)
332 .getResult();
333 }
334 llvm_unreachable("unsupported operand type");
335}
336
337/// Compute the modified metadata for an operands of operation
338/// whose unit dims are being dropped. Return the new indexing map
339/// to use, the shape of the operand in the replacement op
340/// and the `reassocation` to use to go from original operand shape
341/// to modified operand shape.
342struct UnitExtentReplacementInfo {
343 AffineMap indexMap;
344 SmallVector<ReassociationIndices> reassociation;
345 SmallVector<int64_t> targetShape;
346};
347static UnitExtentReplacementInfo dropUnitExtentFromOperandMetadata(
348 MLIRContext *context, IndexingMapOpInterface op, OpOperand *opOperand,
349 llvm::SmallDenseMap<unsigned, unsigned> &oldDimsToNewDimsMap,
350 ArrayRef<AffineExpr> dimReplacements) {
351 UnitExtentReplacementInfo info;
352 ReassociationIndices reassociationGroup;
353 SmallVector<AffineExpr> newIndexExprs;
354 AffineMap indexingMap = op.getMatchingIndexingMap(opOperand);
355 SmallVector<int64_t> operandShape = op.getStaticOperandShape(opOperand);
356 ArrayRef<AffineExpr> exprs = indexingMap.getResults();
357
358 auto isUnitDim = [&](unsigned dim) {
359 if (auto dimExpr = dyn_cast<AffineDimExpr>(Val: exprs[dim])) {
360 unsigned oldPosition = dimExpr.getPosition();
361 return !oldDimsToNewDimsMap.count(Val: oldPosition) &&
362 (operandShape[dim] == 1);
363 }
364 // Handle the other case where the shape is 1, and is accessed using a
365 // constant 0.
366 if (operandShape[dim] == 1) {
367 // Use the new expression after replacing dimensions that will be dropped
368 // here to handle cases where an affine expression with multiple
369 // dimensions (e.g., `d0 + d2`) can be simplified to 0 after dropping all
370 // dimensions used in the expression (`d0` and `d2` in this example).
371 AffineExpr newExpr = exprs[dim].replaceDims(dimReplacements);
372 auto constAffineExpr = dyn_cast<AffineConstantExpr>(Val&: newExpr);
373 return constAffineExpr && constAffineExpr.getValue() == 0;
374 }
375 return false;
376 };
377
378 unsigned dim = 0;
379 while (dim < operandShape.size() && isUnitDim(dim))
380 reassociationGroup.push_back(Elt: dim++);
381 while (dim < operandShape.size()) {
382 assert(!isUnitDim(dim) && "expected non unit-extent");
383 reassociationGroup.push_back(Elt: dim);
384 AffineExpr newExpr = exprs[dim].replaceDims(dimReplacements);
385 newIndexExprs.push_back(Elt: newExpr);
386 info.targetShape.push_back(Elt: operandShape[dim]);
387 ++dim;
388 // Fold all following dimensions that are unit-extent.
389 while (dim < operandShape.size() && isUnitDim(dim)) {
390 reassociationGroup.push_back(Elt: dim++);
391 }
392 info.reassociation.push_back(Elt: reassociationGroup);
393 reassociationGroup.clear();
394 }
395 info.indexMap =
396 AffineMap::get(dimCount: oldDimsToNewDimsMap.size(), symbolCount: indexingMap.getNumSymbols(),
397 results: newIndexExprs, context);
398 return info;
399}
400
401FailureOr<DropUnitDimsResult>
402linalg::dropUnitDims(RewriterBase &rewriter, IndexingMapOpInterface op,
403 const DroppedUnitDimsBuilder &droppedUnitDimsBuilder,
404 const ControlDropUnitDims &options) {
405 auto dpsOp = dyn_cast<DestinationStyleOpInterface>(Val: op.getOperation());
406 if (!dpsOp) {
407 return rewriter.notifyMatchFailure(
408 arg&: op, msg: "op should implement DestinationStyleOpInterface");
409 }
410
411 SmallVector<AffineMap> indexingMaps = op.getIndexingMapsArray();
412 if (indexingMaps.empty())
413 return failure();
414
415 // 1. Check if any of the iteration dimensions are unit-trip count. They will
416 // end up being unit-trip count if they are used to index into a unit-dim
417 // tensor/memref.
418 AffineMap invertedMap =
419 inversePermutation(map: concatAffineMaps(maps: indexingMaps, context: rewriter.getContext()));
420 if (!invertedMap) {
421 return rewriter.notifyMatchFailure(arg&: op,
422 msg: "invalid indexing maps for operation");
423 }
424
425 SmallVector<int64_t> allShapesSizes;
426 for (OpOperand &opOperand : op->getOpOperands())
427 llvm::append_range(C&: allShapesSizes, R: op.getStaticOperandShape(opOperand: &opOperand));
428
429 // 1a. Get the allowed list of dimensions to drop from the `options`.
430 SmallVector<unsigned> allowedUnitDims = options.controlFn(op);
431 if (allowedUnitDims.empty()) {
432 return rewriter.notifyMatchFailure(
433 arg&: op, msg: "control function returns no allowed unit dims to prune");
434 }
435 llvm::SmallDenseSet<unsigned> unitDimsFilter(allowedUnitDims.begin(),
436 allowedUnitDims.end());
437 llvm::SmallDenseSet<unsigned> unitDims;
438 for (const auto &expr : enumerate(First: invertedMap.getResults())) {
439 if (AffineDimExpr dimExpr = dyn_cast<AffineDimExpr>(Val: expr.value())) {
440 if (allShapesSizes[dimExpr.getPosition()] == 1 &&
441 unitDimsFilter.count(V: expr.index()))
442 unitDims.insert(V: expr.index());
443 }
444 }
445
446 // 2. Compute the new loops of the modified op by dropping the one-trip
447 // count loops.
448 llvm::SmallDenseMap<unsigned, unsigned> oldDimToNewDimMap;
449 SmallVector<AffineExpr> dimReplacements;
450 unsigned newDims = 0;
451 for (auto index : llvm::seq<int64_t>(Size: op.getStaticLoopRanges().size())) {
452 if (unitDims.count(V: index)) {
453 dimReplacements.push_back(
454 Elt: getAffineConstantExpr(constant: 0, context: rewriter.getContext()));
455 } else {
456 oldDimToNewDimMap[index] = newDims;
457 dimReplacements.push_back(
458 Elt: getAffineDimExpr(position: newDims, context: rewriter.getContext()));
459 newDims++;
460 }
461 }
462
463 // 3. For each of the operands, find the
464 // - modified affine map to use.
465 // - shape of the operands after the unit-dims are dropped.
466 // - the reassociation indices used to convert from the original
467 // operand type to modified operand (needed only when using reshapes
468 // for rank reduction strategy)
469 // Note that the indexing maps might need changing even if there are no
470 // unit dimensions that are dropped to handle cases where `0` is used to
471 // access a unit-extent tensor. Consider moving this out of this specific
472 // transformation as a stand-alone transformation. Kept here right now due
473 // to legacy.
474 SmallVector<AffineMap> newIndexingMaps;
475 SmallVector<SmallVector<ReassociationIndices>> reassociations;
476 SmallVector<SmallVector<int64_t>> targetShapes;
477 SmallVector<bool> collapsed;
478 for (OpOperand &opOperand : op->getOpOperands()) {
479 auto indexingMap = op.getMatchingIndexingMap(opOperand: &opOperand);
480 auto replacementInfo =
481 dropUnitExtentFromOperandMetadata(context: rewriter.getContext(), op, opOperand: &opOperand,
482 oldDimsToNewDimsMap&: oldDimToNewDimMap, dimReplacements);
483 reassociations.push_back(Elt: replacementInfo.reassociation);
484 newIndexingMaps.push_back(Elt: replacementInfo.indexMap);
485 targetShapes.push_back(Elt: replacementInfo.targetShape);
486 collapsed.push_back(Elt: !(replacementInfo.indexMap.getNumResults() ==
487 indexingMap.getNumResults()));
488 }
489
490 // Abort if the indexing maps of the result operation are not invertible
491 // (i.e. not legal) or if no dimension was reduced.
492 if (newIndexingMaps == indexingMaps ||
493 !inversePermutation(
494 map: concatAffineMaps(maps: newIndexingMaps, context: rewriter.getContext())))
495 return failure();
496
497 Location loc = op.getLoc();
498 // 4. For each of the operands, collapse the operand to convert
499 // from original shape to shape in the modified operation if needed,
500 // either through use of reshapes or rank-reducing slices as
501 // specified in `options`.
502 // Abort if one of the operands cannot be collapsed.
503 SmallVector<Value> newOperands;
504 for (OpOperand &opOperand : op->getOpOperands()) {
505 int64_t idx = opOperand.getOperandNumber();
506 if (!collapsed[idx]) {
507 newOperands.push_back(Elt: opOperand.get());
508 continue;
509 }
510 FailureOr<Value> collapsed =
511 options.collapseFn(rewriter, loc, opOperand.get(), targetShapes[idx],
512 reassociations[idx], options);
513 if (failed(Result: collapsed)) {
514 // Abort if the operand could not be collapsed.
515 return failure();
516 }
517 newOperands.push_back(Elt: collapsed.value());
518 }
519
520 IndexingMapOpInterface replacementOp = droppedUnitDimsBuilder(
521 loc, rewriter, op, newOperands, newIndexingMaps, unitDims);
522
523 // 6. If any result type changes, insert a reshape/slice to convert from the
524 // original type to the new type.
525 // Abort the transformation if the result cannot be expanded back to its
526 // original shape.
527 SmallVector<Value> resultReplacements;
528 for (auto [index, result] : llvm::enumerate(First: replacementOp->getResults())) {
529 unsigned opOperandIndex = index + dpsOp.getNumDpsInputs();
530 Value origDest = dpsOp.getDpsInitOperand(i: index)->get();
531 if (!collapsed[opOperandIndex]) {
532 resultReplacements.push_back(Elt: result);
533 continue;
534 }
535 FailureOr<Value> expanded =
536 options.expandFn(rewriter, loc, result, origDest,
537 reassociations[opOperandIndex], options);
538 if (failed(Result: expanded)) {
539 // Abort if expansion is not successful.
540 return failure();
541 }
542 resultReplacements.push_back(Elt: expanded.value());
543 }
544
545 return DropUnitDimsResult{.resultOp: replacementOp, .replacements: resultReplacements};
546}
547
548FailureOr<DropUnitDimsResult>
549linalg::dropUnitDims(RewriterBase &rewriter, GenericOp genericOp,
550 const ControlDropUnitDims &options) {
551
552 DroppedUnitDimsBuilder build =
553 [](Location loc, OpBuilder &b, IndexingMapOpInterface op,
554 ArrayRef<Value> newOperands, ArrayRef<AffineMap> newIndexingMaps,
555 const llvm::SmallDenseSet<unsigned> &droppedDims)
556 -> IndexingMapOpInterface {
557 auto genericOp = cast<GenericOp>(Val&: op);
558 // Compute the iterator types of the modified op by dropping the one-trip
559 // count loops.
560 SmallVector<utils::IteratorType> newIteratorTypes;
561 for (auto [index, attr] :
562 llvm::enumerate(First: genericOp.getIteratorTypesArray())) {
563 if (!droppedDims.count(V: index))
564 newIteratorTypes.push_back(Elt: attr);
565 }
566
567 // Create the `linalg.generic` operation with the new operands,
568 // indexing maps, iterator types and result types.
569 ArrayRef<Value> newInputs =
570 ArrayRef<Value>(newOperands).take_front(N: genericOp.getNumDpsInputs());
571 ArrayRef<Value> newOutputs =
572 ArrayRef<Value>(newOperands).take_back(N: genericOp.getNumDpsInits());
573 SmallVector<Type> resultTypes;
574 resultTypes.reserve(N: genericOp.getNumResults());
575 for (unsigned i : llvm::seq<unsigned>(Begin: 0, End: genericOp.getNumResults()))
576 resultTypes.push_back(Elt: newOutputs[i].getType());
577 GenericOp replacementOp =
578 GenericOp::create(builder&: b, location: loc, resultTensorTypes: resultTypes, inputs: newInputs, outputs: newOutputs,
579 indexingMaps: newIndexingMaps, iteratorTypes: newIteratorTypes);
580 b.cloneRegionBefore(region&: genericOp.getRegion(), parent&: replacementOp.getRegion(),
581 before: replacementOp.getRegion().begin());
582 // 5a. Replace `linalg.index` operations that refer to the dropped unit
583 // dimensions.
584 IRRewriter rewriter(b);
585 replaceUnitDimIndexOps(genericOp: replacementOp, unitDims: droppedDims, rewriter);
586
587 return replacementOp;
588 };
589
590 return dropUnitDims(rewriter, op: genericOp, droppedUnitDimsBuilder: build, options);
591}
592
593namespace {
594struct DropUnitDims : public OpRewritePattern<GenericOp> {
595 DropUnitDims(MLIRContext *context, ControlDropUnitDims options = {},
596 PatternBenefit benefit = 1)
597 : OpRewritePattern(context, benefit), options(std::move(options)) {}
598
599 LogicalResult matchAndRewrite(GenericOp genericOp,
600 PatternRewriter &rewriter) const override {
601 FailureOr<DropUnitDimsResult> result =
602 dropUnitDims(rewriter, genericOp, options);
603 if (failed(Result: result)) {
604 return failure();
605 }
606 rewriter.replaceOp(op: genericOp, newValues: result->replacements);
607 return success();
608 }
609
610private:
611 ControlDropUnitDims options;
612};
613} // namespace
614
615//===---------------------------------------------------------------------===//
616// Drop dimensions that are unit-extents within tensor operations.
617//===---------------------------------------------------------------------===//
618
619namespace {
620struct DropPadUnitDims : public OpRewritePattern<tensor::PadOp> {
621 DropPadUnitDims(MLIRContext *context, ControlDropUnitDims options = {},
622 PatternBenefit benefit = 1)
623 : OpRewritePattern(context, benefit), options(std::move(options)) {}
624
625 LogicalResult matchAndRewrite(tensor::PadOp padOp,
626 PatternRewriter &rewriter) const override {
627 // 1a. Get the allowed list of dimensions to drop from the `options`.
628 SmallVector<unsigned> allowedUnitDims = options.controlFn(padOp);
629 if (allowedUnitDims.empty()) {
630 return rewriter.notifyMatchFailure(
631 arg&: padOp, msg: "control function returns no allowed unit dims to prune");
632 }
633
634 if (padOp.getSourceType().getEncoding()) {
635 return rewriter.notifyMatchFailure(
636 arg&: padOp, msg: "cannot collapse dims of tensor with encoding");
637 }
638
639 // Fail for non-constant padding values. The body of the pad could
640 // depend on the padding indices and/or properties of the padded
641 // tensor so for now we fail.
642 // TODO: Support non-constant padding values.
643 Value paddingVal = padOp.getConstantPaddingValue();
644 if (!paddingVal) {
645 return rewriter.notifyMatchFailure(
646 arg&: padOp, msg: "unimplemented: non-constant padding value");
647 }
648
649 ArrayRef<int64_t> sourceShape = padOp.getSourceType().getShape();
650 ArrayRef<int64_t> resultShape = padOp.getResultType().getShape();
651 int64_t padRank = sourceShape.size();
652
653 auto isStaticZero = [](OpFoldResult f) {
654 return getConstantIntValue(ofr: f) == 0;
655 };
656
657 llvm::SmallDenseSet<unsigned> unitDimsFilter(allowedUnitDims.begin(),
658 allowedUnitDims.end());
659 llvm::SmallDenseSet<unsigned> unitDims;
660 SmallVector<int64_t> newShape;
661 SmallVector<int64_t> newResultShape;
662 SmallVector<OpFoldResult> newLowPad;
663 SmallVector<OpFoldResult> newHighPad;
664 for (const auto [dim, size, outSize, low, high] : zip_equal(
665 t: llvm::seq(Begin: static_cast<int64_t>(0), End: padRank), u&: sourceShape,
666 args&: resultShape, args: padOp.getMixedLowPad(), args: padOp.getMixedHighPad())) {
667 if (unitDimsFilter.contains(V: dim) && size == 1 && isStaticZero(low) &&
668 isStaticZero(high)) {
669 unitDims.insert(V: dim);
670 } else {
671 newShape.push_back(Elt: size);
672 newResultShape.push_back(Elt: outSize);
673 newLowPad.push_back(Elt: low);
674 newHighPad.push_back(Elt: high);
675 }
676 }
677
678 if (unitDims.empty()) {
679 return rewriter.notifyMatchFailure(arg&: padOp, msg: "no unit dims to collapse");
680 }
681
682 ReassociationIndices reassociationGroup;
683 SmallVector<ReassociationIndices> reassociationMap;
684 int64_t dim = 0;
685 while (dim < padRank && unitDims.contains(V: dim))
686 reassociationGroup.push_back(Elt: dim++);
687 while (dim < padRank) {
688 assert(!unitDims.contains(dim) && "expected non unit-extent");
689 reassociationGroup.push_back(Elt: dim);
690 dim++;
691 // Fold all following dimensions that are unit-extent.
692 while (dim < padRank && unitDims.contains(V: dim))
693 reassociationGroup.push_back(Elt: dim++);
694 reassociationMap.push_back(Elt: reassociationGroup);
695 reassociationGroup.clear();
696 }
697
698 FailureOr<Value> collapsedSource =
699 options.collapseFn(rewriter, padOp.getLoc(), padOp.getSource(),
700 newShape, reassociationMap, options);
701 if (failed(Result: collapsedSource)) {
702 return rewriter.notifyMatchFailure(arg&: padOp, msg: "Failed to collapse source");
703 }
704
705 // Clone the padding value if it is defined in the region of the pad op.
706 if (paddingVal.getParentBlock() == &padOp.getRegion().front())
707 paddingVal = rewriter.clone(op&: *paddingVal.getDefiningOp())->getResult(idx: 0);
708
709 auto newResultType = RankedTensorType::get(
710 shape: newResultShape, elementType: padOp.getResultType().getElementType());
711 auto newPadOp = tensor::PadOp::create(
712 builder&: rewriter, location: padOp.getLoc(), /*result=*/resultType: newResultType,
713 source: collapsedSource.value(), low: newLowPad, high: newHighPad, constantPadValue: paddingVal,
714 nofold: padOp.getNofold());
715
716 Value dest = padOp.getResult();
717 if (options.rankReductionStrategy ==
718 ControlDropUnitDims::RankReductionStrategy::ExtractInsertSlice) {
719 SmallVector<OpFoldResult> expandedSizes;
720 int64_t numUnitDims = 0;
721 for (auto dim : llvm::seq(Begin: static_cast<int64_t>(0), End: padRank)) {
722 if (unitDims.contains(V: dim)) {
723 expandedSizes.push_back(Elt: rewriter.getIndexAttr(value: 1));
724 numUnitDims++;
725 continue;
726 }
727 expandedSizes.push_back(Elt: tensor::getMixedSize(
728 builder&: rewriter, loc: padOp.getLoc(), value: newPadOp, dim: dim - numUnitDims));
729 }
730 dest = tensor::EmptyOp::create(builder&: rewriter, location: padOp.getLoc(), sizes: expandedSizes,
731 elementType: padOp.getResultType().getElementType());
732 }
733
734 FailureOr<Value> expandedValue =
735 options.expandFn(rewriter, padOp.getLoc(), newPadOp.getResult(), dest,
736 reassociationMap, options);
737 if (failed(Result: expandedValue)) {
738 return rewriter.notifyMatchFailure(arg&: padOp, msg: "Failed to expand result");
739 }
740 rewriter.replaceOp(op: padOp, newValues: expandedValue.value());
741 return success();
742 }
743
744private:
745 ControlDropUnitDims options;
746};
747} // namespace
748
749namespace {
750/// Convert `extract_slice` operations to rank-reduced versions.
751struct RankReducedExtractSliceOp
752 : public OpRewritePattern<tensor::ExtractSliceOp> {
753 using OpRewritePattern<tensor::ExtractSliceOp>::OpRewritePattern;
754
755 LogicalResult matchAndRewrite(tensor::ExtractSliceOp sliceOp,
756 PatternRewriter &rewriter) const override {
757 RankedTensorType resultType = sliceOp.getType();
758 SmallVector<OpFoldResult> targetShape;
759 for (auto size : resultType.getShape())
760 targetShape.push_back(Elt: rewriter.getIndexAttr(value: size));
761 auto reassociation = getReassociationMapForFoldingUnitDims(mixedSizes: targetShape);
762 if (!reassociation ||
763 reassociation->size() == static_cast<size_t>(resultType.getRank()))
764 return failure();
765
766 SmallVector<OpFoldResult> offsets = sliceOp.getMixedOffsets();
767 SmallVector<OpFoldResult> strides = sliceOp.getMixedStrides();
768 SmallVector<OpFoldResult> sizes = sliceOp.getMixedSizes();
769 SmallVector<int64_t> staticSizes;
770 std::tie(args&: staticSizes, args: std::ignore) = decomposeMixedValues(mixedValues: sizes);
771 llvm::SmallBitVector droppedDims = getPositionsOfShapeOne(
772 rank: sizes.size() - reassociation->size(), shape: staticSizes);
773 RankedTensorType rankReducedType =
774 tensor::inferSliceType(sourceTensorType: sliceOp.getSourceType(), sizes, droppedDims);
775
776 Location loc = sliceOp.getLoc();
777 Value newSlice = tensor::ExtractSliceOp::create(
778 builder&: rewriter, location: loc, resultType: rankReducedType, source: sliceOp.getSource(), offsets, sizes,
779 strides);
780 rewriter.replaceOpWithNewOp<tensor::ExpandShapeOp>(
781 op: sliceOp, args&: resultType, args&: newSlice, args&: *reassociation);
782 return success();
783 }
784};
785
786/// Convert `insert_slice` operations to rank-reduced versions.
787/// This patterns works with both InsertSliceOp and ParallelInsertSliceOp.
788template <typename InsertOpTy>
789struct RankReducedInsertSliceOp : public OpRewritePattern<InsertOpTy> {
790 using OpRewritePattern<InsertOpTy>::OpRewritePattern;
791
792 LogicalResult matchAndRewrite(InsertOpTy insertSliceOp,
793 PatternRewriter &rewriter) const override {
794 RankedTensorType sourceType = insertSliceOp.getSourceType();
795 SmallVector<OpFoldResult> targetShape;
796 for (auto size : sourceType.getShape())
797 targetShape.push_back(Elt: rewriter.getIndexAttr(value: size));
798 auto reassociation = getReassociationMapForFoldingUnitDims(mixedSizes: targetShape);
799 if (!reassociation ||
800 reassociation->size() == static_cast<size_t>(sourceType.getRank()))
801 return failure();
802
803 Location loc = insertSliceOp.getLoc();
804 tensor::CollapseShapeOp reshapedSource;
805 {
806 OpBuilder::InsertionGuard g(rewriter);
807 // The only difference between InsertSliceOp and ParallelInsertSliceOp
808 // is the insertion point is just before the ParallelCombiningOp in the
809 // parallel case.
810 if (std::is_same<InsertOpTy, tensor::ParallelInsertSliceOp>::value)
811 rewriter.setInsertionPoint(insertSliceOp->getParentOp());
812 reshapedSource = tensor::CollapseShapeOp::create(
813 rewriter, loc, insertSliceOp.getSource(), *reassociation);
814 }
815 rewriter.replaceOpWithNewOp<InsertOpTy>(
816 insertSliceOp, reshapedSource, insertSliceOp.getDest(),
817 insertSliceOp.getMixedOffsets(), insertSliceOp.getMixedSizes(),
818 insertSliceOp.getMixedStrides());
819 return success();
820 }
821};
822} // namespace
823
824/// Patterns that are used to canonicalize the use of unit-extent dims for
825/// broadcasting.
826void mlir::linalg::populateFoldUnitExtentDimsPatterns(
827 RewritePatternSet &patterns, linalg::ControlDropUnitDims &options) {
828 auto *context = patterns.getContext();
829 patterns.add<DropUnitDims>(arg&: context, args&: options);
830 patterns.add<DropPadUnitDims>(arg&: context, args&: options);
831}
832
833void mlir::linalg::populateFoldUnitExtentDimsCanonicalizationPatterns(
834 RewritePatternSet &patterns, linalg::ControlDropUnitDims &options) {
835 auto *context = patterns.getContext();
836 bool reassociativeReshape =
837 options.rankReductionStrategy ==
838 linalg::ControlDropUnitDims::RankReductionStrategy::ReassociativeReshape;
839 if (reassociativeReshape) {
840 patterns.add<RankReducedExtractSliceOp,
841 RankReducedInsertSliceOp<tensor::InsertSliceOp>,
842 RankReducedInsertSliceOp<tensor::ParallelInsertSliceOp>>(
843 arg&: context);
844 tensor::CollapseShapeOp::getCanonicalizationPatterns(results&: patterns, context);
845 tensor::ExpandShapeOp::getCanonicalizationPatterns(results&: patterns, context);
846 }
847 linalg::FillOp::getCanonicalizationPatterns(results&: patterns, context);
848 tensor::EmptyOp::getCanonicalizationPatterns(results&: patterns, context);
849 tensor::populateFoldTensorEmptyPatterns(patterns);
850 memref::populateResolveRankedShapedTypeResultDimsPatterns(patterns);
851 memref::populateResolveShapedTypeResultDimsPatterns(patterns);
852}
853
854void mlir::linalg::populateMoveInitOperandsToInputPattern(
855 RewritePatternSet &patterns) {
856 patterns.add<MoveInitOperandsToInput>(arg: patterns.getContext());
857}
858
859namespace {
860/// Pass that removes unit-extent dims within generic ops.
861struct LinalgFoldUnitExtentDimsPass
862 : public impl::LinalgFoldUnitExtentDimsPassBase<
863 LinalgFoldUnitExtentDimsPass> {
864 using impl::LinalgFoldUnitExtentDimsPassBase<
865 LinalgFoldUnitExtentDimsPass>::LinalgFoldUnitExtentDimsPassBase;
866 void runOnOperation() override {
867 Operation *op = getOperation();
868 MLIRContext *context = op->getContext();
869 ControlDropUnitDims options;
870 if (useRankReducingSlices) {
871 options.rankReductionStrategy = linalg::ControlDropUnitDims::
872 RankReductionStrategy::ExtractInsertSlice;
873 }
874
875 // Apply fold unit extent dims patterns with walk-based driver.
876 {
877 RewritePatternSet patterns(context);
878 linalg::populateFoldUnitExtentDimsPatterns(patterns, options);
879 walkAndApplyPatterns(op, patterns: std::move(patterns));
880 }
881
882 // Apply canonicalization patterns with greedy driver.
883 {
884 RewritePatternSet patterns(context);
885 populateMoveInitOperandsToInputPattern(patterns);
886 linalg::populateFoldUnitExtentDimsCanonicalizationPatterns(patterns,
887 options);
888 (void)applyPatternsGreedily(op, patterns: std::move(patterns));
889 }
890 }
891};
892
893} // namespace
894
895namespace {
896
897/// Returns reassociation indices for collapsing/expanding a
898/// tensor of rank `rank` at position `pos`.
899static SmallVector<ReassociationIndices>
900getReassociationForReshapeAtDim(int64_t rank, int64_t pos) {
901 SmallVector<ReassociationIndices> reassociation(rank - 1, {0, 1});
902 bool lastDim = pos == rank - 1;
903 if (rank > 2) {
904 for (int64_t i = 0; i < rank - 1; i++) {
905 if (i == pos || (lastDim && i == pos - 1))
906 reassociation[i] = ReassociationIndices{i, i + 1};
907 else if (i < pos)
908 reassociation[i] = ReassociationIndices{i};
909 else
910 reassociation[i] = ReassociationIndices{i + 1};
911 }
912 }
913 return reassociation;
914}
915
916/// Returns a collapsed `val` where the collapsing occurs at dim `pos`.
917/// If `pos < 0`, then don't collapse.
918static Value collapseSingletonDimAt(PatternRewriter &rewriter, Value val,
919 int64_t pos) {
920 if (pos < 0)
921 return val;
922 auto valType = cast<ShapedType>(Val: val.getType());
923 SmallVector<int64_t> collapsedShape(valType.getShape());
924 collapsedShape.erase(CI: collapsedShape.begin() + pos);
925 ControlDropUnitDims control{};
926 FailureOr<Value> collapsed = control.collapseFn(
927 rewriter, val.getLoc(), val, collapsedShape,
928 getReassociationForReshapeAtDim(rank: valType.getRank(), pos), control);
929 assert(llvm::succeeded(collapsed) && "Collapsing the value failed");
930 return collapsed.value();
931}
932
933/// Base class for all rank reduction patterns for contraction ops
934/// with unit dimensions. All patterns should convert one named op
935/// to another named op. Intended to reduce only one iteration space dim
936/// at a time.
937/// Reducing multiple dims will happen with recusive application of
938/// pattern rewrites.
939template <typename FromOpTy, typename ToOpTy>
940struct RankReduceContractionOps : OpRewritePattern<FromOpTy> {
941 using OpRewritePattern<FromOpTy>::OpRewritePattern;
942
943 /// Collapse all collapsable operands.
944 SmallVector<Value>
945 collapseOperands(PatternRewriter &rewriter, ArrayRef<Value> operands,
946 ArrayRef<int64_t> operandCollapseDims) const {
947 assert(operandCollapseDims.size() == 3 && operands.size() == 3 &&
948 "expected 3 operands and dims");
949 return llvm::map_to_vector(
950 llvm::zip(t&: operands, u&: operandCollapseDims), [&](auto pair) {
951 return collapseSingletonDimAt(rewriter, std::get<0>(pair),
952 std::get<1>(pair));
953 });
954 }
955
956 /// Expand result tensor.
957 Value expandResult(PatternRewriter &rewriter, Value result,
958 RankedTensorType expandedType, int64_t dim) const {
959 return tensor::ExpandShapeOp::create(
960 builder&: rewriter, location: result.getLoc(), resultType: expandedType, src: result,
961 reassociation: getReassociationForReshapeAtDim(rank: expandedType.getRank(), pos: dim));
962 }
963
964 LogicalResult matchAndRewrite(FromOpTy contractionOp,
965 PatternRewriter &rewriter) const override {
966 if (contractionOp.hasUserDefinedMaps()) {
967 return rewriter.notifyMatchFailure(
968 contractionOp, "ops with user-defined maps are not supported");
969 }
970 // linalg.matmul is the only target op with a `cast` attribute.
971 if constexpr ((std::is_same_v<FromOpTy, MatmulOp> ||
972 std::is_same_v<FromOpTy, BatchMatmulOp>) &&
973 !std::is_same_v<ToOpTy, MatmulOp>) {
974 if (contractionOp.getCast() != TypeFn::cast_signed)
975 return rewriter.notifyMatchFailure(
976 contractionOp, "target op cannot represent a non-signed cast");
977 }
978
979 auto loc = contractionOp.getLoc();
980 auto inputs = contractionOp.getDpsInputs();
981 auto inits = contractionOp.getDpsInits();
982 if (inputs.size() != 2 || inits.size() != 1)
983 return rewriter.notifyMatchFailure(contractionOp,
984 "expected 2 inputs and 1 init");
985 auto lhs = inputs[0];
986 auto rhs = inputs[1];
987 auto init = inits[0];
988 SmallVector<Value> operands{lhs, rhs, init};
989
990 SmallVector<int64_t> operandUnitDims;
991 if (failed(getOperandUnitDims(op: contractionOp, operandUnitDims)))
992 return rewriter.notifyMatchFailure(contractionOp,
993 "no reducable dims found");
994
995 SmallVector<Value> collapsedOperands =
996 collapseOperands(rewriter, operands, operandCollapseDims: operandUnitDims);
997 Value collapsedLhs = collapsedOperands[0];
998 Value collapsedRhs = collapsedOperands[1];
999 Value collapsedInit = collapsedOperands[2];
1000 SmallVector<Type, 1> collapsedResultTy;
1001 if (isa<RankedTensorType>(Val: collapsedInit.getType()))
1002 collapsedResultTy.push_back(Elt: collapsedInit.getType());
1003 ToOpTy collapsedOp;
1004 if constexpr (std::is_same_v<FromOpTy, BatchMatmulOp> &&
1005 std::is_same_v<ToOpTy, MatmulOp>) {
1006 if (TypeFnAttr castAttr = contractionOp.getCastAttr()) {
1007 collapsedOp = ToOpTy::create(rewriter, loc, collapsedResultTy,
1008 ValueRange{collapsedLhs, collapsedRhs},
1009 ValueRange{collapsedInit}, castAttr);
1010 } else {
1011 collapsedOp = ToOpTy::create(rewriter, loc, collapsedResultTy,
1012 ValueRange{collapsedLhs, collapsedRhs},
1013 ValueRange{collapsedInit});
1014 }
1015 } else {
1016 collapsedOp = ToOpTy::create(rewriter, loc, collapsedResultTy,
1017 ValueRange{collapsedLhs, collapsedRhs},
1018 ValueRange{collapsedInit});
1019 }
1020 for (auto attr : contractionOp->getDiscardableAttrDictionary()) {
1021 if (attr.getName() == LinalgDialect::kMemoizedIndexingMapsAttrName ||
1022 attr.getName() == "indexing_maps")
1023 continue;
1024 collapsedOp->setDiscardableAttr(attr.getName(), attr.getValue());
1025 }
1026
1027 auto results = contractionOp.getResults();
1028 assert(results.size() < 2 && "expected at most one result");
1029 if (results.empty()) {
1030 rewriter.replaceOp(contractionOp, collapsedOp);
1031 } else {
1032 rewriter.replaceOp(
1033 contractionOp,
1034 expandResult(rewriter, result: collapsedOp.getResultTensors()[0],
1035 expandedType: cast<RankedTensorType>(results[0].getType()),
1036 dim: operandUnitDims[2]));
1037 }
1038
1039 return success();
1040 }
1041
1042 /// Populate `operandUnitDims` with 3 indices indicating the unit dim
1043 /// for each operand that should be collapsed in this pattern. If an
1044 /// operand shouldn't be collapsed, the index should be negative.
1045 virtual LogicalResult
1046 getOperandUnitDims(LinalgOp op,
1047 SmallVectorImpl<int64_t> &operandUnitDims) const = 0;
1048};
1049
1050/// Patterns for unbatching batched contraction ops
1051template <typename FromOpTy, typename ToOpTy>
1052struct RankReduceToUnBatched : RankReduceContractionOps<FromOpTy, ToOpTy> {
1053 using RankReduceContractionOps<FromOpTy, ToOpTy>::RankReduceContractionOps;
1054
1055 /// Look for unit batch dims to collapse.
1056 LogicalResult
1057 getOperandUnitDims(LinalgOp op,
1058 SmallVectorImpl<int64_t> &operandUnitDims) const override {
1059 FailureOr<ContractionDimensions> maybeContractionDims =
1060 inferContractionDims(linalgOp: op);
1061 if (failed(Result: maybeContractionDims)) {
1062 LLVM_DEBUG(llvm::dbgs() << "could not infer contraction dims");
1063 return failure();
1064 }
1065 const ContractionDimensions &contractionDims = maybeContractionDims.value();
1066
1067 if (contractionDims.batch.size() != 1)
1068 return failure();
1069 auto batchDim = contractionDims.batch[0];
1070 SmallVector<std::pair<Value, unsigned>, 3> bOperands;
1071 op.mapIterationSpaceDimToAllOperandDims(dimPos: batchDim, operandDimPairs&: bOperands);
1072 if (bOperands.size() != 3 || llvm::any_of(bOperands, [](auto pair) {
1073 return cast<ShapedType>(std::get<0>(pair).getType())
1074 .getShape()[std::get<1>(pair)] != 1;
1075 })) {
1076 LLVM_DEBUG(llvm::dbgs() << "specified unit dims not found");
1077 return failure();
1078 }
1079
1080 operandUnitDims = SmallVector<int64_t>{std::get<1>(in&: bOperands[0]),
1081 std::get<1>(in&: bOperands[1]),
1082 std::get<1>(in&: bOperands[2])};
1083 return success();
1084 }
1085};
1086
1087/// Patterns for reducing non-batch dimensions
1088template <typename FromOpTy, typename ToOpTy>
1089struct RankReduceMatmul : RankReduceContractionOps<FromOpTy, ToOpTy> {
1090 using RankReduceContractionOps<FromOpTy, ToOpTy>::RankReduceContractionOps;
1091
1092 /// Helper for determining whether the lhs/init or rhs/init are reduced.
1093 static bool constexpr reduceLeft =
1094 (std::is_same_v<FromOpTy, BatchMatmulOp> &&
1095 std::is_same_v<ToOpTy, BatchVecmatOp>) ||
1096 (std::is_same_v<FromOpTy, MatmulOp> &&
1097 std::is_same_v<ToOpTy, VecmatOp>) ||
1098 (std::is_same_v<FromOpTy, MatvecOp> && std::is_same_v<ToOpTy, DotOp>);
1099
1100 /// Look for non-batch spatial dims to collapse.
1101 LogicalResult
1102 getOperandUnitDims(LinalgOp op,
1103 SmallVectorImpl<int64_t> &operandUnitDims) const override {
1104 FailureOr<ContractionDimensions> maybeContractionDims =
1105 inferContractionDims(linalgOp: op);
1106 if (failed(Result: maybeContractionDims)) {
1107 LLVM_DEBUG(llvm::dbgs() << "could not infer contraction dims");
1108 return failure();
1109 }
1110 const ContractionDimensions &contractionDims = maybeContractionDims.value();
1111
1112 if constexpr (reduceLeft) {
1113 auto m = contractionDims.m[0];
1114 SmallVector<std::pair<Value, unsigned>, 2> mOperands;
1115 op.mapIterationSpaceDimToAllOperandDims(dimPos: m, operandDimPairs&: mOperands);
1116 if (mOperands.size() != 2)
1117 return failure();
1118 if (llvm::all_of(mOperands, [](auto pair) {
1119 return cast<ShapedType>(std::get<0>(pair).getType())
1120 .getShape()[std::get<1>(pair)] == 1;
1121 })) {
1122 operandUnitDims = SmallVector<int64_t>{std::get<1>(in&: mOperands[0]), -1,
1123 std::get<1>(in&: mOperands[1])};
1124 return success();
1125 }
1126 } else {
1127 auto n = contractionDims.n[0];
1128 SmallVector<std::pair<Value, unsigned>, 2> nOperands;
1129 op.mapIterationSpaceDimToAllOperandDims(dimPos: n, operandDimPairs&: nOperands);
1130 if (nOperands.size() != 2)
1131 return failure();
1132 if (llvm::all_of(nOperands, [](auto pair) {
1133 return cast<ShapedType>(std::get<0>(pair).getType())
1134 .getShape()[std::get<1>(pair)] == 1;
1135 })) {
1136 operandUnitDims = SmallVector<int64_t>{-1, std::get<1>(in&: nOperands[0]),
1137 std::get<1>(in&: nOperands[1])};
1138 return success();
1139 }
1140 }
1141 LLVM_DEBUG(llvm::dbgs() << "specified unit dims not found");
1142 return failure();
1143 }
1144};
1145
1146} // namespace
1147
1148void mlir::linalg::populateContractionOpRankReducingPatterns(
1149 RewritePatternSet &patterns) {
1150 MLIRContext *context = patterns.getContext();
1151 // Unbatching patterns for unit batch size
1152 patterns.add<RankReduceToUnBatched<BatchMatmulOp, MatmulOp>>(arg&: context);
1153 patterns.add<RankReduceToUnBatched<BatchMatvecOp, MatvecOp>>(arg&: context);
1154 patterns.add<RankReduceToUnBatched<BatchVecmatOp, VecmatOp>>(arg&: context);
1155
1156 // Non-batch rank 1 reducing patterns
1157 patterns.add<RankReduceMatmul<MatmulOp, VecmatOp>>(arg&: context);
1158 patterns.add<RankReduceMatmul<MatmulOp, MatvecOp>>(arg&: context);
1159 // Batch rank 1 reducing patterns
1160 patterns.add<RankReduceMatmul<BatchMatmulOp, BatchVecmatOp>>(arg&: context);
1161 patterns.add<RankReduceMatmul<BatchMatmulOp, BatchMatvecOp>>(arg&: context);
1162
1163 // Non-batch rank 0 reducing patterns
1164 patterns.add<RankReduceMatmul<MatvecOp, DotOp>>(arg&: context);
1165 patterns.add<RankReduceMatmul<VecmatOp, DotOp>>(arg&: context);
1166}
1167