Глава 21 Оптимизация с помощью Flambda

• 21.1 Обзор
• 21.2 Флаги командной строки
• 21.3 Встраивание
• 21.4 Специализация
• 21.5 Значения параметров по умолчанию
• 21.6 Ручное управление встраиванием и специализацией
• 21.7 Упрощение
• 21.8 Другие преобразования перемещения кода
• 21.9 Преобразования распаковки
• 21.10 Удаление неиспользуемого кода и значений
• 21.11 Другие преобразования кода
• 21.12 Обработка эффектов
• 21.13 Компиляция статически размещенных модулей
• 21.14 Ингибирование оптимизации
• 21.15 Использование небезопасных операций
• 21.16 Словарь

21.1 Обзор

Flambda — это термин, используемый для описания серии проходов оптимизации, предоставляемых нативными компиляторами с OCaml 4.03.

Flambda призван упростить написание идиоматического кода OCaml без потери производительности.

Для использования оптимизаторов Flambda необходимо передать параметр -flambda скрипту конфигурации OCaml configure. (Нет поддержки единого компилятора, который может работать как в режиме Flambda, так и без него.) Код, скомпилированный с Flambda, не может быть связан в одну программу с кодом, скомпилированным без Flambda. Попытка сделать это приведет к ошибке компилятора.

Можно определить, использует ли конкретный ocamlopt Flambda, вызвав его с параметром -config и поиска любой строки, начинающейся с «flambda:». Если такая строка присутствует и содержит «true», то Flambda поддерживается, в противном случае — нет.

Flambda обеспечивает полную оптимизацию по различным единицам компиляции, при условии, что файлы .cmx для зависимостей текущей единицы компиляции доступны. (Единица компиляции соответствует одному файлу исходного кода .ml.) Однако он пока не работает полностью как компилятор всего проекта: например, устранение мертвого кода по всему набору единиц компиляции не поддерживается.

Оптимизация с помощью Flambda в настоящее время не поддерживается при генерации байткода.

В общем случае Flambda не должен влиять на семантику существующих программ. Два исключения из этого правила: возможное удаление чистого кода, который тестируется на производительность (см. раздел 21.14) и изменения в поведении кода, использующего небезопасные операции (см. раздел 21.15).

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

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

21.2 Флаги командной строки

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

Обычно используемые параметры:

-O2

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

-O3

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

-Oclassic

Принимает решения о встраивании на момент определения функции, а не в точке вызова(ов). Это отражает поведение компиляторов OCaml, не использующих Flambda. По сравнению с компиляцией с использованием новых эвристик встраивания Flambda (например, при -O2) он генерирует файлы .cmx меньшего размера, сокращает время компиляции и, вероятно, приводит к более медленной работе кода. При использовании -Oclassic актуальны только следующие параметры, описанные в этом разделе: -inlining-report и -inline. При использовании других параметров, описанных в этом разделе, поведение не определено и может привести к ошибкам в будущих версиях компилятора.

-inlining-report

Создает файлы .inlining (по одному на раунд оптимизации), показывающие все решения инлайнера.

Реже используемые параметры:

-remove-unused-arguments

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

-unbox-closures

Передает свободные переменные через специализированные аргументы, а не через замыкания (оптимизация для уменьшения выделения памяти). См. раздел 21.9.3. Это может незначительно сказаться на производительности.

Расширенные параметры, необходимые только для подробной настройки:

-inline

Поведение зависит от использования -Oclassic.

• При отсутствии режима -Oclassic, -inline ограничивает общий размер функций, рассматриваемых для встраивания во время поиска спекулятивного встраивания. (См. раздел 21.3.6.) Обратите внимание, что этот параметр не управляет оценкой возможности встраивания конкретной функции. Увеличение его до чрезмерных значений не обязательно приведет к встраиванию большего количества функций.
• При использовании режима -Oclassic, -inline ведет себя как в предыдущих версиях компилятора: это максимальный размер функции для встраивания. См. раздел 21.3.1.

-inline-toplevel

Эквивалент -inline, но используется, когда спекулятивное встраивание начинается на уровне верхнего уровня. См. раздел 21.3.6. Не используется в режиме -Oclassic.

...

Примечания

