Working with LLVM

Это не замена документации LLVM, а сборник советов по работе с LLVM для Julia.

Overview of Julia to LLVM Interface

Julia динамически связывается с LLVM по умолчанию. Соберите с USE_LLVM_SHLIB=0, чтобы связать статически.

Код для преобразования AST Julia в LLVM IR или его прямой интерпретации находится в директории src/.

Некоторые из файлов .cpp образуют группу, которая компилируется в один объект.

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

Alias Analysis

Юлия в настоящее время использует LLVM's Type Based Alias Analysis. Чтобы найти комментарии, которые документируют отношения включения, ищите static MDNode* в src/codegen.cpp.

Опция -O включает Basic Alias Analysis LLVM.

Building Julia with a different version of LLVM

Версия LLVM по умолчанию указана в deps/llvm.version. Вы можете переопределить её, создав файл с именем Make.user в корневом каталоге и добавив в него строку, такую как:

LLVM_VER = 13.0.0

Кроме номеров релизов LLVM, вы также можете использовать DEPS_GIT = llvm в сочетании с USE_BINARYBUILDER_LLVM = 0, чтобы собирать против последней версии разработки LLVM.

Вы также можете указать на сборку отладочной версии LLVM, установив либо LLVM_DEBUG = 1, либо LLVM_DEBUG = Release в вашем файле Make.user. Первый вариант будет полностью не оптимизированной сборкой LLVM, а последний создаст оптимизированную сборку LLVM. В зависимости от ваших потребностей последний вариант будет достаточен и значительно быстрее. Если вы используете LLVM_DEBUG = Release, вам также следует установить LLVM_ASSERTIONS = 1, чтобы включить диагностику для различных проходов. Только LLVM_DEBUG = 1 подразумевает эту опцию по умолчанию.

Passing options to LLVM

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

• export JULIA_LLVM_ARGS=-print-after-all выводит IR после каждого прохода.
• export JULIA_LLVM_ARGS=-debug-only=loop-vectorize выводит диагностику LLVM DEBUG(...) для векторизатора циклов. Если вы получаете предупреждения о "Неизвестном аргументе командной строки", пересоберите LLVM с LLVM_ASSERTIONS = 1.
• export JULIA_LLVM_ARGS=-help показывает список доступных опций. export JULIA_LLVM_ARGS=-help-hidden показывает еще больше.
• export JULIA_LLVM_ARGS="-fatal-warnings -print-options" является примером того, как использовать несколько опций.

Useful JULIA_LLVM_ARGS parameters

• -print-after=PASS: печатает IR после любого выполнения PASS, полезно для проверки изменений, внесенных проходом.

• -print-before=PASS: выводит IR перед выполнением любого PASS, полезно для проверки входных данных для прохода.

• -print-changed: печатает IR всякий раз, когда проход изменяет IR, полезно для определения, какие проходы вызывают проблемы.

• -print-(before|after)=MARKER-PASS: конвейер Julia поставляется с рядом маркерных проходов в конвейере, которые можно использовать для определения мест, где возникают проблемы или оптимизации. Маркерный проход определяется как проход, который появляется один раз в конвейере и не выполняет никаких преобразований IR, и полезен только для нацеливания на print-before/print-after. В настоящее время в конвейере существуют следующие маркерные проходы:

  • ПередОптимизацией
  • ПередРаннимУпрощением
  • ПослеРаннегоУпрощения
  • ПередРаннейОптимизацией
  • ПослеРаннейОптимизации
  • ПередОптимизациейЦикла
  • BeforeLICM
  • ПослеLICM
  • ПередУпрощениемЦикла
  • ПослеУпрощенияЦикла
  • ПослеОптимизацииЦикла
  • ПередОптимизациейСкалярныхЗначений
  • ПослеОптимизацииСкалярныхЗначений
  • ПередВекторизацией
  • ПослеВекторизации
  • ПередВнутреннимПонижением
  • ПослеВнутреннегоПонижения
  • ПередОчисткой
  • ПослеОчистки
  • ПослеОптимизации

• -time-passes: выводит время, затраченное на каждый проход, полезно для определения, какие проходы занимают много времени.

• -print-module-scope: используется вместе с -print-(before|after), получает весь модуль, а не единицу IR, полученную проходом

• -debug: выводит много информации для отладки на протяжении всего LLVM

• -debug-only=NAME, выводит отладочные сообщения из файлов, в которых DEBUG_TYPE определен как NAME, полезно для получения дополнительного контекста о проблеме

Debugging LLVM transformations in isolation

Иногда может быть полезно отлаживать преобразования LLVM в изоляции от остальной системы Julia, например, потому что воспроизведение проблемы внутри julia займет слишком много времени, или потому что хочется воспользоваться инструментами LLVM (например, bugpoint).

Чтобы начать, вы можете установить инструменты разработчика для работы с LLVM с помощью:

make -C deps install-llvm-tools

Чтобы получить не оптимизированный IR для всего образа системы, передайте параметр --output-unopt-bc unopt.bc в процесс сборки образа системы, который выведет не оптимизированный IR в файл unopt.bc. Этот файл затем можно передать инструментам LLVM, как обычно. libjulia может функционировать как плагин для прохода LLVM и может быть загружен в инструменты LLVM, чтобы сделать доступными специфические для julia проходы в этой среде. Кроме того, он предоставляет мета-проход -julia, который запускает весь конвейер проходов Julia над IR. В качестве примера, чтобы сгенерировать образ системы со старым менеджером проходов, можно сделать:

llc -o sys.o opt.bc
cc -shared -o sys.so sys.o

Чтобы создать образ системы с новым менеджером паролей, можно сделать следующее:

opt -load-pass-plugin=libjulia-codegen.so --passes='julia' -o opt.bc unopt.bc
llc -o sys.o opt.bc
cc -shared -o sys.so sys.o

Это изображение системы затем может быть загружено с помощью julia, как обычно.

Также возможно создать дамп модуля LLVM IR для одной функции Julia, используя:

fun, T = +, Tuple{Int,Int} # Substitute your function of interest here
optimize = false
open("plus.ll", "w") do file
    println(file, InteractiveUtils._dump_function(fun, T, false, false, false, true, :att, optimize, :default, false))
end

Эти файлы можно обрабатывать так же, как и не оптимизированный sysimg IR, показанный выше.

Running the LLVM test suite

Чтобы запустить тесты llvm локально, вам сначала нужно установить инструменты, собрать julia, а затем вы можете запустить тесты:

make -C deps install-llvm-tools
make -j julia-src-release
make -C test/llvmpasses

Если вы хотите запустить отдельные тестовые файлы напрямую, используя команды в начале каждого тестового файла, первый шаг здесь установит инструменты в ./usr/tools/opt. Затем вам нужно будет вручную заменить %s на имя тестового файла.

Improving LLVM optimizations for Julia

Улучшение генерации кода LLVM обычно включает в себя либо изменение понижения Julia, чтобы оно было более дружелюбным к проходам LLVM, либо улучшение прохода.

Если вы планируете улучшить проход, обязательно прочитайте LLVM developer policy. Лучшая стратегия — создать пример кода в форме, где вы можете использовать инструмент opt от LLVM для его изучения и прохода, представляющего интерес, в изоляции.

1. Create an example Julia code of interest.
2. Используйте JULIA_LLVM_ARGS=-print-after-all, чтобы вывести IR.
3. Выберите IR в момент, непосредственно перед тем, как проходит интересующий пас.
4. Удалите отладочные метаданные и исправьте метаданные TBAA вручную.

Последний шаг трудоемкий. Буду признателен за предложения по улучшению процесса.

The jlcall calling convention

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

jl_value_t *any_unoptimized_call(jl_value_t *, jl_value_t **, int);

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

