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

    <tr>
        <th>Summary</th>
        <td>
            [BasicAA] Incorrect alias analysis causing miscompile in slp-vectorizer
        </td>
    </tr>

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

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

    <tr>
      <th>Reporter</th>
      <td>
          wlei-llvm
      </td>
    </tr>
</table>

<pre>
    Hi! We recently hit a miscompile issue that slp-vectorizer turned two 8 byte(memory overlap) load/store into one 16 byte load/store and we further pinpointed to an incorrect alias analysis. 
Here is the reduced LLVM IR to repro: [reduced.ll.txt](https://github.com/user-attachments/files/16240607/reduced.ll.txt)
Cmd:
```
opt -S -passes=slp-vectorizer  < reduced.ll
```
Incorrect codegen result: (notice the `load <2 x i64>/  store <2 x i64> `)
```
15: ; preds = %15, %14
  %16 = phi ptr [ %0, %15 ], [ %13, %14 ]
  %17 = phi ptr [ null, %15 ], [ %8, %14 ]
  %18 = load <2 x i64>, ptr %16, align 1
  %19 = shufflevector <2 x i64> %18, <2 x i64> poison, <2 x i32> <i32 1, i32 0>
  store <2 x i64> %19, ptr %17, align 1
  br i1 false, label %15, label %.loopexit42.2
```
It's a very tricky case, here are some explanations and pictures to help demo the issue:

1) To be simple, let's start using the node`%3` as root, the node value is a alias check for the same value alias(<%3, %3>) (this is because it's under the [`MaybeCrossIteration`(BasicAliasAnalysis.cpp)](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L1804-L1805) to check if it's no-alias across different iterations )
2) Before recursively checking the dependencies on def-use chain, it initializes the cache with NoAlias(IIUC, this is an assumption based NoAlias [BasicAliasAnalysis.cpp#L1691-L1693)](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L1691-L1693)
3) Keep checking the alias recursively, i,e. check `<%23, %23>`, --> `<%7, %7>` -->`<%3, 3>` until it finds a circle. Then it runs the code in [BasicAliasAnalysis.cpp#L1693-L1702](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L1693-L1702), which fetches the initial assumption based value in the cache for %3. 

4) Then the recursion return back to %7. IIUC, Now %7 is done all the dependencies check, it run the [code](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L1725) to update stats to `definitive`. Since it depends on an assumption based value(%3), it's pushed into the `AssumptionBasedResults`([code](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L1736-L1738)) which IIUC later if the assumption is disproven, we will remove all the results based on this assumption. 

5)  Continue returning to %23 and process %23's right child %8. 


6) (Bug occurs!) when processing %8's child %7, as previously %7 is marked as `definitive`, %8 is not considered as a  assumption based([code](https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L1694)) and never pushed into `AssumptionBasedResult`, this is incorrect because actually %7 is assumption based(its dependence %3 is assumption based and have't been proven yet), and <%8, %8> is missing to be pushed into `AssumptionBasedResult`.
  
 

7) Return and process %3's right child %99, say <%99> is not a NoAlias, now the previous %3's NoAlias assumption is disproven, all the `AssumptionBaseResult` based on %3 are disproven, i,e. `<%23, %23>`, `<%7,%7>` are removed from cache and needed to recompute, but as %8 is missing in `AssumptionBasedResult`, <%8, %8> is still in the cache. Later any query uses the  <%8, %8> is incorrect, in this case, it causes the incorrect <%16, %17> alias that leads to the miscomplile. 

In summary:
There seems to be a bug in this assumption-disproven mechanism: we incorrectly turned a no-alias assumption into a definitive no-alias result, then later alias result (for other use of the def with incorrect result) were produced incorrectly (which should be assumption based result instead of definitive result) too. Finally when assumptions got invalidated correctly due to other alias on dependencies, we failed to invalidate part of the chain due to assumption based result being prematurely turned into definitive result, escaping invalidation.

Therefore, I'm posting here to ask for help how to properly fix this, thanks in advance! 