• Набор флагов командной строки, относящихся к оптимизации, обычно должен быть одинаковым для всего проекта. Flambda в настоящее время не записывает запрошенные флаги в файлы .cmx. Таким образом, встраивание функций из ранее скомпилированных модулей подвергнет их код параметрам оптимизации модуля, который в настоящее время компилируется, а не тем, которые были указаны при их предыдущей компиляции. Надеемся исправить этот недостаток в будущем.
• Флаги, специфичные для Flambda, не влияют на линковку, за исключением влияния на оптимизацию кода в файле загрузки (содержащем сгенерированные функции, такие как вспомогательные функции кюрринга). Как правило, такая оптимизация не будет существенной, поэтому исключение таких флагов во время линковки может быть оправданным.
• Флаги, специфичные для Flambda, молча принимаются даже тогда, когда опция -flambda не была передана скрипту configure. (Нет способа изменить это поведение.) Это призвано упростить выполнение тестов с включенными и выключенными оптимизаторами Flambda.
• Некоторые флаги Flambda могут быть изменены в будущих выпусках.

21.2.1 Указание параметров оптимизации по раундам

Flambda работает в раундах: один раунд состоит из определенной последовательности преобразований, которые затем могут быть повторены для достижения более удовлетворительных результатов. Количество раундов можно установить вручную, используя параметр -rounds (хотя это не обязательно, когда используются предопределённые уровни оптимизации, такие как -O2 и -O3). Для высокой оптимизации количество раундов можно установить в 3 или 4.

Флаги командной строки, которые могут применяться по раундам, например, те, у которых в имени есть -cost, принимают аргументы в форме:

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

Флаги -Oclassic, -O2 и -O3 применяются до всех остальных флагов, что означает, что некоторые параметры могут быть переопределены, не указывая каждый параметр, обычно вызываемый данным уровнем оптимизации.

21.3 Встраивание

Встраивание — это копирование кода функции в место вызова функции. Код функции будет окружён связываниями её параметров с соответствующими аргументами.

Цели встраивания:

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

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

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

Например, в данном коде:

let rec fact x =
  if x = 0 then
    1
  else
    x * fact (x - 1)

let n = fact 4

развёртывание один раз в месте вызова fact 4 даёт (при неизменном теле fact):

let n =
  if 4 = 0 then
    1
  else
    4 * fact (4 - 1)

Это упрощается до:

let n = 4 * fact 3

Flambda предоставляет значительно улучшенные возможности встраивания по сравнению с предыдущими версиями компилятора.

Примечание: когда выполняется встраивание

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

• Разрешает встраивание высшего порядка, например, когда не встраиваемая функция всегда возвращает ту же функцию, но с различными средами определения. Пока не все такие случаи поддерживаются, но предполагается, что такая поддержка будет улучшена в будущем.
• Легче интегрировать с оптимизацией между модулями, так как информация об импортированных модулях уже находится в правильном промежуточном языке.
• Упрощается оптимизация выделения памяти для замыканий, так как расположение замыканий известно. Точно так же становится проще контролировать, какие переменные попадают в какие замыкания, помогая избежать чрезмерного использования памяти под замыкания.

21.3.1 Эвристика классического встраивания

