Esta es la última parte de mi revisión del compilador Swift. Le mostraré cómo generar LLVM IR a partir de AST y qué es un frontend real. Si no ha leído las partes anteriores, siga los enlaces:
LLVM IR Gen
Para la interfaz, este es el paso final. El generador IR LLVM convierte el SIL en una representación LLVM intermedia. Se pasa al backend para una mayor optimización y generación de código de máquina.
Ejemplo de implementación
Para generar una vista intermedia, debe interactuar con la biblioteca LLVM. Está escrito en C ++, pero como no puede llamarlo desde Swift, debe usar la interfaz C. Pero no puedes recurrir a la biblioteca C.
Necesita estar envuelto en un módulo. Hazlo fácil. Aquí hay una buena instrucción. Para LLVM, dicho contenedor ya existe en el dominio público, por lo que es más fácil tomarlo.
El contenedor Swift sobre la biblioteca LLVM-C se publica en la misma cuenta, pero no se utilizará en este artículo.
Para generar una vista intermedia, se creó la clase LLVMIRGen correspondiente. En el inicializador, toma el AST creado por el analizador:
import cllvm class LLVMIRGen { private let ast: ASTNode init(ast: ASTNode) { self.ast = ast }
El método printTo (_, dump) comienza la generación y la guarda en un formato legible en un archivo. El parámetro dump se usa para generar opcionalmente la misma información en la consola:
func printTo(_ fileName: String, dump: Bool) {
Primero necesitas crear un módulo. Su creación, así como la creación de otras entidades, se ponen en métodos separados y se discutirán a continuación. Como se trata de C, debe administrar la memoria manualmente. Para eliminar un módulo de la memoria, use la función LLVMDisposeModule () :
let module = generateModule() defer { LLVMDisposeModule(module) }
Los nombres de todas las funciones y tipos de LLVM comienzan con el prefijo correspondiente. Por ejemplo, un puntero a un módulo es del tipo LLVMModuleRef , y a un constructor es del tipo LLVMBuilderRef . El constructor es una clase auxiliar (después de todo, bajo la inconveniente interfaz C, las clases y los métodos normales están ocultos), lo que ayuda a generar IR:
let builder = generateBuilder() defer { LLVMDisposeBuilder(builder) }
La salida del número de paréntesis a la consola se realizará mediante la función de venta estándar. Para contactar con ella, debes declararlo. Esto sucede en el método generateExternalPutsFunction . El módulo se le pasa porque la declaración debe agregarse. La constante putFunction almacenará un puntero a una función para poder acceder a ella:
let putsFunction = generateExternalPutsFunction(module: module)
El compilador Swift creó la función principal en la etapa SIL. Como el compilador de llaves no tiene una representación intermedia de este tipo, la función se generará inmediatamente en LLVM IR.
Para hacer esto, use el método generateMainFunction (generador, módulo, mainInternalGenerator) . No se llamará a la función principal . Por lo tanto, no necesita guardar un puntero en él:
generateMainFunction(builder: builder, module: module) { // ... }
El último parámetro del método es el cierre, dentro del cual el AST se convierte al IR LLVM correspondiente. Para esto, se ha creado un método separado handleAST (_, putsFunction, builder) :
generateMainFunction(builder: builder, module: module) { handleAST(ast, putsFunction: putsFunction, builder: builder) }
Al final del método, la representación intermedia resultante se envía a la consola y se guarda en el archivo:
if dump { LLVMDumpModule(module) } LLVMPrintModuleToFile(module, fileName, nil)
Ahora más sobre los métodos. El módulo se genera llamando a la función LLVMModuleCreateWithName () con el nombre deseado:
private func generateModule() -> LLVMModuleRef { let moduleName = "BraceCompiller" return LLVMModuleCreateWithName(moduleName) }
El constructor se crea aún más fácil. No necesita parámetros en absoluto:
private func generateBuilder() -> LLVMBuilderRef { return LLVMCreateBuilder() }
Para declarar una función, primero debe asignar memoria para su parámetro y guardar un puntero en Int8. Luego, llame a LLVMFunctionType () para crear el tipo de la función, pasándole el tipo del valor de retorno, una matriz de tipos de argumentos (C-array es un puntero a la secuencia de valores correspondiente) y su número. LLVMAddFunction () agrega la función put al módulo y le devuelve un puntero:
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 se crea de manera similar, pero se le agrega un cuerpo. Al igual que SIL, consta de bloques base. Para hacer esto, llame al método LLVMAppendBasicBlock () , pasándole la función y el nombre del bloque.
Ahora el constructor entra en juego. Al llamar a LLVMPositionBuilderAtEnd (), se mueve al final del bloque aún vacío, y dentro del cierre mainInternalGenerator () , el cuerpo de la función se agregará con él.
Al final del método, el valor constante 0 se devuelve desde main . Esta es la última instrucción en esta función:
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) }
Generar IR de acuerdo con AST en el compilador de paréntesis es muy simple, ya que la única acción que se puede hacer en este "lenguaje de programación" es enviar un número único a la consola. Debe recorrer recursivamente todo el árbol y, cuando encuentre el nodo numérico , agregue una llamada a la función put . Si este nodo no está presente, la función principal contendrá solo un valor de retorno de cero:
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) } }
La llamada put se genera utilizando la función LLVMBuildCall () . Necesita pasar un constructor, un puntero a una función, argumentos y su número. LLVMBuildGlobalStringPtr () crea una constante global para contener una cadena. Ella será el único argumento:
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") }
Para iniciar la generación de LLVM IR, debe crear una instancia de la clase LLVMIRGen y llamar al método printTo (_, dump) :
let llvmIRGen = LLVMIRGen(ast: ast) llvmIRGen.printTo(outputFilePath, dump: false)
Como ahora el compilador de paréntesis está completamente listo, puede iniciarlo desde la línea de comandos. Para hacer esto, debe recopilarlo ( instrucciones ) y ejecutar el comando:
build/debug/BraceCompiler Example/input.b Example/output.ll
El resultado es esta representación intermedia:
; 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 }
Usando LLVM IR Swift Generator
LLVM IR también tiene una forma SSA, pero es de bajo nivel y se parece más al ensamblador. Puede encontrar una descripción de las instrucciones en la documentación .
Los identificadores globales comienzan con b> @ </ b , local con % . En el ejemplo anterior, la cadena "5678 \ 00" se almacena en la constante global b> @print </ b , y luego se usa para llamar a la función b> @puts </ b usando la instrucción de llamada .
Para ver algo interesante en el LLVM IR generado por el compilador Swift, debe complicar un poco más el código. Por ejemplo, agregue la suma:
let x = 16 let y = x + 7
El indicador -emit-ir es responsable de generar IR LLVM:
swiftc -emit-ir main.swift
El resultado del comando:
; 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}
La representación intermedia de un compilador real es un poco más complicada. Hay operaciones adicionales en él, pero las instrucciones necesarias no son difíciles de encontrar. Aquí las constantes globales x e y se declaran con nombres mal formados:
@"$S4main1xSivp" = hidden global %TSi zeroinitializer, align 8 @"$S4main1ySivp" = hidden global %TSi zeroinitializer, align 8
Aquí comienza la definición de la función principal :
define i32 @main(i32, i8**) #0 {
Primero, el valor 16 se almacena en la constante x :
store i64 16, i64* getelementptr inbounds (%TSi, %TSi* @"$S4main1xSivp", i32 0, i32 0), align 8
Luego se carga en el registro 3 y se usa para llamar a la suma junto con el literal 7:
%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)
La suma de verificación de desbordamiento devuelve la estructura. Su primer valor es el resultado de la suma, y el segundo es un indicador que indica si hubo un desbordamiento.
La estructura en LLVM es más como una tupla en Swift. No tiene nombres para los campos, y debe obtener el valor utilizando la instrucción extractvalue . Su primer parámetro indica los tipos de campos en la estructura, el segundo, la estructura misma, y después de la coma, el índice del campo, cuyo valor debe extraerse:
%5 = extractvalue { i64, i1 } %4, 0 %6 = extractvalue { i64, i1 } %4, 1
Ahora el signo de desbordamiento se almacena en el sexto registro. Este valor se verifica utilizando la instrucción de bifurcación. Si hubo un desbordamiento, habrá una transición al bloque label8 , si no, a label7 :
br i1 %6, label %8, label %7
En el primero de estos, la ejecución del programa es interrumpida por una llamada a trap () . En el segundo, el resultado de la suma se almacena en la constante y , y 0 se devuelve desde la función principal :
; <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
Generación de código de ensamblaje
El compilador Swift también puede mostrar el código de ensamblaje. Para hacer esto, pase el indicador -emit-assembly :
swiftc -emit-assembly main.swift
El resultado del comando:
.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
Habiendo entendido el código de la representación intermedia descrita anteriormente, puede encontrar las instrucciones de ensamblador que genera. Aquí se almacena 16 en una constante y se carga en el registro% rax :
movq $16, _$S4main1xSivp(%rip) movq _$S4main1xSivp(%rip), %rax
Aquí está la suma 7 y el valor de la constante. El resultado de la adición se coloca en el registro% rax :
addq $7, %rax
Y así es como se carga el resultado en constante y :
movq %rax, -24(%rbp) movq -24(%rbp), %rcx movq %rcx, _$S4main1ySivp(%rip)
Código fuente:
Conclusión
Swift es un compilador bien estructurado, y no fue difícil descifrar su arquitectura general. También me sorprendió que usando LLVM, puede escribir fácilmente su propio lenguaje de programación. Por supuesto, el compilador de paréntesis es muy primitivo, pero la implementación de Kaleidoscope también es realmente comprensible. Recomiendo leer al menos los primeros tres capítulos del tutorial.
Gracias a todos los que leyeron. Continuaré estudiando el compilador Swift y tal vez escriba sobre lo que salió de él. ¿Qué temas relacionados con él le interesarían?
Enlaces utiles: