Компилятор

Обыденное представление о Deep Learning состоит в том, что для достижения успеха нужно хорошо знать математику и уметь программировать на Python. Но все становится немного сложнее, как только мы начинаем говорить о реализации нейросетевых решений в железе, где критична производительность. Мы пообщались с руководителем направления российского Исследовательского центра Samsung Вячеславом Гарбузовым, чтобы понять, как ускоряют работу нейросетей на аппаратном уровне, при чем тут компиляторы и какие знания требуются в этой редкой профессии. И самое интересное - какие вакансии в его подразделении открыты в настоящий момент.

Слава, привет! Расскажи о себе, чем занимается твоя команда сейчас.

Привет! Я руковожу управлением разработки ПО для систем на кристалле Исследовательского центра Samsung. Мы занимаемся разработкой SDK для ускорения исполнения моделей глубинного обучения (Deep Learning)на процессорах Exynos.

Кто твои непосредственные заказчики?

Наша работа связана с компонентным бизнесом и нашим заказчиком является Samsung Semiconductor. Мы ближе к земле.

Правильно ли я понимаю, чтомобильныйпроцессор Exynosв основном используется в телефонах Samsung и больше нигде?

Вовсе нет. Exynos используется в смартфонах других производителей. Кроме того, Exynos - это не только мобильные системы на кристалле (SoC). Есть микроконтроллеры, компоненты Интернета вещей. Крупные игроки на автомобильном рынке тоже заинтересованы в наших продуктах.

Расскажи про новый Exynos и AI-ускоритель в нем

Разработкой Exynos SoCи SDK к нему занимается подразделение Samsung System LSI (large-scale integration - высокоинтегрированные чипы). Узнать подробнее про новый Exynos 2100 можно извидеопрезентации. В разделе AI and Camera кратко рассказывается, что такое AI-ускоритель. Это железо для ускорения работы нейросетей. Обучение сети производится заранее, а исполнением (inference) как раз занимается это железо.

Что такое inference, что значит выполнить сеть на устройстве? Есть нейросеть, она уже натренирована. На вход готовой нейросети мы подаем картинку с собачкой или кошечкой, а на выходе это устройство дает 0 или 1. То есть наш сопроцессор не занимается обучением нейросети самостоятельно, его задача просто отработать готовую сеть.

Для работы нейросетевого сопроцессора нужен программный инструментарий. Такой инструмент есть, он называется Samsung Neural SDK.

Для каких задач это всё используется?

Применения в телефоне в основном связаны с камерой: живой фокус, ночная съемка, Bixby Vision, обнаружение лиц, улучшающее картинку.

Здесь забавно, что в этом году в S21 добавили фичу для детектирования домашних животных. Раньше алгоритмы не узнавали собак и кошек и не могли их обработать красиво. И вот эта проблема теперь решена.

Расскажи, как устроен этот AI-ускоритель.

Он состоит из двух частей:

1. NPU (Neural Processing Unit - обработчик нейросетей). Фактически это ускоритель операций с тензорами. Он умеет быстро делать свертки (convolution), пулинги (pooling) - набор операций, популярных в глубинном обучении.

2. DSP (digital signal processor - цифровой обработчик сигналов).Это процессор, специализированный под выполнение определенных задач. Его разрабатывают изначально под конкретные алгоритмы. Ребята проектируют этот DSP под распознавание лиц или под более широкий круг задач.

Это единый кластер в составе одной системы на кристалле. Для него мы и разрабатываемSDK. У нас две команды, одна работает над NPU, другая, соответственно, над DSP.

Какие компиляторные задачи у вас с NPU?

Компилятор для NPU - это та штука, которая превращает граф на выходе Deep Learning-фреймворка в последовательность процессорных команд. Отличие от обычного компилятора в том, что мы генерируем код не для CPU, а для нейросетевого ускорителя. Это другой процессор со своим языком. И чтобы вся система работала быстрее, мы оптимизируем ее на уровне компилятора.

В чем суть оптимизации? По большей части это memory allocation (оптимизация работы с памятью) и instruction scheduling (параллелизм на уровне инструкций). Наш процессор может несколько инструкций выполнять одновременно, например, считать ту же самую свертку и загружать данные для свертки. Мы должны сгенерировать код для этого процессора так, чтобы оптимизировать работу с памятью и максимизировать параллелизм.

А что с DSP? Какие задачи там?

Это уже более-менее похоже на традиционный процессор. Если свертку наш NPU умеет делать на уровне железа, то здесь мы должны эту свертку описать на языке C++ и исполнить на DSP. Зачем нужен отдельный сопроцессор, чтобы выполнять ту же самую свертку? Например, NPU занят в какой-то момент, и мы хотим параллельно решать другую задачу. Некоторые операции мы в принципе на NPU выполнить не можем.

У нас достаточно простой DSP, основанный на VLIW-архитектуре (very long instruction word очень длинная машинная команда). Особенность нашего DSP в том, что он аппаратно достаточно простой, и от компилятора требуется серьезная оптимизация.Мы делаем на базе LLVM компилятор для этого DSP.

Поговорим о других вещах. Где ты работал до Samsung?

Непосредственно до Samsung я работал в Topcon Positioning Systems и в Lynx Software Technologies. Занимался разработкой RTOS и инструментов.

Где и на кого ты учился?

Учился в МГУ на физика. Занимался ускорителями элементарных частиц, электронов в частности. Занимался автоматизацией физического эксперимента, системой управления для промышленного ускорителя.

Как помогает образование физика в твоей профессии?

В профессии руководителя это очень сильно помогает, позволяет смотреть на вещи широко.

Работая в твоем отделе, насколько важно хорошо разбираться в железе?

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

А в глубинном обучении?

Базовое представление надо иметь. Я полагаю, что современные выпускники вузов это всё уже знают на определенном уровне. Это всегда хорошо иметь в бэкграунде. Например, курс Нейронные сети и компьютерное зрение Samsung Research Russia на Stepik я добавил в закладки, но пока не прошел. И кстати, вчера в рамках этого курса былалекцияна YouTube про Embedded Inference как раз на эту тему - "Мобильные архитектуры нейросетей и фреймворки для их запуска".

Когда мы начинали этот проект в 2018 году, мне сказали: нужен компилятор для Deep Learning. Нам потребовалось найти людей, которые одновременно умеют и в Deep Learning, и в железо, и в компиляторы. И это сложно, потому что таких людей очень мало. Потом мы поняли, что требование знания Deep Learning не столь критично, всё-таки заказчики от нас просили только компилятор.

С выпускниками каких вузов тебе интересно работать?

Мне приятно работать с выпускниками МФТИ, особенно с теми, которые прошли через базовые кафедры ИСП РАН или Intel. У нас в отделе достаточно много ребят из Intel. По факультетам - ФУПМ, ФРКТ. Если говорить о других вузах, то это и МГУ - забавно, что много моих знакомых компиляторщиков заканчивали физфак. Также это ВШЭ, где есть МИЭМ, там учат проектировать железо, FPGA. А компиляторы можно условно рассматривать как часть железа в принципе.

В нашем Исследовательском центре мы проводили вечернюю школуSamsung Compiler Bootcamp, и , в основном, в ней учились студенты из Бауманки, МГУ и Вышки.

На тему FPGA - полезно ли это изучать?

Как бэкграунд - да, это правильно.

А вообще, много ли таких центров в Москве, где занимаются компиляторами?

Intel, JetBrains, Positive Technologies, Huawei. Из российских - МЦСТ, которые Эльбрус, они тоже компиляторы делают. Например, Роман Русяев, наш коллега из Исследовательского центра Samsung и разработчик компиляторов, как раз оттуда пришел (см. егостатьюна Хабре о Concept-Based Polymorphism), он часто выступает на конференциях и пишет статьи.Он активный участник C++ Community. Например, вот пара его выступлений где затрагивается тема оптимизации при помощи компилятора :"Исключения C++ через призму компиляторных оптимизаций","Настоящее и будущее copy elision".

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

О каких мировых трендах в компиляторов можно сейчас говорить?

Можно выделить такие тренды:

1. Доминирование проекта LLVM

2. Обобщение компилятора для различных предметных областей посредством универсального промежуточного представления (MLIR)

3. Объединение различных инструментов для анализа и преобразования кода (компиляторов, анализаторов, performance estimators, линтеров и пр.) в рамках одного проекта

4. Активные попытки использования высокой науки в промышленных компиляторах (formal verification, polyhedral optimizations, более подробно встатье)

Какие требования к соискателям, будущим разработчикам компиляторов, ты бы озвучил?

Обязательные требования: знание С/С++ на хорошем уровне. Понимание того, как устроены компиляторы, опыт их разработки. Понимание устройства операционной системы. Умение разбираться в больших объемах чужого кода. Навыки отладки embedded-устройств. Знание практик программной инженерии - непрерывная интеграция, ревизия кода, отслеживание задач. Владение скриптовыми языками - Bash или Python.

Помимо технических требований, важно умение работы в команде, быть адекватным человеком. Нужно иметь широкий кругозор, быть профессионалом. Уметь быстро адаптироваться - мы работаем на крайне конкурентном рынке, требования заказчиков меняютсячасто и неожиданно. Хорошо знать английский язык. Уметьвежливо общаться. Понимать, что мы предоставляем сервис. Кому-то это не нравится, а кому-то вполне нормально. Не нужно быть токсичным.

Работая в международной компании, как складывается коммуникация с иностранными коллегами? Как вы решаете вопросы взаимодействия с коллегами в пандемию?

Мы активно взаимодействуем с командами из других стран Корея, Китай, Индия, Израиль, США. До карантина они частенько приезжали к нам в гости, а мы к ним.

Даже сейчас очень много коммуникации. Каждый день видео-планерки, чтобы люди не теряли фокус. У нас уже давно существует виртуальная лаборатория с удаленным доступом к образцам "железа". В этом смысле мы были готовы к работе извне. Мы уже привыкли работать в распределенной команде, поэтому для нас это стрессом не было.

Какие книжки о компиляторах ты бы посоветовал?

Коллеги рекомендуют начинать с "Modern Compiler Implementation in ML", автор Andrew W. Appel.

Какие твои любимые книги о программировании вообще?

Керниган и Ричи Язык программирования С. Они классные. Еще Керниган и Пайк, Практика программирования. Там настолько все четко сделано.

Что скажешь об онлайн-курсах?

Если говорить о курсах по смежным темам, то по глубинному обучению это курс Samsung о нейронных сетях в компьютерном зрении, и известный курс Эндрю на (Andrew Ng). Полезенкурс по С++от Яндекса.

LLVM или GCC - что полезнее изучать?

LLVM. Он более распространенный, и порог вхождения считается ниже.Кроме того, в этом проекте активно используются последние нововведения языка C++ и современные практики программирования. Мы, кстати, сейчас ищем разработчика, который знает LLVM.

Какие инструменты командной работы используете?

Используемgit, точнее корпоративный github. Важно сказать, что мы делаем Code Review, и это неотъемлемая часть работы наших инженеров. Здорово, что все друг другу помогают и делятся знаниями. Также мы делимся знаниями с помощью Confluence, у нас есть вики-портал с внутренней документацией по нашим разработкам. Есть Jira для отслеживания задач. И есть свой чат на основе Mattermost, то есть практически Slack - без него на удаленке мы бы вообще не выжили. Исповедуем ContinuousIntegration, а также автоматизируем все, что можно автоматизировать.

А что насчет методов Agile?

Мы не привязаны к какой-то конкретной методологии. Берем полезные практики, которые подходят нашему проекту, из разных методологий. Например, из скрама мы берем Daily Scrum - ежедневные собрания. У нас есть итеративное планирование. И так далее.

Не могу не спросить. А вот во время пандемии, когда все по видео общались, вы все равно Daily Scrum стоя проводили?

Ну нет, всё-таки все сидели.

Сколько у вас длится Daily Scrum?

От 15 минут до часа, потому что иногда он перетекает в технические дискуссии.

Что еще интересного бывает?

Регулярно проходят онлайн-семинары. Коллеги из разных центров компании рассказывают о своих задачах, обсуждаются технические решения. Мы тоже участвуем, конечно. Также проводим внутренние семинары для сотрудников московской команды. Обмениваемся знаниями, изучаем опыт других. Например, в настоящий момент у нас в Исследовательском центре проходит серия семинаров про алгоритмы аллокации памяти.

----

А сейчас самое интересное: ВАКАНСИИ!

У нас открыты две вакансии, соответственно поNPUи поDSP. Если вас заинтересовало, откликайтесь на вакансию прямо на HeadHunter, и возможно, мы с вами встретимся на собеседовании.

Вопросы задавала: Татьяна Волкова, куратор трека по Интернету вещей социально-образовательной программы для вузов IT Академия Samsung

Отвечал: Вячеслав Гарбузов, руководитель направления, российский Исследовательский центр Samsung

Создать компилятор JS с высокой производительностью означает сделать больше, чем разработать сильно оптимизированный компилятор, например TurboFan, особенно это касается коротких сессий, к примеру, загрузки сайта или инструментов командной строки, когда большая часть работы выполняется до того, как оптимизирующий компилятор получит хотя бы шанс на оптимизацию, не говоря уже о том, чтобы располагать временем на оптимизацию. Как решить эту проблему? К старту курса о Frontend-разработке делимся переводом статьи о Sparkplug свече зажигания под капотом Chrome 91.

Вот почему с 2016 года мы ушли от синтетических бенчмарков, таких как Octane, к измерению реальной производительности и почему старательно работали над производительностью JS вне оптимизирующих компиляторов. Для нас это означало работу над парсером, стримингом [этой поясняющей ссылки в оригинале нет], объектной моделью, конкурентностью, кешированием скомпилированного кода...

Впрочем, повернувшись лицом к улучшению производительности фактического, начального выполнения JS, мы столкнулись с ограничениями процесса оптимизации интерпретатора. Интерпретатор V8 сам по себе быстрый и сильно оптимизированный, но интерпретаторам как таковым свойственны накладные расходы, избавиться от которых мы не можем: например на декодирование байт-кода или диспетчеризацию неотъемлемые части функциональности интерпретатора.

С нашей текущей моделью с двумя компиляторами мы не можем быстро перейти к оптимизированному коду, но после определённого момента ускориться можно, только удаляя снижающие пик производительности проходы оптимизации. Что ещё хуже, мы действительно не можем начать оптимизацию раньше, поскольку ещё нет стабильной обратной связи о форме объекта.

