[dfsan] Do not specialize vector<bool> for DFSan

[stephan.yichao.zhao]

Summary

DataFlow Sanitizer (https://clang.llvm.org/docs/DataFlowSanitizer.html)
tracks dataflow at byte granularity: all bits of a user byte share the
same dataflow label.

The default implementation of vector<bool> causes DFSan uses undefined
labels. The problem is like this:

1. push_back may reserve new memory when out of capacity. Note that after reserve, __construct_at_end initializes only the first new byte.

2. The new bit is pushed at this line, https://github.com/llvm/llvm-project/blob/main/libcxx/include/vector#L3067 which eventually calls operator= like this

__bit_reference& operator=(bool __x) _NOEXCEPT
{
    if (__x)
        *__seg_ |= __mask_;
    else
        *__seg_ &= ~__mask_;
    return *this;
}

Here note that
* __x is not assigned to __seg_ directly, but based on if-else. So DFSan
never has a chance to propagate the label of x to __seq_ without
control-flow-tainting.

* recall that reserve does not zero out new bytes. So the read of __seq_
can return undefined. However at bit-level this is fine because
   * ? & 1 = 1 and ? | 0 = 0;
   * although operator[] does not do bound check,
     it is obvious that reading unset bits is undefined.

     However DFSan reads uninitialized shadow values at the case, causing
     over-tainting. Even if DFSan tracks at bit-level, it also needs to
     understand the semantics of | and & to make it work.

This change, when -DDATAFLOW_SANITIZER is used, disables specializing
vector<bool>, forcing using the general implementation. Although this
increases memory cost 8x, this is acceptable to DFSan because DFSan has
memory overhead anyway.

[ldionne]

Sorry, but this doesn't work. We can't change the API when DF Sanitizer is in use. One thing we could do is add some sort of annotation if you have an attribute to disable that specific sanitizer on vector<bool>, but we can't just not have the declaration.

[stephan.yichao.zhao]

re "We can't change the API". Is this because C++ standard claims that std::vector<bool> must be specialized?

Can we keep all interfaces unchanged, and add some DFSan logic inside a method when the sanitizer is used?
For example, the problem we have is operator= does not propagate DFSan's meta data correctly, and the 'reserve' method does not initialize DFSan's meta data.
When DATAFLOW_SANITIZER is on, the code may add logic to initialize or propagate DFSan's information. This does not change interfaces.
Is this a better approach?

[kcc]

Why not?
DFSan is a separate ABI, you can't mix DFSan-ified code with non-DFSan-ified code.
There is no annotation that we can imagine to work in this case.
DFSan's metadata is per-byte, if we mix different taints in a single byte (8 packet bits) we get an overtaint, i.e. a false positive.
The only other solution for our users is to not use vector<bool>

[miscco]

In D96842#2568789, @stephan.yichao.zhao wrote:

re "We can't change the API". Is this because C++ standard claims that std::vector<bool> must be specialized?

Can we keep all interfaces unchanged, and add some DFSan logic inside a method when the sanitizer is used?
For example, the problem we have is operator= does not propagate DFSan's meta data correctly, and the 'reserve' method does not initialize DFSan's meta data.
When DATAFLOW_SANITIZER is on, the code may add logic to initialize or propagate DFSan's information. This does not change interfaces.
Is this a better approach?

As far as I can tell this should be no blocking issue. Usually the goal is to keep the changes as minimal as possible. E.g. would it suffice if we would zero out after allocating a new block? That would add some "minimal" runtime overhead but if you are running with a sanitizer anyway it should not be that big of a deal

[stephan.yichao.zhao]

DFSan's memory and CPU overhead is 2-3x because each user byte has 1-2 shadow byte, and user instructions have additional inserted code to propagate shadow data. So the overhead added to std::vector<bool> is acceptable.

The ideal fix is like this change. This way DFSan can accurately track flows.

Zeroing out after reserve can ensure DFSan does not read undefined shadow data, but because vector<bool> updates data at bit-level while dfsan tracks at byte-level, dfsan's tracking would not be accurate.

[ldionne]

The reason why we can't make this change as-is is that it modifies the API of std::vector when instantiated with bool when the dataflow sanitizer is used. Specifically, the specialization of vector<bool> has a different interface, it's not only an optimization. For example std::vector<bool>::reference has a .flip() method. So if someone is doing something like v[3].flip() (which is legal), now their code won't compile when they turn on the dataflow sanitizer. That's not acceptable, and it would make us non-conforming when the dataflow sanitizer is used.

Frankly, from your description, it sounds like the dataflow sanitizer is just not clever enough (yet?) to understand our code. This isn't specific to std::vector - you'll run into similar issues in a bunch of places in user code. libc++ is hardly the only place in the C++ world to do these kinds of bit manipulations. Now, this is the standard library, so we definitely want to be team players when it comes to enabling useful tooling - that's why we have things like _LIBCPP_NO_CFI to turn off some sanitizers in specific areas of our code where the sanitizers are known to be wrong.

Are there ways of locally turning off the dataflow sanitizer? Is there some sort of annotation that we could use to tell the dataflow sanitizer to track at the bit level for some operations inside vector<bool>? Those are the kinds of solutions that would be acceptable.

Also, independently of the dataflow sanitizer, it looks to me like we do have UB right here:

template <class _Allocator>
void
vector<bool, _Allocator>::push_back(const value_type& __x)
{
    if (this->__size_ == this->capacity())
        reserve(__recommend(this->__size_ + 1));
    ++this->__size_;
    back() = __x; // UB HERE
}

As you mention in the great description for this review (thanks for that by the way), we call back() = __x;, but we might not have not initialized back() yet (if we're about to set the first bit in that byte). @miscco can you confirm that we're on the same page? If so, I'll send a review to fix this. I'm a bit surprised ubsan doesn't catch that, but I guess ubsan isn't a silver bullet.

[kcc]

In D96842#2569364, @ldionne wrote:

The reason why we can't make this change as-is is that it modifies the API of std::vector when instantiated with bool when the dataflow sanitizer is used. Specifically, the specialization of vector<bool> has a different interface, it's not only an optimization. For example std::vector<bool>::reference has a .flip() method. So if someone is doing something like v[3].flip() (which is legal), now their code won't compile when they turn on the dataflow sanitizer. That's not acceptable, and it would make us non-conforming when the dataflow sanitizer is used.

Bummer, I didn't realize that... Ok...

Frankly, from your description, it sounds like the dataflow sanitizer is just not clever enough (yet?) to understand our code.

It's not about being clever, but about trading overhead for accuracy when it comes to bit-packed data structures.
msan maintains a bit-to-bit metadata and thus doesn't have this kind of false positives.

dfsan maintains a byte-to-byte metadata (currently, byte-to-two-bytes, but we are moving to byte-to-byte).
This enables us to maintain 8 taint bits per one application byte, and thus track up to 8 different data flows (taints).
This means a) 8x fewer runs required compared to a single taint tracer and b) ability to detect when two taints merge.
The downside is that in the presence of bit packing we over-taint, i.e. when setting a single bit with a tainted
value we taint the entire byte.
I am not aware of any good solution here, users will have to workaround in their code,
e.g. by not using bit-packed data structures in cases where data flow tracing is critical.

Valgrind/memcheck uses a secondary shadow for bit-to-bit shadow (for uninitialized),
but I don't think we can afford this in dfsan.

This isn't specific to std::vector - you'll run into similar issues in a bunch of places in user code. libc++ is hardly the only place in the C++ world to do these kinds of bit manipulations. Now, this is the standard library, so we definitely want to be team players when it comes to enabling useful tooling - that's why we have things like _LIBCPP_NO_CFI to turn off some sanitizers in specific areas of our code where the sanitizers are known to be wrong.

Are there ways of locally turning off the dataflow sanitizer? Is there some sort of annotation that we could use to tell the dataflow sanitizer to track at the bit level for some operations inside vector<bool>? Those are the kinds of solutions that would be acceptable.

Also, independently of the dataflow sanitizer, it looks to me like we do have UB right here:

template <class _Allocator>
void
vector<bool, _Allocator>::push_back(const value_type& __x)
{
    if (this->__size_ == this->capacity())
        reserve(__recommend(this->__size_ + 1));
    ++this->__size_;
    back() = __x; // UB HERE
}

