Межпроцедурная оптимизация

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

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

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

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

Анализ

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

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

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

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

ВПО и ДН

Полная оптимизация программы ( WPO ) — это оптимизация программы компилятором с использованием информации обо всех модулях программы. Обычно оптимизация выполняется для каждого модуля, «компилятора», на основе ; но этот подход, хотя его легче писать и тестировать и он менее требовательн к ресурсам во время самой компиляции, он не позволяет быть уверенным в безопасности ряда оптимизаций, таких как агрессивная встраивание , и, следовательно, не может их выполнить, даже если они на самом деле окажутся прирост эффективности, который не меняет семантику создаваемого объектного кода.

Оптимизация времени компоновки ( LTO ) — это тип оптимизации программы, выполняемой компилятором программы во время компоновки . Оптимизация времени компоновки актуальна в языках программирования, которые компилируют программы пофайлово, а затем связывают эти файлы вместе (например, C и Fortran ), а не все сразу (например Java в , компиляция (JIT)).

После того как все файлы скомпилированы по отдельности в объектные файлы , традиционно компилятор связывает (объединяет) объектные файлы в один исполняемый файл . Однако в LTO, реализованном коллекцией компиляторов GNU (GCC) и LLVM , компилятор может выгружать свое промежуточное представление (IR), то есть байт-код GIMPLE или бит-код LLVM, соответственно, так что все различные единицы компиляции, которые будут отправлены в Создание одного исполняемого файла может быть оптимизировано как один модуль, когда ссылка наконец произойдет. Это расширяет возможности межпроцедурной оптимизации, охватывая всю программу (или, скорее, все, что видно во время компоновки). Благодаря оптимизации времени компоновки компилятор может применять различные формы межпроцедурной оптимизации ко всей программе, что позволяет провести более глубокий анализ, большую оптимизацию и, в конечном итоге, повысить производительность программы.

На практике LTO не всегда оптимизирует всю программу — библиотечные функции , особенно динамически связанные общие объекты, намеренно исключены, чтобы избежать чрезмерного дублирования и обеспечить возможность обновления. Статическое связывание, естественно, соответствует концепции LTO, но оно работает только с библиотечными архивами, содержащими IR-объекты, а не с объектными файлами, содержащими только машинный код. Из-за проблем с производительностью даже не весь модуль всегда используется напрямую — программа может быть разделена по принципу LTO в стиле «разделяй и властвуй», например, WHOPR GCC. И, конечно же, когда создаваемая программа сама является библиотекой, оптимизация сохранит каждый доступный извне (экспортированный) символ, не пытаясь слишком усердно удалить их как часть DCE.

Гораздо более ограниченная форма WPO все еще возможна без LTO, примером чему является GCC. -fwhole-program выключатель. Этот режим заставляет GCC предполагать, что компилируемый модуль содержит точку входа всей программы, так что все остальные функции в нем не используются извне и могут быть безопасно оптимизированы. Поскольку это применимо только к одному модулю, оно не может по-настоящему охватить всю программу. Его можно комбинировать с LTO в смысле одного большого модуля, что полезно, когда компоновщик не сообщает GCC о том, какие точки входа или символы используются извне.

Пример

Program example;
   integer b;              {A variable "global" to the procedure Silly.}
   Procedure Silly(a,x)
      if x < 0 then a:=x + b else a:=-6;
   End Silly;              {Reference to b, not a parameter, makes Silly "impure" in general.}
   integer a,x;            {These variables are visible to Silly only if parameters.}
   x:=7; b:=5;
   Silly(a,x); write(x);
   Silly(x,a); write(x);
   Silly(b,b); write(b);
End example;

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

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

x:=7; b:=5;
if x < 0 then a:=x + b else a:=-6; write(x);   {a is changed.}
if a < 0 then x:=a + b else x:=-6; write(x);   {Because the parameters are swapped.}
if b < 0 then b:=b + b else b:=-6; write(b);   {Two versions of variable b in Silly, plus the global usage.}

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

x:=7; b:=5;
a:=-6; write(7);            {b is not referenced, so this usage remains "pure".}
x:=-1; write(-1);           {b is referenced...}
b:=-6; write(-6);           {b is modified via its parameter manifestation.}

А поскольку присвоения a , b и x ничего не передают внешнему миру - они не появляются ни в выходных операторах, ни в качестве входных данных для последующих вычислений (результаты которых, в свою очередь, приводят к выходным данным, иначе они также не нужны) - существует в этом коде тоже нет смысла, и поэтому результат

write(7);
write(-1);
write(-6);

Вариантным методом передачи параметров, которые выглядят как «по ссылке», является копирование-вход-копирование , при котором процедура работает с локальной копией параметров, значения которых копируются обратно в оригиналы при выходе из процедуры. Если процедура имеет доступ к одному и тому же параметру, но разными способами, как при вызовах, таких как Silly(a,a) или Silly(a,b) , могут возникнуть несоответствия. Итак, если бы параметры передавались путем копирования и копирования в порядке слева направо, то Silly(b,b) расширился бы до

p1:=b; p2:=b;                               {Copy in. Local variables p1 and p2 are equal.}
if p2 < 0 then p1:=p2 + b else p1:=-6;      {Thus p1 may no longer equal p2.}
b:=p1; b:=p2;                               {Copy out. In left-to-right order, the value from p1 is overwritten.}

И в этом случае копирование значения p1 (которое было изменено) в b бессмысленно, поскольку оно немедленно перезаписывается значением p2 , значение которого не было изменено внутри процедуры, по сравнению с исходным значением b , и поэтому третье утверждение становится

write(5);          {Not -6}

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

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

Другими словами, тщательно написанная тестовая программа может сообщить, передаются ли параметры по значению или по ссылке, и если используются, то какая схема копирования и копирования. Однако вариации безграничны: простые параметры могут передаваться путем копирования, тогда как большие агрегаты, такие как массивы, могут передаваться по ссылке; простые константы, такие как ноль, могут генерироваться специальными машинными кодами (такими как Clear или LoadZ), в то время как более сложные константы могут храниться в памяти, помеченной как доступная только для чтения, и любая попытка ее изменения приведет к немедленному завершению программы и т. д.

В общем

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

Некоторые компьютерные языки допускают (или даже требуют) утверждения относительно использования параметров и могут дополнительно предлагать возможность объявить, что переменные имеют свои значения, ограниченные некоторым набором (например, 6 < x ≤ 28), тем самым обеспечивая дополнительную основу для процесс оптимизации, а также обеспечение целесообразных проверок связности исходного кода для обнаружения ошибок. Но этого никогда не бывает достаточно — только некоторым переменным можно задать простые ограничения, в то время как другие потребуют сложных спецификаций: как можно указать, что переменная P должна быть простым числом, и если да, включено или нет значение 1? Сразу возникают сложности: каковы допустимые диапазоны для дня месяца D, учитывая, что M — это номер месяца? И все ли нарушения достойны немедленного прекращения? Даже если со всем этим можно справиться, какая от этого будет польза? И какой ценой? Полные спецификации будут означать переформулирование функции программы в другой форме, и, независимо от времени, которое компилятор потратит на их обработку, они, таким образом, будут подвержены ошибкам. Вместо этого допускаются только простые спецификации с проверкой диапазона во время выполнения.

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

История

В процедурных языках, таких как ALGOL , межпроцедурный анализ и оптимизация, похоже, вошли в коммерческую практику в начале 1970-х годов. от IBM Оптимизирующий компилятор PL/I выполнил межпроцедурный анализ, чтобы понять побочные эффекты как вызовов процедур, так и исключений (в терминах PL/I это означает «при условиях»). и в статьях Фрэн Аллен . Работа над компиляцией языка программирования APL обязательно была межпроцедурной.

Методы межпроцедурного анализа и оптимизации были предметом академических исследований в 1980-х и 1990-х годах. Они вновь появились в мире коммерческих компиляторов в начале 1990-х годов с компиляторами как от Convex Computer Corporation («Компилятор приложений» для Convex C4), так и от Ardent (компилятор для Ardent Titan ). Эти компиляторы продемонстрировали, что технологии можно сделать достаточно быстрыми, чтобы их можно было использовать в коммерческом компиляторе; впоследствии межпроцедурные методы появились в ряде коммерческих и некоммерческих систем.

Флаги и реализация

Unix-подобный

Коллекция компиляторов GNU включает встраивание функций на всех уровнях оптимизации. В -O1 это касается только тех, кого вызвали только один раз ( -finline-functions-once), в -O2 это ограничение ослаблено ( -finline-functions). По умолчанию это поведение только для одного файла, но с оптимизацией времени компоновки. -flto это становится целой программой. Интерфейс командной строки Clang аналогичен интерфейсу GCC, за исключением того, что здесь нет -fwhole-program вариант.

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

Поскольку и GCC, и LLVM (clang) способны создавать IR из различных языков программирования, IPO во время компоновки может происходить даже за пределами языковых границ. Чаще всего это демонстрируется на C и C++. но LLVM делает возможным работу с Rust и всеми другими компиляторами на основе LLVM.

Варианты без LTO

GCC и Clang по умолчанию выполняют IPO на уровне оптимизации 2. Однако степень оптимизации ограничена, когда LTO отключен, поскольку IPO может происходить только внутри объектного файла, а нестатические функции невозможно исключить. Последняя проблема имеет решение, отличное от LTO: -fwhole-program переключатель можно использовать, предполагая, что только main() нестатичен, т.е. виден снаружи.

Другой метод, не связанный с LTO, — это «разделы функций» ( -ffunction-sections в GCC и Clang). Помещая каждую функцию в отдельный раздел объектного файла, компоновщик может выполнить удаление мертвого кода без IR, удалив разделы, на которые нет ссылок (используя опцию компоновщика --gc-sections). Аналогичная опция доступна для переменных, но она приводит к созданию гораздо худшего кода.

Другой

Компиляторы Intel C/C++ допускают IPO всей программы. Флаг включения межпроцедурной оптимизации для одного файла: -ip, флаг включения межпроцедурной оптимизации для всех файлов в программе: -ipo.

Компилятор MSVC , интегрированный в Visual Studio, также поддерживает межпроцедурную оптимизацию всей программы.

Независимый от компилятора интерфейс для обеспечения межпроцедурной оптимизации всей программы осуществляется через INTERPROCEDURAL_OPTIMIZATION свойство в CMake .

См. также

• Профильная оптимизация (PGO)
• Единая единица компиляции

Внешние ссылки

• Как заставить компиляторы C/C++ генерировать ужасный код?