Циклы и switch на машинном уровне

В прошлом уроке ты научился читать флаги, условные переходы и cmov. Из этих кирпичей процессор собирает всё, что в языке выглядит как while, for, continue и switch. В этом уроке мы разбираем каждую конструкцию на настоящем ассемблере Zig 0.16 под x86-64: как выглядит do-while, почему компилятор перекладывает while в guarded-do, во что сворачиваются for и continue, и как большой switch превращается в таблицу адресов в памяти, а labeled switch в тот самый computed goto, которым интерпретаторы обходят предсказатель ветвлений. Попутно два шага сквозных проектов: дизассемблер учится читать переход по таблице, а байткод-машина обзаводится тремя исполнителями.

Цели урока

• Прочитать do-while в ассемблере: одно тело, проверка снизу, один условный переход на итерацию.
• Различать две раскладки while, jump-to-middle и guarded-do, и знать, какую выбирает LLVM в режиме оптимизации и почему.
• Увидеть, что for по срезу и эквивалентный while дают байт в байт один и тот же код.
• Понять continue как переход к шагу цикла и заметить, когда оптимизатор стирает этот переход через cmov.
• Разобрать switch через таблицу переходов: проверка границы, косвенный jmp по индексу и сама таблица адресов в .rodata.
• Понять, почему разреженные метки дают не таблицу, а дерево сравнений, и как switch с диапазонами Zig сводится к вычитанию базы и одному беззнаковому сравнению.
• Прочитать labeled switch как computed goto: непрямой переход, реплицированный в каждую ветку, и связать это с предсказателем ветвлений.
• Восстанавливать Zig-код по ассемблеру цикла и switch, как в упражнениях главы 3 книги.

Идея: язык это переходы, а компилятор их раскладывает

На уровне процессора нет ни while, ни switch. Есть только линейный поток инструкций и переходы, которые этот поток гнут: безусловный jmp, условные je, jl, jb по флагам из прошлого урока про сравнения и переходы, и косвенный jmp по адресу из регистра или памяти. Любая конструкция управления в языке это выбор компилятора, как разложить твой замысел в эти переходы. Глава 3 CS:APP разбирает этот выбор для C и GCC, а мы посмотрим на него глазами Zig и LLVM.

Три вопроса, на которые отвечает урок. Как выглядит цикл, у которого проверка стоит внизу, а не вверху, и почему компилятор часто предпочитает именно такую форму. Что происходит, когда веток много: линейная цепочка if слишком медленная, и вместо неё появляется либо таблица адресов, либо дерево сравнений. И зачем языку отдельная форма switch, которая не возвращается в общую точку, а прыгает из каждой ветки напрямую в следующую.

Каждый листинг ниже снят с настоящего компилятора. Zig-файл собран в объектник и разобран через objdump -d, поэтому синтаксис везде AT&T: приёмник справа, % перед регистрами, суффикс размера у инструкции. Функции, чей ассемблер мы показываем, объявлены export fn с указателем и длиной вместо среза, иначе оптимизатор встроил бы их в вызывающего, и смотреть было бы не на что. Команда над каждым листингом говорит, чем он снят.

do-while: проверка внизу

Начнём с формы, которая ложится в ассемблер прямее всего: цикл, тело которого исполняется хотя бы раз, а проверка стоит в конце. В Zig это while (true) с условием выхода в конце тела. Просуммируем массив.

const std = @import("std");

// do-while: тело исполняется хотя бы раз, проверка внизу.
export fn sumDoWhile(a: [*]const i64, len: usize) i64 {
    var total: i64 = 0;
    var i: usize = 0;
    while (true) {
        total += a[i];
        i += 1;
        if (i >= len) break;
    }
    return total;
}

Снимаем ассемблер объектника, собранного в режиме на минимальный размер, где цикл остаётся простым циклом без развёртки:

$ zig build-obj loops.zig -O ReleaseSmall -target x86_64-linux -femit-bin=loops-small.o
$ objdump -d --no-show-raw-insn loops-small.o

<sumDoWhile>:
    pushq   %rbp
    movq    %rsp, %rbp
    xorl    %eax, %eax            # total = 0
    xorl    %ecx, %ecx            # i = 0
    addq    (%rdi,%rcx,8), %rax   # total += a[i]
    incq    %rcx                  # i += 1
    cmpq    %rsi, %rcx            # i < len ?
    jb      <sumDoWhile+0x8>       # да: назад в тело
    popq    %rbp
    retq

Разбери построчно. Аргументы пришли по соглашению System V: указатель a в %rdi, длина len в %rsi. Два xorl обнуляют аккумулятор %rax и счётчик %rcx: xor регистра с самим собой это привычная в x86 идиома записать ноль короче, чем mov $0. Дальше начинается тело сразу, без всякой проверки: addq (%rdi,%rcx,8), %rax читает a[i] по адресу база + индекс * 8 и прибавляет к сумме. Множитель 8 это размер i64 в байтах, тот самый масштаб в адресации, который ты видел в уроке про операнды. incq увеличивает индекс. И только теперь проверка: cmpq %rsi, %rcx вычитает len из i ради флагов, jb (jump if below, беззнаковое меньше) возвращает в начало тела, пока i меньше len. Один условный переход на итерацию, тело всегда исполняется хотя бы раз. Это точная машинная форма do-while.

while: jump-to-middle против guarded-do

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

Первый называют jump-to-middle: на входе стоит безусловный jmp прямо к проверке в конце цикла, а тело расположено выше. Второй называют guarded-do: перед циклом стоит одна проверка-охрана, которая при ложном условии перепрыгивает цикл целиком, а внутри лежит обычный do-while с проверкой снизу. Вот обе формы, написанные руками на ассемблере для суммы массива, чтобы увидеть их рядом. Каждая собрана и проверена: адреса в переходах настоящие.

# jump-to-middle: вход прыгает сразу к проверке.
sum_jtm:
    xorq    %rax, %rax          # total = 0
    xorq    %rcx, %rcx          # i = 0
    jmp     .Ltest              # прыжок в середину, к проверке
.Lbody:
    addq    (%rdi,%rcx,8), %rax # total += a[i]
    incq    %rcx                # i += 1
.Ltest:
    cmpq    %rsi, %rcx          # i < len ?
    jb      .Lbody
    ret

# guarded-do: охрана в начале, проверка снизу.
sum_gdo:
    xorq    %rax, %rax          # total = 0
    testq   %rsi, %rsi          # len == 0 ?
    je      .Ldone              # охрана: пропустить цикл целиком
    xorq    %rcx, %rcx          # i = 0
.Lbody2:
    addq    (%rdi,%rcx,8), %rax # total += a[i]
    incq    %rcx                # i += 1
    cmpq    %rsi, %rcx          # i < len ?
    jb      .Lbody2
.Ldone:
    ret

$ zig cc -c -target x86_64-linux loopforms.s -o loopforms.o
$ objdump -d --no-show-raw-insn loopforms.o
<sum_jtm>:
    xorq    %rax, %rax
    xorq    %rcx, %rcx
    jmp     <sum_jtm+0xf>
    addq    (%rdi,%rcx,8), %rax
    incq    %rcx
    cmpq    %rsi, %rcx
    jb      <sum_jtm+0x8>
    retq
<sum_gdo>:
    xorq    %rax, %rax
    testq   %rsi, %rsi
    je      <sum_gdo+0x17>
    xorq    %rcx, %rcx
    addq    (%rdi,%rcx,8), %rax
    incq    %rcx
    cmpq    %rsi, %rcx
    jb      <sum_gdo+0xb>
    retq

Разница в том, что происходит на входе с пустым диапазоном. У jump-to-middle вход прыгает к проверке, проверка сразу видит i >= len и падает мимо тела: одна копия условия обслуживает и первый вход, и все повторы. У guarded-do отдельная охрана testq %rsi, %rsi; je пропускает цикл, а дальше тело и проверка снизу, как в do-while. Guarded-do дороже на входе на одну инструкцию, зато горячий цикл содержит ровно один условный переход на итерацию, и он в конце, где предсказателю удобно: переход назад почти всегда берётся.

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

const std = @import("std");

const Node = extern struct {
    val: i64,
    next: ?*const Node,
};

// Обход списка: пока указатель не null, прибавляем значение и идём дальше.
export fn listSum(head: ?*const Node) i64 {
    var total: i64 = 0;
    var cur = head;
    while (cur) |node| {
        total += node.val;
        cur = node.next;
    }
    return total;
}

$ zig build-obj listsum.zig -O ReleaseFast -target x86_64-linux -femit-bin=listsum-fast.o
$ objdump -d --no-show-raw-insn listsum-fast.o

<listSum>:
    testq   %rdi, %rdi            # head == null ?
    je      <listSum+0x1e>        # охрана: пустой список -> сразу выход
    pushq   %rbp
    movq    %rsp, %rbp
    xorl    %eax, %eax            # total = 0
    addq    (%rdi), %rax          # total += node.val
    movq    0x8(%rdi), %rdi       # cur = node.next
    testq   %rdi, %rdi            # cur == null ?
    jne     <listSum+0x10>        # нет: назад в тело
    popq    %rbp
    retq
    xorl    %eax, %eax            # ветка пустого списка: total = 0
    retq

Это чистый guarded-do. Сначала охрана testq %rdi, %rdi; je: если список пуст, перепрыгиваем в самый низ, где %rax обнуляется и функция возвращает ноль. Иначе тело: addq (%rdi), %rax берёт поле val по нулевому смещению узла, movq 0x8(%rdi), %rdi читает next со смещения 8 и кладёт в тот же регистр указателя, а testq %rdi, %rdi; jne в конце возвращает к телу, пока указатель не станет null. LLVM в режиме оптимизации почти всегда раскладывает while именно так: это называют ротацией цикла, и делают её ради предсказуемого перехода в конце горячей части.

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

$ objdump -d --no-show-raw-insn loops-small.o    # функция sumWhile, обычный while по индексу

<sumWhile>:
    pushq   %rbp
    movq    %rsp, %rbp
    xorl    %eax, %eax            # total = 0
    xorl    %ecx, %ecx            # i = 0
    cmpq    %rcx, %rsi            # len == i ?
    je      <sumWhile+0x16>       # проверка сверху: выход
    addq    (%rdi,%rcx,8), %rax   # total += a[i]
    incq    %rcx                  # i += 1
    jmp     <sumWhile+0x8>        # безусловно назад к проверке
    popq    %rbp
    retq

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

for это while, вплоть до байта

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

// for по срезу: индекс скрыт, но под капотом тот же while.
export fn sumFor(a: [*]const i64, len: usize) i64 {
    var total: i64 = 0;
    for (a[0..len]) |v| {
        total += v;
    }
    return total;
}

В объектнике этой функции нет отдельного тела. Компилятор увидел, что байты sumFor совпадают с байтами sumWhile, и слил два символа в один адрес. Это видно в таблице символов:

$ nm loops-small.o
0000000000000024 T sumFor
0000000000000024 T sumWhile
000000000000003c T sumDoWhile
0000000000000000 T sumNonNeg

sumFor и sumWhile указывают на один и тот же адрес 0x24: это свёртку одинакового кода. Не просто похожие циклы, а буквально одни байты, поэтому обе метки ссылаются на одну копию. Это лучший возможный ответ на вопрос, отличается ли for от while на уровне машины: нет, вплоть до байта. for берёт на себя счётчик и границу, но раскладка в переходы у него та же, что мы разобрали выше.

continue: переход к шагу или его исчезновение

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

// continue как настоящий переход: пропущенный элемент не пишется в dst.
export fn compactNonNeg(dst: [*]i64, src: [*]const i64, len: usize) usize {
    var w: usize = 0;
    var i: usize = 0;
    while (i < len) : (i += 1) {
        if (src[i] < 0) continue;
        dst[w] = src[i];
        w += 1;
    }
    return w;
}

$ zig build-obj compact.zig -O ReleaseSmall -target x86_64-linux -femit-bin=compact-small.o
$ objdump -d --no-show-raw-insn compact-small.o

