Генерация кода: целевые архитектуры, распределение регистров, ABI

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

Дальше начинается вторая половина компилятора — бэкенд, и с ним меняется природа задач. Фронтенд был про смысл: «что программист имел в виду». Бэкенд — про ресурсы: инструкций конечный набор, регистров ровно шестнадцать, стек растёт вниз, а чужой код ждёт аргументы в строго определённых местах. Здесь нет красивых теорем вроде Хиндли — Милнера; здесь NP-полные задачи с жадными эвристиками и документы на сотни страниц, которые надо соблюдать буквально, иначе программа падает не там, где ошиблись. Разберём три составляющие — выбор инструкций, распределение регистров и ABI, — а в конце напишем генератор x86-64 для Mini, соберём его системным ассемблером и вызовем из C.

Что именно делает бэкенд

Вход — линейное IR, где значений сколько угодно и все они «виртуальные регистры». Выход — текст на ассемблере или сразу байты машинного кода. Между ними четыре обязательных этапа и один необязательный.

Обратите внимание на цикл RA → REWRITE → RA. Пока регистры не распределены, размер кадра неизвестен: вдруг понадобятся слоты вытеснения. А пока размер кадра неизвестен, нельзя выписать пролог. Поэтому пролог и эпилог генерируются последними, когда всё остальное уже решено, — и это первая структурная особенность бэкенда, которая удивляет новичков.

Вторая — проблема порядка фаз (phase ordering). Три главные задачи сцеплены: выбор инструкций меняет давление на аллокатор (lea не трогает флаги и не разрушает операнды, а imul может требовать конкретный регистр); планирование ради сокрытия задержек разносит определение и использование, удлиняя интервалы жизни и провоцируя вытеснение; вытеснение порождает новые load, которые снова надо планировать. Оптимально решить все три сразу практичного алгоритма нет, поэтому промышленные компиляторы выбирают порядок и живут с потерями: LLVM и GCC планируют дважды — до аллокации и после, а JIT-компиляторы планирование часто пропускают вовсе, полагаясь на внеочередное исполнение процессора.

Целевая архитектура: что бэкенд обязан о ней знать

«Целевая архитектура» для компилятора — не «Intel против ARM», а конкретный набор ответов на скучные вопросы. Сколько регистров. Может ли арифметика брать операнд из памяти. Есть ли регистр флагов. Что происходит с делением. Как выглядит вызов.

Следствия прямые. Двухадресная форма x86-64 означает, что почти каждая операция начинается с копирования (mov a, tmp; add b, tmp), и половина работы аллокатора — сделать так, чтобы эти копии исчезли. Богатые режимы адресации означают, что три инструкции IR часто складываются в одну машинную. Отсутствие флагов в RISC-V означает, что результат сравнения — обычное значение в регистре, которое надо распределять наравне с остальными.

Отдельная категория знаний — что железо вообще не умеет. Приведение IR к тому, что существует в системе команд, называется легализацией: широкие типы разбиваются на пары регистров, отсутствующие операции разворачиваются в последовательности или в вызовы библиотечных функций (__divti3, __aeabi_ldivmod — это они). Именно поэтому деление 64-битных чисел на 32-битной платформе оказывается вызовом функции, а не инструкцией.

Выбор инструкций: покрытие дерева плитками

Задача звучит просто: заменить операции IR на машинные. Сложность в том, что соответствие не один к одному. Возьмём кусок IR:

t1 = a * 4
t2 = t1 + b
t3 = t2 + 7

Наивный генератор выдаст три инструкции. Реальный x86-64 умеет всё это одной:

leaq 7(%rsi,%rdi,4), %rax    ; rax = rsi + rdi*4 + 7

Проверить легко — вот что даёт gcc -O2 для long f(long a, long b){ return a*4 + b + 7; }: ровно одна leaq. Значит, генератор должен уметь распознавать поддеревья и заменять их одной инструкцией. Формально это задача покрытия дерева плитками (tree tiling): каждая машинная инструкция — «плитка», кусок дерева операций, который она реализует; надо покрыть дерево IR плитками так, чтобы суммарная стоимость была минимальна. Три классических подхода, в порядке роста качества и сложности:

Макроразвёртка. Каждый узел IR разворачивается в фиксированный шаблон, независимо от соседей. Ровно так устроен генератор, который мы напишем ниже, и все учебные компиляторы. Время O(n), качество плохое: ни lea, ни сложных адресаций, много лишних mov. Для отладочной сборки или первого рабочего бэкенда — то, что нужно.

Maximal munch (жадное «максимальное откусывание»). Идём сверху вниз и на каждом узле выбираем самую крупную подходящую плитку, затем рекурсивно обрабатываем оставшиеся корни. Время O(n), качество заметно лучше. Локально оптимально, глобально — нет.

Динамическое программирование (BURS, tree parsing). Для каждого узла считаем минимальную стоимость покрытия поддерева при условии, что результат окажется в заданном классе регистров, — снизу вверх, как в любой задаче ДП. Время O(n × число плиток), результат оптимален для дерева; так работали генераторы burg/iburg, и та же идея живёт в SelectionDAG внутри LLVM. Оговорка важная: оптимальность на дереве. Настоящее IR — ациклический граф (одно значение используется дважды), а там задача уже NP-трудная, см. NP-полноту и приближения; промышленные генераторы разрезают граф на деревья и применяют ДП к кускам.

Насколько это важно на практике, показывает gcc -O1 для a[i*8+3]:

salq  $6, %rsi                ; i * 64
movq  24(%rsi,%rdi), %rax     ; масштаб, база и смещение — внутри одной адресации

Умножение, сложение и разыменование — две инструкции. Тот же код через макроразвёртку занял бы пять.

Финальная страховка — peephole-оптимизации: проход по окну из 2–3 соседних инструкций с локальными переписываниями. mov %rax, %rbx; mov %rbx, %rax → первая инструкция. jmp .L1 непосредственно перед меткой .L1 → ничего. Умножение на степень двойки → сдвиг shlq. Дёшево, механически, убирает основной мусор после макроразвёртки; исторически именно peephole (Маккимен, 1965) был первым «оптимизатором» в компиляторах.

Распределение регистров

Это главная задача бэкенда и единственная, где теория даёт содержательный результат. Формулировка: в IR бесконечно много виртуальных значений, в процессоре k физических регистров; надо назначить каждому значению регистр так, чтобы два значения, живые одновременно, не попали в один регистр. Кому не хватило — тот отправляется в память (вытеснение, spill), и это дорого: обращение к L1 в 3–4 раза медленнее регистра, см. иерархию памяти.

Шаг 1: анализ живости

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

live_out[B] = ∪ live_in[S] по всем преемникам S
live_in[B]  = use[B] ∪ (live_out[B] \ def[B])

Уравнения решаются итерациями до неподвижной точки — блоки обходят в обратном порядке, чтобы информация быстрее текла назад по графу (см. обходы графов). Сложность — O(число блоков × число рёбер × размер множества) в худшем случае, на практике 2–3 итерации.

def uses(i):
    """Какие значения читает инструкция (у call первый аргумент — имя функции)."""
    if i.op == "call":  return [a for a in i.args[1:] if isinstance(a, str)]
    if i.op in ("const", "param"):  return []
    return [a for a in i.args if isinstance(a, str)]

def liveness(fn):
    succ = {b.label: list(b.term.labels) for b in fn.blocks}
    lin  = {b.label: set() for b in fn.blocks}
    lout = {b.label: set() for b in fn.blocks}
    dirty = True
    while dirty:                                   # итерируем до неподвижной точки
        dirty = False
        for b in reversed(fn.blocks):              # обратный порядок — быстрее сходимость
            out = set().union(*[lin[s] for s in succ[b.label]]) if succ[b.label] else set()
            live = set(out)
            for ins in [b.term] + list(reversed(b.instrs)):
                if ins.dst: live.discard(ins.dst)  # определение убивает живость
                live |= set(uses(ins))             # использование рождает
            if live != lin[b.label] or out != lout[b.label]:
                lin[b.label], lout[b.label] = live, out
                dirty = True
    return lin, lout

