[mlir][sparse] Fix strict weak ordering in sorting

[danlark]

Summary

These checks have been fired when comparing same elements like comp(a, a). Let's fix it. I don't have commit rights.

Danila Kutenin
[e-mail]

[Peiming]

Is there any change to the std::sort that requires such a change? In these two particular cases, there should not be any duplicated item from the array (otherwise, it leads to logical bugs).

[danlark]

In D152152#4397162, @Peiming wrote:

Is there any change to the std::sort that requires such a change? In these two particular cases, there should not be any duplicated item from the array (otherwise, it leads to logical bugs).

std::sort is allowed to call comparator on the same element.

[aartbik]

In D152152#4397277, @danlark wrote:

In D152152#4397162, @Peiming wrote:

Is there any change to the std::sort that requires such a change? In these two particular cases, there should not be any duplicated item from the array (otherwise, it leads to logical bugs).

std::sort is allowed to call comparator on the same element.

But do you have a example that trigger this? The sparse compiler has a non-dup property, and we would like to see the example that leads to this?

[danlark]

In D152152#4397561, @aartbik wrote:

In D152152#4397277, @danlark wrote:

In D152152#4397162, @Peiming wrote:

Is there any change to the std::sort that requires such a change? In these two particular cases, there should not be any duplicated item from the array (otherwise, it leads to logical bugs).

std::sort is allowed to call comparator on the same element.

But do you have a example that trigger this? The sparse compiler has a non-dup property, and we would like to see the example that leads to this?

We added checks in debug mode so it deliberately will https://reviews.llvm.org/D150264

In practice if there are more than 30 elements, it could and can (for example, by being a pivot and waiting for the false condition): https://stackoverflow.com/questions/38966516/should-sorting-algorithm-pass-same-element-in-the-comparison-function

[aartbik]

In practice if there are more than 30 elements, it could and can (for example, by being a pivot and waiting for the false condition): https://stackoverflow.com/questions/38966516/should-sorting-algorithm-pass-same-element-in-the-comparison-function

I understand the general requirement for sort, but this sort is only used in particular situations by the sparse compiler. So my question is, do you have a test case that would trigger the assert at L35.
If so, we would like to understand the example code before removing the assert.

[danlark]

In D152152#4399937, @aartbik wrote:

In practice if there are more than 30 elements, it could and can (for example, by being a pivot and waiting for the false condition): https://stackoverflow.com/questions/38966516/should-sorting-algorithm-pass-same-element-in-the-comparison-function

I understand the general requirement for sort, but this sort is only used in particular situations by the sparse compiler. So my question is, do you have a test case that would trigger the assert at L35.
If so, we would like to understand the example code before removing the assert.

I was not able to reproduce the issue. If we go down to the specifics of std::sort in LLVM, it should take 25 elements to find when comp(a, a) can be called. If we can make here 25 elements anyhow and reorder them as we want, we can fail it

[aartbik]

Any update on this? I am of course willing to accept this if needed, but I would really like to see the test case that exposes the new behavior (should not be too hard to set up, if you have any sequence that exposes this, you can simply construct one sparse vector with indices identical to that sequence).

[danlark]

In D152152#4460962, @aartbik wrote:

Any update on this? I am of course willing to accept this if needed, but I would really like to see the test case that exposes the new behavior (should not be too hard to set up, if you have any sequence that exposes this, you can simply construct one sparse vector with indices identical to that sequence).

I checked and with the new implementation it's impossible to have comp(a, a) in the algorithm itself. My suggestion will be to change the assert to something like

assert(std::addressof(l) == std::addressof(r) || l != r);

[aartbik]

In D152152#4467793, @danlark wrote:

assert(std::addressof(l) == std::addressof(r) || l != r);

That L35 change would be acceptable to me ;-)
What about the L569 change?

[danlark]

In D152152#4474879, @aartbik wrote:

In D152152#4467793, @danlark wrote:

assert(std::addressof(l) == std::addressof(r) || l != r);

That L35 change would be acceptable to me ;-)
What about the L569 change?

Done, sorry for a long response

[wrengr]

It looks like Dialect/SparseTensor/sparse_conv_2d_slice_based.mlir is failing.

[wrengr]

