X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSparseBitVector.h;h=306e92832f0b0fd43b64e4f2dd6bdf83c3f483d4;hb=ac39a035351a20928e087617e412aa6ce510181f;hp=a87aa5475a8805bfc4601e066a51311521644aeb;hpb=2f5d5937eccfaa17c01ab5136bfde20f2f6d767c;p=oota-llvm.git

diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index a87aa5475a8..306e92832f0 100644
--- a/include/llvm/ADT/SparseBitVector.h
+++ b/include/llvm/ADT/SparseBitVector.h
@@ -2,8 +2,8 @@
 //
 //                     The LLVM Compiler Infrastructure
 //
-// This file was developed by Daniel Berlin and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
@@ -15,13 +15,14 @@
 #ifndef LLVM_ADT_SPARSEBITVECTOR_H
 #define LLVM_ADT_SPARSEBITVECTOR_H
 
-#include <cassert>
-#include <cstring>
-#include <list>
-#include <algorithm>
+#include "llvm/ADT/ilist.h"
+#include "llvm/ADT/ilist_node.h"
 #include "llvm/Support/DataTypes.h"
-#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/raw_ostream.h"
+#include <cassert>
+#include <climits>
 
 namespace llvm {
 
@@ -40,34 +41,33 @@ namespace llvm {
 
 
 template <unsigned ElementSize = 128>
-struct SparseBitVectorElement {
+struct SparseBitVectorElement
+  : public ilist_node<SparseBitVectorElement<ElementSize> > {
 public:
   typedef unsigned long BitWord;
   enum {
-    BITWORD_SIZE = sizeof(BitWord) * 8,
+    BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
     BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
     BITS_PER_ELEMENT = ElementSize
   };
+
 private:
   // Index of Element in terms of where first bit starts.
   unsigned ElementIndex;
   BitWord Bits[BITWORDS_PER_ELEMENT];
-  SparseBitVectorElement();
+  // Needed for sentinels
+  friend struct ilist_sentinel_traits<SparseBitVectorElement>;
+  SparseBitVectorElement() {
+    ElementIndex = ~0U;
+    memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
+  }
+
 public:
   explicit SparseBitVectorElement(unsigned Idx) {
     ElementIndex = Idx;
     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
   }
 
-  ~SparseBitVectorElement() {
-  }
-
-  // Copy ctor.
-  SparseBitVectorElement(const SparseBitVectorElement &RHS) {
-    ElementIndex = RHS.ElementIndex;
-    std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits);
-  }
-
   // Comparison.
   bool operator==(const SparseBitVectorElement &RHS) const {
     if (ElementIndex != RHS.ElementIndex)
@@ -105,9 +105,11 @@ public:
 
   bool test_and_set (unsigned Idx) {
     bool old = test(Idx);
-    if (!old)
+    if (!old) {
       set(Idx);
-    return !old;
+      return true;
+    }
+    return false;
   }
 
   void reset(unsigned Idx) {
@@ -126,7 +128,7 @@ public:
       else if (sizeof(BitWord) == 8)
         NumBits += CountPopulation_64(Bits[i]);
       else
-        assert(0 && "Unsupported!");
+        llvm_unreachable("Unsupported!");
     return NumBits;
   }
 
@@ -136,37 +138,34 @@ public:
       if (Bits[i] != 0) {
         if (sizeof(BitWord) == 4)
           return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
-        else if (sizeof(BitWord) == 8)
+        if (sizeof(BitWord) == 8)
           return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
-        else
-          assert(0 && "Unsupported!");
+        llvm_unreachable("Unsupported!");
       }
-    assert(0 && "Illegal empty element");
+    llvm_unreachable("Illegal empty element");
   }
 
-  /// find_next - Returns the index of the next set bit following the
-  /// "Prev" bit. Returns -1 if the next set bit is not found.
-  int find_next(unsigned Prev) const {
-    ++Prev;
-    if (Prev >= BITS_PER_ELEMENT)
+  /// find_next - Returns the index of the next set bit starting from the
+  /// "Curr" bit. Returns -1 if the next set bit is not found.
+  int find_next(unsigned Curr) const {
+    if (Curr >= BITS_PER_ELEMENT)
       return -1;
 
-    unsigned WordPos = Prev / BITWORD_SIZE;
-    unsigned BitPos = Prev % BITWORD_SIZE;
+    unsigned WordPos = Curr / BITWORD_SIZE;
+    unsigned BitPos = Curr % BITWORD_SIZE;
     BitWord Copy = Bits[WordPos];
     assert (WordPos <= BITWORDS_PER_ELEMENT
             && "Word Position outside of element");
 
     // Mask off previous bits.
-    Copy &= ~0L << BitPos;
+    Copy &= ~0UL << BitPos;
 
     if (Copy != 0) {
       if (sizeof(BitWord) == 4)
         return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy);
-      else if (sizeof(BitWord) == 8)
+      if (sizeof(BitWord) == 8)
         return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy);
-      else
-        assert(0 && "Unsupported!");
+      llvm_unreachable("Unsupported!");
     }
 
     // Check subsequent words.
@@ -174,10 +173,9 @@ public:
       if (Bits[i] != 0) {
         if (sizeof(BitWord) == 4)
           return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
-        else if (sizeof(BitWord) == 8)
+        if (sizeof(BitWord) == 8)
           return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
-        else
-          assert(0 && "Unsupported!");
+        llvm_unreachable("Unsupported!");
       }
     return -1;
   }
@@ -189,12 +187,21 @@ public:
       BitWord old = changed ? 0 : Bits[i];
 
       Bits[i] |= RHS.Bits[i];
-      if (old != Bits[i])
+      if (!changed && old != Bits[i])
         changed = true;
     }
     return changed;
   }
 
