Неверно что программная модель построенная на основе компилятора

Процесс компиляции программ на C++

Цель данной статьи:

В данной статье я хочу рассказать о том, как происходит компиляция программ, написанных на языке C++, и описать каждый этап компиляции. Я не преследую цель рассказать обо всем подробно в деталях, а только дать общее видение. Также данная статья — это необходимое введение перед следующей статьей про статические и динамические библиотеки, так как процесс компиляции крайне важен для понимания перед дальнейшим повествованием о библиотеках.

Все действия будут производиться на Ubuntu версии 16.04.
Используя компилятор g++ версии:

Состав компилятора g++

Мы не будем вызывать данные компоненты напрямую, так как для того, чтобы работать с C++ кодом, требуются дополнительные библиотеки, позволив все необходимые подгрузки делать основному компоненту компилятора — g++.

Зачем нужно компилировать исходные файлы?

Исходный C++ файл — это всего лишь код, но его невозможно запустить как программу или использовать как библиотеку. Поэтому каждый исходный файл требуется скомпилировать в исполняемый файл, динамическую или статическую библиотеки (данные библиотеки будут рассмотрены в следующей статье).

Этапы компиляции:

driver.cpp:

1) Препроцессинг

Самая первая стадия компиляции программы.

Препроцессор — это макро процессор, который преобразовывает вашу программу для дальнейшего компилирования. На данной стадии происходит происходит работа с препроцессорными директивами. Например, препроцессор добавляет хэдеры в код (#include), убирает комментирования, заменяет макросы (#define) их значениями, выбирает нужные куски кода в соответствии с условиями #if, #ifdef и #ifndef.

Хэдеры, включенные в программу с помощью директивы #include, рекурсивно проходят стадию препроцессинга и включаются в выпускаемый файл. Однако, каждый хэдер может быть открыт во время препроцессинга несколько раз, поэтому, обычно, используются специальные препроцессорные директивы, предохраняющие от циклической зависимости.

Получим препроцессированный код в выходной файл driver.ii (прошедшие через стадию препроцессинга C++ файлы имеют расширение .ii), используя флаг -E, который сообщает компилятору, что компилировать (об этом далее) файл не нужно, а только провести его препроцессинг:

Взглянув на тело функции main в новом сгенерированном файле, можно заметить, что макрос RETURN был заменен:

В новом сгенерированном файле также можно увидеть огромное количество новых строк, это различные библиотеки и хэдер iostream.

2) Компиляция

На данном шаге g++ выполняет свою главную задачу — компилирует, то есть преобразует полученный на прошлом шаге код без директив в ассемблерный код. Это промежуточный шаг между высокоуровневым языком и машинным (бинарным) кодом.

Ассемблерный код — это доступное для понимания человеком представление машинного кода.

Используя флаг -S, который сообщает компилятору остановиться после стадии компиляции, получим ассемблерный код в выходном файле driver.s:

Мы можем все также посмотреть и прочесть полученный результат. Но для того, чтобы машина поняла наш код, требуется преобразовать его в машинный код, который мы и получим на следующем шаге.

3) Ассемблирование

Так как x86 процессоры исполняют команды на бинарном коде, необходимо перевести ассемблерный код в машинный с помощью ассемблера.

Ассемблер преобразовывает ассемблерный код в машинный код, сохраняя его в объектном файле.

Объектный файл — это созданный ассемблером промежуточный файл, хранящий кусок машинного кода. Этот кусок машинного кода, который еще не был связан вместе с другими кусками машинного кода в конечную выполняемую программу, называется объектным кодом.

Далее возможно сохранение данного объектного кода в статические библиотеки для того, чтобы не компилировать данный код снова.

Получим машинный код с помощью ассемблера (as) в выходной объектный файл driver.o:

Но на данном шаге еще ничего не закончено, ведь объектных файлов может быть много и нужно их всех соединить в единый исполняемый файл с помощью компоновщика (линкера). Поэтому мы переходим к следующей стадии.

4) Компоновка

