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

define i1 @test_second_and_condition_implied_by_first(i8 %x) {
; CHECK-LABEL: @test_second_and_condition_implied_by_first(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
; CHECK-NEXT:    br i1 [[C_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    ret i1 false
; CHECK:       else:
; CHECK-NEXT:    ret i1 true
;
entry:
  %c.1 = icmp ugt i8 %x, 10
  %t.1 = icmp ugt i8 %x, 5
  %and = and i1 %c.1, %t.1
  br i1 %and, label %then, label %else

then:
  ret i1 0

else:
  ret i1 1
}

define i1 @test_first_and_condition_implied_by_second_ops(i8 %x) {
; CHECK-LABEL: @test_first_and_condition_implied_by_second_ops(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
; CHECK-NEXT:    br i1 [[C_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    ret i1 false
; CHECK:       else:
; CHECK-NEXT:    ret i1 true
;
entry:
  %c.1 = icmp ugt i8 %x, 10
  %t.1 = icmp ugt i8 %x, 5
  %and = and i1 %t.1, %c.1
  br i1 %and, label %then, label %else

then:
  ret i1 0

else:
  ret i1 1
}

define i1 @test_second_and_condition_implied_by_first_select_form(i8 %x) {
; CHECK-LABEL: @test_second_and_condition_implied_by_first_select_form(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
; CHECK-NEXT:    br i1 [[C_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    ret i1 false
; CHECK:       else:
; CHECK-NEXT:    ret i1 true
;
entry:
  %c.1 = icmp ugt i8 %x, 10
  %t.1 = icmp ugt i8 %x, 5
  %and = select i1 %c.1, i1 %t.1, i1 false
  br i1 %and, label %then, label %else

then:
  ret i1 0

else:
  ret i1 1
}

define i1 @test_first_and_condition_implied_by_second_select_form(i8 %x) {
; CHECK-LABEL: @test_first_and_condition_implied_by_second_select_form(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
; CHECK-NEXT:    [[AND:%.*]] = select i1 [[T_1]], i1 [[C_1]], i1 false
; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    ret i1 false
; CHECK:       else:
; CHECK-NEXT:    ret i1 true
;
entry:
  %c.1 = icmp ugt i8 %x, 10
  %t.1 = icmp ugt i8 %x, 5
  %and = select i1 %t.1, i1 %c.1, i1 false
  br i1 %and, label %then, label %else

then:
  ret i1 0

else:
  ret i1 1
}

define i1 @test_same_cond_for_and(i8 %x) {
; CHECK-LABEL: @test_same_cond_for_and(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
; CHECK-NEXT:    br i1 [[C_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    ret i1 false
; CHECK:       else:
; CHECK-NEXT:    ret i1 true
;
entry:
  %c.1 = icmp ugt i8 %x, 10
  %and = and i1 %c.1, %c.1
  br i1 %and, label %then, label %else

then:
  ret i1 0

else:
  ret i1 1
}

define i1 @test_same_cond_for_and_select_form(i8 %x) {
; CHECK-LABEL: @test_same_cond_for_and_select_form(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
; CHECK-NEXT:    [[AND:%.*]] = select i1 [[C_1]], i1 [[C_1]], i1 false
; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    ret i1 false
; CHECK:       else:
; CHECK-NEXT:    ret i1 true
;
entry:
  %c.1 = icmp ugt i8 %x, 10
  %and = select i1 %c.1, i1 %c.1, i1 false
  br i1 %and, label %then, label %else

then:
  ret i1 0

else:
  ret i1 1
}

define i1 @test_second_and_condition_not_implied_by_first(i8 %x) {
; CHECK-LABEL: @test_second_and_condition_not_implied_by_first(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt i8 [[X]], 5
; CHECK-NEXT:    br i1 [[C_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    ret i1 false
; CHECK:       else:
; CHECK-NEXT:    ret i1 true
;
entry:
  %c.1 = icmp ugt i8 %x, 10
  %c.2 = icmp ugt i8 %x, 5
  %and = and i1 %c.2, %c.1
  br i1 %and, label %then, label %else

then:
  ret i1 0

else:
  ret i1 1
}

define i1 @test_remove_variables(i1 %c, ptr %A, i64 %B, ptr %C) {
; CHECK-LABEL: @test_remove_variables(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN_1:%.*]], label [[EXIT:%.*]]
; CHECK:       then.1:
; CHECK-NEXT:    [[TMP0:%.*]] = load ptr, ptr [[C:%.*]], align 8
; CHECK-NEXT:    [[C_1:%.*]] = icmp ult ptr [[TMP0]], [[A:%.*]]
; CHECK-NEXT:    br i1 [[C_1]], label [[THEN_2:%.*]], label [[ELSE_2:%.*]]
; CHECK:       then.2:
; CHECK-NEXT:    [[C_3:%.*]] = icmp sgt i64 [[B:%.*]], 0
; CHECK-NEXT:    [[AND:%.*]] = and i1 true, [[C_3]]
; CHECK-NEXT:    ret i1 [[AND]]
; CHECK:       else.2:
; CHECK-NEXT:    ret i1 false
; CHECK:       exit:
; CHECK-NEXT:    ret i1 true
;
entry:
  br i1 %c, label %then.1, label %exit

then.1:
  %0 = load ptr, ptr %C, align 8
  %c.1 = icmp ult ptr %0, %A
  br i1 %c.1, label %then.2, label %else.2

then.2:
  %c.2 = icmp ne ptr %A, null
  %c.3 = icmp sgt i64 %B, 0
  %and = and i1 %c.2, %c.3
  ret i1 %and

else.2:
  ret i1 0

exit:
  %t = icmp eq ptr null, null
  ret i1 %t
}

define i1 @test_and_op_0_simplified(i32 %v) {
; CHECK-LABEL: @test_and_op_0_simplified(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp sgt i32 [[V:%.*]], 0
; CHECK-NEXT:    [[AND:%.*]] = and i1 false, [[C_1]]
; CHECK-NEXT:    ret i1 [[AND]]
;
entry:
  %c.1 = icmp sgt i32 %v, 0
  %t.1 = icmp sgt i32 0, 0
  %and = and i1 %t.1, %c.1
  ret i1 %and
}

define i1 @test_and_op_1_simplified(i32 %v) {
; CHECK-LABEL: @test_and_op_1_simplified(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp sgt i32 [[V:%.*]], 0
; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], false
; CHECK-NEXT:    ret i1 [[AND]]
;
entry:
  %c.1 = icmp sgt i32 %v, 0
  %t.1 = icmp sgt i32 0, 0
  %and = and i1 %c.1, %t.1
  ret i1 %and
}

define i1 @and_select_not_used_for_branch(i32 %x, i32 %y,i32 %z) {
; CHECK-LABEL: @and_select_not_used_for_branch(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ne i32 [[X:%.*]], 0
; CHECK-NEXT:    [[C_2:%.*]] = icmp ne i32 [[Y:%.*]], 0
; CHECK-NEXT:    [[C_3:%.*]] = icmp eq i32 [[X]], 16
; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_2]], [[C_3]]
; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[EXIT:%.*]]
; CHECK:       then:
; CHECK-NEXT:    [[C_4:%.*]] = icmp eq i32 [[Z:%.*]], 0
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C_4]], i1 true, i1 false
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = phi i1 [ [[C_1]], [[ENTRY:%.*]] ], [ [[SEL]], [[THEN]] ]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %c.1 = icmp ne i32 %x, 0
  %c.2 = icmp ne i32 %y, 0
  %c.3 = icmp eq i32 %x, 16
  %and = and i1 %c.2, %c.3
  br i1 %and, label %then, label %exit

then:
  %c.4 = icmp eq i32 %z, 0
  %sel = select i1 %c.4, i1 %c.1, i1 false
  br label %exit

exit:
  %res = phi i1 [ %c.1, %entry ], [ %sel, %then ]
  ret i1 %res
}

define i1 @and_select_scope_limited(i32 %x, i32 %y, i32 %z) {
; CHECK-LABEL: @and_select_scope_limited(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ne i32 [[X:%.*]], 0
; CHECK-NEXT:    [[C_2:%.*]] = icmp ne i32 [[Y:%.*]], 0
; CHECK-NEXT:    [[C_3:%.*]] = icmp eq i32 [[X]], 16
; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_2]], [[C_3]]
; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[EXIT:%.*]]
; CHECK:       then:
; CHECK-NEXT:    [[C_4:%.*]] = icmp eq i32 [[Z:%.*]], 0
; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C_4]], i1 true, i1 false
; CHECK-NEXT:    br i1 [[SEL]], label [[T_1:%.*]], label [[EXIT]]
; CHECK:       t.1:
; CHECK-NEXT:    ret i1 true
; CHECK:       exit:
; CHECK-NEXT:    [[RES:%.*]] = phi i1 [ [[C_1]], [[ENTRY:%.*]] ], [ [[SEL]], [[THEN]] ]
; CHECK-NEXT:    ret i1 [[RES]]
;
entry:
  %c.1 = icmp ne i32 %x, 0
  %c.2 = icmp ne i32 %y, 0
  %c.3 = icmp eq i32 %x, 16
  %and = and i1 %c.2, %c.3
  br i1 %and, label %then, label %exit

then:
  %c.4 = icmp eq i32 %z, 0
  %sel = select i1 %c.4, i1 %c.1, i1 false
  br i1 %sel, label %t.1, label %exit

t.1:
  ret i1 %c.1

exit:
  %res = phi i1 [ %c.1, %entry ], [ %sel, %then ]
  ret i1 %res
}

declare void @use(ptr)

define void @test_monotonic_ptr_iv_inc_1_eq_to_uge(ptr %start, i16 %len) {
; CHECK-LABEL: @test_monotonic_ptr_iv_inc_1_eq_to_uge(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[UPPER:%.*]] = getelementptr inbounds i32, ptr [[START:%.*]], i16 [[LEN:%.*]]
; CHECK-NEXT:    br label [[LOOP_PH:%.*]]
; CHECK:       loop.ph:
; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
; CHECK:       loop.header:
; CHECK-NEXT:    [[PTR_IV:%.*]] = phi ptr [ [[START]], [[LOOP_PH]] ], [ [[PTR_IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
; CHECK-NEXT:    [[LEN_NEG:%.*]] = icmp sgt i16 [[LEN]], 0
; CHECK-NEXT:    [[C:%.*]] = icmp ne ptr [[PTR_IV]], [[UPPER]]
; CHECK-NEXT:    [[AND_0:%.*]] = and i1 [[LEN_NEG]], [[C]]
; CHECK-NEXT:    br i1 [[AND_0]], label [[FOR_BODY:%.*]], label [[EXIT:%.*]]
; CHECK:       for.body:
; CHECK-NEXT:    [[T_1:%.*]] = icmp uge ptr [[PTR_IV]], [[START]]
; CHECK-NEXT:    [[T_2:%.*]] = icmp ult ptr [[PTR_IV]], [[UPPER]]
; CHECK-NEXT:    [[AND:%.*]] = and i1 [[T_1]], [[T_2]]
; CHECK-NEXT:    br i1 [[AND]], label [[LOOP_LATCH]], label [[EXIT]]
; CHECK:       loop.latch:
; CHECK-NEXT:    call void @use(ptr [[PTR_IV]])
; CHECK-NEXT:    [[PTR_IV_NEXT]] = getelementptr inbounds i32, ptr [[PTR_IV]], i16 1
; CHECK-NEXT:    br label [[LOOP_HEADER]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;
entry:
  %upper = getelementptr inbounds i32, ptr %start, i16 %len
  br label %loop.ph

loop.ph:
  br label %loop.header

loop.header:
  %ptr.iv = phi ptr [ %start, %loop.ph ], [ %ptr.iv.next, %loop.latch ]
  %len.neg = icmp sgt i16 %len, 0
  %c = icmp ne ptr %ptr.iv, %upper
  %and.0 = and i1 %len.neg, %c
  br i1 %and.0, label %for.body, label %exit

for.body:
  %t.1 = icmp uge ptr %ptr.iv, %start
  %t.2 = icmp ult ptr %ptr.iv, %upper
  %and = and i1 %t.1, %t.2
  br i1 %and, label %loop.latch, label %exit

loop.latch:
  call void @use(ptr %ptr.iv)
  %ptr.iv.next = getelementptr inbounds i32, ptr %ptr.iv, i16 1
  br label %loop.header

exit:
  ret void
}

define i1 @test_and_used_in_false_branch(i8 %x) {
; CHECK-LABEL: @test_and_used_in_false_branch(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
; CHECK-NEXT:    br i1 [[C_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    ret i1 true
; CHECK:       else:
; CHECK-NEXT:    ret i1 [[T_1]]
;

entry:
  %c.1 = icmp ugt i8 %x, 10
  %t.1 = icmp ugt i8 %x, 5
  %and = and i1 %c.1, %t.1
  br i1 %and, label %then, label %else

then:
  ret i1 %t.1

else:
  ret i1 %t.1
}

define i1 @test_or_used_in_false_branch(i8 %x) {
; CHECK-LABEL: @test_or_used_in_false_branch(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i8 [[X:%.*]], 10
; CHECK-NEXT:    [[T_1:%.*]] = icmp ule i8 [[X]], 5
; CHECK-NEXT:    br i1 [[C_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    ret i1 [[T_1]]
; CHECK:       else:
; CHECK-NEXT:    ret i1 false
;

entry:
  %c.1 = icmp ule i8 %x, 10
  %t.1 = icmp ule i8 %x, 5
  %and = or i1 %c.1, %t.1
  br i1 %and, label %then, label %else

then:
  ret i1 %t.1

else:
  ret i1 %t.1
}

define i1 @test_or_used_in_false_branch2(i8 %x) {
; CHECK-LABEL: @test_or_used_in_false_branch2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
; CHECK-NEXT:    br i1 [[T_1]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    ret i1 [[T_1]]
; CHECK:       else:
; CHECK-NEXT:    ret i1 false
;

entry:
  %c.1 = icmp ugt i8 %x, 10
  %t.1 = icmp ugt i8 %x, 5
  %and = or i1 %c.1, %t.1
  br i1 %and, label %then, label %else

then:
  ret i1 %t.1

else:
  ret i1 %t.1
}

define i1 @and_select_first_implies_second_may_be_poison(ptr noundef %A, ptr noundef %B) {
; CHECK-LABEL: @and_select_first_implies_second_may_be_poison(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ne ptr [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds ptr, ptr [[B]], i64 -1
; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt ptr [[GEP]], [[A]]
; CHECK-NEXT:    ret i1 [[C_2]]
;
entry:
  %c.1 = icmp ne ptr %A, %B
  %gep = getelementptr inbounds ptr, ptr %B, i64 -1
  %c.2 = icmp ugt ptr %gep, %A
  %and = select i1 %c.2, i1 %c.1, i1 false
  ret i1 %and
}

define i1 @and_select_second_implies_first_may_be_poison(ptr noundef %A, ptr noundef %B) {
; CHECK-LABEL: @and_select_second_implies_first_may_be_poison(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ne ptr [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds ptr, ptr [[B]], i64 -1
; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt ptr [[GEP]], [[A]]
; CHECK-NEXT:    [[AND:%.*]] = select i1 [[C_1]], i1 [[C_2]], i1 false
; CHECK-NEXT:    ret i1 [[AND]]
;
entry:
  %c.1 = icmp ne ptr %A, %B
  %gep = getelementptr inbounds ptr, ptr %B, i64 -1
  %c.2 = icmp ugt ptr %gep, %A
  %and = select i1 %c.1, i1 %c.2, i1 false
  ret i1 %and
}

define i1 @and_select_second_implies_first_guaranteed_not_poison(ptr noundef %A, ptr noundef %B) {
; CHECK-LABEL: @and_select_second_implies_first_guaranteed_not_poison(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[C_1:%.*]] = icmp ne ptr [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds ptr, ptr [[B]], i64 -1
; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt ptr [[GEP]], [[A]]
; CHECK-NEXT:    call void @no_noundef(i1 [[C_2]])
; CHECK-NEXT:    [[AND:%.*]] = select i1 [[C_1]], i1 [[C_2]], i1 false
; CHECK-NEXT:    ret i1 [[AND]]
;
entry:
  %c.1 = icmp ne ptr %A, %B
  %gep = getelementptr inbounds ptr, ptr %B, i64 -1
  %c.2 = icmp ugt ptr %gep, %A
  call void @no_noundef(i1 %c.2)
  %and = select i1 %c.1, i1 %c.2, i1 false
  ret i1 %and
}

define void @and_tree_second_implies_first(i32 noundef %v0, i32 noundef %v1, i32 noundef %v2) {
; CHECK-LABEL: @and_tree_second_implies_first(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP0:%.*]] = icmp sge i32 [[V0:%.*]], [[V1:%.*]]
; CHECK-NEXT:    [[CMP1:%.*]] = icmp sge i32 [[V1]], [[V2:%.*]]
; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[CMP0]], [[CMP1]]
; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[V0]], [[V2]]
; CHECK-NEXT:    br i1 false, label [[IF_THEN:%.*]], label [[RETURN:%.*]]
; CHECK:       if.then:
; CHECK-NEXT:    call void @side_effect()
; CHECK-NEXT:    br label [[RETURN]]
; CHECK:       return:
; CHECK-NEXT:    ret void
;
entry:
  %cmp0 = icmp sge i32 %v0, %v1
  %cmp1 = icmp sge i32 %v1, %v2
  %and1 = and i1 %cmp0, %cmp1
  %cmp2 = icmp slt i32 %v0, %v2
  %and2 = and i1 %cmp2, %and1
  br i1 %and2, label %if.then, label %return

if.then:
  call void @side_effect()
  br label %return

return:
  ret void
}

define void @and_tree_second_implies_first_perm1(i32 noundef %v0, i32 noundef %v1, i32 noundef %v2) {
; CHECK-LABEL: @and_tree_second_implies_first_perm1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP0:%.*]] = icmp sge i32 [[V0:%.*]], [[V1:%.*]]
; CHECK-NEXT:    [[CMP1:%.*]] = icmp sge i32 [[V1]], [[V2:%.*]]
; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[V0]], [[V2]]
; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[CMP2]], [[CMP1]]
; CHECK-NEXT:    br i1 false, label [[IF_THEN:%.*]], label [[RETURN:%.*]]
; CHECK:       if.then:
; CHECK-NEXT:    call void @side_effect()
; CHECK-NEXT:    br label [[RETURN]]
; CHECK:       return:
; CHECK-NEXT:    ret void
;
entry:
  %cmp0 = icmp sge i32 %v0, %v1
  %cmp1 = icmp sge i32 %v1, %v2
  %cmp2 = icmp slt i32 %v0, %v2
  %and1 = and i1 %cmp2, %cmp1
  %and2 = and i1 %cmp0, %and1
  br i1 %and2, label %if.then, label %return

if.then:
  call void @side_effect()
  br label %return

return:
  ret void
}


define void @and_tree_second_implies_first_perm2(i32 noundef %v0, i32 noundef %v1, i32 noundef %v2) {
; CHECK-LABEL: @and_tree_second_implies_first_perm2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP0:%.*]] = icmp sge i32 [[V0:%.*]], [[V1:%.*]]
; CHECK-NEXT:    [[CMP1:%.*]] = icmp sge i32 [[V1]], [[V2:%.*]]
; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[V0]], [[V2]]
; CHECK-NEXT:    [[AND1:%.*]] = and i1 [[CMP0]], [[CMP2]]
; CHECK-NEXT:    br i1 false, label [[IF_THEN:%.*]], label [[RETURN:%.*]]
; CHECK:       if.then:
; CHECK-NEXT:    call void @side_effect()
; CHECK-NEXT:    br label [[RETURN]]
; CHECK:       return:
; CHECK-NEXT:    ret void
;
entry:
  %cmp0 = icmp sge i32 %v0, %v1
  %cmp1 = icmp sge i32 %v1, %v2
  %cmp2 = icmp slt i32 %v0, %v2
  %and1 = and i1 %cmp0, %cmp2
  %and2 = and i1 %cmp1, %and1
  br i1 %and2, label %if.then, label %return

if.then:
  call void @side_effect()
  br label %return

return:
  ret void
}

define void @logical_and_tree_second_implies_first(i32 %v0, i32 %v1, i32 %v2) {
; CHECK-LABEL: @logical_and_tree_second_implies_first(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP0:%.*]] = icmp sge i32 [[V0:%.*]], [[V1:%.*]]
; CHECK-NEXT:    [[CMP1:%.*]] = icmp sge i32 [[V1]], [[V2:%.*]]
; CHECK-NEXT:    [[AND1:%.*]] = select i1 [[CMP0]], i1 [[CMP1]], i1 false
; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[V0]], [[V2]]
; CHECK-NEXT:    [[AND2:%.*]] = select i1 [[CMP2]], i1 [[AND1]], i1 false
; CHECK-NEXT:    br i1 [[AND2]], label [[IF_THEN:%.*]], label [[RETURN:%.*]]
; CHECK:       if.then:
; CHECK-NEXT:    call void @side_effect()
; CHECK-NEXT:    br label [[RETURN]]
; CHECK:       return:
; CHECK-NEXT:    ret void
;
entry:
  %cmp0 = icmp sge i32 %v0, %v1
  %cmp1 = icmp sge i32 %v1, %v2
  %and1 = select i1 %cmp0, i1 %cmp1, i1 false
  %cmp2 = icmp slt i32 %v0, %v2
  %and2 = select i1 %cmp2, i1 %and1, i1 false
  br i1 %and2, label %if.then, label %return

if.then:
  call void @side_effect()
  br label %return

return:
  ret void
}

define void @or_tree_second_implies_first(i32 noundef %v0, i32 noundef %v1, i32 noundef %v2) {
; CHECK-LABEL: @or_tree_second_implies_first(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP0:%.*]] = icmp sge i32 [[V0:%.*]], [[V1:%.*]]
; CHECK-NEXT:    [[CMP1:%.*]] = icmp sge i32 [[V1]], [[V2:%.*]]
; CHECK-NEXT:    [[AND1:%.*]] = or i1 [[CMP0]], [[CMP1]]
; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[V0]], [[V2]]
; CHECK-NEXT:    br i1 true, label [[IF_THEN:%.*]], label [[RETURN:%.*]]
; CHECK:       if.then:
; CHECK-NEXT:    call void @side_effect()
; CHECK-NEXT:    br label [[RETURN]]
; CHECK:       return:
; CHECK-NEXT:    ret void
;
entry:
  %cmp0 = icmp sge i32 %v0, %v1
  %cmp1 = icmp sge i32 %v1, %v2
  %and1 = or i1 %cmp0, %cmp1
  %cmp2 = icmp slt i32 %v0, %v2
  %and2 = or i1 %cmp2, %and1
  br i1 %and2, label %if.then, label %return

if.then:
  call void @side_effect()
  br label %return

return:
  ret void
}

define void @or_tree_second_implies_first_with_unknown_cond(i64 %x, i1 %cond) {
; CHECK-LABEL: @or_tree_second_implies_first_with_unknown_cond(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt i64 [[X:%.*]], 1
; CHECK-NEXT:    [[OR1:%.*]] = select i1 [[CMP1]], i1 [[COND:%.*]], i1 false
; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[X]], 2
; CHECK-NEXT:    br i1 false, label [[IF_THEN:%.*]], label [[IF_END:%.*]]
; CHECK:       if.then:
; CHECK-NEXT:    call void @side_effect()
; CHECK-NEXT:    br label [[IF_END]]
; CHECK:       if.end:
; CHECK-NEXT:    ret void
;
entry:
  %cmp1 = icmp ugt i64 %x, 1
  %or1 = select i1 %cmp1, i1 %cond, i1 false
  %cmp2 = icmp ult i64 %x, 2
  %or2 = select i1 %or1, i1 %cmp2, i1 false
  br i1 %or2, label %if.then, label %if.end

if.then:
  call void @side_effect()
  br label %if.end

if.end:
  ret void
}

define void @negative_and_or_tree_second_implies_first(i32 noundef %v0, i32 noundef %v1, i32 noundef %v2) {
; CHECK-LABEL: @negative_and_or_tree_second_implies_first(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP0:%.*]] = icmp sge i32 [[V0:%.*]], [[V1:%.*]]
; CHECK-NEXT:    [[CMP1:%.*]] = icmp sge i32 [[V1]], [[V2:%.*]]
; CHECK-NEXT:    [[AND1:%.*]] = or i1 [[CMP0]], [[CMP1]]
; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[V0]], [[V2]]
; CHECK-NEXT:    [[AND2:%.*]] = and i1 [[CMP2]], [[AND1]]
; CHECK-NEXT:    br i1 [[AND2]], label [[IF_THEN:%.*]], label [[RETURN:%.*]]
; CHECK:       if.then:
; CHECK-NEXT:    call void @side_effect()
; CHECK-NEXT:    br label [[RETURN]]
; CHECK:       return:
; CHECK-NEXT:    ret void
;
entry:
  %cmp0 = icmp sge i32 %v0, %v1
  %cmp1 = icmp sge i32 %v1, %v2
  %and1 = or i1 %cmp0, %cmp1
  %cmp2 = icmp slt i32 %v0, %v2
  %and2 = and i1 %cmp2, %and1
  br i1 %and2, label %if.then, label %return

if.then:
  call void @side_effect()
  br label %return

return:
  ret void
}

declare void @side_effect()
declare void @no_noundef(i1 noundef)