Index: include/llvm/ADT/SmallBitVector.h
===================================================================
--- include/llvm/ADT/SmallBitVector.h
+++ include/llvm/ADT/SmallBitVector.h
@@ -242,7 +242,7 @@
       uintptr_t Bits = getSmallBits();
       if (Bits == 0)
         return -1;
-      return NumBaseBits - countLeadingZeros(Bits);
+      return NumBaseBits - countLeadingZeros(Bits) - 1;
     }
     return getPointer()->find_last();
   }
@@ -265,7 +265,9 @@
         return -1;
 
       uintptr_t Bits = getSmallBits();
-      return NumBaseBits - countLeadingOnes(Bits);
+      // Set unused bits.
+      Bits |= ~uintptr_t(0) << getSmallSize();
+      return NumBaseBits - countLeadingOnes(Bits) - 1;
     }
     return getPointer()->find_last_unset();
   }
@@ -487,10 +489,17 @@
   bool operator==(const SmallBitVector &RHS) const {
     if (size() != RHS.size())
       return false;
-    if (isSmall())
+    if (isSmall() && RHS.isSmall())
       return getSmallBits() == RHS.getSmallBits();
-    else
+    else  if (!isSmall() && !RHS.isSmall())
       return *getPointer() == *RHS.getPointer();
+    else {
+      for (size_t i = 0, e = size(); i != e; ++i) {
+        if ((*this)[i] != RHS[i])
+          return false;
+      }
+      return true;
+    }
   }
 
   bool operator!=(const SmallBitVector &RHS) const {
@@ -498,16 +507,19 @@
   }
 
   // Intersection, union, disjoint union.
+  // FIXME BitVector::operator&= does not resize the LHS but this does
   SmallBitVector &operator&=(const SmallBitVector &RHS) {
     resize(std::max(size(), RHS.size()));
-    if (isSmall())
+    if (isSmall() && RHS.isSmall())
       setSmallBits(getSmallBits() & RHS.getSmallBits());
-    else if (!RHS.isSmall())
+    else if (!isSmall() && !RHS.isSmall())
       getPointer()->operator&=(*RHS.getPointer());
     else {
-      SmallBitVector Copy = RHS;
-      Copy.resize(size());
-      getPointer()->operator&=(*Copy.getPointer());
+      size_t i, e;
+      for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
+        (*this)[i] = test(i) && RHS.test(i);
+      for (e = size(); i != e; ++i)
+        reset(i);
     }
     return *this;
   }
@@ -547,28 +559,26 @@
 
   SmallBitVector &operator|=(const SmallBitVector &RHS) {
     resize(std::max(size(), RHS.size()));
-    if (isSmall())
+    if (isSmall() && RHS.isSmall())
       setSmallBits(getSmallBits() | RHS.getSmallBits());
-    else if (!RHS.isSmall())
+    else if (!isSmall() && !RHS.isSmall())
       getPointer()->operator|=(*RHS.getPointer());
     else {
-      SmallBitVector Copy = RHS;
-      Copy.resize(size());
-      getPointer()->operator|=(*Copy.getPointer());
+      for (size_t i = 0, e = RHS.size(); i != e; ++i)
+        (*this)[i] = test(i) || RHS.test(i);
     }
     return *this;
   }
 
   SmallBitVector &operator^=(const SmallBitVector &RHS) {
     resize(std::max(size(), RHS.size()));
-    if (isSmall())
+    if (isSmall() && RHS.isSmall())
       setSmallBits(getSmallBits() ^ RHS.getSmallBits());
-    else if (!RHS.isSmall())
+    else if (!isSmall() && !RHS.isSmall())
       getPointer()->operator^=(*RHS.getPointer());
     else {
-      SmallBitVector Copy = RHS;
-      Copy.resize(size());
-      getPointer()->operator^=(*Copy.getPointer());
+      for (size_t i = 0, e = RHS.size(); i != e; ++i)
+        (*this)[i] = test(i) != RHS.test(i);
     }
     return *this;
   }
Index: unittests/ADT/BitVectorTest.cpp
===================================================================
--- unittests/ADT/BitVectorTest.cpp
+++ unittests/ADT/BitVectorTest.cpp
@@ -234,6 +234,7 @@
   EXPECT_EQ(99, A.find_next_unset(98));
 
   // Also test with a vector that is small enough to fit in 1 word.
