lcc-wasm: компилятор C, который компилирует сам себя в WebAssembly

Как я научил маленький компилятор C выдавать WebAssembly — а потом скомпилировал им самого себя, чтобы C компилировался прямо в браузере.

  • Демо — компилятор C в веб-странице: пишете код, жмёте кнопку, он тут же компилируется и запускается
  • Репозиторий

Цель

Хотелось компилировать C прямо в браузере — без сервера. Сначала была мысль пойти в лоб: скомпилировать сам Emscripten вместе со всем LLVM в wasm и запустить это в браузере. Но довольно быстро стало понятно, что даже в случае успеха результат вышел бы многомегабайтным — десятки, если не сотни мегабайт. А это убивает всю идею: такой «компилятор» в веб-странице никто не станет грузить и ждать. Значит, компилятор нужен изначально маленький.

Я взял LCC — учебный ретаргетируемый компилятор ANSI C Криса Фрейзера и Дэвида Хэнсона, тот самый из книги «A Retargetable C Compiler». Весь компилятор — около 16 тысяч строк чистого переносимого C. И задача распалась на две:

  1. Научить LCC выдавать WebAssembly — написать новый бэкенд.
  2. Скомпилировать сам LCC в wasm — чтобы компилятор работал в браузере.

А в идеале — соединить: взять компилятор-в-wasm и скомпилировать им же его собственный исходник. Самохостинг.

Как это работает

LCC устроен удобно: фронтенд (лексер, парсер, типы) отдаёт бэкенду маленькое типизированное IR — дерево операций, и каждый бэкенд под конкретную машину — это отдельный небольшой файл. Я добавил src/wasm.c.

Несколько наблюдений сделали бэкенд маленьким:

  • IR уже в постфиксном порядке (сначала операнды, потом операция) — а это ровно порядок стековой машины WebAssembly. ADDI4 → i32.add, INDIRI4 → i32.load, и так почти всё один-в-один. Никакого распределения регистров не нужно.
  • Бэкенд выдаёт текст .wat, а бинарный wasm из него собирает wabt (wat2wasm). Не пришлось писать бинарный энкодер.
  • Управление потоком — единственное действительно сложное место. LCC выдаёт goto-стиль (метки и переходы), а в wasm только структурное управление (block/loop/if). Решается приёмом «гигантский цикл + br_table»: каждый базовый блок — это ветка br_table по переменной-состоянию, каждый переход — «присвоить состояние, прыгнуть в диспетчер».
  • Память: линейная память wasm + теневой стек для локальных переменных, у которых берут адрес; глобальные и строки — в сегменты (data); указатели на функции — через таблицу и call_indirect.

Всё, что программе нужно снаружи (ввод-вывод), она получает через импортированные функции — браузер их и предоставляет.

Как выглядит трансляция

Покажу на пальцах. Вот функция:

1
int f(int a, int b) { return a * b + 7; }

Фронтенд LCC выдаёт промежуточное представление (IR) в постфиксном порядке — сначала операнды, потом операция. А это ровно порядок стековой машины, поэтому бэкенд переписывает IR в wasm почти дословно:

1
2
3
4
5
6
7
8
9
LCC IR            WebAssembly
ADDRFP4 0         local.get 0      ; a
INDIRI4
ADDRFP4 4         local.get 1      ; b
INDIRI4
MULI4             i32.mul          ; a * b
CNSTI4 7          i32.const 7
ADDI4             i32.add          ; + 7
RETI4             return

Соответствие операций почти один-к-одному (суффикс I4/U4/F8 выбирает i32/i64/f32/f64):

LCC IR wasm
ADDI4 i32.add
MULI4 i32.mul
DIVI4 i32.div_s
CNSTI4 n i32.const n
INDIRI4 i32.load
ASGNI4 i32.store
(unsigned char) i32.const 255 + i32.and

Последняя строка — забавная тонкость: в WebAssembly нет 8-битных типов, char живёт в i32, поэтому приведение к unsigned char обязано явно занулить старшие биты. Стоит про это забыть — и любой байт ≥ 128 в данных портится (ровно такой баг я недавно и ловил).

Единственное по-настоящему сложное место — управление потоком. LCC выдаёт goto-стиль (метки и переходы), а в wasm только структурные block/loop/if. Бэкенд решает это приёмом «гигантский цикл + br_table»: каждый базовый блок — ветка br_table по номеру-состоянию, каждый goto — «записать состояние и прыгнуть в начало цикла». Любой for/while/switch превращается в такую таблицу переходов.

Полный разбор — с таблицей опкодов LCC↔WAT и примерами для циклов, памяти, указателей и приведений типов — лежит в репозитории: doc/wasm-codegen.md.

Самохостинг

Дальше — самое интересное. Я склеил весь исходник LCC (плюс крошечный libc) в один файл и скомпилировал его нашим же rcc -target=wasm. Получился rcc.wasm — компилятор C размером ~260 КБ, целиком работающий как WebAssembly.

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

В демо видно весь конвейер: rcc.wasm компилирует ваш C в .wat, wabt собирает его в бинарь, браузер запускает. Компилятор C, который сам является WebAssembly, компилирует и выполняет C — без единого сервера.

Про размер

Размер здесь — не деталь, а вся суть; ради него всё и затевалось.

  • Сам компилятор rcc.wasm — около 280 КБ. Это весь компилятор C целиком: лексер, парсер, типы, кодогенерация и сборщик бинарного wasm. Грузится мгновенно.
  • Скомпилированный hello-world — 223 байта wasm. Не килобайта — байта. LCC не тащит за собой рантайм: всё, что программе нужно снаружи, импортируется у хоста.

Для контраста: clang + LLVM — это сотни мегабайт нативного кода, и даже простой wasm-бинарник, собранный через Emscripten, из-за рантайма легко весит десятки килобайт. Здесь и сам компилятор, и его результат — на порядки меньше. Именно это превращает «компилятор C в браузере» из трюка в рабочую вещь.

Сначала компилятор выдавал текстовый .wat, и в браузере его приходилось собирать в бинарь ассемблером wabt — а это 670 КБ, тяжелее самого компилятора. Поэтому я научил бэкенд выдавать бинарный .wasm напрямую — и wabt удалось выкинуть совсем. Теперь демо грузит только сам компилятор (280 КБ) и собирает модуль прямо внутри себя, без единой внешней зависимости.

Про слегка устаревший C

Стоит честно сказать: LCC — это ANSI C, он же C89 (стандарт 1989 года). Это слегка устаревший диалект. Привычного из C99 здесь нет: нельзя объявить переменную в заголовке for (int i = ...), нет //-комментариев по стандарту, объявления должны идти в начале блока, никаких VLA и inline. Реальный современный код приходится чуть причёсывать под C89.

Но для этой задачи это скорее плюс: язык компактный, компилятор маленький, всё помещается в браузер. А C89 — это ровно тот C, на котором написаны тонны классического софта; для него это естественная среда.

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