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

define i1 @ceil_shift4(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift4(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[ARG0]], 0
; CHECK-NEXT:    ret i1 [[TMP1]]
;
  %quot = lshr i32 %arg0, 4
  %rem = and i32 %arg0, 15
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %quot_or_rem = or i32 %quot, %zext_has_rem
  %is_zero = icmp eq i32 %quot_or_rem, 0
  ret i1 %is_zero
}

define i1 @ceil_shift4_add(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift4_add(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[ARG0]], 0
; CHECK-NEXT:    ret i1 [[TMP6]]
;
  %quot = lshr i32 %arg0, 4
  %rem = and i32 %arg0, 15
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %ceil = add i32 %quot, %zext_has_rem
  %res = icmp eq i32 %ceil, 0
  ret i1 %res
}

define i1 @ceil_shift6(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift6(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[ARG0]], 0
; CHECK-NEXT:    ret i1 [[TMP1]]
;
  %quot = lshr i32 %arg0, 6
  %rem = and i32 %arg0, 63
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %quot_or_rem = or i32 %quot, %zext_has_rem
  %res = icmp eq i32 %quot_or_rem, 0
  ret i1 %res
}

define i1 @ceil_shift6_ne(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift6_ne(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[RES:%.*]] = icmp ne i32 [[ARG0]], 0
; CHECK-NEXT:    ret i1 [[RES]]
;
  %quot = lshr i32 %arg0, 6
  %rem = and i32 %arg0, 63
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %quot_or_rem = or i32 %quot, %zext_has_rem
  %res = icmp ne i32 %quot_or_rem, 0
  ret i1 %res
}

define i1 @ceil_shift11(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift11(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[ARG0]], 0
; CHECK-NEXT:    ret i1 [[TMP1]]
;
  %quot = lshr i32 %arg0, 11
  %rem = and i32 %arg0, 2047
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %quot_or_rem = or i32 %quot, %zext_has_rem
  %res = icmp eq i32 %quot_or_rem, 0
  ret i1 %res
}

define i1 @ceil_shift11_ne(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift11_ne(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[RES:%.*]] = icmp ne i32 [[ARG0]], 0
; CHECK-NEXT:    ret i1 [[RES]]
;
  %quot = lshr i32 %arg0, 6
  %rem = and i32 %arg0, 63
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %quot_or_rem = or i32 %quot, %zext_has_rem
  %res = icmp ne i32 %quot_or_rem, 0
  ret i1 %res
}

define i1 @ceil_shift0(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift0(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[ARG0]], 0
; CHECK-NEXT:    ret i1 [[TMP1]]
;
  %quot = lshr i32 %arg0, 0
  %rem = and i32 %arg0, 0
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %quot_or_rem = or i32 %quot, %zext_has_rem
  %res = icmp eq i32 %quot_or_rem, 0
  ret i1 %res
}

define i1 @ceil_shift4_comm(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift4_comm(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[ARG0]], 0
; CHECK-NEXT:    ret i1 [[TMP6]]
;
  %quot = lshr i32 %arg0, 4
  %rem = and i32 %arg0, 15
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %quot_or_rem = or i32 %zext_has_rem, %quot
  %res = icmp eq i32 %quot_or_rem, 0
  ret i1 %res
}

declare void @use(i32)

define i1 @ceil_shift4_used_1(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift4_used_1(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[ARG0]], 4
; CHECK-NEXT:    call void @use(i32 [[TMP1]])
; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[ARG0]], 0
; CHECK-NEXT:    ret i1 [[TMP6]]
;
  %quot = lshr i32 %arg0, 4
  call void @use(i32 %quot)
  %rem = and i32 %arg0, 15
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %quot_or_rem = or i32 %quot, %zext_has_rem
  %res = icmp eq i32 %quot_or_rem, 0
  ret i1 %res
}

define i1 @ceil_shift4_used_5(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift4_used_5(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[ARG0]], 4
; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[ARG0]], 15
; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
; CHECK-NEXT:    [[TMP4:%.*]] = zext i1 [[TMP3]] to i32
; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP1]], [[TMP4]]
; CHECK-NEXT:    call void @use(i32 [[TMP5]])
; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[ARG0]], 0
; CHECK-NEXT:    ret i1 [[TMP6]]
;
  %quot = lshr i32 %arg0, 4
  %rem = and i32 %arg0, 15
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %quot_or_rem = or i32 %quot, %zext_has_rem
  call void @use(i32 %quot_or_rem)
  %res = icmp eq i32 %quot_or_rem, 0
  ret i1 %res
}

define i1 @ceil_shift4_used_add_nuw_nsw(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift4_used_add_nuw_nsw(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[QUOT:%.*]] = lshr i32 [[ARG0]], 4
; CHECK-NEXT:    [[REM:%.*]] = and i32 [[ARG0]], 15
; CHECK-NEXT:    [[HAS_REM:%.*]] = icmp ne i32 [[REM]], 0
; CHECK-NEXT:    [[ZEXT_HAS_REM:%.*]] = zext i1 [[HAS_REM]] to i32
; CHECK-NEXT:    [[CEIL:%.*]] = add nuw nsw i32 [[QUOT]], [[ZEXT_HAS_REM]]
; CHECK-NEXT:    call void @use(i32 [[CEIL]])
; CHECK-NEXT:    [[RES:%.*]] = icmp eq i32 [[ARG0]], 0
; CHECK-NEXT:    ret i1 [[RES]]
;
  %quot = lshr i32 %arg0, 4
  %rem = and i32 %arg0, 15
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %ceil = add nuw nsw i32 %quot, %zext_has_rem
  call void @use(i32 %ceil)
  %res = icmp eq i32 %ceil, 0
  ret i1 %res
}

