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

[bcl5980]

Summary

When abs source comes from (x - y) , we need to check if exist x > y dominating the instruction or not.

Fix https://github.com/llvm/llvm-project/issues/54132

[bcl5980]

update test

[RKSimon]

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

430

where are the actual codegen checks?

[bcl5980]

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

430

; CHECK-NOT: llvm.abs.i32
If the code works, llvm.abs.i32 will be removed.

[craig.topper]

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

430

Checks in InstCombine tests are usually autogenerated with utils/update_test_checks.py as the top of this file says. Please use that.

[bcl5980]

update test

[bcl5980]

update test

[bcl5980]

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

430

I'm sorry for the terrible test case. I'm an beginner on llvm so can someone tell me how the update_test_checks.py works and what should I do next? Or is there any document or sample to show how it works?

[craig.topper]

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

445

I think the nsw flag is required to make this transform valid, but code doesn't check for it.

[bcl5980]

add nsw check

[peterwaller-arm]

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

430

With my build directory at llvm-project/build, I run something like this. You can name the tests you want to autogenerate as parameters.

./llvm/utils/update_test_checks.py --opt-binary=build/bin/opt llvm/test/Transforms/InstCombine/abs-intrinsic.ll

[bcl5980]

use update_test_checks.py to autogen test check golden

[bcl5980]

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

430

Thanks for the sample

[peterwaller-arm]

Seems reasonable to me.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

794–796

This code would be shorter using 'match':

Value *X, *Y;
if (match(Op, m_NSWSub(m_Value(X), m_Value(Y))))
  return isImpliedByDomCondition(ICmpInst::ICMP_SLT, X, Y, CxtI, DL);

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

429

We should have at least 3 more tests:

1. Check when the dominating condition is 'false' - change the icmp predicate to 'slt'?
2. A negative test (no transform should be made) for wrong predicate - change the icmp predicate to 'ugt' or some other value to make the transform invalid.
3. A negative test (no transform should be made) when there is no 'nsw' on the sub.

[bcl5980]

update based on spatel's suggestion

1. use match pattern
2. add more tests

[spatel]

Do you have commit access? It would be good to push the original tests as a preliminary patch.

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

473

Why did the 'add' operand change from %y to %x?

[bcl5980]

In D122013#3396650, @spatel wrote:

Do you have commit access? It would be good to push the original tests as a preliminary patch.

I have no commit access, can you help me to do this?
name: chenglin.bi
email: [e-mail]

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

473

when I change the condition code from sgt to slt, it become x < y
so abs(x - y) become y - x, I need to change the pattern to y - x + x then return only y
sub_abs_gt :
[ x>y ? abs (x-y) + y : 0 ] -> [ x > y ? x : 0 ]
sub_abs_lt :
[ x< y ? abs (x-y) + x : 0 ] -> [ x < y ? y : 0 ]

[spatel]

In D122013#3396675, @bcl5980 wrote:

In D122013#3396650, @spatel wrote:

Do you have commit access? It would be good to push the original tests as a preliminary patch.

I have no commit access, can you help me to do this?
name: chenglin.bi
email: [e-mail]

Sure - let's make one small change, and then I can commit for you.

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

473

I see. It's fine to include a test with the 'add' from the motivating bug report, but the 'add' is not part of the minimal transform. We should remove it completely from at least these first 2 tests, so we can check that only this transform is tested.

[bcl5980]

minimize tests

[spatel]

I committed the tests with baseline CHECK lines:
01a2ba5dfbee
...and one more test:
c4d74a93f65c

Please rebase and test with Alive2 that we have correct behavior when the 2nd parameter to abs is 'false'.

[bcl5980]

abs(x-y, false) case: https://alive2.llvm.org/ce/z/azMKoT

[spatel]

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

461

This should have propagated the 'nsw', right?
https://alive2.llvm.org/ce/z/5q5YHb

If this is an existing problem (but might be invisible before this patch), I think it is ok to mark this with a 'TODO' comment.

[bcl5980]

Fix [-(x - y) -> y -x ] missing nsw flag

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

241

This change should be an independent patch with its own minimal tests:
https://alive2.llvm.org/ce/z/Ppps-u

[bcl5980]

remove neg nsw flag fix. Will fix it on next commit

[spatel]

LGTM

[bcl5980]

@spatel, Thanks for the detail review.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

static Optional<bool> getKnownSign(Value *Op, Instruction *CxtI,
                                    const DataLayout &DL, AssumptionCache *AC,
                                    DominatorTree *DT) {
   KnownBits Known = computeKnownBits(Op, DL, 0, AC, CxtI, DT);
   if (Known.isNonNegative())
     return false;
   if (Known.isNegative())
     return true;
 
+  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);
 }
 
 /// Try to canonicalize min/max(X + C0, C1) as min/max(X, C1 - C0) + C0. This
 /// can trigger other combines.
 static Instruction *moveAddAfterMinMax(IntrinsicInst *II,
                                        InstCombiner::BuilderTy &Builder) {

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

default:
     break; // Other instructions require recursive reasoning.
   }
 
   if (I->getOpcode() == Instruction::Sub &&
       (I->hasOneUse() || match(I->getOperand(0), m_ImmConstant()))) {
     // `sub` is always negatible.
     // However, only do this either if the old `sub` doesn't stick around, or
     // it was subtracting from a constant. Otherwise, this isn't profitable.
+    if (I->hasNoSignedWrap())
+      return Builder.CreateNSWSub(I->getOperand(1), I->getOperand(0),
+                                  I->getName() + ".neg");
     return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
                              I->getName() + ".neg");
   }
 
   // Some other cases, while still don't require recursion,
   // are restricted to the one-use case.
   if (!V->hasOneUse())
     return nullptr;

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

 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %s = srem i32 %x, 3
   %r = call i32 @llvm.abs.i32(i32 %s, i1 true)
   ret i32 %r
 }
 
 ; Test from https://github.com/llvm/llvm-project/issues/54132.
 define i32 @sub_abs_gt(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_abs_gt(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
 ; 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:    br label [[COND_END]]
 ; CHECK:       cond.end:
-; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[TMP0]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ [[SUB]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   %cmp = icmp sgt 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
 }
 
 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:    [[CMP:%.*]] = icmp sgt i32 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
 ; 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 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:    [[R:%.*]] = phi i32 [ [[SUB_NEG]], [[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
 }
 
 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:    [[CMP:%.*]] = icmp sgt i32 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.true:
-; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[TMP0:%.*]] = call i32 @llvm.abs.i32(i32 [[SUB]], i1 false)
+; CHECK-NEXT:    [[SUB_NEG:%.*]] = 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:    [[R:%.*]] = phi i32 [ [[SUB_NEG]], [[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