Устройство компилятора Swift. Часть 4


    Это последняя часть моего обзора компилятора Swift. Я покажу, как можно осуществить генерацию LLVM IR из AST и что выдаёт настоящий фронтенд. Если вы не читали предыдущие части, то переходите по ссылкам:



    LLVM IR Gen


    Для фронтенда — это завершающий шаг. Генератор LLVM IR преобразует SIL в промежуточное представление LLVM. Оно передаётся в бекенд для дальнейшей оптимизации и генерации машинного кода.


    Пример реализации


    Для того, чтобы сгенерировать промежуточное представление, нужно взаимодействовать с библиотекой LLVM. Она написана на С++, но так как из Swift его не вызвать, придётся использовать С-интерфейс. Но к С-библиотеке просто так не обратиться.


    Её нужно обернуть в модуль. Сделать это несложно. Вот тут есть хорошая инструкция. Для LLVM уже существует такая обёртка в открытом доступе, поэтому проще взять её.


    На этом же аккаунте выложена Swift-обёртка над LLVM-C-библиотекой, но в данной статье она использоваться не будет.


    Для генерации промежуточного представления был создан соответствующий класс LLVMIRGen. В инициализаторе он принимает AST, созданное парсером:


    import cllvm
    
    class LLVMIRGen {
        private let ast: ASTNode
    
        init(ast: ASTNode) {
            self.ast = ast
        }

    Метод printTo(_, dump) запускает генерацию и сохраняет её в читаемом виде в файл. Параметр dump используется для опционального вывода этой же информации в консоль:


    func printTo(_ fileName: String, dump: Bool) {

    Сначала нужно создать модуль. Его создание, как и создание других сущностей, вынесены в отдельные методы и будут рассмотрены ниже. Так как это С, то управлять памятью нужно вручную. Для удаления модуля из памяти используется функция LLVMDisposeModule():


    let module = generateModule()
    defer {
        LLVMDisposeModule(module)
    }

    Названия всех функций и типов LLVM начинаются с соответствующего префикса. Например, указатель на модуль имеет тип LLVMModuleRef, а на билдер — LLVMBuilderRef. Билдер — вспомогательный класс (ведь под неудобным С-интерфейсом скрываются обычные классы и методы), который помогает генерировать IR:


    let builder = generateBuilder()
    defer {
        LLVMDisposeBuilder(builder)
    }

    Вывод числа из скобок в консоль будет осуществляться с помощью стандартной функции puts. Для того, чтобы к ней обратиться, нужно её объявить. Это происходит в методе generateExternalPutsFunction. В него передаётся модуль потому, что объявление нужно добавить к нему. Константа putsFunction будет хранить указатель на функцию, чтобы к ней можно было обратиться:


    let putsFunction = generateExternalPutsFunction(module: module)

    Компилятор Swift создал функцию main на этапе SIL. Так как у компилятора фигурных скобок нет такого промежуточного представления, функция будет генерироваться сразу в LLVM IR.


    Для этого используется метод generateMainFunction(builder, module, mainInternalGenerator). Вызова функции main не будет. Поэтому и указатель на неё сохранять не нужно:


    generateMainFunction(builder: builder, module: module) {
        // ...
    }

    Последний параметр метода — замыкание, внутри которого происходит преобразование AST в соответствующий LLVM IR. Для этого создан отдельный метод handleAST(_, putsFunction, builder):


    generateMainFunction(builder: builder, module: module) {
        handleAST(ast, putsFunction: putsFunction, builder: builder)
    }

    В конце метода осуществляется вывод полученного промежуточного представления в консоль и сохранение его же в файл:


    if dump {
        LLVMDumpModule(module)
    }
    
    LLVMPrintModuleToFile(module, fileName, nil)

    Теперь подробнее о методах. Модуль генерируется вызовом функции LLVMModuleCreateWithName() с нужным названием:


    private func generateModule() -> LLVMModuleRef {
        let moduleName = "BraceCompiller"
        return LLVMModuleCreateWithName(moduleName)
    }

    Билдер создается ещё проще. Ему вообще не нужны параметры:


    private func generateBuilder() -> LLVMBuilderRef {
        return LLVMCreateBuilder()
    }

    Для объявления функции сначала нужно выделить память для ее параметра и сохранить в неё указатель на Int8. Далее — вызвать LLVMFunctionType() для создания типа функции, передав в него тип возвращаемого значения, массив типов аргументов (С-массив — указатель на соответствующую последовательность значений) и их количество. LLVMAddFunction() добавляет функцию puts в модуль и возвращает на неё указатель:


    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 создаётся похожим образом, но в неё добавляется тело. Как и в SIL, оно состоит из базовых блоков. Для этого нужно вызвать метод LLVMAppendBasicBlock(), передав в него функцию и название блока.


    Теперь в дело вступает билдер. Вызовом LLVMPositionBuilderAtEnd() он перемещается в конец пока ещё пустого, блока, а внутри замыкания mainInternalGenerator() с его помощью будет добавлено тело функции.


    В конце метода осуществляется возврат из main константного значения 0. Это последняя инструкция в этой функции:


    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)
    }

    Генерация IR по AST в компиляторе скобок очень проста, так как единственное действие, которое можно сделать на этом "языке программирования" — вывод в консоль одного числа. Нужно пройти рекурсивно по всему дереву, и при нахождении узла number добавить вызов функции puts. Если этого узла нет, функция main будет содержать только возврат нулевого значения:


    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)
        }
    }

    Генерация вызова puts осуществляется с помощью функции LLVMBuildCall(). В неё нужно передать билдер, указатель на функцию, аргументы и их количество. LLVMBuildGlobalStringPtr() создаёт глобальную константу для хранения строки. Она будет единственным аргументом:


    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")
    }

    Для запуска генерации LLVM IR нужно создать экземпляр класса LLVMIRGen и вызывать метод printTo(_, dump):


    let llvmIRGen = LLVMIRGen(ast: ast)
    llvmIRGen.printTo(outputFilePath, dump: false)

    Так как теперь компилятор скобок полностью готов можно его запустить и из командной строки. Для этого нужно его собрать (инструкция) и выполнить команду:


    build/debug/BraceCompiler Example/input.b Example/output.ll

    В результате получается вот такое промежуточное представление:


    ; 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
    }

    Использование генератора LLVM IR Swift


    LLVM IR тоже имеет SSA форму, но оно низкоуровневое и больше похоже на ассемблер. Описание инструкций можно найти в документации.


    Глобальные идентификаторы начинаются с символа b>@</b, локальные с %. В примере выше строка "5678\00" сохраняется в глобальную константу b>@print</b, а затем используется для вызова функции b>@puts</b c помощью инструкции call.


    Для того, чтобы увидеть что-нибудь интересное в LLVM IR, генерируемом компилятором Swift, нужно ещё немного усложнить код. Например, добавить сложение:


    let x = 16
    let y = x + 7

    За генерацию LLVM IR отвечает флаг -emit-ir:


    swiftc -emit-ir main.swift

    Результат выполнения команды:


    ; ModuleID = '-'
    source_filename = "-"
    target datalayout = "e-m: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}

    Промежуточное представление реального компилятора немного сложнее. В нём присутствуют дополнительные операции, но нужные инструкции найти не сложно. Тут объявляются глобальные константы x и y с искажёнными именами:


    @"$S4main1xSivp" = hidden global %TSi zeroinitializer, align 8
    @"$S4main1ySivp" = hidden global %TSi zeroinitializer, align 8

    Тут начинается определение функции main:


    define i32 @main(i32, i8**) #0 {

    Сначала в нём в константу x сохраняется значение 16:


    store i64 16, i64* getelementptr inbounds (%TSi, %TSi* @"$S4main1xSivp", i32 0, i32 0), align 8

    Затем оно загружается в регистр 3 и используется для вызова сложения вместе с литералом 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)

    Сложение с проверкой на переполнение возвращает структуру. Первым её значением является результат сложения, а вторым — флаг, который показывает, было ли переполнение.


    Структура в LLVM больше похожа на кортеж в Swift. У неё нет имен для полей, а получать значение нужно с помощью инструкции extractvalue. Первый её параметр указывает на типы полей в структуре, второй — сама структура, а после запятой — индекс поля, значение которого нужно вытащить:


    %5 = extractvalue { i64, i1 } %4, 0
    %6 = extractvalue { i64, i1 } %4, 1

    Теперь в шестом регистре хранится признак переполнения. Это значение проверяется с помощью инструкции ветвления. Если переполнение было, произойдёт переход в блок label8, если нет — в label7:


    br i1 %6, label %8, label %7

    В первом из них выполнение программы прерывается вызовом trap(). Во втором — результат сложения сохраняется в константу y, и из функции main возвращается 0:


    ; <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

    Генерация ассемблерного кода


    Компилятор Swift может отобразить и ассемблерный код. Для этого нужно передать флаг -emit-assembly:


    swiftc -emit-assembly main.swift

    Результат выполнения команды:


        .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

    Поняв код промежуточного представления, описанного выше, можно найти и ассемблерные инструкции, которые он генерирует. Вот сохранение 16 в константу и её загрузка в регистр %rax:


    movq    $16, _$S4main1xSivp(%rip)
    movq    _$S4main1xSivp(%rip), %rax

    Вот сложение 7 и значения константы. Результат сложения помещается в регистр %rax:


    addq    $7, %rax

    А так выглядит загрузка результата в константу y:


    movq    %rax, -24(%rbp)
    movq    -24(%rbp), %rcx
    movq    %rcx, _$S4main1ySivp(%rip)

    Исходный код:



    Заключение


    Swift — хорошо структурированный компилятор, и разобраться в его общей архитектуре оказалось не сложно. Также меня удивило то, что используя LLVM, можно легко написать свой собственный язык программирования. Конечно, компилятор скобок совсем примитивный, но в реализации Kaleidoscope тоже реально разобраться. Рекомендую прочитать хотя бы первые три главы из туториала.


    Спасибо всем кто прочитал. Я продолжу изучение компилятора Swift и, возможно, напишу о том, что из этого вышло. Какие темы, связанные с ним, были бы вам интересны?


    Полезные ссылки:


    • +29
    • 2,3k
    • 1
    e-Legion
    108,00
    Лидер мобильной разработки в России
    Поделиться публикацией

    Похожие публикации

    Комментарии 1

      +2
      Спасибо за серию статей! Чуть не упустил её, но поймал на финальной части. :)

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое