Die Compiler-Entwicklung ist eine äußerst komplexe Aufgabe. Glücklicherweise wird durch die Fortschritte in Projekten wie LLVM diese Herausforderung erheblich vereinfacht, sodass selbst ein Einzelprogrammierer in der Lage ist, eine neue Sprache zu entwickeln, die in Bezug auf die Leistung vergleichbar mit C ist. Die Arbeit mit LLVM wird dadurch erschwert, dass dieses System aus einem riesigen Codeumfang besteht, der jedoch nur spärlich dokumentiert ist. Um dieses Problem anzugehen, plant der Autor des Materials, dessen Übersetzung wir heute veröffentlichen, Beispiele für mit Go geschriebenen Code zu demonstrieren und zu zeigen, wie sie zunächst in , und danach in LLVM IR unter Verwendung des Compilers . Der Go SSA und der LLVM IR Code wurden leicht bearbeitet, um alle nicht relevanten Teile zu entfernen und die Erklärungen verständlicher zu machen.
Das erste Beispiel
Die erste Funktion, die ich hier analysieren möchte, ist ein einfacher Mechanismus zum Addieren von Zahlen:
func myAdd(a, b int) int{
return a + b
}Diese Funktion ist sehr einfach und könnte nicht grundlegender sein. Sie wird in den folgenden Go SSA-Code übersetzt:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Bei dieser Darstellung der Funktion sind die Datentyp-Hinweise rechts angeordnet, die in den meisten Fällen ignoriert werden können.
Dieses kleine Beispiel zeigt bereits einen der Aspekte der SSA. Genauer gesagt, bei der Umwandlung von Code in die SSA-Form wird jeder Ausdruck in seine grundlegendsten Teile zerlegt. return a + b, stellt tatsächlich zwei Operationen dar: die Addition zweier Zahlen und die Rückgabe des Ergebnisses.
Außerdem lässt sich hier der grundlegende Programmblock erkennen. In diesem Code gibt es nur einen Block – den Eingangsblock (entry block). Mehr dazu werden wir später besprechen.
Go SSA-Code lässt sich leicht in LLVM IR umwandeln:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
} Es ist bemerkenswert, dass obwohl hier andere syntaktische Konstruktionen verwendet werden, die Struktur der Funktion im Wesentlichen unverändert bleibt. Der LLVM IR-Code ist etwas komplexer als der Go SSA-Code und ähnelt C. Hier in der Funktionsdeklaration steht zuerst die Beschreibung des Rückgabetyps, der Typ des Arguments wird vor dem Namen des Arguments angegeben. Darüber hinaus steht zur Vereinfachung des IR-Parsings ein Symbol vor den Namen globaler Entitäten, @, während ein Symbol vor den Namen lokaler Entitäten steht, % (eine Funktion wird ebenfalls als globale Entität betrachtet).
Eine Besonderheit dieses Codes, auf die man achten sollte, ist, dass die Entscheidung über die Darstellung des Go-Typs int, der je nach Compiler und Ziel der Kompilierung als 32-Bit- oder 64-Bit-Wert dargestellt werden kann, bei der Erstellung des LLVM IR-Codes getroffen wird. Dies ist einer der vielen Gründe, warum LLVM IR-Code, wie viele fälschlicherweise denken, nicht plattformunabhängig ist. Ein solcher Code, der für eine Plattform erstellt wurde, kann nicht einfach auf eine andere Plattform kompiliert werden (es sei denn, man geht diese Aufgabe ).
Ein weiterer interessanter Punkt, den es zu beachten gilt, ist, dass der Typ i64 — keine vorzeichenbehaftete Ganzzahl ist: Er ist neutral, was die Darstellung des Vorzeichens betrifft. Abhängig von der Anweisung kann er sowohl vorzeichenbehaftete als auch vorzeichenlose Zahlen repräsentieren. Bei der Darstellung der Addition spielt dies keine Rolle, sodass es keinen Unterschied beim Umgang mit vorzeichenbehafteten oder vorzeichenlosen Zahlen gibt. Es sollte erwähnt werden, dass in C ein Überlauf einer vorzeichenbehafteten Ganzzahl zu einem undefinierten Verhalten führt. Daher fügt der Clang-Frontend der Operation das Flag hinzu nsw (no signed wrap), was LLVM signalisiert, dass es annehmen kann, dass bei der Addition niemals ein Überlauf auftritt.
Dies kann für einige Optimierungen wichtig sein. Zum Beispiel erfordert die Addition zweier Werte i16 auf einer 32-Bit-Plattform (mit 32-Bit-Registern) nach der Ausführung der Addition eine Vorzeichenverlängerung, um im Bereich zu bleiben i16. Deshalb erweist sich häufig die Ausführung von Ganzzahloperationen unter Berücksichtigung der Maschinenregistergröße als effizienter.
Was mit diesem IR-Code im Folgenden geschieht, interessiert uns momentan nicht besonders. Der Code wird optimiert (aber bei so einem einfachen Beispiel wie unserem passiert bereits keine Optimierung mehr) und anschließend in Maschinencode umgewandelt.
Zweites Beispiel
Das nächste Beispiel, das wir betrachten werden, wird etwas komplizierter. Es handelt sich um eine Funktion, die einen Slice von Ganzzahlen summiert:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Dieser Code wird in den folgenden Go SSA-Code umgewandelt:
func sum(numbers []int) int:
entry:
jump for.loop
for.loop:
t0 = phi [entry: 0:int, for.body: t6] #n int
t1 = phi [entry: 0:int, for.body: t7] #i int
t2 = len(numbers) int
t3 = t1 < t2 bool
if t3 goto for.body else for.done
for.body:
t4 = &numbers[t1] *int
t5 = *t4 int
t6 = t0 + t5 int
t7 = t1 + 1:int int
jump for.loop
for.done:
return t0Hier sind bereits mehr Konstruktionen zu sehen, die für die Darstellung von Code in SSA-Form charakteristisch sind. Wahrscheinlich ist das offensichtlichste Merkmal dieses Codes, dass es hier keine strukturierten Steuerbefehle für den Fluss der Berechnungen gibt. Für die Steuerung des Flusses stehen lediglich bedingte und unbedingte Sprünge zur Verfügung, und wenn man diesen Befehl als Steuerung des Flusses betrachtet, ist der Rückgabebefehl ein solcher.
Tatsächlich fällt auf, dass das Programm nicht in Blöcke unter Verwendung von geschweiften Klammern (wie in C-ähnlichen Sprachen) unterteilt ist. Es ist durch Labels getrennt, was an Assemblersprachen erinnert, und es wird in Form von Basisblöcken dargestellt. In SSA werden Basisblöcke als zusammenhängende Codefolgen bezeichnet, die mit einem Label beginnen und mit Abschlussanweisungen für den Basisblock enden, wie zum Beispiel — return und jump.
Ein weiteres interessantes Detail dieses Codes wird durch den Befehl phipräsentiert. Diese Anweisung ist ziemlich ungewöhnlich, und es kann eine Weile dauern, sie zu verstehen. Denken Sie daran, dass — ist eine Abkürzung für Static Single Assignment. Es handelt sich um eine Zwischenrepräsentation des Codes, die von Compilern verwendet wird, bei der jeder Variablen einmalig ein Wert zugewiesen wird. Dies eignet sich hervorragend zur Darstellung einfacher Funktionen, wie z.B. unserer Funktion myAdd, die oben gezeigt wurde, jedoch nicht für komplexere Funktionen – wie die in diesem Abschnitt behandelte Funktion sum. Insbesondere verändern sich die Variablen während der Ausführung der Schleife. i und n.
SSA überwindet das Limit der einmaligen Zuweisung von Variablenwerten mittels einer sogenannten Instruktion phi (ihr Name stammt aus dem griechischen Alphabet). Das Problem ist, dass für die Bildung der SSA-Code-Repräsentation in Sprachen wie C einige Tricks benötigt werden. Das Ergebnis des Aufrufs dieser Instruktion ist der aktuelle Wert der Variablen (i oder n), während als Parameter eine Liste von Basisblöcken verwendet wird. Betrachten wir zum Beispiel eine solche Instruktion:
t0 = phi [entry: 0:int, for.body: t6] #n Ihre Bedeutung ist wie folgt: Wenn der vorherige Basisblock der Block entry (Eingang) war, dann ist t0 — eine Konstante 0, und wenn der vorherige Basisblock for.body, dann müssen Sie den Wert t6 aus diesem Block übernehmen. Das kann alles ziemlich rätselhaft erscheinen, aber dieses System stellt die Funktionalität von SSA sicher. Aus menschlicher Sicht wird das Verständnis des Codes komplizierter, aber die Tatsache, dass jeder Wert nur einmal zugewiesen wird, vereinfacht viele Optimierungen erheblich.
Beachten Sie, dass Sie beim Schreiben eines eigenen Compilers normalerweise nicht mit solchen Dingen konfrontiert werden. Selbst Clang generiert nicht all diese Anweisungen phi, es verwendet das System alloca (das ähnelt der Arbeit mit normalen lokalen Variablen). Dann, während eines Optimierungsdurchlaufs in LLVM, genannt , werden die Anweisungen alloca in die SSA-Form umgewandelt. TinyGo hingegen erhält die Eingaben von Go SSA, die, praktisch, bereits in die SSA-Form umgewandelt wurden.
Eine weitere Innovation des betrachteten Intermediär-Codes besteht darin, dass der Zugriff auf die Elemente eines Slices über den Index als Adressberechnung und Dereferenzierung des erhaltenen Zeigers dargestellt wird. Hier kann man auch die unmittelbare Hinzufügung von Konstanten zum IR-Code sehen (zum Beispiel — 1:int). Im Beispiel mit der Funktion myAdd Ähnliche Konzepte wurden hier nicht verwendet. Jetzt, nachdem wir diese Besonderheiten verstanden haben, schauen wir uns an, wie dieser Code in LLVM IR umgewandelt wird:
define i64 @sum(i64* %ptr, i64 %len, i64 p) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, ref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, ref.next ]
%2 = icmp slt i64 %1, %len
br i1 %2, label %for.body, label %for.done
for.body: ; preds = %for.loop
%3 = getelementptr i64, i64* %ptr, i64 %1
%4 = load i64, i64* %3
%5 = add i64 %0, %4
%6 = add i64 %1, 1
br label %for.loop
for.done: ; preds = %for.loop
ret i64 %0
} Hier können wir, wie zuvor, die gleiche Struktur sehen, die andere syntaktische Konstrukte beinhaltet. Zum Beispiel, in den Aufrufen phi haben sich die Werte und Labels vertauscht. Dennoch gibt es hier etwas, worauf man besonders achten sollte.
Zunächst einmal ist hier eine völlig andere Funktionssignatur zu erkennen. LLVM unterstützt keine Slices, und als Optimierung hat der TinyGo-Compiler, der diesen intermedialen Code generierte, die Beschreibung dieser Datenstruktur in Teile zerlegt. Er könnte drei Elemente des Slices darstellen (ptr, len und cap) in Form einer Struktur (struct), aber die Darstellung als drei separate Entitäten ermöglicht einige Optimierungen. Andere Compiler können Slices anders darstellen, abhängig von den Funktionsaufrufvereinbarungen der Zielplattform.
Eine weitere interessante Eigenschaft dieses Codes ist die Verwendung des Befehls getelementptr (häufig abgekürzt als GEP).
Dieser Befehl arbeitet mit Zeigern und wird verwendet, um einen Zeiger auf ein Element im Slice zu erhalten. Lassen Sie uns das mit dem folgenden Code in C vergleichen:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Oder mit folgendem, equivalenter Code:
int* sliceptr(int *ptr, int index) {
return ptr + index;
} Das Wichtigste dabei ist, dass der Befehl getelementptr keine Dereferenzierungsoperationen durchführt. Er berechnet lediglich einen neuen Zeiger basierend auf dem vorhandenen. Man kann ihn als Befehle betrachten mul und add auf Hardwareebene. Weitere Details zum GEP-Befehl finden Sie .
Eine weitere interessante Eigenschaft dieses Zwischencodes ist die Verwendung des Befehls icmp. Dies ist eine allgemeine Anleitung zur Implementierung des Vergleichs von Ganzzahlen. Das Ergebnis dieser Anweisung ist immer ein Wert des Typs i1 — ein boolescher Wert. In diesem Fall erfolgt der Vergleich mit dem Schlüsselwort slt (signed less than), da wir zwei Zahlen vergleichen, die zuvor als Typ dargestellt wurden int. Wenn wir zwei vorzeichenlose Ganzzahlen vergleichen würden, hätten wir die Anweisung icmp, während das bei der Vergleichsanweisung verwendete Schlüsselwort wäre ult. Für den Vergleich von Gleitkommazahlen wird eine andere Anweisung verwendet, fcmp, die ähnlich funktioniert.
Ergebnisse
Ich denke, dass ich in diesem Material die wichtigsten Merkmale von LLVM IR behandelt habe. Natürlich gibt es hier noch viel mehr. Insbesondere kann in der Zwischenrepräsentation des Codes eine Vielzahl von Anmerkungen enthalten sein, die es ermöglichen, bei Optimierungsdurchläufen bestimmte Merkmale des Codes zu berücksichtigen, die dem Compiler bekannt sind und die nicht auf andere Weise im IR ausgedrückt werden können. Zum Beispiel ist da das Flag inbounds für die GEP-Anweisung oder die Flags nsw und nuw, die zu der Anweisung hinzugefügt werden können. addDas Gleiche gilt für das Schlüsselwort private, der dem Optimierer signalisiert, dass die als solche gekennzeichnete Funktion nicht von außerhalb der aktuellen Kompilationseinheit referenziert wird. Dies ermöglicht eine Vielzahl interessanter interproceduraler Optimierungen, wie die Entfernung ungenutzter Argumente.
Details zu LLVM finden Sie in , auf die Sie häufig zurückgreifen werden, wenn Sie Ihren eigenen Compiler auf der Basis von LLVM entwickeln. Hier ist , der die Entwicklung eines Compilers für eine sehr einfache Sprache behandelt. Beide Informationsquellen werden Ihnen bei der Erstellung Ihres eigenen Compilers nützlich sein.
Sehr geehrte Leser! Nutzen Sie LLVM?
Quelle: habr.com
