Improve clamp recognition in ValueTracking.

[ArturGainullin]

Summary

ValueTracking was recognizing not all variations of clamp. Swapping of
true value and false value of select was added to fix this problem. This
change breaks the canonical form of cmp inside the matchMinMax function,
that is why additional checks for compare predicates is needed. Added
corresponding test cases.

Also there is a reverse transformation for cmp instruction:

icmp smin(x, PositiveValue), 0 -> icmp x, 0

We should only do this after checking for min/max to prevent infinite
looping caused by a reverse canonicalization of these patterns. That is
why this transformation was moved to place after the mentioned check.
Test case was also added to check that we don't go to infinite loop.

[ArturGainullin]

Ping.

[spatel]

I think this makes sense, but adding reviewers for more potential opinions.

But I suggest that we split the "foldICmpMinConstant" part into its own patch as a preliminary step. I went ahead and checked in the tests at rL315461, so I could understand how these things interact.

If I'm seeing it correctly, we'll get one test case (clamp_check_for_no_infinite_loop1) that will become a canonical clamp pattern with the code movement in InstCombineCompares, so we can do that before the value tracking change.

lib/Analysis/ValueTracking.cpp

4085–4086 ↗

(On Diff #117633)

Didn't the caller (llvm::matchSelectPattern()) already check for this?

lib/Transforms/InstCombine/InstCombineCompares.cpp

1322 ↗

(On Diff #117633)

This name confused me because when I see "min constant", I think of 0x8000...
How about "foldICmpSgtZeroMinPos" ?

But shouldn't there be an smax sibling for this fold?
For reference, the fold was added with D17873.

1327 ↗

(On Diff #117633)

Use m_Zero() to simplify this.

1330 ↗

(On Diff #117633)

Don't need to explicitly set to nullptr here?

4470 ↗

(On Diff #117633)

typo: after after

[efriedma]

lib/Transforms/InstCombine/InstCombineCompares.cpp

1331 ↗

(On Diff #117633)

Slightly more general transform:

https://rise4fun.com/Alive/AKv

In any case, this should probably be a separate patch.

[ArturGainullin]

Created separate patch to move folding of cmp instruction: D38934. I will be able to update this differential revision when it will be committed.
I have renamed function so that we will be able to add an smax sibling for this fold with separate commit.

As far as I understood efriedma proposes to implement more general transformation (changed it a little bit so that it is more evident that it is related to current transformation):

Precondition: C2 s> C1

icmp sgt smin(a, C2), C1 -> icmp sgt a, C1

https://rise4fun.com/Alive/oFF
I agree that this should be done as a separate commit.

[ArturGainullin]

Rebase after committing foldICmpWithZero as a separate change.
Also made changes according to comments.

[spatel]

This patch can miscompile because it's not checking predicates correctly. I'm not sure how to expose this in an IR test because we don't canonicalize enough yet, so I added x86 tests at rL315913.

[ArturGainullin]

We need to check that predicate is signed before matching patterns after clamp.
This condition was removed by mistake. Fixed.

[spatel]

LGTM.

If you want to change that first equality predicate check (the one that was removed from the top of the function) into an assert, I think that would be good since it's not obvious that we've filtered those cases out before we call this function.

llvm/trunk/lib/Analysis/ValueTracking.cpp

static SelectPatternResult matchFastFloatClamp(CmpInst::Predicate Pred,
   return {SPF_UNKNOWN, SPNB_NA, false};
 }
 
 /// Match non-obvious integer minimum and maximum sequences.
 static SelectPatternResult matchMinMax(CmpInst::Predicate Pred,
                                        Value *CmpLHS, Value *CmpRHS,
                                        Value *TrueVal, Value *FalseVal,
                                        Value *&LHS, Value *&RHS) {
+  assert(!ICmpInst::isEquality(Pred) && "Expected not equality predicate only!");
+
+  // 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;
 
   // Recognize variations of:
   // CLAMP(v,l,h) ==> ((v) < (l) ? (l) : ((v) > (h) ? (h) : (v)))
   const APInt *C1;
   if (CmpRHS == TrueVal && match(CmpRHS, m_APInt(C1))) {
     const APInt *C2;
 
     // (X <s C1) ? C1 : SMIN(X, C2) ==> 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 <u C1) ? C1 : UMIN(X, C2) ==> 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)
+  if (!CmpInst::isSigned(Pred))
     return {SPF_UNKNOWN, SPNB_NA, false};
 
   // Z = X -nsw Y
   // (X >s Y) ? 0 : Z ==> (Z >s 0) ? 0 : Z ==> SMIN(Z, 0)
   // (X <s Y) ? 0 : Z ==> (Z <s 0) ? 0 : 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 <s Y) ? Z : 0 ==> (Z <s 0) ? Z : 0 ==> 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};
 
   // An unsigned min/max can be written with a signed compare.
   const APInt *C2;
   if ((CmpLHS == TrueVal && match(FalseVal, m_APInt(C2))) ||
       (CmpLHS == FalseVal && match(TrueVal, m_APInt(C2)))) {
     // Is the sign bit set?
     // (X <s 0) ? X : MAXVAL ==> (X >u MAXVAL) ? X : MAXVAL ==> UMAX
     // (X <s 0) ? MAXVAL : 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 <u MINVAL) ? MINVAL : X ==> UMAX
     // (X >s -1) ? X : MINVAL ==> (X <u MINVAL) ? X : MINVAL ==> 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};
   }
 
   // Look through 'not' ops to find disguised signed min/max.
   // (X >s C) ? ~X : ~C ==> (~X <s ~C) ? ~X : ~C ==> SMIN(~X, ~C)
   // (X <s C) ? ~X : ~C ==> (~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 <s ~C) ? ~C : ~X ==> SMAX(~C, ~X)
   // (X <s C) ? ~C : ~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};
 }
 
 static SelectPatternResult matchSelectPattern(CmpInst::Predicate Pred,
                                               FastMathFlags FMF,
                                               Value *CmpLHS, Value *CmpRHS,
                                               Value *TrueVal, Value *FalseVal,

llvm/trunk/test/Transforms/InstCombine/minmax-fold.ll

 }
 
 ; (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:    [[CMP1:%.*]] = icmp sgt i32 [[X]], 15
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[CMP1]], i32 [[MIN]], i32 15
+; 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 <s C1) ? SMAX(X, C2) : C1 ==> 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:    [[CMP1:%.*]] = icmp slt i32 [[X]], 255
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[CMP1]], i32 [[MAX]], i32 255
+; 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 >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:    [[CMP1:%.*]] = icmp ugt i32 [[X]], 15
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[CMP1]], i32 [[MIN]], i32 15
+; 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 <u C1) ? UMAX(X, C2) : C1 ==> 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:    [[CMP1:%.*]] = icmp ult i32 [[X]], 255
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[CMP1]], i32 [[MAX]], i32 255
+; 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
 }
;
   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:    [[CMP2:%.*]] = icmp slt i32 [[I]], 0
-; CHECK-NEXT:    [[RES:%.*]] = select i1 [[CMP2]], i32 [[SEL1]], i32 0
+; 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
 }