SimpleLoopUnswitch reverses branch condition incorrectly

[nunoplopes]

The issue is exposed by the following unit test:

; Transforms/SimpleLoopUnswitch/inject-invariant-conditions.ll

define i32 @test_02_inverse(ptr noundef %p, i32 noundef %n, i32 noundef %limit, ptr noundef %arr, ptr noundef %x_p) {
entry:
  %x = load i32, ptr %x_p, align 4, !noundef !{}
  br label %loop

loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  %el.ptr = getelementptr i32, ptr %p, i32 %iv
  %el = load i32, ptr %el.ptr, align 4
  %bound_check = icmp sge i32 %el, 0
  br i1 %bound_check, label %guarded, label %bound_check_failed, !prof !{!"branch_weights", i32 100, i32 1}

guarded:
  %range_check = icmp uge i32 %el, %x
  ;; <------  the following branch gets conditions inverted
  br i1 %range_check, label %range_check_failed, label %backedge, !prof !{!"branch_weights", i32 1, i32 100}

backedge:
  %arr.ptr = getelementptr i32, ptr %arr, i32 %el
  store i32 %iv, ptr %arr.ptr, align 4
  %iv.next = add i32 %iv, 1
  %loop_cond = icmp slt i32 %iv.next, %n
  br i1 %loop_cond, label %loop, label %exit

exit:
  ret i32 0

bound_check_failed:
  ret i32 -1

range_check_failed:
  ret i32 -2
}

Alive2 report (search for BUG):

define i32 @test_02_inverse(ptr noundef %p, i32 noundef %n, i32 noundef %limit, ptr noundef %arr, ptr noundef %x_p) {
%entry:
  %x = load i32, ptr noundef %x_p, align 4
  assume_welldefined i32 %x
  br label %loop

%loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
  %el.ptr = gep ptr noundef %p, 4 x i32 %iv
  %el = load i32, ptr %el.ptr, align 4
  %bound_check = icmp sge i32 %el, 0
  br i1 %bound_check, label %guarded, label %bound_check_failed

%guarded:
  %range_check = icmp uge i32 %el, %x
  br i1 %range_check, label %range_check_failed, label %backedge

%range_check_failed:
  ret i32 4294967294

%backedge:
  %arr.ptr = gep ptr noundef %arr, 4 x i32 %el
  store i32 %iv, ptr %arr.ptr, align 4
  %iv.next = add i32 %iv, 1
  %loop_cond = icmp slt i32 %iv.next, noundef %n
  br i1 %loop_cond, label %loop, label %exit

%exit:
  ret i32 0

%bound_check_failed:
  ret i32 4294967295
}
=>
define i32 @test_02_inverse(ptr noundef %p, i32 noundef %n, i32 noundef %limit, ptr noundef %arr, ptr noundef %x_p) {
%entry:
  %x = load i32, ptr noundef %x_p, align 4
  assume_welldefined i32 %x
  %injected.cond = icmp ule i32 2147483648, %x
  br i1 %injected.cond, label %entry.split.us, label %entry.split

%entry.split:
  br label %loop

%loop:
  %iv = phi i32 [ 0, %entry.split ], [ %iv.next, %backedge ]
  %el.ptr = gep ptr noundef %p, 4 x i32 %iv
  %el = load i32, ptr %el.ptr, align 4
  %bound_check = icmp sge i32 %el, 0
  br i1 %bound_check, label %guarded, label %bound_check_failed.split

%guarded:
  %range_check = icmp uge i32 %el, %x
  br label %guarded.check

%guarded.check:
  ;; <-----  BUG: this condition is flipped
  br i1 %range_check, label %backedge, label %range_check_failed

%backedge:
  %arr.ptr = gep ptr noundef %arr, 4 x i32 %el
  store i32 %iv, ptr %arr.ptr, align 4
  %iv.next = add i32 %iv, 1
  %loop_cond = icmp slt i32 %iv.next, noundef %n
  br i1 %loop_cond, label %loop, label %exit.split

%exit.split:
  br label %exit

%range_check_failed:
  ret i32 4294967294

%bound_check_failed.split:
  br label %bound_check_failed

%entry.split.us:
  br label %loop.us

%loop.us:
  %iv.us = phi i32 [ 0, %entry.split.us ], [ %iv.next.us, %backedge.us ]
  %el.ptr.us = gep ptr noundef %p, 4 x i32 %iv.us
  %el.us = load i32, ptr %el.ptr.us, align 4
  %bound_check.us = icmp sge i32 %el.us, 0
  br i1 %bound_check.us, label %guarded.us, label %bound_check_failed.split.us

%guarded.us:
  br label %backedge.us

%backedge.us:
  %arr.ptr.us = gep ptr noundef %arr, 4 x i32 %el.us
  store i32 %iv.us, ptr %arr.ptr.us, align 4
  %iv.next.us = add i32 %iv.us, 1
  %loop_cond.us = icmp slt i32 %iv.next.us, noundef %n
  br i1 %loop_cond.us, label %loop.us, label %exit.split.us

%exit.split.us:
  br label %exit

%exit:
  ret i32 0

%bound_check_failed.split.us:
  br label %bound_check_failed

%bound_check_failed:
  ret i32 4294967295
}
Transformation doesn't verify! (unsound)
ERROR: Source is more defined than target

Example:
ptr noundef %p = pointer(non-local, block_id=1, offset=171798691839)
i32 noundef %n = #x00000001 (1)
i32 noundef %limit = #x00000000 (0)
ptr noundef %arr = pointer(non-local, block_id=0, offset=545460846077)
ptr noundef %x_p = pointer(non-local, block_id=1, offset=549755813879)

Source:
i32 %x = #x00000081 (129)
  >> Jump to %loop
i32 %iv = #x00000000 (0)
ptr %el.ptr = pointer(non-local, block_id=1, offset=171798691839)
i32 %el = #x40000080 (1073741952)
i1 %bound_check = #x1 (1)
  >> Jump to %guarded
i1 %range_check = #x1 (1)
  >> Jump to %range_check_failed

SOURCE MEMORY STATE
===================
NON-LOCAL BLOCKS:
Block 0 >	size: 0	align: 4	alloc type: 0	address: 0
Block 1 >	size: 549755817984	align: 2	alloc type: 0	address: 1
Block 2 >	size: 19327352851	align: 2	alloc type: 0	address: 618577002496
Block 3 >	size: 68362243	align: 2	alloc type: 0	address: 618475290624

Target:
i32 %x = #x00000081 (129)
i1 %injected.cond = #x0 (0)
  >> Jump to %entry.split
  >> Jump to %loop
i32 %iv = #x00000000 (0)
ptr %el.ptr = pointer(non-local, block_id=1, offset=171798691839)
i32 %el = #x40000080 (1073741952)
i1 %bound_check = #x1 (1)
  >> Jump to %guarded
i1 %range_check = #x1 (1)
  >> Jump to %guarded.check
  >> Jump to %backedge
ptr %arr.ptr = pointer(non-local, block_id=0, offset=549755813885)
void = UB triggered!

cc @serguei-katkov @xortator