Выход из положения Sparkplug: новый неоптимизирующий компилятор JavaScript, который мы выпустили вместе с V8 9.1, он работает между интерпретатором Ignition и компилятором TurboFan.

Быстрый компилятор

Sparkplug создан компилировать быстро. Очень быстро. Настолько, что мы всегда можем компилировать, когда захотим, повышая уровень кода SparkPlug намного агрессивнее кода TurboFan, [подробнее здесь, этой ссылки в оригинале нет].

Есть пара трюков, делающих Sparkplug быстрым. Первый трюк это читы. Компилируемые им функции уже скомпилированы в байт-код, и компилятор байт-кода уже проделал большую часть тяжёлой работы, такой как разрешение переменных, анализ, не указывают ли скобки на стрелочную функцию, раскрытие выражений деструктуризации в полный код и т. д. Sparkplug компилирует, исходя из байт-кода, поэтому ему не нужно учитывать ничего из перечисленного.

Второй трюк в отличие от большинства компиляторов Sparkplug не генерирует промежуточное представление (IR). Вместо этого Sparkplug компилирует прямо в машинный код за один линейный проход по байт-коду и выдаёт соответствующий выполнению байт-кода машинный код. На самом деле компилятор это switch внутри цикла for, который занят диспетчеризацией, чтобы за каждой инструкцией закрепить генерирующие машинный код функции.

// The Sparkplug compiler (abridged).for (; !iterator.done(); iterator.Advance()) {  VisitSingleBytecode();}

Недочёт промежуточного представления (IR) заключается в том, что компилятор ограничен возможностями оптимизации. Поскольку промежуточной архитектурно независимой стадии нет, этот факт также означает, что всю реализацию нужно переносить на каждую поддерживаемую архитектуру отдельно. Но, оказывается, ни то, ни другое не является проблемой: портировать код довольно легко, вместе с тем Sparkplug не нужно выполнять тяжёлую оптимизацию.

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

Совместимые с интерпретатором фреймы

Добавление нового компилятора в зрелую виртуальную машину JS пугающая задача. Кроме стандартного выполнения в V8 мы должны поддерживать отладчик, профилирование центрального процессора с обходом стека, а значит, трассировки стека для исключений, интеграцию в стратегию динамического повышения уровня функции, замену на стеке, чтобы оптимизировать код горячих циклов. Работы много.

Sparkplug это рука мастера, которая ловкими, красивыми движениями упрощает большинство этих задач, то есть он поддерживает совместимые с интерпретатором стековые фреймы. Давайте вернёмся немного назад. При выполнении кода во стековых фреймах хранится состояние функции. Это касается каждого вызова какой-то новой функции: для её локальных переменных создаётся стековый фрейм. Этот стек определяется указателем на фрейм в начале и указателем на стек в конце.

Сейчас около половины читателей закричит: "Диаграмма не имеет смысла, стек направлен в другую сторону!" Ничего страшного, я сделал кнопку: думаю, стек направлен вниз.

Когда функция вызвана, адрес возврата кладётся на стек и удаляется со стека функцией, когда она возвращается, чтобы знать, куда вернуться. Затем, когда функция создаёт новый фрейм, она сохраняет указатель на старый фрейм на стеке и устанавливает новый указатель в начало собственного стекового фрейма. Таким образом, на стеке образуется цепочка указателей на фреймы, каждый из которых отмечает начало фрейма, указывающего на предыдущий:

Строго говоря, это только соглашение, согласно которому создаётся код, но не требование. Хотя оно довольно универсально; не работает оно только в двух случаях: когда стековые фреймы полностью игнорируются или когда вместо него можно использовать таблицы со стороны отладчика.

Это основной макет стека для всех типов функций; затем идёт соглашение о передаче аргументов и о том, как в своём фрейме функция хранит значения. В V8 мы имеем соглашение для фреймов JS, что аргументы до вызова функции (включая приёмник) добавляются на стек в обратном порядке, а также о том, что первые несколько слотов стека это вызываемая функция, контекст, с которым она вызывается, и количество передаваемых аргументов. Вот наш стандартный фрейм JS.

Это соглашение о вызове JS, общее для оптимизированных и интерпретируемых фреймов, именно оно позволяет нам, например, при профилировании кода на панели производительности отладчика проходить по стеку с минимальными накладными расходами.

В случае Ignition соглашение становится более явным. Ignition интерпретатор на основе регистров, это означает, что есть виртуальные регистры (не путайте их с машинными!), которые хранят текущее состояние интерпретатора. включая локальные переменные (объявления var, let, const) и временные значения. Эти регистры содержатся в стековом фрейме интерпретатора, вместе с указателем на выполняемый массив байт-кода и смещением текущего байт-кода в массиве.

Sparkplug намеренно создаёт и поддерживает соответствующий фрейму интерпретатора макет фрейма. Всякий раз, когда интерпретатор сохраняет значение регистра, SparkPlug также сохраняет его. Делает он это по нескольким причинам:

1. Это упрощает компиляцию Sparkplug; новый компилятор может просто отражать поведение интерпретатора без необходимости сохранять какое-либо отображение из регистров интерпретатора в состояние Sparkplug.

2. Поскольку компилятор байт-кода выполнил тяжёлую работу по распределению регистров, такой подход ускоряет компиляцию.

3. Это делает интеграцию с остальной частью системы почти тривиальной; отладчик, профайлер, раскручивание стека исключений, вывод трассировки все эти операции идут по стеку, чтобы узнать, каков текущий стек выполняемых функций, и все эти операции продолжают работать со Sparkplug почти без изменений, потому всё, что касается их, они получают из фрейма интерпретатора.

4. Тривиальной становится и замена на стеке (OSR). Замена на стеке это когда выполняемая функция заменяется в процессе выполнения; сейчас это происходит, когда интерпретированная функция находится в горячем цикле (в это время она поднимается до оптимизированного кода этого цикла) и где оптимизированный код деоптимизируется (когда он опускается и продолжает выполнение функции в интерпретаторе), любая работающая в интерпретаторе логика замены на стеке будет работать и для Sparkplug. Даже лучше: мы можем взаимозаменять код интерпретатора и SparkPlug почти без накладных расходов на переход фреймов.

Мы немного изменили стековый фрейм интерпретатора: во время выполнения кода Sparkplug не поддерживается актуальная позиция смещения. Вместо этого мы храним двустороннее отображение из диапазона адресов кода Sparkplug к соответствующему смещению. Для декодирования такое сопоставление относительно просто, поскольку код Sparklpug получается линейным проходом через байт-код. Всякий раз, когда стековый фрейм хочет узнать "смещение байт-кода" для фрейма Sparkplug, мы смотрим на текущую выполняемую инструкцию в отображении и возвращаем связанное смещение байт-кода. Аналогично, когда Sparkplug нужно узнать OSR из интерпретатора, мы смотрим на байт-код в смещении и перемещаемся к соответствующей инструкции Sparkplug.

Вы можете заметить, что теперь у нас есть неиспользуемый слот фрейма, где должно быть смещение байт-кода; избавиться от него мы не можем, поскольку хотим сохранить оставшуюся часть стека неизменной. Мы перепрофилируем этот слот стека, чтобы вместо него кешировать "вектор обратной связи" для текущей выполняющейся функции; это вектор, хранящий данные о форме объекта, и он должен быть загружен для большинства операций. Всё, что нам нужно делать, соблюдать осторожность с OSR, чтобы гарантировать, что мы подставляем либо правильное смещение байт-кода, либо правильный вектор обратной связи для этого слота. В итоге стековый фрейм Sparkplug выглядит так:

Полагаемся на встроенный код

На самом деле Sparkplug генерирует очень мало собственного кода. У JS сложная семантика, так что для выполнения даже самых простых операций требуется много кода. Принудительная повторная генерация такого кода при каждой компиляции оказалась бы плохим решениям по нескольким причинам:

1. Из-за огромного количества кода, который необходимо сгенерировать, она значительно увеличила бы время компиляции.

2. Этот подход увеличил бы потребление памяти кодом Sparkplug.

3. Пришлось бы переписывать кодогенерацию для большого количества функциональности JS, что, вероятно, означало бы и больше ошибок, и большую поверхность атаки.

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

Вы можете подумать: "Ну и какой тогда смысл во всём этом? Разве Sparkplug не выполняет ту же работу, что и интерпретатор?" и во многом будете правы. Во многих отношениях Sparkplug является "просто" сериализацией выполнения интерпретатора, вызывая те же встроенные двоичные сниппеты и поддерживая тот же стековый фрейм. Тем не менее оно того стоит, потому что Sparkplug удаляет (или, точнее, предварительно компилирует) те самые неустранимые накладные расходы интерпретатора, такие как декодирование операндов и диспетчеризация следующего байт-кода.

Оказалось, что интерпретация эффективнее множества оптимизаций уровня центрального процессора: статические операнды динамически читаются из памяти интерпретатором, вынуждая процессор делать предположения о том, какими могут быть значения. Диспетчеризация к следующей инструкции байт-кода для сохранения производительности требует успешного прогнозирования ветви выполнения, и, даже если предположения и прогнозы верны, по-прежнему нужно выполнять декодирование и диспетчеризацию кода, а также занимать драгоценное пространство различных буферов и кешей. ЦП сам по себе эффективный интерпретатор, хотя он применяется к машинному коду. С этой точки зрения Sparkplug транспилятор из байт-кода Ignition в байт-код центрального процессора, перемещающий выполнение в "эмуляторе" к "нативному" выполнению.

Производительность

Так как же Sparkplug работает на практике? Мы выполнили несколько бенчмарков Chrome на наших ботах для замера производительности со Sparkplug и без него. Спойлер: мы очень довольны.

В тестах ниже различные боты выполнялись на разных операционных системах. Хотя операционная система выделена в названии бота, мы не считаем, что она оказывает большое влияние на результаты. Скорее разные машины обладают разными конфигурациями процессора и памяти, которые, как мы считаем, являются основной причиной различий.

Speedometer

Speedometer это тест, который пытается эмулировать реально работающий фреймворк, создавая веб-приложение для отслеживания списка задач с использованием нескольких популярных фреймворков и проводя стресс-тестирование производительности этого приложения добавлением и удалением задач. Мы обнаружили, что это отличное отражение поведения загрузки и взаимодействия в реальном мире, и мы неоднократно обнаруживали, что улучшения в спидометре отражаются на наших реальных показателях. Со Sparkplug оценка Speedometer улучшается на 510 %, в зависимости от бота.

Обзор бенчмарка

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

На этих тестах мы решили посмотреть метрику V8 Main-Thread Thread, измеряющую общее проведённое в V8 время (включая компиляцию и выполнение), в основном потоке (то есть исключая стриминговый парсинг или фоновую оптимизацию). Это лучший способ увидеть, насколько оправдан Sparkplug, без учёта других источников шума бенчмарка.

Результаты различны и сильно зависят от машины и веб-сайта, но в целом выглядят прекрасно: видно улучшение около 515 %.

Таким образом, V8 имеет новый сверхбыстрый неоптимизирующий компилятор, повышающий производительность V8 в реальных бенчмарках на 515 %. Он уже доступен в V8 v9.1 (укажите опцию --sparkplug), и мы выпустим его вместе с Chrome 91.

Вот что важно заметить: выделившись в отдельную область разработки, фронтенд не ограничивается одним только JavaScript, например есть множество тонкостей в том, каким образом браузер работает с CSS. Вместе с тем оптимизации на уровне браузера не означают, что можно больше не писать аккуратный, компактный и элегантный код. Скорее они означают, что теперь разработчики будут свободнее чувствовать себя, когда захотят написать сложную или тяжёлую функциональность. Если фронтенд вам интересен, вы можете обратить внимание на наш курс Frontend-разработчик, где получите комплексную подготовку, чтобы в дальнейшем писать и поддерживать приложения различного масштаба и уровня сложности.

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering

Виктор Петухов, студент второго курса аспирантуры Университета ИТМО и техлид в одной из команд проекта Kotlin в JetBrains (занимается компилятором Kotlin), решил совместить работу с детальным изучением профессиональной проблематики в научном формате и присоединился клаборатории машинного обучения ИТМО. Рассказываем, что из этого получилось.

История вопроса

Языки программирования фундамент огромного спектра продуктов, сервисов и критически значимой инфраструктуры. В своей научной статье по этой теме Виктор подчеркивает, что ошибки в коде компиляторов действительно могут привести к существенным последствиям. Однако количество всевозможных тестовых сценариев для них обычно крайне велико, поэтому составлять их приходится с привлечением интеллекта человеческого или искусственного, чтобы должным образом исследовать наиболее подверженные ошибкам части компилятора.

Но автоматическое составление таких тестов обладает ограничениями. Как правило, мы тяготеем к генерированию семантически корректных фрагментов кода, минуя парсер (самую простую часть компилятора) и пробираясь к самым сложными частям: подсистеме вывода типов, механизму разрешения вызовов и прочим. Если использовать для этого формальную модель, такую как грамматику, доля получаемых семантически корректных фрагментов кода будет слишком мала.

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

Задача попутной оптимизации характеристики производительности при генерации кода является не простым дополнением к произвольной генерации. На данный момент над этой проблемой работает не так много специалистов, поэтому Виктор увидел здесь возможность для развития профессиональных и научных компетенций решил предложить такой способ генерации исходного кода на Kotlin, чтобы либо время компиляции, либо потребляемая память были максимальными.

Как это работает

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

Генератор кода, в свою очередь, также должен обеспечивать как можно большую долю семантически корректных фрагментов. Для этого Виктор вместе с коллегами разработал генератор с оператором скрещивания, который учитывает типы доступных переменных.

На скриншоте продемонстрирована возможная подстановка одного фрагмента кода вместо другого (скрещивание двух файлов с исходных кодом). Здесь видно, что такая подстановка будет совместима по типам, в соответствии с реализованным оператором скрещивания. В месте, куда подставляется фрагмент кода, присутствуют все требуемые типы или их подтипы, присутствующие внутри подставляемого фрагмента.

В ходе эксперимента были обнаружены некоторые проблемы в производительности компилятора Kotlin например, экспоненциальный рост времени анализа лямбд в правой части оператора += по мере увеличения глубины вложенности этих лямбд. Команда компилятора уже занимается этой проблемой. На скриншоте далее показываем, как изменяется время компиляции приведенного фрагмента кода, если добавлять вложенные лямбды.

Что дальше

