[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

336

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.

378

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,
+static Value *simplifyDivRem(Value *Op0, Value *Op1,
+                             Instruction::BinaryOps Opcode,
                              const SimplifyQuery &Q) {
+  bool IsDiv = (Opcode == Instruction::SDiv || Opcode == Instruction::UDiv);
+  bool IsSigned = (Opcode == Instruction::SDiv || Opcode == Instruction::SRem);
+
   Type *Ty = Op0->getType();
 
   // X / undef -> poison
   // X % undef -> poison
   if (Q.isUndefValue(Op1))
     return PoisonValue::get(Ty);
 
   // X / 0 -> poison
static Value *simplifyDivRem(Value *Op0, Value *Op1,
   // If this is a boolean op (single-bit element type), we can't have
   // division-by-zero or remainder-by-zero, so assume the divisor is 1.
   // Similarly, if we're zero-extending a boolean divisor, then assume it's a 1.
   Value *X;
   if (match(Op1, m_One()) || Ty->isIntOrIntVectorTy(1) ||
       (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
     return IsDiv ? Op0 : Constant::getNullValue(Ty);
 
+  // If X * Y does not overflow, then:
+  //   X * Y / Y -> X
+  //   X * Y % Y -> 0
+  if (match(Op0, m_c_Mul(m_Value(X), m_Specific(Op1)))) {
+    auto *Mul = cast<OverflowingBinaryOperator>(Op0);
+    // The multiplication can't overflow if it is defined not to, or if
+    // X == A / Y for some A.
+    if ((IsSigned && Q.IIQ.hasNoSignedWrap(Mul)) ||
+        (!IsSigned && Q.IIQ.hasNoUnsignedWrap(Mul)) ||
+        (IsSigned && match(X, m_SDiv(m_Value(), m_Specific(Op1)))) ||
+        (!IsSigned && match(X, m_UDiv(m_Value(), m_Specific(Op1))))) {
+      return IsDiv ? X : Constant::getNullValue(Op0->getType());
+    }
+  }
+
   return nullptr;
 }
 
 /// Given a predicate and two operands, return true if the comparison is true.
 /// This is a helper for div/rem simplification where we return some other value
 /// when we can prove a relationship between the operands.
 static bool isICmpTrue(ICmpInst::Predicate Pred, Value *LHS, Value *RHS,
                        const SimplifyQuery &Q, unsigned MaxRecurse) {

 }
 
 /// These are simplifications common to SDiv and UDiv.
 static Value *simplifyDiv(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
                           const SimplifyQuery &Q, unsigned MaxRecurse) {
   if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
     return C;
 
-  if (Value *V = simplifyDivRem(Op0, Op1, true, Q))
+  if (Value *V = simplifyDivRem(Op0, Op1, Opcode, Q))
     return V;
 
   bool IsSigned = Opcode == Instruction::SDiv;
 
-  // (X * Y) / Y -> X if the multiplication does not overflow.
-  Value *X;
-  if (match(Op0, m_c_Mul(m_Value(X), m_Specific(Op1)))) {
-    auto *Mul = cast<OverflowingBinaryOperator>(Op0);
-    // If the Mul does not overflow, then we are good to go.
-    if ((IsSigned && Q.IIQ.hasNoSignedWrap(Mul)) ||
-        (!IsSigned && Q.IIQ.hasNoUnsignedWrap(Mul)))
-      return X;
-    // If X has the form X = A / Y, then X * Y cannot overflow.
-    if ((IsSigned && match(X, m_SDiv(m_Value(), m_Specific(Op1)))) ||
-        (!IsSigned && match(X, m_UDiv(m_Value(), m_Specific(Op1)))))
-      return X;
-  }
-
   // (X rem Y) / Y -> 0
   if ((IsSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
       (!IsSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
     return Constant::getNullValue(Op0->getType());
 
   // (X /u C1) /u C2 -> 0 if C1 * C2 overflow
   ConstantInt *C1, *C2;
-  if (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_ConstantInt(C1))) &&
+  if (!IsSigned && match(Op0, m_UDiv(m_Value(), m_ConstantInt(C1))) &&
       match(Op1, m_ConstantInt(C2))) {
     bool Overflow;
     (void)C1->getValue().umul_ov(C2->getValue(), Overflow);
     if (Overflow)
       return Constant::getNullValue(Op0->getType());
   }
 
   // If the operation is with the result of a select instruction, check whether

 }
 
 /// These are simplifications common to SRem and URem.
 static Value *simplifyRem(Instruction::BinaryOps Opcode, Value *Op0, Value *Op1,
                           const SimplifyQuery &Q, unsigned MaxRecurse) {
   if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
     return C;
 
-  if (Value *V = simplifyDivRem(Op0, Op1, false, Q))
+  if (Value *V = simplifyDivRem(Op0, Op1, Opcode, Q))
     return V;
 
   // (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;

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:    [[MUL:%.*]] = mul nsw i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[MOD:%.*]] = srem i32 [[MUL]], [[Y]]
-; CHECK-NEXT:    ret i32 [[MOD]]
+; 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:    [[MUL:%.*]] = mul nsw <2 x i32> [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[MOD:%.*]] = srem <2 x i32> [[MUL]], [[Y]]
-; CHECK-NEXT:    ret <2 x i32> [[MOD]]
+; 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 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:    [[MUL:%.*]] = mul nuw i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[MOD:%.*]] = urem i32 [[MUL]], [[Y]]
-; CHECK-NEXT:    ret i32 [[MOD]]
+; 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:    [[MUL:%.*]] = mul nuw <2 x i32> [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[MOD:%.*]] = urem <2 x i32> [[MUL]], [[Y]]
-; CHECK-NEXT:    ret <2 x i32> [[MOD]]
+; 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
 }