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

    <tr>
        <th>Summary</th>
        <td>
            [LAA] Different safety answer in LAA for two equivalent tests.
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

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

    <tr>
      <th>Reporter</th>
      <td>
          max-quazan
      </td>
    </tr>
</table>

<pre>
    Run
`opt  -passes='loop(loop-rotate),print-access-info'`
or 
`opt -passes='loop(loop-rotate),invalidate<loops>,print-access-info'`
on the following test:
```
define void @test_01(i32* %p) {
entry:
  br label %loop

loop.progress:                                              ; preds = %loop
  br label %loop.backedge

loop.backedge:                                              ; preds = %loop.progress
  store i32 1, i32* %tmp7, align 4
  %tmp = add nuw i64 %tmp5, 1
  %tmp3 = icmp ult i64 %tmp, 1000
  br i1 %tmp3, label %loop, label %exit

loop:                                              ; preds = %loop.backedge, %entry
  %tmp5 = phi i64 [ %tmp, %loop.backedge ], [ 16, %entry ]
  %tmp6 = phi i64 [ %tmp5, %loop.backedge ], [ 15, %entry ]
  %tmp7 = getelementptr inbounds i32, i32* %p, i64 %tmp5
  %tmp8 = load i32, i32* %tmp7, align 4
  %tmp9 = add i32 %tmp8, -5
  store i32 %tmp9, i32* %tmp7, align 4
  br i1 false, label %never, label %loop.progress

never:                                             ; preds = %loop
  unreachable

exit:                                             ; preds = %loop.backedge
  ret void
}

define void @test_02(i32* %p) {
entry:
  br label %loop

loop.progress:                                              ; preds = %loop
  br label %loop.backedge

loop.backedge:                                              ; preds = %loop.progress
  store i32 1, i32* %tmp7, align 4
  %tmp = add nuw i64 %tmp5, 1
  %tmp3 = icmp ult i64 %tmp, 1000
  br i1 %tmp3, label %loop, label %exit

loop:                                              ; preds = %loop.backedge, %entry
  %tmp5 = phi i64 [ %tmp, %loop.backedge ], [ 16, %entry ]
  %tmp6 = phi i64 [ %tmp5, %loop.backedge ], [ 15, %entry ]
  %tmp7 = getelementptr inbounds i32, i32* %p, i64 %tmp5
  %tmp8 = load i32, i32* %tmp7, align 4
  %tmp9 = add i32 %tmp8, -5
  store i32 %tmp9, i32* %tmp7, align 4
  br label %loop.progress

exit:                                             ; preds = %loop.backedge
  ret void
}

define void @test_02(i32* %p) {
entry:
  br label %loop

loop.progress:                                    ; preds = %loop
  br label %loop.backedge

loop.backedge:                                    ; preds = %loop.progress
  store i32 1, i32* %tmp7, align 4
  %tmp = add nuw i64 %tmp5, 1
  %tmp3 = icmp ult i64 %tmp, 1000
  br i1 %tmp3, label %loop, label %exit

loop:                                             ; preds = %loop.backedge, %entry
  %tmp5 = phi i64 [ %tmp, %loop.backedge ], [ 16, %entry ]
  %tmp6 = phi i64 [ %tmp5, %loop.backedge ], [ 15, %entry ]
  %tmp7 = getelementptr inbounds i32, i32* %p, i64 %tmp5
  %tmp8 = load i32, i32* %tmp7, align 4
  %tmp9 = add i32 %tmp8, -5
  store i32 %tmp9, i32* %tmp7, align 4
  br label %loop.progress

exit:                                   ; preds = %loop.backedge
  ret void
}

```
These tests are fully equivalent, the only difference is that test_01 has
```
  br i1 false, label %never, label %loop.progress

```
and test_02 immediately does
```
  br label %loop.progress

```
However, LAA treats them differently from safety perspective and says that test_02 is safe while test_01 isn't. This looks like a bug.
```
Loop access info in function 'test_01':
  loop.progress:
    Report: unsafe dependent memory operations in loop. Use #pragma loop distribute(enable) to allow loop distribution to attempt to isolate the offending operations into a separate loop
Backward loop carried data dependence.
    Dependences:
      Forward:
          %tmp8 = load i32, i32* %tmp7, align 4 ->
          store i32 %tmp9, i32* %tmp7, align 4

      Backward:
          store i32 1, i32* %tmp75, align 4 ->
          %tmp8 = load i32, i32* %tmp7, align 4

      Backward:
          store i32 1, i32* %tmp75, align 4 ->
          store i32 %tmp9, i32* %tmp7, align 4

    Run-time memory checks:
    Grouped accesses:

    Non vectorizable stores to invariant address were not found in loop.
    SCEV assumptions:

    Expressions re-written:
Loop access info in function 'test_02':
  loop:
    Memory dependences are safe
    Dependences:
    Run-time memory checks:
    Grouped accesses:

    Non vectorizable stores to invariant address were not found in loop.
    SCEV assumptions:

    Expressions re-written:
```

