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 @@ -4906,6 +4906,19 @@ if (match(Op0, m_Zero()) || match(Op0, m_Undef())) 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, X - undef -> 0, undef - X -> 0 + if (Op0 == Op1 || match(Op0, m_Undef()) || match(Op1, m_Undef())) + 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/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,166 @@ +; 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, max and undef 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 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: call void @dummy(i8 0) +; 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 undef) + call void @dummy(i8 %x4) + %x5 = call i8 @llvm.usub.sat.i8(i8 undef, i8 %a) + call void @dummy(i8 %x5) + %x6 = call i8 @llvm.usub.sat.i8(i8 %a, i8 %a) + call void @dummy(i8 %x6) + + %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 undef) + call void @dummy(i8 %y4) + %y5 = call i8 @llvm.ssub.sat.i8(i8 undef, i8 %a) + call void @dummy(i8 %y5) + %y6 = call i8 @llvm.ssub.sat.i8(i8 %a, i8 %a) + call void @dummy(i8 %y6) + + 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 +}