diff options
3 files changed, 24 insertions, 7 deletions
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h b/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h index 93b99a4cebf..2fb7d4f7138 100644 --- a/compiler-rt/lib/sanitizer_common/sanitizer_bitvector.h +++ b/compiler-rt/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/compiler-rt/lib/sanitizer_common/sanitizer_common.h b/compiler-rt/lib/sanitizer_common/sanitizer_common.h index 5581fb6ef60..6b07135c684 100644 --- a/compiler-rt/lib/sanitizer_common/sanitizer_common.h +++ b/compiler-rt/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/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc b/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc index f32c4c27ade..d2d1a98ea88 100644 --- a/compiler-rt/lib/sanitizer_common/tests/sanitizer_bitvector_test.cc +++ b/compiler-rt/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); } } |
