diff --git a/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
--- a/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
@@ -1681,6 +1681,125 @@
   return nullptr;
 }
 
+static Instruction *simplifyIRemMulShl(BinaryOperator &I,
+                                       InstCombinerImpl &IC) {
+  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
+
+  // Variety of transform for (urem/srem (mul/shl X, Y), (mul/shl X, Z))
+  Value *A, *B, *C, *D;
+  if (!(match(Op0, m_Mul(m_Value(A), m_Value(B))) ||
+        match(Op0, m_Shl(m_Value(A), m_Value(B)))) ||
+      !(match(Op1, m_Mul(m_Value(C), m_Value(D))) ||
+        match(Op1, m_Shl(m_Value(C), m_Value(D)))))
+    return nullptr;
+
+  Value *X, *Y, *Z;
+  X = nullptr;
+  // Do this by hand as opposed to using m_Specific because either A/B (or
+  // C/D) can be our X.
+  if (A == C || A == D) {
+    X = A;
+    Y = B;
+    Z = A == C ? D : C;
+  } else if (B == C || B == D) {
+    X = B;
+    Y = A;
+    Z = B == C ? D : C;
+  }
+
+  if (!X)
+    return nullptr;
+
+  // BO0 = X * Y
+  BinaryOperator *BO0 = dyn_cast<BinaryOperator>(Op0);
+  // BO1 = X * Z
+  BinaryOperator *BO1 = dyn_cast<BinaryOperator>(Op1);
+
+  if (!BO0 || !BO1)
+    return nullptr;
+
+  // If X is constant 1, then we avoid both in the mul and shl case.
+  Constant *CX = dyn_cast<Constant>(X);
+  if (CX && CX->isOneValue())
+    return nullptr;
+
+  Type *Ty = I.getType();
+
+  ConstantInt *ConstY = dyn_cast<ConstantInt>(Y);
+  ConstantInt *ConstZ = dyn_cast<ConstantInt>(Z);
+  if (Ty->isVectorTy()) {
+    auto *VConstY = dyn_cast<Constant>(Y);
+    auto *VConstZ = dyn_cast<Constant>(Z);
+    if (VConstY && VConstZ) {
+      VConstY = VConstY->getSplatValue();
+      VConstZ = VConstZ->getSplatValue();
+      if (VConstY && VConstZ) {
+        ConstY = dyn_cast<ConstantInt>(VConstY);
+        ConstZ = dyn_cast<ConstantInt>(VConstZ);
+      }
+    }
+  }
+  bool IsSigned = I.getOpcode() == Instruction::SRem;
+
+  bool NSW0 = BO0->hasNoSignedWrap();
+  bool NSW1 = BO1->hasNoSignedWrap();
+  bool NUW0 = BO0->hasNoUnsignedWrap();
+  bool NUW1 = BO1->hasNoUnsignedWrap();
+
+  // Try to handle constant cases first.
+  if (!ConstY || !ConstZ)
+    return nullptr;
+
+  APInt APIntY = ConstY->getValue();
+  APInt APIntZ = ConstZ->getValue();
+
+  // Just treat the shifts as mul, we may end up returning a mul by power
+  // of 2 but that will be cleaned up later.
+  if (BO0->getOpcode() == Instruction::Shl)
+    APIntY = APInt(APIntY.getBitWidth(), 1) << APIntY;
+  if (BO1->getOpcode() == Instruction::Shl)
+    APIntZ = APInt(APIntZ.getBitWidth(), 1) << APIntZ;
+
+  APInt RemYZ = IsSigned ? APIntY.srem(APIntZ) : APIntY.urem(APIntZ);
+
+  // (rem (mul nuw/nsw X, Y), (mul X, Z))
+  //      if (rem Y, Z) == 0
+  //          -> 0
+  if (RemYZ.isZero() && (IsSigned ? NSW0 : NUW0))
+    return IC.replaceInstUsesWith(I, ConstantInt::getNullValue(Ty));
+
+  // (rem (mul X, Y), (mul nuw/nsw X, Z))
+  //      if (rem Y, Z) == Y
+  //          -> (mul nuw/nsw X, Y)
+  if (RemYZ == APIntY && (IsSigned ? NSW1 : NUW1)) {
+    // We are returning Op0 essentially but we can also add no wrap flags.
+    BinaryOperator *BO =
+        BinaryOperator::CreateMul(X, ConstantInt::get(Ty, APIntY));
+    // We can add nsw/nuw if remainder op is signed/unsigned, also we
+    // can copy any overflow flags from Op0.
+    if (IsSigned || NSW0)
+      BO->setHasNoSignedWrap();
+    if (!IsSigned || NUW0)
+      BO->setHasNoUnsignedWrap();
+    return BO;
+  }
+
+  // (rem (mul nuw/nsw X, Y), (mul {nsw} X, Z))
+  //      if Y >= Z
+  //          -> (mul {nuw} nsw X, (rem Y, Z))
+  // NB: (rem Y, Z) is a constant.
+  if (APIntY.uge(APIntZ) && (IsSigned ? (NSW0 && NSW1) : NUW0)) {
+    BinaryOperator *BO =
+        BinaryOperator::CreateMul(X, ConstantInt::get(Ty, RemYZ));
+    BO->setHasNoSignedWrap();
+    if (!IsSigned || NUW0)
+      BO->setHasNoUnsignedWrap();
+    return BO;
+  }
+
+  return nullptr;
+}
+
 /// This function implements the transforms common to both integer remainder
 /// instructions (urem and srem). It is called by the visitors to those integer
 /// remainder instructions.
@@ -1733,6 +1852,9 @@
     }
   }
 
+  if (Instruction *R = simplifyIRemMulShl(I, *this))
+    return R;
+
   return nullptr;
 }
 
diff --git a/llvm/test/Transforms/InstCombine/urem-mul.ll b/llvm/test/Transforms/InstCombine/urem-mul.ll
--- a/llvm/test/Transforms/InstCombine/urem-mul.ll
+++ b/llvm/test/Transforms/InstCombine/urem-mul.ll
@@ -31,10 +31,7 @@
 
 define i8 @urem_CY_CZ_is_zero(i8 %X) {
 ; CHECK-LABEL: @urem_CY_CZ_is_zero(
-; CHECK-NEXT:    [[BO0:%.*]] = mul nuw i8 [[X:%.*]], 15
-; CHECK-NEXT:    [[BO1:%.*]] = mul i8 [[X]], 5
-; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 0
 ;
   %BO0 = mul nuw i8 %X, 15
   %BO1 = mul i8 %X, 5
@@ -57,9 +54,7 @@
 
 define i8 @urem_CY_CZ_is_BO0(i8 %X) {
 ; CHECK-LABEL: @urem_CY_CZ_is_BO0(
-; CHECK-NEXT:    [[BO0:%.*]] = mul i8 [[X:%.*]], 3
-; CHECK-NEXT:    [[BO1:%.*]] = mul nuw i8 [[X]], 12
-; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    [[R:%.*]] = mul nuw i8 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %BO0 = mul i8 %X, 3
@@ -70,9 +65,7 @@
 
 define <2 x i8> @urem_CY_CZ_is_BO0_with_nsw_out(<2 x i8> %X) {
 ; CHECK-LABEL: @urem_CY_CZ_is_BO0_with_nsw_out(
-; CHECK-NEXT:    [[BO0:%.*]] = shl nsw <2 x i8> [[X:%.*]], <i8 2, i8 2>
-; CHECK-NEXT:    [[BO1:%.*]] = mul nuw <2 x i8> [[X]], <i8 12, i8 12>
-; CHECK-NEXT:    [[R:%.*]] = urem <2 x i8> [[BO0]], [[BO1]]
+; CHECK-NEXT:    [[R:%.*]] = shl nuw nsw <2 x i8> [[X:%.*]], <i8 2, i8 2>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %BO0 = shl nsw <2 x i8> %X, <i8 2, i8 2>
@@ -83,9 +76,7 @@
 
 define i8 @urem_CY_CZ_is_BO0_no_nsw_out(i8 %X) {
 ; CHECK-LABEL: @urem_CY_CZ_is_BO0_no_nsw_out(
-; CHECK-NEXT:    [[BO0:%.*]] = mul nuw i8 [[X:%.*]], 3
-; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[X]], 3
-; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    [[R:%.*]] = mul nuw i8 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %BO0 = mul nuw i8 %X, 3
@@ -109,9 +100,7 @@
 
 define i8 @urem_CY_CZ_is_mul_X_RemYZ(i8 %X) {
 ; CHECK-LABEL: @urem_CY_CZ_is_mul_X_RemYZ(
-; CHECK-NEXT:    [[BO0:%.*]] = mul nuw i8 [[X:%.*]], 21
-; CHECK-NEXT:    [[BO1:%.*]] = mul i8 [[X]], 6
-; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    [[R:%.*]] = mul nuw nsw i8 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %BO0 = mul nuw i8 %X, 21
@@ -229,10 +218,7 @@
 ;; Signed Verions
 define i8 @srem_CY_CZ_is_zero(i8 %X) {
 ; CHECK-LABEL: @srem_CY_CZ_is_zero(
-; CHECK-NEXT:    [[BO0:%.*]] = mul nsw i8 [[X:%.*]], 9
-; CHECK-NEXT:    [[BO1:%.*]] = mul i8 [[X]], 3
-; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 0
 ;
   %BO0 = mul nsw i8 %X, 9
   %BO1 = mul i8 %X, 3
@@ -255,9 +241,7 @@
 
 define <2 x i8> @srem_CY_CZ_is_BO0(<2 x i8> %X) {
 ; CHECK-LABEL: @srem_CY_CZ_is_BO0(
-; CHECK-NEXT:    [[BO0:%.*]] = shl <2 x i8> [[X:%.*]], <i8 3, i8 3>
-; CHECK-NEXT:    [[BO1:%.*]] = mul nsw <2 x i8> [[X]], <i8 15, i8 15>
-; CHECK-NEXT:    [[R:%.*]] = srem <2 x i8> [[BO0]], [[BO1]]
+; CHECK-NEXT:    [[R:%.*]] = shl nsw <2 x i8> [[X:%.*]], <i8 3, i8 3>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %BO0 = shl <2 x i8> %X, <i8 3, i8 3>
@@ -268,9 +252,7 @@
 
 define i8 @srem_CY_CZ_is_BO0_with_nuw_out(i8 %X) {
 ; CHECK-LABEL: @srem_CY_CZ_is_BO0_with_nuw_out(
-; CHECK-NEXT:    [[BO0:%.*]] = mul nuw i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[BO1:%.*]] = mul nsw i8 [[X]], 15
-; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    [[R:%.*]] = mul nuw nsw i8 [[X:%.*]], 5
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %BO0 = mul nuw i8 %X, 5
@@ -281,9 +263,7 @@
 
 define i8 @srem_CY_CZ_is_BO0_no_nsw_out(i8 %X) {
 ; CHECK-LABEL: @srem_CY_CZ_is_BO0_no_nsw_out(
-; CHECK-NEXT:    [[BO0:%.*]] = mul nsw i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[X]], 4
-; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    [[R:%.*]] = mul nsw i8 [[X:%.*]], 5
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %BO0 = mul nsw i8 %X, 5
@@ -307,9 +287,7 @@
 
 define i8 @srem_CY_CZ_is_mul_X_RemYZ(i8 %X) {
 ; CHECK-LABEL: @srem_CY_CZ_is_mul_X_RemYZ(
-; CHECK-NEXT:    [[BO0:%.*]] = shl nsw i8 [[X:%.*]], 3
-; CHECK-NEXT:    [[BO1:%.*]] = mul nsw i8 [[X]], 6
-; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    [[R:%.*]] = shl nsw i8 [[X:%.*]], 1
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %BO0 = shl nsw i8 %X, 3
@@ -320,9 +298,7 @@
 
 define i8 @srem_CY_CZ_is_mul_X_RemYZ_with_nuw_out(i8 %X) {
 ; CHECK-LABEL: @srem_CY_CZ_is_mul_X_RemYZ_with_nuw_out(
-; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], 10
-; CHECK-NEXT:    [[BO1:%.*]] = mul nsw i8 [[X]], 6
-; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    [[R:%.*]] = shl nuw nsw i8 [[X:%.*]], 2
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %BO0 = mul nsw nuw i8 %X, 10
@@ -333,9 +309,7 @@
 
 define <2 x i8> @srem_CY_CZ_is_mul_X_RemYZ_no_nuw_out(<2 x i8> %X) {
 ; CHECK-LABEL: @srem_CY_CZ_is_mul_X_RemYZ_no_nuw_out(
-; CHECK-NEXT:    [[BO0:%.*]] = mul nsw <2 x i8> [[X:%.*]], <i8 10, i8 10>
-; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw <2 x i8> [[X]], <i8 3, i8 3>
-; CHECK-NEXT:    [[R:%.*]] = srem <2 x i8> [[BO0]], [[BO1]]
+; CHECK-NEXT:    [[R:%.*]] = shl nsw <2 x i8> [[X:%.*]], <i8 1, i8 1>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %BO0 = mul nsw <2 x i8> %X, <i8 10, i8 10>