[mlir][sparse][gpu] recognizing sddmm pattern in GPU libgen path

[K-Wu]

rebase origin/main with sddmm op added

[K-Wu]

clang-format

[K-Wu]

rebase origin/main

[K-Wu]

add test

[K-Wu]

involving the test

[K-Wu]

mlir/test/Dialect/SparseTensor/GPU/gpu_sampled_matmul_lib.mlir

88

can we instead output #CSR type here?

[K-Wu]

incorporating Aart's test case

[K-Wu]

add an in-place (from above, i.e., the program input) op test

[K-Wu]

format

[K-Wu]

saving progress

[K-Wu]

fixing compile error; remove repeated test case

[K-Wu]

adding more tests

[K-Wu]

update comment

[K-Wu]

rebase origin/main

[K-Wu]

drafting rewrite rule

[K-Wu]

saving progress

[K-Wu]

add rules and update tests

[K-Wu]

fix filechck parsing error

[K-Wu]

mlir/lib/Dialect/SparseTensor/Transforms/SparseGPUCodegen.cpp

879

rewrite rule here

[K-Wu]

mlir/test/Integration/Dialect/SparseTensor/GPU/CUDA/sparse-sampled-matmul-lib.mlir

43

TODO: add checking logic

[K-Wu]

mlir/test/Integration/Dialect/SparseTensor/GPU/CUDA/sparse-sampled-matmul-lib.mlir

43

Didn't notice there is already checking logic down below. Closing this

[K-Wu]

mlir/test/Dialect/SparseTensor/GPU/gpu_sampled_matmul_lib.mlir

98

%1 = sparse_tensor_in_place_result %args: tensor<8x8xf64, #SM> // something new, I have to think about it

%2 = linalg.generic #trait_sampled_dense_dense
  ins(%args, %arga, %argb: tensor<8x8xf64, #SM>,
                           tensor<8x8xf64>, tensor<8x8xf64>)
  outs(%1: tensor<8x8xf64, #SM>) {
    ^bb(%s: f64, %a: f64, %b: f64, %x: f64):
      %p = arith.mulf %a, %b : f64
      %q = arith.mulf %s, %p : f64
      %r = arith.addf %x, %q : f64
      linalg.yield %r : f64
} -> tensor<8x8xf64, #SM>
return %2 : tensor<8x8xf64, #SM>

[K-Wu]

fix integration test

[K-Wu]

rebase; clean up a bit rule

[K-Wu]

reformat

[aartbik]

mlir/lib/Dialect/SparseTensor/Transforms/SparseGPUCodegen.cpp

623

we test that C is sparse, but no test at all for D

So, the code below will sometimes crash, since it uses information on C not D
(e.g. isCOO)

628

this comment says more than is done below, is this a note to self, or something else?

632

you miss the d : row here

644

This assumes that D has exactly the same pattern already as C (or more precisely, the right length for all the arrays into which we copy the result). Perhaps we should start with simply returning C again after this operation, and find a way to allow this at IR level.

723

This is the wrong replacement, we need

rewriter.replaceOpWithNewOp<sparse_tensor::LoadOp>(op, ....)

and probably without inserts.

mlir/test/Dialect/SparseTensor/GPU/gpu_sampled_matmul_lib.mlir

111

can you remove this part with reuse completely, I think we will just need the pattern above for proper testing

mlir/test/Integration/Dialect/SparseTensor/GPU/CUDA/sparse-sampled-matmul-lib.mlir

47

dense output, does not go through the GPU kernel then, right?

[K-Wu]

upd test cases to reflect actual need though not passing yet

[K-Wu]

incorporating aart's ad hoc solution

[aartbik]

mlir/lib/Dialect/SparseTensor/Transforms/SparseGPUCodegen.cpp

617

please fix 80-col breaks here in comment

619

I think we need a

if (op.getDpsInitOperand(0) != c)
return failure();

here to enforce the ad-hoc pattern

mlir/test/Dialect/SparseTensor/GPU/gpu_sampled_matmul_lib.mlir

105

perhaps add

TODO: find a cleaner way to express this

mlir/test/Integration/Dialect/SparseTensor/GPU/CUDA/sparse-sampled-matmul-lib.mlir

48

Put the comment about the ad-hoc idiom here too, so we don't forget.
Also the TODO.

93

Just curious if you really want to use the from-file set up of the sampling matrix? We can also just create this in memory like so many other examples, right?

[aartbik]

mlir/lib/Dialect/SparseTensor/Transforms/SparseGPUCodegen.cpp

619

Or probably more precisely after preproc

%0 = bufferization.alloc_tensor() copy(%arg0)

op.getDpsInitOperand(0).getDefiningOp

links to

%0 = bufferization.alloc_tensor() copy(%c)

723

Make sure to return

sparse_tensor.load %arg0

instead of just %arg0, since the rematerialization needs to be made explicit.
You will find an example of this in e.g. the method sparse_simply_dynamic1() in the sparse_out.mlir test

