Licence CC BY

Attention aux optimisations de Clang !

Quand le compilateur optimise trop

Publié :
Auteur :
Catégorie :
Temps de lecture estimé : 7 minutes
Ce billet a été promu en article.

Si vous voulez en savoir plus sur les diverses optimisations réalisées par les compilateurs, allez consulter ce très bon tutoriel.

Bonjour !

J’écris ce billet (mon premier, soyez indulgents ^^ ) pour vous montrer un petit exemple dans lequel les optimisations mises en place lors de la compilation peuvent créer des comportements inattendus, selon le programme utilisé. Dans le cas présenté ci-dessous, en langage C, le problème se produit avec Clang mais pas avec GCC.

Le code

Le code que nous allons utiliser va servir à chercher un contre-exemple de la conjecture de Syracuse. Pour rappel, la suite de Syracuse se construit de la façon suivante : on choisit un entier supérieur à 0, s’il est pair on le divise par 2 et s’il est impair on le multiplie par 3 et on ajoute 1. Puis on recommence avec la nouvelle valeur et ainsi de suite.

u0=NNu_0=N \in \mathbb{N}^*

nN , un+1={un2si un pair3×un+1si un impair\forall n \in \mathbb{N}~,~u_{n+1}=\left\lbrace\begin{array}{ll} \dfrac{u_n}{2} & \text{si }u_n\text{ pair} \\3\times u_n+1 & \text{si }u_n\text{ impair}\end{array}\right.

Il semblerait que la suite de Syracuse se termine systématiquement par la boucle 4 > 2 > 1 > 4 > … quel que soit le nombre de départ. Mais la conjecture n’a encore jamais été démontrée, il se pourrait donc qu’il existe des nombres pour lesquels la suite ne retombe jamais à 1.

Le code ci-dessous va chercher un éventuel contre-exemple en testant la suite de Syracuse pour chaque nombre. Tant qu’il n’a pas trouvé, il reste en boucle infinie. Seule la découverte d’un contre-exemple met fin au programme.

// Cherche un contre-exemple de la conjecture de Syracuse
// dont le vol ne finit pas par 4 > 2 > 1 > 4 > ...

#include <stdio.h>

// Valeur maximum à tester (unsigned int)
// pour éviter l'overflow lors du 3*x+1
#define MAXVAL 1000000000

// Retourne 1 si un contre-exemple est trouvé, et boucle sinon
int syracuse(void)
{
    unsigned int nombre, vol, i;
    
    while(1) // Boucle infinie s'il n'y a pas de contre-exemple
    {
        for(nombre = 1; nombre <= MAXVAL; nombre++) // On teste chaque entier
        {
            vol = nombre;
            for(i = 0; i <= MAXVAL; i++)
            {
                if(vol == 1) break; // On retombe à 1, on passe à l'entier suivant
                if(vol >= MAXVAL) break; // Vol trop grand, on passe à l'entier suivant
                
                if(vol&1) vol = 3 * vol + 1; // Impair
                else vol = vol / 2; // Pair
            }
            
            // Si ici on a fait MAXVAL+1 étapes sans retomber à 1,
            // on a forcément fait une boucle à un moment, différente de 4 > 2 > 1 !
            if(i == MAXVAL + 1) return 1; // Contre-exemple trouvé
        }
    }
    return 0; // Code mort
}

int main(void)
{
    if(syracuse())
    {
        printf("Contre-exemple trouvé !\n");
    }
    return 0;
}

On est bien d’accord, ce programme est idiot, ne sert à rien, est mal foutu et occupe inutilement le CPU. Il n’y a aucune chance pour qu’il trouve un contre-exemple et il ne sert qu’à illustrer ce billet avec un cas plus ou moins concret.

Avec GCC

Bon, commençons par compiler notre ficher syracuse.c sans aucune optimisation avec GCC. La commande (avec Ubuntu) est la suivante :

$ gcc -O0 -o test_syracuse syracuse.c

On exécute alors le programme et…

Ça mouline…
Ça mouline…

Je vous laisse attendre chez vous un résultat aussi longtemps que vous voulez, si vous souhaitez mettre votre patience à l’épreuve, mais moi je vais tuer le processus. :P

On pouvait s’y attendre, puisque plein d’autres mathématiciens avant nous ont déjà essayé avec des programmes bien plus performants. Tentons à présent d’utiliser toutes les optimisations de GCC avec la commande suivante :

$ gcc -O3 -o test_syracuse syracuse.c

Vous pouvez essayer vous-mêmes ou me faire confiance, le comportement est exactement le même (à savoir : rien à l’écran ;) ). Du coup comment savoir si les optimisations sont bien présentes ? On peut regarder le nombre de lignes du code assembleur (fichier syracuse.s) généré par GCC avant la création de l’exécutable final.

