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

    <tr>
        <th>Summary</th>
        <td>
            Clang does not optimize some redundant checks in std::find with a bounds-checked iterator 
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            clang
      </td>
    </tr>

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

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

<pre>
    For some context, see https://github.com/llvm/llvm-project/pull/78876. This bug is about:

> There's also something funny going on with std::ranges::find which I have not yet figured out yet, but I suspect there are some further missed optimization opportunities.

I've now figured that out. 😄 Here is a minimal version of the checks that Clang cannot delete.
```
void minimized(const uint64_t *data, size_t size) {
    const uint64_t *begin = data;
    const uint64_t *end = data + size;
    const uint64_t *iter = begin;
    while (iter != end) {
        if (*iter == 42) {
            break;
        }
        ++iter;
    }

    // This should be very easy to delete. `++iter` cannot overflow,
    // so the compiler should know that `begin <= iter`.
    assert(begin <= iter);

    // This is trickier. I believe the compiler first needs to
    // learn that `begin <= end`. See
    // https://github.com/llvm/llvm-project/issues/78784 for how
    // it could learn this. From there, I think the loop structure
    // should be sufficient. That said, if I stick
    // `assert(begin <= end)` at the top of the function, it
    // could not delete this check, so there may be more going on.
    assert(iter <= end);
}
```

These asserts show up as a consequence of `__rewrap_iter`, as part of how `std::find` determines whether to specialize with `memchr` and friends. In the process of doing that specialization, libc++ needs compute `begin + (iter - begin)`. In principle, that could be replaced with `iter`, but a bounds-checked iterator will emit the above asserts to do it.

See also this godbolt, which contains more extensive examples and some of the intermediate steps to get to that minimal version:
https://godbolt.org/z/6Khxj9d7W

I think #78784 may be needed to delete the second assert. I'm a little surprised it's not deleting the first though.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJykVk1v4zgP_jXKhZjAUVLbOeQwbd_gLfY4A-yxkCU65lSWvBKdTPvrF5KdtJl0B1isEcQfoPj58CFVjHRwiDtxdy_uHhdq5M6HnVFHMg26RePN627vA0TfI2jvGH-ykA8QEaFjHqJYfxVyL-T-QNyNzVL7Xsi9tcfz7csQ_A_ULOR-GK0Vcl_VdVUu4XtHEZrxABRBNX7kpKp4FMX5f_0_-N5hQCGrCMpGn73gjtwB2tG5Vzj49OwdnIg7iGySivXXoNwB4_TckjNw6kh38ASdOiI4z_CKDC0dxoAG_JjfU1TNyPAEcYwDagZOxkEFnKJvx5C-QE8xpmMDU09visk78MPgA4-OmDAuP0bxJGSVjZ4uBrlTnKwuQewLsd2LbS3qDfw_WUu5gJ4c9crCEUPM2tvkC-gO9Uucjj9Y5Q6glUvRGLTIeDZbFvMvvx49mUkhvaERstbeRYaRHJebZwYhvxrFKteU3vCZ803ILYjqflIBAHB7qsEDORDrR8jn178VRmcuoiDk_WTk92eIMeRD2dKV8KkjiyBkPcnIVRJDZ27cThe1SfKDwiS8kZ_KpqsJqF6uzKVLVI-_fJD3Qt4nnVeyF7kPn3J_THiPnR-tgQZTcV8BVXwF9ucKQirbu96yOFfYHzG01p-EfLjRG_2EDt8PZDGcTbwkyGWsiLI4F-shxT7rXr5rUjFiYCHrWzm5vYT3eUQUgQPpF8KwhCdo0BIe8dqllkJkcIgmAvsbPRZVcJ_7mopaFkv4hnhz7F_zD8U4YswMVNUbaH2Azp9u9BKDzik8-0VxCfvg-4kRUqs8pa_uJUdpvR8gchg1j-HWy_eKx7FtSRM6TuSnGKIik7RRm1iHSb_cnBZl8XlxJrQniKjMVMB-OBNFOzqdaCnr5hudU3DvxJEjnNgl04Cfma9Xr8nt3ge8MO1noJn76qNbF8hcuuGalab_7x1GnPXk1jjBOIBKFJjoAP8a0WlMUYmyeH4OeApqeJ7hm1xVEQYVOEmkw6IsLjMg8X7KjkHG0JPDCKcOM4Gzh0TwpCy94TQ6RFn02Osu95xyBtpA6ExcwpPLKR2C1xhjsmRyKjJaL2rUOd2WGj118Az31AMj4wdgy_sLc32ZuS0XMtsaAjlNg80oyzb0GT4BB6s0movHHxKRBpeCxo_OxC-5kmhy_yr2AU5kLWBPE1BU44_vWU_k44H4amh9Q5wGbkbGwZvG2zwgp0Ga9gBFLk7QwJ-MLtIxPal-sBhzBvPMnAFJLhUBDSlGiIxDtntATrcc5S8j77IK_NLjkydLHw5C7t-E3Jd_dD9_bE3159XMnbtTyPXU6TOSU0XS_PXvwEeIqL0zcz6WkOZ1DwosMdvUs2EIFHM28x5yaZsJBDhzG3d-PHTLhdmtzXa9VQvcrarirl7V5d1m0e1qvcG21k1dad1synJdbJuqVsWmqTYrVa4WtJOF3BQruSrKdXG3Wa63VbG5w7KuVmu9amuxKbBXZJeJ1FIGFpnOdlVd13JhVYM25jVOSp2WAyFl2ujCLpNgMx6i2BSWIsd3DUxscTftEsbjFN282MxbT0AzOqMcn9cPcnDVZBMc_xl8izHY3X-h6rqWfwcAAP__74VX1Q">