PLComp

Самый ранний и задавший главные направления исследований в области компиляторов проект это, безусловно, оптимизирующий компилятор языка 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-го года. #history #fortran #registerallocation

Next-gen Haskell Compilation Techniques На мой взгляд, презентация интересна будет многим компиляторщикам. Автор приводит массу академических ссылок. В целом, речь идет о проблематике организации архитектуры современного компилятора. Мне, например, очень понравилась идея с использованием Datalog, которая дополнительно себя оправдала и с точки зрения производительности статического анализа. https://docs.google.com/presentation/u/0/d/1g_-bHgeD7lV4AYybnvjgkWa9GKuP6QFUyd26zpqXssQ/mobilepresent #ghc #grin

И мой комментарий к комментарию https://t.me/plcomp/64 по "A Survey on Register Allocation". Статья-обзор по алгоритмам распределения регистров. Автор старается простыми словами объяснить на ходу базовую терминологию, чтобы читателю не пришлось на каждом шагу сверяться с другими источниками. В этом смысле содержание обзора можно было бы назвать доходчивым. Но, казалось бы, это не большое достижение -- на тему распределения регистров есть разделы в известных учебниках, а проект LLVM, кажется, вообще закрыл эту тему для компиляторщиков, мол, бери готовое и не думай, как оно устроено. А теперь перейду к сути. Fernando M Q Pereira, автор рассматриваемого обзора, один из признанных современных специалистов в области распределения регистров. F.M.Q. — автор передового алгоритма Puzzle Solving и даже имеет патент на него. Что касается самого обзора, то это, на мой взгляд, обязательное чтение для компиляторщика-профессионала, которого интересуют вопросы порождения целевого кода, особенно для нетрадиционных, неортогональных архитектур. И при всей своей внешней доходчивости это нелегкое чтение, требующее серьезной квалификации. В обзоре рассматриваются как классические подходы, так и подходы передовые, специализированные. Передовые настолько, что в реализации LLVM вы их не встретите. Речь, например, о распределении регистров прямо в форме SSA, а также о более экзотических техниках, в духе PBQP. Важно, что перед нами действительно научный обзор, поэтому автор не скупится на изложение важных теоретических результатов. На этот счет, в частности, есть очень ценный, заключительный раздел по NP-полным (современным!) результатам из области распределения регистров. #registerallocation

Размещение сотен промежуточных значений современных программ в десятках регистров типичных процессоров - одна из первых проблем, с которой столкнулись разработчики языков высокого яровня. Со временем было показано, что в общем случае задача распределения регистров является NP-полной, что предполагает множество эвристических и частичных решений. "A survey on register allocation" - обзор темы РР на 2008 год с пояснением ключевой терминологи и перечислением наиболее эффективных подходов к проблеме. Много внимания уделяется вариантам алгоритмов раскраски графа, линейного сканирования (linear scan) и перспективным на момент написания статьи альтернативным подходам (целочисленное линейное программирование, multi-commodity flow problem и др.). В 2008 году все крупные компиляторы перешли к использованию внутренних представляний со статически однократным присваиванием (SSA). Поэтому естественно, что половина обзора посвящена рассмотрению полезных в РР свойств популярнейшего представления и адаптации ключевых алгоритмов к нему. Интересно, что в обзоре почти не упоминаются легковесное локальное (внутри базовых блоков) РР и тяжелое точное РР; рассматриваются прежде всего популярные в больших промышленных компиляторах решения. Материал написан доступно и явно ориентирован на введение в курс дела старшекурсников или аспирантов; автор не только разбирается в материале, но и умеет его донести. #registerallocation #survey http://compilers.cs.ucla.edu/fernando/publications/drafts/survey.pdf

Поздравляю читателей PLComp с предстоящими праздниками! Подведу некоторые итоги этого года. 1. Выход очередного, четвертого тома HOPL. https://t.me/plcomp/6 Замечательное, увлекательное чтение для всех, кто интересуется историей разработки ЯП. 2. Развитие подхода E-Graphs для создания систем оптимизации и синтеза программ. https://t.me/plcomp/8 Именно в этом году появились доступные реализации E-Graphs, в том числе и учебные. Следует ожидать постепенного внедрения подхода в компиляторы. 3. Практические применения SyGuS (синтаксически-управляемый синтез программ) в компиляторах. Для BPF (https://t.me/plcomp/51), для сетевых процессоров (https://dl.acm.org/doi/abs/10.1145/3387514.3405852) и для DSP (https://www.cs.utexas.edu/~bornholt/papers/diospyros-lctes20.pdf ). В будущем году, надеюсь, мы в PLComp также сможем оперативно реагировать на основные события в компиляторной/языковой тематике. Пока же предлагаю "заглянуть в будущее", посмотреть на работы предстоящих конференций. 1. ASPLOS 2021. https://asplos-conference.org/papers/ 2. POPL 2021. https://popl21.sigplan.org/program/program-POPL-2021 3. CGO 2021. https://conf.researchr.org/info/cgo-2021/accepted-papers #conf

Работа Strategic Tree Rewriting in Attribute Grammars заслуживает внимания попыткой объединения стратегического переписывания термов с атрибутными грамматиками. https://www-users.cs.umn.edu/~evw/pubs/kramer20sle/kramer20sle.pdf В последнее время интерес к забытым когда-то атрибутным грамматикам (АГ), похоже, вновь возрастает. Напомню, что АГ, формализованные Д. Кнутом еще в 1968 году, позволяют элегантным образом описывать задачи (статической) семантики и не сводятся только лишь к семантическим действиям какого-нибудь YACC. В случае АГ у нас, в общем случае, имеются как синтезированные, так и унаследованные атрибуты, позволяющие учесть контекст (это может быть, к примеру, таблица имен) при семантических вычислениях. Сами же вычисления могут производиться на графе, по готовности аргументов-атрибутов. Существует ряд современных систем быстрого прототипирования DSL-компиляторов с использованием АГ, это, в частности, JastAdd, Kiama и Silver. В рассматриваемой статье система Silver (http://melt.cs.umn.edu/silver/ ) используется для реализации стратегий в виде атрибутов высшего порядка. Зачем это нужно? Дело в том, что на уровне стратегического переписывания тяжело работать с контекстной информацией. К примеру, классический подход от E. Visser предполагает динамическое создание правил в зависимости от контекста, что не назовешь элегантным решением. На уровне атрибутов с контекстом работать значительно удобнее, в то время, как преобразования программ выразительнее осуществляются с использованием стратегий. В статье демонстрируется ряд примеров использования такого "смешанного" подхода, среди которых: оптимизация регулярных выражений на основе производных Бржозовского и нормализация for-цикла для Halide-подобного языка. Сложно сказать, насколько предложенный подход окажется успешным, но сама по себе система Silver в любом случае представляет интерес [1]. 1. Язык AbleC (расширение C11): http://melt.cs.umn.edu/ableC/ #semantics #ag #dsl #stratego

В среде компиляторщиков можно встретить утверждения в духе "SSA это функциональное программирование" и "в теории нет разницы между phi-функциями и базовыми блоками с параметрами". С инженерной же точки зрения различия, все-таки, имеются. В заметке ниже показан пример этих различий со сравнением императивного и функционального подходов к разработке компилятора: http://blog.ezyang.com/2020/10/the-hidden-problem-with-basic-block-procedures-in-ssa/ Добавлю, что нельзя сказать, что одно из этих представлений в общем случае лучше, чем другое, с точки зрения вариантов проводимого анализа (см. также https://news.ycombinator.com/item?id=24872752 ). Но, в целом, можно отметить тенденцию использования базовых блоков с параметрами в высокоуровневых IR и для межпроцедурных преобразований, а phi-функций -- в низкоуровневых представлениях (вплоть до реализации мультиплексоров в описании генерируемой цифровой схемы). #ssa

https://www.jeffsmits.net/assets/articles/sle20-paper4.pdf Gradually Typing Strategies Статья рассказывает о применении популярной техники постепенной типизации (Gradual Typing) в необычной области -- к языку переписывания термов Stratego (который используется для "program normalization, type checkers, program analyses, code generators, and more"). Несмотря на отсутствие проверки типов в Stratego до сего момента, он тем не менее послужил для вдохновения авторов Haskell фреймворка SYB. Использование Gradual Typing (постепенной типизации) мотивировано двумя факторами. Первый -- обратная совместимость, так как Stratego (в составе фреймворков Stratego/XT и Spoofax) используется в production-системах, разрабатываемых как в академии (researchr.org, conf.researchr.org, платформа онлайн-курсов TU Delft), так и в индустрии (где-то в недрах Oracle Labs). Второй -- высокая "динамичность" переписывания термов, которая в некоторых случаях используется (а кто-то скажет "эксплуатируется") для (временного) порождения нетипизируемых термов и превращения их обратно в типизируемые. Дополнительно задача осложняется наличием в Stratego правил переписывания "высшего порядка" (называемых "стратегиями переписывания"), принимающих и применяющих другие правила переписывания (или стратегии). Отсюда возникает понятие Type-Preserving стратегий, реализующее ограниченную форму Higher-Kinded Types. Кроме того, авторы применяют механизм "прозрачных" во время исполнения прокси-типов для того чтобы избежать накапливания лишних динамических преобразований типов при передаче правил переписывания из статически-типизированных стратегий в динамически-типизированные и обратно. Проверка полученной системы типов на существующем проекте (учебный ассемблер для Java-байткода) продемонстрировала два достаточно ожидаемых результата: а) корректный динамический код написан так как если бы был статически типизирован, поэтому его легко аннотировать явными типами и почти не приходится при этом рефакторить; б) плохо протестированный динамический код содержит ошибки, которые легко обнаруживаются тайп-чекером (например, возврат списка вместо элемента — классика, сам на таком попадался). #stratego #spoofax #gradual #types

Популярный алгоритм распределения регистров линейным сканированием (Linear Scan Register Allocation, 1999) определен на живых интервалах (live intervals) и линейном списке инструкций. Построение и хранение списка интервалов в виде пар индексов инструкций занимает время и память, поэтому исследователи продолжали искать возможность не строить явно список интервалов. Авторы Efficient Global Register Allocation (2020) предложили алгоритм из того же семейства, но определенный на графе потока исполнения (control flow graph). Ключевые идеи здесь две: 1. Список живых интервалов здесь отслеживаются неявно, на каждом из базовых блоков и инструкций внутри блоков. 2. Проход по отдельным инструкциям позволяет не только не строить в явном виде интервалы, но и высвобождать временно регистры внутри блоков, что решает проблему "пустот в живости" (liveness holes). Алгоритм сравним по производительности порожденного кода с актуальными реализациями линейного сканирования, немного выигрывая в ресурсах на этапе компиляции. Из работы следует, что основное преимущество подхода заключается в возможностях специальных оптимизаций. В настоящий момент этот вариант линейного сканирования используется при порождении регистрового байткода dex для виртуальной машины ART, используемый в Android. https://arxiv.org/pdf/2011.05608.pdf #registerallocation #linearscan #dex #art #android

Классический редактор GNU Emacs в скором времени получит, наконец, нативный компилятор для своего языка расширений Emacs Lisp. Это уже третья попытка решить сопутствующие проблемы, но Andrea Corallo за последний год построил на базе libgccjit компилятор, показывающий достойный результат в пакете elisp-benchmarks. Уже сейчас компилятор готовится к вливанию в основную ветку репозитория GNU Emacs. Презентация автора на Linux Plumbers Conference 2020: http://akrl.sdf.org/Kludging_LPC_2020.pdf Дневник разработки: http://akrl.sdf.org/gccemacs.html Обсуждение (в положительном ключе) состояния ветки репозитории: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=43725

