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

Вычисление кода Julia

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

Каждый фрагмент кода обычно проходит через множество этапов с потенциально незнакомыми названиями, такими как (в произвольном порядке): использование интерпретатора flisp, AST, C++, LLVM, eval, typeinf, macroexpand, sysimg (или образ системы), начальная загрузка, компиляция, анализ, выполнение, JIT, интерпретация, упаковка, распаковка, использование встроенной функции и примитивной функции, прежде чем стать желаемым результатом (как хотелось бы надеяться).

Определения

  • REPL

    REPL означает цикл «чтение — вычисление — вывод». Так для краткости мы называем среду командной строки.

  • AST

    Абстрактное синтаксическое дерево. AST — это цифровое представление структуры кода. В этой форме код был размечен по смыслу, чтобы в большей степени подходить для обработки и выполнения.

Выполнение кода Julia

Далее приводится общее описание процесса.

  1. Пользователь запускает julia.

  2. Вызывается функция C main() из cli/loader_exe.c. Эта функция обрабатывает аргументы командной строки , заполняя структуру jl_options и задавая переменную ARGS. Затем она инициализирует Julia (вызывая функцию julia_init в task.c, которая может загрузить ранее скомпилированный образ системы, sysimg). Наконец, она передает управление Julia, вызывая Base._start().

  3. Когда _start() принимает управление, последующая последовательность команд зависит от заданных аргументов командной строки . Например, если было указано имя файла, будет выполнен этот файл. В противном случае будет запущен интерактивный цикл REPL.

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

  5. Если блок кода для выполнения находится в файле, вызывается jl_load(char *filename) для загрузки файла и его анализа. Затем каждый фрагмент кода передается eval для выполнения.

  6. Каждый фрагмент кода (или AST) передается в eval() для преобразования в результат.

  7. eval() takes each code fragment and tries to run it in jl_toplevel_eval_flex().

  8. jl_toplevel_eval_flex() определяет, является ли код действием верхнего уровня (например, using или module), которое будет недопустимо внутри функции. Если это так, код передается интерпретатору верхнего уровня.

  9. Затем jl_toplevel_eval_flex() расширяет код, чтобы исключить любые макросы и понизить AST, чтобы упростить его выполнение.

  10. После этого jl_toplevel_eval_flex() использует некоторые простые эвристические процедуры, чтобы решить, выполнять JIT-компиляцию для AST или интерпретировать его напрямую.

  11. Основную часть работы по интерпретации кода выполняет eval в interpreter.c.

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

  13. В конечном счете пользователь выходит из REPL или достигается конец программы и возвращается метод _start().

  14. Перед самым выходом main() вызывает jl_atexit_hook(exit_code). При этом вызывается функция Base._atexit() (которая вызывает любые функции, зарегистрированные в atexit() внутри Julia). Затем вызывается функция jl_gc_run_all_finalizers(). В итоге она корректно очищает все обработчики libuv и ждет, пока они не будут сброшены и закрыты.

Анализ

Анализатор Julia — это небольшая программа lisp, написанная на языке femtolisp, исходный код которой находится внутри Julia в папке src/flisp.

Ее интерфейсные функции определены в основном в jlfrontend.scm. Код в ast.c обрабатывает эту передачу на стороне Julia.

Другими важными файлами на этом этапе являются julia-parser.scm, который обрабатывает разметку кода Julia и преобразует его в AST, и julia-syntax.scm, который обрабатывает преобразование сложных представлений AST в простые пониженные представления AST, более подходящие для анализа и выполнения.

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

$ cd src
$ flisp/flisp
> (load "jlfrontend.scm")
> (jl-parse-file "<filename>")

Расширение макроса

Когда функция eval() обнаруживает макрос, она расширяет этот узел AST, прежде чем попытаться вычислить выражение. Расширение макроса предполагает передачу из eval() (в Julia) в функцию анализатора jl_macroexpand() (записанную в flisp) к самому макросу Julia (записанному где-то в Julia) с помощью функции fl_invoke_julia_macro() и обратно.

Обычно расширение активируется в качестве первого шага во время вызова Meta.lower()/jl_expand(), хотя оно также может быть инициировано напрямую вызовом macroexpand()/jl_macroexpand().

Вывод типов

В Julia вывод типов реализуется с помощью функции typeinf() в файле compiler/typeinfer.jl. Вывод типов — это процесс исследования функции Julia и определения границ типов каждой ее переменной, а также границ типа возвращаемого значения функции. Это позволяет внедрять многие будущие меры оптимизации, такие как распаковка известных неизменяемых значений, и поднимать во время компиляции различные вычислительные операции, такие как вычисление смещений полей и указателей функций. Вывод типа может также содержать другие шаги, такие как распространение констант и встраивание.

Еще больше определений

  • JIT

    Оперативная компиляция (JIT-компиляция). Процесс генерации собственного машинного кода в память именно тогда, когда это необходимо.

  • LLVM

    Низкоуровневая виртуальная машина (компилятор). JIT-компилятор Julia — это программа или библиотека, называемая libLLVM. Генерация кода в Julia относится как к процессу преобразования AST Julia в инструкции LLVM, так и к процессу оптимизации инструкций LLVM и их преобразования в собственные инструкции сборки.

  • C++

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

  • Упаковка

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

  • Распаковка

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

  • Универсальная функция

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

  • Анонимная функция или метод

    Функция Julia без имени и без возможностей диспетчеризации типов.

  • Примитивная функция

    Функция, реализованная на C, но представленная в Julia как метод именованной функции (хотя и без возможностей диспетчеризации универсальной функций: подобна анонимной функции).

  • Внутренняя функция

    Низкоуровневая операция, представленная в Julia в виде функции. Эти псевдофункции реализуют операции с необработанными битами, такие как сложение и расширение знака, которые не могут быть выражены непосредственно каким-либо другим способом. Поскольку они работают с битами напрямую, они должны быть скомпилированы в функцию и окружены вызовом `Core.Intrinsics.box(T, ...)`для переписывания информации о типе для значения.

JIT-генерация кода

Генерация кода — это процесс преобразования AST Julia в собственный машинный код.

JIT-среда инициализируется заблаговременным вызовом jl_init_codegen в codegen.cpp.

По запросу метод Julia преобразуется в собственную функцию с помощью функции emit_function(jl_method_instance_t*). (Обратите внимание, что при использовании MCJIT (в LLVM v3.4 и более поздних версиях) каждая функция должна быть JIT в новый модуль.) Эта функция рекурсивно вызывает функцию emit_expr() до тех пор, пока не будет выдана вся функция.

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

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

  • debuginfo.cpp

    Обрабатывает обратные трассировки для JIT-функции.

  • ccall.cpp

    Обрабатывает FFI ccall и llvmcall, а также различные файлы abi_*.cpp.

  • intrinsics.cpp

    Обрабатывает выдачу различных низкоуровневых внутренних функций.

Bootstrapping

Процесс создания образа системы называется начальной загрузкой (bootstrapping). Это слово происходит от английской фразы "pulling oneself up by the bootstraps" (добиться всего своими силами) и означает идею начать с очень ограниченного набора доступных функций и определений и закончить созданием полнофункциональной среды.

Образ системы

Образ системы представляет собой предварительно скомпилированный архив набора файлов Julia. Файл sys.ji, распространяемый с Julia, является одним из таких образов системы, созданным путем выполнения файла sysimg.jl и сериализации полученной среды (включая типы, функции, модули и все другие определенные значения) в файл. Поэтому он содержит статичную версию модулей Main, Core и Base (и всего остального, что было в среде в конце начальной загрузки). Этот сериализатор или десериализатор реализован с помощью функции jl_save_system_image или jl_restore_system_image в файле staticdata.c.

Если файл sysimg отсутствует (jl_options.image_file == NULL), это также означает, что в командной строке был указан параметр --build, поэтому конечным результатом должен быть новый файл sysimg. Во время инициализации Julia создаются минимальные модули Core и Main. Затем из текущего каталога вычисляется файл с именем boot.jl. После этого Julia вычисляет любой файл, заданный в качестве аргумента командной строки, пока не дойдет до конца. Наконец, она сохраняет результирующую среду в файл sysimg для использования в качестве отправной точки для будущего выполнения.