Merge commit '72f0976c1b91c7ba50dce4d0ad0289dc14d37f81'

Conflicts:
	lib/Target/ARM/ARMISelDAGToDAG.cpp
	lib/Target/Mips/MipsISelLowering.cpp
	lib/Target/Mips/MipsSubtarget.cpp

2 files changed, 30 insertions, 13 deletions

diff --git a/include/llvm/ADT/PackedVector.h b/include/llvm/ADT/PackedVector.h
index 2eaddc2b4e..1ae2a77e7e 100644
--- a/include/llvm/ADT/PackedVector.h
+++ b/include/llvm/ADT/PackedVector.h
@@ -19,32 +19,32 @@
 
 namespace llvm {
 
-template <typename T, unsigned BitNum, bool isSigned>
+template <typename T, unsigned BitNum, typename BitVectorTy, bool isSigned>
 class PackedVectorBase;
 
 // This won't be necessary if we can specialize members without specializing
 // the parent template.
-template <typename T, unsigned BitNum>
-class PackedVectorBase<T, BitNum, false> {
+template <typename T, unsigned BitNum, typename BitVectorTy>
+class PackedVectorBase<T, BitNum, BitVectorTy, false> {
 protected:
-  static T getValue(const llvm::BitVector &Bits, unsigned Idx) {
+  static T getValue(const BitVectorTy &Bits, unsigned Idx) {
     T val = T();
     for (unsigned i = 0; i != BitNum; ++i)
       val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
     return val;
   }
 
-  static void setValue(llvm::BitVector &Bits, unsigned Idx, T val) {
+  static void setValue(BitVectorTy &Bits, unsigned Idx, T val) {
     assert((val >> BitNum) == 0 && "value is too big");
     for (unsigned i = 0; i != BitNum; ++i)
       Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i);
   }
 };
 
-template <typename T, unsigned BitNum>
-class PackedVectorBase<T, BitNum, true> {
+template <typename T, unsigned BitNum, typename BitVectorTy>
+class PackedVectorBase<T, BitNum, BitVectorTy, true> {
 protected:
-  static T getValue(const llvm::BitVector &Bits, unsigned Idx) {
+  static T getValue(const BitVectorTy &Bits, unsigned Idx) {
     T val = T();
     for (unsigned i = 0; i != BitNum-1; ++i)
       val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
@@ -53,7 +53,7 @@ protected:
     return val;
   }
 
-  static void setValue(llvm::BitVector &Bits, unsigned Idx, T val) {
+  static void setValue(BitVectorTy &Bits, unsigned Idx, T val) {
     if (val < 0) {
       val = ~val;
       Bits.set((Idx << (BitNum-1)) + BitNum-1);
@@ -71,11 +71,12 @@ protected:
 /// @endcode
 /// will create a vector accepting values -2, -1, 0, 1. Any other value will hit
 /// an assertion.
-template <typename T, unsigned BitNum>
-class PackedVector : public PackedVectorBase<T, BitNum,
+template <typename T, unsigned BitNum, typename BitVectorTy = BitVector>
+class PackedVector : public PackedVectorBase<T, BitNum, BitVectorTy,
                                             std::numeric_limits<T>::is_signed> {
-  llvm::BitVector Bits;
-  typedef PackedVectorBase<T, BitNum, std::numeric_limits<T>::is_signed> base;
+  BitVectorTy Bits;
+  typedef PackedVectorBase<T, BitNum, BitVectorTy,
+                           std::numeric_limits<T>::is_signed> base;
 
 public:
   class reference {
diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index 791f1082c2..306e92832f 100644
--- a/include/llvm/ADT/SparseBitVector.h
+++ b/include/llvm/ADT/SparseBitVector.h
@@ -262,6 +262,22 @@ public:
   }
 };
 
+template <unsigned ElementSize>
+struct ilist_traits<SparseBitVectorElement<ElementSize> >
+  : public ilist_default_traits<SparseBitVectorElement<ElementSize> > {
+  typedef SparseBitVectorElement<ElementSize> Element;
+
+  Element *createSentinel() const { return static_cast<Element *>(&Sentinel); }
+  static void destroySentinel(Element *) {}
+
+  Element *provideInitialHead() const { return createSentinel(); }
+  Element *ensureHead(Element *) const { return createSentinel(); }
+  static void noteHead(Element *, Element *) {}
+
+private:
+  mutable ilist_half_node<Element> Sentinel;
+};
+
 template <unsigned ElementSize = 128>
 class SparseBitVector {
   typedef ilist<SparseBitVectorElement<ElementSize> > ElementList;