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