[clang] Implement constexpr evaluation for `__builtin_{add,sub}c`

[BertalanD]

Summary

GCC has gained support for these multiprecision arithmetic builtins in
r14-1896-g2b4e0415ad6, and although they aren't explicitly specified
as such in the documentation, they are usable in a constexpr context.

This commit adds constexpr evaluation support to Clang to match GCC's
behavior. The implementation mirrors how the builtins are lowered to a
pair of u{add,sub}.with.overflow operations and the carryout is set to
1 if either of those result in an overflow.

[aaron.ballman]

Thank you for this! The code changes themselves look good to me, but there's a few minor things left to do. You should also update the documentation somewhere near https://github.com/llvm/llvm-project/blob/118f95b394655d9dd425575025eafc6b79c3d84c/clang/docs/LanguageExtensions.rst?plain=1#L2467 to make it clear that we support these builtins and that they are allowed in a constant expression (we're trying to improve our implementation-defined documentation as we update stuff). And you should also add a release note to clang/docs/ReleaseNotes.rst as well.

clang/test/SemaCXX/builtins-multiprecision.cpp

1

Adding this just to be sure that the include below picks up the limits.h from the compiler and not the limits.h from the test system itself.

[BertalanD]

Moved to https://github.com/llvm/llvm-project/pull/66005

clang/include/clang/Basic/Builtins.def

 // Annotation function
 BUILTIN(__builtin_annotation, "v.", "tn")
 
 // Invariants
 BUILTIN(__builtin_assume, "vb", "nE")
 BUILTIN(__builtin_assume_separate_storage, "vvCD*vCD*", "nE")
 
 // Multiprecision Arithmetic Builtins.
-BUILTIN(__builtin_addcb, "UcUcCUcCUcCUc*", "n")
-BUILTIN(__builtin_addcs, "UsUsCUsCUsCUs*", "n")
-BUILTIN(__builtin_addc, "UiUiCUiCUiCUi*", "n")
-BUILTIN(__builtin_addcl, "ULiULiCULiCULiCULi*", "n")
-BUILTIN(__builtin_addcll, "ULLiULLiCULLiCULLiCULLi*", "n")
-BUILTIN(__builtin_subcb, "UcUcCUcCUcCUc*", "n")
-BUILTIN(__builtin_subcs, "UsUsCUsCUsCUs*", "n")
-BUILTIN(__builtin_subc, "UiUiCUiCUiCUi*", "n")
-BUILTIN(__builtin_subcl, "ULiULiCULiCULiCULi*", "n")
-BUILTIN(__builtin_subcll, "ULLiULLiCULLiCULLiCULLi*", "n")
+BUILTIN(__builtin_addcb, "UcUcCUcCUcCUc*", "nE")
+BUILTIN(__builtin_addcs, "UsUsCUsCUsCUs*", "nE")
+BUILTIN(__builtin_addc, "UiUiCUiCUiCUi*", "nE")
+BUILTIN(__builtin_addcl, "ULiULiCULiCULiCULi*", "nE")
+BUILTIN(__builtin_addcll, "ULLiULLiCULLiCULLiCULLi*", "nE")
+BUILTIN(__builtin_subcb, "UcUcCUcCUcCUc*", "nE")
+BUILTIN(__builtin_subcs, "UsUsCUsCUsCUs*", "nE")
+BUILTIN(__builtin_subc, "UiUiCUiCUiCUi*", "nE")
+BUILTIN(__builtin_subcl, "ULiULiCULiCULiCULi*", "nE")
+BUILTIN(__builtin_subcll, "ULLiULLiCULLiCULLiCULLi*", "nE")
 
 // Checked Arithmetic Builtins for Security.
 BUILTIN(__builtin_add_overflow, "b.", "ntE")
 BUILTIN(__builtin_sub_overflow, "b.", "ntE")
 BUILTIN(__builtin_mul_overflow, "b.", "ntE")
 BUILTIN(__builtin_uadd_overflow, "bUiCUiCUi*", "nE")
 BUILTIN(__builtin_uaddl_overflow, "bULiCULiCULi*", "nE")
 BUILTIN(__builtin_uaddll_overflow, "bULLiCULLiCULLi*", "nE")

clang/lib/AST/ExprConstant.cpp

if (BuiltinOp == Builtin::BI__builtin_add_overflow ||
       Result = Temp;
     }
 
     APValue APV{Result};
     if (!handleAssignment(Info, E, ResultLValue, ResultType, APV))
       return false;
     return Success(DidOverflow, E);
   }
