From: Nathan Slingerland <slingn@gmail.com>
Date: Wed, 18 Nov 2015 00:52:43 +0000 (+0000)
Subject: [llvm-profdata] Add SaturatingAdd/SaturatingMultiply Helper Functions
X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=4918b66f8428f0d5b4559da8f966e3aa54c3b1ba;hp=9eaef595284c567310bc6f0009f83d77a554b881

[llvm-profdata] Add SaturatingAdd/SaturatingMultiply Helper Functions

Summary:
This change adds MathExtras helper functions for handling unsigned, saturating addition and multiplication. It also updates the instrumentation and sample profile merge implementations to use them.

No functional changes.

Reviewers: dnovillo, bogner, davidxl

Subscribers: davidxl, llvm-commits

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@253412 91177308-0d34-0410-b5e6-96231b3b80d8
---

diff --git a/include/llvm/ProfileData/InstrProf.h b/include/llvm/ProfileData/InstrProf.h
index aa100a796f2..384edddf85a 100644
--- a/include/llvm/ProfileData/InstrProf.h
+++ b/include/llvm/ProfileData/InstrProf.h
@@ -226,7 +226,7 @@ struct InstrProfValueSiteRecord {
       while (I != IE && I->Value < J->Value)
         ++I;
       if (I != IE && I->Value == J->Value) {
-        I->Count += J->Count;
+        I->Count = SaturatingAdd(I->Count, J->Count);
         ++I;
         continue;
       }
diff --git a/include/llvm/ProfileData/SampleProf.h b/include/llvm/ProfileData/SampleProf.h
index d7596d7b1b7..a8960cf7bc1 100644
--- a/include/llvm/ProfileData/SampleProf.h
+++ b/include/llvm/ProfileData/SampleProf.h
@@ -173,10 +173,7 @@ public:
   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
   /// around unsigned integers.
   void addSamples(uint64_t S) {
-    if (NumSamples <= std::numeric_limits<uint64_t>::max() - S)
-      NumSamples += S;
-    else
-      NumSamples = std::numeric_limits<uint64_t>::max();
+    NumSamples = SaturatingAdd(NumSamples, S);
   }
 
   /// Add called function \p F with samples \p S.
@@ -185,10 +182,7 @@ public:
   /// around unsigned integers.
   void addCalledTarget(StringRef F, uint64_t S) {
     uint64_t &TargetSamples = CallTargets[F];
-    if (TargetSamples <= std::numeric_limits<uint64_t>::max() - S)
-      TargetSamples += S;
-    else
-      TargetSamples = std::numeric_limits<uint64_t>::max();
+    TargetSamples = SaturatingAdd(TargetSamples, S);
   }
 
   /// Return true if this sample record contains function calls.
diff --git a/include/llvm/Support/MathExtras.h b/include/llvm/Support/MathExtras.h
index 2c515bbd242..b7b3c02dcfe 100644
--- a/include/llvm/Support/MathExtras.h
+++ b/include/llvm/Support/MathExtras.h
@@ -653,6 +653,32 @@ inline int64_t SignExtend64(uint64_t X, unsigned B) {
   return int64_t(X << (64 - B)) >> (64 - B);
 }
 
+/// \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) {
+  // Hacker's Delight, p. 29
+  T Z = X + Y;
+  if (Z < X || Z < Y)
+    return std::numeric_limits<T>::max();
+  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;
+}
+
 extern const float huge_valf;
 } // End llvm namespace
 
diff --git a/unittests/Support/MathExtrasTest.cpp b/unittests/Support/MathExtrasTest.cpp
index 8bd47e34c7e..8adde02ed4e 100644
--- a/unittests/Support/MathExtrasTest.cpp
+++ b/unittests/Support/MathExtrasTest.cpp
@@ -190,4 +190,52 @@ TEST(MathExtras, RoundUpToAlignment) {
   EXPECT_EQ(552u, RoundUpToAlignment(321, 255, 42));
 }
 
+template<typename T>
+void SaturatingAddTestHelper()
+{
+  EXPECT_EQ(static_cast<T>(3),
+            SaturatingAdd(static_cast<T>(1), static_cast<T>(2)));
+  EXPECT_EQ(std::numeric_limits<T>::max(),
+            SaturatingAdd(std::numeric_limits<T>::max(), static_cast<T>(1)));
+  EXPECT_EQ(std::numeric_limits<T>::max(),
+            SaturatingAdd(static_cast<T>(1), std::numeric_limits<T>::max()));
+  EXPECT_EQ(std::numeric_limits<T>::max(),
+            SaturatingAdd(std::numeric_limits<T>::max(),
+                          std::numeric_limits<T>::max()));
+}
+
+TEST(MathExtras, SaturatingAdd) {
+  SaturatingAddTestHelper<uint8_t>();
+  SaturatingAddTestHelper<uint16_t>();
+  SaturatingAddTestHelper<uint32_t>();
+  SaturatingAddTestHelper<uint64_t>();
+}
+
+template<typename T>
+void SaturatingMultiplyTestHelper()
+{
+  EXPECT_EQ(static_cast<T>(0),
+            SaturatingMultiply(static_cast<T>(1), static_cast<T>(0)));
+  EXPECT_EQ(static_cast<T>(0),
+            SaturatingMultiply(static_cast<T>(0), static_cast<T>(1)));
+  EXPECT_EQ(static_cast<T>(6),
+            SaturatingMultiply(static_cast<T>(2), static_cast<T>(3)));
+  EXPECT_EQ(std::numeric_limits<T>::max(),
+            SaturatingMultiply(std::numeric_limits<T>::max(),
+                               static_cast<T>(2)));
+  EXPECT_EQ(std::numeric_limits<T>::max(),
+            SaturatingMultiply(static_cast<T>(2),
+                               std::numeric_limits<T>::max()));
+  EXPECT_EQ(std::numeric_limits<T>::max(),
+            SaturatingMultiply(std::numeric_limits<T>::max(),
+                          std::numeric_limits<T>::max()));
+}
+
+TEST(MathExtras, SaturatingMultiply) {
+  SaturatingMultiplyTestHelper<uint8_t>();
+  SaturatingMultiplyTestHelper<uint16_t>();
+  SaturatingMultiplyTestHelper<uint32_t>();
+  SaturatingMultiplyTestHelper<uint64_t>();
+}
+
 }