[InstCombine] Fold abs of known sign operand when source is sub

[Allen]

Summary

abs(x-y) --> x-y where x >= y, done on D122013
abs(x-y) --> y-x where x <= y

proofs: https://alive2.llvm.org/ce/z/KkeEsd

[goldstein.w.n]

Can you add alive2 links?

llvm/test/Transforms/InstCombine/abs-intrinsic.ll

533

Can you split the new tests to a separate commit?

[Allen]

In D156499#4541169, @goldstein.w.n wrote:

Can you add alive2 links?

Thanks for your attention, I already put the each alive2 link before the matched cases, so do you mean I also should put that in the MR description ?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1032

This looks incorrect from the perspective of the getKnownSign() API. You are returning sign 1 for value 0, which is incorrect. It does work out for the abs optimization because -0 == 0, but it may matter in other cases.

[Allen]

address comment, move the transform out of the getKnownSign to avoid breaking the perspective of the getKnownSign() API

[Allen]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1032

thanks, I move it out of the getKnownSign() API.

llvm/test/Transforms/InstCombine/abs-intrinsic.ll

533

Done on https://reviews.llvm.org/D156521, thanks

[Allen]

ping ?

[goldstein.w.n]

In D156499#4541684, @Allen wrote:

In D156499#4541169, @goldstein.w.n wrote:

Can you add alive2 links?

Thanks for your attention, I already put the each alive2 link before the matched cases, so do you mean I also should put that in the MR description ?

Bah sorry for not following up on this, but where are the alive2 links?

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1555

This is incorrect if the abs allows INT_MIN: https://alive2.llvm.org/ce/z/YNcdRW
It needs to create a new sub w.o nsw.

[Allen]

Thanks for your attention, I already put the each alive2 link before the matched cases, so do you mean I also should put that in the MR description ?

Bah sorry for not following up on this, but where are the alive2 links?

hi @goldstein.w.n，I usually add the alive2 links before the matched cases because there is more than 1 case, such as line 455 in file Transforms/InstCombine/abs-intrinsic.ll (it is more obvious on D156521)
do you mean it is better to put that in the MR description, too ?

[goldstein.w.n]

In D156499#4549679, @Allen wrote:

Thanks for your attention, I already put the each alive2 link before the matched cases, so do you mean I also should put that in the MR description ?

Bah sorry for not following up on this, but where are the alive2 links?

hi @goldstein.w.n，I usually add the alive2 links before the matched cases because there is more than 1 case, such as line 455 in file Transforms/InstCombine/abs-intrinsic.ll (it is more obvious on D156521)
do you mean it is better to put that in the MR description, too ?

MR?

I mean the commit message of this patch (and summary in phab if the two should ever desync).

[Allen]

Address comment
1、Add proof link alive2, https://alive2.llvm.org/ce/z/KkeEsd
2、abs allows INT_MIN，and its related tests

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1521

You also do abs(x-y) --> x - y where x > y.

[Allen]

rebase for 2 new tests

[Allen]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1521

Apply your comment, thanks

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1536

Sorry, noticed this a bit late, but is there a way we can avoid essentially recreating the logic below and instead just add something like getKnownSignOrZero which wraps getKnownSign but also tries SLE if the SLT analysis isn't fruitful? Then you could just replace the function here and we wouldn't need to duplicate so much codes.

[Allen]

Address comment, and a new helper function getKnownSignOrZero

[Allen]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1536

Thanks for your idea. I try that, it work, but will missing nsw for some case, such as src_sub_abs_sleF.
This is because we don't create the a nsw with the two operands of IIOperand, ie
when we match match(IIOperand, m_NSWSub(m_Value(X), m_Value(Y)))

• BinaryOperator::CreateNSWSub(Y, X) will final has a extra nsw
• BinaryOperator::CreateNSWNeg(IIOperand) will miss the nsw, so need a following PR D157187

[goldstein.w.n]

LGTM.

llvm/test/Transforms/InstCombine/abs-intrinsic.ll

578

Imo missing a test with sge i8 %y, %x. Also missing a test where the sub is in the false case (i.e sgt %x, %y but abs in false case).

[Allen]

rebase after 2 new tests sub_abs_sgeT_swap and sub_abs_sgeT_false

[Allen]

llvm/test/Transforms/InstCombine/abs-intrinsic.ll

578

Done, thanks! Added new cases sub_abs_sgeT_swap and sub_abs_sgeT_false

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

     Value *X;
     if (match(IIOperand, m_Neg(m_Value(X))))
       return replaceOperand(*II, 0, X);
     if (match(IIOperand, m_Select(m_Value(), m_Value(X), m_Neg(m_Deferred(X)))))
       return replaceOperand(*II, 0, X);
     if (match(IIOperand, m_Select(m_Value(), m_Neg(m_Value(X)), m_Deferred(X))))
       return replaceOperand(*II, 0, X);
 
