LLVM IR und Go

In diesem Artikel wird erläutert, wie Sie ein Go-Programm erstellen, z. B. einen Compiler oder einen statischen Analysator, der mithilfe der LLVM-IR-Assemblersprache mit dem LLVM-Kompilierungsframework interagiert.

TL; DR Wir haben eine Bibliothek für die Interaktion mit LLVM IR auf pure Go geschrieben. Siehe Links zu Code und ein Beispielprojekt.

Ein einfaches Beispiel für LLVM IR

(Diejenigen unter Ihnen, die mit LLVM IR vertraut sind, können mit dem nächsten Abschnitt fortfahren.)

LLVM IR ist die Low-Level-Zwischendarstellung, die vom LLVM-Kompilierungsframework verwendet wird. Sie können sich LLVM IR als plattformunabhängigen Assembler mit einer unendlichen Anzahl lokaler Register vorstellen.

Beim Entwerfen eines Compilers besteht ein großer Vorteil darin, die Quellsprache in eine Zwischendarstellung (IR) zu kompilieren, anstatt sie in die Zielarchitektur (z. B. x86) zu kompilieren.


Da viele Optimierungstechniken üblich sind (z. B. Entfernen von nicht verwendetem Code, Verteilen von Konstanten), können diese Optimierungsdurchläufe direkt auf IR-Ebene durchgeführt und von allen Zielplattformen verwendet werden.


Daher bestehen Compiler häufig aus drei Teilen: Frontend, Middleland und Backend. Jeder von ihnen führt seine eigene Aufgabe aus, akzeptiert Eingaben und / oder gibt IR-Ausgaben.

• Frontend: Kompiliert die Ausgangssprache im IR
• Middleland: optimiert IR
• Backend: Kompiliert IR in Maschinencode

Beispielprogramm für LLVM IR-Assembler

Betrachten Sie das folgende Programm, um eine Vorstellung davon zu bekommen, wie der LLVM-IR-Assembler aussieht.

int f(int a, int b) { return a + 2*b; } int main() { return f(10, 20); } 

Wir verwenden Clang und kompilieren den obigen C-Code in LLVM IR Assembler.

 define i32 @f(i32 %a, i32 %b) { ; <label>:0 %1 = mul i32 2, %b %2 = add i32 %a, %1 ret i32 %2 } define i32 @main() { ; <label>:0 %1 = call i32 @f(i32 10, i32 20) ret i32 %1 } 

Wenn wir uns den obigen LLVM-IR-Assembler-Code ansehen, können wir einige bemerkenswerte LLVM-IR-Funktionen feststellen, nämlich:

LLVM IR ist statisch typisiert (d. H. 32-Bit-Ganzzahlen werden vom Typ i32 geschnitten).

Lokale Variablen haben einen Gültigkeitsbereich innerhalb der Funktion (d. H.% 1 in main unterscheidet sich von% 1 in @f).

Unbenannte (temporäre Register) erhalten in jeder der Funktionen lokale Kennungen (z. B.% 1,% 2) in aufsteigender Reihenfolge. Jede Funktion kann eine unendliche Anzahl von Registern verwenden (nicht auf 32 Allzweckregister beschränkt). Globale Bezeichner (z. B. @f) und lokale Bezeichner (z. B.% a,% 1) werden durch ein Präfix (@ bzw.%) unterschieden.

Die meisten Befehle machen das, was Sie erwarten, also multipliziert mul, addiert Addition usw.

Kommentare beginnen mit, wie es in Assemblersprachen üblich ist.

LLMV IR Assembler Struktur

Der Inhalt der LLVM-IR-Assemblydatei ist ein Modul. Das Modul enthält übergeordnete Deklarationen wie globale Variablen und Funktionen.

Eine Funktionsdeklaration enthält keine Basisblöcke, eine Funktionsdefinition enthält einen oder mehrere Basisblöcke (d. H. Einen Funktionskörper).

Ein detaillierteres Beispiel des LLVM-IR-Moduls ist unten angegeben. einschließlich der Definition der globalen Variablen @foo und der Definition der @ f-Funktion, die drei Basisblöcke enthält (% entry,% block_1 und% block_2).

 ;  ,  32-  21 @foo = global i32 21 ; f  42,   cond ,  0    define i32 @f(i1 %cond) { ;       ,     ;      entry: ;     br    block_1,  %cond ; ,   block_2   . br i1 %cond, label %block_1, label %block_2 ;     ,    ,     block_1: %tmp = load i32, i32* @foo %result = mul i32 %tmp, 2 ret i32 %result ;     ,     ,     block_2: ret i32 0 } 

Basiseinheit

Eine Basiseinheit ist eine Folge von Befehlen, die keine Übergangsbefehle (Beendigungsbefehle) sind. Die Schlüsselidee der Basiseinheit ist, dass, wenn ein Befehl der Basiseinheit ausgeführt wird, alle anderen Befehle der Basiseinheit ausgeführt werden. Dies vereinfacht die Analyse des Ausführungsflusses.

Das Team

Ein Befehl, der kein Sprungbefehl ist, führt normalerweise Berechnungen oder Speicherzugriff durch (z. B. Hinzufügen, Laden), ändert jedoch nicht den Steuerungsfluss des Programms.

Kündigungsteam

Der Beendigungsbefehl befindet sich am Ende jeder Basiseinheit und bestimmt, wo der Übergang am Ende der Basiseinheit erfolgen soll. Beispielsweise gibt der Befehl zum Beenden von ret den Steuerungsfluss der aufrufenden Funktion zurück, und br führt den Übergang aus, bedingt oder bedingungslos.

SSA-Formular

Eine sehr wichtige Eigenschaft von LLVM IR ist, dass es in der SSA-Form (Static Single Assignment) geschrieben ist, was im Wesentlichen bedeutet, dass jedes Register nur einmal zugewiesen wird. Diese Eigenschaft vereinfacht die statische Analyse des Datenstroms.

Um Variablen zu verarbeiten, die im ursprünglichen Quellcode mehrmals zugewiesen wurden, wird der Befehl phi in LLVM IR verwendet. Der Befehl phi gibt im Wesentlichen einen einzelnen Wert aus einer Reihe von Eingabewerten zurück, je nachdem, auf welchem ​​Ausführungspfad dieser Befehl erreicht wurde. Jeder Eingabewert ist somit einem vorhergehenden Eingabeblock zugeordnet.

Betrachten Sie als Beispiel die folgende LLVM-IR-Funktion:

 define i32 @f(i32 %a) { ; <label>:0 switch i32 %a, label %default [ i32 42, label %case1 ] case1: %x.1 = mul i32 %a, 2 br label %ret default: %x.2 = mul i32 %a, 3 br label %ret ret: %x.0 = phi i32 [ %x.2, %default ], [ %x.1, %case1 ] ret i32 %x.0 } 

Der Befehl phi (manchmal auch als Phi-Knoten bezeichnet) im obigen Beispiel simuliert verschiedene Zuweisungen unter Verwendung einer Reihe möglicher Eingabewerte, einen für jeden möglichen Pfad im Ausführungsthread, was zu einer Variablenzuweisung führt. Beispielsweise lautet einer der entsprechenden Pfade im Datenstrom wie folgt:



Im Allgemeinen können bei der Entwicklung eines Compilers, der Quellcode in LLVM-IR konvertiert, alle lokalen Quellcodevariablen in SSA-Form konvertiert werden, mit Ausnahme der Variablen, für die ihre Adresse verwendet wird.

Um die Implementierung des LLVM-Frontends zu vereinfachen, wird empfohlen, lokale Variablen in der Ausgangssprache als im Speicher zugewiesene Variablen (unter Verwendung von Alloca) zu modellieren, Zuweisungen zu lokalen Variablen als Schreibvorgänge in den Speicher zu simulieren und eine lokale Variable als Lesevorgänge aus dem Speicher zu verwenden. Der Grund ist, dass es eine nicht triviale Aufgabe sein kann, die Ausgangssprache in SSA-Form direkt in LLVM IR zu übersetzen. Solange Speicherzugriffe bestimmten Mustern folgen, können wir uns auf den mem2reg-Optimierungsdurchlauf als Teil von LLVM verlassen, um im Speicher zugewiesene lokale Variablen in Register in SSA-Form umzuwandeln (ggf. unter Verwendung von Phi-Knoten).

LLVM IR-Bibliothek auf pure Go

Es gibt zwei Hauptbibliotheken für die Arbeit mit LLVM IR in Go:

https://godoc.org/llvm.org/llvm/bindings/go/llvm : offizielle LLVM-Bindungen für die Go-Sprache.
github.com/llir/llvm : Eine saubere Go-Bibliothek für die Interaktion mit LLVM IR.

Offizielle LLVM-Bindungen für die Go-Sprache verwenden Cgo, um Zugriff auf die umfangreichen und leistungsstarken APIs des LLVM-Compiler-Frameworks zu gewähren, während das llir / llvm-Projekt vollständig in Go geschrieben ist und LLVM-IR für die Interaktion mit dem LLVM-Framework verwendet.

Dieser Artikel konzentriert sich auf llir / llvm, kann jedoch verallgemeinert werden, um mit anderen Bibliotheken zu arbeiten.

Warum eine neue Bibliothek schreiben?