call %jl_value_t *@julia.call(jl_value_t *(*)(...) @any_unoptimized_call, %jl_value_t *%arg1, %jl_value_t *%arg2)

Это позволяет нам сохранить SSA-образность использований на протяжении всего оптимизатора. Размещение корней GC позже упростит этот вызов до оригинального C ABI.

GC root placement

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

if some_condition()
    #= Use some variables maybe =#
    error("An error occurred")
end

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

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

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

Representation

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

• Пользовательские адресные пространства
• Операндные пакеты
• Нецелочисленные указатели

Пользовательские адресные пространства позволяют нам помечать каждую точку целым числом, которое должно сохраняться в процессе оптимизаций. Компилятор не может вставлять приведения между адресными пространствами, которые не существовали в оригинальной программе, и он никогда не должен изменять адресное пространство указателя при операциях загрузки/сохранения и т. д. Это позволяет нам аннотировать, какие указатели отслеживаются сборщиком мусора (GC) устойчивым к оптимизациям образом. Обратите внимание, что метаданные не смогут достичь той же цели. Метаданные должны всегда быть подлежащими удалению без изменения семантики программы. Однако неспособность идентифицировать указатель, отслеживаемый сборщиком мусора, резко изменяет поведение результирующей программы - она, вероятно, аварийно завершится или вернет неверные результаты. В настоящее время мы используем три разных адресных пространства (их номера определены в src/codegen_shared.cpp):

• GC Tracked Pointers (в настоящее время 10): Это указатели на упакованные значения, которые могут быть помещены в кадр сборщика мусора (GC). Это в некотором роде эквивалентно указателю jl_value_t* на стороне C. Обратите внимание, что незаконно иметь указатель в этом адресном пространстве, который не может быть сохранен в слоте GC.
• Производные указатели (в настоящее время 11): Это указатели, которые производятся из какого-либо указателя, отслеживаемого сборщиком мусора (GC). Использование этих указателей приводит к использованию оригинального указателя. Однако они не обязательно должны быть известны сборщику мусора. Процесс размещения корней GC ДОЛЖЕН всегда находить указатель, отслеживаемый GC, из которого производен этот указатель, и использовать его в качестве указателя на корень.
• Callee Rooted Pointers (в настоящее время 12): Это адресное пространство утилиты для выражения понятия значения, коренящегося в вызываемом. Все значения этого адресного пространства ДОЛЖНЫ быть сохранены в корне GC (хотя в будущем возможно ослабление этого условия), но, в отличие от других указателей, не обязательно должны быть коренены, если переданы в вызов (они все еще должны быть коренены, если они активны между другим безопасным пунктом между определением и вызовом).
• Указатели, загруженные из отслеживаемого объекта (в настоящее время 13): Это используется массивами, которые сами содержат указатель на управляемые данные. Эта область данных принадлежит массиву, но сама по себе не является объектом, отслеживаемым сборщиком мусора. Компилятор гарантирует, что пока этот указатель активен, объект, из которого был загружен этот указатель, останется активным.

Invariants

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

Сначала разрешены только следующие приведения адресного пространства:

• 0->{Отслеживаемый, Производный, КореньВызова}: Разрешается преобразовывать неотслеживаемый указатель в любой из других. Однако имейте в виду, что оптимизатор имеет широкие полномочия не коренить такое значение. Никогда не безопасно иметь значение в адресном пространстве 0 в любой части программы, если оно (или производное от него) является значением, требующим корня сборщика мусора.
• Отслеживаемый->Производный: Это стандартный маршрут распада для внутренних значений. Проход размещения будет искать их, чтобы определить базовый указатель для любого использования.
• Отслеживаемый->CalleeRooted: Адресное пространство CalleeRooted служит лишь подсказкой о том, что корень GC не требуется. Однако обратите внимание, что распад Derived->CalleeRooted запрещен, поскольку указатели, как правило, должны быть хранимыми в слоте GC, даже в этом адресном пространстве.

