From e84034484b91c045e1241a01c89b1b274bf2bd7c Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Mon, 17 Dec 2018 17:45:18 +0000 Subject: [PATCH] [InstSimplify] Simplify saturating add/sub + icmp If a saturating add/sub has one constant operand, then we can determine the possible range of outputs it can produce, and simplify an icmp comparison based on that. The implementation is based on a similar existing mechanism for simplifying binary operator + icmps. Differential Revision: https://reviews.llvm.org/D55735 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@349369 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/InstructionSimplify.cpp | 66 +++++++++++++++++++ .../InstSimplify/saturating-add-sub.ll | 56 ++++------------ 2 files changed, 80 insertions(+), 42 deletions(-) diff --git a/lib/Analysis/InstructionSimplify.cpp b/lib/Analysis/InstructionSimplify.cpp index 120a024ed60..ccf907c144f 100644 --- a/lib/Analysis/InstructionSimplify.cpp +++ b/lib/Analysis/InstructionSimplify.cpp @@ -2630,6 +2630,70 @@ static void setLimitsForBinOp(BinaryOperator &BO, APInt &Lower, APInt &Upper, } } +/// Some intrinsics with a constant operand have an easy-to-compute range of +/// outputs. This can be used to fold a comparison to always true or always +/// false. +static void setLimitsForIntrinsic(IntrinsicInst &II, APInt &Lower, + APInt &Upper) { + unsigned Width = Lower.getBitWidth(); + const APInt *C; + switch (II.getIntrinsicID()) { + case Intrinsic::uadd_sat: + // uadd.sat(x, C) produces [C, UINT_MAX]. + if (match(II.getOperand(0), m_APInt(C)) || + match(II.getOperand(1), m_APInt(C))) + Lower = *C; + break; + case Intrinsic::sadd_sat: + if (match(II.getOperand(0), m_APInt(C)) || + match(II.getOperand(1), m_APInt(C))) { + if (C->isNegative()) { + // sadd.sat(x, -C) produces [SINT_MIN, SINT_MAX + (-C)]. + Lower = APInt::getSignedMinValue(Width); + Upper = APInt::getSignedMaxValue(Width) + *C + 1; + } else { + // sadd.sat(x, +C) produces [SINT_MIN + C, SINT_MAX]. + Lower = APInt::getSignedMinValue(Width) + *C; + Upper = APInt::getSignedMaxValue(Width) + 1; + } + } + break; + case Intrinsic::usub_sat: + // usub.sat(C, x) produces [0, C]. + if (match(II.getOperand(0), m_APInt(C))) + Upper = *C + 1; + // usub.sat(x, C) produces [0, UINT_MAX - C]. + else if (match(II.getOperand(1), m_APInt(C))) + Upper = APInt::getMaxValue(Width) - *C + 1; + break; + case Intrinsic::ssub_sat: + if (match(II.getOperand(0), m_APInt(C))) { + if (C->isNegative()) { + // ssub.sat(-C, x) produces [SINT_MIN, -SINT_MIN + (-C)]. + Lower = APInt::getSignedMinValue(Width); + Upper = *C - APInt::getSignedMinValue(Width) + 1; + } else { + // ssub.sat(+C, x) produces [-SINT_MAX + C, SINT_MAX]. + Lower = *C - APInt::getSignedMaxValue(Width); + Upper = APInt::getSignedMaxValue(Width) + 1; + } + } else if (match(II.getOperand(1), m_APInt(C))) { + if (C->isNegative()) { + // ssub.sat(x, -C) produces [SINT_MIN - (-C), SINT_MAX]: + Lower = APInt::getSignedMinValue(Width) - *C; + Upper = APInt::getSignedMaxValue(Width) + 1; + } else { + // ssub.sat(x, +C) produces [SINT_MIN, SINT_MAX - C]. + Lower = APInt::getSignedMinValue(Width); + Upper = APInt::getSignedMaxValue(Width) - *C + 1; + } + } + break; + default: + break; + } +} + static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const InstrInfoQuery &IIQ) { Type *ITy = GetCompareTy(RHS); // The return type. @@ -2663,6 +2727,8 @@ static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS, APInt Upper = APInt(Width, 0); if (auto *BO = dyn_cast(LHS)) setLimitsForBinOp(*BO, Lower, Upper, IIQ); + else if (auto *II = dyn_cast(LHS)) + setLimitsForIntrinsic(*II, Lower, Upper); ConstantRange LHS_CR = Lower != Upper ? ConstantRange(Lower, Upper) : ConstantRange(Width, true); diff --git a/test/Transforms/InstSimplify/saturating-add-sub.ll b/test/Transforms/InstSimplify/saturating-add-sub.ll index 8e733d6d272..a226cc456ac 100644 --- a/test/Transforms/InstSimplify/saturating-add-sub.ll +++ b/test/Transforms/InstSimplify/saturating-add-sub.ll @@ -408,9 +408,7 @@ define <2 x i8> @ssub_vector_same(<2 x i8> %a) { define i1 @uadd_icmp_op0_known(i8 %a) { ; CHECK-LABEL: @uadd_icmp_op0_known( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.uadd.sat.i8(i8 10, i8 [[A:%.*]]) -; CHECK-NEXT: [[C:%.*]] = icmp uge i8 [[B]], 10 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.uadd.sat.i8(i8 10, i8 %a) %c = icmp uge i8 %b, 10 @@ -430,9 +428,7 @@ define i1 @uadd_icmp_op0_unknown(i8 %a) { define i1 @uadd_icmp_op1_known(i8 %a) { ; CHECK-LABEL: @uadd_icmp_op1_known( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.uadd.sat.i8(i8 [[A:%.*]], i8 10) -; CHECK-NEXT: [[C:%.*]] = icmp uge i8 [[B]], 10 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.uadd.sat.i8(i8 %a, i8 10) %c = icmp uge i8 %b, 10 @@ -452,9 +448,7 @@ define i1 @uadd_icmp_op1_unknown(i8 %a) { define i1 @sadd_icmp_op0_pos_known(i8 %a) { ; CHECK-LABEL: @sadd_icmp_op0_pos_known( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.sadd.sat.i8(i8 10, i8 [[A:%.*]]) -; CHECK-NEXT: [[C:%.*]] = icmp sge i8 [[B]], -118 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.sadd.sat.i8(i8 10, i8 %a) %c = icmp sge i8 %b, -118 @@ -474,9 +468,7 @@ define i1 @sadd_icmp_op0_pos_unknown(i8 %a) { define i1 @sadd_icmp_op0_neg_known(i8 %a) { ; CHECK-LABEL: @sadd_icmp_op0_neg_known( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.sadd.sat.i8(i8 -10, i8 [[A:%.*]]) -; CHECK-NEXT: [[C:%.*]] = icmp sle i8 [[B]], 117 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.sadd.sat.i8(i8 -10, i8 %a) %c = icmp sle i8 %b, 117 @@ -496,9 +488,7 @@ define i1 @sadd_icmp_op0_neg_unknown(i8 %a) { define i1 @sadd_icmp_op1_pos_known(i8 %a) { ; CHECK-LABEL: @sadd_icmp_op1_pos_known( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 10) -; CHECK-NEXT: [[C:%.*]] = icmp sge i8 [[B]], -118 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.sadd.sat.i8(i8 %a, i8 10) %c = icmp sge i8 %b, -118 @@ -518,9 +508,7 @@ define i1 @sadd_icmp_op1_pos_unknown(i8 %a) { define i1 @sadd_icmp_op1_neg_known(i8 %a) { ; CHECK-LABEL: @sadd_icmp_op1_neg_known( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.sadd.sat.i8(i8 [[A:%.*]], i8 -10) -; CHECK-NEXT: [[C:%.*]] = icmp sle i8 [[B]], 117 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.sadd.sat.i8(i8 %a, i8 -10) %c = icmp sle i8 %b, 117 @@ -540,9 +528,7 @@ define i1 @sadd_icmp_op1_neg_unknown(i8 %a) { define i1 @usub_icmp_op0_known(i8 %a) { ; CHECK-LABEL: @usub_icmp_op0_known( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.usub.sat.i8(i8 10, i8 [[A:%.*]]) -; CHECK-NEXT: [[C:%.*]] = icmp ule i8 [[B]], 10 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.usub.sat.i8(i8 10, i8 %a) %c = icmp ule i8 %b, 10 @@ -562,9 +548,7 @@ define i1 @usub_icmp_op0_unknown(i8 %a) { define i1 @usub_icmp_op1_known(i8 %a) { ; CHECK-LABEL: @usub_icmp_op1_known( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[A:%.*]], i8 10) -; CHECK-NEXT: [[C:%.*]] = icmp ule i8 [[B]], -11 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.usub.sat.i8(i8 %a, i8 10) %c = icmp ule i8 %b, 245 @@ -584,9 +568,7 @@ define i1 @usub_icmp_op1_unknown(i8 %a) { define i1 @ssub_icmp_op0_pos_known(i8 %a) { ; CHECK-LABEL: @ssub_icmp_op0_pos_known( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.ssub.sat.i8(i8 10, i8 [[A:%.*]]) -; CHECK-NEXT: [[C:%.*]] = icmp sge i8 [[B]], -117 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.ssub.sat.i8(i8 10, i8 %a) %c = icmp sge i8 %b, -117 @@ -606,9 +588,7 @@ define i1 @ssub_icmp_op0_pos_unknown(i8 %a) { define i1 @ssub_icmp_op0_neg_known(i8 %a) { ; CHECK-LABEL: @ssub_icmp_op0_neg_known( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.ssub.sat.i8(i8 -10, i8 [[A:%.*]]) -; CHECK-NEXT: [[C:%.*]] = icmp sle i8 [[B]], 118 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.ssub.sat.i8(i8 -10, i8 %a) %c = icmp sle i8 %b, 118 @@ -629,9 +609,7 @@ define i1 @ssub_icmp_op0_neg_unknown(i8 %a) { ; Peculiar case: ssub.sat(0, x) is never signed min. define i1 @ssub_icmp_op0_zero(i8 %a) { ; CHECK-LABEL: @ssub_icmp_op0_zero( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.ssub.sat.i8(i8 0, i8 [[A:%.*]]) -; CHECK-NEXT: [[C:%.*]] = icmp ne i8 [[B]], -128 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.ssub.sat.i8(i8 0, i8 %a) %c = icmp ne i8 %b, -128 @@ -640,9 +618,7 @@ define i1 @ssub_icmp_op0_zero(i8 %a) { define i1 @ssub_icmp_op1_pos_known(i8 %a) { ; CHECK-LABEL: @ssub_icmp_op1_pos_known( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A:%.*]], i8 10) -; CHECK-NEXT: [[C:%.*]] = icmp sle i8 [[B]], 117 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.ssub.sat.i8(i8 %a, i8 10) %c = icmp sle i8 %b, 117 @@ -662,9 +638,7 @@ define i1 @ssub_icmp_op1_pos_unknown(i8 %a) { define i1 @ssub_icmp_op1_neg_known(i8 %a) { ; CHECK-LABEL: @ssub_icmp_op1_neg_known( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A:%.*]], i8 -10) -; CHECK-NEXT: [[C:%.*]] = icmp sge i8 [[B]], -118 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.ssub.sat.i8(i8 %a, i8 -10) %c = icmp sge i8 %b, -118 @@ -684,9 +658,7 @@ define i1 @ssub_icmp_op1_neg_unknown(i8 %a) { define i1 @ssub_icmp_op1_smin(i8 %a) { ; CHECK-LABEL: @ssub_icmp_op1_smin( -; CHECK-NEXT: [[B:%.*]] = call i8 @llvm.ssub.sat.i8(i8 [[A:%.*]], i8 -128) -; CHECK-NEXT: [[C:%.*]] = icmp sge i8 [[B]], 0 -; CHECK-NEXT: ret i1 [[C]] +; CHECK-NEXT: ret i1 true ; %b = call i8 @llvm.ssub.sat.i8(i8 %a, i8 -128) %c = icmp sge i8 %b, 0 -- 2.50.1