[ADT] Enable reverse iteration for DenseMap

[dblaikie]

This gets a bit trickier than the SmallPtrSet example already implemented - for pointers we know/expect they're unstable & so changing the iteration order is important.

For non-pointer keys in DenseMaps - do we want LLVM to be resilient to changes in hash algorithm or bucket size, etc? If so, that leads some credence to, for example: http://lists.llvm.org/pipermail/llvm-dev/2017-July/114983.html which I punted on.

I'm not sure it's important that LLVM be deterministic in the face of changes to its internal data structures like that, but if others disagree - I'm totally open to doing that work. I've no idea how far/close we are to conforming to that.

If it turns out that's not a good idea/a preferred goal, then this reverse iteration stuff could still be done - but would be conditionalized also on whether the key in the map is a pointer (or pointer-like - I think we have a trait for that) type & only reverse iteration in that case.

[mehdi_amini]

I had a similar issue when I tried to change the StringMap hash function in LLVM and it broke a bunch of test because LLVM's behavior changes depending on the order of iteration there (this is deterministic but the hash function is part of the inputs to consider for determinism basically...)

[davidxl]

The compilation output depends on 1) input source and 2) the compiler that produces it. When compiler changes, the output may change (though still semantically equivalent unless there is UB in the source). Changing the internal data structures such as hash functions basically changes the compiler, so the output is expected to have possible change. It is unrealistic to expect compiler behavior 'completely' fixed from version to version.

[mgrang]

Thanks all for your valuable comments. I guess I would limit this patch to work only for pointer-like keys.

[mehdi_amini]

@davidxl: while not a bug, it is still annoying from an internal design point of view to tie our behavior to the hash function used in StringMap. Conceptually they are not supposed to be ordered!

[davidxl]

The order is implementation defined which is deterministic -- and I am not sure about the annoyance part of it :) On the other hand, requiring everything related to output to have a fixed/well-defined order which is implementation independent can have its own cost in terms of compile time or memory usage.

[mgrang]

DenseMap will now reverse iterate only for pointer-like keys. The flag ReverseIterate<bool> is now not exposed to clients - they would now call shouldReverseIterate() to check whether to reverse iterate or not.

[dblaikie]

include/llvm/Support/ReverseIteration.h

23

