[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

15

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

24–25

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)

31

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.

89

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

15

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

31

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

15

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

1134–1138

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

37–53

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

9–22

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)

11

default

lib/Support/ReverseIteration.cpp

9–13

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

9

@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

9

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

39

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

39

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

73–74

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() {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIteration::shouldRevIter<KeyT>())
+      return makeIterator(getBucketsEnd() - 1, getBuckets(), *this);
+#endif
     // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets().
-    return empty() ? end() : iterator(getBuckets(), getBucketsEnd(), *this);
+    return empty() ? end()
+                   : makeIterator(getBuckets(), getBucketsEnd(), *this);
   }
   inline iterator end() {
-    return iterator(getBucketsEnd(), getBucketsEnd(), *this, true);
+    return makeIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
   }
   inline const_iterator begin() const {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIteration::shouldRevIter<KeyT>())
+      return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *this);
+#endif
     return empty() ? end()
-                   : const_iterator(getBuckets(), getBucketsEnd(), *this);
+                   : 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
#endif
   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))
#endif
 
   // 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 LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIteration::shouldRevIter<KeyT>()) {
+      BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
+      return iterator(B, E, Epoch, NoAdvance);
+    }
+#endif
+    return iterator(P, E, Epoch, NoAdvance);
+  }
+
+  const_iterator makeConstIterator(const BucketT *P, const BucketT *E,
+                                   const DebugEpochBase &Epoch,
+                                   const bool NoAdvance=false) const {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIteration::shouldRevIter<KeyT>()) {
+      const BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
+      return const_iterator(B, E, Epoch, NoAdvance);
+    }
+#endif
+    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 LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIteration::shouldRevIter<KeyT>()) {
+      if (!NoAdvance) RetreatPastEmptyBuckets();
+      return;
+    }
+#endif
     if (!NoAdvance) 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 LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIteration::shouldRevIter<KeyT>())
+      return Ptr[-1];
+#endif
     return *Ptr;
   }
   pointer operator->() const {
     assert(isHandleInSync() && "invalid iterator access!");
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIteration::shouldRevIter<KeyT>())
+      return &(Ptr[-1]);
+#endif
     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 LLVM_ENABLE_ABI_BREAKING_CHECKS
+    if (ReverseIteration::shouldRevIter<KeyT>()) {
+      --Ptr;
+      RetreatPastEmptyBuckets();
+      return *this;
+    }
+#endif
     ++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;
   }
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+  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;
+  }
+#endif
 };
 
 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

 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 (ReverseIteration::shouldRevIter()) {
       RetreatIfNotValid();
       return;
     }
 #endif
     AdvanceIfNotValid();
   }
 
   bool operator==(const SmallPtrSetIteratorImpl &RHS) const {
public:
 
   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 (ReverseIteration::shouldRevIter()) {
       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 (ReverseIteration::shouldRevIter()) {
       --Bucket;
       RetreatIfNotValid();
       return *this;
     }
 #endif
     ++Bucket;
     AdvanceIfNotValid();
     return *this;
public:
   }
 
   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 (ReverseIteration::shouldRevIter())
       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 (ReverseIteration::shouldRevIter())
       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

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
 };
 
 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> {};
+
+// Provide a trait for checking whether T is pointer-like.
+template <typename T> struct traits {};
+template <typename T> struct traits<T *> {
+  enum { x = 1 };
+};
+
+template <typename T> struct is_pointer_like {
+  static char test_pointer(const void *);
+
+  template <typename U>
+  static typename std::enable_if<traits<U>::x != 0,
+    char (&)[2]>::type test_pointer(U *);
+
+  static const bool value =
+    sizeof(test_pointer(std::declval<T *>())) == sizeof(char (&)[2]);
+};
 }
 
 // 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); }
 

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; };
-#if LLVM_ENABLE_REVERSE_ITERATION
-template <class T> bool ReverseIterate<T>::value = true;
-#else
-template <class T> bool ReverseIterate<T>::value = false;
-#endif
-#endif
+namespace llvm {
+
+class ReverseIteration {
+private:
+  ReverseIteration() {}
+  static bool RevIter;
+
+public:
+  template<class T = void*>
+  static bool shouldRevIter() {
+    return RevIter && detail::is_pointer_like<T>::value;
   }
 
+  static bool get() { return RevIter; };
+  static bool *getRef() { return &RevIter; };
+};
+
+}
+#endif
 #endif

lib/Support/CMakeLists.txt

add_llvm_library(LLVMSupport
   MD5.cpp
   NativeFormatting.cpp
   Options.cpp
   Parallel.cpp
   PluginLoader.cpp
   PrettyStackTrace.cpp
   RandomNumberGenerator.cpp
   Regex.cpp
+  ReverseIteration.cpp
   ScaledNumber.cpp
   ScopedPrinter.cpp
   SHA1.cpp
   SmallPtrSet.cpp
   SmallVector.cpp
   SourceMgr.cpp
   SpecialCaseList.cpp
   Statistic.cpp

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>;

lib/Support/ReverseIteration.cpp

+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ReverseIteration.h"
+
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+namespace llvm {
+
+#if LLVM_ENABLE_REVERSE_ITERATION
+bool ReverseIteration::RevIter = true;
+#else
+bool ReverseIteration::RevIter = false;
+#endif
+
+static cl::opt<bool, true>
+  ReverseIterate("reverse-iterate", cl::Hidden,
+    cl::location(*ReverseIteration::getRef()));
+}
+#endif

unittests/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 (ReverseIteration::get())
+    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.
+  int IterKeys[] = { 2, 4, 1, 3 };
+
+  // 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;
+  void *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.
+  void *IterPtrs[] = { &a, &b, &c, &d };
+  if (ReverseIteration::get())
+    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