Index: include/llvm/ADT/APInt.h =================================================================== --- include/llvm/ADT/APInt.h +++ include/llvm/ADT/APInt.h @@ -1108,6 +1108,8 @@ // Operations that saturate APInt sadd_sat(const APInt &RHS) const; APInt uadd_sat(const APInt &RHS) const; + APInt ssub_sat(const APInt &RHS) const; + APInt usub_sat(const APInt &RHS) const; /// Array-indexing support. /// Index: lib/Analysis/ConstantFolding.cpp =================================================================== --- lib/Analysis/ConstantFolding.cpp +++ lib/Analysis/ConstantFolding.cpp @@ -1401,6 +1401,8 @@ case Intrinsic::umul_with_overflow: case Intrinsic::sadd_sat: case Intrinsic::uadd_sat: + case Intrinsic::ssub_sat: + case Intrinsic::usub_sat: case Intrinsic::convert_from_fp16: case Intrinsic::convert_to_fp16: case Intrinsic::bitreverse: @@ -2025,6 +2027,10 @@ return ConstantInt::get(Ty, Op1->getValue().uadd_sat(Op2->getValue())); case Intrinsic::sadd_sat: return ConstantInt::get(Ty, Op1->getValue().sadd_sat(Op2->getValue())); + case Intrinsic::usub_sat: + return ConstantInt::get(Ty, Op1->getValue().usub_sat(Op2->getValue())); + case Intrinsic::ssub_sat: + return ConstantInt::get(Ty, Op1->getValue().ssub_sat(Op2->getValue())); case Intrinsic::cttz: if (Op2->isOne() && Op1->isZero()) // cttz(0, 1) is undef. return UndefValue::get(Ty); Index: lib/Analysis/InstructionSimplify.cpp =================================================================== --- lib/Analysis/InstructionSimplify.cpp +++ lib/Analysis/InstructionSimplify.cpp @@ -4904,6 +4904,20 @@ if (match(Op0, m_Zero())) return Op1; break; + case Intrinsic::usub_sat: + // sat(0 - X) -> 0 + // sat(X - MAX) -> 0 + if (match(Op0, m_Zero()) || match(Op1, m_AllOnes())) + return Constant::getNullValue(ReturnType); + LLVM_FALLTHROUGH; + case Intrinsic::ssub_sat: + // X - X -> 0 + if (Op0 == Op1) + return Constant::getNullValue(ReturnType); + // X - 0 -> X + if (match(Op1, m_Zero())) + return Op0; + break; case Intrinsic::load_relative: if (auto *C0 = dyn_cast(Op0)) if (auto *C1 = dyn_cast(Op1)) Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -4001,13 +4001,11 @@ if (LHSKnown.isNegative() && RHSKnown.isNegative()) { // The sign bit is set in both cases: this MUST overflow. - // Create a simple add instruction, and insert it into the struct. return OverflowResult::AlwaysOverflows; } if (LHSKnown.isNonNegative() && RHSKnown.isNonNegative()) { // The sign bit is clear in both cases: this CANNOT overflow. - // Create a simple add instruction, and insert it into the struct. return OverflowResult::NeverOverflows; } } @@ -4124,11 +4122,18 @@ AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) { - // If the LHS is negative and the RHS is non-negative, no unsigned wrap. KnownBits LHSKnown = computeKnownBits(LHS, DL, /*Depth=*/0, AC, CxtI, DT); - KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT); - if (LHSKnown.isNegative() && RHSKnown.isNonNegative()) - return OverflowResult::NeverOverflows; + if (LHSKnown.isNonNegative() || LHSKnown.isNegative()) { + KnownBits RHSKnown = computeKnownBits(RHS, DL, /*Depth=*/0, AC, CxtI, DT); + + // If the LHS is negative and the RHS is non-negative, no unsigned wrap. + if (LHSKnown.isNegative() && RHSKnown.isNonNegative()) + return OverflowResult::NeverOverflows; + + // If the LHS is non-negative and the RHS negative, we always wrap. + if (LHSKnown.isNonNegative() && RHSKnown.isNegative()) + return OverflowResult::AlwaysOverflows; + } return OverflowResult::MayOverflow; } Index: lib/Support/APInt.cpp =================================================================== --- lib/Support/APInt.cpp +++ lib/Support/APInt.cpp @@ -1966,6 +1966,25 @@ return APInt::getMaxValue(BitWidth); } +APInt APInt::ssub_sat(const APInt &RHS) const { + bool Overflow; + APInt Res = ssub_ov(RHS, Overflow); + if (!Overflow) + return Res; + + return isNegative() ? APInt::getSignedMinValue(BitWidth) + : APInt::getSignedMaxValue(BitWidth); +} + +APInt APInt::usub_sat(const APInt &RHS) const { + bool Overflow; + APInt Res = usub_ov(RHS, Overflow); + if (!Overflow) + return Res; + + return APInt(BitWidth, 0); +} + void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) { // Check our assumptions here Index: lib/Transforms/InstCombine/InstCombineCalls.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineCalls.cpp +++ lib/Transforms/InstCombine/InstCombineCalls.cpp @@ -2020,37 +2020,61 @@ } case Intrinsic::uadd_sat: - case Intrinsic::sadd_sat: { - Value *Arg0 = II->getArgOperand(0); - Value *Arg1 = II->getArgOperand(1); - if (isa(Arg0) && !isa(Arg1)) { + case Intrinsic::sadd_sat: + if (isa(II->getArgOperand(0)) && + !isa(II->getArgOperand(1))) { // Canonicalize constants into the RHS. - II->setArgOperand(0, Arg1); - II->setArgOperand(1, Arg0); + Value *LHS = II->getArgOperand(0); + II->setArgOperand(0, II->getArgOperand(1)); + II->setArgOperand(1, LHS); return II; } + LLVM_FALLTHROUGH; + case Intrinsic::usub_sat: + case Intrinsic::ssub_sat: { + Value *Arg0 = II->getArgOperand(0); + Value *Arg1 = II->getArgOperand(1); + Intrinsic::ID IID = II->getIntrinsicID(); // Make use of known overflow information. - bool IsUnsigned = II->getIntrinsicID() == Intrinsic::uadd_sat; - if (IsUnsigned) { - OverflowResult OR = computeOverflowForUnsignedAdd(Arg0, Arg1, II); - if (OR == OverflowResult::NeverOverflows) - return replaceInstUsesWith(*II, Builder.CreateNUWAdd(Arg0, Arg1)); - - if (OR == OverflowResult::AlwaysOverflows) - return replaceInstUsesWith(*II, - ConstantInt::getAllOnesValue(II->getType())); - } else { - if (willNotOverflowSignedAdd(Arg0, Arg1, *II)) - return replaceInstUsesWith(*II, Builder.CreateNSWAdd(Arg0, Arg1)); + OverflowResult OR; + switch (IID) { + default: llvm_unreachable("Unexpected intrinsic!"); + case Intrinsic::uadd_sat: + OR = computeOverflowForUnsignedAdd(Arg0, Arg1, II); + if (OR == OverflowResult::NeverOverflows) + return replaceInstUsesWith(*II, Builder.CreateNUWAdd(Arg0, Arg1)); + if (OR == OverflowResult::AlwaysOverflows) + return replaceInstUsesWith(*II, + ConstantInt::getAllOnesValue(II->getType())); + break; + case Intrinsic::usub_sat: + OR = computeOverflowForUnsignedSub(Arg0, Arg1, II); + if (OR == OverflowResult::NeverOverflows) + return replaceInstUsesWith(*II, Builder.CreateNUWSub(Arg0, Arg1)); + if (OR == OverflowResult::AlwaysOverflows) + return replaceInstUsesWith(*II, + ConstantInt::getNullValue(II->getType())); + break; + case Intrinsic::sadd_sat: + if (willNotOverflowSignedAdd(Arg0, Arg1, *II)) + return replaceInstUsesWith(*II, Builder.CreateNSWAdd(Arg0, Arg1)); + break; + case Intrinsic::ssub_sat: + if (willNotOverflowSignedSub(Arg0, Arg1, *II)) + return replaceInstUsesWith(*II, Builder.CreateNSWSub(Arg0, Arg1)); + break; } // sat(sat(X + Val2) + Val) -> sat(X + (Val+Val2)) + // sat(sat(X - Val2) - Val) -> sat(X - (Val+Val2)) // if Val and Val2 have the same sign if (auto *Other = dyn_cast(Arg0)) { Value *X; const APInt *Val, *Val2; APInt NewVal; + bool IsUnsigned = IID == Intrinsic::uadd_sat + || IID == Intrinsic::usub_sat; if (Other->getIntrinsicID() == II->getIntrinsicID() && match(Arg1, m_APInt(Val)) && match(Other->getArgOperand(0), m_Value(X)) && Index: test/Transforms/InstCombine/saturating-sub.ll =================================================================== --- /dev/null +++ test/Transforms/InstCombine/saturating-sub.ll @@ -0,0 +1,154 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -instcombine -S | FileCheck %s + +declare void @dummy(i8) +declare i8 @llvm.usub.sat.i8(i8, i8) +declare i8 @llvm.ssub.sat.i8(i8, i8) + +; Simple constant folding +define void @test1() { +; CHECK-LABEL: @test1( +; CHECK-NEXT: call void @dummy(i8 10) +; CHECK-NEXT: call void @dummy(i8 0) +; CHECK-NEXT: call void @dummy(i8 -30) +; CHECK-NEXT: call void @dummy(i8 127) +; CHECK-NEXT: call void @dummy(i8 -128) +; CHECK-NEXT: ret void +; + %x1 = call i8 @llvm.usub.sat.i8(i8 20, i8 10) + call void @dummy(i8 %x1) + %x2 = call i8 @llvm.usub.sat.i8(i8 200, i8 250) + call void @dummy(i8 %x2) + + %y1 = call i8 @llvm.ssub.sat.i8(i8 -10, i8 20) + call void @dummy(i8 %y1) + %y2 = call i8 @llvm.ssub.sat.i8(i8 120, i8 -10) + call void @dummy(i8 %y2) + %y3 = call i8 @llvm.ssub.sat.i8(i8 -120, i8 10) + call void @dummy(i8 %y3) + + ret void +} + +; Zero and max folding +define void @test2(i8 %a) { +; CHECK-LABEL: @test2( +; CHECK-NEXT: call void @dummy(i8 [[A:%.*]]) +; CHECK-NEXT: call void @dummy(i8 0) +; CHECK-NEXT: call void @dummy(i8 0) +; CHECK-NEXT: call void @dummy(i8 0) +; CHECK-NEXT: call void @dummy(i8 [[A]]) +; CHECK-NEXT: [[Y2:%.*]] = call i8 @llvm.ssub.sat.i8(i8 0, i8 [[A]]) +; CHECK-NEXT: call void @dummy(i8 [[Y2]]) +; CHECK-NEXT: [[Y3:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A]], i8 -1) +; CHECK-NEXT: call void @dummy(i8 [[Y3]]) +; CHECK-NEXT: call void @dummy(i8 0) +; CHECK-NEXT: ret void +; + %x1 = call i8 @llvm.usub.sat.i8(i8 %a, i8 0) + call void @dummy(i8 %x1) + %x2 = call i8 @llvm.usub.sat.i8(i8 0, i8 %a) + call void @dummy(i8 %x2) + %x3 = call i8 @llvm.usub.sat.i8(i8 %a, i8 255) + call void @dummy(i8 %x3) + %x4 = call i8 @llvm.usub.sat.i8(i8 %a, i8 %a) + call void @dummy(i8 %x4) + + %y1 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 0) + call void @dummy(i8 %y1) + %y2 = call i8 @llvm.ssub.sat.i8(i8 0, i8 %a) + call void @dummy(i8 %y2) + %y3 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 255) + call void @dummy(i8 %y3) + %y4 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 %a) + call void @dummy(i8 %y4) + + ret void +} + +; Folding of two saturating subs +define void @test3(i8 %a) { +; CHECK-LABEL: @test3( +; CHECK-NEXT: [[TMP1:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[A:%.*]], i8 30) +; CHECK-NEXT: call void @dummy(i8 [[TMP1]]) +; CHECK-NEXT: call void @dummy(i8 0) +; CHECK-NEXT: [[TMP2:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A]], i8 30) +; CHECK-NEXT: call void @dummy(i8 [[TMP2]]) +; CHECK-NEXT: [[TMP3:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A]], i8 -30) +; CHECK-NEXT: call void @dummy(i8 [[TMP3]]) +; CHECK-NEXT: [[V1:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A]], i8 10) +; CHECK-NEXT: [[V2:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[V1]], i8 -20) +; CHECK-NEXT: call void @dummy(i8 [[V2]]) +; CHECK-NEXT: [[W1:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A]], i8 100) +; CHECK-NEXT: [[W2:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[W1]], i8 100) +; CHECK-NEXT: call void @dummy(i8 [[W2]]) +; CHECK-NEXT: ret void +; + %x1 = call i8 @llvm.usub.sat.i8(i8 %a, i8 10) + %x2 = call i8 @llvm.usub.sat.i8(i8 %x1, i8 20) + call void @dummy(i8 %x2) + + %y1 = call i8 @llvm.usub.sat.i8(i8 %a, i8 100) + %y2 = call i8 @llvm.usub.sat.i8(i8 %y1, i8 200) + call void @dummy(i8 %y2) + + %z1 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 10) + %z2 = call i8 @llvm.ssub.sat.i8(i8 %z1, i8 20) + call void @dummy(i8 %z2) + + %u1 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 -10) + %u2 = call i8 @llvm.ssub.sat.i8(i8 %u1, i8 -20) + call void @dummy(i8 %u2) + + %v1 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 10) + %v2 = call i8 @llvm.ssub.sat.i8(i8 %v1, i8 -20) + call void @dummy(i8 %v2) + + %w1 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 100) + %w2 = call i8 @llvm.ssub.sat.i8(i8 %w1, i8 100) + call void @dummy(i8 %w2) + + ret void +} + +; Use of known overflow/no-overflow information +define void @test4(i8 %a) { +; CHECK-LABEL: @test4( +; CHECK-NEXT: [[A_NEG:%.*]] = or i8 [[A:%.*]], -128 +; CHECK-NEXT: [[A_NNEG:%.*]] = and i8 [[A]], 127 +; CHECK-NEXT: [[TMP1:%.*]] = add i8 [[A_NEG]], -10 +; CHECK-NEXT: call void @dummy(i8 [[TMP1]]) +; CHECK-NEXT: call void @dummy(i8 0) +; CHECK-NEXT: [[TMP2:%.*]] = add nsw i8 [[A_NEG]], 10 +; CHECK-NEXT: call void @dummy(i8 [[TMP2]]) +; CHECK-NEXT: [[TMP3:%.*]] = add nsw i8 [[A_NNEG]], -10 +; CHECK-NEXT: call void @dummy(i8 [[TMP3]]) +; CHECK-NEXT: [[Y3:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A_NEG]], i8 10) +; CHECK-NEXT: call void @dummy(i8 [[Y3]]) +; CHECK-NEXT: [[Y4:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A_NNEG]], i8 -10) +; CHECK-NEXT: call void @dummy(i8 [[Y4]]) +; CHECK-NEXT: ret void +; + %a_neg = or i8 %a, -128 + %a_nneg = and i8 %a, 127 + + %x1 = call i8 @llvm.usub.sat.i8(i8 %a_neg, i8 10) + call void @dummy(i8 %x1) + + %x2 = call i8 @llvm.usub.sat.i8(i8 %a_nneg, i8 -10) + call void @dummy(i8 %x2) + + %y1 = call i8 @llvm.ssub.sat.i8(i8 %a_neg, i8 -10) + call void @dummy(i8 %y1) + + %y2 = call i8 @llvm.ssub.sat.i8(i8 %a_nneg, i8 10) + call void @dummy(i8 %y2) + + %y3 = call i8 @llvm.ssub.sat.i8(i8 %a_neg, i8 10) + call void @dummy(i8 %y3) + + %y4 = call i8 @llvm.ssub.sat.i8(i8 %a_nneg, i8 -10) + call void @dummy(i8 %y4) + + ret void +} Index: unittests/ADT/APIntTest.cpp =================================================================== --- unittests/ADT/APIntTest.cpp +++ unittests/ADT/APIntTest.cpp @@ -1176,7 +1176,7 @@ EXPECT_EQ(APInt(32, uint64_t(-72LL)), APInt(32, "-20", 36)); } -TEST(APIntTest, SaturatingAdd) { +TEST(APIntTest, SaturatingMath) { APInt AP_10 = APInt(8, 10); APInt AP_100 = APInt(8, 100); APInt AP_200 = APInt(8, 200); @@ -1189,6 +1189,15 @@ EXPECT_EQ(APInt(8, 127), AP_100.sadd_sat(AP_100)); EXPECT_EQ(APInt(8, -128), (-AP_100).sadd_sat(-AP_100)); EXPECT_EQ(APInt(8, -128), APInt(8, -128).sadd_sat(APInt(8, -128))); + + EXPECT_EQ(APInt(8, 90), AP_100.usub_sat(AP_10)); + EXPECT_EQ(APInt(8, 0), AP_100.usub_sat(AP_200)); + EXPECT_EQ(APInt(8, 0), APInt(8, 0).usub_sat(APInt(8, 255))); + + EXPECT_EQ(APInt(8, -90), AP_10.ssub_sat(AP_100)); + EXPECT_EQ(APInt(8, 127), AP_100.ssub_sat(-AP_100)); + EXPECT_EQ(APInt(8, -128), (-AP_100).ssub_sat(AP_100)); + EXPECT_EQ(APInt(8, -128), APInt(8, -128).ssub_sat(APInt(8, 127))); } TEST(APIntTest, FromArray) {