Die Hauptmotivation für die Entwicklung einer sauberen Go-Bibliothek für die Interaktion mit LLVM IR bestand darin, das Schreiben von Compilern und statischen Analysetools, die auf dem LLVM IR-Kompilierungsframework basieren, zu einer unterhaltsameren Aufgabe zu machen. Es wurde auch durch die Tatsache beeinflusst, dass die Kompilierungszeit eines Projekts, das auf offiziellen LLVM-Bindungen mit Go basiert, erheblich sein kann (dank @aykevl, dem Autor von TinyGo, ist es jetzt möglich, die Kompilierung aufgrund dynamischer Verknüpfung im Gegensatz zur Standardversion von LLVM 4 zu beschleunigen).


Eine weitere große Motivation war es, die Go-API von Grund auf neu zu entwickeln. Der Hauptunterschied zwischen den LLVM-Bindungs-APIs für Go und llir / llvm besteht darin, wie LLVM-Werte modelliert werden. In LLVM-Bindemitteln für Go werden LLVM-Werte als konkreter Strukturtyp modelliert, der im Wesentlichen alle möglichen Methoden für alle möglichen LLVM-Werte enthält. Meine persönlichen Erfahrungen mit dieser API legen nahe, dass es schwierig ist zu wissen, welche Teilmenge von Methoden einen bestimmten Wert aufrufen darf. Um beispielsweise einen Opcode für Anweisungen zu erhalten, rufen Sie die intuitive InstructionOpcode-Methode auf. Wenn Sie jedoch stattdessen die Opcode-Methode aufrufen, mit der der Opcode eines konstanten Ausdrucks abgerufen werden soll, wird ein Laufzeitfehler angezeigt: "Argument cast () vom inkompatiblen Typ!" (Umwandlung des Arguments in einen inkompatiblen Typ).

Die llir / llvm-Bibliothek wurde entwickelt, um Typen zur Kompilierungszeit zu überprüfen und sicherzustellen, dass sie mit dem Go-Typsystem korrekt verwendet werden. LLVM-Werte in llir / llvm werden als Schnittstellentypen modelliert. Dieser Ansatz stellt nur eine minimale Anzahl von Methoden zur Verfügung, die von allen Werten gemeinsam genutzt werden. Wenn Sie auf bestimmte Methoden oder Felder zugreifen möchten, verwenden Sie die Typumschaltung (wie im folgenden Beispiel gezeigt).

Anwendungsbeispiel

Schauen wir uns nun einige Beispiele für bestimmte Verwendungszwecke an. Lassen Sie uns eine Bibliothek haben, aber was sollen wir mit dem LLVM IR tun?

Zunächst möchten wir möglicherweise die LLVM-IR analysieren, die von einem anderen Tool wie Clang und dem Optimierer LLVM opt generiert wurde (siehe Beispieleingabe unten).

Zweitens möchten wir möglicherweise das LLVM-IR verarbeiten und eine eigene Analyse durchführen oder eigene Optimierungsdurchläufe durchführen oder einen Interpreter oder einen JIT-Compiler implementieren (siehe das folgende Analysebeispiel).

Drittens möchten wir möglicherweise eine LLVM-IR generieren, die als Eingabe für andere Instrumente dient. Dieser Ansatz kann gewählt werden, wenn wir ein Frontend für eine neue Programmiersprache entwickeln (siehe den folgenden Beispielausgabecode).

Beispiel-Eingabecode - LLVM-IR-Analyse

 //       LLVM IR,    //     package main import ( "fmt" "github.com/llir/llvm/asm" ) func main() { //    LLVM IR. m, err := asm.ParseFile("foo.ll") if err != nil { panic(err) } // ,    LLVM IR. // Print LLVM IR module. fmt.Println(m) } 

Analysebeispiel - Verarbeitung von LLVM IR

 //      LLVM IR     //  Graphviz DOT package main import ( "bytes" "fmt" "io/ioutil" "github.com/llir/llvm/asm" "github.com/llir/llvm/ir" ) func main() { //    LLVM IR. m, err := asm.ParseFile("foo.ll") if err != nil { panic(err) } //    . callgraph := genCallgraph(m) //      Graphviz DOT. if err := ioutil.WriteFile("callgraph.dot", callgraph, 0644); err != nil { panic(err) } } // genCallgraph      Graphviz DOT    LLVM IR func genCallgraph(m *ir.Module) []byte { buf := &bytes.Buffer{} buf.WriteString("digraph {\n") //      for _, f := range m.Funcs { //   caller := f.Ident() fmt.Fprintf(buf, "\t%q\n", caller) //       for _, block := range f.Blocks { //   ,       . for _, inst := range block.Insts { //  .   call. switch inst := inst.(type) { case *ir.InstCall: callee := inst.Callee.Ident() //        . fmt.Fprintf(buf, "\t%q -> %q\n", caller, callee) } } //     switch term := block.Term.(type) { case *ir.TermRet: //  - _ = term } } } buf.WriteString("}") return buf.Bytes() } 

