Устройство компилятора Swift. Часть 415.02.2019 13:32
Это последняя часть моего обзора компилятора Swift. Я покажу, как можно осуществить генерацию LLVM IR из AST и что выдаёт настоящий фронтенд. Если вы не читали предыдущие части, то переходите по ссылкам:
Для фронтенда — это завершающий шаг. Генератор 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 не будет. Поэтому и указатель на неё сохранять не нужно:
Последний параметр метода — замыкание, внутри которого происходит преобразование AST в соответствующий LLVM IR. Для этого создан отдельный метод handleAST (_, putsFunction, builder):
Для объявления функции сначала нужно выделить память для ее параметра и сохранить в неё указатель на Int8. Далее — вызвать LLVMFunctionType () для создания типа функции, передав в него тип возвращаемого значения, массив типов аргументов (С-массив — указатель на соответствующую последовательность значений) и их количество. LLVMAddFunction () добавляет функцию puts в модуль и возвращает на неё указатель:
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 () создаёт глобальную константу для хранения строки. Она будет единственным аргументом:
Для запуска генерации LLVM IR нужно создать экземпляр класса LLVMIRGen и вызывать метод printTo (_, dump):
let llvmIRGen = LLVMIRGen(ast: ast)
llvmIRGen.printTo(outputFilePath, dump: false)
Так как теперь компилятор скобок полностью готов можно его запустить и из командной строки. Для этого нужно его собрать (инструкция) и выполнить команду:
LLVM IR тоже имеет SSA форму, но оно низкоуровневое и больше похоже на ассемблер. Описание инструкций можно найти в документации.
Глобальные идентификаторы начинаются с символа b>@%. В примере выше строка »5678\00» сохраняется в глобальную константу b>@print@putscall.
Для того, чтобы увидеть что-нибудь интересное в LLVM IR, генерируемом компилятором Swift, нужно ещё немного усложнить код. Например, добавить сложение:
Промежуточное представление реального компилятора немного сложнее. В нём присутствуют дополнительные операции, но нужные инструкции найти не сложно. Тут объявляются глобальные константы 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:
Сложение с проверкой на переполнение возвращает структуру. Первым её значением является результат сложения, а вторым — флаг, который показывает, было ли переполнение.
Структура в LLVM больше похожа на кортеж в Swift. У неё нет имен для полей, а получать значение нужно с помощью инструкции extractvalue. Первый её параметр указывает на типы полей в структуре, второй — сама структура, а после запятой — индекс поля, значение которого нужно вытащить:
Теперь в шестом регистре хранится признак переполнения. Это значение проверяется с помощью инструкции ветвления. Если переполнение было, произойдёт переход в блок label8, если нет — в label7:
br i1 %6, label %8, label %7
В первом из них выполнение программы прерывается вызовом trap (). Во втором — результат сложения сохраняется в константу y, и из функции main возвращается 0:
Поняв код промежуточного представления, описанного выше, можно найти и ассемблерные инструкции, которые он генерирует. Вот сохранение 16 в константу и её загрузка в регистр %rax:
Swift — хорошо структурированный компилятор, и разобраться в его общей архитектуре оказалось не сложно. Также меня удивило то, что используя LLVM, можно легко написать свой собственный язык программирования. Конечно, компилятор скобок совсем примитивный, но в реализации Kaleidoscope тоже реально разобраться. Рекомендую прочитать хотя бы первые три главы из туториала.
Спасибо всем кто прочитал. Я продолжу изучение компилятора Swift и, возможно, напишу о том, что из этого вышло. Какие темы, связанные с ним, были бы вам интересны?