Skip to content

Commit 872f689

Browse files
author
Mandeep Singh Grang
committedAug 24, 2017
[ADT] Enable reverse iteration for DenseMap
Reviewers: mehdi_amini, dexonsmith, dblaikie, davide, chandlerc, davidxl, echristo, efriedma Reviewed By: dblaikie Subscribers: rsmith, mgorny, emaste, llvm-commits Differential Revision: https://reviews.llvm.org/D35043 llvm-svn: 311730
1 parent 66531dd commit 872f689

File tree

11 files changed

+228
-799
lines changed

11 files changed

+228
-799
lines changed
 

‎llvm/include/llvm/ADT/DenseMap.h

+84-23
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
#include "llvm/Support/AlignOf.h"
2020
#include "llvm/Support/Compiler.h"
2121
#include "llvm/Support/MathExtras.h"
22+
#include "llvm/Support/ReverseIteration.h"
2223
#include "llvm/Support/type_traits.h"
2324
#include <algorithm>
2425
#include <cassert>
@@ -67,18 +68,26 @@ class DenseMapBase : public DebugEpochBase {
6768
DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>;
6869

6970
inline iterator begin() {
70-
// When the map is empty, avoid the overhead of AdvancePastEmptyBuckets().
71-
return empty() ? end() : iterator(getBuckets(), getBucketsEnd(), *this);
71+
// When the map is empty, avoid the overhead of advancing/retreating past
72+
// empty buckets.
73+
if (empty())
74+
return end();
75+
if (shouldReverseIterate<KeyT>())
76+
return makeIterator(getBucketsEnd() - 1, getBuckets(), *this);
77+
return makeIterator(getBuckets(), getBucketsEnd(), *this);
7278
}
7379
inline iterator end() {
74-
return iterator(getBucketsEnd(), getBucketsEnd(), *this, true);
80+
return makeIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
7581
}
7682
inline const_iterator begin() const {
77-
return empty() ? end()
78-
: const_iterator(getBuckets(), getBucketsEnd(), *this);
83+
if (empty())
84+
return end();
85+
if (shouldReverseIterate<KeyT>())
86+
return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *this);
87+
return makeConstIterator(getBuckets(), getBucketsEnd(), *this);
7988
}
8089
inline const_iterator end() const {
81-
return const_iterator(getBucketsEnd(), getBucketsEnd(), *this, true);
90+
return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *this, true);
8291
}
8392

8493
LLVM_NODISCARD bool empty() const {
@@ -137,13 +146,13 @@ class DenseMapBase : public DebugEpochBase {
137146
iterator find(const_arg_type_t<KeyT> Val) {
138147
BucketT *TheBucket;
139148
if (LookupBucketFor(Val, TheBucket))
140-
return iterator(TheBucket, getBucketsEnd(), *this, true);
149+
return makeIterator(TheBucket, getBucketsEnd(), *this, true);
141150
return end();
142151
}
143152
const_iterator find(const_arg_type_t<KeyT> Val) const {
144153
const BucketT *TheBucket;
145154
if (LookupBucketFor(Val, TheBucket))
146-
return const_iterator(TheBucket, getBucketsEnd(), *this, true);
155+
return makeConstIterator(TheBucket, getBucketsEnd(), *this, true);
147156
return end();
148157
}
149158

@@ -156,14 +165,14 @@ class DenseMapBase : public DebugEpochBase {
156165
iterator find_as(const LookupKeyT &Val) {
157166
BucketT *TheBucket;
158167
if (LookupBucketFor(Val, TheBucket))
159-
return iterator(TheBucket, getBucketsEnd(), *this, true);
168+
return makeIterator(TheBucket, getBucketsEnd(), *this, true);
160169
return end();
161170
}
162171
template<class LookupKeyT>
163172
const_iterator find_as(const LookupKeyT &Val) const {
164173
const BucketT *TheBucket;
165174
if (LookupBucketFor(Val, TheBucket))
166-
return const_iterator(TheBucket, getBucketsEnd(), *this, true);
175+
return makeConstIterator(TheBucket, getBucketsEnd(), *this, true);
167176
return end();
168177
}
169178

@@ -197,14 +206,16 @@ class DenseMapBase : public DebugEpochBase {
197206
std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) {
198207
BucketT *TheBucket;
199208
if (LookupBucketFor(Key, TheBucket))
200-
return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
201-
false); // Already in map.
209+
return std::make_pair(
210+
makeIterator(TheBucket, getBucketsEnd(), *this, true),
211+
false); // Already in map.
202212

203213
// Otherwise, insert the new element.
204214
TheBucket =
205215
InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);
206-
return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
207-
true);
216+
return std::make_pair(
217+
makeIterator(TheBucket, getBucketsEnd(), *this, true),
218+
true);
208219
}
209220

