На днях на Cocoa-Heads в Санкт-Петербурге рассказал про устройство компилятора LLVM и Swift Intermediate Language. Под катом текстовый вариант доклада.
Исторический ликбез
Проект LLVM появился относительно недавно — в 2003 году. До этого он в течении трёх лет разрабатывался в стенах Иллинойского университета как научный проект Криса Латтнера. Позднее, как мы знаем, в 2005 году работа над LLVM продолжилась уже в Apple.
Изначально проект LLVM назывался Low Level Virtual Machine. И так как данное название сбивало с толку, намекая на то, что в руках находится виртуальная машина, в будущем LLVM перестал считаться акронимом — сейчас это полное название компилятора. У нас есть обобщенная система команд, прослойка абстракции от конечной архитектуры, но LLVM не навязывает нам ни Runtime, ни правил работы. Это не более, чем система команд, которая может использоваться для достижения своих целей.
Архитектура LLVM
Первое, что стоит знать об LLVM — это компилятор с модульной архитектурой. Он состоит из трех модулей, у каждого из которых есть своя четкая зона ответственности:
- Front End;
- Middle End (Optimizer);
- Back End.
Связующим звеном между модулями является промежуточный язык представления (Intermediate Representation — IR).
- задачей front end’а является преобразование языка высокого уровня (например, Swift’а) в IR;
- middle end ответственен за оптимизацию этого промежуточного представления;
- back end преобразует это представление в машинный код под конкретную архитектуру.
Для преобразования кода в некоторое промежуточное представление, также выполняется цепочка некоторых преобразований, в ходе которых код представляется в трех разных представлениях.
На вход компилятору поступает код, написанный на языке высокого уровня. В данном случае это будет Swift.
Первый этап называется Parsing. Парсер ответственен за генерацию абстрактного синтаксического дерева — AST (Abstract Syntax Tree) без какой-либо семантической информации о типах.
Затем наступает очередь семантического анализа (Semantic analysis). В результате чего формируется уже семантически корректное типизированное синтаксическое дерево. На этом этапе определяется наличие семантических ошибок.
На следующем шаге происходит импорт кода, написанного на Objective-C и C, в Swift’овое представление. За это отвечает ClangImporter.
И на последнем этапе происходит генерация Swift Intermediate Language в его первой форме представления.
Первая форма SIL поступает на вход оптимизатору. Который выполняет анализ, оптимизацию и трансформацию этой формы в каноническую.
Сначала на шаге трансформации выполняется диагностика потока данных и гарантированные преобразования, повышающие производительность программы (определяется использование неинициализированных переменных, проверяется достижимость всех узлов графа потока данных).
Дальше SILOptimizer выполняет высокоуровневые доменно-специфичные оптимизации для базовых типов контейнеров. Также он ответственен за девиртуализацию функций, оптимизацию ARC и спецификацию дженериков.
После этого уже генерируется промежуточное представление LLVM, которое поступает на вход Back-end’у.
Почему-то многие, когда говорят о back-end’е LLVM, имеют ввиду сам LLVM. Хотя на деле этим back-end’ом является LLC (LLVM Static Compiler).
LLC выполняет уже специфичные для конкретных архитектур оптимизации — использование меньшего места на диске, повышение скорости работы, понижение энергозатрат. Также он генерирует машинный код под конкретную архитектуру (x86, ARM, MIPS, и т.д.). Собирает объектные файлы в конечное приложение, библиотеку или фрэймворк.
Как и любая модульность, такое устройство компилятора позволяет независимо от конкретной архитектуры разрабатывать новый язык программирования, сконцентрировавшись на более высокоуровневых оптимизациях и анализе.
Swift Intermediate Language
Swift Intermediate Language — это приватное для компилятора Swift промежуточное представление, которое находится на более низком уровне абстракции, чем AST, но всё ещё выше промежуточного представления LLVM. Для своего представления SIL использует нотацию SSA.
SSA
Это аббревиатура от трех слов — Static Single Assignment — позволяет выражать код программы в виде графа. В ней отсутствуют переменные в привычном нам понимании. И все значения присваиваются лишь единожды.
Для компилятора ”распарсить” кусок кода, изображенного на правой части картинки — не столь тривиальная задача, как для человека. Чтобы её решить, должен быть проведен анализ достигающих определений — компилятор должен решить, какое конкретное значение X достигнет Y в этой конкретной точке программы. Не стоит забывать также про циклы, ветвления и breakpoint’ы. Это безусловно накладывает свои отпечатки на сложность данной задачи.
SSA предоставляет удобный механизм представления кода в виде независимых от значений переменных. Таким образом кусок кода, изображенный слева в нотации SSA будет представлен кодом справа. В нём уже нет значений X и Y, а есть значения X1, X2 и Y1.
SIL представляется двумя инвариантами.
Первый — Raw SIL — данная форма получается на этапе SILGen, она не оптимизирована и не продиагностирована. Raw SIL может содержать в себе ошибки потоков данных, некоторые инструкции могут находиться в неканонических представлениях. Данный формат не должен быть использован для генерации или распространения нативного кода. Для того, чтобы посмотреть, как выглядит эта форма, нужно запустить компилятор в режиме -emit-silgen.
Вторая форма — Canonical SIL — форма, получаемая из Raw SIL после диагностики и оптимизации. В ней уже устранены все ошибки потоков данных, и инструкции приведены к каноническим представлениям. Только эту форму можно использовать для генерации промежуточного представления LLVM или распространения. Эту форму можно увидеть, запустив компилятор в режиме -emit-sil.
SIL используется для анализа потока данных, который обеспечивает выполнение требования самого языка Swift, таких как, например, окончательная инициализация переменных и конструкторов, достижимость различных участков кода, покрытие всех условий switch’а.
Также благодаря SIL осуществляются более высокоуровневые оптимизации: retain/release оптимизация, девиртуализация динамических функций, closure inlining, создание и спецификация generic-функций.
Пример инструкций
Самое время познакомиться с базовыми инструкциями. В качестве примера возьмём простую функцию, проверяющую, является ли число положительным: на вход принимает один целочисленный аргумент, внутри имеет одно ветвление и возвращает логическое значение.
На уровне Swift Intermediate Language это превратится в следующий вид:
Давайте разбираться по частям.
В начале идёт определение формы SIL. Видим, что имеем дело с каноническим видом. Дальше идёт импорт необходимых модулей и объявление самой функции. Ключевое слово hidden говорит о том, что данная функция будет видна только объектам того Swift-модуля, в котором объявлена функция.
Все, наверняка, видели вот такое странное представление названий функций, классов, структур. Такое представление называется мангилированным. По сути, служит для того, чтобы добиться уникальности этих названий в рамках одной программы. Процесс получения человекочитаемого варианта называется демангилированием: на вход передаётся такое представление, и возвращается привычный вариант.
Basic Block (базовый блок bb) — тело функции состоит из одного или нескольких базовых блоков, которые соответствуют узлам графа потока управления данной функции. В SIL базовые блоки могут принимать аргументы, которые являются альтернативой фи-узлов LLVM.
В начале блока объявляется метатип значения. Метатип бывает трёх видов:
- @thin — означает что работаем с value type;
- @thick — перед нами reference type;
- @objc — означает, что хранится ссылка на класс использующего представление Objective-C.
Дальше объявляется целочисленный литерал, тип которого — 64-битный Int, а значение 0 — integer_literal. И создаётся экземпляр структуры Int с помощью инструкции struct.
Инструкция function_ref создаёт ссылку на SIL-функцию, управление которой передаётся с помощью инструкции apply. Напоминаю, что перед нами мангилированное представление. За ним скрывается функция сравнения:
static Swift.Int.> infix(Swift.Int, Swift.Int) -> Swift.Bool
Инструкция struct_extract «извлекает» значение, полученное в результате выполнения операции сравнения.
С последней инструкцией совсем всё просто: cond_br — ветвление по условию: если некоторое значение %7 == 1, то управление передаётся в блок bb1, если 0 — то в блок bb2.
Управление передаётся в один из первых двух блоков. Внутри которых находятся уже известные нам инструкции. В конце каждый блок передаёт управление базовому блоку bb3, который возвращает переданное в него значение.
Применимость Swift Intermediate Language
В первую очередь SIL можно использовать для создания различных инструментариев:
- для анализа покрытия кода;
- для работы с мутационными тестами.
Также форму SIL теоретически можно использовать для распределенной сборки проектов — парсинг, анализ и оптимизация на локальной машине, а генерация машинного кода и линковка объектных файлов — на удаленной.
Самое интересное — форма SIL используется для в проекте Swift for TensorFlow. Благодаря ей работает механизм Graph Program Extraction, который позволяет строить вычисления на графах на достаточно высоком уровне абстракции, и не задумываться о многих низко-уровневых представлениях.
Если тебе, дорогой читатель, материал был интересен, похлопай и подпишись🙂 А если нет — “набрасывай” в комментариях, почему не понравилось🙃
