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

; A == B implies A >u B is false.

define void @test1(i32 %a, i32 %b) {
; CHECK-LABEL: @test1(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[TAKEN:%.*]], label [[END:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 10)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %taken, label %end

taken:
  %cmp2 = icmp ugt i32 %a, %b
  %c = select i1 %cmp2, i32 0, i32 10
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

; If A == B is false then A != B is true.

define void @test2(i32 %a, i32 %b) {
; CHECK-LABEL: @test2(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 20)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %end, label %taken

taken:
  %cmp2 = icmp ne i32 %a, %b
  %c = select i1 %cmp2, i32 20, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

; A >u 10 implies A >u 10 is true.

define void @test3(i32 %a) {
; CHECK-LABEL: @test3(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt i32 [[A:%.*]], 10
; CHECK-NEXT:    br i1 [[CMP1]], label [[TAKEN:%.*]], label [[END:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 30)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp ugt i32 %a, 10
  br i1 %cmp1, label %taken, label %end

taken:
  %cmp2 = icmp ugt i32 %a, 10
  %c = select i1 %cmp2, i32 30, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

define i8 @PR23333(ptr addrspace(1) %ptr) {
; CHECK-LABEL: @PR23333(
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq ptr addrspace(1) [[PTR:%.*]], null
; CHECK-NEXT:    br i1 [[CMP]], label [[TAKEN:%.*]], label [[END:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    ret i8 1
; CHECK:       end:
; CHECK-NEXT:    ret i8 0
;
  %cmp = icmp eq ptr addrspace(1) %ptr, null
  br i1 %cmp, label %taken, label %end

taken:
  %cmp2 = icmp ne ptr addrspace(1) %ptr, null
  %res = select i1 %cmp2, i8 2, i8 1
  ret i8 %res

end:
  ret i8 0
}

; We know the condition of the select is true based on a dominating condition.
; Therefore, we can replace %cond with %len.
; TODO: len == 8 is known false in bb. This is handled by other passes, but should it be handled here?

define void @test4(i32 %len) {
; CHECK-LABEL: @test4(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[TMP0:%.*]] = call i32 @bar(i32 [[LEN:%.*]])
; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[LEN]], 4
; CHECK-NEXT:    br i1 [[CMP]], label [[BB:%.*]], label [[B1:%.*]]
; CHECK:       bb:
; CHECK-NEXT:    br i1 false, label [[B0:%.*]], label [[B1]]
; CHECK:       b0:
; CHECK-NEXT:    call void @foo(i32 [[LEN]])
; CHECK-NEXT:    br label [[B1]]
; CHECK:       b1:
; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ [[LEN]], [[BB]] ], [ undef, [[B0]] ], [ [[TMP0]], [[ENTRY:%.*]] ]
; CHECK-NEXT:    br label [[RET:%.*]]
; CHECK:       ret:
; CHECK-NEXT:    call void @foo(i32 [[TMP1]])
; CHECK-NEXT:    ret void
;
entry:
  %0 = call i32 @bar(i32 %len);
  %cmp = icmp ult i32 %len, 4
  br i1 %cmp, label %bb, label %b1
bb:
  %cond = select i1 %cmp, i32 %len, i32 8
  %cmp11 = icmp eq i32 %cond, 8
  br i1 %cmp11, label %b0, label %b1

b0:
  call void @foo(i32 %len)
  br label %b1

b1:
  %1 = phi i32 [ %cond, %bb ], [ undef, %b0 ], [ %0, %entry ]
  br label %ret

ret:
  call void @foo(i32 %1)
  ret void
}

; A >u 10 implies A >u 9 is true.

define void @test5(i32 %a) {
; CHECK-LABEL: @test5(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt i32 [[A:%.*]], 10
; CHECK-NEXT:    br i1 [[CMP1]], label [[TAKEN:%.*]], label [[END:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 30)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp ugt i32 %a, 10
  br i1 %cmp1, label %taken, label %end

taken:
  %cmp2 = icmp ugt i32 %a, 9
  %c = select i1 %cmp2, i32 30, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

declare void @foo(i32)
declare i32 @bar(i32)

define i32 @test_and(i32 %a, i32 %b) {
; CHECK-LABEL: @test_and(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[A:%.*]], 0
; CHECK-NEXT:    [[CMP2:%.*]] = icmp ne i32 [[B:%.*]], 0
; CHECK-NEXT:    [[AND:%.*]] = and i1 [[CMP1]], [[CMP2]]
; CHECK-NEXT:    br i1 [[AND]], label [[TPATH:%.*]], label [[END:%.*]]
; CHECK:       tpath:
; CHECK-NEXT:    ret i32 313
; CHECK:       end:
; CHECK-NEXT:    ret i32 0
;
entry:
  %cmp1 = icmp ne i32 %a, 0
  %cmp2 = icmp ne i32 %b, 0
  %and = and i1 %cmp1, %cmp2
  br i1 %and, label %tpath, label %end

tpath:
  %cmp3 = icmp eq i32 %a, 0 ;; <-- implied false
  %c = select i1 %cmp3, i32 0, i32 313
  ret i32 %c

end:
  ret i32 0
}

; cmp1 and cmp2 are false on the 'fpath' path and thus cmp3 is true.

define i32 @test_or1(i32 %a, i32 %b) {
; CHECK-LABEL: @test_or1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], 0
; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[B:%.*]], 0
; CHECK-NEXT:    [[OR:%.*]] = or i1 [[CMP1]], [[CMP2]]
; CHECK-NEXT:    br i1 [[OR]], label [[END:%.*]], label [[FPATH:%.*]]
; CHECK:       fpath:
; CHECK-NEXT:    ret i32 37
; CHECK:       end:
; CHECK-NEXT:    ret i32 0
;
entry:
  %cmp1 = icmp eq i32 %a, 0
  %cmp2 = icmp eq i32 %b, 0
  %or = or i1 %cmp1, %cmp2
  br i1 %or, label %end, label %fpath

fpath:
  %cmp3 = icmp ne i32 %a, 0  ;; <-- implied true
  %c = select i1 %cmp3, i32 37, i32 0
  ret i32 %c

end:
  ret i32 0
}

; LHS ==> RHS by definition (true -> true)

define void @test6(i32 %a, i32 %b) {
; CHECK-LABEL: @test6(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[TAKEN:%.*]], label [[END:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 10)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %taken, label %end

taken:
  %c = select i1 %cmp1, i32 10, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

; LHS ==> RHS by definition (false -> false)

define void @test7(i32 %a, i32 %b) {
; CHECK-LABEL: @test7(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 11)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %end, label %taken

taken:
  %c = select i1 %cmp1, i32 0, i32 11
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

define void @implies_or(i32 %a, i32 %b, i1 %x) {
; CHECK-LABEL: @implies_or(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 20)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %end, label %taken

taken:
  %cmp2 = icmp ne i32 %a, %b
  %or = or i1 %cmp2, %x
  %c = select i1 %or, i32 20, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

define void @implies_or_comm(i32 %a, i32 %b, i1 %x) {
; CHECK-LABEL: @implies_or_comm(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 20)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %end, label %taken

taken:
  %cmp2 = icmp ne i32 %a, %b
  %or = or i1 %x, %cmp2
  %c = select i1 %or, i32 20, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

define void @implies_or_branch_comm(i32 %a, i32 %b, i1 %x) {
; CHECK-LABEL: @implies_or_branch_comm(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[TAKEN:%.*]], label [[END:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 20)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp ne i32 %a, %b
  br i1 %cmp1, label %taken, label %end

taken:
  %cmp2 = icmp ne i32 %a, %b
  %or = or i1 %cmp2, %x
  %c = select i1 %or, i32 20, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

define void @implies_logical_or(i32 %a, i32 %b, i1 %x) {
; CHECK-LABEL: @implies_logical_or(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 20)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %end, label %taken

taken:
  %cmp2 = icmp ne i32 %a, %b
  %or = select i1 %cmp2, i1 true, i1 %x
  %c = select i1 %or, i32 20, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

define void @implies_logical_or_comm(i32 %a, i32 %b, i1 %x) {
; CHECK-LABEL: @implies_logical_or_comm(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 20)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %end, label %taken

taken:
  %cmp2 = icmp ne i32 %a, %b
  %or = select i1 %x, i1 true, i1 %cmp2
  %c = select i1 %or, i32 20, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

define void @doesnt_imply_and(i32 %a, i32 %b, i1 %x) {
; CHECK-LABEL: @doesnt_imply_and(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    [[C:%.*]] = select i1 [[X:%.*]], i32 20, i32 0
; CHECK-NEXT:    call void @foo(i32 [[C]])
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %end, label %taken

taken:
  %cmp2 = icmp ne i32 %a, %b
  %or = and i1 %cmp2, %x
  %c = select i1 %or, i32 20, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

define void @implies_not_and(i32 %a, i32 %b, i1 %x) {
; CHECK-LABEL: @implies_not_and(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 0)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %end, label %taken

taken:
  %cmp2 = icmp eq i32 %a, %b
  %and = and i1 %cmp2, %x
  %c = select i1 %and, i32 20, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

define void @implies_not_and_comm(i32 %a, i32 %b, i1 %x) {
; CHECK-LABEL: @implies_not_and_comm(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 0)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %end, label %taken

taken:
  %cmp2 = icmp eq i32 %a, %b
  %and = and i1 %x, %cmp2
  %c = select i1 %and, i32 20, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

define void @implies_not_and_branch_comm(i32 %a, i32 %b, i1 %x) {
; CHECK-LABEL: @implies_not_and_branch_comm(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[TAKEN:%.*]], label [[END:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 0)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp ne i32 %a, %b
  br i1 %cmp1, label %taken, label %end

taken:
  %cmp2 = icmp eq i32 %a, %b
  %and = and i1 %cmp2, %x
  %c = select i1 %and, i32 20, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

define void @implies_not_logical_and(i32 %a, i32 %b, i1 %x) {
; CHECK-LABEL: @implies_not_logical_and(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 0)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %end, label %taken

taken:
  %cmp2 = icmp eq i32 %a, %b
  %and = select i1 %cmp2, i1 %x, i1 false
  %c = select i1 %and, i32 20, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

define void @implies_not_logical_and_comm(i32 %a, i32 %b, i1 %x) {
; CHECK-LABEL: @implies_not_logical_and_comm(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    call void @foo(i32 0)
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %end, label %taken

taken:
  %cmp2 = icmp eq i32 %a, %b
  %and = select i1 %x, i1 %cmp2, i1 false
  %c = select i1 %and, i32 20, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}

define void @doesnt_imply_or(i32 %a, i32 %b, i1 %x) {
; CHECK-LABEL: @doesnt_imply_or(
; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
; CHECK-NEXT:    br i1 [[CMP1]], label [[END:%.*]], label [[TAKEN:%.*]]
; CHECK:       taken:
; CHECK-NEXT:    [[C:%.*]] = select i1 [[X:%.*]], i32 20, i32 0
; CHECK-NEXT:    call void @foo(i32 [[C]])
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    ret void
;
  %cmp1 = icmp eq i32 %a, %b
  br i1 %cmp1, label %end, label %taken

taken:
  %cmp2 = icmp eq i32 %a, %b
  %and = or i1 %cmp2, %x
  %c = select i1 %and, i32 20, i32 0
  call void @foo(i32 %c)
  br label %end

end:
  ret void
}