<compactNonNeg>:
    pushq   %rbp
    movq    %rsp, %rbp
    xorl    %eax, %eax            # w = 0
    xorl    %ecx, %ecx            # i = 0
    cmpq    %rcx, %rdx            # i < len ?
    je      <compactNonNeg+0x22>  # нет: выход
    movq    (%rsi,%rcx,8), %r8    # r8 = src[i]
    testq   %r8, %r8              # src[i] < 0 ?
    js      <compactNonNeg+0x1d>  # да: continue, к шагу i += 1
    movq    %r8, (%rdi,%rax,8)    # dst[w] = src[i]
    incq    %rax                  # w += 1
    incq    %rcx                  # шаг цикла: i += 1
    jmp     <compactNonNeg+0x8>   # назад к проверке
    popq    %rbp
    retq

Вот он, continue, во плоти: js (jump if sign, то есть если число отрицательное) перепрыгивает через запись в приёмник и инкремент w прямо на инструкцию incq %rcx, которая и есть шаг цикла i += 1. Пропущенная итерация не трогает dst и не двигает w, ровно как в исходнике. continue это переход к шагу, и здесь он именно переходом и остался, потому что пропуск влияет на запись в память, которую нельзя предсказать одной командой.

Но так бывает не всегда. Если continue лишь исключает элемент из накопления, оптимизатор часто стирает ветвление совсем. Просуммируем только неотрицательные:

// Здесь continue лишь пропускает прибавление: оптимизатор уберёт ветвление.
export fn sumNonNeg(a: [*]const i64, len: usize) i64 {
    var total: i64 = 0;
    var i: usize = 0;
    while (i < len) : (i += 1) {
        if (a[i] < 0) continue;
        total += a[i];
    }
    return total;
}

<sumNonNeg>:
    pushq   %rbp
    movq    %rsp, %rbp
    xorl    %ecx, %ecx            # ноль для cmov
    xorl    %eax, %eax            # total = 0
    xorl    %edx, %edx            # i = 0
    cmpq    %rdx, %rsi            # i < len ?
    je      <sumNonNeg+0x22>
    movq    (%rdi,%rdx,8), %r8    # r8 = a[i]
    testq   %r8, %r8              # a[i] < 0 ?
    cmovleq %rcx, %r8             # если <= 0, заменить на 0 (без перехода)
    addq    %r8, %rax             # total += (a[i] или 0)
    incq    %rdx
    jmp     <sumNonNeg+0xa>
    popq    %rbp
    retq

Здесь никакого js и никакого прыжка через тело. Вместо этого cmovleq %rcx, %r8: если a[i] меньше или равно нулю, значение заменяется на заранее приготовленный ноль в %rcx, и тогда addq прибавляет ноль, что то же самое, что пропустить элемент. Это ровно приём из прошлого урока про cmov: убрать ветвление, чтобы не мучить предсказатель. Компилятор смог так сделать, потому что оба пути дешёвы и без побочных эффектов. Мораль: continue это не команда процессора, а намерение, и компилятор реализует его переходом или предикатом по обстоятельствам.

switch: таблица переходов

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

Возьмём switch над подряд идущими метками от 0 до 6, каждая со своей операцией:

// Плотный switch: подряд идущие метки 0 до 6. Компилятор строит таблицу переходов.
export fn denseOp(x: u64, a: i64, b: i64) i64 {
    return switch (x) {
        0 => a + b,
        1 => a - b,
        2 => a * b,
        3 => a & b,
        4 => a | b,
        5 => a ^ b,
        6 => a << @intCast(@as(u6, @truncate(@as(u64, @bitCast(b))))),
        else => -1,
    };
}

$ zig build-obj switches.zig -O ReleaseFast -target x86_64-linux -femit-bin=switches-fast.o
$ objdump -d --no-show-raw-insn switches-fast.o

<denseOp>:
    pushq   %rbp
    movq    %rsp, %rbp
    cmpq    $0x6, %rdi            # x > 6 (беззнаково) ?
    ja      <denseOp+0x29>        # да: в default
    movq    %rdx, %rax            # rax = a  (общий пролог веток)
    jmpq    *(,%rdi,8)            # косвенный переход: tab[x]
    addq    %rsi, %rax            # x=0: a + b
    popq    %rbp
    retq
    orq     %rsi, %rax            # x=4: a | b
    popq    %rbp
    retq
    imulq   %rsi, %rax            # x=2: a * b
    ...
    movq    $-0x1, %rax           # default: -1
    popq    %rbp
    retq

Ключевые три инструкции. cmpq $0x6, %rdi; ja это проверка границы: если x больше 6, беззнаковое сравнение отправляет в default. Одно сравнение отсекает всё, что вне диапазона меток, включая огромные значения. Дальше jmpq *(,%rdi,8) это косвенный переход: процессор берёт x, умножает на 8 (размер адреса), читает по этому смещению из таблицы 64-битный адрес ветки и прыгает туда. Не семь сравнений подряд, а одно чтение и один прыжок.

Сама таблица лежит в секции только для чтения. В ассемблерном листинге компилятора она выглядит как список адресов веток:

$ objdump -d switches-fast.s   # фрагмент .s: таблица переходов LLVM
.LJTI2_0:
    .quad  .LBB2_3      # x = 0
    .quad  .LBB2_4      # x = 1
    .quad  .LBB2_5      # x = 2
    .quad  .LBB2_6      # x = 3
    .quad  .LBB2_7      # x = 4
    .quad  .LBB2_8      # x = 5
    .quad  .LBB2_9      # x = 6

А в собранном бинарнике это семь восьмибайтовых адресов в .rodata. Слинкуем программу, которая зовёт denseOp, и посмотрим на настоящие байты таблицы:

$ objdump -d sw_exe        # адрес таблицы виден в самом переходе
    jmpq   *0x1000240(,%rdi,8)

$ objdump -s -j .rodata sw_exe
 1000240 e4a60101 00000000 02a70101 00000000  ................
 1000250 eea60101 00000000 f4a60101 00000000  ................
 1000260 e9a60101 00000000 0aa70101 00000000  ................
 1000270 0fa70101 00000000                     ........

Читаем таблицу как семь little-endian адресов. Слот 0 это 0x0101a6e4, адрес ветки a + b. Слот 1 это 0x0101a702, ветка a - b. Слот 2 это 0x0101a6ee, ветка a * b. И так далее до слота 6. Значение x буквально служит индексом в этот массив адресов. Проверим, что функция ведёт себя как задумано, на a = 12, b = 3:

$ ./sw_exe
0 -> 15    # 12 + 3
1 -> 9     # 12 - 3
2 -> 36    # 12 * 3
3 -> 0     # 12 & 3
4 -> 15    # 12 | 3
5 -> 15    # 12 ^ 3
6 -> 96    # 12 << 3
7 -> -1    # default

Виджет ниже показывает эту механику вживую. Слева исходный switch как список пар “значение → тело”, справа таблица переходов. Выбери значение n кнопкой, и подсветится путь: проверка границы, индекс в таблицу, слот с адресом, ветка. Кнопки x меняют аргумент, чтобы видеть результат. Переключатель справа показывает тот же набор меток как дерево сравнений, а второй пресет с далеко разнесёнными метками объясняет, почему таблицу не всегда строят.

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

Разреженный switch: дерево сравнений

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

// Разреженный switch: далеко разнесённые метки. Таблица была бы огромной.
export fn sparseOp(x: u64, a: i64) i64 {
    return switch (x) {
        1 => a + 1,
        100 => a + 2,
        1000 => a + 3,
        100000 => a + 4,
        else => 0,
    };
}

<sparseOp>:
    pushq   %rbp
    movq    %rsp, %rbp
    xorl    %eax, %eax            # заготовка результата default = 0
    cmpq    $0x3e7, %rdi          # x > 999 ?
    jg      <sparseOp+0x24>       # да: в верхнюю половину (1000, 100000)
    cmpq    $0x1, %rdi            # x == 1 ?
    je      <sparseOp+0x3f>       #   ветка a + 1
    cmpq    $0x64, %rdi           # x == 100 ?
    jne     <sparseOp+0x3d>       #   нет: default
    addq    $0x2, %rsi            #   ветка a + 2
    movq    %rsi, %rax
    popq    %rbp
    retq
    cmpq    $0x3e8, %rdi          # x == 1000 ?
    je      <sparseOp+0x48>       #   ветка a + 3
    cmpq    $0x186a0, %rdi        # x == 100000 ?
    jne     <sparseOp+0x3d>       #   нет: default
    addq    $0x4, %rsi            #   ветка a + 4
    ...

Здесь нет ни таблицы, ни косвенного перехода. Вместо этого дерево: первое сравнение cmpq $0x3e7 (это 999) с переходом jg делит все метки на две половины, нижнюю с 1 и 100 и верхнюю с 1000 и 100000. Дальше в каждой половине идут точечные сравнения на равенство. Чтобы выбрать ветку из четырёх, процессор делает не больше двух сравнений, а не четыре подряд: двоичный поиск, разложенный в переходы. Чем больше меток, тем заметнее выигрыш дерева над линейной цепочкой, и тем сильнее оба проигрывают таблице, если метки удаётся уложить плотно.

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

switch с диапазонами: одно беззнаковое сравнение

В Zig ветка switch может покрывать диапазон значений: 0...9, 'a'...'z'. Это удобно для разбора символов, и компилятор превращает проверку диапазона в один трюк, который ты уже видел в разговоре про сравнения: вычитание базы и беззнаковое сравнение. Классифицируем байт.

// switch с диапазонами: одна ветка на диапазон значений.
export fn classifyByte(x: u8) i64 {
    return switch (x) {
        0...9 => 1,
        'a'...'z' => 2,
        'A'...'Z' => 3,
        else => 0,
    };
}

<classifyByte>:
    pushq   %rbp
    movq    %rsp, %rbp
    movl    $0x1, %eax            # заготовка: результат 1
    cmpb    $0x9, %dil            # x <= 9 ?
    jbe     <classifyByte+0x2d>   # да: диапазон 0..9, вернуть 1
    leal    -0x61(%rdi), %ecx     # ecx = x - 'a'  ('a' = 0x61)
    movl    $0x2, %eax            # заготовка: результат 2
    cmpb    $0x1a, %cl            # (x - 'a') < 26 ?
    jb      <classifyByte+0x2d>   # да: диапазон a..z, вернуть 2
    addb    $-0x41, %dil          # dil = x - 'A'  ('A' = 0x41)
    xorl    %eax, %eax
    cmpb    $0x1a, %dil           # (x - 'A') < 26 ?
    setb    %al                  # al = 1, если да
    leaq    (%rax,%rax,2), %rax   # rax = al * 3  (0 или 3)
    popq    %rbp
    retq

Смотри, как проверяется диапазон 'a'...'z'. Вместо двух сравнений x >= 'a' и x <= 'z' компилятор пишет leal -0x61(%rdi), %ecx, то есть x - 'a', а затем одно беззнаковое cmpb $0x1a, %cl; jb. Если x меньше 'a', разность становится большим беззнаковым числом и сравнение проваливается; если больше 'z', разность больше 25 и тоже мимо. Одно вычитание и одно беззнаковое сравнение вместо двух проверок с границами. Диапазон 'A'...'Z' в конце оформлен ещё хитрее: результат setb даёт 0 или 1, а leaq (%rax,%rax,2) умножает на 3, превращая единицу сразу в тройку. Диапазоны в switch это не роскошь языка, а сахар над той же арифметикой сравнений.

labeled switch: computed goto без цикла

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

const Op = enum(u8) { push, add, mul, halt };

// Классика: цикл вокруг switch. Один общий переход по таблице на все опкоды.
export fn runLoop(code: [*]const u8) i64 {
    var stack: [32]i64 = undefined;
    var sp: usize = 0;
    var pc: usize = 0;
    while (true) {
        switch (@as(Op, @enumFromInt(code[pc]))) {
            .push => {
                stack[sp] = code[pc + 1];
                sp += 1;
                pc += 2;
            },
            .add => {
                stack[sp - 2] += stack[sp - 1];
                sp -= 1;
                pc += 1;
            },
            .mul => {
                stack[sp - 2] *= stack[sp - 1];
                sp -= 1;
                pc += 1;
            },
            .halt => return stack[sp - 1],
        }
    }
}

// labeled switch: каждая ветка сама прыгает к следующему опкоду.
export fn runLabeled(code: [*]const u8) i64 {
    var stack: [32]i64 = undefined;
    var sp: usize = 0;
    var pc: usize = 0;
    dispatch: switch (@as(Op, @enumFromInt(code[pc]))) {
        .push => {
            stack[sp] = code[pc + 1];
            sp += 1;
            pc += 2;
            continue :dispatch @enumFromInt(code[pc]);
        },
        .add => {
            stack[sp - 2] += stack[sp - 1];
            sp -= 1;
            pc += 1;
            continue :dispatch @enumFromInt(code[pc]);
        },
        .mul => {
            stack[sp - 2] *= stack[sp - 1];
            sp -= 1;
            pc += 1;
            continue :dispatch @enumFromInt(code[pc]);
        },
        .halt => return stack[sp - 1],
    }
}

Разница видна в ассемблере как число косвенных переходов. У runLabeled каждая ветка заканчивается своим собственным jmpq *(,%rdx,8): диспетчер реплицирован в каждую ветку.

$ zig build-obj dispatch.zig -O ReleaseSmall -target x86_64-linux -femit-bin=dispatch-small.o
$ objdump -d --no-show-raw-insn dispatch-small.o

<runLabeled>:
    pushq   %rbp
    movq    %rsp, %rbp
    subq    $0x80, %rsp
    movzbl  (%rdi), %edx          # прочитать первый опкод
    xorl    %ecx, %ecx            # sp = 0
    xorl    %eax, %eax            # pc = 0
    jmpq    *(,%rdx,8)            # диспетчер: переход по опкоду
    movzbl  0x1(%rdi,%rax), %edx  # .push: значение
    movq    %rdx, -0x100(%rbp,%rcx,8)
    incq    %rcx
    movzbl  0x2(%rdi,%rax), %edx  # прочитать следующий опкод прямо здесь
    addq    $0x2, %rax
    jmpq    *(,%rdx,8)            # и сразу прыгнуть: свой диспетчер ветки
    movq    -0x108(%rbp,%rcx,8), %rdx  # .add
    addq    %rdx, -0x110(%rbp,%rcx,8)
    decq    %rcx
    movzbl  0x1(%rdi,%rax), %edx
    incq    %rax
    jmpq    *(,%rdx,8)            # ещё один диспетчер
    ...

Вот та самая механика computed goto: в конце ветки .push не возврат к общей точке, а чтение следующего опкода и собственный jmpq *(,%rdx,8) прямо здесь. У каждой ветки свой косвенный переход, и в этой машине их четыре.

Зачем это нужно, объясняет предсказатель ветвлений. Один общий jmp в классическом цикле процессор видит как единственную точку, через которую подряд проходят все опкоды: история переходов там перемешана, и предсказание плохое. Когда у каждой ветки свой jmp, предсказатель ведёт отдельную историю для каждого перехода, и последовательности вроде “за сложением обычно идёт запись” начинают предсказываться. Именно ради этого интерпретаторы на C прибегают к расширению goto *table[op], а Zig даёт то же самое встроенной конструкцией.

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

$ objdump -d ... | подсчёт инструкций jmpq *
                 runLoop   runLabeled
Debug (-O0)         1           4
ReleaseSmall        4           4
ReleaseFast         4           4

Без оптимизаций у обычного цикла ровно один общий диспетчер (jmpq *%rax в конце тела), а labeled switch реплицирует переход всегда, потому что это часть семантики языка, а не оптимизация. В режиме оптимизации LLVM догоняет обычный цикл до той же формы. Смысл labeled switch не в том, что он делает невозможное, а в том, что он выражает намерение и гарантирует нужную раскладку на уровне языка, не полагаясь на удачу оптимизатора. Оба шага проекта zl ниже опираются на это.

Шаг проекта: zt учится косвенным переходам

После прошлого шага zt disasm читает переходы, у которых цель записана прямо в инструкции смещением. Таблица переходов устроена иначе: цели в инструкции нет, она лежит в памяти. Возьми фикстуру этого шага, где ztDenseOp это denseOp из раздела про таблицу переходов, только с другим именем, и посмотри, что печатал zt после урока 12:

$ ./zig-out/bin/zt disasm fixtures/step_13.o
...
      30: 55                           	pushq	%rbp
      31: 48 89 e5                     	movq	%rsp, %rbp
      34: 48 83 ff 06                  	cmpq	$0x6, %rdi
      38: 77 1f                        	ja	0x59
      3a: 48 89 d0                     	movq	%rdx, %rax
      3d: ff                           	(bad)
      3e: 24 fd                        	andb	$-0x3, %al
      40: 00 00                        	addb	%al, (%rax)
      42: 00 00                        	addb	%al, (%rax)
      44: 48 01 f0                     	addq	%rsi, %rax

Самая важная инструкция функции рассыпалась на четыре строки. Декодер не узнал ff 24, отступил на байт и нашёл в хвосте правдоподобную арифметику: 24 fd это настоящий andb с числом, а четыре нуля на месте адреса таблицы выглядят как два addb. Разбору повезло, что нулей чётное число и строка 44 снова попала на границу инструкции. Но читатель такого листинга не увидит в функции ни одного перехода по таблице, а ради него функция и написана.

Байты косвенного перехода

Разберём ff 24 fd 00 00 00 00 по полям, как в уроке про операнды.

• ff это не одна инструкция, а группа из восьми. Какая именно, решает поле reg следующего байта. В уроке 11 из этой группы понадобились номера 0 и 1, inc и dec.
• 24 это байт ModRM: mod равно 00, reg равно 100, rm равно 100. Номер операции 4 означает косвенный jmp, а rm равное 4 означает, что дальше идёт байт SIB.
• fd это SIB: масштаб 11 (множитель 8), индекс 111 (%rdi), база 101. База 5 при mod равном нулю это особый случай из урока 10: базы нет, за SIB идут четыре байта смещения.
• 00 00 00 00 это смещение, то есть адрес таблицы. В объектнике он ещё неизвестен, на его месте нули, а рядом лежит заплатка для компоновщика:

$ objdump -dr fixtures/step_13.o | sed -n '/<ztDenseOp>/,/ 44:/p'
0000000000000030 <ztDenseOp>:
      30: 55                           	pushq	%rbp
      31: 48 89 e5                     	movq	%rsp, %rbp
      34: 48 83 ff 06                  	cmpq	$0x6, %rdi
      38: 77 1f                        	ja	0x59 <ztDenseOp+0x29>
      3a: 48 89 d0                     	movq	%rdx, %rax
      3d: ff 24 fd 00 00 00 00         	jmpq	*(,%rdi,8)
		0000000000000040:  R_X86_64_32S	.rodata
      44: 48 01 f0                     	addq	%rsi, %rax

Перемещение R_X86_64_32S по адресу 0x40 говорит: сюда впиши адрес начала .rodata, четыре байта со знаком. Ровно туда и указывают нули, три байта от начала инструкции. Итого инструкция читает восьмибайтное число по адресу .rodata + %rdi * 8 и прыгает туда, куда оно показывает. Звёздочка в jmpq *(,%rdi,8) это способ AT&T сказать «не сюда, а по адресу, который здесь лежит».

Саму таблицу тоже можно прочитать, не запуская компоновщик. Это семь записей в .rodata, и каждой положено своё перемещение:

$ objdump -r fixtures/step_13.o | sed -n '/\[.rodata\]/,/^$/p'
RELOCATION RECORDS FOR [.rodata]:
OFFSET           TYPE                     VALUE
0000000000000000 R_X86_64_64              .text+0x44
0000000000000008 R_X86_64_64              .text+0x62
0000000000000010 R_X86_64_64              .text+0x4e
0000000000000018 R_X86_64_64              .text+0x54
0000000000000020 R_X86_64_64              .text+0x49
0000000000000028 R_X86_64_64              .text+0x6a
0000000000000030 R_X86_64_64              .text+0x6f

Слот 0 ведёт на 0x44, где стоит addq, то есть на ветку a + b. Слот 1 ведёт на 0x62 с subq, слот 2 на 0x4e с imulq. Ветки лежат в .text не в том порядке, в каком их перечисляет switch: компилятор расставил их как удобно, а порядок меток хранит таблица. Сверишь остальные четыре слота по листингу ниже сам.

Флаг у инструкции и звёздочка в форматтере

Теперь код. Косвенный переход печатается со звёздочкой, и форматтер должен откуда-то узнать, что она нужна. Операнд тут обычный, регистр или адрес, поэтому признак живёт в самой инструкции. В src/x86/instruction.zig у Instruction появляется поле, сразу после operand_count:

    /// Операнд печатается со звёздочкой: косвенные `jmp *%rax` и `call *(%rax)`.
    indirect: bool = false,

В src/x86/formatter.zig цикл печати операндов в format ставит звёздочку перед первым операндом:

    for (operands, 0..) |operand, position| {
        if (position > 0) try out.writeAll(", ");
        // Звёздочка отличает косвенный переход от перехода по адресу:
        // `jmp *%rax` идёт по значению регистра, `jmp 0x40` по метке.
        if (inst.indirect and position == 0) try out.writeByte('*');
        try formatOperand(out, operand);
    }

Группа 0xFF получает переходы

В src/x86/ops_branch.zig, после jump, новая функция:

/// Хвост группы 0xFF: косвенный вызов (`/2`) и косвенный переход (`/4`).
/// Косвенный значит, что адрес цели не записан в инструкции, а лежит в
/// регистре или в памяти. Так выглядит переход по таблице: `jmpq *(,%rdi,8)`.
pub fn indirect(cursor: *Cursor, digit: u3, rm: instruction.Operand) ?Instruction {
    const mnemonic = switch (digit) {
        2 => "call",
        4 => "jmp",
        else => return null,
    };
    var result = cursor.one(mnemonic, 'q', rm);
    result.indirect = true;
    return result;
}

Вызов попал сюда же, хотя урок про таблицы переходов: callq *%rax отличается от jmpq *%rax ровно одним битом поля reg (2 против 4), и держать их порознь незачем. Прямой вызов по смещению, e8, придёт в следующем уроке вместе с разговором про кадры. Номера 3 и 5 это дальние вызов и переход с селектором сегмента, компилятор их не выдаёт, а номер 6, push из памяти, понадобится только в уроке про динамическую компоновку.

Главное изменение в src/x86/decoder.zig. Функция group5 из урока 11 читала ModRM с шириной операнда и отдавала всё incrementDecrement. Теперь ей надо заглянуть в поле reg до чтения ModRM:

/// Группа 0xFE и 0xFF: инкремент и декремент, а у 0xFF ещё косвенные
/// вызов и переход. Те работают с восемью байтами без REX.W, поэтому
/// ModRM для них читаем с шириной qword.
fn group5(cursor: *Cursor, size: Size, comptime has_branches: bool) ?Instruction {
    const digit: u3 = @truncate((cursor.peek() orelse return null) >> 3);
    if (has_branches and digit >= 2) {
        const modrm = cursor.readModRm(.qword) orelse return null;
        return branch.indirect(cursor, modrm.digit, modrm.rm);
    }
    const modrm = cursor.readModRm(size) orelse return null;
    return alu.incrementDecrement(cursor, modrm.digit, modrm.rm, size);
}

И две строки таблицы, которые её зовут:

        0xfe => group5(cursor, .byte, false),
        0xff => group5(cursor, wide, true),

Зачем подглядывать через peek. Ширина регистра в поле rm зависит от операции. У incq %rax она берётся из префиксов: без REX.W это incl %eax. У jmpq *%rax она всегда восемь байтов: адрес в 64-битном режиме другим не бывает, и процессор не ждёт REX.W. Если прочитать ModRM с шириной из префиксов, ff e0 превратится в jmpq *%eax: суффикс верный, регистр половинный, и такой инструкции не существует. Поэтому сначала смотрим номер операции, а потом решаем, с какой шириной читать операнд. readModRm потом всё равно съест этот байт целиком: peek ничего не сдвигает.

