[SLP] Fix various dependency calculating issues in the scheduler in order to support non-alternative opcodes in the pass.

[dtemirbulatov]

Summary

This is part of the change in https://reviews.llvm.org/D28907
During the implementation of new functionality for PR30787, I encountered several issues with dependency calculation is the scheduling algorithm. Here is the fix for the issues. unfortunately, I could not show here any testcase, since I could reproduce those issues only with new functionality.

[dtemirbulatov]

ping

[dtemirbulatov]

Removed redundant code in calculateDependencies().

[dtemirbulatov]

Abandon this change after talking to Alexey Bataev offline.

lib/Transforms/Vectorize/SLPVectorizer.cpp

struct ScheduleData {
     /// single instruction.
     ScheduleData *NextInBundle = nullptr;
 
     /// Single linked list of all memory instructions (e.g. load, store, call)
     /// in the block - until the end of the scheduling region.
     ScheduleData *NextLoadStore = nullptr;
 
     /// The dependent memory instructions.
-    /// This list is derived on demand in calculateDependencies().
-    SmallVector<ScheduleData *, 4> MemoryDependencies;
+    /// This set is derived on demand in calculateDependencies().
+    SmallSet<ScheduleData *, 4> MemoryDependencies;
 
     /// This ScheduleData is in the current scheduling region if this matches
     /// the current SchedulingRegionID of BlockScheduling.
     int SchedulingRegionID = 0;
 
     /// Used for getting a "good" final ordering of instructions.
     int SchedulingPriority = 0;
 
BlockScheduling(BasicBlock *BB)
         : BB(BB), ChunkSize(BB->size()), ChunkPos(ChunkSize) {}
 
     void clear() {
       ReadyInsts.clear();
       ScheduleStart = nullptr;
       ScheduleEnd = nullptr;
       FirstLoadStoreInRegion = nullptr;
       LastLoadStoreInRegion = nullptr;
+      ExtraScheduleDataMap.clear();
 
       // Reduce the maximum schedule region size by the size of the
       // previous scheduling run.
       ScheduleRegionSizeLimit -= ScheduleRegionSize;
       if (ScheduleRegionSizeLimit < MinScheduleRegionSize)
         ScheduleRegionSizeLimit = MinScheduleRegionSize;
       ScheduleRegionSize = 0;
 
void schedule(ScheduleData *SD, ReadyListType &ReadyList) {
           }
         }
         BundleMember = BundleMember->NextInBundle;
       }
     }
 
     void doForAllOpcodes(Value *V,
                          function_ref<void(ScheduleData *SD)> Action) {
-      if (ScheduleData *SD = getScheduleData(V))
-        Action(SD);
+      bool Found = false;
       auto I = ExtraScheduleDataMap.find(V);
-      if (I != ExtraScheduleDataMap.end())
-        for (auto &P : I->second)
-          if (P.second->SchedulingRegionID == SchedulingRegionID)
-            Action(P.second);
+      if (I != ExtraScheduleDataMap.end()) {
+        for (auto &P : I->second) {
+          ScheduleData *SD = P.second;
+          if (SD && !SD->isPartOfBundle())
+            continue;
+          if (SD && SD->SchedulingRegionID == SchedulingRegionID) {
+            Found = true;
+            Action(SD);
+          }
+        }
+      }
+      if (ScheduleData *SD = getScheduleData(V)) {
+        if (!Found || SD->isPartOfBundle())
+          Action(SD);
+      }
     }
 
     /// Put all instructions into the ReadyList which are ready for scheduling.
     template <typename ReadyListType>
     void initialFillReadyList(ReadyListType &ReadyList) {
       for (auto *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
         doForAllOpcodes(I, [&](ScheduleData *SD) {
           if (SD->isSchedulingEntity() && SD->isReady()) {
while (!Bundle->isReady() && !ReadyInsts.empty()) {
     ReadyInsts.pop_back();
 
     if (pickedSD->isSchedulingEntity() && pickedSD->isReady()) {
       schedule(pickedSD, ReadyInsts);
     }
   }
   if (!Bundle->isReady()) {
     cancelScheduling(VL, S.OpValue);
+    // We have to clear all dependencies, since all values
+    // were calculated for the vectorized bundle.
+    for (auto *I = ScheduleStart; I != ScheduleEnd;
+      I = I->getNextNode()) {
+      doForAllOpcodes(I, [](ScheduleData *SD) {
+        SD->clearDependencies();
+      });
+    }
+    resetSchedule();
     return false;
   }
   return true;
 }
 
 void BoUpSLP::BlockScheduling::cancelScheduling(ArrayRef<Value *> VL,
                                                 Value *OpValue) {
   if (isa<PHINode>(OpValue))
while (BundleMember) {
 
         LLVM_DEBUG(dbgs() << "SLP:       update deps of " << *BundleMember
                           << "\n");
         BundleMember->Dependencies = 0;
         BundleMember->resetUnscheduledDeps();
 
         // Handle def-use chain dependencies.
         if (BundleMember->OpValue != BundleMember->Inst) {
-          ScheduleData *UseSD = getScheduleData(BundleMember->Inst);
-          if (UseSD && isInSchedulingRegion(UseSD->FirstInBundle)) {
+          for (User *U : BundleMember->Inst->users()) {
+            if (isa<Instruction>(U)) {
+              doForAllOpcodes(U, [&BundleMember, &WorkList](ScheduleData *UseSD) {
                 BundleMember->Dependencies++;
                 ScheduleData *DestBundle = UseSD->FirstInBundle;
                 if (!DestBundle->IsScheduled)
                   BundleMember->incrementUnscheduledDeps(1);
                 if (!DestBundle->hasValidDependencies())
                   WorkList.push_back(DestBundle);
+              });
+            } else {
+              // I'm not sure if this can ever happen. But we need to be safe.
+              // This lets the instruction/bundle never be scheduled and
+              // eventually disable vectorization.
+              BundleMember->Dependencies++;
+              BundleMember->incrementUnscheduledDeps(1);
+            }
           }
         } else {
           for (User *U : BundleMember->Inst->users()) {
             if (isa<Instruction>(U)) {
-              ScheduleData *UseSD = getScheduleData(U);
-              if (UseSD && isInSchedulingRegion(UseSD->FirstInBundle)) {
+              doForAllOpcodes(U, [&BundleMember, &WorkList](ScheduleData *UseSD) {
                 BundleMember->Dependencies++;
                 ScheduleData *DestBundle = UseSD->FirstInBundle;
                 if (!DestBundle->IsScheduled)
                   BundleMember->incrementUnscheduledDeps(1);
                 if (!DestBundle->hasValidDependencies())
                   WorkList.push_back(DestBundle);
-              }
+              });
             } else {
               // I'm not sure if this can ever happen. But we need to be safe.
               // This lets the instruction/bundle never be scheduled and
               // eventually disable vectorization.
               BundleMember->Dependencies++;
               BundleMember->incrementUnscheduledDeps(1);
             }
           }
while (BundleMember) {
                      (numAliased >= AliasedCheckLimit ||
                       SLP->isAliased(SrcLoc, SrcInst, DepDest->Inst)))) {
 
               // We increment the counter only if the locations are aliased
               // (instead of counting all alias checks). This gives a better
               // balance between reduced runtime and accurate dependencies.
               numAliased++;
 
-              DepDest->MemoryDependencies.push_back(BundleMember);
+              // We don't want any duplicates in the set to have a correct
+              // dependancies.
+              if (DepDest->MemoryDependencies.count(BundleMember) == 0) {
+                DepDest->MemoryDependencies.insert(BundleMember);
                 BundleMember->Dependencies++;
                 ScheduleData *DestBundle = DepDest->FirstInBundle;
                 if (!DestBundle->IsScheduled) {
                   BundleMember->incrementUnscheduledDeps(1);
                 }
                 if (!DestBundle->hasValidDependencies()) {
                   WorkList.push_back(DestBundle);
                 }
               }
+            }
             DepDest = DepDest->NextLoadStore;
 
             // Example, explaining the loop break condition: Let's assume our
             // starting instruction is i0 and MaxMemDepDistance = 3.
             //
             //                      +--------v--v--v
             //             i0,i1,i2,i3,i4,i5,i6,i7,i8
             //             +--------^--^--^