| 1 | //===- SparseTensorDialect.cpp - Sparse tensor dialect 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 <utility> |
| 10 | |
| 11 | #include "Detail/DimLvlMapParser.h" |
| 12 | |
| 13 | #include "mlir/Dialect/SparseTensor/IR/Enums.h" |
| 14 | #include "mlir/Dialect/SparseTensor/IR/SparseTensor.h" |
| 15 | #include "mlir/Dialect/SparseTensor/IR/SparseTensorStorageLayout.h" |
| 16 | #include "mlir/Dialect/SparseTensor/IR/SparseTensorType.h" |
| 17 | |
| 18 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 19 | #include "mlir/Dialect/Bufferization/IR/BufferizableOpInterface.h" |
| 20 | #include "mlir/Dialect/Complex/IR/Complex.h" |
| 21 | #include "mlir/Dialect/Utils/StaticValueUtils.h" |
| 22 | #include "mlir/IR/Builders.h" |
| 23 | #include "mlir/IR/OpImplementation.h" |
| 24 | #include "mlir/IR/PatternMatch.h" |
| 25 | #include "llvm/Support/FormatVariadic.h" |
| 26 | |
| 27 | #define GET_ATTRDEF_CLASSES |
| 28 | #include "mlir/Dialect/SparseTensor/IR/SparseTensorAttrDefs.cpp.inc" |
| 29 | #include "mlir/Dialect/SparseTensor/IR/SparseTensorAttrEnums.cpp.inc" |
| 30 | |
| 31 | // Forward declarations, following custom print/parsing methods are referenced |
| 32 | // by the generated code for SparseTensorTypes.td. |
| 33 | static mlir::ParseResult parseLevelRange(mlir::AsmParser &, |
| 34 | mlir::sparse_tensor::Level &, |
| 35 | mlir::sparse_tensor::Level &); |
| 36 | static void printLevelRange(mlir::AsmPrinter &, mlir::sparse_tensor::Level, |
| 37 | mlir::sparse_tensor::Level); |
| 38 | |
| 39 | #define GET_TYPEDEF_CLASSES |
| 40 | #include "mlir/Dialect/SparseTensor/IR/SparseTensorTypes.cpp.inc" |
| 41 | |
| 42 | using namespace mlir; |
| 43 | using namespace mlir::sparse_tensor; |
| 44 | |
| 45 | // Support hashing LevelType such that SparseTensorEncodingAttr can be hashed as |
| 46 | // well. |
| 47 | namespace mlir::sparse_tensor { |
| 48 | static llvm::hash_code hash_value(LevelType lt) { |
| 49 | return llvm::hash_value(value: static_cast<uint64_t>(lt)); |
| 50 | } |
| 51 | } // namespace mlir::sparse_tensor |
| 52 | |
| 53 | //===----------------------------------------------------------------------===// |
| 54 | // Local Convenience Methods. |
| 55 | //===----------------------------------------------------------------------===// |
| 56 | |
| 57 | static constexpr bool acceptBitWidth(unsigned bitWidth) { |
| 58 | switch (bitWidth) { |
| 59 | case 0: |
| 60 | case 8: |
| 61 | case 16: |
| 62 | case 32: |
| 63 | case 64: |
| 64 | return true; |
| 65 | default: |
| 66 | return false; |
| 67 | } |
| 68 | } |
| 69 | |
| 70 | static SmallVector<Size> |
| 71 | getSparseFieldShape(const SparseTensorEncodingAttr enc, |
| 72 | std::optional<ArrayRef<int64_t>> dimShape) { |
| 73 | assert(enc); |
| 74 | // With only encoding, we can not determine the static shape for leading |
| 75 | // batch levels, we therefore return a dynamic shape memref instead. |
| 76 | SmallVector<int64_t> memrefShape(enc.getBatchLvlRank(), ShapedType::kDynamic); |
| 77 | if (dimShape.has_value()) { |
| 78 | // If the actual tensor shape is provided, we can then refine the leading |
| 79 | // batch dimension. |
| 80 | SmallVector<int64_t> lvlShape = |
| 81 | enc.translateShape(srcShape: *dimShape, CrdTransDirectionKind::dim2lvl); |
| 82 | memrefShape.assign(in_start: lvlShape.begin(), |
| 83 | in_end: lvlShape.begin() + enc.getBatchLvlRank()); |
| 84 | } |
| 85 | // Another dynamic dimension to store the sparse level. |
| 86 | memrefShape.push_back(Elt: ShapedType::kDynamic); |
| 87 | return memrefShape; |
| 88 | } |
| 89 | |
| 90 | //===----------------------------------------------------------------------===// |
| 91 | // SparseTensorDialect StorageLayout. |
| 92 | //===----------------------------------------------------------------------===// |
| 93 | |
| 94 | static constexpr Level kInvalidLevel = -1u; |
| 95 | static constexpr Level kInvalidFieldIndex = -1u; |
| 96 | static constexpr FieldIndex kDataFieldStartingIdx = 0; |
| 97 | |
| 98 | void StorageLayout::foreachField( |
| 99 | llvm::function_ref<bool(FieldIndex, SparseTensorFieldKind, Level, |
| 100 | LevelType)> |
| 101 | callback) const { |
| 102 | const auto lvlTypes = enc.getLvlTypes(); |
| 103 | const Level lvlRank = enc.getLvlRank(); |
| 104 | SmallVector<COOSegment> cooSegs = enc.getCOOSegments(); |
| 105 | FieldIndex fieldIdx = kDataFieldStartingIdx; |
| 106 | |
| 107 | ArrayRef cooSegsRef = cooSegs; |
| 108 | // Per-level storage. |
| 109 | for (Level l = 0; l < lvlRank; /*l += 1 or l += AoSCooLen*/) { |
| 110 | const auto lt = lvlTypes[l]; |
| 111 | if (isWithPosLT(lt)) { |
| 112 | if (!(callback(fieldIdx++, SparseTensorFieldKind::PosMemRef, l, lt))) |
| 113 | return; |
| 114 | } |
| 115 | if (isWithCrdLT(lt)) { |
| 116 | if (!(callback(fieldIdx++, SparseTensorFieldKind::CrdMemRef, l, lt))) |
| 117 | return; |
| 118 | } |
| 119 | if (!cooSegsRef.empty() && cooSegsRef.front().isSegmentStart(l)) { |
| 120 | if (!cooSegsRef.front().isSoA) { |
| 121 | // AoS COO, all singletons are fused into one memrefs. Skips the entire |
| 122 | // COO segement. |
| 123 | l = cooSegsRef.front().lvlRange.second; |
| 124 | } else { |
| 125 | // SoA COO, each singleton level has one memref. |
| 126 | l++; |
| 127 | } |
| 128 | // Expire handled COO segment. |
| 129 | cooSegsRef = cooSegsRef.drop_front(); |
| 130 | } else { |
| 131 | // Non COO levels. |
| 132 | l++; |
| 133 | } |
| 134 | } |
| 135 | // The values array. |
| 136 | if (!(callback(fieldIdx++, SparseTensorFieldKind::ValMemRef, kInvalidLevel, |
| 137 | LevelFormat::Undef))) |
| 138 | return; |
| 139 | // Put metadata at the end. |
| 140 | if (!(callback(fieldIdx++, SparseTensorFieldKind::StorageSpec, kInvalidLevel, |
| 141 | LevelFormat::Undef))) |
| 142 | return; |
| 143 | } |
| 144 | |
| 145 | void sparse_tensor::foreachFieldAndTypeInSparseTensor( |
| 146 | SparseTensorType stt, |
| 147 | llvm::function_ref<bool(Type, FieldIndex, SparseTensorFieldKind, Level, |
| 148 | LevelType)> |
| 149 | callback) { |
| 150 | assert(stt.hasEncoding()); |
| 151 | |
| 152 | SmallVector<int64_t> memrefShape = |
| 153 | getSparseFieldShape(enc: stt.getEncoding(), dimShape: stt.getDimShape()); |
| 154 | |
| 155 | const Type specType = StorageSpecifierType::get(encoding: stt.getEncoding()); |
| 156 | // memref<[batch] x ? x pos> positions |
| 157 | const Type posMemType = MemRefType::get(shape: memrefShape, elementType: stt.getPosType()); |
| 158 | // memref<[batch] x ? x crd> coordinates |
| 159 | const Type crdMemType = MemRefType::get(shape: memrefShape, elementType: stt.getCrdType()); |
| 160 | // memref<[batch] x ? x eltType> values |
| 161 | const Type valMemType = MemRefType::get(shape: memrefShape, elementType: stt.getElementType()); |
| 162 | |
| 163 | StorageLayout(stt).foreachField(callback: [specType, posMemType, crdMemType, valMemType, |
| 164 | callback](FieldIndex fieldIdx, |
| 165 | SparseTensorFieldKind fieldKind, |
| 166 | Level lvl, LevelType lt) -> bool { |
| 167 | switch (fieldKind) { |
| 168 | case SparseTensorFieldKind::StorageSpec: |
| 169 | return callback(specType, fieldIdx, fieldKind, lvl, lt); |
| 170 | case SparseTensorFieldKind::PosMemRef: |
| 171 | return callback(posMemType, fieldIdx, fieldKind, lvl, lt); |
| 172 | case SparseTensorFieldKind::CrdMemRef: |
| 173 | return callback(crdMemType, fieldIdx, fieldKind, lvl, lt); |
| 174 | case SparseTensorFieldKind::ValMemRef: |
| 175 | return callback(valMemType, fieldIdx, fieldKind, lvl, lt); |
| 176 | }; |
| 177 | llvm_unreachable("unrecognized field kind" ); |
| 178 | }); |
| 179 | } |
| 180 | |
| 181 | unsigned StorageLayout::getNumFields() const { |
| 182 | unsigned numFields = 0; |
| 183 | foreachField(callback: [&numFields](FieldIndex, SparseTensorFieldKind, Level, |
| 184 | LevelType) -> bool { |
| 185 | numFields++; |
| 186 | return true; |
| 187 | }); |
| 188 | return numFields; |
| 189 | } |
| 190 | |
| 191 | unsigned StorageLayout::getNumDataFields() const { |
| 192 | unsigned numFields = 0; // one value memref |
| 193 | foreachField(callback: [&numFields](FieldIndex fidx, SparseTensorFieldKind, Level, |
| 194 | LevelType) -> bool { |
| 195 | if (fidx >= kDataFieldStartingIdx) |
| 196 | numFields++; |
| 197 | return true; |
| 198 | }); |
| 199 | numFields -= 1; // the last field is StorageSpecifier |
| 200 | assert(numFields == getNumFields() - kDataFieldStartingIdx - 1); |
| 201 | return numFields; |
| 202 | } |
| 203 | |
| 204 | std::pair<FieldIndex, unsigned> |
| 205 | StorageLayout::getFieldIndexAndStride(SparseTensorFieldKind kind, |
| 206 | std::optional<Level> lvl) const { |
| 207 | FieldIndex fieldIdx = kInvalidFieldIndex; |
| 208 | unsigned stride = 1; |
| 209 | if (kind == SparseTensorFieldKind::CrdMemRef) { |
| 210 | assert(lvl.has_value()); |
| 211 | const Level cooStart = enc.getAoSCOOStart(); |
| 212 | const Level lvlRank = enc.getLvlRank(); |
| 213 | if (lvl.value() >= cooStart && lvl.value() < lvlRank) { |
| 214 | lvl = cooStart; |
| 215 | stride = lvlRank - cooStart; |
| 216 | } |
| 217 | } |
| 218 | foreachField(callback: [lvl, kind, &fieldIdx](FieldIndex fIdx, |
| 219 | SparseTensorFieldKind fKind, Level fLvl, |
| 220 | LevelType lt) -> bool { |
| 221 | if ((lvl && fLvl == lvl.value() && kind == fKind) || |
| 222 | (kind == fKind && fKind == SparseTensorFieldKind::ValMemRef)) { |
| 223 | fieldIdx = fIdx; |
| 224 | // Returns false to break the iteration. |
| 225 | return false; |
| 226 | } |
| 227 | return true; |
| 228 | }); |
| 229 | assert(fieldIdx != kInvalidFieldIndex); |
| 230 | return std::pair<FieldIndex, unsigned>(fieldIdx, stride); |
| 231 | } |
| 232 | |
| 233 | //===----------------------------------------------------------------------===// |
| 234 | // SparseTensorDialect Attribute Methods. |
| 235 | //===----------------------------------------------------------------------===// |
| 236 | |
| 237 | std::optional<uint64_t> SparseTensorDimSliceAttr::getStatic(int64_t v) { |
| 238 | return isDynamic(v) ? std::nullopt |
| 239 | : std::make_optional(t: static_cast<uint64_t>(v)); |
| 240 | } |
| 241 | |
| 242 | std::optional<uint64_t> SparseTensorDimSliceAttr::getStaticOffset() const { |
| 243 | return getStatic(v: getOffset()); |
| 244 | } |
| 245 | |
| 246 | std::optional<uint64_t> SparseTensorDimSliceAttr::getStaticStride() const { |
| 247 | return getStatic(v: getStride()); |
| 248 | } |
| 249 | |
| 250 | std::optional<uint64_t> SparseTensorDimSliceAttr::getStaticSize() const { |
| 251 | return getStatic(v: getSize()); |
| 252 | } |
| 253 | |
| 254 | bool SparseTensorDimSliceAttr::isCompletelyDynamic() const { |
| 255 | return isDynamic(v: getOffset()) && isDynamic(v: getStride()) && |
| 256 | isDynamic(v: getSize()); |
| 257 | } |
| 258 | |
| 259 | std::string SparseTensorDimSliceAttr::getStaticString(int64_t v) { |
| 260 | return isDynamic(v) ? "?" : std::to_string(val: v); |
| 261 | } |
| 262 | |
| 263 | void SparseTensorDimSliceAttr::print(llvm::raw_ostream &os) const { |
| 264 | assert(getImpl() && "Uninitialized SparseTensorDimSliceAttr" ); |
| 265 | os << '('; |
| 266 | os << getStaticString(v: getOffset()); |
| 267 | os << ", " ; |
| 268 | os << getStaticString(v: getSize()); |
| 269 | os << ", " ; |
| 270 | os << getStaticString(v: getStride()); |
| 271 | os << ')'; |
| 272 | } |
| 273 | |
| 274 | void SparseTensorDimSliceAttr::print(AsmPrinter &printer) const { |
| 275 | print(os&: printer.getStream()); |
| 276 | } |
| 277 | |
| 278 | static ParseResult parseOptionalStaticSlice(int64_t &result, |
| 279 | AsmParser &parser) { |
| 280 | auto parseResult = parser.parseOptionalInteger(result); |
| 281 | if (parseResult.has_value()) { |
| 282 | if (parseResult.value().succeeded() && result < 0) { |
| 283 | parser.emitError( |
| 284 | loc: parser.getCurrentLocation(), |
| 285 | message: "expect positive value or ? for slice offset/size/stride" ); |
| 286 | return failure(); |
| 287 | } |
| 288 | return parseResult.value(); |
| 289 | } |
| 290 | |
| 291 | // Else, and '?' which represented dynamic slice |
| 292 | result = SparseTensorDimSliceAttr::kDynamic; |
| 293 | return parser.parseQuestion(); |
| 294 | } |
| 295 | |
| 296 | Attribute SparseTensorDimSliceAttr::parse(AsmParser &parser, Type type) { |
| 297 | int64_t offset = kDynamic, size = kDynamic, stride = kDynamic; |
| 298 | |
| 299 | if (failed(Result: parser.parseLParen()) || |
| 300 | failed(Result: parseOptionalStaticSlice(result&: offset, parser)) || |
| 301 | failed(Result: parser.parseComma()) || |
| 302 | failed(Result: parseOptionalStaticSlice(result&: size, parser)) || |
| 303 | failed(Result: parser.parseComma()) || |
| 304 | failed(Result: parseOptionalStaticSlice(result&: stride, parser)) || |
| 305 | failed(Result: parser.parseRParen())) |
| 306 | return {}; |
| 307 | |
| 308 | return parser.getChecked<SparseTensorDimSliceAttr>(params: parser.getContext(), |
| 309 | params&: offset, params&: size, params&: stride); |
| 310 | } |
| 311 | |
| 312 | LogicalResult |
| 313 | SparseTensorDimSliceAttr::verify(function_ref<InFlightDiagnostic()> emitError, |
| 314 | int64_t offset, int64_t size, int64_t stride) { |
| 315 | if (!isDynamic(v: offset) && offset < 0) |
| 316 | return emitError() << "expect non-negative value or ? for slice offset" ; |
| 317 | if (!isDynamic(v: size) && size <= 0) |
| 318 | return emitError() << "expect positive value or ? for slice size" ; |
| 319 | if (!isDynamic(v: stride) && stride <= 0) |
| 320 | return emitError() << "expect positive value or ? for slice stride" ; |
| 321 | return success(); |
| 322 | } |
| 323 | |
| 324 | SparseTensorEncodingAttr |
| 325 | SparseTensorEncodingAttr::withDimToLvl(AffineMap dimToLvl) const { |
| 326 | assert(getImpl() && "Uninitialized SparseTensorEncodingAttr" ); |
| 327 | return SparseTensorEncodingAttr::get( |
| 328 | context: getContext(), lvlTypes: getLvlTypes(), dimToLvl, lvlToDim: AffineMap(), posWidth: getPosWidth(), |
| 329 | crdWidth: getCrdWidth(), explicitVal: getExplicitVal(), implicitVal: getImplicitVal()); |
| 330 | } |
| 331 | |
| 332 | SparseTensorEncodingAttr |
| 333 | SparseTensorEncodingAttr::withDimToLvl(SparseTensorEncodingAttr enc) const { |
| 334 | return withDimToLvl(dimToLvl: enc ? enc.getDimToLvl() : AffineMap()); |
| 335 | } |
| 336 | |
| 337 | SparseTensorEncodingAttr SparseTensorEncodingAttr::withoutDimToLvl() const { |
| 338 | return withDimToLvl(dimToLvl: AffineMap()); |
| 339 | } |
| 340 | |
| 341 | SparseTensorEncodingAttr |
| 342 | SparseTensorEncodingAttr::withBitWidths(unsigned posWidth, |
| 343 | unsigned crdWidth) const { |
| 344 | assert(getImpl() && "Uninitialized SparseTensorEncodingAttr" ); |
| 345 | return SparseTensorEncodingAttr::get( |
| 346 | context: getContext(), lvlTypes: getLvlTypes(), dimToLvl: getDimToLvl(), lvlToDim: getLvlToDim(), posWidth, |
| 347 | crdWidth, explicitVal: getExplicitVal(), implicitVal: getImplicitVal()); |
| 348 | } |
| 349 | |
| 350 | SparseTensorEncodingAttr SparseTensorEncodingAttr::withoutBitWidths() const { |
| 351 | return withBitWidths(posWidth: 0, crdWidth: 0); |
| 352 | } |
| 353 | |
| 354 | SparseTensorEncodingAttr |
| 355 | SparseTensorEncodingAttr::withExplicitVal(Attribute explicitVal) const { |
| 356 | assert(getImpl() && "Uninitialized SparseTensorEncodingAttr" ); |
| 357 | return SparseTensorEncodingAttr::get( |
| 358 | context: getContext(), lvlTypes: getLvlTypes(), dimToLvl: getDimToLvl(), lvlToDim: getLvlToDim(), posWidth: getPosWidth(), |
| 359 | crdWidth: getCrdWidth(), explicitVal, implicitVal: getImplicitVal()); |
| 360 | } |
| 361 | |
| 362 | SparseTensorEncodingAttr SparseTensorEncodingAttr::withoutExplicitVal() const { |
| 363 | return withExplicitVal(explicitVal: Attribute()); |
| 364 | } |
| 365 | |
| 366 | SparseTensorEncodingAttr |
| 367 | SparseTensorEncodingAttr::withImplicitVal(Attribute implicitVal) const { |
| 368 | assert(getImpl() && "Uninitialized SparseTensorEncodingAttr" ); |
| 369 | return SparseTensorEncodingAttr::get( |
| 370 | context: getContext(), lvlTypes: getLvlTypes(), dimToLvl: getDimToLvl(), lvlToDim: getLvlToDim(), posWidth: getPosWidth(), |
| 371 | crdWidth: getCrdWidth(), explicitVal: getExplicitVal(), implicitVal); |
| 372 | } |
| 373 | |
| 374 | SparseTensorEncodingAttr SparseTensorEncodingAttr::withoutImplicitVal() const { |
| 375 | return withImplicitVal(implicitVal: Attribute()); |
| 376 | } |
| 377 | |
| 378 | SparseTensorEncodingAttr SparseTensorEncodingAttr::withDimSlices( |
| 379 | ArrayRef<SparseTensorDimSliceAttr> dimSlices) const { |
| 380 | return SparseTensorEncodingAttr::get( |
| 381 | context: getContext(), lvlTypes: getLvlTypes(), dimToLvl: getDimToLvl(), lvlToDim: getLvlToDim(), posWidth: getPosWidth(), |
| 382 | crdWidth: getCrdWidth(), explicitVal: getExplicitVal(), implicitVal: getImplicitVal(), dimSlices); |
| 383 | } |
| 384 | |
| 385 | SparseTensorEncodingAttr SparseTensorEncodingAttr::withoutDimSlices() const { |
| 386 | return withDimSlices(dimSlices: ArrayRef<SparseTensorDimSliceAttr>{}); |
| 387 | } |
| 388 | |
| 389 | uint64_t SparseTensorEncodingAttr::getBatchLvlRank() const { |
| 390 | ArrayRef<LevelType> lvlTypes = getLvlTypes(); |
| 391 | auto lastBatch = std::find_if(first: lvlTypes.rbegin(), last: lvlTypes.rend(), pred: isBatchLT); |
| 392 | return std::distance(first: lastBatch, last: lvlTypes.rend()); |
| 393 | } |
| 394 | |
| 395 | bool SparseTensorEncodingAttr::isAllDense() const { |
| 396 | return !getImpl() || llvm::all_of(Range: getLvlTypes(), P: isDenseLT); |
| 397 | } |
| 398 | |
| 399 | bool SparseTensorEncodingAttr::isAllOrdered() const { |
| 400 | return !getImpl() || llvm::all_of(Range: getLvlTypes(), P: isOrderedLT); |
| 401 | } |
| 402 | |
| 403 | Type SparseTensorEncodingAttr::getCrdElemType() const { |
| 404 | if (!getImpl()) |
| 405 | return nullptr; |
| 406 | if (getCrdWidth()) |
| 407 | return IntegerType::get(context: getContext(), width: getCrdWidth()); |
| 408 | return IndexType::get(context: getContext()); |
| 409 | } |
| 410 | |
| 411 | Type SparseTensorEncodingAttr::getPosElemType() const { |
| 412 | if (!getImpl()) |
| 413 | return nullptr; |
| 414 | if (getPosWidth()) |
| 415 | return IntegerType::get(context: getContext(), width: getPosWidth()); |
| 416 | return IndexType::get(context: getContext()); |
| 417 | } |
| 418 | |
| 419 | MemRefType SparseTensorEncodingAttr::getCrdMemRefType( |
| 420 | std::optional<ArrayRef<int64_t>> dimShape) const { |
| 421 | SmallVector<Size> shape = getSparseFieldShape(enc: *this, dimShape); |
| 422 | return MemRefType::get(shape, elementType: getCrdElemType()); |
| 423 | } |
| 424 | |
| 425 | MemRefType SparseTensorEncodingAttr::getPosMemRefType( |
| 426 | std::optional<ArrayRef<int64_t>> dimShape) const { |
| 427 | SmallVector<Size> shape = getSparseFieldShape(enc: *this, dimShape); |
| 428 | return MemRefType::get(shape, elementType: getPosElemType()); |
| 429 | } |
| 430 | |
| 431 | bool SparseTensorEncodingAttr::isIdentity() const { |
| 432 | return !getImpl() || !getDimToLvl() || getDimToLvl().isIdentity(); |
| 433 | } |
| 434 | |
| 435 | bool SparseTensorEncodingAttr::isPermutation() const { |
| 436 | return !getImpl() || !getDimToLvl() || getDimToLvl().isPermutation(); |
| 437 | } |
| 438 | |
| 439 | Dimension SparseTensorEncodingAttr::getDimRank() const { |
| 440 | assert(getImpl() && "Uninitialized SparseTensorEncodingAttr" ); |
| 441 | const auto dimToLvl = getDimToLvl(); |
| 442 | return dimToLvl ? dimToLvl.getNumDims() : getLvlRank(); |
| 443 | } |
| 444 | |
| 445 | Level SparseTensorEncodingAttr::getLvlRank() const { |
| 446 | assert(getImpl() && "Uninitialized SparseTensorEncodingAttr" ); |
| 447 | return getLvlTypes().size(); |
| 448 | } |
| 449 | |
| 450 | LevelType SparseTensorEncodingAttr::getLvlType(Level l) const { |
| 451 | if (!getImpl()) |
| 452 | return LevelFormat::Batch; |
| 453 | assert(l < getLvlRank() && "Level is out of bounds" ); |
| 454 | return getLvlTypes()[l]; |
| 455 | } |
| 456 | |
| 457 | bool SparseTensorEncodingAttr::isSlice() const { |
| 458 | assert(getImpl() && "Uninitialized SparseTensorEncodingAttr" ); |
| 459 | return !getDimSlices().empty(); |
| 460 | } |
| 461 | |
| 462 | SparseTensorDimSliceAttr |
| 463 | SparseTensorEncodingAttr::getDimSlice(Dimension dim) const { |
| 464 | assert(isSlice() && "Is not a slice" ); |
| 465 | const auto dimSlices = getDimSlices(); |
| 466 | assert(dim < dimSlices.size() && "Dimension is out of bounds" ); |
| 467 | return dimSlices[dim]; |
| 468 | } |
| 469 | |
| 470 | std::optional<uint64_t> |
| 471 | SparseTensorEncodingAttr::getStaticDimSliceOffset(Dimension dim) const { |
| 472 | return getDimSlice(dim).getStaticOffset(); |
| 473 | } |
| 474 | |
| 475 | std::optional<uint64_t> |
| 476 | SparseTensorEncodingAttr::getStaticDimSliceStride(Dimension dim) const { |
| 477 | return getDimSlice(dim).getStaticStride(); |
| 478 | } |
| 479 | |
| 480 | std::optional<uint64_t> |
| 481 | SparseTensorEncodingAttr::getStaticLvlSliceOffset(Level lvl) const { |
| 482 | return getStaticDimSliceOffset(dim: toDim(enc: *this, l: lvl)); |
| 483 | } |
| 484 | |
| 485 | std::optional<uint64_t> |
| 486 | SparseTensorEncodingAttr::getStaticLvlSliceStride(Level lvl) const { |
| 487 | return getStaticDimSliceStride(dim: toDim(enc: *this, l: lvl)); |
| 488 | } |
| 489 | |
| 490 | SmallVector<int64_t> |
| 491 | SparseTensorEncodingAttr::translateShape(ArrayRef<int64_t> srcShape, |
| 492 | CrdTransDirectionKind dir) const { |
| 493 | if (isIdentity()) |
| 494 | return SmallVector<int64_t>(srcShape); |
| 495 | |
| 496 | SmallVector<int64_t> ret; |
| 497 | unsigned rank = |
| 498 | dir == CrdTransDirectionKind::dim2lvl ? getLvlRank() : getDimRank(); |
| 499 | ret.reserve(N: rank); |
| 500 | |
| 501 | if (isPermutation()) { |
| 502 | for (unsigned r = 0; r < rank; r++) { |
| 503 | unsigned trans = dir == CrdTransDirectionKind::dim2lvl ? toDim(enc: *this, l: r) |
| 504 | : toLvl(enc: *this, d: r); |
| 505 | ret.push_back(Elt: srcShape[trans]); |
| 506 | } |
| 507 | return ret; |
| 508 | } |
| 509 | |
| 510 | // Handle non-permutation maps. |
| 511 | AffineMap transMap = |
| 512 | dir == CrdTransDirectionKind::dim2lvl ? getDimToLvl() : getLvlToDim(); |
| 513 | |
| 514 | // Check if transMap is valid. There are cases where the lvlToDim map is |
| 515 | // uninitialized due to the format used, e.g. ELL. This is visible as |
| 516 | // inferring lvlToDim (see inferLvlToDim function below) may return an |
| 517 | // uninitialized affine map. Fallback to dynamic shapes. |
| 518 | if (!transMap) { |
| 519 | ret.resize(N: rank, NV: ShapedType::kDynamic); |
| 520 | return ret; |
| 521 | } |
| 522 | |
| 523 | SmallVector<AffineExpr> dimRep; |
| 524 | dimRep.reserve(N: srcShape.size()); |
| 525 | for (int64_t sz : srcShape) { |
| 526 | if (ShapedType::isStatic(dValue: sz)) { |
| 527 | // Push back the max coordinate for the given dimension/level size. |
| 528 | dimRep.push_back(Elt: getAffineConstantExpr(constant: sz - 1, context: getContext())); |
| 529 | } else { |
| 530 | // A dynamic size, use a AffineDimExpr to symbolize the value. |
| 531 | dimRep.push_back(Elt: getAffineDimExpr(position: dimRep.size(), context: getContext())); |
| 532 | } |
| 533 | }; |
| 534 | |
| 535 | // The number of symbols information is included inside the `dimToLvl` map |
| 536 | // during parsing. Here, we're extracting it to be used when simplifying the |
| 537 | // affine expression. |
| 538 | unsigned numSymbols = getDimToLvl().getNumSymbols(); |
| 539 | |
| 540 | for (AffineExpr exp : transMap.getResults()) { |
| 541 | // Do constant propagation on the affine map. |
| 542 | AffineExpr evalExp = simplifyAffineExpr(expr: exp.replaceDims(dimReplacements: dimRep), |
| 543 | numDims: srcShape.size(), numSymbols); |
| 544 | // use llvm namespace here to avoid ambiguity |
| 545 | if (auto c = llvm::dyn_cast<AffineConstantExpr>(Val&: evalExp)) { |
| 546 | ret.push_back(Elt: c.getValue() + 1); |
| 547 | } else { |
| 548 | if (auto mod = llvm::dyn_cast<AffineBinaryOpExpr>(Val&: evalExp); |
| 549 | mod && mod.getKind() == AffineExprKind::Mod) { |
| 550 | // We can still infer a static bound for expressions in form |
| 551 | // "d % constant" since d % constant \in [0, constant). |
| 552 | if (auto bound = llvm::dyn_cast<AffineConstantExpr>(Val: mod.getRHS())) { |
| 553 | ret.push_back(Elt: bound.getValue()); |
| 554 | continue; |
| 555 | } |
| 556 | } |
| 557 | ret.push_back(Elt: ShapedType::kDynamic); |
| 558 | } |
| 559 | } |
| 560 | assert(ret.size() == rank); |
| 561 | return ret; |
| 562 | } |
| 563 | |
| 564 | ValueRange |
| 565 | SparseTensorEncodingAttr::translateCrds(OpBuilder &builder, Location loc, |
| 566 | ValueRange crds, |
| 567 | CrdTransDirectionKind dir) const { |
| 568 | if (!getImpl()) |
| 569 | return crds; |
| 570 | |
| 571 | SmallVector<Type> retType( |
| 572 | dir == CrdTransDirectionKind::lvl2dim ? getDimRank() : getLvlRank(), |
| 573 | builder.getIndexType()); |
| 574 | auto transOp = |
| 575 | CrdTranslateOp::create(builder, location: loc, out_crds: retType, in_crds: crds, direction: dir, encoder: *this); |
| 576 | return transOp.getOutCrds(); |
| 577 | } |
| 578 | |
| 579 | Attribute SparseTensorEncodingAttr::parse(AsmParser &parser, Type type) { |
| 580 | // Open "<{" part. |
| 581 | if (failed(Result: parser.parseLess())) |
| 582 | return {}; |
| 583 | if (failed(Result: parser.parseLBrace())) |
| 584 | return {}; |
| 585 | |
| 586 | // Process the data from the parsed dictionary value into struct-like data. |
| 587 | SmallVector<LevelType> lvlTypes; |
| 588 | SmallVector<SparseTensorDimSliceAttr> dimSlices; |
| 589 | AffineMap dimToLvl = {}; |
| 590 | AffineMap lvlToDim = {}; |
| 591 | unsigned posWidth = 0; |
| 592 | unsigned crdWidth = 0; |
| 593 | Attribute explicitVal; |
| 594 | Attribute implicitVal; |
| 595 | StringRef attrName; |
| 596 | SmallVector<StringRef, 5> keys = {"map" , "posWidth" , "crdWidth" , |
| 597 | "explicitVal" , "implicitVal" }; |
| 598 | while (succeeded(Result: parser.parseOptionalKeyword(keyword: &attrName))) { |
| 599 | // Detect admissible keyword. |
| 600 | auto *it = find(Range&: keys, Val: attrName); |
| 601 | if (it == keys.end()) { |
| 602 | parser.emitError(loc: parser.getNameLoc(), message: "unexpected key: " ) << attrName; |
| 603 | return {}; |
| 604 | } |
| 605 | unsigned keyWordIndex = it - keys.begin(); |
| 606 | // Consume the `=` after keys |
| 607 | if (failed(Result: parser.parseEqual())) |
| 608 | return {}; |
| 609 | // Dispatch on keyword. |
| 610 | switch (keyWordIndex) { |
| 611 | case 0: { // map |
| 612 | ir_detail::DimLvlMapParser cParser(parser); |
| 613 | auto res = cParser.parseDimLvlMap(); |
| 614 | if (failed(Result: res)) |
| 615 | return {}; |
| 616 | const auto &dlm = *res; |
| 617 | |
| 618 | const Level lvlRank = dlm.getLvlRank(); |
| 619 | for (Level lvl = 0; lvl < lvlRank; lvl++) |
| 620 | lvlTypes.push_back(Elt: dlm.getLvlType(lvl)); |
| 621 | |
| 622 | const Dimension dimRank = dlm.getDimRank(); |
| 623 | for (Dimension dim = 0; dim < dimRank; dim++) |
| 624 | dimSlices.push_back(Elt: dlm.getDimSlice(dim)); |
| 625 | // NOTE: the old syntax requires an all-or-nothing approach to |
| 626 | // `dimSlices`; therefore, if any slice actually exists then we need |
| 627 | // to convert null-DSA into default/nop DSA. |
| 628 | const auto isDefined = [](SparseTensorDimSliceAttr slice) { |
| 629 | return static_cast<bool>(slice.getImpl()); |
| 630 | }; |
| 631 | if (llvm::any_of(Range&: dimSlices, P: isDefined)) { |
| 632 | const auto defaultSlice = |
| 633 | SparseTensorDimSliceAttr::get(context: parser.getContext()); |
| 634 | for (Dimension dim = 0; dim < dimRank; dim++) |
| 635 | if (!isDefined(dimSlices[dim])) |
| 636 | dimSlices[dim] = defaultSlice; |
| 637 | } else { |
| 638 | dimSlices.clear(); |
| 639 | } |
| 640 | |
| 641 | dimToLvl = dlm.getDimToLvlMap(context: parser.getContext()); |
| 642 | lvlToDim = dlm.getLvlToDimMap(context: parser.getContext()); |
| 643 | break; |
| 644 | } |
| 645 | case 1: { // posWidth |
| 646 | Attribute attr; |
| 647 | if (failed(Result: parser.parseAttribute(result&: attr))) |
| 648 | return {}; |
| 649 | auto intAttr = llvm::dyn_cast<IntegerAttr>(Val&: attr); |
| 650 | if (!intAttr) { |
| 651 | parser.emitError(loc: parser.getNameLoc(), |
| 652 | message: "expected an integral position bitwidth" ); |
| 653 | return {}; |
| 654 | } |
| 655 | posWidth = intAttr.getInt(); |
| 656 | break; |
| 657 | } |
| 658 | case 2: { // crdWidth |
| 659 | Attribute attr; |
| 660 | if (failed(Result: parser.parseAttribute(result&: attr))) |
| 661 | return {}; |
| 662 | auto intAttr = llvm::dyn_cast<IntegerAttr>(Val&: attr); |
| 663 | if (!intAttr) { |
| 664 | parser.emitError(loc: parser.getNameLoc(), |
| 665 | message: "expected an integral index bitwidth" ); |
| 666 | return {}; |
| 667 | } |
| 668 | crdWidth = intAttr.getInt(); |
| 669 | break; |
| 670 | } |
| 671 | case 3: { // explicitVal |
| 672 | Attribute attr; |
| 673 | if (failed(Result: parser.parseAttribute(result&: attr))) |
| 674 | return {}; |
| 675 | if (auto result = llvm::dyn_cast<FloatAttr>(Val&: attr)) { |
| 676 | explicitVal = result; |
| 677 | } else if (auto result = llvm::dyn_cast<IntegerAttr>(Val&: attr)) { |
| 678 | explicitVal = result; |
| 679 | } else if (auto result = llvm::dyn_cast<complex::NumberAttr>(Val&: attr)) { |
| 680 | explicitVal = result; |
| 681 | } else { |
| 682 | parser.emitError(loc: parser.getNameLoc(), |
| 683 | message: "expected a numeric value for explicitVal" ); |
| 684 | return {}; |
| 685 | } |
| 686 | break; |
| 687 | } |
| 688 | case 4: { // implicitVal |
| 689 | Attribute attr; |
| 690 | if (failed(Result: parser.parseAttribute(result&: attr))) |
| 691 | return {}; |
| 692 | if (auto result = llvm::dyn_cast<FloatAttr>(Val&: attr)) { |
| 693 | implicitVal = result; |
| 694 | } else if (auto result = llvm::dyn_cast<IntegerAttr>(Val&: attr)) { |
| 695 | implicitVal = result; |
| 696 | } else if (auto result = llvm::dyn_cast<complex::NumberAttr>(Val&: attr)) { |
| 697 | implicitVal = result; |
| 698 | } else { |
| 699 | parser.emitError(loc: parser.getNameLoc(), |
| 700 | message: "expected a numeric value for implicitVal" ); |
| 701 | return {}; |
| 702 | } |
| 703 | break; |
| 704 | } |
| 705 | } // switch |
| 706 | // Only last item can omit the comma. |
| 707 | if (parser.parseOptionalComma().failed()) |
| 708 | break; |
| 709 | } |
| 710 | |
| 711 | // Close "}>" part. |
| 712 | if (failed(Result: parser.parseRBrace())) |
| 713 | return {}; |
| 714 | if (failed(Result: parser.parseGreater())) |
| 715 | return {}; |
| 716 | |
| 717 | // Construct struct-like storage for attribute. |
| 718 | if (!lvlToDim || lvlToDim.isEmpty()) { |
| 719 | lvlToDim = inferLvlToDim(dimToLvl, context: parser.getContext()); |
| 720 | } |
| 721 | return parser.getChecked<SparseTensorEncodingAttr>( |
| 722 | params: parser.getContext(), params&: lvlTypes, params&: dimToLvl, params&: lvlToDim, params&: posWidth, params&: crdWidth, |
| 723 | params&: explicitVal, params&: implicitVal, params&: dimSlices); |
| 724 | } |
| 725 | |
| 726 | void SparseTensorEncodingAttr::print(AsmPrinter &printer) const { |
| 727 | auto map = static_cast<AffineMap>(getDimToLvl()); |
| 728 | // Empty affine map indicates identity map |
| 729 | if (!map) |
| 730 | map = AffineMap::getMultiDimIdentityMap(numDims: getLvlTypes().size(), context: getContext()); |
| 731 | printer << "<{ map = " ; |
| 732 | printSymbols(map, printer); |
| 733 | printer << '('; |
| 734 | printDimensions(map, printer, dimSlices: getDimSlices()); |
| 735 | printer << ") -> (" ; |
| 736 | printLevels(map, printer, lvlTypes: getLvlTypes()); |
| 737 | printer << ')'; |
| 738 | // Print remaining members only for non-default values. |
| 739 | if (getPosWidth()) |
| 740 | printer << ", posWidth = " << getPosWidth(); |
| 741 | if (getCrdWidth()) |
| 742 | printer << ", crdWidth = " << getCrdWidth(); |
| 743 | if (getExplicitVal()) { |
| 744 | printer << ", explicitVal = " << getExplicitVal(); |
| 745 | } |
| 746 | if (getImplicitVal()) |
| 747 | printer << ", implicitVal = " << getImplicitVal(); |
| 748 | printer << " }>" ; |
| 749 | } |
| 750 | |
| 751 | void SparseTensorEncodingAttr::printSymbols(AffineMap &map, |
| 752 | AsmPrinter &printer) const { |
| 753 | if (map.getNumSymbols() == 0) |
| 754 | return; |
| 755 | printer << '['; |
| 756 | for (unsigned i = 0, n = map.getNumSymbols() - 1; i < n; i++) |
| 757 | printer << 's' << i << ", " ; |
| 758 | if (map.getNumSymbols() >= 1) |
| 759 | printer << 's' << map.getNumSymbols() - 1; |
| 760 | printer << ']'; |
| 761 | } |
| 762 | |
| 763 | void SparseTensorEncodingAttr::printDimensions( |
| 764 | AffineMap &map, AsmPrinter &printer, |
| 765 | ArrayRef<SparseTensorDimSliceAttr> dimSlices) const { |
| 766 | if (!dimSlices.empty()) { |
| 767 | for (unsigned i = 0, n = map.getNumDims() - 1; i < n; i++) |
| 768 | printer << 'd' << i << " : " << dimSlices[i] << ", " ; |
| 769 | if (map.getNumDims() >= 1) { |
| 770 | printer << 'd' << map.getNumDims() - 1 << " : " |
| 771 | << dimSlices[map.getNumDims() - 1]; |
| 772 | } |
| 773 | } else { |
| 774 | for (unsigned i = 0, n = map.getNumDims() - 1; i < n; i++) |
| 775 | printer << 'd' << i << ", " ; |
| 776 | if (map.getNumDims() >= 1) |
| 777 | printer << 'd' << map.getNumDims() - 1; |
| 778 | } |
| 779 | } |
| 780 | |
| 781 | void SparseTensorEncodingAttr::printLevels(AffineMap &map, AsmPrinter &printer, |
| 782 | ArrayRef<LevelType> lvlTypes) const { |
| 783 | for (unsigned i = 0, n = map.getNumResults() - 1; i < n; i++) { |
| 784 | map.getResult(idx: i).print(os&: printer.getStream()); |
| 785 | printer << " : " << toMLIRString(lt: lvlTypes[i]) << ", " ; |
| 786 | } |
| 787 | if (map.getNumResults() >= 1) { |
| 788 | auto lastIndex = map.getNumResults() - 1; |
| 789 | map.getResult(idx: lastIndex).print(os&: printer.getStream()); |
| 790 | printer << " : " << toMLIRString(lt: lvlTypes[lastIndex]); |
| 791 | } |
| 792 | } |
| 793 | |
| 794 | LogicalResult SparseTensorEncodingAttr::verify( |
| 795 | function_ref<InFlightDiagnostic()> emitError, ArrayRef<LevelType> lvlTypes, |
| 796 | AffineMap dimToLvl, AffineMap lvlToDim, unsigned posWidth, |
| 797 | unsigned crdWidth, Attribute explicitVal, Attribute implicitVal, |
| 798 | ArrayRef<SparseTensorDimSliceAttr> dimSlices) { |
| 799 | if (!acceptBitWidth(bitWidth: posWidth)) |
| 800 | return emitError() << "unexpected position bitwidth: " << posWidth; |
| 801 | if (!acceptBitWidth(bitWidth: crdWidth)) |
| 802 | return emitError() << "unexpected coordinate bitwidth: " << crdWidth; |
| 803 | |
| 804 | // Verify every COO segment. |
| 805 | auto *it = llvm::find_if(Range&: lvlTypes, P: isSingletonLT); |
| 806 | while (it != lvlTypes.end()) { |
| 807 | if (it == lvlTypes.begin() || |
| 808 | !(it - 1)->isa<LevelFormat::Compressed, LevelFormat::LooseCompressed>()) |
| 809 | return emitError() << "expected compressed or loose_compressed level " |
| 810 | "before singleton level" ; |
| 811 | |
| 812 | auto *curCOOEnd = std::find_if_not(first: it, last: lvlTypes.end(), pred: isSingletonLT); |
| 813 | if (!std::all_of(first: it, last: curCOOEnd, pred: isSingletonLT)) |
| 814 | return emitError() << "expected all singleton lvlTypes " |
| 815 | "following a singleton level" ; |
| 816 | // We can potentially support mixed SoA/AoS singleton levels. |
| 817 | if (!std::all_of(first: it, last: curCOOEnd, pred: [it](LevelType i) { |
| 818 | return it->isa<LevelPropNonDefault::SoA>() == |
| 819 | i.isa<LevelPropNonDefault::SoA>(); |
| 820 | })) { |
| 821 | return emitError() << "expected all singleton lvlTypes stored in the " |
| 822 | "same memory layout (SoA vs AoS)." ; |
| 823 | } |
| 824 | it = std::find_if(first: curCOOEnd, last: lvlTypes.end(), pred: isSingletonLT); |
| 825 | } |
| 826 | |
| 827 | auto lastBatch = std::find_if(first: lvlTypes.rbegin(), last: lvlTypes.rend(), pred: isBatchLT); |
| 828 | if (!std::all_of(first: lastBatch, last: lvlTypes.rend(), pred: isBatchLT)) |
| 829 | return emitError() << "Batch lvlType can only be leading levels." ; |
| 830 | |
| 831 | // SoA property can only be applied on singleton level. |
| 832 | auto soaLvls = llvm::make_filter_range(Range&: lvlTypes, Pred: [](LevelType lt) { |
| 833 | return lt.isa<LevelPropNonDefault::SoA>(); |
| 834 | }); |
| 835 | if (llvm::any_of(Range&: soaLvls, P: [](LevelType lt) { |
| 836 | return !lt.isa<LevelFormat::Singleton>(); |
| 837 | })) { |
| 838 | return emitError() << "SoA is only applicable to singleton lvlTypes." ; |
| 839 | } |
| 840 | |
| 841 | // Dense levels cannot follow a non-unique level. The iteration model for |
| 842 | // dense levels requires exactly one parent position to linearize into a |
| 843 | // contiguous range, but a non-unique parent provides two cursor values |
| 844 | // (segment start and end), which the dense level cannot handle. |
| 845 | for (auto [i, lt] : llvm::drop_begin(RangeOrContainer: llvm::enumerate(First&: lvlTypes))) { |
| 846 | if (isDenseLT(lt) && !isUniqueLT(lt: lvlTypes[i - 1])) |
| 847 | return emitError() << "dense level cannot follow a non-unique level" ; |
| 848 | } |
| 849 | |
| 850 | // TODO: audit formats that actually are supported by backend. |
| 851 | if (auto it = llvm::find_if(Range&: lvlTypes, P: isNOutOfMLT); |
| 852 | it != std::end(cont&: lvlTypes)) { |
| 853 | if (it != lvlTypes.end() - 1) |
| 854 | return emitError() << "expected n_out_of_m to be the last level type" ; |
| 855 | if (!std::all_of(first: lvlTypes.begin(), last: it, pred: isDenseLT)) |
| 856 | return emitError() << "expected all dense lvlTypes " |
| 857 | "before a n_out_of_m level" ; |
| 858 | if (dimToLvl && (dimToLvl.getNumDims() != dimToLvl.getNumResults())) { |
| 859 | if (!isBlockSparsity(dimToLvl)) { |
| 860 | return emitError() |
| 861 | << "expected 1xm block structure for n_out_of_m level" ; |
| 862 | } |
| 863 | auto sizes = getBlockSize(dimToLvl); |
| 864 | unsigned coefficient = 0; |
| 865 | for (const auto &elem : sizes) { |
| 866 | if (elem != 0) { |
| 867 | if (elem != coefficient && coefficient != 0) { |
| 868 | return emitError() << "expected only one blocked level " |
| 869 | "with the same coefficients" ; |
| 870 | } |
| 871 | coefficient = elem; |
| 872 | } |
| 873 | } |
| 874 | if (coefficient != getM(lt: *it)) { |
| 875 | return emitError() << "expected coeffiencts of Affine expressions " |
| 876 | "to be equal to m of n_out_of_m level" ; |
| 877 | } |
| 878 | } |
| 879 | } |
| 880 | // Before we can check that the level-rank is consistent/coherent |
| 881 | // across all fields, we need to define it. The source-of-truth for |
| 882 | // the `getLvlRank` method is the length of the level-types array, |
| 883 | // since it must always be provided and have full rank; therefore we |
| 884 | // use that same source-of-truth here. |
| 885 | const Level lvlRank = lvlTypes.size(); |
| 886 | if (lvlRank == 0) |
| 887 | return emitError() << "expected a non-empty array for lvlTypes" ; |
| 888 | // We save `dimRank` here because we'll also need it to verify `dimSlices`. |
| 889 | const Dimension dimRank = dimToLvl ? dimToLvl.getNumDims() : lvlRank; |
| 890 | if (dimToLvl) { |
| 891 | if (dimToLvl.getNumResults() != lvlRank) |
| 892 | return emitError() |
| 893 | << "level-rank mismatch between dimToLvl and lvlTypes: " |
| 894 | << dimToLvl.getNumResults() << " != " << lvlRank; |
| 895 | auto inferRes = inferLvlToDim(dimToLvl, context: dimToLvl.getContext()); |
| 896 | // Symbols can't be inferred but are acceptable. |
| 897 | if (!inferRes && dimToLvl.getNumSymbols() == 0) |
| 898 | return emitError() << "failed to infer lvlToDim from dimToLvl" ; |
| 899 | if (lvlToDim && (inferRes != lvlToDim)) |
| 900 | return emitError() << "expected lvlToDim to be an inverse of dimToLvl" ; |
| 901 | if (dimRank > lvlRank) |
| 902 | return emitError() << "unexpected dimToLvl mapping from " << dimRank |
| 903 | << " to " << lvlRank; |
| 904 | } |
| 905 | if (!dimSlices.empty()) { |
| 906 | if (dimSlices.size() != dimRank) |
| 907 | return emitError() |
| 908 | << "dimension-rank mismatch between dimSlices and dimToLvl: " |
| 909 | << dimSlices.size() << " != " << dimRank; |
| 910 | // Compiler support for `dimSlices` currently requires that the two |
| 911 | // ranks agree. (However, it does allow `dimToLvl` to be a permutation.) |
| 912 | if (dimRank != lvlRank) |
| 913 | return emitError() |
| 914 | << "dimSlices expected dimension-rank to match level-rank: " |
| 915 | << dimRank << " != " << lvlRank; |
| 916 | } |
| 917 | return success(); |
| 918 | } |
| 919 | |
| 920 | static bool isValidPrimaryType(Type elemTp) { |
| 921 | if (elemTp.isF64() || elemTp.isF32() || elemTp.isF16() || elemTp.isBF16() || |
| 922 | elemTp.isInteger(width: 64) || elemTp.isInteger(width: 32) || elemTp.isInteger(width: 16) || |
| 923 | elemTp.isInteger(width: 8)) |
| 924 | return true; |
| 925 | if (auto complexTp = dyn_cast<ComplexType>(Val&: elemTp)) { |
| 926 | Type elt = complexTp.getElementType(); |
| 927 | return elt.isF64() || elt.isF32(); |
| 928 | } |
| 929 | return false; |
| 930 | } |
| 931 | |
| 932 | LogicalResult SparseTensorEncodingAttr::verifyEncoding( |
| 933 | ArrayRef<Size> dimShape, Type elementType, |
| 934 | function_ref<InFlightDiagnostic()> emitError) const { |
| 935 | // Check structural integrity. In particular, this ensures that the |
| 936 | // level-rank is coherent across all the fields. |
| 937 | if (failed(Result: verify(emitError, lvlTypes: getLvlTypes(), dimToLvl: getDimToLvl(), lvlToDim: getLvlToDim(), |
| 938 | posWidth: getPosWidth(), crdWidth: getCrdWidth(), explicitVal: getExplicitVal(), |
| 939 | implicitVal: getImplicitVal(), dimSlices: getDimSlices()))) |
| 940 | return failure(); |
| 941 | // Check integrity with tensor type specifics. In particular, we |
| 942 | // need only check that the dimension-rank of the tensor agrees with |
| 943 | // the dimension-rank of the encoding. |
| 944 | const Dimension dimRank = dimShape.size(); |
| 945 | if (dimRank == 0) |
| 946 | return emitError() << "expected non-scalar sparse tensor" ; |
| 947 | if (getDimRank() != dimRank) |
| 948 | return emitError() |
| 949 | << "dimension-rank mismatch between encoding and tensor shape: " |
| 950 | << getDimRank() << " != " << dimRank; |
| 951 | if (auto expVal = getExplicitVal()) { |
| 952 | Type attrType = llvm::dyn_cast<TypedAttr>(Val&: expVal).getType(); |
| 953 | if (attrType != elementType) { |
| 954 | return emitError() << "explicit value type mismatch between encoding and " |
| 955 | << "tensor element type: " << attrType |
| 956 | << " != " << elementType; |
| 957 | } |
| 958 | } |
| 959 | if (auto impVal = getImplicitVal()) { |
| 960 | Type attrType = llvm::dyn_cast<TypedAttr>(Val&: impVal).getType(); |
| 961 | if (attrType != elementType) { |
| 962 | return emitError() << "implicit value type mismatch between encoding and " |
| 963 | << "tensor element type: " << attrType |
| 964 | << " != " << elementType; |
| 965 | } |
| 966 | // Currently, we only support zero as the implicit value. |
| 967 | auto impFVal = llvm::dyn_cast<FloatAttr>(Val&: impVal); |
| 968 | auto impIntVal = llvm::dyn_cast<IntegerAttr>(Val&: impVal); |
| 969 | auto impComplexVal = llvm::dyn_cast<complex::NumberAttr>(Val&: impVal); |
| 970 | if ((impFVal && impFVal.getValue().isNonZero()) || |
| 971 | (impIntVal && !impIntVal.getValue().isZero()) || |
| 972 | (impComplexVal && (impComplexVal.getImag().isNonZero() || |
| 973 | impComplexVal.getReal().isNonZero()))) { |
| 974 | return emitError() << "implicit value must be zero" ; |
| 975 | } |
| 976 | } |
| 977 | if (!isValidPrimaryType(elemTp: elementType)) |
| 978 | return emitError() << "invalid primary type" ; |
| 979 | return success(); |
| 980 | } |
| 981 | |
| 982 | Level mlir::sparse_tensor::SparseTensorEncodingAttr::getAoSCOOStart() const { |
| 983 | SmallVector<COOSegment> coo = getCOOSegments(); |
| 984 | assert(coo.size() == 1 || coo.empty()); |
| 985 | if (!coo.empty() && coo.front().isAoS()) { |
| 986 | return coo.front().lvlRange.first; |
| 987 | } |
| 988 | return getLvlRank(); |
| 989 | } |
| 990 | |
| 991 | SmallVector<COOSegment> |
| 992 | mlir::sparse_tensor::SparseTensorEncodingAttr::getCOOSegments() const { |
| 993 | SmallVector<COOSegment> ret; |
| 994 | if (getLvlRank() <= 1) |
| 995 | return ret; |
| 996 | |
| 997 | ArrayRef<LevelType> lts = getLvlTypes(); |
| 998 | Level l = 0; |
| 999 | while (l < getLvlRank()) { |
| 1000 | auto lt = lts[l]; |
| 1001 | if (lt.isa<LevelFormat::Compressed, LevelFormat::LooseCompressed>()) { |
| 1002 | auto cur = lts.begin() + l; |
| 1003 | auto end = std::find_if(first: cur + 1, last: lts.end(), pred: [](LevelType lt) { |
| 1004 | return !lt.isa<LevelFormat::Singleton>(); |
| 1005 | }); |
| 1006 | unsigned cooLen = std::distance(first: cur, last: end); |
| 1007 | if (cooLen > 1) { |
| 1008 | // To support mixed SoA/AoS COO, we should break the segment when the |
| 1009 | // storage scheme changes, for now we faithfully assume that all |
| 1010 | // consecutive singleton levels have the same storage format as verified |
| 1011 | // STEA. |
| 1012 | ret.push_back(Elt: COOSegment{.lvlRange: std::make_pair(x&: l, y: l + cooLen), |
| 1013 | .isSoA: lts[l + 1].isa<LevelPropNonDefault::SoA>()}); |
| 1014 | } |
| 1015 | l += cooLen; |
| 1016 | } else { |
| 1017 | l++; |
| 1018 | } |
| 1019 | } |
| 1020 | return ret; |
| 1021 | } |
| 1022 | |
| 1023 | //===----------------------------------------------------------------------===// |
| 1024 | // SparseTensorType Methods. |
| 1025 | //===----------------------------------------------------------------------===// |
| 1026 | |
| 1027 | bool mlir::sparse_tensor::SparseTensorType::isCOOType(Level startLvl, |
| 1028 | bool isUnique) const { |
| 1029 | if (!hasEncoding()) |
| 1030 | return false; |
| 1031 | if (!isCompressedLvl(l: startLvl) && !isLooseCompressedLvl(l: startLvl)) |
| 1032 | return false; |
| 1033 | for (Level l = startLvl + 1; l < lvlRank; ++l) |
| 1034 | if (!isSingletonLvl(l)) |
| 1035 | return false; |
| 1036 | // If isUnique is true, then make sure that the last level is unique, |
| 1037 | // that is, when lvlRank == 1, the only compressed level is unique, |
| 1038 | // and when lvlRank > 1, the last singleton is unique. |
| 1039 | return !isUnique || isUniqueLvl(l: lvlRank - 1); |
| 1040 | } |
| 1041 | |
| 1042 | RankedTensorType |
| 1043 | mlir::sparse_tensor::SparseTensorType::getCOOType(bool ordered) const { |
| 1044 | SmallVector<LevelType> lvlTypes; |
| 1045 | lvlTypes.reserve(N: lvlRank); |
| 1046 | // A non-unique compressed level at beginning (unless this is |
| 1047 | // also the last level, then it is unique). |
| 1048 | lvlTypes.push_back( |
| 1049 | Elt: *buildLevelType(lf: LevelFormat::Compressed, ordered, unique: lvlRank == 1)); |
| 1050 | if (lvlRank > 1) { |
| 1051 | // Followed by n-2 non-unique singleton levels. |
| 1052 | std::fill_n(first: std::back_inserter(x&: lvlTypes), n: lvlRank - 2, |
| 1053 | value: *buildLevelType(lf: LevelFormat::Singleton, ordered, unique: false)); |
| 1054 | // Ends by a unique singleton level. |
| 1055 | lvlTypes.push_back(Elt: *buildLevelType(lf: LevelFormat::Singleton, ordered, unique: true)); |
| 1056 | } |
| 1057 | auto enc = SparseTensorEncodingAttr::get( |
| 1058 | context: getContext(), lvlTypes, dimToLvl: getDimToLvl(), lvlToDim: getLvlToDim(), posWidth: getPosWidth(), |
| 1059 | crdWidth: getCrdWidth(), explicitVal: getExplicitVal(), implicitVal: getImplicitVal()); |
| 1060 | return RankedTensorType::get(shape: getDimShape(), elementType: getElementType(), encoding: enc); |
| 1061 | } |
| 1062 | |
| 1063 | //===----------------------------------------------------------------------===// |
| 1064 | // Convenience Methods. |
| 1065 | //===----------------------------------------------------------------------===// |
| 1066 | |
| 1067 | SparseTensorEncodingAttr |
| 1068 | mlir::sparse_tensor::getSparseTensorEncoding(Type type) { |
| 1069 | if (auto ttp = llvm::dyn_cast<RankedTensorType>(Val&: type)) |
| 1070 | return llvm::dyn_cast_or_null<SparseTensorEncodingAttr>(Val: ttp.getEncoding()); |
| 1071 | if (auto mdtp = llvm::dyn_cast<StorageSpecifierType>(Val&: type)) |
| 1072 | return mdtp.getEncoding(); |
| 1073 | return nullptr; |
| 1074 | } |
| 1075 | |
| 1076 | AffineMap mlir::sparse_tensor::inferLvlToDim(AffineMap dimToLvl, |
| 1077 | MLIRContext *context) { |
| 1078 | auto map = static_cast<AffineMap>(dimToLvl); |
| 1079 | AffineMap lvlToDim; |
| 1080 | // Return an empty lvlToDim when inference is not successful. |
| 1081 | if (!map || map.getNumSymbols() != 0) { |
| 1082 | lvlToDim = AffineMap(); |
| 1083 | } else if (map.isPermutation()) { |
| 1084 | lvlToDim = inversePermutation(map); |
| 1085 | } else if (isBlockSparsity(dimToLvl: map)) { |
| 1086 | lvlToDim = inverseBlockSparsity(dimToLvl: map, context); |
| 1087 | } |
| 1088 | return lvlToDim; |
| 1089 | } |
| 1090 | |
| 1091 | AffineMap mlir::sparse_tensor::inverseBlockSparsity(AffineMap dimToLvl, |
| 1092 | MLIRContext *context) { |
| 1093 | // The results of lvlToDim follow the dimension order, so the vector is |
| 1094 | // filled by dimension position rather than by expression kind. |
| 1095 | SmallVector<AffineExpr> lvlExprs(dimToLvl.getNumDims()); |
| 1096 | auto numLvls = dimToLvl.getNumResults(); |
| 1097 | // lvlExprComponents stores information of the floordiv and mod operations |
| 1098 | // applied to the same dimension, so as to build the lvlToDim map. |
| 1099 | std::map<unsigned, SmallVector<AffineExpr, 3>> lvlExprComponents; |
| 1100 | for (unsigned i = 0, n = numLvls; i < n; i++) { |
| 1101 | auto result = dimToLvl.getResult(idx: i); |
| 1102 | if (auto binOp = dyn_cast<AffineBinaryOpExpr>(Val&: result)) { |
| 1103 | if (result.getKind() == AffineExprKind::FloorDiv) { |
| 1104 | // Position of the dimension in dimToLvl. |
| 1105 | auto pos = dyn_cast<AffineDimExpr>(Val: binOp.getLHS()).getPosition(); |
| 1106 | assert(lvlExprComponents.find(pos) == lvlExprComponents.end() && |
| 1107 | "expected only one floordiv for each dimension" ); |
| 1108 | SmallVector<AffineExpr, 3> components; |
| 1109 | // Level variable for floordiv. |
| 1110 | components.push_back(Elt: getAffineDimExpr(position: i, context)); |
| 1111 | // Multiplier. |
| 1112 | components.push_back(Elt: binOp.getRHS()); |
| 1113 | // Map key is the position of the dimension. |
| 1114 | lvlExprComponents[pos] = components; |
| 1115 | } else if (result.getKind() == AffineExprKind::Mod) { |
| 1116 | auto pos = dyn_cast<AffineDimExpr>(Val: binOp.getLHS()).getPosition(); |
| 1117 | assert(lvlExprComponents.find(pos) != lvlExprComponents.end() && |
| 1118 | "expected floordiv before mod" ); |
| 1119 | // Add level variable for mod to the same vector |
| 1120 | // of the corresponding floordiv. |
| 1121 | lvlExprComponents[pos].push_back(Elt: getAffineDimExpr(position: i, context)); |
| 1122 | } else { |
| 1123 | assert(false && "expected floordiv or mod" ); |
| 1124 | } |
| 1125 | } else { |
| 1126 | auto pos = cast<AffineDimExpr>(Val&: result).getPosition(); |
| 1127 | lvlExprs[pos] = getAffineDimExpr(position: i, context); |
| 1128 | } |
| 1129 | } |
| 1130 | // Build lvlExprs from lvlExprComponents. |
| 1131 | // For example, for il = i floordiv 2 and ii = i mod 2, the components |
| 1132 | // would be [il, 2, ii]. It could be used to build the AffineExpr |
| 1133 | // i = il * 2 + ii in lvlToDim. |
| 1134 | for (auto &components : lvlExprComponents) { |
| 1135 | assert(components.second.size() == 3 && |
| 1136 | "expected 3 components to build lvlExprs" ); |
| 1137 | auto mulOp = getAffineBinaryOpExpr( |
| 1138 | kind: AffineExprKind::Mul, lhs: components.second[0], rhs: components.second[1]); |
| 1139 | auto addOp = |
| 1140 | getAffineBinaryOpExpr(kind: AffineExprKind::Add, lhs: mulOp, rhs: components.second[2]); |
| 1141 | lvlExprs[components.first] = addOp; |
| 1142 | } |
| 1143 | // Dimensions that do not appear in dimToLvl (this is also applied to |
| 1144 | // indexing maps) get no result. |
| 1145 | llvm::erase_if(C&: lvlExprs, P: [](AffineExpr expr) { return !expr; }); |
| 1146 | return dimToLvl.get(dimCount: dimToLvl.getNumResults(), symbolCount: 0, results: lvlExprs, context); |
| 1147 | } |
| 1148 | |
| 1149 | SmallVector<unsigned> mlir::sparse_tensor::getBlockSize(AffineMap dimToLvl) { |
| 1150 | assert(isBlockSparsity(dimToLvl) && |
| 1151 | "expected dimToLvl to be block sparsity for calling getBlockSize" ); |
| 1152 | SmallVector<unsigned> blockSize; |
| 1153 | for (auto result : dimToLvl.getResults()) { |
| 1154 | if (auto binOp = dyn_cast<AffineBinaryOpExpr>(Val&: result)) { |
| 1155 | if (result.getKind() == AffineExprKind::Mod) { |
| 1156 | blockSize.push_back( |
| 1157 | Elt: dyn_cast<AffineConstantExpr>(Val: binOp.getRHS()).getValue()); |
| 1158 | } |
| 1159 | } else { |
| 1160 | blockSize.push_back(Elt: 0); |
| 1161 | } |
| 1162 | } |
| 1163 | return blockSize; |
| 1164 | } |
| 1165 | |
| 1166 | bool mlir::sparse_tensor::isBlockSparsity(AffineMap dimToLvl) { |
| 1167 | if (!dimToLvl) |
| 1168 | return false; |
| 1169 | std::map<unsigned, int64_t> coeffientMap; |
| 1170 | bool hasBlock = false; |
| 1171 | for (auto result : dimToLvl.getResults()) { |
| 1172 | if (auto binOp = dyn_cast<AffineBinaryOpExpr>(Val&: result)) { |
| 1173 | // Check for "dim op const". |
| 1174 | auto dimOp = dyn_cast<AffineDimExpr>(Val: binOp.getLHS()); |
| 1175 | auto conOp = dyn_cast<AffineConstantExpr>(Val: binOp.getRHS()); |
| 1176 | if (!dimOp || !conOp || conOp.getValue() <= 0) |
| 1177 | return false; |
| 1178 | // Inspect "dim / const" or "dim % const". |
| 1179 | auto pos = dimOp.getPosition(); |
| 1180 | if (binOp.getKind() == AffineExprKind::FloorDiv) { |
| 1181 | // Expect only one floordiv for each dimension. |
| 1182 | auto [it, inserted] = coeffientMap.try_emplace(k: pos); |
| 1183 | if (!inserted) |
| 1184 | return false; |
| 1185 | // Record coefficient of the floordiv. |
| 1186 | it->second = conOp.getValue(); |
| 1187 | } else if (binOp.getKind() == AffineExprKind::Mod) { |
| 1188 | // Expect floordiv before mod. |
| 1189 | auto it = coeffientMap.find(x: pos); |
| 1190 | if (it == coeffientMap.end()) |
| 1191 | return false; |
| 1192 | // Expect mod to have the same coefficient as floordiv. |
| 1193 | if (conOp.getValue() != it->second) |
| 1194 | return false; |
| 1195 | hasBlock = true; |
| 1196 | } else { |
| 1197 | return false; |
| 1198 | } |
| 1199 | } else if (auto dimOp = dyn_cast<AffineDimExpr>(Val&: result)) { |
| 1200 | auto pos = dimOp.getPosition(); |
| 1201 | // Expect dim to be unset. |
| 1202 | if (!coeffientMap.try_emplace(k: pos, args: 0).second) |
| 1203 | return false; |
| 1204 | } else { |
| 1205 | return false; |
| 1206 | } |
| 1207 | } |
| 1208 | return hasBlock; |
| 1209 | } |
| 1210 | |
| 1211 | bool mlir::sparse_tensor::hasAnyNonIdentityOperandsOrResults(Operation *op) { |
| 1212 | auto hasNonIdentityMap = [](Value v) { |
| 1213 | auto stt = tryGetSparseTensorType(val: v); |
| 1214 | return stt && !stt->isIdentity(); |
| 1215 | }; |
| 1216 | |
| 1217 | return llvm::any_of(Range: op->getOperands(), P: hasNonIdentityMap) || |
| 1218 | llvm::any_of(Range: op->getResults(), P: hasNonIdentityMap); |
| 1219 | } |
| 1220 | |
| 1221 | Dimension mlir::sparse_tensor::toDim(SparseTensorEncodingAttr enc, Level l) { |
| 1222 | if (enc) { |
| 1223 | assert(enc.isPermutation() && "Non permutation map not supported" ); |
| 1224 | if (const auto dimToLvl = enc.getDimToLvl()) |
| 1225 | return dimToLvl.getDimPosition(idx: l); |
| 1226 | } |
| 1227 | return l; |
| 1228 | } |
| 1229 | |
| 1230 | Level mlir::sparse_tensor::toLvl(SparseTensorEncodingAttr enc, Dimension d) { |
| 1231 | if (enc) { |
| 1232 | assert(enc.isPermutation() && "Non permutation map not supported" ); |
| 1233 | if (const auto lvlToDim = enc.getLvlToDim()) |
| 1234 | return lvlToDim.getDimPosition(idx: d); |
| 1235 | } |
| 1236 | return d; |
| 1237 | } |
| 1238 | |
| 1239 | /// We normalized sparse tensor encoding attribute by always using |
| 1240 | /// ordered/unique LT such that "compressed_nu_no" and "compressed_nu" (as well |
| 1241 | /// as other variants) lead to the same storage specifier type, and stripping |
| 1242 | /// irrelevant fields that do not alter the sparse tensor memory layout. |
| 1243 | static SparseTensorEncodingAttr |
| 1244 | getNormalizedEncodingForSpecifier(SparseTensorEncodingAttr enc) { |
| 1245 | SmallVector<LevelType> lts; |
| 1246 | for (auto lt : enc.getLvlTypes()) |
| 1247 | lts.push_back(Elt: lt.stripStorageIrrelevantProperties()); |
| 1248 | |
| 1249 | return SparseTensorEncodingAttr::get( |
| 1250 | context: enc.getContext(), lvlTypes: lts, |
| 1251 | dimToLvl: AffineMap(), // dimToLvl (irrelevant to storage specifier) |
| 1252 | lvlToDim: AffineMap(), // lvlToDim (irrelevant to storage specifier) |
| 1253 | // Always use `index` for memSize and lvlSize instead of reusing |
| 1254 | // `getPosWidth` and `getCrdWidth`. It allows us to reuse the same SSA |
| 1255 | // value for different bitwidth, it also avoids casting between index and |
| 1256 | // integer (returned by DimOp) |
| 1257 | posWidth: 0, crdWidth: 0, |
| 1258 | explicitVal: Attribute(), // explicitVal (irrelevant to storage specifier) |
| 1259 | implicitVal: Attribute(), // implicitVal (irrelevant to storage specifier) |
| 1260 | dimSlices: enc.getDimSlices()); |
| 1261 | } |
| 1262 | |
| 1263 | StorageSpecifierType |
| 1264 | StorageSpecifierType::get(MLIRContext *ctx, SparseTensorEncodingAttr encoding) { |
| 1265 | return Base::get(ctx, args: getNormalizedEncodingForSpecifier(enc: encoding)); |
| 1266 | } |
| 1267 | |
| 1268 | StorageSpecifierType |
| 1269 | StorageSpecifierType::getChecked(function_ref<InFlightDiagnostic()> emitError, |
| 1270 | MLIRContext *ctx, |
| 1271 | SparseTensorEncodingAttr encoding) { |
| 1272 | return Base::getChecked(emitErrorFn: emitError, ctx, |
| 1273 | args: getNormalizedEncodingForSpecifier(enc: encoding)); |
| 1274 | } |
| 1275 | |
| 1276 | //===----------------------------------------------------------------------===// |
| 1277 | // SparseTensorDialect Operations. |
| 1278 | //===----------------------------------------------------------------------===// |
| 1279 | |
| 1280 | static LogicalResult lvlIsInBounds(Level lvl, Value tensor) { |
| 1281 | return success(IsSuccess: lvl < getSparseTensorType(val: tensor).getLvlRank()); |
| 1282 | } |
| 1283 | |
| 1284 | static LogicalResult isMatchingWidth(Value mem, unsigned width) { |
| 1285 | const Type etp = getMemRefType(t&: mem).getElementType(); |
| 1286 | return success(IsSuccess: width == 0 ? etp.isIndex() : etp.isInteger(width)); |
| 1287 | } |
| 1288 | |
| 1289 | static LogicalResult verifySparsifierGetterSetter( |
| 1290 | StorageSpecifierKind mdKind, std::optional<Level> lvl, |
| 1291 | TypedValue<StorageSpecifierType> md, Operation *op) { |
| 1292 | if (mdKind == StorageSpecifierKind::ValMemSize && lvl) { |
| 1293 | return op->emitError( |
| 1294 | message: "redundant level argument for querying value memory size" ); |
| 1295 | } |
| 1296 | |
| 1297 | const auto enc = md.getType().getEncoding(); |
| 1298 | const Level lvlRank = enc.getLvlRank(); |
| 1299 | |
| 1300 | if (mdKind == StorageSpecifierKind::DimOffset || |
| 1301 | mdKind == StorageSpecifierKind::DimStride) |
| 1302 | if (!enc.isSlice()) |
| 1303 | return op->emitError(message: "requested slice data on non-slice tensor" ); |
| 1304 | |
| 1305 | if (mdKind != StorageSpecifierKind::ValMemSize) { |
| 1306 | if (!lvl) |
| 1307 | return op->emitError(message: "missing level argument" ); |
| 1308 | |
| 1309 | const Level l = lvl.value(); |
| 1310 | if (l >= lvlRank) |
| 1311 | return op->emitError(message: "requested level is out of bounds" ); |
| 1312 | |
| 1313 | if (mdKind == StorageSpecifierKind::PosMemSize && enc.isSingletonLvl(l)) |
| 1314 | return op->emitError( |
| 1315 | message: "requested position memory size on a singleton level" ); |
| 1316 | } |
| 1317 | return success(); |
| 1318 | } |
| 1319 | |
| 1320 | static Type getFieldElemType(SparseTensorType stt, SparseTensorFieldKind kind) { |
| 1321 | switch (kind) { |
| 1322 | case SparseTensorFieldKind::CrdMemRef: |
| 1323 | return stt.getCrdType(); |
| 1324 | case SparseTensorFieldKind::PosMemRef: |
| 1325 | return stt.getPosType(); |
| 1326 | case SparseTensorFieldKind::ValMemRef: |
| 1327 | return stt.getElementType(); |
| 1328 | case SparseTensorFieldKind::StorageSpec: |
| 1329 | return nullptr; |
| 1330 | } |
| 1331 | llvm_unreachable("Unrecognizable FieldKind" ); |
| 1332 | } |
| 1333 | |
| 1334 | static LogicalResult verifyPackUnPack(Operation *op, bool requiresStaticShape, |
| 1335 | SparseTensorType stt, |
| 1336 | RankedTensorType valTp, |
| 1337 | TypeRange lvlTps) { |
| 1338 | if (requiresStaticShape && !stt.hasStaticDimShape()) |
| 1339 | return op->emitError(message: "the sparse-tensor must have static shape" ); |
| 1340 | if (!stt.hasEncoding()) |
| 1341 | return op->emitError(message: "the sparse-tensor must have an encoding attribute" ); |
| 1342 | |
| 1343 | // Verifies the trailing COO. |
| 1344 | Level cooStartLvl = stt.getAoSCOOStart(); |
| 1345 | if (cooStartLvl < stt.getLvlRank()) { |
| 1346 | // We only supports trailing COO for now, must be the last input. |
| 1347 | auto cooTp = llvm::cast<ShapedType>(Val: lvlTps.back()); |
| 1348 | // The coordinates should be in shape of <? x rank> |
| 1349 | unsigned expCOORank = stt.getLvlRank() - cooStartLvl; |
| 1350 | if (cooTp.getRank() != 2 || expCOORank != cooTp.getShape().back()) { |
| 1351 | return op->emitError(message: "input/output trailing COO level-ranks don't match" ); |
| 1352 | } |
| 1353 | } |
| 1354 | |
| 1355 | // Verifies that all types match. |
| 1356 | StorageLayout layout(stt.getEncoding()); |
| 1357 | if (layout.getNumDataFields() != lvlTps.size() + 1) // plus one value memref |
| 1358 | return op->emitError(message: "inconsistent number of fields between input/output" ); |
| 1359 | |
| 1360 | unsigned idx = 0; |
| 1361 | bool misMatch = false; |
| 1362 | layout.foreachField(callback: [&idx, &misMatch, stt, valTp, |
| 1363 | lvlTps](FieldIndex fid, SparseTensorFieldKind fKind, |
| 1364 | Level lvl, LevelType lt) -> bool { |
| 1365 | if (fKind == SparseTensorFieldKind::StorageSpec) |
| 1366 | return true; |
| 1367 | |
| 1368 | Type inputTp = nullptr; |
| 1369 | if (fKind == SparseTensorFieldKind::ValMemRef) { |
| 1370 | inputTp = valTp; |
| 1371 | } else { |
| 1372 | assert(fid == idx && stt.getLvlType(lvl) == lt); |
| 1373 | inputTp = lvlTps[idx++]; |
| 1374 | } |
| 1375 | // The input element type and expected element type should match. |
| 1376 | Type inpElemTp = llvm::cast<TensorType>(Val&: inputTp).getElementType(); |
| 1377 | Type expElemTp = getFieldElemType(stt, kind: fKind); |
| 1378 | if (inpElemTp != expElemTp) { |
| 1379 | misMatch = true; |
| 1380 | return false; // to terminate the iteration |
| 1381 | } |
| 1382 | return true; |
| 1383 | }); |
| 1384 | |
| 1385 | if (misMatch) |
| 1386 | return op->emitError(message: "input/output element-types don't match" ); |
| 1387 | return success(); |
| 1388 | } |
| 1389 | |
| 1390 | LogicalResult AssembleOp::verify() { |
| 1391 | RankedTensorType valuesTp = getValues().getType(); |
| 1392 | const auto lvlsTp = getLevels().getTypes(); |
| 1393 | const auto resTp = getSparseTensorType(val: getResult()); |
| 1394 | return verifyPackUnPack(op: *this, requiresStaticShape: true, stt: resTp, valTp: valuesTp, lvlTps: lvlsTp); |
| 1395 | } |
| 1396 | |
| 1397 | LogicalResult DisassembleOp::verify() { |
| 1398 | if (getOutValues().getType() != getRetValues().getType()) |
| 1399 | return emitError(message: "output values and return value type mismatch" ); |
| 1400 | |
| 1401 | for (auto [ot, rt] : llvm::zip_equal(t: getOutLevels(), u: getRetLevels())) |
| 1402 | if (ot.getType() != rt.getType()) |
| 1403 | return emitError(message: "output levels and return levels type mismatch" ); |
| 1404 | |
| 1405 | RankedTensorType valuesTp = getRetValues().getType(); |
| 1406 | const auto lvlsTp = getRetLevels().getTypes(); |
| 1407 | const auto srcTp = getSparseTensorType(val: getTensor()); |
| 1408 | return verifyPackUnPack(op: *this, requiresStaticShape: false, stt: srcTp, valTp: valuesTp, lvlTps: lvlsTp); |
| 1409 | } |
| 1410 | |
| 1411 | LogicalResult ConvertOp::verify() { |
| 1412 | RankedTensorType tp1 = getSource().getType(); |
| 1413 | RankedTensorType tp2 = getDest().getType(); |
| 1414 | if (tp1.getRank() != tp2.getRank()) |
| 1415 | return emitError(message: "unexpected conversion mismatch in rank" ); |
| 1416 | auto dstEnc = |
| 1417 | llvm::dyn_cast_or_null<SparseTensorEncodingAttr>(Val: tp2.getEncoding()); |
| 1418 | if (dstEnc && dstEnc.isSlice()) |
| 1419 | return emitError(message: "cannot convert to a sparse tensor slice" ); |
| 1420 | |
| 1421 | auto shape1 = tp1.getShape(); |
| 1422 | auto shape2 = tp2.getShape(); |
| 1423 | // Accept size matches between the source and the destination type |
| 1424 | // (e.g. 10 vs. 10, 10 vs. ?, or ? vs. ?), but reject direct mismatches or |
| 1425 | // matches that would need a runtime assert (e.g. 10 vs. 20 or ? vs. 10). |
| 1426 | for (Dimension d = 0, dimRank = tp1.getRank(); d < dimRank; d++) |
| 1427 | if (shape1[d] != shape2[d] && shape2[d] != ShapedType::kDynamic) |
| 1428 | return emitError(message: "unexpected conversion mismatch in dimension " ) << d; |
| 1429 | return success(); |
| 1430 | } |
| 1431 | |
| 1432 | OpFoldResult ConvertOp::fold(FoldAdaptor adaptor) { |
| 1433 | if (getType() == getSource().getType()) |
| 1434 | return getSource(); |
| 1435 | return {}; |
| 1436 | } |
| 1437 | |
| 1438 | bool ConvertOp::() { |
| 1439 | SparseTensorType srcStt = getSparseTensorType(val: getSource()); |
| 1440 | SparseTensorType dstStt = getSparseTensorType(val: getDest()); |
| 1441 | |
| 1442 | // We do not need an extra sort when returning unordered sparse tensors or |
| 1443 | // dense tensor since dense tensor support random access. |
| 1444 | if (dstStt.isAllDense() || !dstStt.isAllOrdered()) |
| 1445 | return false; |
| 1446 | |
| 1447 | if (srcStt.isAllOrdered() && dstStt.isAllOrdered() && |
| 1448 | srcStt.hasSameDimToLvl(other: dstStt)) { |
| 1449 | return false; |
| 1450 | } |
| 1451 | |
| 1452 | // Source and dest tensors are ordered in different ways. We only do direct |
| 1453 | // dense to sparse conversion when the dense input is defined by a sparse |
| 1454 | // constant. Note that we can theoretically always directly convert from dense |
| 1455 | // inputs by rotating dense loops but it leads to bad cache locality and hurt |
| 1456 | // performance. |
| 1457 | if (auto constOp = getSource().getDefiningOp<arith::ConstantOp>()) |
| 1458 | if (isa<SparseElementsAttr>(Val: constOp.getValue())) |
| 1459 | return false; |
| 1460 | |
| 1461 | return true; |
| 1462 | } |
| 1463 | |
| 1464 | LogicalResult CrdTranslateOp::verify() { |
| 1465 | uint64_t inRank = getEncoder().getLvlRank(); |
| 1466 | uint64_t outRank = getEncoder().getDimRank(); |
| 1467 | |
| 1468 | if (getDirection() == CrdTransDirectionKind::dim2lvl) |
| 1469 | std::swap(a&: inRank, b&: outRank); |
| 1470 | |
| 1471 | if (inRank != getInCrds().size() || outRank != getOutCrds().size()) |
| 1472 | return emitError(message: "Coordinate rank mismatch with encoding" ); |
| 1473 | |
| 1474 | return success(); |
| 1475 | } |
| 1476 | |
| 1477 | LogicalResult CrdTranslateOp::fold(FoldAdaptor adaptor, |
| 1478 | SmallVectorImpl<OpFoldResult> &results) { |
| 1479 | if (getEncoder().isIdentity()) { |
| 1480 | results.assign(in_start: getInCrds().begin(), in_end: getInCrds().end()); |
| 1481 | return success(); |
| 1482 | } |
| 1483 | if (getEncoder().isPermutation()) { |
| 1484 | AffineMap perm = getDirection() == CrdTransDirectionKind::dim2lvl |
| 1485 | ? getEncoder().getDimToLvl() |
| 1486 | : getEncoder().getLvlToDim(); |
| 1487 | for (AffineExpr exp : perm.getResults()) |
| 1488 | results.push_back(Elt: getInCrds()[cast<AffineDimExpr>(Val&: exp).getPosition()]); |
| 1489 | return success(); |
| 1490 | } |
| 1491 | |
| 1492 | // Fuse dim2lvl/lvl2dim pairs. |
| 1493 | auto def = getInCrds()[0].getDefiningOp<CrdTranslateOp>(); |
| 1494 | bool sameDef = def && llvm::all_of(Range: getInCrds(), P: [def](Value v) { |
| 1495 | return v.getDefiningOp() == def; |
| 1496 | }); |
| 1497 | if (!sameDef) |
| 1498 | return failure(); |
| 1499 | |
| 1500 | bool oppositeDir = def.getDirection() != getDirection(); |
| 1501 | bool sameOracle = |
| 1502 | def.getEncoder().getDimToLvl() == getEncoder().getDimToLvl(); |
| 1503 | bool sameCount = def.getNumResults() == getInCrds().size(); |
| 1504 | if (!oppositeDir || !sameOracle || !sameCount) |
| 1505 | return failure(); |
| 1506 | |
| 1507 | // The definition produces the coordinates in the same order as the input |
| 1508 | // coordinates. |
| 1509 | bool sameOrder = llvm::all_of(Range: llvm::zip_equal(t: def.getOutCrds(), u: getInCrds()), |
| 1510 | P: [](auto valuePair) { |
| 1511 | auto [lhs, rhs] = valuePair; |
| 1512 | return lhs == rhs; |
| 1513 | }); |
| 1514 | |
| 1515 | if (!sameOrder) |
| 1516 | return failure(); |
| 1517 | // l1 = dim2lvl (lvl2dim l0) |
| 1518 | // ==> l0 |
| 1519 | results.append(in_start: def.getInCrds().begin(), in_end: def.getInCrds().end()); |
| 1520 | return success(); |
| 1521 | } |
| 1522 | |
| 1523 | void LvlOp::build(OpBuilder &builder, OperationState &state, Value source, |
| 1524 | int64_t index) { |
| 1525 | Value val = arith::ConstantIndexOp::create(builder, location: state.location, value: index); |
| 1526 | return build(odsBuilder&: builder, odsState&: state, source, index: val); |
| 1527 | } |
| 1528 | |
| 1529 | LogicalResult LvlOp::verify() { |
| 1530 | if (std::optional<uint64_t> lvl = getConstantLvlIndex()) { |
| 1531 | auto stt = getSparseTensorType(val: getSource()); |
| 1532 | if (static_cast<uint64_t>(lvl.value()) >= stt.getLvlRank()) |
| 1533 | return emitError( |
| 1534 | message: "Level index exceeds the rank of the input sparse tensor" ); |
| 1535 | } |
| 1536 | return success(); |
| 1537 | } |
| 1538 | |
| 1539 | std::optional<uint64_t> LvlOp::getConstantLvlIndex() { |
| 1540 | return getConstantIntValue(ofr: getIndex()); |
| 1541 | } |
| 1542 | |
| 1543 | Speculation::Speculatability LvlOp::getSpeculatability() { |
| 1544 | auto constantIndex = getConstantLvlIndex(); |
| 1545 | if (!constantIndex) |
| 1546 | return Speculation::NotSpeculatable; |
| 1547 | |
| 1548 | assert(constantIndex < |
| 1549 | cast<RankedTensorType>(getSource().getType()).getRank()); |
| 1550 | return Speculation::Speculatable; |
| 1551 | } |
| 1552 | |
| 1553 | OpFoldResult LvlOp::fold(FoldAdaptor adaptor) { |
| 1554 | auto lvlIndex = llvm::dyn_cast_if_present<IntegerAttr>(Val: adaptor.getIndex()); |
| 1555 | if (!lvlIndex) |
| 1556 | return {}; |
| 1557 | |
| 1558 | Level lvl = lvlIndex.getAPSInt().getZExtValue(); |
| 1559 | auto stt = getSparseTensorType(val: getSource()); |
| 1560 | if (lvl >= stt.getLvlRank()) { |
| 1561 | // Follows the same convention used by tensor.dim operation. Out of bound |
| 1562 | // indices produce undefined behavior but are still valid IR. Don't choke on |
| 1563 | // them. |
| 1564 | return {}; |
| 1565 | } |
| 1566 | |
| 1567 | // Helper lambda to build an IndexAttr. |
| 1568 | auto getIndexAttr = [this](int64_t lvlSz) { |
| 1569 | return IntegerAttr::get(type: IndexType::get(context: getContext()), value: APInt(64, lvlSz)); |
| 1570 | }; |
| 1571 | |
| 1572 | SmallVector<Size> lvlShape = stt.getLvlShape(); |
| 1573 | if (ShapedType::isStatic(dValue: lvlShape[lvl])) |
| 1574 | return getIndexAttr(lvlShape[lvl]); |
| 1575 | |
| 1576 | return {}; |
| 1577 | } |
| 1578 | |
| 1579 | void ReinterpretMapOp::build(OpBuilder &odsBuilder, OperationState &odsState, |
| 1580 | SparseTensorEncodingAttr dstEnc, Value source) { |
| 1581 | auto srcStt = getSparseTensorType(val: source); |
| 1582 | SmallVector<int64_t> srcLvlShape = srcStt.getLvlShape(); |
| 1583 | SmallVector<int64_t> dstDimShape = |
| 1584 | dstEnc.translateShape(srcShape: srcLvlShape, dir: CrdTransDirectionKind::lvl2dim); |
| 1585 | auto dstTp = |
| 1586 | RankedTensorType::get(shape: dstDimShape, elementType: srcStt.getElementType(), encoding: dstEnc); |
| 1587 | return build(odsBuilder, odsState, dest: dstTp, source); |
| 1588 | } |
| 1589 | |
| 1590 | LogicalResult ReinterpretMapOp::verify() { |
| 1591 | auto srcStt = getSparseTensorType(val: getSource()); |
| 1592 | auto dstStt = getSparseTensorType(val: getDest()); |
| 1593 | ArrayRef<LevelType> srcLvlTps = srcStt.getLvlTypes(); |
| 1594 | ArrayRef<LevelType> dstLvlTps = dstStt.getLvlTypes(); |
| 1595 | |
| 1596 | if (srcLvlTps.size() != dstLvlTps.size()) |
| 1597 | return emitError(message: "Level rank mismatch between source/dest tensors" ); |
| 1598 | |
| 1599 | for (auto [srcLvlTp, dstLvlTp] : llvm::zip(t&: srcLvlTps, u&: dstLvlTps)) |
| 1600 | if (srcLvlTp != dstLvlTp) |
| 1601 | return emitError(message: "Level type mismatch between source/dest tensors" ); |
| 1602 | |
| 1603 | if (srcStt.getPosWidth() != dstStt.getPosWidth() || |
| 1604 | srcStt.getCrdWidth() != dstStt.getCrdWidth()) { |
| 1605 | return emitError(message: "Crd/Pos width mismatch between source/dest tensors" ); |
| 1606 | } |
| 1607 | |
| 1608 | if (srcStt.getElementType() != dstStt.getElementType()) |
| 1609 | return emitError(message: "Element type mismatch between source/dest tensors" ); |
| 1610 | |
| 1611 | SmallVector<Size> srcLvlShape = srcStt.getLvlShape(); |
| 1612 | SmallVector<Size> dstLvlShape = dstStt.getLvlShape(); |
| 1613 | for (auto [srcLvlSz, dstLvlSz] : llvm::zip(t&: srcLvlShape, u&: dstLvlShape)) { |
| 1614 | if (srcLvlSz != dstLvlSz) { |
| 1615 | // Should we allow one side to be dynamic size, e.g., <?x?> should be |
| 1616 | // compatible to <3x4>? For now, we require all the level sizes to be |
| 1617 | // *exactly* matched for simplicity. |
| 1618 | return emitError(message: "Level size mismatch between source/dest tensors" ); |
| 1619 | } |
| 1620 | } |
| 1621 | |
| 1622 | return success(); |
| 1623 | } |
| 1624 | |
| 1625 | OpFoldResult ReinterpretMapOp::fold(FoldAdaptor adaptor) { |
| 1626 | if (getSource().getType() == getDest().getType()) |
| 1627 | return getSource(); |
| 1628 | |
| 1629 | if (auto def = getSource().getDefiningOp<ReinterpretMapOp>()) { |
| 1630 | // A -> B, B -> A ==> A |
| 1631 | if (def.getSource().getType() == getDest().getType()) |
| 1632 | return def.getSource(); |
| 1633 | } |
| 1634 | return {}; |
| 1635 | } |
| 1636 | |
| 1637 | template <typename ToBufferOp> |
| 1638 | static LogicalResult inferSparseBufferType(ValueRange ops, DictionaryAttr attr, |
| 1639 | PropertyRef prop, RegionRange region, |
| 1640 | SmallVectorImpl<mlir::Type> &ret) { |
| 1641 | typename ToBufferOp::Adaptor adaptor(ops, attr, prop, region); |
| 1642 | SparseTensorType stt = getSparseTensorType(adaptor.getTensor()); |
| 1643 | Type elemTp = nullptr; |
| 1644 | bool withStride = false; |
| 1645 | if constexpr (std::is_same_v<ToBufferOp, ToPositionsOp>) { |
| 1646 | elemTp = stt.getPosType(); |
| 1647 | } else if constexpr (std::is_same_v<ToBufferOp, ToCoordinatesOp> || |
| 1648 | std::is_same_v<ToBufferOp, ToCoordinatesBufferOp>) { |
| 1649 | elemTp = stt.getCrdType(); |
| 1650 | if constexpr (std::is_same_v<ToBufferOp, ToCoordinatesOp>) |
| 1651 | withStride = stt.getAoSCOOStart() <= adaptor.getLevel(); |
| 1652 | } else if constexpr (std::is_same_v<ToBufferOp, ToValuesOp>) { |
| 1653 | elemTp = stt.getElementType(); |
| 1654 | } |
| 1655 | |
| 1656 | assert(elemTp && "unhandled operation." ); |
| 1657 | SmallVector<int64_t> bufShape = stt.getBatchLvlShape(); |
| 1658 | bufShape.push_back(Elt: ShapedType::kDynamic); |
| 1659 | |
| 1660 | auto layout = withStride ? StridedLayoutAttr::StridedLayoutAttr::get( |
| 1661 | context: stt.getContext(), offset: ShapedType::kDynamic, |
| 1662 | strides: {ShapedType::kDynamic}) |
| 1663 | : StridedLayoutAttr(); |
| 1664 | ret.emplace_back(Args: MemRefType::get(shape: bufShape, elementType: elemTp, layout)); |
| 1665 | return success(); |
| 1666 | } |
| 1667 | |
| 1668 | LogicalResult ToPositionsOp::verify() { |
| 1669 | auto stt = getSparseTensorType(val: getTensor()); |
| 1670 | if (failed(Result: lvlIsInBounds(lvl: getLevel(), tensor: getTensor()))) |
| 1671 | return emitError(message: "requested level is out of bounds" ); |
| 1672 | if (failed(Result: isMatchingWidth(mem: getResult(), width: stt.getPosWidth()))) |
| 1673 | return emitError(message: "unexpected type for positions" ); |
| 1674 | return success(); |
| 1675 | } |
| 1676 | |
| 1677 | LogicalResult |
| 1678 | ToPositionsOp::inferReturnTypes(MLIRContext *ctx, std::optional<Location> loc, |
| 1679 | ValueRange ops, DictionaryAttr attr, |
| 1680 | PropertyRef prop, RegionRange region, |
| 1681 | SmallVectorImpl<mlir::Type> &ret) { |
| 1682 | return inferSparseBufferType<ToPositionsOp>(ops, attr, prop, region, ret); |
| 1683 | } |
| 1684 | |
| 1685 | LogicalResult ToCoordinatesOp::verify() { |
| 1686 | auto stt = getSparseTensorType(val: getTensor()); |
| 1687 | if (failed(Result: lvlIsInBounds(lvl: getLevel(), tensor: getTensor()))) |
| 1688 | return emitError(message: "requested level is out of bounds" ); |
| 1689 | if (failed(Result: isMatchingWidth(mem: getResult(), width: stt.getCrdWidth()))) |
| 1690 | return emitError(message: "unexpected type for coordinates" ); |
| 1691 | return success(); |
| 1692 | } |
| 1693 | |
| 1694 | LogicalResult |
| 1695 | ToCoordinatesOp::inferReturnTypes(MLIRContext *ctx, std::optional<Location> loc, |
| 1696 | ValueRange ops, DictionaryAttr attr, |
| 1697 | PropertyRef prop, RegionRange region, |
| 1698 | SmallVectorImpl<mlir::Type> &ret) { |
| 1699 | return inferSparseBufferType<ToCoordinatesOp>(ops, attr, prop, region, ret); |
| 1700 | } |
| 1701 | |
| 1702 | LogicalResult ToCoordinatesBufferOp::verify() { |
| 1703 | auto stt = getSparseTensorType(val: getTensor()); |
| 1704 | if (stt.getAoSCOOStart() >= stt.getLvlRank()) |
| 1705 | return emitError(message: "expected sparse tensor with a COO region" ); |
| 1706 | return success(); |
| 1707 | } |
| 1708 | |
| 1709 | LogicalResult ToCoordinatesBufferOp::inferReturnTypes( |
| 1710 | MLIRContext *ctx, std::optional<Location> loc, ValueRange ops, |
| 1711 | DictionaryAttr attr, PropertyRef prop, RegionRange region, |
| 1712 | SmallVectorImpl<mlir::Type> &ret) { |
| 1713 | return inferSparseBufferType<ToCoordinatesBufferOp>(ops, attr, prop, region, |
| 1714 | ret); |
| 1715 | } |
| 1716 | |
| 1717 | LogicalResult ToValuesOp::verify() { |
| 1718 | auto stt = getSparseTensorType(val: getTensor()); |
| 1719 | auto mtp = getMemRefType(t: getResult()); |
| 1720 | if (stt.getElementType() != mtp.getElementType()) |
| 1721 | return emitError(message: "unexpected mismatch in element types" ); |
| 1722 | return success(); |
| 1723 | } |
| 1724 | |
| 1725 | LogicalResult ToValuesOp::inferReturnTypes(MLIRContext *ctx, |
| 1726 | std::optional<Location> loc, |
| 1727 | ValueRange ops, DictionaryAttr attr, |
| 1728 | PropertyRef prop, RegionRange region, |
| 1729 | SmallVectorImpl<mlir::Type> &ret) { |
| 1730 | return inferSparseBufferType<ToValuesOp>(ops, attr, prop, region, ret); |
| 1731 | } |
| 1732 | |
| 1733 | LogicalResult ToSliceOffsetOp::verify() { |
| 1734 | auto rank = getSlice().getType().getRank(); |
| 1735 | if (rank <= getDim().getSExtValue() || getDim().getSExtValue() < 0) |
| 1736 | return emitError(message: "requested dimension out of bound" ); |
| 1737 | return success(); |
| 1738 | } |
| 1739 | |
| 1740 | LogicalResult ToSliceStrideOp::verify() { |
| 1741 | auto rank = getSlice().getType().getRank(); |
| 1742 | if (rank <= getDim().getSExtValue() || getDim().getSExtValue() < 0) |
| 1743 | return emitError(message: "requested dimension out of bound" ); |
| 1744 | return success(); |
| 1745 | } |
| 1746 | |
| 1747 | LogicalResult GetStorageSpecifierOp::verify() { |
| 1748 | return verifySparsifierGetterSetter(mdKind: getSpecifierKind(), lvl: getLevel(), |
| 1749 | md: getSpecifier(), op: getOperation()); |
| 1750 | } |
| 1751 | |
| 1752 | template <typename SpecifierOp> |
| 1753 | static SetStorageSpecifierOp getSpecifierSetDef(SpecifierOp op) { |
| 1754 | return op.getSpecifier().template getDefiningOp<SetStorageSpecifierOp>(); |
| 1755 | } |
| 1756 | |
| 1757 | OpFoldResult GetStorageSpecifierOp::fold(FoldAdaptor adaptor) { |
| 1758 | const StorageSpecifierKind kind = getSpecifierKind(); |
| 1759 | const auto lvl = getLevel(); |
| 1760 | for (auto op = getSpecifierSetDef(op: *this); op; op = getSpecifierSetDef(op)) |
| 1761 | if (kind == op.getSpecifierKind() && lvl == op.getLevel()) |
| 1762 | return op.getValue(); |
| 1763 | return {}; |
| 1764 | } |
| 1765 | |
| 1766 | LogicalResult SetStorageSpecifierOp::verify() { |
| 1767 | return verifySparsifierGetterSetter(mdKind: getSpecifierKind(), lvl: getLevel(), |
| 1768 | md: getSpecifier(), op: getOperation()); |
| 1769 | } |
| 1770 | |
| 1771 | template <class T> |
| 1772 | static LogicalResult verifyNumBlockArgs(T *op, Region ®ion, |
| 1773 | const char *regionName, |
| 1774 | TypeRange inputTypes, Type outputType) { |
| 1775 | unsigned numArgs = region.getNumArguments(); |
| 1776 | unsigned expectedNum = inputTypes.size(); |
| 1777 | if (numArgs != expectedNum) |
| 1778 | return op->emitError() << regionName << " region must have exactly " |
| 1779 | << expectedNum << " arguments" ; |
| 1780 | |
| 1781 | for (unsigned i = 0; i < numArgs; i++) { |
| 1782 | Type typ = region.getArgument(i).getType(); |
| 1783 | if (typ != inputTypes[i]) |
| 1784 | return op->emitError() << regionName << " region argument " << (i + 1) |
| 1785 | << " type mismatch" ; |
| 1786 | } |
| 1787 | Block &block = region.front(); |
| 1788 | if (!block.mightHaveTerminator()) |
| 1789 | return op->emitError() << regionName |
| 1790 | << " region must end with a terminator" ; |
| 1791 | |
| 1792 | Operation *term = block.getTerminator(); |
| 1793 | YieldOp yield = dyn_cast<YieldOp>(Val: term); |
| 1794 | if (!yield) |
| 1795 | return op->emitError() << regionName |
| 1796 | << " region must end with sparse_tensor.yield" ; |
| 1797 | if (!yield.hasSingleResult() || |
| 1798 | yield.getSingleResult().getType() != outputType) |
| 1799 | return op->emitError() << regionName << " region yield type mismatch" ; |
| 1800 | |
| 1801 | return success(); |
| 1802 | } |
| 1803 | |
| 1804 | LogicalResult BinaryOp::verify() { |
| 1805 | NamedAttrList attrs = (*this)->getDiscardableAttrDictionary().getValue(); |
| 1806 | Type leftType = getX().getType(); |
| 1807 | Type rightType = getY().getType(); |
| 1808 | Type outputType = getOutput().getType(); |
| 1809 | Region &overlap = getOverlapRegion(); |
| 1810 | Region &left = getLeftRegion(); |
| 1811 | Region &right = getRightRegion(); |
| 1812 | |
| 1813 | // Check correct number of block arguments and return type for each |
| 1814 | // non-empty region. |
| 1815 | if (!overlap.empty()) { |
| 1816 | if (failed(Result: verifyNumBlockArgs(op: this, region&: overlap, regionName: "overlap" , |
| 1817 | inputTypes: TypeRange{leftType, rightType}, outputType))) |
| 1818 | return failure(); |
| 1819 | } |
| 1820 | if (!left.empty()) { |
| 1821 | if (failed(Result: verifyNumBlockArgs(op: this, region&: left, regionName: "left" , inputTypes: TypeRange{leftType}, |
| 1822 | outputType))) |
| 1823 | return failure(); |
| 1824 | } else if (getLeftIdentity()) { |
| 1825 | if (leftType != outputType) |
| 1826 | return emitError(message: "left=identity requires first argument to have the same " |
| 1827 | "type as the output" ); |
| 1828 | } |
| 1829 | if (!right.empty()) { |
| 1830 | if (failed(Result: verifyNumBlockArgs(op: this, region&: right, regionName: "right" , inputTypes: TypeRange{rightType}, |
| 1831 | outputType))) |
| 1832 | return failure(); |
| 1833 | } else if (getRightIdentity()) { |
| 1834 | if (rightType != outputType) |
| 1835 | return emitError(message: "right=identity requires second argument to have the " |
| 1836 | "same type as the output" ); |
| 1837 | } |
| 1838 | return success(); |
| 1839 | } |
| 1840 | |
| 1841 | LogicalResult UnaryOp::verify() { |
| 1842 | Type inputType = getX().getType(); |
| 1843 | Type outputType = getOutput().getType(); |
| 1844 | |
| 1845 | // Check correct number of block arguments and return type for each |
| 1846 | // non-empty region. |
| 1847 | Region &present = getPresentRegion(); |
| 1848 | if (!present.empty()) { |
| 1849 | if (failed(Result: verifyNumBlockArgs(op: this, region&: present, regionName: "present" , |
| 1850 | inputTypes: TypeRange{inputType}, outputType))) |
| 1851 | return failure(); |
| 1852 | } |
| 1853 | Region &absent = getAbsentRegion(); |
| 1854 | if (!absent.empty()) { |
| 1855 | if (failed(Result: verifyNumBlockArgs(op: this, region&: absent, regionName: "absent" , inputTypes: TypeRange{}, |
| 1856 | outputType))) |
| 1857 | return failure(); |
| 1858 | // Absent branch can only yield invariant values. |
| 1859 | Block *absentBlock = &absent.front(); |
| 1860 | Block *parent = getOperation()->getBlock(); |
| 1861 | Value absentVal = |
| 1862 | cast<YieldOp>(Val: absentBlock->getTerminator()).getSingleResult(); |
| 1863 | if (auto arg = dyn_cast<BlockArgument>(Val&: absentVal)) { |
| 1864 | if (arg.getOwner() == parent) |
| 1865 | return emitError(message: "absent region cannot yield linalg argument" ); |
| 1866 | } else if (Operation *def = absentVal.getDefiningOp()) { |
| 1867 | if (!isa<arith::ConstantOp>(Val: def) && |
| 1868 | (def->getBlock() == absentBlock || def->getBlock() == parent)) |
| 1869 | return emitError(message: "absent region cannot yield locally computed value" ); |
| 1870 | } |
| 1871 | } |
| 1872 | return success(); |
| 1873 | } |
| 1874 | |
| 1875 | bool ConcatenateOp::() { |
| 1876 | SparseTensorType dstStt = getSparseTensorType(val: *this); |
| 1877 | if (dstStt.isAllDense() || !dstStt.isAllOrdered()) |
| 1878 | return false; |
| 1879 | |
| 1880 | bool allSameOrdered = llvm::all_of(Range: getInputs(), P: [dstStt](Value op) { |
| 1881 | return getSparseTensorType(val: op).hasSameDimToLvl(other: dstStt); |
| 1882 | }); |
| 1883 | // TODO: When conDim != 0, as long as conDim corresponding to the first level |
| 1884 | // in all input/output buffers, and all input/output buffers have the same |
| 1885 | // dimToLvl, the tmp COO buffer is still unnecessary (e.g, concatenate |
| 1886 | // CSC matrices along column). |
| 1887 | bool directLowerable = |
| 1888 | allSameOrdered && getDimension() == 0 && dstStt.isIdentity(); |
| 1889 | return !directLowerable; |
| 1890 | } |
| 1891 | |
| 1892 | LogicalResult ConcatenateOp::verify() { |
| 1893 | const auto dstTp = getSparseTensorType(val: *this); |
| 1894 | const Dimension concatDim = getDimension(); |
| 1895 | const Dimension dimRank = dstTp.getDimRank(); |
| 1896 | |
| 1897 | if (getInputs().size() <= 1) |
| 1898 | return emitError(message: "Need at least two tensors to concatenate." ); |
| 1899 | |
| 1900 | if (concatDim >= dimRank) |
| 1901 | return emitError(message: llvm::formatv( |
| 1902 | Fmt: "Concat-dimension is out of bounds for dimension-rank ({0} >= {1})" , |
| 1903 | Vals: concatDim, Vals: dimRank)); |
| 1904 | |
| 1905 | for (const auto &it : llvm::enumerate(First: getInputs())) { |
| 1906 | const auto i = it.index(); |
| 1907 | const auto srcTp = getSparseTensorType(val: it.value()); |
| 1908 | if (srcTp.hasDynamicDimShape()) |
| 1909 | return emitError(message: llvm::formatv(Fmt: "Input tensor ${0} has dynamic shape" , Vals: i)); |
| 1910 | const Dimension srcDimRank = srcTp.getDimRank(); |
| 1911 | if (srcDimRank != dimRank) |
| 1912 | return emitError( |
| 1913 | message: llvm::formatv(Fmt: "Input tensor ${0} has a different rank (rank={1}) " |
| 1914 | "from the output tensor (rank={2})." , |
| 1915 | Vals: i, Vals: srcDimRank, Vals: dimRank)); |
| 1916 | } |
| 1917 | |
| 1918 | for (Dimension d = 0; d < dimRank; d++) { |
| 1919 | const Size dstSh = dstTp.getDimShape()[d]; |
| 1920 | if (d == concatDim) { |
| 1921 | if (ShapedType::isStatic(dValue: dstSh)) { |
| 1922 | // If we reach here, then all inputs have static shapes. So we |
| 1923 | // can use `getDimShape()[d]` instead of `*getDynamicDimSize(d)` |
| 1924 | // to avoid redundant assertions in the loop. |
| 1925 | Size sumSz = 0; |
| 1926 | for (const auto src : getInputs()) |
| 1927 | sumSz += getSparseTensorType(val: src).getDimShape()[d]; |
| 1928 | // If all dimension are statically known, the sum of all the input |
| 1929 | // dimensions should be equal to the output dimension. |
| 1930 | if (sumSz != dstSh) |
| 1931 | return emitError( |
| 1932 | message: "The concatenation dimension of the output tensor should be the " |
| 1933 | "sum of all the concatenation dimensions of the input tensors." ); |
| 1934 | } |
| 1935 | } else { |
| 1936 | Size prev = dstSh; |
| 1937 | for (const auto src : getInputs()) { |
| 1938 | const auto sh = getSparseTensorType(val: src).getDimShape()[d]; |
| 1939 | if (ShapedType::isStatic(dValue: prev) && sh != prev) |
| 1940 | return emitError(message: "All dimensions (expect for the concatenating one) " |
| 1941 | "should be equal." ); |
| 1942 | prev = sh; |
| 1943 | } |
| 1944 | } |
| 1945 | } |
| 1946 | |
| 1947 | return success(); |
| 1948 | } |
| 1949 | |
| 1950 | void PushBackOp::build(OpBuilder &builder, OperationState &result, |
| 1951 | Value curSize, Value inBuffer, Value value) { |
| 1952 | build(odsBuilder&: builder, odsState&: result, curSize, inBuffer, value, n: Value()); |
| 1953 | } |
| 1954 | |
| 1955 | LogicalResult PushBackOp::verify() { |
| 1956 | if (Value n = getN()) { |
| 1957 | std::optional<int64_t> nValue = getConstantIntValue(ofr: n); |
| 1958 | if (nValue && nValue.value() < 1) |
| 1959 | return emitOpError(message: "n must be not less than 1" ); |
| 1960 | } |
| 1961 | return success(); |
| 1962 | } |
| 1963 | |
| 1964 | LogicalResult CompressOp::verify() { |
| 1965 | const auto stt = getSparseTensorType(val: getTensor()); |
| 1966 | if (stt.getLvlRank() != 1 + static_cast<Level>(getLvlCoords().size())) |
| 1967 | return emitOpError(message: "incorrect number of coordinates" ); |
| 1968 | return success(); |
| 1969 | } |
| 1970 | |
| 1971 | void ForeachOp::build( |
| 1972 | OpBuilder &builder, OperationState &result, Value tensor, |
| 1973 | ValueRange initArgs, AffineMapAttr order, |
| 1974 | function_ref<void(OpBuilder &, Location, ValueRange, Value, ValueRange)> |
| 1975 | bodyBuilder) { |
| 1976 | build(odsBuilder&: builder, odsState&: result, results: initArgs.getTypes(), tensor, initArgs, order); |
| 1977 | // Builds foreach body. |
| 1978 | if (!bodyBuilder) |
| 1979 | return; |
| 1980 | const auto stt = getSparseTensorType(val: tensor); |
| 1981 | const Dimension dimRank = stt.getDimRank(); |
| 1982 | |
| 1983 | // Starts with `dimRank`-many coordinates. |
| 1984 | SmallVector<Type> blockArgTypes(dimRank, builder.getIndexType()); |
| 1985 | // Followed by one value. |
| 1986 | blockArgTypes.push_back(Elt: stt.getElementType()); |
| 1987 | // Followed by the reduction variables. |
| 1988 | blockArgTypes.append(in_start: initArgs.getTypes().begin(), in_end: initArgs.getTypes().end()); |
| 1989 | |
| 1990 | SmallVector<Location> blockArgLocs(blockArgTypes.size(), tensor.getLoc()); |
| 1991 | |
| 1992 | OpBuilder::InsertionGuard guard(builder); |
| 1993 | auto ®ion = *result.regions.front(); |
| 1994 | Block *bodyBlock = |
| 1995 | builder.createBlock(parent: ®ion, insertPt: region.end(), argTypes: blockArgTypes, locs: blockArgLocs); |
| 1996 | bodyBuilder(builder, result.location, |
| 1997 | bodyBlock->getArguments().slice(N: 0, M: dimRank), |
| 1998 | bodyBlock->getArguments()[dimRank], |
| 1999 | bodyBlock->getArguments().drop_front(N: dimRank + 1)); |
| 2000 | } |
| 2001 | |
| 2002 | LogicalResult ForeachOp::verify() { |
| 2003 | const auto t = getSparseTensorType(val: getTensor()); |
| 2004 | const Dimension dimRank = t.getDimRank(); |
| 2005 | const auto args = getBody()->getArguments(); |
| 2006 | |
| 2007 | if (getOrder().has_value() && getOrder()->getNumDims() != t.getLvlRank()) |
| 2008 | return emitError(message: "Level traverse order does not match tensor's level rank" ); |
| 2009 | |
| 2010 | if (dimRank + 1 + getInitArgs().size() != args.size()) |
| 2011 | return emitError(message: "Unmatched number of arguments in the block" ); |
| 2012 | |
| 2013 | if (getNumResults() != getInitArgs().size()) |
| 2014 | return emitError(message: "Mismatch in number of init arguments and results" ); |
| 2015 | |
| 2016 | if (getResultTypes() != getInitArgs().getTypes()) |
| 2017 | return emitError(message: "Mismatch in types of init arguments and results" ); |
| 2018 | |
| 2019 | // Cannot mark this const, because the getters aren't. |
| 2020 | auto yield = cast<YieldOp>(Val: getBody()->getTerminator()); |
| 2021 | if (yield.getNumOperands() != getNumResults() || |
| 2022 | yield.getOperands().getTypes() != getResultTypes()) |
| 2023 | return emitError(message: "Mismatch in types of yield values and results" ); |
| 2024 | |
| 2025 | const auto iTp = IndexType::get(context: getContext()); |
| 2026 | for (Dimension d = 0; d < dimRank; d++) |
| 2027 | if (args[d].getType() != iTp) |
| 2028 | return emitError( |
| 2029 | message: llvm::formatv(Fmt: "Expecting Index type for argument at index {0}" , Vals&: d)); |
| 2030 | |
| 2031 | const auto elemTp = t.getElementType(); |
| 2032 | const auto valueTp = args[dimRank].getType(); |
| 2033 | if (elemTp != valueTp) |
| 2034 | return emitError( |
| 2035 | message: llvm::formatv(Fmt: "Unmatched element type between input tensor and " |
| 2036 | "block argument, expected:{0}, got: {1}" , |
| 2037 | Vals: elemTp, Vals: valueTp)); |
| 2038 | return success(); |
| 2039 | } |
| 2040 | |
| 2041 | OpFoldResult ReorderCOOOp::fold(FoldAdaptor adaptor) { |
| 2042 | if (getSparseTensorEncoding(type: getInputCoo().getType()) == |
| 2043 | getSparseTensorEncoding(type: getResultCoo().getType())) |
| 2044 | return getInputCoo(); |
| 2045 | |
| 2046 | return {}; |
| 2047 | } |
| 2048 | |
| 2049 | LogicalResult ReorderCOOOp::verify() { |
| 2050 | SparseTensorType srcStt = getSparseTensorType(val: getInputCoo()); |
| 2051 | SparseTensorType dstStt = getSparseTensorType(val: getResultCoo()); |
| 2052 | |
| 2053 | if (!srcStt.isCOOType() || !dstStt.isCOOType()) |
| 2054 | return emitError(message: "Expected COO sparse tensors only" ); |
| 2055 | |
| 2056 | if (!srcStt.hasSameDimToLvl(other: dstStt)) |
| 2057 | return emitError(message: "Unmatched dim2lvl map between input and result COO" ); |
| 2058 | |
| 2059 | if (srcStt.getPosType() != dstStt.getPosType() || |
| 2060 | srcStt.getCrdType() != dstStt.getCrdType() || |
| 2061 | srcStt.getElementType() != dstStt.getElementType()) |
| 2062 | return emitError(message: "Unmatched storage format between input and result COO" ); |
| 2063 | |
| 2064 | return success(); |
| 2065 | } |
| 2066 | |
| 2067 | LogicalResult ReduceOp::verify() { |
| 2068 | Type inputType = getX().getType(); |
| 2069 | Region &formula = getRegion(); |
| 2070 | return verifyNumBlockArgs(op: this, region&: formula, regionName: "reduce" , |
| 2071 | inputTypes: TypeRange{inputType, inputType}, outputType: inputType); |
| 2072 | } |
| 2073 | |
| 2074 | LogicalResult SelectOp::verify() { |
| 2075 | Builder b(getContext()); |
| 2076 | Type inputType = getX().getType(); |
| 2077 | Type boolType = b.getI1Type(); |
| 2078 | Region &formula = getRegion(); |
| 2079 | return verifyNumBlockArgs(op: this, region&: formula, regionName: "select" , inputTypes: TypeRange{inputType}, |
| 2080 | outputType: boolType); |
| 2081 | } |
| 2082 | |
| 2083 | LogicalResult SortOp::verify() { |
| 2084 | AffineMap xPerm = getPermMap(); |
| 2085 | uint64_t nx = xPerm.getNumDims(); |
| 2086 | if (nx < 1) |
| 2087 | return emitError(message: llvm::formatv(Fmt: "Expected rank(perm_map) > 1, got {0}" , Vals&: nx)); |
| 2088 | |
| 2089 | if (!xPerm.isPermutation()) |
| 2090 | return emitError( |
| 2091 | message: llvm::formatv(Fmt: "Expected a permutation map, got {0}" , Vals&: xPerm)); |
| 2092 | |
| 2093 | // We can't check the size of the buffers when n or buffer dimensions aren't |
| 2094 | // compile-time constants. |
| 2095 | std::optional<int64_t> cn = getConstantIntValue(ofr: getN()); |
| 2096 | if (!cn) |
| 2097 | return success(); |
| 2098 | |
| 2099 | // Verify dimensions. |
| 2100 | const auto checkDim = [&](Value v, Size minSize, |
| 2101 | const char *message) -> LogicalResult { |
| 2102 | const Size sh = getMemRefType(t&: v).getShape()[0]; |
| 2103 | if (ShapedType::isStatic(dValue: sh) && sh < minSize) |
| 2104 | return emitError( |
| 2105 | message: llvm::formatv(Fmt: "{0} got {1} < {2}" , Vals&: message, Vals: sh, Vals&: minSize)); |
| 2106 | return success(); |
| 2107 | }; |
| 2108 | uint64_t n = cn.value(); |
| 2109 | uint64_t ny = 0; |
| 2110 | if (auto nyAttr = getNyAttr()) |
| 2111 | ny = nyAttr.getInt(); |
| 2112 | if (failed(Result: checkDim(getXy(), n * (nx + ny), |
| 2113 | "Expected dimension(xy) >= n * (rank(perm_map) + ny)" ))) |
| 2114 | return failure(); |
| 2115 | for (Value opnd : getYs()) |
| 2116 | if (failed(Result: checkDim(opnd, n, "Expected dimension(y) >= n" ))) |
| 2117 | return failure(); |
| 2118 | |
| 2119 | return success(); |
| 2120 | } |
| 2121 | |
| 2122 | //===----------------------------------------------------------------------===// |
| 2123 | // Sparse Tensor Iteration Operations. |
| 2124 | //===----------------------------------------------------------------------===// |
| 2125 | |
| 2126 | IterSpaceType IteratorType::getIterSpaceType() const { |
| 2127 | return IterSpaceType::get(context: getContext(), encoding: getEncoding(), loLvl: getLoLvl(), |
| 2128 | hiLvl: getHiLvl()); |
| 2129 | } |
| 2130 | |
| 2131 | IteratorType IterSpaceType::getIteratorType() const { |
| 2132 | return IteratorType::get(context: getContext(), encoding: getEncoding(), loLvl: getLoLvl(), hiLvl: getHiLvl()); |
| 2133 | } |
| 2134 | |
| 2135 | /// Parses a level range in the form "$lo `to` $hi" |
| 2136 | /// or simply "$lo" if $hi - $lo = 1 |
| 2137 | static ParseResult parseLevelRange(AsmParser &parser, Level &lvlLo, |
| 2138 | Level &lvlHi) { |
| 2139 | if (parser.parseInteger(result&: lvlLo)) |
| 2140 | return failure(); |
| 2141 | |
| 2142 | if (succeeded(Result: parser.parseOptionalKeyword(keyword: "to" ))) { |
| 2143 | if (parser.parseInteger(result&: lvlHi)) |
| 2144 | return failure(); |
| 2145 | } else { |
| 2146 | lvlHi = lvlLo + 1; |
| 2147 | } |
| 2148 | |
| 2149 | if (lvlHi <= lvlLo) |
| 2150 | return parser.emitError(loc: parser.getNameLoc(), |
| 2151 | message: "expect larger level upper bound than lower bound" ); |
| 2152 | |
| 2153 | return success(); |
| 2154 | } |
| 2155 | |
| 2156 | /// Parses a level range in the form "$lo `to` $hi" |
| 2157 | /// or simply "$lo" if $hi - $lo = 1 |
| 2158 | static ParseResult parseLevelRange(OpAsmParser &parser, IntegerAttr &lvlLoAttr, |
| 2159 | IntegerAttr &lvlHiAttr) { |
| 2160 | Level lvlLo, lvlHi; |
| 2161 | if (parseLevelRange(parser, lvlLo, lvlHi)) |
| 2162 | return failure(); |
| 2163 | |
| 2164 | lvlLoAttr = IntegerAttr::get(type: parser.getBuilder().getIndexType(), value: lvlLo); |
| 2165 | lvlHiAttr = IntegerAttr::get(type: parser.getBuilder().getIndexType(), value: lvlHi); |
| 2166 | return success(); |
| 2167 | } |
| 2168 | |
| 2169 | /// Prints a level range in the form "$lo `to` $hi" |
| 2170 | /// or simply "$lo" if $hi - $lo = 1 |
| 2171 | static void printLevelRange(AsmPrinter &p, Level lo, Level hi) { |
| 2172 | |
| 2173 | if (lo + 1 == hi) |
| 2174 | p << lo; |
| 2175 | else |
| 2176 | p << lo << " to " << hi; |
| 2177 | } |
| 2178 | |
| 2179 | /// Prints a level range in the form "$lo `to` $hi" |
| 2180 | /// or simply "$lo" if $hi - $lo = 1 |
| 2181 | static void printLevelRange(OpAsmPrinter &p, Operation *, IntegerAttr lvlLo, |
| 2182 | IntegerAttr lvlHi) { |
| 2183 | unsigned lo = lvlLo.getValue().getZExtValue(); |
| 2184 | unsigned hi = lvlHi.getValue().getZExtValue(); |
| 2185 | printLevelRange(p, lo, hi); |
| 2186 | } |
| 2187 | |
| 2188 | /// Parses a list of `optional` defined list in the form of |
| 2189 | /// "(%val0, _, %val1, ...)", where `_` is used to annotate that the |
| 2190 | /// corresponding value is not defined (e.g., to represent an undefined |
| 2191 | /// coordinate in the sparse iteration space). |
| 2192 | static ParseResult parseOptionalDefinedList( |
| 2193 | OpAsmParser &parser, OperationState &state, I64BitSet &definedSet, |
| 2194 | SmallVectorImpl<OpAsmParser::Argument> &definedArgs, |
| 2195 | unsigned maxCnt = std::numeric_limits<unsigned>::max(), |
| 2196 | OpAsmParser::Delimiter delimiter = OpAsmParser::Delimiter::Paren) { |
| 2197 | unsigned cnt = 0; |
| 2198 | ParseResult crdList = |
| 2199 | parser.parseCommaSeparatedList(delimiter, parseElementFn: [&]() -> ParseResult { |
| 2200 | if (parser.parseOptionalKeyword(keyword: "_" )) { |
| 2201 | if (parser.parseArgument(result&: definedArgs.emplace_back())) |
| 2202 | return failure(); |
| 2203 | definedSet.set(cnt); |
| 2204 | } |
| 2205 | cnt += 1; |
| 2206 | return success(); |
| 2207 | }); |
| 2208 | |
| 2209 | if (cnt > maxCnt) |
| 2210 | return parser.emitError(loc: parser.getNameLoc(), |
| 2211 | message: "parsed more value than expected." ); |
| 2212 | |
| 2213 | if (failed(Result: crdList)) { |
| 2214 | return parser.emitError( |
| 2215 | loc: parser.getNameLoc(), |
| 2216 | message: "expecting SSA value or \"_\" for level coordinates" ); |
| 2217 | } |
| 2218 | assert(definedArgs.size() == definedSet.count()); |
| 2219 | return success(); |
| 2220 | } |
| 2221 | |
| 2222 | static void printOptionalDefinedList(OpAsmPrinter &p, unsigned size, |
| 2223 | Block::BlockArgListType blocksArgs, |
| 2224 | I64BitSet definedSet) { |
| 2225 | if (definedSet.empty()) |
| 2226 | return; |
| 2227 | |
| 2228 | for (unsigned i = 0; i < size; i++) { |
| 2229 | if (definedSet[i]) { |
| 2230 | p << blocksArgs.front(); |
| 2231 | blocksArgs = blocksArgs.drop_front(); |
| 2232 | } else { |
| 2233 | p << "_" ; |
| 2234 | } |
| 2235 | if (i != size - 1) |
| 2236 | p << ", " ; |
| 2237 | } |
| 2238 | assert(blocksArgs.empty()); |
| 2239 | } |
| 2240 | |
| 2241 | static ParseResult |
| 2242 | parseUsedCoordList(OpAsmParser &parser, OperationState &state, |
| 2243 | SmallVectorImpl<OpAsmParser::Argument> &coords) { |
| 2244 | // Parse "at(%crd0, _, ...)" |
| 2245 | I64BitSet crdUsedLvlSet; |
| 2246 | if (succeeded(Result: parser.parseOptionalKeyword(keyword: "at" )) && |
| 2247 | failed(Result: parseOptionalDefinedList(parser, state, definedSet&: crdUsedLvlSet, definedArgs&: coords))) |
| 2248 | return failure(); |
| 2249 | |
| 2250 | // Always use IndexType for the coordinate. |
| 2251 | for (auto &coord : coords) |
| 2252 | coord.type = parser.getBuilder().getIndexType(); |
| 2253 | |
| 2254 | // Set the CrdUsedLvl bitset. |
| 2255 | state.addAttribute(name: "crdUsedLvls" , |
| 2256 | attr: parser.getBuilder().getI64IntegerAttr(value: crdUsedLvlSet)); |
| 2257 | return success(); |
| 2258 | } |
| 2259 | |
| 2260 | static ParseResult |
| 2261 | parseSparseIterateLoop(OpAsmParser &parser, OperationState &state, |
| 2262 | SmallVectorImpl<OpAsmParser::Argument> &iterators, |
| 2263 | SmallVectorImpl<OpAsmParser::Argument> &blockArgs) { |
| 2264 | SmallVector<OpAsmParser::UnresolvedOperand> spaces; |
| 2265 | SmallVector<OpAsmParser::UnresolvedOperand> initArgs; |
| 2266 | |
| 2267 | // Parse "%iters, ... in %spaces, ..." |
| 2268 | if (parser.parseArgumentList(result&: iterators) || parser.parseKeyword(keyword: "in" ) || |
| 2269 | parser.parseOperandList(result&: spaces)) |
| 2270 | return failure(); |
| 2271 | |
| 2272 | if (iterators.size() != spaces.size()) |
| 2273 | return parser.emitError( |
| 2274 | loc: parser.getNameLoc(), |
| 2275 | message: "mismatch in number of sparse iterators and sparse spaces" ); |
| 2276 | |
| 2277 | SmallVector<OpAsmParser::Argument> coords; |
| 2278 | if (failed(Result: parseUsedCoordList(parser, state, coords))) |
| 2279 | return failure(); |
| 2280 | size_t numCrds = coords.size(); |
| 2281 | |
| 2282 | // Parse "iter_args(%arg = %init, ...)" |
| 2283 | bool hasIterArgs = succeeded(Result: parser.parseOptionalKeyword(keyword: "iter_args" )); |
| 2284 | if (hasIterArgs) |
| 2285 | if (parser.parseAssignmentList(lhs&: blockArgs, rhs&: initArgs)) |
| 2286 | return failure(); |
| 2287 | |
| 2288 | blockArgs.append(RHS: coords); |
| 2289 | |
| 2290 | SmallVector<Type> iterSpaceTps; |
| 2291 | // parse ": sparse_tensor.iter_space -> ret" |
| 2292 | if (parser.parseColon() || parser.parseTypeList(result&: iterSpaceTps)) |
| 2293 | return failure(); |
| 2294 | if (iterSpaceTps.size() != spaces.size()) |
| 2295 | return parser.emitError(loc: parser.getNameLoc(), |
| 2296 | message: "mismatch in number of iteration space operands " |
| 2297 | "and iteration space types" ); |
| 2298 | |
| 2299 | for (auto [it, tp] : llvm::zip_equal(t&: iterators, u&: iterSpaceTps)) { |
| 2300 | IterSpaceType spaceTp = llvm::dyn_cast<IterSpaceType>(Val&: tp); |
| 2301 | if (!spaceTp) |
| 2302 | return parser.emitError(loc: parser.getNameLoc(), |
| 2303 | message: "expected sparse_tensor.iter_space type for " |
| 2304 | "iteration space operands" ); |
| 2305 | it.type = spaceTp.getIteratorType(); |
| 2306 | } |
| 2307 | |
| 2308 | if (hasIterArgs) |
| 2309 | if (parser.parseArrowTypeList(result&: state.types)) |
| 2310 | return failure(); |
| 2311 | |
| 2312 | // Resolves input operands. |
| 2313 | if (parser.resolveOperands(operands&: spaces, types&: iterSpaceTps, loc: parser.getNameLoc(), |
| 2314 | result&: state.operands)) |
| 2315 | return failure(); |
| 2316 | |
| 2317 | if (hasIterArgs) { |
| 2318 | // Strip off leading args that used for coordinates. |
| 2319 | MutableArrayRef args = MutableArrayRef(blockArgs).drop_back(N: numCrds); |
| 2320 | if (args.size() != initArgs.size() || args.size() != state.types.size()) { |
| 2321 | return parser.emitError( |
| 2322 | loc: parser.getNameLoc(), |
| 2323 | message: "mismatch in number of iteration arguments and return values" ); |
| 2324 | } |
| 2325 | |
| 2326 | for (auto [it, init, tp] : llvm::zip_equal(t&: args, u&: initArgs, args&: state.types)) { |
| 2327 | it.type = tp; |
| 2328 | if (parser.resolveOperand(operand: init, type: tp, result&: state.operands)) |
| 2329 | return failure(); |
| 2330 | } |
| 2331 | } |
| 2332 | return success(); |
| 2333 | } |
| 2334 | |
| 2335 | static ParseResult |
| 2336 | parseSparseCoIterateLoop(OpAsmParser &parser, OperationState &state, |
| 2337 | SmallVectorImpl<Value> &spacesVals, |
| 2338 | SmallVectorImpl<OpAsmParser::Argument> &blockArgs) { |
| 2339 | |
| 2340 | // Parse "(%spaces, ...)" |
| 2341 | SmallVector<OpAsmParser::UnresolvedOperand> spaces; |
| 2342 | if (parser.parseOperandList(result&: spaces, delimiter: OpAsmParser::Delimiter::Paren)) |
| 2343 | return failure(); |
| 2344 | |
| 2345 | SmallVector<OpAsmParser::Argument> coords; |
| 2346 | if (failed(Result: parseUsedCoordList(parser, state, coords))) |
| 2347 | return failure(); |
| 2348 | size_t numCrds = coords.size(); |
| 2349 | |
| 2350 | // Parse "iter_args(%arg = %init, ...)" |
| 2351 | SmallVector<OpAsmParser::UnresolvedOperand> initArgs; |
| 2352 | bool hasIterArgs = succeeded(Result: parser.parseOptionalKeyword(keyword: "iter_args" )); |
| 2353 | if (hasIterArgs) |
| 2354 | if (parser.parseAssignmentList(lhs&: blockArgs, rhs&: initArgs)) |
| 2355 | return failure(); |
| 2356 | blockArgs.append(RHS: coords); |
| 2357 | |
| 2358 | SmallVector<Type> iterSpaceTps; |
| 2359 | // parse ": (sparse_tensor.iter_space, ...) -> ret" |
| 2360 | if (parser.parseColon() || parser.parseLParen() || |
| 2361 | parser.parseTypeList(result&: iterSpaceTps) || parser.parseRParen()) |
| 2362 | return failure(); |
| 2363 | |
| 2364 | if (iterSpaceTps.size() != spaces.size()) |
| 2365 | return parser.emitError(loc: parser.getNameLoc(), |
| 2366 | message: "mismatch in number of iteration space operands " |
| 2367 | "and iteration space types" ); |
| 2368 | |
| 2369 | if (hasIterArgs) |
| 2370 | if (parser.parseArrowTypeList(result&: state.types)) |
| 2371 | return failure(); |
| 2372 | |
| 2373 | // Resolves input sparse iteration spaces. |
| 2374 | if (parser.resolveOperands(operands&: spaces, types&: iterSpaceTps, loc: parser.getNameLoc(), |
| 2375 | result&: spacesVals)) |
| 2376 | return failure(); |
| 2377 | state.operands.append(RHS: spacesVals); |
| 2378 | |
| 2379 | if (hasIterArgs) { |
| 2380 | // Strip off trailing args that used for coordinates. |
| 2381 | MutableArrayRef args = MutableArrayRef(blockArgs).drop_back(N: numCrds); |
| 2382 | if (args.size() != initArgs.size() || args.size() != state.types.size()) { |
| 2383 | return parser.emitError( |
| 2384 | loc: parser.getNameLoc(), |
| 2385 | message: "mismatch in number of iteration arguments and return values" ); |
| 2386 | } |
| 2387 | |
| 2388 | for (auto [it, init, tp] : llvm::zip_equal(t&: args, u&: initArgs, args&: state.types)) { |
| 2389 | it.type = tp; |
| 2390 | if (parser.resolveOperand(operand: init, type: tp, result&: state.operands)) |
| 2391 | return failure(); |
| 2392 | } |
| 2393 | } |
| 2394 | return success(); |
| 2395 | } |
| 2396 | |
| 2397 | LogicalResult ExtractIterSpaceOp::( |
| 2398 | MLIRContext *ctx, std::optional<Location> loc, ValueRange ops, |
| 2399 | DictionaryAttr attr, PropertyRef prop, RegionRange region, |
| 2400 | SmallVectorImpl<mlir::Type> &ret) { |
| 2401 | |
| 2402 | ExtractIterSpaceOp::Adaptor adaptor(ops, attr, prop, region); |
| 2403 | SparseTensorType stt = getSparseTensorType(val: adaptor.getTensor()); |
| 2404 | ret.push_back(Elt: IterSpaceType::get(context: ctx, encoding: stt.getEncoding(), loLvl: adaptor.getLoLvl(), |
| 2405 | hiLvl: adaptor.getHiLvl())); |
| 2406 | return success(); |
| 2407 | } |
| 2408 | |
| 2409 | LogicalResult ExtractIterSpaceOp::() { |
| 2410 | if (getLoLvl() >= getHiLvl()) |
| 2411 | return emitOpError(message: "expected smaller level low than level high" ); |
| 2412 | |
| 2413 | TypedValue<IteratorType> pIter = getParentIter(); |
| 2414 | if ((pIter && getLoLvl() == 0) || (!pIter && getLoLvl() != 0)) { |
| 2415 | return emitOpError( |
| 2416 | message: "parent iterator should be specified iff level lower bound equals 0" ); |
| 2417 | } |
| 2418 | |
| 2419 | if (pIter) { |
| 2420 | IterSpaceType spaceTp = getExtractedSpace().getType(); |
| 2421 | if (pIter.getType().getEncoding() != spaceTp.getEncoding()) |
| 2422 | return emitOpError( |
| 2423 | message: "mismatch in parent iterator encoding and iteration space encoding." ); |
| 2424 | |
| 2425 | if (spaceTp.getLoLvl() != pIter.getType().getHiLvl()) |
| 2426 | return emitOpError(message: "parent iterator should be used to extract an " |
| 2427 | "iteration space from a consecutive level." ); |
| 2428 | } |
| 2429 | |
| 2430 | return success(); |
| 2431 | } |
| 2432 | |
| 2433 | LogicalResult ExtractValOp::() { |
| 2434 | auto stt = getSparseTensorType(val: getTensor()); |
| 2435 | auto itTp = getIterator().getType(); |
| 2436 | |
| 2437 | if (stt.getEncoding() != itTp.getEncoding()) |
| 2438 | return emitOpError(message: "mismatch in tensor encoding and iterator encoding." ); |
| 2439 | |
| 2440 | if (stt.getLvlRank() != itTp.getHiLvl()) |
| 2441 | return emitOpError(message: "must use last-level iterator to extract values. " ); |
| 2442 | |
| 2443 | return success(); |
| 2444 | } |
| 2445 | |
| 2446 | struct RemoveUnusedLvlCrds : public OpRewritePattern<IterateOp> { |
| 2447 | using Base::Base; |
| 2448 | |
| 2449 | LogicalResult matchAndRewrite(IterateOp iterateOp, |
| 2450 | PatternRewriter &rewriter) const override { |
| 2451 | I64BitSet newUsedLvls(0); |
| 2452 | llvm::BitVector toRemove(iterateOp.getBody()->getNumArguments()); |
| 2453 | for (unsigned i = 0, e = iterateOp.getSpaceDim(); i < e; i++) { |
| 2454 | if (auto crd = iterateOp.getLvlCrd(lvl: i)) { |
| 2455 | if (crd->getUsers().empty()) |
| 2456 | toRemove.set(crd->getArgNumber()); |
| 2457 | else |
| 2458 | newUsedLvls.set(i); |
| 2459 | } |
| 2460 | } |
| 2461 | |
| 2462 | // All coordinates are used. |
| 2463 | if (toRemove.none()) |
| 2464 | return failure(); |
| 2465 | |
| 2466 | rewriter.startOpModification(op: iterateOp); |
| 2467 | iterateOp.setCrdUsedLvls(newUsedLvls); |
| 2468 | iterateOp.getBody()->eraseArguments(eraseIndices: toRemove); |
| 2469 | rewriter.finalizeOpModification(op: iterateOp); |
| 2470 | return success(); |
| 2471 | } |
| 2472 | }; |
| 2473 | |
| 2474 | void IterateOp::getCanonicalizationPatterns(mlir::RewritePatternSet &results, |
| 2475 | mlir::MLIRContext *context) { |
| 2476 | results.add<RemoveUnusedLvlCrds>(arg&: context); |
| 2477 | } |
| 2478 | |
| 2479 | void IterateOp::build(OpBuilder &builder, OperationState &odsState, |
| 2480 | Value iterSpace, ValueRange initArgs) { |
| 2481 | unsigned rank = llvm::cast<IterSpaceType>(Val: iterSpace.getType()).getSpaceDim(); |
| 2482 | // All ones. |
| 2483 | I64BitSet set((1 << rank) - 1); |
| 2484 | return build(odsBuilder&: builder, odsState, iterSpace, initArgs, crdUsedLvls: set); |
| 2485 | } |
| 2486 | |
| 2487 | void IterateOp::build(OpBuilder &builder, OperationState &odsState, |
| 2488 | Value iterSpace, ValueRange initArgs, |
| 2489 | I64BitSet crdUsedLvls) { |
| 2490 | OpBuilder::InsertionGuard guard(builder); |
| 2491 | |
| 2492 | odsState.addOperands(newOperands: iterSpace); |
| 2493 | odsState.addOperands(newOperands: initArgs); |
| 2494 | odsState.getOrAddProperties<Properties>().crdUsedLvls = |
| 2495 | builder.getIntegerAttr(type: builder.getIntegerType(width: 64), value: crdUsedLvls); |
| 2496 | Region *bodyRegion = odsState.addRegion(); |
| 2497 | odsState.addTypes(newTypes: initArgs.getTypes()); |
| 2498 | Block *bodyBlock = builder.createBlock(parent: bodyRegion); |
| 2499 | |
| 2500 | // Starts with a list of user-provided loop arguments. |
| 2501 | for (Value v : initArgs) |
| 2502 | bodyBlock->addArgument(type: v.getType(), loc: v.getLoc()); |
| 2503 | |
| 2504 | // Follows by a list of used coordinates. |
| 2505 | for (unsigned i = 0, e = crdUsedLvls.count(); i < e; i++) |
| 2506 | bodyBlock->addArgument(type: builder.getIndexType(), loc: odsState.location); |
| 2507 | |
| 2508 | // Ends with sparse iterator |
| 2509 | bodyBlock->addArgument( |
| 2510 | type: llvm::cast<IterSpaceType>(Val: iterSpace.getType()).getIteratorType(), |
| 2511 | loc: odsState.location); |
| 2512 | } |
| 2513 | |
| 2514 | ParseResult IterateOp::parse(OpAsmParser &parser, OperationState &result) { |
| 2515 | OpAsmParser::Argument iterator; |
| 2516 | OpAsmParser::UnresolvedOperand iterSpace; |
| 2517 | |
| 2518 | SmallVector<OpAsmParser::Argument> iters, iterArgs; |
| 2519 | if (parseSparseIterateLoop(parser, state&: result, iterators&: iters, blockArgs&: iterArgs)) |
| 2520 | return failure(); |
| 2521 | if (iters.size() != 1) |
| 2522 | return parser.emitError(loc: parser.getNameLoc(), |
| 2523 | message: "expected only one iterator/iteration space" ); |
| 2524 | |
| 2525 | iterArgs.append(RHS: iters); |
| 2526 | Region *body = result.addRegion(); |
| 2527 | if (parser.parseRegion(region&: *body, arguments: iterArgs)) |
| 2528 | return failure(); |
| 2529 | |
| 2530 | IterateOp::ensureTerminator(region&: *body, builder&: parser.getBuilder(), loc: result.location); |
| 2531 | |
| 2532 | // Parse the optional attribute list. |
| 2533 | if (parser.parseOptionalAttrDict(result&: result.attributes)) |
| 2534 | return failure(); |
| 2535 | |
| 2536 | return success(); |
| 2537 | } |
| 2538 | |
| 2539 | /// Prints the initialization list in the form of |
| 2540 | /// <prefix>(%inner = %outer, %inner2 = %outer2, <...>) |
| 2541 | /// where 'inner' values are assumed to be region arguments and 'outer' values |
| 2542 | /// are regular SSA values. |
| 2543 | static void printInitializationList(OpAsmPrinter &p, |
| 2544 | Block::BlockArgListType blocksArgs, |
| 2545 | ValueRange initializers, |
| 2546 | StringRef prefix = "" ) { |
| 2547 | assert(blocksArgs.size() == initializers.size() && |
| 2548 | "expected same length of arguments and initializers" ); |
| 2549 | if (initializers.empty()) |
| 2550 | return; |
| 2551 | |
| 2552 | p << prefix << '('; |
| 2553 | llvm::interleaveComma(c: llvm::zip(t&: blocksArgs, u&: initializers), os&: p, each_fn: [&](auto it) { |
| 2554 | p << std::get<0>(it) << " = " << std::get<1>(it); |
| 2555 | }); |
| 2556 | p << ")" ; |
| 2557 | } |
| 2558 | |
| 2559 | template <typename SparseLoopOp> |
| 2560 | static LogicalResult verifySparseLoopOp(SparseLoopOp op) { |
| 2561 | if (op.getInitArgs().size() != op.getNumResults()) { |
| 2562 | return op.emitOpError( |
| 2563 | "mismatch in number of loop-carried values and defined values" ); |
| 2564 | } |
| 2565 | if (op.getCrdUsedLvls().max() > op.getSpaceDim()) |
| 2566 | return op.emitOpError("required out-of-bound coordinates" ); |
| 2567 | |
| 2568 | return success(); |
| 2569 | } |
| 2570 | |
| 2571 | LogicalResult IterateOp::verify() { return verifySparseLoopOp(op: *this); } |
| 2572 | LogicalResult CoIterateOp::verify() { return verifySparseLoopOp(op: *this); } |
| 2573 | |
| 2574 | void IterateOp::print(OpAsmPrinter &p) { |
| 2575 | p << " " << getIterator() << " in " << getIterSpace(); |
| 2576 | if (!getCrdUsedLvls().empty()) { |
| 2577 | p << " at(" ; |
| 2578 | printOptionalDefinedList(p, size: getSpaceDim(), blocksArgs: getCrds(), definedSet: getCrdUsedLvls()); |
| 2579 | p << ")" ; |
| 2580 | } |
| 2581 | printInitializationList(p, blocksArgs: getRegionIterArgs(), initializers: getInitArgs(), prefix: " iter_args" ); |
| 2582 | |
| 2583 | p << " : " << getIterSpace().getType() << " " ; |
| 2584 | if (!getInitArgs().empty()) |
| 2585 | p.printArrowTypeList(types: getInitArgs().getTypes()); |
| 2586 | |
| 2587 | p << " " ; |
| 2588 | p.printRegion(blocks&: getRegion(), /*printEntryBlockArgs=*/false, |
| 2589 | /*printBlockTerminators=*/!getInitArgs().empty()); |
| 2590 | } |
| 2591 | |
| 2592 | LogicalResult IterateOp::verifyRegions() { |
| 2593 | if (getIterator().getType() != getIterSpace().getType().getIteratorType()) |
| 2594 | return emitOpError(message: "mismatch in iterator and iteration space type" ); |
| 2595 | if (getNumRegionIterArgs() != getNumResults()) |
| 2596 | return emitOpError( |
| 2597 | message: "mismatch in number of basic block args and defined values" ); |
| 2598 | |
| 2599 | auto initArgs = getInitArgs(); |
| 2600 | auto iterArgs = getRegionIterArgs(); |
| 2601 | auto yieldVals = getYieldedValues(); |
| 2602 | auto opResults = getResults(); |
| 2603 | if (!llvm::all_equal(Values: {initArgs.size(), iterArgs.size(), yieldVals.size(), |
| 2604 | opResults.size()})) { |
| 2605 | return emitOpError() << "number mismatch between iter args and results." ; |
| 2606 | } |
| 2607 | |
| 2608 | for (auto [i, init, iter, yield, ret] : |
| 2609 | llvm::enumerate(First&: initArgs, Rest&: iterArgs, Rest&: yieldVals, Rest&: opResults)) { |
| 2610 | if (init.getType() != ret.getType()) |
| 2611 | return emitOpError() << "types mismatch between " << i |
| 2612 | << "th iter operand and defined value" ; |
| 2613 | if (iter.getType() != ret.getType()) |
| 2614 | return emitOpError() << "types mismatch between " << i |
| 2615 | << "th iter region arg and defined value" ; |
| 2616 | if (yield.getType() != ret.getType()) |
| 2617 | return emitOpError() << "types mismatch between " << i |
| 2618 | << "th yield value and defined value" ; |
| 2619 | } |
| 2620 | |
| 2621 | return success(); |
| 2622 | } |
| 2623 | |
| 2624 | /// OpInterfaces' methods implemented by IterateOp. |
| 2625 | SmallVector<Region *> IterateOp::getLoopRegions() { return {&getRegion()}; } |
| 2626 | |
| 2627 | MutableArrayRef<OpOperand> IterateOp::getInitsMutable() { |
| 2628 | return getInitArgsMutable(); |
| 2629 | } |
| 2630 | |
| 2631 | Block::BlockArgListType IterateOp::getRegionIterArgs() { |
| 2632 | return getRegion().getArguments().take_front(N: getNumRegionIterArgs()); |
| 2633 | } |
| 2634 | |
| 2635 | std::optional<MutableArrayRef<OpOperand>> IterateOp::getYieldedValuesMutable() { |
| 2636 | return cast<sparse_tensor::YieldOp>( |
| 2637 | Val: getRegion().getBlocks().front().getTerminator()) |
| 2638 | .getResultsMutable(); |
| 2639 | } |
| 2640 | |
| 2641 | std::optional<ResultRange> IterateOp::getLoopResults() { return getResults(); } |
| 2642 | |
| 2643 | OperandRange IterateOp::getEntrySuccessorOperands(RegionSuccessor successor) { |
| 2644 | return getInitArgs(); |
| 2645 | } |
| 2646 | |
| 2647 | void IterateOp::getSuccessorRegions(RegionBranchPoint point, |
| 2648 | SmallVectorImpl<RegionSuccessor> ®ions) { |
| 2649 | // Both the operation itself and the region may be branching into the body |
| 2650 | // or back into the operation itself. |
| 2651 | regions.push_back(Elt: RegionSuccessor(&getRegion())); |
| 2652 | // It is possible for loop not to enter the body. |
| 2653 | regions.push_back(Elt: RegionSuccessor(getOperation())); |
| 2654 | } |
| 2655 | |
| 2656 | ValueRange IterateOp::getSuccessorInputs(RegionSuccessor successor) { |
| 2657 | return successor.isOperation() ? ValueRange(getResults()) |
| 2658 | : ValueRange(getRegionIterArgs()); |
| 2659 | } |
| 2660 | |
| 2661 | void CoIterateOp::build(OpBuilder &builder, OperationState &odsState, |
| 2662 | ValueRange iterSpaces, ValueRange initArgs, |
| 2663 | unsigned numCases) { |
| 2664 | unsigned rank = |
| 2665 | cast<IterSpaceType>(Val: iterSpaces.front().getType()).getSpaceDim(); |
| 2666 | // All ones. |
| 2667 | I64BitSet set((1 << rank) - 1); |
| 2668 | // Generates all-zero case bits (they only serve as placeholders), which are |
| 2669 | // supposed to be overriden later. We need to preallocate all the regions as |
| 2670 | // mlir::Region cannot be dynamically added later after the operation is |
| 2671 | // created. |
| 2672 | SmallVector<int64_t> caseBits(numCases, 0); |
| 2673 | ArrayAttr cases = builder.getI64ArrayAttr(values: caseBits); |
| 2674 | return CoIterateOp::build(odsBuilder&: builder, odsState, results: initArgs.getTypes(), iterSpaces, |
| 2675 | initArgs, crdUsedLvls: set, cases, |
| 2676 | /*caseRegionsCount=*/numCases); |
| 2677 | } |
| 2678 | |
| 2679 | ParseResult CoIterateOp::parse(OpAsmParser &parser, OperationState &result) { |
| 2680 | |
| 2681 | SmallVector<Value> spaces; |
| 2682 | // The block argument list of each regions, it is arranged in the order of |
| 2683 | // ([used coordinate list], [loop iterations args], [sparse iterator list]). |
| 2684 | SmallVector<OpAsmParser::Argument> blockArgs; |
| 2685 | if (parseSparseCoIterateLoop(parser, state&: result, spacesVals&: spaces, blockArgs)) |
| 2686 | return failure(); |
| 2687 | |
| 2688 | result.addAttribute(name: "operandSegmentSizes" , |
| 2689 | attr: parser.getBuilder().getDenseI32ArrayAttr( |
| 2690 | values: {static_cast<int32_t>(spaces.size()), |
| 2691 | static_cast<int32_t>(result.types.size())})); |
| 2692 | |
| 2693 | SmallVector<Attribute> cases; |
| 2694 | while (succeeded(Result: parser.parseOptionalKeyword(keyword: "case" ))) { |
| 2695 | // Parse one region per case. |
| 2696 | I64BitSet definedItSet; |
| 2697 | SmallVector<OpAsmParser::Argument> definedIts; |
| 2698 | if (parseOptionalDefinedList(parser, state&: result, definedSet&: definedItSet, definedArgs&: definedIts, |
| 2699 | maxCnt: spaces.size(), delimiter: OpAsmParser::Delimiter::None)) |
| 2700 | return failure(); |
| 2701 | |
| 2702 | cases.push_back(Elt: parser.getBuilder().getI64IntegerAttr(value: definedItSet)); |
| 2703 | |
| 2704 | for (auto [i, definedIdx] : llvm::enumerate(First: definedItSet.bits())) { |
| 2705 | // Resolve the iterator type based on the iteration space type. |
| 2706 | auto spaceTp = llvm::cast<IterSpaceType>(Val: spaces[definedIdx].getType()); |
| 2707 | definedIts[i].type = spaceTp.getIteratorType(); |
| 2708 | } |
| 2709 | definedIts.insert(I: definedIts.begin(), From: blockArgs.begin(), To: blockArgs.end()); |
| 2710 | Region *body = result.addRegion(); |
| 2711 | if (parser.parseRegion(region&: *body, arguments: definedIts)) |
| 2712 | return failure(); |
| 2713 | |
| 2714 | CoIterateOp::ensureTerminator(region&: *body, builder&: parser.getBuilder(), loc: result.location); |
| 2715 | } |
| 2716 | |
| 2717 | result.addAttribute(name: "cases" , attr: ArrayAttr::get(context: parser.getContext(), value: cases)); |
| 2718 | |
| 2719 | // Parse the optional attribute list. |
| 2720 | if (parser.parseOptionalAttrDict(result&: result.attributes)) |
| 2721 | return failure(); |
| 2722 | |
| 2723 | return success(); |
| 2724 | } |
| 2725 | |
| 2726 | void CoIterateOp::print(OpAsmPrinter &p) { |
| 2727 | p << " (" ; |
| 2728 | llvm::interleaveComma(c: getIterSpaces(), os&: p, each_fn: [&](auto s) { p << s; }); |
| 2729 | p << ")" ; |
| 2730 | |
| 2731 | if (!getCrdUsedLvls().empty()) { |
| 2732 | p << " at(" ; |
| 2733 | printOptionalDefinedList(p, size: getSpaceDim(), blocksArgs: getCrds(regionIdx: 0), definedSet: getCrdUsedLvls()); |
| 2734 | p << ")" ; |
| 2735 | } |
| 2736 | |
| 2737 | printInitializationList(p, blocksArgs: getRegionIterArgs(regionIdx: 0), initializers: getInitArgs(), prefix: " iter_args" ); |
| 2738 | |
| 2739 | p << " : (" << getIterSpaces().getTypes() << ")" ; |
| 2740 | if (!getInitArgs().empty()) |
| 2741 | p.printArrowTypeList(types: getInitArgs().getTypes()); |
| 2742 | |
| 2743 | for (unsigned idx = 0, e = getRegions().size(); idx < e; idx++) { |
| 2744 | p.printNewline(); |
| 2745 | p << "case " ; |
| 2746 | printOptionalDefinedList(p, size: getIterSpaces().size(), blocksArgs: getRegionIterators(regionIdx: idx), |
| 2747 | definedSet: getRegionDefinedSpace(regionIdx: idx)); |
| 2748 | p << " " ; |
| 2749 | p.printRegion(blocks&: getRegion(i: idx), /*printEntryBlockArgs=*/false, |
| 2750 | /*printBlockTerminators=*/!getInitArgs().empty()); |
| 2751 | } |
| 2752 | } |
| 2753 | |
| 2754 | ValueRange CoIterateOp::getYieldedValues(unsigned regionIdx) { |
| 2755 | return cast<sparse_tensor::YieldOp>( |
| 2756 | Val: getRegion(i: regionIdx).getBlocks().front().getTerminator()) |
| 2757 | .getResults(); |
| 2758 | } |
| 2759 | |
| 2760 | LogicalResult CoIterateOp::verifyRegions() { |
| 2761 | for (unsigned r = 0, e = getNumRegions(); r < e; r++) { |
| 2762 | if (getNumRegionIterArgs() != getNumResults()) |
| 2763 | return emitOpError( |
| 2764 | message: "mismatch in number of basic block args and defined values" ); |
| 2765 | |
| 2766 | auto initArgs = getInitArgs(); |
| 2767 | auto iterArgs = getRegionIterArgs(regionIdx: r); |
| 2768 | auto yieldVals = getYieldedValues(regionIdx: r); |
| 2769 | auto opResults = getResults(); |
| 2770 | if (!llvm::all_equal(Values: {initArgs.size(), iterArgs.size(), yieldVals.size(), |
| 2771 | opResults.size()})) { |
| 2772 | return emitOpError() |
| 2773 | << "number mismatch between iter args and results on " << r |
| 2774 | << "th region" ; |
| 2775 | } |
| 2776 | |
| 2777 | for (auto [i, init, iter, yield, ret] : |
| 2778 | llvm::enumerate(First&: initArgs, Rest&: iterArgs, Rest&: yieldVals, Rest&: opResults)) { |
| 2779 | if (init.getType() != ret.getType()) |
| 2780 | return emitOpError() |
| 2781 | << "types mismatch between " << i |
| 2782 | << "th iter operand and defined value on " << r << "th region" ; |
| 2783 | if (iter.getType() != ret.getType()) |
| 2784 | return emitOpError() << "types mismatch between " << i |
| 2785 | << "th iter region arg and defined value on " << r |
| 2786 | << "th region" ; |
| 2787 | if (yield.getType() != ret.getType()) |
| 2788 | return emitOpError() |
| 2789 | << "types mismatch between " << i |
| 2790 | << "th yield value and defined value on " << r << "th region" ; |
| 2791 | } |
| 2792 | } |
| 2793 | |
| 2794 | auto cases = getRegionDefinedSpaces(); |
| 2795 | llvm::SmallSetVector<uint64_t, 8> set(cases.begin(), cases.end()); |
| 2796 | if (set.size() != getNumRegions()) |
| 2797 | return emitOpError(message: "contains duplicated cases." ); |
| 2798 | |
| 2799 | return success(); |
| 2800 | } |
| 2801 | |
| 2802 | SmallVector<Region *> CoIterateOp::getSubCasesOf(unsigned regionIdx) { |
| 2803 | SmallVector<Region *> ret; |
| 2804 | I64BitSet caseBit = getRegionDefinedSpace(regionIdx); |
| 2805 | for (Region &r : getCaseRegions()) |
| 2806 | if (getRegionDefinedSpace(regionIdx: r.getRegionNumber()).isSubSetOf(p: caseBit)) |
| 2807 | ret.push_back(Elt: &r); |
| 2808 | |
| 2809 | return ret; |
| 2810 | } |
| 2811 | |
| 2812 | //===----------------------------------------------------------------------===// |
| 2813 | // Sparse Tensor Dialect Setups. |
| 2814 | //===----------------------------------------------------------------------===// |
| 2815 | |
| 2816 | /// Materialize a single constant operation from a given attribute value with |
| 2817 | /// the desired resultant type. |
| 2818 | Operation *SparseTensorDialect::materializeConstant(OpBuilder &builder, |
| 2819 | Attribute value, Type type, |
| 2820 | Location loc) { |
| 2821 | if (auto op = arith::ConstantOp::materialize(builder, value, type, loc)) |
| 2822 | return op; |
| 2823 | return nullptr; |
| 2824 | } |
| 2825 | |
| 2826 | void SparseTensorDialect::initialize() { |
| 2827 | addAttributes< |
| 2828 | #define GET_ATTRDEF_LIST |
| 2829 | #include "mlir/Dialect/SparseTensor/IR/SparseTensorAttrDefs.cpp.inc" |
| 2830 | >(); |
| 2831 | addTypes< |
| 2832 | #define GET_TYPEDEF_LIST |
| 2833 | #include "mlir/Dialect/SparseTensor/IR/SparseTensorTypes.cpp.inc" |
| 2834 | >(); |
| 2835 | addOperations< |
| 2836 | #define GET_OP_LIST |
| 2837 | #include "mlir/Dialect/SparseTensor/IR/SparseTensorOps.cpp.inc" |
| 2838 | >(); |
| 2839 | declarePromisedInterfaces< |
| 2840 | bufferization::BufferizableOpInterface, ConcatenateOp, ConvertOp, LoadOp, |
| 2841 | NewOp, NumberOfEntriesOp, AssembleOp, DisassembleOp, |
| 2842 | ToCoordinatesBufferOp, ToCoordinatesOp, ToPositionsOp, ToValuesOp>(); |
| 2843 | } |
| 2844 | |
| 2845 | #define GET_OP_CLASSES |
| 2846 | #include "mlir/Dialect/SparseTensor/IR/SparseTensorOps.cpp.inc" |
| 2847 | |
| 2848 | #include "mlir/Dialect/SparseTensor/IR/SparseTensorOpsDialect.cpp.inc" |
| 2849 | |