| 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 | |
| 30 | using namespace mlir; |
| 31 | using 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 | |
| 40 | bool 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 | |
| 61 | bool 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. |
| 87 | static 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. |
| 114 | static 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 | |
| 131 | std::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 | //===----------------------------------------------------------------------===// |
| 140 | std::optional<SmallVector<int64_t>> |
| 141 | linalg::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 | //===----------------------------------------------------------------------===// |
| 198 | std::optional<SmallVector<int64_t>> |
| 199 | linalg::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 | //===----------------------------------------------------------------------===// |
| 230 | std::optional<SmallVector<int64_t>> |
| 231 | linalg::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 | |
| 291 | static 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 | |
| 326 | bool 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 | |
| 337 | bool 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 | |
| 349 | bool 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). |
| 379 | static 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 | |
| 391 | bool 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. |
| 458 | template <typename AddOpTy, typename MulOpTy, typename... Args> |
| 459 | static 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. |
| 473 | template <typename... Args> |
| 474 | static 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. |
| 485 | static llvm::SmallDenseSet<int64_t> |
| 486 | findPermutationsIndexingOperand(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 | |
| 503 | namespace { |
| 504 | auto par = utils::IteratorType::parallel; |
| 505 | auto 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. |
| 512 | static FailureOr<SmallVector<utils::IteratorType>> |
| 513 | inferIteratorsFromOutMap(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. |
| 534 | static FailureOr<ContractionDimensions> |
| 535 | inferContractionDimsImpl(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 | |
| 577 | FailureOr<ContractionDimensions> |
| 578 | mlir::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 | |
| 585 | FailureOr<ContractionDimensions> |
| 586 | mlir::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 | |
| 595 | namespace mlir::linalg::detail { |
| 596 | enum class MatchContractionResult { |
| 597 | Success = 0, |
| 598 | NotLinalgOp, |
| 599 | WrongNumOperands, |
| 600 | NoReduction, |
| 601 | NotProjectedPermutations, |
| 602 | NotAddMul |
| 603 | }; |
| 604 | } // namespace mlir::linalg::detail |
| 605 | |
| 606 | mlir::linalg::detail::MatchContractionResult |
| 607 | mlir::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 | |
| 647 | StringRef |
| 648 | mlir::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 | |
| 666 | bool 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). |
| 688 | LogicalResult 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`) |
| 701 | template <typename T> |
| 702 | static T getAffineExprOfType(AffineExpr lhs, AffineExpr rhs) { |
| 703 | return isa<T>(lhs) ? cast<T>(lhs) : (isa<T>(rhs) ? cast<T>(rhs) : nullptr); |
| 704 | } |
| 705 | |
| 706 | namespace { |
| 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. |
| 715 | struct 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 | |
| 814 | static 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 | |
| 823 | static SmallVector<int64_t, 2> |
| 824 | getConstantsFromExprList(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. |
| 852 | static 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 | |
| 940 | static 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. |
| 974 | FailureOr<ConvolutionDimensions> |
| 975 | mlir::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 | |
| 994 | FailureOr<ConvolutionDimensions> |
| 995 | mlir::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 | |
| 1018 | namespace mlir::linalg::detail { |
| 1019 | enum 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 | |
| 1032 | mlir::linalg::detail::MatchConvolutionResult |
| 1033 | mlir::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 | |
| 1168 | StringRef |
| 1169 | mlir::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 | |
| 1193 | bool 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 | |
| 1200 | LogicalResult 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 | |
| 1211 | namespace { |
| 1212 | enum class MatchFillResult { |
| 1213 | Success = 0, |
| 1214 | NotLinalgOp, |
| 1215 | WrongNumOperands, |
| 1216 | NotScalarInput, |
| 1217 | TypeMismatch |
| 1218 | }; |
| 1219 | } // namespace |
| 1220 | |
| 1221 | static 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 | |
| 1242 | LogicalResult 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 | |
| 1267 | SmallVector<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 | |
| 1277 | SmallVector<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 | |
| 1285 | SmallVector<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. |
| 1304 | struct 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 | |
| 1321 | private: |
| 1322 | llvm::SmallBitVector positions; |
| 1323 | }; |
| 1324 | |
| 1325 | static std::pair<int64_t, int64_t> |
| 1326 | getResultsPositionInLoopsToShapeMap(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 | |
| 1336 | LogicalResult |
| 1337 | LinalgOp::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`. |
| 1398 | int64_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 | |
| 1412 | LogicalResult 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 | |