1//===- CodegenUtils.cpp - Utilities for generating MLIR -------------------===//
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 "CodegenUtils.h"
10
11#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
12#include "mlir/Dialect/LLVMIR/LLVMDialectDecl.h"
13#include "mlir/Dialect/Linalg/IR/Linalg.h"
14#include "mlir/Dialect/Linalg/Utils/Utils.h"
15#include "mlir/Dialect/MemRef/IR/MemRef.h"
16#include "mlir/Dialect/Tensor/IR/Tensor.h"
17#include "mlir/IR/Types.h"
18#include "mlir/IR/Value.h"
19#include <optional>
20
21using namespace mlir;
22using namespace mlir::sparse_tensor;
23
24//===----------------------------------------------------------------------===//
25// ExecutionEngine/SparseTensorUtils helper functions.
26//===----------------------------------------------------------------------===//
27
28OverheadType mlir::sparse_tensor::overheadTypeEncoding(unsigned width) {
29 switch (width) {
30 case 64:
31 return OverheadType::kU64;
32 case 32:
33 return OverheadType::kU32;
34 case 16:
35 return OverheadType::kU16;
36 case 8:
37 return OverheadType::kU8;
38 case 0:
39 return OverheadType::kIndex;
40 }
41 llvm_unreachable("Unsupported overhead bitwidth");
42}
43
44OverheadType mlir::sparse_tensor::overheadTypeEncoding(Type tp) {
45 if (tp.isIndex())
46 return OverheadType::kIndex;
47 if (auto intTp = dyn_cast<IntegerType>(Val&: tp))
48 return overheadTypeEncoding(width: intTp.getWidth());
49 llvm_unreachable("Unknown overhead type");
50}
51
52Type mlir::sparse_tensor::getOverheadType(Builder &builder, OverheadType ot) {
53 switch (ot) {
54 case OverheadType::kIndex:
55 return builder.getIndexType();
56 case OverheadType::kU64:
57 return builder.getIntegerType(width: 64);
58 case OverheadType::kU32:
59 return builder.getIntegerType(width: 32);
60 case OverheadType::kU16:
61 return builder.getIntegerType(width: 16);
62 case OverheadType::kU8:
63 return builder.getIntegerType(width: 8);
64 }
65 llvm_unreachable("Unknown OverheadType");
66}
67
68OverheadType
69mlir::sparse_tensor::posTypeEncoding(SparseTensorEncodingAttr enc) {
70 return overheadTypeEncoding(width: enc.getPosWidth());
71}
72
73OverheadType
74mlir::sparse_tensor::crdTypeEncoding(SparseTensorEncodingAttr enc) {
75 return overheadTypeEncoding(width: enc.getCrdWidth());
76}
77
78// TODO: we ought to add some `static_assert` tests to ensure that the
79// `STEA::get{Pos,Crd}Type` methods agree with `getOverheadType(builder,
80// {pos,crd}OverheadTypeEncoding(enc))`
81
82// TODO: Adjust the naming convention for the constructors of
83// `OverheadType` so we can use the `MLIR_SPARSETENSOR_FOREVERY_O` x-macro
84// here instead of `MLIR_SPARSETENSOR_FOREVERY_FIXED_O`; to further reduce
85// the possibility of typo bugs or things getting out of sync.
86StringRef mlir::sparse_tensor::overheadTypeFunctionSuffix(OverheadType ot) {
87 switch (ot) {
88 case OverheadType::kIndex:
89 return "0";
90#define CASE(ONAME, O) \
91 case OverheadType::kU##ONAME: \
92 return #ONAME;
93 MLIR_SPARSETENSOR_FOREVERY_FIXED_O(CASE)
94#undef CASE
95 }
96 llvm_unreachable("Unknown OverheadType");
97}
98
99StringRef mlir::sparse_tensor::overheadTypeFunctionSuffix(Type tp) {
100 return overheadTypeFunctionSuffix(ot: overheadTypeEncoding(tp));
101}
102
103PrimaryType mlir::sparse_tensor::primaryTypeEncoding(Type elemTp) {
104 if (elemTp.isF64())
105 return PrimaryType::kF64;
106 if (elemTp.isF32())
107 return PrimaryType::kF32;
108 if (elemTp.isF16())
109 return PrimaryType::kF16;
110 if (elemTp.isBF16())
111 return PrimaryType::kBF16;
112 if (elemTp.isInteger(width: 64))
113 return PrimaryType::kI64;
114 if (elemTp.isInteger(width: 32))
115 return PrimaryType::kI32;
116 if (elemTp.isInteger(width: 16))
117 return PrimaryType::kI16;
118 if (elemTp.isInteger(width: 8))
119 return PrimaryType::kI8;
120 if (auto complexTp = dyn_cast<ComplexType>(Val&: elemTp)) {
121 auto complexEltTp = complexTp.getElementType();
122 if (complexEltTp.isF64())
123 return PrimaryType::kC64;
124 if (complexEltTp.isF32())
125 return PrimaryType::kC32;
126 }
127 llvm_unreachable("Unknown primary type");
128}
129
130StringRef mlir::sparse_tensor::primaryTypeFunctionSuffix(PrimaryType pt) {
131 switch (pt) {
132#define CASE(VNAME, V) \
133 case PrimaryType::k##VNAME: \
134 return #VNAME;
135 MLIR_SPARSETENSOR_FOREVERY_V(CASE)
136#undef CASE
137 }
138 llvm_unreachable("Unknown PrimaryType");
139}
140
141StringRef mlir::sparse_tensor::primaryTypeFunctionSuffix(Type elemTp) {
142 return primaryTypeFunctionSuffix(pt: primaryTypeEncoding(elemTp));
143}
144
145//===----------------------------------------------------------------------===//
146// Misc code generators.
147//===----------------------------------------------------------------------===//
148
149Value sparse_tensor::genCast(OpBuilder &builder, Location loc, Value value,
150 Type dstTp) {
151 const Type srcTp = value.getType();
152 if (srcTp == dstTp)
153 return value;
154
155 // int <=> index
156 if (isa<IndexType>(Val: srcTp) || isa<IndexType>(Val: dstTp))
157 return arith::IndexCastOp::create(builder, location: loc, out: dstTp, in: value);
158
159 const auto srcIntTp = dyn_cast_or_null<IntegerType>(Val: srcTp);
160 const bool isUnsignedCast = srcIntTp ? srcIntTp.isUnsigned() : false;
161 return mlir::convertScalarToDtype(b&: builder, loc, operand: value, toType: dstTp, isUnsignedCast);
162}
163
164Value sparse_tensor::genScalarToTensor(OpBuilder &builder, Location loc,
165 Value elem, Type dstTp) {
166 if (auto rtp = dyn_cast<RankedTensorType>(Val&: dstTp)) {
167 // Scalars can only be converted to 0-ranked tensors.
168 assert(rtp.getRank() == 0);
169 elem = sparse_tensor::genCast(builder, loc, value: elem, dstTp: rtp.getElementType());
170 return tensor::FromElementsOp::create(builder, location: loc, result: rtp, elements: elem);
171 }
172 return sparse_tensor::genCast(builder, loc, value: elem, dstTp);
173}
174
175Value sparse_tensor::genIndexLoad(OpBuilder &builder, Location loc, Value mem,
176 ValueRange s) {
177 Value load = memref::LoadOp::create(builder, location: loc, memref: mem, indices: s);
178 if (!isa<IndexType>(Val: load.getType())) {
179 if (load.getType().getIntOrFloatBitWidth() < 64)
180 load = arith::ExtUIOp::create(builder, location: loc, out: builder.getI64Type(), in: load);
181 load =
182 arith::IndexCastOp::create(builder, location: loc, out: builder.getIndexType(), in: load);
183 }
184 return load;
185}
186
187mlir::TypedAttr mlir::sparse_tensor::getOneAttr(Builder &builder, Type tp) {
188 if (isa<FloatType>(Val: tp))
189 return builder.getFloatAttr(type: tp, value: 1.0);
190 if (isa<IndexType>(Val: tp))
191 return builder.getIndexAttr(value: 1);
192 if (auto intTp = dyn_cast<IntegerType>(Val&: tp))
193 return builder.getIntegerAttr(type: tp, value: APInt(intTp.getWidth(), 1));
194 if (isa<RankedTensorType, VectorType>(Val: tp)) {
195 auto shapedTp = cast<ShapedType>(Val&: tp);
196 if (auto one = getOneAttr(builder, tp: shapedTp.getElementType()))
197 return DenseElementsAttr::get(type: shapedTp, values: one);
198 }
199 llvm_unreachable("Unsupported attribute type");
200}
201
202Value mlir::sparse_tensor::genIsNonzero(OpBuilder &builder, mlir::Location loc,
203 Value v) {
204 Type tp = v.getType();
205 Value zero = constantZero(builder, loc, tp);
206 if (isa<FloatType>(Val: tp))
207 return arith::CmpFOp::create(builder, location: loc, predicate: arith::CmpFPredicate::UNE, lhs: v,
208 rhs: zero);
209 if (tp.isIntOrIndex())
210 return arith::CmpIOp::create(builder, location: loc, predicate: arith::CmpIPredicate::ne, lhs: v,
211 rhs: zero);
212 if (isa<ComplexType>(Val: tp))
213 return complex::NotEqualOp::create(builder, location: loc, lhs: v, rhs: zero);
214 llvm_unreachable("Non-numeric type");
215}
216
217void mlir::sparse_tensor::genReshapeDstShape(
218 OpBuilder &builder, Location loc, SmallVectorImpl<Value> &dstShape,
219 ArrayRef<Value> srcShape, ArrayRef<Size> staticDstShape,
220 ArrayRef<ReassociationIndices> reassociation) {
221 // Collapse shape.
222 if (reassociation.size() < srcShape.size()) {
223 unsigned start = 0;
224 for (const auto &map : llvm::enumerate(First&: reassociation)) {
225 auto dstDim = constantIndex(builder, loc, i: 1);
226 for (unsigned i = start; i < start + map.value().size(); i++) {
227 dstDim = arith::MulIOp::create(builder, location: loc, lhs: dstDim, rhs: srcShape[i]);
228 }
229 dstShape.push_back(Elt: dstDim);
230 start = start + map.value().size();
231 }
232 assert(start == srcShape.size());
233 return;
234 }
235
236 // Expand shape.
237 assert(reassociation.size() == srcShape.size());
238 unsigned start = 0;
239 // Expand the i-th dimension in srcShape.
240 for (unsigned i = 0, size = srcShape.size(); i < size; i++) {
241 const auto &map = reassociation[i];
242 auto srcDim = srcShape[i];
243 // Iterate through dimensions expanded from the i-th dimension.
244 for (unsigned j = start; j < start + map.size(); j++) {
245 // There can be only one dynamic sized dimension among dimensions
246 // expanded from the i-th dimension in srcShape.
247 // For example, if srcDim = 8, then the expanded shape could be <2x?x2>,
248 // but not <2x?x?>.
249 if (staticDstShape[j] == ShapedType::kDynamic) {
250 // The expanded dimension has dynamic size. We compute the dimension
251 // by dividing srcDim by the product of the static dimensions.
252 Size product = 1;
253 for (unsigned k = start; k < start + map.size(); k++) {
254 if (staticDstShape[k] != ShapedType::kDynamic) {
255 product *= staticDstShape[k];
256 }
257 }
258 // Compute the dynamic dimension size.
259 Value productVal = constantIndex(builder, loc, i: product);
260 Value dynamicSize =
261 arith::DivUIOp::create(builder, location: loc, lhs: srcDim, rhs: productVal);
262 dstShape.push_back(Elt: dynamicSize);
263 } else {
264 // The expanded dimension is statically known.
265 dstShape.push_back(Elt: constantIndex(builder, loc, i: staticDstShape[j]));
266 }
267 }
268 start = start + map.size();
269 }
270 assert(start == staticDstShape.size());
271}
272
273void mlir::sparse_tensor::reshapeCvs(
274 OpBuilder &builder, Location loc,
275 ArrayRef<ReassociationIndices> reassociation, // NOLINT
276 ValueRange srcSizes, ValueRange srcCvs, // NOLINT
277 ValueRange dstSizes, SmallVectorImpl<Value> &dstCvs) {
278 const unsigned srcRank = srcSizes.size();
279 const unsigned dstRank = dstSizes.size();
280 assert(srcRank == srcCvs.size() && "Source rank mismatch");
281 const bool isCollapse = srcRank > dstRank;
282 const ValueRange sizes = isCollapse ? srcSizes : dstSizes;
283 // Iterate over reassociation map.
284 unsigned i = 0;
285 unsigned start = 0;
286 for (const auto &map : llvm::enumerate(First&: reassociation)) {
287 // Prepare strides information in dimension slice.
288 Value linear = constantIndex(builder, loc, i: 1);
289 for (unsigned j = start, end = start + map.value().size(); j < end; j++) {
290 linear = arith::MulIOp::create(builder, location: loc, lhs: linear, rhs: sizes[j]);
291 }
292 // Start expansion.
293 Value val;
294 if (!isCollapse)
295 val = srcCvs[i];
296 // Iterate over dimension slice.
297 for (unsigned j = start, end = start + map.value().size(); j < end; j++) {
298 linear = arith::DivUIOp::create(builder, location: loc, lhs: linear, rhs: sizes[j]);
299 if (isCollapse) {
300 const Value mul =
301 arith::MulIOp::create(builder, location: loc, lhs: srcCvs[j], rhs: linear);
302 val = val ? arith::AddIOp::create(builder, location: loc, lhs: val, rhs: mul) : mul;
303 } else {
304 const Value old = val;
305 val = arith::DivUIOp::create(builder, location: loc, lhs: val, rhs: linear);
306 assert(dstCvs.size() == j);
307 dstCvs.push_back(Elt: val);
308 val = arith::RemUIOp::create(builder, location: loc, lhs: old, rhs: linear);
309 }
310 }
311 // Finalize collapse.
312 if (isCollapse) {
313 assert(dstCvs.size() == i);
314 dstCvs.push_back(Elt: val);
315 }
316 start += map.value().size();
317 i++;
318 }
319 assert(dstCvs.size() == dstRank);
320}
321
322FlatSymbolRefAttr mlir::sparse_tensor::getFunc(ModuleOp module, StringRef name,
323 TypeRange resultType,
324 ValueRange operands,
325 EmitCInterface emitCInterface) {
326 MLIRContext *context = module.getContext();
327 auto result = SymbolRefAttr::get(ctx: context, value: name);
328 auto func = module.lookupSymbol<func::FuncOp>(name: result.getAttr());
329 if (!func) {
330 OpBuilder moduleBuilder(module.getBodyRegion());
331 func = func::FuncOp::create(
332 builder&: moduleBuilder, location: module.getLoc(), name,
333 type: FunctionType::get(context, inputs: operands.getTypes(), results: resultType));
334 func.setPrivate();
335 if (static_cast<bool>(emitCInterface))
336 func->setDiscardableAttr(name: LLVM::LLVMDialect::getEmitCWrapperAttrName(),
337 value: UnitAttr::get(context));
338 }
339 return result;
340}
341
342func::CallOp mlir::sparse_tensor::createFuncCall(
343 OpBuilder &builder, Location loc, StringRef name, TypeRange resultType,
344 ValueRange operands, EmitCInterface emitCInterface) {
345 auto module = builder.getBlock()->getParentOp()->getParentOfType<ModuleOp>();
346 FlatSymbolRefAttr fn =
347 getFunc(module, name, resultType, operands, emitCInterface);
348 return func::CallOp::create(builder, location: loc, results: resultType, callee: fn, operands);
349}
350
351Type mlir::sparse_tensor::getOpaquePointerType(MLIRContext *ctx) {
352 return LLVM::LLVMPointerType::get(context: ctx);
353}
354
355Type mlir::sparse_tensor::getOpaquePointerType(Builder &builder) {
356 return getOpaquePointerType(ctx: builder.getContext());
357}
358
359Value mlir::sparse_tensor::genAlloca(OpBuilder &builder, Location loc,
360 unsigned sz, Type tp, bool staticShape) {
361 if (staticShape) {
362 auto memTp = MemRefType::get(shape: {sz}, elementType: tp);
363 return memref::AllocaOp::create(builder, location: loc, memrefType: memTp);
364 }
365 return genAlloca(builder, loc, sz: constantIndex(builder, loc, i: sz), tp);
366}
367
368Value mlir::sparse_tensor::genAlloca(OpBuilder &builder, Location loc, Value sz,
369 Type tp) {
370 auto memTp = MemRefType::get(shape: {ShapedType::kDynamic}, elementType: tp);
371 return memref::AllocaOp::create(builder, location: loc, memrefType: memTp, dynamicSizes: ValueRange{sz});
372}
373
374Value mlir::sparse_tensor::genAllocaScalar(OpBuilder &builder, Location loc,
375 Type tp) {
376 return memref::AllocaOp::create(builder, location: loc, memrefType: MemRefType::get(shape: {}, elementType: tp));
377}
378
379Value mlir::sparse_tensor::allocaBuffer(OpBuilder &builder, Location loc,
380 ValueRange values) {
381 const unsigned sz = values.size();
382 assert(sz >= 1);
383 Value buffer = genAlloca(builder, loc, sz, tp: values[0].getType());
384 for (unsigned i = 0; i < sz; i++) {
385 Value idx = constantIndex(builder, loc, i);
386 memref::StoreOp::create(builder, location: loc, valueToStore: values[i], memref: buffer, indices: idx);
387 }
388 return buffer;
389}
390
391Value mlir::sparse_tensor::allocDenseTensor(OpBuilder &builder, Location loc,
392 RankedTensorType tensorTp,
393 ValueRange sizes) {
394 Type elemTp = tensorTp.getElementType();
395 auto shape = tensorTp.getShape();
396 auto memTp = MemRefType::get(shape, elementType: elemTp);
397 SmallVector<Value> dynamicSizes;
398 for (unsigned i = 0, rank = tensorTp.getRank(); i < rank; i++) {
399 if (shape[i] == ShapedType::kDynamic)
400 dynamicSizes.push_back(Elt: sizes[i]);
401 }
402 Value mem = memref::AllocOp::create(builder, location: loc, memrefType: memTp, dynamicSizes);
403 Value zero = constantZero(builder, loc, tp: elemTp);
404 linalg::FillOp::create(builder, location: loc, inputs: ValueRange{zero}, outputs: ValueRange{mem});
405 return mem;
406}
407
408void mlir::sparse_tensor::deallocDenseTensor(OpBuilder &builder, Location loc,
409 Value buffer) {
410 memref::DeallocOp::create(builder, location: loc, memref: buffer);
411}
412
413void mlir::sparse_tensor::sizesFromSrc(OpBuilder &builder,
414 SmallVectorImpl<Value> &sizes,
415 Location loc, Value src) {
416 const Dimension dimRank = getSparseTensorType(val: src).getDimRank();
417 for (Dimension d = 0; d < dimRank; d++)
418 sizes.push_back(Elt: linalg::createOrFoldDimOp(b&: builder, loc, val: src, dim: d));
419}
420
421Operation *mlir::sparse_tensor::getTop(Operation *op) {
422 for (; isa<scf::ForOp, scf::WhileOp, scf::ParallelOp, scf::IfOp>(
423 Val: op->getParentOp());
424 op = op->getParentOp())
425 ;
426 return op;
427}
428
429void sparse_tensor::foreachInSparseConstant(
430 OpBuilder &builder, Location loc, SparseElementsAttr attr, AffineMap order,
431 function_ref<void(ArrayRef<Value>, Value)> callback) {
432 if (!order)
433 order = builder.getMultiDimIdentityMap(rank: attr.getType().getRank());
434
435 auto stt = SparseTensorType(getRankedTensorType(t&: attr));
436 const Dimension dimRank = stt.getDimRank();
437 const auto coordinates = attr.getIndices().getValues<IntegerAttr>();
438 const auto values = attr.getValues().getValues<Attribute>();
439
440 // This is like the `Element<V>` class in the runtime library, but for
441 // MLIR attributes. In the future we may want to move this out into
442 // a proper class definition to help improve code legibility (e.g.,
443 // `first` -> `coords`, `second` -> `value`) as well as being able
444 // to factor out analogues of `ElementLT<V>` for the sort below, etc.
445 using ElementAttr = std::pair<SmallVector<IntegerAttr>, Attribute>;
446
447 // Construct the COO from the SparseElementsAttr.
448 SmallVector<ElementAttr> elems;
449 for (size_t i = 0, nse = values.size(); i < nse; i++) {
450 elems.emplace_back();
451 elems.back().second = values[i];
452 auto &coords = elems.back().first;
453 coords.reserve(N: dimRank);
454 for (Dimension d = 0; d < dimRank; d++)
455 coords.push_back(Elt: coordinates[i * dimRank + d]);
456 }
457
458 // Sorts the sparse element attribute based on coordinates.
459 llvm::sort(C&: elems, Comp: [order](const ElementAttr &lhs, const ElementAttr &rhs) {
460 if (std::addressof(r: lhs) == std::addressof(r: rhs))
461 return false;
462
463 auto lhsCoords = llvm::map_to_vector(
464 C: lhs.first, F: [](IntegerAttr i) { return i.getInt(); });
465 auto rhsCoords = llvm::map_to_vector(
466 C: rhs.first, F: [](IntegerAttr i) { return i.getInt(); });
467
468 SmallVector<int64_t, 4> lhsLvlCrds = order.compose(values: lhsCoords);
469 SmallVector<int64_t, 4> rhsLvlCrds = order.compose(values: rhsCoords);
470 // Sort the element based on the lvl coordinates.
471 for (Level l = 0; l < order.getNumResults(); l++) {
472 if (lhsLvlCrds[l] == rhsLvlCrds[l])
473 continue;
474 return lhsLvlCrds[l] < rhsLvlCrds[l];
475 }
476 llvm_unreachable("no equal coordinate in sparse element attr");
477 });
478
479 SmallVector<Value> cvs;
480 cvs.reserve(N: dimRank);
481 for (size_t i = 0, nse = values.size(); i < nse; i++) {
482 // Remap coordinates.
483 cvs.clear();
484 for (Dimension d = 0; d < dimRank; d++) {
485 auto crd = elems[i].first[d].getInt();
486 cvs.push_back(Elt: arith::ConstantIndexOp::create(builder, location: loc, value: crd));
487 }
488 // Remap value.
489 Value val;
490 if (isa<ComplexType>(Val: attr.getElementType())) {
491 auto valAttr = cast<ArrayAttr>(Val&: elems[i].second);
492 val = complex::ConstantOp::create(builder, location: loc, complex: attr.getElementType(),
493 value: valAttr);
494 } else {
495 auto valAttr = cast<TypedAttr>(Val&: elems[i].second);
496 val = arith::ConstantOp::create(builder, location: loc, value: valAttr);
497 }
498 assert(val);
499 callback(cvs, val);
500 }
501}
502
503SmallVector<Value> sparse_tensor::loadAll(OpBuilder &builder, Location loc,
504 size_t size, Value mem,
505 size_t offsetIdx, Value offsetVal) {
506#ifndef NDEBUG
507 const auto memTp = cast<MemRefType>(mem.getType());
508 assert(memTp.getRank() == 1);
509 const Size memSh = memTp.getDimSize(0);
510 assert(ShapedType::isDynamic(memSh) || memSh >= static_cast<Size>(size));
511 assert(offsetIdx == 0 || offsetIdx < size);
512#endif // NDEBUG
513 SmallVector<Value> vs;
514 vs.reserve(N: size);
515 for (unsigned i = 0; i < size; i++) {
516 Value v = memref::LoadOp::create(builder, location: loc, memref: mem,
517 indices: constantIndex(builder, loc, i));
518 if (i == offsetIdx && offsetVal)
519 v = arith::AddIOp::create(builder, location: loc, lhs: v, rhs: offsetVal);
520 vs.push_back(Elt: v);
521 }
522 return vs;
523}
524
525void sparse_tensor::storeAll(OpBuilder &builder, Location loc, Value mem,
526 ValueRange vs, size_t offsetIdx, Value offsetVal) {
527#ifndef NDEBUG
528 const size_t vsize = vs.size();
529 const auto memTp = cast<MemRefType>(mem.getType());
530 assert(memTp.getRank() == 1);
531 const Size memSh = memTp.getDimSize(0);
532 assert(ShapedType::isDynamic(memSh) || memSh >= static_cast<Size>(vsize));
533 assert(offsetIdx == 0 || offsetIdx < vsize);
534#endif // NDEBUG
535 for (const auto &v : llvm::enumerate(First&: vs)) {
536 const Value w =
537 (offsetIdx == v.index() && offsetVal)
538 ? arith::AddIOp::create(builder, location: loc, lhs: v.value(), rhs: offsetVal)
539 : v.value();
540 memref::StoreOp::create(builder, location: loc, valueToStore: w, memref: mem,
541 indices: constantIndex(builder, loc, i: v.index()));
542 }
543}
544
545TypedValue<BaseMemRefType>
546sparse_tensor::genToMemref(OpBuilder &builder, Location loc, Value tensor) {
547 auto tTp = llvm::cast<TensorType>(Val: tensor.getType());
548 auto mTp = MemRefType::get(shape: tTp.getShape(), elementType: tTp.getElementType());
549 return cast<TypedValue<BaseMemRefType>>(
550 Val: bufferization::ToBufferOp::create(builder, location: loc, buffer: mTp, tensor).getResult());
551}
552
553Value sparse_tensor::createOrFoldSliceOffsetOp(OpBuilder &builder, Location loc,
554 Value tensor, Dimension dim) {
555 auto enc = getSparseTensorEncoding(type: tensor.getType());
556 assert(enc && enc.isSlice());
557 std::optional<unsigned> offset = enc.getStaticDimSliceOffset(dim);
558 if (offset.has_value())
559 return constantIndex(builder, loc, i: *offset);
560 return ToSliceOffsetOp::create(builder, location: loc, slice: tensor, dim: APInt(64, dim));
561}
562
563Value sparse_tensor::createOrFoldSliceStrideOp(OpBuilder &builder, Location loc,
564 Value tensor, Dimension dim) {
565 auto enc = getSparseTensorEncoding(type: tensor.getType());
566 assert(enc && enc.isSlice());
567 std::optional<unsigned> stride = enc.getStaticDimSliceStride(dim);
568 if (stride.has_value())
569 return constantIndex(builder, loc, i: *stride);
570 return ToSliceStrideOp::create(builder, location: loc, slice: tensor, dim: APInt(64, dim));
571}
572
573Value sparse_tensor::genReader(OpBuilder &builder, Location loc,
574 SparseTensorType stt, Value tensor,
575 /*out*/ SmallVectorImpl<Value> &dimSizesValues,
576 /*out*/ Value &dimSizesBuffer) {
577 // Construct the dimension **shapes** buffer. The buffer contains the static
578 // size per dimension, or otherwise a zero for a dynamic size.
579 Dimension dimRank = stt.getDimRank();
580 dimSizesValues.clear();
581 dimSizesValues.reserve(N: dimRank);
582 for (const Size sz : stt.getDimShape()) {
583 const auto s = ShapedType::isDynamic(dValue: sz) ? 0 : sz;
584 dimSizesValues.push_back(Elt: constantIndex(builder, loc, i: s));
585 }
586 Value dimShapesBuffer = allocaBuffer(builder, loc, values: dimSizesValues);
587 // Create the `CheckedSparseTensorReader`. This reader performs a
588 // consistency check on the static sizes, but accepts any size
589 // of each dimension with a dynamic size.
590 Type opaqueTp = getOpaquePointerType(builder);
591 Type eltTp = stt.getElementType();
592 Value valTp = constantPrimaryTypeEncoding(builder, loc, elemTp: eltTp);
593 Value reader =
594 createFuncCall(builder, loc, name: "createCheckedSparseTensorReader", resultType: opaqueTp,
595 operands: {tensor, dimShapesBuffer, valTp}, emitCInterface: EmitCInterface::On)
596 .getResult(i: 0);
597 // For static shapes, the shape buffer can be used right away. For dynamic
598 // shapes, use the information from the reader to construct a buffer that
599 // supplies the actual size for each dynamic dimension.
600 dimSizesBuffer = dimShapesBuffer;
601 if (stt.hasDynamicDimShape()) {
602 Type indexTp = builder.getIndexType();
603 auto memTp = MemRefType::get(shape: {ShapedType::kDynamic}, elementType: indexTp);
604 dimSizesBuffer =
605 createFuncCall(builder, loc, name: "getSparseTensorReaderDimSizes", resultType: memTp,
606 operands: reader, emitCInterface: EmitCInterface::On)
607 .getResult(i: 0);
608 // Also convert the dim shapes values into dim sizes values, just in case
609 // subsequent clients need the values (DCE will remove unused).
610 for (Dimension d = 0; d < dimRank; d++) {
611 if (stt.isDynamicDim(d))
612 dimSizesValues[d] = memref::LoadOp::create(
613 builder, location: loc, memref: dimSizesBuffer, indices: constantIndex(builder, loc, i: d));
614 }
615 }
616 return reader;
617}
618
619Value sparse_tensor::genMapBuffers(
620 OpBuilder &builder, Location loc, SparseTensorType stt,
621 ArrayRef<Value> dimSizesValues, Value dimSizesBuffer,
622 /*out*/ SmallVectorImpl<Value> &lvlSizesValues,
623 /*out*/ Value &dim2lvlBuffer,
624 /*out*/ Value &lvl2dimBuffer) {
625 const Dimension dimRank = stt.getDimRank();
626 const Level lvlRank = stt.getLvlRank();
627 lvlSizesValues.clear();
628 lvlSizesValues.reserve(N: lvlRank);
629 // For an identity mapping, the dim2lvl and lvl2dim mappings are
630 // identical as are dimSizes and lvlSizes, so buffers are reused
631 // as much as possible.
632 if (stt.isIdentity()) {
633 assert(dimRank == lvlRank);
634 SmallVector<Value> iotaValues;
635 iotaValues.reserve(N: lvlRank);
636 for (Level l = 0; l < lvlRank; l++) {
637 iotaValues.push_back(Elt: constantIndex(builder, loc, i: l));
638 lvlSizesValues.push_back(Elt: dimSizesValues[l]);
639 }
640 dim2lvlBuffer = lvl2dimBuffer = allocaBuffer(builder, loc, values: iotaValues);
641 return dimSizesBuffer; // now lvlSizesBuffer
642 }
643 // Otherwise, some code needs to be generated to set up the buffers.
644 // This code deals with permutations as well as non-permutations that
645 // arise from rank changing blocking.
646 const auto dimToLvl = stt.getDimToLvl();
647 const auto lvlToDim = stt.getLvlToDim();
648 SmallVector<Value> dim2lvlValues(lvlRank); // for each lvl, expr in dim vars
649 SmallVector<Value> lvl2dimValues(dimRank); // for each dim, expr in lvl vars
650 // Generate dim2lvl.
651 assert(lvlRank == dimToLvl.getNumResults());
652 for (Level l = 0; l < lvlRank; l++) {
653 AffineExpr exp = dimToLvl.getResult(idx: l);
654 // We expect:
655 // (1) l = d
656 // (2) l = d / c
657 // (3) l = d % c
658 Dimension d = 0;
659 uint64_t cf = 0, cm = 0;
660 switch (exp.getKind()) {
661 case AffineExprKind::DimId: {
662 d = cast<AffineDimExpr>(Val&: exp).getPosition();
663 break;
664 }
665 case AffineExprKind::FloorDiv: {
666 auto floor = cast<AffineBinaryOpExpr>(Val&: exp);
667 d = cast<AffineDimExpr>(Val: floor.getLHS()).getPosition();
668 cf = cast<AffineConstantExpr>(Val: floor.getRHS()).getValue();
669 break;
670 }
671 case AffineExprKind::Mod: {
672 auto mod = cast<AffineBinaryOpExpr>(Val&: exp);
673 d = cast<AffineDimExpr>(Val: mod.getLHS()).getPosition();
674 cm = cast<AffineConstantExpr>(Val: mod.getRHS()).getValue();
675 break;
676 }
677 default:
678 llvm::report_fatal_error(reason: "unsupported dim2lvl in sparse tensor type");
679 }
680 dim2lvlValues[l] = constantIndex(builder, loc, i: encodeDim(i: d, cf, cm));
681 // Compute the level sizes.
682 // (1) l = d : size(d)
683 // (2) l = d / c : size(d) / c
684 // (3) l = d % c : c
685 Value lvlSz;
686 if (cm == 0) {
687 lvlSz = dimSizesValues[d];
688 if (cf != 0)
689 lvlSz = arith::DivUIOp::create(builder, location: loc, lhs: lvlSz,
690 rhs: constantIndex(builder, loc, i: cf));
691 } else {
692 lvlSz = constantIndex(builder, loc, i: cm);
693 }
694 lvlSizesValues.push_back(Elt: lvlSz);
695 }
696 // Generate lvl2dim.
697 assert(dimRank == lvlToDim.getNumResults());
698 for (Dimension d = 0; d < dimRank; d++) {
699 AffineExpr exp = lvlToDim.getResult(idx: d);
700 // We expect:
701 // (1) d = l
702 // (2) d = l' * c + l
703 Level l = 0, ll = 0;
704 uint64_t c = 0;
705 switch (exp.getKind()) {
706 case AffineExprKind::DimId: {
707 l = cast<AffineDimExpr>(Val&: exp).getPosition();
708 break;
709 }
710 case AffineExprKind::Add: {
711 // Always mul on lhs, symbol/constant on rhs.
712 auto add = cast<AffineBinaryOpExpr>(Val&: exp);
713 assert(add.getLHS().getKind() == AffineExprKind::Mul);
714 auto mul = cast<AffineBinaryOpExpr>(Val: add.getLHS());
715 ll = cast<AffineDimExpr>(Val: mul.getLHS()).getPosition();
716 c = cast<AffineConstantExpr>(Val: mul.getRHS()).getValue();
717 l = cast<AffineDimExpr>(Val: add.getRHS()).getPosition();
718 break;
719 }
720 default:
721 llvm::report_fatal_error(reason: "unsupported lvl2dim in sparse tensor type");
722 }
723 lvl2dimValues[d] = constantIndex(builder, loc, i: encodeLvl(i: l, c, ii: ll));
724 }
725 // Return buffers.
726 dim2lvlBuffer = allocaBuffer(builder, loc, values: dim2lvlValues);
727 lvl2dimBuffer = allocaBuffer(builder, loc, values: lvl2dimValues);
728 return allocaBuffer(builder, loc, values: lvlSizesValues); // lvlSizesBuffer
729}
730