Should this use an LLVM trait, to catch more interesting things that are pointer-like but not is_pointer? (I guess unique/shared ptr, and maybe PointerIntPair, PointerUnion, etc? Not sure if there's already an LLVM trait that covers all of those)

unittests/ADT/ReverseIterationTest.cpp

23–24

This, I assume, depends on the particular hash/iteration order of the container? Might be better to, like in the non-pointer test below, gather the order from the container & demonstrate it's the reverse, not that it's any particular order more specifically than that.

(also, I'm not quite sure on the rules for aliasing, etc, of creating pointers to arbitrary values like that - maybe declare 4 ints and have an array of int pointers to those ints?)

Also you can walk an array in reverse with llvm::reverse(TheArray)

30

Having this as a mutable global variable seems surprising to me - though maybe it is the right answer here for testing & the like, I'm not sure.

I'd be OK if it was a constant and this test tested the constant (yeah, that'd mean there would be no coverage for reverse iteration in a build that hadn't enabled reverse iteration, but that might be OK (I think of reverse iteration-clean like being valgrind/sanitizer clean - yeah, we might check in tests that are near-meaningless when run without sanitizers, but they test that this scenario is sanitizer clean when the sanitizers are enabled)) to decide which order to expect results in. Also maybe some comments explaining that this is testing implementation details, clients shouldn't depend on iteration order, and that these tests are here to ensure that the intentional unreliability of the iteration order is functioning.

92

Probably put '++i, begin++' as the loop increment (so you can have both i and begin in the loop header rather than splitting them (or could use 'i++, begin++' to make them look more consistent - not sure which is better here, since the goal is to do the 'interesting' thing with begin)

Also, calling it 'begin' might be confusing, since it starts at begin, but then moves - maybe 'mi' (for 'map iterator', but not sure)

[mgrang]

Addressed comments for the unit test.

[mgrang]

include/llvm/Support/ReverseIteration.h

23

Yes, ideally this should use an LLVM trait. I tried adding a "bool IsPointerLikeType" field to each template specialization in PointerLikeTypeTraits.h. As a result I had to add this field to each definition/specialization of this template throughout llvm/clang/polly as its definitions are scattered throughout.

More pressingly, the compilation failed since it will now call PointerLikeTypeTrait<T>::IsPointerLikeType for a T which does not have a complete trait definition (like LLVMBasicBlockRef).

I also tried adding a similar field to each specialization in DenseMapInfo. But that would make it too specific as I would then need to do something like "DenseMapInfo<T>::IsPointerLikeType". This would make it difficult to generalize this for other containers.

Could you please suggest some ways I can work around these?

unittests/ADT/ReverseIterationTest.cpp

30

Ideally, I want to make ReverseIteration a class and the "value" field a private member and introduce setter/getter functions. I am currently running through compilation failures with this. Will push a subsequent patch once I get a clean build.

[mgrang]

Further cleaned up the code by moving the ReverseIteration code out of CommandLine.cpp and into its own class.
Added set/get functions instead of directly modifying the variable.

[rsmith]

include/llvm/Support/ReverseIteration.h

23

Is there a reason that we define the primary PointerLikeTypeTraits template? SFINAE on whether PointerLikeTypeTraits<T> is a complete type seems like it would be a convenient way to detect if it's been specialized (if it worked).

[mgrang]

Addressed comments.

[dblaikie]

include/llvm/ADT/DenseMap.h

73

Should this have the "is empty" special case? Could the is empty case be moved above this #if ?

if (empty())
  return end();
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
...
#endif
return makeIterator(getBuckets(), getBucketsEnd(), *this);

Similarly for the other ops below

1129–1133

Might be able to factor out the NoAdvance into an early return:

  if (NoAdvance) return;
#if BREAKING_CHECKS
  if (reverse) {
    retreat();
    return;
  }
#endif
  advance()

include/llvm/Support/PointerLikeTypeTraits.h

33–49

Was it not possible to use something more like what I'd suggested - that would've worked (I think) with PointerLikeTypeTraits? Or did that not seem to work out?

Sounded like Richard had an idea of how to do it even more simply than my suggestion, maybe... (if we removed the base definition of PointerLikeTypeTraits & were able to test on the completeness of the class, rather than checking for the specific member as I'd done)

include/llvm/Support/ReverseIteration.h

17–30

This is still a mutable dynamic property - is that necessary/good? Or could it be a constant (indeed having a standalone function template "shouldReverseIterate<T>" that has the value baked in by the macro in the header - no need for an out of line definition, etc)

19

default

lib/Support/ReverseIteration.cpp

8–12 ↗

(On Diff #106675)

I still wonder if it'd be better if this was not mutable - a compile time constant, this would also potentially remove the need for all the preprocessor work. It could rely on the reverse iteration being a constant (not a command line arg, or mutable internally) and rely on the compiler doing dead code elimination to remove the unnecessary code instead of #if.

This would limit the ability to test the feature - really the feature would only be tested on buildbots/configurations that had reverse iteration enabled, or not, etc. But I think that's probably OK?

[mgrang]

Addressed comments.

[mgrang]

Was it not possible to use something more like what I'd suggested - that would've worked (I think) with PointerLikeTypeTraits? Or did that not seem to work out?

Sounded like Richard had an idea of how to do it even more simply than my suggestion, maybe... (if we removed the base definition of PointerLikeTypeTraits & were able to test on the completeness of the class, rather than checking for the specific member as I'd done)

@dblaikie I tried both ways. Checking is_pointer on a PointerLikeTypeTrait I again ran into compile errors due to incomplete types (similar to the ones I had mentioned earlier).
I tried removing the base defintion of PointerLikeTypeTraits but ran into more compile errors (because now there is no sink for a T which is not specialized?). Like:

error: cannot initialize return object of type 'llvm::cl::OptionCategory *const' with an rvalue of type 'llvm::cl::OptionCategory **'
      return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1]));

Also about using SFINAE to check type completeness, this thread states that it's possible but would be broken (what if the type is completed after the point you query it?):
https://stackoverflow.com/questions/21119281/using-sfinae-to-check-if-the-type-is-complete-or-not

[mgrang]

I still wonder if it'd be better if this was not mutable - a compile time constant, this would also potentially remove the need for all the preprocessor work. It could rely on the reverse iteration being a constant (not a command line arg, or mutable internally) and rely on the compiler doing dead code elimination to remove the unnecessary code instead of #if.

Removing the #if, would mean having unittest/ADT/ReverseIteration.cpp enabled even for release builds?
Also I don't know why but when I tried removing the #if, there were a lot of unit test crashes/failures. Need to look more closely.

Do the #if really harm us (other than looking ugly?). If we remove them, then from just reading the code it won't be obvious that we are relying on the compiler to optimize away variables/functions?

[mgrang]

include/llvm/Support/ReverseIteration.h

10

@dblaikie Is this implementation similar to what you had in mind when you said shouldReverseIterate should be a compile time constant w/o the need for an out-of-line definition?

[dblaikie]

include/llvm/Support/ReverseIteration.h

10

Yep, looks about right to me - though it shouldn't be static (shouldn't have internal linkage (non-class scoped static/anonymous namespace) things in headers)

[mgrang]

Addressed comments.

[mgrang]

include/llvm/Support/PointerLikeTypeTraits.h

35

Just checking if T is a complete type is not enough due to the presence of specialization for const T:
template <typename T> class PointerLikeTypeTraits<const T>

In this case, for a const int the type is complete but it's not a pointer type. So to handle such cases I had to check for is_pointer too.

[mgrang]

include/llvm/Support/PointerLikeTypeTraits.h

35

We might as well not check for is_complete and just check for is_pointer, and then add more specialization for is_pointer of other ptr types (like shared, unique ptr, etc)?

[mgrang]

We removed -reverse-iterate flag and the base definition for PointerLikeTypeTraits here, we need https://reviews.llvm.org/D36386
which removes clang unit test which used -reverse-iterate and marks member functions of PointerLikeTypeTraits
as public to get past a compilation error.

[mgrang]

Addressed comments.
Checked if type is pointer-like without adding a new trait. Instead used PointerLikeTypeTraits::NumLowBitsAvailable.

[dblaikie]

include/llvm/Support/PointerLikeTypeTraits.h

19

Probably a layering violation to include this here. Also seems like a narrow solution - would require more special casing here for other types that are like these two whenever they might get used in a map eventually, etc.

Any chance of implementing is_pointer_like as "is a pointer, or (SFINAE'd) is pointer like"?

(I'd probably name the trait "IsPointerLike" to match the kind of naming of PointerLikeTypeTraits - though I realize this might be a bit confusing if it's true for things that don't have PointerLikeTypeTraits, like these two special cases you mentioned (LLVMOpaqueBasicBlock & LLVMOpaqueValue) )

unittests/ADT/ReverseIterationTest.cpp

72–73

Seems like this code shouldn't be here (it's known/expected that "shouldReverseIterate<int>()" is always false, right? - so maybe an ASSERT_FALSE for that?)

[mgrang]

Addressed comments in the unit test.
Moved unittests/ADT/ReverseIteration.cpp to unittests/Support/ReverseIteration.cpp.

[mgrang]

Probably a layering violation to include this here. Also seems like a narrow solution - would require more special casing here for other types that are like these two whenever they might get used in a map eventually, etc.

Yes, this is true. But I cannot think of a way of overcoming this.

Any chance of implementing is_pointer_like as "is a pointer, or (SFINAE'd) is pointer like"?

I have already implemented IsPointerLike as a SFINAE.

(I'd probably name the trait "IsPointerLike" to match the kind of naming of PointerLikeTypeTraits - though I realize this might be a bit confusing if it's true for things that don't have PointerLikeTypeTraits, like these two special cases you mentioned (LLVMOpaqueBasicBlock & LLVMOpaqueValue) )

Done.

[mgrang]

Adopted @dblaikie 's changes for pointer-like traits.

[mgrang]

#Included PointerLikeTypeTraits.h in ReverseIteration.h.

[mgrang]

Minor styling fixes - changed <typename>* to <typename> *.

[mgrang]

@dblaikie Could you please take a look at this? If you have no objections then can we merge this?

include/llvm/ADT/DenseMap.h

 #ifndef LLVM_ADT_DENSEMAP_H
 #define LLVM_ADT_DENSEMAP_H
 
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/EpochTracker.h"
 #include "llvm/Support/AlignOf.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/ReverseIteration.h"
 #include "llvm/Support/type_traits.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstring>
 #include <iterator>
 #include <new>
 #include <type_traits>
public:
   using mapped_type = ValueT;
   using value_type = BucketT;
 
   using iterator = DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT>;
   using const_iterator =
       DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>;
 
   inline iterator begin() {
-    // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets().
-    return empty() ? end() : iterator(getBuckets(), getBucketsEnd(), *this);
+    // When the map is empty, avoid the overhead of advancing/retreating past
+    // empty buckets.
+    if (empty())
+      return end();
+    if (shouldReverseIterate<KeyT>())
+      return makeIterator(getBucketsEnd() - 1, getBuckets(), *this);
+    return makeIterator(getBuckets(), getBucketsEnd(), *this);
   }
   inline iterator end() {
-    return iterator(getBucketsEnd(), getBucketsEnd(), *this, true);
+    return makeIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
   }
   inline const_iterator begin() const {
-    return empty() ? end()
-                   : const_iterator(getBuckets(), getBucketsEnd(), *this);
+    if (empty())
+      return end();
+    if (shouldReverseIterate<KeyT>())
+      return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *this);
+    return makeConstIterator(getBuckets(), getBucketsEnd(), *this);
   }
   inline const_iterator end() const {
-    return const_iterator(getBucketsEnd(), getBucketsEnd(), *this, true);
+    return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
   }
 
   LLVM_NODISCARD bool empty() const {
     return getNumEntries() == 0;
   }
   unsigned size() const { return getNumEntries(); }
 
   /// Grow the densemap so that it can contain at least \p NumEntries items
public:
   size_type count(const_arg_type_t<KeyT> Val) const {
     const BucketT *TheBucket;
     return LookupBucketFor(Val, TheBucket) ? 1 : 0;
   }
 
   iterator find(const_arg_type_t<KeyT> Val) {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return iterator(TheBucket, getBucketsEnd(), *this, true);
+      return makeIterator(TheBucket, getBucketsEnd(), *this, true);
     return end();
   }
   const_iterator find(const_arg_type_t<KeyT> Val) const {
     const BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return const_iterator(TheBucket, getBucketsEnd(), *this, true);
+      return makeConstIterator(TheBucket, getBucketsEnd(), *this, true);
     return end();
   }
 
   /// Alternate version of find() which allows a different, and possibly
   /// less expensive, key type.
   /// The DenseMapInfo is responsible for supplying methods
   /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
   /// type used.
   template<class LookupKeyT>
   iterator find_as(const LookupKeyT &Val) {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return iterator(TheBucket, getBucketsEnd(), *this, true);
+      return makeIterator(TheBucket, getBucketsEnd(), *this, true);
     return end();
   }
   template<class LookupKeyT>
   const_iterator find_as(const LookupKeyT &Val) const {
     const BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return const_iterator(TheBucket, getBucketsEnd(), *this, true);
+      return makeConstIterator(TheBucket, getBucketsEnd(), *this, true);
     return end();
   }
 
   /// lookup - Return the entry for the specified key, or a default
   /// constructed value if no such entry exists.
   ValueT lookup(const_arg_type_t<KeyT> Val) const {
     const BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
public:
 
   // Inserts key,value pair into the map if the key isn't already in the map.
   // The value is constructed in-place if the key is not in the map, otherwise
   // it is not moved.
   template <typename... Ts>
   std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) {
     BucketT *TheBucket;
     if (LookupBucketFor(Key, TheBucket))
-      return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
-                            false); // Already in map.
+      return std::make_pair(
+               makeIterator(TheBucket, getBucketsEnd(), *this, true),
 
     // Otherwise, insert the new element.
     TheBucket =
         InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);
-    return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
-                          true);
+    return std::make_pair(
+             makeIterator(TheBucket, getBucketsEnd(), *this, true),
   }
 
   // Inserts key,value pair into the map if the key isn't already in the map.
   // The value is constructed in-place if the key is not in the map, otherwise
   // it is not moved.
   template <typename... Ts>
   std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&... Args) {
     BucketT *TheBucket;
     if (LookupBucketFor(Key, TheBucket))
-      return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
-                            false); // Already in map.
+      return std::make_pair(
+               makeIterator(TheBucket, getBucketsEnd(), *this, true),
 
     // Otherwise, insert the new element.
     TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
-    return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
-                          true);
+    return std::make_pair(
+             makeIterator(TheBucket, getBucketsEnd(), *this, true),
   }
 
   /// Alternate version of insert() which allows a different, and possibly
   /// less expensive, key type.
   /// The DenseMapInfo is responsible for supplying methods
   /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
   /// type used.
   template <typename LookupKeyT>
   std::pair<iterator, bool> insert_as(std::pair<KeyT, ValueT> &&KV,
                                       const LookupKeyT &Val) {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
-                            false); // Already in map.
+      return std::make_pair(
+               makeIterator(TheBucket, getBucketsEnd(), *this, true),
 
     // Otherwise, insert the new element.
     TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),
                                            std::move(KV.second), Val);