Сейчас проектом занимаются пять человек. Это коллективный труд исследователей Университета ИТМО и представителей JetBrains. Коллеги убеждены в целесообразности продолжения исследования и совершенствования предложенного Виктором подхода.

Мы хотели бы реализовать и оператор мутации, чтобы избавиться от предвзятости относительно начального набора данных и генерировать принципиально новые конструкции языка. Помимо генетического программирования мы планируем применить здесь и генеративные модели, а затем провести сравнение результатов и подумать о разработке методологии тестирования производительности компиляторов

Виктор Петухов, аспирант второго года обучения, программист на факультете ИТ и программирования, программист в JetBrains и в команде компилятора Kotlin.

Дополнительное чтение в нашем блоге на Хабре:

• Какие проекты готовит лаборатория молодежной робототехники

• Мы делаем то, что до нас мало кто делал: говорим об инфохимии

• Как выглядит междисциплинарный подход в области робототехники

Разработка моего статически типизированного скриптового языка Umka вошла в ту стадию, когда потребовалась проверка языковых возможностей на более сложных примерах, чем скрипты в пару десятков строк. Для этого я решил реализовать на своём языке интерпретатор Lisp. На это меня вдохновил педагогический эксперимент Роба Пайка, одного из создателей языка Go. Недавно Пайк опубликовал маленький интерпретатор Lisp на Go. Особенно впечатлило замечание Пайка, что описание интерпретатора заключено на одной странице 13 древнего руководства по Lisp 1.5. Учитывая синтаксическое родство Umka и Go, было трудно не поддаться соблазну построить такой интерпретатор на Umka, но не буквальным переносом кода Пайка, а полностью заново, от основ. Надеюсь, знатоки Lisp и функциональных языков простят мне наивное изумление от соприкосновения с прекрасным.

На непосвящённых Lisp может произвести впечатление, близкое к шоку. Где граница между кодом и данными? Где циклы? Где стек? Единственной структурой данных является дерево. Оно же может представлять список. Оно же становится абстрактным синтаксическим деревом при разборе программы. Оно же заменяет собой стек при вычислении выражений. Любое дерево можно попытаться исполнить как код или использовать как данные. Вместо циклов рекурсия. В ядре языка нет даже арифметики. И тем не менее, это полный по Тьюрингу язык, который можно бесконечно расширять и посыпать синтаксическим сахаром.

Определение минимального интерпретатора Lisp действительно занимает меньше страницы. Конечно, с некоторой натяжкой: в нём используются функции, определённые на нескольких предыдущих страницах. Кажется, создатель Lisp Джон Маккарти из азарта старался превзойти сам себя в лаконизме и в итоге опубликовал микроруководство по Lisp, содержащее определение языка вместе с исходником интерпретатора в общей сложности две журнальные страницы. Правда, добавил в заголовок: "Not the whole truth".

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

С помощью этих конструкций можно определять и вызывать рекурсивные функции, так что в одном выражении будет заключена целая программа. Если к этому добавить ещё и арифметические функции, то можно, например, рассчитать факториал 6:

((label fac (lambda (n) (cond ((eq n 0) 1) ((quote t) (mul n (fac (sub n 1))))))) 6)

В микроруководстве Маккарти этими средствами выражен весь интерпретатор Lisp, за исключением лексического и синтаксического разбора. В руководстве Lisp 1.5 на той самой странице 13 приведён почти такой же интерпретатор, но в более человекочитаемом псевдокоде. Его я и взял за основу своего маленького проекта. Потребовалось лишь добавить разбор текста программы, некое подобие REPL и импровизированную арифметику. Роб Пайк, видимо, поступил так же, но отказался от конструкции label в пользу defn, которая позволила ему не определять функцию заново всякий раз, когда требуется её вызвать. В ядре Lisp такой возможности не предусмотрено.

Поскольку весь интерпретатор пронизан рекурсией и обработкой деревьев, он послужил отличным тестом многих возможностей языка Umka от формирования стековых кадров до сборки мусора. Думаю, Umka хорошо справился с испытанием. Исправлять пришлось лишь два-три мелких бага, связанных с экспортом имён и опережающим описанием типов. Весь код интерпретатора занял меньше 400 строк.

Желающим поиграть с моим интерпретатором и передать по эстафете вдохновение от Роба Пайка рекомендую взять папку с примерами из ветки master, а не из последнего выпуска.

Введение

Как-то на одном из компьютерных форумов участники делились соображениями, чего им не хватает в языках, так сказать, в повседневной деятельности. Один заявил, что ему очень не хватает оператора типа put data. Для тех, кто не слышал о таком, поясню, что в языке PL/1 был предусмотрен оператор вывода (или ввода) значений переменных вместе с их именами, т.е. вместе с идентификаторами.

Например, если обычный вывод put list(X,Y); давал что-нибудь вроде:

1280 1024

то оператор put data(X,Y); печатал:

X= 1280 Y= 1024

не заставляя писать для этого вывод в виде оператора:

put list(X=,X,Y=,Y);

Чаще всего это использовалось в отладочных целях, но не обязательно. Например, используя вывод в текстовый файл с помощью put data, а затем ввод этих же данных как исходных в другой программе с помощью зеркального оператора get data можно было получить удобную для чтения и редактирования форму представления исходных данных в текстовом виде.

Можно возразить, что современные оболочки систем программирования легко позволяют вывести значения (и имена) любых объектов программы в интерактивном режиме безо всяких put data и поэтому в нем больше нет необходимости.

Я тоже использую встроенный интерактивный отладчик, с помощью которого можно посмотреть любые, даже сложные (составные) данные. Однако потребность в возможностях put data не исчезла. Иногда нужен и анализ данных на распечатке, (т.е. в логе) с возможностью быстрого и удобного добавления в текст программы вывода для отладки. К тому же для работы отладочных интерактивных систем используется дополнительная информация, которая обычно в выполняемом exe-файле отсутствует. В этом же случае все имена переменных зашиты в самой программе. Таким образом, удобства, предоставляемые языком в виде оператора, подобного put data, не заменяют, а дополняют возможности отладчиков. Кстати, в стародавние времена так называемая посмертная выдача на печать после ошибки иногда включала в себя и вывод полного списка всех имен переменных вместе с их текущими значениями. Некоторым программистам так нравился такой вывод, что они специально в конце своей программы ставили деление на ноль.

Реализации ввода-вывода с именами

В исходном варианте компилятора, которым я пользуюсь и который по мере сил развиваю, оператора put data не было. И мне его тоже очень не хватало в процессе отладки. Требовалось его ввести, причем хотелось сделать все как можно проще, компактнее и не внося больших изменений в компилятор. Поэтому была принята следующая схема реализации:

1. Сначала компилятором выполняется обычный разбор очередного объекта, перечисленного в списке ввода-вывода. Но при этом все лексемы, которые выдал лексический анализатор по запросу компилятора, еще и запоминаются в специальном буфере. По окончании разбора результат (т.е. все получившиеся операции внутреннего представления программы) отбрасывается, но характеристики объекта, например, его имя в программе, размерность и т.п., становятся известны.

2. Затем разбор повторяется заново, теперь полученные операции внутреннего представления программы будут использованы для генерации кода. Однако при разборе вместо лексического анализатора подключается его эмулятор, который уже не проводит лексический анализ исходного текста, а просто достает и выдает компилятору разобранные ранее и запомненные лексемы. Кроме них эмулятор может выдать и новые, сгенерированные им самим, лексемы.

Получается, что компилятор как бы сам для себя на ходу изменяет и дописывает исходный текст программы и тут же исправленный текст обрабатывает штатным образом. В чем-то эти действия немного похожи на макроподстановку.

Для реализации put data достаточно проанализировать запомненные в буфере лексемы, найти конец разбираемого элемента (это запятая вне скобок или внешняя закрывающая скобка) и все предыдущие лексемы объединить в одну строку, которую в начале работы эмулятора и выдать с признаком текстовая константа.

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

Таким образом, например, текст:

put data(x(i+1,j-1));

внутри компилятора будет восприниматься как:

put list(x(i+1,j-1)=,x(i+1,j-1));

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

Ввод-вывод не скалярных объектов

Идея исправлять исходный текст программы на лету позволила легко решить поставленную задачу. Однако полученный механизм жаль было использовать только для такой мелочи как put data, поскольку этот же подход можно было применить и для более объемной задачи ввода-вывода не скалярных объектов. Автоматический ввод-вывод всех элементов не скалярного объекта также был предусмотрен в языке и тоже отсутствовал в исходной версии компилятора, хотя на практике часто требовался.

Здесь ситуация сложнее, чем с put data для скаляра, так как для вывода массива вместо текста:

put data(x);

требовалось на лету сформировать уже что-нибудь вроде:

do i=lbound(x) to hbound(x); put data(x(i)); end;

Но и это еще не все. Например, если x двумерный массив целых (например, матрица 3х3), тот же самый оператор put data(x); уже должен осуществлять вывод по двум циклам, чтобы дать в результате что-то такое:

X(1,1)= 1 X(1,2)= 2 X(1,3)= 3 X(2,1)= 4 X(2,2)= 5 X(2,3)= 6 X(3,1)= 7 X(3,2)= 8 X(3,3)= 9

Но при этом оператор put data(x(2)); должен вывести лишь одну строку матрицы:

X(2,1)= 4 X(2,2)= 5 X(2,3)= 6

А если x это набор разнотипных элементов (в PL/1 такой набор называется структурой), то нужно еще выводить и имена отдельных полей этого набора, например:

declare

1 a,

2 a1 fixed,

2 a2 fixed,

2 b,

3 b1 fixed,

3 b2 float;

put data(a);

A.A1= 0 A.A2= 0 A.B.B1= 0 A.B.B2= 0.000000E+00

Учитывая, что в структуре могут быть подструктуры, в свою очередь включающие массивы (т.е. могут быть и структуры массивов и массивы структур), то задача автоматического вывода элементов становится довольно громоздкой:

declare

1 a(1:2),

2 a1 fixed,

2 a2 fixed,

2 b,

3 b1 (-5:3) fixed,

3 b2 float;

put data(b);

B(1).B1(-5)= 0 B(1).B1(-4)= 0 B(1).B1(-3)= 0 B(1).B1(-2)= 0 B(1).B1(-1)= 0 B(1).B1(0)= 0 B(1).B1(1)= 0 B(1).B1(2)= 0 B(1).B1(3)= 0 B(1).B2= 0.000000E+00 B(2).B1(-5)= 0 B(2).B1(-4)= 0 B(2).B1(-3)= 0 B(2).B1(-2)= 0 B(2).B1(-1)= 0 B(2).B1(0)= 0 B(2).B1(1)= 0 B(2).B1(2)= 0 B(2).B1(3)= 0 B(2).B2= 0.000000E+00

Однако в языке PL/1 есть хорошая основа для доработок в виде возможности записать оператор цикла прямо внутри оператора ввода-вывода. В свое время разработчикам языка вывод массивов казался очень важным. Поэтому они разрешили писать цикл ввода-вывода в виде:

put list((x(i) do i=lbound(x) to hbound(x)));

вместо обычного цикла:

do i=lbound(x) to hbound(x); put list(x(i)); end;

Признаком начала цикла внутри оператора ввода-вывода является открывающая скобка. Кстати, разработчики PL/1 здесь немного попали впросак, поскольку при выводе выражения, начинающегося со скобки, большинство компиляторов воспримет эту скобку за начало цикла. Программистам приходилось писать выражения в экзотическом виде, только чтобы они не начинались со скобки:

put list(1e0*(x1+x2)/2e0));

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

Легко заметить, что вывод с именами (put data) и вывод не скалярных объектов это дополняющие друг друга возможности. Объединяет их то, что в обоих случаях разбор объекта при трансляции выполняется два раза. Сначала все лексемы при лексическом разборе объекта запоминаются, а при повторном разборе выдаются из буфера так, как если бы из исходного текста. Но при этом в нужный момент выдаются и новые лексемы. В обоих случаях вместо лексического анализатора работает его эмулятор. Когда нужны обе возможности одновременно работают оба эмулятора, один на более низком уровне выдает лексемы для индексов, названий полей структур и заголовков циклов, а второй добавляет к ним элементы с текстовыми константами-именами.

Причем эмулятор верхнего уровня, создающий текстовые константы-имена, даже не подозревает, что лексический анализатор уже заменен на эмулятор для выдачи элементов массива и имен структур. Обе доработки компилятора не мешают друг другу и действуют независимо.

При этом работа эмулятора нижнего уровня гораздо сложнее, чем в случае put data, здесь используется такой алгоритм, как конечный автомат. Т.е. эмулятор имеет несколько состояний, запоминаемых между вызовами, при разборе переходя от одного к другому и выдавая в каждом состоянии лексемы разного типа. Это позволяет сначала выдать одну или несколько лексем - открывающих скобок, затем все имена промежуточных уровней структуры и все индексы, как переменные циклов, а затем набор лексем, обозначающих заголовки циклов по каждой размерности и, наконец, лексемы - закрывающие скобки.

Естественно, что если в исходном тексте старшие индексы объекта были явно указаны, то эмулятор дописывает только недостающие младшие индексы. Поэтому, например, для трехмерного массива x(1:10,1:10,1:10) оператор вывода:

put list(x); выдаст 1000 значений

put list(x(5)); выдаст 100 значений

put list(x(5,6)); выдаст 10 значений.

А для оператора put list(x(5,6,8)); эмулятор вообще не сгенерирует дополнительных лексем-индексов и будет напечатано единственное значение.

Недостатком описанной реализации оказалось то, что при применении оператора put data к не скалярным объектам на печати вместо всех значений индексов печатались идентификаторы переменных циклов, которые подставлялись в исходный текст в момент трансляции. А поскольку для этой цели использовались служебные целые переменные ?A, ?B, ?С,?O (всего 15 штук для максимально возможной размерности массива 15) выдача выглядела странно и во многом теряла ценность:

X(?A,?B)= 1 X(?A,?B)= 2 X(?A,?B)= 3 X(?A,?B)= 4 X(?A,?B)= 5 X(?A,?B)= 6 X(?A,?B)= 7 X(?A,?B)= 8 X(?A,?B)= 9

Для исправления этого недостатка потребовалось доработать системную библиотеку. В случае оператора put data с индексами компилятор не просто формирует текстовую константу имя переменной с подставленными индексами ?A, ?B, ?С,?O, но и дописывает перед каждым индексом специальный не выводимый символ 07FH.

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

Переменные с именами при вводе

