diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
--- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -1294,7 +1294,53 @@
     if (XKnown.countMaxPopulation() == 1 && YKnown.countMinPopulation() >= 2)
       return new ICmpInst(Pred, X, Cmp.getOperand(1));
   }
+  // (icmp eq/ne (mul X Y)) ->
+  // if Y % 2 != 0 AND X % 2 != 0
+  //    (false/true)
+  // if X % 2 != 0
+  //    (icmp eq/ne Y)
+  // if Y % 2 != 0
+  //    (icmp eq/ne X)
+  // if X non-zero and Y non-zero and no_overflow(X * Y)
+  //    (false/true)
+  // if Y non-zero and no_overflow(X * Y)
+  //    (icmp eq/ne X)
+  // if X non-zero and no_overflow(X * Y)
+  //    (icmp eq/ne Y)
+  if (match(Cmp.getOperand(0), m_Mul(m_Value(X), m_Value(Y))) &&
+      ICmpInst::isEquality(Pred)) {
+    KnownBits XKnown = computeKnownBits(X, 0, &Cmp);
+    KnownBits YKnown = computeKnownBits(Y, 0, &Cmp);
 
+    // {X|Y}Unneeded is first set to whether X/Y is known odd. If so we can
+    // eliminate at least one of the values from the condition. If neither are
+    // odd then do then check if the multiplication is known to not overflow and
+    // if so, {X|Y}Unneeded is set to whether X/Y is known non-zero
+    bool XUnneeded = XKnown.countMaxTrailingZeros() == 0;
+    bool YUnneeded = YKnown.countMaxTrailingZeros() == 0;
+    if (!XUnneeded && !YUnneeded) {
+      // No information about oddness of X or Y so see if we can do the
+      // transformation using overflow information and zero/non-status
+      auto *BO0 = cast<OverflowingBinaryOperator>(Cmp.getOperand(0));
+      if (BO0->hasNoUnsignedWrap() || BO0->hasNoSignedWrap()) {
+        const SimplifyQuery Q = SQ.getWithInstruction(&Cmp);
+        XUnneeded = isKnownNonZero(X, DL, 0, Q.AC, Q.CxtI, Q.DT);
+        YUnneeded = isKnownNonZero(Y, DL, 0, Q.AC, Q.CxtI, Q.DT);
+      }
+    }
+    // If both are odd or there is no overflow and both are non-zero the
+    // multiplication is non-zero
+    if (XUnneeded && YUnneeded)
+      return replaceInstUsesWith(
+          Cmp, ConstantInt::getBool(Cmp.getType(), Pred == ICmpInst::ICMP_NE));
+
+    // If one of the ops is odd or there is no overflow and one is non-zero, we
+    // can replace the multiplation with just testing the other op
+    else if (XUnneeded)
+      return new ICmpInst(Pred, Y, Cmp.getOperand(1));
+    else if (YUnneeded)
+      return new ICmpInst(Pred, X, Cmp.getOperand(1));
+  }
   return nullptr;
 }
 
diff --git a/llvm/test/Transforms/InstCombine/icmp-binop.ll b/llvm/test/Transforms/InstCombine/icmp-binop.ll
--- a/llvm/test/Transforms/InstCombine/icmp-binop.ll
+++ b/llvm/test/Transforms/InstCombine/icmp-binop.ll
@@ -4,8 +4,7 @@
 define i64 @mul_assume_V_oddC_u64_setz(i64 %v) {
 ; CHECK-LABEL: @mul_assume_V_oddC_u64_setz(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[V:%.*]], 3
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL]], 0
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V:%.*]], 0
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
 ; CHECK-NEXT:    ret i64 [[CONV]]
 ;
@@ -52,8 +51,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[V]], 3
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL]], 0
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V]], 0
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
 ; CHECK-NEXT:    ret i64 [[CONV]]
 ;
@@ -94,8 +92,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i64 [[V:%.*]], 1
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i64 [[AND]], 0
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
-; CHECK-NEXT:    [[MUL:%.*]] = mul i64 [[V]], 3
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL]], 0
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V]], 0
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
 ; CHECK-NEXT:    ret i64 [[CONV]]
 ;
@@ -846,8 +843,7 @@
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP1]])
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i64 [[OTHER:%.*]], 8
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
-; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[OTHER]], [[V]]
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL]], 0
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[OTHER]], 0
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
 ; CHECK-NEXT:    ret i64 [[CONV]]
 ;
@@ -899,8 +895,7 @@
 ; CHECK-NEXT:    [[CMP4:%.*]] = icmp ne i64 [[OTHER]], 0
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2]])
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP4]])
-; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i64 [[OTHER]], [[V]]
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[MUL]], 0
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64 [[V]], 0
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[TOBOOL_NOT]] to i64
 ; CHECK-NEXT:    ret i64 [[CONV]]
 ;
@@ -1137,8 +1132,7 @@
 define i32 @mul_assume_V_oddC_u32_brz(i32 %v) {
 ; CHECK-LABEL: @mul_assume_V_oddC_u32_brz(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[V:%.*]], 3
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[V:%.*]], 0
 ; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
@@ -1246,8 +1240,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[V]], 3
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[V]], 0
 ; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN1:%.*]], label [[IF_END2:%.*]]
 ; CHECK:       if.then1:
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
@@ -1326,8 +1319,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[V:%.*]], 1
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[AND]], 0
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT]])
-; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[V]], 3
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[V]], 0
 ; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN1:%.*]], label [[IF_END2:%.*]]
 ; CHECK:       if.then1:
 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 (...) @foo32()
diff --git a/llvm/test/Transforms/InstCombine/pr38677.ll b/llvm/test/Transforms/InstCombine/pr38677.ll
--- a/llvm/test/Transforms/InstCombine/pr38677.ll
+++ b/llvm/test/Transforms/InstCombine/pr38677.ll
@@ -12,9 +12,7 @@
 ; CHECK-NEXT:    br label [[FINAL]]
 ; CHECK:       final:
 ; CHECK-NEXT:    [[USE2:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ select (i1 icmp eq (ptr @A, ptr @B), i32 2, i32 1), [[DELAY]] ]
-; CHECK-NEXT:    [[B7:%.*]] = mul i32 [[USE2]], 2147483647
-; CHECK-NEXT:    [[C3:%.*]] = icmp eq i32 [[B7]], 0
-; CHECK-NEXT:    store i1 [[C3]], ptr [[DST:%.*]], align 1
+; CHECK-NEXT:    store i1 false, ptr [[DST:%.*]], align 1
 ; CHECK-NEXT:    ret i32 [[USE2]]
 ;
 entry: