12/03/2021, Alexander Tchitchigin¶
https://hal.inria.fr/hal-01499946/document “A modular module system”, Xavier Leroy
Утверждение, что (ML-style) система модулей не зависит от “базового” языка программирования, и может быть реализована почти для любого, а не только ML, широко известно и озвучивалось в литературе. Данная статья приводит конструктивное доказательство этого тезиса, реализуя такую (слегка упрощённую) систему модулей, в виде, явно параметризованном относительно синтаксиса и системы типов базового языка.
Несмотря на ряд упрощений по сравнению с системой модулей того же Standard ML, представленная модельная система содержит (и корректно реализует) все базовые возможности, включая структурную типизацию модулей, абстрактные типы, функторы, зависимость (типа) результата функтора от (типа) аргумента а также равенства между (абстрактными) типами.
All in all, module type matching resembles subtyping in a functional language with records, with some extra complications due to the dependencies in functor types and signatures.
Статья составлена в духе Literate Programming, перемежая пояснительный текст и реальный рабочий код на языке OCaml. Реализация системы модулей ML с помощью системы модулей ML отсылает к традиции метациркулярных интерпретаторов Лисп. Леруа выражает надежду, что такой способ представления материала не только не запутает читателя, но и дополнительно прояснит связь конкретного и абстрактного синтаксиса как и практическую полезность (и даже необходимость) всех возможностей представленной системы. (По-видимому, метациркулярность системы не оставила Лисперов равнодушными, что привело к появлению реализации MiniML с полноценной системой модулей на Scheme: http://wiki.call-cc.org/eggref/4/miniML 😊)
Для иллюстрации приводятся два примера “надстраивания” реализованной системы модулей над “упрощённым C” в качестве императивного (процедурного) базового языка и Mini-ML в качестве функционального, приближенного к используемым на практике, в частности, реализующего типы высших порядков (Higher-Kinded Types).
Кратко обсуждаются вопросы (модульной) компиляции таких модулей. Упоминаются три основных варианта: компиляция самих модулей в виде структур данных, а функторов — в виде (полиморфных) функций, специализация функторов для всех применений в духе C++ templates и полное стирание модулей во время компиляции (аналогично девиртуализации вызовов методов в ООП). Но за деталями интересующиеся читатели отсылаются к соответствующим публикациям.
В заключительной части Леруа обсуждает ряд расширений модельной системы модулей — как реализованных на практике, так и не до конца проработанных даже в теории — но уже без фактической реализации.
Таким образом, статья представляет собой практическое введение в ML-style системы модулей и связанные вопросы, полезное как для пользователей таких систем, так и для авторов языков программирования, желающих реализовать собственную систему модулей. 😊
#leroy #modules #classic #ocaml #sml
17/02/2021, Vladimir Kazanov¶
Распределение регистров и планирование инструкций - важные аспекты реализации бэкенда компилятора. Обе задачи NP-полны и связаны между собой: распределение может внести в код новые инструкции, планирование же меняет инструкции местами. Несмотря на это в популярных компиляторах решаются они, как правило, раздельно и используют эвристические подходы.
Последние два десятилетия много исследований было посвящено точным комбинаторным методам решения тех же самых задач: предложены методы на основе целочисленного программирования, PBQP, программирования в ограничениях и др. Слабость таких подходов - большое время поиска оптимальных решений, что заставляет исследователей упрощать задачу, делая методы неприменимыми в универсальных компиляторах.
Роберто Лозано (Roberto Castaneda Lozano) задался целью разработать одновременно точный и легкий в реализации подход, причем решающий задачи планирования инструкций и распределения регистров совместно. За основу он взял программирование в ограничениях (constraint programming), позволяющее удобно выразить условия обеих задач и для которого существуют мощные решатели.
Проект Unison заменяет три фазы LLVM: предварительное планирование инструкций, распределение регистров и финальное планирование. Распределение проводится глобальное, планирование же локальное - последнее упрощение дает ощутимый эффект при умеренной сложности.
В отличие от предшественников Unison не упрощает задачу распределения. Все практические аспекты проблемы учитываются в решениях: спиллинг, алиасинг (aliasing), рематериализация (rematerialisation), разбиение областей жизни переменных (live range splitting), слияние (coalescing) и др. Программирование в ограничениях позволяет выразить любые проблемы распределения регистров лаконично и просто.
Оптимальность имеет свою цену: поиск решений занимает много времени. Размер компилируемых функций - до 1000 инструкций. Наибольший эффект от Unison был показан на спецпроцессоре Hexagon с длинным машинным словом (VLIW), где важно оптимальное расписание: на некоторых тестах реальное время исполнения снижается на 40%.
Лозано предлагает использовать Unison как инструмент для порождения кода к спецпроцессорам, оценки эффективности эвристических решений, поиска оптимальных решений в отдельных функциях.
Презентация на конференции LLVM (2017): https://www.youtube.com/watch?v=kx64V74Mba0
Обобщающая исследования Лозано диссертация (2018 год): http://kth.diva-portal.org/smash/get/diva2:1232941/FULLTEXT01.pdf
Оценка производительности Unison (2017): https://www.diva-portal.org/smash/get/diva2:1119107/FULLTEXT01.pdf
Сайт проекта: https://unison-code.github.io/
Программирование в ограничениях: https://ru.wikipedia.org/wiki/Программирование_в_ограничениях
Программная статья от именитых исследователей (Nuno P. Lopes и John Regehr) о роли точных методов в будущих компиляторах: https://arxiv.org/pdf/1809.02161.pdf
#constraintprogramming #unison #registeralloc #instructionscheduling #llvm
13/02/2021, Alexander Tchitchigin¶
https://grosskurth.ca/bib/1997/cardelli.pdf “Program Fragments, Linking, and Modularization” Luca Cardelli.
Статья поднимает вопрос корректности раздельной компиляции и линковки, и потому — я считаю — обязательна к прочтению для всех авторов языков программирования! 😃
Уже во введении на простейшем примере создания воображаемой программы, состоящей всего из двух модулей, разрабатываемых независимо, автор иллюстрирует, наверное, все проблемы, при этом возникающие. Между делом Карделли упоминает публичные репозитории артефактов (типа Maven Central или Nuget. Напомню, что статья опубликована в 1996 году!). Многие из обозначенных проблем линковки раздельно скомпилированных модулей до сих пор не решены ни в мейнстримных, ни в исследовательских языках.
В качестве основного результата Карделли предлагает, вероятно, первую формальную модель раздельной компиляции и последующей линковки, позволяющую строго рассмотреть вопрос о корректности этих процессов. Корректность в этом смысле приведённой простейшей системы модулей для просто типизированного лямбда-исчисления (в качестве модельного языка) формально доказывается. Автор, конечно же, указывает на необходимость расширения модели как в сторону более развитых языков (параметрический полиморфизм, ООП), так и в сторону более сложных систем модулей (параметризованные модули, “функторы” в духе Standard ML, первоклассные модули). Существуют ли такие работы, непосредственно продолжающие это исследование, мне не известно.
Однако, в качестве related work и дальнейшего чтения могу указать на работы по формализации (и доказательству корректности) раздельной компиляции для языка C в рамках проекта CompCert.
#separatecompilation #modules #stlc #linking
07/02/2021, Vladimir Kazanov¶
На Хабре несколько дней назад появилась статья, популярно поясняющая знаменитую технику реализации языка Scheme - Cheney on the M.T.A. Статья излагает историю названия и объясняет работу остроумного подхода к сборке мусора.
Исходный код Scheme здесь сначала должен быть преобразован в представление с продолжениями (см., например, книгу Compiling with Continuations). Функции этого представления один к одному компилируются в функции на языке C. Многочисленные временные значения, характерные для Scheme, сначала размещаются на стеке вызовов C. Во время работы программы стек вызовов функций C будет расти, так как при компиляции с продолжениями функции не возвращаются к точке исходного вызова.
При превышении допустимого размера стек сбрасывается вызовом longjmp. Размер проверяется, например, через численное значение адреса временной переменной. Перед сбросом живые значения из стека перемещаются в кучу для зачистки алгоритмом Чейни, мертвые же значения отбрасываются автоматически.
Техника сильно упрощает компиляцию Scheme в C (например, рекурсивные вызовы и их оптимизацию, легко выражаются продолжения), из-за чего ее используют минимум два популярных компилятора: Cyclone и Chicken.
Статья на Хабре: https://habr.com/ru/company/ruvds/blog/540502/
Подробности реализации техники от разработчика Chicken Scheme: https://www.more-magic.net/posts/internals-gc.html
Реализация Cyclone: https://justinethier.github.io/cyclone/docs/Garbage-Collector
Оригинальная публикация по Cheney on the MTA: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3A988CF024FE807165D1CFA957445BC8?doi=10.1.1.54.7143&rep=rep1&type=pdf
Алгоритм сборки мусора Чейни: https://people.cs.umass.edu/~emery/classes/cmpsci691s-fall2004/papers/p677-cheney.pdf
Компиляторы, использующий другие подходы к компиляции в язык C:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.50.8424&rep=rep1&type=pdf - Bigloo - компилятор Scheme и Standard ML
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.8788&rep=rep1&type=pdf - Gambit - компилятор Scheme
27/01/2021, Vladimir Kazanov¶
Распределение регистров - одна из старейших проблем построения компиляторов, первые работы по которой появились еще в 50-ые годы прошлого века. Как и в других NP-полных задачах недостатка в эвристических решениях нет. Тем не менее, в последние десятилетия разработчики все чаще используют один из двух глобальных подходов: линейное сканирование в динамических (JIT) компиляторах и раскраску графа в статических (AOT) компиляторах.
В своей диссертации Йозеф Эйсель (Josef Eisl) предлагает новый субглобальный подход к распределению регистров в динамических компиляторах, имеющий в основе следующие наблюдения:
-
Глобальные методы тратят много времени на редко исполняемый (холодный) код.
-
В современных динамически компилируемых языках после агрессивного встраивания функций (inline) появляются большие функции, где много холодного кода.
-
Крупные функции при глобальном охвате занимают много времени.
Выходит, что если сконцентрировать внимание алгоритма на горячих участках в ущерб холодным, то можно за то же время найти эффективное (или даже оптимальное!) распределение на отдельных важных участках кода.
В качестве важных участков Эйсель выбрал непересекающиеся последовательности базовых блоков - трассы (traces). Каждая трасса в зависимости от популярности получает свою политику распределения - быструю и неэффективную, долгую и эффективную, компромиссную или даже специализированную.
Интересно, что схожий подход уже применялся в трассирующих jit-компиляторах, но там трассы компилировались целиком, тогда как у Эйселя трассы выделяются только для распределения регистров.
Эйсель в сотрудничестве с Oracle реализовал подход в GraalVM, нового jit-компилятора для JVM, где тот показал сравнимую с актуальными версиями линейного сканирования производительность порожденного кода при меньшем времени РР. При этом распределение на трассах позволяет искать баланс между временем компиляции и производительностью распределения, а также открывает возможности для параллельной работы над трассами.
В настоящий момент код по умолчанию выключен, но доступен в Java версий от 10 и новее через опции
java -XX:+UnlockExperimentalVMOptions -XX:+UseJVMCICompiler -Dgraal.TraceRA=true
.
https://ssw.jku.at/General/Staff/Eisl/papers/phdthesis.pdf
#trace #jvm #registerallocation #graalvm
13/01/2021, Vladimir Kazanov¶
BLISS - один из самых ранних портативных языков для системного программирования, первая версия которого (BLISS-10) была выпущена для PDP-10 еще в 1970-ом году. Наиболее широкое применение язык нашел во внутренних разработках компании DEC, где на BLISS вплоть до 90-х создавались компиляторы, операционные системы и низкоуровневые утилиты.
Но прославился этот язык благодаря версии для PDP-11, вышедшей в 1975 году. Компилятор BLISS-11 был на голову выше конкурентов вроде ранних компиляторов C и поражал воображение разработчиков (“we’d sit and chuckle at what it had done”). Реализацию описывали несколько диссертаций (одна из них - за авторством будущего основателя Adobe) и книга. Пример инновационности BLISS-11 - анализ жизни переменных в применении к глобальному распределению регистров.
Книга описывает собственный подход к анализу областей жизни переменных (потому что “no truly satisfactory solution exists in the literature”). Найденные области обозначались каждая двумя координатами в двухмерном пространстве. Координаты задавали вершины прямоугольников. Если области-прямоугольники времени жизни переменных пересекались, то такие области не должны были оказываться в одном регистре.
Каждая переменная получала рейтинг на основе расположения в коде (напр. глубины вложения циклов) и размера области жизни (меньше - лучше). Переменные сортировались по рейтингу, и за один проход одна за другой сопоставлялись с регистрами, если только при этом не случалось пересечения с уже сопоставленными с регистром переменными.
Позже эта проблема была сведена к NP-сложной задаче об упаковке в контейнеры; и в следующих версиях BLISS разработчики развили подход в семейство алгоритмов binpacking, к которым относится и популярный алгоритм линейного сканирования.
С закатом DEC зашла и звезда BLISS. Но в истории компиляторов реализация языка оставила значимый след: книга The Design of an Optimizing Compiler (1975) стала классикой, и без BLISS любое обсуждение истории компиляторов будет неполным.
Wulf, W.A., 1975. The design of an optimizing compiler.
Brender, Ronald F. 2002. The BLISS programming language: a history
#bliss #history #registerallocation
08/01/2021, Vladimir Kazanov¶
Некоторые разработки получают известность не в силу новаторских решений, а благодаря качественной инженерной работе и удобной сопроводительной документации. Пример - портативный компилятор lcc, ставший прообразом 8cc, chibicc, tcc и других свободно доступных небольших компиляторов.
Разработчики lcc задались целью сделать не просто полноценный компилятор языка Си, но еще и подробно документированный: проект написан в стиле “литературного программирования” Д.Кнута, когда код интегрирован в документацию (а не наоборот).
Более того, из такого “художественного” исходного кода можно собрать полноценную книгу, изданную под названием A Retargetable C Compiler: Design and Implementation. Вместе с книгой для разъяснения ключевых технических решений авторы опубликовали статьи, посвященные, например, распределению регистров и порождению кода.
lcc можно отнести к промежуточному варианту между простыми компиляторами, описываемыми в популярных книгах для программистов, и серьезными оптимизирующими компиляторами. Здесь есть внутреннее представление (лес ациклических графов внутри базовых блоков графа потока исполнения), используются отдельные популярные оптимизации.
Характерное для компилятора решение - распределение регистров. Оно локальное и восходящее, то есть проводится внутри базового блока проходом по списку инструкций. Регистры один за другим выделяются под значения до тех пор, пока не приходится искать значение для вытеснения в память. Вытесняются те значения, следующее использование которых в списке инструкций находится дальше всего.
В результате компилятор был портирован на множество платформ, стал основой для бесчисленных форков и даже использовался для скриптования популярного игрового движка id Tech 3 (см. Quake 3 Arena) компании idSoftware.
https://en.wikipedia.org/wiki/LCC_(compiler)
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.2519&rep=rep1&type=pdf
https://en.wikipedia.org/wiki/Id_Tech_3
#history #lcc #registerallocation
07/01/2021, Vladimir Kazanov¶
Самый ранний и задавший главные направления исследований в области компиляторов проект это, безусловно, оптимизирующий компилятор языка Fortran I. Работы над ним велись в середине 1950-х и примененные в компиляторе техники устарели, но, например, остроумный механизм распределения регистров продержался в Fortran еще много лет.
Распределение регистров в Фортране 1 проводится в два этапа. На вход первого этапа поступает список инструкций, использующих неограниченное число символьных регистров. Список разбивается на базовые блоки, то есть строится граф потока исполнения. При этом во всех ветвлениях (IF, вычисляемых GOTO) программисты на языке должны были сами (!) расставить вероятность перехода по каждой из ветвей. Вероятности впоследствии используются для моделирования частоты базовых блоков метдом Монте-Карло.
Во втором этапе, начиная от самого “горячего” из оставшихся необработанных блоков, строится регион, внутри которого будет проводится распределение регистров. Регион расширяется самым горячим из соседних базовых блоков до тех пор, пока не упирается в другие регионы или начало/конец графа. Специальным образом обрабатывается закольцованные регионы, то есть циклы.
Само выделение регистров происходит внутри каждого такого региона; при необходимости вытесняются регистры, наименее востребованные в оставшейся части региона (например, мертвые).
Материалы для интересующихся историей компиляторов:
https://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2_i1/fortran.pdf - краткий современный обзор компилятора
http://archive.computerhistory.org/resources/text/Fortran/102663113.05.01.acc.pdf - оригинальная публикация 1957-го года.
#fortran #history #registerallocation
07/01/2021, Peter Sovietov¶
Next-gen Haskell Compilation Techniques
На мой взгляд, презентация интересна будет многим компиляторщикам. Автор приводит массу академических ссылок. В целом, речь идет о проблематике организации архитектуры современного компилятора. Мне, например, очень понравилась идея с использованием Datalog, которая дополнительно себя оправдала и с точки зрения производительности статического анализа.
06/01/2021, Peter Sovietov¶
И мой комментарий к комментарию https://t.me/plcomp/64 по “A Survey on Register Allocation”.
Статья-обзор по алгоритмам распределения регистров. Автор старается простыми словами объяснить на ходу базовую терминологию, чтобы читателю не пришлось на каждом шагу сверяться с другими источниками. В этом смысле содержание обзора можно было бы назвать доходчивым. Но, казалось бы, это не большое достижение – на тему распределения регистров есть разделы в известных учебниках, а проект LLVM, кажется, вообще закрыл эту тему для компиляторщиков, мол, бери готовое и не думай, как оно устроено.
А теперь перейду к сути. Fernando M Q Pereira, автор рассматриваемого обзора, один из признанных современных специалистов в области распределения регистров. F.M.Q. — автор передового алгоритма Puzzle Solving и даже имеет патент на него. Что касается самого обзора, то это, на мой взгляд, обязательное чтение для компиляторщика-профессионала, которого интересуют вопросы порождения целевого кода, особенно для нетрадиционных, неортогональных архитектур. И при всей своей внешней доходчивости это нелегкое чтение, требующее серьезной квалификации.
В обзоре рассматриваются как классические подходы, так и подходы передовые, специализированные. Передовые настолько, что в реализации LLVM вы их не встретите. Речь, например, о распределении регистров прямо в форме SSA, а также о более экзотических техниках, в духе PBQP.
Важно, что перед нами действительно научный обзор, поэтому автор не скупится на изложение важных теоретических результатов. На этот счет, в частности, есть очень ценный, заключительный раздел по NP-полным (современным!) результатам из области распределения регистров.