[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

2056

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

2051

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

2051

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

2051

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

// (sub (xor A, B) (or A, B)) --> neg (and A, B)
     // (sub (and Op1, C), Op1) --> neg (and Op1, ~C)
     Constant *C;
     if (match(Op0, m_OneUse(m_And(m_Specific(Op1), m_Constant(C))))) {
       return BinaryOperator::CreateNeg(
           Builder.CreateAnd(Op1, Builder.CreateNot(C)));
     }
   }
 
+  if (auto *II = dyn_cast<MinMaxIntrinsic>(Op1)) {
     {
       // 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))
+      // 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);
+      }
+    }
   }
 
   {
     // 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)
     //     ->
     //   select %Cond, (sub %Op0, %TrueVal), (sub %Op0, %FalseVal)
     // This will result in select between new subtraction and 0.
     auto SinkSubIntoSelect =
         [Ty = I.getType()](Value *Select, Value *OtherHandOfSub,
                            auto SubBuilder) -> Instruction * {
       Value *Cond, *TrueVal, *FalseVal;
       if (!match(Select, m_OneUse(m_Select(m_Value(Cond), m_Value(TrueVal),
                                            m_Value(FalseVal)))))
         return nullptr;
       if (OtherHandOfSub != TrueVal && OtherHandOfSub != 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
 }