[InstCombine] Canonicalize (-X s/ Y) to -(X s/ Y)

[shchenz]

Summary

int foo(int i, int j)
{
  int res = -( i / j);
  int res2 = -i / j;
  return res + res2;
}

Currently, we get:

define dso_local i32 @foo(i32, i32) local_unnamed_addr #0 {
  %3 = sdiv i32 %0, %1
  %4 = sub nsw i32 0, %0
  %5 = sdiv i32 %4, %1
  %6 = sub i32 %5, %3
  ret i32 %6
}

With this fold we will get

define dso_local i32 @foo(i32, i32) local_unnamed_addr #0 {
  %3 = sdiv i32 %0, %1
  %4 = sdiv i32 %0, %1
  %5 = sub nsw i32 0, %4
  %6 = sub i32 %5, %3
  ret i32 %6
}

Which will then get folded into

define dso_local i32 @foo(i32, i32) local_unnamed_addr #0 {
  %3 = sdiv i32 %0, %1
  %factor = mul i32 %3, -2
  ret i32 %factor
}

So we end with just one division:
https://godbolt.org/z/gSCKQ1

[shchenz]

move exact flag fixup code to a seperated patch https://reviews.llvm.org/D60396

[lebedev.ri]

Looks promising.

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1050–1051

It's not commutative like that.

----------------------------------------
Optimization: -X / Y  to  -(X / Y)
Precondition: true
  %t0 = sub nsw i8 0, %x
  %r = sdiv i8 %t0, %y
=>
  %n0 = sdiv i8 %x, %y
  %r = sub i8 0, %n0

Done: 1
Optimization is correct!

----------------------------------------
Optimization: X / -Y --> -(X / Y)
Precondition: true
  %t0 = sub nsw i8 0, %y
  %r = sdiv i8 %x, %t0
=>
  %n0 = sdiv i8 %x, %y
  %r = sub i8 0, %n0


ERROR: Domain of definedness of Target is smaller than Source's for i8 %r

Example:
%y i8 = 0xFF (255, -1)
%x i8 = 0x80 (128, -128)
%t0 i8 = 0x01 (1)
%n0 i8 = 0x80 (128, -128)
Source value: 0x80 (128, -128)
Target value: undef

