[InstCombine] add folds for icmp (smin X, Y), X

[spatel]

Summary

As Volkan noted in the commit thread for rL287585, min/max canonicalization exposes the fact that we're missing combines for min/max patterns. This patch won't solve the example that was attached to that thread, so something else still needs fixing.

The line between InstCombine and InstSimplify gets blurry here because sometimes the icmp instruction that we want to fold to already exists, but sometimes it's the swapped form of what we want.

Also note that there's yet another definition of min/max via the matcher patterns (I didn't find these until recently). I'm still hoping to canonicalize the non-standard patterns detected by matchSelectPattern(), so I went ahead and used m_SMin here even though I think that means those non-standard patterns will fall through for now.

Once this looks ok, I can follow up with the corresponding smax/umin/umax.

[spatel]

Patch updated:
It makes the patch smaller (static function, no need for a switch) to not consider the fold to true/false cases that are obviously handled by InstSimplify, so I removed that part.

[majnemer]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3040–3041 ↗

(On Diff #80649)

Might be nice to have a m_c_SMin or something, would simplify this expression and the one bellow.

[spatel]

Patch updated:
Add and use a commutable SMin matcher as suggested by David.

[spatel]

Ping.

[jmolloy]

LGTM!

llvm/trunk/include/llvm/IR/PatternMatch.h

 /// \brief Matches an Xor with LHS and RHS in either order.
 template<typename LHS, typename RHS>
 inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Xor>,
                         BinaryOp_match<RHS, LHS, Instruction::Xor>>
 m_c_Xor(const LHS &L, const RHS &R) {
   return m_CombineOr(m_Xor(L, R), m_Xor(R, L));
 }
 
+// TODO: Add the related SMax, UMax, UMin commuted matchers.
+
+/// Matches an SMin with LHS and RHS in either order.
+template<typename LHS, typename RHS>
+inline match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>,
+                        MaxMin_match<ICmpInst, RHS, LHS, smin_pred_ty>>
+m_c_SMin(const LHS &L, const RHS &R) {
+  return m_CombineOr(m_SMin(L, R), m_SMin(R, L));
+}
+
 } // end namespace PatternMatch
 } // end namespace llvm
 
 #endif

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (match(BO0, BitwiseAnd) && I.getPredicate() == ICmpInst::ICMP_ULT) {
       auto *Zero = Constant::getNullValue(BO0->getType());
       return new ICmpInst(ICmpInst::ICMP_NE, Op1, Zero);
     }
   }
 
   return nullptr;
 }
 
