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

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

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

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

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

Анализ

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

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

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

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

WPO и LTO

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

Оптимизация времени компоновки (LTO) - это тип оптимизации программы, выполняемый компилятором для программы на время ссылки. Оптимизация времени компоновки актуальна для языков программирования, которые компилируют программы для каждого файла, а затем связывают эти файлы вместе (например, C и Фортран ), а не все сразу (например, Ява с своевременная компиляция (JIT)).

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

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

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

Пример

  Программа пример;   целое число б;              {Переменная "глобальная" для процедуры глупо.}   Процедура Глупый(а,Икс)    если Икс < 0 тогда а:=Икс + б еще а:=-6;   Конец Глупый;              {Ссылка на b, а не на параметр, делает Silly "нечистым" в целом.}   целое число а,Икс;            {Эти переменные видны Глупому, только если параметры.}   Икс:=7; б:=5;   Глупый(а,Икс); записывать(Икс);   Глупый(Икс,а); записывать(Икс);   Глупый(б,б); записывать(б);  Конец пример;

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

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

  Икс:=7; б:=5;  если Икс < 0 тогда а:=Икс + б еще а:=-6; записывать(Икс);   {a изменено.}  если а < 0 тогда Икс:=а + б еще Икс:=-6; записывать(Икс);   {Поскольку параметры меняются местами.}  если б < 0 тогда б:=б + б еще б:=-6; записывать(б);   {Две версии переменной b в Silly плюс глобальное использование.}

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

  Икс:=7; б:=5;  а:=-6; записывать(7);            {b не упоминается, поэтому это использование остается "чистым".}  Икс:=-1; записывать(-1);           {b указан ...}  б:=-6; записывать(-6);           {b модифицируется с помощью своего параметра.}

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

  записывать(7);  записывать(-1);  записывать(-6);

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

 p1:=б; p2:=б;                               {Скопируйте. Локальные переменные p1 и p2 равны.} если p2 < 0 тогда p1:=p2 + б еще p1:=-6;      {Таким образом, p1 может больше не равняться p2.} б:=p1; б:=p2;                               {Скопируйте. В порядке слева направо перезаписывается значение p1.}

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

 записывать(5);          {Не -6}

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

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

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

В целом

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

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

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

История

Для процедурных или АЛГОЛ Подобно языкам, межпроцедурный анализ и оптимизация, похоже, вошли в коммерческую практику в начале 1970-х годов. IBM PL / I Оптимизирующий компилятор провел межпроцедурный анализ, чтобы понять побочные эффекты как вызовов процедур, так и исключений (приведение в терминах PL / I как «при условиях»)[3] и в статьях Фрэн Аллен.[4][5] Работа над составлением APL язык программирования по необходимости был межпроцедурным.[6][7]

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

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

Unix-подобный

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

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

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

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

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

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

Другой

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

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

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

Смотрите также

Рекомендации

  1. ^ а б c d е «Параметры оптимизации». Использование коллекции компиляторов GNU (GCC). Оптимизация времени компоновки не требует присутствия всей программы для работы. Если программа не требует экспорта каких-либо символов, можно комбинировать -flto и -fwhole-program, чтобы позволить межпроцедурным оптимизаторам использовать более агрессивные предположения, что может привести к улучшенным возможностям оптимизации. Использование -fwhole-program не требуется, когда подключаемый модуль компоновщика активен (см. -Fuse-linker-plugin).
  2. ^ «Обзор LTO». GNU Compiler Collection (GCC) Внутреннее устройство.
  3. ^ Томас С. Спиллман, "Выявление побочных эффектов в оптимизирующем компиляторе PL / I", в Труды ИФИПС 1971 г., North-Holland Publishing Company, страницы 376-381.
  4. ^ Фрэнсис Э. Аллен, "Анализ межпроцедурного потока данных", Протоколы IFIPS, 1974.
  5. ^ Фрэнсис Э. Аллен и Джек Шварц, «Определение взаимосвязей потоков данных в наборе процедур», отчет IBM Research Report RC 4989, август 1974 г.
  6. ^ Филип Абрамс, «Машина APL», факультет компьютерных наук Стэнфордского университета, отчет STAN-CS-70-158, февраль 1970 г.
  7. ^ Терренс С. Миллер, "Предварительная компиляция: проект для компилятора APL", доктор философии. Диссертация, Йельский университет, 1978.
  8. ^ "Ссылка на аргумент командной строки Clang". Документация Clang 11.
  9. ^ Рейнхарт, Джонатан. "Может ли LTO для gcc или clang оптимизировать методы C и C ++". Переполнение стека.
  10. ^ Woerister, Майкл. «Устранение разрыва: межъязыковое LTO между Rust и C / C ++». Блог разработчиков LLVM.
  11. ^ «Параметры оптимизации». Использование коллекции компиляторов GNU (GCC).
  12. ^ «Функциональные разделы». elinux.org.
  13. ^ «Документация по компилятору Intel 8». Архивировано из оригинал 21 сентября 2006 г.. Получено 2007-02-13.
  14. ^ Intel Visual Fortran Compiler 9.1, выпуски Standard и Professional, для Windows * - Intel Software Network
  15. ^ "/ GL (Оптимизация всей программы)". Документы Microsoft. 2019-03-12. Получено 2020-01-26.
  16. ^ "INTERPROCEDURAL_OPTIMIZATION". CMake 3.17.2 Документация.

внешняя ссылка