Раздел 32 · Системное программирование: Zig, ассемблер, Verilog

JIT: пишем машинный код x86-64

lead~160 мин

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

JIT: пишем машинный код x86-64

Десять уроков подряд ты читал машинный код: брал вывод компилятора, разбирал префикс REX, считал поля ModRM, восстанавливал по смещению перехода границы цикла. Сегодня стрелка разворачивается. Ты напишешь функцию, которая берёт дерево выражения и выдаёт байты x86-64, положишь эти байты в память, у которой есть право на исполнение, и прыгнешь в них. Программа, которой не было в момент компиляции твоей программы, начнёт работать внутри неё как обычная функция.

Цели урока

Понимать, что делает JIT, и чем он отличается и от интерпретатора, и от обычного компилятора.
Зафиксировать представление значений в одно машинное слово: ноль это пустой список, число это сдвиг с единицей в младшем бите, пара это указатель с нулевым тегом.
Собрать энкодер подмножества x86-64: movabs, пересылки между регистром и слотом кадра, чтение слова со смещением, push, call по регистру, cmp, je и jmp с относительным смещением.
Написать пролог и эпилог рукописной функции так, чтобы соглашение System V выполнялось: кадр кратен шестнадцати, callee-saved регистры возвращены нетронутыми.
Превращать каждый узел дерева в короткий шаблон инструкций и понимать, почему шаблоны стыкуются без переговоров: результат всегда оказывается в одном и том же регистре.
Закрывать переход, чья цель ещё не уложена в буфер, обратной заплаткой по запомненному месту.
Компилировать хвостовой вызов в jmp и объяснять, почему это превращает бесконечную рекурсию в цикл, который не съедает стек.
Просить у ядра память с правом на исполнение, знать про правило W^X и про то, чем за него платят на разных системах.
Проверять кодогенератор так, как проверяют компиляторы: каждая программа считается двумя способами, и ответы обязаны совпасть.
Встроить JIT в zl четвёртым исполнителем: спустить тело lambda из ячеек кучи в дерево, решить один раз на функцию, брать её или отдать байткоду.

Идея: третий способ выполнить программу

У программы, которая исполняет чужой код, есть три пути.

Обход дерева. Ты его уже написал: eval берёт узел, смотрит на его вид и рекурсивно считает потомков. Просто, читаемо, и медленно, потому что на каждое сложение приходится разбор вида узла, переход по указателю и вызов функции.

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

Машинный код. Диспетчеризации нет вообще. Сложение в программе становится инструкцией сложения в процессоре, ветка становится переходом, вызов становится call. Цену платит компилятор, и платит один раз.

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

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

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

Значение в одно слово

Кодогенератор не может работать со значением, которое занимает шестнадцать байт и состоит из тега и полезной нагрузки. Каждое такое значение это две пересылки вместо одной, а каждая проверка вида это чтение из памяти. Поэтому значение уже сжато до одного машинного слова, а вид спрятан в младшие биты: это сделал шаг проекта в уроке про массивы, структуры и выравнивание. Приём называется тегированным указателем. JIT этого урока описывает то же слово своим типом u64 и тремя функциями: для nil, чисел и пар биты у него те же, что в value.zig.

Договорённость короткая, и весь машинный код урока стоит на ней.

Что	Как выглядит слово	Почему так
`nil`	ровно ноль	проверка на ложь это сравнение с нулём, самая дешёвая проверка на свете
число	`n << 3` и единица в младшем бите	младший бит отличает число от любого указателя
пара	адрес ячейки, младшие четыре бита нулевые	ячейка выровнена на шестнадцать, поэтому тег уже нулевой, и снимать нечего

Смотри, что даёт третья строка. Значение пары это буквально адрес двух слов подряд. Значит car это чтение по нулевому смещению от этого адреса, а cdr чтение по смещению восемь. Ни одной инструкции на снятие тега. Ноль под nil даёт то же самое с другой стороны: проверка условия в cond это одна инструкция cmp с нулём, а не разбор поля.

Числа платят за это тремя битами разрядности и сдвигом при арифметике, но платят не всегда: прибавить единицу к тегированному числу это прибавить восемь, потому что единица в сдвинутом виде и есть восемь.

// examples/our-zlisp/src/jit.zig

/// Значение в одно машинное слово.
pub const Value = u64;

/// Сколько младших бит отдано под тег.
pub const tag_bits = 3;

/// Пустой список, он же ложь.
pub const nil: Value = 0;

/// Число в тегированном виде: сдвиг на три бита и единица в младшем.
pub fn fixnum(n: i64) Value {
    return (@as(Value, @bitCast(n)) << tag_bits) | 1;
}

/// Обратно из тегированного вида. Сдвиг арифметический, поэтому
/// отрицательные числа переживают дорогу туда и обратно.
pub fn fixnumOf(v: Value) i64 {
    return @as(i64, @bitCast(v)) >> tag_bits;
}

pub fn isFixnum(v: Value) bool {
    return v & 1 == 1;
}

/// Тегированная единица: то, что прибавляют и вычитают прямо в тегированном
/// виде, не разбирая число. Единица со сдвигом это `1 << 3`, то есть восемь.
pub const fixnum_one_step: i8 = 1 << tag_bits;

/// Пара: два слова подряд, та же раскладка, что у `value.Cell`. Адрес выровнен
/// на шестнадцать, значит младшие четыре бита нулевые, значит указатель на
/// пару и есть готовое значение с тегом cons.
pub const Pair = extern struct {
    car: Value align(16),
    cdr: Value,
};

pub fn pairValue(pair: *const Pair) Value {
    return @intFromPtr(pair);
}

pub fn pairOf(v: Value) *Pair {
    return @ptrFromInt(v);
}

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

И extern struct не для красоты. Обычной структуре Zig не обещает раскладку в памяти и волен переставить поля. Наш машинный код читает cdr по жёстко зашитому смещению восемь, значит раскладка обязана быть той, что записана в объявлении, а это и есть обещание extern struct (об этом был весь разговор в уроке про массивы, структуры и выравнивание).

Контракт скомпилированной функции

Теперь второй контракт: как выглядит снаружи то, что мы породим.

Тело lambda от одного аргумента компилируется в функцию с обычным соглашением C:

pub const Body = *const fn (*Vm, Value) callconv(.c) Value;

Отсюда следует всё остальное. Машина приезжает в %rdi, аргумент в %rsi, результат уходит в %rax. Свои соглашения JIT не изобретает, и это не лень, а расчёт: раз скомпилированный код говорит на языке ABI, его можно позвать из Zig как обычную функцию, а он может позвать примитив, написанный на Zig, тоже как обычную функцию. Граница между «нашим» и «сгенерированным» кодом исчезает, и её не надо охранять.

Примитивы у нас двухаргументные и тоже с соглашением C:

/// Примитив, который зовёт скомпилированный код: машина первым аргументом,
/// два уже вычисленных значения дальше, всё по соглашению C.
pub const Prim2 = *const fn (*Vm, Value, Value) callconv(.c) Value;

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

Дерево, которое мы умеем компилировать, ровно такое, какое нужно одноаргументной lambda, и ни одного узла сверх:

/// Вызов примитива с двумя аргументами.
pub const Call = struct {
    prim: Prim2,
    a: *const Expr,
    b: *const Expr,
};

/// Развилка: одна проверка, две ветки. Больше веток это вложенные `cond`.
pub const Cond = struct {
    check: *const Expr,
    on_true: *const Expr,
    on_false: *const Expr,
};

/// Дерево, которое умеет компилировать этот JIT. Ровно те узлы, что нужны
/// одноаргументной `lambda`, и ни одного лишнего.
pub const Expr = union(enum) {
    /// Числовая константа.
    fixnum: i64,
    /// Аргумент `lambda`.
    param,
    /// Голова пары.
    car: *const Expr,
    /// Хвост пары.
    cdr: *const Expr,
    /// Вызов примитива.
    call: Call,
    /// Развилка.
    cond: Cond,
    /// Хвостовой вызов самой себя с новым аргументом.
    tail: *const Expr,
};

Семь видов узлов, семь шаблонов инструкций. Всё остальное в уроке это обвязка вокруг этих семи.

Энкодер: мнемоника на входе, байты на выходе

Начинаем с самого низа. Энкодер ничего не знает ни про лисп, ни про значения: у него на входе регистр и число, на выходе байты. Из-за этого его можно проверять тестами на любой машине. Чтобы убедиться, что 48 8b 45 f8 это mov -8(%rbp), %rax, процессор x86-64 не нужен, нужна таблица кодировок.

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

// examples/our-zlisp/src/x86.zig

/// Регистры общего назначения в порядке их номеров в кодировке инструкций.
/// Младшие три бита номера идут в поле reg или rm байта ModRM (а у `push`,
/// `pop` и `movabs` прямо в opcode), четвёртый бит поднимает R или B в REX.
pub const Reg = enum(u4) {
    rax = 0,
    rcx = 1,
    rdx = 2,
    rbx = 3,
    rsp = 4,
    rbp = 5,
    rsi = 6,
    rdi = 7,
    r8 = 8,
    r9 = 9,
    r10 = 10,
    r11 = 11,
    r12 = 12,
    r13 = 13,
    r14 = 14,
    r15 = 15,

    /// Младшие три бита номера: попадают в opcode или в поле rm/reg байта ModRM.
    pub fn low3(self: Reg) u3 {
        return @truncate(@intFromEnum(self));
    }

    /// Нужен ли расширяющий бит REX (номера с восьмого по пятнадцатый).
    pub fn extended(self: Reg) bool {
        return @intFromEnum(self) >= 8;
    }
};

Порядок в перечислении не алфавитный и не по красоте: он такой, каким его задали в 8086 и достроили в AMD64. Именно поэтому %rsp имеет номер четыре, а %rbp пять, и именно поэтому у них дальше будет особая роль в адресации.

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

pub const Buf = struct {
    pub const capacity = 1024;

    bytes: [capacity]u8 = undefined,
    len: usize = 0,

    /// Готовые байты кода.
    pub fn slice(self: *const Buf) []const u8 {
        return self.bytes[0..self.len];
    }

    /// Дописать один байт в конец.
    pub fn emit(self: *Buf, byte: u8) void {
        std.debug.assert(self.len < capacity);
        self.bytes[self.len] = byte;
        self.len += 1;
    }

    /// Дописать значение как little-endian по его ширине.
    pub fn emitInt(self: *Buf, comptime T: type, value: T) void {
        var tmp: [@sizeOf(T)]u8 = undefined;
        std.mem.writeInt(T, &tmp, value, .little);
        for (tmp) |byte| self.emit(byte);
    }

    /// Переписать четыре байта на уже занятом месте: это и есть заплатка
    /// перехода, чьё смещение стало известно только сейчас.
    pub fn patchInt(self: *Buf, at: usize, value: i32) void {
        std.debug.assert(at + 4 <= self.len);
        std.mem.writeInt(i32, self.bytes[at..][0..4], value, .little);
    }
};

