shift.ll

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

define <4 x i32> @lshr_non_splat_vector(<4 x i32> %A) {
; CHECK-LABEL: @lshr_non_splat_vector(
; CHECK-NEXT:    [[B:%.*]] = lshr <4 x i32> [[A:%.*]], <i32 32, i32 1, i32 2, i32 3>
; CHECK-NEXT:    ret <4 x i32> [[B]]
;
  %B = lshr <4 x i32> %A, <i32 32, i32 1, i32 2, i32 3>
  ret <4 x i32> %B
}

define <4 x i32> @shl_non_splat_vector(<4 x i32> %A) {
; CHECK-LABEL: @shl_non_splat_vector(
; CHECK-NEXT:    [[B:%.*]] = shl <4 x i32> [[A:%.*]], <i32 32, i32 1, i32 2, i32 3>
; CHECK-NEXT:    ret <4 x i32> [[B]]
;
  %B = shl <4 x i32> %A, <i32 32, i32 1, i32 2, i32 3>
  ret <4 x i32> %B
}

define i32 @test6(i32 %A) {
; CHECK-LABEL: @test6(
; CHECK-NEXT:    [[C:%.*]] = mul i32 [[A:%.*]], 6
; CHECK-NEXT:    ret i32 [[C]]
;
  %B = shl i32 %A, 1      ;; convert to an mul instruction
  %C = mul i32 %B, 3
  ret i32 %C
}

define i32 @test6a(i32 %A) {
; CHECK-LABEL: @test6a(
; CHECK-NEXT:    [[C:%.*]] = mul i32 [[A:%.*]], 6
; CHECK-NEXT:    ret i32 [[C]]
;
  %B = mul i32 %A, 3
  %C = shl i32 %B, 1      ;; convert to an mul instruction
  ret i32 %C
}

;; (A << 5) << 3 === A << 8 == 0
define i8 @test8(i8 %A) {
; CHECK-LABEL: @test8(
; CHECK-NEXT:    ret i8 0
;
  %B = shl i8 %A, 5
  %C = shl i8 %B, 3
  ret i8 %C
}

;; (A << 7) >> 7 === A & 1
define i8 @test9(i8 %A) {
; CHECK-LABEL: @test9(
; CHECK-NEXT:    [[B:%.*]] = and i8 [[A:%.*]], 1
; CHECK-NEXT:    ret i8 [[B]]
;
  %B = shl i8 %A, 7
  %C = lshr i8 %B, 7
  ret i8 %C
}

;; (A >> 7) << 7 === A & 128

define i8 @test10(i8 %A) {
; CHECK-LABEL: @test10(
; CHECK-NEXT:    [[B:%.*]] = and i8 [[A:%.*]], -128
; CHECK-NEXT:    ret i8 [[B]]
;
  %B = lshr i8 %A, 7
  %C = shl i8 %B, 7
  ret i8 %C
}

;; Allow the simplification when the lshr shift is exact.
define i8 @test10a(i8 %A) {
; CHECK-LABEL: @test10a(
; CHECK-NEXT:    ret i8 [[A:%.*]]
;
  %B = lshr exact i8 %A, 7
  %C = shl i8 %B, 7
  ret i8 %C
}

;; (A >> 3) << 4 === (A & 0x1F) << 1
define i8 @test11(i8 %x) {
; CHECK-LABEL: @test11(
; CHECK-NEXT:    [[TMP1:%.*]] = mul i8 [[X:%.*]], 6
; CHECK-NEXT:    [[C:%.*]] = and i8 [[TMP1]], -16
; CHECK-NEXT:    ret i8 [[C]]
;
  %a = mul i8 %x, 3
  %B = lshr i8 %a, 3
  %C = shl i8 %B, 4
  ret i8 %C
}

;; Allow the simplification in InstCombine when the lshr shift is exact.
define i8 @test11a(i8 %A) {
; CHECK-LABEL: @test11a(
; CHECK-NEXT:    [[C:%.*]] = mul i8 [[A:%.*]], 6
; CHECK-NEXT:    ret i8 [[C]]
;
  %a = mul i8 %A, 3
  %B = lshr exact i8 %a, 3
  %C = shl i8 %B, 4
  ret i8 %C
}

;; (A >> 8) << 8 === A & -256
define i32 @test12(i32 %A) {
; CHECK-LABEL: @test12(
; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[A:%.*]], -256
; CHECK-NEXT:    ret i32 [[TMP1]]
;
  %B = ashr i32 %A, 8
  %C = shl i32 %B, 8
  ret i32 %C
}

;; ((A >>s 6) << 6 === (A & FFFFFFC0)
define i8 @shishi(i8 %x) {
; CHECK-LABEL: @shishi(
; CHECK-NEXT:    [[A:%.*]] = ashr i8 [[X:%.*]], 6
; CHECK-NEXT:    [[B:%.*]] = and i8 [[X]], -64
; CHECK-NEXT:    [[EXTRA_USE_OF_A:%.*]] = mul nsw i8 [[A]], 5
; CHECK-NEXT:    [[R:%.*]] = sdiv i8 [[EXTRA_USE_OF_A]], [[B]]
; CHECK-NEXT:    ret i8 [[R]]
;
  %a = ashr i8 %x, 6
  %b = shl i8 %a, 6
  %extra_use_of_a = mul i8 %a, 5
  %r = sdiv i8 %extra_use_of_a, %b
  ret i8 %r
}

;; (A >> 3) << 4 === (A & -8) * 2
define i8 @test13(i8 %x) {
; CHECK-LABEL: @test13(
; CHECK-NEXT:    [[TMP1:%.*]] = mul i8 [[X:%.*]], 6
; CHECK-NEXT:    [[C:%.*]] = and i8 [[TMP1]], -16
; CHECK-NEXT:    ret i8 [[C]]
;
  %a = mul i8 %x, 3
  %B = ashr i8 %a, 3
  %C = shl i8 %B, 4
  ret i8 %C
}

define i8 @test13a(i8 %A) {
; CHECK-LABEL: @test13a(
; CHECK-NEXT:    [[C:%.*]] = mul i8 [[A:%.*]], 6
; CHECK-NEXT:    ret i8 [[C]]
;
  %a = mul i8 %A, 3
  %B = ashr exact i8 %a, 3
  %C = shl i8 %B, 4
  ret i8 %C
}

;; D = ((B | 1234) << 4) === ((B << 4)|(1234 << 4)
define i32 @test14(i32 %A) {
; CHECK-LABEL: @test14(
; CHECK-NEXT:    [[B:%.*]] = and i32 [[A:%.*]], -19760
; CHECK-NEXT:    [[C:%.*]] = or i32 [[B]], 19744
; CHECK-NEXT:    ret i32 [[C]]
;
  %B = lshr i32 %A, 4
  %C = or i32 %B, 1234
  %D = shl i32 %C, 4
  ret i32 %D
}

;; D = ((B | 1234) << 4) === ((B << 4)|(1234 << 4)
define i32 @test14a(i32 %A) {
; CHECK-LABEL: @test14a(
; CHECK-NEXT:    [[C:%.*]] = and i32 [[A:%.*]], 77
; CHECK-NEXT:    ret i32 [[C]]
;
  %B = shl i32 %A, 4
  %C = and i32 %B, 1234
  %D = lshr i32 %C, 4
  ret i32 %D
}

define i32 @test15(i1 %C) {
; CHECK-LABEL: @test15(
; CHECK-NEXT:    [[A:%.*]] = select i1 [[C:%.*]], i32 12, i32 4
; CHECK-NEXT:    ret i32 [[A]]
;
  %A = select i1 %C, i32 3, i32 1
  %V = shl i32 %A, 2
  ret i32 %V
}

define i32 @test15a(i1 %C) {
; CHECK-LABEL: @test15a(
; CHECK-NEXT:    [[V:%.*]] = select i1 [[C:%.*]], i32 512, i32 128
; CHECK-NEXT:    ret i32 [[V]]
;
  %A = select i1 %C, i8 3, i8 1
  %shift.upgrd.4 = zext i8 %A to i32
  %V = shl i32 64, %shift.upgrd.4
  ret i32 %V
}

define i1 @test16(i32 %X) {
; CHECK-LABEL: @test16(
; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], 16
; CHECK-NEXT:    [[I_7:%.*]] = icmp ne i32 [[TMP1]], 0
; CHECK-NEXT:    ret i1 [[I_7]]
;
  %i.3 = ashr i32 %X, 4
  %i.6 = and i32 %i.3, 1
  %i.7 = icmp ne i32 %i.6, 0
  ret i1 %i.7
}

define i1 @test17(i32 %A) {
; CHECK-LABEL: @test17(
; CHECK-NEXT:    [[B_MASK:%.*]] = and i32 [[A:%.*]], -8
; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[B_MASK]], 9872
; CHECK-NEXT:    ret i1 [[C]]
;
  %B = lshr i32 %A, 3
  %C = icmp eq i32 %B, 1234
  ret i1 %C
}

define <2 x i1> @test17vec(<2 x i32> %A) {
; CHECK-LABEL: @test17vec(
; CHECK-NEXT:    [[B_MASK:%.*]] = and <2 x i32> [[A:%.*]], <i32 -8, i32 -8>
; CHECK-NEXT:    [[C:%.*]] = icmp eq <2 x i32> [[B_MASK]], <i32 9872, i32 9872>
; CHECK-NEXT:    ret <2 x i1> [[C]]
;
  %B = lshr <2 x i32> %A, <i32 3, i32 3>
  %C = icmp eq <2 x i32> %B, <i32 1234, i32 1234>
  ret <2 x i1> %C
}

define i1 @test18(i8 %A) {
; CHECK-LABEL: @test18(
; CHECK-NEXT:    ret i1 false
;
  %B = lshr i8 %A, 7
  ;; false
  %C = icmp eq i8 %B, 123
  ret i1 %C
}

define i1 @test19(i32 %A) {
; CHECK-LABEL: @test19(
; CHECK-NEXT:    [[C:%.*]] = icmp ult i32 [[A:%.*]], 4
; CHECK-NEXT:    ret i1 [[C]]
;
  %B = ashr i32 %A, 2
  ;; (X & -4) == 0
  %C = icmp eq i32 %B, 0
  ret i1 %C
}

define <2 x i1> @test19vec(<2 x i32> %A) {
; CHECK-LABEL: @test19vec(
; CHECK-NEXT:    [[C:%.*]] = icmp ult <2 x i32> [[A:%.*]], <i32 4, i32 4>
; CHECK-NEXT:    ret <2 x i1> [[C]]
;
  %B = ashr <2 x i32> %A, <i32 2, i32 2>
  %C = icmp eq <2 x i32> %B, zeroinitializer
  ret <2 x i1> %C
}

;; X >u ~4
define i1 @test19a(i32 %A) {
; CHECK-LABEL: @test19a(
; CHECK-NEXT:    [[C:%.*]] = icmp ugt i32 [[A:%.*]], -5
; CHECK-NEXT:    ret i1 [[C]]
;
  %B = ashr i32 %A, 2
  %C = icmp eq i32 %B, -1
  ret i1 %C
}

define <2 x i1> @test19a_vec(<2 x i32> %A) {
; CHECK-LABEL: @test19a_vec(
; CHECK-NEXT:    [[C:%.*]] = icmp ugt <2 x i32> [[A:%.*]], <i32 -5, i32 -5>
; CHECK-NEXT:    ret <2 x i1> [[C]]
;
  %B = ashr <2 x i32> %A, <i32 2, i32 2>
  %C = icmp eq <2 x i32> %B, <i32 -1, i32 -1>
  ret <2 x i1> %C
}

define i1 @test20(i8 %A) {
; CHECK-LABEL: @test20(
; CHECK-NEXT:    ret i1 false
;
  %B = ashr i8 %A, 7
  ;; false
  %C = icmp eq i8 %B, 123
  ret i1 %C
}

define i1 @test21(i8 %A) {
; CHECK-LABEL: @test21(
; CHECK-NEXT:    [[B_MASK:%.*]] = and i8 [[A:%.*]], 15
; CHECK-NEXT:    [[C:%.*]] = icmp eq i8 [[B_MASK]], 8
; CHECK-NEXT:    ret i1 [[C]]
;
  %B = shl i8 %A, 4
  %C = icmp eq i8 %B, -128
  ret i1 %C
}

define i1 @test22(i8 %A) {
; CHECK-LABEL: @test22(
; CHECK-NEXT:    [[B_MASK:%.*]] = and i8 [[A:%.*]], 15
; CHECK-NEXT:    [[C:%.*]] = icmp eq i8 [[B_MASK]], 0
; CHECK-NEXT:    ret i1 [[C]]
;
  %B = shl i8 %A, 4
  %C = icmp eq i8 %B, 0
  ret i1 %C
}

define i8 @test23(i32 %A) {
; CHECK-LABEL: @test23(
; CHECK-NEXT:    [[D:%.*]] = trunc i32 [[A:%.*]] to i8
; CHECK-NEXT:    ret i8 [[D]]
;
  ;; casts not needed
  %B = shl i32 %A, 24
  %C = ashr i32 %B, 24
  %D = trunc i32 %C to i8
  ret i8 %D
}

define i8 @test24(i8 %X) {
; CHECK-LABEL: @test24(
; CHECK-NEXT:    [[Z:%.*]] = and i8 [[X:%.*]], 3
; CHECK-NEXT:    ret i8 [[Z]]
;
  %Y = and i8 %X, -5
  %Z = shl i8 %Y, 5
  %Q = ashr i8 %Z, 5
  ret i8 %Q
}

;; handle casts between shifts.
define i32 @test26(i32 %A) {
; CHECK-LABEL: @test26(
; CHECK-NEXT:    [[B:%.*]] = and i32 [[A:%.*]], -2
; CHECK-NEXT:    ret i32 [[B]]
;
  %B = lshr i32 %A, 1
  %C = bitcast i32 %B to i32
  %D = shl i32 %C, 1
  ret i32 %D
}


define i1 @test27(i32 %x) nounwind {
; CHECK-LABEL: @test27(
; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], 8
; CHECK-NEXT:    [[Z:%.*]] = icmp ne i32 [[TMP1]], 0
; CHECK-NEXT:    ret i1 [[Z]]
;
  %y = lshr i32 %x, 3
  %z = trunc i32 %y to i1
  ret i1 %z
}

define i1 @test28(i8 %x) {
; CHECK-LABEL: @test28(
; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[X:%.*]], 0
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %shr = lshr i8 %x, 7
  %cmp = icmp ne i8 %shr, 0
  ret i1 %cmp
}

define <2 x i1> @test28vec(<2 x i8> %x) {
; CHECK-LABEL: @test28vec(
; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i8> [[X:%.*]], zeroinitializer
; CHECK-NEXT:    ret <2 x i1> [[CMP]]
;
  %shr = lshr <2 x i8> %x, <i8 7, i8 7>
  %cmp = icmp ne <2 x i8> %shr, zeroinitializer
  ret <2 x i1> %cmp
}

define i8 @test28a(i8 %x, i8 %y) {
; CHECK-LABEL: @test28a(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[I1:%.*]] = lshr i8 [[X:%.*]], 7
; CHECK-NEXT:    [[COND1_NOT:%.*]] = icmp sgt i8 [[X]], -1
; CHECK-NEXT:    br i1 [[COND1_NOT]], label [[BB2:%.*]], label [[BB1:%.*]]
; CHECK:       bb1:
; CHECK-NEXT:    ret i8 [[I1]]
; CHECK:       bb2:
; CHECK-NEXT:    [[I2:%.*]] = add i8 [[I1]], [[Y:%.*]]
; CHECK-NEXT:    ret i8 [[I2]]
;
entry:
; This shouldn't be transformed.
  %i1 = lshr i8 %x, 7
  %cond1 = icmp ne i8 %i1, 0
  br i1 %cond1, label %bb1, label %bb2
bb1:
  ret i8 %i1
bb2:
  %i2 = add i8 %i1, %y
  ret i8 %i2
}

define i32 @test29(i64 %d18) {
; CHECK-LABEL: @test29(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[SUM_SHIFT:%.*]] = lshr i64 [[D18:%.*]], 63
; CHECK-NEXT:    [[I101:%.*]] = trunc i64 [[SUM_SHIFT]] to i32
; CHECK-NEXT:    ret i32 [[I101]]
;
entry:
  %i916 = lshr i64 %d18, 32
  %i917 = trunc i64 %i916 to i32
  %i10 = lshr i32 %i917, 31
  ret i32 %i10
}

define <2 x i32> @test29_uniform(<2 x i64> %d18) {
; CHECK-LABEL: @test29_uniform(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[SUM_SHIFT:%.*]] = lshr <2 x i64> [[D18:%.*]], <i64 63, i64 63>
; CHECK-NEXT:    [[I101:%.*]] = trunc <2 x i64> [[SUM_SHIFT]] to <2 x i32>
; CHECK-NEXT:    ret <2 x i32> [[I101]]
;
entry:
  %i916 = lshr <2 x i64> %d18, <i64 32, i64 32>
  %i917 = trunc <2 x i64> %i916 to <2 x i32>
  %i10 = lshr <2 x i32> %i917, <i32 31, i32 31>
  ret <2 x i32> %i10
}

define <2 x i32> @test29_nonuniform(<2 x i64> %d18) {
; CHECK-LABEL: @test29_nonuniform(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[I916:%.*]] = lshr <2 x i64> [[D18:%.*]], <i64 32, i64 15>
; CHECK-NEXT:    [[I917:%.*]] = trunc <2 x i64> [[I916]] to <2 x i32>
; CHECK-NEXT:    [[I10:%.*]] = lshr <2 x i32> [[I917]], <i32 31, i32 22>
; CHECK-NEXT:    ret <2 x i32> [[I10]]
;
entry:
  %i916 = lshr <2 x i64> %d18, <i64 32, i64 15>
  %i917 = trunc <2 x i64> %i916 to <2 x i32>
  %i10 = lshr <2 x i32> %i917, <i32 31, i32 22>
  ret <2 x i32> %i10
}

define <2 x i32> @test29_poison(<2 x i64> %d18) {
; CHECK-LABEL: @test29_poison(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[I916:%.*]] = lshr <2 x i64> [[D18:%.*]], <i64 32, i64 poison>
; CHECK-NEXT:    [[I917:%.*]] = trunc <2 x i64> [[I916]] to <2 x i32>
; CHECK-NEXT:    [[I10:%.*]] = lshr <2 x i32> [[I917]], <i32 31, i32 poison>
; CHECK-NEXT:    ret <2 x i32> [[I10]]
;
entry:
  %i916 = lshr <2 x i64> %d18, <i64 32, i64 poison>
  %i917 = trunc <2 x i64> %i916 to <2 x i32>
  %i10 = lshr <2 x i32> %i917, <i32 31, i32 poison>
  ret <2 x i32> %i10
}

define i32 @test30(i32 %A, i32 %B, i32 %C) {
; CHECK-LABEL: @test30(
; CHECK-NEXT:    [[X1:%.*]] = and i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    [[Z:%.*]] = shl i32 [[X1]], [[C:%.*]]
; CHECK-NEXT:    ret i32 [[Z]]
;
  %X = shl i32 %A, %C
  %Y = shl i32 %B, %C
  %Z = and i32 %X, %Y
  ret i32 %Z
}

define i32 @test31(i32 %A, i32 %B, i32 %C) {
; CHECK-LABEL: @test31(
; CHECK-NEXT:    [[X1:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    [[Z:%.*]] = lshr i32 [[X1]], [[C:%.*]]
; CHECK-NEXT:    ret i32 [[Z]]
;
  %X = lshr i32 %A, %C
  %Y = lshr i32 %B, %C
  %Z = or i32 %X, %Y
  ret i32 %Z
}

define i32 @test32(i32 %A, i32 %B, i32 %C) {
; CHECK-LABEL: @test32(
; CHECK-NEXT:    [[X1:%.*]] = xor i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    [[Z:%.*]] = ashr i32 [[X1]], [[C:%.*]]
; CHECK-NEXT:    ret i32 [[Z]]
;
  %X = ashr i32 %A, %C
  %Y = ashr i32 %B, %C
  %Z = xor i32 %X, %Y
  ret i32 %Z
}

define i1 @test33(i32 %X) {
; CHECK-LABEL: @test33(
; CHECK-NEXT:    [[I1_MASK:%.*]] = and i32 [[X:%.*]], 16777216
; CHECK-NEXT:    [[I2:%.*]] = icmp ne i32 [[I1_MASK]], 0
; CHECK-NEXT:    ret i1 [[I2]]
;
  %i1 = shl i32 %X, 7
  %i2 = icmp slt i32 %i1, 0
  ret i1 %i2
}

define <2 x i1> @test33vec(<2 x i32> %X) {
; CHECK-LABEL: @test33vec(
; CHECK-NEXT:    [[I1_MASK:%.*]] = and <2 x i32> [[X:%.*]], <i32 16777216, i32 16777216>
; CHECK-NEXT:    [[I2:%.*]] = icmp ne <2 x i32> [[I1_MASK]], zeroinitializer
; CHECK-NEXT:    ret <2 x i1> [[I2]]
;
  %i1 = shl <2 x i32> %X, <i32 7, i32 7>
  %i2 = icmp slt <2 x i32> %i1, zeroinitializer
  ret <2 x i1> %i2
}

define i1 @test34(i32 %X) {
; CHECK-LABEL: @test34(
; CHECK-NEXT:    ret i1 false
;
  %i1 = lshr i32 %X, 7
  %i2 = icmp slt i32 %i1, 0
  ret i1 %i2
}

define i1 @test35(i32 %X) {
; CHECK-LABEL: @test35(
; CHECK-NEXT:    [[I2:%.*]] = icmp slt i32 [[X:%.*]], 0
; CHECK-NEXT:    ret i1 [[I2]]
;
  %i1 = ashr i32 %X, 7
  %i2 = icmp slt i32 %i1, 0
  ret i1 %i2
}

define <2 x i1> @test35vec(<2 x i32> %X) {
; CHECK-LABEL: @test35vec(
; CHECK-NEXT:    [[I2:%.*]] = icmp slt <2 x i32> [[X:%.*]], zeroinitializer
; CHECK-NEXT:    ret <2 x i1> [[I2]]
;
  %i1 = ashr <2 x i32> %X, <i32 7, i32 7>
  %i2 = icmp slt <2 x i32> %i1, zeroinitializer
  ret <2 x i1> %i2
}

define i128 @test36(i128 %A, i128 %B) {
; CHECK-LABEL: @test36(
; CHECK-NEXT:    [[I231:%.*]] = or i128 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT:    [[INS:%.*]] = and i128 [[I231]], 18446744073709551615
; CHECK-NEXT:    ret i128 [[INS]]
;
  %i27 = shl i128 %A, 64
  %i23 = shl i128 %B, 64
  %ins = or i128 %i23, %i27
  %i45 = lshr i128 %ins, 64
  ret i128 %i45
}

define i64 @test37(i128 %A, i32 %B) {
; CHECK-LABEL: @test37(
; CHECK-NEXT:    [[I22:%.*]] = zext i32 [[B:%.*]] to i128
; CHECK-NEXT:    [[I23:%.*]] = shl nuw nsw i128 [[I22]], 32
; CHECK-NEXT:    [[INS:%.*]] = or i128 [[I23]], [[A:%.*]]
; CHECK-NEXT:    [[I46:%.*]] = trunc i128 [[INS]] to i64
; CHECK-NEXT:    ret i64 [[I46]]
;
  %i27 = shl i128 %A, 64
  %i22 = zext i32 %B to i128
  %i23 = shl i128 %i22, 96
  %ins = or i128 %i23, %i27
  %i45 = lshr i128 %ins, 64
  %i46 = trunc i128 %i45 to i64
  ret i64 %i46
}

define <2 x i32> @shl_nuw_nsw_splat_vec(<2 x i8> %x) {
; CHECK-LABEL: @shl_nuw_nsw_splat_vec(
; CHECK-NEXT:    [[T2:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i32>
; CHECK-NEXT:    [[T3:%.*]] = shl nuw nsw <2 x i32> [[T2]], <i32 17, i32 17>
; CHECK-NEXT:    ret <2 x i32> [[T3]]
;
  %t2 = zext <2 x i8> %x to <2 x i32>
  %t3 = shl <2 x i32> %t2, <i32 17, i32 17>
  ret <2 x i32> %t3
}

define i32 @test38(i32 %x) nounwind readnone {
; CHECK-LABEL: @test38(
; CHECK-NEXT:    [[REM1:%.*]] = and i32 [[X:%.*]], 31
; CHECK-NEXT:    [[SHL:%.*]] = shl i32 1, [[REM1]]
; CHECK-NEXT:    ret i32 [[SHL]]
;
  %rem = srem i32 %x, 32
  %shl = shl i32 1, %rem
  ret i32 %shl
}

define <2 x i32> @test38_uniform(<2 x i32> %x) nounwind readnone {
; CHECK-LABEL: @test38_uniform(
; CHECK-NEXT:    [[REM1:%.*]] = and <2 x i32> [[X:%.*]], <i32 31, i32 31>
; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i32> <i32 1, i32 1>, [[REM1]]
; CHECK-NEXT:    ret <2 x i32> [[SHL]]
;
  %rem = srem <2 x i32> %x, <i32 32, i32 32>
  %shl = shl <2 x i32> <i32 1, i32 1>, %rem
  ret <2 x i32> %shl
}

define <3 x i32> @test38_nonuniform(<3 x i32> %x) nounwind readnone {
; CHECK-LABEL: @test38_nonuniform(
; CHECK-NEXT:    [[REM1:%.*]] = and <3 x i32> [[X:%.*]], <i32 31, i32 15, i32 0>
; CHECK-NEXT:    [[SHL:%.*]] = shl <3 x i32> <i32 1, i32 1, i32 1>, [[REM1]]
; CHECK-NEXT:    ret <3 x i32> [[SHL]]
;
  %rem = srem <3 x i32> %x, <i32 32, i32 16, i32 1>
  %shl = shl <3 x i32> <i32 1, i32 1, i32 1>, %rem
  ret <3 x i32> %shl
}

define <2 x i32> @test38_poison(<2 x i32> %x) nounwind readnone {
; CHECK-LABEL: @test38_poison(
; CHECK-NEXT:    ret <2 x i32> poison
;
  %rem = srem <2 x i32> %x, <i32 32, i32 poison>
  %shl = shl <2 x i32> <i32 1, i32 1>, %rem
  ret <2 x i32> %shl
}

; <rdar://problem/8756731>
define i8 @test39(i32 %a0) {
; CHECK-LABEL: @test39(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[I4:%.*]] = trunc i32 [[A0:%.*]] to i8
; CHECK-NEXT:    [[I5:%.*]] = shl i8 [[I4]], 5
; CHECK-NEXT:    [[I49:%.*]] = shl i8 [[I4]], 6
; CHECK-NEXT:    [[I50:%.*]] = and i8 [[I49]], 64
; CHECK-NEXT:    [[I51:%.*]] = xor i8 [[I50]], [[I5]]
; CHECK-NEXT:    [[TMP0:%.*]] = lshr exact i8 [[I5]], 3
; CHECK-NEXT:    [[I54:%.*]] = and i8 [[TMP0]], 16
; CHECK-NEXT:    [[I551:%.*]] = or i8 [[I54]], [[I51]]
; CHECK-NEXT:    ret i8 [[I551]]
;
entry:
  %i4 = trunc i32 %a0 to i8
  %i5 = shl i8 %i4, 5
  %i48 = and i8 %i5, 32
  %i49 = lshr i8 %i48, 5
  %i50 = mul i8 %i49, 64
  %i51 = xor i8 %i50, %i5
  %i52 = and i8 %i51, -128
  %i53 = lshr i8 %i52, 7
  %i54 = mul i8 %i53, 16
  %i55 = xor i8 %i54, %i51
  ret i8 %i55
}

define i32 @test42(i32 %a, i32 %b) nounwind {
; CHECK-LABEL: @test42(
; CHECK-NEXT:    [[DIV:%.*]] = lshr exact i32 4096, [[B:%.*]]
; CHECK-NEXT:    [[DIV2:%.*]] = udiv i32 [[A:%.*]], [[DIV]]
; CHECK-NEXT:    ret i32 [[DIV2]]
;
  %div = lshr i32 4096, %b    ; must be exact otherwise we'd divide by zero
  %div2 = udiv i32 %a, %div
  ret i32 %div2
}

define <2 x i32> @test42vec(<2 x i32> %a, <2 x i32> %b) {
; CHECK-LABEL: @test42vec(
; CHECK-NEXT:    [[DIV:%.*]] = lshr exact <2 x i32> <i32 4096, i32 4096>, [[B:%.*]]
; CHECK-NEXT:    [[DIV2:%.*]] = udiv <2 x i32> [[A:%.*]], [[DIV]]
; CHECK-NEXT:    ret <2 x i32> [[DIV2]]
;
  %div = lshr <2 x i32> <i32 4096, i32 4096>, %b    ; must be exact otherwise we'd divide by zero
  %div2 = udiv <2 x i32> %a, %div
  ret <2 x i32> %div2
}

define i32 @test43(i32 %a, i32 %b) nounwind {
; CHECK-LABEL: @test43(
; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[B:%.*]], 12
; CHECK-NEXT:    [[DIV21:%.*]] = lshr i32 [[A:%.*]], [[TMP1]]
; CHECK-NEXT:    ret i32 [[DIV21]]
;
  %div = shl i32 4096, %b    ; must be exact otherwise we'd divide by zero
  %div2 = udiv i32 %a, %div
  ret i32 %div2
}

define i32 @test44(i32 %a) nounwind {
; CHECK-LABEL: @test44(
; CHECK-NEXT:    [[Y:%.*]] = shl i32 [[A:%.*]], 5
; CHECK-NEXT:    ret i32 [[Y]]
;
  %y = shl nuw i32 %a, 1
  %z = shl i32 %y, 4
  ret i32 %z
}

define i32 @test45(i32 %a) nounwind {
; CHECK-LABEL: @test45(
; CHECK-NEXT:    [[Y:%.*]] = lshr i32 [[A:%.*]], 5
; CHECK-NEXT:    ret i32 [[Y]]
;
  %y = lshr exact i32 %a, 1
  %z = lshr i32 %y, 4
  ret i32 %z
}

; (X >>?exact C1) << C2 --> X >>?exact (C1-C2)

define i32 @test46(i32 %a) {
; CHECK-LABEL: @test46(
; CHECK-NEXT:    [[Z:%.*]] = ashr exact i32 [[A:%.*]], 2
; CHECK-NEXT:    ret i32 [[Z]]
;
  %y = ashr exact i32 %a, 3
  %z = shl i32 %y, 1
  ret i32 %z
}

; (X >>?exact C1) << C2 --> X >>?exact (C1-C2)

define <2 x i32> @test46_splat_vec(<2 x i32> %a) {
; CHECK-LABEL: @test46_splat_vec(
; CHECK-NEXT:    [[Z:%.*]] = ashr exact <2 x i32> [[A:%.*]], <i32 2, i32 2>
; CHECK-NEXT:    ret <2 x i32> [[Z]]
;
  %y = ashr exact <2 x i32> %a, <i32 3, i32 3>
  %z = shl <2 x i32> %y, <i32 1, i32 1>
  ret <2 x i32> %z
}

; (X >>?exact C1) << C2 --> X >>?exact (C1-C2)

define i8 @test47(i8 %a) {
; CHECK-LABEL: @test47(
; CHECK-NEXT:    [[Z:%.*]] = lshr exact i8 [[A:%.*]], 2
; CHECK-NEXT:    ret i8 [[Z]]
;
  %y = lshr exact i8 %a, 3
  %z = shl i8 %y, 1
  ret i8 %z
}

; (X >>?exact C1) << C2 --> X >>?exact (C1-C2)

define <2 x i8> @test47_splat_vec(<2 x i8> %a) {
; CHECK-LABEL: @test47_splat_vec(
; CHECK-NEXT:    [[Z:%.*]] = lshr exact <2 x i8> [[A:%.*]], <i8 2, i8 2>
; CHECK-NEXT:    ret <2 x i8> [[Z]]
;
  %y = lshr exact <2 x i8> %a, <i8 3, i8 3>
  %z = shl <2 x i8> %y, <i8 1, i8 1>
  ret <2 x i8> %z
}

; (X >>u,exact C1) << C2 --> X << (C2-C1) when C2 > C1

define i32 @test48(i32 %x) {
; CHECK-LABEL: @test48(
; CHECK-NEXT:    [[B:%.*]] = shl i32 [[X:%.*]], 2
; CHECK-NEXT:    ret i32 [[B]]
;
  %A = lshr exact i32 %x, 1
  %B = shl i32 %A, 3
  ret i32 %B
}

; Verify that wrap flags are preserved from the original 'shl'.

define i32 @test48_nuw_nsw(i32 %x) {
; CHECK-LABEL: @test48_nuw_nsw(
; CHECK-NEXT:    [[B:%.*]] = shl nuw nsw i32 [[X:%.*]], 2
; CHECK-NEXT:    ret i32 [[B]]
;
  %A = lshr exact i32 %x, 1
  %B = shl nuw nsw i32 %A, 3
  ret i32 %B
}

; (X >>u,exact C1) << C2 --> X << (C2-C1) when splatted C2 > C1

define <2 x i32> @test48_splat_vec(<2 x i32> %x) {
; CHECK-LABEL: @test48_splat_vec(
; CHECK-NEXT:    [[B:%.*]] = shl nuw nsw <2 x i32> [[X:%.*]], <i32 2, i32 2>
; CHECK-NEXT:    ret <2 x i32> [[B]]
;
  %A = lshr exact <2 x i32> %x, <i32 1, i32 1>
  %B = shl nsw nuw <2 x i32> %A, <i32 3, i32 3>
  ret <2 x i32> %B
}

; (X >>s,exact C1) << C2 --> X << (C2-C1) when C2 > C1

define i32 @test49(i32 %x) {
; CHECK-LABEL: @test49(
; CHECK-NEXT:    [[B:%.*]] = shl i32 [[X:%.*]], 2
; CHECK-NEXT:    ret i32 [[B]]
;
  %A = ashr exact i32 %x, 1
  %B = shl i32 %A, 3
  ret i32 %B
}

; Verify that wrap flags are preserved from the original 'shl'.

define i32 @test49_nuw_nsw(i32 %x) {
; CHECK-LABEL: @test49_nuw_nsw(
; CHECK-NEXT:    [[B:%.*]] = shl nuw nsw i32 [[X:%.*]], 2
; CHECK-NEXT:    ret i32 [[B]]
;
  %A = ashr exact i32 %x, 1
  %B = shl nuw nsw i32 %A, 3
  ret i32 %B
}

; (X >>s,exact C1) << C2 --> X << (C2-C1) when splatted C2 > C1

define <2 x i32> @test49_splat_vec(<2 x i32> %x) {
; CHECK-LABEL: @test49_splat_vec(
; CHECK-NEXT:    [[B:%.*]] = shl nuw nsw <2 x i32> [[X:%.*]], <i32 2, i32 2>
; CHECK-NEXT:    ret <2 x i32> [[B]]
;
  %A = ashr exact <2 x i32> %x, <i32 1, i32 1>
  %B = shl nsw nuw <2 x i32> %A, <i32 3, i32 3>
  ret <2 x i32> %B
}

; (X <<nsw C1) >>s C2 --> X >>s (C2-C1)

define i32 @test50(i32 %x) {
; CHECK-LABEL: @test50(
; CHECK-NEXT:    [[B:%.*]] = ashr i32 [[X:%.*]], 2
; CHECK-NEXT:    ret i32 [[B]]
;
  %A = shl nsw i32 %x, 1
  %B = ashr i32 %A, 3
  ret i32 %B
}

; (X <<nsw C1) >>s C2 --> X >>s (C2-C1)
; Also, check that exact is propagated.

define <2 x i32> @test50_splat_vec(<2 x i32> %x) {
; CHECK-LABEL: @test50_splat_vec(
; CHECK-NEXT:    [[B:%.*]] = ashr exact <2 x i32> [[X:%.*]], <i32 2, i32 2>
; CHECK-NEXT:    ret <2 x i32> [[B]]
;
  %A = shl nsw <2 x i32> %x, <i32 1, i32 1>
  %B = ashr exact <2 x i32> %A, <i32 3, i32 3>
  ret <2 x i32> %B
}

; (X <<nuw C1) >>u C2 --> X >>u (C2-C1)

define i32 @test51(i32 %x) {
; CHECK-LABEL: @test51(
; CHECK-NEXT:    [[B:%.*]] = lshr i32 [[X:%.*]], 2
; CHECK-NEXT:    ret i32 [[B]]
;
  %A = shl nuw i32 %x, 1
  %B = lshr i32 %A, 3
  ret i32 %B
}

; (X <<nuw C1) >>u C2 --> X >>u (C2-C1) with splats
; Also, check that exact is propagated.

define <2 x i32> @test51_splat_vec(<2 x i32> %x) {
; CHECK-LABEL: @test51_splat_vec(
; CHECK-NEXT:    [[B:%.*]] = lshr exact <2 x i32> [[X:%.*]], <i32 2, i32 2>
; CHECK-NEXT:    ret <2 x i32> [[B]]
;
  %A = shl nuw <2 x i32> %x, <i32 1, i32 1>
  %B = lshr exact <2 x i32> %A, <i32 3, i32 3>
  ret <2 x i32> %B
}

; (X << C1) >>u C2  --> X >>u (C2-C1) & (-1 >> C2)
; Also, check that exact is propagated.

define i32 @test51_no_nuw(i32 %x) {
; CHECK-LABEL: @test51_no_nuw(
; CHECK-NEXT:    [[TMP1:%.*]] = lshr exact i32 [[X:%.*]], 2
; CHECK-NEXT:    [[B:%.*]] = and i32 [[TMP1]], 536870911
; CHECK-NEXT:    ret i32 [[B]]
;
  %A = shl i32 %x, 1
  %B = lshr exact i32 %A, 3
  ret i32 %B
}

; (X << C1) >>u C2  --> X >>u (C2-C1) & (-1 >> C2)

define <2 x i32> @test51_no_nuw_splat_vec(<2 x i32> %x) {
; CHECK-LABEL: @test51_no_nuw_splat_vec(
; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i32> [[X:%.*]], <i32 2, i32 2>
; CHECK-NEXT:    [[B:%.*]] = and <2 x i32> [[TMP1]], <i32 536870911, i32 536870911>
; CHECK-NEXT:    ret <2 x i32> [[B]]
;
  %A = shl <2 x i32> %x, <i32 1, i32 1>
  %B = lshr <2 x i32> %A, <i32 3, i32 3>
  ret <2 x i32> %B
}

; (X <<nsw C1) >>s C2 --> X <<nsw (C1 - C2)

define i32 @test52(i32 %x) {
; CHECK-LABEL: @test52(
; CHECK-NEXT:    [[B:%.*]] = shl nsw i32 [[X:%.*]], 2
; CHECK-NEXT:    ret i32 [[B]]
;
  %A = shl nsw i32 %x, 3
  %B = ashr i32 %A, 1
  ret i32 %B
}

; (X <<nsw C1) >>s C2 --> X <<nsw (C1 - C2)

define <2 x i32> @test52_splat_vec(<2 x i32> %x) {
; CHECK-LABEL: @test52_splat_vec(
; CHECK-NEXT:    [[B:%.*]] = shl nsw <2 x i32> [[X:%.*]], <i32 2, i32 2>
; CHECK-NEXT:    ret <2 x i32> [[B]]
;
  %A = shl nsw <2 x i32> %x, <i32 3, i32 3>
  %B = ashr <2 x i32> %A, <i32 1, i32 1>
  ret <2 x i32> %B
}

; (X <<nuw C1) >>u C2 --> X <<nuw (C1 - C2)

define i32 @test53(i32 %x) {
; CHECK-LABEL: @test53(
; CHECK-NEXT:    [[B:%.*]] = shl nuw i32 [[X:%.*]], 2
; CHECK-NEXT:    ret i32 [[B]]
;
  %A = shl nuw i32 %x, 3
  %B = lshr i32 %A, 1
  ret i32 %B
}

; (X <<nuw C1) >>u C2 --> X <<nuw (C1 - C2)

define <2 x i32> @test53_splat_vec(<2 x i32> %x) {
; CHECK-LABEL: @test53_splat_vec(
; CHECK-NEXT:    [[B:%.*]] = shl nuw <2 x i32> [[X:%.*]], <i32 2, i32 2>
; CHECK-NEXT:    ret <2 x i32> [[B]]
;
  %A = shl nuw <2 x i32> %x, <i32 3, i32 3>
  %B = lshr <2 x i32> %A, <i32 1, i32 1>
  ret <2 x i32> %B
}

; (X << C1) >>u C2  --> X << (C1 - C2) & (-1 >> C2)

define i8 @test53_no_nuw(i8 %x) {
; CHECK-LABEL: @test53_no_nuw(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[X:%.*]], 2
; CHECK-NEXT:    [[B:%.*]] = and i8 [[TMP1]], 124
; CHECK-NEXT:    ret i8 [[B]]
;
  %A = shl i8 %x, 3
  %B = lshr i8 %A, 1
  ret i8 %B
}

; (X << C1) >>u C2  --> X << (C1 - C2) & (-1 >> C2)

define <2 x i8> @test53_no_nuw_splat_vec(<2 x i8> %x) {
; CHECK-LABEL: @test53_no_nuw_splat_vec(
; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i8> [[X:%.*]], <i8 2, i8 2>
; CHECK-NEXT:    [[B:%.*]] = and <2 x i8> [[TMP1]], <i8 124, i8 124>
; CHECK-NEXT:    ret <2 x i8> [[B]]
;
  %A = shl <2 x i8> %x, <i8 3, i8 3>
  %B = lshr <2 x i8> %A, <i8 1, i8 1>
  ret <2 x i8> %B
}

define i32 @test54(i32 %x) {
; CHECK-LABEL: @test54(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 3
; CHECK-NEXT:    [[AND:%.*]] = and i32 [[TMP1]], 16
; CHECK-NEXT:    ret i32 [[AND]]
;
  %shr2 = lshr i32 %x, 1
  %shl = shl i32 %shr2, 4
  %and = and i32 %shl, 16
  ret i32 %and
}

define <2 x i32> @test54_splat_vec(<2 x i32> %x) {
; CHECK-LABEL: @test54_splat_vec(
; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i32> [[X:%.*]], <i32 3, i32 3>
; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[TMP1]], <i32 16, i32 16>
; CHECK-NEXT:    ret <2 x i32> [[AND]]
;
  %shr2 = lshr <2 x i32> %x, <i32 1, i32 1>
  %shl = shl <2 x i32> %shr2, <i32 4, i32 4>
  %and = and <2 x i32> %shl, <i32 16, i32 16>
  ret <2 x i32> %and
}

define i32 @test55(i32 %x) {
; CHECK-LABEL: @test55(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 3
; CHECK-NEXT:    [[OR:%.*]] = or i32 [[TMP1]], 8
; CHECK-NEXT:    ret i32 [[OR]]
;
  %shr2 = lshr i32 %x, 1
  %shl = shl i32 %shr2, 4
  %or = or i32 %shl, 8
  ret i32 %or
}

define i32 @test56(i32 %x) {
; CHECK-LABEL: @test56(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 3
; CHECK-NEXT:    [[SHL:%.*]] = and i32 [[TMP1]], -16
; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SHL]], 7
; CHECK-NEXT:    ret i32 [[OR]]
;
  %shr2 = lshr i32 %x, 1
  %shl = shl i32 %shr2, 4
  %or = or i32 %shl, 7
  ret i32 %or
}

define i32 @test57(i32 %x) {
; CHECK-LABEL: @test57(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 3
; CHECK-NEXT:    [[SHL:%.*]] = and i32 [[TMP1]], -16
; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SHL]], 7
; CHECK-NEXT:    ret i32 [[OR]]
;
  %shr = ashr i32 %x, 1
  %shl = shl i32 %shr, 4
  %or = or i32 %shl, 7
  ret i32 %or
}

define i32 @test58(i32 %x) {
; CHECK-LABEL: @test58(
; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 3
; CHECK-NEXT:    [[OR:%.*]] = or i32 [[TMP1]], 1
; CHECK-NEXT:    ret i32 [[OR]]
;
  %shr = ashr i32 %x, 4
  %shl = shl i32 %shr, 1
  %or = or i32 %shl, 1
  ret i32 %or
}

define <2 x i32> @test58_splat_vec(<2 x i32> %x) {
; CHECK-LABEL: @test58_splat_vec(
; CHECK-NEXT:    [[TMP1:%.*]] = ashr <2 x i32> [[X:%.*]], <i32 3, i32 3>
; CHECK-NEXT:    [[OR:%.*]] = or <2 x i32> [[TMP1]], <i32 1, i32 1>
; CHECK-NEXT:    ret <2 x i32> [[OR]]
;
  %shr = ashr <2 x i32> %x, <i32 4, i32 4>
  %shl = shl <2 x i32> %shr, <i32 1, i32 1>
  %or = or <2 x i32> %shl, <i32 1, i32 1>
  ret <2 x i32> %or
}

define i32 @test59(i32 %x) {
; CHECK-LABEL: @test59(
; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 3
; CHECK-NEXT:    [[SHL:%.*]] = and i32 [[TMP1]], -4
; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SHL]], 2
; CHECK-NEXT:    ret i32 [[OR]]
;
  %shr = ashr i32 %x, 4
  %shl = shl i32 %shr, 1
  %or = or i32 %shl, 2
  ret i32 %or
}

; propagate "exact" trait
define i32 @test60(i32 %x) {
; CHECK-LABEL: @test60(
; CHECK-NEXT:    [[SHL:%.*]] = ashr exact i32 [[X:%.*]], 3
; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SHL]], 1
; CHECK-NEXT:    ret i32 [[OR]]
;
  %shr = ashr exact i32 %x, 4
  %shl = shl i32 %shr, 1
  %or = or i32 %shl, 1
  ret i32 %or
}

; PR17026
define void @test61(i128 %arg, i1 %c1, i1 %c2, i1 %c3, i1 %c4) {
; CHECK-LABEL: @test61(
; CHECK-NEXT:  bb:
; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB12:%.*]]
; CHECK:       bb1:
; CHECK-NEXT:    br label [[BB2:%.*]]
; CHECK:       bb2:
; CHECK-NEXT:    br i1 [[C2:%.*]], label [[BB3:%.*]], label [[BB7:%.*]]
; CHECK:       bb3:
; CHECK-NEXT:    br label [[BB8:%.*]]
; CHECK:       bb7:
; CHECK-NEXT:    br i1 [[C3:%.*]], label [[BB8]], label [[BB2]]
; CHECK:       bb8:
; CHECK-NEXT:    br i1 undef, label [[BB11:%.*]], label [[BB12]]
; CHECK:       bb11:
; CHECK-NEXT:    br i1 [[C4:%.*]], label [[BB1]], label [[BB12]]
; CHECK:       bb12:
; CHECK-NEXT:    ret void
;
bb:
  br i1 %c1, label %bb1, label %bb12

bb1:                                              ; preds = %bb11, %bb
  br label %bb2

bb2:                                              ; preds = %bb7, %bb1
  br i1 %c2, label %bb3, label %bb7

bb3:                                              ; preds = %bb2
  %i = lshr i128 %arg, 36893488147419103232
  %i4 = shl i128 %i, 0
  %i5 = or i128 %i4, 0
  %i6 = trunc i128 %i5 to i16
  br label %bb8

bb7:                                              ; preds = %bb2
  br i1 %c3, label %bb8, label %bb2

bb8:                                              ; preds = %bb7, %bb3
  %i9 = phi i16 [ %i6, %bb3 ], [ poison, %bb7 ]
  %i10 = icmp eq i16 %i9, 0
  br i1 %i10, label %bb11, label %bb12

bb11:                                             ; preds = %bb8
  br i1 %c4, label %bb1, label %bb12

bb12:                                             ; preds = %bb11, %bb8, %bb
  ret void
}

define i32 @test62(i32 %a) {
; CHECK-LABEL: @test62(
; CHECK-NEXT:    ret i32 poison
;
  %b = ashr i32 %a, 32  ; shift all bits out
  ret i32 %b
}

define <4 x i32> @test62_splat_vector(<4 x i32> %a) {
; CHECK-LABEL: @test62_splat_vector(
; CHECK-NEXT:    ret <4 x i32> poison
;
  %b = ashr <4 x i32> %a, <i32 32, i32 32, i32 32, i32 32>  ; shift all bits out
  ret <4 x i32> %b
}

define <4 x i32> @test62_non_splat_vector(<4 x i32> %a) {
; CHECK-LABEL: @test62_non_splat_vector(
; CHECK-NEXT:    [[B:%.*]] = ashr <4 x i32> [[A:%.*]], <i32 32, i32 0, i32 1, i32 2>
; CHECK-NEXT:    ret <4 x i32> [[B]]
;
  %b = ashr <4 x i32> %a, <i32 32, i32 0, i32 1, i32 2>  ; shift all bits out
  ret <4 x i32> %b
}

define <2 x i65> @test_63(<2 x i64> %t) {
; CHECK-LABEL: @test_63(
; CHECK-NEXT:    [[A:%.*]] = zext <2 x i64> [[T:%.*]] to <2 x i65>
; CHECK-NEXT:    [[SEXT:%.*]] = shl <2 x i65> [[A]], <i65 33, i65 33>
; CHECK-NEXT:    [[B:%.*]] = ashr exact <2 x i65> [[SEXT]], <i65 33, i65 33>
; CHECK-NEXT:    ret <2 x i65> [[B]]
;
  %a = zext <2 x i64> %t to <2 x i65>
  %sext = shl <2 x i65> %a, <i65 33, i65 33>
  %b = ashr <2 x i65> %sext, <i65 33, i65 33>
  ret <2 x i65> %b
}

define i32 @test_shl_zext_bool(i1 %t) {
; CHECK-LABEL: @test_shl_zext_bool(
; CHECK-NEXT:    [[SHL:%.*]] = select i1 [[T:%.*]], i32 4, i32 0
; CHECK-NEXT:    ret i32 [[SHL]]
;
  %ext = zext i1 %t to i32
  %shl = shl i32 %ext, 2
  ret i32 %shl
}

define <2 x i32> @test_shl_zext_bool_splat(<2 x i1> %t) {
; CHECK-LABEL: @test_shl_zext_bool_splat(
; CHECK-NEXT:    [[SHL:%.*]] = select <2 x i1> [[T:%.*]], <2 x i32> <i32 8, i32 8>, <2 x i32> zeroinitializer
; CHECK-NEXT:    ret <2 x i32> [[SHL]]
;
  %ext = zext <2 x i1> %t to <2 x i32>
  %shl = shl <2 x i32> %ext, <i32 3, i32 3>
  ret <2 x i32> %shl
}

define <2 x i32> @test_shl_zext_bool_vec(<2 x i1> %t) {
; CHECK-LABEL: @test_shl_zext_bool_vec(
; CHECK-NEXT:    [[SHL:%.*]] = select <2 x i1> [[T:%.*]], <2 x i32> <i32 4, i32 8>, <2 x i32> zeroinitializer
; CHECK-NEXT:    ret <2 x i32> [[SHL]]
;
  %ext = zext <2 x i1> %t to <2 x i32>
  %shl = shl <2 x i32> %ext, <i32 2, i32 3>
  ret <2 x i32> %shl
}

define i32 @test_shl_zext_bool_not_constant(i1 %cmp, i32 %shamt) {
; CHECK-LABEL: @test_shl_zext_bool_not_constant(
; CHECK-NEXT:    [[CONV3:%.*]] = zext i1 [[CMP:%.*]] to i32
; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[CONV3]], [[SHAMT:%.*]]
; CHECK-NEXT:    ret i32 [[SHL]]
;
  %conv3 = zext i1 %cmp to i32
  %shl = shl i32 %conv3, %shamt
  ret i32 %shl
}

define i64 @shl_zext(i32 %t) {
; CHECK-LABEL: @shl_zext(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[T:%.*]], 8
; CHECK-NEXT:    [[SHL:%.*]] = zext i32 [[TMP1]] to i64
; CHECK-NEXT:    ret i64 [[SHL]]
;
  %and = and i32 %t, 16777215
  %ext = zext i32 %and to i64
  %shl = shl i64 %ext, 8
  ret i64 %shl
}

declare void @use(i64)

define i64 @shl_zext_extra_use(i32 %t) {
; CHECK-LABEL: @shl_zext_extra_use(
; CHECK-NEXT:    [[AND:%.*]] = and i32 [[T:%.*]], 16777215
; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[AND]] to i64
; CHECK-NEXT:    call void @use(i64 [[EXT]])
; CHECK-NEXT:    [[SHL:%.*]] = shl nuw nsw i64 [[EXT]], 8
; CHECK-NEXT:    ret i64 [[SHL]]
;
  %and = and i32 %t, 16777215
  %ext = zext i32 %and to i64
  call void @use(i64 %ext)
  %shl = shl i64 %ext, 8
  ret i64 %shl
}


define <2 x i64> @shl_zext_splat_vec(<2 x i32> %t) {
; CHECK-LABEL: @shl_zext_splat_vec(
; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i32> [[T:%.*]], <i32 8, i32 8>
; CHECK-NEXT:    [[SHL:%.*]] = zext <2 x i32> [[TMP1]] to <2 x i64>
; CHECK-NEXT:    ret <2 x i64> [[SHL]]
;
  %and = and <2 x i32> %t, <i32 16777215, i32 16777215>
  %ext = zext <2 x i32> %and to <2 x i64>
  %shl = shl <2 x i64> %ext, <i64 8, i64 8>
  ret <2 x i64> %shl
}

define i64 @shl_zext_mul(i32 %t) {
; CHECK-LABEL: @shl_zext_mul(
; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[T:%.*]], 16777215
; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[MUL]] to i64
; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i64 [[EXT]], 32
; CHECK-NEXT:    ret i64 [[SHL]]
;
  %mul = mul i32 %t, 16777215
  %ext = zext i32 %mul to i64
  %shl = shl i64 %ext, 32
  ret i64 %shl
}

define <3 x i17> @shl_zext_mul_splat(<3 x i5> %t) {
; CHECK-LABEL: @shl_zext_mul_splat(
; CHECK-NEXT:    [[MUL:%.*]] = mul <3 x i5> [[T:%.*]], <i5 13, i5 13, i5 13>
; CHECK-NEXT:    [[EXT:%.*]] = zext <3 x i5> [[MUL]] to <3 x i17>
; CHECK-NEXT:    [[SHL:%.*]] = shl nuw <3 x i17> [[EXT]], <i17 12, i17 12, i17 12>
; CHECK-NEXT:    ret <3 x i17> [[SHL]]
;
  %mul = mul <3 x i5> %t, <i5 13, i5 13, i5 13>
  %ext = zext <3 x i5> %mul to <3 x i17>
  %shl = shl <3 x i17> %ext, <i17 12, i17 12, i17 12>
  ret <3 x i17> %shl
}

define i64 @shl_zext_mul_low_shift_amount(i32 %t) {
; CHECK-LABEL: @shl_zext_mul_low_shift_amount(
; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[T:%.*]], 16777215
; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[MUL]] to i64
; CHECK-NEXT:    [[SHL:%.*]] = shl nuw nsw i64 [[EXT]], 31
; CHECK-NEXT:    ret i64 [[SHL]]
;
  %mul = mul i32 %t, 16777215
  %ext = zext i32 %mul to i64
  %shl = shl i64 %ext, 31
  ret i64 %shl
}

define i64 @shl_zext_mul_extra_use1(i32 %t) {
; CHECK-LABEL: @shl_zext_mul_extra_use1(
; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[T:%.*]], 16777215
; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[MUL]] to i64
; CHECK-NEXT:    call void @use(i64 [[EXT]])
; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i64 [[EXT]], 32
; CHECK-NEXT:    ret i64 [[SHL]]
;
  %mul = mul i32 %t, 16777215
  %ext = zext i32 %mul to i64
  call void @use(i64 %ext)
  %shl = shl i64 %ext, 32
  ret i64 %shl
}

declare void @use_i32(i32)

define i64 @shl_zext_mul_extra_use2(i32 %t) {
; CHECK-LABEL: @shl_zext_mul_extra_use2(
; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[T:%.*]], 16777215
; CHECK-NEXT:    call void @use_i32(i32 [[MUL]])
; CHECK-NEXT:    [[EXT:%.*]] = zext i32 [[MUL]] to i64
; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i64 [[EXT]], 32
; CHECK-NEXT:    ret i64 [[SHL]]
;
  %mul = mul i32 %t, 16777215
  call void @use_i32(i32 %mul)
  %ext = zext i32 %mul to i64
  %shl = shl i64 %ext, 32
  ret i64 %shl
}

define <2 x i8> @ashr_demanded_bits_splat(<2 x i8> %x) {
; CHECK-LABEL: @ashr_demanded_bits_splat(
; CHECK-NEXT:    [[SHR:%.*]] = ashr <2 x i8> [[X:%.*]], <i8 7, i8 7>
; CHECK-NEXT:    ret <2 x i8> [[SHR]]
;
  %and = and <2 x i8> %x, <i8 128, i8 128>
  %shr = ashr <2 x i8> %and, <i8 7, i8 7>
  ret <2 x i8> %shr
}

define <vscale x 8 x i8> @ashr_demanded_bits_splat2(<vscale x 8 x i8> %x) {
; CHECK-LABEL: @ashr_demanded_bits_splat2(
; CHECK-NEXT:    [[AND:%.*]] = ashr <vscale x 8 x i8> [[X:%.*]], shufflevector (<vscale x 8 x i8> insertelement (<vscale x 8 x i8> poison, i8 7, i32 0), <vscale x 8 x i8> poison, <vscale x 8 x i32> zeroinitializer)
; CHECK-NEXT:    ret <vscale x 8 x i8> [[AND]]
;
  %and = and <vscale x 8 x i8> %x, shufflevector (<vscale x 8 x i8> insertelement (<vscale x 8 x i8> poison, i8 128, i32 0), <vscale x 8 x i8> poison, <vscale x 8 x i32> zeroinitializer)
  %shr = ashr <vscale x 8 x i8> %and, shufflevector (<vscale x 8 x i8> insertelement (<vscale x 8 x i8> poison, i8 7, i32 0), <vscale x 8 x i8> poison, <vscale x 8 x i32> zeroinitializer)
  ret <vscale x 8 x i8> %shr
}

define <2 x i8> @lshr_demanded_bits_splat(<2 x i8> %x) {
; CHECK-LABEL: @lshr_demanded_bits_splat(
; CHECK-NEXT:    [[SHR:%.*]] = lshr <2 x i8> [[X:%.*]], <i8 7, i8 7>
; CHECK-NEXT:    ret <2 x i8> [[SHR]]
;
  %and = and <2 x i8> %x, <i8 128, i8 128>
  %shr = lshr <2 x i8> %and, <i8 7, i8 7>
  ret <2 x i8> %shr
}

define <vscale x 8 x i8> @lshr_demanded_bits_splat2(<vscale x 8 x i8> %x) {
; CHECK-LABEL: @lshr_demanded_bits_splat2(
; CHECK-NEXT:    [[AND:%.*]] = lshr <vscale x 8 x i8> [[X:%.*]], shufflevector (<vscale x 8 x i8> insertelement (<vscale x 8 x i8> poison, i8 7, i32 0), <vscale x 8 x i8> poison, <vscale x 8 x i32> zeroinitializer)
; CHECK-NEXT:    ret <vscale x 8 x i8> [[AND]]
;
  %and = and <vscale x 8 x i8> %x, shufflevector (<vscale x 8 x i8> insertelement (<vscale x 8 x i8> poison, i8 128, i32 0), <vscale x 8 x i8> poison, <vscale x 8 x i32> zeroinitializer)
  %shr = lshr <vscale x 8 x i8> %and, shufflevector (<vscale x 8 x i8> insertelement (<vscale x 8 x i8> poison, i8 7, i32 0), <vscale x 8 x i8> poison, <vscale x 8 x i32> zeroinitializer)
  ret <vscale x 8 x i8> %shr
}

; Make sure known bits works correctly with non power of 2 bit widths.
define i7 @test65(i7 %a, i7 %b) {
; CHECK-LABEL: @test65(
; CHECK-NEXT:    ret i7 0
;
  %shiftamt = and i7 %b, 6 ; this ensures the shift amount is even and less than the bit width.
  %x = lshr i7 42, %shiftamt ; 42 has a zero in every even numbered bit and a one in every odd bit.
  %y = and i7 %x, 1 ; this extracts the lsb which should be 0 because we shifted an even number of bits and all even bits of the shift input are 0.
  ret i7 %y
}

define i32 @shl_select_add_true(i32 %x, i1 %cond) {
; CHECK-LABEL: @shl_select_add_true(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[TMP1]], 14
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = add i32 %x, 7
  %2 = select i1 %cond, i32 %1, i32 %x
  %3 = shl i32 %2, 1
  ret i32 %3
}

define i32 @shl_select_add_false(i32 %x, i1 %cond) {
; CHECK-LABEL: @shl_select_add_false(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[TMP1]], 14
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = add i32 %x, 7
  %2 = select i1 %cond, i32 %x, i32 %1
  %3 = shl i32 %2, 1
  ret i32 %3
}

define i32 @shl_select_and_true(i32 %x, i1 %cond) {
; CHECK-LABEL: @shl_select_and_true(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 14
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = and i32 %x, 7
  %2 = select i1 %cond, i32 %1, i32 %x
  %3 = shl i32 %2, 1
  ret i32 %3
}

define i32 @shl_select_and_false(i32 %x, i1 %cond) {
; CHECK-LABEL: @shl_select_and_false(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 14
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = and i32 %x, 7
  %2 = select i1 %cond, i32 %x, i32 %1
  %3 = shl i32 %2, 1
  ret i32 %3
}

define i32 @lshr_select_and_true(i32 %x, i1 %cond) {
; CHECK-LABEL: @lshr_select_and_true(
; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 3
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = and i32 %x, 7
  %2 = select i1 %cond, i32 %1, i32 %x
  %3 = lshr i32 %2, 1
  ret i32 %3
}

define i32 @lshr_select_and_false(i32 %x, i1 %cond) {
; CHECK-LABEL: @lshr_select_and_false(
; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 3
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = and i32 %x, 7
  %2 = select i1 %cond, i32 %x, i32 %1
  %3 = lshr i32 %2, 1
  ret i32 %3
}

define i32 @ashr_select_and_true(i32 %x, i1 %cond) {
; CHECK-LABEL: @ashr_select_and_true(
; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], -1073741821
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = and i32 %x, 2147483655
  %2 = select i1 %cond, i32 %1, i32 %x
  %3 = ashr i32 %2, 1
  ret i32 %3
}

define i32 @ashr_select_and_false(i32 %x, i1 %cond) {
; CHECK-LABEL: @ashr_select_and_false(
; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], -1073741821
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = and i32 %x, 2147483655
  %2 = select i1 %cond, i32 %x, i32 %1
  %3 = ashr i32 %2, 1
  ret i32 %3
}

define i32 @shl_select_or_true(i32 %x, i1 %cond) {
; CHECK-LABEL: @shl_select_or_true(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], 14
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = or i32 %x, 7
  %2 = select i1 %cond, i32 %1, i32 %x
  %3 = shl i32 %2, 1
  ret i32 %3
}

define i32 @shl_select_or_false(i32 %x, i1 %cond) {
; CHECK-LABEL: @shl_select_or_false(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], 14
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = or i32 %x, 7
  %2 = select i1 %cond, i32 %x, i32 %1
  %3 = shl i32 %2, 1
  ret i32 %3
}

define i32 @lshr_select_or_true(i32 %x, i1 %cond) {
; CHECK-LABEL: @lshr_select_or_true(
; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], 3
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = or i32 %x, 7
  %2 = select i1 %cond, i32 %1, i32 %x
  %3 = lshr i32 %2, 1
  ret i32 %3
}

define i32 @lshr_select_or_false(i32 %x, i1 %cond) {
; CHECK-LABEL: @lshr_select_or_false(
; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], 3
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = or i32 %x, 7
  %2 = select i1 %cond, i32 %x, i32 %1
  %3 = lshr i32 %2, 1
  ret i32 %3
}

define i32 @ashr_select_or_true(i32 %x, i1 %cond) {
; CHECK-LABEL: @ashr_select_or_true(
; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], 3
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = or i32 %x, 7
  %2 = select i1 %cond, i32 %1, i32 %x
  %3 = ashr i32 %2, 1
  ret i32 %3
}

define i32 @ashr_select_or_false(i32 %x, i1 %cond) {
; CHECK-LABEL: @ashr_select_or_false(
; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], 3
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = or i32 %x, 7
  %2 = select i1 %cond, i32 %x, i32 %1
  %3 = ashr i32 %2, 1
  ret i32 %3
}

define i32 @shl_select_xor_true(i32 %x, i1 %cond) {
; CHECK-LABEL: @shl_select_xor_true(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], 14
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = xor i32 %x, 7
  %2 = select i1 %cond, i32 %1, i32 %x
  %3 = shl i32 %2, 1
  ret i32 %3
}

define i32 @shl_select_xor_false(i32 %x, i1 %cond) {
; CHECK-LABEL: @shl_select_xor_false(
; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], 14
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = xor i32 %x, 7
  %2 = select i1 %cond, i32 %x, i32 %1
  %3 = shl i32 %2, 1
  ret i32 %3
}

define i32 @lshr_select_xor_true(i32 %x, i1 %cond) {
; CHECK-LABEL: @lshr_select_xor_true(
; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], 3
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = xor i32 %x, 7
  %2 = select i1 %cond, i32 %1, i32 %x
  %3 = lshr i32 %2, 1
  ret i32 %3
}

define i32 @lshr_select_xor_false(i32 %x, i1 %cond) {
; CHECK-LABEL: @lshr_select_xor_false(
; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], 3
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = xor i32 %x, 7
  %2 = select i1 %cond, i32 %x, i32 %1
  %3 = lshr i32 %2, 1
  ret i32 %3
}

define i32 @ashr_select_xor_true(i32 %x, i1 %cond) {
; CHECK-LABEL: @ashr_select_xor_true(
; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], 3
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = xor i32 %x, 7
  %2 = select i1 %cond, i32 %1, i32 %x
  %3 = ashr i32 %2, 1
  ret i32 %3
}

define i32 @ashr_select_xor_false(i32 %x, i1 %cond) {
; CHECK-LABEL: @ashr_select_xor_false(
; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 1
; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], 3
; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[COND:%.*]], i32 [[TMP1]], i32 [[TMP2]]
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %1 = xor i32 %x, 7
  %2 = select i1 %cond, i32 %x, i32 %1
  %3 = ashr i32 %2, 1
  ret i32 %3
}

; OSS Fuzz #4871
; https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=4871
define i177 @lshr_out_of_range(i177 %Y, ptr %A2, ptr %ptr) {
; CHECK-LABEL: @lshr_out_of_range(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i177 [[Y:%.*]], -1
; CHECK-NEXT:    [[B4:%.*]] = sext i1 [[TMP1]] to i177
; CHECK-NEXT:    [[C8:%.*]] = icmp ult i177 [[B4]], [[Y]]
; CHECK-NEXT:    [[TMP2:%.*]] = sext i1 [[C8]] to i64
; CHECK-NEXT:    [[G18:%.*]] = getelementptr ptr, ptr [[A2:%.*]], i64 [[TMP2]]
; CHECK-NEXT:    store ptr [[G18]], ptr [[PTR:%.*]], align 8
; CHECK-NEXT:    ret i177 0
;
  %B5 = udiv i177 %Y, -1
  %B4 = add i177 %B5, -1
  %B2 = add i177 %B4, -1
  %B6 = mul i177 %B5, %B2
  %B3 = add i177 %B2, %B2
  %B10 = sub i177 %B5, %B3
  %B12 = lshr i177 %Y, %B6
  %C8 = icmp ugt i177 %B12, %B4
  %G18 = getelementptr ptr, ptr %A2, i1 %C8
  store ptr %G18, ptr %ptr
  %B1 = udiv i177 %B10, %B6
  ret i177 %B1
}

; OSS Fuzz #26716
; https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=26716
define i177 @lshr_out_of_range2(i177 %Y, ptr %A2, ptr %ptr) {
; CHECK-LABEL: @lshr_out_of_range2(
; CHECK-NEXT:    ret i177 0
;
  %B5 = udiv i177 %Y, -1
  %B = sdiv i177 %B5, -1
  %B4 = add i177 %B5, %B
  %B2 = add i177 %B4, -1
  %B6 = mul i177 %B5, %B2
  %B12 = lshr i177 %Y, %B6
  %C8 = icmp ugt i177 %B12, %B4
  %G18 = getelementptr ptr, ptr %A2, i1 %C8
  store ptr %G18, ptr %ptr, align 8
  %B1 = udiv i177 %B5, %B6
  ret i177 %B1
}

; OSS Fuzz #5032
; https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=5032
define void @ashr_out_of_range(ptr %A) {
; CHECK-LABEL: @ashr_out_of_range(
; CHECK-NEXT:    [[L:%.*]] = load i177, ptr [[A:%.*]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i177 [[L]], -1
; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i64 -1, i64 -2
; CHECK-NEXT:    [[G11:%.*]] = getelementptr i177, ptr [[A]], i64 [[TMP2]]
; CHECK-NEXT:    [[L7:%.*]] = load i177, ptr [[G11]], align 4
; CHECK-NEXT:    [[C171:%.*]] = icmp slt i177 [[L7]], 0
; CHECK-NEXT:    [[C17:%.*]] = select i1 [[TMP1]], i1 [[C171]], i1 false
; CHECK-NEXT:    [[TMP3:%.*]] = sext i1 [[C17]] to i64
; CHECK-NEXT:    [[G62:%.*]] = getelementptr i177, ptr [[G11]], i64 [[TMP3]]
; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i177 [[L7]], -1
; CHECK-NEXT:    [[B28:%.*]] = select i1 [[TMP4]], i177 0, i177 [[L7]]
; CHECK-NEXT:    store i177 [[B28]], ptr [[G62]], align 4
; CHECK-NEXT:    ret void
;
  %L = load i177, ptr %A
  %B5 = udiv i177 %L, -1
  %B4 = add i177 %B5, -1
  %B2 = add i177 %B4, -1
  %G11 = getelementptr i177, ptr %A, i177 %B2
  %L7 = load i177, ptr %G11
  %B6 = mul i177 %B5, %B2
  %B24 = ashr i177 %L7, %B6
  %B36 = and i177 %L7, %B4
  %C17 = icmp sgt i177 %B36, %B24
  %G62 = getelementptr i177, ptr %G11, i1 %C17
  %B28 = urem i177 %B24, %B6
  store i177 %B28, ptr %G62
  ret void
}

; OSS Fuzz #26135
; https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=26135
define void @ashr_out_of_range_1(ptr %A) {
; CHECK-LABEL: @ashr_out_of_range_1(
; CHECK-NEXT:    [[L:%.*]] = load i177, ptr [[A:%.*]], align 4
; CHECK-NEXT:    [[G11:%.*]] = getelementptr i177, ptr [[A]], i64 -1
; CHECK-NEXT:    [[B24_LOBIT:%.*]] = ashr i177 [[L]], 175
; CHECK-NEXT:    [[TMP1:%.*]] = trunc i177 [[B24_LOBIT]] to i64
; CHECK-NEXT:    [[G62:%.*]] = getelementptr i177, ptr [[G11]], i64 [[TMP1]]
; CHECK-NEXT:    store i177 0, ptr [[G62]], align 4
; CHECK-NEXT:    ret void
;
  %L = load i177, ptr %A, align 4
  %B5 = udiv i177 %L, -1
  %B4 = add i177 %B5, -1
  %B = and i177 %B4, %L
  %B2 = add i177 %B, -1
  %G11 = getelementptr i177, ptr %A, i177 %B2
  %B6 = mul i177 %B5, %B2
  %B24 = ashr i177 %L, %B6
  %C17 = icmp sgt i177 %B, %B24
  %G62 = getelementptr i177, ptr %G11, i1 %C17
  %B28 = urem i177 %B24, %B6
  store i177 %B28, ptr %G62, align 4
  ret void
}

; OSS Fuzz #38078
; https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=38078
define void @ossfuzz_38078(i32 %arg, i32 %arg1, ptr %ptr, ptr %ptr2, ptr %ptr3, ptr %ptr4, ptr %ptr5, ptr %ptr6, ptr %ptr7) {
; CHECK-LABEL: @ossfuzz_38078(
; CHECK-NEXT:  bb:
; CHECK-NEXT:    [[I2:%.*]] = add nsw i32 [[ARG:%.*]], [[ARG1:%.*]]
; CHECK-NEXT:    [[B3:%.*]] = or i32 [[I2]], 2147483647
; CHECK-NEXT:    [[G1:%.*]] = getelementptr i32, ptr [[PTR:%.*]], i64 -1
; CHECK-NEXT:    [[I5:%.*]] = icmp eq i32 [[I2]], 0
; CHECK-NEXT:    call void @llvm.assume(i1 [[I5]])
; CHECK-NEXT:    store volatile i32 [[B3]], ptr [[G1]], align 4
; CHECK-NEXT:    br label [[BB:%.*]]
; CHECK:       BB:
; CHECK-NEXT:    unreachable
;
bb:
  %i = or i32 0, -1
  %B24 = urem i32 %i, -2147483648
  %B21 = or i32 %i, %i
  %i2 = add nsw i32 %arg, %arg1
  %B7 = or i32 %i, %i2
  %B8 = and i32 %i, %i2
  %B12 = sdiv i32 %i2, %B7
  %B3 = add i32 %i2, %B24
  %B5 = and i32 %i, %B3
  %B18 = and i32 %i, %B8
  %i3 = xor i32 %i2, %B3
  %C1 = icmp ne i32 %B8, %B5
  %i4 = lshr i32 %B5, %i3
  %B29 = shl nuw i32 %B8, %i3
  %B2 = lshr i32 %B12, %i2
  %B16 = add i32 %B2, %i3
  %B = sdiv i32 %B29, %B5
  %B15 = sub i32 %i2, %B5
  %B22 = or i32 %B21, %B29
  %B23 = mul i32 %B15, %B
  %C2 = icmp sge i1 %C1, false
  %C7 = icmp sle i32 %i3, %B16
  %B20 = xor i32 %B21, %B22
  %G1 = getelementptr i32, ptr %ptr, i32 %B22
  %B1 = sub i32 %B, 0
  %B26 = ashr i32 %B29, 0
  %B4 = add i32 0, %B5
  %B27 = srem i32 %B12, %B21
  %i5 = icmp eq i32 %B20, %B18
  %C11 = icmp ugt i32 %i4, %B4
  call void @llvm.assume(i1 %i5)
  store volatile i32 %B4, ptr %G1, align 4
  %B11 = or i32 0, %B23
  br label %BB

BB:
  store i1 %C7, ptr %ptr2, align 1
  store i32 %B11, ptr %ptr3, align 4
  store i1 %C11, ptr %ptr4, align 1
  store i32 %B1, ptr %ptr5, align 4
  store i32 %B27, ptr %ptr6, align 4
  %C = icmp ne i32 %B26, 0
  %B17 = or i1 %C, %C2
  store i1 %B17, ptr %ptr7, align 1
  unreachable
}
declare void @llvm.assume(i1 noundef)

define i8 @lshr_mask_demand(i8 %x) {
; CHECK-LABEL: @lshr_mask_demand(
; CHECK-NEXT:    [[S:%.*]] = lshr i8 63, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = and i8 [[S]], 32
; CHECK-NEXT:    ret i8 [[R]]
;
  %s = lshr i8 63, %x ; 0b00111111
  %r = and i8 %s, 224 ; 0b11100000
  ret i8 %r
}

define i8 @shl_mask_demand(i8 %x) {
; CHECK-LABEL: @shl_mask_demand(
; CHECK-NEXT:    [[S:%.*]] = shl i8 12, [[X:%.*]]
; CHECK-NEXT:    [[R:%.*]] = and i8 [[S]], 4
; CHECK-NEXT:    ret i8 [[R]]
;
  %s = shl i8 12, %x ; 0b00001100
  %r = and i8 %s, 7  ; 0b00000111
  ret i8 %r
}

define i64 @lshr_mul_negpow2(i64 %x) {
; CHECK-LABEL: @lshr_mul_negpow2(
; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 0, [[X:%.*]]
; CHECK-NEXT:    [[A:%.*]] = and i64 [[TMP1]], 4294967295
; CHECK-NEXT:    ret i64 [[A]]
;
  %a = mul i64 %x, -4294967296
  %b = lshr i64 %a, 32
  ret i64 %b
}

define i64 @lshr_mul_negpow2_2(i64 %x) {
; CHECK-LABEL: @lshr_mul_negpow2_2(
; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 0, [[X:%.*]]
; CHECK-NEXT:    [[A:%.*]] = and i64 [[TMP1]], 281474976710655
; CHECK-NEXT:    ret i64 [[A]]
;
  %a = mul i64 %x, -65536
  %b = lshr i64 %a, 16
  ret i64 %b
}

define <2 x i32> @lshr_mul_negpow2_3(<2 x i32> %x) {
; CHECK-LABEL: @lshr_mul_negpow2_3(
; CHECK-NEXT:    [[TMP1:%.*]] = sub <2 x i32> zeroinitializer, [[X:%.*]]
; CHECK-NEXT:    [[A:%.*]] = and <2 x i32> [[TMP1]], <i32 255, i32 255>
; CHECK-NEXT:    ret <2 x i32> [[A]]
;
  %a = mul <2 x i32> %x, <i32 -16777216, i32 -16777216>
  %b = lshr <2 x i32> %a, <i32 24, i32 24>
  ret <2 x i32>  %b
}

define i32 @lshr_mul_negpow2_4(i32 %x) {
; CHECK-LABEL: @lshr_mul_negpow2_4(
; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 0, [[X:%.*]]
; CHECK-NEXT:    [[A:%.*]] = and i32 [[TMP1]], 65535
; CHECK-NEXT:    [[B:%.*]] = xor i32 [[A]], 1
; CHECK-NEXT:    ret i32 [[B]]
;
  %a = mul i32 %x, -65536
  %b = xor i32 %a, 65536
  %c = lshr i32 %b, 16
  ret i32 %c
}

define <2 x i32> @lshr_mul_negpow2_5(<2 x i32> %x) {
; CHECK-LABEL: @lshr_mul_negpow2_5(
; CHECK-NEXT:    [[TMP1:%.*]] = sub <2 x i32> zeroinitializer, [[X:%.*]]
; CHECK-NEXT:    [[A:%.*]] = and <2 x i32> [[TMP1]], <i32 65527, i32 65527>
; CHECK-NEXT:    [[B:%.*]] = or <2 x i32> [[A]], <i32 8, i32 8>
; CHECK-NEXT:    ret <2 x i32> [[B]]
;
  %a = mul <2 x i32> %x, <i32 -65536, i32 -65536>
  %b = or <2 x i32> %a, <i32 524288, i32 524288>
  %c = lshr <2 x i32> %b, <i32 16, i32 16>
  ret <2 x i32> %c
}

define i64 @lshr_mul_negpow2_extra_use(i64 %x) {
; CHECK-LABEL: @lshr_mul_negpow2_extra_use(
; CHECK-NEXT:    [[A:%.*]] = mul i64 [[X:%.*]], -4294967296
; CHECK-NEXT:    [[B:%.*]] = lshr exact i64 [[A]], 32
; CHECK-NEXT:    call void @use(i64 [[A]])
; CHECK-NEXT:    ret i64 [[B]]
;
  %a = mul i64 %x, -4294967296
  %b = lshr i64 %a, 32
  call void @use(i64 %a)
  ret i64 %b
}

define i8 @ashr_sdiv_pos(i8 %x) {
; CHECK-LABEL: @ashr_sdiv_pos(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i8 [[X:%.*]], -41
; CHECK-NEXT:    [[R:%.*]] = sext i1 [[TMP1]] to i8
; CHECK-NEXT:    ret i8 [[R]]
;
  %d = sdiv i8 %x, 42
  %r = ashr i8 %d, 7
  ret i8 %r
}

define <2 x i8> @ashr_sdiv_neg_splat_vec(<2 x i8> %x) {
; CHECK-LABEL: @ashr_sdiv_neg_splat_vec(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt <2 x i8> [[X:%.*]], <i8 41, i8 41>
; CHECK-NEXT:    [[R:%.*]] = sext <2 x i1> [[TMP1]] to <2 x i8>
; CHECK-NEXT:    ret <2 x i8> [[R]]
;
  %d = sdiv <2 x i8> %x, <i8 -42, i8 -42>
  %r = ashr <2 x i8> %d, <i8 7, i8 7>
  ret <2 x i8> %r
}

define <2 x i8> @ashr_sdiv_neg_splat_vec_poison(<2 x i8> %x) {
; CHECK-LABEL: @ashr_sdiv_neg_splat_vec_poison(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <2 x i8> [[X:%.*]], <i8 127, i8 127>
; CHECK-NEXT:    [[R:%.*]] = sext <2 x i1> [[TMP1]] to <2 x i8>
; CHECK-NEXT:    ret <2 x i8> [[R]]
;
  %d = sdiv <2 x i8> %x, <i8 -127, i8 -127>
  %r = ashr <2 x i8> %d, <i8 7, i8 poison>
  ret <2 x i8> %r
}

define i8 @lshr_sdiv_pos(i8 %x) {
; CHECK-LABEL: @lshr_sdiv_pos(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i8 [[X:%.*]], -11
; CHECK-NEXT:    [[R:%.*]] = zext i1 [[TMP1]] to i8
; CHECK-NEXT:    ret i8 [[R]]
;
  %d = sdiv i8 %x, 12
  %r = lshr i8 %d, 7
  ret i8 %r
}

define i18 @lshr_sdiv_neg(i18 %x) {
; CHECK-LABEL: @lshr_sdiv_neg(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i18 [[X:%.*]], 11
; CHECK-NEXT:    [[R:%.*]] = zext i1 [[TMP1]] to i18
; CHECK-NEXT:    ret i18 [[R]]
;
  %d = sdiv i18 %x, -12
  %r = lshr i18 %d, 17
  ret i18 %r
}

; negative test

define i8 @ashr_sdiv_not_full_shift(i8 %x) {
; CHECK-LABEL: @ashr_sdiv_not_full_shift(
; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[X:%.*]], 42
; CHECK-NEXT:    [[R:%.*]] = ashr i8 [[D]], 6
; CHECK-NEXT:    ret i8 [[R]]
;
  %d = sdiv i8 %x, 42
  %r = ashr i8 %d, 6
  ret i8 %r
}

; negative test

define i32 @ashr_sdiv_extra_use(i32 %x) {
; CHECK-LABEL: @ashr_sdiv_extra_use(
; CHECK-NEXT:    [[D:%.*]] = sdiv i32 [[X:%.*]], 42
; CHECK-NEXT:    call void @use_i32(i32 [[D]])
; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X]], -41
; CHECK-NEXT:    [[R:%.*]] = sext i1 [[TMP1]] to i32
; CHECK-NEXT:    ret i32 [[R]]
;
  %d = sdiv i32 %x, 42
  call void @use_i32(i32 %d)
  %r = ashr i32 %d, 31
  ret i32 %r
}