После написания предыдущей статьи прошло чуть больше года, и пора написать вторую часть, так как здесь есть, о чём рассказать. Главное изменение в языке: в нём теперь есть intermediate representation (IR) и сразу два codegen-а: снова в x86_64 assembly, и в C. В самом же языке почти ничего не изменилось.
Компилятор и главный репозиторий: GitHub
Здесь я напишу о своём личном проекте — компиляторе к C-подобному языку. Я не являюсь профессиональным разработчиком, изучал эту тему почти самостоятельно и не читал никакие книги по написанию компиляторов (но читал по операционным системам).
Документацию к языку и к его стандартной библиотеке Altlib можно найти в репозитории. Реализация (надеюсь) полностью рабочая (по крайней мере, есть немаленький набор тестов).
Есть вспомогательный репозиторий для упрощения установки компилятора и IDE к нему: GitHub
В процессе чтения статьи вы увидите, что я сильно вдохновлялся языком Zig.
Немного теории об assembler-е/машинном коде
Есть регистры: “ячейки” памяти для наиболее быстрого доступа. Их несколько десятков.
Есть стек - доступный для записи отрезок памяти, обычно длинной в мегабайты+. Один из регистров указывает на важную точку в стеке.
Есть инструкции. Они могут в качестве аргументов принимать:
Регистры
Константы
“Effective addresses” - адреса в специфическом формате, например,
[reg + reg * const]
Память процесса состоит из сегментов. У сегментов могут быть права на запись и/или исполнение.
Инструкции, которые выполняет процессор, записаны в каком-то сегменте с правами на исполнение.
Глобальные переменные записаны в каком-то сегменте с правами на запись.
Как генерировался код раньше
Более подробно об этом было написано в предыдущей части. По сути, у меня генерируется “стековая машина”. На каждую вершину синтаксического дерева должен сгенерироваться код, при выполнении которого результат выполнения вершины будет лежать на вершине стека.
Например, генерация сложения у меня выглядит примерно так:
func generate_addition(Node *left, Node *right) { generate_node(left); output_asm("add rsp, -8"); // Чтобы результат вычисления первого аргумента не затёрся generate_node(right); output_asm("add rsp, +8"); output_asm("mov rax, [rsp - 8]"); // Здесь был сохранён первый аргумент output_asm("add rax, [rsp - 16]"); // Здесь был сохранён второй аргумент, так как стек был сдвинут output_asm("mov [rsp - 8], rax"); // Здесь мы должны сохранить результат }
Особенно интересно выглядит генерация агрегатов, которые были представлены только инстансами (объектами структуры): сначала положить каждое поле на стек с постоянным выравниванием на машинное слово, а затем “спрессовать” их.
Ниже мы узнаем, какое примерно время показывает такая реализация.
Теперь, с появлением нового “нормального” backend-а, этот backend называется x86_64_asm_legacy.
IR - intermediate representation
Базовая информация
Отличия от языка assembler-а следующие:
Регистров нет. Вместо них - бесконечное множество значений (values).
Большинство инструкций не записывают что-либо куда-либо: вместо этого они “возвращают” значение.
Значения не являются переменными (то есть, изменить их нельзя).
Например, там выглядит функция, суммирующая аргументы:
function foo(i32 %0, i32 %1) i32 { .0: %2 := %0 + %1 return %2 }
Значения обозначаются знаком процента %, а блоки точкой ..
Здесь я буду показывать куски IR-кода. Однако я их пишу в llvm-стиле, так как у меня нет вывода IR-а вообще (хотя, результат компиляции в C весьма читаем, и обычно я читал IR с него).
Из базовых инструкций у нас будут следующие:
+,-,*,/и другие арифметические и логические инструкции.Терминаторы - инструкции, завершающие блок. Они не возвращают значения.
br .a- безусловный переход на блок.a.condbr %a, .b, .c- условный переход: если условие%aне ноль, то на блок.b, иначе на блок.c.return %a- возврат из функции со значением%a.
Структура у IR-а следующая:
Есть функции. Они хранят список блоков.
Есть блоки. Они хранят список значений.
Есть значения. Они хранят аргументы, которые являются указателями на другие значения или другие блоки.
Важно: аргументы-блоки я буду рисовать оранжевыми стрелками, а аргументы-блоки у phi-nodes не буду рисовать, чтобы не загромождать рисунок.
Если сравнить IR с AST, то первый является “сплющенной” и обратно упорядоченной версией второго (то есть, в AST сложение является родителем операндов, а в IR-е сложение идёт после вычисления операндов в списке).
Вообще, если использовать goto без ограничений, то даже определение того, точно ли переменная будет объявлена до использования, не является очевидной задачей. (Я потыкал некоторые компиляторы, и они если я объявлял переменную “ниже” в коде, но использовал goto так, что точка объявления точно проходила, то получал ошибку на фронтенде. Интересно, насколько много свободы они дают при использовании goto.) В моём случае goto отсутствует, и потому возможные формы IR-а весьма ограниченны. И эта форма будет использована для, по сути, единственного псевдо-pass-а, о котором будет написано ниже.
Почему в IR-ах значения не являются переменными (такие IR-ы называются single static assignment (SSA) и такими они стали не сразу)? Для облегчения выполнения преобразований. Менять код, в котором значения меняются, очень сложно, так как есть очень много инвариантов, которые можно случайно сломать. В случае же неизменных значений, значение почти (так как есть, например, терминаторы) изоморфно инструкции, и в такой ситуации сломать почти нечего.
Пока у меня полноценных оптимизационных обходов (pass-ов) нет.
Как имитировать переменные
Для имитации работы с переменными есть две “структуры”:
Инструкции
alloca/load/store:alloca- аллоцирует место на стеке и возвращает указатель на него.load- разыменовывает указатель и возвращает его содержимое.store- сохраняет по первому аргументу указателю значение второго аргумента. Не возвращает значение.
phi-nodes - о них ниже.
Пусть мы хотим написать функцию, которая, в зависимости от значения первого аргумента, записывает по адресу второго аргумента разную константу.
void foo(int a, int *b) { if (a) { *b = a; } else { *b = 1; } }
alloca/load/store
Так это можно сделать первым способом. По сути, мы имитируем переменные ячейками, выделяемыми инструкцией alloca.
function foo(i32 %0, i32* %1) void { .0: %2 := alloca, i32 // "Аллоцировали" ячейку на стеке condbr %0, .1, .2 .1 store %2, %0 // Загрузили в ячейку число br .3 .2 store %2, 1 br .3 .3 %3 := load %2 // Достали из ячейки число store %1, %3 return }
Часто в IR-ах alloca не лежат в списках инструкций в блоках, а лежат в отдельных списках в функциях.
phi-nodes
Так это можно сделать вторым способом.
function foo(i32 %0, i32* %1) void { .0: condbr %0, .1, .2 .1 br .3 .2 br .3 .3 %2 := phi [%0, .1], [1, .2] // Если пришли из блока .1, то получаем значение %0. Если пришли из блока .2, то получаем значение 1. store %1, %2 return }
В отличии от всех других инструкций, phi-инструкция не генерирует код в месте, где она написана. Она генерирует код в самом конце блоков-источников перед прыжками: в данном случае, перед обеими инструкциями br .3. Более того, эта инструкция, как бы, не включена в последовательность инструкций в блоке (так как в этом нет смысла), она находится в отдельном списке в контексте блока. (А в некоторых IR-ах такие инструкции вообще лежат на рёбрах.)
Какой способ лучше
Работать с результатами alloca, как с регистрами, сложно, так как значение меняется, а это, как было сказано ранее, усложняет все дальнейшие алгоритмы. (В случае взятия адреса переменной &, необходимо разместить её на стек, и эти рассуждения не имеют смысла.) В случае же с phi-nodes, нет проблем всё держать в регистрах.
Поэтому alloca пытаются переписывать в phi-nodes. Для этого используются преобразования, которые называются mem-to-reg (mem2reg).
В то же время писать код через phi-nodes вручную весьма сложно (если мы генерируем IR вручную, как, например, при JIT-компиляции), и гораздо легче видеть в коде обычные “переменные”.
Как генерировать IR
Главная проблема в генерации IR-а - генерация phi-nodes для переменных. Я их генерирую одним проходом за O(количество переменных * количество блоков) (поэтому, лучше иметь много мелких функций, чем одну большую), и “алгоритм” непростой.
Начнём с генерации control flow-структур. Генерация идёт линейно. В каждый момент времени есть “текущий” блок и список инструкций в нём.
Block
Важно: не путать блок в контексте синтаксического дерева и блок в контексте IR-а.
Итак, есть текущий блок с некоторым множеством инструкций. В данном языке блок возвращает значение, и точек возврата может быть много. Значит, на конце блока должна быть phi-node, и каждый return (да, это ключевое слово делает возврат из блока, а не функции) должен класть свой аргумент и текущий IR-блок в список аргументов этой phi-node.
Логика генерации примерно такая:
void generate_block(IRBuilder *builder, ASTBlock *block) { IRBlock *block = create_block(builder); // Новый блок, в который будут вести все return. IRPhi *phi = create_phi(builder, block); // Создаём phi-node в новом блоке. Но пока этот блок не выбираем. push_phi(builder, block, phi, block->label); // Сохраняем phi-node и её блок в некий стек, по которому находящиеся в блоке return-ы будут её находить. for (ASTStatement *stmt : block) { generate_node(builder, stmt); } pop_phi(builder); // Если блок возвращает void, то здесь нужно сгенерировать безусловный прыжок, а phi-node не нужен вообще. Но этот отдельный случай показывать не будем. set_block(builder, block); // И теперь выбираем новый блок, в который будут генерироваться следующие инструкции. }
void generate_return(IRBuilder *builder, ASTReturn *return) { IRBlock *block, IRPhi *phi = find_phi(builder, return->label); // Находим соответствующую phi-node. vector_push(phi->blocks, builder->current_block); // Кладём в её аргументы текущий блок. vector_push(phi->values, generate(builder, return->value)); // И аргумент return-а. IRBr *br = create_br(builder, builder->current_block, block); // Генерируем безусловный прыжок на блок, в котором лежит phi-node. }
Поясняющая картинка.
Сгенерировали
phi-node в отдельном блоке.Вызвали генерацию вершин-детей в AST-блоке. Там нашлась вершина
return, которая сгенерировала инструкциюbr. Добавились взаимосвязи:brсодержит аргументом блок сphi, аphiсодержит аргументами блок сbr, и возвращённое значение.Продолжили генерацию вершин-детей в AST-блоке. Сгенерировался ещё один
return.
Пример (увы, так как мы пока не видели ветвления, очень глупый).
func foo(a #I) -> #V { def b := { def c := a + 2 return c } ... }
function foo(i32 %0) void { .0 %1 := %0 + 2 br .1 .1 %2 := phi [%1, .0] ... }
If/else
Снова в этом языке if возвращает значение, а значит на его конце должна быть phi-node. Логика здесь такая же, как и в случае с блоком, поэтому ограничимся картинкой.
Вызвали генерацию вершины-условия в AST.
Сгенерировали инструкцию
condbr. Также, по аналогии с блоком в предыдущем пункте, создалиphi.Сгенерировали вершину
thenв AST. Положили последнюю инструкцию и текущий блок в аргументы кphi-node.Сгенерировали вершину
elseв AST. Положили последнюю инструкцию и текущий блок в аргументы кphi-node.
Пример.
func foo(a #I) -> #V { def b := if (a - 3) { def c := a + 2 return c } else 7 ... }
function foo(i32 %0) void { .0 %1 := %0 - 3 condbr %1, .1, .3 .1 %2 := %0 + 2 br .2 .2 %3 := phi [%2, .1] // Это phi и блок сгенерировала функция generate_block. br .4 .3 br .4 .4 %3 := phi [%3, .2], [7, .3] // В качестве значений могут быть и константы. Они не привязаны к структуре и "висят в воздухе". ... }
Переменные
С циклами повременим, так как там самое страшное. Для начала нужно разобраться с переменными и научиться генерировать для них phi-nodes.
Делаем это так. Для каждого блока для каждой переменной храним соответствующее ей значение. При присваивании значение у переменной в блоке меняется, но не меняется в параллельном блоке.
func foo(a #I) -> #V { b := 0 // a :: Arg(0), b :: Const(0) eval if (a) { b := 1 // a :: Arg(0), b :: Const(1) } else { b := a + 1 // a :: Arg(0), b :: Addition(Arg(0), Const(1)) } // ??? ... }
В этом коде в каждом блоке я написал сопоставление переменная :: значение (надо ещё не забыть о том, что переменные могут иметь одинаковое имя). Когда мы генерируем if, мы сначала генерируем его ветви, а затем переходим в новый блок, где появляется возможная phi-node от if-а (но в данном примере он void) и где появляются phi-nodes от переменных.
Смотрим на два предшествующих блока и видим, что переменной a соответствует одно значение Arg(0). А вот переменной b - два разных значения. А значит, нужно для неё сделать phi-node. Поэтому вместо ??? у нас появляется следующее.
%x := phi [Const(1), ...], [Addition(...), ...] ... // a :: Arg(0), b :: %x
Обозначения здесь очень схематические и перемешанные. Но, думаю, дублировать всё IR-ом было бы не лучше.
Нужно отметить, что присваивания не заканчивают блок, а значит по мере генерации блока сопоставление переменная :: значение меняется. Здесь я писал его таким, каким оно является в конце блока, после генерации всех присваиваний.
While
Итак, мы не знаем наперёд, какие переменные изменятся и на что. Поэтому построим по phi-node для каждой переменной, предварительно объявив новый блок. Первым источником этих phi-nodes будет последний блок и значения переменных в нём. Вторым источником у phi-nodes будет блок, полученный после генерации тела цикла, и значения переменных в нём.
Пример.
func foo(a #I) -> #V { def b := 0 eval while (b < a) { b := b + a } ... }
function foo(i32 %0) void { .0 br .1 .1 %1 := phi [%0, .0], [%1, .2] %2 := phi [0, .0], [%4, .2] %3 := %2 < %0 condbr %3, .2, .3 .2 %4 := %2 + %1 br .1 .3 ... }
Здесь мы видим, что для переменной, которая не поменялась, появилась бессмысленная phi-node.
Решение проблемы довольно очевидно: удалить phi-node (а точнее, сделать её no-op), если в результате значение переменной не изменилось. Вместе с этим нужно также изменить места, где она использовалась как аргумент, записав там адрес старого значения (то есть, заменить %4 := %2 + %1 на %4 := %2 + %0), что несколько больно.
Условие удаления также может транзитивно передаться из вложенных блоков: если phi-node была удалена из внутреннего цикла и заменена, то в конец блока внешнего цикла она также дойдёт в оригинальном виде, поэтому и там будет удалена. (Что, конечно, не было бы верным, если бы были goto.)
Небольшой вопрос, ответ на который будет позже: если мы представляем lifetime значение лишь отрезком, то какой он будет у переменной, которая как-либо пересекалась с циклом?
Немного для понимания: так выглядит IR абстрактной большой функции. Но для простоты картинки я нарисовал не цикл while, а цикл do while (в первом присутствует слишком длинная стрелка направо).
Генерация C
Первой была написана генерация кода на C. Здесь проблем особо нет, и, как и было написано выше, это практически просто вывод IR-а.
Чтобы не было проблем с порядком объявления переменных, я их просто объявляю в самом начале функции. Никаких if/while не генерируется - вместо них goto (кажется, я в первый раз писал этот keyword (хотя нет, я лишь написал код, который его генерирует: моя совесть по-прежнему чиста)). При генерации alloca создаётся массив, а самому значению присваивается указатель на него. (Кстати, тот факт, что массив в C неявно преобразуется в указатель, немного попутало меня в процессе. У себя я сделал типизацию у массива как в Zig-е).
Единственной проблемой была типизация, так как компилятор меня заставлял указывать типы явно, поэтому пришлось их корректно генерировать. Но, с другой стороны, это дало читаемость.
Генерация x86_64
Как и ранее, я генерирую язык ассемблера, а не объектный файл, но здесь есть *, о которой позже.
Основная проблема - это вариативность расположения значений. Они могут быть на стеке, как и в старом backend-е, а могут быть в регистре.
Regalloc
Сейчас алгоритм regalloc-а (аллокации регистров) глупый и работает следующим образом.
Все значения делятся на две группы: те, которые живут в регистре (для простоты используются те регистры, которые не используются в инструкциях), и те, которые живут на стеке.
У каждого значения есть свой lifetime (время жизни). Так как мой IR “сплющенный”, можно представлять lifetime, как отрезок. В каждой точке каждый регистр соответствует только одному значению, и это распределение идёт жадно: в первую очередь регистры получают значения с максимальным количеством инструкций, которые их содержат как аргументы.
Псевдокод этого алгоритма такой.
void regalloc(IRBuilder *builder) { int cnt_blocks = vector_size(builder->blocks); Vector *registers_used = vector_create(cnt_blocks); // Создаёт вектор заданной длины из нулей. VectorPairs *instructions = vector_pairs_create(0); // Создаёт вектор пар. for (IRBlock *block : builder->blocks) { for (IRValue *value : block->values) { vector_pairs_push(-vector_size(value->uses), value); // value->uses - вектор значений, которые содержат value, как аргумент. } } vector_pairs_sort(instructions); for (IRValue *value : vector_pairs_second(instructions)) { int left = value->lifetime_left; // Индекс блока. int right = value->lifetime_right; int mask_free = ~0; // Изначально все регистры свободны. for (int i = left; i <= right; i++) { mask_free &= ~registers_used[i]; // Выключаем все использованные регистры на отрезке lifetime. } if (mask_free) { // Есть свободный регистр на всём отрезке - возьмём его. int idx = __builtin_ctz(mask_free); assign_reg(value, idx); for (int i = left; i <= right; i++) { registers_uses[i] |= (1 << idx); } } } }
Для работы же со значениями, живущими на стеке, есть набор функций (которые для значений, живущих в регистре, ничего не делают):
Занять регистр - значению будет сопоставлен регистр.
Переместить в регистр - то же самое, дополнительно будет сгенерирована инструкция, перемещающая значение со стека в регистр.
Освободить регистр - значение будет отвязано от регистра.
Убрать из регистра - то же самое, дополнительно будет сгенерирована инструкция, перемещающая значение из регистра в стек.
Например, генерация значение-сложения и значения-равенства будет выглядеть примерно так.
void codegen_addition(IRAddition *node) { // У инструкций mov и add хотя бы один аргумент должен быть регистром (в общем случае). Пусть это будет выходное значение. occupy_reg(node->reg); output_asm("mov ", node->reg, ", ", position(node->left)); // Пусть position проверяет положение значения и возвращает её регистр или effective address. output_asm("add ", node->reg, ", ", position(node->right)); from_reg(node->reg); // Теперь регистр можно снова использовать. При этом его значение сохранено на стек. }
void codegen_equal(IREqual *node) { output_asm("xor rax, rax"); to_reg(node->left); // На этот раз уберём (а не просто займём) в регистр один из аргументов, так как инструкция cmp тоже требует хотя бы один из аргументов в регистре. output_asm("cmp ", position(node->left), ", ", position(node->right)); free_reg(node->left); // Только освободили регистр. Никаких перемещений не нужно. output_asm("sete rax, 1"); output_asm("mov ", node, ", rax"); }
Как вычислять lifetime
Lifetime - это отрезок инструкций или блоков, в течении которых значение может быть использовано, а значит, регистр, в котором оно живёт, не должен быть использован.
На первый взгляд, чтобы вычислить lifetime, нужно взять самое левое объявление/использование значения и самое правое объявление/использование значения. Но здесь есть исключения.
Если значение является phi-node, то начало его использования это не его объявление, а конец блока-источника, так как там и будет впервые загрузка в регистр этой phi-node.
function foo(i32 %0) { .0 %1 := %0 + 1 condbr %1, .1, .2 .1 %2 := %1 * 2 br .3 /--- %3 lifetime begin .2 | br .3 | .3 | %3 := phi [%2, .1], [5, .2] | %4 := %3 - 7 \--- %3 lifetime end return %4 }
Если значение находится в цикле, то оно должно занимать свой регистр на протяжении всего цикла, чтобы не потерять его на суффиксе цикла после последнего его использования в нём.
function foo(i32 %0) { .0 %1 := %0 + 1 %2 := %0 * 2 /--- %2 lifetime begin br .1 | .1 | %3 := phi [.0, %1], [.2, %5] | condbr %1, .2, .3 | .2 | %4 := %2 + %3 | %5 := %3 - 1 | br .1 \--- %2 lifetime end .3 return %1 }
Performance testing
Для тестирования времени используются следующие шесть способов компиляции. gcc и clang запускаются с -O2.
stdlib- это маленькая стандартная библиотека, написанная на C. Скомпилирована системнымgccс-O0.altlib- это ещё более маленькая стандартная библиотека, написанная на alias-е. Скомпилированаcalias-ом.
Функции, требующие языка ассемблера (например, memcpy) у них общие.
Результаты замеров на моём компьютере сейчас следующие (все числа в секундах).
# | dfs | fft | floyd | merge_sort |
|---|---|---|---|---|
1 | 0.29 | 1.81 | 1.40 | 0.64 |
2 | 0.25 | 1.23 | 0.49 | 0.32 |
3 | 0.21 | 0.58 | 0.09 | 0.18 |
4 | 0.30 | 0.18 | 0.08 | 0.19 |
5 | 0.20 | 0.52 | 0.06 | 0.20 |
6 | 0.28 | 0.18 | 0.06 | 0.20 |
Выводы
Выводы здесь будут краткие. Обычно я изучаю выходной код и смотрю, что компилятор сделал плохо, но здесь я ограничусь лишь одним примером без комментариев.
Тест
fftпоказывает, что мой mem2reg скорее всего плохой, так как портит результаты “нормальных” компиляторов на нём в ~3 раза.В тесте
dfsиз-за линейности алгоритма по большей части замеряется генерация графа. Кроме того, так как в коде на alias-е используется линейный аллокатор, а в коде на C сложный, с возможностью деаллокации, то второй аллокатор скорее медленный, чем сложный.Тест
merge_sortпо большей части показывает более плохой regalloc, так как других недостатков в его выходном коде я не увидел.Тест
floydпросто требует много не очень сложных оптимизаций. Очень часто он просто повторно вычисляет одинаковые значения, значительно увеличивая количество IR-значений, что в добавок ухудшает regalloc.
Так выглядит код функции floyd, сгенерированный gcc.
void floyd(long n, long **a) { for (long k = 0; k < n; k++) { for (long i = 0; i < n; i++) { for (long j = 0; j < n; j++) { long x = a[i][k] + a[k][j]; if (a[i][j] > x) { a[i][j] = x; } } } } }
Подсказка: увидеть переменные i, j, k можно, посмотрев на инструкции cmp.
00000000000011d0 <floyd>: 11d0: f3 0f 1e fa endbr64 11d4: 48 85 ff test %rdi,%rdi 11d7: 7e 66 jle 123f <floyd+0x6f> 11d9: 55 push %rbp 11da: 48 8d 2c fd 00 00 00 lea 0x0(,%rdi,8),%rbp 11e1: 00 11e2: 49 89 f8 mov %rdi,%r8 11e5: 45 31 d2 xor %r10d,%r10d 11e8: 53 push %rbx 11e9: 4c 8d 5c 35 00 lea 0x0(%rbp,%rsi,1),%r11 11ee: 48 89 f3 mov %rsi,%rbx 11f1: 0f 1f 80 00 00 00 00 nopl 0x0(%rax) 11f8: 4a 8b 3c 13 mov (%rbx,%r10,1),%rdi 11fc: 49 89 d9 mov %rbx,%r9 11ff: 90 nop 1200: 49 8b 09 mov (%r9),%rcx 1203: 31 c0 xor %eax,%eax 1205: 4a 8d 34 11 lea (%rcx,%r10,1),%rsi 1209: 0f 1f 80 00 00 00 00 nopl 0x0(%rax) 1210: 48 8b 14 c7 mov (%rdi,%rax,8),%rdx 1214: 48 03 16 add (%rsi),%rdx 1217: 48 39 14 c1 cmp %rdx,(%rcx,%rax,8) 121b: 7e 04 jle 1221 <floyd+0x51> 121d: 48 89 14 c1 mov %rdx,(%rcx,%rax,8) 1221: 48 83 c0 01 add $0x1,%rax 1225: 49 39 c0 cmp %rax,%r8 1228: 75 e6 jne 1210 <floyd+0x40> 122a: 49 83 c1 08 add $0x8,%r9 122e: 4d 39 cb cmp %r9,%r11 1231: 75 cd jne 1200 <floyd+0x30> 1233: 49 83 c2 08 add $0x8,%r10 1237: 4c 39 d5 cmp %r10,%rbp 123a: 75 bc jne 11f8 <floyd+0x28> 123c: 5b pop %rbx 123d: 5d pop %rbp 123e: c3 ret 123f: c3 ret
Генерация AST
Так можно сгенерировать AST (можно генерировать и IR, но там нужен IRBuilder и всё значительно больнее) в отдельной программе на C, которое затем можно скомпилировать в объектный файл.
int main() { struct Node *tree = create_module(vector(1, create_function_definition( NULL, "foo", create_function_signature( vector(2, "a", "b" ), vector(2, create_type_int(0), create_type_int(0) ), create_type_int(0) ), create_binary_operator( NodeAddition, create_identifier("a", false), create_identifier("b", false) ), true, false ) )); struct Settings *settings = _malloc(sizeof(struct Settings)); settings->testing = false; settings->filename_compile_output = "a.out"; compile_process(tree, settings); return 0; }
Здесь интересно то, что генерация такого дерева и сам mem2reg довольно дёшевы, и можно делать JIT-компиляцию, генерируя не IR со значениями-константами и phi-nodes, а AST с нормальными переменными.
JIT-компиляция
Как выполнить JIT-компиляцию?
Попросить у ОС сегмент для записи с помощью системного вызова
mmap.Вывести в этот сегмент код. Он должен быть position independent (PIC) - все инструкции, использующие глобальные значения, должны использовать их по относительным адресам.
Сделать сегмент исполняемым с помощью системного вызова
mprotect.
Чтобы выполнить сгенерированный код, его необходимо ассемблировать (обычные ассемблеры не очень пригодны для этого, так как слишком медленные и обычно генерируют машинный код в файлы), и я попробовал это сделать с помощью fadec-а. Я пока не решил, добавлю ли я его в зависимости, или нет, поэтому этого кода в публичном репозитории нет.
Смысл такой компиляции - расположение “констант относительно генерируемого кода” не как значений, а как immediate arguments в инструкциях.
Например, пусть есть функция.
foo: mov rax, rdi add rax, [boo] ret
Если известно, что переменная boo в процессе вызовов функции foo не будет менятся, можно скомпилировать такой код.
foo: lea rax, [rdi + 0x43215] ; boo = 0x43215 ret
Более глобальный пример, это интерпретатор, где для программы для интерпретатора можно сгенерировать код, избавившись от диспетчеризации (switch-case) инструкций.
Что дальше?
Чуть позже я обозначу текущее состояние компилятора как версию 0.2.
Скорее всего, следующей целью у меня будут:
Управляемые и как можно более лёгкие оптимизационные обходы.
Усложнённые типы (можно заметить, сгенерировав code coverage, что в файле
type.cв принципе исполняется не весь код, и текущее состояние типов плохое).comptime.