In D152152#4467793, @danlark wrote:

assert(std::addressof(l) == std::addressof(r) || l != r);

Personally, I'd be a lot more comfortable with instead replacing the assertion with if (LLVM_UNLIKELY(l == r)) return false; which is just short-circuiting what the rest of the comparison function would compute anyways (modulo that it doesn't cause assertion error when l/r doesn't occur in order).

Note that LoopId is just unsigned, so there's no funny business going on with the operator== in the for-loop.

[rnk]

Any thoughts on this? As I understand it, this is the last remaining strict weak ordering violation in llvm-project, and after that folks can enable the checks for this in libc++. The other two changes (D155811, D155809) landed.

[danlark]

In D152152#4581304, @rnk wrote:

Any thoughts on this? As I understand it, this is the last remaining strict weak ordering violation in llvm-project, and after that folks can enable the checks for this in libc++. The other two changes (D155811, D155809) landed.

No, there are 3-4 more, I am unable to fix with my knowledge of llvm. One example is https://github.com/llvm/llvm-project/issues/64121

[danlark]

Ping. Looks like Dialect/SparseTensor/sparse_conv_2d_slice_based.mlir was a flake, I cannot reproduce

[Peiming]

In D152152#4587709, @danlark wrote:

Ping. Looks like Dialect/SparseTensor/sparse_conv_2d_slice_based.mlir was a flake, I cannot reproduce

We changed the std::sort to std::stable_sort in LoopEmitter.cpp@574 to fix some ordering issue a while back, it might have been already resolved.

[danlark]

Ping. What is required for me here? I believe the change is very safe to submit

[aartbik]

Sorry this took so long!

[danlark]

Please, submit on my behalf

[aartbik]

Submitting....

[aartbik]

rebased with main

[aartbik]

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

38

hmm, the i++ was replaced with i
(did this pass tests? :-)

Fixing...

[danlark]

Oops but seems to pass :)

[aartbik]

fixed typo on i++

[aartbik]

Submitting...

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

 static bool isMaterializing(Value val) {
   return val.getDefiningOp<tensor::EmptyOp>() ||
          val.getDefiningOp<bufferization::AllocTensorOp>();
 }
 
 /// Makes target array's elements sorted according to the `order` array.
 static void sortArrayBasedOnOrder(std::vector<LoopId> &target,
                                   ArrayRef<LoopId> order) {
-  std::sort(target.begin(), target.end(), [&order](LoopId l, LoopId r) {
-    assert(l != r);
+  std::sort(target.begin(), target.end(),
+            [&order](const LoopId &l, const LoopId &r) {
+              assert(std::addressof(l) == std::addressof(r) || l != r);
               int idxL = -1, idxR = -1;
               for (int i = 0, e = order.size(); i < e; i++) {
                 if (order[i] == l)
                   idxL = i;
                 if (order[i] == r)
                   idxR = i;
               }
               assert(idxL >= 0 && idxR >= 0);
               return idxL < idxR;
             });
 }
-
 //===----------------------------------------------------------------------===//
 // Code generation environment constructor and general methods
 //===----------------------------------------------------------------------===//
 
 CodegenEnv::CodegenEnv(linalg::GenericOp linop, SparsificationOptions opts,
                        unsigned numTensors, unsigned numLoops,
                        unsigned numFilterLoops, unsigned maxRank)
     : linalgOp(linop), sparseOptions(opts),

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

std::sort(elems.begin(), elems.end(),
                 // FIXME: This only makes sense for permutations.
                 // And since we don't check that `order` is a permutation,
                 // it can also cause OOB errors when we use `l`.
                 const Level l = order ? order.getDimPosition(d) : d;
                 if (lhsCoords[l].getInt() == rhsCoords[l].getInt())
                   continue;
                 return lhsCoords[l].getInt() < rhsCoords[l].getInt();
               }
+              if (std::addressof(lhs) == std::addressof(rhs))
+                return false;
               llvm_unreachable("no equal coordinate in sparse element attr");
             });
 
   SmallVector<Value> cvs;
   cvs.reserve(dimRank);
   for (size_t i = 0, nse = values.size(); i < nse; i++) {
     // Remap coordinates.
     cvs.clear();