Три метода на всё. emit пишет байт, emitInt раскладывает число младшим байтом вперёд, patchInt переписывает четыре байта там, где они уже лежат. Последний нужен только для одного, для перехода, чья цель стала известна позже, чем сама инструкция. Дойдём до него в разделе про cond.

Дальше два помощника, которые собирают служебные байты. Оба разбирались в уроке про операнды и mov, здесь они просто записаны кодом.

/// Префикс REX это байт `0100WRXB`. W делает операцию 64-битной, R расширяет
/// поле reg байта ModRM, X расширяет индекс в байте SIB (нам не нужен),
/// B расширяет поле rm или номер регистра, зашитый прямо в opcode.
fn rex(w: bool, r: bool, x: bool, b: bool) u8 {
    return 0x40 |
        (@as(u8, @intFromBool(w)) << 3) |
        (@as(u8, @intFromBool(r)) << 2) |
        (@as(u8, @intFromBool(x)) << 1) |
        @as(u8, @intFromBool(b));
}

/// Байт ModRM: два бита режима, три бита поля reg, три бита поля rm.
/// В инструкциях с расширением opcode (`/2`, `/5`, `/7`) в поле reg лежит не
/// регистр, а цифра расширения.
fn modrm(mod: u2, reg: u3, rm: u3) u8 {
    return (@as(u8, mod) << 6) | (@as(u8, reg) << 3) | @as(u8, rm);
}

Теперь сами инструкции. Их девять, и это весь набор, из которого JIT собирает любую программу.

/// `movabs $imm64, dst`: единственный способ положить в регистр произвольное
/// 64-битное число, включая адрес функции. REX.W, opcode `0xB8` плюс младшие
/// три бита регистра, затем восемь байт значения младшим вперёд.
pub fn movImm64(buf: *Buf, dst: Reg, imm: u64) void {
    buf.emit(rex(true, false, false, dst.extended()));
    buf.emit(0xB8 + @as(u8, dst.low3()));
    buf.emitInt(u64, imm);
}

/// `mov src, dst`, оба операнда регистры: REX.W, opcode `0x89`, ModRM с
/// `mod = 11`, источник в поле reg, приёмник в поле rm.
pub fn movRegReg(buf: *Buf, dst: Reg, src: Reg) void {
    buf.emit(rex(true, src.extended(), false, dst.extended()));
    buf.emit(0x89);
    buf.emit(modrm(0b11, src.low3(), dst.low3()));
}

/// `mov disp(base), dst`: чтение слова из памяти со смещением в один байт.
/// Смещение пишется всегда, даже нулевое: так длина инструкции не зависит
/// от значения, и это удобно, когда байты уже уложены и их правят заплаткой.
pub fn movLoad(buf: *Buf, dst: Reg, base: Reg, disp: i8) void {
    assertBase(base);
    buf.emit(rex(true, dst.extended(), false, base.extended()));
    buf.emit(0x8B);
    buf.emit(modrm(0b01, dst.low3(), base.low3()));
    buf.emitInt(i8, disp);
}

/// `mov src, disp(base)`: запись слова в память со смещением в один байт.
pub fn movStore(buf: *Buf, base: Reg, disp: i8, src: Reg) void {
    assertBase(base);
    buf.emit(rex(true, src.extended(), false, base.extended()));
    buf.emit(0x89);
    buf.emit(modrm(0b01, src.low3(), base.low3()));
    buf.emitInt(i8, disp);
}

Четыре пересылки, и в них спрятаны два решения, о которых стоит сказать вслух.

Первое: movLoad и movStore всегда пишут байт смещения, даже когда оно нулевое. Кодировка с mod = 00 короче на байт, но тогда длина инструкции зависела бы от значения смещения, а нам важнее, чтобы она не зависела ни от чего. Кодогенератор, у которого длина шаблона предсказуема, куда проще того, у которого она плавает.

Второе: базой адресации не бывает %rsp и %r12. Их коды в поле rm заняты под особое значение, они означают «дальше идёт байт SIB», и адресация от них требует лишнего байта. Мы просто запрещаем такую базу проверкой:

/// База адресации с восьмибитным смещением. Коды `rsp` и `r12` в поле rm
/// означают, что дальше идёт байт SIB, поэтому базой они у нас не бывают.
fn assertBase(base: Reg) void {
    std.debug.assert(base != .rsp and base != .r12);
}

Остальные пять инструкций короче.

/// `push reg`: opcode `0x50` плюс младшие три бита. Префикса REX.W нет,
/// в 64-битном режиме `push` и так кладёт на стек восемь байт.
pub fn push(buf: *Buf, reg: Reg) void {
    if (reg.extended()) buf.emit(rex(false, false, false, true));
    buf.emit(0x50 + @as(u8, reg.low3()));
}

/// `pop reg`: opcode `0x58` плюс младшие три бита.
pub fn pop(buf: *Buf, reg: Reg) void {
    if (reg.extended()) buf.emit(rex(false, false, false, true));
    buf.emit(0x58 + @as(u8, reg.low3()));
}

/// `call *reg`: косвенный вызов по адресу в регистре. Opcode `0xFF` с цифрой
/// расширения `/2`, поэтому в поле reg байта ModRM стоит двойка.
pub fn callReg(buf: *Buf, reg: Reg) void {
    if (reg.extended()) buf.emit(rex(false, false, false, true));
    buf.emit(0xFF);
    buf.emit(modrm(0b11, 2, reg.low3()));
}

/// `sub $imm8, dst`: opcode `0x83` с цифрой расширения `/5`, знаковое
/// восьмибитное значение расширяется до 64 бит.
pub fn subImm8(buf: *Buf, dst: Reg, imm: i8) void {
    buf.emit(rex(true, false, false, dst.extended()));
    buf.emit(0x83);
    buf.emit(modrm(0b11, 5, dst.low3()));
    buf.emitInt(i8, imm);
}

/// `cmp $imm8, dst`: тот же opcode `0x83`, цифра расширения `/7`.
/// Выставляет флаги и ничего не пишет.
pub fn cmpImm8(buf: *Buf, dst: Reg, imm: i8) void {
    buf.emit(rex(true, false, false, dst.extended()));
    buf.emit(0x83);
    buf.emit(modrm(0b11, 7, dst.low3()));
    buf.emitInt(i8, imm);
}

Заметь sub и cmp: у них один и тот же opcode 0x83, а различает их цифра в поле reg байта ModRM. Поле, которое обычно указывает регистр, здесь занято под доразбор операции, потому что второй операнд у таких инструкций и так известен, он лежит в самой инструкции. Ровно то же у call *reg: opcode 0xFF обслуживает целое семейство, и /2 выбирает из него косвенный вызов.

Проверяем себя дизассемблером

Кодировку по памяти не выписывают. Её берут из справочника (том 2 руководства Intel или таблицы на felixcloutier), а потом обязательно проверяют в обратную сторону: скармливают полученные байты дизассемблеру и смотрят, что он напечатает. Если напечатал то, что ты имел в виду, кодировка верна. Если напечатал что-то другое или упёрся в непонятный байт, ошибка найдена до того, как процессор попробовал это исполнить.

Так проверены все байты этого урока. Скомпилированное тело для выражения (car (cdr xs)) выглядит вот так:

   0: 55                       push  %rbp
   1: 48 89 e5                 mov   %rsp, %rbp
   4: 48 83 ec 10              sub   $16, %rsp
   8: 48 89 5d f0              mov   %rbx, -16(%rbp)
  12: 48 89 fb                 mov   %rdi, %rbx
  15: 48 89 75 f8              mov   %rsi, -8(%rbp)
  19: 48 8b 45 f8              mov   -8(%rbp), %rax
  23: 48 8b 40 08              mov   8(%rax), %rax
  27: 48 8b 40 00              mov   0(%rax), %rax
  31: 48 8b 5d f0              mov   -16(%rbp), %rbx
  35: c9                       leave
  36: c3                       ret

Тридцать семь байт, из них шесть инструкций пролога и эпилога, и всего две на само выражение: cdr это чтение по смещению восемь, car это чтение по смещению ноль. Ни одной инструкции на разбор тегов, ни одного вызова. Вот ради чего мы сжимали значение до слова.

Пролог, эпилог и раскладка кадра

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

/// Слот кадра под аргумент `lambda`. Первый аргумент приезжает в `%rsi`
/// (в `%rdi` лежит машина) и сразу сгружается сюда: так его адрес не зависит
/// от того, что код успел сделать с регистрами, а хвостовой вызов просто
/// переписывает слот и прыгает на начало тела.
pub const param_slot: i8 = -8;

/// Слот, куда пролог прячет `%rbx`: этот регистр callee-saved, а мы держим
/// в нём указатель на машину, значит обязаны вернуть вызывающему как было.
pub const saved_rbx_slot: i8 = -16;

/// Первый временный слот. Дальше вниз с шагом восемь, по одному на уровень
/// вложенности вызовов примитивов.
pub const first_scratch_slot: i8 = -24;

/// Слот под левый операнд вызова на глубине `depth`.
pub fn scratchSlot(depth: u8) i8 {
    return first_scratch_slot - @as(i8, @intCast(depth)) * 8;
}

/// Размер кадра под `depth` уровней вложенности, округлённый вверх до 16.
/// Кратность шестнадцати не косметика: перед `call` указатель стека обязан
/// быть выровнен на 16 байт, иначе первая же инструкция SSE внутри примитива
/// упадёт.
pub fn frameSize(depth: u8) u8 {
    const need: usize = 16 + @as(usize, depth) * 8;
    return @intCast((need + 15) / 16 * 16);
}

Три решения подряд, и каждое стоит объяснить.

Аргумент живёт в кадре, а не в регистре. Соблазн понятный: аргумент уже приехал в %rsi, оставь его там и читай оттуда. Но %rsi caller-saved, и первый же вызов примитива его затрёт. Держать аргумент в callee-saved регистре можно, но тогда придётся его сохранять и восстанавливать, а слотов всё равно не хватит на вложенные вызовы. Слот кадра решает вопрос раз и навсегда: адрес -8(%rbp) не меняется в течение всего вызова, что бы код ни делал с регистрами.

Указатель на машину живёт в %rbx. Он нужен на каждом вызове примитива и обязан пережить сам вызов, а %rdi, куда его положил вызывающий, caller-saved. Значит нужен callee-saved регистр, и %rbx первый в списке. Но раз он callee-saved, то теперь уже мы обязаны вернуть его вызывающему нетронутым, поэтому пролог прячет старое значение в слот, а эпилог достаёт обратно. Симметрия честная: взял чужое, положи на место.

Кадр кратен шестнадцати. Правило System V: в момент выполнения call значение %rsp обязано делиться на шестнадцать. Разбор был в уроке про процедуры и кадры, а здесь оно превращается в арифметику. Посчитаем. В момент входа в наше тело вызывающий уже положил на стек восьмибайтовый адрес возврата, значит %rsp кратен шестнадцати минус восемь. push %rbp вычитает ещё восемь, и %rsp становится кратен шестнадцати. Дальше sub на размер кадра: если размер кратен шестнадцати, выравнивание сохраняется, и любой call внутри тела законен. Отсюда округление вверх в frameSize, и отсюда же вывод: временные значения надо держать в кадре, а не пихать push, потому что каждый непарный push ломает выравнивание.

Сам пролог после этого пишется в шесть строк:

/// Пролог тела `lambda`. На входе `%rdi` это машина, `%rsi` это аргумент.
/// Возвращает смещение первой инструкции тела: это метка, на которую прыгает
/// хвостовой вызов.
pub fn prologue(buf: *Buf, frame_size: u8) usize {
    push(buf, .rbp);
    movRegReg(buf, .rbp, .rsp);
    subImm8(buf, .rsp, @intCast(frame_size));
    movStore(buf, .rbp, saved_rbx_slot, .rbx);
    movRegReg(buf, .rbx, .rdi);
    movStore(buf, .rbp, param_slot, .rsi);
    return buf.len;
}

/// Эпилог: вернуть `%rbx`, свернуть кадр, отдать результат из `%rax`.
pub fn epilogue(buf: *Buf) void {
    movLoad(buf, .rbx, .rbp, saved_rbx_slot);
    leave(buf);
    ret(buf);
}

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

leave в эпилоге это одна инструкция вместо двух: она копирует %rbp в %rsp и снимает старый %rbp со стека. Именно так сворачивают кадр, когда базовый указатель настроен.

Шаблон на каждый узел

Дальше начинается собственно кодогенерация, и она устроена проще, чем кажется. Правило одно: любой узел оставляет свой результат в %rax. Из этого правила растёт всё остальное. Шаблоны не договариваются между собой, не передают друг другу ничего, кроме этого негласного условия, и потому их можно складывать в любом порядке.

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

Константа

.fixnum => |n| x86.movImm64(buf, .rax, fixnum(n)),

Одна инструкция: movabs с уже тегированным значением. Тегирование делает компилятор, а не сгенерированный код, поэтому во время работы за него не платят ничего. Единица превращается в девятку (1 << 3 плюс единица), десятка в восемьдесят один.

Аргумент

.param => x86.movLoad(buf, .rax, .rbp, x86.param_slot),

Тоже одна инструкция: чтение из своего слота. Хвостовой вызов, который позже перепишет слот, не потребует от этого шаблона ни единой правки.

car и cdr

.car => |inner| {
    self.gen(inner, depth);
    x86.movLoad(buf, .rax, .rax, 0);
},
.cdr => |inner| {
    self.gen(inner, depth);
    x86.movLoad(buf, .rax, .rax, 8);
},

Сначала считаем поддерево (его результат по правилу окажется в %rax), потом читаем слово по смещению от него. Тег нулевой, снимать нечего, значение и есть адрес. Разница между car и cdr ровно в одном байте смещения.

Именно тут окупается решение про тегированные указатели. При значении из двух слов на шестнадцать байт, как до урока про выравнивание, car был бы проверкой тега, переходом и чтением по вычисленному адресу. Здесь одна инструкция.

Обрати внимание, чего в шаблоне нет: проверки, что значение вообще пара. Мы её не генерируем, и это осознанный выбор быстрого пути. Если в car придёт число, машинный код прочитает память по адресу, которого нет, и процесс умрёт. Настоящий JIT ставит перед чтением проверку младших бит, а рядом код, который бросает ошибку, и это ещё три инструкции на каждое обращение. Наш вариант это учебный минимум, и знать про его цену важнее, чем её платить.

Вызов примитива

.call => |call| {
    self.gen(call.a, depth);
    x86.movStore(buf, .rbp, x86.scratchSlot(depth), .rax);
    self.gen(call.b, depth + 1);
    x86.movRegReg(buf, .rdx, .rax);
    x86.movLoad(buf, .rsi, .rbp, x86.scratchSlot(depth));
    x86.movRegReg(buf, .rdi, .rbx);
    x86.movImm64(buf, .rax, @intFromPtr(call.prim));
    x86.callReg(buf, .rax);
},

Читай по шагам. Считаем левый операнд, он оказывается в %rax. Убираем его в свой временный слот, потому что дальше %rax понадобится правому. Считаем правый, он тоже приходит в %rax, и оттуда переезжает в %rdx, второй регистр аргумента примитива. Достаём левый из слота в %rsi. Кладём машину из %rbx в %rdi. Загружаем адрес примитива в %rax через movabs и зовём косвенно.

Три вещи в этом шаблоне заслуживают отдельного взгляда.

Почему слот, а не стек. Убрать левый операнд коротким push и достать pop было бы на четыре байта короче. Но push вычитает восемь из %rsp, и пока правый операнд считается, выравнивание сломано. Если внутри правого операнда есть свой вызов, он попадёт на невыровненный стек, и первая же инструкция SSE в примитиве упадёт. Слот кадра этой проблемы не создаёт: он выделен один раз в прологе, %rsp при этом не двигается вообще.

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

/// Сколько временных слотов нужно дереву. Слот занимает левый операнд вызова,
/// пока считается правый, поэтому глубина растёт только по правой ветке вызова.
pub fn scratchDepth(expr: *const Expr) u8 {
    return switch (expr.*) {
        .fixnum, .param => 0,
        .car, .cdr, .tail => |inner| scratchDepth(inner),
        .call => |call| @max(scratchDepth(call.a), 1 + scratchDepth(call.b)),
        .cond => |cond| @max(
            scratchDepth(cond.check),
            @max(scratchDepth(cond.on_true), scratchDepth(cond.on_false)),
        ),
    };
}

Строка про call тут самая содержательная: единица прибавляется только к правой ветке. Левый операнд к моменту, когда понадобится следующий слот, уже уехал из %rax и отпустил свой уровень. Поэтому выражение вида «вызов, у которого левый операнд тоже вызов» стоит один слот, а «вызов, у которого вызов справа» уже два. Кодогенератор, который считает по-простому, а не по правой ветке, отвёл бы кадр вдвое больше нужного.

Почему адрес через movabs, а не call rel32. Прямой call кодирует цель относительным смещением в тридцать два бита, то есть добивает не дальше чем на два гигабайта от себя. Наш код лежит в свежей странице от ядра, примитив в загруженном образе программы, и расстояние между ними никто не обещал. Поэтому адрес кладётся в регистр целиком, восемью байтами, и вызов идёт по регистру. Такой же приём ты видел бы в любом линкере, когда он ставит переходник для дальнего вызова.

cond и обратная заплатка

.cond => |cond| {
    self.gen(cond.check, depth);
    x86.cmpImm8(buf, .rax, 0);
    const to_else = x86.je32(buf);
    self.gen(cond.on_true, depth);
    const to_end = x86.jmp32(buf);
    x86.patchHere(buf, to_else);
    self.gen(cond.on_false, depth);
    x86.patchHere(buf, to_end);
},

Проверка на ложь это cmp $0, потому что nil у нас ровно ноль. Если равно, прыгаем во вторую ветку. Первая ветка кончается безусловным прыжком за развилку.

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

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

/// Незакрытый переход: где лежат четыре байта смещения и где кончается сама
/// инструкция. Смещение rel32 отсчитывается от конца инструкции, поэтому
/// заплатке нужны оба числа.
pub const Patch = struct {
    at: usize,
    end: usize,
};

/// `je rel32`: переход, если предыдущее сравнение дало ноль. Смещение пока
/// нулевое, его впишет `patchHere`, когда цель уляжется в буфер.
pub fn je32(buf: *Buf) Patch {
    buf.emit(0x0F);
    buf.emit(0x84);
    const at = buf.len;
    buf.emitInt(i32, 0);
    return .{ .at = at, .end = buf.len };
}

/// `jmp rel32`: безусловный переход с той же незакрытой целью.
pub fn jmp32(buf: *Buf) Patch {
    buf.emit(0xE9);
    const at = buf.len;
    buf.emitInt(i32, 0);
    return .{ .at = at, .end = buf.len };
}

/// Заплатка на произвольное смещение внутри буфера.
pub fn patchTo(buf: *Buf, spot: Patch, target: usize) void {
    const rel = @as(i64, @intCast(target)) - @as(i64, @intCast(spot.end));
    buf.patchInt(spot.at, @intCast(rel));
}

/// Заплатка на текущий конец буфера: цель это то, что будет уложено следующим.
pub fn patchHere(buf: *Buf, spot: Patch) void {
    patchTo(buf, spot, buf.len);
}

/// `jmp` назад, на уже известное место. Цель позади, значит rel32 отрицательный.
pub fn jmpBack(buf: *Buf, target: usize) void {
    const spot = jmp32(buf);
    patchTo(buf, spot, target);
}

В структуре Patch два числа, и оба обязательны. at это место, куда вписывать. end это адрес следующей инструкции, потому что rel32 отсчитывается именно от него, а не от начала перехода. Забыть про это самая частая ошибка новичка в кодогенерации: смещение получается ровно на длину инструкции больше нужного, программа улетает в середину чужой инструкции, и процессор исполняет мусор.

Условный je занимает шесть байт (два на opcode, четыре на смещение), безусловный jmp пять (один на opcode, четыре на смещение). Разница появилась ещё в 8086, где однобайтовых кодов не хватило на все условные переходы, и их вынесли в двухбайтовое пространство с префиксом 0x0F.

Посмотрим, что получается на выражении (cond (x 1) (t 0)), то есть «если аргумент не пуст, верни единицу, иначе ноль». Байты после пролога:

  19: 48 8b 45 f8              mov   -8(%rbp), %rax
  23: 48 83 f8 00              cmp   $0, %rax
  27: 0f 84 0f 00 00 00        je    48
  33: 48 b8 09 ...             movabs $9, %rax
  43: e9 0a 00 00 00           jmp   58
  48: 48 b8 01 00 00 00 00 00 00 00   movabs $1, %rax
  58: 48 8b 5d f0              mov   -16(%rbp), %rbx

Проверь заплатки сам. Инструкция je начинается на смещении 27 и занимает шесть байт, значит следующая начинается на 33, и записанное смещение пятнадцать даёт цель 48. Ровно там лежит вторая ветка. Инструкция jmp начинается на 43, занимает пять байт, следующая на 48, смещение десять даёт цель 58, а там уже эпилог. Обе заплатки закрылись правильно, и заметь, что число пятнадцать нельзя было знать в момент печати je: тогда байты первой ветки ещё не были уложены.

Хвостовой вызов

.tail => |inner| {
    self.gen(inner, depth);
    x86.movStore(buf, .rbp, x86.param_slot, .rax);
    x86.jmpBack(buf, self.body);
},

Три инструкции, и в них лежит одно из старейших решений в истории языков.

Хвостовой вызов это вызов, после которого функции больше нечего делать: результат вызванной функции и есть результат вызывающей. Если такой вызов компилировать честно, через call, кадр вызывающей будет висеть на стеке до самого конца, хотя в нём уже ничего нужного нет. Цикл, записанный рекурсией, съест стек за несколько миллионов витков.

Решение: не звать, а прыгать. Кладём новый аргумент в тот же слот кадра, где лежал старый, и делаем jmp на начало тела. Кадр не растёт, адрес возврата на стек не кладётся, %rsp не двигается. Рекурсия превращается в цикл.

В лиспе это не оптимизация, а часть языка: там нет отдельного оператора цикла, циклы пишутся рекурсией, и без такого преобразования диалект был бы непригоден. В стандарте Scheme это записано требованием. Компилятор C делать это не обязан, и потому одна и та же рекурсия на C то работает миллион витков, то падает, в зависимости от уровня оптимизации.

Наш jmpBack целится в self.body, то есть в смещение, которое вернул prologue. Смотри, что попадает выше этой метки, а что ниже. Выше: настройка кадра, сохранение %rbx, сгрузка аргумента из %rsi в слот. Ниже: собственно тело. Если бы метка стояла раньше сгрузки аргумента, прыжок затирал бы только что записанный слот тем, что осталось в %rsi, и цикл крутился бы с одним и тем же значением вечно. Порядок трёх строк в прологе не косметика.

И сразу ловушка, на которой легко обжечься с тегированными значениями. Цикл обязан на чём-то остановиться, а условие остановки читается как «значение ложно», то есть «слово равно нулю». Обход списка кончается сам собой: последний cdr вернёт nil, а nil и есть ноль. А вот обратный отсчёт по числу так не остановится: fixnum(0) в тегированном виде это единица, и с точки зрения cond она истинна. Значит числовому циклу нужна явная проверка примитивом вроде «больше нуля», который вернёт nil на конце. Это не особенность нашего JIT, а обычная жизнь любого языка, где ноль и ложь разные вещи.

Виджет: узел дерева в поток байтов

Дальше проще увидеть, чем прочитать. Выбирай программу слева, жми шаг, и виджет выкладывает по одной инструкции: слева подсвечивается узел дерева, который её породил, справа растёт поток байтов с подписями полей (префикс REX, opcode, ModRM, смещение, значение, rel32). Байты перехода до заплатки показаны точками, а когда цель уложена, точки превращаются в число: это ровно тот момент, о котором был разговор выше.

Обрати внимание на три вещи. Первая: у программы (car xs) на всё выражение приходятся две инструкции, а всё остальное это обвязка. Вторая: у (cond ...) смещение в je появляется не сразу, а через несколько шагов. Третья: у (loop (- x 1)) последний прыжок целится назад, и его rel32 отрицательный, записанный в дополнительном коде.

Виджет показывает тело без пролога и эпилога и потому заканчивает выражение инструкцией ret прямо на месте: ему нечего сворачивать. В нашем кодогенераторе ret стоит один раз в эпилоге, а ветки cond сходятся к нему через jmp. На байты самих шаблонов это не влияет.

Сборка целиком

Теперь всё складывается в одну функцию. Компилятор это структура из двух полей: буфер и смещение метки тела.

const Compiler = struct {
    buf: *x86.Buf,
    /// Смещение первой инструкции тела: цель хвостового прыжка.
    body: usize,

    fn gen(self: *Compiler, expr: *const Expr, depth: u8) void {
        const buf = self.buf;
        switch (expr.*) {
            // Константа целиком помещается в инструкцию.
            .fixnum => |n| x86.movImm64(buf, .rax, fixnum(n)),

            // Аргумент лежит в своём слоте кадра с самого пролога.
            .param => x86.movLoad(buf, .rax, .rbp, x86.param_slot),

            // Тег cons нулевой, поэтому снимать нечего: значение уже адрес пары.
            .car => |inner| {
                self.gen(inner, depth);
                x86.movLoad(buf, .rax, .rax, 0);
            },
            .cdr => |inner| {
                self.gen(inner, depth);
                x86.movLoad(buf, .rax, .rax, 8);
            },

            // Левый операнд считается первым и ждёт в слоте кадра, пока
            // считается правый. Через стек это было бы короче, но `push`
            // сбивает выравнивание, а слот кадра нет.
            .call => |call| {
                self.gen(call.a, depth);
                x86.movStore(buf, .rbp, x86.scratchSlot(depth), .rax);
                self.gen(call.b, depth + 1);
                x86.movRegReg(buf, .rdx, .rax);
                x86.movLoad(buf, .rsi, .rbp, x86.scratchSlot(depth));
                x86.movRegReg(buf, .rdi, .rbx);
                x86.movImm64(buf, .rax, @intFromPtr(call.prim));
                x86.callReg(buf, .rax);
            },

            // Ложь это ноль, поэтому проверка это сравнение с нулём, а прыжок
            // по равенству уводит во вторую ветку.
            .cond => |cond| {
                self.gen(cond.check, depth);
                x86.cmpImm8(buf, .rax, 0);
                const to_else = x86.je32(buf);
                self.gen(cond.on_true, depth);
                const to_end = x86.jmp32(buf);
                x86.patchHere(buf, to_else);
                self.gen(cond.on_false, depth);
                x86.patchHere(buf, to_end);
            },

            // Хвостовой вызов: новый аргумент ложится в тот же слот, и вместо
            // `call` идёт `jmp` на начало тела. Кадр не растёт, возврата нет.
            .tail => |inner| {
                self.gen(inner, depth);
                x86.movStore(buf, .rbp, x86.param_slot, .rax);
                x86.jmpBack(buf, self.body);
            },
        }
    }
};

/// Собрать машинный код тела `lambda` в буфер.
pub fn compile(buf: *x86.Buf, expr: *const Expr) void {
    const frame = x86.frameSize(scratchDepth(expr));
    var compiler: Compiler = .{ .buf = buf, .body = x86.prologue(buf, frame) };
    compiler.gen(expr, 0);
    x86.epilogue(buf);
}

Весь кодогенератор это один switch на сорок строк. Никакой отдельной фазы, никакого промежуточного представления, никакого распределения регистров: обход дерева печатает байты прямо в буфер. Такой компилятор называют однопроходным, и именно с него начинали все, включая первые лиспы.

Порядок в compile важен: scratchDepth обязан отработать до пролога, потому что размер кадра нужно знать в момент печати sub, а править его потом заплаткой мы не умеем. Настоящие компиляторы обходят это иначе, они печатают пролог в самом конце, когда о функции известно уже всё.

Посмотрим, что выходит на обходе списка. В лиспе это (cond (xs (loop (cdr xs))) (t 0)): пока список не пуст, переходим к хвосту, а на пустом возвращаем ноль. Семьдесят один байт целиком:

   0: 55                       push  %rbp
   1: 48 89 e5                 mov   %rsp, %rbp
   4: 48 83 ec 10              sub   $16, %rsp
   8: 48 89 5d f0              mov   %rbx, -16(%rbp)
  12: 48 89 fb                 mov   %rdi, %rbx
  15: 48 89 75 f8              mov   %rsi, -8(%rbp)
; сюда целится хвостовой прыжок
  19: 48 8b 45 f8              mov   -8(%rbp), %rax
  23: 48 83 f8 00              cmp   $0, %rax
  27: 0f 84 16 00 00 00        je    55
  33: 48 8b 45 f8              mov   -8(%rbp), %rax
  37: 48 8b 40 08              mov   8(%rax), %rax
  41: 48 89 45 f8              mov   %rax, -8(%rbp)
  45: e9 e1 ff ff ff           jmp   19
  50: e9 0a 00 00 00           jmp   65
  55: 48 b8 01 00 00 00 00 00 00 00   movabs $1, %rax
  65: 48 8b 5d f0              mov   -16(%rbp), %rbx
  69: c9                       leave
  70: c3                       ret

Разбери эту картинку строку за строкой, она вмещает весь урок. Кадр вышел на шестнадцать байт: вызовов примитива нет, значит и временных слотов не нужно, а меньше шестнадцати кадр не бывает из-за выравнивания. Проверка на ноль стоит сразу за меткой тела. Прыжок с 27 уводит на 55, где лежит вторая ветка со своим movabs $1 (это тегированный ноль). Тело цикла занимает три инструкции: прочитать аргумент, взять cdr чтением по смещению восемь, положить обратно в слот. Прыжок с 45 возвращает нас на 19, и его смещение e1 ff ff ff это минус тридцать один в дополнительном коде, ровно расстояние от 50 назад до 19. Прыжок с 50 уводит за развилку на 65, к эпилогу.

Заметь, чего в этом коде нет. В цикле нет ни одного call. Нет роста стека: после sub в прологе %rsp не двигается больше ни разу, сколько бы элементов ни было в списке. Нет разбора видов значений: cdr это одна инструкция чтения, а проверка конца списка одна инструкция сравнения. Ради такой картинки и затевалось всё остальное.

Программа с вызовом примитива выглядит так же по устройству, но длиннее: обратный отсчёт (cond ((> x 0) (loop (- x 1))) (t 0)) занимает сто тридцать девять байт, потому что в нём два вызова, сравнение и вычитание, и каждый разворачивается в свои восемь инструкций. Тесты эталона гоняют обе программы.

Байты в памяти, у которой есть право на исполнение

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

Причина понятная и разбиралась в уроке про переполнение буфера: запрет на исполнение данных это защита от подсунутого кода. Значит память под код надо просить у ядра отдельно и с явным правом на исполнение.

