PLComp

Использование рекомендательных систем для автонастройки компилятора, с учетом собранной ранее информации. Результаты внушают оптимизм.
A Collaborative Filtering Approach for the Automatic Tuning of Compiler Optimisations
https://arxiv.org/pdf/2005.04092.pdf

#autotuning #ml

SSA в историческом контексте. Очень хорошая систематизация знаний по теме.
Program Analisys and Transformation Survey and Links
https://github.com/pfalcon/awesome-program-analysis

#analysis #ssa

Очень доходчивый и практико-ориентированный разбор одной из ключевых статей в области супероптимизации на основе метода CEGIS. Автор даже не поленился расшифровать формулы из статьи для тех, кто сторонится математической нотации.
Synthesizing Loop-Free Programs with Rust and Z3
https://fitzgeraldnick.com/2020/01/13/synthesizing-loop-free-programs.html

#synthesis #smt

Halide — яркий пример современного и популярного DSL для высокопроизводительных вычислений (обработка изображений, нейросети). В работе по ссылке ниже представлена его формальная семантика. Достаточная, по большому счету, для разработки собственного компилятора Halide. Любопытно, что в описании трансляции в императивное представление использован формализм из области синтеза программ.
Formal Semantics for the Halide Language
https://www2.eecs.berkeley.edu/Pubs/TechRpts/2020/EECS-2020-40.pdf

#dsl #semantics #synthesis

Любопытная работа по применению методов машинного обучения без учителя (Q learning) для разработки адаптивного сборщика мусора. Впрочем, полученные в статье результаты пока не очень впечатляют.
Learned Garbage Collection
https://arxiv.org/pdf/2004.13301.pdf

#gc #ml

Возможно, вы уже слышали новость о древнем GW-BASIC. Компания Microsoft выложила исходники интерпретатора на github: https://devblogs.microsoft.com/commandline/microsoft-open-sources-gw-basic/

В заметке по ссылке есть одна интригующая фраза: "Microsoft was able to generate a substantial amount of the code for a port from the sources of a master implementation. (Alas, sorry, we’re unable to open-source the ISA translator.)". И действительно, текст на языке ассемблера для 8088 был получен автоматически с помощью специального транслятора. При этом даже комментарии в коде остались нетронутыми, там речь идет, судя по всему, о 8080.

В статье из журнала Byte за 1982 год сравниваются возможности трех трансляторов, которые автоматически преобразуют код 8-битных процессоров 8080/Z80 для CP/M в 16-битный код 8088/8086 для MS-DOS: https://tech-insider.org/personal-computers/research/acrobat/8206-b.pdf

Особенно выделяется среди этих трансляторов XLT86 (8080 -> 8086) от компании Digital Research. Этот транслятор — детище Гэри Килдалла, о котором специально говорить, наверное, нет необходимости. В области построения компиляторов Килдалл известен своей работой A unified approach to global program optimization (1973): https://dl.acm.org/doi/pdf/10.1145/512927.512945

Статья Килдалла до сих пор находится в числе самых цитируемых по компиляторной тематике и речь идет об алгоритме анализа потока данных, который позже был описан во множестве учебников и применяется в самых современных компиляторах: http://compcert.inria.fr/doc-1.6/html/Kildall.html

Вернемся, однако, к XLT86. К счастью, сохранилась документация к транслятору: http://www.s100computers.com/Software%20Folder/Assembler%20Collection/Digital%20Research%20XLT86%20Manual.pdf

Из нее можно узнать, в частности, что:

1. Трансляция состоит из 5 фаз.
2. В начале определяются линейные участки и строится граф потока управления. Затем проводится глобальный анализ потока данных для определения "живых" регистров и флагов процессора.
3. Сам процесс "выбора команд" элегантно описан табличным образом. Некоторые правила преобразований являются условными и зависят от ранее полученных результатов анализа потока данных.
4. Транслятор написан на ЯП PL/I-80 и имеет ограничение на размер входной программы — не более 6 Kбайт.

#history #analysis

