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

Флаги, переходы и cmov

senior~170 мин

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

Флаги, переходы и cmov

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

Цели урока

Знать четыре флага условия x86-64 и понимать, что они побочный продукт арифметики, а не отдельная операция.
Помнить, какие инструкции флаги ставят, какие только читают и почему lea не ставит их вовсе.
Читать cmp как вычитание без записи результата, а test как побитовое И без записи результата.
Знать всю таблицу условий: одно четырёхбитное поле cc, три семейства инструкций setcc, jcc, cmovcc и синонимы вроде setl против setb.
Отличать знаковое сравнение от беззнакового по мнемонике и понимать, откуда компилятор берёт выбор.
Считать цель условного перехода по байтам: смещение относительно адреса следующей инструкции, короткая форма и длинная.
Видеть за if его форму с переходами и восстанавливать исходный код по ассемблеру.
Понимать, что делает cmov, когда компилятор его выбирает и три причины, по которым он этого не делает.
Написать безопасное чтение по указателю без ветвления и объяснить, почему наивная версия падает.
Измерить цену ошибки предсказания на своём железе и честно интерпретировать полученные числа.

Идея: четыре бита, которые остаются после операции

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

Регистр флагов держит:

Флаг	Имя	Ставится, когда
CF	carry flag	из старшего бита ушёл перенос, это переполнение беззнаковой операции
ZF	zero flag	результат оказался нулём
SF	sign flag	старший бит результата единица, то есть как знаковое число результат отрицателен
OF	overflow flag	результат не помещается в диапазон знакового числа, это переполнение дополнительного кода

Два верхних флага смотрят на одну и ту же операцию с двух разных сторон. CF отвечает на вопрос “вышло ли за границы, если считать числа беззнаковыми”, OF отвечает на вопрос “вышло ли за границы, если считать их знаковыми”. Процессор не знает, какие у тебя числа: он выставляет оба флага всегда, а какой из них читать, решает компилятор по типам из исходного кода. Это прямое продолжение разговора про дополнительный код: одни и те же байты, две интерпретации, и вот тут они расходятся в поведении.

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

export fn addIsZero(x: i64, y: i64) u8 {
    const s = x +% y;
    return @intFromBool(s == 0);
}

export fn maskIsSet(x: u64, mask: u64) u8 {
    return @intFromBool((x & mask) != 0);
}

export fn sameSign(x: i64, y: i64) u8 {
    return @intFromBool((x ^ y) >= 0);
}

Собираем объектный файл под Linux x86-64 и читаем его дизассемблером. Флаг -fomit-frame-pointer убирает из начала каждой функции пару push %rbp и mov %rsp, %rbp, которая нам сейчас только мешает:

zig build-obj flags.zig -O ReleaseSafe -target x86_64-linux -fomit-frame-pointer -femit-bin=flags.o
objdump -d flags.o

Важная деталь про инструменты. Ключ -femit-asm у Zig печатает ассемблер в синтаксисе Intel, а нам нужен AT&T, тот же, что в книге. Поэтому все ассемблерные листинги в этом уроке сняты через objdump -d с объектного файла: он печатает AT&T и заодно показывает байты каждой инструкции, а байты нам сегодня понадобятся.

0000000000000000 <sameSign>:
       0: 48 31 f7                     	xorq	%rsi, %rdi
       3: 0f 99 c0                     	setns	%al
       6: c3                           	retq

0000000000000010 <maskIsSet>:
      10: 48 85 fe                     	testq	%rdi, %rsi
      13: 0f 95 c0                     	setne	%al
      16: c3                           	retq

0000000000000030 <flags.addIsZero>:
      30: 48 01 f7                     	addq	%rsi, %rdi
      33: 0f 94 c0                     	sete	%al
      36: c3                           	retq

Разбери три функции.

В addIsZero нет ни одного сравнения. Инструкция addq сложила x и y, и заодно выставила ZF, потому что она выставляет его всегда. Следующая инструкция просто прочитала этот флаг. Проверка на ноль обошлась в ноль дополнительных инструкций.
В maskIsSet компилятор не стал вычислять x & mask вовсе: результат никому не нужен, нужен только флаг. Для этого есть test, побитовое И, которое выставляет флаги и выбрасывает результат.
В sameSign проверка “знаки совпадают” свелась к xor плюс чтение SF. Логические операции тоже ставят флаги: ZF и SF по результату, а CF и OF они всегда обнуляют.

Итак, флаги ставят: арифметика (add, sub, inc, dec, neg, imul), логика (and, or, xor, not не ставит), сдвиги, и две инструкции, созданные ради флагов, cmp и test. Флаги читают: setcc, jcc, cmovcc и арифметика с переносом (adc, sbb).

А кто их не ставит? Инструкция, которая формально считает адрес, а фактически используется как трёхадресная арифметика.

Почему lea не трогает флаги

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

export fn addNegative(x: i64, y: i64) u8 {
    return @intFromBool(x +% y < 0);
}

0000000000000020 <lea2.addNegative>:
      20: 48 8d 04 37                  	leaq	(%rdi,%rsi), %rax
      24: 48 c1 e8 3f                  	shrq	$0x3f, %rax
      28: c3                           	retq

Сравни с addIsZero выше. Там сложение сделал addq, и знание “результат ноль” пришло бесплатно, вместе с флагом. Здесь компилятор выбрал leaq, потому что она не портит %rdi и %rsi, и тут же остался без флагов: SF не выставлен, читать нечего. Пришлось доставать знак руками, логическим сдвигом на 63 бита вправо, который перегоняет старший бит в младший. Две инструкции вместо двух, но по совсем другой причине: не “сравнили и прочитали флаг”, а “посчитали и вытащили бит”.

Запомни правило: lea считает, но молчит. Всё остальное из арифметики говорит.

cmp и test: посчитать и выбросить

Две инструкции существуют только ради флагов.

cmp S, D вычисляет D - S и выставляет флаги по разности, а саму разность никуда не пишет.
test S, D вычисляет D & S и выставляет флаги по результату, а результат выбрасывает.

В синтаксисе AT&T второй операнд это тот, из которого вычитают, и это регулярный источник путаницы. Строка cmpq %rsi, %rdi означает “посчитай %rdi минус %rsi”, то есть сравни первый аргумент функции со вторым. Читай справа налево, как и все остальные инструкции AT&T.

У test есть две типовые роли. Первая, testq %rax, %rax с одинаковыми операндами: x & x равно x, значит ZF скажет “равно нулю”, а SF скажет “отрицательное”. Это самый дешёвый способ проверить регистр на ноль, дешевле, чем cmpq $0, %rax, потому что кодируется тремя байтами вместо четырёх и не требует непосредственного операнда. Вторая роль, проверка маски: testq %rdi, %rsi отвечает на вопрос “есть ли хоть один общий единичный бит”, то есть ровно на вопрос (x & mask) != 0 из листинга выше.

export fn isZero(x: i64) u8 {
    return @intFromBool(x == 0);
}

export fn ltUnsigned(x: u64, y: u64) u8 {
    return @intFromBool(x < y);
}

export fn ltSigned(x: i64, y: i64) u8 {
    return @intFromBool(x < y);
}

0000000000000010 <setcc.isZero>:
      10: 48 85 ff                     	testq	%rdi, %rdi
      13: 0f 94 c0                     	sete	%al
      16: c3                           	retq

0000000000000020 <setcc.ltUnsigned>:
      20: 48 39 f7                     	cmpq	%rsi, %rdi
      23: 0f 92 c0                     	setb	%al
      26: c3                           	retq

0000000000000030 <setcc.ltSigned>:
      30: 48 39 f7                     	cmpq	%rsi, %rdi
      33: 0f 9c c0                     	setl	%al
      36: c3                           	retq

Смотри внимательно на последние две функции. Исходный код различается ровно одной буквой: u64 против i64. Ассемблерное сравнение у них одно и то же, байт в байт: 48 39 f7. А инструкция, которая читает флаги, разная: setb против setl. Процессор посчитал разность и выставил все четыре флага, а решение “какие флаги считать за меньше” принял компилятор, глядя на тип в исходнике. Одни и те же биты, две интерпретации, и вся разница знакового и беззнакового сравнения живёт вот в этой одной букве мнемоники.

setcc: флаг превращается в байт

Семейство setcc берёт комбинацию флагов и записывает 0 или 1 в однобайтовый регистр. Оно не трогает остальные 56 бит регистра назначения, поэтому компилятор обычно обнуляет весь регистр заранее либо расширяет байт потом. Соберём все десять сравнений разом.

export fn ltS(x: i64, y: i64) u8 {
    return @intFromBool(x < y);
}
export fn leS(x: i64, y: i64) u8 {
    return @intFromBool(x <= y);
}
export fn gtS(x: i64, y: i64) u8 {
    return @intFromBool(x > y);
}
export fn geS(x: i64, y: i64) u8 {
    return @intFromBool(x >= y);
}
export fn ltU(x: u64, y: u64) u8 {
    return @intFromBool(x < y);
}
export fn leU(x: u64, y: u64) u8 {
    return @intFromBool(x <= y);
}
export fn gtU(x: u64, y: u64) u8 {
    return @intFromBool(x > y);
}
export fn geU(x: u64, y: u64) u8 {
    return @intFromBool(x >= y);
}
export fn eq(x: i64, y: i64) u8 {
    return @intFromBool(x == y);
}
export fn ne(x: i64, y: i64) u8 {
    return @intFromBool(x != y);
}

zig build-obj cmpsuite.zig -O ReleaseSafe -target x86_64-linux -fomit-frame-pointer -femit-bin=cmpsuite.o
objdump -d cmpsuite.o | grep -E "^[0-9a-f]+ <|set|cmp"

0000000000000000 <ne>:
       0: 48 39 f7                     	cmpq	%rsi, %rdi
       3: 0f 95 c0                     	setne	%al
0000000000000010 <eq>:
      10: 48 39 f7                     	cmpq	%rsi, %rdi
      13: 0f 94 c0                     	sete	%al
0000000000000020 <geU>:
      20: 48 39 f7                     	cmpq	%rsi, %rdi
      23: 0f 93 c0                     	setae	%al
0000000000000030 <gtU>:
      30: 48 39 f7                     	cmpq	%rsi, %rdi
      33: 0f 97 c0                     	seta	%al
