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

Межпроцедурная оптимизация ( 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 и Fortran ), а не все сразу (например, Java «S точно в срок компиляция (JIT)).

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

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

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

Пример [ править ]

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

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

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

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

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

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

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

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

написать ( 7 ) ; написать ( - 1 ) ; написать ( - 6 ) ;

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

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

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

написать ( 5 ) ;  {Not -6}

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

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

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

В общем [ править ]

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

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

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

История [ править ]

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

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

Флаги и реализация [ править ]

Unix-подобный [ править ]

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

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

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

Варианты без LTO [ править ]

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

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

Другое [ править ]

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

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

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

См. Также [ править ]

• Оптимизация по профилю (PGO)
• Единый блок компиляции

Ссылки [ править ]

Внешние ссылки [ править ]

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