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

Project Infrastructure LLVM Dev List Archives
1

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.

2

"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.