1//===- SparseReinterpretMap.cpp - reinterpret sparse tensor maps ----------===/
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "Utils/CodegenUtils.h"
10#include "Utils/IterationGraphSorter.h"
11
12#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
13#include "mlir/Dialect/Linalg/IR/Linalg.h"
14#include "mlir/Dialect/Linalg/Utils/Utils.h"
15#include "mlir/Dialect/SparseTensor/IR/SparseTensor.h"
16#include "mlir/Dialect/SparseTensor/IR/SparseTensorType.h"
17#include "mlir/Dialect/SparseTensor/Transforms/Passes.h"
18#include "mlir/Dialect/Tensor/IR/Tensor.h"
19#include "mlir/IR/AffineExprVisitor.h"
20#include "mlir/IR/AffineMap.h"
21
22#include <type_traits>
23
24using namespace mlir;
25using namespace mlir::sparse_tensor;
26
27namespace {
28
29//===----------------------------------------------------------------------===//
30// File Local Helper classes.
31//===----------------------------------------------------------------------===//
32
33// CRTP to help implementing a rewriter that demaps all its inputs.
34template <typename SubClass, typename SourceOp>
35struct DemapInsRewriter : public OpRewritePattern<SourceOp> {
36 using OpRewritePattern<SourceOp>::OpRewritePattern;
37 using OpAdaptor = typename SourceOp::Adaptor;
38
39 LogicalResult matchAndRewrite(SourceOp op,
40 PatternRewriter &rewriter) const override {
41 Location loc = op.getLoc();
42
43 for (Value in : op->getOperands())
44 if (auto stt = tryGetSparseTensorType(val: in);
45 stt && !stt->isIdentity() &&
46 stt->getEncoding().getDimToLvl().getNumSymbols() != 0)
47 return failure();
48
49 // Demaps non-trivial inputs.
50 bool changed = false;
51 SmallVector<Value> deMappedIns(op->getOperands());
52 for (Value &in : deMappedIns) {
53 if (auto stt = tryGetSparseTensorType(val: in); stt && !stt->isIdentity()) {
54 in =
55 ReinterpretMapOp::create(builder&: rewriter, location: loc, dest: stt->getDemappedType(), source: in);
56 changed = true;
57 }
58 }
59
60 // CRTP call.
61 OpAdaptor adaptor(deMappedIns, op);
62 LogicalResult status =
63 static_cast<const SubClass *>(this)->rewriteOp(op, adaptor, rewriter);
64 return changed ? success() : status;
65 }
66};
67
68// Flattens an affine expression into a list of AffineDimExprs.
69struct AffineDimCollector : public AffineExprVisitor<AffineDimCollector> {
70 explicit AffineDimCollector(unsigned dimNum) : dims(dimNum) {};
71 void visitDimExpr(AffineDimExpr expr) { dims.set(expr.getPosition()); }
72 BitVector dims;
73};
74
75// Flattens an affine expression into a list of AffineDimExprs.
76struct AffineExprAdmissibleVisitor
77 : public AffineExprVisitor<AffineExprAdmissibleVisitor> {
78 explicit AffineExprAdmissibleVisitor(bool isOutput) : isOutput(isOutput) {};
79
80 // We only allow AffineDimExpr on output.
81 void visitAddExpr(AffineBinaryOpExpr expr) {
82 if (isOutput)
83 admissible = false;
84 }
85 void visitMulExpr(AffineBinaryOpExpr expr) {
86 if (isOutput)
87 admissible = false;
88 }
89
90 // We disallow mod, floor div and ceil div on inputs.
91 void visitModExpr(AffineBinaryOpExpr expr) { admissible = false; }
92 void visitFloorDivExpr(AffineBinaryOpExpr expr) { admissible = false; }
93 void visitCeilDivExpr(AffineBinaryOpExpr expr) { admissible = false; }
94 operator bool() { return admissible; }
95
96private:
97 bool admissible = true;
98 bool isOutput;
99};
100
101// The first BitVector stores levels where inadmissible exprs are used.
102// The second BitVector stores the AffineDimExp that are used by the
103// inadmissible expressions.
104using InadmissInfo = std::pair<BitVector, BitVector>;
105
106} // namespace
107
108//===----------------------------------------------------------------------===//
109// File Local Helper methods.
110//===----------------------------------------------------------------------===//
111
112// Collects the inadmissible affine expression imposed on levels.
113static InadmissInfo collectInadmissInfo(AffineMap map, bool isOutput) {
114 auto ret = std::make_pair(x: BitVector(map.getNumResults()),
115 y: BitVector(map.getNumDims()));
116 AffineDimCollector collector(map.getNumDims());
117 for (unsigned lvl = 0, e = map.getNumResults(); lvl < e; lvl++) {
118 AffineExprAdmissibleVisitor admissible(isOutput);
119 admissible.walkPostOrder(expr: map.getResult(idx: lvl));
120 if (!admissible) {
121 // Record the inadmissible level.
122 ret.first.set(lvl);
123 // Record the AffineDimExpr that is used in the inadmissible expr.
124 collector.walkPostOrder(expr: map.getResult(idx: lvl));
125 }
126 }
127 ret.second = collector.dims;
128 return ret;
129}
130
131// Builds the AffineMap to replace the idx in idxMap to lvl such that all tht
132// inadmissible affine expressions can be eliminated.
133// For example, we can rewrite
134// idxMap = (d0, d1) -> (d0 floordiv 2, d1 floordiv 3, d0 mod 2, d1 mod 3)
135// to
136// idxMap = (l0, l1, l2, l3) -> (l0, l1, l2, l3)
137// by composing inverse(idxMap), that is
138// inverse(idxMap) . idxMap = (l0, l1, l2, l3) -> (l0 * 2 + l2, l1 * 3 + l3)
139// -> ((l0 * 2 + l2) floordiv 2,
140// (l1 * 3 + l3) floordiv 3,
141// (l0 * 2 + l2) mod 2,
142// (l1 * 3 + l3) mod 3) = (l0, l1, l2, l3)
143//
144// This function builds the inverse(idxMap) that replace every dimensions used
145// in `info` to levels, and updates the iterator type array `itTps` for the new
146// index variable introduced.
147//
148// Note that the returned affine map does not retain the order of the input
149// affine map. Instead, it always uses the first `info.inAdlvls.count()` for the
150// replaced levels, and remaining ones for unused dimensions.
151// For example, to handle
152// idxMap = (d0, d1) -> (d0, d1 floordiv 4, d2 mod 4)
153// which is a typical map for block_2to4. The function returns:
154// inverse(idxMap) = (l0, l1, d0) -> (d0, l0 * 4 + l1)
155// in which, (l0, l1) together replaces `d1`, yet they appear
156// before `d0` in the resulting affine map.
157// The index (loop) order can later be canonicalized by a topo sort.
158static AffineMap
159genReplaceDimToLvlMap(const InadmissInfo &info, AffineMap idxMap,
160 SmallVector<utils::IteratorType> &itTps) {
161 MLIRContext *ctx = idxMap.getContext();
162 auto [inAdLvls, usedDims] = info;
163 // Note that idxMap does not equal to dim2Lvl map, it is computed by
164 // composing idx2Dim(dim2Lvl). They are only equal when idx2Dim is an
165 // ID map.
166 // TODO: we might fail here, in those case we should really return
167 // failure instead of assertion error.
168 auto lvl2Idx = inferLvlToDim(dimToLvl: idxMap, context: ctx);
169
170 assert(lvl2Idx.getNumResults() <= idxMap.getNumDims());
171 if (lvl2Idx.getNumResults() != idxMap.getNumDims()) {
172 // This could happen when some dimensions are projected.
173 // E.g., idx2Lvl = (*i*, j, k) -> (j, k)
174 // ==> lvl2Idx = (j, k) -> (j, k)
175 // In this case, we append the unused dimesion at the end.
176 // ==> lvl2Idx = (j, k, *i*) -> (*i*, j, k)
177 SmallVector<AffineExpr> results;
178 AffineDimCollector usedInLvl(idxMap.getNumDims());
179 for (auto e : idxMap.getResults())
180 usedInLvl.walkPostOrder(expr: e);
181
182 unsigned curUsedDimID = 0;
183 unsigned curUnusedDimID = lvl2Idx.getNumDims();
184
185 BitVector unused = usedInLvl.dims.flip();
186 for (unsigned i = 0; i < idxMap.getNumDims(); i++) {
187 if (unused.test(Idx: i))
188 results.push_back(Elt: getAffineDimExpr(position: curUnusedDimID++, context: ctx));
189 else
190 results.push_back(Elt: lvl2Idx.getResult(idx: curUsedDimID++));
191 }
192 lvl2Idx =
193 AffineMap::get(dimCount: lvl2Idx.getNumDims() + unused.count(), symbolCount: 0, results, context: ctx);
194 }
195 assert(lvl2Idx.getNumResults() == idxMap.getNumDims());
196
197 // We do not need to replace the DimExpr that is not used in inadmissible
198 // level expressions. We use the first inAdLvl.count() dim to represent the
199 // replaced level, the remainings are reserved for unchanged ones.
200 // Note that results from the inverse map computed previously does not follow
201 // the convention we used, and we need to fix the mismatch below.
202 unsigned curRepID = 0;
203 unsigned curOriID = inAdLvls.count();
204 SmallVector<AffineExpr> results;
205 SmallVector<AffineExpr> dimRep(idxMap.getNumResults(), AffineExpr());
206 SmallVector<utils::IteratorType> transItTps;
207
208 for (unsigned l : inAdLvls.set_bits()) {
209 // By our convention, the inadmissible level `l` always appears in the
210 // leading part (accumulated by curRepID) of the affine map's parameter
211 // list. Record the mapping so that we can replace all the uses of `l` to
212 // the correct position after the translation.
213 dimRep[l] = getAffineDimExpr(position: curRepID++, context: ctx);
214 // A new index variable is introduced for the inadmissible level, inherit
215 // the iterator type. E.g., if l0 = d0 floordiv 2, the
216 // iterator type of l0 equals to the iterator type of d0.
217 AffineExpr lvlExp = idxMap.getResult(idx: l);
218 AffineDimCollector collector(idxMap.getNumDims());
219 collector.walkPostOrder(expr: lvlExp);
220 // We assumes a level can only be derived from one dimension.
221 assert(collector.dims.count() == 1);
222 transItTps.push_back(Elt: itTps[collector.dims.find_first()]);
223 }
224
225 for (unsigned d = 0, e = idxMap.getNumDims(); d < e; d++) {
226 if (usedDims.test(Idx: d)) {
227 // The dimension is used in some of the inadmissible levels, and it need
228 // to be inversed. Get the inversion from the inverse map, and fix the
229 // mismatch captured by the above loop.
230 results.push_back(Elt: lvl2Idx.getResult(idx: d).replaceDims(dimReplacements: dimRep));
231 } else {
232 // The dimension is not used in any of the inadmissible levels, and it
233 // does not need to be inversed. Fix the mismatch by mapping it to the
234 // trailing part of the affine map (accumulated by curOriID).
235 results.push_back(Elt: getAffineDimExpr(position: curOriID++, context: ctx));
236 transItTps.push_back(Elt: itTps[d]);
237 }
238 }
239 unsigned numDim = idxMap.getNumDims() - usedDims.count() + inAdLvls.count();
240 // Update iterator type.
241 itTps.assign(in_start: transItTps.begin(), in_end: transItTps.end());
242 return AffineMap::get(dimCount: numDim, symbolCount: 0, results, context: ctx);
243}
244
245// Translates the index map in the linalg::GenericOp from idx->dim map to
246// idx->lvl map. Returns failure if the index map can not be translated to an
247// admissible form.
248// Returns the translated index map array and the iterator type array.
249static std::optional<std::pair<ArrayAttr, ArrayAttr>>
250translateMap(linalg::GenericOp op, PatternRewriter &rewriter) {
251 // idxMap is a idx2dim map before reinterpretation.
252 MLIRContext *ctx = op.getContext();
253 SmallVector<AffineMap> idxMapArray = op.getIndexingMapsArray();
254 SmallVector<utils::IteratorType> itTps = op.getIteratorTypesArray();
255 for (unsigned i = 0, e = idxMapArray.size(); i < e; i++) {
256 Value tensor = op->getOpOperand(idx: i).get();
257 auto stt = tryGetSparseTensorType(val: tensor);
258 if (stt && !stt->isIdentity()) {
259 AffineMap dim2Lvl = stt->getDimToLvl();
260 // By composing the idx2dim(dim2lvl), we got a idx2lvl Map
261 idxMapArray[i] = dim2Lvl.compose(map: idxMapArray[i]);
262 }
263 }
264
265 // A naive way to handle common constant expressions that arise during dim2lvl
266 // translation.
267 auto populateCstMapping = [ctx](DenseMap<AffineExpr, AffineExpr> &cstMapping,
268 unsigned pos, int64_t lvlSz) {
269 if (ShapedType::isStatic(dValue: lvlSz)) {
270 auto c0 = getAffineConstantExpr(constant: 0, context: ctx);
271 auto lvlExp = getAffineDimExpr(position: pos, context: ctx);
272 auto szExp = getAffineConstantExpr(constant: lvlSz, context: ctx);
273
274 // lvl floordiv lvlSz = 0
275 auto divExp =
276 getAffineBinaryOpExpr(kind: AffineExprKind::FloorDiv, lhs: lvlExp, rhs: szExp);
277 cstMapping.try_emplace(Key: divExp, Args&: c0);
278
279 // lvl mod lvlSz = lvl
280 auto modExp = getAffineBinaryOpExpr(kind: AffineExprKind::Mod, lhs: lvlExp, rhs: szExp);
281 cstMapping.try_emplace(Key: modExp, Args&: lvlExp);
282 }
283 };
284
285 unsigned boundedNum = 0;
286 // A fixed-point algorithm.
287 bool changed = true;
288 while (changed) {
289 changed = false;
290 for (OpOperand &operand : op->getOpOperands()) {
291 auto stt = tryGetSparseTensorType(val: operand.get());
292 // Skip on dense operands.
293 if (!stt || !stt->getEncoding())
294 continue;
295
296 unsigned tid = operand.getOperandNumber();
297 bool isOutput = &operand == op.getDpsInitOperand(i: 0);
298 AffineMap idxMap = idxMapArray[tid];
299 InadmissInfo inAdInfo = collectInadmissInfo(map: idxMap, isOutput);
300 auto [inAdLvls, dimExprs] = inAdInfo;
301 for (unsigned d : dimExprs.set_bits()) {
302 // The first `boundedNum` used in the AffineMap is introduced to
303 // resolve previous inadmissible expressions. We can not replace them
304 // as it might bring back the inadmissible expressions.
305 if (d < boundedNum)
306 return std::nullopt;
307 }
308
309 if (inAdLvls.count() != 0) {
310 // Naive constant progagation, should be sufficient to handle block
311 // sparsity in our cases.
312 SmallVector<int64_t> lvlShape = stt->getLvlShape();
313 DenseMap<AffineExpr, AffineExpr> cstMapping;
314 unsigned position = 0;
315 for (unsigned lvl : inAdLvls.set_bits()) {
316 int64_t lvlSz = lvlShape[lvl];
317 populateCstMapping(cstMapping, position, lvlSz);
318 position++;
319 }
320
321 AffineMap lvl2Idx = genReplaceDimToLvlMap(info: inAdInfo, idxMap, itTps);
322 // Compose the lvl2Idx Map to all AffineIdxMap to eliminate
323 // inadmissible expressions.
324 for (unsigned tid = 0, e = idxMapArray.size(); tid < e; tid++) {
325 AffineMap transMap = idxMapArray[tid].compose(map: lvl2Idx);
326 idxMapArray[tid] = transMap.replace(
327 map: cstMapping, /*numResultDims=*/transMap.getNumDims(),
328 /*numResultSyms=*/0);
329 }
330 changed = true;
331 boundedNum += inAdLvls.count();
332 }
333 }
334 };
335
336 SmallVector<Attribute> iterAttr =
337 llvm::map_to_vector(C&: itTps, F: [ctx](auto itTp) -> Attribute {
338 return linalg::IteratorTypeAttr::get(context: ctx, value: itTp);
339 });
340
341 return std::make_pair(x: rewriter.getAffineMapArrayAttr(values: idxMapArray),
342 y: rewriter.getArrayAttr(value: iterAttr));
343}
344
345// Generates a "de"mapping reinterpretation of the map.
346static Value genDemap(OpBuilder &builder, SparseTensorEncodingAttr enc,
347 Value val) {
348 return ReinterpretMapOp::create(builder, location: val.getLoc(), dstEnc: enc.withoutDimToLvl(),
349 source: val);
350}
351
352// Generates a "re"mapping reinterpretation of the map.
353static Value genRemap(OpBuilder &builder, SparseTensorEncodingAttr enc,
354 Value val) {
355 return ReinterpretMapOp::create(builder, location: val.getLoc(), dstEnc: enc, source: val);
356}
357
358static SmallVector<Value> remapValueRange(OpBuilder &rewriter, TypeRange types,
359 ValueRange outs) {
360 SmallVector<Value> ret(outs);
361 assert(outs.size() == types.size());
362 for (auto [r, t] : llvm::zip(t&: ret, u&: types))
363 if (r.getType() != t)
364 r = ReinterpretMapOp::create(builder&: rewriter, location: r.getLoc(), dest: t, source: r);
365 return ret;
366}
367
368namespace {
369
370//===----------------------------------------------------------------------===//
371// Rewriting rules for linalg generic ops.
372//===----------------------------------------------------------------------===//
373
374/// Sparse rewriting rule for the generic `linalg` operation.
375struct GenericOpReinterpretMap
376 : public DemapInsRewriter<GenericOpReinterpretMap, linalg::GenericOp> {
377public:
378 using DemapInsRewriter::DemapInsRewriter;
379 LogicalResult rewriteOp(linalg::GenericOp linalgOp, OpAdaptor adaptor,
380 PatternRewriter &rewriter) const {
381 // Only rewrite single output operations with pure (sparse) tensor
382 // semantics.
383 if (linalgOp.getNumDpsInits() != 1 || !linalgOp.hasPureTensorSemantics() ||
384 !hasAnySparseOperandOrResult(op: linalgOp) ||
385 !hasAnyNonIdentityOperandsOrResults(op: linalgOp))
386 return failure();
387
388 // Try translating the index map.
389 auto transMap = translateMap(op: linalgOp, rewriter);
390 if (!transMap)
391 return rewriter.notifyMatchFailure(
392 arg&: linalgOp, msg: "the sparse kernel can not be sparsified.");
393
394 // On success, replace update the linalg operands and maps in place.
395 Value res = linalgOp.getResult(i: 0);
396 auto stt = tryGetSparseTensorType(val: res);
397 auto [idxMap, itTp] = *transMap;
398
399 rewriter.startOpModification(op: linalgOp);
400 linalgOp.setIndexingMapsAttr(idxMap);
401 linalgOp.setIteratorTypesAttr(itTp);
402 // Use demapped arguments.
403 linalgOp.getInputsMutable().assign(values: adaptor.getInputs());
404 linalgOp.getDpsInitsMutable().assign(values: adaptor.getOutputs());
405 res.setType(adaptor.getOutputs()[0].getType());
406 rewriter.finalizeOpModification(op: linalgOp);
407
408 rewriter.setInsertionPointAfter(linalgOp);
409 if (stt && stt->hasEncoding()) {
410 Value t = genRemap(builder&: rewriter, enc: stt->getEncoding(), val: res);
411 rewriter.replaceAllUsesExcept(from: res, to: t, exceptedUser: t.getDefiningOp());
412 }
413 return success();
414 }
415};
416
417struct GenericOpScheduler : public OpRewritePattern<linalg::GenericOp> {
418 GenericOpScheduler(MLIRContext *context,
419 sparse_tensor::LoopOrderingStrategy strategy)
420 : OpRewritePattern<linalg::GenericOp>(context), strategy(strategy) {}
421
422 LogicalResult matchAndRewrite(linalg::GenericOp linalgOp,
423 PatternRewriter &rewriter) const override {
424 if (linalgOp.getNumDpsInits() != 1 || !linalgOp.hasPureTensorSemantics() ||
425 hasAnyNonIdentityOperandsOrResults(op: linalgOp) || // need demap first
426 !hasAnySparseOperandOrResult(op: linalgOp)) {
427 return failure();
428 }
429
430 const StringRef sorted = "sorted";
431 if (linalgOp->hasDiscardableAttr(name: sorted))
432 return failure();
433
434 // Pass strategy to IterationGraphSorter.
435 auto scheduler = IterationGraphSorter::fromGenericOp(genericOp: linalgOp, strategy);
436 bool isAdmissible = false;
437 AffineMap order;
438 // A const list of all masks that we used for iteration graph
439 // computation. Must be ordered from more strict to less strict.
440 // Ideally (though might not be guaranteed), the earlier a constraint mask
441 // can be satisfied, the faster the generated kernel will be.
442 const auto allMasks = {SortMask::kIncludeAll, SortMask::kIncludeDense,
443 SortMask::kIncludeDenseInput,
444 SortMask::kIncludeDenseOutput,
445 SortMask::kSparseOnly};
446 for (const SortMask mask : allMasks) {
447 order = scheduler.sort(mask);
448 if (order) {
449 if (isAdmissibleOrder(linalgOp, order)) {
450 isAdmissible = true;
451 break;
452 }
453 // else try a set of less strict constraints.
454 }
455 }
456
457 if (!order) {
458 // Cycles detected.
459 if (failed(Result: resolveCycle(scheduler, linalgOp, rewriter))) {
460 return rewriter.notifyMatchFailure(
461 arg&: linalgOp, msg: "the sparse kernel can not be scheduled: loop detected.");
462 }
463 return success();
464 }
465
466 if (!isAdmissible) {
467 return rewriter.notifyMatchFailure(
468 arg&: linalgOp, msg: "the sparse kernel can not be scheduled.");
469 }
470
471 // Marks the GenericOp to avoid recursive matching.
472 rewriter.modifyOpInPlace(root: linalgOp, callable: [&]() {
473 linalgOp->setDiscardableAttr(name: sorted, value: rewriter.getBoolAttr(value: true));
474 });
475
476 // Already sorted.
477 if (order.isIdentity())
478 return success();
479
480 assert(order.isPermutation());
481 // `order` is orignial loop -> sorted loop map
482 ArrayAttr preItTypes = linalgOp.getIteratorTypesAttr();
483 SmallVector<Attribute> curItTypes;
484 curItTypes.reserve(N: preItTypes.size());
485 for (AffineExpr expr : order.getResults()) {
486 unsigned loopID = llvm::cast<AffineDimExpr>(Val&: expr).getPosition();
487 curItTypes.push_back(Elt: preItTypes[loopID]);
488 }
489
490 // Inverse `order` to get sorted loop -> original loop map
491 order = inversePermutation(map: order);
492 SmallVector<AffineMap> idxMaps = linalgOp.getIndexingMapsArray();
493 for (AffineMap &idxMap : idxMaps)
494 idxMap = idxMap.compose(map: order); // sorted loop -> lvl map
495
496 rewriter.startOpModification(op: linalgOp);
497 linalgOp.setIndexingMapsAttr(rewriter.getAffineMapArrayAttr(values: idxMaps));
498 linalgOp.setIteratorTypesAttr(rewriter.getArrayAttr(value: curItTypes));
499 rewriter.finalizeOpModification(op: linalgOp);
500
501 return success();
502 }
503
504private:
505 /// Whether the loop order is admissible by sparsification.
506 static bool isAdmissibleOrder(linalg::GenericOp linalgOp, AffineMap order) {
507 if (!hasAnySparseResult(op: linalgOp))
508 return true;
509
510 OpOperand *lhs = linalgOp.getDpsInitOperand(i: 0);
511 unsigned nest = 0;
512 const auto iteratorTypes = linalgOp.getIteratorTypesArray();
513 for (const AffineExpr l : order.getResults()) {
514 unsigned loopId = llvm::cast<AffineDimExpr>(Val: l).getPosition();
515 auto itTp =
516 cast<linalg::IteratorTypeAttr>(Val: linalgOp.getIteratorTypes()[loopId]);
517 if (linalg::isReductionIterator(iteratorType: itTp.getValue()))
518 break; // terminate at first reduction
519 nest++;
520 }
521 // Determine admissible dynamic insertion situations:
522 // (1) fully injective, since there are no reductions,
523 // (2) admissible 1-d expansion in innermost dimension.
524 return static_cast<int64_t>(nest) >= linalgOp.getRank(opOperand: lhs) - 1;
525 };
526
527 // Last resort cycle resolution.
528 static LogicalResult resolveCycle(IterationGraphSorter &scheduler,
529 linalg::LinalgOp linalgOp,
530 PatternRewriter &rewriter) {
531 // Compute topological sort while leaving out every sparse input tensor in
532 // succession until an acylic iteration graph results.
533 for (OpOperand *t : linalgOp.getDpsInputOperands()) {
534 Value tval = t->get();
535 auto srcEnc = getSparseTensorEncoding(type: tval.getType());
536 // The constraints introduced by compound index expression are
537 // complicated. Skip them.
538 AffineMap idxMap = linalgOp.getMatchingIndexingMap(opOperand: t);
539 bool hasCompExpr = llvm::any_of(Range: idxMap.getResults(), P: [](AffineExpr exp) {
540 return !llvm::isa<AffineDimExpr>(Val: exp);
541 });
542 if (!srcEnc || hasCompExpr)
543 continue;
544
545 // Try scheduling loop without constraints from `tval`.
546 AffineMap order = scheduler.sort(mask: SortMask::kSparseOnly, ignored: tval);
547 if (!order) // still cyclic
548 continue;
549
550 // Found an input tensor that resolves the cycle by inserting a
551 // conversion into a sparse tensor that adheres to the iteration
552 // graph order.
553 auto stt = getSparseTensorType(val: tval);
554 assert(stt.isIdentity());
555 order = inversePermutation(map: order);
556 // sorted loop -> lvl map.
557 idxMap = idxMap.compose(map: order);
558
559 // Found a permutation such that the results in `idxMap` is sorted.
560 // For example,
561 // (d0, d1, d2, d3) -> (d2, d1, d0)
562 // loops are scheduled in order of d0->d1->d2->d3, to resolve the cycle,
563 // we find a permutation, perm(d2, d1, d0) -> (d0, d1, d2), such that the
564 // transposed tensor's levels are visited in the same order as the loop
565 // scheduling order.
566 SmallVector<std::pair<unsigned, unsigned>> lvlSeq;
567 for (AffineExpr expr : idxMap.getResults()) {
568 unsigned lvl = llvm::cast<AffineDimExpr>(Val&: expr).getPosition();
569 lvlSeq.push_back(Elt: std::make_pair(x&: lvl, y: lvlSeq.size()));
570 }
571 llvm::sort(C&: lvlSeq, Comp: llvm::less_first());
572 SmallVector<unsigned> perm =
573 llvm::to_vector(Range: llvm::make_second_range(c&: lvlSeq));
574 auto dimToLvl = AffineMap::getPermutationMap(permutation: perm, context: linalgOp.getContext());
575 // The result of the idxMap must be unsorted.
576 assert(!dimToLvl.isIdentity());
577
578 // Inserting the transpose
579 rewriter.setInsertionPoint(linalgOp);
580 RankedTensorType dstTp = stt.withDimToLvl(dimToLvl).getRankedTensorType();
581 Value dst = ConvertOp::create(builder&: rewriter, location: tval.getLoc(), dest: dstTp, source: tval);
582 rewriter.modifyOpInPlace(root: linalgOp, callable: [&]() {
583 linalgOp->setOperand(idx: t->getOperandNumber(), value: dst);
584 });
585
586 // Release the transposed form afterwards.
587 // TODO: CSE when used in more than one following op?
588 rewriter.setInsertionPointAfter(linalgOp);
589 bufferization::DeallocTensorOp::create(builder&: rewriter, location: dst.getLoc(), tensor: dst);
590
591 return success();
592 }
593 // Cannot be resolved with a single conversion.
594 // TODO: convert more than one?
595 return failure();
596 }
597
598private:
599 sparse_tensor::LoopOrderingStrategy strategy;
600};
601
602//===----------------------------------------------------------------------===//
603// Reinterpret Map Rewriters for operations other than linalg.generics
604//===----------------------------------------------------------------------===//
605
606template <typename AllocOp>
607struct TensorAllocDemapper : public OpRewritePattern<AllocOp> {
608 using OpRewritePattern<AllocOp>::OpRewritePattern;
609 LogicalResult matchAndRewrite(AllocOp op,
610 PatternRewriter &rewriter) const override {
611 if (!hasAnyNonIdentityOperandsOrResults(op))
612 return failure();
613
614 Location loc = op.getLoc();
615 auto stt = getSparseTensorType(op.getResult());
616 if (stt.getEncoding().getDimToLvl().getNumSymbols() != 0)
617 return failure();
618
619 if constexpr (std::is_same_v<AllocOp, bufferization::AllocTensorOp>) {
620 // `bufferization.alloc_tensor` does not carry any dynamic size
621 // operands when it has a `copy` operand -- the shape (and the
622 // contents) are inherited from `copy` instead. Simply demap the
623 // `copy` operand and forward it to a newly created (demapped)
624 // `alloc_tensor` op.
625 if (Value copy = op.getCopy()) {
626 Value demappedCopy = genDemap(rewriter, stt.getEncoding(), copy);
627 auto allocOp = AllocOp::create(rewriter, loc, stt.getDemappedType(),
628 ValueRange{}, demappedCopy);
629 Value t = genRemap(rewriter, stt.getEncoding(), allocOp.getResult());
630 rewriter.replaceOp(op, t);
631 return success();
632 }
633 }
634
635 SmallVector<Value> maxDimCrds;
636 maxDimCrds.reserve(N: stt.getDimRank());
637 ValueRange dynSz = op.getDynamicSizes();
638 for (int64_t dimSz : stt.getDimShape()) {
639 if (ShapedType::isDynamic(dValue: dimSz)) {
640 Value maxCrd = arith::SubIOp::create(builder&: rewriter, location: loc, lhs: dynSz.front(),
641 rhs: constantIndex(builder&: rewriter, loc, i: 1));
642 maxDimCrds.push_back(Elt: maxCrd);
643 dynSz = dynSz.drop_front();
644 } else {
645 maxDimCrds.push_back(Elt: constantIndex(builder&: rewriter, loc, i: dimSz - 1));
646 }
647 }
648
649 ValueRange maxLvlCrds = stt.translateCrds(rewriter, loc, maxDimCrds,
650 CrdTransDirectionKind::dim2lvl);
651 auto lvlShape = stt.getLvlShape();
652 SmallVector<Value> dynLvlSzs;
653 for (unsigned i = 0, e = lvlShape.size(); i < e; i++) {
654 if (ShapedType::isDynamic(dValue: lvlShape[i])) {
655 Value sz = arith::AddIOp::create(builder&: rewriter, location: loc, lhs: maxLvlCrds[i],
656 rhs: constantIndex(builder&: rewriter, loc, i: 1));
657 dynLvlSzs.push_back(Elt: sz);
658 }
659 }
660
661 assert(dynSz.empty()); // should have consumed all.
662
663 // Create a new op to let the MLIR builder calculate the correct metadata.
664 auto allocOp =
665 AllocOp::create(rewriter, loc, stt.getDemappedType(), dynLvlSzs);
666
667 Value t = genRemap(rewriter, stt.getEncoding(), allocOp.getResult());
668 rewriter.replaceOp(op, t);
669 return success();
670 }
671};
672
673struct TensorInsertDemapper
674 : public DemapInsRewriter<TensorInsertDemapper, tensor::InsertOp> {
675 using DemapInsRewriter::DemapInsRewriter;
676 LogicalResult rewriteOp(tensor::InsertOp op, OpAdaptor adaptor,
677 PatternRewriter &rewriter) const {
678 if (!hasAnySparseResult(op) || !hasAnyNonIdentityOperandsOrResults(op))
679 return failure();
680
681 Location loc = op.getLoc();
682 auto stt = getSparseTensorType(val: op.getResult());
683 ValueRange lvlCrd = stt.translateCrds(builder&: rewriter, loc, crds: op.getIndices(),
684 dir: CrdTransDirectionKind::dim2lvl);
685 auto insertOp = tensor::InsertOp::create(builder&: rewriter, location: loc, scalar: op.getScalar(),
686 dest: adaptor.getDest(), indices: lvlCrd);
687
688 Value out = genRemap(builder&: rewriter, enc: stt.getEncoding(), val: insertOp.getResult());
689 rewriter.replaceOp(op, newValues: out);
690 return success();
691 }
692};
693
694struct SparseAssembleDemapper : public OpRewritePattern<AssembleOp> {
695 using Base::Base;
696 LogicalResult matchAndRewrite(AssembleOp op,
697 PatternRewriter &rewriter) const override {
698 if (!hasAnyNonIdentityOperandsOrResults(op))
699 return failure();
700
701 assert(hasAnySparseResult(op));
702 auto stt = getSparseTensorType(val: op.getResult());
703 if (stt.getEncoding().getDimToLvl().getNumSymbols() != 0)
704 return failure();
705 rewriter.modifyOpInPlace(
706 root: op, callable: [&op, &stt]() { op.getResult().setType(stt.getDemappedType()); });
707 rewriter.setInsertionPointAfter(op);
708 Value out = genRemap(builder&: rewriter, enc: stt.getEncoding(), val: op.getResult());
709 rewriter.replaceAllUsesExcept(from: op, to: out, exceptedUser: out.getDefiningOp());
710 return success();
711 }
712};
713
714struct SparseDisassembleDemapper
715 : public DemapInsRewriter<SparseDisassembleDemapper, DisassembleOp> {
716 using DemapInsRewriter::DemapInsRewriter;
717 LogicalResult rewriteOp(DisassembleOp op, OpAdaptor adaptor,
718 PatternRewriter &rewriter) const {
719 if (!hasAnyNonIdentityOperandsOrResults(op))
720 return failure();
721
722 assert(hasAnySparseOperandOrResult(op));
723 rewriter.modifyOpInPlace(root: op, callable: [&op, &adaptor]() {
724 op.getTensorMutable().assign(value: adaptor.getTensor());
725 });
726 return success();
727 }
728};
729
730struct ForeachOpDemapper
731 : public DemapInsRewriter<ForeachOpDemapper, ForeachOp> {
732 using DemapInsRewriter::DemapInsRewriter;
733 LogicalResult rewriteOp(ForeachOp op, OpAdaptor adaptor,
734 PatternRewriter &rewriter) const {
735 // Only handle operations with sparse input/output with non-identity dim2lvl
736 // maps.
737 if (!hasAnyNonIdentityOperandsOrResults(op))
738 return failure();
739
740 // TODO: demap constant as well.
741 if (auto constOp = op.getTensor().getDefiningOp<arith::ConstantOp>())
742 if (auto attr = dyn_cast<SparseElementsAttr>(Val: constOp.getValue()))
743 return failure();
744
745 Location loc = op.getLoc();
746 // Cache the type information since we update the foreach op in-place.
747 auto srcStt = getSparseTensorType(val: op.getTensor());
748 SmallVector<Type> prevRetTps(op.getResultTypes());
749
750 rewriter.startOpModification(op);
751 op.getTensorMutable().assign(value: adaptor.getTensor());
752 op.getInitArgsMutable().assign(values: adaptor.getInitArgs());
753 // Update results' types.
754 for (auto r : op.getResults())
755 if (auto stt = tryGetSparseTensorType(val: r); stt && !stt->isIdentity())
756 r.setType(stt->getDemappedType());
757
758 Level lvlRank = getSparseTensorType(val: adaptor.getTensor()).getLvlRank();
759 // Update the foreach body.
760 SmallVector<Type> blockArgTps(lvlRank, rewriter.getIndexType());
761 blockArgTps.push_back(Elt: srcStt.getElementType());
762 blockArgTps.append(in_start: adaptor.getInitArgs().getTypes().begin(),
763 in_end: adaptor.getInitArgs().getTypes().end());
764 Block *body = op.getBody();
765 // Block Args: [dimCrd, val, initArgs]
766 unsigned preArgNum = body->getNumArguments();
767 for (Type t : blockArgTps)
768 body->addArgument(type: t, loc);
769
770 // Block Args: [dimCrd, val, initArgs, lvlCrds, val, DemappedArgs]
771 rewriter.setInsertionPointToStart(body);
772 ValueRange lvlCrds = body->getArguments().slice(N: preArgNum, M: lvlRank);
773
774 ValueRange dimCrds = srcStt.translateCrds(builder&: rewriter, loc, crds: lvlCrds,
775 dir: CrdTransDirectionKind::lvl2dim);
776 rewriter.replaceAllUsesWith(
777 from: body->getArguments().take_front(N: srcStt.getDimRank()), to: dimCrds);
778 body->eraseArguments(start: 0, num: srcStt.getDimRank());
779 // Block Args: [val, initArgs, lvlCrds, val, DemappedArgs]
780 unsigned numInitArgs = op.getInitArgs().size();
781 rewriter.replaceAllUsesWith(from: body->getArgument(i: 0),
782 to: body->getArgument(i: lvlRank + numInitArgs + 1));
783 body->eraseArgument(index: 0);
784 // Block Args: [initArgs, lvlCrds, val, DemappedArgs]
785 ValueRange srcArgs = body->getArguments().take_front(N: numInitArgs);
786 ValueRange dstArgs = body->getArguments().take_back(N: numInitArgs);
787 // Remap back before replacement.
788 SmallVector<Value> reMappedArgs =
789 remapValueRange(rewriter, types: srcArgs.getTypes(), outs: dstArgs);
790 rewriter.replaceAllUsesWith(from: srcArgs, to: reMappedArgs);
791 body->eraseArguments(start: 0, num: numInitArgs);
792 // Block Args: [lvlCrds, DemappedArgs] and we are done.
793
794 // Update yield operations.
795 if (numInitArgs != 0) {
796 rewriter.setInsertionPointToEnd(body);
797 auto yield = llvm::cast<YieldOp>(Val: body->getTerminator());
798 if (auto stt = tryGetSparseTensorType(val: yield.getSingleResult());
799 stt && !stt->isIdentity()) {
800 Value y =
801 genDemap(builder&: rewriter, enc: stt->getEncoding(), val: yield.getSingleResult());
802 YieldOp::create(builder&: rewriter, location: loc, yieldVal: y);
803 rewriter.eraseOp(op: yield);
804 }
805 }
806 rewriter.finalizeOpModification(op);
807
808 rewriter.setInsertionPointAfter(op);
809 SmallVector<Value> outs =
810 remapValueRange(rewriter, types: prevRetTps, outs: op.getResults());
811
812 // Replace all the uses of the foreach results, expect the use in
813 // reinterpret_map used to remap the output.
814 for (auto [from, to] : llvm::zip(t: op.getResults(), u&: outs))
815 rewriter.replaceAllUsesExcept(from, to, exceptedUser: to.getDefiningOp());
816
817 return success();
818 }
819};
820
821} // namespace
822
823void mlir::populateSparseReinterpretMap(
824 RewritePatternSet &patterns, ReinterpretMapScope scope,
825 sparse_tensor::LoopOrderingStrategy strategy) {
826 if (scope == ReinterpretMapScope::kAll ||
827 scope == ReinterpretMapScope::kGenericOnly) {
828 patterns.add<GenericOpReinterpretMap>(arg: patterns.getContext());
829 patterns.add<GenericOpScheduler>(arg: patterns.getContext(), args&: strategy);
830 }
831 if (scope == ReinterpretMapScope::kAll ||
832 scope == ReinterpretMapScope::kExceptGeneric) {
833 patterns.add<TensorAllocDemapper<bufferization::AllocTensorOp>,
834 TensorAllocDemapper<tensor::EmptyOp>, SparseAssembleDemapper,
835 SparseDisassembleDemapper, TensorInsertDemapper,
836 ForeachOpDemapper>(arg: patterns.getContext());
837 }
838}
839