/// Страница памяти с машинным кодом, которую можно вызвать.
///
/// Мы просим у ядра страницу, где одновременно можно писать и исполнять.
/// Это самый простой и самый нечестный способ: правило W^X говорит, что
/// страница должна быть либо записываемой, либо исполняемой. Честный вариант
/// это отобразить страницу на запись, сложить байты и переключить права на
/// чтение с исполнением. Так мы и сделаем в уроке про отображение памяти,
/// а пока держим этот компромисс на виду.
pub const Code = struct {
    memory: []align(std.heap.page_size_min) u8,
    len: usize,

    pub fn map(bytes: []const u8) MapError!Code {
        const page = std.heap.pageSize();
        if (bytes.len > page) return error.CodeTooLong;
        const memory = try std.posix.mmap(
            null,
            page,
            .{ .READ = true, .WRITE = true, .EXEC = true },
            .{ .TYPE = .PRIVATE, .ANONYMOUS = true },
            -1,
            0,
        );
        @memcpy(memory[0..bytes.len], bytes);
        return .{ .memory = memory, .len = bytes.len };
    }

    /// Код как обычная функция с соглашением C.
    pub fn body(self: Code) Body {
        return @ptrFromInt(@intFromPtr(self.memory.ptr));
    }

    pub fn deinit(self: *Code) void {
        std.posix.munmap(self.memory);
        self.* = undefined;
    }
};

/// Скомпилировать дерево и сразу отобразить его в исполняемую память.
pub fn jit(expr: *const Expr) MapError!Code {
    var buf: x86.Buf = .{};
    compile(&buf, expr);
    return Code.map(buf.slice());
}

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

Дальше копируем байты и превращаем адрес в указатель на функцию. Вот и весь JIT: @ptrFromInt это то место, где данные перестают быть данными и становятся кодом. Никакой магии в нём нет, магия была в правах страницы.

Вызывается это как обычная функция:

var code = try jit.jit(&expr);
defer code.deinit();
const result = code.body()(&vm, jit.fixnum(41));

Про W^X, и почему у нас нечестно

Мы попросили страницу, где одновременно можно писать и исполнять. Это удобно и это плохая практика. Правило называется W xor X, и смысл его простой: если в процессе нет ни одной страницы, куда можно и писать, и прыгать, то подсунуть свой код становится сильно труднее.

Честный порядок такой: попросить страницу только на запись, сложить туда байты, потом отдельным вызовом переключить права на чтение с исполнением. Записывать после этого нельзя, а исполнять можно. Разберём этот путь как следует в уроке про отображение памяти, где он появится вместе с остальным устройством виртуальной памяти. Пока компромисс просто стоит на виду, в комментарии над структурой.

Две системные подробности, которые честнее знать заранее, чем узнать из падения.

На macOS страницу с правами на запись и исполнение так просто не дадут. Ядро требует особый флаг отображения, а дальше процесс переключает свой поток между режимом записи и режимом исполнения отдельным вызовом. То есть W^X там не совет, а требование, обойти которое нельзя, можно только выполнить. На Linux, где мы гоняем раздел, права выдаются как попросили, и наш простой вариант работает.

На процессорах со слабой моделью памяти нужен ещё и сброс кэша инструкций. Ты записал байты как данные, значит они лежат в кэше данных, а процессор будет читать их как инструкции, через кэш инструкций, и эти два кэша не обязаны сами договориться. На aarch64 после записи кода полагается явно очистить строки кэша данных и сбросить кэш инструкций. На x86-64 этого делать не надо: архитектура обещает согласованность кэша инструкций с записями в память, и это одна из немногих вещей, где x86-64 удобнее.

Проверка: два пути, один ответ

Кодогенератор нельзя проверить, глядя на его вывод. Байты выглядят правдоподобно всегда. Проверяют иначе: считают ту же программу другим способом и сверяют ответы.

Поэтому рядом с JIT живёт толкователь того же самого дерева. Это десять строк, и они не для скорости, а именно для сверки.

/// Тот же `Expr`, но исполненный обходом дерева. Хвостовой вызов здесь это
/// цикл, а не рекурсия, ровно как `jmp` в скомпилированном коде.
pub fn interpret(vm: *Vm, expr: *const Expr, arg: Value) Value {
    var current = arg;
    while (true) {
        switch (step(vm, expr, current)) {
            .done => |v| return v,
            .again => |next| current = next,
        }
    }
}

Обрати внимание, что хвостовой вызов и здесь превращается в цикл: step возвращает либо готовое значение, либо новый аргумент, с которым надо начать сначала. Это тот же jmp, только выраженный в Zig. Если бы толкователь честно рекурсировал, он падал бы там, где JIT работает, и сверка перестала бы что-либо значить.

Сама сверка занимает три строки:

/// Главная проверка шага: дерево и машинный код обязаны сойтись.
fn expectSame(vm: *Vm, expr: *const Expr, arg: Value) !void {
    const walked = jit.interpret(vm, expr, arg);
    const compiled = try runJit(vm, expr, arg);
    try testing.expectEqual(walked, compiled);
}

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

Отдельно стоит тест на то, ради чего затевался хвостовой вызов:

test "хвостовой вызов крутится в одном кадре и не переполняет стек" {
    if (!jit.canRun()) return error.SkipZigTest;

    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();

    // Миллион витков: рекурсия через call снесла бы стек, jmp его не двигает.
    try testing.expectEqual(
        @as(i64, 0),
        jit.fixnumOf(try runJit(&vm, &countdown, jit.fixnum(1_000_000))),
    );
    try expectSame(&vm, &countdown, jit.fixnum(1000));
}

Посчитай, во что обошёлся бы честный call. Кадр у этой программы тридцать два байта, плюс восемь на сохранённый %rbp, плюс восемь на адрес возврата: сорок восемь байт на виток. Миллион витков это сорок восемь мегабайт стека, а поток по умолчанию получает восемь. Честный вариант упал бы примерно на ста семидесяти тысячах витков. Наш проходит миллион и мог бы крутиться бесконечно, и это лучшее доказательство, что jmp действительно заменил call.

Тесты разделены на две половины по признаку, нужен ли им настоящий процессор x86-64. Байты энкодера верны везде, поэтому первая половина идёт на любой машине. Вторая прыгает в свежесобранный код, поэтому на другой архитектуре честно пропускает себя:

/// Запускать ли скомпилированный код на этой машине. Байты энкодера верны
/// везде, а вот прыгнуть в них можно только там, где процессор их понимает.
pub fn canRun() bool {
    return builtin.cpu.arch == .x86_64;
}

Тест, который тихо ничего не проверил, хуже отсутствующего теста. Тест, который честно сказал «пропущено, не та архитектура», нормален: на ноутбуке ты видишь зелёный энкодер и семь пропусков, в контейнере под x86-64 зелёное всё.

Шаг проекта: JIT встаёт четвёртым исполнителем zl

До сих пор JIT жил сам по себе. Дерево Expr мы собирали в тестах руками, пары лежали в массивах на стеке теста, примитивы были тестовыми функциями сложения. А у zl с урока про переходы и таблицы уже есть три исполнителя одной программы: обход дерева, байткод под циклом со switch и тот же байткод под labeled switch. Этот шаг ставит рядом четвёртый: zl --exec jit исполняет файл байткодом, но каждую функцию, которая JIT по силам, при первом вызове компилирует в машинный код и дальше зовёт напрямую.

Для этого не хватает трёх вещей. Первая: из тела настоящей lambda, то есть из ячеек кучи, надо получить дерево Expr. Этот перевод называют спуском (lowering): с языка побогаче на язык победнее. Вторая: дереву не хватает двух узлов, готового слова (символ, nil, список из quote) и вызова самой себя не из хвостовой позиции, без которого не скомпилировать ни fib, ни iota. Третья: машина байткода должна уметь спросить «есть ли для этой функции машинный код» и позвать его.

Значения сращивать не пришлось. После шага про тегированный указатель у value.Value и у jit.Value одни и те же биты для nil, чисел и пар, а ячейка value.Cell раскладкой совпадает с jit.Pair: 16 байт, car по нулю, cdr по восьми, выравнивание 16. Поэтому слово из кучи уходит в машинный код через @bitCast и возвращается так же, без единого преобразования.

Что JIT берёт, а что оставляет байткоду

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

В теле функции	Что делает спуск
один параметр и больше ничего не захвачено	берёт
число, `nil`, `t`, `quote`	узел `fixnum` или готовое слово `word`
`car`, `cdr` от одного аргумента	чтение по смещению 0 или 8, без вызова
примитив с постоянным числом аргументов (`cons`, `atom`, `eq`, `+`, `-`, `*`, `<`, `=`, `print`)	вызов через вход с соглашением C
`cond`	вложенные развилки на две ветки, последняя ложная ветка это `nil`
вызов самой себя	в хвосте `tail` (прыжок), иначе `self_call` (настоящий `call`)
два параметра, вызов параметра, `lambda`, `define`, вызов другой функции, `list`, свободное имя	отказ, функция остаётся байткоду

Отказ не ошибка. Машина запоминает его и больше эту функцию не спрашивает.

lower.zig целиком

//! Спуск: тело `lambda` из ячеек кучи превращается в дерево JIT.
//!
//! Дерево `jit.Expr` знает немногое: один аргумент, числа и готовые слова,
//! `car` и `cdr`, вызов примитива, развилку и вызов самой себя, в том числе
//! хвостовой. Если в теле есть что-то ещё (второй параметр, вызов другого
//! замыкания, `lambda`, `define`, свободное имя), функция целиком остаётся
//! байткоду. Решение принимается один раз, при первом вызове: исполнять
//! половину функции машинным кодом, а половину байткодом этот JIT не умеет.
//!
//! Два решения спуск принимает за программу, и оба надо держать в голове.
//! Имена примитивов и имя самой функции связываются в момент компиляции:
//! если программа потом переопределит `+`, скомпилированный код этого не
//! увидит. И машинный код верит типам: `car` это чтение по адресу без
//! проверки, что там пара. Правильная программа этого не заметит, а
//! неправильная упадёт по сигналу там, где байткод вернул бы `NotAPair`.

const std = @import("std");

const jit = @import("jit.zig");
const primitives = @import("primitives.zig");
const value = @import("value.zig");
const Vm = @import("vm.zig").Vm;
const x86 = @import("x86.zig");

const Cell = value.Cell;
const SymbolId = value.SymbolId;
const Value = value.Value;

pub const Error = std.mem.Allocator.Error;

