[Support] Added overflow checking add, sub and mul.

[nand]

Summary

Added AddOverflow, SubOverflow and MulOverflow to compute truncated results and return a flag indicating whether overflow occured.

[jfb]

Can you confirm that the tests pass with UBSan enabled?

llvm/include/llvm/Support/MathExtras.h

862

I think you want to have T1 X, T2 Y and enable_if::<is_same<T1, T2>::value since you're trying to avoid promotions entirely.

I'd also rather return a pair or a struct with named values instead of having a reference return value, and make the result nodiscard.

870

We have bit_cast in ADT/bit.h if that's what you meant to use. I think you meant static_cast thought :)

llvm/unittests/Support/MathExtrasTest.cpp

474

You probably want signed char instead of char.

[lebedev.ri]

llvm/include/llvm/Support/MathExtras.h

783–786

Do you want to also refactor the functions that already used that checking at the same time?

[nand]

llvm/include/llvm/Support/MathExtras.h

783–786

Unfortunately, I would like to avoid any refactoring in this diff.

862

I would like to keep these functions simple so at some point we might make them straightforward wrappers over __builtin_add_overflow etc, reason why I would like to keep this signature. Promotions can be handled on the callee's side. For my use case, I always want to explicitly specify the template parameter type.

Regarding struct returns, that sounds like a use case for a class such as CheckedInt/SafeInt etc, which doesn't seem to be required yet. A future implementation might use these methods though.

870

If the sizes match, doesn't static cast simply move the number bit by bit to the result? I have adjusted the comment.

[nand]

Updated comments about bitcast

[nand]

Just checked: tests pass with UBSan.

[nand]

s/char/signed char/

[nand]

replaced char with signed char

[jfb]

llvm/include/llvm/Support/MathExtras.h

862

OK seeing this as the base helper SGTM.

You probably still want nodiscard however.

[nand]

llvm/include/llvm/Support/MathExtras.h

862

This method is the only way to compute the result of overflow - if we know overflow happens, we might not want to look at the return flag at all.

[jfb]

llvm/include/llvm/Support/MathExtras.h

862

That sounds good!

[jfb]

http://llvm.org/r367470

llvm/include/llvm/Support/MathExtras.h

 /// 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, bool *ResultOverflowed = nullptr) {
   bool Dummy;
   bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
   // Hacker's Delight, p. 29
   T Z = X + Y;
   Overflowed = (Z < X || Z < Y);
   if (Overflowed)
     return std::numeric_limits<T>::max();
   else
     return Z;
 }
 
 /// 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.
SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
   if (Overflowed)
     return Product;
 
   return SaturatingAdd(A, Product, &Overflowed);
 }
 
 /// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
 extern const float huge_valf;
