Why does GCC -O3 cause infinite std::distance with filter iterators over a std::deque?

Question

After much pain and misery, I've tracked down some very odd behaviour where std::distance never returns when given a range of boost::filter_iterators over a std::deque. It appears the problem is unique to GCC (6.1+) with -O3 optimisations. Here is an example demonstrating the offending behaviour:

#include <string>
#include <deque>
#include <iterator>
#include <iostream>

#include <boost/iterator/filter_iterator.hpp>

struct Foo
{
    std::string bar, s = "";
    char a = '\0';
};

int main()
{
    const std::deque<Foo> foos(14, {""});
    const std::string test {};
    const auto p = [test] (const auto& foo) { return foo.bar == test; };
    using boost::make_filter_iterator;
    const auto begin = make_filter_iterator(p, std::cbegin(foos), std::cend(foos));
    const auto end   = make_filter_iterator(p, std::cend(foos), std::cend(foos));
    std::cout << std::distance(begin, end) << std::endl;
}

Some observations:

• GCC with optimisations -O2 or less returns as expected.
• Clang (3.8) returns the correct answer with any optimisation level.
• Changing std::deque to std::vector or std::list results in expected behaviour.
• The 14 is critical; anything less and the problem disappears.
• The sizeof(Foo) is important; removing s or a makes the problem go away.
• Capturing test by reference, or just comparing to a constant expression (e.g. foo.bar == " ") results in normal behaviour.
• There are no compiler warnings (with -Wall -Wextra -pedantic).
• Valgrind reports no errors.
• Use fsanitize=undefined and the problem goes away.

What's going on?

Answer 1

This behaviour was due to a GCC bug caused by bad vectorisation optimisation. A fix has now been issued, which should appear in GCC 6.3.

For those stuck with GCC 5.4 - 6.2, the compiler option -fno-tree-slp-vectorize will 'fix' the issue.