[LoopSink] Don't sort BBs if there is only 1 of them (NFC)

[danlark]

Summary

This was trigerred by the debug check when comp(a, a) was called.
On line 216 it's checked that LoopBlockNumber should contain
all if there are more than 1. NFC for end users

I don't have commit rights. Danila Kutenin. [e-mail]

[nikic]

Which debug check did this trigger? Do you have a test case?

[danlark]

In D157954#4587555, @nikic wrote:

Which debug check did this trigger? Do you have a test case?

If you build llvm with libcxx at head as a standard library with -D_LIBCPP_DEBUG_STRICT_WEAK_ORDERING_CHECK and -D_LIBCPP_ENABLE_DEBUG_MODE, then for this sorting it will invoke comp(a, a) for llvm/test/Transforms/LICM/loopsink.ll.test

This change is extremely safe, on line 216 it's checked that llvm::set_is_subset(BBsToSinkInto, LoopBlockNumber) if BBsToSinkInto.size() > 1. If it's size 1, it implicitly thought no comparator would be called. But it can and LoopBlockNumber.find(A)->second will be a .end() iterator dereference

[nikic]

LGTM. Took me a while to get it, but you're saying that by default sort with one element will not invoke the comparison callback, while in debug mode it will be done to verify the strict weak ordering. That's why we did not previously hit the assertion failure.

I'm not sure whether this is really the right fix (possibly the earlier BBsToSinkInto.size() > 1 check should be removed), but this is fine to fix the assertion failure while keeping the current behavior.

[danlark]

Please, submit on my behalf

llvm/lib/Transforms/Scalar/LoopSink.cpp

if (BBsToSinkInto.size() > 1 &&
       !llvm::set_is_subset(BBsToSinkInto, LoopBlockNumber))
     return false;
 
   // Copy the final BBs into a vector and sort them using the total ordering
   // of the loop block numbers as iterating the set doesn't give a useful
   // order. No need to stable sort as the block numbers are a total ordering.
   SmallVector<BasicBlock *, 2> SortedBBsToSinkInto;
   llvm::append_range(SortedBBsToSinkInto, BBsToSinkInto);
+  if (SortedBBsToSinkInto.size() > 1) {
     llvm::sort(SortedBBsToSinkInto, [&](BasicBlock *A, BasicBlock *B) {
       return LoopBlockNumber.find(A)->second < LoopBlockNumber.find(B)->second;
     });
+  }
 
   BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
   // FIXME: Optimize the efficiency for cloned value replacement. The current
   //        implementation is O(SortedBBsToSinkInto.size() * I.num_uses()).
   for (BasicBlock *N : ArrayRef(SortedBBsToSinkInto).drop_front(1)) {
     assert(LoopBlockNumber.find(N)->second >
                LoopBlockNumber.find(MoveBB)->second &&
            "BBs not sorted!");