[Support] Generic wrapper over __builtin_clz with cross-platform fallback

[nand]

Summary

Added CountLeadingZeros<T> for signed and unsigned types to count the number
of leading zeros. On platforms with __builtin_clz, the builtin is used, otherwise
a generic fallback is provided. Unlike __builtin_clz, the method returns the
bit width of the type for 0.

llvm/include/llvm/Support/MathExtras.h

#else
   // positive) divided by an argument compares to the other.
   if (IsNegative)
     return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY;
   else
     return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY;
 #endif
 }
 
+/// Returns the number of leading zeros. The number of leading zeros of 0 is
+/// the number of bits in of the underlying type.
+template <typename T>
+typename std::enable_if<std::is_unsigned<T>::value, unsigned>::type
+CountLeadingZeros(T V) {
+  constexpr unsigned BitWidth = sizeof(T) * CHAR_BIT;
+#if __has_builtin(__builtin_clzll)
+  if (!V)
+    return BitWidth;
+  unsigned LeadingZeros = __builtin_clzll(V);
+  constexpr auto FullBits = std::numeric_limits<unsigned long long>::digits;
+  return LeadingZeros - (FullBits - BitWidth);
+#else
+  for (unsigned I = 0; I < BitWidth; ++I) {
+    if (V & (T(1) << T(BitWidth - I - 1)))
+      return I;
+  }
+  return BitWidth;
+#endif
+}
+
+template <typename T>
+typename std::enable_if<std::is_signed<T>::value, unsigned>::type
+CountLeadingZeros(T Value) {
+    using U = typename std::make_unsigned<T>::type;
+    return Value < 0  ? 0 : CountLeadingZeros(static_cast<U>(Value));
+}
+
 } // End llvm namespace
 
 #endif

llvm/unittests/Support/MathExtrasTest.cpp

TYPED_TEST(OverflowTest, MulResultZero) {
   EXPECT_FALSE(MulOverflow<TypeParam>(-5, 0, Result));
   EXPECT_EQ(Result, TypeParam(0));
   EXPECT_FALSE(MulOverflow<TypeParam>(0, 5, Result));
   EXPECT_EQ(Result, TypeParam(0));
   EXPECT_FALSE(MulOverflow<TypeParam>(0, -5, Result));
   EXPECT_EQ(Result, TypeParam(0));
 }
 
+template <typename T>
+class CLZSignedTest : public ::testing::Test { };
+
+using CLZSignedTestTypes = ::testing::Types<int8_t, int16_t, int32_t, int64_t>;
+
+TYPED_TEST_CASE(CLZSignedTest, CLZSignedTestTypes);
+
+TYPED_TEST(CLZSignedTest, Zero)  {
+  EXPECT_EQ(sizeof(TypeParam) * CHAR_BIT, CountLeadingZeros<TypeParam>(0));
+}
+
+TYPED_TEST(CLZSignedTest, MinusOne)  {
+  EXPECT_EQ(0u, CountLeadingZeros(TypeParam(-1)));
+}
+
+TYPED_TEST(CLZSignedTest, Max) {
+  constexpr TypeParam MaxValue = std::numeric_limits<TypeParam>::max();
+  EXPECT_EQ(1u, CountLeadingZeros<TypeParam>(MaxValue));
+}
+
+template <typename T>
+class CLZUnsignedTest : public ::testing::Test { };
+
+using CLZUnsignedTestTypes = ::testing::Types<uint8_t, uint16_t, uint32_t,
+                                              uint64_t>;
+
+TYPED_TEST_CASE(CLZUnsignedTest, CLZUnsignedTestTypes);
+
+TYPED_TEST(CLZUnsignedTest, Zero)  {
+  EXPECT_EQ(sizeof(TypeParam) * CHAR_BIT, CountLeadingZeros<TypeParam>(0));
+}
+
+TYPED_TEST(CLZUnsignedTest, Max) {
+  constexpr TypeParam MaxValue = std::numeric_limits<TypeParam>::max();
+  EXPECT_EQ(0u, CountLeadingZeros<TypeParam>(MaxValue));
+}
+
+TEST(CLZSingleTest, CountLeadingZeros) {
+  EXPECT_EQ(1u, CountLeadingZeros<uint8_t>(127));
+  EXPECT_EQ(2u, CountLeadingZeros<uint8_t>(63));
+  EXPECT_EQ(9u, CountLeadingZeros<uint16_t>(127));
+  EXPECT_EQ(10u, CountLeadingZeros<uint16_t>(63));
+  EXPECT_EQ(25u, CountLeadingZeros<uint32_t>(127));
+  EXPECT_EQ(26u, CountLeadingZeros<uint32_t>(63));
+  EXPECT_EQ(57u, CountLeadingZeros<uint64_t>(127));
+  EXPECT_EQ(58u, CountLeadingZeros<uint64_t>(63));
+}
+
 } // namespace