Промежуточное представление: IR, SSA, зачем нужен средний слой

К этому месту трека у нас есть дерево, размеченное типами: лексер дал токены, парсер — AST, семантический анализ привязал каждое имя к объявлению, а проверка типов убедилась, что программа осмысленна. Фронтенд закончил работу. Программа корректна — осталось сделать её быстрой и исполнимой.

И вот здесь почти каждый серьёзный компилятор делает то, что новичку кажется расточительством: выбрасывает дерево. Не сразу и не полностью, но AST перестаёт быть рабочей структурой и уступает место другой форме — плоской, безымянной, некрасивой и невероятно удобной для анализа. Эта форма называется промежуточным представлением, IR.

Статья отвечает на три вопроса. Почему дерева недостаточно и что именно мешает. Как выглядит средний слой — трёхадресный код, базовые блоки, граф потока управления. И что такое SSA — форма, в которой держат IR все современные оптимизирующие компиляторы, от LLVM и GCC до Go, V8 и HotSpot. К концу мы напишем конвертер AST → IR → SSA → обратно, который реально работает на цикле из языка Mini.

Почему дерева недостаточно

Возьмём кусок Mini и три вопроса, которые задаёт любой оптимизатор.

let s = 0;
let i = 0;
while i < n {
  s = s + i;
  i = i + 1;
}
return s;

Вопрос первый: «откуда взялось значение i вот в этом сложении?» По AST это поиск: подняться к объемлющему блоку, посмотреть предыдущие инструкции, не забыть, что мы внутри цикла и предыдущая итерация тоже считается, учесть, что i может быть переприсвоено в теле if. Ответ — «из двух мест сразу», и AST его никак не выражает: у узла Var("i") нет ребра к определению. Информация есть, но она размазана по структуре и добывается обходом.

Вопрос второй: «выполнится ли это выражение хотя бы раз?» Тело while может не выполниться ни разу, тело if — выполниться или нет, return в середине блока обрывает всё, что ниже. В дереве порядок исполнения задан неявно: он вытекает из семантики каждого вида узла. Чтобы его узнать, надо интерпретировать дерево, а не читать его.

Вопрос третий: «можно ли переставить эти две операции местами?» Это вопрос о зависимостях по данным, и он предполагает, что операции вообще есть — атомарные, сравнимые, лежащие в линию. В дереве операции вложены друг в друга: s + i не «операция», а поддерево, которое где-то посередине выражения.

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

Вторая, независимая причина существования IR — та самая песочные часы M × N против M + N, о которой шла речь в обзоре трека: фронтенд знает язык, бэкенд знает платформу, встречаются они в общем IR, и оптимизации пишутся ровно один раз. Обе причины действуют вместе, но вторая — про архитектуру проекта, а первая — про то, почему без IR оптимизатор вообще не пишется.

Что называют промежуточным представлением

IR — это любое представление программы, которое не является ни исходником, ни целевым кодом. Классификаций три, и они ортогональны.

По уровню абстракции. Высокий IR (HIR) близок к языку: там ещё есть циклы, обобщения, типы исходника. Средний (MIR) — плоские операции и явный граф переходов, машины ещё нет. Низкий (LIR) — почти ассемблер: конкретные регистры, флаги, режимы адресации. Крупные компиляторы держат все три и спускаются по лестнице.

По форме. Древовидные (GENERIC в GCC, «дерево выражений» в .NET), линейные (трёхадресный код, байткод), графовые (sea of nodes в HotSpot C2). Линейные проще печатать и отлаживать, графовые точнее выражают зависимости — и хуже читаются человеком.

По свойствам. Ключевое свойство — SSA или не SSA, про него вся вторая половина статьи. Дополнительно: типизированный или нет, есть ли явная память, разрешён ли произвольный поток управления.

Что используют в реальности:

Обратите внимание на Java и V8: их «компилятор» отдаёт наружу байткод — намеренно высокоуровневый IR, который переносим и компактен, а всерьёз оптимизируется уже во время выполнения, потому что тогда известны фактические типы. Это тема статьи про JIT.

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

Трёхадресный код: как выглядит средний слой

Каноническая форма среднего IR — трёхадресный код (three-address code, TAC). Каждая инструкция имеет вид

результат := операнд1 оператор операнд2

то есть максимум три «адреса»: два входа и один выход. Отсюда название. Ключевое свойство — операнды не могут быть выражениями, только имена и константы. Значит, вложенность исчезает, а любое сложное выражение разворачивается в цепочку простых с промежуточными переменными — временными (temporaries), которые компилятор порождает сам.

s = (a + b) * (c - d) превращается в

t1 = a + b
t2 = c - d
s  = t1 * t2

Три инструкции вместо одного дерева из пяти узлов. Что мы получили:

• Единица работы стала атомарной. «Переставить местами», «удалить», «заменить константой» теперь операции над элементом списка, а не над поддеревом.
• Промежуточные значения получили имена. t1 можно упомянуть в анализе, посчитать его использования, заметить, что такое же выражение уже вычислялось выше (это будет нумерация значений в статье про оптимизации).
• Порядок вычисления зафиксирован. В f() + g() дерево не говорит, кто вызывается первым (в C это неопределено, в Java — слева направо). В TAC порядок уже выбран и записан, дальше все проходы видят один и тот же порядок.

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