Initially test_01 also demonstrated that LAA's algorithm is sensitive to blocks order within a Loop, and https://github.com/llvm/llvm-project/issues/56672 removes this dependency by defining traversal order independent on their storage in loop. However, seems that it doesn't fix the original miscompile caused by wrong loop evaluation.

Thanks @fhahn for finding this!

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztWFFz4jYQ_jXmZQfG2BjDAw9JuGs7c-3D9drXjmwtWI0t-SQZkvv1XclgbJIjyV3ambZhGIOl1be7n1a7kjLF71cfGxmE6yC8Cuahqi3AuGbGoAnidRClpVJ1EC3cz1gryywG0TKIbmotpB2zPEdjxkJuFMkSQIukNAwgn4Uo5I6Vgrv3-Mb1kvy7JzVJsAXCRpWl2gu5BYvGBvFVp_7w9a8cN0Ii7JTgEMxCJ_pHOCVbRBwF0RUEUUKWLSFIr9sBKK2-79AAMg0ly7B0kt6NVot_uvdJrdVWk500Bl70CeJrqDVyQ__WQ_iHaicZy2-Rb_GB_q7jVfSf3DkYYqzSCMQWEGs3cKLNVnXqWmgCtxJmR_m2x0MyzkE2exDz2aE5cQOmQ9HYy4qcBjWl7Ql72TAMe5SI6XGQ6xzOS78B74Q9J-qV-OnoJn1Okw-XgUOJl68L0fqSXPf8OUeh7rVvJ6npvI_pewa486_gJk8CJ5eBUw-8RYslViRTW2JaZqqR5Luf8P68ez_6UzrAWnisUjH-cOTFiFl2IeNi7QDmpMfJw1A8DHkWfBs2G1YaHMSIxB3qB2F0Fv_tsxV9YfxcXN6N1MjygmXlYEH7uH0NPWfpAkCj9UnwoC1d99U-miSjtyT5VXbfkuRlft6S5L8vST6dBt-y0wWf_vac9JaJvifQ3hLR_zIRvUL6OTtQfirQoD9yGmDk4KYpy3vAz42goyxNh_PJHU-VpGYuNhvUKHMiwlAzs3A4gULBzKP4r7JhPcNkkh_0RiCqCrmgE7czT-EFI16s5ke1P5r44eoKLG1xrfMaq44IS1o3WlVg2AbtPdSoTY25FTsEZ6Vh9wOeIsebk4V9IUrs2BNGBlFqJ_CpIAEy8Jae4pZAIGu2k0fN-0BuQHunAO5OgR40e5KUKwkO7Xg3kPZqx3l9OLYDfMRaaR-GjfQWcqxRcvIRKqwULV1F3jGH7vS1SPAbBU8QxbVm24r5NuLGWC2yxl2KLFD6MwGVM6tobZRqfybkjHVd1mJVW_dXGFXSfLZRRzRL7i5FBsrdADBYM-0ET-XqmhbCnmne6siZ1gI5cGZZ502Ok5PP665xyAXAe6Ud0FmrX4IvzTQwdpdAZyjfkk36GEdPHzHwYslMnjLsGxPpP2Lb95H2sZFjKyo8hnNeYH47nPcftGpqiph2VfWC4iTyC8Xrjla40uKLC-3WKOMDV-6YFowWDBUSt75gTzkCpLKwceWsWzUntF9v3v0OzJiGYt_F9iMK393VDstHvsbxXgtaKrITfF4WiB5mgYHjP7eUnBZJWwxcHnh6tfw3iT3Ltu3zJymsYK5CHjM3lTVFvFWEYl024m26p4JBlBOL5ZYcskXlEz9KI3xtIKeyUhFLoDRHDXsSIScYfDjsJV3xKKytveHRe_puSaTJJrmq6KUsd8efMWXzP4k3ehXkL3EbvU_m8zQipyq1cwy6mtJN7T1kbqLpDOLvmjWjEmdYeTBEyFPaby-mhfYzwWhX12X9XmU0iNWhxAnrK7CvZLARd20G12IrJOFXwpDttat6OWsMEUV27LUiI3y2RtpvND7DT_qMfyqYJJrooLQpWEGxrTRhtzXBORZEhw39CFfTebJYLqfTdDniq5gv4yUbWWFLXNFG1M1Isob1sXIfSzaTZu8d90Xewdu96m2A2r3RZNTocvU9M5Km01GxysM8mfEsy_l0ueDTxSxdZnEYzWIWp3kexiO_SzHO4CCKJNLxxUHQfzJ-JFZRGEVhGi3CeRIl6WSe8vlyFuez2RQ3YYZEE1ZMlBNnx0Tp7UivvEm0izDUWQrnS9dJC4RSJXp-HD5rbKH0qmJ3488N-8LkyGtfeev_AqeQLCg">