Utility functions for checked arithmetic

[george.karpenkov]

Summary

Provide checkedAdd and checkedMul functions, providing checked arithmetic on signed 64 bit integers.

[vsk]

It would be great to have checked* utilities which work with all the different kinds of integers.

include/llvm/Support/MathExtras.h

852

Once this lands, I think people will want to use it for more than just int64_t. To make this generic we'll need templates, and that introduces a cyclic-dependency problem with APInt.h.

Sorry for not thinking of this earlier, but: wdyt of moving this to Support/CheckedArithmetic.h (or similar)?

lib/Support/MathExtras.cpp

21

Could you move the APInt include up to the right spot?

26

Please clang-format your diffs.

29

llvm::function_ref is more appropriate for non-owning callables.

[george.karpenkov]

lib/Support/MathExtras.cpp

29

...except it does not work here, and I don't think it's worth it to investigate why

[vsk]

include/llvm/Support/CheckedArithmetic.h

31 ↗

(On Diff #135765)

Can you move this out of the llvm namespace, into an anonymous namespace?

33 ↗

(On Diff #135765)

I'd rather just have the type of the function be some free template parameter, then, so it's clear the object isn't copied.

[george.karpenkov]

include/llvm/Support/CheckedArithmetic.h

33 ↗

(On Diff #135765)

Could you elaborate?

[vsk]

include/llvm/Support/CheckedArithmetic.h

33 ↗

(On Diff #135765)

I'm suggesting adding 'typename F' to the template parameter list and using F as the type of Op. It's shorter, and since there's no std::function, it signals to the reader that there are no unnecessary copies happening. Taken together this makes the code easier to read.

[vsk]

Thanks! Please wait a day or so before committing to give others time to provide feedback.

include/llvm/Support/CheckedArithmetic.h

20 ↗

(On Diff #135972)

This include can go away now.

[delcypher]

This comment was removed by delcypher.

include/llvm/Support/MathExtras.h

SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
 
   T Product = SaturatingMultiply(X, Y, &Overflowed);
   if (Overflowed)
     return Product;
 
   return SaturatingAdd(A, Product, &Overflowed);
 }
 
+/// Add two integers \p LHS and \p RHS, write into \p Res if non-null and the
+/// operation does not oveflow.
+/// Does not guarantee saturating arithmetic.
+/// \return Whether the result overflows.
+bool checkedAdd(int64_t LHS, int64_t RHS, int64_t *Res=nullptr);
+
+/// Multiply two integers \p LHS and \p RHS, write into \p Res if non-null and
+/// the operation does not oveflow.
+/// Does not guarantee saturating arithmetic.
+/// \return Whether the result overflows.
+bool checkedMul(int64_t LHS, int64_t RHS, int64_t *Res=nullptr);
+
 /// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
 extern const float huge_valf;
 } // End llvm namespace
 
 #endif

lib/Support/MathExtras.cpp

 
 #include "llvm/Support/MathExtras.h"
 
 #ifdef _MSC_VER
 #include <limits>
 #else
 #include <math.h>
 #endif
+#include <llvm/ADT/APInt.h>
+#include <functional>
 
 namespace llvm {
 
+static bool checkedOp(
+    int64_t LHS,
+    int64_t RHS,
+    std::function<llvm::APInt(llvm::APInt *, const llvm::APInt &, bool &)> Op,
+    int64_t *Res = nullptr) {
+  llvm::APInt ALHS(/*BitSize=*/64, LHS, /*Signed=*/true);
+  llvm::APInt ARHS(/*BitSize=*/64, RHS, /*Signed=*/true);
+  bool Overflow;
+  llvm::APInt Out = Op(&ALHS, ARHS, Overflow);
+  if (!Overflow && Res)
+    *Res = Out.getSExtValue();
+  return Overflow;
+}
+
+bool checkedAdd(
+    int64_t LHS,
+    int64_t RHS,
+    int64_t *Res) {
+  return checkedOp(LHS, RHS, &llvm::APInt::sadd_ov, Res);
+}
+
+bool checkedMul(
+    int64_t LHS,
+    int64_t RHS,
+    int64_t *Res) {
+  return checkedOp(LHS, RHS, &llvm::APInt::smul_ov, Res);
+}
+
 #if defined(_MSC_VER)
   // Visual Studio defines the HUGE_VAL class of macros using purposeful
   // constant arithmetic overflow, which it then warns on when encountered.
   const float huge_valf = std::numeric_limits<float>::infinity();
 #else
   const float huge_valf = HUGE_VALF;
 #endif
 
 }

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)));
 }
 
+TEST(MathExtras, CheckedAdd) {
+  const int64_t Max = std::numeric_limits<int64_t>::max();
+  const int64_t Min = std::numeric_limits<int64_t>::min();
+  EXPECT_EQ(checkedAdd(Max, Max), true);
+  EXPECT_EQ(checkedAdd(Min, -1), true);
+  EXPECT_EQ(checkedAdd(Max, 1), true);
+  int64_t Out;
+  EXPECT_EQ(checkedAdd(10, 1, &Out), false);
+  EXPECT_EQ(Out, 11);
+
+}
+
+TEST(MathExtras, CheckedMul) {
+  const int64_t Max = std::numeric_limits<int64_t>::max();
+  const int64_t Min = std::numeric_limits<int64_t>::min();
+  EXPECT_EQ(checkedMul(Max, 2), true);
+  EXPECT_EQ(checkedMul(Max, Max), true);
+  EXPECT_EQ(checkedMul(Min, 2), true);
+  int64_t Out;
+  EXPECT_EQ(checkedMul(10, 2, &Out), false);
+  EXPECT_EQ(Out, 20);
+}
+
 } // namespace