+  case Builtin::BI__builtin_addcb:
+  case Builtin::BI__builtin_addcs:
+  case Builtin::BI__builtin_addc:
+  case Builtin::BI__builtin_addcl:
+  case Builtin::BI__builtin_addcll:
+  case Builtin::BI__builtin_subcb:
+  case Builtin::BI__builtin_subcs:
+  case Builtin::BI__builtin_subc:
+  case Builtin::BI__builtin_subcl:
+  case Builtin::BI__builtin_subcll: {
+    APSInt X, Y, CarryIn;
+    LValue CarryOut;
+
+    QualType ResultType = E->getArg(3)->getType()->getPointeeType();
+    if (!EvaluateInteger(E->getArg(0), X, Info) ||
+        !EvaluateInteger(E->getArg(1), Y, Info) ||
+        !EvaluateInteger(E->getArg(2), CarryIn, Info) ||
+        !EvaluatePointer(E->getArg(3), CarryOut, Info))
+      return false;
+
+    APInt Result;
+    bool DidOverflow1 = false;
+    bool DidOverflow2 = false;
+
+    switch (BuiltinOp) {
+    default:
+      llvm_unreachable("Invalid value for BuiltinOp");
+    case Builtin::BI__builtin_addcb:
+    case Builtin::BI__builtin_addcs:
+    case Builtin::BI__builtin_addc:
+    case Builtin::BI__builtin_addcl:
+    case Builtin::BI__builtin_addcll:
+      Result = X.uadd_ov(Y, DidOverflow1).uadd_ov(CarryIn, DidOverflow2);
+      break;
+    case Builtin::BI__builtin_subcb:
+    case Builtin::BI__builtin_subcs:
+    case Builtin::BI__builtin_subc:
+    case Builtin::BI__builtin_subcl:
+    case Builtin::BI__builtin_subcll:
+      Result = X.usub_ov(Y, DidOverflow1).usub_ov(CarryIn, DidOverflow2);
+      break;
+    }
+
+    APSInt DidOverflow(
+        APInt(Result.getBitWidth(), DidOverflow1 || DidOverflow2));
+    APValue DidOverflowVal{DidOverflow};
+    if (!handleAssignment(Info, E, CarryOut, ResultType, DidOverflowVal))
+      return false;
+    return Success(Result, E);
+  }
   }
 }
 
 /// Determine whether this is a pointer past the end of the complete
 /// object referred to by the lvalue.
 static bool isOnePastTheEndOfCompleteObject(const ASTContext &Ctx,
                                             const LValue &LV) {
   // A null pointer can be viewed as being "past the end" but we don't

clang/test/SemaCXX/builtins-multiprecision.cpp

+// RUN: %clang_cc1 -fsyntax-only -std=c++17 -verify %s
+// expected-no-diagnostics
+
+#include <limits.h>
+
+template<typename T>
+struct Result {
+  T value;
+  T carry;
+  constexpr bool operator==(const Result<T> &Other) {
+    return value == Other.value && carry == Other.carry;
+  }
+};
+
+template<typename T>
+constexpr Result<T> add(T Lhs, T Rhs, T Carryin)
+{
+  T Carryout = 0;
+  if constexpr(__is_same(T, unsigned char))
+    return { __builtin_addcb(Lhs, Rhs, Carryin, &Carryout), Carryout };
+  else if constexpr(__is_same(T, unsigned short))
+    return { __builtin_addcs(Lhs, Rhs, Carryin, &Carryout), Carryout };
+  else if constexpr(__is_same(T, unsigned int))
+    return { __builtin_addc(Lhs, Rhs, Carryin, &Carryout), Carryout };
+  else if constexpr(__is_same(T, unsigned long))
+    return { __builtin_addcl(Lhs, Rhs, Carryin, &Carryout), Carryout };
+  else if constexpr(__is_same(T, unsigned long long))
+    return { __builtin_addcll(Lhs, Rhs, Carryin, &Carryout), Carryout };
+}
+
+static_assert(add<unsigned char>(0, 0, 0) == Result<unsigned char>{0, 0});
+static_assert(add<unsigned char>(0, 0, 1) == Result<unsigned char>{1, 0});
+static_assert(add<unsigned char>(UCHAR_MAX - 1, 1, 1) == Result<unsigned char>{0, 1});
+static_assert(add<unsigned char>(UCHAR_MAX, 1, 0) == Result<unsigned char>{0, 1});
+static_assert(add<unsigned char>(UCHAR_MAX, 1, 1) == Result<unsigned char>{1, 1});
+
+static_assert(add<unsigned short>(0, 0, 0) == Result<unsigned short>{0, 0});
+static_assert(add<unsigned short>(0, 0, 1) == Result<unsigned short>{1, 0});
+static_assert(add<unsigned short>(USHRT_MAX - 1, 1, 1) == Result<unsigned short>{0, 1});
+static_assert(add<unsigned short>(USHRT_MAX, 1, 0) == Result<unsigned short>{0, 1});
+static_assert(add<unsigned short>(USHRT_MAX, 1, 1) == Result<unsigned short>{1, 1});
+
+static_assert(add<unsigned int>(0, 0, 0) == Result<unsigned int>{0, 0});
+static_assert(add<unsigned int>(0, 0, 1) == Result<unsigned int>{1, 0});
+static_assert(add<unsigned int>(UINT_MAX - 1, 1, 1) == Result<unsigned int>{0, 1});
+static_assert(add<unsigned int>(UINT_MAX, 1, 0) == Result<unsigned int>{0, 1});
+static_assert(add<unsigned int>(UINT_MAX, 1, 1) == Result<unsigned int>{1, 1});
+
+static_assert(add<unsigned long>(0, 0, 0) == Result<unsigned long>{0, 0});
+static_assert(add<unsigned long>(0, 0, 1) == Result<unsigned long>{1, 0});
+static_assert(add<unsigned long>(ULONG_MAX - 1, 1, 1) == Result<unsigned long>{0, 1});
+static_assert(add<unsigned long>(ULONG_MAX, 1, 0) == Result<unsigned long>{0, 1});
+static_assert(add<unsigned long>(ULONG_MAX, 1, 1) == Result<unsigned long>{1, 1});
+
+static_assert(add<unsigned long long>(0, 0, 0) == Result<unsigned long long>{0, 0});
+static_assert(add<unsigned long long>(0, 0, 1) == Result<unsigned long long>{1, 0});
+static_assert(add<unsigned long long>(ULLONG_MAX - 1, 1, 1) == Result<unsigned long long>{0, 1});
+static_assert(add<unsigned long long>(ULLONG_MAX, 1, 0) == Result<unsigned long long>{0, 1});
+static_assert(add<unsigned long long>(ULLONG_MAX, 1, 1) == Result<unsigned long long>{1, 1});
+
+template<typename T>
+constexpr Result<T> sub(T Lhs, T Rhs, T Carryin)
+{
+  T Carryout = 0;
+  if constexpr(__is_same(T, unsigned char))
+    return { __builtin_subcb(Lhs, Rhs, Carryin, &Carryout), Carryout };
+  else if constexpr(__is_same(T, unsigned short))
+    return { __builtin_subcs(Lhs, Rhs, Carryin, &Carryout), Carryout };
+  else if constexpr(__is_same(T, unsigned int))
+    return { __builtin_subc(Lhs, Rhs, Carryin, &Carryout), Carryout };
+  else if constexpr(__is_same(T, unsigned long))
+    return { __builtin_subcl(Lhs, Rhs, Carryin, &Carryout), Carryout };
+  else if constexpr(__is_same(T, unsigned long long))
+    return { __builtin_subcll(Lhs, Rhs, Carryin, &Carryout), Carryout };
+}
+
+static_assert(sub<unsigned char>(0, 0, 0) == Result<unsigned char>{0, 0});
+static_assert(sub<unsigned char>(0, 0, 1) == Result<unsigned char>{UCHAR_MAX, 1});
+static_assert(sub<unsigned char>(0, 1, 0) == Result<unsigned char>{UCHAR_MAX, 1});
+static_assert(sub<unsigned char>(0, 1, 1) == Result<unsigned char>{UCHAR_MAX - 1, 1});
+static_assert(sub<unsigned char>(1, 0, 0) == Result<unsigned char>{1, 0});
+
+static_assert(sub<unsigned short>(0, 0, 0) == Result<unsigned short>{0, 0});
+static_assert(sub<unsigned short>(0, 0, 1) == Result<unsigned short>{USHRT_MAX, 1});
+static_assert(sub<unsigned short>(0, 1, 0) == Result<unsigned short>{USHRT_MAX, 1});
+static_assert(sub<unsigned short>(0, 1, 1) == Result<unsigned short>{USHRT_MAX - 1, 1});
+static_assert(sub<unsigned short>(1, 0, 0) == Result<unsigned short>{1, 0});
+
+static_assert(sub<unsigned int>(0, 0, 0) == Result<unsigned int>{0, 0});
+static_assert(sub<unsigned int>(0, 0, 1) == Result<unsigned int>{UINT_MAX, 1});
+static_assert(sub<unsigned int>(0, 1, 0) == Result<unsigned int>{UINT_MAX, 1});
+static_assert(sub<unsigned int>(0, 1, 1) == Result<unsigned int>{UINT_MAX - 1, 1});
+static_assert(sub<unsigned int>(1, 0, 0) == Result<unsigned int>{1, 0});
+
+static_assert(sub<unsigned long>(0, 0, 0) == Result<unsigned long>{0, 0});
+static_assert(sub<unsigned long>(0, 0, 1) == Result<unsigned long>{ULONG_MAX, 1});
+static_assert(sub<unsigned long>(0, 1, 0) == Result<unsigned long>{ULONG_MAX, 1});
+static_assert(sub<unsigned long>(0, 1, 1) == Result<unsigned long>{ULONG_MAX - 1, 1});
+static_assert(sub<unsigned long>(1, 0, 0) == Result<unsigned long>{1, 0});
+
+static_assert(sub<unsigned long long>(0, 0, 0) == Result<unsigned long long>{0, 0});
+static_assert(sub<unsigned long long>(0, 0, 1) == Result<unsigned long long>{ULLONG_MAX, 1});
+static_assert(sub<unsigned long long>(0, 1, 0) == Result<unsigned long long>{ULLONG_MAX, 1});
+static_assert(sub<unsigned long long>(0, 1, 1) == Result<unsigned long long>{ULLONG_MAX - 1, 1});
+static_assert(sub<unsigned long long>(1, 0, 0) == Result<unsigned long long>{1, 0});