Шаг 2а: граф интерференции и раскраска

Классический подход Чейтина (1981). Строим граф интерференции: вершины — значения, ребро между двумя значениями, если они одновременно живы. Назначить регистры = раскрасить граф в k цветов, где соседи имеют разные цвета. Это та самая раскраска из теории графов, и она NP-полна — Чейтин же и доказал, что задача распределения регистров NP-полна, сведя к ней раскраску произвольного графа.

Спасает эвристика Кемпе: вершина степени меньше k всегда раскрашиваема — как бы ни покрасили соседей, свободный цвет останется. Отсюда алгоритм Чейтина — Бриггса:

Два шага заслуживают отдельного слова.

Coalescing (слияние) — то место, где исчезают копии. Если есть b = copy a и a с b не интерферируют, их можно слить в одну вершину: оба получат один регистр, копия испарится. Ровно сюда попадают копии, оставшиеся после выхода из SSA — φ-функция подсказывает аллокатору, какие значения хотят жить вместе. Слияние технически делается через систему непересекающихся множеств. Опасность: агрессивное слияние повышает степень вершин и провоцирует вытеснение. Бриггс предложил сливать, только если у слитой вершины меньше k соседей высокой степени, — это и есть «консервативное слияние».

Выбор жертвы вытеснения. Метрика Чейтина: стоимость = (число обращений, взвешенное по вложенности цикла) делить на степень вершины. Значение внутри тройного цикла получает вес 10³ и не вытесняется почти никогда; значение, использованное один раз в стороне от горячего пути, уходит в память первым. Плохой выбор здесь дороже любой другой ошибки бэкенда.

Отдельный красивый факт: если IR в SSA-форме, граф интерференции хордальный, а хордальные графы раскрашиваются жадно за полиномиальное время. NP-полнота никуда не делась — она переехала в вытеснение и слияние, — но сама раскраска становится простой. На этом построены аллокаторы Хака и Бушакова и подход в современных SSA-бэкендах.

Шаг 2б: linear scan

Раскраска графа стоит O(n²) памяти под матрицу смежности и заметного времени — для JIT это неприемлемо. Полетто и Саркар (1999) предложили радикальное упрощение: приблизить живость одним отрезком [начало, конец] в линейном порядке инструкций и раздавать регистры как в задаче о расписании — жадно, слева направо (см. жадные алгоритмы).

POOL = ["%rbx", "%r12", "%r13", "%r14", "%r15"]     # только callee-saved: переживают call

def linear_scan(iv, pool=POOL):
    order = sorted(iv.items(), key=lambda kv: (kv[1][0], kv[1][1]))   # по началу интервала
    free, active, loc, nsp = list(pool), [], {}, 0
    for v, (s, e) in order:
        keep = []
        for ae, av in active:                       # expire: чьи интервалы уже кончились
            if ae < s: free.append(loc[av])         # регистр возвращается в пул
            else:      keep.append((ae, av))
        active = keep
        if free:
            loc[v] = free.pop(0)
            active.append((e, v))
        else:
            active.sort()
            fe, fv = active[-1]                     # самый долгоживущий — кандидат в память
            if fe > e:                              # ему жить дольше => вытесняем его
                loc[v], nsp = loc[fv], nsp + 1
                loc[fv] = f"-{8 * nsp}(%rbp)"
                active.pop(); active.append((e, v))
            else:                                   # иначе в память уходит текущий
                nsp += 1
                loc[v] = f"-{8 * nsp}(%rbp)"
        active.sort()
    return loc, nsp

Сложность. Сортировка O(n log n), основной цикл O(n × k) при k регистрах, память O(n). Против O(n²)+ у раскраски — отсюда популярность в JIT. Цена — дырки: значение, живое только в начале и в конце функции, занимает регистр всё время между ними. Отсюда развитие идеи — linear scan с интервалами из нескольких отрезков (Виммер и Мёссенбёк, HotSpot C1) и «second-chance binpacking».

Что ломает наивный аллокатор

• Значение, живое через вызов. В caller-saved регистре его уничтожит любой call. Либо класть в callee-saved (плата — сохранение в прологе), либо спасать вокруг каждого вызова (плата — две инструкции на вызов). Наш генератор выбирает первое и потому обходится без спасательных операций.
• Инструкции с фиксированными регистрами. idiv требует делимое в rdx:rax и портит rdx, сдвиг на переменную величину — счётчик в cl. Такие «предраскрашенные» вершины аллокатор обязан знать заранее, иначе выданный код просто неверен.
• Регистровые классы. Целые и вещественные значения живут в разных файлах регистров; раскраска ведётся по классам, а перенос между ними требует отдельной инструкции.
• Циклы в линейном порядке. Отрезок, посчитанный только по позициям использований, не учитывает обратное ребро. Лечится тем, что интервал накрывает весь блок, если значение есть в live_in/live_out блока, — ровно так сделано в коде ниже.

ABI: правила, по которым код разговаривает с чужим кодом

ABI (application binary interface) — договор об уровне машинного кода: где лежат аргументы, где результат, кто сохраняет регистры, как выровнен стек, как раскладываются структуры, как кодируются имена в объектных файлах. API описывает, как вызвать функцию из исходника; ABI — как вызвать её, когда исходника уже нет. Это не вопрос вкуса: вашу функцию вызывают libc, системный колбэк и код, собранный другим компилятором пять лет назад, а ошибка в ABI даёт не сообщение об ошибке, а падение в чужой библиотеке через тысячу инструкций.

Ключевые пункты System V AMD64 psABI — того договора, который действует в Linux, macOS и BSD:

• Целочисленные аргументы: rdi, rsi, rdx, rcx, r8, r9; вещественные — xmm0–xmm7; остальные на стеке, справа налево. Возврат: rax (пара rax:rdx для 128 бит), xmm0 для вещественных.
• Callee-saved: rbx, rbp, r12–r15. Всё остальное вызывающий обязан считать уничтоженным.
• Выравнивание: в момент выполнения call значение rsp кратно 16. Нарушить — получить падение в чужом коде на инструкции movaps, которой нужен выровненный адрес.
• Красная зона: 128 байт ниже rsp принадлежат функции и не будут затёрты прерыванием. Листовая функция пользуется ими вообще без изменения rsp. В коде ядра красной зоны нет — обработчик прерывания её затирает, поэтому ядро Linux собирают с -mno-red-zone.
• Классификация структур — самая недооценённая часть. Структура до 16 байт разбирается по полям на классы INTEGER/SSE и передаётся в регистрах по кусочкам; крупнее — копией через память, а адрес результата приходит скрытым нулевым аргументом в rdi. Отсюда неинтуитивное: struct {double x, y;} едет в двух xmm-регистрах, а struct {double x, y, z;} — через стек.
• Varargs: в al кладётся число векторных аргументов. Забыть — и printf с %f прочитает мусор.

Сравнение с двумя другими мирами — на схеме регистров выше: Microsoft x64 передаёт четыре аргумента в rcx, rdx, r8, r9, требует 32 байта shadow space и не знает красной зоны; AAPCS64 отдаёт под аргументы восемь регистров x0–x7, кладёт адрес возврата в x30 вместо стека и требует выравнивания sp постоянно, а не только в точке вызова. Один и тот же фронтенд, три разных бэкенда — вот почему кросс-компиляция это не только «другой набор инструкций».

Поверх ABI лежат ещё два слоя договорённостей: кодирование имён (в C имя как есть, в C++ — манглирование с типами, откуда _ZN3foo3barEi) и модель кода — как адресуются глобальные объекты. Позиционно-независимый код (PIE, обязательный по умолчанию в современных дистрибутивах) требует обращений вида foo(%rip) и вызовов через PLT; ровно из-за него r11 считается испорченным после вызова через динамический компоновщик.

