Средний

15 мин

658

Часть 1

После написания предыдущей статьи прошло чуть больше года, и пора написать вторую часть, так как здесь есть, о чём рассказать. Главное изменение в языке: в нём теперь есть 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.
}

Поясняющая картинка.

1. Сгенерировали phi-node в отдельном блоке.

2. Вызвали генерацию вершин-детей в AST-блоке. Там нашлась вершина return, которая сгенерировала инструкцию br. Добавились взаимосвязи: br содержит аргументом блок с phi, а phi содержит аргументами блок с br, и возвращённое значение.

3. Продолжили генерацию вершин-детей в 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. Логика здесь такая же, как и в случае с блоком, поэтому ограничимся картинкой.

1. Вызвали генерацию вершины-условия в AST.

2. Сгенерировали инструкцию condbr. Также, по аналогии с блоком в предыдущем пункте, создали phi.

3. Сгенерировали вершину then в AST. Положили последнюю инструкцию и текущий блок в аргументы к phi-node.

4. Сгенерировали вершину 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) у них общие.

Результаты замеров на моём компьютере сейчас следующие (все числа в секундах).

Выводы

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

1. Тест fft показывает, что мой mem2reg скорее всего плохой, так как портит результаты “нормальных” компиляторов на нём в ~3 раза.

2. В тесте dfs из-за линейности алгоритма по большей части замеряется генерация графа. Кроме того, так как в коде на alias-е используется линейный аллокатор, а в коде на C сложный, с возможностью деаллокации, то второй аллокатор скорее медленный, чем сложный.

3. Тест merge_sort по большей части показывает более плохой regalloc, так как других недостатков в его выходном коде я не увидел.

4. Тест 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-компиляцию?

1. Попросить у ОС сегмент для записи с помощью системного вызова mmap.

2. Вывести в этот сегмент код. Он должен быть position independent (PIC) - все инструкции, использующие глобальные значения, должны использовать их по относительным адресам.

3. Сделать сегмент исполняемым с помощью системного вызова 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.

Скорее всего, следующей целью у меня будут:

1. Управляемые и как можно более лёгкие оптимизационные обходы.

2. Усложнённые типы (можно заметить, сгенерировав code coverage, что в файле type.c в принципе исполняется не весь код, и текущее состояние типов плохое).

3. comptime.