Implement constexpr __builtin_*_overflow

[erichkeane]

Summary

As requested here:https://bugs.llvm.org/show_bug.cgi?id=37633

permit the __builtin_*_overflow builtins in constexpr functions.

[rjmccall]

lib/AST/ExprConstant.cpp

8260 ↗

(On Diff #150798)

The comment should explain *why* growth isn't possible (it's because we extended to the max-width type earlier).

I don't think a casual reader is going to understand what you're saying about TruncOrSelf (that APSInt doesn't have such an operation, but that we can safely simulate it with extOrTrunc because we'll never do an extension).

[efriedma]

lib/Sema/SemaChecking.cpp

210 ↗

(On Diff #150808)

Can you split this change into a separate patch? Testcase:

int a() {
  const int x = 3;
  static int z;
  constexpr int * y = &z;
  return []() { return __builtin_sub_overflow(x,x,y); }();
}

[erichkeane]

lib/Sema/SemaChecking.cpp

210 ↗

(On Diff #150808)

Can you clarify what you mean? That above testcase (with added captures) seems to work currently. What difference in behavior should I be expecting?

[efriedma]

lib/Sema/SemaChecking.cpp

210 ↗

(On Diff #150808)

The testcase should type-check as-is, without adding any captures. Reading the value of a constexpr variable, or a const variable of integer type, isn't an odr-use. This doesn't work correctly at the moment because the lvalue-to-rvalue conversions are missing from the AST. Compare to the following:

int a() {
  const int x = 3;
  static int z;
  constexpr int * y = &z;
  return []() { return __builtin_sub_overflow((int)x,(int)x,(int*)y); }();
}

[erichkeane]

lib/Sema/SemaChecking.cpp

210 ↗

(On Diff #150808)

Ah, got it! I 'll split that off into a separate patch with those test cases now. Look for the review soon!

[erichkeane]

Alright, done here: https://reviews.llvm.org/D48053

This one'll require some rebasing on that change, but I'm not sure how to do it in SVN. Therefore, I'll just rebase this one when it comes to commit it.

-Erich

[rjmccall]

Thanks, comment change looks good. LGTM.

[erichkeane]

Separated out the other patch as Eli suggested (which has now been committed), and rebased this patch on top of it.

[efriedma]

I'd like to see a couple of testcases ensuring the return value is correct on overflow (we had a problem with that for __builtin_mul_overflow in the past).

Otherwise LGTM.

[erichkeane]

I believe my tests DO validate the return value correctly, don't they? It uses a sentinel, but the ternary should check that return value, right?

Or is there an obvious thing I'm missing?

[efriedma]

Oh, sorry, I mixed up the two values. I meant that you should add a couple testcases to ensure the stored value is correct on overflow.

cfe/trunk/lib/AST/ExprConstant.cpp

case Builtin::BI__c11_atomic_is_lock_free: {
     }
 
     return BuiltinOp == Builtin::BI__atomic_always_lock_free ?
         Success(0, E) : Error(E);
   }
   case Builtin::BIomp_is_initial_device:
     // We can decide statically which value the runtime would return if called.
     return Success(Info.getLangOpts().OpenMPIsDevice ? 0 : 1, E);
+  case Builtin::BI__builtin_add_overflow:
+  case Builtin::BI__builtin_sub_overflow:
+  case Builtin::BI__builtin_mul_overflow:
+  case Builtin::BI__builtin_sadd_overflow:
+  case Builtin::BI__builtin_uadd_overflow:
+  case Builtin::BI__builtin_uaddl_overflow:
+  case Builtin::BI__builtin_uaddll_overflow:
+  case Builtin::BI__builtin_usub_overflow:
+  case Builtin::BI__builtin_usubl_overflow:
+  case Builtin::BI__builtin_usubll_overflow:
+  case Builtin::BI__builtin_umul_overflow:
+  case Builtin::BI__builtin_umull_overflow:
+  case Builtin::BI__builtin_umulll_overflow:
+  case Builtin::BI__builtin_saddl_overflow:
+  case Builtin::BI__builtin_saddll_overflow:
+  case Builtin::BI__builtin_ssub_overflow:
+  case Builtin::BI__builtin_ssubl_overflow:
+  case Builtin::BI__builtin_ssubll_overflow:
+  case Builtin::BI__builtin_smul_overflow:
+  case Builtin::BI__builtin_smull_overflow:
+  case Builtin::BI__builtin_smulll_overflow: {
+    LValue ResultLValue;
+    APSInt LHS, RHS;
+
+    QualType ResultType = E->getArg(2)->getType()->getPointeeType();
+    if (!EvaluateInteger(E->getArg(0), LHS, Info) ||
+        !EvaluateInteger(E->getArg(1), RHS, Info) ||
+        !EvaluatePointer(E->getArg(2), ResultLValue, Info))
+      return false;
+
+    APSInt Result;
+    bool DidOverflow = false;
+
+    // If the types don't have to match, enlarge all 3 to the largest of them.
+    if (BuiltinOp == Builtin::BI__builtin_add_overflow ||
+        BuiltinOp == Builtin::BI__builtin_sub_overflow ||
+        BuiltinOp == Builtin::BI__builtin_mul_overflow) {
+      bool IsSigned = LHS.isSigned() || RHS.isSigned() ||
+                      ResultType->isSignedIntegerOrEnumerationType();
+      bool AllSigned = LHS.isSigned() && RHS.isSigned() &&
+                      ResultType->isSignedIntegerOrEnumerationType();
+      uint64_t LHSSize = LHS.getBitWidth();
+      uint64_t RHSSize = RHS.getBitWidth();
+      uint64_t ResultSize = Info.Ctx.getTypeSize(ResultType);
+      uint64_t MaxBits = std::max(std::max(LHSSize, RHSSize), ResultSize);
+
+      // Add an additional bit if the signedness isn't uniformly agreed to. We
+      // could do this ONLY if there is a signed and an unsigned that both have
+      // MaxBits, but the code to check that is pretty nasty.  The issue will be
+      // caught in the shrink-to-result later anyway.
+      if (IsSigned && !AllSigned)
+        ++MaxBits;
+
+      LHS = APSInt(IsSigned ? LHS.sextOrSelf(MaxBits) : LHS.zextOrSelf(MaxBits),
+                   !IsSigned);
+      RHS = APSInt(IsSigned ? RHS.sextOrSelf(MaxBits) : RHS.zextOrSelf(MaxBits),
+                   !IsSigned);
+      Result = APSInt(MaxBits, !IsSigned);
+    }
+
+    // Find largest int.
+    switch (BuiltinOp) {
+    default:
+      llvm_unreachable("Invalid value for BuiltinOp");
+    case Builtin::BI__builtin_add_overflow:
+    case Builtin::BI__builtin_sadd_overflow:
+    case Builtin::BI__builtin_saddl_overflow:
+    case Builtin::BI__builtin_saddll_overflow:
+    case Builtin::BI__builtin_uadd_overflow:
+    case Builtin::BI__builtin_uaddl_overflow:
+    case Builtin::BI__builtin_uaddll_overflow:
+      Result = LHS.isSigned() ? LHS.sadd_ov(RHS, DidOverflow)
+                              : LHS.uadd_ov(RHS, DidOverflow);
+      break;
+    case Builtin::BI__builtin_sub_overflow:
+    case Builtin::BI__builtin_ssub_overflow:
+    case Builtin::BI__builtin_ssubl_overflow:
+    case Builtin::BI__builtin_ssubll_overflow:
+    case Builtin::BI__builtin_usub_overflow:
+    case Builtin::BI__builtin_usubl_overflow:
+    case Builtin::BI__builtin_usubll_overflow:
+      Result = LHS.isSigned() ? LHS.ssub_ov(RHS, DidOverflow)
+                              : LHS.usub_ov(RHS, DidOverflow);
+      break;
+    case Builtin::BI__builtin_mul_overflow:
+    case Builtin::BI__builtin_smul_overflow:
+    case Builtin::BI__builtin_smull_overflow:
+    case Builtin::BI__builtin_smulll_overflow:
+    case Builtin::BI__builtin_umul_overflow:
+    case Builtin::BI__builtin_umull_overflow:
+    case Builtin::BI__builtin_umulll_overflow:
+      Result = LHS.isSigned() ? LHS.smul_ov(RHS, DidOverflow)
+                              : LHS.umul_ov(RHS, DidOverflow);
+      break;
+    }
+
+    // In the case where multiple sizes are allowed, truncate and see if
+    // the values are the same.
+    if (BuiltinOp == Builtin::BI__builtin_add_overflow ||
+        BuiltinOp == Builtin::BI__builtin_sub_overflow ||
+        BuiltinOp == Builtin::BI__builtin_mul_overflow) {
+      // APSInt doesn't have a TruncOrSelf, so we use extOrTrunc instead,
+      // since it will give us the behavior of a TruncOrSelf in the case where
+      // its parameter <= its size.  We previously set Result to be at least the
+      // type-size of the result, so getTypeSize(ResultType) <= Result.BitWidth
+      // will work exactly like TruncOrSelf.
+      APSInt Temp = Result.extOrTrunc(Info.Ctx.getTypeSize(ResultType));
+      Temp.setIsSigned(ResultType->isSignedIntegerOrEnumerationType());
+
+      if (!APSInt::isSameValue(Temp, Result))
+        DidOverflow = true;
+      Result = Temp;
+    }
+
+    APValue APV{Result};
+    handleAssignment(Info, E, ResultLValue, ResultType, APV);
+    return Success(DidOverflow, E);
+  }
   }
 }
 
 static bool HasSameBase(const LValue &A, const LValue &B) {
   if (!A.getLValueBase())
     return !B.getLValueBase();
   if (!B.getLValueBase())
     return false;

cfe/trunk/test/SemaCXX/builtins-overflow.cpp

 // RUN: %clang_cc1 -fsyntax-only -std=c++17 -verify %s
 // expected-no-diagnostics
 
+#include <limits.h>
+
 int a() {
   const int x = 3;
   static int z;
   constexpr int *y = &z;
   return []() { return __builtin_sub_overflow((int)x, (int)x, (int *)y); }();
 }
 int a2() {
   const int x = 3;
   static int z;
   constexpr int *y = &z;
   return []() { return __builtin_sub_overflow(x, x, y); }();
 }
+
+template<typename T>
+struct Result {
+  bool B;
+  T Value;
+  constexpr bool operator==(const Result<T> &Other) {
+    return B == Other.B && Value == Other.Value;
+  }
+};
+
+
+template <typename RET, typename LHS, typename RHS>
+constexpr Result<RET> add(LHS &&lhs, RHS &&rhs) {
+  RET sum{};
+  bool b = __builtin_add_overflow(lhs, rhs, &sum);
+  return {b, sum};
+}
+
+static_assert(add<short>(static_cast<char>(120), static_cast<char>(10)) == Result<short>{false, 130});
+static_assert(add<char>(static_cast<short>(120), static_cast<short>(10)) == Result<char>{true, -126});
+static_assert(add<unsigned int>(INT_MAX, INT_MAX) == Result<unsigned int>{false, static_cast<unsigned int>(INT_MAX) * 2u});
+static_assert(add<int>(static_cast<unsigned int>(INT_MAX), 1u) == Result<int>{true, INT_MIN});
+
+static_assert(add<int>(17, 22) == Result<int>{false, 39});
+static_assert(add<int>(INT_MAX - 22, 24) == Result<int>{true, INT_MIN + 1});
+static_assert(add<int>(INT_MIN + 22, -23) == Result<int>{true, INT_MAX});
+
+template <typename RET, typename LHS, typename RHS>
+constexpr Result<RET> sub(LHS &&lhs, RHS &&rhs) {
+  RET sum{};
+  bool b = __builtin_sub_overflow(lhs, rhs, &sum);
+  return {b, sum};
+}
+
+static_assert(sub<unsigned char>(static_cast<char>(0),static_cast<char>(1)) == Result<unsigned char>{true, UCHAR_MAX});
+static_assert(sub<char>(static_cast<unsigned char>(0),static_cast<unsigned char>(1)) == Result<char>{false, -1});
+static_assert(sub<unsigned short>(static_cast<short>(0),static_cast<short>(1)) == Result<unsigned short>{true, USHRT_MAX});
+
+static_assert(sub<int>(17,22) == Result<int>{false, -5});
+static_assert(sub<int>(INT_MAX - 22, -23) == Result<int>{true, INT_MIN});
+static_assert(sub<int>(INT_MIN + 22, 23) == Result<int>{true, INT_MAX});
+
+template <typename RET, typename LHS, typename RHS>
+constexpr Result<RET> mul(LHS &&lhs, RHS &&rhs) {
+  RET sum{};
+  bool b  = __builtin_mul_overflow(lhs, rhs, &sum);
+  return {b, sum};
+}
+
+static_assert(mul<int>(17,22) == Result<int>{false, 374});
+static_assert(mul<int>(INT_MAX / 22, 23) == Result<int>{true, -2049870757});
+static_assert(mul<int>(INT_MIN / 22, -23) == Result<int>{true, -2049870757});
+
+constexpr Result<int> sadd(int lhs, int rhs) {
+  int sum{};
+  bool b = __builtin_sadd_overflow(lhs, rhs, &sum);
+  return {b, sum};
+}
+
+static_assert(sadd(17,22) == Result<int>{false, 39});
+static_assert(sadd(INT_MAX - 22, 23) == Result<int>{true, INT_MIN});
+static_assert(sadd(INT_MIN + 22, -23) == Result<int>{true, INT_MAX});
+
+constexpr Result<int> ssub(int lhs, int rhs) {
+  int sum{};
+  bool b = __builtin_ssub_overflow(lhs, rhs, &sum);
+  return {b, sum};
+}
+
+static_assert(ssub(17,22) == Result<int>{false, -5});
+static_assert(ssub(INT_MAX - 22, -23) == Result<int>{true, INT_MIN});
+static_assert(ssub(INT_MIN + 22, 23) == Result<int>{true, INT_MAX});
+
+constexpr Result<int> smul(int lhs, int rhs) {
+  int sum{};
+  bool b = __builtin_smul_overflow(lhs, rhs, &sum);
+  return {b, sum};
+}
+
+static_assert(smul(17,22) == Result<int>{false, 374});
+static_assert(smul(INT_MAX / 22, 23) == Result<int>{true, -2049870757});
+static_assert(smul(INT_MIN / 22, -23) == Result<int>{true, -2049870757});