Dies ist der letzte Teil meiner Überprüfung des Swift-Compilers. Ich werde Ihnen zeigen, wie Sie LLVM-IR aus AST generieren und was ein echtes Frontend ist. Wenn Sie die vorherigen Teile nicht gelesen haben, folgen Sie den Links:
LLVM IR Gen.
Für das Frontend ist dies der letzte Schritt. Der LLVM-IR-Generator wandelt das SIL in eine LLVM-Zwischendarstellung um. Es wird zur weiteren Optimierung und Generierung von Maschinencode an das Backend übergeben.
Implementierungsbeispiel
Um eine Zwischenansicht zu generieren, müssen Sie mit der LLVM-Bibliothek interagieren. Es ist in C ++ geschrieben, aber da Sie es nicht von Swift aus aufrufen können, müssen Sie die C-Schnittstelle verwenden. Sie können sich jedoch nicht einfach an die C-Bibliothek wenden.
Es muss in ein Modul eingeschlossen werden. Mach es einfach. Hier ist eine gute Anleitung. Für LLVM ist ein solcher Wrapper bereits gemeinfrei, sodass es einfacher ist, ihn zu verwenden.
Der Swift-Wrapper über die LLVM-C-Bibliothek wird auf demselben Konto veröffentlicht, wird jedoch in diesem Artikel nicht verwendet.
Um eine Zwischenansicht zu generieren, wurde die entsprechende LLVMIRGen- Klasse erstellt. Im Initialisierer wird der vom Parser erstellte AST verwendet:
import cllvm class LLVMIRGen { private let ast: ASTNode init(ast: ASTNode) { self.ast = ast }
Die printTo (_, dump) -Methode startet die Generierung und speichert sie in lesbarer Form in einer Datei. Der Parameter dump wird verwendet, um optional dieselben Informationen an die Konsole auszugeben:
func printTo(_ fileName: String, dump: Bool) {
Zuerst müssen Sie ein Modul erstellen. Die Erstellung sowie die Erstellung anderer Entitäten werden in separate Methoden unterteilt und im Folgenden erörtert. Da dies C ist, müssen Sie den Speicher manuell verwalten. Verwenden Sie die Funktion LLVMDisposeModule (), um ein Modul aus dem Speicher zu entfernen:
let module = generateModule() defer { LLVMDisposeModule(module) }
Die Namen aller LLVM-Funktionen und -Typen beginnen mit dem entsprechenden Präfix. Beispielsweise ist ein Zeiger auf ein Modul vom Typ LLVMModuleRef und auf einen Builder vom Typ LLVMBuilderRef . Der Builder ist eine Hilfsklasse (schließlich sind unter der unbequemen C-Schnittstelle gewöhnliche Klassen und Methoden verborgen), mit deren Hilfe IR generiert werden kann:
let builder = generateBuilder() defer { LLVMDisposeBuilder(builder) }
Die Ausgabe der Nummer aus Klammern an die Konsole erfolgt mit der Standard- Puts- Funktion. Um sie zu kontaktieren, müssen Sie es deklarieren. Dies geschieht in der generateExternalPutsFunction- Methode. Das Modul wird an es übergeben, da die Deklaration hinzugefügt werden muss. Die Konstante putFunction speichert einen Zeiger auf eine Funktion, auf die zugegriffen werden kann:
let putsFunction = generateExternalPutsFunction(module: module)
Der Swift-Compiler hat die Hauptfunktion in der SIL-Phase erstellt. Da der Klammer-Compiler keine solche Zwischendarstellung hat, wird die Funktion sofort in LLVM IR generiert.
Verwenden Sie dazu die generateMainFunction- Methode (Builder, Modul, mainInternalGenerator) . Die Hauptfunktion wird nicht aufgerufen. Daher müssen Sie keinen Zeiger darauf speichern:
generateMainFunction(builder: builder, module: module) { // ... }
Der letzte Parameter der Methode ist der Abschluss, in dem der AST in den entsprechenden LLVM-IR konvertiert wird. Zu diesem Zweck wurde eine separate Methode handleAST (_, putFunction, builder) erstellt :
generateMainFunction(builder: builder, module: module) { handleAST(ast, putsFunction: putsFunction, builder: builder) }
Am Ende der Methode wird die resultierende Zwischendarstellung an die Konsole ausgegeben und in der Datei gespeichert:
if dump { LLVMDumpModule(module) } LLVMPrintModuleToFile(module, fileName, nil)
Nun mehr zu den Methoden. Das Modul wird durch Aufrufen der Funktion LLVMModuleCreateWithName () mit dem gewünschten Namen generiert:
private func generateModule() -> LLVMModuleRef { let moduleName = "BraceCompiller" return LLVMModuleCreateWithName(moduleName) }
Der Builder wird noch einfacher erstellt. Er braucht überhaupt keine Parameter:
private func generateBuilder() -> LLVMBuilderRef { return LLVMCreateBuilder() }
Um eine Funktion zu deklarieren, müssen Sie zuerst Speicher für ihren Parameter zuweisen und einen Zeiger auf Int8 darin speichern. Rufen Sie als Nächstes LLVMFunctionType () auf, um den Typ der Funktion zu erstellen, und übergeben Sie ihm den Typ des Rückgabewerts, ein Array von Argumenttypen (C-Array ist ein Zeiger auf die entsprechende Folge von Werten) und deren Nummer. LLVMAddFunction () fügt dem Modul die Funktion put hinzu und gibt einen Zeiger darauf zurück:
private func generateExternalPutsFunction(module: LLVMModuleRef) -> LLVMValueRef { var putParamTypes = UnsafeMutablePointer<LLVMTypeRef?>.allocate(capacity: 1) defer { putParamTypes.deallocate() } putParamTypes[0] = LLVMPointerType(LLVMInt8Type(), 0) let putFunctionType = LLVMFunctionType(LLVMInt32Type(), putParamTypes, 1, 0) return LLVMAddFunction(module, "puts", putFunctionType) }
main wird auf ähnliche Weise erstellt, aber ein Körper wird hinzugefügt. Wie SIL besteht es aus Basisblöcken. Rufen Sie dazu die Methode LLVMAppendBasicBlock () auf und übergeben Sie die Funktion und den Namen des Blocks.
Jetzt kommt der Erbauer ins Spiel. Durch Aufrufen von LLVMPositionBuilderAtEnd () wird an das Ende des noch leeren Blocks verschoben , und innerhalb des Abschlusses mainInternalGenerator () wird der Funktionskörper hinzugefügt.
Am Ende der Methode wird der konstante Wert 0 von main zurückgegeben . Dies ist die letzte Anweisung in dieser Funktion:
private func generateMainFunction(builder: LLVMBuilderRef, module: LLVMModuleRef, mainInternalGenerator: () -> Void) { let mainFunctionType = LLVMFunctionType(LLVMInt32Type(), nil, 0, 0) let mainFunction = LLVMAddFunction(module, "main", mainFunctionType) let mainEntryBlock = LLVMAppendBasicBlock(mainFunction, "entry") LLVMPositionBuilderAtEnd(builder, mainEntryBlock) mainInternalGenerator() let zero = LLVMConstInt(LLVMInt32Type(), 0, 0) LLVMBuildRet(builder, zero) }
Das Generieren von IR gemäß AST im Klammer-Compiler ist sehr einfach, da die einzige Aktion, die in dieser "Programmiersprache" ausgeführt werden kann, darin besteht, eine einzelne Nummer an die Konsole auszugeben. Sie müssen den gesamten Baum rekursiv durchlaufen. Wenn Sie den Nummernknoten gefunden haben , fügen Sie der Puts- Funktion einen Aufruf hinzu. Wenn dieser Knoten nicht vorhanden ist, enthält die Hauptfunktion nur eine Rückgabe mit dem Wert Null:
private func handleAST(_ ast: ASTNode, putsFunction: LLVMValueRef, builder: LLVMBuilderRef) { switch ast { case let .brace(childNode): guard let childNode = childNode else { break } handleAST(childNode, putsFunction: putsFunction, builder: builder) case let .number(value): generatePrint(value: value, putsFunction: putsFunction, builder: builder) } }
Der Puts- Aufruf wird mit der Funktion LLVMBuildCall () generiert . Es muss einen Builder, einen Zeiger auf eine Funktion, Argumente und deren Nummer übergeben. LLVMBuildGlobalStringPtr () erstellt eine globale Konstante für eine Zeichenfolge. Sie wird das einzige Argument sein:
private func generatePrint(value: Int, putsFunction: LLVMValueRef, builder: LLVMBuilderRef) { let putArgumentsSize = MemoryLayout<LLVMValueRef?>.size let putArguments = UnsafeMutablePointer<LLVMValueRef?>.allocate(capacity: 1) defer { putArguments.deallocate() } putArguments[0] = LLVMBuildGlobalStringPtr(builder, "\(value)", "print") _ = LLVMBuildCall(builder, putsFunction, putArguments, 1, "put") }
Um die LLVM-IR-Generierung zu starten, müssen Sie eine Instanz der LLVMIRGen- Klasse erstellen und die printTo (_, dump) -Methode aufrufen:
let llvmIRGen = LLVMIRGen(ast: ast) llvmIRGen.printTo(outputFilePath, dump: false)
Da der Klammer-Compiler jetzt vollständig bereit ist, können Sie ihn über die Befehlszeile starten. Dazu müssen Sie es sammeln ( Anweisung ) und den Befehl ausführen:
build/debug/BraceCompiler Example/input.b Example/output.ll
Das Ergebnis ist diese Zwischendarstellung:
; ModuleID = 'BraceCompiller' source_filename = "BraceCompiller" @print = private unnamed_addr constant [5 x i8] c"5678\00" declare i32 @puts(i8*) define i32 @main() { entry: %put = call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @print, i32 0, i32 0)) ret i32 0 }
Verwenden des LLVM IR Swift Generator
LLVM IR hat auch eine SSA-Form, ist jedoch auf niedriger Ebene und ähnelt eher einem Assembler. Eine Beschreibung der Anleitung finden Sie in der Dokumentation .
Globale Bezeichner beginnen mit b> @ </ b , lokal mit % . Im obigen Beispiel wird die Zeichenfolge "5678 \ 00" in der globalen Konstante b> @print </ b gespeichert und dann zum Aufrufen der Funktion b> @puts </ b mithilfe der call- Anweisung verwendet.
Um etwas Interessantes in der vom Swift-Compiler generierten LLVM-IR zu sehen, müssen Sie den Code etwas komplizierter machen. Fügen Sie beispielsweise einen Zusatz hinzu:
let x = 16 let y = x + 7
Das Flag -emit-ir ist für die Erzeugung von LLVM-IR verantwortlich:
swiftc -emit-ir main.swift
Das Ergebnis des Befehls:
; ModuleID = '-' source_filename = "-" target datalayout = "em:o-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-apple-macosx10.14.0" %TSi = type <{ i64 }> @"$S4main1xSivp" = hidden global %TSi zeroinitializer, align 8 @"$S4main1ySivp" = hidden global %TSi zeroinitializer, align 8 @__swift_reflection_version = linkonce_odr hidden constant i16 3 @llvm.used = appending global [1 x i8*] [i8* bitcast (i16* @__swift_reflection_version to i8*)], section "llvm.metadata", align 8 define i32 @main(i32, i8**) #0 { entry: %2 = bitcast i8** %1 to i8* store i64 16, i64* getelementptr inbounds (%TSi, %TSi* @"$S4main1xSivp", i32 0, i32 0), align 8 %3 = load i64, i64* getelementptr inbounds (%TSi, %TSi* @"$S4main1xSivp", i32 0, i32 0), align 8 %4 = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 %3, i64 7) %5 = extractvalue { i64, i1 } %4, 0 %6 = extractvalue { i64, i1 } %4, 1 br i1 %6, label %8, label %7 ; <label>:7: ; preds = %entry store i64 %5, i64* getelementptr inbounds (%TSi, %TSi* @"$S4main1ySivp", i32 0, i32 0), align 8 ret i32 0 ; <label>:8: ; preds = %entry call void @llvm.trap() unreachable } ; Function Attrs: nounwind readnone speculatable declare { i64, i1 } @llvm.sadd.with.overflow.i64(i64, i64) #1 ; Function Attrs: noreturn nounwind declare void @llvm.trap() #2 attributes #0 = { "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" } attributes #1 = { nounwind readnone speculatable } attributes #2 = { noreturn nounwind } !llvm.module.flags = !{!0, !1, !2, !3, !4, !5, !6, !7} !llvm.linker.options = !{!8, !9, !10} !llvm.asan.globals = !{!11} !0 = !{i32 1, !"Objective-C Version", i32 2} !1 = !{i32 1, !"Objective-C Image Info Version", i32 0} !2 = !{i32 1, !"Objective-C Image Info Section", !"__DATA,__objc_imageinfo,regular,no_dead_strip"} !3 = !{i32 4, !"Objective-C Garbage Collection", i32 1536} !4 = !{i32 1, !"Objective-C Class Properties", i32 64} !5 = !{i32 1, !"wchar_size", i32 4} !6 = !{i32 7, !"PIC Level", i32 2} !7 = !{i32 1, !"Swift Version", i32 6} !8 = !{!"-lswiftSwiftOnoneSupport"} !9 = !{!"-lswiftCore"} !10 = !{!"-lobjc"} !11 = !{[1 x i8*]* @llvm.used, null, null, i1 false, i1 true}
Die Zwischendarstellung eines echten Compilers ist etwas komplizierter. Es gibt zusätzliche Operationen, aber die erforderlichen Anweisungen sind nicht schwer zu finden. Hier werden die globalen Konstanten x und y mit fehlerhaften Namen deklariert:
@"$S4main1xSivp" = hidden global %TSi zeroinitializer, align 8 @"$S4main1ySivp" = hidden global %TSi zeroinitializer, align 8
Hier beginnt die Definition der Hauptfunktion:
define i32 @main(i32, i8**) #0 {
Zunächst wird der Wert 16 in der Konstanten x gespeichert:
store i64 16, i64* getelementptr inbounds (%TSi, %TSi* @"$S4main1xSivp", i32 0, i32 0), align 8
Dann wird es in Register 3 geladen und verwendet, um Addition zusammen mit Literal 7 aufzurufen:
%3 = load i64, i64* getelementptr inbounds (%TSi, %TSi* @"$S4main1xSivp", i32 0, i32 0), align 8 %4 = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 %3, i64 7)
Durch Hinzufügen der Überlaufprüfung wird die Struktur zurückgegeben. Der erste Wert ist das Ergebnis der Addition, und der zweite Wert ist ein Flag, das angibt, ob ein Überlauf aufgetreten ist.
Die Struktur in LLVM ähnelt eher einem Tupel in Swift. Es gibt keine Namen für die Felder, und Sie müssen den Wert mithilfe der Anweisung extractvalue abrufen . Sein erster Parameter gibt die Feldtypen in der Struktur an, der zweite - die Struktur selbst und nach dem Komma - den Index des Feldes, dessen Wert herausgezogen werden muss:
%5 = extractvalue { i64, i1 } %4, 0 %6 = extractvalue { i64, i1 } %4, 1
Jetzt wird das Überlaufzeichen im sechsten Register gespeichert. Dieser Wert wird mit der Verzweigungsanweisung überprüft. Wenn es einen Überlauf gab, erfolgt ein Übergang zum label8- Block, wenn nicht, zu label7 :
br i1 %6, label %8, label %7
Im ersten Fall wird die Programmausführung durch einen Aufruf von trap () unterbrochen. In der zweiten wird das Ergebnis der Addition in der Konstanten y gespeichert und 0 wird von der Hauptfunktion zurückgegeben:
; <label>:7: ; preds = %entry store i64 %5, i64* getelementptr inbounds (%TSi, %TSi* @"$S4main1ySivp", i32 0, i32 0), align 8 ret i32 0 ; <label>:8: ; preds = %entry call void @llvm.trap() unreachable
Assembly-Code-Generierung
Der Swift-Compiler kann auch Assemblycode anzeigen. Übergeben Sie dazu das Flag -emit-Assembly :
swiftc -emit-assembly main.swift
Das Ergebnis des Befehls:
.section __TEXT,__text,regular,pure_instructions .build_version macos, 10, 14 .globl _main .p2align 4, 0x90 _main: .cfi_startproc pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset %rbp, -16 movq %rsp, %rbp .cfi_def_cfa_register %rbp movq $16, _$S4main1xSivp(%rip) movq _$S4main1xSivp(%rip), %rax addq $7, %rax seto %cl movl %edi, -4(%rbp) movq %rsi, -16(%rbp) movq %rax, -24(%rbp) movb %cl, -25(%rbp) jo LBB0_2 xorl %eax, %eax movq -24(%rbp), %rcx movq %rcx, _$S4main1ySivp(%rip) popq %rbp retq LBB0_2: ud2 .cfi_endproc .private_extern _$S4main1xSivp .globl _$S4main1xSivp .zerofill __DATA,__common,_$S4main1xSivp,8,3 .private_extern _$S4main1ySivp .globl _$S4main1ySivp .zerofill __DATA,__common,_$S4main1ySivp,8,3 .private_extern ___swift_reflection_version .section __TEXT,__const .globl ___swift_reflection_version .weak_definition ___swift_reflection_version .p2align 1 ___swift_reflection_version: .short 3 .no_dead_strip ___swift_reflection_version .linker_option "-lswiftSwiftOnoneSupport" .linker_option "-lswiftCore" .linker_option "-lobjc" .section __DATA,__objc_imageinfo,regular,no_dead_strip L_OBJC_IMAGE_INFO: .long 0 .long 1600 .subsections_via_symbols
Nachdem Sie den oben beschriebenen Code der Zwischendarstellung verstanden haben, finden Sie die Assembler-Anweisungen, die er generiert. Hier wird 16 in einer Konstanten gespeichert und in das % rax-Register geladen :
movq $16, _$S4main1xSivp(%rip) movq _$S4main1xSivp(%rip), %rax
Hier ist Addition 7 und der Wert der Konstante. Das Ergebnis der Addition wird in das % rax-Register eingetragen :
addq $7, %rax
Und so sieht das Laden des Ergebnisses in die Konstante y aus:
movq %rax, -24(%rbp) movq -24(%rbp), %rcx movq %rcx, _$S4main1ySivp(%rip)
Quellcode:
Fazit
Swift ist ein gut strukturierter Compiler, und es war nicht schwierig, seine allgemeine Architektur herauszufinden. Ich war auch überrascht, dass Sie mit LLVM problemlos Ihre eigene Programmiersprache schreiben können. Natürlich ist der Klammer-Compiler ziemlich primitiv, aber die Kaleidoskop-Implementierung ist auch wirklich real. Ich empfehle, mindestens die ersten drei Kapitel des Tutorials zu lesen.
Vielen Dank an alle, die gelesen haben. Ich werde den Swift-Compiler weiter studieren und vielleicht darüber schreiben, was daraus geworden ist. Welche Themen, die ihn betreffen, würden Sie interessieren?
Nützliche Links: