CodeGen: Improve generated IR for __builtin_mul_overflow(uint, uint, int)

[tstellar]

Summary

Add a special case for handling builtin_mul_overflow with unsigned
inputs and a signed output to avoid emitting the muloti4 library
call on x86_64. muloti4 is not implemented in libgcc, so avoiding
this call fixes compilation of some programs that call
builtin_mul_overflow with these arguments.

For example, this fixes the build of cpio with clang, which includes code from
gnulib that calls __builtin_mul_overflow with these argument types.

[tstellar]

Remove stray comment.

[vsk]

How were you able to show that the specialized IRGen is equivalent to the generic kind? I tried doing this with direct inspection (https://godbolt.org/z/o5WEn3), but wasn't able to convince myself. In the past I used a test driver to compare the before/after compiler output -- you might find that useful (https://gist.github.com/vedantk/3eb9c88f82e5c32f2e590555b4af5081).

clang/test/CodeGen/builtins-overflow.c

123

Could you add a test for the volatile result case?

[tstellar]

In D84405#2170110, @vsk wrote:

How were you able to show that the specialized IRGen is equivalent to the generic kind? I tried doing this with direct inspection (https://godbolt.org/z/o5WEn3), but wasn't able to convince myself. In the past I used a test driver to compare the before/after compiler output -- you might find that useful (https://gist.github.com/vedantk/3eb9c88f82e5c32f2e590555b4af5081).

I compared with what gcc was generating and it looked similar (although my x86 assembly knowledge is not great), but I will give your test driver a try, thanks.

[tstellar]

Add 64-bit test.

[tstellar]

This is the test driver I used for testing. I compared the clang 11 + this patch with gcc 10 and saw no differences: https://gist.github.com/tstellar/80dae2ab8a18d810b10b8e42777f4fe4

[tstellar]

Here is the assembly comparison for the 64-bit test I added between gcc and clang trunk + patch: https://reviews.llvm.org/P8227

[vsk]

Thanks, looks good to me with a small test addition.

clang/test/CodeGen/builtins-overflow.c

123

I think this is still missing?

[tstellar]

Add volatile test.

[tstellar]

clang/test/CodeGen/builtins-overflow.c

123

Yes, I forgot to add this, there is one in the latest patch now.

[vsk]

Thanks!

clang/lib/CodeGen/CGBuiltin.cpp

RValue CodeGenFunction::emitBuiltinOSLogFormat(const CallExpr &E) {
   const CGFunctionInfo &FI =
       CGM.getTypes().arrangeBuiltinFunctionCall(Ctx.VoidTy, Args);
   llvm::Function *F = CodeGenFunction(CGM).generateBuiltinOSLogHelperFunction(
       Layout, BufAddr.getAlignment());
   EmitCall(FI, CGCallee::forDirect(F), ReturnValueSlot(), Args);
   return RValue::get(BufAddr.getPointer());
 }
 
+static bool isSpecialUnsignedMultiplySignedResult(
+    unsigned BuiltinID, WidthAndSignedness Op1Info, WidthAndSignedness Op2Info,
+    WidthAndSignedness ResultInfo) {
+  return BuiltinID == Builtin::BI__builtin_mul_overflow &&
+         Op1Info.Width == Op2Info.Width && Op2Info.Width == ResultInfo.Width &&
+         !Op1Info.Signed && !Op2Info.Signed && ResultInfo.Signed;
+}
+
+static RValue EmitCheckedUnsignedMultiplySignedResult(
+    CodeGenFunction &CGF, const clang::Expr *Op1, WidthAndSignedness Op1Info,
+    const clang::Expr *Op2, WidthAndSignedness Op2Info,
+    const clang::Expr *ResultArg, QualType ResultQTy,
+    WidthAndSignedness ResultInfo) {
+  assert(isSpecialUnsignedMultiplySignedResult(
+             Builtin::BI__builtin_mul_overflow, Op1Info, Op2Info, ResultInfo) &&
+         "Cannot specialize this multiply");
+
+  llvm::Value *V1 = CGF.EmitScalarExpr(Op1);
+  llvm::Value *V2 = CGF.EmitScalarExpr(Op2);
+
+  llvm::Value *HasOverflow;
+  llvm::Value *Result = EmitOverflowIntrinsic(
+      CGF, llvm::Intrinsic::umul_with_overflow, V1, V2, HasOverflow);
+
+  // The intrinsic call will detect overflow when the value is > UINT_MAX,
+  // however, since the original builtin had a signed result, we need to report
+  // an overflow when the result is greater than INT_MAX.
+  auto IntMax = llvm::APInt::getSignedMaxValue(ResultInfo.Width);
+  llvm::Value *IntMaxValue = llvm::ConstantInt::get(Result->getType(), IntMax);
+
+  llvm::Value *IntMaxOverflow = CGF.Builder.CreateICmpUGT(Result, IntMaxValue);
+  HasOverflow = CGF.Builder.CreateOr(HasOverflow, IntMaxOverflow);
+
+  bool isVolatile =
+      ResultArg->getType()->getPointeeType().isVolatileQualified();
+  Address ResultPtr = CGF.EmitPointerWithAlignment(ResultArg);
+  CGF.Builder.CreateStore(CGF.EmitToMemory(Result, ResultQTy), ResultPtr,
+                          isVolatile);
+  return RValue::get(HasOverflow);
+}
+
 /// Determine if a binop is a checked mixed-sign multiply we can specialize.
 static bool isSpecialMixedSignMultiply(unsigned BuiltinID,
                                        WidthAndSignedness Op1Info,
                                        WidthAndSignedness Op2Info,
                                        WidthAndSignedness ResultInfo) {
   return BuiltinID == Builtin::BI__builtin_mul_overflow &&
          std::max(Op1Info.Width, Op2Info.Width) >= ResultInfo.Width &&
          Op1Info.Signed != Op2Info.Signed;
case Builtin::BI__builtin_mul_overflow: {
 
     // Handle mixed-sign multiplication as a special case, because adding
     // runtime or backend support for our generic irgen would be too expensive.
     if (isSpecialMixedSignMultiply(BuiltinID, LeftInfo, RightInfo, ResultInfo))
       return EmitCheckedMixedSignMultiply(*this, LeftArg, LeftInfo, RightArg,
                                           RightInfo, ResultArg, ResultQTy,
                                           ResultInfo);
 
+    if (isSpecialUnsignedMultiplySignedResult(BuiltinID, LeftInfo, RightInfo,
+                                              ResultInfo))
+      return EmitCheckedUnsignedMultiplySignedResult(
+          *this, LeftArg, LeftInfo, RightArg, RightInfo, ResultArg, ResultQTy,
+          ResultInfo);
+
     WidthAndSignedness EncompassingInfo =
         EncompassingIntegerType({LeftInfo, RightInfo, ResultInfo});
 
     llvm::Type *EncompassingLLVMTy =
         llvm::IntegerType::get(CGM.getLLVMContext(), EncompassingInfo.Width);
 
     llvm::Type *ResultLLVMTy = CGM.getTypes().ConvertType(ResultQTy);
 

clang/test/CodeGen/builtins-overflow.c

 // Test CodeGen for Security Check Overflow Builtins.
 // rdar://13421498
 
-// RUN: %clang_cc1 -triple "i686-unknown-unknown"   -emit-llvm -x c %s -o - | FileCheck %s
-// RUN: %clang_cc1 -triple "x86_64-unknown-unknown" -emit-llvm -x c %s -o - | FileCheck %s
-// RUN: %clang_cc1 -triple "x86_64-mingw32"         -emit-llvm -x c %s -o - | FileCheck %s
+// RUN: %clang_cc1 -triple "i686-unknown-unknown"   -emit-llvm -x c %s -o - | FileCheck -DLONG_TYPE=i32 -DLONG_MAX=2147483647 %s
+// RUN: %clang_cc1 -triple "x86_64-unknown-unknown" -emit-llvm -x c %s -o - | FileCheck -DLONG_TYPE=i64 -DLONG_MAX=9223372036854775807 %s
+// RUN: %clang_cc1 -triple "x86_64-mingw32"         -emit-llvm -x c %s -o - | FileCheck -DLONG_TYPE=i32 -DLONG_MAX=2147483647 %s
 
 extern unsigned UnsignedErrorCode;
 extern unsigned long UnsignedLongErrorCode;
 extern unsigned long long UnsignedLongLongErrorCode;
 extern int IntErrorCode;
 extern long LongErrorCode;
 extern long long LongLongErrorCode;
 void overflowed(void);
unsigned test_mul_overflow_uint_uint_uint(unsigned x, unsigned y) {
   // CHECK: store i32 [[Q]], i32*
   // CHECK: br i1 [[C]]
   unsigned r;
   if (__builtin_mul_overflow(x, y, &r))
     overflowed();
   return r;
 }
 
+int test_mul_overflow_uint_uint_int(unsigned x, unsigned y) {
+  // CHECK-LABEL: define {{(dso_local )?}}i32 @test_mul_overflow_uint_uint_int
+  // CHECK: [[S:%.+]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 %{{.+}}, i32 %{{.+}})
+  // CHECK-DAG: [[Q:%.+]] = extractvalue { i32, i1 } [[S]], 0
+  // CHECK-DAG: [[C:%.+]] = extractvalue { i32, i1 } [[S]], 1
+  // CHECK: [[C1:%.+]] = icmp ugt i32 [[Q]], 2147483647
+  // CHECK: [[C2:%.+]] = or i1 [[C]], [[C1]]
+  // CHECK: store i32 [[Q]], i32*
+  // CHECK: br i1 [[C2]]
+  int r;
+  if (__builtin_mul_overflow(x, y, &r))
+    overflowed();
+  return r;
+}
+
+int test_mul_overflow_uint_uint_int_volatile(unsigned x, unsigned y) {
+  // CHECK-LABEL: define {{(dso_local )?}}i32 @test_mul_overflow_uint_uint_int_volatile
+  // CHECK: [[S:%.+]] = call { i32, i1 } @llvm.umul.with.overflow.i32(i32 %{{.+}}, i32 %{{.+}})
+  // CHECK-DAG: [[Q:%.+]] = extractvalue { i32, i1 } [[S]], 0
+  // CHECK-DAG: [[C:%.+]] = extractvalue { i32, i1 } [[S]], 1
+  // CHECK: [[C1:%.+]] = icmp ugt i32 [[Q]], 2147483647
+  // CHECK: [[C2:%.+]] = or i1 [[C]], [[C1]]
+  // CHECK: store volatile i32 [[Q]], i32*
+  // CHECK: br i1 [[C2]]
+  volatile int r;
+  if (__builtin_mul_overflow(x, y, &r))
+    overflowed();
+  return r;
+}
+
+long test_mul_overflow_ulong_ulong_long(unsigned long x, unsigned long y) {
+  // CHECK-LABEL: @test_mul_overflow_ulong_ulong_long
+  // CHECK: [[S:%.+]] =  call { [[LONG_TYPE]], i1 } @llvm.umul.with.overflow.[[LONG_TYPE]]([[LONG_TYPE]] %{{.+}}, [[LONG_TYPE]] %{{.+}})
+  // CHECK-DAG: [[Q:%.+]] = extractvalue { [[LONG_TYPE]], i1 } [[S]], 0
+  // CHECK-DAG: [[C:%.+]] = extractvalue { [[LONG_TYPE]], i1 } [[S]], 1
+  // CHECK: [[C1:%.+]] = icmp ugt [[LONG_TYPE]] [[Q]], [[LONG_MAX]]
+  // CHECK: [[C2:%.+]] = or i1 [[C]], [[C1]]
+  // LONG64: store [[LONG_TYPE]] [[Q]], [[LONG_TYPE]]*
+  // LONG64: br i1 [[C2]]
+  long r;
+  if (__builtin_mul_overflow(x, y, &r))
+    overflowed();
+  return r;
+}
+
 int test_mul_overflow_int_int_int(int x, int y) {
   // CHECK-LABEL: define {{(dso_local )?}}i32 @test_mul_overflow_int_int_int
   // CHECK-NOT: ext
   // CHECK: [[S:%.+]] = call { i32, i1 } @llvm.smul.with.overflow.i32(i32 %{{.+}}, i32 %{{.+}})
   // CHECK-DAG: [[C:%.+]] = extractvalue { i32, i1 } [[S]], 1
   // CHECK-DAG: [[Q:%.+]] = extractvalue { i32, i1 } [[S]], 0
   // CHECK: store i32 [[Q]], i32*
   // CHECK: br i1 [[C]]