[InstCombine] "X - (X / C) * C == 0" to "X & C-1 == 0"

[EgorBo]

Summary

"X % C == 0" is optimized to "X & C-1 == 0" (where C is a power-of-two)
However, "X % Y" can also be represented as "X - (X / Y) * Y" so if I rewrite the initial expression:
"X - (X / C) * C == 0" it's not currently optimized to "X & C-1 == 0", see godbolt: https://godbolt.org/z/KzuXUj

This is my first contribution to LLVM so I hope I didn't mess things up

[EgorBo]

Fix test name

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1362–1363 ↗

(On Diff #261950)

I think we should first instead fold X - (X / C) * C/((X / -C1) >> C2)) + X into X % C.
We have integer division/remainder either way, but with remainder it's less instructions.

But that won't help here, because your target pattern @is_rem32_pos_decomposed_i8
is currently folded into

define i1 @is_rem32_pos_decomposed_i8(i8 %x) {
  %d.neg = sdiv i8 %x, -32
  %m.neg = shl i8 %d.neg, 5
  %s = sub i8 0, %x
  %r = icmp eq i8 %m.neg, %s
  ret i1 %r
}

instead of

define i1 @tgt(i8 %x) {
  %d.neg = sdiv i8 %x, -32
  %m.neg = shl i8 %d.neg, 5
  %m.neg.add = add i8 %m.neg, %x
  %r = icmp eq i8 %m.neg.add, 0
  ret i1 %r
}

For that, i'd think we should extend foldIRemByPowerOfTwoToBitTest().

1391 ↗

(On Diff #261950)

Don't use fixed-size integers, use APInt.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1362–1363 ↗

(On Diff #261950)

Edit: err, actually, disregard foldIRemByPowerOfTwoToBitTest() comment.
We should also fold

define i1 @is_rem32_pos_decomposed_i8(i8 %x) {
  %d.neg = sdiv i8 %x, -32
  %m.neg = shl i8 %d.neg, 5
  %s = sub i8 0, %x
  %r = icmp eq i8 %m.neg, %s
  ret i1 %r
}

into

define i1 @is_rem32_pos_decomposed_i8(i8 %x) {
  %s = srem i8 %x, 32
  %r = icmp eq i8 %s, 0
  ret i1 %r
}

and then foldIRemByPowerOfTwoToBitTest() will just work.

[EgorBo]

Moved to InstCombiner::visitAdd

[EgorBo]

@lebedev.ri Thanks for review!
I've moved the transformation to "InstCombiner::visitAdd"

So now it converts "((X / C1) << C2) + X" to "X % C1" thus "((X / C1) << C2) + X == 0" is automatically optimized to "X & C-1 == 0" later.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1309–1310

// ((X / C1) << C2) + X => X % -C1
// where -C1 = 1 << C2

1311–1312

Do we care about non-splat vector support?
This will only work for scalars/splat vectors.

1317

Just return the new srem.

llvm/test/Transforms/InstCombine/icmp-div-constant.ll

41

Please pull into a new file. Some comments:

• there should be no icmp here, this isn't the pattern we are folding (although yes, that is the larger pattern)
• there shouldn't be nsw flags since we don't use them
• there shouldn't be mul, we are looking for shl
• there shouldn't be sub, we are looking for add

And this needs more tests, in particular:

• splat vector test
• non-splat vector test
• vector splat with undef lane test: there's two constants here, so two tests where either one of them contains undef lane, and a test where both of them contain undef lane
• one test with extra uses (see @use in this file) on every of the values - we don't care whether there are extra uses
• Negative tests - what are preconditions on the constants?

[EgorBo]

Add more tests (TODO: add non-splat vectors)

[EgorBo]

Add more tests (TODO: non-splat vectors)

[EgorBo]

Add more tests (undef, negative, non-splat vectors)

[EgorBo]

@lebedev.ri can you please re-review? do you want me to add more tests?

Regarding the non-splat vectors, I am not super familiar with it yet, will it complicate my code significantly?

[lebedev.ri]

Please feel free to add weekly-ish "ping" comments, i lost track of this, sorry :/
This looks good for the time being modulo nits.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

1309–1310

Eeeh, i walked into that one myself, but let's explicitly spell out sigdness of ops:
((X s/ C1) << C2) + X => X s% -C1

1312

if (match(LHS, m_Shl(m_SDiv(m_Specific(RHS), m_APInt(C1)), m_APInt(C2)))) {

1313–1315

I'm not sure why all these preconditions are needed?
I think you only want -C1 == 1 << C2, i.e. -(*C1) == (one << *C2).
https://rise4fun.com/Alive/wslBO

1316

Why not just -(*C1)?
While there, we now do that twice, so cache it in some new variable.

[lebedev.ri]

Reverse-ping.

[EgorBo]

@lebedev.ri I am so sorry for this huge delay, totally forgot about this pr and broke my notifications, I promise I'll respond without delays in future :-) Addressed your feedback I beleive.

[lebedev.ri]

LGTM, thanks you.
If you need help committing this, do specify the "name <[e-mail]>" to be used.

[EgorBo]

In D79369#2085994, @lebedev.ri wrote:

LGTM, thanks you.
If you need help committing this, do specify the "name <[e-mail]>" to be used.

@lebedev.ri I'm not sure I understand what you mean, do I need to add a header on top of that diff? something like

From: EgorBo <[e-mail]>

---

?

[lebedev.ri]

In D79369#2086224, @EgorBo wrote:

In D79369#2085994, @lebedev.ri wrote:

LGTM, thanks you.
If you need help committing this, do specify the "name <[e-mail]>" to be used.

@lebedev.ri I'm not sure I understand what you mean, do I need to add a header on top of that diff? something like

From: EgorBo <[e-mail]>

---

?

https://llvm.org/docs/DeveloperPolicy.html#attribution-of-changes
https://llvm.org/docs/DeveloperPolicy.html#commit-messages

If you’re not the original author, ensure the ‘Author’ property of the commit is set to the original author and the ‘Committer’ property is set to yourself. You can use a command similar to git commit --amend --author="John Doe <[e-mail]> to correct the author property if it is incorrect. See Attribution of Changes for more information including the method we used for attribution before the project migrated to git.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
   // (A + ~B) + 1 --> A - B
   if (match(&I, m_c_BinOp(m_Add(m_Value(A), m_One()), m_Not(m_Value(B)))) ||
       match(&I, m_BinOp(m_c_Add(m_Not(m_Value(B)), m_Value(A)), m_One())))
     return BinaryOperator::CreateSub(A, B);
 
   // X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1)
   if (Value *V = SimplifyAddWithRemainder(I)) return replaceInstUsesWith(I, V);
 
-  // ((X / C1) << C2) + X => X % C1
-  // where C1 = 1 << C2
+  // ((X / C1) << C2) + X => X % -C1
+  // where -C1 = 1 << C2
   const APInt *C1, *C2;
   if (match(LHS, m_Shl(m_SDiv(m_Value(A), m_APInt(C1)), m_APInt(C2)))) {
     if ((RHS == A) && C1->abs().isPowerOf2() && C1->isNegative()) {
       APInt one(C2->getBitWidth(), 1);
       if ((C1->abs() == one.shl(*C2)) && C2->sgt(one)) {
         Constant *NewRHS = ConstantInt::get(RHS->getType(), C1->abs());
-        return replaceInstUsesWith(I, Builder.CreateSRem(RHS, NewRHS, "srem"));
+        return BinaryOperator::CreateSRem(RHS, NewRHS);
       }
     }
   }
 
   // A+B --> A|B iff A and B have no bits set in common.
   if (haveNoCommonBitsSet(LHS, RHS, DL, &AC, &I, &DT))
     return BinaryOperator::CreateOr(LHS, RHS);
 

llvm/test/Transforms/InstCombine/add-shl-sdiv-to-srem.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+define i8 @add-shl-sdiv-i8-2(i8 %x) {
+; CHECK-LABEL: @add-shl-sdiv-i8-2(
+; CHECK-NEXT:    [[RZ:%.*]] = srem i8 [[X:%.*]], 4
+; CHECK-NEXT:    ret i8 [[RZ]]
+;
+  %sd = sdiv i8 %x, -4
+  %sl = shl i8 %sd, 2
+  %rz = add i8 %sl, %x
+  ret i8 %rz
+}
+
+define i8 @add-shl-sdiv-i8-6(i8 %x) {
+; CHECK-LABEL: @add-shl-sdiv-i8-6(
+; CHECK-NEXT:    [[RZ:%.*]] = srem i8 [[X:%.*]], 64
+; CHECK-NEXT:    ret i8 [[RZ]]
+;
+  %sd = sdiv i8 %x, -64
+  %sl = shl i8 %sd, 6
+  %rz = add i8 %sl, %x
+  ret i8 %rz
+}
+
+define i32 @add-shl-sdiv-i32-30(i32 %x) {
+; CHECK-LABEL: @add-shl-sdiv-i32-30(
+; CHECK-NEXT:    [[RZ:%.*]] = srem i32 [[X:%.*]], 1073741824
+; CHECK-NEXT:    ret i32 [[RZ]]
+;
+  %sd = sdiv i32 %x, -1073741824
+  %sl = shl i32 %sd, 30
+  %rz = add i32 %sl, %x
+  ret i32 %rz
+}
+
+; Splat vectors
+
+define <3 x i8> @add-shl-sdiv-3xi8-2(<3 x i8> %x) {
+; CHECK-LABEL: @add-shl-sdiv-3xi8-2(
+; CHECK-NEXT:    [[RZ:%.*]] = srem <3 x i8> [[X:%.*]], <i8 4, i8 4, i8 4>
+; CHECK-NEXT:    ret <3 x i8> [[RZ]]
+;
+  %sd = sdiv <3 x i8> %x, <i8 -4, i8 -4, i8 -4>
+  %sl = shl <3 x i8> %sd, <i8 2, i8 2, i8 2>
+  %rz = add <3 x i8> %sl, %x
+  ret <3 x i8> %rz
+}
+
+define <2 x i64> @add-shl-sdiv-2xi64-5(<2 x i64> %x) {
+; CHECK-LABEL: @add-shl-sdiv-2xi64-5(
+; CHECK-NEXT:    [[RZ:%.*]] = srem <2 x i64> [[X:%.*]], <i64 32, i64 32>
+; CHECK-NEXT:    ret <2 x i64> [[RZ]]
+;
+  %sd = sdiv <2 x i64> %x, <i64 -32, i64 -32>
+  %sl = shl <2 x i64> %sd, <i64 5, i64 5>
+  %rz = add <2 x i64> %sl, %x
+  ret <2 x i64> %rz
+}
+
+; One-use tests
+
+declare void @use32(i32)
+define i32 @add-shl-sdiv-i32-4-use-1(i32 %x) {
+; CHECK-LABEL: @add-shl-sdiv-i32-4-use-1(
+; CHECK-NEXT:    call void @use32(i32 [[X:%.*]])
+; CHECK-NEXT:    [[RZ:%.*]] = srem i32 [[X]], 16
+; CHECK-NEXT:    ret i32 [[RZ]]
+;
+  call void @use32(i32 %x)
+  %sd = sdiv i32 %x, -16
+  %sl = shl i32 %sd, 4
+  %rz = add i32 %sl, %x
+  ret i32 %rz
+}
+
+define i32 @add-shl-sdiv-i32-4-use-2(i32 %x) {
+; CHECK-LABEL: @add-shl-sdiv-i32-4-use-2(
+; CHECK-NEXT:    [[SD:%.*]] = sdiv i32 [[X:%.*]], -16
+; CHECK-NEXT:    call void @use32(i32 [[SD]])
+; CHECK-NEXT:    [[RZ:%.*]] = srem i32 [[X]], 16
+; CHECK-NEXT:    ret i32 [[RZ]]
+;
+  %sd = sdiv i32 %x, -16
+  call void @use32(i32 %sd)
+  %sl = shl i32 %sd, 4
+  %rz = add i32 %sl, %x
+  ret i32 %rz
+}
+
+define i32 @add-shl-sdiv-i32-4-use-3(i32 %x) {
+; CHECK-LABEL: @add-shl-sdiv-i32-4-use-3(
+; CHECK-NEXT:    [[SD:%.*]] = sdiv i32 [[X:%.*]], -16
+; CHECK-NEXT:    [[SL:%.*]] = shl i32 [[SD]], 4
+; CHECK-NEXT:    call void @use32(i32 [[SL]])
+; CHECK-NEXT:    [[RZ:%.*]] = srem i32 [[X]], 16
+; CHECK-NEXT:    ret i32 [[RZ]]
+;
+  %sd = sdiv i32 %x, -16
+  %sl = shl i32 %sd, 4
+  call void @use32(i32 %sl)
+  %rz = add i32 %sl, %x
+  ret i32 %rz
+}
+
+; Negative
+
+define i8 @add-shl-sdiv-negative-1(i8 %x) {
+; CHECK-LABEL: @add-shl-sdiv-negative-1(
+; CHECK-NEXT:    [[SD:%.*]] = sdiv i8 [[X:%.*]], 4
+; CHECK-NEXT:    [[SL:%.*]] = shl nsw i8 [[SD]], 2
+; CHECK-NEXT:    [[RZ:%.*]] = add i8 [[SL]], [[X]]
+; CHECK-NEXT:    ret i8 [[RZ]]
+;
+  %sd = sdiv i8 %x, 4
+  %sl = shl i8 %sd, 2
+  %rz = add i8 %sl, %x
+  ret i8 %rz
+}
+
+define <3 x i8> @add-shl-sdiv-negative-2(<3 x i8> %x) {
+; CHECK-LABEL: @add-shl-sdiv-negative-2(
+; CHECK-NEXT:    [[SD:%.*]] = sdiv <3 x i8> [[X:%.*]], <i8 -5, i8 -5, i8 -5>
+; CHECK-NEXT:    [[SL:%.*]] = shl <3 x i8> [[SD]], <i8 2, i8 2, i8 2>
+; CHECK-NEXT:    [[RZ:%.*]] = add <3 x i8> [[SL]], [[X]]
+; CHECK-NEXT:    ret <3 x i8> [[RZ]]
+;
+  %sd = sdiv <3 x i8> %x, <i8 -5, i8 -5, i8 -5>
+  %sl = shl <3 x i8> %sd, <i8 2, i8 2, i8 2>
+  %rz = add <3 x i8> %sl, %x
+  ret <3 x i8> %rz
+}
+
+define <2 x i64> @add-shl-sdiv-negative-3(<2 x i64> %x) {
+; CHECK-LABEL: @add-shl-sdiv-negative-3(
+; CHECK-NEXT:    ret <2 x i64> undef
+;
+  %sd = sdiv <2 x i64> %x, <i64 32, i64 32>
+  %sl = shl <2 x i64> %sd, <i64 -5, i64 -5>
+  %rz = add <2 x i64> %sl, %x
+  ret <2 x i64> %rz
+}

llvm/test/Transforms/InstCombine/icmp-div-constant.ll

 ; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = srem i8 %x, 32
   %r = icmp sgt i8 %s, 0
   ret i1 %r
 }
 
-define i1 @is_rem32_pos_decomposed_i8(i8 %x) {
-; CHECK-LABEL: @is_rem32_pos_decomposed_i8(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], -97
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[TMP1]], 0
-; CHECK-NEXT:    ret i1 [[R]]
-;
-  %d = sdiv i8 %x, 32
-  %m = mul nsw i8 %d, 32
-  %s = sub nsw i8 %x, %m
-  %r = icmp eq i8 %s, 0
-  ret i1 %r
-}
-
 ; i16 -32765 == 32771 == 0b1000000000000011
 
 define i1 @is_rem4_neg_i16(i16 %x) {
 ; CHECK-LABEL: @is_rem4_neg_i16(
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i16 [[X:%.*]], -32765
 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i16 [[TMP1]], -32768
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %s = srem i16 %x, 4