[SLP] Fixed non-determenistic behavior in Loop Vectorizer.

[aaboud]

Summary

We should not iterate on Set container.
Added a SmallVector "CheckDepsList", which is used to keep the order when iterating over "CheckDeps" Set.

[mkuper]

Is there a reason not to make MemAccessInfoSet a SmallSetVector instead?

[aaboud]

In D30638#693511, @mkuper wrote:

Is there a reason not to make MemAccessInfoSet a SmallSetVector instead?

You are right, I needed to change "erase" to "remove" in order to work with SetVector, which I missed in my first try.
Notice that we will still need to iterate on the ordered set with a "while(!empty())" because we are removing entries from the Set while iterating on it.

[mkuper]

In D30638#694112, @aaboud wrote:

Notice that we will still need to iterate on the ordered set with a "while(!empty())" because we are removing entries from the Set while iterating on it.

Oy. That's not good. Removal from SetVector (except with pop_back) is linear-time... :-\

I'm not a fan of the original patch either, though - both because it keeps the same data twice, in two different members. The best idea I can think off of the top of my head, is having the member be an ordered container, then making a copy into a regular set in areDepsSafe(), and then iterating over the ordered container, but working with the set, like your patch does.
But that's also pretty ugly. Better ideas are welcome.

[aaboud]

One more try.

[mkuper]

include/llvm/Analysis/LoopAccessAnalysis.h

97 ↗

