[llvm][SLP] Exit early if inputs to comparator are equal

[davidberard98]

Summary

TL;DR: This PR modifies a comparator. The comparator is used in a subsequent call to llvm::stable_sort. Sorting comparators should follow strict weak ordering - in particular, (x < x) should return false. This PR adds a fix to avoid an infinite loop when the inputs to the comparator are equal.

Details:

Sometimes when two equivalent tensors passed into the comparator, we encounter infinite looping (at https://github.com/llvm/llvm-project/blob/aae2eaae2cefd3132059925c4592276defdb1faa/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp#L4049)

Although it seems like this comparator will never be called with two equivalent pointers, some sanitizers, e.g. https://chromium.googlesource.com/chromiumos/third_party/gcc/+/refs/heads/stabilize-zako-5712.88.B/libstdc++-v3/include/bits/stl_algo.h#360, will add checks for (x < x). When this sanitizer is used with the current implementation, it triggers a comparator check for (x < x) which runs into the infinite loop

[ayermolo]

I don't remember anything about this code. :)
Can you add a test, and I guess this was submitted through web UI, can you do it with -999 so surrounding code can be viewed?

[ABataev]

Add full context

[davidberard98]

added more context - will see if I can get arcanist working to provide more context

testing - I will look further into adding tests

[davidberard98]

update using arcanist

[davidberard98]

@ABataev @ayermolo could you let me know if you still want a test for this, and if so do you have suggestions on where/how to add it?

context on why I'm not sure where to add a test - as far as I can tell, BoUpSLP internals are not exposed outside of SLPVectorizer.cpp. Meanwhile, I don't think I can reproduce the error "organically" - i.e. I don't think we ever encounter the case where V1 == V2 except with this CheckedCompare code path linked above. So, I could refactor some of this code to expose PHICompare somewhere where it can be unit tested, but I figured I'd ask first whether this is a good idea or whether you have other suggestions.

[ABataev]

LG, I think it is ok to commit it as is

[davidberard98]

Thanks! I don't have commit access, so could one of you commit it for me?

[ABataev]

In D155874#4520898, @davidberard98 wrote:

Thanks! I don't have commit access, so could one of you commit it for me?

Will do tommorow

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

BoUpSLP::getReorderingData(const TreeEntry &TE, bool TopToBottom) {
   }
   if (TE.State == TreeEntry::Vectorize &&
       (isa<LoadInst, ExtractElementInst, ExtractValueInst>(TE.getMainOp()) ||
        (TopToBottom && isa<StoreInst, InsertElementInst>(TE.getMainOp()))) &&
       !TE.isAltShuffle())
     return TE.ReorderIndices;
   if (TE.State == TreeEntry::Vectorize && TE.getOpcode() == Instruction::PHI) {
     auto PHICompare = [](llvm::Value *V1, llvm::Value *V2) {
+      if (V1 == V2)
+        return false;
       if (!V1->hasOneUse() || !V2->hasOneUse())
         return false;
       auto *FirstUserOfPhi1 = cast<Instruction>(*V1->user_begin());
       auto *FirstUserOfPhi2 = cast<Instruction>(*V2->user_begin());
       if (auto *IE1 = dyn_cast<InsertElementInst>(FirstUserOfPhi1))
         if (auto *IE2 = dyn_cast<InsertElementInst>(FirstUserOfPhi2)) {
           if (!areTwoInsertFromSameBuildVector(
                   IE1, IE2,