Iterate SmallPtrSet in reverse order to uncover codegen non-determinism

[mehdi_amini]

Summary

Given a flag (-mllvm -reverse-iterate) this patch will enable iteration of SmallPtrSet in reverse order. The idea is to compile the same source with and without this flag and expect the code to not change.
If there is a difference in codegen then it would mean that the codegen is sensitive to the iteration order of SmallPtrSet.

[mehdi_amini]

You need to add llvm-commits as a subscriber on the creation of the revision, otherwise there is no proper thread on the mailing list with a patch attached.

Can you please recreate the revision?

Thanks!

include/llvm/ADT/SmallPtrSet.h

 #include "llvm/Support/PointerLikeTypeTraits.h"
 #include <cassert>
 #include <cstddef>
 #include <cstring>
 #include <cstdlib>
 #include <iterator>
 #include <utility>
 
+#ifndef NDEBUG
+extern bool ReverseIterate;
+#endif
+
 namespace llvm {
 
 class SmallPtrSetIteratorImpl;
 
 /// SmallPtrSetImplBase - This is the common code shared among all the
 /// SmallPtrSet<>'s, which is almost everything.  SmallPtrSet has two modes, one
 /// for small and one for large sets.
 ///

 class SmallPtrSetIteratorImpl {
 protected:
   const void *const *Bucket;
   const void *const *End;
 
 public:
   explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
     : Bucket(BP), End(E) {
+#ifndef NDEBUG
+    if (ReverseIterate)
+      RetreatIfNotValid();
+    else
+#endif
       AdvanceIfNotValid();
   }
 
   bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
     return Bucket == RHS.Bucket;
   }
   bool operator!=(const SmallPtrSetIteratorImpl &RHS) const {
     return Bucket != RHS.Bucket;
   }
 
 protected:
   /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket
   /// that is.   This is guaranteed to stop because the end() bucket is marked
   /// valid.
   void AdvanceIfNotValid() {
     assert(Bucket <= End);
     while (Bucket != End &&
            (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
             *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
       ++Bucket;
   }
+
+#ifndef NDEBUG
+  void RetreatIfNotValid() {
+    --Bucket;
+    assert(Bucket <= End);
+    while (Bucket != End &&
+           (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
+            *Bucket == SmallPtrSetImplBase::getTombstoneMarker())) {
+      --Bucket;
+    }
+  }
+#endif
 };
 
 /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
 template<typename PtrTy>
 class SmallPtrSetIterator : public SmallPtrSetIteratorImpl {
   typedef PointerLikeTypeTraits<PtrTy> PtrTraits;
 
 public:
public:
   // Most methods provided by baseclass.
 
   const PtrTy operator*() const {
     assert(Bucket < End);
     return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
   }
 
   inline SmallPtrSetIterator& operator++() {          // Preincrement
+#ifndef NDEBUG
+    if (ReverseIterate)
+      RetreatIfNotValid();
+    else {
       ++Bucket;
       AdvanceIfNotValid();
+    }
+#else
+    ++Bucket;
+    AdvanceIfNotValid();
+#endif
     return *this;
   }
 
   SmallPtrSetIterator operator++(int) {        // Postincrement
-    SmallPtrSetIterator tmp = *this; ++*this; return tmp;
+    SmallPtrSetIterator tmp = *this;
+#ifndef NDEBUG
+    if (ReverseIterate)
+      --*this;
+    else
+#endif
+      ++*this;
+    return tmp;
   }
 };
 
 /// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next
 /// power of two (which means N itself if N is already a power of two).
 template<unsigned N>
 struct RoundUpToPowerOfTwo;
 
public:
 
   template <typename IterT>
   void insert(IterT I, IterT E) {
     for (; I != E; ++I)
       insert(*I);
   }
 
   inline iterator begin() const {
+#ifndef NDEBUG
+    if (ReverseIterate)
+      return endPtr();
+#endif
     return iterator(CurArray, EndPointer());
   }
+
   inline iterator end() const {
+#ifndef NDEBUG
+    if (ReverseIterate)
+      return iterator(CurArray, CurArray);
+#endif
+    return endPtr();
+  }
+
+private:
+  inline iterator endPtr() const {
     const void *const *End = EndPointer();
     return iterator(End, End);
   }
 };
 
 /// SmallPtrSet - This class implements a set which is optimized for holding
 /// SmallSize or less elements.  This internally rounds up SmallSize to the next
 /// power of two if it is not already a power of two.  See the comments above

lib/Support/CommandLine.cpp

 #include "llvm/Support/raw_ostream.h"
 #include <cstdlib>
 #include <map>
 using namespace llvm;
 using namespace cl;
 
 #define DEBUG_TYPE "commandline"
 
+#ifndef NDEBUG
+bool ReverseIterate;
+static cl::opt<bool, true> ReverseIteration("reverse-iterate",
+  cl::location(ReverseIterate), cl::init(false));
+#endif
+
+
 //===----------------------------------------------------------------------===//
 // Template instantiations and anchors.
 //
 namespace llvm {
 namespace cl {
 template class basic_parser<bool>;
 template class basic_parser<boolOrDefault>;
 template class basic_parser<int>;