[ADT] Make filter_iterator support bidirectional iteration
authorVedant Kumar <vsk@apple.com>
Wed, 25 Apr 2018 21:50:09 +0000 (21:50 +0000)
committerVedant Kumar <vsk@apple.com>
Wed, 25 Apr 2018 21:50:09 +0000 (21:50 +0000)
commit75fda2e0a5530b72443712bd9606bbd48f884817
tree1013f47f87ff72d11d7cd3a53b14ed888614938d
parent1eeb26293d76039094406f43c7339986a622cfb0
[ADT] Make filter_iterator support bidirectional iteration

This makes it possible to reverse a filtered range. For example, here's
a way to visit memory accesses in a BasicBlock in reverse order:

    auto MemInsts = reverse(make_filter_range(BB, [](Instruction &I) {
      return isa<StoreInst>(&I) || isa<LoadInst>(&I);
    }));

    for (auto &MI : MemInsts)
      ...

To implement this functionality, I factored out forward iteration
functionality into filter_iterator_base, and added a specialization of
filter_iterator_impl which supports bidirectional iteration. Thanks to
Tim Shen, Zachary Turner, and others for suggesting this design and
providing feedback! This version of the patch supersedes the original
(https://reviews.llvm.org/D45792).

This was motivated by a problem we encountered in D45657: we'd like to
visit the non-debug-info instructions in a BasicBlock in reverse order.

Testing: check-llvm, check-clang

Differential Revision: https://reviews.llvm.org/D45853

llvm-svn: 330875
llvm/include/llvm/ADT/STLExtras.h
llvm/unittests/ADT/IteratorTest.cpp
llvm/unittests/IR/BasicBlockTest.cpp