Chris Lattner: Revolutioniert die C++-Welt

Fast alle C++-Entwickler kennen vermutlich die LLVM-Infrastruktur und den Clang-Compiler. Doch wie viele wissen, dass Chris Lattner ihr Schöpfer ist und damals erst 25 Jahre alt war? Wie ist das möglich? Ich erinnere mich, dass ich mit 25 noch damit beschäftigt war, die Grundlagen von C++ zu verstehen :)

Die Geschichte beginnt mit einer Abschlussarbeit

Ende 2000 kam Lattner als wissenschaftlicher Mitarbeiter und Masterstudent an die University of Illinois at Urbana-Champaign. Während seiner Arbeit mit Vikram Adve entwarf er LLVM und begann mit dessen Implementierung – eine innovative Infrastruktur für optimierende Compiler, die Gegenstand seiner Masterarbeit von 2002 war. 2005 schloss er seine Promotion ab; dabei erforschte er neue Techniken zur Optimierung pointer-intensiver Programme und integrierte sie in LLVM.

Aus dem Abstract seiner Arbeit geht die Motivation hinter dem LLVM-Design hervor:

Moderne Programmiersprachen und Software-Engineering-Prinzipien stellen Compilersysteme vor zunehmende Herausforderungen. Traditionelle Ansätze mit einem einfachen Compile-Link-Execute-Modell können unter den neuen Anforderungen keine ausreichende Anwendungsperformance liefern. Klassische Verfahren für interprozedurale und profilgesteuerte Kompilierung können zwar die nötige Performance erreichen, benötigen zum Erstellen der Anwendung jedoch unpraktikabel lange Kompilierungszeiten.Diese Dissertation stellt LLVM vor, den Entwurf und die Implementierung einer Compiler-Infrastruktur, die ein einzigartiges mehrstufiges Optimierungssystem unterstützt. Dieses System ist für umfassende interprozedurale und profilgesteuerte Optimierungen, und ist zugleich effizient genug für den Einsatz in kommerziellen Compilersystemen.Der virtuelle LLVM-Befehlssatz ist das Bindeglied, das das System zusammenhält. Er ist eine Low-Level-Repräsentation, enthält jedoch High-Level-Typinformationen. Dadurch bietet er die Vorteile einer Low-Level-Repräsentation (kompakte Darstellung, große Auswahl verfügbarer Transformationen usw.) mit High-Level-Informationen, die aggressive interprozedurale Optimierungen zur Link- und Post-Link-Zeit ermöglichen. Das System ist insbesondere für Optimierungen im produktiven Einsatz ausgelegt – sowohl zur Laufzeit als auch während ansonsten ungenutzter Leerlaufzeiten des Rechners.

Kurz gesagt besteht die Idee hinter LLVM darin, die LLVM Intermediate Representation (IR) zu verwenden, die Java-Bytecode oder .NET IL ähnelt.

LLVM IR ist für Analysen und Transformationen auf mittlerer Ebene konzipiert, wie sie im Optimierer eines Compilers vorkommen. Zu den Zielen gehören leichtgewichtige Laufzeitoptimierungen, funktionsübergreifende bzw. interprozedurale Optimierungen, Whole-Program-Analysen und aggressive Umstrukturierungstransformationen. Besonders wichtig ist jedoch, dass LLVM IR selbst als vollwertige Sprache mit klar definierter Semantik spezifiziert ist.

Betrachten wir eine relativ einfache Funktion, die drei Integer-Parameter entgegennimmt und eine arithmetische Kombination daraus zurückgibt.

int mul_add(int x, int y, int z) {
  return x * y + z;
}

Die LLVM IR für diese Funktion sieht so aus:

define i32 @mul_add(i32 %x, i32 %y, i32 %z) {
entry:
  %tmp = mul i32 %x, %y
  %tmp2 = add i32 %tmp, %z
  ret i32 %tmp2
}

Kehren wir zum Ziel der Arbeit zurück, das sich auf Optimierung konzentriert. Diese Compilerphase lässt sich kaum besser erklären als durch Chris Lattner, den Vater von LLVM, in diesem Beitrag:

„Um ein Gefühl dafür zu vermitteln, wie Optimierungen funktionieren, ist es hilfreich, einige Beispiele durchzugehen. Es gibt viele verschiedene Arten von Compileroptimierungen, daher lässt sich kein allgemeines Rezept für beliebige Probleme angeben. Die meisten Optimierungen folgen jedoch einer einfachen dreiteiligen Struktur:

