Pourquoi les compilateurs C++ modernes n'optimisent-ils pas simplement les boucles simples comme celle-ci ? (Clang, MSVC)

Question

Lorsque je compile et exécute ce code avec Clang (-O3) ou MSVC (/O2)...

#include 
#include 

static int const N = 0x8000;

int main()
{
    clock_t const start = clock();
    for (int i = 0; i < N; ++i)
    {
        int a[N];    // Jamais utilisé en dehors de ce bloc, mais pas optimisé
        for (int j = 0; j < N; ++j)
        {
            ++a[j];  // C'est aussi un comportement indéfini, mais Clang ne le voit pas
        }
    }
    clock_t const finish = clock();
    fprintf(stderr, "%u ms\n",
        static_cast((finish - start) * 1000 / CLOCKS_PER_SEC));
    return 0;
}

... la boucle n'est pas optimisée.

De plus, ni Clang 3.6 ni Visual C++ 2013 ni GCC 4.8.1 ne me dit que la variable est non initialisée !

Maintenant je réalise que le manque d'optimisation n'est pas un bug en soi, mais je trouve cela étonnant étant donné que les compilateurs sont censés être assez intelligents de nos jours. Il semble que même des techniques d'analyse de vieillesse datant d'une décennie devraient pouvoir prendre en charge l'optimisation de la variable a et donc de toute la boucle -- peu importe le fait que l'incrémentation de la variable est déjà un comportement indéfini.

Pourtant, seul GCC est capable de comprendre que c'est un no-op, et aucun des compilateurs ne me dit qu'il s'agit d'une variable non initialisée.

Pourquoi cela ? Qu'empêche une simple analyse de vivacité de dire au compilateur que a est inutilisé ? De plus, pourquoi le compilateur ne détecte-t-il pas que a[j] est non initialisé en premier lieu ? Pourquoi les détections existantes de variables non initialisées dans tous ces compilateurs ne peuvent-elles pas attraper cette erreur évidente ?

Answer 1

Changez le type de a en unsigned int[N], et la boucle disparaît.

Ce qui précède est apparemment incorrect, le code généré n'est pas affecté par ce changement.

Alternativement, laissez a comme int[N] et changez le corps de la boucle pour

a[j] = 0;
++a[j];

et elle disparaît complètement à nouveau.

N'ai essayé cela qu'avec clang.

Je suppose que clang est réticent à optimiser certains types de comportements indéfinis.

Answer 2

Le comportement indéfini est sans importance ici. Remplacer la boucle interne par :

    for (int j = 1; j < N; ++j)
    {
        a[j-1] = a[j];
        a[j] = j;
    }

... a le même effet, du moins avec Clang.

Le problème est que la boucle interne charge à la fois de a[j] (pour un certain j) et stocke à a[j] (pour un certain j). Aucun des enregistrements ne peut être supprimé, car le compilateur pense qu'ils peuvent être visibles pour des charges ultérieures, et aucune des charges ne peut être supprimée, car leurs valeurs sont utilisées (comme entrée pour les enregistrements ultérieurs). En conséquence, la boucle a toujours des effets secondaires sur la mémoire, donc le compilateur ne voit pas qu'elle peut être supprimée.

Contrairement à la réponse de n.m., remplacer int par unsigned ne résout pas le problème. Le code généré par Clang 3.4.1 en utilisant int et en utilisant unsigned int est identique.

Answer 3

C'est une question intéressante en ce qui concerne l'optimisation. Je m'attends à ce que dans la plupart des cas, le compilateur traite chaque élément du tableau comme une variable individuelle lors de l'analyse du code mort. Et 0x8000 crée trop de variables individuelles à suivre, donc le compilateur n'essaie pas. Le fait que a[j] n'accède pas toujours au même objet pourrait également poser des problèmes pour l'optimiseur.