+  // Return true if we have any bits in common with RHS
+  bool intersects(const SparseBitVectorElement &RHS) const {
+    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
+      if (RHS.Bits[i] & Bits[i])
+        return true;
+    }
+    return false;
+  }
+
   // Intersect this Element with RHS and return true if this one changed.
   // BecameZero is set to true if this element became all-zero bits.
   bool intersectWith(const SparseBitVectorElement &RHS,
@@ -210,17 +217,70 @@ public:
       if (Bits[i] != 0)
         allzero = false;
 
-      if (old != Bits[i])
+      if (!changed && old != Bits[i])
         changed = true;
     }
-    BecameZero = !allzero;
+    BecameZero = allzero;
     return changed;
   }
+  // Intersect this Element with the complement of RHS and return true if this
+  // one changed.  BecameZero is set to true if this element became all-zero
+  // bits.
+  bool intersectWithComplement(const SparseBitVectorElement &RHS,
+                               bool &BecameZero) {
+    bool changed = false;
+    bool allzero = true;
+
+    BecameZero = false;
+    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
+      BitWord old = changed ? 0 : Bits[i];
+
+      Bits[i] &= ~RHS.Bits[i];
+      if (Bits[i] != 0)
+        allzero = false;
+
+      if (!changed && old != Bits[i])
+        changed = true;
+    }
+    BecameZero = allzero;
+    return changed;
+  }
+  // Three argument version of intersectWithComplement that intersects
+  // RHS1 & ~RHS2 into this element
+  void intersectWithComplement(const SparseBitVectorElement &RHS1,
+                               const SparseBitVectorElement &RHS2,
+                               bool &BecameZero) {
+    bool allzero = true;
+
+    BecameZero = false;
+    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
+      Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
+      if (Bits[i] != 0)
+        allzero = false;
+    }
+    BecameZero = allzero;
+  }
+};
+
+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 std::list<SparseBitVectorElement<ElementSize> *> ElementList;
+  typedef ilist<SparseBitVectorElement<ElementSize> > ElementList;
   typedef typename ElementList::iterator ElementListIter;
   typedef typename ElementList::const_iterator ElementListConstIter;
   enum {
@@ -247,17 +307,16 @@ class SparseBitVector {
     // Search from our current iterator, either backwards or forwards,
     // depending on what element we are looking for.
     ElementListIter ElementIter = CurrElementIter;
-    if ((*CurrElementIter)->index() == ElementIndex) {
+    if (CurrElementIter->index() == ElementIndex) {
       return ElementIter;
-    } else if ((*CurrElementIter)->index() > ElementIndex) {
+    } else if (CurrElementIter->index() > ElementIndex) {
       while (ElementIter != Elements.begin()
-             && (*ElementIter)->index() > ElementIndex)
+             && ElementIter->index() > ElementIndex)
         --ElementIter;
     } else {
       while (ElementIter != Elements.end() &&
-             (*ElementIter)->index() <= ElementIndex)
+             ElementIter->index() < ElementIndex)
         ++ElementIter;
-      --ElementIter;
     }
     CurrElementIter = ElementIter;
     return ElementIter;
@@ -265,11 +324,11 @@ class SparseBitVector {
 
   // Iterator to walk set bits in the bitmap.  This iterator is a lot uglier
   // than it would be, in order to be efficient.
-  struct SparseBitVectorIterator {
+  class SparseBitVectorIterator {
   private:
     bool AtEnd;
 
-    SparseBitVector<ElementSize> &BitVector;
+    const SparseBitVector<ElementSize> *BitVector;
 
     // Current element inside of bitmap.
     ElementListConstIter Iter;
@@ -287,16 +346,16 @@ class SparseBitVector {
     void AdvanceToFirstNonZero() {
       if (AtEnd)
         return;
-      if (BitVector.Elements.empty()) {
+      if (BitVector->Elements.empty()) {
         AtEnd = true;
         return;
       }
-      Iter = BitVector.Elements.begin();
-      BitNumber = (*Iter)->index() * ElementSize;
-      unsigned BitPos = (*Iter)->find_first();
+      Iter = BitVector->Elements.begin();
+      BitNumber = Iter->index() * ElementSize;
+      unsigned BitPos = Iter->find_first();
       BitNumber += BitPos;
       WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
-      Bits = (*Iter)->word(WordNumber);
+      Bits = Iter->word(WordNumber);
       Bits >>= BitPos % BITWORD_SIZE;
     }
 
@@ -312,35 +371,37 @@ class SparseBitVector {
 
       // See if we ran out of Bits in this word.
       if (!Bits) {
-        int NextSetBitNumber = (*Iter)->find_next(BitNumber % ElementSize) ;
+        int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
         // If we ran out of set bits in this element, move to next element.
         if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
-          Iter++;
+          ++Iter;
           WordNumber = 0;
 
           // We may run out of elements in the bitmap.
-          if (Iter == BitVector.Elements.end()) {
+          if (Iter == BitVector->Elements.end()) {
             AtEnd = true;
             return;
           }
           // Set up for next non zero word in bitmap.
-          BitNumber = (*Iter)->index() * ElementSize;
-          NextSetBitNumber = (*Iter)->find_first();
+          BitNumber = Iter->index() * ElementSize;
+          NextSetBitNumber = Iter->find_first();
           BitNumber += NextSetBitNumber;
           WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
-          Bits = (*Iter)->word(WordNumber);
+          Bits = Iter->word(WordNumber);
           Bits >>= NextSetBitNumber % BITWORD_SIZE;
         } else {
           WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
-          Bits = (*Iter)->word(WordNumber);
+          Bits = Iter->word(WordNumber);
           Bits >>= NextSetBitNumber % BITWORD_SIZE;
+          BitNumber = Iter->index() * ElementSize;
+          BitNumber += NextSetBitNumber;
         }
       }
     }
   public:
     // Preincrement.
     inline SparseBitVectorIterator& operator++() {
-      BitNumber++;
+      ++BitNumber;
       Bits >>= 1;
       AdvanceToNextNonZero();
       return *this;
@@ -360,7 +421,7 @@ class SparseBitVector {
 
     bool operator==(const SparseBitVectorIterator &RHS) const {
       // If they are both at the end, ignore the rest of the fields.
-      if (AtEnd == RHS.AtEnd)
+      if (AtEnd && RHS.AtEnd)
         return true;
       // Otherwise they are the same if they have the same bit number and
       // bitmap.
@@ -369,10 +430,13 @@ class SparseBitVector {
     bool operator!=(const SparseBitVectorIterator &RHS) const {
       return !(*this == RHS);
     }
+    SparseBitVectorIterator(): BitVector(NULL) {
+    }
 
-    explicit SparseBitVectorIterator(SparseBitVector<ElementSize> &RHS,
-                                     bool end = false):BitVector(RHS) {
-      Iter = BitVector.Elements.begin();
+
+    SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
+                            bool end = false):BitVector(RHS) {
+      Iter = BitVector->Elements.begin();
       BitNumber = 0;
       Bits = 0;
       WordNumber = ~0;
@@ -382,27 +446,43 @@ class SparseBitVector {
   };
 public:
   typedef SparseBitVectorIterator iterator;
-  typedef const SparseBitVectorIterator const_iterator;
 
   SparseBitVector () {
     CurrElementIter = Elements.begin ();
   }
 
   ~SparseBitVector() {
-    for_each(Elements.begin(), Elements.end(),
-             deleter<SparseBitVectorElement<ElementSize> >);
   }
 
   // SparseBitVector copy ctor.
   SparseBitVector(const SparseBitVector &RHS) {
     ElementListConstIter ElementIter = RHS.Elements.begin();
     while (ElementIter != RHS.Elements.end()) {
-      SparseBitVectorElement<ElementSize> *ElementCopy;
-      ElementCopy = new SparseBitVectorElement<ElementSize>(*(*ElementIter));
-      Elements.push_back(ElementCopy);
+      Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
+      ++ElementIter;
+    }
+
+    CurrElementIter = Elements.begin ();
+  }
+
+  // Clear.
+  void clear() {
+    Elements.clear();
+  }
+
+  // Assignment
+  SparseBitVector& operator=(const SparseBitVector& RHS) {
+    Elements.clear();
+
+    ElementListConstIter ElementIter = RHS.Elements.begin();
+    while (ElementIter != RHS.Elements.end()) {
+      Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
+      ++ElementIter;
     }
 
     CurrElementIter = Elements.begin ();
+
+    return *this;
   }
 
   // Test, Reset, and Set a bit in the bitmap.
@@ -416,9 +496,9 @@ public:
     // If we can't find an element that is supposed to contain this bit, there
     // is nothing more to do.
     if (ElementIter == Elements.end() ||
-        (*ElementIter)->index() != ElementIndex)
+        ElementIter->index() != ElementIndex)
       return false;
-    return (*ElementIter)->test(Idx % ElementSize);
+    return ElementIter->test(Idx % ElementSize);
   }
 
   void reset(unsigned Idx) {
@@ -431,38 +511,69 @@ public:
     // If we can't find an element that is supposed to contain this bit, there
     // is nothing more to do.
     if (ElementIter == Elements.end() ||
-        (*ElementIter)->index() != ElementIndex)
+        ElementIter->index() != ElementIndex)
       return;
-    (*ElementIter)->reset(Idx % ElementSize);
+    ElementIter->reset(Idx % ElementSize);
 
     // When the element is zeroed out, delete it.
-    if ((*ElementIter)->empty()) {
-      delete (*ElementIter);
+    if (ElementIter->empty()) {
       ++CurrElementIter;
       Elements.erase(ElementIter);
     }
   }
 
   void set(unsigned Idx) {
-    SparseBitVectorElement<ElementSize> *Element;
     unsigned ElementIndex = Idx / ElementSize;
-
+    SparseBitVectorElement<ElementSize> *Element;
+    ElementListIter ElementIter;
     if (Elements.empty()) {
       Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
-      Elements.push_back(Element);
+      ElementIter = Elements.insert(Elements.end(), Element);
+
     } else {
-      ElementListIter ElementIter = FindLowerBound(ElementIndex);
+      ElementIter = FindLowerBound(ElementIndex);
 
-      if (ElementIter != Elements.end() &&
-          (*ElementIter)->index() == ElementIndex)
-        Element = *ElementIter;
-      else {
+      if (ElementIter == Elements.end() ||
+          ElementIter->index() != ElementIndex) {
         Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
-        // Insert does insert before, and lower bound gives the one before.
-        Elements.insert(++ElementIter, Element);
+        // We may have hit the beginning of our SparseBitVector, in which case,
+        // we may need to insert right after this element, which requires moving
+        // the current iterator forward one, because insert does insert before.
+        if (ElementIter != Elements.end() &&
+            ElementIter->index() < ElementIndex)
+          ElementIter = Elements.insert(++ElementIter, Element);
+        else
+          ElementIter = Elements.insert(ElementIter, Element);
       }
     }
-    Element->set(Idx % ElementSize);
+    CurrElementIter = ElementIter;
+
+    ElementIter->set(Idx % ElementSize);
+  }
+
+  bool test_and_set (unsigned Idx) {
+    bool old = test(Idx);
+    if (!old) {
+      set(Idx);
+      return true;
+    }
+    return false;
+  }
+
+  bool operator!=(const SparseBitVector &RHS) const {
+    return !(*this == RHS);
+  }
+
+  bool operator==(const SparseBitVector &RHS) const {
+    ElementListConstIter Iter1 = Elements.begin();
+    ElementListConstIter Iter2 = RHS.Elements.begin();
+
+    for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
+         ++Iter1, ++Iter2) {
+      if (*Iter1 != *Iter2)
+        return false;
+    }
+    return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
   }
 
   // Union our bitmap with the RHS and return true if we changed.
@@ -471,30 +582,22 @@ public:
     ElementListIter Iter1 = Elements.begin();
     ElementListConstIter Iter2 = RHS.Elements.begin();
 
-    // IE They may both be end
-    if (Iter1 == Iter2)
+    // If RHS is empty, we are done
+    if (RHS.Elements.empty())
       return false;
 
-    // See if the first bitmap element is the same in both.  This is only
-    // possible if they are the same bitmap.
-    if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
-      if (*Iter1 == *Iter2)
-        return false;
-
     while (Iter2 != RHS.Elements.end()) {
-      if (Iter1 == Elements.end() || (*Iter1)->index() > (*Iter2)->index()) {
-        SparseBitVectorElement<ElementSize> *NewElem;
-
-        NewElem = new SparseBitVectorElement<ElementSize>(*(*Iter2));
-        Elements.insert(Iter1, NewElem);
-        Iter2++;
+      if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
+        Elements.insert(Iter1,
+                        new SparseBitVectorElement<ElementSize>(*Iter2));
+        ++Iter2;
         changed = true;
-      } else if ((*Iter1)->index() == (*Iter2)->index()) {
-        changed |= (*Iter1)->unionWith(*(*Iter2));
-        Iter1++;
-        Iter2++;
+      } else if (Iter1->index() == Iter2->index()) {
+        changed |= Iter1->unionWith(*Iter2);
+        ++Iter1;
+        ++Iter2;
       } else {
-        Iter1++;
+        ++Iter1;
       }
     }
     CurrElementIter = Elements.begin();
@@ -507,54 +610,288 @@ public:
     ElementListIter Iter1 = Elements.begin();
     ElementListConstIter Iter2 = RHS.Elements.begin();
 
-    // IE They may both be end.
-    if (Iter1 == Iter2)
+    // Check if both bitmaps are empty.
+    if (Elements.empty() && RHS.Elements.empty())
       return false;
 
-    // See if the first bitmap element is the same in both.  This is only
-    // possible if they are the same bitmap.
-    if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
-      if (*Iter1 == *Iter2)
-        return false;
-
     // Loop through, intersecting as we go, erasing elements when necessary.
     while (Iter2 != RHS.Elements.end()) {
-      if (Iter1 == Elements.end())
+      if (Iter1 == Elements.end()) {
+        CurrElementIter = Elements.begin();
         return changed;
+      }
 
-      if ((*Iter1)->index() > (*Iter2)->index()) {
-        Iter2++;
-      } else if ((*Iter1)->index() == (*Iter2)->index()) {
+      if (Iter1->index() > Iter2->index()) {
+        ++Iter2;
+      } else if (Iter1->index() == Iter2->index()) {
         bool BecameZero;
-        changed |= (*Iter1)->intersectWith(*(*Iter2), BecameZero);
+        changed |= Iter1->intersectWith(*Iter2, BecameZero);
         if (BecameZero) {
           ElementListIter IterTmp = Iter1;
-          delete *IterTmp;
+          ++Iter1;
           Elements.erase(IterTmp);
-          Iter1++;
         } else {
-          Iter1++;
+          ++Iter1;
         }
-        Iter2++;
+        ++Iter2;
       } else {
         ElementListIter IterTmp = Iter1;
-        Iter1++;
-        delete *IterTmp;
+        ++Iter1;
         Elements.erase(IterTmp);
       }
     }
+    Elements.erase(Iter1, Elements.end());
+    CurrElementIter = Elements.begin();
+    return changed;
+  }
+
+  // Intersect our bitmap with the complement of the RHS and return true
+  // if ours changed.
+  bool intersectWithComplement(const SparseBitVector &RHS) {
+    bool changed = false;
+    ElementListIter Iter1 = Elements.begin();
+    ElementListConstIter Iter2 = RHS.Elements.begin();
+
+    // If either our bitmap or RHS is empty, we are done
+    if (Elements.empty() || RHS.Elements.empty())
+      return false;
+
+    // Loop through, intersecting as we go, erasing elements when necessary.
+    while (Iter2 != RHS.Elements.end()) {
+      if (Iter1 == Elements.end()) {
+        CurrElementIter = Elements.begin();
+        return changed;
+      }
+
+      if (Iter1->index() > Iter2->index()) {
+        ++Iter2;
+      } else if (Iter1->index() == Iter2->index()) {
+        bool BecameZero;
+        changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
+        if (BecameZero) {
+          ElementListIter IterTmp = Iter1;
+          ++Iter1;
+          Elements.erase(IterTmp);
+        } else {
+          ++Iter1;
+        }
+        ++Iter2;
+      } else {
+        ++Iter1;
+      }
+    }
     CurrElementIter = Elements.begin();
     return changed;
   }
 
+  bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
+    return intersectWithComplement(*RHS);
+  }
+
+
+  //  Three argument version of intersectWithComplement.
+  //  Result of RHS1 & ~RHS2 is stored into this bitmap.
+  void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
+                               const SparseBitVector<ElementSize> &RHS2)
+  {
+    Elements.clear();
+    CurrElementIter = Elements.begin();
+    ElementListConstIter Iter1 = RHS1.Elements.begin();
+    ElementListConstIter Iter2 = RHS2.Elements.begin();
+
+    // If RHS1 is empty, we are done
+    // If RHS2 is empty, we still have to copy RHS1
+    if (RHS1.Elements.empty())
+      return;
+
+    // Loop through, intersecting as we go, erasing elements when necessary.
+    while (Iter2 != RHS2.Elements.end()) {
+      if (Iter1 == RHS1.Elements.end())
+        return;
+
+      if (Iter1->index() > Iter2->index()) {
+        ++Iter2;
+      } else if (Iter1->index() == Iter2->index()) {
+        bool BecameZero = false;
+        SparseBitVectorElement<ElementSize> *NewElement =
+          new SparseBitVectorElement<ElementSize>(Iter1->index());
+        NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero);
+        if (!BecameZero) {
+          Elements.push_back(NewElement);
+        }
+        else
+          delete NewElement;
+        ++Iter1;
+        ++Iter2;
+      } else {
+        SparseBitVectorElement<ElementSize> *NewElement =
+          new SparseBitVectorElement<ElementSize>(*Iter1);
+        Elements.push_back(NewElement);
+        ++Iter1;
+      }
+    }
+
+    // copy the remaining elements
+    while (Iter1 != RHS1.Elements.end()) {
+        SparseBitVectorElement<ElementSize> *NewElement =
+          new SparseBitVectorElement<ElementSize>(*Iter1);
+        Elements.push_back(NewElement);
+        ++Iter1;
+      }
+
+    return;
+  }
+
+  void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
+                               const SparseBitVector<ElementSize> *RHS2) {
+    intersectWithComplement(*RHS1, *RHS2);
+  }
+
+  bool intersects(const SparseBitVector<ElementSize> *RHS) const {
+    return intersects(*RHS);
+  }
+
+  // Return true if we share any bits in common with RHS
+  bool intersects(const SparseBitVector<ElementSize> &RHS) const {
+    ElementListConstIter Iter1 = Elements.begin();
+    ElementListConstIter Iter2 = RHS.Elements.begin();
+
+    // Check if both bitmaps are empty.
+    if (Elements.empty() && RHS.Elements.empty())
+      return false;
+
+    // Loop through, intersecting stopping when we hit bits in common.
+    while (Iter2 != RHS.Elements.end()) {
+      if (Iter1 == Elements.end())
+        return false;
+
+      if (Iter1->index() > Iter2->index()) {
+        ++Iter2;
+      } else if (Iter1->index() == Iter2->index()) {
+        if (Iter1->intersects(*Iter2))
+          return true;
+        ++Iter1;
+        ++Iter2;
+      } else {
+        ++Iter1;
+      }
+    }
+    return false;
+  }
+
+  // Return true iff all bits set in this SparseBitVector are
+  // also set in RHS.
+  bool contains(const SparseBitVector<ElementSize> &RHS) const {
+    SparseBitVector<ElementSize> Result(*this);
+    Result &= RHS;
+    return (Result == RHS);
+  }
+
+  // Return the first set bit in the bitmap.  Return -1 if no bits are set.
+  int find_first() const {
+    if (Elements.empty())
+      return -1;
+    const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
+    return (First.index() * ElementSize) + First.find_first();
+  }
+
+  // Return true if the SparseBitVector is empty
+  bool empty() const {
+    return Elements.empty();
+  }
+
+  unsigned count() const {
+    unsigned BitCount = 0;
+    for (ElementListConstIter Iter = Elements.begin();
+         Iter != Elements.end();
+         ++Iter)
+      BitCount += Iter->count();
+
+    return BitCount;
+  }
   iterator begin() const {
-    return iterator(*this);
+    return iterator(this);
   }
 
   iterator end() const {
-    return iterator(*this, ~0);
+    return iterator(this, true);
   }
 };
+
+// Convenience functions to allow Or and And without dereferencing in the user
+// code.
+
+template <unsigned ElementSize>
+inline bool operator |=(SparseBitVector<ElementSize> &LHS,
+                        const SparseBitVector<ElementSize> *RHS) {
+  return LHS |= *RHS;
+}
+
+template <unsigned ElementSize>
+inline bool operator |=(SparseBitVector<ElementSize> *LHS,
+                        const SparseBitVector<ElementSize> &RHS) {
+  return LHS->operator|=(RHS);
+}
+
+template <unsigned ElementSize>
+inline bool operator &=(SparseBitVector<ElementSize> *LHS,
+                        const SparseBitVector<ElementSize> &RHS) {
+  return LHS->operator&=(RHS);
+}
+
+template <unsigned ElementSize>
+inline bool operator &=(SparseBitVector<ElementSize> &LHS,
+                        const SparseBitVector<ElementSize> *RHS) {
+  return LHS &= *RHS;
+}
+
+// Convenience functions for infix union, intersection, difference operators.
+
+template <unsigned ElementSize>
+inline SparseBitVector<ElementSize>
+operator|(const SparseBitVector<ElementSize> &LHS,
+          const SparseBitVector<ElementSize> &RHS) {
+  SparseBitVector<ElementSize> Result(LHS);
+  Result |= RHS;
+  return Result;
+}
+
+template <unsigned ElementSize>
+inline SparseBitVector<ElementSize>
+operator&(const SparseBitVector<ElementSize> &LHS,
+          const SparseBitVector<ElementSize> &RHS) {
+  SparseBitVector<ElementSize> Result(LHS);
+  Result &= RHS;
+  return Result;
+}
+
+template <unsigned ElementSize>
+inline SparseBitVector<ElementSize>
+operator-(const SparseBitVector<ElementSize> &LHS,
+          const SparseBitVector<ElementSize> &RHS) {
+  SparseBitVector<ElementSize> Result;
+  Result.intersectWithComplement(LHS, RHS);
+  return Result;
+}
+
+
+
+
+// Dump a SparseBitVector to a stream
+template <unsigned ElementSize>
+void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) {
+  out << "[";
+
+  typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(),
+    be = LHS.end();
+  if (bi != be) {
+    out << *bi;
+    for (++bi; bi != be; ++bi) {
+      out << " " << *bi;
+    }
+  }
+  out << "]\n";
 }
+} // end namespace llvm
 
 #endif