[llvm-profdata] Add SaturatingAdd/SaturatingMultiply Helper Functions

[slingn]

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.

[slingn]

Related question:

Is it by design that intstr profile count overflow is treated differently from sample profile count overflow?
Instr profile merging appears to skip records that would result in overflow and print a warning. Sample profile count overflow saturates and does not show a warning.

[davidxl]

The way InstrProf handles overflow is a little extreme (by skipping the
record for the whole function). I think Using saturating add with some form
of warning is better.

David

[davidxl]

lgtm.

[dnovillo]

In D14720#290631, @slingn wrote:

Related question:

Is it by design that intstr profile count overflow is treated differently from sample profile count overflow?
Instr profile merging appears to skip records that would result in overflow and print a warning. Sample profile count overflow saturates and does not show a warning.

Sample PGO will warn when the weights read from the profile saturate 32-bit values. Showing a warning in llvm-profdata when adding 64 bit values sounds like a good idea.

include/llvm/ProfileData/InstrProf.h

void mergeValueData(InstrProfValueSiteRecord &Input) {
     Input.sortByTargetValues();
     auto I = ValueData.begin();
     auto IE = ValueData.end();
     for (auto J = Input.ValueData.begin(), JE = Input.ValueData.end(); J != JE;
          ++J) {
       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;
       }
       ValueData.insert(I, *J);
     }
   }
 };
 

include/llvm/ProfileData/SampleProf.h

public:
 
   SampleRecord() : NumSamples(0), CallTargets() {}
 
   /// Increment the number of samples for this record by \p S.
   ///
   /// 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.
   ///
   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
   /// 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.
   bool hasCalls() const { return CallTargets.size() > 0; }
 
   uint64_t getSamples() const { return NumSamples; }
   const CallTargetMap &getCallTargets() const { return CallTargets; }
 

include/llvm/Support/MathExtras.h

 }
 
 /// \brief Sign extend number in the bottom B bits of X to a 64-bit int.
 /// Requires 0 < B <= 64.
 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
 
 #endif

unittests/Support/MathExtrasTest.cpp

TEST(MathExtras, RoundUpToAlignment) {
   EXPECT_EQ(0u, RoundUpToAlignment(~0LL, 8));
 
   EXPECT_EQ(7u, RoundUpToAlignment(5, 8, 7));
   EXPECT_EQ(17u, RoundUpToAlignment(17, 8, 1));
   EXPECT_EQ(3u, RoundUpToAlignment(~0LL, 8, 3));
   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>();
+}
+
 }