Параметр has_branches помечен comptime, и это не украшение. У 0xfe номера со второго по седьмой не определены, байтовых переходов не бывает. Вместо проверки опкода в рантайме у функции две версии, собранные компилятором: в версии для 0xfe ветка с переходами вырезана целиком.

Осталась обещанная в прошлом уроке загадка префикса 0x3e. Перед косвенным переходом LLVM ставит его как notrack, пометку для защиты потока управления, а перед обращением в память это замена сегмента на %ds. Курсор запоминает оба смысла, и оказалось, что различать их не нужно. Если адрес цели в регистре, сегмент печатать некуда, и 3e ff e0 выходит просто jmpq *%rax. Если в памяти, LLVM и сам печатает jmpq *%ds:(,%rdi,8). Наш форматтер делает то же самое без единой новой строки.

Фикстура и тесты шага

Фикстура состоит из двух функций: настоящий switch, собранный компилятором, и функция на ассемблере со всеми формами адреса цели, которые встречаются в коде:

//! Фикстура шага 13: косвенные переходы и таблица переходов.
//!
//! Собирается так:
//!   zig build-obj fixtures/step_13.zig -O ReleaseFast \
//!       -target x86_64-linux-musl -femit-bin=fixtures/step_13.o

/// Плотный switch из урока: метки от 0 до 6 подряд, поэтому компилятор
/// строит таблицу переходов и выбирает ветку одним `jmpq *(,%rdi,8)`.
/// Адрес таблицы в объектнике ещё не известен: на его месте нули, которые
/// заполнит компоновщик.
export fn ztDenseOp(x: u64, a: i64, b: i64) i64 {
    return switch (x) {
        0 => a + b,
        1 => a - b,
        2 => a * b,
        3 => a & b,
        4 => a | b,
        5 => a ^ b,
        6 => a << @intCast(@as(u6, @truncate(@as(u64, @bitCast(b))))),
        else => -1,
    };
}

/// Все формы косвенного перехода и вызова, которые встречаются в коде
/// компилятора: адрес цели в регистре, в памяти по базе, по базе с индексом
/// и по индексу без базы, как у таблицы переходов.
export fn ztIndirect() callconv(.naked) void {
    asm volatile (
        \\jmpq *%rax
        \\jmpq *%r11
        \\jmpq *(%rax)
        \\jmpq *0x8(%rax,%rcx,8)
        \\jmpq *0x10(,%rdi,8)
        \\jmpq *(,%rdx,8)
        \\notrack jmpq *%rax
        \\callq *%rax
        \\callq *%r12
        \\callq *0x18(%rbx)
        \\ret
    );
}

zig build-obj fixtures/step_13.zig -O ReleaseFast \
    -target x86_64-linux-musl -femit-bin=fixtures/step_13.o
objdump -d fixtures/step_13.o > fixtures/step_13.objdump.txt

В fixtures/root.zig рядом с шагом 12 новая запись:

pub const step_13 = Fixture{
    .object = @embedFile("step_13.o"),
    .objdump = @embedFile("step_13.objdump.txt"),
};

Тесты в tests/step_13.zig:

//! Шаг 13: косвенные переходы и вызовы, таблица переходов.
//!
//! У косвенного перехода адреса цели в инструкции нет: он лежит в регистре
//! или в памяти. Кодируется это группой 0xFF, где поле reg байта ModRM
//! выбирает операцию, а поле r/m описывает, откуда брать адрес, теми же
//! одиннадцатью формами, что и у `mov`.

const std = @import("std");

const fixtures = @import("fixtures");
const zt = @import("zt");

const support = @import("support.zig");

const decode = zt.x86.decoder.decode;

test "фикстура шага разбирается целиком" {
    try support.expectNoBadInstructions(fixtures.step_13);
}

test "вывод совпадает с objdump построчно" {
    try support.expectMatchesObjdump(fixtures.step_13);
}

test "предыдущие шаги остались зелёными" {
    try support.expectMatchesObjdump(fixtures.step_09);
    try support.expectMatchesObjdump(fixtures.step_10);
    try support.expectMatchesObjdump(fixtures.step_11);
    try support.expectMatchesObjdump(fixtures.step_12);
}

test "переход по таблице: индекс без базы, масштаб 8" {
    // ff 24 fd 00 00 00 00: база 5 при mod 0 значит «базы нет, дальше disp32».
    // На месте disp32 нули: адрес таблицы впишет компоновщик.
    try expectOne(&.{ 0xff, 0x24, 0xfd, 0x00, 0x00, 0x00, 0x00 }, "jmpq\t*(,%rdi,8)");
    try expectOne(&.{ 0xff, 0x24, 0xfd, 0x10, 0x00, 0x00, 0x00 }, "jmpq\t*0x10(,%rdi,8)");
}

test "адрес цели в регистре или в памяти" {
    try expectOne(&.{ 0xff, 0xe0 }, "jmpq\t*%rax");
    try expectOne(&.{ 0x41, 0xff, 0xe3 }, "jmpq\t*%r11");
    try expectOne(&.{ 0xff, 0x20 }, "jmpq\t*(%rax)");
    try expectOne(&.{ 0xff, 0x64, 0xc8, 0x08 }, "jmpq\t*0x8(%rax,%rcx,8)");
}

test "поле reg выбирает операцию группы: 2 это call, 4 это jmp" {
    try expectOne(&.{ 0xff, 0xd0 }, "callq\t*%rax");
    try expectOne(&.{ 0x41, 0xff, 0xd4 }, "callq\t*%r12");
    try expectOne(&.{ 0xff, 0x53, 0x18 }, "callq\t*0x18(%rbx)");
    // Те же байты ModRM с reg 0 и 1 это inc и dec из шага 11.
    try expectOne(&.{ 0x48, 0xff, 0xc0 }, "incq\t%rax");
}

test "косвенный переход всегда восьмибайтный, REX.W ему не нужен" {
    const jump = decode(&.{ 0xff, 0xe0 }, 0);
    try std.testing.expect(jump.indirect);
    try std.testing.expectEqual(@as(?u8, 'q'), jump.suffix);
    try std.testing.expectEqualStrings("rax", jump.operandSlice()[0].register.name());
}

test "префикс notrack не печатается" {
    // 3e перед косвенным переходом это пометка для защиты потока управления.
    try expectOne(&.{ 0x3e, 0xff, 0xe0 }, "jmpq\t*%rax");
}

/// Прогоняет байты через декодер и форматтер и сверяет мнемонику с операндами.
fn expectOne(code: []const u8, expected: []const u8) !void {
    const decoded = decode(code, 0);
    try std.testing.expectEqual(code.len, decoded.length());

    var buffer: [256]u8 = undefined;
    var out: std.Io.Writer = .fixed(&buffer);
    try zt.x86.formatter.format(&out, decoded);
    try std.testing.expectEqualStrings(expected, out.buffered());
}

Тест про incq в группе переходов нужен как сторож. Самая лёгкая ошибка этого шага: переписать group5 так, что ветка переходов съест и номера 0 и 1. Тогда 48 ff c0 перестанет быть incq, и заметит это только фикстура урока 11, если в ней случится inc. Лучше, чтобы о границе между двумя половинами группы помнил отдельный тест.

И номер шага в build.zig: const project_steps = [_]u8{ 6, 7, 9, 10, 11, 12, 13 };.

Прогон

$ zig build test -Dstep=13 --summary all
Build Summary: 3/3 steps succeeded; 8/8 tests passed
test success
+- run test 8 pass (8 total) 13ms MaxRSS:3M

Флаг -Dstep=13 гоняет только тесты шага, но среди них есть «предыдущие шаги остались зелёными», так что фикстуры уроков 9 до 12 проверены тоже. Полный zig build test прогонит ещё и встроенные тесты модулей.

Функция со switch теперь читается целиком:

$ ./zig-out/bin/zt disasm fixtures/step_13.o | sed -n '/ 30:/,$p'
      30: 55                           	pushq	%rbp
      31: 48 89 e5                     	movq	%rsp, %rbp
      34: 48 83 ff 06                  	cmpq	$0x6, %rdi
      38: 77 1f                        	ja	0x59
      3a: 48 89 d0                     	movq	%rdx, %rax
      3d: ff 24 fd 00 00 00 00         	jmpq	*(,%rdi,8)
      44: 48 01 f0                     	addq	%rsi, %rax
      47: 5d                           	popq	%rbp
      48: c3                           	retq
      49: 48 09 f0                     	orq	%rsi, %rax
      4c: 5d                           	popq	%rbp
      4d: c3                           	retq
      4e: 48 0f af c6                  	imulq	%rsi, %rax
      52: 5d                           	popq	%rbp
      53: c3                           	retq
      54: 48 21 f0                     	andq	%rsi, %rax
      57: 5d                           	popq	%rbp
      58: c3                           	retq
      59: 48 c7 c0 ff ff ff ff         	movq	$-0x1, %rax
      60: 5d                           	popq	%rbp
      61: c3                           	retq
      62: 48 29 c6                     	subq	%rax, %rsi
      65: 48 89 f0                     	movq	%rsi, %rax
      68: 5d                           	popq	%rbp
      69: c3                           	retq
      6a: 48 31 f0                     	xorq	%rsi, %rax
      6d: 5d                           	popq	%rbp
      6e: c3                           	retq
      6f: 89 c1                        	movl	%eax, %ecx
      71: 48 d3 e6                     	shlq	%cl, %rsi
      74: 48 89 f0                     	movq	%rsi, %rax
      77: 5d                           	popq	%rbp
      78: c3                           	retq

Положи рядом таблицу из .rodata, и функцию можно восстановить, не глядя в исходник: семь адресов веток, каждая из двух или трёх инструкций, плюс default на 0x59, куда ведёт ja. Ветка 0x62 (x равен 1) интереснее соседних. Общую для всех веток пересылку movq %rdx, %rax компилятор вынес перед jmpq, и пять веток сразу работают над %rax. Двум оставшимся это не подошло. У вычитания важен порядок, a - b не равно b - a, поэтому разность считается в %rsi и перекладывается в %rax отдельной инструкцией. Сдвигу число b нужно в %cl, и ветка 0x6f тоже работает над %rsi.

Сравнение с objdump -d по-прежнему расходится только подписями: заголовков <ztDenseOp>: и имён вроде <ztDenseOp+0x29> после адреса цели у zt нет. Подписям нужна таблица символов, и в следующем уроке zt научится брать её готовой.

Шаг проекта: zl получает байткод и два диспетчера

До этого урока zl исполнял программу одним способом: обходом дерева. eval берёт форму, смотрит, что у неё в голове, и рекурсивно считает потомков. Посмотри, сколько работы уходит на один вызов (fib (- n 1)) внутри fib. eval проверяет, что форма это пара и что в голове символ, сравнивает символ с quote, cond, lambda и define, ищет fib сначала в списке пар окружения, потом в глобальной карте, вычисляет аргументы, собирает их в новый список из ячеек кучи, связывает n с новым значением, добавляя в окружение ещё две ячейки, и только потом берётся за тело. Всё это заново на каждом из двадцати тысяч вызовов, хотя сама форма не меняется ни разу.

Байткод выносит эти решения в момент компиляции. Компилятор один раз проходит по телу lambda и записывает ответы в плоский массив команд: здесь положить аргумент номер ноль, здесь позвать функцию с двумя аргументами. Машине остаётся идти по массиву и на каждую команду делать один выбор по опкоду. Этот выбор и есть switch из урока, и на нём мы сравним две формы диспетчера, которые только что разобрали на игрушечной машине: цикл вокруг switch и labeled switch.

Итог шага: три исполнителя одной программы. Тесты гоняют каждую программу из programs/ через все три и сверяют ответы, а в ассемблере видно, чем исполнители отличаются.

Устройство машины

Машина стековая, как runLoop выше. Команда берёт операнды с вершины стека значений и кладёт результат туда же. Аргументы функции это тоже слоты стека: к моменту вызова функция и её аргументы уже лежат на стеке подряд, и машине достаточно запомнить, где начинается первый аргумент. Параметр n в теле fib превращается в команду «положить слот номер 0 от начала кадра», без всякого поиска.

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

