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

    <tr>
        <th>Summary</th>
        <td>
            c++ reverse_iterator: std::find iterates using ptrtoint, instead of ptrs
        </td>
    </tr>

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

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

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

<pre>
    Hi

TLDR: SCEV's `getPointerBase` cannot deal with iterations of integer type (for good reason), but `std::find` over an `std::vector` with reverse iterators seems to use an integer (representing a pointer) to iterate over the vector elements at `O2`, which makes it much harder to look through the otherwise simple recurrence in the std::find loop.

When experimenting with some loop optimizations, I saw that std::find in the below snippet would iterate using `ptrtoint`-ed iterators at `-O2`, instead of `ptr` like I expected, and like the forward iterator does. I ran into a problem when trying to use the SCEV interface on this "integer", e.g., `SCEV.getPointerBase` bails out when the type of its argument is not a pointer.

Reproducer on trunk:
```C++
#include <vector>
#include <cstdint>
#include <algorithm>

std::vector<uint64_t> vec;

bool func(uint64_t num) {        
    auto first = vec.rbegin();
    auto last = vec.rend(); 
    auto res = std::find(++first, last, num);

    return res != last;        
}
```

As you can see [here in godbolt](https://godbolt.org/z/xoa3Mv9Pz), the iterating "pointer" of the find loop is initialized as follows (at `-O2`):
```llvm
define dso_local noundef zeroext i1 @func(unsigned long)(i64 noundef %num) local_unnamed_addr {
entry:
  %0 = load ptr, ptr getelementptr inbounds ({ { ptr, ptr, ptr } }, ptr @vec, i64 0, i32 0, i32 1), align 8
  %1 = load ptr, ptr @vec, align 8
  %incdec.ptr.i.i = getelementptr inbounds i64, ptr %0, i64 -1
  %2 = ptrtoint ptr %incdec.ptr.i.i to i64
  %3 = ptrtoint ptr %1 to i64
  %sub.ptr.sub.i.i.i.i.i = sub i64 %2, %3
 %cmp79.i.i.i = icmp sgt i64 %sub.ptr.sub.i.i.i.i.i, 31
  br i1 %cmp79.i.i.i, label %for.body.lr.ph.i.i.i, label %for.end.i.i.i

for.body.lr.ph.i.i.i:
  %shr.i.i.i = lshr i64 %sub.ptr.sub.i.i.i.i.i, 5
  br label %for.body.i.i.i

for.body.i.i.i:
  %4 = phi ptr [ %incdec.ptr.i.i, %for.body.lr.ph.i.i.i ], [ %incdec.ptr.i.i.i44.i.i.i, %if.end16.i.i.i ]
 %5 = phi i64 [ %2, %for.body.lr.ph.i.i.i ], [ %11, %if.end16.i.i.i ]
 %__trip_count.080.i.i.i = phi i64 [ %shr.i.i.i, %for.body.lr.ph.i.i.i ], [ %dec.i.i.i, %if.end16.i.i.i ]
  %6 = inttoptr i64 %5 to ptr
 %incdec.ptr.i.i.i.i.i.i = getelementptr inbounds i64, ptr %6, i64 -1
  %7 = load i64, ptr %incdec.ptr.i.i.i.i.i.i, align 8
  %cmp.i.i.i.i = icmp eq i64 %7, %num
; ....
```
The `++first` expression is evaluated into `%incdec.ptr.i.i`, and then `ptrtoint`-ed in `%2` to compute the trip count. This also happens at `-O1`. However, the phinode `%5`, which is semantically the iterating pointer, is of type `i64`, and gets `inttoptr`-converted in the body of the loop to access the vector elements. This seems to differ from the behavior at `-O1`, which keeps the phinode as a pointer type (initialized with `%incdec.ptr.i.i`), and does not rely on `inttoptr` inside the loop. 

The SCEV expression for the `%5` phinode is `{(-8 + (ptrtoint i64* %incdec.ptr.i.i to i64)),+,-32}<nw><%for.body.i.i.i>`, which is an AddRec on which `ScalarEvolution::getPointerBase` immediately bails:
```C++
/// Transitively follow the chain of pointer-type operands until reaching a
/// SCEV that does not have a single pointer operand. This returns a
/// SCEVUnknown pointer for well-formed pointer-type expressions, but corner
/// cases do exist.
const SCEV *ScalarEvolution::getPointerBase(const SCEV *V) {
  // A pointer operand may evaluate to a nonpointer expression, such as null.
  if (!V->getType()->isPointerTy())
    return V;
// ...
}
```

As the comment explains, this might be a corner case. I looked for another interface to look through this construct, but the core issue seems to be that the base of the AddRec is an Add expression (`(-8 + (ptrtoint i64* %incdec.ptr.i.i to i64))`), for which SCEV (or any analysis for that matter) needs to know which side is the pointer and which side is the integer (offset). In this case, I could hardcode a fix for it because the offset is a constant, but more generally, why does the iteration happen using an integer in the first place? 

FYI: as visible in the godbolt, a forward iteration using std::find does not suffer from the same issue. This made me think that std::find using reverse_iterators was simply coded this way, but I could not immediately find source-level `ptrtoint` casts, and the fact that `O1` does not do this (even for reverse_iterators) also throws me off.

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJycWFtv47oR_jXMyyCCTPn6kIfE2eAs0KIHp9st-hTQ4sjiCUWqJGWv99cXQ0qyfFmcoLtJnEic4Vy-uQrv1d4gPrHFC1u8Pogu1NY9CemUEOZPUdqdf9hZeXr6TbH8leXP6ee3v73-wYpn-Of2y3fGVx7YMt9j-N0qE9C9CI9smUMpjLEBJAoNRxVqUAGdCMoaD7YCOrtHB-HUIjC-rqyDvbUSHApvDeMbxrew6wJx90Gy4pkVz5UykpjbAzoQ5uLdActgHb2N1zk8oPPYX2udB4_YeAgWOo9EPIjA-Nph69CjCcrsQUCbVGF8Q8cTB0yXhhoh3QSosUETPIgo5D84W-Yk9LFWZQ2N-EAPKkDTlTXUwkmitqCt_YBQO9vt68jNhhrdUXkEr5pWIzgsO-fQlAjKxCMX-hOHNps65N81GsAfLTrV9DpEE3jbYDwNtg2qUT-T-UnGr-DFEUItwhXz_sYdansEb1TbYoCj7bQc7dB5uoEt8za4QJZiy_wR5cTSySCPo0WU8QGFJL8nMvKSVh8IX6PcZUBJ5wRpR49JhMq6o3BntiAt-gy-gku-s-QoZ3caGziSBYI7kWC9g4kFITS62VWiRLCkm_LAOO99zzinezHbZ_TJljmRZLdo3gmlPdgu9FfVmJBLSCYEuH1HpgflgVA_QujCT39g66zsSnRRFNeZD7J8OrHM09eW8Rf6Sk95oUypO4nAim2P8OLLvZelD5J8cf-t0HvrVKib8_v48zp6im2nTFjO34kRAZ0VL9PzO2s1VJ0pGV8PJ8F0DYUKW71A_y8dpt9EFyxUyvkArHgljpnb4V4ZxtcU5AP78awW06No5HjwmqtDHw9eZgc6TQaMd5JTiSF9Jimv9CFmDkPnTGLHZ8QxkhRX2rDV65WrpoyePZxsR1mP8gywxUuNLgbw3sqd1YEtXhlf1yG0nqTlb4y_9a8y6_aMv_1k_O2HFcXfD5vff_YJkIDWJ06KOc7H1MQJezFOhpxA4FNGBSW0-okShIfKam2PpNf6MiY3t8DT-tCkRxIrZRCkt-_alkKDsZ2RWMFPdBZ_BFAzYPN8gIGJZYRkMPso9lot5yMN44seH5HXe2eMaFC-CykdQSZdiSa40ygTEFUenautkEAZg2_pA_YY-rxLfymzo2uiggQ_-j4fHmjY6pW-xz_nOQGb8tJyDilBFfz8y6y3vdBqb2A9EWl2V6Qzv1sKZUqJZdYGl6lMRfJfaKCW85EhX-SDeI-zCTceGQxpdzh7dQdVrOV8QlXcpZrdHvTdLnKhTzX8TyHW7aI0JENMlHxR9ISML8qmXW0mp1XZtOD3YSC5y5fYFKNyOxdBdcErBe8ONT2vrMuoF8m0y9r6FwfQyP7NJDLvUl4gzdduIr32tftLyRcTwW9l_LUMd26fJ_fUKnlm8XLr097k9zSBmFe29-kyNZ-fZabXFdlotpzQjl5cjHJE5RM__vmrZ7NPXPL-Hpxq30vbmZDl63xi96ubR6d8XgLS_FPa0stlgqoJwcY4TA5fUFRQbI8SX1t0IvGnInl5N5JX50xyefz-dfeTS9m0F_LEuMP_DrqsejNQ-k1YLF4gy7Lsbhn7ViPE0nAunsucujOH3itrqLrgQehOBOr1qP-Kx6-hmjo-6uQCdUp32kTTE1IlInOXtmm7kDo2QgckdMA36tWE9hZq0bZozn3ljC3zDH6zR-rxhzLZ1spY2SuxWFw044q6_0aYoEqh9emqrI41dUsHqazGoWSZk2vO-uwxxFlnwAyJUlpzQJcskhpnK09DZY5FmfrUskTv740OvZLjZCJVVaGDytmmb8NrcVDWXWh-VusDsfUXygt_7j3H2WraFMTB4JeO2wy6Uq8dO1mH-kTd6qXe1NEriaOWGVwMiEPrPUEPzXehnnpnlFlFq1IrwNePa2Ccgnk91qsYH3dCcahfJDTJHZG7fSw4lfpia47U6hbb27xcfLnGhjDwLOUfWJKm6SmNAqXQwn05WN3R3JR6zNvRQDUNSiUCGSqOCX_Z07-lL_jmhPEqqAORplYt2qishTIEot6Rj2nUaNEJyi-dCUrTnFzWcVy9ZhtNH0e70Yu1OCAIoMFN44iPnmMPwtQG-_v8_mU-jD2akZTceUStHyvrGpSXkp7d7ochvrTOoLvmXAqPHqQF_KF86PNSaY0PSQnGnz_jBL6-pPneTyPnVBlve75WHBpxGnNaDFQw1gyHzlqQEp6meOHBdFpnA2NVxcaTz74_suLLHsO3U4tpXqEHyvdSfjv1Qwzf3Iwd388TSRLznKD_auCIWLFNHDzxR6uFSgaPQ26j9nWAHbk9GT9am-Znbe0HyuhCYeL2YTIj324olIdoXteVYXBnupnmG-87POevHSbgxdwlPA6ZsI-uMdSmmYFMQ_H4_8f-mLkiKmP49lBYRx1PIIzQJ698n4ZEgEaEfsNjEGUUnhDek8fkpvrU2uOBAHP7drJEslXlMTC-yeBrv2koIzy38JVqmpZxDVTGPA2V-hGlUeSkUgwri8QkWiqZXZjR6g1ZfI8GHRWxlMFOKcgnBc2avl72i5rJpquvUWkcb7UokRVvF6n77T9fWfFMQD8or3Z6XEENUyzVh6vVDN2YrrpcJY3Zx3eXVc2LpkdOn3oaIREaMoAyH_e2Uol9v9J7Py-ajsKnrdkJyKwyWf0oToPJBsOTGNNEHbl627kSHzUeqH-_aFTIc8FPOhmoRBmSaGyZxzp8VlDaYbG0xgOmYncjLGEtdjMUWkdP-tqq6mP9QT4VclNsxAM-zZab-Ww1L4rZQ_20Wc6LYr1eLkQld1isSr4speCrUuJqkc83D-qJ57zIN_l6NlusF7NsvsLFfM0XOaLkq0qweY6NUDqjAT-zbv8QTf-0XKzmxUMcXnxcAXNu8Jj8wjhni9cH90Q0j7tu79k818oHf-YSVND4VKbSdqMuoehqs5jWh7535mjsy_1gG5x_6Jx-utqUqFB3u6y0DeNvcVORPh5bZ_9ESkxvUXDP-FtU7H8BAAD__2kNIbc">