[K-Wu]

still fixing

[K-Wu]

addressing comments

[K-Wu]

correcting the sddmm rewriter and tests except for the recognition rule

[K-Wu]

addressing comment

[K-Wu]

incorporating the new pattern

[K-Wu]

passed tests it seems

[K-Wu]

mlir/test/Integration/Dialect/SparseTensor/GPU/CUDA/sparse-sampled-matmul-lib.mlir

93

Okay I will incorporate it next time

[Peiming]

mlir/lib/Dialect/SparseTensor/Transforms/SparseGPUCodegen.cpp

334–351

The nest is too deep here. Could you either try to break it into more functions or early returns on some simple conditions?

e.g.,

if (!isa_and_nonnull(def)) 
   return false;

Value s_out = xxx
xxx

[aartbik]

mlir/test/Integration/Dialect/SparseTensor/GPU/CUDA/sparse-sampled-matmul-lib.mlir

48

We can now use https://reviews.llvm.org/D152969
and remove all comments about hacks, since this is proper in-place
definition that matches cuSPARSE precisely.

[aartbik]

mlir/lib/ExecutionEngine/CudaRuntimeWrappers.cpp

274 ↗

(On Diff #531523)

actually with the new formulation, you no longer need this since this is proper

S(I,J) = SPY( S(I,J) ) x SUM_K A(I,K) B(K,J) * alpha + beta * S(I,J)

[K-Wu]

removing obsolete comments

[K-Wu]

mlir/lib/Dialect/SparseTensor/Transforms/SparseGPUCodegen.cpp

334–351

Good point and example! Incorporated

[K-Wu]

incorporating comments

[Peiming]

mlir/lib/Dialect/SparseTensor/Transforms/SparseGPUCodegen.cpp

335

You need to do a null check too

[K-Wu]

addressing comment

[K-Wu]

rebase origin/main

[aartbik]

mlir/lib/Dialect/SparseTensor/Transforms/SparseGPUCodegen.cpp

332

Add comment

// Helper to detect .....

344

return s_out == use->getOperand(0); ?

348

This seems way too simple. You pretty much match any

%1 = sparse_tensor.unary
%2 = sparse_tensor.reduce

but you don't check that %1 produces A * B and %2 produces sum accumulation

It will match the current example, but also much more! Please fix

641

remove this TODO. The current idiom has in-place semantics that will be correctly dealt with by bufferization

mlir/test/Integration/Dialect/SparseTensor/GPU/CUDA/sparse-sampled-matmul-lib.mlir

116

releasing %0 feels cleaner, so that we have the in-place behavior clear

[K-Wu]

rebase

[K-Wu]

addressing comments

[K-Wu]

fixing compile errors

[aartbik]

mlir/lib/Dialect/SparseTensor/Transforms/SparseGPUCodegen.cpp

335

You will often find the idiom

if (Operation *def = ....getDefiningOp()) {

use def

}

for this purpose, which you can even combine with the isa

if (Operation *def getDefiningOp<...>

353

technically, you have not checked if unary feeds into reduce, right?
or did I miss that?

[K-Wu]

fix errors

[K-Wu]

fixing runtime error

[K-Wu]

fix format

[K-Wu]

mlir/lib/Dialect/SparseTensor/Transforms/SparseGPUCodegen.cpp

344

This is checked two times in the loop so I don't find an easy way to simplify the logic

mlir/lib/Dialect/SparseTensor/Transforms/SparseGPUCodegen.cpp

if (isa<arith::AddFOp>(def) || isa<arith::AddIOp>(def)) {
               matchMulOfArgs(op, def->getOperand(1))) ||
              (def->getOperand(1) == x &&
               matchMulOfArgs(op, def->getOperand(0)));
     }
   }
   return false;
 }
 
 /// Test for sorted COO with suitable data and coordinates types.
 static bool isAdmissibleCOO(SparseTensorType &aTp) {
   return aTp.isCompressedLvl(0) && aTp.isOrderedLvl(0) && !aTp.isUniqueLvl(0) &&
          aTp.isSingletonLvl(1) && aTp.isOrderedLvl(1) && aTp.isUniqueLvl(1) &&
          (aTp.getElementType().isF64() || aTp.getElementType().isF32()) &&
          (aTp.getCrdWidth() == 0 || aTp.getCrdWidth() == 32 ||
           aTp.getCrdWidth() == 64);
 }
 
 /// Test for CSR with suitable data and coordinates types.
 static bool isAdmissibleCSR(SparseTensorType &aTp) {
   return aTp.isDenseLvl(0) && aTp.isCompressedLvl(1) && aTp.isOrderedLvl(1) &&
          aTp.isUniqueLvl(1) &&
          (aTp.getElementType().isF64() || aTp.getElementType().isF32()) &&
          (aTp.getCrdWidth() == 0 || aTp.getCrdWidth() == 32 ||
           aTp.getCrdWidth() == 64);
 }
 
 /// Test for admissible types on operands (with output parameter `isCOO`).
 static bool areAdmissibleTypes(SparseTensorType aTp, SparseTensorType bTp,
                                SparseTensorType cTp, bool enableRT,
                                bool &isCOO) {
   if (bTp.hasEncoding() || cTp.hasEncoding())
     return false;
   if (isAdmissibleCOO(aTp)) {
     isCOO = true;
     return enableRT; // TODO: CreateCooAoSOp was deprecated, find another way
   }
   return isAdmissibleCSR(aTp);
 }
