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

[GN⁺]

Commentaires sur Hacker News

• Le code qui implémente cette fonctionnalité se trouve dans ScalarEvolution.cpp et IndVarSimplify.cpp

  • C’est à la fois impressionnant et un peu inquiétant de voir qu’un seul fichier contient près de 16 000 lignes de code

• Ce genre d’optimisation est vraiment intéressant
  Les optimisations de compilateur se divisent globalement en deux catégories — analyse de flux de données et reconnaissance de motifs avec substitution
  La première est efficace pour la plupart des programmes, tandis que la seconde consiste à accumuler des motifs avec un rendement de plus en plus faible
  L’exemple lié est intelligent et amusant, mais en pratique il n’a pas beaucoup de valeur. En 45 ans, je n’ai jamais écrit une boucle de ce type
  Bien sûr, ce genre de substitution de motifs reste important, car il est généré automatiquement à partir de code de haut niveau
  Pour être honnête, c’est peut-être juste moi qui râle un peu parce que mon optimizer n’est pas capable de faire ce genre d’optimisation

  • En réalité, cela a peut-être plus de valeur qu’on ne le pense. Le SCEV (Scalar Evolution) de LLVM sert surtout à l’analyse et permet aussi d’autres optimisations au-delà des boucles mathématiques
  • On ne voit pas clairement quelle optimisation a été effectuée. À l’époque où je développais un compilateur de niche, je me souviens avoir été surpris de voir le compilateur traiter plus intelligemment que les optimisations que j’avais écrites moi-même

• Il s’agit d’une fonctionnalité appelée Scalar Evolution (SCEV), et son implémentation dans LLVM est assez complexe

• Il existe un cas d’optimisation similaire dans l’article « Do not optimize away »

  • L’explication du début de cet article est légèrement erronée. Le code additionne de 0 à N mais exclut N, donc le bon résultat est en réalité N(N-1)/2. Mathématiquement, la somme de 1 à N vaut N(N+1)/2, donc pour exclure la borne supérieure, il faut remplacer N par (N-1)
  • Je me demande si le compilateur ne pourrait pas quand même optimiser cela. Il pourrait sans doute générer une version avec constant folding et une version sans, puis brancher à l’exécution

• Ce qu’il y a de vraiment remarquable dans cette optimisation, c’est qu’elle est générique
  Ce qui impressionne, ce n’est pas simplement qu’elle reconnaisse le motif « somme d’une suite entière finie », mais qu’elle s’applique de façon générale

• J’ai l’impression que le compilateur pourrait ajouter davantage de closed forms. Je me demande si cela en vaudrait la peine
  Il y a un concept connexe avec les paires de Wilf–Zeilberger

• Une fois de plus, j’ai été surpris par un résultat où GCC est plus lent que Clang
  Même avec 20 ans d’avance, il arrive encore que GCC produise un code plus lent que Clang
  Autrefois, lors d’une extraction de bits, Clang s’en sortait avec deux décalages, alors que GCC en faisait trois

  • Il existe un grand écart générationnel en matière de technologie de compilation entre GCC et LLVM/Clang. GCC reste un projet impressionnant, mais j’ai entendu dire qu’il est structurellement difficile d’y appliquer des techniques d’optimisation modernes
  • En pratique, les performances des deux compilateurs sont similaires. Ils ont simplement des passes d’optimisation différentes, donc le résultat varie selon les cas
  • Au départ, GCC souffrait d’une conception idéaliste centrée sur la licence, ce qui nuisait à son extensibilité. C’est bien moins vrai aujourd’hui, mais son générateur de code reste complexe. À l’inverse, Clang a une structure plus simple, ce qui facilite l’implémentation des optimisations. Personnellement, je trouve aussi la sortie de MSVC et ICC plutôt bonne
  • C’était peut-être du code lié aux bitfields ? GCC est particulièrement faible sur cette partie

• Je me demande si quelqu’un a déjà tenté une optimisation qui remplace un problème de coloration de graphe (graph coloring) par une constante

  • La coloration de graphe est un problème NP-hard, donc difficile à transformer en O(1). Pour les graphes planaires, le théorème des quatre couleurs s’applique, mais on n’obtient pas toujours la même réponse. J’avais juste envie de parler théorie des graphes

• Voilà un exemple qui brouille la frontière entre implémentation et spécification
  Nous pensons écrire une implémentation, mais en réalité nous écrivons une sorte de proxy de la spécification
  Autrement dit, le compilateur crée l’illusion d’une machine impérative

• Au début, j’étais surpris que Matt ne connaisse pas ce comportement
  Moi aussi, à l’université, en jouant avec LLVM IR, j’avais été choqué de voir une récursion se simplifier en multiplication
  Le fait que Matt ne le sache pas pourrait vouloir dire que cette optimisation ne s’applique qu’à des cas simples qu’il ne rencontre pas

  • En fait, il le savait déjà. Dans une présentation de 2017, il mentionnait lui-même exactement le même exemple
    Lien vers la vidéo YouTube