Оглавление:
Часть 1: Введение и лексический анализ
Часть 2: Реализация парсера и AST
Часть 3: Генерация кода LLVM IR
Часть 4: Добавление JIT и поддержки оптимизатора
Часть 5: Расширение языка: Поток управления
Часть 6: Расширение языка: Операторы, определяемые пользователем
Часть 7: Расширение языка: Изменяемые переменные
Часть 8: Компиляция в объектный код
Часть 9: Добавляем отладочную информацию
Часть 10: Заключение и другие вкусности LLVM
Добро пожаловать в заключительную часть руководства “Создание языка программирования с использованием LLVM”. На протяжении этого руководства, мы вырастили наш маленький язык Калейдоскоп с бесполезной игрушки до довольно интересной (хотя, возможно, по-прежнему бесполезной) игрушки.
Интересно видеть, как далеко мы зашли, и насколько мало кода это потребовало. Мы построили полный лексический анализатор, парсер, AST, генератор кода, интерактивное исполнение (с JIT!) и генерацию отладочной информации в самостоятельный исполняемый файл — всё это меньше 1000 строк уода (без учёта пустых строк и комментариев).
Наш маленький язык поддерживает пару интересных возможностей: он поддерживает определяемые пользователем бинарные и унарные операторы, использует JIT-компиляцию для немедленного исполнения, и поддерживает некоторые конструкции управления потоком исполнения с помощью генерации кода в SSA-форме.
Частью идеи этого руководства было показать вам как легко можно определить, построить и поиграть с языком. Построение компилятора не обязательно должно быть пугающим или мистическим процессом! Сейчас, когда вы увидели основы, я настоятельно рекомендую взять код и разбираться с ним. Например, попробуйте добавить:
глобальные переменные — хотя ценность глобальных переменных в современной программной инженерии находится под вопросом, они часто используются для маленьких быстрых хаков, таких, как сам по себе компилятор Калейдоскопа. К счастью, в нашу программу добавить глобальные переменные очень легко: просто проверяем для каждой переменной, есть ли она в глобальной таблице символов. Для того. чтобы создать новую глобальную переменную, создайте экземпляр класса LLVM GlobalVariable.
типизированные переменные — сейчас Калейдоскоп поддерживает только переменные типа double. Это делает язык очень элегантным, потому что поддержка только одного типа означает, что вам не нужно указывать типы переменных. Различные языки имею разные способы решения этой проблемы. Самый простой путь — потребовать от пользователя указывать тип для каждого определения переменной, и записывать типы переменных в таблицу символов вместе с их Value*.
массивы, структуры, вектора, и т.п. Если вы вводите типы, вы можете начать расширять систему типов в разных интересных направлениях. Простые массивы сделать очень просто и полезно для разных видов приложений. Добавьте их в качестве упражнения, для изучения того, как работает инструкция LLVM getelementptr: она настолько элегантна и необычна, что имеет свой собственный FAQ!
стандартный рантайм — в текущем виде язык даёт пользователю возможность доступа к произвольным внешним функциям, и мы используем это для таких вещей, как «printd» и «putchard». Вы можете расширить язык так, чтобы добавить конструкции более высокого уровня, часто имеет смысл приводить такие конструкции к функциям рантайма, чем делать их в виде inline-последовательностей команд.
управление памятью — сейчас в языке Калейдоскоп есть доступ только к стеку. Также будет полезно выделять память в куче, либо путём вызова стандартных интерфейсов libc malloc/free, либо с помощью сборщика мусора. Если вы предпочтёте сборщик мусора, заметим, что LLVM полностью поддерживает точную сборку мусора (Accurate Garbage Collection), включая алгоритмы перемещения объектов, и необходимые для сканирования/обновления стека.
поддержка исключений — LLVM поддерживает генерацию исключений с нулевой стоимостью и с возможностью взаимодействия с кодом, скомпилированным в других языках. Вы можете также генерировать код, который подразумевает, что каждая функция возвращает значение ошибки, и проверяет это. Также можно реализовать исключения явным использованием setjmp/longjmp. В общем, существует много разных способов.
ООП, обобщённые типы, доступ к базам данных, комплексные числа, геометрическое программирование,… на самом деле, нет конца безумным штукам, которые можно добавить в язык.
необычные применения — мы говорили о применении LLVM в области, которой интересуются многие: построение компилятора для специфического языка. Однако, существует много других областей, для которых применение компилятора, на первый взгляд, не рассматривается. Например, LLVM используется для ускорения графики OpenGL, трансляции кода C++ в ActionScript, и множества других интересных вещей. Возможно, вы будете первым, кто построит JIT-компилятор в нативный код для регулярных выражений с помощью LLVM?
удовольствие — пробуйте сделать что-то безумное и необычное. Сделать язык, такой же, как все остальные, не так весело, как сделать что-то безумное. Если вы хотите поговорить об этом, не стесняйтесь писать в рассылку llvm-dev: там много людей, которые интересуются языками и часто желают помочь.
Перед тем, как мы закончим руководство, я хочу дать некоторые советы насчёт генерации LLVM IR. Есть некоторые тонкости, которые могут быть неочевидны, но очень полезны, если вы хотите получить преимущества от возможностей LLVM.
Есть пара вопросов насчёт кода в форме LLVM IR, давайте рассмотрим их сейчас.
Калейдоскоп является примером «переносимого языка»: любая программа, написанная на Калейдоскопе будет работать одинаково на любой целевой платформе, на которой будет запущена. Многие другие языки имеют такое же свойство, например, Lisp, Java, Haskell, Javascript, Python и т.п. (отметим, что, хотя эти языки являются переносимыми, не все их библиотеки переносимы).
Один хороший аспект LLVM состоит в сохранении независимости от целевой платформы на уровне IR: вы можете взять LLVM IR для программы, скомпилированной Калейдоскопом и запустить на любой целевой платформе, поддерживаемой LLVM, даже сгенерировать С-код и скомпилировать на тех целевых платформах, которые Калейдоскоп не поддерживает нативно. Можно сказать, что компилятор Калейдоскопа генерирует платформенно-независимый код потому что он не запрашивает никакой информации о платформе при генерации кода.
Тот факт, что LLVM предоставляет компактное, платформенно-независимое представление кода, очень привлекает. К сожалению, люди часто думают только о компиляции С или С-подобных языков, когда они спрашивают о переносимости языка. Я сказал «к сожалению», потому что на самом деле нельзя (в общем случае) сделать С-код переносимым, т.к., конечно же, сам по себе исходный код на С не является переносимым в общем случае, даже в случае портирования приложения с 32 на 64 бита.
Проблема с С (опять же, в общем случае) в том, что он очень полагается на платформеннозависимые допущения. В качестве простого примера, препроцессор сделает код платформеннозависимым, если он обрабатывает следующий текст:
Хотя возможно решить эту проблему разными сложными путями, она не может быть решена в общем виде.
Но подмножество С можно сделать переносимым. Если вы сделаете примитивные типы фиксированного размера (например, int = 32 бита, long = 64 бита), не будете беспокоиться насчёт совместимости ABI с существующими бинарными файлами, и откажетесь от некоторых других возможностей, то вы можете получить переносимый код. Это имеет смысл для некоторых особых случаев.
Многие из упомянутых языков также являются «безопасными»: для программы, написанной на Java невозможно испортить адресное пространство и уронить процесс (подразумевая, что JVM не имеет багов). Безопасность — это интересное свойство, требующее комбинации проектирования языка, поддержки рантайма, и, зачастую, поддержки ОС.
Определённо возможно реализовать безопасный язык в LLVM, но LLVM IR сам по себе не гарантирует безопасности. LLVM IR допускает небезопасные преобразования указателей, использование памяти после её освобождения, переполнение буферов, и различные другие проблемы. Безопасность должна быть реализована на уровне выше, чем LLVM и, к счастью, несколько групп занимались исследованием этого вопроса. Спрашивайте в списке рассылки llvm-dev, если вам интересны детали.
Есть одна вещь в LLVM, которая многим не нравится: он не решает в рамках одной системы всех проблем мира (простите, голодающие дети, вашу проблему должен решить кто-то другой, не сегодня). Одна претензия, которую предъявляют LLVM, выражается в том, что он не способен выполнить высокоуровневую, специфическую для языка, оптимизацию: LLVM «теряет слишком много информации».
К сожалению, здесь нет места, чтобы написать для вас полную и универсальную версию «теории прокектирования компиляторов». Вместо этого, я сделаю несколько наблюдений:
Первое, это правда, LLVM теряет информацию. Например, невозможно различить на уровне LLVM IR, было ли SSA-значение порождено из типа С «int» или «long» на ILP32-машине (кроме как из отладочной информации). Оба компилируются в значение типа «i32», и информация об исходном типе теряется. Более общая проблема в том, что система типов LLVM считает эквивалентными типы с одинаковой структурой, не с одинаковыми именами. Это ещё одна вещь, которая удивляет людей, что если у вас есть два типа в высокоуровневом языке, имеющие одинаковую структуру, (например, две разных структуры, имеющие по одному полю int): эти типы будут скомпилированы в один тип LLVM, и будет невозможно сказать, какой исходной структуре принадлежали переменные.
Второе, хотя LLVM и теряет информацию, он не имеет фиксированной целевой платформы: мы продолжаем расширять и улучшать его в разных направлениях. Мы добавляем новые возможности (LLVM не всегда поддерживал исключения или отладочную информацию), мы расширяем IR, чтобы захватывать важную для оптимизации информацию (был ли аргумент расширен нулями или знаковым битом, информацию об аласинге указателей и т.п.). Многие улучшения инициированы пользователями: люди хотят, чтобы LLVM имел какие-либо специфические возможности, и мы идём им навстречу.
В-третьих, возможно легко добавлять специфические для языка оптимизации, и есть ряд способов сделать это. Как тривиальный пример, легко добавить проход оптимизации, который «знает» разные вещи о исходном коде. В случае С-подобных языков, такой проход оптимизации «знает» о функциях стандартной библиотеки С. Если вы вызываете функцию «exit(0)» в main(), он знает, что вызов можно безопасно конвертировать в «return 0», потому что стандарт С описывает, что должна делать функция «exit».
Вдобавок к простым знаниям о библиотеке, возможно встроить другую различную специфическую для языка информацию в LLVM IR. Если у вас есть специфические нужды, пожалуйста, напишите в список рассылки llvm-dev. В худшем случае, вы можете рассматривать LLVM как если бы он был «тупым кодогенератором» и реализовывать высокоуровневые оптимизации, какие вам угодно, в вашем фронтенде, в специфичном для вашего языка AST.
Есть различные полезные приёмы и хитрости, к которым вы приходите после того, как поработали с/над LLVM, и которые неочевидны с первого взгляда. Чтобы каждый не открывал их заново, этот раздел посвящён некоторым из них.
Одна интересная вещь заключается в том, что если вы пытаетесь сохранить код, сгенерированный вашим компилятором «платформенно-независимым», вам нужно знать размер типов LLVM и смещение конкретных подей в структурах. Например, вы можете передавать размер типа в функцию, которая аллоцирует память.
К сожалению, размер типов может сильно меняться в зависимости от платформы: размер указателя является простейшим примером. Умным способом решения таких задач будет использование инструкции getelementptr.
Некоторые языки хотят явно управлять кадрами стека, часто из=за наличия сборщика мусора или для того, чтобы проще реализовать замыкания. Часто есть лучшие способы реализации этих возможностей, чем явное управление кадрами стека, но LLVM поддерживает это, если вы хотите. Для этого нужно, чтобы ваш фронтенд конвертировал код в Continuation Passing Style и использовал хвостовые вызовы (которые LLVM также поддерживает).
Часть 1: Введение и лексический анализ
Часть 2: Реализация парсера и AST
Часть 3: Генерация кода LLVM IR
Часть 4: Добавление JIT и поддержки оптимизатора
Часть 5: Расширение языка: Поток управления
Часть 6: Расширение языка: Операторы, определяемые пользователем
Часть 7: Расширение языка: Изменяемые переменные
Часть 8: Компиляция в объектный код
Часть 9: Добавляем отладочную информацию
Часть 10: Заключение и другие вкусности LLVM
9.1. Заключение
Добро пожаловать в заключительную часть руководства “Создание языка программирования с использованием LLVM”. На протяжении этого руководства, мы вырастили наш маленький язык Калейдоскоп с бесполезной игрушки до довольно интересной (хотя, возможно, по-прежнему бесполезной) игрушки.
Интересно видеть, как далеко мы зашли, и насколько мало кода это потребовало. Мы построили полный лексический анализатор, парсер, AST, генератор кода, интерактивное исполнение (с JIT!) и генерацию отладочной информации в самостоятельный исполняемый файл — всё это меньше 1000 строк уода (без учёта пустых строк и комментариев).
Наш маленький язык поддерживает пару интересных возможностей: он поддерживает определяемые пользователем бинарные и унарные операторы, использует JIT-компиляцию для немедленного исполнения, и поддерживает некоторые конструкции управления потоком исполнения с помощью генерации кода в SSA-форме.
Частью идеи этого руководства было показать вам как легко можно определить, построить и поиграть с языком. Построение компилятора не обязательно должно быть пугающим или мистическим процессом! Сейчас, когда вы увидели основы, я настоятельно рекомендую взять код и разбираться с ним. Например, попробуйте добавить:
глобальные переменные — хотя ценность глобальных переменных в современной программной инженерии находится под вопросом, они часто используются для маленьких быстрых хаков, таких, как сам по себе компилятор Калейдоскопа. К счастью, в нашу программу добавить глобальные переменные очень легко: просто проверяем для каждой переменной, есть ли она в глобальной таблице символов. Для того. чтобы создать новую глобальную переменную, создайте экземпляр класса LLVM GlobalVariable.
типизированные переменные — сейчас Калейдоскоп поддерживает только переменные типа double. Это делает язык очень элегантным, потому что поддержка только одного типа означает, что вам не нужно указывать типы переменных. Различные языки имею разные способы решения этой проблемы. Самый простой путь — потребовать от пользователя указывать тип для каждого определения переменной, и записывать типы переменных в таблицу символов вместе с их Value*.
массивы, структуры, вектора, и т.п. Если вы вводите типы, вы можете начать расширять систему типов в разных интересных направлениях. Простые массивы сделать очень просто и полезно для разных видов приложений. Добавьте их в качестве упражнения, для изучения того, как работает инструкция LLVM getelementptr: она настолько элегантна и необычна, что имеет свой собственный FAQ!
стандартный рантайм — в текущем виде язык даёт пользователю возможность доступа к произвольным внешним функциям, и мы используем это для таких вещей, как «printd» и «putchard». Вы можете расширить язык так, чтобы добавить конструкции более высокого уровня, часто имеет смысл приводить такие конструкции к функциям рантайма, чем делать их в виде inline-последовательностей команд.
управление памятью — сейчас в языке Калейдоскоп есть доступ только к стеку. Также будет полезно выделять память в куче, либо путём вызова стандартных интерфейсов libc malloc/free, либо с помощью сборщика мусора. Если вы предпочтёте сборщик мусора, заметим, что LLVM полностью поддерживает точную сборку мусора (Accurate Garbage Collection), включая алгоритмы перемещения объектов, и необходимые для сканирования/обновления стека.
поддержка исключений — LLVM поддерживает генерацию исключений с нулевой стоимостью и с возможностью взаимодействия с кодом, скомпилированным в других языках. Вы можете также генерировать код, который подразумевает, что каждая функция возвращает значение ошибки, и проверяет это. Также можно реализовать исключения явным использованием setjmp/longjmp. В общем, существует много разных способов.
ООП, обобщённые типы, доступ к базам данных, комплексные числа, геометрическое программирование,… на самом деле, нет конца безумным штукам, которые можно добавить в язык.
необычные применения — мы говорили о применении LLVM в области, которой интересуются многие: построение компилятора для специфического языка. Однако, существует много других областей, для которых применение компилятора, на первый взгляд, не рассматривается. Например, LLVM используется для ускорения графики OpenGL, трансляции кода C++ в ActionScript, и множества других интересных вещей. Возможно, вы будете первым, кто построит JIT-компилятор в нативный код для регулярных выражений с помощью LLVM?
удовольствие — пробуйте сделать что-то безумное и необычное. Сделать язык, такой же, как все остальные, не так весело, как сделать что-то безумное. Если вы хотите поговорить об этом, не стесняйтесь писать в рассылку llvm-dev: там много людей, которые интересуются языками и часто желают помочь.
Перед тем, как мы закончим руководство, я хочу дать некоторые советы насчёт генерации LLVM IR. Есть некоторые тонкости, которые могут быть неочевидны, но очень полезны, если вы хотите получить преимущества от возможностей LLVM.
10.2. Свойства LLVM IR
Есть пара вопросов насчёт кода в форме LLVM IR, давайте рассмотрим их сейчас.
10.2.1. Независимость от целевой платформы
Калейдоскоп является примером «переносимого языка»: любая программа, написанная на Калейдоскопе будет работать одинаково на любой целевой платформе, на которой будет запущена. Многие другие языки имеют такое же свойство, например, Lisp, Java, Haskell, Javascript, Python и т.п. (отметим, что, хотя эти языки являются переносимыми, не все их библиотеки переносимы).
Один хороший аспект LLVM состоит в сохранении независимости от целевой платформы на уровне IR: вы можете взять LLVM IR для программы, скомпилированной Калейдоскопом и запустить на любой целевой платформе, поддерживаемой LLVM, даже сгенерировать С-код и скомпилировать на тех целевых платформах, которые Калейдоскоп не поддерживает нативно. Можно сказать, что компилятор Калейдоскопа генерирует платформенно-независимый код потому что он не запрашивает никакой информации о платформе при генерации кода.
Тот факт, что LLVM предоставляет компактное, платформенно-независимое представление кода, очень привлекает. К сожалению, люди часто думают только о компиляции С или С-подобных языков, когда они спрашивают о переносимости языка. Я сказал «к сожалению», потому что на самом деле нельзя (в общем случае) сделать С-код переносимым, т.к., конечно же, сам по себе исходный код на С не является переносимым в общем случае, даже в случае портирования приложения с 32 на 64 бита.
Проблема с С (опять же, в общем случае) в том, что он очень полагается на платформеннозависимые допущения. В качестве простого примера, препроцессор сделает код платформеннозависимым, если он обрабатывает следующий текст:
#ifdef __i386__
int X = 1;
#else
int X = 42;
#endif
Хотя возможно решить эту проблему разными сложными путями, она не может быть решена в общем виде.
Но подмножество С можно сделать переносимым. Если вы сделаете примитивные типы фиксированного размера (например, int = 32 бита, long = 64 бита), не будете беспокоиться насчёт совместимости ABI с существующими бинарными файлами, и откажетесь от некоторых других возможностей, то вы можете получить переносимый код. Это имеет смысл для некоторых особых случаев.
10.2.2. Гарантии безопасности
Многие из упомянутых языков также являются «безопасными»: для программы, написанной на Java невозможно испортить адресное пространство и уронить процесс (подразумевая, что JVM не имеет багов). Безопасность — это интересное свойство, требующее комбинации проектирования языка, поддержки рантайма, и, зачастую, поддержки ОС.
Определённо возможно реализовать безопасный язык в LLVM, но LLVM IR сам по себе не гарантирует безопасности. LLVM IR допускает небезопасные преобразования указателей, использование памяти после её освобождения, переполнение буферов, и различные другие проблемы. Безопасность должна быть реализована на уровне выше, чем LLVM и, к счастью, несколько групп занимались исследованием этого вопроса. Спрашивайте в списке рассылки llvm-dev, если вам интересны детали.
10.2.3. Оптимизации, специфичные для языка
Есть одна вещь в LLVM, которая многим не нравится: он не решает в рамках одной системы всех проблем мира (простите, голодающие дети, вашу проблему должен решить кто-то другой, не сегодня). Одна претензия, которую предъявляют LLVM, выражается в том, что он не способен выполнить высокоуровневую, специфическую для языка, оптимизацию: LLVM «теряет слишком много информации».
К сожалению, здесь нет места, чтобы написать для вас полную и универсальную версию «теории прокектирования компиляторов». Вместо этого, я сделаю несколько наблюдений:
Первое, это правда, LLVM теряет информацию. Например, невозможно различить на уровне LLVM IR, было ли SSA-значение порождено из типа С «int» или «long» на ILP32-машине (кроме как из отладочной информации). Оба компилируются в значение типа «i32», и информация об исходном типе теряется. Более общая проблема в том, что система типов LLVM считает эквивалентными типы с одинаковой структурой, не с одинаковыми именами. Это ещё одна вещь, которая удивляет людей, что если у вас есть два типа в высокоуровневом языке, имеющие одинаковую структуру, (например, две разных структуры, имеющие по одному полю int): эти типы будут скомпилированы в один тип LLVM, и будет невозможно сказать, какой исходной структуре принадлежали переменные.
Второе, хотя LLVM и теряет информацию, он не имеет фиксированной целевой платформы: мы продолжаем расширять и улучшать его в разных направлениях. Мы добавляем новые возможности (LLVM не всегда поддерживал исключения или отладочную информацию), мы расширяем IR, чтобы захватывать важную для оптимизации информацию (был ли аргумент расширен нулями или знаковым битом, информацию об аласинге указателей и т.п.). Многие улучшения инициированы пользователями: люди хотят, чтобы LLVM имел какие-либо специфические возможности, и мы идём им навстречу.
В-третьих, возможно легко добавлять специфические для языка оптимизации, и есть ряд способов сделать это. Как тривиальный пример, легко добавить проход оптимизации, который «знает» разные вещи о исходном коде. В случае С-подобных языков, такой проход оптимизации «знает» о функциях стандартной библиотеки С. Если вы вызываете функцию «exit(0)» в main(), он знает, что вызов можно безопасно конвертировать в «return 0», потому что стандарт С описывает, что должна делать функция «exit».
Вдобавок к простым знаниям о библиотеке, возможно встроить другую различную специфическую для языка информацию в LLVM IR. Если у вас есть специфические нужды, пожалуйста, напишите в список рассылки llvm-dev. В худшем случае, вы можете рассматривать LLVM как если бы он был «тупым кодогенератором» и реализовывать высокоуровневые оптимизации, какие вам угодно, в вашем фронтенде, в специфичном для вашего языка AST.
10.3. Приёмы и хитрости
Есть различные полезные приёмы и хитрости, к которым вы приходите после того, как поработали с/над LLVM, и которые неочевидны с первого взгляда. Чтобы каждый не открывал их заново, этот раздел посвящён некоторым из них.
10.3.1. Реализация переносимых offsetof/sizeof
Одна интересная вещь заключается в том, что если вы пытаетесь сохранить код, сгенерированный вашим компилятором «платформенно-независимым», вам нужно знать размер типов LLVM и смещение конкретных подей в структурах. Например, вы можете передавать размер типа в функцию, которая аллоцирует память.
К сожалению, размер типов может сильно меняться в зависимости от платформы: размер указателя является простейшим примером. Умным способом решения таких задач будет использование инструкции getelementptr.
10.3.2. Стековые кадры сборщика мусора
Некоторые языки хотят явно управлять кадрами стека, часто из=за наличия сборщика мусора или для того, чтобы проще реализовать замыкания. Часто есть лучшие способы реализации этих возможностей, чем явное управление кадрами стека, но LLVM поддерживает это, если вы хотите. Для этого нужно, чтобы ваш фронтенд конвертировал код в Continuation Passing Style и использовал хвостовые вызовы (которые LLVM также поддерживает).
