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