Die Entwicklung eines Compilers ist eine sehr anspruchsvolle Aufgabe. Doch zum Glück wird die Lösung dieses Problems durch die Entwicklung von Projekten wie LLVM erheblich erleichtert, was es sogar einem allein arbeitenden Programmierer ermöglicht, eine neue Sprache zu schaffen, die in der Leistung mit C vergleichbar ist. Die Arbeit mit LLVM wird dadurch erschwert, dass dieses System durch einen enormen Codeumfang gekennzeichnet ist, der nur wenig Dokumentation bietet. Um diesen Nachteil zu beheben, plant der Autor des Materials, dessen Übersetzung wir heute veröffentlichen, Beispiele von in Go geschriebenem Code zu präsentieren und zu zeigen, wie sie zunächst in , und dann in LLVM IR unter Verwendung des Compilers übertragen werden. Der Go SSA- und LLVM IR-Code wurde etwas bearbeitet, um einiges zu entfernen, das für die hier bereitgestellten Erklärungen nicht relevant ist, sodass diese Erklärungen verständlicher werden.
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 wahrscheinlich könnte man es nicht einfacher machen. Sie wird in folgenden Go SSA-Code übersetzt:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0In dieser Darstellung der Funktion werden die Datentypen rechts angegeben, die in den meisten Fällen ignoriert werden können.
Dieses kleine Beispiel zeigt bereits einen der Aspekte von SSA. Bei der Umwandlung des Codes in die SSA-Form wird jeder Ausdruck in die elementarsten Teile zerlegt, aus denen er besteht. In unserem Fall stellt der Befehl return a + bin Wirklichkeit zwei Operationen dar: die Addition zweier Zahlen und die Rückgabe des Ergebnisses.
Außerdem lassen sich hier die grundlegenden Blöcke des Programms erkennen, in diesem Code gibt es nur einen Block - den Eingangsblock (entry block). Über Blöcke werden wir später ausführlicher sprechen.
Der 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 zu bemerken, dass, obwohl hier andere syntaktische Konstruktionen verwendet werden, die Struktur der Funktion im Wesentlichen unverändert geblieben ist. Der LLVM IR-Code ist ein wenig stärker als der Go SSA-Code und ähnelt C. Hier, in der Funktionsdeklaration, steht zuerst die Beschreibung des zurückgegebenen Datentyps, der Argumenttyp wird vor dem Namen des Arguments angegeben. Außerdem steht vor den Namen der globalen Entitäten ein Symbol @, und vor den Namen der lokalen — ein Symbol % (eine Funktion wird ebenfalls als globale Entität betrachtet).
Eine der Besonderheiten dieses Codes, auf die man achten sollte, ist, dass die Entscheidung über die Darstellung des Go-Typs int, der als 32-Bit- oder 64-Bit-Wert dargestellt werden kann, je nach Compiler und Zielkompilierung, beim Erstellen des LLVM IR-Codes getroffen wird. Dies ist einer der vielen Gründe, warum der LLVM IR-Code nicht, wie viele denken, plattformunabhängig ist. Ein solcher Code, der für eine Plattform erstellt wurde, kann nicht einfach für eine andere Plattform kompiliert werden (es sei denn, man geht an das Problem ).
Ein weiterer interessanter Punkt, den man beachten sollte, ist, dass der Typ i64 keine vorzeichenbehaftete Ganzzahl ist: Er ist in Bezug auf die Darstellung des Vorzeichens der Zahl neutral. Je nach Anweisung kann er sowohl vorzeichenbehaftete als auch vorzeichenlose Zahlen darstellen. Im Fall der Darstellung der Additionsoperation spielt dies keine Rolle, daher gibt es hier keinen Unterschied beim Umgang mit vorzeichenbehafteten oder vorzeichenlosen Zahlen. Hier sollte erwähnt werden, dass Überlauf einer vorzeichenbehafteten Ganzzahl in C zu unbestimmtem Verhalten führt, weshalb das Clang-Frontend der Operation ein Flag nsw (no signed wrap) hinzufügt, was LLVM anzeigt, dass es davon ausgehen kann, dass beim Addieren niemals ein Überlauf auftritt.
Dies kann für einige Optimierungen wichtig sein. Zum Beispiel erfordert das Addieren zweier Werte i16 auf einer 32-Bit-Plattform (mit 32-Bit-Registrierungen), nach Durchführung der Addition, eine Vorzeichenverlängerungsoperation, um im Bereich zu bleiben i16. Daher erweist sich oft die Durchführung arithmetischer Operationen unter Berücksichtigung der Maschinenregistergrößen als effizienter.
Was mit diesem IR-Code im Weiteren passiert, interessiert uns jetzt nicht besonders. Der Code wird optimiert (aber im Falle eines so einfachen Beispiels wie unserem wird nichts mehr optimiert), und dann wird er in Maschinencode umgewandelt.
Zweites Beispiel
Das nächste Beispiel, das wir betrachten werden, wird etwas komplizierter. Genauer gesagt handelt es sich um eine Funktion, die einen Slice 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 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 sichtbar, die für die Darstellung von Code in SSA-Form typisch sind. Wahrscheinlich ist das offensichtlichste Merkmal dieses Codes, dass es hier keine strukturierten Steuerbefehle für den Kontrollfluss gibt. Für die Steuerung des Kontrollflusses gibt es hier nur bedingte und unbedingte Sprünge, und wenn man diesen Befehl als einen zur Steuerung des Flusses zählt, den Rückgabebefehl.
Tatsächlich kann man hier bemerken, dass das Programm nicht in Blöcke unter Verwendung von geschweiften Klammern (wie in Sprachen der C-Familie) unterteilt ist. Es ist durch Labels unterteilt, was an Assemblersprachen erinnert, und wird als eine Folge von Basisblöcken präsentiert. In SSA werden Basisblöcke als durchgehende Codefolgen bezeichnet, die mit einem Label beginnen und mit Anweisungen zum Abschluss des Basisblocks enden, zum Beispiel — return und jump.
Ein weiteres interessantes Detail dieses Codes wird durch die Anweisung phi. Diese Anweisung ist ziemlich ungewöhnlich, und es kann einige Zeit dauern, sie zu verstehen. Denken Sie daran, dass — es ist eine Abkürzung für Static Single Assignment. Es ist eine Zwischenrepräsentation von Code, die von Compilern verwendet wird, bei der jeder Variablen nur einmal ein Wert zugewiesen wird. Dies eignet sich hervorragend für einfache Funktionen, wie unsere Funktion myAdd, die oben gezeigt wurde, passt jedoch nicht für komplexere Funktionen — wie die im vorliegenden Abschnitt behandelte Funktion. sum. Insbesondere während der Ausführung einer Schleife ändern sich die Variablen. i und n.
SSA umgeht die Einschränkung der einmaligen Zuweisung von Werten an Variablen durch die Verwendung einer sogenannten Anweisung phi (ihr Name stammt aus dem griechischen Alphabet). Der Grund dafür ist, dass ein SSA-Code für Sprachen wie C generiert werden muss, erfordert einige Tricks. Das Ergebnis des Aufrufs dieser Anweisung ist der aktuelle Wert der Variablen (i oder n), und ihre Parameter bestehen aus einer Liste von Basisblöcken. Zum Beispiel betrachten wir eine solche Anweisung:
t0 = phi [entry: 0:int, for.body: t6] #n Ihre Bedeutung ist folgende: Wenn der vorherige Basisblock der Block entry war, dann ist t0 eine Konstante 0, und wenn der vorherige Basisblock for.bodywar, dann muss der Wert t6 aus diesem Block genommen werden. Das erscheint vielleicht ziemlich mysteriös, aber durch diesen Mechanismus wird die Funktionalität von SSA sichergestellt. Aus menschlicher Sicht kompliziert dies das Verständnis des Codes, aber die Tatsache, dass jeder Wert nur einmal zugewiesen wird, vereinfacht viele Optimierungen erheblich.
Bitte beachten Sie, dass Sie, wenn Sie Ihren eigenen Compiler schreiben, in der Regel nicht mit solchen Dingen konfrontiert werden. Selbst Clang generiert nicht all diese Anweisungen phi, es verwendet einen Mechanismus alloca (er ähnelt der Arbeit mit normalen lokalen Variablen). Dann werden während eines Optimierungspasses von LLVM, der als bezeichnet wird, die Anweisungen in die SSA-Form umgewandelt. TinyGo hingegen erhält Daten von Go SSA, die, was praktisch ist, bereits in die SSA-Form umgewandelt wurden. alloca Ein weiteres neues Merkmal des betrachteten Fragments des Zwischencodes besteht darin, dass der Zugriff auf Elemente eines Slices über den Index in Form einer Adressberechnungsoperation und einer Dereferenzierungsoperation des erhaltenen Zeigers dargestellt wird. Hier sieht man auch die direkte Einfügung von Konstanten in den IR-Code (zum Beispiel —
1:int ). Im Beispiel mit der Funktion). Im Beispiel mit der Funktion myAdd So etwas wurde nicht verwendet. Jetzt, nachdem wir diese Besonderheiten geklärt haben, schauen wir uns an, wie dieser Code aussieht, wenn er 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 sehen wir wie zuvor die gleiche Struktur, die andere syntaktische Konstrukte umfasst. Zum Beispiel in den Aufrufen phi haben sich Werte und Bezeichner vertauscht. Allerdings gibt es hier auch etwas, auf das man besonders achten sollte.
Zunächst einmal sieht man hier eine völlig andere Funktionssignatur. LLVM unterstützt keine Slices, weshalb der TinyGo-Compiler, der diesen Zwischencode erzeugt hat, die Beschreibung dieser Datenstruktur in Teile zerlegt hat. Er könnte drei Elemente eines Slices (ptr, len und cap) in Form einer Struktur (struct) darstellen, aber ihre Darstellung als drei separate Entitäten ermöglicht gewisse Optimierungen. Andere Compiler könnten das Slice noch anders darstellen, abhängig von den Funktionsaufrufkonventionen der Zielplattform.
Eine weitere interessante Eigenschaft dieses Codes ist die Verwendung der Anweisung getelementptr (die oft als GEP abgekürzt wird).
Diese Anweisung arbeitet mit Zeigern und wird verwendet, um einen Zeiger auf ein Element eines Slices zu erhalten. Zum Beispiel, lassen Sie uns es mit dem folgenden Code, der in C geschrieben wurde, vergleichen:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Oder mit dem folgenden, das gleichwertig ist:
int* sliceptr(int *ptr, int index) {
return ptr + index;
} Das Wichtigste hier ist, dass die Anweisung getelementptr keine Dereferenzierungsoperationen ausführt. Sie berechnet lediglich einen neuen Zeiger basierend auf dem bestehenden. Man kann sie als Anweisung mul und add auf Hardwareebene ansehen. Details zur GEP-Anweisung können nachgelesen werden. .
Eine weitere interessante Eigenschaft dieses Zwischencodes ist die Verwendung der Anweisung icmp. Dies ist eine allgemeine Anweisung, die zur Realisierung des Vergleichs von Ganzzahlen verwendet wird. Das Ergebnis dieser Anweisung ist immer ein Wert vom Typ i1 — ein boolescher Wert. In diesem Fall erfolgt der Vergleich unter Verwendung des Schlüsselworts slt (signed less than), da wir zwei Zahlen vergleichen, die zuvor als intdargestellt wurden. Wenn wir zwei unsigned Ganzzahlen verglichen hätten, hätten wir die Anweisung icmpverwendet, und das Schlüsselwort, das beim Vergleich verwendet worden wäre, 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 noch viele weitere Aspekte. Insbesondere kann die Zwischenrepräsentation des Codes viele Anmerkungen enthalten, die es ermöglichen, bestimmte Eigenschaften des Codes bei den Optimierungspässen zu berücksichtigen, die dem Compiler bekannt sind und die sich anderweitig nicht in IR ausdrücken lassen. Zum Beispiel ist dies das Flag inbounds der 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, das dem Optimierer signalisiert, dass auf die als solche gekennzeichnete Funktion von außerhalb der aktuellen Übersetzungseinheit nicht zugegriffen wird. Dies ermöglicht eine Vielzahl interessanter interproceduraler Optimierungen, wie die Eliminierung ungenutzter Argumente.
Details zu LLVM können in gelesen werden, auf die Sie häufig zurückgreifen werden, wenn Sie Ihren eigenen Compiler auf der Basis von LLVM entwickeln. Hier ist , in dem die Entwicklung eines Compilers für eine sehr einfache Sprache behandelt wird. Diese beiden Informationsquellen werden Ihnen bei der Erstellung Ihres eigenen Compilers nützlich sein.
Liebe Leser! Benutzen Sie LLVM?
Quelle: habr.com
