[CodeGen] Specialize mixed-sign mul-with-overflow (fix PR34920)

[vsk]

Summary

This patch introduces a specialized way to lower overflow-checked
multiplications with mixed-sign operands. This fixes link failures and
ICEs on code like this:

void mul(int64_t a, uint64_t b) {
  int64_t res;
  __builtin_mul_overflow(a, b, &res);
}

The generic checked-binop irgen would use a 65-bit multiplication
intrinsic here, which requires runtime support for _muloti4 (128-bit
multiplication), and therefore fails to link on i386. To get an ICE
on x86_64, change the example to use int128_t / uint128_t.

Adding runtime and backend support for 65-bit or 129-bit checked
multiplication on all of our supported targets is infeasible.

This patch solves the problem by using simpler, specialized irgen for
the mixed-sign case.

llvm.org/PR34920, rdar://34963321

Testing: Apart from check-clang, I compared the output from this fairly
comprehensive test driver using unpatched & patched clangs:
https://gist.github.com/vedantk/3eb9c88f82e5c32f2e590555b4af5081

[vsk]

• Make sure the result can be stored into the result ptr.

[efriedma]

test/CodeGen/builtins-overflow.c

402

I think the rules for __builtin_mul_overflow say you have to check whether the truncate changes the value of the result.

Missing testcases for the case where the result is unsigned.

[vsk]

• Handle unsigned result types.
• Extend the test driver to validate 54 different combinations of signed, unsigned, and result types: https://gist.github.com/vedantk/3eb9c88f82e5c32f2e590555b4af5081
• Don't try to specialize irgen for cases where the result type is wider than the operand type.

test/CodeGen/builtins-overflow.c

402

Thanks for the catch. I've updated my test driver to catch cases like this.

[efriedma]

LGTM

lib/CodeGen/CGBuiltin.cpp

912

zext() rather than zextOrSelf().

[vsk]

Thanks for the review!

lib/CodeGen/CGBuiltin.cpp

912

Will fix before committing.

lib/CodeGen/CGBuiltin.cpp

RValue CodeGenFunction::emitBuiltinOSLogFormat(const CallExpr &E) {
   if (!RetainableOperands.empty() && getLangOpts().ObjCAutoRefCount &&
       CGM.getCodeGenOpts().OptimizationLevel != 0)
     for (llvm::Value *Object : RetainableOperands)
       pushFullExprCleanup<CallObjCArcUse>(getARCCleanupKind(), Object);
 
   return RValue::get(BufAddr.getPointer());
 }
 