+  A.clear();
   A.resize(20);
   A.set(3);
   A.set(4);
@@ -431,6 +432,8 @@
   A &= B;
   EXPECT_FALSE(A.test(2));
   EXPECT_FALSE(A.test(7));
+  EXPECT_TRUE(A.test(4));
+  EXPECT_TRUE(A.test(5));
   EXPECT_EQ(2U, A.count());
   EXPECT_EQ(50U, A.size());
 
@@ -444,6 +447,242 @@
   EXPECT_EQ(100U, A.size());
 }
 
+// Test SmallBitVector operations with mixed big/small representations
+TYPED_TEST(BitVectorTest, MixedBigSmall) {
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Small &= Big;
+    EXPECT_TRUE(Small.test(0));
+    EXPECT_EQ(1u, Small.count());
+    // FIXME BitVector and SmallBitVector behave differently here.
+    // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size())
+    // but BitVector does not.
+    //EXPECT_EQ(20u, Small.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Big &= Small;
+    EXPECT_TRUE(Big.test(0));
+    EXPECT_EQ(1u, Big.count());
+    // FIXME BitVector and SmallBitVector behave differently here.
+    // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size())
+    // but BitVector does not.
+    //EXPECT_EQ(20u, Big.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Small |= Big;
+    EXPECT_TRUE(Small.test(0));
+    EXPECT_TRUE(Small.test(1));
+    EXPECT_TRUE(Small.test(2));
+    EXPECT_TRUE(Small.test(16));
+    EXPECT_EQ(4u, Small.count());
+    EXPECT_EQ(20u, Small.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Big |= Small;
+    EXPECT_TRUE(Big.test(0));
+    EXPECT_TRUE(Big.test(1));
+    EXPECT_TRUE(Big.test(2));
+    EXPECT_TRUE(Big.test(16));
+    EXPECT_EQ(4u, Big.count());
+    EXPECT_EQ(20u, Big.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Small ^= Big;
+    EXPECT_TRUE(Small.test(1));
+    EXPECT_TRUE(Small.test(2));
+    EXPECT_TRUE(Small.test(16));
+    EXPECT_EQ(3u, Small.count());
+    EXPECT_EQ(20u, Small.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Big ^= Small;
+    EXPECT_TRUE(Big.test(1));
+    EXPECT_TRUE(Big.test(2));
+    EXPECT_TRUE(Big.test(16));
+    EXPECT_EQ(3u, Big.count());
+    EXPECT_EQ(20u, Big.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Small.reset(Big);
+    EXPECT_TRUE(Small.test(1));
+    EXPECT_EQ(1u, Small.count());
+    EXPECT_EQ(10u, Small.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+    Big.set(2);
+    Big.set(16);
+
+    Big.reset(Small);
+    EXPECT_TRUE(Big.test(2));
+    EXPECT_TRUE(Big.test(16));
+    EXPECT_EQ(2u, Big.count());
+    EXPECT_EQ(20u, Big.size());
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(10);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+
+    EXPECT_FALSE(Big == Small);
+    EXPECT_FALSE(Small == Big);
+    Big.set(1);
+    EXPECT_TRUE(Big == Small);
+    EXPECT_TRUE(Small == Big);
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(20);
+    Small.resize(10);
+
+    Small.set(0);
+    Big.set(1);
+
+    EXPECT_FALSE(Small.anyCommon(Big));
+    EXPECT_FALSE(Big.anyCommon(Small));
+    Big.set(0);
+    EXPECT_TRUE(Small.anyCommon(Big));
+    EXPECT_TRUE(Big.anyCommon(Small));
+  }
+
+  {
+    TypeParam Big;
+    TypeParam Small;
+
+    Big.reserve(100);
+    Big.resize(10);
+    Small.resize(10);
+
+    Small.set(0);
+    Small.set(1);
+    Big.set(0);
+
+    EXPECT_TRUE(Small.test(Big));
+    EXPECT_FALSE(Big.test(Small));
+    Big.set(1);
+    EXPECT_FALSE(Small.test(Big));
+    EXPECT_FALSE(Big.test(Small));
+  }
+}
+
 TYPED_TEST(BitVectorTest, ProxyIndex) {
   TypeParam Vec(3);
   EXPECT_TRUE(Vec.none());