[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

1 files changed, 9 insertions, 0 deletions

diff --git a/llvm/unittests/IR/BasicBlockTest.cpp b/llvm/unittests/IR/BasicBlockTest.cpp
index 5e3b11e434b..07ed997f638 100644
--- a/llvm/unittests/IR/BasicBlockTest.cpp
+++ b/llvm/unittests/IR/BasicBlockTest.cpp
@@ -69,6 +69,15 @@ TEST(BasicBlockTest, PhiRange) {
   CI = BB->phis().begin();
   EXPECT_NE(CI, BB->phis().end());
 
+  // Test that filtering iterators work with basic blocks.
+  auto isPhi = [](Instruction &I) { return isa<PHINode>(&I); };
+  auto Phis = make_filter_range(*BB, isPhi);
+  auto ReversedPhis = reverse(make_filter_range(*BB, isPhi));
+  EXPECT_EQ(std::distance(Phis.begin(), Phis.end()), 3);
+  EXPECT_EQ(&*Phis.begin(), P1);
+  EXPECT_EQ(std::distance(ReversedPhis.begin(), ReversedPhis.end()), 3);
+  EXPECT_EQ(&*ReversedPhis.begin(), P3);
+
   // And iterate a const range.
   for (const auto &PN : const_cast<const BasicBlock *>(BB.get())->phis()) {
     EXPECT_EQ(BB.get(), PN.getIncomingBlock(0));