1//===- SparseTensorCodegen.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 types and primitives to actual compiler
10// visible buffers and actual compiler IR that implements these primitives on
11// the selected sparse tensor storage schemes. This pass provides an alternative
12// to the SparseTensorConversion pass, eliminating the dependence on a runtime
13// support library (other than for file I/O), and providing many more
14// opportunities for subsequent compiler optimization of the generated code.
15//
16//===----------------------------------------------------------------------===//
17
18#include "Utils/CodegenUtils.h"
19#include "Utils/SparseTensorDescriptor.h"
20
21#include "mlir/Dialect/Arith/Utils/Utils.h"
22#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
23#include "mlir/Dialect/Func/IR/FuncOps.h"
24#include "mlir/Dialect/Linalg/Utils/Utils.h"
25#include "mlir/Dialect/MemRef/IR/MemRef.h"
26#include "mlir/Dialect/SparseTensor/IR/Enums.h"
27#include "mlir/Dialect/SparseTensor/IR/SparseTensor.h"
28#include "mlir/Dialect/SparseTensor/IR/SparseTensorType.h"
29#include "mlir/Dialect/SparseTensor/Transforms/Passes.h"
30#include "mlir/Dialect/Tensor/IR/Tensor.h"
31#include "mlir/Transforms/DialectConversion.h"
32#include "llvm/ADT/SmallVectorExtras.h"
33
34#include <optional>
35
36using namespace mlir;
37using namespace mlir::sparse_tensor;
38
39//===----------------------------------------------------------------------===//
40// Helper methods.
41//===----------------------------------------------------------------------===//
42
43/// Flatten the given value ranges into a single vector of values.
44static SmallVector<Value> flattenValues(ArrayRef<ValueRange> values) {
45 SmallVector<Value> result;
46 for (const auto &vals : values)
47 llvm::append_range(C&: result, R: vals);
48 return result;
49}
50
51/// Generates a load with proper `index` typing.
52static Value genLoad(OpBuilder &builder, Location loc, Value mem, Value idx) {
53 idx = genCast(builder, loc, value: idx, dstTy: builder.getIndexType());
54 return memref::LoadOp::create(builder, location: loc, memref: mem, indices: idx);
55}
56
57/// Generates a store with proper `index` typing and proper value.
58static void genStore(OpBuilder &builder, Location loc, Value val, Value mem,
59 Value idx) {
60 idx = genCast(builder, loc, value: idx, dstTy: builder.getIndexType());
61 val = genCast(builder, loc, value: val,
62 dstTy: cast<ShapedType>(Val: mem.getType()).getElementType());
63 memref::StoreOp::create(builder, location: loc, valueToStore: val, memref: mem, indices: idx);
64}
65
66/// Creates a straightforward counting for-loop.
67static scf::ForOp createFor(OpBuilder &builder, Location loc, Value upper,
68 MutableArrayRef<Value> fields,
69 Value lower = Value()) {
70 Type indexType = builder.getIndexType();
71 if (!lower)
72 lower = constantZero(builder, loc, tp: indexType);
73 Value one = constantOne(builder, loc, tp: indexType);
74 scf::ForOp forOp =
75 scf::ForOp::create(builder, location: loc, lowerBound: lower, upperBound: upper, step: one, initArgs: fields);
76 for (unsigned i = 0, e = fields.size(); i < e; i++)
77 fields[i] = forOp.getRegionIterArg(index: i);
78 builder.setInsertionPointToStart(forOp.getBody());
79 return forOp;
80}
81
82/// Creates a push back operation.
83static void createPushback(OpBuilder &builder, Location loc,
84 MutSparseTensorDescriptor desc,
85 SparseTensorFieldKind kind, std::optional<Level> lvl,
86 Value value, Value repeat = Value()) {
87 Type etp = desc.getMemRefElementType(kind, lvl);
88 Value field = desc.getMemRefField(kind, lvl);
89 StorageSpecifierKind specFieldKind = toSpecifierKind(kind);
90
91 auto pushBackOp = PushBackOp::create(
92 builder, location: loc, curSize: desc.getSpecifierField(builder, loc, kind: specFieldKind, lvl),
93 inBuffer: field, value: genCast(builder, loc, value, dstTy: etp), n: repeat);
94
95 desc.setMemRefField(kind, lvl, v: pushBackOp.getOutBuffer());
96 desc.setSpecifierField(builder, loc, kind: specFieldKind, lvl,
97 v: pushBackOp.getNewSize());
98}
99
100/// Generates code that allocates a sparse storage scheme for given rank.
101static void allocSchemeForRank(OpBuilder &builder, Location loc,
102 MutSparseTensorDescriptor desc, Level startLvl) {
103 const SparseTensorType stt(desc.getRankedTensorType());
104 Value linear = constantIndex(builder, loc, i: 1);
105 const Level lvlRank = stt.getLvlRank();
106 for (Level lvl = startLvl; lvl < lvlRank; lvl++) {
107 const auto lt = stt.getLvlType(l: lvl);
108 if (isCompressedLT(lt) || isLooseCompressedLT(lt)) {
109 // Append linear x positions, initialized to zero. Since each compressed
110 // dimension initially already has a single zero entry, this maintains
111 // the desired "linear + 1" length property at all times. For loose
112 // compression, we multiply linear by two in order to append both the
113 // lo/hi positions.
114 Value posZero = constantZero(builder, loc, tp: stt.getPosType());
115 if (isLooseCompressedLT(lt)) {
116 Value two = constantIndex(builder, loc, i: 2);
117 linear = arith::MulIOp::create(builder, location: loc, lhs: linear, rhs: two);
118 }
119 createPushback(builder, loc, desc, kind: SparseTensorFieldKind::PosMemRef, lvl,
120 /*value=*/posZero, /*repeat=*/linear);
121 return;
122 } else if (isSingletonLT(lt) || isNOutOfMLT(lt)) {
123 return; // nothing to do
124 }
125 // Keep compounding the size, but nothing needs to be initialized
126 // at this level. We will eventually reach a compressed level or
127 // otherwise the values array for the from-here "all-dense" case.
128 assert(isDenseLT(lt));
129 Value size = desc.getLvlSize(builder, loc, lvl);
130 linear = arith::MulIOp::create(builder, location: loc, lhs: linear, rhs: size);
131 }
132 // Reached values array so prepare for an insertion.
133 Value valZero = constantZero(builder, loc, tp: stt.getElementType());
134 createPushback(builder, loc, desc, kind: SparseTensorFieldKind::ValMemRef,
135 lvl: std::nullopt, /*value=*/valZero, /*repeat=*/linear);
136}
137
138/// Creates allocation operation.
139static Value createAllocation(OpBuilder &builder, Location loc,
140 MemRefType memRefType, Value sz,
141 bool enableInit) {
142 Value buffer = memref::AllocOp::create(builder, location: loc, memrefType: memRefType, dynamicSizes: sz);
143 Type elemType = memRefType.getElementType();
144 if (enableInit) {
145 Value fillValue = constantZero(builder, loc, tp: elemType);
146 linalg::FillOp::create(builder, location: loc, inputs: fillValue, outputs: buffer);
147 }
148 return buffer;
149}
150
151/// Creates the dim sizes array, filling in from dynamic sizes.
152static void createDimSizes(OpBuilder &builder, Location loc,
153 SparseTensorType stt, ValueRange dynSizes,
154 /*out*/ SmallVectorImpl<Value> &dimSizesValues) {
155 const Dimension dimRank = stt.getDimRank();
156 dimSizesValues.clear();
157 dimSizesValues.reserve(N: dimRank);
158 unsigned i = 0;
159 for (const Size sz : stt.getDimShape())
160 dimSizesValues.push_back(Elt: ShapedType::isDynamic(dValue: sz)
161 ? dynSizes[i++]
162 : constantIndex(builder, loc, i: sz));
163}
164
165/// Creates allocation for each field in sparse tensor type. Note that
166/// for all dynamic memrefs in the sparse tensor stroage layout, the
167/// memory size is really the capacity of the "vector", while the actual
168/// size resides in the sizes array.
169static void createAllocFields(OpBuilder &builder, Location loc,
170 SparseTensorType stt, bool enableInit,
171 Value sizeHint,
172 SmallVectorImpl<Value> &lvlSizesValues,
173 /*out*/ SmallVectorImpl<Value> &fields) {
174 Level lvlRank = stt.getLvlRank();
175 // Set up some heuristic sizes. We try to set the initial
176 // size based on available information. Otherwise we just
177 // initialize a few elements to start the reallocation chain.
178 // TODO: refine this
179 Value posHeuristic, crdHeuristic, valHeuristic;
180 if (stt.isAllDense()) {
181 valHeuristic = lvlSizesValues[0];
182 for (Level lvl = 1; lvl < lvlRank; lvl++)
183 valHeuristic = arith::MulIOp::create(builder, location: loc, lhs: valHeuristic,
184 rhs: lvlSizesValues[lvl]);
185 } else if (sizeHint) {
186 if (stt.getAoSCOOStart() == 0) {
187 posHeuristic = constantIndex(builder, loc, i: 2);
188 crdHeuristic = arith::MulIOp::create(
189 builder, location: loc, lhs: constantIndex(builder, loc, i: lvlRank), rhs: sizeHint); // AOS
190 } else if (lvlRank == 2 && stt.isDenseLvl(l: 0) && stt.isCompressedLvl(l: 1)) {
191 posHeuristic = arith::AddIOp::create(builder, location: loc, lhs: sizeHint,
192 rhs: constantIndex(builder, loc, i: 1));
193 crdHeuristic = sizeHint;
194 } else {
195 posHeuristic = crdHeuristic = constantIndex(builder, loc, i: 16);
196 }
197 valHeuristic = sizeHint;
198 } else {
199 posHeuristic = crdHeuristic = valHeuristic =
200 constantIndex(builder, loc, i: 16);
201 }
202 // Initializes all fields. An initial storage specifier and allocated
203 // positions/coordinates/values memrefs (with heuristic capacity).
204 foreachFieldAndTypeInSparseTensor(
205 stt,
206 [&builder, &fields, stt, loc, posHeuristic, crdHeuristic, valHeuristic,
207 enableInit](Type fType, FieldIndex fIdx, SparseTensorFieldKind fKind,
208 Level /*lvl*/, LevelType /*lt*/) -> bool {
209 assert(fields.size() == fIdx);
210 Value field;
211 switch (fKind) {
212 case SparseTensorFieldKind::StorageSpec:
213 field = SparseTensorSpecifier::getInitValue(builder, loc, stt);
214 break;
215 case SparseTensorFieldKind::PosMemRef:
216 field = createAllocation(builder, loc, memRefType: cast<MemRefType>(Val&: fType),
217 sz: posHeuristic, enableInit);
218 break;
219 case SparseTensorFieldKind::CrdMemRef:
220 field = createAllocation(builder, loc, memRefType: cast<MemRefType>(Val&: fType),
221 sz: crdHeuristic, enableInit);
222 break;
223 case SparseTensorFieldKind::ValMemRef:
224 field = createAllocation(builder, loc, memRefType: cast<MemRefType>(Val&: fType),
225 sz: valHeuristic, enableInit);
226 break;
227 }
228 assert(field);
229 fields.push_back(Elt: field);
230 // Returns true to continue the iteration.
231 return true;
232 });
233 // Initialize the storage scheme to an empty tensor. Sets the lvlSizes
234 // and gives all position fields an initial zero entry, so that it is
235 // easier to maintain the "linear + 1" length property.
236 MutSparseTensorDescriptor desc(stt, fields);
237 Value posZero = constantZero(builder, loc, tp: stt.getPosType());
238 for (Level lvl = 0, lvlRank = stt.getLvlRank(); lvl < lvlRank; lvl++) {
239 desc.setLvlSize(builder, loc, lvl, v: lvlSizesValues[lvl]);
240 const auto lt = stt.getLvlType(l: lvl);
241 if (isCompressedLT(lt) || isLooseCompressedLT(lt))
242 createPushback(builder, loc, desc, kind: SparseTensorFieldKind::PosMemRef, lvl,
243 /*value=*/posZero);
244 }
245 allocSchemeForRank(builder, loc, desc, /*rank=*/startLvl: 0);
246}
247
248/// Helper method that generates block specific to compressed case:
249///
250/// // given: parentPos = posCursor[lvl-1]
251/// pstart = desc.positions[lvl][parentPos]
252/// pstop = desc.positions[lvl][parentPos+1]
253/// plast = pstop - 1
254/// msz = desc.coordinates[lvl].size()
255/// if (pstart < pstop) {
256/// isPresent = (desc.coordinates[lvl][plast] == lvlCoords[lvl])
257/// } else { // first insertion
258/// isPresent = false
259/// desc.positions[lvl][parentPos] = msz
260/// }
261/// if (isPresent) { // coordinate is already present
262/// pnext = plast
263/// } else {
264/// desc.coordinates[lvl].push_back(lvlCoords[lvl])
265/// desc.positions[lvl][parentPos+1] = msz+1
266/// pnext = msz
267/// <prepare level lvl+1>
268/// }
269/// posCursor[lvl] = pnext
270static Value genCompressed(OpBuilder &builder, Location loc,
271 MutSparseTensorDescriptor desc, ValueRange lvlCoords,
272 Value /*unused*/, Value parentPos, Level lvl) {
273 const SparseTensorType stt(desc.getRankedTensorType());
274 const Level lvlRank = stt.getLvlRank();
275 assert(lvl < lvlRank && "Level is out of bounds");
276 assert(lvlCoords.size() == static_cast<size_t>(lvlRank) &&
277 "Level-rank mismatch");
278 SmallVector<Type> types;
279 Type indexType = builder.getIndexType();
280 Type boolType = builder.getIntegerType(width: 1);
281 unsigned crdFidx;
282 unsigned crdStride;
283 std::tie(args&: crdFidx, args&: crdStride) = desc.getCrdMemRefIndexAndStride(lvl);
284 const Value one = constantIndex(builder, loc, i: 1);
285 const Value pp1 = arith::AddIOp::create(builder, location: loc, lhs: parentPos, rhs: one);
286 const Value positionsAtLvl = desc.getPosMemRef(lvl);
287 const Value pstart = genLoad(builder, loc, mem: positionsAtLvl, idx: parentPos);
288 const Value pstop = genLoad(builder, loc, mem: positionsAtLvl, idx: pp1);
289 const Value crdMsz = desc.getCrdMemSize(builder, loc, lvl);
290 const Value crdStrideC =
291 crdStride > 1 ? constantIndex(builder, loc, i: crdStride) : Value();
292 const Value msz =
293 crdStrideC ? arith::DivUIOp::create(builder, location: loc, lhs: crdMsz, rhs: crdStrideC)
294 : crdMsz;
295 const Value plast = arith::SubIOp::create(
296 builder, location: loc, lhs: genCast(builder, loc, value: pstop, dstTy: indexType), rhs: one);
297 // Conditional expression.
298 Value lt = arith::CmpIOp::create(builder, location: loc, predicate: arith::CmpIPredicate::ult,
299 lhs: pstart, rhs: pstop);
300 types.push_back(Elt: boolType);
301 scf::IfOp ifOp1 = scf::IfOp::create(builder, location: loc, resultTypes: types, cond: lt, /*else*/ withElseRegion: true);
302 types.pop_back();
303 builder.setInsertionPointToStart(&ifOp1.getThenRegion().front());
304 Value crd = genLoad(
305 builder, loc, mem: desc.getMemRefField(fidx: crdFidx),
306 idx: crdStrideC ? arith::MulIOp::create(builder, location: loc, lhs: plast, rhs: crdStrideC)
307 : plast);
308 Value eq = arith::CmpIOp::create(builder, location: loc, predicate: arith::CmpIPredicate::eq,
309 lhs: genCast(builder, loc, value: crd, dstTy: indexType),
310 rhs: lvlCoords[lvl]);
311 scf::YieldOp::create(builder, location: loc, results: eq);
312 builder.setInsertionPointToStart(&ifOp1.getElseRegion().front());
313 if (lvl > 0)
314 genStore(builder, loc, val: msz, mem: positionsAtLvl, idx: parentPos);
315 scf::YieldOp::create(builder, location: loc, results: constantI1(builder, loc, b: false));
316 builder.setInsertionPointAfter(ifOp1);
317 // If present construct. Note that for a non-unique dimension level, we
318 // simply set the condition to false and rely on CSE/DCE to clean up the IR.
319 //
320 // TODO: generate less temporary IR?
321 //
322 for (unsigned i = 0, e = desc.getNumFields(); i < e; i++)
323 types.push_back(Elt: desc.getField(fidx: i).getType());
324 types.push_back(Elt: indexType);
325 const Value p = stt.isUniqueLvl(l: lvl) ? ifOp1.getResult(i: 0)
326 : constantI1(builder, loc, b: false);
327 scf::IfOp ifOp2 = scf::IfOp::create(builder, location: loc, resultTypes: types, cond: p, /*else*/ withElseRegion: true);
328 // If present (fields unaffected, update pnext to plast).
329 builder.setInsertionPointToStart(&ifOp2.getThenRegion().front());
330
331 // FIXME: This does not looks like a clean way, but probably the most
332 // efficient way.
333 desc.getFields().push_back(Elt: plast);
334 scf::YieldOp::create(builder, location: loc, results: desc.getFields());
335 desc.getFields().pop_back();
336
337 // If !present (changes fields, update pnext).
338 builder.setInsertionPointToStart(&ifOp2.getElseRegion().front());
339 Value mszp1 = arith::AddIOp::create(builder, location: loc, lhs: msz, rhs: one);
340 genStore(builder, loc, val: mszp1, mem: positionsAtLvl, idx: pp1);
341 createPushback(builder, loc, desc, kind: SparseTensorFieldKind::CrdMemRef, lvl,
342 /*value=*/lvlCoords[lvl]);
343 // Prepare the next level "as needed".
344 if ((lvl + 1) < lvlRank)
345 allocSchemeForRank(builder, loc, desc, startLvl: lvl + 1);
346
347 desc.getFields().push_back(Elt: msz);
348 scf::YieldOp::create(builder, location: loc, results: desc.getFields());
349 desc.getFields().pop_back();
350
351 // Update fields and return next pos.
352 builder.setInsertionPointAfter(ifOp2);
353 unsigned o = 0;
354 for (unsigned i = 0, e = desc.getNumFields(); i < e; i++)
355 desc.setField(fidx: i, v: ifOp2.getResult(i: o++));
356 return ifOp2.getResult(i: o);
357}
358
359/// Generates insertion finalization code.
360static void genEndInsert(OpBuilder &builder, Location loc,
361 SparseTensorDescriptor desc) {
362 const SparseTensorType stt(desc.getRankedTensorType());
363 const Level lvlRank = stt.getLvlRank();
364 for (Level lvl = 0; lvl < lvlRank; lvl++) {
365 const auto lt = stt.getLvlType(l: lvl);
366 if (isCompressedLT(lt)) {
367 // Compressed dimensions need a position cleanup for all entries
368 // that were not visited during the insertion pass.
369 //
370 // TODO: avoid cleanup and keep compressed scheme consistent at all
371 // times?
372 //
373 if (lvl > 0) {
374 Type posType = stt.getPosType();
375 Value posMemRef = desc.getPosMemRef(lvl);
376 Value hi = desc.getPosMemSize(builder, loc, lvl);
377 Value zero = constantIndex(builder, loc, i: 0);
378 Value one = constantIndex(builder, loc, i: 1);
379 // Vector of only one, but needed by createFor's prototype.
380 SmallVector<Value, 1> inits{genLoad(builder, loc, mem: posMemRef, idx: zero)};
381 scf::ForOp loop = createFor(builder, loc, upper: hi, fields: inits, lower: one);
382 Value i = loop.getInductionVar();
383 Value oldv = loop.getRegionIterArg(index: 0);
384 Value newv = genLoad(builder, loc, mem: posMemRef, idx: i);
385 Value posZero = constantZero(builder, loc, tp: posType);
386 Value cond = arith::CmpIOp::create(
387 builder, location: loc, predicate: arith::CmpIPredicate::eq, lhs: newv, rhs: posZero);
388 scf::IfOp ifOp = scf::IfOp::create(builder, location: loc, resultTypes: TypeRange(posType),
389 cond, /*else*/ withElseRegion: true);
390 builder.setInsertionPointToStart(&ifOp.getThenRegion().front());
391 genStore(builder, loc, val: oldv, mem: posMemRef, idx: i);
392 scf::YieldOp::create(builder, location: loc, results: oldv);
393 builder.setInsertionPointToStart(&ifOp.getElseRegion().front());
394 scf::YieldOp::create(builder, location: loc, results: newv);
395 builder.setInsertionPointAfter(ifOp);
396 scf::YieldOp::create(builder, location: loc, results: ifOp.getResult(i: 0));
397 builder.setInsertionPointAfter(loop);
398 }
399 } else {
400 assert(isDenseLT(lt) || isLooseCompressedLT(lt) || isSingletonLT(lt) ||
401 isNOutOfMLT(lt));
402 }
403 }
404}
405
406/// Generates a subview into the sizes.
407static Value genSliceToSize(OpBuilder &builder, Location loc, Value mem,
408 Value sz) {
409 auto memTp = llvm::cast<MemRefType>(Val: mem.getType());
410 // For higher-dimensional memrefs, we assume that the innermost
411 // dimension is always of the right size.
412 // TODO: generate complex truncating view here too?
413 if (memTp.getRank() > 1)
414 return mem;
415 // Truncate linear memrefs to given size.
416 return memref::SubViewOp::create(
417 builder, location: loc,
418 result: MemRefType::get(shape: {ShapedType::kDynamic}, elementType: memTp.getElementType()),
419 source: mem, offsets: ValueRange{}, sizes: ValueRange{sz}, strides: ValueRange{},
420 static_offsets: ArrayRef<int64_t>{0}, // static offset
421 static_sizes: ArrayRef<int64_t>{ShapedType::kDynamic}, // dynamic size
422 static_strides: ArrayRef<int64_t>{1}) // static stride
423 .getResult();
424}
425
426/// Creates the reassociation array.
427static SmallVector<ReassociationIndices>
428getReassociationForFlattening(ShapedType srcTp, unsigned batchLvls) {
429 SmallVector<ReassociationIndices> ret(batchLvls + 1, {});
430 // Create reassociation in the form:
431 // {0}, {1}, ..., {batchLvl - 1}, {batchLvl, ..., rank}
432 for (unsigned i = 0; i < batchLvls; i++)
433 ret[i].push_back(Elt: i);
434
435 for (int i = batchLvls, e = srcTp.getRank(); i < e; i++)
436 ret.back().push_back(Elt: i);
437
438 return ret;
439}
440
441//===----------------------------------------------------------------------===//
442// Codegen rules.
443//===----------------------------------------------------------------------===//
444
445namespace {
446
447/// Helper class to help lowering sparse_tensor.insert operation.
448class SparseInsertGenerator
449 : public FuncCallOrInlineGenerator<SparseInsertGenerator> {
450public:
451 SparseInsertGenerator(TensorType rtp, TypeRange retTypes, ValueRange params,
452 bool genCall)
453 : FuncCallOrInlineGenerator(retTypes, params, genCall), rtp(rtp) {};
454
455 /// Generates code along an insertion path without the need for a "cursor".
456 /// This current insertion strategy comes at the expense of some testing
457 /// overhead for each insertion. The strategy will be optimized later for
458 /// common insertion patterns. The current insertion strategy also assumes
459 /// insertions occur in "a reasonable order" that enables building the
460 /// storage scheme in an appending/inserting kind of fashion (i.e. no
461 /// in-between insertions that need data movement). The implementation
462 /// relies on CSE/DCE to clean up all bookkeeping that is not needed.
463 ///
464 /// TODO: better unord/not-unique; also generalize, optimize, specialize!
465 SmallVector<Value> genImplementation(TypeRange retTypes, ValueRange args,
466 OpBuilder &builder, Location loc) {
467 const SparseTensorType stt(llvm::cast<RankedTensorType>(Val&: rtp));
468 const Level lvlRank = stt.getLvlRank();
469 // Extract fields and coordinates from args.
470 SmallVector<Value> fields = llvm::to_vector(Range: args.drop_back(n: lvlRank + 1));
471 MutSparseTensorDescriptor desc(stt, fields);
472 const SmallVector<Value> coords =
473 llvm::to_vector(Range: args.take_back(n: lvlRank + 1).drop_back());
474 Value value = args.back();
475 Value parentPos = constantZero(builder, loc, tp: builder.getIndexType());
476 // Generate code for every level.
477 for (Level lvl = 0; lvl < lvlRank; lvl++) {
478 const auto lt = stt.getLvlType(l: lvl);
479 if (isCompressedLT(lt) || isLooseCompressedLT(lt)) {
480 // Create:
481 // if (!present) {
482 // coordinates[lvl].push_back(coords[lvl])
483 // <update positions and prepare level lvl + 1>
484 // }
485 // positions[lvl] = coordinates.size() - 1
486 // <insert @ positions[lvl] at next level lvl + 1>
487 if (isLooseCompressedLT(lt)) {
488 Value two = constantIndex(builder, loc, i: 2);
489 parentPos = arith::MulIOp::create(builder, location: loc, lhs: parentPos, rhs: two);
490 }
491 parentPos =
492 genCompressed(builder, loc, desc, lvlCoords: coords, value, parentPos, lvl);
493 } else if (isSingletonLT(lt) || isNOutOfMLT(lt)) {
494 // Create:
495 // coordinates[lvl].push_back(coords[lvl])
496 // positions[lvl] = positions[lvl-1]
497 // <insert @ positions[lvl] at next level lvl + 1>
498 createPushback(builder, loc, desc, kind: SparseTensorFieldKind::CrdMemRef,
499 lvl, /*value=*/coords[lvl]);
500 } else {
501 assert(isDenseLT(lt));
502 // Construct the new position as:
503 // positions[lvl] = size * positions[lvl-1] + coords[lvl]
504 // <insert @ positions[lvl] at next level lvl + 1>
505 Value size = desc.getLvlSize(builder, loc, lvl);
506 Value mult = arith::MulIOp::create(builder, location: loc, lhs: size, rhs: parentPos);
507 parentPos = arith::AddIOp::create(builder, location: loc, lhs: mult, rhs: coords[lvl]);
508 }
509 }
510 // Reached the actual value append/insert.
511 if (!stt.isDenseLvl(l: lvlRank - 1))
512 createPushback(builder, loc, desc, kind: SparseTensorFieldKind::ValMemRef,
513 lvl: std::nullopt, value);
514 else
515 genStore(builder, loc, val: value, mem: desc.getValMemRef(), idx: parentPos);
516 return fields;
517 }
518
519 std::string getMangledFuncName() {
520 // The mangled name of the function has this format:
521 // <namePrefix>_<LT>_<shape>_<ordering>_<eltType>_<crdWidth>_<posWidth>
522 constexpr const char kInsertFuncNamePrefix[] = "_insert_";
523 const SparseTensorType stt(llvm::cast<RankedTensorType>(Val&: rtp));
524 SmallString<32> nameBuffer;
525 llvm::raw_svector_ostream nameOstream(nameBuffer);
526 nameOstream << kInsertFuncNamePrefix;
527 const Level lvlRank = stt.getLvlRank();
528 for (Level l = 0; l < lvlRank; l++) {
529 std::string lvlType = toMLIRString(lt: stt.getLvlType(l));
530 // Replace/remove punctuations in level properties.
531 std::replace_if(
532 first: lvlType.begin(), last: lvlType.end(),
533 pred: [](char c) { return c == '(' || c == ','; }, new_value: '_');
534 llvm::erase_if(C&: lvlType, P: [](char c) { return c == ')' || c == ' '; });
535 nameOstream << lvlType << "_";
536 }
537 // Static dim sizes are used in the generated code while dynamic sizes are
538 // loaded from the dimSizes buffer. This is the reason for adding the shape
539 // to the function name.
540 for (const auto sz : stt.getDimShape())
541 nameOstream << sz << "_";
542 // Permutation information is also used in generating insertion.
543 if (!stt.isIdentity())
544 nameOstream << stt.getDimToLvl() << "_";
545 nameOstream << stt.getElementType() << "_";
546 nameOstream << stt.getCrdWidth() << "_" << stt.getPosWidth();
547 return nameOstream.str().str();
548 }
549
550private:
551 TensorType rtp;
552};
553
554/// Sparse tensor storage conversion rule for returns.
555class SparseReturnConverter : public OpConversionPattern<func::ReturnOp> {
556public:
557 using Base::Base;
558 LogicalResult
559 matchAndRewrite(func::ReturnOp op, OneToNOpAdaptor adaptor,
560 ConversionPatternRewriter &rewriter) const override {
561 // Create a return with the flattened value extracted from sparse tensors.
562 rewriter.replaceOpWithNewOp<func::ReturnOp>(
563 op, args: flattenValues(values: adaptor.getOperands()));
564 return success();
565 }
566};
567
568/// Sparse tensor storage conversion rule for calls.
569class SparseCallConverter : public OpConversionPattern<func::CallOp> {
570public:
571 // The default CallOp converter can not handle 1:N type conversion.
572 using Base::Base;
573 LogicalResult
574 matchAndRewrite(func::CallOp op, OneToNOpAdaptor adaptor,
575 ConversionPatternRewriter &rewriter) const override {
576 Location loc = op.getLoc();
577 // In case of:
578 // sparse_tensor, f, sparse_tensor = call @foo(...)
579 // ==>
580 // memref..., f, memref = call @foo(...) replace with
581 // cast(memref...)->sparse_tensor, f, cast(memref...)->sparse_tensor
582 SmallVector<Type> finalRetTy;
583 if (failed(Result: typeConverter->convertTypes(types: op.getResultTypes(), results&: finalRetTy)))
584 return failure();
585
586 // (1) Generates new call with flattened return value.
587 auto newCall =
588 func::CallOp::create(builder&: rewriter, location: loc, callee: op.getCallee(), results: finalRetTy,
589 operands: flattenValues(values: adaptor.getOperands()));
590 // (2) Gather sparse tensor returns.
591 SmallVector<SmallVector<Value>> packedResultVals;
592 // Tracks the offset of current return value (of the original call)
593 // relative to the new call (after sparse tensor flattening);
594 unsigned retOffset = 0;
595 // Temporal buffer to hold the flattened list of type for
596 // a sparse tensor.
597 SmallVector<Type> sparseFlat;
598 for (auto ret : op.getResults()) {
599 assert(retOffset < newCall.getNumResults());
600 auto retType = ret.getType();
601 if (failed(Result: typeConverter->convertType(t: retType, results&: sparseFlat)))
602 llvm_unreachable("Failed to convert type in sparse tensor codegen");
603
604 // Converted types can not be empty when the type conversion succeed.
605 assert(!sparseFlat.empty());
606 if (sparseFlat.size() > 1) {
607 auto flatSize = sparseFlat.size();
608 packedResultVals.emplace_back();
609 llvm::append_range(C&: packedResultVals.back(),
610 R: newCall.getResults().slice(n: retOffset, m: flatSize));
611 retOffset += flatSize;
612 } else {
613 // If this is an 1:1 conversion, no need for casting.
614 packedResultVals.emplace_back();
615 packedResultVals.back().push_back(Elt: newCall.getResult(i: retOffset));
616 retOffset++;
617 }
618 sparseFlat.clear();
619 }
620
621 assert(packedResultVals.size() == op.getNumResults());
622 rewriter.replaceOpWithMultiple(op, newValues: std::move(packedResultVals));
623 return success();
624 }
625};
626
627/// Sparse codegen rule for level accesses.
628class SparseLvlOpConverter : public OpConversionPattern<LvlOp> {
629public:
630 using Base::Base;
631 LogicalResult
632 matchAndRewrite(LvlOp op, OneToNOpAdaptor adaptor,
633 ConversionPatternRewriter &rewriter) const override {
634 std::optional<int64_t> lvl = op.getConstantLvlIndex();
635 RankedTensorType srcType = op.getSource().getType();
636 if (!lvl || !getSparseTensorEncoding(type: srcType))
637 return failure();
638
639 auto desc = getDescriptorFromTensorTuple(adaptorValues: adaptor.getSource(), type: srcType);
640 auto sz = desc.getLvlSize(builder&: rewriter, loc: op.getLoc(), lvl: *lvl);
641
642 rewriter.replaceOp(op, newValues: sz);
643 return success();
644 }
645};
646
647// TODO: use a new SortCOO operation here instead of reusing convert op.
648struct SparseReorderCOOConverter : public OpConversionPattern<ReorderCOOOp> {
649 using Base::Base;
650 LogicalResult
651 matchAndRewrite(ReorderCOOOp op, OneToNOpAdaptor adaptor,
652 ConversionPatternRewriter &rewriter) const override {
653 Location loc = op.getLoc();
654 MLIRContext *ctx = op.getContext();
655
656 SparseTensorType srcStt = getSparseTensorType(val: op.getInputCoo());
657 SparseTensorType dstStt = getSparseTensorType(val: op.getResultCoo());
658
659 // Should have been verified.
660 assert(dstStt.isAllOrdered() && !srcStt.isAllOrdered() &&
661 dstStt.isCOOType() && srcStt.isCOOType());
662 assert(dstStt.hasSameDimToLvl(srcStt));
663
664 // We don't need a mutable descriptor here as we perform sorting in-place.
665 auto desc = getDescriptorFromTensorTuple(adaptorValues: adaptor.getInputCoo(),
666 type: op.getInputCoo().getType());
667 auto nnz = desc.getValMemSize(builder&: rewriter, loc: op.getLoc());
668 auto crd = desc.getAOSMemRef();
669 auto val = desc.getValMemRef();
670
671 // Otherwise we need another data shuffle and a non-identity map.
672 assert(dstStt.hasSameDimToLvl(srcStt));
673 (void)dstStt; // to silence warning when assertion is disabled
674
675 auto id = AffineMap::getMultiDimIdentityMap(numDims: srcStt.getLvlRank(), context: ctx);
676
677 SortOp::create(builder&: rewriter, location: loc, n: nnz, xy: crd, ys: ValueRange{val}, perm_map: id,
678 ny: rewriter.getIndexAttr(value: 0), algorithm: op.getAlgorithm());
679
680 // Since we do in-place sorting, the destinate tensor will have the same set
681 // of memrefs as the source tensor.
682 rewriter.replaceOpWithMultiple(op, newValues: {adaptor.getInputCoo()});
683 return success();
684 }
685};
686
687template <typename Op, StorageSpecifierKind kind>
688class SparseSliceGetterOpConverter : public OpConversionPattern<Op> {
689public:
690 using OpConversionPattern<Op>::OpConversionPattern;
691 using typename OpConversionPattern<Op>::OneToNOpAdaptor;
692
693 LogicalResult
694 matchAndRewrite(Op op, OneToNOpAdaptor adaptor,
695 ConversionPatternRewriter &rewriter) const override {
696 // Simply lowers to specifer.get <field> operation.
697 auto desc = getDescriptorFromTensorTuple(adaptor.getSlice(),
698 op.getSlice().getType());
699 auto v = desc.getSpecifierField(rewriter, op.getLoc(), kind,
700 op.getDim().getZExtValue());
701
702 rewriter.replaceOp(op, v);
703 return success();
704 }
705};
706
707/// Sparse codegen rule for trivial tensor casts.
708class SparseCastConverter : public OpConversionPattern<tensor::CastOp> {
709public:
710 using Base::Base;
711 LogicalResult
712 matchAndRewrite(tensor::CastOp op, OneToNOpAdaptor adaptor,
713 ConversionPatternRewriter &rewriter) const override {
714 // Only rewrite identically annotated source/dest.
715 auto encDst = getSparseTensorEncoding(type: op.getType());
716 auto encSrc = getSparseTensorEncoding(type: op.getSource().getType());
717 if (!encDst || encDst != encSrc)
718 return failure();
719 rewriter.replaceOpWithMultiple(op, newValues: {adaptor.getSource()});
720 return success();
721 }
722};
723
724class SparseReMapConverter : public OpConversionPattern<ReinterpretMapOp> {
725public:
726 using Base::Base;
727 LogicalResult
728 matchAndRewrite(ReinterpretMapOp op, OneToNOpAdaptor adaptor,
729 ConversionPatternRewriter &rewriter) const override {
730 // Simply fold the operation.
731 rewriter.replaceOpWithMultiple(op, newValues: {adaptor.getSource()});
732 return success();
733 }
734};
735
736/// Sparse codegen rule for the alloc operator.
737class SparseTensorAllocConverter
738 : public OpConversionPattern<bufferization::AllocTensorOp> {
739public:
740 using Base::Base;
741 SparseTensorAllocConverter(const TypeConverter &typeConverter,
742 MLIRContext *context, bool enableInit)
743 : OpConversionPattern(typeConverter, context),
744 enableBufferInitialization(enableInit) {}
745
746 LogicalResult
747 matchAndRewrite(bufferization::AllocTensorOp op, OneToNOpAdaptor adaptor,
748 ConversionPatternRewriter &rewriter) const override {
749 const auto resType = getSparseTensorType(val: op);
750 if (!resType.hasEncoding())
751 return failure();
752
753 Location loc = op.getLoc();
754 // Deal with copy.
755 if (op.getCopy()) {
756 auto desc = getDescriptorFromTensorTuple(
757 adaptorValues: adaptor.getCopy(), type: cast<RankedTensorType>(Val: op.getCopy().getType()));
758 SmallVector<Value> fields;
759 fields.reserve(N: desc.getNumFields());
760 // Memcpy on memref fields.
761 for (auto field : desc.getMemRefFields()) {
762 auto memrefTp = cast<MemRefType>(Val: field.getType());
763 auto size = memref::DimOp::create(builder&: rewriter, location: loc, source: field, index: 0);
764 auto copied =
765 memref::AllocOp::create(builder&: rewriter, location: loc, memrefType: memrefTp, dynamicSizes: ValueRange{size});
766 memref::CopyOp::create(builder&: rewriter, location: loc, source: field, target: copied);
767 fields.push_back(Elt: copied);
768 }
769 // Reuses specifier.
770 fields.push_back(Elt: desc.getSpecifier());
771 assert(fields.size() == desc.getNumFields());
772 rewriter.replaceOpWithMultiple(op, newValues: {fields});
773 return success();
774 }
775
776 if (!resType.isIdentity()) {
777 return rewriter.notifyMatchFailure(
778 arg&: op, msg: "try run --sparse-reinterpret-map before codegen");
779 }
780 // Level size equals to dimension size since lvl2dim map is an identity map.
781 SmallVector<Value> lvlSizesValues;
782 createDimSizes(builder&: rewriter, loc, stt: resType,
783 dynSizes: flattenValues(values: adaptor.getDynamicSizes()),
784 /*dimSizesValues=*/lvlSizesValues);
785
786 // Construct allocation for each field.
787 Value sizeHint = op.getSizeHint();
788 SmallVector<Value> fields;
789 createAllocFields(builder&: rewriter, loc, stt: resType, enableInit: enableBufferInitialization,
790 sizeHint, lvlSizesValues, fields);
791
792 // Replace operation with resulting memrefs.
793 rewriter.replaceOpWithMultiple(op, newValues: {fields});
794 return success();
795 }
796
797private:
798 bool enableBufferInitialization;
799};
800
801/// Sparse codegen rule for the empty tensor operator.
802class SparseTensorEmptyConverter : public OpConversionPattern<tensor::EmptyOp> {
803public:
804 using Base::Base;
805 SparseTensorEmptyConverter(const TypeConverter &typeConverter,
806 MLIRContext *context, bool enableInit)
807 : OpConversionPattern(typeConverter, context),
808 enableBufferInitialization(enableInit) {}
809
810 LogicalResult
811 matchAndRewrite(tensor::EmptyOp op, OpAdaptor adaptor,
812 ConversionPatternRewriter &rewriter) const override {
813 const auto resType = getSparseTensorType(val: op);
814 if (!resType.hasEncoding())
815 return failure();
816
817 if (!resType.isIdentity()) {
818 return rewriter.notifyMatchFailure(
819 arg&: op, msg: "try run --sparse-reinterpret-map before codegen");
820 }
821
822 Location loc = op.getLoc();
823 // Level size equals to dimension size since lvl2dim map is an identity map.
824 SmallVector<Value> lvlSizesValues;
825 createDimSizes(builder&: rewriter, loc, stt: resType, dynSizes: adaptor.getDynamicSizes(),
826 /*dimSizesValues=*/lvlSizesValues);
827 // Construct allocation for each field.
828 Value sizeHint; // none
829 SmallVector<Value> fields;
830 createAllocFields(builder&: rewriter, loc, stt: resType, enableInit: enableBufferInitialization,
831 sizeHint, lvlSizesValues, fields);
832
833 // Replace operation with resulting memrefs.
834 rewriter.replaceOpWithMultiple(op, newValues: {fields});
835 return success();
836 }
837
838private:
839 bool enableBufferInitialization;
840};
841
842/// Sparse codegen rule for the dealloc operator.
843class SparseTensorDeallocConverter
844 : public OpConversionPattern<bufferization::DeallocTensorOp> {
845public:
846 using Base::Base;
847 SparseTensorDeallocConverter(const TypeConverter &typeConverter,
848 MLIRContext *context, bool createDeallocs)
849 : OpConversionPattern(typeConverter, context),
850 createDeallocs(createDeallocs) {}
851
852 LogicalResult
853 matchAndRewrite(bufferization::DeallocTensorOp op, OneToNOpAdaptor adaptor,
854 ConversionPatternRewriter &rewriter) const override {
855 auto enc = getSparseTensorEncoding(type: op.getTensor().getType());
856 if (!enc)
857 return failure();
858
859 // If user requests not to deallocate sparse tensors, simply erase the
860 // operation.
861 if (createDeallocs) {
862 // Replace the sparse tensor deallocation with field deallocations.
863 Location loc = op.getLoc();
864 auto desc = getDescriptorFromTensorTuple(
865 adaptorValues: adaptor.getTensor(),
866 type: cast<RankedTensorType>(Val: op.getTensor().getType()));
867 for (auto input : desc.getMemRefFields())
868 // Deallocate every buffer used to store the sparse tensor handler.
869 memref::DeallocOp::create(builder&: rewriter, location: loc, memref: input);
870 }
871 rewriter.eraseOp(op);
872 return success();
873 }
874
875private:
876 const bool createDeallocs;
877};
878
879/// Sparse codegen rule for tensor rematerialization.
880class SparseTensorLoadConverter : public OpConversionPattern<LoadOp> {
881public:
882 using Base::Base;
883 LogicalResult
884 matchAndRewrite(LoadOp op, OneToNOpAdaptor adaptor,
885 ConversionPatternRewriter &rewriter) const override {
886 // Prepare descriptor.
887 auto desc = getDescriptorFromTensorTuple(adaptorValues: adaptor.getTensor(),
888 type: op.getTensor().getType());
889 // Generate optional insertion finalization code.
890 if (op.getHasInserts())
891 genEndInsert(builder&: rewriter, loc: op.getLoc(), desc);
892 // Replace operation with resulting memrefs.
893 rewriter.replaceOpWithMultiple(op, newValues: {desc.getFields()});
894 return success();
895 }
896};
897
898/// Sparse codegen rule for the expand op.
899class SparseExpandConverter : public OpConversionPattern<ExpandOp> {
900public:
901 using Base::Base;
902 LogicalResult
903 matchAndRewrite(ExpandOp op, OneToNOpAdaptor adaptor,
904 ConversionPatternRewriter &rewriter) const override {
905 if (!getSparseTensorEncoding(type: op.getTensor().getType()))
906 return failure();
907 Location loc = op->getLoc();
908 auto desc = getDescriptorFromTensorTuple(adaptorValues: adaptor.getTensor(),
909 type: op.getTensor().getType());
910 const auto srcType = getSparseTensorType(val: op.getTensor());
911 Type eltType = srcType.getElementType();
912 Type boolType = rewriter.getIntegerType(width: 1);
913 Type idxType = rewriter.getIndexType();
914 // All initialization should be done on entry of the loop nest.
915 if (isa<BlockArgument>(Val: op.getTensor())) {
916 rewriter.setInsertionPointToStart(op->getBlock());
917 } else {
918 rewriter.setInsertionPointAfter(op.getTensor().getDefiningOp());
919 }
920
921 // Determine the size for access expansion (always the innermost stored
922 // level size).
923 const auto sz = desc.getLvlSize(builder&: rewriter, loc, lvl: srcType.getLvlRank() - 1);
924 // Generate a memref for `sz` elements of type `t`.
925 const auto genAlloc = [&](Type t) {
926 const auto memTp = MemRefType::get(shape: {ShapedType::kDynamic}, elementType: t);
927 return memref::AllocOp::create(builder&: rewriter, location: loc, memrefType: memTp, dynamicSizes: ValueRange{sz});
928 };
929 // Allocate temporary buffers for values/filled-switch and added.
930 // We do not use stack buffers for this, since the expanded size may
931 // be rather large (as it envelops a single expanded dense dimension).
932 Value values = genAlloc(eltType);
933 Value filled = genAlloc(boolType);
934 Value added = genAlloc(idxType);
935 Value zero = constantZero(builder&: rewriter, loc, tp: idxType);
936 // Reset the values/filled-switch to all-zero/false. Note that this
937 // introduces an O(N) operation into the computation, but this reset
938 // operation is amortized over the innermost loops for the access
939 // pattern expansion. As noted in the operation doc, we would like
940 // to amortize this setup cost even between kernels.
941 linalg::FillOp::create(builder&: rewriter, location: loc,
942 inputs: ValueRange{constantZero(builder&: rewriter, loc, tp: eltType)},
943 outputs: ValueRange{values});
944 linalg::FillOp::create(builder&: rewriter, location: loc,
945 inputs: ValueRange{constantZero(builder&: rewriter, loc, tp: boolType)},
946 outputs: ValueRange{filled});
947 // Replace expansion op with these buffers and initial coordinate.
948 assert(op.getNumResults() == 4);
949 rewriter.replaceOp(op, newValues: {values, filled, added, zero});
950 return success();
951 }
952};
953
954/// Sparse codegen rule for the compress operator.
955class SparseCompressConverter : public OpConversionPattern<CompressOp> {
956public:
957 using Base::Base;
958 LogicalResult
959 matchAndRewrite(CompressOp op, OneToNOpAdaptor adaptor,
960 ConversionPatternRewriter &rewriter) const override {
961 Location loc = op->getLoc();
962 SmallVector<Value> fields;
963 auto desc = getMutDescriptorFromTensorTuple(adaptorValues: adaptor.getTensor(), fields,
964 type: op.getTensor().getType());
965 Value values = llvm::getSingleElement(C: adaptor.getValues());
966 Value filled = llvm::getSingleElement(C: adaptor.getFilled());
967 Value added = llvm::getSingleElement(C: adaptor.getAdded());
968 Value count = llvm::getSingleElement(C: adaptor.getCount());
969 const SparseTensorType dstType(desc.getRankedTensorType());
970 Type eltType = dstType.getElementType();
971
972 // If the innermost level is ordered, we need to sort the coordinates
973 // in the "added" array prior to applying the compression.
974 if (dstType.isOrderedLvl(l: dstType.getLvlRank() - 1))
975 SortOp::create(builder&: rewriter, location: loc, n: count, xy: added, ys: ValueRange{},
976 perm_map: rewriter.getMultiDimIdentityMap(rank: 1),
977 ny: rewriter.getIndexAttr(value: 0),
978 algorithm: SparseTensorSortKind::HybridQuickSort);
979 // While performing the insertions, we also need to reset the elements
980 // of the values/filled-switch by only iterating over the set elements,
981 // to ensure that the runtime complexity remains proportional to the
982 // sparsity of the expanded access pattern.
983 //
984 // Generate
985 // out_memrefs = for (i = 0; i < count; i++)(in_memrefs) {
986 // crd = added[i];
987 // value = values[crd];
988 // insert({lvlCoords, crd}, value);
989 // new_memrefs = insert(in_memrefs, {lvlCoords, crd}, value);
990 // values[crd] = 0;
991 // filled[crd] = false;
992 // yield new_memrefs
993 // }
994 scf::ForOp loop = createFor(builder&: rewriter, loc, upper: count, fields: desc.getFields());
995 Value i = loop.getInductionVar();
996
997 Value crd = genLoad(builder&: rewriter, loc, mem: added, idx: i);
998 Value value = genLoad(builder&: rewriter, loc, mem: values, idx: crd);
999 SmallVector<Value> params(desc.getFields().begin(), desc.getFields().end());
1000 SmallVector<Type> flatSpTensorTps = llvm::map_to_vector(
1001 C&: desc.getFields(), F: [](Value v) { return v.getType(); });
1002 SmallVector<Value> flatLvlCoords = flattenValues(values: adaptor.getLvlCoords());
1003 params.append(in_start: flatLvlCoords.begin(), in_end: flatLvlCoords.end());
1004 params.push_back(Elt: crd);
1005 params.push_back(Elt: value);
1006 SparseInsertGenerator insertGen(op.getTensor().getType(), flatSpTensorTps,
1007 params, /*genCall=*/true);
1008 SmallVector<Value> insertRet = insertGen.genCallOrInline(builder&: rewriter, loc);
1009 genStore(builder&: rewriter, loc, val: constantZero(builder&: rewriter, loc, tp: eltType), mem: values, idx: crd);
1010 genStore(builder&: rewriter, loc, val: constantI1(builder&: rewriter, loc, b: false), mem: filled, idx: crd);
1011 scf::YieldOp::create(builder&: rewriter, location: loc, results: insertRet);
1012
1013 rewriter.setInsertionPointAfter(loop);
1014 // Deallocate the buffers on exit of the full loop nest.
1015 Operation *parent = getTop(op);
1016 rewriter.setInsertionPointAfter(parent);
1017 memref::DeallocOp::create(builder&: rewriter, location: loc, memref: values);
1018 memref::DeallocOp::create(builder&: rewriter, location: loc, memref: filled);
1019 memref::DeallocOp::create(builder&: rewriter, location: loc, memref: added);
1020 // Replace operation with resulting memrefs.
1021 rewriter.replaceOpWithMultiple(op, newValues: {loop->getResults()});
1022 return success();
1023 }
1024};
1025
1026/// Sparse codegen rule for the insert operator.
1027class SparseInsertConverter : public OpConversionPattern<tensor::InsertOp> {
1028public:
1029 using Base::Base;
1030 LogicalResult
1031 matchAndRewrite(tensor::InsertOp op, OneToNOpAdaptor adaptor,
1032 ConversionPatternRewriter &rewriter) const override {
1033 auto stt = getSparseTensorType(val: op.getDest());
1034 if (!stt.hasEncoding())
1035 return failure();
1036 assert(stt.isIdentity() && "Run reinterpret-map before conversion.");
1037
1038 Location loc = op.getLoc();
1039 auto desc =
1040 getDescriptorFromTensorTuple(adaptorValues: adaptor.getDest(), type: op.getDest().getType());
1041 TypeRange flatSpTensorTps = desc.getFields().getTypes();
1042 SmallVector<Value> params = llvm::to_vector(Range: desc.getFields());
1043 SmallVector<Value> flatIndices = flattenValues(values: adaptor.getIndices());
1044 params.append(in_start: flatIndices.begin(), in_end: flatIndices.end());
1045 params.push_back(Elt: llvm::getSingleElement(C: adaptor.getScalar()));
1046 SparseInsertGenerator insertGen(op.getDest().getType(), flatSpTensorTps,
1047 params, /*genCall=*/true);
1048 SmallVector<Value> ret = insertGen.genCallOrInline(builder&: rewriter, loc);
1049 // Replace operation with resulting memrefs.
1050 rewriter.replaceOpWithMultiple(op, newValues: {ret});
1051 return success();
1052 }
1053};
1054
1055/// Sparse codegen rule for position accesses.
1056class SparseToPositionsConverter : public OpConversionPattern<ToPositionsOp> {
1057public:
1058 using OpAdaptor = ToPositionsOp::Adaptor;
1059 using OpConversionPattern<ToPositionsOp>::OpConversionPattern;
1060 LogicalResult
1061 matchAndRewrite(ToPositionsOp op, OneToNOpAdaptor adaptor,
1062 ConversionPatternRewriter &rewriter) const override {
1063 // Replace the requested position access with corresponding field.
1064 // The view is restricted to the actual size to ensure clients
1065 // of this operation truly observe size, not capacity!
1066 Location loc = op.getLoc();
1067 Level lvl = op.getLevel();
1068 auto desc = getDescriptorFromTensorTuple(adaptorValues: adaptor.getTensor(),
1069 type: op.getTensor().getType());
1070 auto mem = desc.getPosMemRef(lvl);
1071 auto size = desc.getPosMemSize(builder&: rewriter, loc, lvl);
1072 rewriter.replaceOp(op, newValues: genSliceToSize(builder&: rewriter, loc, mem, sz: size));
1073 return success();
1074 }
1075};
1076
1077/// Sparse codegen rule for accessing the coordinates arrays.
1078class SparseToCoordinatesConverter
1079 : public OpConversionPattern<ToCoordinatesOp> {
1080public:
1081 using OpAdaptor = ToCoordinatesOp::Adaptor;
1082 using OpConversionPattern<ToCoordinatesOp>::OpConversionPattern;
1083 LogicalResult
1084 matchAndRewrite(ToCoordinatesOp op, OneToNOpAdaptor adaptor,
1085 ConversionPatternRewriter &rewriter) const override {
1086 // Replace the requested coordinates access with corresponding field.
1087 // The view is restricted to the actual size to ensure clients
1088 // of this operation truly observe size, not capacity!
1089 Location loc = op.getLoc();
1090 Level lvl = op.getLevel();
1091 auto desc = getDescriptorFromTensorTuple(adaptorValues: adaptor.getTensor(),
1092 type: op.getTensor().getType());
1093 auto mem = desc.getCrdMemRefOrView(builder&: rewriter, loc, lvl);
1094 if (lvl < getSparseTensorType(val: op.getTensor()).getAoSCOOStart()) {
1095 auto size = desc.getCrdMemSize(builder&: rewriter, loc, lvl);
1096 mem = genSliceToSize(builder&: rewriter, loc, mem, sz: size);
1097 }
1098 rewriter.replaceOp(op, newValues: mem);
1099 return success();
1100 }
1101};
1102
1103/// Sparse codegen rule for accessing the linear coordinates buffer.
1104class SparseToCoordinatesBufferConverter
1105 : public OpConversionPattern<ToCoordinatesBufferOp> {
1106public:
1107 using OpAdaptor = ToCoordinatesBufferOp::Adaptor;
1108 using OpConversionPattern<ToCoordinatesBufferOp>::OpConversionPattern;
1109 LogicalResult
1110 matchAndRewrite(ToCoordinatesBufferOp op, OneToNOpAdaptor adaptor,
1111 ConversionPatternRewriter &rewriter) const override {
1112 // Replace the requested coordinates access with corresponding field.
1113 // The view is restricted to the actual size to ensure clients
1114 // of this operation truly observe size, not capacity!
1115 Location loc = op.getLoc();
1116 Level lvl = getSparseTensorType(val: op.getTensor()).getAoSCOOStart();
1117 auto desc = getDescriptorFromTensorTuple(adaptorValues: adaptor.getTensor(),
1118 type: op.getTensor().getType());
1119 auto mem = desc.getAOSMemRef();
1120 auto size = desc.getCrdMemSize(builder&: rewriter, loc, lvl);
1121 rewriter.replaceOp(op, newValues: genSliceToSize(builder&: rewriter, loc, mem, sz: size));
1122 return success();
1123 }
1124};
1125
1126/// Sparse codegen rule for value accesses.
1127class SparseToValuesConverter : public OpConversionPattern<ToValuesOp> {
1128public:
1129 using OpAdaptor = ToValuesOp::Adaptor;
1130 using OpConversionPattern<ToValuesOp>::OpConversionPattern;
1131 LogicalResult
1132 matchAndRewrite(ToValuesOp op, OneToNOpAdaptor adaptor,
1133 ConversionPatternRewriter &rewriter) const override {
1134 // Replace the requested values access with corresponding field.
1135 // The view is restricted to the actual size to ensure clients
1136 // of this operation truly observe size, not capacity!
1137 Location loc = op.getLoc();
1138 auto desc = getDescriptorFromTensorTuple(adaptorValues: adaptor.getTensor(),
1139 type: op.getTensor().getType());
1140 auto mem = desc.getValMemRef();
1141 auto size = desc.getValMemSize(builder&: rewriter, loc);
1142 rewriter.replaceOp(op, newValues: genSliceToSize(builder&: rewriter, loc, mem, sz: size));
1143 return success();
1144 }
1145};
1146
1147/// Sparse codegen rule for the convert operator.
1148class SparseConvertConverter : public OpConversionPattern<ConvertOp> {
1149public:
1150 using Base::Base;
1151 LogicalResult
1152 matchAndRewrite(ConvertOp op, OneToNOpAdaptor adaptor,
1153 ConversionPatternRewriter &rewriter) const override {
1154 SparseTensorEncodingAttr encDst = getSparseTensorEncoding(type: op.getType());
1155 SparseTensorEncodingAttr encSrc =
1156 getSparseTensorEncoding(type: op.getSource().getType());
1157
1158 // If either the source or the destination don't have a valid sparse
1159 // tensor encoding, we should fail to legalize. This should be handled
1160 // by another set of passes before reaching here.
1161 if (!encSrc || !encDst)
1162 return failure();
1163
1164 // The output tensor can not be a slice and those cases should have been
1165 // rejected by ConvertOp::verify() already.
1166 assert(!encDst.isSlice() && "Cannot convert to a sparse tensor slices.");
1167 // Different encoding (except for different bitwidth) should be handled by
1168 // rewriting.
1169 // We need further rewrites if the input tensor is a slice too.
1170 if (encDst.withoutBitWidths() != encSrc.withoutBitWidths() ||
1171 encSrc.isSlice()) {
1172 return failure();
1173 }
1174
1175 Type retElemTp = op.getResult().getType().getElementType();
1176 Type srcElemTp = op.getSource().getType().getElementType();
1177 // Fold the trivial cases.
1178 if (retElemTp == srcElemTp && encDst == encSrc) {
1179 rewriter.replaceOpWithMultiple(op, newValues: {adaptor.getSource()});
1180 return success();
1181 }
1182 //
1183 // Do element-wise type conversion without using InsertOp.
1184 //
1185 // for each memref in srcTensor:
1186 // dst = memref.alloc
1187 // if srcMemRefType != dstMemRefType:
1188 // for every dst[i] = cast(src[i])
1189 // else:
1190 // dst = memref.copy(src)
1191 Location loc = op.getLoc();
1192 auto srcDesc = getDescriptorFromTensorTuple(adaptorValues: adaptor.getSource(),
1193 type: op.getSource().getType());
1194 SmallVector<Value> fields;
1195 foreachFieldAndTypeInSparseTensor(
1196 SparseTensorType(cast<RankedTensorType>(Val: op.getResult().getType())),
1197 [&rewriter, &fields, srcDesc,
1198 loc](Type fTp, FieldIndex fIdx, SparseTensorFieldKind fKind, Level lvl,
1199 LevelType /*lt*/) -> bool {
1200 // Simply reuses the storage specifier as it is an SSA value.
1201 if (fKind == SparseTensorFieldKind::StorageSpec) {
1202 fields.push_back(Elt: srcDesc.getSpecifier());
1203 } else {
1204 // Allocates new memrefs
1205 Value srcMem = srcDesc.getMemRefField(fidx: fIdx);
1206 // TODO: We can instead use the actual memSize in specifier, that
1207 // would require a subViewOp to avoid overflow when copying
1208 // values.
1209 Value sz = linalg::createOrFoldDimOp(b&: rewriter, loc, val: srcMem, dim: 0);
1210 auto dstMem = memref::AllocOp::create(builder&: rewriter, location: loc,
1211 memrefType: cast<MemRefType>(Val&: fTp), dynamicSizes: sz);
1212 if (fTp != srcMem.getType()) {
1213 // Converts elements type.
1214 scf::buildLoopNest(
1215 builder&: rewriter, loc, lbs: constantIndex(builder&: rewriter, loc, i: 0), ubs: sz,
1216 steps: constantIndex(builder&: rewriter, loc, i: 1),
1217 bodyBuilder: [srcMem, &dstMem](OpBuilder &builder, Location loc,
1218 ValueRange ivs) {
1219 Value v = memref::LoadOp::create(builder, location: loc, memref: srcMem, indices: ivs);
1220 Value casted = genCast(builder, loc, value: v,
1221 dstTy: dstMem.getType().getElementType());
1222 memref::StoreOp::create(builder, location: loc, valueToStore: casted, memref: dstMem, indices: ivs);
1223 });
1224 } else {
1225 // TODO: We can even reuse the same memref for the new tensor,
1226 // but that requires a `ref-counting` based memory management
1227 // for shared memrefs between multiple sparse tensors.
1228 memref::CopyOp::create(builder&: rewriter, location: loc, source: srcMem, target: dstMem);
1229 }
1230 fields.push_back(Elt: dstMem);
1231 }
1232 return true;
1233 });
1234
1235 rewriter.replaceOpWithMultiple(op, newValues: {fields});
1236 return success();
1237 }
1238};
1239
1240class SparseExtractSliceConverter
1241 : public OpConversionPattern<tensor::ExtractSliceOp> {
1242public:
1243 using Base::Base;
1244 LogicalResult
1245 matchAndRewrite(tensor::ExtractSliceOp op, OneToNOpAdaptor adaptor,
1246 ConversionPatternRewriter &rewriter) const override {
1247 Location loc = op.getLoc();
1248 MLIRContext *ctx = op.getContext();
1249 auto srcEnc = getSparseTensorEncoding(type: op.getSourceType());
1250 auto dstEnc = getSparseTensorEncoding(type: op.getResult().getType());
1251 // TODO: We should check these in ExtractSliceOp::verify.
1252 if (!srcEnc || !dstEnc || !dstEnc.isSlice())
1253 return failure();
1254 assert(srcEnc.withoutDimSlices() == dstEnc.withoutDimSlices());
1255
1256 SmallVector<Value> fields;
1257 auto desc = getMutDescriptorFromTensorTuple(adaptorValues: adaptor.getSource(), fields,
1258 type: op.getSource().getType());
1259
1260 auto newSpec = StorageSpecifierInitOp::create(
1261 builder&: rewriter, location: loc, result: StorageSpecifierType::get(context: ctx, encoding: dstEnc),
1262 source: desc.getSpecifier());
1263 desc.setSpecifier(newSpec);
1264
1265 // Fills in slice information.
1266 for (auto [idx, offset, size, stride] : llvm::enumerate(
1267 First: op.getMixedOffsets(), Rest: op.getMixedSizes(), Rest: op.getMixedStrides())) {
1268 Dimension dim = idx;
1269
1270 Value offsetV = getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: offset);
1271 Value sizeV = getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: size);
1272 Value strideV = getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: stride);
1273 // TODO: We could probably only set dynamic value here. But it would
1274 // requires us to fill the hole when casting a static slice to dynamic
1275 // slice.
1276 desc.setSpecifierField(builder&: rewriter, loc, kind: StorageSpecifierKind::DimOffset,
1277 lvl: dim, v: offsetV);
1278
1279 // FIXME: we need to distinguish level sizes and dimension size for slices
1280 // here. Maybe we should store slice level sizes in a different array
1281 // instead of reusing it.
1282 assert(srcEnc.isIdentity());
1283 desc.setSpecifierField(builder&: rewriter, loc, kind: StorageSpecifierKind::LvlSize, lvl: dim,
1284 v: sizeV);
1285 desc.setSpecifierField(builder&: rewriter, loc, kind: StorageSpecifierKind::DimStride,
1286 lvl: dim, v: strideV);
1287 }
1288
1289 // NOTE: we can not generate tuples directly from descriptor here, as the
1290 // descriptor is holding the original type, yet we want the slice type
1291 // here (they shared every memref but with an updated specifier).
1292 rewriter.replaceOpWithMultiple(op, newValues: {desc.getFields()});
1293 return success();
1294 }
1295};
1296
1297/// Sparse codegen rule for number of entries operator.
1298class SparseNumberOfEntriesConverter
1299 : public OpConversionPattern<NumberOfEntriesOp> {
1300public:
1301 using Base::Base;
1302 LogicalResult
1303 matchAndRewrite(NumberOfEntriesOp op, OneToNOpAdaptor adaptor,
1304 ConversionPatternRewriter &rewriter) const override {
1305 // Query memSizes for the actually stored values.
1306 // FIXME: the nse value computed in this way might be wrong when there is
1307 // any "loose_compressed" level.
1308 auto desc = getDescriptorFromTensorTuple(adaptorValues: adaptor.getTensor(),
1309 type: op.getTensor().getType());
1310 rewriter.replaceOp(op, newValues: desc.getValMemSize(builder&: rewriter, loc: op.getLoc()));
1311 return success();
1312 }
1313};
1314
1315struct SparseAssembleOpConverter : public OpConversionPattern<AssembleOp> {
1316 using Base::Base;
1317 LogicalResult
1318 matchAndRewrite(AssembleOp op, OpAdaptor adaptor,
1319 ConversionPatternRewriter &rewriter) const override {
1320 Location loc = op.getLoc();
1321 const auto stt = getSparseTensorType(val: op.getResult());
1322
1323 SmallVector<Value> fields;
1324
1325 foreachFieldAndTypeInSparseTensor(
1326 stt,
1327 [&rewriter, &fields, &op, &stt,
1328 loc](Type fType, FieldIndex fIdx, SparseTensorFieldKind fKind,
1329 Level /*lvl*/, LevelType lt) -> bool {
1330 assert(fields.size() == fIdx);
1331 if (fKind == SparseTensorFieldKind::StorageSpec) {
1332 fields.push_back(
1333 Elt: SparseTensorSpecifier::getInitValue(builder&: rewriter, loc, stt));
1334 } else {
1335 // Else simply takes the inputs.
1336 Value tensor = fKind == SparseTensorFieldKind::ValMemRef
1337 ? op.getValues()
1338 : op.getLevels()[fIdx];
1339 // TODO: handle batch.
1340 TypedValue<BaseMemRefType> mem = genToMemref(builder&: rewriter, loc, tensor);
1341 if (mem.getType().getRank() > stt.getBatchLvlRank() + 1) {
1342 // Flattens the buffer to batchLvlRank.
1343 auto reassoc = getReassociationForFlattening(
1344 srcTp: mem.getType(), batchLvls: stt.getBatchLvlRank());
1345 mem = memref::CastOp::create(
1346 builder&: rewriter, location: loc, dest: fType,
1347 source: memref::CollapseShapeOp::create(builder&: rewriter, location: loc, src: mem, reassociation: reassoc));
1348 } else {
1349 mem = memref::CastOp::create(builder&: rewriter, location: loc, dest: fType, source: mem);
1350 }
1351 fields.push_back(Elt: mem);
1352 }
1353 return true;
1354 });
1355
1356 MutSparseTensorDescriptor desc(stt, fields);
1357 Value c0 = constantIndex(builder&: rewriter, loc, i: 0);
1358 Value c1 = constantIndex(builder&: rewriter, loc, i: 1);
1359 Value c2 = constantIndex(builder&: rewriter, loc, i: 2);
1360 Value posBack = c0; // index to the last value in the position array
1361 Value memSize = c1; // memory size for current array
1362
1363 Level trailCOOStart = stt.getAoSCOOStart();
1364 Level trailCOORank = stt.getLvlRank() - trailCOOStart;
1365 // Sets up SparseTensorSpecifier.
1366 for (Level lvl = 0, lvlRank = stt.getLvlRank(); lvl < lvlRank; lvl++) {
1367 assert(ShapedType::isStatic(stt.getLvlShape()[lvl]));
1368
1369 // Sets up the level size.
1370 auto lvlSize = constantIndex(builder&: rewriter, loc, i: stt.getLvlShape()[lvl]);
1371 desc.setLvlSize(builder&: rewriter, loc, lvl, v: lvlSize);
1372 // We use a single AOS array to store the trailing COO, so there is only
1373 // one memory size to set for the entire COO section.
1374 if (lvl > trailCOOStart)
1375 continue;
1376
1377 // Sets up the memory size by reading the last value in position array.
1378 LevelType lt = stt.getLvlType(l: lvl);
1379 // Simply forwards the position index when this is a dense level.
1380 if (lt.isa<LevelFormat::Dense>()) {
1381 memSize = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: lvlSize, rhs: memSize);
1382 posBack = arith::SubIOp::create(builder&: rewriter, location: loc, lhs: memSize, rhs: c1);
1383 continue;
1384 }
1385 if (lt.isa<LevelFormat::Batch>()) {
1386 // Skips batch levels as it is not linearized.
1387 // FIXME: this assumes that every batch has the same number of nse, need
1388 // to be generalized to handle varied-size batches.
1389 continue;
1390 }
1391
1392 if (isWithPosLT(lt)) {
1393 assert(isCompressedLT(lt) || isLooseCompressedLT(lt));
1394 if (isLooseCompressedLT(lt)) {
1395 memSize = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: memSize, rhs: c2);
1396 posBack = arith::SubIOp::create(builder&: rewriter, location: loc, lhs: memSize, rhs: c1);
1397 } else {
1398 assert(isCompressedLT(lt));
1399 posBack = memSize;
1400 memSize = arith::AddIOp::create(builder&: rewriter, location: loc, lhs: memSize, rhs: c1);
1401 }
1402 desc.setPosMemSize(builder&: rewriter, loc, lvl, v: memSize);
1403 // The last value in position array is the memory size for next level.
1404 // FIXME: this assumes that every batch has the same number of nse, need
1405 // to be generalized to handle varied-size batches.
1406 SmallVector<Value> batched(stt.getBatchLvlRank(),
1407 constantIndex(builder&: rewriter, loc, i: 0));
1408 batched.push_back(Elt: posBack);
1409 memSize = genIndexLoad(builder&: rewriter, loc, mem: desc.getPosMemRef(lvl), s: batched);
1410 posBack = arith::SubIOp::create(builder&: rewriter, location: loc, lhs: posBack, rhs: c1);
1411 }
1412 assert(isWithCrdLT(lt) && lvl <= trailCOOStart);
1413 // FIXME: This seems to be unnecessarily complex, can we simplify it?
1414 if (lvl == trailCOOStart) {
1415 Value cooSz = arith::MulIOp::create(
1416 builder&: rewriter, location: loc, lhs: memSize, rhs: constantIndex(builder&: rewriter, loc, i: trailCOORank));
1417 desc.setCrdMemSize(builder&: rewriter, loc, lvl, v: cooSz);
1418 } else {
1419 desc.setCrdMemSize(builder&: rewriter, loc, lvl, v: memSize);
1420 }
1421 }
1422 desc.setValMemSize(builder&: rewriter, loc, v: memSize);
1423
1424 rewriter.replaceOpWithMultiple(op, newValues: {desc.getFields()});
1425 return success();
1426 }
1427};
1428
1429struct SparseDisassembleOpConverter
1430 : public OpConversionPattern<DisassembleOp> {
1431 using Base::Base;
1432 SparseDisassembleOpConverter(const TypeConverter &typeConverter,
1433 MLIRContext *context)
1434 : OpConversionPattern(typeConverter, context) {}
1435
1436 LogicalResult
1437 matchAndRewrite(DisassembleOp op, OneToNOpAdaptor adaptor,
1438 ConversionPatternRewriter &rewriter) const override {
1439 auto desc = getDescriptorFromTensorTuple(adaptorValues: adaptor.getTensor(),
1440 type: op.getTensor().getType());
1441 Location loc = op.getLoc();
1442 SmallVector<Value> retMem;
1443 SmallVector<Value> retLen;
1444 desc.getLayout().foreachField([desc, loc, &rewriter, &op, &retMem,
1445 &retLen](FieldIndex fid,
1446 SparseTensorFieldKind fKind,
1447 Level lvl, LevelType lt) -> bool {
1448 if (fKind == SparseTensorFieldKind::StorageSpec)
1449 return true;
1450 SparseTensorType stt(desc.getRankedTensorType());
1451 Value sz, src;
1452 TypedValue<BaseMemRefType> dst;
1453 if (fKind == SparseTensorFieldKind::ValMemRef) {
1454 sz = desc.getValMemSize(builder&: rewriter, loc);
1455 src = desc.getValMemRef();
1456 dst = genToMemref(builder&: rewriter, loc, tensor: op.getOutValues());
1457
1458 retMem.push_back(Elt: dst);
1459 Type valLenTp = op.getValLen().getType();
1460 retLen.push_back(Elt: genScalarToTensor(builder&: rewriter, loc, elem: sz, dstTp: valLenTp));
1461 } else {
1462 assert(fKind == SparseTensorFieldKind::PosMemRef ||
1463 fKind == SparseTensorFieldKind::CrdMemRef);
1464
1465 sz = fKind == SparseTensorFieldKind::PosMemRef
1466 ? desc.getPosMemSize(builder&: rewriter, loc, lvl)
1467 : desc.getCrdMemSize(builder&: rewriter, loc, lvl);
1468 src = desc.getMemRefField(fidx: fid);
1469 dst = genToMemref(builder&: rewriter, loc, tensor: op.getOutLevels()[fid]);
1470 retMem.push_back(Elt: dst);
1471 // Retrieves the corresponding level length type.
1472 Type lvlLenTp = op.getLvlLens().getTypes()[retLen.size()];
1473 retLen.push_back(Elt: genScalarToTensor(builder&: rewriter, loc, elem: sz, dstTp: lvlLenTp));
1474 }
1475 Value flatOut = dst;
1476 if (dst.getType().getRank() > stt.getBatchLvlRank() + 1) {
1477 auto reassoc =
1478 getReassociationForFlattening(srcTp: dst.getType(), batchLvls: stt.getBatchLvlRank());
1479 flatOut = memref::CollapseShapeOp::create(builder&: rewriter, location: loc, src: dst, reassociation: reassoc);
1480 }
1481 Value dstMem = genSliceToSize(builder&: rewriter, loc, mem: flatOut, sz);
1482 Value srcMem = genSliceToSize(builder&: rewriter, loc, mem: src, sz);
1483 memref::CopyOp::create(builder&: rewriter, location: loc, source: srcMem, target: dstMem);
1484 return true;
1485 });
1486
1487 // Converts MemRefs back to Tensors.
1488 SmallVector<Value> retValues =
1489 llvm::map_to_vector(C&: retMem, F: [&rewriter, loc](Value v) -> Value {
1490 return bufferization::ToTensorOp::create(
1491 builder&: rewriter, location: loc, result: memref::getTensorTypeFromMemRefType(type: v.getType()),
1492 buffer: v);
1493 });
1494 // Appends the actual memory length used in each buffer returned.
1495 retValues.append(in_start: retLen.begin(), in_end: retLen.end());
1496 rewriter.replaceOp(op, newValues: retValues);
1497 return success();
1498 }
1499};
1500
1501struct SparseNewConverter : public OpConversionPattern<NewOp> {
1502 using Base::Base;
1503 LogicalResult
1504 matchAndRewrite(NewOp op, OpAdaptor adaptor,
1505 ConversionPatternRewriter &rewriter) const override {
1506 Location loc = op.getLoc();
1507 const auto dstTp = getSparseTensorType(val: op.getResult());
1508 // Creating COO with NewOp is handled by direct IR codegen. All other cases
1509 // are handled by rewriting.
1510 if (!dstTp.hasEncoding() || dstTp.getAoSCOOStart() != 0)
1511 return failure();
1512
1513 // Implement as follows:
1514 // %reader = @createCheckedSparseTensorReader(%filename)
1515 // %nse = @getSparseTensorNSE(%reader)
1516 // %coo = bufferization.alloc_tensor an ordered COO with
1517 // dst dim ordering, size_hint = %nse
1518 // %coordinates = sparse_tensor.coordinates_buffer(%coo)
1519 // %values = sparse_tensor.values(%coo)
1520 // %isSorted = @sparseTensorReaderReadToBuffers(%coordinates, %values)
1521 // if (! %isSorted) sparse_tensor.sort_coo(%nse, %coordinates, %values)
1522 // update storage specifier
1523 // @delSparseTensorReader(%reader)
1524 SmallVector<Value> dimSizesValues;
1525 Value dimSizesBuffer;
1526 Value reader = genReader(builder&: rewriter, loc, stt: dstTp, tensor: adaptor.getOperands()[0],
1527 dimSizesValues, dimSizesBuffer);
1528
1529 // Get the number of stored entries.
1530 const Type indexTp = rewriter.getIndexType();
1531 Value nse = createFuncCall(builder&: rewriter, loc, name: "getSparseTensorReaderNSE",
1532 resultType: {indexTp}, operands: {reader}, emitCInterface: EmitCInterface::Off)
1533 .getResult(i: 0);
1534
1535 // Construct the lvl sizes and the dim2lvl/lvl2dim buffers.
1536 SmallVector<Value> lvlSizesValues;
1537 Value dim2lvlBuffer;
1538 Value lvl2dimBuffer;
1539 genMapBuffers(builder&: rewriter, loc, stt: dstTp, dimSizesValues, dimSizesBuffer,
1540 lvlSizesValues, dim2lvlBuffer, lvl2dimBuffer);
1541
1542 // Construct allocation for each field.
1543 Value sizeHint = nse;
1544 SmallVector<Value> fields;
1545 createAllocFields(builder&: rewriter, loc, stt: dstTp, /*enableInit=*/false, sizeHint,
1546 lvlSizesValues, fields);
1547
1548 // Read the COO tensor data.
1549 MutSparseTensorDescriptor desc(dstTp, fields);
1550 Value xs = desc.getAOSMemRef();
1551 Value ys = desc.getValMemRef();
1552 const Type boolTp = rewriter.getIntegerType(width: 1);
1553 const Type elemTp = dstTp.getElementType();
1554 const Type crdTp = dstTp.getCrdType();
1555 SmallString<32> readToBuffersFuncName{"getSparseTensorReaderReadToBuffers",
1556 overheadTypeFunctionSuffix(overheadTp: crdTp),
1557 primaryTypeFunctionSuffix(elemTp)};
1558 Value isSorted =
1559 createFuncCall(builder&: rewriter, loc, name: readToBuffersFuncName, resultType: {boolTp},
1560 operands: {reader, dim2lvlBuffer, lvl2dimBuffer, xs, ys},
1561 emitCInterface: EmitCInterface::On)
1562 .getResult(i: 0);
1563
1564 // If the destination tensor is a sorted COO, we need to sort the COO tensor
1565 // data if the input elements aren't sorted yet.
1566 const Level lvlRank = dstTp.getLvlRank();
1567 if (dstTp.isOrderedLvl(l: lvlRank - 1)) {
1568 Value kFalse = constantI1(builder&: rewriter, loc, b: false);
1569 Value notSorted = arith::CmpIOp::create(
1570 builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::eq, lhs: isSorted, rhs: kFalse);
1571 scf::IfOp ifOp =
1572 scf::IfOp::create(builder&: rewriter, location: loc, cond: notSorted, /*else*/ withElseRegion: false);
1573 rewriter.setInsertionPointToStart(&ifOp.getThenRegion().front());
1574 auto xPerm = rewriter.getMultiDimIdentityMap(rank: lvlRank);
1575 SortOp::create(builder&: rewriter, location: loc, n: nse, xy: xs, ys: ValueRange{ys}, perm_map: xPerm,
1576 ny: rewriter.getIndexAttr(value: 0),
1577 algorithm: SparseTensorSortKind::HybridQuickSort);
1578 rewriter.setInsertionPointAfter(ifOp);
1579 }
1580
1581 // Set PosMemRef0[1] = nse.
1582 const Value c1 = constantIndex(builder&: rewriter, loc, i: 1);
1583 const Value posMemref0 = desc.getPosMemRef(lvl: 0);
1584 const Type posTp = dstTp.getPosType();
1585 const Value posNse = genCast(builder&: rewriter, loc, value: nse, dstTy: posTp);
1586 memref::StoreOp::create(builder&: rewriter, location: loc, valueToStore: posNse, memref: posMemref0, indices: c1);
1587
1588 // Update storage specifier.
1589 Value coordinatesSize = arith::MulIOp::create(
1590 builder&: rewriter, location: loc, lhs: nse, rhs: constantIndex(builder&: rewriter, loc, i: lvlRank));
1591 desc.setSpecifierField(builder&: rewriter, loc, kind: StorageSpecifierKind::CrdMemSize, lvl: 0,
1592 v: coordinatesSize);
1593 desc.setSpecifierField(builder&: rewriter, loc, kind: StorageSpecifierKind::ValMemSize,
1594 lvl: std::nullopt, v: nse);
1595
1596 // Release the sparse tensor reader.
1597 createFuncCall(builder&: rewriter, loc, name: "delSparseTensorReader", resultType: {}, operands: {reader},
1598 emitCInterface: EmitCInterface::Off);
1599
1600 // Replace operation with resulting memrefs.
1601 rewriter.replaceOpWithMultiple(op, newValues: {fields});
1602 return success();
1603 }
1604};
1605
1606struct SparseHasRuntimeLibraryConverter
1607 : public OpConversionPattern<HasRuntimeLibraryOp> {
1608 using Base::Base;
1609 LogicalResult
1610 matchAndRewrite(HasRuntimeLibraryOp op, OpAdaptor adaptor,
1611 ConversionPatternRewriter &rewriter) const override {
1612 auto i1Type = rewriter.getI1Type();
1613 rewriter.replaceOpWithNewOp<arith::ConstantOp>(
1614 op, args&: i1Type, args: rewriter.getIntegerAttr(type: i1Type, value: 0));
1615 return success();
1616 }
1617};
1618
1619} // namespace
1620
1621//===----------------------------------------------------------------------===//
1622// Public method for populating conversion rules.
1623//===----------------------------------------------------------------------===//
1624
1625/// Populates the given patterns list with conversion rules required for
1626/// the sparsification of linear algebra operations.
1627void mlir::populateSparseTensorCodegenPatterns(
1628 const TypeConverter &typeConverter, RewritePatternSet &patterns,
1629 bool createSparseDeallocs, bool enableBufferInitialization) {
1630 patterns.add<
1631 SparseAssembleOpConverter, SparseDisassembleOpConverter,
1632 SparseReturnConverter, SparseCallConverter, SparseLvlOpConverter,
1633 SparseCastConverter, SparseExtractSliceConverter,
1634 SparseTensorLoadConverter, SparseExpandConverter, SparseCompressConverter,
1635 SparseInsertConverter, SparseReorderCOOConverter, SparseReMapConverter,
1636 SparseSliceGetterOpConverter<ToSliceOffsetOp,
1637 StorageSpecifierKind::DimOffset>,
1638 SparseSliceGetterOpConverter<ToSliceStrideOp,
1639 StorageSpecifierKind::DimStride>,
1640 SparseToPositionsConverter, SparseToCoordinatesConverter,
1641 SparseToCoordinatesBufferConverter, SparseToValuesConverter,
1642 SparseConvertConverter, SparseNewConverter,
1643 SparseNumberOfEntriesConverter, SparseHasRuntimeLibraryConverter>(
1644 arg: typeConverter, args: patterns.getContext());
1645 patterns.add<SparseTensorDeallocConverter>(
1646 arg: typeConverter, args: patterns.getContext(), args&: createSparseDeallocs);
1647 patterns.add<SparseTensorAllocConverter, SparseTensorEmptyConverter>(
1648 arg: typeConverter, args: patterns.getContext(), args&: enableBufferInitialization);
1649}
1650