Implement offline variable substitution in order to reduce memory

[oota-llvm.git] / include / llvm / ADT / SparseBitVector.h

diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index 5622aab6540a535fbb0c0fd024a32b214909fb0e..97439706c509b4775d361932968d7a6c0993f0c2 100644 (file)
--- a/include/llvm/ADT/SparseBitVector.h
+++ b/include/llvm/ADT/SparseBitVector.h
@@ -75,7 +75,6 @@ private:
   }
 
   friend struct ilist_traits<SparseBitVectorElement<ElementSize> >;
-
 public:
   explicit SparseBitVectorElement(unsigned Idx) {
     ElementIndex = Idx;
@@ -128,9 +127,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) {
@@ -285,6 +286,14 @@ public:
     }
     BecameZero = allzero;
   }
+  // Get a hash value for this element;
+  uint64_t getHashValue() const {
+    uint64_t HashVal = 0;
+    for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
+      HashVal ^= Bits[i];
+    }
+    return HashVal;
+  }
 };
 
 template <unsigned ElementSize = 128>
@@ -403,6 +412,8 @@ class SparseBitVector {
           WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
           Bits = Iter->word(WordNumber);
           Bits >>= NextSetBitNumber % BITWORD_SIZE;
+          BitNumber = Iter->index() * ElementSize;
+          BitNumber += NextSetBitNumber;
         }
       }
     }
@@ -533,9 +544,27 @@ public:
 
   bool test_and_set (unsigned Idx) {
     bool old = test(Idx);
-    if (!old)
+    if (!old) {
       set(Idx);
-    return !old;
+      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.
@@ -765,6 +794,17 @@ public:
     return iterator(this, ~0);
   }
 
+  // Get a hash value for this bitmap.
+  uint64_t getHashValue() const {
+    uint64_t HashVal = 0;
+    for (ElementListConstIter Iter = Elements.begin();
+         Iter != Elements.end();
+         ++Iter) {
+      HashVal ^= Iter->index();
+      HashVal ^= Iter->getHashValue();
+    }
+    return HashVal;
+  }
 };
 
 // Convenience functions to allow Or and And without dereferencing in the user
@@ -804,9 +844,10 @@ void dump(const SparseBitVector<ElementSize> &LHS, llvm::OStream &out) {
   for (bi = LHS.begin(); bi != LHS.end(); ++bi) {
     out << *bi << " ";
   }
-    out << "\n";
+    out << " ]\n";
 }
-
 }
 
+
+
 #endif