1//===- LinalgInterfaces.cpp - Linalg interfaces implementation ------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "mlir/Dialect/Linalg/IR/LinalgInterfaces.h"
10
11#include "mlir/Dialect/Affine/IR/AffineOps.h"
12#include "mlir/Dialect/Arith/IR/Arith.h"
13#include "mlir/Dialect/Arith/Utils/Utils.h"
14#include "mlir/Dialect/Complex/IR/Complex.h"
15#include "mlir/Dialect/Linalg/IR/Linalg.h"
16#include "mlir/IR/AffineExpr.h"
17#include "mlir/IR/AffineExprVisitor.h"
18#include "mlir/IR/AffineMap.h"
19#include "mlir/IR/BuiltinTypeInterfaces.h"
20#include "mlir/IR/MLIRContext.h"
21#include "mlir/IR/TypeUtilities.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/SetOperations.h"
24#include "llvm/ADT/SmallBitVector.h"
25#include "llvm/ADT/SmallVector.h"
26#include "llvm/Support/Casting.h"
27#include "llvm/Support/raw_ostream.h"
28#include <optional>
29
30using namespace mlir;
31using namespace mlir::linalg;
32
33/// Include the definitions of the copy operation interface.
34#include "mlir/Dialect/Linalg/IR/LinalgInterfaces.cpp.inc"
35
36//===----------------------------------------------------------------------===//
37// Interface utility functions
38//===----------------------------------------------------------------------===//
39
40bool linalg::detail::canOpOperandsBeDroppedImpl(
41 linalg::LinalgOp linalgOp, ArrayRef<OpOperand *> droppedOperands) {
42 SmallVector<AffineMap> indexingMaps;
43 for (auto &opOperand : linalgOp->getOpOperands()) {
44 if (llvm::is_contained(Range&: droppedOperands, Element: &opOperand))
45 continue;
46 indexingMaps.push_back(Elt: linalgOp.getMatchingIndexingMap(opOperand: &opOperand));
47 }
48 if (indexingMaps.empty()) {
49 // If there are no indexing maps, the operand can only be dropped
50 // if the op has no loops.
51 return linalgOp.getNumLoops() == 0;
52 }
53 return inversePermutation(map: concatAffineMaps(
54 maps: indexingMaps, context: linalgOp.getContext())) != AffineMap();
55}
56
57//===----------------------------------------------------------------------===//
58// CopyOpInterface implementation
59//===----------------------------------------------------------------------===//
60
61bool linalg::isaCopyOpInterface(LinalgOp op) {
62 // Check all loops are parallel and linalgOp is single input and output.
63 if (!op.isAllParallelLoops() || !op.isSingleInputOutput())
64 return false;
65
66 auto mapRange = op.getIndexingMapsArray();
67 if (mapRange.size() != 2 || !mapRange.front().isIdentity() ||
68 !mapRange.back().isIdentity()) {
69 return false;
70 }
71 // Check yield first block argument.
72 Block *body = op.getBlock();
73 if (body->getOperations().size() != 1)
74 return false;
75 auto yieldOp = dyn_cast<linalg::YieldOp>(Val&: body->back());
76 if (!yieldOp || yieldOp.getNumOperands() != 1)
77 return false;
78 return yieldOp->getOperand(idx: 0) == body->getArgument(i: 0);
79}
80
81//===----------------------------------------------------------------------===//
82// FillOpInterface implementation
83//===----------------------------------------------------------------------===//
84/// Detects if a linalg.generic operation represents a fill with an inlined
85/// constant. If so, returns the constant value. Otherwise, returns
86/// std::nullopt.
87static std::optional<Value> isaInlinedFillOp(GenericOp op) {
88 if (!op.isAllParallelLoops() || op.getNumDpsInits() != 1 ||
89 op.getNumDpsInputs() != 0)
90 return std::nullopt;
91
92 // Init should not be referenced.
93 if (op.payloadUsesValueFromOperand(opOperand: op.getDpsInitOperand(i: 0)))
94 return std::nullopt;
95
96 Block *body = op.getBody();
97 if (body->getOperations().size() != 1)
98 return std::nullopt;
99
100 auto yieldOp = dyn_cast<linalg::YieldOp>(Val&: body->back());
101 if (!yieldOp || yieldOp.getNumOperands() != 1)
102 return std::nullopt;
103
104 Value yieldOperand = yieldOp->getOperand(idx: 0);
105 if (!yieldOperand.getDefiningOp<arith::ConstantOp>() &&
106 !yieldOperand.getDefiningOp<complex::ConstantOp>())
107 return std::nullopt;
108
109 return yieldOperand;
110}
111
112/// Detects if a linalg.generic operation represents an external scalar input.
113/// If so, returns the constant value. Otherwise, returns std::nullopt.
114static std::optional<Value> isaExternalFillOp(GenericOp op) {
115 // Structural.
116 if (!op.isAllParallelLoops() || !op.isSingleInputOutput() ||
117 !op.isSingleYieldOp())
118 return std::nullopt;
119
120 // Input should be referenced and init should not.
121 if (!op.payloadUsesValueFromOperand(opOperand: op.getDpsInputOperand(i: 0)) ||
122 op.payloadUsesValueFromOperand(opOperand: op.getDpsInitOperand(i: 0)))
123 return std::nullopt;
124
125 OpOperand *value = op.getDpsInputOperand(i: 0);
126 if (!op.isScalar(opOperand: value))
127 return std::nullopt;
128 return value->get();
129}
130
131std::optional<Value> linalg::isaFillOpInterface(GenericOp op) {
132 if (auto fillVal = isaInlinedFillOp(op))
133 return fillVal;
134 return isaExternalFillOp(op);
135}
136
137//===----------------------------------------------------------------------===//
138// BroadcastOpInterface implementation
139//===----------------------------------------------------------------------===//
140std::optional<SmallVector<int64_t>>
141linalg::isaBroadcastOpInterface(LinalgOp linalgOp) {
142 if (auto broadcastOp = dyn_cast<BroadcastOp>(Val: linalgOp.getOperation()))
143 return SmallVector<int64_t>(broadcastOp.getDimensions().begin(),
144 broadcastOp.getDimensions().end());
145
146 auto op = dyn_cast<GenericOp>(Val: linalgOp.getOperation());
147 if (!op)
148 return std::nullopt;
149
150 // Structural.
151 if (!op.isAllParallelLoops() || !op.isSingleInputOutput() ||
152 !op.isSingleYieldOp())
153 return std::nullopt;
154
155 auto srcTy = op.getDpsInputOperand(i: 0)->get().getType();
156 auto dstTy = op.getDpsInitOperand(i: 0)->get().getType();
157 if (!isa<MemRefType, RankedTensorType>(Val: srcTy) ||
158 !isa<MemRefType, RankedTensorType>(Val: dstTy))
159 return std::nullopt;
160
161 // Check output is identity map. Broadcast could additionally be
162 // employing permutation of indices and that would be expressible
163 // in linalg.generic but is not expressible for named broadcast op.
164 auto dstMap = op.getIndexingMapsArray()[1];
165 if (!dstMap.isIdentity())
166 return std::nullopt;
167
168 SmallVector<int64_t> position;
169 auto srcMap = op.getIndexingMapsArray()[0];
170
171 if (srcMap.getResults().size() >= dstMap.getResults().size())
172 return std::nullopt;
173
174 // Check input map is monotonically increasing DimIds.
175 for (unsigned i = 0; i < srcMap.getNumResults(); ++i) {
176 auto expr = llvm::dyn_cast<AffineDimExpr>(Val: srcMap.getResults()[i]);
177 if (!expr)
178 return std::nullopt;
179 int64_t pos = expr.getPosition();
180 if (i > 0 && pos <= position[i - 1])
181 return std::nullopt;
182 position.push_back(Elt: expr.getPosition());
183 }
184
185 SmallVector<int64_t> broadcastedDims;
186 auto numDims = srcMap.getNumDims();
187 // This is quadratic but number of items is generally small.
188 for (auto dim : llvm::seq<int64_t>(Begin: 0, End: numDims)) {
189 if (!llvm::is_contained(Range&: position, Element: dim))
190 broadcastedDims.push_back(Elt: dim);
191 }
192 return broadcastedDims;
193}
194
195//===----------------------------------------------------------------------===//
196// TransposeOpInterface implementation
197//===----------------------------------------------------------------------===//
198std::optional<SmallVector<int64_t>>
199linalg::isaTransposeOpInterface(GenericOp op) {
200 // To specialize as a transpose op, the genericOp must be
201 // all parallel loops, single input, single output, and its body
202 // should be just a yield op, yielding input as output as is (no compute).
203 if (!op.isAllParallelLoops() || !op.isSingleInputOutput() ||
204 !op.isSingleYieldOp())
205 return std::nullopt;
206
207 auto mapRange = op.getIndexingMapsArray();
208 if (mapRange.size() != 2)
209 return std::nullopt;
210
211 auto mapOfInput = mapRange.front();
212 auto mapOfResult = mapRange.back();
213
214 // linalg.transpose permutes the dimensions of input using this
215 // rule: dim(result, i) = dim(input, permutation[i])
216 if (!mapOfResult.isIdentity() || !mapOfInput.isPermutation())
217 return std::nullopt;
218
219 SmallVector<int64_t> permutation(mapOfInput.getNumDims());
220 for (unsigned i = 0; i < mapOfInput.getNumDims(); ++i) {
221 auto expr = llvm::cast<AffineDimExpr>(Val: mapOfInput.getResults()[i]);
222 permutation[expr.getPosition()] = i;
223 }
224 return permutation;
225}
226
227//===----------------------------------------------------------------------===//
228// ReduceOpInterface implementation
229//===----------------------------------------------------------------------===//
230std::optional<SmallVector<int64_t>>
231linalg::isaReductionOpInterface(GenericOp op) {
232 // It must reduce along at least one dimension.
233 if (op.getNumReductionLoops() == 0)
234 return std::nullopt;
235
236 // linalg.reduce takes N inputs and N inits, N >= 1.
237 unsigned numInputs = op.getNumDpsInputs();
238 if (numInputs == 0 || numInputs != op.getNumDpsInits())
239 return std::nullopt;
240
241 // The reduction dimensions are the loops carrying a reduction iterator.
242 SmallVector<int64_t> reductionDims;
243 for (auto [idx, iter] : llvm::enumerate(First: op.getIteratorTypesArray()))
244 if (iter == utils::IteratorType::reduction)
245 reductionDims.push_back(Elt: idx);
246
247 // All inputs must be read with an identity indexing map and all outputs with
248 // the identity map with the reduction dimensions dropped, matching the
249 // semantics of linalg.reduce.
250 AffineMap expectedOutputMap =
251 AffineMap::getMultiDimIdentityMap(numDims: op.getNumLoops(), context: op.getContext())
252 .dropResults(positions: reductionDims);
253 for (OpOperand *input : op.getDpsInputOperands())
254 if (!op.getMatchingIndexingMap(opOperand: input).isIdentity())
255 return std::nullopt;
256 for (OpOperand &init : op.getDpsInitsMutable())
257 if (op.getMatchingIndexingMap(opOperand: &init) != expectedOutputMap)
258 return std::nullopt;
259
260 // Unlike linalg.generic, linalg.reduce requires all inputs to share the same
261 // shape and all inits to match it exactly, including static sizes, after
262 // dropping the reduction dimensions.
263 auto inputType =
264 dyn_cast<ShapedType>(Val: op.getDpsInputOperand(i: 0)->get().getType());
265 if (!inputType || !inputType.hasRank())
266 return std::nullopt;
267 for (OpOperand *input : op.getDpsInputOperands()) {
268 auto type = dyn_cast<ShapedType>(Val: input->get().getType());
269 if (!type || !type.hasRank() || type.getShape() != inputType.getShape())
270 return std::nullopt;
271 }
272
273 SmallVector<int64_t> expectedOutputShape;
274 for (auto [idx, size] : llvm::enumerate(First: inputType.getShape()))
275 if (!llvm::is_contained(Range&: reductionDims, Element: idx))
276 expectedOutputShape.push_back(Elt: size);
277 for (OpOperand &init : op.getDpsInitsMutable()) {
278 auto type = dyn_cast<ShapedType>(Val: init.get().getType());
279 if (!type || !type.hasRank() ||
280 type.getShape() != ArrayRef<int64_t>(expectedOutputShape))
281 return std::nullopt;
282 }
283
284 return reductionDims;
285}
286
287//===----------------------------------------------------------------------===//
288// Elementwise Single Unary/Binary-OpInterface implementation
289//===----------------------------------------------------------------------===//
290
291static bool isaElemwiseSingleOpInterface(linalg::GenericOp op, unsigned arity) {
292 // Check all loops are parallel.
293 if (!op.isAllParallelLoops() || op.getNumLoops() < 1)
294 return false;
295
296 // Check there are arity-inputs and 1-output. Non-identity indexing maps are
297 // allowed as they can be represented by the category op.
298 if (op.getNumDpsInputs() != arity || op.getNumDpsInits() != 1)
299 return false;
300
301 // Init should not be referenced for elementwise operations.
302 if (op.payloadUsesValueFromOperand(opOperand: op.getDpsInitOperand(i: 0)))
303 return false;
304
305 // A linalg.generic could be series of elementwise ops e.g. exp(neg(x)) such
306 // as resulting from producer-consumer fusion. Here, we restrict to two ops in
307 // the body, where the first is the elementwise single op and the second a
308 // yield.
309 Block *body = op.getBody();
310 if (body->getOperations().size() != 2)
311 return false;
312
313 // The payload op must have one result and at least arity-many operands
314 // (otherwise not all inputs can be used). It can have additional operands
315 // from outside of the generic op (e.g. div(1, x) for elementwise reciprocal)
316 // or use an input more than once (e.g. mul(x, x) for elementwise square).
317 Operation *oper = &body->front();
318 if (oper->getNumOperands() < arity || oper->getNumResults() != 1)
319 return false;
320
321 auto yieldOp = dyn_cast<linalg::YieldOp>(Val&: body->back());
322 return !(!yieldOp || yieldOp.getNumOperands() != 1 ||
323 yieldOp->getOperand(idx: 0).getDefiningOp() != oper);
324}
325
326bool linalg::isaElemwiseSingleUnaryOpInterface(linalg::GenericOp op) {
327 // All basic elemwise checks.
328 if (!isaElemwiseSingleOpInterface(op, arity: 1))
329 return false;
330
331 // Check input is actually used.
332 if (!op.payloadUsesValueFromOperand(opOperand: op.getDpsInputOperand(i: 0)))
333 return false;
334 return true;
335}
336
337bool linalg::isaElemwiseSingleBinaryOpInterface(linalg::GenericOp op) {
338 // All basic elemwise checks.
339 if (!isaElemwiseSingleOpInterface(op, arity: 2))
340 return false;
341
342 // Check both inputs are used (elementwise).
343 OpOperand *inputOpOperand0 = op.getDpsInputOperand(i: 0);
344 OpOperand *inputOpOperand1 = op.getDpsInputOperand(i: 1);
345 return !(!op.payloadUsesValueFromOperand(opOperand: inputOpOperand0) ||
346 !op.payloadUsesValueFromOperand(opOperand: inputOpOperand1));
347}
348
349bool linalg::isaElemwiseSingleTernaryOpInterface(linalg::GenericOp op) {
350 // All basic elemwise checks.
351 if (!isaElemwiseSingleOpInterface(op, arity: 3))
352 return false;
353
354 // The only ternary (select) has a boolean argument as its first operand.
355 // If we add more ternaries later, we need to change this check.
356 // But for now, it simplifies other checks, like checking for swapped
357 // operands.
358 if (!getElementTypeOrSelf(type: op.getDpsInputOperand(i: 0)->get().getType())
359 .isInteger(width: 1))
360 return false;
361
362 // Check all three inputs are used (elementwise).
363 OpOperand *inputOpOperand0 = op.getDpsInputOperand(i: 0);
364 OpOperand *inputOpOperand1 = op.getDpsInputOperand(i: 1);
365 OpOperand *inputOpOperand2 = op.getDpsInputOperand(i: 2);
366 return !(!op.payloadUsesValueFromOperand(opOperand: inputOpOperand0) ||
367 !op.payloadUsesValueFromOperand(opOperand: inputOpOperand1) ||
368 !op.payloadUsesValueFromOperand(opOperand: inputOpOperand2));
369}
370
371//===----------------------------------------------------------------------===//
372// ContractionOpInterface implementation
373//===----------------------------------------------------------------------===//
374
375/// If the value is defined by a chain of unary side effect-free, go up the
376/// use-def chain until the first value that isn't defined by such an op.
377// TODO: relax to multi-operands with constants, which are technically unary ops
378// as needed (e.g. add5).
379static Value getSourceSkipUnary(Value value) {
380 Operation *op = value.getDefiningOp();
381 while (op && op->getNumOperands() == 1) {
382 auto iface = dyn_cast<MemoryEffectOpInterface>(Val: op);
383 if (!iface || !iface.hasNoEffect())
384 break;
385 value = op->getOperand(idx: 0);
386 op = value.getDefiningOp();
387 }
388 return value;
389}
390
391bool mlir::linalg::detail::isContractionBody(
392 Block &block, function_ref<bool(Operation *, Operation *)> isaPair,
393 llvm::raw_ostream &errs) {
394 if (block.empty() || !block.back().mightHaveTrait<OpTrait::IsTerminator>()) {
395 errs << "no terminator in the block";
396 return false;
397 }
398
399 if (block.getNumArguments() != 3) {
400 errs << "expected block with 3 arguments";
401 return false;
402 }
403
404 Operation *terminator = block.getTerminator();
405 if (terminator->getNumOperands() != 1) {
406 errs << "expected terminator with 1 operand";
407 return false;
408 }
409
410 Value yielded = getSourceSkipUnary(value: terminator->getOperand(idx: 0));
411 Operation *reductionOp = yielded.getDefiningOp();
412 if (!reductionOp || reductionOp->getNumResults() != 1 ||
413 reductionOp->getNumOperands() != 2) {
414 errs << "expected reduction op to be binary";
415 return false;
416 }
417
418 Value reductionLHS = getSourceSkipUnary(value: reductionOp->getOperand(idx: 0));
419 Value reductionRHS = getSourceSkipUnary(value: reductionOp->getOperand(idx: 1));
420
421 if (reductionLHS != block.getArgument(i: 2) &&
422 reductionRHS != block.getArgument(i: 2)) {
423 errs << "expected reduction to take block argument #2 as one of the "
424 "operands (modulo unary casts)";
425 return false;
426 }
427
428 Value contributed = getSourceSkipUnary(
429 value: isa<BlockArgument>(Val: reductionLHS) ? reductionRHS : reductionLHS);
430 Operation *elementwiseOp = contributed.getDefiningOp();
431 if (!elementwiseOp || elementwiseOp->getNumResults() != 1 ||
432 elementwiseOp->getNumOperands() != 2) {
433 errs << "expected elementwise op to be binary";
434 return false;
435 }
436
437 if (!isaPair(elementwiseOp, reductionOp)) {
438 errs << "expected reduction/elementwise op kind not satisfied";
439 return false;
440 }
441
442 Value elementwiseLHS = getSourceSkipUnary(value: elementwiseOp->getOperand(idx: 0));
443 Value elementwiseRHS = getSourceSkipUnary(value: elementwiseOp->getOperand(idx: 1));
444 if ((elementwiseLHS == block.getArgument(i: 0) &&
445 elementwiseRHS == block.getArgument(i: 1)) ||
446 (elementwiseLHS == block.getArgument(i: 1) &&
447 elementwiseRHS == block.getArgument(i: 0))) {
448 return true;
449 }
450
451 errs << "expected elementwise op to apply to block arguments (modulo unary "
452 "casts)";
453 return false;
454}
455
456/// Returns true if the two operations are of the kinds specified by a pair of
457/// consecutive template arguments.
458template <typename AddOpTy, typename MulOpTy, typename... Args>
459static bool isPairTemplateImpl(Operation *add, Operation *mul) {
460 static_assert(sizeof...(Args) % 2 == 0,
461 "expected an even number of template arguments");
462 if (isa<AddOpTy>(add) && isa<MulOpTy>(mul))
463 return true;
464
465 if constexpr (sizeof...(Args) > 0)
466 return isPairTemplateImpl<Args...>(add, mul);
467 else
468 return false;
469}
470
471/// Returns true if the block is a body of a contraction with the kinds of
472/// operations given pairwise by template arguments.
473template <typename... Args>
474static bool isContractionBody(Block &block) {
475 return linalg::detail::isContractionBody(block, isaPair: &isPairTemplateImpl<Args...>);
476}
477
478/// Given an `indexingMap` and its corresponding `iterators`, returns
479/// the positions of the iterators of type `iter` that are indexed by
480/// the `indexingMap` as a permutation. This is useful to infer various
481/// subcomputations on a `LinalgOp`. This is performed by looking up
482/// each result in the `indexingMap` and determining whether:
483/// - It is a single AffineDimExpr.
484/// - It is the only result involving this AffineDimExpr.
485static llvm::SmallDenseSet<int64_t>
486findPermutationsIndexingOperand(AffineMap indexingMap,
487 ArrayRef<utils::IteratorType> iterators,
488 utils::IteratorType iter) {
489 assert(iterators.size() == indexingMap.getNumDims());
490 llvm::SmallDenseSet<int64_t> res;
491 for (AffineExpr e : indexingMap.getResults()) {
492 if (auto d = dyn_cast<AffineDimExpr>(Val&: e)) {
493 if (iterators[d.getPosition()] == iter &&
494 llvm::count_if(Range: indexingMap.getResults(), P: [d](AffineExpr e) {
495 return e.isFunctionOfDim(position: d.getPosition());
496 }) == 1)
497 res.insert(V: d.getPosition());
498 }
499 }
500 return res;
501}
502
503namespace {
504auto par = utils::IteratorType::parallel;
505auto red = utils::IteratorType::reduction;
506} // namespace
507
508/// Infer the iterator types from the init affine map. This looks at which dims
509/// are present in the map results, and returns an iterator types array with
510/// parallel types for dims that are present, and reduction types for dims that
511/// are not present.
512static FailureOr<SmallVector<utils::IteratorType>>
513inferIteratorsFromOutMap(AffineMap map) {
514 if (!map.isProjectedPermutation())
515 return failure();
516 SmallVector<utils::IteratorType> iterators(map.getNumDims(), red);
517 for (auto expr : map.getResults())
518 if (auto dim = dyn_cast<AffineDimExpr>(Val&: expr))
519 iterators[dim.getPosition()] = par;
520 return iterators;
521}
522
523/// Find 2 parallel (m and n) and 1 reduction (k) dimension candidates that form
524/// a matmul subcomputation within `linalgOp`. These dimensions are such that:
525/// 1. The m dimension is involved in an outer-product along LHS
526/// (i.e. it is a permutation on RES and LHS and does not appear in RHS).
527/// 2. The n dimension is involved in an outer-product along RHS
528/// (i.e. it is a permutation on RES and RHS and does not appear in LHS).
529/// 3. The k dimension appears as a permutation on LHS and RHS.
530/// 4. m, n and k appear only once in any given indexing.
531/// 5. Optional batch dimensions that appear in all operands are captured.
532/// This allows e.g. detecting that some contraction is embedded within
533/// `linalgOp` with some orthogonal heuristic.
534static FailureOr<ContractionDimensions>
535inferContractionDimsImpl(ArrayRef<AffineMap> indexingMaps,
536 ArrayRef<utils::IteratorType> iterators) {
537 llvm::SmallDenseSet<int64_t> a =
538 findPermutationsIndexingOperand(indexingMap: indexingMaps[0], iterators, iter: par);
539 llvm::SmallDenseSet<int64_t> b =
540 findPermutationsIndexingOperand(indexingMap: indexingMaps[1], iterators, iter: par);
541 llvm::SmallDenseSet<int64_t> c =
542 findPermutationsIndexingOperand(indexingMap: indexingMaps[2], iterators, iter: par);
543
544 // A & C - B are the iterators involved in an outer-product along A (the LHS).
545 llvm::SmallDenseSet<int64_t> ac = a;
546 llvm::set_intersect(S1&: ac, S2: c);
547 llvm::set_subtract(S1&: ac, S2: b);
548 // B & C - A are the iterators involved in an outer-product along B (the RHS).
549 llvm::SmallDenseSet<int64_t> bc = b;
550 llvm::set_intersect(S1&: bc, S2: c);
551 llvm::set_subtract(S1&: bc, S2: a);
552 // A & B & C are the "batch" dimensions.
553 llvm::SmallDenseSet<int64_t> batches = a;
554 llvm::set_intersect(S1&: batches, S2: b);
555 llvm::set_intersect(S1&: batches, S2: c);
556
557 // A & B red are the reduction dimensions.
558 llvm::SmallDenseSet<int64_t> ra =
559 findPermutationsIndexingOperand(indexingMap: indexingMaps[0], iterators, iter: red);
560 llvm::SmallDenseSet<int64_t> rb =
561 findPermutationsIndexingOperand(indexingMap: indexingMaps[1], iterators, iter: red);
562 llvm::set_intersect(S1&: ra, S2: rb);
563
564 // Return each set in sorted order.
565 ContractionDimensions dimensions{
566 .batch: SmallVector<unsigned, 2>(batches.begin(), batches.end()),
567 .m: SmallVector<unsigned, 2>(ac.begin(), ac.end()),
568 .n: SmallVector<unsigned, 2>(bc.begin(), bc.end()),
569 .k: SmallVector<unsigned, 2>(ra.begin(), ra.end())};
570 llvm::sort(C&: dimensions.batch);
571 llvm::sort(C&: dimensions.m);
572 llvm::sort(C&: dimensions.n);
573 llvm::sort(C&: dimensions.k);
574 return dimensions;
575}
576
577FailureOr<ContractionDimensions>
578mlir::linalg::inferContractionDims(LinalgOp linalgOp) {
579 if (linalgOp.getNumDpsInits() != 1 || linalgOp.getNumDpsInputs() != 2)
580 return failure();
581 return inferContractionDimsImpl(indexingMaps: linalgOp.getIndexingMapsArray(),
582 iterators: linalgOp.getIteratorTypesArray());
583}
584
585FailureOr<ContractionDimensions>
586mlir::linalg::inferContractionDims(ArrayRef<AffineMap> indexingMaps) {
587 if (indexingMaps.size() != 3)
588 return failure();
589 auto iterators = inferIteratorsFromOutMap(map: indexingMaps[2]);
590 if (failed(Result: iterators))
591 return failure();
592 return inferContractionDimsImpl(indexingMaps, iterators: iterators.value());
593}
594
595namespace mlir::linalg::detail {
596enum class MatchContractionResult {
597 Success = 0,
598 NotLinalgOp,
599 WrongNumOperands,
600 NoReduction,
601 NotProjectedPermutations,
602 NotAddMul
603};
604} // namespace mlir::linalg::detail
605
606mlir::linalg::detail::MatchContractionResult
607mlir::linalg::detail::isContractionInterfaceImpl(
608 Operation *op, mlir::linalg::ContractionDimensions *dimensions) {
609 auto linalgOp = dyn_cast<linalg::LinalgOp>(Val: op);
610 if (!linalgOp)
611 return MatchContractionResult::NotLinalgOp;
612 if (linalgOp.getNumDpsInputs() != 2 || linalgOp.getNumDpsInits() != 1)
613 return MatchContractionResult::WrongNumOperands;
614 auto mapRange = linalgOp.getIndexingMapsArray();
615 if (linalgOp.getNumReductionLoops() == 0)
616 return MatchContractionResult::NoReduction;
617 if (llvm::any_of(Range&: mapRange,
618 P: [](AffineMap m) { return !m.isProjectedPermutation(); }))
619 return MatchContractionResult::NotProjectedPermutations;
620
621 // Inputs may be cast to the accumulator type inside the body (mixed
622 // precision, int<->float), so the init element type alone selects which
623 // mul/add pair the contraction must use.
624 Type accType =
625 getElementTypeOrSelf(type: linalgOp.getDpsInitOperand(i: 0)->get().getType());
626 Block &body = *linalgOp.getBlock();
627 bool isContraction = false;
628 if (accType.isInteger(width: 1))
629 isContraction = ::isContractionBody<arith::AndIOp, arith::OrIOp>(block&: body);
630 else if (isa<IntegerType>(Val: accType))
631 isContraction = ::isContractionBody<arith::MulIOp, arith::AddIOp>(block&: body);
632 else if (isa<FloatType>(Val: accType))
633 isContraction = ::isContractionBody<arith::MulFOp, arith::AddFOp>(block&: body);
634 else if (isa<ComplexType>(Val: accType))
635 isContraction = ::isContractionBody<complex::MulOp, complex::AddOp>(block&: body);
636 if (!isContraction)
637 return MatchContractionResult::NotAddMul;
638
639 if (dimensions) {
640 FailureOr<ContractionDimensions> res = inferContractionDims(linalgOp);
641 assert(succeeded(res) && "unexpected failure to infer contraction dims");
642 *dimensions = *res;
643 }
644 return MatchContractionResult::Success;
645}
646
647StringRef
648mlir::linalg::detail::getMatchContractionMessage(MatchContractionResult res) {
649 switch (res) {
650 case MatchContractionResult::NotLinalgOp:
651 return "expected a LinalgOp";
652 case MatchContractionResult::WrongNumOperands:
653 return "expected op with 2 inputs and 1 output";
654 case MatchContractionResult::NoReduction:
655 return "expected at least 1 reduction";
656 case MatchContractionResult::NotProjectedPermutations:
657 return "expected indexing maps to be projected permutations";
658 case MatchContractionResult::NotAddMul:
659 return "expected add/mul op in the body";
660 case MatchContractionResult::Success:
661 return "";
662 }
663 llvm_unreachable("unhandled MatchContractionResult case");
664}
665
666bool mlir::linalg::isaContractionOpInterface(LinalgOp linalgOp) {
667 if (!linalgOp)
668 return false;
669 Operation *op = linalgOp.getOperation();
670 return isa<ContractionOpInterface>(Val: op) ||
671 (mlir::linalg::detail::isContractionInterfaceImpl(op) ==
672 mlir::linalg::detail::MatchContractionResult::Success);
673}
674
675/// Verify that a LinalgOp `op` is a contraction.
676/// A Linalg contraction is defined in general terms:
677/// 1. Has 2 input and 1 output shapes.
678/// 2. Has at least one reduction dimension.
679/// 3. Has only projected permutation indexing maps.
680/// 4. its body computes `u5(u1(c) + u2(u3(a) * u4(b)))` on some field
681/// (AddOpType, MulOpType), where u1, u2, u3, u4 and u5 represent scalar unary
682/// operations that may change the type (e.g. for mixed-precision).
683/// As a consequence, when vectorization of such an op occurs, the only special
684/// behavior is that the (unique) MulOpType is vectorized into a
685/// `vector.contract`. All other ops are handled in a generic fashion.
686/// In the future, we may wish to allow more input arguments and elementwise and
687/// constant operations that do not involve the reduction dimension(s).
688LogicalResult mlir::linalg::detail::verifyContractionInterface(Operation *op) {
689 auto res = isContractionInterfaceImpl(op);
690 if (res != MatchContractionResult::Success)
691 return op->emitError(message: getMatchContractionMessage(res));
692 return success();
693}
694
695//===----------------------------------------------------------------------===//
696// ConvolutionOpInterface implementation
697//===----------------------------------------------------------------------===//
698
699/// Of the given two expressions returns one that is of type T (`lhs` gets
700/// preference over `rhs`)
701template <typename T>
702static T getAffineExprOfType(AffineExpr lhs, AffineExpr rhs) {
703 return isa<T>(lhs) ? cast<T>(lhs) : (isa<T>(rhs) ? cast<T>(rhs) : nullptr);
704}
705
706namespace {
707/// Walk the indexing expressions for input of a convolution operation to verify
708/// its of the right form, either
709/// - AffineDimExpr
710/// - AffineDimExpr (`*` (AffineSymbolExpr | AffineConstantExpr))?
711/// (`+` AffineDimExpr (`*` (AffineSymbolExpr | AffineConstantExpr))?)*
712///
713/// classifies the AffineDimExpr as convolved dimensions or unconvolved
714/// dimensions and verifies each dimension occurs only once.
715struct ConvAccessExprWalker
716 : public AffineExprVisitor<ConvAccessExprWalker, LogicalResult> {
717 // Stores dimensions used in expressions of the above form.
718 llvm::SmallDenseSet<int64_t> convolvedDims;
719 // Stores the dual mapping between LHS and RHS of convolution exprs.
720 llvm::SmallDenseMap<int64_t, int64_t> convolvedDimMapping;
721 // Stores single use dimensions used by an AffineDimExpr.
722 llvm::SmallDenseSet<int64_t> unConvolvedDims;
723 // Stores a mapping from convolved dims to their coefficient.
724 llvm::SmallDenseMap<int64_t, AffineExpr> strideAndDilationMapping;
725
726 // Removes dims with multiple uses in the source input map from dimension
727 // sets tracked by this walker.
728 void clearMultiUseDims(AffineMap map) {
729 for (int dimPos = 0, e = map.getNumDims(); dimPos < e; ++dimPos) {
730 if (llvm::count_if(Range: map.getResults(), P: [dimPos](AffineExpr e) {
731 return e.isFunctionOfDim(position: dimPos);
732 }) > 1) {
733 convolvedDims.erase(V: dimPos);
734 unConvolvedDims.erase(V: dimPos);
735 // If a duplicate dim is marked as convolved, the pair of the duplicate
736 // dim must be removed from the map as well.
737 auto it = convolvedDimMapping.find(Val: dimPos);
738 if (it != convolvedDimMapping.end()) {
739 int64_t pairedDim = it->second;
740 convolvedDims.erase(V: pairedDim);
741 unConvolvedDims.erase(V: pairedDim);
742 strideAndDilationMapping.erase(Val: pairedDim);
743 convolvedDimMapping.erase(Val: dimPos);
744 convolvedDimMapping.erase(Val: pairedDim);
745 }
746 }
747 }
748 }
749
750 LogicalResult visitDimExpr(AffineDimExpr dimExpr) {
751 unsigned position = dimExpr.getPosition();
752 if (unConvolvedDims.count(V: position) || convolvedDims.count(V: position)) {
753 return failure();
754 }
755 unConvolvedDims.insert(V: position);
756 return success();
757 }
758
759 LogicalResult visitSymbolExpr(AffineSymbolExpr expr) { return failure(); }
760
761 LogicalResult visitConstantExpr(AffineConstantExpr expr) { return failure(); }
762
763 LogicalResult visitAffineBinaryOpExpr(AffineBinaryOpExpr binaryExpr) {
764 // In pre-order visit, top level op has to be an add op.
765 if (binaryExpr.getKind() != AffineExprKind::Add)
766 return failure();
767 auto lhsDimPos = getDimExprOrMulExprDimPos(expr: binaryExpr.getLHS());
768 auto rhsDimPos = getDimExprOrMulExprDimPos(expr: binaryExpr.getRHS());
769 if (failed(Result: lhsDimPos) || failed(Result: rhsDimPos))
770 return failure();
771 convolvedDimMapping[*lhsDimPos] = *rhsDimPos;
772 convolvedDimMapping[*rhsDimPos] = *lhsDimPos;
773 return success();
774 }
775
776 FailureOr<int64_t> getDimExprOrMulExprDimPos(AffineExpr expr) {
777 if (auto dimExpr = dyn_cast<AffineDimExpr>(Val&: expr)) {
778 int64_t dim = dimExpr.getPosition();
779 if (convolvedDims.count(V: dim) || unConvolvedDims.count(V: dim))
780 return failure();
781 // Stride/dilation for this dim is implicitly 1.
782 strideAndDilationMapping[dim] =
783 getAffineConstantExpr(constant: 1, context: expr.getContext());
784 convolvedDims.insert(V: dim);
785 return dim;
786 }
787 if (auto symbolMulExpr = dyn_cast<AffineBinaryOpExpr>(Val&: expr)) {
788 if (symbolMulExpr.getKind() != AffineExprKind::Mul)
789 return failure();
790 auto lhsExpr = symbolMulExpr.getLHS();
791 auto rhsExpr = symbolMulExpr.getRHS();
792 // Check for symbol expression.
793 AffineExpr mulExpr =
794 getAffineExprOfType<AffineSymbolExpr>(lhs: lhsExpr, rhs: rhsExpr);
795 // If there was no symbol expr, check for constant expression.
796 if (!mulExpr) {
797 mulExpr = getAffineExprOfType<AffineConstantExpr>(lhs: lhsExpr, rhs: rhsExpr);
798 }
799 auto dimExpr = getAffineExprOfType<AffineDimExpr>(lhs: lhsExpr, rhs: rhsExpr);
800 if (!mulExpr || !dimExpr)
801 return failure();
802 int64_t dim = dimExpr.getPosition();
803 if (convolvedDims.count(V: dim) || unConvolvedDims.count(V: dim))
804 return failure();
805 strideAndDilationMapping[dim] = mulExpr;
806 convolvedDims.insert(V: dim);
807 return dim;
808 }
809 return failure();
810 }
811};
812} // namespace
813
814static llvm::SmallDenseSet<int64_t> getPreservedDims(AffineMap map) {
815 assert(map.isProjectedPermutation() &&
816 "expected map to have projected permutations");
817 llvm::SmallDenseSet<int64_t> preservedDims;
818 for (auto expr : map.getResults())
819 preservedDims.insert(V: cast<AffineDimExpr>(Val&: expr).getPosition());
820 return preservedDims;
821}
822
823static SmallVector<int64_t, 2>
824getConstantsFromExprList(const SmallVector<AffineExpr, 2> &exprs) {
825 SmallVector<int64_t, 2> vals;
826 for (auto e : exprs) {
827 auto constantExpr = dyn_cast<AffineConstantExpr>(Val&: e);
828 assert(constantExpr && "Found non-constant stride/dilation");
829 vals.push_back(Elt: constantExpr.getValue());
830 }
831 return vals;
832}
833
834/// Classifies dimensions in the `indexingMaps` used by a convolution
835/// subcomputation, as captured by `inputExprWalker`. If
836/// `allowEmptyConvolvedDims` is not set this will fail if there is not
837/// at least one convolved dimension pair (output image + filter loop).
838///
839/// The returned dimensions are ordered as follows:
840/// - `outputImage` is sorted by dimension index.
841/// - `filterLoop` is ordered to match the pairing with `outputImage`, i.e.,
842/// `outputImage[i]` and `filterLoop[i]` are paired dimensions from the
843/// convolution access pattern (e.g., `oh + kh` pairs `oh` with `kh`).
844/// - `strides[i]` corresponds to `outputImage[i]`.
845/// - `dilations[i]` corresponds to `filterLoop[i]`.
846/// - Other dimension sets (batch, outputChannel, etc.) are sorted by index.
847///
848/// `nativeStrides` and `nativeDilations`, when non-null, are the op-carried
849/// `strides`/`dilations` attributes and take precedence over the values derived
850/// from the convolution access pattern. They are null for the maps-based
851/// overload.
852static FailureOr<ConvolutionDimensions> inferConvolutionDimsImpl(
853 ArrayRef<AffineMap> indexingMaps, ArrayRef<utils::IteratorType> iterators,
854 ConvAccessExprWalker &inputExprWalker, bool allowEmptyConvolvedDims,
855 DenseIntElementsAttr nativeStrides, DenseIntElementsAttr nativeDilations) {
856 AffineMap filterMap = indexingMaps[1];
857 AffineMap outputMap = indexingMaps.back();
858 llvm::SmallDenseSet<int64_t> filterDims =
859 findPermutationsIndexingOperand(indexingMap: filterMap, iterators, iter: par);
860 llvm::SmallDenseSet<int64_t> outputDims =
861 findPermutationsIndexingOperand(indexingMap: outputMap, iterators, iter: par);
862
863 // unConvolvedDims & outputDims - filterDims are the batch iterators.
864 llvm::SmallDenseSet<int64_t> batch = inputExprWalker.unConvolvedDims;
865 llvm::set_intersect(S1&: batch, S2: outputDims);
866 llvm::set_subtract(S1&: batch, S2: filterDims);
867
868 // convolvedDims & outputDims are the output image iterators.
869 llvm::SmallDenseSet<int64_t> oi = inputExprWalker.convolvedDims;
870 llvm::set_intersect(S1&: oi, S2: outputDims);
871
872 // filterDims & outputDims - unConvolvedDims are the output channel iterators.
873 llvm::SmallDenseSet<int64_t> oc = filterDims;
874 llvm::set_intersect(S1&: oc, S2: outputDims);
875 llvm::set_subtract(S1&: oc, S2: inputExprWalker.unConvolvedDims);
876
877 // filterDims & outputDims & unConvolvedDims are the depth iterators.
878 llvm::SmallDenseSet<int64_t> depth = filterDims;
879 llvm::set_intersect(S1&: depth, S2: outputDims);
880 llvm::set_intersect(S1&: depth, S2: inputExprWalker.unConvolvedDims);
881
882 llvm::SmallDenseSet<int64_t> filterReducedDims =
883 findPermutationsIndexingOperand(indexingMap: filterMap, iterators, iter: red);
884
885 // convolvedDims & filterReducedDims are the filter loop iterators.
886 llvm::SmallDenseSet<int64_t> fl = inputExprWalker.convolvedDims;
887 llvm::set_intersect(S1&: fl, S2: filterReducedDims);
888
889 // unConvolvedDims & filterReducedDims are the input channel iterators.
890 llvm::SmallDenseSet<int64_t> ic = inputExprWalker.unConvolvedDims;
891 llvm::set_intersect(S1&: ic, S2: filterReducedDims);
892
893 if (oi.empty() && !allowEmptyConvolvedDims)
894 return failure();
895
896 // Return each set in sorted order, with outputImage and filterLoop
897 // ordered so that outputImage[i] pairs with filterLoop[i].
898 ConvolutionDimensions dimensions{
899 .batch: SmallVector<unsigned, 2>(batch.begin(), batch.end()),
900 .outputImage: SmallVector<unsigned, 2>(oi.begin(), oi.end()),
901 .outputChannel: SmallVector<unsigned, 2>(oc.begin(), oc.end()),
902 /*filterLoop=*/SmallVector<unsigned, 2>{},
903 .inputChannel: SmallVector<unsigned, 2>(ic.begin(), ic.end()),
904 .depth: SmallVector<unsigned, 2>(depth.begin(), depth.end()),
905 /*strides=*/SmallVector<int64_t, 2>{},
906 /*dilations=*/SmallVector<int64_t, 2>{}};
907 llvm::sort(C&: dimensions.batch);
908 llvm::sort(C&: dimensions.outputImage);
909 llvm::sort(C&: dimensions.outputChannel);
910 llvm::sort(C&: dimensions.inputChannel);
911 llvm::sort(C&: dimensions.depth);
912 // Order filterLoop to match the pairing with outputImage. Each outputImage
913 // dimension has a corresponding filterLoop dimension from the convolution
914 // access pattern (e.g., oh + kh). This ensures outputImage[i] pairs with
915 // filterLoop[i].
916 for (unsigned oiDim : dimensions.outputImage)
917 dimensions.filterLoop.push_back(Elt: inputExprWalker.convolvedDimMapping[oiDim]);
918
919 // Use the op carried strides/dilations attribute if present.
920 if (!nativeStrides) {
921 SmallVector<AffineExpr, 2> strideExprs;
922 for (unsigned oiDim : dimensions.outputImage)
923 strideExprs.push_back(Elt: inputExprWalker.strideAndDilationMapping[oiDim]);
924 dimensions.strides = getConstantsFromExprList(exprs: strideExprs);
925 } else {
926 dimensions.strides = llvm::to_vector<2>(Range: nativeStrides.getValues<int64_t>());
927 }
928 if (!nativeDilations) {
929 SmallVector<AffineExpr, 2> dilationExprs;
930 for (unsigned flDim : dimensions.filterLoop)
931 dilationExprs.push_back(Elt: inputExprWalker.strideAndDilationMapping[flDim]);
932 dimensions.dilations = getConstantsFromExprList(exprs: dilationExprs);
933 } else {
934 dimensions.dilations =
935 llvm::to_vector<2>(Range: nativeDilations.getValues<int64_t>());
936 }
937 return dimensions;
938}
939
940static DenseIntElementsAttr getInherentConvolutionAttr(LinalgOp linalgOp,
941 StringRef name) {
942 return dyn_cast_or_null<DenseIntElementsAttr>(
943 Val: linalgOp->getInherentAttr(name).value_or(u: Attribute{}));
944}
945
946/// Find at least 1 parallel (output_image) and reduction (filter_loop)
947/// dimension candidates that form a convolution subcomputation within
948/// `linalgOp`. The LHS is assumed to be the convolution input while the
949/// RHS is assumed as the filter.
950/// These dimensions are such that:
951/// 1. Optional batch dimensions that appear in the input and filter.
952/// 2. The output_image dimension is involved in a cross-correlation along LHS
953/// (i.e. it is a permutation on RES and LHS and has an associated
954/// filter_loop in RHS).
955/// 3. Optional output_channel dimension is involved in an outer-product along
956/// RHS (i.e. it is a permutation on RES and RHS and does not appear in
957/// LHS).
958/// 4. Optional input_channel dimension appears as a permutation on LHS and
959/// RHS.
960/// 5. The filter_loop dimension appears as a permutation on the RHS and
961/// represents the shape of the kernel cross-correlated along a
962/// corresponding output_image dim.
963/// 6. The input_channel dimension appears as a permutation on LHS and RHS.
964/// 7. All dimensions appear only once in any given indexing map.
965/// This allows e.g. detecting that some convolution is embedded within
966/// `linalgOp` with some orthogonal heuristic.
967///
968/// The `outputImage` and `filterLoop` arrays are ordered such that
969/// `outputImage[i]` pairs with `filterLoop[i]` based on the convolution access
970/// pattern in the input indexing map (e.g., `d0 + d2` pairs dimension 0 with
971/// dimension 2). Other dimension sets are returned in sorted order.
972///
973/// Returns a failure if `output_image` (and implicitly `filter_loop`) is empty.
974FailureOr<ConvolutionDimensions>
975mlir::linalg::inferConvolutionDims(LinalgOp linalgOp) {
976 if (linalgOp.getNumDpsInits() != 1 || linalgOp.getNumDpsInputs() != 2)
977 return failure();
978
979 auto indexingMaps = linalgOp.getIndexingMapsArray();
980
981 // Check the input indexing map has the right form.
982 ConvAccessExprWalker inputExprWalker;
983 for (AffineExpr expr : indexingMaps[0].getResults())
984 (void)inputExprWalker.visit(expr);
985 inputExprWalker.clearMultiUseDims(map: indexingMaps[0]);
986
987 return inferConvolutionDimsImpl(
988 indexingMaps, iterators: linalgOp.getIteratorTypesArray(), inputExprWalker,
989 /*allowEmptyConvolvedDims=*/false,
990 nativeStrides: getInherentConvolutionAttr(linalgOp, name: "strides"),
991 nativeDilations: getInherentConvolutionAttr(linalgOp, name: "dilations"));
992}
993
994FailureOr<ConvolutionDimensions>
995mlir::linalg::inferConvolutionDims(ArrayRef<AffineMap> indexingMaps) {
996 if (indexingMaps.size() != 3)
997 return failure();
998
999 // Infer iterator types from the output map.
1000 FailureOr<SmallVector<utils::IteratorType>> iterators =
1001 inferIteratorsFromOutMap(map: indexingMaps[2]);
1002 if (failed(Result: iterators))
1003 return failure();
1004
1005 // Check the input indexing map has the right form.
1006 ConvAccessExprWalker inputExprWalker;
1007 for (AffineExpr expr : indexingMaps[0].getResults())
1008 (void)inputExprWalker.visit(expr);
1009 inputExprWalker.clearMultiUseDims(map: indexingMaps[0]);
1010
1011 return inferConvolutionDimsImpl(indexingMaps, iterators: iterators.value(),
1012 inputExprWalker,
1013 /*allowEmptyConvolvedDims=*/false,
1014 /*nativeStrides=*/nullptr,
1015 /*nativeDilations=*/nullptr);
1016}
1017
1018namespace mlir::linalg::detail {
1019enum class MatchConvolutionResult {
1020 Success = 0,
1021 NotLinalgOp,
1022 WrongNumOperands,
1023 WrongInputIndexingMap,
1024 NotProjectedPermutations,
1025 NonConvolutionLoop,
1026 OutputDimsNotParallel,
1027 NonOutputDimNotReduction,
1028 EmptyConvolvedDims
1029};
1030} // namespace mlir::linalg::detail
1031
1032mlir::linalg::detail::MatchConvolutionResult
1033mlir::linalg::detail::isConvolutionInterfaceImpl(
1034 Operation *op, ConvolutionDimensions *dimensions,
1035 bool allowEmptyConvolvedDims) {
1036 auto linalgOp = dyn_cast<linalg::LinalgOp>(Val: op);
1037 if (!linalgOp)
1038 return MatchConvolutionResult::NotLinalgOp;
1039 if (linalgOp.getNumDpsInputs() < 2 || linalgOp.getNumDpsInits() != 1)
1040 return MatchConvolutionResult::WrongNumOperands;
1041
1042 auto indexingMaps = linalgOp.getIndexingMapsArray();
1043
1044 // Check the input indexing map has the right form.
1045 ConvAccessExprWalker inputExprWalker;
1046 if (llvm::any_of(Range: indexingMaps[0].getResults(),
1047 P: [&inputExprWalker](AffineExpr expr) {
1048 return failed(Result: inputExprWalker.visit(expr));
1049 })) {
1050 return MatchConvolutionResult::WrongInputIndexingMap;
1051 }
1052
1053 // Filter and output maps must be projected permutation.
1054 if (!indexingMaps[1].isProjectedPermutation() ||
1055 !indexingMaps.back().isProjectedPermutation())
1056 return MatchConvolutionResult::NotProjectedPermutations;
1057
1058 auto iteratorTypes = linalgOp.getIteratorTypesArray();
1059
1060 llvm::SmallDenseSet<int64_t> outputDims =
1061 getPreservedDims(map: indexingMaps.back());
1062 llvm::SmallDenseSet<int64_t> filterDims = getPreservedDims(map: indexingMaps[1]);
1063 // Make sure all loops are characterized as one of:
1064 // - Batch loop : present in output, as non-convolved in input, not present in
1065 // filter.
1066 // - Output image dimension : present in output, convolved dims in input, not
1067 // present in filter.
1068 // - Output channel dimension : present in output, not present in input,
1069 // present in filter.
1070 // - Filter loop dimension : present in filter, convolved in input, not
1071 // present in output.
1072 // - Input channel dimension : unconvolved in input, not present in output,
1073 // present in filter.
1074 // - Depth multiplier : unconvolved in input, present in output, present in
1075 // filter.
1076 llvm::SmallDenseSet<int64_t> allLoopDims;
1077 for (auto outputExpr : indexingMaps.back().getResults()) {
1078 int64_t outputDim = cast<AffineDimExpr>(Val&: outputExpr).getPosition();
1079 if (inputExprWalker.unConvolvedDims.count(V: outputDim) &&
1080 !filterDims.count(V: outputDim)) {
1081 // Batch dimension.
1082 if (iteratorTypes[outputDim] != utils::IteratorType::parallel)
1083 return MatchConvolutionResult::OutputDimsNotParallel;
1084 allLoopDims.insert(V: outputDim);
1085 continue;
1086 }
1087 if (inputExprWalker.convolvedDims.count(V: outputDim) &&
1088 !filterDims.count(V: outputDim)) {
1089 // Output image Loop dimension.
1090 if (iteratorTypes[outputDim] != utils::IteratorType::parallel)
1091 return MatchConvolutionResult::OutputDimsNotParallel;
1092 allLoopDims.insert(V: outputDim);
1093 continue;
1094 }
1095 if (!inputExprWalker.convolvedDims.count(V: outputDim) &&
1096 !inputExprWalker.unConvolvedDims.count(V: outputDim) &&
1097 filterDims.count(V: outputDim)) {
1098 // Output channel dimension.
1099 if (iteratorTypes[outputDim] != utils::IteratorType::parallel)
1100 return MatchConvolutionResult::OutputDimsNotParallel;
1101 allLoopDims.insert(V: outputDim);
1102 continue;
1103 }
1104 if (inputExprWalker.unConvolvedDims.count(V: outputDim) &&
1105 filterDims.count(V: outputDim)) {
1106 // Depth multiplier.
1107 if (iteratorTypes[outputDim] != utils::IteratorType::parallel)
1108 return MatchConvolutionResult::OutputDimsNotParallel;
1109 allLoopDims.insert(V: outputDim);
1110 continue;
1111 }
1112 return MatchConvolutionResult::NonConvolutionLoop;
1113 }
1114 for (auto filterExpr : indexingMaps[1].getResults()) {
1115 int64_t filterDim = cast<AffineDimExpr>(Val&: filterExpr).getPosition();
1116 if (outputDims.count(V: filterDim) &&
1117 !inputExprWalker.unConvolvedDims.count(V: filterDim) &&
1118 !inputExprWalker.convolvedDims.count(V: filterDim)) {
1119 // Output channel dimension. This is already seen, continue;
1120 continue;
1121 }
1122 if (inputExprWalker.convolvedDims.count(V: filterDim) &&
1123 !outputDims.count(V: filterDim)) {
1124 // Filter loop dimension.
1125 if (iteratorTypes[filterDim] != utils::IteratorType::reduction)
1126 return MatchConvolutionResult::NonOutputDimNotReduction;
1127 if (allLoopDims.count(V: filterDim))
1128 return MatchConvolutionResult::NonConvolutionLoop;
1129 allLoopDims.insert(V: filterDim);
1130 continue;
1131 }
1132 if (inputExprWalker.unConvolvedDims.count(V: filterDim) &&
1133 !outputDims.count(V: filterDim)) {
1134 // Input channel dimension.
1135 if (iteratorTypes[filterDim] != utils::IteratorType::reduction)
1136 return MatchConvolutionResult::NonOutputDimNotReduction;
1137 if (allLoopDims.count(V: filterDim))
1138 return MatchConvolutionResult::NonConvolutionLoop;
1139 allLoopDims.insert(V: filterDim);
1140 continue;
1141 }
1142 if (inputExprWalker.unConvolvedDims.count(V: filterDim) &&
1143 outputDims.count(V: filterDim)) {
1144 // Depthwise loop. Already seen.
1145 continue;
1146 }
1147 return MatchConvolutionResult::NonConvolutionLoop;
1148 }
1149 // All loops must be covered now.
1150 if (allLoopDims.size() != linalgOp.getNumLoops())
1151 return MatchConvolutionResult::NonConvolutionLoop;
1152
1153 if (!allowEmptyConvolvedDims && inputExprWalker.convolvedDims.empty())
1154 return MatchConvolutionResult::EmptyConvolvedDims;
1155
1156 if (dimensions) {
1157 FailureOr<ConvolutionDimensions> res = inferConvolutionDimsImpl(
1158 indexingMaps, iterators: iteratorTypes, inputExprWalker, allowEmptyConvolvedDims,
1159 nativeStrides: getInherentConvolutionAttr(linalgOp, name: "strides"),
1160 nativeDilations: getInherentConvolutionAttr(linalgOp, name: "dilations"));
1161 assert(succeeded(res) && "unexpected failure to infer convolution dims");
1162 *dimensions = *res;
1163 }
1164
1165 return MatchConvolutionResult::Success;
1166}
1167
1168StringRef
1169mlir::linalg::detail::getMatchConvolutionMessage(MatchConvolutionResult res) {
1170 switch (res) {
1171 case MatchConvolutionResult::NotLinalgOp:
1172 return "expected a LinalgOp";
1173 case MatchConvolutionResult::WrongNumOperands:
1174 return "expected op with 2 inputs and 1 output";
1175 case MatchConvolutionResult::WrongInputIndexingMap:
1176 return "unexpected input index map for convolutions";
1177 case MatchConvolutionResult::NotProjectedPermutations:
1178 return "expected output/filter indexing maps to be projected permutations";
1179 case MatchConvolutionResult::NonConvolutionLoop:
1180 return "unexpected loop dimension for convolution op";
1181 case MatchConvolutionResult::OutputDimsNotParallel:
1182 return "expected all iterators used to access outputs to be parallel";
1183 case MatchConvolutionResult::NonOutputDimNotReduction:
1184 return "expected all iterators not used to access outputs to be reduction";
1185 case MatchConvolutionResult::EmptyConvolvedDims:
1186 return "expected convolved dim to be non-empty";
1187 case MatchConvolutionResult::Success:
1188 return "";
1189 }
1190 llvm_unreachable("unhandled MatchConvolutionResult case");
1191}
1192
1193bool mlir::linalg::isaConvolutionOpInterface(LinalgOp linalgOp,
1194 bool allowEmptyConvolvedDims) {
1195 return linalg::detail::isConvolutionInterfaceImpl(
1196 op: linalgOp.getOperation(), dimensions: nullptr, allowEmptyConvolvedDims) ==
1197 linalg::detail::MatchConvolutionResult::Success;
1198}
1199
1200LogicalResult mlir::linalg::detail::verifyConvolutionInterface(Operation *op) {
1201 MatchConvolutionResult res = isConvolutionInterfaceImpl(op);
1202 if (res != MatchConvolutionResult::Success)
1203 return op->emitError(message: getMatchConvolutionMessage(res));
1204 return success();
1205}
1206
1207//===----------------------------------------------------------------------===//
1208// FillOpInterface implementation
1209//===----------------------------------------------------------------------===//
1210
1211namespace {
1212enum class MatchFillResult {
1213 Success = 0,
1214 NotLinalgOp,
1215 WrongNumOperands,
1216 NotScalarInput,
1217 TypeMismatch
1218};
1219} // namespace
1220
1221static MatchFillResult isFillInterfaceImpl(Operation *op) {
1222 auto linalgOp = dyn_cast<linalg::LinalgOp>(Val: op);
1223 if (!linalgOp)
1224 return MatchFillResult::NotLinalgOp;
1225 if (linalgOp.getNumDpsInputs() != 1 || linalgOp.getNumDpsInits() != 1)
1226 return MatchFillResult::WrongNumOperands;
1227
1228 OpOperand *value = linalgOp.getDpsInputOperand(i: 0);
1229 if (!linalgOp.isScalar(opOperand: value))
1230 return MatchFillResult::NotScalarInput;
1231
1232 // Check that the scalar input type matches the output element type.
1233 OpOperand *output = linalgOp.getDpsInitOperand(i: 0);
1234 Type scalarType = value->get().getType();
1235 Type outputElementType = getElementTypeOrSelf(type: output->get().getType());
1236 if (scalarType != outputElementType)
1237 return MatchFillResult::TypeMismatch;
1238
1239 return MatchFillResult::Success;
1240}
1241
1242LogicalResult mlir::linalg::detail::verifyFillInterface(Operation *op) {
1243 MatchFillResult res = isFillInterfaceImpl(op);
1244 if (res == MatchFillResult::NotLinalgOp)
1245 return op->emitError(message: "expected a LinalgOp");
1246 if (res == MatchFillResult::WrongNumOperands)
1247 return op->emitError(message: "expected op with 1 input and 1 output");
1248 if (res == MatchFillResult::NotScalarInput)
1249 return op->emitError(message: "expected op with scalar input");
1250 if (res == MatchFillResult::TypeMismatch) {
1251 auto linalgOp = cast<linalg::LinalgOp>(Val: op);
1252 Type scalarType = linalgOp.getDpsInputOperand(i: 0)->get().getType();
1253 Type outputElementType =
1254 getElementTypeOrSelf(type: linalgOp.getDpsInitOperand(i: 0)->get().getType());
1255 return op->emitOpError(message: "expected fill value type (")
1256 << scalarType << ") to match output element type ("
1257 << outputElementType << ")";
1258 }
1259
1260 return success();
1261}
1262
1263//===----------------------------------------------------------------------===//
1264// StructuredOpInterface implementation
1265//===----------------------------------------------------------------------===//
1266
1267SmallVector<OpFoldResult> LinalgOp::createFlatListOfOperandDims(OpBuilder &b,
1268 Location loc) {
1269 SmallVector<OpFoldResult> res;
1270 for (OpOperand &opOperand : getOperation()->getOpOperands()) {
1271 for (int64_t i = 0, e = getRank(opOperand: &opOperand); i < e; ++i)
1272 res.push_back(Elt: createFoldedDimOp(b, loc, val: opOperand.get(), dim: i));
1273 }
1274 return res;
1275}
1276
1277SmallVector<int64_t, 4> LinalgOp::createFlatListOfOperandStaticDims() {
1278 SmallVector<int64_t, 4> res;
1279 assert(!hasDynamicShape() && "expected operands to have static shapes");
1280 for (OpOperand &opOperand : getOperation()->getOpOperands())
1281 llvm::append_range(C&: res, R: getShape(opOperand: &opOperand));
1282 return res;
1283}
1284
1285SmallVector<Range, 4> LinalgOp::createLoopRanges(OpBuilder &b, Location loc) {
1286 AffineMap map = getLoopsToShapesMap();
1287 unsigned numDims = map.getNumDims(), numRes = map.getNumResults();
1288 auto viewSizes = createFlatListOfOperandDims(b, loc);
1289 SmallVector<Range, 4> res(numDims);
1290 for (unsigned idx = 0; idx < numRes; ++idx) {
1291 auto result = map.getResult(idx);
1292 if (auto d = dyn_cast<AffineDimExpr>(Val&: result)) {
1293 if (res[d.getPosition()].offset)
1294 continue;
1295 res[d.getPosition()] =
1296 Range{.offset: b.getIndexAttr(value: 0), .size: viewSizes[idx], .stride: b.getIndexAttr(value: 1)};
1297 }
1298 }
1299 return res;
1300}
1301
1302/// Visitor to check if any of the given set of positions from AffineDimExprs
1303/// are used within an AffineExpr.
1304struct HasAffineDimExprVisitor
1305 : public AffineExprVisitor<HasAffineDimExprVisitor, bool> {
1306 HasAffineDimExprVisitor(llvm::SmallBitVector positions)
1307 : positions(std::move(positions)) {}
1308
1309 bool visitAffineBinaryOpExpr(AffineBinaryOpExpr binaryOpExpr) {
1310 return visit(expr: binaryOpExpr.getLHS()) || visit(expr: binaryOpExpr.getRHS());
1311 }
1312
1313 bool visitDimExpr(AffineDimExpr dimExpr) {
1314 return positions.test(Idx: dimExpr.getPosition());
1315 }
1316
1317 bool visitConstantExpr(AffineConstantExpr constExpr) { return false; }
1318
1319 bool visitSymbolExpr(AffineSymbolExpr symbolExpr) { return false; }
1320
1321private:
1322 llvm::SmallBitVector positions;
1323};
1324
1325static std::pair<int64_t, int64_t>
1326getResultsPositionInLoopsToShapeMap(LinalgOp &op) {
1327 int64_t inputRankSum = 0;
1328 int64_t outputRankSum = 0;
1329 for (OpOperand *input : op.getDpsInputOperands())
1330 inputRankSum += op.getRank(opOperand: input);
1331 for (OpOperand &output : op.getDpsInitsMutable())
1332 outputRankSum += op.getRank(opOperand: &output);
1333 return {inputRankSum, inputRankSum + outputRankSum};
1334}
1335
1336LogicalResult
1337LinalgOp::reifyResultShapes(OpBuilder &b,
1338 ReifiedRankedShapedTypeDims &reifiedReturnShapes) {
1339 // An example that helps understand the logic below.
1340 // Consider the following expression O(i+j, j) += A(i,k) * B(k, j)
1341 // We want to express the shape of dim 0 of O in terms of shape of the inputs.
1342 // This is achieved as follows.
1343 // loopsToShapesMap = (d0, d1, d2) -> (d0, d2, d2, d1, d0 + d1, d1)
1344 // subMapOfResultShapes = (d0, d1, d2) -> (d0 + d1, d1)
1345 // shapesToLoopsMap = (d0, d2, d2, d3, d4, d5) -> (d0, d3, d2)
1346 // resultShapesFromInputShapes = subMapOfResultDim.compose(shapesToLoopMap)
1347 // = (d0, d1, d2, d3, d4, d5) -> (d0 + d1, d1)
1348 AffineMap loopsToShapesMap = getLoopsToShapesMap();
1349
1350 // Find the position in the above map that represents the shape of the
1351 // result:dim being inferred.
1352 auto resultShapesSubMapPos = getResultsPositionInLoopsToShapeMap(op&: *this);
1353
1354 /// From loopsToShapesMap extract the submap that represents the shape of the
1355 /// (resultIdx, dim) needed.
1356 AffineMap loopToResultsShapeMap = loopsToShapesMap.getSliceMap(
1357 start: resultShapesSubMapPos.first,
1358 length: resultShapesSubMapPos.second - resultShapesSubMapPos.first);
1359 AffineMap resultShapesFromInputShapesMap =
1360 loopToResultsShapeMap.compose(map: getShapesToLoopsMap());
1361
1362 // Check that the result dim map does not contain the positions corresponding
1363 // to the outputs.
1364 llvm::SmallBitVector outputDims(resultShapesFromInputShapesMap.getNumDims());
1365 outputDims.set(I: resultShapesSubMapPos.first, E: resultShapesSubMapPos.second);
1366 HasAffineDimExprVisitor checkDimExpr(std::move(outputDims));
1367 Location loc = getOperation()->getLoc();
1368 IRRewriter rewriter(b);
1369 SmallVector<OpFoldResult> allResultDimValues =
1370 affine::makeComposedFoldedMultiResultAffineApply(
1371 b&: rewriter, loc, map: resultShapesFromInputShapesMap,
1372 operands: createFlatListOfOperandDims(b, loc));
1373 int64_t pos = 0;
1374 ArrayRef<AffineExpr> shapeExprs = resultShapesFromInputShapesMap.getResults();
1375 for (OpOperand &opOperand : getDpsInitsMutable()) {
1376 SmallVector<OpFoldResult> shapes;
1377 for (int64_t dim : llvm::seq<int64_t>(Begin: 0, End: getRank(opOperand: &opOperand))) {
1378 auto shapedType = llvm::cast<ShapedType>(Val: opOperand.get().getType());
1379 if (!shapedType.isDynamicDim(idx: dim)) {
1380 // Static dim: Return IntegerAttr.
1381 shapes.push_back(Elt: b.getIndexAttr(value: shapedType.getDimSize(idx: dim)));
1382 } else {
1383 // Dynamic dim: Return Value.
1384 OpFoldResult ofr = checkDimExpr.visit(expr: shapeExprs[pos])
1385 ? createOrFoldDimOp(b, loc, val: opOperand.get(), dim)
1386 : allResultDimValues[pos];
1387 shapes.push_back(Elt: getValueOrCreateConstantIndexOp(b, loc, ofr));
1388 }
1389 pos++;
1390 }
1391 reifiedReturnShapes.emplace_back(Args: std::move(shapes));
1392 }
1393 return success();
1394}
1395
1396/// Return the index in the indexingMaps vector that corresponds to this
1397/// `opOperand`.
1398int64_t LinalgOp::getIndexingMapIndex(OpOperand *opOperand) {
1399 auto operandNumber = opOperand->getOperandNumber();
1400 auto dpsIface = cast<DestinationStyleOpInterface>(Val&: *this->getOperation());
1401 if (!dpsIface.isDpsInput(opOperand))
1402 return operandNumber;
1403 unsigned start = dpsIface.getDpsInits().getBeginOperandIndex();
1404 assert(!dpsIface.isDpsInit(opOperand));
1405 // Account for potential inputs that are not DPS and may not appear in
1406 // `indexingMaps`.
1407 return cast<DestinationStyleOpInterface>(Val&: *this->getOperation())
1408 .getNumDpsInputs() +
1409 operandNumber - start;
1410}
1411
1412LogicalResult mlir::linalg::detail::verifyStructuredOpInterface(Operation *op) {
1413 LinalgOp linalgOp = cast<LinalgOp>(Val: op);
1414 // Mixed tensor/buffer operands are not allowed.
1415 if (!linalgOp.hasPureTensorSemantics() &&
1416 !linalgOp.hasPureBufferSemantics() && op->getNumOperands() > 0)
1417 return op->emitOpError(message: "expected to have pure tensor or buffer semantics");
1418
1419 // Before checking indexing maps, we need to make sure the attributes
1420 // referenced by it are valid.
1421 if (linalgOp.hasDynamicIndexingMaps())
1422 if (failed(Result: linalgOp.verifyIndexingMapRequiredAttributes()))
1423 return failure();
1424
1425 // Delayed calling of IndexingMapOpInterface::verifyImpl.
1426 if (failed(Result: cast<IndexingMapOpInterface>(Val: op).verifyImpl()))
1427 return failure();
1428
1429 // Set this flag if this op has user defined maps. This is required to guard
1430 // the below error condition which assume default indexing maps.
1431 for (OpOperand &opOperand : linalgOp->getOpOperands()) {
1432 AffineMap indexingMap = linalgOp.getMatchingIndexingMap(opOperand: &opOperand);
1433 // Domain must be consistent.
1434 unsigned numLoops = linalgOp.getNumLoops();
1435 if (indexingMap.getNumDims() != numLoops)
1436 return op->emitOpError(message: "expected indexing_map #")
1437 << opOperand.getOperandNumber() << " to have " << numLoops
1438 << " dim(s) to match the number of loops";
1439 }
1440 SmallVector<unsigned> redDims;
1441 linalgOp.getReductionDims(res&: redDims);
1442
1443 if (!linalgOp.getShapesToLoopsMap())
1444 return op->emitOpError(message: "expected the shape-to-loops map to be non-null");
1445
1446 // Check the region has exactly one block.
1447 if (linalgOp->getNumRegions() != 1 || !linalgOp->getRegion(index: 0).hasOneBlock())
1448 return op->emitOpError(message: "expects to have 1 region with 1 block");
1449
1450 // Simplifying assumption: bbargs match 1-1 with shape operands elemental
1451 // types.
1452 // TODO: once ranked shape types are plugged in, we may want to drop the
1453 // corresponding bbargs, that can never be read from. This will be subject to
1454 // consistency discussions (i.e. what to do with output tensors whose bbarg is
1455 // not used).
1456 Block &block = linalgOp->getRegion(index: 0).front();
1457
1458 if (linalgOp.getOpOperandsMatchingBBargs().size() != block.getNumArguments())
1459 return op->emitOpError(message: "expected as many non-induction variable region "
1460 "arguments as the number of input/output operands");
1461
1462 for (OpOperand *opOperand : linalgOp.getOpOperandsMatchingBBargs()) {
1463 Type elementType = opOperand->get().getType();
1464 if (isa<MemRefType, RankedTensorType>(Val: elementType))
1465 elementType = getElementTypeOrSelf(type: opOperand->get().getType());
1466 Type argType = block.getArgument(i: opOperand->getOperandNumber()).getType();
1467 if (elementType != argType)
1468 return op->emitOpError(message: "expected type of bb argument #")
1469 << opOperand->getOperandNumber() << " (" << argType << ")"
1470 << " to match element or self type of the corresponding operand ("
1471 << elementType << ")";
1472 }
1473
1474 return success();
1475}
1476