[InstSimplify] Transform X * Y % Y --> 0.

[davidtgoldblatt]

Summary

simplifyDiv already handles the case X * Y / Y --> X (barring overflow).
This adds the equivalent handling to simplifyRem.

Correctness:
https://alive2.llvm.org/ce/z/J2cUbS
https://alive2.llvm.org/ce/z/us9NUM
https://alive2.llvm.org/ce/z/AvaDGJ
https://alive2.llvm.org/ce/z/kq9ige

Extending the situations in which we apply this transform would not be
correct:
https://alive2.llvm.org/ce/z/Lf9V63
https://alive2.llvm.org/ce/z/6RPQK3
https://alive2.llvm.org/ce/z/p9UdxC
https://alive2.llvm.org/ce/z/A2zlhE
https://alive2.llvm.org/ce/z/vHTtLw
https://alive2.llvm.org/ce/z/lvpH42

[spatel]

Do you have commit access? If so, please add the test file with baseline CHECK lines as a preliminary patch.

llvm/test/Transforms/InstSimplify/rem.ll

335

We should have the commuted variant of this test too. Even better if you use a vector type for that case, so we have coverage for that possibility too.

377

Similar to above - please add a commuted mul operand test for more coverage.

[davidtgoldblatt]

Add commuted and vector test cases.

[davidtgoldblatt]

I don't have commit access. Happy to split this in two and do two diffs if you'd prefer, though.

[spatel]

In D102864#2772310, @davidtgoldblatt wrote:

I don't have commit access. Happy to split this in two and do two diffs if you'd prefer, though.

No problem. I can commit on your behalf. To confirm - use your gmail address for author info?

Would it make sense to unify this with the related div transforms? If I'm seeing it correctly, we could also pick up this (and unsigned sibling) transform if we can generalize that block:
https://alive2.llvm.org/ce/z/AvaDGJ

define i8 @src(i8 %a, i8 %y) {
  %x = sdiv i8 %a, %y
  %mul = mul i8 %x, %y
  %mod = srem i8 %mul, %y
  ret i8 %mod
}

define i8 @tgt(i8 %x, i8 %y) {
  ret i8 0
}

Interestingly, it looks like we currently miscompile that pattern in instcombine.

[davidtgoldblatt]

In D102864#2773521, @spatel wrote:

No problem. I can commit on your behalf. To confirm - use your gmail address for author info?

Yep, that should be fine, thank you.

Would it make sense to unify this with the related div transforms? If I'm seeing it correctly, we could also pick up this (and unsigned sibling) transform if we can generalize that block:
https://alive2.llvm.org/ce/z/AvaDGJ

I.e. pull out the signedness checks into bool NoOverflow or something, and additionally set NoOverflow to true if the X in X * Y / Y or X * Y % Y is of the form A / Y? I think we still need to check the specific operation (to decide to reduce to X or 0), but I think it does get us some extra cases we can simplify. Happy to do so if you'd prefer, although my initial thought is that it's a little complex for a case I don't know I've seen.

[spatel]

In D102864#2774356, @davidtgoldblatt wrote:

In D102864#2773521, @spatel wrote:

No problem. I can commit on your behalf. To confirm - use your gmail address for author info?

Yep, that should be fine, thank you.

Please update and regenerate the test CHECK lines after: 3c4b79481d45

Would it make sense to unify this with the related div transforms? If I'm seeing it correctly, we could also pick up this (and unsigned sibling) transform if we can generalize that block:
https://alive2.llvm.org/ce/z/AvaDGJ

I.e. pull out the signedness checks into bool NoOverflow or something, and additionally set NoOverflow to true if the X in X * Y / Y or X * Y % Y is of the form A / Y? I think we still need to check the specific operation (to decide to reduce to X or 0), but I think it does get us some extra cases we can simplify. Happy to do so if you'd prefer, although my initial thought is that it's a little complex for a case I don't know I've seen.

That's fine - we can make that a potential follow-up. You could add a TODO comment. The related block in simplifyDiv() is at line 1055. We make the code a bit more complicated by generalizing it in simplifyDivRem(), but then we're less likely to lose a transform.

[spatel]

In D102864#2773521, @spatel wrote:

define i8 @src(i8 %a, i8 %y) {

%x = sdiv i8 %a, %y
%mul = mul i8 %x, %y
%mod = srem i8 %mul, %y
ret i8 %mod

}
Interestingly, it looks like we currently miscompile that pattern in instcombine.

For reference, that miscompile appears to be only with an undef input. We have a mul transform that creates an extra use of the numerator op, so we need to freeze it to make the transform safe.

[davidtgoldblatt]

Merge cases into simplifyDivRem

Went ahead and did the suggested unification, which was an obvious improvement
once I understood things better.

[davidtgoldblatt]

BTW, re-reading I realized I phrased that diff update poorly. I meant to say something more like "now that I understand better, it's obvious to me that you're right", not like "that thing you pointed out was obvious"; hopefully it parsed that way, and sorry if it didn't.

[xbolva00]

llvm/lib/Analysis/InstructionSimplify.cpp

926

Nit: opcode as 1st arg?

[spatel]

Since we expanded the scope of the transform, we need a few more tests. Feel free to add to or adjust this if you want:
cb3bc9d81d

Also, we should add an Alive2 link for that general pattern to the list in the patch summary/commit message:
https://alive2.llvm.org/ce/z/AvaDGJ

[davidtgoldblatt]

Add (a / y) * y % y tests, make Opcode first arg, add Alive2 links to the commit message.

[spatel]

LGTM - thanks!
Sorry if it wasn't clear - I already committed the extra tests to the main branch, so you can rebase off of that here. If you get to it first, please update here, otherwise I'll merge before landing.

[davidtgoldblatt]