Компоновщик (линкер) связывает все объектные файлы и статические библиотеки в единый исполняемый файл, который мы и сможем запустить в дальнейшем. Для того, чтобы понять как происходит связка, следует рассказать о таблице символов.

Таблица символов — это структура данных, создаваемая самим компилятором и хранящаяся в самих объектных файлах. Таблица символов хранит имена переменных, функций, классов, объектов и т.д., где каждому идентификатору (символу) соотносится его тип, область видимости. Также таблица символов хранит адреса ссылок на данные и процедуры в других объектных файлах.
Именно с помощью таблицы символов и хранящихся в них ссылок линкер будет способен в дальнейшем построить связи между данными среди множества других объектных файлов и создать единый исполняемый файл из них.

Получим исполняемый файл driver:

5) Загрузка

Последний этап, который предстоит пройти нашей программе — вызвать загрузчик для загрузки нашей программы в память. На данной стадии также возможна подгрузка динамических библиотек.

Запустим нашу программу:

Заключение

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

Источник

Краткий и бодрый обзор архитектуры компиляторов

Большинство компиляторов имеют следующую архитектуру:

В данной статье я собираюсь детально препарировать эту архитектуру, элемент за элементом.
Можно сказать, что эта статья — дополнение к огромному количеству существующих ресурсов на тему компиляторов. Она является автономным источником, который позволит вам разобраться в основах дизайна и реализации языков программирования.

Целевая аудитория статьи — люди, чье представление о работе компиляторов крайне ограничено (максимум — то, что они занимаются компилированием). Однако я жду, что читатель разбирается в структурах и алгоритмах данных.

Статья ни в коем случае не посвящена современным производственным компиляторам с миллионами строк кода — нет, это краткий курс «компиляторы для чайников», помогающий разобраться, что такое компилятор.

Введение

Сейчас я работаю над системным языком Krug, вдохновленным Rust и Go. В статье я буду обращаться к Krug в качестве примера для иллюстрации своих мыслей. Krug находится в стадии разработки, но уже доступен на https://github.com/krug-lang в репозиториях caasper и krug. Язык не совсем типичен по сравнению с обычной архитектурой компиляторов, что отчасти и вдохновило меня на написание статьи — но об этом позже.

Спешу сообщить, что я ни в коей степени не являюсь специалистом по компиляторам! У меня нет докторской степени, и я не проходил никакого формального обучения — все описанное в статье я изучил самостоятельно в свободное время. Также должен сказать, что я не описываю фактический, единственно верный подход к созданию компилятора, а, скорее, представляю базовые методы, пригодные для создания небольшого «игрушечного» компилятора.

Фронтенд

Лексический анализ

Когда я начинал изучать компиляторы и дизайн языков, мне сказали, что лексический анализ — то же самое, что и токенизация. Этим описанием мы и воспользуемся. Анализатор берет вводные данные в форме строк или потока символов и распознает в них паттерны, которые он нарезает в токены.

В случае компилятора на вход он получает написанную программу. Она считывается в строку из файла, а анализатор токенизирует ее исходный код.

В данном фрагменте, написанном на C-образном языке, можно увидеть структуру, содержащую вышеупомянутую lexeme, а также TokenType, который служит для распознавания данной лексемы.

Примечание: статья не является инструкцией для создания языка с примерами — но для лучшего понимания я буду время от времени вставлять фрагменты кода.

Обычно анализаторы являются простейшими компонентами компилятора. Весь фронтенд, по сути, довольно прост по сравнению с остальными кусочками паззла. Хотя это во многом зависит от вашей работы.

Возьмем следующий кусочек кода на C:

Считав его из файла в строку и проведя линейное сканирование, вы, возможно, сможете нарезать токены. Мы идентифицируем токены естественным образом — видя, что int — это «слово», а 0 в операторе возврата — «число». Лексический анализатор проделывает ту же процедуру, что и мы — позже мы разберемся в этом процессе детальнее. Например, проанализируем числа:

Определение слов может представлять сложность. Большинство языков определяют слово как последовательность букв и цифр, а идентификатор, как правило, должен начинаться с буквы или нижнего подчеркивания. Например:

В Go этот код не будет считаться правильным и будет разобран на следующие токены:

Большинство встречающихся идентификаторов выглядят так:

Анализаторам придется решать и другие проблемы, связанные, например, с пробелами, многострочными и однострочными комментариями, идентификаторами, числами, системами счисления и форматированием чисел (например, 1_000_000) и кодировками (например, поддержкой UTF8 вместо ASCII).

И если вы думаете, что можете прибегнуть к регулярным выражениям — лучше не стоит. Гораздо проще написать анализатор с нуля, но я очень рекомендую прочесть эту статью от нашего царя и бога Роба Пайка. Причины, по которым нам не подойдет Regex, описаны во множестве других статей, так что этот момент я опущу. К тому же, писать анализатор гораздо интереснее, чем мучиться над длинными многословными выражениями, загруженными на regex101.com в 5:24 утра. В своем первом языке я использовал для токенизации функцию split(str) — и далеко не продвинулся.

Парсинг

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

Парсеры в компиляторах обычно принимают входные данные в форме токенов и строят определенное дерево — абстрактное синтаксическое дерево или дерево парсинга. По своей природе они сходны, но имеют некоторые различия.

Эти этапы можно представить в виде функций:

Обычно компиляторы строятся из множества маленьких компонентов, которые берут входные данные, меняют их или преобразуют их в различные выходные данные. Это одна из причин, по которым функциональные языки хорошо подходят для создания компиляторов. Другие причины — прекрасное сопоставление с эталоном и довольно обширные стандартные библиотеки. Прикольный факт: первая реализация компилятора Rust была на Ocaml.

Советую держать эти компоненты как можно более простыми и автономными — модульность сильно облегчит процесс. По-моему, то же можно сказать и о многих других аспектах разработки ПО.

Деревья

Дерево парсинга

Что это, блин, такое? Также известное как дерево грамматического разбора, это густое дерево служит для визуализации программы-источника. В них содержится вся информация (или большая ее часть) о программе ввода, обычно совпадающая с тем, что описано в грамматике вашего языка. Каждый узел дерева будет концевым или неконцевым, например, NumberConstant или StringConstant.

Абстрактное синтаксическое дерево

Как можно понять из названия, АСД — абстрактное синтаксическое дерево. Дерево парсинга содержит множество (часто излишней) информации о вашей программе, а в случае АСД она не требуется. АСД не нуждается в бесполезной информации о структуре и грамматике, которая не влияет на семантику программы.

Предположим, в вашем дереве есть выражение типа ((5+5)-3)+2. В дереве парсинга вы хранили бы его полностью, вместе со скобками, операторами и значениями 5, 5, 3 и 2. Но с АСД можно просто провести ассоциации — нам нужно знать только значения, операторы и их порядок.

На картинке ниже показано дерево для выражения a+b/c.

АСД можно представить следующим образом:

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

Надеюсь, что вы уловили суть того, как будет проходить пошаговый парсинг остальных узлов, начиная с высокоуровневых языковых конструкций. Как именно реализуется синтаксический анализатор с рекурсивным спуском, вам нужно изучить самостоятельно.

Грамматика

Проведение парсинга в АСД из набора токенов может оказаться непростым. Обычно вам следует начать с грамматики вашего языка. По сути, грамматика определяет структуру вашего языка. Существует несколько языков для определения языков, которые могут описать (или разобрать) сами себя.

Пример языка для определения языков — расширенная форма Бэкуса-Наура (РБНФ). Она представляет собой вариацию БНФ с меньшим количеством угловых скобок. Вот пример РБНФ из статьи Википедии:

Продукционные правила определены: они указывают, какой шаблон терминалов составляет «нетерминал». Терминалы — часть алфавита, например, токен if или 0 и 1 в примере выше — терминалы. Нетерминалы — их противоположность, они находятся в левой части продукционных правил, и их можно считать переменными или «именованными указателями» на группы терминалов и нетерминалов.

