[InstCombine] Add transform for `(mul X, OddC) eq/ne N * C` --> `X eq/ne N`

[goldstein.w.n]

Summary

We previously only did this if the mul was nuw, but it works for
any odd value.

Alive2 Links:
EQ: https://alive2.llvm.org/ce/z/6_HPZ5
NE: https://alive2.llvm.org/ce/z/c34qSU

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::foldICmpMulConstant(ICmpInst &Cmp,
   // (X * +MulC) < 0 --> X < 0
   // (X * -MulC) < 0 --> X > 0
   if (isSignTest(Pred, C) && Mul->hasNoSignedWrap()) {
     if (MulC->isNegative())
       Pred = ICmpInst::getSwappedPredicate(Pred);
     return new ICmpInst(Pred, X, ConstantInt::getNullValue(MulTy));
   }
 
-  if (MulC->isZero() || (!Mul->hasNoSignedWrap() && !Mul->hasNoUnsignedWrap()))
+  if (MulC->isZero())
     return nullptr;
 
-  // If the multiply does not wrap, try to divide the compare constant by the
-  // multiplication factor.
+  // If the multiply does not wrap or the constant is odd, try to divide the
+  // compare constant by the multiplication factor.
   if (Cmp.isEquality()) {
-    // (mul nsw X, MulC) == C --> X == C /s MulC
+    // (mul nsw X, MulC) eq/ne C --> X eq/ne C /s MulC
     if (Mul->hasNoSignedWrap() && C.srem(*MulC).isZero()) {
       Constant *NewC = ConstantInt::get(MulTy, C.sdiv(*MulC));
       return new ICmpInst(Pred, X, NewC);
     }
-    // (mul nuw X, MulC) == C --> X == C /u MulC
-    if (Mul->hasNoUnsignedWrap() && C.urem(*MulC).isZero()) {
+
+    // C % MulC == 0 is weaker than we could use if MulC is odd because it
+    // correct to transform if MulC * N == C including overflow. I.e with i8
+    // (icmp eq (mul X, 5), 101) -> (icmp eq X, 225) but since 101 % 5 != 0, we
+    // miss that case.
+    if (C.urem(*MulC).isZero()) {
+      // (mul nuw X, MulC) eq/ne C --> X eq/ne C /u MulC
+      // (mul X, OddC) eq/ne N * C --> X eq/ne N
+      if ((*MulC & 1).isOne() || Mul->hasNoUnsignedWrap()) {
         Constant *NewC = ConstantInt::get(MulTy, C.udiv(*MulC));
         return new ICmpInst(Pred, X, NewC);
       }
     }
+  }
+
+  if (!Mul->hasNoSignedWrap() && !Mul->hasNoUnsignedWrap())
+    return nullptr;
 
   // With a matching no-overflow guarantee, fold the constants:
   // (X * MulC) < C --> X < (C / MulC)
   // (X * MulC) > C --> X > (C / MulC)
   // TODO: Assert that Pred is not equal to SGE, SLE, UGE, ULE?
   Constant *NewC = nullptr;
   if (Mul->hasNoSignedWrap()) {
     // MININT / -1 --> overflow.

llvm/test/Transforms/InstCombine/icmp-mul.ll

 ;
   %a = mul nsw i8 %x, 0
   %b = icmp sgt i8 %a, 21
   ret i1 %b
 }
 
 define i1 @eq_rem_zero_nonuw(i8 %x) {
 ; CHECK-LABEL: @eq_rem_zero_nonuw(
-; CHECK-NEXT:    [[A:%.*]] = mul i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[B:%.*]] = icmp eq i8 [[A]], 20
+; CHECK-NEXT:    [[B:%.*]] = icmp eq i8 [[X:%.*]], 4
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul i8 %x, 5
   %b = icmp eq i8 %a, 20
   ret i1 %b
 }
 
 define i1 @ne_rem_zero_nonuw(i8 %x) {
 ; CHECK-LABEL: @ne_rem_zero_nonuw(
-; CHECK-NEXT:    [[A:%.*]] = mul i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[B:%.*]] = icmp ne i8 [[A]], 30
+; CHECK-NEXT:    [[B:%.*]] = icmp ne i8 [[X:%.*]], 6
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul i8 %x, 5
   %b = icmp ne i8 %a, 30
   ret i1 %b
 }
 
 define i1 @mul_constant_eq(i32 %x, i32 %y) {

 ;
   %mul = mul i8 %v, 6
   %cmp = icmp ne i8 %mul, 36
   ret i1 %cmp
 }
 
 define <2 x i1> @mul_oddC_ne_vec(<2 x i8> %v) {
 ; CHECK-LABEL: @mul_oddC_ne_vec(
-; CHECK-NEXT:    [[MUL:%.*]] = mul <2 x i8> [[V:%.*]], <i8 3, i8 3>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i8> [[MUL]], <i8 12, i8 12>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i8> [[V:%.*]], <i8 4, i8 4>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %mul = mul <2 x i8> %v, <i8 3, i8 3>
   %cmp = icmp ne <2 x i8> %mul, <i8 12, i8 12>
   ret <2 x i1> %cmp
 }
 
 define <2 x i1> @mul_oddC_ne_nosplat_vec(<2 x i8> %v) {