rem-mul-shl.ll

; 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:    ret <vscale x 16 x i8> zeroinitializer
;
  %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:    ret i8 0
;
  %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:    [[R:%.*]] = mul nuw i8 [[X:%.*]], 3
; 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:    [[R:%.*]] = mul nuw nsw i8 [[X:%.*]], 3
; 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:    ret <vscale x 16 x i8> zeroinitializer
;
  %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:    ret i8 0
;
  %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:    [[R:%.*]] = mul nuw nsw i8 [[X:%.*]], 5
; 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:    [[R:%.*]] = shl nuw nsw i8 [[X:%.*]], 2
; 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
}