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

Симулятор Y86-64 на Zig

senior~140 мин

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

Симулятор Y86-64 на Zig

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

Цели урока

Разложить исполнение одной инструкции на шесть этапов: fetch, decode, execute, memory, writeback, pcUpdate.
Завести структуру состояния, видимого программисту, и отдельно структуру проводов, живущих внутри одного такта.
Знать наизусть, откуда берутся icode, ifun, rA, rB, valC, valP, valA, valB, valE, valM и Cnd для каждого класса инструкций.
Понимать четыре кода состояния и почему порядок проверок ADR и INS не произволен.
Прочитать формат трассы v1 и объяснить каждую её строку.
Разобрать pushq %rsp и popq %rsp до уровня “какое значение в каком порядке уходит в память и в регистр”.
Собрать тесты, где каждая программа урока 21 даёт заранее известные регистры, память и число тактов.

Идея: инструкция это шесть шагов над одним состоянием

Интерпретатор байткода из урока про циклы и switch устроен просто: цикл, switch по опкоду, в каждой ветке всё, что нужно этой инструкции. Так пишут виртуальные машины, и так было бы быстрее всего написать симулятор Y86-64. Мы напишем иначе, и вот почему.

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

Поэтому книга раскладывает любую инструкцию Y86-64 на шесть этапов, одинаковых для всех:

этап	что делает	что производит
fetch	читает байты по адресу PC	`icode`, `ifun`, `rA`, `rB`, `valC`, `valP`
decode	читает регистры	`valA`, `valB` (и номера `srcA`, `srcB`, `dstE`, `dstM`)
execute	считает в ALU	`valE`, `Cnd`, новые флаги
memory	читает или пишет слово	`valM`
writeback	пишет в регистры	новое содержимое `dstE` и `dstM`
pcUpdate	выбирает следующий адрес	новый PC

Каждая инструкция проходит все шесть, только у части из них на некоторых этапах ничего не происходит. У nop работает только fetch и pcUpdate. У mrmovq работают все, кроме флагов. Это выглядит избыточно для программы на Zig, и это действительно избыточно: наш симулятор будет медленнее наивного интерпретатора. Зато у него есть свойство, ради которого мы всё и затеваем. Каждая из шести функций переводится на Verilog почти строка в строку, и когда через четыре урока мы начнём писать SEQ (32-systems/26 · SEQ: этапы fetch и decode), у нас уже будет работающий эталон, с которым можно сравнить каждый сигнал.

Второе свойство важнее первого. Симулятор печатает трассу, и формат этой трассы мы фиксируем сегодня раз и навсегда. Дальше её будут печатать SEQ и PIPE, и три реализации одной архитектуры будут давать побайтово одинаковый текст. Разошлись, значит кто-то из троих неправ, и различие видно построчно, а не “программа выдала не то”.

Состояние: всё, что видит программист

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

Файл src/sim/state.zig целиком:

//! Состояние машины Y86-64, видимое программисту.
//!
//! Пятнадцать регистров, четыре килобайта памяти, счётчик команд, три флага
//! и код состояния. Больше у машины ничего нет: всё остальное это провода
//! внутри такта, и они живут в `cpu.zig`.

const std = @import("std");

const isa = @import("../isa.zig");

const Reg = isa.Reg;
const Stat = isa.Stat;

pub const State = struct {
    regs: [isa.reg_count]u64 = @splat(0),
    mem: [isa.mem_size]u8 = @splat(0),
    pc: u64 = 0,
    /// Флаг нуля.
    zf: bool = true,
    /// Флаг знака.
    sf: bool = false,
    /// Флаг переполнения.
    of: bool = false,
    stat: Stat = .aok,

    /// Машина после сброса: регистры нулевые, ZF = 1, как у yis.
    pub fn init() State {
        return .{};
    }

    /// Чтение регистра. RNONE это не регистр, из него всегда читается ноль:
    /// так же ведёт себя и регистровый файл в железе.
    pub fn get(self: *const State, r: Reg) u64 {
        if (r == .none) return 0;
        return self.regs[@intFromEnum(r)];
    }

    /// Запись регистра. В RNONE запись просто не происходит.
    pub fn set(self: *State, r: Reg, value: u64) void {
        if (r == .none) return;
        self.regs[@intFromEnum(r)] = value;
    }

    /// Восьмибайтное слово из памяти или null, если адрес за границей.
    /// Выравнивание не требуется, как и в книге.
    pub fn readWord(self: *const State, addr: u64) ?u64 {
        if (addr > isa.mem_size - 8) return null;
        const at: usize = @intCast(addr);
        return std.mem.readInt(u64, self.mem[at..][0..8], .little);
    }

    /// Записывает слово и говорит, получилось ли.
    pub fn writeWord(self: *State, addr: u64, value: u64) bool {
        if (addr > isa.mem_size - 8) return false;
        const at: usize = @intCast(addr);
        std.mem.writeInt(u64, self.mem[at..][0..8], value, .little);
        return true;
    }

    /// Загружает образ памяти с адреса 0. Всё, что образ не покрыл, остаётся нулём.
    pub fn load(self: *State, image: []const u8) void {
        const n = @min(image.len, isa.mem_size);
        @memcpy(self.mem[0..n], image[0..n]);
    }
};

Три решения в этом файле стоят того, чтобы на них остановиться.

RNONE читается как ноль и не пишется. Код регистра 0xf в Y86-64 означает “поля нет”. В программе это удобно превратить в исключение и падать, но мы делаем наоборот: get(.none) возвращает ноль, set(.none, x) молча ничего не делает. Так ведёт себя настоящий регистровый файл, у которого адресный вход просто получил значение, ни на что не отображённое. Благодаря этому в execute появится трюк с cmovXX, а в writeback не будет ни одной проверки.

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

const std = @import("std");

const mem_size = 4096;

fn readWord(mem: *const [mem_size]u8, addr: u64) ?u64 {
    if (addr > mem_size - 8) return null;
    const at: usize = @intCast(addr);
    return std.mem.readInt(u64, mem[at..][0..8], .little);
}

test "последнее целое слово начинается на 4088" {
    var mem: [mem_size]u8 = @splat(0);
    mem[mem_size - 8] = 0x2a;

    try std.testing.expectEqual(@as(u64, 0x2a), readWord(&mem, mem_size - 8).?);
    // На единицу дальше хвост слова уже торчит за память.
    try std.testing.expectEqual(@as(?u64, null), readWord(&mem, mem_size - 7));
    // И совсем далёкий адрес тоже не должен переполнить usize.
    try std.testing.expectEqual(@as(?u64, null), readWord(&mem, 1 << 40));
}

После сброса ZF равен единице. Регистры нулевые, значит “последний результат” условно ноль. Это соглашение симулятора yis из книги, и мы его повторяем, чтобы трассы совпадали. Если поставить все флаги в ноль, программа, которая начинается с je, поведёт себя иначе, чем у книги.

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

Провода: что живёт внутри одного такта

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

