Updating branches/google/stable to r176857

git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/google/stable@177040 91177308-0d34-0410-b5e6-96231b3b80d8

8 files changed, 757 insertions, 0 deletions

diff --git a/unittests/ADT/APFloatTest.cpp b/unittests/ADT/APFloatTest.cpp
index ff350a7872..278983565c 100644
--- a/unittests/ADT/APFloatTest.cpp
+++ b/unittests/ADT/APFloatTest.cpp
@@ -33,6 +33,58 @@ static std::string convertToString(double d, unsigned Prec, unsigned Pad) {
 
 namespace {
 
+TEST(APFloatTest, Denormal) {
+  APFloat::roundingMode rdmd = APFloat::rmNearestTiesToEven;
+
+  // Test single precision
+  {
+    const char *MinNormalStr = "1.17549435082228750797e-38";
+    EXPECT_FALSE(APFloat(APFloat::IEEEsingle, MinNormalStr).isDenormal());
+    EXPECT_FALSE(APFloat(APFloat::IEEEsingle, 0.0).isDenormal());
+
+    APFloat Val2(APFloat::IEEEsingle, 2.0e0);
+    APFloat T(APFloat::IEEEsingle, MinNormalStr);
+    T.divide(Val2, rdmd);
+    EXPECT_TRUE(T.isDenormal());
+  }
+
+  // Test double precision
+  {
+    const char *MinNormalStr = "2.22507385850720138309e-308";
+    EXPECT_FALSE(APFloat(APFloat::IEEEdouble, MinNormalStr).isDenormal());
+    EXPECT_FALSE(APFloat(APFloat::IEEEdouble, 0.0).isDenormal());
+
+    APFloat Val2(APFloat::IEEEdouble, 2.0e0);
+    APFloat T(APFloat::IEEEdouble, MinNormalStr);
+    T.divide(Val2, rdmd);
+    EXPECT_TRUE(T.isDenormal());
+  }
+
+  // Test Intel double-ext
+  {
+    const char *MinNormalStr = "3.36210314311209350626e-4932";
+    EXPECT_FALSE(APFloat(APFloat::x87DoubleExtended, MinNormalStr).isDenormal());
+    EXPECT_FALSE(APFloat(APFloat::x87DoubleExtended, 0.0).isDenormal());
+
+    APFloat Val2(APFloat::x87DoubleExtended, 2.0e0);
+    APFloat T(APFloat::x87DoubleExtended, MinNormalStr);
+    T.divide(Val2, rdmd);
+    EXPECT_TRUE(T.isDenormal());
+  }
+
+  // Test quadruple precision
+  {
+    const char *MinNormalStr = "3.36210314311209350626267781732175260e-4932";
+    EXPECT_FALSE(APFloat(APFloat::IEEEquad, MinNormalStr).isDenormal());
+    EXPECT_FALSE(APFloat(APFloat::IEEEquad, 0.0).isDenormal());
+
+    APFloat Val2(APFloat::IEEEquad, 2.0e0);
+    APFloat T(APFloat::IEEEquad, MinNormalStr);
+    T.divide(Val2, rdmd);
+    EXPECT_TRUE(T.isDenormal());
+  }
+}
+
 TEST(APFloatTest, Zero) {
   EXPECT_EQ(0.0f,  APFloat(0.0f).convertToFloat());
   EXPECT_EQ(-0.0f, APFloat(-0.0f).convertToFloat());
@@ -742,6 +794,32 @@ TEST(APFloatTest, convert) {
   test.convert(APFloat::IEEEdouble, APFloat::rmNearestTiesToEven, &losesInfo);
   EXPECT_EQ(4294967295.0, test.convertToDouble());
   EXPECT_FALSE(losesInfo);
+
+  test = APFloat::getSNaN(APFloat::IEEEsingle);
+  APFloat X87SNaN = APFloat::getSNaN(APFloat::x87DoubleExtended);
+  test.convert(APFloat::x87DoubleExtended, APFloat::rmNearestTiesToEven,
+               &losesInfo);
+  EXPECT_TRUE(test.bitwiseIsEqual(X87SNaN));
+  EXPECT_FALSE(losesInfo);
+
+  test = APFloat::getQNaN(APFloat::IEEEsingle);
+  APFloat X87QNaN = APFloat::getQNaN(APFloat::x87DoubleExtended);
+  test.convert(APFloat::x87DoubleExtended, APFloat::rmNearestTiesToEven,
+               &losesInfo);
+  EXPECT_TRUE(test.bitwiseIsEqual(X87QNaN));
+  EXPECT_FALSE(losesInfo);
+
+  test = APFloat::getSNaN(APFloat::x87DoubleExtended);
+  test.convert(APFloat::x87DoubleExtended, APFloat::rmNearestTiesToEven,
+               &losesInfo);
+  EXPECT_TRUE(test.bitwiseIsEqual(X87SNaN));
+  EXPECT_FALSE(losesInfo);
+
+  test = APFloat::getQNaN(APFloat::x87DoubleExtended);
+  test.convert(APFloat::x87DoubleExtended, APFloat::rmNearestTiesToEven,
+               &losesInfo);
+  EXPECT_TRUE(test.bitwiseIsEqual(X87QNaN));
+  EXPECT_FALSE(losesInfo);
 }
 
 TEST(APFloatTest, PPCDoubleDouble) {
diff --git a/unittests/ADT/APIntTest.cpp b/unittests/ADT/APIntTest.cpp
index 2a4c5b4c49..f129fa71c8 100644
--- a/unittests/ADT/APIntTest.cpp
+++ b/unittests/ADT/APIntTest.cpp
@@ -56,6 +56,14 @@ TEST(APIntTest, i33_Count) {
 #endif
 
 TEST(APIntTest, i65_Count) {
+  APInt i65(65, 0, true);
+  EXPECT_EQ(65u, i65.countLeadingZeros());
+  EXPECT_EQ(0u, i65.countLeadingOnes());
+  EXPECT_EQ(0u, i65.getActiveBits());
+  EXPECT_EQ(1u, i65.getActiveWords());
+  EXPECT_EQ(65u, i65.countTrailingZeros());
+  EXPECT_EQ(0u, i65.countPopulation());
+
   APInt i65minus(65, 0, true);
   i65minus.setBit(64);
   EXPECT_EQ(0u, i65minus.countLeadingZeros());
@@ -514,4 +522,14 @@ TEST(APIntTest, Rotate) {
   EXPECT_EQ(Rot, Big.rotr(144));
 }
 
+TEST(APIntTest, Splat) {
+  APInt ValA(8, 0x01);
+  EXPECT_EQ(ValA, APInt::getSplat(8, ValA));
+  EXPECT_EQ(APInt(64, 0x0101010101010101ULL), APInt::getSplat(64, ValA));
+
+  APInt ValB(3, 5);
+  EXPECT_EQ(APInt(4, 0xD), APInt::getSplat(4, ValB));
+  EXPECT_EQ(APInt(15, 0xDB6D), APInt::getSplat(15, ValB));
+}
+
 }
diff --git a/unittests/ADT/CMakeLists.txt b/unittests/ADT/CMakeLists.txt
index 94f7fda2a9..9aad793d8b 100644
--- a/unittests/ADT/CMakeLists.txt
+++ b/unittests/ADT/CMakeLists.txt
@@ -18,12 +18,15 @@ set(ADTSources
   IntEqClassesTest.cpp
   IntervalMapTest.cpp
   IntrusiveRefCntPtrTest.cpp
+  MapVectorTest.cpp
+  OptionalTest.cpp
   PackedVectorTest.cpp
   SCCIteratorTest.cpp
   SmallPtrSetTest.cpp
   SmallStringTest.cpp
   SmallVectorTest.cpp
   SparseBitVectorTest.cpp
+  SparseMultiSetTest.cpp
   SparseSetTest.cpp
   StringMapTest.cpp
   StringRefTest.cpp
diff --git a/unittests/ADT/MapVectorTest.cpp b/unittests/ADT/MapVectorTest.cpp
new file mode 100644
index 0000000000..11178bc15e
--- /dev/null
+++ b/unittests/ADT/MapVectorTest.cpp
@@ -0,0 +1,55 @@
+//===- unittest/ADT/MapVectorTest.cpp - MapVector unit tests ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "llvm/ADT/MapVector.h"
+#include <utility>
+
+using namespace llvm;
+
+TEST(MapVectorTest, insert_pop) {
+  MapVector<int, int> MV;
+  std::pair<MapVector<int, int>::iterator, bool> R;
+
+  R = MV.insert(std::make_pair(1, 2));
+  ASSERT_EQ(R.first, MV.begin());
+  EXPECT_EQ(R.first->first, 1);
+  EXPECT_EQ(R.first->second, 2);
+  EXPECT_TRUE(R.second);
+
+  R = MV.insert(std::make_pair(1, 3));
+  ASSERT_EQ(R.first, MV.begin());
+  EXPECT_EQ(R.first->first, 1);
+  EXPECT_EQ(R.first->second, 2);
+  EXPECT_FALSE(R.second);
+
+  R = MV.insert(std::make_pair(4, 5));
+  ASSERT_NE(R.first, MV.end());
+  EXPECT_EQ(R.first->first, 4);
+  EXPECT_EQ(R.first->second, 5);
+  EXPECT_TRUE(R.second);
+
+  EXPECT_EQ(MV.size(), 2u);
+  EXPECT_EQ(MV[1], 2);
+  EXPECT_EQ(MV[4], 5);
+
+  MV.pop_back();
+  EXPECT_EQ(MV.size(), 1u);
+  EXPECT_EQ(MV[1], 2);
+
+  R = MV.insert(std::make_pair(4, 7));
+  ASSERT_NE(R.first, MV.end());
+  EXPECT_EQ(R.first->first, 4);
+  EXPECT_EQ(R.first->second, 7);
+  EXPECT_TRUE(R.second);  
+
+  EXPECT_EQ(MV.size(), 2u);
+  EXPECT_EQ(MV[1], 2);
+  EXPECT_EQ(MV[4], 7);
+}
diff --git a/unittests/ADT/OptionalTest.cpp b/unittests/ADT/OptionalTest.cpp
new file mode 100644
index 0000000000..21e38475d3
--- /dev/null
+++ b/unittests/ADT/OptionalTest.cpp
@@ -0,0 +1,284 @@
+//===- llvm/unittest/ADT/OptionalTest.cpp - Optional unit tests -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "llvm/ADT/Optional.h"
+using namespace llvm;
+
+namespace {
+
+struct NonDefaultConstructible {
+  static unsigned CopyConstructions;
+  static unsigned Destructions;
+  static unsigned CopyAssignments;
+  explicit NonDefaultConstructible(int) {
+  }
+  NonDefaultConstructible(const NonDefaultConstructible&) {
+    ++CopyConstructions;
+  }
+  NonDefaultConstructible &operator=(const NonDefaultConstructible&) {
+    ++CopyAssignments;
+    return *this;
+  }
+  ~NonDefaultConstructible() {
+    ++Destructions;
+  }
+  static void ResetCounts() {
+    CopyConstructions = 0;
+    Destructions = 0;
+    CopyAssignments = 0;
+  }
+};
+
+unsigned NonDefaultConstructible::CopyConstructions = 0;
+unsigned NonDefaultConstructible::Destructions = 0;
+unsigned NonDefaultConstructible::CopyAssignments = 0;
+
+// Test fixture
+class OptionalTest : public testing::Test {
+};
+
+TEST_F(OptionalTest, NonDefaultConstructibleTest) {
+  Optional<NonDefaultConstructible> O;
+  EXPECT_FALSE(O);
+}
+
+TEST_F(OptionalTest, ResetTest) {
+  NonDefaultConstructible::ResetCounts();
+  Optional<NonDefaultConstructible> O(NonDefaultConstructible(3));
+  EXPECT_EQ(1u, NonDefaultConstructible::CopyConstructions);
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+  EXPECT_EQ(1u, NonDefaultConstructible::Destructions);
+  NonDefaultConstructible::ResetCounts();
+  O.reset();
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyConstructions);
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+  EXPECT_EQ(1u, NonDefaultConstructible::Destructions);
+}
+
+TEST_F(OptionalTest, InitializationLeakTest) {
+  NonDefaultConstructible::ResetCounts();
+  Optional<NonDefaultConstructible>(NonDefaultConstructible(3));
+  EXPECT_EQ(1u, NonDefaultConstructible::CopyConstructions);
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+  EXPECT_EQ(2u, NonDefaultConstructible::Destructions);
+}
+
+TEST_F(OptionalTest, CopyConstructionTest) {
+  NonDefaultConstructible::ResetCounts();
+  {
+    Optional<NonDefaultConstructible> A(NonDefaultConstructible(3));
+    EXPECT_EQ(1u, NonDefaultConstructible::CopyConstructions);
+    EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+    EXPECT_EQ(1u, NonDefaultConstructible::Destructions);
+    NonDefaultConstructible::ResetCounts();
+    Optional<NonDefaultConstructible> B(A);
+    EXPECT_EQ(1u, NonDefaultConstructible::CopyConstructions);
+    EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+    EXPECT_EQ(0u, NonDefaultConstructible::Destructions);
+    NonDefaultConstructible::ResetCounts();
+  }
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyConstructions);
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+  EXPECT_EQ(2u, NonDefaultConstructible::Destructions);
+}
+
+TEST_F(OptionalTest, ConstructingCopyAssignmentTest) {
+  NonDefaultConstructible::ResetCounts();
+  {
+    Optional<NonDefaultConstructible> A(NonDefaultConstructible(3));
+    Optional<NonDefaultConstructible> B;
+    EXPECT_EQ(1u, NonDefaultConstructible::CopyConstructions);
+    EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+    EXPECT_EQ(1u, NonDefaultConstructible::Destructions);
+    NonDefaultConstructible::ResetCounts();
+    B = A;
+    EXPECT_EQ(1u, NonDefaultConstructible::CopyConstructions);
+    EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+    EXPECT_EQ(0u, NonDefaultConstructible::Destructions);
+    NonDefaultConstructible::ResetCounts();
+  }
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyConstructions);
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+  EXPECT_EQ(2u, NonDefaultConstructible::Destructions);
+}
+
+TEST_F(OptionalTest, CopyingCopyAssignmentTest) {
+  NonDefaultConstructible::ResetCounts();
+  {
+    Optional<NonDefaultConstructible> A(NonDefaultConstructible(3));
+    Optional<NonDefaultConstructible> B(NonDefaultConstructible(4));
+    EXPECT_EQ(2u, NonDefaultConstructible::CopyConstructions);
+    EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+    EXPECT_EQ(2u, NonDefaultConstructible::Destructions);
+    NonDefaultConstructible::ResetCounts();
+    B = A;
+    EXPECT_EQ(0u, NonDefaultConstructible::CopyConstructions);
+    EXPECT_EQ(1u, NonDefaultConstructible::CopyAssignments);
+    EXPECT_EQ(0u, NonDefaultConstructible::Destructions);
+    NonDefaultConstructible::ResetCounts();
+  }
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyConstructions);
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+  EXPECT_EQ(2u, NonDefaultConstructible::Destructions);
+}
+
+TEST_F(OptionalTest, DeletingCopyAssignmentTest) {
+  NonDefaultConstructible::ResetCounts();
+  {
+    Optional<NonDefaultConstructible> A;
+    Optional<NonDefaultConstructible> B(NonDefaultConstructible(3));
+    EXPECT_EQ(1u, NonDefaultConstructible::CopyConstructions);
+    EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+    EXPECT_EQ(1u, NonDefaultConstructible::Destructions);
+    NonDefaultConstructible::ResetCounts();
+    B = A;
+    EXPECT_EQ(0u, NonDefaultConstructible::CopyConstructions);
+    EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+    EXPECT_EQ(1u, NonDefaultConstructible::Destructions);
+    NonDefaultConstructible::ResetCounts();
+  }
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyConstructions);
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+  EXPECT_EQ(0u, NonDefaultConstructible::Destructions);
+}
+
+TEST_F(OptionalTest, NullCopyConstructionTest) {
+  NonDefaultConstructible::ResetCounts();
+  {
+    Optional<NonDefaultConstructible> A;
+    Optional<NonDefaultConstructible> B;
+    EXPECT_EQ(0u, NonDefaultConstructible::CopyConstructions);
+    EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+    EXPECT_EQ(0u, NonDefaultConstructible::Destructions);
+    NonDefaultConstructible::ResetCounts();
+    B = A;
+    EXPECT_EQ(0u, NonDefaultConstructible::CopyConstructions);
+    EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+    EXPECT_EQ(0u, NonDefaultConstructible::Destructions);
+    NonDefaultConstructible::ResetCounts();
+  }
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyConstructions);
+  EXPECT_EQ(0u, NonDefaultConstructible::CopyAssignments);
+  EXPECT_EQ(0u, NonDefaultConstructible::Destructions);
+}
+
+#if LLVM_HAS_RVALUE_REFERENCES
+struct MoveOnly {
+  static unsigned MoveConstructions;
+  static unsigned Destructions;
+  static unsigned MoveAssignments;
+  int val;
+  explicit MoveOnly(int val) : val(val) {
+  }
+  MoveOnly(MoveOnly&& other) {
+    val = other.val;
+    ++MoveConstructions;
+  }
+  MoveOnly &operator=(MoveOnly&& other) {
+    val = other.val;
+    ++MoveAssignments;
+    return *this;
+  }
+  ~MoveOnly() {
+    ++Destructions;
+  }
+  static void ResetCounts() {
+    MoveConstructions = 0;
+    Destructions = 0;
+    MoveAssignments = 0;
+  }
+};
+
+unsigned MoveOnly::MoveConstructions = 0;
+unsigned MoveOnly::Destructions = 0;
+unsigned MoveOnly::MoveAssignments = 0;
+
+TEST_F(OptionalTest, MoveOnlyNull) {
+  MoveOnly::ResetCounts();
+  Optional<MoveOnly> O;
+  EXPECT_EQ(0u, MoveOnly::MoveConstructions);
+  EXPECT_EQ(0u, MoveOnly::MoveAssignments);
+  EXPECT_EQ(0u, MoveOnly::Destructions);
+}
+
+TEST_F(OptionalTest, MoveOnlyConstruction) {
+  MoveOnly::ResetCounts();
+  Optional<MoveOnly> O(MoveOnly(3));
+  EXPECT_TRUE((bool)O);
+  EXPECT_EQ(3, O->val);
+  EXPECT_EQ(1u, MoveOnly::MoveConstructions);
+  EXPECT_EQ(0u, MoveOnly::MoveAssignments);
+  EXPECT_EQ(1u, MoveOnly::Destructions);
+}
+
+TEST_F(OptionalTest, MoveOnlyMoveConstruction) {
+  Optional<MoveOnly> A(MoveOnly(3));
+  MoveOnly::ResetCounts();
+  Optional<MoveOnly> B(std::move(A));
+  EXPECT_FALSE((bool)A);
+  EXPECT_TRUE((bool)B);
+  EXPECT_EQ(3, B->val);
+  EXPECT_EQ(1u, MoveOnly::MoveConstructions);
+  EXPECT_EQ(0u, MoveOnly::MoveAssignments);
+  EXPECT_EQ(1u, MoveOnly::Destructions);
+}
+
+TEST_F(OptionalTest, MoveOnlyAssignment) {
+  MoveOnly::ResetCounts();
+  Optional<MoveOnly> O;
+  O = MoveOnly(3);
+  EXPECT_TRUE((bool)O);
+  EXPECT_EQ(3, O->val);
+  EXPECT_EQ(1u, MoveOnly::MoveConstructions);
+  EXPECT_EQ(0u, MoveOnly::MoveAssignments);
+  EXPECT_EQ(1u, MoveOnly::Destructions);
+}
+
+TEST_F(OptionalTest, MoveOnlyInitializingAssignment) {
+  Optional<MoveOnly> A(MoveOnly(3));
+  Optional<MoveOnly> B;
+  MoveOnly::ResetCounts();
+  B = std::move(A);
+  EXPECT_FALSE((bool)A);
+  EXPECT_TRUE((bool)B);
+  EXPECT_EQ(3, B->val);
+  EXPECT_EQ(1u, MoveOnly::MoveConstructions);
+  EXPECT_EQ(0u, MoveOnly::MoveAssignments);
+  EXPECT_EQ(1u, MoveOnly::Destructions);
+}
+
+TEST_F(OptionalTest, MoveOnlyNullingAssignment) {
+  Optional<MoveOnly> A;
+  Optional<MoveOnly> B(MoveOnly(3));
+  MoveOnly::ResetCounts();
+  B = std::move(A);
+  EXPECT_FALSE((bool)A);
+  EXPECT_FALSE((bool)B);
+  EXPECT_EQ(0u, MoveOnly::MoveConstructions);
+  EXPECT_EQ(0u, MoveOnly::MoveAssignments);
+  EXPECT_EQ(1u, MoveOnly::Destructions);
+}
+
+TEST_F(OptionalTest, MoveOnlyAssigningAssignment) {
+  Optional<MoveOnly> A(MoveOnly(3));
+  Optional<MoveOnly> B(MoveOnly(4));
+  MoveOnly::ResetCounts();
+  B = std::move(A);
+  EXPECT_FALSE((bool)A);
+  EXPECT_TRUE((bool)B);
+  EXPECT_EQ(3, B->val);
+  EXPECT_EQ(0u, MoveOnly::MoveConstructions);
+  EXPECT_EQ(1u, MoveOnly::MoveAssignments);
+  EXPECT_EQ(1u, MoveOnly::Destructions);
+}
+#endif
+
+} // end anonymous namespace
+
diff --git a/unittests/ADT/SparseMultiSetTest.cpp b/unittests/ADT/SparseMultiSetTest.cpp
new file mode 100644
index 0000000000..032990e4bc
--- /dev/null
+++ b/unittests/ADT/SparseMultiSetTest.cpp
@@ -0,0 +1,235 @@
+//===------ ADT/SparseSetTest.cpp - SparseSet unit tests -  -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SparseMultiSet.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+typedef SparseMultiSet<unsigned> USet;
+
+// Empty set tests.
+TEST(SparseMultiSetTest, EmptySet) {
+  USet Set;
+  EXPECT_TRUE(Set.empty());
+  EXPECT_EQ(0u, Set.size());
+
+  Set.setUniverse(10);
+
+  // Lookups on empty set.
+  EXPECT_TRUE(Set.find(0) == Set.end());
+  EXPECT_TRUE(Set.find(9) == Set.end());
+
+  // Same thing on a const reference.
+  const USet &CSet = Set;
+  EXPECT_TRUE(CSet.empty());
+  EXPECT_EQ(0u, CSet.size());
+  EXPECT_TRUE(CSet.find(0) == CSet.end());
+  USet::const_iterator I = CSet.find(5);
+  EXPECT_TRUE(I == CSet.end());
+}
+
+// Single entry set tests.
+TEST(SparseMultiSetTest, SingleEntrySet) {
+  USet Set;
+  Set.setUniverse(10);
+  USet::iterator I = Set.insert(5);
+  EXPECT_TRUE(I != Set.end());
+  EXPECT_TRUE(*I == 5);
+
+  EXPECT_FALSE(Set.empty());
+  EXPECT_EQ(1u, Set.size());
+
+  EXPECT_TRUE(Set.find(0) == Set.end());
+  EXPECT_TRUE(Set.find(9) == Set.end());
+
+  EXPECT_FALSE(Set.contains(0));
+  EXPECT_TRUE(Set.contains(5));
+
+  // Extra insert.
+  I = Set.insert(5);
+  EXPECT_TRUE(I != Set.end());
+  EXPECT_TRUE(I == ++Set.find(5));
+  I--;
+  EXPECT_TRUE(I == Set.find(5));
+
+  // Erase non-existent element.
+  I = Set.find(1);
+  EXPECT_TRUE(I == Set.end());
+  EXPECT_EQ(2u, Set.size());
+  EXPECT_EQ(5u, *Set.find(5));
+
+  // Erase iterator.
+  I = Set.find(5);
+  EXPECT_TRUE(I != Set.end());
+  I = Set.erase(I);
+  EXPECT_TRUE(I != Set.end());
+  I = Set.erase(I);
+  EXPECT_TRUE(I == Set.end());
+  EXPECT_TRUE(Set.empty());
+}
+
+// Multiple entry set tests.
+TEST(SparseMultiSetTest, MultipleEntrySet) {
+  USet Set;
+  Set.setUniverse(10);
+
+  Set.insert(5);
+  Set.insert(5);
+  Set.insert(5);
+  Set.insert(3);
+  Set.insert(2);
+  Set.insert(1);
+  Set.insert(4);
+  EXPECT_EQ(7u, Set.size());
+
+  // Erase last element by key.
+  EXPECT_TRUE(Set.erase(Set.find(4)) == Set.end());
+  EXPECT_EQ(6u, Set.size());
+  EXPECT_FALSE(Set.contains(4));
+  EXPECT_TRUE(Set.find(4) == Set.end());
+
+  // Erase first element by key.
+  EXPECT_EQ(3u, Set.count(5));
+  EXPECT_TRUE(Set.find(5) != Set.end());
+  EXPECT_TRUE(Set.erase(Set.find(5)) != Set.end());
+  EXPECT_EQ(5u, Set.size());
+  EXPECT_EQ(2u, Set.count(5));
+
+  Set.insert(6);
+  Set.insert(7);
+  EXPECT_EQ(7u, Set.size());
+
+  // Erase tail by iterator.
+  EXPECT_TRUE(Set.getTail(6) == Set.getHead(6));
+  USet::iterator I = Set.erase(Set.find(6));
+  EXPECT_TRUE(I == Set.end());
+  EXPECT_EQ(6u, Set.size());
+
+  // Erase tails by iterator.
+  EXPECT_EQ(2u, Set.count(5));
+  I = Set.getTail(5);
+  I = Set.erase(I);
+  EXPECT_TRUE(I == Set.end());
+  --I;
+  EXPECT_EQ(1u, Set.count(5));
+  EXPECT_EQ(5u, *I);
+  I = Set.erase(I);
+  EXPECT_TRUE(I == Set.end());
+  EXPECT_EQ(0u, Set.count(5));
+
+  Set.insert(8);
+  Set.insert(8);
+  Set.insert(8);
+  Set.insert(8);
+  Set.insert(8);
+
+  // Erase all the 8s
+  EXPECT_EQ(5, std::distance(Set.getHead(8), Set.end()));
+  Set.eraseAll(8);
+  EXPECT_EQ(0, std::distance(Set.getHead(8), Set.end()));
+
+  // Clear and resize the universe.
+  Set.clear();
+  EXPECT_EQ(0u, Set.size());
+  EXPECT_FALSE(Set.contains(3));
+  Set.setUniverse(1000);
+
+  // Add more than 256 elements.
+  for (unsigned i = 100; i != 800; ++i)
+    Set.insert(i);
+
+  for (unsigned i = 0; i != 10; ++i)
+    Set.eraseAll(i);
+
+  for (unsigned i = 100; i != 800; ++i)
+    EXPECT_EQ(1u, Set.count(i));
+
+  EXPECT_FALSE(Set.contains(99));
+  EXPECT_FALSE(Set.contains(800));
+  EXPECT_EQ(700u, Set.size());
+}
+
+// Test out iterators
+TEST(SparseMultiSetTest, Iterators) {
+  USet Set;
+  Set.setUniverse(100);
+
+  Set.insert(0);
+  Set.insert(1);
+  Set.insert(2);
+  Set.insert(0);
+  Set.insert(1);
+  Set.insert(0);
+
+  USet::RangePair RangePair = Set.equal_range(0);
+  USet::iterator B = RangePair.first;
+  USet::iterator E = RangePair.second;
+
+  // Move the iterators around, going to end and coming back.
+  EXPECT_EQ(3, std::distance(B, E));
+  EXPECT_EQ(B, --(--(--E)));
+  EXPECT_EQ(++(++(++E)), Set.end());
+  EXPECT_EQ(B, --(--(--E)));
+  EXPECT_EQ(++(++(++E)), Set.end());
+
+  // Insert into the tail, and move around again
+  Set.insert(0);
+  EXPECT_EQ(B, --(--(--(--E))));
+  EXPECT_EQ(++(++(++(++E))), Set.end());
+  EXPECT_EQ(B, --(--(--(--E))));
+  EXPECT_EQ(++(++(++(++E))), Set.end());
+
+  // Erase a tail, and move around again
+  USet::iterator Erased = Set.erase(Set.getTail(0));
+  EXPECT_EQ(Erased, E);
+  EXPECT_EQ(B, --(--(--E)));
+
+  USet Set2;
+  Set2.setUniverse(11);
+  Set2.insert(3);
+  EXPECT_TRUE(!Set2.contains(0));
+  EXPECT_TRUE(!Set.contains(3));
+
+  EXPECT_EQ(Set2.getHead(3), Set2.getTail(3));
+  EXPECT_EQ(Set2.getHead(0), Set2.getTail(0));
+  B = Set2.find(3);
+  EXPECT_EQ(Set2.find(3), --(++B));
+}
+
+struct Alt {
+  unsigned Value;
+  explicit Alt(unsigned x) : Value(x) {}
+  unsigned getSparseSetIndex() const { return Value - 1000; }
+};
+
+TEST(SparseMultiSetTest, AltStructSet) {
+  typedef SparseMultiSet<Alt> ASet;
+  ASet Set;
+  Set.setUniverse(10);
+  Set.insert(Alt(1005));
+
+  ASet::iterator I = Set.find(5);
+  ASSERT_TRUE(I != Set.end());
+  EXPECT_EQ(1005u, I->Value);
+
+  Set.insert(Alt(1006));
+  Set.insert(Alt(1006));
+  I = Set.erase(Set.find(6));
+  ASSERT_TRUE(I != Set.end());
+  EXPECT_EQ(1006u, I->Value);
+  I = Set.erase(Set.find(6));
+  ASSERT_TRUE(I == Set.end());
+
+  EXPECT_TRUE(Set.contains(5));
+  EXPECT_FALSE(Set.contains(6));
+}
+} // namespace
diff --git a/unittests/ADT/TripleTest.cpp b/unittests/ADT/TripleTest.cpp
index 7c3ab97389..b402896390 100644
--- a/unittests/ADT/TripleTest.cpp
+++ b/unittests/ADT/TripleTest.cpp
@@ -407,6 +407,11 @@ TEST(TripleTest, getOSVersion) {
   unsigned Major, Minor, Micro;
 
   T = Triple("i386-apple-darwin9");
+  EXPECT_TRUE(T.isMacOSX());
+  EXPECT_FALSE(T.isiOS());
+  EXPECT_FALSE(T.isArch16Bit());
+  EXPECT_TRUE(T.isArch32Bit());
+  EXPECT_FALSE(T.isArch64Bit());
   T.getMacOSXVersion(Major, Minor, Micro);
   EXPECT_EQ((unsigned)10, Major);
   EXPECT_EQ((unsigned)5, Minor);
@@ -417,6 +422,11 @@ TEST(TripleTest, getOSVersion) {
   EXPECT_EQ((unsigned)0, Micro);
 
   T = Triple("x86_64-apple-darwin9");
+  EXPECT_TRUE(T.isMacOSX());
+  EXPECT_FALSE(T.isiOS());
+  EXPECT_FALSE(T.isArch16Bit());
+  EXPECT_FALSE(T.isArch32Bit());
+  EXPECT_TRUE(T.isArch64Bit());
   T.getMacOSXVersion(Major, Minor, Micro);
   EXPECT_EQ((unsigned)10, Major);
   EXPECT_EQ((unsigned)5, Minor);
@@ -427,6 +437,11 @@ TEST(TripleTest, getOSVersion) {
   EXPECT_EQ((unsigned)0, Micro);
 
   T = Triple("x86_64-apple-macosx");
+  EXPECT_TRUE(T.isMacOSX());
+  EXPECT_FALSE(T.isiOS());
+  EXPECT_FALSE(T.isArch16Bit());
+  EXPECT_FALSE(T.isArch32Bit());
+  EXPECT_TRUE(T.isArch64Bit());
   T.getMacOSXVersion(Major, Minor, Micro);
   EXPECT_EQ((unsigned)10, Major);
   EXPECT_EQ((unsigned)4, Minor);
@@ -437,6 +452,11 @@ TEST(TripleTest, getOSVersion) {
   EXPECT_EQ((unsigned)0, Micro);
 
   T = Triple("x86_64-apple-macosx10.7");
+  EXPECT_TRUE(T.isMacOSX());
+  EXPECT_FALSE(T.isiOS());
+  EXPECT_FALSE(T.isArch16Bit());
+  EXPECT_FALSE(T.isArch32Bit());
+  EXPECT_TRUE(T.isArch64Bit());
   T.getMacOSXVersion(Major, Minor, Micro);
   EXPECT_EQ((unsigned)10, Major);
   EXPECT_EQ((unsigned)7, Minor);
@@ -447,6 +467,11 @@ TEST(TripleTest, getOSVersion) {
   EXPECT_EQ((unsigned)0, Micro);
 
   T = Triple("armv7-apple-ios");
+  EXPECT_FALSE(T.isMacOSX());
+  EXPECT_TRUE(T.isiOS());
+  EXPECT_FALSE(T.isArch16Bit());
+  EXPECT_TRUE(T.isArch32Bit());
+  EXPECT_FALSE(T.isArch64Bit());
   T.getMacOSXVersion(Major, Minor, Micro);
   EXPECT_EQ((unsigned)10, Major);
   EXPECT_EQ((unsigned)4, Minor);
@@ -457,6 +482,11 @@ TEST(TripleTest, getOSVersion) {
   EXPECT_EQ((unsigned)0, Micro);
 
   T = Triple("armv7-apple-ios5.0");
+  EXPECT_FALSE(T.isMacOSX());
+  EXPECT_TRUE(T.isiOS());
+  EXPECT_FALSE(T.isArch16Bit());
+  EXPECT_TRUE(T.isArch32Bit());
+  EXPECT_FALSE(T.isArch64Bit());
   T.getMacOSXVersion(Major, Minor, Micro);
   EXPECT_EQ((unsigned)10, Major);
   EXPECT_EQ((unsigned)4, Minor);
diff --git a/unittests/ADT/ilistTest.cpp b/unittests/ADT/ilistTest.cpp
index 83eaa31981..0c0cd0fd56 100644
--- a/unittests/ADT/ilistTest.cpp
+++ b/unittests/ADT/ilistTest.cpp
@@ -8,6 +8,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/ilist.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ilist_node.h"
 #include "gtest/gtest.h"
 #include <ostream>
@@ -21,6 +22,7 @@ struct Node : ilist_node<Node> {
 
   Node() {}
   Node(int _Value) : Value(_Value) {}
+  ~Node() { Value = -1; }
 };
 
 TEST(ilistTest, Basic) {
@@ -41,4 +43,56 @@ TEST(ilistTest, Basic) {
   EXPECT_EQ(1, ConstList.back().getPrevNode()->Value);
 }
 
+TEST(ilistTest, SpliceOne) {
+  ilist<Node> List;
+  List.push_back(1);
+
+  // The single-element splice operation supports noops.
+  List.splice(List.begin(), List, List.begin());
+  EXPECT_EQ(1u, List.size());
+  EXPECT_EQ(1, List.front().Value);
+  EXPECT_TRUE(llvm::next(List.begin()) == List.end());
+
+  // Altenative noop. Move the first element behind itself.
+  List.push_back(2);
+  List.push_back(3);
+  List.splice(llvm::next(List.begin()), List, List.begin());
+  EXPECT_EQ(3u, List.size());
+  EXPECT_EQ(1, List.front().Value);
+  EXPECT_EQ(2, llvm::next(List.begin())->Value);
+  EXPECT_EQ(3, List.back().Value);
+}
+
+TEST(ilistTest, UnsafeClear) {
+  ilist<Node> List;
+
+  // Before even allocating a sentinel.
+  List.clearAndLeakNodesUnsafely();
+  EXPECT_EQ(0u, List.size());
+
+  // Empty list with sentinel.
+  ilist<Node>::iterator E = List.end();
+  List.clearAndLeakNodesUnsafely();
+  EXPECT_EQ(0u, List.size());
+  // The sentinel shouldn't change.
+  EXPECT_TRUE(E == List.end());
+
+  // List with contents.
+  List.push_back(1);
+  ASSERT_EQ(1u, List.size());
+  Node *N = List.begin();
+  EXPECT_EQ(1, N->Value);
+  List.clearAndLeakNodesUnsafely();
+  EXPECT_EQ(0u, List.size());
+  ASSERT_EQ(1, N->Value);
+  delete N;
+
+  // List is still functional.
+  List.push_back(5);
+  List.push_back(6);
+  ASSERT_EQ(2u, List.size());
+  EXPECT_EQ(5, List.front().Value);
+  EXPECT_EQ(6, List.back().Value);
+}
+
 }