Add benchmarks for 128 bit division and create a directory for all builtins benchmarks

[danlark]

Summary

Preliminary to https://reviews.llvm.org/D81809

[danlark]

Remove unnecessary header

[courbet]

MicroBenchmarks/Builtins/Int128/main.cpp

17

Why is the default mt19937 not fine ? (please add a comment)

26

Could we make H a provate typedef inside the class ? (It's not used outside, and I don;t see any specialization)

39

H looks unused.

41

Can you add some doc ?

62

Use kSampleSize instead of values.size() for more accurate results (the DoNotOptimize call above will likely force the compiler to recompute the size at every iteration).

Also it would be better to make kSampleSize a power of two and do: i = (i+1)%kSampleSize to avoid the branch altogether.

67

why not __uint128_t ?

[danlark]

Fix comments

MicroBenchmarks/Builtins/Int128/main.cpp

17

You are right, does not matter

[danlark]

Could you submit it for me? I don't have commit rights for now. [e-mail]

[MaskRay]

MicroBenchmarks/Builtins/Int128/main.cpp

42

What if a=b=1? max(a,b) < max(2,min(a,b))

[MaskRay]

MicroBenchmarks/Builtins/Int128/CMakeLists.txt

2

You can set 14 because LLVM requires 14 now..
MSVC friendly alternative:

set(CMAKE_CXX_STANDARD 14)
set(CMAKE_CXX_STANDARD_REQUIRED TRUE)

[danlark]

Fix comments

[danlark]

MicroBenchmarks/Builtins/Int128/main.cpp

42

The probability of that is 2^{-254} (a <= 1 and b <= 1) and it does not matter at that point, overall updated to match the comment

[danlark]

Fix

[MaskRay]

Thanks!

[danlark]

879f4962e83f98863c83e385e956d579e131791f

MicroBenchmarks/Builtins/CMakeLists.txt

+add_subdirectory(Int128)

MicroBenchmarks/Builtins/Int128/CMakeLists.txt

+set(CMAKE_CXX_STANDARD 14)
+set(CMAKE_CXX_STANDARD_REQUIRED TRUE)
+
+llvm_test_run(WORKDIR ${CMAKE_CURRENT_BINARY_DIR})
+
+llvm_test_executable(Builtins main.cpp)
+
+target_link_libraries(Builtins benchmark)

MicroBenchmarks/Builtins/Int128/main.cpp

+#include <algorithm>
+#include <cstdint>
+#include <limits>
+#include <random>
+#include <type_traits>
+#include <vector>
+
+#include "benchmark/benchmark.h"
+
+#if defined(__SIZEOF_INT128__)
+
+namespace {
+
+constexpr size_t kSampleSize = 1 << 20;
+
+// Some implementations of <random> do not support __int128_t when it is
+// available, so we make our own uniform_int_distribution-like type.
+template <typename T>
+class UniformIntDistribution128 {
+ public:
+  T operator()(std::mt19937& generator) {
+    return (static_cast<T>(dist64_(generator)) << 64) | dist64_(generator);
+  }
+
+ private:
+  using H = typename std::conditional<
+              std::is_same<T, __int128_t>::value, int64_t, uint64_t>::type;
+  std::uniform_int_distribution<H> dist64_;
+};
+
+// Generates uniformly pairs (a, b) of 128-bit integers such as a >= b.
+template <typename T>
+std::vector<std::pair<T, T>> GetRandomIntrinsic128SampleUniformDivisor() {
+  std::vector<std::pair<T, T>> values;
+  std::mt19937 random;
+  UniformIntDistribution128<T> uniform_128;
+  values.reserve(kSampleSize);
+  for (size_t i = 0; i < kSampleSize; ++i) {
+    T a = uniform_128(random);
+    T b = uniform_128(random);
+    values.emplace_back(std::max(static_cast<T>(2), std::max(a, b)),
+                        std::max(static_cast<T>(2), std::min(a, b)));
+  }
+  return values;
+}
+
+template <typename T>
+void BM_DivideIntrinsic128UniformDivisor(benchmark::State& state) {
+  auto values = GetRandomIntrinsic128SampleUniformDivisor<T>();
+  size_t i = 0;
+  for (const auto _ : state) {
+    benchmark::DoNotOptimize(values[i].first / values[i].second);
+    i = (i + 1) % kSampleSize;
+  }
+}
+BENCHMARK_TEMPLATE(BM_DivideIntrinsic128UniformDivisor, __uint128_t);
+BENCHMARK_TEMPLATE(BM_DivideIntrinsic128UniformDivisor, __int128_t);
+
+template <typename T>
+void BM_RemainderIntrinsic128UniformDivisor(benchmark::State& state) {
+  auto values = GetRandomIntrinsic128SampleUniformDivisor<T>();
+  size_t i = 0;
+  for (const auto _ : state) {
+    benchmark::DoNotOptimize(values[i].first % values[i].second);
+    i = (i + 1) % kSampleSize;
+  }
+}
+BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128UniformDivisor, __uint128_t);
+BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128UniformDivisor, __int128_t);
+
+// Generates random pairs of (a, b) where a >= b, a is 128-bit and
+// b is 64-bit.
+template <typename T, typename H = typename std::conditional<
+              std::is_same<T, __int128_t>::value, int64_t, uint64_t>::type>
+std::vector<std::pair<T, H>> GetRandomIntrinsic128SampleSmallDivisor() {
+  std::vector<std::pair<T, H>> values;
+  std::mt19937 random;
+  UniformIntDistribution128<T> uniform_int128;
+  std::uniform_int_distribution<H> uniform_int64;
+  values.reserve(kSampleSize);
+  for (size_t i = 0; i < kSampleSize; ++i) {
+    T a = uniform_int128(random);
+    H b = std::max(H{2}, uniform_int64(random));
+    values.emplace_back(std::max(a, static_cast<T>(b)), b);
+  }
+  return values;
+}
+
+template <typename T>
+void BM_DivideIntrinsic128SmallDivisor(benchmark::State& state) {
+  auto values = GetRandomIntrinsic128SampleSmallDivisor<T>();
+  size_t i = 0;
+  for (const auto _ : state) {
+    benchmark::DoNotOptimize(values[i].first / values[i].second);
+    i = (i + 1) % kSampleSize;
+  }
+}
+BENCHMARK_TEMPLATE(BM_DivideIntrinsic128SmallDivisor, __uint128_t);
+BENCHMARK_TEMPLATE(BM_DivideIntrinsic128SmallDivisor, __int128_t);
+
+template <typename T>
+void BM_RemainderIntrinsic128SmallDivisor(benchmark::State& state) {
+  auto values = GetRandomIntrinsic128SampleSmallDivisor<T>();
+  size_t i = 0;
+  for (const auto _ : state) {
+    benchmark::DoNotOptimize(values[i].first % values[i].second);
+    i = (i + 1) % kSampleSize;
+  }
+}
+BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128SmallDivisor, __uint128_t);
+BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128SmallDivisor, __int128_t);
+
+}  // namespace
+
+#endif
+
+BENCHMARK_MAIN();

MicroBenchmarks/CMakeLists.txt

 file(COPY lit.local.cfg DESTINATION ${CMAKE_CURRENT_BINARY_DIR})
 
 add_subdirectory(libs)
 add_subdirectory(XRay)
 add_subdirectory(LCALS)
 add_subdirectory(harris)
 add_subdirectory(ImageProcessing)
 add_subdirectory(LoopInterchange)
 add_subdirectory(MemFunctions)
+add_subdirectory(Builtins)