[test-suite] Update bitreverse benchmark.

[nemanjai]

With the above changes to the test case (and the corresponding changes to the reference output), the problem would have been blatantly obvious from the start and we wouldn't have to jump through hoops to ensure opt isn't just giving us the right answer.

SingleSource/Benchmarks/Misc/revertBits.c

42 ↗

(On Diff #119174)

I believe the focus in a test case such as this should be not only on ensuring the faster code-gen, but on functional correctness.
To that end, it would be preferable to have 4 print statements here that will reverse a rather obvious pattern in various ways.
For example:

unsigned int Rev32 = strtoll("0x11223344", NULL, 16);
unsigned long long Rev64 = strtoll("0x1122334455667788", NULL, 16);
printf("0x%X -> 0x%X\n", Rev32, ReverseBits32(Rev32));
printf("0x%llX -> 0x%llX\n", Rev64, ReverseBits64(Rev64));

45 ↗

(On Diff #119174)

Here' we'd just print the expected values:

printf("0x%X -> 0x%X\n", Rev32, ReverseBits32(Rev32));
printf("0x%llX -> 0x%llX\n", Rev64, ReverseBits64(Rev64));

48 ↗

(On Diff #119174)

And here, we'd generate the values using the builtin:

printf("0x%X -> 0x%X\n", Rev32, __builtin_bitreverse32(Rev32));
printf("0x%llX -> 0x%llX\n", Rev64, __builtin_bitreverse64(Rev64));

SingleSource/Benchmarks/Misc/revertBits.reference_output

1 ↗

(On Diff #119174)

As I mentioned before, I would very much prefer that this test case include an obvious, easily verifiable functional test. See above.

[MaskRay]

Add an easily verifiable functional test.

[jtony]

SingleSource/Benchmarks/Misc/revertBits.c

36 ↗

(On Diff #119489)

Changing the type from long long to int here is probably not safe. Since we are calculating the summation of 0x1000000 reversed numbers. Without reversing them, the total sum would definitely overflow an integer ((1+0x1000000)* 0x1000000/2). With reversing, I don't calculate, but we'd better leave it to long long for safety.

42 ↗

(On Diff #119174)

I agree with Nemanja here. Some obvious functional testing is necessary.

[MaskRay]

Change int -> unsigned

[MaskRay]

SingleSource/Benchmarks/Misc/revertBits.c

42 ↗

(On Diff #119174)

There is another issue. ReverseBits32/64 should use unsigned types.

Updated

[nemanjai]

LGTM.

[MatzeB]

While the change itself makes sense:

• Please give some more descriptions than "update test" in the future.
• Also give a warning in the commit message as this changes performance and will show up in the LNT numbers.

[MaskRay]

In D38962#910832, @MatzeB wrote:

While the change itself makes sense:

• Please give some more descriptions than "update test" in the future.
• Also give a warning in the commit message as this changes performance and will show up in the LNT numbers.

Thanks! I did not know LNT ( http://llvm.org/docs/lnt/quickstart.html ) before.

[MatzeB]

We also have a live installation at http://lnt.llvm.org
A few of our buildbots submit data there.

test-suite/trunk/SingleSource/Benchmarks/Misc/revertBits.c

 /*
  * A performance regression test for bit reverse. The bit reverse algorithm on
  * PPC was O(N) and had lots of dependency between contiguous instructions. We
  * replace it with a faster O(lgN) algorithm in the following two patches:
  * https://reviews.llvm.org/D33572
  * https://reviews.llvm.org/D34908
  * This test case tests both the 32-bit and 64-bit bit reverse to ensure the
  * new implementation is functionally correct and has a better performance.
  */
 #include <stdio.h>
+#include <stdlib.h>
+
 #define NUM 0x1000000
-int __attribute__((noinline)) ReverseBits32(int n) {
-  n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1);
-  n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);
-  n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
+
+unsigned __attribute__((noinline)) ReverseBits32(unsigned n) {
+  n = ((n >> 1) & 0x55555555u) | ((n & 0x55555555u) << 1);
+  n = ((n >> 2) & 0x33333333u) | ((n & 0x33333333u) << 2);
+  n = ((n >> 4) & 0x0F0F0F0Fu) | ((n & 0x0F0F0F0Fu) << 4);
   return ((n & 0xff000000u) >> 24) | ((n & 0x00ff0000u) >> 8) |
          ((n & 0x0000ff00u) << 8) | ((n & 0x000000ffu) << 24);
 }
 
-long long __attribute__((noinline)) ReverseBits64(long long n) {
-  n = ((n >> 1) & 0x5555555555555555L) | ((n & 0x5555555555555555L) << 1);
-  n = ((n >> 2) & 0x3333333333333333L) | ((n & 0x3333333333333333L) << 2);
-  n = ((n >> 4) & 0x0F0F0F0F0F0F0F0FL) | ((n & 0x0F0F0F0F0F0F0F0FL) << 4);
-  return ((n & 0xFF00000000000000L) >> 56) |
-         ((n & 0x00FF000000000000L) >> 40) |
-         ((n & 0x0000FF0000000000L) >> 24) |
-         ((n & 0x000000FF00000000L) >> 8)  |
-         ((n & 0x00000000000000FFL) << 56) |
-         ((n & 0x000000000000FF00L) << 40) |
-         ((n & 0x0000000000FF0000L) << 24) |
-         ((n & 0x00000000FF000000L) << 8);
+unsigned long long __attribute__((noinline)) ReverseBits64(unsigned long long n) {
+  n = ((n >> 1) & 0x5555555555555555ull) | ((n & 0x5555555555555555ull) << 1);
+  n = ((n >> 2) & 0x3333333333333333ull) | ((n & 0x3333333333333333ull) << 2);
+  n = ((n >> 4) & 0x0F0F0F0F0F0F0F0Full) | ((n & 0x0F0F0F0F0F0F0F0Full) << 4);
+  return ((n & 0xFF00000000000000ull) >> 56) |
+         ((n & 0x00FF000000000000ull) >> 40) |
+         ((n & 0x0000FF0000000000ull) >> 24) |
+         ((n & 0x000000FF00000000ull) >> 8)  |
+         ((n & 0x00000000000000FFull) << 56) |
+         ((n & 0x000000000000FF00ull) << 40) |
+         ((n & 0x0000000000FF0000ull) << 24) |
+         ((n & 0x00000000FF000000ull) << 8);
 }
 
 int main (void) {
-  unsigned long long sum = 0;
+  unsigned long long sum32 = 0, sum64 = 0;
+  unsigned int rev32 = strtoll("0x12345678", NULL, 16);
+  unsigned long long rev64 = strtoll("0x0123456789012345", NULL, 16);
 
 // Check for compilers that don't support __has_builtin
 #ifndef __has_builtin
 #define __has_builtin(x) 0
 #endif
 
 // Check for compilers that support __has_builtin but not __builtin_bitreverse*
 #if (!__has_builtin(__builtin_bitreverse32) ||\
      !__has_builtin(__builtin_bitreverse64))
-  printf("Sum1 = 0, Sum2 = feff800000800000\n");
+  printf("0x%x -> 0x%x\n", rev32, ReverseBits32(rev32));
+  printf("0x%llx -> 0x%llx\n", rev64, ReverseBits64(rev64));
   return 0;
 #else
 
   for (int i = 0; i < NUM; ++i) {
-    sum += ReverseBits32(__builtin_bitreverse32(i));
-    sum -= ReverseBits64(__builtin_bitreverse64(i));
+    sum32 += ReverseBits32(i);
+    sum64 += ReverseBits64(i);
   }
-  printf("Sum1 = %llx, ", sum);
-
   for (int i = 0; i < NUM; ++i) {
-    sum -= ReverseBits64(ReverseBits64(0x100000000 + i));
+    sum32 -= __builtin_bitreverse32(i);
+    sum64 -= __builtin_bitreverse64(i);
   }
-  printf("Sum2 = %llx\n", sum);
-
-  return 0;
+  printf("0x%x -> 0x%x\n", rev32, __builtin_bitreverse32(rev32));
+  printf("0x%llx -> 0x%llx\n", rev64, __builtin_bitreverse64(rev64));
+  return sum32 == 0 && sum64 == 0 ? 0 : 1;
 #endif
 }

test-suite/trunk/SingleSource/Benchmarks/Misc/revertBits.reference_output

-Sum1 = 0, Sum2 = feff800000800000
+0x12345678 -> 0x1e6a2c48
+0x123456789012345 -> 0xa2c48091e6a2c480
 exit 0