https://ruslanspivak.com/lsbasi-part1/

Интересный цикл статей о создании интерпретатора/компилятора с нуля. Обычно англоязычные статьи советуют использовать готовые либы типа Lex/Yacc, LLVM и пр. Сам процесс синтаксического и семантического разбора при этом скрыт от читателя.

вот такое скидывали тут, насколько я смог понять, автор избегает автоматизированные тулзы и всё показывает "с низов"

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

Ну разве что LLVM делает оптимизации и генерацию машинного кода и в принципе если хочется, то можно её выкинуть и сделать руками.

Но сама реализация семантики и кодогенерации (даже если происходит генерация llvm кода) всегда отдаётся создателю компилятора/интерпретатора. А это же самая мякотка

А как в настоящее время дела с созданием самоприменимого специализатора? Это из проекции Футамуры-Турчина. Штука как вроде волшебная.. есть ли прогресс?

Японцы пытались, но из-за накопления ошибок у них всё расползлось, насколько я помню. Недавно в моде была супекомпиляция, но к ней чёрт знает с какой стороны подступаться.

Даже optimal evaluator и то понятнее

Размещение сотен промежуточных значений современных программ в десятках регистров типичных процессоров - одна из первых проблем, с которой столкнулись разработчики языков высокого яровня. Со временем было показано, что в общем случае задача распределения регистров является NP-полной, что предполагает множество эвристических и частичных решений.

"A survey on register allocation" - обзор темы РР на 2008 год с пояснением ключевой терминологи и перечислением наиболее эффективных подходов к проблеме.

Много внимания уделяется вариантам алгоритмов раскраски графа, линейного сканирования (linear scan) и перспективным на момент написания статьи альтернативным подходам (целочисленное линейное программирование, multi-commodity flow problem и др.).

В 2008 году все крупные компиляторы перешли к использованию внутренних представляний со статически однократным присваиванием (SSA). Поэтому естественно, что половина обзора посвящена рассмотрению полезных в РР свойств популярнейшего представления и адаптации ключевых алгоритмов к нему.

Интересно, что в обзоре почти не упоминаются легковесное локальное (внутри базовых блоков) РР и тяжелое точное РР; рассматриваются прежде всего популярные в больших промышленных компиляторах решения.

Материал написан доступно и явно ориентирован на введение в курс дела старшекурсников или аспирантов; автор не только разбирается в материале, но и умеет его донести.

http://compilers.cs.ucla.edu/fernando/publications/drafts/survey.pdf

И мой комментарий к комментарию https://t.me/plcomp/64 по "A Survey on Register Allocation".

Статья-обзор по алгоритмам распределения регистров. Автор старается простыми словами объяснить на ходу базовую терминологию, чтобы читателю не пришлось на каждом шагу сверяться с другими источниками. В этом смысле содержание обзора можно было бы назвать доходчивым. Но, казалось бы, это не большое достижение -- на тему распределения регистров есть разделы в известных учебниках, а проект LLVM, кажется, вообще закрыл эту тему для компиляторщиков, мол, бери готовое и не думай, как оно устроено.

А теперь перейду к сути. Fernando M Q Pereira, автор рассматриваемого обзора, один из признанных современных специалистов в области распределения регистров. F.M.Q. — автор передового алгоритма Puzzle Solving и даже имеет патент на него. Что касается самого обзора, то это, на мой взгляд, обязательное чтение для компиляторщика-профессионала, которого интересуют вопросы порождения целевого кода, особенно для нетрадиционных, неортогональных архитектур. И при всей своей внешней доходчивости это нелегкое чтение, требующее серьезной квалификации.

В обзоре рассматриваются как классические подходы, так и подходы передовые, специализированные. Передовые настолько, что в реализации LLVM вы их не встретите. Речь, например, о распределении регистров прямо в форме SSA, а также о более экзотических техниках, в духе PBQP.

Важно, что перед нами действительно научный обзор, поэтому автор не скупится на изложение важных теоретических результатов. На этот счет, в частности, есть очень ценный, заключительный раздел по NP-полным (современным!) результатам из области распределения регистров.

#regalloc #survey

Значит в тему будет и это видео про применение машинного обучения для аллокации регистров https://youtu.be/4FW7iznzIoE

если кто-то таки читал статейки выше - какой из способов аллокации регистров самый легкий в плане затрат времени и памяти и понимания программистом? в ущерб оптимальности генерации кода

См., к примеру, https://t.me/plcomp/3

ссылка1 и ссылка2 крашат мою читалку пдф (у меня их две. обе падают. андроид)

третья работает, но там требования 150кб и довольно продвинутые идеи (поиск горячих мест)

Возможно, полезнее начать с "литературы" в описании чата.

посмотри видосики, может так не покрашит )

Гм. В книге a retargetable c compiler описан простой и популярный метод. В engineering a compiler аж два простых локальных алгоритма.

Самое простое, что я видел -- linear scan

Но литературу надо читать, безусловно :)