[sema] Disallow __builtin_mul_overflow under special condition.

[FreddyYe]

update commit message

[FreddyYe]

https://gcc.godbolt.org/z/ex9MYan84 is the example bug this patch to fix.
https://gcc.godbolt.org/z/Mjsn5n99h is the reason why I'd like to abort this builtin on this special input combination.

[FreddyYe]

rebase and refactor clang-format and clang-tidy.

[erichkeane]

This seems lie an incomplete fix. Is this the ONLY configuration that this has trouble with?

Also, the error message seems awkward, @aaron.ballman : Can you suggest a better spelling?

[aaron.ballman]

clang/lib/Sema/SemaChecking.cpp

334–335

340

Isn't the result type a pointer type?

clang/test/Sema/builtins-overflow.c

45

Yeah, this diagnostic really doesn't tell me what's going wrong with the code or how to fix it. Do we basically want to prevent using larger-than-64-bit argument types with mixed signs? Or are there other problematic circumstances?

[FreddyYe]

Address comments. I'll refactor clang-format later. Pls help review the new condition and diagnostic.

[FreddyYe]

Addressed. THX review!

clang/test/Sema/builtins-overflow.c

45

Yes, let me try to refine. I can explain more what happened to such input combination.
According to gcc's the definition on this builtin: https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html
'These built-in functions promote the first two operands into infinite precision signed type and perform multiply on those promoted operands. The result is then cast to the type the third pointer argument points to and stored there.'

Since signing integer has a smaller range than unsigned integer. And now the API in compiler-rt (__muloti4) to checking 128 integer's multiplying is implemented in signed version. So the overflow max absolute value it can check is 2^127. When the result input is larger equal than 128 bits, __muloti4 has no usage. We should prevent this situation for now. Or the backend will crush as the example shows.

I found the input operand doesn't need both of them larger than 64 bits, but just the sum of their larger 128. I'll refine in my patch.

[FreddyYe]

clang/include/clang/Basic/DiagnosticSemaKinds.td

8351–8353

The new diagnostic is here. Forgot to update tests since I've not rebuilt completely.

[FreddyYe]

update lit test, clang-format, if condition, diagnostic

[lebedev.ri]

I don't personally care, but i think this diag doesn't make sense.
What is "backend"? Which one? All of them? What happens when one, but not all of them supports it?
What if i don't intend to codegen this into an assembly, but only want to produce the IR?

[FreddyYe]

In D107420#2927856, @lebedev.ri wrote:

I don't personally care, but i think this diag doesn't make sense.
What is "backend"? Which one? All of them? What happens when one, but not all of them supports it?
What if i don't intend to codegen this into an assembly, but only want to produce the IR?

THX for comment. The root cause unable to support this is same as the code added before (line 328-329). I'm suppossing we can view this patch as a supplementary patch of the old one?

[craig.topper]

I put up a patch for a simple fix for this in the backend. https://reviews.llvm.org/D107581 The generated code is not optimal, but maybe better than frontend workarounds.

[aaron.ballman]

In D107420#2928975, @craig.topper wrote:

I put up a patch for a simple fix for this in the backend. https://reviews.llvm.org/D107581 The generated code is not optimal, but maybe better than frontend workarounds.

Thanks for putting up the backend fix! That's much better than frontend workarounds.

[craig.topper]

In D107420#2929039, @aaron.ballman wrote:

In D107420#2928975, @craig.topper wrote:

I put up a patch for a simple fix for this in the backend. https://reviews.llvm.org/D107581 The generated code is not optimal, but maybe better than frontend workarounds.

Thanks for putting up the backend fix! That's much better than frontend workarounds.

Looks like I may have opened a small can of worms. In 32-bit mode, a __builtin_mul_overflow of _ExtInt(128) producing a signed result generates a call to _muloti4 which neither compiler-rt or libgcc implement in 32-bit mode. In 64-bit mode only compiler-rt implements _muloti4 for x86-64.