Исторически TAC записывали тремя способами: квадруплы (op, arg1, arg2, result — то, что мы делаем ниже), триплы (без поля результата: на инструкцию ссылаются по её номеру) и косвенные триплы (список указателей на триплы, чтобы дешевле переставлять). В современных компиляторах победил вариант, где сама инструкция и есть значение: в LLVM %3 = add i32 %1, %2 — не «инструкция, пишущая в переменную %3», а значение с именем %3. Это уже почти SSA, к которой мы идём.

Лоуэринг Mini в TAC

Пишем на Python. Узлы AST берём из статьи 02, к языку добавляем две вещи, которые нужны, чтобы граф получился интересным: присваивание существующей переменной и цикл while — одно правило грамматики и один метод парсера.

from dataclasses import dataclass, field
from typing import Optional

# ---------- AST (сокращённо, из статьи 02) ----------
@dataclass
class Num: value: int
@dataclass
class Var: name: str
@dataclass
class Binary: op: str; left: object; right: object
@dataclass
class Call: callee: str; args: list
@dataclass
class Let: name: str; init: object
@dataclass
class Assign: name: str; value: object
@dataclass
class If: cond: object; then: list; els: list
@dataclass
class While: cond: object; body: list
@dataclass
class Return: value: object

# ---------- IR ----------
@dataclass
class Instr:
    op: str                          # const | copy | phi | + | < | call | jmp | br | ret ...
    args: tuple = ()                 # операнды-значения
    dst: Optional[str] = None        # куда пишем (None у терминаторов)
    labels: tuple = ()               # метки-приёмники, только у jmp/br
    var: Optional[str] = None        # исходная переменная, только у phi
    def __str__(self):
        a = ", ".join(str(x) for x in self.args + self.labels)
        return f"  {self.dst} = {self.op} {a}" if self.dst else f"  {self.op} {a}"

@dataclass
class Block:
    label: str
    instrs: list = field(default_factory=list)
    term: Optional[Instr] = None     # ровно один терминатор в конце

@dataclass
class Func:
    name: str
    params: list
    blocks: list = field(default_factory=list)

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

Теперь строитель. Он держит указатель на текущий блок и умеет две вещи: снижать выражение (возвращая имя значения) и снижать инструкцию (порождая инструкции и, возможно, новые блоки).

class Builder:
    def __init__(self):
        self.blocks, self.cur, self.nt, self.nb = [], None, 0, 0

    def new_block(self, hint="bb"):
        self.nb += 1
        b = Block(f"{hint}{self.nb}")
        self.blocks.append(b)
        return b

    def temp(self):                                  # свежее имя временного значения
        self.nt += 1
        return f"%{self.nt}"

    def emit(self, op, *args, dst=None):
        self.cur.instrs.append(Instr(op, args, dst))
        return dst

    def term(self, op, *args, labels=()):
        if self.cur.term is None:                    # первый терминатор побеждает:
            self.cur.term = Instr(op, args, labels=labels)   # код после return недостижим

    def expr(self, e):
        """Возвращает ИМЯ значения, в котором лежит результат выражения."""
        match e:
            case Num(value=v):
                return self.emit("const", v, dst=self.temp())
            case Var(name=n):
                return n                             # переменная — уже имя, инструкция не нужна
            case Binary(op=o, left=l, right=r):
                a, b = self.expr(l), self.expr(r)    # порядок вычисления фиксируем здесь
                return self.emit(o, a, b, dst=self.temp())
            case Call(callee=f, args=xs):
                vals = [self.expr(a) for a in xs]
                return self.emit("call", f, *vals, dst=self.temp())
        raise TypeError(e)

Снижение инструкций — то место, где структурный поток управления превращается в графовый. if порождает три блока, while — тоже три, и оба заканчиваются тем, что «текущим» становится блок продолжения.

    def stmt(self, s):
        match s:
            case Let(name=n, init=e) | Assign(name=n, value=e):
                self.emit("copy", self.expr(e), dst=n)
            case Return(value=e):
                self.term("ret", self.expr(e))
            case If(cond=c, then=t, els=f):
                cv = self.expr(c)
                bt, bf, bj = self.new_block("then"), self.new_block("else"), self.new_block("join")
                self.term("br", cv, labels=(bt.label, bf.label))
                self.cur = bt
                for x in t: self.stmt(x)
                self.term("jmp", labels=(bj.label,))
                self.cur = bf
                for x in f: self.stmt(x)
                self.term("jmp", labels=(bj.label,))
                self.cur = bj
            case While(cond=c, body=body):
                bh, bb, bx = self.new_block("head"), self.new_block("body"), self.new_block("exit")
                self.term("jmp", labels=(bh.label,))      # вход в цикл — отдельный переход
                self.cur = bh
                cv = self.expr(c)                         # условие вычисляется в заголовке,
                self.term("br", cv, labels=(bb.label, bx.label))   # т.е. на каждой итерации
                self.cur = bb
                for x in body: self.stmt(x)
                self.term("jmp", labels=(bh.label,))      # обратное ребро
                self.cur = bx
            case _:
                raise TypeError(s)

