From ed92b41a392c7a92859a9f80eedaed6be28e09bd Mon Sep 17 00:00:00 2001
From: Owen Anderson <resistor@mac.com>
Date: Mon, 7 Apr 2008 17:38:23 +0000
Subject: 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
---
 llvm/lib/Transforms/Scalar/GVN.cpp | 24 ++++++++----------------
 1 file changed, 8 insertions(+), 16 deletions(-)

(limited to 'llvm/lib/Transforms')

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>();
 
-- 
cgit v1.2.3