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.
33static mlir::ParseResult parseLevelRange(mlir::AsmParser &,
34 mlir::sparse_tensor::Level &,
35 mlir::sparse_tensor::Level &);
36static 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
42using namespace mlir;
43using namespace mlir::sparse_tensor;
44
45// Support hashing LevelType such that SparseTensorEncodingAttr can be hashed as
46// well.
47namespace mlir::sparse_tensor {
48static 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
57static 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
70static SmallVector<Size>
71getSparseFieldShape(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
94static constexpr Level kInvalidLevel = -1u;
95static constexpr Level kInvalidFieldIndex = -1u;
96static constexpr FieldIndex kDataFieldStartingIdx = 0;
97
98void 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
145void 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
181unsigned 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
191unsigned 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
204std::pair<FieldIndex, unsigned>
205StorageLayout::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
237std::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
242std::optional<uint64_t> SparseTensorDimSliceAttr::getStaticOffset() const {
243 return getStatic(v: getOffset());
244}
245
246std::optional<uint64_t> SparseTensorDimSliceAttr::getStaticStride() const {
247 return getStatic(v: getStride());
248}
249
250std::optional<uint64_t> SparseTensorDimSliceAttr::getStaticSize() const {
251 return getStatic(v: getSize());
252}
253
254bool SparseTensorDimSliceAttr::isCompletelyDynamic() const {
255 return isDynamic(v: getOffset()) && isDynamic(v: getStride()) &&
256 isDynamic(v: getSize());
257}
258
259std::string SparseTensorDimSliceAttr::getStaticString(int64_t v) {
260 return isDynamic(v) ? "?" : std::to_string(val: v);
261}
262
263void 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
274void SparseTensorDimSliceAttr::print(AsmPrinter &printer) const {
275 print(os&: printer.getStream());
276}
277
278static 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
296Attribute 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
312LogicalResult
313SparseTensorDimSliceAttr::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
324SparseTensorEncodingAttr
325SparseTensorEncodingAttr::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
332SparseTensorEncodingAttr
333SparseTensorEncodingAttr::withDimToLvl(SparseTensorEncodingAttr enc) const {
334 return withDimToLvl(dimToLvl: enc ? enc.getDimToLvl() : AffineMap());
335}
336
337SparseTensorEncodingAttr SparseTensorEncodingAttr::withoutDimToLvl() const {
338 return withDimToLvl(dimToLvl: AffineMap());
339}
340
341SparseTensorEncodingAttr
342SparseTensorEncodingAttr::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
350SparseTensorEncodingAttr SparseTensorEncodingAttr::withoutBitWidths() const {
351 return withBitWidths(posWidth: 0, crdWidth: 0);
352}
353
354SparseTensorEncodingAttr
355SparseTensorEncodingAttr::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
362SparseTensorEncodingAttr SparseTensorEncodingAttr::withoutExplicitVal() const {
363 return withExplicitVal(explicitVal: Attribute());
364}
365
366SparseTensorEncodingAttr
367SparseTensorEncodingAttr::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
374SparseTensorEncodingAttr SparseTensorEncodingAttr::withoutImplicitVal() const {
375 return withImplicitVal(implicitVal: Attribute());
376}
377
378SparseTensorEncodingAttr 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
385SparseTensorEncodingAttr SparseTensorEncodingAttr::withoutDimSlices() const {
386 return withDimSlices(dimSlices: ArrayRef<SparseTensorDimSliceAttr>{});
387}
388
389uint64_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
395bool SparseTensorEncodingAttr::isAllDense() const {
396 return !getImpl() || llvm::all_of(Range: getLvlTypes(), P: isDenseLT);
397}
398
399bool SparseTensorEncodingAttr::isAllOrdered() const {
400 return !getImpl() || llvm::all_of(Range: getLvlTypes(), P: isOrderedLT);
401}
402
403Type 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
411Type 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
419MemRefType 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
425MemRefType 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
431bool SparseTensorEncodingAttr::isIdentity() const {
432 return !getImpl() || !getDimToLvl() || getDimToLvl().isIdentity();
433}
434
435bool SparseTensorEncodingAttr::isPermutation() const {
436 return !getImpl() || !getDimToLvl() || getDimToLvl().isPermutation();
437}
438
439Dimension SparseTensorEncodingAttr::getDimRank() const {
440 assert(getImpl() && "Uninitialized SparseTensorEncodingAttr");
441 const auto dimToLvl = getDimToLvl();
442 return dimToLvl ? dimToLvl.getNumDims() : getLvlRank();
443}
444
445Level SparseTensorEncodingAttr::getLvlRank() const {
446 assert(getImpl() && "Uninitialized SparseTensorEncodingAttr");
447 return getLvlTypes().size();
448}
449
450LevelType 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
457bool SparseTensorEncodingAttr::isSlice() const {
458 assert(getImpl() && "Uninitialized SparseTensorEncodingAttr");
459 return !getDimSlices().empty();
460}
461
462SparseTensorDimSliceAttr
463SparseTensorEncodingAttr::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
470std::optional<uint64_t>
471SparseTensorEncodingAttr::getStaticDimSliceOffset(Dimension dim) const {
472 return getDimSlice(dim).getStaticOffset();
473}
474
475std::optional<uint64_t>
476SparseTensorEncodingAttr::getStaticDimSliceStride(Dimension dim) const {
477 return getDimSlice(dim).getStaticStride();
478}
479
480std::optional<uint64_t>
481SparseTensorEncodingAttr::getStaticLvlSliceOffset(Level lvl) const {
482 return getStaticDimSliceOffset(dim: toDim(enc: *this, l: lvl));
483}
484
485std::optional<uint64_t>
486SparseTensorEncodingAttr::getStaticLvlSliceStride(Level lvl) const {
487 return getStaticDimSliceStride(dim: toDim(enc: *this, l: lvl));
488}
489
490SmallVector<int64_t>
491SparseTensorEncodingAttr::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
564ValueRange
565SparseTensorEncodingAttr::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
579Attribute 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
726void 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
751void 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
763void 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
781void 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
794LogicalResult 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
920static 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
932LogicalResult 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
982Level 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
991SmallVector<COOSegment>
992mlir::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
1027bool 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
1042RankedTensorType
1043mlir::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
1067SparseTensorEncodingAttr
1068mlir::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
1076AffineMap 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
1091AffineMap 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
1149SmallVector<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
1166bool 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
1211bool 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
1221Dimension 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
1230Level 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.
1243static SparseTensorEncodingAttr
1244getNormalizedEncodingForSpecifier(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
1263StorageSpecifierType
1264StorageSpecifierType::get(MLIRContext *ctx, SparseTensorEncodingAttr encoding) {
1265 return Base::get(ctx, args: getNormalizedEncodingForSpecifier(enc: encoding));
1266}
1267
1268StorageSpecifierType
1269StorageSpecifierType::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
1280static LogicalResult lvlIsInBounds(Level lvl, Value tensor) {
1281 return success(IsSuccess: lvl < getSparseTensorType(val: tensor).getLvlRank());
1282}
1283
1284static 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
1289static 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
1320static 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
1334static 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
1390LogicalResult 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
1397LogicalResult 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
1411LogicalResult 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
1432OpFoldResult ConvertOp::fold(FoldAdaptor adaptor) {
1433 if (getType() == getSource().getType())
1434 return getSource();
1435 return {};
1436}
1437
1438bool ConvertOp::needsExtraSort() {
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
1464LogicalResult 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
1477LogicalResult 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
1523void 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
1529LogicalResult 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
1539std::optional<uint64_t> LvlOp::getConstantLvlIndex() {
1540 return getConstantIntValue(ofr: getIndex());
1541}
1542
1543Speculation::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
1553OpFoldResult 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
1579void 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
1590LogicalResult 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
1625OpFoldResult 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
1637template <typename ToBufferOp>
1638static 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
1668LogicalResult 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
1677LogicalResult
1678ToPositionsOp::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
1685LogicalResult 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
1694LogicalResult
1695ToCoordinatesOp::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
1702LogicalResult 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
1709LogicalResult 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
1717LogicalResult 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
1725LogicalResult 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
1733LogicalResult 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
1740LogicalResult 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
1747LogicalResult GetStorageSpecifierOp::verify() {
1748 return verifySparsifierGetterSetter(mdKind: getSpecifierKind(), lvl: getLevel(),
1749 md: getSpecifier(), op: getOperation());
1750}
1751
1752template <typename SpecifierOp>
1753static SetStorageSpecifierOp getSpecifierSetDef(SpecifierOp op) {
1754 return op.getSpecifier().template getDefiningOp<SetStorageSpecifierOp>();
1755}
1756
1757OpFoldResult 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
1766LogicalResult SetStorageSpecifierOp::verify() {
1767 return verifySparsifierGetterSetter(mdKind: getSpecifierKind(), lvl: getLevel(),
1768 md: getSpecifier(), op: getOperation());
1769}
1770
1771template <class T>
1772static LogicalResult verifyNumBlockArgs(T *op, Region &region,
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
1804LogicalResult 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
1841LogicalResult 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
1875bool ConcatenateOp::needsExtraSort() {
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
1892LogicalResult 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
1950void 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
1955LogicalResult 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
1964LogicalResult 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
1971void 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 &region = *result.regions.front();
1994 Block *bodyBlock =
1995 builder.createBlock(parent: &region, 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
2002LogicalResult 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
2041OpFoldResult ReorderCOOOp::fold(FoldAdaptor adaptor) {
2042 if (getSparseTensorEncoding(type: getInputCoo().getType()) ==
2043 getSparseTensorEncoding(type: getResultCoo().getType()))
2044 return getInputCoo();
2045
2046 return {};
2047}
2048
2049LogicalResult 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
2067LogicalResult 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
2074LogicalResult 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
2083LogicalResult 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
2126IterSpaceType IteratorType::getIterSpaceType() const {
2127 return IterSpaceType::get(context: getContext(), encoding: getEncoding(), loLvl: getLoLvl(),
2128 hiLvl: getHiLvl());
2129}
2130
2131IteratorType 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
2137static 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
2158static 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
2171static 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
2181static 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).
2192static 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
2222static 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
2241static ParseResult
2242parseUsedCoordList(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
2260static ParseResult
2261parseSparseIterateLoop(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
2335static ParseResult
2336parseSparseCoIterateLoop(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
2397LogicalResult ExtractIterSpaceOp::inferReturnTypes(
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
2409LogicalResult ExtractIterSpaceOp::verify() {
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
2433LogicalResult ExtractValOp::verify() {
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
2446struct 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
2474void IterateOp::getCanonicalizationPatterns(mlir::RewritePatternSet &results,
2475 mlir::MLIRContext *context) {
2476 results.add<RemoveUnusedLvlCrds>(arg&: context);
2477}
2478
2479void 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
2487void 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
2514ParseResult 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.
2543static 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
2559template <typename SparseLoopOp>
2560static 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
2571LogicalResult IterateOp::verify() { return verifySparseLoopOp(op: *this); }
2572LogicalResult CoIterateOp::verify() { return verifySparseLoopOp(op: *this); }
2573
2574void 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
2592LogicalResult 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.
2625SmallVector<Region *> IterateOp::getLoopRegions() { return {&getRegion()}; }
2626
2627MutableArrayRef<OpOperand> IterateOp::getInitsMutable() {
2628 return getInitArgsMutable();
2629}
2630
2631Block::BlockArgListType IterateOp::getRegionIterArgs() {
2632 return getRegion().getArguments().take_front(N: getNumRegionIterArgs());
2633}
2634
2635std::optional<MutableArrayRef<OpOperand>> IterateOp::getYieldedValuesMutable() {
2636 return cast<sparse_tensor::YieldOp>(
2637 Val: getRegion().getBlocks().front().getTerminator())
2638 .getResultsMutable();
2639}
2640
2641std::optional<ResultRange> IterateOp::getLoopResults() { return getResults(); }
2642
2643OperandRange IterateOp::getEntrySuccessorOperands(RegionSuccessor successor) {
2644 return getInitArgs();
2645}
2646
2647void IterateOp::getSuccessorRegions(RegionBranchPoint point,
2648 SmallVectorImpl<RegionSuccessor> &regions) {
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
2656ValueRange IterateOp::getSuccessorInputs(RegionSuccessor successor) {
2657 return successor.isOperation() ? ValueRange(getResults())
2658 : ValueRange(getRegionIterArgs());
2659}
2660
2661void 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
2679ParseResult 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
2726void 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
2754ValueRange CoIterateOp::getYieldedValues(unsigned regionIdx) {
2755 return cast<sparse_tensor::YieldOp>(
2756 Val: getRegion(i: regionIdx).getBlocks().front().getTerminator())
2757 .getResults();
2758}
2759
2760LogicalResult 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
2802SmallVector<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.
2818Operation *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
2826void 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