diff --git a/llvm/test/Transforms/InstCombine/rem-mul-shl.ll b/llvm/test/Transforms/InstCombine/rem-mul-shl.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/InstCombine/rem-mul-shl.ll
@@ -0,0 +1,827 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=instcombine -S | FileCheck %s
+declare void @use8(i8)
+
+define i8 @srem_non_matching(i8 %X, i8 %Y) {
+; CHECK-LABEL: @srem_non_matching(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], 15
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[Y:%.*]], 5
+; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nsw nuw i8 %X, 15
+  %BO1 = mul nsw nuw i8 %Y, 5
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_1_shl(i8 %X, i8 %Y) {
+; CHECK-LABEL: @urem_1_shl(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 1, [[X:%.*]]
+; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i8 -1, [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[NOTMASK]], -1
+; CHECK-NEXT:    [[R:%.*]] = and i8 [[BO0]], [[TMP1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nsw nuw i8 1, %X
+  %BO1 = shl nsw nuw i8 1, %Y
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define <vscale x 16 x i8> @urem_XY_XZ_with_CY_rem_CZ_eq_0_scalable(<vscale x 16 x i8> %X) {
+; CHECK-LABEL: @urem_XY_XZ_with_CY_rem_CZ_eq_0_scalable(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw <vscale x 16 x i8> [[X:%.*]], shufflevector (<vscale x 16 x i8> insertelement (<vscale x 16 x i8> poison, i8 15, i64 0), <vscale x 16 x i8> poison, <vscale x 16 x i32> zeroinitializer)
+; CHECK-NEXT:    [[BO1:%.*]] = mul <vscale x 16 x i8> [[X]], shufflevector (<vscale x 16 x i8> insertelement (<vscale x 16 x i8> poison, i8 5, i64 0), <vscale x 16 x i8> poison, <vscale x 16 x i32> zeroinitializer)
+; CHECK-NEXT:    [[R:%.*]] = urem <vscale x 16 x i8> [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret <vscale x 16 x i8> [[R]]
+;
+  %BO0 = mul nuw <vscale x 16 x i8> %X, shufflevector(<vscale x 16 x i8> insertelement(<vscale x 16 x i8> poison, i8 15, i64 0) , <vscale x 16 x i8> poison, <vscale x 16 x i32> zeroinitializer)
+  %BO1 = mul <vscale x 16 x i8> %X, shufflevector(<vscale x 16 x i8> insertelement(<vscale x 16 x i8> poison, i8 5, i64 0) , <vscale x 16 x i8> poison, <vscale x 16 x i32> zeroinitializer)
+  %r = urem <vscale x 16 x i8> %BO0, %BO1
+  ret <vscale x 16 x i8> %r
+}
+
+define i8 @urem_XY_XZ_with_CY_rem_CZ_eq_0(i8 %X) {
+; CHECK-LABEL: @urem_XY_XZ_with_CY_rem_CZ_eq_0(
+; 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]]
+;
+  %BO0 = mul nuw i8 %X, 15
+  %BO1 = mul i8 %X, 5
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_XY_XZ_with_CY_rem_CZ_eq_0_fail_missing_flag(i8 %X) {
+; CHECK-LABEL: @urem_XY_XZ_with_CY_rem_CZ_eq_0_fail_missing_flag(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nsw i8 [[X:%.*]], 15
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[X]], 5
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nsw i8 %X, 15
+  %BO1 = mul nsw nuw i8 %X, 5
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_XY_XZ_with_CY_lt_CZ(i8 %X) {
+; CHECK-LABEL: @urem_XY_XZ_with_CY_lt_CZ(
+; CHECK-NEXT:    [[BO0:%.*]] = mul i8 [[X:%.*]], 3
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw i8 [[X]], 12
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul i8 %X, 3
+  %BO1 = mul nuw i8 %X, 12
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define <2 x i8> @urem_XY_XZ_with_CY_lt_CZ_with_nsw_out(<2 x i8> %X) {
+; CHECK-LABEL: @urem_XY_XZ_with_CY_lt_CZ_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:    ret <2 x i8> [[R]]
+;
+  %BO0 = shl nsw <2 x i8> %X, <i8 2, i8 2>
+  %BO1 = mul nuw <2 x i8> %X, <i8 12, i8 12>
+  %r = urem <2 x i8> %BO0, %BO1
+  ret <2 x i8> %r
+}
+
+define i8 @urem_XY_XZ_with_CY_lt_CZ_no_nsw_out(i8 %X) {
+; CHECK-LABEL: @urem_XY_XZ_with_CY_lt_CZ_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:    ret i8 [[R]]
+;
+  %BO0 = mul nuw i8 %X, 3
+  %BO1 = shl nsw nuw i8 %X, 3
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_XY_XZ_with_CY_lt_CZ_fail_missing_flag(i8 %X) {
+; CHECK-LABEL: @urem_XY_XZ_with_CY_lt_CZ_fail_missing_flag(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], 3
+; CHECK-NEXT:    [[BO1:%.*]] = mul nsw i8 [[X]], 12
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw nsw i8 %X, 3
+  %BO1 = mul nsw i8 %X, 12
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_XY_XZ_with_CY_gt_CZ(i8 %X) {
+; CHECK-LABEL: @urem_XY_XZ_with_CY_gt_CZ(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw i8 [[X:%.*]], 21
+; CHECK-NEXT:    [[BO1:%.*]] = mul i8 [[X]], 6
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw i8 %X, 21
+  %BO1 = mul i8 %X, 6
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_XY_XZ_with_CY_gt_CZ_fail_missing_flag(i8 %X) {
+; CHECK-LABEL: @urem_XY_XZ_with_CY_gt_CZ_fail_missing_flag(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nsw i8 [[X:%.*]], 21
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[X]], 6
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nsw i8 %X, 21
+  %BO1 = mul nsw nuw i8 %X, 6
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_XY_XZ_with_Y_Z_is_mul_X_RemYZ(i8 %X, i8 %Y, i8 %Z) {
+; CHECK-LABEL: @urem_XY_XZ_with_Y_Z_is_mul_X_RemYZ(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw i8 [[Z:%.*]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw i8 %X, %Y
+  %BO1 = mul nuw i8 %Z, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_XY_XZ_with_CX_Y_Z_is_mul_X_RemYZ(i8 %Y, i8 %Z) {
+; CHECK-LABEL: @urem_XY_XZ_with_CX_Y_Z_is_mul_X_RemYZ(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw i8 [[Y:%.*]], 10
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw i8 10, [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw i8 10, %Y
+  %BO1 = shl nuw i8 10, %Z
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_with_nsw_out1(i8 %X, i8 %Y, i8 %Z) {
+; CHECK-LABEL: @urem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_with_nsw_out1(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw i8 [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw nsw i8 %X, %Y
+  %BO1 = shl nuw i8 %X, %Z
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define <2 x i8> @urem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_with_nsw_out2(<2 x i8> %X, <2 x i8> %Y, <2 x i8> %Z) {
+; CHECK-LABEL: @urem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_with_nsw_out2(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw <2 x i8> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw <2 x i8> [[Z:%.*]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem <2 x i8> [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret <2 x i8> [[R]]
+;
+  %BO0 = shl nuw <2 x i8> %Y, %X
+  %BO1 = shl nuw nsw <2 x i8> %Z, %X
+  %r = urem <2 x i8> %BO0, %BO1
+  ret <2 x i8> %r
+}
+
+define i8 @urem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_fail_reused1(i8 %X, i8 %Y, i8 %Z) {
+; CHECK-LABEL: @urem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_fail_reused1(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    call void @use8(i8 [[BO0]])
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nsw nuw i8 %X, %Y
+  %BO1 = mul nsw nuw i8 %X, %Z
+  %r = urem i8 %BO0, %BO1
+  call void @use8(i8 %BO0)
+  ret i8 %r
+}
+
+define <2 x i8> @urem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_fail_missing_flags1(<2 x i8> %X, <2 x i8> %Y, <2 x i8> %Z) {
+; CHECK-LABEL: @urem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_fail_missing_flags1(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nsw <2 x i8> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw <2 x i8> [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = urem <2 x i8> [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret <2 x i8> [[R]]
+;
+  %BO0 = mul nsw <2 x i8> %X, %Y
+  %BO1 = mul nsw nuw <2 x i8> %X, %Z
+  %r = urem <2 x i8> %BO0, %BO1
+  ret <2 x i8> %r
+}
+
+define i8 @urem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_fail_missing_flags2(i8 %X, i8 %Y, i8 %Z) {
+; CHECK-LABEL: @urem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_fail_missing_flags2(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nsw i8 [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nsw nuw i8 %X, %Y
+  %BO1 = shl nsw i8 %X, %Z
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+;; Signed Verions
+define <vscale x 16 x i8> @srem_XY_XZ_with_CY_rem_CZ_eq_0_scalable(<vscale x 16 x i8> %X) {
+; CHECK-LABEL: @srem_XY_XZ_with_CY_rem_CZ_eq_0_scalable(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nsw <vscale x 16 x i8> [[X:%.*]], shufflevector (<vscale x 16 x i8> insertelement (<vscale x 16 x i8> poison, i8 15, i64 0), <vscale x 16 x i8> poison, <vscale x 16 x i32> zeroinitializer)
+; CHECK-NEXT:    [[BO1:%.*]] = mul <vscale x 16 x i8> [[X]], shufflevector (<vscale x 16 x i8> insertelement (<vscale x 16 x i8> poison, i8 5, i64 0), <vscale x 16 x i8> poison, <vscale x 16 x i32> zeroinitializer)
+; CHECK-NEXT:    [[R:%.*]] = srem <vscale x 16 x i8> [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret <vscale x 16 x i8> [[R]]
+;
+  %BO0 = mul nsw <vscale x 16 x i8> %X, shufflevector(<vscale x 16 x i8> insertelement(<vscale x 16 x i8> poison, i8 15, i64 0) , <vscale x 16 x i8> poison, <vscale x 16 x i32> zeroinitializer)
+  %BO1 = mul <vscale x 16 x i8> %X, shufflevector(<vscale x 16 x i8> insertelement(<vscale x 16 x i8> poison, i8 5, i64 0) , <vscale x 16 x i8> poison, <vscale x 16 x i32> zeroinitializer)
+  %r = srem <vscale x 16 x i8> %BO0, %BO1
+  ret <vscale x 16 x i8> %r
+}
+
+define i8 @srem_XY_XZ_with_CY_rem_CZ_eq_0(i8 %X) {
+; CHECK-LABEL: @srem_XY_XZ_with_CY_rem_CZ_eq_0(
+; 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]]
+;
+  %BO0 = mul nsw i8 %X, 9
+  %BO1 = mul i8 %X, 3
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @srem_XY_XZ_with_CY_rem_CZ_eq_0_fail_missing_flag(i8 %X) {
+; CHECK-LABEL: @srem_XY_XZ_with_CY_rem_CZ_eq_0_fail_missing_flag(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw i8 [[X:%.*]], 9
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[X]], 3
+; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw i8 %X, 9
+  %BO1 = mul nsw nuw i8 %X, 3
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define <2 x i8> @srem_XY_XZ_with_CY_lt_CZ(<2 x i8> %X) {
+; CHECK-LABEL: @srem_XY_XZ_with_CY_lt_CZ(
+; 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:    ret <2 x i8> [[R]]
+;
+  %BO0 = shl <2 x i8> %X, <i8 3, i8 3>
+  %BO1 = mul nsw <2 x i8> %X, <i8 15, i8 15>
+  %r = srem <2 x i8> %BO0, %BO1
+  ret <2 x i8> %r
+}
+
+define i8 @srem_XY_XZ_with_CY_lt_CZ_with_nuw_out(i8 %X) {
+; CHECK-LABEL: @srem_XY_XZ_with_CY_lt_CZ_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:    ret i8 [[R]]
+;
+  %BO0 = mul nuw i8 %X, 5
+  %BO1 = mul nsw i8 %X, 15
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @srem_XY_XZ_with_CY_lt_CZ_no_nsw_out(i8 %X) {
+; CHECK-LABEL: @srem_XY_XZ_with_CY_lt_CZ_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:    ret i8 [[R]]
+;
+  %BO0 = mul nsw i8 %X, 5
+  %BO1 = shl nsw nuw i8 %X, 4
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @srem_XY_XZ_with_CY_lt_CZ_fail_missing_flag(i8 %X) {
+; CHECK-LABEL: @srem_XY_XZ_with_CY_lt_CZ_fail_missing_flag(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], 5
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw i8 [[X]], 4
+; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw nsw i8 %X, 5
+  %BO1 = shl nuw i8 %X, 4
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @srem_XY_XZ_with_CY_gt_CZ(i8 %X) {
+; CHECK-LABEL: @srem_XY_XZ_with_CY_gt_CZ(
+; 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:    ret i8 [[R]]
+;
+  %BO0 = shl nsw i8 %X, 3
+  %BO1 = mul nsw i8 %X, 6
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @srem_XY_XZ_with_CY_gt_CZ_with_nuw_out(i8 %X) {
+; CHECK-LABEL: @srem_XY_XZ_with_CY_gt_CZ_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:    ret i8 [[R]]
+;
+  %BO0 = mul nsw nuw i8 %X, 10
+  %BO1 = mul nsw i8 %X, 6
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define <2 x i8> @srem_XY_XZ_with_CY_gt_CZ_no_nuw_out(<2 x i8> %X) {
+; CHECK-LABEL: @srem_XY_XZ_with_CY_gt_CZ_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:    ret <2 x i8> [[R]]
+;
+  %BO0 = mul nsw <2 x i8> %X, <i8 10, i8 10>
+  %BO1 = shl nsw nuw <2 x i8> %X, <i8 3, i8 3>
+  %r = srem <2 x i8> %BO0, %BO1
+  ret <2 x i8> %r
+}
+
+define i8 @srem_XY_XZ_with_CY_gt_CZ_fail_missing_flag1(i8 %X) {
+; CHECK-LABEL: @srem_XY_XZ_with_CY_gt_CZ_fail_missing_flag1(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], 10
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw i8 [[X]], 6
+; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nsw nuw i8 %X, 10
+  %BO1 = mul nuw i8 %X, 6
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @srem_XY_XZ_with_CY_gt_CZ_fail_missing_flag2(i8 %X) {
+; CHECK-LABEL: @srem_XY_XZ_with_CY_gt_CZ_fail_missing_flag2(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw i8 [[X:%.*]], 4
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[X]], 5
+; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw i8 %X, 4
+  %BO1 = mul nsw nuw i8 %X, 5
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @srem_XY_XZ_with_Y_Z_is_mul_X_RemYZ(i8 %X, i8 %Y, i8 %Z) {
+; CHECK-LABEL: @srem_XY_XZ_with_Y_Z_is_mul_X_RemYZ(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nsw i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nsw i8 %Y, %X
+  %BO1 = mul nsw nuw i8 %X, %Z
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @srem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_with_nuw_out(i8 %X, i8 %Y, i8 %Z) {
+; CHECK-LABEL: @srem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_with_nuw_out(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[Z:%.*]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nsw nuw i8 %Y, %X
+  %BO1 = mul nsw nuw i8 %Z, %X
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @srem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_fail_shl(i8 %X, i8 %Y, i8 %Z) {
+; CHECK-LABEL: @srem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_fail_shl(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nsw nuw i8 %X, %Y
+  %BO1 = shl nsw nuw i8 %X, %Z
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+
+define i8 @srem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_fail_missing_flags1(i8 %X, i8 %Y, i8 %Z) {
+; CHECK-LABEL: @srem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_fail_missing_flags1(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw i8 %X, %Y
+  %BO1 = mul nsw nuw i8 %X, %Z
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @srem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_fail_missing_flags2(i8 %X, i8 %Y, i8 %Z) {
+; CHECK-LABEL: @srem_XY_XZ_with_Y_Z_is_mul_X_RemYZ_fail_missing_flags2(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw i8 [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = srem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nsw nuw i8 %X, %Y
+  %BO1 = mul nuw i8 %X, %Z
+  %r = srem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_XY_shl_ZX_fail(i8 %X, i8 %Z, i8 %Y) {
+; CHECK-LABEL: @urem_shl_XY_shl_ZX_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[Z:%.*]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %X, %Y
+  %BO1 = shl nuw nsw i8 %Z, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_mul_XY_shl_ZX_fail(i8 %X, i8 %Z, i8 %Y) {
+; CHECK-LABEL: @urem_mul_XY_shl_ZX_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[Z:%.*]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw nsw i8 %X, %Y
+  %BO1 = shl nuw nsw i8 %Z, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_YX_shl_XZ_fail(i8 %X, i8 %Z, i8 %Y) {
+; CHECK-LABEL: @urem_shl_YX_shl_XZ_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %Y, %X
+  %BO1 = shl nuw nsw i8 %X, %Z
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_YX_mul_XZ_fail(i8 %X, i8 %Z, i8 %Y) {
+; CHECK-LABEL: @urem_shl_YX_mul_XZ_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %Y, %X
+  %BO1 = mul nuw nsw i8 %X, %Z
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_YX_mul_ZX_fail(i8 %X, i8 %Z, i8 %Y) {
+; CHECK-LABEL: @urem_shl_YX_mul_ZX_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[Z:%.*]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %Y, %X
+  %BO1 = mul nuw nsw i8 %Z, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_mul_YX_shl_ZX_fail(i8 %X, i8 %Z, i8 %Y) {
+; CHECK-LABEL: @urem_mul_YX_shl_ZX_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[Z:%.*]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw nsw i8 %Y, %X
+  %BO1 = shl nuw nsw i8 %Z, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_CXY_shl_ZCX_fail(i8 %Z, i8 %Y) {
+; CHECK-LABEL: @urem_shl_CXY_shl_ZCX_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 3, [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[Z:%.*]], 3
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 3, %Y
+  %BO1 = shl nuw nsw i8 %Z, 3
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_YCX_shl_CXZ_fail(i8 %Z, i8 %Y) {
+; CHECK-LABEL: @urem_shl_YCX_shl_CXZ_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[Y:%.*]], 3
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 3, [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %Y, 3
+  %BO1 = shl nuw nsw i8 3, %Z
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_YCX_mul_ZCX_fail(i8 %Z, i8 %Y) {
+; CHECK-LABEL: @urem_shl_YCX_mul_ZCX_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[Y:%.*]], 3
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[Z:%.*]], 10
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %Y, 3
+  %BO1 = mul nuw nsw i8 %Z, 10
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_mul_YCX_shl_ZCX_fail(i8 %Z, i8 %Y) {
+; CHECK-LABEL: @urem_mul_YCX_shl_ZCX_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[Y:%.*]], 3
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[Z:%.*]], 3
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw nsw i8 %Y, 3
+  %BO1 = shl nuw nsw i8 %Z, 3
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_XCY_shl_CZX_fail(i8 %X) {
+; CHECK-LABEL: @urem_shl_XCY_shl_CZX_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[X:%.*]], 3
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 6, [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %X, 3
+  %BO1 = shl nuw nsw i8 6, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_mul_XCY_shl_CZX_fail(i8 %X) {
+; CHECK-LABEL: @urem_mul_XCY_shl_CZX_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], 6
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 3, [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw nsw i8 %X, 6
+  %BO1 = shl nuw nsw i8 3, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_CYX_shl_XCZ_fail(i8 %X) {
+; CHECK-LABEL: @urem_shl_CYX_shl_XCZ_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 3, [[X:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[X]], 6
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 3, %X
+  %BO1 = shl nuw nsw i8 %X, 6
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_CYX_mul_XCZ_fail(i8 %X) {
+; CHECK-LABEL: @urem_shl_CYX_mul_XCZ_fail(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 3, [[X:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[X]], 10
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 3, %X
+  %BO1 = mul nuw nsw i8 %X, 10
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_XX_shl_ZX(i8 %X, i8 %Z) {
+; CHECK-LABEL: @urem_shl_XX_shl_ZX(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[X:%.*]], [[X]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[Z:%.*]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %X, %X
+  %BO1 = shl nuw nsw i8 %Z, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_YX_shl_XX(i8 %X, i8 %Y) {
+; CHECK-LABEL: @urem_shl_YX_shl_XX(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[X]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %Y, %X
+  %BO1 = shl nuw nsw i8 %X, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_XX_shl_XZ(i8 %X, i8 %Z) {
+; CHECK-LABEL: @urem_shl_XX_shl_XZ(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[X:%.*]], [[X]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %X, %X
+  %BO1 = shl nuw nsw i8 %X, %Z
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_XY_shl_XX(i8 %X, i8 %Y) {
+; CHECK-LABEL: @urem_shl_XY_shl_XX(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[X]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %X, %Y
+  %BO1 = shl nuw nsw i8 %X, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_mul_XX_shl_ZX(i8 %X, i8 %Z) {
+; CHECK-LABEL: @urem_mul_XX_shl_ZX(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], [[X]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[Z:%.*]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw nsw i8 %X, %X
+  %BO1 = shl nuw nsw i8 %Z, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_mul_YX_shl_XX(i8 %X, i8 %Y) {
+; CHECK-LABEL: @urem_mul_YX_shl_XX(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[X]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw nsw i8 %Y, %X
+  %BO1 = shl nuw nsw i8 %X, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_mul_XX_shl_XZ(i8 %X, i8 %Z) {
+; CHECK-LABEL: @urem_mul_XX_shl_XZ(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], [[X]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw nsw i8 %X, %X
+  %BO1 = shl nuw nsw i8 %X, %Z
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_mul_XY_shl_XX(i8 %X, i8 %Y) {
+; CHECK-LABEL: @urem_mul_XY_shl_XX(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[X]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw nsw i8 %X, %Y
+  %BO1 = shl nuw nsw i8 %X, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_XX_mul_ZX(i8 %X, i8 %Z) {
+; CHECK-LABEL: @urem_shl_XX_mul_ZX(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[X:%.*]], [[X]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[Z:%.*]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %X, %X
+  %BO1 = mul nuw nsw i8 %Z, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_YX_mul_XX(i8 %X, i8 %Y) {
+; CHECK-LABEL: @urem_shl_YX_mul_XX(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[X]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %Y, %X
+  %BO1 = mul nuw nsw i8 %X, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_XX_mul_XZ(i8 %X, i8 %Z) {
+; CHECK-LABEL: @urem_shl_XX_mul_XZ(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[X:%.*]], [[X]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[X]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %X, %X
+  %BO1 = mul nuw nsw i8 %X, %Z
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_XY_mul_XX(i8 %X, i8 %Y) {
+; CHECK-LABEL: @urem_shl_XY_mul_XX(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[X]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %X, %Y
+  %BO1 = mul nuw nsw i8 %X, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_mul_XX_shl_XX(i8 %X) {
+; CHECK-LABEL: @urem_mul_XX_shl_XX(
+; CHECK-NEXT:    [[BO0:%.*]] = mul nuw nsw i8 [[X:%.*]], [[X]]
+; CHECK-NEXT:    [[BO1:%.*]] = shl nuw nsw i8 [[X]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = mul nuw nsw i8 %X, %X
+  %BO1 = shl nuw nsw i8 %X, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}
+
+define i8 @urem_shl_XX_mul_XX(i8 %X) {
+; CHECK-LABEL: @urem_shl_XX_mul_XX(
+; CHECK-NEXT:    [[BO0:%.*]] = shl nuw nsw i8 [[X:%.*]], [[X]]
+; CHECK-NEXT:    [[BO1:%.*]] = mul nuw nsw i8 [[X]], [[X]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[BO0]], [[BO1]]
+; CHECK-NEXT:    ret i8 [[R]]
+;
+  %BO0 = shl nuw nsw i8 %X, %X
+  %BO1 = mul nuw nsw i8 %X, %X
+  %r = urem i8 %BO0, %BO1
+  ret i8 %r
+}