Команда	Операнд	Что делает
constant	номер константы	кладёт константу на стек
arg	номер параметра	кладёт аргумент текущей функции
name	номер константы с символом	ищет имя в окружении замыкания, потом среди глобальных
jump_if_nil	номер команды	снимает значение; если это nil, переходит
jump	номер команды	переходит
closure	номер константы (параметры тело)	собирает замыкание
define	номер константы с символом	снимает значение и связывает его глобально
call	число аргументов	зовёт функцию, лежащую под аргументами
tail_call	число аргументов	то же из хвостовой позиции, без нового кадра
ret	не нужен	возвращает вершину стека вызывающему

Константы (числа, цитаты, символы) лежат в одном общем списке машины, команда хранит только номер. Команда целиком занимает восемь байт: опкод и 32-битный операнд.

Кадр вызова это запись { chunk, pc, base }: какой код исполняется, номер следующей команды и номер слота первого аргумента. Под первым аргументом, в слоте base - 1, лежит сама вызванная функция. Она нужна, чтобы найти окружение замыкания, а после возврата её слот займёт результат. Кадры живут в отдельном массиве машины, а не на стеке Zig, поэтому рекурсия в программе на zl не становится рекурсией интерпретатора.

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

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

bytecode.zig

Новый файл целиком:

//! Байткод zl: компилятор дерева в команды стековой машины и два диспетчера.
//!
//! Обход дерева на каждом узле заново выясняет, что перед ним: число, имя,
//! специальная форма или вызов. Компилятор выясняет это один раз и кладёт
//! ответ в плоский массив команд. Машине остаётся идти по массиву и на каждую
//! команду делать один выбор по опкоду.
//!
//! Машина стековая: команды берут операнды с вершины стека значений и кладут
//! результат туда же. Аргументы функции это слоты того же стека, поэтому
//! параметр читается по номеру слота, без поиска по списку пар.
//!
//! Диспетчеров два, и байткод у них общий: цикл вокруг `switch` и labeled
//! switch, в котором каждая ветка сама прыгает к следующей команде.

const std = @import("std");

const errors = @import("errors.zig");
const eval = @import("eval.zig");
const primitives = @import("primitives.zig");
const reader = @import("reader.zig");
const value = @import("value.zig");
const Vm = @import("vm.zig").Vm;

const Error = errors.Error;
const Value = value.Value;

pub const SourceError = Error || reader.Error;

pub const Op = enum(u8) {
    /// Положить константу номер `arg`.
    constant,
    /// Положить аргумент текущей функции номер `arg`.
    arg,
    /// Положить значение имени. Символ лежит в константе номер `arg`, имя
    /// ищется в окружении замыкания, потом среди глобальных.
    name,
    /// Снять значение со стека и, если это nil, перейти на команду `arg`.
    jump_if_nil,
    /// Перейти на команду `arg`.
    jump,
    /// Собрать замыкание. Константа номер `arg` это `(параметры тело)`.
    closure,
    /// Снять значение и связать глобально с символом из константы `arg`.
    define,
    /// Вызвать: на стеке функция и над ней `arg` аргументов.
    call,
    /// Тот же вызов из хвостовой позиции: кадр вызывающего переиспользуется.
    tail_call,
    /// Вернуть вершину стека вызывающему.
    ret,
};

pub const Instr = struct {
    op: Op,
    arg: u32 = 0,
};

/// Скомпилированная функция или форма верхнего уровня.
pub const Chunk = struct {
    code: std.ArrayList(Instr) = .empty,
    /// Список параметров. Параметр номер i лежит в слоте `base + i`.
    params: Value = .nil,
    arity: u32 = 0,

    pub fn deinit(self: *Chunk, gpa: std.mem.Allocator) void {
        self.code.deinit(gpa);
        self.* = undefined;
    }

    /// Только опкоды, без аргументов. Удобно сверять в тестах.
    pub fn ops(self: *const Chunk, buf: []Op) []Op {
        for (self.code.items, 0..) |ins, i| buf[i] = ins.op;
        return buf[0..self.code.items.len];
    }
};

/// Кадр вызова. Под первым аргументом на стеке лежит сама вызванная функция:
/// через неё машина находит окружение замыкания.
pub const Frame = struct {
    chunk: *const Chunk,
    /// Номер следующей команды.
    pc: u32,
    /// Номер слота первого аргумента на стеке значений.
    base: u32,
};

pub const Dispatch = enum {
    /// Цикл вокруг `switch`: один общий переход по таблице на все команды.
    loop,
    /// labeled switch: у каждой ветки свой переход к следующей команде.
    labeled,
};

/// Тело функции узнаётся по паре (параметры, тело): её выдаёт `asClosure`,
/// и она одна и та же у всех замыканий, собранных из одной `lambda`.
const FunctionKey = struct {
    params: Value,
    body: Value,
};

pub const Machine = struct {
    vm: *Vm,
    /// Константы всех скомпилированных функций. Команда хранит только номер.
    constants: std.ArrayList(Value) = .empty,
    /// Стек значений: аргументы, промежуточные результаты, вызванные функции.
    stack: std.ArrayList(Value) = .empty,
    frames: std.ArrayList(Frame) = .empty,
    /// Тела функций компилируются при первом вызове и дальше берутся отсюда.
    functions: std.AutoHashMapUnmanaged(FunctionKey, *Chunk) = .empty,
    /// Наибольшая глубина кадров за жизнь машины.
    peak_frames: usize = 0,

    pub fn init(vm: *Vm) Machine {
        return .{ .vm = vm };
    }

    pub fn deinit(self: *Machine) void {
        const gpa = self.vm.gpa;
        var chunks = self.functions.valueIterator();
        while (chunks.next()) |chunk| {
            chunk.*.deinit(gpa);
            gpa.destroy(chunk.*);
        }
        self.functions.deinit(gpa);
        self.frames.deinit(gpa);
        self.stack.deinit(gpa);
        self.constants.deinit(gpa);
        self.* = undefined;
    }

    /// Прочитать исходник и исполнить формы подряд, вернув значение последней.
    pub fn runSource(self: *Machine, source: []const u8, dispatch: Dispatch) SourceError!Value {
        var r: reader.Reader = .init(self.vm, source);
        var last: Value = .nil;
        while (try r.next()) |form| last = try self.runForm(form, dispatch);
        return last;
    }

    /// Скомпилировать одну форму верхнего уровня и исполнить её.
    pub fn runForm(self: *Machine, form: Value, dispatch: Dispatch) Error!Value {
        var chunk: Chunk = .{};
        defer chunk.deinit(self.vm.gpa);
        try self.compile(&chunk, .nil, form);

        // После ошибки на стеке остаются обломки прерванных вызовов. Машина
        // сбрасывает их, чтобы следующая форма начала с чистого листа.
        errdefer {
            self.stack.clearRetainingCapacity();
            self.frames.clearRetainingCapacity();
        }
        std.debug.assert(self.frames.items.len == 0);
        // Места вызванной функции у формы нет, его занимает nil.
        try self.push(.nil);
        try self.pushFrame(.{ .chunk = &chunk, .pc = 0, .base = 1 });
        return switch (dispatch) {
            .loop => self.runLoop(),
            .labeled => self.runLabeled(),
        };
    }

    // --- Два диспетчера ---
    //
    // Оба `noinline`: так каждый остаётся отдельной функцией в ассемблерном
    // листинге и в профиле, и их можно сравнивать бок о бок.

    /// Классика: цикл вокруг `switch`. Команда выбирается в одном месте.
    noinline fn runLoop(self: *Machine) Error!Value {
        var frame = self.top();
        while (true) {
            const ins = frame.chunk.code.items[frame.pc];
            frame.pc += 1;
            switch (ins.op) {
                .constant => try self.push(self.constants.items[ins.arg]),
                .arg => try self.push(self.stack.items[frame.base + ins.arg]),
                .name => try self.push(try self.lookup(frame, ins.arg)),
                .jump_if_nil => if (self.pop().isNil()) {
                    frame.pc = ins.arg;
                },
                .jump => frame.pc = ins.arg,
                .closure => try self.push(try self.makeClosure(frame, ins.arg)),
                .define => try self.define(ins.arg),
                .call => {
                    try self.call(ins.arg);
                    frame = self.top();
                },
                .tail_call => {
                    try self.tailCall(ins.arg);
                    frame = self.top();
                },
                .ret => {
                    if (self.ret()) |result| return result;
                    frame = self.top();
                },
            }
        }
    }

    /// labeled switch: каждая ветка сама читает следующую команду и через
    /// `continue :dispatch` прыгает прямо в её ветку, минуя общую точку.
    noinline fn runLabeled(self: *Machine) Error!Value {
        var frame = self.top();
        var ins = fetch(frame);
        dispatch: switch (ins.op) {
            .constant => {
                try self.push(self.constants.items[ins.arg]);
                ins = fetch(frame);
                continue :dispatch ins.op;
            },
            .arg => {
                try self.push(self.stack.items[frame.base + ins.arg]);
                ins = fetch(frame);
                continue :dispatch ins.op;
            },
            .name => {
                try self.push(try self.lookup(frame, ins.arg));
                ins = fetch(frame);
                continue :dispatch ins.op;
            },
            .jump_if_nil => {
                if (self.pop().isNil()) frame.pc = ins.arg;
                ins = fetch(frame);
                continue :dispatch ins.op;
            },
            .jump => {
                frame.pc = ins.arg;
                ins = fetch(frame);
                continue :dispatch ins.op;
            },
            .closure => {
                try self.push(try self.makeClosure(frame, ins.arg));
                ins = fetch(frame);
                continue :dispatch ins.op;
            },
            .define => {
                try self.define(ins.arg);
                ins = fetch(frame);
                continue :dispatch ins.op;
            },
            .call => {
                try self.call(ins.arg);
                frame = self.top();
                ins = fetch(frame);
                continue :dispatch ins.op;
            },
            .tail_call => {
                try self.tailCall(ins.arg);
                frame = self.top();
                ins = fetch(frame);
                continue :dispatch ins.op;
            },
            .ret => {
                if (self.ret()) |result| return result;
                frame = self.top();
                ins = fetch(frame);
                continue :dispatch ins.op;
            },
        }
    }

    fn fetch(frame: *Frame) Instr {
        const ins = frame.chunk.code.items[frame.pc];
        frame.pc += 1;
        return ins;
    }

    // --- Команды, общие для обоих диспетчеров ---

    fn top(self: *Machine) *Frame {
        return &self.frames.items[self.frames.items.len - 1];
    }

    fn push(self: *Machine, v: Value) Error!void {
        try self.stack.append(self.vm.gpa, v);
    }

    fn pop(self: *Machine) Value {
        return self.stack.pop().?;
    }

    fn pushFrame(self: *Machine, frame: Frame) Error!void {
        try self.frames.append(self.vm.gpa, frame);
        self.peak_frames = @max(self.peak_frames, self.frames.items.len);
    }

    /// Окружение текущей функции: оно лежит в замыкании под аргументами.
    fn envOf(self: *Machine, frame: *const Frame) Value {
        const callee = self.stack.items[frame.base - 1];
        return if (callee.tag() == .closure) callee.asClosure().env else .nil;
    }

    fn lookup(self: *Machine, frame: *const Frame, index: u32) Error!Value {
        const id = self.constants.items[index].asSymbol();
        return eval.lookup(self.vm, id, self.envOf(frame)) orelse error.UnboundSymbol;
    }

    fn define(self: *Machine, index: u32) Error!void {
        const name = self.constants.items[index];
        try self.vm.define(name.asSymbol(), self.pop());
        try self.push(name);
    }

    /// Замыкание захватывает окружение списком пар, как у `eval`. Параметры
    /// текущей функции живут в слотах стека, поэтому переносятся в список.
    fn makeClosure(self: *Machine, frame: *const Frame, index: u32) Error!Value {
        const form = self.constants.items[index];
        var env = self.envOf(frame);
        var params = frame.chunk.params;
        var slot = frame.base;
        while (params.isCons()) : (params = params.asCell().cdr) {
            env = try eval.bind(self.vm, params.asCell().car.asSymbol(), self.stack.items[slot], env);
            slot += 1;
        }
        const body = form.asCell().cdr.asCell().car;
        return self.vm.heap.closure(form.asCell().car, body, env);
    }

    fn call(self: *Machine, argc: u32) Error!void {
        const base: u32 = @intCast(self.stack.items.len - argc);
        const callee = self.stack.items[base - 1];
        switch (callee.tag()) {
            .primitive => {
                // Примитив ждёт список аргументов: собираем его из слотов.
                var args: Value = .nil;
                var i = self.stack.items.len;
                while (i > base) {
                    i -= 1;
                    args = try self.vm.heap.cons(self.stack.items[i], args);
                }
                const result = try primitives.call(self.vm, callee.asPrimitive(), args);
                self.stack.shrinkRetainingCapacity(base);
                self.stack.items[base - 1] = result;
            },
            .closure => {
                const chunk = try self.functionOf(callee, argc);
                try self.pushFrame(.{ .chunk = chunk, .pc = 0, .base = base });
            },
            else => return error.NotApplicable,
        }
    }

    /// Хвостовой вызов замыкания: функция и аргументы переезжают на место
    /// текущих, кадр переиспользуется, и стек не растёт. Примитив в хвосте
    /// зовётся как обычно: своего кадра у него нет.
    fn tailCall(self: *Machine, argc: u32) Error!void {
        const from = self.stack.items.len - argc - 1;
        const callee = self.stack.items[from];
        if (callee.tag() != .closure) return self.call(argc);

        const chunk = try self.functionOf(callee, argc);
        const frame = self.top();
        const to = frame.base - 1;
        std.mem.copyForwards(Value, self.stack.items[to..], self.stack.items[from..]);
        self.stack.shrinkRetainingCapacity(to + 1 + argc);
        frame.* = .{ .chunk = chunk, .pc = 0, .base = frame.base };
    }

    /// Снять кадр и оставить результат на месте вызванной функции. Значение
    /// возвращается, когда снят последний кадр, то есть закончилась форма.
    fn ret(self: *Machine) ?Value {
        const frame = self.frames.pop().?;
        const result = self.stack.items[self.stack.items.len - 1];
        self.stack.shrinkRetainingCapacity(frame.base);
        self.stack.items[frame.base - 1] = result;
        if (self.frames.items.len > 0) return null;
        _ = self.pop();
        return result;
    }

    fn functionOf(self: *Machine, callee: Value, argc: u32) Error!*const Chunk {
        const cl = callee.asClosure();
        const key: FunctionKey = .{ .params = cl.params, .body = cl.body };
        const chunk = self.functions.get(key) orelse try self.compileFunction(key);
        if (chunk.arity != argc) return error.ArityMismatch;
        return chunk;
    }

    fn compileFunction(self: *Machine, key: FunctionKey) Error!*Chunk {
        const gpa = self.vm.gpa;
        const chunk = try gpa.create(Chunk);
        errdefer gpa.destroy(chunk);
        chunk.* = .{};
        errdefer chunk.deinit(gpa);
        try self.compile(chunk, key.params, key.body);
        // Ключ держим среди констант: так он проживёт столько же, сколько машина.
        try self.constants.appendSlice(gpa, &.{ key.params, key.body });
        try self.functions.put(gpa, key, chunk);
        return chunk;
    }

    // --- Компилятор ---

    /// Скомпилировать тело функции с такими параметрами. Форма верхнего
    /// уровня это функция без параметров.
    pub fn compile(self: *Machine, chunk: *Chunk, params: Value, body: Value) Error!void {
        chunk.params = params;
        var rest = params;
        while (rest.isCons()) : (rest = rest.asCell().cdr) {
            if (rest.asCell().car.tag() != .symbol) return error.MalformedForm;
            chunk.arity += 1;
        }
        var c: Compiler = .{ .m = self, .chunk = chunk };
        try c.expr(body, true);
        _ = try c.emit(.ret, 0);
    }
};

const Compiler = struct {
    m: *Machine,
    chunk: *Chunk,

    fn emit(self: *Compiler, op: Op, arg: u32) Error!u32 {
        const at: u32 = @intCast(self.chunk.code.items.len);
        try self.chunk.code.append(self.m.vm.gpa, .{ .op = op, .arg = arg });
        return at;
    }

    /// Направить переход, записанный раньше, на следующую команду.
    fn patchHere(self: *Compiler, at: u32) void {
        self.chunk.code.items[at].arg = @intCast(self.chunk.code.items.len);
    }

    fn constant(self: *Compiler, v: Value) Error!u32 {
        const at: u32 = @intCast(self.m.constants.items.len);
        try self.m.constants.append(self.m.vm.gpa, v);
        return at;
    }

    /// Номер слота параметра или null, если имя не параметр этой функции.
    /// Если имя повторяется, побеждает последнее, как в окружении `apply`.
    fn slotOf(self: *Compiler, id: value.SymbolId) ?u32 {
        var found: ?u32 = null;
        var i: u32 = 0;
        var rest = self.chunk.params;
        while (rest.isCons()) : (rest = rest.asCell().cdr) {
            if (rest.asCell().car.asSymbol() == id) found = i;
            i += 1;
        }
        return found;
    }

    /// `tail` говорит, что значение выражения сразу станет значением функции.
    fn expr(self: *Compiler, e: Value, tail: bool) Error!void {
        switch (e.tag()) {
            .nil, .fixnum, .closure, .primitive => _ = try self.emit(.constant, try self.constant(e)),
            .symbol => if (self.slotOf(e.asSymbol())) |slot| {
                _ = try self.emit(.arg, slot);
            } else {
                _ = try self.emit(.name, try self.constant(e));
            },
            .cons => try self.form(e, tail),
        }
    }

    fn form(self: *Compiler, e: Value, tail: bool) Error!void {
        const head = e.asCell().car;
        const args = e.asCell().cdr;

        if (head.tag() == .symbol) {
            const id = head.asSymbol();
            const s = self.m.vm.sym;
            if (id == s.quote) return self.quote(args);
            if (id == s.cond) return self.cond(args, tail);
            if (id == s.lambda) return self.lambda(args);
            if (id == s.define) return self.define(args);
        }

        // Вызов: функция, потом аргументы слева направо, потом сама команда.
        try self.expr(head, false);
        var argc: u32 = 0;
        var rest = args;
        while (rest.isCons()) : (rest = rest.asCell().cdr) {
            try self.expr(rest.asCell().car, false);
            argc += 1;
        }
        if (!rest.isNil()) return error.MalformedForm;
        _ = try self.emit(if (tail) .tail_call else .call, argc);
    }

    fn quote(self: *Compiler, args: Value) Error!void {
        const quoted = value.car(args) orelse return error.MalformedForm;
        if (!(value.cdr(args) orelse Value.nil).isNil()) return error.MalformedForm;
        _ = try self.emit(.constant, try self.constant(quoted));
    }

    /// Каждая ветка это проверка, переход мимо тела и тело с переходом в конец.
    /// Адреса переходов вперёд ещё неизвестны, их закрывают заплатками.
    fn cond(self: *Compiler, clauses: Value, tail: bool) Error!void {
        const gpa = self.m.vm.gpa;
        var exits: std.ArrayList(u32) = .empty;
        defer exits.deinit(gpa);

        var rest = clauses;
        while (rest.isCons()) : (rest = rest.asCell().cdr) {
            const clause = rest.asCell().car;
            if (!clause.isCons()) return error.MalformedForm;
            const body_list = clause.asCell().cdr;
            if (!body_list.isCons()) return error.MalformedForm;

            try self.expr(clause.asCell().car, false);
            const skip = try self.emit(.jump_if_nil, 0);
            try self.expr(body_list.asCell().car, tail);
            try exits.append(gpa, try self.emit(.jump, 0));
            self.patchHere(skip);
        }
        // Ни одна ветка не сработала: значение nil.
        _ = try self.emit(.constant, try self.constant(.nil));
        for (exits.items) |at| self.patchHere(at);
    }

    fn lambda(self: *Compiler, args: Value) Error!void {
        _ = value.car(args) orelse return error.MalformedForm;
        const body_list = value.cdr(args) orelse return error.MalformedForm;
        _ = value.car(body_list) orelse return error.MalformedForm;
        if (!(value.cdr(body_list) orelse Value.nil).isNil()) return error.MalformedForm;
        _ = try self.emit(.closure, try self.constant(args));
    }

    fn define(self: *Compiler, args: Value) Error!void {
        const name = value.car(args) orelse return error.MalformedForm;
        if (name.tag() != .symbol) return error.MalformedForm;
        const rest = value.cdr(args) orelse return error.MalformedForm;
        const e = value.car(rest) orelse return error.MalformedForm;
        if (!(value.cdr(rest) orelse Value.nil).isNil()) return error.MalformedForm;
        try self.expr(e, false);
        _ = try self.emit(.define, try self.constant(name));
    }
};

Пройдёмся по файлу снизу вверх, от компилятора к машине.

Компилятор. expr раскладывает значение по виду. Самовычисляющееся становится constant, символ становится arg, если это параметр функции, иначе name, пара уходит в form. form узнаёт специальные формы по символу в голове ровно так же, как eval, а всё остальное компилирует как вызов: функция, аргументы слева направо, команда call. Флаг tail протаскивается сверху вниз. Тело функции стоит в хвостовой позиции, тело ветки cond наследует позицию самого cond, а аргументы вызова и проверка ветки в хвосте не бывают никогда. Отсюда и берётся tail_call.

Самое интересное в cond. Для каждой ветки компилятор пишет проверку и jump_if_nil, но куда прыгать, ещё неизвестно: тело ветки не скомпилировано. Поэтому операнд пишется нулём, номер команды запоминается, и когда тело готово, patchHere вписывает туда номер следующей команды. Переходы в конец cond копятся в exits и закрываются так же, одним махом в конце. Это обратная заплатка, и тот же приём понадобится в JIT, только там заплатка пишется в четыре байта rel32.

Машина. call смотрит на вид функции под аргументами. Примитиву нужен список, и машина собирает его из слотов, а результат кладёт на место функции. Замыканию нужен кадр: машина берёт скомпилированное тело (при первом вызове компилирует его), сверяет число аргументов и кладёт кадр, у которого base смотрит на первый аргумент. Никакого списка пар под аргументы не строится, и в этом главная экономия против eval. Список пар появляется только в makeClosure, когда функция создаёт внутри себя другую lambda, и той нужно захватить параметры.

Диспетчеры. runLoop и runLabeled исполняют один байткод одними и теми же функциями call, ret, lookup. Отличаются они только тем, как выбирается следующая команда. В runLoop это одна точка наверху цикла. В runLabeled каждая ветка сама читает следующую команду через fetch и прыгает прямо в её ветку через continue :dispatch, в точности как runLabeled из раздела выше. Обе функции помечены noinline: иначе компилятор вклеил бы их в runForm, и в листинге их было бы не найти.

Во что превращается fib

Тело fib из programs/fib.zl после компилятора (номер команды, опкод, операнд, для констант и имён их значение):

  0  name        0   <
  1  arg         0
  2  constant    1   2
  3  call        2
  4  jump_if_nil 7
  5  arg         0
  6  jump        25
  7  name        2   t
  8  jump_if_nil 24
  9  name        3   +
 10  name        4   fib
 11  name        5   -
 12  arg         0
 13  constant    6   1
 14  call        2
 15  call        1
 16  name        7   fib
 17  name        8   -
 18  arg         0
 19  constant    9   2
 20  call        2
 21  call        1
 22  tail_call   2
 23  jump        25
 24  constant    10  nil
 25  ret         0

Читается как ассемблер стековой машины. Команды с 0 по 4 это (< n 2) и проверка: сначала функция, потом аргументы, потом вызов; результат ложится на вершину, jump_if_nil его снимает. Первая ветка n заняла две команды. Сложение стало tail_call, а оба вызова fib внутри него остались обычными call: их результат ещё нужен сложению. Но + это примитив, своего кадра у него нет, и хвостовой вызов примитива ничем не отличается от обычного: результат ложится на стек, и машина идёт дальше, к jump и ret. Команда 24 не исполнится никогда, потому что t не бывает nil. Компилятор её всё равно пишет: t для него обычное глобальное имя, которое можно переопределить.

И ещё одно наблюдение: fib, +, - и < ищутся по имени на каждом вызове. Список пар обходить уже не надо (у fib окружение пустое), остаётся поиск в глобальной карте. Это цена того, что глобальное имя можно переопределить в любой момент, и к ней мы вернёмся, когда будем мерить исполнителей.

main.zig: ключ --exec

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

//!   zl                          диалог
//!   zl <file.zl>                исполнить файл и напечатать значение последней формы
//!   zl --exec loop <file.zl>    исполнитель: tree (по умолчанию), loop или labeled

const bytecode = @import("bytecode.zig");
const eval = @import("eval.zig");
const printer = @import("printer.zig");
const repl = @import("repl.zig");
const Value = @import("value.zig").Value;
const Vm = @import("vm.zig").Vm;

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

Разбор ключей встаёт перед созданием машины:

    // Ключи идут перед именем файла.
    var executor: Executor = .tree;
    var rest = args[1..];
    while (rest.len > 0 and std.mem.startsWith(u8, rest[0], "--")) {
        if (std.mem.eql(u8, rest[0], "--exec") and rest.len > 1) {
            executor = std.meta.stringToEnum(Executor, rest[1]) orelse {
                try out.print("--exec ждёт tree, loop или labeled, а получил {s}\n", .{rest[1]});
                try out.flush();
                return error.BadArgument;
            };
            rest = rest[2..];
        } else {
            try out.print("неизвестный ключ {s}\n", .{rest[0]});
            try out.flush();
            return error.BadArgument;
        }
    }

Дальше args.len < 2 становится rest.len == 0, args[1] становится rest[0], а вызов eval.evalSource уступает место выбору исполнителя:

    var machine: bytecode.Machine = .init(&vm);
    defer machine.deinit();

    const result = run(&machine, source, executor) catch |err| {
        try out.print("ошибка: {t}\n", .{err});
        try out.flush();
        return err;
    };

fn run(machine: *bytecode.Machine, source: []const u8, executor: Executor) !Value {
    return switch (executor) {
        .tree => eval.evalSource(machine.vm, source),
        .loop => machine.runSource(source, .loop),
        .labeled => machine.runSource(source, .labeled),
    };
}

std.meta.stringToEnum превращает строку в значение перечня по имени поля, так что имена ключа и имена в коде одни и те же. Диалог по-прежнему работает обходом дерева.

build.zig: шаг asm

В src/root.zig добавляется строка pub const bytecode = @import("bytecode.zig");, в build.zig номер шага, const steps = [_][]const u8{ "05", "06", "13" };, и новый шаг сборки рядом с run:

    // Ассемблер всей программы, чтобы читать исполнителей глазами:
    // zig build asm -Dtarget=x86_64-linux -Doptimize=ReleaseFast
    // кладёт листинг в zig-out/zl.s и тот же код бинарником в zig-out/bin/zl-llvm.
    // В Debug под x86-64 Zig по умолчанию собирает своим бэкендом, а листинг
    // умеет печатать только LLVM, поэтому он включён явно.
    const asm_exe = b.addExecutable(.{ .name = "zl-llvm", .root_module = exe.root_module, .use_llvm = true });
    const asm_step = b.step("asm", "Положить ассемблер zl в zig-out/zl.s");
    asm_step.dependOn(&b.addInstallFile(asm_exe.getEmittedAsm(), "zl.s").step);
    asm_step.dependOn(&b.addInstallArtifact(asm_exe, .{}).step);

Это тот же -femit-asm, которым мы снимали листинги весь урок, только для целой программы: getEmittedAsm просит компилятор положить рядом с бинарником ассемблерный файл, addInstallFile копирует его в zig-out. Бинарник кладём тоже: у .s синтаксис Intel, а objdump покажет тот же код в привычном AT&T и с адресами.

Тесты шага

//! Шаг 13: три исполнителя одной программы. Обход дерева, байткод под циклом
//! вокруг `switch` и тот же байткод под labeled switch обязаны дать один ответ.

const std = @import("std");

const zl = @import("zl");

const bytecode = zl.bytecode;
const eval = zl.eval;
const printer = zl.printer;
const programs = zl.programs;
const reader = zl.reader;
const Value = zl.Value;
const Vm = zl.Vm;

const testing = std.testing;

const dispatches = [_]bytecode.Dispatch{ .loop, .labeled };

fn expectPrinted(vm: *Vm, v: Value, expected: []const u8) !void {
    const text = try printer.toOwned(testing.allocator, vm, v);
    defer testing.allocator.free(text);
    try testing.expectEqualStrings(expected, text);
}

test "каждая программа даёт один ответ у всех трёх исполнителей" {
    for (programs.all) |program| {
        {
            var vm: Vm = try .init(testing.allocator);
            defer vm.deinit();
            try expectPrinted(&vm, try eval.evalSource(&vm, program.source), program.expected);
        }
        for (dispatches) |dispatch| {
            var vm: Vm = try .init(testing.allocator);
            defer vm.deinit();
            var m: bytecode.Machine = .init(&vm);
            defer m.deinit();
            const result = try m.runSource(program.source, dispatch);
            expectPrinted(&vm, result, program.expected) catch |err| {
                std.debug.print("{s} под {t}\n", .{ program.name, dispatch });
                return err;
            };
        }
    }
}

test "тело fib компилируется в плоский поток команд" {
    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();
    var m: bytecode.Machine = .init(&vm);
    defer m.deinit();

    const lambda = try reader.readOne(&vm,
        \\(lambda (n)
        \\  (cond ((< n 2) n)
        \\        (t (+ (fib (- n 1)) (fib (- n 2))))))
    );
    const params = zl.value.car(lambda.asCell().cdr).?;
    const body = zl.value.car(lambda.asCell().cdr.asCell().cdr).?;

    var chunk: bytecode.Chunk = .{};
    defer chunk.deinit(vm.gpa);
    try m.compile(&chunk, params, body);

    const Op = bytecode.Op;
    // (< n 2): функция, аргументы, вызов; nil уводит к следующей ветке.
    const check = [_]Op{ .name, .arg, .constant, .call, .jump_if_nil };
    // n и прыжок в конец.
    const base_case = [_]Op{ .arg, .jump };
    // t это глобальное имя, а не константа, поэтому проверка честная.
    const always = [_]Op{ .name, .jump_if_nil };
    // (+ (fib (- n 1)) (fib (- n 2))): оба fib обычные вызовы, сложение в хвосте.
    const left = [_]Op{ .name, .name, .name, .arg, .constant, .call, .call };
    const right = [_]Op{ .name, .name, .arg, .constant, .call, .call };
    const add = [_]Op{ .tail_call, .jump };
    // Ни одна ветка не подошла: nil, потом возврат.
    const fallthrough = [_]Op{ .constant, .ret };

    var buf: [64]Op = undefined;
    try testing.expectEqualSlices(
        Op,
        &(check ++ base_case ++ always ++ left ++ right ++ add ++ fallthrough),
        chunk.ops(&buf),
    );
    try testing.expectEqual(@as(u32, 1), chunk.arity);
}