Пролог, эпилог и раскрутка стека

Пролог решает три задачи: связать кадры (push %rbp; mov %rsp, %rbp), выделить место (sub), сохранить занятые callee-saved регистры. Эпилог делает обратное; leave — сокращение для mov %rbp, %rsp; pop %rbp.

Указатель кадра rbp формально не обязателен: смещения можно считать от rsp, и -fomit-frame-pointer освобождает целый регистр. Плата — раскрутка стека перестаёт работать простым проходом по цепочке rbp, и компилятор вынужден писать метаданные: директивы .cfi_startproc, .cfi_def_cfa_offset и прочие превращаются в секцию .eh_frame формата DWARF CFI, по которой отладчик, профайлер и механизм исключений C++ восстанавливают кадры (эти строки видны в выводе любого gcc -S). Показательно, что Fedora и Ubuntu вернули frame pointer по умолчанию в 2023–2024 годах: раскрутка по DWARF слишком дорога для сэмплирующего профайлера, и наблюдаемость в проде оказалась дороже одного регистра.

Работающий кусок: генератор x86-64 для Mini

Собираем всё вместе. Вход — линейное IR из статьи 06 после выхода из SSA (классы Instr, Block, Func берём оттуда без изменений). Выход — ассемблер AT&T, который понимает системный as.

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

def linearize(fn):
    """Сквозная нумерация инструкций; span[label] = (первая, последняя)."""
    seq, span = [], {}
    for b in fn.blocks:
        start = len(seq)
        seq.extend(b.instrs); seq.append(b.term)
        span[b.label] = (start, len(seq) - 1)
    return seq, span

def intervals(fn):
    seq, span = linearize(fn)
    lin, lout = liveness(fn)
    iv = {}
    def cover(v, p):
        iv[v] = (min(iv[v][0], p), max(iv[v][1], p)) if v in iv else (p, p)
    for b in fn.blocks:
        s, e = span[b.label]
        for v in lin[b.label]:  cover(v, s)     # живо на входе — интервал тянется от начала блока
        for v in lout[b.label]: cover(v, e)     # живо на выходе — до конца; так учитываются циклы
        for p in range(s, e + 1):
            if seq[p].dst: cover(seq[p].dst, p)
            for v in uses(seq[p]): cover(v, p)
    return iv

Теперь эмиссия. Стратегия сознательно простая — макроразвёртка через %rax как рабочий регистр: он никогда не выдаётся аллокатором, поэтому всегда свободен, а операнд-источник может быть и регистром, и ячейкой кадра, и константой — x86-64 это позволяет.

ARGS = ["%rdi", "%rsi", "%rdx", "%rcx", "%r8", "%r9"]     # System V, целочисленные
CC   = {"<": "l", "<=": "le", ">": "g", ">=": "ge", "==": "e", "!=": "ne"}
ALU  = {"+": "addq", "-": "subq", "*": "imulq"}