0000000000000040 <leU>:
      40: 48 39 f7                     	cmpq	%rsi, %rdi
      43: 0f 96 c0                     	setbe	%al
0000000000000050 <ltU>:
      50: 48 39 f7                     	cmpq	%rsi, %rdi
      53: 0f 92 c0                     	setb	%al
0000000000000060 <geS>:
      60: 48 39 f7                     	cmpq	%rsi, %rdi
      63: 0f 9d c0                     	setge	%al
0000000000000070 <gtS>:
      70: 48 39 f7                     	cmpq	%rsi, %rdi
      73: 0f 9f c0                     	setg	%al
0000000000000080 <leS>:
      80: 48 39 f7                     	cmpq	%rsi, %rdi
      83: 0f 9e c0                     	setle	%al
0000000000000090 <ltS>:
      90: 48 39 f7                     	cmpq	%rsi, %rdi
      93: 0f 9c c0                     	setl	%al

Десять функций, одна и та же инструкция сравнения, десять разных вторых байтов опкода. Выпиши их столбиком, и структура станет очевидной: все опкоды имеют вид 0F 9x, где x это одна шестнадцатеричная цифра. Эта цифра и есть четырёхбитное поле cc, и она полностью описывает условие.

`cc`	Мнемоника и синонимы	Условие по флагам	Смысл
0	`o`	OF	знаковое переполнение
1	`no`	~OF	нет знакового переполнения
2	`b`, `nae`, `c`	CF	меньше, беззнаковое
3	`ae`, `nb`, `nc`	~CF	не меньше, беззнаковое
4	`e`, `z`	ZF	равно
5	`ne`, `nz`	~ZF	не равно
6	`be`, `na`	CF \| ZF	не больше, беззнаковое
7	`a`, `nbe`	~CF & ~ZF	больше, беззнаковое
8	`s`	SF	отрицательное
9	`ns`	~SF	неотрицательное
a	`p`, `pe`	PF	чётность, для сравнения чисел с плавающей точкой
b	`np`, `po`	~PF	нет чётности
c	`l`, `nge`	SF ^ OF	меньше, знаковое
d	`ge`, `nl`	~(SF ^ OF)	не меньше, знаковое
e	`le`, `ng`	(SF ^ OF) \| ZF	не больше, знаковое
f	`g`, `nle`	~(SF ^ OF) & ~ZF	больше, знаковое

Пары синонимов это не разные инструкции, а разные имена одного опкода. Ассемблер принимает любое, дизассемблер печатает канонический вариант. Например setnge и setl это оба 0F 9C, а setc и setb это оба 0F 92.

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

Беззнаковое “меньше” это cc = 2, то есть просто CF. Логика прямая: если при вычитании x - y из старшего разряда пришлось занимать, значит x было меньше y. Один флаг, одна проверка.

Знаковое “меньше” это cc = c, то есть SF ^ OF. Почему не просто SF? Потому что при вычитании знаковых чисел разность может не поместиться в 64 бита, и тогда знак результата врёт. Возьми x = -9223372036854775808 и y = 1: настоящая разность равна минус девять с лишним квинтиллионов минус один, она не помещается, результат переполняется в положительное число, SF окажется нулём, хотя x меньше y. Ровно в этом случае процессор поднимает OF, и SF ^ OF возвращает правильный ответ. Исключающее ИЛИ здесь читается как “знак результата, исправленный на переполнение”.

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

export fn isNan(x: f64) u8 {
    return @intFromBool(x != x);
}

0000000000000000 <lea2.isNan>:
       0: 66 0f 2e c0                  	ucomisd	%xmm0, %xmm0
       4: 0f 9a c0                     	setp	%al
       7: c3                           	retq

Опкод 0F 9A, то есть cc = a, то есть PF. Сравнение x != x истинно только для NaN, и ucomisd сообщает про несравнимость именно флагом чётности. Подробнее про это в уроке про числа с плавающей точкой и SIMD, здесь достаточно знать, что PF занят.

Оставшиеся два флага тоже доступны через setcc, и Zig даёт к ним прямой доступ встроенными функциями с проверкой переполнения.

export fn addOverflows(x: i64, y: i64) u8 {
    const r = @addWithOverflow(x, y);
    return r[1];
}

0000000000000030 <lea2.addOverflows>:
      30: 50                           	pushq	%rax
      31: 48 01 f7                     	addq	%rsi, %rdi
      34: 0f 90 c0                     	seto	%al
      37: 0f 90 04 24                  	seto	(%rsp)
      3b: 59                           	popq	%rcx
      3c: c3                           	retq

0F 90, то есть cc = 0, то есть OF. Встроенная функция @addWithOverflow возвращает кортеж из суммы и бита переполнения, и этот бит физически и есть флаг OF, снятый инструкцией seto. Всё, чем занимаются проверки переполнения в режиме Debug и ReleaseSafe, это чтение того же флага плюс переход на код паники. Инструкции pushq и popq вокруг это следствие того, что мы просим у функции только один элемент кортежа: компилятор всё равно материализовал второй в стеке. В настоящем коде такого хвоста не будет.

Условный переход и его кодирование

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

Короткая форма: один байт опкода 7x, где x это cc, плюс один байт знакового смещения. Диапазон от минус 128 до плюс 127.
Длинная форма: два байта опкода 0F 8x, плюс четыре байта знакового смещения. Диапазон в два гигабайта в каждую сторону.

Безусловный переход jmp кодируется отдельно: EB плюс байт для короткой формы, E9 плюс четыре байта для длинной.

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

export fn gcd(a: u64, b: u64) u64 {
    var x = a;
    var y = b;
    while (y != 0) {
        const t = x % y;
        x = y;
        y = t;
    }
    return x;
}

zig build-obj jumps.zig -O ReleaseSmall -target x86_64-linux -fomit-frame-pointer -femit-bin=jumps_small.o
objdump -d jumps_small.o

0000000000000000 <gcd>:
       0: 48 89 f2                     	movq	%rsi, %rdx
       3: 48 89 f8                     	movq	%rdi, %rax
       6: 48 85 d2                     	testq	%rdx, %rdx
       9: 74 0d                        	je	0x18 <gcd+0x18>
       b: 48 89 d1                     	movq	%rdx, %rcx
       e: 31 d2                        	xorl	%edx, %edx
      10: 48 f7 f1                     	divq	%rcx
      13: 48 89 c8                     	movq	%rcx, %rax
      16: eb ee                        	jmp	0x6 <gcd+0x6>
      18: c3                           	retq

Посчитаем обе цели руками, не глядя на подсказку дизассемблера.

Переход вперёд на адресе 0x9. Байты 74 0d. Опкод 74 это 7x с cc = 4, то есть je. Смещение 0x0d это 13. Инструкция занимает два байта, значит следующая начинается на 0xb. Цель равна 0xb + 13, то есть 0x18. Дизассемблер печатает 0x18, сходится.

Переход назад на адресе 0x16. Байты eb ee. Опкод eb это безусловный jmp в короткой форме. Смещение 0xee это знаковый байт, старший бит единица, значит число отрицательное: 0xee это 238 без знака, минус 18 со знаком. Следующая инструкция начинается на 0x18. Цель равна 0x18 - 18, то есть 0x18 - 0x12, то есть 0x6. Дизассемблер печатает 0x6, сходится.

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

Теперь длинная форма. Она появляется, когда цель дальше 127 байт.

export fn fillIfPositive(x: i64, out: [*]i64) i64 {
    if (x > 0) {
        inline for (0..40) |k| {
            out[k] = x *% @as(i64, k + 1);
        }
        return 1;
    }
    out[0] = 0;
    return 0;
}

0000000000000000 <fillIfPositive>:
       0: 48 85 ff                     	testq	%rdi, %rdi
       3: 0f 8e 93 01 00 00            	jle	0x19c <fillIfPositive+0x19c>
       9: 48 8d 04 3f                  	leaq	(%rdi,%rdi), %rax
       d: 48 89 46 08                  	movq	%rax, 0x8(%rsi)
      11: 48 8d 04 7f                  	leaq	(%rdi,%rdi,2), %rax
      15: 48 89 46 10                  	movq	%rax, 0x10(%rsi)
...
     190: 48 89 86 38 01 00 00         	movq	%rax, 0x138(%rsi)
     197: 6a 01                        	pushq	$0x1
     199: 58                           	popq	%rax
     19a: eb 04                        	jmp	0x1a0 <fillIfPositive+0x1a0>
     19c: 31 ff                        	xorl	%edi, %edi
     19e: 31 c0                        	xorl	%eax, %eax
     1a0: 48 89 3e                     	movq	%rdi, (%rsi)
     1a3: c3                           	retq

Первый переход на адресе 0x3. Байты 0f 8e 93 01 00 00. Опкод 0f 8e это 0F 8x с cc = e, то есть jle, знаковое “не больше”. Смещение занимает четыре байта и лежит в порядке от младшего к старшему, как всё в x86-64: 93 01 00 00 это 0x00000193, то есть 403. Инструкция занимает шесть байт, следующая начинается на 0x9. Цель равна 0x9 + 0x193, то есть 0x19c. Сходится.

Второй переход на 0x19a короткий, eb 04: следующая инструкция на 0x19c, плюс 4, получаем 0x1a0. Сходится.

Заодно этот листинг показывает, зачем компилятору lea: leaq (%rdi,%rdi), %rax это умножение на два, leaq (%rdi,%rdi,2), %rax это умножение на три, обе за одну инструкцию и обе без чтения памяти. Мы это разбирали в уроке про арифметику.

if в форме с переходами

Книга предлагает удобный способ читать ассемблер условия: переписать исходник в форму, где остались только прямолинейные куски и переходы между ними. В C для этого есть goto, и получается запись, один к одному ложащаяся на машинный код. В Zig оператора goto нет вовсе, и это осознанное решение языка: любой поток управления в Zig выражается блоками, метками блоков и break. Поэтому промежуточную форму мы напишем на C, а потом убедимся, что она и Zig-версия дают один и тот же машинный код.

Начнём с Zig. Функция считает модуль разности и попутно ведёт два счётчика, сколько раз сработала каждая ветвь.

var lt_cnt: u64 = 0;
var ge_cnt: u64 = 0;

export fn absdiffSe(x: i64, y: i64) i64 {
    if (x < y) {
        lt_cnt +%= 1;
        return y -% x;
    }
    ge_cnt +%= 1;
    return x -% y;
}

0000000000000060 <cmov.absdiffSe>:
      60: 48 89 f8                     	movq	%rdi, %rax
      63: 48 29 f0                     	subq	%rsi, %rax
      66: 7d 0f                        	jge	0x77 <cmov.absdiffSe+0x17>
      68: 48 83 05 00 00 00 00 01      	addq	$0x1, (%rip)            # 0x70
      70: 48 29 fe                     	subq	%rdi, %rsi
      73: 48 89 f0                     	movq	%rsi, %rax
      76: c3                           	retq
      77: 48 83 05 00 00 00 00 01      	addq	$0x1, (%rip)            # 0x7f
      7f: c3                           	retq

Теперь та же функция на C, где условие развёрнуто в переход, а тела ветвей выписаны подряд:

long lt_cnt = 0;
long ge_cnt = 0;

long absdiff_goto(long x, long y) {
    long result;
    if (x >= y) goto x_ge_y;
    lt_cnt++;
    result = y - x;
    return result;
x_ge_y:
    ge_cnt++;
    result = x - y;
    return result;
}

zig cc -c -target x86_64-linux -O2 -fomit-frame-pointer goto_form.c -o goto_form.o
objdump -dr goto_form.o

0000000000000000 <absdiff_goto>:
       0: 48 89 f8                     	movq	%rdi, %rax
       3: 48 29 f0                     	subq	%rsi, %rax
       6: 7d 0f                        	jge	0x17 <absdiff_goto+0x17>
       8: 48 83 05 00 00 00 00 01      	addq	$0x1, (%rip)            # 0x10
		000000000000000b:  R_X86_64_PC32	lt_cnt-0x5
      10: 48 29 fe                     	subq	%rdi, %rsi
      13: 48 89 f0                     	movq	%rsi, %rax
      16: c3                           	retq
      17: 48 83 05 00 00 00 00 01      	addq	$0x1, (%rip)            # 0x1f
		000000000000001a:  R_X86_64_PC32	ge_cnt-0x5
      1f: c3                           	retq

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

Условие в исходнике было x < y, а в машинном коде стоит jge, противоположное. Это стандартный приём: тело первой ветви оставляют сразу после проверки, а переход делают по отрицанию условия, чтобы прыгать только в редком случае. Прямолинейный код быстрее, а какая ветвь окажется прямолинейной, компилятор решает по своим оценкам.
Вычитание subq %rsi, %rax делает двойную работу: считает x - y в %rax на случай второй ветви и выставляет флаги для проверки. Отдельного cmp нет, потому что разность всё равно нужна.
В первой ветви разность считается заново, subq %rdi, %rsi даёт y - x, и результат переезжает в %rax.
Строка addq $0x1, (%rip) это увеличение глобальной переменной, адресуемой относительно счётчика команд. В объектном файле на месте смещения стоят нули, а рядом дизассемблер печатает запись перемещения R_X86_64_PC32 lt_cnt-0x5. Компоновщик подставит настоящее смещение, когда узнает, где лежит переменная. В Zig-варианте перемещения точно такие же, я убрал их из листинга, чтобы не мешали сравнивать.

Ещё одна деталь про адресацию (%rip). Смещение считается от адреса следующей инструкции, ровно как у переходов, и -0x5 в записи перемещения это поправка на пять байт хвоста инструкции после поля смещения. Тот же принцип, что мы считали руками выше, только применённый к данным, а не к коду.

Реверс: восстанови исходник по ассемблеру

Читать компилятор мы учимся не ради красоты, а чтобы уметь ответить на вопрос “что здесь вообще происходит”, когда исходника под рукой нет. Вот функция, собранная из Zig в режиме ReleaseFast. Три аргумента типа i64 пришли в %rdi, %rsi и %rdx, результат уходит в %rax.

0000000000000020 <mystery.mystery>:
      20: 48 89 f8                     	movq	%rdi, %rax
      23: 48 29 d0                     	subq	%rdx, %rax
      26: 7d 0c                        	jge	0x34 <mystery.mystery+0x14>
      28: 48 39 fe                     	cmpq	%rdi, %rsi
      2b: 7d 19                        	jge	0x46 <mystery.mystery+0x26>
      2d: 48 29 d6                     	subq	%rdx, %rsi
      30: 48 89 f0                     	movq	%rsi, %rax
      33: c3                           	retq
      34: 48 39 d6                     	cmpq	%rdx, %rsi
      37: 7e 07                        	jle	0x40 <mystery.mystery+0x20>
      39: 48 29 fe                     	subq	%rdi, %rsi
      3c: 48 89 f0                     	movq	%rsi, %rax
      3f: c3                           	retq
      40: 48 29 fa                     	subq	%rdi, %rdx
      43: 48 89 d0                     	movq	%rdx, %rax
      46: c3                           	retq

Прежде чем читать дальше, попробуй сам. Подсказка: обрати внимание, что на 0x46 стоит retq без единой инструкции перед ним, и на него кто-то прыгает.

Разбор по шагам, назовём аргументы x, y, z.

movq %rdi, %rax плюс subq %rdx, %rax: в %rax теперь x - z, и флаги выставлены по этой разности. Значение в %rax пока живёт как кандидат в результат.
jge 0x34: переход по знаковому “не меньше”, то есть если x - z >= 0. Значит на прямолинейном пути мы оказываемся при x < z. Это и есть внешнее условие исходника.
Ветвь x < z начинается на 0x28 с cmpq %rdi, %rsi, то есть y - x, и jge 0x46 уходит при y >= x. Прыгаем на 0x46, где стоит голый retq. Возвращается то, что лежит в %rax, а там с самого начала лежит x - z. Вот зачем компилятор посчитал эту разность заранее: она пригодилась как результат целой ветви, и переход на общий ret обошёлся в два байта.
Если же y < x, выполняется subq %rdx, %rsi, то есть y - z, и результат переезжает в %rax.
Ветвь x >= z начинается на 0x34 с cmpq %rdx, %rsi, то есть y - z, и jle 0x40 уходит при y <= z. Там считается z - x.
Иначе, при y > z, считается y - x.

Собираем обратно:

export fn mystery(x: i64, y: i64, z: i64) i64 {
    if (x < z) {
        if (y < x) return y -% z;
        return x -% z;
    }
    if (y > z) return y -% x;
    return z -% x;
}

Два наблюдения на будущее.

Первое: компилятор охотно считает значение до того, как узнает, понадобится ли оно. Разность x - z посчитана в первой же инструкции, ещё до всех проверок, потому что она всё равно нужна для флагов, а раз посчитана, то пусть заодно и полежит как результат. Это та же идея, из которой дальше вырастет условная передача данных.

Второе: subq в этом листинге выступает в двух ролях одновременно, как арифметика и как сравнение, а честный cmpq появляется только там, где разность сама по себе не нужна. Увидев cmp, знай: результат разности выбрасывается. Увидев sub перед переходом, ищи, где потом используется его результат.

cmov: выбрать значение вместо пути

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

Отсюда идея: если обе ветви дёшевы, можно посчитать обе и выбрать результат, не трогая счётчик команд вовсе. Семейство cmovcc делает ровно это: копирует источник в приёмник, если условие выполнено, и не делает ничего, если не выполнено. Опкод 0F 4x, где x это то же самое поле cc из таблицы выше.

export fn maxOf(x: i64, y: i64) i64 {
    return if (x > y) x else y;
}

export fn clampTo(x: i64, lo: i64, hi: i64) i64 {
    if (x < lo) return lo;
    if (x > hi) return hi;
    return x;
}

0000000000000000 <maxOf>:
       0: 48 89 f0                     	movq	%rsi, %rax
       3: 48 39 f7                     	cmpq	%rsi, %rdi
       6: 48 0f 4f c7                  	cmovgq	%rdi, %rax
       a: c3                           	retq

0000000000000000 <mystery.clampTo>:
       0: 48 89 d0                     	movq	%rdx, %rax
       3: 48 39 d7                     	cmpq	%rdx, %rdi
       6: 48 0f 4c c7                  	cmovlq	%rdi, %rax
       a: 48 39 f7                     	cmpq	%rsi, %rdi
       d: 48 0f 4c c6                  	cmovlq	%rsi, %rax
      11: c3                           	retq

Функция maxOf уложилась в три инструкции без единого перехода. Схема стандартная: сначала в приёмник кладут значение “ветви по умолчанию”, потом сравнивают, потом условно перезаписывают. Опкод 0F 4F это cc = f, то есть g, знаковое “больше”, ровно как в исходном x > y.

clampTo интереснее: там два cmov подряд, и порядок у них не тот, что в исходнике. Компилятор начал с верхней границы (0F 4C это cc = c, знаковое “меньше”: если x < hi, берём x), а потом наложил нижнюю. Порядок именно такой, потому что нижняя граница должна победить: при lo > hi результатом будет lo. Перевернёшь два cmov местами, и семантика поменяется. Это типичная ловушка при чтении цепочек условной передачи данных: у cmov нет своих ветвей, поэтому вся логика сидит в порядке инструкций.

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

export fn absdiff(x: i64, y: i64) i64 {
    return if (x < y) y -% x else x -% y;
}

0000000000000036 <absdiff>:
      36: 48 89 f8                     	movq	%rdi, %rax
      39: 48 29 f0                     	subq	%rsi, %rax
      3c: 48 29 fe                     	subq	%rdi, %rsi
      3f: 48 0f 4d c6                  	cmovgeq	%rsi, %rax
      43: c3                           	retq

Вот она, главная особенность условной передачи данных: обе ветви посчитаны. Первое вычитание даёт x - y, второе даёт y - x, и только потом одно из двух значений выбирается. Флаги при этом выставлены вторым вычитанием, поэтому cmovge читается как “если y - x неотрицательно, то есть если y >= x, возьми y - x”. Никакого перехода, никакого предсказания, четыре инструкции всегда.

Сравни с версией absdiffSe из предыдущего раздела, где были счётчики. Там компилятор оставил переход. Почему, разберём прямо сейчас.

Три причины, по которым cmov не появится

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

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

      60: 48 89 f8                     	movq	%rdi, %rax
      63: 48 29 f0                     	subq	%rsi, %rax
      66: 7d 0f                        	jge	0x77
      68: 48 83 05 00 00 00 00 01      	addq	$0x1, (%rip)

