RFC: ilist::reverse_iterator should have a handle to its current node

The current ilist::reverse_iterator is a typedef from std::reverse_iteratorilist::iterator. The latter is well-designed for data structures where iterators are invalidated on changes to the container (e.g., std::vector). However, its invalidation characteristics vs. its underlying iterator are unintuitive.

This comes up from time to time, most recently in a WIP patch for a loop sink pass:
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160815/383835.html

I have a patch on llvm-commits that fixes this (and I won’t repeat the commit message here):
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160822/384491.html

I’m surfacing this on llvm-dev so it gets visibility of out-of-tree users. If you have algorithms that rely on the strange invalidation semantics of std::reverse_iterator, like the patch fixes up in lib/Transforms/Scalar/LoopRerollPass.cpp, you’ll need to update your code. Unfortunately, I couldn’t find a way to catch that at runtime.

If you’re interested in testing the patch before I commit (if you don’t trust the coverage of ninja check for your bot), let me know in the review thread and I’ll try to hold off.

"Duncan P. N. Exon Smith via llvm-dev" <llvm-dev@lists.llvm.org> writes:

The current ilist::reverse_iterator is a typedef from
std::reverse_iterator<ilist::iterator>. The latter is well-designed
for data structures where iterators are invalidated on changes to the
container (e.g., std::vector). However, its invalidation
characteristics vs. its underlying iterator are unintuitive.

This comes up from time to time, most recently in a WIP patch for a
loop sink pass:
  [PATCH] D22778: Add Loop Sink pass to reverse the LICM based of basic block frequency.

I have a patch on llvm-commits that fixes this (and I won't repeat the
commit message here):
  http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20160822/384491.html

I'm surfacing this on llvm-dev so it gets visibility of out-of-tree
users. If you have algorithms that rely on the strange invalidation
semantics of std::reverse_iterator, like the patch fixes up in
lib/Transforms/Scalar/LoopRerollPass.cpp, you'll need to update your
code. Unfortunately, I couldn't find a way to catch that at runtime.

This seems reasonable to me - the new model is much easier to understand
for a list-type datastructure.