[LLVM][PASSES][InstCombine] Fix (a + a + ...) / a cases

[AntonBikineev]

Summary

This quickly fixes 35709 . Please note that this is my first patch to the llvm passes infrastructure, so take it easy - I'm pretty sure I've done something dumb in this 3-liner :)

[lebedev.ri]

1. Please upload patches with full context (-U999999)
2. This needs testing coverage https://bugs.llvm.org/show_bug.cgi?id=35709#c1 notes that "(x+x+x)/x" is already handled, so maybe search for it and look how it is tested? And given that this is a generalization of that, perhaps that one is no longer needed?

[AntonBikineev]

Hey Roman,
Thanks for the comments.

1. Please upload patches with full context (-U999999)

Done.

2. This needs testing coverage https://bugs.llvm.org/show_bug.cgi?id=35709#c1 notes that "(x+x+x)/x" is already handled, so maybe search for it and look how it is tested? And given that this is a generalization of that, perhaps that one is no longer needed?

The "(x+x+x)/x" case is handled because "(x+x+x)" gets turned into "mul %x, 3" and then another simplification "(x * y) / x -> y" takes place. Things like "x+x" (with power-of-2 number of terms) in turn, get simplified into "shl %x, constant". So it's not a generalization, but a particular case.

[lebedev.ri]

In D42032#975917, @AntonBikineev wrote:

Hey Roman,
Thanks for the comments.

1. Please upload patches with full context (-U999999)

Done.

2. This needs testing coverage https://bugs.llvm.org/show_bug.cgi?id=35709#c1 notes that "(x+x+x)/x" is already handled, so maybe search for it and look how it is tested? And given that this is a generalization of that, perhaps that one is no longer needed?

The "(x+x+x)/x" case is handled because "(x+x+x)" gets turned into "mul %x, 3" and then another simplification "(x * y) / x -> y" takes place. Things like "x+x" (with power-of-2 number of terms) in turn, get simplified into "shl %x, constant". So it's not a generalization, but a particular case.

Ah, makes sense. https://godbolt.org/g/qyDUQv
Now, not that i know what i'm talking about, but Alive does not like those testcases as-is:
https://rise4fun.com/Alive/bvYn
But if we look at the IR in godbolt, we can note that it's "shl nsw i32", and then it likes it:
https://rise4fun.com/Alive/23e
So i wonder if that "no signed wrap" needs to be matched too.

[AntonBikineev]

Roman,

As the description shows, it's absolutely right. Thanks for pointing this out.

[lebedev.ri]

Thank you for working on this!
Looks sane to me, but someone who actually knows this should review.

test/Transforms/InstSimplify/reassociate.ll

166 ↗

(On Diff #129826)

Does this need negative tests, with missing nsw?

[majnemer]

lib/Analysis/InstructionSimplify.cpp

997–998 ↗

(On Diff #129826)

Instead of using m_Value(X) and X == Op1, just use m_Specific(Op1)

[AntonBikineev]

@lebedev.ri
My pleasure. Thanks for reviewing this!
@majnemer
Done.

[spatel]

test/Transforms/InstSimplify/reassociate.ll

161 ↗

(On Diff #130338)

The 'y' param is unused here and the other tests. Please remove.
Make one of the positive tests use a vector type, so we know case that works correctly too.

[spatel]

This patch raises a question that I don't know the answer to. We're missing the more general fold (shift amount is not constant) in instcombine:

Name: shl_div
%a = shl nsw i8 %x, %y
%r = sdiv i8 %a, %x
  =>
%r = shl i8 1, %y

https://rise4fun.com/Alive/7l

You can't do that here in instsimplify because we don't create new instructions here.

Is it better to just add that to instcombine and forego adding the special-case with constant shift amount to instsimplify?

[AntonBikineev]

Is it better to just add that to instcombine and forego adding the special-case with constant shift amount to instsimplify?

Yes, I think so. Thanks for indicating this.

[spatel]

This looks right, but see inline comments for some small improvements. Do you have commit access?

Note: we're missing the related 'rem' transforms for these patterns...but I think they would go back in instsimplify:
https://rise4fun.com/Alive/wqHz

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1019

No need to initialize this; we don't touch 'Y' if the matches fail.
Feel free to fix the similar line above here as a clean-up commit.

1020

Probably best not to speculatively create this constant. I think you can move this into the 'Create' lines below without violating the 80-column limit. :)

test/Transforms/InstCombine/div-shift.ll

117–119

I always suggest using the script at utils/update_test_checks.py to auto-generate the check lines. The regex that it would use here are more resilient to underlying cosmetic changes in instcombine (someone might want to give the values special names, and then this test would fail to match).

I also prefer to check all of the tests in first to show the current output of trunk. That way if your code commit is reverted for some reason, at least the tests will survive and show what was lost by the revert.

[AntonBikineev]

In D42032#981882, @spatel wrote:

This looks right, but see inline comments for some small improvements. Do you have commit access?

No, unfortunately.

No need to initialize this; we don't touch 'Y' if the matches fail.

In this particular case it's correct - we eliminate the extra store, but on the other hand IMHO it promotes a good code style by not accidentally reading uninitialized data.

Probably best not to speculatively create this constant. I think you can move this into the 'Create' lines below without violating the 80-column limit. :)

But then we would either need to duplicate this line in both statements or use an extra check... I don't know if it's better :)

[spatel]

In D42032#982440, @AntonBikineev wrote:

In D42032#981882, @spatel wrote:

This looks right, but see inline comments for some small improvements. Do you have commit access?

No, unfortunately.

No problem; I can commit on your behalf when the patch is complete. I can check in the tests first if you agree with my explanation on that.

No need to initialize this; we don't touch 'Y' if the matches fail.

In this particular case it's correct - we eliminate the extra store, but on the other hand IMHO it promotes a good code style by not accidentally reading uninitialized data.

I think the argument goes the other way - we want to see a compiler warning if we accidentally read the variable uninitialized, so we purposely leave it uninitialized to allow that possibility.

Probably best not to speculatively create this constant. I think you can move this into the 'Create' lines below without violating the 80-column limit. :)

But then we would either need to duplicate this line in both statements or use an extra check... I don't know if it's better :)

It's correct that you'll duplicate the line, but I think that's better than potentially executing code that won't be used.

[AntonBikineev]

In D42032#981882, @spatel wrote:

I also prefer to check all of the tests in first to show the current output of trunk. That way if your code commit is reverted for some reason, at least the tests will survive and show what was lost by the revert.

I've checked all the test on my machine. The only one that failed was CodeGen/Generic/dwarf-md5.ll:

error: expected string not found in input
; OBJ-5: Dir MD5 Checksum File Name

but it doesn't seem to relate to the change.

[lebedev.ri]

In D42032#982890, @AntonBikineev wrote:

In D42032#981882, @spatel wrote:

I also prefer to check all of the tests in first to show the current output of trunk. That way if your code commit is reverted for some reason, at least the tests will survive and show what was lost by the revert.

check all of the tests in

check<..>in == commit

[spatel]

In D42032#982900, @lebedev.ri wrote:

In D42032#982890, @AntonBikineev wrote:

In D42032#981882, @spatel wrote:

I also prefer to check all of the tests in first to show the current output of trunk. That way if your code commit is reverted for some reason, at least the tests will survive and show what was lost by the revert.

check all of the tests in

check<..>in == commit

Right - sorry, my writing was lousy there. Let me commit the tests now to demonstrate what I was hoping for. :)

[AntonBikineev]

In D42032#982921, @spatel wrote:

In D42032#982900, @lebedev.ri wrote:

In D42032#982890, @AntonBikineev wrote:

In D42032#981882, @spatel wrote:

I also prefer to check all of the tests in first to show the current output of trunk. That way if your code commit is reverted for some reason, at least the tests will survive and show what was lost by the revert.

check all of the tests in

