Index: lib/Transforms/InstCombine/InstCombineCompares.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -1797,9 +1797,38 @@
   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);
Index: test/Transforms/InstCombine/icmp-mul.ll
===================================================================
--- test/Transforms/InstCombine/icmp-mul.ll
+++ test/Transforms/InstCombine/icmp-mul.ll
@@ -5,8 +5,7 @@
 
 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
@@ -16,8 +15,7 @@
 
 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
@@ -38,8 +36,7 @@
 
 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
@@ -62,8 +59,7 @@
 
 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
@@ -73,8 +69,7 @@
 
 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
@@ -95,8 +90,7 @@
 
 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
@@ -119,8 +113,7 @@
 
 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
@@ -130,8 +123,7 @@
 
 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