+    // abs(x-y) --> y-x where x <= y
+    Value *Y;
+    if (match(IIOperand, m_NSWSub(m_Value(X), m_Value(Y)))) {
+      if (std::optional<bool> Known =
+              isImpliedByDomCondition(ICmpInst::ICMP_SLE, X, Y, II, DL)) {
+        if (!*Known)
+          return replaceInstUsesWith(*II, IIOperand);
+
+        // nsw is not permitted if the abs allows INT_MIN.
+        if (IntMinIsPoison)
+          return BinaryOperator::CreateNSWSub(Y, X);
+        return BinaryOperator::CreateSub(Y, X);
+      }
+    }
+
     if (std::optional<bool> Sign = getKnownSign(IIOperand, II, DL, &AC, &DT)) {
-      // abs(x) -> x if x >= 0
+      // abs(x) -> x if x >= 0 (include abs(x-y) --> x-y where x >= y)
       if (!*Sign)
         return replaceInstUsesWith(*II, IIOperand);
 
       // abs(x) -> -x if x < 0
       if (IntMinIsPoison)
         return BinaryOperator::CreateNSWNeg(IIOperand);
       return BinaryOperator::CreateNeg(IIOperand);
     }
 
     // abs (sext X) --> zext (abs X*)
     // Clear the IsIntMin (nsw) bit on the abs to allow narrowing.
     if (match(IIOperand, m_OneUse(m_SExt(m_Value(X))))) {
       Value *NarrowAbs =
           Builder.CreateBinaryIntrinsic(Intrinsic::abs, X, Builder.getFalse());
       return CastInst::Create(Instruction::ZExt, NarrowAbs, II->getType());
     }
 
     // Match a complicated way to check if a number is odd/even:
     // abs (srem X, 2) --> and X, 1
     const APInt *C;
     if (match(IIOperand, m_SRem(m_Value(X), m_APInt(C))) && *C == 2)
       return BinaryOperator::CreateAnd(X, ConstantInt::get(II->getType(), 1));
 
     break;
   }
   case Intrinsic::umin: {

llvm/test/Transforms/InstCombine/abs-intrinsic.ll

 }
 
 define i32 @sub_abs_lt(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_abs_lt(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.true:
-; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub nsw i32 [[Y]], [[X]]
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[SUB_NEG]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   %cmp = icmp slt i32 %x, %y
   br i1 %cmp, label %cond.true, label %cond.end
 
 cond.true:
   %sub = sub nsw i32 %x, %y
   %0 = call i32 @llvm.abs.i32(i32 %sub, i1 true)
   br label %cond.end
 
 cond.end:
   %r = phi i32 [ %0, %cond.true ], [ 0, %entry ]
   ret i32 %r
 }
 
 ; https://alive2.llvm.org/ce/z/9wQo6G
 define i32 @sub_abs_sle(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_abs_sle(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
 ; CHECK:       cond.true:
-; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[TMP0:%.*]] = call i32 @llvm.abs.i32(i32 [[SUB]], i1 true)
+; CHECK-NEXT:    [[TMP0:%.*]] = sub nsw i32 [[Y]], [[X]]
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   %cmp = icmp sle i32 %x, %y
   br i1 %cmp, label %cond.true, label %cond.end
 
 cond.true:
   %sub = sub nsw i32 %x, %y
   %0 = call i32 @llvm.abs.i32(i32 %sub, i1 true)
   br label %cond.end
 
 cond.end:
   %r = phi i32 [ %0, %cond.true ], [ 0, %entry ]
   ret i32 %r
 }
 
+; https://alive2.llvm.org/ce/z/xlpSO0
+define i8 @src_sub_abs_sleF(i8 %x, i8 %y) {
+; CHECK-LABEL: @src_sub_abs_sleF(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 [[Y]], [[X]]
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[TMP0]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+entry:
+  %cmp = icmp sle i8 %x, %y
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %sub = sub nsw i8 %x, %y
+  %0 = call i8 @llvm.abs.i8(i8 %sub, i1 false)
+  br label %cond.end
+
+cond.end:
+  %r = phi i8 [ %0, %cond.true ], [ 0, %entry ]
+  ret i8 %r
+}
+
+define i8 @sub_abs_sleT(i8 %x, i8 %y) {
+; CHECK-LABEL: @sub_abs_sleT(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[COND_END:%.*]], label [[COND_TRUE:%.*]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    [[TMP0:%.*]] = sub nsw i8 [[Y]], [[X]]
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    [[R:%.*]] = phi i8 [ [[TMP0]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+entry:
+  %cmp = icmp sle i8 %x, %y
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %sub = sub nsw i8 %x, %y
+  %0 = call i8 @llvm.abs.i8(i8 %sub, i1 true)
+  br label %cond.end
+
+cond.end:
+  %r = phi i8 [ %0, %cond.true ], [ 0, %entry ]
+  ret i8 %r
+}
+
 define i32 @sub_abs_lt_min_not_poison(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_abs_lt_min_not_poison(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.true:
-; CHECK-NEXT:    [[SUB_NEG:%.*]] = sub i32 [[Y]], [[X]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[Y]], [[X]]
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[SUB_NEG]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   %cmp = icmp slt i32 %x, %y
   br i1 %cmp, label %cond.true, label %cond.end
 
 cond.true:
   %sub = sub nsw i32 %x, %y