check<..>in == commit

Right - sorry, my writing was lousy there. Let me commit the tests now to demonstrate what I was hoping for. :)

Sure, go ahead :)

[spatel]

Tests committed at:
https://reviews.llvm.org/rL323043

If you rebase the patch now, we'll just see the diffs / improvements from the new fold.

[spatel]

LGTM.

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

 }
 
 /// This function implements the transforms common to both integer division
 /// instructions (udiv and sdiv). It is called by the visitors to those integer
 /// division instructions.
 /// @brief Common integer divide transforms
 Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
+  bool IsSigned = I.getOpcode() == Instruction::SDiv;
 
   // The RHS is known non-zero.
   if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
     I.setOperand(1, V);
     return &I;
   }
 
   // Handle cases involving: [su]div X, (select Cond, Y, Z)
   // This does not apply for fdiv.
   if (simplifyDivRemOfSelectWithZeroOp(I))
     return &I;
 
   if (Instruction *LHS = dyn_cast<Instruction>(Op0)) {
     const APInt *C2;
     if (match(Op1, m_APInt(C2))) {
       Value *X;
       const APInt *C1;
-      bool IsSigned = I.getOpcode() == Instruction::SDiv;
 
       // (X / C1) / C2  -> X / (C1*C2)
       if ((IsSigned && match(LHS, m_SDiv(m_Value(X), m_APInt(C1)))) ||
           (!IsSigned && match(LHS, m_UDiv(m_Value(X), m_APInt(C1))))) {
         APInt Product(C1->getBitWidth(), /*Val=*/0ULL, IsSigned);
         if (!MultiplyOverflows(*C1, *C2, Product, IsSigned))
           return BinaryOperator::Create(I.getOpcode(), X,
                                         ConstantInt::get(I.getType(), Product));
if (match(Op0, m_One())) {
     }
   }
 
   // See if we can fold away this div instruction.
   if (SimplifyDemandedInstructionBits(I))
     return &I;
 
   // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
-  Value *X = nullptr, *Z = nullptr;
-  if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1
-    bool isSigned = I.getOpcode() == Instruction::SDiv;
-    if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
-        (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
+  Value *X, *Z;
+  if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) // (X - Z) / Y; Y = Op1
+    if ((IsSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
+        (!IsSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
       return BinaryOperator::Create(I.getOpcode(), X, Op1);
+
+  // (X << Y) / X -> 1 << Y
+  Value *Y;
+  if (IsSigned && match(Op0, m_NSWShl(m_Specific(Op1), m_Value(Y)))) {
+    Constant *C = ConstantInt::get(Op1->getType(), 1);
+    return BinaryOperator::CreateNSWShl(C, Y);
+  }
+  if (!IsSigned && match(Op0, m_NUWShl(m_Specific(Op1), m_Value(Y)))) {
+    Constant *C = ConstantInt::get(Op1->getType(), 1);
+    return BinaryOperator::CreateNUWShl(C, Y);
   }
 
   return nullptr;
 }
 
 static const unsigned MaxDepth = 6;
 
 namespace {
 
 using FoldUDivOperandCb = Instruction *(*)(Value *Op0, Value *Op1,
                                            const BinaryOperator &I,
                                            InstCombiner &IC);

test/Transforms/InstCombine/div-shift.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define i32 @t1(i16 zeroext %x, i32 %y) {
 ; CHECK-LABEL: @t1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CONV:%.*]] = zext i16 %x to i32
-; CHECK-NEXT:    [[TMP0:%.*]] = add i32 %y, 1
+; CHECK-NEXT:    [[CONV:%.*]] = zext i16 [[X:%.*]] to i32
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[Y:%.*]], 1
 ; CHECK-NEXT:    [[D:%.*]] = lshr i32 [[CONV]], [[TMP0]]
 ; CHECK-NEXT:    ret i32 [[D]]
 ;
 entry:
   %conv = zext i16 %x to i32
   %s = shl i32 2, %y
   %d = sdiv i32 %conv, %s
   ret i32 %d
entry:
   %s = shl <2 x i32> <i32 2, i32 2>, %y
   %d = sdiv <2 x i32> %conv, %s
   ret <2 x i32> %d
 }
 
 ; rdar://11721329
 define i64 @t2(i64 %x, i32 %y) {
 ; CHECK-LABEL: @t2(
-; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 %y to i64
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i64 %x, [[TMP1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[Y:%.*]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = lshr i64 [[X:%.*]], [[TMP1]]
 ; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
   %1 = shl i32 1, %y
   %2 = zext i32 %1 to i64
   %3 = udiv i64 %x, %2
   ret i64 %3
 }
 
 ; PR13250
 define i64 @t3(i64 %x, i32 %y) {
 ; CHECK-LABEL: @t3(
-; CHECK-NEXT:    [[TMP1:%.*]] = add i32 %y, 2
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[Y:%.*]], 2
 ; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[TMP1]] to i64
-; CHECK-NEXT:    [[TMP3:%.*]] = lshr i64 %x, [[TMP2]]
+; CHECK-NEXT:    [[TMP3:%.*]] = lshr i64 [[X:%.*]], [[TMP2]]
 ; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
   %1 = shl i32 4, %y
   %2 = zext i32 %1 to i64
   %3 = udiv i64 %x, %2
   ret i64 %3
 }
 
 define i32 @t4(i32 %x, i32 %y) {
 ; CHECK-LABEL: @t4(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 %y, 5
-; CHECK-NEXT:    [[DOTV:%.*]] = select i1 [[TMP1]], i32 %y, i32 5
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 %x, [[DOTV]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[Y:%.*]], 5
+; CHECK-NEXT:    [[DOTV:%.*]] = select i1 [[TMP1]], i32 [[Y]], i32 5
+; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[X:%.*]], [[DOTV]]
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %1 = shl i32 1, %y
   %2 = icmp ult i32 %1, 32
   %3 = select i1 %2, i32 32, i32 %1
   %4 = udiv i32 %x, %3
   ret i32 %4
 }
 
 define i32 @t5(i1 %x, i1 %y, i32 %V) {
 ; CHECK-LABEL: @t5(
-; CHECK-NEXT:    [[DOTV:%.*]] = select i1 %x, i32 5, i32 6
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 %V, [[DOTV]]
-; CHECK-NEXT:    [[TMP2:%.*]] = select i1 %y, i32 [[TMP1]], i32 0
+; CHECK-NEXT:    [[DOTV:%.*]] = select i1 [[X:%.*]], i32 5, i32 6
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[V:%.*]], [[DOTV]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[Y:%.*]], i32 [[TMP1]], i32 0
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %1 = shl i32 1, %V
   %2 = select i1 %x, i32 32, i32 64
   %3 = select i1 %y, i32 %2, i32 %1
   %4 = udiv i32 %V, %3
   ret i32 %4
 }
 
 define i32 @t6(i32 %x, i32 %z) {
 ; CHECK-LABEL: @t6(
-; CHECK-NEXT:    [[X_IS_ZERO:%.*]] = icmp eq i32 %x, 0
-; CHECK-NEXT:    [[DIVISOR:%.*]] = select i1 [[X_IS_ZERO]], i32 1, i32 %x
-; CHECK-NEXT:    [[Y:%.*]] = udiv i32 %z, [[DIVISOR]]
+; CHECK-NEXT:    [[X_IS_ZERO:%.*]] = icmp eq i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[DIVISOR:%.*]] = select i1 [[X_IS_ZERO]], i32 1, i32 [[X]]
+; CHECK-NEXT:    [[Y:%.*]] = udiv i32 [[Z:%.*]], [[DIVISOR]]
 ; CHECK-NEXT:    ret i32 [[Y]]
 ;
   %x_is_zero = icmp eq i32 %x, 0
   %divisor = select i1 %x_is_zero, i32 1, i32 %x
   %y = udiv i32 %z, %divisor
   ret i32 %y
 }
+
+; (X << C1) / X -> 1 << C1 optimizations
+
+define i32 @t7(i32 %x) {
+; CHECK-LABEL: @t7(
+; CHECK-NEXT:    ret i32 4
+;
+  %shl = shl nsw i32 %x, 2
+  %r = sdiv i32 %shl, %x
+  ret i32 %r
+}
+
+; make sure the previous opt doesn't take place for wrapped shifts
+
+define i32 @t8(i32 %x) {
+; CHECK-LABEL: @t8(
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], 2
+; CHECK-NEXT:    [[R:%.*]] = sdiv i32 [[SHL]], [[X]]
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %shl = shl i32 %x, 2
+  %r = sdiv i32 %shl, %x
+  ret i32 %r
+}
+
+define <2 x i32> @t9(<2 x i32> %x) {
+; CHECK-LABEL: @t9(
+; CHECK-NEXT:    ret <2 x i32> <i32 4, i32 8>
+;
+  %shl = shl nsw <2 x i32> %x, <i32 2, i32 3>
+  %r = sdiv <2 x i32> %shl, %x
+  ret <2 x i32> %r
+}
+
+define i32 @t10(i32 %x, i32 %y) {
+; CHECK-LABEL: @t10(
+; CHECK-NEXT:    [[R:%.*]] = shl nsw i32 1, [[Y:%.*]]
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %shl = shl nsw i32 %x, %y
+  %r = sdiv i32 %shl, %x
+  ret i32 %r
+}
+
+define <2 x i32> @t11(<2 x i32> %x, <2 x i32> %y) {
+; CHECK-LABEL: @t11(
+; CHECK-NEXT:    [[R:%.*]] = shl nsw <2 x i32> <i32 1, i32 1>, [[Y:%.*]]
+; CHECK-NEXT:    ret <2 x i32> [[R]]
+;
+  %shl = shl nsw <2 x i32> %x, %y
+  %r = sdiv <2 x i32> %shl, %x
+  ret <2 x i32> %r
+}
+
+define i32 @t12(i32 %x) {
+; CHECK-LABEL: @t12(
+; CHECK-NEXT:    ret i32 4
+;
+  %shl = shl nuw i32 %x, 2
+  %r = udiv i32 %shl, %x
+  ret i32 %r
+}
+
+; make sure the previous opt doesn't take place for wrapped shifts
+
+define i32 @t13(i32 %x) {
+; CHECK-LABEL: @t13(
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], 2
+; CHECK-NEXT:    [[R:%.*]] = udiv i32 [[SHL]], [[X]]
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %shl = shl i32 %x, 2
+  %r = udiv i32 %shl, %x
+  ret i32 %r
+}
+
+define <2 x i32> @t14(<2 x i32> %x) {
+; CHECK-LABEL: @t14(
+; CHECK-NEXT:    ret <2 x i32> <i32 4, i32 8>
+;
+  %shl = shl nuw <2 x i32> %x, <i32 2, i32 3>
+  %r = udiv <2 x i32> %shl, %x
+  ret <2 x i32> %r
+}
+
+define i32 @t15(i32 %x, i32 %y) {
+; CHECK-LABEL: @t15(
+; CHECK-NEXT:    [[R:%.*]] = shl nuw i32 1, [[Y:%.*]]
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %shl = shl nuw i32 %x, %y
+  %r = udiv i32 %shl, %x
+  ret i32 %r
+}
+
+define <2 x i32> @t16(<2 x i32> %x, <2 x i32> %y) {
+; CHECK-LABEL: @t16(
+; CHECK-NEXT:    [[R:%.*]] = shl nuw <2 x i32> <i32 1, i32 1>, [[Y:%.*]]
+; CHECK-NEXT:    ret <2 x i32> [[R]]
+;
+  %shl = shl nuw <2 x i32> %x, %y
+  %r = udiv <2 x i32> %shl, %x
+  ret <2 x i32> %r
+}