[SLP] Fix crash in reorderBottomToTop().

[vporpo]

Summary

The crash is caused by incorrect order set by reorderBottomToTop(), which
happens when it is reordering a TreeEntry which has a user that has already been
reordered earlier. Please see the detailed description in the lit test.

[vporpo]

Removed single-user assertion for getting the UserTE. Instead we iterate over all user entries and get the one in the Users map.

Also Updated failing AArch64 test.

[vporpo]

Fixed condition (line 4037) which was somehow flipped in the last version of the patch.

[ABataev]

Hi Vasileos, thanks for the reproducer and the patch. Could you try something like this instead:

diff --git a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
index a8de0bffe8d5..d74153c4c636 100644
--- a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
+++ b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
@@ -3858,7 +3858,7 @@ void BoUpSLP::reorderBottomToTop(bool IgnoreReorder) {
   while (!OrderedEntries.empty()) {
     // 1. Filter out only reordered nodes.
     // 2. If the entry has multiple uses - skip it and jump to the next node.
-    MapVector<TreeEntry *, SmallVector<std::pair<unsigned, TreeEntry *>>> Users;
+    DenseMap<TreeEntry *, SmallVector<std::pair<unsigned, TreeEntry *>>> Users;
     SmallVector<TreeEntry *> Filtered;
     for (TreeEntry *TE : OrderedEntries) {
       if (!(TE->State == TreeEntry::Vectorize ||
@@ -3886,7 +3886,13 @@ void BoUpSLP::reorderBottomToTop(bool IgnoreReorder) {
     // Erase filtered entries.
     for_each(Filtered,
              [&OrderedEntries](TreeEntry *TE) { OrderedEntries.remove(TE); });
-    for (auto &Data : Users) {
+    SmallVector<
+        std::pair<TreeEntry *, SmallVector<std::pair<unsigned, TreeEntry *>>>>
+        UsersVec(Users.begin(), Users.end());
+    sort(UsersVec, [](const auto &Data1, const auto &Data2) {
+      return Data1.first->Idx > Data2.first->Idx;
+    });
+    for (auto &Data : UsersVec) {
       // Check that operands are used only in the User node.
       SmallVector<TreeEntry *> GatherOps;
       if (!canReorderOperands(Data.first, Data.second, NonVectorized,

It just simply reorders the users to start the reordering from the bottom elements of the graph rather than from the top.

[vporpo]

Changed visiting order as suggested by @ABataev.

[ABataev]

Are these tests realy affected by the patch? Couldy you check one more time? Also, can you try these patch with dome SPECs?

[vporpo]

It looks strange, let me double check.

[vporpo]

Removed AArch64/loadorder.ll changes.

It turns out that update_test_check won't complain if you update a test using
a build that does not support the target.

[ABataev]

LG

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

void BoUpSLP::reorderBottomToTop(bool IgnoreReorder) {
   // 1. Propagate order to the graph nodes, which use only reordered nodes.
   // I.e., if the node has operands, that are reordered, try to make at least
   // one operand order in the natural order and reorder others + reorder the
   // user node itself.
   SmallPtrSet<const TreeEntry *, 4> Visited;
   while (!OrderedEntries.empty()) {
     // 1. Filter out only reordered nodes.
     // 2. If the entry has multiple uses - skip it and jump to the next node.
-    MapVector<TreeEntry *, SmallVector<std::pair<unsigned, TreeEntry *>>> Users;
+    DenseMap<TreeEntry *, SmallVector<std::pair<unsigned, TreeEntry *>>> Users;
     SmallVector<TreeEntry *> Filtered;
     for (TreeEntry *TE : OrderedEntries) {
       if (!(TE->State == TreeEntry::Vectorize ||
             (TE->State == TreeEntry::NeedToGather &&
              GathersToOrders.count(TE))) ||
           TE->UserTreeIndices.empty() || !TE->ReuseShuffleIndices.empty() ||
           !all_of(drop_begin(TE->UserTreeIndices),
                   [TE](const EdgeInfo &EI) {
for (TreeEntry *TE : OrderedEntries) {
         if (It == Users.end())
           It = Users.insert({UserTE, {}}).first;
         It->second.emplace_back(EI.EdgeIdx, TE);
       }
     }
     // Erase filtered entries.
     for_each(Filtered,
              [&OrderedEntries](TreeEntry *TE) { OrderedEntries.remove(TE); });
-    for (auto &Data : Users) {
+    SmallVector<
+        std::pair<TreeEntry *, SmallVector<std::pair<unsigned, TreeEntry *>>>>
+        UsersVec(Users.begin(), Users.end());
+    sort(UsersVec, [](const auto &Data1, const auto &Data2) {
+      return Data1.first->Idx > Data2.first->Idx;
+    });
+    for (auto &Data : UsersVec) {
       // Check that operands are used only in the User node.
       SmallVector<TreeEntry *> GatherOps;
       if (!canReorderOperands(Data.first, Data.second, NonVectorized,
                               GatherOps)) {
         for_each(Data.second,
                  [&OrderedEntries](const std::pair<unsigned, TreeEntry *> &Op) {
                    OrderedEntries.remove(Op.second);
                  });

llvm/test/Transforms/SLPVectorizer/X86/reorder_with_reordered_users.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -slp-vectorizer -mtriple=x86_64-grtev4-linux-gnu -S | FileCheck %s
+
+; This checks that reorderBottomToTop() can handle reordering of a TreeEntry
+; which has a user TreeEntry that has already been reordered.
+; Here is when the crash occurs:
+;
+;                        (N4)OrderB
+;                         |
+;  (N1)OrderA (N2)OrderA (N3)NoOrder
+;            \      |     /
+;               (Phi)NoOrder
+;
+;  1. Phi is visited along with its operands (N1,N2,N3). BestOrder is "OrderA".
+;  2. Phi along with all its operands (N1,N2,N3) are reordered. The result is:
+;
+;                          (N4)OrderB
+;                           |
+;  (N1)NoOrder (N2)NoOrder (N3)OrderA
+;            \      |     /
+;               (Phi)OrderA
+;
+;  3. N3 is now visited along with its operand N4. BestOrder is "OrderB".
+;  4. N3 and N4 are reordered. The result is this:
+;
+;                          (N4)NoOrder
+;                           |
+;  (N1)NoOrder (N2)NoOrder (N3)OrderB
+;            \      |     /
+;               (Phi)OrderA
+;
+;  At this point there is a discrepancy between Phi's Operand 2 which are
+;  reordered based on OrderA and N3's OrderB. This results in a crash in
+;  vectorizeTree() on its way from N3 back to the Phi. The reason is that
+;  N3->isSame(Phi's operand 2) returns false and vectorizeTree() skips N3.
+;
+;  This patch changes the order in which the nodes are visited to bottom-up,
+;  which fixes the issue.
+;
+; NOTE: The crash shows up when reorderTopToBottom() does not reorder the tree,
+; so to simulate this we add external store users. Alternatively one can
+; comment out reorderTopToBottom() and remove the stores.
+
+
+define void @reorder_crash(float* %ptr) {
+; CHECK-LABEL: @reorder_crash(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[GEP0:%.*]] = getelementptr inbounds float, float* [[PTR:%.*]], i64 0
+; CHECK-NEXT:    br i1 undef, label [[BB0:%.*]], label [[BB12:%.*]]
+; CHECK:       bb0:
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast float* [[GEP0]] to <4 x float>*
+; CHECK-NEXT:    [[TMP1:%.*]] = load <4 x float>, <4 x float>* [[TMP0]], align 4
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast float* [[GEP0]] to <4 x float>*
+; CHECK-NEXT:    store <4 x float> [[TMP1]], <4 x float>* [[TMP2]], align 4
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb12:
+; CHECK-NEXT:    br i1 undef, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast float* [[GEP0]] to <4 x float>*
+; CHECK-NEXT:    [[TMP4:%.*]] = load <4 x float>, <4 x float>* [[TMP3]], align 4
+; CHECK-NEXT:    [[TMP5:%.*]] = bitcast float* [[GEP0]] to <4 x float>*
+; CHECK-NEXT:    store <4 x float> [[TMP4]], <4 x float>* [[TMP5]], align 4
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[TMP6:%.*]] = bitcast float* [[GEP0]] to <4 x float>*
+; CHECK-NEXT:    [[TMP7:%.*]] = load <4 x float>, <4 x float>* [[TMP6]], align 4
+; CHECK-NEXT:    [[TMP8:%.*]] = fadd <4 x float> [[TMP7]], zeroinitializer
+; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <4 x float> [[TMP8]], <4 x float> poison, <4 x i32> <i32 3, i32 2, i32 0, i32 1>
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[TMP9:%.*]] = phi <4 x float> [ [[TMP1]], [[BB0]] ], [ [[TMP4]], [[BB1]] ], [ [[SHUFFLE]], [[BB2]] ]
+; CHECK-NEXT:    ret void
+;
+entry:
+  %gep0 = getelementptr inbounds float, float* %ptr, i64 0
+  %gep1 = getelementptr inbounds float, float* %ptr, i64 1
+  %gep2 = getelementptr inbounds float, float* %ptr, i64 2
+  %gep3 = getelementptr inbounds float, float* %ptr, i64 3
+  br i1 undef, label %bb0, label %bb12
+
+bb0:
+  ; Used by phi in this order: 1, 0, 2, 3
+  %ld00 = load float, float* %gep0
+  %ld01 = load float, float* %gep1
+  %ld02 = load float, float* %gep2
+  %ld03 = load float, float* %gep3
+
+  ; External store users in natural order 0, 1, 2, 3
+  store float %ld00, float *%gep0
+  store float %ld01, float *%gep1
+  store float %ld02, float *%gep2
+  store float %ld03, float *%gep3
+  br label %bb3
+
+bb12:
+  br i1 undef, label %bb1, label %bb2
+
+bb1:
+  ; Used by phi in this order: 1, 0, 2, 3
+  %ld10 = load float, float* %gep0
+  %ld11 = load float, float* %gep1
+  %ld12 = load float, float* %gep2
+  %ld13 = load float, float* %gep3
+
+  ; External store users in natural order 0, 1, 2, 3
+  store float %ld10, float *%gep0
+  store float %ld11, float *%gep1
+  store float %ld12, float *%gep2
+  store float %ld13, float *%gep3
+
+  br label %bb3
+
+bb2:
+  ; Used by fadd in this order: 2, 3, 0, 1
+  %ld20 = load float, float* %gep0
+  %ld21 = load float, float* %gep1
+  %ld22 = load float, float* %gep2
+  %ld23 = load float, float* %gep3
+
+  ; Used by phi in this order: 0, 1, 2, 3
+  %add20 = fadd float %ld22, 0.0
+  %add21 = fadd float %ld23, 0.0
+  %add22 = fadd float %ld20, 0.0
+  %add23 = fadd float %ld21, 0.0
+  br label %bb3
+
+bb3:
+  %phi0 = phi float [ %ld01, %bb0 ], [ %ld11, %bb1 ], [ %add20, %bb2 ]
+  %phi1 = phi float [ %ld00, %bb0 ], [ %ld10, %bb1 ], [ %add21, %bb2 ]
+  %phi2 = phi float [ %ld02, %bb0 ], [ %ld12, %bb1 ], [ %add22, %bb2 ]
+  %phi3 = phi float [ %ld03, %bb0 ], [ %ld13, %bb1 ], [ %add23, %bb2 ]
+  ret void
+}