From: Nathan Slingerland Date: Mon, 23 Nov 2015 21:54:22 +0000 (+0000) Subject: [Support] Add optional argument to SaturatingAdd() and SaturatingMultiply() to indica... X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=0197bd6d5ecc07c89e7302c67212c4fcdbc3f48c;ds=sidebyside [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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@253921 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/include/llvm/Support/MathExtras.h b/include/llvm/Support/MathExtras.h index d853e8a21e4..0d0a2efa7ad 100644 --- a/include/llvm/Support/MathExtras.h +++ b/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 std::enable_if::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::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 std::enable_if::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 std::enable_if::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::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 std::enable_if::value, T>::type +SaturatingMultiply(T X, T Y) { + bool ResultOverflowed; + return SaturatingMultiply(X, Y, ResultOverflowed); } extern const float huge_valf; diff --git a/unittests/Support/MathExtrasTest.cpp b/unittests/Support/MathExtrasTest.cpp index fa12f750407..ee2fc1b9034 100644 --- a/unittests/Support/MathExtrasTest.cpp +++ b/unittests/Support/MathExtrasTest.cpp @@ -194,10 +194,27 @@ template void SaturatingAddTestHelper() { const T Max = std::numeric_limits::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 void SaturatingMultiplyTestHelper() { const T Max = std::numeric_limits::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); } } }