cc @nikic @WenleiHe  @fhahn @hiraditya @jdoerfert  @preames  
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzEWF1zpLjO_jXkRkUXmKaBi1wkPZva1Du7F7v7nr02RgRvjM2xTWd6f_0p2dB0MsnM-biYqlQHsC1b0qNHkrlz8kkj3iblfVJ-uuGzH4y9fVEoU6VO401ruvPtzzJhOfyJYFGg9uoMg_TAYZROmHGSCkE6NyP4gXtwakpPKLyx8m-04GersQP_YqCG9uwxYfWIo7FnMCe0ik8Ja0AZ3iXswXljEaT2BoxGyA9hxetRrjt4Qehn6we0MEk9Gak97WGAa5BaGGtReOBKcgdcc3V20u0gyT4l2d3PSFs48AMp1M0CO_j8-R-_wONvJMHiZE1S3EFS3i_DO6V2_otPyk8JqwfvJ5cUdwl7SNjDk_TD3O6EGRP2MDu0Kfeei2FE7V3CHnqpkP7nB7bPDlmVsIc3QlkTj3UcO5IanpNDtvyFVzN5SH-HdOLOoUuKT29MDElxhE3suzIeL1YRpsMn1GDRzcoHTVmtjZcCg02SQ0b2JqEMvoA87JPip4Q9AET7v_pOsy8qvNkyL4Pw4h4mi52DpPgECSvzMmHH8LCP8yC8HML4NEiYvCXj09dsnVpCsP5xHciLi5AwciWo-kqQnpX6SFD9oZw6yHnPFMcomQ5NL1zJJw359domrHXD3PcKo6fe2o12CHu_-jwZ6Yy-_l6wML04yoJBTiP0kNFBlg3fdQsd4vqk1TsnbS3IHHquHNKo4i2qzUOX150yZsIv0u_Zjr0PLp-wygGHE9ozeCvF8xkEj2IHijduEZwZEfDLpLjmXhrtQihPUvjZoqPYG1BN0OFoAhADp2wxETFFZPGHgRbByXFS8eAY93eeWw-zk_opCNCmw4DPskgOGXAH1hhPK9ZROHE1BzbgC1uIAcUz9MaGOY6P65wwnLA6KY5BYIRNEQDRUAj5QTqS1KLgs0OQ8VCz7jAKI449ZL_wc4tHa5x79GiDIcIZ63vupLijXe5WxhITkeN3eYeYevmXTtb8hcIn7KFVpk3Yw8ilvpoj6du6QcIePtq1-JzX2T6l35IU9GYxjexXzbRJF4YVpA50su_RovYgV80cXMiBkZR77AmrFsVsnTyhOkepq8c6nFB3qIVEB0ZDh31KthRD0OII0oPU0kuu5N8YOVxwMSC8SD_Ar-Zu8dLj4_8fo6OjU7gG7tw8TnQqaLnDbp1NfvmGFQ5NntJv8QM98eoMMRpYnpT3FCr5f5OWKJGEB8ZZ1oimSvkem3SfdX3a5JVID6Iu2SGvDnWLl01pe_g_xOm10yIIrnwaHJWwI-4WzBDAQ9iwNW5YCJxD4Pc0XRNJmFMtU6o4Iw5fRoOAZTHM2ktFmOil7iiGhbRC4Q7-GFDTdzvrBSQU7FJ_19dF-jmvMvbjHL0egAX2fhmkGKBHL4YF7Qv6v0bzwmT6KiaIxchka-UTf_eBQslAsQIKbjNUD1CpBi0XzxTt5IEdrHH0q3kJXyiWOirNuFJfR2zw9hKmdtYr65Hxf5RFK7bS1zx13CMlCR-STXLIOuyDPU-UJnbwu9SCeHtRKjDQe8QRTE2pIMCxiQoHSpxmN2AXC9illrq7rL6nxb-FqstFyv_RtikOhLaiDko0C9rI5aC4R0tcHwJ8MwC5X7rJmhMGPn4h5lUKLI7mtKEi1pZusZfRkYc3Oa8RGTwER6O91DMuQAzsYiJXxELBGoHOLexB1rbyafAgBqm6UMpdpF7I8fuB_C1ybLNa8KouU5YhpnuRVWmblUValKJn2OXY7ZuNka9-D0tJcD8_gREUYHSkYGHUqyKkYCxAK7cpEes0RyXzSZrZqfMl7kZun7GjwbfQXRizplnaUImvnezQxtkcvoLwj8feodkvqCPfajxRK3cVPR9FzqLtmte3Zm8tu7jwM1dXZntHd-ndRlwYOPK9meFoAz9hwiraIPruhBrO6JfApykxM62dRE3ZjNwlo499qFb_Td12ly4i_n8L6OJ_AvRB5Lzq6zLt-qZM93nP07qty1R0JYoy3zPeVG8ATe_wW0wNb6Lw3SBsglUcPy9WaZrFHIRLvlVoR9DmJXDFivRN5FqYfYN3VqL5ypQXS27cE9xLDcgrCUuB8u3S5FVRclWT8FDEEuV10FszLgk3Qhm7eBdhUZhxmn3oUdrZh8hdonQFB5Uk30b6--Bynlj3Otvv4HPgbK7P8M-Z-rDZLTXDBzIusRPMsXD02rVJDyGe1qpjDbMoKja-sa8sfloqwHD7o5B3Ib3SsuWCSEmqya5R9ajBzePI7fnS3_0R-kSHOLolZDi089PlYBsY0osfYUQxcC3dmBR3lIsu51Tn9eKJX_UpV3iiOOSwseg2a7kXiV2iXjLh9RAxO5VWJtw_EeeYfqmF-tiHbOZahTXwQupN1sQLp-uDJqyOmdcNZlZdUP0tEy07S-088o42vDr6tok3ZgcPUgcCDMlmk-TgyZCEE1eSKqEOtiN0M5LRo0ZR19B9bbXdkux7LlVE9yYIJmq7FxuETm2V95EaLRL2J4sjp95_c1ZwyzuaHQGd4FOMmGVfKiOuMRUARO0lTX9MWDXCZJynNQFa4TyxtQ_3DAPxjyGXTGjVGXr5JSAtep7rZ4oQ4N2Ja4EJy18BWAhI9pmWzzI8_IlaofyZQm2f9QMfND0M0vJO-jOnl786g7ZH68OcySIf0QHcdLdF1xQNv8HbvGJ5Vjes2t8Mt21fFn1ZH_qc7duq7yrO91XDi6pgbS344Ubesoztsyo_ZBnL8_2OXgXvsCrarupZlewzHLlUO0rPO2OfbsKNym1TN1V9E653XLj4ZUzjy3LdwqhkurG3Id-385NL9pmSzrtNipdehRvjmN7vkvITPH5w6RpIhFxwfVes39wR38xW3f7HJUg4L2W1qM_plv0rAAD__66_N0g">