[InstCombine] Reduce absolute diff from min+max+sub

[junaire]

Summary

This patch implement fold: max(a,b) nsw/nuw - min(a,b) --> abs(a nsw - b)

Alive2: https://alive2.llvm.org/ce/z/4yLp7D
Fixes: https://github.com/llvm/llvm-project/issues/61228

Signed-off-by: Jun Zhang <[e-mail]>

[junaire]

Apply clang-format.

[RKSimon]

Please can you rebase after rG4585b54d660b1570f7dd1649fb13cf3d38cc502a ?

[junaire]

Rebase

[junaire]

Make clang-format happy

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2413

What about cases where we have smin(Y,X) instead?

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

1141

multi use negative tests?

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2413

Also, don't we have m_SMax / m_SMin ?

[junaire]

Update commute tests and negative tests

[RKSimon]

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

1035

shouldn't this be:

%max = call i8 @llvm.smax.i8(i8 %a, i8 %b)

[junaire]

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

1035

shouldn't this be:

%max = call i8 @llvm.smax.i8(i8 %a, i8 %b)

IIUC, we should test all the following cases?

1. max(a, b) - min(a, b)
2. max(b, a) - min(b, a)
3. max(a, b) - min(b, a)
4. max(b, a) - min(a, b)

However, I'm not certain it is worth doing so. I'll pick case 1 and case 3 then.

[junaire]

Update tests.

[RKSimon]

LGTM - cheers

[junaire]

In D145540#4182018, @RKSimon wrote:

LGTM - cheers

Thank you, Simon!

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(Op0, m_OneUse(m_Mul(m_Value(X), m_Deferred(X)))) &&
     bool PropagateNUW = I.hasNoUnsignedWrap() && OBO0->hasNoUnsignedWrap() &&
                         OBO1->hasNoUnsignedWrap() && BitWidth > 1;
     Value *Add = Builder.CreateAdd(X, Y, "add", PropagateNUW, PropagateNSW);
     Value *Sub = Builder.CreateSub(X, Y, "sub", PropagateNUW, PropagateNSW);
     Value *Mul = Builder.CreateMul(Add, Sub, "", PropagateNUW, PropagateNSW);
     return replaceInstUsesWith(I, Mul);
   }
 