+
+
+/// Add two signed integers, computing the two's complement truncated result,
+/// returning true if overflow occured.
+template <typename T>
+typename std::enable_if<std::is_signed<T>::value, T>::type
+AddOverflow(T X, T Y, T &Result) {
+  // Perform the unsigned addition.
+  using U = typename std::make_unsigned<T>::type;
+  const U UX = static_cast<U>(X);
+  const U UY = static_cast<U>(Y);
+  const U UResult = UX + UY;
+
+  // Bitcast to signed.
+  Result = static_cast<T>(UResult);
+
+  // Adding two positive numbers should result in a positive number.
+  if (X > 0 && Y > 0)
+    return Result <= 0;
+  // Adding two negatives should result in a negative number.
+  if (X < 0 && Y < 0)
+    return Result >= 0;
+  return false;
+}
+
+/// Subtract two signed integers, computing the two's complement truncated
+/// result, returning true if an overflow ocurred.
+template <typename T>
+typename std::enable_if<std::is_signed<T>::value, T>::type
+SubOverflow(T X, T Y, T &Result) {
+  // Perform the unsigned addition.
+  using U = typename std::make_unsigned<T>::type;
+  const U UX = static_cast<U>(X);
+  const U UY = static_cast<U>(Y);
+  const U UResult = UX - UY;
+
+  // Bitcast to signed.
+  Result = static_cast<T>(UResult);
+
+  // Subtracting a positive number from a negative results in a negative number.
+  if (X <= 0 && Y > 0)
+    return Result >= 0;
+  // Subtracting a negative number from a positive results in a positive number.
+  if (X >= 0 && Y < 0)
+    return Result <= 0;
+  return false;
+}
+
+
+/// Multiply two signed integers, computing the two's complement truncated
+/// result, returning true if an overflow ocurred.
+template <typename T>
+typename std::enable_if<std::is_signed<T>::value, T>::type
+MulOverflow(T X, T Y, T &Result) {
+  // Perform the unsigned multiplication on absolute values.
+  using U = typename std::make_unsigned<T>::type;
+  const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X);
+  const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y);
+  const U UResult = UX * UY;
+
+  // Convert to signed.
+  const bool IsNegative = (X < 0) ^ (Y < 0);
+  Result = IsNegative ? (0 - UResult) : UResult;
+
+  // If any of the args was 0, result is 0 and no overflow occurs.
+  if (UX == 0 || UY == 0)
+    return false;
+
+  // UX and UY are in [1, 2^n], where n is the number of digits.
+  // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for
+  // 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;
+}
+
 } // End llvm namespace
 
 #endif

llvm/unittests/Support/MathExtrasTest.cpp

TEST(MathExtras, IsShiftedInt) {
   EXPECT_TRUE((isShiftedInt<11, 5>(-(int64_t(0x201) << 5))));
   EXPECT_FALSE((isShiftedInt<11, 5>(-(int64_t(0x201) << 3))));
   EXPECT_FALSE((isShiftedInt<11, 5>(-(int64_t(0x201) << 6))));
 
   EXPECT_TRUE((isShiftedInt<6, 10>(-(int64_t(1) << 15))));
   EXPECT_FALSE((isShiftedInt<6, 10>(int64_t(1) << 15)));
 }
 
