История компиляторов: от Fortran до LLVM

1957 год. IBM. Джон Бэкус и его команда выпускают Fortran compiler. Скептики ожидали: программисты откажутся доверять машине перевод кода в ассемблер - они потеряют контроль над производительностью. Fortran compiler был принят немедленно: он генерировал код быстрее, чем большинство программистов писали вручную. С тех пор каждые 15-20 лет происходит следующая революция - C, GCC, LLVM. И каждый раз скептики ошибаются.

• PyTorch TorchDynamo: Python → LLVM IR → GPU kernels в реальном времени - Python-код обучает нейросети быстрее, чем ручной CUDA
• Apple Xcode: Swift → Clang/LLVM IR → ARM64 (M1/M2) - каждое iOS приложение проходит через наследника PhD-проекта 2000 года
• Rust: borrow checker + LLVM backend = memory safety без сборщика мусора + C-скорость
• Julia: JIT через LLVM, BLAS через Fortran, скорость C при гибкости Python - 70 лет компиляторной истории в одном стеке

Эволюция за 70 лет

1957: Fortran - первый высокоуровневый язык + компилятор. BNF изобретена для описания грамматики. | 1972: C + однопроходный компилятор. Unix переписан с ассемблера - первая портируемая ОС. | 1984: Thompson's Trusting Trust - bootstrap-проблема компиляторов как угроза безопасности. | 1987: GCC 1.0 (Richard Stallman, GNU project) - компилятор как свободное ПО. | 2000: LLVM (Chris Lattner, UIUC) - модульная архитектура через общий IR. | 2005: Apple принимает LLVM, Clang заменяет GCC в Xcode. | 2015: Rust 1.0 с LLVM backend - безопасность памяти + производительность C. | 2019: MLIR (Google) - компиляция ML-моделей через расширяемые IR диалекты.

Каждое из этих событий изменило индустрию: Fortran доказал что машина может заменить ассемблерщика, C сделал ОС портируемыми, GCC - свободный toolchain, LLVM - модульность как архитектурный принцип.

Fortran: рождение высокоуровневой компиляции

1957 год. IBM 704. Джон Бэкус и команда из 13 человек выпускают **Fortran** - FORmula TRANslation. Скептики прогнозировали провал: программисты не доверят машине перевод математики в машинный код. Результат оказался противоположным - Fortran compiler генерировал код, сопоставимый по скорости с ручным ассемблером, а разработка ускорилась в 10 раз. За три года Fortran стал стандартом для научных вычислений.

**Backus-Naur Form (BNF)** - формальная нотация для описания грамматики языка - была изобретена именно для спецификации Fortran. Сегодня BNF используется в каждом стандарте языка программирования и каждом parser generator.

Fortran решал реальную проблему: математики и физики хотели записывать формулы, а не управлять регистрами. Первый Fortran компилятор для IBM 704 весил 25 000 строк ассемблера и занимал 18 месяцев разработки. Он поддерживал выражения вроде `Y = SQRT(A**2 + B**2)` и транслировал их в оптимальные последовательности floating-point инструкций IBM 704.

**Почему Fortran не умирает:** PyTorch → calls → NumPy → calls → BLAS → calls → LAPACK → written in Fortran 77. Прошло 70 лет - цепочка не прервалась. Intel MKL (Math Kernel Library), используемый в большинстве ML-фреймворков, содержит миллионы строк Fortran.

C: компилятор для операционных систем

1972 год. Bell Labs. Деннис Ритчи создаёт C для переписи Unix с ассемблера. Задача была конкретной: один язык должен компилироваться под PDP-11, VAX и будущие архитектуры без изменения исходников. Решение - минималистичный язык с явной работой с памятью и однопроходный компилятор. Unix переписан на C к 1973 году - первая операционная система на высокоуровневом языке.

**Undefined Behavior как фича производительности:** C намеренно оставляет часть поведения неопределённой (переполнение знакового int, разыменование NULL, гонки данных). Компилятор может предполагать, что UB никогда не произойдёт, и оптимизировать на этом основании. Именно это делает C-компиляторы быстрее Java/Python: меньше проверок в рантайме.

В 1984 году Кен Томпсон произнёс легендарную лекцию при вручении Turing Award - **"Reflections on Trusting Trust"**. Главный тезис: компилятор C в Unix содержал скрытый backdoor в login, который не был виден в исходниках компилятора. Бэкдор был вшит в сам бинарник компилятора. Любой перекомпилированный компилятор заново вставлял бэкдор. Цепочка доверия компиляторов - фундаментальная проблема безопасности.

**Thompson's Trusting Trust:** компилятор компилирует сам себя (bootstrap). Если бинарник компилятора скомпрометирован - исходники безопасны, но бинарник продолжает воспроизводить уязвимость при каждой перекомпиляции. Защита - diverse double-compilation: компилировать через независимую цепочку и сравнивать бинарники.

GCC: компилятор, переживший эпохи

1987 год. Ричард Столлман пишет GCC - GNU C Compiler - для проекта GNU. Задача: свободный компилятор C, который bootstrap'ит себя сам. За 35 лет GCC превратился из C-компилятора в **GNU Compiler Collection** - поддерживающий C, C++, Fortran, Ada, Go, D, Objective-C. Сегодня GCC компилирует Linux kernel, большинство embedded firmware и критическую инфраструктуру по всему миру.

