Межпроцедурная оптимизация (IPO ) представляет собой набор методы компилятора, используемые в компьютерном программировании для повышения производительности в программах, содержащих множество часто используемых функций малой или средней длины. IPO отличается от других оптимизаций компилятора тем, что анализирует всю программу; другие оптимизации рассматривают только одну функцию или даже один блок кода.
IPO направлено на сокращение или устранение дублирующих вычислений, неэффективное использование памяти и упрощение итерационных последовательностей, таких как циклы. Если в цикле происходит вызов другой подпрограммы, анализ IPO может определить, что лучше всего встроить в это. Кроме того, IPO может переупорядочивать подпрограммы для лучшей компоновки памяти, а locality.
IPO также может включать типичные оптимизации компилятора на уровне всей программы, например устранение мертвого кода (DCE), который удаляет код, который никогда не выполняется. Для этого компилятор проверяет ветки, которые никогда не выполняются, и удаляет код в этой ветке. IPO также пытается обеспечить лучшее использование констант. Современные компиляторы предлагают IPO в качестве опции во время компиляции. Фактический процесс IPO может происходить на любом этапе между понятным человеком исходным кодом и созданием готовой исполняемой двоичной программы.
Для языков, которые компилируются пофайлово, эффективное IPO для единиц перевода (файлов модулей) требует знания «точек входа» программы, так что оптимизация всей программы (WPO ) можно запустить. Во многих случаях это реализуется как проход оптимизации времени компоновки (LTO ), потому что вся программа видна компоновщику.
Целью любой оптимизации скорости является получение программы бежать как можно быстрее; проблема в том, что компилятор не может правильно проанализировать программу и определить, что она будет делать, не говоря уже о том, что программист намеревался делать. Напротив, люди-программисты начинают с другой стороны с целью и пытаются создать программу, которая ее достигнет, желательно без особых размышлений в процессе.
По разным причинам, включая удобочитаемость, программы часто разбиваются на несколько процедур, которые обрабатывают несколько общих случаев. Однако универсальность каждой процедуры может привести к потере усилий при конкретном использовании. Межпроцедурная оптимизация представляет собой попытку сократить эти потери.
Предположим, существует процедура, которая оценивает F (x), и код запрашивает результат F (6), а затем снова F (6). В этой второй оценке почти наверняка нет необходимости: вместо этого результат можно было бы сохранить и использовать позже, если предположить, что F является чистой функцией. Эта простая оптимизация срывается в тот момент, когда реализация F (x) становится нечистой; то есть его выполнение включает ссылку на параметры, отличные от явного аргумента 6, которые были изменены между вызовами, или побочные эффекты, такие как печать некоторого сообщения в журнале, подсчет количества оценок, накопление CPU время, подготовка внутренних таблиц для облегчения последующих вызовов связанных параметров и т. д. Утрата этих побочных эффектов из-за отсутствия оценки во второй раз может быть приемлемой, а может и нет.
В более общем плане, помимо оптимизации, вторая причина использования процедур - избежать дублирования кода, который будет давать одинаковые или почти одинаковые результаты при каждом выполнении процедуры. Таким образом, общий подход к оптимизации состоит в том, чтобы обратить это вспять: некоторые или все вызовы определенной процедуры заменяются соответствующим кодом с соответствующей заменой параметров. Затем компилятор попытается оптимизировать результат.
Оптимизация всей программы (WPO ) - это оптимизация компилятора программы с использованием информации обо всех модулях в программе. Обычно оптимизации выполняются на на каждый модуль, "компиленд", на основе ; но этот подход, хотя его проще писать и тестировать и требует меньше ресурсов во время самой компиляции, не позволяет быть уверенным в безопасности ряда оптимизаций, таких как агрессивное встраивание, и, следовательно, не может их выполнить, даже если они фактически окажется повышением эффективности, которое не меняет семантику испускаемого объектного кода.
Оптимизация времени связывания (LTO ) - это тип оптимизации программы, выполняемой компилятором для программы во время времени связывания. Оптимизация времени компоновки актуальна для языков программирования, которые компилируют программы для каждого файла, а затем связывают эти файлы вместе (например, C и Fortran ), а не все и один раз (например, Java JIT-компиляция (JIT)).
После того, как все файлы были скомпилированы отдельно в объектные файлы, обычно компилятор связывает (объединяет) объектные файлы в один файл, исполняемый файл. Однако в LTO, реализованном с помощью GNU Compiler Collection (GCC) или LLVM, компилятор может выгружать свое промежуточное представление (GIMPLE байт-код или бит-код LLVM) на диск, так что все различные единицы компиляции, которые будут составлять один исполняемый файл, могут быть оптимизированы как один модуль, когда, наконец, произойдет связь. Это расширяет объем межпроцедурных оптимизаций, чтобы охватить всю программу (или, скорее, все, что видно во время компоновки). Благодаря оптимизации времени компоновки компилятор может применять различные формы межпроцедурной оптимизации ко всей программе, обеспечивая более глубокий анализ, большую оптимизацию и, в конечном итоге, лучшую производительность программы.
На практике LTO не всегда оптимизирует всю программу - библиотечные функции, особенно динамически связанные общие объекты, намеренно не используются, чтобы избежать чрезмерного дублирования и разрешить обновление. Статическая компоновка естественным образом соответствует концепции LTO, но она работает только с архивами библиотек, которые содержат объекты IR, а не с объектными файлами только с машинным кодом. Из-за проблем с производительностью не всегда напрямую используется даже весь модуль - программа может быть разбита на разделы в стиле LTO типа «разделяй и властвуй», например WHOPR GCC. И, конечно же, когда создаваемая программа сама по себе является библиотекой, оптимизация сохранит каждый доступный извне (экспортируемый) символ, не пытаясь слишком сильно удалить их как часть DCE.
Гораздо более ограниченный форма WPO все еще возможна без LTO, что подтверждается переключателем GCC -fwhole-program
. Этот режим заставляет GCC предполагать, что компилируемый модуль содержит точку входа (обычно main ()
) всей программы, так что все остальные функции в нем не используются извне и могут быть безопасно оптимизированы. Поскольку он применим только к одному модулю, он не может полностью охватить всю программу. (Его можно комбинировать с LTO в смысле одного большого модуля, что полезно, когда компоновщик не передает обратно в GCC, какие точки входа или символы используются извне.)
Пример программы ; целое число b; {Переменная "глобальная" для процедуры Silly.} Процедура Silly (a, x), если 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, и т.д.), его код плюс все вызовы могут быть полностью оптимизированы, оставляя значение undefined (что не имеет значения), так что остаются только операторы печати, и они для постоянных значений.
Если вместо этого параметры передаются по ссылке, то действие над ними в 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; а: = - 6; написать (7); {b не упоминается, поэтому это использование остается "чистым".} x: = - 1; написать (-1); {указан b...} b: = - 6; написать (-6); {b модифицируется посредством его проявления параметра.}
И поскольку присвоения a, b и x ничего не передают внешнему миру - они не появляются в операторах вывода, ни как ввод для последующих вычислений (результаты которых, в свою очередь, приводят к выводу, иначе они тоже не нужны) - в этом коде тоже нет смысла, поэтому результат
write (7); написать (-1); написать (-6);
Вариантный метод передачи параметров, которые кажутся «по ссылке», - это копирование в, копирование и выход, при этом процедура работает с локальной копией параметров, значения которых копируются обратно в оригиналы. при выходе из процедуры. Если процедура имеет доступ к одному и тому же параметру, но разными способами, как при вызовах, таких как Silly (a, a) или Silly (a, b), могут возникнуть расхождения. Итак, если параметры были переданы путем копирования-в-копирования в порядке слева направо, то Silly (b, b) расширился бы до
p1: = b; p2: = b; {Копировать. Локальные переменные p1 и p2 равны.} 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), в то время как более сложные константы могут храниться в памяти с пометкой только для чтения с любой попыткой их изменения, приводящей к немедленному завершению программы и т. д.
Этот пример чрезвычайно прост, хотя сложности уже очевидны. Скорее всего, это будет случай многих процедур, имеющих множество выводимых или объявленных программистом свойств, которые могут позволить оптимизации компилятора найти некоторые преимущества. Любой параметр процедуры может быть доступен только для чтения, может быть записан, может быть как для чтения, так и для записи или может быть полностью проигнорирован, что может привести к появлению таких возможностей, как константы, не нуждающиеся в защите с помощью временных переменных, но то, что происходит при любом данном вызове, может зависеть от сложная сеть соображений. Другие процедуры, особенно процедуры, подобные функциям, будут иметь определенное поведение, которое при определенных вызовах может позволить избежать некоторой работы: например, Гамма-функция, если вызывается с целочисленным параметром, может быть преобразована в вычисление. с целочисленными факториалами.
Некоторые компьютерные языки разрешают (или даже требуют) утверждения относительно использования параметров и могут дополнительно предлагать возможность объявить, что значения переменных ограничены некоторым набором (например, 6 < x ≤ 28) thus providing further grist for the optimisation process to grind through, and also providing worthwhile checks on the coherence of the source code to detect blunders. But this is never enough - only some variables can be given simple constraints, while others would require complex specifications: how might it be specified that variable P is to be a prime number, and if so, is or is not the value 1 included? Complications are immediate: what are the valid ranges for a day-of-month D given that M is a month number? And are all violations worthy of immediate termination? Even if all that could be handled, what benefit might follow? And at what cost? Full specifications would amount to a re-statement of the program's function in another form and quite aside from the time the compiler would consume in processing them, they would thus be subject to bugs. Instead, only simple specifications are allowed with run-time range checking provided.
В случаях где программа не считывает ввод (как в примере), можно представить, что анализ компилятора переносится вперед, так что результатом будет не более чем серия операторов печати или, возможно, некие циклы, которые целесообразно генерируют такие значения. Узнает ли он тогда программа для генерации простых чисел и преобразования в наиболее известный метод для этого или предоставления вместо этого ссылки на библиотеку? Маловероятно! Как правило, возникают произвольно сложные соображения (Entscheidungsproblem ), чтобы исключить это, и нет другого выхода, кроме как запускать код только с ограниченными улучшениями.
Для процедурных языков или языков, подобных ALGOL, появляется межпроцедурный анализ и оптимизация вступить в коммерческую практику в е в начале 1970-х. Оптимизирующий компилятор IBM PL / I выполнил межпроцедурный анализ, чтобы понять побочные эффекты как вызовов процедур, так и исключений (приведенных в терминах PL / I как «на условиях») и в статьях Фрэн Аллен. Работа над компиляцией языка программирования APL была по необходимости межпроцедурной.
Методы межпроцедурного анализа и оптимизации были предметом научных исследований в 1980-х и 1990-х годах. Они вновь появились в мире коммерческих компиляторов в начале 1990-х годов с компиляторами как от Convex («Компилятор приложений» для Convex C4 ), так и от Ardent (компилятор для Пламенный Титан ). Эти компиляторы продемонстрировали, что технологии могут быть сделаны достаточно быстрыми, чтобы их можно было использовать в коммерческом компиляторе; впоследствии межпроцедурные методы появились в ряде коммерческих и некоммерческих систем.
Коллекция компиляторов GNU имеет функцию встраивания на всех уровнях оптимизации. В -O1
это применимо только к тем, которые вызываются только один раз (-finline-functions-once
), в -O2
это ограничение ослаблено (- finline-функции
). По умолчанию это поведение только для одного файла, но при оптимизации времени компоновки -flto
оно становится всей программой. Интерфейс командной строки Clang аналогичен интерфейсу GCC, за исключением отсутствия опции -fwhole-program
.
Объектные файлы, созданные LTO, содержат зависящее от компилятора промежуточное представление (IR), которое интерпретируется во время ссылки. Чтобы убедиться, что это хорошо работает с статическими библиотеками, новые компоновщики GNU имеют интерфейс «подключаемого модуля компоновщика», который позволяет компилятору при необходимости преобразовывать объектные файлы в форму машинного кода. Этот плагин также помогает управлять процессом LTO в целом. В качестве альтернативы можно создать объект «толстого LTO», содержащий как машинный код, так и IR, но для этого потребуется больше места.
Поскольку и GCC, и LLVM (clang) могут создавать IR из различных программ языков, IPO во время компоновки может происходить даже за пределами языковых границ. Чаще всего это демонстрируется на C и C ++, но LLVM делает это возможным для Rust и всех других компиляторов на основе LLVM.
GCC и Clang выполняет IPO по умолчанию на уровне оптимизации 2. Однако степень оптимизации ограничена, когда LTO отключен, поскольку IPO может происходить только в объектном файле, а не статические функции никогда не могут быть устранены. У последней проблемы есть решение, отличное от LTO: переключатель -fwhole-program
может использоваться для предположения, что только main ()
нестатичен, то есть виден снаружи.
Другой метод, не связанный с LTO, - это «функциональные разделы» (-ffunction-section
в GCC и Clang). Помещая каждую функцию в отдельный раздел объектного файла, компоновщик может выполнять удаление мертвого кода без IR, удаляя разделы, на которые нет ссылок (--gc-section
). Аналогичный вариант доступен для переменных, но он приводит к созданию гораздо худшего кода.
Компиляторы Intel C / C ++ допускают IPO целой программы. Флаг для включения межпроцедурной оптимизации для одного файла - -ip
, флаг для включения межпроцедурной оптимизации для всех файлов в программе - -ipo
.
Компилятор MSVC, интегрированный в Visual Studio, также поддерживает межпроцедурную оптимизацию для всей программы.
Независимый от компилятора интерфейс для включения межпроцедурной оптимизации всей программы осуществляется через свойство INTERPROCEDURAL_OPTIMIZATION
в CMake.