static LogicalResult rewriteSpMM(PatternRewriter &rewriter,
   genBlockingWait(rewriter, loc, tokens);
   tokens.clear();
 
   // Done.
   rewriter.replaceOpWithNewOp<bufferization::ToTensorOp>(op, bufC);
   return success();
 }
 
+/// Match and rewrite SDDMM kernel.
+static LogicalResult rewriteSDDMM(PatternRewriter &rewriter, linalg::GenericOp op,
+                     bool enableRT) {
+  Location loc = op.getLoc();
+  Value a = op.getOperand(1);
+  Value b = op.getOperand(2);
+  Value c = op.getOperand(0); // we have C = AB
+  SmallVector<Value> tokens;
+
+  // Only admissible sparse matrix format and dense matrices.
+  bool isCOO = false;
+  SparseTensorType aTp = getSparseTensorType(a);
+  SparseTensorType bTp = getSparseTensorType(b);
+  SparseTensorType cTp = getSparseTensorType(c);
+  if (!areAdmissibleTypes(aTp, bTp, cTp, enableRT, isCOO))
+    return failure();
+
+  // TODO: duplicate C and update its user later than this GenericOp line if it
+  // is used by other ops.
+
+  // the following does the in-place operation. If the sparse matrix C is
+  // reused, we may need to copy it before the operation so that users could use
+  // the new copy instead. Start sparse kernel and copy data from host to
+  // device.
+  // TODO: assert no other uses of c is later than this GenericOp operator
+
+  //   a : bufA           -> matA
+  //   b : bufB           -> matA
+  //   c : memR/memC/memV -> rowC,colC,valC
+  Value nseC = rewriter.create<NumberOfEntriesOp>(loc, a);
+  Value szm = linalg::createOrFoldDimOp(rewriter, loc, a, 0);
+  Value szk = linalg::createOrFoldDimOp(rewriter, loc, a, 1);
+  Value szn = linalg::createOrFoldDimOp(rewriter, loc, b, 1);
+  Value bufA = genTensorToMemref(rewriter, loc, a);
+  Value matA = genAllocCopy(rewriter, loc, bufA, tokens);
+  Value bufB = genTensorToMemref(rewriter, loc, b);
+  Value matB = genAllocCopy(rewriter, loc, bufB, tokens);
+  Value memR = genFirstPosOrCrds(rewriter, loc, c, isCOO, enableRT);
+  Value memC = genSecondCrds(rewriter, loc, c, isCOO, enableRT);
+  Value memV = genToValues(rewriter, loc, c);
+  Value rowC = genAllocCopy(rewriter, loc, memR, tokens);
+  Value colC = memC ? genAllocCopy(rewriter, loc, memC, tokens) : Value();
+  Value valC = genAllocCopy(rewriter, loc, memV, tokens);
+  genBlockingWait(rewriter, loc, tokens);
+  tokens.clear();
+
+  // Create sparse environment and sparse matrix/dense matrix handles.
+  Type indexTp = rewriter.getIndexType();
+  Type envHandleTp = rewriter.getType<gpu::SparseEnvHandleType>();
+  Type dnMatHandleTp = rewriter.getType<gpu::SparseDnMatHandleType>();
+  Type spMatHandleTp = rewriter.getType<gpu::SparseSpMatHandleType>();
+  Type tokenTp = rewriter.getType<gpu::AsyncTokenType>();
+  Value token = genFirstWait(rewriter, loc);
+  auto env =
+      rewriter.create<gpu::CreateSparseEnvOp>(loc, envHandleTp, tokenTp, token);
+  Value handle = env.getResult(0);
+  token = env.getAsyncToken();
+
+  auto dmatA = rewriter.create<gpu::CreateDnMatOp>(loc, dnMatHandleTp, tokenTp,
+                                                   token, szm, szk, matA);
+  Value dnA = dmatA.getResult(0);
+  token = dmatA.getAsyncToken();
+  auto dmatB = rewriter.create<gpu::CreateDnMatOp>(loc, dnMatHandleTp, tokenTp,
+                                                   token, szk, szn, matB);
+  Value dnB = dmatB.getResult(0);
+  token = dmatB.getAsyncToken();
+
+  Operation *spGenC =
+      genSpMat(rewriter, loc, spMatHandleTp, tokenTp, token, szm, szn, nseC,
+               rowC, colC, valC, isCOO, enableRT);
+  Value spMatC = spGenC->getResult(0);
+  token = spGenC->getResult(1);
+
+  // Precompute buffersize for SDDMM.
+  auto bufferComp = rewriter.create<gpu::SDDMMBufferSizeOp>(
+      loc, indexTp, tokenTp, token, handle, dnA, dnB, spMatC);
+  Value bufferSz = bufferComp.getResult(0);
+  token = bufferComp.getAsyncToken();
+  auto buf = genAllocBuffer(rewriter, loc, bufferSz, token);
+  Value buffer = buf.getResult(0);
+  token = buf.getAsyncToken();
+
+  // Perform the SDDMM.
+  auto sddmmComp = rewriter.create<gpu::SDDMMOp>(loc, tokenTp, token, handle,
+                                                 dnA, dnB, spMatC, buffer);
+  token = sddmmComp.getAsyncToken();
+
+  // Copy data back to host and free all the resoures.
+  token = rewriter.create<gpu::DestroyDnMatOp>(loc, tokenTp, token, dnA)
+              .getAsyncToken();
+  token = rewriter.create<gpu::DestroyDnMatOp>(loc, tokenTp, token, dnB)
+              .getAsyncToken();
+  token = rewriter.create<gpu::DestroySpMatOp>(loc, tokenTp, token, spMatC)
+              .getAsyncToken();
+  token = rewriter.create<gpu::DestroySparseEnvOp>(loc, tokenTp, token, handle)
+              .getAsyncToken();
+  tokens.push_back(token);
+  genBlockingWait(rewriter, loc, tokens);
+  tokens.clear();
+  token = genFirstWait(rewriter, loc);
+  token = genCopyMemRef(rewriter, loc, memR, rowC, token);
+  token = genCopyMemRef(rewriter, loc, memC, colC, token);
+  token = genCopyMemRef(rewriter, loc, memV, valC, token);
+  token = genDeallocMemRef(rewriter, loc, buffer, token);
+  token = genDeallocMemRef(rewriter, loc, matA, token);
+  token = genDeallocMemRef(rewriter, loc, matB, token);
+  token = genDeallocMemRef(rewriter, loc, rowC, token);
+  if (colC)
+    token = genDeallocMemRef(rewriter, loc, colC, token);
+  token = genDeallocMemRef(rewriter, loc, valC, token);
+  tokens.push_back(token);
+  genBlockingWait(rewriter, loc, tokens);
+  tokens.clear();
+
+  // Done.
+  rewriter.replaceOp(op, op.getDpsInitOperand(0)->get());
+  return success();
+}
+
 //===----------------------------------------------------------------------===//
 // Rewriting rules for direct code generation.
 //===----------------------------------------------------------------------===//
 
 /// Proof-of-concept rewriter. This rule generates a GPU implementation
 /// for each outermost forall loop generated by the sparse compiler.
 /// TODO: right works with parallelization-strategy=dense-outer-loop
 ///       but give this its own flags in the future