Во многих языках имеются спецификации, которые содержат грамматику. Например, для Go, Rust и D.

Анализаторы с рекурсивным спуском

Рекурсивный спуск — самый простой из многочисленных подходов к парсингу.

Анализаторы с рекурсивным спуском — нисходящие, основанные на рекурсивных процедурах. Гораздо проще написать парсер, ведь в вашей грамматике нет левой рекурсии. В большинстве «игрушечных» языков этой техники достаточна для парсинга. В GCC используется написанный вручную нисходящий парсер, хотя до того использовался YACC.

Впрочем, с парсингом этих языков могут возникать проблемы. В особенности C, где

может быть интерпретировано как

В реализации Clang также используется анализатор с рекурсивным спуском:

Поскольку это обычный код для C++, рекурсивный спуск позволяет новичкам легко его понять. Он поддерживает специально созданные правила и другие странные штуки, требуемые C/C++ и помогает с легкостью реализовать диагностику и исправление ошибок.

Также стоит обратить внимание на другие подходы:

Парсер-генераторы

Еще один хороший способ. Конечно, есть и минусы — но это можно сказать про любой другой выбор, который делают программисты при создании ПО.

Парсер-генераторы работают очень резво. Использовать их проще, чем написать собственный анализатор и получить качественный результат — хотя они и не очень дружелюбны к пользователю и не всегда выводят сообщения об ошибках. К тому же вам придется учиться использовать парсер-генератор, а при раскрутке компилятора, вероятно, придется раскручивать и парсер-генератор.

Пример генератора парсеров — ANTLR, есть и множество других.

Думаю, что этот инструмент подходит для тех, кому не хочется тратить время на написание фронтенда, и кто предпочел бы написать середину и бэкенд компилятора/интерпретатора и анализировать что бы то ни было.

Применение парсинга

Если вы еще не поняли сами. Даже фронтенд компилятора (lex/parse) может применяться и для решения других проблем:

Середина

Семантический анализ! Анализ семантики языка — одна из сложнейших задач при создании компилятора.

Нужно удостовериться, что все входные программы работают правильно. В мой язык Krug пока не включены аспекты, связанные с семантическим анализом, а без него программист будет обязан всегда писать верный код. В реальности это невозможно — и мы все время пишем, компилируем, иногда запускаем, исправляем ошибки. Эта спираль бесконечна.

Кроме того, компиляция программ невозможна без анализа правильности семантики на соответствующем этапе компиляции.

Когда-то мне попадалась диаграмма, посвященная процентному соотношению фронтенда, миддленда и бэкенда. Тогда оно выглядело как

Сегодня оно представляет собой что-то вроде

Фронтендом занимается, в основном, генератор, а в бесконтекстных языках, не обладающих двойственностью грамматики, их можно выполнить довольно быстро — здесь поможет рекурсивный спуск.

С технологией LLVM большая часть работы по оптимизации может быть загружена во фреймворк, в котором представлен целый ряд готовых оптимизаций.

Следующий шаг — семантический анализ, важнейшая часть фазы компиляции.

Например, в Rust с его моделью управления памятью компилятор выступает как большая мощная машина, которая проводит различные виды статического анализа на вводных формах. Отчасти эта задача состоит в конвертации входных данных в более удобную для анализа форму.

По этой причине семантический анализ играет важную роль в архитектуре компилятора, а изнурительная подготовительная работа вроде оптимизации сгенерированной сборки или считывания входных данных в АСД выполняется за вас.

Семантические проходы

Я не буду рассматривать каждый проход, тем более что они разнятся в зависимости от языка, но ниже описано несколько шагов в Krug.

Объявление высшего уровня

Компилятор пройдется по всем объявлениям «высшего уровня» в модулях и осознает их существование. Глубже в блоки он не пойдет — он просто объявит, какие структуры, функции и т.д. имеются в том или ином модуле.

Разрешение имени/символа

