[sanitizer] replace MostSignificantSetBitIndex with LeastSignificantSetBitIndex in bit vector (to iterate bits in increasing order)

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

3 files changed, 24 insertions, 7 deletions

diff --git a/lib/sanitizer_common/sanitizer_bitvector.h b/lib/sanitizer_common/sanitizer_bitvector.h
index 93b99a4ce..2fb7d4f71 100644
--- a/lib/sanitizer_common/sanitizer_bitvector.h
+++ b/lib/sanitizer_common/sanitizer_bitvector.h
@@ -48,8 +48,7 @@ class BasicBitVector {
 
   uptr getAndClearFirstOne() {
     CHECK(!empty());
-    // FIXME: change to LeastSignificantSetBitIndex?
-    uptr idx = MostSignificantSetBitIndex(bits_);
+    uptr idx = LeastSignificantSetBitIndex(bits_);
     clearBit(idx);
     return idx;
   }
diff --git a/lib/sanitizer_common/sanitizer_common.h b/lib/sanitizer_common/sanitizer_common.h
index 5581fb6ef..6b07135c6 100644
--- a/lib/sanitizer_common/sanitizer_common.h
+++ b/lib/sanitizer_common/sanitizer_common.h
@@ -260,6 +260,19 @@ INLINE uptr MostSignificantSetBitIndex(uptr x) {
   return up;
 }
 
+INLINE uptr LeastSignificantSetBitIndex(uptr x) {
+  CHECK_NE(x, 0U);
+  unsigned long up;  // NOLINT
+#if !SANITIZER_WINDOWS || defined(__clang__) || defined(__GNUC__)
+  up = __builtin_ctzl(x);
+#elif defined(_WIN64)
+  _BitScanForward64(&up, x);
+#else
+  _BitScanForward(&up, x);
+#endif
+  return up;
+}
+
 INLINE bool IsPowerOfTwo(uptr x) {
   return (x & (x - 1)) == 0;
 }
diff --git a/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc b/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc
index f32c4c27a..d2d1a98ea 100644
--- a/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc
+++ b/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc
@@ -25,13 +25,18 @@ using namespace __sanitizer;
 using namespace std;
 
 
+// Check the 'bv' == 's' and that the indexes go in increasing order.
 template <class BV>
-static void SameAs(const BV &bv, const set<uptr> &s) {
+static void CheckBV(const BV &bv, const set<uptr> &s) {
   BV t;
   t.copyFrom(bv);
   set<uptr> t_s(s);
+  uptr last_idx = bv.size();
   while (!t.empty()) {
     uptr idx = t.getAndClearFirstOne();
+    if (last_idx != bv.size())
+      EXPECT_LT(last_idx, idx);
+    last_idx = idx;
     EXPECT_TRUE(t_s.erase(idx));
   }
   EXPECT_TRUE(t_s.empty());
@@ -105,12 +110,12 @@ void TestBitVector(uptr expected_size) {
       bv.setBit(bits[i]);
       s.insert(bits[i]);
     }
-    SameAs(bv, s);
+    CheckBV(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);
+    CheckBV(bv1, s1);
 
     vector<uptr> vec;
     set_intersection(s.begin(), s.end(), s1.begin(), s1.end(),
@@ -122,13 +127,13 @@ void TestBitVector(uptr expected_size) {
     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);
+    CheckBV(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);
+    CheckBV(t_bv, t_s);
   }
 }