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

    <tr>
        <th>Summary</th>
        <td>
            [InstCombine] Wrong add+gep canonicalization to gep+gep
        </td>
    </tr>

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

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

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

<pre>
    In a series of commits, ADD+GEP canonicalization was introduced in InstCombine:
1. https://github.com/llvm/llvm-project/commit/e13bed4c5f3544c076ce57e36d9a11eefa5a7815
2. https://github.com/llvm/llvm-project/commit/feaddc10194e54a5ef977320134956ad91591324

The combine is true, in case the GEP index size is equal to the pointer size.

In llvm LangRef it's states that the idx must be less than or equal to the pointer size [[1]](https://llvm.org/docs/LangRef.html#:~:text=%3Cidx%3E%20is%20the%20size%20of%20the%20index%20that%20used%20for%20address%20calculation%2C%20which%20must%20be%20less%20than%20or%20equal%20to%20the%20pointer%20size).

But in case the ADD overflows, the combine becomes incorrect.

As shown in [[2]](https://godbolt.org/z/e7GraTT7K), the compiler applies the transformation when the pointer size is 64 bits and the index size is 32 bits.
In [[3]](https://alive2.llvm.org/ce/z/NTVnvL), we can see a counterexample using Alive2, demonstrating why this transformation is invalid.

I think a possible fix would be to check whether the ADD instruction is guarded by the nsw.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJykVN-P4yYQ_mvIy6iRDcGOH_yQ3VxOp56qqlq1zxjGNj0MKeAkuw_92yuw95rotA9VpUgzYfA3H9_8ECHowSK2hD8RftyIOY7Ot6MII05xdJMI5aZz6rX9YkFAQK8xgOtBumnSMRD6DIfjkdCnz59-BSmss1oKo99E1M7CVQTQNnqnZokKtIUvNsRnN3XaImEHUhzKLYwxnkP6R0-EngYdx7nbSjcRejLm8m5-Onv3J8pI6GlJTugJS9ah2kneM77byaKuJPIaWaUaUZaIveCi3pecFAf6f_L0KJSSZVE2O-Q7wbFv6prRomS7hldCNSVvSkZ3pEhPehkx6ZPeCDpA9DMmnbQFKQJCHBGSWtoqvEHQb_kW_jULA9Hl8NlpG9Hn4HYB_WIhsYOvwg6_YQ-JVx0gRBExQBxFzF9qdYNpDhE6BIMhRyw4_zE-5NI_lYQf04_uH2VKSbfOD4SelJOB0NPKYDvGyRDKCDv8Tdgh4i0SdiSUs2etbsl-IpTTQods4ojZppTZcf3DeVZjPRExO3NAlZ3e-WyFUh7DgieFkbPJbZb-P-fD66jlmL2kQXa6Bd68f5f0WPIvmFmXJeIeCK0a3ZFu1lI8zfGhmIfjEdwFfW_cNU9EvGuADqWbMI2BdN6jjCvIIUAY3dUmpKUC9IMKDE51zsS1CG-p7evPXry81D8T2tzlO2uDHsT5bHRuCYTohQ2989M6jiPaH-uvA1Q76HQMIKxauuihNRnN0e3ShQtZ9gFZYfQF6fauaySurH95-d1evq6Ur5i2BQREECDdnOjgTUxngzAHbQc4ZKR0V-HkbIhexHR-HV8hjnmuHh6nk8YXYbR6n5h0zX4DAWcXgu4MQq9vcHWzUWk8ogM5ovyWZIkj-u-11CnZLN9Rh1l4hQq613zDhut2o1qmGtaIDbZlzRpalE1db8a2biQred3sGe-F6up9VZV91XR1X7F9J6qNbmlBeUHLouSsYXzbNV1T17TfFxWrGevIrsBJaPNdwo0OYca2pBVnbGNEhybkdU2pxSvkKKGpeTa-zQusm4dAdoXRIYZ_YaKOJu_5-xXMj_CHd3YAoRShTwOef1zi0cGA5yW6mb1p__MezRzT6lgfcWnpPwEAAP__ojgTUA">