+template <typename T>
+class OverflowTest : public ::testing::Test { };
+
+using OverflowTestTypes = ::testing::Types<char, short, int, long, long long>;
+
+TYPED_TEST_CASE(OverflowTest, OverflowTestTypes);
+
+TYPED_TEST(OverflowTest, AddNoOverflow) {
+  TypeParam Result;
+  EXPECT_FALSE(AddOverflow<TypeParam>(1, 2, Result));
+  EXPECT_EQ(Result, TypeParam(3));
+}
+
+TYPED_TEST(OverflowTest, AddOverflowToNegative) {
+  TypeParam Result;
+  auto MaxValue = std::numeric_limits<TypeParam>::max();
+  EXPECT_TRUE(AddOverflow<TypeParam>(MaxValue, MaxValue, Result));
+  EXPECT_EQ(Result, TypeParam(-2));
+}
+
+TYPED_TEST(OverflowTest, AddOverflowToMin) {
+  TypeParam Result;
+  auto MaxValue = std::numeric_limits<TypeParam>::max();
+  EXPECT_TRUE(AddOverflow<TypeParam>(MaxValue, TypeParam(1), Result));
+  EXPECT_EQ(Result, std::numeric_limits<TypeParam>::min());
+}
+
+TYPED_TEST(OverflowTest, AddOverflowToZero) {
+  TypeParam Result;
+  auto MinValue = std::numeric_limits<TypeParam>::min();
+  EXPECT_TRUE(AddOverflow<TypeParam>(MinValue, MinValue, Result));
+  EXPECT_EQ(Result, TypeParam(0));
+}
+
+TYPED_TEST(OverflowTest, AddOverflowToMax) {
+  TypeParam Result;
+  auto MinValue = std::numeric_limits<TypeParam>::min();
+  EXPECT_TRUE(AddOverflow<TypeParam>(MinValue, TypeParam(-1), Result));
+  EXPECT_EQ(Result, std::numeric_limits<TypeParam>::max());
+}
+
+TYPED_TEST(OverflowTest, SubNoOverflow) {
+  TypeParam Result;
+  EXPECT_FALSE(SubOverflow<TypeParam>(1, 2, Result));
+  EXPECT_EQ(Result, TypeParam(-1));
+}
+
+TYPED_TEST(OverflowTest, SubOverflowToMax) {
+  TypeParam Result;
+  auto MinValue = std::numeric_limits<TypeParam>::min();
+  EXPECT_TRUE(SubOverflow<TypeParam>(0, MinValue, Result));
+  EXPECT_EQ(Result, MinValue);
+}
+
+TYPED_TEST(OverflowTest, SubOverflowToMin) {
+  TypeParam Result;
+  auto MinValue = std::numeric_limits<TypeParam>::min();
+  EXPECT_TRUE(SubOverflow<TypeParam>(0, MinValue, Result));
+  EXPECT_EQ(Result, MinValue);
+}
+
+TYPED_TEST(OverflowTest, SubOverflowToNegative) {
+  TypeParam Result;
+  auto MaxValue = std::numeric_limits<TypeParam>::max();
+  auto MinValue = std::numeric_limits<TypeParam>::min();
+  EXPECT_TRUE(SubOverflow<TypeParam>(MaxValue, MinValue, Result));
+  EXPECT_EQ(Result, TypeParam(-1));
+}
+
+TYPED_TEST(OverflowTest, SubOverflowToPositive) {
+  TypeParam Result;
+  auto MaxValue = std::numeric_limits<TypeParam>::max();
+  auto MinValue = std::numeric_limits<TypeParam>::min();
+  EXPECT_TRUE(SubOverflow<TypeParam>(MinValue, MaxValue, Result));
+  EXPECT_EQ(Result, TypeParam(1));
+}
+
+TYPED_TEST(OverflowTest, MulNoOverflow) {
+  TypeParam Result;
+  EXPECT_FALSE(MulOverflow<TypeParam>(1, 2, Result));
+  EXPECT_EQ(Result, 2);
+  EXPECT_FALSE(MulOverflow<TypeParam>(-1, 3, Result));
+  EXPECT_EQ(Result, -3);
+  EXPECT_FALSE(MulOverflow<TypeParam>(4, -2, Result));
+  EXPECT_EQ(Result, -8);
+  EXPECT_FALSE(MulOverflow<TypeParam>(-6, -5, Result));
+  EXPECT_EQ(Result, 30);
+}
+
+TYPED_TEST(OverflowTest, MulNoOverflowToMax) {
+  TypeParam Result;
+  auto MaxValue = std::numeric_limits<TypeParam>::max();
+  auto MinValue = std::numeric_limits<TypeParam>::min();
+  EXPECT_FALSE(MulOverflow<TypeParam>(MinValue + 1, -1, Result));
+  EXPECT_EQ(Result, MaxValue);
+}
+
+TYPED_TEST(OverflowTest, MulOverflowToMin) {
+  TypeParam Result;
+  auto MinValue = std::numeric_limits<TypeParam>::min();
+  EXPECT_TRUE(MulOverflow<TypeParam>(MinValue, -1, Result));
+  EXPECT_EQ(Result, MinValue);
+}
+
+TYPED_TEST(OverflowTest, MulOverflowMax) {
+  TypeParam Result;
+  auto MinValue = std::numeric_limits<TypeParam>::min();
+  auto MaxValue = std::numeric_limits<TypeParam>::max();
+  EXPECT_TRUE(MulOverflow<TypeParam>(MinValue, MinValue, Result));
+  EXPECT_EQ(Result, 0);
+  EXPECT_TRUE(MulOverflow<TypeParam>(MaxValue, MaxValue, Result));
+  EXPECT_EQ(Result, 1);
+}
+
+TYPED_TEST(OverflowTest, MulResultZero) {
+  TypeParam Result;
+  EXPECT_FALSE(MulOverflow<TypeParam>(4, 0, Result));
+  EXPECT_EQ(Result, TypeParam(0));
+  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));
+}
+
 } // namespace