Nach einem Muster suchen, das transformiert werden soll.
Prüfen, ob die Transformation für die gefundene Instanz sicher und korrekt ist.
Die Transformation durchführen und den Code aktualisieren.

Der Optimierer liest LLVM IR ein, verarbeitet sie und gibt anschließend wieder LLVM IR aus, die hoffentlich schneller ausgeführt wird. In LLVM – wie auch in vielen anderen Compilern – ist der Optimierer als Pipeline einzelner Optimierungspässe organisiert. Jeder Pass verarbeitet die Eingabe und kann Änderungen vornehmen. Typische Beispiele sind der Inliner, der den Funktionskörper an Aufrufstellen einsetzt, die Neuassoziation von Ausdrücken oder Loop-Invariant Code Motion. Je nach Optimierungsstufe werden unterschiedliche Pässe ausgeführt: Bei -O0 (keine Optimierung) führt Clang keine Pässe aus, bei -O3 dagegen eine Folge von 67 Optimierungspässen (Stand LLVM 2.8).

LLVM und Clang als Infrastruktur für die Entwicklung von Tools

Ein zentrales Designkonzept von Clang ist seine bibliotheksbasierte Architektur. Dabei lassen sich verschiedene Teile des Frontends sauber in separate Bibliotheken aufteilen, die je nach Bedarf unterschiedlich kombiniert werden können. Dieser Ansatz fördert außerdem gute Schnittstellen und erleichtert neuen Entwicklern den Einstieg, weil sie zunächst nur kleine Teile des Gesamtsystems verstehen müssen.

Das Design von LLVM/Clang macht die Plattform zu einer leistungsfähigen Infrastruktur für die Entwicklung von Tools. Dank der bibliotheksbasierten Architektur können Komponenten leicht wiederverwendet und neue Funktionen in andere Projekte integriert werden.

Viele Tools basieren auf LLVM und Clang, darunter clang-tidy, clang-query, CppDepend und weitere.

Clang bleibt bei neuen Standards stets auf dem neuesten Stand

Clang hält konsequent mit neuen Standards Schritt und bietet zudem stets experimentelle Unterstützung für kommende Features. Die damalige Version unterstützte experimentell einige vorgeschlagene Funktionen des auf C++17 folgenden Standards, der vorläufig C++2a genannt wurde. Da sich der Entwurf weiterentwickelte, konnte sich die Unterstützung jederzeit ändern oder ohne Vorankündigung entfallen.

Clang kann im C++2a-Modus mit der -std=c++2a Option verwendet werden.

Sprachfeature	C++2a-Vorschlag	In Clang verfügbar?
Standard-Memberinitialisierer für Bitfelder	P0683R1	Clang 6
`const&`-qualifizierte Zeiger auf Member	P0704R1	Clang 6
Erlaubt lambda-capture `[=, this]`	P0409R2	Clang 6
`__VA_OPT__` für das Entfernen von Kommas im Präprozessor	P0306R4	Clang 6
Designierte Initialisierer	P0329R4	Teilweise (Erweiterung)
Initializer-List-Konstruktoren bei der Argumentableitung von Klassentemplates	P0702R1	Clang 6
Zugriffsprüfung bei Spezialisierungen	P0692R1	Teilweise

Clang wird inzwischen von vielen großen Unternehmen eingesetzt, darunter Google, Microsoft und natürlich Apple, das Clang von Anfang an verwendet hat.

Die LLVM-Infrastruktur kann zur Implementierung von Compilern und Interpretern für viele Programmiersprachen genutzt werden. PostgreSQL verwendet beispielsweise LLVM JIT zur Optimierung der Abfrageausführung, wie hier:

Derzeit führt PostgreSQL SQL-Abfragen über den Interpreter aus, was relativ langsam ist. Eine deutliche Beschleunigung lässt sich jedoch erreichen, indem eine Abfrage mit LLVM JIT „on the fly“ kompiliert wird. So kann für eine bestimmte SQL-Abfrage effizienterer Code erzeugt werden, der anhand der zur Laufzeit und anschließend zusätzlich mit LLVM optimieren. Dieser Ansatz ist besonders bei komplexen Abfragen wichtig, deren Performance durch die CPU begrenzt wird.

Vielen Dank an alle LLVM/Clang-Entwickler und insbesondere an Chris Lattner, der diese Revolution angestoßen und uns eine leistungsfähige Infrastruktur zur Entwicklung nützlicher Tools gegeben hat.

Zum Schluss eine Botschaft an junge Entwickler: Werden Sie der nächste Chris Lattner und starten Sie eine Revolution in der Programmierwelt :)