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

declare void @use(i8)

define i1 @test1(i32 %i, ptr %p) {
; CHECK-LABEL: define i1 @test1(
; CHECK-SAME: i32 [[I:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT:    [[DOTLOBIT:%.*]] = lshr i32 [[I]], 31
; CHECK-NEXT:    store i32 [[DOTLOBIT]], ptr [[P]], align 1
; CHECK-NEXT:    ret i1 false
;
  %lobit = lshr i32 %i, 31
  %t = trunc nuw i32 %lobit to i1
  %b = icmp slt i32 %i, 0
  %not = xor i1 %t, true
  %op = select i1 %not, i1 %b, i1 false
  store i32 %lobit, ptr %p, align 1
  ret i1 %op
}

define i1 @test2(i32 %i, ptr %p) {
; CHECK-LABEL: define i1 @test2(
; CHECK-SAME: i32 [[I:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT:    [[DOTLOBIT:%.*]] = ashr i32 [[I]], 31
; CHECK-NEXT:    store i32 [[DOTLOBIT]], ptr [[P]], align 1
; CHECK-NEXT:    ret i1 false
;
  %lobit = ashr i32 %i, 31
  %t = trunc nuw i32 %lobit to i1
  %b = icmp slt i32 %i, 0
  %not = xor i1 %t, true
  %op = select i1 %not, i1 %b, i1 false
  store i32 %lobit, ptr %p, align 1
  ret i1 %op
}

define i1 @test3(i32 %i, ptr %p, ptr %q) {
; CHECK-LABEL: define i1 @test3(
; CHECK-SAME: i32 [[I:%.*]], ptr [[P:%.*]], ptr [[Q:%.*]]) {
; CHECK-NEXT:    [[DOTLOBIT:%.*]] = lshr i32 [[I]], 31
; CHECK-NEXT:    store i32 [[DOTLOBIT]], ptr [[P]], align 1
; CHECK-NEXT:    store i32 [[DOTLOBIT]], ptr [[Q]], align 1
; CHECK-NEXT:    ret i1 false
;
  %lobit = lshr i32 %i, 31
  %t = trunc nuw i32 %lobit to i1
  %b = icmp slt i32 %i, 0
  %not = xor i1 %t, true
  %op = select i1 %not, i1 %b, i1 false
  store i32 %lobit, ptr %p, align 1
  store i32 %lobit, ptr %q, align 1
  ret i1 %op
}

; Negative Test
define i1 @test4(i32 %i, ptr %p) {
; CHECK-LABEL: define i1 @test4(
; CHECK-SAME: i32 [[I:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT:    [[DOTLOBIT:%.*]] = lshr i32 [[I]], 30
; CHECK-NEXT:    [[T:%.*]] = trunc nuw i32 [[DOTLOBIT]] to i1
; CHECK-NEXT:    [[B:%.*]] = icmp slt i32 [[I]], 0
; CHECK-NEXT:    [[NOT_:%.*]] = xor i1 [[T]], true
; CHECK-NEXT:    [[COMMON_RET1_OP:%.*]] = select i1 [[NOT_]], i1 [[B]], i1 false
; CHECK-NEXT:    store i32 [[DOTLOBIT]], ptr [[P]], align 1
; CHECK-NEXT:    ret i1 [[COMMON_RET1_OP]]
;
  %lobit = lshr i32 %i, 30 ; should not fold as no. of bits shifted < BitWidth - 1
  %t = trunc nuw i32 %lobit to i1
  %b = icmp slt i32 %i, 0
  %not = xor i1 %t, true
  %op = select i1 %not, i1 %b, i1 false
  store i32 %lobit, ptr %p, align 1
  ret i1 %op
}

; Negative Test
define i1 @test5(i32 %i, ptr %p) {
; CHECK-LABEL: define i1 @test5(
; CHECK-SAME: i32 [[I:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT:    [[DOTLOBIT:%.*]] = ashr i32 [[I]], 30
; CHECK-NEXT:    [[T:%.*]] = trunc nuw i32 [[DOTLOBIT]] to i1
; CHECK-NEXT:    [[B:%.*]] = icmp slt i32 [[I]], 0
; CHECK-NEXT:    [[NOT_:%.*]] = xor i1 [[T]], true
; CHECK-NEXT:    [[COMMON_RET1_OP:%.*]] = select i1 [[NOT_]], i1 [[B]], i1 false
; CHECK-NEXT:    store i32 [[DOTLOBIT]], ptr [[P]], align 1
; CHECK-NEXT:    ret i1 [[COMMON_RET1_OP]]
;
  %lobit = ashr i32 %i, 30 ; should not fold as no. of bits shifted < BitWidth - 1
  %t = trunc nuw i32 %lobit to i1
  %b = icmp slt i32 %i, 0
  %not = xor i1 %t, true
  %op = select i1 %not, i1 %b, i1 false
  store i32 %lobit, ptr %p, align 1
  ret i1 %op
}

define i1 @fold_lshr_power_of_2(i8 %x) {
; CHECK-LABEL: define i1 @fold_lshr_power_of_2(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[TRUNC:%.*]] = icmp eq i8 [[X]], 4
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %lshr = lshr i8 16, %x ; 16 is a power of 2
  %trunc = trunc i8 %lshr to i1
  ret i1 %trunc
}

define i1 @fold_lshr_power_of_2_minus_1(i8 %x) {
; CHECK-LABEL: define i1 @fold_lshr_power_of_2_minus_1(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[TRUNC:%.*]] = icmp ult i8 [[X]], 4
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %lshr = lshr i8 15, %x
  %trunc = trunc i8 %lshr to i1
  ret i1 %trunc
}

define i1 @fold_ashr_power_of_2(i8 %x) {
; CHECK-LABEL: define i1 @fold_ashr_power_of_2(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[TRUNC:%.*]] = icmp eq i8 [[X]], 4
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %ashr = ashr i8 16, %x
  %trunc = trunc i8 %ashr to i1
  ret i1 %trunc
}

define i1 @fold_ashr_power_of_2_minus_1(i8 %x) {
; CHECK-LABEL: define i1 @fold_ashr_power_of_2_minus_1(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[TRUNC:%.*]] = icmp ult i8 [[X]], 4
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %ashr = ashr i8 15, %x ; (15 + 1) is a power of 2
  %trunc = trunc i8 %ashr to i1
  ret i1 %trunc
}

define i1 @fold_lshr_power_of_2_multi_use(i8 %x) {
; CHECK-LABEL: define i1 @fold_lshr_power_of_2_multi_use(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[LSHR:%.*]] = lshr i8 16, [[X]]
; CHECK-NEXT:    call void @use(i8 [[LSHR]])
; CHECK-NEXT:    [[TRUNC:%.*]] = icmp eq i8 [[X]], 4
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %lshr = lshr i8 16, %x ; 16 is a power of 2
  call void @use(i8 %lshr)
  %trunc = trunc i8 %lshr to i1
  ret i1 %trunc
}

define i1 @fold_lshr_power_of_2_minus_1_multi_use(i8 %x) {
; CHECK-LABEL: define i1 @fold_lshr_power_of_2_minus_1_multi_use(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[LSHR:%.*]] = lshr i8 15, [[X]]
; CHECK-NEXT:    call void @use(i8 [[LSHR]])
; CHECK-NEXT:    [[TRUNC:%.*]] = icmp ult i8 [[X]], 4
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %lshr = lshr i8 15, %x
  call void @use(i8 %lshr)
  %trunc = trunc i8 %lshr to i1
  ret i1 %trunc
}

define i1 @fold_ashr_power_of_2_multi_use(i8 %x) {
; CHECK-LABEL: define i1 @fold_ashr_power_of_2_multi_use(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[ASHR:%.*]] = lshr i8 16, [[X]]
; CHECK-NEXT:    call void @use(i8 [[ASHR]])
; CHECK-NEXT:    [[TRUNC:%.*]] = icmp eq i8 [[X]], 4
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %ashr = ashr i8 16, %x
  call void @use(i8 %ashr)
  %trunc = trunc i8 %ashr to i1
  ret i1 %trunc
}

define i1 @fold_ashr_power_of_2_minus_1_multi_use(i8 %x) {
; CHECK-LABEL: define i1 @fold_ashr_power_of_2_minus_1_multi_use(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[ASHR:%.*]] = lshr i8 15, [[X]]
; CHECK-NEXT:    call void @use(i8 [[ASHR]])
; CHECK-NEXT:    [[TRUNC:%.*]] = icmp ult i8 [[X]], 4
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %ashr = ashr i8 15, %x ; (15 + 1) is a power of 2
  call void @use(i8 %ashr)
  %trunc = trunc i8 %ashr to i1
  ret i1 %trunc
}

define i1 @negative_test_fold_lshr(i8 %x) {
; CHECK-LABEL: define i1 @negative_test_fold_lshr(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[LSHR:%.*]] = lshr i8 9, [[X]]
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i8 [[LSHR]] to i1
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %lshr = lshr i8 9, %x ; 9 or (9 + 1) is not a power of 2
  %trunc = trunc i8 %lshr to i1
  ret i1 %trunc
}

; Negative Test for arithmetic shift right
define i1 @negative_test_fold_ashr(i8 %x) {
; CHECK-LABEL: define i1 @negative_test_fold_ashr(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[ASHR:%.*]] = lshr i8 9, [[X]]
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i8 [[ASHR]] to i1
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %ashr = ashr i8 9, %x ; 9 or (9 + 1) is not a power of 2
  %trunc = trunc i8 %ashr to i1
  ret i1 %trunc
}

define i1 @fold_lshr_negated_power_of_2(i8 %x) {
; CHECK-LABEL: define i1 @fold_lshr_negated_power_of_2(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[TRUNC:%.*]] = icmp ugt i8 [[X]], 3
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %lshr = lshr i8 -16, %x
  %trunc = trunc i8 %lshr to i1
  ret i1 %trunc
}

define i1 @fold_ashr_negated_power_of_2(i8 %x) {
; CHECK-LABEL: define i1 @fold_ashr_negated_power_of_2(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[TRUNC:%.*]] = icmp ugt i8 [[X]], 3
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %ashr = ashr i8 -16, %x
  %trunc = trunc i8 %ashr to i1
  ret i1 %trunc
}

define i1 @fold_lshr_negated_power_of_2_multi_use(i8 %x) {
; CHECK-LABEL: define i1 @fold_lshr_negated_power_of_2_multi_use(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[LSHR:%.*]] = lshr i8 -16, [[X]]
; CHECK-NEXT:    call void @use(i8 [[LSHR]])
; CHECK-NEXT:    [[TRUNC:%.*]] = icmp ugt i8 [[X]], 3
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %lshr = lshr i8 -16, %x
  call void @use(i8 %lshr)
  %trunc = trunc i8 %lshr to i1
  ret i1 %trunc
}

define i1 @fold_ashr_negated_power_of_2_multi_use(i8 %x) {
; CHECK-LABEL: define i1 @fold_ashr_negated_power_of_2_multi_use(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[ASHR:%.*]] = ashr i8 -16, [[X]]
; CHECK-NEXT:    call void @use(i8 [[ASHR]])
; CHECK-NEXT:    [[TRUNC:%.*]] = icmp ugt i8 [[X]], 3
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %ashr = ashr i8 -16, %x
  call void @use(i8 %ashr)
  %trunc = trunc i8 %ashr to i1
  ret i1 %trunc
}

define i1 @negative_test_fold_lshr_negated_power_of_2(i8 %x) {
; CHECK-LABEL: define i1 @negative_test_fold_lshr_negated_power_of_2(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[LSHR:%.*]] = lshr i8 -17, [[X]]
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i8 [[LSHR]] to i1
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %lshr = lshr i8 -17, %x
  %trunc = trunc i8 %lshr to i1
  ret i1 %trunc
}

define i1 @negative_test_fold_ashr_negated_power_of_2(i8 %x) {
; CHECK-LABEL: define i1 @negative_test_fold_ashr_negated_power_of_2(
; CHECK-SAME: i8 [[X:%.*]]) {
; CHECK-NEXT:    [[ASHR1:%.*]] = lshr i8 -17, [[X]]
; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i8 [[ASHR1]] to i1
; CHECK-NEXT:    ret i1 [[TRUNC]]
;
  %ashr = ashr i8 -17, %x
  %trunc = trunc i8 %ashr to i1
  ret i1 %trunc
}