Add operator= implementations to SparseBitVector, allowing it to be used in GVN. This results

in both time and memory savings for GVN.  For example, one testcase went from 10.5s to 6s with
this patch.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49345 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 31 insertions, 16 deletions

diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h
index 1ed28607ef..4c28682d39 100644
--- a/include/llvm/ADT/SparseBitVector.h
+++ b/include/llvm/ADT/SparseBitVector.h
@@ -89,6 +89,14 @@ public:
     ElementIndex = RHS.ElementIndex;
     std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits);
   }
+  
+  // Assignment 
+  SparseBitVectorElement& operator=(const SparseBitVectorElement& RHS) {
+    ElementIndex = RHS.ElementIndex;
+    std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits);
+    
+    return *this;
+  }
 
   // Comparison.
   bool operator==(const SparseBitVectorElement &RHS) const {
@@ -483,6 +491,21 @@ public:
 
     CurrElementIter = Elements.begin ();
   }
+  
+  // 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.
   bool test(unsigned Idx) {
diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index 9a03c21593..91f72c4ba6 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -22,11 +22,11 @@
 #include "llvm/Instructions.h"
 #include "llvm/ParameterAttributes.h"
 #include "llvm/Value.h"
-#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Analysis/AliasAnalysis.h"
@@ -590,9 +590,9 @@ namespace {
 class VISIBILITY_HIDDEN ValueNumberedSet {
   private:
     SmallPtrSet<Value*, 8> contents;
-    BitVector numbers;
+    SparseBitVector<64> numbers;
   public:
-    ValueNumberedSet() { numbers.resize(1); }
+    ValueNumberedSet() { }
     ValueNumberedSet(const ValueNumberedSet& other) {
       numbers = other.numbers;
       contents = other.contents;
@@ -610,9 +610,6 @@ class VISIBILITY_HIDDEN ValueNumberedSet {
     size_t size() { return contents.size(); }
     
     void set(unsigned i)  {
-      if (i >= numbers.size())
-        numbers.resize(i+1);
-      
       numbers.set(i);
     }
     
@@ -622,21 +619,12 @@ class VISIBILITY_HIDDEN ValueNumberedSet {
     }
     
     void reset(unsigned i)  {
-      if (i < numbers.size())
-        numbers.reset(i);
+      numbers.reset(i);
     }
     
     bool test(unsigned i)  {
-      if (i >= numbers.size())
-        return false;
-      
       return numbers.test(i);
     }
-    
-    void clear() {
-      contents.clear();
-      numbers.clear();
-    }
 };
 }
 
@@ -1598,6 +1586,10 @@ bool GVN::processInstruction(Instruction *I, ValueNumberedSet &currAvail,
   if (isa<AllocationInst>(I))
     return false;
   
+  // Allocations are always unique, so don't bother value numbering them.
+  if (isa<AllocationInst>(I))
+    return false;
+  
   if (MemCpyInst* M = dyn_cast<MemCpyInst>(I)) {
     MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();