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

    <tr>
        <th>Summary</th>
        <td>
            [DA] Insufficient validation of delinearization results
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:analysis
      </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 %k) {
entry:
  %cmp = icmp eq i64 %k, 0
  br i1 %cmp, label %exit, label %loop

loop:
  %i = phi i64 [ 0, %entry ], [ %i.next, %loop ]
  %i.next = add i64 %i, 1
  %subscript.0 = mul i64 %i, %k
 %subscript.1 = mul i64 %i.next, %k
  %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
  %cond.exit = icmp eq i64 %i.next, 10000
  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 - consistent output [-1]!
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/8Pc4Ev565

The dependencies between the two stores are reported as `[-1]`, which is incorrect if `%k` is negative, as it should be `[1]`. I think the delinearization check is insufficient .Executing `opt --pass='print<delinearization>'` yields the following output:

```
Delinearization on function f:

Inst:  %idx.0 = getelementptr i8, ptr %a, i64 %subscript.0
In Loop with Header: loop
AccessFunction: 0
failed to delinearize

Inst:  %idx.1 = getelementptr i8, ptr %a, i64 %subscript.1
In Loop with Header: loop
AccessFunction: 0
failed to delinearize

Inst:  store i8 42, ptr %idx.0, align 1
In Loop with Header: loop
AccessFunction: {0,+,%k}<%loop>
Base offset: %a
ArrayDecl[UnknownSize][%k] with elements of 1 bytes.
ArrayRef[{0,+,1}<nuw><nsw><%loop>][0]

Inst:  store i8 42, ptr %idx.1, align 1
In Loop with Header: loop
AccessFunction: {%k,+,%k}<%loop>
Base offset: %a
ArrayDecl[UnknownSize][%k] with elements of 1 bytes.
ArrayRef[{1,+,1}<nuw><nsw><%loop>][0]
Compiler returned: 0
```

godbolt: https://godbolt.org/z/9W6YWcMsG

The line `ArrayDecl[UnknownSize][%k] ...` indicates the estimated array size. Maybe we should reject such a result in DA if we cannot prove `%k` is non-negative.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJzEV1GP2jgX_TXm5YrIcQjMPPAQyPB9I22lqt1VtY-Oc0NcjJ21HRjm16_shIGh3e5s29VKaCbkXp97fHx9bLhzcqsRlyRfkbyc8N63xi533PVbPm0-TypTn5aPuus9yQpC42dOh49Shz2hRY2N1AgHI2sgM9oQdtd5C4TlnLA1yPksPO8IuweyWBFaoPb2NMBBCIl9ByQrQYYH_ONqxBpoTKosyHRMDW8Vr1CF7_gk_asXyphuoBmfLkVkLNG1coDPV0DDwIAR6ADJy_g9X8XsROOTHxMCUoyfoWIw4vG6PtOVITs957i-csLKzic0Ju579Soxzo8Wr1PTL1Kvaexe6tdPI-oWPSrco_ZBcXkXMr-i_RWZa4z0-zCGOTpvLIK8gxm7GhGp_U38RSNhdJ2EFfza6l-mnlJKb9vgPPKtzRBDYzNY9LFZQ2RRXjf0kPsBXa_O7X4dYjMwnYdpx51DR7KSsEVnpfYkW9ecZA-ELWBaS8crhVPT-6734NH5RClCi_chVeotcM3VyUkHhC1K7FDXqAVCMb4OKI2x0PRaeGl0SGsIWwyMPlpBsuKb8rM1cCW3GlKYTkn2AKUL0_n2ml0GBZFqPrB8RpiCNhoJSy_Ff3b19Kb66_LCaCedR-1h1JTkq2kaN2z6FkXSn8HpLxS56Z2tqSsTmwda7zsX1oxtCNuMgcTYLWGbZ8I2d-_F7OGQz_Nh5K8tQn1uBokOKvRHRA2-RfBHM1B1wC2Cxc5YjzVwB6H0WY55VP_YStGCdCC1MNai8CCbmBc8ZE5DSOOWe3nAOEkH0oNrTa9qqHBEHAETeATfSr2LPGpUUiO38pnHzhQtit1QyvVNI4UMq5Q8PKHoY6uTOY1bJu6Zmx3zGmvYPoHeSaKqXazXGKXMMQANK__lGURoUd6QMvqydZqXEY96XPIfN9BHDb-EI-EofQv_R16jDcij2xRCoHObkUEIhDENlwpr8OZKQ_w6sx-w5X-L2ZuN458SIItVQCBsFf_mu-DI2frs3dkDocWKOwTTNA4jmSgALQpr-alEoUi--k3vtDnqj4F4XoarTEDKy4HGKKMD00AK1cmjS84AH7AJ6dcs0oGC7o-hfLbWbny4IhWL0OFK8Dad0h_WabwR_fdSpd8t1drsO6nQhiO4txrrcw9-v4vef5r__km8c_-7uGho4mA8b5p2kiTREnUtBfc42A46L_c8GmzAACefMYF3_FQhHPFslRY_B291vWiBg423BpAayiL47RFBcK2Nh86aA976r9HTswcnk3qZ1ffZPZ_gMl3k2WyW5lk2aZdZxrlAmt9lVZOLmchykdGqynJcVPe8ohO5ZJTldMHyNKV5liV37G7WYIOM1Yv0Pm3IjOKeS5WEu3qQbSKd63GZ5nROZ5N4U3Lx8s9YvM5nBX-5hrDwi8Auw_tp1W8dmVElnXcXMC-9ir8dyiKI-Xh9Chy4kvXoyM0XJ8cgl5v0Vi1v1lj6tq8SYfaEbSKn4d-0syYITtgmzsERthmncViyPwMAAP__GajUlQ">