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 ↗

(On Diff #135743)

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 ↗

(On Diff #135743)

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

26 ↗

(On Diff #135743)

Please clang-format your diffs.

29 ↗

(On Diff #135743)

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

[george.karpenkov]

lib/Support/MathExtras.cpp

29 ↗

(On Diff #135743)

...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.

llvm/trunk/include/llvm/Support/CheckedArithmetic.h

+//==-- llvm/Support/CheckedArithmetic.h - Safe arithmetical operations *- C++ //
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains generic functions for operating on integers which
+// give the indication on whether the operation has overflown.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_CHECKEDARITHMETIC_H
+#define LLVM_SUPPORT_CHECKEDARITHMETIC_H
+
+#include "llvm/ADT/APInt.h"
+
+#include <type_traits>
+
+namespace {
+
+/// Utility function to apply a given method of \c APInt \p F to \p LHS and
+/// \p RHS, and write the output into \p Res.
+/// \return Whether the operation overflows.
+template <typename T, typename F>
+typename std::enable_if<std::is_integral<T>::value && sizeof(T) * 8 <= 64,
+                        bool>::type
+checkedOp(T LHS, T RHS, F Op, T *Res = nullptr, bool Signed = true) {
+  llvm::APInt ALHS(/*BitSize=*/sizeof(T) * 8, LHS, Signed);
+  llvm::APInt ARHS(/*BitSize=*/sizeof(T) * 8, RHS, Signed);
+  bool Overflow;
+  llvm::APInt Out = (ALHS.*Op)(ARHS, Overflow);
+  if (Res)
+    *Res = Signed ? Out.getSExtValue() : Out.getZExtValue();
+  return Overflow;
+}
+}
+
+namespace llvm {
+
+/// Add two signed integers \p LHS and \p RHS, write into \p Res if non-null.
+/// Does not guarantee saturating arithmetic.
+/// \return Whether the result overflows.
+template <typename T>
+typename std::enable_if<std::is_signed<T>::value, bool>::type
+checkedAdd(T LHS, T RHS, T *Res = nullptr) {
+  return checkedOp(LHS, RHS, &llvm::APInt::sadd_ov, Res);
+}
+
+/// Multiply two signed integers \p LHS and \p RHS, write into \p Res if
+/// non-null.
+/// Does not guarantee saturating arithmetic.
+/// \return Whether the result overflows.
+template <typename T>
+typename std::enable_if<std::is_signed<T>::value, bool>::type
+checkedMul(T LHS, T RHS, T *Res = nullptr) {
+  return checkedOp(LHS, RHS, &llvm::APInt::smul_ov, Res);
+}
+
+/// Add two unsigned integers \p LHS and \p RHS, write into \p Res if non-null.
+/// Does not guarantee saturating arithmetic.
+/// \return Whether the result overflows.
+template <typename T>
+typename std::enable_if<std::is_unsigned<T>::value, bool>::type
+checkedAddUnsigned(T LHS, T RHS, T *Res = nullptr) {
+  return checkedOp(LHS, RHS, &llvm::APInt::uadd_ov, Res, /*Signed=*/false);
+}
+
+/// Multiply two unsigned integers \p LHS and \p RHS, write into \p Res if
+/// non-null.
+/// Does not guarantee saturating arithmetic.
+/// \return Whether the result overflows.
+template <typename T>
+typename std::enable_if<std::is_unsigned<T>::value, bool>::type
+checkedMulUnsigned(T LHS, T RHS, T *Res = nullptr) {
+  return checkedOp(LHS, RHS, &llvm::APInt::umul_ov, Res, /*Signed=*/false);
+}
+
+} // End llvm namespace
+
+#endif

llvm/trunk/unittests/Support/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_llvm_unittest(SupportTests
   AlignOfTest.cpp
   AllocatorTest.cpp
   ARMAttributeParser.cpp
   ArrayRecyclerTest.cpp
   BinaryStreamTest.cpp
   BlockFrequencyTest.cpp
   BranchProbabilityTest.cpp
   CachePruningTest.cpp
   CrashRecoveryTest.cpp
   Casting.cpp
+  CheckedArithmeticTest.cpp
   Chrono.cpp
   CommandLineTest.cpp
   CompressionTest.cpp
   ConvertUTFTest.cpp
   DataExtractorTest.cpp
   DebugTest.cpp
   DJBTest.cpp
   EndianStreamTest.cpp

llvm/trunk/unittests/Support/CheckedArithmeticTest.cpp

+#include "llvm/Support/CheckedArithmetic.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+TEST(CheckedArithmetic, CheckedAdd) {
+  int64_t Out;
+  const int64_t Max = std::numeric_limits<int64_t>::max();
+  const int64_t Min = std::numeric_limits<int64_t>::min();
+  EXPECT_EQ(checkedAdd<int64_t>(Max, Max, &Out), true);
+  EXPECT_EQ(checkedAdd<int64_t>(Min, -1, &Out), true);
+  EXPECT_EQ(checkedAdd<int64_t>(Max, 1, &Out), true);
+  EXPECT_EQ(checkedAdd<int64_t>(10, 1, &Out), false);
+  EXPECT_EQ(Out, 11);
+}
+
+TEST(CheckedArithmetic, CheckedAddSmall) {
+  int16_t Out;
+  const int16_t Max = std::numeric_limits<int16_t>::max();
+  const int16_t Min = std::numeric_limits<int16_t>::min();
+  EXPECT_EQ(checkedAdd<int16_t>(Max, Max, &Out), true);
+  EXPECT_EQ(checkedAdd<int16_t>(Min, -1, &Out), true);
+  EXPECT_EQ(checkedAdd<int16_t>(Max, 1, &Out), true);
+  EXPECT_EQ(checkedAdd<int16_t>(10, 1, &Out), false);
+  EXPECT_EQ(Out, 11);
+}
+
+TEST(CheckedArithmetic, CheckedMul) {
+  int64_t Out;
+  const int64_t Max = std::numeric_limits<int64_t>::max();
+  const int64_t Min = std::numeric_limits<int64_t>::min();
+  EXPECT_EQ(checkedMul<int64_t>(Max, 2, &Out), true);
+  EXPECT_EQ(checkedMul<int64_t>(Max, Max, &Out), true);
+  EXPECT_EQ(checkedMul<int64_t>(Min, 2, &Out), true);
+  EXPECT_EQ(checkedMul<int64_t>(10, 2, &Out), false);
+  EXPECT_EQ(Out, 20);
+}
+
+TEST(CheckedArithmetic, CheckedMulSmall) {
+  int16_t Out;
+  const int16_t Max = std::numeric_limits<int16_t>::max();
+  const int16_t Min = std::numeric_limits<int16_t>::min();
+  EXPECT_EQ(checkedMul<int16_t>(Max, 2, &Out), true);
+  EXPECT_EQ(checkedMul<int16_t>(Max, Max, &Out), true);
+  EXPECT_EQ(checkedMul<int16_t>(Min, 2, &Out), true);
+  EXPECT_EQ(checkedMul<int16_t>(10, 2, &Out), false);
+  EXPECT_EQ(Out, 20);
+}
+
+TEST(CheckedArithmetic, CheckedAddUnsigned) {
+  uint64_t Out;
+  const uint64_t Max = std::numeric_limits<uint64_t>::max();
+  EXPECT_EQ(checkedAddUnsigned<uint64_t>(Max, Max, &Out), true);
+  EXPECT_EQ(checkedAddUnsigned<uint64_t>(Max, 1, &Out), true);
+  EXPECT_EQ(checkedAddUnsigned<uint64_t>(10, 1, &Out), false);
+  EXPECT_EQ(Out, uint64_t(11));
+}
+
+TEST(CheckedArithmetic, CheckedMulUnsigned) {
+  uint64_t Out;
+  const uint64_t Max = std::numeric_limits<uint64_t>::max();
+  EXPECT_EQ(checkedMulUnsigned<uint64_t>(Max, 2, &Out), true);
+  EXPECT_EQ(checkedMulUnsigned<uint64_t>(Max, Max, &Out), true);
+  EXPECT_EQ(checkedMulUnsigned<uint64_t>(10, 2, &Out), false);
+  EXPECT_EQ(Out, uint64_t(20));
+}
+
+
+} // namespace