[Support] Add optional argument to SaturatingAdd() and SaturatingMultiply() to indicate that overflow occurred

Summary: Adds the ability for callers to detect when saturation occurred on the result of saturating addition/multiplication.

Reviewers: davidxl, silvas, rsmith

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D14931

llvm-svn: 253921

2 files changed, 90 insertions, 8 deletions

diff --git a/llvm/include/llvm/Support/MathExtras.h b/llvm/include/llvm/Support/MathExtras.h
index d853e8a21e4..0d0a2efa7ad 100644
--- a/llvm/include/llvm/Support/MathExtras.h
+++ b/llvm/include/llvm/Support/MathExtras.h
@@ -655,46 +655,79 @@ inline int64_t SignExtend64(uint64_t X, unsigned B) {
 
 /// \brief Add two unsigned integers, X and Y, of type T.
 /// Clamp the result to the maximum representable value of T on overflow.
+/// ResultOverflowed indicates if the result is larger than the maximum
+/// representable value of type T.
 template <typename T>
 typename std::enable_if<std::is_unsigned<T>::value, T>::type
-SaturatingAdd(T X, T Y) {
+SaturatingAdd(T X, T Y, bool &ResultOverflowed) {
   // Hacker's Delight, p. 29
   T Z = X + Y;
-  if (Z < X || Z < Y)
+  ResultOverflowed = (Z < X || Z < Y);
+  if (ResultOverflowed)
     return std::numeric_limits<T>::max();
   else
     return Z;
 }
 
+/// \brief Add 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
+SaturatingAdd(T X, T Y) {
+  bool ResultOverflowed;
+  return SaturatingAdd(X, Y, ResultOverflowed);
+}
+
 /// \brief Multiply two unsigned integers, X and Y, of type T.
 /// Clamp the result to the maximum representable value of T on overflow.
+/// ResultOverflowed indicates if the result is larger than the maximum
+/// representable value of type T.
 template <typename T>
 typename std::enable_if<std::is_unsigned<T>::value, T>::type
-SaturatingMultiply(T X, T Y) {
+SaturatingMultiply(T X, T Y, bool &ResultOverflowed) {
   // 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.
 
+  ResultOverflowed = false;
+
   // 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)
+  if (Log2Z < Log2Max) {
     return X * Y;
-  if (Log2Z > Log2Max)
+  }
+  if (Log2Z > Log2Max) {
+    ResultOverflowed = true;
     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))
+  if (Z & ~(Max >> 1)) {
+    ResultOverflowed = true;
     return Max;
+  }
   Z <<= 1;
-  return (X & 1) ? SaturatingAdd(Z, Y) : Z;
+  if (X & 1)
+    return SaturatingAdd(Z, Y, ResultOverflowed);
+
+  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) {
+  bool ResultOverflowed;
+  return SaturatingMultiply(X, Y, ResultOverflowed);
 }
 
 extern const float huge_valf;
diff --git a/llvm/unittests/Support/MathExtrasTest.cpp b/llvm/unittests/Support/MathExtrasTest.cpp
index fa12f750407..ee2fc1b9034 100644
--- a/llvm/unittests/Support/MathExtrasTest.cpp
+++ b/llvm/unittests/Support/MathExtrasTest.cpp
@@ -194,10 +194,27 @@ template<typename T>
 void SaturatingAddTestHelper()
 {
   const T Max = std::numeric_limits<T>::max();
+  bool ResultOverflowed;
+
   EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2)));
+  EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2), ResultOverflowed));
+  EXPECT_FALSE(ResultOverflowed);
+
   EXPECT_EQ(Max, SaturatingAdd(Max, T(1)));
+  EXPECT_EQ(Max, SaturatingAdd(Max, T(1), ResultOverflowed));
+  EXPECT_TRUE(ResultOverflowed);
+
+  EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1)));
+  EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1), ResultOverflowed));
+  EXPECT_FALSE(ResultOverflowed);
+
   EXPECT_EQ(Max, SaturatingAdd(T(1), Max));
+  EXPECT_EQ(Max, SaturatingAdd(T(1), Max, ResultOverflowed));
+  EXPECT_TRUE(ResultOverflowed);
+
   EXPECT_EQ(Max, SaturatingAdd(Max, Max));
+  EXPECT_EQ(Max, SaturatingAdd(Max, Max, ResultOverflowed));
+  EXPECT_TRUE(ResultOverflowed);
 }
 
 TEST(MathExtras, SaturatingAdd) {
@@ -211,22 +228,50 @@ template<typename T>
 void SaturatingMultiplyTestHelper()
 {
   const T Max = std::numeric_limits<T>::max();
+  bool ResultOverflowed;
 
   // Test basic multiplication.
   EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3)));
+  EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3), ResultOverflowed));
+  EXPECT_FALSE(ResultOverflowed);
+
   EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2)));
+  EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2), ResultOverflowed));
+  EXPECT_FALSE(ResultOverflowed);
 
   // Test multiplication by zero.
   EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0)));
+  EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0), ResultOverflowed));
+  EXPECT_FALSE(ResultOverflowed);
+
   EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0)));
+  EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0), ResultOverflowed));
+  EXPECT_FALSE(ResultOverflowed);
+
   EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1)));
+  EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1), ResultOverflowed));
+  EXPECT_FALSE(ResultOverflowed);
+
   EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0)));
+  EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0), ResultOverflowed));
+  EXPECT_FALSE(ResultOverflowed);
+
   EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max));
+  EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max, ResultOverflowed));
+  EXPECT_FALSE(ResultOverflowed);
 
   // Test multiplication by maximum value.
   EXPECT_EQ(Max, SaturatingMultiply(Max, T(2)));
-  EXPECT_EQ(Max, SaturatingMultiply(T(2),Max));
+  EXPECT_EQ(Max, SaturatingMultiply(Max, T(2), ResultOverflowed));
+  EXPECT_TRUE(ResultOverflowed);
+
+  EXPECT_EQ(Max, SaturatingMultiply(T(2), Max));
+  EXPECT_EQ(Max, SaturatingMultiply(T(2), Max, ResultOverflowed));
+  EXPECT_TRUE(ResultOverflowed);
+
   EXPECT_EQ(Max, SaturatingMultiply(Max, Max));
+  EXPECT_EQ(Max, SaturatingMultiply(Max, Max, ResultOverflowed));
+  EXPECT_TRUE(ResultOverflowed);
 
   // Test interesting boundary conditions for algorithm -
   // ((1 << A) - 1) * ((1 << B) + K) for K in [-1, 0, 1]
@@ -241,8 +286,12 @@ void SaturatingMultiplyTestHelper()
 
       if(OverflowExpected) {
         EXPECT_EQ(Max, SaturatingMultiply(X, Y));
+        EXPECT_EQ(Max, SaturatingMultiply(X, Y, ResultOverflowed));
+        EXPECT_TRUE(ResultOverflowed);
       } else {
         EXPECT_EQ(X * Y, SaturatingMultiply(X, Y));
+        EXPECT_EQ(X * Y, SaturatingMultiply(X, Y, ResultOverflowed));
+        EXPECT_FALSE(ResultOverflowed);
       }
     }
   }