[InstCombine] sub(add(X,Y),umin(Y,Z)) --> add(X,usub.sat(Y,Z))

[Chenbing.Zheng]

Summary

This patch deal with TODO left in D123399.

Alive2: https://alive2.llvm.org/ce/z/2UNVbp

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2043

Is it worth putting the fold within the dyn_cast<MinMaxIntrinsic>(Op1) check above?

llvm/test/Transforms/InstCombine/sub-minmax.ll

734

(style) Don't enumerate tests - use the name to describe the actual test (commutations etc).

767

vector tests?
you probably want negative tests for where the m_Specific() match fails as well

[Chenbing.Zheng]

address comment

[RKSimon]

rebase?

[Chenbing.Zheng]

rebase

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2038

I meant - can you incorporate these tests under the existing dyn_cast<MinMaxIntrinsic> check at Line 2021?

[Chenbing.Zheng]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2038

I try to do it, but the code doesn't get much cleaner and it breaks readability.

[RKSimon]

@nikic Any thoughts?

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2038

At the very least the isa<MinMaxIntrinsic>(Op1) check should be at the top, not inside a loop in which its invariant.

if (isa<MinMaxIntrinsic>(Op1)) {
  Value *X, *Y, *Z;
  Type *Ty = I.getType();
  for (bool Swap : {false, true}) {
    ....
  }
}

[Chenbing.Zheng]

address comment

[RKSimon]

A couple of minors

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2029

(style) Move this inside braces (and the same for the new fold):

{
    Value *X = II->getLHS();
    Value *Y = II->getRHS();
    if (match(Op0, m_c_Add(m_Specific(X), m_Specific(Y))) &&
        (Op0->hasOneUse() || Op1->hasOneUse())) {
      Intrinsic::ID InvID = getInverseMinMaxIntrinsic(II->getIntrinsicID());
      Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, X, Y);
      return replaceInstUsesWith(I, InvMaxMin);
    }
}

2036

Maybe move the "for (bool Swap : {false, true})" loop inside the match to avoid performing the match twice?

[Chenbing.Zheng]

address comments

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2042

Do we have a m_c_UMin that we can use instead?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2042

We do have that matcher, but this would be easier if we match the umin first and then find the common operand in the add?

// sub(add(X,Y),umin(Y,Z)) --> add(X,usub.sat(Y,Z))
// sub(add(X,Z),umin(Y,Z)) --> add(X,usub.sat(Y,Z))
Value *X, *Y, *Z;
if (match(Op1, m_OneUse(m_UMin(m_Value(Y), m_Value(Z)))) &&
    (match(Op0, m_OneUse(m_c_Add(m_Specific(Y), m_Value(X)))) ||
     match(Op0, m_OneUse(m_c_Add(m_Specific(Z), m_Value(X)))))) {
  Value *USub =
      Builder.CreateIntrinsic(Intrinsic::usub_sat, I.getType(), {Y, Z});
  return BinaryOperator::CreateAdd(X, USub);
}

[Chenbing.Zheng]

According to spatel's suggestion.

