; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; This test makes sure that these instructions are properly eliminated.
;
; RUN: opt < %s -passes=instcombine -S | FileCheck %s

declare void @use(i8)

define i32 @shl_C1_add_A_C2_i32(i16 %A) {
; CHECK-LABEL: @shl_C1_add_A_C2_i32(
; CHECK-NEXT:    [[B:%.*]] = zext i16 [[A:%.*]] to i32
; CHECK-NEXT:    [[D:%.*]] = shl i32 192, [[B]]
; CHECK-NEXT:    ret i32 [[D]]
;
  %B = zext i16 %A to i32
  %C = add i32 %B, 5
  %D = shl i32 6, %C
  ret i32 %D
}

define i32 @ashr_C1_add_A_C2_i32(i32 %A) {
; CHECK-LABEL: @ashr_C1_add_A_C2_i32(
; CHECK-NEXT:    ret i32 0
;
  %B = and i32 %A, 65535
  %C = add i32 %B, 5
  %D = ashr i32 6, %C
  ret i32 %D
}

define i32 @lshr_C1_add_A_C2_i32(i32 %A) {
; CHECK-LABEL: @lshr_C1_add_A_C2_i32(
; CHECK-NEXT:    [[B:%.*]] = and i32 [[A:%.*]], 65535
; CHECK-NEXT:    [[D:%.*]] = shl i32 192, [[B]]
; CHECK-NEXT:    ret i32 [[D]]
;
  %B = and i32 %A, 65535
  %C = add i32 %B, 5
  %D = shl i32 6, %C
  ret i32 %D
}

define <4 x i32> @shl_C1_add_A_C2_v4i32(<4 x i16> %A) {
; CHECK-LABEL: @shl_C1_add_A_C2_v4i32(
; CHECK-NEXT:    [[B:%.*]] = zext <4 x i16> [[A:%.*]] to <4 x i32>
; CHECK-NEXT:    [[D:%.*]] = shl <4 x i32> <i32 6, i32 4, i32 poison, i32 -458752>, [[B]]
; CHECK-NEXT:    ret <4 x i32> [[D]]
;
  %B = zext <4 x i16> %A to <4 x i32>
  %C = add <4 x i32> %B, <i32 0, i32 1, i32 50, i32 16>
  %D = shl <4 x i32> <i32 6, i32 2, i32 1, i32 -7>, %C
  ret <4 x i32> %D
}

define <4 x i32> @ashr_C1_add_A_C2_v4i32(<4 x i32> %A) {
; CHECK-LABEL: @ashr_C1_add_A_C2_v4i32(
; CHECK-NEXT:    [[B:%.*]] = and <4 x i32> [[A:%.*]], <i32 0, i32 15, i32 255, i32 65535>
; CHECK-NEXT:    [[D:%.*]] = ashr <4 x i32> <i32 6, i32 1, i32 poison, i32 -1>, [[B]]
; CHECK-NEXT:    ret <4 x i32> [[D]]
;
  %B = and <4 x i32> %A, <i32 0, i32 15, i32 255, i32 65535>
  %C = add <4 x i32> %B, <i32 0, i32 1, i32 50, i32 16>
  %D = ashr <4 x i32> <i32 6, i32 2, i32 1, i32 -7>, %C
  ret <4 x i32> %D
}

define <4 x i32> @lshr_C1_add_A_C2_v4i32(<4 x i32> %A) {
; CHECK-LABEL: @lshr_C1_add_A_C2_v4i32(
; CHECK-NEXT:    [[B:%.*]] = and <4 x i32> [[A:%.*]], <i32 0, i32 15, i32 255, i32 65535>
; CHECK-NEXT:    [[D:%.*]] = lshr <4 x i32> <i32 6, i32 1, i32 poison, i32 65535>, [[B]]
; CHECK-NEXT:    ret <4 x i32> [[D]]
;
  %B = and <4 x i32> %A, <i32 0, i32 15, i32 255, i32 65535>
  %C = add <4 x i32> %B, <i32 0, i32 1, i32 50, i32 16>
  %D = lshr <4 x i32> <i32 6, i32 2, i32 1, i32 -7>, %C
  ret <4 x i32> %D
}

define <4 x i32> @shl_C1_add_A_C2_v4i32_splat(i16 %I) {
; CHECK-LABEL: @shl_C1_add_A_C2_v4i32_splat(
; CHECK-NEXT:    [[A:%.*]] = zext i16 [[I:%.*]] to i32
; CHECK-NEXT:    [[B:%.*]] = insertelement <4 x i32> undef, i32 [[A]], i64 0
; CHECK-NEXT:    [[C:%.*]] = shufflevector <4 x i32> [[B]], <4 x i32> undef, <4 x i32> zeroinitializer
; CHECK-NEXT:    [[E:%.*]] = shl <4 x i32> <i32 6, i32 4, i32 poison, i32 -458752>, [[C]]
; CHECK-NEXT:    ret <4 x i32> [[E]]
;
  %A = zext i16 %I to i32
  %B = insertelement <4 x i32> undef, i32 %A, i32 0
  %C = shufflevector <4 x i32> %B, <4 x i32> undef, <4 x i32> zeroinitializer
  %D = add <4 x i32> %C, <i32 0, i32 1, i32 50, i32 16>
  %E = shl <4 x i32> <i32 6, i32 2, i32 1, i32 -7>, %D
  ret <4 x i32> %E
}

define <4 x i32> @ashr_C1_add_A_C2_v4i32_splat(i16 %I) {
; CHECK-LABEL: @ashr_C1_add_A_C2_v4i32_splat(
; CHECK-NEXT:    [[A:%.*]] = zext i16 [[I:%.*]] to i32
; CHECK-NEXT:    [[B:%.*]] = insertelement <4 x i32> undef, i32 [[A]], i64 0
; CHECK-NEXT:    [[C:%.*]] = shufflevector <4 x i32> [[B]], <4 x i32> undef, <4 x i32> zeroinitializer
; CHECK-NEXT:    [[E:%.*]] = ashr <4 x i32> <i32 6, i32 1, i32 poison, i32 -1>, [[C]]
; CHECK-NEXT:    ret <4 x i32> [[E]]
;
  %A = zext i16 %I to i32
  %B = insertelement <4 x i32> undef, i32 %A, i32 0
  %C = shufflevector <4 x i32> %B, <4 x i32> undef, <4 x i32> zeroinitializer
  %D = add <4 x i32> %C, <i32 0, i32 1, i32 50, i32 16>
  %E = ashr <4 x i32> <i32 6, i32 2, i32 1, i32 -7>, %D
  ret <4 x i32> %E
}

define <4 x i32> @lshr_C1_add_A_C2_v4i32_splat(i16 %I) {
; CHECK-LABEL: @lshr_C1_add_A_C2_v4i32_splat(
; CHECK-NEXT:    [[A:%.*]] = zext i16 [[I:%.*]] to i32
; CHECK-NEXT:    [[B:%.*]] = insertelement <4 x i32> undef, i32 [[A]], i64 0
; CHECK-NEXT:    [[C:%.*]] = shufflevector <4 x i32> [[B]], <4 x i32> undef, <4 x i32> zeroinitializer
; CHECK-NEXT:    [[E:%.*]] = lshr <4 x i32> <i32 6, i32 1, i32 poison, i32 65535>, [[C]]
; CHECK-NEXT:    ret <4 x i32> [[E]]
;
  %A = zext i16 %I to i32
  %B = insertelement <4 x i32> undef, i32 %A, i32 0
  %C = shufflevector <4 x i32> %B, <4 x i32> undef, <4 x i32> zeroinitializer
  %D = add <4 x i32> %C, <i32 0, i32 1, i32 50, i32 16>
  %E = lshr <4 x i32> <i32 6, i32 2, i32 1, i32 -7>, %D
  ret <4 x i32> %E
}

define i32 @shl_add_nuw(i32 %x) {
; CHECK-LABEL: @shl_add_nuw(
; CHECK-NEXT:    [[R:%.*]] = shl i32 192, [[X:%.*]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add nuw i32 %x, 5
  %r = shl i32 6, %a
  ret i32 %r
}

; vectors with arbitrary constants work too

define <2 x i12> @lshr_add_nuw(<2 x i12> %x) {
; CHECK-LABEL: @lshr_add_nuw(
; CHECK-NEXT:    [[R:%.*]] = lshr <2 x i12> <i12 0, i12 21>, [[X:%.*]]
; CHECK-NEXT:    ret <2 x i12> [[R]]
;
  %a = add nuw <2 x i12> %x, <i12 5, i12 1>
  %r = lshr <2 x i12> <i12 6, i12 42>, %a
  ret <2 x i12> %r
}

; extra use is ok and in this case the result can be simplified to a constant

define i32 @ashr_add_nuw(i32 %x, i32* %p) {
; CHECK-LABEL: @ashr_add_nuw(
; CHECK-NEXT:    [[A:%.*]] = add nuw i32 [[X:%.*]], 5
; CHECK-NEXT:    store i32 [[A]], i32* [[P:%.*]], align 4
; CHECK-NEXT:    ret i32 -1
;
  %a = add nuw i32 %x, 5
  store i32 %a, i32* %p
  %r = ashr i32 -6, %a
  ret i32 %r
}

; negative test - must have 'nuw'

define i32 @shl_add_nsw(i32 %x) {
; CHECK-LABEL: @shl_add_nsw(
; CHECK-NEXT:    [[A:%.*]] = add nsw i32 [[X:%.*]], 5
; CHECK-NEXT:    [[R:%.*]] = shl i32 6, [[A]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add nsw i32 %x, 5
  %r = shl i32 6, %a
  ret i32 %r
}

; offset precondition check (must be negative constant) for lshr_exact_add_negative_shift_positive

define i32 @lshr_exact_add_positive_shift_positive(i32 %x) {
; CHECK-LABEL: @lshr_exact_add_positive_shift_positive(
; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], 1
; CHECK-NEXT:    [[R:%.*]] = lshr exact i32 2, [[A]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add i32 %x, 1
  %r = lshr exact i32 2, %a
  ret i32 %r
}

define i32 @lshr_exact_add_big_negative_offset(i32 %x) {
; CHECK-LABEL: @lshr_exact_add_big_negative_offset(
; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], -33
; CHECK-NEXT:    [[R:%.*]] = lshr exact i32 2, [[A]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add i32 %x, -33
  %r = lshr exact i32 2, %a
  ret i32 %r
}

; leading zeros for shifted constant precondition check for lshr_exact_add_negative_shift_positive

define i32 @lshr_exact_add_negative_shift_negative(i32 %x) {
; CHECK-LABEL: @lshr_exact_add_negative_shift_negative(
; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], -1
; CHECK-NEXT:    [[R:%.*]] = lshr exact i32 -2, [[A]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add i32 %x, -1
  %r = lshr exact i32 -2, %a
  ret i32 %r
}

; exact precondition check for lshr_exact_add_negative_shift_positive

define i32 @lshr_add_negative_shift_no_exact(i32 %x) {
; CHECK-LABEL: @lshr_add_negative_shift_no_exact(
; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], -1
; CHECK-NEXT:    [[R:%.*]] = lshr i32 2, [[A]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add i32 %x, -1
  %r = lshr i32 2, %a
  ret i32 %r
}

define i32 @lshr_exact_add_negative_shift_positive(i32 %x) {
; CHECK-LABEL: @lshr_exact_add_negative_shift_positive(
; CHECK-NEXT:    [[R:%.*]] = lshr exact i32 4, [[X:%.*]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add i32 %x, -1
  %r = lshr exact i32 2, %a
  ret i32 %r
}

define i8 @lshr_exact_add_negative_shift_positive_extra_use(i8 %x) {
; CHECK-LABEL: @lshr_exact_add_negative_shift_positive_extra_use(
; CHECK-NEXT:    [[A:%.*]] = add i8 [[X:%.*]], -1
; CHECK-NEXT:    call void @use(i8 [[A]])
; CHECK-NEXT:    [[R:%.*]] = lshr exact i8 -128, [[X]]
; CHECK-NEXT:    ret i8 [[R]]
;
  %a = add i8 %x, -1
  call void @use(i8 %a)
  %r = lshr exact i8 64, %a
  ret i8 %r
}

define <2 x i9> @lshr_exact_add_negative_shift_positive_vec(<2 x i9> %x) {
; CHECK-LABEL: @lshr_exact_add_negative_shift_positive_vec(
; CHECK-NEXT:    [[R:%.*]] = lshr exact <2 x i9> <i9 -256, i9 -256>, [[X:%.*]]
; CHECK-NEXT:    ret <2 x i9> [[R]]
;
  %a = add <2 x i9> %x, <i9 -7, i9 -7>
  %r = lshr exact <2 x i9> <i9 2, i9 2>, %a
  ret <2 x i9> %r
}

; not enough leading zeros in shift constant

define <2 x i9> @lshr_exact_add_negative_shift_lzcnt(<2 x i9> %x) {
; CHECK-LABEL: @lshr_exact_add_negative_shift_lzcnt(
; CHECK-NEXT:    [[A:%.*]] = add <2 x i9> [[X:%.*]], <i9 -7, i9 -7>
; CHECK-NEXT:    [[R:%.*]] = lshr exact <2 x i9> <i9 4, i9 4>, [[A]]
; CHECK-NEXT:    ret <2 x i9> [[R]]
;
  %a = add <2 x i9> %x, <i9 -7, i9 -7>
  %r = lshr exact <2 x i9> <i9 4, i9 4>, %a
  ret <2 x i9> %r
}

; leading ones precondition check for ashr_exact_add_negative_shift_[positive,negative]

define i8 @ashr_exact_add_negative_shift_no_trailing_zeros(i8 %x) {
; CHECK-LABEL: @ashr_exact_add_negative_shift_no_trailing_zeros(
; CHECK-NEXT:    [[A:%.*]] = add i8 [[X:%.*]], -4
; CHECK-NEXT:    [[R:%.*]] = ashr exact i8 -112, [[A]]
; CHECK-NEXT:    ret i8 [[R]]
;
  %a = add i8 %x, -4
  %r = ashr exact i8 -112, %a ; 0b1001_0000
  ret i8 %r
}

define i32 @ashr_exact_add_big_negative_offset(i32 %x) {
; CHECK-LABEL: @ashr_exact_add_big_negative_offset(
; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], -33
; CHECK-NEXT:    [[R:%.*]] = ashr exact i32 -2, [[A]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add i32 %x, -33
  %r = ashr exact i32 -2, %a
  ret i32 %r
}

; exact precondition check for ashr_exact_add_negative_shift_[positive,negative]

define i32 @ashr_add_negative_shift_no_exact(i32 %x) {
; CHECK-LABEL: @ashr_add_negative_shift_no_exact(
; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], -1
; CHECK-NEXT:    [[R:%.*]] = ashr i32 -2, [[A]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add i32 %x, -1
  %r = ashr i32 -2, %a
  ret i32 %r
}

define i32 @ashr_exact_add_negative_shift_negative(i32 %x) {
; CHECK-LABEL: @ashr_exact_add_negative_shift_negative(
; CHECK-NEXT:    [[R:%.*]] = ashr exact i32 -4, [[X:%.*]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add i32 %x, -1
  %r = ashr exact i32 -2, %a
  ret i32 %r
}

define i8 @ashr_exact_add_negative_shift_negative_extra_use(i8 %x) {
; CHECK-LABEL: @ashr_exact_add_negative_shift_negative_extra_use(
; CHECK-NEXT:    [[A:%.*]] = add i8 [[X:%.*]], -2
; CHECK-NEXT:    call void @use(i8 [[A]])
; CHECK-NEXT:    [[R:%.*]] = ashr exact i8 -128, [[X]]
; CHECK-NEXT:    ret i8 [[R]]
;
  %a = add i8 %x, -2
  call void @use(i8 %a)
  %r = ashr exact i8 -32, %a
  ret i8 %r
}

define <2 x i7> @ashr_exact_add_negative_shift_negative_vec(<2 x i7> %x) {
; CHECK-LABEL: @ashr_exact_add_negative_shift_negative_vec(
; CHECK-NEXT:    [[R:%.*]] = ashr exact <2 x i7> <i7 -64, i7 -64>, [[X:%.*]]
; CHECK-NEXT:    ret <2 x i7> [[R]]
;
  %a = add <2 x i7> %x, <i7 -5, i7 -5>
  %r = ashr exact <2 x i7> <i7 -2, i7 -2>, %a
  ret <2 x i7> %r
}

; not enough leading ones in shift constant

define <2 x i7> @ashr_exact_add_negative_leading_ones_vec(<2 x i7> %x) {
; CHECK-LABEL: @ashr_exact_add_negative_leading_ones_vec(
; CHECK-NEXT:    [[A:%.*]] = add <2 x i7> [[X:%.*]], <i7 -5, i7 -5>
; CHECK-NEXT:    [[R:%.*]] = ashr exact <2 x i7> <i7 -4, i7 -4>, [[A]]
; CHECK-NEXT:    ret <2 x i7> [[R]]
;
  %a = add <2 x i7> %x, <i7 -5, i7 -5>
  %r = ashr exact <2 x i7> <i7 -4, i7 -4>, %a
  ret <2 x i7> %r
}

; PR54890

define i32 @shl_nsw_add_negative(i32 %x) {
; CHECK-LABEL: @shl_nsw_add_negative(
; CHECK-NEXT:    [[R:%.*]] = shl i32 1, [[X:%.*]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add i32 %x, -1
  %r = shl nsw i32 2, %a
  ret i32 %r
}

; vectors and extra uses are allowed
; nuw propagates to the new shift

define <2 x i8> @shl_nuw_add_negative_splat_uses(<2 x i8> %x, <2 x i8>* %p) {
; CHECK-LABEL: @shl_nuw_add_negative_splat_uses(
; CHECK-NEXT:    [[A:%.*]] = add <2 x i8> [[X:%.*]], <i8 -2, i8 -2>
; CHECK-NEXT:    store <2 x i8> [[A]], <2 x i8>* [[P:%.*]], align 2
; CHECK-NEXT:    [[R:%.*]] = shl nuw <2 x i8> <i8 3, i8 3>, [[X]]
; CHECK-NEXT:    ret <2 x i8> [[R]]
;
  %a = add <2 x i8> %x, <i8 -2, i8 -2>
  store <2 x i8> %a, <2 x i8>* %p
  %r = shl nuw <2 x i8> <i8 12, i8 12>, %a
  ret <2 x i8> %r
}

; negative test - shift constant must have enough trailing zeros to allow the pre-shift

define i32 @shl_nsw_add_negative_invalid_constant(i32 %x) {
; CHECK-LABEL: @shl_nsw_add_negative_invalid_constant(
; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], -2
; CHECK-NEXT:    [[R:%.*]] = shl nsw i32 2, [[A]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add i32 %x, -2
  %r = shl nsw i32 2, %a
  ret i32 %r
}

; negative test - the offset constant must be negative

define i32 @shl_nsw_add_positive_invalid_constant(i32 %x) {
; CHECK-LABEL: @shl_nsw_add_positive_invalid_constant(
; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], 2
; CHECK-NEXT:    [[R:%.*]] = shl nsw i32 4, [[A]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add i32 %x, 2
  %r = shl nsw i32 4, %a
  ret i32 %r
}

; negative test - a large shift must be detected without crashing

define i32 @shl_nsw_add_negative_invalid_constant2(i32 %x) {
; CHECK-LABEL: @shl_nsw_add_negative_invalid_constant2(
; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], -33
; CHECK-NEXT:    [[R:%.*]] = shl nsw i32 2, [[A]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add i32 %x, -33
  %r = shl nsw i32 2, %a
  ret i32 %r
}

; negative test - currently transformed to 'xor' before we see it,
; but INT_MIN should be handled too

define i4 @shl_nsw_add_negative_invalid_constant3(i4 %x) {
; CHECK-LABEL: @shl_nsw_add_negative_invalid_constant3(
; CHECK-NEXT:    [[A:%.*]] = xor i4 [[X:%.*]], -8
; CHECK-NEXT:    [[R:%.*]] = shl nsw i4 2, [[A]]
; CHECK-NEXT:    ret i4 [[R]]
;
  %a = add i4 %x, 8
  %r = shl nsw i4 2, %a
  ret i4 %r
}