Документация Engee

Разработка и реализация JIT

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

Введение

JIT осуществляет управление ресурсами компиляции, поиск ранее скомпилированного кода и компиляцию нового кода. В основном он построен на технологии компиляции по запросу (ORCv2) в LLVM, которая реализует поддержку ряда полезных функций, таких как параллельная компиляция, отложенная компиляция и возможность компиляции кода в отдельном процессе. Хотя LLVM предоставляет базовый JIT-компилятор в виде LLJIT, для создания собственного JIT-компилятора в Julia напрямую используются многие API ORCv2.

Обзор

compiler diagram

При генерации кода создается модуль LLVM, содержащий IR для одной или нескольких функций Julia, из исходного IR SSA Julia, полученного в результате вывода типов (помечен как translate (преобразование) на диаграмме компилятора выше). Также производится сопоставление экземпляра кода с именем функции LLVM. Однако, несмотря на то, что компилятор на основе Julia применил некоторые оптимизации к IR Julia, представление IR LLVM, полученное при генерации кода, все еще содержит много возможностей для оптимизации. Таким образом, первым шагом JIT является запуск независимого от целевого объекта конвейера оптимизации[1] в модуле LLVM. Затем JIT запускает зависящий от цели конвейер оптимизации для оптимизации и генерации кода и выводит файл объекта. Наконец, JIT компонует полученный файл объекта в текущий процесс и делает код доступным для выполнения. Все эти действия контролируются кодом в файле src/jitlayers.cpp.

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

Конвейер оптимизации

Конвейер оптимизации основан на новом диспетчере проходов LLVM, но адаптирован под нужды Julia. Конвейер определен в src/pipeline.cpp и в целом проходит несколько этапов, которые подробно описаны ниже.

  1. Упрощение на ранних этапах

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

  3. Оптимизация на ранних этапах

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

  5. Оптимизация циклов

  6. Эти проходы канонизируют и упрощают циклы. Циклы часто являются «горячим» кодом, что делает оптимизацию циклов чрезвычайно важной для производительности. Ключевую роль здесь играют LoopRotate, LICM и LoopFullUnroll. В результате прохода IRCE также происходит устранение части проверки границ, которое подтверждает, что определенные границы никогда не превышаются.

  7. Скалярная оптимизация

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

  9. Векторизация

  10. Автоматическая векторизация — это чрезвычайно мощное преобразование для кода, требующего интенсивной загрузки ЦП. Если коротко, векторизация позволяет выполнять одну инструкцию с множеством данных (SIMD), например выполнять 8 операций сложения одновременно. Однако доказать, что код одновременно поддерживает векторизацию и выгоден для векторизации, довольно сложно, и это в значительной степени зависит от предварительных проходов оптимизации для перевода IR в состояние, в котором векторизация будет оправдана.

  11. Понижение внутренних функций

  12. Julia вставляет ряд пользовательских собственных внутренних функций для таких целей, как распределение объектов, сборка мусора и обработка исключений. Изначально эти внутренние функции были размещены для того, чтобы сделать возможности оптимизации более очевидными, но теперь они понижены в IR LLVM, чтобы IR можно было выдавать в виде машинного кода.

  13. Очистка

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

Зависящая от целевого объекта оптимизация и генерация кода

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

Компоновка

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

Выполнение

Код, скомпонованный в текущий процесс, становится доступным для выполнения. Генерирующий экземпляр кода узнает об этом в результате соответствующего обновления полей invoke, specsigflags и specptr. Экземпляры кода поддерживают обновление полей invoke, specsigflags и specptr при условии возможности вызова каждого их сочетания, существующего в любой момент времени. В этом случае JIT может обновлять эти поля, не аннулируя существующие экземпляры кода, поддерживая потенциально возможный в будущем параллельный JIT. В частности, могут быть действительны следующие состояния:

  1. invoke имеет значение NULL, specsigflags имеет значение 0b00, specptr имеет значение NULL

  2. Это начальное состояние экземпляра кода, которое указывает на то, что экземпляр кода еще не скомпилирован.

  3. invoke имеет ненулевое значение, specsigflags имеет значение 0b00, specptr имеет значение NULL

  4. Это указывает на то, что экземпляр кода не был скомпилирован с какой-либо специализацией и что его следует вызывать напрямую. Обратите внимание, что в данном случае invoke не считывает ни поле specsigflags, ни поле specptr, поэтому их можно изменить, не аннулируя указатель invoke.

  5. invoke имеет ненулевое значение, specsigflags имеет значение 0b10, specptr имеет ненулевое значение

  6. Это указывает на то, что экземпляр кода был скомпилирован, но специализированная сигнатура функции признана ненужной для генерации кода.

  7. invoke имеет ненулевое значение, specsigflags имеет значение 0b11, specptr имеет ненулевое значение

  8. Это указывает на то, что экземпляр кода был скомпилирован, и специализированная сигнатура функции признана необходимой для генерации кода. Поле specptr содержит указатель на специализированную сигнатуру функции. Указатель invoke может считывать оба поля specsigflags и specptr.

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

  1. При записи в поля invoke, specsigflags и specptr:

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

  3. Если specptr не равен нулю, прекратите операцию записи и дождитесь записи бита 0b10 specsigflags, затем при необходимости начните с шага 1.

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

  5. Запишите новый указатель для invoke в качестве его конечного значения. Для синхронизации с операциями чтения invoke у него должно быть, по крайней мере, упорядочение освобождения памяти.

  6. Задайте второму биту specsigflags значение 1. Для синхронизации с операциями чтения specsigflags требуется, по крайней мере, упорядочение освобождения памяти. Этот шаг завершает операцию записи и сообщает всем остальным потокам о том, что все поля были заданы.

  7. При чтении всех полей invoke, specsigflags и specptr:

  8. Считать поле specptr с любым порядком памяти.

  9. Прочитайте поле invoke с минимальным порядком запоминания acquire. Эта загрузка будет называться initial_invoke.

  10. Если initial_invoke равно NULL, код еще не готов к выполнению. invoke равно NULL, specsigflags может рассматриваться как 0b00, specptr может рассматриваться как NULL.

  11. Если specptr имеет значение NULL, то указатель initial_invoke не должен полагаться на specptr для правильного выполнения. Поэтому invoke имеет ненулевое значение, specsigflags может рассматриваться как имеющее значение 0b00, specptr может рассматриваться как имеющее значение NULL.

  12. Если specptr имеет ненулевое значение, то initial_invoke может не быть конечным полем invoke, использующим specptr. Это может произойти, если specptr уже записано, а invoke — еще нет. Поэтому перебирайте второй бит поля specsigflags до тех пор, пока не будет задано значение 1, по крайней мере, с упорядочением памяти захвата.

  13. Перечитайте поле invoke с любым порядком памяти. Эта загрузка будет называться final_invoke.

  14. Считайте поле specsigflags с любым упорядочением памяти.

  15. invoke является final_invoke, specsigflags — это значение, считанное на шаге 7, specptr — это значение, считанное на шаге 3.

  16. При обновлении specptr до другого, но аналогичного указателя функции:

  17. Выполните освобождение памяти нового указателя функции в specptr. Гонки здесь должны неопасны, так как старый указатель функции должен быть все еще допустимым, так же как и любой новый. Указатель, записанный в specptr, всегда должен быть доступен для вызова, независимо от того, будет ли он впоследствии перезаписан или нет.

Правильное считывание этих полей реализовано в jl_read_codeinst_invoke.

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

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