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

    <tr>
        <th>Summary</th>
        <td>
            [DA] Does not account for wrapping accesses
        </td>
    </tr>

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

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

    <tr>
      <th>Reporter</th>
      <td>
          kasuga-fj
      </td>
    </tr>
</table>

<pre>
    Input:

```llvm
define void @f(ptr %a, i64 %n, i64 %m) {
entry:
  %bound = sub i64 %m, %n
  br label %loop

loop:
 %i = phi i64 [ 0, %entry ], [ %i.next, %loop ]
  %subscript.0 = add i64 %i, %n
  %subscript.1 = add i64 %i, %m
  %idx.0 = getelementptr i8, ptr %a, i64 %subscript.0
  %idx.1 = getelementptr i8, ptr %a, i64 %subscript.1
  store i8 42, ptr %idx.0
  store i8 42, ptr %idx.1
  %i.next = add i64 %i, 1
 %cond.exit = icmp eq i64 %i.next, %bound
  br i1 %cond.exit, label %exit, label %loop

exit:
  ret void
}
```

Result:

```
$ opt -passes='print<da>' -disable-output test.ll
Printing analysis 'Dependence Analysis' for function 'f':
Src:  store i8 42, ptr %idx.0, align 1 --> Dst: store i8 42, ptr %idx.0, align 1
  da analyze - none!
Src:  store i8 42, ptr %idx.0, align 1 --> Dst:  store i8 42, ptr %idx.1, align 1
  da analyze - none!
Src:  store i8 42, ptr %idx.1, align 1 --> Dst:  store i8 42, ptr %idx.1, align 1
  da analyze - none!
```

godbolt: https://godbolt.org/z/jvascaoo7

At the very least, when both `%n` and `%m` are zero, there is a dependency between the two stores within a single iteration.

Here is a portion of the debug output related to the analysis between them:

```
testing subscript 0, SIV
    src = {(%n + %a),+,1}<%loop>
    dst = {(%m + %a),+,1}<%loop>
        Strong SIV test
         Coeff = 1, i64
            SrcConst = (%n + %a), ptr
            DstConst = (%m + %a), ptr
            Delta = ((-1 * %m) + %n), i64
            UpperBound = (-1 + (-1 * %n) + %m), i64
none!
```

The root cause seems to be that DA uses the backedge-taken count as the iteration count without considering any wrapping accesses (ref: [strongSIVtest](https://github.com/llvm/llvm-project/blob/6c63316ee17462c97c722a960680b2b45d2fff4d/llvm/lib/Analysis/DependenceAnalysis.cpp#L1268-L1283)). In this case, the issue is caused by `strongSIVtest`, but I suspect similar issues may exist elsewhere in DA.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJy0VluP2zgP_TXKC5HAlmM7fshDEjf4BujDh53dvutCJ2ptySvJk0l__UKyc5tOt90bECC2SB4dkYeUmXPqoBHXJN-SvJ6xwR-NXX9hbjiwefN5xo08r590P3iSbUgSf0Uy_tr2pSPJRmKjNMKLURLIMmkIXfXeAqE5I3QHqliGZ3333BFaASm3JNmg9vY8QkMwcTNoCSSrwQ38zn83YgQvbqFlHNuw0hrTj6zi04hDaK4iRH9UI0S-hWTCiBsCyev4nm-j90Ljq58cAlC0T4zcwJ2wqveLJIIyKS-81AOvB9_0e77dxVfJ1wnxgB5b7FD7kDe1Cp7vZPCOyD1G-vcw0ojhvLEIagVLehcRqf3Anl45xOS9e9x0qoYwWi7wVY1eSnQ94O9Xz_vkx_JfqqzSh-Dgci38Nws3JUTTpCiLPgozWMr6Xryj7y_ohvYdaYdnugTTe5j3zDl0JKsJLXurtCfZTjKSfSC0hLlUjvEW52bw_eDBo_OLtiXJ5v_BVekDMM3as1MOCC1r7FFL1AJhMy0HlMZYaAYtvDI6uDWEliOpZytI9oNC0R2wVh00pDCfk-wD1C4c6SdjYp4kG2l-RZiDNhoJTf_h7n-qnX9r-_S_3P6NVg5GchPFAkfvexcKRPeE7ifDwtgDofuvhO4_vzAnmDHlGLnx4I8IL2jP0CJzUbmnI2rgxh8h7BCGSJEAC8Mvvnbx1SJ8RWuCvz9iOI8DBvKiojNw9CdEHfH9yYyndnBS_qg0MHBKH1oE5dGyoK7FyOh_V6ze2Kg600QMiXw4wCRmiy3zKMGbaLsK-W7T7t3eCV0QpH8dN-P4fX76FPMN4KyIsyBcAnQVTg-EbqdpVRG6I3RL6C4NTZvtLu2dfZjCpfOP4d1Ph5OkevbW6ENgE9t1XISdwaaJqOk0MCcDADxbsTP6sum7hIPAbgG1828D3lJ8E4CtZzfv1TzMvs3tshxD9RT6QO63vke7vd6bl-AtPMDoO5juAea7gv_1iGCN8SDY4BAcYueCFjiCPzIP9QYGhy5qgzPxBeUB5559QQ3CDNoDG21X8U3LQZxm8CCMdkqiHYfkGU6W9X18EQLDzA0nsNiEjiP51sWyPT99ikULF_jqTR8qfxz4QpiO0H38OBn_5r01n1F4Qve8NZzQfSGKLEsLxLRcFlRUpSgpZVWRFKuEU77MJW2aZinvcFSIu83s_W2SXxYXou8JzT6mtFjNP6Z0lcU0Vwt4Cq2iHAjmcGplUM4NsQVjciXwc2j8xzMWsWv44OEJ3OB6FB6c6lTL7BjvoGNnwFflPGDr8DTOCA31ZjGT60xWWcVmuE7LnK6yqizy2XFdLfNGSlYxXiETiUhkwjGpqmW6rEqayJla04TmSZmu0jQvknyRYUornjS5SCkvkowsE-yYahchOWHszSKbdbqs8iSdxTvZxU9KSjWeRq6E0vCFadexJHw4OLJMWuW8u8F45dv4LVpvSF5DbdCBNj4IIion3JPfqGQ22Hb9l5Uw5o_Q_UT6ZU3_CAAA___HeTtV">