9 files changed, 295 insertions, 30 deletions

diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h
index 45108c8cc5198..b9f2d83322639 100644
--- a/include/llvm/ADT/BitVector.h
+++ b/include/llvm/ADT/BitVector.h
@@ -307,15 +307,17 @@ public:
   }
 
   BitVector &operator|=(const BitVector &RHS) {
-    assert(Size == RHS.Size && "Illegal operation!");
-    for (unsigned i = 0; i < NumBitWords(size()); ++i)
+    if (size() < RHS.size())
+      resize(RHS.size());
+    for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
       Bits[i] |= RHS.Bits[i];
     return *this;
   }
 
   BitVector &operator^=(const BitVector &RHS) {
-    assert(Size == RHS.Size && "Illegal operation!");
-    for (unsigned i = 0; i < NumBitWords(size()); ++i)
+    if (size() < RHS.size())
+      resize(RHS.size());
+    for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
       Bits[i] ^= RHS.Bits[i];
     return *this;
   }
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 8b161eae73fb5..735090627c3ef 100644
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -359,7 +359,7 @@ private:
     BucketT *OldBuckets = Buckets;
 
     // Double the number of buckets.
-    while (NumBuckets <= AtLeast)
+    while (NumBuckets < AtLeast)
       NumBuckets <<= 1;
     NumTombstones = 0;
     Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets));
diff --git a/include/llvm/ADT/DenseSet.h b/include/llvm/ADT/DenseSet.h
index 89f55caa95475..0898b968aca91 100644
--- a/include/llvm/ADT/DenseSet.h
+++ b/include/llvm/ADT/DenseSet.h
@@ -41,8 +41,8 @@ public:
     return TheMap.count(V);
   }
 