define <4 x i1> @ceil_shift4_v4i32(<4 x i32> %arg0) {
; CHECK-LABEL: define <4 x i1> @ceil_shift4_v4i32(
; CHECK-SAME: <4 x i32> [[ARG0:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <4 x i32> [[ARG0]], zeroinitializer
; CHECK-NEXT:    ret <4 x i1> [[TMP1]]
;
  %quot = lshr <4 x i32> %arg0, splat (i32 16)
  %rem = and <4 x i32> %arg0, splat (i32 65535)
  %has_rem = icmp ne <4 x i32> %rem, zeroinitializer
  %zext_has_rem = zext <4 x i1> %has_rem to <4 x i32>
  %quot_or_rem = or <4 x i32> %quot, %zext_has_rem
  %res = icmp eq <4 x i32> %quot_or_rem, zeroinitializer
  ret <4 x i1> %res
}

define <8 x i1> @ceil_shift4_v8i16(<8 x i16> %arg0) {
; CHECK-LABEL: define <8 x i1> @ceil_shift4_v8i16(
; CHECK-SAME: <8 x i16> [[ARG0:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <8 x i16> [[ARG0]], zeroinitializer
; CHECK-NEXT:    ret <8 x i1> [[TMP1]]
;
  %quot = lshr <8 x i16> %arg0, splat (i16 4)
  %rem = and <8 x i16> %arg0, splat (i16 15)
  %has_rem = icmp ne <8 x i16> %rem, zeroinitializer
  %zext_has_rem = zext <8 x i1> %has_rem to <8 x i16>
  %quot_or_rem = or <8 x i16> %quot, %zext_has_rem
  %res = icmp eq <8 x i16> %quot_or_rem, zeroinitializer
  ret <8 x i1> %res
}

; negative tests

define i1 @ceil_shift_not_mask_1(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift_not_mask_1(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[ARG0]], 4
; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[ARG0]], 31
; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
; CHECK-NEXT:    [[TMP4:%.*]] = zext i1 [[TMP3]] to i32
; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP1]], [[TMP4]]
; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[TMP5]], 0
; CHECK-NEXT:    ret i1 [[TMP6]]
;
  %quot = lshr i32 %arg0, 4
  %rem = and i32 %arg0, 31
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %quot_or_rem = or i32 %quot, %zext_has_rem
  %res = icmp eq i32 %quot_or_rem, 0
  ret i1 %res
}

define i1 @ceil_shift_not_mask_2(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift_not_mask_2(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[ARG0]], 5
; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[ARG0]], 15
; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
; CHECK-NEXT:    [[TMP4:%.*]] = zext i1 [[TMP3]] to i32
; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP1]], [[TMP4]]
; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32 [[TMP5]], 0
; CHECK-NEXT:    ret i1 [[TMP6]]
;
  %quot = lshr i32 %arg0, 5
  %rem = and i32 %arg0, 15
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %quot_or_rem = or i32 %quot, %zext_has_rem
  %res = icmp eq i32 %quot_or_rem, 0
  ret i1 %res
}

define i1 @ceil_shift_not_add_or(i32 %arg0) {
; CHECK-LABEL: define i1 @ceil_shift_not_add_or(
; CHECK-SAME: i32 [[ARG0:%.*]]) {
; CHECK-NEXT:    [[REM:%.*]] = and i32 [[ARG0]], 15
; CHECK-NEXT:    [[HAS_REM_NOT:%.*]] = icmp eq i32 [[REM]], 0
; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[ARG0]], 32
; CHECK-NEXT:    [[RES1:%.*]] = icmp eq i32 [[TMP1]], 0
; CHECK-NEXT:    [[RES:%.*]] = or i1 [[HAS_REM_NOT]], [[RES1]]
; CHECK-NEXT:    ret i1 [[RES]]
;
  %quot = lshr i32 %arg0, 5
  %rem = and i32 %arg0, 15
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %quot_and_rem = and i32 %quot, %zext_has_rem
  %res = icmp eq i32 %quot_and_rem, 0
  ret i1 %res
}

define i32 @ceil_shift_should_infer_ge_zero(i32 %x) {
; CHECK-LABEL: define i32 @ceil_shift_should_infer_ge_zero(
; CHECK-SAME: i32 [[X:%.*]]) {
; CHECK-NEXT:    [[COND_NOT:%.*]] = icmp eq i32 [[X]], 0
; CHECK-NEXT:    br i1 [[COND_NOT]], label %[[IF_ELSE:.*]], label %[[IF_THEN:.*]]
; CHECK:       [[IF_THEN]]:
; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X]], 20
; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[X]], 1048575
; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
; CHECK-NEXT:    [[TMP4:%.*]] = zext i1 [[TMP3]] to i32
; CHECK-NEXT:    [[TMP5:%.*]] = add nuw nsw i32 [[TMP1]], [[TMP4]]
; CHECK-NEXT:    ret i32 [[TMP5]]
; CHECK:       [[IF_ELSE]]:
; CHECK-NEXT:    ret i32 0
;
  %cond = icmp ne i32 %x, 0
  br i1 %cond, label %if.then, label %if.else

if.then:
  %quot = lshr i32 %x, 20
  %rem = and i32 %x, 1048575
  %has_rem = icmp ne i32 %rem, 0
  %zext_has_rem = zext i1 %has_rem to i32
  %ceil = add nuw nsw i32 %quot, %zext_has_rem
  %max = call i32 @llvm.umax.i32(i32 %ceil, i32 1)
  ret i32 %max

if.else:
  ret i32 0
}