Die Compilerentwicklung ist eine sehr schwierige Aufgabe. Glücklicherweise wird mit der Entwicklung von Projekten wie LLVM die Lösung dieses Problems erheblich vereinfacht, sodass selbst ein einzelner Programmierer eine neue Sprache erstellen kann, deren Leistung C nahe kommt. Die Arbeit mit LLVM wird durch die Tatsache erschwert, dass dieses System durch eine große Menge an Code dargestellt wird, der mit einer kleinen Dokumentation ausgestattet ist. Um diesen Fehler zu beheben, wird der Autor des Materials, das wir heute veröffentlichen, Beispiele für in Go geschriebenen Code demonstrieren und zeigen, wie sie zuerst mit dem
TinyGO- Compiler an
Go SSA und dann an LLVM IR übertragen werden. Der Go SSA- und LLVM-IR-Code wurde leicht bearbeitet. Etwas, das nicht zu den hier gegebenen Erklärungen gehört, wurde entfernt, um diese Erklärungen verständlicher zu machen.
Erstes Beispiel
Die erste Funktion, die ich hier analysieren werde, ist ein einfacher Mechanismus zum Hinzufügen von Zahlen:
func myAdd(a, b int) int{ return a + b }
Diese Funktion ist sehr einfach, und vielleicht ist es einfacher, nichts zu finden. Es wird in den folgenden Go SSA-Code übersetzt:
func myAdd(a int, b int) int: entry: t0 = a + b int return t0
Mit dieser Darstellung der Funktion werden rechts Hinweise zu Datentypen platziert. In den meisten Fällen können Sie diese ignorieren.
In diesem kleinen Beispiel können Sie bereits den Kern eines Aspekts von SSA sehen. Beim Konvertieren von Code in SSA-Form wird jeder Ausdruck in die elementarsten Teile unterteilt, aus denen er besteht. In unserem Fall repräsentiert der Befehl
return a + b tatsächlich zwei Operationen: Hinzufügen von zwei Zahlen und Zurückgeben des Ergebnisses.
Außerdem sehen Sie hier die Grundblöcke des Programms. In diesem Code gibt es nur einen Block - den Eingang (Eingabeblock). Wir werden mehr über die Blöcke unten sprechen.
Go SSA-Code kann einfach in LLVM IR konvertiert werden:
define i64 @myAdd(i64 %a, i64 %b) { entry: %0 = add i64 %a, %b ret i64 %0 }
Möglicherweise stellen Sie fest, dass sich die Struktur der Funktion im Wesentlichen nicht geändert hat, obwohl hier andere syntaktische Konstruktionen verwendet werden. Der LLVM-IR-Code ist etwas stärker als der Go-SSA-Code, ähnlich wie C. Hier wird in der Funktionsdeklaration zunächst eine Beschreibung des zurückgegebenen Datentyps angegeben. Der Argumenttyp wird vor dem Argumentnamen angegeben. Um die IR-Analyse zu vereinfachen, wird den Namen globaler Entitäten das
@ -Symbol und vor den Namen lokaler Entitäten das
% -Zeichen vorangestellt (die Funktion wird auch als globale Entität betrachtet).
Eine der Funktionen dieses Codes, auf die Sie achten müssen, ist, dass beim Erstellen von LLVM die Entscheidung getroffen wird, den Typ Go
int darzustellen, der je nach Compiler und Kompilierungszweck durch einen 32-Bit- oder 64-Bit-Wert dargestellt werden kann IR-Code. Dies ist einer der vielen Gründe, warum LLVM-IR-Code nicht plattformunabhängig ist. Ein solcher Code, der für eine Plattform erstellt wurde, kann nicht einfach für eine andere Plattform übernommen und kompiliert werden (es sei denn, Sie gehen diese Aufgabe
mit äußerster Vorsicht an ).
Ein weiterer interessanter Punkt ist, dass der Typ
i64 keine vorzeichenbehaftete Ganzzahl ist: Er ist neutral in Bezug auf die Darstellung des Vorzeichens der Zahl. Abhängig von der Anweisung kann es sowohl vorzeichenbehaftete als auch vorzeichenlose Zahlen darstellen. Bei der Darstellung der Additionsoperation spielt dies keine Rolle, so dass es keinen Unterschied gibt, mit Zahlen mit oder ohne Vorzeichen zu arbeiten. An dieser Stelle möchte ich darauf hinweisen, dass in C ein Überlauf einer vorzeichenbehafteten Ganzzahlvariablen zu einem undefinierten Verhalten führt. Daher fügt das Clang-Frontend der
nsw das
nsw (kein vorzeichenbehafteter
nsw ) hinzu, das LLVM anzeigt, dass es von der Annahme ausgehen kann, dass mit Zugabe tritt nie Überlauf auf.
Dies kann für einige Optimierungen wichtig sein. Zum Beispiel
i16 das Hinzufügen von zwei
i16 Werten auf einer 32-Bit-Plattform (mit 32-Bit-Registern), dass nach Abschluss des Hinzufügens die Vorzeichenerweiterungsoperation im
i16 Bereich
i16 . Aus diesem Grund ist es häufig effizienter, ganzzahlige Operationen unter Berücksichtigung der Maschinengröße des Registers durchzuführen.
Was in Zukunft mit diesem IR-Code passiert, ist für uns derzeit nicht besonders interessant. Der Code wird optimiert (aber bei einem so einfachen Beispiel wie unserem ist bereits nichts optimiert) und dann in Maschinencode konvertiert.
Zweites Beispiel
Das folgende Beispiel, das wir untersuchen werden, wird etwas komplizierter sein. Wir sprechen nämlich von einer Funktion, die das Stück von ganzen 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 t0
Hier sehen Sie bereits weitere Konstruktionen, die für die Darstellung von Code in Form von SSA spezifisch sind. Das wahrscheinlich offensichtlichste Merkmal dieses Codes ist die Tatsache, dass es keine strukturierten Flusssteuerungsbefehle gibt. Um den Berechnungsfluss zu steuern, gibt es nur bedingte und bedingungslose Sprünge. Wenn wir diesen Befehl als Befehl zur Steuerung des Ablaufs betrachten, als Rückgabebefehl.
In der Tat können Sie hier darauf achten, dass das Programm nicht mit geschweiften Klammern in Blöcke unterteilt ist (wie in den Sprachen der C-Familie). Es ist durch Beschriftungen unterteilt, die Assemblersprachen ähneln, und wird in Form von Basisblöcken dargestellt. In SSA sind Basisblöcke zusammenhängende Codesequenzen, die mit einer Beschriftung beginnen und mit Anweisungen zum Vervollständigen des Basisblocks enden, z. B.
return und
jump .
Ein weiteres interessantes Detail dieses Codes ist die
phi Anweisung. Die Anweisung ist ziemlich ungewöhnlich, es kann einige Zeit dauern, sie herauszufinden. Denken Sie daran, dass
SSA für Static Single Assignment steht. Dies ist eine Zwischendarstellung des von Compilern verwendeten Codes, bei dem jede Variable nur einmal zugewiesen wird. Dies ist
myAdd um einfache Funktionen wie unsere
myAdd gezeigte
myAdd Funktion
myAdd , nicht jedoch für komplexere Funktionen wie die in diesem Abschnitt beschriebene
sum . Insbesondere während der Ausführung der Schleife ändern sich die Variablen
i und
n .
SSA umgeht die Beschränkung einer einzelnen Zuweisung von Variablenwerten mithilfe des sogenannten
phi Befehls (sein Name stammt aus dem griechischen Alphabet). Tatsache ist, dass Sie auf einige Tricks zurückgreifen müssen, damit die SSA-Darstellung des Codes für Sprachen wie C erstellt wird. Das Ergebnis des Aufrufs dieser Anweisung ist der aktuelle Wert der Variablen (
i oder
n ), und eine Liste von Basisblöcken wird als Parameter 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 Eingabeblock (Eingabeblock) war, dann ist
t0 die Konstante
0 , und wenn der vorherige Basisblock
for.body , müssen Sie den Wert
t6 von diesem Block nehmen. All dies mag ziemlich mysteriös aussehen, aber dank dieses Mechanismus ist SSA gewährleistet. Aus menschlicher Sicht erschwert dies das Verständnis des Codes, aber die Tatsache, dass jeder Wert nur einmal zugewiesen wird, vereinfacht viele Optimierungen erheblich.
Beachten Sie, dass Sie sich normalerweise nicht mit solchen Dingen befassen müssen, wenn Sie Ihren eigenen Compiler schreiben. Selbst
alloca Clang nicht alle diese
phi Anweisungen generiert, verwendet er den
alloca (er ähnelt der Arbeit mit normalen lokalen Variablen). Wenn dann ein LLVM-Optimierungsdurchlauf namens
mem2reg ausgeführt wird , werden die
alloca in die SSA-Form konvertiert. TinyGo erhält jedoch Eingaben von Go SSA, die bequemerweise bereits in SSA-Form konvertiert wurden.
Eine weitere Neuerung dieses Zwischencodes besteht darin, dass der Zugriff auf die Slice-Elemente durch Index in Form der Operation zum Berechnen der Adresse und der Dereferenzierungsoperation des erhaltenen Zeigers dargestellt wird. Hier sehen Sie die direkte Hinzufügung von Konstanten zum IR-Code (zum Beispiel -
1:int ). Im Beispiel mit der Funktion
myAdd dies nicht verwendet. Nachdem wir diese Funktionen herausgefunden haben, werden wir uns ansehen, wie sich dieser Code bei der Konvertierung in das LLVM-IR-Formular entwickeln 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 dieselbe Struktur, die auch andere syntaktische Konstruktionen enthält. Beispielsweise werden bei
phi Aufrufen Werte und Beschriftungen vertauscht. Es gibt jedoch auch etwas, dem man besondere Aufmerksamkeit schenken sollte.
Für den Anfang sehen Sie hier eine völlig andere Signatur der Funktion. LLVM unterstützt keine Slices. Daher hat der TinyGo-Compiler, der diesen Zwischencode generiert hat, die Beschreibung dieser Datenstruktur in Teile unterteilt. Er könnte drei Slice-Elemente (
ptr ,
len und
cap ) als Struktur (struct) darstellen, aber die Darstellung als drei separate Entitäten ermöglicht einige Optimierungen. Andere Compiler können das Slice auf andere Weise präsentieren. Dies hängt von den Konventionen zum Aufrufen der Funktionen der Zielplattform ab.
Ein weiteres interessantes Merkmal dieses Codes ist die Verwendung der
getelementptr (oft kurz GEP genannt).
Diese Anweisung arbeitet mit Zeigern und wird verwendet, um einen Zeiger auf ein Slice-Element zu erhalten. Vergleichen wir es beispielsweise 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, dass die Anweisung
getelementptr Dereferenzierungsoperationen ausführt. Es wird nur ein neuer Zeiger basierend auf dem vorhandenen berechnet. Es kann als
mul interpretiert werden und
add auf Hardwareebene
add . Details zu den GEP-Anweisungen finden Sie
hier .
Ein weiteres interessantes Merkmal dieses Zwischencodes ist die Verwendung des
icmp . Dies ist eine allgemeine Anweisung, die zum Implementieren von Ganzzahlvergleichen verwendet wird. Das Ergebnis dieser Anweisung ist immer ein Wert vom Typ
i1 - ein logischer Wert. In diesem Fall wird ein Vergleich mit dem Schlüsselwort
slt (weniger als signiert) durchgeführt, da zwei Zahlen verglichen werden, die zuvor durch den Typ
int . Wenn wir zwei vorzeichenlose Ganzzahlen vergleichen würden, würden wir
icmp als Anweisung verwenden, und das im Vergleich verwendete Schlüsselwort wäre
ult . Um Gleitkommazahlen zu vergleichen, wird eine andere Anweisung verwendet,
fcmp , die auf ähnliche Weise funktioniert.
Zusammenfassung
Ich glaube, dass ich in diesem Artikel die wichtigsten Merkmale von LLVM IR untersucht habe. Natürlich gibt es noch viele Dinge. Insbesondere in der Zwischendarstellung des Codes kann es viele Anmerkungen geben, die es ermöglichen, bestimmte Merkmale des Codes zu berücksichtigen, die dem Compiler während Optimierungsdurchläufen bekannt sind und die im IR nicht auf andere Weise ausgedrückt werden können. Dies sind beispielsweise das
inbounds Flag des
inbounds Befehls oder die
nsw und
nuw , die der
add Anweisung hinzugefügt werden können. Gleiches gilt für das
private Schlüsselwort, das dem Optimierer anzeigt, dass die von ihm markierte Funktion nicht von außerhalb der aktuellen Kompilierungseinheit referenziert wird. Auf diese Weise können Sie viele interessante interprozedurale Optimierungen durchführen, z. B. das Entfernen nicht verwendeter Argumente.
Weitere Informationen zu LLVM finden Sie in der
Dokumentation , auf die Sie bei der Entwicklung Ihres eigenen LLVM-basierten Compilers häufig verweisen. Hier ist eine
Anleitung , die die Compilerentwicklung für eine sehr einfache Sprache beschreibt. Diese beiden Informationsquellen sind nützlich, wenn Sie Ihren eigenen Compiler erstellen.
Liebe Leser! Verwenden Sie LLVM?