[Support] Fix SaturatingMultiply<T>() to be correct (and fast), Re-enable Unit Tests

[slingn]

Summary

This change fixes the SaturatingMultiply<T>() function template to not cause undefined behavior with T=uint16_t.
Thanks to Richard Smith's contribution, it also no longer requires an integer division.

Patch by Richard Smith.

[davidxl]

Is there a bug in UBSan?

[davidxl]

integer division is expensive. I wonder if we can take some fast path to by pass it

T Upper = Max >> (sizeof(T)*4);
if (X <= Upper && Y <= Upper)

return X * Y;

// regular stuff

[slingn]

https://llvm.org/bugs/show_bug.cgi?id=25580

Apparently not a bug with UBSan - there was a valid problem with signed integer overflow due to up-conversion of integer types with the previous implementation.

[davidxl]

ok makes sense.

[davidxl]

If you have time, finding a way to speed up the method will be welcome (such as the fast path suggestion).

[rsmith]

See the patch I posted on the other thread for this issue -- that should
avoid the UB and the division in all cases.

[slingn]

Updated with Richard Smith's patch for SaturatingMultiply().

[davidxl]

neat - count leading zeros instructions is very fast on intel platforms. The implementation completely removed the need for idiv.

[rsmith]

unittests/Support/MathExtrasTest.cpp

220 ↗

(On Diff #40803)

It'd be useful to also test cases like ((1 << A) - 1) * ((1 << B) + K), for K in [-1, 0, 1] and A + B == numeric_limits<T>::digits, as those are interesting transition cases for the new algorithm (you get overflow iff A > B and K = 1). More generally, testcases where overflow almost happens or only just happens would be good here.

Also, coverage for 0 * Max and 0 * 0 would be good.

[slingn]

Added unit tests based on rsmith's suggestions.

[davidxl]

lgtm.

llvm/trunk/include/llvm/Support/MathExtras.h

else
     return Z;
 }
 
 /// \brief Multiply two unsigned integers, X and Y, of type T.
 /// Clamp the result to the maximum representable value of T on overflow.
 template <typename T>
 typename std::enable_if<std::is_unsigned<T>::value, T>::type
 SaturatingMultiply(T X, T Y) {
-  // Hacker's Delight, p. 30
-  T Z = X * Y;
-  if (Y != 0 && Z / Y != X)
-    return std::numeric_limits<T>::max();
-  else
-    return Z;
+  // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
+  // because it fails for uint16_t (where multiplication can have undefined
+  // behavior due to promotion to int), and requires a division in addition
+  // to the multiplication.
+
+  // Log2(Z) would be either Log2Z or Log2Z + 1.
+  // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
+  // will necessarily be less than Log2Max as desired.
+  int Log2Z = Log2_64(X) + Log2_64(Y);
+  const T Max = std::numeric_limits<T>::max();
+  int Log2Max = Log2_64(Max);
+  if (Log2Z < Log2Max)
+    return X * Y;
+  if (Log2Z > Log2Max)
+    return Max;
+
+  // We're going to use the top bit, and maybe overflow one
+  // bit past it. Multiply all but the bottom bit then add
+  // that on at the end.
+  T Z = (X >> 1) * Y;
+  if (Z & ~(Max >> 1))
+    return Max;
+  Z <<= 1;
+  return (X & 1) ? SaturatingAdd(Z, Y) : Z;
 }
 
 extern const float huge_valf;
 } // End llvm namespace
 
 #endif

llvm/trunk/unittests/Support/MathExtrasTest.cpp

 
 TEST(MathExtras, SaturatingAdd) {
   SaturatingAddTestHelper<uint8_t>();
   SaturatingAddTestHelper<uint16_t>();
   SaturatingAddTestHelper<uint32_t>();
   SaturatingAddTestHelper<uint64_t>();
 }
 
+template<typename T>
+void SaturatingMultiplyTestHelper()
+{
+  const T Max = std::numeric_limits<T>::max();
+
+  // Test basic multiplication.
+  EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3)));
+  EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2)));
+
+  // Test multiplication by zero.
+  EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0)));
+  EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0)));
+  EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1)));
+  EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0)));
+  EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max));
+
+  // Test multiplication by maximum value.
+  EXPECT_EQ(Max, SaturatingMultiply(Max, T(2)));
+  EXPECT_EQ(Max, SaturatingMultiply(T(2),Max));
+  EXPECT_EQ(Max, SaturatingMultiply(Max, Max));
+
+  // Test interesting boundary conditions for algorithm -
+  // ((1 << A) - 1) * ((1 << B) + K) for K in [-1, 0, 1]
+  // and A + B == std::numeric_limits<T>::digits.
+  // We expect overflow iff A > B and K = 1.
+  const int Digits = std::numeric_limits<T>::digits;
+  for (int A = 1, B = Digits - 1; B >= 1; ++A, --B) {
+    for (int K = -1; K <= 1; ++K) {
+      T X = (T(1) << A) - T(1);
+      T Y = (T(1) << B) + K;
+      bool OverflowExpected = A > B && K == 1;
+
+      if(OverflowExpected) {
+        EXPECT_EQ(Max, SaturatingMultiply(X, Y));
+      } else {
+        EXPECT_EQ(X * Y, SaturatingMultiply(X, Y));
+      }
+    }
+  }
+}
+
+TEST(MathExtras, SaturatingMultiply) {
+  SaturatingMultiplyTestHelper<uint8_t>();
+  SaturatingMultiplyTestHelper<uint16_t>();
+  SaturatingMultiplyTestHelper<uint32_t>();
+  SaturatingMultiplyTestHelper<uint64_t>();
+}
+
 }