class Emitter:
    def __init__(self, fn, pool=POOL):
        self.fn = fn
        self.loc, self.nsp = linear_scan(intervals(fn), pool)
        used = {l for l in self.loc.values() if l.startswith("%")}
        self.saved = [r for r in pool if r in used]       # сохраняем только реально занятые
        need = 8 * (self.nsp + len(self.saved))
        self.frame = (need + 15) // 16 * 16               # кадр кратен 16 — требование ABI
        self.out = []

    def op(self, v):                                      # операнд: константа, регистр или слот
        return f"${v}" if isinstance(v, int) else self.loc[v]

    def e(self, s): self.out.append("        " + s)

    def gen(self):
        f, base = self.fn, 8 * self.nsp                   # слоты вытеснения идут первыми
        self.out += [f"        .globl {f.name}", f"        .type  {f.name}, @function", f"{f.name}:"]
        self.e("pushq %rbp"); self.e("movq  %rsp, %rbp")
        if self.frame: self.e(f"subq  ${self.frame}, %rsp")
        for k, r in enumerate(self.saved):
            self.e(f"movq  {r}, -{base + 8 * (k + 1)}(%rbp)")
        for b in f.blocks:
            self.out.append(f".L{f.name}_{b.label}:")
            for i in b.instrs: self.instr(i)
            self.term(b.term)
        self.out.append(f".L{f.name}_epilogue:")          # единая точка выхода на функцию
        for k, r in enumerate(self.saved):
            self.e(f"movq  -{base + 8 * (k + 1)}(%rbp), {r}")
        self.e("leave"); self.e("ret")
        return "\n".join(self.out)

    def instr(self, i):
        if i.dst is None: return
        d, a = self.op(i.dst), lambda k: self.op(i.args[k])
        if i.op == "param":   self.e(f"movq  {ARGS[i.args[0]]}, {d}")   # аргумент в фиксированном регистре
        elif i.op == "const": self.e(f"movq  ${i.args[0]}, {d}")
        elif i.op == "copy":  self.e(f"movq  {a(0)}, %rax"); self.e(f"movq  %rax, {d}")
        elif i.op in ALU:                                 # двухадресная форма: сначала копия в rax
            self.e(f"movq  {a(0)}, %rax"); self.e(f"{ALU[i.op]} {a(1)}, %rax")
            self.e(f"movq  %rax, {d}")
        elif i.op == "/":                                 # idiv: делимое в rdx:rax, cqto расширяет знак
            self.e(f"movq  {a(0)}, %rax"); self.e("cqto")
            self.e(f"idivq {a(1)}"); self.e(f"movq  %rax, {d}")
        elif i.op in CC:                                  # сравнение -> флаги -> setcc -> 0/1
            self.e(f"movq  {a(0)}, %rax"); self.e(f"cmpq  {a(1)}, %rax")
            self.e(f"set{CC[i.op]} %al"); self.e("movzbq %al, %rax")
            self.e(f"movq  %rax, {d}")
        elif i.op == "call":
            for k, x in enumerate(i.args[1:]):            # аргументы раскладываются строго по ABI
                self.e(f"movq  {self.op(x)}, {ARGS[k]}")
            self.e(f"call  {i.args[0]}"); self.e(f"movq  %rax, {d}")   # результат всегда в rax
        else: raise NotImplementedError(i.op)

    def term(self, t):
        n = self.fn.name
        if t.op == "jmp":  self.e(f"jmp   .L{n}_{t.labels[0]}")
        elif t.op == "br":
            self.e(f"cmpq  $0, {self.op(t.args[0])}")
            self.e(f"jne   .L{n}_{t.labels[0]}"); self.e(f"jmp   .L{n}_{t.labels[1]}")
        elif t.op == "ret":
            self.e(f"movq  {self.op(t.args[0])}, %rax"); self.e(f"jmp   .L{n}_epilogue")

Скармливаем ему IR функции sum(n) — той самой, что была примером в статье про IR: s = 0; i = 0; while (i < n) { s = s + i; i = i + 1; } return s;. Аллокатор выдаёт n → %rbx, s → %r12, i → %r13, временные переиспользуют %r14 и %r15, вытеснений нет, кадр 48 байт. Заголовок цикла выглядит так:

.Lmini_sum_head:
        movq  %r13, %rax
        cmpq  %rbx, %rax        # i < n
        setl %al
        movzbq %al, %rax        # условие материализовалось в значение — вот цена простоты
        movq  %rax, %r14
        cmpq  $0, %r14
        jne   .Lmini_sum_body
        jmp   .Lmini_sum_exit

Собираем и проверяем — вызов из обычной программы на C, без обёрток, потому что ABI соблюдён:

python3 codegen.py > mini.s          # генератор дописывает .text и .note.GNU-stack
cat > drv.c <<'EOF'
#include <stdio.h>
long mini_sum(long n);
int main(void) { printf("%ld\n", mini_sum(1000)); return 0; }
EOF
gcc -o demo drv.c mini.s && ./demo    # 499500

Работает — и то же самое с рекурсией: генератор для fib(n) даёт корректные fib(30) = 832040, а если искусственно сузить пул до двух регистров (pool=["%rbx", "%r12"]), появляются два слота вытеснения, n переезжает в -8(%rbp) — и результат остаётся правильным. Это лучший тест для аллокатора: правильный код при любом размере пула.

Теперь честно про качество. Вот что для того же цикла делает gcc -O1:

.L3:
        addq  %rax, %rdx      ; s += i
        addq  $1, %rax        ; i += 1
        cmpq  %rax, %rdi
        jne   .L3

Четыре инструкции на итерацию против наших двадцати. Разница не в том, что «gcc умнее», а в трёх конкретных приёмах, каждый из которых разобран выше: сравнение не материализуется в значение (переход идёт прямо по флагам), копии слиты аллокатором (coalescing), а регистры взяты caller-saved — функция листовая, вызовов нет, пролог не нужен вовсе. Ветвление по флагам и слияние копий — упражнение строк на сорок, и разрыв сокращается в разы.

Сложность конвейера. Живость — O(итераций × рёбер), на практике линейна; интервалы — O(n); linear scan — O(n log n); эмиссия — O(n); память — O(n). Весь бэкенд линеен по размеру функции, и это не случайность: именно поэтому квадратичные проходы включают только на высоких уровнях оптимизации.

Планирование инструкций: коротко о том, что мы пропустили

Между выбором инструкций и распределением регистров есть ещё одна задача — упорядочить инструкции так, чтобы конвейер не простаивал: загрузка из памяти имеет задержку в несколько тактов, и перестановка независимых инструкций между определением и использованием её скрывает. Классический алгоритм — list scheduling: строим граф зависимостей внутри базового блока и на каждом такте берём готовую инструкцию с самым длинным критическим путём; оптимальное планирование блока NP-трудно, жадный список даёт приличный результат за O(n²). Насколько это важно, зависит от процессора: на внеочередных x86-64 и Apple Silicon аппаратура сама переставляет инструкции в окне на сотни микроопераций, а на упорядоченных ядрах (Cortex-M, DSP, VLIW) весь параллелизм обязан найти компилятор — там планирование и программная конвейеризация циклов (modulo scheduling) дают кратный выигрыш.

Типичные ошибки

• Выравнивание стека забыли. Кадр не кратен 16 — падение не у вас, а внутри printf на векторной инструкции. Проверяется трассировкой rsp в точке call.
• Значение живёт через вызов в caller-saved регистре. Мусор после call, воспроизводится через раз. Лечится пулом из callee-saved или честным учётом «пересекает вызов» в интервалах.
• Забыли, что idiv портит rdx. Любая инструкция с неявными операндами должна быть отражена в модели аллокатора, иначе значение из rdx тихо исчезает после деления.
• Интервал не накрывает обратное ребро цикла. Значение считается мёртвым внутри цикла, его регистр отдают другому — и цикл работает с чужими данными.
• Метки без префикса функции. Два блока head в разных функциях дают дублирующиеся символы; локальные метки обязаны начинаться с .L, иначе попадут в таблицу символов.
• Пролог сгенерирован до аллокации. Размер кадра ещё неизвестен: либо переписывать уже выданный текст, либо резервировать «с запасом».

Как это устроено в промышленных компиляторах

• LLVM. IR → SelectionDAG (покрытие плитками с ДП по описаниям TableGen) → MachineIR → распределение регистров (greedy — потомок linear scan с расщеплением интервалов, есть и PBQP) → эмиссия через MC-слой прямо в объектный файл. Новый путь — GlobalISel, быстрее и работает за пределами базового блока.
• GCC. GIMPLE → RTL → распределение регистров IRA/LRA → вывод ассемблера для as. RTL-паттерны в файлах .md — прямой аналог плиток.
• Go. Свой SSA-бэкенд с декларативными правилами перезаписи и быстрым аллокатором: приоритет отдан скорости компиляции, а не последним процентам производительности.
• Cranelift (Wasmtime) с аллокатором regalloc2 и QBE — несколько тысяч строк C — оба спроектированы под быструю компиляцию и достаточно компактны, чтобы прочитать их целиком.