As you mention in the great description for this review (thanks for that by the way), we call back() = __x;, but we might not have not initialized back() yet (if we're about to set the first bit in that byte). @miscco can you confirm that we're on the same page? If so, I'll send a review to fix this. I'm a bit surprised ubsan doesn't catch that, but I guess ubsan isn't a silver bullet.

[eugenis]

Can we keep all interfaces unchanged, and add some DFSan logic inside a method when the sanitizer is used?

This sounds like an acceptable solution.

To double check my understanding, you are proposing vector<bool> owns a small shadow for its contents (2 bytes per bit!) internally, and, for example, implementation of operator[] would copy the right label to its output.

[stephan.yichao.zhao]

In D96842#2569694, @eugenis wrote:

Can we keep all interfaces unchanged, and add some DFSan logic inside a method when the sanitizer is used?

This sounds like an acceptable solution.

To double check my understanding, you are proposing vector<bool> owns a small shadow for its contents (2 bytes per bit!) internally, and, for example, implementation of operator[] would copy the right label to its output.

Yup. This will be adding more code but not be changing interfaces... I need to try, and see how the change would look like.

[kcc]

(2 bytes per bit!)

1 byte per bit, hopefully. (for the new 8-bit mode only)

[ldionne]

In D96842#2569703, @stephan.yichao.zhao wrote:

Yup. This will be adding more code but not be changing interfaces... I need to try, and see how the change would look like.

I'm open to that solution if it doesn't add much complexity. Please feel free to update this patch with that proposed solution and we'll see what that looks like.

[stephan.yichao.zhao]

Before doing a complete test, this shows how one potential change would look like.
Please have a look and see if this is on the right way.

What the change does are

1. extended all operations of __bit_reference/_bit_iterator with dfsan label propagation The two classes take an additional iterator of dfsan label storage
2. vector<bool> uses <__bit_reference>, and allocates dfsan label storage We use vector<int> as the storage, so we can get all operations like copy/fill for free.
3. bitset uses <bit_reference>. So it got changed, and this increases dfsan accuracy too. Its change is more than vector<bool> because its logic is not only in bit_reference.

[kcc]

ugh..
If I were the maintainer of this file, I would run away from this change.
Not because there is something wrong with it functionality-wise, but because of the ifdefs :(
We ourselves in the sanitizer land would reject a change with this many ifdefs w/o looking further.

Some options to explore, even though I am not sure any of those options are nice:

• Have an ifdef in one place and function calls in all other places, e.g. instead of #ifdef DATAFLOW_SANITIZER do-foo #endif ... #ifdef DATAFLOW_SANITIZER do-bar #endif

have

#ifdef DATAFLOW_SANITIZER
  void doo_foo() { stuff(); } 
  void doo_bar() { other_stuff(); }
#else
  void doo_foo() { }
  void doo_bar() { }   
#endif

 do_foo();
  ...
 do_bar()

• Have a separate specialization for vector<bool> under dfsan, that would use vector<uint8_t> but implement the rest of the vector<bool> interface however ineffectively.

• Give up, and fix issues like this on the user side, by not using vector<bool> directly (for cases when we need taint tracking).

• ???

[ldionne]

Yeah, I kinda want to echo what @kcc said. I think there's not enough bang for the buck with this change as it is.

[stephan.yichao.zhao]

In D96842#2569364, @ldionne wrote:

... If so, I'll send a review to fix this. I'm a bit surprised ubsan doesn't catch that, but I guess ubsan isn't a silver bullet.

Did we confirm if this is undefined behavior?

libcxx/include/__bit_reference

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___BIT_REFERENCE
 #define _LIBCPP___BIT_REFERENCE
 
 #include <__config>
 #include <__bits>
 #include <algorithm>
 
+#ifdef DATAFLOW_SANITIZER
+#include <sanitizer/dfsan_interface.h>
+#endif
+
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Cp, bool _IsConst, typename _Cp::__storage_type = 0> class __bit_iterator;
 template <class _Cp> class __bit_const_reference;
 
 template <class _Tp>
 struct __has_storage_type
 {
     static const bool value = false;
 };
 
 template <class _Cp, bool = __has_storage_type<_Cp>::value>
 class __bit_reference
 {
+#ifdef DATAFLOW_SANITIZER
+    typedef typename _Cp::__dfsan_labels_iterator __dfsan_label_iterator;
+#endif
     typedef typename _Cp::__storage_type    __storage_type;
     typedef typename _Cp::__storage_pointer __storage_pointer;
     
+#ifdef DATAFLOW_SANITIZER
+    __dfsan_label_iterator __label_;
+#endif
     __storage_pointer __seg_;
     __storage_type    __mask_;
 
     friend typename _Cp::__self;
 
     friend class __bit_const_reference<_Cp>;
     friend class __bit_iterator<_Cp, false>;
 public:
     _LIBCPP_INLINE_VISIBILITY
     __bit_reference(const __bit_reference&) = default;
 
     _LIBCPP_INLINE_VISIBILITY operator bool() const _NOEXCEPT
-        {return static_cast<bool>(*__seg_ & __mask_);}
+    {
+#ifdef DATAFLOW_SANITIZER
+        bool __r = static_cast<bool>(*__seg_ & __mask_);
+        dfsan_set_label(*__label_, &__r, sizeof(__r));
+        return __r;
+#else
+        return static_cast<bool>(*__seg_ & __mask_);
+#endif
+    }
     _LIBCPP_INLINE_VISIBILITY bool operator ~() const _NOEXCEPT
         {return !static_cast<bool>(*this);}
 
     _LIBCPP_INLINE_VISIBILITY
     __bit_reference& operator=(bool __x) _NOEXCEPT
     {
         if (__x)
             *__seg_ |= __mask_;
         else
             *__seg_ &= ~__mask_;
+#ifdef DATAFLOW_SANITIZER
+        *__label_ = dfsan_union(*__label_, dfsan_get_label(__x));
+#endif
         return *this;
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __bit_reference& operator=(const __bit_reference& __x) _NOEXCEPT
         {return operator=(static_cast<bool>(__x));}
 
     _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {*__seg_ ^= __mask_;}
     _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, false> operator&() const _NOEXCEPT
-        {return __bit_iterator<_Cp, false>(__seg_, static_cast<unsigned>(__libcpp_ctz(__mask_)));}
+    {
+        return __bit_iterator<_Cp, false>(
+#ifdef DATAFLOW_SANITIZER
+            __label_,
+#endif
+            __seg_, static_cast<unsigned>(__libcpp_ctz(__mask_)));
+    }
 private:
     _LIBCPP_INLINE_VISIBILITY
-    __bit_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
-        : __seg_(__s), __mask_(__m) {}
+    __bit_reference(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_label_iterator __label,
+#endif
+        __storage_pointer __s, __storage_type __m) _NOEXCEPT
+        :
+#ifdef DATAFLOW_SANITIZER
+        __label_(__label),
+#endif
+        __seg_(__s), __mask_(__m) {}
 };
 
 template <class _Cp>
 class __bit_reference<_Cp, false>
 {
 };
 
 template <class _Cp>
swap(bool& __x, __bit_reference<_Cp> __y) _NOEXCEPT
     bool __t = __x;
     __x = __y;
     __y = __t;
 }
 
 template <class _Cp>
 class __bit_const_reference
 {
+#ifdef DATAFLOW_SANITIZER
+    typedef typename _Cp::__dfsan_labels_iterator __dfsan_label_iterator;
+#endif
     typedef typename _Cp::__storage_type          __storage_type;
     typedef typename _Cp::__const_storage_pointer __storage_pointer;
 
+#ifdef DATAFLOW_SANITIZER
+    __dfsan_label_iterator __label_;
+#endif
     __storage_pointer        __seg_;
     __storage_type __mask_;
 
     friend typename _Cp::__self;
     friend class __bit_iterator<_Cp, true>;
 public:
     _LIBCPP_INLINE_VISIBILITY
     __bit_const_reference(const __bit_const_reference&) = default;
 
     _LIBCPP_INLINE_VISIBILITY
     __bit_const_reference(const __bit_reference<_Cp>& __x) _NOEXCEPT
-        : __seg_(__x.__seg_), __mask_(__x.__mask_) {}
+        :
+#ifdef DATAFLOW_SANITIZER
+        __label_(__x.__label_),
+#endif
+        __seg_(__x.__seg_), __mask_(__x.__mask_) {}
 
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR operator bool() const _NOEXCEPT
-        {return static_cast<bool>(*__seg_ & __mask_);}
+    {
+#ifdef DATAFLOW_SANITIZER
+        bool __r = static_cast<bool>(*__seg_ & __mask_);
+        dfsan_set_label(*__label_, &__r, sizeof(__r));
+        return __r;
+#else
+        return static_cast<bool>(*__seg_ & __mask_);
+#endif
+    }
 
     _LIBCPP_INLINE_VISIBILITY __bit_iterator<_Cp, true> operator&() const _NOEXCEPT
-        {return __bit_iterator<_Cp, true>(__seg_, static_cast<unsigned>(__libcpp_ctz(__mask_)));}
+    {
+        return __bit_iterator<_Cp, true>(
+#ifdef DATAFLOW_SANITIZER
+            __label_,
+#endif
+            __seg_, static_cast<unsigned>(__libcpp_ctz(__mask_)));
+    }
 private:
     _LIBCPP_INLINE_VISIBILITY
     _LIBCPP_CONSTEXPR
-    __bit_const_reference(__storage_pointer __s, __storage_type __m) _NOEXCEPT
-        : __seg_(__s), __mask_(__m) {}
+    __bit_const_reference(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_label_iterator __label,
+#endif
+        __storage_pointer __s, __storage_type __m) _NOEXCEPT
+        :
+#ifdef DATAFLOW_SANITIZER
+        __label_(__label),
+#endif
+        __seg_(__s), __mask_(__m) {}
 
     __bit_const_reference& operator=(const __bit_const_reference&) = delete;
 };
 
 // find
 
 template <class _Cp, bool _IsConst>
 __bit_iterator<_Cp, _IsConst>
 __find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
 {
     typedef __bit_iterator<_Cp, _IsConst> _It;
     typedef typename _It::__storage_type __storage_type;
     static const int __bits_per_word = _It::__bits_per_word;
     // do first partial word
     if (__first.__ctz_ != 0)
     {
         __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
         __storage_type __dn = _VSTD::min(__clz_f, __n);
         __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
         __storage_type __b = *__first.__seg_ & __m;
         if (__b)
+#ifdef DATAFLOW_SANITIZER
+            return __first + _VSTD::__libcpp_ctz(__b) - __first.__ctz_;
+#else
             return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
+#endif
         if (__n == __dn)
             return __first + __n;
         __n -= __dn;
         ++__first.__seg_;
+#ifdef DATAFLOW_SANITIZER
+        __first.__label_ += __dn;
+#endif
     }
     // do middle whole words
-    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
+    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word
+#ifdef DATAFLOW_SANITIZER
+    , __first.__label_ += __bits_per_word
+#endif
+    )
         if (*__first.__seg_)
+#ifdef DATAFLOW_SANITIZER
+        {
+            int __ctz = _VSTD::__libcpp_ctz(*__first.__seg_);
+            return _It(__first.__label_ += __ctz, __first.__seg_, static_cast<unsigned>(__ctz));
+        }
+#else
             return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(*__first.__seg_)));
