Базовый CS с нуля
Условия как ветвления
Ты можешь написать if (x > 0) { ... } else { ... } на любом языке. Но что CPU реально
делает, когда доходит до этой строки?
Ответ — не «CPU проверяет условие». У CPU нет схемы, понимающей > как абстрактную идею.
Есть два гораздо более простых механизма, работающих вместе: инструкция сравнения,
которая записывает соотношение между двумя значениями в набор однобитных флагов
результата, и инструкция условного перехода, которая читает один из этих флагов и
решает — исключительно по тому, равен ли один бит 0 или 1 — прыгать или продолжить
выполнение дальше.
Эта двухшаговая последовательность — сравнение, затем условный переход — и есть то, как
каждый if в каждой программе на каждой CPU-архитектуре реализован с 1950-х годов. Как
только ты это поймёшь, ты никогда не будешь смотреть на if по-прежнему.
После этого урока ты сможешь описать, как инструкция сравнения записывает результат в регистр флагов, объяснить, что означает «продолжение без перехода» (fall-through) для условного перехода, трассировать машинное выполнение простого if/else через обе ветви и объяснить, почему if/else — это два возможных пункта назначения для счётчика команд.
Регистр флагов: запись результатов сравнения. В большинстве CPU есть специальный регистр, называемый регистром флагов (также регистром кодов условия или регистром состояния на разных архитектурах). В отличие от регистра общего назначения R0 или R1, регистр флагов — не одно большое число. Это набор отдельных битов, каждый из которых представляет ответ на один вопрос «да/нет» о последней арифметической или сравнивающей операции.
Три наиболее важных флага для условий:
- Z (флаг нуля): устанавливается в 1, если результат последней операции равен нулю; 0 в противном случае.
- N (флаг знака/отрицательного числа): устанавливается в 1, если результат отрицателен (старший бит равен 1 в знаковой арифметике); 0 в противном случае.
- C (флаг переноса): устанавливается в 1, если последнее беззнаковое сложение произвело перенос из старшего бита (т. е. результат переполнил ширину регистра).
Эти флаги обновляются автоматически многими инструкциями — арифметическими, логическими и инструкциями сравнения — как побочный эффект их нормального выполнения. Инструкции LOAD и STORE не устанавливают флаги: они не производят числового результата.
Инструкция сравнения: вычитание, которое только обновляет флаги. Инструкция CMP (compare, сравнение) принимает два операнда — обычно два регистра или регистр и константу — и вычитает один из другого. Ключевая особенность: CMP отбрасывает результат вычитания. Он не записывает результат ни в какой регистр. Его единственная цель — обновить флаги.
Например, CMP R0, R1 вычисляет R0 − R1 внутренне, выбрасывает числовой результат
и обновляет флаги:
- Если R0 = R1, то R0 − R1 = 0, поэтому флаг Z устанавливается в 1.
- Если R0 < R1 (в знаковой арифметике), результат отрицательный, поэтому флаг N устанавливается в 1.
- Если R0 > R1 (в знаковой арифметике), результат положительный и ненулевой, поэтому Z = 0 и N = 0.
Ни один регистр не модифицируется. R0 и R1 сохраняют свои значения. Изменяется только регистр флагов.
Инструкция сравнения — это механизм, с помощью которого CPU записывает соотношение между двумя значениями в форму, которую может прочитать следующая инструкция — условный переход.
Условный переход: чтение одного бита флага. Инструкция условного перехода (иногда обозначается Jxx, где xx называет условие — например, JZ для «прыжок, если ноль», JNZ для «прыжок, если не ноль», JL для «прыжок, если меньше») делает одно: читает конкретный флаг из регистра флагов и принимает бинарное решение:
- Если флаг равен 1 (условие выполнено): переход — установить счётчик команд в адрес назначения перехода.
- Если флаг равен 0 (условие не выполнено): продолжение без перехода (fall-through) — ничего не делать со СК; дать ему продвинуться в обычном порядке к следующей инструкции.
Продолжение без перехода означает «перейти к непосредственно следующей инструкции в памяти». Это не отдельная инструкция — это отсутствие перехода. Когда условие ложно, условный переход ведёт себя идентично пустой операции: СК продвигается на размер инструкции и выполнение продолжается со следующей инструкцией.
Условный переход читает ровно один бит флага. Он не переоценивает исходное выражение
x > 0. Сравнение уже произошло; флаг — это остаток того сравнения.
Почему это работает
Зачем разделять CMP и условный переход? Разделение делает обе инструкции простыми. CMP — чистый установщик флагов, которому не нужна логика управления потоком. Условный переход — чистый изменитель СК, которому не нужна арифметическая логика. Объединение их в одну инструкцию потребовало бы от декодера обрабатывать и арифметику, и ветвление одновременно, что усложняет конвейер. Многие реальные архитектуры (x86, ARM, RISC-V) используют именно такой подход CMP + условный переход. Машина Hack из nand2tetris учит тому же разделению в своём минимальном наборе инструкций.
if/else как два пункта назначения. Конструкция if/else в исходном коде
компилируется в паттерн с двумя возможными путями в памяти. Вот общий вид для
if (условие) { A } else { B }:
[инструкция CMP] ; сравнить операнды
[условный переход на ELSE] ; прыжок в блок else, если условие ЛОЖНО
[инструкции для A] ; блок if-true
[безусловный JUMP на END] ; пропустить блок else
[ELSE: инструкции для B] ; блок if-false (else)
[END: ...] ; выполнение продолжается здесь после любой ветвиДва важных наблюдения:
- Условный переход написан как «прыжок если условие ложно», потому что блок true следует сразу после инструкции перехода (fall-through случай), а блок else — позже. Если условие истинно, переход не срабатывает (fall-through), и выполняется блок true. Если условие ложно, переход срабатывает, и выполняется блок else.
- После блока true стоит безусловный переход, пропускающий блок else. Без этого перехода выполнение упало бы в блок else после завершения блока true.
Это конкретный пример того, как счётчик команд направляется к двум разным пунктам назначения в зависимости от значения одного бита флага.
Трассировка if (R0 == R1) через обе ветви.
Предположим, программа компилируется в следующие инструкции (каждая по 4 байта):
Адрес 100: CMP R0, R1 ; сравнить R0 и R1, обновить флаги
Адрес 104: JNE 116 ; прыжок на 116, если Z=0 (R0 ≠ R1)
Адрес 108: STORE R0, 200 ; if-true: записать значение R0 по адресу 200
Адрес 112: JUMP 120 ; пропустить блок else
Адрес 116: STORE R1, 200 ; if-false (else): записать значение R1 по адресу 200
Адрес 120: ... ; программа продолжается здесьСлучай 1: R0 = R1 = 7 (условие истинно).
- CMP по адресу 100: вычислить R0 − R1 = 7 − 7 = 0. Z-флаг ← 1. СК → 104.
- JNE по адресу 104: читать Z-флаг = 1. Условие «не равно» требует Z = 0. Z = 1, поэтому условие ЛОЖНО. Fall-through. СК → 108.
- STORE по адресу 108: записать R0 (= 7) по адресу памяти 200. СК → 112.
- JUMP по адресу 112: безусловный. СК ← 120. Выполнение продолжается с 120.
- Блок else по адресу 116 не был достигнут.
Случай 2: R0 = 3, R1 = 9 (условие ложно).
- CMP по адресу 100: вычислить R0 − R1 = 3 − 9 = −6. Z-флаг ← 0. N-флаг ← 1. СК → 104.
- JNE по адресу 104: читать Z-флаг = 0. Условие «не равно» требует Z = 0. Z = 0, поэтому условие ИСТИННО. Переход. СК ← 116.
- STORE по адресу 116: записать R1 (= 9) по адресу памяти 200. СК → 120.
- Выполнение продолжается с 120.
- Блок if-true по адресам 108–112 не был достигнут.
В обоих случаях один бит флага (Z) определил, по какому из двух путей через память пойдёт счётчик команд. Стоимость if/else на уровне CPU — ровно одна инструкция сравнения и один условный переход.
Граничные случаи
Как насчёт else if? Цепочка else if — это просто несколько пар CMP + условный
переход подряд. Первое условие проверяется; если оно ложно, условный переход пропускает
первый блок к следующему CMP. Паттерн повторяется, пока одно условие не окажется
истинным или все не будут исчерпаны. Каждый дополнительный else if добавляет один
CMP и один условный переход — длина цепочки ограничена только размером программы,
но не каким-либо ограничением CPU.
CMP R0, R1 вычисляет R0 − R1 и отбрасывает результат. Если R0 = 5 и R1 = 5, чему равен флаг Z после выполнения CMP?
CMP R0, R1 выполняется при R0 = 3 и R1 = 7. Чему равен флаг Z?
Инструкция JZ (прыжок если ноль) указывает на адрес 300. Текущее значение Z-флага — 0. CPU прыгает на 300 или продолжает без перехода? Введи 0 для fall-through, 1 для перехода.
Инструкция JZ указывает на адрес 300. Z-флаг равен 1. Сама инструкция JZ находится по адресу 200 (4 байта). Чему равен СК после выполнения JZ?
В блоке if/else, скомпилированном в машинный код, после блока if-true стоит безусловный JUMP. Что он пропускает?
Что такое «продолжение без перехода» (fall-through) в контексте инструкции условного перехода?
Оператор if компилируется в две машинные инструкции, работающие последовательно.
Сначала инструкция CMP (сравнение) вычитает одно значение из другого, отбрасывает
числовой результат и записывает соотношение в виде отдельных битов в регистр флагов —
прежде всего флаг Z (нуля) и флаг N (знака). Затем инструкция условного
перехода читает один из этих битов флага: если условие истинно — устанавливает счётчик
команд в адрес назначения (переход); если ложно — ничего не делает и даёт СК
продвинуться к следующей инструкции (fall-through). if/else — это ровно два
пункта назначения для СК: блок if-true (достигается через fall-through) и блок if-false
(достигается через переход). После блока if-true безусловный переход пропускает блок
else. Во время выполнения выбор между двумя путями стоит ровно одно сравнение и один
условный переход.