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

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

SingleSource/Benchmarks/Misc/revertBits.c

13

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

13

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

[jtony]

Kindly ping.

[hfinkel]

SingleSource/Benchmarks/Misc/revertBits.c

36

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

38

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

38

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

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()

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/

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;
+}

SingleSource/Benchmarks/Misc/revertBits.reference_output

+Sum1 = 0, Sum2 = feff800000800000
+exit 0