1
2#include "Utils/CodegenUtils.h"
3#include "Utils/LoopEmitter.h"
4#include "Utils/SparseTensorIterator.h"
5
6#include "mlir/Dialect/MemRef/IR/MemRef.h"
7#include "mlir/Dialect/SCF/IR/SCF.h"
8#include "mlir/Dialect/SparseTensor/IR/SparseTensor.h"
9#include "mlir/Dialect/SparseTensor/Transforms/Passes.h"
10#include "mlir/Transforms/DialectConversion.h"
11
12using namespace mlir;
13using namespace mlir::sparse_tensor;
14
15static void convertLevelType(SparseTensorEncodingAttr enc, Level lvl,
16 SmallVectorImpl<Type> &fields) {
17 // Position and coordinate buffer in the sparse structure.
18 if (enc.getLvlType(l: lvl).isWithPosLT())
19 fields.push_back(Elt: enc.getPosMemRefType());
20 if (enc.getLvlType(l: lvl).isWithCrdLT())
21 fields.push_back(Elt: enc.getCrdMemRefType());
22 // One index for shape bound (result from lvlOp).
23 fields.push_back(Elt: IndexType::get(context: enc.getContext()));
24}
25
26static std::optional<LogicalResult>
27convertIterSpaceType(IterSpaceType itSp, SmallVectorImpl<Type> &fields) {
28
29 auto idxTp = IndexType::get(context: itSp.getContext());
30 for (Level l = itSp.getLoLvl(); l < itSp.getHiLvl(); l++)
31 convertLevelType(enc: itSp.getEncoding(), lvl: l, fields);
32
33 // Two indices for lower and upper bound (we only need one pair for the last
34 // iteration space).
35 fields.append(IL: {idxTp, idxTp});
36 return success();
37}
38
39static std::optional<LogicalResult>
40convertIteratorType(IteratorType itTp, SmallVectorImpl<Type> &fields) {
41 // The actually Iterator Values (that are updated every iteration).
42 auto idxTp = IndexType::get(context: itTp.getContext());
43 // TODO: handle batch dimension.
44 assert(itTp.getEncoding().getBatchLvlRank() == 0);
45 if (!itTp.isUnique()) {
46 // Segment high for non-unique iterator.
47 fields.push_back(Elt: idxTp);
48 }
49 fields.push_back(Elt: idxTp);
50 return success();
51}
52
53static ValueRange
54genCoIterateBranchNest(PatternRewriter &rewriter, Location loc, CoIterateOp op,
55 Value loopCrd,
56 ArrayRef<std::unique_ptr<SparseIterator>> iters,
57 ArrayRef<Block *> newBlocks, ArrayRef<Block *> oldBlocks,
58 ArrayRef<Value> userReduc) {
59 if (newBlocks.empty())
60 return userReduc;
61
62 // The current branch that we are handling.
63 Block *newBlock = newBlocks.front();
64 Block *oldBlock = oldBlocks.front();
65 Value casePred = constantI1(builder&: rewriter, loc, b: true);
66 I64BitSet caseBits =
67 op.getRegionDefinedSpace(regionIdx: newBlock->getParent()->getRegionNumber());
68 for (unsigned i : caseBits.bits()) {
69 SparseIterator *it = iters[i].get();
70 Value pred = arith::CmpIOp::create(builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::eq,
71 lhs: it->getCrd(), rhs: loopCrd);
72 casePred = arith::AndIOp::create(builder&: rewriter, location: loc, lhs: casePred, rhs: pred);
73 }
74 scf::IfOp ifOp = scf::IfOp::create(
75 builder&: rewriter, location: loc, resultTypes: ValueRange(userReduc).getTypes(), cond: casePred, /*else=*/withElseRegion: true);
76 rewriter.setInsertionPointToStart(&ifOp.getThenRegion().front());
77
78 // Erase the empty block.
79 rewriter.eraseBlock(block: &ifOp.getThenRegion().front());
80 // Set up block arguments: user-provided values -> loop coord -> iterators.
81 SmallVector<Value> blockArgs(userReduc);
82 blockArgs.push_back(Elt: loopCrd);
83 for (unsigned idx : caseBits.bits())
84 llvm::append_range(C&: blockArgs, R: iters[idx]->getCursor());
85
86 // Map the old block arguments, because the dialect conversion driver does
87 // not immediately perform SSA value replacements. This function is still
88 // seeing the old uses.
89 IRMapping mapping;
90 for (auto [from, to] : llvm::zip_equal(t: oldBlock->getArguments(), u&: blockArgs)) {
91 mapping.map(from, to);
92 }
93
94 // Clone the region, we can not erase the region now because the same region
95 // might be a subcase for multiple lattice point.
96 rewriter.cloneRegionBefore(region&: *newBlock->getParent(), parent&: ifOp.getThenRegion(),
97 before: ifOp.getThenRegion().begin(), mapping);
98 // Remove the block arguments, they were already replaced via `mapping`.
99 ifOp.getThenRegion().front().eraseArguments(start: 0, num: blockArgs.size());
100
101 // replace sparse_tensor::YieldOp -> scf::YieldOp
102 auto spY = cast<sparse_tensor::YieldOp>(Val: &ifOp.getThenRegion().front().back());
103 ValueRange yields = spY.getResults();
104 rewriter.eraseOp(op: spY);
105 rewriter.setInsertionPointToEnd(&ifOp.getThenRegion().front());
106 scf::YieldOp::create(builder&: rewriter, location: loc, results: yields);
107
108 // Generates remaining case recursively.
109 rewriter.setInsertionPointToStart(&ifOp.getElseRegion().front());
110 ValueRange res = genCoIterateBranchNest(rewriter, loc, op, loopCrd, iters,
111 newBlocks: newBlocks.drop_front(),
112 oldBlocks: oldBlocks.drop_front(), userReduc);
113 if (!res.empty())
114 scf::YieldOp::create(builder&: rewriter, location: loc, results: res);
115
116 rewriter.setInsertionPointAfter(ifOp);
117 return ifOp.getResults();
118}
119
120static ValueRange genLoopWithIterator(
121 PatternRewriter &rewriter, Location loc, SparseIterator *it,
122 ValueRange reduc,
123 function_ref<SmallVector<Value>(PatternRewriter &rewriter, Location loc,
124 Region &loopBody, SparseIterator *it,
125 ValueRange reduc)>
126 bodyBuilder) {
127 if (it->iteratableByFor()) {
128 auto [lo, hi] = it->genForCond(b&: rewriter, l: loc);
129 Value step = constantIndex(builder&: rewriter, loc, i: 1);
130 scf::ForOp forOp = scf::ForOp::create(
131 builder&: rewriter, location: loc, lowerBound: lo, upperBound: hi, step, initArgs: reduc,
132 odsArg4: [&](OpBuilder &b, Location loc, Value iv, ValueRange iterArgs) {
133 // Empty builder function to ensure that no terminator is created.
134 });
135 {
136 OpBuilder::InsertionGuard guard(rewriter);
137 rewriter.setInsertionPointToStart(forOp.getBody());
138 if (it->randomAccessible())
139 it->locate(b&: rewriter, l: loc, crd: forOp.getInductionVar());
140 else
141 it->linkNewScope(pos: forOp.getInductionVar());
142 SmallVector<Value> ret = bodyBuilder(rewriter, loc, forOp.getBodyRegion(),
143 it, forOp.getRegionIterArgs());
144
145 rewriter.setInsertionPointToEnd(forOp.getBody());
146 scf::YieldOp::create(builder&: rewriter, location: loc, results: ret);
147 }
148 return forOp.getResults();
149 }
150
151 SmallVector<Value> ivs(reduc);
152 llvm::append_range(C&: ivs, R: it->getCursor());
153
154 TypeRange types = ValueRange(ivs).getTypes();
155 auto whileOp = scf::WhileOp::create(builder&: rewriter, location: loc, resultTypes: types, operands: ivs);
156 {
157 OpBuilder::InsertionGuard guard(rewriter);
158 // Generates loop conditions.
159 SmallVector<Location> l(types.size(), loc);
160 Block *before = rewriter.createBlock(parent: &whileOp.getBefore(), insertPt: {}, argTypes: types, locs: l);
161 rewriter.setInsertionPointToStart(before);
162 ValueRange bArgs = before->getArguments();
163 auto [whileCond, remArgs] = it->genWhileCond(b&: rewriter, l: loc, vs: bArgs);
164 scf::ConditionOp::create(builder&: rewriter, location: loc, condition: whileCond, args: before->getArguments());
165
166 // Delegates loop body generation.
167 Region &dstRegion = whileOp.getAfter();
168 Block *after = rewriter.createBlock(parent: &dstRegion, insertPt: {}, argTypes: types, locs: l);
169 ValueRange aArgs = whileOp.getAfterArguments();
170 it->linkNewScope(pos: aArgs.drop_front(n: reduc.size()));
171 aArgs = aArgs.take_front(n: reduc.size());
172
173 rewriter.setInsertionPointToStart(after);
174 SmallVector<Value> ret = bodyBuilder(rewriter, loc, dstRegion, it, aArgs);
175 rewriter.setInsertionPointToEnd(after);
176
177 // Forward loops
178 SmallVector<Value> yields;
179 llvm::append_range(C&: yields, R&: ret);
180 llvm::append_range(C&: yields, R: it->forward(b&: rewriter, l: loc));
181 scf::YieldOp::create(builder&: rewriter, location: loc, results: yields);
182 }
183 return whileOp.getResults().drop_front(n: it->getCursor().size());
184}
185
186namespace {
187
188/// Sparse codegen rule for number of entries operator.
189class ExtractIterSpaceConverter
190 : public OpConversionPattern<ExtractIterSpaceOp> {
191public:
192 using Base::Base;
193 LogicalResult
194 matchAndRewrite(ExtractIterSpaceOp op, OneToNOpAdaptor adaptor,
195 ConversionPatternRewriter &rewriter) const override {
196 Location loc = op.getLoc();
197
198 // Construct the iteration space.
199 SparseIterationSpace space(loc, rewriter,
200 llvm::getSingleElement(C: adaptor.getTensor()), 0,
201 op.getLvlRange(), adaptor.getParentIter());
202
203 SmallVector<Value> result = space.toValues();
204 rewriter.replaceOpWithMultiple(op, newValues: {result});
205 return success();
206 }
207};
208
209/// Sparse codegen rule for number of entries operator.
210class ExtractValOpConverter : public OpConversionPattern<ExtractValOp> {
211public:
212 using Base::Base;
213 LogicalResult
214 matchAndRewrite(ExtractValOp op, OneToNOpAdaptor adaptor,
215 ConversionPatternRewriter &rewriter) const override {
216 Location loc = op.getLoc();
217 Value pos = adaptor.getIterator().back();
218 Value valBuf = ToValuesOp::create(
219 builder&: rewriter, location: loc, tensor: llvm::getSingleElement(C: adaptor.getTensor()));
220 rewriter.replaceOpWithNewOp<memref::LoadOp>(op, args&: valBuf, args&: pos);
221 return success();
222 }
223};
224
225class SparseIterateOpConverter : public OpConversionPattern<IterateOp> {
226public:
227 using Base::Base;
228 LogicalResult
229 matchAndRewrite(IterateOp op, OneToNOpAdaptor adaptor,
230 ConversionPatternRewriter &rewriter) const override {
231 if (!op.getCrdUsedLvls().empty())
232 return rewriter.notifyMatchFailure(
233 arg&: op, msg: "non-empty coordinates list not implemented.");
234
235 Location loc = op.getLoc();
236
237 auto iterSpace = SparseIterationSpace::fromValues(
238 dstTp: op.getIterSpace().getType(), values: adaptor.getIterSpace(), tid: 0);
239
240 std::unique_ptr<SparseIterator> it =
241 iterSpace.extractIterator(b&: rewriter, l: loc);
242
243 SmallVector<Value> ivs;
244 for (ValueRange inits : adaptor.getInitArgs())
245 llvm::append_range(C&: ivs, R&: inits);
246
247 // Type conversion on iterate op block.
248 unsigned numOrigArgs = op.getBody()->getArgumentTypes().size();
249 TypeConverter::SignatureConversion signatureConversion(numOrigArgs);
250 if (failed(Result: typeConverter->convertSignatureArgs(
251 types: op.getBody()->getArgumentTypes(), result&: signatureConversion)))
252 return rewriter.notifyMatchFailure(
253 arg&: op, msg: "failed to convert iterate region argurment types");
254
255 Block *block = rewriter.applySignatureConversion(
256 block: op.getBody(), conversion&: signatureConversion, converter: getTypeConverter());
257 ValueRange ret = genLoopWithIterator(
258 rewriter, loc, it: it.get(), reduc: ivs,
259 bodyBuilder: [block](PatternRewriter &rewriter, Location loc, Region &loopBody,
260 SparseIterator *it, ValueRange reduc) -> SmallVector<Value> {
261 SmallVector<Value> blockArgs(reduc);
262 // TODO: Also appends coordinates if used.
263 // blockArgs.push_back(it->deref(rewriter, loc));
264 llvm::append_range(C&: blockArgs, R: it->getCursor());
265
266 Block *dstBlock = &loopBody.getBlocks().front();
267 rewriter.inlineBlockBefore(source: block, dest: dstBlock, before: dstBlock->end(),
268 argValues: blockArgs);
269 auto yield = llvm::cast<sparse_tensor::YieldOp>(Val&: dstBlock->back());
270 // We can not use ValueRange as the operation holding the values will
271 // be destroyed.
272 SmallVector<Value> result(yield.getResults());
273 rewriter.eraseOp(op: yield);
274 return result;
275 });
276
277 rewriter.replaceOp(op, newValues: ret);
278 return success();
279 }
280};
281
282class SparseCoIterateOpConverter : public OpConversionPattern<CoIterateOp> {
283 using Base::Base;
284
285 LogicalResult
286 matchAndRewrite(CoIterateOp op, OneToNOpAdaptor adaptor,
287 ConversionPatternRewriter &rewriter) const override {
288 assert(op.getSpaceDim() == 1 && "Not implemented");
289 Location loc = op.getLoc();
290
291 I64BitSet denseBits(0);
292 for (auto [idx, spaceTp] : llvm::enumerate(First: op.getIterSpaces().getTypes()))
293 if (all_of(Range: cast<IterSpaceType>(Val&: spaceTp).getLvlTypes(), P: isDenseLT))
294 denseBits.set(idx);
295
296 // If there exists a case that only contains dense spaces. I.e., case
297 // bits is a subset of dense bits, or when there is a full empty case (due
298 // to complements), we need a universal pointer to forward the coiteration
299 // loop.
300 bool needUniv =
301 any_of(Range: op.getRegionDefinedSpaces(), P: [denseBits](I64BitSet caseBits) {
302 // A case for complement.
303 if (caseBits.count() == 0)
304 return true;
305 // An all-dense case.
306 return caseBits.isSubSetOf(p: denseBits);
307 });
308 assert(!needUniv && "Not implemented");
309 (void)needUniv;
310
311 SmallVector<Block *> newBlocks;
312 DenseMap<Block *, Block *> newToOldBlockMap;
313 for (Region &region : op.getCaseRegions()) {
314 // Do a one-shot type conversion on all region blocks, since the same
315 // region might be used multiple time.
316 Block *block = &region.getBlocks().front();
317 TypeConverter::SignatureConversion blockTypeMapping(
318 block->getArgumentTypes().size());
319 if (failed(Result: typeConverter->convertSignatureArgs(types: block->getArgumentTypes(),
320 result&: blockTypeMapping))) {
321 return rewriter.notifyMatchFailure(
322 arg&: op, msg: "failed to convert coiterate region argurment types");
323 }
324
325 newBlocks.push_back(Elt: rewriter.applySignatureConversion(
326 block, conversion&: blockTypeMapping, converter: getTypeConverter()));
327 newToOldBlockMap[newBlocks.back()] = block;
328 }
329
330 SmallVector<SparseIterationSpace> spaces;
331 SmallVector<std::unique_ptr<SparseIterator>> iters;
332 for (auto [spaceTp, spaceVals] : llvm::zip_equal(
333 t: op.getIterSpaces().getTypes(), u: adaptor.getIterSpaces())) {
334 // TODO: do we really need tid?
335 spaces.push_back(Elt: SparseIterationSpace::fromValues(
336 dstTp: cast<IterSpaceType>(Val&: spaceTp), values: spaceVals, /*tid=*/0));
337 // Extract the iterator.
338 iters.push_back(Elt: spaces.back().extractIterator(b&: rewriter, l: loc));
339 }
340
341 auto getFilteredIters = [&iters](I64BitSet caseBits) {
342 // Retrives a vector of pointers to the iterators used in the case.
343 SmallVector<SparseIterator *> validIters;
344 for (auto idx : caseBits.bits())
345 validIters.push_back(Elt: iters[idx].get());
346 return validIters;
347 };
348
349 // Get a flattened user-provided loop reduction values.
350 SmallVector<Value> userReduc;
351 for (ValueRange r : adaptor.getInitArgs())
352 llvm::append_range(C&: userReduc, R&: r);
353
354 // TODO: we need to sort the cases such that they appears in lexical order.
355 // Although sparsification always generates cases in that order, it might
356 // not be the case for human-written code.
357
358 // Generates a loop sequence, one loop per case.
359 for (auto [r, caseBits] :
360 llvm::zip_equal(t&: newBlocks, u: op.getRegionDefinedSpaces())) {
361 assert(caseBits.count() > 0 && "Complement space not implemented");
362
363 // Retrives a vector of pointers to the iterators used in the case.
364 SmallVector<SparseIterator *> validIters = getFilteredIters(caseBits);
365
366 if (validIters.size() > 1) {
367 auto [loop, loopCrd] =
368 genCoIteration(builder&: rewriter, loc, iters: validIters, reduc: userReduc,
369 /*uniIdx=*/nullptr, /*userReducFirst=*/true);
370
371 // 1st. find all the cases that is a strict subset of the current case
372 // condition, for which we generate one branch per case inside the loop.
373 // The subcases are never empty, it must contains at least the current
374 // region itself.
375 // TODO: these cases should be sorted.
376 SmallVector<Region *> subCases =
377 op.getSubCasesOf(regionIdx: r->getParent()->getRegionNumber());
378 SmallVector<Block *> newBlocks, oldBlocks;
379 for (Region *r : subCases) {
380 newBlocks.push_back(Elt: &r->front());
381 oldBlocks.push_back(Elt: newToOldBlockMap[newBlocks.back()]);
382 }
383 assert(!subCases.empty());
384
385 ValueRange res = genCoIterateBranchNest(
386 rewriter, loc, op, loopCrd, iters, newBlocks, oldBlocks, userReduc);
387
388 SmallVector<Value> nextIterYields(res);
389 // 2nd. foward the loop.
390 for (SparseIterator *it : validIters) {
391 Value cmp = arith::CmpIOp::create(
392 builder&: rewriter, location: loc, predicate: arith::CmpIPredicate::eq, lhs: it->getCrd(), rhs: loopCrd);
393 it->forwardIf(b&: rewriter, l: loc, cond: cmp);
394 llvm::append_range(C&: nextIterYields, R: it->getCursor());
395 }
396 scf::YieldOp::create(builder&: rewriter, location: loc, results: nextIterYields);
397
398 // Exit the loop, relink the iterator SSA value.
399 rewriter.setInsertionPointAfter(loop);
400 ValueRange iterVals = loop->getResults().drop_front(n: userReduc.size());
401 for (SparseIterator *it : validIters)
402 iterVals = it->linkNewScope(pos: iterVals);
403 assert(iterVals.empty());
404
405 ValueRange curResult = loop->getResults().take_front(n: userReduc.size());
406 userReduc.assign(in_start: curResult.begin(), in_end: curResult.end());
407 } else {
408 // This is a simple iteration loop.
409 assert(caseBits.count() == 1);
410
411 Block *block = r;
412 ValueRange curResult = genLoopWithIterator(
413 rewriter, loc, it: validIters.front(), reduc: userReduc,
414 /*bodyBuilder=*/
415 [block](PatternRewriter &rewriter, Location loc, Region &dstRegion,
416 SparseIterator *it,
417 ValueRange reduc) -> SmallVector<Value> {
418 SmallVector<Value> blockArgs(reduc);
419 blockArgs.push_back(Elt: it->deref(b&: rewriter, l: loc));
420 llvm::append_range(C&: blockArgs, R: it->getCursor());
421
422 Block *dstBlock = &dstRegion.getBlocks().front();
423 rewriter.inlineBlockBefore(
424 source: block, dest: dstBlock, before: rewriter.getInsertionPoint(), argValues: blockArgs);
425 auto yield = llvm::cast<sparse_tensor::YieldOp>(Val&: dstBlock->back());
426 SmallVector<Value> result(yield.getResults());
427 rewriter.eraseOp(op: yield);
428 return result;
429 });
430
431 userReduc.assign(in_start: curResult.begin(), in_end: curResult.end());
432 }
433 }
434
435 rewriter.replaceOp(op, newValues: userReduc);
436 return success();
437 }
438};
439
440} // namespace
441
442mlir::SparseIterationTypeConverter::SparseIterationTypeConverter() {
443 addConversion(callback: [](Type type) { return type; });
444 addConversion(callback&: convertIteratorType);
445 addConversion(callback&: convertIterSpaceType);
446
447 addSourceMaterialization(callback: [](OpBuilder &builder, IterSpaceType spTp,
448 ValueRange inputs, Location loc) -> Value {
449 return UnrealizedConversionCastOp::create(builder, location: loc, resultTypes: TypeRange(spTp),
450 operands: inputs)
451 .getResult(i: 0);
452 });
453}
454
455void mlir::populateLowerSparseIterationToSCFPatterns(
456 const TypeConverter &converter, RewritePatternSet &patterns) {
457
458 IterateOp::getCanonicalizationPatterns(results&: patterns, context: patterns.getContext());
459 patterns.add<ExtractIterSpaceConverter, ExtractValOpConverter,
460 SparseIterateOpConverter, SparseCoIterateOpConverter>(
461 arg: converter, args: patterns.getContext());
462}
463