(You could use https://rise4fun.com/Alive, but it appears down for the moment?)

[shchenz]

Will fix it later. Thanks for your comments @lebedev.ri

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1050–1051

hmm, seems can not canonicalize X/-Y ---> -(X/Y).
I will only focus on -X / Y to -(X / Y) for this patch.

There should be same opportunity for (X/-Y) if Y is constant. Will let it to be improved in later patch.

[shchenz]

address comments.

Now only canonicalize pattern -X/Y ---> -(X/Y).

[lebedev.ri]

Almost there.
Since we never touch the denominator, i think we are always good re vectors.
Does this need rebasing now that the other patch has landed?

llvm/test/Transforms/InstCombine/sdiv-canonicalize.ll

7

Shouldn't this sub also be nsw?

----------------------------------------
Optimization: nsw preserved
Precondition: true
  %o0 = sub nsw i8 0, %x
  %r = sdiv i8 %o0, %y
=>
  %n0 = sdiv i8 %x, %y
  %r = sub nsw i8 0, %n0

Done: 1
Optimization is correct!

----------------------------------------
Optimization: exact preserved
Precondition: true
  %o0 = sub nsw i8 0, %x
  %r = sdiv exact i8 %o0, %y
=>
  %n0 = sdiv exact i8 %x, %y
  %r = sub i8 0, %n0

Done: 1
Optimization is correct!

----------------------------------------
Optimization: both preserved
Precondition: true
  %o0 = sub nsw i8 0, %x
  %r = sdiv exact i8 %o0, %y
=>
  %n0 = sdiv exact i8 %x, %y
  %r = sub nsw i8 0, %n0

Done: 1
Optimization is correct!

11

There is a test that will show that we propagate exact?

[lebedev.ri]

Given that this doesn't fall into endless loop, i guess we don't do reverse transform.
I'm just wondering, this is the direction we should be doing it? @spatel

[spatel]

In D60395#1458421, @lebedev.ri wrote:

Given that this doesn't fall into endless loop, i guess we don't do reverse transform.
I'm just wondering, this is the direction we should be doing it? @spatel

We already have these for mul:

// -X * Y --> -(X * Y)
// X * -Y --> -(X * Y)

...so that provides some precedent for the direction to move the negation.

Is there a sibling fold for srem?

[lebedev.ri]

In D60395#1458889, @spatel wrote:

In D60395#1458421, @lebedev.ri wrote:

Given that this doesn't fall into endless loop, i guess we don't do reverse transform.
I'm just wondering, this is the direction we should be doing it? @spatel

We already have these for mul:

// -X * Y --> -(X * Y)
// X * -Y --> -(X * Y)

...so that provides some precedent for the direction to move the negation.

Okay, that confirmed my suspicions.

Is there a sibling fold for srem?

Yep!

----------------------------------------
Optimization: nsw preserved
Precondition: true
  %o0 = sub nsw i8 0, %x
  %r = srem i8 %o0, %y
=>
  %n0 = srem i8 %x, %y
  %r = sub nsw i8 0, %n0

Done: 1
Optimization is correct!

[shchenz]

llvm/test/Transforms/InstCombine/sdiv-canonicalize.ll

7

I have one question here before I set sub with nsw.

  %o0 = sub nsw i8 0, %x
  %r = sdiv i8 %o0, %y
=>
  %n0 = sdiv i8 %x, %y
  %r = sub i8 0, %n0

Is this a valid transformation? I know we get a affirmative answer in https://rise4fun.com/Alive/9G4. But assume this input %x is -128, %y is -2, for the source %o0 is a position value so %r is a position value too. But for the target %n0 is 64, and %r is -64? So source %r and target %r is not equal? Can you please help to point out what's wrong here? Thanks @lebedev.ri @spatel

11

will add one.

[lebedev.ri]

llvm/test/Transforms/InstCombine/sdiv-canonicalize.ll

7

-128 is SINT_MIN for i8, therefore the sub nsw 0, -128 is UB since it overflows despite the nsw flag.
https://godbolt.org/z/sWekHw
Therefore any and every answer is correct.

[shchenz]

address comments.

[lebedev.ri]

In D60395#1459712, @shchenz wrote:

address comments.

Ok, thank you, looks good now.

In D60395#1458897, @lebedev.ri wrote:

----------------------------------------
Optimization: nsw preserved
Precondition: true
  %o0 = sub nsw i8 0, %x
  %r = srem i8 %o0, %y
=>
  %n0 = srem i8 %x, %y
  %r = sub nsw i8 0, %n0

Done: 1
Optimization is correct!

@shchenz if you don't intend to immediately-ish submit a patch for that sibling pattern, could you please file a bug?

[shchenz]

In D60395#1459781, @lebedev.ri wrote:

In D60395#1459712, @shchenz wrote:

address comments.

Ok, thank you, looks good now.

In D60395#1458897, @lebedev.ri wrote:

----------------------------------------
Optimization: nsw preserved
Precondition: true
  %o0 = sub nsw i8 0, %x
  %r = srem i8 %o0, %y
=>
  %n0 = srem i8 %x, %y
  %r = sub nsw i8 0, %n0

Done: 1
Optimization is correct!

@shchenz if you don't intend to immediately-ish submit a patch for that sibling pattern, could you please file a bug?

Sure, https://bugs.llvm.org/show_bug.cgi?id=41443 is filed.

[lebedev.ri]

In D60395#1460010, @shchenz wrote:

In D60395#1459781, @lebedev.ri wrote:

In D60395#1459712, @shchenz wrote:

address comments.

Ok, thank you, looks good now.

In D60395#1458897, @lebedev.ri wrote:

----------------------------------------
Optimization: nsw preserved
Precondition: true
  %o0 = sub nsw i8 0, %x
  %r = srem i8 %o0, %y
=>
  %n0 = srem i8 %x, %y
  %r = sub nsw i8 0, %n0

Done: 1
Optimization is correct!

@shchenz if you don't intend to immediately-ish submit a patch for that sibling pattern, could you please file a bug?

Sure, https://bugs.llvm.org/show_bug.cgi?id=41443 is filed.

Thank you.

[lebedev.ri]

@shchenz how did rL358017 end up committing this diff into completely different place in this function?

[shchenz]

In D60395#1460248, @lebedev.ri wrote:

@shchenz how did rL358017 end up committing this diff into completely different place in this function?

Sorry, my bad. My remote dev machine is very slow yesterday night so I did not do a make check-all test before I committed the code. And I didn't reliaze that git merges my code into a wrong place in file lib/Transforms/InstCombine/InstCombineMulDivRem.cpp which was also changed by other patch yesterday.

I will send out another patch later.

[shchenz]

rebased.

Sorry for breaking down unit testing. Could you please help to do another review for this patch. Thanks a lot.

[lebedev.ri]

LG, please do run at least the check-llvm before committing..

[shchenz]

In D60395#1460782, @lebedev.ri wrote:

LG, please do run at least the check-llvm before committing..

absolutely will. ^-^

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) &&
           ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType());
       Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor);
       return new SExtInst(NarrowOp, Op0->getType());
     }
 
     // -X / C --> X / -C (if the negation doesn't overflow).
     // TODO: This could be enhanced to handle arbitrary vector constants by
     //       checking if all elements are not the min-signed-val.
     if (!Op1C->isMinSignedValue() &&
         match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) {
       Constant *NegC = ConstantInt::get(I.getType(), -(*Op1C));
       Instruction *BO = BinaryOperator::CreateSDiv(X, NegC);
       BO->setIsExact(I.isExact());
       return BO;
     }
   }
 
+  // -X / Y --> -(X / Y)
+  Value *Y;
+  if (match(&I, m_SDiv(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
+    return BinaryOperator::CreateNSWNeg(
+        Builder.CreateSDiv(X, Y, I.getName(), I.isExact()));
+
   // If the sign bits of both operands are zero (i.e. we can prove they are
   // unsigned inputs), turn this into a udiv.
   APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits()));
   if (MaskedValueIsZero(Op0, Mask, 0, &I)) {
     if (MaskedValueIsZero(Op1, Mask, 0, &I)) {
       // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
       auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
       BO->setIsExact(I.isExact());

llvm/test/Transforms/InstCombine/div.ll

 ;
   %neg = sub nsw <2 x i8> zeroinitializer, %x
   %d = sdiv <2 x i8> %neg, <i8 -128, i8 undef>
   ret <2 x i8> %d
 }
 
 define <2 x i64> @sdiv_negated_dividend_constant_divisor_vec(<2 x i64> %x) {
 ; CHECK-LABEL: @sdiv_negated_dividend_constant_divisor_vec(
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw <2 x i64> zeroinitializer, [[X:%.*]]
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv <2 x i64> [[NEG]], <i64 3, i64 4>
+; CHECK-NEXT:    [[DIV1:%.*]] = sdiv <2 x i64> [[X:%.*]], <i64 3, i64 4>
+; CHECK-NEXT:    [[DIV:%.*]] = sub nsw <2 x i64> zeroinitializer, [[DIV1]]
 ; CHECK-NEXT:    ret <2 x i64> [[DIV]]
 ;
   %neg = sub nsw <2 x i64> zeroinitializer, %x
   %div = sdiv <2 x i64> %neg, <i64 3, i64 4>
   ret <2 x i64> %div
 }
 
 define <2 x i64> @sdiv_exact_negated_dividend_constant_divisor_vec(<2 x i64> %x) {
 ; CHECK-LABEL: @sdiv_exact_negated_dividend_constant_divisor_vec(
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw <2 x i64> zeroinitializer, [[X:%.*]]
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv exact <2 x i64> [[NEG]], <i64 3, i64 4>
+; CHECK-NEXT:    [[DIV1:%.*]] = sdiv exact <2 x i64> [[X:%.*]], <i64 3, i64 4>
+; CHECK-NEXT:    [[DIV:%.*]] = sub nsw <2 x i64> zeroinitializer, [[DIV1]]
 ; CHECK-NEXT:    ret <2 x i64> [[DIV]]
 ;
   %neg = sub nsw <2 x i64> zeroinitializer, %x
   %div = sdiv exact <2 x i64> %neg, <i64 3, i64 4>
   ret <2 x i64> %div
 }
 
 ; Can't negate signed min vector element.
 
 define <2 x i8> @sdiv_exact_negated_dividend_constant_divisor_vec_overflow(<2 x i8> %x) {
 ; CHECK-LABEL: @sdiv_exact_negated_dividend_constant_divisor_vec_overflow(
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw <2 x i8> zeroinitializer, [[X:%.*]]
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv exact <2 x i8> [[NEG]], <i8 -128, i8 42>
+; CHECK-NEXT:    [[DIV1:%.*]] = sdiv exact <2 x i8> [[X:%.*]], <i8 -128, i8 42>
+; CHECK-NEXT:    [[DIV:%.*]] = sub nsw <2 x i8> zeroinitializer, [[DIV1]]
 ; CHECK-NEXT:    ret <2 x i8> [[DIV]]
 ;
   %neg = sub nsw <2 x i8> zeroinitializer, %x
   %div = sdiv exact <2 x i8> %neg, <i8 -128, i8 42>
   ret <2 x i8> %div
 }
 
 define i32 @test35(i32 %A) {

llvm/test/Transforms/InstCombine/sdiv-canonicalize.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define i32 @test_sdiv_canonicalize_op0(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test_sdiv_canonicalize_op0(
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw i32 0, [[X:%.*]]
-; CHECK-NEXT:    [[SDIV:%.*]] = sdiv i32 [[NEG]], [[Y:%.*]]
+; CHECK-NEXT:    [[SDIV1:%.*]] = sdiv i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[SDIV:%.*]] = sub nsw i32 0, [[SDIV1]]
 ; CHECK-NEXT:    ret i32 [[SDIV]]
 ;
   %neg = sub nsw i32 0, %x
   %sdiv = sdiv i32 %neg, %y
   ret i32 %sdiv
 }
 
 define i32 @test_sdiv_canonicalize_op0_exact(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test_sdiv_canonicalize_op0_exact(
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw i32 0, [[X:%.*]]
-; CHECK-NEXT:    [[SDIV:%.*]] = sdiv exact i32 [[NEG]], [[Y:%.*]]
+; CHECK-NEXT:    [[SDIV1:%.*]] = sdiv exact i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[SDIV:%.*]] = sub nsw i32 0, [[SDIV1]]
 ; CHECK-NEXT:    ret i32 [[SDIV]]
 ;
   %neg = sub nsw i32 0, %x
   %sdiv = sdiv exact i32 %neg, %y
   ret i32 %sdiv
 }
 
+; (X/-Y) is not equal to -(X/Y), don't canonicalize.
 define i32 @test_sdiv_canonicalize_op1(i32 %x, i32 %z) {
 ; CHECK-LABEL: @test_sdiv_canonicalize_op1(
 ; CHECK-NEXT:    [[Y:%.*]] = mul i32 [[Z:%.*]], 3
 ; CHECK-NEXT:    [[NEG:%.*]] = sub nsw i32 0, [[X:%.*]]
 ; CHECK-NEXT:    [[SDIV:%.*]] = sdiv i32 [[Y]], [[NEG]]
 ; CHECK-NEXT:    ret i32 [[SDIV]]
 ;
   %y = mul i32 %z, 3

 ;
   %neg = sub i32 0, %x
   %sdiv = sdiv i32 %neg, %y
   ret i32 %sdiv
 }
 
 define <2 x i32> @test_sdiv_canonicalize_vec(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @test_sdiv_canonicalize_vec(
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw <2 x i32> zeroinitializer, [[X:%.*]]
-; CHECK-NEXT:    [[SDIV:%.*]] = sdiv <2 x i32> [[NEG]], [[Y:%.*]]
+; CHECK-NEXT:    [[SDIV1:%.*]] = sdiv <2 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[SDIV:%.*]] = sub nsw <2 x i32> zeroinitializer, [[SDIV1]]
 ; CHECK-NEXT:    ret <2 x i32> [[SDIV]]
 ;
   %neg = sub nsw <2 x i32> <i32 0, i32 0>, %x
   %sdiv = sdiv <2 x i32> %neg, %y
   ret <2 x i32> %sdiv
 }
 
 define i32 @test_sdiv_canonicalize_multiple_uses(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test_sdiv_canonicalize_multiple_uses(
 ; CHECK-NEXT:    [[NEG:%.*]] = sub nsw i32 0, [[X:%.*]]
 ; CHECK-NEXT:    [[SDIV:%.*]] = sdiv i32 [[NEG]], [[Y:%.*]]
 ; CHECK-NEXT:    [[SDIV2:%.*]] = sdiv i32 [[SDIV]], [[NEG]]
 ; CHECK-NEXT:    ret i32 [[SDIV2]]
 ;
   %neg = sub nsw i32 0, %x
   %sdiv = sdiv i32 %neg, %y
   %sdiv2 = sdiv i32 %sdiv, %neg
   ret i32 %sdiv2
 }
 
-; There is combination: (X/-CE) -> -(X/CE)
-; There is another combination: -(X/CE) -> (X/-CE)
-; Make sure don't combine them endless.
+; There is combination: -(X/CE) -> (X/-CE).
+; If combines (X/-CE) to -(X/CE), make sure don't combine them endless.
 
 @X = global i32 5
 
 define i64 @test_sdiv_canonicalize_constexpr(i64 %L1) {
 ; currently opt folds (sub nsw i64 0, constexpr) -> (sub i64, 0, constexpr).
 ; sdiv canonicalize requires a nsw sub.
 ; CHECK-LABEL: @test_sdiv_canonicalize_constexpr(
 ; CHECK-NEXT:    [[B4:%.*]] = sdiv i64 [[L1:%.*]], sub (i64 0, i64 ptrtoint (i32* @X to i64))
 ; CHECK-NEXT:    ret i64 [[B4]]
 ;
   %v1 = ptrtoint i32* @X to i64
   %B8 = sub nsw i64 0, %v1
   %B4 = sdiv i64 %L1, %B8
   ret i64 %B4
 }