Page MenuHomePhabricator

[SLP] Fix crash in reorderBottomToTop().

Authored by vporpo on May 20 2022, 4:04 PM.



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.

Diff Detail

Event Timeline

vporpo created this revision.May 20 2022, 4:04 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 20 2022, 4:04 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
vporpo requested review of this revision.May 20 2022, 4:04 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 20 2022, 4:04 PM
vporpo updated this revision to Diff 431093.May 20 2022, 4:42 PM

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 updated this revision to Diff 431435.May 23 2022, 11:15 AM

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

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.
              [&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 updated this revision to Diff 431695.May 24 2022, 9:35 AM

Changed visiting order as suggested by @ABataev.

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

It looks strange, let me double check.

vporpo updated this revision to Diff 431736.May 24 2022, 11:19 AM

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.

This revision is now accepted and ready to land.May 24 2022, 11:39 AM
This revision was landed with ongoing or failed builds.May 24 2022, 12:25 PM
This revision was automatically updated to reflect the committed changes.