Ich wollte einen Artikel darüber schreiben, wie LLVM eine Funktion optimiert, aber zuerst müssen Sie schreiben, wie Clang C oder C ++ in LLVM übersetzt.
Betrachten Sie die Aspekte auf hoher Ebene, ohne in die Tiefen von Clang einzutauchen. Ich möchte darauf achten, wie die Clang-Ausgabe mit der Eingabe zusammenhängt, während wir die nicht trivialen Funktionen von C ++ nicht berücksichtigen. Wir verwenden diese kleine Funktion, die ich aus hervorragenden
Vorlesungen über zyklische Optimierungen entlehnt habe:
bool is_sorted(int *a, int n) { for (int i = 0; i < n - 1; i++) if (a[i] > a[i + 1]) return false; return true; }
Da Clang keine Optimierungen vornimmt und LLVM IR ursprünglich für C und C ++ entwickelt wurde, ist die Konvertierung relativ einfach. Ich werde Clang 6.0.1 (oder eine nahe Version, da diese noch nicht veröffentlicht wurde) auf x86-64 verwenden.
Die Befehlszeile lautet wie folgt:
clang++ is_sorted.cpp -O0 -S -emit-llvm
Mit anderen Worten: Wir kompilieren die Datei is_sorted.cpp als C ++ und teilen der LLVM-Toolchain Folgendes mit: Nicht optimieren, den Assembler als Textdarstellung von LLVM-IR ausgeben. LLVM IR ist umfangreich und kann nicht schnell angezeigt oder analysiert werden. Ein binäres Bitcode-Format ist immer vorzuziehen, wenn eine Person diesen Code nicht betrachten muss.
Hier ist die vollständige LLVM-IR, wir werden sie in Teilen überprüfen.
Beginnen wir oben in der Datei:
; ModuleID = 'is_sorted.cpp' source_filename = "is_sorted.cpp" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu"
Der gesamte Text zwischen dem Semikolon und dem Ende der Zeile ist ein Kommentar, was bedeutet, dass die erste Zeile nichts bewirkt. Wenn Sie jedoch an LLVM interessiert sind, ist ein „Modul“ eine Kompilierungseinheit, ein Container für Code und Daten. Die zweite Zeile sollte uns auch nicht stören. In der dritten Zeile werden einige vom Compiler getroffene Annahmen beschrieben. Sie spielen in diesem Artikel keine Rolle. Weitere Informationen finden Sie
hier .
Das Ziel drei ist das Erbe von gcc und braucht uns nicht mehr.
Die LLVM-Funktion verfügt über optionale Attribute:
; Function Attrs: noinline nounwind optnone uwtable
Einige von ihnen (wie diese) werden vom Front-End unterstützt, andere werden später durch Optimierungsdurchläufe hinzugefügt. Diese Attribute haben nichts mit der Bedeutung des Codes zu tun. Ich werde sie hier nicht diskutieren, aber Sie können sie
hier lesen
, wenn Sie interessiert sind.
Und schließlich unsere Funktion:
define zeroext i1 @_Z9is_sortedPii(i32* %a, i32 %n)
"Zeroext" bedeutet, dass der Rückgabewert der Funktion (i1, eine Einzelbit-Ganzzahl) im Backend mit Nullen auf die vom ABI benötigte Breite erweitert werden muss. Dann kommt der "verstümmelte" Funktionsname, dann ist die Liste der Parameter im Grunde die gleiche wie im C ++ - Code, außer dass i32 eine 32-Bit-Variable definiert. # 0 verbindet die Funktion mit
der Attributgruppe am Ende der Datei.
Hier ist die erste Basiseinheit:
entry: %retval = alloca i1, align 1 %a.addr = alloca i32*, align 8 %n.addr = alloca i32, align 4 %i = alloca i32, align 4 store i32* %a, i32** %a.addr, align 8 store i32 %n, i32* %n.addr, align 4 store i32 0, i32* %i, align 4 br label %for.cond
Jeder LLVM-Befehl muss sich innerhalb der Basiseinheit befinden: ein Befehlssatz mit einem Eingang am Anfang und einem Ausgang am Ende. Die letzte Anweisung der Basiseinheit muss eine
Beendigungsanweisung sein : "Fehler" in der nächsten Basiseinheit ist nicht zulässig. Jede Funktion muss einen Eingabeblock haben, der keine Vorgänger hat, die den Übergang zu diesem Block ausführen. Diese und
andere Eigenschaften werden beim Parsen von IR überprüft. Diese Überprüfungen können auch während des Kompilierungsprozesses vom „Modulprüfer“ mehrmals aufgerufen werden. Der Verifizierer ist nützlich zum Debuggen, wenn ein Durchlauf eine ungültige IR generiert.
Die ersten vier Anweisungen in diesem Basisblock lauten "alloca": Zuweisen des Stapelspeichers. Die ersten drei erstellen Variablen, die implizit während der Kompilierung erstellt werden, die vierte - eine Schleifenvariable. Auf diese Weise zugewiesene Variablen können nur über Lade- und Speicheranweisungen aufgerufen werden. Die folgenden drei Anweisungen initialisieren die drei Stapelschlitze a.addr und n.addr werden unter Verwendung der an die Funktion als Parameter übergebenen Werte initialisiert, und i wird auf Null initialisiert. Der Rückgabewert muss nicht initialisiert werden, jeder Code, der in C und C ++ nicht undefiniert ist, muss sich darum kümmern. Die letzte Anweisung ist ein bedingungsloser Übergang zur nächsten Basiseinheit (darüber sind wir noch nicht besorgt, die meisten unnötigen Übergänge werden vom LLVM-Backend gelöscht).
Sie fragen sich vielleicht: Warum weist Clang Stapelschlitze für a und n zu? Warum verwendet er diese Werte nicht direkt? Da sich a und n in dieser Funktion nicht ändern, funktioniert eine solche Strategie. Dieser Fall wird jedoch vom Optimierer berücksichtigt und liegt außerhalb der Zuständigkeit von Calng. Wenn a und n geändert werden können, sollten sie sich im Speicher befinden und keine SSA-Werte sein, die per Definition nur an einer Stelle im Programm einen Wert annehmen können. Speicherzellen befinden sich außerhalb der SSA-Welt und können jederzeit geändert werden. Dies mag seltsam erscheinen, aber mit einer solchen Lösung können Sie die Arbeit aller Teile des Compilers auf natürliche und effiziente Weise organisieren.
Ich stelle mir Clang als einen Generator für entarteten SSA-Code vor, der alle Anforderungen von SSA erfüllt, aber nur, weil der Informationsaustausch zwischen den Basiseinheiten über den Speicher erfolgt. Das Generieren von nicht entartetem Code erfordert einige Aufmerksamkeit und einige Analysen, und Clang-Entwickler lehnten dies ab, um die Verantwortlichkeiten für das Generieren und Optimieren des Codes zu trennen. Ich habe die Messergebnisse nicht gesehen, aber nach meinem Verständnis werden viele Speicheroperationen generiert, und dann werden die meisten fast sofort vom Optimierer gelöscht, ohne dass dies zu einem hohen Aufwand an Kompilierungszeit führt.
Überlegen Sie, wie die for-Schleife übersetzt wird. Im Allgemeinen sieht es so aus:
for (initializer; condition; modifier) { body }
Dies bedeutet ungefähr so:
initializer goto COND COND: if (condition) goto BODY else goto EXIT BODY: body modifier goto COND EXIT:
Natürlich ist eine solche Übersetzung nicht spezifisch für Clang, jeder C- und C ++ - Compiler macht dasselbe.
In unserem Beispiel wird der Schleifeninitialisierer in den Eingabebasisblock eingeblendet. Die folgende Basiseinheit ist eine Schleifenzustandsprüfung:
for.cond: ; preds = %for.inc, %entry %0 = load i32, i32* %i, align 4 %1 = load i32, i32* %n.addr, align 4 %sub = sub nsw i32 %1, 1 %cmp = icmp slt i32 %0, %sub br i1 %cmp, label %for.body, label %for.end
Clang macht auch einen nützlichen Kommentar, dass dieser Basisblock entweder von for.inc oder vom Eingabebasisblock aus erreichbar ist. Dieser Block lädt i und n aus dem Speicher, reduziert n (das nsw-Flag spiegelt die C-Spracheigenschaft wider, dass der Vorzeichenüberlauf nicht definiert ist; ohne dieses Flag verwendet LLVM die Semantik des zusätzlichen Codes) und vergleicht den reduzierten Wert mit i unter Verwendung des slt (signiert kleiner als, signiere weniger als) und verzweige dann schließlich in die Basis für.body oder for.end Block.
Der Zugang zum Schleifenkörper ist nur über den for.cond-Block möglich:
for.body: %2 = load i32*, i32** %a.addr, align 8 %3 = load i32, i32* %i, align 4 %idxprom = sext i32 %3 to i64 %arrayidx = getelementptr inbounds i32, i32* %2, i64 %idxprom %4 = load i32, i32* %arrayidx, align 4 %5 = load i32*, i32** %a.addr, align 8 %6 = load i32, i32* %i, align 4 %add = add nsw i32 %6, 1 %idxprom1 = sext i32 %add to i64 %arrayidx2 = getelementptr inbounds i32, i32* %5, i64 %idxprom1 %7 = load i32, i32* %arrayidx2, align 4 %cmp3 = icmp sgt i32 %4, %7 br i1 %cmp3, label %if.then, label %if.end
Die ersten beiden Zeilen laden a und i in die SSA-Register; Ich expandiere dann auf 64 Bit und kann an der Berechnung der Adresse teilnehmen. Der Befehl
getelementptr (oder kurz gep) ist der LLVM-Befehl, der für seine Anmaßung bekannt ist, und verfügt sogar über einen eigenen
Hilfeabschnitt . Im Gegensatz zur Maschinensprache behandelt LLVM Zeiger nicht als Ganzzahlen. Dies erleichtert die Alias-Analyse und andere Speicheroptimierungen. Dieser Code lädt ein [i] und ein [i + 1], vergleicht sie und führt je nach Ergebnis eine Verzweigung durch.
Der if.then-Block speichert 0 für den Rückgabewert der Funktion im Stapelsteckplatz und springt bedingungslos zum Ausgabeblock der Funktion:
if.then: store i1 false, i1* %retval, align 1 br label %return
Der else-Block ist trivial:
if.end: br label %for.inc
Und der Block zum Hinzufügen einer zur Schleifenvariablen ist ebenfalls sehr einfach:
for.inc: %8 = load i32, i32* %i, align 4 %inc = add nsw i32 %8, 1 store i32 %inc, i32* %i, align 4 br label %for.cond
Dieser Code springt zurück, um nach Schleifenbedingungen zu suchen.
Wenn die Schleife normal abgeschlossen ist, geben wir true zurück:
for.end: store i1 true, i1* %retval, align 1 br label %return
Und schließlich wird das, was wir in den Stapelschlitz des Rückgabewerts geladen haben, geladen und zurückgegeben:
return: %9 = load i1, i1* %retval, align 1 ret i1 %9
Am Ende der Funktion gibt es nichts Besonderes. Der Beitrag war länger als ich dachte. Im nächsten Beitrag werden wir überlegen, den IR-Pegel für diese Funktion zu optimieren.
(Danke an Xi Wang und Alex Rosenberg für die Korrekturen)