/// Самый длинный шаблон одного узла: вызов примитива, 26 байт.
const max_node_bytes = 26;
/// Пролог и эпилог: 19 и 6 байт.
const frame_bytes = 25;
/// Временные слоты адресуются восьмибитным смещением от `%rbp`: ниже
/// двенадцатого уровня смещение уже не помещается в байт.
const max_depth = 12;

/// Скомпилировать тело замыкания в машинный код или вернуть null, если JIT
/// его не берёт. Дерево живёт только на время компиляции.
pub fn compile(gpa: std.mem.Allocator, vm: *Vm, callee: Value) Error!?jit.Code {
    var arena: std.heap.ArenaAllocator = .init(gpa);
    defer arena.deinit();
    const root = try translate(arena.allocator(), vm, callee) orelse return null;
    // Если ядро не дало исполняемую память, функцию исполнит байткод.
    return jit.jit(root) catch null;
}

/// Дерево JIT для замыкания или null, если JIT его не берёт.
pub fn translate(arena: std.mem.Allocator, vm: *Vm, callee: Value) Error!?*const jit.Expr {
    const cl = callee.asClosure();
    // Захваченное окружение значит свободные имена: их JIT читать не умеет.
    if (!cl.env.isNil()) return null;
    const params = cl.params;
    if (!params.isCons() or !params.asCell().cdr.isNil()) return null;
    const param = params.asCell().car;
    if (param.tag() != .symbol) return null;

    var lowering: Lowering = .{
        .arena = arena,
        .vm = vm,
        .param = param.asSymbol(),
        .params = cl.params,
        .body = cl.body,
    };
    const root = try lowering.expr(cl.body, true) orelse return null;
    // Буфер кода фиксированный: тело, которое может в него не влезть,
    // остаётся байткоду.
    if (lowering.nodes * max_node_bytes + frame_bytes > x86.Buf.capacity) return null;
    if (jit.scratchDepth(root) > max_depth) return null;
    return root;
}

const Lowering = struct {
    arena: std.mem.Allocator,
    vm: *Vm,
    param: SymbolId,
    /// Пара (параметры, тело) узнаёт саму функцию среди глобальных имён.
    params: Value,
    body: Value,
    nodes: usize = 0,

    fn node(self: *Lowering, e: jit.Expr) Error!?*const jit.Expr {
        self.nodes += 1;
        const at = try self.arena.create(jit.Expr);
        at.* = e;
        return at;
    }

    /// `tail` говорит, что значение выражения сразу станет значением функции.
    fn expr(self: *Lowering, e: Value, tail: bool) Error!?*const jit.Expr {
        return switch (e.tag()) {
            .nil => self.node(.{ .word = jit.nil }),
            .fixnum => self.node(.{ .fixnum = e.asFixnum() }),
            .symbol => self.name(e.asSymbol()),
            .cons => self.form(e, tail),
            .closure, .primitive => null,
        };
    }

    /// Из имён JIT знает параметр и две константы диалекта. Остальное это
    /// глобальные переменные, а их значение может смениться после компиляции.
    fn name(self: *Lowering, id: SymbolId) Error!?*const jit.Expr {
        if (id == self.param) return self.node(.param);
        if (id == self.vm.sym.nil) return self.node(.{ .word = jit.nil });
        if (id == self.vm.sym.t) return self.node(.{ .word = @bitCast(self.vm.true_()) });
        return null;
    }

    fn form(self: *Lowering, e: Value, tail: bool) Error!?*const jit.Expr {
        const head = e.asCell().car;
        const args = e.asCell().cdr;
        if (head.tag() != .symbol) return null;
        const id = head.asSymbol();

        // `quote` отдаёт готовое слово: символ или адрес списка. Список
        // лежит внутри тела, а тело держит машина, так что адрес не протухнет.
        if (id == self.vm.sym.quote) {
            const quoted = value.car(args) orelse return null;
            return self.node(.{ .word = @bitCast(quoted) });
        }
        if (id == self.vm.sym.cond) return self.cond(args, tail);
        // Вызов параметра это функция высшего порядка: не наш случай.
        if (id == self.param) return null;

        const callee = self.vm.lookupGlobal(id) orelse return null;
        var argv: [2]*const jit.Expr = undefined;
        var argc: usize = 0;
        var rest = args;
        while (rest.isCons()) : (rest = rest.asCell().cdr) {
            if (argc == argv.len) return null;
            argv[argc] = try self.expr(rest.asCell().car, false) orelse return null;
            argc += 1;
        }
        if (!rest.isNil()) return null;

        return switch (callee.tag()) {
            .closure => {
                const cl = callee.asClosure();
                if (argc != 1 or !cl.params.eql(self.params) or !cl.body.eql(self.body)) return null;
                return self.node(if (tail) .{ .tail = argv[0] } else .{ .self_call = argv[0] });
            },
            .primitive => self.primitive(callee.asPrimitive(), argv[0..argc]),
            else => null,
        };
    }

    fn primitive(self: *Lowering, index: primitives.Index, argv: []const *const jit.Expr) Error!?*const jit.Expr {
        // `car` и `cdr` не вызываются вовсе: это чтение по смещению 0 и 8.
        if (index == primitives.indexOf("car") and argv.len == 1) return self.node(.{ .car = argv[0] });
        if (index == primitives.indexOf("cdr") and argv.len == 1) return self.node(.{ .cdr = argv[0] });
        const known = entries[index] orelse return null;
        if (known.arity != argv.len) return null;
        // Второй аргумент одноместного примитива никто не читает.
        const b = if (argv.len == 2) argv[1] else try self.node(.{ .word = jit.nil }) orelse return null;
        return self.node(.{ .call = .{ .prim = known.prim, .a = argv[0], .b = b } });
    }

    /// Ветки `cond` разворачиваются во вложенные развилки на две ветки.
    /// Последняя ложная ветка это nil: ни одно условие не сработало.
    fn cond(self: *Lowering, clauses: Value, tail: bool) Error!?*const jit.Expr {
        if (clauses.isNil()) return self.node(.{ .word = jit.nil });
        if (!clauses.isCons()) return null;
        const clause = clauses.asCell().car;
        if (!clause.isCons()) return null;
        const body_list = clause.asCell().cdr;
        if (!body_list.isCons()) return null;

        const check = try self.expr(clause.asCell().car, false) orelse return null;
        const on_true = try self.expr(body_list.asCell().car, tail) orelse return null;
        const on_false = try self.cond(clauses.asCell().cdr, tail) orelse return null;
        return self.node(.{ .cond = .{ .check = check, .on_true = on_true, .on_false = on_false } });
    }
};

/// Примитив, который машинный код зовёт напрямую, и сколько он ждёт аргументов.
const Entry = struct {
    prim: jit.Prim2,
    arity: usize,
};

/// Примитивы с постоянным числом аргументов. `list` сюда не входит: он
/// возвращает сам список аргументов, а у входа ниже этот список на стеке.
const supported = .{
    .{ "cons", 2 }, .{ "atom", 1 }, .{ "eq", 2 },
    .{ "+", 2 },    .{ "-", 2 },    .{ "*", 2 },
    .{ "<", 2 },    .{ "=", 2 },    .{ "print", 1 },
};

const entries: [primitives.count]?Entry = blk: {
    var out: [primitives.count]?Entry = @splat(null);
    for (supported) |s| {
        const index = primitives.indexOf(s[0]);
        out[index] = .{ .prim = entry(index, s[1]), .arity = s[1] };
    }
    break :blk out;
};

/// Вход для машинного кода: значения приезжают в `%rsi` и `%rdx`, а примитив
/// ждёт список. Список из одной или двух ячеек собирается прямо в кадре
/// входа, куча не трогается. Ошибка примитива, как и на шаге 14, остаётся
/// в `vm.failure`, и её заберёт тот, кто звал машинный код.
fn entry(comptime index: primitives.Index, comptime arity: usize) jit.Prim2 {
    return struct {
        fn call(vm: *Vm, a: jit.Value, b: jit.Value) callconv(.c) jit.Value {
            var cells: [2]Cell = .{
                .{ .car = @bitCast(a), .cdr = .nil },
                .{ .car = @bitCast(b), .cdr = .nil },
            };
            if (arity == 2) cells[0].cdr = .fromCell(&cells[1]);
            return @bitCast(primitives.natives[index](vm, .fromCell(&cells[0])));
        }
    }.call;
}

Пройди по нему сверху вниз.

translate сначала проверяет форму функции: окружение пустое (замыкание, собранное внутри другой функции, читает захваченные имена, а их машинный код не видит), параметр ровно один и это символ. Потом спуск идёт по телу и на каждом узле либо строит Expr, либо возвращает null, и orelse return null поднимает отказ до самого верха. Параметр tail едет вниз по дереву так же, как в компиляторе байткода: значение ветки cond в хвосте тоже в хвосте, аргумент вызова никогда.

Буфер кода у нас фиксированного размера, поэтому спуск считает узлы и заранее отказывается от тела, которое может в буфер не влезть: самый длинный шаблон, вызов примитива, это 26 байт, пролог и эпилог ещё 25. Второе ограничение из кадра: временный слот адресуется восьмибитным смещением от %rbp, и глубже двенадцатого уровня оно в байт не помещается.

Главная хитрость в entry. Примитив zl с урока про соглашение о вызовах ждёт список аргументов, а машинный код кладёт аргументы в %rsi и %rdx. Можно было бы собирать список в куче, как делает байткод, но на это ушла бы ячейка на каждый аргумент каждого вызова. Вход поступает дешевле: две ячейки лежат в его собственном кадре на стеке, список из них живёт ровно до возврата примитива, куча не тронута. Так можно только потому, что ни один примитив не сохраняет свой список аргументов. cons кладёт в новую ячейку значения из списка, а не сам список. comptime-параметры index и arity дают по отдельной функции на каждый примитив, как и таблица natives на шаге 14. Ошибку примитив по-прежнему оставляет в vm.failure, и её заберёт тот, кто позвал машинный код.

Два решения спуск принимает за программу, и оба записаны в шапке файла. Имена примитивов и имя самой функции связываются при компиляции: если программа потом переопределит +, машинный код этого не увидит. А car в машинном коде это чтение по адресу без проверки, что там пара. Правильная программа разницы не заметит, неправильная упадёт по сигналу там, где байткод вернул бы NotAPair. Настоящие JIT платят за такие проверки несколькими инструкциями на обращение и откатываются в интерпретатор, когда предположение нарушено; у нас учебный минимум, и цену его лучше знать.

Два новых узла

