Index: lib/Transforms/InstCombine/InstCombine.h =================================================================== --- lib/Transforms/InstCombine/InstCombine.h +++ lib/Transforms/InstCombine/InstCombine.h @@ -284,6 +284,7 @@ bool WillNotOverflowUnsignedAdd(Value *LHS, Value *RHS, Instruction *CxtI); bool WillNotOverflowSignedSub(Value *LHS, Value *RHS, Instruction *CxtI); bool WillNotOverflowUnsignedSub(Value *LHS, Value *RHS, Instruction *CxtI); + bool WillNotOverflowSignedMul(Value *LHS, Value *RHS, Instruction *CxtI); Value *EmitGEPOffset(User *GEP); Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN); Value *EvaluateInDifferentElementOrder(Value *V, ArrayRef Mask); @@ -330,6 +331,20 @@ return &I; } + /// Creates a result-struct for an overflow intrinsic \p II with a given + /// \p Result and a constant \p Overflow value. If \p ReUseName is true the + /// \p Result's name is taken from \p II. + Instruction *CreateOverflowResult(IntrinsicInst *II, Value *Result, + bool Overflow, bool ReUseName = true) { + if (ReUseName) + Result->takeName(II); + Constant *V[] = { UndefValue::get(Result->getType()), + Overflow ? Builder->getTrue() : Builder->getFalse() }; + StructType *ST = cast(II->getType()); + Constant *Struct = ConstantStruct::get(ST, V); + return InsertValueInst::Create(Struct, Result, 0); + } + // EraseInstFromFunction - When dealing with an instruction that has side // effects or produces a void value, we can't rely on DCE to delete the // instruction. Instead, visit methods should return the value returned by Index: lib/Transforms/InstCombine/InstCombineAddSub.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineAddSub.cpp +++ lib/Transforms/InstCombine/InstCombineAddSub.cpp @@ -1008,6 +1008,32 @@ return false; } +/// \brief Return true if we can prove that: +/// (mul LHS, RHS) === (mul nsw LHS, RHS) +bool InstCombiner::WillNotOverflowSignedMul(Value *LHS, Value *RHS, + Instruction *CxtI) { + if (IntegerType *IT = dyn_cast(LHS->getType())) { + unsigned BitWidth = IT->getBitWidth(); + unsigned SignBits = ComputeNumSignBits(LHS, 0, CxtI) + + ComputeNumSignBits(RHS, 0, CxtI); + if (SignBits > BitWidth + 1) + return true; + + if (SignBits == BitWidth + 1) { + // The smallest negative numbers in this case still overflow. + // E.g. mul i16 with 17 sign bits: 0xff00 * 0xff80 = 0x8000 + bool LHSNonNegative, LHSNegative; + bool RHSNonNegative, RHSNegative; + ComputeSignBit(LHS, LHSNonNegative, LHSNegative, DL, 0, AT, CxtI, DT); + ComputeSignBit(RHS, RHSNonNegative, RHSNegative, DL, 0, AT, CxtI, DT); + if (LHSNonNegative || RHSNonNegative) + // No overflow if at least one side is not negative. + return true; + } + } + return false; +} + // Checks if any operand is negative and we can convert add to sub. // This function checks for following negative patterns // ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C)) Index: lib/Transforms/InstCombine/InstCombineCalls.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineCalls.cpp +++ lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -369,29 +369,14 @@ if (LHSKnownNegative && RHSKnownNegative) { // The sign bit is set in both cases: this MUST overflow. // Create a simple add instruction, and insert it into the struct. - Value *Add = Builder->CreateAdd(LHS, RHS); - Add->takeName(&CI); - Constant *V[] = { - UndefValue::get(LHS->getType()), - ConstantInt::getTrue(II->getContext()) - }; - StructType *ST = cast(II->getType()); - Constant *Struct = ConstantStruct::get(ST, V); - return InsertValueInst::Create(Struct, Add, 0); + return CreateOverflowResult(II, Builder->CreateAdd(LHS, RHS), true, + /*ReUseName*/true); } if (LHSKnownPositive && RHSKnownPositive) { // The sign bit is clear in both cases: this CANNOT overflow. // Create a simple add instruction, and insert it into the struct. - Value *Add = Builder->CreateNUWAdd(LHS, RHS); - Add->takeName(&CI); - Constant *V[] = { - UndefValue::get(LHS->getType()), - ConstantInt::getFalse(II->getContext()) - }; - StructType *ST = cast(II->getType()); - Constant *Struct = ConstantStruct::get(ST, V); - return InsertValueInst::Create(Struct, Add, 0); + return CreateOverflowResult(II, Builder->CreateNUWAdd(LHS, RHS), false); } } } @@ -413,13 +398,8 @@ if (ConstantInt *RHS = dyn_cast(II->getArgOperand(1))) { // X + 0 -> {X, false} if (RHS->isZero()) { - Constant *V[] = { - UndefValue::get(II->getArgOperand(0)->getType()), - ConstantInt::getFalse(II->getContext()) - }; - Constant *Struct = - ConstantStruct::get(cast(II->getType()), V); - return InsertValueInst::Create(Struct, II->getArgOperand(0), 0); + return CreateOverflowResult(II, II->getArgOperand(0), false, + /*ReUseName*/false); } } @@ -428,37 +408,36 @@ if (II->getIntrinsicID() == Intrinsic::sadd_with_overflow) { Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1); if (WillNotOverflowSignedAdd(LHS, RHS, II)) { - Value *Add = Builder->CreateNSWAdd(LHS, RHS); - Add->takeName(&CI); - Constant *V[] = {UndefValue::get(Add->getType()), Builder->getFalse()}; - StructType *ST = cast(II->getType()); - Constant *Struct = ConstantStruct::get(ST, V); - return InsertValueInst::Create(Struct, Add, 0); + return CreateOverflowResult(II, Builder->CreateNSWAdd(LHS, RHS), false); } } break; case Intrinsic::usub_with_overflow: - case Intrinsic::ssub_with_overflow: + case Intrinsic::ssub_with_overflow: { + Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1); // undef - X -> undef // X - undef -> undef - if (isa(II->getArgOperand(0)) || - isa(II->getArgOperand(1))) + if (isa(LHS) || isa(RHS)) return ReplaceInstUsesWith(CI, UndefValue::get(II->getType())); - if (ConstantInt *RHS = dyn_cast(II->getArgOperand(1))) { + if (ConstantInt *ConstRHS = dyn_cast(RHS)) { // X - 0 -> {X, false} - if (RHS->isZero()) { - Constant *V[] = { - UndefValue::get(II->getArgOperand(0)->getType()), - ConstantInt::getFalse(II->getContext()) - }; - Constant *Struct = - ConstantStruct::get(cast(II->getType()), V); - return InsertValueInst::Create(Struct, II->getArgOperand(0), 0); + if (ConstRHS->isZero()) { + return CreateOverflowResult(II, LHS, false, /*ReUseName*/false); } } + if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) { + if (WillNotOverflowSignedSub(LHS, RHS, II)) { + return CreateOverflowResult(II, Builder->CreateNSWSub(LHS, RHS), false); + } + } else { + if (WillNotOverflowUnsignedSub(LHS, RHS, II)) { + return CreateOverflowResult(II, Builder->CreateNUWSub(LHS, RHS), false); + } + } break; + } case Intrinsic::umul_with_overflow: { Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1); unsigned BitWidth = cast(LHS->getType())->getBitWidth(); @@ -479,13 +458,7 @@ bool Overflow; LHSMax.umul_ov(RHSMax, Overflow); if (!Overflow) { - Value *Mul = Builder->CreateNUWMul(LHS, RHS, "umul_with_overflow"); - Constant *V[] = { - UndefValue::get(LHS->getType()), - Builder->getFalse() - }; - Constant *Struct = ConstantStruct::get(cast(II->getType()),V); - return InsertValueInst::Create(Struct, Mul, 0); + return CreateOverflowResult(II, Builder->CreateNUWMul(LHS, RHS), false); } } // FALL THROUGH case Intrinsic::smul_with_overflow: @@ -509,15 +482,16 @@ // X * 1 -> {X, false} if (RHSI->equalsInt(1)) { - Constant *V[] = { - UndefValue::get(II->getArgOperand(0)->getType()), - ConstantInt::getFalse(II->getContext()) - }; - Constant *Struct = - ConstantStruct::get(cast(II->getType()), V); - return InsertValueInst::Create(Struct, II->getArgOperand(0), 0); + return CreateOverflowResult(II, II->getArgOperand(0), false, + /*ReUseName*/false); } } + if (II->getIntrinsicID() == Intrinsic::smul_with_overflow) { + Value *LHS = II->getArgOperand(0), *RHS = II->getArgOperand(1); + if (WillNotOverflowSignedMul(LHS, RHS, II)) { + return CreateOverflowResult(II, Builder->CreateNSWMul(LHS, RHS), false); + } + } break; case Intrinsic::minnum: case Intrinsic::maxnum: { Index: test/Transforms/InstCombine/intrinsics.ll =================================================================== --- test/Transforms/InstCombine/intrinsics.ll +++ test/Transforms/InstCombine/intrinsics.ll @@ -1,10 +1,17 @@ ; RUN: opt -instcombine -S < %s | FileCheck %s %overflow.result = type {i8, i1} +%ov.result.32 = type { i32, i1 } -declare %overflow.result @llvm.uadd.with.overflow.i8(i8, i8) -declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32) -declare %overflow.result @llvm.umul.with.overflow.i8(i8, i8) + +declare %overflow.result @llvm.uadd.with.overflow.i8(i8, i8) nounwind readnone +declare %overflow.result @llvm.umul.with.overflow.i8(i8, i8) nounwind readnone +declare %ov.result.32 @llvm.sadd.with.overflow.i32(i32, i32) nounwind readnone +declare %ov.result.32 @llvm.uadd.with.overflow.i32(i32, i32) nounwind readnone +declare %ov.result.32 @llvm.ssub.with.overflow.i32(i32, i32) nounwind readnone +declare %ov.result.32 @llvm.usub.with.overflow.i32(i32, i32) nounwind readnone +declare %ov.result.32 @llvm.smul.with.overflow.i32(i32, i32) nounwind readnone +declare %ov.result.32 @llvm.umul.with.overflow.i32(i32, i32) nounwind readnone declare double @llvm.powi.f64(double, i32) nounwind readonly declare i32 @llvm.cttz.i32(i32, i1) nounwind readnone declare i32 @llvm.ctlz.i32(i32, i1) nounwind readnone @@ -91,18 +98,97 @@ } ; PR20194 -define { i32, i1 } @saddtest1(i8 %a, i8 %b) { +define %ov.result.32 @saddtest_nsw(i8 %a, i8 %b) { %A = sext i8 %a to i32 %B = sext i8 %b to i32 - %x = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %A, i32 %B) - ret { i32, i1 } %x -; CHECK-LABEL: @saddtest1 + %x = call %ov.result.32 @llvm.sadd.with.overflow.i32(i32 %A, i32 %B) + ret %ov.result.32 %x +; CHECK-LABEL: @saddtest_nsw ; CHECK: %x = add nsw i32 %A, %B -; CHECK-NEXT: %1 = insertvalue { i32, i1 } { i32 undef, i1 false }, i32 %x, 0 -; CHECK-NEXT: ret { i32, i1 } %1 +; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0 +; CHECK-NEXT: ret %ov.result.32 %1 } +define %ov.result.32 @uaddtest_nuw(i32 %a, i32 %b) { + %A = and i32 %a, 2147483647 + %B = and i32 %b, 2147483647 + %x = call %ov.result.32 @llvm.uadd.with.overflow.i32(i32 %A, i32 %B) + ret %ov.result.32 %x +; CHECK-LABEL: @uaddtest_nuw +; CHECK: %x = add nuw i32 %A, %B +; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0 +; CHECK-NEXT: ret %ov.result.32 %1 +} +define %ov.result.32 @ssubtest_nsw(i8 %a, i8 %b) { + %A = sext i8 %a to i32 + %B = sext i8 %b to i32 + %x = call %ov.result.32 @llvm.ssub.with.overflow.i32(i32 %A, i32 %B) + ret %ov.result.32 %x +; CHECK-LABEL: @ssubtest_nsw +; CHECK: %x = sub nsw i32 %A, %B +; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0 +; CHECK-NEXT: ret %ov.result.32 %1 +} + +define %ov.result.32 @usubtest_nuw(i32 %a, i32 %b) { + %A = or i32 %a, 2147483648 + %B = and i32 %b, 2147483647 + %x = call %ov.result.32 @llvm.usub.with.overflow.i32(i32 %A, i32 %B) + ret %ov.result.32 %x +; CHECK-LABEL: @usubtest_nuw +; CHECK: %x = sub nuw i32 %A, %B +; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0 +; CHECK-NEXT: ret %ov.result.32 %1 +} + +define %ov.result.32 @smultest1_nsw(i32 %a, i32 %b) { + %A = and i32 %a, 4095 ; 0xfff + %B = and i32 %b, 524287; 0x7ffff + %x = call %ov.result.32 @llvm.smul.with.overflow.i32(i32 %A, i32 %B) + ret %ov.result.32 %x +; CHECK-LABEL: @smultest1_nsw +; CHECK: %x = mul nsw i32 %A, %B +; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0 +; CHECK-NEXT: ret %ov.result.32 %1 +} + +define %ov.result.32 @smultest2_nsw(i32 %a, i32 %b) { + %A = ashr i32 %a, 16 + %B = ashr i32 %b, 16 + %x = call %ov.result.32 @llvm.smul.with.overflow.i32(i32 %A, i32 %B) + ret %ov.result.32 %x +; CHECK-LABEL: @smultest2_nsw +; CHECK: %x = mul nsw i32 %A, %B +; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0 +; CHECK-NEXT: ret %ov.result.32 %1 +} + +define %ov.result.32 @smultest3_sw(i32 %a, i32 %b) { + %A = ashr i32 %a, 16 + %B = ashr i32 %b, 15 + %x = call %ov.result.32 @llvm.smul.with.overflow.i32(i32 %A, i32 %B) + ret %ov.result.32 %x +; CHECK-LABEL: @smultest3_sw +; CHECK: %x = call %ov.result.32 @llvm.smul.with.overflow.i32(i32 %A, i32 %B) +; CHECK-NEXT: ret %ov.result.32 %x +} + +define %ov.result.32 @umultest_nuw(i32 %a, i32 %b) { + %A = and i32 %a, 65535 ; 0xffff + %B = and i32 %b, 65535 ; 0xffff + %x = call %ov.result.32 @llvm.umul.with.overflow.i32(i32 %A, i32 %B) + ret %ov.result.32 %x +; CHECK-LABEL: @umultest_nuw +; CHECK: %x = mul nuw i32 %A, %B +; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0 +; CHECK-NEXT: ret %ov.result.32 %1 +} + + + + + define i8 @umultest1(i8 %A, i1* %overflowPtr) { %x = call %overflow.result @llvm.umul.with.overflow.i8(i8 0, i8 %A) %y = extractvalue %overflow.result %x, 0 @@ -125,9 +211,6 @@ ; CHECK-NEXT: ret i8 %A } -%ov.result.32 = type { i32, i1 } -declare %ov.result.32 @llvm.umul.with.overflow.i32(i32, i32) nounwind readnone - define i32 @umultest3(i32 %n) nounwind { %shr = lshr i32 %n, 2 %mul = call %ov.result.32 @llvm.umul.with.overflow.i32(i32 %shr, i32 3)