1//===- SparseTensorConversion.cpp - Sparse tensor primitives conversion ---===//
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// A pass that converts sparse tensor primitives into calls into a runtime
10// support library. Sparse tensor types are converted into opaque pointers
11// to the underlying sparse storage schemes. The use of opaque pointers
12// together with runtime support library keeps the conversion relatively
13// simple, but at the expense of IR opacity, which obscures opportunities
14// for subsequent optimization of the IR. An alternative is provided by
15// the SparseTensorCodegen pass.
16//
17//===----------------------------------------------------------------------===//
18
19#include "Utils/CodegenUtils.h"
20#include "mlir/Dialect/LLVMIR/LLVMConstantOps.h"
21#include "mlir/Dialect/LLVMIR/LLVMConversionOps.h"
22#include "mlir/Dialect/LLVMIR/LLVMTypes.h"
23
24#include "mlir/Dialect/Bufferization/IR/BufferizableOpInterface.h"
25#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
26#include "mlir/Dialect/Linalg/Utils/Utils.h"
27#include "mlir/Dialect/MemRef/IR/MemRef.h"
28#include "mlir/Dialect/SCF/IR/SCF.h"
29#include "mlir/Dialect/SparseTensor/IR/Enums.h"
30#include "mlir/Dialect/SparseTensor/IR/SparseTensor.h"
31#include "mlir/Dialect/SparseTensor/IR/SparseTensorType.h"
32#include "mlir/Dialect/SparseTensor/Transforms/Passes.h"
33#include "mlir/Dialect/Tensor/IR/Tensor.h"
34#include "mlir/Transforms/DialectConversion.h"
35
36using namespace mlir;
37using namespace mlir::sparse_tensor;
38
39namespace {
40
41//===----------------------------------------------------------------------===//
42// Helper methods.
43//===----------------------------------------------------------------------===//
44
45/// Maps each sparse tensor type to an opaque pointer.
46static std::optional<Type> convertSparseTensorTypes(Type type) {
47 if (getSparseTensorEncoding(type) != nullptr)
48 return LLVM::LLVMPointerType::get(context: type.getContext());
49 return std::nullopt;
50}
51
52/// Generates call to lookup a level-size. N.B., this only generates
53/// the raw function call, and therefore (intentionally) does not perform
54/// any dim<->lvl conversion or other logic.
55static Value genLvlSizeCall(OpBuilder &builder, Location loc, Value tensor,
56 uint64_t lvl) {
57 StringRef name = "sparseLvlSize";
58 SmallVector<Value, 2> params{tensor, constantIndex(builder, loc, i: lvl)};
59 Type iTp = builder.getIndexType();
60 return createFuncCall(builder, loc, name, resultType: iTp, operands: params, emitCInterface: EmitCInterface::Off)
61 .getResult(i: 0);
62}
63
64/// Generates call to lookup a dimension-size. N.B., this only generates
65/// the raw function call, and therefore (intentionally) does not perform
66/// any dim<->lvl conversion or other logic.
67static Value genDimSizeCall(OpBuilder &builder, Location loc, Value tensor,
68 uint64_t dim) {
69 StringRef name = "sparseDimSize";
70 SmallVector<Value, 2> params{tensor, constantIndex(builder, loc, i: dim)};
71 Type iTp = builder.getIndexType();
72 return createFuncCall(builder, loc, name, resultType: iTp, operands: params, emitCInterface: EmitCInterface::Off)
73 .getResult(i: 0);
74}
75
76/// Looks up a level-size by returning a statically-computed constant
77/// (when possible), or by calling `genLvlSizeCall` (when dynamic).
78static Value createOrFoldLvlCall(OpBuilder &builder, Location loc,
79 SparseTensorType stt, Value tensor,
80 Level lvl) {
81 // Only sparse tensors have "levels" to query.
82 assert(stt.hasEncoding());
83 // TODO: The following implementation only handles permutations;
84 // we'll need to generalize this to handle arbitrary AffineExpr.
85 //
86 // There's no need to assert `isPermutation` here: because
87 // `getDimPosition` checks that the expr isa `AffineDimExpr`,
88 // which is all we care about (for supporting permutations).
89 const Dimension dim =
90 stt.isIdentity() ? lvl : stt.getDimToLvl().getDimPosition(idx: lvl);
91 const Size sz = stt.getDynamicDimSize(d: dim);
92 if (ShapedType::isStatic(dValue: sz))
93 return constantIndex(builder, loc, i: sz);
94 // If we cannot statically compute the size from the shape, then we
95 // must dynamically query it. (In principle we could also dynamically
96 // compute it, but since we already did so to construct the `tensor`
97 // in the first place, we might as well query rather than recompute.)
98 return genLvlSizeCall(builder, loc, tensor, lvl);
99}
100
101/// Looks up a dimension-size by returning a constant from the shape
102/// (for static sizes), or by calling `genDimSizeCall` (for dynamic sizes
103/// of sparse tensors) or `linalg::createOrFoldDimOp` (for dynamic sizes
104/// of dense tensors).
105static Value createOrFoldDimCall(OpBuilder &builder, Location loc,
106 SparseTensorType stt, Value tensor,
107 Dimension dim) {
108 const Size sz = stt.getDynamicDimSize(d: dim);
109 if (ShapedType::isStatic(dValue: sz))
110 return constantIndex(builder, loc, i: sz);
111 if (stt.hasEncoding())
112 return genDimSizeCall(builder, loc, tensor, dim);
113 return linalg::createOrFoldDimOp(b&: builder, loc, val: tensor, dim);
114}
115
116/// Populates the array with the dimension-sizes of the given tensor.
117static void fillDimSizes(OpBuilder &builder, Location loc, SparseTensorType stt,
118 Value tensor, SmallVectorImpl<Value> &out) {
119 const Dimension dimRank = stt.getDimRank();
120 out.clear();
121 out.reserve(N: dimRank);
122 for (Dimension d = 0; d < dimRank; d++)
123 out.push_back(Elt: createOrFoldDimCall(builder, loc, stt, tensor, dim: d));
124}
125
126/// Returns an array with the dimension-sizes of the given tensor.
127/// If the *tensor* parameters is null, the tensor type is assumed to have a
128/// static shape.
129static SmallVector<Value> getDimSizes(OpBuilder &builder, Location loc,
130 SparseTensorType stt,
131 Value tensor = Value()) {
132 SmallVector<Value> out;
133 fillDimSizes(builder, loc, stt, tensor, out);
134 return out;
135}
136
137/// Generates an uninitialized buffer of the given size and type,
138/// but returns it as type `memref<? x $tp>` (rather than as type
139/// `memref<$sz x $tp>`). Unlike temporary buffers on the stack,
140/// this buffer must be explicitly deallocated by client.
141static Value genAlloc(RewriterBase &rewriter, Location loc, Value sz, Type tp) {
142 auto memTp = MemRefType::get(shape: {ShapedType::kDynamic}, elementType: tp);
143 return memref::AllocOp::create(builder&: rewriter, location: loc, memrefType: memTp, dynamicSizes: ValueRange{sz});
144}
145
146/// Generates a temporary buffer for the level-types of the given encoding.
147static Value genLvlTypesBuffer(OpBuilder &builder, Location loc,
148 SparseTensorType stt) {
149 SmallVector<Value> lvlTypes;
150 lvlTypes.reserve(N: stt.getLvlRank());
151 for (const auto lt : stt.getEncoding().getLvlTypes())
152 lvlTypes.push_back(Elt: constantLevelTypeEncoding(builder, loc, lt));
153 return allocaBuffer(builder, loc, values: lvlTypes);
154}
155
156/// Extracts the bare (aligned) pointers that point to the tensor.
157static Value extractBarePtrFromTensor(OpBuilder &builder, Location loc,
158 Value tensor) {
159 auto buf = genToMemref(builder, loc, tensor);
160 return memref::ExtractAlignedPointerAsIndexOp::create(builder, location: loc, source: buf);
161}
162
163/// Generates a temporary buffer for the level-types of the given encoding.
164static Value genLvlPtrsBuffers(OpBuilder &builder, Location loc,
165 ValueRange lvlTensors, Value valTensor) {
166 SmallVector<Value> lvlBarePtrs;
167 lvlBarePtrs.reserve(N: lvlTensors.size() + 1);
168 // Passing in lvl buffer pointers.
169 for (const auto lvl : lvlTensors)
170 lvlBarePtrs.push_back(Elt: extractBarePtrFromTensor(builder, loc, tensor: lvl));
171
172 // Passing in value buffer pointers.
173 lvlBarePtrs.push_back(Elt: extractBarePtrFromTensor(builder, loc, tensor: valTensor));
174 Value idxPtr = memref::ExtractAlignedPointerAsIndexOp::create(
175 builder, location: loc, source: allocaBuffer(builder, loc, values: lvlBarePtrs));
176 Value idxCast =
177 arith::IndexCastOp::create(builder, location: loc, out: builder.getI64Type(), in: idxPtr);
178 return LLVM::IntToPtrOp::create(builder, location: loc, resultType: getOpaquePointerType(builder),
179 operands: idxCast);
180}
181
182/// This class abstracts over the API of `_mlir_ciface_newSparseTensor`:
183/// the "swiss army knife" method of the sparse runtime support library
184/// for materializing sparse tensors into the computation. This abstraction
185/// reduces the need for modifications when the API changes.
186class NewCallParams final {
187public:
188 /// Allocates the `ValueRange` for the `func::CallOp` parameters.
189 NewCallParams(OpBuilder &builder, Location loc)
190 : builder(builder), loc(loc), pTp(getOpaquePointerType(builder)) {}
191
192 /// Initializes all static parameters (i.e., those which indicate
193 /// type-level information such as the encoding and sizes), generating
194 /// MLIR buffers as needed, and returning `this` for method chaining.
195 NewCallParams &genBuffers(SparseTensorType stt,
196 ArrayRef<Value> dimSizesValues,
197 Value dimSizesBuffer = Value()) {
198 assert(dimSizesValues.size() == static_cast<size_t>(stt.getDimRank()));
199 // Sparsity annotations.
200 params[kParamLvlTypes] = genLvlTypesBuffer(builder, loc, stt);
201 // Construct dimSizes, lvlSizes, dim2lvl, and lvl2dim buffers.
202 params[kParamDimSizes] = dimSizesBuffer
203 ? dimSizesBuffer
204 : allocaBuffer(builder, loc, values: dimSizesValues);
205 SmallVector<Value> lvlSizesValues; // unused
206 params[kParamLvlSizes] = genMapBuffers(
207 builder, loc, stt, dimSizesValues, dimSizesBuffer: params[kParamDimSizes],
208 lvlSizesValues, dim2lvlBuffer&: params[kParamDim2Lvl], lvl2dimBuffer&: params[kParamLvl2Dim]);
209 // Secondary and primary types encoding.
210 const auto enc = stt.getEncoding();
211 params[kParamPosTp] = constantPosTypeEncoding(builder, loc, enc);
212 params[kParamCrdTp] = constantCrdTypeEncoding(builder, loc, enc);
213 params[kParamValTp] =
214 constantPrimaryTypeEncoding(builder, loc, elemTp: stt.getElementType());
215 // Return `this` for method chaining.
216 return *this;
217 }
218
219 /// Checks whether all the static parameters have been initialized.
220 bool isInitialized() const {
221 for (unsigned i = 0; i < kNumStaticParams; ++i)
222 if (!params[i])
223 return false;
224 return true;
225 }
226
227 /// Generates a function call, with the current static parameters
228 /// and the given dynamic arguments.
229 Value genNewCall(Action action, Value ptr = Value()) {
230 assert(isInitialized() && "Must initialize before genNewCall");
231 StringRef name = "newSparseTensor";
232 params[kParamAction] = constantAction(builder, loc, action);
233 params[kParamPtr] = ptr ? ptr : LLVM::ZeroOp::create(builder, location: loc, res: pTp);
234 return createFuncCall(builder, loc, name, resultType: pTp, operands: params, emitCInterface: EmitCInterface::On)
235 .getResult(i: 0);
236 }
237
238private:
239 static constexpr unsigned kNumStaticParams = 8;
240 static constexpr unsigned kNumDynamicParams = 2;
241 static constexpr unsigned kNumParams = kNumStaticParams + kNumDynamicParams;
242 static constexpr unsigned kParamDimSizes = 0;
243 static constexpr unsigned kParamLvlSizes = 1;
244 static constexpr unsigned kParamLvlTypes = 2;
245 static constexpr unsigned kParamDim2Lvl = 3;
246 static constexpr unsigned kParamLvl2Dim = 4;
247 static constexpr unsigned kParamPosTp = 5;
248 static constexpr unsigned kParamCrdTp = 6;
249 static constexpr unsigned kParamValTp = 7;
250 static constexpr unsigned kParamAction = 8;
251 static constexpr unsigned kParamPtr = 9;
252
253 OpBuilder &builder;
254 Location loc;
255 Type pTp;
256 Value params[kNumParams];
257};
258
259/// Generates a call to obtain the values array.
260static Value genValuesCall(OpBuilder &builder, Location loc,
261 SparseTensorType stt, Value ptr) {
262 auto eltTp = stt.getElementType();
263 auto resTp = MemRefType::get(shape: {ShapedType::kDynamic}, elementType: eltTp);
264 SmallString<15> name{"sparseValues", primaryTypeFunctionSuffix(elemTp: eltTp)};
265 return createFuncCall(builder, loc, name, resultType: resTp, operands: {ptr}, emitCInterface: EmitCInterface::On)
266 .getResult(i: 0);
267}
268
269/// Generates a call to obtain the positions array.
270static Value genPositionsCall(OpBuilder &builder, Location loc,
271 SparseTensorType stt, Value ptr, Level l) {
272 Type posTp = stt.getPosType();
273 auto resTp = MemRefType::get(shape: {ShapedType::kDynamic}, elementType: posTp);
274 Value lvl = constantIndex(builder, loc, i: l);
275 SmallString<17> name{"sparsePositions", overheadTypeFunctionSuffix(overheadTp: posTp)};
276 return createFuncCall(builder, loc, name, resultType: resTp, operands: {ptr, lvl},
277 emitCInterface: EmitCInterface::On)
278 .getResult(i: 0);
279}
280
281/// Generates a call to obtain the coordinates array.
282static Value genCoordinatesCall(OpBuilder &builder, Location loc,
283 SparseTensorType stt, Value ptr, Level l) {
284 Type crdTp = stt.getCrdType();
285 auto resTp = MemRefType::get(shape: {ShapedType::kDynamic}, elementType: crdTp);
286 Value lvl = constantIndex(builder, loc, i: l);
287 SmallString<19> name{"sparseCoordinates", overheadTypeFunctionSuffix(overheadTp: crdTp)};
288 return createFuncCall(builder, loc, name, resultType: resTp, operands: {ptr, lvl},
289 emitCInterface: EmitCInterface::On)
290 .getResult(i: 0);
291}
292
293/// Generates a call to obtain the coordinates array (AoS view).
294static Value genCoordinatesBufferCall(OpBuilder &builder, Location loc,
295 SparseTensorType stt, Value ptr,
296 Level l) {
297 Type crdTp = stt.getCrdType();
298 auto resTp = MemRefType::get(shape: {ShapedType::kDynamic}, elementType: crdTp);
299 Value lvl = constantIndex(builder, loc, i: l);
300 SmallString<25> name{"sparseCoordinatesBuffer",
301 overheadTypeFunctionSuffix(overheadTp: crdTp)};
302 return createFuncCall(builder, loc, name, resultType: resTp, operands: {ptr, lvl},
303 emitCInterface: EmitCInterface::On)
304 .getResult(i: 0);
305}
306
307//===----------------------------------------------------------------------===//
308// Conversion rules.
309//===----------------------------------------------------------------------===//
310
311/// Sparse conversion rule for returns.
312class SparseReturnConverter : public OpConversionPattern<func::ReturnOp> {
313public:
314 using Base::Base;
315 LogicalResult
316 matchAndRewrite(func::ReturnOp op, OpAdaptor adaptor,
317 ConversionPatternRewriter &rewriter) const override {
318 rewriter.replaceOpWithNewOp<func::ReturnOp>(op, args: adaptor.getOperands());
319 return success();
320 }
321};
322
323/// Sparse conversion rule for accessing level-sizes.
324class SparseTensorLvlOpConverter : public OpConversionPattern<LvlOp> {
325public:
326 using Base::Base;
327 LogicalResult
328 matchAndRewrite(LvlOp op, OpAdaptor adaptor,
329 ConversionPatternRewriter &rewriter) const override {
330 const auto stt = getSparseTensorType(val: op.getSource());
331 // Only rewrite sparse DimOp.
332 if (!stt.hasEncoding())
333 return failure();
334
335 // Only rewrite DimOp with constant index.
336 std::optional<int64_t> lvl = op.getConstantLvlIndex();
337
338 if (!lvl)
339 return failure();
340
341 // By now, if the level size is constant, the operation should have already
342 // been folded by LvlOp's folder, so we generate the call unconditionally.
343 Value src = adaptor.getOperands()[0];
344 rewriter.replaceOp(op, newValues: genLvlSizeCall(builder&: rewriter, loc: op.getLoc(), tensor: src, lvl: *lvl));
345 return success();
346 }
347};
348
349/// Sparse conversion rule for trivial tensor casts.
350class SparseCastConverter : public OpConversionPattern<tensor::CastOp> {
351public:
352 using Base::Base;
353 LogicalResult
354 matchAndRewrite(tensor::CastOp op, OpAdaptor adaptor,
355 ConversionPatternRewriter &rewriter) const override {
356 // Only rewrite identically annotated source/dest.
357 auto encDst = getSparseTensorEncoding(type: op.getType());
358 auto encSrc = getSparseTensorEncoding(type: op.getSource().getType());
359 if (!encDst || encDst != encSrc)
360 return failure();
361 rewriter.replaceOp(op, newValues: adaptor.getOperands());
362 return success();
363 }
364};
365
366class SparseReMapConverter : public OpConversionPattern<ReinterpretMapOp> {
367public:
368 using Base::Base;
369 LogicalResult
370 matchAndRewrite(ReinterpretMapOp op, OpAdaptor adaptor,
371 ConversionPatternRewriter &rewriter) const override {
372 // Simply fold the operation.
373 rewriter.replaceOp(op, newValues: adaptor.getSource());
374 return success();
375 }
376};
377
378/// Sparse conversion rule for the new operator.
379class SparseTensorNewConverter : public OpConversionPattern<NewOp> {
380public:
381 using Base::Base;
382 LogicalResult
383 matchAndRewrite(NewOp op, OpAdaptor adaptor,
384 ConversionPatternRewriter &rewriter) const override {
385 Location loc = op.getLoc();
386 const auto stt = getSparseTensorType(val: op);
387 if (!stt.hasEncoding())
388 return failure();
389 // Construct the `reader` opening method calls.
390 SmallVector<Value> dimSizesValues;
391 Value dimSizesBuffer;
392 Value reader = genReader(builder&: rewriter, loc, stt, tensor: adaptor.getOperands()[0],
393 dimSizesValues, dimSizesBuffer);
394 // Use the `reader` to parse the file.
395 Value tensor = NewCallParams(rewriter, loc)
396 .genBuffers(stt, dimSizesValues, dimSizesBuffer)
397 .genNewCall(action: Action::kFromReader, ptr: reader);
398 // Free the memory for `reader`.
399 createFuncCall(builder&: rewriter, loc, name: "delSparseTensorReader", resultType: {}, operands: {reader},
400 emitCInterface: EmitCInterface::Off);
401 rewriter.replaceOp(op, newValues: tensor);
402 return success();
403 }
404};
405
406/// Sparse conversion rule for the alloc operator.
407/// TODO(springerm): remove when bufferization.alloc_tensor is gone
408class SparseTensorAllocConverter
409 : public OpConversionPattern<bufferization::AllocTensorOp> {
410public:
411 using Base::Base;
412 LogicalResult
413 matchAndRewrite(bufferization::AllocTensorOp op, OpAdaptor adaptor,
414 ConversionPatternRewriter &rewriter) const override {
415 const auto stt = getSparseTensorType(val: op);
416 if (!stt.hasEncoding())
417 return failure();
418 if (op.getCopy())
419 return rewriter.notifyMatchFailure(arg&: op, msg: "alloc copy not implemented");
420 // Gather all dimension sizes as SSA values.
421 Location loc = op.getLoc();
422 const Dimension dimRank = stt.getDimRank();
423 SmallVector<Value> dimSizesValues;
424 dimSizesValues.reserve(N: dimRank);
425 unsigned operandCtr = 0;
426 for (Dimension d = 0; d < dimRank; d++) {
427 dimSizesValues.push_back(
428 Elt: stt.isDynamicDim(d)
429 ? adaptor.getOperands()[operandCtr++]
430 : constantIndex(builder&: rewriter, loc, i: op.getStaticSize(idx: d)));
431 }
432 // Generate the call to construct empty tensor. The sizes are
433 // explicitly defined by the arguments to the alloc operator.
434 rewriter.replaceOp(op, newValues: NewCallParams(rewriter, loc)
435 .genBuffers(stt, dimSizesValues)
436 .genNewCall(action: Action::kEmpty));
437 return success();
438 }
439};
440
441/// Sparse conversion rule for the empty tensor.
442class SparseTensorEmptyConverter : public OpConversionPattern<tensor::EmptyOp> {
443public:
444 using Base::Base;
445 LogicalResult
446 matchAndRewrite(tensor::EmptyOp op, OpAdaptor adaptor,
447 ConversionPatternRewriter &rewriter) const override {
448 Location loc = op.getLoc();
449 const auto stt = getSparseTensorType(val: op);
450 if (!stt.hasEncoding())
451 return failure();
452 // Gather all dimension sizes as SSA values.
453 const Dimension dimRank = stt.getDimRank();
454 SmallVector<Value> dimSizesValues;
455 dimSizesValues.reserve(N: dimRank);
456 auto shape = op.getType().getShape();
457 unsigned operandCtr = 0;
458 for (Dimension d = 0; d < dimRank; d++) {
459 dimSizesValues.push_back(Elt: stt.isDynamicDim(d)
460 ? adaptor.getOperands()[operandCtr++]
461 : constantIndex(builder&: rewriter, loc, i: shape[d]));
462 }
463 // Generate the call to construct empty tensor. The sizes are
464 // explicitly defined by the arguments to the alloc operator.
465 rewriter.replaceOp(op, newValues: NewCallParams(rewriter, loc)
466 .genBuffers(stt, dimSizesValues)
467 .genNewCall(action: Action::kEmpty));
468 return success();
469 }
470};
471
472/// Sparse conversion rule for the convert operator.
473class SparseTensorReorderCOOConverter
474 : public OpConversionPattern<ReorderCOOOp> {
475public:
476 using Base::Base;
477
478 LogicalResult
479 matchAndRewrite(ReorderCOOOp op, OpAdaptor adaptor,
480 ConversionPatternRewriter &rewriter) const override {
481 const Location loc = op->getLoc();
482 const auto srcTp = getSparseTensorType(val: op.getInputCoo());
483 const auto dstTp = getSparseTensorType(val: op);
484
485 const Value src = adaptor.getInputCoo();
486
487 NewCallParams params(rewriter, loc);
488 SmallVector<Value> dimSizesValues = getDimSizes(builder&: rewriter, loc, stt: srcTp, tensor: src);
489 rewriter.replaceOp(op, newValues: params.genBuffers(stt: dstTp, dimSizesValues)
490 .genNewCall(action: Action::kSortCOOInPlace, ptr: src));
491
492 return success();
493 }
494};
495
496/// Sparse conversion rule for the dealloc operator.
497class SparseTensorDeallocConverter
498 : public OpConversionPattern<bufferization::DeallocTensorOp> {
499public:
500 using Base::Base;
501 LogicalResult
502 matchAndRewrite(bufferization::DeallocTensorOp op, OpAdaptor adaptor,
503 ConversionPatternRewriter &rewriter) const override {
504 if (!getSparseTensorType(val: op.getTensor()).hasEncoding())
505 return failure();
506 StringRef name = "delSparseTensor";
507 createFuncCall(builder&: rewriter, loc: op->getLoc(), name, resultType: {}, operands: adaptor.getOperands(),
508 emitCInterface: EmitCInterface::Off);
509 rewriter.eraseOp(op);
510 return success();
511 }
512};
513
514/// Sparse conversion rule for position accesses.
515class SparseTensorToPositionsConverter
516 : public OpConversionPattern<ToPositionsOp> {
517public:
518 using Base::Base;
519 LogicalResult
520 matchAndRewrite(ToPositionsOp op, OpAdaptor adaptor,
521 ConversionPatternRewriter &rewriter) const override {
522 auto stt = getSparseTensorType(val: op.getTensor());
523 auto poss = genPositionsCall(builder&: rewriter, loc: op.getLoc(), stt,
524 ptr: adaptor.getTensor(), l: op.getLevel());
525 rewriter.replaceOp(op, newValues: poss);
526 return success();
527 }
528};
529
530/// Sparse conversion rule for coordinate accesses.
531class SparseTensorToCoordinatesConverter
532 : public OpConversionPattern<ToCoordinatesOp> {
533public:
534 using Base::Base;
535 LogicalResult
536 matchAndRewrite(ToCoordinatesOp op, OpAdaptor adaptor,
537 ConversionPatternRewriter &rewriter) const override {
538 const Location loc = op.getLoc();
539 auto stt = getSparseTensorType(val: op.getTensor());
540 auto crds = genCoordinatesCall(builder&: rewriter, loc, stt, ptr: adaptor.getTensor(),
541 l: op.getLevel());
542 // Cast the MemRef type to the type expected by the users, though these
543 // two types should be compatible at runtime.
544 if (op.getType() != crds.getType())
545 crds = memref::CastOp::create(builder&: rewriter, location: loc, dest: op.getType(), source: crds);
546 rewriter.replaceOp(op, newValues: crds);
547 return success();
548 }
549};
550
551/// Sparse conversion rule for coordinate accesses (AoS style).
552class SparseToCoordinatesBufferConverter
553 : public OpConversionPattern<ToCoordinatesBufferOp> {
554public:
555 using Base::Base;
556 LogicalResult
557 matchAndRewrite(ToCoordinatesBufferOp op, OpAdaptor adaptor,
558 ConversionPatternRewriter &rewriter) const override {
559 const Location loc = op.getLoc();
560 auto stt = getSparseTensorType(val: op.getTensor());
561 auto crds = genCoordinatesBufferCall(
562 builder&: rewriter, loc, stt, ptr: adaptor.getTensor(), l: stt.getAoSCOOStart());
563 // Cast the MemRef type to the type expected by the users, though these
564 // two types should be compatible at runtime.
565 if (op.getType() != crds.getType())
566 crds = memref::CastOp::create(builder&: rewriter, location: loc, dest: op.getType(), source: crds);
567 rewriter.replaceOp(op, newValues: crds);
568 return success();
569 }
570};
571
572/// Sparse conversion rule for value accesses.
573class SparseTensorToValuesConverter : public OpConversionPattern<ToValuesOp> {
574public:
575 using Base::Base;
576 LogicalResult
577 matchAndRewrite(ToValuesOp op, OpAdaptor adaptor,
578 ConversionPatternRewriter &rewriter) const override {
579 auto stt = getSparseTensorType(val: op.getTensor());
580 auto vals = genValuesCall(builder&: rewriter, loc: op.getLoc(), stt, ptr: adaptor.getTensor());
581 rewriter.replaceOp(op, newValues: vals);
582 return success();
583 }
584};
585
586/// Sparse conversion rule for number of entries operator.
587class SparseNumberOfEntriesConverter
588 : public OpConversionPattern<NumberOfEntriesOp> {
589public:
590 using Base::Base;
591 LogicalResult
592 matchAndRewrite(NumberOfEntriesOp op, OpAdaptor adaptor,
593 ConversionPatternRewriter &rewriter) const override {
594 // Query values array size for the actually stored values size.
595 auto stt = getSparseTensorType(val: op.getTensor());
596 auto vals = genValuesCall(builder&: rewriter, loc: op.getLoc(), stt, ptr: adaptor.getTensor());
597 auto zero = constantIndex(builder&: rewriter, loc: op.getLoc(), i: 0);
598 rewriter.replaceOpWithNewOp<memref::DimOp>(op, args&: vals, args&: zero);
599 return success();
600 }
601};
602
603/// Sparse conversion rule for tensor rematerialization.
604class SparseTensorLoadConverter : public OpConversionPattern<LoadOp> {
605public:
606 using Base::Base;
607 LogicalResult
608 matchAndRewrite(LoadOp op, OpAdaptor adaptor,
609 ConversionPatternRewriter &rewriter) const override {
610 if (op.getHasInserts()) {
611 // Finalize any pending insertions.
612 StringRef name = "endLexInsert";
613 createFuncCall(builder&: rewriter, loc: op->getLoc(), name, resultType: {}, operands: adaptor.getOperands(),
614 emitCInterface: EmitCInterface::Off);
615 }
616 rewriter.replaceOp(op, newValues: adaptor.getOperands());
617 return success();
618 }
619};
620
621/// Sparse conversion rule for the insertion operator.
622class SparseTensorInsertConverter
623 : public OpConversionPattern<tensor::InsertOp> {
624public:
625 using Base::Base;
626 LogicalResult
627 matchAndRewrite(tensor::InsertOp op, OpAdaptor adaptor,
628 ConversionPatternRewriter &rewriter) const override {
629 // Note that the current regime only allows for strict lexicographic
630 // coordinate order. All values are passed by reference through stack
631 // allocated memrefs.
632 Location loc = op->getLoc();
633 const auto stt = getSparseTensorType(val: op.getDest());
634
635 // Dense tensor insertion.
636 if (!stt.hasEncoding())
637 return failure();
638
639 assert(stt.isIdentity() && "Run reinterpret-map before conversion.");
640 const auto elemTp = stt.getElementType();
641 const Level lvlRank = stt.getLvlRank();
642 Value lvlCoords, vref;
643 {
644 OpBuilder::InsertionGuard guard(rewriter);
645 Operation *loop = op;
646 // Finds the outermost loop.
647 while (auto l = loop->getParentOfType<LoopLikeOpInterface>())
648 loop = l;
649
650 if (llvm::isa<LoopLikeOpInterface>(Val: loop)) {
651 // Hoists alloca outside the loop to avoid stack overflow.
652 rewriter.setInsertionPoint(loop);
653 }
654 lvlCoords = genAlloca(builder&: rewriter, loc, sz: lvlRank, tp: rewriter.getIndexType());
655 vref = genAllocaScalar(builder&: rewriter, loc, tp: elemTp);
656 }
657 storeAll(builder&: rewriter, loc, mem: lvlCoords, vs: adaptor.getIndices());
658 memref::StoreOp::create(builder&: rewriter, location: loc, valueToStore: adaptor.getScalar(), memref: vref);
659 SmallString<12> name{"lexInsert", primaryTypeFunctionSuffix(elemTp)};
660 createFuncCall(builder&: rewriter, loc, name, resultType: {},
661 operands: {adaptor.getDest(), lvlCoords, vref}, emitCInterface: EmitCInterface::On);
662 rewriter.replaceOp(op, newValues: adaptor.getDest());
663 return success();
664 }
665};
666
667/// Sparse conversion rule for the expand operator.
668class SparseTensorExpandConverter : public OpConversionPattern<ExpandOp> {
669public:
670 using Base::Base;
671 LogicalResult
672 matchAndRewrite(ExpandOp op, OpAdaptor adaptor,
673 ConversionPatternRewriter &rewriter) const override {
674 Location loc = op->getLoc();
675 const auto srcTp = getSparseTensorType(val: op.getTensor());
676 Type eltType = srcTp.getElementType();
677 Type boolType = rewriter.getIntegerType(width: 1);
678 Type idxType = rewriter.getIndexType();
679 // All initialization should be done on entry of the loop nest.
680 rewriter.setInsertionPointAfter(op.getTensor().getDefiningOp());
681 // Get the cardinality of valid coordinates for the innermost level.
682 Value sz = createOrFoldLvlCall(builder&: rewriter, loc, stt: srcTp, tensor: adaptor.getTensor(),
683 lvl: srcTp.getLvlRank() - 1);
684 // Allocate temporary buffers for values, filled-switch, and coordinates.
685 // We do not use stack buffers for this, since the expanded size may
686 // be rather large (as it envelops a single expanded dense dimension).
687 Value values = genAlloc(rewriter, loc, sz, tp: eltType);
688 Value filled = genAlloc(rewriter, loc, sz, tp: boolType);
689 Value lastLvlCoordinates = genAlloc(rewriter, loc, sz, tp: idxType);
690 Value zero = constantZero(builder&: rewriter, loc, tp: idxType);
691 // Reset the values/filled-switch to all-zero/false. Note that this
692 // introduces an O(N) operation into the computation, but this reset
693 // operation is amortized over the innermost loops for the access
694 // pattern expansion. As noted in the operation doc, we would like
695 // to amortize this setup cost even between kernels.
696 linalg::FillOp::create(builder&: rewriter, location: loc,
697 inputs: ValueRange{constantZero(builder&: rewriter, loc, tp: eltType)},
698 outputs: ValueRange{values});
699 linalg::FillOp::create(builder&: rewriter, location: loc,
700 inputs: ValueRange{constantZero(builder&: rewriter, loc, tp: boolType)},
701 outputs: ValueRange{filled});
702 // Replace expansion op with these buffers and initial coordinate.
703 assert(op.getNumResults() == 4);
704 rewriter.replaceOp(op, newValues: {values, filled, lastLvlCoordinates, zero});
705 return success();
706 }
707};
708
709/// Sparse conversion rule for the compress operator.
710class SparseTensorCompressConverter : public OpConversionPattern<CompressOp> {
711public:
712 using Base::Base;
713 LogicalResult
714 matchAndRewrite(CompressOp op, OpAdaptor adaptor,
715 ConversionPatternRewriter &rewriter) const override {
716 Location loc = op->getLoc();
717 // Note that this method call resets the values/filled-switch back to
718 // all-zero/false by only iterating over the set elements, so the
719 // complexity remains proportional to the sparsity of the expanded
720 // access pattern.
721 Value values = adaptor.getValues();
722 Value filled = adaptor.getFilled();
723 Value added = adaptor.getAdded();
724 Value count = adaptor.getCount();
725 Value tensor = adaptor.getTensor();
726 const auto stt = getSparseTensorType(val: op.getTensor());
727 const Type elemTp = stt.getElementType();
728 const Level lvlRank = stt.getLvlRank();
729 auto lvlCoords = genAlloca(builder&: rewriter, loc, sz: lvlRank, tp: rewriter.getIndexType());
730 storeAll(builder&: rewriter, loc, mem: lvlCoords, vs: adaptor.getLvlCoords());
731 SmallString<12> name{"expInsert", primaryTypeFunctionSuffix(elemTp)};
732 createFuncCall(builder&: rewriter, loc, name, resultType: {},
733 operands: {tensor, lvlCoords, values, filled, added, count},
734 emitCInterface: EmitCInterface::On);
735 Operation *parent = getTop(op);
736 rewriter.setInsertionPointAfter(parent);
737 rewriter.replaceOp(op, newValues: adaptor.getTensor());
738 // Deallocate the buffers on exit of the loop nest.
739 memref::DeallocOp::create(builder&: rewriter, location: loc, memref: values);
740 memref::DeallocOp::create(builder&: rewriter, location: loc, memref: filled);
741 memref::DeallocOp::create(builder&: rewriter, location: loc, memref: added);
742 return success();
743 }
744};
745
746/// Sparse conversion rule for the sparse_tensor.assemble operator.
747class SparseTensorAssembleConverter : public OpConversionPattern<AssembleOp> {
748public:
749 using Base::Base;
750 LogicalResult
751 matchAndRewrite(AssembleOp op, OpAdaptor adaptor,
752 ConversionPatternRewriter &rewriter) const override {
753 const Location loc = op->getLoc();
754 const auto dstTp = getSparseTensorType(val: op.getResult());
755 assert(dstTp.hasStaticDimShape());
756 SmallVector<Value> dimSizesValues = getDimSizes(builder&: rewriter, loc, stt: dstTp);
757 // Use a library method to transfer the external buffers from
758 // clients to the internal SparseTensorStorage. Since we cannot
759 // assume clients transfer ownership of the buffers, this method
760 // will copy all data over into a new SparseTensorStorage.
761 Value dst =
762 NewCallParams(rewriter, loc)
763 .genBuffers(stt: dstTp.withoutDimToLvl(), dimSizesValues)
764 .genNewCall(action: Action::kPack,
765 ptr: genLvlPtrsBuffers(builder&: rewriter, loc, lvlTensors: adaptor.getLevels(),
766 valTensor: adaptor.getValues()));
767 rewriter.replaceOp(op, newValues: dst);
768 return success();
769 }
770};
771
772/// Sparse conversion rule for the sparse_tensor.disassemble operator.
773/// Note that the current implementation simply exposes the buffers to
774/// the external client. This assumes the client only reads the buffers
775/// (usually copying it to the external data structures, such as numpy
776/// arrays). The semantics of the disassemble operation technically
777/// require that the copying is done here already using the out-levels
778/// and out-values clause.
779class SparseTensorDisassembleConverter
780 : public OpConversionPattern<DisassembleOp> {
781public:
782 using Base::Base;
783 LogicalResult
784 matchAndRewrite(DisassembleOp op, OpAdaptor adaptor,
785 ConversionPatternRewriter &rewriter) const override {
786 Location loc = op->getLoc();
787 auto stt = getSparseTensorType(val: op.getTensor());
788 SmallVector<Value> retVal;
789 SmallVector<Value> retLen;
790 // Get the positions and coordinates buffers.
791 const Level lvlRank = stt.getLvlRank();
792 Level trailCOOLen = 0;
793 for (Level l = 0; l < lvlRank; l++) {
794 if (!stt.isUniqueLvl(l) &&
795 (stt.isCompressedLvl(l) || stt.isLooseCompressedLvl(l))) {
796 // A `(loose)compressed_nu` level marks the start of trailing COO
797 // start level. Since the target coordinate buffer used for trailing
798 // COO is passed in as AoS scheme and SparseTensorStorage uses a SoA
799 // scheme, we cannot simply use the internal buffers.
800 trailCOOLen = lvlRank - l;
801 break;
802 }
803 if (stt.isWithPos(l)) {
804 auto poss =
805 genPositionsCall(builder&: rewriter, loc, stt, ptr: adaptor.getTensor(), l);
806 auto posLen = linalg::createOrFoldDimOp(b&: rewriter, loc, val: poss, dim: 0);
807 auto posLenTp = op.getLvlLens().getTypes()[retLen.size()];
808 retVal.push_back(Elt: poss);
809 retLen.push_back(Elt: genScalarToTensor(builder&: rewriter, loc, elem: posLen, dstTp: posLenTp));
810 }
811 if (stt.isWithCrd(l)) {
812 auto crds =
813 genCoordinatesCall(builder&: rewriter, loc, stt, ptr: adaptor.getTensor(), l);
814 auto crdLen = linalg::createOrFoldDimOp(b&: rewriter, loc, val: crds, dim: 0);
815 auto crdLenTp = op.getLvlLens().getTypes()[retLen.size()];
816 retVal.push_back(Elt: crds);
817 retLen.push_back(Elt: genScalarToTensor(builder&: rewriter, loc, elem: crdLen, dstTp: crdLenTp));
818 }
819 }
820 // Handle AoS vs. SoA mismatch for COO.
821 if (trailCOOLen != 0) {
822 uint64_t cooStartLvl = lvlRank - trailCOOLen;
823 assert(!stt.isUniqueLvl(cooStartLvl) &&
824 (stt.isCompressedLvl(cooStartLvl) ||
825 stt.isLooseCompressedLvl(cooStartLvl)));
826 // Positions.
827 auto poss = genPositionsCall(builder&: rewriter, loc, stt, ptr: adaptor.getTensor(),
828 l: cooStartLvl);
829 auto posLen = linalg::createOrFoldDimOp(b&: rewriter, loc, val: poss, dim: 0);
830 auto posLenTp = op.getLvlLens().getTypes()[retLen.size()];
831 retVal.push_back(Elt: poss);
832 retLen.push_back(Elt: genScalarToTensor(builder&: rewriter, loc, elem: posLen, dstTp: posLenTp));
833 // Coordinates, copied over with:
834 // for (i = 0; i < crdLen; i++)
835 // buf[i][0] = crd0[i]; buf[i][1] = crd1[i];
836 auto buf = genToMemref(builder&: rewriter, loc, tensor: op.getOutLevels()[retLen.size()]);
837 auto crds0 = genCoordinatesCall(builder&: rewriter, loc, stt, ptr: adaptor.getTensor(),
838 l: cooStartLvl);
839 auto crds1 = genCoordinatesCall(builder&: rewriter, loc, stt, ptr: adaptor.getTensor(),
840 l: cooStartLvl + 1);
841 auto crdLen = linalg::createOrFoldDimOp(b&: rewriter, loc, val: crds0, dim: 0);
842 auto two = constantIndex(builder&: rewriter, loc, i: 2);
843 auto bufLen = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: crdLen, rhs: two);
844 Type indexType = rewriter.getIndexType();
845 auto zero = constantZero(builder&: rewriter, loc, tp: indexType);
846 auto one = constantOne(builder&: rewriter, loc, tp: indexType);
847 scf::ForOp forOp = scf::ForOp::create(builder&: rewriter, location: loc, lowerBound: zero, upperBound: crdLen, step: one);
848 auto idx = forOp.getInductionVar();
849 rewriter.setInsertionPointToStart(forOp.getBody());
850 auto c0 = memref::LoadOp::create(builder&: rewriter, location: loc, memref: crds0, indices: idx);
851 auto c1 = memref::LoadOp::create(builder&: rewriter, location: loc, memref: crds1, indices: idx);
852 SmallVector<Value> args;
853 args.push_back(Elt: idx);
854 args.push_back(Elt: zero);
855 memref::StoreOp::create(builder&: rewriter, location: loc, valueToStore: c0, memref: buf, indices: args);
856 args[1] = one;
857 memref::StoreOp::create(builder&: rewriter, location: loc, valueToStore: c1, memref: buf, indices: args);
858 rewriter.setInsertionPointAfter(forOp);
859 auto bufLenTp = op.getLvlLens().getTypes()[retLen.size()];
860 retVal.push_back(Elt: buf);
861 retLen.push_back(Elt: genScalarToTensor(builder&: rewriter, loc, elem: bufLen, dstTp: bufLenTp));
862 }
863 // Get the values buffer last.
864 auto vals = genValuesCall(builder&: rewriter, loc, stt, ptr: adaptor.getTensor());
865 auto valLenTp = op.getValLen().getType();
866 auto valLen = linalg::createOrFoldDimOp(b&: rewriter, loc, val: vals, dim: 0);
867 retVal.push_back(Elt: vals);
868 retLen.push_back(Elt: genScalarToTensor(builder&: rewriter, loc, elem: valLen, dstTp: valLenTp));
869
870 // Converts MemRefs back to Tensors.
871 assert(retVal.size() + retLen.size() == op.getNumResults());
872 for (unsigned i = 0, sz = retVal.size(); i < sz; i++) {
873 auto tensor = bufferization::ToTensorOp::create(
874 builder&: rewriter, location: loc,
875 result: memref::getTensorTypeFromMemRefType(type: retVal[i].getType()), buffer: retVal[i]);
876 retVal[i] =
877 tensor::CastOp::create(builder&: rewriter, location: loc, dest: op.getResultTypes()[i], source: tensor);
878 }
879
880 // Appends the actual memory length used in each buffer returned.
881 retVal.append(in_start: retLen.begin(), in_end: retLen.end());
882 rewriter.replaceOp(op, newValues: retVal);
883 return success();
884 }
885};
886
887struct SparseHasRuntimeLibraryConverter
888 : public OpConversionPattern<HasRuntimeLibraryOp> {
889 using Base::Base;
890 LogicalResult
891 matchAndRewrite(HasRuntimeLibraryOp op, OpAdaptor adaptor,
892 ConversionPatternRewriter &rewriter) const override {
893 auto i1Type = rewriter.getI1Type();
894 rewriter.replaceOpWithNewOp<arith::ConstantOp>(
895 op, args&: i1Type, args: rewriter.getIntegerAttr(type: i1Type, value: 1));
896 return success();
897 }
898};
899
900} // namespace
901
902//===----------------------------------------------------------------------===//
903// Sparse tensor type conversion into opaque pointer.
904//===----------------------------------------------------------------------===//
905
906mlir::SparseTensorTypeToPtrConverter::SparseTensorTypeToPtrConverter() {
907 addConversion(callback: [](Type type) { return type; });
908 addConversion(callback&: convertSparseTensorTypes);
909}
910
911//===----------------------------------------------------------------------===//
912// Public method for populating conversion rules.
913//===----------------------------------------------------------------------===//
914
915/// Populates the given patterns list with conversion rules required for
916/// the sparsification of linear algebra operations.
917void mlir::populateSparseTensorConversionPatterns(
918 const TypeConverter &typeConverter, RewritePatternSet &patterns) {
919 patterns
920 .add<SparseReturnConverter, SparseTensorLvlOpConverter,
921 SparseCastConverter, SparseReMapConverter, SparseTensorNewConverter,
922 SparseTensorAllocConverter, SparseTensorEmptyConverter,
923 SparseTensorDeallocConverter, SparseTensorReorderCOOConverter,
924 SparseTensorToPositionsConverter, SparseTensorToCoordinatesConverter,
925 SparseToCoordinatesBufferConverter, SparseTensorToValuesConverter,
926 SparseNumberOfEntriesConverter, SparseTensorLoadConverter,
927 SparseTensorInsertConverter, SparseTensorExpandConverter,
928 SparseTensorCompressConverter, SparseTensorAssembleConverter,
929 SparseTensorDisassembleConverter, SparseHasRuntimeLibraryConverter>(
930 arg: typeConverter, args: patterns.getContext());
931}
932