Естественно, имеется парный оператор к put data - это get data, который должен вводить значения переменных, заданные вместе с их именами. Но здесь, на мой взгляд, разработчики PL/1 переусложнили данный оператор. В соответствии со стандартом языка оператор ввода должен не просто пропускать имена, но распознавать их и записывать следующее далее значение по нужному адресу. Например, если перетасовать значения, выданные put data(x);, в другом порядке:

X(1,2)= 2 X(1,1)= 1 X(2,3)= 6 X(2,1)= 4 X(2,2)= 5 X(3,1)= 7 X(1,3)= 3 X(3,2)= 8 X(3,3)= 9

То оператор get data(x); все равно должен ввести значения в правильном порядке, распознав каждое имя и индексы перед знаком равенства. И хотя такая обработка дает дополнительные удобства, например, можно пропускать данные, которые не меняются при вводе, все-таки это слишком хлопотно и сложно для реализации. А, главное, для такой возможности нужно иметь таблицу имен переменных и их адресов в каждом exe-файле, использующем get data. Поэтому я не стал реализовывать распознавание имен при вводе, а ограничился при чтении простым пропуском всех символов до знака равенства при разборе очередного элемента. Самое важное для меня операторы put data и get data остались зеркальными и выдача данных оператором put позволяет потом безошибочно читать их оператором get с таким же списком объектов.

Заключение

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

Мало этого, в данном случае удалось, не затрагивая работу основных частей компилятора, добавить дополняющие друг друга возможности и автоматического формирования имен, и автоматического вывода всех элементов массива. Объем кода доработок составил менее процента от общего объема компилятора, однако они оказывают существенную помощь, особенно при отладке, экономя и время, и внимание программиста при написании операторов ввода-вывода.

Послесловие

По личному опыту знаю, что, самая распространенная реакция на подобные заметки обычно сводится к двум заявлениям:

1. Это нафиг никому не нужно.

2.Это легко повторить на любом современном языке.

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

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

Поэтому мне была предложена несложная библиотека на Немерле, реализующая, как уверял ее автор, вывод с именами и повторяющий возможности старого PL/1:

using System.Console;using PL1.Macro;module Program{  Main() : void  {    def x = 1280;    def y = 1024;    put data(x, y);    put data(x, y, x + y, x.ToString() + "asd");    _ = ReadLine();  }}using Nemerle;using Nemerle.Compiler;using Nemerle.Compiler.Parsetree;using System.Collections.Generic;using System.Linq;namespace PL1.Macro{  public macro PutData(args)  syntax ("put", "data", args)  {    PutDataImpl.Impl(args)  }  module PutDataImpl  {    public Impl(args : PExpr) : PExpr    {      match (args)      {        | PExpr.Tuple as args =>          def code = List();          foreach (arg in args.args)          {            code.Add(<[ $(arg.ToString()) ]>);            code.Add(<[ "=" ]>);            code.Add(arg);            code.Add(<[ " " ]>);          }          code.RemoveAt(code.Count - 1);          def code = code.Aggregate((a1, a2) => <[ $a1 + $a2 ]>);          <[ System.Console.WriteLine($(code)) ]>        | _ => PExpr.Error(args.Location, "Tuple expected.")      }    }  }}

Однако на предложение доработать библиотеку, чтобы она позволяла выводить и не скалярные объекты с печатью всех индексов (и тогда действительно бы повторяла возможности PL/1), мне в ответ было предложено сделать это самому в виде домашнего задания. Оказанную честь я отклонил, под предлогом того, что вообще-то у меня все это уже давно есть и используется. Судя по всему, автор библиотеки просто сразу не сообразил, как это сделать. И почему-то вспомнилась сцена из фильма Формула любви, где Калиостро удивив всех поеданием вилки, все-таки отказался съесть при этом еще и тарелку.

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

Счетчики вызовов методов и итераций циклов

Главным фактором влияющим на решение JVM о компиляции какого-либо кода является частота его исполнения. Решение принимается на основе двух счетчиков: счетчика количества вызовов метода и счетчика количества итераций циклов в методе.

Когда JVM исполняет какой-либо метод, она проверяет значения этих двух счетчиков, и принимает решение о необходимости его компиляции. У этого типа компиляции нет официального названия, но часто его называют стандартной компиляцией.

Аналогично, после каждой итерации цикла проверяется значение счетчика цикла и принимается решение о необходимости его компиляции.

При выключенной многоуровневой компиляции стандартная компиляция управляется параметром -XX:CompileThreshold. Значением по умолчанию является 10000. Несмотря на то, что параметр всего один, превышение порога определяется суммой значений двух счетчиков. В настоящее время этот флаг ни на что не влияет (многоуровневая компиляция включена по умолчанию), но знать о нем полезно, ведь существует довольно много унаследованных систем.

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

Последнее утверждение довольно интересно. Ведь если программа исполняется бесконечно, не должен ли весь ее код в конце концов скомпилироваться? На самом деле не должен, поскольку значения счетчиков не только увеличиваются при каждом вызове метода или итерации цикла, но и периодически уменьшаются. Таким образом, они являются отражением текущего нагрева метода или цикла.

Получается, что до внедрения многоуровневой компиляции методы, выполнявшиеся довольно часто, но недостаточно часто, чтобы превысить порог, никогда бы не были скомпилированы. В настоящее время такие методы будут скомпилированы компилятором C1, хотя, возможно, их производительность была бы выше, будь они скомпилированы компилятором C2. При желании можно поиграть параметрами -XX:Tier3InvocationThreshold (значение по умолчанию 200) и -XX:Tier4InvocationThreshold (значение по умолчанию 5000), но вряд ли в этом есть большой практический смысл. Такие же параметры (-XX:TierXBackEdgeThreshold) существуют и для задания пороговых значений счетчиков циклов.

Потоки компиляции

Как только JVM решает скомпилировать метод или цикл, они помещаются в очередь. Эта очередь приоритетная - чем выше значения счетчиков, тем выше приоритет. Это особенно помогает при старте приложения, когда необходимо компилировать огромное количество кода. Таким образом, более важный код будет скомпилирован раньше.

Компиляторы C1 и C2 имеют собственные очереди, каждая из которых может обрабатывается несколькими потоками. Существует специальная формула для вычисления количества потоков в зависимости от количества ядер. Некоторые значения приведены в таблице:

Задать произвольное количество потоков можно параметром -XX:CICompilerCount. Это общее количество потоков компиляции, которое будет использовать JVM. При включенной многоуровневой компиляции одна треть из них (но минимум один) будут отданы компилятору C1, остальные достанутся компилятору C2. Значением по умолчанию для этого флага является сумма потоков из таблицы выше. При выключенной многоуровневой компиляции все потоки достанутся компилятору C2.

В каком случае имеет смысл менять настройки по умолчанию? Ранние версии Java 8 (до update 191) при запуске в Docker контейнере не корректно определяли количество ядер. Вместо количества ядер, выделенных контейнеру определялось количество ядер на сервере. В этом случае есть смысл задать количество потоков вручную, исходя из значений, приведенных в таблице выше.

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

Еще один параметр, влияющий на количество потоков компиляции - это -XX:+BackgroundCompilation. Его значение по умолчанию - true. Он означает, что компиляция должна происходить в асинхронном режиме. Если установить его в false, каждый раз при наличии кода, который необходимо скомпилировать, JVM будет ожидать завершения компиляции, прежде чем этот код исполнить.

Оптимизации

Как мы знаем, JVM использует результаты профилирования методов в процессе компиляции. JVM хранит данные профиля в объектах, называемых method data objects (MDO). Объекты MDO используются интерпретатором и компилятором C1 для записи информации, которая затем используется для принятия решения о том, какие оптимизации возможно применить к компилируемому коду. Объекты MDO хранят информацию о вызванных методах, выбранных ветвях в операторах ветвления, наблюдаемых типах в точках вызова. Как только принято решение о компиляции, компилятор строит внутреннее представление компилируемого кода, которое затем оптимизируется. Компиляторы способны проводить широкий набор оптимизаций, включающий:

• встраивание (inlining);

• escape-анализ (escape-analysis);

• размотка (раскрутка) цикла (loop unrolling);

• мономорфная диспетчеризация (monomorphic dispatch);

• intrinsic-методы.

Встраивание

Встраивание - это копирование вызываемого метода в место его вызова. Это позволяет устранить накладные расходы, связанные с вызовом метода, такие как:

• подготовка параметров;

• поиск по таблице виртуальных методов;

• создание и инициализация объекта Stack Frame;

• передача управления;

• опциональный возврат значения.

Встраивание является одной из оптимизаций, выполняемых JVM в первую очередь, оно включено по умолчанию. Отключить его можно флагом -XX:-Inline, хотя делать этого не рекомендуется. JVM принимает решение о необходимости встраивания метода на основе нескольких факторов, некоторые из которых приведены ниже.

• Размер метода. Горячие методы являются кандидатами для встраивания если их размер меньше 325 байт (или меньше размера заданного параметром -XX:MaxFreqInlineSize). Если метод вызывается не так часто, он является кандидатом для встраивания только если его размер меньше 35 байт (или меньше размера заданного параметром -XX:MaxInlineSize).

• Позиция метода в цепочке вызовов. Не подлежат встраиванию методы с позицией больше 9 (или значения заданного параметром -XX:MaxInlineLevel).

• Размер памяти, занимаемой уже скомпилированными версиями метода в code cache. Встраиванию не подлежат методы, скомпилированные на последнем уровне, версии которых занимают более 1000 байт при выключенной многоуровневой компиляции и 2000 байт при включенной (или значения заданного параметром -XX:InlineSmallCode).

Escape-анализ

Escape-анализ - это техника анализа кода, которая позволяет определить пределы достижимости какого-либо объекта. Например, escape-анализ может использоваться для определения является ли объект созданный внутри метода достижимым за пределами области видимости метода. Сам по себе escape-анализ не является оптимизацией, но оптимизации могут выполняются по его результатам.

Предотвращение выделений памяти в куче

Создание новых объектов внутри циклов может создать нагрузку на систему выделения памяти. Создание большого числа короткоживущих объектов потребует частых сборок мусора в молодом поколении. Если частота создания объектов будет достаточно большой, короткоживущие объекты могут попасть и в старое поколение, что потребует уже дорогостоящей полной сборки мусора. Если JVM убедится, что объект не достижим за пределами области видимости метода, она может применить технику оптимизации, называемую скаляризация. Поля объекта станут скалярными значениями и будут храниться в регистрах процессора. Если регистров не достаточно, скалярные значения могут храниться в стеке.

Блокировки и escape-анализ

JVM способна использовать результаты escape-анализа для оптимизации производительности блокировок. Это относится только к блокировкам с помощью ключевого слова synchronized, блокировки из пакета java.util.concurrent таким оптимизациям не подвержены. Возможными оптимизации приведены ниже.

• Удаление блокировок с объектов недостижимых за пределами области видимости (lock elision).

• Объединение последовательных синхронизированных секций, использующих один и тот же объект синхронизации (lock coarsening). Выключить эту оптимизацию можно флагом -XX:-EliminateLocks.

• Определение и удаление вложенных блокировок на одном и том же объекте (nested locks). Выключить эту оптимизацию можно флагом -XX:-EliminateNestedLocks.

Ограничения escape-анализа

Поскольку регистры процессора и стек являются ресурсами довольно ограниченными, существуют ограничения и на их использование. Так, например, массивы размером более 64 элементов не участвуют в escape-анализе. Этот размер можно задавать параметром -XX:EliminateAllocationArraySizeLimit. Представьте код, создающий временный массив в цикле. Если массив не достижим за пределами метода, массив не должен создаваться в куче. Но если его размер больше 64 элементов, он будет создаваться именно там, даже при условии, что реально используется не весь массив.

Еще одно ограничение заключается в том, что частичный escape-анализ не поддерживается. Если объект выходит за пределы области видимости метода хотя бы по одной из веток, оптимизация по предотвращению создания объекта в куче не применима. Пример подобного кода приведен ниже.

for (int i = 0; i < 100_000_000; i++) {    Object mightEscape = new Object(i);    if (condition) {        result += inlineableMethod(mightEscape);    } else {        result += tooBigToInline(mightEscape);    }}

Но если вам удастся локализовать создание объекта внутри ветки, в которой объект не выходит за пределы области видимости, то данная оптимизация будет применена в этой ветке.

if (condition) {        Object mightEscape = new Object(i);        result += inlineableMethod(mightEscape);    } else {        Object mightEscape = new Object(i);        result += tooBigToInline(mightEscape);    }}

Размотка (раскрутка) цикла

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

В результате размотки цикла такой код:

int i;for ( i = 1; i < n; i++){    a[i] = (i % b[i]);}

преобразуется в код вида:

int i;for (i = 1; i < n - 3; i += 4){    a[i] = (i % b[i]);    a[i + 1] = ((i + 1) % b[i + 1]);    a[i + 2] = ((i + 2) % b[i + 2]);    a[i + 3] = ((i + 3) % b[i + 3]);}for (; i < n; i++) {    a[i] = (i % b[i]);}

JVM принимает решение о размотке цикла по нескольким критериям:

• по типу счетчика цикла, он должен быть одним из типов int, short или char;

• по значению, на которое меняется счетчик цикла каждую итерацию;

• по количеству точек выхода из цикла.

Мономорфная диспетчеризация

Многие оптимизации, выполняемые компилятором C2 основаны на эмпирических наблюдениях. Одним из примеров является оптимизация под названием мономорфная диспетчеризация. Она основана на факте, что очень часто в точках вызова тип объекта во время выполнения остается неизменным. Это связано с особенностями объектно-ориентированного дизайна. Например, при вызове метода на объекте, наблюдаемый тип объекта при первом и последующих вызовах будет одним и тем же. Если это предположение верно, то вызов метода в этой точке можно оптимизировать. В частности, нет необходимости каждый раз выполнять поиск по таблице виртуальных методов. Достаточно один раз определить целевой тип объекта и заменить вызов виртуального метода быстрой проверкой типа и прямым вызовом метода на объекте целевого типа. Если в какой-то момент тип объекта поменяется, JVM откатит оптимизацию и будет снова выполнять вызов виртуального метода.

Большое число вызовов в типичном приложении являются мономорфными. JVM также поддерживает биморфную диспетчеризацию. Она позволяет делать быстрые вызовы методов в одной точке на объектах двух разных типов.

