[ADT] Introduce lazy unique iterator

[lebedev.ri]

Summary

You sometimes want to only deal with unique values of an underlying range.
Manually maintaining a set of already-dealt-with elements is cumbersome.

This introduces a unique_iterator forward iterator,
which lazily(!) tracks the elements of the range that were pointed-at already,
and skips them afterwards.

I've added some basic tests and adjusted a few places to use it.

[grandinj]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

310

using make_unique_range here, but did not remove the old "make unique logic" ?

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

310

This is correct, we are dealing with two different ranges here,
and want to only deal with unique common successors.

[dblaikie]

Yeah, not entirely sure this abstraction carries its weight. (I was going to suggest the set could be moved from the iterator into a range object (rather than using iterator_range) but then copies of the iterator wouldn't be independent (only one of them would visit a given element and the other would skip it) & then that starts to make me worry about the abstraction in general - making the iterators a bit big/expensive to copy/etc)

Perhaps there are some more use cases you could highlight/migrate to demonstrate the value?

[dblaikie]

I probably wouldn't mind an algorithm-like function, rather than an iterator (not composable, but avoids some of the harder design issues) - llvm::for_each_unique_element(R, [](const T& t) { ... });

llvm/include/llvm/ADT/UniqueRange.h

+//===- llvm/ADT/UniqueIterator.h - Iterate over unique elements -*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// An iterator adaptor that uniques the elements of given inner iterators.
+//
+// \code
+//   int A[] = { 1, 2, 3, 2 };
+//   auto R = make_unique_range(A);
+//   // R contains { 1, 2, 3 }.
+// \endcode
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_UNIQUEITERATOR_H
+#define LLVM_ADT_UNIQUEITERATOR_H
+
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/ADT/iterator_range.h"
+#include <iterator>
+#include <type_traits>
+#include <utility>
+
+namespace llvm {
+
+namespace detail {
+
+template <typename RangeT>
+using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
+
+template <typename RangeT>
+using ValueOfIterOfRange =
+    typename std::remove_cv<typename std::remove_reference<decltype(*std::begin(
+        std::declval<RangeT &>()))>::type>::type;
+
+} // end namespace detail
+
+template <typename WrappedIteratorT, typename SetT>
+class unique_iterator
+    : public iterator_adaptor_base<unique_iterator<WrappedIteratorT, SetT>,
+                                   WrappedIteratorT,
+                                   std::forward_iterator_tag> {
+  using BaseT =
+      iterator_adaptor_base<unique_iterator<WrappedIteratorT, SetT>,
+                            WrappedIteratorT, std::forward_iterator_tag>;
+
+  WrappedIteratorT End;
+  SetT Set;
+
+  void findNextUnique() {
+    while (this->I != End && !Set.insert(*this->I).second)
+      BaseT::operator++();
+  }
+
+public:
+  // Construct the iterator. The begin iterator needs to know where the end
+  // is, so that it can properly stop when it gets there.
+  unique_iterator(WrappedIteratorT Begin, WrappedIteratorT End)
+      : BaseT(Begin), End(End) {
+    findNextUnique();
+  }
+
+  using BaseT::operator++;
+
+  unique_iterator &operator++() {
+    BaseT::operator++();
+    findNextUnique();
+    return *this;
+  }
+};
+
+/// Convenience function that takes a range of elements,
+/// and return a new unique_iterator range.
+///
+/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
+/// lifetime of that temporary is not kept by the returned range object, and the
+/// temporary is going to be dropped on the floor after the make_iterator_range
+/// full expression that contains this function call.
+template <typename RangeT,
+          typename SetT = SmallSet<detail::ValueOfIterOfRange<RangeT>, 8>>
+iterator_range<unique_iterator<detail::IterOfRange<RangeT>, SetT>>
+make_unique_range(RangeT &&Range) {
+  using UniqueIteratorT = unique_iterator<detail::IterOfRange<RangeT>, SetT>;
+  return make_range(UniqueIteratorT(std::begin(std::forward<RangeT>(Range)),
+                                    std::end(std::forward<RangeT>(Range))),
+                    UniqueIteratorT(std::end(std::forward<RangeT>(Range)),
+                                    std::end(std::forward<RangeT>(Range))));
+}
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_UNIQUEITERATOR_H

llvm/lib/Analysis/ValueTracking.cpp

 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/UniqueRange.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumeBundleQueries.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"

 }
 
 static bool isNonEqualPHIs(const PHINode *PN1, const PHINode *PN2,
                            unsigned Depth, const Query &Q) {
   // Check two PHIs are in same block.
   if (PN1->getParent() != PN2->getParent())
     return false;
 
-  SmallPtrSet<const BasicBlock *, 8> VisitedBBs;
   bool UsedFullRecursion = false;
-  for (const BasicBlock *IncomBB : PN1->blocks()) {
-    if (!VisitedBBs.insert(IncomBB).second)
-      continue; // Don't reprocess blocks that we have dealt with already.
+  for (const BasicBlock *IncomBB : make_unique_range(PN1->blocks())) {
     const Value *IV1 = PN1->getIncomingValueForBlock(IncomBB);
     const Value *IV2 = PN2->getIncomingValueForBlock(IncomBB);
     const APInt *C1, *C2;
     if (match(IV1, m_APInt(C1)) && match(IV2, m_APInt(C2)) && *C1 != *C2)
       continue;
 
     // Only one pair of phi operands is allowed for full recursion.
     if (UsedFullRecursion)

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/Sequence.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/UniqueRange.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
SafeToMergeTerminators(Instruction *SI1, Instruction *SI2,
   // It is not safe to merge these two switch instructions if they have a common
   // successor, and if that successor has a PHI node, and if *that* PHI node has
   // conflicting incoming values from the two switch blocks.
   BasicBlock *SI1BB = SI1->getParent();
   BasicBlock *SI2BB = SI2->getParent();
 
   SmallPtrSet<BasicBlock *, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB));
   bool Fail = false;
-  for (BasicBlock *Succ : successors(SI2BB))
-    if (SI1Succs.count(Succ))
-      for (BasicBlock::iterator BBI = Succ->begin(); isa<PHINode>(BBI); ++BBI) {
-        PHINode *PN = cast<PHINode>(BBI);
-        if (PN->getIncomingValueForBlock(SI1BB) !=
-            PN->getIncomingValueForBlock(SI2BB)) {
-          if (FailBlocks)
-            FailBlocks->insert(Succ);
-          Fail = true;
-        }
-      }
+  for (BasicBlock *Succ : make_unique_range(successors(SI2BB))) {
+    if (!SI1Succs.count(Succ))
+      continue;
+    for (PHINode &PN : Succ->phis()) {
+      if (PN.getIncomingValueForBlock(SI1BB) !=
+          PN.getIncomingValueForBlock(SI2BB)) {
+  }
 
   return !Fail;
 }
 
 /// Update PHI nodes in Succ to indicate that there will now be entries in it
 /// from the 'NewPred' block. The values that will be flowing into the PHI nodes
 /// will be the same as those coming in from ExistPred, an existing predecessor
 /// of Succ.

llvm/unittests/ADT/IteratorTest.cpp

 //===- IteratorTest.cpp - Unit tests for iterator utilities ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/ADT/ilist.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/UniqueRange.h"
+#include "llvm/ADT/ilist.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
 template <int> struct Shadow;
 
TEST(FilterIteratorTest, ReverseFilterRange) {
   // Check that we don't skip the first element, provided it isn't filtered
   // away.
   auto IsEven = [](int N) { return N % 2 == 0; };
   auto Range4 = reverse(make_filter_range(A, IsEven));
   SmallVector<int, 4> Actual4(Range4.begin(), Range4.end());
   EXPECT_EQ((SmallVector<int, 4>{6, 4, 2, 0}), Actual4);
 }
 
+TEST(UniqueIteratorTest, BasicInt) {
+  int A[] = {0, 4, 4, 1, 2, 1, 3, 4, 3};
+  auto Range = make_unique_range(A);
+  SmallVector<int, 3> Actual(Range.begin(), Range.end());
+  EXPECT_EQ((SmallVector<int, 5>{0, 4, 1, 2, 3}), Actual);
+}
+
+TEST(UniqueIteratorTest, BasicPtr) {
+  void *A = nullptr, *B = nullptr, *C = nullptr, *D = nullptr;
+  void **Arr[] = {&A, &D, &C, &B, &A, &B, &B};
+  auto Range = make_unique_range(Arr);
+  SmallVector<void **, 3> Actual(Range.begin(), Range.end());
+  EXPECT_EQ((SmallVector<void **, 4>{&A, &D, &C, &B}), Actual);
+}
+
+TEST(UniqueIteratorTest, Lazy) {
+  SmallSet<int, 4> Referenced;
+  struct Vindictive {
+    int i;
+    SmallSet<int, 4> *Referenced;
+    bool operator<(const Vindictive &Other) const {
+      Referenced->insert(i);
+      Referenced->insert(Other.i);
+      return i < Other.i;
+    }
+    bool operator==(const Vindictive &Other) const {
+      Referenced->insert(i);
+      Referenced->insert(Other.i);
+      return i == Other.i;
+    }
+  };
+  Vindictive A[] = {
+      {0, &Referenced}, {2, &Referenced}, {3, &Referenced}, {5, &Referenced}};
+  auto Range = make_unique_range(A);
+  auto Begin = Range.begin();
+  auto End = Range.begin();
+  {
+    SmallVector<int, 4> ReferencedActual(Referenced.begin(), Referenced.end());
+    EXPECT_EQ((SmallVector<int, 4>{}), ReferencedActual);
+  }
+  ++Begin;
+  {
+    SmallVector<int, 4> ReferencedActual(Referenced.begin(), Referenced.end());
+    EXPECT_EQ((SmallVector<int, 4>{0, 2}), ReferencedActual);
+  }
+  ++Begin;
+  {
+    SmallVector<int, 4> ReferencedActual(Referenced.begin(), Referenced.end());
+    EXPECT_EQ((SmallVector<int, 4>{0, 2, 3}), ReferencedActual);
+  }
+  ++Begin;
+  {
+    SmallVector<int, 4> ReferencedActual(Referenced.begin(), Referenced.end());
+    EXPECT_EQ((SmallVector<int, 4>{0, 2, 3, 5}), ReferencedActual);
+  }
+}
+
 TEST(PointerIterator, Basic) {
   int A[] = {1, 2, 3, 4};
   pointer_iterator<int *> Begin(std::begin(A)), End(std::end(A));
   EXPECT_EQ(A, *Begin);
   ++Begin;
   EXPECT_EQ(A + 1, *Begin);
   ++Begin;
   EXPECT_EQ(A + 2, *Begin);