+#endif
+
     // do last partial word
     if (__n > 0)
     {
         __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
         __storage_type __b = *__first.__seg_ & __m;
         if (__b)
+#ifdef DATAFLOW_SANITIZER
+            return __first + _VSTD::__libcpp_ctz(__b);
+#else
             return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
+#endif
     }
-    return _It(__first.__seg_, static_cast<unsigned>(__n));
+    return _It(
+#ifdef DATAFLOW_SANITIZER
+        __first.__label_,
+#endif
+        __first.__seg_, static_cast<unsigned>(__n));
 }
 
 template <class _Cp, bool _IsConst>
 __bit_iterator<_Cp, _IsConst>
 __find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
 {
     typedef __bit_iterator<_Cp, _IsConst> _It;
     typedef typename _It::__storage_type __storage_type;
     const int __bits_per_word = _It::__bits_per_word;
     // do first partial word
     if (__first.__ctz_ != 0)
     {
         __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
         __storage_type __dn = _VSTD::min(__clz_f, __n);
         __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
         __storage_type __b = ~*__first.__seg_ & __m;
         if (__b)
+#ifdef DATAFLOW_SANITIZER
+            return __first + _VSTD::__libcpp_ctz(__b) - __first.__ctz_;
+#else
             return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
+#endif
         if (__n == __dn)
             return __first + __n;
         __n -= __dn;
         ++__first.__seg_;
+#ifdef DATAFLOW_SANITIZER
+        __first.__label_ += __dn;
+#endif
     }
     // do middle whole words
-    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word)
+    for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word
+#ifdef DATAFLOW_SANITIZER
+    , __first.__label_ += __bits_per_word
+#endif
+    )
     {
         __storage_type __b = ~*__first.__seg_;
         if (__b)
+#ifdef DATAFLOW_SANITIZER
+        {
+            int __ctz = _VSTD::__libcpp_ctz(__b);
+            return _It(__first.__label_ += __ctz, __first.__seg_, static_cast<unsigned>(__ctz));
+        }
+#else
             return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
+#endif
     }
     // do last partial word
     if (__n > 0)
     {
         __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
         __storage_type __b = ~*__first.__seg_ & __m;
         if (__b)
+#ifdef DATAFLOW_SANITIZER
+            return __first + _VSTD::__libcpp_ctz(__b);
+#else
             return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__libcpp_ctz(__b)));
+#endif
     }
-    return _It(__first.__seg_, static_cast<unsigned>(__n));
+    return _It(
+#ifdef DATAFLOW_SANITIZER
+        __first.__label_,
+#endif
+        __first.__seg_, static_cast<unsigned>(__n));
 }
 
 template <class _Cp, bool _IsConst, class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY
 __bit_iterator<_Cp, _IsConst>
 find(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_)
 {
     if (static_cast<bool>(__value_))
         return _VSTD::__find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
     return _VSTD::__find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
 }
 
 // count
 
+#ifdef DATAFLOW_SANITIZER
+template <class _Cp, bool _IsConst>
+dfsan_label __union_labels(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) {
+    dfsan_label __dfsan_label = 0;
+    typename _Cp::size_type __i = 0;
+    typedef __bit_iterator<_Cp, _IsConst> _It;
+    for (typename _It::__dfsan_labels_iterator __it = __first.__label_; __i < __n; ++__i, ++__it) {
+        __dfsan_label = dfsan_union(__dfsan_label, *__it);
+    }
+    return __dfsan_label;
+}
+#endif
+
 template <class _Cp, bool _IsConst>
 typename __bit_iterator<_Cp, _IsConst>::difference_type
 __count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
 {
     typedef __bit_iterator<_Cp, _IsConst> _It;
     typedef typename _It::__storage_type __storage_type;
     typedef typename _It::difference_type difference_type;
     const int __bits_per_word = _It::__bits_per_word;
     difference_type __r = 0;
+#ifdef DATAFLOW_SANITIZER
+    dfsan_label __dfsan_label = __union_labels(__first, __n);
+    dfsan_set_label(__dfsan_label, &__r, sizeof(__r));
+#endif
     // do first partial word
     if (__first.__ctz_ != 0)
     {
         __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
         __storage_type __dn = _VSTD::min(__clz_f, __n);
         __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
         __r = _VSTD::__libcpp_popcount(*__first.__seg_ & __m);
         __n -= __dn;

 typename __bit_iterator<_Cp, _IsConst>::difference_type
 __count_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
 {
     typedef __bit_iterator<_Cp, _IsConst> _It;
     typedef typename _It::__storage_type __storage_type;
     typedef typename _It::difference_type difference_type;
     const int __bits_per_word = _It::__bits_per_word;
     difference_type __r = 0;
+#ifdef DATAFLOW_SANITIZER
+    dfsan_label __dfsan_label = __union_labels(__first, __n);
+    dfsan_set_label(__dfsan_label, &__r, sizeof(__r));
+#endif
     // do first partial word
     if (__first.__ctz_ != 0)
     {
         __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_);
         __storage_type __dn = _VSTD::min(__clz_f, __n);
         __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn));
         __r = _VSTD::__libcpp_popcount(~*__first.__seg_ & __m);
         __n -= __dn;

 fill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_)
 {
     if (__n > 0)
     {
         if (__value_)
             _VSTD::__fill_n_true(__first, __n);
         else
             _VSTD::__fill_n_false(__first, __n);
+#ifdef DATAFLOW_SANITIZER
+        _VSTD::fill_n(__first.__label_, __n, dfsan_get_label(__value_));
+#endif
     }
 }
 
 // fill
 
 template <class _Cp>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 fill(__bit_iterator<_Cp, false> __first, __bit_iterator<_Cp, false> __last, bool __value_)
 {
     _VSTD::fill_n(__first, static_cast<typename _Cp::size_type>(__last - __first), __value_);
+#ifdef DATAFLOW_SANITIZER
+    _VSTD::fill_n(__first.__label_, __last.__label_, dfsan_get_label(__value_));
+#endif
 }
 
 // copy
 
 template <class _Cp, bool _IsConst>
 __bit_iterator<_Cp, false>
 __copy_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
                                                      __bit_iterator<_Cp, false> __result)
