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

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

Дальше начинается странная работа: компилятор переписывает вашу программу в другую программу. Не в «более правильную» — в такую, которая делает то же самое, но быстрее или меньше. Слово «оптимизация» здесь историческое и неточное: никакого оптимума никто не находит и найти не может. Компилятор применяет набор локально выгодных переписываний, надеясь, что сумма окажется полезной, и регулярно ошибается.

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

Контракт оптимизатора: что нельзя ломать

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

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

Каждый проход отвечает на три разных вопроса, и путать их — главный источник багов в оптимизаторах:

1. Корректно ли? Сохранит ли переписывание семантику на всех входах, включая те, которых никогда не будет. Ответ должен быть доказательством, а не наблюдением.
2. Выгодно ли? Станет ли программа быстрее. Ответ — эвристика или профиль, и он почти всегда приблизительный.
3. Сколько стоит анализ? Компилятор запускают тысячи раз в день, а точный анализ бывает экспоненциальным.

Первый вопрос бинарный, остальные два — компромиссы. Пассы, которые смешивают их в одном условии («если выглядит выгодно — считаем корректным»), ломают код.

Почему компилятор обязан быть пессимистом

«Будет ли эта переменная всегда равна 42?», «может ли этот указатель быть нулевым?», «выполнится ли эта ветка хоть раз?» — все такие вопросы алгоритмически неразрешимы. Это не техническая трудность, а теорема Райса: любое нетривиальное семантическое свойство программ неразрешимо (см. вычислимость).

Отсюда единственно возможная стратегия: консервативное приближение. Анализ отвечает не «да/нет», а «точно да» / «не знаю», и любое «не знаю» трактуется в пользу отказа от преобразования. Отсюда асимметрия, которую надо принять сразу: упущенная оптимизация — неприятность, ложно применённая оптимизация — катастрофа. Именно поэтому изучать оптимизации стоит начиная с вопроса «что здесь может пойти не так», а не «сколько процентов это даст».

Три этажа: где живут оптимизации

Разделение не бюрократия, а следствие экономики компилятора: средний слой пишется один раз на все целевые архитектуры и все фронтенды — та самая идея «песочных часов», ради которой IR и существует. Правило простое: не требует знания о числе регистров и латентности инструкций — место в середине; требует («умножение на 7 дешевле пары сдвигов на этом ядре») — в бэкенде.

Шкала уровней, полезная как чек-лист при чтении чужого компилятора:

IR, с которым мы работаем

Соберём минимальный SSA-IR из статьи 06 в самодостаточном виде — весь код ниже работает на нём.

from __future__ import annotations
from dataclasses import dataclass, replace
from collections import defaultdict

@dataclass(frozen=True, slots=True)
class Const: value: int
@dataclass(frozen=True, slots=True)
class Reg:   name: str           # SSA-значение: определено ровно один раз

Operand = Const | Reg

@dataclass(frozen=True, slots=True)
class Instr:
    dest: str | None
    op: str                      # copy add sub mul div shl lt gt eq call phi
    args: tuple                  # tuple[Operand, ...]; для phi — ((метка, Operand), ...)
    callee: str | None = None

@dataclass(frozen=True, slots=True)
class Jmp: target: str
@dataclass(frozen=True, slots=True)
class Br:  cond: Operand; then_: str; else_: str
@dataclass(frozen=True, slots=True)
class Ret: value: Operand

Term = Jmp | Br | Ret

@dataclass
class Block:
    label: str
    instrs: list[Instr]
    term: Term                   # блок всегда заканчивается терминатором

@dataclass
class Func:
    name: str
    params: list[str]
    blocks: list[Block]          # blocks[0] — вход

def succs(t: Term) -> list[str]:
    if isinstance(t, Jmp): return [t.target]
    if isinstance(t, Br):  return [t.then_, t.else_]
    return []

def instr_operands(i):           # операнды инструкции, с учётом формы phi
    return [o for _, o in i.args] if i.op == "phi" else list(i.args)

def term_operands(t):
    if isinstance(t, Br):  return [t.cond]
    if isinstance(t, Ret): return [t.value]
    return []

def size(fn: Func) -> int:       # метрика «сколько инструкций осталось»
    return sum(len(b.instrs) + 1 for b in fn.blocks)

Вот программа на Mini, которую мы будем улучшать, и её IR — ровно то, что выдал бы наш фронтенд после проверки типов:

fn area(w: int, h: int) -> int { return w * h; }

fn main() -> int {
    let w = 3;
    let h = 4;
    let a = area(w, h);
    let scale = 100;
    let unused = a * scale;      // никем не читается
    if a > 10 { return a; } else { return 0; }
}

fn main():
b0:
  %w = copy 3
  %h = copy 4
  %a = call area(%w, %h)
  %scale = copy 100
  %unused = mul %a, %scale
  %c = gt %a, 10
  br %c, b1, b2
b1:
  ret %a
b2:
  ret 0

Девять инструкций. Человек видит, что вся функция — это return 12. Задача статьи — научить этому компилятор, причём не спецкейсом, а последовательностью независимых проходов.

