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

declare void @use1(i1)
declare void @use8(i8)
declare void @f1()
declare void @f2()

define i32 @test1(i32 %A) {
; CHECK-LABEL: @test1(
; CHECK-NEXT:    ret i32 [[A:%.*]]
;
  %B = xor i32 %A, -1
  %C = xor i32 %B, -1
  ret i32 %C
}

define i1 @invert_icmp(i32 %A, i32 %B) {
; CHECK-LABEL: @invert_icmp(
; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    ret i1 [[CMP_NOT]]
;
  %cmp = icmp sle i32 %A, %B
  %not = xor i1 %cmp, true
  ret i1 %not
}

; PR1570

define i1 @invert_fcmp(float %X, float %Y) {
; CHECK-LABEL: @invert_fcmp(
; CHECK-NEXT:    [[CMP:%.*]] = fcmp uge float [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %cmp = fcmp olt float %X, %Y
  %not = xor i1 %cmp, true
  ret i1 %not
}

; PR2298

define i1 @not_not_cmp(i32 %a, i32 %b) {
; CHECK-LABEL: @not_not_cmp(
; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %nota = xor i32 %a, -1
  %notb = xor i32 %b, -1
  %cmp = icmp slt i32 %nota, %notb
  ret i1 %cmp
}

define <2 x i1> @not_not_cmp_vector(<2 x i32> %a, <2 x i32> %b) {
; CHECK-LABEL: @not_not_cmp_vector(
; CHECK-NEXT:    [[CMP:%.*]] = icmp ult <2 x i32> [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    ret <2 x i1> [[CMP]]
;
  %nota = xor <2 x i32> %a, <i32 -1, i32 -1>
  %notb = xor <2 x i32> %b, <i32 -1, i32 -1>
  %cmp = icmp ugt <2 x i32> %nota, %notb
  ret <2 x i1> %cmp
}

define i1 @not_cmp_constant(i32 %a) {
; CHECK-LABEL: @not_cmp_constant(
; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A:%.*]], -43
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %nota = xor i32 %a, -1
  %cmp = icmp ugt i32 %nota, 42
  ret i1 %cmp
}

define <2 x i1> @not_cmp_constant_vector(<2 x i32> %a) {
; CHECK-LABEL: @not_cmp_constant_vector(
; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt <2 x i32> [[A:%.*]], splat (i32 -43)
; CHECK-NEXT:    ret <2 x i1> [[CMP]]
;
  %nota = xor <2 x i32> %a, <i32 -1, i32 -1>
  %cmp = icmp slt <2 x i32> %nota, <i32 42, i32 42>
  ret <2 x i1> %cmp
}

define <2 x i1> @test7(<2 x i32> %A, <2 x i32> %B) {
; CHECK-LABEL: @test7(
; CHECK-NEXT:    [[COND_NOT:%.*]] = icmp sgt <2 x i32> [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    ret <2 x i1> [[COND_NOT]]
;
  %cond = icmp sle <2 x i32> %A, %B
  %Ret = xor <2 x i1> %cond, <i1 true, i1 true>
  ret <2 x i1> %Ret
}

define i32 @not_ashr_not(i32 %A, i32 %B) {
; CHECK-LABEL: @not_ashr_not(
; CHECK-NEXT:    [[NOT1_NOT:%.*]] = ashr i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    ret i32 [[NOT1_NOT]]
;
  %not1 = xor i32 %A, -1
  %ashr = ashr i32 %not1, %B
  %not2 = xor i32 %ashr, -1
  ret i32 %not2
}

define i8 @not_ashr_const(i8 %x) {
; CHECK-LABEL: @not_ashr_const(
; CHECK-NEXT:    [[NOT:%.*]] = lshr i8 41, [[X:%.*]]
; CHECK-NEXT:    ret i8 [[NOT]]
;
  %shr = ashr i8 -42, %x
  %not = xor i8 %shr, -1
  ret i8 %not
}

define <2 x i8> @not_ashr_const_splat(<2 x i8> %x) {
; CHECK-LABEL: @not_ashr_const_splat(
; CHECK-NEXT:    [[NOT:%.*]] = lshr <2 x i8> splat (i8 41), [[X:%.*]]
; CHECK-NEXT:    ret <2 x i8> [[NOT]]
;
  %shr = ashr <2 x i8> <i8 -42, i8 -42>, %x
  %not = xor <2 x i8> %shr, <i8 -1, i8 -1>
  ret <2 x i8> %not
}

; We can't get rid of the 'not' on a logical shift of a negative constant.

define i8 @not_lshr_const_negative(i8 %x) {
; CHECK-LABEL: @not_lshr_const_negative(
; CHECK-NEXT:    [[SHR:%.*]] = lshr i8 -42, [[X:%.*]]
; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[SHR]], -1
; CHECK-NEXT:    ret i8 [[NOT]]
;
  %shr = lshr i8 -42, %x
  %not = xor i8 %shr, -1
  ret i8 %not
}

define i8 @not_lshr_const(i8 %x) {
; CHECK-LABEL: @not_lshr_const(
; CHECK-NEXT:    [[NOT:%.*]] = ashr i8 -43, [[X:%.*]]
; CHECK-NEXT:    ret i8 [[NOT]]
;
  %shr = lshr i8 42, %x
  %not = xor i8 %shr, -1
  ret i8 %not
}

define <2 x i8> @not_lshr_const_splat(<2 x i8> %x) {
; CHECK-LABEL: @not_lshr_const_splat(
; CHECK-NEXT:    [[NOT:%.*]] = ashr <2 x i8> splat (i8 -43), [[X:%.*]]
; CHECK-NEXT:    ret <2 x i8> [[NOT]]
;
  %shr = lshr <2 x i8> <i8 42, i8 42>, %x
  %not = xor <2 x i8> %shr, <i8 -1, i8 -1>
  ret <2 x i8> %not
}

define i32 @not_sub(i32 %y) {
; CHECK-LABEL: @not_sub(
; CHECK-NEXT:    [[R:%.*]] = add i32 [[Y:%.*]], -124
; CHECK-NEXT:    ret i32 [[R]]
;
  %s = sub i32 123, %y
  %r = xor i32 %s, -1
  ret i32 %r
}

define i32 @not_sub_extra_use(i32 %y, ptr %p) {
; CHECK-LABEL: @not_sub_extra_use(
; CHECK-NEXT:    [[S:%.*]] = sub i32 123, [[Y:%.*]]
; CHECK-NEXT:    store i32 [[S]], ptr [[P:%.*]], align 4
; CHECK-NEXT:    [[R:%.*]] = add i32 [[Y]], -124
; CHECK-NEXT:    ret i32 [[R]]
;
  %s = sub i32 123, %y
  store i32 %s, ptr %p
  %r = xor i32 %s, -1
  ret i32 %r
}

define <2 x i32> @not_sub_splat(<2 x i32> %y) {
; CHECK-LABEL: @not_sub_splat(
; CHECK-NEXT:    [[R:%.*]] = add <2 x i32> [[Y:%.*]], splat (i32 -124)
; CHECK-NEXT:    ret <2 x i32> [[R]]
;
  %s = sub <2 x i32> <i32 123, i32 123>, %y
  %r = xor <2 x i32> %s, <i32 -1, i32 -1>
  ret <2 x i32> %r
}

define <2 x i32> @not_sub_extra_use_splat(<2 x i32> %y, ptr %p) {
; CHECK-LABEL: @not_sub_extra_use_splat(
; CHECK-NEXT:    [[S:%.*]] = sub <2 x i32> splat (i32 123), [[Y:%.*]]
; CHECK-NEXT:    store <2 x i32> [[S]], ptr [[P:%.*]], align 8
; CHECK-NEXT:    [[R:%.*]] = add <2 x i32> [[Y]], splat (i32 -124)
; CHECK-NEXT:    ret <2 x i32> [[R]]
;
  %s = sub <2 x i32> <i32 123, i32 123>, %y
  store <2 x i32> %s, ptr %p
  %r = xor <2 x i32> %s, <i32 -1, i32 -1>
  ret <2 x i32> %r
}

define <2 x i32> @not_sub_vec(<2 x i32> %y) {
; CHECK-LABEL: @not_sub_vec(
; CHECK-NEXT:    [[R:%.*]] = add <2 x i32> [[Y:%.*]], <i32 -43, i32 -124>
; CHECK-NEXT:    ret <2 x i32> [[R]]
;
  %s = sub <2 x i32> <i32 42, i32 123>, %y
  %r = xor <2 x i32> %s, <i32 -1, i32 -1>
  ret <2 x i32> %r
}

define <2 x i32> @not_sub_extra_use_vec(<2 x i32> %y, ptr %p) {
; CHECK-LABEL: @not_sub_extra_use_vec(
; CHECK-NEXT:    [[S:%.*]] = sub <2 x i32> <i32 123, i32 42>, [[Y:%.*]]
; CHECK-NEXT:    store <2 x i32> [[S]], ptr [[P:%.*]], align 8
; CHECK-NEXT:    [[R:%.*]] = add <2 x i32> [[Y]], <i32 -124, i32 -43>
; CHECK-NEXT:    ret <2 x i32> [[R]]
;
  %s = sub <2 x i32> <i32 123, i32 42>, %y
  store <2 x i32> %s, ptr %p
  %r = xor <2 x i32> %s, <i32 -1, i32 -1>
  ret <2 x i32> %r
}

; ~(X + C) --> -X - C - 1 --> -(C + 1) - X

define i32 @not_add(i32 %x) {
; CHECK-LABEL: @not_add(
; CHECK-NEXT:    [[R:%.*]] = sub i32 -124, [[X:%.*]]
; CHECK-NEXT:    ret i32 [[R]]
;
  %a = add i32 %x, 123
  %r = xor i32 %a, -1
  ret i32 %r
}

define <2 x i32> @not_add_splat(<2 x i32> %x) {
; CHECK-LABEL: @not_add_splat(
; CHECK-NEXT:    [[R:%.*]] = sub <2 x i32> splat (i32 -124), [[X:%.*]]
; CHECK-NEXT:    ret <2 x i32> [[R]]
;
  %a = add <2 x i32> %x, <i32 123, i32 123>
  %r = xor <2 x i32> %a, <i32 -1, i32 -1>
  ret <2 x i32> %r
}

define <2 x i32> @not_add_vec(<2 x i32> %x) {
; CHECK-LABEL: @not_add_vec(
; CHECK-NEXT:    [[R:%.*]] = sub <2 x i32> <i32 -43, i32 -124>, [[X:%.*]]
; CHECK-NEXT:    ret <2 x i32> [[R]]
;
  %a = add <2 x i32> %x, <i32 42, i32 123>
  %r = xor <2 x i32> %a, <i32 -1, i32 -1>
  ret <2 x i32> %r
}

define i1 @not_select_cmp_cmp(i32 %x, i32 %y, float %z, float %w, i1 %cond) {
; CHECK-LABEL: @not_select_cmp_cmp(
; CHECK-NEXT:    [[CMPT:%.*]] = icmp sgt i32 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    [[CMPF:%.*]] = fcmp ole float [[Z:%.*]], [[W:%.*]]
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMPT]], i1 [[CMPF]]
; CHECK-NEXT:    ret i1 [[SEL]]
;
  %cmpt = icmp sle i32 %x, %y
  %cmpf = fcmp ugt float %z, %w
  %sel = select i1 %cond, i1 %cmpt, i1 %cmpf
  %not = xor i1 %sel, true
  ret i1 %not
}

; TODO: Missed canonicalization - hoist 'not'?

define i1 @not_select_cmp_cmp_extra_use1(i32 %x, i32 %y, float %z, float %w, i1 %cond) {
; CHECK-LABEL: @not_select_cmp_cmp_extra_use1(
; CHECK-NEXT:    [[CMPT:%.*]] = icmp sle i32 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    call void @use1(i1 [[CMPT]])
; CHECK-NEXT:    [[CMPF:%.*]] = fcmp ugt float [[Z:%.*]], [[W:%.*]]
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMPT]], i1 [[CMPF]]
; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
; CHECK-NEXT:    ret i1 [[NOT]]
;
  %cmpt = icmp sle i32 %x, %y
  call void @use1(i1 %cmpt)
  %cmpf = fcmp ugt float %z, %w
  %sel = select i1 %cond, i1 %cmpt, i1 %cmpf
  %not = xor i1 %sel, true
  ret i1 %not
}

; TODO: Missed canonicalization - hoist 'not'?

define i1 @not_select_cmp_cmp_extra_use2(i32 %x, i32 %y, float %z, float %w, i1 %cond) {
; CHECK-LABEL: @not_select_cmp_cmp_extra_use2(
; CHECK-NEXT:    [[CMPT:%.*]] = icmp sle i32 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    [[CMPF:%.*]] = fcmp ugt float [[Z:%.*]], [[W:%.*]]
; CHECK-NEXT:    call void @use1(i1 [[CMPF]])
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMPT]], i1 [[CMPF]]
; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
; CHECK-NEXT:    ret i1 [[NOT]]
;
  %cmpt = icmp sle i32 %x, %y
  %cmpf = fcmp ugt float %z, %w
  call void @use1(i1 %cmpf)
  %sel = select i1 %cond, i1 %cmpt, i1 %cmpf
  %not = xor i1 %sel, true
  ret i1 %not
}

; Negative test - extra uses would require more instructions.

define i1 @not_select_cmp_cmp_extra_use3(i32 %x, i32 %y, float %z, float %w, i1 %cond) {
; CHECK-LABEL: @not_select_cmp_cmp_extra_use3(
; CHECK-NEXT:    [[CMPT:%.*]] = icmp sle i32 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    call void @use1(i1 [[CMPT]])
; CHECK-NEXT:    [[CMPF:%.*]] = fcmp ugt float [[Z:%.*]], [[W:%.*]]
; CHECK-NEXT:    call void @use1(i1 [[CMPF]])
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMPT]], i1 [[CMPF]]
; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
; CHECK-NEXT:    ret i1 [[NOT]]
;
  %cmpt = icmp sle i32 %x, %y
  call void @use1(i1 %cmpt)
  %cmpf = fcmp ugt float %z, %w
  call void @use1(i1 %cmpf)
  %sel = select i1 %cond, i1 %cmpt, i1 %cmpf
  %not = xor i1 %sel, true
  ret i1 %not
}

; Negative test - extra uses would require more instructions.

define i1 @not_select_cmp_cmp_extra_use4(i32 %x, i32 %y, float %z, float %w, i1 %cond) {
; CHECK-LABEL: @not_select_cmp_cmp_extra_use4(
; CHECK-NEXT:    [[CMPT:%.*]] = icmp sle i32 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    [[CMPF:%.*]] = fcmp ugt float [[Z:%.*]], [[W:%.*]]
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMPT]], i1 [[CMPF]]
; CHECK-NEXT:    call void @use1(i1 [[SEL]])
; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
; CHECK-NEXT:    ret i1 [[NOT]]
;
  %cmpt = icmp sle i32 %x, %y
  %cmpf = fcmp ugt float %z, %w
  %sel = select i1 %cond, i1 %cmpt, i1 %cmpf
  call void @use1(i1 %sel)
  %not = xor i1 %sel, true
  ret i1 %not
}

; TODO: Missed canonicalization - hoist 'not'?

define i1 @not_select_cmpt(double %x, double %y, i1 %z, i1 %cond) {
; CHECK-LABEL: @not_select_cmpt(
; CHECK-NEXT:    [[CMPT:%.*]] = fcmp oeq double [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMPT]], i1 [[Z:%.*]]
; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
; CHECK-NEXT:    ret i1 [[NOT]]
;
  %cmpt = fcmp oeq double %x, %y
  %sel = select i1 %cond, i1 %cmpt, i1 %z
  %not = xor i1 %sel, true
  ret i1 %not
}

; TODO: Missed canonicalization - hoist 'not'?

define i1 @not_select_cmpf(i1 %x, i32 %z, i32 %w, i1 %cond) {
; CHECK-LABEL: @not_select_cmpf(
; CHECK-NEXT:    [[CMPF:%.*]] = icmp ugt i32 [[Z:%.*]], [[W:%.*]]
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[X:%.*]], i1 [[CMPF]]
; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
; CHECK-NEXT:    ret i1 [[NOT]]
;
  %cmpf = icmp ugt i32 %z, %w
  %sel = select i1 %cond, i1 %x, i1 %cmpf
  %not = xor i1 %sel, true
  ret i1 %not
}

define i1 @not_select_cmpt_extra_use(double %x, double %y, i1 %z, i1 %cond) {
; CHECK-LABEL: @not_select_cmpt_extra_use(
; CHECK-NEXT:    [[CMPT:%.*]] = fcmp oeq double [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    call void @use1(i1 [[CMPT]])
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[CMPT]], i1 [[Z:%.*]]
; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
; CHECK-NEXT:    ret i1 [[NOT]]
;
  %cmpt = fcmp oeq double %x, %y
  call void @use1(i1 %cmpt)
  %sel = select i1 %cond, i1 %cmpt, i1 %z
  %not = xor i1 %sel, true
  ret i1 %not
}

define i1 @not_select_cmpf_extra_use(i1 %x, i32 %z, i32 %w, i1 %cond) {
; CHECK-LABEL: @not_select_cmpf_extra_use(
; CHECK-NEXT:    [[CMPF:%.*]] = icmp ugt i32 [[Z:%.*]], [[W:%.*]]
; CHECK-NEXT:    call void @use1(i1 [[CMPF]])
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i1 [[X:%.*]], i1 [[CMPF]]
; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[SEL]], true
; CHECK-NEXT:    ret i1 [[NOT]]
;
  %cmpf = icmp ugt i32 %z, %w
  call void @use1(i1 %cmpf)
  %sel = select i1 %cond, i1 %x, i1 %cmpf
  %not = xor i1 %sel, true
  ret i1 %not
}

define i8 @not_or_neg(i8 %x, i8 %y)  {
; CHECK-LABEL: @not_or_neg(
; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[Y:%.*]], -1
; CHECK-NEXT:    [[TMP2:%.*]] = xor i8 [[X:%.*]], -1
; CHECK-NEXT:    [[NOT:%.*]] = and i8 [[TMP1]], [[TMP2]]
; CHECK-NEXT:    ret i8 [[NOT]]
;
  %s = sub i8 0, %y
  %o = or i8 %s, %x
  %not = xor i8 %o, -1
  ret i8 %not
}

define <3 x i5> @not_or_neg_commute_vec(<3 x i5> %x, <3 x i5> %p)  {
; CHECK-LABEL: @not_or_neg_commute_vec(
; CHECK-NEXT:    [[Y:%.*]] = mul <3 x i5> [[P:%.*]], <i5 1, i5 2, i5 3>
; CHECK-NEXT:    [[TMP1:%.*]] = add <3 x i5> [[X:%.*]], splat (i5 -1)
; CHECK-NEXT:    [[TMP2:%.*]] = xor <3 x i5> [[Y]], splat (i5 -1)
; CHECK-NEXT:    [[NOT:%.*]] = and <3 x i5> [[TMP1]], [[TMP2]]
; CHECK-NEXT:    ret <3 x i5> [[NOT]]
;
  %y = mul <3 x i5> %p, <i5 1, i5 2, i5 3> ; thwart complexity-based-canonicalization
  %s = sub <3 x i5> <i5 0, i5 0, i5 poison>, %x
  %o = or <3 x i5> %y, %s
  %not = xor <3 x i5> %o, <i5 -1, i5 poison, i5 -1>
  ret <3 x i5> %not
}

; negative test

define i8 @not_or_neg_use1(i8 %x, i8 %y)  {
; CHECK-LABEL: @not_or_neg_use1(
; CHECK-NEXT:    [[S:%.*]] = sub i8 0, [[Y:%.*]]
; CHECK-NEXT:    call void @use8(i8 [[S]])
; CHECK-NEXT:    [[O:%.*]] = or i8 [[X:%.*]], [[S]]
; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[O]], -1
; CHECK-NEXT:    ret i8 [[NOT]]
;
  %s = sub i8 0, %y
  call void @use8(i8 %s)
  %o = or i8 %s, %x
  %not = xor i8 %o, -1
  ret i8 %not
}

; negative test

define i8 @not_or_neg_use2(i8 %x, i8 %y)  {
; CHECK-LABEL: @not_or_neg_use2(
; CHECK-NEXT:    [[S:%.*]] = sub i8 0, [[Y:%.*]]
; CHECK-NEXT:    [[O:%.*]] = or i8 [[X:%.*]], [[S]]
; CHECK-NEXT:    call void @use8(i8 [[O]])
; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[O]], -1
; CHECK-NEXT:    ret i8 [[NOT]]
;
  %s = sub i8 0, %y
  %o = or i8 %s, %x
  call void @use8(i8 %o)
  %not = xor i8 %o, -1
  ret i8 %not
}

define i1 @not_select_bool(i1 %x, i1 %y, i1 %z) {
; CHECK-LABEL: @not_select_bool(
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 [[Z:%.*]]
; CHECK-NEXT:    [[R:%.*]] = xor i1 [[SEL]], true
; CHECK-NEXT:    ret i1 [[R]]
;
  %sel = select i1 %x, i1 %y, i1 %z
  %r = xor i1 %sel, true
  ret i1 %r
}

define i1 @not_select_bool_const1(i1 %x, i1 %y) {
; CHECK-LABEL: @not_select_bool_const1(
; CHECK-NEXT:    [[Y_NOT:%.*]] = xor i1 [[Y:%.*]], true
; CHECK-NEXT:    [[R:%.*]] = select i1 [[X:%.*]], i1 [[Y_NOT]], i1 false
; CHECK-NEXT:    ret i1 [[R]]
;
  %sel = select i1 %x, i1 %y, i1 true
  %r = xor i1 %sel, true
  ret i1 %r
}

define i1 @not_select_bool_const2(i1 %x, i1 %y) {
; CHECK-LABEL: @not_select_bool_const2(
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 false
; CHECK-NEXT:    [[R:%.*]] = xor i1 [[SEL]], true
; CHECK-NEXT:    ret i1 [[R]]
;
  %sel = select i1 %x, i1 %y, i1 false
  %r = xor i1 %sel, true
  ret i1 %r
}

define i1 @not_select_bool_const3(i1 %x, i1 %y) {
; CHECK-LABEL: @not_select_bool_const3(
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]]
; CHECK-NEXT:    [[R:%.*]] = xor i1 [[SEL]], true
; CHECK-NEXT:    ret i1 [[R]]
;
  %sel = select i1 %x, i1 true, i1 %y
  %r = xor i1 %sel, true
  ret i1 %r
}

define i1 @not_select_bool_const4(i1 %x, i1 %y) {
; CHECK-LABEL: @not_select_bool_const4(
; CHECK-NEXT:    [[Y_NOT:%.*]] = xor i1 [[Y:%.*]], true
; CHECK-NEXT:    [[R:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y_NOT]]
; CHECK-NEXT:    ret i1 [[R]]
;
  %sel = select i1 %x, i1 false, i1 %y
  %r = xor i1 %sel, true
  ret i1 %r
}

define <2 x i1> @not_logicalAnd_not_op0(<2 x i1> %x, <2 x i1> %y) {
; CHECK-LABEL: @not_logicalAnd_not_op0(
; CHECK-NEXT:    [[Y_NOT:%.*]] = xor <2 x i1> [[Y:%.*]], splat (i1 true)
; CHECK-NEXT:    [[NOTAND:%.*]] = select <2 x i1> [[X:%.*]], <2 x i1> splat (i1 true), <2 x i1> [[Y_NOT]]
; CHECK-NEXT:    ret <2 x i1> [[NOTAND]]
;
  %notx = xor <2 x i1> %x, <i1 true, i1 true>
  %and = select <2 x i1> %notx, <2 x i1> %y, <2 x i1> zeroinitializer
  %notand = xor <2 x i1> %and, <i1 true, i1 true>
  ret <2 x i1> %notand
}

define i1 @not_logicalAnd_not_op1(i1 %x, i1 %y) {
; CHECK-LABEL: @not_logicalAnd_not_op1(
; CHECK-NEXT:    [[NOT_X:%.*]] = xor i1 [[X:%.*]], true
; CHECK-NEXT:    [[NOTAND:%.*]] = select i1 [[NOT_X]], i1 true, i1 [[Y:%.*]]
; CHECK-NEXT:    ret i1 [[NOTAND]]
;
  %noty = xor i1 %y, true
  %and = select i1 %x, i1 %noty, i1 false
  %notand = xor i1 %and, true
  ret i1 %notand
}

define i1 @not_logicalAnd_not_op0_use1(i1 %x, i1 %y) {
; CHECK-LABEL: @not_logicalAnd_not_op0_use1(
; CHECK-NEXT:    [[NOTX:%.*]] = xor i1 [[X:%.*]], true
; CHECK-NEXT:    call void @use1(i1 [[NOTX]])
; CHECK-NEXT:    [[Y_NOT:%.*]] = xor i1 [[Y:%.*]], true
; CHECK-NEXT:    [[NOTAND:%.*]] = select i1 [[X]], i1 true, i1 [[Y_NOT]]
; CHECK-NEXT:    ret i1 [[NOTAND]]
;
  %notx = xor i1 %x, true
  call void @use1(i1 %notx)
  %and = select i1 %notx, i1 %y, i1 false
  %notand = xor i1 %and, true
  ret i1 %notand
}

; negative test

define i1 @not_logicalAnd_not_op0_use2(i1 %x, i1 %y) {
; CHECK-LABEL: @not_logicalAnd_not_op0_use2(
; CHECK-NEXT:    [[NOTX:%.*]] = xor i1 [[X:%.*]], true
; CHECK-NEXT:    [[AND:%.*]] = select i1 [[NOTX]], i1 [[Y:%.*]], i1 false
; CHECK-NEXT:    call void @use1(i1 [[AND]])
; CHECK-NEXT:    [[NOTAND:%.*]] = xor i1 [[AND]], true
; CHECK-NEXT:    ret i1 [[NOTAND]]
;
  %notx = xor i1 %x, true
  %and = select i1 %notx, i1 %y, i1 false
  call void @use1(i1 %and)
  %notand = xor i1 %and, true
  ret i1 %notand
}

define <2 x i1> @not_logicalOr_not_op0(<2 x i1> %x, <2 x i1> %y) {
; CHECK-LABEL: @not_logicalOr_not_op0(
; CHECK-NEXT:    [[Y_NOT:%.*]] = xor <2 x i1> [[Y:%.*]], splat (i1 true)
; CHECK-NEXT:    [[NOTOR:%.*]] = select <2 x i1> [[X:%.*]], <2 x i1> [[Y_NOT]], <2 x i1> zeroinitializer
; CHECK-NEXT:    ret <2 x i1> [[NOTOR]]
;
  %notx = xor <2 x i1> %x, <i1 true, i1 true>
  %or = select <2 x i1> %notx, <2 x i1> <i1 true, i1 true>, <2 x i1> %y
  %notor = xor <2 x i1> %or, <i1 true, i1 true>
  ret <2 x i1> %notor
}

define i1 @not_logicalOr_not_op1(i1 %x, i1 %y) {
; CHECK-LABEL: @not_logicalOr_not_op1(
; CHECK-NEXT:    [[NOT_X:%.*]] = xor i1 [[X:%.*]], true
; CHECK-NEXT:    [[NOTOR:%.*]] = select i1 [[NOT_X]], i1 [[Y:%.*]], i1 false
; CHECK-NEXT:    ret i1 [[NOTOR]]
;
  %noty = xor i1 %y, true
  %or = select i1 %x, i1 true, i1 %noty
  %notor = xor i1 %or, true
  ret i1 %notor
}

define i1 @not_logicalOr_not_op0_use1(i1 %x, i1 %y) {
; CHECK-LABEL: @not_logicalOr_not_op0_use1(
; CHECK-NEXT:    [[NOTX:%.*]] = xor i1 [[X:%.*]], true
; CHECK-NEXT:    call void @use1(i1 [[NOTX]])
; CHECK-NEXT:    [[Y_NOT:%.*]] = xor i1 [[Y:%.*]], true
; CHECK-NEXT:    [[NOTOR:%.*]] = select i1 [[X]], i1 [[Y_NOT]], i1 false
; CHECK-NEXT:    ret i1 [[NOTOR]]
;
  %notx = xor i1 %x, true
  call void @use1(i1 %notx)
  %or = select i1 %notx, i1 true, i1 %y
  %notor = xor i1 %or, true
  ret i1 %notor
}

; negative test

define i1 @not_logicalOr_not_op0_use2(i1 %x, i1 %y) {
; CHECK-LABEL: @not_logicalOr_not_op0_use2(
; CHECK-NEXT:    [[NOTX:%.*]] = xor i1 [[X:%.*]], true
; CHECK-NEXT:    [[OR:%.*]] = select i1 [[NOTX]], i1 true, i1 [[Y:%.*]]
; CHECK-NEXT:    call void @use1(i1 [[OR]])
; CHECK-NEXT:    [[NOTOR:%.*]] = xor i1 [[OR]], true
; CHECK-NEXT:    ret i1 [[NOTOR]]
;
  %notx = xor i1 %x, true
  %or = select i1 %notx, i1 true, i1 %y
  call void @use1(i1 %or)
  %notor = xor i1 %or, true
  ret i1 %notor
}

; canonicalize 'not' ahead of casts of a bool value

define <2 x i64> @bitcast_to_wide_elts_sext_bool(<4 x i1> %b) {
; CHECK-LABEL: @bitcast_to_wide_elts_sext_bool(
; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i1> [[B:%.*]], splat (i1 true)
; CHECK-NEXT:    [[TMP2:%.*]] = sext <4 x i1> [[TMP1]] to <4 x i32>
; CHECK-NEXT:    [[NOT:%.*]] = bitcast <4 x i32> [[TMP2]] to <2 x i64>
; CHECK-NEXT:    ret <2 x i64> [[NOT]]
;
  %sext = sext <4 x i1> %b to <4 x i32>
  %bc = bitcast <4 x i32> %sext to <2 x i64>
  %not = xor <2 x i64> %bc, <i64 -1, i64 -1>
  ret <2 x i64> %not
}

define <8 x i16> @bitcast_to_narrow_elts_sext_bool(<4 x i1> %b) {
; CHECK-LABEL: @bitcast_to_narrow_elts_sext_bool(
; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i1> [[B:%.*]], splat (i1 true)
; CHECK-NEXT:    [[TMP2:%.*]] = sext <4 x i1> [[TMP1]] to <4 x i32>
; CHECK-NEXT:    [[NOT:%.*]] = bitcast <4 x i32> [[TMP2]] to <8 x i16>
; CHECK-NEXT:    ret <8 x i16> [[NOT]]
;
  %sext = sext <4 x i1> %b to <4 x i32>
  %bc = bitcast <4 x i32> %sext to <8 x i16>
  %not = xor <8 x i16> %bc, <i16 -1, i16 -1, i16 -1, i16 -1, i16 -1, i16 -1, i16 -1, i16 -1>
  ret <8 x i16> %not
}

define <2 x i16> @bitcast_to_vec_sext_bool(i1 %b) {
; CHECK-LABEL: @bitcast_to_vec_sext_bool(
; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[B:%.*]], true
; CHECK-NEXT:    [[TMP2:%.*]] = sext i1 [[TMP1]] to i32
; CHECK-NEXT:    [[NOT:%.*]] = bitcast i32 [[TMP2]] to <2 x i16>
; CHECK-NEXT:    ret <2 x i16> [[NOT]]
;
  %sext = sext i1 %b to i32
  %bc = bitcast i32 %sext to <2 x i16>
  %not = xor <2 x i16> %bc, <i16 -1, i16 -1>
  ret <2 x i16> %not
}

define i128 @bitcast_to_scalar_sext_bool(<4 x i1> %b) {
; CHECK-LABEL: @bitcast_to_scalar_sext_bool(
; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i1> [[B:%.*]], splat (i1 true)
; CHECK-NEXT:    [[TMP2:%.*]] = sext <4 x i1> [[TMP1]] to <4 x i32>
; CHECK-NEXT:    [[NOT:%.*]] = bitcast <4 x i32> [[TMP2]] to i128
; CHECK-NEXT:    ret i128 [[NOT]]
;
  %sext = sext <4 x i1> %b to <4 x i32>
  %bc = bitcast <4 x i32> %sext to i128
  %not = xor i128 %bc, -1
  ret i128 %not
}

; negative test

define <2 x i4> @bitcast_to_vec_sext_bool_use1(i1 %b) {
; CHECK-LABEL: @bitcast_to_vec_sext_bool_use1(
; CHECK-NEXT:    [[SEXT:%.*]] = sext i1 [[B:%.*]] to i8
; CHECK-NEXT:    call void @use8(i8 [[SEXT]])
; CHECK-NEXT:    [[BC:%.*]] = bitcast i8 [[SEXT]] to <2 x i4>
; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i4> [[BC]], splat (i4 -1)
; CHECK-NEXT:    ret <2 x i4> [[NOT]]
;
  %sext = sext i1 %b to i8
  call void @use8(i8 %sext)
  %bc = bitcast i8 %sext to <2 x i4>
  %not = xor <2 x i4> %bc, <i4 -1, i4 -1>
  ret <2 x i4> %not
}

; negative test

define i8 @bitcast_to_scalar_sext_bool_use2(<4 x i1> %b) {
; CHECK-LABEL: @bitcast_to_scalar_sext_bool_use2(
; CHECK-NEXT:    [[SEXT:%.*]] = sext <4 x i1> [[B:%.*]] to <4 x i2>
; CHECK-NEXT:    [[BC:%.*]] = bitcast <4 x i2> [[SEXT]] to i8
; CHECK-NEXT:    call void @use8(i8 [[BC]])
; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[BC]], -1
; CHECK-NEXT:    ret i8 [[NOT]]
;
  %sext = sext <4 x i1> %b to <4 x i2>
  %bc = bitcast <4 x i2> %sext to i8
  call void @use8(i8 %bc)
  %not = xor i8 %bc, -1
  ret i8 %not
}

; PR74302
define i1 @invert_both_cmp_operands_add(i32 %a, i32 %b) {
; CHECK-LABEL: @invert_both_cmp_operands_add(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[TMP0]], -1
; CHECK-NEXT:    ret i1 [[CMP]]
;
entry:
  %not.a = xor i32 %a, -1
  %add = add i32 %b, %not.a
  %cmp = icmp sgt i32 %add, 0
  ret i1 %cmp
}

define i1 @invert_both_cmp_operands_sub(i32 %a, i32 %b) {
; CHECK-LABEL: @invert_both_cmp_operands_sub(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[TMP0]], -43
; CHECK-NEXT:    ret i1 [[CMP]]
;
entry:
  %not.a = xor i32 %a, -1
  %add = sub i32 %not.a, %b
  %cmp = icmp ult i32 %add, 42
  ret i1 %cmp
}

define i1 @invert_both_cmp_operands_complex(i1 %x, i32 %a, i32 %b, i32 %c) {
; CHECK-LABEL: @invert_both_cmp_operands_complex(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 [[A:%.*]], [[C:%.*]]
; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[X:%.*]], i32 [[TMP0]], i32 [[B:%.*]]
; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[TMP1]], [[C]]
; CHECK-NEXT:    ret i1 [[CMP]]
;
entry:
  %not.a = xor i32 %a, -1
  %not.b = xor i32 %b, -1
  %not.c = xor i32 %c, -1
  %add = add i32 %c, %not.a
  %select = select i1 %x, i32 %add, i32 %not.b
  %cmp = icmp sle i32 %select, %not.c
  ret i1 %cmp
}

define i32 @test_sext(i32 %a, i32 %b){
; CHECK-LABEL: @test_sext(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i32 [[A:%.*]], 0
; CHECK-NEXT:    [[TMP2:%.*]] = sext i1 [[TMP1]] to i32
; CHECK-NEXT:    [[NOT:%.*]] = sub i32 [[TMP2]], [[B:%.*]]
; CHECK-NEXT:    ret i32 [[NOT]]
;
  %cmp = icmp eq i32 %a, 0
  %sext = sext i1 %cmp to i32
  %add = add i32 %b, %sext
  %not = xor i32 %add, -1
  ret i32 %not
}

define <2 x i32> @test_sext_vec(<2 x i32> %a, <2 x i32> %b){
; CHECK-LABEL: @test_sext_vec(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne <2 x i32> [[A:%.*]], zeroinitializer
; CHECK-NEXT:    [[TMP2:%.*]] = sext <2 x i1> [[TMP1]] to <2 x i32>
; CHECK-NEXT:    [[NOT:%.*]] = sub <2 x i32> [[TMP2]], [[B:%.*]]
; CHECK-NEXT:    ret <2 x i32> [[NOT]]
;
  %cmp = icmp eq <2 x i32> %a, zeroinitializer
  %sext = sext <2 x i1> %cmp to <2 x i32>
  %add = add <2 x i32> %b, %sext
  %not = xor <2 x i32> %add, <i32 -1, i32 -1>
  ret <2 x i32> %not
}

define i64 @test_zext_nneg(i32 %c1, i64 %c2, i64 %c3){
; CHECK-LABEL: @test_zext_nneg(
; CHECK-NEXT:    [[DOTNEG:%.*]] = add i64 [[C2:%.*]], -4
; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[C1:%.*]] to i64
; CHECK-NEXT:    [[TMP2:%.*]] = sub i64 [[TMP1]], [[C3:%.*]]
; CHECK-NEXT:    [[SUB:%.*]] = add i64 [[DOTNEG]], [[TMP2]]
; CHECK-NEXT:    ret i64 [[SUB]]
;
  %not = xor i32 %c1, -1
  %conv = zext nneg i32 %not to i64
  %add1 = add i64 %c2, -5
  %add2 = add i64 %conv, %c3
  %sub = sub i64 %add1, %add2
  ret i64 %sub
}

define i8 @test_trunc(i8 %a){
; CHECK-LABEL: @test_trunc(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i8 [[A:%.*]], 0
; CHECK-NEXT:    [[NOT:%.*]] = sext i1 [[TMP1]] to i8
; CHECK-NEXT:    ret i8 [[NOT]]
;
  %zext = zext i8 %a to i32
  %sub = add nsw i32 %zext, -1
  %shr = ashr i32 %sub, 31
  %conv = trunc i32 %shr to i8
  %not = xor i8 %conv, -1
  ret i8 %not
}

define <2 x i8> @test_trunc_vec(<2 x i8> %a){
; CHECK-LABEL: @test_trunc_vec(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne <2 x i8> [[A:%.*]], zeroinitializer
; CHECK-NEXT:    [[NOT:%.*]] = sext <2 x i1> [[TMP1]] to <2 x i8>
; CHECK-NEXT:    ret <2 x i8> [[NOT]]
;
  %zext = zext <2 x i8> %a to <2 x i32>
  %sub = add nsw <2 x i32> %zext, <i32 -1, i32 -1>
  %shr = ashr <2 x i32> %sub, <i32 31, i32 31>
  %conv = trunc <2 x i32> %shr to <2 x i8>
  %not = xor <2 x i8> %conv, <i8 -1, i8 -1>
  ret <2 x i8> %not
}

; Negative tests

define i32 @test_zext(i32 %a, i32 %b){
; CHECK-LABEL: @test_zext(
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[A:%.*]], 0
; CHECK-NEXT:    [[SEXT:%.*]] = zext i1 [[CMP]] to i32
; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[B:%.*]], [[SEXT]]
; CHECK-NEXT:    [[NOT:%.*]] = xor i32 [[ADD]], -1
; CHECK-NEXT:    ret i32 [[NOT]]
;
  %cmp = icmp eq i32 %a, 0
  %sext = zext i1 %cmp to i32
  %add = add i32 %b, %sext
  %not = xor i32 %add, -1
  ret i32 %not
}

define void @test_invert_demorgan_or(i32 %a, i32 %b, i1 %cond) {
; CHECK-LABEL: @test_invert_demorgan_or(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[A:%.*]], 0
; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[B:%.*]], 0
; CHECK-NEXT:    [[OR_NOT1:%.*]] = and i1 [[CMP1]], [[CMP2]]
; CHECK-NEXT:    [[MERGE_NOT:%.*]] = and i1 [[OR_NOT1]], [[COND:%.*]]
; CHECK-NEXT:    br i1 [[MERGE_NOT]], label [[IF_ELSE:%.*]], label [[IF_THEN:%.*]]
; CHECK:       if.then:
; CHECK-NEXT:    call void @f1()
; CHECK-NEXT:    unreachable
; CHECK:       if.else:
; CHECK-NEXT:    call void @f2()
; CHECK-NEXT:    unreachable
;
entry:
  %cmp1 = icmp eq i32 %a, 0
  %cmp2 = icmp ne i32 %b, 0
  %or = or i1 %cmp1, %cmp2
  %not = xor i1 %cond, true
  %merge = or i1 %not, %or
  br i1 %merge, label %if.then, label %if.else
if.then:
  call void @f1()
  unreachable
if.else:
  call void @f2()
  unreachable
}

define i1 @test_invert_demorgan_or2(i64 %a, i64 %b, i64 %c) {
; CHECK-LABEL: @test_invert_demorgan_or2(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i64 [[A:%.*]], 24
; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[B:%.*]], 60
; CHECK-NEXT:    [[OR1_NOT1:%.*]] = and i1 [[CMP1]], [[CMP2]]
; CHECK-NEXT:    [[CMP3:%.*]] = icmp ult i64 [[C:%.*]], 60
; CHECK-NEXT:    [[OR2_NOT:%.*]] = and i1 [[OR1_NOT1]], [[CMP3]]
; CHECK-NEXT:    ret i1 [[OR2_NOT]]
;
  %cmp1 = icmp ugt i64 %a, 23
  %cmp2 = icmp ugt i64 %b, 59
  %or1 = or i1 %cmp1, %cmp2
  %cmp3 = icmp ugt i64 %c, 59
  %or2 = or i1 %or1, %cmp3
  %not = xor i1 %or2, true
  ret i1 %not
}

define i1 @test_invert_demorgan_or3(i32 %a, i32 %b) {
; CHECK-LABEL: @test_invert_demorgan_or3(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[A:%.*]], 178206
; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[B:%.*]], -196608
; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[TMP1]], -1506
; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[B]], -917760
; CHECK-NEXT:    [[CMP3:%.*]] = icmp ult i32 [[TMP2]], -716213
; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[B]], -1114112
; CHECK-NEXT:    [[CMP4:%.*]] = icmp ult i32 [[TMP3]], -196112
; CHECK-NEXT:    [[OR1_NOT2:%.*]] = and i1 [[CMP1]], [[CMP2]]
; CHECK-NEXT:    [[OR2_NOT1:%.*]] = and i1 [[OR1_NOT2]], [[CMP3]]
; CHECK-NEXT:    [[OR3_NOT:%.*]] = and i1 [[OR2_NOT1]], [[CMP4]]
; CHECK-NEXT:    ret i1 [[OR3_NOT]]
;
  %cmp1 = icmp eq i32 %a, 178206
  %v1 = add i32 %b, -195102
  %cmp2 = icmp ult i32 %v1, 1506
  %v2 = add i32 %b, -201547
  %cmp3 = icmp ult i32 %v2, 716213
  %v3 = add i32 %b, -918000
  %cmp4 = icmp ult i32 %v3, 196112
  %or1 = or i1 %cmp1, %cmp2
  %or2 = or i1 %or1, %cmp3
  %or3 = or i1 %or2, %cmp4
  %not = xor i1 %or3, true
  ret i1 %not
}

define i1 @test_invert_demorgan_logical_or(i64 %x, i64 %y) {
; CHECK-LABEL: @test_invert_demorgan_logical_or(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i64 [[X:%.*]], 27
; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[Y:%.*]], 0
; CHECK-NEXT:    [[SEL_NOT1:%.*]] = select i1 [[CMP1]], i1 [[CMP2]], i1 false
; CHECK-NEXT:    [[CMP3:%.*]] = icmp ne i64 [[X]], 0
; CHECK-NEXT:    [[OR_NOT:%.*]] = and i1 [[CMP3]], [[SEL_NOT1]]
; CHECK-NEXT:    ret i1 [[OR_NOT]]
;
  %cmp1 = icmp eq i64 %x, 27
  %cmp2 = icmp eq i64 %y, 0
  %sel = select i1 %cmp1, i1 true, i1 %cmp2
  %cmp3 = icmp eq i64 %x, 0
  %or = or i1 %cmp3, %sel
  %not = xor i1 %or, true
  ret i1 %not
}

define i1 @test_invert_demorgan_and(i32 %a, i32 %b, i1 %cond) {
; CHECK-LABEL: @test_invert_demorgan_and(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[A:%.*]], 0
; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[B:%.*]], 0
; CHECK-NEXT:    [[AND_NOT1:%.*]] = or i1 [[CMP1]], [[CMP2]]
; CHECK-NEXT:    [[MERGE_NOT:%.*]] = or i1 [[AND_NOT1]], [[COND:%.*]]
; CHECK-NEXT:    br i1 [[MERGE_NOT]], label [[IF_ELSE:%.*]], label [[IF_THEN:%.*]]
; CHECK:       if.then:
; CHECK-NEXT:    call void @f1()
; CHECK-NEXT:    unreachable
; CHECK:       if.else:
; CHECK-NEXT:    call void @f2()
; CHECK-NEXT:    unreachable
;
entry:
  %cmp1 = icmp eq i32 %a, 0
  %cmp2 = icmp ne i32 %b, 0
  %and = and i1 %cmp1, %cmp2
  %not = xor i1 %cond, true
  %merge = and i1 %not, %and
  br i1 %merge, label %if.then, label %if.else
if.then:
  call void @f1()
  unreachable
if.else:
  call void @f2()
  unreachable
}

define i64 @test_invert_demorgan_and2(i64 %x) {
; CHECK-LABEL: @test_invert_demorgan_and2(
; CHECK-NEXT:    [[TMP1:%.*]] = sub i64 0, [[X:%.*]]
; CHECK-NEXT:    [[SUB:%.*]] = or i64 [[TMP1]], -9223372036854775808
; CHECK-NEXT:    ret i64 [[SUB]]
;
  %add = add i64 %x, 9223372036854775807
  %and = and i64 %add, 9223372036854775807
  %sub = xor i64 %and, -1
  ret i64 %sub
}

define i1 @test_invert_demorgan_and3(i32 %a, i32 %b) {
; CHECK-LABEL: @test_invert_demorgan_and3(
; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 4095
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP2]], 4095
; CHECK-NEXT:    ret i1 [[CMP]]
;
  %not = xor i32 %a, -1
  %add = add i32 %b, %not
  %and = and i32 %add, 4095
  %cmp = icmp eq i32 %and, 0
  ret i1 %cmp
}

define i1 @test_invert_demorgan_logical_and(i64 %x, i64 %y) {
; CHECK-LABEL: @test_invert_demorgan_logical_and(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i64 [[X:%.*]], 27
; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i64 [[Y:%.*]], 0
; CHECK-NEXT:    [[SEL_NOT1:%.*]] = select i1 [[CMP1]], i1 true, i1 [[CMP2]]
; CHECK-NEXT:    [[CMP3:%.*]] = icmp ne i64 [[X]], 0
; CHECK-NEXT:    [[OR_NOT:%.*]] = and i1 [[CMP3]], [[SEL_NOT1]]
; CHECK-NEXT:    ret i1 [[OR_NOT]]
;
  %cmp1 = icmp eq i64 %x, 27
  %cmp2 = icmp eq i64 %y, 0
  %sel = select i1 %cmp1, i1 %cmp2, i1 false
  %cmp3 = icmp eq i64 %x, 0
  %or = or i1 %cmp3, %sel
  %not = xor i1 %or, true
  ret i1 %not
}

define i1 @test_invert_demorgan_and_multiuse(i32 %a, i32 %b, i1 %cond) {
; CHECK-LABEL: @test_invert_demorgan_and_multiuse(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], 0
; CHECK-NEXT:    call void @use1(i1 [[CMP1]])
; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[B:%.*]], 0
; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[COND:%.*]], true
; CHECK-NEXT:    [[TMP0:%.*]] = and i1 [[CMP2]], [[NOT]]
; CHECK-NEXT:    [[MERGE:%.*]] = and i1 [[TMP0]], [[CMP1]]
; CHECK-NEXT:    br i1 [[MERGE]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
; CHECK:       if.then:
; CHECK-NEXT:    call void @f1()
; CHECK-NEXT:    unreachable
; CHECK:       if.else:
; CHECK-NEXT:    call void @f2()
; CHECK-NEXT:    unreachable
;
entry:
  %cmp1 = icmp eq i32 %a, 0
  call void @use1(i1 %cmp1)
  %cmp2 = icmp ne i32 %b, 0
  %and = and i1 %cmp1, %cmp2
  %not = xor i1 %cond, true
  %merge = and i1 %not, %and
  br i1 %merge, label %if.then, label %if.else
if.then:
  call void @f1()
  unreachable
if.else:
  call void @f2()
  unreachable
}