Это absdiffSe, и переход в ней остался именно потому, что каждая ветвь увеличивает свой счётчик. С cmov увеличились бы оба.

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

export fn creadNaive(xp: ?*const i64) i64 {
    return if (xp) |p| p.* else 0;
}

0000000000000020 <creadNaive>:
      20: 48 85 ff                     	testq	%rdi, %rdi
      23: 74 04                        	je	0x29 <creadNaive+0x9>
      25: 48 8b 07                     	movq	(%rdi), %rax
      28: c3                           	retq
      29: 31 c0                        	xorl	%eax, %eax
      2b: c3                           	retq

Переход остался, и это правильное поведение компилятора. Мы к этому случаю ещё вернёмся, он стоит отдельного разбора.

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

export fn safeDiv(x: i64, y: i64) i64 {
    return if (y == 0) 0 else @divTrunc(x, y);
}

0000000000000030 <safeDiv>:
      30: 48 85 f6                     	testq	%rsi, %rsi
      33: 74 15                        	je	0x4a <safeDiv+0x1a>
      35: 48 89 f8                     	movq	%rdi, %rax
      38: 48 09 f0                     	orq	%rsi, %rax
      3b: 48 c1 e8 20                  	shrq	$0x20, %rax
      3f: 74 0c                        	je	0x4d <safeDiv+0x1d>
      41: 48 89 f8                     	movq	%rdi, %rax
      44: 48 99                        	cqto
      46: 48 f7 fe                     	idivq	%rsi
      49: c3                           	retq
      4a: 31 c0                        	xorl	%eax, %eax
      4c: c3                           	retq
      4d: 89 f8                        	movl	%edi, %eax
      4f: 31 d2                        	xorl	%edx, %edx
      51: f7 f6                        	divl	%esi
      53: c3                           	retq

Здесь переход обязателен, потому что деление на ноль это не “неправильный ответ”, а исключение процессора. Но обрати внимание на бонус: компилятор добавил вторую проверку. Инструкции с orq и shrq спрашивают “помещаются ли оба числа в 32 бита”, и если да, уходят на divl, деление половинной ширины, которое на большинстве процессоров заметно быстрее полного. Три перехода вместо одного, и все три ради того, чтобы редко выполнять дорогую инструкцию.

Есть и четвёртая причина, обратная по знаку. Иногда компилятор убирает ветвь там, где ты её писал руками и не просил. Проверим на цикле.

export fn countAbove(xs: [*]const i64, n: usize, t: i64) usize {
    var c: usize = 0;
    var i: usize = 0;
    while (i < n) : (i += 1) {
        if (xs[i] > t) c +%= 1;
    }
    return c;
}

0000000000000019 <countAbove>:
      19: 31 c0                        	xorl	%eax, %eax
      1b: 31 c9                        	xorl	%ecx, %ecx
      1d: 48 39 ce                     	cmpq	%rcx, %rsi
      20: 74 13                        	je	0x35 <countAbove+0x1c>
      22: 45 31 c0                     	xorl	%r8d, %r8d
      25: 48 39 14 cf                  	cmpq	%rdx, (%rdi,%rcx,8)
      29: 41 0f 9f c0                  	setg	%r8b
      2d: 4c 01 c0                     	addq	%r8, %rax
      30: 48 ff c1                     	incq	%rcx
      33: eb e8                        	jmp	0x1d <countAbove+0x4>
      35: c3                           	retq

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

Как процессор угадывает и сколько стоит промах

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

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

Виджет ниже прогоняет цикл if (v >= порог) sum += v по массиву из 64 элементов и показывает состояние счётчика на каждом шаге. Покрути две вещи. Сначала нажми “проход” на перемешанном массиве и посмотри на красные столбики: это промахи, и их примерно половина. Потом нажми “отсортировать” и повтори: массив тот же, порог тот же, сумма та же, а промахов остаётся два или три, все около точки, где значения переходят через порог. Потом подвигай порог к краям диапазона и увидь, что даже на случайном массиве промахов почти нет: когда ветвь почти всегда берётся или почти никогда, угадывать легко.

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

Измерение: тринадцать раз на ровном месте

Теперь то же самое, но на настоящем железе. Программа складывает элементы массива, которые не меньше порога, в двух формах и на двух порядках данных: перемешанном и отсортированном. Массив один и тот же, элементы одни и те же, сумма одна и та же. Разница только в порядке.

const std = @import("std");

const n = 1 << 22;
const threshold: u32 = 500;
const rounds = 7;

/// Ветвь сохранена: подсказка .unlikely говорит оптимизатору, что условие
/// редкое, и на x86-64 он оставляет настоящий условный переход.
noinline fn sumBranch(xs: []const u32, t: u32) u64 {
    var sum: u64 = 0;
    for (xs) |v| {
        if (v >= t) {
            @branchHint(.unlikely);
            sum +%= v;
        }
    }
    return sum;
}

/// Тот же смысл, но выбор значения вместо выбора пути.
noinline fn sumSelect(xs: []const u32, t: u32) u64 {
    var sum: u64 = 0;
    for (xs) |v| sum +%= if (v >= t) v else 0;
    return sum;
}

/// Лучшее из rounds прогонов: минимум режет шум планировщика.
fn best(io: std.Io, f: *const fn ([]const u32, u32) u64, xs: []const u32, sink: *u64) i96 {
    var lowest: i96 = std.math.maxInt(i96);
    var round: usize = 0;
    while (round < rounds) : (round += 1) {
        const started = std.Io.Clock.awake.now(io);
        sink.* +%= f(xs, threshold);
        const took = started.durationTo(std.Io.Clock.awake.now(io)).nanoseconds;
        if (took < lowest) lowest = took;
    }
    return lowest;
}

pub fn main(init: std.process.Init) !void {
    var buf: [512]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &buf);
    const out = &w.interface;

    var gpa: std.heap.DebugAllocator(.{}) = .init;
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    const random_data = try allocator.alloc(u32, n);
    defer allocator.free(random_data);
    const sorted_data = try allocator.alloc(u32, n);
    defer allocator.free(sorted_data);

    var prng = std.Random.DefaultPrng.init(0x5eed);
    const rand = prng.random();
    for (random_data) |*slot| slot.* = rand.uintLessThan(u32, 1000);
    @memcpy(sorted_data, random_data);
    std.mem.sort(u32, sorted_data, {}, std.sort.asc(u32));

    var sink: u64 = 0;
    const br = best(init.io, &sumBranch, random_data, &sink);
    const bs = best(init.io, &sumBranch, sorted_data, &sink);
    const sr = best(init.io, &sumSelect, random_data, &sink);
    const ss = best(init.io, &sumSelect, sorted_data, &sink);

    try out.print("элементов: {d}, порог: {d}\n", .{ n, threshold });
    try out.print("ветка   , случайный : {d:>8.2} мс\n", .{@as(f64, @floatFromInt(br)) / 1e6});
    try out.print("ветка   , сортирован: {d:>8.2} мс\n", .{@as(f64, @floatFromInt(bs)) / 1e6});
    try out.print("без ветки, случайный : {d:>8.2} мс\n", .{@as(f64, @floatFromInt(sr)) / 1e6});
    try out.print("без ветки, сортирован: {d:>8.2} мс\n", .{@as(f64, @floatFromInt(ss)) / 1e6});
    try out.print("контрольная сумма: {d}\n", .{sink});
    try out.flush();
}

Три места в этой программе стоит объяснить.

Функции помечены noinline, иначе оптимизатор встроит их в main, увидит, что данные известны, и посчитает всё заранее. Обе накапливают результат в общий sink, который печатается в конце: без этого компилятор имеет право выбросить весь цикл как вычисление никому не нужного значения.

Подсказка @branchHint(.unlikely) внутри if это способ сказать оптимизатору, что условие срабатывает редко. Без неё компилятор сам сворачивает этот if в условную передачу данных, и обе функции превращаются в одну. Это не догадка, это видно по таблице символов. Соберём обе версии без подсказки:

$ zig build-obj nohint.zig -O ReleaseFast -target x86_64-linux -fomit-frame-pointer -femit-bin=nohint.o
$ nm nohint.o
0000000000000000 t nohint.sumBranch
0000000000000000 T sumBranch
0000000000000000 T sumSelect

Тело в объектнике осталось одно, и на него смотрят оба имени по адресу ноль. Компилятор превратил if в выбор значения, увидел, что получившийся код байт в байт совпадает со второй функцией, и склеил их. С подсказкой такого не происходит: функции расходятся, и sumBranch получает настоящие jae и jb в теле цикла.

Времени в Zig 0.16 нет в старом виде: std.time.Timer из прежних версий убран, часы стали частью явно передаваемого std.Io. Отсюда std.Io.Clock.awake.now(io) и разность двух отметок через durationTo. Часы awake монотонны, то есть не прыгают назад при переводе системного времени.

Сначала снимем числа на своей машине, ноутбуке на Apple Silicon:

$ zig build-exe bench.zig -O ReleaseFast -femit-bin=bench-native
$ ./bench-native
элементов: 4194304, порог: 500
ветка   , случайный :     2.02 мс
ветка   , сортирован:     2.11 мс
без ветки, случайный :     1.05 мс
без ветки, сортирован:     1.09 мс
контрольная сумма: 43976364684

Порядок данных не изменил ничего. Это не потому, что предсказатель на этом процессоре идеален, а потому, что ветви в машинном коде нет вовсе. На aarch64 компилятор проигнорировал подсказку и всё равно свернул if в csel, аналог cmov для этой архитектуры:

