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

    <tr>
        <th>Summary</th>
        <td>
            GVN wrong optimization with skipped out-of-bounds accesses
        </td>
    </tr>

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

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

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

<pre>
    Please consider this function:

```llvm
define i32 @f(i1 %false, i64 %zero) {
entry:
  %a = alloca i32
  store i32 1, ptr %a
  br i1 %false, label %bb.1, label %bb.2
bb.1:
  %x = load i64, ptr %a
  store i64 %x, ptr %a
  br label %bb.2
bb.2:
  br i1 %false, label %bb.4, label %bb.3
bb.3:
  %j = getelementptr i32, ptr %a, i64 %zero
  store i32 3, ptr %j
  br label %bb.4
bb.4:
  %z = load i32, ptr %a
  ret i32 %z
}
```
This is a valid function to call with two zero arguments, in which case `%bb.1` is skipped, `%bb.3` is entered, `3` is stored to `%a`, and in `%bb.4`, `3` is then returned.

If this function is called with any other argument, the behavior is undefined. If `%false` is non-zero, `%bb.1` is entered and `%a` is accessed past its end. If `%false` is zero but `%zero` is non-zero, `%bb.3` stores past `%a`'s end.

GVN transforms this (`opt -passes=gvn`, LLVM commit 09c00b6f0463f6936be5d2100f9d47c0077700f8) to:

```llvm
define i32 @f(i1 %false, i64 %zero) {
entry:
  %a = alloca i32, align 4
  store i32 1, ptr %a, align 4
  br i1 %false, label %bb.1, label %bb.2
bb.1:
  %x = load i64, ptr %a, align 4
  store i64 %x, ptr %a, align 4
  %0 = trunc i64 %x to i32
  br label %bb.2
bb.2:
  %z = phi i32 [ %0, %bb.1 ], [ 1, %entry ]
  br i1 %false, label %bb.4, label %bb.3
bb.3:
  %j = getelementptr i32, ptr %a, i64 %zero
  store i32 3, ptr %j, align 4
  br label %bb.4
bb.4:
  ret i32 %z
}
```
If called with two zero arguments, `%bb.3` is still entered and still stores `3` to `%a`, but the load in `%bb.4` has been mis-optimized to its earlier value.

Alive agrees that this transformation is invalid: https://alive2.llvm.org/ce/z/EhdxXU

I have not fully understood yet what is happening, but at first glance, it appears that this bit in [`MemoryDependenceResults::getNonLocalPointerDepFromBB`](https://github.com/llvm/llvm-project/blob/433ca3ebbef50002bec716ef2c6d6a82db71048d/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp#L1097) is wrong:
```c++
        // This query's Size is less than the cached one. Conservatively restart
        // the query using the greater size.
        return getNonLocalPointerDepFromBB(
 QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad,
 StartBB, Result, Visited, SkipFirstBlock, IsIncomplete);
```
This assumes that querying with a greater size can only find additional possible dependencies, but it ignores that a greater size may cause dependencies to be left out if that size is greater than the memory region.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzMV01z47gR_TXQpcsqEPyQddDBslYpV3mnNplkkisINknMgAADgPLIvz4FgNJIsj27uSTrUlkm0P36A68fYe6c7DTihpRbUu4WfPK9sZv-0Miv3xa1aY6b3xRyhyCMdrJBC76XDtpJCy-NJvkDoTtCT78rmj5KHYa01GArNYLMGZCCtoTdywwIK1uuHBL2CLIqwvMrWkPYGshqmxxRe3s840Ow4UDyHXCljOAB8bTlvLEpRBYQR2-j9Wm7tnATU_EaVVip62V2uzDDxq2r8N9jeGV4E5J-L9KcSKro-we5vB-LXcT6ecLF7UJ-BsmvE_4aE-7Qo8IBtQ_JhLZd5nVzAm86ml9Yf_2giuKcQHGdwOtFx27izkYWfeIGK19nDq12N2RKj38PvJMOOBy4ks2ZguANCK4UvEjfg38xEAoBbrsp1OxihRpeeil6EIHKAXI--ooGSPdNjiM2wfK8l897qD3a895pNfanCaGTA49fj8B1E4KdUYp5_cLV96hD2ZPV2Cwvp-epvR6uYB0qwybVxvURjO_RnosL0L5HqLHnB2ls8Jh0GrlmCU_tnEniUYqvjb5Lw_b4thNztbGOH5XFtguBzmEDI3cepA-2H4WIB1BPft6K0X4SPHYmdtQl9MuerlKgyz795csn8JZr1xo7uNQzwu5JRc3o4W7kzqEj-a476Ln9z89ffgVhhkF6oGtBaV21tKjytlrnVY1lwzJK23VTrASlq9WK0vY-iJE3_2eBC5RSstNQ_J7WvbX8H8jeh-m9p4BvjQkraQT3dtLi7BXG6kLd_5BknsVm7GU6i3Ib8SPTUsVAyl18LLepeYSV8RDixp9ee9894d-X4T-usE_tldy8L6VvBNJ5qdSVcKSVeaBPyvdGKoM-BO1KxLrRTOi5gxpRwyDdnRm9HORrEtwoPdwqiTa8CSa80oYHJQ8IvLOIQRm4T_Jwlgt-Elap42uE5A_Qez-60DG2J2zPAwJbhgFfGtsRthdI2P6VsP0vffP9X_-4kmzo-QFBGw_tpNQxqq913pgGjujhJWQgHfR8HFFL3Z0q5x5aaZ2HTnEtkk54CFbcXiZeSx-bU25JRX_FwdjjDkfUDWqBf0M3KR9Tzx869J-MfjaCq9-MDMexw3FvzbANrpH699eVdtL3U70UZiBsHwUtfd2N1nxF4Qnb18rUhO2LPBc8x7rGtqSUshrFKquwZaJqKn7PmnqV0eK-ucCRwe9Bc3V00hG2v839tLUU40hY_pzR9SrIo3TwYo3ufgjviaSCsG34zLxOP6kSiJeDf09oj_GN8Vm-YkBS6GIzdWSa4KLHBozGJTwa7dAeuJcHVEew6Dy3_l3s4BqhYXJSd_G5s8g9WnDy9cS_k1d6tcPPjoPdzy5_DbBP2sUX-WwW31dGLDv0_5S-_4QvoRrC7h9D-k-6NXck_yWtrSNv3LPh4YIyg34OlYQoj5AIEv76Ip306Rrz-Zsc94F7W2XEt7Dy5J60MMOo0EfQfPvxDYw7Nw2n2YptCT1J95OrtoDgGoxWR2ilboA3jQyzxxWMxjlZK4TmxAaJ7jQYge-djtIRQ9yADvwIgk_u2jnoQo2gsPVgAkibnN3MgxPEmQpDZCNY7KTRy0WzyZt1vuYL3GQrVq6rIquyRb9pV9mqZCLLslaUpaBI21w0BWLBeZVV5UJuGGUFXWc0o2zNsmWbtRWWAkWZiYJzSgqKA5fqrCcL6dyEm4yu1utqEeXbxf--GBukC6cgVRQpwsLLgjAWJyoPt56wVO4WdhOntJ46RwqqpPPuB7yXXuEmXJHiGMGsnUn34jHNt93QqDvT3tVm0s35fucWk1Wb_1onYlFhzOe6Dhv2nwAAAP__z2BFBQ">