[erichkeane]

In D107420#2929115, @craig.topper wrote:

In D107420#2929039, @aaron.ballman wrote:

In D107420#2928975, @craig.topper wrote:

I put up a patch for a simple fix for this in the backend. https://reviews.llvm.org/D107581 The generated code is not optimal, but maybe better than frontend workarounds.

Thanks for putting up the backend fix! That's much better than frontend workarounds.

Looks like I may have opened a small can of worms. In 32-bit mode, a __builtin_mul_overflow of _ExtInt(128) producing a signed result generates a call to _muloti4 which neither compiler-rt or libgcc implement in 32-bit mode. In 64-bit mode only compiler-rt implements _muloti4 for x86-64.

We also lack a proper codegen implementation of 'div' in cases of ints larger than 128. Since _ExtIntis now part of the C23 standard (spelled as _BitInt), we should probably be supporting these as much as we can. I would think we'd have to compose the _muloti and _divoti calls somehow for those.

[FreddyYe]

In D107420#2928975, @craig.topper wrote:

I put up a patch for a simple fix for this in the backend. https://reviews.llvm.org/D107581 The generated code is not optimal, but maybe better than frontend workarounds.

THX for fix! LGTM.

[nickdesaulniers]

In D107420#2929115, @craig.topper wrote:

In D107420#2929039, @aaron.ballman wrote:

In D107420#2928975, @craig.topper wrote:

I put up a patch for a simple fix for this in the backend. https://reviews.llvm.org/D107581 The generated code is not optimal, but maybe better than frontend workarounds.

Thanks for putting up the backend fix! That's much better than frontend workarounds.

Looks like I may have opened a small can of worms. In 32-bit mode, a __builtin_mul_overflow of _ExtInt(128) producing a signed result generates a call to _muloti4 which neither compiler-rt or libgcc implement in 32-bit mode. In 64-bit mode only compiler-rt implements _muloti4 for x86-64.

I think this is also producing references to __mulodi4 for signed long long on 32b targets, see: https://bugs.llvm.org/show_bug.cgi?id=28629.

[craig.topper]

In D107420#2969715, @nickdesaulniers wrote:

In D107420#2929115, @craig.topper wrote:

In D107420#2929039, @aaron.ballman wrote:

In D107420#2928975, @craig.topper wrote:

I put up a patch for a simple fix for this in the backend. https://reviews.llvm.org/D107581 The generated code is not optimal, but maybe better than frontend workarounds.

Thanks for putting up the backend fix! That's much better than frontend workarounds.

Looks like I may have opened a small can of worms. In 32-bit mode, a __builtin_mul_overflow of _ExtInt(128) producing a signed result generates a call to _muloti4 which neither compiler-rt or libgcc implement in 32-bit mode. In 64-bit mode only compiler-rt implements _muloti4 for x86-64.

I think this is also producing references to __mulodi4 for signed long long on 32b targets, see: https://bugs.llvm.org/show_bug.cgi?id=28629.

That's true. I only fixed the case that didn't work with either library.

clang/include/clang/Basic/DiagnosticSemaKinds.td

 def err_overflow_builtin_must_be_int : Error<
   "operand argument to overflow builtin must be an integer (%0 invalid)">;
 def err_overflow_builtin_must_be_ptr_int : Error<
   "result argument to overflow builtin must be a pointer "
   "to a non-const integer (%0 invalid)">;
 def err_overflow_builtin_ext_int_max_size : Error<
   "__builtin_mul_overflow does not support signed _ExtInt operands of more "
   "than %0 bits">;
