GitHub

Eval of Julia code

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

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

Definitions

  • REPL

    REPL означает Read-Eval-Print Loop. Это просто то, как мы называем среду командной строки в сокращенном виде.

  • AST

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

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

Julia Execution

Общий обзор всего процесса на высоте 10,000 футов выглядит следующим образом:

  1. Пользователь запускает julia.
  2. Функция C main() из cli/loader_exe.c вызывается. Эта функция обрабатывает аргументы командной строки, заполняя структуру jl_options и устанавливая переменную ARGS. Затем она инициализирует Julia (вызывая julia_init in init.c, что может загрузить ранее скомпилированный sysimg). Наконец, она передает управление Julia, вызывая Base._start().
  3. Когда _start() берет на себя управление, последующая последовательность команд зависит от аргументов командной строки. Например, если было указано имя файла, он продолжит выполнение этого файла. В противном случае он начнет интерактивный REPL.
  4. Пропустив детали о том, как REPL взаимодействует с пользователем, скажем просто, что программа в конечном итоге получает блок кода, который она хочет выполнить.
  5. Если блок кода для выполнения находится в файле, jl_load(char *filename) вызывается для загрузки файла и parse его. Каждый фрагмент кода затем передается в eval для выполнения.
  6. Каждый фрагмент кода (или AST) передается eval() для получения результатов.
  7. eval() берет каждый фрагмент кода и пытается выполнить его в jl_toplevel_eval_flex().
  8. jl_toplevel_eval_flex() решает, является ли код "топовым" действием (таким как using или module), что было бы недопустимо внутри функции. Если да, то он передает код интерпретатору верхнего уровня.
  9. jl_toplevel_eval_flex() затем expands код для устранения любых макросов и для "понижения" AST, чтобы сделать его проще для выполнения.
  10. jl_toplevel_eval_flex() затем использует некоторые простые эвристики, чтобы решить, компилировать ли AST с помощью JIT или интерпретировать его напрямую.
  11. Основная часть работы по интерпретации кода выполняется eval in interpreter.c.
  12. Если вместо этого код компилируется, основная часть работы выполняется codegen.cpp. Каждый раз, когда функция Julia вызывается в первый раз с заданным набором типов аргументов, type inference будет выполнена для этой функции. Эта информация используется на этапе codegen для генерации более быстрого кода.
  13. В конечном итоге пользователь выходит из REPL, или достигается конец программы, и метод _start() возвращает значение.
  14. Прямо перед выходом main() вызывает jl_atexit_hook(exit_code). Это вызывает Base._atexit() (который вызывает любые функции, зарегистрированные в atexit() внутри Julia). Затем он вызывает jl_gc_run_all_finalizers(). Наконец, он аккуратно очищает все дескрипторы libuv и ждет, пока они не будут сброшены и закрыты.

Parsing

Парсер 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>")

Macro Expansion

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

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

Type Inference

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

More Definitions

  • JIT

    Just-In-Time Компиляция Процесс генерации нативного машинного кода в память именно тогда, когда он нужен.

  • LLVM

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

  • C++

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

  • коробка

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

  • распаковать

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

  • генерическая функция

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

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

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

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

    Функция, реализованная на C, но представленная в Julia как именованная функция "method" (хотя и без возможностей диспетчеризации обобщенных функций, аналогично анонимной функции)

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

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

JIT Code Generation

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

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

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

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

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

  • debuginfo.cpp

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

  • ccall.cpp

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

  • intrinsics.cpp

    Обрабатывает эмиссию различных низкоуровневых встроенных функций

Bootstrapping

Процесс создания нового образа системы называется "bootstrapping".

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

System Image

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

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