/// Провода между этапами. Имена как в книге, чтобы код читался рядом с ней.
pub const Signals = struct {
    // fetch
    icode: Icode = isa.icode_none,
    ifun: u4 = 0,
    ra: Reg = .none,
    rb: Reg = .none,
    val_c: u64 = 0,
    /// Адрес следующей по порядку инструкции.
    val_p: u64 = 0,

    // decode и writeback
    src_a: Reg = .none,
    src_b: Reg = .none,
    dst_e: Reg = .none,
    dst_m: Reg = .none,
    val_a: u64 = 0,
    val_b: u64 = 0,

    // execute
    val_e: u64 = 0,
    cnd: bool = false,

    // memory
    mem_addr: u64 = 0,
    mem_data: u64 = 0,
    mem_read: bool = false,
    mem_write: bool = false,
    val_m: u64 = 0,

    stat: Stat = .aok,
};

Обрати внимание, что src_a, src_b, dst_e и dst_m лежат в одной группе с val_a и val_b, хотя dst_e и dst_m понадобятся только в writeback. Так и в железе: номера портов регистрового файла вычисляются на этапе decode все четыре сразу, а два из них просто доезжают до конца такта неиспользованными.

Ещё одна деталь, которая пригодится, когда мы дойдём до конвейера. Здесь у нас один набор проводов на инструкцию. В PIPE таких наборов будет пять одновременно, по одному на каждую инструкцию в полёте, и именно поэтому там понадобятся продвижение и остановы. Пока держи в голове, что структура Signals это будущий конвейерный регистр.

Шесть этапов

Файл src/sim/cpu.zig, по частям. Начало у него такое:

//! Шесть этапов SEQ над состоянием машины.
//!
//! Каждая функция это один этап из таблиц 4.18 до 4.21 книги, а `Signals` это
//! провода между этапами: в железе они существуют внутри одного такта, здесь
//! живут в одной структуре. Такое разбиение выглядит избыточным для
//! интерпретатора, зато потом строка в строку ложится на Verilog.

const std = @import("std");

const isa = @import("../isa.zig");
const encoder = @import("../asm/encoder.zig");
const state = @import("state.zig");

const Icode = isa.Icode;
const Reg = isa.Reg;
const Stat = isa.Stat;
const State = state.State;

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

fetch: байты становятся полями

/// Выборка: достать байты инструкции и разложить их по полям.
///
/// Порядок проверок тот же, что у SEQ. Сначала выясняем, лежит ли инструкция
/// в памяти целиком (иначе ADR), и только потом смотрим, законна ли она
/// (иначе INS). Первое старше второго, как в функции Stat у книги.
pub fn fetch(st: *const State, s: *Signals) void {
    if (st.pc >= isa.mem_size) {
        s.stat = .adr;
        return;
    }
    const at: usize = @intCast(st.pc);
    const decoded = encoder.decode(st.mem[at..]) catch {
        s.stat = .adr;
        return;
    };

    s.icode = decoded.icode;
    s.ifun = decoded.ifun;
    s.ra = decoded.ra;
    s.rb = decoded.rb;
    s.val_c = decoded.val_c;
    s.val_p = st.pc + decoded.len;

    if (!decoded.valid) {
        s.stat = .ins;
        return;
    }
    if (decoded.icode == .halt) s.stat = .hlt;
}

Три выхода из одной функции, и все три означают разное.

Первый: PC уже за пределами памяти, читать нечего. Это ADR, и icode остаётся равным 0xf, потому что мы даже не знаем, что за инструкция там была бы.

Второй: байты есть, но их не хватило до конца инструкции. decode отвечает ошибкой Truncated, и это тоже ADR. Заметь: не INS. Инструкция, у которой обрезан хвост, это не “неправильная инструкция”, это “обращение за границу памяти”, просто обращение шло за байтами кода, а не за данными.

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

halt попадает в ту же воронку, хотя это не ошибка. Он ставит stat в HLT, и дальше все этапы выключаются одним и тем же условием. Поэтому halt не двигает PC, и после останова в состоянии остаётся адрес самого halt, а не следующий за ним.

Отдельно про valP. Это адрес следующей по порядку инструкции, то есть pc плюс длина. Длина известна сразу после первого байта, потому что зависит только от icode: нужен ли байт регистров и нужна ли константа. В x86-64 так нельзя, там длину приходится выяснять, разбирая префиксы и ModRM, и это одна из причин, по которым Y86-64 годится в учебную архитектуру.

decode: номера регистров и их значения

/// Декодирование: выбрать номера читаемых и записываемых регистров и прочитать
/// значения. Указатель стека читается явно там, где инструкция его меняет.
pub fn decode(st: *const State, s: *Signals) void {
    if (s.stat != .aok) return;

    s.src_a = switch (s.icode) {
        .cmovxx, .rmmovq, .opq, .pushq => s.ra,
        .popq, .ret => .rsp,
        else => .none,
    };
    s.src_b = switch (s.icode) {
        .rmmovq, .mrmovq, .opq, .iaddq => s.rb,
        .pushq, .popq, .call, .ret => .rsp,
        else => .none,
    };
    s.dst_e = switch (s.icode) {
        .cmovxx, .irmovq, .opq, .iaddq => s.rb,
        .pushq, .popq, .call, .ret => .rsp,
        else => .none,
    };
    s.dst_m = switch (s.icode) {
        .mrmovq, .popq => s.ra,
        else => .none,
    };

    s.val_a = st.get(s.src_a);
    s.val_b = st.get(s.src_b);
}

Четыре таблицы, и каждая это буквально столбец из книги. Читать их надо так: “какой регистр подать на порт A”, “какой на порт B”, “в какой регистр пойдёт результат ALU”, “в какой пойдёт слово из памяти”.

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

Четыре инструкции работают со стеком, и у всех четырёх %rsp появляется в таблицах явно, без единого специального случая. pushq читает его на порт B (чтобы вычесть восемь) и пишет туда же через порт E. popq читает его сразу на оба порта: на A, чтобы взять адрес вершины, и на B, чтобы прибавить восемь. call только пишет, ret читает на оба порта, как popq.

Именно из-за этой симметрии pushq %rsp и popq %rsp работают правильно сами собой, без единого if. Мы разберём оба случая чуть ниже, когда посмотрим на настоящую трассу.

execute: одно ALU на все случаи

/// Исполнение: АЛУ считает valE, оно же проверяет условие и ставит флаги.
pub fn execute(st: *State, s: *Signals) void {
    if (s.stat != .aok) return;

    switch (s.icode) {
        .cmovxx => {
            s.val_e = s.val_a;
            s.cnd = isa.cond(s.ifun, st.zf, st.sf, st.of);
            // Условие не выполнилось: инструкция превращается в пустую тем,
            // что порт записи выключается. Регистр не портится.
            if (!s.cnd) s.dst_e = .none;
        },
        .irmovq => s.val_e = s.val_c,
        .rmmovq, .mrmovq => s.val_e = s.val_b +% s.val_c,
        .opq => {
            const result = isa.alu(@enumFromInt(s.ifun), s.val_b, s.val_a);
            s.val_e = result.value;
            setFlags(st, result);
        },
        .iaddq => {
            const result = isa.alu(.add, s.val_b, s.val_c);
            s.val_e = result.value;
            setFlags(st, result);
        },
        .jxx => s.cnd = isa.cond(s.ifun, st.zf, st.sf, st.of),
        // Стек растёт вниз: положить это минус восемь, снять это плюс восемь.
        .pushq, .call => s.val_e = s.val_b -% 8,
        .popq, .ret => s.val_e = s.val_b +% 8,
        else => {},
    }
}

