Wenn der Compiler Sie überrascht

• Ein Beispiel, das die Unterschiede bei der Optimierung zwischen GCC und Clang beim Kompilieren einer einfachen Funktion zur Summierung von Ganzzahlen zeigt
• GCC führt innerhalb der Schleife eine Schleifenoptimierung in der Form x*2 + 1 aus, bei der zwei Zahlen auf einmal addiert werden
• Clang entfernt die Schleife vollständig und ersetzt die Berechnung durch die geschlossene Formel v(v - 1)/2
• Dadurch wird der Code von O(n) zu O(1) verändert und eine mathematische Vereinfachung automatisch durchgeführt
• Ein Beispiel, das selbst den seit über 20 Jahren mit Compilern arbeitenden Autor durch das intelligente Optimierungsniveau moderner Compiler überrascht hat

---

Schleifenoptimierung in GCC

• Beim Schreiben einer einfachen Funktion zur Summierung von Ganzzahlen erzeugt GCC effizienten summierungsbasierten Code auf Schleifenbasis
  • Innerhalb der Schleife wird die Instruktion lea edx, [rdx+1+rax*2] verwendet, um zwei Zahlen gleichzeitig zu addieren
  • Das ist eine Transformation der Addition von x und x+1 in die Form x*2 + 1
• Wird das Optimierungsniveau auf -O3 erhöht, verarbeitet die Schleife die Werte durch parallele Addition (Vectorization) noch schneller
• Dieser Ansatz ist eine klassische Form der Optimierung, die die Schleife beibehält und zugleich die Recheneffizienz maximiert

Mathematische Optimierung in Clang

• Wird derselbe Code mit Clang kompiliert, verschwindet die Schleife vollständig
  • Clang prüft, ob der Eingabewert positiv ist, und führt die Berechnung dann mit einer Reihe von lea-, imul- und shr-Instruktionen aus
  • Im Ergebnis wird in (v² - v)/2, also in die geschlossene Formel der Ganzzahlsumme, umgewandelt
• Diese Transformation entfernt die Schleife und ersetzt sie durch eine Berechnung in konstanter Zeit (O(1))
• Der Autor beschreibt das Ergebnis so, als habe Clang „die mathematische Lösung der Ganzzahlsumme selbst gefunden“

Herleitung der Formel

• Verfolgt man den von Clang erzeugten Assemblercode mathematisch zurück, ergibt sich folgende Transformation
  • v + ((v - 1)(v - 2) / 2) - 1
  • Entwickelt und vereinfacht man dies, erhält man (v² - v)/2
• Am Ende ergibt sich die Form v(v - 1)/2, die mit der Summenformel von 1 bis v übereinstimmt
• Dies wird als Beispiel dafür präsentiert, dass der Compiler mathematische Muster erkennt und optimiert

Intelligentes Verhalten des Compilers

• Dass Clang genau diese Befehlssequenz verwendet, wird mit Vermeidung von Overflow und der Verfolgung induzierter Variablen erklärt
• Die genaue Ursache des internen Ablaufs ist zwar nicht eindeutig, wird aber als Ergebnis eines komplexen internen Optimierungsmechanismus von Clang beschrieben
• Der Autor bezeichnet dieses Ergebnis als „demütigende und inspirierende Erfahrung“

Abschluss und Kontext der Serie

• Dieser Beitrag ist der 24. Artikel der Reihe „Advent of Compiler Optimisations 2025“
• Er untersucht, wie Compiler durch Code-Transformationen mathematische Vereinfachung und Leistungssteigerung erreichen
• Der Autor betont: „Compiler überraschen mich immer noch“ – und damit das anhaltende technische Staunen trotz langjähriger Erfahrung

[GN⁺]

Hacker-News-Kommentare

• Der Code, der diese Funktion implementiert, befindet sich in ScalarEvolution.cpp und IndVarSimplify.cpp

  • Es ist erstaunlich und zugleich ein wenig beunruhigend, dass eine einzelne Datei fast 16.000 Zeilen Code enthält

• Diese Art von Optimierung ist wirklich interessant
  Compiler-Optimierungen lassen sich grob in zwei Kategorien einteilen — Datenflussanalyse sowie Mustererkennung und Ersetzung
  Ersteres ist für die meisten Programme wirksam, Letzteres ist eher das Ansammeln von Mustern mit zunehmend abnehmendem Ertrag
  Das verlinkte Beispiel ist klug und unterhaltsam, hat in der Praxis aber keinen großen Wert. In 45 Jahren habe ich nie eine solche Schleife geschrieben
  Natürlich bleiben solche Musterersetzungen wichtig, weil sie aus höherstufigem Code automatisch erzeugt werden
  Ehrlich gesagt könnte ich auch einfach ein wenig darüber meckern, dass mein Optimizer solche Optimierungen nicht beherrscht

  • Tatsächlich könnte das wertvoller sein, als man denkt. LLVMs SCEV (Scalar Evolution) wird hauptsächlich für Analysen verwendet und ermöglicht auch andere Optimierungen außerhalb mathematischer Schleifen
  • Es ist nicht ganz klar, welche Optimierung durchgeführt wurde. Als ich früher einmal einen Nischen-Compiler gebaut habe, war ich überrascht zu sehen, dass der Compiler Dinge intelligenter behandelte als die Optimierungen, die ich selbst geschrieben hatte

• Das ist eine Funktion namens Scalar Evolution (SCEV), und in LLVM ist sie ziemlich komplex implementiert

• Ein ähnlicher Optimierungsfall findet sich im Artikel „Do not optimize away“

  • Die Erklärung am Anfang dieses Artikels ist leicht falsch. Der Code addiert von 0 bis N, schließt N aber aus, also ist tatsächlich N(N-1)/2 korrekt. Mathematisch ist die Summe von 1 bis N gleich N(N+1)/2, daher muss man N durch (N-1) ersetzen, wenn die Obergrenze ausgeschlossen wird
  • Ich frage mich, ob der Compiler das nicht trotzdem optimieren könnte. Vermutlich, indem er eine Version mit Constant Folding und eine ohne erzeugt und zur Laufzeit verzweigt

• Das wirklich Coole an dieser Optimierung ist, dass sie generisch ist
  Beeindruckend ist, dass nicht einfach nur das Muster „Summe einer endlichen Integer-Folge“ erkannt wird, sondern dass es allgemein anwendbar ist

• Es sieht so aus, als könnte der Compiler noch mehr closed forms hinzufügen. Ich frage mich, ob sich das lohnen würde
  Ein verwandtes Konzept ist das Wilf–Zeilberger-Paar

• Wieder einmal war ich überrascht über ein Ergebnis, bei dem GCC langsamer als Clang war
  Obwohl GCC 20 Jahre Vorsprung hatte, gibt es immer noch Fälle, in denen Clang schnelleren Code erzeugt
  Früher, beim Extrahieren von Bits, kam Clang mit zwei Shifts aus, während GCC gleich drei machte

  • Zwischen GCC und LLVM/Clang gibt es einen großen Generationsunterschied in der Compiler-Technik. GCC ist nach wie vor ein großartiges Projekt, aber ich habe gehört, dass seine Struktur die Anwendung moderner Optimierungstechniken erschwert
  • Die tatsächliche Performance ist bei beiden Compilern ähnlich. Sie haben unterschiedliche Optimierungs-Passes, daher hängt das Ergebnis von der jeweiligen Situation ab
  • GCC war anfangs wegen eines lizenzzentrierten idealistischen Designs nur begrenzt erweiterbar. Das ist heute deutlich entschärft, aber der Codegenerator ist weiterhin komplex. Clang hat dagegen eine einfachere Struktur, wodurch sich Optimierungen leichter implementieren lassen. Persönlich finde ich auch die Ausgaben von MSVC und ICC ziemlich ordentlich
  • War das vielleicht Code im Zusammenhang mit Bitfeldern? Dort ist GCC bei Optimierungen besonders schwach

• Ich frage mich, ob schon einmal jemand eine Optimierung versucht hat, die das Graph-Coloring-Problem durch eine Konstante ersetzt

  • Graph Coloring ist ein NP-schweres Problem, daher lässt es sich nur schwer in O(1) verwandeln. Bei planaren Graphen gilt zwar der Vierfarbensatz, aber es kommt trotzdem nicht immer dieselbe Antwort heraus. Ich wollte einfach mal über Graphentheorie sprechen

• Das ist ein Beispiel dafür, wie die Grenze zwischen Implementierung und Spezifikation verschwimmt
  Wir glauben, eine Implementierung zu schreiben, tatsächlich schreiben wir aber gewissermaßen einen Proxy der Spezifikation
  Anders gesagt: Der Compiler erschafft die Illusion einer imperativen Maschine

• Anfangs war ich überrascht, dass Matt dieses Verhalten nicht kannte
  Ich war ebenfalls schockiert, als ich während meiner Studienzeit mit LLVM IR herumspielte und sah, wie Rekursion zu Multiplikation vereinfacht wurde
  Dass Matt es angeblich nicht wusste, könnte auch bedeuten, dass diese Optimierung nur auf einfache Fälle angewendet wird, mit denen er sich nicht beschäftigt

  • Tatsächlich wusste er es bereits. In einem Vortrag von 2017 erwähnte er genau dieses Beispiel selbst
    YouTube-Video-Link