__copy_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
     return __result;
 }
 
 template <class _Cp, bool _IsConst>
 inline _LIBCPP_INLINE_VISIBILITY
 __bit_iterator<_Cp, false>
 copy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
 {
+#ifdef DATAFLOW_SANITIZER
+    __result.__label_ = _VSTD::copy(__first.__label_, __last.__label_, __result.__label_);
+#endif
     if (__first.__ctz_ == __result.__ctz_)
         return _VSTD::__copy_aligned(__first, __last, __result);
     return _VSTD::__copy_unaligned(__first, __last, __result);
 }
 
 // copy_backward
 
 template <class _Cp, bool _IsConst>
__copy_backward_unaligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
     return __result;
 }
 
 template <class _Cp, bool _IsConst>
 inline _LIBCPP_INLINE_VISIBILITY
 __bit_iterator<_Cp, false>
 copy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
 {
+#ifdef DATAFLOW_SANITIZER
+    __result.__label_ = _VSTD::copy_backward(__first.__label_, __last.__label_, __result.__label_);
+#endif
     if (__last.__ctz_ == __result.__ctz_)
         return _VSTD::__copy_backward_aligned(__first, __last, __result);
     return _VSTD::__copy_backward_unaligned(__first, __last, __result);
 }
 
 // move
 
 template <class _Cp, bool _IsConst>

 }
 
 template <class __C1, class __C2>
 inline _LIBCPP_INLINE_VISIBILITY
 __bit_iterator<__C2, false>
 swap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1,
             __bit_iterator<__C2, false> __first2)
 {
+#ifdef DATAFLOW_SANITIZER
+    __first2.__label_ = _VSTD::swap_ranges(__first1.__label_, __last1.__label_, __first2.__label_);
+#endif
     if (__first1.__ctz_ == __first2.__ctz_)
         return _VSTD::__swap_ranges_aligned(__first1, __last1, __first2);
     return _VSTD::__swap_ranges_unaligned(__first1, __last1, __first2);
 }
 
 // rotate
 
 template <class _Cp>
__equal_aligned(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1,
     return true;
 }
 
 template <class _Cp, bool _IC1, bool _IC2>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 equal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2)
 {
+#ifdef DATAFLOW_SANITIZER
+    typename __bit_iterator<_Cp, _IC1>::difference_type __n = __last1 - __first1;
+    dfsan_label __dfsan_label = __union_labels(__first1, __n);
+    __dfsan_label = dfsan_union(__dfsan_label, __union_labels(__first2, __n));
+    bool __r = __first1.__ctz_ == __first2.__ctz_?
+        _VSTD::__equal_aligned(__first1, __last1, __first2):
+        _VSTD::__equal_unaligned(__first1, __last1, __first2);
+    dfsan_set_label(__dfsan_label, &__r, sizeof(__r));
+    return __r;
+#else
     if (__first1.__ctz_ == __first2.__ctz_)
         return _VSTD::__equal_aligned(__first1, __last1, __first2);
     return _VSTD::__equal_unaligned(__first1, __last1, __first2);
+#endif
 }
 
 template <class _Cp, bool _IsConst,
           typename _Cp::__storage_type>
 class __bit_iterator
 {
 public:
     typedef typename _Cp::difference_type                                                          difference_type;
     typedef bool                                                                                  value_type;
     typedef __bit_iterator                                                                        pointer;
     typedef typename conditional<_IsConst, __bit_const_reference<_Cp>, __bit_reference<_Cp> >::type reference;
     typedef random_access_iterator_tag                                                            iterator_category;
 
 private:
     typedef typename _Cp::__storage_type                                           __storage_type;
     typedef typename conditional<_IsConst, typename _Cp::__const_storage_pointer,
                                            typename _Cp::__storage_pointer>::type  __storage_pointer;
     static const unsigned __bits_per_word = _Cp::__bits_per_word;
     
+#ifdef DATAFLOW_SANITIZER
+    typedef typename _Cp::__dfsan_labels_iterator __dfsan_labels_iterator;
+#endif
+
+#ifdef DATAFLOW_SANITIZER
+    __dfsan_labels_iterator __label_;
+#endif
     __storage_pointer __seg_;
     unsigned          __ctz_;
 
 public:
     _LIBCPP_INLINE_VISIBILITY __bit_iterator() _NOEXCEPT
 #if _LIBCPP_STD_VER > 11
     : __seg_(nullptr), __ctz_(0)
 #endif
     {}
 
     // avoid re-declaring a copy constructor for the non-const version.
     using __type_for_copy_to_const =
       _If<_IsConst, __bit_iterator<_Cp, false>, struct __private_nat>;
 
     _LIBCPP_INLINE_VISIBILITY
     __bit_iterator(const __type_for_copy_to_const& __it) _NOEXCEPT
-        : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {}
+        :
+#ifdef DATAFLOW_SANITIZER
+        __label_(__it.__label_),
+#endif
+        __seg_(__it.__seg_), __ctz_(__it.__ctz_) {}
 
     // The non-const __bit_iterator has historically had a non-trivial
     // copy constructor (as a quirk of its construction). We need to maintain
     // this for ABI purposes.
     using __type_for_abi_non_trivial_copy_ctor =
       _If<!_IsConst, __bit_iterator, struct __private_nat>;
 
     _LIBCPP_INLINE_VISIBILITY
     __bit_iterator(__type_for_abi_non_trivial_copy_ctor const& __it) _NOEXCEPT
-      : __seg_(__it.__seg_), __ctz_(__it.__ctz_) {}
+      :
+#ifdef DATAFLOW_SANITIZER
+       __label_(__it.__label_),
+#endif
+       __seg_(__it.__seg_), __ctz_(__it.__ctz_) {}
 
     // Always declare the copy assignment operator since the implicit declaration
     // is deprecated.
     _LIBCPP_INLINE_VISIBILITY
     __bit_iterator& operator=(__bit_iterator const&) = default;
 
     _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT
-        {return reference(__seg_, __storage_type(1) << __ctz_);}
+        {return reference(
+#ifdef DATAFLOW_SANITIZER
+        __label_,
+#endif
+        __seg_, __storage_type(1) << __ctz_);}
 
     _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator++()
     {
         if (__ctz_ != __bits_per_word-1)
             ++__ctz_;
         else
         {
             __ctz_ = 0;
             ++__seg_;
         }
+#ifdef DATAFLOW_SANITIZER
+        ++__label_;
+#endif        
         return *this;
     }
 
     _LIBCPP_INLINE_VISIBILITY __bit_iterator operator++(int)
     {
         __bit_iterator __tmp = *this;
         ++(*this);
         return __tmp;
     }
 
     _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator--()
     {
         if (__ctz_ != 0)
             --__ctz_;
         else
         {
             __ctz_ = __bits_per_word - 1;
             --__seg_;
         }
+#ifdef DATAFLOW_SANITIZER
+        --__label_;
+#endif
         return *this;
     }
 
     _LIBCPP_INLINE_VISIBILITY __bit_iterator operator--(int)
     {
         __bit_iterator __tmp = *this;
         --(*this);
         return __tmp;
     }
 
     _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator+=(difference_type __n)
     {
         if (__n >= 0)
             __seg_ += (__n + __ctz_) / __bits_per_word;
         else
             __seg_ += static_cast<difference_type>(__n - __bits_per_word + __ctz_ + 1)
                     / static_cast<difference_type>(__bits_per_word);
         __n &= (__bits_per_word - 1);
         __ctz_ = static_cast<unsigned>((__n + __ctz_)  % __bits_per_word);
+#ifdef DATAFLOW_SANITIZER
+        __label_ += __n;
+#endif               
         return *this;
     }
 
     _LIBCPP_INLINE_VISIBILITY __bit_iterator& operator-=(difference_type __n)
     {
         return *this += -__n;
     }
 
#endif
     _LIBCPP_INLINE_VISIBILITY friend bool operator<=(const __bit_iterator& __x, const __bit_iterator& __y)
         {return !(__y < __x);}
 
     _LIBCPP_INLINE_VISIBILITY friend bool operator>=(const __bit_iterator& __x, const __bit_iterator& __y)
         {return !(__x < __y);}
 
 private:
     _LIBCPP_INLINE_VISIBILITY
-    __bit_iterator(__storage_pointer __s, unsigned __ctz) _NOEXCEPT
-        : __seg_(__s), __ctz_(__ctz) {}
+    __bit_iterator(
+#ifdef DATAFLOW_SANITIZER
+         __dfsan_labels_iterator __label,
+#endif        
+         __storage_pointer __s, unsigned __ctz) _NOEXCEPT
+#ifdef DATAFLOW_SANITIZER
+        : __label_(__label),
+#endif               
+        __seg_(__s), __ctz_(__ctz) {}
 
     friend typename _Cp::__self;
 
     friend class __bit_reference<_Cp>;
     friend class __bit_const_reference<_Cp>;
     friend class __bit_iterator<_Cp, true>;
     template <class _Dp> friend struct __bit_array;
     template <class _Dp> friend void __fill_n_false(__bit_iterator<_Dp, false> __first, typename _Dp::size_type __n);
#endif
     template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_true(__bit_iterator<_Dp, _IC>,
                                                                           typename _Dp::size_type);
     template <class _Dp, bool _IC> friend __bit_iterator<_Dp, _IC> __find_bool_false(__bit_iterator<_Dp, _IC>,
                                                                            typename _Dp::size_type);
     template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
                    __count_bool_true(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
     template <class _Dp, bool _IC> friend typename __bit_iterator<_Dp, _IC>::difference_type
                    __count_bool_false(__bit_iterator<_Dp, _IC>, typename _Dp::size_type);
+
+#ifdef DATAFLOW_SANITIZER
+    template <class _Dp, bool _IC> friend dfsan_label
+                   __union_labels(__bit_iterator<_Dp, _IC> __first, typename _Dp::size_type __n);
+#endif
 };
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif  // _LIBCPP___BIT_REFERENCE

libcxx/include/bitset

 #include <__bit_reference>
 #include <cstddef>
 #include <climits>
 #include <string>
 #include <stdexcept>
 #include <iosfwd>
 #include <__functional_base>
 
+#ifdef DATAFLOW_SANITIZER
+#include <vector>
+#endif
+
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 

 public:
     typedef ptrdiff_t              difference_type;
     typedef size_t                 size_type;
     typedef size_type              __storage_type;
 protected:
     typedef __bitset __self;
     typedef       __storage_type*  __storage_pointer;
     typedef const __storage_type*  __const_storage_pointer;
+
+#ifdef DATAFLOW_SANITIZER
+    typedef vector<unsigned short int>::iterator     __dfsan_labels_iterator;
+#endif
+
     static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
 
     friend class __bit_reference<__bitset>;
     friend class __bit_const_reference<__bitset>;
     friend class __bit_iterator<__bitset, false>;
     friend class __bit_iterator<__bitset, true>;
     friend struct __bit_array<__bitset>;
 
+#ifdef DATAFLOW_SANITIZER
+    vector<unsigned short int> __dfsan_labels_;
+#endif
+
     __storage_type __first_[_N_words];
 
     typedef __bit_reference<__bitset>                  reference;
     typedef __bit_const_reference<__bitset>            const_reference;
     typedef __bit_iterator<__bitset, false>            iterator;
     typedef __bit_iterator<__bitset, true>             const_iterator;
 
     _LIBCPP_INLINE_VISIBILITY
     _LIBCPP_CONSTEXPR __bitset() _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     explicit _LIBCPP_CONSTEXPR __bitset(unsigned long long __v) _NOEXCEPT;
 
     _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_t __pos) _NOEXCEPT