-    return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
-                          true);
+    return std::make_pair(
+             makeIterator(TheBucket, getBucketsEnd(), *this, true),
   }
 
   /// insert - Range insertion of pairs.
   template<typename InputIt>
   void insert(InputIt I, InputIt E) {
     for (; I != E; ++I)
       insert(*I);
   }
static const KeyT getEmptyKey() {
     return KeyInfoT::getEmptyKey();
   }
 
   static const KeyT getTombstoneKey() {
     return KeyInfoT::getTombstoneKey();
   }
 
 private:
+  iterator makeIterator(BucketT *P, BucketT *E,
+                        DebugEpochBase &Epoch,
+                        bool NoAdvance=false) {
+    if (shouldReverseIterate<KeyT>()) {
+      BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
+      return iterator(B, E, Epoch, NoAdvance);
+    }
+    return iterator(P, E, Epoch, NoAdvance);
+  }
+
+  const_iterator makeConstIterator(const BucketT *P, const BucketT *E,
+                                   const DebugEpochBase &Epoch,
+                                   const bool NoAdvance=false) const {
+    if (shouldReverseIterate<KeyT>()) {
+      const BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
+      return const_iterator(B, E, Epoch, NoAdvance);
+    }
+    return const_iterator(P, E, Epoch, NoAdvance);
+  }
+
   unsigned getNumEntries() const {
     return static_cast<const DerivedT *>(this)->getNumEntries();
   }
 
   void setNumEntries(unsigned Num) {
     static_cast<DerivedT *>(this)->setNumEntries(Num);
   }
 

 
 public:
   DenseMapIterator() = default;
 
   DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch,
                    bool NoAdvance = false)
       : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) {
     assert(isHandleInSync() && "invalid construction!");
-    if (!NoAdvance) AdvancePastEmptyBuckets();
+
+    if (NoAdvance) return;
+    if (shouldReverseIterate<KeyT>()) {
+      RetreatPastEmptyBuckets();
+      return;
+    }
+    AdvancePastEmptyBuckets();
   }
 
   // Converting ctor from non-const iterators to const iterators. SFINAE'd out
   // for const iterator destinations so it doesn't end up as a user defined copy
   // constructor.
   template <bool IsConstSrc,
             typename = typename std::enable_if<!IsConstSrc && IsConst>::type>
   DenseMapIterator(
       const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I)
       : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {}
 
   reference operator*() const {
     assert(isHandleInSync() && "invalid iterator access!");
+    if (shouldReverseIterate<KeyT>())
+      return Ptr[-1];
     return *Ptr;
   }
   pointer operator->() const {
     assert(isHandleInSync() && "invalid iterator access!");
+    if (shouldReverseIterate<KeyT>())
+      return &(Ptr[-1]);
     return Ptr;
   }
 
   bool operator==(const ConstIterator &RHS) const {
     assert((!Ptr || isHandleInSync()) && "handle not in sync!");
     assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!");
     assert(getEpochAddress() == RHS.getEpochAddress() &&
            "comparing incomparable iterators!");
     return Ptr == RHS.Ptr;
   }
   bool operator!=(const ConstIterator &RHS) const {
     assert((!Ptr || isHandleInSync()) && "handle not in sync!");
     assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!");
     assert(getEpochAddress() == RHS.getEpochAddress() &&
            "comparing incomparable iterators!");
     return Ptr != RHS.Ptr;
   }
 
   inline DenseMapIterator& operator++() {  // Preincrement
     assert(isHandleInSync() && "invalid iterator access!");
+    if (shouldReverseIterate<KeyT>()) {
+      --Ptr;
+      RetreatPastEmptyBuckets();
+      return *this;
+    }
     ++Ptr;
     AdvancePastEmptyBuckets();
     return *this;
   }
   DenseMapIterator operator++(int) {  // Postincrement
     assert(isHandleInSync() && "invalid iterator access!");
     DenseMapIterator tmp = *this; ++*this; return tmp;
   }
 
 private:
   void AdvancePastEmptyBuckets() {
+    assert(Ptr <= End);
     const KeyT Empty = KeyInfoT::getEmptyKey();
     const KeyT Tombstone = KeyInfoT::getTombstoneKey();
 
     while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) ||
                           KeyInfoT::isEqual(Ptr->getFirst(), Tombstone)))
       ++Ptr;
   }
+
+  void RetreatPastEmptyBuckets() {
+    assert(Ptr >= End);
+    const KeyT Empty = KeyInfoT::getEmptyKey();
+    const KeyT Tombstone = KeyInfoT::getTombstoneKey();
+
+    while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) ||
+                          KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone)))
+      --Ptr;
+  }
 };
 
 template<typename KeyT, typename ValueT, typename KeyInfoT>
 static inline size_t
 capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) {
   return X.getMemorySize();
 }
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_DENSEMAP_H