Вызовы, которые не являются ни мономорфными ни биморфными, называются мегаморфными. Если в точке вызова наблюдается не очень большое число типов, используя один трюк, можно немного выиграть в производительности. Достаточно отделить от точки вызова несколько типов, используя оператор instanceof так, чтобы в ней осталось только 2 конкретных типа. Примеры биморфного, мегаморфного и разделенного мегаморфного вызовов приведены ниже.

interface Shape {int getSides();}class Triangle implements Shape {public int getSides() {return 3;}}class Square implements Shape {public int getSides() {return 4;}}class Octagon implements Shape {public int getSides() {return 8;}}class Example {  private Random random = new Random();private Shape triangle = new Triangle();private Shape square = new Square();private Shape octagon = new Octagon();public int getSidesBimorphic() {Shape currentShape = null;switch (random.nextInt(2)) {case 0:currentShape = triangle;break;case 1:currentShape = square;break;}return currentShape.getSides();}  public int getSidesMegamorphic() {    Shape currentShape = null;    switch (random.nextInt(3))    {    case 0:      currentShape = triangle;      break;    case 1:      currentShape = square;      break;    case 2:      currentShape = octagon;      break;    }    return currentShape.getSides();}  public int getSidesPeeledMegamorphic() {    Shape currentShape = null;    switch (random.nextInt(3))    {    case 0:      currentShape = triangle;      break;    case 1:      currentShape = square;      break;    case 2:      currentShape = octagon;      break;    }    // peel one observed type from the original call site    if (currentShape instanceof Triangle) {      return ((Triangle) currentShape).getSides();    }    else {      return currentShape.getSides(); // now only bimorphic    }}}

Intrinsic-методы

Intrinsic-методы - это оптимизированные нативные реализации методов готовые к использованию JVM. Обычно это базовые, критичные к производительности методы, использующие специфичные функции операционной системы (ОС) или архитектуры процессора. Из-за этого они являются платформо-зависимыми и некоторые из них могут поддерживаться не каждой платформой. Примеры intrinsic-методов приведены в таблице ниже.

Шаблоны intrinsic-методов содержатся в исходном коде OpenJDK в файлах с расширением .ad (architecture dependent). Для архитектуры x86_64 они находятся в файле hotspot/src/cpu/x86/vm/x86_64.ad.

Деоптимизации

Когда мы рассматривали мониторинг работы компилятора в первой части, мы упомянули, что в логе могут появиться сообщения о деоптимизации кода. Деоптимизация означает откат ранее скомпилированного кода. В результате деоптимизации производительность приложения будет временно снижена. Существует два вида деоптимизации: недействительный код (not entrant code) и зомби код (zombie code).

Недействительный код

Код может стать недействительным в двух случаях:

• при использовании полиморфизма;

• в случае многоуровневой компиляции.

Полиморфизм

Рассмотрим пример:

Validator validator;if (document.isOrder()) {  validator = new OrderValidator();} else {  validator = new CommonValidator();}ValidationResult validationResult = validator.validate(document);

Выбор валидатора зависит от типа документа. Пусть для заказов у нас есть собственный валидатор. Предположим, что необходимо провалидировать большое количество заказов. Компилятор зафиксирует, что всегда используется валидатор заказов. Он встроит метод validate (если это возможно) и применит другие оптимизации. Далее, если на валидацию придет документ другого типа, предыдущее предположение окажется неверным, и сгенерированный код будет помечен как недействительный (non entrant). JVM перейдет на интерпретацию этого кода, и в будущем сгенерирует новую его версию.

Многоуровневая компиляция

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

Зомби код

Если в логе компиляции появилось сообщение о зомби коде, это значит, что все объекты, использующие предыдущие оптимизации были удалены из памяти и, как следствие, из code cache был удален код, ранее помеченный недействительным.

Список литературы и ссылки

• Java Performance: In-Depth Advice for Tuning and Programming Java 8, 11, and Beyond, Scott Oaks. ISBN: 978-1-492-05611-9.

• Optimizing Java: Practical Techniques for Improving JVM Application Performance, Benjamin J. Evans, James Gough, and Chris Newland. ISBN: 978-1-492-02579-5.

• Размотка цикла - википедия

Статьи цикла

• Java HotSpot JIT компилятор устройство, мониторинг и настройка (часть 1)

• Java HotSpot JIT компилятор устройство, мониторинг и настройка (часть 2)

На Хабре есть множество статей на тему ELF - что только люди с ними не делают - объясняют их устройство, собирают вручную и автоматически, редактируют, шифруют и еще много чего. Я, в свою очередь, хотел бы поделиться интересным, на мой взгляд, кейсом, познакомившим меня сразу со многими аспектами низкоуровневого программирования на практике:

• компиляция программ,

• своеобразный реверс-инжиниринг и портирование runtime-библиотек,

• устройство исполняемых файлов Windows и Linux,

• сборка и редактирование таких файлов вручную

Эти и некоторые другие аспекты, а так же множество нестандартных ходов будут затронуты при портировании компилятора. При этом, часть работы, связанная с исполняемыми файлами (и ELF'ами в частности) показалась мне наиболее интересной, поэтому она и станет лейтмотивом статьи.

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

В ходе работы нам понадобятся:

• компилятор gcc, линкер ld, отладчик gdb

• утилиты из binutils (readelf, strip, hexdump)

• базовое понимание устройства PE (Portable executable) и ELF

• знакомство с Pascal и ассемблером

Компилятор

Компилятор, который мы хотим портировать называется Bero TinyPascal Compiler (далее, BTPC) был написан в 2016 году немецким программистом-музыкантом и энтузиастом Pascal, Бенжамином Россо (Benjamin Rosseaux). Он компилирует подмножество Pascal'я (Delphi 7-XE7 и FreePascal >= 3) в бинарный код Windows x32. К тому же, компилятор самоприменимый.

Проект доступен на github и сейчас репозиторий содержит почти все необходимые для работы над ним инструменты. Однако, на момент выполнения работы, репозиторий выглядел примерно так:

Компилятор BTPC (и собранный из него btpc.exe) выполнен в self-contained виде - на все про все - один файл на ~3 тыс. строк паскаля. В нем представлен конвейер со всеми основными шагами компиляции - чтением входного потока, лексическим и синтаксическим анализом, генерацией промежуточного представления, генерацией кода. Поскольку, это не промышленный продукт, то никаких оптимизаций нет.

Начальные фазы разбора Pascal'я, вплоть до построения промежуточного кода, нас не очень интересуют - во-первых, это абсолютно типичные лексер и парсер, а во-вторых, они практически не будут изменены при портировании. Так что, примем их как данность. Наибольший интерес для нас представляет фаза синтеза и "все что после".

Фаза синтеза или умышленное падение с Seg fault

Итог работы компилятора BTPC - исполняемый файл формата PE (Portable Executable, подробнее на Википедии или Mircosoft), т.е. "ELF для Windows". В нем так же, как и в ELF, содержится все необходимое для отображения файла в память и запуска процесса, но организовано это все несколько иначе - отличия в основном касаются размещения в памяти.

Начнем рассмотрение фазы синтеза с момента, когда фронтенд уже выполнил свою часть, разобрав Pascal, и, когда у нас уже есть промежуточный код программы, байт-код:

• каждой инструкции байт-кода компилятор ставит в соответствие набор ассемблерных инструкций

• этот набор ассемблерных инструкций - по сути представление "бизнес-логики" программы в ассемблере

• бизнес-логика "подкладывается" в некоторый существующий PE-файл

• PE-файл редактируется, чтобы эта логика не "отвалилась" в процессе.

Концептуально это напоминает работу какого-нибудь фреймворка. Хотя фактически, это классическая библиотека времени выполнения (Runtime Library, RTL).

Наш PE-файл содержит библиотеку RTL с реализацией 9 простых функций:

• RTLHalt остановка программы

• RTLWriteChar запись charа в stdout

• RTLWriteInteger запись integer'а в stdout

• RTLWriteLn вывод linebreak'а в stdout

• RTLReadChar сохранение в EAX символа из STDIN

• RTLReadInteger сохранение в EAX integer'а из STDOUT

• RTLReadLn пропуск STDIN до EOF (конец файла) или ближайшего перевода строки

• RTLEOF возвращает в EAX положительное число в случае EOF. 0 в противном случае.

• RTLEOLN устанавливает 1 в DL, если следующий символ - \n, 0 в противном случае

Технически - это ассемблерный файл с одной лишь секцией кода на пару сотен строк, со следующей структурой:

.ENTRYPOINT  JMP StubEntryPoint# точка входа тут же отправляет нас в конец файлаRTLHalt:  ...                                 # определение фукнции RTLHaltRTLWriteChar:  ...                                 ...                                   # опеределения остальных функций RTLRTLFunctionTable:                     # таблица указателей на функции  DD OFFSET RTLHalt  DD OFFSET RTLWriteChar  DD OFFSET RTLWriteInteger  ...StubEntryPoint:  INVOKE HeapAlloc ...                # резервирование памяти  MOV ESI, OFFSET RTLFunctionTable    # сохранение таблицы функцийProgramEntryPoint:

Теперь, если скомпилировать и запустить приведенный выше RTL, происходит следующее:

• входная точка программы отправляет нас на метку StubEntryPoint

• резервируется память для будущей программы

• таблица функций сохраняется в неизменяемый в процессе работы регистр ESI

• управление передается программе

И программа падает, ведь метка ProgramEntryPoint указывает в никуда!

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

{ фронтенд компилятора }procedure EmitStubCode;begin  OutputCodeDataSize := 0;  OutputCodeString(#77#90#82#195#66#101#82#111#94#102#114#0#80#69#0#0#76#1#1#0#0#0#0#0#...  OutputCodeString(#0#0#0#0#0#0#0#0#0#0#0#0#0#0#16#0#0#0#16#0#0#143##16#0#0#0#0...  OutputCodeString(#0#0#0#0#0#0#0#0#0#0#255#255#255#255#40#16#0#0#53#0#0#0...  OutputCodeString(#101#110#106#97#109#105#110#32#39#66#101#82#111#...  OutputCodeDataSize := 1423;end;{ бэкенд компилятора }

И кажется, теперь стала понятна и архитектура компилятора:

• Библиотека RTL (с реализациями базовых функций) компилируется и дает нам исходный, готовый к работе PE-файл (хоть он и падает, но он чисто технически - рабочий)

• Этот PE-файл сериализуется в паскаль-строки (те самые, с ограничением в 255 символов в длину)

  • Если кода меньше, то окончание добивается инструкциями-заглушками NOP

• Эти паскаль-строки помещаются в качестве шаблона (набора констант) непосредственно в компилятор

Компилятор BTPC работает следующим образом:

• Считывает программу из stdin

• В процессе анализа генерирует промежуточный код программы, байт-код

• В процессе синтеза, инструкциям байт-кода ставит в соответствие ассемблерные инструкции

• Дописывает получающиеся инструкции в конец шаблона (сериализованного в паскаль-строки PE-файла)

• Редактирует шаблон таким образом, чтобы загрузчик "увидел" новый, дописанный в конец, код компилируемой программы

• Десериализует результат в исполняемый файл

Редактирование PE32

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

Пример правильного патчевания: размер секции кода занимает 4 байта, начиная со 156 байта. При этом во время компиляции было сгенерировано 100 байтов кода. Тогда, необходимо извлечь значение из этих 4х байтов, прибавить к нему 100 и записать обратно.

Стоит отметить, что изначально для компиляции RTL, Бенджамин использовал свой собственный тулчейн Excagena, который во-первых собирает крайне минималистичный выходной PE-файл. Обычно компиляторы/линкеры добавляют отладочную информацию в выходной файл, но Excagena вырезает все, что не влияет напрямую на работу.

Во-вторых, секция кода находится в самом конце полученного PE. То есть, буквально, метка ProgramEntryPoint - последнее, что в нем есть.

Цель всего этого - облегчить последний этап - редактирование PE-файла. И Бенджамину это вполне удалось - от него требуется лишь обновить пару значений в общей структуре:

• размер кода (OptionalHeader.SizeOfCode)

• размер секций (SectionTable.VirtualSize)

• размер образа (OptionalHeader.SizeOfImage), загруженного в память

Так что вся его хирургия выглядит вполне компактно - он считывает предыдущее значение поля, корректирует его с учетом добавленного фрагмента и выравнивания, и записывает обратно по прежнему адресу:

{ Вычисление размера кода } CodeSize := OutputCodeGetInt32($29) + (OutputCodeDataSize - CodeStart);OutputCodePutInt32($29, CodeSize);{ Определение текущего значения выравнивания } SectionAlignment := OutputCodeGetInt32($45);{ Вычисление и редактирование виртуального размера секции с учетом выравнивания }SectionVirtualSize := CodeSize;Value := CodeSize mod SectionAlignment;SectionVirtualSize := SectionVirtualSize + (SectionAlignment - Value);OutputCodePutInt32($10d, SectionVirtualSize);{ Редактирование размера образа при загрузке в память }OutputCodePutInt32($5d, SectionVirtualSize + OutputCodeGetInt32($39));

Хотя общая идея сейчас ясна, магическим $29, $45, $115 в оригинальном коде не помешали бы имена

Портирование компилятора

Мы разобрались с устройством компилятора, но наша конечная цель - получить работающий под Linux x64 компилятор. Чтобы ее достичь, понадобится выполнить следующее:

• переписать RTL библиотеку с использованием системных вызовов Linux x64

• собрать из нее исходный ELF-файл

• научиться динамически редактировать ELF-файл, дополненный кодом

Всего-то 3 шага

Первый эта достаточно простой - нужно "лишь" заменить системные вызовы к WinApi на линуксовые.

Но, как всегда, просто было на бумаге. Для примера можно взять вспомогательную функцию чтения символа. Устройство функции достаточно простое - подготовка регистров, обращение к Win32 API, установка еще пары значений:

ReadCharBuffer: DB 0x90ReadCharBytesRead: DB 0x90,0x8D,0x40,0x00ReadCharEx:  PUSHAD  INVOKE  ReadFile, DWORD PTR StdHandleInput, OFFSET ReadCharBuffer, 1, OFFSET ReadCharBytesRead, BYTE 0  TEST    EAX, EAX  SETZ    AL  OR      BYTE PTR IsEOF, AL  CMP     DWORD PTR [ReadCharBytesRead], 0  SETZ    AL  OR      BYTE PTR IsEOF, AL  POPAD  RET

Как упоминалось ранее, секция кода у нас единственная, при этом она и исполняемая и перезаписываемая. Причина в том, что среди кода хранятся и данные - в данном случае "между функций" приталились несколько байт под буферы чтения - ReadCharBuffer и ReadCharBytesRead. Пожалуй, мы знаем причину этого

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

Напомню, что в 64-битных системах системные вызовы совершаются инструкцией syscall (хотя это и не единственный способ). Аргументы передаются через регистры по порядку, RDI, RSI, RDX и так далее. Результат возвращается через RAX.

В x64 исчезли аналоги pusha, pushad, popa, popad. В качестве замены введем свои макросы pushall, popall, работающие аналогично. Поместим эти макросы в секцию неинициализированных данных - bss.

В свою очередь, буферы уходят в секцию данных - data.

В итоге описанная выше функция принимает вид:

.section .data# буфер чтения - в секции данных ReadCharBuffer:    .byte 0x3c.section .text# код - в секции кодаReadCharEx:    PUSHALL# макрос - в секции bss    XORQ    %RAX, %RAX              # syscall #0: read(int fd, void *buf, size_t count)    XORQ    %RDI, %RDI              # fd        : 0 == stdin    MOVQ    $ReadCharBuffer, %RSI   # buf       : ReadCharBuffer    MOVQ    $1, %RDX                # count     : 1 byte    SYSCALL    CMPQ    $0, %RAX    SETZ    %BL                         ORB     %BL, (IsEOF)    POPALL    RET

Следующее, что делал Бенджамин после заполнения таблицы указателей на функции - резервировал стек. В нашем случае для резервирования можно было бы пройти с некоторым шагом по стеку, записывая какие-нибудь значения, пока не встретится Guard Page.

Однако, выяснилось, что Linux для каждого запущенного процесса запоминает список регионов виртуальной памяти и, в случае ошибки обращения, проверяет, не произошел ли Segmentation fault. Если не произошел, значит было обращение к неинициализированной странице, а значит необходимо лишь выделить еще одну страницу виртуальной памяти и добавить к региону. Получатся, резервировать память заранее не требуется. В вот столкнуться с Guard Page в принципе непростая задача. Значит, необходимость в подготовке стека в новой библиотеке отпала, что для нас, конечно же, плюс.

Осталось скомпилировать и слинковать библиотеку:

$ gcc -c rtl64.s$ ld rtl64.o -g --output rtl64

Полученный ELF сериализуем в паскаль-строки и помещаем в BTPC вместо прежнего шаблона. На этом библиотеку можно считать портированной.

Кодогенерация

Как мы уже видели, BTPC в процессе компиляции переводит байт-код в ассемблерные инструкции и конкатенирует их с шаблоном процедурами EmitByte:

procedure OCPopESI;begin  EmitByte($5e);  LastOutputCodeValue := locPopESI;end;procedure OCMovzxEAXAL;begin  EmitByte($0f);   EmitByte($b6);   EmitByte($c0);  LastOutputCodeValue := locMovzxEAXAL;end;

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

Переведем вручную инструкцию MOV R10, [R12 + R13], (напомню, квадратные скобки обозначают взятие значения по адресу) воспользовавшись материалами методички "Intel 64 and IA-32 Architectures Developers Manual"

1. Переводим номера операндов в двоичный вид. Регистр-приемник R10 подходит под формат "R?".

2. Находим инструкцию MOV в таблице кодов инструкций i8086+. Нужен формат "r/m R?". Итого, получаем 0x8B.

3. Операнд R10 в двоичном представлении имеет длину 4 бита, а значит не входит в отведенные 3 бита Rn байта ModR/M.

4. Для представления подобных "больших" регистров понадобится байт "Префикс REX".

5. Старший бит R10 уходит в бит R префикса REX и расширяет Rn в байте ModR/M.

6. Согласно таблице ModR/M для 32-разрядных инструкций, биты R/M байта ModR/M = 100, а биты Mod = 00. Это дает дополнительный байт SIB.

7. Старший бит регистра R12, равный 1, взводит бит X в префиксе REX и расширяет номер индекса в SIB.

8. Байт SIB выглядит, как [#Base + #Index2^(Scale)]. Базу Base образует регистр R12. 3 младших его бита = 100 и устанавливаются на место 3х битов Base в SIB.

9. Индекс(Index) в SIB составляют 3 младших бита регистра R13 = 101.

10. Так как в инструкции лишь сложение (1 регистр + 1 регистр), биты Scale в байте SIB = 00 и дают 2^(Scale) = 2^0 = 1.

11. Старший бит регистра R13 уходит в бит B префикса REX. Это расширяет набор базового регистра в байте SIB.

12. Конкатенируем байт префикса REX: "0100" + "W:1" + "R:1" + "X:1" + "B:1" = 01001111, что в hex записи дает 0x4F. Префикс REX найден.

13. Конкатенируем байт ModR/M: "Mod:00" + "Rn:010" + "R/M:100" = 00010100, что дает байт 0x14.

14. Конкатенируем наконец байт SIB: "Scale:00" + "Index:101" + "Base:100" = 00101100, что дает байт 0x2C.

Путем конкатенации полученных байтов имеем инструкцию MOV R10, (R12 + R13) в виде 0x4F 0x8B 0x14 0x2C .

Мы уже видели, как происходит хирургическая операция над PE-файлом и делать еще одну операцию, взводя и обнуляя биты, совсем не хочется. Тем более, что таких инструкций в BTPC около 70 штук.

Мы же сразу перейдем к упрощенному способу: надо лишь приготовить все нужные нам инструкции, скомпилировать, а затем дизассемблировать полученный файл и достать нужные нам байты.

Осталось заменить в коде выше значения байтов и на этом этап кодогенерации можно считать завершенным.

Хирургическая операция над ELF'ом

Очевидно, код, который BTPC генерирует сейчас - невидим для исполняемого файла, ведь он дописывается даже не в конец, а "после" файла, то есть, грубо говоря, лежит рядом. При этом генерируемый код конситентен с уже существующим.

Для нас это означает то, что настал шаг, которого мы ждали и боялись - микрохирургия ELF'а - будем пришивать хвост живому эльфу код рабочему ELF'у.

Но для начала оценим, насколько все плохо. Опасение вызывают 2 факта:

• ELF64 отличается от PE32

• PE32 был собран вручную, с некоторыми хаками

Воспользуемся readelf'ом и прочтем собранный ранее rtl64:

$ readelf --section-headers rtl64Section Headers:  [Nr] Name              Type             Address           Offset       Size              EntSize          Flags  Link  Info  Align  [ 0]                   NULL             0000000000000000  00000000       0000000000000000  0000000000000000           0     0     0  [ 1] .text             PROGBITS         00000000004000b0  000000b0       0000000000000317  0000000000000000  AX       0     0     1  [ 2] .data             PROGBITS         00000000006003c7  000003c7       00000000000000bf  0000000000000000  WA       0     0     1  [ 3] .symtab           SYMTAB           0000000000000000  00000488       0000000000000408  0000000000000018           4    39     8  [ 4] .strtab           STRTAB           0000000000000000  00000890       0000000000000248  0000000000000000           0     0     1  [ 5] .shstrtab         STRTAB           0000000000000000  00000ad8       0000000000000027  0000000000000000           0     0     1

Чуда не случилось - в нашем ELF'е аж 6 секций!:

• нулевая пустая секция (согласно стандарту)

• секция кода text

• секция данных data

• секция имен секций shstrtab (Section header string table)

• таблица символов в symtab

• метки из ассемблерного ассемблерного кода в strtab

Чем ближе секция кода к концу файла, тем лучше для нас. Нам не повезло от слова совсем - секция кода плотно зажата данными и метаданными. Если мы сейчас найдем метку ProgramEntryPoint и пойдем записывать код после нее, мы с большой вероятностью "потеряем пациента".

Откуда столько секций? Мы ведь компилировали лишь код и данные. Получается, они подтянулись на стадии линковки и наш файл стал весить почти 4 Кб, а там ведь всего пара сотен строк кода, не считая внутренностей самого ELF'а.

Попросим ld не включать ничего лишнего (--nostdlib, --strip-all):

$ ld rtl64.o -g --output rtl64-min -nostdlib --strip-all

ELF сжался в 2 раза - теперь весит всего 1.4 Кб. Взглянем еще раз на секции:

$ readelf --section-headers rtl64-minSection Headers:  [Nr] Name              Type             Address           Offset       Size              EntSize          Flags  Link  Info  Align  [ 0]                   NULL             0000000000000000  00000000       0000000000000000  0000000000000000           0     0     0  [ 1] .text             PROGBITS         00000000004000b0  000000b0       0000000000000317  0000000000000000  AX       0     0     1  [ 2] .data             PROGBITS         00000000006003c7  000003c7       00000000000000bf  0000000000000000  WA       0     0     1  [ 3] .shstrtab         STRTAB           0000000000000000  00000486       0000000000000017  0000000000000000           0     0     1

Минус 2 секции. Уже лучше, хотя shstrtab все еще на месте. Вспоминаем, что в комплекте binutils есть утилита strip, которая умеет редактировать исполняемые файлы. Пробуем вырезать shstrtab из нашего файла и снова прочесть оставшиеся секции:

$ strip -R shstrtab rtl64-min$ readelf --section-headers rtl64-minSection Headers:  [Nr] Name              Type             Address           Offset       Size              EntSize          Flags  Link  Info  Align  [ 0]                   NULL             0000000000000000  00000000       0000000000000000  0000000000000000           0     0     0  [ 1] .text             PROGBITS         00000000004000b0  000000b0       0000000000000317  0000000000000000  AX       0     0     1  [ 2] .data             PROGBITS         00000000006003c7  000003c7       00000000000000bf  0000000000000000  WA       0     0     1  [ 3] .shstrtab         STRTAB           0000000000000000  00000486       0000000000000017  0000000000000000           0     0     1

Shstrtab и ныне там. Посмотрим, что же внутри:

$ hexdump -C rtl64-min00000480  40 00 00 00 00 00 00 2e  73 68 73 74 72 74 61 62  |@.......shstrtab|00000490  00 2e 74 65 78 74 00 2e  64 61 74 61 00 00 00 00  |..text..data....|000004a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

В секции с именами секций лежат имена секций! Хотя бы здесь все предсказуемо. Оказывается, что секция .shstrtab всегда генерируется при линковке. Хотя, согласно спецификации, для исполнения она не нужна - то есть, теоретически избавиться от нее возможно.

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

Концептуально, минималистичный скрипт линкера выглядел бы для нас следующим образом:

ENTRY(_start)                           /* точка входа */SECTIONS{    . = 0x4000b0;                       /* адрес размещения секции данных */    .data : { *(.data) }    .bss :  { *(.bss)  *(COMMON) }    . = 0x6000d3;                       /* адрес размещения секции кода */    .text : { *(.text) }                /* секция кода идет последней в файле */}

В реальности скрипт ld занимает две сотни строк - приводить его здесь не имеет смысла. Интересующиеся, однако, могут воспользоваться командой ld --verbose - выглядит этот скрипт довольно пугающе, но найти блок, отвечающий за размещение секции кода все же можно. Перемещаем этот блок в самый конец.

Теперь у нас имеется специальный скрипт линковки. Воспользуемся им и вновь прочтем секции:

$ ld rtl64.o -g --output rtl64-custom-ld -T linkerScript.ld -nostdlib --strip-all$ readelf --section-headers rtl64-custom-ldSection Headers:  [Nr] Name              Type             Address           Offset       Size              EntSize          Flags  Link  Info  Align  [ 0]                   NULL             0000000000000000  00000000       0000000000000000  0000000000000000           0     0     0  [ 1] .data             PROGBITS         00000000006000b0  000000b0       00000000000000bf  0000000000000000  WA       0     0     1  [ 2] .text             PROGBITS         0000000000a00170  00000170       0000000000000317  0000000000000000  AX       0     0     1  [ 3] .shstrtab         STRTAB           0000000000000000  00000487       0000000000000017  0000000000000000           0     0     1

Бинго, скрипт сработал! Секция text, действительно, поменялась местами с секцией data.

Однако, кажется, мы выстрелили себе в ногу. До этого мы могли отлаживать процесс старым добрым gdb, но сейчас из-за того, что мы вырезали и таблицы символов, и метки в коде, и всю отладочную информацию, отлаживать стало просто невозможно.

Хотя ранее по соседству содержались и код и данные, так что некоторые команды из-за этого неверно отображались в gdb и запутаться было крайне легко. Как с этим всем справился Бенджамин, история умалчивает

Мы же, поняв, что погорячились, возвращаем секции symtab и strtab на место, убрав опции линкера. И вот, у нашей реализации появилось преимущество над оригиналом - несравнимо более удобный для отладки код - в нем только актуальные команды (все отображается корректно, т.к. не перемешано с данными) и в нем есть отладочные символы

Тем не менее, код все еще зажат в глубине файла. Кажется, пришло время волевым решением разрезать файл напополам, вставить в середину код и склеить обратно. Мой аналогичный вопрос на stackoverflow был, мягко скажем, воспринят неоднозначно. Но мы будем проделывать этот процесс при каждой компиляции:

Тогда, чтобы добиться работспособности файла, необходимо отредактировать поля следующих структур:

Приведенные выше значения надо увеличить на размер сгенерированного кода: sizeof(injection). Значения учитывают порядок размещения секций в файле.

Внимательный читатель заметит, что после того, как мы научились редактировать ELF'ы, можно не утруждаться перемещением секций - ведь теперь, где бы ни хранился код, мы сможем до него добраться, не сломав все вокруг.

И, поскольку теперь мы знаем, где "резать", где "пришивать" и куда "колоть", реализовать эти функции в компиляторе не составит труда.

На этом процесс разработки можно считать завершенным. Теперь, у нас генерируется ELF, мы проводим над ним операцию, которая на проверку оказалась не такой и страшной. Осталось лишь итеративно отладить результаты компиляции - начать с самых простых однострочных программ и постепенно их усложнять. В качестве образца берем исходный компилятор и ожидаем, что для одной и той же программы наш новый компилятор выдаст нам файл с идентичными инструкциями с точностью до разрядности и деталей портирования RTL.

Через несколько итераций получаем работоспособный компилятор.

# Получаем кросскомпилятор$ btpc.exe < btpc64.pas > btpcCrossWin.exe# Еще шаг и получаем его Linuxверсию$ btpcCrossWin.exe < btpc64.pas > btpc64Linux# Еще один, контрольный шаг, уже на Linux$ btpc64Linux < btpc64.pas > btpc64Check

И в конце концов получаем самоприменимый компилятор подмножества Pascal, работающий под Linux x64, как и было запланировано.

Заключение

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

• разобрались с архитектурой компилятора BTPC

• Выяснили, как устроен процесс от исходного кода на Pascal до исполняемого файла Windows

• Пересобрали библиотеку времени выполнения (RTL)

• Собрали из RTL файл ELF и разобрались в его внутреннем устройстве и научились динамически его редактировать

• Исправили процесс кодогенерации

• Собрали полученное в рабочий компилятор

Результаты работы доступны в репозитории на github.

Если Вы дочитали до этого момента, то, надеюсь, не жалеете о потраченном времени. Надесюь, что Вы открыли для себя что-то новое. Но, даже если Вас ничего не удивило, возможно вы освежили знания

P.S.

Наверняка, многие уже догадались, что задача походит на учебный проект. Это, действительно, курсовая работа по компиляторам на кафедре ИУ9 в МГТУ им. Баумана, которую я выполнил несколько лет назад. Предстоящий объем работы казался тогда невыполнимым. И чем больше работы было проделано, тем, казалось, больше работы предстоит впереди. Но процесс и достигнутый результат оказались более занимательным, чем шаги в неизвестность (и возгласы "а так можно было?") на каждом этапе работы. И вот, спустя несколько лет, у меня дошли руки написать краткую статью о проделанной тогда работе, попытавшись сохранить интересные и важные "открытия", сделанные в ходе нее, и опустив лишние технические детали ("невошедшее" можно найти в отчете в репозитории выше).

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

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

Ссылки

• Спецификация ELF

• Исходный компилятор BTPC

• Портированная версия BTPC64

В моей предыдущей статье о rust я попытался рассказать об истории языка, и показать откуда он пришёл. В статье было сделано множество упрощений. Просто нереальное множество. Народу не понравилось. Но в опросе, в конце статьи вы сказали, что надо бы показать кишки компилятора. Ну что же, под катом вы найдёте разбор исходных кодов компилятора rust. Мы проследим путь программы, начиная из исходного файла, прямиком к бинарнику.

Словарь

Далее по тексту я буду разбрасываться следующими терминами без удержи. Если вы знаете что это всё значит - хорошо. Если нет, убедитесь что подтянули свои знания, перед тем как заныривать.

1. LLVM - система компиляции которая состоит из компилятора и набора инструментов, позволяющая создавать фронт-энд для любого языка и компилировать его на множество различных платформ.

2. AST - (abstract syntax tree) древовидная репрезентация семантической структуры исходного кода. Каждый узел обычно показывает конструкцию, встречающуюся в коде.

3. IR (intermediate representation) - Структура данных, обычно используемая в кишках компилятора или виртуальной машины, для представления исходного кода программы. Такую структуру обычно оптимизируют и перегоняют в конечный код.

4. HIR (High Level IR) - IR высокого уровня. Это основная репрезентация кода, используемая в rust. Фактически это представление AST, которым компилятору удобно пользоваться.

5. MIR (Mid Level IR) - Это репрезентация HIR, которая намного ближе к LLVMIR.

6. LLVMIR (Language Independent IR) - фактически это высокоуровневый ассемблер, который не привязан к определённому языку или системе. Такой код удобно оптимизировать и после он передаётся компилятору.

7. Крейт, crate - Это то, что будет скомпилировано либо в библиотеку или бинарник. На выходе будет одна библиотека или бинарник, вне зависимости от того, сколько файлов входят в крейт.

8. ICE (Internal compiler error), ошибка компилятора.

Дальнейший текст подразумевает, что вы умеете программировать. Можно и не на rust.

Начало

Поехали. Мы будем лезть нашими ручками в сам компилятор и смотреть на его исходники. Для начала нам понадобятся кое-какие инструменты. Ставим чистую виртуальную машину с Windows 10. Идём в интернеты и льём следующее:

1. Сорцы компилятора. Достаются с github. Можно лить просто zip, ибо обратно коммитить мы ничего не будем.

2. VSCode.

3. Установщик компилятора. Любая свежая стабильная версия подойдёт.

4. Не будем мучиться, давайте, заодно, установим nightly компилятор.
   rustup toolchain install nightly --allow-downgrade --profile minimal --component clippy rustup default nightly

5. Guide to Rustc Development. Инструкция по разработке компилятора. 460 страниц. Не хило. Сохраняем pdf.

Проверяем:

C:\>rustc -Vrustc 1.49.0 (e1884a8e3 2020-12-29)

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

cd \mkdir workcd workmkdir rustcd rustcargo new hello-world

Ок, это было просто. Но мы не будем использовать cargo для самой компиляции. Используем компилятор напрямую. Но я же на надо cargo издеваюсь, так ведь?

cd hello-worldcd srcrustc main.rs

И Бух.

Чего? Так, сам по себе компилятор всё собрал, но ругается на отсутствие линкера. От жеж, зараза. То есть, линкер ему нужен внешний. Ругаемся на компилятор, встаём с удобного кресла и идём обратно, подключаться к проводному интернету, потому что палить 5 гигов установщика Visual Studio Build Tools не хочется на хотспоте.

Билдим всё ещё раз и смотрим.

Ах, ты, ржавая банка! Какого чёрта?? Я уже как две недели рассказываю всем обитателям Хабра о том, какой ты прекрасный компилятор, и как хорошо ты собираешь минимальные бинарники, а ты??? 150 килобайт исполняемого кода из-за одной только линии текста на экране?

Пытаемся скомпилировать с -C opt-level=3 и получаем то же самое. Что случилось с бинарником? Сейчас на этот вопрос отвечать не будем. Мотаем на Ус и едем дальше.

Копирайт - сдесь же.

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

Ладно, что мы знаем? Компилятор не работает без внешнего линкера и исходник для вывода одной строки текста раздувается до 150 килобайт. Ну, по крайней мере мы это можем скомпилировать. Давайте пока распакуем исходники компилятора и начнём рыться. (Собирать компилятор я не собираюсь. Если вам очень хочется - это можно сделать, но процесс это долгий и утомительный.)

Шаг первый: rustc

Открываем сорцы и наслаждаемся. Всё выглядит очень прилично и чисто. Тут, понятное дело, можно учиться тому как правильно разделять свой проект на куски и как правильно управлять кодом на rust. Собственно говоря, сразу понятно куда идти. Забираемся в compiler/rustc/src/main.rs и смотрим.

Хм. То есть точка входа в программу просто тянет jemalloc вызовы и запускает ещё две функции. Ну вот, всё. Теперь понятно как работает компилятор rust. Делов-то! Кстати, jemalloc это специальный менеджер памяти, изначально разработанный для FreeBSD в 2005 году. Основной упор был сделан на то, чтобы избежать фрагментации памяти при работе с этим аллокатором. В оригинальной версии он просто заменяет malloc. В 2007 году Firefox начал использовать этот менеджер для снижения расхода памяти, а ещё через пару лет он попал в Facebook.

Шаг второй: rustc-driver

Ладно, всё выглядит слишком уж просто. Погружаемся дальше. rustc тянет за собой rustc-driver. Ныряем туда.

Тут мы найдём небольшой readme, который расскажет нам о том, что компилятора в самом драйвере мы не найдём. Эта программа собирает конфигурацию из аргументов и запускает сам процесс компиляции из других крейтов. После изучения исходников находим функцию для запуска процесса компиляции.

    interface::run_compiler(config, |compiler| {        let sess = compiler.session();        let should_stop = RustcDefaultCalls::print_crate_info(            &***compiler.codegen_backend(),            sess,            Some(compiler.input()),            compiler.output_dir(),            compiler.output_file(),        )        .and_then(|| {            RustcDefaultCalls::list_metadata(                sess,                &*compiler.codegen_backend().metadata_loader(),                &matches,                compiler.input(),            )        })        .and_then(|| RustcDefaultCalls::try_process_rlink(sess, compiler));

Да, в этом крейте файлов не так-то много, но что бы тут не творилось, на самом деле всё сводится к вызову методов в крейте под названием interface. Вышеприведённый код это и показывает. interface::run_compiler и поехали.

Что же произошло в rustc-driver? Мы собрали все конфиги. Подгрузили все файлы и нашли их местоположение в файловой системе. Создали замыкание, которое следит за процессом компиляции и запускает линкер после успешной компиляции. Запустили линтеры (если такие имелись) и приготовили сам компилятор к запуску. Давайте запускать.

Шак третий: rustc-interface

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

Так, осматриваемся и находим

pub fn run_compiler<r: send="">(mut config: Config, f: impl FnOnce(&Compiler) -> R + Send) -> R {    tracing::trace!("run_compiler");    let stderr = config.stderr.take();    util::setup_callbacks_and_run_in_thread_pool_with_globals(        config.opts.edition,        config.opts.debugging_opts.threads,        &stderr,        || create_compiler_and_run(config, f),    )}

Кстати тут же, недалеко, мы можем найти настройку механизма кодогенерации.

pub fn get_builtin_codegen_backend(backend_name: &amp;str) -> fn() -> Box<dyn codegenbackend=""> {    match backend_name {        #[cfg(feature = "llvm")]        "llvm" => rustc_codegen_llvm::LlvmCodegenBackend::new,        _ => get_codegen_sysroot(backend_name),    }}

Быстренько посмотрим на наши сорцы и увидим что у нас прямо в сорцах есть 3 различных модуля кодогенерации. Что они делают? Превращают MIR в конечный код для системы компиляции. Открываем rustc-codegen-llvm и смотрим в README:

The `codegen` crate contains the code to convert from MIR into LLVM IR,and then from LLVM IR into machine code. In general it contains codethat runs towards the end of the compilation process.

Ок, ну тут всё понятно, мы берём MIR и переделываем его в LLVM IR. После этого LLVM может скомпилировать код в конечный бинарник. Но погодите, помимо LLVM бекенда у нас есть ещё два других! Смотрим туда. rustc-codegen-ssa согласно документации, позволяет генерировать низкоуровневый код, который не будет привязан к определённому бекэнду (например, LLVM) и позволит в дальнейшем использовать другие системы компиляции.

Собственно говоря, прямо там же вы найдёте rustc-codegen-cranelift. То есть MIR в будущем может компилироваться через cranelift, который в идеале ускорит процесс компиляции. Ну это в будущем, пока что проект в процессе тестирования и работает не лучше, чем Газель без мотора.

Открываем модуль и смотрим, что происходит внутри:

fn configure_and_expand_inner<'a>(    sess: 'a Session,    lint_store: 'a LintStore,    mut krate: ast::Crate,    crate_name: &str,    resolver_arenas: &'a ResolverArenas<'a>,    metadata_loader: &'a MetadataLoaderDyn,) -> Result<(ast::Crate, Resolver<'a>)> {//[snip]

Ага, вот тут мы берём быка за рога и начинаем разбирать исходный код на части. Далее, создаём и проверяем AST

let has_proc_macro_decls = sess.time("AST_validation", || {rustc_ast_passes::ast_validation::check_crate(sess, &krate, &mut resolver.lint_buffer())});

И вот тут у нас начинается полное мясо. Прикол вот в чём, обычно компиляторы делают достаточно простую вещь - берёшь сорцы, проходишься по ним несколько раз, парсишь синтаксис, находишь ошибки, разбираешь на куски макросы, всё хорошо. rust в стародавние времена начинал именно так же. Но, со временем, была предложена новая модель компиляции. Запросы. Вместо того чтобы делать всю работу несколько раз подряд, давайте просто превратим проходы в запросы. Результат запроса можно сохранить в кеш. Если пользователь (программист) не менял ничего в определённом файле, то и компилировать его не надо. Если мы видим что делать это не надо, мы просто возвращаем данные из кеша запроса.

Даже если вы и поменяли что-то в каком-либо файле, то благодаря системе запросов вы сможете избежать ненужной перекомпиляции. Что если вы изменили только одну линию в комментариях к файлу? Пересобирать такой не придётся.

Давайте посмотрим на запросы, которые создаёт компилятор:

pub struct Queries<'tcx> {    compiler: &'tcx Compiler,    gcx: OnceCell<globalctxt<'tcx>>,    arena: WorkerLocal<arena<'tcx>>,    hir_arena: WorkerLocal<rustc_ast_lowering::arena<'tcx>>,    dep_graph_future: Query<option<depgraphfuture>>,    parse: Query<ast::crate>,    crate_name: Query<string>,    register_plugins: Query<(ast::Crate, Lrc<lintstore>)>,    expansion: Query<(ast::Crate, Steal<rc<refcell<boxedresolver>>>, Lrc<lintstore>)>,    dep_graph: Query<depgraph>,    lower_to_hir: Query<(&'tcx Crate<'tcx>, Steal<resolveroutputs>)>,    prepare_outputs: Query<outputfilenames>,    global_ctxt: Query<querycontext<'tcx>>,    ongoing_codegen: Query<box<dyn any="">>,}

Парсинг, создание крейта, сбор HIR - всё это делается через запросы. Один момент про который полезно знать, это то что ещё не всё переписано на запросах.

В итоге у нас на выходе получается большая и толстая структура:

    pub fn global_ctxt(&'tcx self) -> Result<&Query<querycontext<'tcx>>> {        self.global_ctxt.compute(|| {            let crate_name = self.crate_name()?.peek().clone();            let outputs = self.prepare_outputs()?.peek().clone();            let lint_store = self.expansion()?.peek().2.clone();            let hir = self.lower_to_hir()?.peek();            let dep_graph = self.dep_graph()?.peek().clone();            let (ref krate, ref resolver_outputs) = &*hir;            let _timer = self.session().timer("create_global_ctxt");            Ok(passes::create_global_ctxt(                self.compiler,                lint_store,                krate,                dep_graph,                resolver_outputs.steal(),                outputs,                &crate_name,                &self.gcx,                &self.arena,            ))        })    }

И как раз её можно дёргать для выполнения необходимых запросов.

Шаг четвёртый: rustc-parse и rustc-lexer

Далее по тексту вы найдёте простую логику всех этих запросов. "Простая" логика заключается в вызове крейтов, которые её обрабатывают. Например, rustc-parse. Это крейт, который использует rustc-lexer. Лексер читает строки из файлов и преобразовывает их в очень простые токены. Токены передаются парсеру, который превращает их в Span и продолжает работу с кодом. Основной момент этого Span заключается в том, что к каждому элементу в дереве кода будет добавлена информация о том, в каком конкретно месте этот элемент записан в исходном файле. Когда компилятор будет сообщать об ошибке, вы увидите, где именно эта ошибка произошла.

Основная часть парсера запускается через вызов parse_crate_mod в rustc_parse\src\parser\item.rs. А дальше по тексту вы найдёте невероятное количество проверок синтаксиса, который этот парсер делает. Вот, например:

    /// Error in-case a `default` was parsed but no item followed.    fn error_on_unmatched_defaultness(&self, def: Defaultness) {        if let Defaultness::Default(sp) = def {            self.struct_span_err(sp, "`default` is not followed by an item")                .span_label(sp, "the `default` qualifier")                .note("only `fn`, `const`, `type`, or `impl` items may be prefixed by `default`")                .emit();        }    }

Шаг пятый: rustc-expand

В результате работы парсера мы получаем наш самый великий и могучий AST.

Всё это создаётся огромным макросом astfragments! в \compiler\rustcexpand\src\expand.rs

AST используется для дальнейшей генерации кода и приведения его в нужный вид. Про это можно писать отдельную книгу. Но мы пока удовольствуемся там, что AST можно разобрать до HIR.

Шаг шестой: rustc-middle

Куда ты завёл нас? Не видно ни зги! Простите, ребята, не варят мозги. Вернее, мозг начинает вариться. Сложность процесса увеличивается настолько, что просто читая коды дальше ходить страшно. Ладно, обратимся к инструкции для разработчиков - смотрим. Видим что после того как у нас появился AST мы можем заняться приведением его в приличный вид. Вернее, в HIR.

Этим как раз и занимается rustc-middle. Вернее, не только этим. Залезаем в исходники и видим что тут у нас есть HIR, MIR и Types.

//! - **HIR.** The "high-level (H) intermediate representation (IR)" is//!   defined in the `hir` module.//! - **MIR.** The "mid-level (M) intermediate representation (IR)" is//!   defined in the `mir` module. This module contains only the//!   *definition* of the MIR; the passes that transform and operate//!   on MIR are found in `rustc_mir` crate.//! - **Types.** The internal representation of types used in rustc is//!   defined in the `ty` module. This includes the **type context**//!   (or `tcx`), which is the central context during most of//!   compilation, containing the interners and other things.

Что же происходит в реальности? Ну, для начала мы начинаем обработку AST. Этим, кстати занимается ещё один модуль, rust_ast_lowering. Смотрим туда и находим достаточно длинный файл, в котором и происходит преобразование каждого элемента AST в HIR.

pub(super) fn lower_expr_mut(;mut self, e: &Expr) -> hir::Expr<'hir> {        ensure_sufficient_stack(|| {            let kind = match e.kind {                ExprKind::Box(ref inner) => hir::ExprKind::Box(self.lower_expr(inner)),                ExprKind::Array(ref exprs) => hir::ExprKind::Array(self.lower_exprs(exprs)),                ExprKind::ConstBlock(ref anon_const) => {                    let anon_const = self.lower_anon_const(anon_const);                    hir::ExprKind::ConstBlock(anon_const)                }                ExprKind::Repeat(ref expr, ref count) => {                    let expr = self.lower_expr(expr);                    let count = self.lower_anon_const(count);                    hir::ExprKind::Repeat(expr, count)                }                ExprKind::Tup(ref elts) => hir::ExprKind::Tup(self.lower_exprs(elts)),                ExprKind::Call(ref f, ref args) => {                    let f = self.lower_expr(f);                    hir::ExprKind::Call(f, self.lower_exprs(args))                }///[snip]

Здесь весь синтаксический сахар растворяется в чае и перестаёт быть сахаром. Так моя любимая for node in data превращается в

/// Desugar `ExprForLoop` from: `[opt_ident]: for <pat> in  ` into:/// /// {///     let result = match ::std::iter::IntoIterator::into_iter() {///         mut iter => {///             [opt_ident]: loop {///                 let mut __next;///                 match ::std::iter::Iterator::next(&mut iter) {///                     ::std::option::Option::Some(val) => __next = val,///                     ::std::option::Option::None => break///                 };///                 let <pat> = __next;///                 StmtKind::Expr();///             }///         }///     };///     result/// }

А вот здесь, как раз, всеми любимый оператор ? первращается в Try::into_result:

/// Desugar `ExprKind::Try` from: `<expr>?` into:/// match Try::into_result(<expr>) {///     Ok(val) => #[allow(unreachable_code)] val,///     Err(err) => #[allow(unreachable_code)]///                 // If there is an enclosing `try {...}`:///                 break 'catch_target Try::from_error(From::from(err)),///                 // Otherwise:///                 return Try::from_error(From::from(err)),/// }

С HIR теперь можно работать

Шаг седьмой: rustc_ty

И .\rust-master\compiler\rustc_middle\src\ty\mod.rs. Одна из самых больших частей компилятора занимается проверками системы типов после того, как у нас есть HIR. Какой тип будет у let mut a = 5;? Вот на этот вопрос и ответит наша система работы с типами. Две основных структуры здесь:

//! - [`rustc_middle::ty::Ty`], used to represent the semantics of a type.//! - [`rustc_middle::ty::TyCtxt`], the central data structure in the compiler.

Последняя тянется через весь процесс компиляции.

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

Кстати, смотрим в rust-master\compiler\rustc_typeck\src\check\expr.rs

if let Some(ref e) = expr_opt {                self.check_expr_with_hint(e, err);                // ... except when we try to 'break rust;'.                // ICE this expression in particular (see #43162).                if let ExprKind::Path(QPath::Resolved(_, ref path)) = e.kind {                    if path.segments.len() == 1 && path.segments[0].ident.name == sym::rust {                        fatally_break_rust(self.tcx.sess);                    }                }            }

Хмм.. Если мы натыкаемся на брейк, после которого есть только один лейбл - rust то нужно запустить функцию fatally_break_rust.

Проверяем.

break rust;

Компилируем и запускаем:

error: internal compiler error: It looks like you're trying to break rust; would you like some ICE?note: the compiler expectedly panicked. this is a feature.note: we would appreciate a joke overview: https://github.com/rust-lang/rust/issues/43162#issuecomment-320764675note: rustc 1.51.0-nightly (b12290861 2021-01-29) running on x86_64-pc-windows-msvc

Пасхалки они выглядят именно вот так.

Так, вычислили типы и теперь можем проверить что никто не пытается запихнуть строку в Int. Хорошо. Можно идти дальше.

Шаг восьмой: rustc_mir и rustc_mir_build

Теперь наш HIR можно преобразовать в MIR. Берём ранее созданный TyCtxt и начинаем преобразовывать его в

/// Construct the MIR for a given `DefId`.fn mir_build(tcx: TyCtxt<'_>, def: ty::WithOptConstParam<localdefid>) -> Body<'_> {    let id = tcx.hir().local_def_id_to_hir_id(def.did);    // Figure out what primary body this item has.    let (body_id, return_ty_span, span_with_body) = match tcx.hir().get(id) {        Node::Expr(hir::Expr { kind: hir::ExprKind::Closure(_, decl, body_id, _, _), .. }) => {            (*body_id, decl.output.span(), None)        }        Node::Item(hir::Item {            kind: hir::ItemKind::Fn(hir::FnSig { decl, .. }, _, body_id),            span,            ..        })        | Node::ImplItem(hir::ImplItem {            kind: hir::ImplItemKind::Fn(hir::FnSig { decl, .. }, body_id),            span,            ..        })        | Node::TraitItem(hir::TraitItem {            kind: hir::TraitItemKind::Fn(hir::FnSig { decl, .. }, hir::TraitFn::Provided(body_id)),            span,            ..        }) => {            // Use the `Span` of the `Item/ImplItem/TraitItem` as the body span,            // since the def span of a function does not include the body            (*body_id, decl.output.span(), Some(*span))        }

И так далее по всем нодам. MIR это намного более генерализированная версия HIR. Она очень близка к тому что требует от нас LLVM для компиляции. В результате этой генерализации мы можем намного более эффективно работать над оптимизацией написанного вами кода и заниматься проверками заимствований и оптимизацией.

Шаг девятый: Проверка заимствования

Самая "страшная" функция rust это всем известный borrow cheker. Сам он живёт в

fn do_mir_borrowck<'a, 'tcx>(    infcx: &InferCtxt<'a, 'tcx>,    input_body: &Body<'tcx>,    input_promoted: &IndexVec<promoted, body<'tcx="">>,) -> BorrowCheckResult<'tcx> {    let def = input_body.source.with_opt_param().as_local().unwrap();    debug!("do_mir_borrowck(def = {:?})", def);    let tcx = infcx.tcx;    let param_env = tcx.param_env(def.did);    let id = tcx.hir().local_def_id_to_hir_id(def.did);    let mut local_names = IndexVec::from_elem(None, &input_body.local_decls);    for var_debug_info in &input_body.var_debug_info {        if let VarDebugInfoContents::Place(place) = var_debug_info.value {            if let Some(local) = place.as_local() {                if let Some(prev_name) = local_names[local] {                    if var_debug_info.name != prev_name {                        span_bug!(                            var_debug_info.source_info.span,                            "local {:?} has many names (`{}` vs `{}`)",                            local,                            prev_name,                            var_debug_info.name                        );                    }                }                local_names[local] = Some(var_debug_info.name);            }        }    }

В rust-master\compiler\rustc_mir\src\borrow_check\mod.rs. Да, сам модуль такой же огромный и страшный, как и borrow checker. А вот тут, например, можно найти всю логику проверки заимствования при перемещении переменных rust-master\compiler\rustc_mir\src\borrow_check\diagnostics\move_errors.rs

Шаг десятый: Оптимизации

Про систему оптимизаций в rust можно писать отдельную книгу. Всё аккуратно сложено в rust-master\compiler\rustc_mir\src\transform. LLVM сам по себе не сможет оптимизировать некоторые высокоуровневые примитивы, о которых знает только rust. И вот тут мы как раз и занимаемся оптимизацией этих примитивов.

Например:

//Вот такую конструкциюlet x: Option<()>;let y: Option<()>;match (x,y) {    (Some(_), Some(_)) => {0},    _ => {1}}//Можно привести к такой:let x: Option<()>;let y: Option<()>;let discriminant_x = //get discriminant of xlet discriminant_y = //get discriminant of yif discriminant_x != discriminant_y || discriminant_x == None {1} else {0}

Шак одиннадцатый: прощай, rust!

Полученный оптимизированный MIR можно теперь переделать в LLVM IR. Поехали. rustc-codegen-llvm создаёт LLVM-IR на базе MIR, который мы сгенерировали на предыдущем этапе. Здесь заканчивается rust и начинается llvm. Хотя, мы ещё не закончили с сорцами компилятора.

Тут можно найти пару интересных моментов, например rust-master\compiler\rustc_codegen_llvm\src\asm.rs содержит код для компилирования ассемблера напрямую из rust. Даже не замечал этого. Смотрим в документацию - есть такая поддержка в этом компиляторе!

Копаемся чуть глубже и находим rustc-target в котором видим различные дополнительные классы для работы с определённым ассемблером.

После того как кодогенерация завершена, мы можем передать IR в сам LLVM. rustc_llvm нам в помощь.

Вот, собственно говоря, и всё, ребята! LLVM за пределами нашей видимости. На моей операционной системе Visual Studio Build Tools берут на себя контроль и перегоняют LLVMIR в обычный бинарник.

TL;DR

Процесс компиляции в rust - это вам не мешки ворочать. Надо проверить неимоверное количество разных вещей. Вот что происходит с вашим кодом:

1. Он парсится из текста в AST.

2. AST обрабатывается и оптимизируется в HIR

3. HIR обрабатывается и оптимизируется в MIR.

4. MIR делает проверки заимствования и оптимизацию и перегоняется в LLVMIR.

5. LLVMIR компилируется на конечной платформе.

Пробуем ручками

Ну что же, напоследок осталось написать простенькую программку, типа этого:

fn main() {    let z = 10;    if z > 5 {        println!("Number Five is ALIVE!");    } else {        println!("Hmmm... No, number 5 is actually dead as a piece of wood.");    }    let mut input = String::new();    let stdin = std::io::stdin();    stdin.read_line(&mut input).ok().expect("You have failed me for the last time!");}

И начать её компилировать, только показывая все внутренности. Для начала есть замечательная опция компилятора, которая работает на любой версии:

--emit [asm|llvm-bc|llvm-ir|obj|metadata|link|dep-info|mir]       Comma separated list of types of output for the       compiler to emit

Значит, запуская компиляцию следующим образом:

rustc --emit asm,llvm-bc,llvm-ir,obj,metadata,link,dep-info,mir main.rs

Мы получаем на выходе мириады различных форматов, включая сгенерированный ассемблеровский код, байткод и IR для LLVM, и даже челвоеко-читаемый MIR.

А если у вас есть nightly компилятор, то вы можете запустить

rustc main.rs  -Z unpretty=hir-tree > hir.txt

И полюбоваться вашим HIR, в то время как

rustc main.rs  -Z ast-json=yes > ast.json

Даст вам возможность посмотреть на то, как выглядит AST.

Напоследок

Ну что же, мы залезли в дебри компилятора. Теперь вы знаете, что происходит каждый раз когда вы запускаете билд на своей машине. Я показал вам rust. Но не бойтесь, ваш любимый язык, скорее всего, ничуть не менее сложен. Проще будет только компилировать ассемблер для 386 под досом. И не важно, если вы запускаете C#, Java, Javascript, Golang или haskell. Происходить будет многое, хотя и совсем по-разному.

Понятно? Ну и хорошо.

Постскриптум

Ус размотался.

А почему бинарник такой-то большой? Ну, на этот вопрос можно ответить легко. Залезаем вашим любимым дебаггером в .pdb файл и смотрим на указатели функций, которые тянутся в наш бинарник. Их много. Подсистема работы со строками, макросами и памятью. Плюс система ввода-вывода. Что, считаете что 150 килобайт - слишком много?

C:\work\rust\hello-world\src>rustc -C opt-level=3 main.rsC:\work\rust\hello-world\src>upx --brute main.exe                       Ultimate Packer for eXecutables                          Copyright (C) 1996 - 2020UPX 3.96w       Markus Oberhumer, Laszlo Molnar & John Reiser   Jan 23rd 2020        File size         Ratio      Format      Name   --------------------   ------   -----------   -----------    154624 ->     65536   42.38%    win64/pe     main.exe                                                                                                                                                                                                                                                                                                                                                                                                           Packed 1 file.