(Это мой старый перечень, но интерес, как мне кажется, он все еще представляет) Ниже я хочу представить краткий список полновесных книг по специальным вопросам компиляции. Эти книги много дали лично мне. Надеюсь, они окажутся в соответствующий момент полезными и вам. 1. Automatic Algorithm Recognition and Replacement. A New Approach to Program Optimization (https://mitpress.mit.edu/books/automatic-algorithm-recognition-and-replacement?cr=reset). Тема распознавания алгоритмов очень мало изучена. Но перспективы здесь самые впечатляющие. Оптимизации на уровне алгоритмов, автоматическое распараллеливание и проч. Весьма вдохновляющее чтение. 2. Reasoning About Program Transformations. Imperative Programming and Flow of Data. (https://www.springer.com/us/book/9780387953915). Очень нетипичная книга по анализу и преобразованиям программ. Доходчиво написано, автор предмет понимает настолько глубоко, что не стесняется быть субъективным, оригинальным в изложении традиционной теории. Рассматривается в том числе полиэдральная модель программы. 3. Instruction Selection. Principles, Methods, and Applications. (https://www.springer.com/us/book/9783319340173). Такого подробного, эницклопедического обзора подходов к выбору инструкций не хватало давно. Автор систематизировал различные приемы, использовал в изложении исторический контекст. 4. Partial Evaluation and Automatic Program Generation (https://www.itu.dk/~sestoft/pebook/). В наше время все чаще на практике используются давние результаты Турчина, Футамуры, Ершова и других исследователей в области частичных вычислений/метапрограммирования. В какой-то момент, после прочтения очередной заметки в блоге с упоминанием проекций Футамуры (PyPy, Truffle и так далее), нелишне будет открыть и эту книгу, где подробно изложены все эти темы.

Очередная работа от John Regehr со товарищи на тему супероптимизации. Dataflow-based Pruning for Speeding up Superoptimization https://www.cs.utah.edu/~regehr/dataflow-pruning.pdf Заметно, как первая эйфория от полностью автоматического применения SMT-решателя и метода CEGIS уходит. Оказывается, для задач реалистичных размерностей все равно приходится придумывать если не полностью собственную процедуру поиска с учетом эвристик из предметной области, то хотя бы ее элементы -- иначе SMT-решателю справиться будет тяжело. Ключевая идея авторов -- прежде чем передавать на вход SMT-решателю очередную программу-кандидат из пространства поиска, полезно эту недооформленную программу (описывающую целое семейство конкретных программ) проверить на соответствие спецификации с помощью абстрактной интерпретации (анализ потоков данных на предмет known bits, int. ranges и так далее). В том числе, на конкретных тестовых входах. В завершающей части статьи есть краткий и полезный обзор современного положения дел в области синтеза программ. #smt #analysis #synthesis

Известно, что в компиляторе IR выбирается таким образом, чтобы облегчить порождение кода для выбранного класса целевых архитектур. Но бывает ли так, чтобы уже само абстрактное IR оказывало влияние на набор команд процессора? Оказывается, и такое существует, причем речь здесь не идет о предметно-ориентированном наборе команд или поддержке конструкций входного языка. Ниже два характерных примера. BasicBlocker: Redesigning ISAs to Eliminate Speculative-Execution Attacks https://arxiv.org/pdf/2007.15919.pdf В этой работе предлагается добавить к ISA процессора специальную команду, отмечающую начало линейного участка (basic block) с указанием его длины. Это нужно для предотвращения Spectre-подобных атак. Здесь мы видим, как черты абстрактного управляющего графа (CFG) проступают в машинном коде. Hardware Acceleration for Programs in SSA Form https://pp.ipd.kit.edu/uploads/publikationen/mohr13cases.pdf В современных компиляторах форму SSA стараются сохранять настолько долго, насколько возможно, включая и фазу распределения регистров. Тем не менее, в какой-то момент из формы SSA приходится выходить и выход это достаточно болезнен, поскольку требует формирования дополнительных машинных команд. Особенно это касается phi-инструкций, имитировать которые приходится с помощью команд, заменяющих параллельные копирования/перестановки регистровых значений. А если попробовать реализовать phi-инструкцию аппаратным образом? При этом вместо реального копирования часто можно обойтись перестановками, которые на аппаратном уровне заключаются в переименовании регистров. Здесь в ISA процессора появляются черты абстрактной phi-инструкции из формы SSA. #ssa #isa

Очередной выпад в сторону классического подхода к преподаванию синтаксического разбора. Простое и изящное в части содержания пособие по написанию разбора арифметических выражений. Автор красиво и плавно приводит к идее использования рекурсивного спуска совместно с парсером Пратта. Just write the #!%/* parser https://tiarkrompf.github.io/notes/?/just-write-the-parser/ На первый взгляд эта новость не слишком подходит для PLComp, но обращает на себя внимание личность автора (Tiark Rompf — один из лучших специалистов в области DSL-компиляции) и идеологическая спорность его подхода. Действительно ли это правильный путь — перейти в обучении сразу к нюансам низкоуровневого кодирования, оставив за бортом вопросы формальной спецификации языка, его синтаксиса? Известные примеры реальных проектов, безусловно, говорят, мол, да, так оно и происходит на практике. И даже если есть спецификация, то она остается «на бумаге» и со временем расходится с реализацией все больше и больше. #parsing

Очередное подтверждение тому факту, что работа над компиляторами -- это не только известные проекты-бегемоты в духе LLVM/GCC для 2-3 популярных архитектур и виртуальных машин. Вы слышали о BPF? Впрочем, что я говорю, если читаете внимательно PLComp, то, конечно, слышали. Но, в любом случае, есть замечательная заметка, которая вводит в предмет: BPF, XDP, Packet Filters and UDP https://fly.io/blog/bpf-xdp-packet-filters-and-udp/ Посмотрите, сколько всего интересного! Узкая предметная область, виртуальные машины, JIT-компиляция, статический анализ кода, верификация. В заметке есть ссылка на хорошую статью 1999 года: BPF+: Exploiting Global Data-flow Optimization in a Generalized Packet Filter Architecture https://andrewbegel.com/papers/bpf.pdf Ничего себе, да? Такие-то технологии для, вроде бы, заурядной задачи фильтрации пакетов! И вот кульминация, статья уже совсем свежая: Specification and verification in the field: Applying formal methods to BPF just-in-time compilers in the Linux kernel https://unsat.cs.washington.edu/papers/nelson-jitterbug.pdf Складывается ощущение, что BPF -- своеобразный полигон для обкатки перспективных технологий компиляции. Это объяснимо: на исходный язык и вычисления накладываются жесткие ограничения, сама виртуальная машина простая -- есть где развернуться и применить что-нибудь изощренное. И, разумеется, интересны перспективы использования BPF в специализированных аппаратных решениях. P.S. Вообще, в области обработки сетевых пакетов компиляторные технологии в целом развиваются очень интересным образом, существуют работающие подходы из области синтеза программ и я к этой теме еще обязательно вернусь. #jit #analysis #vm #verification #bpf

Обсуждения вокруг эффективности интерпретатора и компилятора LuaJIT не утихают в нишевых сообществах до сих пор, при этом сам автор развернутых пояснений так и не оставил. Отдельные его комментарии можно найти на Reddit и в рассылке lua: http://lua-users.org/lists/lua-l/2008-07/msg00651.html http://lua-users.org/lists/lua-l/2010-11/msg00437.html http://lua-users.org/lists/lua-l/2011-02/msg00671.html http://lua-users.org/lists/lua-l/2011-02/msg00742.html https://www.reddit.com/r/programming/comments/hkzg8/author_of_luajit_explains_why_compilers_cant_beat/c1w8xyz/?context=3 https://www.reddit.com/r/programming/comments/badl2/luajit_2_beta_3_is_out_support_both_x32_x64/c0lrus0/ #JIT #Lua

Пособие по реализации проверки для refinement-типов. В духе разработки компиляторов на основе техники nanopass. Предикаты проверяются с помощью SMT-решателя Z3. Refinement Types: A Tutorial https://arxiv.org/abs/2010.07763 https://github.com/ranjitjhala/sprite-lang #analysis #smt

Formulog -- выразительный DSL для задач статического анализа. Основан на Datalog и ML, реализация использует SMT-решатель. Formulog: ML + Datalog + SMT http://www.weaselhat.com/2020/08/07/formulog-ml-datalog-smt/ #analysis #datalog #smt

Детальный анализ трассирующего JIT-компилятора Lua LuaJIT https://github.com/MethodicalAcceleratorDesign/MADdocs/blob/master/luajit/luajit-doc.pdf #JIT #lua