Раздел 32 · Системное программирование: Zig, ассемблер, Verilog
Ассемблер Y86-64 на Zig
открытый урокЭтот раздел читается без входа. Войди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти
Ассемблер Y86-64 на Zig
В прошлом уроке ты кодировал инструкции руками: брал мнемонику, находил icode и ifun, складывал байт регистров, дописывал восемь байт valC. Занятие честное, но на третьей программе надоедает. Сегодня мы поручаем это программе. Пишем настоящий ассемблер: лексер режет строку на токены, парсер собирает из токенов инструкцию или директиву, первый проход считает адреса и запоминает метки, второй кодирует байты. На выходе два файла. Листинг
.yo, где каждая строка исходника стоит рядом со своими байтами, и образ памяти.hex, который через несколько уроков загрузит процессор на Verilog. Это первый инструмент y86lab, и весь остальной блок будет им пользоваться.
Цели урока
- Понять, зачем ассемблеру нужны именно два прохода и почему в Y86-64 их хватает ровно двух, а в x86-64 нет.
- Написать лексер, который режет строку исходника на токены и умеет отличить
-8(%rbp)от%rbpи от8. - Написать парсер, который по мнемонике знает форму операндов и собирает инструкцию, оставляя метки неразрешёнными.
- Реализовать директивы
.pos,.alignи.quadи понять, чем они отличаются от инструкций с точки зрения адреса. - Собрать таблицу меток в первом проходе и разрешить по ней переходы вперёд во втором.
- Напечатать листинг в формате
.yoи понять, зачем в нём одна строка исходника на строку вывода. - Выдать образ памяти в формате
.hex, который читает системная задача$readmemhв Verilog. - Написать на Y86-64 шесть программ главы 4 и собрать их своим ассемблером: сумму массива, рекурсивную сумму, сумму модулей с переходом и с
cmov, пузырьковую сортировку и переключатель через таблицу адресов.
Идея: длина известна заранее, значит проходов хватит двух
Ассемблер решает одну неудобную задачу. Программа читается сверху вниз, а ссылки идут в обе стороны. Строка jmp test встречается раньше, чем метка test, и в этот момент адрес метки ещё не известен. Значит одним проходом не обойтись: пока читаешь текст, ты не знаешь всех адресов, а чтобы знать адреса, надо прочитать текст.
Выход классический. Первый проход не кодирует ничего, он только считает адрес каждой строки и складывает метки в таблицу. Второй проход кодирует байты, и таблица к этому моменту полная, поэтому ссылка вперёд разрешается так же просто, как ссылка назад.
Первый проход умеет считать адреса только потому, что длина инструкции Y86-64 известна сразу. Она зависит от кода операции и больше ни от чего: halt это один байт всегда, addq два байта всегда, irmovq десять байт всегда, независимо от того, какое число или какая метка стоит в операнде. Прочитал мнемонику, узнал длину, прибавил к адресу.
В x86-64 это не так. Там jmp бывает коротким (смещение в один байт) и длинным (смещение в четыре байта), и какой выбрать, зависит от расстояния до цели, а расстояние зависит от того, какие переходы выбраны по дороге. Настоящий ассемблер x86 решает эту задачу итеративно: начинает с коротких переходов и удлиняет те, которым не хватило, пока размеры не перестанут меняться. Проходов получается не два, а сколько понадобится. Учебная система команд избавляет нас от этой возни нарочно, и это одна из причин, по которым в главе 4 книги вообще возможен ассемблер на две сотни строк.
Ещё одно упрощение, которое стоит назвать вслух. Наш ассемблер не создаёт объектный файл и не оставляет ничего компоновщику: он сразу пишет байты по абсолютным адресам в образ памяти на четыре килобайта. Никакой релокации здесь не будет. Это не упущение, а свойство машины: память у Y86-64 одна, программа в ней одна, адреса окончательные. Компоновку мы разберём отдельно, в блоке про ELF.
Вот вся схема по шагам.
- Текст
.ysпопадает в лексер, лексер отдаёт токены. - Парсер собирает из токенов строку: метку, директиву или инструкцию.
- Первый проход раскладывает строки по адресам и заполняет таблицу меток.
- Второй проход кодирует байты и печатает листинг.
Дальше по коду в том же порядке.
Раскладка проекта
Весь y86lab живёт в одном проекте на Zig. Сегодня появляются четыре файла ассемблера и таблицы системы команд, к которым они обращаются:
y86/
build.zig
src/
isa.zig таблицы Y86-64: коды, регистры, длины, мнемоники
asm/
lexer.zig строка исходника в токены
parser.zig токены в метку, директиву или инструкцию
encoder.zig поля инструкции в байты
assembler.zig два прохода, таблица меток, листинг и образ
main.zig программа y86, подкоманда asm
programs/
sum.ys rsum.ys abs_sum.ys abs_sum_cmov.ys bubble.ys switchv.ysФайл isa.zig целиком разобран в прошлом уроке: там перечисления Icode и Reg, функции needRegids, needValC и length, таблица мнемоник и lookupMnemonic. Сегодня к ним добавится одна вещь: форма операндов.
/// Форма операндов: она же говорит ассемблеру, что разбирать после мнемоники.
pub const Form = enum {
/// `halt`, `nop`, `ret`
none,
/// `rrmovq rA, rB`, `cmovXX rA, rB`, `OPq rA, rB`
reg_reg,
/// `irmovq V, rB`, `iaddq V, rB`
imm_reg,
/// `rmmovq rA, D(rB)`
reg_mem,
/// `mrmovq D(rB), rA`
mem_reg,
/// `pushq rA`, `popq rA`
reg,
/// `jXX Dest`, `call Dest`
dest,
};
pub fn form(icode: Icode) Form {
return switch (icode) {
.cmovxx, .opq => .reg_reg,
.irmovq, .iaddq => .imm_reg,
.rmmovq => .reg_mem,
.mrmovq => .mem_reg,
.pushq, .popq => .reg,
.jxx, .call => .dest,
else => .none,
};
}Семь форм на двенадцать инструкций. Это вся грамматика операндов Y86-64, и парсеру больше ничего знать не нужно: он смотрит на форму и разбирает ровно то, что она обещает. Обрати внимание, что форма привязана к icode, а не к мнемонике: addq и xorq это один icode с разным ifun, и разбираются они одинаково.
Лексер: строка в токены
Язык ассемблера построчный. Инструкция не переносится на следующую строку, метка тоже, директива тоже. Значит и лексер можно сделать построчным: он получает одну строку и отдаёт токены до конца строки. Комментарий от решётки до конца строки лексер съедает и говорит eof.
//! Токены одной строки исходника на yas.
//!
//! Разбор построчный, потому что и язык построчный: инструкция, директива или
//! метка не переносятся на следующую строку. Комментарий от `#` до конца строки
//! лексер просто съедает и отдаёт `eof`.
const std = @import("std");
pub const Tag = enum {
/// Имя метки или мнемоника.
ident,
/// Число: десятичное, шестнадцатеричное `0x...`, возможно со знаком минус.
number,
/// Регистр вместе с процентом: `%rax`.
register,
/// Директива без точки: у `.pos` текст токена будет `pos`.
directive,
dollar,
comma,
lparen,
rparen,
colon,
eof,
};
pub const Token = struct {
tag: Tag,
/// Срез исходной строки, годится и для сообщения об ошибке.
text: []const u8,
};
pub const Error = error{
/// Символ, которому в yas места нет.
BadCharacter,
/// Число не разобралось или не влезло в 64 бита.
BadNumber,
};
pub const Lexer = struct {
src: []const u8,
pos: usize = 0,
pub fn init(line: []const u8) Lexer {
return .{ .src = line };
}
pub fn next(self: *Lexer) Error!Token {
self.skipSpace();
if (self.pos >= self.src.len) return .{ .tag = .eof, .text = self.src[self.src.len..] };
const start = self.pos;
const c = self.src[start];
switch (c) {
',' => return self.single(.comma),
'(' => return self.single(.lparen),
')' => return self.single(.rparen),
':' => return self.single(.colon),
'$' => return self.single(.dollar),
'.' => {
self.pos += 1;
const name_start = self.pos;
self.skipIdent();
if (self.pos == name_start) return error.BadCharacter;
return .{ .tag = .directive, .text = self.src[name_start..self.pos] };
},
'%' => {
self.pos += 1;
self.skipIdent();
return .{ .tag = .register, .text = self.src[start..self.pos] };
},
'-', '0'...'9' => {
self.pos += 1;
while (self.pos < self.src.len and isNumberChar(self.src[self.pos])) self.pos += 1;
const text = self.src[start..self.pos];
_ = try parseNumber(text);
return .{ .tag = .number, .text = text };
},
else => {
if (!isIdentStart(c)) return error.BadCharacter;
self.skipIdent();
return .{ .tag = .ident, .text = self.src[start..self.pos] };
},
}
}
fn single(self: *Lexer, tag: Tag) Token {
const start = self.pos;
self.pos += 1;
return .{ .tag = tag, .text = self.src[start..self.pos] };
}
fn skipSpace(self: *Lexer) void {
while (self.pos < self.src.len) : (self.pos += 1) {
const c = self.src[self.pos];
// Решётка начинает комментарий, значит для лексера строка кончилась.
if (c == '#') {
self.pos = self.src.len;
return;
}
if (c != ' ' and c != '\t' and c != '\r') return;
}
}
fn skipIdent(self: *Lexer) void {
while (self.pos < self.src.len and isIdentChar(self.src[self.pos])) self.pos += 1;
}
};
fn isIdentStart(c: u8) bool {
return std.ascii.isAlphabetic(c) or c == '_';
}
fn isIdentChar(c: u8) bool {
return std.ascii.isAlphanumeric(c) or c == '_';
}
fn isNumberChar(c: u8) bool {
return std.ascii.isAlphanumeric(c);
}
/// Разбирает число в его битовое представление: `-1` даёт 0xffff...ff.
pub fn parseNumber(text: []const u8) Error!u64 {
var body = text;
var negative = false;
if (body.len > 0 and body[0] == '-') {
negative = true;
body = body[1..];
}
if (body.len == 0) return error.BadNumber;
const magnitude = blk: {
if (body.len > 2 and body[0] == '0' and (body[1] == 'x' or body[1] == 'X')) {
break :blk std.fmt.parseInt(u64, body[2..], 16) catch return error.BadNumber;
}
break :blk std.fmt.parseInt(u64, body, 10) catch return error.BadNumber;
};
if (!negative) return magnitude;
if (magnitude > 1 << 63) return error.BadNumber;
return 0 -% magnitude;
}Четыре решения в этом файле стоит проговорить.
Токен не хранит копию текста, он хранит срез входной строки. Ни одного выделения памяти в лексере нет вовсе, а имя метки, которое дальше попадёт в таблицу, это указатель внутрь исходника. Исходник живёт дольше сборки, поэтому копировать нечего. Заодно текст токена сразу годится для сообщения об ошибке.
Число хранится текстом, а не значением, и тут же проверяется вызовом parseNumber, результат которого выбрасывается. Выглядит расточительно, а на деле удобно: лексер не решает, что означает число, он только гарантирует, что оно разберётся. Ошибка BadNumber всплывает там, где видно строку.
Отрицательное число превращается в биты сразу: parseNumber("-1") даёт 0xffff_ffff_ffff_ffff. Ассемблеру нужны байты, а не знак, поэтому дополнительный код считается один раз, здесь, а дальше по конвейеру идёт голое 64-битное слово. Проверка magnitude > 1 << 63 ловит -9223372036854775809, для которого места нет.
Директива теряет точку: у .pos текст токена будет pos. Мелочь, но она избавляет парсер от сравнения строк с точкой в начале.
Тест на лексер удобно писать через список ожидаемых тегов: видно форму строки целиком, без разбора значений.
test "строки yas разбираются на токены" {
try expectTags("loop: mrmovq (%rdi),%r10 # get *start", &.{
.ident, .colon, .ident, .lparen, .register, .rparen, .comma, .register,
});
try expectTags(" irmovq $8, %r8", &.{ .ident, .dollar, .number, .comma, .register });
try expectTags(" mrmovq -8(%rbp), %rax", &.{
.ident, .number, .lparen, .register, .rparen, .comma, .register,
});
try expectTags(" .quad 0x000d000d000d", &.{ .directive, .number });
try expectTags("# только комментарий", &.{});
try expectTags("", &.{});
}Посмотри на третью строку. Смещение -8 пришло отдельным токеном number, а скобка отдельным lparen. Лексер не знает, что это одна конструкция “смещение и база”, и знать не должен: собирать её будет парсер. Это и есть разделение обязанностей между двумя слоями, из-за которого лексер помещается в полторы сотни строк и не имеет ни одной причины меняться, когда в системе команд появится новая инструкция.
Парсер: токены в строку программы
Парсер отвечает на вопрос “что это за строка”. Ответов ровно три: пустая (она же комментарий, она же строка с одной меткой), директива, инструкция. Плюс необязательная метка в начале, которая может стоять перед любым из трёх.
Главное решение парсера в том, чего он не делает. Он не знает про адреса. Метка в операнде остаётся именем, и превращать имя в число будет второй проход ассемблера. Благодаря этому одна и та же строка разбирается один раз, а не по разу на проход, и парсер остаётся чистой функцией от текста.
//! Строка исходника превращается в метку, директиву или инструкцию.
//!
//! Парсер ничего не знает про адреса: метка в операнде остаётся именем, и
//! разрешает его второй проход ассемблера. Поэтому одна и та же строка
//! разбирается один раз, а не по разу на проход.
const std = @import("std");
const isa = @import("../isa.zig");
const lexer = @import("lexer.zig");
const Icode = isa.Icode;
const Reg = isa.Reg;
const Token = lexer.Token;
/// Операнд, который знает своё значение, или имя метки вместо него.
pub const Value = union(enum) {
number: u64,
label: []const u8,
};
pub const Directive = union(enum) {
/// `.pos ADDR`: дальше собираем с этого адреса.
pos: u64,
/// `.align N`: подтянуть адрес вверх до кратного N.
align_to: u64,
/// `.quad V`: восемь байтов little-endian.
quad: Value,
/// `.byte V`: один байт.
byte: Value,
};
pub const Instruction = struct {
icode: Icode,
ifun: u4,
ra: Reg = .none,
rb: Reg = .none,
val_c: ?Value = null,
};
pub const Statement = union(enum) {
/// Пустая строка, комментарий или строка с одной меткой.
empty,
directive: Directive,
instruction: Instruction,
};
pub const Line = struct {
label: ?[]const u8 = null,
stmt: Statement = .empty,
};
pub const Error = lexer.Error || error{
UnknownMnemonic,
UnknownRegister,
UnknownDirective,
BadOperand,
MissingOperand,
TrailingGarbage,
};
/// Больше токенов в одной строке yas не бывает: самая длинная форма это
/// `label: mrmovq -8(%rbp), %rax`.
const max_tokens = 16;
pub fn parseLine(text: []const u8) Error!Line {
var lx: lexer.Lexer = .init(text);
var buf: [max_tokens]Token = undefined;
var count: usize = 0;
while (true) {
const token = try lx.next();
if (token.tag == .eof) break;
if (count == max_tokens) return error.TrailingGarbage;
buf[count] = token;
count += 1;
}
var p: Parser = .{ .items = buf[0..count] };
var line: Line = .{};
if (p.items.len >= 2 and p.items[0].tag == .ident and p.items[1].tag == .colon) {
line.label = p.items[0].text;
p.at = 2;
}
if (p.at == p.items.len) return line;
line.stmt = if (p.items[p.at].tag == .directive)
.{ .directive = try p.directive() }
else
.{ .instruction = try p.instruction() };
if (p.at != p.items.len) return error.TrailingGarbage;
return line;
}Три детали.
Токены строки складываются в массив на стеке, а не в список в куче. Шестнадцати хватает с запасом: самая длинная законная строка это label: mrmovq -8(%rbp), %rax, в ней девять токенов. Ассемблер выделяет память только для целой сборки (массив строк, таблица меток, образ, буфер листинга) и ни разу в разборе строки.
Метка распознаётся по паре токенов, а не по позиции в строке. Ни отступы, ни выравнивание значения не имеют, важно только сочетание ident и двоеточия в начале.
Хвост проверяется явно. Если после разбора остались лишние токены, это TrailingGarbage, а не молчаливое “ладно”. Строка ret %rax не бывает правильной, и лучше узнать об этом сразу, чем гадать над байтами.
Дальше сам разбор. Parser это тонкая обёртка над массивом токенов с курсором: take берёт следующий, expect берёт и проверяет тег, eat берёт, если тег совпал.
const Parser = struct {
items: []const Token,
at: usize = 0,
fn take(self: *Parser) Error!Token {
if (self.at == self.items.len) return error.MissingOperand;
defer self.at += 1;
return self.items[self.at];
}
fn peek(self: *const Parser) ?Token {
if (self.at == self.items.len) return null;
return self.items[self.at];
}
fn expect(self: *Parser, tag: lexer.Tag) Error!Token {
const token = try self.take();
if (token.tag != tag) return error.BadOperand;
return token;
}
fn eat(self: *Parser, tag: lexer.Tag) bool {
const token = self.peek() orelse return false;
if (token.tag != tag) return false;
self.at += 1;
return true;
}
fn register(self: *Parser) Error!Reg {
const token = try self.expect(.register);
return isa.parseReg(token.text) orelse error.UnknownRegister;
}
/// Число или имя метки: так пишут `.quad`, цель перехода и значение irmovq.
fn value(self: *Parser) Error!Value {
const token = try self.take();
return switch (token.tag) {
.number => .{ .number = try lexer.parseNumber(token.text) },
.ident => .{ .label = token.text },
else => error.BadOperand,
};
}
/// Непосредственное значение: `$8` или метка без доллара, как у yas.
fn immediate(self: *Parser) Error!Value {
_ = self.eat(.dollar);
return self.value();
}
/// Смещение и база: `8(%rbx)`, `(%rbx)`, `-8(%rbp)`.
fn memory(self: *Parser) Error!struct { base: Reg, disp: Value } {
const disp: Value = if (self.eat(.lparen))
.{ .number = 0 }
else blk: {
const d = try self.value();
_ = try self.expect(.lparen);
break :blk d;
};
const base = try self.register();
_ = try self.expect(.rparen);
return .{ .base = base, .disp = disp };
}
fn directive(self: *Parser) Error!Directive {
const name = (try self.take()).text;
if (std.mem.eql(u8, name, "pos")) {
return .{ .pos = try self.constant() };
} else if (std.mem.eql(u8, name, "align")) {
return .{ .align_to = try self.constant() };
} else if (std.mem.eql(u8, name, "quad")) {
return .{ .quad = try self.value() };
} else if (std.mem.eql(u8, name, "byte")) {
return .{ .byte = try self.value() };
}
return error.UnknownDirective;
}
/// Адрес и выравнивание метками не задают: они нужны уже в первом проходе.
fn constant(self: *Parser) Error!u64 {
const token = try self.expect(.number);
return lexer.parseNumber(token.text);
}
fn instruction(self: *Parser) Error!Instruction {
const name = (try self.expect(.ident)).text;
const mnemonic = isa.lookupMnemonic(name) orelse return error.UnknownMnemonic;
var out: Instruction = .{ .icode = mnemonic.icode, .ifun = mnemonic.ifun };
switch (isa.form(mnemonic.icode)) {
.none => {},
.reg_reg => {
out.ra = try self.register();
_ = try self.expect(.comma);
out.rb = try self.register();
},
.imm_reg => {
out.val_c = try self.immediate();
_ = try self.expect(.comma);
out.rb = try self.register();
},
.reg_mem => {
out.ra = try self.register();
_ = try self.expect(.comma);
const mem = try self.memory();
out.rb = mem.base;
out.val_c = mem.disp;
},
.mem_reg => {
const mem = try self.memory();
out.rb = mem.base;
out.val_c = mem.disp;
_ = try self.expect(.comma);
out.ra = try self.register();
},
.reg => out.ra = try self.register(),
.dest => out.val_c = try self.value(),
}
return out;
}
};Функция instruction это вся грамматика операндов, и она читается как таблица. Нашли мнемонику, спросили у isa.form её форму, разобрали ровно то, что форма обещает. Новая инструкция в системе команд не потребует ни строчки в парсере, если её форма одна из семи: достаточно строки в таблице мнемоник. Ты проверишь это в домашнем задании, когда добавишь iaddq.
Две тонкости, которые легко пропустить.
Доллар необязателен. У настоящего yas пишут и irmovq $8, %r8, и irmovq stack, %rsp, потому что метка идёт без доллара. Поэтому immediate глотает доллар, если он есть, и не жалуется, если его нет.
Адрес и выравнивание метками не задаются. Метод constant требует число, а не имя, потому что .pos и .align нужны первому проходу, а таблица меток в этот момент ещё не готова. Написать .pos array нельзя, и это не ограничение реализации, а свойство схемы с двумя проходами.
Разница между mem_reg и reg_mem сводится к порядку разбора, но поля заполняются одинаково: база всегда в rb, смещение всегда в val_c, а второй регистр всегда в ra. Так требует кодирование, и парсеру приходится помнить это за тебя.
Энкодер: поля в байты
Энкодер ты уже писал руками в прошлом уроке. Вот он в виде функции.
/// Инструкция в виде полей, ещё не в виде байтов.
pub const Instr = struct {
icode: Icode,
ifun: u4 = 0,
ra: Reg = .none,
rb: Reg = .none,
val_c: u64 = 0,
};
/// Максимальная длина инструкции: `irmovq V, rB` это байт кода, байт регистров
/// и восемь байтов значения.
pub const max_len = 10;
/// Кодирует инструкцию в `out` и возвращает занятую часть буфера.
pub fn encode(instr: Instr, out: *[max_len]u8) []u8 {
var n: usize = 0;
out[n] = (@as(u8, @intFromEnum(instr.icode)) << 4) | instr.ifun;
n += 1;
if (isa.needRegids(instr.icode)) {
out[n] = (@as(u8, @intFromEnum(instr.ra)) << 4) | @intFromEnum(instr.rb);
n += 1;
}
if (isa.needValC(instr.icode)) {
// Little-endian, как у x86-64: младший байт первым.
std.mem.writeInt(u64, out[n..][0..8], instr.val_c, .little);
n += 8;
}
return out[0..n];
}Пятнадцать строк, и это весь кодировщик системы команд. Возвращается срез буфера, а не длина: вызывающему всё равно нужны байты, а длина у среза и так есть.
Обрати внимание на Instr рядом с parser.Instruction. Похожие структуры, но разные: у парсера val_c это ?Value, то есть “число или имя метки, а может и ничего”, у энкодера это уже голое u64. Граница между ними и есть тот момент, когда метка превращается в адрес. Пока значение не разрешено, кодировать нечего.
В том же файле рядом лежит decode, обратная функция: из байтов обратно в поля. Ассемблеру она не нужна, а симулятору нужна, поэтому разбирать её будем в следующем уроке. То, что обе функции живут в одном файле, не случайность: так видно, что это одна таблица, прочитанная в две стороны, и расходиться им нельзя.
Два прохода
Теперь всё вместе. Первый проход идёт по строкам, спрашивает у парсера, что это за строка, обновляет адрес и заполняет таблицу меток. Второй проход идёт по тем же строкам, кодирует байты, кладёт их в образ памяти и печатает листинг.
//! Ассемблер yas: два прохода по исходнику.
//!
//! Первый проход считает адреса и запоминает метки, второй кодирует байты и
//! печатает листинг. Двух проходов хватает потому, что длина инструкции
//! известна сразу: она зависит только от кода операции, но не от значения
//! операнда. Ассемблер x86-64 так не умеет, там переход бывает короткий и
//! длинный, и проходов нужно больше.
const std = @import("std");
const isa = @import("../isa.zig");
const encoder = @import("encoder.zig");
const lexer = @import("lexer.zig");
const parser = @import("parser.zig");
const Allocator = std.mem.Allocator;
const Value = parser.Value;
pub const Error = parser.Error || error{
DuplicateLabel,
UndefinedLabel,
AddressOutOfRange,
ByteOutOfRange,
} || Allocator.Error;
/// Где именно сломалось. Заполняется только при ошибке.
pub const Diagnostic = struct {
/// Номер строки исходника, считая с единицы.
line: u32 = 0,
/// Кусок исходника, на который стоит посмотреть.
token: []const u8 = "",
};
/// Столбец, в котором у yas начинается разделитель листинга.
/// Семь символов адреса плюс двадцать шестнадцатеричных цифр плюс пробел.
pub const listing_column = 28;
pub const Result = struct {
/// Листинг `.yo`: одна строка на строку исходника.
listing: []u8,
/// Образ памяти целиком, ровно `isa.mem_size` байт.
image: []u8,
pub fn deinit(self: *Result, gpa: Allocator) void {
gpa.free(self.listing);
gpa.free(self.image);
self.* = undefined;
}
};
/// Строка исходника вместе с тем, что о ней узнал первый проход.
const Row = struct {
text: []const u8,
/// Адрес печатается не у всех строк: у пустой и у комментария его нет.
addr: ?u64,
parsed: parser.Line,
};
pub fn assemble(gpa: Allocator, source: []const u8, diag: ?*Diagnostic) Error!Result {
var rows: std.ArrayList(Row) = .empty;
defer rows.deinit(gpa);
var labels: std.StringHashMapUnmanaged(u64) = .empty;
defer labels.deinit(gpa);
var line_no: u32 = 0;
var addr: u64 = 0;
// Первый проход: адреса и метки.
var lines = std.mem.splitScalar(u8, source, '\n');
while (lines.next()) |raw| {
line_no += 1;
const text = std.mem.trimEnd(u8, raw, "\r");
const parsed = parser.parseLine(text) catch |err| return fail(diag, line_no, text, err);
switch (parsed.stmt) {
.directive => |d| switch (d) {
.pos => |p| addr = p,
// Округление вверх без требования степени двойки: `.align 3`
// в yas законен, хотя и бесполезен.
.align_to => |n| if (n != 0) {
addr = ((addr + n - 1) / n) * n;
},
else => {},
},
else => {},
}
if (parsed.label) |name| {
const gop = try labels.getOrPut(gpa, name);
if (gop.found_existing) return fail(diag, line_no, name, error.DuplicateLabel);
gop.value_ptr.* = addr;
}
const has_addr = parsed.label != null or parsed.stmt != .empty;
try rows.append(gpa, .{ .text = text, .addr = if (has_addr) addr else null, .parsed = parsed });
addr += statementSize(parsed.stmt);
}
// Второй проход: байты, образ памяти и листинг.
const image = try gpa.alloc(u8, isa.mem_size);
errdefer gpa.free(image);
@memset(image, 0);
var listing: std.Io.Writer.Allocating = .init(gpa);
errdefer listing.deinit();
var bytes_buf: [encoder.max_len]u8 = undefined;
for (rows.items, 1..) |row, n| {
const at = @as(u32, @intCast(n));
const bytes = emit(&labels, row, &bytes_buf) catch |err| return fail(diag, at, row.text, err);
if (bytes.len > 0) {
const start = row.addr.?;
if (start + bytes.len > isa.mem_size) return fail(diag, at, row.text, error.AddressOutOfRange);
@memcpy(image[@intCast(start)..][0..bytes.len], bytes);
}
writeListingLine(&listing.writer, row, bytes) catch return error.OutOfMemory;
}
return .{ .listing = try listing.toOwnedSlice(), .image = image };
}
fn fail(diag: ?*Diagnostic, line: u32, token: []const u8, err: Error) Error {
if (diag) |d| d.* = .{ .line = line, .token = token };
return err;
}
fn statementSize(stmt: parser.Statement) u64 {
return switch (stmt) {
.empty => 0,
.instruction => |i| isa.length(i.icode),
.directive => |d| switch (d) {
.quad => 8,
.byte => 1,
.pos, .align_to => 0,
},
};
}Порядок внутри первого прохода не случайный, и переставить строки нельзя. Сначала директива двигает адрес, потом объявляется метка, и только потом адрес растёт на размер строки. Проверь на примере:
.align 8
array: .quad 0x000d000d000dЕсли сначала записать метку, а потом выровнять, array получит адрес до выравнивания, то есть невыровненный, и все ссылки на массив уедут. Правильный порядок даёт array значение уже после округления вверх. Такая же логика у .pos: метка в той же строке, что и .pos 0x200, обязана указывать на новый адрес, а не на старый.
Обрати внимание на строку с has_addr. У пустой строки и у строки-комментария адреса нет вовсе, и в листинге у них будет пустое поле слева. Это не украшательство: адрес печатается там, где в памяти что-то происходит, а комментарий в памяти не занимает ничего. У строки с одной меткой адрес есть, хотя байтов нет: метка это точка в памяти, и её адрес хочется видеть.
Первый проход хранит разобранные строки в rows, чтобы не разбирать исходник дважды. Это одно из немногих выделений памяти за всю сборку: массив строк, таблица меток, образ на четыре килобайта и растущий буфер листинга. Таблица меток это std.StringHashMapUnmanaged, где ключом лежит срез исходника, а значением адрес.
Второй проход короче. Для каждой строки он просит байты, копирует их в образ по адресу из первого прохода и печатает строку листинга.
/// Байты одной строки. Пусто у меток, комментариев, `.pos` и `.align`.
fn emit(labels: *const std.StringHashMapUnmanaged(u64), row: Row, buf: *[encoder.max_len]u8) Error![]u8 {
switch (row.parsed.stmt) {
.empty => return buf[0..0],
.directive => |d| switch (d) {
.pos, .align_to => return buf[0..0],
.quad => |v| {
std.mem.writeInt(u64, buf[0..8], try resolve(labels, v), .little);
return buf[0..8];
},
.byte => |v| {
const value = try resolve(labels, v);
if (value > 0xff) return error.ByteOutOfRange;
buf[0] = @intCast(value);
return buf[0..1];
},
},
.instruction => |i| {
const instr: encoder.Instr = .{
.icode = i.icode,
.ifun = i.ifun,
.ra = i.ra,
.rb = i.rb,
.val_c = if (i.val_c) |v| try resolve(labels, v) else 0,
};
return encoder.encode(instr, buf);
},
}
}
fn resolve(labels: *const std.StringHashMapUnmanaged(u64), value: Value) Error!u64 {
return switch (value) {
.number => |n| n,
.label => |name| labels.get(name) orelse error.UndefinedLabel,
};
}Вся разница между двумя проходами умещается в функцию resolve на четыре строки. Число берётся как есть, имя ищется в таблице. Если имени там нет, это UndefinedLabel, и структура Diagnostic сообщит номер строки. Больше нигде во втором проходе метки не упоминаются: .quad со ссылкой на метку, цель перехода и адрес в irmovq идут через одну и ту же функцию.
Заметь, что .quad с меткой это не какой-то особый механизм, а просто восемь байт, в которые лёг адрес. Именно так устроена таблица переходов, к которой мы придём в конце урока.
Виджет: два прохода вживую
Ниже тот же алгоритм в браузере. Слева исходник, справа таблица меток, под ними листинг. Главное здесь кнопки: “первый проход” и “второй проход” показывают работу по ступеням. Сначала голый текст без адресов. После первого прохода появляются адреса и таблица меток, а место будущих байтов занимают точки, ровно столько знаков, сколько там потом будет. После второго на их месте встают настоящие байты. Ссылки вперёд считаются отдельно и подписываются в таблице, а внизу перечислено, какая строка какую метку просит и в какой строке эта метка стоит.
Попробуй три вещи. Возьми sum и следи за строкой jmp test: после первого прохода у неё есть адрес, но нет байтов, после второго в поле цели встаёт 0x087. Удали строку с меткой test, и та же строка ответит “метка не найдена”. Подвинь .pos или измени .align, и увидишь, как за одной директивой едут адреса всех строк ниже, а с ними и все ссылки на метки.
Листинг .yo
Формат листинга держится на одном правиле: одна строка исходника на одну строку вывода. Слева адрес и байты, справа исходная строка как есть, вместе с комментариями и отступами.
fn writeListingLine(w: *std.Io.Writer, row: Row, bytes: []const u8) std.Io.Writer.Error!void {
var width: usize = 0;
if (row.addr) |a| {
var addr_buf: [20]u8 = undefined;
const addr_text = std.fmt.bufPrint(&addr_buf, "0x{x:0>3}: ", .{a}) catch unreachable;
try w.writeAll(addr_text);
width += addr_text.len;
for (bytes) |b| {
try w.print("{x:0>2}", .{b});
width += 2;
}
}
// Исходная строка всегда начинается с одного столбца, чтобы листинг читался
// как исходник с полями слева.
if (width < listing_column) try w.splatByteAll(' ', listing_column - width);
// Хвостовые пробелы исходника в листинг не переносим: иначе в файле повисают
// невидимые символы, а у пустой строки ещё и пробел после разделителя.
const text = std.mem.trimEnd(u8, row.text, " \t");
if (text.len == 0) {
try w.writeAll("|");
} else {
try w.writeAll("| ");
try w.writeAll(text);
}
try w.writeByte('\n');
}Константа listing_column равна 28, и это число берётся из арифметики: семь символов на 0x000: плюс двадцать шестнадцатеричных цифр самой длинной инструкции плюс один пробел перед разделителем. Столбец фиксирован, поэтому разделитель | стоит ровно на одном месте во всех строках, и глаз читает листинг как исходник с полями слева.
Зачем вообще печатать исходник рядом с байтами. Затем, что листинг это инструмент отладки, а не формат хранения. Когда симулятор из следующего урока остановится на адресе 0x087, ты найдёшь этот адрес в листинге и увидишь не только байты, но и строку, которую сам написал, вместе со своим же комментарием.
Образ .hex для Verilog
Второй выход ассемблера это образ памяти, записанный по одному байту в строке.
/// Образ памяти в формате `$readmemh`: ровно `isa.mem_size` строк по байту.
pub fn hexImage(gpa: Allocator, image: []const u8) Allocator.Error![]u8 {
var out: std.Io.Writer.Allocating = .init(gpa);
errdefer out.deinit();
try out.ensureUnusedCapacity(image.len * 3);
for (image) |b| out.writer.print("{x:0>2}\n", .{b}) catch return error.OutOfMemory;
return out.toOwnedSlice();
}Формат выглядит расточительно: четыре тысячи строк по три байта ради четырёх килобайт памяти. Но выбран он не нами. Это ровно то, что читает системная задача $readmemh в Verilog, и процессор из проводов, который мы соберём к концу блока, будет стартовать с этого файла. Один и тот же ассемблер кормит и симулятор на Zig, и железо на Verilog, поэтому байты у них гарантированно одни и те же.
В том же файле рядом с hexImage лежат две функции чтения: loadYo разбирает листинг обратно в образ (ему нужны только строки, начинающиеся с 0x), а loadHex читает образ по байту в строке. Ассемблеру они не нужны, их будет вызывать симулятор из следующего урока, когда ему дадут готовый .yo или .hex вместо исходника.
Проверить всю цепочку удобно одним тестом на четыре формата сразу.
test "листинг и образ памяти сходятся" {
const source =
\\ .pos 0
\\init: irmovq stack, %rsp
\\ halt
\\ .pos 0x100
\\stack:
\\
;
var result = try assemble(testing.allocator, source, null);
defer result.deinit(testing.allocator);
try testing.expectEqualStrings(
\\0x000: | .pos 0
\\0x000: 30f40001000000000000 | init: irmovq stack, %rsp
\\0x00a: 00 | halt
\\0x100: | .pos 0x100
\\0x100: | stack:
\\ |
\\
, result.listing);
try testing.expectEqual(@as(u8, 0x30), result.image[0]);
try testing.expectEqual(@as(u8, 0x00), result.image[0x0a]);
// Листинг читается обратно в тот же самый образ.
const back = try loadYo(testing.allocator, result.listing);
defer testing.allocator.free(back);
try testing.expectEqualSlices(u8, result.image, back);
// И hex-образ тоже.
const hex = try hexImage(testing.allocator, result.image);
defer testing.allocator.free(hex);
const from_hex = try loadHex(testing.allocator, hex);
defer testing.allocator.free(from_hex);
try testing.expectEqualSlices(u8, result.image, from_hex);
}Тест написан как круговой прогон: собрали исходник, прочитали листинг обратно, прочитали hex обратно, и все три образа обязаны совпасть побайтно. Один такой тест закрывает и печать, и разбор, потому что ошибка в любой из четырёх функций разведёт образы.
Обрати внимание на последнюю строку ожидаемого листинга. У пустой строки исходника нет ни адреса, ни байтов, и после разделителя не остаётся ни одного пробела. Хвостовые пробелы обрезаются нарочно: иначе в файле повисают невидимые символы, которые потом путают сравнение листингов.
Подкоманда asm
Осталось соединить всё в программу. У y86 три подкоманды, но сегодня нас интересует одна.
//! Программа `y86`.
//!
//! y86 asm prog.ys [-o prog.yo] [--hex prog.hex] собрать
//! y86 sim prog.yo | prog.hex прогнать и напечатать трассу
//! y86 trace prog.ys собрать и сразу прогнать
//!
//! Без `-o` листинг уходит на стандартный вывод, так что ассемблер можно
//! поставить в конвейер.
const Cli = struct {
gpa: std.mem.Allocator,
io: std.Io,
out: *std.Io.Writer,
err: *std.Io.Writer,
};
fn assembleCommand(cli: Cli, args: []const []const u8) !void {
var listing_path: ?[]const u8 = null;
var hex_path: ?[]const u8 = null;
var i: usize = 3;
while (i < args.len) : (i += 1) {
const target = if (std.mem.eql(u8, args[i], "-o"))
&listing_path
else if (std.mem.eql(u8, args[i], "--hex"))
&hex_path
else {
try cli.err.print("неизвестный ключ: {s}\n", .{args[i]});
return error.BadUsage;
};
i += 1;
if (i == args.len) {
try cli.err.print("у ключа {s} нет значения\n", .{args[i - 1]});
return error.BadUsage;
}
target.* = args[i];
}
var result = try assembleFile(cli, args[2]);
defer result.deinit(cli.gpa);
if (listing_path) |path| {
try std.Io.Dir.cwd().writeFile(cli.io, .{ .sub_path = path, .data = result.listing });
} else {
try cli.out.writeAll(result.listing);
}
if (hex_path) |path| {
const hex = try assembler.hexImage(cli.gpa, result.image);
defer cli.gpa.free(hex);
try std.Io.Dir.cwd().writeFile(cli.io, .{ .sub_path = path, .data = hex });
}
}
fn assembleFile(cli: Cli, path: []const u8) !assembler.Result {
const source = try readSource(cli, path);
defer cli.gpa.free(source);
var diag: assembler.Diagnostic = .{};
return assembler.assemble(cli.gpa, source, &diag) catch |err| {
try cli.err.print("{s}:{d}: {t}\n", .{ path, diag.line, err });
if (diag.token.len > 0) try cli.err.print(" {s}\n", .{diag.token});
return err;
};
}Одна ловушка Zig 0.16 стоит отдельной строки. Стандартный вывод открывается через writerStreaming, а не через writer:
// writerStreaming, а не writer: позиционный писатель начинает с нулевого
// смещения и затирает файл при перенаправлении `y86 asm p.ys > p.yo`.
var out_buf: [4096]u8 = undefined;
var stdout = std.Io.File.stdout().writerStreaming(init.io, &out_buf);Позиционный писатель пишет по смещениям от начала файла. Пока вывод идёт в терминал, разницы нет, но стоит перенаправить его в файл, и записи лягут с нулевого смещения, затирая друг друга. Ошибка неприятна тем, что проявляется только при перенаправлении, то есть ровно тогда, когда её меньше всего ждёшь. И не забывай flush: буферизованный писатель Zig 0.16 без него молча теряет хвост вывода.
Функция assembleFile показывает, зачем нужна Diagnostic. Ошибка Zig это значение, и в нём нет места для номера строки. Структура диагностики принимается по указателю, ассемблер заполняет её перед возвратом ошибки, и вызывающий печатает человеческое сообщение вида programs/sum.ys:14: UndefinedLabel. Тот же приём ты встретишь в разборе аргументов и в парсерах стандартной библиотеки: значение ошибки говорит, что случилось, диагностика говорит, где.
Программы главы 4
Инструмент готов, теперь ему нужна работа. Шесть программ ниже написаны на Y86-64 и собраны этим самым ассемблером. Все листинги сняты командой zig build run -- asm programs/ИМЯ.ys, поэтому адреса и байты в них настоящие, и ты можешь сверить с ними свои.
У всех программ одинаковый пролог: выставить указатель стека, уйти в main, вернуться и остановиться.
.pos 0
init: irmovq stack, %rsp # завести указатель стека
call main # уйти в main
halt # и остановитьсяТак делает и книга. Стек нужен потому, что call кладёт адрес возврата в память, а %rsp после сброса машины равен нулю, и класть было бы некуда. Метка stack объявлена в самом конце, после .pos 0x200, а стек растёт вниз, к программе. Заметь, что это первая в программе ссылка вперёд: имя stack стоит в первой же строке кода, а сама метка появляется последней строкой файла.
Сумма массива
Классический цикл: указатель на начало, счётчик элементов, аккумулятор в %rax.
| # Сумма массива, итеративная версия. Та же программа, что в главе 4 книги:
| # по ней удобно сверять байты, потому что её листинг там напечатан целиком.
|
0x000: | .pos 0
0x000: 30f40002000000000000 | init: irmovq stack, %rsp # завести указатель стека
0x00a: 803800000000000000 | call main # уйти в main
0x013: 00 | halt # и остановиться
|
| # Массив из четырёх элементов. Сумма равна 0xabcdabcdabcd.
0x018: | .align 8
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 # sum(array, 4)
0x055: 90 | ret
|
| # long sum(long *start, long count)
0x056: 30f80800000000000000 | sum: irmovq $8, %r8 # константа 8, размер элемента
0x060: 30f90100000000000000 | irmovq $1, %r9 # константа 1, шаг счётчика
0x06a: 6300 | xorq %rax, %rax # сумма равна нулю
0x06c: 6266 | andq %rsi, %rsi # выставить флаги по count
0x06e: 708700000000000000 | jmp test
0x077: 50a70000000000000000 | loop: mrmovq (%rdi), %r10 # взять *start
0x081: 60a0 | addq %r10, %rax # прибавить к сумме
0x083: 6087 | addq %r8, %rdi # сдвинуть указатель на элемент
0x085: 6196 | subq %r9, %rsi # уменьшить счётчик, флаги
0x087: 747700000000000000 | test: jne loop # пока счётчик не ноль
0x090: 90 | ret
|
| # Стек начинается здесь и растёт вниз.
0x200: | .pos 0x200
0x200: | stack:
|Читай листинг как отчёт обоих проходов сразу. Первая инструкция 30f4 плюс 0002000000000000 это irmovq stack, %rsp: 3 это icode для irmovq, 0 это ifun, f в поле rA означает RNONE (регистра нет), 4 это %rsp, дальше восемь байт значения. Значение 0x200 лежит младшим байтом вперёд, поэтому в строке видно 00 02 и шесть нулей. Метка stack превратилась в число только во втором проходе, а место под него отвели ещё в первом.
Три подробности, из-за которых эта программа устроена так, а не иначе.
Констант в системе команд нет. OPq работает только с регистрами, поэтому размер элемента и шаг счётчика приходится заранее загрузить в %r8 и %r9. Отсюда две лишние инструкции irmovq в прологе функции. Инструкция iaddq из упражнения 4.3 книги нужна ровно затем, чтобы их убрать, и это твоё домашнее задание.
Инструкции сравнения нет тоже. Флаги выставляет любая операция ALU, поэтому andq %rsi, %rsi это идиома “выставить флаги по значению регистра, ничего не изменив”. То же самое делает testq в x86-64, и по той же причине.
Цикл разложен по схеме jump-to-middle из урока про циклы: вход прыгает на проверку в конце, тело лежит выше. Одна копия условия на весь цикл, ценой безусловного перехода на входе. Ты собственными глазами видишь тут выбор, который компилятор делает за тебя в языке высокого уровня.
Между halt по адресу 0x013 и массивом по 0x018 в образе памяти остаётся дыра в четыре нулевых байта: так сработала .align 8. Выравнивание тут не для скорости (память Y86-64 одинаково быстра по любому адресу), а для читаемости адресов: массив начинается с круглого числа, и элементы отличаются на восемь.
Рекурсивная сумма
Та же задача, но функция вызывает саму себя. Смотри на pushq %rbx перед вложенным вызовом.
| # Сумма массива, рекурсивная версия. Тот же ответ, что у sum.ys, но стек
| # вырастает на пять кадров: видно, как call, ret и pushq делят один регистр.
|
0x000: | .pos 0
0x000: 30f40002000000000000 | init: irmovq stack, %rsp
0x00a: 803800000000000000 | call main
0x013: 00 | halt
|
0x018: | .align 8
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 rsum
0x055: 90 | ret
|
| # long rsum(long *start, long count)
0x056: 30f80800000000000000 | rsum: irmovq $8, %r8
0x060: 30f90100000000000000 | irmovq $1, %r9
0x06a: 6300 | xorq %rax, %rax # сумма пустого хвоста равна нулю
0x06c: 6266 | andq %rsi, %rsi # флаги по count
0x06e: 739400000000000000 | je done # count равен нулю, возвращаем ноль
0x077: a03f | pushq %rbx # %rbx обязан пережить вложенный вызов
0x079: 50370000000000000000 | mrmovq (%rdi), %rbx # запомнить *start
0x083: 6087 | addq %r8, %rdi
0x085: 6196 | subq %r9, %rsi
0x087: 805600000000000000 | call rsum # сумма хвоста
0x090: 6030 | addq %rbx, %rax # плюс голова
0x092: b03f | popq %rbx
0x094: 90 | done: ret
|
0x200: | .pos 0x200
0x200: | stack:
|Здесь работает то же соглашение о сохранении регистров, что и в уроке про кадры стека, только записанное руками. Головной элемент нужен после возврата из вложенного вызова, а вложенный вызов портит всё, что захочет. Значит элемент надо положить в регистр, который переживёт вызов, а такой регистр надо сначала сохранить самому. Отсюда пара pushq %rbx и popq %rbx вокруг рекурсии.
Обрати внимание на байты a03f у pushq %rbx. Первый байт a0 это icode и ifun, второй байт это пара регистров: 3 это %rbx, а f это RNONE. Поле rB у pushq не используется, но байт регистров всё равно есть: его наличие определяет icode, а не смысл. Симулятор и процессор из следующих уроков будут проверять, что в неиспользуемом поле стоит именно f, и ругаться кодом INS, если там что-то другое.
Стек здесь вырастает на пять кадров, и результат тот же самый: 0xabcdabcdabcd. Число тактов другое, 65 против 34, и это первая цена рекурсии, которую можно измерить, а не обсуждать.
Сумма модулей: переход против cmov
Задача одна, решения два, и разница между ними станет главной темой конца блока, когда мы посчитаем цену ошибочно предсказанного перехода. Сначала версия с ветвлением.
| # Сумма модулей: ветвление сделано условным переходом.
| # Ответ равен 29, то есть 0x1d.
|
0x000: | .pos 0
0x000: 30f40002000000000000 | init: irmovq stack, %rsp
0x00a: 804800000000000000 | call main
0x013: 00 | halt
|
0x018: | .align 8
0x018: 0500000000000000 | array: .quad 5
0x020: fdffffffffffffff | .quad -3
0x028: 0700000000000000 | .quad 7
0x030: f7ffffffffffffff | .quad -9
0x038: 0100000000000000 | .quad 1
0x040: fcffffffffffffff | .quad -4
|
0x048: 30f71800000000000000 | main: irmovq array, %rdi
0x052: 30f60600000000000000 | irmovq $6, %rsi
0x05c: 806600000000000000 | call abs_sum
0x065: 90 | ret
|
| # long abs_sum(long *start, long count)
0x066: | abs_sum:
0x066: 30f80800000000000000 | irmovq $8, %r8
0x070: 30f90100000000000000 | irmovq $1, %r9
0x07a: 6300 | xorq %rax, %rax
0x07c: 6266 | andq %rsi, %rsi
0x07e: 73b900000000000000 | je asdone
0x087: 50a70000000000000000 | asloop: mrmovq (%rdi), %r10 # x
0x091: 62aa | andq %r10, %r10 # флаги по x
0x093: 75aa00000000000000 | jge aspos # x неотрицательный, брать как есть
0x09c: 30fb0000000000000000 | irmovq $0, %r11
0x0a6: 61ab | subq %r10, %r11 # %r11 равен нулю минус x
0x0a8: 20ba | rrmovq %r11, %r10
0x0aa: 60a0 | aspos: addq %r10, %rax
0x0ac: 6087 | addq %r8, %rdi
0x0ae: 6196 | subq %r9, %rsi
0x0b0: 748700000000000000 | jne asloop
0x0b9: 90 | asdone: ret
|
0x200: | .pos 0x200
0x200: | stack:
|Отрицательные числа в .quad превратились в дополнительный код прямо в листинге: -3 это fdffffffffffffff. Взятие модуля тоже сделано вычитанием из нуля, потому что инструкции отрицания в системе команд нет.
Теперь та же функция на условной пересылке. Пролог программы и массив совпадают байт в байт, а в начале самой функции отличается только цель je, поэтому ниже только тело цикла.
0x087: 50a70000000000000000 | acloop: mrmovq (%rdi), %r10 # x
0x091: 30fb0000000000000000 | irmovq $0, %r11
0x09b: 61ab | subq %r10, %r11 # %r11 равен нулю минус x, флаги по нему
0x09d: 26ba | cmovg %r11, %r10 # минус x положителен, значит x был меньше нуля
0x09f: 60a0 | addq %r10, %rax
0x0a1: 6087 | addq %r8, %rdi
0x0a3: 6196 | subq %r9, %rsi
0x0a5: 748700000000000000 | jne acloop
0x0ae: 90 | acdone: retВнутри цикла не осталось ни одного ветвления, кроме самого цикла. Обе ветки считаются всегда: минус x вычисляется в любом случае, а cmovg решает, забрать его или оставить как было. Байты 26ba стоит разобрать: 2 это icode для семейства cmovXX, 6 это ifun условия “больше”, b это %r11 в поле rA, a это %r10 в поле rB. Ровно тот же байт кода, что у rrmovq, только ifun не нулевой. Это не совпадение, а решение авторов системы команд: условная пересылка это обычная пересылка с условием, и в железе она будет отличаться одним сигналом.
Такты уже сейчас показывают разницу: 64 у версии с переходом против 61 у версии с cmov, при одинаковом ответе 29. На нашем симуляторе, где каждая инструкция стоит один такт, экономия целиком объясняется числом исполненных инструкций. Настоящая разница появится в конце блока, когда мы дойдём до конвейера, и промах предсказания начнёт стоить два такта сверху. Про ту же развилку в x86-64 был урок про флаги и cmov.
Пузырьковая сортировка
Два вложенных цикла, обмен через два rmmovq, и всё это без единой инструкции с константой.
0x048: 30f71800000000000000 | main: irmovq array, %rdi
0x052: 30f60600000000000000 | irmovq $6, %rsi
0x05c: 807a00000000000000 | call bubble
0x065: 30f71800000000000000 | irmovq array, %rdi
0x06f: 50070000000000000000 | mrmovq (%rdi), %rax # наименьший элемент оказался первым
0x079: 90 | ret
|
| # void bubble(long *data, long count)
| # Внешний счётчик i идёт от count минус один до единицы, внутренний j от i до
| # единицы. За каждый проход самое большое число всплывает в конец.
0x07a: 30f80800000000000000 | bubble: irmovq $8, %r8
0x084: 30f90100000000000000 | irmovq $1, %r9
0x08e: 2063 | rrmovq %rsi, %rbx
0x090: 6193 | subq %r9, %rbx # i равен count минус один
0x092: 71ec00000000000000 | jle bdone # сортировать нечего
0x09b: 2072 | bouter: rrmovq %rdi, %rdx # p указывает на начало
0x09d: 2031 | rrmovq %rbx, %rcx # j равен i
0x09f: 50a20000000000000000 | binner: mrmovq (%rdx), %r10 # a равно p[0]
0x0a9: 50b20800000000000000 | mrmovq 8(%rdx), %r11 # b равно p[1]
0x0b3: 20bc | rrmovq %r11, %r12
0x0b5: 61ac | subq %r10, %r12 # сравнить b с a
0x0b7: 75d400000000000000 | jge bnext # порядок уже верный
0x0c0: 40b20000000000000000 | rmmovq %r11, (%rdx) # иначе поменять местами
0x0ca: 40a20800000000000000 | rmmovq %r10, 8(%rdx)
0x0d4: 6082 | bnext: addq %r8, %rdx # p на следующий элемент
0x0d6: 6191 | subq %r9, %rcx # j минус один
0x0d8: 749f00000000000000 | jne binner
0x0e1: 6193 | subq %r9, %rbx # i минус один
0x0e3: 749b00000000000000 | jne bouter
0x0ec: 90 | bdone: retПролог с init опущен, он такой же, как выше. Массив тоже стоит на прежнем месте, но числа в нём другие: 5, 3, 9, 1, 7, 2.
Сравнение делается вычитанием в третий регистр: rrmovq %r11, %r12 и subq %r10, %r12. Портить %r10 или %r11 нельзя, они ещё понадобятся для обмена, а инструкции cmp в системе команд нет. Три инструкции вместо одной, и это честная цена маленькой системы команд.
Смещение 8 в mrmovq 8(%rdx), %r11 и в rmmovq %r10, 8(%rdx) это соседний элемент. Заметь, что в кодировке смещение занимает те же восемь байт, что и любое другое значение: 50b2 плюс 0800000000000000. Экономного короткого смещения, как в x86-64, тут нет, потому что длина инструкции обязана зависеть только от кода операции.
После сортировки в памяти лежит 1, 2, 3, 5, 7, 9, а в %rax оказывается наименьший элемент. Программа тратит 173 такта, больше всех остальных в уроке.
Переключатель через таблицу адресов
Последняя программа самая интересная, потому что решает задачу, которой в системе команд решения нет.
| # Переключатель через таблицу переходов. Прямого перехода по регистру в Y86-64
| # нет, поэтому адрес обработчика кладётся на стек и снимается инструкцией ret.
| # Выбран вариант 2, значит ответ равен 30, то есть 0x1e.
|
0x000: | .pos 0
0x000: 30f40002000000000000 | init: irmovq stack, %rsp
0x00a: 801400000000000000 | call main
0x013: 00 | halt
|
0x014: 30f70200000000000000 | main: irmovq $2, %rdi # номер варианта
0x01e: 802800000000000000 | call dispatch
0x027: 90 | ret
|
| # long dispatch(long x)
0x028: | dispatch:
0x028: 30f80300000000000000 | irmovq $3, %r8
0x032: 2079 | rrmovq %rdi, %r9
0x034: 6189 | subq %r8, %r9 # x минус три
0x036: 758c00000000000000 | jge sdefault # номер слишком большой
0x03f: 6277 | andq %rdi, %rdi
0x041: 728c00000000000000 | jl sdefault # номер отрицательный
0x04a: 207a | rrmovq %rdi, %r10
0x04c: 60aa | addq %r10, %r10 # x умножить на два
0x04e: 60aa | addq %r10, %r10 # x умножить на четыре
0x050: 60aa | addq %r10, %r10 # x умножить на восемь
0x052: 30fb9800000000000000 | irmovq table, %r11
0x05c: 60ba | addq %r11, %r10 # адрес ячейки таблицы
0x05e: 50aa0000000000000000 | mrmovq (%r10), %r10 # адрес обработчика
0x068: a0af | pushq %r10
0x06a: 90 | ret # переход по вычисленному адресу
|
0x06b: 30f00a00000000000000 | scase0: irmovq $10, %rax
0x075: 90 | ret
0x076: 30f01400000000000000 | scase1: irmovq $20, %rax
0x080: 90 | ret
0x081: 30f01e00000000000000 | scase2: irmovq $30, %rax
0x08b: 90 | ret
0x08c: | sdefault:
0x08c: 30f0ffffffffffffffff | irmovq $-1, %rax
0x096: 90 | ret
|
| # Таблица адресов: обычные восьмибайтные слова, только читает их не программа,
| # а сама машина, когда снимает адрес возврата.
0x098: | .align 8
0x098: 6b00000000000000 | table: .quad scase0
0x0a0: 7600000000000000 | .quad scase1
0x0a8: 8100000000000000 | .quad scase2
|
0x200: | .pos 0x200
0x200: | stack:
|Разберём фокус в конце dispatch. В x86-64 переключатель по таблице заканчивается инструкцией jmpq *(%rax): косвенный переход по адресу из памяти, тот самый, который мы читали в уроке про switch. В Y86-64 такой инструкции нет вовсе. Все переходы jXX и call берут восьмибайтную цель прямо из кода инструкции, а значит она известна при сборке и меняться не может.
Но одна инструкция, которая кладёт в PC значение из регистра, в системе команд всё-таки есть, просто называется иначе. Это ret: она снимает слово с вершины стека и ставит его в счётчик команд. Откуда там взялось слово, ret не спрашивает. Отсюда пара:
pushq %r10
ret # переход по вычисленному адресуПоложил вычисленный адрес на стек, снял его инструкцией возврата. Переход по регистру собран из двух инструкций, которых для этого никто не предназначал. Приём древний и живучий: точно так же собирают непрямой переход на архитектурах, где его нет, и точно так же он ломает предсказатель адреса возврата в настоящих процессорах, потому что тот ждёт возврата в вызывающего, а получает прыжок в середину функции. Мы вернёмся к этому в конце блока, когда ret в конвейере будет стоить три пузырька.
Проверка границы сделана в два приёма, потому что беззнакового сравнения одним вычитанием тут не выйдет: subq выставляет знаковые флаги, а jge и jl читают именно их. Сначала отсекаем слишком большой номер, потом отрицательный. Умножение на восемь сделано тремя сложениями регистра с самим собой: инструкции сдвига в Y86-64 нет.
И посмотри на саму таблицу. Три .quad со ссылками на метки, ничем не отличающиеся от массива чисел в sum.ys. Адрес это обычное 64-битное слово, и то, что оно попадёт в счётчик команд, для ассемблера ничего не меняет. Байты 6b, 76 и 81 в младших позициях это адреса scase0, scase1 и scase2, которые второй проход подставил по таблице меток. Программа выбирает вариант 2 и возвращает 30, потратив 23 такта: меньше всех в уроке.
Практика
Задача просит написать сердце урока: два прохода. Таблицы системы команд, энкодер одной инструкции и лексер тебе дадут готовыми, а разбор строки и оба прохода ты напишешь сам. Функция одна, assemble(gpa, source), и возвращает она образ памяти на четыре килобайта: байты программы по своим адресам, нули везде, где программы нет.
Тесты сверяют байты sum.ys из этого урока с эталоном, проверяют переход вперёд и назад, .quad со ссылкой на метку, .align и .pos, все семь форм операндов и три ошибки. Аллокатор тестовый, поэтому утечка памяти это провал наравне с неверным байтом: не забудь defer на таблице меток и errdefer на образе.
Упражнения
Итоги
- Ассемблеру нужны два прохода, потому что ссылка вперёд не разрешается в момент чтения. Первый проход считает адреса и заполняет таблицу меток, второй кодирует байты по готовой таблице.
- Двух проходов хватает только потому, что длина инструкции Y86-64 зависит от кода операции и больше ни от чего. В x86-64 длина перехода зависит от расстояния до цели, и проходов там нужно столько, сколько потребуется до сходимости.
- Лексер, парсер и энкодер разделены по одной причине на каждого. Лексер не знает про инструкции, парсер не знает про адреса, энкодер не знает про метки. Новая инструкция в системе команд меняет только таблицу мнемоник.
- Форма операндов, привязанная к icode, это вся грамматика ассемблера: семь форм на двенадцать инструкций, и
switchпо форме заменяет разбор частных случаев. - Порядок внутри первого прохода задан жёстко: сначала директива двигает адрес, потом объявляется метка, потом адрес растёт на размер строки. Переставишь, и метки после
.alignуедут. - Разница между проходами умещается в четыре строки функции
resolve: число берётся как есть, имя ищется в таблице, отсутствие имени это ошибка с номером строки. - Листинг
.yoдержит одну строку исходника на строку вывода вместе с комментариями, потому что это инструмент отладки: по адресу из трассы находится не только байт, но и твоя собственная строка. - Образ
.hexпо байту в строке нужен не нам, а системной задаче$readmemhв Verilog. Один ассемблер кормит и симулятор на Zig, и процессор на проводах, поэтому байты у них одни и те же. - В Y86-64 нет ни констант в арифметике, ни сравнения, ни отрицания, ни сдвига, ни перехода по регистру. Каждое отсутствие видно в программах главы 4 как лишняя пара инструкций, и это честная цена маленькой системы команд.
- Переход по вычисленному адресу собирается из
pushqиret. Инструкция возврата не спрашивает, откуда на стеке взялось слово, и это единственный способ положить в PC значение из регистра.
Дальше
Байты есть, исполнять их некому. Следующий урок пишет вторую половину y86lab: симулятор уровня инструкций. Шесть этапов из книги станут шестью функциями над одной структурой состояния, каждая инструкция пройдёт их по очереди, а коды Stat остановят машину при halt, при неверной инструкции и при выходе за границу памяти. Там же зафиксируется формат трассы, который потом будет печатать и процессор на Verilog, и по которому мы будем сверять железо с софтом до самого конца блока. И там же проверим твой записанный ответ про pushq %rsp и popq %rsp.
домашка