Практический совет, который окупается за вечер: откройте godbolt.org, включите -O2 и посмотрите, во что превращаются знакомые конструкции. Это единственный способ перестать гадать, «оптимизирует ли компилятор вот это».

Мини-итог

• Бэкенд решает три сцепленные задачи — выбор инструкций, планирование, распределение регистров; оптимально их не решить, порядок фаз всегда компромисс.
• Выбор инструкций — покрытие дерева плитками: макроразвёртка проста и плоха, maximal munch неплох, ДП оптимально на деревьях. Разрыв виден глазами: три инструкции IR против одной lea.
• Распределение регистров = раскраска графа интерференции, задача NP-полная. Практика — Чейтин — Бриггс с консервативным слиянием или linear scan там, где важна скорость компиляции; в SSA граф хордальный и раскраска становится полиномиальной.
• Живость считается обратным анализом потока данных, и интервал обязан накрывать циклы — иначе аллокатор выдаёт правдоподобный, но неверный код.
• ABI — договор, а не рекомендация: регистры аргументов, callee-saved, выравнивание на 16 байт, красная зона, классификация структур. Нарушения проявляются далеко от места ошибки.
• Пролог и эпилог генерируются последними: размер кадра известен только после аллокации.
• Полтораста строк Python дают ассемблер, который собирается системным as и вызывается из C; разрыв с gcc -O2 объясняется конкретными пропущенными приёмами, а не магией.

Что почитать

• Cooper, Torczon, Engineering a Compiler, главы 11–13 — лучший современный разбор выбора инструкций, планирования и раскраски; Aho, Lam, Sethi, Ullman, Compilers — те же темы в главах 8–9 канонически.
• Gregory Chaitin, «Register Allocation and Spilling via Graph Coloring», 1982 — статья, с которой всё началось, и Preston Briggs et al., «Improvements to Graph Coloring Register Allocation», TOPLAS 1994 — консервативное слияние и оптимистическое вытеснение.
• Poletto, Sarkar, «Linear Scan Register Allocation», TOPLAS 1999 — алгоритм, который мы реализовали; Wimmer, Mössenböck, «Optimized Interval Splitting…», VEE 2005 — его версия из HotSpot.
• Hack, Grund, Goos, «Register Allocation for Programs in SSA-Form», CC 2006 — хордальность и её последствия.
• System V AMD64 psABI — первоисточник; раздел о классификации аргументов стоит прочитать целиком. Для сравнения: ARM AAPCS64 и Microsoft x64 calling convention.
• Eli Bendersky, «Stack frame layout on x86-64» — разбор кадра с дизассемблером; LLVM Code Generator — устройство бэкенда, который вы, скорее всего, будете использовать вместо своего.
• Связанные статьи портала: как работает процессор и от кода к исполнению — что происходит с нашим ассемблером дальше; управление памятью — откуда берётся стек; теория графов — раскраска; жадные алгоритмы — основа linear scan; стратегии вычислений — порядок, который бэкенд обязан сохранить; императивная парадигма — модель машины, к которой мы всё сводим.

Что дальше

Мы получили машинный код для конкретной архитектуры — быстро, но непереносимо: каждая новая платформа требует нового бэкенда, а компиляция занимает время. Есть противоположный ответ на тот же вопрос «как исполнить IR»: не спускаться до железа, а придумать собственную машину — простую, одинаковую везде и достаточно быструю. Следующая статья разбирает виртуальные машины: чем стековая ВМ отличается от регистровой и почему JVM выбрала первую, а Lua и Dalvik — вторую, как устроен формат байткода, во что обходится цикл диспетчеризации и какие приёмы (computed goto, threaded code, суперинструкции) отыгрывают потерянную производительность.

Виртуальные машины: стековые и регистровые, байткод, интерпретация