; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -passes=instcombine -S | FileCheck %s

declare void @use(i32)

define i64 @match_unsigned(i64 %x) {
; CHECK-LABEL: @match_unsigned(
; CHECK-NEXT:    [[UREM:%.*]] = urem i64 [[X:%.*]], 19136
; CHECK-NEXT:    ret i64 [[UREM]]
;
  %t = urem i64 %x, 299
  %t1 = udiv i64 %x, 299
  %t2 = urem i64 %t1, 64
  %t3 = mul i64 %t2, 299
  %t4 = add i64 %t, %t3
  ret i64 %t4
}

define <2 x i64> @match_unsigned_vector(<2 x i64> %x) {
; CHECK-LABEL: @match_unsigned_vector(
; CHECK-NEXT:  bb:
; CHECK-NEXT:    [[UREM:%.*]] = urem <2 x i64> [[X:%.*]], splat (i64 19136)
; CHECK-NEXT:    ret <2 x i64> [[UREM]]
;
bb:
  %tmp = urem <2 x i64> %x, <i64 299, i64 299>
  %tmp1 = udiv <2 x i64> %x, <i64 299, i64 299>
  %tmp2 = urem <2 x i64> %tmp1, <i64 64, i64 64>
  %tmp3 = mul <2 x i64> %tmp2, <i64 299, i64 299>
  %tmp4 = add <2 x i64> %tmp, %tmp3
  ret <2 x i64> %tmp4
}
define i64 @match_andAsRem_lshrAsDiv_shlAsMul(i64 %x) {
; CHECK-LABEL: @match_andAsRem_lshrAsDiv_shlAsMul(
; CHECK-NEXT:    [[UREM:%.*]] = urem i64 [[X:%.*]], 576
; CHECK-NEXT:    ret i64 [[UREM]]
;
  %t = and i64 %x, 63
  %t1 = lshr i64 %x, 6
  %t2 = urem i64 %t1, 9
  %t3 = shl i64 %t2, 6
  %t4 = add i64 %t, %t3
  ret i64 %t4
}

define i64 @match_signed(i64 %x) {
; CHECK-LABEL: @match_signed(
; CHECK-NEXT:    [[SREM1:%.*]] = srem i64 [[X:%.*]], 172224
; CHECK-NEXT:    ret i64 [[SREM1]]
;
  %t = srem i64 %x, 299
  %t1 = sdiv i64 %x, 299
  %t2 = srem i64 %t1, 64
  %t3 = sdiv i64 %x, 19136
  %t4 = srem i64 %t3, 9
  %t5 = mul i64 %t2, 299
  %t6 = add i64 %t, %t5
  %t7 = mul i64 %t4, 19136
  %t8 = add i64 %t6, %t7
  ret i64 %t8
}

define <2 x i64> @match_signed_vector(<2 x i64> %x) {
; CHECK-LABEL: @match_signed_vector(
; CHECK-NEXT:  bb:
; CHECK-NEXT:    [[SREM1:%.*]] = srem <2 x i64> [[X:%.*]], splat (i64 172224)
; CHECK-NEXT:    ret <2 x i64> [[SREM1]]
;
bb:
  %tmp = srem <2 x i64> %x, <i64 299, i64 299>
  %tmp1 = sdiv <2 x i64> %x, <i64 299, i64 299>
  %tmp2 = srem <2 x i64> %tmp1, <i64 64, i64 64>
  %tmp3 = sdiv <2 x i64> %x, <i64 19136, i64 19136>
  %tmp4 = srem <2 x i64> %tmp3, <i64 9, i64 9>
  %tmp5 = mul <2 x i64> %tmp2, <i64 299, i64 299>
  %tmp6 = add <2 x i64> %tmp, %tmp5
  %tmp7 = mul <2 x i64> %tmp4, <i64 19136, i64 19136>
  %tmp8 = add <2 x i64> %tmp6, %tmp7
  ret <2 x i64> %tmp8
}

define i64 @not_match_inconsistent_signs(i64 %x) {
; CHECK-LABEL: @not_match_inconsistent_signs(
; CHECK-NEXT:    [[T:%.*]] = urem i64 [[X:%.*]], 299
; CHECK-NEXT:    [[T1:%.*]] = sdiv i64 [[X]], 299
; CHECK-NEXT:    [[T2:%.*]] = and i64 [[T1]], 63
; CHECK-NEXT:    [[T3:%.*]] = mul nuw nsw i64 [[T2]], 299
; CHECK-NEXT:    [[T4:%.*]] = add nuw nsw i64 [[T]], [[T3]]
; CHECK-NEXT:    ret i64 [[T4]]
;
  %t = urem i64 %x, 299
  %t1 = sdiv i64 %x, 299
  %t2 = urem i64 %t1, 64
  %t3 = mul i64 %t2, 299
  %t4 = add i64 %t, %t3
  ret i64 %t4
}

define i64 @not_match_inconsistent_values(i64 %x) {
; CHECK-LABEL: @not_match_inconsistent_values(
; CHECK-NEXT:    [[T:%.*]] = urem i64 [[X:%.*]], 299
; CHECK-NEXT:    [[T1:%.*]] = udiv i64 [[X]], 29
; CHECK-NEXT:    [[T2:%.*]] = and i64 [[T1]], 63
; CHECK-NEXT:    [[T3:%.*]] = mul nuw nsw i64 [[T2]], 299
; CHECK-NEXT:    [[T4:%.*]] = add nuw nsw i64 [[T]], [[T3]]
; CHECK-NEXT:    ret i64 [[T4]]
;
  %t = urem i64 %x, 299
  %t1 = udiv i64 %x, 29
  %t2 = urem i64 %t1, 64
  %t3 = mul i64 %t2, 299
  %t4 = add i64 %t, %t3
  ret i64 %t4
}

define i32 @not_match_overflow(i32 %x) {
; CHECK-LABEL: @not_match_overflow(
; CHECK-NEXT:    [[X_FR:%.*]] = freeze i32 [[X:%.*]]
; CHECK-NEXT:    [[T:%.*]] = urem i32 [[X_FR]], 299
; CHECK-NEXT:    [[TMP1:%.*]] = urem i32 [[X_FR]], 299
; CHECK-NEXT:    [[T3:%.*]] = sub nuw i32 [[X_FR]], [[TMP1]]
; CHECK-NEXT:    [[T4:%.*]] = add i32 [[T]], [[T3]]
; CHECK-NEXT:    ret i32 [[T4]]
;
  %t = urem i32 %x, 299
  %t1 = udiv i32 %x, 299
  %t2 = urem i32 %t1, 147483647
  %t3 = mul i32 %t2, 299
  %t4 = add i32 %t, %t3
  ret i32 %t4
}

; Tests from PR76128.
define i32 @fold_add_udiv_urem(i32 noundef %val) {
; CHECK-LABEL: @fold_add_udiv_urem(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10
; CHECK-NEXT:    [[TMP0:%.*]] = mul nuw i32 [[DIV]], 6
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[TMP0]], [[VAL]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
entry:
  %div = udiv i32 %val, 10
  %shl = shl i32 %div, 4
  %rem = urem i32 %val, 10
  %add = add i32 %shl, %rem
  ret i32 %add
}
define i32 @fold_add_sdiv_srem(i32 noundef %val) {
; CHECK-LABEL: @fold_add_sdiv_srem(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[VAL:%.*]], 10
; CHECK-NEXT:    [[TMP0:%.*]] = mul nsw i32 [[DIV]], 6
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[TMP0]], [[VAL]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
entry:
  %div = sdiv i32 %val, 10
  %shl = shl i32 %div, 4
  %rem = srem i32 %val, 10
  %add = add i32 %shl, %rem
  ret i32 %add
}
define i32 @fold_add_udiv_urem_to_mul(i32 noundef %val) {
; CHECK-LABEL: @fold_add_udiv_urem_to_mul(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[ADD:%.*]] = mul i32 [[VAL:%.*]], 3
; CHECK-NEXT:    ret i32 [[ADD]]
;
entry:
  %div = udiv i32 %val, 7
  %mul1 = mul i32 %div, 21
  %rem = urem i32 %val, 7
  %mul2 = mul i32 %rem, 3
  %add = add i32 %mul1, %mul2
  ret i32 %add
}
define i32 @fold_add_udiv_urem_to_mul_multiuse(i32 noundef %val) {
; CHECK-LABEL: @fold_add_udiv_urem_to_mul_multiuse(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[VAL:%.*]], 7
; CHECK-NEXT:    call void @use(i32 [[REM]])
; CHECK-NEXT:    [[ADD:%.*]] = mul i32 [[VAL]], 3
; CHECK-NEXT:    ret i32 [[ADD]]
;
entry:
  %div = udiv i32 %val, 7
  %mul1 = mul i32 %div, 21
  %rem = urem i32 %val, 7
  call void @use(i32 %rem)
  %mul2 = mul i32 %rem, 3
  %add = add i32 %mul1, %mul2
  ret i32 %add
}
define i32 @fold_add_udiv_urem_commuted(i32 noundef %val) {
; CHECK-LABEL: @fold_add_udiv_urem_commuted(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10
; CHECK-NEXT:    [[TMP0:%.*]] = mul nuw i32 [[DIV]], 6
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[TMP0]], [[VAL]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
entry:
  %div = udiv i32 %val, 10
  %shl = shl i32 %div, 4
  %rem = urem i32 %val, 10
  %add = add i32 %rem, %shl
  ret i32 %add
}
define i32 @fold_add_udiv_urem_or_disjoint(i32 noundef %val) {
; CHECK-LABEL: @fold_add_udiv_urem_or_disjoint(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10
; CHECK-NEXT:    [[TMP0:%.*]] = mul nuw i32 [[DIV]], 6
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[TMP0]], [[VAL]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
entry:
  %div = udiv i32 %val, 10
  %shl = shl i32 %div, 4
  %rem = urem i32 %val, 10
  %add = or disjoint i32 %shl, %rem
  ret i32 %add
}
; Negative tests
define i32 @fold_add_udiv_urem_without_noundef(i32 %val) {
; CHECK-LABEL: @fold_add_udiv_urem_without_noundef(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10
; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[DIV]], 4
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[VAL]], 10
; CHECK-NEXT:    [[ADD:%.*]] = or disjoint i32 [[SHL]], [[REM]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
entry:
  %div = udiv i32 %val, 10
  %shl = shl i32 %div, 4
  %rem = urem i32 %val, 10
  %add = add i32 %shl, %rem
  ret i32 %add
}
define i32 @fold_add_udiv_urem_multiuse_mul(i32 noundef %val) {
; CHECK-LABEL: @fold_add_udiv_urem_multiuse_mul(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10
; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[DIV]], 4
; CHECK-NEXT:    call void @use(i32 [[SHL]])
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[VAL]], 10
; CHECK-NEXT:    [[ADD:%.*]] = or disjoint i32 [[SHL]], [[REM]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
entry:
  %div = udiv i32 %val, 10
  %shl = shl i32 %div, 4
  call void @use(i32 %shl)
  %rem = urem i32 %val, 10
  %add = add i32 %shl, %rem
  ret i32 %add
}
define i32 @fold_add_udiv_srem(i32 noundef %val) {
; CHECK-LABEL: @fold_add_udiv_srem(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10
; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[DIV]], 4
; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[VAL]], 10
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[SHL]], [[REM]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
entry:
  %div = udiv i32 %val, 10
  %shl = shl i32 %div, 4
  %rem = srem i32 %val, 10
  %add = add i32 %shl, %rem
  ret i32 %add
}
define i32 @fold_add_udiv_urem_non_constant(i32 noundef %val, i32 noundef %c) {
; CHECK-LABEL: @fold_add_udiv_urem_non_constant(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[VAL:%.*]], [[C:%.*]]
; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[DIV]], 4
; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[VAL]], [[C]]
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[SHL]], [[REM]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
entry:
  %div = udiv i32 %val, %c
  %shl = shl i32 %div, 4
  %rem = urem i32 %val, %c
  %add = add i32 %shl, %rem
  ret i32 %add
}

define i32 @fold_add_udiv_urem_no_mul(i32 noundef %val) {
; CHECK-LABEL: @fold_add_udiv_urem_no_mul(
; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10
; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[DIV]], -9
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[TMP1]], [[VAL]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
  %div = udiv i32 %val, 10
  %rem = urem i32 %val, 10
  %add = add i32 %div, %rem
  ret i32 %add
}

define i32 @fold_add_udiv_urem_rem_mul(i32 noundef %val) {
; CHECK-LABEL: @fold_add_udiv_urem_rem_mul(
; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[VAL:%.*]], 10
; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[VAL]], 3
; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[DIV]], -29
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[TMP2]], [[TMP1]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
  %div = udiv i32 %val, 10
  %rem = urem i32 %val, 10
  %mul = mul i32 %rem, 3
  %add = add i32 %div, %mul
  ret i32 %add
}

define i32 @fold_add_udiv_urem_pow2_no_mul(i32 noundef %arg) {
; CHECK-LABEL: @fold_add_udiv_urem_pow2_no_mul(
; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[ARG:%.*]], 4
; CHECK-NEXT:    [[AND:%.*]] = and i32 [[ARG]], 15
; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i32 [[LSHR]], [[AND]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
  %lshr = lshr i32 %arg, 4
  %and = and i32 %arg, 15
  %add = add i32 %lshr, %and
  ret i32 %add
}

define i32 @fold_add_udiv_urem_pow2_div_mul(i32 noundef %arg) {
; CHECK-LABEL: @fold_add_udiv_urem_pow2_div_mul(
; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[ARG:%.*]], 4
; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[LSHR]], -13
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[TMP1]], [[ARG]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
  %lshr = lshr i32 %arg, 4
  %mul = mul i32 %lshr, 3
  %and = and i32 %arg, 15
  %add = add i32 %mul, %and
  ret i32 %add
}

define i32 @fold_add_sdiv_srem_no_mul(i32 noundef %val) {
; CHECK-LABEL: @fold_add_sdiv_srem_no_mul(
; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[VAL:%.*]], 10
; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[DIV]], -9
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[TMP1]], [[VAL]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
  %div = sdiv i32 %val, 10
  %rem = srem i32 %val, 10
  %add = add i32 %div, %rem
  ret i32 %add
}

define i32 @fold_add_udiv_urem_pow2_rem_mul(i32 noundef %arg) {
; CHECK-LABEL: @fold_add_udiv_urem_pow2_rem_mul(
; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[ARG:%.*]], 4
; CHECK-NEXT:    [[AND:%.*]] = and i32 [[ARG]], 15
; CHECK-NEXT:    [[MUL:%.*]] = mul nuw nsw i32 [[AND]], 3
; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i32 [[LSHR]], [[MUL]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
  %lshr = lshr i32 %arg, 4
  %and = and i32 %arg, 15
  %mul = mul i32 %and, 3
  %add = add i32 %lshr, %mul
  ret i32 %add
}

define i32 @fold_add_udiv_urem_pow2_both_mul(i32 noundef %arg) {
; CHECK-LABEL: @fold_add_udiv_urem_pow2_both_mul(
; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[ARG:%.*]], 4
; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[ARG]], 3
; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[LSHR]], -41
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[TMP2]], [[TMP1]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
  %lshr = lshr i32 %arg, 4
  %mul1 = mul i32 %lshr, 7
  %and = and i32 %arg, 15
  %mul2 = mul i32 %and, 3
  %add = add i32 %mul1, %mul2
  ret i32 %add
}

define i32 @fold_add_udiv_urem_by_two_no_mul(i32 noundef %arg) {
; CHECK-LABEL: @fold_add_udiv_urem_by_two_no_mul(
; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[ARG:%.*]], 1
; CHECK-NEXT:    [[ADD:%.*]] = sub i32 [[ARG]], [[LSHR]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
  %lshr = lshr i32 %arg, 1
  %and = and i32 %arg, 1
  %add = add i32 %lshr, %and
  ret i32 %add
}

define i32 @fold_add_sdiv_srem_by_two_no_mul(i32 noundef %arg) {
; CHECK-LABEL: @fold_add_sdiv_srem_by_two_no_mul(
; CHECK-NEXT:    [[DIV_NEG:%.*]] = sdiv i32 [[ARG:%.*]], -2
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[DIV_NEG]], [[ARG]]
; CHECK-NEXT:    ret i32 [[ADD]]
;
  %div = sdiv i32 %arg, 2
  %rem = srem i32 %arg, 2
  %add = add i32 %div, %rem
  ret i32 %add
}