210221
// Inserts key,value pair into the map if the key isn't already in the map.
@@ -214,13 +225,15 @@ class DenseMapBase : public DebugEpochBase {
214225
std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&... Args) {
215226
BucketT *TheBucket;
216227
if (LookupBucketFor(Key, TheBucket))
217-
return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
218-
false); // Already in map.
228+
return std::make_pair(
229+
makeIterator(TheBucket, getBucketsEnd(), *this, true),
230+
false); // Already in map.
219231

220232
// Otherwise, insert the new element.
221233
TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
222-
return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
223-
true);
234+
return std::make_pair(
235+
makeIterator(TheBucket, getBucketsEnd(), *this, true),
236+
true);
224237
}
225238

226239
/// Alternate version of insert() which allows a different, and possibly
@@ -233,14 +246,16 @@ class DenseMapBase : public DebugEpochBase {
233246
const LookupKeyT &Val) {
234247
BucketT *TheBucket;
235248
if (LookupBucketFor(Val, TheBucket))
236-
return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
237-
false); // Already in map.
249+
return std::make_pair(
250+
makeIterator(TheBucket, getBucketsEnd(), *this, true),
251+
false); // Already in map.
238252

239253
// Otherwise, insert the new element.
240254
TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),
241255
std::move(KV.second), Val);
242-
return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true),
243-
true);
256+
return std::make_pair(
257+
makeIterator(TheBucket, getBucketsEnd(), *this, true),
258+
true);
244259
}
245260

246261
/// insert - Range insertion of pairs.
@@ -411,6 +426,26 @@ class DenseMapBase : public DebugEpochBase {
411426
}
412427

413428
private:
429+
iterator makeIterator(BucketT *P, BucketT *E,
430+
DebugEpochBase &Epoch,
431+
bool NoAdvance=false) {
432+
if (shouldReverseIterate<KeyT>()) {
433+
BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
434+
return iterator(B, E, Epoch, NoAdvance);
435+
}
436+
return iterator(P, E, Epoch, NoAdvance);
437+
}
438+
439+
const_iterator makeConstIterator(const BucketT *P, const BucketT *E,
440+
const DebugEpochBase &Epoch,
441+
const bool NoAdvance=false) const {
442+
if (shouldReverseIterate<KeyT>()) {
443+
const BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1;
444+
return const_iterator(B, E, Epoch, NoAdvance);
445+
}
446+
return const_iterator(P, E, Epoch, NoAdvance);
447+
}
448+
414449
unsigned getNumEntries() const {
415450
return static_cast<const DerivedT *>(this)->getNumEntries();
416451
}
@@ -1095,7 +1130,13 @@ class DenseMapIterator : DebugEpochBase::HandleBase {
10951130
bool NoAdvance = false)
10961131
: DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) {
10971132
assert(isHandleInSync() && "invalid construction!");
1098-
if (!NoAdvance) AdvancePastEmptyBuckets();
1133+
1134+
if (NoAdvance) return;
1135+
if (shouldReverseIterate<KeyT>()) {
1136+
RetreatPastEmptyBuckets();
1137+
return;
1138+
}
1139+
AdvancePastEmptyBuckets();
10991140
}
11001141

11011142
// Converting ctor from non-const iterators to const iterators. SFINAE'd out
@@ -1109,10 +1150,14 @@ class DenseMapIterator : DebugEpochBase::HandleBase {
11091150

11101151
reference operator*() const {
11111152
assert(isHandleInSync() && "invalid iterator access!");
1153+
if (shouldReverseIterate<KeyT>())
1154+
return Ptr[-1];
11121155
return *Ptr;
11131156
}
11141157
pointer operator->() const {
11151158
assert(isHandleInSync() && "invalid iterator access!");
1159+
if (shouldReverseIterate<KeyT>())
1160+
return &(Ptr[-1]);
11161161
return Ptr;
11171162
}
11181163

@@ -1133,6 +1178,11 @@ class DenseMapIterator : DebugEpochBase::HandleBase {
11331178

11341179
inline DenseMapIterator& operator++() { // Preincrement
11351180
assert(isHandleInSync() && "invalid iterator access!");
1181+
if (shouldReverseIterate<KeyT>()) {
1182+
--Ptr;
1183+
RetreatPastEmptyBuckets();
1184+
return *this;
1185+
}
11361186
++Ptr;
11371187
AdvancePastEmptyBuckets();
11381188
return *this;
@@ -1144,13 +1194,24 @@ class DenseMapIterator : DebugEpochBase::HandleBase {
11441194

11451195
private:
11461196
void AdvancePastEmptyBuckets() {
1197+
assert(Ptr <= End);
11471198
const KeyT Empty = KeyInfoT::getEmptyKey();
11481199
const KeyT Tombstone = KeyInfoT::getTombstoneKey();
11491200

11501201
while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) ||
11511202
KeyInfoT::isEqual(Ptr->getFirst(), Tombstone)))
11521203
++Ptr;
11531204
}
1205+
1206+
void RetreatPastEmptyBuckets() {
1207+
assert(Ptr >= End);
1208+
const KeyT Empty = KeyInfoT::getEmptyKey();
1209+
const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1210+
1211+
while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) ||
1212+
KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone)))
1213+
--Ptr;
1214+
}
11541215
};
11551216