def lower(name, params, body):
    b = Builder()
    b.cur = b.new_block("entry")
    for i, p in enumerate(params):
        b.emit("param", i, dst=p)                    # параметры — обычные определения во входном блоке
    for s in body:
        b.stmt(s)
    b.term("ret", 0)                                 # неявный возврат, если управление дошло до конца
    return Func(name, params, b.blocks)

Сложность. Один проход по дереву: O(n) по времени, где n — число узлов AST. Память — O(n) на инструкции плюс O(глубины дерева) на стек рекурсии. Число порождённых временных ровно равно числу внутренних узлов выражений, то есть IR систематически больше исходника в 2–4 раза. Это нормально и это плата за плоскость.

Отдельно отметьте, что while не превратился в «инструкцию цикла». Циклов в IR больше нет — есть блоки и переходы, а цикл придётся распознавать заново анализом графа (обратные рёбра, о них ниже). Кажется потерей — но именно благодаря этому оптимизатору всё равно, откуда взялся цикл: из while, из for, из рекурсии после хвостового вызова или из goto.

Базовые блоки и граф потока управления

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

Граф потока управления (CFG, control flow graph) — ориентированный граф, где вершины это базовые блоки, а рёбра — возможные переходы. Это обычный граф со всеми вытекающими: обходы, достижимость, компоненты сильной связности, доминаторы — весь аппарат из теории графов и обходов графов применяется как есть.

Наш строитель создаёт блоки сразу, но если IR приходит извне плоским списком (например, из байткода), блоки выделяют классическим алгоритмом лидеров:

ЛИДЕРЫ:
  1. первая инструкция функции — лидер
  2. цель любого перехода — лидер
  3. инструкция сразу после перехода — лидер
БЛОКИ: от каждого лидера до следующего лидера (не включая)

Два прохода по списку, O(n) времени и O(числа блоков) памяти. Дальше рёбра ставятся по терминаторам.

def succs(blk):
    return list(blk.term.labels) if blk.term else []

def cfg(fn):
    """Строит списки предшественников и удаляет недостижимые блоки."""
    by = {b.label: b for b in fn.blocks}
    entry = fn.blocks[0].label
    seen, stack = {entry}, [entry]
    while stack:                                     # обход в глубину от входа
        l = stack.pop()
        for s in succs(by[l]):
            if s not in seen:
                seen.add(s); stack.append(s)
    fn.blocks = [b for b in fn.blocks if b.label in seen]   # unreachable code elimination
    preds = {b.label: [] for b in fn.blocks}
    for b in fn.blocks:
        for s in succs(b):
            preds[s].append(b.label)
    return preds

def dump(fn):                                        # текстовый формат IR — не роскошь, а инструмент отладки
    out = [f"func {fn.name}({', '.join(fn.params)}):"]
    for b in fn.blocks:
        out.append(f"{b.label}:")
        out += [str(i) for i in b.instrs]
        if b.term: out.append(str(b.term))
    return "\n".join(out)

Заметьте побочный эффект: первая оптимизация досталась бесплатно. Блок join, стоящий после if, обе ветки которого заканчиваются return, просто не попадёт в список достижимых. Это удаление недостижимого кода, и оно здесь не «оптимизация», а следствие того, что мы вообще построили граф. O(V + E) по времени.

Вот CFG для нашего цикла — ровно то, что печатает код выше:

Терминология, которая дальше используется постоянно:

• Обратное ребро — ребро u → v, где v доминирует u (определение доминирования — в следующем разделе). Наличие обратного ребра и есть формальное определение цикла в CFG.
• Заголовок цикла — цель обратного ребра, здесь head2. Это точка, где сходятся вход в цикл и возврат с предыдущей итерации.
• Критическое ребро — ребро из блока с несколькими преемниками в блок с несколькими предшественниками. На таком ребре некуда положить код, и оно ломает выход из SSA; лечится вставкой пустого блока («расщепление критических рёбер»).
• Инварианты IR: у каждого блока ровно один терминатор и он последний; все метки существуют; каждое использование значения имеет определение. Эти проверки стоит написать сразу — в LLVM они называются -verify, и они ловят 90% ошибок в новых проходах. Компилятор, падающий с внятным «нарушен инвариант IR в проходе X», отлаживается на порядок быстрее компилятора, падающего сегфолтом в кодогенераторе.

Одно имя — много определений: зачем нужна SSA

Посмотрите на дамп нашего IR до всяких преобразований (это буквально вывод программы, которую мы пишем):

func sum_to(n):
entry1:
  n = param 0
  %1 = const 0
  s = copy %1
  %2 = const 0
  i = copy %2
  jmp head2
head2:
  %3 = < i, n
  br %3, body3, exit4
body3:
  %4 = + s, i
  s = copy %4
  %5 = const 1
  %6 = + i, %5
  i = copy %6
  jmp head2
exit4:
  ret s