$ gcc -O0 -S syracuse.c
$ wc -l syracuse.s
143 syracuse.s
$ gcc -O3 -S syracuse.c
$ wc -l syracuse.s
105 syracuse.s

On constate qu’il y a 143 lignes sans les optimisations et seulement 105 avec, donc le compilateur a bien fait son travail.

Avec Clang

Passons maintenant à Clang pour compiler notre ficher syracuse.c, toujours sans aucune optimisation pour commencer. La commande est la suivante :

$ clang -O0 -o test_syracuse syracuse.c

Quand on exécute le programme, ça alors ! il ne se passe toujours rien.

Ça mouline encore…
Ça mouline encore…

Je vous sens presque déçus. :D Allez, on ajoute à présent les optimisations de Clang et on regarde le résultat :

$ clang -O3 -o test_syracuse syracuse.c
On a trouvé ! O_o
On a trouvé ! O_o

Hein ?!? :waw: Le programme s’arrête instantanément en annonçant sa magnifique victoire, tuant une conjecture vieille de 90 ans ! o_O

Petit indice pour la suite : le problème vient de Clang, pas des maths. :-°

Alors que s’est-il passé ? Pourquoi ce résultat surprenant ? Il faut analyser le code assembleur généré par Clang pour mieux comprendre. Je vous rassure, pas besoin de connaître l’assembleur en détail, on ne va s’occuper que de quelques instructions.

Pour être exact, Clang ne produit pas vraiment de l’assembleur. En fait, il va compiler le C vers un langage qui ressemble à de l’assembleur et qui va ensuite être pris en charge par la LLVM (Low Level Virtual Machine) pour devenir un exécutable. LLVM est ainsi une seule infrastructure indépendante qui regroupe différents compilateurs selon les langages : pour le C, elle s’associe donc avec Clang. Dans la suite du billet, ces détails ne sont pas très importants donc on fera comme si c’était simplement de l’assembleur, mais c’est pour ça que je ne vais pas comparer les tailles des fichiers entre GCC et Clang.

Plus d’informations sur Clang et sur la LLVM. Le logo de ce billet est d’ailleurs celui de LLVM.

La commande pour obtenir le fichier assembleur syracuse.s sans optimisation est la suivante :

$ clang -O0 -S syracuse.c

Le fichier fait 113 lignes, nous ne nous intéresserons qu’à la fonction main :

main:                                   # @main
# %bb.0:
    pushl   %ebp
    movl    %esp, %ebp
    subl    $24, %esp
    movl    $0, -4(%ebp)
    calll   syracuse
    cmpl    $0, %eax
    je  .LBB1_2
# %bb.1:
    leal    .L.str, %eax
    movl    %eax, (%esp)
    calll   printf
    movl    %eax, -8(%ebp)          # 4-byte Spill
.LBB1_2:
    xorl    %eax, %eax
    addl    $24, %esp
    popl    %ebp
    retl

Ainsi, sans optimisation, on a les actions suivantes :

  • Le programme appelle bien la fonction syracuse à la ligne 7 (calll).
  • Puis, ligne 8, la valeur de retour est comparée à 0 (cmpl : compare).
  • Si c’est le cas (mais ça n’arrive jamais) on saute directement de la ligne 9 à la ligne 15 (je : jump if equal) puis fin.
  • Sinon, le code continue jusqu’à la ligne 13 qui appelle printf (calll) et affiche la phrase, puis fin.

C’est bien le comportement attendu. Comparons maintenant avec les optimisations :

$ clang -O3 -S syracuse.c

Le fichier fait cette fois 80 lignes, regardons à nouveau la fonction main :

main:                                   # @main
# %bb.0:
    subl    $12, %esp
    movl    $.Lstr, (%esp)
    calll   puts
    xorl    %eax, %eax
    addl    $12, %esp
    retl

