[sanitizer] optimize TwoLevelBitVector::intersectsWith, extend tests, fix a check

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

4 files changed, 91 insertions, 26 deletions

diff --git a/lib/sanitizer_common/sanitizer_bitvector.h b/lib/sanitizer_common/sanitizer_bitvector.h
index cf7b8ccba..93b99a4ce 100644
--- a/lib/sanitizer_common/sanitizer_bitvector.h
+++ b/lib/sanitizer_common/sanitizer_bitvector.h
@@ -61,6 +61,13 @@ class BasicBitVector {
     return bits_ != old;
   }
 
+  // Do "this &= v" and return whether any bits have been removed.
+  bool setIntersection(const BasicBitVector &v) {
+    basic_int_t old = bits_;
+    bits_ &= v.bits_;
+    return bits_ != old;
+  }
+
   void copyFrom(const BasicBitVector &v) { bits_ = v.bits_; }
 
   // Returns true if 'this' intersects with 'v'.
@@ -180,6 +187,26 @@ class TwoLevelBitVector {
     return res;
   }
 
+  // Do "this &= v" and return whether any bits have been removed.
+  bool setIntersection(const TwoLevelBitVector &v) {
+    bool res = false;
+    for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
+      if (l1_[i0].setIntersection(v.l1_[i0]))
+        res = true;
+      if (!l1_[i0].empty()) {
+        BV t = l1_[i0];
+        while (!t.empty()) {
+          uptr i1 = t.getAndClearFirstOne();
+          if (l2_[i0][i1].setIntersection(v.l2_[i0][i1]))
+            res = true;
+          if (l2_[i0][i1].empty())
+            l1_[i0].clearBit(i1);
+        }
+      }
+    }
+    return res;
+  }
+
   void copyFrom(const TwoLevelBitVector &v) {
     clear();
     setUnion(v);
@@ -189,7 +216,7 @@ class TwoLevelBitVector {
   bool intersectsWith(const TwoLevelBitVector &v) const {
     for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
       BV t = l1_[i0];
-      // FIXME: optimization: t &= v.l1_[i0]
+      t.setIntersection(v.l1_[i0]);
       while (!t.empty()) {
         uptr i1 = t.getAndClearFirstOne();
         if (!v.l1_[i0].getBit(i1)) continue;
diff --git a/lib/sanitizer_common/sanitizer_bvgraph.h b/lib/sanitizer_common/sanitizer_bvgraph.h
index 958dd4d2a..4aed87ab5 100644
--- a/lib/sanitizer_common/sanitizer_bvgraph.h
+++ b/lib/sanitizer_common/sanitizer_bvgraph.h
@@ -78,7 +78,10 @@ class BVGraph {
   }
 
  private:
-  void check(uptr idx1, uptr idx2) const { CHECK_LE(idx1|idx2, size()); }
+  void check(uptr idx1, uptr idx2) const {
+    CHECK_LT(idx1, size());
+    CHECK_LT(idx2, size());
+  }
   BV v[kSize];
 };
 
diff --git a/lib/sanitizer_common/sanitizer_deadlock_detector.h b/lib/sanitizer_common/sanitizer_deadlock_detector.h
index 66ec0186d..fcdc3f2e5 100644
--- a/lib/sanitizer_common/sanitizer_deadlock_detector.h
+++ b/lib/sanitizer_common/sanitizer_deadlock_detector.h
@@ -95,10 +95,10 @@ class DeadlockDetector {
       return getAvailableNode(data);
     }
     // We are out of vacant nodes. Flush and increment the current_epoch_.
-    uptr new_epoch = current_epoch_ + size();
-    clear();
-    current_epoch_ = new_epoch;
+    current_epoch_ += size();
+    recycled_nodes_.clear();
     available_nodes_.setAll();
+    g_.clear();
     return getAvailableNode(data);
   }
 
diff --git a/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc b/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc
index d512f57dd..f32c4c27a 100644
--- a/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc
+++ b/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc
@@ -24,19 +24,50 @@
 using namespace __sanitizer;
 using namespace std;
 
+
+template <class BV>
+static void SameAs(const BV &bv, const set<uptr> &s) {
+  BV t;
+  t.copyFrom(bv);
+  set<uptr> t_s(s);
+  while (!t.empty()) {
+    uptr idx = t.getAndClearFirstOne();
+    EXPECT_TRUE(t_s.erase(idx));
+  }
+  EXPECT_TRUE(t_s.empty());
+}
+
+template <class BV>
+void Print(const BV &bv) {
+  BV t;
+  t.copyFrom(bv);
+  while (!t.empty()) {
+    uptr idx = t.getAndClearFirstOne();
+    fprintf(stderr, "%zd ", idx);
+  }
+  fprintf(stderr, "\n");
+}
+
+void Print(const set<uptr> &s) {
+  for (set<uptr>::reverse_iterator it = s.rbegin(); it != s.rend(); ++it) {
+    fprintf(stderr, "%zd ", *it);
+  }
+  fprintf(stderr, "\n");
+}
+
 template <class BV>
 void TestBitVector(uptr expected_size) {
-  BV bv, bv1;
+  BV bv, bv1, t_bv;
   EXPECT_EQ(expected_size, BV::kSize);
   bv.clear();
   EXPECT_TRUE(bv.empty());
-  bv.setBit(13);
+  bv.setBit(5);
   EXPECT_FALSE(bv.empty());
-  EXPECT_FALSE(bv.getBit(12));
-  EXPECT_FALSE(bv.getBit(14));
-  EXPECT_TRUE(bv.getBit(13));
-  bv.clearBit(13);
-  EXPECT_FALSE(bv.getBit(13));
+  EXPECT_FALSE(bv.getBit(4));
+  EXPECT_FALSE(bv.getBit(6));
+  EXPECT_TRUE(bv.getBit(5));
+  bv.clearBit(5);
+  EXPECT_FALSE(bv.getBit(5));
 
   // test random bits
   bv.clear();
@@ -58,12 +89,12 @@ void TestBitVector(uptr expected_size) {
   }
 
   vector<uptr>bits(bv.size());
-  // Test setUnion, intersectsWith, and getAndClearFirstOne.
+  // Test setUnion, setIntersection, intersectsWith, and getAndClearFirstOne.
   for (uptr it = 0; it < 30; it++) {
     // iota
     for (size_t j = 0; j < bits.size(); j++) bits[j] = j;
     random_shuffle(bits.begin(), bits.end());
-    set<uptr> s, s1;
+    set<uptr> s, s1, t_s;
     bv.clear();
     bv1.clear();
     uptr n_bits = ((uptr)my_rand() % bv.size()) + 1;
@@ -74,32 +105,36 @@ void TestBitVector(uptr expected_size) {
       bv.setBit(bits[i]);
       s.insert(bits[i]);
     }
+    SameAs(bv, s);
     for (uptr i = 0; i < n_bits1; i++) {
       bv1.setBit(bits[bv.size() / 2 + i]);
       s1.insert(bits[bv.size() / 2 + i]);
     }
+    SameAs(bv1, s1);
 
     vector<uptr> vec;
     set_intersection(s.begin(), s.end(), s1.begin(), s1.end(),
                      back_insert_iterator<vector<uptr> >(vec));
     EXPECT_EQ(bv.intersectsWith(bv1), !vec.empty());
 
-    size_t old_size = s.size();
-    s.insert(s1.begin(), s1.end());
-    EXPECT_EQ(bv.setUnion(bv1), old_size != s.size());
-    if (0)
-      printf("union %zd %zd: %zd => %zd;  added %zd; intersection: %zd\n",
-             n_bits, n_bits1, old_size, s.size(), s.size() - old_size,
-             vec.size());
-    while (!bv.empty()) {
-      uptr idx = bv.getAndClearFirstOne();
-      EXPECT_TRUE(s.erase(idx));
-    }
-    EXPECT_TRUE(s.empty());
+    // setUnion
+    t_s = s;
+    t_bv.copyFrom(bv);
+    t_s.insert(s1.begin(), s1.end());
+    EXPECT_EQ(t_bv.setUnion(bv1), s.size() != t_s.size());
+    SameAs(t_bv, t_s);
+
+    // setIntersection
+    t_s = set<uptr>(vec.begin(), vec.end());
+    t_bv.copyFrom(bv);
+    EXPECT_EQ(t_bv.setIntersection(bv1), s.size() != t_s.size());
+    SameAs(t_bv, t_s);
   }
 }
 
 TEST(SanitizerCommon, BasicBitVector) {
+  TestBitVector<BasicBitVector<u8> >(8);
+  TestBitVector<BasicBitVector<u16> >(16);
   TestBitVector<BasicBitVector<> >(SANITIZER_WORDSIZE);
 }