Временные значения %1…%6 определены ровно один раз каждое — с ними легко: увидел %4, сразу знаешь, что это s + i. А вот i определена дважды, и s дважды. И теперь простой вопрос: в инструкции %3 = < i, n какое i имеется в виду? Ответ — «зависит от того, откуда мы пришли в блок», то есть зависит от исполнения, а не от текста. Любой анализ, который хочет знать, что такое i, обязан таскать с собой отображение «переменная → множество возможных определений» и обновлять его в каждой точке программы. Это и есть классический анализ достигающих определений: дорого, громоздко, переписывается в каждом проходе.

SSA (static single assignment, статическая форма одиночного присваивания) — это IR, в котором каждое имя значения определяется ровно один раз в тексте программы. Слово «статическая» существенно: динамически инструкция в цикле выполняется много раз, но место её определения в коде одно.

Что это даёт немедленно:

• Вопрос «откуда пришло значение» перестаёт быть анализом и становится чтением: у имени ровно одно определение, и указатель на него можно хранить прямо в операнде.
• Появляются def-use цепочки за O(1): у каждого значения список его использований, у каждого использования — ссылка на определение. Именно так устроен llvm::Value с его списком Use.
• Отпадает переиспользование имён: x в одной ветке и x в другой — это разные значения, и никакой анализ их не спутает.
• Многие оптимизации становятся почти тривиальными. Распространение констант: если определение это const 5, замени все использования на 5 — и всё, никакого обхода в поисках «а не переприсвоили ли по дороге». Удаление мёртвого кода: у значения пустой список использований и нет побочных эффектов — удаляй.

Остаётся проблема, ради которой SSA и знаменита. Что написать в head2, куда i приходит двумя разными путями — как i.1 из входа и как i.3 с предыдущей итерации?

φ-функция

Ответ: специальная псевдоинструкция φ (фи), которая означает «выбери значение в зависимости от того, из какого предшественника мы пришли».

head2:
  i.2 = phi i.1, i.3        ; i.1 если пришли из entry1, i.3 если из body3

Три свойства φ, которые надо усвоить сразу, иначе будет больно:

1. φ — не настоящая инструкция. У процессора нет команды «посмотри, откуда пришло управление». φ — это нотация для места слияния; в реальный код она превращается копиями при выходе из SSA.
2. Все φ блока выполняются одновременно, атомарно, в самом начале блока, до любых обычных инструкций. Это важно, когда φ ссылаются друг на друга: a.2 = phi a.1, b.3 и b.2 = phi b.1, a.3 в заголовке цикла означают обмен значениями, а не последовательное присваивание.
3. Аргументы φ позиционные и соответствуют списку предшественников. Порядок предшественников — часть контракта IR; если проход переставляет рёбра, он обязан переставить и аргументы всех φ. Забытая синхронизация — источник самых загадочных багов в компиляторах.

Наивный способ построить SSA — поставить φ в каждом блоке для каждой переменной. Работать будет, но φ окажется столько, что оптимизатор захлебнётся. Задача «поставить φ ровно там, где нужно» решается через доминаторы.

Доминаторы: фундамент SSA

Пусть в CFG есть выделенный вход. Тогда:

• Блок d доминирует блок n (пишут d dom n), если любой путь от входа к n проходит через d. Доминирование рефлексивно: каждый блок доминирует сам себя.
• Строгое доминирование (sdom) — то же самое, но d ≠ n.
• Непосредственный доминатор idom(n) — ближайший строгий доминатор n; он единственный, и это ключевая теорема. Из неё следует, что отношение непосредственного доминирования образует дерево доминаторов с корнем во входном блоке.

Интуиция: d dom n означает «код в d гарантированно выполнился к моменту входа в n». Поэтому доминирование — это ровно то отношение, которое отвечает на вопрос «можно ли здесь пользоваться результатом, посчитанным там». В SSA есть жёсткое правило корректности: определение обязано доминировать все свои использования (единственное исключение — аргументы φ, которые «используются» в конце соответствующего предшественника).

Доминаторы считаются как задача о потоке данных — это неподвижная точка системы уравнений:

Dom(вход) = { вход }
Dom(n)    = { n } ∪ ( ∩ Dom(p) по всем p из pred(n) )

Читается прямо: доминаторы блока — он сам плюс то, что доминирует все входы в него. Пересечение, а не объединение, потому что путь может прийти по любому ребру.

def dominators(fn, preds):
    labels = [b.label for b in fn.blocks]
    entry = labels[0]
    dom = {l: set(labels) for l in labels}           # старт: «доминируют все», кроме входа
    dom[entry] = {entry}
    changed = True
    while changed:                                   # итерируем до неподвижной точки
        changed = False
        for l in labels:
            if l == entry: continue
            ps = preds[l]
            new = set.intersection(*(dom[p] for p in ps)) if ps else set()
            new.add(l)
            if new != dom[l]:
                dom[l] = new; changed = True
    idom = {}
    for l in labels:                                 # непосредственный доминатор — самый «глубокий»
        if l == entry: continue                      # из строгих, т.е. с наибольшим Dom
        idom[l] = max(dom[l] - {l}, key=lambda d: len(dom[d]))
    return dom, idom

Сложность. Наивно — O(V²·E) в худшем случае на операциях с множествами; при обходе блоков в обратном постпорядке (reverse postorder) число итераций внешнего цикла на реальных графах равно 2–3, а с битовыми множествами каждая итерация стоит O(V·E / w). Именно так это делают в GCC. Существует алгоритм Ленгауэра–Тарьяна со сложностью почти линейной, O(E·α(E, V)) — оригинальная статья 1979 года; а для практики Купер, Харви и Кеннеди показали, что аккуратный итеративный алгоритм с представлением дерева массивом idom обгоняет Ленгауэра–Тарьяна на графах реальных программ — «A Simple, Fast Dominance Algorithm», их вариант стоит в LLVM.

Фронт доминирования

Теперь центральное определение всей конструкции.

Фронт доминирования DF(n) — множество блоков m, таких что n доминирует хотя бы одного предшественника m, но не доминирует строго сам m:

DF(n) = { m | ∃ p ∈ pred(m): n dom p, и при этом НЕ (n sdom m) }

Словами: DF(n) — это блоки, где влияние n заканчивается; куда значение из n доходит по одному пути, но не по всем. Ровно там разные значения одной переменной впервые встречаются — и ровно там нужна φ.

Алгоритм Cytron и соавторов вычисляет фронты за один проход по узлам слияния: для каждого блока с двумя и более предшественниками идём от каждого предшественника вверх по дереву доминаторов до idom этого блока, добавляя блок в фронты всех, кого прошли.

def dom_frontier(fn, preds, idom):
    df = {b.label: set() for b in fn.blocks}
    for b in fn.blocks:
        if len(preds[b.label]) < 2: continue         # фронты рождаются только в точках слияния
        for p in preds[b.label]:
            runner = p
            while runner != idom.get(b.label):       # поднимаемся по дереву доминаторов
                df[runner].add(b.label)
                runner = idom.get(runner)
                if runner is None: break
    return df

Стоимость — O(суммарного размера всех фронтов); на типичных графах это близко к O(E), в патологических случаях (граф-«лестница» с множеством слияний) — O(V²).

Вставка φ и переименование

Построение SSA по Cytron состоит ровно из двух шагов, и оба у нас уже почти написаны.

Шаг 1: где ставить φ. Для каждой переменной v берём множество блоков, где v определяется, и вычисляем итерированный фронт доминирования: φ сама по себе является определением v, поэтому её появление в блоке может потребовать ещё φ где-то дальше. Итерируем до неподвижной точки.

def is_var(x):                                       # временные (%N) уже single-assignment
    return isinstance(x, str) and not x.startswith("%")

def insert_phis(fn, preds, df):
    by = {b.label: b for b in fn.blocks}
    defs = {}                                        # переменная -> блоки, где она определяется
    for b in fn.blocks:
        for i in b.instrs:
            if i.dst and is_var(i.dst):
                defs.setdefault(i.dst, set()).add(b.label)
    for v, sites in defs.items():
        work, has = list(sites), set()
        while work:
            x = work.pop()
            for y in df[x]:                          # фронт — кандидаты на phi
                if y in has: continue
                has.add(y)
                args = tuple(v for _ in preds[y])    # пока заглушки, заполним при переименовании
                by[y].instrs.insert(0, Instr("phi", args, dst=v, var=v))
                if y not in sites: work.append(y)    # phi сама себе определение -> итерируем
    return defs

Получается минимальная SSA: φ стоят везде, где сходятся два разных значения. Это ещё не оптимум — φ может оказаться в блоке, где переменная дальше вообще не используется («мёртвая» φ). Варианты, которые встречаются в реальных компиляторах:

Последняя строка заслуживает внимания: «Simple and Efficient Construction of Static Single Assignment Form» (CC 2013) показывает, как строить SSA «на лету», по запросу readVariable(v, block), вообще не вычисляя доминаторы. Так делают многие JIT-компиляторы, которым некогда считать фронты, и так устроен, например, Cranelift.

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

Почему именно дерево доминаторов, а не CFG? Потому что «текущая версия переменной в блоке n» — это версия, определённая в ближайшем доминаторе n. Стек, синхронный с обходом дерева, воспроизводит это точно.

def rename(fn, preds, idom, defs):
    by = {b.label: b for b in fn.blocks}
    children = {b.label: [] for b in fn.blocks}      # дерево доминаторов из idom
    for l, d in idom.items():
        children[d].append(l)
    counter = {v: 0 for v in defs}
    stack = {v: [] for v in defs}

    def fresh(v):
        counter[v] += 1
        n = f"{v}.{counter[v]}"
        stack[v].append(n)
        return n

    def top(v):
        return stack[v][-1] if stack.get(v) else v   # использование без определения — параметр/ошибка

    def walk(l):
        b, pushed = by[l], []
        for i in b.instrs:
            if i.op != "phi":                        # аргументы phi НЕ переименовываем здесь:
                i.args = tuple(top(a) if is_var(a) else a for a in i.args)   # они «живут» в предшественниках
            if i.dst and is_var(i.dst):
                base = i.dst
                i.dst = fresh(base); pushed.append(base)
        if b.term:
            b.term.args = tuple(top(a) if is_var(a) else a for a in b.term.args)
        for s in succs(b):                           # заполняем свой слот в phi у преемников
            j = preds[s].index(l)
            for i in by[s].instrs:
                if i.op == "phi":
                    a = list(i.args); a[j] = top(i.var); i.args = tuple(a)
        for c in children[l]:
            walk(c)
        for base in pushed:                          # выходим из поддерева — восстанавливаем стеки
            stack[base].pop()

    walk(fn.blocks[0].label)

