[ADT] Add a leader_iterator to EquivalenceClasses

[anemet]

Summary

Recently we had a bug that was caught during the review where the
isLeader check was mistakenly omitted from the usual pattern of
traversing an EC:

for (EquivalenceClasses<int>::iterator I = EC.begin(), E = EC.end();
     I != E; ++I) {
  if (!I->isLeader()) continue // <----------- this line
  for (EquivalenceClasses<int>::member_iterator MI = EC.member_begin(I);
       MI != EC.member_end(); ++MI)
    ...

I don't think that anything bad really happens if the check is omitted
other than some overhead but that made me think if we could have an
iterator in the outer loop that only traverses the leaders/classes:

for (EquivalenceClasses<int>::leader_iterator I = EC.leader_begin(),
       E = EC.leader_end(); I != E; ++I) {
  for (EquivalenceClasses<int>::member_iterator MI = EC.member_begin(I);
       MI != EC.member_end(); ++MI)
    ...

EC internally uses a set, so leader_iterator is built on top of the
set::iterator. In addition, it also needs the end iterator to avoid
over-running the set when looking for the leader.

Let me know if this seems like a good idea and then I will update the
patch with unit tests.

[dblaikie]

(shooting from the hip a bit - only glanced at the code)

It'd be good to have a generic filtering iterator abstraction as we already
have a few uses for such a thing special cased & could refactor those out.
(I'd have to go looking to find the existing examples if none come to
mind/are already known to you)

It could take a function pointer as a non-type template parameter, or a
lambda (ugh, stateless lambdas still aren't default constructible, and I'm
not sure you can derive from them, so I don't know if you can do the empty
base class optimization with them... )

include/llvm/ADT/EquivalenceClasses.h

 // Generic implementation of equivalence classes through the use Tarjan's
 // efficient union-find algorithm.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_EQUIVALENCECLASSES_H
 #define LLVM_ADT_EQUIVALENCECLASSES_H
 
+#include "llvm/ADT/iterator.h"
 #include "llvm/Support/DataTypes.h"
 #include <cassert>
 #include <cstddef>
 #include <set>
 
 namespace llvm {
 
 /// EquivalenceClasses - This represents a collection of equivalence classes and
public:
 
   /// member_* Iterate over the members of an equivalence class.
   ///
   class member_iterator;
   member_iterator member_begin(iterator I) const {
     // Only leaders provide anything to iterate over.
     return member_iterator(I->isLeader() ? &*I : nullptr);
   }
+  class leader_iterator;
+  member_iterator member_begin(leader_iterator I) const {
+    return member_iterator(&*I);
+  }
   member_iterator member_end() const {
     return member_iterator(nullptr);
   }
 
+  /// Iterate over the leaders (i.e. the equivalence classes).
+  leader_iterator leader_begin() const {
+    // Only leaders provide anything to iterate over.
+    return leader_iterator(TheMapping.begin(), TheMapping.end());
+  }
+  leader_iterator leader_end() const {
+    return leader_iterator(TheMapping.end(), TheMapping.end());
+  }
+
   /// findValue - Return an iterator to the specified value.  If it does not
   /// exist, end() is returned.
   iterator findValue(const ElemTy &V) const {
     return TheMapping.find(V);
   }
 
   /// getLeaderValue - Return the leader for the specified value that is in the
   /// set.  It is an error to call this method for a value that is not yet in
public:
 
     bool operator==(const member_iterator &RHS) const {
       return Node == RHS.Node;
     }
     bool operator!=(const member_iterator &RHS) const {
       return Node != RHS.Node;
     }
   };
+
+  class leader_iterator
+      : public iterator_facade_base<leader_iterator, std::forward_iterator_tag,
+                                    const ECValue> {
+    typedef iterator_facade_base<leader_iterator, std::forward_iterator_tag,
+                                 const ECValue> super;
+
+    iterator Iter;
+    iterator End;
+
+    void findLeader() {
+      for (; Iter != End; ++Iter)
+        if (Iter->isLeader())
+          break;
+    }
+
+  public:
+    typedef size_t size_type;
+    typedef typename super::pointer pointer;
+    typedef typename super::reference reference;
+
+    explicit leader_iterator() {}
+    explicit leader_iterator(iterator First, iterator Last)
+        : Iter(First), End(Last) {
+      // Ensure that Iter is pointing at the first leader.
+      findLeader();
+    }
+
+    leader_iterator &operator++() {
+      assert(Iter != End && "++'d off the end of the list!");
+      ++Iter;
+      // If this is not a leader, keep going.
+      findLeader();
+      return *this;
+    }
+
+    reference operator*() const {
+      assert(Iter != End && "Dereferencing end()!");
+      return *Iter;
+    }
+
+    bool operator==(const leader_iterator &RHS) const {
+      return Iter == RHS.Iter;
+    }
+  };
 };
 
 } // End llvm namespace
 
 #endif