-        {return reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
+        {return reference(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_.begin() + __pos,
+#endif
+        __first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR const_reference __make_ref(size_t __pos) const _NOEXCEPT
-        {return const_reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
+        {return const_reference(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_.begin() + __pos,
+#endif
+        __first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
     _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_t __pos) _NOEXCEPT
-        {return iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);}
+        {return iterator(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_.begin() + __pos,
+#endif
+        __first_ + __pos / __bits_per_word, __pos % __bits_per_word);}
     _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_t __pos) const _NOEXCEPT
-        {return const_iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);}
+        {return const_iterator(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_.begin() + __pos,
+#endif
+        __first_ + __pos / __bits_per_word, __pos % __bits_per_word);}
 
     _LIBCPP_INLINE_VISIBILITY
     void operator&=(const __bitset& __v) _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     void operator|=(const __bitset& __v) _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     void operator^=(const __bitset& __v) _NOEXCEPT;
 
#endif  // _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     unsigned long to_ulong(true_type) const;
     unsigned long long to_ullong(false_type) const;
     _LIBCPP_INLINE_VISIBILITY
     unsigned long long to_ullong(true_type) const;
     _LIBCPP_INLINE_VISIBILITY
     unsigned long long to_ullong(true_type, false_type) const;
     unsigned long long to_ullong(true_type, true_type) const;
+#ifdef DATAFLOW_SANITIZER
+    dfsan_label union_labels() const _NOEXCEPT;
+    void merge_labels(const __bitset& __v) _NOEXCEPT;
+#endif
 };
 
 template <size_t _N_words, size_t _Size>
 inline
 _LIBCPP_CONSTEXPR
 __bitset<_N_words, _Size>::__bitset() _NOEXCEPT
 #ifndef _LIBCPP_CXX03_LANG
     : __first_{0}
 #endif
+#ifdef DATAFLOW_SANITIZER
+    , __dfsan_labels_(_Size, 0)
+#endif    
 {
 #ifdef _LIBCPP_CXX03_LANG
     _VSTD::fill_n(__first_, _N_words, __storage_type(0));
 #endif
 }
 
 #ifdef _LIBCPP_CXX03_LANG
 
 template <size_t _N_words, size_t _Size>
 void
 __bitset<_N_words, _Size>::__init(unsigned long long __v, false_type) _NOEXCEPT
 {
     __storage_type __t[sizeof(unsigned long long) / sizeof(__storage_type)];
     size_t __sz = _Size;
     for (size_t __i = 0; __i < sizeof(__t)/sizeof(__t[0]); ++__i, __v >>= __bits_per_word, __sz -= __bits_per_word )
         if ( __sz < __bits_per_word)
             __t[__i] = static_cast<__storage_type>(__v) & ( 1ULL << __sz ) - 1;
         else
             __t[__i] = static_cast<__storage_type>(__v);
 
     _VSTD::copy(__t, __t + sizeof(__t)/sizeof(__t[0]), __first_);
     _VSTD::fill(__first_ + sizeof(__t)/sizeof(__t[0]), __first_ + sizeof(__first_)/sizeof(__first_[0]),
                __storage_type(0));
+#ifdef DATAFLOW_SANITIZER
+    _VSTD::fill(__dfsan_labels_, _Size, dfsan_get_label(__v));
+#endif
 }
 
 template <size_t _N_words, size_t _Size>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 __bitset<_N_words, _Size>::__init(unsigned long long __v, true_type) _NOEXCEPT
 {
+#ifdef DATAFLOW_SANITIZER
+    _VSTD::fill(__dfsan_labels_, _Size, dfsan_get_label(__v));
+#endif
+
     __first_[0] = __v;
     if (_Size < __bits_per_word)
         __first_[0] &= ( 1ULL << _Size ) - 1;
 
     _VSTD::fill(__first_ + 1, __first_ + sizeof(__first_)/sizeof(__first_[0]), __storage_type(0));
 }
 
 #endif  // _LIBCPP_CXX03_LANG
 
 template <size_t _N_words, size_t _Size>
 inline
 _LIBCPP_CONSTEXPR
 __bitset<_N_words, _Size>::__bitset(unsigned long long __v) _NOEXCEPT
 #ifndef _LIBCPP_CXX03_LANG
 #if __SIZEOF_SIZE_T__ == 8
     : __first_{__v}
 #elif __SIZEOF_SIZE_T__ == 4
     : __first_{static_cast<__storage_type>(__v),
                 _Size >= 2 * __bits_per_word ? static_cast<__storage_type>(__v >> __bits_per_word)
                 : static_cast<__storage_type>((__v >> __bits_per_word) & (__storage_type(1) << (_Size - __bits_per_word)) - 1)}
 #else
 #error This constructor has not been ported to this platform
 #endif
 #endif
+#ifdef DATAFLOW_SANITIZER
+    , __dfsan_labels_(_Size, 0)
+#endif    
 {
 #ifdef _LIBCPP_CXX03_LANG
     __init(__v, integral_constant<bool, sizeof(unsigned long long) == sizeof(__storage_type)>());
 #endif
 }
 
+#ifdef DATAFLOW_SANITIZER
+template <size_t _N_words, size_t _Size>
+inline
+void
+__bitset<_N_words, _Size>::merge_labels(const __bitset& __v) _NOEXCEPT
+{
+    for (size_type __i = 0; __i < _Size; ++__i)
+        __dfsan_labels_[__i] = dfsan_union(__dfsan_labels_[__i], __v.__dfsan_labels_[__i]);
+}
+#endif
+
 template <size_t _N_words, size_t _Size>
 inline
 void
 __bitset<_N_words, _Size>::operator&=(const __bitset& __v) _NOEXCEPT
 {
     for (size_type __i = 0; __i < _N_words; ++__i)
         __first_[__i] &= __v.__first_[__i];
+#ifdef DATAFLOW_SANITIZER
+    merge_labels(__v);
+#endif
 }
 
 template <size_t _N_words, size_t _Size>
 inline
 void
 __bitset<_N_words, _Size>::operator|=(const __bitset& __v) _NOEXCEPT
 {
     for (size_type __i = 0; __i < _N_words; ++__i)
         __first_[__i] |= __v.__first_[__i];
+#ifdef DATAFLOW_SANITIZER
+    merge_labels(__v);
+#endif
 }
 
 template <size_t _N_words, size_t _Size>
 inline
 void
 __bitset<_N_words, _Size>::operator^=(const __bitset& __v) _NOEXCEPT
 {
     for (size_type __i = 0; __i < _N_words; ++__i)
         __first_[__i] ^= __v.__first_[__i];
+#ifdef DATAFLOW_SANITIZER
+    merge_labels(__v);
+#endif
 }
 
 template <size_t _N_words, size_t _Size>
 void
 __bitset<_N_words, _Size>::flip() _NOEXCEPT
 {
     // do middle whole words
     size_type __n = _Size;

 unsigned long
 __bitset<_N_words, _Size>::to_ulong(false_type) const
 {
     const_iterator __e = __make_iter(_Size);
     const_iterator __i = _VSTD::find(__make_iter(sizeof(unsigned long) * CHAR_BIT), __e, true);
     if (__i != __e)
         __throw_overflow_error("bitset to_ulong overflow error");
 
+#ifdef DATAFLOW_SANITIZER
+    unsigned long __r = __first_[0];
+    dfsan_set_label(*__i.__label_, &__r, sizeof(__r));
+    return __r;
+#else    
     return __first_[0];
+#endif
 }
 
 template <size_t _N_words, size_t _Size>
 inline
 unsigned long
 __bitset<_N_words, _Size>::to_ulong(true_type) const
 {
+#ifdef DATAFLOW_SANITIZER
+    unsigned long __r = __first_[0];
+    dfsan_set_label(__dfsan_labels_[0], &__r, sizeof(__r));
+    return __r;
+#else
     return __first_[0];
+#endif
 }
 
 template <size_t _N_words, size_t _Size>
 unsigned long long
 __bitset<_N_words, _Size>::to_ullong(false_type) const
 {
     const_iterator __e = __make_iter(_Size);
     const_iterator __i = _VSTD::find(__make_iter(sizeof(unsigned long long) * CHAR_BIT), __e, true);
__bitset<_N_words, _Size>::to_ullong(true_type) const
     return to_ullong(true_type(), integral_constant<bool, sizeof(__storage_type) < sizeof(unsigned long long)>());
 }
 
 template <size_t _N_words, size_t _Size>
 inline
 unsigned long long
 __bitset<_N_words, _Size>::to_ullong(true_type, false_type) const
 {
+#ifdef DATAFLOW_SANITIZER
+    unsigned long __r = __first_[0];
+    dfsan_set_label(__dfsan_labels_[0], &__r, sizeof(__r));
+    return __r;
+#else
     return __first_[0];
+#endif
+}
+
+#ifdef DATAFLOW_SANITIZER
+template <size_t _N_words, size_t _Size>
+inline
+dfsan_label
+__bitset<_N_words, _Size>::union_labels() const _NOEXCEPT
+{
+    dfsan_label __dfsan_label = 0;
+    for (size_type __i = 0; __i < _Size; ++__i)
+        __dfsan_label = dfsan_union(__dfsan_label, __dfsan_labels_[__i]);
+    return __dfsan_label;
 }
+#endif
 
 template <size_t _N_words, size_t _Size>
 unsigned long long
 __bitset<_N_words, _Size>::to_ullong(true_type, true_type) const
 {
     unsigned long long __r = __first_[0];
     for (size_t __i = 1; __i < sizeof(unsigned long long) / sizeof(__storage_type); ++__i)
         __r |= static_cast<unsigned long long>(__first_[__i]) << (sizeof(__storage_type) * CHAR_BIT);
+#ifdef DATAFLOW_SANITIZER
+    dfsan_set_label(union_labels(), &__r, sizeof(__r));
+#endif
     return __r;
 }
 
 template <size_t _N_words, size_t _Size>
 bool
 __bitset<_N_words, _Size>::all() const _NOEXCEPT
 {
     // do middle whole words
     size_type __n = _Size;
+#ifdef DATAFLOW_SANITIZER
+    dfsan_label __dfsan_label = union_labels();
+#endif
     __const_storage_pointer __p = __first_;
     for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
-        if (~*__p)
+        if (~*__p) {
+#ifdef DATAFLOW_SANITIZER
+            bool __r = false;
+            dfsan_set_label(__dfsan_label, &__r, sizeof(__r));
+            return __r;
+#else
             return false;
+#endif
+        }
     // do last partial word
     if (__n > 0)
     {
         __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
-        if (~*__p & __m)
+        if (~*__p & __m) {
+#ifdef DATAFLOW_SANITIZER
+            bool __r = false;
+            dfsan_set_label(__dfsan_label, &__r, sizeof(__r));
+            return __r;
+#else
             return false;
+#endif
         }
+    }
+#ifdef DATAFLOW_SANITIZER
+    bool __r = true;
+    dfsan_set_label(__dfsan_label, &__r, sizeof(__r));
+    return __r;
+#else
     return true;
+#endif
 }
 
 template <size_t _N_words, size_t _Size>
 bool
 __bitset<_N_words, _Size>::any() const _NOEXCEPT
 {
     // do middle whole words
     size_type __n = _Size;
+#ifdef DATAFLOW_SANITIZER
+    dfsan_label __dfsan_label = union_labels();
+#endif
     __const_storage_pointer __p = __first_;
     for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
-        if (*__p)
+        if (*__p) {
+#ifdef DATAFLOW_SANITIZER
+            bool __r = true;
+            dfsan_set_label(__dfsan_label, &__r, sizeof(__r));
+            return __r;
+#else            
             return true;
+#endif            
+        }
     // do last partial word
     if (__n > 0)
     {
         __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
-        if (*__p & __m)
+        if (*__p & __m) {
+#ifdef DATAFLOW_SANITIZER
+            bool __r = true;
+            dfsan_set_label(__dfsan_label, &__r, sizeof(__r));
+            return __r;
+#else            
             return true;
+#endif            
+        }
     }
+#ifdef DATAFLOW_SANITIZER
+    bool __r = false;
+    dfsan_set_label(__dfsan_label, &__r, sizeof(__r));
+    return __r;
+#else            
     return false;
+#endif            
 }
 
 template <size_t _N_words, size_t _Size>
 inline
 size_t
 __bitset<_N_words, _Size>::__hash_code() const _NOEXCEPT
 {
     size_t __h = 0;
     for (size_type __i = 0; __i < _N_words; ++__i)
         __h ^= __first_[__i];
+#ifdef DATAFLOW_SANITIZER
+    dfsan_set_label(union_labels(), &__h, sizeof(__h));
+#endif
     return __h;
 }
 
 template <size_t _Size>
 class __bitset<1, _Size>
 {
 public:
     typedef ptrdiff_t              difference_type;
     typedef size_t                 size_type;
     typedef size_type              __storage_type;
 protected:
     typedef __bitset __self;
     typedef       __storage_type*  __storage_pointer;
     typedef const __storage_type*  __const_storage_pointer;
     static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
 
+#ifdef DATAFLOW_SANITIZER
+    typedef vector<unsigned short int>::iterator     __dfsan_labels_iterator;
+#endif
+
     friend class __bit_reference<__bitset>;
     friend class __bit_const_reference<__bitset>;
     friend class __bit_iterator<__bitset, false>;
     friend class __bit_iterator<__bitset, true>;
     friend struct __bit_array<__bitset>;
 
+#ifdef DATAFLOW_SANITIZER
+    vector<unsigned short int> __dfsan_labels_;
+#endif
+
     __storage_type __first_;
 
     typedef __bit_reference<__bitset>                  reference;
     typedef __bit_const_reference<__bitset>            const_reference;
     typedef __bit_iterator<__bitset, false>            iterator;
     typedef __bit_iterator<__bitset, true>             const_iterator;
 
     _LIBCPP_INLINE_VISIBILITY
     _LIBCPP_CONSTEXPR __bitset() _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     explicit _LIBCPP_CONSTEXPR __bitset(unsigned long long __v) _NOEXCEPT;
 
     _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_t __pos) _NOEXCEPT
-        {return reference(&__first_, __storage_type(1) << __pos);}
+        {return reference(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_.begin() + __pos,
+#endif
+        &__first_, __storage_type(1) << __pos);}
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR const_reference __make_ref(size_t __pos) const _NOEXCEPT
-        {return const_reference(&__first_, __storage_type(1) << __pos);}
+        {return const_reference(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_.begin() + __pos,
+#endif
+        &__first_, __storage_type(1) << __pos);}
     _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_t __pos) _NOEXCEPT
-        {return iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word);}
+        {return iterator(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_.begin() + __pos,
+#endif
+        &__first_ + __pos / __bits_per_word, __pos % __bits_per_word);}
     _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_t __pos) const _NOEXCEPT