Особенно же интересными (субъективно, разумеется) событиями симпозиума по Лиспу оказались: доклад и семинар по передовому фреймворку (набор eDSL на языке Scheme) для быстрой разработки компиляторов Nanopass. По Nanopass как раз не хватало свежей, актуальной информации в авторском изложении.

Доклад The Nanopass Framework as a Nanopass Compiler
Слайды: https://www.european-lisp-symposium.org/static/2020/keep-slides-keynote.pdf
Видео: https://www.youtube.com/watch?v=lqVN1fGNpZw

Семинар Mixing Mutability into the Nanopass Framework
Слайды: https://www.european-lisp-symposium.org/static/2020/keep-slides-workshop.pdf
Видео: https://www.youtube.com/watch?v=wTGlKCfP90A

#langworkbench #dsl

Недавно (27-28 апреля, 2020) состоялся европейский симпозиум по Лиспу.

European Lisp Symposium
https://www.european-lisp-symposium.org/2020/
Видеозаписи докладов: https://www.youtube.com/playlist?list=PLA66mD-6yK8yjlJCI0Ay2f2IvvmB9Ktga

Ниже краткая информация о 3 докладах по околокомпиляторной тематике:

Partial Evaluation Based CPS Transformation: An Implementation Case Study
Описание компилятора для диалекта Лиспа pLisp. В компиляторе используются частичные вычисления и CPS.
Слайды: https://www.european-lisp-symposium.org/static/2020/jayaprakash-slides.pdf
Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf

LLVM Code Generation for Open Dylan
Dylan — это диалект Лиспа с Алгол-подобным синтаксисом. В начале 90-х этот язык развивался компанией Apple. В докладе представлено описание генератора кода для Dylan на основе LLVM.
Слайды: https://www.european-lisp-symposium.org/static/2020/housel-slides.pdf
Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf

Later Binding: Just in Time Compilation of a Younger Dynamic Programming Language
Краткий анализ компилятора LuaJIT
Видео выступления: https://www.youtube.com/watch?v=FBk5XAEhu2s
Текст доклада в сборнике: https://www.european-lisp-symposium.org/static/proceedings/2020.pdf

#conf #jit #llvm #cps #pe

A Language for Describing Optimization Strategies
Пример использования стратегического переписывания термов в духе Stratego. В статье демонстрируются оптимизирующие преобразования на Scala, для GPU и других ускорителей.
https://arxiv.org/pdf/2002.02268.pdf

#optimization

Работа по синтезу программ с использованием Rosette (Racket). Cинтезируется JIT-компилятор DSL BPF (ядро Linux) в машинный код (в примере использован RISC-V)
Synthesizing JIT Compilers for In-Kernel DSLs
https://www.cs.utexas.edu/~isil/jitsynth.pdf

Подробности о BPF VM:
BPF: A New Type of Software
http://www.brendangregg.com/blog/2019-12-02/bpf-a-new-type-of-software.html

#synthesis #jit

Полезная ссылка для участия в спорах на тему, какой ЯП выбрать для реализации компилятора
Comparing the Same Project in Rust, Haskell, C++, Python, Scala and OCaml
https://thume.ca/2019/04/29/comparing-compilers-in-rust-haskell-c-and-python/

Работы Ian Piumarta, участника проекта STEPS

Maru
Миниатюрный расширяемый Лисп-подобный язык с компилятором в IA32-код. Использовался в проекте STEPS.
Open, extensible composition models
https://www.piumarta.com/freeco11/freeco11-piumarta-oecm.pdf
STEPS Toward the Reinvention of Programming, 2012 Final Report
http://www.vpri.org/pdf/tr2012001_steps.pdf

PEG-based transformer provides front-, middleand back-end stages in a simple compiler
http://www.vpri.org/pdf/tr2010003_PEG.pdf
Шедевр изящества и миниатюризации в области генераторов компиляторов.

#lisp #metacompiler

В стадии call for papers

Конференция по ЯП с управляемым кодом и VM
MPLR 2020
Ноябрь 4-6, 2020
https://mplr2020.cs.manchester.ac.uk/index.php/mplr/call-for-papers

Симпозиум по ЯП и системам
APLAS 2020
30 ноября 2020
https://conf.researchr.org/home/aplas-2020

#conf