[sanitizer] implement node removal in Deadlock graph

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

1 files changed, 24 insertions, 0 deletions

diff --git a/lib/sanitizer_common/sanitizer_bitvector.h b/lib/sanitizer_common/sanitizer_bitvector.h
index 4ad379b91..d16205a7c 100644
--- a/lib/sanitizer_common/sanitizer_bitvector.h
+++ b/lib/sanitizer_common/sanitizer_bitvector.h
@@ -67,6 +67,13 @@ class BasicBitVector {
     return bits_ != old;
   }
 
+  // Do "this &= ~v" and return whether any bits have been removed.
+  bool setDifference(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'.
@@ -221,6 +228,23 @@ class TwoLevelBitVector {
     return res;
   }
 
+  // Do "this &= ~v" and return whether any bits have been removed.
+  bool setDifference(const TwoLevelBitVector &v) {
+    bool res = false;
+    for (uptr i0 = 0; i0 < kLevel1Size; i0++) {
+      BV t = l1_[i0];
+      t.setIntersection(v.l1_[i0]);
+      while (!t.empty()) {
+        uptr i1 = t.getAndClearFirstOne();
+        if (l2_[i0][i1].setDifference(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);