fn setFlags(st: *State, result: isa.AluResult) void {
    st.zf = result.zf;
    st.sf = result.sf;
    st.of = result.of;
}

Здесь спрятаны три вещи, которые студенты обычно ломают.

Флаги меняют только OPq и iaddq. Сложение адреса в rmmovq, вычитание восьми в pushq, прибавление восьми в ret идут через то же ALU, но флаги не трогают. Если бы трогали, ни один цикл главы 4 не работал бы: между subq, который выставляет флаги, и jne, который на них смотрит, в теле цикла стоят другие инструкции. В железе это отдельный управляющий сигнал set_cc, а у нас просто вызов setFlags в двух ветках из десяти.

cmovXX при ложном условии не пишет, а не “пишет то же самое”. Соблазн написать “если условие, то запиши” велик, но правильный ответ другой: отключить порт записи, поставив dst_e в RNONE. Разница видна там, где приёмник и источник это разные регистры и старое значение приёмника кому-то нужно. И это ровно то, что делает железо: значение на шине есть всегда, а вот адресный вход порта записи гасится.

rrmovq это cmovXX с нулевым ifun. Отдельной ветки ему не нужно, потому что cond(0, ...) всегда истинно. Один код операции обслуживает семь мнемоник.

Про порядок операндов стоит сказать вслух, потому что на нём ошибаются все. Формула такая: valE = valB OP valA. Значит subq %rax, %rbx считает %rbx минус %rax: вычитаемое приходит с порта A, уменьшаемое с порта B. В синтаксисе ATT первый операнд это источник, и он же попадает в rA.

Условия живут в src/isa.zig, в функции cond. Вот она, выписанная отдельным самодостаточным блоком, чтобы этот листинг можно было запустить прямо как есть: в эталоне на месте числовых ifun стоит перечисление Cond, всё остальное совпадает.

/// Выполняется ли условие при таких флагах. Ровно таблица 4.3 книги.
pub fn cond(ifun: u4, zf: bool, sf: bool, of: bool) bool {
    return switch (ifun) {
        // always
        0 => true,
        // Знаковое «меньше» это SF xor OF: знак результата, исправленный
        // переполнением.
        1 => (sf != of) or zf, // le
        2 => sf != of, // l
        3 => zf, // e
        4 => !zf, // ne
        5 => sf == of, // ge
        6 => (sf == of) and !zf, // g
        else => false,
    };
}

test "условия совпадают с таблицей книги" {
    const testing = @import("std").testing;

    // ZF = 1, SF = 0, OF = 0: результат ноль.
    try testing.expect(cond(3, true, false, false)); // e
    try testing.expect(cond(1, true, false, false)); // le
    try testing.expect(!cond(6, true, false, false)); // g

    // SF = 1, OF = 0: результат отрицательный, переполнения не было.
    try testing.expect(cond(2, false, true, false)); // l
    try testing.expect(!cond(5, false, true, false)); // ge

    // SF = 1, OF = 1: переполнение перевернуло знак, на самом деле больше.
    try testing.expect(!cond(2, false, true, true)); // l
    try testing.expect(cond(6, false, true, true)); // g
}

Последний случай стоит того, чтобы прочитать его дважды. Знаковое “меньше” это не “знак результата”, а “знак результата, исправленный переполнением”. Если вычитание переполнилось, знак соврал, и SF надо перевернуть. Именно поэтому в таблице стоит SF не равно OF, а не просто SF.

memory: второй этап, который умеет ADR

/// Обращение к памяти. Единственный этап, кроме выборки, который умеет
/// поставить ADR.
pub fn memory(st: *State, s: *Signals) void {
    if (s.stat != .aok) return;

    switch (s.icode) {
        .rmmovq, .pushq => {
            s.mem_addr = s.val_e;
            s.mem_data = s.val_a;
            s.mem_write = true;
        },
        .call => {
            s.mem_addr = s.val_e;
            // На стек ложится адрес возврата, а он и есть valP.
            s.mem_data = s.val_p;
            s.mem_write = true;
        },
        .mrmovq => {
            s.mem_addr = s.val_e;
            s.mem_read = true;
        },
        .popq, .ret => {
            // Читаем по старому указателю стека, а не по увеличенному.
            s.mem_addr = s.val_a;
            s.mem_read = true;
        },
        else => return,
    }

    if (s.mem_write and !st.writeWord(s.mem_addr, s.mem_data)) s.stat = .adr;
    if (s.mem_read) {
        if (st.readWord(s.mem_addr)) |word| s.val_m = word else s.stat = .adr;
    }
}

Шесть инструкций из тринадцати ходят в память, и адрес у них берётся из двух разных мест. У rmmovq, mrmovq, pushq и call адрес это valE, то есть свежий результат ALU. У popq и ret адрес это valA, то есть старое значение %rsp, прочитанное на этапе decode.

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

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

writeback: два порта и их порядок

/// Запись обратно в регистры.
pub fn writeback(st: *State, s: *Signals) void {
    if (s.stat != .aok) return;
    // Порядок портов важен: E раньше M. Поэтому `popq %rsp` оставляет в %rsp
    // значение из памяти, а не увеличенный указатель стека.
    st.set(s.dst_e, s.val_e);
    st.set(s.dst_m, s.val_m);
}

Две строки, и обе принципиальны. У регистрового файла Y86-64 два порта записи: E принимает результат ALU, M принимает слово из памяти. Обычно они пишут в разные регистры или один из них выключен. Ровно одна инструкция во всём наборе способна направить оба порта в один регистр, и это popq %rsp. Тогда решает порядок, и он зафиксирован: побеждает порт M.

Никаких проверок здесь нет, потому что set в RNONE не пишет. Инструкция, у которой нет приёмника, дважды записывает “никуда”.

pcUpdate: куда идти дальше

/// Выбор следующего PC.
pub fn pcUpdate(st: *State, s: *Signals) void {
    if (s.stat != .aok) return;
    st.pc = switch (s.icode) {
        .jxx => if (s.cnd) s.val_c else s.val_p,
        .call => s.val_c,
        .ret => s.val_m,
        else => s.val_p,
    };
}

Четыре источника нового PC, и каждый из них уже посчитан кем-то раньше: valC пришёл из fetch, valP оттуда же, valM из памяти, Cnd из execute. Сам этап ничего не вычисляет, он только выбирает. В Verilog это будет мультиплексор на четыре входа, и код рядом с ним будет выглядеть почти так же.

Заметь, что ret берёт новый PC из памяти, то есть из результата этапа memory. Это самая длинная цепочка зависимостей во всей машине: прочитать байты, прочитать регистр, посчитать адрес, сходить в память, выбрать PC. В конвейере она обернётся тремя пузырьками, и мы к этому вернёмся в 32-systems/29 · PIPE: риски, продвижение и остановы.

step и run

/// Один такт: шесть этапов подряд над одним набором проводов.
pub fn step(st: *State) Retired {
    const pc = st.pc;
    var s: Signals = .{};

    fetch(st, &s);
    decode(st, &s);
    execute(st, &s);
    memory(st, &s);
    writeback(st, &s);
    pcUpdate(st, &s);

    st.stat = s.stat;
    return .{ .pc = pc, .icode = s.icode, .ifun = s.ifun, .stat = s.stat };
}

/// Крутит такты, пока машина в состоянии AOK. Возвращает число тактов;
/// у последовательной машины это же и число исполненных инструкций.
pub fn run(st: *State, max_steps: usize) usize {
    var cycles: usize = 0;
    while (st.stat == .aok and cycles < max_steps) : (cycles += 1) {
        _ = step(st);
    }
    return cycles;
}

Вот и весь процессор. Шесть вызовов подряд, Signals заводится заново на каждой инструкции, stat переезжает из проводов в состояние в самом конце.

step возвращает маленькую структуру Retired. В ней адрес самой инструкции (а не следующей, pc снят до всех этапов), пара icode и ifun и код состояния после инструкции. Больше трассе ничего не нужно.

/// Что нужно знать трассе об исполненной инструкции.
pub const Retired = struct {
    /// Адрес самой инструкции, а не следующей.
    pc: u64,
    icode: Icode,
    ifun: u4,
    /// Состояние машины после этой инструкции.
    stat: Stat,
};

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

Пощёлкай машину по шагам, прежде чем читать дальше. Выбери программу и жми “шаг”: после каждой инструкции виджет показывает четыре вещи разом. Сверху бейджи с PC, кодом состояния, числом тактов и тремя флагами. Слева регистры, изменившиеся подсвечены. В середине панель сигналов, и это главное, ради чего виджет тут стоит: те самые имена из таблицы этапов, от icode и valP до valE, Cnd, dstE, dstM, valM и нового PC, с их значениями в этом такте. Справа два окна памяти, вокруг %rsp с отметкой на вершине стека и вокруг данных программы. Снизу копится трасса того самого формата, который мы зафиксируем ниже.

Кнопка “назад” отменяет шаг, “до конца” догоняет программу до останова. Останови машину на pushq и загляни в панель сигналов: valA это то, что уйдёт в память, valE это новый указатель стека. На этой паре держится вся история с pushq %rsp, к которой мы придём в конце урока.

Коды Stat и порядок проверок

Четыре кода состояния, и у каждого своя точка появления:

код	значение	кто ставит
AOK	всё в порядке	никто, это исходное
HLT	встретился `halt`	fetch
ADR	обращение за границу памяти	fetch или memory
INS	недопустимая инструкция	fetch

Три из четырёх ставятся в fetch, и это не случайность: почти всё, что может пойти не так в Y86-64, выясняется при чтении байтов. Единственное исключение это обращение к данным по плохому адресу, и его ловит memory.

Порядок проверок внутри fetch не произволен. Сначала “влезает ли инструкция в память”, потом “законна ли она”. Возьми последний байт памяти и положи туда 0x30, начало irmovq. Инструкция должна занять десять байт, а их нет. Что это?

Если проверять законность первой, получится INS: irmovq с непонятно чем в полях. Но в железе никакой законности проверить нельзя, потому что байты просто не прочитаны, память их не отдала. Значит правильный ответ ADR, и наш fetch даёт именно его, потому что decode отвечает ошибкой Truncated раньше, чем доходит до проверки valid.

То же самое сформулировано в книге как функция Stat, где imem_error стоит выше instr_valid. Мы к этому вернёмся в 32-systems/27 · SEQ: execute, memory, write back и новый PC, когда будем писать модуль stat.sv: там порядок задаётся приоритетом веток в case, и перепутать его так же легко.

Посмотрим на оба случая живьём. Программа с плохим адресом:

        .pos 0
        irmovq $0xff0, %rbx
        mrmovq 0x10(%rbx), %rax
        halt

Адрес чтения это 0xff0 плюс 0x10, то есть 0x1000, а память кончается на 0xfff. Запускаем:

$ zig build run -- trace adr.ys
0x000 30 AOK
0x00a 50 ADR
halt cycles=2
%rax 0x0000000000000000
...

Две инструкции: irmovq прошла, mrmovq встала. В %rax ноль, потому что этап writeback у сломанной инструкции не отработал. До halt дело не дошло.

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

        .pos 0
        irmovq $7, %rax
        jmp bad
        .align 8
bad:    .byte 0xd0

$ zig build run -- trace ins.ys
0x000 30 AOK
0x00a 70 AOK
0x018 d0 INS
halt cycles=3
%rax 0x0000000000000007
...

Машина дошла по jmp до данных, попыталась прочитать их как код и остановилась. В трассе стоит d0: кода операции 0xd в наборе нет. Это ровно то, что происходит в настоящей программе, когда испорченный указатель функции уводит поток управления в данные, только там вместо аккуратного INS будет сигнал от операционной системы.

halt идёт через тот же механизм, хотя это не ошибка. Разница только в том, что HLT это нормальное завершение: тесты ждут именно его.

Трасса v1: контракт между тремя реализациями

Симулятор должен что-то печатать, и вот тут начинается самое важное решение урока. Формат вывода это не удобство отладки, это контракт. Через пять уроков такой же текст будет печатать тестбенч SEQ на Verilog, через восемь уроков конвейерный PIPE, и все три обязаны совпасть.

Файл src/sim/trace.zig:

//! Трасса v1: единственный формат, по которому сверяются все реализации
//! Y86-64 в этом курсе.
//!
//! Строки идут так:
//!
//!   0x000 30 AOK        адрес инструкции, icode и ifun одной парой, статус после неё
//!   ...
//!   halt cycles=12      сколько тактов заняла программа
//!   %rax 0x00000000...  пятнадцать регистров в порядке от rax до r14
//!   mem 0x0f8 0x...     слова памяти, отличающиеся от загруженного образа
//!
//! Сверять трассы разных реализаций можно построчно, кроме строки с тактами:
//! у последовательной машины такт равен инструкции, у конвейера нет.

const std = @import("std");

const isa = @import("../isa.zig");
const cpu = @import("cpu.zig");
const state = @import("state.zig");

const State = state.State;
const Writer = std.Io.Writer;

pub const Options = struct {
    /// Предохранитель от программы, которая не доходит до останова.
    max_steps: usize = 100_000,
};

pub const Summary = struct {
    cycles: usize,
    stat: isa.Stat,
    /// true, если такты кончились раньше, чем машина остановилась.
    hit_limit: bool,
};

/// Загружает образ, прогоняет программу и пишет трассу. Состояние остаётся
/// в `st`, так что после вызова его можно проверить.
pub fn write(w: *Writer, st: *State, image: []const u8, opts: Options) Writer.Error!Summary {
    st.* = .init();
    st.load(image);

    var cycles: usize = 0;
    while (st.stat == .aok and cycles < opts.max_steps) {
        const retired = cpu.step(st);
        cycles += 1;
        try writeInstruction(w, retired);
    }

    try w.print("halt cycles={d}\n", .{cycles});
    try writeRegisters(w, st);
    try writeMemory(w, st, image);

    return .{ .cycles = cycles, .stat = st.stat, .hit_limit = st.stat == .aok };
}

/// То же самое, но текстом в памяти: так удобнее тестам.
pub fn toOwned(gpa: std.mem.Allocator, image: []const u8, opts: Options) std.mem.Allocator.Error![]u8 {
    var out: Writer.Allocating = .init(gpa);
    errdefer out.deinit();
    var st: State = .init();
    _ = write(&out.writer, &st, image, opts) catch return error.OutOfMemory;
    return out.toOwnedSlice();
}

fn writeInstruction(w: *Writer, retired: cpu.Retired) Writer.Error!void {
    try w.print("0x{x:0>3} {x}{x} {s}\n", .{
        retired.pc,
        @intFromEnum(retired.icode),
        retired.ifun,
        retired.stat.name(),
    });
}

fn writeRegisters(w: *Writer, st: *const State) Writer.Error!void {
    for (isa.reg_names, st.regs) |name, value| {
        try w.print("{s} 0x{x:0>16}\n", .{ name, value });
    }
}

/// Печатает только те слова, которые программа изменила. Полный дамп четырёх
/// килобайт читать невозможно, а разница почти всегда в десяток строк.
fn writeMemory(w: *Writer, st: *const State, image: []const u8) Writer.Error!void {
    var addr: u64 = 0;
    while (addr + 8 <= isa.mem_size) : (addr += 8) {
        const now = st.readWord(addr).?;
        if (now == initialWord(image, addr)) continue;
        try w.print("mem 0x{x:0>3} 0x{x:0>16}\n", .{ addr, now });
    }
}

/// Слово из загруженного образа. Байты, до которых образ не дотянулся, нулевые.
fn initialWord(image: []const u8, addr: u64) u64 {
    var bytes: [8]u8 = @splat(0);
    const at: usize = @intCast(addr);
    for (&bytes, 0..) |*b, i| {
        if (at + i < image.len) b.* = image[at + i];
    }
    return std.mem.readInt(u64, &bytes, .little);
}

Четыре решения, которые делают этот формат пригодным для сверки.

Одна строка на исполненную инструкцию, и в ней только то, что видно снаружи. Адрес, байт кода операции целиком (icode и ifun слитно, как они лежат в памяти) и код состояния после инструкции. Ни valE, ни valM, ни номеров регистров. Всё это внутренние сигналы, и у конвейера они появляются в других тактах. Сверять можно только то, что есть у всех трёх реализаций.

Дамп памяти это разница с образом, а не сама память. Четыре тысячи строк, из которых интересны десять, никто читать не станет. Мы печатаем слово, только если оно отличается от того, что загрузилось. Поэтому в трассе sum.ys видно ровно два адреса возврата, а сам массив, который программа читала, но не меняла, не попадает.

Регистры печатаются всегда все пятнадцать, в фиксированном порядке. Даже нулевые. Это делает diff двух трасс осмысленным: строки не съезжают.

Строка с тактами стоит отдельно и сверке не подлежит. У SEQ такт равен инструкции, у PIPE нет: там будут пузырьки и остановы, и число тактов вырастет. Поэтому tools/compare-trace.sh эту строку выкидывает, а всё остальное сравнивает построчно.

Читаем трассу sum.ys построчно

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

0x000: 30f40002000000000000 | init:   irmovq stack, %rsp
0x00a: 803800000000000000   |         call main
0x013: 00                   |         halt
0x018: 0d000d000d000000     | array:  .quad 0x000d000d000d
0x020: c000c000c0000000     |         .quad 0x00c000c000c0
0x028: 000b000b000b0000     |         .quad 0x0b000b000b00
0x030: 00a000a000a00000     |         .quad 0xa000a000a000
0x038: 30f71800000000000000 | main:   irmovq array, %rdi
0x042: 30f60400000000000000 |         irmovq $4, %rsi
0x04c: 805600000000000000   |         call sum
0x055: 90                   |         ret
0x056: 30f80800000000000000 | sum:    irmovq $8, %r8
0x060: 30f90100000000000000 |         irmovq $1, %r9
0x06a: 6300                 |         xorq %rax, %rax
0x06c: 6266                 |         andq %rsi, %rsi
0x06e: 708700000000000000   |         jmp test
0x077: 50a70000000000000000 | loop:   mrmovq (%rdi), %r10
0x081: 60a0                 |         addq %r10, %rax
0x083: 6087                 |         addq %r8, %rdi
0x085: 6196                 |         subq %r9, %rsi
0x087: 747700000000000000   | test:   jne loop
0x090: 90                   |         ret

А теперь трасса, целиком, как её печатает zig build run -- trace programs/sum.ys:

0x000 30 AOK
0x00a 80 AOK
0x038 30 AOK
0x042 30 AOK
0x04c 80 AOK
0x056 30 AOK
0x060 30 AOK
0x06a 63 AOK
0x06c 62 AOK
0x06e 70 AOK
0x087 74 AOK
0x077 50 AOK
0x081 60 AOK
0x083 60 AOK
0x085 61 AOK
0x087 74 AOK
0x077 50 AOK
0x081 60 AOK
0x083 60 AOK
0x085 61 AOK
0x087 74 AOK
0x077 50 AOK
0x081 60 AOK
0x083 60 AOK
0x085 61 AOK
0x087 74 AOK
0x077 50 AOK
0x081 60 AOK
0x083 60 AOK
0x085 61 AOK
0x087 74 AOK
0x090 90 AOK
0x055 90 AOK
0x013 00 HLT
halt cycles=34
%rax 0x0000abcdabcdabcd
%rcx 0x0000000000000000
%rdx 0x0000000000000000
%rbx 0x0000000000000000
%rsp 0x0000000000000200
%rbp 0x0000000000000000
%rsi 0x0000000000000000
%rdi 0x0000000000000038
%r8 0x0000000000000008
%r9 0x0000000000000001
%r10 0x0000a000a000a000
%r11 0x0000000000000000
%r12 0x0000000000000000
%r13 0x0000000000000000
%r14 0x0000000000000000
mem 0x1f0 0x0000000000000055
mem 0x1f8 0x0000000000000013

Разберём её по кускам.

Первые пять строк это вход в программу. 0x000 30 это irmovq stack, %rsp, указатель стека стал 0x200. 0x00a 80 это call main: valE равен 0x200 минус восемь, то есть 0x1f8, туда уходит valP, а valP у девятибайтного call с адреса 0x00a равен 0x013. Смотри последнюю строку дампа памяти: там лежит именно 0x13, адрес halt. Дальше PC становится valC, то есть 0x038, и трасса прыгает туда.

Второй call кладёт второй адрес возврата. 0x04c 80 вычитает ещё восемь, вершина уезжает на 0x1f0, и туда ложится 0x055, адрес ret в main. Обе строки дампа памяти теперь объяснены: это два кадра вызова, которые остались в памяти после того, как ret их сняли. Стек не “очищается”, просто %rsp возвращается наверх, а байты остаются лежать. Ровно то же самое ты видел в уроке про кадры вызова на настоящем x86-64, только там кадр больше двух слов и в нём лежат ещё сохранённые регистры и локальные переменные.

Пролог функции виден по четырём строкам подряд. 0x056 30 и 0x060 30 заводят константы 8 и 1 в %r8 и %r9. 0x06a 63 это xorq %rax, %rax: icode равен 6, ifun равен 3, то есть xor. Регистр обнулился, заодно выставились флаги. 0x06c 62 это andq %rsi, %rsi, ifun равен 2. Значение %rsi не изменилось, а флаги выставились по нему: это единственная причина, по которой инструкция здесь стоит.

Цикл начинается с прыжка в конец. 0x06e 70 это jmp test, безусловный переход с ifun равным нулю, и следующая строка сразу 0x087, то есть jne loop. Это раскладка jump to middle из урока про циклы: проверка стоит внизу, и первый вход в цикл идёт сразу на неё. Если бы %rsi был нулём, jne не сработал бы и тело не выполнилось бы ни разу.

Тело цикла это пять строк, повторённых четыре раза. Найди в трассе последовательность 0x077 50, 0x081 60, 0x083 60, 0x085 61, 0x087 74 и посчитай, сколько раз она встречается. Ровно четыре, по числу элементов массива. Три соседние строки с icode равным 6 отличаются только ifun: 60 это addq дважды, 61 это subq. Именно subq выставляет флаги, на которые смотрит 74, то есть jne.

Хвост это два ret и halt. 0x090 90 возвращается в main по адресу 0x055, 0x055 90 возвращается в init по адресу 0x013, и там стоит 00 HLT. Обрати внимание, что после halt строки больше нет и PC остался равен 0x013: halt не двигает счётчик.

Итоговое состояние сходится с арифметикой. В %rax сумма, 0xabcdabcdabcd. В %rdi адрес 0x38, то есть указатель дошёл до конца массива: 0x18 плюс четыре раза по восемь. В %rsi ноль, счётчик отработал. В %r10 последний прочитанный элемент. %rsp вернулся на 0x200, значит call и ret сошлись, и это самая полезная проверка во всей трассе: разъехавшийся стек ловится одним взглядом.

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

push_pop_rsp: две тонкости указателя стека

Есть две инструкции, на которых расходятся симуляторы, написанные по невнимательности. Обе про %rsp в качестве операнда, и книга обе выносит в отдельные упражнения.

Вопрос первый: pushq %rsp кладёт в память старое значение указателя или уже уменьшенное?

Вопрос второй: popq %rsp оставляет в регистре слово из памяти или увеличенный указатель?

Ответы не выводятся из здравого смысла, они выводятся из схемы. Программа programs/push_pop_rsp.ys проверяет оба случая:

# Два спорных случая из книги, оба про указатель стека.
#
# pushq %rsp кладёт в память старое значение %rsp, потому что valA читается
# до того, как порт E запишет уменьшенный указатель.
#
# popq %rsp оставляет в %rsp значение из памяти, потому что порт M пишет
# после порта E.

        .pos 0
init:   irmovq stack, %rsp
        pushq %rsp              # в память уходит 0x200
        popq %rax               # %rax равен 0x200, а не 0x1f8
        irmovq $0x123, %rbx
        pushq %rbx
        popq %rsp               # %rsp равен 0x123, а не 0x200
        halt

        .pos 0x200
stack:

Трасса короткая, разберём её целиком:

$ zig build run -- trace programs/push_pop_rsp.ys
0x000 30 AOK
0x00a a0 AOK
0x00c b0 AOK
0x00e 30 AOK
0x018 a0 AOK
0x01a b0 AOK
0x01c 00 HLT
halt cycles=7
%rax 0x0000000000000200
%rcx 0x0000000000000000
%rdx 0x0000000000000000
%rbx 0x0000000000000123
%rsp 0x0000000000000123
%rbp 0x0000000000000000
%rsi 0x0000000000000000
%rdi 0x0000000000000000
%r8 0x0000000000000000
%r9 0x0000000000000000
%r10 0x0000000000000000
%r11 0x0000000000000000
%r12 0x0000000000000000
%r13 0x0000000000000000
%r14 0x0000000000000000
mem 0x1f8 0x0000000000000123

Пройдём pushq %rsp по этапам. Инструкция на адресе 0x00a, %rsp равен 0x200.

этап	что происходит
fetch	`icode` равен a, `rA` это `%rsp`, `rB` это RNONE, `valP` равен `0x00c`
decode	`srcA` это `%rsp`, `srcB` это `%rsp`, `dstE` это `%rsp`. `valA` равен `0x200`, `valB` равен `0x200`
execute	`valE` равен `valB` минус восемь, то есть `0x1f8`
memory	пишет `valA`, то есть `0x200`, по адресу `valE`, то есть `0x1f8`
writeback	порт E пишет `0x1f8` в `%rsp`
pcUpdate	PC равен `valP`

Ключ в том, что valA прочитан на этапе decode, а порт E пишет на этапе writeback, то есть на два этапа позже. К моменту записи в память значение valA уже давно снято с регистрового файла и едет по проводу. Поэтому в память уходит старое 0x200. Следующая инструкция popq %rax снимает его обратно, и в %rax оказывается 0x200, что трасса и показывает.

Теперь popq %rsp на адресе 0x01a. К этому моменту на вершине стека лежит 0x123, положенное предыдущим pushq %rbx, и %rsp равен 0x1f8.

этап	что происходит
fetch	`icode` равен b, `rA` это `%rsp`, `rB` это RNONE
decode	`srcA` это `%rsp`, `srcB` это `%rsp`, `dstE` это `%rsp`, `dstM` это `rA`, то есть тоже `%rsp`
execute	`valE` равен `valB` плюс восемь, то есть `0x200`
memory	читает по `valA`, то есть по `0x1f8`, и получает `0x123` в `valM`
writeback	порт E пишет `0x200` в `%rsp`, потом порт M пишет `0x123` в `%rsp`
pcUpdate	PC равен `valP`

Оба порта нацелены на один регистр, и побеждает тот, который пишет последним. В нашем коде это две строки подряд, и порядок между ними задан явно. В железе это тоже не случайность: приоритет портов записи прописан в регистровом файле, и мы напишем его руками в 32-systems/25 · Verilog: такт, регистры и память.

Итог в трассе: %rsp равен 0x123, а не 0x200. Указатель стека уехал в произвольное место, потому что программист так попросил.

Заодно посмотри, сколько строк в дампе памяти. Одна. Первый pushq записал 0x200 по адресу 0x1f8, второй записал туда же 0x123 и затёр первое значение. В памяти остался только результат, а история осталась в трассе. Это тоже часть контракта: трасса показывает, что делала машина, дамп показывает, чем всё кончилось.

Загрузка программы: .yo и .hex

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

Подкоманды sim и trace из src/main.zig:

fn simulateCommand(cli: Cli, path: []const u8) !void {
    const text = try readSource(cli, path);
    defer cli.gpa.free(text);

    const image = if (std.mem.endsWith(u8, path, ".hex"))
        try assembler.loadHex(cli.gpa, text)
    else
        try assembler.loadYo(cli.gpa, text);
    defer cli.gpa.free(image);

    try runImage(cli, image);
}

fn traceCommand(cli: Cli, path: []const u8) !void {
    var result = try assembleFile(cli, path);
    defer result.deinit(cli.gpa);
    try runImage(cli, result.image);
}

fn runImage(cli: Cli, image: []const u8) !void {
    var machine: state.State = .init();
    const summary = try trace.write(cli.out, &machine, image, .{});
    if (summary.hit_limit) {
        try cli.err.writeAll("программа не дошла до останова: такты кончились\n");
        return error.StepLimit;
    }
}

Разница между sim и trace только в том, откуда берётся образ. sim читает уже собранный файл, trace собирает исходник на лету. Вторая команда для человека, первая для сверки с железом: Verilog получает тот же .hex, что и симулятор, и никакой ассемблер в цепочку не вмешивается.

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

Заметь hit_limit в Summary. Если такты кончились, а машина всё ещё в AOK, это не успешное завершение, а зацикливание, и команда обязана выйти с ошибкой. Иначе бесконечный цикл в тесте выглядел бы как “программа отработала, вот трасса”.

Вся связка целиком:

$ zig build run -- asm programs/sum.ys -o sum.yo --hex sum.hex
$ zig build run -- sim sum.yo | head -3
0x000 30 AOK
0x00a 80 AOK
0x038 30 AOK
$ zig build run -- sim sum.hex | tail -2
mem 0x1f0 0x0000000000000055
mem 0x1f8 0x0000000000000013

Оба формата дают один образ и одну трассу. В уроке 27 в эту же цепочку встанет bash hdl/run.sh seq sum.hex, и его вывод сравнится с этим построчно.

Тесты: каждая программа даёт известное состояние

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

Трассы лежат рядом с программами в programs/expected/ и вшиваются в модуль через @embedFile, как и сами исходники:

pub const Program = struct {
    /// Имя файла в `programs/`.
    name: []const u8,
    source: []const u8,
    /// Трасса v1, снятая этим же симулятором. Она же образец для Verilog
    /// и для движка виджетов: расходиться им нельзя.
    expected_trace: []const u8,
};

fn program(comptime name: []const u8) Program {
    return .{
        .name = name ++ ".ys",
        .source = @embedFile(name ++ ".ys"),
        .expected_trace = @embedFile(name ++ ".trace"),
    };
}

pub const all = [_]Program{
    program("sum"),
    program("rsum"),
    program("abs_sum"),
    program("abs_sum_cmov"),
    program("bubble"),
    program("switchv"),
    program("push_pop_rsp"),
    program("iaddq_sum"),
    program("hazard_forward"),
    program("load_use"),
    program("ret_bubbles"),
    program("mispredict"),
};

Собрать программу и получить её образ нужно в каждом тесте, поэтому это отдельный помощник:

/// Собирает программу и возвращает её образ памяти.
fn imageOf(program: y86.programs.Program) ![]u8 {
    var result = try y86.assembler.assemble(testing.allocator, program.source, null);
    defer result.deinit(testing.allocator);
    return testing.allocator.dupe(u8, result.image);
}

Главный тест урока сравнивает трассу с образцом байт в байт:

test "трасса каждой программы совпадает с образцом байт в байт" {
    for (y86.programs.all) |program| {
        const image = try imageOf(program);
        defer testing.allocator.free(image);

        const trace = try y86.trace.toOwned(testing.allocator, image, .{});
        defer testing.allocator.free(trace);

        testing.expectEqualStrings(program.expected_trace, trace) catch |err| {
            std.debug.print("программа {s}\n", .{program.name});
            return err;
        };
    }
}

Обёртка вокруг expectEqualStrings нужна ради одной строки диагностики. Без неё падение говорит “строки различаются”, и приходится гадать, какая из двенадцати программ сломалась.

Теперь неприятный вопрос. Что будет, если образец трассы пустой или обрезанный? Тест пройдёт. Сравнение с пустотой ничего не проверяет, а обрезанный файл молча разрешает любое расхождение в хвосте. Образцы читает не только этот тест, но и Verilog в уроках 27 и 30, так что порченый образец отравит весь блок. Поэтому отдельный тест проверяет форму каждого образца до сравнения:

test "образец трассы у каждой программы непустой и правильной формы" {
    for (y86.programs.all) |program| {
        const trace = program.expected_trace;

        testing.expect(trace.len > 0) catch |err| {
            std.debug.print("образец трассы {s} пуст\n", .{program.name});
            return err;
        };

        // Первая строка это всегда первая инструкция по адресу 0x000.
        try testing.expect(std.mem.startsWith(u8, trace, "0x000 30 AOK\n"));

        // Ровно одна строка тактов, и число в ней больше нуля.
        try testing.expectEqual(@as(usize, 1), std.mem.count(u8, trace, "\nhalt cycles="));
        const marker = std.mem.indexOf(u8, trace, "halt cycles=").?;
        const after = trace[marker + "halt cycles=".len ..];
        const end = std.mem.indexOfScalar(u8, after, '\n').?;
        const cycles = try std.fmt.parseInt(usize, after[0..end], 10);
        try testing.expect(cycles > 0);

        // Инструкций в трассе ровно столько, сколько тактов: у последовательной
        // машины такт равен инструкции.
        try testing.expectEqual(cycles, std.mem.count(u8, trace[0..marker], "\n"));

        // Пятнадцать регистров, все до одного, в порядке от %rax до %r14.
        var at = marker;
        for (isa.reg_names) |name| {
            const line = std.mem.indexOfPos(u8, trace, at, name).?;
            at = line + name.len;
        }

        // Последняя строка кончается переводом строки: обрезанный файл
        // сравнение бы прошёл, а модели разошлись бы на последней строке.
        try testing.expect(std.mem.endsWith(u8, trace, "\n"));
    }
}

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

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

test "программы считают то, что обещают их комментарии" {
    const cases = [_]struct { name: []const u8, reg: isa.Reg, want: u64 }{
        // Сумма массива из четырёх слов, итеративная и рекурсивная.
        .{ .name = "sum.ys", .reg = .rax, .want = 0xabcdabcdabcd },
        .{ .name = "rsum.ys", .reg = .rax, .want = 0xabcdabcdabcd },
        .{ .name = "iaddq_sum.ys", .reg = .rax, .want = 0xabcdabcdabcd },
        // Сумма модулей: 5 плюс 3 плюс 7 плюс 9 плюс 1 плюс 4 равно 29.
        .{ .name = "abs_sum.ys", .reg = .rax, .want = 29 },
        .{ .name = "abs_sum_cmov.ys", .reg = .rax, .want = 29 },
        // ... остальные семь программ так же
        // popq %rsp взял значение из памяти, а не увеличенный указатель.
        .{ .name = "push_pop_rsp.ys", .reg = .rsp, .want = 0x123 },
    };
    // Каждая программа набора должна быть в списке.
    try testing.expectEqual(y86.programs.all.len, cases.len);
    // ... дальше прогон каждой программы и сравнение одного регистра
}

Последняя строка списка важнее, чем кажется. expectEqual(y86.programs.all.len, cases.len) не даёт добавить программу в набор и забыть про неё: новая программа сразу валит тест, пока для неё не написано, что она должна посчитать. Без такой проверки список тихо отстаёт от набора.

Три программы дают одну и ту же сумму 0xabcdabcdabcd тремя разными способами: итеративно, рекурсивно и через iaddq. Две дают 29 через ветвление и через cmovg. Это те самые пары, ради которых программы и написаны, и тест фиксирует, что расхождение между ними это ошибка, а не особенность.

Отдельный тест проверяет исключения, причём не только код состояния, но и то, что инструкция попала в трассу со своим статусом:

test "ошибки останавливают машину и попадают в трассу" {
    const cases = [_]struct { image: []const u8, want: isa.Stat, tail: []const u8 }{
        // Байта 0xf0 в наборе нет.
        .{ .image = &[_]u8{0xf0}, .want = .ins, .tail = "0x000 f0 INS\n" },
        // mrmovq 0xfff(%rax), %rbx: слово по такому адресу не помещается.
        .{ .image = &[_]u8{ 0x50, 0x30, 0xff, 0x0f, 0, 0, 0, 0, 0, 0 }, .want = .adr, .tail = "0x000 50 ADR\n" },
        // halt на первой же инструкции.
        .{ .image = &[_]u8{0x00}, .want = .hlt, .tail = "0x000 00 HLT\n" },
    };
    for (cases) |case| {
        var st: State = .init();
        var out: std.Io.Writer.Allocating = .init(testing.allocator);
        defer out.deinit();
        const summary = try y86.trace.write(&out.writer, &st, case.image, .{});

        try testing.expectEqual(case.want, summary.stat);
        try testing.expectEqual(@as(usize, 1), summary.cycles);
        try testing.expect(std.mem.startsWith(u8, out.written(), case.tail));
    }
}

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

И последний тест закрывает предохранитель:

test "предохранитель по тактам срабатывает на вечной программе" {
    // jmp 0: программа прыгает сама на себя и никогда не остановится.
    const image = [_]u8{ 0x70, 0, 0, 0, 0, 0, 0, 0, 0 };
    var st: State = .init();
    var out: std.Io.Writer.Discarding = .init(&.{});
    const summary = try y86.trace.write(&out.writer, &st, &image, .{ .max_steps = 50 });

    try testing.expectEqual(@as(usize, 50), summary.cycles);
    try testing.expect(summary.hit_limit);
}

Девять байт, из которых восемь нули: jmp на адрес ноль, то есть на самого себя. Без max_steps этот тест повесил бы сборку навсегда, а с ним он проверяет, что hit_limit действительно выставляется и sim вернёт ошибку, а не сделает вид, что программа отработала.

Ключ -Dstep=22 гоняет тесты только этого шага, без него zig build test гоняет все:

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

Двадцать два теста это те, что лежат прямо рядом с кодом, в самих файлах модуля: границы памяти в state.zig, таблица условий и переполнение в isa.zig, кодирование в обе стороны в encoder.zig. Восемь это тесты шага 22 из tests/step_22.zig, разобранные выше.

Практика

Напиши сердце симулятора сам. Всё вокруг уже готово: состояние, чтение и запись слов, декодер байтов, таблица условий и ALU. Нет только step, то есть одной инструкции от выборки байтов до нового PC.

Тесты гоняют настоящие программы четвёртой главы, включая обе тонкости с %rsp и сумму на iaddq, и сверяют регистры, изменённые слова памяти, число тактов и код состояния. Отдельные тесты ловят ADR и INS, в том числе порядок между ними.

Упражнения

CHK-1★

Возьми трассу sum.ys и найди в ней все строки, где icode равен 6. Выпиши для каждой, какая это мнемоника (по ifun) и что она делает с флагами. Объясни, почему andq %rsi, %rsi вообще стоит в программе, если её результат равен её же операнду.

CHK-2★★

Книга разбирает pushq %rsp и popq %rsp в упражнениях 4.7 и 4.8. Ответь на оба, не заглядывая в код: какое значение уходит в память при pushq %rsp и какое остаётся в регистре после popq %rsp. Потом проверь себя на programs/push_pop_rsp.ys и объясни ответы через этапы, а не через результат.

CHK-3★★

Поменяй в writeback местами две строки, то есть пусть порт M пишет раньше порта E. Какие программы из двенадцати сломаются? Прогони zig build test и убедись, что твой прогноз совпал с падением. Верни порядок обратно.

CHK-4★★

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

CHK-5★★★

Добавь в симулятор дизассемблирующую трассу: рядом с байтом кода операции печатай мнемонику и операнды, как их написал бы человек. Функция isa.mnemonicOf уже есть. Сделай это отдельным флагом, чтобы обычная трасса осталась побайтово прежней, иначе сверка с Verilog сломается.

CHK-6★★★

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

Итоги

Одна инструкция это шесть этапов над одной структурой состояния: fetch, decode, execute, memory, writeback, pcUpdate. Разбиение избыточно для интерпретатора и обязательно для того, чтобы код лёг на Verilog.
Состояние, видимое программисту, это пятнадцать регистров, память, PC, три флага и код состояния. Всё остальное это провода, живущие внутри одного такта.
RNONE читается как ноль и не пишется. Из этого сами собой получаются cmovXX с ложным условием и writeback без единой проверки.
Флаги меняют только OPq и iaddq. Адресная арифметика и работа со стеком идут через то же ALU, но флаги не трогают.
Порядок проверок в fetch не произволен: сначала “влезает ли инструкция в память” (ADR), потом “законна ли она” (INS). В железе иначе и не выйдет, потому что байты сначала надо прочитать.
Порт E пишет раньше порта M. Отсюда popq %rsp, оставляющий в регистре слово из памяти.
valA читается на decode, а порт E пишет на writeback. Отсюда pushq %rsp, кладущий в память старое значение.
Трасса v1 это контракт: адрес, байт кода операции, статус на инструкцию, потом такты, потом все регистры, потом изменённые слова памяти. По ней сверяются симулятор, SEQ и PIPE.
Тесты проверяют полное совпадение трассы для всех двенадцати программ плюс отдельные утверждения о смысле: суммы совпадают, стек возвращается на место, iaddq укорачивает цикл.

Дальше

Y86-64 у тебя теперь есть дважды: как ассемблер, который делает из текста байты, и как симулятор, который эти байты исполняет. Обе половины написаны на Zig, обе работают, и трасса, которую печатает вторая, зафиксирована как формат.

Дальше начинается железо. Следующий урок это первое знакомство с языком описания аппаратуры: модуль как схема с портами, assign как провод, вентили как операторы, и главное отличие HDL от программы: в схеме всё вычисляется одновременно, и порядок строк не важен. Примеры на HCL из книги мы переведём на Verilog один в один: равенство битов, битовый мультиплексор, компаратор слов. Гонять их будем под Icarus Verilog, а verilator --lint-only возьмём в привычку сразу, потому что незамеченный провод и несовпадение ширин ловятся им раньше, чем симуляцией.

Через пять уроков эти вентили сложатся в шесть модулей SEQ с теми же именами, что у шести функций сегодняшнего файла cpu.zig, и первое, что мы сделаем, собрав процессор, это прогоним на нём sum.ys и сравним трассу с той, которую ты сегодня читал построчно.

домашка

Домашка

Возьми любую программу из урока 21, руками распиши шесть этапов для первых пяти инструкций (icode, ifun, rA, rB, valC, valP, valA, valB, valE, valM, Cnd) и сверь свою таблицу с настоящей трассой симулятора.S
Поменяй в writeback порядок портов E и M местами, прогони push_pop_rsp.ys и опиши, какая строка трассы изменилась и почему. Верни порядок обратно.S
Добавь в машину пятый код состояния для деления на ноль (инструкции divq пока нет, придумай, как она выглядела бы) и объясни, на каком этапе он должен появляться и почему не раньше.S