Компиляторы
SSA-форма
Каждый компилятор, использующий LLVM - Clang, rustc, swiftc - неявно использует SSA. Все их оптимизации: constant propagation, dead code elimination, loop-invariant code motion - работают именно потому, что LLVM IR в SSA-форме. SSA изобрели в IBM в 1988 году - и с тех пор она стала стандартом де-факто для оптимизирующих компиляторов.
- **GCC** перешёл на SSA (GIMPLE SSA) в версии 4.0 (2005). До этого оптимизации работали на RTL и были значительно менее эффективными. Переход занял несколько лет разработки.
- **V8** (JavaScript engine) строит SSA в Turbofan для JIT-оптимизации горячего кода. Sea of Nodes representation в V8 - вариация SSA, где и control flow, и data flow представлены единым графом.
- **WASM компиляторы** (Cranelift в Wasmtime/Firefox, LLVM в Emscripten) строят SSA перед генерацией машинного кода из WebAssembly - даже если сам WASM stack-based bytecode.
Phi-Functions
Phi-функция (phi-node) в SSA - специальная инструкция на входе basic block, которая выбирает значение из нескольких возможных предшественников. `x2 = phi(x0: BB_if, x1: BB_else)` означает: x2 равно x0 если пришли из BB_if, и x1 если из BB_else.
Параллельная семантика phi-функций важна: если в одном блоке есть `a = phi(b, ...)` и `b = phi(a, ...)`, то оба читают старые значения, не новые. При destruction SSA (перед codegen) phi-функции разворачиваются в moves, и порядок имеет значение - нужно избегать 'lost copy problem' и 'swap problem'. GCC решает это через введение параллельных копий.
Где в basic block могут располагаться phi-функции?
Dominance
Блок A доминирует над блоком B, если любой путь от entry до B проходит через A. Dominance - ключевая концепция для построения SSA: phi-функции нужны именно там, где разные определения переменной 'встречаются' - на доминаторных границах (dominance frontiers).
Дерево доминаторов строится алгоритмом Lengauer-Tarjan за O(N * alpha(N)) - почти линейное время. LLVM использует именно этот алгоритм в `DominatorTree`. GCC использует аналог. Знание дерева доминаторов критично не только для SSA: loop analysis (обратные рёбра в CFG - это циклы), inlining, и многие другие оптимизации опираются на dominance.
Зачем нужна концепция dominance при построении SSA?
SSA Construction
Построение SSA - преобразование обычного IR в SSA-форму. Алгоритм Cytron et al. (1991) делает это в два прохода: сначала вставляет phi-функции в нужные места (используя dominance frontiers), затем переименовывает переменные.
Простая альтернатива полному алгоритму - 'mem2reg' в LLVM: выделять все переменные через `alloca` (на стеке), а затем pass `mem2reg` продвигает их в SSA-регистры. Clang использует именно этот подход - сначала генерирует наивный код с alloca, затем запускает mem2reg. Это упрощает codegen, перекладывая сложность построения SSA на оптимизирующий pass.
Что делает LLVM pass `mem2reg`?
SSA Destruction
SSA destruction - обратное преобразование: из SSA-формы в обычный IR перед генерацией машинного кода. Phi-функции не существуют в реальном железе - их нужно заменить копиями (moves) в предшествующих блоках.
LLVM не делает явного SSA destruction как отдельной фазы - register allocator понимает phi-функции и вставляет необходимые move-инструкции сам. GCC наоборот, явно destructs SSA перед распределением регистров. Оба подхода корректны - вопрос в разделении ответственности между SSA-destruction и register allocation.
Почему нельзя прямолинейно заменить `phi(a, b)` на просто `a` (взять первый аргумент)?
Ключевые идеи
- **Phi-функции** на входе в basic block выбирают значение из нескольких предшественников. Параллельная семантика - все phi читают старые значения.
- **Dominance** и dominance frontiers определяют где нужны phi-функции. Алгоритм Cytron O(N alpha(N)) - почти линейный.
- **SSA construction** - вставка phi + переименование. LLVM упрощает через alloca + mem2reg pass.
- **SSA destruction** заменяет phi на moves перед codegen. Требует осторожности при циклических зависимостях (swap problem).
Связанные темы
SSA - основа для большинства оптимизаций в modern компиляторах:
- Промежуточное представление — SSA - специальная форма IR; понимание TAC и CFG необходимо для SSA
- Локальные оптимизации — Constant propagation и dead code elimination работают непосредственно на SSA-форме
- Глобальные оптимизации — Dataflow analysis и глобальная оптимизация используют SSA-форму и доминаторное дерево
Вопросы для размышления
- В LLVM phi-функции только в начале блока; в GCC GIMPLE phi-функции также в начале. Почему нельзя разрешить phi в любом месте блока - что сломается в оптимизациях?
- V8 использует 'Sea of Nodes' - единый граф для control flow и data flow без явных basic blocks. Какие оптимизации проще в Sea of Nodes по сравнению с классическим SSA?
- SSA требует O(N) phi-функций в худшем случае. Существуют ли практические программы, где количество phi-функций значительно превышает количество переменных?