if (numLoops == 3 && numTensors == 3 &&
         linalg::isReductionIterator(iteratorTypes[2]) &&
         // TODO: add transposed {i, k}, {k, j}
         // TODO: maybe add transposed {i, j} in future
         maps == infer({{i, k}, {k, j}, {i, j}}) && matchSumOfMultOfArgs(op)) {
       return rewriteSpMM(rewriter, op, enableRT);
     }
 
     return failure();
   }
 
 private:
   bool enableRT;
 };
 
 } // namespace
 
 //===----------------------------------------------------------------------===//

mlir/test/Dialect/SparseTensor/GPU/gpu_sampled_matmul_lib.mlir

+// RUN: mlir-opt %s --linalg-generalize-named-ops \
+// RUN:             --sparsification="enable-gpu-libgen" | FileCheck %s
+
+#trait_sampled_dense_dense = {
+  indexing_maps = [
+    affine_map<(i,j,k) -> (i,j)>,  // S
+    affine_map<(i,j,k) -> (i,k)>,  // A
+    affine_map<(i,j,k) -> (k,j)>,  // B
+    affine_map<(i,j,k) -> (i,j)>   // X (out)
+  ],
+  iterator_types = ["parallel", "parallel", "reduction"],
+  doc = "X(i,j) += S(i,j) SUM_k A(i,k) B(k,j)"
+}
+
+#trait_vec_op = {
+  indexing_maps = [
+    affine_map<(i,j) -> (i,j)>,  // a (in)
+    affine_map<(i,j) -> (i,j)>,  // b (in)
+    affine_map<(i,j) -> (i,j)>   // x (out)
+  ],
+  iterator_types = ["parallel", "parallel"]
+}
+
+#CSR = #sparse_tensor.encoding<{ lvlTypes = [ "dense", "compressed" ] }>
+
+module {
+
+//
+// A kernel that computes a direct sampled matrix matrix multiplication
+// (with sparse result).
+// Compute SDDMM C = C\spy AB
+// VAL_0 is C
+//
+// CHECK-LABEL:   func.func @sampled_dense_dense_matmul(
+// CHECK-SAME:      %[[VAL_0:.*]]: tensor<?x?xf64, #sparse_tensor.encoding<{{{.*}}}>>,
+// CHECK-SAME:      %[[VAL_1:.*]]: tensor<?x?xf64>,
+// CHECK-SAME:      %[[VAL_2:.*]]: tensor<?x?xf64>) -> tensor<?x?xf64> {
+// CHECK-DAG:       %[[VAL_3:.*]] = arith.constant 0 : index
+// CHECK-DAG:       %[[VAL_4:.*]] = arith.constant 1 : index
+// CHECK-DAG:       %[[VAL_5:.*]] = sparse_tensor.number_of_entries %[[VAL_0]] : tensor<?x?xf64, #sparse_tensor.encoding<{{{.*}}}>>
+// CHECK-DAG:       %[[VAL_6:.*]] = tensor.dim %[[VAL_0]], %[[VAL_3]] : tensor<?x?xf64, #sparse_tensor.encoding<{{{.*}}}>>
+// CHECK-DAG:       %[[VAL_7:.*]] = tensor.dim %[[VAL_0]], %[[VAL_4]] : tensor<?x?xf64, #sparse_tensor.encoding<{{{.*}}}>>
+// CHECK-DAG:       %[[VAL_8:.*]] = tensor.dim %[[VAL_1]], %[[VAL_4]] : tensor<?x?xf64>
+// CHECK-DAG:       %[[VAL_9:.*]] = sparse_tensor.positions %[[VAL_0]] {level = 1 : index} : tensor<?x?xf64, #sparse_tensor.encoding<{{{.*}}}>> to memref<?xindex>
+// CHECK-DAG:       %[[VAL_10:.*]] = sparse_tensor.coordinates %[[VAL_0]] {level = 1 : index} : tensor<?x?xf64, #sparse_tensor.encoding<{{{.*}}}>> to memref<?xindex>
+// CHECK-DAG:       %[[VAL_11:.*]] = sparse_tensor.values %[[VAL_0]] : tensor<?x?xf64, #sparse_tensor.encoding<{{{.*}}}>> to memref<?xf64>
+// CHECK:           %[[VAL_12:.*]] = gpu.wait async
+// CHECK:           %[[VAL_13:.*]] = memref.dim %[[VAL_9]], %[[VAL_3]] : memref<?xindex>
+// CHECK:           %[[VAL_14:.*]], %[[VAL_15:.*]] = gpu.alloc async {{\[}}%[[VAL_12]]] (%[[VAL_13]]) : memref<?xindex>
+// CHECK:           %[[VAL_16:.*]] = gpu.memcpy async {{\[}}%[[VAL_15]]] %[[VAL_14]], %[[VAL_9]] : memref<?xindex>, memref<?xindex>
+// CHECK:           %[[VAL_17:.*]] = gpu.wait async
+// CHECK:           %[[VAL_18:.*]] = memref.dim %[[VAL_10]], %[[VAL_3]] : memref<?xindex>
+// CHECK:           %[[VAL_19:.*]], %[[VAL_20:.*]] = gpu.alloc async {{\[}}%[[VAL_17]]] (%[[VAL_18]]) : memref<?xindex>
+// CHECK:           %[[VAL_21:.*]] = gpu.memcpy async {{\[}}%[[VAL_20]]] %[[VAL_19]], %[[VAL_10]] : memref<?xindex>, memref<?xindex>
+// CHECK:           %[[VAL_22:.*]] = gpu.wait async
+// CHECK:           %[[VAL_23:.*]] = memref.dim %[[VAL_11]], %[[VAL_3]] : memref<?xf64>
+// CHECK:           %[[VAL_24:.*]], %[[VAL_25:.*]] = gpu.alloc async {{\[}}%[[VAL_22]]] (%[[VAL_23]]) : memref<?xf64>
+// CHECK:           %[[VAL_26:.*]] = gpu.memcpy async {{\[}}%[[VAL_25]]] %[[VAL_24]], %[[VAL_11]] : memref<?xf64>, memref<?xf64>
+// CHECK:           %[[VAL_27:.*]] = bufferization.to_memref %[[VAL_1]] : memref<?x?xf64>
+// CHECK:           %[[VAL_28:.*]] = gpu.wait async
+// CHECK:           %[[VAL_29:.*]] = memref.dim %[[VAL_27]], %[[VAL_3]] : memref<?x?xf64>
+// CHECK:           %[[VAL_30:.*]] = memref.dim %[[VAL_27]], %[[VAL_4]] : memref<?x?xf64>
+// CHECK:           %[[VAL_31:.*]], %[[VAL_32:.*]] = gpu.alloc async {{\[}}%[[VAL_28]]] (%[[VAL_29]], %[[VAL_30]]) : memref<?x?xf64>
+// CHECK:           %[[VAL_33:.*]] = gpu.memcpy async {{\[}}%[[VAL_32]]] %[[VAL_31]], %[[VAL_27]] : memref<?x?xf64>, memref<?x?xf64>
+// CHECK:           %[[VAL_34:.*]] = bufferization.to_memref %[[VAL_2]] : memref<?x?xf64>
+// CHECK:           %[[VAL_35:.*]] = gpu.wait async
+// CHECK:           %[[VAL_36:.*]] = memref.dim %[[VAL_34]], %[[VAL_3]] : memref<?x?xf64>
+// CHECK:           %[[VAL_37:.*]] = memref.dim %[[VAL_34]], %[[VAL_4]] : memref<?x?xf64>
+// CHECK:           %[[VAL_38:.*]], %[[VAL_39:.*]] = gpu.alloc async {{\[}}%[[VAL_35]]] (%[[VAL_36]], %[[VAL_37]]) : memref<?x?xf64>
+// CHECK:           %[[VAL_40:.*]] = gpu.memcpy async {{\[}}%[[VAL_39]]] %[[VAL_38]], %[[VAL_34]] : memref<?x?xf64>, memref<?x?xf64>
+// CHECK:           gpu.wait {{\[}}%[[VAL_16]], %[[VAL_21]], %[[VAL_26]], %[[VAL_33]], %[[VAL_40]]]
+// CHECK:           %[[VAL_41:.*]] = gpu.wait async
+// CHECK:           %[[VAL_42:.*]], %[[VAL_43:.*]] = gpu.create_sparse_env async {{\[}}%[[VAL_41]]]
+// CHECK:           %[[VAL_44:.*]], %[[VAL_45:.*]] = gpu.create_csr async {{\[}}%[[VAL_43]]] %[[VAL_6]], %[[VAL_7]], %[[VAL_5]], %[[VAL_14]], %[[VAL_19]], %[[VAL_24]] : memref<?xindex>, memref<?xindex>, memref<?xf64>
+// CHECK:           %[[VAL_46:.*]], %[[VAL_47:.*]] = gpu.create_dn_mat async {{\[}}%[[VAL_45]]] %[[VAL_7]], %[[VAL_8]], %[[VAL_31]] : memref<?x?xf64>
+// CHECK:           %[[VAL_48:.*]], %[[VAL_49:.*]] = gpu.create_dn_mat async {{\[}}%[[VAL_47]]] %[[VAL_6]], %[[VAL_8]], %[[VAL_38]] : memref<?x?xf64>
+// CHECK:           %[[VAL_50:.*]], %[[VAL_51:.*]] = gpu.sddmm_buffer_size async {{\[}}%[[VAL_49]]] %[[VAL_42]], %[[VAL_44]], %[[VAL_46]], %[[VAL_48]]
+// CHECK:           %[[VAL_52:.*]], %[[VAL_53:.*]] = gpu.alloc async {{\[}}%[[VAL_51]]] (%[[VAL_50]]) : memref<?xi8>
+// CHECK:           %[[VAL_54:.*]] = gpu.sddmm async {{\[}}%[[VAL_53]]] %[[VAL_42]], %[[VAL_44]], %[[VAL_46]], %[[VAL_48]], %[[VAL_52]] : memref<?xi8>
+// CHECK:           %[[VAL_55:.*]] = gpu.destroy_sp_mat async {{\[}}%[[VAL_54]]] %[[VAL_44]]
+// CHECK:           %[[VAL_56:.*]] = gpu.destroy_dn_mat async {{\[}}%[[VAL_55]]] %[[VAL_46]]
+// CHECK:           %[[VAL_57:.*]] = gpu.destroy_dn_mat async {{\[}}%[[VAL_56]]] %[[VAL_48]]
+// CHECK:           %[[VAL_58:.*]] = gpu.destroy_sparse_env async {{\[}}%[[VAL_57]]] %[[VAL_42]]
+// CHECK:           %[[VAL_59:.*]] = gpu.dealloc async {{\[}}%[[VAL_58]]] %[[VAL_14]] : memref<?xindex>
+// CHECK:           %[[VAL_60:.*]] = gpu.dealloc async {{\[}}%[[VAL_59]]] %[[VAL_19]] : memref<?xindex>
+// CHECK:           %[[VAL_61:.*]] = gpu.dealloc async {{\[}}%[[VAL_60]]] %[[VAL_24]] : memref<?xf64>
+// CHECK:           %[[VAL_62:.*]] = gpu.dealloc async {{\[}}%[[VAL_61]]] %[[VAL_52]] : memref<?xi8>
+// CHECK:           %[[VAL_63:.*]] = gpu.dealloc async {{\[}}%[[VAL_62]]] %[[VAL_31]] : memref<?x?xf64>
+// CHECK:           %[[VAL_64:.*]] = gpu.memcpy async {{\[}}%[[VAL_63]]] %[[VAL_34]], %[[VAL_38]] : memref<?x?xf64>, memref<?x?xf64>
+// CHECK:           %[[VAL_65:.*]] = gpu.dealloc async {{\[}}%[[VAL_64]]] %[[VAL_38]] : memref<?x?xf64>
+// CHECK:           gpu.wait {{\[}}%[[VAL_65]]]
+// CHECK:           %[[VAL_66:.*]] = bufferization.to_tensor %[[VAL_34]] : memref<?x?xf64>
+// CHECK:           return %[[VAL_66]] : tensor<?x?xf64>
+// CHECK:         }
+func.func @sparse_sampled_dd(%args: tensor<8x8xf64, #CSR>,
+                              %arga: tensor<8x8xf64>,
+                              %argb: tensor<8x8xf64>) -> tensor<8x8xf64, #CSR> {
+  %1 = bufferization.alloc_tensor() : tensor<8x8xf64, #CSR>
+  %2 = linalg.generic #trait_sampled_dense_dense
+    ins(%args, %arga, %argb: tensor<8x8xf64, #CSR>,
+                              tensor<8x8xf64>, tensor<8x8xf64>)
+    outs(%1: tensor<8x8xf64, #CSR>) {
+      ^bb(%s: f64, %a: f64, %b: f64, %x: f64):
+        %p = arith.mulf %a, %b : f64 
+        %q = arith.mulf %s, %p : f64
+        %r = arith.addf %x, %q : f64
+        linalg.yield %r : f64
+  } -> tensor<8x8xf64, #CSR>
+  return %2 : tensor<8x8xf64, #CSR>
+}
+
+func.func @sparse_sampled_dd_with_reuse(%args: tensor<8x8xf64, #CSR>,
+                              %arga: tensor<8x8xf64>,
+                              %argb: tensor<8x8xf64>) -> tensor<8x8xf64, #CSR> {
+  %1 = bufferization.alloc_tensor() : tensor<8x8xf64, #CSR>
+  %2 = linalg.generic #trait_sampled_dense_dense
+    ins(%args, %arga, %argb: tensor<8x8xf64, #CSR>,
+                              tensor<8x8xf64>, tensor<8x8xf64>)
+    outs(%1: tensor<8x8xf64, #CSR>) {
+      ^bb(%s: f64, %a: f64, %b: f64, %x: f64):
+        %p = arith.mulf %a, %b : f64 
+        %q = arith.mulf %s, %p : f64
+        %r = arith.addf %x, %q : f64
+        linalg.yield %r : f64
+  } -> tensor<8x8xf64, #CSR>
+
+  // reuse the input by doing the computation again
+  %3 = bufferization.alloc_tensor() : tensor<8x8xf64, #CSR>
+  %4 = linalg.generic #trait_sampled_dense_dense
+    ins(%args, %arga, %argb: tensor<8x8xf64, #CSR>,
+                              tensor<8x8xf64>, tensor<8x8xf64>)
+    outs(%3: tensor<8x8xf64, #CSR>) {
+      ^bb(%s: f64, %a: f64, %b: f64, %x: f64):
+        %p = arith.mulf %a, %b : f64 
+        %q = arith.mulf %s, %p : f64
+        %r = arith.addf %x, %q : f64
+        linalg.yield %r : f64
+  } -> tensor<8x8xf64, #CSR>
+
+  // elementwise-min operation to produce the return tensor
+
+  %5 = bufferization.alloc_tensor() : tensor<8x8xf64, #CSR>
+  %6 = linalg.generic #trait_vec_op
+      ins(%2, %4: tensor<8x8xf64, #CSR>, tensor<8x8xf64, #CSR>)
+      outs(%5: <8x8xf64, #CSR>) {
+      ^bb(%a: f64, %b: f64, %x: f64):
+        %1 = sparse_tensor.binary %a, %b : f64, f64 to f64
+          overlap={
+            ^bb0(%a0: f64, %b0: f64):
+              %2 = arith.minsi %a0, %b0: f64
+              sparse_tensor.yield %2 : f64
+          }
+          left=identity
+          right=identity
+        linalg.yield %1 : f64
+  } -> tensor<8x8xf64, #CSR>
+  return %0 : tensor<8x8xf64, #CSR>
+
+  return %2 : tensor<8x8xf64, #CSR>
+}
+
+}