+/// Determine whether a binop is a checked mixed-sign multiply.
+static bool isCheckedMixedSignMultiply(unsigned BuiltinID,
+                                       WidthAndSignedness Op1Info,
+                                       WidthAndSignedness Op2Info) {
+  return BuiltinID == Builtin::BI__builtin_mul_overflow &&
+         Op1Info.Width == Op2Info.Width && Op1Info.Signed != Op2Info.Signed;
+}
+
+/// Emit a checked mixed-sign multiply. This is a cheaper specialization of
+/// the generic checked-binop irgen.
+static RValue
+EmitCheckedMixedSignMultiply(CodeGenFunction &CGF, const clang::Expr *Op1,
+                             WidthAndSignedness Op1Info, const clang::Expr *Op2,
+                             WidthAndSignedness Op2Info,
+                             const clang::Expr *ResultArg, QualType ResultQTy) {
+  assert(isCheckedMixedSignMultiply(Builtin::BI__builtin_mul_overflow, Op1Info,
+                                    Op2Info) &&
+         "Not a mixed-sign multipliction");
+
+  // Emit the signed and unsigned operands.
+  const clang::Expr *SignedOp = Op1Info.Signed ? Op1 : Op2;
+  const clang::Expr *UnsignedOp = Op1Info.Signed ? Op2 : Op1;
+  llvm::Value *Signed = CGF.EmitScalarExpr(SignedOp);
+  llvm::Value *Unsigned = CGF.EmitScalarExpr(UnsignedOp);
+
+  llvm::Type *OpTy = Signed->getType();
+  llvm::Value *Zero = llvm::Constant::getNullValue(OpTy);
+  Address ResultPtr = CGF.EmitPointerWithAlignment(ResultArg);
+
+  // Take the absolute value of the signed operand.
+  llvm::Value *IsNegative = CGF.Builder.CreateICmpSLT(Signed, Zero);
+  llvm::Value *AbsOfNegative = CGF.Builder.CreateSub(Zero, Signed);
+  llvm::Value *AbsSigned =
+      CGF.Builder.CreateSelect(IsNegative, AbsOfNegative, Signed);
+
+  // Perform a checked unsigned multiplication.
+  llvm::Value *UnsignedOverflow;
+  llvm::Value *UnsignedResult =
+      EmitOverflowIntrinsic(CGF, llvm::Intrinsic::umul_with_overflow, AbsSigned,
+                            Unsigned, UnsignedOverflow);
+
+  // Signed overflow occurs if the result is greater than INT_MAX or lesser
+  // than INT_MIN, i.e when |Result| > (INT_MAX + IsNegative).
+  llvm::Value *IntMax = llvm::ConstantInt::get(
+      OpTy, llvm::APInt::getSignedMaxValue(Op1Info.Width));
+  llvm::Value *MaxResult =
+      CGF.Builder.CreateAdd(IntMax, CGF.Builder.CreateZExt(IsNegative, OpTy));
+  llvm::Value *SignedOverflow =
+      CGF.Builder.CreateICmpUGT(UnsignedResult, MaxResult);
+
+  // Prepare the signed result (possibly by negating it).
+  llvm::Value *NegativeResult = CGF.Builder.CreateSub(Zero, UnsignedResult);
+  llvm::Value *Overflow =
+      CGF.Builder.CreateOr(UnsignedOverflow, SignedOverflow);
+  llvm::Value *Result =
+      CGF.Builder.CreateSelect(IsNegative, NegativeResult, UnsignedResult);
+
+  bool isVolatile =
+      ResultArg->getType()->getPointeeType().isVolatileQualified();
+  CGF.Builder.CreateStore(CGF.EmitToMemory(Result, ResultQTy), ResultPtr,
+                          isVolatile);
+  return RValue::get(Overflow);
+}
+
 RValue CodeGenFunction::EmitBuiltinExpr(const FunctionDecl *FD,
                                         unsigned BuiltinID, const CallExpr *E,
                                         ReturnValueSlot ReturnValue) {
   // See if we can constant fold this builtin.  If so, don't emit it at all.
   Expr::EvalResult Result;
   if (E->EvaluateAsRValue(Result, CGM.getContext()) &&
       !Result.hasSideEffects()) {
     if (Result.Val.isInt())
       return RValue::get(llvm::ConstantInt::get(getLLVMContext(),
                                                 Result.Val.getInt()));
     if (Result.Val.isFloat())
       return RValue::get(llvm::ConstantFP::get(getLLVMContext(),
                                                Result.Val.getFloat()));
   }
 
clang::QualType ResultQTy =
         ResultArg->getType()->castAs<PointerType>()->getPointeeType();
 
     WidthAndSignedness LeftInfo =
         getIntegerWidthAndSignedness(CGM.getContext(), LeftArg->getType());
     WidthAndSignedness RightInfo =
         getIntegerWidthAndSignedness(CGM.getContext(), RightArg->getType());
     WidthAndSignedness ResultInfo =
         getIntegerWidthAndSignedness(CGM.getContext(), ResultQTy);
+
+    // Handle mixed-sign multiplication as a special case, because adding
+    // runtime or backend support for our generic irgen would be too expensive.
+    if (isCheckedMixedSignMultiply(BuiltinID, LeftInfo, RightInfo))
+      return EmitCheckedMixedSignMultiply(*this, LeftArg, LeftInfo, RightArg,
+                                          RightInfo, ResultArg, ResultQTy);
+
     WidthAndSignedness EncompassingInfo =
         EncompassingIntegerType({LeftInfo, RightInfo, ResultInfo});
 
     llvm::Type *EncompassingLLVMTy =
         llvm::IntegerType::get(CGM.getLLVMContext(), EncompassingInfo.Width);
 
     llvm::Type *ResultLLVMTy = CGM.getTypes().ConvertType(ResultQTy);
 

test/CodeGen/builtins-overflow.c

 long long test_smulll_overflow(long long x, long long y) {
 // CHECK: @test_smulll_overflow
 // CHECK: %{{.+}} = call { i64, i1 } @llvm.smul.with.overflow.i64(i64 %{{.+}}, i64 %{{.+}})
   long long result;
   if (__builtin_smulll_overflow(x, y, &result))
     return LongLongErrorCode;
   return result;
 }
+
+int test_mixed_sign_mull_overflow(int x, unsigned y) {
+// CHECK: @test_mixed_sign_mull_overflow
+// CHECK:       [[IsNeg:%.*]] = icmp slt i32 [[Op1:%.*]], 0
+// CHECK-NEXT:  [[Signed:%.*]] = sub i32 0, [[Op1]]
+// CHECK-NEXT:  [[AbsSigned:%.*]] = select i1 [[IsNeg]], i32 [[Signed]], i32 [[Op1]]
+// CHECK-NEXT:  call { i32, i1 } @llvm.umul.with.overflow.i32(i32 [[AbsSigned]], i32 %{{.*}})
+// CHECK-NEXT:  [[UnsignedOFlow:%.*]] = extractvalue { i32, i1 } %{{.*}}, 1
+// CHECK-NEXT:  [[UnsignedResult:%.*]] = extractvalue { i32, i1 } %{{.*}}, 0
+// CHECK-NEXT:  [[IsNegZext:%.*]] = zext i1 [[IsNeg]] to i32
+// CHECK-NEXT:  [[MaxResult:%.*]] = add i32 2147483647, [[IsNegZext]]
+// CHECK-NEXT:  [[SignedOFlow:%.*]] = icmp ugt i32 [[UnsignedResult]], [[MaxResult]]
+// CHECK-NEXT:  [[NegativeResult:%.*]] = sub i32 0, [[UnsignedResult]]
+// CHECK-NEXT:  [[OFlow:%.*]] = or i1 [[UnsignedOFlow]], [[SignedOFlow]]
+// CHECK-NEXT:  [[Result:%.*]] = select i1 [[IsNeg]], i32 [[NegativeResult]], i32 [[UnsignedResult]]
+// CHECK-NEXT:  store i32 [[Result]], i32* %{{.*}}, align 4
+// CHECK:       br i1 [[OFlow]]
+
+  int result;
+  if (__builtin_mul_overflow(x, y, &result))
+    return LongErrorCode;
+  return result;
+}
+
+int test_mixed_sign_mull_overflow_swapped(int x, unsigned y) {
+// CHECK: @test_mixed_sign_mull_overflow_swapped
+// CHECK:  call { i32, i1 } @llvm.umul.with.overflow.i32
+// CHECK:  add i32 2147483647
+  int result;
+  if (__builtin_mul_overflow(y, x, &result))
+    return LongErrorCode;
+  return result;
+}
+
+long long test_mixed_sign_mulll_overflow(long long x, unsigned long long y) {
+// CHECK: @test_mixed_sign_mulll_overflow
+// CHECK:  call { i64, i1 } @llvm.umul.with.overflow.i64
+// CHECK:  add i64 92233720368547
+  long long result;
+  if (__builtin_mul_overflow(x, y, &result))
+    return LongLongErrorCode;
+  return result;
+}
+
+long long test_mixed_sign_mulll_overflow_swapped(long long x, unsigned long long y) {
+// CHECK: @test_mixed_sign_mulll_overflow_swapped
+// CHECK:  call { i64, i1 } @llvm.umul.with.overflow.i64
+// CHECK:  add i64 92233720368547
+  long long result;
+  if (__builtin_mul_overflow(y, x, &result))
+    return LongLongErrorCode;
+  return result;
+}