C’est beaucoup plus court. Et remarquez-vous un problème ? L’appel à la fonction syracuse a totalement disparu ! :o Et en plus, même printf est parti ! Ce code optimisé réalise uniquement un appel à la fonction puts (ligne 5) et s’arrête.

Voilà donc pourquoi le programme optimisé avec Clang affiche immédiatement « Contre-exemple trouvé ! » et se termine.

Explications

La mise en place à priori étrange de cette optimisation à l’extrême s’explique par la structure particulière du code de la fonction syracuse : tout est de la faute de la boucle infinie. Elle est sans effet de bord (elle ne modifie rien en dehors de ses variables locales) et provoque ainsi un comportement indéterminé en C.

Chaque compilateur possède ses propres règles et méthodes d’optimisation, plus ou moins efficaces et justes. Et en particulier dans le cas d’un comportement indéterminé, chacun peut faire comme bon lui semble, au risque d’avoir des résultats inattendus comme ici.

GCC a décidé dans un cas comme celui-ci de ne rien faire et de laisser la boucle en place. Concernant Clang, en revanche, il a constaté une chose : quel que soit le temps passé dans la boucle, quels que soient les calculs effectués à l’intérieur, la fonction ne peut retourner qu’une seule et unique valeur : un 1 (ligne 31). Du coup, son optimisation est simple et radicale : inutile d’appeler syracuse, la ligne 39 sera toujours vraie et il ne reste plus qu’à afficher directement le texte. Pas mal comme amélioration, non ? :soleil:

Pour éviter ce problème et obliger Clang a tenir compte de l’évolution des variables au sein de la boucle, la solution est d’utiliser le mot-clé volatile. La ligne 13 devient alors volatile unsigned int nombre, vol, i;.

Et concernant le printf ? Cette fois, GCC et Clang ont tous les deux remplacé la fonction par un puts. En effet, la ligne 41 satisfait trois critères qui permettent cette optimisation :

  • La chaîne de caractères est constante, elle n’affiche pas le contenu d’une variable.
  • La chaîne de caractères se termine par un retour à la ligne ('\n').
  • On ne récupère pas la valeur retournée par le printf après l’affichage.

Dans ce cas, le résultat de puts est très exactement le même que celui de printf, mais ce dernier est moins rapide et efficace car il doit analyser chaque caractère de la chaîne pour vérifier s’il n’y a pas des formats à interpréter (par exemple %d, %c, %f…). Donc les compilateurs ont tout intérêt à utiliser puts à la place.

Voilà, c’est la fin de ce billet. ^^ Si un jour vous constatez des comportements bizarres dans vos programmes sans pouvoir l’expliquer par rapport au code C qui semble correct, pensez peut-être à volatile. Que ce soit pour des projets scolaires ou professionnels, il m’a déjà aidé plusieurs fois !



11 commentaires

Je trouve cet article un peu confus.

Déjà, tu dis que ce code contient une boucle infinie. Est-ce réellement le cas ? Si j’ai bien compris, la boucle est infinie si la conjecture de Syracuse est vraie, donc personne ne sait si la boucle est réellement infinie. On a une boucle "qui pourrait être infinie", ou "dont on ne sait pas si elle est finie".

Ensuite, tu dis que cette boucle (sans actions observables) est un comportement indéfini en C (undefined behavior). Il me semble qu’une boucle réellement infinie est un comportement indéfini en C; mais cette boucle-ci ne l’est pas, c’est seulement une boucle "qui pourrait être infinie". Je crois qu’il serait plus correct de dire : comme une boucle silencieuse infinie a un comportement indéfini, le compilateur peut se comporter avec toutes les boucles silencieuses comme si elle terminait. Toutes les exécutions définies de cette boucle exécutent return 1, donc Clang (qui par du principe que son entrée est un programme C bien défini) renvoie toujours 1.

Enfin, il y a une erreur d’interprétation du problème. Le problème n’est pas que Clang n’optimise pas correctement ce programme, c’est que ce programme C est sans doute incorrect. En C, un programme dont le comportement est indéfini est invalide, ce n’est pas un programme C correct. Ici, le programme est peut-être défini (si la conjecture de Syracuse est fausse), mais peut-être indéfini. C’est la façon d’écrire ce programme qui pose problème, et non Clang qui, en soit, a fait un choix parfaitement correct, valide, autorisé par la norme. C’est le programmeur qui s’est trompé, pas le compilateur — si on considère "la norme du langage" comme juge de cette dispute.

