GHC изнутри

Весь блок про рантайм мы кружили вокруг одной машины. В уроке 32 смотрели, как thunk живёт в куче, в уроке 33 обещали, что fusion склеит конвейер в один цикл, в уроке 35 полагались на планировщик и зелёные потоки. Пора спуститься в машинное отделение и посмотреть, кто всё это обеспечивает. Сегодня проходим конвейер GHC от текста до машинного кода: парсер, тайпчекер, Core, симплифайер со всеми его трюками, STG, Cmm и бэкенды. По дороге учимся главному практическому навыку этого урока: читать то, что компилятор сделал с твоим кодом, потому что у каждой стадии есть свой флаг, который её распечатывает.

Идея: конвейер понижений

GHC старше многих его пользователей: проект стартовал в 1989 году, и за тридцать с лишним лет в нём накопилось всё, что наука знает о компиляции ленивых функциональных языков. При этом устроен он на удивление прозрачно. Это конвейер понижений: программа проходит через цепочку промежуточных представлений, и каждое следующее проще предыдущего синтаксически, но честнее операционно. Наверху богатый Haskell со всем сахаром. Внизу машинный код, где нет ни типов, ни лямбд, только регистры и переходы.

Весь маршрут в одной таблице. Третья колонка самая важная: каждое представление можно распечатать своим флагом, конвейер прозрачен насквозь.

Стадия	Представление	Что происходит	Флаг
парсинг	HsSyn GhcPs	текст становится деревом	-ddump-parsed-ast
rename	HsSyn GhcRn	имена находят свои определения	-ddump-rn
typecheck	HsSyn GhcTc	вывод типов, классы становятся словарями	-ddump-tc
desugar	Core	весь сахар раскрыт в крошечный язык	-ddump-ds
оптимизации	Core	десятки проходов Core в Core	-ddump-simpl
кодген, шаг 1	STG	аллокации и вычисления становятся явными	-ddump-stg-final
кодген, шаг 2	Cmm	переносимый ассемблер	-ddump-cmm
бэкенд	asm	NCG, LLVM, WebAssembly, JavaScript	-ddump-asm

Обрати внимание на пропорцию: три стадии наверху понимают твой исходник, а всё интересное для производительности происходит в середине, на уровне Core. Это сознательное архитектурное решение, описанное в главе про GHC в The Architecture of Open Source Applications: фронтенд большой и сложный, потому что Haskell большой и сложный, зато оптимизатор работает с языком из горстки конструкций, и каждую оптимизацию можно записать как простое переписывание дерева.

Фронтенд: parse, rename, typecheck

Первые три стадии работают с одним и тем же деревом HsSyn, но дерево это растёт. Тип у него параметризован стадией: HsSyn GhcPs после парсера, HsSyn GhcRn после renamer, HsSyn GhcTc после тайпчекера, и на каждой стадии в узлах появляются новые поля. Этот приём называется trees that grow, по одноимённой статье: вместо трёх почти одинаковых деревьев одно, расширяемое через type families.

Парсер. Лексер сгенерирован из Alex, грамматика из Happy, это Haskell-аналоги lex и yacc. На выходе чистый синтаксис: + в дереве это просто имя из одного символа, про которое неизвестно ничего, кроме места в файле. Здесь рождаются все parse error.

Renamer. Каждое имя привязывается к месту определения и получает уникальный идентификатор: x превращается в x_a1k4, + в GHC.Num.+. Заодно он разрешает импорты, проверяет области видимости, ловит дубли. Знакомое Variable not in scope живёт именно здесь, до всяких типов.

Тайпчекер. Самая большая и наукоёмкая часть фронтенда. Работает в два такта: сначала тайпчекер обходит дерево и собирает ограничения (что с чем обязано совпасть), потом решатель их разрешает. Алгоритм называется OutsideIn(X), и именно его расширяемость позволяет GHC тянуть GADT, type families и весь type-level зоопарк, который мы встретим в уроке 40. Для нас сейчас важны два выхода этой стадии. Во-первых, ошибки: No instance for и Couldn't match expected type рождаются в решателе ограничений. Во-вторых, elaboration: тайпчекер вписывает свои решения прямо в дерево. Каждое ограничение Num a становится конкретным словарём, тем самым, что мы разбирали в уроке про тайпклассы. После этой стадии вывод типов больше не нужен: всё выведенное записано явно.

Кстати, фронтендом GHC пользуешься не только ты при сборке. HLS в твоём редакторе это тот же фронтенд GHC, вызванный как библиотека: подсветка ошибок, типы при наведении, всё это parse, rename и typecheck без кодогенерации. А ghci прогоняет код через фронтенд и Core, а дальше вместо машинного кода генерирует байткод и крутит его интерпретатором, поэтому он стартует мгновенно, но числодробилки в нём медленные.

Core: весь Haskell в десятке конструкций

Дальше происходит самое красивое архитектурное событие конвейера: desugar. Весь синтаксис Haskell, сотни конструкций с учётом сахара, переписывается в Core, язык из одного типа данных примерно с десятью конструкторами:

data Expr b                  -- слегка упрощённый CoreExpr из исходников GHC
  = Var   Id                 -- переменная
  | Lit   Literal            -- литерал
  | App   (Expr b) (Expr b)  -- применение
  | Lam   b (Expr b)         -- лямбда
  | Let   (Bind b) (Expr b)  -- let-связывание
  | Case  (Expr b) b Type [Alt b]   -- разбор случаев
  | Cast  (Expr b) Coercion  -- смена типа по доказательству
  | Type  Type               -- тип как аргумент

do-нотация, guards, where, list comprehensions, классы, pattern matching по нескольким аргументам: всё это исчезает. Остаётся лямбда-исчисление с let, case и типами. Формально Core реализует System FC: полиморфное лямбда-исчисление, расширенное коэрциями, доказательствами равенства типов, без которых не выразить GADT и type families.

Ключевое слово здесь: типизированный. Большинство компиляторов выбрасывает типы после проверки. GHC несёт их через все оптимизации, и это не сентиментальность, а контроль качества: после каждого прохода оптимизатора можно включить Core Lint (-dcore-lint), быстрый тайпчекер, который проверяет, что проход не сломал типы. Оптимизация, которая ломает типы, почти наверняка ломает и семантику, и Lint ловит это в момент преступления, а не через десять проходов в виде segfault. Если когда-нибудь будешь писать плагин к GHC, этот флаг станет твоим лучшим другом.

Теперь главный практический навык. Core печатается флагом -ddump-simpl (после оптимизаций) или -ddump-ds (сразу после desugar), и в сыром виде он завален служебными деталями. Рецепт чтения, который стоит записать:

ghc -O2 -fforce-recomp Double.hs \
  -ddump-simpl -dsuppress-all -dsuppress-uniques

-dsuppress-all прячет аннотации, -dsuppress-uniques убирает суффиксы вроде _a1k4, -fforce-recomp заставляет перекомпилировать, даже если файл не менялся. Для функции double x = x + x получится примерно такое:

-- RHS size: {terms: 8, types: 3, coercions: 0, joins: 0/0}
double = \ x -> case x of { I# x# -> I# (+# x# x#) }

Разбор по словам. \ x -> это лямбда, как и была. case x of I# x# это форсирование: в Core case всегда означает вычислить до WHNF и разобрать результат, прямо как в уроке 08. I# это конструктор коробки Int: внутри лежит голый машинный Int#. А +# это уже не функция, а инструкция сложения. Заметь, чего тут нет: нет словаря $fNumInt, который был после desugar. Оптимизатор его съел, и это нормально. Если словари в горячем коде остались, значит специализация не сработала, и это первое, что ищут глазами в Core при разборе медленного кода.

Прокрути теперь весь спуск по конвейеру в виджете, первая вкладка. На каждой стадии смотри на чип с флагом: это та самая команда, которой ты можешь распечатать эту стадию у себя. Вторая вкладка пригодится чуть позже, в разделе про -O2.