+  // max(X,Y) nsw/nuw - min(X,Y) --> abs(X nsw - Y)
+  if (match(Op0, m_OneUse(m_c_SMax(m_Value(X), m_Value(Y)))) &&
+      match(Op1, m_OneUse(m_c_SMin(m_Specific(X), m_Specific(Y))))) {
+    if (I.hasNoUnsignedWrap() || I.hasNoSignedWrap()) {
+      Value *Sub =
+          Builder.CreateSub(X, Y, "sub", /*HasNUW=*/false, /*HasNSW=*/true);
+      Value *Call =
+          Builder.CreateBinaryIntrinsic(Intrinsic::abs, Sub, Builder.getTrue());
+      return replaceInstUsesWith(I, Call);
+    }
+  }
+
   return TryToNarrowDeduceFlags();
 }
 
 /// This eliminates floating-point negation in either 'fneg(X)' or
 /// 'fsub(-0.0, X)' form by combining into a constant operand.
 static Instruction *foldFNegIntoConstant(Instruction &I, const DataLayout &DL) {
   // This is limited with one-use because fneg is assumed better for
   // reassociation and cheaper in codegen than fmul/fdiv.

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

;
   %m = call i8 @llvm.smin.i8(i8 %sub, i8 0)
   %r = sub i8 %x, %m
   ret i8 %r
 }
 
 define i8 @sub_max_min_nsw(i8 %a, i8 %b) {
 ; CHECK-LABEL: define {{[^@]+}}@sub_max_min_nsw
 ; CHECK-SAME: (i8 [[A:%.*]], i8 [[B:%.*]]) {
-; CHECK-NEXT:    [[MIN:%.*]] = call i8 @llvm.smin.i8(i8 [[A]], i8 [[B]])
-; CHECK-NEXT:    [[MAX:%.*]] = call i8 @llvm.smax.i8(i8 [[A]], i8 [[B]])
-; CHECK-NEXT:    [[AB:%.*]] = sub nsw i8 [[MAX]], [[MIN]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i8 [[A]], [[B]]
+; CHECK-NEXT:    [[AB:%.*]] = call i8 @llvm.abs.i8(i8 [[SUB]], i1 true)
 ; CHECK-NEXT:    ret i8 [[AB]]
 ;
   %min = call i8 @llvm.smin.i8(i8 %a, i8 %b)
   %max = call i8 @llvm.smax.i8(i8 %a, i8 %b)
   %ab = sub nsw i8 %max, %min
   ret i8 %ab
 }
 
 define i8 @sub_max_min_nuw(i8 %a, i8 %b) {
 ; CHECK-LABEL: define {{[^@]+}}@sub_max_min_nuw
 ; CHECK-SAME: (i8 [[A:%.*]], i8 [[B:%.*]]) {
-; CHECK-NEXT:    [[MIN:%.*]] = call i8 @llvm.smin.i8(i8 [[A]], i8 [[B]])
-; CHECK-NEXT:    [[MAX:%.*]] = call i8 @llvm.smax.i8(i8 [[A]], i8 [[B]])
-; CHECK-NEXT:    [[AB:%.*]] = sub nuw i8 [[MAX]], [[MIN]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i8 [[A]], [[B]]
+; CHECK-NEXT:    [[AB:%.*]] = call i8 @llvm.abs.i8(i8 [[SUB]], i1 true)
 ; CHECK-NEXT:    ret i8 [[AB]]
 ;
   %min = call i8 @llvm.smin.i8(i8 %a, i8 %b)
   %max = call i8 @llvm.smax.i8(i8 %a, i8 %b)
   %ab = sub nuw i8 %max, %min
   ret i8 %ab
 }
 
+define i8 @sub_max_min_nsw_commute(i8 %a, i8 %b) {
+; CHECK-LABEL: define {{[^@]+}}@sub_max_min_nsw_commute
+; CHECK-SAME: (i8 [[A:%.*]], i8 [[B:%.*]]) {
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i8 [[A]], [[B]]
+; CHECK-NEXT:    [[AB:%.*]] = call i8 @llvm.abs.i8(i8 [[SUB]], i1 true)
+; CHECK-NEXT:    ret i8 [[AB]]
+;
+  %min = call i8 @llvm.smin.i8(i8 %b, i8 %a)
+  %max = call i8 @llvm.smax.i8(i8 %a, i8 %b)
+  %ab = sub nsw i8 %max, %min
+  ret i8 %ab
+}
+
+define i8 @sub_max_min_nuw_commute(i8 %a, i8 %b) {
+; CHECK-LABEL: define {{[^@]+}}@sub_max_min_nuw_commute
+; CHECK-SAME: (i8 [[A:%.*]], i8 [[B:%.*]]) {
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i8 [[A]], [[B]]
+; CHECK-NEXT:    [[AB:%.*]] = call i8 @llvm.abs.i8(i8 [[SUB]], i1 true)
+; CHECK-NEXT:    ret i8 [[AB]]
+;
+  %min = call i8 @llvm.smin.i8(i8 %b, i8 %a)
+  %max = call i8 @llvm.smax.i8(i8 %a, i8 %b)
+  %ab = sub nuw i8 %max, %min
+  ret i8 %ab
+}
+
 define <2 x i8> @sub_max_min_vec_nsw(<2 x i8> %a, <2 x i8> %b) {
 ; CHECK-LABEL: define {{[^@]+}}@sub_max_min_vec_nsw
 ; CHECK-SAME: (<2 x i8> [[A:%.*]], <2 x i8> [[B:%.*]]) {
-; CHECK-NEXT:    [[MIN:%.*]] = call <2 x i8> @llvm.smin.v2i8(<2 x i8> [[A]], <2 x i8> [[B]])
-; CHECK-NEXT:    [[MAX:%.*]] = call <2 x i8> @llvm.smax.v2i8(<2 x i8> [[A]], <2 x i8> [[B]])
-; CHECK-NEXT:    [[AB:%.*]] = sub nsw <2 x i8> [[MAX]], [[MIN]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw <2 x i8> [[A]], [[B]]
+; CHECK-NEXT:    [[AB:%.*]] = call <2 x i8> @llvm.abs.v2i8(<2 x i8> [[SUB]], i1 true)
 ; CHECK-NEXT:    ret <2 x i8> [[AB]]
 ;
   %min = call <2 x i8> @llvm.smin.v2i8(<2 x i8> %a, <2 x i8> %b)
   %max = call <2 x i8> @llvm.smax.v2i8(<2 x i8> %a, <2 x i8> %b)
   %ab = sub nsw <2 x i8> %max, %min
   ret <2 x i8> %ab
 }
 
 define <2 x i8> @sub_max_min_vec_nuw(<2 x i8> %a, <2 x i8> %b) {
 ; CHECK-LABEL: define {{[^@]+}}@sub_max_min_vec_nuw
 ; CHECK-SAME: (<2 x i8> [[A:%.*]], <2 x i8> [[B:%.*]]) {
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw <2 x i8> [[A]], [[B]]
+; CHECK-NEXT:    [[AB:%.*]] = call <2 x i8> @llvm.abs.v2i8(<2 x i8> [[SUB]], i1 true)
+; CHECK-NEXT:    ret <2 x i8> [[AB]]
+;
+  %min = call <2 x i8> @llvm.smin.v2i8(<2 x i8> %a, <2 x i8> %b)
+  %max = call <2 x i8> @llvm.smax.v2i8(<2 x i8> %a, <2 x i8> %b)
+  %ab = sub nuw <2 x i8> %max, %min
+  ret <2 x i8> %ab
+}
+
+define <2 x i8> @sub_max_min_vec_nsw_commute(<2 x i8> %a, <2 x i8> %b) {
+; CHECK-LABEL: define {{[^@]+}}@sub_max_min_vec_nsw_commute
+; CHECK-SAME: (<2 x i8> [[A:%.*]], <2 x i8> [[B:%.*]]) {
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw <2 x i8> [[A]], [[B]]
+; CHECK-NEXT:    [[AB:%.*]] = call <2 x i8> @llvm.abs.v2i8(<2 x i8> [[SUB]], i1 true)
+; CHECK-NEXT:    ret <2 x i8> [[AB]]
+;
+  %min = call <2 x i8> @llvm.smin.v2i8(<2 x i8> %b, <2 x i8> %a)
+  %max = call <2 x i8> @llvm.smax.v2i8(<2 x i8> %a, <2 x i8> %b)
+  %ab = sub nsw <2 x i8> %max, %min
+  ret <2 x i8> %ab
+}
+
+define <2 x i8> @sub_max_min_vec_nuw_commute(<2 x i8> %a, <2 x i8> %b) {
+; CHECK-LABEL: define {{[^@]+}}@sub_max_min_vec_nuw_commute
+; CHECK-SAME: (<2 x i8> [[A:%.*]], <2 x i8> [[B:%.*]]) {
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw <2 x i8> [[A]], [[B]]
+; CHECK-NEXT:    [[AB:%.*]] = call <2 x i8> @llvm.abs.v2i8(<2 x i8> [[SUB]], i1 true)
+; CHECK-NEXT:    ret <2 x i8> [[AB]]
+;
+  %min = call <2 x i8> @llvm.smin.v2i8(<2 x i8> %b, <2 x i8> %a)
+  %max = call <2 x i8> @llvm.smax.v2i8(<2 x i8> %a, <2 x i8> %b)
+  %ab = sub nuw <2 x i8> %max, %min
+  ret <2 x i8> %ab
+}
+
+; negative test - multiple use
+
+define i8 @sub_max_min_multi_use(i8 %a, i8 %b) {
+; CHECK-LABEL: define {{[^@]+}}@sub_max_min_multi_use
+; CHECK-SAME: (i8 [[A:%.*]], i8 [[B:%.*]]) {
+; CHECK-NEXT:    [[MIN:%.*]] = call i8 @llvm.smin.i8(i8 [[A]], i8 [[B]])
+; CHECK-NEXT:    call void @use8(i8 [[MIN]])
+; CHECK-NEXT:    [[MAX:%.*]] = call i8 @llvm.smax.i8(i8 [[A]], i8 [[B]])
+; CHECK-NEXT:    call void @use8(i8 [[MAX]])
+; CHECK-NEXT:    [[AB:%.*]] = sub nsw i8 [[MAX]], [[MIN]]
+; CHECK-NEXT:    ret i8 [[AB]]
+;
+  %min = call i8 @llvm.smin.i8(i8 %a, i8 %b)
+  call void @use8(i8 %min)
+  %max = call i8 @llvm.smax.i8(i8 %a, i8 %b)
+  call void @use8(i8 %max)
+  %ab = sub nsw i8 %max, %min
+  ret i8 %ab
+}
+
+define <2 x i8> @sub_max_min_vec_multi_use(<2 x i8> %a, <2 x i8> %b) {
+; CHECK-LABEL: define {{[^@]+}}@sub_max_min_vec_multi_use
+; CHECK-SAME: (<2 x i8> [[A:%.*]], <2 x i8> [[B:%.*]]) {
 ; CHECK-NEXT:    [[MIN:%.*]] = call <2 x i8> @llvm.smin.v2i8(<2 x i8> [[A]], <2 x i8> [[B]])
+; CHECK-NEXT:    call void @use8v2(<2 x i8> [[MIN]])
 ; CHECK-NEXT:    [[MAX:%.*]] = call <2 x i8> @llvm.smax.v2i8(<2 x i8> [[A]], <2 x i8> [[B]])
-; CHECK-NEXT:    [[AB:%.*]] = sub nuw <2 x i8> [[MAX]], [[MIN]]
+; CHECK-NEXT:    call void @use8v2(<2 x i8> [[MAX]])
+; CHECK-NEXT:    [[AB:%.*]] = sub nsw <2 x i8> [[MAX]], [[MIN]]
 ; CHECK-NEXT:    ret <2 x i8> [[AB]]
 ;
   %min = call <2 x i8> @llvm.smin.v2i8(<2 x i8> %a, <2 x i8> %b)
+  call void @use8v2(<2 x i8> %min)
   %max = call <2 x i8> @llvm.smax.v2i8(<2 x i8> %a, <2 x i8> %b)
-  %ab = sub nuw <2 x i8> %max, %min
+  call void @use8v2(<2 x i8> %max)
+  %ab = sub nsw <2 x i8> %max, %min
   ret <2 x i8> %ab
 }
 
 declare void @use8(i8)
 declare void @use32(i32 %u)
+
+declare void @use8v2(i8)