СофтХабрахабр

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

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

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

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

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

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

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

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

import cllvm class LLVMIRGen

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

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

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

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

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

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

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

let putsFunction = generateExternalPutsFunction(module: module)

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

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

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

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

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

Далее — вызвать LLVMFunctionType() для создания типа функции, передав в него тип возвращаемого значения, массив типов аргументов (С-массив — указатель на соответствующую последовательность значений) и их количество. Для объявления функции сначала нужно выделить память для ее параметра и сохранить в неё указатель на Int8. 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)
}

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

Нужно пройти рекурсивно по всему дереву, и при нахождении узла number добавить вызов функции puts. Генерация IR по AST в компиляторе скобок очень проста, так как единственное действие, которое можно сделать на этом "языке программирования" — вывод в консоль одного числа. Если этого узла нет, функция 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 форму, но оно низкоуровневое и больше похоже на ассемблер.

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

Например, добавить сложение: Для того, чтобы увидеть что-нибудь интересное в 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)

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

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

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

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

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

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

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

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

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

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

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

addq $7, %rax

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

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

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

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

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

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть