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,26 @@ DenseMapIterator; 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()) + 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()) + 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 { @@ -131,13 +140,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 +159,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 +200,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 +219,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 +240,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 +420,26 @@ } private: + iterator makeIterator(BucketT *P, BucketT *E, + DebugEpochBase &Epoch, + bool NoAdvance=false) { + if (shouldReverseIterate()) { + 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()) { + 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(this)->getNumEntries(); } @@ -1089,7 +1124,13 @@ bool NoAdvance = false) : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) { assert(isHandleInSync() && "invalid construction!"); - if (!NoAdvance) AdvancePastEmptyBuckets(); + + if (NoAdvance) return; + if (shouldReverseIterate()) { + RetreatPastEmptyBuckets(); + return; + } + AdvancePastEmptyBuckets(); } // Converting ctor from non-const iterators to const iterators. SFINAE'd out @@ -1103,10 +1144,14 @@ reference operator*() const { assert(isHandleInSync() && "invalid iterator access!"); + if (shouldReverseIterate()) + return Ptr[-1]; return *Ptr; } pointer operator->() const { assert(isHandleInSync() && "invalid iterator access!"); + if (shouldReverseIterate()) + return &(Ptr[-1]); return Ptr; } @@ -1127,6 +1172,11 @@ inline DenseMapIterator& operator++() { // Preincrement assert(isHandleInSync() && "invalid iterator access!"); + if (shouldReverseIterate()) { + --Ptr; + RetreatPastEmptyBuckets(); + return *this; + } ++Ptr; AdvancePastEmptyBuckets(); return *this; @@ -1138,6 +1188,7 @@ private: void AdvancePastEmptyBuckets() { + assert(Ptr <= End); const KeyT Empty = KeyInfoT::getEmptyKey(); const KeyT Tombstone = KeyInfoT::getTombstoneKey(); @@ -1145,6 +1196,16 @@ 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 Index: include/llvm/ADT/SmallPtrSet.h =================================================================== --- include/llvm/ADT/SmallPtrSet.h +++ include/llvm/ADT/SmallPtrSet.h @@ -224,12 +224,10 @@ public: explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E) : Bucket(BP), End(E) { -#if LLVM_ENABLE_ABI_BREAKING_CHECKS - if (ReverseIterate::value) { + if (shouldReverseIterate()) { RetreatIfNotValid(); return; } -#endif AdvanceIfNotValid(); } @@ -251,7 +249,6 @@ *Bucket == SmallPtrSetImplBase::getTombstoneMarker())) ++Bucket; } -#if LLVM_ENABLE_ABI_BREAKING_CHECKS void RetreatIfNotValid() { assert(Bucket >= End); while (Bucket != End && @@ -260,7 +257,6 @@ --Bucket; } } -#endif }; /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet. @@ -281,24 +277,20 @@ // Most methods provided by baseclass. const PtrTy operator*() const { -#if LLVM_ENABLE_ABI_BREAKING_CHECKS - if (ReverseIterate::value) { + if (shouldReverseIterate()) { assert(Bucket > End); return PtrTraits::getFromVoidPointer(const_cast(Bucket[-1])); } -#endif assert(Bucket < End); return PtrTraits::getFromVoidPointer(const_cast(*Bucket)); } inline SmallPtrSetIterator& operator++() { // Preincrement -#if LLVM_ENABLE_ABI_BREAKING_CHECKS - if (ReverseIterate::value) { + if (shouldReverseIterate()) { --Bucket; RetreatIfNotValid(); return *this; } -#endif ++Bucket; AdvanceIfNotValid(); return *this; @@ -396,10 +388,8 @@ } iterator begin() const { -#if LLVM_ENABLE_ABI_BREAKING_CHECKS - if (ReverseIterate::value) + if (shouldReverseIterate()) return makeIterator(EndPointer() - 1); -#endif return makeIterator(CurArray); } iterator end() const { return makeIterator(EndPointer()); } @@ -407,10 +397,8 @@ 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::value) + if (shouldReverseIterate()) 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 @@ -22,11 +22,7 @@ /// A traits type that is used to handle pointer types and things that are just /// wrappers for pointers as a uniform entity. -template class PointerLikeTypeTraits { - // getAsVoidPointer - // getFromVoidPointer - // getNumLowBitsAvailable -}; +template class PointerLikeTypeTraits; namespace detail { /// A tiny meta function to compute the log2 of a compile time constant. @@ -34,6 +30,22 @@ struct ConstantLog2 : std::integral_constant::value + 1> {}; template <> struct ConstantLog2<1> : std::integral_constant {}; + +// Trait to check if T is pointer. +template +struct is_pointer { static const bool value = false; }; + +template +struct is_pointer { static const bool value = true; }; + +// Trait to check if T is a complete type. +template +struct is_complete { static const bool value = false; }; + +template +struct is_complete { + static const bool value = true; +}; } // Provide PointerLikeTypeTraits for non-cvr pointers. Index: include/llvm/Support/ReverseIteration.h =================================================================== --- include/llvm/Support/ReverseIteration.h +++ include/llvm/Support/ReverseIteration.h @@ -4,14 +4,16 @@ #include "llvm/Config/abi-breaking.h" namespace llvm { -#if LLVM_ENABLE_ABI_BREAKING_CHECKS -template struct ReverseIterate { static bool value; }; + +template +bool shouldReverseIterate() { #if LLVM_ENABLE_REVERSE_ITERATION -template bool ReverseIterate::value = true; + return detail::is_complete::value && + detail::is_pointer::value; #else -template bool ReverseIterate::value = false; -#endif + return false; #endif } +} #endif 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: test/Transforms/Util/PredicateInfo/condprop2.ll =================================================================== --- test/Transforms/Util/PredicateInfo/condprop2.ll +++ /dev/null @@ -1,474 +0,0 @@ -; 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 ; [#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 -} Index: test/Transforms/Util/PredicateInfo/testandor2.ll =================================================================== --- test/Transforms/Util/PredicateInfo/testandor2.ll +++ /dev/null @@ -1,214 +0,0 @@ -; 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 -} Index: unittests/ADT/ReverseIterationTest.cpp =================================================================== --- unittests/ADT/ReverseIterationTest.cpp +++ unittests/ADT/ReverseIterationTest.cpp @@ -1,52 +1,97 @@ -//===- 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 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()) + 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 }; + if (shouldReverseIterate()) + 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 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::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. + int *IterPtrs[] = { &a, &b, &c, &d }; + if (shouldReverseIterate()) + 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