mlir/test/Integration/Dialect/SparseTensor/GPU/CUDA/sparse-sampled-matmul-lib.mlir

+//
+// NOTE: this test requires gpu-sm80
+//
+//
+// RUN: mlir-opt %s \
+// RUN:   --sparse-compiler="enable-runtime-library=true enable-gpu-libgen gpu-triple=nvptx64-nvidia-cuda gpu-chip=sm_80 gpu-features=+ptx71"  \
+// RUN: | mlir-cpu-runner \
+// RUN:   --shared-libs=%mlir_cuda_runtime \
+// RUN:   --shared-libs=%mlir_c_runner_utils \
+// RUN:   --e main --entry-point-result=void \
+// RUN: | FileCheck %s
+//
+
+!Filename = !llvm.ptr<i8>
+
+#SparseMatrix = #sparse_tensor.encoding<{
+  lvlTypes = [ "compressed", "compressed" ],
+  posWidth = 32,
+  crdWidth = 32
+}>
+
+#trait_sampled_dense_dense = {
+  indexing_maps = [
+    affine_map<(i,j,k) -> (i,j)>,  // S
+    affine_map<(i,j,k) -> (i,k)>,  // A
+    affine_map<(i,j,k) -> (k,j)>,  // B
+    affine_map<(i,j,k) -> (i,j)>   // X (out)
+  ],
+  iterator_types = ["parallel", "parallel", "reduction"],
+  doc = "X(i,j) += S(i,j) SUM_k A(i,k) B(k,j)"
+}
+
+//
+// Integration test that lowers a kernel annotated as sparse to
+// actual sparse code, initializes a matching sparse storage scheme
+// from file, and runs the resulting code with the JIT compiler.
+//
+module {
+  //
+  // A kernel that computes a sampled matrix matrix multiplication.
+  //
+  func.func @sampled_dense_dense(%args: tensor<?x?xf32, #SparseMatrix>,
+                                 %arga: tensor<?x?xf32>,
+                                 %argb: tensor<?x?xf32>,
+                                 %argx: tensor<?x?xf32>) -> tensor<?x?xf32> {
+    %0 = linalg.generic #trait_sampled_dense_dense
+      ins(%args, %arga, %argb: tensor<?x?xf32, #SparseMatrix>, tensor<?x?xf32>, tensor<?x?xf32>)
+      outs(%argx: tensor<?x?xf32>) {
+        ^bb(%s: f32, %a: f32, %b: f32, %x: f32):
+          %0 = arith.mulf %a, %b : f32
+          %1 = arith.mulf %s, %0 : f32
+          %2 = arith.addf %x, %1 : f32
+          linalg.yield %2 : f32
+    } -> tensor<?x?xf32>
+    return %0 : tensor<?x?xf32>
+  }
+
+  func.func private @getTensorFilename(index) -> (!Filename)
+
+  //
+  // Main driver that reads matrix from file and calls the sparse kernel.
+  //
+  func.func @entry() {
+    %d0 = arith.constant 0.0 : f32
+    %c0 = arith.constant 0 : index
+    %c1 = arith.constant 1 : index
+    %c5 = arith.constant 5 : index
+    %c10 = arith.constant 10 : index
+
+    // Initialize dense matrices.
+    %x = tensor.generate %c5, %c5 {
+    ^bb0(%i : index, %j : index):
+      tensor.yield %d0 : f32
+    } : tensor<?x?xf32>
+
+    %a = tensor.generate %c5, %c10 {
+    ^bb0(%i: index, %j: index):
+      %p = arith.addi %i, %c1 : index
+      %q = arith.index_cast %p : index to i32
+      %d = arith.sitofp %q : i32 to f32
+      tensor.yield %d : f32
+    } : tensor<?x?xf32>
+
+    %b = tensor.generate %c10, %c5 {
+    ^bb0(%i: index, %j: index):
+      %p = arith.addi %j, %c1 : index
+      %q = arith.index_cast %p : index to i32
+      %d = arith.sitofp %q : i32 to f32
+      tensor.yield %d : f32
+    } : tensor<?x?xf32>
+
+    // Read the sparse matrix from file, construct sparse storage.
+    %fileName = call @getTensorFilename(%c0) : (index) -> (!Filename)
+    %s = sparse_tensor.new %fileName : !Filename to tensor<?x?xf32, #SparseMatrix>
+
+    // Call the kernel.
+    %0 = call @sampled_dense_dense(%s, %a, %b, %x)
+       : (tensor<?x?xf32, #SparseMatrix>,
+          tensor<?x?xf32>, tensor<?x?xf32>, tensor<?x?xf32>) -> tensor<?x?xf32>
+
+    // Print the result for verification.
+    //
+    // CHECK: ( 10, 0, 0, 56, 0 )
+    // CHECK: ( 0, 80, 0, 0, 250 )
+    // CHECK: ( 0, 0, 270, 0, 0 )
+    // CHECK: ( 164, 0, 0, 640, 0 )
+    // CHECK: ( 0, 520, 0, 0, 1250 )
+    //
+    scf.for %i = %c0 to %c5 step %c1 {
+      %v = vector.transfer_read %0[%i, %c0], %d0: tensor<?x?xf32>, vector<5xf32>
+      vector.print %v : vector<5xf32>
+    }
+
+    // Release the resources.
+    bufferization.dealloc_tensor %s : tensor<?x?xf32, #SparseMatrix>
+
+    return
+  }
+}