include/llvm/ADT/SmallPtrSet.h

 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) {
-#if LLVM_ENABLE_ABI_BREAKING_CHECKS
-    if (ReverseIterate<bool>::value) {
+    if (shouldReverseIterate()) {
       RetreatIfNotValid();
       return;
     }
-#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;
   }
-#if LLVM_ENABLE_ABI_BREAKING_CHECKS
   void RetreatIfNotValid() {
     assert(Bucket >= End);
     while (Bucket != End &&
            (Bucket[-1] == SmallPtrSetImplBase::getEmptyMarker() ||
             Bucket[-1] == SmallPtrSetImplBase::getTombstoneMarker())) {
       --Bucket;
     }
   }
-#endif
 };
 
 /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
 template<typename PtrTy>
 class SmallPtrSetIterator : public SmallPtrSetIteratorImpl {
   using PtrTraits = PointerLikeTypeTraits<PtrTy>;
 
 public:
   using value_type = PtrTy;
   using reference = PtrTy;
   using pointer = PtrTy;
   using difference_type = std::ptrdiff_t;
   using iterator_category = std::forward_iterator_tag;
 
   explicit SmallPtrSetIterator(const void *const *BP, const void *const *E)
     : SmallPtrSetIteratorImpl(BP, E) {}
 
   // Most methods provided by baseclass.
 
   const PtrTy operator*() const {
-#if LLVM_ENABLE_ABI_BREAKING_CHECKS
-    if (ReverseIterate<bool>::value) {
+    if (shouldReverseIterate()) {
       assert(Bucket > End);
       return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1]));
     }
-#endif
     assert(Bucket < End);
     return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
   }
 
   inline SmallPtrSetIterator& operator++() {          // Preincrement
-#if LLVM_ENABLE_ABI_BREAKING_CHECKS
-    if (ReverseIterate<bool>::value) {
+    if (shouldReverseIterate()) {
       --Bucket;
       RetreatIfNotValid();
       return *this;
     }
-#endif
     ++Bucket;
     AdvanceIfNotValid();
     return *this;
   }
 
   SmallPtrSetIterator operator++(int) {        // Postincrement
     SmallPtrSetIterator tmp = *this;
     ++*this;
for (; I != E; ++I)
       insert(*I);
   }
 
   void insert(std::initializer_list<PtrType> IL) {
     insert(IL.begin(), IL.end());
   }
 
   iterator begin() const {
-#if LLVM_ENABLE_ABI_BREAKING_CHECKS
-    if (ReverseIterate<bool>::value)
+    if (shouldReverseIterate())
       return makeIterator(EndPointer() - 1);
-#endif
     return makeIterator(CurArray);
   }
   iterator end() const { return makeIterator(EndPointer()); }
 
 private:
   /// Create an iterator that dereferences to same place as the given pointer.
   iterator makeIterator(const void *const *P) const {
-#if LLVM_ENABLE_ABI_BREAKING_CHECKS
-    if (ReverseIterate<bool>::value)
+    if (shouldReverseIterate())
       return iterator(P == EndPointer() ? CurArray : P + 1, CurArray);
-#endif
     return iterator(P, EndPointer());
   }
 };
 
 /// 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
 /// SmallPtrSetImplBase for details of the algorithm.

include/llvm/Support/PointerLikeTypeTraits.h

 // structures to reason about pointers and other things that are pointer sized.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_POINTERLIKETYPETRAITS_H
 #define LLVM_SUPPORT_POINTERLIKETYPETRAITS_H
 
 #include "llvm/Support/DataTypes.h"
 #include <type_traits>
 
 namespace llvm {
 
 /// A traits type that is used to handle pointer types and things that are just
 /// wrappers for pointers as a uniform entity.
-template <typename T> class PointerLikeTypeTraits {
-  // getAsVoidPointer
-  // getFromVoidPointer
-  // getNumLowBitsAvailable
-};
+template <typename T> class PointerLikeTypeTraits;
 
 namespace detail {
 /// A tiny meta function to compute the log2 of a compile time constant.
 template <size_t N>
 struct ConstantLog2
     : std::integral_constant<size_t, ConstantLog2<N / 2>::value + 1> {};
 template <> struct ConstantLog2<1> : std::integral_constant<size_t, 0> {};
+
+// Trait to check if T is a complete type.
+template<class T, class V = void>
+struct is_complete { static const bool value = false; };
+
+template<class T>
+struct is_complete<T, decltype(sizeof(T), void())> {
+  static const bool value = true;
+};
 }
 
 // Provide PointerLikeTypeTraits for non-cvr pointers.
 template <typename T> class PointerLikeTypeTraits<T *> {
 public:
   static inline void *getAsVoidPointer(T *P) { return P; }
   static inline T *getFromVoidPointer(void *P) { return static_cast<T *>(P); }
 
   enum { NumLowBitsAvailable = detail::ConstantLog2<alignof(T)>::value };
 };
 
 template <> class PointerLikeTypeTraits<void *> {
 public:
   static inline void *getAsVoidPointer(void *P) { return P; }
   static inline void *getFromVoidPointer(void *P) { return P; }
 

include/llvm/Support/ReverseIteration.h

 #ifndef LLVM_SUPPORT_REVERSEITERATION_H
 #define LLVM_SUPPORT_REVERSEITERATION_H
 
 #include "llvm/Config/abi-breaking.h"
 
 namespace llvm {
-#if LLVM_ENABLE_ABI_BREAKING_CHECKS
-template <class T = void> struct ReverseIterate { static bool value; };
+
+template<class T = void*>
+bool shouldReverseIterate() {
 #if LLVM_ENABLE_REVERSE_ITERATION
-template <class T> bool ReverseIterate<T>::value = true;
+  return detail::is_complete<T>::value;
 #else
-template <class T> bool ReverseIterate<T>::value = false;
-#endif
+  return false;
 #endif
 }
 
+}
 #endif

lib/Support/CommandLine.cpp

 #include "llvm/Support/raw_ostream.h"
 #include <cstdlib>
 #include <map>
 using namespace llvm;
 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));
