Die Entwicklung eines Compilers ist eine sehr schwierige Aufgabe. Aber glücklicherweise wird die Lösung dieses Problems mit der Entwicklung von Projekten wie LLVM erheblich vereinfacht, sodass sogar ein einzelner Programmierer eine neue Sprache erstellen kann, deren Leistung C nahe kommt. Die Arbeit mit LLVM wird dadurch erschwert, dass dies der Fall ist Das System wird durch eine riesige Menge an Code repräsentiert, ausgestattet mit wenig Dokumentation. Um diesen Mangel zu beheben, wird der Autor des Materials, dessen Übersetzung wir heute veröffentlichen, Beispiele für in Go geschriebenen Code vorführen und zeigen, wie sie zunächst übersetzt werden und dann in LLVM IR mit dem Compiler . Der Go SSA- und LLVM IR-Code wurde leicht bearbeitet, um Dinge zu entfernen, die für die hier gegebenen Erklärungen nicht relevant sind, um die Erklärungen verständlicher zu machen.
Erstes Beispiel
Die erste Funktion, die ich mir hier ansehen werde, ist ein einfacher Mechanismus zum Addieren von Zahlen:
func myAdd(a, b int) int{
return a + b
}Diese Funktion ist sehr einfach und vielleicht könnte nichts einfacher sein. Es wird in den folgenden Go SSA-Code übersetzt:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Bei dieser Ansicht werden die Datentyphinweise rechts platziert und können in den meisten Fällen ignoriert werden.
Dieses kleine Beispiel lässt Sie bereits die Essenz eines Aspekts von SSA erkennen. Bei der Konvertierung von Code in die SSA-Form wird nämlich jeder Ausdruck in die elementarsten Teile zerlegt, aus denen er besteht. In unserem Fall der Befehl return a + bstellt tatsächlich zwei Operationen dar: das Addieren zweier Zahlen und das Zurückgeben des Ergebnisses.
Außerdem sehen Sie hier die Grundblöcke des Programms; in diesem Code gibt es nur einen Block – den Eingabeblock. Wir werden weiter unten mehr über Blöcke sprechen.
Der Go SSA-Code lässt sich problemlos in LLVM IR konvertieren:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Was Sie bemerken können, ist, dass hier zwar unterschiedliche syntaktische Strukturen verwendet werden, die Struktur der Funktion jedoch grundsätzlich unverändert bleibt. Der LLVM-IR-Code ist etwas stärker als der Go-SSA-Code, ähnlich wie C. Hier gibt es in der Funktionsdeklaration zunächst eine Beschreibung des Datentyps, den sie zurückgibt, der Argumenttyp wird vor dem Argumentnamen angegeben. Um das IR-Parsing zu vereinfachen, wird den Namen globaler Entitäten außerdem das Symbol vorangestellt @, und vor lokalen Namen steht ein Symbol % (Eine Funktion wird auch als globale Entität betrachtet).
Bei diesem Code ist zu beachten, dass Go die Typdarstellungsentscheidung trifft int, der je nach Compiler und Ziel der Kompilierung als 32-Bit- oder 64-Bit-Wert dargestellt werden kann, wird akzeptiert, wenn LLVM den IR-Code generiert. Dies ist einer der vielen Gründe, warum LLVM-IR-Code nicht, wie viele Leute denken, plattformunabhängig ist. Ein solcher Code, der für eine Plattform erstellt wurde, kann nicht einfach übernommen und für eine andere Plattform kompiliert werden (es sei denn, Sie sind für die Lösung dieses Problems geeignet). ).
Ein weiterer interessanter Punkt ist der Typ i64 ist keine ganze Zahl mit Vorzeichen: Sie ist hinsichtlich der Darstellung des Vorzeichens der Zahl neutral. Je nach Anweisung kann es sowohl vorzeichenbehaftete als auch vorzeichenlose Zahlen darstellen. Bei der Darstellung der Additionsoperation spielt dies keine Rolle, es gibt also keinen Unterschied, ob mit vorzeichenbehafteten oder vorzeichenlosen Zahlen gearbeitet wird. Hier möchte ich darauf hinweisen, dass in der C-Sprache der Überlauf einer vorzeichenbehafteten Ganzzahlvariablen zu undefiniertem Verhalten führt, sodass das Clang-Frontend der Operation ein Flag hinzufügt nsw (kein signierter Wrap), was LLVM mitteilt, dass davon ausgegangen werden kann, dass die Addition niemals überläuft.
Dies kann für einige Optimierungen wichtig sein. Beispiel: Addieren von zwei Werten i16 Auf einer 32-Bit-Plattform (mit 32-Bit-Registern) ist nach der Addition eine Vorzeichenerweiterungsoperation erforderlich, um im Bereich zu bleiben i16. Aus diesem Grund ist es oft effizienter, ganzzahlige Operationen basierend auf Maschinenregistergrößen durchzuführen.
Was mit diesem IR-Code weiter passiert, interessiert uns derzeit nicht besonders. Der Code wird optimiert (aber bei einem einfachen Beispiel wie unserem ist nichts optimiert) und dann in Maschinencode umgewandelt.
Zweites Beispiel
Das nächste Beispiel, das wir uns ansehen werden, wird etwas komplizierter sein. Wir sprechen nämlich von einer Funktion, die ein Stück ganzer Zahlen 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 konvertiert:
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 sehen Sie bereits weitere typische Konstruktionen zur Darstellung von Code in der SSA-Form. Das vielleicht offensichtlichste Merkmal dieses Codes ist die Tatsache, dass es keine strukturierten Flusskontrollbefehle gibt. Um den Rechenfluss zu steuern, gibt es nur bedingte und unbedingte Sprünge und, wenn wir diesen Befehl als Befehl zur Steuerung des Flusses betrachten, einen Rücksprungbefehl.
Tatsächlich kann man hier darauf achten, dass das Programm nicht (wie in der C-Sprachfamilie) durch geschweifte Klammern in Blöcke unterteilt wird. Es ist durch Beschriftungen unterteilt, die an Assemblersprachen erinnern, und in Form von Grundblöcken dargestellt. In SSA werden Basisblöcke als zusammenhängende Codesequenzen definiert, die mit einer Bezeichnung beginnen und mit grundlegenden Anweisungen zur Blockvervollständigung enden, z. B. − return и jump.
Ein weiteres interessantes Detail dieses Codes wird durch die Anweisung dargestellt phi. Die Anweisungen sind recht ungewöhnlich und es kann einige Zeit dauern, bis sie verstanden sind. erinnere dich daran ist die Abkürzung für Static Single Assignment. Dabei handelt es sich um eine Zwischendarstellung des von Compilern verwendeten Codes, bei der jeder Variablen nur einmal ein Wert zugewiesen wird. Dies eignet sich hervorragend, um einfache Funktionen wie unsere Funktion auszudrücken myAddDie oben gezeigte Funktion ist jedoch nicht für komplexere Funktionen wie die in diesem Abschnitt beschriebene Funktion geeignet sum. Insbesondere ändern sich Variablen während der Ausführung der Schleife i и n.
SSA umgeht die Beschränkung der einmaligen Zuweisung von Variablenwerten durch eine sogenannte Anweisung phi (sein Name ist dem griechischen Alphabet entnommen). Tatsache ist, dass man auf einige Tricks zurückgreifen muss, damit die SSA-Darstellung von Code für Sprachen wie C generiert werden kann. Das Ergebnis des Aufrufs dieser Anweisung ist der aktuelle Wert der Variablen (i oder n), und als Parameter wird eine Liste von Basisblöcken verwendet. Betrachten Sie zum Beispiel diese Anweisung:
t0 = phi [entry: 0:int, for.body: t6] #n
Seine Bedeutung ist wie folgt: Wenn der vorherige Basisblock ein Block war entry (Eingabe), dann t0 ist eine Konstante 0, und wenn der vorherige Basisblock war for.body, dann müssen Sie den Wert nehmen t6 aus diesem Block. Das mag alles ziemlich mysteriös erscheinen, aber dieser Mechanismus sorgt dafür, dass die SSA funktioniert. Aus menschlicher Sicht macht das alles den Code schwer verständlich, aber die Tatsache, dass jeder Wert nur einmal zugewiesen wird, macht viele Optimierungen viel einfacher.
Beachten Sie, dass Sie sich mit solchen Dingen normalerweise nicht befassen müssen, wenn Sie Ihren eigenen Compiler schreiben. Selbst Clang generiert nicht alle diese Anweisungen phi, es nutzt einen Mechanismus alloca (es ähnelt der Arbeit mit gewöhnlichen lokalen Variablen). Dann wird beim Ausführen ein LLVM-Optimierungsdurchlauf aufgerufen , Anweisungen alloca in SSA-Form umgewandelt. TinyGo erhält jedoch Eingaben von Go SSA, die praktischerweise bereits in die SSA-Form konvertiert sind.
Eine weitere Neuerung des betrachteten Zwischencodefragments besteht darin, dass der Zugriff auf Slice-Elemente anhand des Index in Form einer Operation zur Berechnung der Adresse und einer Operation zur Dereferenzierung des resultierenden Zeigers dargestellt wird. Hier sehen Sie das direkte Hinzufügen von Konstanten zum IR-Code (z. B. - 1:int). Im Beispiel mit der Funktion myAdd Dies wurde nicht verwendet. Nachdem wir diese Funktionen nun aus dem Weg geräumt haben, werfen wir einen Blick darauf, wie dieser Code aussieht, wenn er in die LLVM-IR-Form konvertiert wird:
define i64 @sum(i64* %ptr, i64 %len, i64 %cap) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, %deref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, %deref.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 sehen wir nach wie vor die gleiche Struktur, die andere syntaktische Strukturen umfasst. Zum Beispiel bei Anrufen phi Werte und Beschriftungen vertauscht. Allerdings gibt es hier etwas, auf das es sich zu achten lohnt.
Hier sehen Sie zunächst eine völlig andere Funktionssignatur. LLVM unterstützt keine Slices. Aus diesem Grund hat der TinyGo-Compiler, der diesen Zwischencode generiert hat, die Beschreibung dieser Datenstruktur zur Optimierung in Teile aufgeteilt. Es könnte drei Slice-Elemente darstellen (ptr, len и cap) als Struktur (struct), aber die Darstellung als drei separate Einheiten ermöglicht einige Optimierungen. Andere Compiler stellen das Slice möglicherweise auf andere Weise dar, abhängig von den Aufrufkonventionen der Funktionen der Zielplattform.
Ein weiteres interessantes Merkmal dieses Codes ist die Verwendung der Anweisung getelementptr (oft als GEP abgekürzt).
Diese Anweisung arbeitet mit Zeigern und wird verwendet, um einen Zeiger auf ein Slice-Element zu erhalten. Vergleichen wir es zum Beispiel mit dem folgenden in C geschriebenen Code:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Oder mit folgendem Äquivalent dazu:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Das Wichtigste dabei ist die Anleitung getelementptr führt keine Dereferenzierungsoperationen durch. Es berechnet lediglich einen neuen Zeiger basierend auf dem vorhandenen. Es kann als Anleitung verstanden werden mul и add auf Hardwareebene. Sie können mehr über die GEP-Anweisungen lesen .
Ein weiteres interessantes Merkmal dieses Zwischencodes ist die Verwendung der Anweisung icmp. Dies ist eine Allzweckanweisung zur Implementierung von Ganzzahlvergleichen. Das Ergebnis dieser Anweisung ist immer ein Wert vom Typ i1 — logischer Wert. In diesem Fall erfolgt ein Vergleich anhand des Schlüsselworts slt (vorzeichenlos kleiner als), da wir zwei Zahlen vergleichen, die zuvor durch den Typ dargestellt wurden int. Wenn wir zwei vorzeichenlose Ganzzahlen vergleichen würden, würden wir verwenden icmp, und das im Vergleich verwendete Schlüsselwort wäre ult. Um Gleitkommazahlen zu vergleichen, wird eine andere Anweisung verwendet: fcmp, was auf ähnliche Weise funktioniert.
Ergebnisse
Ich glaube, dass ich in diesem Material die wichtigsten Funktionen von LLVM IR behandelt habe. Natürlich gibt es hier noch viel mehr. Insbesondere kann die Zwischendarstellung des Codes viele Anmerkungen enthalten, die es Optimierungsdurchgängen ermöglichen, bestimmte dem Compiler bekannte Merkmale des Codes zu berücksichtigen, die sonst nicht in IR ausgedrückt werden können. Dies ist zum Beispiel eine Flagge inbounds GEP-Anweisungen oder Flags nsw и nuw, die der Anleitung hinzugefügt werden kann add. Das Gleiche gilt für das Schlüsselwort privateDies zeigt dem Optimierer an, dass auf die von ihm markierte Funktion nicht von außerhalb der aktuellen Kompilierungseinheit verwiesen wird. Dies ermöglicht viele interessante interprozedurale Optimierungen wie die Eliminierung nicht verwendeter Argumente.
Weitere Informationen zu LLVM finden Sie unter , auf die Sie häufig zurückgreifen, wenn Sie Ihren eigenen LLVM-basierten Compiler entwickeln. Hier , in dem es um die Entwicklung eines Compilers für eine sehr einfache Sprache geht. Beide Informationsquellen werden Ihnen beim Erstellen Ihres eigenen Compilers nützlich sein.
Liebe Leser! Verwenden Sie LLVM?
Source: habr.com