В режиме -Oclassic поведение встроенного модуля Flambda имитирует предыдущие версии компилятора. (Код по-прежнему может быть подвергнут дальнейшей оптимизации, не выполняемой предыдущими версиями компилятора: функторы могут быть встроены, константы подняты, и неиспользуемый код удаляется, как описано в этой главе. См. разделы 21.3.3, 21.8.1 и 21.10. В месте определения функции тело функции измеряется. Затем оно будет помечено как подходящее для встраивания (и, следовательно, встроено в каждом месте прямого вызова), если:

• измеренный размер (в не указанных единицах) меньше размера вызова функции плюс аргумент флага командной строки -inline; и
• функция не является рекурсивной.

Не-Flambda версии компилятора не могут встроить функции, содержащие определение другой функции. Однако -Oclassic это позволяет. Кроме того, не-Flambda версии также не могут встраивать функции, которые сами по себе доступны только в результате предыдущего прохода встраивания, но это разрешено -Oclassic. Например:

module M : sig
  val i : int
end = struct
  let f x =
    let g y = x + y in
    g
  let h = f 3
  let i = h 4  (* h is correctly discovered to be g and inlined *)
end

Всё это контрастирует с обычным режимом Flambda, то есть без -Oclassic, где:

• решение о встраивании принимается в месте вызова; и
• рекурсивные функции могут обрабатываться путём специализации (см. ниже).

Режим Flambda описан в следующем разделе.

21.3.2 Обзор эвристик встраивания «Flambda»

Эвристики встраивания Flambda, используемые всякий раз, когда компилятор настроен на Flambda и не был указан -Oclassic, принимают решения о встраивании в местах вызова. Это помогает в ситуациях, когда контекст важен. Например:

let f b x =
  if b then
    x
  else
    ... big expression ...

let g x = f true x

В этом случае мы хотели бы встроить f в g, потому что условный переход может быть исключён, и размер кода должен уменьшиться. Если решение о встраивании было принято после объявления f без просмотра использования, его размер, вероятно, сделал бы его непригодным для встраивания; но в месте вызова его окончательный размер может быть известен. Кроме того, эта функция, вероятно, не должна встраиваться систематически: если b неизвестно, или, действительно, равно false, выгода мала по сравнению с большим увеличением размера кода. В существующем не-Flambda встроенном модуле это не большая проблема, потому что цепочки встраивания обрывались довольно быстро. Однако это привело к чрезмерному использованию чрезмерно больших параметров встраивания, таких как -inline 10000.

Более подробно, в каждом месте вызова выполняется следующая процедура:

• Определите, очевидно ли, что встраивание будет выгодно, не выполняя пока никакого встраивания внутри самой функции. (Точный анализ выгоды описан ниже.) Если это так, функция встраивается.
• Если встраивание функции явно не выгодно, тогда встраивание будет выполняться спекулятивно внутри самой функции. Поиск возможных спекулятивных встраиваний контролируется двумя параметрами: порогом встраивания и глубиной встраивания. (Они описаны более подробно ниже.)
  • Если такая спекуляция показывает, что выполнение некоторого встраивания внутри функции было бы выгодно, то такое встраивание выполняется, и получившаяся функция встраивается в исходное место вызова.
  • В противном случае ничего не происходит.

Встраивание внутри рекурсивных функций вызовов других функций в той же группе взаимной рекурсии контролируется глубиной развёртывания, описанной ниже. Это гарантирует, что функции не будут развёртываться чрезмерно. (Развёртывание включено только если выбран уровень оптимизации -O3 и/или передан флаг -inline-max-unroll с аргументом больше нуля.)

21.3.3 Обработка конкретных конструкций языка

Функторы

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

Применения функторов на верхнем уровне имеют тенденцию к встраиванию. (Этот уклон может быть скорректирован: см. документацию по -inline-lifting-benefit ниже.)

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

Модули первого класса

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

Объекты

Вызовы методов к объектам в настоящее время не встраиваются Flambda.

21.3.4 Отчеты о встраивании

Если компилятору предоставлен параметр -inlining-report, то будет создан файл, соответствующий каждому раунду оптимизации. Для файла исходного кода OCaml basename.ml файлы называются basename.round.inlining.org, где round — целочисленное значение, начиная с нуля. Внутри файлов, отформатированных в формате «org mode», будет представлен текст на английском языке, описывающий решения, принятые инлайнером.

21.3.5 Оценка выгоды от встраивания

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

Например, для следующего кода:

let f b x =
  if b then
    x
  else
    ... big expression ...

let g x = f true x

можно заметить, что встраивание f приведет к удалению:

• одного прямого вызова;
• одного условного перехода.

Формально, оценка выгоды от производительности во время выполнения вычисляется путем суммирования стоимости операций, которые известны как удаляемые в результате встраивания и последующего упрощения тела встраиваемого блока. Индивидуальные затраты на различные виды операций могут быть скорректированы с помощью различных флагов -inline-...-cost следующим образом. Стоимости задаются целыми числами. Все эти флаги принимают один аргумент, описывающий такие целые числа, используя соглашения, описанные в разделе 21.2.1.

-inline-alloc-cost

Стоимость выделения памяти.

-inline-branch-cost

Стоимость перехода.

-inline-call-cost

Стоимость прямого вызова функции.

-inline-indirect-cost

Стоимость косвенного вызова функции.

-inline-prim-cost

Стоимость примитива. Примитивы охватывают операции, включая арифметику и доступ к памяти.

(Значения по умолчанию описаны в разделе 21.5 ниже.)

Начальное значение выгоды затем масштабируется с помощью множителя, который пытается компенсировать тот факт, что текущая точка в коде, если находится под несколькими условными переходами, может быть холодной. (Flambda в настоящее время не вычисляет горячие и холодные пути.) Множитель — оценочная вероятность того, что инлайнер действительно находится на горячем пути — вычисляется как 1/(1 + f)^d, где f устанавливается флагом -inline-branch-factor, а d — глубина вложения переходов в текущей точке. По мере того как инлайнер спускается в более глубоко вложенные переходы, выгода от встраивания уменьшается.

Полученное значение выгоды известно как ожидаемая выгода.

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

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

Применения функторов на верхнем уровне получат дополнительную выгоду (которую можно настроить с помощью флага -inline-lifting-benefit), чтобы настроить встраивание в таких ситуациях в сторону сохранения встраиваемого варианта.

21.3.6 Управление спекуляцией

Как описано выше, есть три параметра, которые ограничивают поиск возможностей встраивания во время спекуляции:

• порог встраивания;
• глубина встраивания;
• глубина разворачивания.

Эти параметры в конечном итоге ограничены аргументами, предоставленными соответствующим флагам командной строки (или их значениям по умолчанию):

• -inline (или, если место вызова, вызвавшее спекуляцию, находится на верхнем уровне, -inline-toplevel);
• -inline-max-depth;
• -inline-max-unroll.

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

Когда начинается спекуляция, порог встраивания устанавливается в значение, заданное -inline (или -inline-toplevel, если это уместно, см. выше). При принятии спекулятивного решения о встраивании порог уменьшается на размер кода встраиваемой функции. Если порог исчерпан, равный или ниже нуля, дальнейшая спекуляция не будет проводиться.

Глубина встраивания начинается с нуля и увеличивается на единицу каждый раз, когда инлайнер спускается в другую функцию. Затем она уменьшается на единицу каждый раз, когда инлайнер выходит из такой функции. Если глубина превышает значение, заданное -inline-max-depth, то спекуляция прекращается. Этот параметр предназначен в качестве общего стопора для ситуаций, когда порог встраивания не контролирует поиск достаточно эффективно.

Глубина разворачивания применяется к вызовам в пределах той же взаимно-рекурсивной группы функций. Каждый раз, когда выполняется встраивание такого вызова, глубина увеличивается на единицу при изучении результирующего тела. Если глубина достигает предела, заданного -inline-max-unroll, то спекуляция прекращается.

21.4 Специализация

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

Если не переопределено атрибутом (см. ниже), специализация функции не будет попытана, если:

• компилятор находится в режиме -Oclassic;
• функция не является очевидно рекурсивной;
• функция не является закрытой.

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

Следует отметить, что проход распаковки замыканий (см. ниже) может вводить специализированные аргументы в нерекурсивные функции. (В настоящее время нигде в компиляторе это не делается.)

Пример: известная функция List.iter

Эта функция может быть записана следующим образом:

let rec iter f l =
  match l with
  | [] -> ()
  | h :: t ->
    f h;
    iter f t

и использоваться так:

let print_int x =
  print_endline (Int.to_string x)

let run xs =
  iter print_int (List.rev xs)

Аргумент f для iter является инвариантным, поэтому функция может быть специализирована:

let run xs =
  let rec iter' f l =
    (* The compiler knows: f holds the same value as foo throughout iter'. *)
    match l with
    | [] -> ()
    | h :: t ->
      f h;
      iter' f t
  in
  iter' print_int (List.rev xs)

Компилятор записывает, что для функции iter’ аргумент f специализирован на постоянном замыкании print_int. Это означает, что тело iter’ может быть упрощено:

let run xs =
  let rec iter' f l =
    (* The compiler knows: f holds the same value as foo throughout iter'. *)
    match l with
    | [] -> ()
    | h :: t ->
      print_int h;  (* this is now a direct call *)
      iter' f t
  in
  iter' print_int (List.rev xs)

Вызов print_int действительно можно встроить:

let run xs =
  let rec iter' f l =
    (* The compiler knows: f holds the same value as foo throughout iter'. *)
    match l with
    | [] -> ()
    | h :: t ->
      print_endline (Int.to_string h);
      iter' f t
  in
  iter' print_int (List.rev xs)

Неиспользуемый специализированный аргумент f теперь можно удалить, оставив:

let run xs =
  let rec iter' l =
    match l with
    | [] -> ()
    | h :: t ->
      print_endline (Int.to_string h);
      iter' t
  in
  iter' (List.rev xs)

Отступление по инвариантным параметрам.

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

let rec iter_swap f g l =
  match l with
  | [] -> ()
  | 0 :: t ->
    iter_swap g f l
  | h :: t ->
    f h;
    iter_swap f g t

21.4.1 Оценка выгоды от специализации

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

21.5 Значения параметров по умолчанию

Значения параметров по умолчанию (при отсутствии -Oclassic) предназначены для одного раунда оптимизации с использованием следующих параметров.

21.5.1 Настройки при оптимизации -O2

При указании -O2 выполняются два раунда оптимизации. Первый раунд использует параметры по умолчанию (см. выше). Второй раунд использует следующие параметры.

21.5.2 Настройки при оптимизации -O3

При указании -O3 выполняются три раунда оптимизации. Первые два раунда аналогичны оптимизации -O2. Третий раунд использует следующие параметры.

21.6 Ручное управление встраиванием и специализацией

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

Для управления встраивателем используются атрибуты. Для нерекурсивных функций (и одношагового развёртывания рекурсивных функций, хотя для этой цели более ясен @unroll) поддерживаются следующие:

@@inline always или @@inline never

Прикреплённые к объявлению функции или функтора, они указывают встраивателю на встраивание всегда или никогда, независимо от расчёта размера/выгоды. (Если функция рекурсивна, то тело подставляется, и никаких специальных действий не предпринимается для сайта(ов) рекурсивного вызова.) @@inline без аргумента эквивалентно @@inline always.

@inlined always или @inlined never

Прикреплённые к применению функции, они аналогичным образом управляют встраивателем. Эти атрибуты на сайтах вызова переопределяют любые другие атрибуты, которые могут присутствовать в соответствующем объявлении. @inlined без аргумента эквивалентно @inlined always. @@inlined hint эквивалентно @@inline always, за исключением того, что оно не будет вызывать предупреждение 55, если приложение функции нельзя встроить.

Для рекурсивных функций соответствующие атрибуты:

@@specialise always или @@specialise never

Прикреплённые к объявлению функции или функтора, они указывают встраивателю на специализацию функции всегда или никогда, при наличии соответствующих контекстных знаний, независимо от расчёта размера/выгоды. @@specialise без аргумента эквивалентно @@specialise always.

@specialised always или @specialised never

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

@unrolled n

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

• Если n равно нулю или меньше, ничего не происходит.
• В противном случае вызываемая функция подставляется на месте вызова своим телом, которое было переписано таким образом, что любые рекурсивные вызовы этой функции или любых других функций в той же группе взаимной рекурсии помечены атрибутом unrolled(n − 1). Встраивание может продолжаться в этом теле.

Таким образом, n является «максимальной глубиной развёртывания».

Предупреждение компилятора будет выведено, если выяснилось, что невозможно выполнить аннотацию из атрибута @inlined или @specialised.

Пример правильного размещения атрибутов

module F (M : sig type t end) = struct
  let[@inline never] bar x =
    x * 3

  let foo x =
    (bar [@inlined]) (42 + x)
end [@@inline never]

module X = F [@inlined] (struct type t = int end)

21.7 Упрощение

Упрощение, которое выполняется совместно с встраиванием, распространяет информацию (известную как приближения) о том, какие переменные содержат какие значения во время выполнения. Также отслеживаются определённые отношения между переменными и символами: например, может быть известно, что какая-то переменная всегда содержит то же значение, что и какая-то другая переменная; или, возможно, какая-то переменная всегда содержит значение, на которое указывает какой-то символ.

Распространение может помочь в устранении выделений в таких случаях, как:

let f x y =
  ...
  let p = x, y in
  ...
  ... (fst p) ... (snd p) ...

Проекции из p могут быть заменены использованием переменных x и y, что потенциально может означать, что p станет неиспользуемым.

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

Обратите внимание, что информация о содержимом строк не распространяется, даже в режиме safe-string, потому что пока нельзя гарантировать, что они неизменны на протяжении всего заданного программы.

21.8 Другие преобразования перемещения кода

21.8.1 Поднятие констант

Выражения, являющиеся константами, будут подняты до привязок символов — то есть, они будут статически размещены в объектном файле — когда они оцениваются как упакованные значения. Такие константы могут быть простыми числовыми константами, такими как число с плавающей точкой 42.0, или более сложными значениями, такими как константные замыкания.

Поднятие констант до верхнего уровня уменьшает выделение памяти во время выполнения.

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

Примечания об массивах чисел с плавающей точкой

Следующие семантические правила языка применяются конкретно к массивам чисел с плавающей точкой-константам. (Под «массивом чисел с плавающей точкой-константой» понимается массив, состоящий только из чисел с плавающей точкой, известных во время компиляции. Частым случаем является литерал, такой как [| 42.0; 43.0; |].

• Массивы чисел с плавающей точкой-константы на верхнем уровне являются изменяемыми и никогда не разделяются. (То есть, для каждого такого определения существует отдельный символ в разделе данных объектного файла, указывающий на массив.)
• Массивы чисел с плавающей точкой-константы, не находящиеся на верхнем уровне, являются изменяемыми и создаются каждый раз при оценке выражения. Это можно рассматривать как операцию, которая принимает неизменяемый массив (который в исходном коде не имеет связанного имени; назовем его инициализирующим массивом) и дублирует его в новый изменяемый массив.
  • Если массив имеет размер четыре или меньше, выражение создаст новый блок и запишет значения в него по одному. Нет ссылки на инициализирующий массив как на целое.
  • В противном случае инициализирующий массив поднимается и подвергается обычной процедуре совместного использования констант; создание массива состоит из объемной копии инициализирующего массива в новое значение в куче OCaml.

21.8.2 Поднятие привязок let на верхнем уровне

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

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

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

21.9 Преобразования разыменования

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

21.9.1 Разыменование переменных замыкания

Это преобразование включено, если не указан параметр -no-unbox-free-vars-of-closures.

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

Пример:

В приведенном ниже коде компилятор замечает, что замыкание, возвращаемое функцией f, содержит переменную pair (свободная в теле f), которую можно разделить на две отдельные переменные.

let f x0 x1 =
  let pair = x0, x1 in
  Printf.printf "foo\n";
  fun y ->
    fst pair + snd pair + y

После некоторых упрощений получаем:

let f x0 x1 =
  let pair_0 = x0 in
  let pair_1 = x1 in
  Printf.printf "foo\n";
  fun y ->
    pair_0 + pair_1 + y

и затем:

let f x0 x1 =
  Printf.printf "foo\n";
  fun y ->
    x0 + x1 + y

Выделение памяти для пары было устранено.

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

21.9.2 Разыменование специализированных аргументов

Это преобразование включено, если не указан параметр -no-unbox-specialised-args.

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

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

Пример:

Получив данный код, компилятор внедрит loop в f, а затем заметит, что inv является неизменным и всегда представляет пару, образованную добавлением 42 и 43 к аргументу x функции f.

let rec loop inv xs =
  match xs with
  | [] -> fst inv + snd inv
  | x::xs -> x + loop2 xs inv
and loop2 ys inv =
  match ys with
  | [] -> 4
  | y::ys -> y - loop inv ys

let f x =
  Printf.printf "%d\n" (loop (x + 42, x + 43) [1; 2; 3])

После некоторых упрощений получаем:

let f x =
  let rec loop' xs inv_0 inv_1 =
    match xs with
    | [] -> inv_0 + inv_1
    | x::xs -> x + loop2' xs inv_0 inv_1
  and loop2' ys inv_0 inv_1 =
    match ys with
    | [] -> 4
    | y::ys -> y - loop' ys inv_0 inv_1
  in
  Printf.printf "%d\n" (loop' [1; 2; 3] (x + 42) (x + 43))

Выделение памяти для пары в f было удалено. (Поскольку два замыкания для loop’ и loop2’ являются константами, они также будут подняты до верхнего уровня без накладных расходов на выделение памяти во время выполнения. Это также произошло бы без выполнения преобразования разыменования специализированных аргументов.)

Преобразование разыменования специализированных аргументов никогда не приводит к дополнительным выделениям памяти.

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

Преобразование реализуется путем создания оберточной функции, принимающей исходные аргументы. При этом исходная функция переименовывается, и добавляются дополнительные аргументы, соответствующие разыменованным специализированным аргументам; эта новая функция вызывается из обертки. Затем обертка будет встроенной в местах прямых вызовов. Действительно, все места вызовов будут прямыми, если не используется -unbox-closures, поскольку они были сгенерированы компилятором при первоначальной специализации функции. (В случае -unbox-closures могут появиться другие функции со специализированными аргументами; в этом случае может быть косвенные вызовы, и это приведет к небольшим затратам, поскольку придется прыгать через оберточную функцию. Прием прямых вызовов-заменителей, используемый для -unbox-closures, не используется преобразованием разыменования специализированных аргументов.)

21.9.3 Разыменование замыканий

Это преобразование по умолчанию выключено. Его можно включить, используя флаг -unbox-closures.

Преобразование заменяет переменные замыкания специализированными аргументами. Цель состоит в том, чтобы заставить больше замыканий стать закрытыми. Это особенно применимо в качестве средства уменьшения выделения памяти, когда рассматриваемую функцию нельзя встроить или специализировать. Например, некоторая нерекурсивная функция может быть слишком большой для встраивания; или некоторая рекурсивная функция может не предлагать возможностей специализации, возможно, потому, что ее единственный аргумент имеет тип unit.

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

Простой пример:

В приведенном ниже коде (который обычно возникает, когда g слишком велика для встраивания) значение x обычно передается в применение функции + через замыкание g.

let f x =
  let g y =
    x + y
  in
  (g [@inlined never]) 42

Разыменование замыкания приводит к тому, что значение для x внутри g передается как аргумент в g, а не через его замыкание. Это означает, что замыкание g становится константой и может быть поднято до верхнего уровня, устраняя выделение памяти во время выполнения.

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

Добавление такой обертки нанесет штраф за косвенные вызовы функции (которые могут существовать в произвольных местах; помните, что эта трансформация, например, не применяется только к функциям, сгенерированным компилятором в результате специализации), так как такие вызовы будут проходить через обертывающую функцию. Для смягчения этого, если функция достаточно мала по сравнению с количеством удаляемых свободных переменных, она будет дублироваться трансформациями, чтобы получить две версии: исходную (используемую для косвенных вызовов, так как мы не можем сделать лучше) и пару обертка/переписанная функция, как описано в предыдущем абзаце. Пара обертка/переписанная функция будет использоваться только в местах непосредственного вызова функции. (В этом случае обертка известна как субъект непосредственного вызова, так как она занимает место другой функции — неизмененной версии, используемой для косвенных вызовов — в местах непосредственного вызова.)

Флаг командной строки -unbox-closures-factor, принимающий целое число, может использоваться для корректировки точки, в которой функция считается достаточно большой, чтобы не подлежать дублированию. Преимущество дублирования масштабируется целым числом перед оценкой относительно размера.

Более сложный пример:

В следующем коде есть две переменные замыкания, которые обычно вызывают выделение памяти для замыканий. Одна называется fv и встречается внутри функции baz; другая называется z и встречается внутри функции bar. В этом игрушечном (но сложнейшем) примере мы снова используем атрибут для имитации типичной ситуации, когда первый аргумент функции baz слишком велик для встраивания.

let foo c =
  let rec bar zs fv =
    match zs with
    | [] -> []
    | z::zs ->
      let rec baz f = function
        | [] -> []
        | a::l -> let r = fv + ((f [@inlined never]) a) in r :: baz f l
      in
      (map2 (fun y -> z + y) [z; 2; 3; 4]) @ bar zs fv
  in
  Printf.printf "%d" (List.length (bar [1; 2; 3; 4] c))

Код, полученный в результате применения -O3 -unbox-closures к этому коду, передает свободные переменные через аргументы функций, чтобы устранить все выделение памяти для замыканий в этом примере (кроме тех, которые могут выполняться внутри printf).

21.10 Удаление неиспользуемого кода и значений

21.10.1 Удаление избыточных выражений let

Этап упрощения удаляет неиспользуемые связывания let, если соответствующие выражения определения не имеют «никаких эффектов». См. раздел «Обработка эффектов» ниже для точного определения этого термина.

21.10.2 Удаление избыточных конструкций программы

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

21.10.3 Удаление неиспользуемых аргументов

Эта трансформация по умолчанию включена только для специализированных аргументов. Она может быть включена для всех аргументов с помощью флага -remove-unused-arguments.

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

21.10.4 Удаление неиспользуемых переменных замыканий

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

21.11 Другие трансформации кода

21.11.1 Преобразование неэскэпирующих ссылок в переменные

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

21.11.2 Подстановка переменных замыканий для специализированных аргументов

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

21.12 Обработка эффектов

Оптимизаторы Flambda классифицируют выражения, чтобы определить, может ли выражение:

• не нуждаться в вычислении вообще; и/или
• может быть продублировано.

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

Эффекты классифицируются следующим образом:

Без эффектов:

Выражение не изменяет наблюдаемого состояния мира. Например, оно не должно записывать в любую изменяемую область памяти, вызывать произвольные внешние функции или изменять поток управления (например, путем повышения исключения). Обратите внимание, что выделение не считается «без эффектов» (см. ниже).

• Предполагается в компиляторе, что выражения без эффектов, результаты которых не используются, могут быть устранены. (Это обычно происходит, когда выражение является определяющим выражением let; в таких случаях выражение let будет устранено.) Кроме того, предполагается, что такие выражения без эффектов могут быть продублированы (и, следовательно, возможно, выполнены более одного раза).
• Исключения, возникающие из точек выделения памяти, например, «недостаточно памяти», или исключения, распространяемые от финализаторов или обработчиков сигналов, рассматриваются как «эффекты из ниоткуда» и, таким образом, игнорируются для нашего определения здесь эффектов. То же самое касается операций с плавающей точкой, которые могут вызывать аппаратные ловушки на некоторых платформах.

Только генеративные эффекты:

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

Произвольные эффекты:

Все остальные выражения.

Существует одна классификация для сопутствующих эффектов:

Без сопутствующих эффектов:

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

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

21.13 Компиляция статически размещенных модулей

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

21.14 Ингибирование оптимизации

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

21.15 Использование небезопасных операций

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

В частности, запрещается изменять любое значение (например, с помощью Obj.set_field или Obj.set_tag), которое не является изменяемым. (Значения, возвращаемые из C-заглушек, всегда обрабатываются как изменяемые.) Компилятор выдаст предупреждение 59, если обнаружит такую запись — но не может предупредить во всех случаях. Вот пример кода, который вызовет предупреждение:

let f x =
  let a = 42, x in
  (Obj.magic a : int ref) := 1;
  fst a

Причина, по которой это небезопасно, заключается в том, что этап упрощения считает, что fst a содержит значение 42; и на самом деле оно должно, если целостность типов не была нарушена небезопасными операциями.

Если необходимо написать код, который вызовет предупреждение 59, но известно, что код на самом деле корректен (при некотором определении корректности), то Sys.opaque_identity можно использовать для обертывания значения перед выполнением небезопасных операций. Необходимо проявлять особую осторожность, чтобы обеспечить добавление непрозрачности в нужном месте. Необходимо подчеркнуть, что это использование Sys.opaque_identity предназначено только для исключительных случаев. Его не следует использовать в обычном коде или для попытки направить оптимизатор.

В качестве примера, этот код вернёт целое число 1:

let f x =
  let a = Sys.opaque_identity (42, x) in
  (Obj.magic a : int ref) := 1;
  fst a

Однако следующий код всё равно вернёт 42:

let f x =
  let a = 42, x in
  Sys.opaque_identity (Obj.magic a : int ref) := 1;
  fst a

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

21.16 Глоссарий

В этой главе руководства используется следующая терминология.

Место вызова

См. прямое место вызова и косвенное место вызова ниже.

Закрытая функция

Функция, тело которой не имеет свободных переменных, кроме своих параметров и любых переменных, которые связаны другими функциями в том же (возможно, взаимно-рекурсивном) объявлении.

Замыкание

Представление функции в среде выполнения. Оно включает указатели на код функции вместе со значениями любых переменных, используемых в теле функции, но фактически определённых вне функции, в области видимости внешнего уровня. Значения таких переменных, коллективно известных как окружение, необходимы, потому что функция может быть вызвана из места, где исходные привязки таких переменных больше не находятся в области видимости. Группа возможно взаимно-рекурсивных функций, определённых с помощью let rec, все делят одно замыкание. (Примечание для разработчиков: в исходном коде Flambda замыкание всегда соответствует одной функции; набор замыканий относится к группе таких.)

Переменная замыкания

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

Константа

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

Замыкание-константа

Замыкание, которое статически выделяется в объектном файле. Почти всегда часть окружения такого замыкания пуста.

Определяющее выражение

Выражение e в let x = e in e’.

Прямое место вызова

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

Косвенное место вызова

Место в коде программы, где вызывается функция, но не известно, что это прямое место вызова.

Программа

Совокупность связываний символов, формирующих определение единицы компиляции (т.е. файла .cmx).

Специализированный аргумент

Аргумент функции, который известно, что всегда содержит определённое значение во время выполнения. Они вводятся инлайнером при специализации рекурсивных функций; и проходом unbox-closures. (См. раздел 21.4.)

Символ

Имя, ссылающееся на определённое место в объектном файле или исполняемом изображении. В этом месте будет храниться некоторое постоянное значение. К символам можно обратиться с помощью инструментов, специфичных для операционной системы (например, objdump в Linux).

Связывание символов

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

Топ-уровень

Выражение в текущей программе, которое не заключено в объявление функции.

Переменная

Имя сущности, к которой некоторое значение OCaml привязано выражением let, конструкцией сопоставления с образцом или подобным.