Attention aux optimisations de Clang !

• La revue de code, c'est important !
• Récap' communautaire #9 — Novembre 2018

Bonjour !

J’écris cet article (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
• Avec GCC
• Avec Clang
• Explications

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.

$u_0=N \in \mathbb{N}^*$

$\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 <limits.h>
#include <stdio.h>

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

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

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…

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.

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 fichier 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.

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

$ clang -O3 -o test_syracuse syracuse.c

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

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.

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 ! 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 : elle comporte une boucle infinie avec une seule porte de sortie, l’instruction return 1 et ne produit aucun effet de bord.

Chaque compilateur possède ses propres règles et méthodes d’optimisation, plus ou moins efficaces et justes. 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 ?

Et concernant 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 ne comprend pas de formats, elle n’affiche donc 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 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 cet article.
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 !

• La revue de code, c'est important !
• Récap' communautaire #9 — Novembre 2018