From c0637c1828fdadd7c1b49d71d39c9d5070ea0d7c Mon Sep 17 00:00:00 2001
From: "bmeurer@chromium.org"
 <bmeurer@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Tue, 16 Jul 2013 07:07:04 +0000
Subject: [PATCH] Use BitVector instead of handcrafted SparseSet.

R=svenpanne@chromium.org

Review URL: https://codereview.chromium.org/19272011

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@15683 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/hydrogen-gvn.cc |  5 +++--
 src/hydrogen-gvn.h  | 42 +-----------------------------------------
 2 files changed, 4 insertions(+), 43 deletions(-)

diff --git a/src/hydrogen-gvn.cc b/src/hydrogen-gvn.cc
index 10826a6..65c5c3a 100644
--- a/src/hydrogen-gvn.cc
+++ b/src/hydrogen-gvn.cc
@@ -368,7 +368,7 @@ HGlobalValueNumberingPhase::HGlobalValueNumberingPhase(HGraph* graph)
         removed_side_effects_(false),
         block_side_effects_(graph->blocks()->length(), zone()),
         loop_side_effects_(graph->blocks()->length(), zone()),
-        visited_on_paths_(zone(), graph->blocks()->length()) {
+        visited_on_paths_(graph->blocks()->length(), zone()) {
     ASSERT(!AllowHandleAllocation::IsAllowed());
     block_side_effects_.AddBlock(GVNFlagSet(), graph->blocks()->length(),
                                  zone());
@@ -621,7 +621,8 @@ HGlobalValueNumberingPhase::CollectSideEffectsOnPathsToDominatedBlock(
     HBasicBlock* block = dominated->predecessors()->at(i);
     if (dominator->block_id() < block->block_id() &&
         block->block_id() < dominated->block_id() &&
-        visited_on_paths_.Add(block->block_id())) {
+        !visited_on_paths_.Contains(block->block_id())) {
+      visited_on_paths_.Add(block->block_id());
       side_effects.Add(block_side_effects_[block->block_id()]);
       if (block->IsLoopHeader()) {
         side_effects.Add(loop_side_effects_[block->block_id()]);
diff --git a/src/hydrogen-gvn.h b/src/hydrogen-gvn.h
index 66224e4..64a0fec 100644
--- a/src/hydrogen-gvn.h
+++ b/src/hydrogen-gvn.h
@@ -36,46 +36,6 @@
 namespace v8 {
 namespace internal {
 
-// Simple sparse set with O(1) add, contains, and clear.
-class SparseSet {
- public:
-  SparseSet(Zone* zone, int capacity)
-      : capacity_(capacity),
-        length_(0),
-        dense_(zone->NewArray<int>(capacity)),
-        sparse_(zone->NewArray<int>(capacity)) {
-#ifndef NVALGRIND
-    // Initialize the sparse array to make valgrind happy.
-    memset(sparse_, 0, sizeof(sparse_[0]) * capacity);
-#endif
-  }
-
-  bool Contains(int n) const {
-    ASSERT(0 <= n && n < capacity_);
-    int d = sparse_[n];
-    return 0 <= d && d < length_ && dense_[d] == n;
-  }
-
-  bool Add(int n) {
-    if (Contains(n)) return false;
-    dense_[length_] = n;
-    sparse_[n] = length_;
-    ++length_;
-    return true;
-  }
-
-  void Clear() { length_ = 0; }
-
- private:
-  int capacity_;
-  int length_;
-  int* dense_;
-  int* sparse_;
-
-  DISALLOW_COPY_AND_ASSIGN(SparseSet);
-};
-
-
 // Perform common subexpression elimination and loop-invariant code motion.
 class HGlobalValueNumberingPhase : public HPhase {
  public:
@@ -118,7 +78,7 @@ class HGlobalValueNumberingPhase : public HPhase {
 
   // Used when collecting side effects on paths from dominator to
   // dominated.
-  SparseSet visited_on_paths_;
+  BitVector visited_on_paths_;
 
   DISALLOW_COPY_AND_ASSIGN(HGlobalValueNumberingPhase);
 };
-- 
2.7.4