diff --git a/llvm/include/llvm/Support/MathExtras.h b/llvm/include/llvm/Support/MathExtras.h --- a/llvm/include/llvm/Support/MathExtras.h +++ b/llvm/include/llvm/Support/MathExtras.h @@ -848,6 +848,83 @@ /// 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 std::enable_if::value, T>::type +AddOverflow(T X, T Y, T &Result) { + // Perform the unsigned addition. + using U = typename std::make_unsigned::type; + const U UX = static_cast(X); + const U UY = static_cast(Y); + const U UResult = UX + UY; + + // Convert to signed. + Result = static_cast(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 std::enable_if::value, T>::type +SubOverflow(T X, T Y, T &Result) { + // Perform the unsigned addition. + using U = typename std::make_unsigned::type; + const U UX = static_cast(X); + const U UY = static_cast(Y); + const U UResult = UX - UY; + + // Convert to signed. + Result = static_cast(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 std::enable_if::value, T>::type +MulOverflow(T X, T Y, T &Result) { + // Perform the unsigned multiplication on absolute values. + using U = typename std::make_unsigned::type; + const U UX = X < 0 ? (0 - static_cast(X)) : static_cast(X); + const U UY = Y < 0 ? (0 - static_cast(Y)) : static_cast(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(std::numeric_limits::max()) + U(1)) / UY; + else + return UX > (static_cast(std::numeric_limits::max())) / UY; +} + } // End llvm namespace #endif diff --git a/llvm/unittests/Support/MathExtrasTest.cpp b/llvm/unittests/Support/MathExtrasTest.cpp --- a/llvm/unittests/Support/MathExtrasTest.cpp +++ b/llvm/unittests/Support/MathExtrasTest.cpp @@ -468,4 +468,131 @@ EXPECT_FALSE((isShiftedInt<6, 10>(int64_t(1) << 15))); } +template +class OverflowTest : public ::testing::Test { }; + +using OverflowTestTypes = ::testing::Types; + +TYPED_TEST_CASE(OverflowTest, OverflowTestTypes); + +TYPED_TEST(OverflowTest, AddNoOverflow) { + TypeParam Result; + EXPECT_FALSE(AddOverflow(1, 2, Result)); + EXPECT_EQ(Result, TypeParam(3)); +} + +TYPED_TEST(OverflowTest, AddOverflowToNegative) { + TypeParam Result; + auto MaxValue = std::numeric_limits::max(); + EXPECT_TRUE(AddOverflow(MaxValue, MaxValue, Result)); + EXPECT_EQ(Result, TypeParam(-2)); +} + +TYPED_TEST(OverflowTest, AddOverflowToMin) { + TypeParam Result; + auto MaxValue = std::numeric_limits::max(); + EXPECT_TRUE(AddOverflow(MaxValue, TypeParam(1), Result)); + EXPECT_EQ(Result, std::numeric_limits::min()); +} + +TYPED_TEST(OverflowTest, AddOverflowToZero) { + TypeParam Result; + auto MinValue = std::numeric_limits::min(); + EXPECT_TRUE(AddOverflow(MinValue, MinValue, Result)); + EXPECT_EQ(Result, TypeParam(0)); +} + +TYPED_TEST(OverflowTest, AddOverflowToMax) { + TypeParam Result; + auto MinValue = std::numeric_limits::min(); + EXPECT_TRUE(AddOverflow(MinValue, TypeParam(-1), Result)); + EXPECT_EQ(Result, std::numeric_limits::max()); +} + +TYPED_TEST(OverflowTest, SubNoOverflow) { + TypeParam Result; + EXPECT_FALSE(SubOverflow(1, 2, Result)); + EXPECT_EQ(Result, TypeParam(-1)); +} + +TYPED_TEST(OverflowTest, SubOverflowToMax) { + TypeParam Result; + auto MinValue = std::numeric_limits::min(); + EXPECT_TRUE(SubOverflow(0, MinValue, Result)); + EXPECT_EQ(Result, MinValue); +} + +TYPED_TEST(OverflowTest, SubOverflowToMin) { + TypeParam Result; + auto MinValue = std::numeric_limits::min(); + EXPECT_TRUE(SubOverflow(0, MinValue, Result)); + EXPECT_EQ(Result, MinValue); +} + +TYPED_TEST(OverflowTest, SubOverflowToNegative) { + TypeParam Result; + auto MaxValue = std::numeric_limits::max(); + auto MinValue = std::numeric_limits::min(); + EXPECT_TRUE(SubOverflow(MaxValue, MinValue, Result)); + EXPECT_EQ(Result, TypeParam(-1)); +} + +TYPED_TEST(OverflowTest, SubOverflowToPositive) { + TypeParam Result; + auto MaxValue = std::numeric_limits::max(); + auto MinValue = std::numeric_limits::min(); + EXPECT_TRUE(SubOverflow(MinValue, MaxValue, Result)); + EXPECT_EQ(Result, TypeParam(1)); +} + +TYPED_TEST(OverflowTest, MulNoOverflow) { + TypeParam Result; + EXPECT_FALSE(MulOverflow(1, 2, Result)); + EXPECT_EQ(Result, 2); + EXPECT_FALSE(MulOverflow(-1, 3, Result)); + EXPECT_EQ(Result, -3); + EXPECT_FALSE(MulOverflow(4, -2, Result)); + EXPECT_EQ(Result, -8); + EXPECT_FALSE(MulOverflow(-6, -5, Result)); + EXPECT_EQ(Result, 30); +} + +TYPED_TEST(OverflowTest, MulNoOverflowToMax) { + TypeParam Result; + auto MaxValue = std::numeric_limits::max(); + auto MinValue = std::numeric_limits::min(); + EXPECT_FALSE(MulOverflow(MinValue + 1, -1, Result)); + EXPECT_EQ(Result, MaxValue); +} + +TYPED_TEST(OverflowTest, MulOverflowToMin) { + TypeParam Result; + auto MinValue = std::numeric_limits::min(); + EXPECT_TRUE(MulOverflow(MinValue, -1, Result)); + EXPECT_EQ(Result, MinValue); +} + +TYPED_TEST(OverflowTest, MulOverflowMax) { + TypeParam Result; + auto MinValue = std::numeric_limits::min(); + auto MaxValue = std::numeric_limits::max(); + EXPECT_TRUE(MulOverflow(MinValue, MinValue, Result)); + EXPECT_EQ(Result, 0); + EXPECT_TRUE(MulOverflow(MaxValue, MaxValue, Result)); + EXPECT_EQ(Result, 1); +} + +TYPED_TEST(OverflowTest, MulResultZero) { + TypeParam Result; + EXPECT_FALSE(MulOverflow(4, 0, Result)); + EXPECT_EQ(Result, TypeParam(0)); + EXPECT_FALSE(MulOverflow(-5, 0, Result)); + EXPECT_EQ(Result, TypeParam(0)); + EXPECT_FALSE(MulOverflow(0, 5, Result)); + EXPECT_EQ(Result, TypeParam(0)); + EXPECT_FALSE(MulOverflow(0, -5, Result)); + EXPECT_EQ(Result, TypeParam(0)); +} + } // namespace