Quand le compilateur vous surprend

• Exemple observé lors de la compilation d’une simple fonction de somme d’entiers, mettant en évidence les différences d’optimisation entre GCC et Clang
• GCC effectue dans la boucle une optimisation de type x*2 + 1, en additionnant deux nombres à la fois
• Clang supprime complètement la boucle et remplace le calcul par une forme fermée v(v - 1)/2
• Cette transformation fait passer le code de O(n) à O(1), avec une simplification mathématique réalisée automatiquement
• Même pour l’auteur, qui travaille avec les compilateurs depuis plus de 20 ans, c’est un exemple marquant du niveau d’optimisation intelligent des compilateurs

---

Optimisation de boucle dans GCC

• Lorsqu’on écrit une simple fonction de somme d’entiers, GCC génère un code de sommation efficace basé sur une boucle
  • Dans la boucle, l’instruction lea edx, [rdx+1+rax*2] est utilisée pour additionner deux nombres simultanément
  • Cela revient à transformer l’opération consistant à additionner x et x+1 en x*2 + 1
• En poussant le niveau d’optimisation à -O3, la boucle est traitée plus rapidement grâce à l’addition parallèle (vectorization)
• Cette approche est une forme d’optimisation traditionnelle qui maximise l’efficacité des opérations tout en conservant la boucle

Optimisation mathématique dans Clang

• En compilant le même code avec Clang, la boucle disparaît complètement
  • Clang vérifie d’abord si la valeur d’entrée est positive, puis effectue le calcul à l’aide d’une série d’instructions lea, imul et shr
  • Au final, le calcul est transformé en (v² - v)/2, c’est-à-dire en forme fermée de la somme d’entiers
• Cette transformation élimine la boucle et la remplace par un calcul en temps constant (O(1))
• L’auteur décrit ce résultat comme le fait d’avoir « trouvé par lui-même la solution mathématique de la somme d’entiers »

Développement de la formule

• En retraçant mathématiquement le code assembleur généré par Clang, on obtient la transformation suivante
  • v + ((v - 1)(v - 2) / 2) - 1
  • En développant et en simplifiant, on obtient (v² - v)/2
• Au final, on arrive à la forme v(v - 1)/2, qui correspond à la formule de la somme de 1 à v
• Ce processus est présenté comme un exemple d’optimisation où le compilateur reconnaît un motif mathématique

Fonctionnement intelligent du compilateur

• La raison pour laquelle Clang utilise cette séquence d’instructions particulière est expliquée par des considérations de prévention des débordements et de suivi des variables d’induction
• Même si la cause exacte de son fonctionnement interne n’est pas parfaitement claire, le résultat est attribué à la logique d’optimisation interne complexe de Clang
• L’auteur qualifie cette découverte d’« expérience à la fois humble et inspirante »

Conclusion et contexte de la série

• Cet article est le 24e billet de la série « Advent of Compiler Optimisations 2025 »
• Il explore la manière dont les compilateurs parviennent, par transformation du code, à simplifier mathématiquement les calculs et améliorer les performances
• L’auteur souligne que « les compilateurs continuent de me surprendre », mettant en avant cet émerveillement technique qui perdure malgré une longue expérience