Pourquoi GCC -O3 provoque-t-il une infinité de std::distance avec des itérateurs de filtre sur un std::deque ?

Question

Après beaucoup de peine et de misère, j'ai trouvé un comportement très étrange où std::distance ne revient jamais lorsqu'on lui donne une gamme de boost::filter_iterator sur une std::deque . Il semble que le problème soit unique à GCC (6.1+) avec -O3 optimisations. Voici un exemple démontrant le comportement fautif :

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

Quelques observations :

• GCC avec optimisations -O2 ou moins revient comme prévu.
• Clang (3.8) renvoie la réponse correcte avec n'importe quel niveau d'optimisation.
• Changer std::deque a std::vector o std::list entraîne un comportement attendu.
• El 14 est critique ; si elle est inférieure, le problème disparaît.
• El sizeof(Foo) est important ; la suppression s o a fait disparaître le problème.
• Capturer test par référence, ou simplement en le comparant à une expression constante (par ex. foo.bar == " " ) entraîne un comportement normal.
• Il n'y a pas d'avertissement du compilateur (avec -Wall -Wextra -pedantic ).
• Valgrind ne signale aucune erreur.
• Utilice fsanitize=undefined et le problème disparaît.

Qu'est-ce qui se passe ?

Answer 1

Je pense que les résultats ci-dessous peuvent être utiles à la fois pour améliorer le rapport de bogue et aussi pour l'utiliser dans votre code pour contourner le problème.

En déboguant la sortie optimisée, en jouant avec les drapeaux d'optimisation et en modifiant légèrement le code, je suis parvenu à la conclusion que les drapeaux d'optimisation spécifiques sont à l'origine de l'erreur.

L'ensemble des options sont :

-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

Désolé pour cette longue série, mais ce que je voulais vraiment, c'était quelque chose comme ça : -O0 -ftree-copy-prop -ftree-pta -ftree-dce -fstrict-aliasing -ftree-slp-vectorize (j'ai essayé avec -Og aussi) plus les étapes magiques de O1...

Notez que juste -O3 -f-no-tree-slp-vectorize corrigera déjà le comportement, mais en utilisant les options complètes que j'ai envoyées, le débogage est presque facile...

De plus, il semble que l'existence de l'opérateur ==(string, string) génère la confusion dans le compilateur.

Si vous examinez le code collé ci-dessous où tout le code commenté par #if 0, lorsqu'il est activé, fonctionne à la place du code original, vous trouverez peut-être le problème là où je ne l'ai pas trouvé.

Notez que le ==() n'est même pas appelé car l'opérateur foo.a != '\0' est toujours vrai dans le test. Il semble donc que son existence incite le compilateur à générer le mauvais code.

Notez également que n'importe quel code commenté à l'intérieur de la boucle change également le comportement en celui attendu et c'est pourquoi j'ai suspecté les drapeaux de vectorisation pour commencer.

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

}

Answer 2

Ce comportement était dû à une Bogue de GCC causés par une mauvaise optimisation de la vectorisation. Un correctif a maintenant été publié, qui devrait apparaître dans GCC 6.3.

Pour ceux qui sont coincés avec GCC 5.4 - 6.2, l'option du compilateur -fno-tree-slp-vectorize va "régler" le problème.