Почему GCC-O3 вызывает бесконечное std :: distance с итераторами фильтров по std :: deque?

Question

После долгих страданий и страданий я обнаружил очень странное поведение, когда std::distance никогда не возвращается, если задан диапазон boost::filter_iterator с по сравнению с std::deque. Похоже, что проблема уникальна для GCC (6.1+) с оптимизацией -O3. Вот пример, демонстрирующий поведение нарушителя:

#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; 
} 

Некоторые наблюдения:

• GCC с оптимизаций -O2 или меньше отдачи, как и ожидалось.
• Clang (3.8) возвращает правильный ответ с любым уровнем оптимизации.
• Изменение std::deque до std::vector или std::list приводит к ожидаемому поведению.
• Важный вопрос: 14; что-то меньшее, и проблема исчезает.
• Важное значение имеет sizeof(Foo); удаление s или a заставляет проблему уйти.
• Захват test по ссылке или просто по сравнению с постоянным выражением (например, foo.bar == " ") приводит к нормальному поведению.
• Предупреждений о компиляторе нет (с -Wall -Wextra -pedantic).
• Valgrind сообщает об ошибках.
• Используйте fsanitize=undefined, и проблема исчезнет.

Что происходит?

Answer 1

Такое поведение было связано с GCC bug, вызванной плохой оптимизации векторизации. Теперь вышло исправление, которое должно появиться в GCC 6.3.

Для тех, кто связан с GCC 5.4 - 6.2, опция компилятора -fno-tree-slp-vectorize «исправит» проблему.

Answer 2

Я думаю, что эти выводы ниже могут быть полезны как для улучшения отчета об ошибке, так и для использования в вашем коде для решения этой проблемы.

Отладка оптимизированного вывода и воспроизведение с помощью флагов оптимизации и с незначительными изменениями кода Я пришел к выводу о конкретных флагах оптимизации, которые вызывают ошибку.

Набор опций:

-O -fno-auto-inc-dec -fno-branch-count-reg -fno-combine-stack-adjustments -fno-compare-elim -fno-cprop-registers -fno-dce -fno-defer-pop -fno-delayed-branch -fno-dse -fno-forward-propagate -fno-guess-branch-probability -fno-if-conversion2 -fno-if-conversion -fno-inline-functions-called-once -fno-ipa-pure-const -fno-ipa-profile -fno-ipa-reference -fno-merge-constants -fno-move-loop-invariants -fno-reorder-blocks -fno-shrink-wrap -fno-split-wide-types -fno-ssa-backprop -fno-ssa-phiopt -fno-tree-bit-ccp -fno-tree-ccp -fno-tree-ch -fno-tree-coalesce-vars -fno-tree-phiprop -fno-tree-sink -fno-tree-slsr -fno-tree-dse -fno-tree-forwprop -fno-tree-fre -fno-unit-at-a-time -fno-tree-ter -fno-tree-sra -fno-tree-copy-prop -fstrict-aliasing -ftree-slp-vectorize -std=c++14 

Извините за что длинный сет, но то, что я на самом деле хотел было что-то вроде: -O0 -ftree-copy-prop -ftree-pta -ftree-dce -fstrict-aliasing -ftree-slp-vectorize (я пробовал с -OG также) плюс магические ступеньках O1 .. .

Обратите внимание, что только -O3 -f-no-tree-slp-vectorize уже исправить свое поведение, но и с помощью полных вариантов я послал отладки почти легко ...

Кроме того, это выглядит как существование оператора ==(string, string) генерирует путаница в компиляторе.

Если вы изучите код, вставленный ниже, где все прокомментированное кодом #if 0, когда активировано, работает вместо исходного кода, вы можете найти проблему, где я этого не сделал.

Обратите внимание, что оператор ==() даже не вызывается, потому что значение foo.a != '\0' всегда истинно в тесте. Поэтому похоже, что это существование заставляет компилятор генерировать плохой код.

Обратите внимание, что любой из прокомментированного кода внутри цикла также меняет поведение на ожидаемый, и именно поэтому я подозревал флаги векторизации для стартеров.

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

#include <boost/iterator/filter_iterator.hpp> 
#include <string.h> 

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

std::ostream& operator<<(std::ostream& os, const Foo& f) 
{ 
    os << f.bar << '/' << f.a; 
    return os; 
} 

int main() 
{ 
    std::deque<Foo> foos(14, {"abc"}); 
    const std::string test {"abc"}; 
    Foo other; 
    other.bar = "last"; other.a = 'l'; 
    foos.push_back(other); 
    other.bar = "first"; 
    other.a = 'f'; 
    foos.push_front(other); 
    // 
#if 0 
    const auto p = [test] (const auto& foo) { return foo.a != '\0'; }; 
#elif 0 
    const auto p = [test] (const auto& foo) { 
     bool rc = (foo.a != '\0'); 
     if (!rc) 
      rc = (foo.bar == std::string(test)); 
     return rc; 
    }; 
#elif 1 
    const auto p = [test] (const auto& foo) { 
     bool rc = (foo.a != '\0'); 
     if (!rc) 
      rc = (foo.bar == test); 
     return rc; 
    }; 
#endif 
    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(end, end) << std::endl; 
    std::cout << std::distance(begin, begin) << std::endl; 
    std::cout << std::distance(std::cbegin(foos), std::cend(foos)) << std::endl; 

    auto __first = begin; 
    auto __last = end; 

    int __n = 0; 
    //std::cout << __last << std::endl; 
    //std::deque<char> trace; 
    //Foo trace[21]; 
    const int max = foos.size(); 
    char trace[max+5]; memset(trace, 'c', sizeof(trace)); 

    std::cout << max << std::endl; 
    std::cout << *__last << std::endl; 

    while (__first != __last) 
    { 
     trace[__n] = (*__first).a; 
     //trace[__n] = (*__first); 
     //trace.push_back((*__first).a); 
     //std::cout << *__first << std::endl; 
     ++__n; 
     ++__first; 
     if (__n > max + 5) 
      break; 
     //std::cout << __n << std::endl; 
     //std::cout << (__first != __last) << std::endl; 
    } 

    for (auto f: trace) 
     std::cout << f << std::endl; 
    std::cout << "Tadaaaaa: " << __n << std::endl; 

    //std::cout << std::distance(begin, end) << std::endl; 

}