Промежуточное представление (IR)

Clang, Rust, Swift, Kotlin, Julia - разные языки с разным синтаксисом и типами. Но все они генерируют один и тот же LLVM IR. Это возможно благодаря промежуточному представлению: слою абстракции между языком и железом. IR - lingua franca компиляторного мира.

• **LLVM IR** используется более чем 30 языками: Clang (C/C++), rustc, swiftc, kotlinc/native, flang (Fortran), Julia, LDC (D), Crystal. Один и тот же backend обрабатывает x86, ARM, RISC-V, WebAssembly - это стало возможным именно благодаря единому IR.
• **GCC GIMPLE** - собственный IR GCC, более высокоуровневый чем LLVM IR. При компиляции с `-fdump-tree-all` GCC выводит все промежуточные представления - можно увидеть как исходный код трансформируется через 20+ фаз.
• **WebAssembly** сам по себе является IR: это stack-based bytecode, который браузеры компилируют в нативный код через свои JIT-компиляторы (V8 TurboFan, SpiderMonkey IonMonkey, JavaScriptCore B3).

Three-Address Code

Three-address code (TAC) - промежуточное представление, где каждая инструкция содержит не более трёх операндов: результат = операнд1 op операнд2. Это резко упрощает оптимизации: каждое вычисление именовано, побочные эффекты изолированы.

LLVM IR - наиболее известный пример трёхадресного IR в SSA-форме. Он типизированный (каждый операнд имеет тип: `i32`, `float`, `ptr`), строго SSA (каждое имя определяется ровно один раз), и предназначен для machine-independent оптимизаций. Clang, rustc, swiftc, kotlinc, Julia - все используют LLVM IR как общий backend.

SSA Form

SSA (Static Single Assignment) - форма IR, где каждая переменная определяется ровно один раз. При ветвлении используются phi-функции для объединения значений из разных путей. SSA кардинально упрощает dataflow analysis и большинство оптимизаций.

LLVM IR всегда в SSA-форме. GCC переходит в SSA на уровне GIMPLE (функция `gimple_convert_to_ssa`). Java bytecode и JVM JIT (HotSpot C2) также строят SSA для оптимизаций. SSA была изобретена в IBM в 1988 году (Cytron et al.) - до этого оптимизаторы использовали более сложный dataflow analysis. Переход индустрии на SSA занял около 10 лет.

Control Flow Graph

Control Flow Graph (CFG) - ориентированный граф, где узлы - basic blocks (линейные последовательности инструкций без переходов), а рёбра - возможные переходы между блоками. CFG явно представляет все возможные пути выполнения программы.

LLVM IR явно содержит CFG: каждая функция - список basic blocks, каждый block заканчивается terminator instruction (br, ret, switch, invoke). Rustc MIR тоже явно CFG с `BasicBlock` и `Terminator`. CFG - основа для большинства оптимизаций: dead code elimination ищет недостижимые блоки, loop detection ищет циклы (strongly connected components в CFG).

Basic Blocks

Basic block - максимальная линейная последовательность инструкций, такая что управление входит только в начало и выходит только в конец. Внутри basic block нет условных переходов. Это единица оптимизации: локальные оптимизации работают внутри одного блока.

LLVM IR проверяет корректность basic blocks через `verifyFunction()` - если функция не проходит верификацию, LLVM падает с assertion. Это помогает отлаживать новые бэкенды: если сгенерированный IR некорректный (например phi не в начале блока, или блок без terminator), верификатор сразу указывает проблему.

Ключевые идеи

• **Three-address code** - IR где каждая инструкция: `result = op1 operator op2`. Каждое подвыражение именовано - основа для оптимизаций.
• **SSA форма** гарантирует: каждая переменная определяется ровно один раз. Phi-функции на стыках путей. Упрощает dataflow analysis и constant propagation.
• **CFG** - граф из basic blocks (узлы) и переходов (рёбра). Явное представление всех путей выполнения программы.
• **Basic block** - линейная последовательность без внутренних переходов. Начинается с leader, заканчивается terminator.

Связанные темы

IR - мост между семантическим анализом и генерацией кода:

• SSA-форма — SSA - специализированная форма IR, детально рассматривается в следующем уроке
• Локальные оптимизации — Большинство оптимизаций работают на уровне IR - constant folding, CSE, DCE
• Семантические проходы — Lowering из HIR/AST производит IR - это последний шаг semantic analysis

Вопросы для размышления

• LLVM IR типизирован (`i32`, `float`, `ptr`), а GCC RTL - нет. Какие оптимизации становятся возможными при наличии типов в IR?
• WebAssembly - это IR или ISA? Аргументируйте - у него есть свойства обоих.
• Почему SSA была изобретена так поздно (1988) несмотря на то, что dataflow analysis существовал с 1960-х? Что именно усложняло переход?

Связанные уроки

• plt-27-ir-optimization