Компилятор проходит по всем блокам кода в функциях и т.п. и разрешает их — то есть, находит символы, требующие разрешения. Это распространенный проход, и именно отсюда, как правило, приходит ошибка No such symbol XYZ при компиляции кода Go.

Выполнить этот проход может быть очень непросто, особенно если в вашей диаграмме зависимостей есть циклические зависимости. Некоторые языки их не допускают, например, Go выдаст ошибку, если какой-то из ваших пакетов формирует цикл, как и мой язык Krug. Циклические зависимости можно считать побочным эффектом плохой архитектуры.

Циклы можно определять, модифицируя DFS в диаграмме зависимостей, или воспользовавшись алгоритмом Тарьяна (как это сделано в Krug) для определения (множественных) циклов.

Выведение типов (Type Inference)

Компилятор проходит через все переменные и выводит их типы. Выведение типов в Krug очень слабое, оно просто выводит переменные на основе их значений. Это никоим образом не причудливая система, вроде тех, можно встретить в функциональных языках наподобие Haskell.

Выводить типы можно с помощью процесса «унификации», или «унификации типов». Для более простых систем типов можно использовать очень простую реализацию.

Типы реализованы в Krug так:

Когда-то я написал простое приведение типов на Go, которое стало прототипом реализации для Krug.

Проход на изменяемость переменных (Mutability Pass)

Krug (как и Rust) по умолчанию является неизменяемым языком, то есть переменные остаются неизменными, если не задано иное:

Компилятор проходит по всем блокам и функциям и проверяет, что их «переменные корректны», то есть мы не меняем то, что не следует, и что все переменные, передаваемые определённым функциям, являются постоянными или изменяемым там, где требуется.

Это делается с помощью символьной информации, которая собрана за предыдущие проходы. Символьная таблица, построенная по результатам семантического прохода, содержит имена токенов и признаки изменяемости переменных. Она может содержать и другие данные, к примеру, в С++ в таблице может храниться информация о том, является символ внешним или статичным.

Символьные таблицы

Символьная таблица, или «stab», это таблица для поиска символов, которые используются в вашей программе. Для каждой области видимости создаётся по одной таблице, и все они содержат информацию о символах, присутствующих в конкретной области видимости.

К этой информации относятся такие свойства, как имя символа, тип, признак изменяемости, наличие внешней связи, расположение в статичной памяти и прочее.

Область видимости

Это важная концепция в языках программирования. Конечно, ваш язык не обязан давать возможность создавать вложенные области видимости, всё можно поместить в одно общее пространство имён!

Хотя представление области видимости является интересной задачей для архитектуры компилятора, в большинстве С-подобных языков область видимости ведёт себя (или является) как стековая структура данных (stack data structure).

Обычно мы создаём и уничтожаем области видимости, и обычно они используются для управления именами, то есть позволяют нам скрывать (shadowing) переменные:

Это можно представить иначе:

Небольшой оффтоп, но рекомендую почитать про спагетти-стек. Это структура данных, которая используется для хранения областей видимости в АСД-узлах противоположных блоков.

Системы типов

Многие из последующих разделов можно развить в отдельные статьи, но мне кажется, этот заголовок заслуживает этого больше всего. Сегодня доступно много информации о системах типов, как и разновидностей самих систем, вокруг которых ломается много копий. Я не будут глубоко погружаться в эту тему, лишь оставлю ссылку на прекрасную статью Стива Клабника.

Система типов — это то, что обеспечивается и семантически определяется в компиляторе с помощью представлений компилятора и анализа этих представлений.

Владение

Эта концепция используется в программировании всё шире. Принципы семантики владения и перемещения заложены в язык Rust, и надеюсь, будут появляться и в других языках. В Rust выполняется много разных видов статического анализа, с помощью которого проверяется, удовлетворяют ли входные данные набору правил в отношении памяти: кто и какой памятью владеет, когда память уничтожается и сколько существует ссылок (или заимствований) на эти значения или память.

Красота Rust заключается в том, что всё это выполняется в ходе компиляции, внутри компилятора, так что программисту не приходится заниматься сборкой мусора или подсчётом ссылок. Все эти семантики отнесены к системе типов и могут обеспечиваться ещё до того, как программа будет представлена в виде завершённого бинарного файла.