Сложность всей конструкции SSA: O(V + E + |инструкции| + суммарный размер фронтов). Число φ на реальном коде растёт линейно, но в худшем случае квадратично по числу блоков — существуют графы, требующие Θ(V²) φ. Практическое следствие: компиляторы ставят предохранители и отказываются от агрессивных проходов на функциях с гигантским CFG (в LLVM это, например, пороги на число блоков в инлайнере).

Запускаем всё вместе на нашем цикле:

prog = [
    Let("s", Num(0)),
    Let("i", Num(0)),
    While(Binary("<", Var("i"), Var("n")), [
        Assign("s", Binary("+", Var("s"), Var("i"))),
        Assign("i", Binary("+", Var("i"), Num(1))),
    ]),
    Return(Var("s")),
]

fn = lower("sum_to", ["n"], prog)
preds = cfg(fn)
dom, idom = dominators(fn, preds)
df = dom_frontier(fn, preds, idom)
defs = insert_phis(fn, preds, df)
rename(fn, preds, idom, defs)

Промежуточные величины ровно те, что на схеме выше:

preds = {'entry1': [], 'head2': ['entry1', 'body3'], 'body3': ['head2'], 'exit4': ['head2']}
idom  = {'head2': 'entry1', 'body3': 'head2', 'exit4': 'head2'}
DF    = {'entry1': [], 'head2': ['head2'], 'body3': ['head2'], 'exit4': []}

DF(head2) = {head2} — заголовок цикла лежит в собственном фронте доминирования, и это не ошибка: цикл возвращается сам в себя, поэтому его заголовок всегда является точкой встречи значений. А результат:

func sum_to(n):
entry1:
  n.1 = param 0
  %1 = const 0
  s.1 = copy %1
  %2 = const 0
  i.1 = copy %2
  jmp head2
head2:
  i.2 = phi i.1, i.3          ; из entry1 либо из body3
  s.2 = phi s.1, s.3
  %3 = < i.2, n.1
  br %3, body3, exit4
body3:
  %4 = + s.2, i.2
  s.3 = copy %4
  %5 = const 1
  %6 = + i.2, %5
  i.3 = copy %6
  jmp head2
exit4:
  ret s.2

Каждое имя определено ровно один раз. Теперь любая оптимизация читает граф зависимостей напрямую: %3 зависит от i.2 и n.1, i.2 — это φ от i.1 и i.3, i.1 — константа 0. Отсюда, например, немедленно следует, что i неотрицательна, а n.1 инвариантна в цикле, — и это уже материал следующей статьи.

Выход из SSA

φ надо чем-то заменить, потому что процессор её не умеет. Базовая схема: φ в блоке B превращается в копии в конце каждого предшественника.

def out_of_ssa(fn, preds):
    by = {b.label: b for b in fn.blocks}
    for b in fn.blocks:
        phis = [i for i in b.instrs if i.op == "phi"]
        if not phis: continue
        b.instrs = [i for i in b.instrs if i.op != "phi"]
        for j, p in enumerate(preds[b.label]):
            for ph in phis:                          # копия ставится ПЕРЕД терминатором предшественника
                by[p].instrs.append(Instr("copy", (ph.args[j],), dst=ph.dst))

Результат для нашей функции: в entry1 появляются i.2 = copy i.1 и s.2 = copy s.1, в body3 — i.2 = copy i.3 и s.2 = copy s.3. Обратите внимание: SSA-свойство сломано намеренно, i.2 теперь определена дважды. Так и надо — SSA нужна была оптимизациям, а не машине.

Три ловушки, на которых спотыкаются все, кто пишет это в первый раз:

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

Потерянная копия (lost copy). Если после копирования из φ значение-источник ещё используется дальше, а регистр под него переиспользован, значение теряется. Возникает после агрессивного слияния копий.

Проблема обмена (swap). Из-за того, что φ выполняются параллельно, две φ вида a = phi(b, ...) и b = phi(a, ...) означают обмен. Последовательные копии a = b; b = a его не воспроизводят. Правильный выход — трактовать группу φ как параллельное копирование и разворачивать его алгоритмом, который при необходимости заводит временную (или использует три XOR, если временных нет).

Классический разбор всех трёх — Briggs et al., «Practical Improvements to the Construction and Destruction of Static Single Assignment Form», и глава «SSA destruction» в SSA Book — бесплатной книге, целиком посвящённой SSA.

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

SSA — это функциональное программирование

Взгляд, который переворачивает картинку. Посмотрите на блок с φ ещё раз:

head2(i.2, s.2):              ; блок как функция от своих phi-аргументов
  ...
  jmp head2(i.3, s.3)         ; переход как хвостовой вызов

