Add bitreverse LNT benchmark.

[jtony]

Summary

This patch implements 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.

For this specific benchmark, it is 3x faster with patches D33572 and D34908 (0.574s) than without them (1.919s).
[jtony@moose1 ~]$ time ./new.out
Sum1 = 0, Sum2 = feff800000800000
real 0m0.574s
user 0m0.574s
sys 0m0.000s
[jtony@moose1 ~]$ time ./old.out
Sum1 = 0, Sum2 = feff800000800000
real 0m1.919s
user 0m1.919s
sys 0m0.000s

This patch is requested by Hal Finkel.

[nemanjai]

SingleSource/Benchmarks/Misc/CMakeLists.txt

26 ↗

(On Diff #105798)

I don't follow why the name is revertBits when what you're doing is reversing the bits.

SingleSource/Benchmarks/Misc/revertBits.c

12 ↗

(On Diff #105798)

We had equivalently poor code gen for __builtin_bitreverse<N>. Don't we want this in the test case as well?

[jtony]

(1) Also test builtin_bitreverse32 and builtin_bitreverse64.
(2) Add the missing newline at the end of the second printf.

[jtony]

SingleSource/Benchmarks/Misc/revertBits.c

12 ↗

(On Diff #105798)

Yes, we want that too, it is added in the new patch.

[jtony]

Kindly ping.

[hfinkel]

SingleSource/Benchmarks/Misc/revertBits.c

35 ↗

(On Diff #105907)

Are you sure this doesn't signed overflow? Should we make this unsigned to avoid the possibility of UB.

37 ↗

(On Diff #105907)

The test suite is used with compilers other than Clang. You should guard this with __has_builtin using the pattern detailed here: https://clang.llvm.org/docs/LanguageExtensions.html#feature-checking-macros (it's probably fine for the test to just exit 0 if we're on a compiler without the builtin)

[jtony]

Address comments from Hal Finkel.

[hfinkel]

SingleSource/Benchmarks/Misc/revertBits.c

37 ↗

(On Diff #110901)

You need to put:

#ifndef __has_builtin
#define __has_builtin(x) 0
#endif

before this (or else this won't work with compilers that don't support __has_builtin).

[jtony]

Address one more new comment from Hal (add check for compilers that don't support __has_builtin)

[hfinkel]

LGTM

test-suite/trunk/SingleSource/Benchmarks/Misc/CMakeLists.txt

set(Source
   himenobmtxpa.c
   lowercase.c
   mandel-2.c
   mandel.c
   matmul_f64_4x4.c
   oourafft.c
   perlin.c
   pi.c
+  revertBits.c
   richards_benchmark.c
   salsa20.c
   whetstone.c
 )
 if(NOT ARCH STREQUAL "PowerPC" OR NOT TARGET_OS STREQUAL "Darwin")
   list(APPEND Source dt.c)
 endif()
 llvm_singlesource()

test-suite/trunk/SingleSource/Benchmarks/Misc/LICENSE.TXT

 (c) Copyright 1998 Painter Engineering, Inc.  See source file for
 license details.
 
 Pi
 ------------------------------------------------------------------------------
 This program is licensed under the LLVM license.  It was written by Don Shull
 and Mark Riordan.
 
+revertBits
+------------------------------------------------------------------------------
+This program is licensed under the LLVM license.  It was written by Tony Jiang.
+
 evalloop
 ------------------------------------------------------------------------------
 This is licensed under the Python Software Foundation License Version 2.
 See https://www.python.org/download/releases/2.7/license/

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>
+#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);
+  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);
+}
+
+int main (void) {
+  unsigned long long sum = 0;
+
+// 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");
+  return 0;
+#endif
+
+  for (int i = 0; i < NUM; ++i) {
+    sum += ReverseBits32(__builtin_bitreverse32(i));
+    sum -= ReverseBits64(__builtin_bitreverse64(i));
+  }
+  printf("Sum1 = %llx, ", sum);
+
+  for (int i = 0; i < NUM; ++i) {
+    sum -= ReverseBits64(ReverseBits64(0x100000000 + i));
+  }
+  printf("Sum2 = %llx\n", sum);
+
+  return 0;
+}

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

+Sum1 = 0, Sum2 = feff800000800000
+exit 0