4 files changed, 104 insertions, 1 deletions

diff --git a/llvm/include/llvm/ADT/SmallPtrSet.h b/llvm/include/llvm/ADT/SmallPtrSet.h
index 16e5ed8933f..438f10b11a2 100644
--- a/llvm/include/llvm/ADT/SmallPtrSet.h
+++ b/llvm/include/llvm/ADT/SmallPtrSet.h
@@ -15,6 +15,7 @@
 #ifndef LLVM_ADT_SMALLPTRSET_H
 #define LLVM_ADT_SMALLPTRSET_H
 
+#include "llvm/Config/abi-breaking.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
 #include <cassert>
@@ -25,6 +26,13 @@
 #include <iterator>
 #include <utility>
 
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+namespace llvm {
+template <class T = void> struct ReverseIterate { static bool value; };
+template <class T> bool ReverseIterate<T>::value = true;
+}
+#endif
+
 namespace llvm {
 
 /// SmallPtrSetImplBase - This is the common code shared among all the
@@ -206,6 +214,12 @@ protected:
 public:
   explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
     : Bucket(BP), End(E) {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIterate<bool>::value) {
+      RetreatIfNotValid();
+      return;
+    }
+#endif
     AdvanceIfNotValid();
   }
 
@@ -227,6 +241,17 @@ protected:
             *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
       ++Bucket;
   }
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+  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.
@@ -252,13 +277,27 @@ public:
   }
 
   inline SmallPtrSetIterator& operator++() {          // Preincrement
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIterate<bool>::value) {
+      RetreatIfNotValid();
+      return *this;
+    }
+#endif
     ++Bucket;
     AdvanceIfNotValid();
     return *this;
   }
 
   SmallPtrSetIterator operator++(int) {        // Postincrement
-    SmallPtrSetIterator tmp = *this; ++*this; return tmp;
+    SmallPtrSetIterator tmp = *this;
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIterate<bool>::value) {
+      --*this;
+      return tmp;
+    }
+#endif
+    ++*this;
+    return tmp;
   }
 };
 
@@ -343,9 +382,22 @@ public:
   }
 
   inline iterator begin() const {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIterate<bool>::value)
+      return endPtr();
+#endif
     return iterator(CurArray, EndPointer());
   }
   inline iterator end() const {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIterate<bool>::value)
+      return iterator(CurArray, CurArray);
+#endif
+    return endPtr();
+  }
+
+private:
+  inline iterator endPtr() const {
     const void *const *End = EndPointer();
     return iterator(End, End);
   }
diff --git a/llvm/lib/Support/CommandLine.cpp b/llvm/lib/Support/CommandLine.cpp
index c9751c093d6..f4d501aceba 100644
--- a/llvm/lib/Support/CommandLine.cpp
+++ b/llvm/lib/Support/CommandLine.cpp
@@ -45,6 +45,17 @@ using namespace cl;
 
 #define DEBUG_TYPE "commandline"
 
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+namespace llvm {
+// If LLVM_ENABLE_ABI_BREAKING_CHECKS is set the flag -mllvm -reverse-iterate
+// can be used to toggle forward/reverse iteration of unordered containers.
+// This will help uncover differences in codegen caused due to undefined
+// iteration order.
+static cl::opt<bool, true> ReverseIteration("reverse-iterate",
+  cl::location(ReverseIterate<bool>::value), cl::init(true));
+}
+#endif
+
 //===----------------------------------------------------------------------===//
 // Template instantiations and anchors.
 //
diff --git a/llvm/unittests/ADT/CMakeLists.txt b/llvm/unittests/ADT/CMakeLists.txt
index 9e10e92de49..738f6efe92d 100644
--- a/llvm/unittests/ADT/CMakeLists.txt
+++ b/llvm/unittests/ADT/CMakeLists.txt
@@ -41,6 +41,7 @@ set(ADTSources
   PostOrderIteratorTest.cpp
   PriorityWorklistTest.cpp
   RangeAdapterTest.cpp
+  ReverseIterationTest.cpp
   SCCIteratorTest.cpp
   STLExtrasTest.cpp
   ScopeExitTest.cpp
diff --git a/llvm/unittests/ADT/ReverseIterationTest.cpp b/llvm/unittests/ADT/ReverseIterationTest.cpp
new file mode 100644
index 00000000000..9235ecd7432
--- /dev/null
+++ b/llvm/unittests/ADT/ReverseIterationTest.cpp
@@ -0,0 +1,39 @@
+//===- llvm/unittest/ADT/ReverseIterationTest.cpp ------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// ReverseIteration unit tests.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "llvm/ADT/SmallPtrSet.h"
+
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+using namespace llvm;
+
+TEST(ReverseIterationTest, SmallPtrSetTest) {
+
+  SmallPtrSet<void*, 4> Set;
+  void *Ptrs[] = { (void*)0x1, (void*)0x2, (void*)0x3, (void*)0x4 };
+  void *ReversePtrs[] = { (void*)0x4, (void*)0x3, (void*)0x2, (void*)0x1 };
+
+  for (auto *Ptr: Ptrs)
+    Set.insert(Ptr);
+
+  // Check forward iteration.
+  ReverseIterate<bool>::value = false;
+  for (const auto &Tuple : zip(Set, Ptrs))
+    ASSERT_EQ(std::get<0>(Tuple), std::get<1>(Tuple));
+
+  // Check reverse iteration.
+  ReverseIterate<bool>::value = true;
+  for (const auto &Tuple : zip(Set, ReversePtrs))
+    ASSERT_EQ(std::get<0>(Tuple), std::get<1>(Tuple));
+}
+#endif