?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[InstCombine] Signed saturation tests. NFC
[llvm-complete.git] / unittests / ADT / HashingTest.cpp
blob66d63d437a4661d4cdf04262f157ffa97fb5525b
1 //===- llvm/unittest/ADT/HashingTest.cpp ----------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Hashing.h unit tests.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "llvm/ADT/Hashing.h"
14 #include "llvm/Support/DataTypes.h"
15 #include "gtest/gtest.h"
16 #include <deque>
17 #include <list>
18 #include <map>
19 #include <vector>
20
21 namespace llvm {
22
23 // Helper for test code to print hash codes.
24 void PrintTo(const hash_code &code, std::ostream *os) {
25 *os << static_cast<size_t>(code);
26 }
27
28 // Fake an object that is recognized as hashable data to test super large
29 // objects.
30 struct LargeTestInteger { uint64_t arr[8]; };
31
32 struct NonPOD {
33 uint64_t x, y;
34 NonPOD(uint64_t x, uint64_t y) : x(x), y(y) {}
35 friend hash_code hash_value(const NonPOD &obj) {
36 return hash_combine(obj.x, obj.y);
37 }
38 };
39
40 namespace hashing {
41 namespace detail {
42 template <> struct is_hashable_data<LargeTestInteger> : std::true_type {};
43 } // namespace detail
44 } // namespace hashing
45
46 } // namespace llvm
47
48 using namespace llvm;
49
50 namespace {
51
52 enum TestEnumeration {
53 TE_Foo = 42,
54 TE_Bar = 43
55 };
56
57 TEST(HashingTest, HashValueBasicTest) {
58 int x = 42, y = 43, c = 'x';
59 void *p = nullptr;
60 uint64_t i = 71;
61 const unsigned ci = 71;
62 volatile int vi = 71;
63 const volatile int cvi = 71;
64 uintptr_t addr = reinterpret_cast<uintptr_t>(&y);
65 EXPECT_EQ(hash_value(42), hash_value(x));
66 EXPECT_EQ(hash_value(42), hash_value(TE_Foo));
67 EXPECT_NE(hash_value(42), hash_value(y));
68 EXPECT_NE(hash_value(42), hash_value(TE_Bar));
69 EXPECT_NE(hash_value(42), hash_value(p));
70 EXPECT_EQ(hash_value(71), hash_value(i));
71 EXPECT_EQ(hash_value(71), hash_value(ci));
72 EXPECT_EQ(hash_value(71), hash_value(vi));
73 EXPECT_EQ(hash_value(71), hash_value(cvi));
74 EXPECT_EQ(hash_value(c), hash_value('x'));
75 EXPECT_EQ(hash_value('4'), hash_value('0' + 4));
76 EXPECT_EQ(hash_value(addr), hash_value(&y));
77 }
78
79 TEST(HashingTest, HashValueStdPair) {
80 EXPECT_EQ(hash_combine(42, 43), hash_value(std::make_pair(42, 43)));
81 EXPECT_NE(hash_combine(43, 42), hash_value(std::make_pair(42, 43)));
82 EXPECT_NE(hash_combine(42, 43), hash_value(std::make_pair(42ull, 43ull)));
83 EXPECT_NE(hash_combine(42, 43), hash_value(std::make_pair(42, 43ull)));
84 EXPECT_NE(hash_combine(42, 43), hash_value(std::make_pair(42ull, 43)));
85
86 // Note that pairs are implicitly flattened to a direct sequence of data and
87 // hashed efficiently as a consequence.
88 EXPECT_EQ(hash_combine(42, 43, 44),
89 hash_value(std::make_pair(42, std::make_pair(43, 44))));
90 EXPECT_EQ(hash_value(std::make_pair(42, std::make_pair(43, 44))),
91 hash_value(std::make_pair(std::make_pair(42, 43), 44)));
92
93 // Ensure that pairs which have padding bytes *inside* them don't get treated
94 // this way.
95 EXPECT_EQ(hash_combine('0', hash_combine(1ull, '2')),
96 hash_value(std::make_pair('0', std::make_pair(1ull, '2'))));
97
98 // Ensure that non-POD pairs don't explode the traits used.
99 NonPOD obj1(1, 2), obj2(3, 4), obj3(5, 6);
100 EXPECT_EQ(hash_combine(obj1, hash_combine(obj2, obj3)),
101 hash_value(std::make_pair(obj1, std::make_pair(obj2, obj3))));
102 }
103
104 TEST(HashingTest, HashValueStdString) {
105 std::string s = "Hello World!";
106 EXPECT_EQ(hash_combine_range(s.c_str(), s.c_str() + s.size()), hash_value(s));
107 EXPECT_EQ(hash_combine_range(s.c_str(), s.c_str() + s.size() - 1),
108 hash_value(s.substr(0, s.size() - 1)));
109 EXPECT_EQ(hash_combine_range(s.c_str() + 1, s.c_str() + s.size() - 1),
110 hash_value(s.substr(1, s.size() - 2)));
111
112 std::wstring ws = L"Hello Wide World!";
113 EXPECT_EQ(hash_combine_range(ws.c_str(), ws.c_str() + ws.size()),
114 hash_value(ws));
115 EXPECT_EQ(hash_combine_range(ws.c_str(), ws.c_str() + ws.size() - 1),
116 hash_value(ws.substr(0, ws.size() - 1)));
117 EXPECT_EQ(hash_combine_range(ws.c_str() + 1, ws.c_str() + ws.size() - 1),
118 hash_value(ws.substr(1, ws.size() - 2)));
119 }
120
121 template <typename T, size_t N> T *begin(T (&arr)[N]) { return arr; }
122 template <typename T, size_t N> T *end(T (&arr)[N]) { return arr + N; }
123
124 // Provide a dummy, hashable type designed for easy verification: its hash is
125 // the same as its value.
126 struct HashableDummy { size_t value; };
127 hash_code hash_value(HashableDummy dummy) { return dummy.value; }
128
129 TEST(HashingTest, HashCombineRangeBasicTest) {
130 // Leave this uninitialized in the hope that valgrind will catch bad reads.
131 int dummy;
132 hash_code dummy_hash = hash_combine_range(&dummy, &dummy);
133 EXPECT_NE(hash_code(0), dummy_hash);
134
135 const int arr1[] = { 1, 2, 3 };
136 hash_code arr1_hash = hash_combine_range(begin(arr1), end(arr1));
137 EXPECT_NE(dummy_hash, arr1_hash);
138 EXPECT_EQ(arr1_hash, hash_combine_range(begin(arr1), end(arr1)));
139
140 const std::vector<int> vec(begin(arr1), end(arr1));
141 EXPECT_EQ(arr1_hash, hash_combine_range(vec.begin(), vec.end()));
142
143 const std::list<int> list(begin(arr1), end(arr1));
144 EXPECT_EQ(arr1_hash, hash_combine_range(list.begin(), list.end()));
145
146 const std::deque<int> deque(begin(arr1), end(arr1));
147 EXPECT_EQ(arr1_hash, hash_combine_range(deque.begin(), deque.end()));
148
149 const int arr2[] = { 3, 2, 1 };
150 hash_code arr2_hash = hash_combine_range(begin(arr2), end(arr2));
151 EXPECT_NE(dummy_hash, arr2_hash);
152 EXPECT_NE(arr1_hash, arr2_hash);
153
154 const int arr3[] = { 1, 1, 2, 3 };
155 hash_code arr3_hash = hash_combine_range(begin(arr3), end(arr3));
156 EXPECT_NE(dummy_hash, arr3_hash);
157 EXPECT_NE(arr1_hash, arr3_hash);
158
159 const int arr4[] = { 1, 2, 3, 3 };
160 hash_code arr4_hash = hash_combine_range(begin(arr4), end(arr4));
161 EXPECT_NE(dummy_hash, arr4_hash);
162 EXPECT_NE(arr1_hash, arr4_hash);
163
164 const size_t arr5[] = { 1, 2, 3 };
165 const HashableDummy d_arr5[] = { {1}, {2}, {3} };
166 hash_code arr5_hash = hash_combine_range(begin(arr5), end(arr5));
167 hash_code d_arr5_hash = hash_combine_range(begin(d_arr5), end(d_arr5));
168 EXPECT_EQ(arr5_hash, d_arr5_hash);
169 }
170
171 TEST(HashingTest, HashCombineRangeLengthDiff) {
172 // Test that as only the length varies, we compute different hash codes for
173 // sequences.
174 std::map<size_t, size_t> code_to_size;
175 std::vector<char> all_one_c(256, '\xff');
176 for (unsigned Idx = 1, Size = all_one_c.size(); Idx < Size; ++Idx) {
177 hash_code code = hash_combine_range(&all_one_c[0], &all_one_c[0] + Idx);
178 std::map<size_t, size_t>::iterator
179 I = code_to_size.insert(std::make_pair(code, Idx)).first;
180 EXPECT_EQ(Idx, I->second);
181 }
182 code_to_size.clear();
183 std::vector<char> all_zero_c(256, '\0');
184 for (unsigned Idx = 1, Size = all_zero_c.size(); Idx < Size; ++Idx) {
185 hash_code code = hash_combine_range(&all_zero_c[0], &all_zero_c[0] + Idx);
186 std::map<size_t, size_t>::iterator
187 I = code_to_size.insert(std::make_pair(code, Idx)).first;
188 EXPECT_EQ(Idx, I->second);
189 }
190 code_to_size.clear();
191 std::vector<unsigned> all_one_int(512, -1);
192 for (unsigned Idx = 1, Size = all_one_int.size(); Idx < Size; ++Idx) {
193 hash_code code = hash_combine_range(&all_one_int[0], &all_one_int[0] + Idx);
194 std::map<size_t, size_t>::iterator
195 I = code_to_size.insert(std::make_pair(code, Idx)).first;
196 EXPECT_EQ(Idx, I->second);
197 }
198 code_to_size.clear();
199 std::vector<unsigned> all_zero_int(512, 0);
200 for (unsigned Idx = 1, Size = all_zero_int.size(); Idx < Size; ++Idx) {
201 hash_code code = hash_combine_range(&all_zero_int[0], &all_zero_int[0] + Idx);
202 std::map<size_t, size_t>::iterator
203 I = code_to_size.insert(std::make_pair(code, Idx)).first;
204 EXPECT_EQ(Idx, I->second);
205 }
206 }
207
208 TEST(HashingTest, HashCombineRangeGoldenTest) {
209 struct { const char *s; uint64_t hash; } golden_data[] = {
210 #if SIZE_MAX == UINT64_MAX || SIZE_MAX == UINT32_MAX
211 { "a", 0xaeb6f9d5517c61f8ULL },
212 { "ab", 0x7ab1edb96be496b4ULL },
213 { "abc", 0xe38e60bf19c71a3fULL },
214 { "abcde", 0xd24461a66de97f6eULL },
215 { "abcdefgh", 0x4ef872ec411dec9dULL },
216 { "abcdefghijklm", 0xe8a865539f4eadfeULL },
217 { "abcdefghijklmnopqrstu", 0x261cdf85faaf4e79ULL },
218 { "abcdefghijklmnopqrstuvwxyzabcdef", 0x43ba70e4198e3b2aULL },
219 { "abcdefghijklmnopqrstuvwxyzabcdef"
220 "abcdefghijklmnopqrstuvwxyzghijkl"
221 "abcdefghijklmnopqrstuvwxyzmnopqr"
222 "abcdefghijklmnopqrstuvwxyzstuvwx"
223 "abcdefghijklmnopqrstuvwxyzyzabcd", 0xdcd57fb2afdf72beULL },
224 { "a", 0xaeb6f9d5517c61f8ULL },
225 { "aa", 0xf2b3b69a9736a1ebULL },
226 { "aaa", 0xf752eb6f07b1cafeULL },
227 { "aaaaa", 0x812bd21e1236954cULL },
228 { "aaaaaaaa", 0xff07a2cff08ac587ULL },
229 { "aaaaaaaaaaaaa", 0x84ac949d54d704ecULL },
230 { "aaaaaaaaaaaaaaaaaaaaa", 0xcb2c8fb6be8f5648ULL },
231 { "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", 0xcc40ab7f164091b6ULL },
232 { "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
233 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
234 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
235 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
236 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", 0xc58e174c1e78ffe9ULL },
237 { "z", 0x1ba160d7e8f8785cULL },
238 { "zz", 0x2c5c03172f1285d7ULL },
239 { "zzz", 0x9d2c4f4b507a2ac3ULL },
240 { "zzzzz", 0x0f03b9031735693aULL },
241 { "zzzzzzzz", 0xe674147c8582c08eULL },
242 { "zzzzzzzzzzzzz", 0x3162d9fa6938db83ULL },
243 { "zzzzzzzzzzzzzzzzzzzzz", 0x37b9a549e013620cULL },
244 { "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz", 0x8921470aff885016ULL },
245 { "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
246 "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
247 "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
248 "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
249 "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz", 0xf60fdcd9beb08441ULL },
250 { "a", 0xaeb6f9d5517c61f8ULL },
251 { "ab", 0x7ab1edb96be496b4ULL },
252 { "aba", 0x3edb049950884d0aULL },
253 { "ababa", 0x8f2de9e73a97714bULL },
254 { "abababab", 0xee14a29ddf0ce54cULL },
255 { "ababababababa", 0x38b3ddaada2d52b4ULL },
256 { "ababababababababababa", 0xd3665364219f2b85ULL },
257 { "abababababababababababababababab", 0xa75cd6afbf1bc972ULL },
258 { "abababababababababababababababab"
259 "abababababababababababababababab"
260 "abababababababababababababababab"
261 "abababababababababababababababab"
262 "abababababababababababababababab", 0x840192d129f7a22bULL }
263 #else
264 #error This test only supports 64-bit and 32-bit systems.
265 #endif
266 };
267 for (unsigned i = 0; i < sizeof(golden_data)/sizeof(*golden_data); ++i) {
268 StringRef str = golden_data[i].s;
269 hash_code hash = hash_combine_range(str.begin(), str.end());
270 #if 0 // Enable this to generate paste-able text for the above structure.
271 std::string member_str = "\"" + str.str() + "\",";
272 fprintf(stderr, " { %-35s 0x%016llxULL },\n",
273 member_str.c_str(), static_cast<uint64_t>(hash));
274 #endif
275 EXPECT_EQ(static_cast<size_t>(golden_data[i].hash),
276 static_cast<size_t>(hash));
277 }
278 }
279
280 TEST(HashingTest, HashCombineBasicTest) {
281 // Hashing a sequence of homogenous types matches range hashing.
282 const int i1 = 42, i2 = 43, i3 = 123, i4 = 999, i5 = 0, i6 = 79;
283 const int arr1[] = { i1, i2, i3, i4, i5, i6 };
284 EXPECT_EQ(hash_combine_range(arr1, arr1 + 1), hash_combine(i1));
285 EXPECT_EQ(hash_combine_range(arr1, arr1 + 2), hash_combine(i1, i2));
286 EXPECT_EQ(hash_combine_range(arr1, arr1 + 3), hash_combine(i1, i2, i3));
287 EXPECT_EQ(hash_combine_range(arr1, arr1 + 4), hash_combine(i1, i2, i3, i4));
288 EXPECT_EQ(hash_combine_range(arr1, arr1 + 5),
289 hash_combine(i1, i2, i3, i4, i5));
290 EXPECT_EQ(hash_combine_range(arr1, arr1 + 6),
291 hash_combine(i1, i2, i3, i4, i5, i6));
292
293 // Hashing a sequence of heterogeneous types which *happen* to all produce the
294 // same data for hashing produces the same as a range-based hash of the
295 // fundamental values.
296 const size_t s1 = 1024, s2 = 8888, s3 = 9000000;
297 const HashableDummy d1 = { 1024 }, d2 = { 8888 }, d3 = { 9000000 };
298 const size_t arr2[] = { s1, s2, s3 };
299 EXPECT_EQ(hash_combine_range(begin(arr2), end(arr2)),
300 hash_combine(s1, s2, s3));
301 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(s1, s2, d3));
302 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(s1, d2, s3));
303 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(d1, s2, s3));
304 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(d1, d2, s3));
305 EXPECT_EQ(hash_combine(s1, s2, s3), hash_combine(d1, d2, d3));
306
307 // Permuting values causes hashes to change.
308 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i1, i1, i2));
309 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i1, i2, i1));
310 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i2, i1, i1));
311 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i2, i2, i1));
312 EXPECT_NE(hash_combine(i1, i1, i1), hash_combine(i2, i2, i2));
313 EXPECT_NE(hash_combine(i2, i1, i1), hash_combine(i1, i1, i2));
314 EXPECT_NE(hash_combine(i1, i1, i2), hash_combine(i1, i2, i1));
315 EXPECT_NE(hash_combine(i1, i2, i1), hash_combine(i2, i1, i1));
316
317 // Changing type w/o changing value causes hashes to change.
318 EXPECT_NE(hash_combine(i1, i2, i3), hash_combine((char)i1, i2, i3));
319 EXPECT_NE(hash_combine(i1, i2, i3), hash_combine(i1, (char)i2, i3));
320 EXPECT_NE(hash_combine(i1, i2, i3), hash_combine(i1, i2, (char)i3));
321
322 // This is array of uint64, but it should have the exact same byte pattern as
323 // an array of LargeTestIntegers.
324 const uint64_t bigarr[] = {
325 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL,
326 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL,
327 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL,
328 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL,
329 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL,
330 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL,
331 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL,
332 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL,
333 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL
334 };
335 // Hash a preposterously large integer, both aligned with the buffer and
336 // misaligned.
337 const LargeTestInteger li = { {
338 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL,
339 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL, 0xafafafafededededULL,
340 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL
341 } };
342 // Rotate the storage from 'li'.
343 const LargeTestInteger l2 = { {
344 0xacacacacbcbcbcbcULL, 0xccddeeffeeddccbbULL, 0xdeadbeafdeadbeefULL,
345 0xfefefefededededeULL, 0xafafafafededededULL, 0xffffeeeeddddccccULL,
346 0xaaaacbcbffffababULL, 0xaaaaaaaaababababULL
347 } };
348 const LargeTestInteger l3 = { {
349 0xccddeeffeeddccbbULL, 0xdeadbeafdeadbeefULL, 0xfefefefededededeULL,
350 0xafafafafededededULL, 0xffffeeeeddddccccULL, 0xaaaacbcbffffababULL,
351 0xaaaaaaaaababababULL, 0xacacacacbcbcbcbcULL
352 } };
353 EXPECT_EQ(hash_combine_range(begin(bigarr), end(bigarr)),
354 hash_combine(li, li, li));
355 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 9),
356 hash_combine(bigarr[0], l2));
357 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 10),
358 hash_combine(bigarr[0], bigarr[1], l3));
359 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 17),
360 hash_combine(li, bigarr[0], l2));
361 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 18),
362 hash_combine(li, bigarr[0], bigarr[1], l3));
363 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 18),
364 hash_combine(bigarr[0], l2, bigarr[9], l3));
365 EXPECT_EQ(hash_combine_range(bigarr, bigarr + 20),
366 hash_combine(bigarr[0], l2, bigarr[9], l3, bigarr[18], bigarr[19]));
367 }
368
369 TEST(HashingTest, HashCombineArgs18) {
370 // This tests that we can pass in up to 18 args.
371 #define CHECK_SAME(...) \
372 EXPECT_EQ(hash_combine(__VA_ARGS__), hash_combine(__VA_ARGS__))
373 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18);
374 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17);
375 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16);
376 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);
377 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14);
378 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13);
379 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12);
380 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11);
381 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
382 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8, 9);
383 CHECK_SAME(1, 2, 3, 4, 5, 6, 7, 8);
384 CHECK_SAME(1, 2, 3, 4, 5, 6, 7);
385 CHECK_SAME(1, 2, 3, 4, 5, 6);
386 CHECK_SAME(1, 2, 3, 4, 5);
387 CHECK_SAME(1, 2, 3, 4);
388 CHECK_SAME(1, 2, 3);
389 CHECK_SAME(1, 2);
390 CHECK_SAME(1);
391 #undef CHECK_SAME
392 }
393
394 }
The low level virtual machine