diff --git a/mlir/include/mlir/Dialect/SparseTensor/Utils/Merger.h b/mlir/include/mlir/Dialect/SparseTensor/Utils/Merger.h --- a/mlir/include/mlir/Dialect/SparseTensor/Utils/Merger.h +++ b/mlir/include/mlir/Dialect/SparseTensor/Utils/Merger.h @@ -192,10 +192,11 @@ /// Returns true if any set bit corresponds to queried dim. bool hasAnyDimOf(const llvm::BitVector &bits, Dim d) const; - /// Returns true if given tensor co-iterates with conjunction only in the - /// given tensor expression. For the output tensor, this defines a "simply - /// dynamic" operation [Bik96]. For instance: a(i) *= b(i) * c(i) - bool isConjunction(unsigned t, unsigned e) const; + /// Returns true if given tensor iterates *only* in the given tensor + /// expression. For the output tensor, this defines a "simply dynamic" + /// operation [Bik96]. For instance: a(i) *= 2.0 or a(i) += a(i) for + /// sparse vector a. + bool isSingleCondition(unsigned t, unsigned e) const; /// Dimension setter. void setDim(unsigned t, unsigned i, Dim d) { dims[t][i] = d; } diff --git a/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp b/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp --- a/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp +++ b/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp @@ -321,7 +321,7 @@ // but not its nonzero structure, an operation called "simply dynamic" in // [Bik96,Ch9], is also admissable without special codegen, provided // the tensor's underlying sparse storage scheme can be modified in place. - if (merger.isConjunction(tensor, exp) && isInPlace(lhs->get())) + if (merger.isSingleCondition(tensor, exp) && isInPlace(lhs->get())) return true; // Accept "truly dynamic" if the output tensor materializes uninitialized // into the computation and insertions occur in lexicographic index order. diff --git a/mlir/lib/Dialect/SparseTensor/Utils/Merger.cpp b/mlir/lib/Dialect/SparseTensor/Utils/Merger.cpp --- a/mlir/lib/Dialect/SparseTensor/Utils/Merger.cpp +++ b/mlir/lib/Dialect/SparseTensor/Utils/Merger.cpp @@ -213,7 +213,7 @@ return false; } -bool Merger::isConjunction(unsigned t, unsigned e) const { +bool Merger::isSingleCondition(unsigned t, unsigned e) const { switch (tensorExps[e].kind) { case kTensor: return tensorExps[e].tensor == t; @@ -232,22 +232,30 @@ case kCastU: case kTruncI: case kBitCast: - return isConjunction(t, tensorExps[e].children.e0); + return isSingleCondition(t, tensorExps[e].children.e0); case kDivF: // note: x / c only case kDivS: case kDivU: assert(!maybeZero(tensorExps[e].children.e1)); - return isConjunction(t, tensorExps[e].children.e0); + return isSingleCondition(t, tensorExps[e].children.e0); case kShrS: // note: x >> inv only case kShrU: case kShlI: assert(isInvariant(tensorExps[e].children.e1)); - return isConjunction(t, tensorExps[e].children.e0); + return isSingleCondition(t, tensorExps[e].children.e0); case kMulF: case kMulI: case kAndI: - return isConjunction(t, tensorExps[e].children.e0) || - isConjunction(t, tensorExps[e].children.e1); + if (isSingleCondition(t, tensorExps[e].children.e0)) + return isSingleCondition(t, tensorExps[e].children.e1) || + isInvariant(tensorExps[e].children.e1); + if (isSingleCondition(t, tensorExps[e].children.e1)) + return isInvariant(tensorExps[e].children.e0); + return false; + case kAddF: + case kAddI: + return isSingleCondition(t, tensorExps[e].children.e0) && + isSingleCondition(t, tensorExps[e].children.e1); default: return false; } diff --git a/mlir/test/Dialect/SparseTensor/sparse_out.mlir b/mlir/test/Dialect/SparseTensor/sparse_out.mlir --- a/mlir/test/Dialect/SparseTensor/sparse_out.mlir +++ b/mlir/test/Dialect/SparseTensor/sparse_out.mlir @@ -20,7 +20,7 @@ affine_map<(i,j) -> (i,j)> // X (out) ], iterator_types = ["parallel", "parallel"], - doc = "X(i,j) = X(i,j) * 2" + doc = "X(i,j) *= 2 or X(i,j) += X(i,j)" } // CHECK-LABEL: func @sparse_simply_dynamic1( @@ -57,78 +57,34 @@ return %0 : tensor<32x16xf32, #DCSR> } -#trait_elt_wise_mult = { - indexing_maps = [ - affine_map<(i,j) -> (i,j)>, // A - affine_map<(i,j) -> (i,j)> // X (out) - ], - iterator_types = ["parallel", "parallel"], - doc = "X(i,j) = A(i,j) * X(i,j)" -} - // CHECK-LABEL: func @sparse_simply_dynamic2( -// CHECK-SAME: %[[VAL_0:.*]]: tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>>, -// CHECK-SAME: %[[VAL_1:.*]]: tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> { -// CHECK-DAG: %[[VAL_2:.*]] = arith.constant 0 : index -// CHECK-DAG: %[[VAL_3:.*]] = arith.constant 1 : index -// CHECK: %[[VAL_4:.*]] = sparse_tensor.pointers %[[VAL_0]], %[[VAL_3]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> to memref -// CHECK: %[[VAL_5:.*]] = sparse_tensor.indices %[[VAL_0]], %[[VAL_3]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> to memref -// CHECK: %[[VAL_6:.*]] = sparse_tensor.values %[[VAL_0]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> to memref -// CHECK: %[[VAL_7:.*]] = sparse_tensor.pointers %[[VAL_1]], %[[VAL_2]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> to memref -// CHECK: %[[VAL_8:.*]] = sparse_tensor.indices %[[VAL_1]], %[[VAL_2]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> to memref -// CHECK: %[[VAL_9:.*]] = sparse_tensor.pointers %[[VAL_1]], %[[VAL_3]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> to memref -// CHECK: %[[VAL_10:.*]] = sparse_tensor.indices %[[VAL_1]], %[[VAL_3]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> to memref -// CHECK: %[[VAL_11:.*]] = sparse_tensor.values %[[VAL_1]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> to memref -// CHECK: %[[VAL_12:.*]] = memref.load %[[VAL_7]]{{\[}}%[[VAL_2]]] : memref -// CHECK: %[[VAL_13:.*]] = memref.load %[[VAL_7]]{{\[}}%[[VAL_3]]] : memref -// CHECK: scf.for %[[VAL_14:.*]] = %[[VAL_12]] to %[[VAL_13]] step %[[VAL_3]] { -// CHECK: %[[VAL_15:.*]] = memref.load %[[VAL_8]]{{\[}}%[[VAL_14]]] : memref -// CHECK: %[[VAL_16:.*]] = memref.load %[[VAL_4]]{{\[}}%[[VAL_15]]] : memref -// CHECK: %[[VAL_17:.*]] = arith.addi %[[VAL_15]], %[[VAL_3]] : index -// CHECK: %[[VAL_18:.*]] = memref.load %[[VAL_4]]{{\[}}%[[VAL_17]]] : memref -// CHECK: %[[VAL_19:.*]] = memref.load %[[VAL_9]]{{\[}}%[[VAL_14]]] : memref -// CHECK: %[[VAL_20:.*]] = arith.addi %[[VAL_14]], %[[VAL_3]] : index -// CHECK: %[[VAL_21:.*]] = memref.load %[[VAL_9]]{{\[}}%[[VAL_20]]] : memref -// CHECK: %[[VAL_22:.*]]:2 = scf.while (%[[VAL_23:.*]] = %[[VAL_16]], %[[VAL_24:.*]] = %[[VAL_19]]) : (index, index) -> (index, index) { -// CHECK: %[[VAL_25:.*]] = arith.cmpi ult, %[[VAL_23]], %[[VAL_18]] : index -// CHECK: %[[VAL_26:.*]] = arith.cmpi ult, %[[VAL_24]], %[[VAL_21]] : index -// CHECK: %[[VAL_27:.*]] = arith.andi %[[VAL_25]], %[[VAL_26]] : i1 -// CHECK: scf.condition(%[[VAL_27]]) %[[VAL_23]], %[[VAL_24]] : index, index -// CHECK: } do { -// CHECK: ^bb0(%[[VAL_28:.*]]: index, %[[VAL_29:.*]]: index): -// CHECK: %[[VAL_30:.*]] = memref.load %[[VAL_5]]{{\[}}%[[VAL_28]]] : memref -// CHECK: %[[VAL_31:.*]] = memref.load %[[VAL_10]]{{\[}}%[[VAL_29]]] : memref -// CHECK: %[[VAL_32:.*]] = arith.cmpi ult, %[[VAL_31]], %[[VAL_30]] : index -// CHECK: %[[VAL_33:.*]] = select %[[VAL_32]], %[[VAL_31]], %[[VAL_30]] : index -// CHECK: %[[VAL_34:.*]] = arith.cmpi eq, %[[VAL_30]], %[[VAL_33]] : index -// CHECK: %[[VAL_35:.*]] = arith.cmpi eq, %[[VAL_31]], %[[VAL_33]] : index -// CHECK: %[[VAL_36:.*]] = arith.andi %[[VAL_34]], %[[VAL_35]] : i1 -// CHECK: scf.if %[[VAL_36]] { -// CHECK: %[[VAL_37:.*]] = memref.load %[[VAL_11]]{{\[}}%[[VAL_29]]] : memref -// CHECK: %[[VAL_38:.*]] = memref.load %[[VAL_6]]{{\[}}%[[VAL_28]]] : memref -// CHECK: %[[VAL_39:.*]] = arith.mulf %[[VAL_37]], %[[VAL_38]] : f32 -// CHECK: memref.store %[[VAL_39]], %[[VAL_11]]{{\[}}%[[VAL_29]]] : memref -// CHECK: } else { -// CHECK: } -// CHECK: %[[VAL_40:.*]] = arith.cmpi eq, %[[VAL_30]], %[[VAL_33]] : index -// CHECK: %[[VAL_41:.*]] = arith.addi %[[VAL_28]], %[[VAL_3]] : index -// CHECK: %[[VAL_42:.*]] = select %[[VAL_40]], %[[VAL_41]], %[[VAL_28]] : index -// CHECK: %[[VAL_43:.*]] = arith.cmpi eq, %[[VAL_31]], %[[VAL_33]] : index -// CHECK: %[[VAL_44:.*]] = arith.addi %[[VAL_29]], %[[VAL_3]] : index -// CHECK: %[[VAL_45:.*]] = select %[[VAL_43]], %[[VAL_44]], %[[VAL_29]] : index -// CHECK: scf.yield %[[VAL_42]], %[[VAL_45]] : index, index +// CHECK-SAME: %[[VAL_0:.*]]: tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> +// CHECK-DAG: %[[VAL_1:.*]] = arith.constant 0 : index +// CHECK-DAG: %[[VAL_2:.*]] = arith.constant 1 : index +// CHECK: %[[VAL_3:.*]] = sparse_tensor.pointers %[[VAL_0]], %[[VAL_1]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> +// CHECK: %[[VAL_4:.*]] = sparse_tensor.pointers %[[VAL_0]], %[[VAL_2]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> +// CHECK: %[[VAL_5:.*]] = sparse_tensor.values %[[VAL_0]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> +// CHECK: %[[VAL_6:.*]] = memref.load %[[VAL_3]]{{\[}}%[[VAL_1]]] : memref +// CHECK: %[[VAL_7:.*]] = memref.load %[[VAL_3]]{{\[}}%[[VAL_2]]] : memref +// CHECK: scf.for %[[VAL_8:.*]] = %[[VAL_6]] to %[[VAL_7]] step %[[VAL_2]] { +// CHECK: %[[VAL_9:.*]] = memref.load %[[VAL_4]]{{\[}}%[[VAL_8]]] : memref +// CHECK: %[[VAL_10:.*]] = arith.addi %[[VAL_8]], %[[VAL_2]] : index +// CHECK: %[[VAL_11:.*]] = memref.load %[[VAL_4]]{{\[}}%[[VAL_10]]] : memref +// CHECK: scf.for %[[VAL_12:.*]] = %[[VAL_9]] to %[[VAL_11]] step %[[VAL_2]] { +// CHECK: %[[VAL_13:.*]] = memref.load %[[VAL_5]]{{\[}}%[[VAL_12]]] : memref +// CHECK: %[[VAL_14:.*]] = memref.load %[[VAL_5]]{{\[}}%[[VAL_12]]] : memref +// CHECK: %[[VAL_15:.*]] = arith.addf %[[VAL_13]], %[[VAL_14]] : f32 +// CHECK: memref.store %[[VAL_15]], %[[VAL_5]]{{\[}}%[[VAL_12]]] : memref // CHECK: } // CHECK: } -// CHECK: %[[VAL_46:.*]] = sparse_tensor.load %[[VAL_1]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> -// CHECK: return %[[VAL_46]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> +// CHECK: %[[VAL_16:.*]] = sparse_tensor.load %[[VAL_0]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> +// CHECK: return %[[VAL_16]] : tensor<32x16xf32, #sparse_tensor.encoding<{{.*}}>> // CHECK: } -func @sparse_simply_dynamic2(%arga: tensor<32x16xf32, #CSR>, - %argx: tensor<32x16xf32, #DCSR> {linalg.inplaceable = true}) -> tensor<32x16xf32, #DCSR> { - %0 = linalg.generic #trait_elt_wise_mult - ins(%arga: tensor<32x16xf32, #CSR>) +func @sparse_simply_dynamic2(%argx: tensor<32x16xf32, #DCSR> {linalg.inplaceable = true}) -> tensor<32x16xf32, #DCSR> { + %0 = linalg.generic #trait_scale_inpl outs(%argx: tensor<32x16xf32, #DCSR>) { - ^bb(%a: f32, %x: f32): - %1 = arith.mulf %x, %a : f32 + ^bb(%x: f32): + %1 = arith.addf %x, %x : f32 linalg.yield %1 : f32 } -> tensor<32x16xf32, #DCSR> return %0 : tensor<32x16xf32, #DCSR>