[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

1540

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

1537

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

1537

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, *Y;
   if (match(Op, m_NSWSub(m_Value(X), m_Value(Y))))
     return isImpliedByDomCondition(ICmpInst::ICMP_SLT, X, Y, CxtI, DL);
 
   return isImpliedByDomCondition(
       ICmpInst::ICMP_SLT, Op, Constant::getNullValue(Op->getType()), CxtI, DL);
 }
 
+static std::optional<bool> getKnownSignOrZero(Value *Op, Instruction *CxtI,
+                                              const DataLayout &DL,
+                                              AssumptionCache *AC,
+                                              DominatorTree *DT) {
+  if (std::optional<bool> Sign = getKnownSign(Op, CxtI, DL, AC, DT))
+    return Sign;
+
+  Value *X, *Y;
+  if (match(Op, m_NSWSub(m_Value(X), m_Value(Y))))
+    return isImpliedByDomCondition(ICmpInst::ICMP_SLE, X, Y, CxtI, DL);
+}
+
 /// Return true if two values \p Op0 and \p Op1 are known to have the same sign.
 static bool signBitMustBeTheSame(Value *Op0, Value *Op1, Instruction *CxtI,
                                  const DataLayout &DL, AssumptionCache *AC,
                                  DominatorTree *DT) {
   std::optional<bool> Known1 = getKnownSign(Op1, CxtI, DL, AC, DT);
   if (!Known1)
     return false;
   std::optional<bool> Known0 = getKnownSign(Op0, CxtI, DL, AC, DT);

       for (Instruction *Inserted : InsertedInstructions)
         Worklist.add(Inserted);
       return replaceInstUsesWith(CI, V);
     }
     return nullptr;
   }
   case Intrinsic::abs: {
     Value *IIOperand = II->getArgOperand(0);
     bool IntMinIsPoison = cast<Constant>(II->getArgOperand(1))->isOneValue();
 
     // abs(-x) -> abs(x)
     // TODO: Copy nsw if it was present on the neg?
     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);
 
-    if (std::optional<bool> Sign = getKnownSign(IIOperand, II, DL, &AC, &DT)) {
-      // abs(x) -> x if x >= 0
-      if (!*Sign)
+    if (std::optional<bool> Known =
+            getKnownSignOrZero(IIOperand, II, DL, &AC, &DT)) {
+      // abs(x) -> x if x >= 0 (include abs(x-y) --> x - y where x >= y)
+      // abs(x) -> x if x > 0 (include abs(x-y) --> x - y where x > y)
+      if (!*Known)
         return replaceInstUsesWith(*II, IIOperand);
 
       // abs(x) -> -x if x < 0
+      // abs(x) -> -x if x < = 0 (include abs(x-y) --> y - x where x <= y)
       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))))) {

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

 
 ; 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:    [[SUB_NEG:%.*]] = sub i32 [[Y]], [[X]]
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[SUB_NEG]], [[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:    [[SUB:%.*]] = sub nsw i8 [[X]], [[Y]]
-; CHECK-NEXT:    [[TMP0:%.*]] = call i8 @llvm.abs.i8(i8 [[SUB]], i1 false)
+; CHECK-NEXT:    [[SUB_NEG:%.*]] = 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:    [[R:%.*]] = phi i8 [ [[SUB_NEG]], [[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:    [[SUB:%.*]] = sub nsw i8 [[X]], [[Y]]
-; CHECK-NEXT:    [[TMP0:%.*]] = call i8 @llvm.abs.i8(i8 [[SUB]], i1 true)
+; CHECK-NEXT:    [[SUB_NEG:%.*]] = 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:    [[R:%.*]] = phi i8 [ [[SUB_NEG]], [[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
 }