Я не могу сказать, как всё это устроено под капотом, но всё это является результатом статического анализа и замечательного исследования команды Mozilla и участников проекта Cyclone.

Графы потоков управления (Control Flow Graphs)

Для представления потоков программ мы используем графы потоков управления (CFG), которые содержат все пути, по которым может пойти исполнение программы. Это используется при семантическом анализе для исключения нерабочих участков кода, то есть блоков, функций и даже модулей, которые никогда не будут достигнуты в ходе исполнения программы. Также графы можно применять для выявления циклов, которые не могут прерваться. Или для поиска недоступного кода, например, когда вы вызываете «панику» (call a panic), или возвращаете в цикле, а код снаружи цикла не исполняется. Анализ потока данных играет важную роль в ходе семантической фазы работы компилятора, так что рекомендую почитать о тех видах анализа, которые вы можете выполнять, как они работают и какие оптимизации могут делать.

Бэкенд

Заключительная часть нашей схемы архитектуры.

Мы сделали большую часть работы по генерированию исполняемых бинарников. Сделать это можно разными способами, которые мы обсудим ниже.

Не обязательно сильно менять фазу семантического анализа из-за информации, содержащейся в дереве. Возможно, лучше вообще её не менять, чтобы избежать возникновения «спагетти».

Несколько слов о транспиляторах

Это разновидность компиляторов, которые преобразуют код на одном языке в исходный код на другом. Например, вы можете написать код, который компилируется в исходники на С. На мой взгляд, вещь довольно бессмысленная, если только ваш язык не уступает сильно тому языку, в который он компилируется. Обычно траспиляция имеет смысл для относительно высокоуровневых языков, или для языков с ограниченными возможностями.

Тем не менее, в истории компиляторов очень часто встречается преобразование в код на С. По сути, первый компилятор С++ — Cfront — транспилировал в код на C.

Хорошим примером является JavaScript. В его код транспилирует TypeScript и многие другие языки, чтобы привнести больше возможностей и, что ещё важнее, чувствительную систему типов с разным количеством видов статического анализа для ловли багов и ошибок, прежде чем мы столкнёмся с ними в ходе исполнения.

Это одна из «целей» компилятора, причём чаще всего самая простая, поскольку вам не нужно думать в рамках более низкоуровневых концепций о присвоении переменных, о работе с оптимизацией и так далее, ведь вы просто «падаете на хвост» другому языку. Однако у этого подхода есть очевидный недостаток — большие накладные расходы, к тому же вы обычно ограничены возможностями языка, в который транспилируете свой код.

Многие современные компиляторы обычно используют в качестве своего бэкенда LLVM: Rust, Swift, C/C++ (clang), D, Haskell.

Это можно считать «простым путём», потому что за вас проделали большую часть работы по поддержке широкого спектра архитектур, и вам доступны оптимизации высочайшего уровня. По сравнению с вышеупомянутой транспиляцией, LLVM предоставляет и большие возможности по управлению. Уж точно больше, чем если бы вы компилировали в С. К примеру, вы можете решать, насколько большими должны быть типы, скажем, 1, 4, 8 или 16-битные. В С это сделать не так просто, иногда невозможно, а для каких-то платформ даже нельзя определить.

Генерирование ассемблер-кода

Генерирование кода под конкретную архитектуру — то есть генерирование машинного кода, — это технически самый популярный путь, который применяется во множестве языков программирования.

Go — это пример современного языка, который не пользуется преимуществами фреймворка LLVM (на момент написания этой статьи). Go генерирует код для нескольких платформ, в том числе Windows, Linux и MacOS. Забавно, что в прототипе Krug раньше тоже генерировался ассемблер-код.

У этого подхода есть много достоинств и недостатков. Однако сегодня, когда доступны технологии вроде LLVM, уже неразумно самостоятельно генерировать ассемблер, потому что маловероятно, что игрушечный компилятор с собственным бэкендом превзойдёт LLVM по уровню оптимизации для одной платформы, не говоря уже о нескольких.

