Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -4082,6 +4082,15 @@ Value *CmpLHS, Value *CmpRHS, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS) { + if (ICmpInst::isEquality(Pred)) + return {SPF_UNKNOWN, SPNB_NA, false}; + + // First, check if select has inverse order of what we will check below: + if (CmpRHS == FalseVal) { + std::swap(TrueVal, FalseVal); + Pred = CmpInst::getInversePredicate(Pred); + } + // Assume success. If there's no match, callers should not use these anyway. LHS = TrueVal; RHS = FalseVal; @@ -4094,41 +4103,46 @@ // (X SMAX(SMIN(X, C2), C1) if (match(FalseVal, m_SMin(m_Specific(CmpLHS), m_APInt(C2))) && - C1->slt(*C2) && Pred == CmpInst::ICMP_SLT) + C1->slt(*C2) && + (Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE)) return {SPF_SMAX, SPNB_NA, false}; // (X >s C1) ? C1 : SMAX(X, C2) ==> SMIN(SMAX(X, C2), C1) if (match(FalseVal, m_SMax(m_Specific(CmpLHS), m_APInt(C2))) && - C1->sgt(*C2) && Pred == CmpInst::ICMP_SGT) + C1->sgt(*C2) && + (Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE)) return {SPF_SMIN, SPNB_NA, false}; // (X UMAX(UMIN(X, C2), C1) if (match(FalseVal, m_UMin(m_Specific(CmpLHS), m_APInt(C2))) && - C1->ult(*C2) && Pred == CmpInst::ICMP_ULT) + C1->ult(*C2) && + (Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE)) return {SPF_UMAX, SPNB_NA, false}; // (X >u C1) ? C1 : UMAX(X, C2) ==> UMIN(UMAX(X, C2), C1) if (match(FalseVal, m_UMax(m_Specific(CmpLHS), m_APInt(C2))) && - C1->ugt(*C2) && Pred == CmpInst::ICMP_UGT) + C1->ugt(*C2) && + (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE)) return {SPF_UMIN, SPNB_NA, false}; } - if (Pred != CmpInst::ICMP_SGT && Pred != CmpInst::ICMP_SLT) - return {SPF_UNKNOWN, SPNB_NA, false}; - // Z = X -nsw Y // (X >s Y) ? 0 : Z ==> (Z >s 0) ? 0 : Z ==> SMIN(Z, 0) // (X (Z SMAX(Z, 0) if (match(TrueVal, m_Zero()) && match(FalseVal, m_NSWSub(m_Specific(CmpLHS), m_Specific(CmpRHS)))) - return {Pred == CmpInst::ICMP_SGT ? SPF_SMIN : SPF_SMAX, SPNB_NA, false}; + return {(Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE) ? SPF_SMIN + : SPF_SMAX, + SPNB_NA, false}; // Z = X -nsw Y // (X >s Y) ? Z : 0 ==> (Z >s 0) ? Z : 0 ==> SMAX(Z, 0) // (X (Z SMIN(Z, 0) if (match(FalseVal, m_Zero()) && match(TrueVal, m_NSWSub(m_Specific(CmpLHS), m_Specific(CmpRHS)))) - return {Pred == CmpInst::ICMP_SGT ? SPF_SMAX : SPF_SMIN, SPNB_NA, false}; + return {(Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE) ? SPF_SMAX + : SPF_SMIN, + SPNB_NA, false}; if (!match(CmpRHS, m_APInt(C1))) return {SPF_UNKNOWN, SPNB_NA, false}; @@ -4140,14 +4154,15 @@ // Is the sign bit set? // (X (X >u MAXVAL) ? X : MAXVAL ==> UMAX // (X (X >u MAXVAL) ? MAXVAL : X ==> UMIN - if (Pred == CmpInst::ICMP_SLT && *C1 == 0 && C2->isMaxSignedValue()) + if ((Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE) && *C1 == 0 && + C2->isMaxSignedValue()) return {CmpLHS == TrueVal ? SPF_UMAX : SPF_UMIN, SPNB_NA, false}; // Is the sign bit clear? // (X >s -1) ? MINVAL : X ==> (X UMAX // (X >s -1) ? X : MINVAL ==> (X UMIN - if (Pred == CmpInst::ICMP_SGT && C1->isAllOnesValue() && - C2->isMinSignedValue()) + if ((Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE) && + C1->isAllOnesValue() && C2->isMinSignedValue()) return {CmpLHS == FalseVal ? SPF_UMAX : SPF_UMIN, SPNB_NA, false}; } @@ -4156,13 +4171,17 @@ // (X (~X >s ~C) ? ~X : ~C ==> SMAX(~X, ~C) if (match(TrueVal, m_Not(m_Specific(CmpLHS))) && match(FalseVal, m_APInt(C2)) && ~(*C1) == *C2) - return {Pred == CmpInst::ICMP_SGT ? SPF_SMIN : SPF_SMAX, SPNB_NA, false}; + return {(Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE) ? SPF_SMIN + : SPF_SMAX, + SPNB_NA, false}; // (X >s C) ? ~C : ~X ==> (~X SMAX(~C, ~X) // (X (~X >s ~C) ? ~C : ~X ==> SMIN(~C, ~X) if (match(FalseVal, m_Not(m_Specific(CmpLHS))) && match(TrueVal, m_APInt(C2)) && ~(*C1) == *C2) - return {Pred == CmpInst::ICMP_SGT ? SPF_SMAX : SPF_SMIN, SPNB_NA, false}; + return {(Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE) ? SPF_SMAX + : SPF_SMIN, + SPNB_NA, false}; return {SPF_UNKNOWN, SPNB_NA, false}; } Index: lib/Transforms/InstCombine/InstCombineCompares.cpp =================================================================== --- lib/Transforms/InstCombine/InstCombineCompares.cpp +++ lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -1318,6 +1318,28 @@ return ExtractValueInst::Create(Call, 1, "sadd.overflow"); } +// Handle (icmp sgt smin(PosA, B) 0) -> (icmp sgt B 0) +Instruction *InstCombiner::foldICmpMinConstant(ICmpInst &Cmp) { + CmpInst::Predicate Pred = Cmp.getPredicate(); + Value *X = Cmp.getOperand(0); + + const APInt *C; + if (!match(Cmp.getOperand(1), m_APInt(C))) + return nullptr; + + Value *A = nullptr, *B = nullptr; + if (C->isNullValue() && Pred == ICmpInst::ICMP_SGT) { + SelectPatternResult SPR = matchSelectPattern(X, A, B); + if (SPR.Flavor == SPF_SMIN) { + if (isKnownPositive(A, DL, 0, &AC, &Cmp, &DT)) + return new ICmpInst(Pred, B, Cmp.getOperand(1)); + if (isKnownPositive(B, DL, 0, &AC, &Cmp, &DT)) + return new ICmpInst(Pred, A, Cmp.getOperand(1)); + } + } + return nullptr; +} + // Fold icmp Pred X, C. Instruction *InstCombiner::foldICmpWithConstant(ICmpInst &Cmp) { CmpInst::Predicate Pred = Cmp.getPredicate(); @@ -1349,17 +1371,6 @@ return Res; } - // (icmp sgt smin(PosA, B) 0) -> (icmp sgt B 0) - if (C->isNullValue() && Pred == ICmpInst::ICMP_SGT) { - SelectPatternResult SPR = matchSelectPattern(X, A, B); - if (SPR.Flavor == SPF_SMIN) { - if (isKnownPositive(A, DL, 0, &AC, &Cmp, &DT)) - return new ICmpInst(Pred, B, Cmp.getOperand(1)); - if (isKnownPositive(B, DL, 0, &AC, &Cmp, &DT)) - return new ICmpInst(Pred, A, Cmp.getOperand(1)); - } - } - // FIXME: Use m_APInt to allow folds for splat constants. ConstantInt *CI = dyn_cast(Cmp.getOperand(1)); if (!CI) @@ -4456,6 +4467,10 @@ (SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1)) return nullptr; + // Do this after after checking for min/max to prevent infinite looping. + if (Instruction *Res = foldICmpMinConstant(I)) + return Res; + // FIXME: We only do this after checking for min/max to prevent infinite // looping caused by a reverse canonicalization of these patterns for min/max. // FIXME: The organization of folds is a mess. These would naturally go into Index: lib/Transforms/InstCombine/InstCombineInternal.h =================================================================== --- lib/Transforms/InstCombine/InstCombineInternal.h +++ lib/Transforms/InstCombine/InstCombineInternal.h @@ -694,6 +694,7 @@ Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp); Instruction *foldICmpBinOp(ICmpInst &Cmp); Instruction *foldICmpEquality(ICmpInst &Cmp); + Instruction *foldICmpMinConstant(ICmpInst &Cmp); Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select, ConstantInt *C); Index: test/Transforms/InstCombine/minmax-fold.ll =================================================================== --- test/Transforms/InstCombine/minmax-fold.ll +++ test/Transforms/InstCombine/minmax-fold.ll @@ -361,7 +361,7 @@ ret i32 %retval } -; The next 4 tests are value clamping with constants: +; The next 10 tests are value clamping with constants: ; https://llvm.org/bugs/show_bug.cgi?id=31693 ; (X SMAX(SMIN(X, C2), C1) @@ -398,6 +398,40 @@ ret i32 %r } +; (X >s C1) ? SMIN(X, C2) : C1 ==> SMAX(SMIN(X, C2), C1) + +define i32 @clamp_signed3(i32 %x) { +; CHECK-LABEL: @clamp_signed3( +; CHECK-NEXT: [[CMP2:%.*]] = icmp slt i32 [[X:%.*]], 255 +; CHECK-NEXT: [[MIN:%.*]] = select i1 [[CMP2]], i32 [[X]], i32 255 +; CHECK-NEXT: [[TMP1:%.*]] = icmp sgt i32 [[MIN]], 15 +; CHECK-NEXT: [[R:%.*]] = select i1 [[TMP1]], i32 [[MIN]], i32 15 +; CHECK-NEXT: ret i32 [[R]] +; + %cmp2 = icmp slt i32 %x, 255 + %min = select i1 %cmp2, i32 %x, i32 255 + %cmp1 = icmp sgt i32 %x, 15 + %r = select i1 %cmp1, i32 %min, i32 15 + ret i32 %r +} + +; (X SMIN(SMAX(X, C1), C2) + +define i32 @clamp_signed4(i32 %x) { +; CHECK-LABEL: @clamp_signed4( +; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i32 [[X:%.*]], 15 +; CHECK-NEXT: [[MAX:%.*]] = select i1 [[CMP2]], i32 [[X]], i32 15 +; CHECK-NEXT: [[TMP1:%.*]] = icmp slt i32 [[MAX]], 255 +; CHECK-NEXT: [[R:%.*]] = select i1 [[TMP1]], i32 [[MAX]], i32 255 +; CHECK-NEXT: ret i32 [[R]] +; + %cmp2 = icmp sgt i32 %x, 15 + %max = select i1 %cmp2, i32 %x, i32 15 + %cmp1 = icmp slt i32 %x, 255 + %r = select i1 %cmp1, i32 %max, i32 255 + ret i32 %r +} + ; (X UMAX(UMIN(X, C2), C1) define i32 @clamp_unsigned1(i32 %x) { @@ -432,6 +466,74 @@ ret i32 %r } +; (X >u C1) ? UMIN(X, C2) : C1 ==> UMAX(UMIN(X, C2), C1) + +define i32 @clamp_unsigned3(i32 %x) { +; CHECK-LABEL: @clamp_unsigned3( +; CHECK-NEXT: [[CMP2:%.*]] = icmp ult i32 [[X:%.*]], 255 +; CHECK-NEXT: [[MIN:%.*]] = select i1 [[CMP2]], i32 [[X]], i32 255 +; CHECK-NEXT: [[TMP1:%.*]] = icmp ugt i32 [[MIN]], 15 +; CHECK-NEXT: [[R:%.*]] = select i1 [[TMP1]], i32 [[MIN]], i32 15 +; CHECK-NEXT: ret i32 [[R]] +; + %cmp2 = icmp ult i32 %x, 255 + %min = select i1 %cmp2, i32 %x, i32 255 + %cmp1 = icmp ugt i32 %x, 15 + %r = select i1 %cmp1, i32 %min, i32 15 + ret i32 %r +} + +; (X UMIN(UMAX(X, C2), C1) + +define i32 @clamp_unsigned4(i32 %x) { +; CHECK-LABEL: @clamp_unsigned4( +; CHECK-NEXT: [[CMP2:%.*]] = icmp ugt i32 [[X:%.*]], 15 +; CHECK-NEXT: [[MAX:%.*]] = select i1 [[CMP2]], i32 [[X]], i32 15 +; CHECK-NEXT: [[TMP1:%.*]] = icmp ult i32 [[MAX]], 255 +; CHECK-NEXT: [[R:%.*]] = select i1 [[TMP1]], i32 [[MAX]], i32 255 +; CHECK-NEXT: ret i32 [[R]] +; + %cmp2 = icmp ugt i32 %x, 15 + %max = select i1 %cmp2, i32 %x, i32 15 + %cmp1 = icmp ult i32 %x, 255 + %r = select i1 %cmp1, i32 %max, i32 255 + ret i32 %r +} + +; Check that clamp is recognized and there is no infinite +; loop because of reverse cmp transformation: +; (icmp sgt smin(PositiveA, B) 0) -> (icmp sgt B 0) +define i32 @clamp_check_for_no_infinite_loop1(i32 %i) { +; CHECK-LABEL: @clamp_check_for_no_infinite_loop1( +; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 [[I:%.*]], 255 +; CHECK-NEXT: [[SEL1:%.*]] = select i1 [[CMP1]], i32 [[I]], i32 255 +; CHECK-NEXT: [[TMP1:%.*]] = icmp sgt i32 [[SEL1]], 0 +; CHECK-NEXT: [[RES:%.*]] = select i1 [[TMP1]], i32 [[SEL1]], i32 0 +; CHECK-NEXT: ret i32 [[RES]] +; + %cmp1 = icmp slt i32 %i, 255 + %sel1 = select i1 %cmp1, i32 %i, i32 255 + %cmp2 = icmp slt i32 %i, 0 + %res = select i1 %cmp2, i32 0, i32 %sel1 + ret i32 %res +} +; Check that there is no infinite loop in case of: +; (icmp slt smax(NegativeA, B) 0) -> (icmp slt B 0) +define i32 @clamp_check_for_no_infinite_loop2(i32 %i) { +; CHECK-LABEL: @clamp_check_for_no_infinite_loop2( +; CHECK-NEXT: [[CMP1:%.*]] = icmp sgt i32 [[I:%.*]], -255 +; CHECK-NEXT: [[SEL1:%.*]] = select i1 [[CMP1]], i32 [[I]], i32 -255 +; CHECK-NEXT: [[TMP1:%.*]] = icmp slt i32 [[SEL1]], 0 +; CHECK-NEXT: [[RES:%.*]] = select i1 [[TMP1]], i32 [[SEL1]], i32 0 +; CHECK-NEXT: ret i32 [[RES]] +; + %cmp1 = icmp sgt i32 %i, -255 + %sel1 = select i1 %cmp1, i32 %i, i32 -255 + %cmp2 = icmp slt i32 %i, 0 + %res = select i1 %cmp2, i32 %sel1, i32 0 + ret i32 %res +} + ; The next 3 min tests should canonicalize to the same form...and not infinite loop. define double @PR31751_umin1(i32 %x) {