Index: include/llvm/ADT/SmallPtrSet.h
===================================================================
--- include/llvm/ADT/SmallPtrSet.h
+++ include/llvm/ADT/SmallPtrSet.h
@@ -69,11 +69,11 @@
                       const SmallPtrSetImplBase &that);
   SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize,
                       SmallPtrSetImplBase &&that);
-  explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) :
-    SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize) {
+  explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize)
+      : SmallArray(SmallStorage), CurArray(SmallStorage),
+        CurArraySize(SmallSize), NumElements(0) {
     assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
            "Initial size must be a power of two!");
-    clear();
   }
   ~SmallPtrSetImplBase() {
     if (!isSmall())
@@ -86,9 +86,14 @@
   size_type size() const { return NumElements; }
 
   void clear() {
+    if (isSmall()) {
+      NumElements = 0;
+      return;
+    }
+
     // If the capacity of the array is huge, and the # elements used is small,
     // shrink the array.
-    if (!isSmall() && NumElements*4 < CurArraySize && CurArraySize > 32)
+    if (NumElements*4 < CurArraySize && CurArraySize > 32)
       return shrink_and_clear();
 
     // Fill the array with empty markers.
@@ -177,12 +182,13 @@
 /// instances of SmallPtrSetIterator.
 class SmallPtrSetIteratorImpl {
 protected:
+  const SmallPtrSetImplBase *Set;
   const void *const *Bucket;
-  const void *const *End;
 
 public:
-  explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E)
-    : Bucket(BP), End(E) {
+  explicit SmallPtrSetIteratorImpl(const SmallPtrSetImplBase *Set,
+                                   const void *const *BP)
+    : Set(Set), Bucket(BP) {
     AdvanceIfNotValid();
   }
 
@@ -194,15 +200,19 @@
   }
 
 protected:
-  /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket
-  /// that is.   This is guaranteed to stop because the end() bucket is marked
-  /// valid.
+  /// If the current bucket isn't valid, advance to a bucket that is or stop
+  /// at the end.
   void AdvanceIfNotValid() {
-    assert(Bucket <= End);
-    while (Bucket != End &&
+    const void *const *End = Set->CurArray +
+      (Set->isSmall() ? Set->NumElements : Set->CurArraySize);
+    assert(Bucket <= Set->CurArray + Set->CurArraySize);
+
+    while (Bucket < End &&
            (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
             *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
       ++Bucket;
+    if (Bucket >= End)
+      Bucket = Set->CurArray + Set->CurArraySize;
   }
 };
 
@@ -218,13 +228,13 @@
   typedef std::ptrdiff_t            difference_type;
   typedef std::forward_iterator_tag iterator_category;
 
-  explicit SmallPtrSetIterator(const void *const *BP, const void *const *E)
-    : SmallPtrSetIteratorImpl(BP, E) {}
+  explicit SmallPtrSetIterator(const SmallPtrSetImplBase *Set,
+                               const void *const *BP)
+    : SmallPtrSetIteratorImpl(Set, BP) {}
 
   // Most methods provided by baseclass.
 
   const PtrTy operator*() const {
-    assert(Bucket < End);
     return PtrTraits::getFromVoidPointer(const_cast<void*>(*Bucket));
   }
 
@@ -293,13 +303,16 @@
   /// Ptr. The bool component of the returned pair is true if and only if the
   /// insertion takes place, and the iterator component of the pair points to
   /// the element equal to Ptr.
+  /// All other iterators to this set are invalidated.
   std::pair<iterator, bool> insert(PtrType Ptr) {
     auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr));
-    return std::make_pair(iterator(p.first, CurArray + CurArraySize), p.second);
+    return std::make_pair(iterator(this, p.first), p.second);
   }
 
   /// erase - If the set contains the specified pointer, remove it and return
   /// true, otherwise return false.
+  /// Invalidate any iterator to the removed element, other iterators remain
+  /// valid.
   bool erase(PtrType Ptr) {
     return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
   }
@@ -316,10 +329,10 @@
   }
 
   inline iterator begin() const {
-    return iterator(CurArray, CurArray+CurArraySize);
+    return iterator(this, CurArray);
   }
   inline iterator end() const {
-    return iterator(CurArray+CurArraySize, CurArray+CurArraySize);
+    return iterator(this, CurArray+CurArraySize);
   }
 };