Тем не менее, значительное преимущество самостоятельного генерирования ассемблера заключается в том, что ваш компилятор наверняка окажется гораздо быстрее, чем если бы вы использовали фреймворк наподобие LLVM, который сначала должен собрать ваш IR, оптимизировать и так далее, и потом, наконец, сможет выдать ассемблер (или что вы там выберете).

Но попытаться всё равно приятно. И к тому же будет интересно, если вы захотите узнать больше о программировании на ассемблере, или о том, как языки программирования работают на нижних уровнях. Проще всего открыть АСД или сгенерированный IR (если у вас он есть) и «выдать» инструкции ассемблера в файл с помощью fprintf или другой утилиты. Так работает 8cc.

Генерирование байткода

Также вы можете генерировать байткод для виртуальной машины определённого вида или интерпретатора байткода. Яркий пример — Java: по сути, JVM породила целое семейство генерирующих для неё байткод языков, например, Kotlin.

У генерирования байткода много преимуществ, и для Java главным была портируемость. Если вы можете где угодно запускать свою виртуальную машину, то любой выполняемый на ней код тоже будет работать где угодно. К тому же гораздо проще запускать на машинах абстрактный набор байткодовых инструкций, чем генерировать код по стопицот компьютерных архитектур.
Насколько я знаю, JVM с помощью JIT превращает часто используемый код в нативные функции, а также применяет другие JIT-ухищрения, чтобы выжать ещё больше производительности.

Оптимизации

Они являются неотъемлемой частью компилятора, никому не нужен медленно работающий код! Обычно оптимизации составляют большую часть бэкенда, и разработчики прикладывают много усилий, чтобы повысить производительность. Если вы когда-нибудь скомпилируете код на С и запустите его со всеми оптимизациями, ты вы удивитесь, какое безумие получится. Godbolt — прекрасный инструмент, позволяющий понять, как современные компиляторы генерируют код и какие инструкции к какому исходному коду относятся. Также вы сможете задать нужный уровень оптимизаций, цели, версии компиляторов и так далее.

Если вы когда либо писали компилятор, то можете начать с создания простой программы на С, выключить все оптимизации и символы отладки (strip the debug symbols), и посмотрите, что сгенерирует GCC. Можете потом использовать как памятку, если когда-нибудь возникнут затруднения.

При настройке оптимизаций можно находить компромисс между точностью и скоростью работы программы. Однако нащупать верный баланс не так просто. Некоторые оптимизации очень специфичны, и в некоторых случаях могут приводить к ошибочному результату. По очевидным причинам их не включают в production-компиляторы.

В комментариях к этой статье на другом ресурсе пользователь rwmj заметил, что достаточно всего 8 оптимизирующих проходов, чтобы получить 80% от максимальной производительности вашего компилятора. И все эти оптимизации были описаны в 1971-м! Речь идёт о публикации Грейдона Хоара, вдохновителя Rust.

Промежуточное представление (intermediate representation, IR) не обязательно, но полезно. Вы можете генерировать код из АСД, хотя это может быть довольно утомительно и неаккуратно, а результат сложно будет оптимизировать.

Можно считать IR более высокоуровневым представлением генерируемого кода. Оно должно очень точно отражать то, что представляет, и содержать всю информацию, необходимую для генерирования кода.

Есть конкретные виды IR, или «формы», которые вы можете создать с помощью IR для упрощения оптимизаций. Например, SSA — Static Single Assignment, единственное статическое присваивание, при котором каждая переменная присваивается лишь один раз.

В Go перед генерированием кода строится IR на основе SSA. IR в LLVM основан на SSA, чтобы обеспечить его оптимизации.

Изначально SSA предоставляет несколько оптимизаций, к примеру, подстановка констант (constant propagation), исключение нерабочего кода и (очень важное) распределение регистров.

Распределение регистров