-}
-#endif
-
 //===----------------------------------------------------------------------===//
 // Template instantiations and anchors.
 //
 namespace llvm {
 namespace cl {
 template class basic_parser<bool>;
 template class basic_parser<boolOrDefault>;
 template class basic_parser<int>;

test/Transforms/Util/PredicateInfo/condprop2.ll

-; REQUIRES: abi-breaking-checks
-; NOTE: The flag -reverse-iterate is present only in a +Asserts build.
-; Hence, this test has been split from condprop.ll to test with -reverse-iterate.
-; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -print-predicateinfo -analyze -reverse-iterate  < %s 2>&1 | FileCheck %s
-
-@a = external global i32    ; <i32*> [#uses=7]
-
-define i32 @test1() nounwind {
-; CHECK-LABEL: @test1(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* @a, align 4
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 4
-; CHECK-NEXT:    br i1 [[TMP1]], label [[BB:%.*]], label [[BB1:%.*]]
-; CHECK:       bb:
-; CHECK-NEXT:    br label [[BB8:%.*]]
-; CHECK:       bb1:
-; CHECK-NEXT:    [[TMP2:%.*]] = load i32, i32* @a, align 4
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 5
-; CHECK-NEXT:    br i1 [[TMP3]], label [[BB2:%.*]], label [[BB3:%.*]]
-; CHECK:       bb2:
-; CHECK-NEXT:    br label [[BB8]]
-; CHECK:       bb3:
-; CHECK-NEXT:    [[TMP4:%.*]] = load i32, i32* @a, align 4
-; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[TMP4]], 4
-; CHECK-NEXT:    br i1 [[TMP5]], label [[BB4:%.*]], label [[BB5:%.*]]
-; CHECK:       bb4:
-; CHECK-NEXT:    [[TMP6:%.*]] = load i32, i32* @a, align 4
-; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[TMP6]], 5
-; CHECK-NEXT:    br label [[BB8]]
-; CHECK:       bb5:
-; CHECK-NEXT:    [[TMP8:%.*]] = load i32, i32* @a, align 4
-; CHECK-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], 5
-; CHECK-NEXT:    br i1 [[TMP9]], label [[BB6:%.*]], label [[BB7:%.*]]
-; CHECK:       bb6:
-; CHECK-NEXT:    [[TMP10:%.*]] = load i32, i32* @a, align 4
-; CHECK-NEXT:    [[TMP11:%.*]] = add i32 [[TMP10]], 4
-; CHECK-NEXT:    br label [[BB8]]
-; CHECK:       bb7:
-; CHECK-NEXT:    [[TMP12:%.*]] = load i32, i32* @a, align 4
-; CHECK-NEXT:    br label [[BB8]]
-; CHECK:       bb8:
-; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ [[TMP12]], [[BB7]] ], [ [[TMP11]], [[BB6]] ], [ [[TMP7]], [[BB4]] ], [ 4, [[BB2]] ], [ 5, [[BB]] ]
-; CHECK-NEXT:    br label [[RETURN:%.*]]
-; CHECK:       return:
-; CHECK-NEXT:    ret i32 [[DOT0]]
-;
-entry:
-  %0 = load i32, i32* @a, align 4
-  %1 = icmp eq i32 %0, 4
-  br i1 %1, label %bb, label %bb1
-
-bb:   ; preds = %entry
-  br label %bb8
-
-bb1:    ; preds = %entry
-  %2 = load i32, i32* @a, align 4
-  %3 = icmp eq i32 %2, 5
-  br i1 %3, label %bb2, label %bb3
-
-bb2:    ; preds = %bb1
-  br label %bb8
-
-bb3:    ; preds = %bb1
-  %4 = load i32, i32* @a, align 4
-  %5 = icmp eq i32 %4, 4
-  br i1 %5, label %bb4, label %bb5
-
-bb4:    ; preds = %bb3
-  %6 = load i32, i32* @a, align 4
-  %7 = add i32 %6, 5
-  br label %bb8
-
-bb5:    ; preds = %bb3
-  %8 = load i32, i32* @a, align 4
-  %9 = icmp eq i32 %8, 5
-  br i1 %9, label %bb6, label %bb7
-
-bb6:    ; preds = %bb5
-  %10 = load i32, i32* @a, align 4
-  %11 = add i32 %10, 4
-  br label %bb8
-
-bb7:    ; preds = %bb5
-  %12 = load i32, i32* @a, align 4
-  br label %bb8
-
-bb8:    ; preds = %bb7, %bb6, %bb4, %bb2, %bb
-  %.0 = phi i32 [ %12, %bb7 ], [ %11, %bb6 ], [ %7, %bb4 ], [ 4, %bb2 ], [ 5, %bb ]
-  br label %return
-
-return:   ; preds = %bb8
-  ret i32 %.0
-}
-
-declare void @foo(i1)
-declare void @bar(i32)
-
-define void @test3(i32 %x, i32 %y) {
-; CHECK-LABEL: @test3(
-; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
-; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XZ]], [[YZ]]
-; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
-; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
-; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
-; CHECK:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[Z]])
-; CHECK-NEXT:    br i1 [[Z]], label [[BOTH_ZERO:%.*]], label [[NOPE:%.*]]
-; CHECK:       both_zero:
-; CHECK-NEXT:    call void @foo(i1 [[XZ_0]])
-; CHECK-NEXT:    call void @foo(i1 [[YZ_0]])
-; CHECK-NEXT:    call void @bar(i32 [[X_0]])
-; CHECK-NEXT:    call void @bar(i32 [[Y_0]])
-; CHECK-NEXT:    ret void
-; CHECK:       nope:
-; CHECK-NEXT:    call void @foo(i1 [[Z_0]])
-; CHECK-NEXT:    ret void
-;
-  %xz = icmp eq i32 %x, 0
-  %yz = icmp eq i32 %y, 0
-  %z = and i1 %xz, %yz
-  br i1 %z, label %both_zero, label %nope
-both_zero:
-  call void @foo(i1 %xz)
-  call void @foo(i1 %yz)
-  call void @bar(i32 %x)
-  call void @bar(i32 %y)
-  ret void
-nope:
-  call void @foo(i1 %z)
-  ret void
-}
-
-define void @test4(i1 %b, i32 %x) {
-; CHECK-LABEL: @test4(
-; CHECK-NEXT:    br i1 [[B:%.*]], label [[SW:%.*]], label [[CASE3:%.*]]
-; CHECK:       sw:
-; CHECK:         i32 0, label [[CASE0:%.*]]
-; CHECK-NEXT:    i32 1, label [[CASE1:%.*]]
-; CHECK-NEXT:    i32 2, label [[CASE0]]
-; CHECK-NEXT:    i32 3, label [[CASE3]]
-; CHECK-NEXT:    i32 4, label [[DEFAULT:%.*]]
-; CHECK-NEXT:    ] Edge: [label [[SW]],label %case1] }
-; CHECK-NEXT:    [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X:%.*]])
-; CHECK-NEXT:    switch i32 [[X]], label [[DEFAULT]] [
-; CHECK-NEXT:    i32 0, label [[CASE0]]
-; CHECK-NEXT:    i32 1, label [[CASE1]]
-; CHECK-NEXT:    i32 2, label [[CASE0]]
-; CHECK-NEXT:    i32 3, label [[CASE3]]
-; CHECK-NEXT:    i32 4, label [[DEFAULT]]
-; CHECK-NEXT:    ]
-; CHECK:       default:
-; CHECK-NEXT:    call void @bar(i32 [[X]])
-; CHECK-NEXT:    ret void
-; CHECK:       case0:
-; CHECK-NEXT:    call void @bar(i32 [[X]])
-; CHECK-NEXT:    ret void
-; CHECK:       case1:
-; CHECK-NEXT:    call void @bar(i32 [[X_0]])
-; CHECK-NEXT:    ret void
-; CHECK:       case3:
-; CHECK-NEXT:    call void @bar(i32 [[X]])
-; CHECK-NEXT:    ret void
-;
-  br i1 %b, label %sw, label %case3
-sw:
-  switch i32 %x, label %default [
-  i32 0, label %case0
-  i32 1, label %case1
-  i32 2, label %case0
-  i32 3, label %case3
-  i32 4, label %default
-  ]
-default:
-  call void @bar(i32 %x)
-  ret void
-case0:
-  call void @bar(i32 %x)
-  ret void
-case1:
-  call void @bar(i32 %x)
-  ret void
-case3:
-  call void @bar(i32 %x)
-  ret void
-}
-
-define i1 @test5(i32 %x, i32 %y) {
-; CHECK-LABEL: @test5(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
-; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
-; CHECK:         [[Y_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
-; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
-; CHECK:       same:
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[X_0]], [[Y_0]]
-; CHECK-NEXT:    ret i1 [[CMP2]]
-; CHECK:       different:
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp eq i32 [[X_1]], [[Y_1]]
-; CHECK-NEXT:    ret i1 [[CMP3]]
-;
-  %cmp = icmp eq i32 %x, %y
-  br i1 %cmp, label %same, label %different
-
-same:
-  %cmp2 = icmp ne i32 %x, %y
-  ret i1 %cmp2
-
-different:
-  %cmp3 = icmp eq i32 %x, %y
-  ret i1 %cmp3
-}
-
-define i1 @test6(i32 %x, i32 %y) {
-; CHECK-LABEL: @test6(
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp eq i32 [[X]], [[Y]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
-; CHECK:       same:
-; CHECK-NEXT:    ret i1 [[CMP2]]
-; CHECK:       different:
-; CHECK-NEXT:    ret i1 [[CMP3]]
-;
-  %cmp2 = icmp ne i32 %x, %y
-  %cmp = icmp eq i32 %x, %y
-  %cmp3 = icmp eq i32 %x, %y
-  br i1 %cmp, label %same, label %different
-
-same:
-  ret i1 %cmp2
-
-different:
-  ret i1 %cmp3
-}
-
-define i1 @test6_fp(float %x, float %y) {
-; CHECK-LABEL: @test6_fp(
-; CHECK-NEXT:    [[CMP2:%.*]] = fcmp une float [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = fcmp oeq float [[X]], [[Y]]
-; CHECK-NEXT:    [[CMP3:%.*]] = fcmp oeq float [[X]], [[Y]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
-; CHECK:       same:
-; CHECK-NEXT:    ret i1 [[CMP2]]
-; CHECK:       different:
-; CHECK-NEXT:    ret i1 [[CMP3]]
-;
-  %cmp2 = fcmp une float %x, %y
-  %cmp = fcmp oeq float %x, %y
-  %cmp3 = fcmp oeq float  %x, %y
-  br i1 %cmp, label %same, label %different
-
-same:
-  ret i1 %cmp2
-
-different:
-  ret i1 %cmp3
-}
-
-define i1 @test7(i32 %x, i32 %y) {
-; CHECK-LABEL: @test7(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]]
-; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
-; CHECK:         [[Y_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
-; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
-; CHECK:       same:
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[X_0]], [[Y_0]]
-; CHECK-NEXT:    ret i1 [[CMP2]]
-; CHECK:       different:
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp sgt i32 [[X_1]], [[Y_1]]
-; CHECK-NEXT:    ret i1 [[CMP3]]
-;
-  %cmp = icmp sgt i32 %x, %y
-  br i1 %cmp, label %same, label %different
-
-same:
-  %cmp2 = icmp sle i32 %x, %y
-  ret i1 %cmp2
-
-different:
-  %cmp3 = icmp sgt i32 %x, %y
-  ret i1 %cmp3
-}
-
-define i1 @test7_fp(float %x, float %y) {
-; CHECK-LABEL: @test7_fp(
-; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[X:%.*]], [[Y:%.*]]
-; CHECK:         [[X_0:%.*]] = call float @llvm.ssa.copy.f32(float [[X]])
-; CHECK:         [[X_1:%.*]] = call float @llvm.ssa.copy.f32(float [[X]])
-; CHECK:         [[Y_0:%.*]] = call float @llvm.ssa.copy.f32(float [[Y]])
-; CHECK:         [[Y_1:%.*]] = call float @llvm.ssa.copy.f32(float [[Y]])
-; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
-; CHECK:       same:
-; CHECK-NEXT:    [[CMP2:%.*]] = fcmp ule float [[X_0]], [[Y_0]]
-; CHECK-NEXT:    ret i1 [[CMP2]]
-; CHECK:       different:
-; CHECK-NEXT:    [[CMP3:%.*]] = fcmp ogt float [[X_1]], [[Y_1]]
-; CHECK-NEXT:    ret i1 [[CMP3]]
-;
-  %cmp = fcmp ogt float %x, %y
-  br i1 %cmp, label %same, label %different
-
-same:
-  %cmp2 = fcmp ule float %x, %y
-  ret i1 %cmp2
-
-different:
-  %cmp3 = fcmp ogt float %x, %y
-  ret i1 %cmp3
-}
-
-define i1 @test8(i32 %x, i32 %y) {
-; CHECK-LABEL: @test8(
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[CMP3:%.*]] = icmp sgt i32 [[X]], [[Y]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
-; CHECK:       same:
-; CHECK-NEXT:    ret i1 [[CMP2]]
-; CHECK:       different:
-; CHECK-NEXT:    ret i1 [[CMP3]]
-;
-  %cmp2 = icmp sle i32 %x, %y
-  %cmp = icmp sgt i32 %x, %y
-  %cmp3 = icmp sgt i32 %x, %y
-  br i1 %cmp, label %same, label %different
-
-same:
-  ret i1 %cmp2
-
-different:
-  ret i1 %cmp3
-}
-
-define i1 @test8_fp(float %x, float %y) {
-; CHECK-LABEL: @test8_fp(
-; CHECK-NEXT:    [[CMP2:%.*]] = fcmp ule float [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = fcmp ogt float [[X]], [[Y]]
-; CHECK-NEXT:    [[CMP3:%.*]] = fcmp ogt float [[X]], [[Y]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[SAME:%.*]], label [[DIFFERENT:%.*]]
-; CHECK:       same:
-; CHECK-NEXT:    ret i1 [[CMP2]]
-; CHECK:       different:
-; CHECK-NEXT:    ret i1 [[CMP3]]
-;
-  %cmp2 = fcmp ule float %x, %y
-  %cmp = fcmp ogt float %x, %y
-  %cmp3 = fcmp ogt float %x, %y
-  br i1 %cmp, label %same, label %different
-
-same:
-  ret i1 %cmp2
-
-different:
-  ret i1 %cmp3
-}
-
-define i32 @test9(i32 %i, i32 %j) {
-; CHECK-LABEL: @test9(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[I:%.*]], [[J:%.*]]
-; CHECK:         [[I_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[I]])
-; CHECK:         [[J_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[J]])
-; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[RET:%.*]]
-; CHECK:       cond_true:
-; CHECK-NEXT:    [[DIFF:%.*]] = sub i32 [[I_0]], [[J_0]]
-; CHECK-NEXT:    ret i32 [[DIFF]]
-; CHECK:       ret:
-; CHECK-NEXT:    ret i32 5
-;
-  %cmp = icmp eq i32 %i, %j
-  br i1 %cmp, label %cond_true, label %ret
-
-cond_true:
-  %diff = sub i32 %i, %j
-  ret i32 %diff
-
-ret:
-  ret i32 5
-}
-
-define i32 @test10(i32 %j, i32 %i) {
-; CHECK-LABEL: @test10(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[I:%.*]], [[J:%.*]]
-; CHECK:         [[J_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[J]])
-; CHECK:         [[I_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[I]])
-; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[RET:%.*]]
-; CHECK:       cond_true:
-; CHECK-NEXT:    [[DIFF:%.*]] = sub i32 [[I_0]], [[J_0]]
-; CHECK-NEXT:    ret i32 [[DIFF]]
-; CHECK:       ret:
-; CHECK-NEXT:    ret i32 5
-;
-  %cmp = icmp eq i32 %i, %j
-  br i1 %cmp, label %cond_true, label %ret
-
-cond_true:
-  %diff = sub i32 %i, %j
-  ret i32 %diff
-
-ret:
-  ret i32 5
-}
-
-declare i32 @yogibar()
-
-define i32 @test11(i32 %x) {
-; CHECK-LABEL: @test11(
-; CHECK-NEXT:    [[V0:%.*]] = call i32 @yogibar()
-; CHECK-NEXT:    [[V1:%.*]] = call i32 @yogibar()
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[V0]], [[V1]]
-; CHECK:         [[V0_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[V0]])
-; CHECK:         [[V1_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[V1]])
-; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[NEXT:%.*]]
-; CHECK:       cond_true:
-; CHECK-NEXT:    ret i32 [[V1_0]]
-; CHECK:       next:
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[X:%.*]], [[V0_0]]
-; CHECK:         [[V0_0_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[V0_0]])
-; CHECK-NEXT:    br i1 [[CMP2]], label [[COND_TRUE2:%.*]], label [[NEXT2:%.*]]
-; CHECK:       cond_true2:
-; CHECK-NEXT:    ret i32 [[V0_0_1]]
-; CHECK:       next2:
-; CHECK-NEXT:    ret i32 0
-;
-  %v0 = call i32 @yogibar()
-  %v1 = call i32 @yogibar()
-  %cmp = icmp eq i32 %v0, %v1
-  br i1 %cmp, label %cond_true, label %next
-
-cond_true:
-  ret i32 %v1
-
-next:
-  %cmp2 = icmp eq i32 %x, %v0
-  br i1 %cmp2, label %cond_true2, label %next2
-
-cond_true2:
-  ret i32 %v0
-
-next2:
-  ret i32 0
-}
-
-define i32 @test12(i32 %x) {
-; CHECK-LABEL: @test12(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], 0
-; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[X_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_FALSE:%.*]]
-; CHECK:       cond_true:
-; CHECK-NEXT:    br label [[RET:%.*]]
-; CHECK:       cond_false:
-; CHECK-NEXT:    br label [[RET]]
-; CHECK:       ret:
-; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[X_0]], [[COND_TRUE]] ], [ [[X_1]], [[COND_FALSE]] ]
-; CHECK-NEXT:    ret i32 [[RES]]
-;
-  %cmp = icmp eq i32 %x, 0
-  br i1 %cmp, label %cond_true, label %cond_false
-
-cond_true:
-  br label %ret
-
-cond_false:
-  br label %ret
-
-ret:
-  %res = phi i32 [ %x, %cond_true ], [ %x, %cond_false ]
-  ret i32 %res
-}

test/Transforms/Util/PredicateInfo/testandor2.ll

-; REQUIRES: abi-breaking-checks
-; NOTE: The flag -reverse-iterate is present only in a +Asserts build.
-; Hence, this test has been split from testandor.ll to test with -reverse-iterate.
-; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -print-predicateinfo -reverse-iterate < %s 2>&1 | FileCheck %s
-
-declare void @foo(i1)
-declare void @bar(i32)
-declare void @llvm.assume(i1)
-
-define void @testor(i32 %x, i32 %y) {
-; CHECK-LABEL: @testor(
-; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
-; CHECK-NEXT:    [[Z:%.*]] = or i1 [[XZ]], [[YZ]]
-; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
-; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
-; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
-; CHECK:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[Z]])
-; CHECK-NEXT:    br i1 [[Z]], label [[ONEOF:%.*]], label [[NEITHER:%.*]]
-; CHECK:       oneof:
-; CHECK-NEXT:    call void @foo(i1 [[XZ]])
-; CHECK-NEXT:    call void @foo(i1 [[YZ]])
-; CHECK-NEXT:    call void @bar(i32 [[X]])
-; CHECK-NEXT:    call void @bar(i32 [[Y]])
-; CHECK-NEXT:    ret void
-; CHECK:       neither:
-; CHECK-NEXT:    call void @foo(i1 [[XZ_0]])
-; CHECK-NEXT:    call void @foo(i1 [[YZ_0]])
-; CHECK-NEXT:    call void @bar(i32 [[X_0]])
-; CHECK-NEXT:    call void @bar(i32 [[Y_0]])
-; CHECK-NEXT:    call void @foo(i1 [[Z_0]])
-; CHECK-NEXT:    ret void
-;
-  %xz = icmp eq i32 %x, 0
-  %yz = icmp eq i32 %y, 0
-  %z = or i1 %xz, %yz
-  br i1 %z, label %oneof, label %neither
-oneof:
-;; Should not insert on the true edge for or
-  call void @foo(i1 %xz)
-  call void @foo(i1 %yz)
-  call void @bar(i32 %x)
-  call void @bar(i32 %y)
-  ret void
-neither:
-  call void @foo(i1 %xz)
-  call void @foo(i1 %yz)
-  call void @bar(i32 %x)
-  call void @bar(i32 %y)
-  call void @foo(i1 %z)
-  ret void
-}
-define void @testand(i32 %x, i32 %y) {
-; CHECK-LABEL: @testand(
-; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
-; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XZ]], [[YZ]]
-; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[Y_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
-; CHECK:         [[XZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
-; CHECK:         [[YZ_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
-; CHECK:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[Z]])
-; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
-; CHECK:       both:
-; CHECK-NEXT:    call void @foo(i1 [[XZ_0]])
-; CHECK-NEXT:    call void @foo(i1 [[YZ_0]])
-; CHECK-NEXT:    call void @bar(i32 [[X_0]])
-; CHECK-NEXT:    call void @bar(i32 [[Y_0]])
-; CHECK-NEXT:    ret void
-; CHECK:       nope:
-; CHECK-NEXT:    call void @foo(i1 [[XZ]])
-; CHECK-NEXT:    call void @foo(i1 [[YZ]])
-; CHECK-NEXT:    call void @bar(i32 [[X]])
-; CHECK-NEXT:    call void @bar(i32 [[Y]])
-; CHECK-NEXT:    call void @foo(i1 [[Z_0]])
-; CHECK-NEXT:    ret void
-;
-  %xz = icmp eq i32 %x, 0
-  %yz = icmp eq i32 %y, 0
-  %z = and i1 %xz, %yz
-  br i1 %z, label %both, label %nope
-both:
-  call void @foo(i1 %xz)
-  call void @foo(i1 %yz)
-  call void @bar(i32 %x)
-  call void @bar(i32 %y)
-  ret void
-nope:
-;; Should not insert on the false edge for and
-  call void @foo(i1 %xz)
-  call void @foo(i1 %yz)
-  call void @bar(i32 %x)
-  call void @bar(i32 %y)
-  call void @foo(i1 %z)
-  ret void
-}
-define void @testandsame(i32 %x, i32 %y) {
-; CHECK-LABEL: @testandsame(
-; CHECK-NEXT:    [[XGT:%.*]] = icmp sgt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[XLT:%.*]] = icmp slt i32 [[X]], 100
-; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XGT]], [[XLT]]
-; CHECK:         [[X_0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[X_0_1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X_0]])
-; CHECK:         [[XGT_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XGT]])
-; CHECK:         [[XLT_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XLT]])
-; CHECK:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[Z]])
-; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
-; CHECK:       both:
-; CHECK-NEXT:    call void @foo(i1 [[XGT_0]])
-; CHECK-NEXT:    call void @foo(i1 [[XLT_0]])
-; CHECK-NEXT:    call void @bar(i32 [[X_0_1]])
-; CHECK-NEXT:    ret void
-; CHECK:       nope:
-; CHECK-NEXT:    call void @foo(i1 [[XGT]])
-; CHECK-NEXT:    call void @foo(i1 [[XLT]])
-; CHECK-NEXT:    call void @foo(i1 [[Z_0]])
-; CHECK-NEXT:    ret void
-;
-  %xgt = icmp sgt i32 %x, 0
-  %xlt = icmp slt i32 %x, 100
-  %z = and i1 %xgt, %xlt
-  br i1 %z, label %both, label %nope
-both:
-  call void @foo(i1 %xgt)
-  call void @foo(i1 %xlt)
-  call void @bar(i32 %x)
-  ret void
-nope:
-  call void @foo(i1 %xgt)
-  call void @foo(i1 %xlt)
-  call void @foo(i1 %z)
-  ret void
-}
-
-define void @testandassume(i32 %x, i32 %y) {
-; CHECK-LABEL: @testandassume(
-; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
-; CHECK-NEXT:    [[Z:%.*]] = and i1 [[XZ]], [[YZ]]
-; CHECK:         [[TMP1:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[X]])
-; CHECK:         [[TMP2:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[Y]])
-; CHECK:         [[TMP3:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[XZ]])
-; CHECK:         [[TMP4:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[YZ]])
-; CHECK:         [[TMP5:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[Z]])
-; CHECK-NEXT:    call void @llvm.assume(i1 [[TMP5]])
-; CHECK:         [[DOT0:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[TMP1]])
-; CHECK:         [[DOT01:%.*]] = call i32 @llvm.ssa.copy.i32(i32 [[TMP2]])
-; CHECK:         [[DOT02:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[TMP3]])
-; CHECK:         [[DOT03:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[TMP4]])
-; CHECK:         [[DOT04:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[TMP5]])
-; CHECK-NEXT:    br i1 [[TMP5]], label [[BOTH:%.*]], label [[NOPE:%.*]]
-; CHECK:       both:
-; CHECK-NEXT:    call void @foo(i1 [[DOT02]])
-; CHECK-NEXT:    call void @foo(i1 [[DOT03]])
-; CHECK-NEXT:    call void @bar(i32 [[DOT0]])
-; CHECK-NEXT:    call void @bar(i32 [[DOT01]])
-; CHECK-NEXT:    ret void
-; CHECK:       nope:
-; CHECK-NEXT:    call void @foo(i1 [[DOT04]])
-; CHECK-NEXT:    ret void
-;
-  %xz = icmp eq i32 %x, 0
-  %yz = icmp eq i32 %y, 0
-  %z = and i1 %xz, %yz
-  call void @llvm.assume(i1 %z)
-  br i1 %z, label %both, label %nope
-both:
-  call void @foo(i1 %xz)
-  call void @foo(i1 %yz)
-  call void @bar(i32 %x)
-  call void @bar(i32 %y)
-  ret void
-nope:
-  call void @foo(i1 %z)
-  ret void
-}
-
-;; Unlike and/or for branches, assume is *always* true, so we only match and for it
-define void @testorassume(i32 %x, i32 %y) {
-;
-; CHECK-LABEL: @testorassume(
-; CHECK-NEXT:    [[XZ:%.*]] = icmp eq i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[YZ:%.*]] = icmp eq i32 [[Y:%.*]], 0
-; CHECK-NEXT:    [[Z:%.*]] = or i1 [[XZ]], [[YZ]]
-; CHECK-NEXT:    call void @llvm.assume(i1 [[Z]])
-; CHECK:         [[Z_0:%.*]] = call i1 @llvm.ssa.copy.i1(i1 [[Z]])
-; CHECK-NEXT:    br i1 [[Z]], label [[BOTH:%.*]], label [[NOPE:%.*]]
-; CHECK:       both:
-; CHECK-NEXT:    call void @foo(i1 [[XZ]])
-; CHECK-NEXT:    call void @foo(i1 [[YZ]])
-; CHECK-NEXT:    call void @bar(i32 [[X]])
-; CHECK-NEXT:    call void @bar(i32 [[Y]])
-; CHECK-NEXT:    ret void
-; CHECK:       nope:
-; CHECK-NEXT:    call void @foo(i1 [[Z_0]])
-; CHECK-NEXT:    ret void
-;
-  %xz = icmp eq i32 %x, 0
-  %yz = icmp eq i32 %y, 0
-  %z = or i1 %xz, %yz
-  call void @llvm.assume(i1 %z)
-  br i1 %z, label %both, label %nope
-both:
-  call void @foo(i1 %xz)
-  call void @foo(i1 %yz)
-  call void @bar(i32 %x)
-  call void @bar(i32 %y)
-  ret void
-nope:
-  call void @foo(i1 %z)
-  ret void
-}

unittests/ADT/ReverseIterationTest.cpp

-//===- llvm/unittest/ADT/ReverseIterationTest.cpp ------------------------------===//
+//===- 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.
+// Reverse Iteration unit tests.
 //
-//===----------------------------------------------------------------------===//
+//===---------------------------------------------------------------------===//
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Support/ReverseIteration.h"
 #include "gtest/gtest.h"
 
-#if LLVM_ENABLE_ABI_BREAKING_CHECKS
 using namespace llvm;
 
-TEST(ReverseIterationTest, SmallPtrSetTest) {
+TEST(ReverseIterationTest, DenseMapTest1) {
+  // Test reverse iteration for a DenseMap with pointer-like keys.
+  // DenseMap should reverse iterate if its keys are pointer-like.
+  DenseMap<int*, int> Map;
+  int a = 1, b = 2, c = 3, d = 4;
+  int *Keys[] = { &a, &b, &c, &d };
+
+  // Insert keys into the DenseMap.
+  for (auto *Key: Keys)
+    Map[Key] = 0;
+
+  // Note: This is the observed order of keys in the DenseMap.
+  // If there is any change in the behavior of the DenseMap, this order would
+  // need to be adjusted accordingly.
+  int *IterKeys[] = { &a, &b, &c, &d };
+  if (shouldReverseIterate<int *>())
+    std::reverse(&IterKeys[0], &IterKeys[4]);
+
+  // Check that the DenseMap is iterated in the expected order.
+  for (const auto &Tuple : zip(Map, IterKeys))
+    ASSERT_EQ(std::get<0>(Tuple).first, std::get<1>(Tuple));
+
+  // Check operator++ (post-increment).
+  int i = 0;
+  for (auto iter = Map.begin(), end = Map.end(); iter != end; iter++, ++i)
+    ASSERT_EQ(iter->first, IterKeys[i]);
+}
 
+TEST(ReverseIterationTest, DenseMapTest2) {
+  // For a DenseMap with non-pointer-like keys, forward iteration equals
+  // reverse iteration.
+  DenseMap<int, int> Map;
+  int Keys[] = { 1, 2, 3, 4 };
+
+  // Insert keys into the DenseMap.
+  for (auto Key: Keys)
+    Map[Key] = 0;
+
+  // Note: This is the observed order of keys in the DenseMap.
+  // If there is any change in the behavior of the DenseMap, this order
+  // would need to be adjusted accordingly.
+  int IterKeys[] = { 2, 4, 1, 3 };
+  if (shouldReverseIterate<int>())
+    std::reverse(&IterKeys[0], &IterKeys[4]);
+
+  // Check that the DenseMap is iterated in the expected order.
+  for (const auto &Tuple : zip(Map, IterKeys))
+    ASSERT_EQ(std::get<0>(Tuple).first, std::get<1>(Tuple));
+
+  // Check operator++ (post-increment).
+  int i = 0;
+  for (auto iter = Map.begin(), end = Map.end(); iter != end; iter++, ++i)
+    ASSERT_EQ(iter->first, IterKeys[i]);
+}
+
+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 };
+  int a = 1, b = 2, c = 3, d = 4;
+  int *Ptrs[] = { &a, &b, &c, &d };
 
   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));
