[InstCombine] Add combines of icmp (mul nsw/nuw X, C2), C when C % C2 == 0

[Nicola]

Summary

I think this is the least tricky part of the combines. The proof for this (and all the others) is here:

• eq/neq: https://rise4fun.com/Alive/9PBA
• sgt/ugt: https://rise4fun.com/Alive/58yr
• slt/ult: https://rise4fun.com/Alive/VCQ

The ones implemented here are the ones with the C2 % C1 == 0

[spatel]

There's enough going on here that I'd prefer to split this patch up further. Can you start by handling just the eq/ne predicates? If the remainder is non-zero there, instsimplify should fold this down to a true or false value. Start with that patch?

We're missing tests/proofs for the 'nuw' variants of the eq/ne patterns. Also, what happens if the mul has both nsw and nuw?

lib/Transforms/InstCombine/InstCombineCompares.cpp

1814–1816

We should always bail out of this function if MulC is 0 right at the top. That means instsimplify hasn't run yet on this expression, so we're wasting time on (and potentially obscuring) a pattern that can be completely eliminated.

1819

Sink the creation of ReducedVal. We don't want to do that unless we know the transform will fire.

1821–1823

Don't use braces here according to LLVM coding guidelines.

lib/Transforms/InstCombine/InstCombineCompares.cpp

 /// Fold icmp (mul X, Y), C.
 Instruction *InstCombiner::foldICmpMulConstant(ICmpInst &Cmp,
                                                BinaryOperator *Mul,
                                                const APInt &C) {
   const APInt *MulC;
   if (!match(Mul->getOperand(1), m_APInt(MulC)))
     return nullptr;
 
+  ICmpInst::Predicate Pred = Cmp.getPredicate();
+  // Recognize patterns such as icmp (mul X, MulC), C --> icmp X, C/MulC
+  // If C is a multiple of MulC, then the mul can be folded in the icmp.
+  if ((Mul->hasNoSignedWrap() &&
+       (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLT)) ||
+      (Mul->hasNoUnsignedWrap() &&
+       (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_ULT)) ||
+      (Cmp.isEquality() &&
+       (Mul->hasNoUnsignedWrap() || Mul->hasNoSignedWrap()))) {
+    Type *OpType = Mul->getType();
+    APInt MinInt = APInt::getSignedMinValue(C.getBitWidth());
+    // When matching a signed comparison we can't fold if C is MinInt and
+    // MulC is negative as -MinInt doesn't exist.
+    // Avoid handing the MinInt case for now.
+    bool ReduceSigned = Cmp.isSigned() && (*MulC != 0 && C != MinInt);
+    bool ReduceUnsigned = Cmp.isUnsigned() && *MulC != 0;
+    bool ReduceEquality = Cmp.isEquality() && (*MulC != 0 && C != MinInt);
+    if (ReduceSigned || ReduceUnsigned || ReduceEquality) {
+      APInt RemVal = Mul->hasNoSignedWrap() ? C.srem(*MulC) : C.urem(*MulC);
+      APInt ReducedVal = Mul->hasNoSignedWrap() ? C.sdiv(*MulC) : C.udiv(*MulC);
+      if (RemVal == 0) {
+        if (MulC->isNegative()) {
+          Pred = ICmpInst::getSwappedPredicate(Pred);
+        }
+        return new ICmpInst(Pred, Mul->getOperand(0),
+                            ConstantInt::get(OpType, ReducedVal));
+      }
+    }
+  }
+
   // If this is a test of the sign bit and the multiply is sign-preserving with
   // a constant operand, use the multiply LHS operand instead.
-  ICmpInst::Predicate Pred = Cmp.getPredicate();
   if (isSignTest(Pred, C) && Mul->hasNoSignedWrap()) {
     if (MulC->isNegative())
       Pred = ICmpInst::getSwappedPredicate(Pred);
     return new ICmpInst(Pred, Mul->getOperand(0),
                         Constant::getNullValue(Mul->getType()));
   }
 
   return nullptr;

test/Transforms/InstCombine/icmp-mul.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; Tests for slt/ult
 
 define i1 @slt_positive_multip_rem_zero(i8 %x) {
 ; CHECK-LABEL: @slt_positive_multip_rem_zero(
-; CHECK-NEXT:    [[A:%.*]] = mul nsw i8 [[X:%.*]], 7
-; CHECK-NEXT:    [[B:%.*]] = icmp slt i8 [[A]], 21
+; CHECK-NEXT:    [[B:%.*]] = icmp slt i8 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nsw i8 %x, 7
   %b = icmp slt i8 %a, 21
   ret i1 %b
 }
 
 define i1 @slt_negative_multip_rem_zero(i8 %x) {
 ; CHECK-LABEL: @slt_negative_multip_rem_zero(
-; CHECK-NEXT:    [[A:%.*]] = mul nsw i8 [[X:%.*]], -7
-; CHECK-NEXT:    [[B:%.*]] = icmp slt i8 [[A]], 21
+; CHECK-NEXT:    [[B:%.*]] = icmp sgt i8 [[X:%.*]], -3
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nsw i8 %x, -7
   %b = icmp slt i8 %a, 21
   ret i1 %b
 }
 
 define i1 @slt_positive_multip_rem_nz(i8 %x) {
 ; CHECK-LABEL: @slt_positive_multip_rem_nz(
 ; CHECK-NEXT:    [[A:%.*]] = mul nsw i8 [[X:%.*]], 5
 ; CHECK-NEXT:    [[B:%.*]] = icmp slt i8 [[A]], 21
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nsw i8 %x, 5
   %b = icmp slt i8 %a, 21
   ret i1 %b
 }
 
 define i1 @ult_rem_zero(i8 %x) {
 ; CHECK-LABEL: @ult_rem_zero(
-; CHECK-NEXT:    [[A:%.*]] = mul nuw i8 [[X:%.*]], 7
-; CHECK-NEXT:    [[B:%.*]] = icmp ult i8 [[A]], 21
+; CHECK-NEXT:    [[B:%.*]] = icmp ult i8 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nuw i8 %x, 7
   %b = icmp ult i8 %a, 21
   ret i1 %b
 }
 
 define i1 @ult_rem_nz(i8 %x) {
 ; CHECK-LABEL: @ult_rem_nz(
 ; CHECK-NEXT:    [[A:%.*]] = mul nuw i8 [[X:%.*]], 5
 ; CHECK-NEXT:    [[B:%.*]] = icmp ult i8 [[A]], 21
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nuw i8 %x, 5
   %b = icmp ult i8 %a, 21
   ret i1 %b
 }
 
 ; Tests for sgt/ugt
 
 define i1 @sgt_positive_multip_rem_zero(i8 %x) {
 ; CHECK-LABEL: @sgt_positive_multip_rem_zero(
-; CHECK-NEXT:    [[A:%.*]] = mul nsw i8 [[X:%.*]], 7
-; CHECK-NEXT:    [[B:%.*]] = icmp sgt i8 [[A]], 21
+; CHECK-NEXT:    [[B:%.*]] = icmp sgt i8 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nsw i8 %x, 7
   %b = icmp sgt i8 %a, 21
   ret i1 %b
 }
 
 define i1 @sgt_negative_multip_rem_zero(i8 %x) {
 ; CHECK-LABEL: @sgt_negative_multip_rem_zero(
-; CHECK-NEXT:    [[A:%.*]] = mul nsw i8 [[X:%.*]], -7
-; CHECK-NEXT:    [[B:%.*]] = icmp sgt i8 [[A]], 21
+; CHECK-NEXT:    [[B:%.*]] = icmp slt i8 [[X:%.*]], -3
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nsw i8 %x, -7
   %b = icmp sgt i8 %a, 21
   ret i1 %b
 }
 
 define i1 @sgt_positive_multip_rem_nz(i8 %x) {
 ; CHECK-LABEL: @sgt_positive_multip_rem_nz(
 ; CHECK-NEXT:    [[A:%.*]] = mul nsw i8 [[X:%.*]], 5
 ; CHECK-NEXT:    [[B:%.*]] = icmp sgt i8 [[A]], 21
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nsw i8 %x, 5
   %b = icmp sgt i8 %a, 21
   ret i1 %b
 }
 
 define i1 @ugt_rem_zero(i8 %x) {
 ; CHECK-LABEL: @ugt_rem_zero(
-; CHECK-NEXT:    [[A:%.*]] = mul nuw i8 [[X:%.*]], 7
-; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[A]], 21
+; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nuw i8 %x, 7
   %b = icmp ugt i8 %a, 21
   ret i1 %b
 }
 
 define i1 @ugt_rem_nz(i8 %x) {
 ; CHECK-LABEL: @ugt_rem_nz(
 ; CHECK-NEXT:    [[A:%.*]] = mul nuw i8 [[X:%.*]], 5
 ; CHECK-NEXT:    [[B:%.*]] = icmp ugt i8 [[A]], 21
 ; CHECK-NEXT:    ret i1 [[B]]
 ;
   %a = mul nuw i8 %x, 5
   %b = icmp ugt i8 %a, 21
   ret i1 %b
 }
 
 ; Tests for eq/ne
 
 define i1 @eq_rem_zero(i8 %x) {
 ; CHECK-LABEL: @eq_rem_zero(
-; CHECK-NEXT:    [[A:%.*]] = mul nuw 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 nuw i8 %x, 5
   %b = icmp eq i8 %a, 20
   ret i1 %b
 }
 
 define i1 @ne_rem_zero(i8 %x) {
 ; CHECK-LABEL: @ne_rem_zero(
-; CHECK-NEXT:    [[A:%.*]] = mul nuw 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 nuw i8 %x, 5
   %b = icmp ne i8 %a, 30
   ret i1 %b
 }
 
 define i1 @eq_rem_nz(i8 %x) {