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

define i32 @sub1(i32 %x) {
; CHECK-LABEL: @sub1(
; CHECK-NEXT:    [[Y:%.*]] = sub i32 0, [[X:%.*]]
; CHECK-NEXT:    [[Z:%.*]] = sdiv i32 [[Y]], 337
; CHECK-NEXT:    ret i32 [[Z]]
;
  %y = sub i32 0, %x
  %z = sdiv i32 %y, 337
  ret i32 %z
}

define i32 @sub2(i32 %x) {
; CHECK-LABEL: @sub2(
; CHECK-NEXT:    [[Z:%.*]] = sdiv i32 [[X:%.*]], -337
; CHECK-NEXT:    ret i32 [[Z]]
;
  %y = sub nsw i32 0, %x
  %z = sdiv i32 %y, 337
  ret i32 %z
}

define i1 @shl_icmp(i64 %X) {
; CHECK-LABEL: @shl_icmp(
; CHECK-NEXT:    [[B:%.*]] = icmp eq i64 [[X:%.*]], 0
; CHECK-NEXT:    ret i1 [[B]]
;
  %A = shl nuw i64 %X, 2   ; X/4
  %B = icmp eq i64 %A, 0
  ret i1 %B
}

define i64 @shl1(i64 %X, ptr %P) {
; CHECK-LABEL: @shl1(
; CHECK-NEXT:    [[A:%.*]] = and i64 [[X:%.*]], 312
; CHECK-NEXT:    store i64 [[A]], ptr [[P:%.*]], align 4
; CHECK-NEXT:    [[B:%.*]] = shl nuw nsw i64 [[A]], 8
; CHECK-NEXT:    ret i64 [[B]]
;
  %A = and i64 %X, 312
  store i64 %A, ptr %P  ; multiple uses of A.
  %B = shl i64 %A, 8
  ret i64 %B
}

define i32 @preserve1(i32 %x) {
; CHECK-LABEL: @preserve1(
; CHECK-NEXT:    [[ADD3:%.*]] = add nsw i32 [[X:%.*]], 5
; CHECK-NEXT:    ret i32 [[ADD3]]
;
  %add = add nsw i32 %x, 2
  %add3 = add nsw i32 %add, 3
  ret i32 %add3
}

define i8 @nopreserve1(i8 %x) {
; CHECK-LABEL: @nopreserve1(
; CHECK-NEXT:    [[ADD3:%.*]] = add i8 [[X:%.*]], -126
; CHECK-NEXT:    ret i8 [[ADD3]]
;
  %add = add nsw i8 %x, 127
  %add3 = add nsw i8 %add, 3
  ret i8 %add3
}

define i8 @nopreserve2(i8 %x) {
; CHECK-LABEL: @nopreserve2(
; CHECK-NEXT:    [[ADD3:%.*]] = add i8 [[X:%.*]], 3
; CHECK-NEXT:    ret i8 [[ADD3]]
;
  %add = add i8 %x, 1
  %add3 = add nsw i8 %add, 2
  ret i8 %add3
}

define i8 @nopreserve3(i8 %A, i8 %B) {
; CHECK-LABEL: @nopreserve3(
; CHECK-NEXT:    [[Y:%.*]] = add i8 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[Y]], 20
; CHECK-NEXT:    ret i8 [[ADD]]
;
  %x = add i8 %A, 10
  %y = add i8 %B, 10
  %add = add nsw i8 %x, %y
  ret i8 %add
}

define i8 @nopreserve4(i8 %A, i8 %B) {
; CHECK-LABEL: @nopreserve4(
; CHECK-NEXT:    [[Y:%.*]] = add i8 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    [[ADD:%.*]] = add i8 [[Y]], 20
; CHECK-NEXT:    ret i8 [[ADD]]
;
  %x = add nsw i8 %A, 10
  %y = add nsw i8 %B, 10
  %add = add nsw i8 %x, %y
  ret i8 %add
}

define <3 x i32> @shl_nuw_nsw_shuffle_splat_vec(<2 x i8> %x) {
; CHECK-LABEL: @shl_nuw_nsw_shuffle_splat_vec(
; CHECK-NEXT:    [[T2:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i32>
; CHECK-NEXT:    [[SHUF:%.*]] = shufflevector <2 x i32> [[T2]], <2 x i32> poison, <3 x i32> <i32 1, i32 0, i32 1>
; CHECK-NEXT:    [[T3:%.*]] = shl nuw nsw <3 x i32> [[SHUF]], splat (i32 17)
; CHECK-NEXT:    ret <3 x i32> [[T3]]
;
  %t2 = zext <2 x i8> %x to <2 x i32>
  %shuf = shufflevector <2 x i32> %t2, <2 x i32> undef, <3 x i32> <i32 1, i32 0, i32 1>
  %t3 = shl <3 x i32> %shuf, <i32 17, i32 17, i32 17>
  ret <3 x i32> %t3
}

; Negative test - if the shuffle mask contains an undef, we bail out to
; avoid propagating information that may not be used consistently by callers.

define <3 x i32> @shl_nuw_nsw_shuffle_undef_elt_splat_vec(<2 x i8> %x) {
; CHECK-LABEL: @shl_nuw_nsw_shuffle_undef_elt_splat_vec(
; CHECK-NEXT:    [[T2:%.*]] = zext <2 x i8> [[X:%.*]] to <2 x i32>
; CHECK-NEXT:    [[SHUF:%.*]] = shufflevector <2 x i32> [[T2]], <2 x i32> poison, <3 x i32> <i32 1, i32 poison, i32 0>
; CHECK-NEXT:    [[T3:%.*]] = shl <3 x i32> [[SHUF]], splat (i32 17)
; CHECK-NEXT:    ret <3 x i32> [[T3]]
;
  %t2 = zext <2 x i8> %x to <2 x i32>
  %shuf = shufflevector <2 x i32> %t2, <2 x i32> undef, <3 x i32> <i32 1, i32 undef, i32 0>
  %t3 = shl <3 x i32> %shuf, <i32 17, i32 17, i32 17>
  ret <3 x i32> %t3
}

; Make sure we don't crash on a ConstantExpr shufflevector
define <vscale x 2 x i64> @mul_nuw_nsw_shuffle_constant_expr(<vscale x 2 x i8> %z) {
; CHECK-LABEL: @mul_nuw_nsw_shuffle_constant_expr(
; CHECK-NEXT:    [[XX:%.*]] = zext <vscale x 2 x i8> [[Z:%.*]] to <vscale x 2 x i64>
; CHECK-NEXT:    [[T3:%.*]] = mul <vscale x 2 x i64> [[XX]], shufflevector (<vscale x 2 x i64> insertelement (<vscale x 2 x i64> undef, i64 3, i32 0), <vscale x 2 x i64> zeroinitializer, <vscale x 2 x i32> zeroinitializer)
; CHECK-NEXT:    ret <vscale x 2 x i64> [[T3]]
;
  %xx = zext <vscale x 2 x i8> %z to <vscale x 2 x i64>
  %shuf = shufflevector <vscale x 2 x i64> insertelement (<vscale x 2 x i64> undef, i64 3, i32 0), <vscale x 2 x i64> zeroinitializer, <vscale x 2 x i32> zeroinitializer
  %t3 = mul <vscale x 2 x i64> %shuf, %xx
  ret <vscale x 2 x i64> %t3
}

; This could propagate nsw.

define i32 @neg_sub0_sub_nsw_nsw(i32 %a, i32 %b) {
; CHECK-LABEL: @neg_sub0_sub_nsw_nsw(
; CHECK-NEXT:    [[C_NEG:%.*]] = sub nsw i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT:    ret i32 [[C_NEG]]
;
  %c = sub nsw i32 %a, %b
  %d = sub nsw i32 0, %c
  ret i32 %d
}

; Must not propagate nsw.

define i32 @neg_sub_sub_nsw0(i32 %a, i32 %b) {
; CHECK-LABEL: @neg_sub_sub_nsw0(
; CHECK-NEXT:    [[C_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT:    ret i32 [[C_NEG]]
;
  %c = sub nsw i32 %a, %b
  %d = sub i32 0, %c
  ret i32 %d
}

; Must not propagate nsw.

define i32 @neg_sub_sub_nsw1(i32 %a, i32 %b) {
; CHECK-LABEL: @neg_sub_sub_nsw1(
; CHECK-NEXT:    [[C_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT:    ret i32 [[C_NEG]]
;
  %c = sub i32 %a, %b
  %d = sub nsw i32 0, %c
  ret i32 %d
}

; This could propagate nsw.

define i32 @neg_mul_sub_nsw_nsw(i32 %a, i32 %b) {
; CHECK-LABEL: @neg_mul_sub_nsw_nsw(
; CHECK-NEXT:    [[C_NEG:%.*]] = sub nsw i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT:    ret i32 [[C_NEG]]
;
  %c = sub nsw i32 %a, %b
  %d = mul nsw i32 -1, %c
  ret i32 %d
}

; Must not propagate nsw.

define i32 @neg_mul_sub_nsw0(i32 %a, i32 %b) {
; CHECK-LABEL: @neg_mul_sub_nsw0(
; CHECK-NEXT:    [[C_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT:    ret i32 [[C_NEG]]
;
  %c = sub nsw i32 %a, %b
  %d = mul i32 -1, %c
  ret i32 %d
}

; Must not propagate nsw.

define i32 @neg_mul_sub_nsw1(i32 %a, i32 %b) {
; CHECK-LABEL: @neg_mul_sub_nsw1(
; CHECK-NEXT:    [[C_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT:    ret i32 [[C_NEG]]
;
  %c = sub i32 %a, %b
  %d = mul nsw i32 -1, %c
  ret i32 %d
}

; Must not propagate nsw.

define i8 @neg_sub_sub2(i16 %a, i16 %b) {
; CHECK-LABEL: @neg_sub_sub2(
; CHECK-NEXT:    [[C_NEG:%.*]] = sub i16 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT:    [[D_NEG:%.*]] = trunc i16 [[C_NEG]] to i8
; CHECK-NEXT:    ret i8 [[D_NEG]]
;
  %c = sub nsw i16 %a, %b
  %d = trunc i16 %c to i8
  %e = sub nsw i8 0, %d
  ret i8 %e
}

; Must not propagate nsw.

define i32 @sub_sub0_nsw_nsw(i32 %a, i32 %b, i32 %c) {
; CHECK-LABEL: @sub_sub0_nsw_nsw(
; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[B:%.*]], [[C:%.*]]
; CHECK-NEXT:    [[S2:%.*]] = sub i32 [[A:%.*]], [[TMP1]]
; CHECK-NEXT:    ret i32 [[S2]]
;
  %s1 = sub nsw i32 %a, %b
  %s2 = sub nsw i32 %s1, %c
  ret i32 %s2
}

; Must not propagate nsw.

define i32 @sub_sub1_nsw_nsw(i32 %a, i32 %b, i32 %c) {
; CHECK-LABEL: @sub_sub1_nsw_nsw(
; CHECK-NEXT:    [[S1_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT:    [[S2:%.*]] = add i32 [[S1_NEG]], [[C:%.*]]
; CHECK-NEXT:    ret i32 [[S2]]
;
  %s1 = sub nsw i32 %a, %b
  %s2 = sub nsw i32 %c, %s1
  ret i32 %s2
}

define i8 @neg_nsw_freeze(i8 %a1, i8 %a2) {
; CHECK-LABEL: @neg_nsw_freeze(
; CHECK-NEXT:    [[A1_FR:%.*]] = freeze i8 [[A1:%.*]]
; CHECK-NEXT:    [[A2_FR:%.*]] = freeze i8 [[A2:%.*]]
; CHECK-NEXT:    [[A_NEG:%.*]] = sub i8 [[A2_FR]], [[A1_FR]]
; CHECK-NEXT:    ret i8 [[A_NEG]]
;
  %a = sub nsw i8 %a1, %a2
  %fr = freeze i8 %a
  %neg = sub nsw i8 0, %fr
  ret i8 %neg
}

define i8 @neg_nsw_phi(i1 %c, i8 %a1, i8 %a2, i8 %b1, i8 %b2) {
; CHECK-LABEL: @neg_nsw_phi(
; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
; CHECK:       if:
; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw i8 [[A2:%.*]], [[A1:%.*]]
; CHECK-NEXT:    br label [[JOIN:%.*]]
; CHECK:       else:
; CHECK-NEXT:    [[B_NEG:%.*]] = sub nsw i8 [[B2:%.*]], [[B1:%.*]]
; CHECK-NEXT:    br label [[JOIN]]
; CHECK:       join:
; CHECK-NEXT:    [[PHI_NEG:%.*]] = phi i8 [ [[A_NEG]], [[IF]] ], [ [[B_NEG]], [[ELSE]] ]
; CHECK-NEXT:    ret i8 [[PHI_NEG]]
;
  br i1 %c, label %if, label %else

if:
  %a = sub nsw i8 %a1, %a2
  br label %join

else:
  %b = sub nsw i8 %b1, %b2
  br label %join

join:
  %phi = phi i8 [ %a, %if ], [ %b, %else ]
  %neg = sub nsw i8 0, %phi
  ret i8 %neg
}

define i8 @neg_nsw_select(i1 %c, i8 %a1, i8 %a2, i8 %b1, i8 %b2) {
; CHECK-LABEL: @neg_nsw_select(
; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw i8 [[A2:%.*]], [[A1:%.*]]
; CHECK-NEXT:    [[B_NEG:%.*]] = sub nsw i8 [[B2:%.*]], [[B1:%.*]]
; CHECK-NEXT:    [[SEL_NEG:%.*]] = select i1 [[C:%.*]], i8 [[A_NEG]], i8 [[B_NEG]]
; CHECK-NEXT:    ret i8 [[SEL_NEG]]
;
  %a = sub nsw i8 %a1, %a2
  %b = sub nsw i8 %b1, %b2
  %sel = select i1 %c, i8 %a, i8 %b
  %neg = sub nsw i8 0, %sel
  ret i8 %neg
}

define <4 x i8> @neg_nsw_shufflevector(<2 x i8> %a1, <2 x i8> %a2, <2 x i8> %b1, <2 x i8> %b2) {
; CHECK-LABEL: @neg_nsw_shufflevector(
; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw <2 x i8> [[A2:%.*]], [[A1:%.*]]
; CHECK-NEXT:    [[B_NEG:%.*]] = sub nsw <2 x i8> [[B2:%.*]], [[B1:%.*]]
; CHECK-NEXT:    [[SHUF_NEG:%.*]] = shufflevector <2 x i8> [[A_NEG]], <2 x i8> [[B_NEG]], <4 x i32> <i32 0, i32 1, i32 2, i32 3>
; CHECK-NEXT:    ret <4 x i8> [[SHUF_NEG]]
;
  %a = sub nsw <2 x i8> %a1, %a2
  %b = sub nsw <2 x i8> %b1, %b2
  %shuf = shufflevector <2 x i8> %a, <2 x i8> %b, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
  %neg = sub nsw <4 x i8> zeroinitializer, %shuf
  ret <4 x i8> %neg
}

define i8 @neg_nsw_extractelement(<2 x i8> %a1, <2 x i8> %a2) {
; CHECK-LABEL: @neg_nsw_extractelement(
; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw <2 x i8> [[A2:%.*]], [[A1:%.*]]
; CHECK-NEXT:    [[EXTR_NEG:%.*]] = extractelement <2 x i8> [[A_NEG]], i64 0
; CHECK-NEXT:    ret i8 [[EXTR_NEG]]
;
  %a = sub nsw <2 x i8> %a1, %a2
  %extr = extractelement <2 x i8> %a, i32 0
  %neg = sub nsw i8 0, %extr
  ret i8 %neg
}

define <2 x i8> @neg_nsw_insertelement(<2 x i8> %a1, <2 x i8> %a2, i8 %b1, i8 %b2) {
; CHECK-LABEL: @neg_nsw_insertelement(
; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw <2 x i8> [[A2:%.*]], [[A1:%.*]]
; CHECK-NEXT:    [[B_NEG:%.*]] = sub nsw i8 [[B2:%.*]], [[B1:%.*]]
; CHECK-NEXT:    [[INSERT_NEG:%.*]] = insertelement <2 x i8> [[A_NEG]], i8 [[B_NEG]], i64 0
; CHECK-NEXT:    ret <2 x i8> [[INSERT_NEG]]
;
  %a = sub nsw <2 x i8> %a1, %a2
  %b = sub nsw i8 %b1, %b2
  %insert  = insertelement <2 x i8> %a, i8 %b, i32 0
  %neg = sub nsw <2 x i8> zeroinitializer, %insert
  ret <2 x i8> %neg
}

define i8 @neg_nsw_shl(i8 %a1, i8 %a2, i8 %b) {
; CHECK-LABEL: @neg_nsw_shl(
; CHECK-NEXT:    [[A_NEG:%.*]] = sub nsw i8 [[A2:%.*]], [[A1:%.*]]
; CHECK-NEXT:    [[SHL_NEG:%.*]] = shl nsw i8 [[A_NEG]], [[B:%.*]]
; CHECK-NEXT:    ret i8 [[SHL_NEG]]
;
  %a = sub nsw i8 %a1, %a2
  %shl = shl nsw i8 %a, %b
  %neg = sub nsw i8 0, %shl
  ret i8 %neg
}

define i8 @neg_nsw_shl_missing_nsw_on_shl(i8 %a1, i8 %a2, i8 %b) {
; CHECK-LABEL: @neg_nsw_shl_missing_nsw_on_shl(
; CHECK-NEXT:    [[A_NEG:%.*]] = sub i8 [[A2:%.*]], [[A1:%.*]]
; CHECK-NEXT:    [[SHL_NEG:%.*]] = shl i8 [[A_NEG]], [[B:%.*]]
; CHECK-NEXT:    ret i8 [[SHL_NEG]]
;
  %a = sub nsw i8 %a1, %a2
  %shl = shl i8 %a, %b
  %neg = sub nsw i8 0, %shl
  ret i8 %neg
}

define i8 @neg_nsw_shl_to_mul(i8 %a, i8 %b) {
; CHECK-LABEL: @neg_nsw_shl_to_mul(
; CHECK-NEXT:    [[SHL_NEG:%.*]] = mul nsw i8 [[A:%.*]], -2
; CHECK-NEXT:    ret i8 [[SHL_NEG]]
;
  %shl = shl nsw i8 %a, 1
  %neg = sub nsw i8 0, %shl
  ret i8 %neg
}

define i8 @neg_nsw_shl_to_mul_missing_nsw_on_shl(i8 %a, i8 %b) {
; CHECK-LABEL: @neg_nsw_shl_to_mul_missing_nsw_on_shl(
; CHECK-NEXT:    [[SHL_NEG:%.*]] = mul i8 [[A:%.*]], -2
; CHECK-NEXT:    ret i8 [[SHL_NEG]]
;
  %shl = shl i8 %a, 1
  %neg = sub nsw i8 0, %shl
  ret i8 %neg
}

define i8 @neg_nsw_mul(i8 %a1, i8 %a2, i8 %b) {
; CHECK-LABEL: @neg_nsw_mul(
; CHECK-NEXT:    [[A_NEG:%.*]] = sub i8 [[A2:%.*]], [[A1:%.*]]
; CHECK-NEXT:    [[SHL_NEG:%.*]] = mul nsw i8 [[A_NEG]], [[B:%.*]]
; CHECK-NEXT:    ret i8 [[SHL_NEG]]
;
  %a = sub nsw i8 %a1, %a2
  %shl = mul nsw i8 %a, %b
  %neg = sub nsw i8 0, %shl
  ret i8 %neg
}

define i8 @neg_nsw_mul_missing_nsw_on_mul(i8 %a1, i8 %a2, i8 %b) {
; CHECK-LABEL: @neg_nsw_mul_missing_nsw_on_mul(
; CHECK-NEXT:    [[A_NEG:%.*]] = sub i8 [[A2:%.*]], [[A1:%.*]]
; CHECK-NEXT:    [[SHL_NEG:%.*]] = mul i8 [[A_NEG]], [[B:%.*]]
; CHECK-NEXT:    ret i8 [[SHL_NEG]]
;
  %a = sub nsw i8 %a1, %a2
  %shl = mul i8 %a, %b
  %neg = sub nsw i8 0, %shl
  ret i8 %neg
}

; This could propagate nsw.

define i16 @mul_nsw_reassoc_prop(i16 %x) {
; CHECK-LABEL: @mul_nsw_reassoc_prop(
; CHECK-NEXT:    [[B:%.*]] = mul nsw i16 [[X:%.*]], 6
; CHECK-NEXT:    ret i16 [[B]]
;
  %a = mul nsw i16 %x, 3
  %b = mul nsw i16 %a, 2
  ret i16 %b
}

; This could propagate nsw.

define i16 @mul_nsw_reassoc_prop_neg(i16 %x) {
; CHECK-LABEL: @mul_nsw_reassoc_prop_neg(
; CHECK-NEXT:    [[B:%.*]] = mul nsw i16 [[X:%.*]], -2201
; CHECK-NEXT:    ret i16 [[B]]
;
  %a = mul nsw i16 %x, -71
  %b = mul nsw i16 %a, 31
  ret i16 %b
}

; Must not propagate nsw.

define i16 @mul_nsw_reassoc_prop_no_nsw1(i16 %x) {
; CHECK-LABEL: @mul_nsw_reassoc_prop_no_nsw1(
; CHECK-NEXT:    [[B:%.*]] = mul i16 [[X:%.*]], 6
; CHECK-NEXT:    ret i16 [[B]]
;
  %a = mul i16 %x, 3
  %b = mul nsw i16 %a, 2
  ret i16 %b
}

; Must not propagate nsw.

define i16 @mul_nsw_reassoc_prop_no_nsw2(i16 %x) {
; CHECK-LABEL: @mul_nsw_reassoc_prop_no_nsw2(
; CHECK-NEXT:    [[B:%.*]] = mul i16 [[X:%.*]], 6
; CHECK-NEXT:    ret i16 [[B]]
;
  %a = mul nsw i16 %x, 3
  %b = mul i16 %a, 2
  ret i16 %b
}

; Must not propagate nsw.

define i16 @mul_nsw_reassoc_prop_overflow(i16 %x) {
; CHECK-LABEL: @mul_nsw_reassoc_prop_overflow(
; CHECK-NEXT:    [[B:%.*]] = mul i16 [[X:%.*]], -31777
; CHECK-NEXT:    ret i16 [[B]]
;
  %a = mul nsw i16 %x, 1023
  %b = mul nsw i16 %a, 33
  ret i16 %b
}