+  // Note: This is the observed order of keys in the SmallPtrSet.
+  // If there is any change in the behavior of the SmallPtrSet, this order
+  // would need to be adjusted accordingly.
+  int *IterPtrs[] = { &a, &b, &c, &d };
+  if (shouldReverseIterate<int *>())
+    std::reverse(&IterPtrs[0], &IterPtrs[4]);
 
-  // Check operator++ (post-increment) in forward iteration.
-  int i = 0;
-  for (auto begin = Set.begin(), end = Set.end();
-             begin != end; i++)
-    ASSERT_EQ(*begin++, Ptrs[i]);
-
-  // Check reverse iteration.
-  ReverseIterate<bool>::value = true;
-  for (const auto &Tuple : zip(Set, ReversePtrs))
+  // Check that the SmallPtrSet is iterated in the expected order.
+  for (const auto &Tuple : zip(Set, IterPtrs))
     ASSERT_EQ(std::get<0>(Tuple), std::get<1>(Tuple));
 
-  // Check operator++ (post-increment) in reverse iteration. 
-  i = 0;
-  for (auto begin = Set.begin(), end = Set.end();
-             begin != end; i++)
-    ASSERT_EQ(*begin++, ReversePtrs[i]);
-
+  // Check operator++ (post-increment).
+  int i = 0;
+  for (auto iter = Set.begin(), end = Set.end(); iter != end; iter++, ++i)
+    ASSERT_EQ(*iter, IterPtrs[i]);
 }
-#endif