1//===- SparseTensorRewriting.cpp - Sparse tensor rewriting rules ----------===//
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// This file implements rewriting rules that are specific to sparse tensors.
10//
11//===----------------------------------------------------------------------===//
12
13#include "Utils/CodegenUtils.h"
14#include "Utils/LoopEmitter.h"
15
16#include "mlir/Dialect/Affine/IR/AffineOps.h"
17#include "mlir/Dialect/Arith/IR/Arith.h"
18#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
19#include "mlir/Dialect/Linalg/IR/Linalg.h"
20#include "mlir/Dialect/Linalg/Utils/Utils.h"
21#include "mlir/Dialect/MemRef/IR/MemRef.h"
22#include "mlir/Dialect/SCF/IR/SCF.h"
23#include "mlir/Dialect/SparseTensor/IR/SparseTensor.h"
24#include "mlir/Dialect/SparseTensor/IR/SparseTensorStorageLayout.h"
25#include "mlir/Dialect/SparseTensor/IR/SparseTensorType.h"
26#include "mlir/Dialect/SparseTensor/Transforms/Passes.h"
27#include "mlir/Dialect/Tensor/IR/Tensor.h"
28#include "mlir/Dialect/Vector/IR/VectorOps.h"
29#include "mlir/IR/AffineMap.h"
30#include "mlir/IR/Matchers.h"
31#include "mlir/Support/LLVM.h"
32
33using namespace mlir;
34using namespace mlir::bufferization;
35using namespace mlir::linalg;
36using namespace mlir::sparse_tensor;
37
38//===---------------------------------------------------------------------===//
39// Helper methods for the actual rewriting rules.
40//===---------------------------------------------------------------------===//
41
42// Helper to detect a sparse tensor type operand.
43static bool isSparseTensor(Value v) {
44 auto enc = getSparseTensorEncoding(type: v.getType());
45 return enc && !llvm::all_of(Range: enc.getLvlTypes(),
46 P: [](auto lt) { return lt == LevelFormat::Dense; });
47}
48static bool isSparseTensor(OpOperand *op) { return isSparseTensor(v: op->get()); }
49
50// Helper method to find zero/uninitialized tensor materialization.
51static bool isMaterializing(OpOperand *op, bool isZero) {
52 Value val = op->get();
53 // Check allocation, with zero alloc when required.
54 if (auto alloc = val.getDefiningOp<AllocTensorOp>()) {
55 Value copy = alloc.getCopy();
56 if (isZero)
57 return copy && isZeroIntegerOrFloat(v: copy);
58 return !copy;
59 }
60 // Check for empty tensor materialization.
61 if (auto empty = val.getDefiningOp<tensor::EmptyOp>())
62 return !isZero;
63 // Last resort for zero alloc: the whole value is zero.
64 return isZero && isZeroIntegerOrFloat(v: val);
65}
66
67// Helper to detect sampling operation.
68static bool isSampling(GenericOp op) {
69 auto yieldOp = cast<linalg::YieldOp>(Val: op.getRegion().front().getTerminator());
70 if (auto *def = yieldOp.getOperand(i: 0).getDefiningOp()) {
71 if (isa<arith::MulFOp>(Val: def) || isa<arith::MulIOp>(Val: def)) {
72 // Both scalar input arguments used exactly once.
73 Value s1 = op.getBlock()->getArgument(i: 0);
74 Value s2 = op.getBlock()->getArgument(i: 1);
75 return (def->getOperand(idx: 0) == s1 && def->getOperand(idx: 1) == s2) ||
76 (def->getOperand(idx: 1) == s1 && def->getOperand(idx: 0) == s2);
77 }
78 }
79 return false;
80}
81
82// Helper to detect chain of multiplications that do not involve x.
83static bool isMulChain(Value val, Value x) {
84 if (auto arg = dyn_cast<BlockArgument>(Val&: val))
85 return arg != x;
86 if (auto *def = val.getDefiningOp()) {
87 if (isa<arith::MulFOp>(Val: def) || isa<arith::MulIOp>(Val: def))
88 return isMulChain(val: def->getOperand(idx: 0), x) &&
89 isMulChain(val: def->getOperand(idx: 1), x);
90 }
91 return false;
92}
93
94// Helper to detect x = x + <multiplications>.
95static bool isSumOfMul(GenericOp op) {
96 auto yieldOp = cast<linalg::YieldOp>(Val: op.getRegion().front().getTerminator());
97 if (auto *def = yieldOp.getOperand(i: 0).getDefiningOp()) {
98 if (isa<arith::AddFOp>(Val: def) || isa<arith::AddIOp>(Val: def)) {
99 Value x = op.getBlock()->getArguments().back();
100 return (def->getOperand(idx: 0) == x && isMulChain(val: def->getOperand(idx: 1), x)) ||
101 (def->getOperand(idx: 1) == x && isMulChain(val: def->getOperand(idx: 0), x));
102 }
103 }
104 return false;
105}
106
107// Helper to detect direct yield of a zero value.
108static bool isZeroYield(GenericOp op) {
109 auto yieldOp = cast<linalg::YieldOp>(Val: op.getRegion().front().getTerminator());
110 if (auto arg = dyn_cast<BlockArgument>(Val: yieldOp.getOperand(i: 0))) {
111 if (arg.getOwner()->getParentOp() == op) {
112 return isZeroIntegerOrFloat(v: op->getOperand(idx: arg.getArgNumber()));
113 }
114 }
115 return isZeroIntegerOrFloat(v: yieldOp.getOperand(i: 0));
116}
117
118/// Populates given sizes array from type (for static sizes) and from
119/// the tensor (for dynamic sizes).
120static void sizesForTensor(OpBuilder &builder, SmallVectorImpl<Value> &sizes,
121 Location loc, ShapedType stp, Value tensor) {
122 for (const auto &d : enumerate(First: stp.getShape())) {
123 Value dim;
124 if (d.value() == ShapedType::kDynamic)
125 dim = tensor::DimOp::create(builder, location: loc, source: tensor, index: d.index());
126 else
127 dim = constantIndex(builder, loc, i: d.value());
128 sizes.push_back(Elt: dim);
129 }
130}
131
132static RankedTensorType getBufferType(const SparseTensorType &stt,
133 bool needTmpCOO) {
134 return needTmpCOO ? stt.getCOOType(/*ordered=*/false)
135 : stt.getRankedTensorType();
136}
137
138/// Collects the dynamic dimension sizes for `tp` with the assumption that
139/// `sizes` are the dimension sizes for the type. Stores the dynamic dimension
140/// sizes to dynSizes.
141static void getDynamicSizes(RankedTensorType tp, ValueRange sizes,
142 SmallVectorImpl<Value> &dynSizes) {
143 for (const auto &d : enumerate(First: tp.getShape())) {
144 if (d.value() == ShapedType::kDynamic)
145 dynSizes.push_back(Elt: sizes[d.index()]);
146 }
147}
148
149static LogicalResult genForeachOnSparseConstant(ForeachOp op,
150 RewriterBase &rewriter,
151 SparseElementsAttr attr) {
152 auto loc = op.getLoc();
153 SmallVector<Value> reduc = op.getInitArgs();
154
155 // Foreach on constant.
156 foreachInSparseConstant(
157 builder&: rewriter, loc, attr, order: op.getOrder().value_or(u: AffineMap()),
158 callback: [&reduc, &rewriter, op](ArrayRef<Value> cvs, Value v) mutable {
159 SmallVector<Value> args;
160 args.append(in_start: cvs.begin(), in_end: cvs.end());
161 args.push_back(Elt: v);
162 args.append(RHS: reduc);
163 // Clones the foreach op to get a copy of the loop body.
164 auto cloned = cast<ForeachOp>(Val: rewriter.clone(op&: *op.getOperation()));
165 assert(args.size() == cloned.getBody()->getNumArguments());
166 Operation *yield = cloned.getBody()->getTerminator();
167 rewriter.inlineBlockBefore(source: cloned.getBody(), op, argValues: args);
168 // clean up
169 rewriter.eraseOp(op: cloned);
170 reduc = yield->getOperands();
171 rewriter.eraseOp(op: yield);
172 });
173
174 rewriter.replaceOp(op, newValues: reduc);
175 return success();
176}
177
178/// Populates the given sizes array for concatenation from types (for static
179/// sizes) and from the source tensors (for dynamic sizes).
180static void concatSizesFromInputs(OpBuilder &builder,
181 SmallVectorImpl<Value> &sizes, Location loc,
182 ShapedType dstTp, ValueRange srcs,
183 unsigned dim) {
184 auto dstShape = dstTp.getShape();
185 sizesFromSrc(builder, sizes, loc, src: srcs[0]);
186
187 // Sum up on the `dim` if the dimension is dynamic.
188 if (dstShape[dim] != ShapedType::kDynamic) {
189 // Faithfully take the static size.
190 sizes[dim] = constantIndex(builder, loc, i: dstShape[dim]);
191 } else {
192 // Else, compute the shape dynamically.
193 for (const auto &src : srcs.drop_front()) {
194 Value srcSz = linalg::createOrFoldDimOp(b&: builder, loc, val: src, dim);
195 // Sum up all the sizes.
196 sizes[dim] = arith::AddIOp::create(builder, location: loc, lhs: sizes[dim], rhs: srcSz);
197 }
198 }
199}
200
201//===---------------------------------------------------------------------===//
202// The actual sparse tensor rewriting rules.
203//===---------------------------------------------------------------------===//
204
205namespace {
206
207/// TODO: move it to tensor dialect instead.
208///
209/// Fold `tensor.concat` and `tensor.extract_slice`
210///
211/// %concat = tensor.concat dim(2) %t0, %t1
212/// : (tensor<1x64x1xf32>, tensor<1x64x1xf32>) -> tensor<1x64x2xf32>
213/// %extracted0 = tensor.extract_slice %concat[0, 0, 0][1, 64, 1][1, 1, 1]
214/// : tensor<1x64x2xf32> to tensor<1x64x1xf32>
215/// %extracted1 = tensor.extract_slice %concat[0, 0, 1][1, 64, 1][1, 1, 1]
216/// : tensor<1x64x2xf32> to tensor<1x64x1xf32>
217///
218/// Becomes
219///
220/// %extract0, %extract1 = %t0, %t1
221struct FuseExtractSliceWithConcat
222 : public OpRewritePattern<tensor::ExtractSliceOp> {
223 using OpRewritePattern<tensor::ExtractSliceOp>::OpRewritePattern;
224
225 LogicalResult matchAndRewrite(tensor::ExtractSliceOp extractOp,
226 PatternRewriter &rewriter) const override {
227 auto concatOp = extractOp.getSource().getDefiningOp<tensor::ConcatOp>();
228 if (!concatOp)
229 return failure();
230
231 Location loc = extractOp.getLoc();
232 int64_t dim = concatOp.getDim();
233 int64_t rank = extractOp.getResultType().getRank();
234
235 SmallVector<OpFoldResult> srcStrides(rank, rewriter.getIndexAttr(value: 1));
236 SmallVector<OpFoldResult> srcOffsets(rank, rewriter.getIndexAttr(value: 0));
237
238 // Compute the partial sums for the slice offsets.
239 AffineExpr sum = rewriter.getAffineDimExpr(position: 0);
240 SmallVector<AffineExpr> partialSums = {sum};
241 SmallVector<OpFoldResult> offsetStrides = {rewriter.getIndexAttr(value: 0)};
242 for (auto [idx, input] :
243 llvm::enumerate(First: concatOp.getInputs().drop_back())) {
244 sum = sum + rewriter.getAffineDimExpr(position: idx + 1);
245 partialSums.push_back(Elt: sum);
246 offsetStrides.push_back(
247 Elt: rewriter.createOrFold<tensor::DimOp>(location: loc, args&: input, args&: dim));
248 }
249 auto partialSumMap = AffineMap::get(dimCount: concatOp.getInputs().size(), symbolCount: 0,
250 results: partialSums, context: rewriter.getContext());
251 SmallVector<OpFoldResult> dimOffsets =
252 affine::makeComposedFoldedMultiResultAffineApply(
253 b&: rewriter, loc, map: partialSumMap, operands: offsetStrides);
254
255 auto allEqual = [](ArrayRef<OpFoldResult> lhs, ArrayRef<OpFoldResult> rhs) {
256 for (auto [l, r] : llvm::zip(t&: lhs, u&: rhs)) {
257 std::optional<int64_t> staticVal = getConstantIntValue(ofr: l);
258 if (!staticVal.has_value() || staticVal != getConstantIntValue(ofr: r))
259 return false;
260 }
261 return lhs.size() == rhs.size();
262 };
263
264 for (auto [i, input, offset] :
265 llvm::enumerate(First: concatOp.getInputs(), Rest&: dimOffsets)) {
266 SmallVector<OpFoldResult> srcSizes =
267 tensor::getMixedSizes(builder&: rewriter, loc, value: input);
268 srcOffsets[dim] = offset;
269
270 SmallVector<OpFoldResult> dstSizes = extractOp.getMixedSizes();
271 SmallVector<OpFoldResult> dstOffsets = extractOp.getMixedOffsets();
272 SmallVector<OpFoldResult> dstStrides = extractOp.getMixedStrides();
273
274 if (allEqual(srcSizes, dstSizes) && allEqual(srcOffsets, dstOffsets) &&
275 allEqual(srcStrides, dstStrides)) {
276 Value operand = concatOp.getOperand(i);
277 if (operand.getType() == extractOp.getResultType())
278 rewriter.replaceOp(op: extractOp, newValues: operand);
279 break;
280 }
281 }
282
283 return success();
284 }
285};
286
287/// Rewriting rule that fuses sparse_tensor.convert into producer.
288struct FoldConvertIntoProducer : public OpRewritePattern<ConvertOp> {
289public:
290 using Base::Base;
291
292 LogicalResult matchAndRewrite(ConvertOp op,
293 PatternRewriter &rewriter) const override {
294 auto producer = op.getSource().getDefiningOp<GenericOp>();
295 if (!producer || producer.getDpsInits().size() != 1 ||
296 !isMaterializing(op: producer.getDpsInitOperand(i: 0), isZero: false) ||
297 !producer.getResult(i: 0).hasOneUse()) {
298 return failure();
299 }
300 // Clone the materialization operation, but update the result to sparse.
301 rewriter.setInsertionPoint(producer);
302 Operation *init = producer.getDpsInitOperand(i: 0)->get().getDefiningOp();
303 Operation *cloned = rewriter.clone(op&: *init);
304 cloned->getResult(idx: 0).setType(op.getResult().getType());
305
306 rewriter.modifyOpInPlace(root: producer, callable: [&]() {
307 producer.getDpsInitsMutable().assign(values: cloned->getResults());
308 producer.getResult(i: 0).setType(op.getResult().getType());
309 });
310
311 rewriter.replaceAllOpUsesWith(from: op, to: producer);
312 rewriter.eraseOp(op);
313
314 return success();
315 }
316};
317
318/// Rewriting rule that converts direct yield of zero with initial allocation.
319struct FoldInvariantYield : public OpRewritePattern<GenericOp> {
320public:
321 using OpRewritePattern<GenericOp>::OpRewritePattern;
322
323 LogicalResult matchAndRewrite(GenericOp op,
324 PatternRewriter &rewriter) const override {
325 if (!op.hasPureTensorSemantics() || op.getNumResults() != 1 ||
326 !isMaterializing(op: op.getDpsInitOperand(i: 0), /*isZero=*/false) ||
327 !isZeroYield(op) || !op.getDpsInitOperand(i: 0)->get().hasOneUse())
328 return failure();
329 auto outputType = getRankedTensorType(t: op.getResult(i: 0));
330 // Yielding zero on newly materialized sparse tensor can be
331 // optimized directly (regardless of dynamic or static size).
332 if (getSparseTensorEncoding(type: outputType)) {
333 rewriter.replaceOp(op, newValues: op.getDpsInitOperand(i: 0)->get());
334 return success();
335 }
336 // Use static zero value directly instead of materialization.
337 if (!outputType.hasStaticShape())
338 return failure();
339 Operation *def = op.getDpsInitOperand(i: 0)->get().getDefiningOp();
340 rewriter.replaceOp(op, newValues: constantZero(builder&: rewriter, loc: op.getLoc(), tp: outputType));
341 rewriter.eraseOp(op: def);
342 return success();
343 }
344};
345
346/// Rewriting rule that converts two kernels:
347///
348/// T(i,j) = SUM(k, A(i,j,k) * B(i,j,k) * ... )
349/// X(i,j) = S(i,j) * T(i,j)
350///
351/// into a single kernel, using distributive law:
352///
353/// X(i,j) = SUM(k, S(i,j) * A(i,j,k) * B(i,j,k) * ... )
354///
355/// This kind of fusion (merging two ops into one but using arithmetic
356/// equalities that may not hold for floating-point computations) would
357/// be undesirable in the dense case, since we distribute the multiplication
358/// into the reduction loop. However, for sparse sampling tensor S, such
359/// a fusion may actually reduce the asymptotic complexity of the kernel,
360/// since intermediate results may be nullified.
361struct FuseSparseMultiplyOverAdd : public OpRewritePattern<GenericOp> {
362public:
363 using OpRewritePattern<GenericOp>::OpRewritePattern;
364
365 LogicalResult matchAndRewrite(GenericOp op,
366 PatternRewriter &rewriter) const override {
367 // Check consumer.
368 if (!op.hasPureTensorSemantics() || op.getNumDpsInputs() != 2 ||
369 op.getNumResults() != 1 ||
370 op.getNumParallelLoops() != op.getNumLoops() ||
371 !op.getMatchingIndexingMap(opOperand: op.getDpsInitOperand(i: 0)).isIdentity() ||
372 !op.getMatchingIndexingMap(opOperand: op.getDpsInputOperand(i: 0)).isIdentity() ||
373 !op.getMatchingIndexingMap(opOperand: op.getDpsInputOperand(i: 1)).isIdentity())
374 return failure();
375 // Find consuming OP2(sparse, other) or OP2(other, sparse). The other
376 // operand can be sparse or dense, since the point of this rewriting rule
377 // is detecting a situation in which *more* sparsity is introduced into
378 // a computation, be it already sparse or still dense.
379 unsigned other = 0;
380 if (isSparseTensor(op: op.getDpsInputOperand(i: 0)))
381 other = 1;
382 else if (!isSparseTensor(op: op.getDpsInputOperand(i: 1)))
383 return failure();
384 // Check producer.
385 auto prod = dyn_cast_or_null<GenericOp>(
386 Val: op.getDpsInputOperand(i: other)->get().getDefiningOp());
387 if (!prod || !prod.hasPureTensorSemantics() || prod.getNumResults() != 1 ||
388 !prod.getResult(i: 0).hasOneUse())
389 return failure();
390 // Sampling consumer and sum of multiplication chain producer.
391 if (!isMaterializing(op: op.getDpsInitOperand(i: 0), /*isZero=*/false) ||
392 !isMaterializing(op: prod.getDpsInitOperand(i: 0), /*isZero=*/true) ||
393 !isSampling(op) || !isSumOfMul(op: prod))
394 return failure();
395 // Modify operand structure of producer and consumer.
396 Location loc = prod.getLoc();
397 SmallVector<Value> inputOps = prod.getInputs();
398 SmallVector<Value> outputOps = op.getOutputs();
399 SmallVector<AffineMap> fusedIndexMaps = prod.getIndexingMapsArray();
400 inputOps.push_back(Elt: op.getDpsInputOperand(i: 1 - other)->get());
401 fusedIndexMaps.push_back(Elt: fusedIndexMaps.back()); // mimic other
402 // Fuse producer and consumer into a new generic op.
403 auto fusedOp = GenericOp::create(
404 builder&: rewriter, location: loc, result_tensors: op.getResult(i: 0).getType(), inputs: inputOps, outputs: outputOps,
405 indexing_maps: rewriter.getAffineMapArrayAttr(values: fusedIndexMaps), iterator_types: prod.getIteratorTypes(),
406 /*doc=*/nullptr, /*library_call=*/nullptr);
407 Block &prodBlock = prod.getRegion().front();
408 Block &consBlock = op.getRegion().front();
409 IRMapping mapper;
410 Block *fusedBlock = rewriter.createBlock(parent: &fusedOp.getRegion());
411 unsigned num = prodBlock.getNumArguments();
412 for (unsigned i = 0; i < num - 1; i++)
413 addArg(mapper, b: fusedBlock, a: prodBlock.getArgument(i));
414 addArg(mapper, b: fusedBlock, a: consBlock.getArgument(i: 1 - other));
415 addArg(mapper, b: fusedBlock, a: prodBlock.getArgument(i: num - 1));
416 // Clone bodies of the producer and consumer in new evaluation order.
417 auto *acc = prodBlock.getTerminator()->getOperand(idx: 0).getDefiningOp();
418 auto *sampler = consBlock.getTerminator()->getOperand(idx: 0).getDefiningOp();
419 Value last;
420 for (auto &op : prodBlock.without_terminator())
421 if (&op != acc) {
422 last = op.getResult(idx: 0);
423 rewriter.clone(op, mapper);
424 }
425 mapper.map(from: consBlock.getArgument(i: other), to: fusedBlock->back().getResult(idx: 0));
426 mapper.map(from: last, to: rewriter.clone(op&: *sampler, mapper)->getResult(idx: 0));
427 last = rewriter.clone(op&: *acc, mapper)->getResult(idx: 0);
428 linalg::YieldOp::create(builder&: rewriter, location: loc, values: last);
429 // Force initial value on merged allocation for dense outputs.
430 // TODO: deal with non alloc tensor here one day
431 if (!getSparseTensorEncoding(type: op.getResult(i: 0).getType())) {
432 Value init = prod.getDpsInitOperand(i: 0)
433 ->get()
434 .getDefiningOp<AllocTensorOp>()
435 .getCopy();
436 AllocTensorOp a =
437 op.getDpsInitOperand(i: 0)->get().getDefiningOp<AllocTensorOp>();
438 rewriter.modifyOpInPlace(root: a, callable: [&]() { a.getCopyMutable().assign(value: init); });
439 }
440 // Replace consumer with fused operation. Old producer
441 // and consumer ops will be removed by DCE.
442 rewriter.replaceOp(op, newValues: fusedOp->getResults());
443 return success();
444 }
445
446private:
447 // Helper to add argument and record the mapping.
448 static void addArg(IRMapping &mapper, Block *b, BlockArgument a) {
449 mapper.map(from: a, to: b->addArgument(type: a.getType(), loc: a.getLoc()));
450 }
451};
452
453// Fuse a tensor cast into producing operation. Note that a tensor.cast
454// should really not be used to convert between sparse encodings. Since
455// the pattern currently appears as a result of some prior rewriting
456// we make an attempt to repair very obvious cases.
457// TODO: audit the pure tensor dialect rewriting rules
458struct FuseTensorCast : public OpRewritePattern<tensor::CastOp> {
459public:
460 using OpRewritePattern<tensor::CastOp>::OpRewritePattern;
461
462 LogicalResult matchAndRewrite(tensor::CastOp op,
463 PatternRewriter &rewriter) const override {
464 Type srcType = op.getSource().getType();
465 Type dstType = op.getDest().getType();
466 // A nop cast simply folds away.
467 if (srcType == dstType) {
468 rewriter.replaceOp(op, newValues: op->getResults());
469 return success();
470 }
471 // See if a sparsity changing cast can be fused into producer.
472 if (tensor::isSameTypeWithoutEncoding(tp1: srcType, tp2: dstType)) {
473 if (Operation *def = op.getSource().getDefiningOp()) {
474 if (def->hasOneUse() && isa<tensor::ExtractSliceOp>(Val: def)) {
475 rewriter.modifyOpInPlace(root: def, callable: [&]() {
476 def->getResult(idx: 0).setType(op->getResultTypes()[0]);
477 });
478 rewriter.replaceOp(op, newValues: def->getResult(idx: 0));
479 return success();
480 }
481 }
482 }
483 // Repair tensor casts with at least one sparse operand into the
484 // the properly supported sparse_tensor.convert.
485 if (getSparseTensorEncoding(type: srcType) || getSparseTensorEncoding(type: dstType)) {
486 rewriter.replaceOpWithNewOp<ConvertOp>(op, args&: dstType, args: op.getSource());
487 return success();
488 }
489 // Fail otherwise.
490 return failure();
491 }
492};
493
494/// Rewrites a sequence of operations for sparse tensor selections in to
495/// semi-ring operations such that they can be compiled correctly by the
496/// sparsifier. E.g., transforming the following sequence
497///
498/// %sel = arith.select %cond, %sp1, %sp2
499///
500/// to
501///
502/// %sel = binary %sp1, %sp2:
503/// both (%l, %r) {yield select %cond, %l, %r}
504/// left (%l) {yield select %cond, %l, 0}
505/// right (%r) {yield select %cond, 0, %r}
506///
507/// TODO: We require that the tensor used for extracting conditions to be dense
508/// to sparsify the code. To support a sparse condition tensor, we need a
509/// tri-nary operation.
510struct GenSemiRingSelect : public OpRewritePattern<GenericOp> {
511public:
512 using OpRewritePattern<GenericOp>::OpRewritePattern;
513 LogicalResult matchAndRewrite(GenericOp op,
514 PatternRewriter &rewriter) const override {
515 // Rejects non sparse kernels.
516 if (!op.hasPureTensorSemantics() || !hasAnySparseOperand(op))
517 return failure();
518
519 Location loc = op.getLoc();
520 SmallVector<std::pair<Operation *, sparse_tensor::BinaryOp>> semiRings;
521 for (Operation &inst : *op.getBody()) {
522 // Matches pattern.
523 auto matched = isRewritablePattern(op, v: &inst);
524 if (!matched.has_value())
525 continue;
526
527 rewriter.setInsertionPoint(&inst);
528 auto [c, t, f] = matched.value();
529 assert(t.getType() == f.getType());
530 auto selTp = t.getType();
531 auto c0 = constantZero(builder&: rewriter, loc, tp: selTp);
532 auto binOp = sparse_tensor::BinaryOp::create(builder&: rewriter, location: loc, output: selTp, x: t, y: f);
533 // Initializes all the blocks.
534 rewriter.createBlock(parent: &binOp.getOverlapRegion(), insertPt: {}, argTypes: {selTp, selTp},
535 locs: {t.getLoc(), f.getLoc()});
536 rewriter.createBlock(parent: &binOp.getRightRegion(), insertPt: {}, argTypes: selTp, locs: f.getLoc());
537 rewriter.createBlock(parent: &binOp.getLeftRegion(), insertPt: {}, argTypes: selTp, locs: t.getLoc());
538
539 for (auto *r : binOp.getRegions()) {
540 Block *b = &r->front();
541 rewriter.setInsertionPointToStart(b);
542
543 IRMapping irMap;
544 // Clones the cmp operations into the region to make the binary op
545 // admissible.
546 Value newC = c;
547 if (auto *def = c.getDefiningOp())
548 newC = rewriter.clone(op&: *def, mapper&: irMap)->getResult(idx: 0);
549
550 irMap.map(from: c, to: newC);
551 if (r == &binOp.getLeftRegion()) {
552 irMap.map(from: t, to: b->getArgument(i: 0));
553 irMap.map(from: f, to: c0);
554 } else if (r == &binOp.getRightRegion()) {
555 irMap.map(from: t, to: c0);
556 irMap.map(from: f, to: b->getArgument(i: 0));
557 } else {
558 irMap.map(from: t, to: b->getArgument(i: 0));
559 irMap.map(from: f, to: b->getArgument(i: 1));
560 }
561 auto y = rewriter.clone(op&: inst, mapper&: irMap)->getResult(idx: 0);
562 sparse_tensor::YieldOp::create(builder&: rewriter, location: loc, yieldVal: y);
563 }
564
565 // We successfully rewrited a operation. We can not do replacement here
566 // becuase it invalidate the iterator for the current loop to traverse
567 // the instructions.
568 semiRings.emplace_back(Args: &inst, Args&: binOp);
569 }
570
571 // Finalizes the replacement.
572 for (auto [sel, semi] : semiRings)
573 rewriter.replaceOp(op: sel, newValues: semi->getResults());
574
575 return success(IsSuccess: !semiRings.empty());
576 }
577
578private:
579 static std::optional<std::tuple<Value, BlockArgument, BlockArgument>>
580 isRewritablePattern(GenericOp op, Operation *v) {
581 auto sel = dyn_cast<arith::SelectOp>(Val: v);
582 if (!sel)
583 return std::nullopt;
584
585 auto tVal = dyn_cast<BlockArgument>(Val: sel.getTrueValue());
586 auto fVal = dyn_cast<BlockArgument>(Val: sel.getFalseValue());
587 // TODO: For simplicity, we only handle cases where both true/false value
588 // are directly loaded the input tensor. We can probably admit more cases
589 // in theory.
590 if (!tVal || !fVal)
591 return std::nullopt;
592
593 // Helper lambda to determine whether the value is loaded from a dense input
594 // or is a loop invariant.
595 auto isValFromDenseInputOrInvariant = [&op](Value v) -> bool {
596 if (auto bArg = dyn_cast<BlockArgument>(Val&: v);
597 bArg && !isSparseTensor(op: op.getDpsInputOperand(i: bArg.getArgNumber())))
598 return true;
599 // If the value is defined outside the loop, it is a loop invariant.
600 return v.getDefiningOp() && v.getDefiningOp()->getBlock() != op.getBody();
601 };
602
603 // If the condition value is load directly from a dense tensor or
604 // loop-invariants, we can sparsify the kernel.
605 auto cond = sel.getCondition();
606 if (isValFromDenseInputOrInvariant(cond))
607 return std::make_tuple(args&: cond, args&: tVal, args&: fVal);
608
609 Value cmpL, cmpR;
610 if (matchPattern(value: cond, pattern: m_Op<arith::CmpIOp>(matchers: matchers::m_Any(val: &cmpL),
611 matchers: matchers::m_Any(val: &cmpR))) ||
612 matchPattern(value: cond, pattern: m_Op<arith::CmpFOp>(matchers: matchers::m_Any(val: &cmpL),
613 matchers: matchers::m_Any(val: &cmpR)))) {
614 // TODO: we can do it recursively to check whether all the leaf values are
615 // loaded from dense tensors or are loop invariants.
616 if (isValFromDenseInputOrInvariant(cmpL) ||
617 isValFromDenseInputOrInvariant(cmpR))
618 return std::make_tuple(args&: cond, args&: tVal, args&: fVal);
619 }
620
621 return std::nullopt;
622 };
623};
624
625/// Rewrites a sparse reduction that would not sparsify directly since
626/// doing so would only iterate over the stored elements, ignoring the
627/// implicit zeros, into a semi-ring. Applies to all prod/and/min/max
628/// (note that reductions like add/sub/or/xor can directly be sparsified
629/// since the implicit zeros do not contribute to the final result).
630/// Note that prod/and are still included since, even though they often
631/// are nullified in sparse data, they may still occur for special
632/// situations in which e.g. some rows in a sparse matrix are fully
633/// dense. For min/max, including the implicit zeros is a much more
634/// common situation.
635///
636/// TODO: this essentially "densifies" the operation; we want to implement
637/// this much more efficiently by performing the reduction over the
638/// stored values, and feed in the zero once if there were *any*
639/// implicit zeros as well; but for now, at least we provide
640/// the functionality
641///
642struct GenSemiRingReduction : public OpRewritePattern<GenericOp> {
643public:
644 using OpRewritePattern<GenericOp>::OpRewritePattern;
645
646 LogicalResult matchAndRewrite(GenericOp op,
647 PatternRewriter &rewriter) const override {
648 // Reject non-reductions.
649 if (!op.hasPureTensorSemantics() || op.getNumDpsInputs() != 1 ||
650 op.getNumReductionLoops() == 0 || op.getNumResults() != 1)
651 return failure();
652 auto *inp = op.getDpsInputOperand(i: 0);
653 auto *init = op.getDpsInitOperand(i: 0);
654 if (!isSparseTensor(op: inp))
655 return failure();
656 // Look for direct x = x OP y for semi-ring ready reductions.
657 auto *red = cast<linalg::YieldOp>(Val: op.getRegion().front().getTerminator())
658 .getOperand(i: 0)
659 .getDefiningOp();
660 if (!isa<arith::AndIOp, arith::MulIOp, arith::MulFOp, arith::MinimumFOp,
661 arith::MinSIOp, arith::MinUIOp, arith::MaximumFOp, arith::MaxSIOp,
662 arith::MaxUIOp>(Val: red))
663 return failure();
664 Value s0 = op.getBlock()->getArgument(i: 0);
665 Value s1 = op.getBlock()->getArgument(i: 1);
666 if ((red->getOperand(idx: 0) != s0 || red->getOperand(idx: 1) != s1) &&
667 (red->getOperand(idx: 0) != s1 || red->getOperand(idx: 1) != s0))
668 return failure();
669 // Identity.
670 Location loc = op.getLoc();
671 Value identity =
672 tensor::ExtractOp::create(builder&: rewriter, location: loc, tensor: init->get(), indices: ValueRange());
673 // Unary {
674 // present -> value
675 // absent -> zero.
676 // }
677 Type rtp = s0.getType();
678 rewriter.setInsertionPointToStart(&op.getRegion().front());
679 auto semiring = sparse_tensor::UnaryOp::create(builder&: rewriter, location: loc, output: rtp, x: s0);
680 Block *present =
681 rewriter.createBlock(parent: &semiring.getPresentRegion(), insertPt: {}, argTypes: rtp, locs: loc);
682 rewriter.setInsertionPointToStart(&semiring.getPresentRegion().front());
683 sparse_tensor::YieldOp::create(builder&: rewriter, location: loc, yieldVal: present->getArgument(i: 0));
684 rewriter.createBlock(parent: &semiring.getAbsentRegion(), insertPt: {}, argTypes: {}, locs: {});
685 rewriter.setInsertionPointToStart(&semiring.getAbsentRegion().front());
686 auto zero =
687 arith::ConstantOp::create(builder&: rewriter, location: loc, value: rewriter.getZeroAttr(type: rtp));
688 sparse_tensor::YieldOp::create(builder&: rewriter, location: loc, yieldVal: zero);
689 rewriter.setInsertionPointAfter(semiring);
690 // CustomReduce {
691 // x = x REDUC y, identity
692 // }
693 auto custom = sparse_tensor::ReduceOp::create(
694 builder&: rewriter, location: loc, output: rtp, x: semiring.getResult(), y: s1, identity);
695 Block *region =
696 rewriter.createBlock(parent: &custom.getRegion(), insertPt: {}, argTypes: {rtp, rtp}, locs: {loc, loc});
697 rewriter.setInsertionPointToStart(&custom.getRegion().front());
698 IRMapping irMap;
699 irMap.map(from: red->getOperand(idx: 0), to: region->getArgument(i: 0));
700 irMap.map(from: red->getOperand(idx: 1), to: region->getArgument(i: 1));
701 auto *cloned = rewriter.clone(op&: *red, mapper&: irMap);
702 sparse_tensor::YieldOp::create(builder&: rewriter, location: loc, yieldVal: cloned->getResult(idx: 0));
703 rewriter.setInsertionPointAfter(custom);
704 rewriter.replaceOp(op: red, newValues: custom.getResult());
705 return success();
706 }
707};
708
709/// Sparse rewriting rule for the print operator. This operation is mainly used
710/// for debugging and testing. As such, it lowers to the vector.print operation
711/// which only require very light-weight runtime support.
712struct PrintRewriter : public OpRewritePattern<PrintOp> {
713public:
714 using Base::Base;
715 LogicalResult matchAndRewrite(PrintOp op,
716 PatternRewriter &rewriter) const override {
717 Location loc = op.getLoc();
718 auto tensor = op.getTensor();
719 auto stt = getSparseTensorType(val: tensor);
720 // Header with NSE.
721 auto nse = NumberOfEntriesOp::create(builder&: rewriter, location: loc, tensor);
722 vector::PrintOp::create(
723 builder&: rewriter, location: loc,
724 string: rewriter.getStringAttr(bytes: "---- Sparse Tensor ----\nnse = "));
725 vector::PrintOp::create(builder&: rewriter, location: loc, source: nse);
726 // Print run-time contents for dim/lvl sizes.
727 vector::PrintOp::create(builder&: rewriter, location: loc, string: rewriter.getStringAttr(bytes: "dim = "));
728 printSizes(rewriter, loc, tensor, size: stt.getDimRank(), /*isDim=*/true);
729 vector::PrintOp::create(builder&: rewriter, location: loc, string: rewriter.getStringAttr(bytes: "lvl = "));
730 printSizes(rewriter, loc, tensor, size: stt.getLvlRank(), /*isDim=*/false);
731 // Use the "codegen" foreach loop construct to iterate over
732 // all typical sparse tensor components for printing.
733 foreachFieldAndTypeInSparseTensor(stt, [&rewriter, &loc, &tensor,
734 &stt](Type, FieldIndex,
735 SparseTensorFieldKind kind,
736 Level l, LevelType) {
737 switch (kind) {
738 case SparseTensorFieldKind::StorageSpec: {
739 break;
740 }
741 case SparseTensorFieldKind::PosMemRef: {
742 auto lvl = constantIndex(builder&: rewriter, loc, i: l);
743 vector::PrintOp::create(builder&: rewriter, location: loc, string: rewriter.getStringAttr(bytes: "pos["));
744 vector::PrintOp::create(builder&: rewriter, location: loc, source: lvl,
745 punctuation: vector::PrintPunctuation::NoPunctuation);
746 vector::PrintOp::create(builder&: rewriter, location: loc, string: rewriter.getStringAttr(bytes: "] : "));
747 auto pos = ToPositionsOp::create(builder&: rewriter, location: loc, tensor, level: l);
748 printContents(rewriter, loc, vec: pos);
749 break;
750 }
751 case SparseTensorFieldKind::CrdMemRef: {
752 auto lvl = constantIndex(builder&: rewriter, loc, i: l);
753 vector::PrintOp::create(builder&: rewriter, location: loc, string: rewriter.getStringAttr(bytes: "crd["));
754 vector::PrintOp::create(builder&: rewriter, location: loc, source: lvl,
755 punctuation: vector::PrintPunctuation::NoPunctuation);
756 vector::PrintOp::create(builder&: rewriter, location: loc, string: rewriter.getStringAttr(bytes: "] : "));
757 Value crd = nullptr;
758 // For COO AoS storage, we want to print a single, linear view of
759 // the full coordinate storage at this level. For any other storage,
760 // we show the coordinate storage for every indivual level.
761 if (stt.getAoSCOOStart() == l)
762 crd = ToCoordinatesBufferOp::create(builder&: rewriter, location: loc, tensor);
763 else
764 crd = ToCoordinatesOp::create(builder&: rewriter, location: loc, tensor, level: l);
765 printContents(rewriter, loc, vec: crd);
766 break;
767 }
768 case SparseTensorFieldKind::ValMemRef: {
769 vector::PrintOp::create(builder&: rewriter, location: loc,
770 string: rewriter.getStringAttr(bytes: "values : "));
771 auto val = ToValuesOp::create(builder&: rewriter, location: loc, tensor);
772 printContents(rewriter, loc, vec: val);
773 break;
774 }
775 }
776 return true;
777 });
778 vector::PrintOp::create(builder&: rewriter, location: loc, string: rewriter.getStringAttr(bytes: "----\n"));
779 rewriter.eraseOp(op);
780 return success();
781 }
782
783private:
784 // Helper to print contents of a single memref. For "push_back" vectors,
785 // we assume that the previous getters for pos/crd/val have added a
786 // slice-to-size view to make sure we just print the size and not the
787 // full capacity.
788 //
789 // Generates code to print (1-dim or higher):
790 // ( a0, a1, ... )
791 static void printContents(PatternRewriter &rewriter, Location loc,
792 Value vec) {
793 auto shape = cast<ShapedType>(Val: vec.getType()).getShape();
794 SmallVector<Value> idxs;
795 printContentsLevel(rewriter, loc, vec, i: 0, shape, idxs);
796 vector::PrintOp::create(builder&: rewriter, location: loc, punctuation: vector::PrintPunctuation::NewLine);
797 }
798
799 // Helper to the helper.
800 static void printContentsLevel(PatternRewriter &rewriter, Location loc,
801 Value vec, unsigned i, ArrayRef<int64_t> shape,
802 SmallVectorImpl<Value> &idxs) {
803 // Open bracket.
804 vector::PrintOp::create(builder&: rewriter, location: loc, punctuation: vector::PrintPunctuation::Open);
805 // Generate for loop.
806 auto zero = constantIndex(builder&: rewriter, loc, i: 0);
807 auto index = constantIndex(builder&: rewriter, loc, i);
808 auto size = memref::DimOp::create(builder&: rewriter, location: loc, source: vec, index);
809 auto step = constantIndex(builder&: rewriter, loc, i: 1);
810 auto forOp = scf::ForOp::create(builder&: rewriter, location: loc, lowerBound: zero, upperBound: size, step);
811 idxs.push_back(Elt: forOp.getInductionVar());
812 rewriter.setInsertionPointToStart(forOp.getBody());
813 if (i < shape.size() - 1) {
814 // Enter deeper loop nest.
815 printContentsLevel(rewriter, loc, vec, i: i + 1, shape, idxs);
816 } else {
817 // Actual contents printing.
818 auto val = memref::LoadOp::create(builder&: rewriter, location: loc, memref: vec, indices: idxs);
819 if (llvm::isa<ComplexType>(Val: val.getType())) {
820 // Since the vector dialect does not support complex types in any op,
821 // we split those into (real, imag) pairs here.
822 Value real = complex::ReOp::create(builder&: rewriter, location: loc, complex: val);
823 Value imag = complex::ImOp::create(builder&: rewriter, location: loc, complex: val);
824 vector::PrintOp::create(builder&: rewriter, location: loc, punctuation: vector::PrintPunctuation::Open);
825 vector::PrintOp::create(builder&: rewriter, location: loc, source: real,
826 punctuation: vector::PrintPunctuation::Comma);
827 vector::PrintOp::create(builder&: rewriter, location: loc, source: imag,
828 punctuation: vector::PrintPunctuation::Close);
829 } else {
830 vector::PrintOp::create(builder&: rewriter, location: loc, source: val,
831 punctuation: vector::PrintPunctuation::NoPunctuation);
832 }
833 // Terminating comma (except at end).
834 auto bound = arith::AddIOp::create(builder&: rewriter, location: loc, lhs: idxs.back(), rhs: step);
835 Value cond = arith::CmpIOp::create(builder&: rewriter, location: loc,
836 predicate: arith::CmpIPredicate::ne, lhs: bound, rhs: size);
837 scf::IfOp ifOp = scf::IfOp::create(builder&: rewriter, location: loc, cond, /*else*/ withElseRegion: false);
838 rewriter.setInsertionPointToStart(&ifOp.getThenRegion().front());
839 vector::PrintOp::create(builder&: rewriter, location: loc, punctuation: vector::PrintPunctuation::Comma);
840 }
841 idxs.pop_back();
842 rewriter.setInsertionPointAfter(forOp);
843 // Close bracket.
844 vector::PrintOp::create(builder&: rewriter, location: loc, punctuation: vector::PrintPunctuation::Close);
845 }
846
847 // Helper method to print run-time lvl/dim sizes.
848 static void printSizes(PatternRewriter &rewriter, Location loc, Value tensor,
849 unsigned size, bool isDim) {
850 // Open bracket.
851 vector::PrintOp::create(builder&: rewriter, location: loc, punctuation: vector::PrintPunctuation::Open);
852 // Print unrolled contents (dimop requires constant value).
853 for (unsigned i = 0; i < size; i++) {
854 auto idx = constantIndex(builder&: rewriter, loc, i);
855 Value val;
856 if (isDim)
857 val = tensor::DimOp::create(builder&: rewriter, location: loc, source: tensor, index: idx);
858 else
859 val = LvlOp::create(builder&: rewriter, location: loc, source: tensor, index: idx);
860 vector::PrintOp::create(builder&: rewriter, location: loc, source: val,
861 punctuation: i != size - 1
862 ? vector::PrintPunctuation::Comma
863 : vector::PrintPunctuation::NoPunctuation);
864 }
865 // Close bracket and end of line.
866 vector::PrintOp::create(builder&: rewriter, location: loc, punctuation: vector::PrintPunctuation::Close);
867 vector::PrintOp::create(builder&: rewriter, location: loc, punctuation: vector::PrintPunctuation::NewLine);
868 }
869};
870
871/// Sparse rewriting rule for sparse-to-sparse reshape operator.
872struct TensorReshapeRewriter : public OpRewritePattern<tensor::ReshapeOp> {
873public:
874 using OpRewritePattern<tensor::ReshapeOp>::OpRewritePattern;
875
876 LogicalResult matchAndRewrite(tensor::ReshapeOp op,
877 PatternRewriter &rewriter) const override {
878 Location loc = op.getLoc();
879 Value srcTensor = op.getSource();
880 const auto srcTp = tryGetSparseTensorType(val: srcTensor);
881 const auto dstTp = tryGetSparseTensorType(val: op.getResult());
882 if (!srcTp || !dstTp)
883 return failure();
884
885 if (!srcTp->hasEncoding() || !dstTp->hasEncoding() ||
886 !dstTp->hasStaticDimShape())
887 return failure();
888
889 SmallVector<Value> srcSizes;
890 sizesForTensor(builder&: rewriter, sizes&: srcSizes, loc, stp: *srcTp, tensor: srcTensor);
891 SmallVector<Value> dstSizes;
892 for (Dimension d : dstTp->getDimShape())
893 dstSizes.push_back(Elt: constantIndex(builder&: rewriter, loc, i: d));
894
895 Value nnz = NumberOfEntriesOp::create(builder&: rewriter, location: loc, tensor: srcTensor);
896 // Only need an unordered COO buffer if input and output are not sorted
897 // in the same way.
898 Type bufferTp = getBufferType(
899 stt: dstTp->withoutDimToLvl(),
900 needTmpCOO: !srcTp->isAllOrdered() || !srcTp->isIdentity() || !dstTp->isIdentity());
901 SmallVector<Value> dynSizes;
902 Value buffer = AllocTensorOp::create(builder&: rewriter, location: loc, result: bufferTp, dynamic_sizes: dynSizes,
903 copy: Value(), size_hint: nnz, memory_space: Attribute())
904 .getResult();
905
906 // Convert src coordinates to dst coordinates by first collapsing it to 1D
907 // and then expand it to the match the rank of the destination tensor.
908 // Implemented as follows:
909 // foreach srcCoords %srcTensor
910 // collapsedCoords = reshapeCvs(srcCoords, [1, ..., srcRank])
911 // expandedCoords = reshapeCvs(collapsedCoords, [1, ..., dstRank])
912 // insert expandedCoords, %buffer
913 //
914 // followed by an optional
915 // %t = sparse_tensor.cast %tmp
916 // depending on whether the input/output are sorted in the same way.
917 const auto encSrc = srcTp->getEncoding();
918 ForeachOp foreachOp = ForeachOp::create(
919 builder&: rewriter, location: loc, tensor: srcTensor, iterArgs: buffer,
920 bodyBuilder: [&](OpBuilder &builder, Location loc, ValueRange srcLcvs, Value v,
921 ValueRange reduc) {
922 const Dimension srcRank = srcTp->getDimRank();
923 SmallVector<Value> srcDcvs;
924 srcDcvs.reserve(N: srcRank);
925 for (Dimension d = 0; d < srcRank; d++) {
926 Level lvl = toLvl(enc: encSrc, d);
927 srcDcvs.push_back(Elt: srcLcvs[lvl]);
928 }
929
930 Value collapseSize = constantIndex(builder, loc, i: 1);
931 for (Dimension d = 0; d < srcRank; d++)
932 collapseSize =
933 arith::MulIOp::create(builder, location: loc, lhs: collapseSize, rhs: srcSizes[d]);
934 SmallVector<Value, 1> collapsedSizes = {collapseSize};
935
936 ReassociationIndices collapseIdx;
937 for (Dimension i = 0; i < srcRank; i++)
938 collapseIdx.push_back(Elt: i);
939 SmallVector<ReassociationIndices, 1> collapseReass = {collapseIdx};
940 SmallVector<Value, 1> collapsedDcvs;
941 reshapeCvs(builder, loc, reassociation: collapseReass, srcSizes, srcCvs: srcDcvs,
942 dstSizes: collapsedSizes, dstCvs&: collapsedDcvs);
943
944 ReassociationIndices expandIdx;
945 for (Dimension i = 0; i < dstTp->getDimRank(); i++)
946 expandIdx.push_back(Elt: i);
947 SmallVector<ReassociationIndices, 1> expandReass = {expandIdx};
948 SmallVector<Value> dstDcvs;
949 reshapeCvs(builder, loc, reassociation: expandReass, srcSizes: collapsedSizes, srcCvs: collapsedDcvs,
950 dstSizes, dstCvs&: dstDcvs);
951
952 auto t =
953 tensor::InsertOp::create(builder, location: loc, scalar: v, dest: reduc.front(), indices: dstDcvs);
954 sparse_tensor::YieldOp::create(builder, location: loc, yieldVal: t);
955 });
956
957 Value t = LoadOp::create(builder&: rewriter, location: loc, tensor: foreachOp.getResult(i: 0), hasInserts: true);
958 if (bufferTp != *dstTp) {
959 auto dstRTT = dstTp->getRankedTensorType();
960 Value converted = ConvertOp::create(builder&: rewriter, location: loc, dest: dstRTT, source: t).getResult();
961 DeallocTensorOp::create(builder&: rewriter, location: loc, tensor: t);
962 t = converted;
963 }
964 rewriter.replaceOp(op, newValues: t);
965 return success();
966 }
967};
968
969/// Sparse rewriting rule for sparse-to-sparse reshape operator.
970template <typename ReshapeOp>
971struct Sparse2SparseReshapeRewriter : public OpRewritePattern<ReshapeOp> {
972public:
973 using OpRewritePattern<ReshapeOp>::OpRewritePattern;
974
975 LogicalResult matchAndRewrite(ReshapeOp op,
976 PatternRewriter &rewriter) const override {
977 Location loc = op.getLoc();
978 Value srcTensor = op.getSrc();
979 const auto srcTp = getSparseTensorType(val: srcTensor);
980 const auto dstTp = getSparseTensorType(op.getResult());
981 if (!srcTp.hasEncoding() || !dstTp.hasEncoding())
982 return failure();
983
984 // Generate code to represent the static dimension constants or compute
985 // the dynamic dimension values.
986 SmallVector<Value> srcSizes;
987 sizesForTensor(builder&: rewriter, sizes&: srcSizes, loc, stp: srcTp, tensor: srcTensor);
988 SmallVector<Value> dstSizes;
989 SmallVector<Value> dstDynSizes;
990 if (dstTp.hasStaticDimShape()) {
991 for (Dimension d : dstTp.getDimShape())
992 dstSizes.push_back(Elt: constantIndex(builder&: rewriter, loc, i: d));
993 } else {
994 ArrayRef<Size> dstShape = dstTp.getDimShape();
995 genReshapeDstShape(rewriter, loc, dstSizes, srcSizes, dstShape,
996 op.getReassociationIndices());
997 for (auto [idx, shape] : llvm::enumerate(First&: dstShape)) {
998 if (shape == ShapedType::kDynamic)
999 dstDynSizes.push_back(Elt: dstSizes[idx]);
1000 }
1001 }
1002 Value nnz = NumberOfEntriesOp::create(builder&: rewriter, location: loc, tensor: srcTensor);
1003 // Only need a unordered COO buffer if input and output are not sorted
1004 // in the same way.
1005 Type bufferTp = getBufferType(
1006 dstTp.withoutDimToLvl(),
1007 !srcTp.isAllOrdered() || !srcTp.isIdentity() || !dstTp.isIdentity());
1008
1009 Value buffer =
1010 AllocTensorOp::create(builder&: rewriter, location: loc, result: bufferTp, dynamic_sizes: dstDynSizes, copy: Value(),
1011 /*size_hint=*/nnz, memory_space: Attribute())
1012 .getResult();
1013
1014 // Implement the sparse2sparse reshape as follows:
1015 // foreach srcCoords %srcTensor
1016 // insert reshapeCvs(srcCoords), %buffer
1017 //
1018 // followed by an optional
1019 // %t = sparse_tensor.cast %tmp
1020 // depending on whether the input/output are sorted in the same way.
1021 const auto encSrc = srcTp.getEncoding();
1022 ForeachOp foreachOp = ForeachOp::create(
1023 rewriter, loc, srcTensor, buffer,
1024 [&](OpBuilder &builder, Location loc, ValueRange srcLcvs, Value v,
1025 ValueRange reduc) {
1026 const Dimension dimRank = srcTp.getDimRank();
1027 SmallVector<Value> srcDcvs;
1028 srcDcvs.reserve(N: dimRank);
1029 for (Dimension d = 0; d < dimRank; d++) {
1030 Level lvl = toLvl(enc: encSrc, d);
1031 srcDcvs.push_back(Elt: srcLcvs[lvl]);
1032 }
1033 SmallVector<Value> dstDcvs;
1034 reshapeCvs(builder, loc, op.getReassociationIndices(), srcSizes,
1035 srcDcvs, dstSizes, dstDcvs);
1036 auto t =
1037 tensor::InsertOp::create(builder, location: loc, scalar: v, dest: reduc.front(), indices: dstDcvs);
1038 sparse_tensor::YieldOp::create(builder, location: loc, yieldVal: t);
1039 });
1040
1041 Value t = LoadOp::create(builder&: rewriter, location: loc, tensor: foreachOp.getResult(i: 0), hasInserts: true);
1042 if (bufferTp != dstTp) {
1043 auto dstRTT = dstTp.getRankedTensorType();
1044 Value converted = ConvertOp::create(rewriter, loc, dstRTT, t).getResult();
1045 DeallocTensorOp::create(builder&: rewriter, location: loc, tensor: t);
1046 t = converted;
1047 }
1048 rewriter.replaceOp(op, t);
1049 return success();
1050 }
1051};
1052
1053/// Sparse rewriting rule for sparse-to-dense and dense-to-sparse reshape
1054/// operator.
1055template <typename ReshapeOp>
1056struct ReshapeRewriter : public OpRewritePattern<ReshapeOp> {
1057public:
1058 using OpRewritePattern<ReshapeOp>::OpRewritePattern;
1059
1060 LogicalResult matchAndRewrite(ReshapeOp op,
1061 PatternRewriter &rewriter) const override {
1062 Location loc = op->getLoc();
1063 auto encDst = getSparseTensorEncoding(op.getResult().getType());
1064 auto encSrc = getSparseTensorEncoding(op.getSrc().getType());
1065 // Since a pure dense expansion is very cheap (change of view), for
1066 // a sparse2dense or dense2sparse, we can simply unfuse a sparse
1067 // conversion from the reshape operation itself.
1068 // All other cases are handled elsewhere.
1069 if (encDst && encSrc) {
1070 return failure();
1071 }
1072 if (encSrc) {
1073 auto rtp = getRankedTensorType(op.getSrc());
1074 auto denseTp =
1075 RankedTensorType::get(shape: rtp.getShape(), elementType: rtp.getElementType());
1076 auto convert = ConvertOp::create(rewriter, loc, denseTp, op.getSrc());
1077 rewriter.modifyOpInPlace(op, [&]() { op->setOperand(0, convert); });
1078 return success();
1079 }
1080 if (encDst) {
1081 auto rtp = getRankedTensorType(op.getResult());
1082 auto denseTp =
1083 RankedTensorType::get(shape: rtp.getShape(), elementType: rtp.getElementType());
1084 ReshapeOp reshape;
1085 if constexpr (std::is_same<ReshapeOp, tensor::ExpandShapeOp>::value) {
1086 reshape = ReshapeOp::create(rewriter, loc, denseTp, op.getSrc(),
1087 op.getReassociation(), op.getOutputShape(),
1088 op.getStaticOutputShape());
1089 } else {
1090 reshape = ReshapeOp::create(rewriter, loc, denseTp, op.getSrc(),
1091 op.getReassociation());
1092 }
1093 Value convert = ConvertOp::create(rewriter, loc, rtp, reshape);
1094 rewriter.replaceOp(op, convert);
1095 return success();
1096 }
1097 return failure();
1098 }
1099};
1100
1101// A trivial wrapper to help generate different operations for dense/sparse
1102// tensors.
1103struct TensorLike {
1104 TensorLike(OpBuilder &builder, Location loc, RankedTensorType rtt,
1105 ValueRange sizes) {
1106 SmallVector<Value> dynSzs;
1107 getDynamicSizes(tp: rtt, sizes, dynSizes&: dynSzs);
1108
1109 val = AllocTensorOp::create(builder, location: loc, type: rtt, dynamicSizes: dynSzs);
1110 if (!isSparse()) {
1111 Value c0 = constantZero(builder, loc, tp: rtt.getElementType());
1112 val = linalg::FillOp::create(builder, location: loc, inputs: c0, outputs: val).getResult(i: 0);
1113 }
1114 }
1115
1116 void insert(OpBuilder &builder, Location loc, Value v, ValueRange crds) {
1117 val = tensor::InsertOp::create(builder, location: loc, scalar: v, dest: val, indices: crds);
1118 }
1119
1120 Value finalize(OpBuilder &builder, Location loc, RankedTensorType rtp) const {
1121 if (isSparse())
1122 return LoadOp::create(builder, location: loc, tensor: val, hasInserts: true);
1123 return val;
1124 }
1125
1126 bool isSparse() const {
1127 return getSparseTensorEncoding(type: val.getType()) != nullptr;
1128 }
1129
1130 Value val;
1131};
1132
1133struct SparseTensorDimOpRewriter : public OpRewritePattern<tensor::DimOp> {
1134 using Base::Base;
1135 LogicalResult matchAndRewrite(tensor::DimOp op,
1136 PatternRewriter &rewriter) const override {
1137 std::optional<int64_t> dim = op.getConstantIndex();
1138 auto stt = tryGetSparseTensorType(val: op.getSource());
1139 if (!dim || !stt || !stt->hasEncoding())
1140 return failure();
1141
1142 if (stt->isPermutation()) {
1143 rewriter.replaceOpWithNewOp<LvlOp>(op, args: op.getSource(),
1144 args: toLvl(enc: stt->getEncoding(), d: *dim));
1145 return success();
1146 }
1147
1148 // Non-permutation dim2lvl/lvl2dim maps.
1149 // Compute as follows:
1150 // affine.apply #map (l0 - 1, l1 - 1, ...) + 1
1151 // Note that it is not the most efficient way (but a more general one) for
1152 // the lvl to dim translation, e.g., for BSR, the dimension size for can be
1153 // computed simply by lvl_size * block_size.
1154 Location loc = op.getLoc();
1155 SmallVector<Value> maxLvlCrds;
1156 for (Level l = 0; l < stt->getLvlRank(); l++) {
1157 Value lvlSz = LvlOp::create(builder&: rewriter, location: loc, source: op.getSource(), index: l);
1158 Value maxLvlCrd = arith::SubIOp::create(
1159 builder&: rewriter, location: loc, lhs: lvlSz,
1160 rhs: constantOne(builder&: rewriter, loc, tp: rewriter.getIndexType()));
1161 maxLvlCrds.push_back(Elt: maxLvlCrd);
1162 }
1163
1164 AffineExpr lvl2DimExp = stt->getLvlToDim().getResult(idx: *dim);
1165 Value maxDimCrd = affine::AffineApplyOp::create(
1166 builder&: rewriter, location: op.getLoc(), map: AffineMap::get(dimCount: stt->getLvlRank(), symbolCount: 0, result: lvl2DimExp),
1167 mapOperands: maxLvlCrds);
1168
1169 Value dimSz = arith::AddIOp::create(
1170 builder&: rewriter, location: loc, lhs: maxDimCrd,
1171 rhs: constantOne(builder&: rewriter, loc, tp: rewriter.getIndexType()));
1172 rewriter.replaceOp(op, newValues: dimSz);
1173 return success();
1174 }
1175};
1176
1177struct ConcatenateRewriter : public OpRewritePattern<ConcatenateOp> {
1178 using Base::Base;
1179 LogicalResult matchAndRewrite(ConcatenateOp op,
1180 PatternRewriter &rewriter) const override {
1181 if (op.needsExtraSort())
1182 op.emitError(message: "ConcatenateOp not staged");
1183
1184 const Location loc = op.getLoc();
1185 const auto dstTp = getSparseTensorType(val: op);
1186 const Dimension conDim = op.getDimension();
1187 SmallVector<Value> sizes;
1188 concatSizesFromInputs(builder&: rewriter, sizes, loc, dstTp, srcs: op.getInputs(), dim: conDim);
1189
1190 // %t = concatenate %s1, %s2, %s3 {dim = 1}
1191 // ==>
1192 // if (isSparseDst)
1193 // if (allDense)
1194 // %tmp = bufferization.alloc_tensor dstTp
1195 // else
1196 // %tmp = bufferization.alloc_tensor : unordered COO
1197 // else
1198 // %tmp = memref.alloc : dense tensor
1199 // foreach in %s1 : insert d0, d1, %tmp
1200 // foreach in %s2 : insert d0, d1 + size(s1), %tmp
1201 // foreach in %s3 : insert d0, d1 + size(s1) + size(s2), %tmp
1202
1203 TensorLike dstBuf(rewriter, loc, dstTp.getRankedTensorType(), sizes);
1204 Value offset = constantIndex(builder&: rewriter, loc, i: 0);
1205 Value iterArg = dstBuf.val;
1206
1207 ForeachOp foreachOp;
1208 for (Value input : op.getInputs()) {
1209 // Builds a for op for each input tensor to append new values into the
1210 // output tensor.
1211 foreachOp = ForeachOp::create(
1212 builder&: rewriter, location: loc, tensor: input, iterArgs: iterArg,
1213 bodyBuilder: [&](OpBuilder &builder, Location loc, ValueRange dcvs, Value v,
1214 ValueRange reduc) {
1215 SmallVector<Value> offDimCrd(dcvs);
1216 offDimCrd[conDim] =
1217 arith::AddIOp::create(builder, location: loc, lhs: offDimCrd[conDim], rhs: offset);
1218
1219 // Enters foreach, updates the SSA chain.
1220 dstBuf.val = reduc.front();
1221 if (!dstTp.isAllDense()) {
1222 Value cond = genIsNonzero(builder, loc, v);
1223 auto ifOp =
1224 scf::IfOp::create(builder, location: loc, resultTypes: reduc.getTypes(), cond,
1225 /*else*/ withElseRegion: true);
1226 builder.setInsertionPointToStart(&ifOp.getElseRegion().front());
1227 scf::YieldOp::create(builder, location: loc, results: dstBuf.val);
1228
1229 builder.setInsertionPointToStart(&ifOp.getThenRegion().front());
1230 dstBuf.insert(builder, loc, v, crds: offDimCrd);
1231 scf::YieldOp::create(builder, location: loc, results: dstBuf.val);
1232
1233 // Exits the ifOp, update the sparse tensor SSA value.
1234 builder.setInsertionPointAfter(ifOp);
1235 dstBuf.val = ifOp.getResult(i: 0);
1236 } else {
1237 dstBuf.insert(builder, loc, v, crds: offDimCrd);
1238 }
1239 sparse_tensor::YieldOp::create(builder, location: loc, yieldVal: dstBuf.val);
1240 });
1241 // Accumulates the offset. Note that only static-shaped inputs are allowed
1242 // by concatenate op verifier, which saves us from computing the offset
1243 // dynamically.
1244 const Size sz = getSparseTensorType(val: input).getDynamicDimSize(d: conDim);
1245 assert(ShapedType::isStatic(sz));
1246 offset = arith::AddIOp::create(builder&: rewriter, location: loc, lhs: offset,
1247 rhs: constantIndex(builder&: rewriter, loc, i: sz));
1248 iterArg = foreachOp.getResult(i: 0);
1249 dstBuf.val = iterArg;
1250 }
1251
1252 dstBuf.val = iterArg;
1253 Value ret = dstBuf.finalize(builder&: rewriter, loc, rtp: dstTp.getRankedTensorType());
1254 rewriter.replaceOp(op, newValues: ret);
1255 return success();
1256 }
1257};
1258
1259struct DirectConvertRewriter : public OpRewritePattern<ConvertOp> {
1260 using Base::Base;
1261 LogicalResult matchAndRewrite(ConvertOp op,
1262 PatternRewriter &rewriter) const override {
1263 if (op.needsExtraSort())
1264 return op.emitError(message: "ConvertOp not staged.");
1265
1266 // TODO: Maybe we want a different operation for this too.
1267 auto encDst = getSparseTensorEncoding(type: op.getType());
1268 auto encSrc = getSparseTensorEncoding(type: op.getSource().getType());
1269 if (encDst && encSrc && !encSrc.isSlice() &&
1270 encSrc.withoutBitWidths() == encDst.withoutBitWidths()) {
1271 // Trivial tensor conversion and simple element type conversion is handled
1272 // in codegen.
1273 return failure();
1274 }
1275
1276 Location loc = op.getLoc();
1277 Value src = op.getSource();
1278
1279 SparseTensorType srcStt = getSparseTensorType(val: op.getSource());
1280 SparseTensorType dstStt = getSparseTensorType(val: op.getDest());
1281
1282 bool fromSparseConst = false;
1283 if (auto constOp = op.getSource().getDefiningOp<arith::ConstantOp>())
1284 if (isa<SparseElementsAttr>(Val: constOp.getValue()))
1285 fromSparseConst = true;
1286
1287 const AffineMapAttr foreachOrder =
1288 (!dstStt.isIdentity() && fromSparseConst)
1289 ? AffineMapAttr::get(value: dstStt.getExpandedDimToLvl())
1290 : nullptr;
1291
1292 bool skipZeroCheck = srcStt.hasEncoding() || fromSparseConst;
1293
1294 SmallVector<Value> sizes;
1295 sizesFromSrc(builder&: rewriter, sizes, loc, src);
1296 ValueRange vs;
1297 TensorLike dstBuf(rewriter, loc, dstStt.getRankedTensorType(), sizes);
1298
1299 auto foreachOp = ForeachOp::create(
1300 builder&: rewriter, location: loc, tensor: src, iterArgs: dstBuf.val, order: foreachOrder,
1301 odsArg3: [&](OpBuilder &builder, Location loc, ValueRange dcvs, Value v,
1302 ValueRange reduc) {
1303 // Enters the loop, update the SSA value for insertion chain.
1304 dstBuf.val = reduc.front();
1305 if (!skipZeroCheck) {
1306 Value cond = genIsNonzero(builder, loc, v);
1307 auto ifOp = scf::IfOp::create(builder, location: loc, resultTypes: reduc.getTypes(), cond,
1308 /*else*/ withElseRegion: true);
1309 builder.setInsertionPointToStart(&ifOp.getElseRegion().front());
1310 scf::YieldOp::create(builder, location: loc, results: dstBuf.val);
1311
1312 builder.setInsertionPointToStart(&ifOp.getThenRegion().front());
1313 dstBuf.insert(builder, loc, v, crds: dcvs);
1314 scf::YieldOp::create(builder, location: loc, results: dstBuf.val);
1315
1316 // Exits the ifOp, update the sparse tensor SSA value.
1317 builder.setInsertionPointAfter(ifOp);
1318 dstBuf.val = ifOp.getResult(i: 0);
1319 } else {
1320 dstBuf.insert(builder, loc, v, crds: dcvs);
1321 }
1322 sparse_tensor::YieldOp::create(builder, location: loc, yieldVal: dstBuf.val);
1323 });
1324
1325 rewriter.setInsertionPointAfter(foreachOp);
1326
1327 // Exits the for loop, links the SSA chain.
1328 dstBuf.val = foreachOp.getResult(i: 0);
1329
1330 Value ret = dstBuf.finalize(builder&: rewriter, loc, rtp: dstStt.getRankedTensorType());
1331 rewriter.replaceOp(op, newValues: ret);
1332 return success();
1333 }
1334};
1335
1336struct CrdTranslateRewriter : public OpRewritePattern<CrdTranslateOp> {
1337 using Base::Base;
1338 LogicalResult matchAndRewrite(CrdTranslateOp op,
1339 PatternRewriter &rewriter) const override {
1340 AffineMap map = op.getDirection() == CrdTransDirectionKind::dim2lvl
1341 ? op.getEncoder().getDimToLvl()
1342 : op.getEncoder().getLvlToDim();
1343 if (!map || map.getNumSymbols() != 0)
1344 return failure();
1345
1346 SmallVector<Value> outCrds;
1347 for (AffineExpr result : map.getResults()) {
1348 // TODO: we should probably expand the affine map to IR using our own
1349 // rules, since affine.apply assume signed value, while the cooridinates
1350 // we provided must always be signless.
1351 Value trans = affine::AffineApplyOp::create(
1352 builder&: rewriter, location: op.getLoc(), map: AffineMap::get(dimCount: map.getNumDims(), symbolCount: 0, result),
1353 mapOperands: op.getInCrds());
1354 outCrds.push_back(Elt: trans);
1355 }
1356 rewriter.replaceOp(op, newValues: outCrds);
1357 return success();
1358 }
1359};
1360
1361/// Sparse rewriting rule for the foreach operator.
1362struct ForeachRewriter : public OpRewritePattern<ForeachOp> {
1363public:
1364 using Base::Base;
1365
1366 LogicalResult matchAndRewrite(ForeachOp op,
1367 PatternRewriter &rewriter) const override {
1368
1369 auto loc = op.getLoc();
1370 Value input = op.getTensor();
1371 SmallVector<Value> reduc = op.getInitArgs();
1372 const auto stt = getSparseTensorType(val: input);
1373 const Level lvlRank = stt.getLvlRank();
1374
1375 // Special-case: for each over a sparse constant uses its own rewriting
1376 // rule.
1377 if (auto constOp = input.getDefiningOp<arith::ConstantOp>()) {
1378 if (auto attr = dyn_cast<SparseElementsAttr>(Val: constOp.getValue())) {
1379 return genForeachOnSparseConstant(op, rewriter, attr);
1380 }
1381 }
1382
1383 // Otherwise, use loop emitter to generate loops.
1384 const auto enc = stt.getEncoding();
1385
1386 // Special-case: rank-0 tensors have no dimensions to loop over.
1387 // The LoopEmitter (getValPosits) requires at least one loop level, so
1388 // handle scalar tensors separately.
1389 if (lvlRank == 0) {
1390 // Sparse rank-0 tensors are not yet supported.
1391 if (enc)
1392 return rewriter.notifyMatchFailure(
1393 arg&: op, msg: "foreach over rank-0 sparse tensors is not supported");
1394 // Dense rank-0 tensor: bufferize and load the single element once,
1395 // then inline the body without any surrounding loop.
1396 LoopEmitter loopEmitter(
1397 ValueRange{input},
1398 StringAttr::get(context: getContext(), bytes: ForeachOp::getOperationName()));
1399 loopEmitter.initializeLoopEmit(builder&: rewriter, loc);
1400 Value vals = loopEmitter.getValBuffer()[0];
1401 Value val = memref::LoadOp::create(builder&: rewriter, location: loc, memref: vals, indices: ValueRange{});
1402 // Rank-0 has no coordinates; body args = [value, reductions...].
1403 SmallVector<Value> args = {val};
1404 args.append(RHS: reduc);
1405 Block *srcBlock = op.getBody();
1406 Operation *terminator = srcBlock->getTerminator();
1407 SmallVector<Value> reducValue(terminator->getOperands());
1408 // Remap any block-arg entries in reducValue to their post-inline values
1409 // before the terminator is erased and the block is inlined, because
1410 // inlineBlockBefore() will detach the block args.
1411 for (Value &v : reducValue)
1412 if (auto ba = dyn_cast<BlockArgument>(Val&: v))
1413 if (ba.getOwner() == srcBlock)
1414 v = args[ba.getArgNumber()];
1415 rewriter.eraseOp(op: terminator);
1416 Operation &last = rewriter.getBlock()->back();
1417 if (llvm::isa<scf::YieldOp>(Val: last))
1418 rewriter.setInsertionPoint(&last);
1419 rewriter.inlineBlockBefore(source: srcBlock, dest: rewriter.getBlock(),
1420 before: rewriter.getInsertionPoint(), argValues: args);
1421 rewriter.setInsertionPointToEnd(rewriter.getBlock());
1422 rewriter.replaceOp(op, newValues: reducValue);
1423 return success();
1424 }
1425
1426 // 1. Generates loop for the sparse input.
1427 LoopEmitter loopEmitter(
1428 ValueRange{input},
1429 StringAttr::get(context: getContext(), bytes: ForeachOp::getOperationName()));
1430 loopEmitter.initializeLoopEmit(builder&: rewriter, loc);
1431 for (Level l = 0; l < lvlRank; l++) {
1432 // TODO: provide utility function for loop sequences that only contains
1433 // one for loop?
1434 const SmallVector<TensorLevel, 1> tidLvls{
1435 loopEmitter.makeTensorLevel(t: 0, l)};
1436 loopEmitter.enterNewLoopSeq(builder&: rewriter, loc, tidLvls);
1437 // Note that reduc will be taken care of by loop emitter and get updated
1438 // in place.
1439 loopEmitter.enterCoIterationOverTensorsAtLvls(builder&: rewriter, loc, tidLvls, numCases: 1,
1440 reduc);
1441 }
1442
1443 SmallVector<Value> lcvs = loopEmitter.getLoopIVs();
1444 if (op.getOrder()) {
1445 // TODO: Support it so that we can do direct conversion from CSR->BSR.
1446 llvm_unreachable(
1447 "Level order not yet implemented on non-constant input tensors.");
1448 }
1449
1450 Value vals = loopEmitter.getValBuffer()[0];
1451 SmallVector<Value> pos = loopEmitter.getValPosits(tid: 0);
1452 // Loads the value from sparse tensor using position-index;
1453 // loads the value from dense tensor using coords.
1454 Value val = enc ? memref::LoadOp::create(builder&: rewriter, location: loc, memref: vals, indices: pos)
1455 : memref::LoadOp::create(builder&: rewriter, location: loc, memref: vals, indices: lcvs);
1456
1457 // 2. Inline the block in the foreach operator.
1458 Block *srcBlock = op.getBody();
1459
1460 // Remap coordinates.
1461 SmallVector<Value> args =
1462 enc.translateCrds(builder&: rewriter, loc, crds: lcvs, CrdTransDirectionKind::lvl2dim);
1463
1464 // Remap value.
1465 args.push_back(Elt: val);
1466 // Remap reduction variables.
1467 args.append(RHS: reduc);
1468
1469 // Remove sparse_tensor.yield.
1470 SmallVector<Value> reducValue = srcBlock->getTerminator()->getOperands();
1471 rewriter.eraseOp(op: srcBlock->getTerminator());
1472
1473 Operation &last = rewriter.getBlock()->back();
1474 if (llvm::isa<scf::YieldOp>(Val: last)) {
1475 // Because `scf.for` inserts an implicit yield op when there is no
1476 // reduction variable upon creation, we reset the insertion point such
1477 // that the block is inlined before *before* the yield op.
1478 rewriter.setInsertionPoint(&last);
1479 }
1480
1481 rewriter.inlineBlockBefore(source: srcBlock, dest: rewriter.getBlock(),
1482 before: rewriter.getInsertionPoint(), argValues: args);
1483 rewriter.setInsertionPointToEnd(rewriter.getBlock());
1484 for (Level l = 0; l < lvlRank; l++) {
1485 // Link the reduction chain. Note that loop emitter update the reducValue
1486 // in place.
1487 loopEmitter.exitCurrentLoop(rewriter, loc, reduc: reducValue);
1488 loopEmitter.exitCurrentLoopSeq(builder&: rewriter, loc);
1489 }
1490
1491 // Replace the foreach operator with the value returned by the outtermost
1492 // for loop.
1493 rewriter.replaceOp(op, newValues: reducValue);
1494 return success();
1495 }
1496};
1497
1498/// Sparse rewriting rule for the new operator.
1499struct NewRewriter : public OpRewritePattern<NewOp> {
1500 using Base::Base;
1501 LogicalResult matchAndRewrite(NewOp op,
1502 PatternRewriter &rewriter) const override {
1503 Location loc = op.getLoc();
1504 auto stt = getSparseTensorType(val: op.getResult());
1505 if (!stt.hasEncoding() || stt.getAoSCOOStart() == 0)
1506 return failure();
1507
1508 // Implement the NewOp as follows:
1509 // %orderedCoo = sparse_tensor.new %filename
1510 // %t = sparse_tensor.convert %orderedCoo
1511 // with enveloping reinterpreted_map ops for non-permutations.
1512 RankedTensorType dstTp = stt.getRankedTensorType();
1513 RankedTensorType cooTp = stt.getCOOType(/*ordered=*/true);
1514 Value cooTensor = NewOp::create(builder&: rewriter, location: loc, result: cooTp, source: op.getSource());
1515 Value convert = cooTensor;
1516 auto enc = stt.getEncoding();
1517 if (!stt.isPermutation()) { // demap coo, demap dstTp
1518 auto coo = getSparseTensorType(val: cooTensor).getEncoding().withoutDimToLvl();
1519 convert = ReinterpretMapOp::create(builder&: rewriter, location: loc, dstEnc: coo, source: convert);
1520 dstTp = getSparseTensorType(val: convert).withEncoding(newEnc: enc.withoutDimToLvl());
1521 }
1522 convert = ConvertOp::create(builder&: rewriter, location: loc, dest: dstTp, source: convert);
1523 if (!stt.isPermutation()) // remap to original enc
1524 convert = ReinterpretMapOp::create(builder&: rewriter, location: loc, dstEnc: enc, source: convert);
1525 rewriter.replaceOp(op, newValues: convert);
1526
1527 // Release the temporary ordered COO tensor.
1528 rewriter.setInsertionPointAfterValue(convert);
1529 DeallocTensorOp::create(builder&: rewriter, location: loc, tensor: cooTensor);
1530
1531 return success();
1532 }
1533};
1534
1535/// Sparse rewriting rule for the out operator.
1536struct OutRewriter : public OpRewritePattern<OutOp> {
1537 using Base::Base;
1538 LogicalResult matchAndRewrite(OutOp op,
1539 PatternRewriter &rewriter) const override {
1540 Location loc = op.getLoc();
1541 // Calculate NNZ.
1542 Value src = op.getTensor();
1543 Value nnz = NumberOfEntriesOp::create(builder&: rewriter, location: loc, tensor: src);
1544
1545 // Allocate a temporary buffer for storing dimension-sizes/coordinates.
1546 const auto srcTp = getSparseTensorType(val: src);
1547 const Dimension dimRank = srcTp.getDimRank();
1548 Type indexTp = rewriter.getIndexType();
1549 Value dimSizes = genAlloca(builder&: rewriter, loc, sz: dimRank, tp: indexTp);
1550
1551 // Generate code to calculate dimension size values and store the values to
1552 // the buffer.
1553 SmallVector<Value> dims;
1554 sizesForTensor(builder&: rewriter, sizes&: dims, loc, stp: srcTp, tensor: src);
1555 for (Dimension d = 0; d < dimRank; d++) {
1556 memref::StoreOp::create(builder&: rewriter, location: loc, valueToStore: dims[d], memref: dimSizes,
1557 indices: constantIndex(builder&: rewriter, loc, i: d));
1558 }
1559
1560 // Create a sparse tensor writer and output meta data.
1561 Type opaqueTp = getOpaquePointerType(builder&: rewriter);
1562 Value writer =
1563 createFuncCall(builder&: rewriter, loc, name: "createSparseTensorWriter", resultType: {opaqueTp},
1564 operands: {op.getDest()}, emitCInterface: EmitCInterface::Off)
1565 .getResult(i: 0);
1566 Value rankValue = constantIndex(builder&: rewriter, loc, i: dimRank);
1567 createFuncCall(builder&: rewriter, loc, name: "outSparseTensorWriterMetaData", resultType: {},
1568 operands: {writer, rankValue, nnz, dimSizes}, emitCInterface: EmitCInterface::On);
1569
1570 Value dimCoords = dimSizes; // Reuse the dimSizes buffer for dimCoords.
1571 Type eltTp = srcTp.getElementType();
1572 SmallString<29> outNextFuncName{"outSparseTensorWriterNext",
1573 primaryTypeFunctionSuffix(elemTp: eltTp)};
1574 Value value = genAllocaScalar(builder&: rewriter, loc, tp: eltTp);
1575 ModuleOp module = op->getParentOfType<ModuleOp>();
1576
1577 // For each element in the source tensor, output the element.
1578 ForeachOp::create(
1579 builder&: rewriter, location: loc, tensor: src, iterArgs: ValueRange(),
1580 bodyBuilder: [&](OpBuilder &builder, Location loc, ValueRange dcvs, Value v,
1581 ValueRange reduc) {
1582 for (Dimension d = 0; d < dimRank; d++) {
1583 memref::StoreOp::create(builder&: rewriter, location: loc, valueToStore: dcvs[d], memref: dimCoords,
1584 indices: constantIndex(builder, loc, i: d));
1585 }
1586 memref::StoreOp::create(builder&: rewriter, location: loc, valueToStore: v, memref: value);
1587 SmallVector<Value> operands{writer, rankValue, dimCoords, value};
1588 FlatSymbolRefAttr fn = getFunc(module, name: outNextFuncName, resultType: {}, operands,
1589 emitCInterface: EmitCInterface::On);
1590 func::CallOp::create(builder, location: loc, results: TypeRange(), callee: fn, operands);
1591 sparse_tensor::YieldOp::create(builder, location: loc);
1592 });
1593
1594 // Release the writer.
1595 createFuncCall(builder&: rewriter, loc, name: "delSparseTensorWriter", resultType: {}, operands: {writer},
1596 emitCInterface: EmitCInterface::Off);
1597
1598 rewriter.eraseOp(op);
1599 return success();
1600 }
1601};
1602
1603} // namespace
1604
1605//===---------------------------------------------------------------------===//
1606// Methods that add patterns described in this file to a pattern list.
1607//===---------------------------------------------------------------------===//
1608
1609void mlir::populatePreSparsificationRewriting(RewritePatternSet &patterns) {
1610 patterns.add<FuseExtractSliceWithConcat, FoldConvertIntoProducer,
1611 FoldInvariantYield, FuseSparseMultiplyOverAdd, FuseTensorCast,
1612 GenSemiRingReduction, GenSemiRingSelect, PrintRewriter>(
1613 arg: patterns.getContext());
1614}
1615
1616void mlir::populateLowerSparseOpsToForeachPatterns(RewritePatternSet &patterns,
1617 bool enableRT,
1618 bool enableConvert) {
1619 patterns.add<ConcatenateRewriter, ReshapeRewriter<tensor::ExpandShapeOp>,
1620 ReshapeRewriter<tensor::CollapseShapeOp>,
1621 Sparse2SparseReshapeRewriter<tensor::ExpandShapeOp>,
1622 Sparse2SparseReshapeRewriter<tensor::CollapseShapeOp>,
1623 SparseTensorDimOpRewriter, TensorReshapeRewriter, OutRewriter>(
1624 arg: patterns.getContext());
1625
1626 if (enableConvert)
1627 patterns.add<DirectConvertRewriter>(arg: patterns.getContext());
1628 if (!enableRT)
1629 patterns.add<NewRewriter>(arg: patterns.getContext());
1630}
1631
1632void mlir::populateLowerForeachToSCFPatterns(RewritePatternSet &patterns) {
1633 // Run CrdTranslateRewriter later in the pipeline so that operation can be
1634 // folded before lowering to affine.apply
1635 patterns.add<CrdTranslateRewriter, ForeachRewriter>(arg: patterns.getContext());
1636}
1637