[mlir] Construct SmallVector with ArrayRef (NFC) (#101896)

[mlir][sparse] refactor utilities into transform/utils dir (#75250)

Separates actual transformation files from supporting utility files in
the transforms directory. Includes a bazel overlay fix for

[mlir][sparse] refactor utilities into transform/utils dir (#75250)

Separates actual transformation files from supporting utility files in
the transforms directory. Includes a bazel overlay fix for the build (as
well as a bit of cleanup of that file to be less verbose and more
flexible).

show more ...

[mlir][SparseTensor] Fix insertion point in `createQuickSort` (#74549)

`createQuickSort` used to generate invalid IR:
```
"func.func"() <{function_type = (index, index, memref<?xindex>, memref<?xf

[mlir][SparseTensor] Fix insertion point in `createQuickSort` (#74549)

`createQuickSort` used to generate invalid IR:
```
"func.func"() <{function_type = (index, index, memref<?xindex>, memref<?xf32>, memref<?xi32>) -> (), sym_name = "_sparse_qsort_0_1_index_coo_1_f32_i32", sym_visibility = "private"}> ({
^bb0(%arg0: index, %arg1: index, %arg2: memref<?xindex>, %arg3: memref<?xf32>, %arg4: memref<?xi32>):
%0:2 = "scf.while"(%arg0, %arg1) ({
^bb0(%arg5: index, %arg6: index):
// ...
"scf.condition"(%3, %arg5, %arg6) : (i1, index, index) -> ()
}, {
^bb0(%arg5: index, %arg6: index):
// ...
%7:2 = "scf.if"(%6) ({
%8 = "arith.cmpi"(%2, %3) <{predicate = 7 : i64}> : (index, index) -> i1
// ...
"scf.yield"(%9#0, %9#1) : (index, index) -> ()
%10 = "arith.constant"() <{value = 0 : index}> : () -> index
}, {
"scf.yield"(%arg5, %arg5) : (index, index) -> ()
}) : (i1) -> (index, index)
"scf.yield"(%7#0, %7#1) : (index, index) -> ()
}) : (index, index) -> (index, index)
"func.return"() : () -> ()
}) : () -> ()
within split at mlir/test/Dialect/SparseTensor/buffer_rewriting.mlir:76 offset :11:1: error: 'scf.yield' op must be the last operation in the parent block
```

This commit fixes tests such as
`mlir/test/Dialect/SparseTensor/buffer_rewriting.mlir` when verifying
the IR after each pattern application (#74270).

show more ...

[mlir][affine][nfc] cleanup deprecated T.cast style functions (#71269)

detail see the docment: https://mlir.llvm.org/deprecation/

Not all changes are made manually, most of them are made through

[mlir][affine][nfc] cleanup deprecated T.cast style functions (#71269)

detail see the docment: https://mlir.llvm.org/deprecation/

Not all changes are made manually, most of them are made through a clang
tool I wrote https://github.com/lipracer/cpp-refactor.

show more ...

[mlir][sparse] renaming sparse_tensor.sort_coo to sparse_tensor.sort (#68161)

Rationale: the operation does not always sort COO tensors (also used for
sparse_tensor.compress for example).

[mlir][sparse] unifies sparse_tensor.sort_coo/sort into one operation. (#66722)

The use cases of the two operations are largely overlapped, let's
simplify it and only use one of them.

[mlir][sparse] fix logical error when generating sort_coo. (#66690)

To fix issue: https://github.com/llvm/llvm-project/issues/66664

[mlir][sparse] Modify the pivot selection method for quick sort.

Previously, we choose the median of three values. We now choose the median of
five values when the number of values being sorted exce

[mlir][sparse] Modify the pivot selection method for quick sort.

Previously, we choose the median of three values. We now choose the median of
five values when the number of values being sorted exceed a threshold
(currently 100). This is similar to std::sort.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D145534

show more ...

[mlir][sparse] Improve sort operation by generating inlined code to compare values.

Previously, we generate function calls to compare values for sorting. It turns
out that the compiler doesn't inlin

[mlir][sparse] Improve sort operation by generating inlined code to compare values.

Previously, we generate function calls to compare values for sorting. It turns
out that the compiler doesn't inline those function calls. We now directly
generate inlined code. Also, modify the code for comparing values to use less
number of branches.

This improves all sort implementation in general. For arabic-2005.mtx CSR, the
improvement is around 25%.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D145442

show more ...

[mlir][sparse] Improve quick sort by using a loop to sort the bigger partition.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D145440

[mlir][sparse] Add checking parent op of SortOp

Fix crash with segmentation fault caused by setting a parent operator
that is not func::FuncOp with sparse_tensor SortOp.

fixes https://github.com/ll

[mlir][sparse] Add checking parent op of SortOp

Fix crash with segmentation fault caused by setting a parent operator
that is not func::FuncOp with sparse_tensor SortOp.

fixes https://github.com/llvm/llvm-project/issues/59988

Reviewed By: aartbik, wrengr

Differential Revision: https://reviews.llvm.org/D143874

show more ...

[mlir][sparse] Implement hybrid quick sort for sparse_tensor.sort.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D143227

[mlir][sparse] Implement heap sort for sparse_tensor.sort.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D142913

[mlir][sparse] Extend sorting function generator to support operand beyond (lo, hi, xs, ys).

This is to prepare for implementing a hybrid quick sort, which switches to heap
sort when the recursive d

[mlir][sparse] Extend sorting function generator to support operand beyond (lo, hi, xs, ys).

This is to prepare for implementing a hybrid quick sort, which switches to heap
sort when the recursive depth exceeds certain limits.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D142731

show more ...

[mlir][sparse] Extend sparse_tensor.sort with a enum attribute to specify a sorting implementation.

Currently, all the non-stable sorting algorithms are implemented via the
straightforward quick sor

[mlir][sparse] Extend sparse_tensor.sort with a enum attribute to specify a sorting implementation.

Currently, all the non-stable sorting algorithms are implemented via the
straightforward quick sort. This will be fixed in the following PR.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D142678

show more ...

[mlir][sparse] Change the quick sort pivot selection.

Previously, we choose the value at (lo + hi)/2 as a pivot for partitioning the
data in [lo, hi). We now choose the median for the three values a

[mlir][sparse] Change the quick sort pivot selection.

Previously, we choose the value at (lo + hi)/2 as a pivot for partitioning the
data in [lo, hi). We now choose the median for the three values at lo, (lo +
hi)/2, and (hi-1) as a pivot to match the std::qsort implementation.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D142679

show more ...

[mlir][sparse] (re)introducing getRankedTensorType/getMemrefType

The bulk of D142074 seems to have gotten overwritten due to some sort of merge conflict (afaict there's no record of it having been r

[mlir][sparse] (re)introducing getRankedTensorType/getMemrefType

The bulk of D142074 seems to have gotten overwritten due to some sort of merge conflict (afaict there's no record of it having been reverted intentionally). So this commit redoes those changes. In addition to the original changes, this commit also:
* moves the definition of `getRankedTensorType` (from `Transforms/CodegenUtils.h` to `IR/SparseTensor.h`), so that it can be used by `IR/SparseTensorDialect.cpp`.
* adds `getMemRefType` as another abbreviation.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D142503

show more ...

[mlir][sparse] use sparse_tensor::StorageSpecifier to store dim/memSizes

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D140130

[mlir][sparse] Fix problems in creating complex zero for initialization.

Reviewed By: aartbik, wrengr

Differential Revision: https://reviews.llvm.org/D139591

Merge kDynamicSize and kDynamicSentinel into one constant.

resolve conflicts

Differential Revision: https://reviews.llvm.org/D138282

[mlir][sparse] avoid single small vector, set exact number 3

Reviewed By: wrengr

Differential Revision: https://reviews.llvm.org/D138071

[mlir][sparse] cleanup small vector constant hints

Following advise from

https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h

This revision removes the size hints from SmallVector (

[mlir][sparse] cleanup small vector constant hints

Following advise from

https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h

This revision removes the size hints from SmallVector (unless we are
certain of the resulting number of elements). Also, this replaces
SmallVector references with SmallVectorImpl references.

Reviewed By: Peiming

Differential Revision: https://reviews.llvm.org/D138063

show more ...

[mlir][sparse] Add rewriting rules for sparse_tensor.sort_coo.

Refactor the rewriting of sparse_tensor.sort to support the implementation of
sparse_tensor.sort_coo.

Reviewed By: aartbik

Differenti

[mlir][sparse] Add rewriting rules for sparse_tensor.sort_coo.

Refactor the rewriting of sparse_tensor.sort to support the implementation of
sparse_tensor.sort_coo.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D137522

show more ...

[mlir][sparse] Add option enable-buffer-initialization to initialize the memory buffers for sparse tensors to support debugging.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org

[mlir][sparse] Add option enable-buffer-initialization to initialize the memory buffers for sparse tensors to support debugging.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D137592

show more ...

[mlir][sparse] Improve the non-stable sort implementation.

Replace the quick sort partition method with one that is more similar to the
method used by C++ std quick sort. This improves the runtime f

[mlir][sparse] Improve the non-stable sort implementation.

Replace the quick sort partition method with one that is more similar to the
method used by C++ std quick sort. This improves the runtime for sorting
sk_2005.mtx by more than 10x.

Reviewed By: aartbik

Differential Revision: https://reviews.llvm.org/D137290

show more ...