В Expr появляются word и self_call:

    /// Готовое слово: nil, символ или адрес списка из `quote`.
    word: Value,

    /// Вызов самой себя не из хвостовой позиции: настоящий `call` со своим
    /// кадром и возвратом.
    self_call: *const Expr,

Слово ложится в %rax тем же movabs, что и число, только тегирует его не компилятор, а спуск: символ t приезжает уже как номер << 4 | 1000, список из quote как адрес его первой ячейки. Адрес не протухнет: тело функции держит машина байткода, об этом ниже.

            .word => |w| x86.movImm64(buf, .rax, w),

Вызов самой себя собирается из того, что уже есть: аргумент в %rsi, машина из %rbx в %rdi, и call на нулевое смещение, в самое начало функции, где стоит пролог. Новый вызов строит свой кадр ниже нашего, а временные слоты вызывающего лежат выше %rsp и переживут его нетронутыми.

            // Вызов самой себя: аргумент в `%rsi`, машина в `%rdi` и `call`
            // на нулевое смещение, в пролог. Кадр вызывающего ниже не трогают:
            // его временные слоты переживут вызов.
            .self_call => |inner| {
                self.gen(inner, depth);
                x86.movRegReg(buf, .rsi, .rax);
                x86.movRegReg(buf, .rdi, .rbx);
                x86.callBack(buf, 0);
            },

Здесь call прямой, с rel32, хотя примитивы мы зовём через movabs и регистр. Противоречия нет: цель лежит в том же буфере, в паре сотен байт от места вызова, и двух гигабайт хватает с запасом.

/// `call rel32` на уже известное место того же буфера: opcode `0xE8` и
/// смещение от конца инструкции. Прямой вызов годится, когда цель лежит
/// в том же куске кода: до неё заведомо ближе двух гигабайт.
pub fn callBack(buf: *Buf, target: usize) void {
    buf.emit(0xE8);
    const at = buf.len;
    buf.emitInt(i32, 0);
    patchTo(buf, .{ .at = at, .end = buf.len }, target);
}

Выравнивание стека сходится само. Кадр кратен шестнадцати, значит в момент call %rsp делится на шестнадцать, как и перед вызовом примитива; call кладёт адрес возврата, и вызванная копия видит на входе ровно то, что видит любая функция по System V.

scratchDepth узнаёт новые узлы в тех же строках, что и старые: слово глубины не требует, вызов самой себя требует столько же, сколько его аргумент.

        .fixnum, .word, .param => 0,
        .car, .cdr, .self_call, .tail => |inner| scratchDepth(inner),

Толкователь дерева, с которым сверяется JIT, получает параметр root, всё тело функции: туда ведёт вызов самой себя.

        .self_call => |inner| .{ .done = interpret(vm, root, evalValue(vm, root, inner, arg)) },

Машина зовёт машинный код

В bytecode.zig у машины два новых поля:

    /// Четвёртый исполнитель. Если включён, замыкание, чьё тело по силам
    /// JIT, при первом вызове компилируется в машинный код x86-64 и дальше
    /// зовётся напрямую. Всё остальное по-прежнему исполняет байткод.
    use_jit: bool = false,
    /// Машинный код по телам функций. null значит: JIT посмотрел и отказался.
    natives: std.AutoHashMapUnmanaged(FunctionKey, ?jit.Code) = .empty,

Ключ тот же, что у кэша скомпилированного байткода, пара (параметры, тело): она одна у всех замыканий одной lambda. Решение принимается один раз и запоминается вместе с отказом:

    /// Машинный код замыкания, если JIT включён и тело ему по силам. Решение
    /// принимается при первом вызове и запоминается вместе с отказом.
    fn nativeOf(self: *Machine, callee: Value, argc: u32) Error!?jit.Body {
        if (!self.use_jit or argc != 1) return null;
        const gpa = self.vm.gpa;
        const cl = callee.asClosure();
        const key: FunctionKey = .{ .params = cl.params, .body = cl.body };
        const slot = try self.natives.getOrPut(gpa, key);
        if (!slot.found_existing) {
            slot.value_ptr.* = null;
            // Машинный код держит адреса из тела, поэтому тело держим и мы.
            try self.constants.appendSlice(gpa, &.{ key.params, key.body });
            slot.value_ptr.* = try lower.compile(gpa, self.vm, callee);
        }
        return if (slot.value_ptr.*) |*code| code.body() else null;
    }

slot.value_ptr.* = null стоит до компиляции не случайно. Если спуск не справится с памятью и вернёт ошибку, в карте уже лежит честный отказ, а не мусор из getOrPut.

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

            .closure => if (try self.nativeOf(callee, argc)) |body| {
                // Машинный код работает на стеке Zig и возвращается со значением,
                // как примитив: кадра байткода ему не нужно.
                const result: Value = @bitCast(body(self.vm, @bitCast(self.stack.items[base])));
                if (self.vm.takeFailure()) |err| return err;
                self.stack.shrinkRetainingCapacity(base);
                self.stack.items[base - 1] = result;
            } else {
                const chunk = try self.functionOf(callee, argc);
                try self.pushFrame(.{ .chunk = chunk, .pc = 0, .base = base });
            },

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

        if (try self.nativeOf(callee, argc) != null) return self.call(argc);

Ключ --exec jit

В main.zig исполнитель получает четвёртое значение:

/// Кто исполняет программу: обход дерева, байткод под одним из диспетчеров
/// или машинный код там, где JIT берёт функцию, и байткод во всём остальном.
const Executor = enum { tree, loop, labeled, jit };

    if (executor == .jit and !jit.canRun()) {
        try out.writeAll("--exec jit исполняет машинный код x86-64, а этот процессор другой\n");
        try out.flush();
        return error.BadArgument;
    }

        .jit => {
            machine.use_jit = true;
            return machine.runSource(source, .labeled);
        },

На Apple M4 Max ключ честно отказывается:

$ zig build run -- --exec jit programs/fib.zl
--exec jit исполняет машинный код x86-64, а этот процессор другой
error: BadArgument

Под amd64 все четыре исполнителя дают один ответ:

$ docker run --rm --platform linux/amd64 -v "$PWD":/work -w /work \
    ghcr.io/bondiano/runner-zig:dev-amd64 sh -c \
    'zig build --cache-dir /work/.zc --global-cache-dir /work/.zg &&
     for e in tree loop labeled jit; do
       echo "== $e"; ./zig-out/bin/zl --exec $e programs/fib.zl
       ./zig-out/bin/zl --exec $e programs/list-sum.zl
     done'
== tree
6765
500500
== loop
6765
500500
== labeled
6765
500500
== jit
6765
500500

В list-sum.zl машинным кодом исполняется только iota: у sum два параметра, и её JIT даже не рассматривает.

Что получилось в байтах

Функция last из тестов, (lambda (xs) (cond ((cdr xs) (last (cdr xs))) (t (car xs)))), после спуска и компиляции занимает 108 байт. Байты сложены в объектный файл и разобраны objdump для x86_64-linux:

0000000000000000 <last>:
       0:      	pushq	%rbp
       1:      	movq	%rsp, %rbp
       4:      	subq	$0x10, %rsp
       8:      	movq	%rbx, -0x10(%rbp)
       c:      	movq	%rdi, %rbx
       f:      	movq	%rsi, -0x8(%rbp)
      13:      	movq	-0x8(%rbp), %rax
      17:      	movq	0x8(%rax), %rax
      1b:      	cmpq	$0x0, %rax
      1f:      	je	0x3b <last+0x3b>
      25:      	movq	-0x8(%rbp), %rax
      29:      	movq	0x8(%rax), %rax
      2d:      	movq	%rax, -0x8(%rbp)
      31:      	jmp	0x13 <last+0x13>
      36:      	jmp	0x66 <last+0x66>
      3b:      	movabsq	$0x98, %rax
      45:      	cmpq	$0x0, %rax
      49:      	je	0x5c <last+0x5c>
      4f:      	movq	-0x8(%rbp), %rax
      53:      	movq	(%rax), %rax
      57:      	jmp	0x66 <last+0x66>
      5c:      	movabsq	$0x0, %rax
      66:      	movq	-0x10(%rbp), %rbx
      6a:      	leave
      6b:      	retq

Цикл по списку это пять инструкций с 0x13 по 0x31, без единого вызова. Видно и то, чего однопроходный компилятор не замечает: вторая ветка cond проверяет символ t (0x98, номер 9 со сдвигом и тегом 1000), хотя он истинен всегда, а jmp на 0x36 недостижим. Свёртку константных условий делает любой компилятор с оптимизатором; нашему она не нужна для правильности, и это хорошее домашнее задание.

У fib 247 байт и кадр на 32 байта: глубина временных слотов два, потому что сложение ждёт в слоте результат первого вызова, пока считается второй. Середина тела, два вызова самой себя:

      62:      	movq	-0x8(%rbp), %rax
      66:      	movq	%rax, -0x18(%rbp)
      6a:      	movabsq	$0x9, %rax
      74:      	movq	%rax, %rdx
      77:      	movq	-0x18(%rbp), %rsi
      7b:      	movq	%rbx, %rdi
      7e:      	movabsq	$0x100cbcaf4, %rax      # imm = 0x100CBCAF4
      88:      	callq	*%rax
      8a:      	movq	%rax, %rsi
      8d:      	movq	%rbx, %rdi
      90:      	callq	0x0 <fib>
      95:      	movq	%rax, -0x18(%rbp)
      99:      	movq	-0x8(%rbp), %rax
      9d:      	movq	%rax, -0x20(%rbp)
      a1:      	movabsq	$0x11, %rax
      ab:      	movq	%rax, %rdx
      ae:      	movq	-0x20(%rbp), %rsi
      b2:      	movq	%rbx, %rdi
      b5:      	movabsq	$0x100cbcaf4, %rax      # imm = 0x100CBCAF4
      bf:      	callq	*%rax
      c1:      	movq	%rax, %rsi
      c4:      	movq	%rbx, %rdi
      c7:      	callq	0x0 <fib>
      cc:      	movq	%rax, %rdx

(- n 1) это вызов входа примитива - по адресу из movabs (адрес свой в каждой сборке), потом callq 0x0, прямой вызов на начало функции. Результат первого вызова уезжает в слот -0x18, второй вычитает 0x11, тегированную двойку, и тоже зовёт себя. После 0xcc результат второго вызова стоит в %rdx, первого ждёт в слоте, и дальше идёт вызов +.

Тесты шага

К tests/step_19.zig добавились тесты четвёртого исполнителя. Первый проверяет байты вызова самой себя и идёт везде. Второй проверяет, что спуск берёт и от чего отказывается, и тоже идёт везде: спуск чистый, ему процессор x86-64 не нужен. Остальные три прыгают в машинный код, поэтому под другой архитектурой пропускают себя: все программы из programs/ дают под JIT тот же ответ, что под обходом дерева; fib компилируется целиком, а в list-sum.zl JIT берёт iota и не трогает sum; ошибка примитива из машинного кода доходит до вызывающего.

test "спуск берёт функцию от одного аргумента и отказывается от остального" {
    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();
    _ = try eval.evalSource(&vm, definitions);
    var arena: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena.deinit();
    const a = arena.allocator();

    // Берёт: один параметр, примитивы, cond, вызов самой себя.
    const fib = (try lowered(&vm, a, "fib")).?;
    try testing.expect(fib.* == .cond);
    try testing.expect((try lowered(&vm, a, "iota")) != null);
    // В хвосте вызов самой себя становится прыжком.
    const last = (try lowered(&vm, a, "last")).?;
    try testing.expect(last.cond.on_true.* == .tail);

    // Два параметра, вызов параметра, lambda в теле, захваченное окружение,
    // вызов другой функции: всё это остаётся байткоду.
    for ([_][]const u8{ "sum", "twice", "adder", "add5", "later" }) |name| {
        try testing.expectEqual(@as(?*const Expr, null), try lowered(&vm, a, name));
    }
}

test "ошибка примитива из машинного кода доходит до вызывающего" {
    if (!jit.canRun()) return error.SkipZigTest;

    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();
    var m: bytecode.Machine = .init(&vm);
    defer m.deinit();

    try testing.expectError(error.NotANumber, runWithJit(&m,
        \\(define bad (lambda (x) (+ x 'a)))
        \\(bad 1)
    ));
    try testing.expectEqual([2]usize{ 1, 0 }, tally(&m));
}

Прогон на Apple M4 Max и под amd64:

$ zig build test --summary all
Build Summary: 15/15 steps succeeded; 66/76 tests passed (10 skipped)

$ docker run --rm --platform linux/amd64 -v "$PWD":/work -w /work \
    ghcr.io/bondiano/runner-zig:dev-amd64 \
    zig build test --summary all --cache-dir /work/.zc --global-cache-dir /work/.zg
Build Summary: 15/15 steps succeeded; 76/76 tests passed

Десять пропусков на arm64 это все тесты, которые прыгают в машинный код: семь из первой половины урока и три новых.

Ловушки, которые ждут любого кодогенератора

Соберём в одно место всё, на чём спотыкаются, когда пишут машинный код руками.

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

Незакрытая заплатка. Если генератор забыл вписать смещение, там останется ноль, а нулевой rel32 это переход на следующую инструкцию. Программа не упадёт, она просто будет делать не то. Лечится тем, что каждая функция, печатающая переход, возвращает Patch, а язык не даёт молча выбросить возвращённое значение.

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

Callee-saved регистры. Взял %rbx под своё, будь добр вернуть. Нарушение проявляется не в твоём коде, а в вызывающем, у которого испортилось значение, пережившее вызов. Отладка такого занимает часы, потому что ищут не там, где сломали.

Кэш инструкций. На x86-64 не проблема, на aarch64 проблема. Признак ровно тот же, что у испорченного регистра: код работает через раз и падает не там, где ошибка.

Диапазон rel32. Тридцать два бита знакового смещения это плюс-минус два гигабайта. Для тела одной функции запас бесконечный, а вот для вызова функции, лежащей в другом отображении, никакого запаса нет. Отсюда и movabs с адресом вместо прямого call.

Практика

Задача про самое дно кодогенератора: четыре функции энкодера, байт в байт. Тебе даны тип регистра с методами low3 и extended и буфер с методами emit и emitInt, а написать надо emitMovImm64 (это movabs), emitPush, emitCall (косвенный вызов по регистру) и emitJneRel32 (переход по неравенству на абсолютное смещение внутри того же буфера, со смещением, посчитанным от конца шестибайтной инструкции). Скрытые тесты сверяют байты с эталоном, включая расширенные регистры, у которых поднимается бит B в префиксе REX, и отрицательное смещение перехода назад в дополнительном коде. Никакого x86-64 под тобой при этом не нужно: логика чистая.

Упражнения

CHK-1★

Возьми байты 48 8b 40 08 и 48 8b 45 f8 и разбери каждый по полям: префикс REX (какие из битов W, R, X, B подняты), opcode, байт ModRM (режим, поле reg, поле rm), смещение. Объясни, почему у первой базой оказался %rax, а у второй %rbp, хотя байт ModRM отличается всего на пять.

CHK-2★★

Посчитай на бумаге, сколько байт займёт тело для выражения (+ (car xs) (cdr xs)), зная длины шаблонов из урока. Потом собери эталон, скомпилируй это выражение и сверь с настоящей длиной. Если не сошлось, найди шаблон, в котором ошибся на инструкцию.

CHK-3★★

Сломай заплатку нарочно: в patchTo посчитай смещение от начала инструкции перехода, а не от её конца. Прогони тесты энкодера и запиши, какие именно упали и с каким числом. Потом верни как было и объясни в одном абзаце, почему ошибка на пять или шесть байт уводит исполнение в середину чужой инструкции.

CHK-4★★★

Убери из шаблона вызова примитива строку, которая кладёт машину из %rbx в %rdi, и объясни, почему первый же вызов начнёт получать мусор первым аргументом. Затем убери из пролога сохранение %rbx и покажи на примере вызывающего кода, что именно ломается и почему падение приходит не оттуда, где ошибка.

CHK-5★★

Замени в кадре временный слот на пару push и pop вокруг вычисления правого операнда. Проверь, что простые программы работают, а потом собери выражение, у которого внутри правого операнда есть свой вызов примитива, и посмотри на выравнивание стека в момент внутреннего call. Посчитай %rsp по модулю шестнадцать вручную и объясни результат.

CHK-6★★★

Замени хвостовой jmp на честный call с последующим ret и найди опытным путём, на каком числе витков обратный отсчёт перестаёт работать. Оцени по этому числу размер кадра и размер стека, доступного потоку, и сравни оценку с тем, что говорит система.

CHK-7★★

Сделай шаг zl у себя и научи спуск сворачивать константные условия: ветка cond, чьё условие это число, t или quote, истинна всегда, и развилка на ней не нужна, а всё, что стоит после неё, недостижимо. Посчитай, сколько байт ушло из last и из fib, и сверь с листингом objdump из урока, какие инструкции исчезли.

CHK-8★★★

Под --exec jit вызови функцию со сложением, потом переопредели + через define и вызови её снова. Покажи, что обход дерева и байткод видят новое определение, а машинный код нет, и объясни, где именно спуск связал имя. Предложи два способа это исправить (подсказка: таблица адресов на странице данных из урока про отображение памяти и сброс кэша natives при define) и оцени цену каждого на вызов.

Итоги

JIT это третий способ выполнить программу после обхода дерева и байткода: диспетчеризация исчезает совсем, потому что операция программы становится инструкцией процессора.
Перед кодогенерацией значение сжимают до одного слова и прячут вид в младшие биты. nil это ноль, число это сдвиг с единицей в младшем бите, пара это указатель с нулевым тегом, и потому car и cdr это одна инструкция чтения со смещением.
Скомпилированное тело говорит на языке обычного соглашения о вызовах. Из-за этого граница между сгенерированным кодом и кодом на Zig исчезает: они зовут друг друга как равные.
Энкодер это чистая функция от мнемоники и операндов к байтам. Он не зависит ни от машины, ни от операционной системы, поэтому проверяется тестами на любой архитектуре, а проверять его надо обязательно, сверяя вывод с дизассемблером.
Кодогенерация в один аккумулятор держится на одном негласном правиле: любой узел оставляет результат в %rax. Из него растёт стыкуемость шаблонов без всяких переговоров между ними.
Временные значения живут в слотах кадра, а не на стеке через push: кадр выделен один раз и не трогает %rsp, а значит не ломает выравнивание на шестнадцать перед call.
Переход, чья цель ещё не уложена, печатается с нулевым смещением, а место запоминается. Обратная заплатка вписывает настоящее число, когда цель появилась. Смещение rel32 отсчитывается от конца инструкции перехода.
Хвостовой вызов компилируется в jmp на начало тела с переписанным слотом аргумента. Кадр не растёт, и рекурсия становится циклом, который выдерживает миллион витков.
Байты становятся кодом только в памяти с правом на исполнение. Правило W^X требует разделять запись и исполнение по времени, macOS требует этого жёстко, а на архитектурах со слабой моделью памяти нужен ещё и сброс кэша инструкций.
Кодогенератор проверяют сверкой: та же программа считается обходом дерева и машинным кодом, и ответы обязаны совпасть. Тест, которому нужен настоящий x86-64, на другой архитектуре честно пропускает себя.
Шаг zl: спуск переводит тело lambda из ячеек кучи в дерево JIT или отказывается целиком, машина байткода компилирует функцию при первом вызове и дальше зовёт машинный код напрямую, а zl --exec jit даёт тот же ответ, что три других исполнителя.

Дальше

Ты замкнул круг блока: сначала читал чужие байты, потом писал свои. Кодогенератор, который у тебя получился, наивен по мерке настоящих компиляторов (один аккумулятор, никакого распределения регистров, никаких проверок видов значений), но он настоящий: он печатает те же байты, что печатает любой другой, и по тем же правилам.

Дальше начинается блок, где меняется точка зрения. До сих пор процессор был данностью: система команд существует, ты учишься на ней говорить. В следующем уроке, 32-systems/20 · Y86-64: система команд и кодирование, мы возьмём маленькую систему команд и построим под неё всё: ассемблер, симулятор, а потом настоящий процессор на Verilog, сначала последовательный, потом конвейерный. Начнём с того же, с чего начинали сегодня, с контракта: какое состояние машина показывает программисту и как каждая инструкция превращается в байты. Только теперь этот контракт будешь исполнять не ты, а железо, которое ты сам и опишешь.

домашка

Домашка

Добавь шаблон сложения тегированных чисел без вызова примитива: сложение регистров плюс поправка на тег. Покажи, на сколько байт и на сколько вызовов сократилась программа со сложением, и почему такой шаблон нельзя применять вслепую.MS
Расширь соглашение до двух аргументов: второй приезжает в rdx и получает свой слот кадра. Перепиши пролог, таблицу слотов и хвостовой вызов, оставив тесты на одном аргументе зелёными.S
Переведи отображение кода на честный W^X: страница на запись, байты, потом права на чтение с исполнением. Покажи, что прыжок в код до переключения прав падает, а после работает.S