$ objdump -d bench-native --disassemble-symbols=_bench.sumBranch
...
10003d5c8: b85f016d    	ldur	w13, [x11, #-0x10]
10003d5cc: 6b0201bf    	cmp	w13, w2
10003d5d0: 8b0d010d    	add	x13, x8, x13
10003d5d4: 9a8d3108    	csel	x8, x8, x13, lo

Загрузка, сравнение, безусловное сложение, условный выбор. Ни одного перехода в теле цикла. Полезный урок сам по себе: подсказка это подсказка, и разные бэкенды слушают её по-разному.

Теперь то же самое под x86-64. Собираем кросс-компиляцией и запускаем в контейнере:

$ zig build-exe bench.zig -O ReleaseFast -target x86_64-linux -femit-bin=bench-amd64
$ docker run --rm --platform linux/amd64 -v "$PWD":/work -w /work \
    ghcr.io/bondiano/runner-zig:dev-amd64 ./bench-amd64
элементов: 4194304, порог: 500
ветка   , случайный :    10.98 мс
ветка   , сортирован:     0.86 мс
без ветки, случайный :     0.83 мс
без ветки, сортирован:     0.84 мс
контрольная сумма: 43976364684

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

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

Теперь честно про эти числа. Мой контейнер linux/amd64 работает на процессоре Apple Silicon через эмуляцию, а не на настоящем x86-64. Эмулятор транслирует машинный код, и цена условного перехода в трансляции выше, чем на живом железе, поэтому тринадцатикратный разрыв это верхняя оценка, а не типичная. На настоящем процессоре x86-64 для этого цикла обычно получается разница от трёх до шести раз: базовая работа на элемент там дешевле, а штраф за промах те же полтора десятка тактов. Что не меняется от эмуляции, так это качественная картина: сортированный массив против перемешанного даёт кратную разницу, а безветвевая форма её убирает. Если у тебя есть доступ к машине с настоящим x86-64, прогони и сравни, это хорошее упражнение на аккуратность в измерениях.

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

Безопасное чтение по указателю без ветвления

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

export fn creadNaive(xp: ?*const i64) i64 {
    return if (xp) |p| p.* else 0;
}

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

	.text
	.globl	cread_broken
cread_broken:
	movq	(%rdi), %rax
	xorl	%edx, %edx
	testq	%rdi, %rdi
	cmoveq	%rdx, %rax
	ret

$ zig cc -c -target x86_64-linux cread_broken.s -o cread_broken.o
$ objdump -d cread_broken.o

0000000000000000 <cread_broken>:
       0: 48 8b 07                     	movq	(%rdi), %rax
       3: 31 d2                        	xorl	%edx, %edx
       5: 48 85 ff                     	testq	%rdi, %rdi
       8: 48 0f 44 c2                  	cmoveq	%rdx, %rax
       c: c3                           	retq

Собирается, четыре инструкции, переходов нет, красиво. И неправильно. Первая же инструкция читает по адресу из %rdi, ничего о нём не зная. Если там ноль, программа получит нарушение доступа к памяти и умрёт, не дойдя до cmov. Условная передача данных выбирает результат уже после того, как обе ветви посчитаны, и “посчитать” тут означает “сходить в память”. Никакое условие после чтения не спасёт от чтения.

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

$ objdump -dr cmov.o

0000000000000010 <creadCmov>:
      10: 48 85 ff                     	testq	%rdi, %rdi
      13: b8 00 00 00 00               	movl	$0x0, %eax
		0000000000000014:  R_X86_64_32	.rodata.cst8
      18: 48 0f 45 c7                  	cmovneq	%rdi, %rax
      1c: 48 8b 00                     	movq	(%rax), %rax
      1f: c3                           	retq

Пять инструкций, ни одного перехода, и обращение к памяти ровно одно. Разбери порядок.

testq %rdi, %rdi спрашивает, пустой ли указатель, и выставляет ZF.
movl $0x0, %eax кладёт в регистр адрес нашей нулевой ячейки. Нули в байтах инструкции это не значение ноль, а заглушка: строка ниже, R_X86_64_32 .rodata.cst8, говорит компоновщику вписать сюда адрес постоянной из секции неизменяемых данных. В несвязанном объектнике настоящего адреса ещё не существует.
cmovneq %rdi, %rax перезаписывает адрес исходным указателем, если тот не пустой. После этой инструкции в %rax лежит гарантированно годный адрес.
movq (%rax), %rax читает, и это чтение всегда законно.

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

Шаг проекта: zt учится ветвиться

После прошлого шага zt disasm читает прямолинейный код: пересылки, адреса, арифметику. Но в прямолинейном коде нет ни одного if, а первая же развилка ломает ему разбор. Возьми gcd из раздела про кодирование переходов, тот же объектник jumps_small.o, и посмотри, что печатал zt после урока 11:

$ ./zig-out/bin/zt disasm jumps_small.o
       0: 48 89 f2                     	movq	%rsi, %rdx
       3: 48 89 f8                     	movq	%rdi, %rax
       6: 48                           	(bad)
       7: 85                           	(bad)
       8: d2 74 0d 48                  	shlb	%cl, 0x48(%rbp,%rcx)
       c: 89 d1                        	movl	%edx, %ecx
       e: 31 d2                        	xorl	%edx, %edx
      10: 48 f7 f1                     	divq	%rcx
      13: 48 89 c8                     	movq	%rcx, %rax
      16: eb                           	(bad)
      17: ee                           	(bad)
      18: c3                           	retq

Хуже всего здесь не четыре (bad), а строка 8. Декодер не узнал 48 85 (это testq) и пошёл дальше по одному байту. Хвост testq, весь je и префикс следующей инструкции сложились в правдоподобный shlb с адресом в памяти, которого в программе нет, а оставшийся без своего REX movq %rdx, %rcx превратился в movl. Длина инструкции x86-64 известна только тому, кто её понял, поэтому одна пропущенная инструкция может утянуть за собой соседей. Сегодня декодер узнает всё, что было в уроке: test, шестнадцать условий в трёх семействах jcc, setcc, cmovcc, безусловный jmp и заодно префикс замены сегмента.

Цель перехода считает курсор

Разбирая gcd руками, ты складывал смещение с адресом следующей инструкции. В курсоре этот адрес уже есть: address это начало инструкции, а pos к концу разбора равен её длине. Новый метод в src/x86/cursor.zig:

    /// Абсолютный адрес цели перехода. В машинном коде записано смещение
    /// от конца инструкции, поэтому складывать надо с позицией курсора,
    /// а не с адресом её начала.
    pub fn relativeTarget(cursor: Cursor, displacement: i64) u64 {
        const end: i64 = @bitCast(cursor.address + cursor.pos);
        return @bitCast(end + displacement);
    }

Смещение у перехода всегда последнее поле инструкции. Значит, в момент, когда оно прочитано, pos уже указывает за конец, и цель можно посчитать сразу. У адресации относительно RIP в прошлом уроке было иначе: после смещения там может идти непосредственное значение, поэтому понадобился fixupRip, который правит адрес после разбора. Здесь поправка не нужна.

Два @bitCast нужны ради перехода назад. Смещение знаковое, адрес беззнаковый; складывать надо со знаком, а результат снова читать как адрес. Для eb ee на 0x16 получается 0x18 + (-18), то есть 0x6, ровно как в ручном расчёте.

Одна таблица условий на три семейства

Новый файл src/x86/ops_branch.zig:

//! Условия и переходы: `test`, `jcc`, `jmp`, `setcc`, `cmovcc`.
//!
//! Шестнадцать условий это четыре бита, и эти четыре бита лежат в младшей
//! половине опкода. Поэтому три совершенно разных семейства инструкций
//! (переход, установка байта, условная пересылка) читаются одинаково:
//! берём младшие четыре бита опкода и смотрим имя в одной и той же таблице.
//!
//! Цель перехода в машинном коде записана смещением от конца инструкции,
//! а не адресом. Абсолютный адрес считает декодер, чтобы читателю не
//! приходилось складывать числа в уме.

const std = @import("std");

const cursor_mod = @import("cursor.zig");
const instruction = @import("instruction.zig");

const Cursor = cursor_mod.Cursor;
const Instruction = instruction.Instruction;
const Size = instruction.Size;

/// Шестнадцать условий в порядке младших четырёх битов опкода.
/// Пары идут подряд: условие и его отрицание.
pub const condition_names = [16][]const u8{
    "o",  "no", "b",  "ae", "e",  "ne", "be", "a",
    "s",  "ns", "p",  "np", "l",  "ge", "le", "g",
};

/// Приклеивает общее начало к каждому из шестнадцати имён условий.
/// Считается на этапе компиляции, в готовой программе это просто таблица строк.
fn withPrefix(comptime prefix: []const u8) [16][]const u8 {
    var result: [16][]const u8 = undefined;
    inline for (condition_names, 0..) |name, index| result[index] = prefix ++ name;
    return result;
}

pub const jump_names = withPrefix("j");
pub const set_names = withPrefix("set");
pub const cmov_names = withPrefix("cmov");

/// Условный переход. Смещение бывает однобайтным (опкоды с 0x70 по 0x7F)
/// и четырёхбайтным (0x0F вместе с опкодами с 0x80 по 0x8F).
pub fn conditionalJump(cursor: *Cursor, condition: u4, comptime width: usize) ?Instruction {
    const displacement = cursor.readSigned(width) orelse return null;
    return cursor.one(
        jump_names[condition],
        null,
        .{ .target = cursor.relativeTarget(displacement) },
    );
}

/// Безусловный переход по смещению: 0xEB на один байт, 0xE9 на четыре.
pub fn jump(cursor: *Cursor, comptime width: usize) ?Instruction {
    const displacement = cursor.readSigned(width) orelse return null;
    return cursor.one("jmp", null, .{ .target = cursor.relativeTarget(displacement) });
}

/// Установка байта по условию: результат сравнения превращается в 0 или 1
/// без единой ветки. Приёмник всегда однобайтный, суффикса у мнемоники нет.
pub fn setCondition(cursor: *Cursor, condition: u4) ?Instruction {
    const modrm = cursor.readModRm(.byte) orelse return null;
    return cursor.one(set_names[condition], null, modrm.rm);
}

/// Условная пересылка: значение переносится, только если условие верно.
/// Ветки в машинном коде нет, поэтому предсказатель переходов не ошибается.
pub fn conditionalMove(cursor: *Cursor, condition: u4, size: Size) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    return cursor.two(
        cmov_names[condition],
        size.suffix(),
        modrm.rm,
        .{ .register = cursor.register(modrm.reg, size) },
    );
}

test "имена условий склеиваются на этапе компиляции" {
    try std.testing.expectEqualStrings("je", jump_names[4]);
    try std.testing.expectEqualStrings("jne", jump_names[5]);
    try std.testing.expectEqualStrings("setl", set_names[12]);
    try std.testing.expectEqualStrings("cmovg", cmov_names[15]);
}

Всё, что ты узнал про поле cc, здесь стало одной таблицей. Шестнадцать имён лежат в порядке младших четырёх битов опкода, а три таблицы с приставками j, set и cmov склеивает функция withPrefix на этапе компиляции. Поэтому jle из 7e, jle из 0f 8e, setle из 0f 9e и cmovle из 0f 4e берут имя из одной и той же клетки номер 14.