Свёртка констант: от наивной к настоящей

Уровень 1: свёртка на AST

Самая простая форма — переписывание дерева снизу вверх: если у узла все дети стали литералами, вычисляем его прямо сейчас. Это тот самый Transformer из статьи 03:

def fold(node: Expr) -> Expr:
    match node:
        case Binary(op, l, r, span):
            l, r = fold(l), fold(r)
            if isinstance(l, IntLit) and isinstance(r, IntLit):
                if op == "/" and r.value == 0:
                    return Binary(op, l, r, span)      # деление на ноль не сворачиваем!
                v = {"+": l.value + r.value, "-": l.value - r.value,
                     "*": l.value * r.value, "/": l.value // r.value}[op]
                return IntLit(v, span)
            return Binary(op, l, r, span)
        case _:
            return node

O(n) по времени и O(глубина) по стеку. Двенадцать строк, и они реально экономят: выражения вида 60 * 60 * 24 программист имеет право писать читаемо, не платя за это в рантайме.

Обратите внимание на строку с делением. Свернуть 1 / 0 в «ошибку компиляции» нельзя: если эта ветка недостижима, вы сломаете корректную программу. Свернуть в произвольное число — тем более. Единственный корректный ответ — не трогать. Это микроскопический пример общего правила: оптимизатор не имеет права улучшать поведение на входах, где программа падала бы.

Но в нашем main нет ни одного выражения из двух литералов: есть %a = call area(%w, %h), где %w и %h — переменные, и AST-свёртка не видит ничего. Чтобы увидеть, нужно распространение констант — знание о значении переменной надо протащить по программе, а для этого нужны поток управления, поток данных и аккуратная теория того, что делать в точках слияния путей.

Уровень 2: решётка

Введём для каждого SSA-значения не «число или ничего», а элемент решётки:

• ⊤ (top) — «пока не знаем»: до этого места анализ ещё не дошёл;
• конкретное число — «на всех достижимых путях сюда приходит именно оно»;
• ⊥ (bottom) — «не константа»: зависит от входа программы или от того, каким путём мы пришли.

Ключевое свойство — высота 2. Значение может опуститься максимум дважды (⊤ → c → ⊥) и никогда не поднимается. Отсюда сразу следует завершаемость анализа: суммарное число изменений ограничено 2 · (число значений), а значит итеративный алгоритм обязан прийти к неподвижной точке. Формально: множество состояний — частично упорядоченное множество конечной высоты, а функции переноса монотонны, поэтому по теореме Клини итерация сходится. Ту же алгебраическую конструкцию вы встречали в абстрактной алгебре как полурешётку с операцией meet.

Уровень 3: SCCP — свёртка вместе с достижимостью

Наивный алгоритм («пессимистичный»: всё сначала ⊥, поднимаем, что сможем) слабее, чем нужно. Классический алгоритм SCCP (Sparse Conditional Constant Propagation, Wegman & Zadeck, TOPLAS 1991) устроен оптимистично: всё сначала ⊤, и одновременно считаются две вещи —

• какие значения константны;
• какие рёбра CFG вообще исполнимы.

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

class _Top:
    def __repr__(self): return "T"
class _Bot:
    def __repr__(self): return "B"
TOP, BOT = _Top(), _Bot()

def meet(a, b):
    if a is TOP: return b
    if b is TOP: return a
    if a is BOT or b is BOT: return BOT
    return a if a == b else BOT          # c ⊓ c = c, c ⊓ d = ⊥

def apply_op(op, xs):
    a = xs[0]
    if op == "copy": return a
    b = xs[1]
    if op == "add": return a + b
    if op == "sub": return a - b
    if op == "mul": return a * b
    if op == "div": return None if b == 0 else a // b   # None = «сворачивать нельзя»
    if op == "shl": return a << b
    if op == "lt":  return int(a < b)
    if op == "gt":  return int(a > b)
    if op == "eq":  return int(a == b)
    return None

Сам анализ. Он ведёт два рабочих списка: рёбра CFG, ставшие исполнимыми, и блоки, которые надо пересчитать, потому что использованное в них значение изменилось.

def sccp_analyze(fn: Func):
    blocks = {b.label: b for b in fn.blocks}
    val: dict[str, object] = {p: BOT for p in fn.params}   # параметры неизвестны
    look = lambda o: o.value if isinstance(o, Const) else val.get(o.name, TOP)

    users = defaultdict(set)                # значение -> блоки, где оно читается
    for b in fn.blocks:
        for o in [x for i in b.instrs for x in instr_operands(i)] + term_operands(b.term):
            if isinstance(o, Reg): users[o.name].add(b.label)

    exec_edge, reachable = set(), set()
    edge_wl = [(None, fn.blocks[0].label)]  # вход исполним по определению
    block_wl = []

    def eval_block(lab):
        b, changed = blocks[lab], set()
        for i in b.instrs:
            if i.op == "phi":               # meet только по исполнимым входам!
                new = TOP
                for src, o in i.args:
                    if (src, lab) in exec_edge:
                        new = meet(new, look(o))
            elif i.op == "call":
                new = BOT                   # межпроцедурно пока не считаем
            else:
                xs = [look(a) for a in i.args]
                if any(x is BOT for x in xs):   new = BOT
                elif any(x is TOP for x in xs): new = TOP
                else:
                    r = apply_op(i.op, xs)
                    new = BOT if r is None else r
            if val.get(i.dest, TOP) != new:
                val[i.dest] = new
                changed |= users[i.dest]
        t, edges = b.term, []
        if isinstance(t, Jmp):
            edges.append(t.target)
        elif isinstance(t, Br):
            c = look(t.cond)
            if c is BOT:      edges += [t.then_, t.else_]   # неизвестно — обе
            elif c is not TOP: edges.append(t.then_ if c else t.else_)
        return changed, edges                                # ⊤ — пока ни одной

    while edge_wl or block_wl:
        while edge_wl:
            pred, lab = edge_wl.pop()
            fresh = (pred, lab) not in exec_edge or lab not in reachable
            exec_edge.add((pred, lab)); reachable.add(lab)
            if fresh: block_wl.append(lab)
        if block_wl:
            lab = block_wl.pop()
            changed, edges = eval_block(lab)
            edge_wl += [(lab, e) for e in edges]
            block_wl += [u for u in changed if u in reachable]
    return val, reachable, exec_edge

Тонкость, из-за которой алгоритм и работает: если условие br пока имеет значение ⊤, ни одна ветка не помечается исполнимой. Пессимист пометил бы обе и потерял бы всё. Оптимист ждёт и в награду получает константы там, где их «нет».

Перезапись по результатам анализа — отдельная, простая фаза: подставляем константы вместо использований, выкидываем определения константных значений, схлопываем br с известным условием в jmp, удаляем недостижимые блоки, чиним phi.

def sccp(fn: Func) -> Func:
    val, reachable, exec_edge = sccp_analyze(fn)
    def rw(o):
        v = val.get(o.name, TOP) if isinstance(o, Reg) else None
        return Const(v) if isinstance(v, int) else o
    out = []
    for b in fn.blocks:
        if b.label not in reachable:
            continue                                   # недостижимый блок — целиком вон
        instrs = []
        for i in b.instrs:
            if isinstance(val.get(i.dest, TOP), int):
                continue                               # все использования уже заменены
            if i.op == "phi":
                args = tuple((s, rw(o)) for s, o in i.args if (s, b.label) in exec_edge)
                instrs.append(Instr(i.dest, "copy", (args[0][1],)) if len(args) == 1
                              else Instr(i.dest, "phi", args))
            else:
                instrs.append(replace(i, args=tuple(rw(a) for a in i.args)))
        t = b.term
        if isinstance(t, Br):
            c = rw(t.cond)
            t = Jmp(t.then_ if c.value else t.else_) if isinstance(c, Const) else Br(c, t.then_, t.else_)
        elif isinstance(t, Ret):
            t = Ret(rw(t.value))
        out.append(Block(b.label, instrs, t))
    return Func(fn.name, fn.params, out)

Сложность. Каждое ребро CFG становится исполнимым не более одного раза; каждое значение опускается по решётке не более двух раз, и каждое опускание ставит в очередь только его потребителей. Итого O(V + E + U) по времени, где U — суммарное число использований, и O(V + E) по памяти. То есть практически линейно от размера функции — поэтому SCCP включён на всех уровнях оптимизации во всех промышленных компиляторах.

Проверим на примере, где наивный алгоритм проигрывает. Цикл, счётчик которого «изменяется»:

fn loopy():
b0:  %i = copy 1
     jmp b1
b1:  %x = phi [b0 %i], [b2 %y]
     %c = lt %x, 1
     br %c, b2, b3
b2:  %y = add %x, 1
     jmp b1
b3:  ret %x

Пессимистичный анализ рассуждает так: у %x два входа, один из них %y, про %y пока ничего не известно → %x = ⊥ → всё, конец. SCCP рассуждает иначе: ребро b2 → b1 ещё не помечено исполнимым, значит %x = 1; тогда %c = lt 1, 1 = 0; тогда исполнимо только ребро b1 → b3; значит b2 недостижим и второй вход phi не появится никогда. Результат — ret 1, вся функция схлопывается в одну инструкцию. Наш код выдаёт именно это.

Алгебраические упрощения и снижение силы операций

Свёртка работает, когда известны все операнды. Но многое можно упростить, зная только один:

def is_c(o, v): return isinstance(o, Const) and o.value == v

def simplify(i: Instr) -> Instr:
    if i.op not in ("add", "sub", "mul", "div"):
        return i
    a, b = i.args
    cp = lambda o: Instr(i.dest, "copy", (o,))
    if i.op == "add" and is_c(b, 0): return cp(a)          # x + 0 = x
    if i.op == "add" and is_c(a, 0): return cp(b)
    if i.op == "sub" and is_c(b, 0): return cp(a)
    if i.op == "sub" and a == b:     return cp(Const(0))   # x - x = 0
    if i.op == "mul" and is_c(b, 1): return cp(a)          # x * 1 = x
    if i.op == "mul" and is_c(a, 1): return cp(b)
    if i.op == "mul" and (is_c(a, 0) or is_c(b, 0)):       # x * 0 = 0 даже при x = ⊥
        return cp(Const(0))
    if i.op == "div" and is_c(b, 1): return cp(a)
    if i.op == "mul" and isinstance(b, Const) and b.value > 0 and b.value & (b.value - 1) == 0:
        return Instr(i.dest, "shl", (a, Const(b.value.bit_length() - 1)))   # снижение силы
    return i

Это peephole-оптимизация — идея 1965 года (McKeeman), в LLVM выросшая в проход InstCombine объёмом в десятки тысяч строк. Локально, дёшево, O(n), и удивительно результативно, потому что предыдущие проходы (особенно инлайнинг) постоянно порождают такой мусор: x * 1 в исходнике не пишут, а после подстановки шаблонной функции он появляется сам.

Три места, где на этом ломаются:

• Числа с плавающей точкой не ассоциативны. (a + b) + c и a + (b + c) дают разные результаты, а x * 0 не равно 0, если x — NaN или бесконечность. Все эти правила для float запрещены, пока пользователь явно не разрешил их флагом (-ffast-math), и это ровно та причина, по которой численные алгоритмы из численных методов живут в мире, где компилятор оптимизирует их гораздо хуже целочисленного кода.
• Знаковое переполнение. x + 1 > x — тождественно истинно в C (переполнение знакового — неопределённое поведение), но ложно при x == INT_MAX в Java или в C с -fwrapv. Одно и то же переписывание корректно в одном языке и является багом в другом.
• Деление и остаток на отрицательных. x / 2 не заменяется на x >> 1 для знаковых типов: округление у деления идёт к нулю, у сдвига — вниз. Компиляторы генерируют здесь три инструкции с коррекцией, и это не глупость, а корректность.

Нумерация значений: не считать одно и то же дважды

Устранение общих подвыражений (CSE) в SSA превращается в простую задачу: раз у значения одно определение, два вычисления с одинаковой операцией и одинаковыми операндами дают одинаковый результат, и второе можно просто выбросить. Локальный вариант — нумерация значений (local value numbering) внутри одного блока, через хеш-таблицу (см. хеш-таблицы):

PURE = {"copy", "add", "sub", "mul", "div", "shl", "lt", "gt", "eq", "phi"}
COMMUTATIVE = {"add", "mul", "eq"}

def lvn(fn: Func) -> Func:
    out = []
    for b in fn.blocks:
        table: dict[tuple, str] = {}          # (операция, операнды) -> имя значения
        repl: dict[str, Operand] = {}
        instrs = []
        res = lambda o: repl.get(o.name, o) if isinstance(o, Reg) else o
        for i in b.instrs:
            if i.op == "phi" or i.op not in PURE:
                args = (tuple((s, res(o)) for s, o in i.args) if i.op == "phi"
                        else tuple(res(a) for a in i.args))
                instrs.append(replace(i, args=args)); continue
            args = tuple(res(a) for a in i.args)
            key = (i.op, tuple(sorted(args, key=str)) if i.op in COMMUTATIVE else args)
            if key in table:                  # уже считали — переиспользуем
                repl[i.dest] = Reg(table[key]); continue
            table[key] = i.dest
            instrs.append(replace(i, args=args))
        t = b.term
        if isinstance(t, Br):    t = Br(res(t.cond), t.then_, t.else_)
        elif isinstance(t, Ret): t = Ret(res(t.value))
        out.append(Block(b.label, instrs, t))
    return Func(fn.name, fn.params, out)

Нормализация коммутативных операций (сортировка операндов) бесплатно ловит a+b и b+a. На функции с восемью инструкциями и двумя повторами это даёт минус два вычисления:

fn dist2(%x, %y):            →     fn dist2(%x, %y):
  %a = mul %x, %x                    %a = mul %x, %x
  %b = mul %y, %y                    %b = mul %y, %y
  %c = add %a, %b                    %c = add %a, %b
  %d = mul %x, %x   (то же, что %a)  %f = add %c, %a
  %e = add %b, %a   (то же, что %c)  %g = add %f, %c
  %f = add %c, %d                    ret %g
  %g = add %f, %e
  ret %g                             8 инструкций → 6

O(n) по времени с хешированием, O(n) по памяти. Глобальный вариант — GVN, где нумерация распространяется по дереву доминаторов: выражение из доминирующего блока доступно во всех подчинённых, потому что гарантированно вычислено раньше. Ещё дальше идёт hash-consing, когда IR устроен так, что одинаковые выражения физически представлены одним объектом и CSE происходит в момент построения — так работают e-graph-подходы (egg, Cranelift ISLE) и решатели вроде Z3.

Устранение мёртвого кода

«Мёртвый код» — три разные вещи, и путать их не стоит:

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

Классический DCE в SSA — это mark-and-sweep, буквально та же схема, что у сборщика мусора из статьи 10: корни — то, что заведомо нужно, дальше транзитивное замыкание по ссылкам, всё непомеченное удаляется. Только вместо объектов в куче — инструкции, а вместо указателей — use-def-рёбра.

def dce(fn: Func) -> Func:
    live: set[str] = set()
    defs = {i.dest: i for b in fn.blocks for i in b.instrs}
    wl = []
    for b in fn.blocks:                       # корни
        for o in term_operands(b.term):       # то, что читает терминатор
            if isinstance(o, Reg): wl.append(o.name)
        for i in b.instrs:
            if i.op not in PURE:              # вызовы и запись в память — эффекты
                live.add(i.dest)
                wl += [o.name for o in instr_operands(i) if isinstance(o, Reg)]
    while wl:                                 # транзитивное замыкание
        r = wl.pop()
        if r in live: continue
        live.add(r)
        d = defs.get(r)
        if d is not None:
            wl += [o.name for o in instr_operands(d) if isinstance(o, Reg)]
    return Func(fn.name, fn.params,
                [Block(b.label, [i for i in b.instrs if i.dest in live or i.op not in PURE], b.term)
                 for b in fn.blocks])

O(n + U) по времени, O(n) по памяти. Главная строчка здесь — if i.op not in PURE. Всё, что имеет побочный эффект (вызов неизвестной функции, запись в память, ввод-вывод, работа с volatile), — живо по определению и тянет за собой свои аргументы. Ошибка в классификации чистоты — это не «потеряли оптимизацию», это удалённый printf.

Агрессивный DCE (ADCE) переворачивает логику: считать мёртвым всё, пока не доказано обратное. Разница проявляется на циклах — обычный DCE не тронет цикл, который ничего не делает, но крутится (его переменная используется им же самим), а ADCE, начав с пустого множества живого, такой цикл удалит целиком. Отсюда, кстати, знаменитая проблема бесконечных пустых циклов в C++: стандарт разрешает считать их не имеющими эффекта, и компилятор их выбрасывает, чем регулярно шокирует авторов бенчмарков.

Практическая ловушка того же рода. Код memset(password, 0, len); free(password); — идеальная мишень для устранения мёртвых записей: буфер после этого не читается, запись бессмысленна, компилятор её удаляет, пароль остаётся в памяти. Правильный ответ — explicit_bzero, memset_s или SecureZeroMemory: функции, специально помеченные как имеющие эффект. Компилятор здесь абсолютно прав по букве стандарта — просто ваша модель «наблюдаемого» шире, чем у языка.

Инлайнинг: мать всех оптимизаций

Подстановка тела функции в место вызова. С точки зрения теории — это β-редукция из лямбда-исчисления: (λx. body) arg → body[x := arg], ровно то же самое переписывание, включая необходимость аккуратно переименовывать связанные имена, чтобы не поймать чужую переменную. В SSA переименование обязательно и по другой причине: два экземпляра одного тела не могут определять значение с одним именем.

_uid = 0

def inline(fn: Func, funcs: dict[str, Func], budget: int = 8) -> tuple[Func, bool]:
    global _uid
    changed, out = False, []
    for b in fn.blocks:
        instrs = []
        for i in b.instrs:
            callee = funcs.get(i.callee) if i.op == "call" else None
            body = callee.blocks[0] if callee else None
            # упрощение: инлайним только листовые функции из одного блока
            if (callee and len(callee.blocks) == 1
                    and isinstance(body.term, Ret) and len(body.instrs) <= budget):
                _uid += 1
                m = {p: a for p, a in zip(callee.params, i.args)}   # параметры → аргументы
                sub = lambda o: m.get(o.name, o) if isinstance(o, Reg) else o
                for ci in body.instrs:
                    nd = f"{ci.dest}.{_uid}"                        # свежие имена
                    instrs.append(Instr(nd, ci.op, tuple(sub(a) for a in ci.args), ci.callee))
                    m[ci.dest] = Reg(nd)
                instrs.append(Instr(i.dest, "copy", (sub(body.term.value),)))
                changed = True
                continue
            instrs.append(i)
        out.append(Block(b.label, instrs, b.term))
    return Func(fn.name, fn.params, out), changed

Ограничение «одна ветвь, один ret» — не принципиальное, а ради краткости: в общем случае вызывающий блок разрезается по месту вызова, блоки вызываемой функции вставляются между половинами, а несколько return сливаются в phi в блоке-продолжении. Логика подстановки от этого не меняется.

Зачем это на самом деле нужно

Наивное объяснение — «экономим пролог, эпилог и переход» — почти всегда неверно: на современном процессоре вызов стоит единицы тактов и отлично предсказывается. Настоящая ценность в другом: инлайнинг превращает межпроцедурную задачу во внутрипроцедурную. До подстановки %a — результат вызова, то есть ⊥ для любого анализа. После — обычное выражение, у которого видны аргументы.

Отсюда же цена, и она реальна:

• Раздувание кода. Тело копируется в каждое место вызова. Больше кода — хуже попадания в кэш инструкций, и на больших программах это может перевесить весь выигрыш.
• Время компиляции. После инлайнинга функция растёт, а многие анализы нелинейны по её размеру. Инлайнинг всего подряд — типичная причина, по которой сборка проекта занимает час.
• Рекурсия. Без ограничения глубины подстановка не завершится никогда. Отдельный проход «раскрутка рекурсии» делает это осознанно и на фиксированную глубину.

Поэтому инлайнер — это модель стоимости плюс бюджет. Реальные критерии: размер тела в инструкциях IR; число мест вызова (функция с единственным вызовом инлайнится почти всегда — тело после этого удаляется целиком, и код даже уменьшается); «горячесть» места вызова по профилю; константность аргументов (передали литерал — после подстановки схлопнется полфункции); наличие always_inline / noinline. У LLVM это InlineCost с настраиваемым порогом (по умолчанию около 225 условных единиц, -inline-threshold), у GCC — семейство --param max-inline-insns-*.

Порядок обхода графа вызовов

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

Листья (area, format_int) оптимизируются первыми, затем report со вставленными телами, затем main. Компонента сильной связности обрабатывается как единое целое, и внутри неё инлайнинг ограничивается жёстким лимитом.

Собираем конвейер и запускаем

Остались три мелочи, каждая в несколько строк: применить simplify ко всем инструкциям, протащить copy (после инлайнинга их появляется много) и склеить блоки, соединённые единственным jmp.

def peephole(fn: Func) -> Func:
    return Func(fn.name, fn.params,
                [Block(b.label, [simplify(i) for i in b.instrs], b.term) for b in fn.blocks])

def copy_prop(fn: Func) -> Func:
    src = {i.dest: i.args[0] for b in fn.blocks for i in b.instrs if i.op == "copy"}
    def res(o):                                  # разворачиваем цепочки copy → copy → …
        seen = set()
        while isinstance(o, Reg) and o.name in src and o.name not in seen:
            seen.add(o.name); o = src[o.name]
        return o
    def fix(i):
        args = (tuple((s, res(o)) for s, o in i.args) if i.op == "phi"
                else tuple(res(a) for a in i.args))
        return replace(i, args=args)
    def fix_t(t):
        if isinstance(t, Br):  return Br(res(t.cond), t.then_, t.else_)
        if isinstance(t, Ret): return Ret(res(t.value))
        return t
    return Func(fn.name, fn.params,
                [Block(b.label, [fix(i) for i in b.instrs], fix_t(b.term)) for b in fn.blocks])

def merge_blocks(fn: Func) -> Func:
    preds = defaultdict(list)
    for b in fn.blocks:
        for s in succs(b.term): preds[s].append(b.label)
    blocks, dead, out = {b.label: b for b in fn.blocks}, set(), []
    for b in fn.blocks:
        if b.label in dead: continue
        cur = Block(b.label, list(b.instrs), b.term)
        while isinstance(cur.term, Jmp):                       # у преемника один вход и нет phi?
            nxt = blocks.get(cur.term.target)
            if (nxt is None or len(preds[nxt.label]) != 1
                    or nxt.label == fn.blocks[0].label or any(i.op == "phi" for i in nxt.instrs)):
                break
            cur = Block(cur.label, cur.instrs + list(nxt.instrs), nxt.term)
            dead.add(nxt.label)
        out.append(cur)
    return Func(fn.name, fn.params, [b for b in out if b.label not in dead])

Теперь конвейер:

def optimize(fn: Func, funcs: dict[str, Func], rounds: int = 5) -> Func:
    for _ in range(rounds):
        before = size(fn)
        fn, _ = inline(fn, funcs)     # раскрыть контекст
        fn = sccp(fn)                 # константы + недостижимость
        fn = peephole(fn)             # алгебраические тождества
        fn = lvn(fn)                  # общие подвыражения
        fn = copy_prop(fn)            # убрать copy-цепочки
        fn = dce(fn)                  # вымести мусор
        fn = merge_blocks(fn)         # склеить блоки с одним входом
        if size(fn) == before:        # неподвижная точка — дальше смысла нет
            break
    return fn

Вывод на нашем main:

=== ДО ===                        === ПОСЛЕ ===
fn main():                        fn main():
b0:                               b0:
  %w = copy 3                       ret 12
  %h = copy 4
  %a = call area(%w, %h)          инструкций: 1
  %scale = copy 100
  %unused = mul %a, %scale
  %c = gt %a, 10
  br %c, b1, b2
b1: ret %a
b2: ret 0

инструкций: 9

Стоит проследить промежуточные шаги, потому что в них вся суть. После инлайнинга инструкций становится десять — больше, чем было. Проход, который оценивали бы в одиночку по метрике «размер кода», выглядел бы вредным. Потом SCCP видит mul 3, 4, сворачивает всю цепочку до 12, вычисляет 12 > 10 = 1, выкидывает ветку b2 как недостижимую; DCE убирает %unused; слияние блоков склеивает остаток. Ни один шаг не сработал бы без предыдущего.

Отсюда важнейший практический вывод: оптимизации оцениваются только конвейером целиком. Проход может быть полезен исключительно тем, что создаёт условия для другого прохода, — и в LLVM таких проходов (SROA, SimplifyCFG, Reassociate) едва ли не большинство.

Общий каркас: анализ потока данных

Всё, что мы написали, — частные случаи одной схемы, формализованной Килдаллом в 1973 году («A Unified Approach to Global Program Optimization»). Задача анализа потока данных задаётся четвёркой: решётка значений, направление обхода, функция переноса для инструкции и операция слияния в точках соединения путей.

Разница «may / must» — это выбор между «хотя бы на одном пути» и «на всех путях», и она напрямую задаёт, объединение у вас или пересечение. Перепутать — значит получить неверный, а не просто неточный анализ.

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

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

use[B] — прочитано в B до записи;  def[B] — записано в B.
Инициализация пустыми множествами, worklist из предшественников изменившегося блока,
обход в обратном постпорядке (для обратных анализов — в прямом).

Сложность итеративного анализа. Пусть h — высота решётки, E — число рёбер CFG. Каждое значение может измениться не более h раз, каждое изменение ставит в очередь предшественников, поэтому время — O(E · h · c), где c — стоимость одного применения функции переноса. Для битвекторных задач (живость, доступные выражения) h равно числу переменных, но на практике при обходе в обратном постпорядке число итераций оказывается пропорционально «глубине вложенности циклов» плюс два (результат Кэма и Ульмана) — то есть на реальном коде это 3–4 прохода, а не теоретический максимум. Память — O(V · |переменных|) на битвекторы, и это единственное место, где анализ потока данных бывает по-настоящему прожорлив.

Именно ради этой стоимости и придумана SSA: она делает анализ разреженным. В SSA не нужно держать множество «что живо в каждой точке» для распространения констант — информация течёт прямо по рёбрам def-use, минуя точки программы, где ничего не происходит. Наш SCCP поэтому и линейный.

Порядок проходов: задача без решения

Разделение на анализы (считают факты, ничего не меняют, кешируются) и трансформации (меняют IR, инвалидируют кеш) — центральная архитектурная идея любого промышленного оптимизатора. Больше всего багов в компиляторах живёт не в самих проходах, а в инвалидации: проход изменил CFG, но забыл сказать, что дерево доминаторов протухло, — и следующий анализ работает по устаревшим данным.

Теперь главный неприятный факт: оптимального порядка проходов не существует. Он зависит от программы, проходы не коммутируют, а поиск лучшей последовательности — комбинаторная задача, решаемая на практике эвристиками. Есть целое направление, применяющее к ней поисковые методы — генетические алгоритмы над последовательностями проходов (Cooper и др., 1999) и машинное обучение; это ровно та постановка, которой занимается трек поисковой инженерии.

На практике компиляторы используют фиксированный конвейер, выстроенный опытом, и гоняют его блоками по нескольку раз. Уровни -O — это именно разные конвейеры, а не «сила» одного и того же:

• -O0 — без оптимизаций, быстрая сборка, отладка работает буквально (переменные живут там, где объявлены);
• -O1 — дешёвые проходы, почти линейные по времени;
• -O2 — стандарт для продакшена: полный набор без раздувания кода;
• -O3 — плюс агрессивный инлайнинг и векторизация; иногда медленнее -O2 из-за кэша инструкций;
• -Os / -Oz — те же проходы с моделью стоимости, штрафующей размер;
• -flto — оптимизация на этапе линковки, когда виден весь модуль целиком.

Что мешает оптимизировать

Практически всегда, когда компилятор «не оптимизировал очевидное», причина в одном из четырёх:

1. Алиасинг. Если два указателя могут указывать на одну память, запись через один аннулирует всё, что известно про другой. Именно поэтому C-код с указателями оптимизируется хуже Fortran-кода (там алиасинг запрещён языком), и именно поэтому существуют restrict в C и модель владения в Rust — это способы сообщить компилятору то, что он не может доказать.
2. Непрозрачные вызовы. Вызов функции из другого модуля может сделать что угодно: изменить любую глобальную переменную, бросить исключение, не вернуться. Всё, что о ней известно, — сигнатура. Отсюда ценность LTO, атрибутов чистоты (__attribute__((const)), pure) и — глубже — того, что функциональная парадигма даёт компилятору бесплатно: у чистой функции результат зависит только от аргументов, поэтому её вызов можно вынести из цикла, продублировать или удалить.
3. Наблюдаемые эффекты и модели памяти. volatile, атомики, барьеры, обработчики сигналов ограничивают перестановки. В многопоточном коде перестановка двух записей, безобидная в одном потоке, ломает синхронизацию.
4. Порядок вычислений, зафиксированный языком. Строгая семантика вычисляет аргументы до вызова; ленивая — по требованию. Это меняет само множество допустимых преобразований, из-за чего у Haskell и у C наборы оптимизаций разные (подробно — в стратегиях вычисления).

Отдельная тема — неопределённое поведение как топливо. В C переполнение знакового, разыменование нулевого указателя и гонки данных объявлены UB, и компилятор имеет право считать, что их не бывает. Из «этот указатель разыменован» следует «он не нулевой», следовательно проверку if (p == NULL) ниже по коду можно удалить. Так была создана уязвимость в драйвере tun ядра Linux (CVE-2009-1897): проверка на NULL стояла после использования, компилятор законно её выкинул. Компилятор не «поступил плохо» — он применил корректное рассуждение к программе, у которой не было определённого смысла.

Как этим пользоваться на практике

• Смотрите на вывод. godbolt.org показывает ассемблер для любого компилятора и флага; clang -O2 -Rpass-missed=inline объясняет, почему что-то не заинлайнилось; opt -passes='default<O2>' -print-after-all печатает IR после каждого прохода LLVM.
• Не боритесь с компилятором вручную. Развернуть цикл руками, заменить x/2 на x>>1, завести временную переменную «чтобы не считать дважды» — бесполезно и вредно: ломает читаемость, а иногда и мешает оптимизатору распознать шаблон.
• Помогайте информацией, а не трюками. const, restrict, noexcept, final, атрибуты чистоты, узкие типы, отсутствие лишней косвенности — это доказательства, которые вы сообщаете бесплатно, а он сам вывести не может.
• PGO — самый недооценённый рычаг. Профиль (-fprofile-generate / -fprofile-use) превращает эвристики в измерения: компилятор узнаёт горячие ветки, нужные инлайны и раскладку блоков.
• Проверяйте сам оптимизатор. Верификатор IR после каждого прохода, дифференциальное тестирование генераторами вроде Csmith и формальная проверка переписываний: Alive2 регулярно находит некорректные правила в InstCombine LLVM. Крайняя точка пути — CompCert, компилятор C с машинно проверенным доказательством сохранения семантики.

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

• Оптимизация, применённая без доказательства. «На всех примерах работает» — не аргумент. Каждое переписывание нуждается в предусловии, и его надо уметь произнести вслух.
• Забытая инвалидация анализа. Изменили CFG — дерево доминаторов, граф вызовов и информация о циклах устарели. Именно здесь живут самые неприятные баги компиляторов: проявляются редко и на чужом коде.
• Неполный список эффектов. Считать чистым то, что пишет в память или бросает исключение, — прямой путь к удалённому коду, который был нужен.
• Оптимизация без измерения. -O3 не всегда быстрее -O2, инлайнинг не всегда полезен, а векторизация может замедлить короткий цикл. Метрика — время работы на реальной нагрузке.
• Работа с AST там, где нужен IR. На дереве не выразить «это значение уже вычислено в другом блоке». Попытки сделать серьёзные оптимизации до построения IR оборачиваются кодом, который невозможно поддерживать.
• Оценка прохода в одиночку. Инлайнинг сам по себе ухудшает почти все метрики. Смысл появляется только в связке.
• Игнорирование времени компиляции. Оптимизатор — тоже программа, и её сложность видна пользователю. Проход с квадратичным поведением на больших функциях сделает сборку невыносимой.

Мини-итог

Оптимизация — это пара «анализ + трансформация», где анализ даёт консервативное приближение неразрешимого свойства, а трансформация имеет право сработать только там, где приближение достаточно точное. Решётка конечной высоты и монотонные функции переноса гарантируют, что итерация сойдётся; SSA делает анализ разреженным и потому дешёвым; SCCP показывает, что комбинация двух анализов сильнее их последовательного применения; DCE — это mark-and-sweep по use-def-рёбрам; инлайнинг ценен не экономией на вызове, а тем, что открывает контекст остальным проходам. Наш оптимизатор в двести строк превратил девять инструкций в одну — не потому, что в нём есть умный проход, а потому, что в нём есть конвейер, доведённый до неподвижной точки.

Источники

• Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, главы 8–9 — канонический разбор анализа потока данных и машинно-независимых оптимизаций.
• Cooper, Torczon, Engineering a Compiler, главы 8–10 — современнее и практичнее по SSA, нумерации значений и построению конвейера проходов.
• Muchnick, Advanced Compiler Design and Implementation — справочник по конкретным преобразованиям.
• Wegman, Zadeck, «Constant Propagation with Conditional Branches», TOPLAS 1991 — оригинальная статья про SCCP.
• Kildall, «A Unified Approach to Global Program Optimization», POPL 1973 — общая теория анализа потока данных.
• Cytron, Ferrante, Rosen, Wegman, Zadeck, «Efficiently Computing Static Single Assignment Form», TOPLAS 1991.
• LLVM Passes и LLVM Language Reference — живой каталог того, что делают промышленные проходы.
• Chris Lattner, «The Architecture of Open Source Applications: LLVM».
• Alive2 — формальная проверка корректности переписываний.
• Chris Lattner, «What Every C Programmer Should Know About Undefined Behavior» — три части.
• Robert Nystrom, Crafting Interpreters — оптимизация байткода как более простой вход в тему.

Что дальше

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

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