+/// Fold icmp Pred smin(X, Y), X.
+static Instruction *foldICmpWithSMin(ICmpInst &Cmp) {
+  ICmpInst::Predicate Pred = Cmp.getPredicate();
+  Value *Op0 = Cmp.getOperand(0);
+  Value *X = Cmp.getOperand(1);
+
+  // TODO: This should be expanded to handle smax/umax/umin.
+
+  // Canonicalize minimum operand to LHS of the icmp.
+  if (match(X, m_c_SMin(m_Specific(Op0), m_Value()))) {
+    std::swap(Op0, X);
+    Pred = Cmp.getSwappedPredicate();
+  }
+
+  Value *Y;
+  if (!match(Op0, m_c_SMin(m_Specific(X), m_Value(Y))))
+    return nullptr;
+
+  // smin(X, Y) == X --> X <= Y
+  // smin(X, Y) >= X --> X <= Y
+  if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_SGE)
+    return new ICmpInst(ICmpInst::ICMP_SLE, X, Y);
+
+  // smin(X, Y) != X --> X > Y
+  // smin(X, Y) <  X --> X > Y
+  if (Pred == CmpInst::ICMP_NE || Pred == CmpInst::ICMP_SLT)
+    return new ICmpInst(ICmpInst::ICMP_SGT, X, Y);
+
+  // These cases should be handled in InstSimplify:
+  // smin(X, Y) <= X --> true
+  // smin(X, Y) > X --> false
+  return nullptr;
+}
+
 Instruction *InstCombiner::foldICmpEquality(ICmpInst &I) {
   if (!I.isEquality())
     return nullptr;
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   Value *A, *B, *C, *D;
   if (match(Op0, m_Xor(m_Value(A), m_Value(B)))) {
     if (A == Op1 || B == Op1) { // (A^B) == A  ->  B == 0
if (isa<CastInst>(Op0)) {
     if (isa<Constant>(Op1) || isa<CastInst>(Op1))
       if (Instruction *R = foldICmpWithCastAndCast(I))
         return R;
   }
 
   if (Instruction *Res = foldICmpBinOp(I))
     return Res;
 
+  if (Instruction *Res = foldICmpWithSMin(I))
+    return Res;
+
   {
     Value *A, *B;
     // Transform (A & ~B) == 0 --> (A & B) != 0
     // and       (A & ~B) != 0 --> (A & B) == 0
     // if A is a power of 2.
     if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
         match(Op1, m_Zero()) &&
         isKnownToBeAPowerOfTwo(A, DL, false, 0, &I, &DT) && I.isEquality())

llvm/trunk/test/Transforms/InstCombine/smin-icmp.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine < %s | FileCheck %s
 
 ; If we have an smin feeding a signed or equality icmp that shares an
 ; operand with the smin, the compare should always be folded.
 ; Test all 6 foldable predicates (eq,ne,sge,sgt,sle,slt) * 4 commutation
 ; possibilities for each predicate. Note that folds to true/false or
 ; folds to an existing instruction may be handled by InstSimplify.
 
 ; smin(X, Y) == X --> X <= Y
 
 define i1 @eq_smin1(i32 %x, i32 %y) {
 ; CHECK-LABEL: @eq_smin1(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 %x, %y
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32 %x, i32 %y
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[SEL]], %x
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 %x, %y
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp1 = icmp slt i32 %x, %y
   %sel = select i1 %cmp1, i32 %x, i32 %y
   %cmp2 = icmp eq i32 %sel, %x
   ret i1 %cmp2
 }
 
 ; Commute min operands.
 
 define i1 @eq_smin2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @eq_smin2(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 %y, %x
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32 %y, i32 %x
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[SEL]], %x
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 %x, %y
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp1 = icmp slt i32 %y, %x
   %sel = select i1 %cmp1, i32 %y, i32 %x
   %cmp2 = icmp eq i32 %sel, %x
   ret i1 %cmp2
 }
 
 ; Disguise the icmp predicate by commuting the min op to the RHS.
 
 define i1 @eq_smin3(i32 %a, i32 %y) {
 ; CHECK-LABEL: @eq_smin3(
 ; CHECK-NEXT:    [[X:%.*]] = add i32 %a, 3
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[X]], %y
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32 [[X]], i32 %y
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[X]], [[SEL]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[X]], %y
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %x = add i32 %a, 3 ; thwart complexity-based canonicalization
   %cmp1 = icmp slt i32 %x, %y
   %sel = select i1 %cmp1, i32 %x, i32 %y
   %cmp2 = icmp eq i32 %x, %sel
   ret i1 %cmp2
 }
 
 ; Commute min operands.
 
 define i1 @eq_smin4(i32 %a, i32 %y) {
 ; CHECK-LABEL: @eq_smin4(
 ; CHECK-NEXT:    [[X:%.*]] = add i32 %a, 3
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i32 [[X]], %y
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32 %y, i32 [[X]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[X]], [[SEL]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[X]], %y
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %x = add i32 %a, 3 ; thwart complexity-based canonicalization
   %cmp1 = icmp slt i32 %y, %x
   %sel = select i1 %cmp1, i32 %y, i32 %x
   %cmp2 = icmp eq i32 %x, %sel
   ret i1 %cmp2
 }
 
 ; smin(X, Y) >= X --> X <= Y
 
 define i1 @sge_smin1(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sge_smin1(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 %x, %y
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32 %x, i32 %y
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sge i32 [[SEL]], %x
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 %x, %y
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp1 = icmp slt i32 %x, %y
   %sel = select i1 %cmp1, i32 %x, i32 %y
   %cmp2 = icmp sge i32 %sel, %x
   ret i1 %cmp2
 }
 
 ; Commute min operands.
 
 define i1 @sge_smin2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sge_smin2(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 %y, %x
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32 %y, i32 %x
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sge i32 [[SEL]], %x
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 %x, %y
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp1 = icmp slt i32 %y, %x
   %sel = select i1 %cmp1, i32 %y, i32 %x
   %cmp2 = icmp sge i32 %sel, %x
   ret i1 %cmp2
 }
 
 ; Disguise the icmp predicate by commuting the min op to the RHS.
 
 define i1 @sge_smin3(i32 %a, i32 %y) {
 ; CHECK-LABEL: @sge_smin3(
 ; CHECK-NEXT:    [[X:%.*]] = add i32 %a, 3
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[X]], %y
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32 [[X]], i32 %y
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[X]], [[SEL]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[X]], %y
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %x = add i32 %a, 3 ; thwart complexity-based canonicalization
   %cmp1 = icmp slt i32 %x, %y
   %sel = select i1 %cmp1, i32 %x, i32 %y
   %cmp2 = icmp sle i32 %x, %sel
   ret i1 %cmp2
 }
 
 ; Commute min operands.
 
 define i1 @sge_smin4(i32 %a, i32 %y) {
 ; CHECK-LABEL: @sge_smin4(
 ; CHECK-NEXT:    [[X:%.*]] = add i32 %a, 3
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i32 [[X]], %y
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32 %y, i32 [[X]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[X]], [[SEL]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sle i32 [[X]], %y
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %x = add i32 %a, 3 ; thwart complexity-based canonicalization
   %cmp1 = icmp slt i32 %y, %x
   %sel = select i1 %cmp1, i32 %y, i32 %x
   %cmp2 = icmp sle i32 %x, %sel
   ret i1 %cmp2
 }
 
 ; smin(X, Y) != X --> X > Y
 
 define i1 @ne_smin1(i32 %x, i32 %y) {
 ; CHECK-LABEL: @ne_smin1(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 %x, %y
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32 %x, i32 %y
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[SEL]], %x
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 %x, %y
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp1 = icmp slt i32 %x, %y
   %sel = select i1 %cmp1, i32 %x, i32 %y
   %cmp2 = icmp ne i32 %sel, %x
   ret i1 %cmp2
 }
 
;
   ret i1 %cmp2
 }
 
 ; Disguise the icmp predicate by commuting the min op to the RHS.
 
 define i1 @ne_smin3(i32 %a, i32 %y) {
 ; CHECK-LABEL: @ne_smin3(
 ; CHECK-NEXT:    [[X:%.*]] = add i32 %a, 3
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[X]], %y
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32 [[X]], i32 %y
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[X]], [[SEL]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[X]], %y
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %x = add i32 %a, 3 ; thwart complexity-based canonicalization
   %cmp1 = icmp slt i32 %x, %y
   %sel = select i1 %cmp1, i32 %x, i32 %y
   %cmp2 = icmp ne i32 %x, %sel
   ret i1 %cmp2
 }
;
   %cmp2 = icmp ne i32 %x, %sel
   ret i1 %cmp2
 }
 
 ; smin(X, Y) < X --> X > Y
 
 define i1 @slt_smin1(i32 %x, i32 %y) {
 ; CHECK-LABEL: @slt_smin1(
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 %x, %y
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32 %x, i32 %y
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[SEL]], %x
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 %x, %y
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %cmp1 = icmp slt i32 %x, %y
   %sel = select i1 %cmp1, i32 %x, i32 %y
   %cmp2 = icmp slt i32 %sel, %x
   ret i1 %cmp2
 }
 
;
   ret i1 %cmp2
 }
 
 ; Disguise the icmp predicate by commuting the min op to the RHS.
 
 define i1 @slt_smin3(i32 %a, i32 %y) {
 ; CHECK-LABEL: @slt_smin3(
 ; CHECK-NEXT:    [[X:%.*]] = add i32 %a, 3
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[X]], %y
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP1]], i32 [[X]], i32 %y
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[X]], [[SEL]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[X]], %y
 ; CHECK-NEXT:    ret i1 [[CMP2]]
 ;
   %x = add i32 %a, 3 ; thwart complexity-based canonicalization
   %cmp1 = icmp slt i32 %x, %y
   %sel = select i1 %cmp1, i32 %x, i32 %y
   %cmp2 = icmp sgt i32 %x, %sel
   ret i1 %cmp2
 }