GitHub

JIT Design and Implementation

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

Introduction

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

Overview

Схема потока компилятора

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

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

Optimization Pipeline

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

  1. Раннее упрощение

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

  2. Ранняя оптимизация

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

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

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

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

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

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

    1. Automatic vectorization является чрезвычайно мощной трансформацией для кода, требующего интенсивных вычислений на ЦП. Кратко говоря, векторизация позволяет выполнять single instruction on multiple data (SIMD), т.е. выполнять 8 операций сложения одновременно. Однако доказать, что код способен как на векторизацию, так и на получение выгоды от векторизации, сложно, и это сильно зависит от предыдущих этапов оптимизации, чтобы преобразовать IR в состояние, в котором векторизация оправдана.

  6. Внутреннее понижение

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

  7. Очистка

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

Target-Dependent Optimization and Code Generation

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

Linking

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

Execution

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

  1. invoke равно NULL, specsigflags равно 0b00, specptr равно NULL

    1. Это начальное состояние codeinst и указывает на то, что codeinst еще не был скомпилирован.

  2. invoke не равен нулю, specsigflags равен 0b00, specptr равен NULL

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

  3. invoke не равен null, specsigflags равно 0b10, specptr не равен null

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

  4. invoke не равен null, specsigflags равен 0b11, specptr не равен null

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

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

  1. При написании invoke, specsigflags и specptr:

    1. Выполните атомарную операцию сравнения и обмена для specptr, предполагая, что старое значение было NULL. Эта операция сравнения и обмена должна иметь как минимум порядок acquire-release, чтобы обеспечить гарантии порядка оставшихся операций с памятью в записи.
    2. Если specptr не равен нулю, прекратите операцию записи и дождитесь записи бита 0b10 в specsigflags.
    3. Запишите новый низкий бит specsigflags в его окончательное значение. Это может быть ослабленная запись.
    4. Запишите новый указатель invoke в его окончательное значение. Это должно иметь как минимум порядок памяти release для синхронизации с чтениями invoke.
    5. Установите второй бит specsigflags в 1. Это должно быть как минимум упорядочивание памяти для синхронизации с чтениями specsigflags. Этот шаг завершает операцию записи и сообщает всем другим потокам, что все поля были установлены.

  2. При чтении всех invoke, specsigflags и specptr:

    1. Прочитайте поле invoke с как минимум порядком памяти acquire. Эта загрузка будет называться initial_invoke.
    2. Если initial_invoke равно NULL, код не может быть выполнен. invoke равно NULL, specsigflags может рассматриваться как 0b00, specptr может рассматриваться как NULL.
    3. Прочитайте поле specptr с как минимум порядком памяти acquire.
    4. Если specptr равен NULL, то указатель initial_invoke не должен полагаться на specptr для гарантии корректного выполнения. Следовательно, invoke не равен NULL, specsigflags может рассматриваться как 0b00, specptr может рассматриваться как NULL.
    5. Если specptr не равен нулю, то initial_invoke может не быть конечным полем invoke, которое использует specptr. Это может произойти, если specptr был записан, но invoke еще не был записан. Поэтому необходимо ожидать второго бита specsigflags, пока он не будет установлен в 1 с как минимум порядком памяти acquire.
    6. Перечитайте поле invoke с как минимум порядком памяти acquire. Эта загрузка будет называться final_invoke.
    7. Прочитайте поле specsigflags с любым порядком памяти.
    8. invoke это final_invoke, specsigflags это значение, считанное на шаге 7, specptr это значение, считанное на шаге 3.

  3. При обновлении specptr на другой, но эквивалентный указатель функции:

    1. Выполните операцию release store нового указателя функции в specptr. Состояния гонки здесь должны быть безвредными, так как старый указатель функции должен оставаться действительным, и любые новые также должны быть действительными. Как только указатель записан в specptr, он всегда должен быть вызываемым, независимо от того, будет ли он позже перезаписан.

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

  • tdpThis is not a totally-target independent pipeline, as transformations such as vectorization rely upon target information such as vector register width and cost modeling. Additionally, codegen itself makes a few target-dependent assumptions, and the optimization pipeline will take advantage of that knowledge.