Из таблицы видно и то, чего в ней нет. Синонимов вроде setnge или jz здесь не найдёшь: у опкода одно имя, и дизассемблер печатает то, которое выбрал LLVM. Об этом второе упражнение урока.

Суффиксы ширины расставлены по смыслу. У перехода его нет вовсе, у setcc приёмник всегда байт, и писать ширину незачем, а cmovcc работает с 16, 32 и 64 битами и получает суффикс, как mov.

test и новые строки таблицы

В src/x86/decoder.zig появляется импорт const branch = @import("ops_branch.zig");, а в однобайтной таблице, сразу после 0x63, три новых блока:

        // Условные переходы с однобайтным смещением: младшие четыре бита
        // опкода это номер условия.
        0x70...0x7f => branch.conditionalJump(cursor, @truncate(opcode), 1),

        // Проверка битов без записи результата: только флаги.
        0x84 => data.regToRm(cursor, "test", .byte),
        0x85 => data.regToRm(cursor, "test", wide),
        0xa8 => testAccumulator(cursor, .byte),
        0xa9 => testAccumulator(cursor, wide),

        // Безусловные переходы по смещению.
        0xe9 => branch.jump(cursor, 4),
        0xeb => branch.jump(cursor, 1),

В двухбайтной таблице, между 0x1f и 0xaf, ещё три строки, по одной на семейство:

        // Условная пересылка, условный переход с четырёхбайтным смещением
        // и установка байта по условию: три семейства, одна таблица условий.
        0x40...0x4f => branch.conditionalMove(cursor, @truncate(opcode), wide),
        0x80...0x8f => branch.conditionalJump(cursor, @truncate(opcode), 4),
        0x90...0x9f => branch.setCondition(cursor, @truncate(opcode)),

@truncate(opcode) до u4 отрезает старшую половину байта, и остаются ровно четыре бита условия. Функция testAccumulator живёт рядом с multiByteNop:

/// Опкоды 0xA8 и 0xA9: проверка аккумулятора непосредственным значением.
/// Номер регистра здесь нулевой и в машинном коде не записан.
fn testAccumulator(cursor: *Cursor, size: Size) ?Instruction {
    const value = cursor.readImmediate(size) orelse return null;
    return cursor.two(
        "test",
        size.suffix(),
        .{ .immediate = value },
        .{ .register = cursor.register(0, size) },
    );
}

Параметр mnemonic у data.regToRm, заведённый на прошлом шаге, окупился здесь: test в форме MR ничем не отличается от mov, кроме имени. А у testAccumulator форма та же, что у add $imm, %eax: номер регистра ноль подразумевается самим опкодом.

Последний test сидит в группе 0xf7, в номерах 0 и 1, которые на прошлом шаге возвращали null. В src/x86/ops_alu.zig функция group3 теперь выглядит так:

/// Группа 0xF6 и 0xF7. Поле reg выбирает одну из восьми операций, и две из
/// них ведут себя иначе всех: `test` берёт непосредственное значение,
/// а умножение и деление работают с парой регистров молча, не записывая их.
pub fn group3(cursor: *Cursor, size: Size) ?Instruction {
    const modrm = cursor.readModRm(size) orelse return null;
    return switch (modrm.digit) {
        0, 1 => blk: {
            const value = cursor.readImmediate(size) orelse break :blk null;
            break :blk cursor.two("test", size.suffix(), .{ .immediate = value }, modrm.rm);
        },
        2 => cursor.one("not", size.suffix(), modrm.rm),
        3 => cursor.one("neg", size.suffix(), modrm.rm),
        4 => cursor.one("mul", size.suffix(), modrm.rm),
        5 => cursor.one("imul", size.suffix(), modrm.rm),
        6 => cursor.one("div", size.suffix(), modrm.rm),
        7 => cursor.one("idiv", size.suffix(), modrm.rm),
    };
}

Номер 1 это запасное кодирование того же test: процессор его понимает, ассемблеры его не выдают, а дизассемблер обязан прочитать.

Замена сегмента

Последняя деталь шага нужна не для переходов, а для чужого кода. Заведи в Zig переменную threadlocal и прочитай её:

threadlocal var counter: u64 = 0;

export fn bump() u64 {
    counter += 1;
    return counter;
}

$ zig build-obj tls.zig -O ReleaseFast -target x86_64-linux -femit-bin=tls.o
$ objdump -dr tls.o | tail -n +6
0000000000000000 <tls.bump>:
       0: 55                           	pushq	%rbp
       1: 48 89 e5                     	movq	%rsp, %rbp
       4: 64 48 8b 04 25 00 00 00 00   	movq	%fs:0x0, %rax
		0000000000000009:  R_X86_64_TPOFF32	tls.counter
       d: 48 83 c0 01                  	addq	$0x1, %rax
      11: 64 48 89 04 25 00 00 00 00   	movq	%rax, %fs:0x0
		0000000000000016:  R_X86_64_TPOFF32	tls.counter
      1a: 5d                           	popq	%rbp
      1b: c3                           	retq

Байт 64 перед 48 8b это префикс замены сегмента: адрес считается не от нуля, а от базы сегмента %fs, которую система для каждого потока ставит на его блок локальных данных. Нули в смещении это заглушка, которую заполнит компоновщик по перемещению R_X86_64_TPOFF32, так же как в creadCmov выше. Декодер после урока 11 этот байт не знал:

$ ./zig-out/bin/zt disasm tls.o
       0: 55                           	pushq	%rbp
       1: 48 89 e5                     	movq	%rsp, %rbp
       4: 64                           	(bad)
       5: 48 8b 04 25 00 00 00 00      	movq	0x0, %rax
       d: 48 83 c0 01                  	addq	$0x1, %rax
      11: 64                           	(bad)
      12: 48 89 04 25 00 00 00 00      	movq	%rax, 0x0
      1a: 5d                           	popq	%rbp
      1b: c3                           	retq

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

    /// Префикс замены сегмента: он же 0x3E, если после него идёт обращение
    /// в память. Печатается перед адресом, как `%cs:(%rax)`.
    segment: ?[]const u8 = null,

readPrefixes учится шести байтам сегментов:

    /// Префиксы идут перед опкодом в любом порядке, но REX обязан стоять
    /// последним: сразу за ним читается опкод.
    pub fn readPrefixes(cursor: *Cursor) void {
        while (cursor.peek()) |byte| {
            switch (byte) {
                0x66 => cursor.prefixes.operand_size = true,
                0xf2 => cursor.prefixes.repne = true,
                0xf3 => cursor.prefixes.repe = true,
                // Один и тот же байт 0x3E значит замену сегмента перед
                // обращением в память и notrack перед косвенным переходом.
                // Что именно, становится ясно только по операндам.
                0x3e => {
                    cursor.prefixes.notrack = true;
                    cursor.prefixes.segment = "ds";
                },
                0x26 => cursor.prefixes.segment = "es",
                0x2e => cursor.prefixes.segment = "cs",
                0x36 => cursor.prefixes.segment = "ss",
                0x64 => cursor.prefixes.segment = "fs",
                0x65 => cursor.prefixes.segment = "gs",
                0x40...0x4f => {
                    cursor.prefixes.rex = byte;
                    cursor.pos += 1;
                    return;
                },
                else => return,
            }
            cursor.pos += 1;
        }
    }

readMemory переносит сегмент из префиксов в адрес: его первая строка теперь var memory: Memory = .{ .segment = cursor.prefixes.segment };. Поле segment в Memory заведено ещё в уроке 9, так что instruction.zig не меняется. Остаётся форматтер, где сегмент печатается впереди адреса. Вот formatMemory из src/x86/formatter.zig целиком:

fn formatMemory(out: *std.Io.Writer, memory: instruction.Memory) !void {
    // Замена сегмента идёт впереди всего адреса.
    if (memory.segment) |segment| try out.print("%{s}:", .{segment});

    // Нулевое смещение не печатается, если адрес и без него полный.
    const show_displacement = memory.displacement != 0 or
        (memory.base == null and memory.index == null);
    if (show_displacement) {
        if (memory.displacement < 0) {
            try out.print("-0x{x}", .{@abs(memory.displacement)});
        } else {
            try out.print("0x{x}", .{memory.displacement});
        }
    }

    if (memory.rip_target != null) {
        try out.writeAll("(%rip)");
        return;
    }
    if (memory.base == null and memory.index == null) return;

    try out.writeByte('(');
    if (memory.base) |base| try out.print("%{s}", .{base.name()});
    if (memory.index) |index| {
        try out.print(",%{s}", .{index.name()});
        // Множитель 1 подразумевается и не печатается.
        if (memory.scale != 1) try out.print(",{d}", .{memory.scale});
    }
    try out.writeByte(')');
}

Байт 0x3e особенный: перед обращением в память это замена сегмента на %ds, а перед косвенным переходом это notrack, пометка для защиты потока управления. Какой смысл верный, видно только по самой инструкции, поэтому курсор запоминает оба. Как этот байт выглядит перед косвенным переходом, увидишь в уроке 13.

Тот же объектник после шага:

$ ./zig-out/bin/zt disasm tls.o
       0: 55                           	pushq	%rbp
       1: 48 89 e5                     	movq	%rsp, %rbp
       4: 64 48 8b 04 25 00 00 00 00   	movq	%fs:0x0, %rax
       d: 48 83 c0 01                  	addq	$0x1, %rax
      11: 64 48 89 04 25 00 00 00 00   	movq	%rax, %fs:0x0
      1a: 5d                           	popq	%rbp
      1b: c3                           	retq

Остаётся сослаться на новый файл из src/root.zig строкой pub const ops_branch = @import("x86/ops_branch.zig"); в структуре x86 и дописать 12 в project_steps в build.zig.

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

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

