Clang hat sich – ebenso wie GCC und die Compiler von Microsoft – als ausgereifter Compiler für C und C++ etabliert. Das Besondere an Clang ist jedoch, dass es weit mehr als nur ein Compiler ist. Dank seiner bibliotheksbasierten Architektur dient es zugleich als Infrastruktur für die Entwicklung von Werkzeugen und erleichtert die Wiederverwendung seiner Funktionen sowie deren Integration in andere Projekte.Das Design von Clang:
Wie viele andere Compiler ist auch Clang in drei Phasen gegliedert:
- Das Frontend analysiert den Quellcode, prüft ihn auf Fehler und erzeugt einen sprachspezifischen Abstract Syntax Tree (AST), der den Eingabecode repräsentiert.
- Der Optimierer führt Optimierungen auf dem vom Frontend erzeugten AST durch.
- Das Backend erzeugt den endgültigen Maschinencode; seine Ausgabe hängt von der Zielplattform ab.
Worin unterscheidet sich Clang von anderen Compilern?
Der wichtigste Unterschied im Design besteht darin, dass Clang auf LLVM basiert. LLVM verwendet eine Intermediate Representation (IR), die sich mit dem Bytecode von Java vergleichen lässt. Die LLVM IR ist für die Analysen und Transformationen der mittleren Compilerschicht ausgelegt, wie sie typischerweise im Optimierer stattfinden. Zu ihren Zielen gehören leichtgewichtige Laufzeitoptimierungen, funktionsübergreifende beziehungsweise interprozedurale Optimierungen, Whole-Program-Analysen und weitreichende Restrukturierungen. Besonders wichtig ist, dass die IR selbst als vollwertige Sprache mit klar definierter Semantik spezifiziert ist.
Durch dieses Design lässt sich ein großer Teil des Compilers für andere Compiler wiederverwenden. So kann beispielsweise lediglich das Frontend ausgetauscht werden, um eine andere Sprache zu unterstützen.
Es ist äußerst interessant, diese leistungsfähige Compiler-Infrastruktur zu untersuchen und zu verstehen, wie sie entworfen und implementiert wurde. C++-Entwickler können aus dieser Codebasis zahlreiche bewährte Praktiken ableiten.
Let's X-ray its source code using CppDepend and CQLinqund CQLinq, um einige Design- und Implementierungsentscheidungen des Entwicklungsteams zu untersuchen.
1 – Modularität:
1-1 Modularität durch Bibliotheken
Ein zentrales Designprinzip von Clang ist seine bibliotheksbasierte Architektur. Dabei werden die verschiedenen Teile des Frontends sauber in separate Bibliotheken aufgeteilt, die sich je nach Anwendungsfall unterschiedlich kombinieren lassen. Dieser Ansatz fördert außerdem klar definierte Schnittstellen und erleichtert neuen Entwicklern den Einstieg, da sie zunächst nur einen kleinen Teil des Gesamtsystems verstehen müssen.
Die DSM (Dependency Structure Matrix) ist eine kompakte Darstellung, mit der sich Abhängigkeiten zwischen Komponenten visualisieren und untersuchen lassen. Eine nicht leere Zelle enthält eine Zahl, die die Stärke der jeweiligen Kopplung angibt. Diese kann anhand der beteiligten Member, Methoden, Felder, Typen oder Namespaces ausgedrückt werden. Darüber hinaus macht die DSM Abhängigkeitszyklen zwischen Bibliotheken sichtbar.
Dieser Abhängigkeitsgraph zeigt die Bibliotheken, die Clang direkt verwendet.
Wie zu sehen ist, bestehen drei Abhängigkeitszyklen zwischen clangBasic/clangFrontend, clangBasic/clangDriver und clangBasic/clangLex. Solche Zyklen zwischen Bibliotheken sollten nach Möglichkeit beseitigt werden, um Lesbarkeit und Wartbarkeit des Codes zu verbessern.
Dass clangFrontend clangBasic verwendet, ist nachvollziehbar. Doch warum greift clangBasic auf die Bibliothek clangFrontend zu?
Lediglich ein einziges Enum-Feld verursacht diesen Abhängigkeitszyklus. Durch ein einfaches Refactoring ließe sich die Abhängigkeit beseitigen.
1-2 Modularität durch Namespaces
In C++ werden Namespaces ebenfalls zur Modularisierung der Codebasis eingesetzt. Bei LLVM/Clang erfüllen sie vor allem drei Aufgaben:
- Viele Namespaces enthalten ausschließlich Enums. Die folgende CQLinq-Abfrage zeigt die entsprechenden Namespaces:
In einem großen Projekt lässt sich nicht ausschließen, dass zwei unterschiedliche Enums denselben Namen verwenden. C++11 löst dieses Problem mitenum class, wodurch die Enum-Werte implizit innerhalb des Enum-Namens gekapselt werden. Der Code könnte in naher Zukunft auf Enum-Klassen aus C++11 umgestellt werden.
- Anonyme Namespaces: Ein Namespace ohne Namen vermeidet globale statische Variablen. Ein solcher anonymer Namespace ist nur innerhalb der Datei sichtbar, in der er definiert wurde. Hier ist die Liste aller verwendeten anonymen Namespaces:
- Modularisierung der Codebasis: Suchen wir nach allen nicht anonymen Namespaces:
Namespaces bieten eine gute Möglichkeit, eine Anwendung zu modularisieren. LLVM/Clang definiert mehr als 500 Namespaces und stärkt damit die Modularität sowie die Lesbarkeit und Wartbarkeit des Codes.
2 – Verwendete Programmierparadigmen:
C++ ist nicht nur eine objektorientierte Sprache. Wie Bjarne Stroustrup betont, ist C++ eine Multiparadigmensprache. Sie unterstützt verschiedene Programmierstile beziehungsweise Paradigmen; die objektorientierte Programmierung ist nur eines davon. Weitere sind die prozedurale und die generische Programmierung.
2-1 Prozedurales Paradigma
2-1-1 Globale Funktionen
Suchen wir nach allen globalen Funktionen, die im LLVM/Clang-Quellcode definiert sind:
Diese Funktionen lassen sich in drei Kategorien einteilen:
1 – Hilfsfunktionen: Viele Funktionen dienen beispielsweise der Konvertierung von einem Typ in einen anderen.
2 – Operatoren: Wie das Ergebnis der folgenden CQLinq-Abfrage zeigt, sind zahlreiche Operatoren definiert.
Im LLVM/Clang-Quellcode sind nahezu alle Arten von Operatoren implementiert.
3 – Funktionen der Compilerlogik: Zahlreiche globale Funktionen implementieren Teile der eigentlichen Compilerverarbeitung.
Möglicherweise könnten diese Funktionen nach Kategorien als statische Methoden in Klassen zusammengefasst oder in Namespaces organisiert werden.
2-1-2 Statische globale Funktionen
Es gilt als bewährte Praxis, eine globale Funktion als static zu deklarieren, sofern sie nicht ausdrücklich aus einer anderen Quelldatei aufgerufen werden muss.
Nahezu alle globalen Funktionen sind als static deklariert.
2-1-3 Globale Funktionen, die als static deklariert werden könnten
Nicht exportierte globale Funktionen, die weder in einem anonymen Namespace definiert noch außerhalb ihrer Quelldatei verwendet werden, sind gute Kandidaten für eine Umstellung auf static.
Wie zu sehen ist, kommen nur sehr wenige Funktionen für ein solches Refactoring infrage.
2-2 Objektorientiertes Paradigma
2-2-1 Vererbung
In der objektorientierten Programmierung (OOP) dient Vererbung dazu, eine „ist-ein“-Beziehung zwischen Objekten auszudrücken. Sie wird häufig fälschlicherweise als Mittel zur Wiederverwendung vorhandenen Codes betrachtet. Vererbung allein zur Wiederverwendung von Implementierungen führt jedoch zu enger Kopplung. Für die Wiederverwendung von Code ist Komposition meist die bessere Wahl („Composition over Inheritance“). Suchen wir nach allen Klassen mit mindestens einer Basisklasse:
Um einen besseren Überblick über die von dieser Abfrage betroffenen Klassen zu erhalten, können wir die Metric View verwenden.
In der Metric View wird die Codebasis als Treemap dargestellt. Treemapping visualisiert hierarchische Daten mithilfe ineinander verschachtelter Rechtecke. Die CppDepend-Treemap verwendet dabei die übliche Codehierarchie:
- Projekte enthalten Namespaces.
- Namespaces enthalten Typen.
- Typen enthalten Methoden und Felder.
Die Treemap eignet sich hervorragend zur Darstellung des Ergebnisses einer CQLinq-Abfrage. Die blauen Rechtecke markieren die Treffer, sodass die betroffenen Typen unmittelbar erkennbar sind.
Wie zu erkennen ist, wird Vererbung im LLVM/Clang-Quellcode intensiv eingesetzt.
Mehrfachvererbung: Suchen wir nach Klassen, die von mehr als einer konkreten Klasse erben.
Mehrfachvererbung wird nur selten eingesetzt; weniger als 1 % der Klassen erben von mehr als einer Klasse.
2-2-2 Virtuelle Methoden
Suchen wir nach allen virtuellen Methoden im Quellcode:
Viele Methoden sind virtuell, einige davon rein virtuell:
Das OOP-Paradigma wird im LLVM/Clang-Quellcode umfassend genutzt. Wie sieht es mit generischer Programmierung aus?
2-3 Generische Programmierung
C++ bietet mit Templates besonders leistungsfähige Möglichkeiten für generische Programmierung. Templates stellen eine Form des parametrischen Polymorphismus dar und ermöglichen generische Algorithmen und Datenstrukturen. Der Instanziierungsmechanismus sorgt dafür, dass bei der Verwendung eines generischen Algorithmus oder einer generischen Datenstruktur eine vollständig optimierte, auf den konkreten Einsatz zugeschnittene Variante erzeugt wird. Dadurch können generische Algorithmen ebenso effizient sein wie nicht generische Varianten.
2-3-1 Generische Typen
Suchen wir nach allen generischen Typen, die im Quellcode definiert sind:
Viele Typen sind generisch definiert. Suchen wir nun nach generischen Methoden:
Weniger als 1 % der Methoden sind generisch.
Zusammenfassend kombiniert der LLVM/Clang-Quellcode alle drei Paradigmen.
3 – PODs zur Definition des Datenmodells
In der objektorientierten Programmierung bezeichnet Plain Old Data (POD) eine Datenstruktur, die lediglich als passive Sammlung von Feldwerten beziehungsweise Instanzvariablen dargestellt wird und keine objektorientierten Mechanismen nutzt. In der Informatik spricht man dabei von einer passiven Datenstruktur.
Suchen wir nach POD-Typen im Quellcode.
Mehr als 1.500 Typen sind als POD-Typen definiert; viele davon dienen zur Beschreibung des Datenmodells des Compilers.
4 – Design Patterns der Gang of Four
Design Patterns beschreiben wiederkehrende Lösungen für typische Probleme im Softwaredesign. Die Muster der Gang of Four gehören zu den bekanntesten. Sehen wir uns einige davon im LLVM/Clang-Quellcode an.
4-1 Factory
Eine Factory kapselt die Instanziierungslogik und kann die Kohäsion verbessern. Hier ist die Liste der im Quellcode definierten Factories:
Und hier die Liste der abstrakten Factories:
4-3 Observer
Beim Observer Pattern verwaltet ein Objekt eine Liste abhängiger Objekte, der sogenannten Observer, und informiert diese automatisch über Zustandsänderungen – üblicherweise durch den Aufruf einer ihrer Methoden.
Im Quellcode ist nur ein Observer definiert:
4-4 Visitor
Das Visitor Pattern eignet sich, wenn eine Struktur durchlaufen und auf jedem ihrer Knoten eine bestimmte Operation ausgeführt werden soll.
Im LLVM/Clang-Quellcode wird das Visitor Pattern häufig eingesetzt:
5 – Kopplung und Kohäsion
5-1 Kopplung
Eine geringe Kopplung ist wünschenswert, weil Änderungen in einem Bereich der Anwendung dadurch weniger Folgeänderungen im restlichen System erfordern. Langfristig lassen sich so Zeit, Aufwand und Kosten für Änderungen und neue Funktionen deutlich reduzieren.
Eine geringe Kopplung lässt sich unter anderem durch abstrakte Klassen sowie generische Typen und Methoden erreichen.
Suchen wir nach allen abstrakten Klassen im Quellcode:
Mehr als 280 Typen sind als abstrakt deklariert. Zusätzlich tragen generische Typen und Methoden zu einer geringen Kopplung bei.
Kohäsion
Das Single-Responsibility-Prinzip besagt, dass eine Klasse nicht mehr als einen Grund für Änderungen haben sollte. Eine solche Klasse gilt als kohäsiv. Ein hoher LCOM-Wert weist in der Regel auf eine geringe Kohäsion hin. Es existieren mehrere LCOM-Metriken. LCOM liegt im Bereich [0–1], LCOM HS (Henderson-Sellers) im Bereich [0–2]. Ein LCOM-HS-Wert über 1 sollte als Warnsignal betrachtet werden. Die Metriken werden wie folgt berechnet:
LCOM = 1 – (sum(MF)/M*F) LCOM HS = (M – sum(MF)/F)(M-1)
Dabei gilt:
- M ist die Anzahl der Methoden einer Klasse; gezählt werden statische und Instanzmethoden sowie Konstruktoren, Property-Getter/-Setter und Methoden zum Hinzufügen beziehungsweise Entfernen von Events.
- F ist die Anzahl der Instanzfelder der Klasse.
- MF ist die Anzahl der Methoden der Klasse, die auf ein bestimmtes Instanzfeld zugreifen.
- Sum(MF) ist die Summe von MF über alle Instanzfelder der Klasse.
Die Grundidee dieser Formeln lautet: Eine Klasse ist vollständig kohäsiv, wenn alle ihre Methoden sämtliche Instanzfelder verwenden. Dann gilt sum(MF)=M*F und folglich LCOM = 0 sowie LCOMHS = 0.
Ein LCOMHS-Wert über 1 sollte als Warnsignal betrachtet werden.
235 Klassen sind davon betroffen. Bei einigen könnte ein Refactoring die Kohäsion verbessern.
6 – Unveränderlichkeit, Reinheit und Seiteneffekte
6-1 Unveränderliche Typen
Ein Objekt ist grundsätzlich unveränderlich, wenn sich sein Zustand nach der Erzeugung nicht mehr ändert. Entsprechend gilt eine Klasse als unveränderlich, wenn ihre Instanzen unveränderlich sind.
Ein wichtiges Argument für unveränderliche Objekte ist, dass sie nebenläufige Programmierung erheblich vereinfachen. Warum ist korrekter Multithread-Code so schwierig? Weil die Zugriffe mehrerer Threads auf Objekte und andere Ressourcen synchronisiert werden müssen und Race Conditions zwischen Lese- und Schreibzugriffen schwer auszuschließen sind. Entfallen die Schreibzugriffe, weil sich der Zustand der von den Threads verwendeten Objekte nicht ändert, entfällt auch ein großer Teil dieses Synchronisationsbedarfs.
Ein weiterer Vorteil unveränderlicher Klassen besteht darin, dass sie das Liskovsche Substitutionsprinzip (LSP) nicht verletzen können. Hier eine Definition des LSP:
Liskovs Konzept eines verhaltensbezogenen Subtyps beschreibt die Ersetzbarkeit veränderlicher Objekte: Ist S ein Subtyp von T, können Objekte des Typs T in einem Programm durch Objekte des Typs S ersetzt werden, ohne erwünschte Eigenschaften des Programms – etwa seine Korrektheit – zu verändern.
Hier ist die Liste der im Quellcode definierten unveränderlichen Typen:
6-2 Reinheit und Seiteneffekte
Der wichtigste Vorteil unveränderlicher Typen besteht darin, dass sie Seiteneffekte vermeiden. Treffender alsWes Dyer, so I quote him:
Wir alle wissen, dass globale Variablen im Allgemeinen keine gute Idee sind. Sie sind gewissermaßen die extremste Form offengelegter Seiteneffekte – im globalen Gültigkeitsbereich. Viele Programmierer, die keine globalen Variablen verwenden, übersehen jedoch, dass dieselben Prinzipien in kleinerem Maßstab auch für Felder, Properties, Parameter und Variablen gelten: Verändern Sie sie nur, wenn es dafür einen guten Grund gibt. (…)Eine Möglichkeit, die Zuverlässigkeit einer Einheit zu erhöhen, besteht darin, Seiteneffekte zu eliminieren. Dadurch lassen sich Einheiten wesentlich einfacher und robuster kombinieren und integrieren. Da sie frei von Seiteneffekten sind, verhalten sie sich unabhängig von ihrer Umgebung immer gleich. Dies bezeichnet man als referenzielle Transparenz.
Wenn Funktionen beziehungsweise Methoden ohne Seiteneffekte geschrieben werden – also alsreine Funktionen, die das Objekt nicht verändern– lässt sich die Korrektheit eines Programms wesentlich leichter nachvollziehen.
Hier ist die Liste aller Methoden ohne Seiteneffekte.
Mehr als 100.000 Methoden sind rein.
7 – Implementierungsqualität
7-1 Zu große Methoden
Methoden mit sehr vielen Codezeilen sind schwerer zu verstehen und zu warten. Suchen wir nach Methoden mit mehr als 60 Zeilen.
Der LLVM/Clang-Quellcode enthält mehr als 100.000 Methoden; weniger als 2 % davon können daher als zu groß betrachtet werden.
7-2 Methoden mit vielen Parametern
Nur wenige Methoden haben mehr als acht Parameter.
7-3 Methoden mit vielen lokalen Variablen
Weniger als 1 % verfügen über sehr viele lokale Variablen.
7-4 Zu komplexe Methoden
Zur Erkennung komplexer Funktionen gibt es zahlreiche Metriken. NBLinesOfCode, die Anzahl der Parameter und die Anzahl lokaler Variablen gehören zu den grundlegenden Kennzahlen.
Darüber hinaus gibt es weitere interessante Metriken zur Erkennung komplexer Funktionen:
- Die zyklomatische Komplexität ist eine verbreitete prozedurale Softwaremetrik und entspricht der Anzahl möglicher Entscheidungen innerhalb einer Prozedur.
- Nesting Depth beschreibt die maximale Verschachtelungstiefe eines Gültigkeitsbereichs innerhalb eines Methodenkörpers.
- Max Nested Loops entspricht der maximalen Verschachtelungstiefe von Schleifen innerhalb einer Funktion.
Welche Höchstwerte für diese Metriken akzeptabel sind, hängt von den Vorgaben des jeweiligen Teams ab; allgemeingültige Standardwerte gibt es nicht.
Suchen wir nach Methoden, die in der Codebasis als komplex gelten könnten.
Nur 1,5 % kommen für ein Refactoring zur Verringerung ihrer Komplexität infrage.
7-5 Halstead-Komplexität
Halstead-Komplexitätbezeichnet Softwaremetriken, die Maurice Howard Halstead 1977 einführte. Halstead ging davon aus, dass Softwaremetriken die Implementierung beziehungsweise Ausdrucksform von Algorithmen in unterschiedlichen Sprachen widerspiegeln sollten, dabei jedoch unabhängig von der Ausführung auf einer bestimmten Plattform sein müssen. Daher werden diese Metriken statisch aus dem Code berechnet.
Halstead führte mehrere Metriken ein. Als Beispiel betrachten wir TimeToImplement, das die geschätzte Zeit zur Implementierung einer Methode in Sekunden angibt.
Für 2.690 Methoden wird eine Implementierungszeit von mehr als einer Stunde veranschlagt.
8 – RTTI
RTTI bezeichnet die Fähigkeit eines Systems, den dynamischen Typ eines Objekts zu ermitteln und zur Laufzeit Informationen über diesen Typ bereitzustellen – im Gegensatz zur Ermittlung zur Compile-Zeit. RTTI ist in der C++-Community allerdings umstritten, und viele Entwickler verzichten bewusst darauf.
Wie handhabt es das LLVM/Clang-Entwicklungsteam?
Keine Methode verwendet das Schlüsselwort dynamic_cast. Das LLVM/Clang-Team hat sich somit gegen den Einsatz von RTTI entschieden.
9 – Exceptions
Auch Exception Handling ist ein umstrittenes C++-Feature. Viele bekannte Open-Source-Projekte in C++ verzichten darauf.
Prüfen wir, ob im Quellcode Exceptions ausgelöst werden.
Wie bei RTTI wird auch der Exception-Mechanismus nicht verwendet.
10 – Einige Statistiken
10-1 Am häufigsten verwendete Typen
Es ist hilfreich zu wissen, welche Typen in einem Projekt am häufigsten verwendet werden. Gerade diese Typen müssen sorgfältig entworfen, implementiert und getestet werden, denn Änderungen an ihnen können sich auf das gesamte Projekt auswirken.
Wir können sie mithilfe derTypesUsingMeMetrik ermitteln:
Eine weitere interessante Metrik zur Ermittlung wichtiger Typen ist TypeRank.
TypeRank-Werte werden berechnet, indem der Google-PageRank-Algorithmus auf den Abhängigkeitsgraphen der Typen angewendet wird. Anschließend erfolgt eine Skalierung mit dem Faktor 0,15, sodass der durchschnittliche TypeRank bei 1 liegt.
Typen mit hohem TypeRank sollten besonders sorgfältig getestet werden, da Fehler in diesen Typen voraussichtlich gravierendere Auswirkungen haben.
Hier ist das Ergebnis für die wichtigsten Typen gemäß der TypeRank-Metrik:
10-2 Am häufigsten verwendete Methoden
10-3 Methoden, die viele andere Methoden aufrufen
Es ist interessant zu ermitteln, welche Methoden besonders viele andere Methoden aufrufen. Dies kann auf Designprobleme hinweisen; in manchen Fällen ist ein Refactoring sinnvoll, um Lesbarkeit und Wartbarkeit zu verbessern.
Zusammenfassung
LLVM/Clang ist sehr gut entworfen und implementiert. Wie bei jedem großen Projekt gibt es dennoch Stellen, die durch Refactoring weiter verbessert werden könnten. In diesem Beitrag haben wir einige kleinere Optimierungsmöglichkeiten im Quellcode aufgezeigt. Es lohnt sich, die Codebasis selbst zu erkunden und daraus für die eigenen C++-Kenntnisse zu lernen.