C’est important de faire passer cette idée : un programme avec un comportement indéfini est incorrect, ce n’est pas l’optimiseur qui se trompe mais le programmeur qui se trompe. C’est important en C, où presque tous les programmes sont incorrects. C’est contre-intuitif, et le signe d’un langage qui ne peut pas être utilisé de façon très fiable, mais c’est comme cela que la programmation en C est pensée (par les gens qui implémentent le langage) et il faut bien le comprendre.

Pour finir, je me demande si le détour par l’assembleur est bien utile ici. Le comportement du programme peut être expliqué uniquement par les règles du langage C et le comportement des compilateurs : Clang a réussi à comprendre que ton comportement défini de ce programme renvoie 1, donc il l’optimise en renvoyant 1 immédiatement. Je pense que tu aurais pu passer un peu plus de temps à expliquer le concept de boucle silencieuse infinie et de comportement défini/indéfini, et moins de temps sur l’assembleur qui observe (… comme le fait de lancer le programme) mais n’explique pas.

Édité par gasche

+6 -0

Salut,

Désolé si le billet donne l’impression que Clang est en tort et a fait une erreur, ce n’est pas du tout ce que je voulais dire. :( Je voulais juste montrer que chaque compilateur peut réagir différemment dans le cas d’un comportement indéterminé, et qu’il n’y a pas de bons ou de mauvais choix. Simplement, ici, GCC laisse la boucle et tout semble normal contrairement à Clang qui donne à l’utilisateur une réponse inattendue. Donc on ne peut pas dire qu’il optimise mal, mais il fait un choix qui ne correspond pas à ce que l’utilisateur souhaitait. Mais oui je suis entièrement d’accord que le problème vient du code et pas des compilateurs. Mon programme d’exemple provoque volontairement un comportement indéfini pour bien montrer que si c’est mal codé, on peut s’attendre à avoir des résultats imprévus (ou pas, puisque la norme n’impose rien dans ce cas).

Quand je parle de boucle infinie, c’est simplement parce qu’il y a un while(1), donc le compilateur ne peut pas savoir en effet si on va en sortir ou non. Par contre, même dans une boucle réellement infinie, le choix de Clang est le même. Dans le code ci-dessous, il affiche directement "a = 200" :

#include <stdio.h>

int cpt(void)
{
    int i, a;
    while(1)
    {
        a = 0;
        for(i = 0; i <= 100; i++) a++;
        if(a == 200) return 1;
    }
    return 0;
}

int main(void)
{
    if(cpt()) printf("a = 200\n");
    return 0;
}

“I don’t love studying. I hate studying. I like learning. Learning is beautiful.” – Natalie Portman

+0 -0

Ça existe un mode gcc/clang pour jeter un programme indéfini selon la norme ? Ou, au moins certains cas comme celui-ci, qui semble assez facile à « détecter » ?

Merida is so cool · “Now that I have built my very own hammer, nothing looks like a nail anymore. ”

+0 -0

Quand je parle de boucle infinie, c’est simplement parce qu’il y a un while(1), donc le compilateur ne peut pas savoir en effet si on va en sortir ou non.

Attention, le compilateur est tout à fait capable de raisonner sur la présence de break ou de return à l’intérieur d’une boucle while(1) pour vérifier qu’elle termine correctement.

En fait en y repensant, je ne suis pas sûr qu’une boucle silencieuse infinie soit décrite comme un comportement indéfini par la norme — je me demande si elle ne dit pas juste qu’on peut toujours suppoer qu’une boucle silencieuse termine. Ce serait bien d’avoir des experts de C qui peuvent commenter sur ce que disent (ou ne disent pas) les normes sur ce point-là.

+0 -0

En effet, une boucle infinie sans effets de bord est un comportement indéterminé en C (cppreference), les règles sont légèrement plus détaillé dans l’article sur le C++ (c++ memory model)

Le compilateur est donc face à deux choix:

  • soit il est possible d’atteindre le return 1, auquel cas ça sera la valeur retourné par la fonction.
  • soit il n’est pas possible d’atteindre le return 1, auquel cas on est face à une boucle infini sans effet de bord.

Étant donné que le deuxième choix est un comportement indéterminé, le compilateur peut simplement dire "ça ne peux pas arriver" et en conclure que la fonction retourne toujours 1 et ne produit aucun effet de bord.

Il est aussi intéressant de comprendre que le raisonnement de "ça ne peux pas arriver" peux aussi être appliqué pour supposer que ce qui amène à un comportement indéterminé est impossible.

Voici un autre exemple de ce qu’un compilateur peux faire:

if (ptr == NULL) printf("ptr is NULL");
return *ptr;

ptr ne peux pas être NULL sur la deuxième ligne (parce que ce serait un comportement indéterminé), par conséquence on ne rentre jamais dans la condition et on n’appelle jamais printf. Le code peux donc être remplacé par return *ptr;.

+0 -0

Bon, je suis allé vérifier dans la norme, et en fait ce n’est pas un comportement indéfini — le standard dit seulement que les boucles silencieuses "peuvent être supposées finies" — cf. le point 6 du paragraphe 6.8.6 (Iteration statements) de la norme C11, que j’ai trouvé à partir de ce message de Hans Boehm.

Par exemple, le programme suivant:

while (1) {};
return 1;

a le droit de boucler à l’infini ou de renvoyer 1, mais pas de renvoyer 2 ou 3 ou quoi que soit d’autre. Si while (1) {}; était un comportement indéfini, alors la valeur de retour 2 serait un comportement valide sur ce programme.

+2 -0

cf. le point 6 du paragraphe 6.8.6 (Iteration statements) de la norme C11, que j’ai trouvé à partir de ce message de Hans Boehm.

Paragraphe 6.8.5, mais j’approuve. ;)