11561217
template<typename KeyT, typename ValueT, typename KeyInfoT>

‎llvm/include/llvm/ADT/SmallPtrSet.h

+5-18
Original file line numberDiff line numberDiff line change
@@ -16,7 +16,6 @@
1616
#define LLVM_ADT_SMALLPTRSET_H
1717

1818
#include "llvm/Support/Compiler.h"
19-
#include "llvm/Support/PointerLikeTypeTraits.h"
2019
#include "llvm/Support/ReverseIteration.h"
2120
#include "llvm/Support/type_traits.h"
2221
#include <cassert>
@@ -224,12 +223,10 @@ class SmallPtrSetIteratorImpl {
224223
public:
225224
explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
226225
: Bucket(BP), End(E) {
227-
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
228-
if (ReverseIterate<bool>::value) {
226+
if (shouldReverseIterate()) {
229227
RetreatIfNotValid();
230228
return;
231229
}
232-
#endif
233230
AdvanceIfNotValid();
234231
}
235232

@@ -251,7 +248,6 @@ class SmallPtrSetIteratorImpl {
251248
*Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
252249
++Bucket;
253250
}
254-
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
255251
void RetreatIfNotValid() {
256252
assert(Bucket >= End);
257253
while (Bucket != End &&
@@ -260,7 +256,6 @@ class SmallPtrSetIteratorImpl {
260256
--Bucket;
261257
}
262258
}
263-
#endif
264259
};
265260

266261
/// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet.
@@ -281,24 +276,20 @@ class SmallPtrSetIterator : public SmallPtrSetIteratorImpl {
281276
// Most methods provided by baseclass.
282277

283278
const PtrTy operator*() const {
284-
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
285-
if (ReverseIterate<bool>::value) {
279+
if (shouldReverseIterate()) {
286280
assert(Bucket > End);
287281
return PtrTraits::getFromVoidPointer(const_cast<void *>(Bucket[-1]));
288282
}
289-
#endif
290283
assert(Bucket < End);
291284
return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
292285
}
293286

294287
inline SmallPtrSetIterator& operator++() { // Preincrement
295-
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
296-
if (ReverseIterate<bool>::value) {
288+
if (shouldReverseIterate()) {
297289
--Bucket;
298290
RetreatIfNotValid();
299291
return *this;
300292
}
301-
#endif
302293
++Bucket;
303294
AdvanceIfNotValid();
304295
return *this;
@@ -396,21 +387,17 @@ class SmallPtrSetImpl : public SmallPtrSetImplBase {
396387
}
397388

398389
iterator begin() const {
399-
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
400-
if (ReverseIterate<bool>::value)
390+
if (shouldReverseIterate())
401391
return makeIterator(EndPointer() - 1);
402-
#endif
403392
return makeIterator(CurArray);
404393
}
405394
iterator end() const { return makeIterator(EndPointer()); }
406395

407396
private:
408397
/// Create an iterator that dereferences to same place as the given pointer.
409398
iterator makeIterator(const void *const *P) const {
410-
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
411-
if (ReverseIterate<bool>::value)
399+
if (shouldReverseIterate())
412400
return iterator(P == EndPointer() ? CurArray : P + 1, CurArray);
413-
#endif
414401
return iterator(P, EndPointer());
415402
}
416403
};

‎llvm/include/llvm/Support/PointerLikeTypeTraits.h

+20-1
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,26 @@ template <size_t N>
3030
struct ConstantLog2
3131
: std::integral_constant<size_t, ConstantLog2<N / 2>::value + 1> {};
3232
template <> struct ConstantLog2<1> : std::integral_constant<size_t, 0> {};
33-
}
33+
34+
// Provide a trait to check if T is pointer-like.
35+
template <typename T, typename U = void> struct HasPointerLikeTypeTraits {
36+
static const bool value = false;
37+
};
38+
39+
// sizeof(T) is valid only for a complete T.
40+
template <typename T> struct HasPointerLikeTypeTraits<
41+
T, decltype((sizeof(PointerLikeTypeTraits<T>) + sizeof(T)), void())> {
42+
static const bool value = true;
43+
};
44+
45+
template <typename T> struct IsPointerLike {
46+
static const bool value = HasPointerLikeTypeTraits<T>::value;
47+
};
48+
49+
template <typename T> struct IsPointerLike<T *> {
50+
static const bool value = true;
51+
};
52+
} // namespace detail
3453

3554
// Provide PointerLikeTypeTraits for non-cvr pointers.
3655
template <typename T> struct PointerLikeTypeTraits<T *> {

‎llvm/include/llvm/Support/ReverseIteration.h

+7-5
Original file line numberDiff line numberDiff line change
@@ -2,16 +2,18 @@
22
#define LLVM_SUPPORT_REVERSEITERATION_H
33

44
#include "llvm/Config/abi-breaking.h"
5+
#include "llvm/Support/PointerLikeTypeTraits.h"
56

67
namespace llvm {
7-
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
8-
template <class T = void> struct ReverseIterate { static bool value; };
8+
9+
template<class T = void *>
10+
bool shouldReverseIterate() {
911
#if LLVM_ENABLE_REVERSE_ITERATION
10-
template <class T> bool ReverseIterate<T>::value = true;
12+
return detail::IsPointerLike<T>::value;
1113
#else
12-
template <class T> bool ReverseIterate<T>::value = false;
13-
#endif
14+
return false;
1415
#endif
1516
}
1617

18+
}
1719
#endif

‎llvm/lib/Support/CommandLine.cpp

-11
Original file line numberDiff line numberDiff line change
@@ -46,17 +46,6 @@ using namespace cl;
4646

4747
#define DEBUG_TYPE "commandline"
4848

49-
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
50-
namespace llvm {
51-
// If LLVM_ENABLE_ABI_BREAKING_CHECKS is set the flag -mllvm -reverse-iterate
52-
// can be used to toggle forward/reverse iteration of unordered containers.
53-
// This will help uncover differences in codegen caused due to undefined
54-
// iteration order.
55-
static cl::opt<bool, true> ReverseIteration("reverse-iterate",
56-
cl::location(ReverseIterate<bool>::value));
57-
}
58-
#endif
59-
6049
//===----------------------------------------------------------------------===//
6150
// Template instantiations and anchors.
6251
//

‎llvm/test/Transforms/Util/PredicateInfo/condprop2.ll

-474
This file was deleted.

‎llvm/test/Transforms/Util/PredicateInfo/testandor2.ll

-214
This file was deleted.

‎llvm/unittests/ADT/CMakeLists.txt

-1
Original file line numberDiff line numberDiff line change
@@ -42,7 +42,6 @@ set(ADTSources
4242
PostOrderIteratorTest.cpp
4343
PriorityWorklistTest.cpp
4444
RangeAdapterTest.cpp
45-
ReverseIterationTest.cpp
4645
SCCIteratorTest.cpp
4746
STLExtrasTest.cpp
4847
ScopeExitTest.cpp

‎llvm/unittests/ADT/ReverseIterationTest.cpp

-52
This file was deleted.

‎llvm/unittests/Support/CMakeLists.txt

+1
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,7 @@ add_llvm_unittest(SupportTests
4242
ProcessTest.cpp
4343
ProgramTest.cpp
4444
RegexTest.cpp
45+
ReverseIterationTest.cpp
4546
ReplaceFileTest.cpp
4647
ScaledNumberTest.cpp
4748
SourceMgrTest.cpp
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,111 @@
1+
//===- llvm/unittest/Support/ReverseIterationTest.cpp ---------------------===//
2+
//
3+
// The LLVM Compiler Infrastructure
4+
//
5+
// This file is distributed under the University of Illinois Open Source
6+
// License. See LICENSE.TXT for details.
7+
//
8+
//===---------------------------------------------------------------------===//
9+
//
10+
// Reverse Iteration unit tests.
11+
//
12+
//===---------------------------------------------------------------------===//
13+
14+
#include "llvm/ADT/DenseMap.h"
15+
#include "llvm/ADT/SmallPtrSet.h"
16+
#include "llvm/Support/ReverseIteration.h"
17+
#include "gtest/gtest.h"
18+
19+
using namespace llvm;
20+
21+
TEST(ReverseIterationTest, DenseMapTest1) {
22+
static_assert(detail::IsPointerLike<int *>::value,
23+
"int * is pointer-like");
24+
static_assert(detail::IsPointerLike<uintptr_t>::value,
25+
"uintptr_t is pointer-like");
26+
struct IncompleteType;
27+
static_assert(detail::IsPointerLike<IncompleteType *>::value,
28+
"incomplete * is pointer-like");
29+
30+
// Test reverse iteration for a DenseMap with pointer-like keys.
31+
// DenseMap should reverse iterate if its keys are pointer-like.
32+
DenseMap<int *, int> Map;
33+
int a = 1, b = 2, c = 3, d = 4;
34+
int *Keys[] = { &a, &b, &c, &d };
35+
36+
// Insert keys into the DenseMap.
37+
for (auto *Key: Keys)
38+
Map[Key] = 0;
39+
40+
// Note: This is the observed order of keys in the DenseMap.
41+
// If there is any change in the behavior of the DenseMap, this order would
42+
// need to be adjusted accordingly.
43+
int *IterKeys[] = { &a, &b, &c, &d };
44+
if (shouldReverseIterate<int *>())
45+
std::reverse(&IterKeys[0], &IterKeys[4]);
46+
47+
// Check that the DenseMap is iterated in the expected order.
48+
for (const auto &Tuple : zip(Map, IterKeys))
49+
ASSERT_EQ(*(std::get<0>(Tuple).first), *(std::get<1>(Tuple)));
50+
51+
// Check operator++ (post-increment).
52+
int i = 0;
53+
for (auto iter = Map.begin(), end = Map.end(); iter != end; iter++, ++i)
54+
ASSERT_EQ(iter->first, IterKeys[i]);
55+
}
56+
57+
TEST(ReverseIterationTest, DenseMapTest2) {
58+
static_assert(!detail::IsPointerLike<int>::value,
59+
"int is not pointer-like");
60+
61+
// For a DenseMap with non-pointer-like keys, forward iteration equals
62+
// reverse iteration.
63+
DenseMap<int, int> Map;
64+
int Keys[] = { 1, 2, 3, 4 };
65+
66+
// Insert keys into the DenseMap.
67+
for (auto Key: Keys)
68+
Map[Key] = 0;
69+
70+
// Note: This is the observed order of keys in the DenseMap.
71+
// If there is any change in the behavior of the DenseMap, this order
72+
// would need to be adjusted accordingly.
73+
int IterKeys[] = { 2, 4, 1, 3 };
74+
75+
// Check that the DenseMap is iterated in the expected order.
76+
for (const auto &Tuple : zip(Map, IterKeys))
77+
ASSERT_EQ(std::get<0>(Tuple).first, std::get<1>(Tuple));
78+
79+
// Check operator++ (post-increment).
80+
int i = 0;
81+
for (auto iter = Map.begin(), end = Map.end(); iter != end; iter++, ++i)
82+
ASSERT_EQ(iter->first, IterKeys[i]);
83+
}
84+
85+
TEST(ReverseIterationTest, SmallPtrSetTest) {
86+
static_assert(detail::IsPointerLike<void *>::value,
87+
"void * is pointer-like");
88+
89+
SmallPtrSet<void *, 4> Set;
90+
int a = 1, b = 2, c = 3, d = 4;
91+
int *Ptrs[] = { &a, &b, &c, &d };
92+
93+
for (auto *Ptr: Ptrs)
94+
Set.insert(Ptr);
95+
96+
// Note: This is the observed order of keys in the SmallPtrSet.
97+
// If there is any change in the behavior of the SmallPtrSet, this order
98+
// would need to be adjusted accordingly.
99+
int *IterPtrs[] = { &a, &b, &c, &d };
100+
if (shouldReverseIterate<int *>())
101+
std::reverse(&IterPtrs[0], &IterPtrs[4]);
102+
103+
// Check that the SmallPtrSet is iterated in the expected order.
104+
for (const auto &Tuple : zip(Set, IterPtrs))
105+
ASSERT_EQ(std::get<0>(Tuple), std::get<1>(Tuple));
106+
107+
// Check operator++ (post-increment).
108+
int i = 0;
109+
for (auto iter = Set.begin(), end = Set.end(); iter != end; iter++, ++i)
110+
ASSERT_EQ(*iter, IterPtrs[i]);
111+
}

0 commit comments

Comments
 (0)
Please sign in to comment.