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.

llvm-svn: 49345

1 files changed, 8 insertions, 16 deletions

diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp
index 9a03c21593c..91f72c4ba65 100644
--- a/llvm/lib/Transforms/Scalar/GVN.cpp
+++ b/llvm/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>();