An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate.

ISO/IEC 9899:201x, doc. N1570, 6.8.5, Iteration statements, al. 6, p. 150

Toutefois, cela ne s’applique pas ici étant donné que la condition est une expression contante.

Édité par Taurre

+1 -0

Oh final, c’est vraiment une optimisation abusée de Clang ?

ache.one                 🦹         👾                                🦊

+0 -0

C’est une optimisation extrême due à la structure particulière du code, mais c’est un choix que Clang a le droit de faire.

“I don’t love studying. I hate studying. I like learning. Learning is beautiful.” – Natalie Portman

+0 -0

Oh final, c’est vraiment une optimisation abusée de Clang ?

ache

De mon côté j’ai un doute sur le fait que cette optimisation respecte la norme ou non. Techniquement, les compilateurs peuvent faire à peu près ce qu’ils veulent du moment que le comportement « visible » du programme est le même que si l’exécution avait eu lieu sur la « machine abstraite » décrite dans la norme (en gros, si l’exécution n’est pas optimisée).

The least requirements on a conforming implementation are:

  • Accesses to volatile objects are evaluated strictly according to the rules of the abstract machine.
  • At program termination, all data written into files shall be identical to the result that execution of the program according to the abstract semantics would have produced.
  • The input and output dynamics of interactive devices shall take place as specified in 7.21.3. The intent of these requirements is that unbuffered or line-buffered output appear as soon as possible, to ensure that prompting messages actually appear prior to a program waiting for input.

This is the observable behavior of the program.

ISO/IEC 9899:201x, doc. N1570, 5.1.2.3, Program execution, al. 6, p. 15.

De mon point de vue, le point 2 n’est pas respecté parce que si l’exécution a lieu sans optimisation, il n’y a pas de données écrites, mais ce n’est que mon avis et le cas présenté est assez particulier. Du coup, utiliser le qualificateur volatile pour éviter toute ambiguïté est probablement la meilleure solution.

Édité par Taurre

+0 -0

Le problème majeur de ce programme, c’est qu’il possède une boucle probablement infini sans produire le moindre effet de bord. C’est quelque chose qui n’arrive quasiment que dans des exemples créé juste pour montrer que c’est un comportement possible d’un compilateur.

Plutôt que d’utiliser volatile, n’importe quel programme qui essaye vraiment de faire quelque chose d’utile va avoir des effets de bords réguliers affin d’avoir des informations sur l’avancement du programme. Typiquement, lors de l’écriture d’un programme qui va vérifier s’il existe un nombre qui possède certaines caractéristiques, un code typique fera:

int i = 0;
while (1) {
  if (hasProperty(i)) {
    printf("found %d!", i);
    return;
  }
  if (i % 10000 == 0) {
    printf("i=%d", i);
  }
  ++i;
}

Dans ce cas, la boucle infini a un effet de bord et ne pourra pas être simplement supprimé.

Édité par Berdes

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte