Кратчайшее введение в создание компилятора
Здесь я попытался показать на практике, что собой представляют некоторые важные концепции из области создания компиляторов. Есть вероятность, что подобные 15-минутные завершенные истории могут оказаться неплохим способом погружения в сложные темы. Только хорошо бы не пассивно читать то, что представлено ниже, а еще и проверять код в работе.
Если первый опыт окажется успешным, то в будущем вас могут ожидать и другие 15-минутные «зарисовки» по тематике компиляторов.
О чем пойдет речь
Давайте сделаем компилятор арифметических выражений. Такой, который переведет исходный текст в обратной польской форме записи (ее еще называют RPN или ПОЛИЗ) в промежуточный код, работающий со стеком. Но мы обойдемся здесь без интерпретаторов. Далее мы сразу переведем результат в представление на языке Си. То есть у нас получится компилятор из RPN в Си.
Кстати говоря, писать компилятор мы будем на Python. Но пусть это не останавливает тех, кто предпочитает какой-то иной язык программирования. Вот вам полезное упражнение: переведите приведенный код на ваш любимый язык. Или воспользуйтесь уже готовым переводом:
Начнем с синтаксического анализа
Что мы здесь сделали? Функция scan получает от пользователя строку в обратной польской форме записи («2 2 +»).
А на выходе мы получаем ее промежуточное представление. Вот такое, например:
Вот так, мы уже получили компилятор. Но уж очень он несерьезный. Вспомним, что изначально речь шла о коде на Си.
Займемся трансляцией в Си
Что здесь происходит? Давайте посмотрим на вывод данной функции (на том же примере с «2 2 +»).
Да, это уже похоже на код на Си. Массив st играет роль стека, а sp — его указатель. Обычно с этими вещами работают виртуальные стековые машины.
Вот только самой машины — интерпретатора у нас-то и нет. Есть компилятор. Что нам осталось? Надо добавить необходимое обрамление для программы на Си.
Наш первый компилятор в готовом виде
Остается скомпилировать вывод данной программы компилятором Си.
Вы все еще готовы продолжать? Тогда давайте обсудим, что у нас получилось. Есть один сомнительный момент — наш компилятор транслирует константные выражения, а ведь их можно вычислить просто на этапе компиляции. Нет смысла переводить их в код. Но давайте пока считать, что какие-то аргументы могут попасть в стек извне. Остановимся на том, что практический смысл нашей разработке можно придать и позднее. Сейчас же важно получить общее представление о построении простейших компиляторов, верно?
Компилятор с использованием формы SSA
Вам нравится заголовок? SSA — это звучит очень солидно для любого компиляторщика. А мы уже сейчас будем использовать эту самую SSA. Что же это такое? Давайте двигаться по порядку.
Мы генерируем в данный момент код на Си, безо всяких виртуальных машин. Но зачем нам тогда рудимент в виде операций со стеком? Давайте заменим эти операции работой с обычными переменными из Си. Причем, мы не будем экономить переменные — для каждого выражения заведем новое имя. Пусть компилятор Си сам со всем этим разбирается. Получается, что у нас каждой переменной значение присваивается лишь однажды. А это, кстати говоря, и есть форма SSA.
Вот наш новый компилятор.
Обратите внимание — стека в коде на Си уже нет, а работа с ним имитируется в процессе трансляции. На стеке, который используется в процессе компиляции, содержатся не значения, а имена переменных.
Вот окончательный результат:
Итоги
Похоже, время нашего совместного занятия истекло. Мы занимались тем, что переводили программу с одного языка на другой. Это называется source-to-source трансляцией. Или же — просто трансляцией, которую можно считать синонимом компиляции, но обычно компилятор переводит программу из высокоуровневого представления в низкоуровневое. Существует еще модное словечко «транспилятор» для обозначения source-to-source транслятора. Но упоминание «транспилятора» может вызвать раздражение у специалистов по компиляторам, будьте осторожны!
Как написать простейший компилятор
Лучший способ понять как работает компилятор — написать свой собственный. В этом поможет этот краткий, но исчерпывающий гайд.
Введение
Стандартный компилятор осуществляет следующие шаги:
В большинстве современных компиляторов (вроде gcc и clang) последние два пункта повторяются еще раз. Для начальной генерации кода они используют не совсем низкоуровневый, но платформонезависимый язык. Потом этот промежуточный код переводится в зависящий от архитектуры (x86, ARM и так далее).
После этого объектный код готов к линковке. Большая часть нативных компиляторов автоматически вызывает линковщик, создающий исполняемый код, но это еще не компиляция. В языках вроде Java или C# линковка может быть полностью динамической и выполняться в виртуальной машине в момент загрузки.
Запомните основные моменты
Компилятор должен быть:
Эта классическая последовательность применима ко всей сфере разработки ПО. Сконцентрируйтесь на первом пункте. Сделайте простейшую вещь и заставьте ее работать.
Читайте книги!
Прочтите книгу «Компиляторы: принципы, технологии и инструменты». Эта бессмертная классика до сегодняшнего дня не потеряла актуальности. «Дизайн современных компиляторов» — также стоящая вещь.
Если на данном этапе это кажется вам слишком сложным, почитайте для начала какие-нибудь введения в парсинг.
Убедитесь, что вам комфортно работать с графами, особенно с деревьями. Это основа построения программ на логическом уровне.
Хорошо определите свой язык
Вы можете использовать любую нотацию, но будьте уверены, что имеете полное и последовательное описание языка. Оно включает в себя как синтаксис, так и семантику.
Используйте свой любимый язык
Это совершенно нормально — писать компилятор на Pyhton, Ruby или любом другом языке, который вам нравится. Используйте простые алгоритмы, принцип которых вы хорошо понимаете. Первый ваш компилятор вовсе не обязан быть быстрым, или эффективным, или обладать кучей фич. Все, что от него требуется — работать достаточно правильно и легко поддаваться переработкам.
Также нормально писать разные стадии развития компилятора на разных языках, если это требуется.
Приготовьтесь к написанию множества тестов
Весь ваш язык должен быть стопроцентно покрыт тестами, эффективнее всего, если он будет определен ими. Будьте на ты с выбранным тестовым фреймворком. Пишите тесты с первого дня. Рационально отдавать предпочтение «позитивным» тестам, которые предполагают корректную работу кода.
Регулярно прогоняйте все тесты. Чините некорректные тесты. Будет очень обидно остаться у разбитого корыта с плохо определенным языком, который не способен принять валидный код.
Сделайте хороший парсер
Парсеров существует огромное количество, выбирайте любой. Можно написать свой собственный, но это сработает только в том случае, если синтаксис вашего языка примитивен до маразма.
Парсер должен выявлять синтаксически ошибки и сообщать о них. Пишите много тестов, как позитивных, так и негативных. Переиспользуйте написанный код для определения языка.
На выходе ваш парсер должен генерировать абстрактное синтаксическое дерево. Если ваш язык использует модули, то результатом работы парсера может быть простейшее представление генерируемого «объектного кода».
Напишите семантический валидатор
Вполне вероятно, что ваш язык допускает синтаксически правильные конструкции, не имеющие смысла в некоторых контекстах. Примером может служить повторное объявление одной и той же переменной или пропуск параметра неправильного типа. Валидатор призван выявлять ошибки такого рода.
Также зона его ответственности охватывает разрешение зависимостей с другими модулями, написанными на вашем языке, загрузкой этих модулей и использовании их в процессе валидации. Например, именно на этом этапе проверяется соответствие количества параметров, поступающих на вход функции из подключаемого модуля.
Еще раз, пишите и запускайте много тестов. Тривиальные случаи также обязательны к рассмотрению, как и сложные.
Генерируйте код
Воспользуйтесь простейшими техниками, которые вы знаете. Чаще всего допустимо непосредственно переводить языковую конструкцию (например, условны й оператор) в слабо параметризированный шаблон кода.
Забудьте об эффективности и сосредоточьтесь только на правильности.
Настройте платформо-независимую низкоуровневую виртуальную машину
Вероятнее всего, вас не очень интересуют низкоуровневые аспекты, если только вы не страстный поклонник всего, что связано с архитектурой.
Забудьте об оптимизации
Оптимизация — это сложно. И почти всегда она бывает преждевременной. Генерируйте неэффективный, но рабочий код. Реализуйте весь язык прежде чем приступите к оптимизации.
Конечно, некоторая простая оптимизация вполне уместна на начальном этапе. Но старайтесь избегать излишних хитростей, пока ваш компилятор не будет достаточно стабилен.
Пишем примитивный и никому не нужный компилятор
Я считаю, что каждый программист должен написать свой компилятор.
Я сам долгое время считал, что создание компиляторов — это удел элиты, а простому смертному программисту не постичь этой науки. Попробую доказать, что это не так.
В посте мы рассмотрим, как можно написать свой компилятор C-подобного языка меньше чем за час, исписав всего 300 строчек кода. В качестве бонуса, сюда входит и код виртуальной машины, в байткод которой будет компилироваться исходник.
Компилятор будет писаться на Python. Я очень люблю этот язык, но код может быть местами корявым. Если что не так — пишите в личку.
Да, компилятор совершенно нагло основан на Tiny-С.
Грамматика
Прежде чем начать, давайте определимся, что именно будет уметь наш язык.
Уметь он будет очень мало:
— единственный тип данных — int
— все переменные — глобальные. Всего есть 26 переменных (a-z)
— из математических операций поддерживаются только «+» и «-»
— единственный оператор сравнения — это »
Это запись грамматики в форме EBNF. Вот что эта запись приблизительно означает.
Программа — это один оператор (statement).
Операторы бывают условными (if..else. ), циклическими (while. ) и просто операторами (напр., «a=2+3»).
Условные и циклические содержат в себе выражение-условие и тело (в виде оператора). Обычные операторы заканчиваются точкой с запятой. Можно группировать операторы в фигурных скобках, тогда получим составной оператор.
Выражения — это либо сумма, либо присваивание переменной значения.
Здесь сумма — это последовательность сложений-вычитаний термов.
Терм — это число, переменная или выражение в скобках.
Переменные — это символы от a до z. Числа — это набор цифр от 0 до 9.
Все эти сложности нужны для того, чтобы указать компилятору как именно автоматически анализировать исходный код. Например, встретили слово «if» — значит дальше идет выражение в скобках, а за ним — оператор.
Лексический анализатор
На вход компилятору поступает текстовый файл (исходник). Лексический анализатор нужен для того, чтобы выделить в этом файле токены. Т.е. строчку «a = 3 + 42;» лексический анализатор должен представить в виде «идентификатор: a», «оператор =», «число 3», «оператор +», «число 42», «символ ;». Лексический анализатор работает только с последовательностью букв, т.е. для него строчка «a b if =» тоже имеет смысл и является абсолютно корректной.
Итак, наш лексический анализатор должен узнавать следующие токены:
Дерево, которое строится парсером, состоит из узлов. У узла есть тип (IF, LESS, SET, VAR. ), значение (если это число или переменная) и несколько дочерних узлов-операндов (в коде — op1, op2, op3). Для if в них хранятся условие и ветки then/else, для циклов — условие и тело цикла.
Для описания узлов введем класс Node. Вот код класса парсера и класса Node:
Этот парсер работает рекурсивно, начиная с метода parse().
Вначале он создает узел «Программа», дочерним узлом которого становится главный оператор программы.
Операторы формируются в методе statement(). В этом методе проверяется первый токен и в зависимости от него формируется if, if/else, while, do/while, составной оператор (если начинается с фигурной скобки) или просто одиночный оператор, завершающийся точкой с запятой.
При построении операторов используются методы expr() — получить выражение и paren_expr() — получить выражение в скобках.
Выражения строятся из проверок, которые строятся из сумм, которые состоят из термов. А термы в свою очередь состоят из чисел, переменных и выражений в скобках. В доме, который построил Джек.
Такая вот рекурсия. Как видите, методы соответствуют понятиям описанной выше грамматики.
На выходе метода parse() получаем объект класса Node, который содержит дерево нашей программы. Это дерево теперь можно преобразовывать в машинный код.
Машинный код
Компилировать мы будем в простенький байт-код нашей специальной виртуальной машины. Виртуальная машина будет стековой, т.к. они значительно проще регистровых. Вот ее возможные инструкции:
Например, операторы «a = 2; b = 5;» преобразуется в такую последовательность инструкций:
Код виртуальной машины очень простой. Он весь описывается в методе run:
Осталось написать собственно компилятор — генератор кода.
Компилятор
Венец нашего творения. Вот его исходный код:
Метод gen() добавляет новый байт (команду или аргумент) в программу (список байт).
В методе compile() собирается вся программа. Фактически, этот метод рекурсивно обходит дерево узлов. и для каждого типа узла генерирует соответствующий код.
Обратите внимание на хитрость в условных операторах и циклах. После JMP/JZ сперва пишем 0, а когда сама ветка скомпилирована и известен адрес, на который надо перейти, чтобы не выполнять эту ветку — значение 0 меняем на фактический адрес.
Тестируем
Тут лежит полный исходник компилятора. Я использовал скриптик для запуска и проверки (у меня Lexer читал из stdin):
Ответы машина выдавала вроде бы правильные.
Как я писал компилятор С++. Пересказ спустя 15 лет
15 лет назад не было Хабрахабра, не было фейсбука, и что характерно, не было компилятора С++, с выводом диагностических сообщений на русском. С тех пор, вышло несколько новых стандартов С++, технологии разработки сделали гигантский скачок, а для написания своего языка программирования или анализатора кода может потребоваться в разы меньше времени, используя существующие фреймворки. Пост о том, как я начинал свою карьеру и путем самообразования и написания компилятора С++, пришел к экспертному уровню. Общие детали реализации, сколько времени это заняло, что получилось в итоге и смысл затеи — тоже внутри.
С чего все начиналось
В далеком 2001-ом году, когда мне купили первый компьютер Duron 800mhz/128mb ram/40gb hdd, я стремительно взялся за изучение программирования. Хотя нет, сначала меня постоянно мучил вопрос, что же поставить Red Hat Linux, FreeBSD или Windows 98/Me? Ориентиром в этом бесконечном мире технологий для меня служил журнал Хакер.
Старый такой, стебный журнал. К слову, с тех пор, стиль изложения в этом издании почти не поменялся.
Виндузятники, ламеры, трояны, элита, линух — вот это все сносило крышу. Реально хотелось
поскорей освоить этот весь стек, которые они там печатали и хакнуть Пентагон (без интернета).
Внутренняя борьба за то, становиться ли Линуксоидом или рубится в игры на винде продолжалась до тех пор, пока в дом не провели интернет. Модемный, скрежечащий 56kb/s интернет, который занимал телефон на время подключения, и качал mp3-песню в районе получаса. При цене порядка 0.1$/mb, одна песня вытягивала на 40-50 центов. Это днем.
А вот ночью, были совсем другие расценки. Можно было с 23.00 до 6.00 залипать во все сайты не отключая изображения в браузере! Поэтому все что можно было скачать из сети за ночь, качалось на винт, и далее прочитывалось уже днем.
В первый день, когда мне домой провели и настроили сеть, админ передо мной открыл IE 5 и Яндекс. И быстро ретировался. Думая, что же первым делом искать в сети, я набрал что-то вроде «сайт для программистов». На что первой ссылкой в выдаче выпал совсем недавно открывшийся rsdn.ru. И на нем я стал зависать продолжительное время, испытывая чувство неудовлетворенности, от того, что мало что понимаю. На то время флагманом и самым популярным языком на форуме (да и вообще) был С++. Поэтому вызов был брошен, и ничего не оставалось, как догонять бородатых дядек в их знаниях по С++.
А еще был не менее интересный сайт на то время — firststeps.ru. Я до сих пор считаю их метод подачи материала наилучшим. Маленькими порциями (шагами), с небольшими конечными результатами. Тем не менее все получалось!
Но вернемся к теме поста. Осилив Кнута, надо было двигаться дальше. Попутно я сходил на курсы Turbo Pascal, прочитал Кернигана и Ритчи, а за ними С++ за 21 день. Из С и С++, мне было не все понятно, я просто брал и переписывал тексты из книг. Загуглить или спросить было не у кого, но зато времени было вагон, так как школу я забросил и перешел в вечернюю, в которую можно было практически не ходить, или появляться на 3-4 урока в неделю.
В итоге с утра до ночи, я фанатично развивался, познавая все новые и новые темы. Мог написать калькулятор, мог написать простое приложение на WinApi. На Delphi 6 тоже получалось что-то нашлепать. В итоге, получив диплом о среднем образовании, я уже был подготовлен на уровне 3-4 курса университета, и разумеется на какую специальность идти учится вопроса не стояло.
Поступив на кафедру Компьютерных систем и сетей, я уже свободно писал на С и С++ задачи любого уровня сложности университета. Хотя, зайдя на тот же rsdn.ru, понимал, как много еще нужно изучить и насколько бывалые форумчане прокаченней меня в плюсах. Это задевало, непонимание и вместе с тем жгучее желание знать все, привело меня к книге «Компиляторы. Инструменты. Методы. Технологии» — А.Ахо, Рави Сети. В простонародье именуемой книгой Дракона. Вот тут и началось самое интересное. Перед этой книгой, был прочитан Герберт Шилдт, Теория и практика С++, в которой он раскрывал продвинутые темы разработки, такие как шифрование, сжатие данных, и самое интересное — написание собственного парсера.
Начав скрупулезно изучать книгу дракона, двигаясь от лексического анализа, затем к синтаксическому и наконец к проверке семантики и генерации кода, ко мне пришло судьбоносное решение — написать свой компилятор С++.
— А почему бы и нет, спросил себя?
— А давай, ответила та часть мозга, которая с возрастом становится все скептичней ко всему
новому. И разработка компилятора началась.
Подготовка
Модемный интернет к тому времени мне перекрыли, в силу смены телефонных линий на цифровые, поэтому для ориентира был скачан стандарт ISO C++ редакции 1998 года. Уже полюбившимся и привычным инструментом стала Visual C++ 6.0.
И по сути задача свелась к тому, чтобы реализовать то, что написано в стандарте С++. Подспорьем в разработке компилятора была книга дракона. А отправной точкой, был парсер-калькулятор из книги Шилдта. Все части пазла собрались воедино и разработка началась.
Препроцессор
Лексический анализатор
Синтаксический анализатор
nrcpp/Parser.cpp
Задача синтаксического анализатора — проверить правильность расстановки лексем, который были получены на этапы лексического анализа.
За основу синтаксического анализатора были взяты опять же простенький парсер из Шилдта, прокаченный до уровня синтаксиса С++, с проверкой переполнения стека. Если мы например напишем:
То мой рекурсивный анализатор съест стэк, и выдаст, что выражение слишком сложное.
У внимательного читателя, может возникнуть вопрос. А зачем изобретать велосипед, ведь был же yacc и lex. Да, был. Но на том этапе, хотелся велосипед с полным контролем над кодом. Разумеется в производительности он уступал сгенерированному этими утилитами коду. Но не в этом была цель — техническое совершенство. Цель была — понять все.
Семантика
Занимает соотвественно главы с 3-ей по 14-ую стандарта ISO C++ 98. Эта наиболее сложная часть, и я уверен, что >90% С++ разработчиков не знает всех правил описанных в этих разделах. Например:
Знали ли вы, что функцию можно объявлять дважды, таким образом:
Есть такие конструкции для указателей:
А это указатель на функцию-член класса X:
Это первое, что пришло в голову. Стоит ли говорить, что при тестировании кода из стандарта в Visual C++ 6, я не редко получал Internal Compiler Error.
Разработка анализатора семантики языка заняла у меня 1.5 года, или полтора курса универа. За это время меня чуть не выгнали, по другим предметам кроме программирования, за счастье получалась тройка (ну, ок четверка), а компилятор тем временем разрабатывался и обрастал функционалом.
Генератор кода
Чего нет в nrcpp?
Зачем писать свой велосипед?
А в заключении хочу отметить то, ради чего писалась этот пост. Написание своего велосипеда, даже если на это потрачено 2 с лишним года, кормит меня до сих пор. Это бесценные знания, база, которая будет с Вами на протяжении всей карьеры разработчика. Будут меняться технологии, фреймворки, выходить новые языки — но фундамент в них будет заложен из прошлого. И на их понимание и освоение уйдет совсем немного времени.
LLVM: компилятор своими руками. Введение
Представим себе, что в один прекрасный день вам пришла в голову идея процессора собственной, ни на что не похожей архитектуры, и вам очень захотелось эту идею реализовать «в железе». К счастью, в этом нет ничего невозможного. Немного верилога, и вот ваша идея реализована. Вам уже снятся прекрасные сны про то, как Intel разорилась, Microsoft спешно переписывает Windows под вашу архитектуру, а Linux-сообщество уже написало под ваш микропроцессор свежую версию системы с весьма нескучными обоями.
Однако, для всего этого не хватает одной мелочи: компилятора!
Да, я знаю, что многие не считают наличие компилятора чем-то важным, считая, что все должны программировать строго на ассемблере. Если вы тоже так считаете, я не буду с вами спорить, просто не читайте дальше.
Если вы хотите, чтобы для вашей оригинальной архитектуры был доступен хотя бы язык С, прошу под кат.
В статье будет рассматриваться применение инфраструктуры компиляторов LLVM для построения собственных решений на её основе.
Область применения LLVM не ограничивается разработкой компиляторов для новых процессоров, инфраструктура компиляторов LLVM также может применяться для разработки компиляторов новых языков программирования, новых алгоритмов оптимизации и специфических инструментов статического анализа программного кода (поиск ошибок, сбор статистики и т.п.).
Например, вы можете использовать какой-то стандартный процессор (например, ARM) в сочетании с специализированным сопроцессором (например, матричный FPU), в этом случае вам может понадобиться модифицировать существующий компилятор для ARM так, чтобы он мог генерировать код для вашего FPU.
Также интересным применением LLVM может быть генерация исходных текстов на языке высокого уровня («перевод» с одного языка на другой). Например, можно написать генератор кода на Verilog по исходному коду на С.
Почему LLVM?
На сегодняшний день существует только два реалистичных пути разработки компилятора для собственной архитектуры: использование GCC либо использование LLVM. Другие проекты компиляторов с открытым исходным кодом либо не достигли той степени развития, как GCC и LLVM, либо устарели и перестали развиваться, они не обладают развитыми алгоритмами оптимизации, и могут не обеспечивать полной совместимости даже со стандартом языка С, не говоря уже о поддержке других языков программирования. Разработка собственного компилятора “с нуля», это весьма нерациональный путь, т.к. существующие опенсорсные решения уже реализуют фронтенд компилятора с множеством весьма нетривиальных алгоритмов оптимизации, которые, к тому же, хорошо протестированы и используются уже длительное время.
Какой из этих двух open-source проектов выбрать в качестве основы для своего компилятора? GCC (GNU Compiler Collection) является более старым проектом, первый релиз которого состоялся в 1987 году, его автором является Ричард Столлман, известный деятель open-source движения [4]. Он поддерживает множество языков программирования: C, C++, Objective C, Fortran, Java, Ada, Go. Также существуют фронтенды для многих других языков программирования, не включенных в основную сборку. Компилятор GCC поддерживает большое количество процессорных архитектур и операционных систем, и является в настоящее время наиболее распространённым компилятором. Сам GCC написан на языке С (в комментариях меня поправили, что он уже по большей части переписан на С++).
LLVM гораздо «моложе», его первый релиз состоялся в 2003 году, он (а точнее, его фронтенд Clang) поддерживает языки программирования C, C++, Objective-C and Objective-C++, и также имеет фронтенды для языков Common Lisp, ActionScript, Ada, D, Fortran, OpenGL Shading Language, Go, Haskell, Java bytecode, Julia, Swift, Python, Ruby, Rust, Scala, C# и Lua. Он разработан в университете Иллинойса, в США, и является основным компилятором для разработки под операционную систему OS X. LLVM написан на языке С++ (С++11 для последних релизов) [5]. 
Относительная «молодость» LLVM не является недостатком, он достаточно зрелый, чтобы в нём не было критических багов, и при этом он не несёт в себе огромного груза устаревших архитектурных решений, как GCC. Модульная структура компилятора позволяет использовать фронтенд LLVM-GCC, который обеспечивает полную поддержку стандартов GCC, при этом генерация кода целевой платформы будет осуществляться LLC (бэкенд LLVM). Также можно использовать Clang — оригинальный фронтенд LLVM.
LLVM хорошо документирован, и для него большое количество примеров кода.
Модульная архитектура компилятора
Рис. 1. Модульная архитектура компилятора
Кроме вышеперечисленных программ, LLVM включает в себя и другие утилиты [6].
Итак, напишем простейшую программу на C.
; Function Attrs: nounwind
define i32 @foo(i32 %x, i32 %y) #0 <
%1 = alloca i32, align 4
%2 = alloca i32, align 4
store i32 %x, i32* %1, align 4
store i32 %y, i32* %2, align 4
%3 = load i32* %1, align 4
%4 = load i32* %2, align 4
%5 = add nsw i32 %3, %4
ret i32 %5
>
Структура кода LLVM
Структура кода LLVM очень проста. Код программы состоит из модулей, компилятор обрабатывает по одному модулю за раз. В модуле есть глобальные объявления (переменные, константы и объявления заголовков функций, находящихся в других модулях) и функции. Функции имеют аргументы и возвращаемые типы. Функции состоят из базовых блоков. Базовый блок — это последовательность команд ассемблера LLVM, имеющая одну точку входа и одну точку выхода. Базовый блок не содержит внутри себя никаких ветвлений и циклов, он выполняется строго последовательно от начала до конца и должен заканчиваться терминирующей командой (возвратом из функции или переходом на другой блок).
И, наконец, базовый блок состоит из команд ассемблера. Список команд приведён в документации на LLVM [7].
Итак, ещё раз: базовый блок имеет одну точку входа, помеченную меткой, и обязательно должен заканчиваться командой безусловного перехода br или командой возврата ret. Перед ними может быть команда условного перехода, в этом случае она должна быть непосредственно перед терминирующей командой. Базовый блок имеет список predecessors — базовых блоков, из которых управление может приходить на него, и successors — базовых блоков, которым он может передавать управление. На основе этой информации строится CFG — Control Flow Graph, граф потока управления, важнейшая структура, представляющая программу в компиляторе.
Рассмотрим тестовый пример на языке С:
Пусть исходный код на языке С имеет цикл:
SSA-форма
Код в SSA-форме: load/store
; :2 ; preds = %12, %0
%3 = load i32* %i, align 4
%4 = icmp slt i32 %3, 10
br i1 %4, label %5, label %15
; :5 ; preds = %2
%6 = load i32* %i, align 4
%7 = load i32** %1, align 4
%8 = getelementptr inbounds i32* %7, i32 %6
%9 = load i32* %8, align 4
%10 = load i32* %sum, align 4
%11 = add nsw i32 %10, %9
store i32 %11, i32* %sum, align 4
br label %12
; :12 ; preds = %5
%13 = load i32* %i, align 4
%14 = add nsw i32 %13, 1
store i32 %14, i32* %i, align 4
br label %2
; :15 ; preds = %2
%16 = load i32* %sum, align 4
ret i32 %16
>
Здесь мы видим то, о чем было написано выше: переменная цикла, это просто ячейка памяти, на которую ссылается указатель %i.
Код в SSA-форме: φ-функции
Теперь попробуем уровень оптимизации O1:
define i32 @for_loop(i32* nocapture readonly %x) #0 <
br label %1
; :6 ; preds = %1
ret i32 %4
>
Здесь мы видим, что переменной цикла является %i.02 (имена переменных в LLVM могут содержать точки), и это не указатель, а обычная 32-битная переменная, а присваивание значения происходит с помощью функции phi i32 [ 0, %0 ], [ %5, %1 ]. Это означает, что функция примет значение 0, если переход произошёл с базового блока %0 (первый базовый блок в функции), и значение переменной %5, если переход произошёл с базового блока %1 (т.е. с выходной точки этого же базового блока). Таким образом, генератор IR-кода избавился от двух присваиваний переменной, строго следуя формальным правилам SSA. Далее видно, что сходным образом происходит присваивание переменной %sum.01.
Итак, смысл φ-функции состоит в том, что её значение зависит от того, из какого базового блока был произведён переход на неё. φ-функции могут находиться только в начале базового блока. Если их несколько, они должны следовать непрерывно, начиная с первой инструкции базового блока.
Moar optimization!
Компоновка IR-кода
Реальные программы состоят не из одного модуля. Традиционный компилятор компилирует модули по отдельности, превращая их в объектные файлы, а затем передаёт их компоновщику (линкеру), который объединяет их в один исполняемый файл. LLVM тоже позволяет так делать.
Но LLVM имеет также возможность компоновки IR-кода. Проще всего рассмотреть это на примере. Пусть есть два исходных модуля: foo.c и bar.c:
; Function Attrs: nounwind readnone
define i32 @bar(i32 %x, i32 %k) #0 <
%1 = mul nsw i32 %x, %x
%2 = mul nsw i32 %1, %k
ret i32 %2
>
Здесь видно, что в функции foo не происходит никаких вызовов, компилятор перенёс в неё содержимое bar() полностью, попутно подставив константные значения k. Хотя функция bar() осталась в модуле, она будет исключена при компиляции исполняемого файла, при условии, что она не вызывается нигде больше в программе.
Нужно отметить, что в GCC также есть возможность компоновки и оптимизации промежуточного кода (LTO, link-time optimization) [6].
Разумеется, оптимизация в LLVM не исчерпывается оптимизацией IR-кода. Внутри бэкенда также происходят различные оптимизации на разных стадиях преобразования IR-кода в машинное представление. Часть таких оптимизаций LLVM производит самостоятельно, но разработчик бэкенда может (и должен) разработать собственные алгоритмы оптимизации, которые позволят в полной мере использовать особенности архитектуры процессора.
Генерация кода целевой платформы
Разработка компилятора для оригинальной архитектуры процессора, это, в основном, разработка бэкенда. Вмешательство в алгоритмы фронтенда, как правило, не является необходимым, или, во всяком случае, требует весьма веских оснований. Если проанализировать исходный код Clang, можно увидеть, что большая часть «особенных» алгоритмов приходится на процессоры x86 и PowerPC с их нестандартными форматами вещественных чисел. Для большинства других процессоров нужно указать только размеры базовых типов и endianness (big-endian или little-endian). Чаще всего можно просто найти аналогичный (в плане разрядности) процессор среди множества поддерживаемых.
Генерация кода для целевой платформы происходит в бэкенде LLVM, LLC. LLC поддерживает множество различных процессоров, и вы можете на его основе сделать генератор кода для вашего собственного оригинального процессора. Эта задача упрощается ещё и благодаря тому, что весь исходный код, включая модули для каждой поддерживаемой архитектуры, полностью открыт и доступен для изучения.
Именно генератор кода для целевой платформы (таргета) является наиболее трудоёмкой задачей при разработке компилятора на основе инфрастуктуры LLVM. Я решил не останавливаться подробно здесь на особенностях реализации бэкенда, так как они существенным образом зависят от архитектуры целевого процессора. Впрочем, если у уважаемой аудитории хабра возникнет интерес к данной теме, я готов описать ключевые моменты разработки бэкенда в следующей статье.