[RKSimon]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(Op0, m_OneUse(m_And(m_Specific(Op1), m_Constant(C))))) {
       return BinaryOperator::CreateNeg(
           Builder.CreateAnd(Op1, Builder.CreateNot(C)));
     }
   }
 
   {
     // sub(add(X,Y), s/umin(X,Y)) --> s/umax(X,Y)
     // sub(add(X,Y), s/umax(X,Y)) --> s/umin(X,Y)
-    // TODO: generalize to sub(add(Z,Y),umin(X,Y)) --> add(Z,usub.sat(Y,X))?
     if (auto *II = dyn_cast<MinMaxIntrinsic>(Op1)) {
       Value *X = II->getLHS();
       Value *Y = II->getRHS();
       if (match(Op0, m_c_Add(m_Specific(X), m_Specific(Y))) &&
           (Op0->hasOneUse() || Op1->hasOneUse())) {
         Intrinsic::ID InvID = getInverseMinMaxIntrinsic(II->getIntrinsicID());
         Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, X, Y);
         return replaceInstUsesWith(I, InvMaxMin);
       }
     }
   }
 
   {
+    // sub(add(X,Y),umin(Y,Z)) --> add(X,usub.sat(Y,Z))
+    Value *X, *Y, *Z;
+    Type *Ty = I.getType();
+    for (bool Swap : {false, true}) {
+      if (!isa<MinMaxIntrinsic>(Op1))
+        break;
+      if (match(Op0, m_c_Add(m_Value(X), m_Value(Y))) && Op0->hasOneUse() &&
+          Op1->hasOneUse()) {
+        if (Swap)
+          std::swap(X, Y);
+        if (match(Op1, m_UMin(m_Specific(Y), m_Value(Z))) ||
+            match(Op1, m_UMin(m_Value(Z), m_Specific(Y)))) {
+          Value *USub =
+              Builder.CreateIntrinsic(Intrinsic::usub_sat, {Ty}, {Y, Z});
+          return BinaryOperator::CreateAdd(X, USub);
+        }
+      }
+    }
+  }
+
+  {
     // If we have a subtraction between some value and a select between
     // said value and something else, sink subtraction into select hands, i.e.:
     //   sub (select %Cond, %TrueVal, %FalseVal), %Op1
     //     ->
     //   select %Cond, (sub %TrueVal, %Op1), (sub %FalseVal, %Op1)
     //  or
     //   sub %Op0, (select %Cond, %TrueVal, %FalseVal)
     //     ->

llvm/test/Transforms/InstCombine/sub-minmax.ll

 }
 
 ;
 ; TODO: sub(add(X,Y),umin(Y,Z)) --> add(X,usubsat(Y,Z))
 ;
 
 define i8 @sub_add_umin(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @sub_add_umin(
-; CHECK-NEXT:    [[A:%.*]] = add i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[Y]], i8 [[Z:%.*]])
-; CHECK-NEXT:    [[S:%.*]] = sub i8 [[A]], [[M]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[Y:%.*]], i8 [[Z:%.*]])
+; CHECK-NEXT:    [[S:%.*]] = add i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[S]]
 ;
   %a = add i8 %x, %y
   %m = call i8 @llvm.umin.i8(i8 %y, i8 %z)
   %s = sub i8 %a, %m
   ret i8 %s
 }
 
 define i8 @sub_add_umin_commute_umin(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @sub_add_umin_commute_umin(
-; CHECK-NEXT:    [[A:%.*]] = add i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[Z:%.*]], i8 [[Y]])
-; CHECK-NEXT:    [[S:%.*]] = sub i8 [[A]], [[M]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[Y:%.*]], i8 [[Z:%.*]])
+; CHECK-NEXT:    [[S:%.*]] = add i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[S]]
 ;
   %a = add i8 %x, %y
   %m = call i8 @llvm.umin.i8(i8 %z, i8 %y)
   %s = sub i8 %a, %m
   ret i8 %s
 }
 
 define i8 @sub_add_umin_commute_add(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @sub_add_umin_commute_add(
-; CHECK-NEXT:    [[A:%.*]] = add i8 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[Y]], i8 [[Z:%.*]])
-; CHECK-NEXT:    [[S:%.*]] = sub i8 [[A]], [[M]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[Y:%.*]], i8 [[Z:%.*]])
+; CHECK-NEXT:    [[S:%.*]] = add i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[S]]
 ;
   %a = add i8 %y, %x
   %m = call i8 @llvm.umin.i8(i8 %y, i8 %z)
   %s = sub i8 %a, %m
   ret i8 %s
 }
 
 define i8 @sub_add_umin_commute_add_umin(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @sub_add_umin_commute_add_umin(
-; CHECK-NEXT:    [[A:%.*]] = add i8 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[Z:%.*]], i8 [[Y]])
-; CHECK-NEXT:    [[S:%.*]] = sub i8 [[A]], [[M]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.usub.sat.i8(i8 [[Y:%.*]], i8 [[Z:%.*]])
+; CHECK-NEXT:    [[S:%.*]] = add i8 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[S]]
 ;
   %a = add i8 %y, %x
   %m = call i8 @llvm.umin.i8(i8 %z, i8 %y)
   %s = sub i8 %a, %m
   ret i8 %s
 }
 
 define <2 x i8> @sub_add_umin_vec(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
 ; CHECK-LABEL: @sub_add_umin_vec(
-; CHECK-NEXT:    [[A:%.*]] = add <2 x i8> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[M:%.*]] = call <2 x i8> @llvm.umin.v2i8(<2 x i8> [[Y]], <2 x i8> [[Z:%.*]])
-; CHECK-NEXT:    [[S:%.*]] = sub <2 x i8> [[A]], [[M]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i8> @llvm.usub.sat.v2i8(<2 x i8> [[Y:%.*]], <2 x i8> [[Z:%.*]])
+; CHECK-NEXT:    [[S:%.*]] = add <2 x i8> [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret <2 x i8> [[S]]
 ;
   %a = add <2 x i8> %x, %y
   %m = call <2 x i8> @llvm.umin.v2i8(<2 x i8> %y, <2 x i8> %z)
   %s = sub <2 x i8> %a, %m
   ret <2 x i8> %s
 }