-        {return const_iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word);}
+        {return const_iterator(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_.begin() + __pos,
+#endif
+        &__first_ + __pos / __bits_per_word, __pos % __bits_per_word);}
 
     _LIBCPP_INLINE_VISIBILITY
     void operator&=(const __bitset& __v) _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     void operator|=(const __bitset& __v) _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     void operator^=(const __bitset& __v) _NOEXCEPT;
 
     _LIBCPP_INLINE_VISIBILITY
     void flip() _NOEXCEPT;
 
     _LIBCPP_INLINE_VISIBILITY
     unsigned long to_ulong() const;
     _LIBCPP_INLINE_VISIBILITY
     unsigned long long to_ullong() const;
 
     _LIBCPP_INLINE_VISIBILITY
     bool all() const _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     bool any() const _NOEXCEPT;
 
     _LIBCPP_INLINE_VISIBILITY
     size_t __hash_code() const _NOEXCEPT;
+    
+#ifdef DATAFLOW_SANITIZER
+    dfsan_label union_labels() const _NOEXCEPT;
+    void merge_labels(const __bitset& __v) _NOEXCEPT;
+#endif    
 };
 
 template <size_t _Size>
 inline
 _LIBCPP_CONSTEXPR
 __bitset<1, _Size>::__bitset() _NOEXCEPT
     : __first_(0)
+#ifdef DATAFLOW_SANITIZER
+    , __dfsan_labels_(_Size, 0)
+#endif    
 {
 }
 
 template <size_t _Size>
 inline
 _LIBCPP_CONSTEXPR
 __bitset<1, _Size>::__bitset(unsigned long long __v) _NOEXCEPT
     : __first_(
         _Size == __bits_per_word ? static_cast<__storage_type>(__v)
                                  : static_cast<__storage_type>(__v) & ((__storage_type(1) << _Size) - 1)
     )
+#ifdef DATAFLOW_SANITIZER
+    , __dfsan_labels_(_Size, dfsan_get_label(__v))
+#endif
 {
 }
 
+#ifdef DATAFLOW_SANITIZER
+template <size_t _Size>
+inline
+void
+__bitset<1, _Size>::merge_labels(const __bitset& __v) _NOEXCEPT
+{
+    for (size_type __i = 0; __i < _Size; ++__i)
+        __dfsan_labels_[__i] = dfsan_union(__dfsan_labels_[__i], __v.__dfsan_labels_[__i]);
+}
+#endif
+
 template <size_t _Size>
 inline
 void
 __bitset<1, _Size>::operator&=(const __bitset& __v) _NOEXCEPT
 {
     __first_ &= __v.__first_;
+#ifdef DATAFLOW_SANITIZER
+    merge_labels(__v);
+#endif
 }
 
 template <size_t _Size>
 inline
 void
 __bitset<1, _Size>::operator|=(const __bitset& __v) _NOEXCEPT
 {
     __first_ |= __v.__first_;
+#ifdef DATAFLOW_SANITIZER
+    merge_labels(__v);
+#endif
 }
 
 template <size_t _Size>
 inline
 void
 __bitset<1, _Size>::operator^=(const __bitset& __v) _NOEXCEPT
 {
     __first_ ^= __v.__first_;
+#ifdef DATAFLOW_SANITIZER
+    merge_labels(__v);
+#endif
 }
 
 template <size_t _Size>
 inline
 void
 __bitset<1, _Size>::flip() _NOEXCEPT
 {
     __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size);
     __first_ = ~__first_;
     __first_ &= __m;
 }
 
+#ifdef DATAFLOW_SANITIZER
+template <size_t _Size>
+inline
+dfsan_label
+__bitset<1, _Size>::union_labels() const _NOEXCEPT
+{
+    dfsan_label __dfsan_label = 0;
+    for (size_type __i = 0; __i < _Size; ++__i)
+        __dfsan_label = dfsan_union(__dfsan_label, __dfsan_labels_[__i]);
+    return __dfsan_label;
+}
+#endif
+
 template <size_t _Size>
 inline
 unsigned long
 __bitset<1, _Size>::to_ulong() const
 {
+#ifdef DATAFLOW_SANITIZER
+    unsigned long __r = __first_;
+    dfsan_set_label(union_labels(), &__r, sizeof(__r));
+    return __r;
+#else        
     return __first_;
+#endif
 }
 
 template <size_t _Size>
 inline
 unsigned long long
 __bitset<1, _Size>::to_ullong() const
 {
+#ifdef DATAFLOW_SANITIZER
+    unsigned long long __r = __first_;
+    dfsan_set_label(union_labels(), &__r, sizeof(__r));
+    return __r;
+#else        
     return __first_;
+#endif
 }
 
 template <size_t _Size>
 inline
 bool
 __bitset<1, _Size>::all() const _NOEXCEPT
 {
     __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size);
+#ifdef DATAFLOW_SANITIZER
+    bool __r = !(~__first_ & __m);
+    dfsan_set_label(union_labels(), &__r, sizeof(__r));
+    return __r;
+#else        
     return !(~__first_ & __m);
+#endif
 }
 
 template <size_t _Size>
 inline
 bool
 __bitset<1, _Size>::any() const _NOEXCEPT
 {
     __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size);
+#ifdef DATAFLOW_SANITIZER
+    bool __r = __first_ & __m;
+    dfsan_set_label(union_labels(), &__r, sizeof(__r));
+    return __r;
+#else        
     return __first_ & __m;
+#endif
 }
 
 template <size_t _Size>
 inline
 size_t
 __bitset<1, _Size>::__hash_code() const _NOEXCEPT
 {
+#ifdef DATAFLOW_SANITIZER
+    size_t __r = __first_;
+    dfsan_set_label(union_labels(), &__r, sizeof(__r));
+    return __r;
+#else        
     return __first_;
+#endif    
 }
 
 template <>
 class __bitset<0, 0>
 {
 public:
     typedef ptrdiff_t              difference_type;
     typedef size_t                 size_type;
     typedef size_type              __storage_type;
 protected:
     typedef __bitset __self;
     typedef       __storage_type*  __storage_pointer;
     typedef const __storage_type*  __const_storage_pointer;
+#ifdef DATAFLOW_SANITIZER
+    typedef vector<unsigned short int>::iterator     __dfsan_labels_iterator;
+#endif
     static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
 
     friend class __bit_reference<__bitset>;
     friend class __bit_const_reference<__bitset>;
     friend class __bit_iterator<__bitset, false>;
     friend class __bit_iterator<__bitset, true>;
     friend struct __bit_array<__bitset>;
 
     typedef __bit_reference<__bitset>                  reference;
     typedef __bit_const_reference<__bitset>            const_reference;
     typedef __bit_iterator<__bitset, false>            iterator;
     typedef __bit_iterator<__bitset, true>             const_iterator;
 
     _LIBCPP_INLINE_VISIBILITY
     _LIBCPP_CONSTEXPR __bitset() _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     explicit _LIBCPP_CONSTEXPR __bitset(unsigned long long) _NOEXCEPT;
 
     _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_t) _NOEXCEPT
-        {return reference(nullptr, 1);}
+        {return reference(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_iterator(),
+#endif
+        nullptr, 1);}
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR const_reference __make_ref(size_t) const _NOEXCEPT
-        {return const_reference(nullptr, 1);}
+        {return const_reference(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_iterator(),
+#endif
+        nullptr, 1);}
     _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_t) _NOEXCEPT
-        {return iterator(nullptr, 0);}
+        {return iterator(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_iterator(),
+#endif
+        nullptr, 0);}
     _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_t) const _NOEXCEPT
-        {return const_iterator(nullptr, 0);}
+        {return const_iterator(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_iterator(),
+#endif
+        nullptr, 0);}
 
     _LIBCPP_INLINE_VISIBILITY void operator&=(const __bitset&) _NOEXCEPT {}
     _LIBCPP_INLINE_VISIBILITY void operator|=(const __bitset&) _NOEXCEPT {}
     _LIBCPP_INLINE_VISIBILITY void operator^=(const __bitset&) _NOEXCEPT {}
 
     _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {}
 
     _LIBCPP_INLINE_VISIBILITY unsigned long to_ulong() const {return 0;}
for (size_t __i = 0; __i < __rlen; ++__i)
         if (__str[__i] != __zero && __str[__i] != __one)
             __throw_invalid_argument("bitset string ctor has invalid argument");
 
     size_t _Mp = _VSTD::min(__rlen, _Size);
     size_t __i = 0;
     for (; __i < _Mp; ++__i)
     {
         _CharT __c = __str[_Mp - 1 - __i];
+#ifdef DATAFLOW_SANITIZER
+        bool __b = __c == __zero;
+        (*this)[__i] = __b;
+#else
         if (__c == __zero)
             (*this)[__i] = false;
         else
             (*this)[__i] = true;
+#endif
     }
     _VSTD::fill(base::__make_iter(__i), base::__make_iter(_Size), false);
 }
 
 template <size_t _Size>
 template<class _CharT, class _Traits, class _Allocator>
 bitset<_Size>::bitset(const basic_string<_CharT,_Traits,_Allocator>& __str,
        typename basic_string<_CharT,_Traits,_Allocator>::size_type __pos,

 template <size_t _Size>
 template <class _CharT, class _Traits, class _Allocator>
 basic_string<_CharT, _Traits, _Allocator>
 bitset<_Size>::to_string(_CharT __zero, _CharT __one) const
 {
     basic_string<_CharT, _Traits, _Allocator> __r(_Size, __zero);
     for (size_t __i = 0; __i < _Size; ++__i)
     {
-        if ((*this)[__i])
+#ifdef DATAFLOW_SANITIZER
+        bool __b = (*this)[__i];
+        if (__b) {
+            dfsan_set_label(dfsan_get_label(__b), &__one, sizeof(__one));
             __r[_Size - 1 - __i] = __one;
+        } else {
+            dfsan_set_label(dfsan_get_label(__b), &__zero, sizeof(__zero));
+            __r[_Size - 1 - __i] = __zero;
+        }
+#else
+        if ((*this)[__i]) {
+            __r[_Size - 1 - __i] = __one;
+        }
+#endif
     }
     return __r;
 }
 
 template <size_t _Size>
 template <class _CharT, class _Traits>
 inline
 basic_string<_CharT, _Traits, allocator<_CharT> >

libcxx/include/vector

public:
     typedef _VSTD::reverse_iterator<iterator>         reverse_iterator;
     typedef _VSTD::reverse_iterator<const_iterator>   const_reverse_iterator;
 
 private:
     typedef typename __rebind_alloc_helper<__alloc_traits, __storage_type>::type __storage_allocator;
     typedef allocator_traits<__storage_allocator>    __storage_traits;
     typedef typename __storage_traits::pointer       __storage_pointer;
     typedef typename __storage_traits::const_pointer __const_storage_pointer;
     
+#ifdef DATAFLOW_SANITIZER
+    typedef vector<unsigned short int>::iterator     __dfsan_labels_iterator;
+#endif
+
     __storage_pointer                                      __begin_;
     size_type                                              __size_;
     __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
+    
+#ifdef DATAFLOW_SANITIZER
+    vector<unsigned short int> __dfsan_labels_;
+#endif
+    
 public:
     typedef __bit_reference<vector>                  reference;
     typedef __bit_const_reference<vector>            const_reference;
 private:
     _LIBCPP_INLINE_VISIBILITY
     size_type& __cap() _NOEXCEPT
         {return __cap_alloc_.first();}
     _LIBCPP_INLINE_VISIBILITY
template <class _ForwardIterator>
         <
             __is_cpp17_forward_iterator<_ForwardIterator>::value,
             void
         >::type
         __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
     void __append(size_type __n, const_reference __x);
     _LIBCPP_INLINE_VISIBILITY
     reference __make_ref(size_type __pos) _NOEXCEPT
-        {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
+        {return reference(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_.begin() + __pos,
+#endif
+        __begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
     _LIBCPP_INLINE_VISIBILITY
     const_reference __make_ref(size_type __pos) const _NOEXCEPT
-        {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
+        {return const_reference(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_.begin() + __pos,
+#endif
+        __begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
     _LIBCPP_INLINE_VISIBILITY
     iterator __make_iter(size_type __pos) _NOEXCEPT
-        {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
+        {return iterator(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_.begin() + __pos,
+#endif
+        __begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
     _LIBCPP_INLINE_VISIBILITY
     const_iterator __make_iter(size_type __pos) const _NOEXCEPT
-        {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
+        {return const_iterator(
+#ifdef DATAFLOW_SANITIZER
+        __dfsan_labels_.begin() + __pos,
+#endif
+        __begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
     _LIBCPP_INLINE_VISIBILITY
     iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT
         {return begin() + (__p - cbegin());}
 
     _LIBCPP_INLINE_VISIBILITY
     void __copy_assign_alloc(const vector& __v)
         {__copy_assign_alloc(__v, integral_constant<bool,
                       __storage_traits::propagate_on_container_copy_assignment::value>());}

 vector<bool, _Allocator>::__vallocate(size_type __n)
 {
     if (__n > max_size())
         this->__throw_length_error();
     __n = __external_cap_to_internal(__n);
     this->__begin_ = __storage_traits::allocate(this->__alloc(), __n);
     this->__size_ = 0;
     this->__cap() = __n;
+#ifdef DATAFLOW_SANITIZER
+    __dfsan_labels_.resize(__n, 0);
+#endif    
 }
 
 template <class _Allocator>
 void
 vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT
 {
     if (this->__begin_ != nullptr)
     {

 inline _LIBCPP_INLINE_VISIBILITY vector<bool, _Allocator>::vector(vector&& __v)
 #if _LIBCPP_STD_VER > 14
     _NOEXCEPT
 #else
     _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
 #endif
     : __begin_(__v.__begin_),
       __size_(__v.__size_),
-      __cap_alloc_(_VSTD::move(__v.__cap_alloc_)) {
+#ifdef DATAFLOW_SANITIZER
+      __dfsan_labels_(_VSTD::move(__v.__dfsan_labels_)),
+#endif
+      __cap_alloc_(_VSTD::move(__v.__cap_alloc_))
+{
     __v.__begin_ = nullptr;
     __v.__size_ = 0;
     __v.__cap() = 0;
 }
 
 template <class _Allocator>
 vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a)
     : __begin_(nullptr),
       __size_(0),
       __cap_alloc_(0, __a)
 {
     if (__a == allocator_type(__v.__alloc()))
     {
         this->__begin_ = __v.__begin_;
         this->__size_ = __v.__size_;
         this->__cap() = __v.__cap();
+#ifdef DATAFLOW_SANITIZER
+        this->__dfsan_labels_ = std::move(__v.__dfsan_labels_);
+#endif
         __v.__begin_ = nullptr;
         __v.__cap() = __v.__size_ = 0;
     }
     else if (__v.size() > 0)
     {
         __vallocate(__v.size());
         __construct_at_end(__v.begin(), __v.end());
     }

 vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
     _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
 {
     __vdeallocate();
     __move_assign_alloc(__c);
     this->__begin_ = __c.__begin_;
     this->__size_ = __c.__size_;
     this->__cap() = __c.__cap();
+#ifdef DATAFLOW_SANITIZER
+    this->__dfsan_labels_ = std::move(__c.__dfsan_labels_);
+#endif
     __c.__begin_ = nullptr;
     __c.__cap() = __c.__size_ = 0;
 }
 
 #endif  // !_LIBCPP_CXX03_LANG
 
 template <class _Allocator>
 void
_NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
                 __is_nothrow_swappable<allocator_type>::value)
 #endif
 {
     _VSTD::swap(this->__begin_, __x.__begin_);
     _VSTD::swap(this->__size_, __x.__size_);
     _VSTD::swap(this->__cap(), __x.__cap());
     _VSTD::__swap_allocator(this->__alloc(), __x.__alloc(),
         integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>());
+#ifdef DATAFLOW_SANITIZER
+    _VSTD::swap(__dfsan_labels_, __x.__dfsan_labels_);
+#endif
 }
 
 template <class _Allocator>
 void
 vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
 {
     size_type __cs = size();
     if (__cs < __sz)