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
@@ -1295,6 +1295,48 @@
       return new ICmpInst(Pred, X, Cmp.getOperand(1));
   }
 
+  // (icmp eq/ne (mul X Y)) -> (icmp eq/ne X/Y) if we know about whether X/Y are
+  // odd/non-zero/there is no overflow.
+  if (match(Cmp.getOperand(0), m_Mul(m_Value(X), m_Value(Y))) &&
+      ICmpInst::isEquality(Pred)) {
+
+    KnownBits XKnown = computeKnownBits(X, 0, &Cmp);
+    // if X % 2 != 0
+    //    (icmp eq/ne Y)
+    if (XKnown.countMaxTrailingZeros() == 0)
+      return new ICmpInst(Pred, Y, Cmp.getOperand(1));
+
+    KnownBits YKnown = computeKnownBits(Y, 0, &Cmp);
+    // if Y % 2 != 0
+    //    (icmp eq/ne X)
+    if (YKnown.countMaxTrailingZeros() == 0)
+      return new ICmpInst(Pred, X, Cmp.getOperand(1));
+
+    auto *BO0 = cast<OverflowingBinaryOperator>(Cmp.getOperand(0));
+    if (BO0->hasNoUnsignedWrap() || BO0->hasNoSignedWrap()) {
+      const SimplifyQuery Q = SQ.getWithInstruction(&Cmp);
+      // `isKnownNonZero` does more analysis than just `!KnownBits.One.isZero()`
+      // but to avoid unnecessary work, first just if this is an obvious case.
+
+      // if X non-zero and NoOverflow(X * Y)
+      //    (icmp eq/ne Y)
+      if (!XKnown.One.isZero() || isKnownNonZero(X, DL, 0, Q.AC, Q.CxtI, Q.DT))
+        return new ICmpInst(Pred, Y, Cmp.getOperand(1));
+
+      // if Y non-zero and NoOverflow(X * Y)
+      //    (icmp eq/ne X)
+      if (!YKnown.One.isZero() || isKnownNonZero(Y, DL, 0, Q.AC, Q.CxtI, Q.DT))
+        return new ICmpInst(Pred, X, Cmp.getOperand(1));
+    }
+    // Note, we are skipping cases:
+    //      if Y % 2 != 0 AND X % 2 != 0
+    //          (false/true)
+    //      if X non-zero and Y non-zero and NoOverflow(X * Y)
+    //          (false/true)
+    // Those can be simplified later as we would have already replaced the (icmp
+    // eq/ne (mul X, Y)) with (icmp eq/ne X/Y) and if X/Y is known non-zero that
+    // will fold to a constant elsewhere.
+  }
   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]]
 ;
@@ -88,8 +87,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]]
 ;
@@ -130,8 +128,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i64 [[OTHER:%.*]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[MUL:%.*]] = mul 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]]
 ;
@@ -199,8 +196,7 @@
 ; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
 ; CHECK-NEXT:    [[CMP2_NOT:%.*]] = icmp eq i64 [[AND1]], 0
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2_NOT]])
-; CHECK-NEXT:    [[MUL:%.*]] = mul 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]]
 ;
@@ -704,8 +700,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i64 [[OTHER:%.*]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64 [[AND]], 0
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; 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]]
 ;
@@ -773,8 +768,7 @@
 ; CHECK-NEXT:    [[AND1:%.*]] = and i64 [[OTHER:%.*]], 1
 ; CHECK-NEXT:    [[CMP2_NOT:%.*]] = icmp eq i64 [[AND1]], 0
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2_NOT]])
-; 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]]
 ;
@@ -823,8 +817,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]]
 ;
@@ -876,8 +869,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]]
 ;
@@ -1108,8 +1100,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()
@@ -1291,8 +1282,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()
@@ -1371,8 +1361,7 @@
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[OTHER:%.*]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[OTHER]], [[V:%.*]]
-; 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()
@@ -1497,8 +1486,7 @@
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[OTHER:%.*]], 1
 ; CHECK-NEXT:    [[CMP2_NOT:%.*]] = icmp eq i32 [[AND1]], 0
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP2_NOT]])
-; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[OTHER]], [[V]]
-; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[MUL]], 0
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i32 [[OTHER]], 0
 ; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_THEN5:%.*]], label [[IF_END6:%.*]]
 ; CHECK:       if.then5:
 ; 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: