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

declare void @use(i8)
declare void @use32(i32)

declare i8 @llvm.umin.i8(i8, i8)
declare i8 @llvm.umax.i8(i8, i8)
declare i8 @llvm.smin.i8(i8, i8)
declare i8 @llvm.smax.i8(i8, i8)

define i32 @t1(i16 zeroext %x, i32 %y) {
; CHECK-LABEL: @t1(
; CHECK-NEXT:    [[CONV:%.*]] = zext i16 [[X:%.*]] to i32
; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[Y:%.*]], 1
; CHECK-NEXT:    [[D1:%.*]] = lshr i32 [[CONV]], [[TMP1]]
; CHECK-NEXT:    ret i32 [[D1]]
;
  %conv = zext i16 %x to i32
  %s = shl i32 2, %y
  %d = sdiv i32 %conv, %s
  ret i32 %d
}

define <2 x i32> @t1vec(<2 x i16> %x, <2 x i32> %y) {
; CHECK-LABEL: @t1vec(
; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i16> [[X:%.*]] to <2 x i32>
; CHECK-NEXT:    [[TMP1:%.*]] = add <2 x i32> [[Y:%.*]], <i32 1, i32 1>
; CHECK-NEXT:    [[D1:%.*]] = lshr <2 x i32> [[CONV]], [[TMP1]]
; CHECK-NEXT:    ret <2 x i32> [[D1]]
;
  %conv = zext <2 x i16> %x to <2 x i32>
  %s = shl <2 x i32> <i32 2, i32 2>, %y
  %d = sdiv <2 x i32> %conv, %s
  ret <2 x i32> %d
}

; rdar://11721329
define i64 @t2(i64 %x, i32 %y) {
; CHECK-LABEL: @t2(
; CHECK-NEXT:    [[TMP1:%.*]] = zext nneg i32 [[Y:%.*]] to i64
; CHECK-NEXT:    [[TMP2:%.*]] = lshr i64 [[X:%.*]], [[TMP1]]
; CHECK-NEXT:    ret i64 [[TMP2]]
;
  %1 = shl i32 1, %y
  %2 = zext i32 %1 to i64
  %3 = udiv i64 %x, %2
  ret i64 %3
}

; PR13250
define i64 @t3(i64 %x, i32 %y) {
; CHECK-LABEL: @t3(
; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[Y:%.*]], 2
; CHECK-NEXT:    [[TMP2:%.*]] = zext nneg i32 [[TMP1]] to i64
; CHECK-NEXT:    [[TMP3:%.*]] = lshr i64 [[X:%.*]], [[TMP2]]
; CHECK-NEXT:    ret i64 [[TMP3]]
;
  %1 = shl i32 4, %y
  %2 = zext i32 %1 to i64
  %3 = udiv i64 %x, %2
  ret i64 %3
}

define i32 @t4(i32 %x, i32 %y) {
; CHECK-LABEL: @t4(
; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.umax.i32(i32 [[Y:%.*]], i32 5)
; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[X:%.*]], [[TMP1]]
; CHECK-NEXT:    ret i32 [[TMP2]]
;
  %1 = shl i32 1, %y
  %2 = icmp ult i32 %1, 32
  %3 = select i1 %2, i32 32, i32 %1
  %4 = udiv i32 %x, %3
  ret i32 %4
}

define i32 @t5(i1 %x, i1 %y, i32 %V) {
; CHECK-LABEL: @t5(
; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X:%.*]], i32 5, i32 6
; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[Y:%.*]], i32 [[TMP1]], i32 [[V:%.*]]
; CHECK-NEXT:    [[TMP3:%.*]] = lshr i32 [[V]], [[TMP2]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = shl i32 1, %V
  %2 = select i1 %x, i32 32, i32 64
  %3 = select i1 %y, i32 %2, i32 %1
  %4 = udiv i32 %V, %3
  ret i32 %4
}

define i32 @t6(i32 %x, i32 %z) {
; CHECK-LABEL: @t6(
; CHECK-NEXT:    [[DIVISOR:%.*]] = call i32 @llvm.umax.i32(i32 [[X:%.*]], i32 1)
; CHECK-NEXT:    [[Y:%.*]] = udiv i32 [[Z:%.*]], [[DIVISOR]]
; CHECK-NEXT:    ret i32 [[Y]]
;
  %x_is_zero = icmp eq i32 %x, 0
  %divisor = select i1 %x_is_zero, i32 1, i32 %x
  %y = udiv i32 %z, %divisor
  ret i32 %y
}

define i8 @udiv_umin(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_umin(
; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.umin.i8(i8 [[Y:%.*]], i8 [[Z:%.*]])
; CHECK-NEXT:    [[D1:%.*]] = lshr i8 [[X:%.*]], [[TMP1]]
; CHECK-NEXT:    ret i8 [[D1]]
;
  %y2 = shl i8 1, %y
  %z2 = shl i8 1, %z
  %m = call i8 @llvm.umin.i8(i8 %y2, i8 %z2)
  %d = udiv i8 %x, %m
  ret i8 %d
}

define i8 @udiv_umax(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_umax(
; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.umax.i8(i8 [[Y:%.*]], i8 [[Z:%.*]])
; CHECK-NEXT:    [[D1:%.*]] = lshr i8 [[X:%.*]], [[TMP1]]
; CHECK-NEXT:    ret i8 [[D1]]
;
  %y2 = shl i8 1, %y
  %z2 = shl i8 1, %z
  %m = call i8 @llvm.umax.i8(i8 %y2, i8 %z2)
  %d = udiv i8 %x, %m
  ret i8 %d
}

; Negative test, cannot take exact log2
define i8 @udiv_umin_(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_umin_(
; CHECK-NEXT:    [[Y2:%.*]] = shl nuw i8 1, [[Y:%.*]]
; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[Y2]], i8 [[Z:%.*]])
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[X:%.*]], [[M]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %y2 = shl i8 1, %y
  %m = call i8 @llvm.umin.i8(i8 %y2, i8 %z)
  %d = udiv i8 %x, %m
  ret i8 %d
}

; Negative test, extra use
define i8 @udiv_umin_extra_use(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_umin_extra_use(
; CHECK-NEXT:    [[Y2:%.*]] = shl nuw i8 1, [[Y:%.*]]
; CHECK-NEXT:    [[Z2:%.*]] = shl nuw i8 1, [[Z:%.*]]
; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[Y2]], i8 [[Z2]])
; CHECK-NEXT:    call void @use(i8 [[M]])
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[X:%.*]], [[M]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %y2 = shl i8 1, %y
  %z2 = shl i8 1, %z
  %m = call i8 @llvm.umin.i8(i8 %y2, i8 %z2)
  call void @use(i8 %m)
  %d = udiv i8 %x, %m
  ret i8 %d
}

; Negative test, signed min/max
define i8 @udiv_smin(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_smin(
; CHECK-NEXT:    [[Y2:%.*]] = shl nuw i8 1, [[Y:%.*]]
; CHECK-NEXT:    [[Z2:%.*]] = shl nuw i8 1, [[Z:%.*]]
; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smin.i8(i8 [[Y2]], i8 [[Z2]])
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[X:%.*]], [[M]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %y2 = shl i8 1, %y
  %z2 = shl i8 1, %z
  %m = call i8 @llvm.smin.i8(i8 %y2, i8 %z2)
  %d = udiv i8 %x, %m
  ret i8 %d
}

; Negative test, signed min/max
define i8 @udiv_smax(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_smax(
; CHECK-NEXT:    [[Y2:%.*]] = shl nuw i8 1, [[Y:%.*]]
; CHECK-NEXT:    [[Z2:%.*]] = shl nuw i8 1, [[Z:%.*]]
; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smax.i8(i8 [[Y2]], i8 [[Z2]])
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[X:%.*]], [[M]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %y2 = shl i8 1, %y
  %z2 = shl i8 1, %z
  %m = call i8 @llvm.smax.i8(i8 %y2, i8 %z2)
  %d = udiv i8 %x, %m
  ret i8 %d
}

; (X << C1) / X -> 1 << C1 optimizations

define i32 @t7(i32 %x) {
; CHECK-LABEL: @t7(
; CHECK-NEXT:    ret i32 4
;
  %shl = shl nsw i32 %x, 2
  %r = sdiv i32 %shl, %x
  ret i32 %r
}

; make sure the previous opt doesn't take place for wrapped shifts

define i32 @t8(i32 %x) {
; CHECK-LABEL: @t8(
; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], 2
; CHECK-NEXT:    [[R:%.*]] = sdiv i32 [[SHL]], [[X]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %shl = shl i32 %x, 2
  %r = sdiv i32 %shl, %x
  ret i32 %r
}

define <2 x i32> @t9(<2 x i32> %x) {
; CHECK-LABEL: @t9(
; CHECK-NEXT:    ret <2 x i32> <i32 4, i32 8>
;
  %shl = shl nsw <2 x i32> %x, <i32 2, i32 3>
  %r = sdiv <2 x i32> %shl, %x
  ret <2 x i32> %r
}

define i32 @t10(i32 %x, i32 %y) {
; CHECK-LABEL: @t10(
; CHECK-NEXT:    [[R:%.*]] = shl nuw nsw i32 1, [[Y:%.*]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %shl = shl nsw i32 %x, %y
  %r = sdiv i32 %shl, %x
  ret i32 %r
}

define <2 x i32> @t11(<2 x i32> %x, <2 x i32> %y) {
; CHECK-LABEL: @t11(
; CHECK-NEXT:    [[R:%.*]] = shl nuw nsw <2 x i32> <i32 1, i32 1>, [[Y:%.*]]
; CHECK-NEXT:    ret <2 x i32> [[R]]
;
  %shl = shl nsw <2 x i32> %x, %y
  %r = sdiv <2 x i32> %shl, %x
  ret <2 x i32> %r
}

define i32 @t12(i32 %x) {
; CHECK-LABEL: @t12(
; CHECK-NEXT:    ret i32 4
;
  %shl = shl nuw i32 %x, 2
  %r = udiv i32 %shl, %x
  ret i32 %r
}

; make sure the previous opt doesn't take place for wrapped shifts

define i32 @t13(i32 %x) {
; CHECK-LABEL: @t13(
; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], 2
; CHECK-NEXT:    [[R:%.*]] = udiv i32 [[SHL]], [[X]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %shl = shl i32 %x, 2
  %r = udiv i32 %shl, %x
  ret i32 %r
}

define <2 x i32> @t14(<2 x i32> %x) {
; CHECK-LABEL: @t14(
; CHECK-NEXT:    ret <2 x i32> <i32 4, i32 8>
;
  %shl = shl nuw <2 x i32> %x, <i32 2, i32 3>
  %r = udiv <2 x i32> %shl, %x
  ret <2 x i32> %r
}

define i32 @t15(i32 %x, i32 %y) {
; CHECK-LABEL: @t15(
; CHECK-NEXT:    [[R:%.*]] = shl nuw i32 1, [[Y:%.*]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %shl = shl nuw i32 %x, %y
  %r = udiv i32 %shl, %x
  ret i32 %r
}

define <2 x i32> @t16(<2 x i32> %x, <2 x i32> %y) {
; CHECK-LABEL: @t16(
; CHECK-NEXT:    [[R:%.*]] = shl nuw <2 x i32> <i32 1, i32 1>, [[Y:%.*]]
; CHECK-NEXT:    ret <2 x i32> [[R]]
;
  %shl = shl nuw <2 x i32> %x, %y
  %r = udiv <2 x i32> %shl, %x
  ret <2 x i32> %r
}

; (X * Y) s/ (X << Z) --> Y s/ (1 << Z)

define i5 @sdiv_mul_shl_nsw(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @sdiv_mul_shl_nsw(
; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw i5 1, [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = sdiv i5 [[Y:%.*]], [[TMP1]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = mul nsw i5 %x, %y
  %m2 = shl nsw i5 %x, %z
  %d = sdiv i5 %m1, %m2
  ret i5 %d
}

; (Y * Z) s/ (X << Z) --> Y s/ (1 << Z)

define i5 @sdiv_mul_shl_nsw_exact_commute1(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @sdiv_mul_shl_nsw_exact_commute1(
; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw i5 1, [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = sdiv exact i5 [[Y:%.*]], [[TMP1]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = mul nsw i5 %y, %x
  %m2 = shl nsw i5 %x, %z
  %d = sdiv exact i5 %m1, %m2
  ret i5 %d
}

; negative test - shl is not commutative

define i5 @sdiv_mul_shl_nsw_commute2(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @sdiv_mul_shl_nsw_commute2(
; CHECK-NEXT:    [[M1:%.*]] = mul nsw i5 [[Y:%.*]], [[X:%.*]]
; CHECK-NEXT:    [[M2:%.*]] = shl nsw i5 [[Z:%.*]], [[X]]
; CHECK-NEXT:    [[D:%.*]] = sdiv i5 [[M1]], [[M2]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = mul nsw i5 %y, %x
  %m2 = shl nsw i5 %z, %x
  %d = sdiv i5 %m1, %m2
  ret i5 %d
}

; extra use is ok

define i8 @sdiv_mul_shl_nsw_use1(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @sdiv_mul_shl_nsw_use1(
; CHECK-NEXT:    [[M1:%.*]] = mul nsw i8 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    call void @use(i8 [[M1]])
; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw i8 1, [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[Y]], [[TMP1]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %m1 = mul nsw i8 %x, %y
  call void @use(i8 %m1)
  %m2 = shl nsw i8 %x, %z
  %d = sdiv i8 %m1, %m2
  ret i8 %d
}

; extra use is ok

define i8 @sdiv_mul_shl_nsw_use2(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @sdiv_mul_shl_nsw_use2(
; CHECK-NEXT:    [[M2:%.*]] = shl nsw i8 [[X:%.*]], [[Z:%.*]]
; CHECK-NEXT:    call void @use(i8 [[M2]])
; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw i8 1, [[Z]]
; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[Y:%.*]], [[TMP1]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %m1 = mul nsw i8 %x, %y
  %m2 = shl nsw i8 %x, %z
  call void @use(i8 %m2)
  %d = sdiv i8 %m1, %m2
  ret i8 %d
}

; negative test - both operands can't have extra uses

define i8 @sdiv_mul_shl_nsw_use3(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @sdiv_mul_shl_nsw_use3(
; CHECK-NEXT:    [[M1:%.*]] = mul nsw i8 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    call void @use(i8 [[M1]])
; CHECK-NEXT:    [[M2:%.*]] = shl nsw i8 [[X]], [[Z:%.*]]
; CHECK-NEXT:    call void @use(i8 [[M2]])
; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[M1]], [[M2]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %m1 = mul nsw i8 %x, %y
  call void @use(i8 %m1)
  %m2 = shl nsw i8 %x, %z
  call void @use(i8 %m2)
  %d = sdiv i8 %m1, %m2
  ret i8 %d
}

; negative test - shl must be divisor

define i5 @sdiv_shl_mul_nsw(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @sdiv_shl_mul_nsw(
; CHECK-NEXT:    [[M1:%.*]] = shl nsw i5 [[Z:%.*]], [[X:%.*]]
; CHECK-NEXT:    [[M2:%.*]] = mul nsw i5 [[X]], [[Y:%.*]]
; CHECK-NEXT:    [[D:%.*]] = sdiv i5 [[M1]], [[M2]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = shl nsw i5 %z, %x
  %m2 = mul nsw i5 %x, %y
  %d = sdiv i5 %m1, %m2
  ret i5 %d
}

; negative test - wrong no-wrap

define i5 @sdiv_mul_shl_missing_nsw1(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @sdiv_mul_shl_missing_nsw1(
; CHECK-NEXT:    [[M1:%.*]] = mul nsw i5 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    [[M2:%.*]] = shl nuw i5 [[Y]], [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = sdiv i5 [[M1]], [[M2]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = mul nsw i5 %x, %y
  %m2 = shl nuw i5 %y, %z
  %d = sdiv i5 %m1, %m2
  ret i5 %d
}

; negative test - wrong no-wrap

define i5 @sdiv_mul_shl_missing_nsw2(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @sdiv_mul_shl_missing_nsw2(
; CHECK-NEXT:    [[M1:%.*]] = mul nuw i5 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    [[M2:%.*]] = shl nsw i5 [[Y]], [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = sdiv i5 [[M1]], [[M2]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = mul nuw i5 %x, %y
  %m2 = shl nsw i5 %y, %z
  %d = sdiv i5 %m1, %m2
  ret i5 %d
}

; (X * Y) u/ (X << Z) --> Y u>> Z

define i5 @udiv_mul_shl_nuw(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @udiv_mul_shl_nuw(
; CHECK-NEXT:    [[D:%.*]] = lshr i5 [[Y:%.*]], [[Z:%.*]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = mul nuw i5 %x, %y
  %m2 = shl nuw i5 %x, %z
  %d = udiv i5 %m1, %m2
  ret i5 %d
}

; (Y * X) u/ (X << Z) --> Y u>> Z

define i5 @udiv_mul_shl_nuw_exact_commute1(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @udiv_mul_shl_nuw_exact_commute1(
; CHECK-NEXT:    [[D:%.*]] = lshr exact i5 [[Y:%.*]], [[Z:%.*]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = mul nuw i5 %y, %x
  %m2 = shl nuw i5 %x, %z
  %d = udiv exact i5 %m1, %m2
  ret i5 %d
}

; negative test - shl is not commutative

define i5 @udiv_mul_shl_nuw_commute2(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @udiv_mul_shl_nuw_commute2(
; CHECK-NEXT:    [[M1:%.*]] = mul nuw i5 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    [[M2:%.*]] = shl nuw i5 [[Z:%.*]], [[X]]
; CHECK-NEXT:    [[D:%.*]] = udiv i5 [[M1]], [[M2]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = mul nuw i5 %x, %y
  %m2 = shl nuw i5 %z, %x
  %d = udiv i5 %m1, %m2
  ret i5 %d
}

; extra uses are ok

define i8 @udiv_mul_shl_nsw_use1(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_mul_shl_nsw_use1(
; CHECK-NEXT:    [[M1:%.*]] = mul nuw i8 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    call void @use(i8 [[M1]])
; CHECK-NEXT:    [[D:%.*]] = lshr i8 [[Y]], [[Z:%.*]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %m1 = mul nuw i8 %x, %y
  call void @use(i8 %m1)
  %m2 = shl nuw i8 %x, %z
  %d = udiv i8 %m1, %m2
  ret i8 %d
}

; extra uses are ok

define i8 @udiv_mul_shl_nsw_use2(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_mul_shl_nsw_use2(
; CHECK-NEXT:    [[M2:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]
; CHECK-NEXT:    call void @use(i8 [[M2]])
; CHECK-NEXT:    [[D:%.*]] = lshr i8 [[Y:%.*]], [[Z]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %m1 = mul nuw i8 %x, %y
  %m2 = shl nuw i8 %x, %z
  call void @use(i8 %m2)
  %d = udiv i8 %m1, %m2
  ret i8 %d
}

; extra uses are ok

define i8 @udiv_mul_shl_nsw_use3(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_mul_shl_nsw_use3(
; CHECK-NEXT:    [[M1:%.*]] = mul nuw i8 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    call void @use(i8 [[M1]])
; CHECK-NEXT:    [[M2:%.*]] = shl nuw i8 [[X]], [[Z:%.*]]
; CHECK-NEXT:    call void @use(i8 [[M2]])
; CHECK-NEXT:    [[D:%.*]] = lshr i8 [[Y]], [[Z]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %m1 = mul nuw i8 %x, %y
  call void @use(i8 %m1)
  %m2 = shl nuw i8 %x, %z
  call void @use(i8 %m2)
  %d = udiv i8 %m1, %m2
  ret i8 %d
}

; (X << Z) / (X * Y) -> (1 << Z) / Y

define i5 @udiv_shl_mul_nuw(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @udiv_shl_mul_nuw(
; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw i5 1, [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = udiv i5 [[TMP1]], [[Y:%.*]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = shl nuw i5 %x, %z
  %m2 = mul nuw i5 %x, %y
  %d = udiv i5 %m1, %m2
  ret i5 %d
}

define i5 @udiv_shl_mul_nuw_swap(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @udiv_shl_mul_nuw_swap(
; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw i5 1, [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = udiv i5 [[TMP1]], [[Y:%.*]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = shl nuw i5 %x, %z
  %m2 = mul nuw i5 %y, %x
  %d = udiv i5 %m1, %m2
  ret i5 %d
}

define i5 @udiv_shl_mul_nuw_exact(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @udiv_shl_mul_nuw_exact(
; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw i5 1, [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = udiv exact i5 [[TMP1]], [[Y:%.*]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = shl nuw i5 %x, %z
  %m2 = mul nuw i5 %x, %y
  %d = udiv exact i5 %m1, %m2
  ret i5 %d
}

define <2 x i4> @udiv_shl_mul_nuw_vec(<2 x i4> %x, <2 x i4> %y, <2 x i4> %z) {
; CHECK-LABEL: @udiv_shl_mul_nuw_vec(
; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw <2 x i4> <i4 1, i4 1>, [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = udiv <2 x i4> [[TMP1]], [[Y:%.*]]
; CHECK-NEXT:    ret <2 x i4> [[D]]
;
  %m1 = shl nuw <2 x i4> %x, %z
  %m2 = mul nuw <2 x i4> %y, %x
  %d = udiv <2 x i4> %m1, %m2
  ret <2 x i4> %d
}

define i8 @udiv_shl_mul_nuw_extra_use_of_shl(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_shl_mul_nuw_extra_use_of_shl(
; CHECK-NEXT:    [[M1:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]
; CHECK-NEXT:    call void @use(i8 [[M1]])
; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw i8 1, [[Z]]
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[TMP1]], [[Y:%.*]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %m1 = shl nuw i8 %x, %z
  call void @use(i8 %m1)
  %m2 = mul nuw i8 %y, %x
  %d = udiv i8 %m1, %m2
  ret i8 %d
}

; negative test - extra use

define i8 @udiv_shl_mul_nuw_extra_use_of_mul(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_shl_mul_nuw_extra_use_of_mul(
; CHECK-NEXT:    [[M1:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]
; CHECK-NEXT:    [[M2:%.*]] = mul nuw i8 [[Y:%.*]], [[X]]
; CHECK-NEXT:    call void @use(i8 [[M2]])
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[M1]], [[M2]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %m1 = shl nuw i8 %x, %z
  %m2 = mul nuw i8 %y, %x
  call void @use(i8 %m2)
  %d = udiv i8 %m1, %m2
  ret i8 %d
}

define i8 @udiv_shl_mul_nuw_extra_use(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_shl_mul_nuw_extra_use(
; CHECK-NEXT:    [[M1:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]
; CHECK-NEXT:    call void @use(i8 [[M1]])
; CHECK-NEXT:    [[M2:%.*]] = mul nuw i8 [[Y:%.*]], [[X]]
; CHECK-NEXT:    call void @use(i8 [[M2]])
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[M1]], [[M2]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %m1 = shl nuw i8 %x, %z
  call void @use(i8 %m1)
  %m2 = mul nuw i8 %y, %x
  call void @use(i8 %m2)
  %d = udiv i8 %m1, %m2
  ret i8 %d
}

; negative test - sdiv

define i5 @sdiv_shl_mul_nuw(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @sdiv_shl_mul_nuw(
; CHECK-NEXT:    [[M1:%.*]] = shl nuw i5 [[X:%.*]], [[Z:%.*]]
; CHECK-NEXT:    [[M2:%.*]] = mul nuw i5 [[X]], [[Y:%.*]]
; CHECK-NEXT:    [[D:%.*]] = sdiv i5 [[M1]], [[M2]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = shl nuw i5 %x, %z
  %m2 = mul nuw i5 %x, %y
  %d = sdiv i5 %m1, %m2
  ret i5 %d
}

; negative test - wrong no-wrap

define i5 @udiv_mul_shl_missing_nsw1(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @udiv_mul_shl_missing_nsw1(
; CHECK-NEXT:    [[M1:%.*]] = mul nsw i5 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    [[M2:%.*]] = shl nuw i5 [[Y]], [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = udiv i5 [[M1]], [[M2]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = mul nsw i5 %x, %y
  %m2 = shl nuw i5 %y, %z
  %d = udiv i5 %m1, %m2
  ret i5 %d
}

; negative test - wrong no-wrap

define i5 @udiv_mul_shl_missing_nsw2(i5 %x, i5 %y, i5 %z) {
; CHECK-LABEL: @udiv_mul_shl_missing_nsw2(
; CHECK-NEXT:    [[M1:%.*]] = mul nuw i5 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    [[M2:%.*]] = shl nsw i5 [[Y]], [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = udiv i5 [[M1]], [[M2]]
; CHECK-NEXT:    ret i5 [[D]]
;
  %m1 = mul nuw i5 %x, %y
  %m2 = shl nsw i5 %y, %z
  %d = udiv i5 %m1, %m2
  ret i5 %d
}

define i8 @udiv_shl_nuw(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_shl_nuw(
; CHECK-NEXT:    [[S:%.*]] = shl nuw i8 [[Y:%.*]], [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[X:%.*]], [[S]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %s = shl nuw i8 %y, %z
  %d = udiv i8 %x, %s
  ret i8 %d
}

define <2 x i4> @udiv_shl_nuw_exact(<2 x i4> %x, <2 x i4> %y, <2 x i4> %z) {
; CHECK-LABEL: @udiv_shl_nuw_exact(
; CHECK-NEXT:    [[S:%.*]] = shl nuw <2 x i4> [[Y:%.*]], [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = udiv exact <2 x i4> [[X:%.*]], [[S]]
; CHECK-NEXT:    ret <2 x i4> [[D]]
;
  %s = shl nuw <2 x i4> %y, %z
  %d = udiv exact <2 x i4> %x, %s
  ret <2 x i4> %d
}

define i8 @udiv_shl(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_shl(
; CHECK-NEXT:    [[S:%.*]] = shl i8 [[Y:%.*]], [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[X:%.*]], [[S]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %s = shl i8 %y, %z
  %d = udiv i8 %x, %s
  ret i8 %d
}

define i8 @udiv_shl_nuw_use(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_shl_nuw_use(
; CHECK-NEXT:    [[S:%.*]] = shl nuw i8 [[Y:%.*]], [[Z:%.*]]
; CHECK-NEXT:    call void @use(i8 [[S]])
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[X:%.*]], [[S]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %s = shl nuw i8 %y, %z
  call void @use(i8 %s)
  %d = udiv i8 %x, %s
  ret i8 %d
}

; ((X * Y) >> Z) / X --> Y >> Z

define i8 @udiv_lshr_mul_nuw(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_lshr_mul_nuw(
; CHECK-NEXT:    [[DIV:%.*]] = lshr i8 [[Y:%.*]], [[Z:%.*]]
; CHECK-NEXT:    ret i8 [[DIV]]
;
  %m = mul nuw i8 %x, %y
  %s = lshr i8 %m, %z
  %div = udiv i8 %s, %x
  ret i8 %div
}

; ((Y * X) >> Z) / X --> Y >> Z

define <2 x i4> @udiv_lshr_mul_nuw_exact_commute1(<2 x i4> %x, <2 x i4> %y, <2 x i4> %z) {
; CHECK-LABEL: @udiv_lshr_mul_nuw_exact_commute1(
; CHECK-NEXT:    [[DIV:%.*]] = lshr exact <2 x i4> [[Y:%.*]], [[Z:%.*]]
; CHECK-NEXT:    ret <2 x i4> [[DIV]]
;
  %m = mul nuw <2 x i4> %y, %x
  %s = lshr exact <2 x i4> %m, %z
  %div = udiv exact <2 x i4> %s, %x
  ret <2 x i4> %div
}

; negative test - mul is shifted amount, not shifted value

define i8 @udiv_lshr_mul_nuw_commute2(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_lshr_mul_nuw_commute2(
; CHECK-NEXT:    [[M:%.*]] = mul nuw i8 [[Y:%.*]], [[X:%.*]]
; CHECK-NEXT:    [[S:%.*]] = lshr i8 [[Z:%.*]], [[M]]
; CHECK-NEXT:    [[DIV:%.*]] = udiv i8 [[S]], [[X]]
; CHECK-NEXT:    ret i8 [[DIV]]
;
  %m = mul nuw i8 %y, %x
  %s = lshr i8 %z, %m
  %div = udiv i8 %s, %x
  ret i8 %div
}

; extra uses are ok

define i8 @udiv_lshr_mul_nuw_use1(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_lshr_mul_nuw_use1(
; CHECK-NEXT:    [[M:%.*]] = mul nuw i8 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    call void @use(i8 [[M]])
; CHECK-NEXT:    [[DIV:%.*]] = lshr i8 [[Y]], [[Z:%.*]]
; CHECK-NEXT:    ret i8 [[DIV]]
;
  %m = mul nuw i8 %x, %y
  call void @use(i8 %m)
  %s = lshr i8 %m, %z
  %div = udiv i8 %s, %x
  ret i8 %div
}

; extra uses are ok

define i8 @udiv_lshr_mul_nuw_use2(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_lshr_mul_nuw_use2(
; CHECK-NEXT:    [[M:%.*]] = mul nuw i8 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    [[S:%.*]] = lshr i8 [[M]], [[Z:%.*]]
; CHECK-NEXT:    call void @use(i8 [[S]])
; CHECK-NEXT:    [[DIV:%.*]] = lshr i8 [[Y]], [[Z]]
; CHECK-NEXT:    ret i8 [[DIV]]
;
  %m = mul nuw i8 %x, %y
  %s = lshr i8 %m, %z
  call void @use(i8 %s)
  %div = udiv i8 %s, %x
  ret i8 %div
}

; extra uses are ok

define i8 @udiv_lshr_mul_nuw_use3(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_lshr_mul_nuw_use3(
; CHECK-NEXT:    [[M:%.*]] = mul nuw i8 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    call void @use(i8 [[M]])
; CHECK-NEXT:    [[S:%.*]] = lshr i8 [[M]], [[Z:%.*]]
; CHECK-NEXT:    call void @use(i8 [[S]])
; CHECK-NEXT:    [[DIV:%.*]] = lshr i8 [[Y]], [[Z]]
; CHECK-NEXT:    ret i8 [[DIV]]
;
  %m = mul nuw i8 %x, %y
  call void @use(i8 %m)
  %s = lshr i8 %m, %z
  call void @use(i8 %s)
  %div = udiv i8 %s, %x
  ret i8 %div
}

; negative test - must have nuw

define i8 @udiv_lshr_mul_nsw(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_lshr_mul_nsw(
; CHECK-NEXT:    [[M:%.*]] = mul nsw i8 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    [[S:%.*]] = lshr i8 [[M]], [[Z:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = udiv i8 [[S]], [[X]]
; CHECK-NEXT:    ret i8 [[DIV]]
;
  %m = mul nsw i8 %x, %y
  %s = lshr i8 %m, %z
  %div = udiv i8 %s, %x
  ret i8 %div
}

; negative test - doesn't fold with signed div

define i8 @sdiv_lshr_mul_nsw(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @sdiv_lshr_mul_nsw(
; CHECK-NEXT:    [[M:%.*]] = mul nsw i8 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    [[S:%.*]] = lshr i8 [[M]], [[Z:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = sdiv i8 [[S]], [[X]]
; CHECK-NEXT:    ret i8 [[DIV]]
;
  %m = mul nsw i8 %x, %y
  %s = lshr i8 %m, %z
  %div = sdiv i8 %s, %x
  ret i8 %div
}

; (X << Z) / (Y << Z) --> X / Y

define i8 @sdiv_shl_shl_nsw2_nuw(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @sdiv_shl_shl_nsw2_nuw(
; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %xz = shl nsw i8 %x, %z
  %yz = shl nsw nuw i8 %y, %z
  %d = sdiv i8 %xz, %yz
  ret i8 %d
}

; extra uses are ok and 'exact' propagates

define i8 @sdiv_shl_shl_nsw2_nuw_exact_use(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @sdiv_shl_shl_nsw2_nuw_exact_use(
; CHECK-NEXT:    [[XZ:%.*]] = shl nsw i8 [[X:%.*]], [[Z:%.*]]
; CHECK-NEXT:    call void @use(i8 [[XZ]])
; CHECK-NEXT:    [[D:%.*]] = sdiv exact i8 [[X]], [[Y:%.*]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %xz = shl nsw i8 %x, %z
  call void @use(i8 %xz)
  %yz = shl nsw nuw i8 %y, %z
  %d = sdiv exact i8 %xz, %yz
  ret i8 %d
}

; negative test - wrong wrap

define i8 @sdiv_shl_shl_nsw_nuw2(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @sdiv_shl_shl_nsw_nuw2(
; CHECK-NEXT:    [[XZ:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]
; CHECK-NEXT:    [[YZ:%.*]] = shl nuw nsw i8 [[Y:%.*]], [[Z]]
; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[XZ]], [[YZ]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %xz = shl nuw i8 %x, %z
  %yz = shl nsw nuw i8 %y, %z
  %d = sdiv i8 %xz, %yz
  ret i8 %d
}

; negative test - wrong wrap

define i8 @sdiv_shl_shl_nsw_nuw(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @sdiv_shl_shl_nsw_nuw(
; CHECK-NEXT:    [[XZ:%.*]] = shl nsw i8 [[X:%.*]], [[Z:%.*]]
; CHECK-NEXT:    [[YZ:%.*]] = shl nuw i8 [[Y:%.*]], [[Z]]
; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[XZ]], [[YZ]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %xz = shl nsw i8 %x, %z
  %yz = shl nuw i8 %y, %z
  %d = sdiv i8 %xz, %yz
  ret i8 %d
}

; negative test - wrong wrap

define i8 @sdiv_shl_shl_nuw_nsw2(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @sdiv_shl_shl_nuw_nsw2(
; CHECK-NEXT:    [[XZ:%.*]] = shl nuw nsw i8 [[X:%.*]], [[Z:%.*]]
; CHECK-NEXT:    [[YZ:%.*]] = shl nsw i8 [[Y:%.*]], [[Z]]
; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[XZ]], [[YZ]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %xz = shl nuw nsw i8 %x, %z
  %yz = shl nsw i8 %y, %z
  %d = sdiv i8 %xz, %yz
  ret i8 %d
}

; (X << Z) / (Y << Z) --> X / Y

define <2 x i8> @udiv_shl_shl_nuw2(<2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
; CHECK-LABEL: @udiv_shl_shl_nuw2(
; CHECK-NEXT:    [[D:%.*]] = udiv <2 x i8> [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    ret <2 x i8> [[D]]
;
  %xz = shl nuw <2 x i8> %x, %z
  %yz = shl nuw <2 x i8> %y, %z
  %d = udiv <2 x i8> %xz, %yz
  ret <2 x i8> %d
}

; extra uses are ok and 'exact' propagates

define i8 @udiv_shl_shl_nuw2_exact_use2(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_shl_shl_nuw2_exact_use2(
; CHECK-NEXT:    [[XZ:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]
; CHECK-NEXT:    call void @use(i8 [[XZ]])
; CHECK-NEXT:    [[YZ:%.*]] = shl nuw i8 [[Y:%.*]], [[Z]]
; CHECK-NEXT:    call void @use(i8 [[YZ]])
; CHECK-NEXT:    [[D:%.*]] = udiv exact i8 [[X]], [[Y]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %xz = shl nuw i8 %x, %z
  call void @use(i8 %xz)
  %yz = shl nuw i8 %y, %z
  call void @use(i8 %yz)
  %d = udiv exact i8 %xz, %yz
  ret i8 %d
}

; negative test - wrong wrap

define i8 @udiv_shl_shl_nuw_nsw(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_shl_shl_nuw_nsw(
; CHECK-NEXT:    [[XZ:%.*]] = shl nuw i8 [[X:%.*]], [[Z:%.*]]
; CHECK-NEXT:    [[YZ:%.*]] = shl nsw i8 [[Y:%.*]], [[Z]]
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[XZ]], [[YZ]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %xz = shl nuw i8 %x, %z
  %yz = shl nsw i8 %y, %z
  %d = udiv i8 %xz, %yz
  ret i8 %d
}

; negative test - wrong wrap

define i8 @udiv_shl_shl_nsw_nuw(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_shl_shl_nsw_nuw(
; CHECK-NEXT:    [[XZ:%.*]] = shl nsw i8 [[X:%.*]], [[Z:%.*]]
; CHECK-NEXT:    [[YZ:%.*]] = shl nuw i8 [[Y:%.*]], [[Z]]
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[XZ]], [[YZ]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %xz = shl nsw i8 %x, %z
  %yz = shl nuw i8 %y, %z
  %d = udiv i8 %xz, %yz
  ret i8 %d
}

define i8 @udiv_shl_shl_nuw_nsw2(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_shl_shl_nuw_nsw2(
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %xz = shl nuw nsw i8 %x, %z
  %yz = shl nsw i8 %y, %z
  %d = udiv i8 %xz, %yz
  ret i8 %d
}

; TODO: X / (Y << Z) --> (X >> Z) / Y
; https://alive2.llvm.org/ce/z/FjoN_A

define i8 @udiv_shl_nuw_divisor(i8 %x, i8 %y, i8 %z) {
; CHECK-LABEL: @udiv_shl_nuw_divisor(
; CHECK-NEXT:    [[S:%.*]] = shl nuw i8 [[Y:%.*]], [[Z:%.*]]
; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[X:%.*]], [[S]]
; CHECK-NEXT:    ret i8 [[D]]
;
  %s = shl nuw i8 %y, %z
  %d = udiv i8 %x, %s
  ret i8 %d
}

define i8 @udiv_fail_shl_overflow(i8 %x, i8 %y) {
; CHECK-LABEL: @udiv_fail_shl_overflow(
; CHECK-NEXT:    [[SHL:%.*]] = shl i8 2, [[Y:%.*]]
; CHECK-NEXT:    [[MIN:%.*]] = call i8 @llvm.umax.i8(i8 [[SHL]], i8 1)
; CHECK-NEXT:    [[MUL:%.*]] = udiv i8 [[X:%.*]], [[MIN]]
; CHECK-NEXT:    ret i8 [[MUL]]
;
  %shl = shl i8 2, %y
  %min = call i8 @llvm.umax.i8(i8 %shl, i8 1)
  %mul = udiv i8 %x, %min
  ret i8 %mul
}

define i8 @udiv_shl_no_overflow(i8 %x, i8 %y) {
; CHECK-LABEL: @udiv_shl_no_overflow(
; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[Y:%.*]], 1
; CHECK-NEXT:    [[MUL1:%.*]] = lshr i8 [[X:%.*]], [[TMP1]]
; CHECK-NEXT:    ret i8 [[MUL1]]
;
  %shl = shl nuw i8 2, %y
  %min = call i8 @llvm.umax.i8(i8 %shl, i8 1)
  %mul = udiv i8 %x, %min
  ret i8 %mul
}

; (X<<Y) / (X<<Z) -> 1 << Y >> Z

define i32 @sdiv_shl_pair_const(i32 %a) {
; CHECK-LABEL: @sdiv_shl_pair_const(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    ret i32 2
;
entry:
  %lhs = shl nsw i32 %a, 2
  %rhs = shl nsw i32 %a, 1
  %div = sdiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @udiv_shl_pair_const(i32 %a) {
; CHECK-LABEL: @udiv_shl_pair_const(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    ret i32 2
;
entry:
  %lhs = shl nuw i32 %a, 2
  %rhs = shl nuw i32 %a, 1
  %div = udiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @sdiv_shl_pair1(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @sdiv_shl_pair1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[SHL_DIVIDEND:%.*]] = shl nuw nsw i32 1, [[X:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nsw i32 %a, %x
  %rhs = shl nuw nsw i32 %a, %y
  %div = sdiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @sdiv_shl_pair2(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @sdiv_shl_pair2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[SHL_DIVIDEND:%.*]] = shl nuw nsw i32 1, [[X:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nuw nsw i32 %a, %x
  %rhs = shl nsw i32 %a, %y
  %div = sdiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @sdiv_shl_pair3(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @sdiv_shl_pair3(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[SHL_DIVIDEND:%.*]] = shl nuw i32 1, [[X:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nsw i32 %a, %x
  %rhs = shl nsw i32 %a, %y
  %div = sdiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @sdiv_shl_no_pair_fail(i32 %a, i32 %b, i32 %x, i32 %y) {
; CHECK-LABEL: @sdiv_shl_no_pair_fail(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LHS:%.*]] = shl nuw nsw i32 [[A:%.*]], [[X:%.*]]
; CHECK-NEXT:    [[RHS:%.*]] = shl nuw i32 [[B:%.*]], [[Y:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[LHS]], [[RHS]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nuw nsw i32 %a, %x
  %rhs = shl nuw i32 %b, %y
  %div = sdiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @udiv_shl_pair1(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @udiv_shl_pair1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[SHL_DIVIDEND:%.*]] = shl nuw i32 1, [[X:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nuw i32 %a, %x
  %rhs = shl nuw i32 %a, %y
  %div = udiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @udiv_shl_pair2(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @udiv_shl_pair2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[SHL_DIVIDEND:%.*]] = shl nuw nsw i32 1, [[X:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nuw nsw i32 %a, %x
  %rhs = shl nuw i32 %a, %y
  %div = udiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @udiv_shl_pair3(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @udiv_shl_pair3(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[SHL_DIVIDEND:%.*]] = shl nuw i32 1, [[X:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nuw i32 %a, %x
  %rhs = shl nuw nsw i32 %a, %y
  %div = udiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @sdiv_shl_pair_overflow_fail1(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @sdiv_shl_pair_overflow_fail1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LHS:%.*]] = shl i32 [[A:%.*]], [[X:%.*]]
; CHECK-NEXT:    [[RHS:%.*]] = shl nsw i32 [[A]], [[Y:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[LHS]], [[RHS]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl i32 %a, %x
  %rhs = shl nsw i32 %a, %y
  %div = sdiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @sdiv_shl_pair_overflow_fail2(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @sdiv_shl_pair_overflow_fail2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LHS:%.*]] = shl nsw i32 [[A:%.*]], [[X:%.*]]
; CHECK-NEXT:    [[RHS:%.*]] = shl nuw i32 [[A]], [[Y:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[LHS]], [[RHS]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nsw i32 %a, %x
  %rhs = shl nuw i32 %a, %y
  %div = sdiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @udiv_shl_pair_overflow_fail1(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @udiv_shl_pair_overflow_fail1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LHS:%.*]] = shl nsw i32 [[A:%.*]], [[X:%.*]]
; CHECK-NEXT:    [[RHS:%.*]] = shl nuw i32 [[A]], [[Y:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[LHS]], [[RHS]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nsw i32 %a, %x
  %rhs = shl nuw i32 %a, %y
  %div = udiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @udiv_shl_pair_overflow_fail2(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @udiv_shl_pair_overflow_fail2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LHS:%.*]] = shl nsw i32 [[A:%.*]], [[X:%.*]]
; CHECK-NEXT:    [[RHS:%.*]] = shl i32 [[A]], [[Y:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[LHS]], [[RHS]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nsw i32 %a, %x
  %rhs = shl i32 %a, %y
  %div = udiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @udiv_shl_pair_overflow_fail3(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @udiv_shl_pair_overflow_fail3(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LHS:%.*]] = shl nuw nsw i32 [[A:%.*]], [[X:%.*]]
; CHECK-NEXT:    [[RHS:%.*]] = shl i32 [[A]], [[Y:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[LHS]], [[RHS]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nuw nsw i32 %a, %x
  %rhs = shl i32 %a, %y
  %div = udiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @sdiv_shl_pair_multiuse1(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @sdiv_shl_pair_multiuse1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LHS:%.*]] = shl nuw nsw i32 [[A:%.*]], [[X:%.*]]
; CHECK-NEXT:    call void @use32(i32 [[LHS]])
; CHECK-NEXT:    [[SHL_DIVIDEND:%.*]] = shl nuw nsw i32 1, [[X]]
; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y:%.*]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nuw nsw i32 %a, %x
  call void @use32(i32 %lhs)
  %rhs = shl nsw i32 %a, %y
  %div = sdiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @sdiv_shl_pair_multiuse2(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @sdiv_shl_pair_multiuse2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[RHS:%.*]] = shl nsw i32 [[A:%.*]], [[Y:%.*]]
; CHECK-NEXT:    call void @use32(i32 [[RHS]])
; CHECK-NEXT:    [[SHL_DIVIDEND:%.*]] = shl nuw nsw i32 1, [[X:%.*]]
; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nuw nsw i32 %a, %x
  %rhs = shl nsw i32 %a, %y
  call void @use32(i32 %rhs)
  %div = sdiv i32 %lhs, %rhs
  ret i32 %div
}

define i32 @sdiv_shl_pair_multiuse3(i32 %a, i32 %x, i32 %y) {
; CHECK-LABEL: @sdiv_shl_pair_multiuse3(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[LHS:%.*]] = shl nuw nsw i32 [[A:%.*]], [[X:%.*]]
; CHECK-NEXT:    [[RHS:%.*]] = shl nsw i32 [[A]], [[Y:%.*]]
; CHECK-NEXT:    call void @use32(i32 [[LHS]])
; CHECK-NEXT:    call void @use32(i32 [[RHS]])
; CHECK-NEXT:    [[SHL_DIVIDEND:%.*]] = shl nuw nsw i32 1, [[X]]
; CHECK-NEXT:    [[DIV:%.*]] = lshr i32 [[SHL_DIVIDEND]], [[Y]]
; CHECK-NEXT:    ret i32 [[DIV]]
;
entry:
  %lhs = shl nuw nsw i32 %a, %x
  %rhs = shl nsw i32 %a, %y
  call void @use32(i32 %lhs)
  call void @use32(i32 %rhs)
  %div = sdiv i32 %lhs, %rhs
  ret i32 %div
}

@a = external global i32
define i32 @pr69291() {
; CHECK-LABEL: @pr69291(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    ret i32 1
;
entry:
  %conv = load i32, ptr @a, align 1
  %add = shl nuw nsw i32 %conv, 1
  %add2 = shl nuw nsw i32 %conv, 1
  %div = sdiv i32 %add, %add2
  ret i32 %div
}