Ah, gotcha, thanks. Still learning the LLVM diff workflows.

llvm/lib/Analysis/InstructionSimplify.cpp

 }
 
 Value *llvm::SimplifyMulInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
   return ::SimplifyMulInst(Op0, Op1, Q, RecursionLimit);
 }
 
 /// Check for common or similar folds of integer division or integer remainder.
 /// This applies to all 4 opcodes (sdiv/udiv/srem/urem).
 static Value *simplifyDivRem(Value *Op0, Value *Op1, bool IsDiv,
                              const SimplifyQuery &Q) {
   Type *Ty = Op0->getType();
 
   // X / undef -> poison
   // X % undef -> poison
   if (Q.isUndefValue(Op1))
     return PoisonValue::get(Ty);
 
static Value *simplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
 
   // (X % Y) % Y -> X % Y
   if ((Opcode == Instruction::SRem &&
        match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
       (Opcode == Instruction::URem &&
        match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
     return Op0;
 
+  // (X * Y) % Y -> 0 if the multiplication does not overflow.
+  Value *X;
+  if (match(Op0, m_c_Mul(m_Value(X), m_Specific(Op1)))) {
+    bool IsSigned = Opcode == Instruction::SRem;
+    auto *Mul = cast<OverflowingBinaryOperator>(Op0);
+    if ((IsSigned && Q.IIQ.hasNoSignedWrap(Mul)) ||
+        (!IsSigned && Q.IIQ.hasNoUnsignedWrap(Mul)))
+      return Constant::getNullValue(Op0->getType());
+  }
+
   // (X << Y) % X -> 0
   if (Q.IIQ.UseInstrInfo &&
       ((Opcode == Instruction::SRem &&
         match(Op0, m_NSWShl(m_Specific(Op1), m_Value()))) ||
        (Opcode == Instruction::URem &&
         match(Op0, m_NUWShl(m_Specific(Op1), m_Value())))))
     return Constant::getNullValue(Op0->getType());
 

llvm/test/Transforms/InstSimplify/rem.ll

 }
 
 define i8 @srem_minusone_divisor() {
 ; CHECK-LABEL: @srem_minusone_divisor
 ; CHECK-NEXT:   ret i8 poison
   %v = srem i8 -128, -1
   ret i8 %v
 }
+
+define i32 @srem_of_mul_nsw(i32 %x, i32 %y) {
+; CHECK-LABEL: @srem_of_mul_nsw(
+; CHECK-NEXT:    ret i32 0
+;
+  %mul = mul nsw i32 %x, %y
+  %mod = srem i32 %mul, %y
+  ret i32 %mod
+}
+
+; Verify that the optimization kicks in for:
+;   - Y * X % Y as well as X * Y % Y
+;   - vector types
+define <2 x i32> @srem_of_mul_nsw_vec_commuted(<2 x i32> %x, <2 x i32> %y) {
+; CHECK-LABEL: @srem_of_mul_nsw_vec_commuted(
+; CHECK-NEXT:    ret <2 x i32> zeroinitializer
+;
+  %mul = mul nsw <2 x i32> %y, %x
+  %mod = srem <2 x i32> %mul, %y
+  ret <2 x i32> %mod
+}
+
+define i32 @srem_of_mul_nuw(i32 %x, i32 %y) {
+; CHECK-LABEL: @srem_of_mul_nuw(
+; CHECK-NEXT:    [[MUL:%.*]] = mul nuw i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[MOD:%.*]] = srem i32 [[MUL]], [[Y]]
+; CHECK-NEXT:    ret i32 [[MOD]]
+;
+  %mul = mul nuw i32 %x, %y
+  %mod = srem i32 %mul, %y
+  ret i32 %mod
+}
+
+define i32 @srem_of_mul(i32 %x, i32 %y) {
+; CHECK-LABEL: @srem_of_mul(
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[MOD:%.*]] = srem i32 [[MUL]], [[Y]]
+; CHECK-NEXT:    ret i32 [[MOD]]
+;
+  %mul = mul i32 %x, %y
+  %mod = srem i32 %mul, %y
+  ret i32 %mod
+}
+
+define i32 @urem_of_mul_nsw(i32 %x, i32 %y) {
+; CHECK-LABEL: @urem_of_mul_nsw(
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[MOD:%.*]] = urem i32 [[MUL]], [[Y]]
+; CHECK-NEXT:    ret i32 [[MOD]]
+;
+  %mul = mul nsw i32 %x, %y
+  %mod = urem i32 %mul, %y
+  ret i32 %mod
+}
+
+define i32 @urem_of_mul_nuw(i32 %x, i32 %y) {
+; CHECK-LABEL: @urem_of_mul_nuw(
+; CHECK-NEXT:    ret i32 0
+;
+  %mul = mul nuw i32 %x, %y
+  %mod = urem i32 %mul, %y
+  ret i32 %mod
+}
+
+define <2 x i32> @srem_of_mul_nuw_vec_commuted(<2 x i32> %x, <2 x i32> %y) {
+; CHECK-LABEL: @srem_of_mul_nuw_vec_commuted(
+; CHECK-NEXT:    ret <2 x i32> zeroinitializer
+;
+  %mul = mul nuw <2 x i32> %y, %x
+  %mod = urem <2 x i32> %mul, %y
+  ret <2 x i32> %mod
+}
+
+define i32 @urem_of_mul(i32 %x, i32 %y) {
+; CHECK-LABEL: @urem_of_mul(
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[MOD:%.*]] = urem i32 [[MUL]], [[Y]]
+; CHECK-NEXT:    ret i32 [[MOD]]
+;
+  %mul = mul i32 %x, %y
+  %mod = urem i32 %mul, %y
+  ret i32 %mod
+}