Beispielausgabecode - LLVM-IR-Generierung

 //     LLVM IR,    C, //    . // // int abs(int x); // // int seed = 0; // // // ref: https://en.wikipedia.org/wiki/Linear_congruential_generator // // a = 0x15A4E35 // // c = 1 // int rand(void) { // seed = seed*0x15A4E35 + 1; // return abs(seed); // } package main import ( "fmt" "github.com/llir/llvm/ir" "github.com/llir/llvm/ir/constant" "github.com/llir/llvm/ir/types" ) func main() { //      i32 := types.I32 zero := constant.NewInt(i32, 0) a := constant.NewInt(i32, 0x15A4E35) //  PRNG. c := constant.NewInt(i32, 1) //  PRNG. //    LLVM IR. m := ir.NewModule() //         . // // int abs(int x); abs := m.NewFunc("abs", i32, ir.NewParam("x", i32)) //         . // // int seed = 0; seed := m.NewGlobalDef("seed", zero) //        . // // int rand(void) { ... } rand := m.NewFunc("rand", i32) //           `rand`. entry := rand.NewBlock("") //         . tmp1 := entry.NewLoad(seed) tmp2 := entry.NewMul(tmp1, a) tmp3 := entry.NewAdd(tmp2, c) entry.NewStore(tmp3, seed) tmp4 := entry.NewCall(abs, tmp3) entry.NewRet(tmp4) //   LLVM IR  . fmt.Println(m) } 

Fazit

Die Entwicklung und Implementierung von llir / llvm wurde von einer Community von Mitwirkenden durchgeführt und geleitet, die nicht nur Code geschrieben, sondern auch Diskussionen geführt, Programmiersitzungen gepaart, debuggt, profiliert und im Lernprozess neugierig gezeigt haben.

Einer der schwierigsten Teile des llir / llvm-Projekts war die Erstellung einer EBNF-Grammatik für LLVM-IR, die die gesamte LLVM-IR-Sprache bis zur Version LLVM 7.0 abdeckt. Die Schwierigkeit liegt hier nicht im Prozess selbst, sondern in der Tatsache, dass es keine offiziell veröffentlichte Grammatik gibt, die die gesamte Sprache abdeckt. Einige Open-Source-Communities haben versucht, eine formale Grammatik für den LLVM-Assembler zu definieren, aber sie decken, soweit wir wissen, nur Teilmengen der Sprache ab.

Grammatik LLVM IR ebnet den Weg für interessante Projekte. Beispielsweise kann die Generierung eines syntaktisch gültigen LLVM-IR-Assemblers für verschiedene Tools und Bibliotheken unter Verwendung von LLVM-IR verwendet werden. Ein ähnlicher Ansatz wird in GoSmith verwendet. Dies kann zur Kreuzvalidierung von in anderen Sprachen implementierten LLVM-Projekten sowie zur Überprüfung auf Schwachstellen und Implementierungsfehler verwendet werden.

Die Zukunft ist wunderbar, fröhliches Hacken!

Referenzen

1. Ein sehr gut geschriebenes Kapitel über LLVM, geschrieben von Chris Lattner, dem Autor des ersten LLVM-Projekts, im Buch „Architektur von Open Source-Anwendungen“.

2. Das Tutorial Implementieren einer Sprache mit LLVM - oft auch als Kaleidoscope Language Guide bezeichnet - beschreibt ausführlich, wie eine einfache Programmiersprache implementiert wird, die in LLVM IR kompiliert wurde. Der Artikel beschreibt alle Hauptphasen des Schreibens eines Frontends, einschließlich eines lexikalischen Analysators, eines Parsers und der Codegenerierung.

3. Für diejenigen, die einen Compiler aus der Eingabesprache in LLVM IR schreiben möchten, wird das Buch " Mapping High Level Constructs to LLVM IR " empfohlen.

Ein guter Satz von Folien ist LLVM, das ausführlich die wichtigen Konzepte von LLVM IR beschreibt, eine Einführung in die LLVM C ++ - API bietet und einige sehr nützliche Passagen zur LLVM-Optimierung beschreibt.

Offizielle Go-Bindungen für LLVM eignen sich für viele Projekte. Sie repräsentieren die LLVM C-API, sind leistungsstark und stabil.

Eine gute Ergänzung zum Beitrag ist eine Einführung in LLVM in Go.