<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/63962>63962</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            SimpleLoopUnswitch reverses branch condition incorrectly
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            miscompilation,
            llvm:optimizations
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          nunoplopes
      </td>
    </tr>
</table>

<pre>
    The issue is exposed by the following unit test:
```llvm
; 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):
```llvm
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
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsWV1v8yoS_jXkBiWywZ8XuWiadqXd95xKbd-LvYocmyRsibEA503Pr1-Bv_BH2rSnu9uVTlW5NTAz8MzMw2ASKek-J2QJ_BXw17OkVAculnmZ84LxgsjZlmevy-cDgVTKUj8hORdckgxuX6E6ELjjjPFfNN_DMqcKKiIVwDfAWQPnBgRO9cvY6Vg34RV8Fkkud1wcJUD3T_RYMPKD8-JnLn9RlR4Auqf5v0iq5jQ_JYImuZqnPM-oojyXC8ZqTeaZkR3NCaQYQeA52vrGQRuan4iQBKCoUALmvMwzsoMA-QVAt2aw1ZZPtDF6pEq3D-QTISZaz5sCoBiCcFVNiuRKvLYoQDMEAryGjCeZNtXoaGRvYcLoPoee_hcgt9PtaqXhutG0FZAlW8LMHDkvbCjMe88oPRmrxYFWAPkr6FQWfDNFCPy1efdX1fBFTs6qHrFN0heS7YkZ1OkkbGFmjtdwTxRh5EhypVv6y2qBNnp78peQqDTbYHRSWw3IJj2Q9MWI0_RYQLknjQnCtJxjwUTdgZwe0GK3LxORkazXZo3d7BLKqm6A3ELw1hXIBQhtRZKnh80vQvcHJQFCzWJdx2n_bb1WPRuLPQeJJN-T4bLK4bJ0lLRCeKVTCODbufkZ5GA1M-0ZCbucgSYfFMlG-FgT6GFhtVtYdFDVsfFxgGyk-gC1OnsIJUJcFW91Yna41Sqk4oJYgdiTuBxvdSoYs0mW9RW41kCddBuNtBWWTHXj7YzKR_C30j10TSLbDeRMlQ2Vee9gEqQy6PTgHEdzK9EIzF1bYsLnYxtzVIu0zms43lZ1w-iJIChIwYWCAEWSJCI9wB0XcPXzbwDFb-0R35LTG868htaHakYRlkhZHsnmF2GsWmwbYedrmL5p-u-SfTFcm1mZB8___zzfx3ZE1Z9i6i_j2P7krspSD8VeHIQo9gbS15DsyM91glie_ob82kv-L-LZpukdqp2OqTe84g85FK8BvvuL_M52hJgjAMkWfeeXrMIGuV7oRTjwoot519PQ97Ney0IWjKpFKS91DSPB6ulg-HKarix8e7L-n3H1pG--qLi2nVmrXFTznDRX91lG-8U5NLUOvoHqQK1yXB-id4wWxQfqcbvgfmsD-X5s_63JfjrRu47pPJ_YJv7krnwpyqftv1vADPjtMlvp3jFh9WUq5Et5DW2ZYVPMVdOsFZPN0CF_NZauorB2_o2CWvgikdXzeLPwbJSM-ayWfpPShhtKwxWD5ksuH3vEUnAhHDpEL-T_yKF1tr6B9RQLWGgPiKBeXZ8LLmLdxcSYEmqhSVboO2ZEDLXoddww9EcT99MMMYa233c1T_TLyeuryfdMvUsJf65Abb_YJmYDyziROUChgici6O4VIA1uVOZSW9GneyN19_j48Kj3vydeitR8PD7qsGmqPnVIcqgSsSc9mO7OybFg3aY1ZIGKiDjNFREARTnP54ynidnNt4ynLxuaAbw2n5r4bieJ0m-hG8ZRELsRjtsJDutmoxkgfHaqH7Mq99JwU1IPRRwt4rQi46y6cvZOb_a-53uBE3mBE4aXdJ83n0PG9-LQ9yMXR2GHTPWs_NY6oqnSB2uOKphQJ60roTuA7-Dfy2MBFe8Xx23WXoFdv6z9Mqd3Ja8271XLMOZdJ8Sh58Y-6gSGFN8KDuJjatlNZWppGtalV2p6u9p7evj5eHsHf7v77eHxn_Dp-eb5zjpbfurXiP_-8Pv8x8PtzQ-4-vFw-4-nNhhWGnTomIk6saR_6DjRTBYbwtcvnnlhPIXqtei6s0wQKevXTpU7UNXEZRhHnq0VvafVtbWigVY3xijEPop890NKAzfyw9BxkBcHtn480B9EOEDIwx9V7oU-ip0A9UrD54obP5x_E-ffTqafZFORNjoD_5XP_4F8njhgTg3rfwbsV1if3Esavo_8doInTqsQ-bmCStD9ngh9Em_uB6a-8acpBJ4jidiXhM5fEvXCT7rlzIVKFBezbImzGMfJjCzdIIrDyHV9f3ZYejsnDVwncOIkxCj2siyMiReEuxTjHdkmM7pEDsJO6Mauj2PXX-AocN0Q-V6SuGkcYOA55JhQtmDsdFxwsZ-Z2-llgOMAzUxRJM2VNkJHKlN-LCgzlUt1EwUQMpcN-IYXih7pH6bPXFP565lY6s75ttxL4DmMSiU7O4oqRpbjO2soiPlAJ5sbOOu0n6dcCJIq9jorBVselCpMGYfuAbrfU3Uot4uUHwG6N7Oq_swLwXX6AnRv1iYBujfL-3cAAAD__zxhD04">