diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp
--- a/llvm/lib/Analysis/InstructionSimplify.cpp
+++ b/llvm/lib/Analysis/InstructionSimplify.cpp
@@ -1115,6 +1115,16 @@
        match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
     return Op0;
 
+  // (X * Y) % Y -> 0 if the multiplication does not overflow.
+  Value *X;
+  if (match(Op0, m_c_Mul(m_Value(X), m_Specific(Op1)))) {
+    bool IsSigned = Opcode == Instruction::SRem;
+    auto *Mul = cast<OverflowingBinaryOperator>(Op0);
+    if ((IsSigned && Q.IIQ.hasNoSignedWrap(Mul)) ||
+        (!IsSigned && Q.IIQ.hasNoUnsignedWrap(Mul)))
+      return Constant::getNullValue(Op0->getType());
+  }
+
   // (X << Y) % X -> 0
   if (Q.IIQ.UseInstrInfo &&
       ((Opcode == Instruction::SRem &&
diff --git a/llvm/test/Transforms/InstSimplify/rem.ll b/llvm/test/Transforms/InstSimplify/rem.ll
--- a/llvm/test/Transforms/InstSimplify/rem.ll
+++ b/llvm/test/Transforms/InstSimplify/rem.ll
@@ -331,3 +331,86 @@
   %v = srem i8 -128, -1
   ret i8 %v
 }
+
+define i32 @srem_of_mul_nsw(i32 %x, i32 %y) {
+; CHECK-LABEL: @srem_of_mul_nsw(
+; CHECK-NEXT:    ret i32 0
+;
+  %mul = mul nsw i32 %x, %y
+  %mod = srem i32 %mul, %y
+  ret i32 %mod
+}
+
+; Verify that the optimization kicks in for:
+;   - Y * X % Y as well as X * Y % Y
+;   - vector types
+define <2 x i32> @srem_of_mul_nsw_vec_commuted(<2 x i32> %x, <2 x i32> %y) {
+; CHECK-LABEL: @srem_of_mul_nsw_vec_commuted(
+; CHECK-NEXT:    ret <2 x i32> zeroinitializer
+;
+  %mul = mul nsw <2 x i32> %y, %x
+  %mod = srem <2 x i32> %mul, %y
+  ret <2 x i32> %mod
+}
+
+define i32 @srem_of_mul_nuw(i32 %x, i32 %y) {
+; CHECK-LABEL: @srem_of_mul_nuw(
+; CHECK-NEXT:    [[MUL:%.*]] = mul nuw i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[MOD:%.*]] = srem i32 [[MUL]], [[Y]]
+; CHECK-NEXT:    ret i32 [[MOD]]
+;
+  %mul = mul nuw i32 %x, %y
+  %mod = srem i32 %mul, %y
+  ret i32 %mod
+}
+
+define i32 @srem_of_mul(i32 %x, i32 %y) {
+; CHECK-LABEL: @srem_of_mul(
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[MOD:%.*]] = srem i32 [[MUL]], [[Y]]
+; CHECK-NEXT:    ret i32 [[MOD]]
+;
+  %mul = mul i32 %x, %y
+  %mod = srem i32 %mul, %y
+  ret i32 %mod
+}
+
+define i32 @urem_of_mul_nsw(i32 %x, i32 %y) {
+; CHECK-LABEL: @urem_of_mul_nsw(
+; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[MOD:%.*]] = urem i32 [[MUL]], [[Y]]
+; CHECK-NEXT:    ret i32 [[MOD]]
+;
+  %mul = mul nsw i32 %x, %y
+  %mod = urem i32 %mul, %y
+  ret i32 %mod
+}
+
+define i32 @urem_of_mul_nuw(i32 %x, i32 %y) {
+; CHECK-LABEL: @urem_of_mul_nuw(
+; CHECK-NEXT:    ret i32 0
+;
+  %mul = mul nuw i32 %x, %y
+  %mod = urem i32 %mul, %y
+  ret i32 %mod
+}
+
+define <2 x i32> @srem_of_mul_nuw_vec_commuted(<2 x i32> %x, <2 x i32> %y) {
+; CHECK-LABEL: @srem_of_mul_nuw_vec_commuted(
+; CHECK-NEXT:    ret <2 x i32> zeroinitializer
+;
+  %mul = mul nuw <2 x i32> %y, %x
+  %mod = urem <2 x i32> %mul, %y
+  ret <2 x i32> %mod
+}
+
+define i32 @urem_of_mul(i32 %x, i32 %y) {
+; CHECK-LABEL: @urem_of_mul(
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[MOD:%.*]] = urem i32 [[MUL]], [[Y]]
+; CHECK-NEXT:    ret i32 [[MOD]]
+;
+  %mul = mul i32 %x, %y
+  %mod = urem i32 %mul, %y
+  ret i32 %mod
+}