**GCC и NumPy:** NumPy вызывает OpenBLAS или MKL для матричных операций. OpenBLAS компилируется GCC с флагами `-O3 -march=native`. GCC auto-vectorization генерирует AVX2 инструкции, которые обрабатывают 4 double или 8 float за одну инструкцию. Без `-O3` NumPy был бы в 4-8 раз медленнее.

Внутреннее представление GCC - **RTL (Register Transfer Language)** - описывает программу как операции над абстрактными регистрами. Это предшественник SSA-формы LLVM. GCC имеет более 200 optimization passes, которые работают на уровне GIMPLE (высокоуровневый IR) и RTL (низкоуровневый). Монолитная архитектура GCC означает: добавить новый backend (новую архитектуру) - это недели работы. LLVM решит эту проблему модульностью.

**Почему Linux kernel использует GCC, а не Clang/LLVM:** GCC поддерживает расширения GNU C (`__attribute__`, `typeof`, вложенные функции), которые Linux kernel использует десятилетиями. Clang поддержку добавил позже, и с 2021 года Linux можно собрать обоими. Но GCC - исторически первый и остаётся основным toolchain для kernel разработки.

LLVM: модульная революция

2000 год. Университет Иллинойса. Крис Латнер начинает PhD-проект - **LLVM (Low Level Virtual Machine)**. Центральная идея: разделить компилятор на независимые части через общее промежуточное представление. Frontend (Clang для C/C++) → **LLVM IR** → Optimizer → Backend (x86/ARM/WASM). Любой язык, скомпилированный в LLVM IR, получает все оптимизации и все целевые архитектуры бесплатно.

**LLVM IR в SSA-форме:** каждая переменная присваивается ровно один раз (Static Single Assignment). Это упрощает анализ зависимостей и большинство оптимизаций. Phi-функции (`%x = phi [%a, %bb1], [%b, %bb2]`) обрабатывают merge points в control flow графе.

Apple приняла LLVM в 2005 году для Xcode. С тех пор экосистема росла лавинообразно: **Clang** заменил GCC во всей Apple-разработке, **Swift** использует LLVM backend (Swift → LLVM IR → ARM64 для M1/M2), **Rust** использует LLVM для всех оптимизаций (borrow checker работает до LLVM, LLVM генерирует машинный код). **Julia** JIT-компилирует через LLVM в рантайме. **Kotlin/Native** компилирует в нативные бинарники через LLVM.

**MLIR (Multi-Level IR)** - следующий шаг, разработанный в Google для TensorFlow XLA. MLIR позволяет определять кастомные IR диалекты для разных уровней абстракции: от ML-операций (матричное умножение) до аппаратных инструкций (TPU операции). PyTorch **TorchInductor** использует MLIR для компиляции Python-кода в GPU kernels в реальном времени.

**Clang vs GCC производительность:** в среднем Clang компилирует быстрее (меньше времени на компиляцию), GCC генерирует чуть более быстрый код для числодробилок (лучше auto-vectorization в ряде случаев). На практике разница в скорости бинарников - единицы процентов. Разница в developer experience (сообщения об ошибках, static analysis) - значительная в пользу Clang.

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

• **Fortran 1957:** первый высокоуровневый компилятор доказал, что машина может генерировать код не хуже человека. BNF - формальная грамматика языков - создана для Fortran и используется до сих пор
• **C 1972:** однопроходный компилятор + препроцессор + undefined behavior как фича. Thompson's Trusting Trust: бинарник компилятора может содержать backdoor, невидимый в исходниках
• **GCC 1987:** свободный компилятор, переживший десятилетия. RTL как IR, 200+ optimization passes, LTO для межфайловых оптимизаций. До сих пор собирает Linux kernel
• **LLVM 2000:** модульная архитектура frontend/IR/backend разделила компиляторостроение навсегда. LLVM IR в SSA-форме - общий язык для Rust, Swift, Julia, Kotlin. MLIR расширяет это на ML-компиляторы

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

История компиляторов проходит через всю CS - от теории языков до архитектуры процессоров:

• Архитектура компилятора — Модульность LLVM (frontend/optimizer/backend) - практическое воплощение принципов из этого урока
• Теория языков программирования — BNF, изобретённая для Fortran, стала основой формальных грамматик и теории языков
• Сложность алгоритмов — Optimization passes в GCC и LLVM реализуют алгоритмы с конкретными сложностями: O(n) constant folding, O(n²) some dataflow analyses
• Цикл инструкций CPU — LLVM backend генерирует инструкции для конкретного ISA - именно те, что CPU исполняет в instruction cycle

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

• Fortran до сих пор работает в ядре NumPy и PyTorch через BLAS. Это признак надёжности или технического долга? Когда имеет смысл переписывать 50-летний код, а когда - нет?
• Thompson показал: доверять нельзя даже исходникам компилятора, если бинарник скомпрометирован. Как diverse double-compilation решает эту проблему и почему это всё равно не абсолютная защита?
• LLVM победил GCC в экосистеме Apple/Rust/Swift благодаря модульности. Означает ли это, что монолитные архитектуры всегда проигрывают модульным в долгосрочной перспективе?

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

• comp-03-compiler-architecture — Архитектура компилятора (frontend/optimizer/backend) - то, что LLVM модуляризовал в 2000 году
• alg-01-big-o — Оптимизации GCC и LLVM реализуют те же алгоритмы сложности, что изучаются в теории алгоритмов
• arch-05-instruction-cycle — Instruction Set Architecture, которую генерирует LLVM backend - тема архитектуры компьютера
• plt-01-paradigms — Теория языков программирования и формальные грамматики - то, что Бэкус формализовал через BNF для Fortran