-  void erase(const ValueT &V) {
-    TheMap.erase(V);
+  bool erase(const ValueT &V) {
+    return TheMap.erase(V);
   }
 
   DenseSet &operator=(const DenseSet &RHS) {
diff --git a/include/llvm/ADT/ImmutableIntervalMap.h b/include/llvm/ADT/ImmutableIntervalMap.h
new file mode 100644
index 0000000000000..f33fb1eb0a82f
--- /dev/null
+++ b/include/llvm/ADT/ImmutableIntervalMap.h
@@ -0,0 +1,238 @@
+//===--- ImmutableIntervalMap.h - Immutable (functional) map  ---*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the ImmutableIntervalMap class.
+//
+//===----------------------------------------------------------------------===//
+#include "llvm/ADT/ImmutableMap.h"
+
+namespace llvm {
+
+class Interval {
+private:
+  uint64_t Start;
+  uint64_t End;
+
+public:
+  Interval(uint64_t S, uint64_t E) : Start(S), End(E) {}
+
+  uint64_t getStart() const { return Start; }
+  uint64_t getEnd() const { return End; }
+};
+
+template <typename T>
+struct ImutIntervalInfo {
+  typedef const std::pair<Interval, T> value_type;
+  typedef const value_type &value_type_ref;
+  typedef const Interval key_type;
+  typedef const Interval &key_type_ref;
+  typedef const T data_type;
+  typedef const T &data_type_ref;
+
+  static key_type_ref KeyOfValue(value_type_ref V) {
+    return V.first;
+  }
+
+  static data_type_ref DataOfValue(value_type_ref V) {
+    return V.second;
+  }
+
+  static bool isEqual(key_type_ref L, key_type_ref R) {
+    return L.getStart() == R.getStart() && L.getEnd() == R.getEnd();
+  }
+
+  static bool isDataEqual(data_type_ref L, data_type_ref R) {
+    return ImutContainerInfo<T>::isEqual(L,R);
+  }
+
+  static bool isLess(key_type_ref L, key_type_ref R) {
+    // Assume L and R does not overlap.
+    if (L.getStart() < R.getStart()) {
+      assert(L.getEnd() < R.getStart());
+      return true;
+    } else if (L.getStart() == R.getStart()) {
+      assert(L.getEnd() == R.getEnd());
+      return false;
+    } else {
+      assert(L.getStart() > R.getEnd());
+      return false;
+    }
+  }
+
+  static bool isContainedIn(key_type_ref K, key_type_ref L) {
+    if (K.getStart() >= L.getStart() && K.getEnd() <= L.getEnd())
+      return true;
+    else
+      return false;
+  }
+
+  static void Profile(FoldingSetNodeID &ID, value_type_ref V) {
+    ID.AddInteger(V.first.getStart());
+    ID.AddInteger(V.first.getEnd());
+    ImutProfileInfo<T>::Profile(ID, V.second);
+  }
+};
+
+template <typename ImutInfo>
+class ImutIntervalAVLFactory : public ImutAVLFactory<ImutInfo> {
+  typedef ImutAVLTree<ImutInfo> TreeTy;
+  typedef typename ImutInfo::value_type     value_type;
+  typedef typename ImutInfo::value_type_ref value_type_ref;
+  typedef typename ImutInfo::key_type       key_type;
+  typedef typename ImutInfo::key_type_ref   key_type_ref;
+  typedef typename ImutInfo::data_type      data_type;
+  typedef typename ImutInfo::data_type_ref  data_type_ref;
+
+public:
+  ImutIntervalAVLFactory(BumpPtrAllocator &Alloc) 
+    : ImutAVLFactory<ImutInfo>(Alloc) {}
+
+  TreeTy *Add(TreeTy *T, value_type_ref V) {
+    T = Add_internal(V,T);
+    this->MarkImmutable(T);
+    return T;
+  }
+
+  TreeTy *Find(TreeTy *T, key_type_ref K) {
+    if (!T)
+      return NULL;
+
+    key_type_ref CurrentKey = ImutInfo::KeyOfValue(this->Value(T));
+
+    if (ImutInfo::isContainedIn(K, CurrentKey))
+      return T;
+    else if (ImutInfo::isLess(K, CurrentKey))
+      return Find(this->Left(T), K);
+    else
+      return Find(this->Right(T), K);
+  }
+
+private:
+  TreeTy *Add_internal(value_type_ref V, TreeTy *T) {
+    key_type_ref K = ImutInfo::KeyOfValue(V);
+    T = RemoveAllOverlaps(T, K);
+    if (this->isEmpty(T))
+      return this->CreateNode(NULL, V, NULL);
+
+    assert(!T->isMutable());
+
+    key_type_ref KCurrent = ImutInfo::KeyOfValue(this->Value(T));
+
+    if (ImutInfo::isLess(K, KCurrent))
+      return this->Balance(Add_internal(V, this->Left(T)), this->Value(T), this->Right(T));
+    else
+      return this->Balance(this->Left(T), this->Value(T), Add_internal(V, this->Right(T)));
+  }
+
+  // Remove all overlaps from T.
+  TreeTy *RemoveAllOverlaps(TreeTy *T, key_type_ref K) {
+    bool Changed;
+    do {
+      Changed = false;
+      T = RemoveOverlap(T, K, Changed);
+      this->MarkImmutable(T);
+    } while (Changed);
+
+    return T;
+  }
+
+  // Remove one overlap from T.
+  TreeTy *RemoveOverlap(TreeTy *T, key_type_ref K, bool &Changed) {
+    if (!T)
+      return NULL;
+    Interval CurrentK = ImutInfo::KeyOfValue(this->Value(T));
+
+    // If current key does not overlap the inserted key.
+    if (CurrentK.getStart() > K.getEnd())
+      return this->Balance(RemoveOverlap(this->Left(T), K, Changed), this->Value(T), this->Right(T));
+    else if (CurrentK.getEnd() < K.getStart())
+      return this->Balance(this->Left(T), this->Value(T), RemoveOverlap(this->Right(T), K, Changed));
+
+    // Current key overlaps with the inserted key.
+    // Remove the current key.
+    Changed = true;
+    data_type_ref OldData = ImutInfo::DataOfValue(this->Value(T));
+    T = this->Remove_internal(CurrentK, T);
+    // Add back the unoverlapped part of the current key.
+    if (CurrentK.getStart() < K.getStart()) {
+      if (CurrentK.getEnd() <= K.getEnd()) {
+        Interval NewK(CurrentK.getStart(), K.getStart()-1);
+        return Add_internal(std::make_pair(NewK, OldData), T);
+      } else {
+        Interval NewK1(CurrentK.getStart(), K.getStart()-1);
+        T = Add_internal(std::make_pair(NewK1, OldData), T); 
+
+        Interval NewK2(K.getEnd()+1, CurrentK.getEnd());
+        return Add_internal(std::make_pair(NewK2, OldData), T);
+      }
+    } else {
+      if (CurrentK.getEnd() > K.getEnd()) {
+        Interval NewK(K.getEnd()+1, CurrentK.getEnd());
+        return Add_internal(std::make_pair(NewK, OldData), T);
+      } else
+        return T;
+    }
+  }
+};
+
+/// ImmutableIntervalMap maps an interval [start, end] to a value. The intervals
+/// in the map are guaranteed to be disjoint.
+template <typename ValT>
+class ImmutableIntervalMap 
+  : public ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> > {
+
+  typedef typename ImutIntervalInfo<ValT>::value_type      value_type;
+  typedef typename ImutIntervalInfo<ValT>::value_type_ref  value_type_ref;
+  typedef typename ImutIntervalInfo<ValT>::key_type        key_type;
+  typedef typename ImutIntervalInfo<ValT>::key_type_ref    key_type_ref;
+  typedef typename ImutIntervalInfo<ValT>::data_type       data_type;
+  typedef typename ImutIntervalInfo<ValT>::data_type_ref   data_type_ref;
+  typedef ImutAVLTree<ImutIntervalInfo<ValT> > TreeTy;
+
+public:
+  explicit ImmutableIntervalMap(TreeTy *R) 
+    : ImmutableMap<Interval, ValT, ImutIntervalInfo<ValT> >(R) {}
+
+  class Factory {
+    ImutIntervalAVLFactory<ImutIntervalInfo<ValT> > F;
+
+  public:
+    Factory(BumpPtrAllocator& Alloc) : F(Alloc) {}
+
+    ImmutableIntervalMap GetEmptyMap() { 
+      return ImmutableIntervalMap(F.GetEmptyTree()); 
+    }
+
+    ImmutableIntervalMap Add(ImmutableIntervalMap Old, 
+                             key_type_ref K, data_type_ref D) {
+      TreeTy *T = F.Add(Old.Root, std::make_pair<key_type, data_type>(K, D));
+      return ImmutableIntervalMap(F.GetCanonicalTree(T));
+    }
+
+    ImmutableIntervalMap Remove(ImmutableIntervalMap Old, key_type_ref K) {
+      TreeTy *T = F.Remove(Old.Root, K);
+      return ImmutableIntervalMap(F.GetCanonicalTree(T));
+    }
+
+    data_type *Lookup(ImmutableIntervalMap M, key_type_ref K) {
+      TreeTy *T = F.Find(M.getRoot(), K);
+      if (T)
+        return &T->getValue().second;
+      else
+        return 0;
+    }
+  };
+
+private:
+  // For ImmutableIntervalMap, the lookup operation has to be done by the 
+  // factory.
+  data_type* lookup(key_type_ref K) const;
+};
+
+} // end namespace llvm
diff --git a/include/llvm/ADT/ImmutableMap.h b/include/llvm/ADT/ImmutableMap.h
index 1b3f1a911ebd3..8af128ef3bd84 100644
--- a/include/llvm/ADT/ImmutableMap.h
+++ b/include/llvm/ADT/ImmutableMap.h
@@ -68,7 +68,7 @@ public:
   typedef typename ValInfo::data_type_ref   data_type_ref;
   typedef ImutAVLTree<ValInfo>              TreeTy;
 
-private:
+protected:
   TreeTy* Root;
 
 public:
@@ -106,13 +106,10 @@ public:
     void operator=(const Factory& RHS); // DO NOT IMPLEMENT
   };
 
-  friend class Factory;
-
   bool contains(key_type_ref K) const {
     return Root ? Root->contains(K) : false;
   }
 
-
   bool operator==(ImmutableMap RHS) const {
     return Root && RHS.Root ? Root->isEqual(*RHS.Root) : Root == RHS.Root;
   }
diff --git a/include/llvm/ADT/ImmutableSet.h b/include/llvm/ADT/ImmutableSet.h
index ac06a4072b8fa..65e70e279ab32 100644
--- a/include/llvm/ADT/ImmutableSet.h
+++ b/include/llvm/ADT/ImmutableSet.h
@@ -27,6 +27,7 @@ namespace llvm {
 //===----------------------------------------------------------------------===//
 
 template <typename ImutInfo> class ImutAVLFactory;
+template <typename ImutInfo> class ImutIntervalAVLFactory;
 template <typename ImutInfo> class ImutAVLTreeInOrderIterator;
 template <typename ImutInfo> class ImutAVLTreeGenericIterator;
 
@@ -39,6 +40,7 @@ public:
 
   typedef ImutAVLFactory<ImutInfo>          Factory;
   friend class ImutAVLFactory<ImutInfo>;
+  friend class ImutIntervalAVLFactory<ImutInfo>;
 
   friend class ImutAVLTreeGenericIterator<ImutInfo>;
   friend class FoldingSet<ImutAVLTree>;
@@ -389,7 +391,7 @@ public:
   // These have succinct names so that the balancing code
   // is as terse (and readable) as possible.
   //===--------------------------------------------------===//
-private:
+protected:
 
   bool           isEmpty(TreeTy* T) const { return !T; }
   unsigned Height(TreeTy* T) const { return T ? T->getHeight() : 0; }
@@ -581,25 +583,14 @@ public:
         continue;
       
       // We found a collision.  Perform a comparison of Contents('T')
-      // with Contents('L')+'V'+Contents('R').
+      // with Contents('TNew')
       typename TreeTy::iterator TI = T->begin(), TE = T->end();
       
-      // First compare Contents('L') with the (initial) contents of T.
-      if (!CompareTreeWithSection(TNew->getLeft(), TI, TE))
-        continue;
-      
-      // Now compare the new data element.
-      if (TI == TE || !TI->ElementEqual(TNew->getValue()))
-        continue;
-      
-      ++TI;
-      
-      // Now compare the remainder of 'T' with 'R'.
-      if (!CompareTreeWithSection(TNew->getRight(), TI, TE))
+      if (!CompareTreeWithSection(TNew, TI, TE))
         continue;
       
       if (TI != TE)
-        continue; // Contents('R') did not match suffix of 'T'.
+        continue; // T has more contents than TNew.
       
       // Trees did match!  Return 'T'.
       return T;
diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h
index 346fb1ca43dcd..5c774b90ee3df 100644
--- a/include/llvm/ADT/SmallBitVector.h
+++ b/include/llvm/ADT/SmallBitVector.h
@@ -310,11 +310,47 @@ public:
   }
 
   // Intersection, union, disjoint union.
-  BitVector &operator&=(const SmallBitVector &RHS); // TODO: implement
+  SmallBitVector &operator&=(const SmallBitVector &RHS) {
+    resize(std::max(size(), RHS.size()));
+    if (isSmall())
+      setSmallBits(getSmallBits() & RHS.getSmallBits());
+    else if (!RHS.isSmall())
+      X.getPointer()->operator&=(*RHS.X.getPointer());
+    else {
+      SmallBitVector Copy = RHS;
+      Copy.resize(size());
+      X.getPointer()->operator&=(*Copy.X.getPointer());
+    }
+    return *this;
+  }
 
-  BitVector &operator|=(const SmallBitVector &RHS); // TODO: implement
+  SmallBitVector &operator|=(const SmallBitVector &RHS) {
+    resize(std::max(size(), RHS.size()));
+    if (isSmall())
+      setSmallBits(getSmallBits() | RHS.getSmallBits());
+    else if (!RHS.isSmall())
+      X.getPointer()->operator|=(*RHS.X.getPointer());
+    else {
+      SmallBitVector Copy = RHS;
+      Copy.resize(size());
+      X.getPointer()->operator|=(*Copy.X.getPointer());
+    }
+    return *this;
+  }
 
-  BitVector &operator^=(const SmallBitVector &RHS); // TODO: implement
+  SmallBitVector &operator^=(const SmallBitVector &RHS) {
+    resize(std::max(size(), RHS.size()));
+    if (isSmall())
+      setSmallBits(getSmallBits() ^ RHS.getSmallBits());
+    else if (!RHS.isSmall())
+      X.getPointer()->operator^=(*RHS.X.getPointer());
+    else {
+      SmallBitVector Copy = RHS;
+      Copy.resize(size());
+      X.getPointer()->operator^=(*Copy.X.getPointer());
+    }
+    return *this;
+  }
 
   // Assignment operator.
   const SmallBitVector &operator=(const SmallBitVector &RHS) {
diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h
index c29fc9f3d244c..ef0812592be1b 100644
--- a/include/llvm/ADT/SmallPtrSet.h
+++ b/include/llvm/ADT/SmallPtrSet.h
@@ -225,7 +225,7 @@ struct NextPowerOfTwo {
 };
   
 
-/// SmallPtrSet - This class implements a set which is optimizer for holding
+/// SmallPtrSet - This class implements a set which is optimized for holding
 /// SmallSize or less elements.  This internally rounds up SmallSize to the next
 /// power of two if it is not already a power of two.  See the comments above
 /// SmallPtrSetImpl for details of the algorithm.
diff --git a/include/llvm/ADT/Triple.h b/include/llvm/ADT/Triple.h
index fe39324dd5c72..8798b0e394c10 100644
--- a/include/llvm/ADT/Triple.h
+++ b/include/llvm/ADT/Triple.h
@@ -66,6 +66,7 @@ public:
     ppc,     // PPC: powerpc
     ppc64,   // PPC64: powerpc64, ppu
     sparc,   // Sparc: sparc
+    sparcv9, // Sparcv9: Sparcv9
     systemz, // SystemZ: s390x
     tce,     // TCE (http://tce.cs.tut.fi/): tce
     thumb,   // Thumb: thumb, thumbv.*