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