Теперь давайте рассмотрим, что составляет использование:

• Загрузки, чьи загруженные значения находятся в одном из адресных пространств
• Сохранение значения в одном из адресных пространств по адресу
• Сохраняет указатель в одном из адресных пространств
• Вызовы, для которых значение в одном из адресных пространств является операндом
• Вызовы в ABI jlcall, для которых массив аргументов содержит значение
• Пожалуйста, вставьте текст или содержимое Markdown, которое вы хотите перевести.

Мы явно разрешаем загрузки/сохранения и простые вызовы в адресных пространствах Tracked/Derived. Элементы массивов аргументов jlcall всегда должны находиться в адресном пространстве Tracked (это требуется ABI, чтобы они были действительными указателями jl_value_t*). То же самое касается инструкций возврата (хотя стоит отметить, что аргументы возврата структур могут иметь любое из адресных пространств). Единственное допустимое использование указателя CalleeRooted в адресном пространстве — это передача его в вызов (который должен иметь соответствующий тип операнда).

Далее мы запрещаем getelementptr в адресном пространстве Tracked. Это связано с тем, что если операция не является noop, то полученный указатель не может быть корректно сохранен в слоте GC и, следовательно, может не находиться в этом адресном пространстве. Если такой указатель необходим, его следует сначала преобразовать в адресное пространство Derived.

Наконец, мы запрещаем инструкции inttoptr/ptrtoint в этих адресных пространствах. Наличие этих инструкций означало бы, что некоторые значения i64 действительно отслеживаются сборщиком мусора. Это проблематично, потому что это нарушает заявленное требование о том, что мы должны иметь возможность идентифицировать указатели, относящиеся к сборщику мусора. Это инвариант достигается с помощью функции LLVM "нецелочисленные указатели", которая новая в LLVM 5.0. Она запрещает оптимизатору выполнять оптимизации, которые могли бы ввести эти операции. Обратите внимание, что мы все еще можем вставлять статические константы во время JIT, используя inttoptr в адресном пространстве 0, а затем переходя к соответствующему адресному пространству.

Supporting ccall

Одним из важных аспектов, отсутствующих в обсуждении до сих пор, является обработка ccall. 4d61726b646f776e2e436f64652822222c20226363616c6c2229_40726566 имеет своеобразную особенность, что местоположение и область использования не совпадают. В качестве примера рассмотрим:

A = randn(1024)
ccall(:foo, Cvoid, (Ptr{Float64},), A)

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

return $(Expr(:foreigncall, :(:foo), Cvoid, svec(Ptr{Float64}), 0, :(:ccall), Expr(:foreigncall, :(:jl_array_ptr), Ptr{Float64}, svec(Any), 0, :(:ccall), :(A)), :(A)))

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

call void inttoptr (i64 ... to void (double*)*)(double* %5) [ "jl_roots"(%jl_value_t addrspace(10)* %A) ]

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

Supporting pointer_from_objref

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

declared %jl_value_t *julia.pointer_from_objref(%jl_value_t addrspace(10)*)

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

Keeping values alive in the absence of uses

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

token @llvm.julia.gc_preserve_begin(...)
void @llvm.julia.gc_preserve_end(token)

(Требуется llvm. в имени, чтобы можно было использовать тип token). Семантика этих встроенных функций следующая: в любой точке безопасности, которая контролируется вызовом gc_preserve_begin, но не контролируется соответствующим вызовом gc_preserve_end (т.е. вызовом, аргументом которого является токен, возвращаемый вызовом gc_preserve_begin), значения, переданные в качестве аргументов этому gc_preserve_begin, будут оставаться живыми. Обратите внимание, что gc_preserve_begin по-прежнему считается обычным использованием этих значений, поэтому стандартная семантика времени жизни обеспечит, что значения будут оставаться живыми перед входом в область сохранения.