(On Diff #90907)

I don't think there's a reason to keep the Set typedef here if the only use is for a local variable.

lib/Analysis/LoopAccessAnalysis.cpp

825 ↗

(On Diff #90907)

We never have duplicates here anyway, right? So it doesn't matter if it's a set or a list.

1611 ↗

(On Diff #90907)

Is this necessary?
I mean, it used to happen as a side-effect of the way the loop was structured, but is CheckDeps every actually used after this?

[aaboud]

Thanks, Michael for the comments.
Unfortunately, I do not have answers for all!

include/llvm/Analysis/LoopAccessAnalysis.h

97 ↗

(On Diff #90907)

Agree, will fix.

lib/Analysis/LoopAccessAnalysis.cpp

825 ↗

(On Diff #90907)

I do not know this code Michael, but even if we end up having duplication, we are going to process them once due to the "Visited" set.

1611 ↗

(On Diff #90907)

Again, I am not familiar with the code, from my check, this is why I preferred to keep same behavior as before.

I do not mind removing this line.

[mkuper]

LGTM, modulo the minor issues inline.

lib/Analysis/LoopAccessAnalysis.cpp

825 ↗

(On Diff #90907)

Yes, but if there's a lot of duplication, then the loop now has many more iterations. I think this is fine, though, since a pointer can't be in more than one AliasSet.

1611 ↗

(On Diff #90907)

I don't know this code well enough either to positively say whether it's safe to remove. That's why I'm asking you to check. :-)

[aaboud]

Updated patch as agreed.
I doubled check and it seems that it is safe not to clear the CheckDeps at areDepsSafe, if need to be reused the code clear it, otherwise it will be deleted when deleting the LoopAccessInfo instance.

[mkuper]

LGTM.

llvm/trunk/include/llvm/Analysis/LoopAccessAnalysis.h

 ///
 ///     Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
 ///
 ///  * Zero distances and all accesses have the same size.
 ///
 class MemoryDepChecker {
 public:
   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
-  typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;
+  typedef SmallVector<MemAccessInfo, 8> MemAccessInfoList;
   /// \brief Set of potential dependent memory accesses.
   typedef EquivalenceClasses<MemAccessInfo> DepCandidates;
 
   /// \brief Dependece between memory access instructions.
   struct Dependence {
     /// \brief The type of the dependence.
     enum DepType {
       // No dependence.
void addAccess(LoadInst *LI) {
     Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
     InstMap.push_back(LI);
     ++AccessIdx;
   }
 
   /// \brief Check whether the dependencies between the accesses are safe.
   ///
   /// Only checks sets with elements in \p CheckDeps.
-  bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoSet &CheckDeps,
+  bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps,
                    const ValueToValueMap &Strides);
 
   /// \brief No memory dependence was encountered that would inhibit
   /// vectorization.
   bool isSafeForVectorization() const { return SafeForVectorization; }
 
   /// \brief The maximum number of bytes of a vector register we can vectorize
   /// the accesses safely with.

llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

 /// \brief Analyses memory accesses in a loop.
 ///
 /// Checks whether run time pointer checks are needed and builds sets for data
 /// dependence checking.
 class AccessAnalysis {
 public:
   /// \brief Read or write access location.
   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
-  typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;
+  typedef SmallVector<MemAccessInfo, 8> MemAccessInfoList;
 
   AccessAnalysis(const DataLayout &Dl, AliasAnalysis *AA, LoopInfo *LI,
                  MemoryDepChecker::DepCandidates &DA,
                  PredicatedScalarEvolution &PSE)
       : DL(Dl), AST(*AA), LI(LI), DepCands(DA), IsRTCheckAnalysisNeeded(false),
         PSE(PSE) {}
 
   /// \brief Register a load  and whether it is only read from.
public:
   bool isDependencyCheckNeeded() { return !CheckDeps.empty(); }
 
   /// We decided that no dependence analysis would be used.  Reset the state.
   void resetDepChecks(MemoryDepChecker &DepChecker) {
     CheckDeps.clear();
     DepChecker.clearDependences();
   }
 
-  MemAccessInfoSet &getDependenciesToCheck() { return CheckDeps; }
+  MemAccessInfoList &getDependenciesToCheck() { return CheckDeps; }
 
 private:
   typedef SetVector<MemAccessInfo> PtrAccessSet;
 
   /// \brief Go over all memory access and check whether runtime pointer checks
   /// are needed and build sets of dependency check candidates.
   void processMemAccesses();
 
   /// Set of all accesses.
   PtrAccessSet Accesses;
 
   const DataLayout &DL;
 
-  /// Set of accesses that need a further dependence check.
-  MemAccessInfoSet CheckDeps;
+  /// List of accesses that need a further dependence check.
+  MemAccessInfoList CheckDeps;
 
   /// Set of pointers that are read only.
   SmallPtrSet<Value*, 16> ReadOnlyPtr;
 
   /// An alias set tracker to partition the access set by underlying object and
   //intrinsic property (such as TBAA metadata).
   AliasSetTracker AST;
 
for (int SetIteration = 0; SetIteration < 2; ++SetIteration) {
             continue;
           }
 
           // If this is a write - check other reads and writes for conflicts. If
           // this is a read only check other writes for conflicts (but only if
           // there is no other write to the ptr - this is an optimization to
           // catch "a[i] = a[i] + " without having to do a dependence check).
           if ((IsWrite || IsReadOnlyPtr) && SetHasWrite) {
-            CheckDeps.insert(Access);
+            CheckDeps.push_back(Access);
             IsRTCheckAnalysisNeeded = true;
           }
 
           if (IsWrite)
             SetHasWrite = true;
 
           // Create sets of pointers connected by a shared alias set and
           // underlying object.
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue()
                << " with max VF = "
                << MaxSafeDepDistBytes / (TypeByteSize * Stride) << '\n');
 
   return Dependence::BackwardVectorizable;
 }
 
 bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
-                                   MemAccessInfoSet &CheckDeps,
+                                   MemAccessInfoList &CheckDeps,
                                    const ValueToValueMap &Strides) {
 
   MaxSafeDepDistBytes = -1;
-  while (!CheckDeps.empty()) {
-    MemAccessInfo CurAccess = *CheckDeps.begin();
+  SmallPtrSet<MemAccessInfo, 8> Visited;
+  for (MemAccessInfo CurAccess : CheckDeps) {
+    if (Visited.count(CurAccess))
+      continue;
 
     // Get the relevant memory access set.
     EquivalenceClasses<MemAccessInfo>::iterator I =
       AccessSets.findValue(AccessSets.getLeaderValue(CurAccess));
 
     // Check accesses within this set.
     EquivalenceClasses<MemAccessInfo>::member_iterator AI =
         AccessSets.member_begin(I);
     EquivalenceClasses<MemAccessInfo>::member_iterator AE =
         AccessSets.member_end();
 
     // Check every access pair.
     while (AI != AE) {
-      CheckDeps.erase(*AI);
+      Visited.insert(*AI);
       EquivalenceClasses<MemAccessInfo>::member_iterator OI = std::next(AI);
       while (OI != AE) {
         // Check every accessing instruction pair in program order.
         for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(),
              I1E = Accesses[*AI].end(); I1 != I1E; ++I1)
           for (std::vector<unsigned>::iterator I2 = Accesses[*OI].begin(),
                I2E = Accesses[*OI].end(); I2 != I2E; ++I2) {
             auto A = std::make_pair(&*AI, *I1);