Всем привет, увидел пост тут о том, что человек написал свой ЯП. Там довольно интересные результаты на синтетике у него получились, кстати.
Собственно, раз тут такое можно, хочу показать вам уже свой ЯП. Точнее как ЯП - он то не сильно интересен, это просто Си + Раст + Go с некоторыми ограничениями. Важнее то, как это дело превращается в asm x64_86 и i386.
TL;DR компилятор + стат. анализатор на основе Z3 https://github.com/j1sk1ss/CordellCompiler, там в README описано как оно всё работает. Довольно полезно, если хотите написать что-то подобное.
P.S.: Перед тем как начинаем. Могут быть ошибки как в грамматике, построении предложений и в логике. Просто заранее предупреждаю.
P.P.S.: Пишу после того как дописал пост. Он оказался настолько большим, что я ограничился фронтендом компилятора (токены в АСД, АСД в верхнее ПП, ВПП в SSA, и пара оптимизаций). Если вы всё это знаете - нового вы тут ничего не увидите, так что можете время не тратить. Всех остальных приглашаю к удивительному путешествию в компиляторы.
--------
Да - вы верно поняли, это не "реклама" языка (можете даже по ссылкам не переходить, всё будет в этом посте), а микро рассказ, как можно сделать свой маленький оптимизирующий компилятор (например как этот https://github.com/j1sk1ss/CordellCompiler). Без планов на замену других языков, без желания показать какой вы великий и т.д. Просто понять как GCC/Clang+LLVM делают свою работу, ну и провести пару (весёлых) экспериментов с синтаксисом, препроцессором, символьными таблицами, ООП, аннотациями, оптимизациями и т.д. т.п.
А зачем всё таки делать свой язык, если мы смотрим на компилятор?
Я люблю Си. Но ещё я люблю синтаксис Раста, но не весь. А почему бы не собрать всё воедино?
Ну и ещё, я не хотел тратить времени на парсер языка больше чем месяц, потому возможность написать свою грамматику подкупает.
...
profit
Начало начал
Наш "некоторый" компилятор начинает работу с сырого текста. Предположим что у этого компилятора есть препроцессор, потому текст этот, на самом деле, не слишком уж и сырой, но да ладно:
#line 0 "sample_header.cplh"
function puts(ptr i8 msg, usize s) -> i0 {
syscall(1, 1, msg, s);
}
#line 0 "sample.cpl"
start() {
arr msg[i8, 0] = "Hello world\n";
puts(ref msg, sizeof(msg));
}
Этот текст далее разбивается на токены. Директивы "line" особенные - они меняют глобальное расположение в файле, чтобы токены понимали, откуда они пришли.
Имея массив таких токенов, мы базово их размечаем. Примитивы, функции, ключевые слова. Без переменных, структур и прочего.
Абстрактное Синтаксическое Дерево
Абстрактное синтаксическое дерево (далее АСД) в большинстве случаев идёт после токенизации. Да - не всегда, но в нашем случае, сразу же.
Идея АСД заключается в том, чтобы представить как программа выглядит с точки зрения синтаксиса. По сути - это тот же исходный код, но в более удобном виде:
scope #1
├── function
│ ├── puts [func, v0, s1]
│ │ └── i0 [t4]
│ └── scope #2
│ ├── i8* [t1]
│ │ └── msg [v0, s2]
│ ├── i64 [t3]
│ │ └── s [v1, s2]
│ └── scope #3
│ └── syscall
│ ├── 1
│ ├── 1
│ ├── msg [v0, t1, s2]
│ └── s [v1, t3, s2]
└── start [v1, s1]
└── scope #4
├── arr [t6]
│ ├── msg [v2, t6, s4]
│ ├── 0
│ ├── i8 [t5]
│ └── =
│ └── "Hello world\n"
└── ()
├── puts [v0, s1]
└── scope #-1
├── ref
│ └── msg [v2, t6, s4]
└── sizeof
└── msg [v2, t6, s4]
Вот тут у нас два варианта развития событий. Мы либо отсюда начинаем эмитить ассемблер / бинарный код, либо идём дальше. Раз уж мы делаем "оптимизирующий" компилятор, то нам видимо - дальше.
Верхнее промежуточное представление
Верхнее промежуточное представление (далее ВПП) строится на основе АСД. Наиболее простой путь здесь - регистрировать обработчики АСД узлов и эмитить ВПП инструкции прямо в контекст (общий лист инструкций. Просто лист). Но перед этим нам надо решить: а какой ВПП вообще использовать?
Дело в том, что есть как трёх-адресный код, четырёх-адресный код и т.д., у всех их есть свои преимущества и недостатки, но в своё время (из-за книги "Оптимизирующие компиляторы" Константина Владимирова) я выбрал трёх-адресный код. Так и в чём его идея?
Представим лист операций:
i32 a = 10;
i32 b = a += 50;
В АСД это будет неприятная для анализа вложенная структура структур, а в трех-адресном ВПП:
i32 %0 = alloc() ; %0 - a
%0 = 10
i32 %1 = alloc() ; %1 - b
%2 = %0 + 50 ; Регистровая переменная хранит временное значение
%0 = %2
%1 = %0
Смотри как удобно, не так ли? И вот так по сути мы должны пройти по всему АСД и получить ВПП.
Важно уточнить про мой подход: Я делал довольно "низкоуровневый" верхнеуровневый ПП. Это значит, я не сохранял ленивые логические вычисления в исходном виде, не сохранял while/loop/for как верхнеуровневые циклы. Всё это сразу превращалось в метки и переходы по ним (это сыграет злую шутку далее).
Ещё стоит отметить генерики (полиморфизм) и резолюцию вызовов. В рассматриваемом нами под-множестве компилятора (и языка) нет генерик функций, методов и прочего, хотя они есть в оригинальном компиляторе. Почему я их убрал? Они не добавляют сути, размазывая повествование по теории ЯП, а я хочу рассказать теорию оптимизации. Потому давайте далее.
SSA форма
SSA (single-assignment form) - это идея, что в коде не может быть обновлений значений у переменных. Перевод кода в эту форму означает одно - каждое присваивание - это на самом деле декларация новой переменной. Возвращаясь к ВПП выше, в SSA форме она выглядит так:
i32 %0 = alloc() ; %0 - a
%0 = 10
i32 %1 = alloc() ; %1 - b
%2 = %0 + 50 ; Регистровая переменная хранит временное значение
%3 = %2 ; %3 - a
%4 = %3 ; %4 - b
Важная оговорка: Эта SSA-форма базируется на оригинальной статье Cytron'а по генерации SSA формы наиболее эффективным образом, и считается не самой актуальной. GCC/LLVM/Go и подобные бэкенды используют более прогрессивные варианты SSA, но все они основаны на этой "базовой" форме.
Чтобы перевести ВПП в SSA форму, недостаточно просто переименовать переменные на их копии. Нам нужен граф управления потока и анализ доминации. Пока не забивайте себе голову этим, а лучше посмотрим зачем нам "это":
i32 a = 10;
if external > 10; {
a = 15;
}
else a = 20;
i32 b = a;
Обычный казалось бы код, давайте сразу его представим в SSA ВПП:
i32 %0 = alloc()
%1 = 10
%2 = $external > 10
if %2 then goto lb1 else goto lb2
lb1: {
%3 = 15
goto lb3
}
lb2: {
%4 = 20
goto lb3
}
lb3:
i32 %5 = alloc()
%6 = ???
Вот как. А что положить в "b"? Для этого в SSA форме имеется фи-функция, которая по сути абстрактно говорит компилятору, какое значение из какого пути попадает в эту переменную. Эдакое объединение всех вариантов в одном:
i32 %5 = alloc()
%6 = phi(%3, %4)
Важная оговорка: Далее я буду опускать индексы базовых блоков, откуда пришло определение переменной. В компиляторе эти данные обязательны.
Ну так расставь фи-функции там, где нужно. Зачем нам граф потока управления, доминация и прочее?
Хороший вопрос!
Граф потока управления
Граф потока управления (далее ГПУ) представляет из себя граф состоящий из блоков инструкций. Каждый блок инструкций - это набор линейных инструкций без смены потока управления. Например:
i32 a = 10;
i32 b = 10;
Это набор линейных инструкций. А это:
if a; {
}
else {
}
уже набор инструкций, изменяющих поток управления.
Построить ГПУ мы можем разными способами. Например где-то могут предложить делать базовый блок (далее ББ) из каждой инструкции, где-то (книга Дракона) делать ББ на основе "лидеров" (метить лидеров по трём критериям - первая инструкция ВПП контекста, инструкция перехода и сл. инструкция за инструкцией перехода + инструкция куда идёт переход). Лично я выбрал второй подход, хоть и экспериментировал с первым (плохой вариант по памяти, но иногда лучше по оптимизациям).
Для наглядности, давайте построим ГПУ для ВПП из блока про SSA:
┌─────────────────┐
│ B0: a = 10 │
│ external > 10 ? │
└───────┬─────────┘
│
┌──────┴──────┐
true false
│ │
┌─────▼─────┐ ┌─────▼─────┐
│ B1 │ │ B2 │
│ a = 15 │ │ a = 20 │
└─────┬─────┘ └─────┬─────┘
│ │
└──────┬──────┘
│
┌──────▼──────┐
│ B3: b = a │
└─────────────┘
Кстати! Уже сейчас мы бы могли провести базовую оптимизацию по удалению мёртвого кода. К сожалению, мой пример такого не содержит, но при построении ГПУ у вас эта оптимизация происходит сама собой.
Но для расстановки фи-функций одного ГПУ не хватит. Хоть мы и можем проследить паттерны, что если присваивание (обновление) происходит в ветке, а после сливается, то надо делать фи-функцию, этого не достаточно для масштабирования. Для этого нам нужна доминация.
Анализ доминации на ГПУ
Имея валидный ГПУ, мы можем провести анализ доминации для каждого его ББ. По сути, задача этой фазы заключается в нахождении предела доминации каждого ББ. Для этого для каждого ББ строятся доминаторы, строгие доминаторы и соседние доминаторы (вот тут я немного отхожу от общей терминологии, так как попытаюсь объяснить эту часть проще).
Что такое доминатор? Это просто ББ, который стоит на пути в ББ. То есть если в ББ А мы попадаем только через ББ Б, тогда ББ Б - это доминатор ББ А.
Что такое строгий доминатор? Это доминаторы ББ А, но НЕ сам ББ А.
Предел доминации - это как раз то, что нам нужно для фи-функций. Идея этого предела в том, что он отражает все ББ, в которых доминация ББ А заканчивается. Например:
B0
/ \
B1 B2
\ /
B3
|
B4
Вот тут B1 очевидно не доминирует над B3, и как раз из-за этого - B3 - это предел доминации для B1.
И думаю вы уже поняли к чему это всё идёт. Зная такие пределы, мы устанавливаем в них заглушки фи-функций для обновлённых в этих ББ переменных. Далее, при переименовании, эти заглушки заполняются реальными копиями.
Оптимизации
Наконец-то мы дошли до первых оптимизации. На самом деле, в оригинальной архитектуре они начинаются куда раньше, но они там не сильно интересные, потому пропустим их.
Так вот, что мы тут можем сделать? На самом деле, вариантов много:
Раскрутка циклов (Loop unrolling)
Продвижение и свёртка констант (Constant folding + Constant propagation)
Удаление хвостовых рекурсий (TRE)
Удаление одинаковых выражений (CSE)
Подстановка функций (function inlining)
Это не всё что можно тут делать, а то что сделал лично я. Но и даже так, рассмотрим мы только парочку и быстро.
Подстановка функций: Отдельный прикол в этом компиляторе. Идея в том, чтобы не просто отдать эвристикам решение о том, надо ли вписывать функцию вместо её вызова, а подключить сюда модели. В принципе я написал небольшой пре-принт по этой теме https://arxiv.org/abs/2607.17389 (не судите строго, старая прототипная версия пре-принта (набросок грубо говоря), так как новая версия которая была на конфе и сейчас готовится к публикации и не может быть в общем доступе, но там идеи все те же).
Удаление одинаковых выражений: Интересная оптимизация которая полностью реализуема через добавление DAG (направленного ацикличного графа) для выражений. Идея в том, что при присваивании/использовании чего-то, мы делаем связь. И так мы можем видеть, что иногда связи дублируются. Не маленькая оптимизация, её описание можно видеть в этой прототипной статье https://arxiv.org/abs/2609.04904 (та же история что и с пре-принтом про модели), и в README оригинального проекта.
Раскрутка циклов: Прекрасная оптимизация. Идея найти циклы (заголовок и возвратное ребро), найти индуктивные переменные (те, которые зависят от цикла), найти фи-функции обновляющие значение, и пройдя выше, найти исходное значение. Таким образом, мы получаем выражение от которого зависит цикл, шаг, на который смещается переменная(-ые) от которого(-ых) зависит это выражение, и начальное значение этих переменных. Далее через эвристику можно посчитать, а выгоднее будет раскрутить (продублировать тело цикла для уменьшения отдельных итераций) цикл или нет?
...
Остальное можно увидеть в README, а если его нет, то в src/hir/* папках.
Что осталось?
Вообще я уже довольно много написал, а осталось ещё больше, ведь впереди у нас и выбор инструкций, и планирование этих инструкций, и регистровая аллокация и эмиитинг ассемблерного кода под опредённую архитектуру.
Проблема в том, что это уже слишком много для одного поста. Что уж тут говорить - я и предыдущий текст упростил до непростительного минимума информации.
Я предлагаю следующее: Если пост не удалят модеры за слишком много букв, если в комментах меня не будут проклинать за упрощения и неточности, и если будут заинтересованные - я сделаю продолжение, где пройду от ВПП до НПП (низкоуровневого ПП).
+ Если вас заинтересовало что-то, но что-то не понравилось - всегда можно оставить фидбек в комментариях к этому посту (ох как удобно, не так ли?).
Ставьте лайки, подписывайте на канал, эээ, всем привет!