Если считать базовые блоки функциями, φ — параметрами, а переходы — хвостовыми вызовами, то SSA превращается в набор взаимно рекурсивных функций, то есть в чистый функциональный код. Это не метафора, а точная эквивалентность, доказанная Эндрю Аппелем в заметке «SSA is Functional Programming» (SIGPLAN Notices, 1998). Именно так устроен MLIR-диалект с блочными аргументами, так устроен Swift SIL, Cranelift и Rust MIR — там нет φ, есть аргументы базовых блоков, что решает проблему порядка предшественников по построению.

Обратное направление тоже работает: компиляторы функциональных языков давно используют CPS (continuation passing style) и ANF (administrative normal form) — формы, где всякое промежуточное вычисление именовано, а порядок вычисления явен. ANF — это буквально трёхадресный код, записанный через let. Связь с лямбда-исчислением здесь прямая: продолжения — это то, во что превращается поток управления, когда его выражают стратегиями редукции. Классика темы — Flanagan et al., «The Essence of Compiling with Continuations» (PLDI 1993). Практический вывод для инженера: если вы читали про функциональную парадигму, вы уже знаете половину теории SSA — просто под другими именами.

Важное ограничение, которое надо знать до того, как оно испортит вам день: SSA работает для значений, но не для памяти. *p = 1 не определяет никакого имени, и φ для «содержимого кучи» не построишь. Стандартный приём LLVM: фронтенд кладёт все локальные переменные в стек через alloca, работает с ними через load/store, а специальный проход mem2reg (он же SROA) поднимает те, чей адрес никуда не утёк, в SSA-значения. Всё, что осталось в памяти, обслуживается уже анализом псевдонимов — отдельной и заметно менее точной дисциплиной. Отсюда практическое следствие для прикладного программиста: взятие адреса локальной переменной может помешать оптимизациям, потому что переменная не поднимется в регистр.

Скелет SSA-компилятора в коде

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

Эта диаграмма — скелет практически любого SSA-компилятора, и в ней спрятан главный инженерный трюк: Use — это двусвязная штука. Из инструкции видно, что она использует; из значения видно, кто его использует. Поэтому replaceAllUsesWith в LLVM работает за O(числа использований), а не за O(размера функции), и любая оптимизация превращается в локальную правку графа.

Другие формы IR

Линейный SSA — не единственный вариант, и полезно знать, какие бывают ещё и чем они платят.

Стековый байткод. JVM, WebAssembly, CPython, .NET CIL: операнды берутся с неявного стека, инструкции однобайтовые и без операндов. Плюсы — компактность (важно, когда IR передаётся по сети) и тривиальная кодогенерация из AST. Минусы — анализ требует сначала восстановить, что откуда пришло; стек прячет поток данных. Поэтому JIT-компиляторы первым делом переводят байткод обратно в SSA. Подробно — в статье про виртуальные машины.

Sea of nodes. Форма Клиффа Клика, использованная в HotSpot C2: инструкции — узлы графа, рёбра — только зависимости (по данным и по управлению), а порядок внутри блока не фиксирован до самого планирования. Идея красивая: не задавать порядок там, где он не важен, значит не мешать оптимизациям. Оригинал — «A Simple Graph-Based Intermediate Representation». Расплата — сложность отладки и непредсказуемое планирование; в 2024 году команда V8 публично отказалась от sea of nodes в пользу линейного CFG с SSA, объяснив это стоимостью сопровождения: «Land ahoy: leaving the Sea of Nodes». Хороший урок про инженерные компромиссы: «более выразительный IR» и «более удобный IR» — не одно и то же.

E-графы и равенственное насыщение. Вместо того чтобы применять переписывания по очереди и жалеть о порядке, держат структуру, представляющую все эквивалентные варианты сразу, и в конце извлекают лучший. Библиотека egg и оптимизатор ISLE в Cranelift — самая заметная практика.

Как посмотреть настоящий IR своими глазами

Лучший способ понять IR — распечатать его для кода, который вы сами написали. Всё это работает прямо сейчас:

# LLVM IR из C — сначала как есть (переменные в стеке), потом после mem2reg (в SSA)
clang -O0 -S -emit-llvm sum.c -o - | head -40
clang -O0 -S -emit-llvm sum.c -o - | opt -passes=mem2reg -S | head -40

# посмотреть, что делает конкретный проход, и во что превращается функция
clang -O2 -mllvm -print-after-all -S sum.c -o /dev/null 2>&1 | less

# GIMPLE и RTL в GCC (файлы sum.c.*)
gcc -O2 -fdump-tree-ssa -fdump-rtl-expand sum.c

# MIR в Rust — тот самый средний слой, где живёт borrow checker
rustc --emit=mir sum.rs -o sum.mir

# SSA в Go: генерирует ssa.html с интерактивным дампом ВСЕХ проходов подряд
GOSSAFUNC=SumTo go build ./...

# байткод: JVM, Python, WebAssembly
javap -c Sum.class
python3 -m dis sum.py
wasm2wat sum.wasm | head -40

Файл ssa.html из Go стоит открыть хотя бы раз: там колонками показаны все ~40 проходов, и видно, как i < n из исходника доезжает до CMPQ — включая появление и исчезновение φ. Это лучший бесплатный учебник по среднему слою, какой есть. Описание проходов — в README компилятора Go.

Типичные ошибки при проектировании IR

• Слишком высокий IR. Оставили в IR «инструкцию цикла» или «инструкцию вызова метода с диспетчеризацией» — и каждый проход обязан знать про их семантику. IR должен быть настолько простым, насколько позволяют оптимизации, которые вы собираетесь делать.
• Слишком низкий IR. Спустились до регистров до того, как сделали инлайнинг, — потеряли типы, потеряли информацию об алиасинге, оптимизации стали невозможны. Правило: делайте преобразование на самом высоком уровне, где оно ещё выразимо.
• Нет верификатора. Без проверки инвариантов после каждого прохода ошибка проявляется через три прохода в чужом коде. Верификатор пишется за час и окупается в первый же день.
• φ не в начале блока. Перестановка φ вниз или обычной инструкции вверх ломает атомарность слияний. Инвариант «все φ идут подряд в начале блока» проверяйте в верификаторе.
• Забыли синхронизировать порядок предшественников с аргументами φ. Проход удалил ребро, забыл удалить аргумент — и φ читает мусор. Практический совет: сделайте preds не списком, а частью структуры блока с единственным API для правки рёбер, который сам чинит все φ.
• Критические рёбра не расщеплены. Всё работает, пока не появится первая φ на пути с условным переходом.
• Нет позиций исходника в инструкциях. IR — единственное, что доедет до бэкенда; если инструкция не несёт span, ни отладчик, ни предупреждение «переменная не используется» на уровне IR построить не получится. Отладочная информация должна переживать все проходы, и оптимизации обязаны её обновлять.
• IR нельзя напечатать и прочитать обратно. Текстовый формат IR — не роскошь, а способ писать тесты на отдельный проход: «вот вход, вот ожидаемый выход». LLVM держит .ll именно ради этого, и то же самое стоит сделать даже в учебном компиляторе.
• Мутация структуры во время обхода. Удаление инструкций прямо в цикле по списку — классический источник повреждения IR. Собирайте список «на удаление» и применяйте после обхода.

Мини-итог

• AST хранит синтаксис, IR хранит вычисление. Оптимизациям нужен второй, поэтому средний слой существует во всех промышленных компиляторах.
• Трёхадресный код делает операции атомарными и именует промежуточные значения; вложенность и порядок вычисления перестают быть неявными.
• Базовые блоки и CFG превращают поток управления в обычный граф. Циклы становятся обратными рёбрами, недостижимый код отваливается сам.
• SSA — форма, где у каждого имени ровно одно определение. Она превращает вопрос «откуда значение» из анализа в чтение, и почти все современные оптимизации формулируются в её терминах.
• φ-функции ставятся в итерированный фронт доминирования, переименование идёт обходом дерева доминаторов. Сложность конструкции практически линейна, в патологиях квадратична.
• Выход из SSA — копии в предшественниках, с оговорками про критические рёбра, потерянную копию и обмен; на практике совмещается со слиянием при распределении регистров.
• SSA эквивалентна функциональному коду, где блоки — функции, а переходы — хвостовые вызовы. Современные IR (MLIR, SIL, Cranelift, Rust MIR) прямо используют аргументы блоков вместо φ.

Что почитать

• Ron Cytron, Jeanne Ferrante et al., «Efficiently Computing Static Single Assignment Form and the Control Dependence Graph», TOPLAS 1991 — статья, из которой выросла вся практика SSA.
• SSA Book — бесплатная книга целиком про SSA: построение, разрушение, проходы, регистры.
• Cooper, Harvey, Kennedy, «A Simple, Fast Dominance Algorithm» — тот алгоритм доминаторов, который стоит писать в своём компиляторе.
• Braun et al., «Simple and Efficient Construction of SSA Form», CC 2013 — SSA без фронтов доминирования.
• Andrew Appel, «SSA is Functional Programming» — три страницы, меняющие взгляд на предмет.
• LLVM Language Reference — образцовая документация IR; читайте разделы про phi, undef/poison и атрибуты.
• Rust MIR в rustc dev guide и GIMPLE в GCC internals — два разных промышленных средних слоя, полезно сравнить.
• QBE — компактный SSA-бэкенд на нескольких тысячах строк C; отличный образец для своего компилятора, если LLVM кажется слишком большим.
• Steven Muchnick, Advanced Compiler Design and Implementation — до сих пор лучший справочник по представлениям и анализам; главы 4–8.
• Связанные статьи портала: теория графов — доминаторы это графовое отношение, обходы графов — обходы, на которых всё построено, функциональная парадигма и лямбда-исчисление — вторая половина теории SSA под другими именами.

Что дальше

У нас есть IR в SSA-форме — и до сих пор ни одной оптимизации, кроме случайно получившегося удаления недостижимых блоков. Следующая статья превращает средний слой в то, ради чего он и строился: свёртка констант и распространение копий, нумерация значений, удаление мёртвого кода, инлайнинг и вынос инвариантов из цикла. Мы увидим, как каждая из них записывается в терминах def-use цепочек в десяток строк, почему проходы гоняют до неподвижной точки и где проходит граница между «быстрее» и «уже не та программа».

Оптимизации: свёртка констант, инлайнинг, устранение мёртвого кода