1//===- Sparsification.cpp - Implementation of sparsification --------------===//
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 converting sparse tensor types to actual sparse code.
10//
11//===----------------------------------------------------------------------===//
12
13#include "Utils/CodegenEnv.h"
14#include "Utils/CodegenUtils.h"
15#include "Utils/LoopEmitter.h"
16
17#include "mlir/Dialect/Arith/IR/Arith.h"
18#include "mlir/Dialect/Bufferization/IR/BufferizableOpInterface.h"
19#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
20#include "mlir/Dialect/Func/IR/FuncOps.h"
21#include "mlir/Dialect/Linalg/IR/Linalg.h"
22#include "mlir/Dialect/Linalg/Utils/Utils.h"
23#include "mlir/Dialect/MemRef/IR/MemRef.h"
24#include "mlir/Dialect/SCF/IR/SCF.h"
25#include "mlir/Dialect/SCF/Transforms/Transforms.h"
26#include "mlir/Dialect/SparseTensor/IR/SparseTensor.h"
27#include "mlir/Dialect/SparseTensor/IR/SparseTensorType.h"
28#include "mlir/Dialect/SparseTensor/Transforms/Passes.h"
29#include "mlir/Dialect/SparseTensor/Utils/Merger.h"
30#include "mlir/Dialect/Tensor/IR/Tensor.h"
31
32#include <optional>
33
34using namespace mlir;
35using namespace mlir::sparse_tensor;
36
37//===----------------------------------------------------------------------===//
38// Sparsifier analysis methods.
39//===----------------------------------------------------------------------===//
40
41/// Returns true iff affine expression is invariant. Sets the
42/// parameter `isCurrentLoop` when expression just became invariant.
43static bool isInvariantAffine(AffineExpr a, LoopId curr, bool &isCurrentLoop) {
44 switch (a.getKind()) {
45 case AffineExprKind::DimId: {
46 const LoopId i = cast<AffineDimExpr>(Val&: a).getPosition();
47 if (i + 1 == curr) {
48 isCurrentLoop = true;
49 return true; // becomes invariant at current loop
50 }
51 return i < curr; // invariant when already generated
52 }
53 case AffineExprKind::Add:
54 case AffineExprKind::Mul: {
55 auto binOp = cast<AffineBinaryOpExpr>(Val&: a);
56 return isInvariantAffine(a: binOp.getLHS(), curr, isCurrentLoop) &&
57 isInvariantAffine(a: binOp.getRHS(), curr, isCurrentLoop);
58 }
59 default: {
60 assert(isa<AffineConstantExpr>(a));
61 return true;
62 }
63 }
64}
65
66/// Helper method to inspect affine expressions. Rejects cases where the
67/// same index is used more than once. Also rejects compound affine
68/// expressions in sparse dimensions.
69static bool findAffine(Merger &merger, TensorId tid, Level lvl, AffineExpr a,
70 LevelType lt, bool setLvlFormat = true) {
71 switch (a.getKind()) {
72 case AffineExprKind::DimId: {
73 const LoopId idx = merger.makeLoopId(i: cast<AffineDimExpr>(Val&: a).getPosition());
74 if (!isUndefLT(lt: merger.getLvlType(t: tid, i: idx)))
75 return false; // used more than once
76 if (setLvlFormat)
77 merger.setLevelAndType(t: tid, i: idx, lvl, lt);
78 return true;
79 }
80 case AffineExprKind::Add:
81 case AffineExprKind::Mul:
82 case AffineExprKind::Constant: {
83 assert(lt.hasDenseSemantic());
84 if (auto binOp = dyn_cast<AffineBinaryOpExpr>(Val&: a)) {
85 // We do not set dim level format for affine expression like d0 + d1 on
86 // either loop index at d0 or d1. We continue the recursion merely to
87 // check whether current affine is admissible or not.
88 return findAffine(merger, tid, lvl, a: binOp.getLHS(), lt, setLvlFormat: false) &&
89 findAffine(merger, tid, lvl, a: binOp.getRHS(), lt, setLvlFormat: false);
90 }
91 // Falls through when it is a constant Affine
92 return true;
93 }
94 default:
95 return false;
96 }
97}
98
99/// Helper method to inspect affine expressions for index variable reduction
100/// based codegen. It finds the dependent index set for all tensor levels in the
101/// current expression we are generating.
102///
103/// For example, when handling A[i+j][j+k], we build the two way mapping in
104/// merger between (tensor, level) pairs and their dependent index variable set:
105/// A_0 <=> [i, j] and A_1 <=> [j, k]
106///
107/// It rejects cases (returns false)
108/// 1st, when the same index is used more than once, e.g., A[i+j][i]
109/// 2nd, when multiplication is used in the non-trivial index expression.
110/// 3rd, when a constant operand is used in the non-trivial index expression.
111///
112/// TODO: constant should be easy to handle.
113static bool findDepIdxSet(Merger &merger, TensorId tensor, Level lvl,
114 AffineExpr a, LevelType lt, bool isSubExp = false,
115 int64_t coefficient = 1) {
116 switch (a.getKind()) {
117 case AffineExprKind::DimId: {
118 // Only allow positive coefficients on AffineDimExpr.
119 if (coefficient <= 0)
120 return false;
121
122 const LoopId idx = merger.makeLoopId(i: cast<AffineDimExpr>(Val&: a).getPosition());
123 if (!isUndefLT(lt: merger.getLvlType(t: tensor, i: idx)))
124 return false; // used more than once, e.g., A[i][i]
125
126 // TODO: Generalizes the following two cases. A[i] (with trivial index
127 // expression) can be treated as a special affine index expression. We do
128 // not necessarily need to differentiate them.
129 if (!isSubExp) {
130 assert(coefficient == 1);
131 merger.setLevelAndType(t: tensor, i: idx, lvl, lt);
132 }
133
134 if (isSubExp) {
135 // The current loops appears in more than one affine expressions on the
136 // same tensor. We can not handle this case. e.g., A[i+j][i+k], `i` is
137 // used twice.
138 if (merger.hasDependentLvl(i: idx, t: tensor)) {
139 // TODO: This can be supported by coiterate slices if the loop idx is
140 // appeared on affine index for different tensor, or take slice on
141 // multiple dimensions when it is on the same tensor.
142 // E.g.,
143 // `d0 + d1` for indexing t0[lvl0] and `d0 + d2` for indexing t1[lvl0]
144 // d0_1 = getNextSliceOffset t0 along lvl0
145 // d0_2 = getNextSliceOffset t1 along lvl0
146 // if d0_1 == d0_2 then d0 = d0_1 = d0_1
147 // else increase min(d0_1, d0_2).
148 return false;
149 }
150 merger.setLoopDependentTensorLevel(i: idx, t: tensor, lvl, lt, coefficient);
151 }
152 return true;
153 }
154 case AffineExprKind::Constant:
155 case AffineExprKind::Mul: {
156 // TODO: Support index expression like `2 * d0`, we now only support more
157 // complicated cases like `2 * d0 + d1`.
158 if (!isSubExp)
159 return false;
160
161 // TODO: Support Constant AffineExp for slice-based codegen
162 if (isa<AffineConstantExpr>(Val: a))
163 llvm_unreachable("Not yet implemented");
164
165 auto binOp = cast<AffineBinaryOpExpr>(Val&: a);
166 auto lhs = binOp.getLHS(), rhs = binOp.getRHS();
167 if (isa<AffineConstantExpr>(Val: rhs))
168 std::swap(a&: lhs, b&: rhs);
169 // Must be in form of `constant * d`.
170 assert(isa<AffineConstantExpr>(lhs) && isa<AffineDimExpr>(rhs));
171 int64_t coefficient = cast<AffineConstantExpr>(Val&: lhs).getValue();
172 return findDepIdxSet(merger, tensor, lvl, a: rhs, lt, isSubExp, coefficient);
173 }
174 case AffineExprKind::Add: {
175 auto binOp = cast<AffineBinaryOpExpr>(Val&: a);
176 return findDepIdxSet(merger, tensor, lvl, a: binOp.getLHS(), lt, isSubExp: true) &&
177 findDepIdxSet(merger, tensor, lvl, a: binOp.getRHS(), lt, isSubExp: true);
178 }
179 default:
180 return false;
181 }
182}
183
184/// Gets the total number of compound affine expressions in the
185/// `getMatchingIndexingMap` for the given tensor. For the following inputs:
186///
187/// map = (d0, d1, d2) => (d0 + d1 : compressed, d2 : compressed)
188///
189/// Returns 1 (because the first level is compressed and its corresponding
190/// indexing-expression is `d0 + d1`)
191static unsigned getNumNonTrivialIdxExpOnSparseLvls(AffineMap map,
192 Value tensor) {
193 // The `tensor` is not guaranteed to have `RankedTensorType`, therefore
194 // we can't use `getRankedTensorType`/`getSparseTensorType` here.
195 // However, we don't need to handle `StorageSpecifierType`, so we
196 // can use `SparseTensorType` once we guard against non-tensors.
197 const auto rtp = dyn_cast<RankedTensorType>(Val: tensor.getType());
198 if (!rtp)
199 return 0;
200 const SparseTensorType stt(rtp);
201
202 const Level lvlRank = stt.getLvlRank();
203 const auto exprs = map.getResults();
204 assert(static_cast<Dimension>(exprs.size()) == lvlRank &&
205 "AffineMap does not have dimension-rank many results");
206 unsigned num = 0;
207 for (Level l = 0; l < lvlRank; l++) {
208 if (!isa<AffineDimExpr>(Val: exprs[l]) && !stt.getLvlType(l).hasDenseSemantic())
209 num++;
210 }
211 return num;
212}
213
214/// Gets the total number of sparse levels with compound affine
215/// expressions, summed over all operands of the `GenericOp`.
216static unsigned getNumNonTrivialIdxExpOnSparseLvls(linalg::GenericOp op) {
217 unsigned num = 0;
218 for (OpOperand &t : op->getOpOperands())
219 num += getNumNonTrivialIdxExpOnSparseLvls(map: op.getMatchingIndexingMap(opOperand: &t),
220 tensor: t.get());
221 return num;
222}
223
224// Returns true iff output has nontrivial affine indices.
225static bool hasNonTrivialAffineOnSparseOut(linalg::GenericOp op) {
226 OpOperand *out = op.getDpsInitOperand(i: 0);
227 if (getSparseTensorType(val: out->get()).isAllDense())
228 return false;
229 return getNumNonTrivialIdxExpOnSparseLvls(map: op.getMatchingIndexingMap(opOperand: out),
230 tensor: out->get());
231}
232
233/// Helper method to inspect sparse encodings in the tensor types.
234/// Fills the per-dimension sparsity information for all tensors.
235/// Returns true if the sparse annotations and affine subscript
236/// expressions of all tensors are admissible. Returns false if
237/// no annotations are found or inadmissible constructs occur.
238/// We currently support two different ways to handle non-trivial index
239/// expression on sparse tensors, and they accept different affine expressions.
240/// When using dependent index reducton-based approach, it currently only
241/// supports affine addition index expression.
242static bool findSparseAnnotations(CodegenEnv &env, bool idxReducBased) {
243 bool annotated = false;
244 for (OpOperand &t : env.op()->getOpOperands()) {
245 const TensorId tid = env.makeTensorId(t: t.getOperandNumber());
246 const auto map = env.op().getMatchingIndexingMap(opOperand: &t);
247 const auto enc = getSparseTensorEncoding(type: t.get().getType());
248 if (enc)
249 annotated = true;
250 const Level lvlRank = map.getNumResults();
251 assert(!enc || lvlRank == enc.getLvlRank());
252 assert(static_cast<Level>(env.op().getRank(&t)) == lvlRank);
253 // We only need to do index reduction if there is at least one
254 // non-trivial index expression on sparse levels. If all non-trivial
255 // index expression is on dense levels, we can efficiently rely on
256 // the random access to locate the element.
257 bool needIdxReduc =
258 enc && getNumNonTrivialIdxExpOnSparseLvls(map, tensor: t.get()) != 0;
259 // If then current tensor being inspected requires affine index, it need
260 // to be sliced.
261 for (Level l = 0; l < lvlRank; l++) {
262 const AffineExpr a = map.getResult(idx: l);
263 const LevelType lt = enc.getLvlType(l);
264 if (idxReducBased && needIdxReduc) {
265 if (!findDepIdxSet(merger&: env.merger(), tensor: tid, lvl: l, a, lt))
266 return false; // inadmissible affine expression
267 } else {
268 if (!findAffine(merger&: env.merger(), tid, lvl: l, a, lt))
269 return false; // inadmissible affine expression
270 }
271 }
272 }
273 return annotated;
274}
275
276//===----------------------------------------------------------------------===//
277// Sparsifier synthesis methods (statements and expressions).
278//===----------------------------------------------------------------------===//
279
280/// Local bufferization of all dense and sparse data structures.
281static void genBuffers(CodegenEnv &env, OpBuilder &builder) {
282 linalg::GenericOp op = env.op();
283 Location loc = op.getLoc();
284 assert(op.getNumOperands() == op.getNumDpsInputs() + 1);
285
286 SmallVector<Range, 4> loopRange =
287 llvm::cast<linalg::LinalgOp>(Val: op.getOperation())
288 .createLoopRanges(b&: builder, loc);
289
290 env.emitter().initializeLoopEmit(
291 builder, loc,
292 /// Generates buffer for the output tensor.
293 /// Note that all sparse kernels assume that when all elements are written
294 /// to (viz. x(i) = y(i) * z(i)), the output buffer is already initialized
295 /// to all zeroes and only nonzeroes values are computed and written out.
296 /// For updates (viz. x(i) += y(i) * z(i)), only nonzeroes values are used
297 /// for the updates and no assumption on the original contents of the
298 /// output buffer is necessary.
299 updater: [&op](OpBuilder &builder, Location loc, Value memref,
300 Value tensor) -> Value {
301 // Must not be a sparse tensor.
302 assert(!getSparseTensorEncoding(tensor.getType()));
303 // Two output tensor references should point to the same object.
304 OpOperand *lhs = op.getDpsInitOperand(i: 0);
305 assert(lhs->get() == tensor);
306 // An output tensor can simply materialize from the buffer of the tensor
307 // that appears in the outs() clause. For updates, this has the
308 // advantage that only the nonzero value are involved in the
309 // computation, keeping the operation O(nnz). In all other cases, we are
310 // forced to zero out the buffer to enforce the assumption above, which
311 // may negatively impact running complexity (viz. O(n^2 + nnz) vs.
312 // O(nnz) for matrices).
313 // TODO: use better analysis to avoid zeroing out the buffer?
314 bool isInit = op.isInitTensor(opOperand: lhs);
315 Value init = memref;
316 if (!isInit) {
317 Value zero = constantZero(builder, loc,
318 tp: getElementTypeOrSelf(type: tensor.getType()));
319 linalg::FillOp::create(builder, location: loc, inputs: ValueRange{zero},
320 outputs: ValueRange{init});
321 }
322 return init;
323 },
324 synSetter: [&loopRange](OpBuilder &b, Location loc, Level l) {
325 assert(l < loopRange.size());
326 return mlir::getValueOrCreateConstantIndexOp(b, loc, ofr: loopRange[l].size);
327 });
328}
329
330/// Generates index for load/store on sparse tensor.
331static Value genIndex(CodegenEnv &env, OpOperand *t) {
332 const auto map = env.op().getMatchingIndexingMap(opOperand: t);
333 const auto stt = getSparseTensorType(val: t->get());
334 const Level lvlRank = stt.getLvlRank();
335 assert(static_cast<Level>(map.getNumResults()) == lvlRank);
336 const AffineExpr a = map.getResult(idx: lvlRank - 1);
337 assert(a.getKind() == AffineExprKind::DimId);
338 const LoopId idx = env.makeLoopId(i: cast<AffineDimExpr>(Val: a).getPosition());
339 return env.getLoopVar(i: idx);
340}
341
342/// Generates subscript for load/store on a dense or sparse tensor.
343static Value genSubscript(CodegenEnv &env, OpBuilder &builder, OpOperand *t,
344 SmallVectorImpl<Value> &args) {
345 const Location loc = env.op().getLoc();
346 const TensorId tid = env.makeTensorId(t: t->getOperandNumber());
347 const auto map = env.op().getMatchingIndexingMap(opOperand: t);
348 const auto stt = getSparseTensorType(val: t->get());
349 if (stt.hasEncoding()) {
350 // For sparse tensors we only push the last-level's position onto `args`.
351 const auto pos = env.emitter().getValPosits(tid);
352 assert(!pos.empty());
353 args.append(RHS: pos);
354 // Simply returns the tensor to extract value using iterators.
355 if (env.options().sparseEmitStrategy == SparseEmitStrategy::kSparseIterator)
356 return t->get();
357 } else {
358 // For dense tensors we push all level's coordinates onto `args`.
359 const Level lvlRank = stt.getLvlRank();
360 assert(static_cast<Level>(map.getNumResults()) == lvlRank);
361 for (Level l = 0; l < lvlRank; l++) {
362 const auto lvlExpr = map.getResult(idx: l);
363 const auto lvlCrd = env.emitter().genAffine(builder, loc, a: lvlExpr);
364 args.push_back(Elt: lvlCrd);
365 }
366 }
367 return env.emitter().getValBuffer()[tid];
368}
369
370/// Generates insertion code to implement dynamic tensor load.
371static Value genInsertionLoad(CodegenEnv &env, OpBuilder &builder,
372 OpOperand *t) {
373 linalg::GenericOp op = env.op();
374 Location loc = op.getLoc();
375 // Direct lexicographic coordinate order, tensor loads as zero.
376 if (!env.isExpand()) {
377 Type tp = getElementTypeOrSelf(type: t->get().getType());
378 return constantZero(builder, loc, tp);
379 }
380 // Load from expanded access pattern.
381 Value index = genIndex(env, t);
382 return memref::LoadOp::create(builder, location: loc, memref: env.getExpandValues(), indices: index);
383}
384
385/// Generates insertion code to implement dynamic tensor load for reduction.
386static Value genInsertionLoadReduce(CodegenEnv &env, OpBuilder &builder,
387 OpOperand *t) {
388 linalg::GenericOp op = env.op();
389 Location loc = op.getLoc();
390 Value identity = env.getCustomRedId();
391 // Direct lexicographic coordinate order, tensor loads as identity.
392 if (!env.isExpand())
393 return identity;
394 // Load from expanded access pattern if filled, identity otherwise.
395 Value values = env.getExpandValues();
396 Value filled = env.getExpandFilled();
397 Value index = genIndex(env, t);
398 Value isFilled = memref::LoadOp::create(builder, location: loc, memref: filled, indices: index);
399 Value valAtIndex = memref::LoadOp::create(builder, location: loc, memref: values, indices: index);
400 return arith::SelectOp::create(builder, location: loc, condition: isFilled, true_value: valAtIndex, false_value: identity);
401}
402
403static Value genConditionalInsert(Location loc, OpBuilder &builder, Value cond,
404 Value sparseOut, ValueRange ivs, Value v) {
405 scf::IfOp condInsert =
406 scf::IfOp::create(builder, location: loc, resultTypes: sparseOut.getType(), cond, withElseRegion: true);
407 // True branch.
408 builder.setInsertionPointToStart(condInsert.thenBlock());
409 Value res = tensor::InsertOp::create(builder, location: loc, scalar: v, dest: sparseOut, indices: ivs);
410 scf::YieldOp::create(builder, location: loc, results: res);
411 // False branch.
412 builder.setInsertionPointToStart(condInsert.elseBlock());
413 scf::YieldOp::create(builder, location: loc, results: sparseOut);
414 // Value assignment.
415 builder.setInsertionPointAfter(condInsert);
416 return condInsert.getResult(i: 0);
417}
418
419/// Generates insertion code to implement dynamic tensor store.
420static void genInsertionStore(CodegenEnv &env, OpBuilder &builder, OpOperand *t,
421 Value rhs) {
422 linalg::GenericOp op = env.op();
423 Location loc = op.getLoc();
424 // Direct insertion in lexicographic coordinate order.
425 if (!env.isExpand()) {
426 const LoopId numLoops = op.getRank(opOperand: t);
427 // Retrieves the first `numLoop` induction variables.
428 SmallVector<Value> ivs = llvm::to_vector(Range: llvm::drop_end(
429 RangeOrContainer: env.emitter().getLoopIVsRange(), N: env.getCurrentDepth() - numLoops));
430 Value chain = env.getInsertionChain();
431 if (env.isValidLexInsert()) {
432 // Generates runtime check for a valid lex during reduction,
433 // to avoid inserting the identity value for empty reductions.
434 // if (validLexInsert) then
435 // insert(rhs) into chain
436 // return updated chain
437 // else
438 // return unmodified chain
439 Value out = genConditionalInsert(loc, builder, cond: env.getValidLexInsert(),
440 sparseOut: chain, ivs, v: rhs);
441 env.updateInsertionChain(chain: out);
442 } else {
443 Value sparseOut;
444 if (!hasAnySparseType(types: env.op().getInputs().getTypes())) {
445 // This is an all-dense -> sparse kernel, test rhs != 0 before
446 // insertion.
447 Value nz = genIsNonzero(builder, loc, v: rhs);
448 sparseOut = genConditionalInsert(loc, builder, cond: nz, sparseOut: chain, ivs, v: rhs);
449 } else {
450 sparseOut = tensor::InsertOp::create(builder, location: loc, scalar: rhs, dest: chain, indices: ivs);
451 }
452 // Generates regular insertion chain.
453 env.updateInsertionChain(chain: sparseOut);
454 }
455 return;
456 }
457 // Generates insertion code along expanded access pattern.
458 // if (!expFilled[i]) then
459 // expFilled[i] = true
460 // expAdded[inserts++] = i
461 // endif
462 // values[i] = rhs
463 Value values = env.getExpandValues();
464 Value filled = env.getExpandFilled();
465 Value added = env.getExpandAdded();
466 Value count = env.getExpandCount();
467 Value index = genIndex(env, t);
468 Value fval = constantI1(builder, loc, b: false);
469 Value tval = constantI1(builder, loc, b: true);
470 // If statement.
471 Value isFilled = memref::LoadOp::create(builder, location: loc, memref: filled, indices: index);
472 Value cond = arith::CmpIOp::create(builder, location: loc, predicate: arith::CmpIPredicate::eq,
473 lhs: isFilled, rhs: fval);
474 scf::IfOp ifOp = scf::IfOp::create(builder, location: loc, resultTypes: builder.getIndexType(), cond,
475 /*else=*/withElseRegion: true);
476 // True branch.
477 builder.setInsertionPointToStart(&ifOp.getThenRegion().front());
478 memref::StoreOp::create(builder, location: loc, valueToStore: tval, memref: filled, indices: index);
479 memref::StoreOp::create(builder, location: loc, valueToStore: index, memref: added, indices: count);
480 Value one = constantIndex(builder, loc, i: 1);
481 Value add = arith::AddIOp::create(builder, location: loc, lhs: count, rhs: one);
482 scf::YieldOp::create(builder, location: loc, results: add);
483 // False branch.
484 builder.setInsertionPointToStart(&ifOp.getElseRegion().front());
485 scf::YieldOp::create(builder, location: loc, results: count);
486 builder.setInsertionPointAfter(ifOp);
487 // Value assignment.
488 env.updateExpandCount(count: ifOp.getResult(i: 0));
489 memref::StoreOp::create(builder, location: loc, valueToStore: rhs, memref: values, indices: index);
490}
491
492/// Generates a load on a dense or sparse tensor.
493static Value genTensorLoad(CodegenEnv &env, OpBuilder &builder, ExprId exp) {
494 // Test if the load was hoisted to a higher loop nest.
495 Value val = env.exp(e: exp).val;
496 if (val)
497 return val;
498 // Get tensor operand.
499 linalg::GenericOp op = env.op();
500 Location loc = op.getLoc();
501 OpOperand *t = &op->getOpOperand(idx: env.exp(e: exp).tensor);
502 // Fold binary-valued tensor into explicit value.
503 const auto stt = getSparseTensorType(val: t->get());
504 if (auto explVal = stt.getExplicitVal())
505 return genValFromAttr(builder, loc, attr: explVal);
506 // Load during insertion.
507 if (env.isSparseOutput(o: t)) {
508 if (env.isCustomReduc())
509 return genInsertionLoadReduce(env, builder, t);
510 return genInsertionLoad(env, builder, t);
511 }
512
513 // Actual load.
514 SmallVector<Value> args;
515 Value ptr = genSubscript(env, builder, t, args);
516 if (llvm::isa<TensorType>(Val: ptr.getType())) {
517 assert(env.options().sparseEmitStrategy ==
518 SparseEmitStrategy::kSparseIterator);
519 return ExtractValOp::create(builder, location: loc, tensor: ptr,
520 iterator: llvm::getSingleElement(C&: args));
521 }
522 return memref::LoadOp::create(builder, location: loc, memref: ptr, indices: args);
523}
524
525/// Generates a store on a dense or sparse tensor.
526static void genTensorStore(CodegenEnv &env, OpBuilder &builder, ExprId exp,
527 Value rhs) {
528 // Only unary and binary are allowed to return an uninitialized rhs
529 // to indicate missing output. Or otherwise a custom reduction that
530 // received no value to accumulate.
531 if (!rhs) {
532 assert(env.exp(exp).kind == TensorExp::Kind::kUnary ||
533 env.exp(exp).kind == TensorExp::Kind::kBinary ||
534 env.exp(exp).kind == TensorExp::Kind::kReduce);
535 return;
536 }
537 // Test if this is a scalarized reduction.
538 if (env.isReduc()) {
539 env.updateReduc(val: rhs);
540 return;
541 }
542 // Regular store.
543 linalg::GenericOp op = env.op();
544 Location loc = op.getLoc();
545 OpOperand *t = op.getDpsInitOperand(i: 0);
546 if (!env.isSparseOutput(o: t)) {
547 SmallVector<Value> args;
548 Value ptr = genSubscript(env, builder, t, args);
549 memref::StoreOp::create(builder, location: loc, valueToStore: rhs, memref: ptr, indices: args);
550 return;
551 }
552 // Store during sparse insertion.
553 if (env.exp(e: exp).kind != TensorExp::Kind::kSelect) {
554 genInsertionStore(env, builder, t, rhs);
555 return;
556 }
557 // Select operation insertion.
558 Value chain = env.getInsertionChain();
559 scf::IfOp ifOp =
560 scf::IfOp::create(builder, location: loc, resultTypes: chain.getType(), cond: rhs, /*else=*/withElseRegion: true);
561 builder.setInsertionPointToStart(&ifOp.getThenRegion().front());
562 // Existing value was preserved to be used here.
563 assert(env.exp(exp).val);
564 Value v0 = env.exp(e: exp).val;
565 genInsertionStore(env, builder, t, rhs: v0);
566 env.merger().clearExprValue(e: exp);
567 // Yield modified insertion chain along true branch.
568 Value mchain = env.getInsertionChain();
569 scf::YieldOp::create(builder, location: op.getLoc(), results: mchain);
570 // Yield original insertion chain along false branch.
571 builder.setInsertionPointToStart(&ifOp.getElseRegion().front());
572 scf::YieldOp::create(builder, location: loc, results: chain);
573 // Done with if statement.
574 env.updateInsertionChain(chain: ifOp->getResult(idx: 0));
575 builder.setInsertionPointAfter(ifOp);
576}
577
578/// Generates an invariant value.
579inline static Value genInvariantValue(CodegenEnv &env, ExprId exp) {
580 return env.exp(e: exp).val;
581}
582
583/// Semi-ring branches are simply inlined by the sparsifier. Prior
584/// analysis has verified that all computations are "local" to the inlined
585/// branch or otherwise invariantly defined outside the loop nest, with the
586/// exception of index computations, which need to be relinked to actual
587/// inlined cloned code.
588static Value relinkBranch(CodegenEnv &env, RewriterBase &rewriter, Block *block,
589 Value e) {
590 if (auto arg = dyn_cast<BlockArgument>(Val&: e)) {
591 // Direct arguments of the original linalg op must be converted into
592 // tensor element loads. This handles both dense tensor loads (using
593 // current loop coordinates) and sparse tensor loads (using the current
594 // value position tracked by the loop emitter).
595 linalg::GenericOp op = env.op();
596 if (arg.getOwner()->getParentOp() == op) {
597 const TensorId tid = env.makeTensorId(t: arg.getArgNumber());
598 OpOperand *t = &op->getOpOperand(idx: tid);
599 SmallVector<Value> args;
600 Value ptr = genSubscript(env, builder&: rewriter, t, args);
601 Location loc = op.getLoc();
602 if (llvm::isa<TensorType>(Val: ptr.getType())) {
603 // kSparseIterator strategy: extract value at the iterator position.
604 assert(env.options().sparseEmitStrategy ==
605 SparseEmitStrategy::kSparseIterator);
606 return ExtractValOp::create(builder&: rewriter, location: loc, tensor: ptr,
607 iterator: llvm::getSingleElement(C&: args));
608 }
609 return memref::LoadOp::create(builder&: rewriter, location: loc, memref: ptr, indices: args);
610 }
611 } else if (Operation *def = e.getDefiningOp()) {
612 // Handle index computation.
613 if (auto indexOp = dyn_cast<linalg::IndexOp>(Val: def))
614 return env.getLoopVar(i: env.makeLoopId(i: indexOp.getDim()));
615 // When still defined in new body, recurse into operands.
616 if (def->getBlock() == block) {
617 rewriter.setInsertionPoint(def);
618 for (unsigned i = 0, n = def->getNumOperands(); i < n; i++) {
619 rewriter.modifyOpInPlace(root: def, callable: [&]() {
620 def->setOperand(
621 idx: i, value: relinkBranch(env, rewriter, block, e: def->getOperand(idx: i)));
622 });
623 }
624 }
625 }
626 return e;
627}
628
629/// Recursively generates tensor expression.
630static Value genExp(CodegenEnv &env, RewriterBase &rewriter, ExprId e) {
631 if (e == ::mlir::sparse_tensor::detail::kInvalidId)
632 return Value();
633
634 linalg::GenericOp op = env.op();
635 Location loc = op.getLoc();
636 const TensorExp &exp = env.exp(e);
637 const auto kind = exp.kind;
638 if (kind == TensorExp::Kind::kTensor)
639 return genTensorLoad(env, builder&: rewriter, exp: e);
640 if (kind == TensorExp::Kind::kInvariant)
641 return genInvariantValue(env, exp: e);
642 if (kind == TensorExp::Kind::kLoopVar)
643 return env.getLoopVar(i: exp.loop);
644
645 if (kind == TensorExp::Kind::kReduce)
646 env.startCustomReduc(exp: e); // enter custom
647
648 // If either lhs/rhs is a synthetic zero, we infer the type for the zero value
649 // based on the type of the other operand.
650 Value v0, v1;
651 if (exp.children.e0 != ::mlir::sparse_tensor::detail::kInvalidId &&
652 env.exp(e: exp.children.e0).kind == TensorExp::Kind::kSynZero) {
653 v1 = genExp(env, rewriter, e: exp.children.e1);
654 v0 = constantZero(builder&: rewriter, loc, tp: v1.getType());
655 } else if (exp.children.e1 != ::mlir::sparse_tensor::detail::kInvalidId &&
656 env.exp(e: exp.children.e1).kind == TensorExp::Kind::kSynZero) {
657 v0 = genExp(env, rewriter, e: exp.children.e0);
658 v1 = constantZero(builder&: rewriter, loc, tp: v0.getType());
659 } else {
660 v0 = genExp(env, rewriter, e: exp.children.e0);
661 v1 = genExp(env, rewriter, e: exp.children.e1);
662 }
663
664 Value ee;
665 if (kind == TensorExp::Kind::kReduce && (!v0 || !v1)) {
666 // custom reduce did not receive a value
667 } else {
668 ee = env.merger().buildExp(rewriter, loc, e, v0, v1);
669 if (ee &&
670 (kind == TensorExp::Kind::kUnary || kind == TensorExp::Kind::kBinary ||
671 kind == TensorExp::Kind::kBinaryBranch ||
672 kind == TensorExp::Kind::kReduce ||
673 kind == TensorExp::Kind::kSelect)) {
674 OpBuilder::InsertionGuard guard(rewriter);
675 ee = relinkBranch(env, rewriter, block: ee.getParentBlock(), e: ee);
676 }
677 }
678
679 if (kind == TensorExp::Kind::kReduce)
680 env.endCustomReduc(); // exit custom
681
682 if (kind == TensorExp::Kind::kSelect)
683 env.merger().setExprValue(e, v: v0); // Preserve value for later use.
684
685 return ee;
686}
687
688/// Hoists loop invariant tensor loads for which indices have been exhausted.
689static void genInvariants(CodegenEnv &env, OpBuilder &builder, ExprId exp,
690 LoopId curr, bool isStart) {
691 if (exp == ::mlir::sparse_tensor::detail::kInvalidId)
692 return;
693 if (env.exp(e: exp).kind == TensorExp::Kind::kTensor) {
694 // Inspect tensor indices.
695 linalg::GenericOp op = env.op();
696 OpOperand &t = op->getOpOperand(idx: env.exp(e: exp).tensor);
697 const auto map = op.getMatchingIndexingMap(opOperand: &t);
698 const auto stt = getSparseTensorType(val: t.get());
699 const Level lvlRank = stt.getLvlRank();
700 assert(static_cast<Level>(map.getNumResults()) == lvlRank);
701 bool isCurrentLoop = curr == 0; // for scalar tensors
702 for (Level l = 0; l < lvlRank; l++) {
703 const AffineExpr a = map.getResult(idx: l);
704 if (!isInvariantAffine(a, curr, /*out*/ isCurrentLoop))
705 return; // still in play
706 }
707 // All exhausted at current level.
708 if (!isCurrentLoop)
709 return;
710 // Generate code for a scalarized reduction or invariant. Note that
711 // because custom reduction lhs may occur several times in the IR,
712 // we have a built-in safety for only initializing and wrapping-up
713 // the scalarized reduction once.
714 OpOperand *lhs = op.getDpsInitOperand(i: 0);
715 if (lhs == &t) {
716 // Start or end a scalarized reduction.
717 if (isStart) {
718 if (env.isCustomReduc()) {
719 if (!env.isReduc())
720 env.startReduc(exp, val: env.getCustomRedId());
721 } else {
722 env.startReduc(exp, val: genTensorLoad(env, builder, exp));
723 }
724 if (env.hasSparseOutput())
725 env.startValidLexInsert(
726 val: constantI1(builder, loc: env.op().getLoc(), b: false));
727 } else {
728 if (!env.isCustomReduc() || env.isReduc())
729 genTensorStore(env, builder, exp, rhs: env.endReduc());
730 if (env.hasSparseOutput())
731 env.endValidLexInsert();
732 }
733 } else {
734 // Start or end loop invariant hoisting of a tensor load.
735 if (isStart) {
736 env.merger().setExprValue(e: exp, v: genTensorLoad(env, builder, exp));
737 } else {
738 env.merger().clearExprValue(e: exp);
739 }
740 }
741 } else if (env.exp(e: exp).kind != TensorExp::Kind::kInvariant &&
742 env.exp(e: exp).kind != TensorExp::Kind::kLoopVar &&
743 env.exp(e: exp).kind != TensorExp::Kind::kSynZero) {
744 // Traverse into the binary operations. Note that we only hoist
745 // tensor loads, since subsequent MLIR/LLVM passes know how to
746 // deal with all other kinds of derived loop invariants.
747 if (env.exp(e: exp).kind == TensorExp::Kind::kReduce)
748 env.startCustomReduc(exp); // enter custom
749 const ExprId e0 = env.exp(e: exp).children.e0;
750 const ExprId e1 = env.exp(e: exp).children.e1;
751 genInvariants(env, builder, exp: e0, curr, isStart);
752 genInvariants(env, builder, exp: e1, curr, isStart);
753 if (env.exp(e: exp).kind == TensorExp::Kind::kReduce)
754 env.endCustomReduc(); // exit custom
755 }
756}
757
758/// Generates an expanded access pattern in innermost dimension.
759static void genExpand(CodegenEnv &env, OpBuilder &builder, LoopId curr,
760 bool isStart) {
761 linalg::GenericOp op = env.op();
762 OpOperand *lhs = op.getDpsInitOperand(i: 0);
763 if (!env.atExpandLevel(o: lhs, rank: op.getRank(opOperand: lhs), n: curr))
764 return; // not needed at current level
765 assert(!env.isReduc());
766 // Generate start or end of an expanded access pattern. Note that because
767 // an expansion does not rely on the ongoing contents of the sparse storage
768 // scheme, we can use the original tensor as incoming SSA value (which
769 // simplifies codegen a bit). If expansion on the actual contents is ever
770 // needed, we will need to use the SSA value in the insertion chain instead.
771 Value tensor = lhs->get();
772 Location loc = op.getLoc();
773 if (isStart) {
774 auto dynShape = {ShapedType::kDynamic};
775 Type etp = cast<ShapedType>(Val: tensor.getType()).getElementType();
776 Type t1 = MemRefType::get(shape: dynShape, elementType: etp);
777 Type t2 = MemRefType::get(shape: dynShape, elementType: builder.getI1Type());
778 Type t3 = MemRefType::get(shape: dynShape, elementType: builder.getIndexType());
779 Type t4 = builder.getIndexType();
780 auto r =
781 ExpandOp::create(builder, location: loc, resultTypes: TypeRange({t1, t2, t3, t4}), tensor);
782 assert(r.getNumResults() == 4);
783 env.startExpand(values: r.getResult(i: 0), filled: r.getResult(i: 1), added: r.getResult(i: 2),
784 count: r.getResult(i: 3));
785 } else {
786 SmallVector<Value> indices;
787 for (LoopId i = 0; i < curr; i++)
788 indices.push_back(Elt: env.emitter().getLoopIV(n: i));
789 Value values = env.getExpandValues();
790 Value filled = env.getExpandFilled();
791 Value added = env.getExpandAdded();
792 Value count = env.getExpandCount();
793 Value chain = env.getInsertionChain();
794 Value compress = CompressOp::create(builder, location: loc, values, filled, added,
795 count, tensor: chain, lvlCoords: indices);
796 env.updateInsertionChain(chain: compress);
797 env.endExpand();
798 }
799}
800
801/// Returns parallelization strategy. Any implicit loop in the Linalg
802/// operation that is marked "parallel" is a candidate. Whether it is actually
803/// converted to a parallel operation depends on the requested strategy.
804static bool isParallelFor(CodegenEnv &env, bool isOuter, bool isSparse) {
805 // Reject parallelization of sparse output.
806 if (env.hasSparseOutput())
807 return false;
808 // Parallel loops on tensor expansion can cause data races.
809 if (env.isExpand())
810 return false;
811 // Inspect strategy.
812 switch (env.options().parallelizationStrategy) {
813 case SparseParallelizationStrategy::kNone:
814 return false;
815 case SparseParallelizationStrategy::kDenseOuterLoop:
816 return isOuter && !isSparse;
817 case SparseParallelizationStrategy::kAnyStorageOuterLoop:
818 return isOuter;
819 case SparseParallelizationStrategy::kDenseAnyLoop:
820 return !isSparse;
821 case SparseParallelizationStrategy::kAnyStorageAnyLoop:
822 return true;
823 }
824 llvm_unreachable("unexpected parallelization strategy");
825}
826
827/// Whether or not the current loop being generated should be parallized (if
828/// possible) according to the configuration.
829static bool shouldTryParallize(CodegenEnv &env, LoopId curr,
830 ArrayRef<TensorLevel> tidLvls) {
831 linalg::GenericOp op = env.op();
832 auto iteratorTypes = op.getIteratorTypesArray();
833 bool isSparse = llvm::any_of(Range&: tidLvls, P: [curr, &env](TensorLevel tidLvl) {
834 // Queries the LT based on the tensor and loop id, as requested by
835 // `CodegenEnv::lt(TensorId, LoopId)`. The returned LT from CodegenEnv
836 // should be consistent with the LT indexed by <TensorId, Level>.
837 const auto lt = env.lt(t: env.unpackTensorLevel(tl: tidLvl).first, i: curr);
838 return lt.hasSparseSemantic();
839 });
840 return isParallelFor(env, /*isOuter=*/curr == 0, isSparse);
841}
842
843/// Emit a loop to coiterate over the list of tensor levels. The generated loop
844/// can either be a for loop or while loop depending on whether there is at most
845/// one sparse level in the list.
846static Operation *genCoIteration(CodegenEnv &env, OpBuilder &builder,
847 ArrayRef<TensorLevel> tidLvls,
848 unsigned numCases, bool tryParallel,
849 bool needsUniv) {
850 Operation *loop = *env.genLoopBoundary(callback: [&](MutableArrayRef<Value> reduc) {
851 // Construct while-loop with a parameter for each index.
852 return env.emitter().enterCoIterationOverTensorsAtLvls(
853 builder, loc: env.op().getLoc(), tidLvls, numCases, reduc, isParallel: tryParallel,
854 needsUniv);
855 });
856 assert(loop);
857 return loop;
858}
859
860/// Generates a for-loop or a while-loop, depending on whether it implements
861/// singleton iteration or co-iteration over the given conjunction.
862static Operation *genLoop(CodegenEnv &env, OpBuilder &builder, LoopId curr,
863 unsigned numCases, bool needsUniv,
864 ArrayRef<TensorLevel> tidLvls) {
865 bool tryParallel = shouldTryParallize(env, curr, tidLvls);
866 return genCoIteration(env, builder, tidLvls, numCases, tryParallel,
867 needsUniv);
868}
869
870/// Generates the induction structure for a while-loop.
871static void finalizeWhileOp(CodegenEnv &env, OpBuilder &builder,
872 bool needsUniv) {
873 Location loc = env.op().getLoc();
874 // Finalize each else branch of all if statements.
875 if (env.isReduc() || env.isExpand() || env.getInsertionChain()) {
876 while (auto ifOp = dyn_cast_or_null<scf::IfOp>(
877 Val: builder.getInsertionBlock()->getParentOp())) {
878 // Break on IfOp for slicing filtering.
879 if (ifOp->getDiscardableAttr(name: LoopEmitter::getLoopEmitterLoopAttrName()) ==
880 StringAttr::get(context: ifOp->getContext(), bytes: "slice"))
881 break;
882
883 unsigned y = 0;
884 SmallVector<Value> yields;
885 if (env.isReduc()) {
886 yields.push_back(Elt: env.getReduc());
887 env.updateReduc(val: ifOp.getResult(i: y++));
888 if (env.isValidLexInsert()) {
889 yields.push_back(Elt: env.getValidLexInsert());
890 env.updateValidLexInsert(val: ifOp.getResult(i: y++));
891 }
892 }
893 if (env.isExpand()) {
894 yields.push_back(Elt: env.getExpandCount());
895 env.updateExpandCount(count: ifOp->getResult(idx: y++));
896 }
897 if (env.getInsertionChain()) {
898 yields.push_back(Elt: env.getInsertionChain());
899 env.updateInsertionChain(chain: ifOp->getResult(idx: y++));
900 }
901 assert(y == yields.size());
902 scf::YieldOp::create(builder, location: loc, results: yields);
903 builder.setInsertionPointAfter(ifOp);
904 }
905 }
906 // No need to set the insertion point here as LoopEmitter keeps track of the
907 // basic block where scf::Yield should be inserted.
908}
909
910/// Generates a case region in the coiterate operation.
911static void genCoIterationCase(CodegenEnv &env, OpBuilder &builder,
912 unsigned caseIdx, LatPointId allCase,
913 LatPointId curCase,
914 MutableArrayRef<Value> reduc) {
915 assert(allCase == curCase || env.merger().latGT(allCase, curCase));
916 const BitVector &allCaseBits = env.merger().lat(p: allCase).simple;
917 const BitVector &curCaseBits = env.merger().lat(p: curCase).simple;
918
919 /// Computes the subset of iterators that are valid in the current case being
920 /// generated.
921 I64BitSet caseBit(0);
922 for (auto [idx, set] : llvm::enumerate(First: allCaseBits.set_bits()))
923 if (curCaseBits.test(Idx: set))
924 caseBit.set(idx);
925
926 env.emitter().enterCurrentCoIterationCase(builder, loc: env.op().getLoc(), caseBit,
927 caseIdx, reduc);
928}
929
930/// Generates a single if-statement within a while-loop.
931static scf::IfOp genIf(CodegenEnv &env, OpBuilder &builder, LoopId curr,
932 LatPointId p) {
933 Location loc = env.op().getLoc();
934 SmallVector<Type> types;
935 Value cond;
936 env.merger().foreachTensorLoopId(
937 p, /*simple=*/true,
938 callback: [&](TensorLoopId b, TensorId tid, std::optional<Level> lvl, LevelType lt,
939 bool isIdxRed) {
940 if (isIdxRed) {
941 // Since there is no 1:1 mapping from loop to level (multiple loops
942 // are required to resolve one level with non-trivial index
943 // expression), we need to reconstruct the tensor level types if this
944 // loop requires index reduction condition.
945 assert(lvl.has_value() && isUndefLT(lt));
946 auto stt = getSparseTensorType(val: env.op().getInputs()[tid]);
947 lt = stt.getLvlType(l: *lvl);
948 }
949 assert(curr == env.merger().loop(b));
950 Value clause;
951 if (lt.hasSparseSemantic()) {
952 assert(lvl.has_value());
953 const Value crd = env.emitter().getCoord(tid, lvl: *lvl);
954 const Value lvar = env.getLoopVar(i: curr);
955 clause = arith::CmpIOp::create(builder, location: loc, predicate: arith::CmpIPredicate::eq,
956 lhs: crd, rhs: lvar);
957 } else {
958 assert(lt.hasDenseSemantic() || isUndefLT(lt));
959 clause = constantI1(builder, loc, b: true);
960 }
961 cond =
962 cond ? arith::AndIOp::create(builder, location: loc, lhs: cond, rhs: clause) : clause;
963 });
964 if (env.isReduc()) {
965 types.push_back(Elt: env.getReduc().getType());
966 if (env.isValidLexInsert())
967 types.push_back(Elt: env.getValidLexInsert().getType());
968 }
969 if (env.isExpand())
970 types.push_back(Elt: builder.getIndexType());
971 if (env.getInsertionChain())
972 types.push_back(Elt: env.getInsertionChain().getType());
973 scf::IfOp ifOp = scf::IfOp::create(builder, location: loc, resultTypes: types, cond, /*else=*/withElseRegion: true);
974 builder.setInsertionPointToStart(&ifOp.getThenRegion().front());
975 return ifOp;
976}
977
978/// Generates end of true branch of if-statement within a while-loop.
979static void endIf(CodegenEnv &env, OpBuilder &builder, scf::IfOp ifOp,
980 Value redInput, Value cntInput, Value insInput,
981 Value validIns) {
982 SmallVector<Value> operands;
983 if (env.isReduc()) {
984 operands.push_back(Elt: env.getReduc());
985 env.updateReduc(val: redInput);
986 if (env.isValidLexInsert()) {
987 // Any overlapping indices during a reduction creates a valid lex insert.
988 operands.push_back(Elt: constantI1(builder, loc: env.op().getLoc(), b: true));
989 env.updateValidLexInsert(val: validIns);
990 }
991 }
992 if (env.isExpand()) {
993 operands.push_back(Elt: env.getExpandCount());
994 env.updateExpandCount(count: cntInput);
995 }
996 if (env.getInsertionChain()) {
997 operands.push_back(Elt: env.getInsertionChain());
998 env.updateInsertionChain(chain: insInput);
999 }
1000 if (!operands.empty())
1001 scf::YieldOp::create(builder, location: env.op().getLoc(), results: operands);
1002 builder.setInsertionPointToStart(&ifOp.getElseRegion().front());
1003}
1004
1005//===----------------------------------------------------------------------===//
1006// Sparsifier synthesis methods (loop sequence).
1007//===----------------------------------------------------------------------===//
1008
1009static bool getAllTidLvlsInLatPoints(
1010 CodegenEnv &env, LatPointId li, LoopId curr,
1011 llvm::function_ref<void(TensorLevel, AffineExpr)> callback) {
1012 const BitVector &simple = env.lat(l: li).simple;
1013 const TensorId outTid = env.merger().getOutTensorID();
1014 const std::optional<Level> outLvl = env.merger().getLvl(t: outTid, i: curr);
1015
1016 unsigned numloopCond = 0;
1017 bool hasNonUnique = false;
1018 env.merger().foreachTensorLoopId(
1019 p: li, callback: [&, curr](TensorLoopId b, TensorId tid, std::optional<Level> lvl,
1020 LevelType lt, bool isIdxReduc) {
1021 if (simple[b]) {
1022 if (isIdxReduc) {
1023 callback(env.makeTensorLevel(t: tid, l: *lvl), nullptr);
1024 numloopCond++;
1025 return;
1026 }
1027 if (isUndefLT(lt)) {
1028 // An undefined lt in the lattices, we probably mean to
1029 // generate a dense loop according to the synthetic tensor (for
1030 // invariants and sparse output tensor).
1031 if (env.merger().getSynTensorID() == tid) {
1032 // Coiterating with an invariant
1033 // e.g., out = prod(in[i][j] op invariant);
1034 // or a broadcast
1035 // e.g., out[i][j] = in[i] (j is undef for input)
1036 //
1037 // The level of the synthetic tensor is the current loop depth;
1038 // the rank of the synthetic tensor equals to number of loops.
1039 assert(curr == env.getCurrentDepth());
1040 lvl = curr;
1041 } else if (!lvl) {
1042 // Skips invalid lvl (e.g., when this is a zero ranked tensor).
1043 return;
1044 }
1045 }
1046 hasNonUnique = !isUniqueLT(lt) || hasNonUnique;
1047 callback(env.makeTensorLevel(t: tid, l: *lvl), nullptr);
1048 numloopCond++;
1049 } else if (lt.hasDenseSemantic() || isIdxReduc) {
1050 callback(env.makeTensorLevel(t: tid, l: *lvl), nullptr);
1051 } else {
1052 assert(isUndefLT(lt));
1053 linalg::GenericOp op = env.op();
1054 if (tid >= op.getNumDpsInputs())
1055 // We only handle affine expression on input tensors (for now).
1056 return;
1057 OpOperand *operand = &op->getOpOperand(idx: tid);
1058 const auto stt = getSparseTensorType(val: operand->get());
1059 // Non-annotated dense tensors requires no special handling.
1060 if (!stt.hasEncoding())
1061 return;
1062
1063 ArrayRef<AffineExpr> affines =
1064 op.getMatchingIndexingMap(opOperand: operand).getResults();
1065 const Level lvlRank = stt.getLvlRank();
1066 assert(affines.size() == static_cast<size_t>(lvlRank));
1067 for (Level l = 0; l < lvlRank; l++) {
1068 AffineExpr exp = affines[l];
1069 // Skip simple affine expression and non-dense levels (which
1070 // have their own filter loop).
1071 LevelType lt = stt.getLvlType(l);
1072 if (isa<AffineDimExpr>(Val: exp) || !lt.hasDenseSemantic())
1073 continue;
1074
1075 // Constant affine expression are handled in genLoop.
1076 if (!isa<AffineConstantExpr>(Val: exp)) {
1077 bool isCurrentLoop = false;
1078 assert(curr == env.getCurrentDepth());
1079 if (isInvariantAffine(a: exp, curr: curr + 1, /*out*/ isCurrentLoop) &&
1080 isCurrentLoop) {
1081 // If the compound affine is invariant and we are right at the
1082 // level. We need to generate the address according to the
1083 // affine expression. This is also the best place we can do it
1084 // to avoid putting it inside inner loops.
1085 callback(env.makeTensorLevel(t: tid, l), exp);
1086 }
1087 }
1088 }
1089 }
1090 });
1091
1092 if (isDenseLT(lt: env.lt(t: outTid, i: curr))) {
1093 auto stt = getSparseTensorType(val: env.op().getOutputs().front());
1094 // Note that we generate dense indices of the output tensor unconditionally,
1095 // since they may not appear in the lattice, but may be needed for
1096 // linearized env.
1097 // TODO: we should avoid introducing corner cases for all-dense sparse
1098 // tensors.
1099 if (stt.hasEncoding() && stt.isAllDense())
1100 callback(env.makeTensorLevel(t: outTid, l: *outLvl), nullptr);
1101 }
1102
1103 if (numloopCond == 0) {
1104 // Corner cases where the loop bound is defined by a *unused* operand, in
1105 // this case, we just generate a dense "fake" loop by iterating over the
1106 // synthetic tensor.
1107 callback(env.makeTensorLevel(t: env.merger().getSynTensorID(), l: curr), nullptr);
1108 numloopCond++;
1109 }
1110 // If we just need to one loop conditions and the conditions is not imposed on
1111 // non-unique level, the loop can be generated by a for loop.
1112 // Or, if we are generating sparse-iterator-based loops, we always generate
1113 // `sparse_tensor.iterate` regardless whether the level is unique or not.
1114 return numloopCond == 1 &&
1115 (!hasNonUnique || env.options().sparseEmitStrategy ==
1116 SparseEmitStrategy::kSparseIterator);
1117}
1118
1119/// Starts a loop sequence at given level. Returns true if
1120/// the universal loop index must be maintained at this level.
1121static bool startLoopSeq(CodegenEnv &env, OpBuilder &builder, ExprId exp,
1122 LoopId curr, LatSetId lts) {
1123 assert(!env.getLoopVar(curr));
1124 // Emit invariants at this loop sequence level.
1125 genInvariants(env, builder, exp, curr, /*isStart=*/true);
1126 // Emit access pattern expansion for sparse tensor output.
1127 genExpand(env, builder, curr, /*isStart=*/true);
1128 // Emit further initialization at this loop sequence level.
1129 const LatPointId l0 = env.set(lts)[0];
1130
1131 SmallVector<TensorLevel> tidLvls;
1132 getAllTidLvlsInLatPoints(env, li: l0, curr, callback: [&](TensorLevel tl, AffineExpr) {
1133 // TODO: remove this! The same tensor level might be added for multiple
1134 // times due to the special handling for all-dense "sparse" output tensor
1135 // (see L1038).
1136 if (llvm::is_contained(Range&: tidLvls, Element: tl))
1137 return;
1138 tidLvls.emplace_back(Args&: tl);
1139 });
1140
1141 env.emitter().enterNewLoopSeq(builder, loc: env.op().getLoc(), tidLvls);
1142
1143 // Maintain the universal index only if it is actually
1144 // consumed by a subsequent lattice point.
1145 for (const LatPointId li : env.set(lts).drop_front())
1146 if (!env.merger().hasAnySparse(bits: env.lat(l: li).simple))
1147 return true;
1148
1149 return false;
1150}
1151
1152// Generates dense affine address for encoding.
1153static void genConstantDenseAddressFromLevel(CodegenEnv &env,
1154 OpBuilder &builder, TensorId tid,
1155 Level startLvl) {
1156 // TODO: Handle affine expression on output tensor.
1157 linalg::GenericOp op = env.op();
1158 assert(tid < op.getNumDpsInputs());
1159 OpOperand *input = op.getDpsInputOperands()[tid];
1160 const auto lvlExprs = op.getMatchingIndexingMap(opOperand: input).getResults();
1161 const auto enc = getSparseTensorEncoding(type: input->get().getType());
1162 if (enc) {
1163 const Location loc = op.getLoc();
1164 const TensorId tid = env.makeTensorId(t: input->getOperandNumber());
1165 const Level lvlRank = enc.getLvlRank();
1166 assert(lvlExprs.size() == static_cast<size_t>(lvlRank));
1167 for (Level l = startLvl; l < lvlRank; l++) {
1168 AffineExpr lvlExpr = lvlExprs[l];
1169 if (enc.getLvlType(l).hasDenseSemantic() &&
1170 isa<AffineConstantExpr>(Val: lvlExpr))
1171 env.emitter().locateLvlAtAffineAddress(
1172 builder, loc, tidLvl: env.makeTensorLevel(t: tid, l), lvlExpr);
1173 else
1174 return; // break on first non-dense non-constant level
1175 }
1176 }
1177}
1178
1179// We can generate address for constant affine expression before any loops
1180// starting from the first level as they do not depend on anything.
1181// E.g., [Dense, Dense, Sparse] -> (1, 2, d0), the addresses for the first two
1182// levels can be determined before loops.
1183static void genInitConstantDenseAddress(CodegenEnv &env,
1184 RewriterBase &rewriter) {
1185 for (TensorId tid = 0, e = env.op().getNumDpsInputs(); tid < e; tid++)
1186 genConstantDenseAddressFromLevel(env, builder&: rewriter, tid, startLvl: 0);
1187}
1188
1189/// Returns true if the lattice bit can be iterated by a for loop.
1190static bool translateBitsToTidLvlPairs(
1191 CodegenEnv &env, LatPointId li, LoopId curr,
1192 SmallVectorImpl<TensorLevel> &tidLvls,
1193 SmallVectorImpl<std::pair<TensorLevel, AffineExpr>> &affineTidLvls) {
1194 return getAllTidLvlsInLatPoints(env, li, curr,
1195 callback: [&](TensorLevel tl, AffineExpr exp) {
1196 if (exp)
1197 affineTidLvls.emplace_back(Args&: tl, Args&: exp);
1198 else
1199 tidLvls.emplace_back(Args&: tl);
1200 });
1201}
1202
1203/// Starts a single loop in current sequence.
1204static std::pair<Operation *, bool> startLoop(CodegenEnv &env,
1205 OpBuilder &builder, LoopId curr,
1206 LatPointId li, unsigned numCases,
1207 bool needsUniv) {
1208 // TODO: numCases only used when generating iterator-based loops. Cleanup
1209 // after fully migration.
1210 // The set of tensors + lvls to generate loops on
1211 SmallVector<TensorLevel> tidLvls;
1212
1213 // The set of dense tensors with non-trivial affine expression that just
1214 // becomes invariant and the address are generated at the current level.
1215 SmallVector<std::pair<TensorLevel, AffineExpr>> affineTidLvls;
1216 bool isSingleCond =
1217 translateBitsToTidLvlPairs(env, li, curr, tidLvls, affineTidLvls);
1218
1219 // Emit the for/while-loop control.
1220 Operation *loop = genLoop(env, builder, curr, numCases, needsUniv, tidLvls);
1221 Location loc = env.op().getLoc();
1222 for (auto [tidLvl, exp] : affineTidLvls) {
1223 env.emitter().locateLvlAtAffineAddress(builder, loc, tidLvl, lvlExpr: exp);
1224 }
1225
1226 // Until now, we have entered every <tid, lvl> pair in {cond, extra,
1227 // affine}Tids/Lvls. The addresses of the upcoming levels which are dependent
1228 // on constant affines expression may now be determined.
1229 auto allTidLvls =
1230 llvm::concat<TensorLevel>(Ranges&: tidLvls, Ranges: llvm::make_first_range(c&: affineTidLvls));
1231 for (auto [tid, lvl] : env.unpackTensorLevelRange(c&: allTidLvls)) {
1232 if (tid != env.merger().getOutTensorID() &&
1233 tid != env.merger().getSynTensorID())
1234 genConstantDenseAddressFromLevel(env, builder, tid, startLvl: lvl + 1);
1235 }
1236
1237 return std::make_pair(x&: loop, y&: isSingleCond);
1238}
1239
1240/// Ends a single loop in current sequence. Returns new values for needsUniv.
1241static bool endLoop(CodegenEnv &env, RewriterBase &rewriter, Operation *loop,
1242 LatPointId li, bool needsUniv, bool isSingleCond) {
1243 // Either a for-loop or a while-loop that iterates over a slice.
1244 if (isSingleCond) {
1245 // Any iteration creates a valid lex insert.
1246 if (env.isReduc() && env.isValidLexInsert())
1247 env.updateValidLexInsert(val: constantI1(builder&: rewriter, loc: env.op().getLoc(), b: true));
1248 } else if (auto whileOp = dyn_cast<scf::WhileOp>(Val: loop)) {
1249 // End a while-loop.
1250 finalizeWhileOp(env, builder&: rewriter, needsUniv);
1251 } else {
1252 needsUniv = false;
1253 }
1254 env.genLoopBoundary(callback: [&](MutableArrayRef<Value> reduc) {
1255 env.emitter().exitCurrentLoop(rewriter, loc: env.op().getLoc(), reduc);
1256 return std::nullopt;
1257 });
1258 return needsUniv;
1259}
1260
1261/// Ends a loop sequence at given level.
1262static void endLoopSeq(CodegenEnv &env, OpBuilder &builder, unsigned exp,
1263 unsigned at) {
1264 assert(!env.getLoopVar(at));
1265 env.emitter().exitCurrentLoopSeq(builder, loc: env.op().getLoc());
1266 // Unmark bookkeeping of invariants and loop index.
1267 genInvariants(env, builder, exp, curr: at, /*isStart=*/false);
1268 // Finalize access pattern expansion for sparse tensor output.
1269 genExpand(env, builder, curr: at, /*isStart=*/false);
1270}
1271
1272/// Recursively generates code while computing iteration lattices in order
1273/// to manage the complexity of implementing co-iteration over unions
1274/// and intersections of sparse iterations spaces.
1275static void genStmt(CodegenEnv &env, RewriterBase &rewriter, ExprId exp,
1276 LoopId curr) {
1277 assert(curr == env.getCurrentDepth());
1278
1279 // At each leaf, assign remaining tensor (sub)expression to output tensor.
1280 if (curr == env.getLoopNum()) {
1281 Value rhs = genExp(env, rewriter, e: exp);
1282 genTensorStore(env, builder&: rewriter, exp, rhs);
1283 return;
1284 }
1285
1286 // Construct iteration lattices for current loop index.
1287 const LatSetId lts =
1288 env.merger().optimizeSet(s: env.merger().buildLattices(e: exp, i: curr));
1289
1290 // Start a loop sequence.
1291 bool needsUniv = startLoopSeq(env, builder&: rewriter, exp, curr, lts);
1292
1293 // When using sparse-iterator-based loops, we only need one loops, as
1294 // opposed to a loop sequence, to cover all the iterator spaces.
1295 const unsigned lsize = env.set(lts).size();
1296 if (env.generatingSparseIterator()) {
1297 // Get the largest lattice point and start a loop.
1298 const LatPointId li = env.set(lts)[0];
1299 auto [loop, isSingleCond] =
1300 startLoop(env, builder&: rewriter, curr, li, numCases: lsize, needsUniv);
1301 assert(isSingleCond == llvm::isa<IterateOp>(loop));
1302 // We cannot change this to `for (const LatPointId li : env.set(lts))`
1303 // because the loop body causes data-movement which invalidates
1304 // the iterator.
1305 for (unsigned j = 0; j < lsize; j++) {
1306 const LatPointId lj = env.set(lts)[j];
1307 const ExprId ej = env.lat(l: lj).exp;
1308 // Recurse into body of each branch.
1309 if (!isSingleCond) {
1310 env.genLoopBoundary(callback: [&, curr, j, li, lj](MutableArrayRef<Value> reduc) {
1311 genCoIterationCase(env, builder&: rewriter, /*caseIdx*/ j, allCase: li, curCase: lj, reduc);
1312 genStmt(env, rewriter, exp: ej, curr: curr + 1);
1313 // TODO: handle yield values.
1314 assert(reduc.empty() && "Not Implemented");
1315 sparse_tensor::YieldOp::create(builder&: rewriter, location: env.op().getLoc());
1316 return std::nullopt;
1317 });
1318 // endIf(env, rewriter, ifOp, redInput, cntInput, insInput, validIns);
1319 } else {
1320 genStmt(env, rewriter, exp: ej, curr: curr + 1);
1321 }
1322 }
1323 // End a loop.
1324 needsUniv = endLoop(env, rewriter, loop, li: curr, needsUniv, isSingleCond);
1325 } else {
1326 // Emit a loop for every lattice point L0 >= Li in this loop sequence.
1327 for (unsigned i = 0; i < lsize; i++) {
1328 const LatPointId li = env.set(lts)[i];
1329 // Start a loop.
1330 auto [loop, isSingleCond] =
1331 startLoop(env, builder&: rewriter, curr, li, numCases: lsize, needsUniv);
1332
1333 // Visit all lattices points with Li >= Lj to generate the
1334 // loop-body, possibly with if statements for coiteration.
1335 Value redInput = env.getReduc();
1336 Value cntInput = env.getExpandCount();
1337 Value insInput = env.getInsertionChain();
1338 Value validIns = env.getValidLexInsert();
1339 // We cannot change this to `for (const LatPointId lj : env.set(lts))`
1340 // because the loop body causes data-movement which invalidates the
1341 // iterator.
1342 for (unsigned j = 0; j < lsize; j++) {
1343 const LatPointId lj = env.set(lts)[j];
1344 const ExprId ej = env.lat(l: lj).exp;
1345 if (li == lj || env.merger().latGT(p0: li, p1: lj)) {
1346 // Recurse into body of each branch.
1347 if (!isSingleCond) {
1348 scf::IfOp ifOp = genIf(env, builder&: rewriter, curr, p: lj);
1349 genStmt(env, rewriter, exp: ej, curr: curr + 1);
1350 endIf(env, builder&: rewriter, ifOp, redInput, cntInput, insInput, validIns);
1351 } else {
1352 genStmt(env, rewriter, exp: ej, curr: curr + 1);
1353 }
1354 }
1355 }
1356
1357 // End a loop.
1358 needsUniv = endLoop(env, rewriter, loop, li: curr, needsUniv, isSingleCond);
1359 }
1360 }
1361
1362 // End a loop sequence.
1363 endLoopSeq(env, builder&: rewriter, exp, at: curr);
1364 assert(curr == env.getCurrentDepth());
1365}
1366
1367/// Converts the result computed by the sparse kernel into the required form.
1368static void genResult(CodegenEnv &env, RewriterBase &rewriter) {
1369 linalg::GenericOp op = env.op();
1370 OpOperand *lhs = op.getDpsInitOperand(i: 0);
1371 Value tensor = lhs->get();
1372 Type resType = tensor.getType();
1373 if (getSparseTensorEncoding(type: resType)) {
1374 // The sparse tensor rematerializes from the original sparse tensor's
1375 // underlying sparse storage format. For an insertion chain, the
1376 // tensor materializes from the chain with 'hasInserts' enabled.
1377 bool hasInserts = false;
1378 if (Value chain = env.getInsertionChain()) {
1379 hasInserts = true;
1380 tensor = chain;
1381 }
1382 rewriter.replaceOpWithNewOp<LoadOp>(op, args&: resType, args&: tensor, args&: hasInserts);
1383 } else {
1384 // To rematerialize an non-annotated tensor, simply load it
1385 // from the bufferized value.
1386 Value val = env.emitter().getValBuffer()[env.merger().getOutTensorID()];
1387 rewriter.replaceOpWithNewOp<bufferization::ToTensorOp>(op, args&: resType, args&: val);
1388 }
1389}
1390
1391//===----------------------------------------------------------------------===//
1392// Sparsifier rewriting methods.
1393//===----------------------------------------------------------------------===//
1394
1395namespace {
1396
1397/// Sparse rewriting rule for generic Lingalg operation.
1398struct GenericOpSparsifier : public OpRewritePattern<linalg::GenericOp> {
1399public:
1400 GenericOpSparsifier(MLIRContext *context, SparsificationOptions o)
1401 : OpRewritePattern<linalg::GenericOp>(context), options(o) {}
1402
1403 LogicalResult matchAndRewrite(linalg::GenericOp op,
1404 PatternRewriter &rewriter) const override {
1405 // Only accept single output operations with pure tensor semantics.
1406 if (op.getNumDpsInits() != 1 || !op.hasPureTensorSemantics())
1407 return failure();
1408
1409 // Only accept trivial affine indices.
1410 if (hasNonTrivialAffineOnSparseOut(op))
1411 return failure();
1412
1413 // Only accept scheduled loops.
1414 if (!op->hasDiscardableAttr(name: "sorted")) {
1415 return rewriter.notifyMatchFailure(
1416 arg&: op, msg: "Loops not yet scheduled, try run --sparse-reinterpret-map "
1417 "before sparsification.");
1418 }
1419
1420 // Must have been demapped as well if the generic op is sorted.
1421 assert(!hasAnyNonIdentityOperandsOrResults(op));
1422
1423 // Sets up a code generation environment.
1424 const unsigned numTensors = op->getNumOperands();
1425 const unsigned numLoops = op.getNumLoops();
1426 bool needIdxRed = getNumNonTrivialIdxExpOnSparseLvls(op) != 0;
1427 // If we have indexing map like (d0) -> (0, d0), there might be more
1428 // levels then loops because of the constant index, that means we can not
1429 // use numLoops as the upper bound for ranks of all tensors.
1430 // TODO: Constant indices are currently not support on sparse tensor, but
1431 // are allowed in non-annotated dense tensor. Support it, it would be
1432 // required for sparse tensor slice rank reducing too.
1433 Level maxLvlRank = 0;
1434 for (auto operand : op.getOperands()) {
1435 if (auto rtp = dyn_cast<RankedTensorType>(Val: operand.getType())) {
1436 maxLvlRank = std::max(a: maxLvlRank, b: SparseTensorType(rtp).getLvlRank());
1437 }
1438 }
1439
1440 // Detects sparse annotations and translates the per-level sparsity
1441 // information for all tensors to loop indices in the kernel.
1442 CodegenEnv env(op, options, numTensors, numLoops, maxLvlRank);
1443 if (!findSparseAnnotations(env, idxReducBased: needIdxRed))
1444 return failure();
1445
1446 // Only standard reduction operations (add, sub, or, xor) that can be
1447 // sparsified by merely reducing the stored values are admissible. More
1448 // elaborate reduction operations (such as mul, and, min, max) would need
1449 // to know whether implicit zeros occur as well. They can still be
1450 // implemented with a custom reduction operation, accepted here as well.
1451 if (op.getNumReductionLoops() > 0) {
1452 Operation *yield = op.getRegion().front().getTerminator();
1453 assert(isa<linalg::YieldOp>(yield));
1454 Operation *redop = yield->getOperand(idx: 0).getDefiningOp();
1455 if (!isa<arith::AddFOp>(Val: redop) && !isa<complex::AddOp>(Val: redop) &&
1456 !isa<arith::AddIOp>(Val: redop) && !isa<arith::SubFOp>(Val: redop) &&
1457 !isa<complex::SubOp>(Val: redop) && !isa<arith::SubIOp>(Val: redop) &&
1458 !isa<arith::OrIOp>(Val: redop) && !isa<arith::XOrIOp>(Val: redop) &&
1459 !isa<ReduceOp>(Val: redop)) {
1460 return failure();
1461 }
1462 }
1463
1464 // Constructs the tensor expressions tree from `op`, returns failure if the
1465 // tree can not be built or the tensor expression is inadmissible.
1466 if (failed(Result: env.initTensorExp()))
1467 return failure();
1468
1469 // Recursively generates code if admissible.
1470 env.startEmit(emitStrategy: options.sparseEmitStrategy);
1471 genBuffers(env, builder&: rewriter);
1472 // TODO: Constant affine expression should be handled differently when using
1473 // slice-based codegen, it does not matter now because we already reject the
1474 // constant expression at an earlier stage.
1475 genInitConstantDenseAddress(env, rewriter);
1476 genStmt(env, rewriter, exp: env.getExprId(), curr: 0);
1477 genResult(env, rewriter);
1478 return success();
1479 }
1480
1481private:
1482 /// Options to control sparse code generation.
1483 SparsificationOptions options;
1484};
1485
1486} // namespace
1487
1488/// Populates the given patterns list with rewriting rules required for
1489/// the sparsification of linear algebra operations.
1490void mlir::populateSparsificationPatterns(
1491 RewritePatternSet &patterns, const SparsificationOptions &options) {
1492 patterns.add<GenericOpSparsifier>(arg: patterns.getContext(), args: options);
1493}
1494