Index: include/llvm/ADT/DenseMap.h =================================================================== --- include/llvm/ADT/DenseMap.h +++ include/llvm/ADT/DenseMap.h @@ -19,6 +19,7 @@ #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 #include @@ -67,18 +68,27 @@ DenseMapIterator; inline iterator begin() { +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + if (ReverseIteration::shouldRevIter()) + 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()) + 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 { @@ -131,13 +141,13 @@ iterator find(const_arg_type_t 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 Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return const_iterator(TheBucket, getBucketsEnd(), *this, true); + return makeConstIterator(TheBucket, getBucketsEnd(), *this, true); return end(); } @@ -150,14 +160,14 @@ 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 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(); } @@ -191,14 +201,16 @@ std::pair 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), + false); // Already in map. // Otherwise, insert the new element. TheBucket = InsertIntoBucket(TheBucket, std::move(Key), std::forward(Args)...); - return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), - true); + return std::make_pair( + makeIterator(TheBucket, getBucketsEnd(), *this, true), + true); } // Inserts key,value pair into the map if the key isn't already in the map. @@ -208,13 +220,15 @@ std::pair 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), + false); // Already in map. // Otherwise, insert the new element. TheBucket = InsertIntoBucket(TheBucket, Key, std::forward(Args)...); - return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), - true); + return std::make_pair( + makeIterator(TheBucket, getBucketsEnd(), *this, true), + true); } /// Alternate version of insert() which allows a different, and possibly @@ -227,14 +241,16 @@ 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), + false); // Already in map. // 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), + true); } /// insert - Range insertion of pairs. @@ -405,6 +421,30 @@ } private: + iterator makeIterator(BucketT *P, BucketT *E, + DebugEpochBase &Epoch, + bool NoAdvance=false) { +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + if (ReverseIteration::shouldRevIter()) { + 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()) { + 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(this)->getNumEntries(); } @@ -1089,6 +1129,12 @@ bool NoAdvance = false) : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) { assert(isHandleInSync() && "invalid construction!"); +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + if (ReverseIteration::shouldRevIter()) { + if (!NoAdvance) RetreatPastEmptyBuckets(); + return; + } +#endif if (!NoAdvance) AdvancePastEmptyBuckets(); } @@ -1103,10 +1149,18 @@ reference operator*() const { assert(isHandleInSync() && "invalid iterator access!"); +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + if (ReverseIteration::shouldRevIter()) + return Ptr[-1]; +#endif return *Ptr; } pointer operator->() const { assert(isHandleInSync() && "invalid iterator access!"); +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + if (ReverseIteration::shouldRevIter()) + return &(Ptr[-1]); +#endif return Ptr; } @@ -1127,6 +1181,13 @@ inline DenseMapIterator& operator++() { // Preincrement assert(isHandleInSync() && "invalid iterator access!"); +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + if (ReverseIteration::shouldRevIter()) { + --Ptr; + RetreatPastEmptyBuckets(); + return *this; + } +#endif ++Ptr; AdvancePastEmptyBuckets(); return *this; @@ -1138,6 +1199,7 @@ private: void AdvancePastEmptyBuckets() { + assert(Ptr <= End); const KeyT Empty = KeyInfoT::getEmptyKey(); const KeyT Tombstone = KeyInfoT::getTombstoneKey(); @@ -1145,6 +1207,17 @@ 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 Index: include/llvm/ADT/SmallPtrSet.h =================================================================== --- include/llvm/ADT/SmallPtrSet.h +++ include/llvm/ADT/SmallPtrSet.h @@ -225,7 +225,7 @@ explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E) : Bucket(BP), End(E) { #if LLVM_ENABLE_ABI_BREAKING_CHECKS - if (ReverseIterate::value) { + if (ReverseIteration::shouldRevIter()) { RetreatIfNotValid(); return; } @@ -282,7 +282,7 @@ const PtrTy operator*() const { #if LLVM_ENABLE_ABI_BREAKING_CHECKS - if (ReverseIterate::value) { + if (ReverseIteration::shouldRevIter()) { assert(Bucket > End); return PtrTraits::getFromVoidPointer(const_cast(Bucket[-1])); } @@ -293,7 +293,7 @@ inline SmallPtrSetIterator& operator++() { // Preincrement #if LLVM_ENABLE_ABI_BREAKING_CHECKS - if (ReverseIterate::value) { + if (ReverseIteration::shouldRevIter()) { --Bucket; RetreatIfNotValid(); return *this; @@ -397,7 +397,7 @@ iterator begin() const { #if LLVM_ENABLE_ABI_BREAKING_CHECKS - if (ReverseIterate::value) + if (ReverseIteration::shouldRevIter()) return makeIterator(EndPointer() - 1); #endif return makeIterator(CurArray); @@ -408,7 +408,7 @@ /// 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::value) + if (ReverseIteration::shouldRevIter()) return iterator(P == EndPointer() ? CurArray : P + 1, CurArray); #endif return iterator(P, EndPointer()); Index: include/llvm/Support/PointerLikeTypeTraits.h =================================================================== --- include/llvm/Support/PointerLikeTypeTraits.h +++ include/llvm/Support/PointerLikeTypeTraits.h @@ -34,6 +34,23 @@ struct ConstantLog2 : std::integral_constant::value + 1> {}; template <> struct ConstantLog2<1> : std::integral_constant {}; + +// Provide a trait for checking whether T is pointer-like. +template struct traits {}; +template struct traits { + enum { x = 1 }; +}; + +template struct is_pointer_like { + static char test_pointer(const void *); + + template + static typename std::enable_if::x != 0, + char (&)[2]>::type test_pointer(U *); + + static const bool value = + sizeof(test_pointer(std::declval())) == sizeof(char (&)[2]); +}; } // Provide PointerLikeTypeTraits for non-cvr pointers. Index: include/llvm/Support/ReverseIteration.h =================================================================== --- include/llvm/Support/ReverseIteration.h +++ include/llvm/Support/ReverseIteration.h @@ -3,15 +3,24 @@ #include "llvm/Config/abi-breaking.h" -namespace llvm { #if LLVM_ENABLE_ABI_BREAKING_CHECKS -template struct ReverseIterate { static bool value; }; -#if LLVM_ENABLE_REVERSE_ITERATION -template bool ReverseIterate::value = true; -#else -template bool ReverseIterate::value = false; -#endif -#endif -} +namespace llvm { +class ReverseIteration { +private: + ReverseIteration() {} + static bool RevIter; + +public: + template + static bool shouldRevIter() { + return RevIter && detail::is_pointer_like::value; + } + + static bool get() { return RevIter; }; + static bool *getRef() { return &RevIter; }; +}; + +} +#endif #endif Index: lib/Support/CMakeLists.txt =================================================================== --- lib/Support/CMakeLists.txt +++ lib/Support/CMakeLists.txt @@ -87,6 +87,7 @@ PrettyStackTrace.cpp RandomNumberGenerator.cpp Regex.cpp + ReverseIteration.cpp ScaledNumber.cpp ScopedPrinter.cpp SHA1.cpp Index: lib/Support/CommandLine.cpp =================================================================== --- lib/Support/CommandLine.cpp +++ lib/Support/CommandLine.cpp @@ -46,17 +46,6 @@ #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 ReverseIteration("reverse-iterate", - cl::location(ReverseIterate::value)); -} -#endif - //===----------------------------------------------------------------------===// // Template instantiations and anchors. // Index: lib/Support/ReverseIteration.cpp =================================================================== --- /dev/null +++ lib/Support/ReverseIteration.cpp @@ -0,0 +1,17 @@ +#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 + ReverseIterate("reverse-iterate", cl::Hidden, + cl::location(*ReverseIteration::getRef())); +} +#endif Index: unittests/ADT/ReverseIterationTest.cpp =================================================================== --- unittests/ADT/ReverseIterationTest.cpp +++ unittests/ADT/ReverseIterationTest.cpp @@ -7,46 +7,91 @@ // //===----------------------------------------------------------------------===// // -// 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 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 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 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::value = false; - for (const auto &Tuple : zip(Set, Ptrs)) - ASSERT_EQ(std::get<0>(Tuple), std::get<1>(Tuple)); - - // 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]); + // 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 reverse iteration. - ReverseIterate::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