/// Все шестнадцать условий в трёх семействах сразу, плюс test и оба
/// безусловных перехода. Метки нужны только затем, чтобы смещения
/// получились и вперёд, и назад.
export fn ztConditions() callconv(.naked) void {
    asm volatile (
        \\testl %eax, %eax
        \\testq %rax, %rbx
        \\testb %al, %cl
        \\testl %eax, (%rdi)
        \\testb $1, %al
        \\testl $0x1234, %eax
        \\testq $0xff, %rax
        \\cmpl %eax, %ebx
        \\1:
        \\jo 2f
        \\jno 2f
        \\jb 2f
        \\jae 2f
        \\je 2f
        \\jne 2f
        \\jbe 2f
        \\ja 2f
        \\js 2f
        \\jns 2f
        \\jp 2f
        \\jnp 2f
        \\jl 2f
        \\jge 2f
        \\jle 2f
        \\jg 2f
        \\jmp 1b
        \\seto %al
        \\setb %cl
        \\sete %dl
        \\setne %bl
        \\setbe %sil
        \\seta %dil
        \\sets %r8b
        \\setns %r9b
        \\setp %al
        \\setnp %al
        \\setl %al
        \\setge %al
        \\setle %al
        \\setg %al
        \\setl 8(%rsp)
        \\cmovol %eax, %ecx
        \\cmovbl %eax, %ecx
        \\cmovel %eax, %ecx
        \\cmovneq %rax, %rcx
        \\cmovbeq %rax, %rcx
        \\cmoval %eax, %ecx
        \\cmovsl %eax, %ecx
        \\cmovnsq %rax, %rcx
        \\cmovll %eax, %ecx
        \\cmovgeq %rax, %rcx
        \\cmovlel %eax, %ecx
        \\cmovgq %rax, %rcx
        \\cmovel (%rdi), %ecx
        \\2:
        \\ret
    );
}

/// Далёкий переход: смещение не влезает в один байт, и кодировщик
/// вынужден взять четырёхбайтную форму. Расстояние набирается сотней
/// пустых инструкций, чтобы в секции не было дыры из нулей.
export fn ztFarJump() callconv(.naked) void {
    asm volatile (
        \\je 1f
        \\jmp 1f
        \\.rept 100
        \\nop
        \\.endr
        \\1:
        \\ret
    );
}

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

Сверь эталон с комментарием к ztFarJump, и ты найдёшь расхождение. Замысел был получить длинную форму перехода, но сотня nop это сто байтов, а до цели от конца je всего 0x66, то есть 102. В знаковый байт это влезает, и ассемблер честно выбрал короткую форму 74 66: он всегда берёт самую короткую кодировку, которой хватает. Чтобы получить 0f 84, нужно больше 127 байтов. Замени .rept 100 на .rept 200, собери файл как far.o, и ассемблер сдастся:

$ objdump -d far.o | sed -n '6,8p'
0000000000000000 <ztFarJump>:
       0: 0f 84 cd 00 00 00            	je	0xd3 <ztFarJump+0xd3>
       6: e9 c8 00 00 00               	jmp	0xd3 <ztFarJump+0xd3>

Ровно эти байты записаны в тест «далёкое смещение» ниже, поэтому длинная форма проверена, хоть фикстура её и не содержит. Цель у jmp в тесте получится 0xcd, а не 0xd3: тест разбирает его с адреса ноль, а не шесть.

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

//! Шаг 12: test, условные переходы, setcc и cmovcc.
//!
//! Шестнадцать условий это четыре бита, и лежат они в младшей половине
//! опкода. Поэтому три разных семейства инструкций читаются одинаково:
//! берём младшие четыре бита и смотрим имя в одной таблице.

const std = @import("std");

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

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

const decode = zt.x86.decoder.decode;

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

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

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

test "test проверяет биты, не записывая результат" {
    try expectOne(&.{ 0x85, 0xc0 }, "testl\t%eax, %eax");
    try expectOne(&.{ 0x48, 0x85, 0xc3 }, "testq\t%rax, %rbx");
    try expectOne(&.{ 0x84, 0xc1 }, "testb\t%al, %cl");
    try expectOne(&.{ 0x85, 0x07 }, "testl\t%eax, (%rdi)");
    try expectOne(&.{ 0xa8, 0x01 }, "testb\t$0x1, %al");
    try expectOne(&.{ 0x48, 0xf7, 0xc3, 0x01, 0x00, 0x00, 0x00 }, "testq\t$0x1, %rbx");
}

test "все шестнадцать условий в порядке младших четырёх битов опкода" {
    const expected = [16][]const u8{
        "jo", "jno", "jb", "jae", "je",  "jne", "jbe", "ja",
        "js", "jns", "jp", "jnp", "jl",  "jge", "jle", "jg",
    };
    for (expected, 0..) |name, index| {
        const short = decode(&.{ @intCast(0x70 + index), 0x00 }, 0);
        try std.testing.expectEqualStrings(name, short.mnemonic);
        const near = decode(&.{ 0x0f, @intCast(0x80 + index), 0, 0, 0, 0 }, 0);
        try std.testing.expectEqualStrings(name, near.mnemonic);
    }
}

test "цель перехода считается от конца инструкции" {
    // je с однобайтным смещением 0x66: два байта длиной, цель 0x68.
    const short = decode(&.{ 0x74, 0x66 }, 0);
    try std.testing.expectEqual(@as(u64, 0x68), short.operandSlice()[0].target);
    try expectOne(&.{ 0x74, 0x66 }, "je\t0x68");

    // Переход назад: смещение отрицательное.
    const backward = decode(&.{ 0xeb, 0xfa }, 0x10);
    try std.testing.expectEqual(@as(u64, 0x0c), backward.operandSlice()[0].target);
}

test "далёкое смещение не влезает в байт и берёт четырёхбайтную форму" {
    const near = [_]u8{ 0x0f, 0x84, 0xcd, 0x00, 0x00, 0x00 };
    try std.testing.expectEqual(@as(usize, 6), decode(&near, 0).length());
    try expectOne(&near, "je\t0xd3");
    try expectOne(&.{ 0xe9, 0xc8, 0x00, 0x00, 0x00 }, "jmp\t0xcd");
}

test "setcc превращает условие в байт без единой ветки" {
    try expectOne(&.{ 0x0f, 0x94, 0xc0 }, "sete\t%al");
    try expectOne(&.{ 0x0f, 0x95, 0xc1 }, "setne\t%cl");
    try expectOne(&.{ 0x0f, 0x9c, 0xc0 }, "setl\t%al");
    try expectOne(&.{ 0x0f, 0x9f, 0xc0 }, "setg\t%al");
    try expectOne(&.{ 0x0f, 0x9c, 0x44, 0x24, 0x08 }, "setl\t0x8(%rsp)");
}

test "cmovcc переносит значение без ветвления" {
    try expectOne(&.{ 0x0f, 0x44, 0xc8 }, "cmovel\t%eax, %ecx");
    try expectOne(&.{ 0x48, 0x0f, 0x45, 0xc8 }, "cmovneq\t%rax, %rcx");
    try expectOne(&.{ 0x0f, 0x44, 0x0f }, "cmovel\t(%rdi), %ecx");
}

test "у setcc нет суффикса ширины, а у cmovcc есть" {
    // Приёмник setcc всегда один байт, поэтому ширину писать незачем.
    try std.testing.expectEqual(@as(?u8, null), decode(&.{ 0x0f, 0x94, 0xc0 }, 0).suffix);
    try std.testing.expectEqual(@as(?u8, 'l'), decode(&.{ 0x0f, 0x44, 0xc8 }, 0).suffix);
    try std.testing.expectEqual(@as(?u8, 'q'), decode(&.{ 0x48, 0x0f, 0x45, 0xc8 }, 0).suffix);
}

test "замена сегмента печатается перед адресом" {
    // Выравнивающий nop с префиксом cs и чтение локальных данных потока.
    try expectOne(&.{ 0x2e, 0x0f, 0x1f, 0x04, 0x00 }, "nopl\t%cs:(%rax,%rax)");
    try expectOne(&.{ 0x64, 0x48, 0x8b, 0x04, 0x25, 0x00, 0x00, 0x00, 0x00 }, "movq\t%fs:0x0, %rax");
}

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

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

Тест «все шестнадцать условий» стоит отдельного взгляда: он не перечисляет тридцать две строки, а обходит таблицу циклом и собирает опкод на лету, 0x70 + index для короткой формы и 0x0f, 0x80 + index для длинной. Раз условия лежат по порядку, тест тоже можно написать по порядку.

Прогон

$ zig build test --summary all
Build Summary: 15/15 steps succeeded; 80/80 tests passed
test success
+- run test 20 pass (20 total) 10ms MaxRSS:2M
|  +- compile test Debug native cached 79ms MaxRSS:35M
+- run test 5 pass (5 total) 35ms MaxRSS:2M
|  +- compile test Debug native cached 79ms MaxRSS:35M
+- run test 7 pass (7 total) 18ms MaxRSS:2M
|  +- compile test Debug native cached 78ms MaxRSS:35M
+- run test 10 pass (10 total) 18ms MaxRSS:2M
|  +- compile test Debug native cached 79ms MaxRSS:35M
+- run test 14 pass (14 total) 49ms MaxRSS:2M
|  +- compile test Debug native cached 77ms MaxRSS:35M
+- run test 13 pass (13 total) 33ms MaxRSS:2M
|  +- compile test Debug native cached 79ms MaxRSS:35M
+- run test 11 pass (11 total) 17ms MaxRSS:2M
   +- compile test Debug native cached 79ms MaxRSS:35M

Прибавилась строка шага 12, а в тестах модулей стало на один больше: это тест про имена условий внутри ops_branch.zig.

Дизассемблер на фикстуре, середина из сотни nop пропущена:

$ zig build && ./zig-out/bin/zt disasm fixtures/step_12.o
       0: 74 66                        	je	0x68
       2: eb 64                        	jmp	0x68
       4: 90                           	nop
       5: 90                           	nop
       6: 90                           	nop
...
      66: 90                           	nop
      67: 90                           	nop
      68: c3                           	retq
      69: 0f 1f 80 00 00 00 00         	nopl	(%rax)
      70: 85 c0                        	testl	%eax, %eax
      72: 48 85 c3                     	testq	%rax, %rbx
      75: 84 c1                        	testb	%al, %cl
      77: 85 07                        	testl	%eax, (%rdi)
      79: a8 01                        	testb	$0x1, %al
      7b: a9 34 12 00 00               	testl	$0x1234, %eax
      80: 48 a9 ff 00 00 00            	testq	$0xff, %rax
      86: 39 c3                        	cmpl	%eax, %ebx
      88: 70 7f                        	jo	0x109
      8a: 71 7d                        	jno	0x109
      8c: 72 7b                        	jb	0x109
      8e: 73 79                        	jae	0x109
      90: 74 77                        	je	0x109
      92: 75 75                        	jne	0x109
      94: 76 73                        	jbe	0x109
      96: 77 71                        	ja	0x109
      98: 78 6f                        	js	0x109
      9a: 79 6d                        	jns	0x109
      9c: 7a 6b                        	jp	0x109
      9e: 7b 69                        	jnp	0x109
      a0: 7c 67                        	jl	0x109
      a2: 7d 65                        	jge	0x109
      a4: 7e 63                        	jle	0x109
      a6: 7f 61                        	jg	0x109
      a8: eb de                        	jmp	0x88
      aa: 0f 90 c0                     	seto	%al
      ad: 0f 92 c1                     	setb	%cl
      b0: 0f 94 c2                     	sete	%dl
      b3: 0f 95 c3                     	setne	%bl
      b6: 40 0f 96 c6                  	setbe	%sil
      ba: 40 0f 97 c7                  	seta	%dil
      be: 41 0f 98 c0                  	sets	%r8b
      c2: 41 0f 99 c1                  	setns	%r9b
      c6: 0f 9a c0                     	setp	%al
      c9: 0f 9b c0                     	setnp	%al
      cc: 0f 9c c0                     	setl	%al
      cf: 0f 9d c0                     	setge	%al
      d2: 0f 9e c0                     	setle	%al
      d5: 0f 9f c0                     	setg	%al
      d8: 0f 9c 44 24 08               	setl	0x8(%rsp)
      dd: 0f 40 c8                     	cmovol	%eax, %ecx
      e0: 0f 42 c8                     	cmovbl	%eax, %ecx
      e3: 0f 44 c8                     	cmovel	%eax, %ecx
      e6: 48 0f 45 c8                  	cmovneq	%rax, %rcx
      ea: 48 0f 46 c8                  	cmovbeq	%rax, %rcx
      ee: 0f 47 c8                     	cmoval	%eax, %ecx
      f1: 0f 48 c8                     	cmovsl	%eax, %ecx
      f4: 48 0f 49 c8                  	cmovnsq	%rax, %rcx
      f8: 0f 4c c8                     	cmovll	%eax, %ecx
      fb: 48 0f 4d c8                  	cmovgeq	%rax, %rcx
      ff: 0f 4e c8                     	cmovlel	%eax, %ecx
     102: 48 0f 4f c8                  	cmovgq	%rax, %rcx
     106: 0f 44 0f                     	cmovel	(%rdi), %ecx
     109: c3                           	retq

Сравнение с эталоном, первые строки:

$ objdump -d fixtures/step_12.o | tail -n +6 > od12.txt
$ ./zig-out/bin/zt disasm fixtures/step_12.o > zt12.txt
$ diff od12.txt zt12.txt | head -n 14
1,3c1,2
< 0000000000000000 <ztFarJump>:
<        0: 74 66                        	je	0x68 <ztFarJump+0x68>
<        2: eb 64                        	jmp	0x68 <ztFarJump+0x68>
---
>        0: 74 66                        	je	0x68
>        2: eb 64                        	jmp	0x68
106,107d104
< 
< 0000000000000070 <ztConditions>:
113c110
<       7b: a9 34 12 00 00               	testl	$0x1234, %eax           # imm = 0x1234
---
>       7b: a9 34 12 00 00               	testl	$0x1234, %eax

Остальная часть diff устроена так же, как первый блок: семнадцать переходов, у которых objdump дописал подпись цели вроде <ztConditions+0x99>. Адреса совпадают все до одного, а подписи требуют таблицы символов. Это ровно тот случай, ради которого zt в уроке 42 научится читать ELF: тогда вместо jo 0x109 появится jo 0x109 <ztConditions+0x99>.

И наконец gcd, с которого раздел начался:

$ ./zig-out/bin/zt disasm jumps_small.o
       0: 48 89 f2                     	movq	%rsi, %rdx
       3: 48 89 f8                     	movq	%rdi, %rax
       6: 48 85 d2                     	testq	%rdx, %rdx
       9: 74 0d                        	je	0x18
       b: 48 89 d1                     	movq	%rdx, %rcx
       e: 31 d2                        	xorl	%edx, %edx
      10: 48 f7 f1                     	divq	%rcx
      13: 48 89 c8                     	movq	%rcx, %rax
      16: eb ee                        	jmp	0x6
      18: c3                           	retq

Сверь с листингом objdump выше: байты, мнемоники и обе цели совпадают, 0x18 вперёд и 0x6 назад.

Практика

Обе половины задачи урока ты уже разобрал по частям. Первая это cread(xp: ?*const i64) i64: прочитать число по указателю, а на null вернуть ноль, и чтобы в машинном коде не осталось условного перехода. Выбирать надо адрес, а не прочитанное значение, иначе получится та самая сломанная версия, которая ходит по нулевому адресу и умирает.

Вторая функция absDiff(x, y) считает модуль разности. Разность бери с переносом (x -% y), иначе на краях диапазона сработает проверка переполнения. Модуль тоже получается без сравнения: арифметический сдвиг вправо на 63 превращает знак в маску из одних нулей или одних единиц, а исключающее или с этой маской плюс вычитание её же переворачивают знак ровно тогда, когда он отрицательный. Отсутствие переходов тесты не проверяют, это дело чести: собери объектник под x86-64 и посмотри дизассемблер сам, там должны остаться cmov и арифметика.

Упражнения

CHK-1★

Выпиши из таблицы cc четыре строки знаковых сравнений и четыре беззнаковых, а рядом условие по флагам. Потом возьми x равный minInt(i64) и y равный 1 и покажи на этой паре, почему знаковое «меньше» это SF ^ OF, а не просто SF. Ответ проверь тестом на Zig: сравни x < y для i64 и для тех же битов, прочитанных как u64.

CHK-2★★

Собери десять функций сравнения из урока и выпиши второй байт опкода для каждой. Затем напиши рукописный ассемблер, где те же условия записаны синонимами (setnge вместо setl, setc вместо setb, setna вместо setbe), собери и убедись по байтам, что опкоды совпали. Объясни, почему дизассемблер печатает не то имя, которое ты написал.

CHK-3★★

Возьми свою функцию с циклом, собери её в ReleaseSmall и посчитай руками цель каждого перехода: опкод, смещение, адрес следующей инструкции, сумма. Сверь с тем, что напечатал дизассемблер. Найди в том же файле хотя бы один переход в длинной форме 0F 8x и объясни, почему для него не хватило одного байта смещения.

CHK-4★★

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

CHK-5★★

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

CHK-6★★★

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

CHK-7★★★

Сделай шаг проекта у себя: relativeTarget в курсоре, файл ops_branch.zig, test в трёх местах таблицы и префиксы сегментов. Прогони zig build test --summary all, тесты шагов 09, 10 и 11 обязаны остаться зелёными. Потом собери свою фикстуру с длинным переходом (.rept 200), сними эталон и добейся пустого diff с zt disasm после удаления подписей в угловых скобках. В конце найди в любом своём объектнике переход назад и проверь, что zt посчитал его цель так же, как ты руками.

Итоги

Флаги это побочный продукт арифметики, а не отдельная операция. CF смотрит на переполнение беззнаковой операции, OF на переполнение знаковой, ZF на ноль, SF на старший бит результата.
Процессор выставляет все четыре флага всегда. Какие из них считать за «меньше», решает компилятор по типам из исходника, и вся разница знакового и беззнакового сравнения живёт в мнемонике читающей инструкции.
cmp это вычитание без записи результата, test это побитовое И без записи результата. Обе созданы только ради флагов.
testq %rax, %rax дешевле, чем cmpq $0, %rax: три байта против четырёх, а ZF и SF получаются те же.
lea считает, но молчит: флаги остаются прежними. Поэтому её можно поставить между сравнением и переходом, но если результат надо проверить, за проверку придётся платить отдельно.
Условие это одно четырёхбитное поле cc, общее для трёх семейств: setcc с опкодом 0F 9x, jcc с 0F 8x или коротким 7x, cmovcc с 0F 4x. Таблицу условий достаточно выучить один раз.
Пары вроде setl и setnge это не разные инструкции, а разные имена одного опкода.
Смещение перехода отсчитывается от адреса следующей инструкции, а не от адреса самого перехода, и потому не зависит от того, куда программу загрузят в память.
У перехода две формы: короткая, один байт опкода плюс знаковый байт смещения, и длинная, два байта опкода плюс четыре байта смещения.
if в машинном коде обычно развёрнут по отрицанию условия: тело первой ветви лежит сразу за проверкой, а переход уводит в редкий случай.
cmov считает обе ветви и выбирает результат, поэтому перехода нет вовсе. Схема всегда одна: положить значение ветви по умолчанию, сравнить, условно перезаписать.
Компилятор не поставит cmov, если ветвь имеет побочный эффект, если она читает по указателю, который может оказаться пустым, или если она дорогая, как деление.
Обратное тоже верно: написанный руками if часто исчезает из машинного кода, превращаясь в setcc плюс безусловную арифметику.
Безопасное чтение без ветвления выбирает не прочитанное значение, а адрес: на месте пустого указателя должен оказаться адрес настоящей ячейки с нулём. Сначала сделай операцию безусловно безопасной, потом убирай ветвь.
Штраф за ошибку предсказания это полтора десятка тактов, и на непредсказуемых данных он даёт разницу на порядок. У безветвевой формы цена не зависит от данных вообще.
В шаге проекта zt disasm научился читать test, jcc, setcc, cmovcc и jmp: одна таблица из шестнадцати условий на три семейства, цель перехода считается от конца инструкции сразу при разборе, а префикс сегмента печатается перед адресом, как в %fs:0x0.

Дальше

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

домашка

Домашка

Возьми свою функцию с двумя вложенными условиями, собери объектник под x86-64 и посчитай цель каждого перехода руками по байтам смещения, потом сверь с адресом, который напечатал objdump.M
Найди в своём коде две функции: одну, где компилятор выбрал cmov, и одну, где он оставил переход. Объясни для второй, какое именно свойство ветви запретило условную передачу данных.MS
Прогони измерение из урока с порогами от 0 до 1000 с шагом 100 и построй таблицу время против доли взятых ветвей. Объясни, почему кривая симметрична и где у неё максимум.MS