+def err_overflow_builtin_mul_special_condition_max_size : Error<
+  "when __builtin_mul_overflow's result argument points to unsigned 128 bit integer, pls make sure "
+  "input operands won't produce positive (2^127)~(2^128-1) from two negative integer value. That's "
+  "not supported yet.">;
 
 def err_atomic_load_store_uses_lib : Error<
   "atomic %select{load|store}0 requires runtime support that is not "
   "available for this target">;
 
 def err_nontemporal_builtin_must_be_pointer : Error<
   "address argument to nontemporal builtin must be a pointer (%0 invalid)">;
 def err_nontemporal_builtin_must_be_pointer_intfltptr_or_vector : Error<

clang/lib/Sema/SemaChecking.cpp

 //===- SemaChecking.cpp - Extra Semantic Checking -------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (!PtrTy ||
         << Ty << Arg.get()->getSourceRange();
       return true;
     }
   }
 
   // Disallow signed ExtIntType args larger than 128 bits to mul function until
   // we improve backend support.
   if (BuiltinID == Builtin::BI__builtin_mul_overflow) {
+    const auto LeftTy = TheCall->getArg(0)->getType();
+    const auto RightTy = TheCall->getArg(1)->getType();
+    const auto ResultPointeeTy =
+        TheCall->getArg(2)->getType()->getPointeeType();
+    // Input combination below will also emit an integer value larger than
+    // 128 bits in the backend, disallow same as above.
+    if (!ResultPointeeTy->isSignedIntegerType() &&
+        S.getASTContext().getIntWidth(ResultPointeeTy) == 128 &&
+        ((LeftTy->isSignedIntegerType() ? S.getASTContext().getIntWidth(LeftTy)
+                                        : 0) +
+         (RightTy->isSignedIntegerType()
+              ? S.getASTContext().getIntWidth(RightTy)
+              : 0)) > 128) {
+      return S.Diag(TheCall->getArg(0)->getBeginLoc(),
+                    diag::err_overflow_builtin_mul_special_condition_max_size);
+    }
     for (unsigned I = 0; I < 3; ++I) {
       const auto Arg = TheCall->getArg(I);
       // Third argument will be a pointer.
       auto Ty = I < 2 ? Arg->getType() : Arg->getType()->getPointeeType();
       if (Ty->isExtIntType() && Ty->isSignedIntegerType() &&
           S.getASTContext().getIntWidth(Ty) > 128)
         return S.Diag(Arg->getBeginLoc(),
                       diag::err_overflow_builtin_ext_int_max_size)

clang/test/Sema/builtins-overflow.c

__builtin_add_overflow(1, 1, &q);  // expected-error {{result argument to overflow builtin must be a pointer to a non-const integer ('const unsigned int *' invalid)}}
     _Bool status = __builtin_mul_overflow(x, y, &result); // expect ok
   }
   {
     _ExtInt(129) x = 1;
     _ExtInt(129) y = 1;
     _ExtInt(129) result;
     _Bool status = __builtin_mul_overflow(x, y, &result); // expected-error {{__builtin_mul_overflow does not support signed _ExtInt operands of more than 128 bits}}
   }
+  {
+    _ExtInt(128) x = 1;
+    _ExtInt(128) y = 1;
+    unsigned _ExtInt(128) result;
+    _Bool status = __builtin_mul_overflow(x, y, &result); // expected-error {{when __builtin_mul_overflow's result argument points to unsigned 128 bit integer, pls make sure input operands won't produce positive (2^127)~(2^128-1) from two negative integer value. That's not supported yet.}}
+  }
+  {
+    _ExtInt(65) x = 1;
+    _ExtInt(64) y = 1;
+    unsigned _ExtInt(128) result;
+    _Bool status = __builtin_mul_overflow(x, y, &result); // expected-error {{when __builtin_mul_overflow's result argument points to unsigned 128 bit integer, pls make sure input operands won't produce positive (2^127)~(2^128-1) from two negative integer value. That's not supported yet.}}
+  }
+  {
+    _ExtInt(64) x = 1;
+    _ExtInt(64) y = 1;
+    unsigned _ExtInt(128) result;
+    _Bool status = __builtin_mul_overflow(x, y, &result); // expected ok
+  }
 }