test "хвостовой вызов не наращивает кадры, обычный наращивает" {
    for (dispatches) |dispatch| {
        var vm: Vm = try .init(testing.allocator);
        defer vm.deinit();
        var m: bytecode.Machine = .init(&vm);
        defer m.deinit();

        const count_down =
            \\(define count-down
            \\  (lambda (n) (cond ((eq n 0) 'done) (t (count-down (- n 1))))))
            \\(count-down 100000)
        ;
        try expectPrinted(&vm, try m.runSource(count_down, dispatch), "done");
        // Хвостовой вызов из формы верхнего уровня занял её кадр, а дальше
        // count-down сто тысяч раз занимала свой же: кадр всё время один.
        try testing.expectEqual(@as(usize, 1), m.peak_frames);

        const depth =
            \\(define depth (lambda (n) (cond ((eq n 0) 0) (t (+ 1 (depth (- n 1)))))))
            \\(depth 10000)
        ;
        try expectPrinted(&vm, try m.runSource(depth, dispatch), "10000");
        // Сложение ждёт результата, поэтому кадр на каждый уровень. Кадры
        // лежат в массиве машины, а не на стеке Zig: десять тысяч уровней
        // рекурсии стоят десять тысяч записей по 16 байт.
        try testing.expectEqual(@as(usize, 10001), m.peak_frames);
    }
}

test "замыкания и окружения одинаковы у обхода дерева и байткода" {
    for (dispatches) |dispatch| {
        var vm: Vm = try .init(testing.allocator);
        defer vm.deinit();
        var m: bytecode.Machine = .init(&vm);
        defer m.deinit();

        try expectPrinted(&vm, try m.runSource(
            \\(define make-adder (lambda (n) (lambda (x) (+ x n))))
            \\(define add5 (make-adder 5))
            \\(add5 10)
        , dispatch), "15");

        // Замыкание, собранное обходом дерева, байткод зовёт как своё, и наоборот.
        _ = try eval.evalSource(&vm, "(define add7 (make-adder 7))");
        try expectPrinted(&vm, try m.runSource("(add7 1)", dispatch), "8");
        _ = try m.runSource("(define add9 (make-adder 9))", dispatch);
        try expectPrinted(&vm, try eval.evalSource(&vm, "(add9 1)"), "10");

        // Примитив это значение, его можно передать и позвать косвенно.
        try expectPrinted(&vm, try m.runSource("((lambda (f) (f '(1 2))) car)", dispatch), "1");
    }
}

test "ошибки те же, и после ошибки машина работает дальше" {
    for (dispatches) |dispatch| {
        var vm: Vm = try .init(testing.allocator);
        defer vm.deinit();
        var m: bytecode.Machine = .init(&vm);
        defer m.deinit();

        try testing.expectError(error.NotAPair, m.runSource("(car 1)", dispatch));
        try testing.expectError(error.UnboundSymbol, m.runSource("(+ 1 nope)", dispatch));
        try testing.expectError(error.ArityMismatch, m.runSource("((lambda (x) x))", dispatch));
        try testing.expectError(error.NotApplicable, m.runSource("(1 2)", dispatch));
        try testing.expectError(error.MalformedForm, m.runSource("(quote)", dispatch));
        // Ошибка в глубине рекурсии оставила бы на стеке обломки кадров.
        try testing.expectError(error.NotANumber, m.runSource(
            \\(define bad (lambda (n) (cond ((eq n 0) (+ 'a 1)) (t (+ 1 (bad (- n 1)))))))
            \\(bad 50)
        , dispatch));

        try testing.expectEqual(@as(usize, 0), m.stack.items.len);
        try testing.expectEqual(@as(usize, 0), m.frames.items.len);
        try expectPrinted(&vm, try m.runSource("(+ 2 3)", dispatch), "5");
    }
}

Главный тест первый: каждая программа из каталога, включая метациклический eval.zl, проходит через трёх исполнителей и даёт тот же ответ. Второй фиксирует форму байткода fib, чтобы случайная правка компилятора не прошла незамеченной. Третий проверяет обещание про хвостовой вызов: сто тысяч итераций count-down живут в одном кадре, а нехвостовая рекурсия на десять тысяч уровней честно занимает десять тысяч кадров, не трогая стек Zig. Четвёртый гоняет замыкания между исполнителями в обе стороны. Пятый следит, чтобы ошибка в глубине рекурсии не оставила на стеке обломков.

Одно отличие от eval тесты не ловят, и о нём стоит знать. Обход дерева находит неправильную форму, только когда до неё дойдёт исполнение, а компилятор разбирает тело целиком при первом вызове. Функция с опечаткой в ветке, которая никогда не исполняется, у eval работает, а у байткода падает с MalformedForm.

Прогон

$ zig build test --summary all
Build Summary: 9/9 steps succeeded; 34/34 tests passed
test success
+- run test 7 pass (7 total) 365ms MaxRSS:2M      тесты внутри модулей
+- run test 12 pass (12 total) 753ms MaxRSS:3M    шаг 05
+- run test 10 pass (10 total) 1s MaxRSS:10M      шаг 06
+- run test 5 pass (5 total) 2s MaxRSS:29M        шаг 13

$ zig build
$ ./zig-out/bin/zl --exec tree programs/fib.zl
6765
$ ./zig-out/bin/zl --exec loop programs/fib.zl
6765
$ ./zig-out/bin/zl --exec labeled programs/fib.zl
6765
$ ./zig-out/bin/zl --exec jit programs/fib.zl
--exec ждёт tree, loop или labeled, а получил jit
error: BadArgument

Три исполнителя в ассемблере

Теперь то, ради чего шаг стоит в этом уроке. Соберём программу под x86_64-linux и сосчитаем косвенные переходы в каждом исполнителе, как в упражнении с игрушечной машиной:

$ zig build asm -Dtarget=x86_64-linux
$ for f in eval.eval bytecode.Machine.runLoop bytecode.Machine.runLabeled; do
>   printf '%-28s ' $f
>   objdump -d --disassemble-symbols=$f zig-out/bin/zl-llvm | grep -c 'jmpq.*\*'
> done
eval.eval                    0
bytecode.Machine.runLoop     1
bytecode.Machine.runLabeled  11

В отладочной сборке картина ровно та, что обещал раздел про labeled switch. У runLoop один косвенный переход на все десять команд. Вот он, вместе с чтением опкода:

<bytecode.Machine.runLoop>:
    ...
    movl    %ecx, (%rax)                  # frame.pc += 1 записан в кадр
    movzbl  -0x1bc(%rbp), %eax            # ins.op
    movq    %rax, -0x228(%rbp)
    subq    $0x9, %rax                    # опкод больше 9?
    ja      <bytecode.Machine.runLoop+0x380>   # да: паника corruptSwitch
    movq    -0x228(%rbp), %rax
    movq    0x100d9e0(,%rax,8), %rax      # адрес ветки из таблицы
    jmpq    *%rax                         # единственный диспетчер цикла
    jmp     <bytecode.Machine.runLoop+0x7b>
    movq    -0x1d8(%rbp), %rcx            # 0x11877d1: ветка .constant
    ...

Проверка границы та же, что в denseOp, только ведёт она не в default, а в панику: в switch по перечню ветки else нет, и значение вне перечня в Debug считается порчей памяти. Таблицу видно в .rodata по адресу из movq:

$ objdump -s -j .rodata zig-out/bin/zl-llvm | grep -A4 '^ 100d9e0'
 100d9e0 d1771801 00000000 10781801 00000000  .w.......x......
 100d9f0 54781801 00000000 9d781801 00000000  Tx.......x......
 100da00 0f791801 00000000 24791801 00000000  .y......$y......
 100da10 6d791801 00000000 9c791801 00000000  my.......y......
 100da20 cb791801 00000000 fa791801 00000000  .y.......y......

Десять адресов по восемь байт, в порядке объявления Op. Слот 0 это 0x011877d1, первая инструкция ветки .constant, сразу за jmpq и обратным jmp цикла.

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

$ objdump -d --disassemble-symbols=bytecode.Machine.runLabeled zig-out/bin/zl-llvm | grep -B1 'jmpq.*\*' | head -4
 1169652: 48 8b 04 c5 40 dc 1d 01      	movq	0x11ddc40(,%rax,8), %rax
 116965a: ff e0                        	jmpq	*%rax
--
 11697a2: 48 8b 04 c5 40 dc 1d 01      	movq	0x11ddc40(,%rax,8), %rax
$ nm zig-out/bin/zl-llvm | grep 11ddc40
00000000011ddc40 d __jmptab_386

Заметь имя. Таблицу обычного switch строит LLVM и кладёт в .rodata под служебной меткой. Таблицу labeled switch Zig строит сам, ещё до LLVM, потому что реплицированный переход для него часть семантики языка, а не оптимизация. Она лежит в .data под своим символом __jmptab_386, а в zl.s видна как обычный массив из десяти .quad.

У eval.eval косвенных переходов ноль. switch (expr.tag()) в обходе дерева слишком мал для таблицы (три группы видов), а специальные формы это цепочка if со сравнением номеров символов. Диспетчеризация обхода дерева размазана по сравнениям и рекурсивным вызовам, и одной точки выбора, которую можно было бы ускорить, у него нет.

Теперь режим оптимизации:

$ zig build asm -Dtarget=x86_64-linux -Doptimize=ReleaseFast
$ for f in eval.eval bytecode.Machine.runLoop bytecode.Machine.runLabeled; do
>   printf '%-28s ' $f
>   objdump -d --disassemble-symbols=$f zig-out/bin/zl-llvm | grep -c 'jmpq.*\*'
> done
eval.eval                    0
bytecode.Machine.runLoop     12
bytecode.Machine.runLabeled  13

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

<bytecode.Machine.runLabeled>:
    ...
    movq    -0x10(%rcx,%rsi), %rax        # frame.chunk
    movl    -0x8(%rcx,%rsi), %edi         # frame.pc
    movq    (%rax), %rdx                  # chunk.code.items.ptr
    movq    (%rdx,%rdi,8), %rdx           # ins = code[pc], восемь байт разом
    addl    $0x1, %edi
    movl    %edi, -0x8(%rcx,%rsi)         # pc += 1 обратно в кадр
    movq    %rdx, %rsi
    shrq    $0x20, %rsi                   # op лежит в старшей половине слова
    andl    $0xf, %esi
    movl    %edx, %ecx                    # arg в младшей
    jmpq    *0x1013e90(,%rsi,8)           # переход по таблице

Команда читается одним восьмибайтовым movq, и опкод достаётся сдвигом. Обрати внимание, где он оказался: в старшей половине слова, хотя в Instr поле op объявлено первым. Обычная структура Zig не обещает порядок полей, и компилятор поставил 32-битный arg на выровненное нулевое смещение, а байт опкода за ним. Это та свобода раскладки, о которой шла речь в уроке про структуры.

А вот команда jump_if_nil целиком. У неё два исхода, и у каждого свой диспетчер:

    movq    0x28(%r14), %rax              # stack.items.len
    testq   %rax, %rax
    je      <runLabeled+0x1a0>            # пустой стек: `.?` здесь не проверяется,
                                          # и LLVM свёл этот случай к ветке nil
    movq    0x20(%r14), %rdx
    movq    %rax, %rsi
    shlq    $0x4, %rsi
    addq    $-0x1, %rax
    testb   $0x7, -0x8(%rdx,%rsi)         # тег снятого значения: nil?
    movq    %rax, 0x28(%r14)              # pop
    je      <runLabeled+0x1a0>            # nil: на переход
    movl    0x8(%r15), %ecx               # не nil: следующая команда
    movq    (%r15), %rax
    movl    %ecx, %edx
    movq    (%rax), %rsi
    movq    (%rsi,%rdx,8), %rdx
    addl    $0x1, %ecx
    movl    %ecx, 0x8(%r15)
    movq    %rdx, %rsi
    shrq    $0x20, %rsi
    andl    $0xf, %esi
    movl    %edx, %ecx
    jmpq    *0x1013e90(,%rsi,8)           # свой диспетчер у ветки «не nil»
    nopl    (%rax)
    movl    %ecx, 0x8(%r15)               # runLabeled+0x1a0: pc = arg
    movq    (%r15), %rax
    movl    %ecx, %edx
    movq    (%rax), %rsi
    movq    (%rsi,%rdx,8), %rdx
    addl    $0x1, %ecx
    movl    %ecx, 0x8(%r15)
    movq    %rdx, %rsi
    shrq    $0x20, %rsi
    andl    $0xf, %esi
    movl    %edx, %ecx
    jmpq    *0x1013e90(,%rsi,8)           # и свой у ветки «nil»

Условный переход в программе на zl превратился в условный переход в машине плюс два разных косвенных перехода. У предсказателя теперь отдельная история на «после проверки прошли дальше» и на «после проверки прыгнули», и это ровно то, ради чего labeled switch придумывали. Сколько это даёт в тактах на реальном процессоре, мы измерим в уроке про ветвления, а цену каждого из трёх исполнителей на команду снимем в уроке про CPE.

Практика

Задача собирает вместе всё про switch. Тебе дан дизассемблированный switchProb(x, n) вместе с таблицей переходов: проверка границы, косвенный jmpq *(,%rsi,8) и семь адресов рядом. Прочитай таблицу как список пар “значение → тело”, заметь, что несколько значений n делят одну ветку, а всё вне диапазона уходит в default, и восстанови pub fn switchProb(x: i64, n: i64) i64 с тем же поведением. Тесты проверяют каждую ветку и default. Сборка идёт в Debug с проверками переполнения, поэтому арифметику пиши обёрточными операторами +%, -%, *%.

Упражнения

Итоги

• На уровне процессора нет циклов и switch, есть только jmp, условные переходы по флагам и косвенный переход по адресу. Любая конструкция языка это выбор компилятора, как разложить её в эти переходы.
• do-while ложится в ассемблер прямее всего: тело сверху, проверка снизу, один условный переход назад на итерацию, тело всегда исполняется хотя бы раз.
• У while две раскладки. Jump-to-middle прыгает на входе сразу к проверке, одна копия условия на всё. Guarded-do ставит охрану перед циклом и держит проверку снизу, ценой инструкции на входе получая один условный переход в горячей части.
• LLVM в режиме оптимизации почти всегда выбирает guarded-do (ротация цикла), потому что переход назад в конце тела предсказывается лучше всего. В режиме на размер компилятор может оставить проверку сверху с безусловным возвратом.
• for по срезу и эквивалентный while компилируются в байт в байт одинаковый код: компилятор сворачивает их в один символ.
• continue это намерение прыгнуть к шагу цикла. Иногда он остаётся настоящим переходом (js через тело к инкременту), а иногда исчезает: оптимизатор заменяет пропуск на cmov, если оба пути дёшевы и без побочных эффектов.
• Плотный switch становится таблицей переходов: cmp/ja отсекает выход за диапазон, jmpq *tab(,%reg,8) берёт значение как индекс и прыгает по адресу из таблицы. Выбор ветки за постоянное время независимо от их числа.
• Таблица адресов лежит в .rodata как массив восьмибайтовых адресов веток. Несколько меток могут делить ветку: тогда в разных слотах стоит один адрес.
• Разреженные метки дают не таблицу, а дерево сравнений (двоичный поиск): не больше логарифма сравнений вместо линейной цепочки. Границу между таблицей и деревом компилятор проводит по плотности меток.
• switch с диапазонами Zig сводит проверку lo...hi к вычитанию базы и одному беззнаковому сравнению: x - lo беззнаково меньше hi - lo.
• labeled switch это computed goto: непрямой переход реплицирован в каждую ветку, и предсказатель ведёт по истории на ветку вместо одной перемешанной. LLVM умеет ту же раскладку и для обычного цикла (дублирование хвоста), но labeled switch гарантирует её на уровне языка.
• В шаге проекта zt disasm научился косвенным jmp * и call *: поле reg группы 0xff выбирает операцию, операнд читается с шириной восемь байтов без REX.W, а таблицу переходов видно по перемещениям .rodata.
• В шаге проекта zl получил байткод стековой машины и два диспетчера над ним. Три исполнителя (обход дерева, цикл вокруг switch, labeled switch) дают один ответ на каждой программе; в Debug у цикла один косвенный переход на все команды, у labeled switch по переходу на ветку, а в ReleaseFast LLVM размножает и диспетчер цикла.

Дальше

Ты научился читать любой поток управления в ассемблере: циклы во всех формах, continue как переход или как cmov, switch как таблицу, дерево или computed goto. Пока функции у нас были плоские: аргументы приходили в регистрах, результат уходил в %rax, и стек мы почти не трогали. Следующий урок разбирает, что происходит при вызове: как аргументы раскладываются по регистрам и стеку, как устроен кадр вызванной функции, куда сохраняется адрес возврата и как рекурсия наматывает кадры один на другой. Дизассемблер zl там научится читать call и ret, а байткод-машина получит настоящие вызовы примитивов через соглашение C.