Это не требование для генерирования кода, а оптимизация. Одна абстракция, которую мы считаем данностью, заключается в том, что мы можем определять столько переменных, сколько нужно нашим программам. Однако в ассемблере нам доступно конечное количество регистров (обычно от 16 до 32), которые нужно держать в голове, или мы можем воспользоваться стеком (spill to the stack).

Распределение регистров — это попытка выбрать для конкретной переменной конкретный регистр в определённый момент времени (без перезаписывания других значений). Это гораздо эффективнее использования стека, хотя может повлечь дополнительные расходы, да и компьютер не всегда может вычислить идеальную схему распределения.

Есть несколько алгоритмов распределения регистров:

О чём нужно помнить

О компиляторах написано очень много. Столько, что не поместится ни в одну статью. Я хочу напомнить, или хотя бы упомянуть несколько важных моментов, о которых нужно помнить в ходе ваших будущих проектов.

Искажение имён (Name Mangling)

Если вы генерируете ассемблер-код, в котором на самом деле нет никаких областей видимости или пространств имён, то у вас часто будут возникать конфликты символов. Особенно если ваш язык поддерживает переопределение функций или классов, и тому подобное.

Например, в этом коде (если переменные каким-либо образом не оптимизированы 🙂 ) вам придётся искажать имена этих символов, чтобы в ассемблере они не конфликтовали. Также искажение обычно используется для обозначения типа информации, или оно может содержать информацию о пространстве имён.

Отладочная информация

Инструменты вроде LLDB обычно используют стандарты наподобие DWARF. Одно из замечательных свойств LLVM заключается в том, что благодаря DWARF вы получается относительно простую интеграцию с существующим отладочным GNU-инструментарием. Возможно, вашему языку понадобится отладочный инструмент, и всегда легче использовать готовый, чем писать свой.

Интерфейс внешних функций (Foreign Function Interface, FFI)

Обычно от libc никуда не деться, вам нужно почитать об этой библиотеке и подумать, как встроить её в свой язык. Как вы подключитесь к коду на С, или как вы откроете свой код для С?

Линкер

Компилятор как сервис (CaaS)

Здесь все рассмотренные выше фазы компилятора распределены по API-маршрутам. Это означает, что текстовый редактор может обращаться к Krug-серверу, чтобы тот токенизировал файл и вернул в ответ токены. Кроме того, все маршруты статического анализа открыты, так что применять инструментарий становится проще.

Конечно, у этого подхода есть недостатки, например, задержка при отправке и получении файлов. К тому же многие аспекты архитектуры компилятора нужно переосмыслить, чтобы работать в контексте API-маршрутов.

Мало какие production-компиляторы используются подход CaaS. На память приходит Microsofts Roslyn, хотя я мало знаю об этом компиляторе, так что изучите его самостоятельно. И я могу ошибаться, но, похоже, во многих компиляторах реализован этот подход, но их авторы пишут API-машруты, которые подключаются к существующим компиляторам, например, в Rust есть RLS.

В моём языке Krug — который ещё активно разрабатывается и работает неустойчиво — в компиляторе Caasper используется CaaS-архитектура.

Caasper выполняется локально на вашей машине (или, если захотите, на сервере), а затем фронтенды или клиенты например, krug, взаимодействуют с этим сервисом. Плюс в том, что у вас может быть много реализаций фронтенда, а единственный фронтенд можно загружать (bootstrap) в самом языке, прежде чем переписывать весь компилятор.

Фронтенд для Krug реализован на JavaScript, хотя будут и альтернативные реализации на Go*, а также, надеюсь, на самом Krug. JavaScript был выбран за его доступность, его можно скачать с очень популярными менеджерами пакетов yarn/npm.

* Изначально фронтенд был написан на Go и оказался (ожидаемо) значительно быстрее, чем вариант на JS.

Исходный код компилятора Caasper лежит здесь. В моём личном Github лежит прототип Krug, он написан на D и компилируется в LLVM. Также можете посмотреть демо на моём YouTube-канале.

Руководство по Krug (промежуточное) лежит здесь.

Источник