De toute évidence, différents compilateurs utilisent différentes heuristiques; un compilateur pourrait traiter le tableau comme un seul objet, et détecter qu'il n'a jamais affecté la sortie (comportement observable). Cependant, certains compilateurs pourraient choisir de ne pas le faire, sous prétexte que, généralement, c'est beaucoup de travail pour peu de gain : à quelle fréquence de telles optimisations seraient-elles applicables dans du code réel?

Answer 4

C'est en effet très intéressant. J'ai essayé votre exemple avec MSVC 2013. Ma première idée était que le fait que ++a[j] soit quelque peu indéfini est la raison pour laquelle la boucle n'est pas supprimée, car enlever cela changerait définitivement le sens du programme d'une sémantique indéfinie/incorrecte à quelque chose de significatif, donc j'ai essayé d'initialiser les valeurs avant mais les boucles n'ont pas disparu.

Ensuite j'ai remplacé ++a[j]; par a[j] = 0; ce qui a alors produit une sortie sans aucune boucle donc tout ce qui se trouve entre les deux appels à clock() a été supprimé. Je ne peux que spéculer sur la raison. Peut-être que l'optimiseur n'est pas capable de prouver que l'opérateur++ n'a pas d'effets secondaires pour une raison quelconque.

Answer 5

++a[j];  // C'est aussi un comportement indéfini, mais Clang ne le voit pas

Dites-vous que c'est un comportement indéfini parce que les éléments du tableau ne sont pas initialisés?

Si tel est le cas, bien que ce soit une interprétation courante de la clause 4.1/1 de la norme, je pense que c'est incorrect. Les éléments sont 'non initialisés' dans le sens que les programmeurs utilisent généralement ce terme, mais je ne crois pas que cela corresponde exactement à l'utilisation du terme par la spécification C++.

En particulier, C++11 8.5/11 indique que ces objets sont en réalité initialisés par défaut, ce qui me semble être mutuellement exclusif avec le fait d'être non initialisé. La norme précise également que pour certains objets, être initialisés par défaut signifie que 'aucune initialisation n'est effectuée'. Certains pourraient supposer que cela signifie qu'ils ne sont pas initialisés, mais cela n'est pas spécifié et je le comprends simplement comme signifiant qu'aucune telle exécution n'est requise.

La spécification précise cependant que les éléments du tableau auront des valeurs indéterminées. C++ spécifie, par référence à la norme C, que des valeurs indéterminées peuvent être soit des représentations valides, légalement accessibles normalement, soit des représentations piège. Si les valeurs indéterminées particulières des éléments du tableau se révèlent être toutes des représentations valides (et aucune n'est INT_MAX, évitant le débordement) alors la ligne ci-dessus ne déclenche aucun comportement indéfini en C++11.

Étant donné que ces éléments de tableau pourraient être des représentations piège, il serait parfaitement conforme à Clang de les traiter comme garanties pour être des représentations piège, choisissant effectivement de rendre le code UB afin de créer une opportunité d'optimisation.

Même si Clang ne fait pas cela, il pourrait quand même choisir d'optimiser en fonction du flux de données. Clang sait le faire, comme le montre le fait que si la boucle interne est légèrement modifiée, les boucles sont bien supprimées.

Alors, pourquoi la présence (optionnelle) de UB semble-t-elle bloquer l'optimisation, alors que UB est généralement considéré comme une opportunité pour plus d'optimisations?

Ce qui pourrait se passer, c'est que Clang a décidé que les utilisateurs veulent un piégeage en fonction du matériel. Ainsi, plutôt que de considérer les pièges comme une opportunité d'optimisation, Clang doit générer du code qui reproduit fidèlement le comportement du programme sur le matériel. Cela signifie que les boucles ne peuvent pas être éliminées en fonction du flux de données, car cela pourrait éliminer les pièges matériels.

---

C++14 met à jour le comportement de sorte que l'accès à des valeurs indéterminées lui-même produit un comportement indéfini, indépendamment du fait de considérer ou non la variable comme non initialisée : http://stackoverflow.com/a/23415662/365496