Оптимизирующий компилятор - Optimizing compiler

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

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

Из-за этих факторов оптимизация редко дает «оптимальный» результат в каком-либо смысле, и на самом деле «оптимизация» в некоторых случаях может снизить производительность. Скорее, это эвристические методы улучшения использования ресурсов в типичных программах.

Виды оптимизации

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

Оптимизация глазка
Обычно они выполняются в конце процесса компиляции после того, как был сгенерирован машинный код . Эта форма оптимизации исследует несколько смежных инструкций (например, «просмотр кода через глазок»), чтобы увидеть, можно ли их заменить одной инструкцией или более короткой последовательностью инструкций. Например, умножение значения на 2 может быть более эффективно выполнено путем сдвига значения влево или добавления значения к самому себе (этот пример также является примером уменьшения силы ).
Локальные оптимизации
Они рассматривают только информацию, локальную для базового блока . Поскольку в базовых блоках нет потока управления, эти оптимизации требуют очень небольшого анализа, что экономит время и снижает требования к хранилищу, но это также означает, что информация не сохраняется при переходах.
Глобальные оптимизации
Они также называются «внутрипроцедурными методами» и действуют на целые функции. Это дает им больше информации для работы, но часто требует дорогостоящих вычислений. При вызове функций или обращении к глобальным переменным приходится делать предположения в худшем случае, потому что информации о них мало.
Оптимизация цикла
Они действуют на заявлениях , которые составляют цикл, такие как для цикла, например , движение кода петли-инвариантной . Оптимизация циклов может иметь значительное влияние, потому что многие программы проводят большую часть своего времени внутри циклов.
Предварительная оптимизация магазина
Это позволяет операциям хранилища происходить раньше, чем это было бы разрешено в контексте потоков и блокировок. Процессу нужен способ заранее знать, какое значение будет сохранено назначением, которому он должен был следовать. Цель этого ослабления состоит в том, чтобы позволить оптимизации компилятора выполнять определенные виды перестройки кода, которые сохраняют семантику правильно синхронизированных программ.
Межпроцедурная оптимизация, оптимизация всей программы или времени компоновки
Они анализируют весь исходный код программы. Большее количество извлекаемой информации означает, что оптимизации могут быть более эффективными по сравнению с тем, когда они имеют доступ только к локальной информации, то есть в рамках одной функции. Такой вид оптимизации также может позволить использовать новые методы. Например, встраивание функции , когда вызов функции заменяется копией тела функции.
Оптимизация машинного кода и оптимизатор объектного кода
Они анализируют образ исполняемой задачи программы после связывания всего исполняемого машинного кода . Некоторые методы, которые могут применяться в более ограниченном объеме, такие как сжатие макросов, которое экономит пространство за счет сворачивания общих последовательностей инструкций, более эффективны, когда для анализа доступен весь исполняемый образ задачи.

В дополнение к оптимизации с ограниченным объемом есть еще две общие категории оптимизации:

Язык программирования - независимый или зависящий от языка
Большинство языков высокого уровня имеют общие программные конструкции и абстракции: решение (если, переключатель, регистр), цикл (для, пока, повторять .. до, делать .. пока) и инкапсуляция (структуры, объекты). Таким образом, аналогичные методы оптимизации могут использоваться для разных языков. Однако некоторые языковые функции затрудняют некоторые виды оптимизации. Например, наличие указателей в C и C ++ затрудняет оптимизацию доступа к массивам (см. Анализ псевдонимов ). Однако такие языки, как PL / 1 (который также поддерживает указатели), тем не менее, имеют доступные сложные оптимизирующие компиляторы для достижения лучшей производительности различными другими способами. И наоборот, некоторые языковые функции упрощают определенную оптимизацию. Например, в некоторых языках функциям не разрешено иметь побочные эффекты . Следовательно, если программа выполняет несколько вызовов одной и той же функции с одними и теми же аргументами, компилятор может сразу сделать вывод, что результат функции необходимо вычислить только один раз. В языках, где функциям разрешено иметь побочные эффекты, возможна другая стратегия. Оптимизатор может определить, какая функция не имеет побочных эффектов, и ограничить такую ​​оптимизацию функциями без побочных эффектов. Эта оптимизация возможна только тогда, когда оптимизатор имеет доступ к вызываемой функции.
Независимость от машины против зависимости от машины
Многие оптимизации, которые работают с абстрактными концепциями программирования (циклы, объекты, структуры), не зависят от машины, на которую нацелен компилятор, но многие из наиболее эффективных оптимизаций - это те, которые лучше всего используют специальные возможности целевой платформы. Примерами являются инструкции, которые выполняют несколько действий одновременно, например регистр уменьшения и переход, если не равен нулю.

Ниже приведен пример оптимизации, зависящей от локальной машины. Чтобы установить регистр в 0, очевидным способом является использование константы «0» в инструкции, которая устанавливает значение регистра в константу. Менее очевидный способ - выполнить XOR регистра с самим собой. Компилятор должен знать, какой вариант инструкции использовать. На многих RISC- машинах обе инструкции будут одинаково подходящими, поскольку они будут иметь одинаковую длину и занимать одинаковое время. На многих других микропроцессорах, таких как семейство Intel x86 , оказывается, что вариант XOR короче и, вероятно, быстрее, поскольку не будет необходимости ни декодировать непосредственный операнд, ни использовать внутренний «регистр непосредственного операнда». Потенциальная проблема заключается в том, что XOR может ввести зависимость данных от предыдущего значения регистра, вызывая остановку конвейера . Однако процессоры часто имеют XOR регистра с самим собой как особый случай, который не вызывает остановок.

Факторы, влияющие на оптимизацию

Сама машина
Многие варианты оптимизации могут и должны быть выполнены в зависимости от характеристик целевой машины. Иногда можно параметризовать некоторые из этих машинно-зависимых факторов, так что один фрагмент кода компилятора можно использовать для оптимизации различных машин, просто изменяя параметры машинного описания. GCC из проекта GNU и Clang из инфраструктуры компилятора LLVM являются примерами оптимизирующих компиляторов, которые следуют этому подходу.
Архитектура целевого процессора
Количество регистров ЦП : в определенной степени, чем больше регистров, тем легче оптимизировать производительность. Локальные переменные можно размещать в регистрах, а не в стеке . Временные / промежуточные результаты можно оставить в регистрах без записи и чтения из памяти.
  • RISC против CISC : наборы инструкций CISC часто имеют переменную длину инструкций, часто имеют большее количество возможных инструкций, которые можно использовать, и каждая инструкция может занимать разное количество времени. Наборы инструкций RISC пытаются ограничить вариативность в каждом из них: наборы инструкций обычно имеют постоянную длину, за некоторыми исключениями, обычно меньше комбинаций регистров и операций с памятью, а также скорость выдачи инструкций (количество инструкций, выполненных за период времени, обычно является целым числом, кратным тактовому циклу) обычно является постоянным в случаях, когда задержка памяти не является фактором. Может быть несколько способов выполнения определенной задачи, при этом CISC обычно предлагает больше альтернатив, чем RISC. Компиляторы должны знать относительную стоимость различных инструкций и выбирать наилучшую последовательность инструкций (см. Выбор инструкций ).
  • Конвейеры : конвейер - это, по сути, ЦП, разбитый на сборочную линию . Он позволяет использовать части ЦП для разных инструкций, разбивая выполнение инструкций на различные этапы: декодирование инструкций, декодирование адреса, выборка из памяти, выборка из регистров, вычисление, хранение регистров и т. Д. Одна инструкция может находиться на этапе хранения регистров. , в то время как другой может находиться на этапе выборки регистра. Конфликты конвейера возникают, когда инструкция на одном этапе конвейера зависит от результата другой инструкции, предшествующей ей в конвейере, но еще не завершенной. Конфликты конвейера могут привести к остановкам конвейера : когда ЦП тратит циклы в ожидании разрешения конфликта.
Компиляторы могут планировать или переупорядочивать инструкции, чтобы сбои в конвейере происходили реже.
  • Количество функциональных блоков : некоторые процессоры имеют несколько ALU и FPU . Это позволяет им выполнять несколько инструкций одновременно. Могут быть ограничения на то, какие инструкции могут сочетаться с какими другими инструкциями («спаривание» - это одновременное выполнение двух или более инструкций) и какой функциональный блок может выполнять какую инструкцию. У них также есть проблемы, похожие на конфликты трубопроводов.
Здесь снова инструкции должны быть запланированы таким образом, чтобы различные функциональные блоки были полностью снабжены инструкциями для выполнения.
Архитектура машины
  • Размер кэша (256 кБ – 12 МБ) и тип (прямое сопоставление, 2- / 4- / 8- / 16-сторонний ассоциативный, полностью ассоциативный): такие методы, как встроенное расширение и развертывание цикла, могут увеличить размер сгенерированного кода и уменьшить локальность кода. Программа может резко замедлиться, если часто используемый участок кода (например, внутренние циклы в различных алгоритмах) внезапно не помещается в кеш. Кроме того, кеши, которые не являются полностью ассоциативными, имеют более высокие шансы на коллизии кеша даже в незаполненном кеше.
  • Скорость передачи кэша / памяти: они дают компилятору указание на штраф за промахи в кэше. Это используется в основном в специализированных приложениях.
Предполагаемое использование сгенерированного кода
Отладка
При написании приложения программист часто перекомпилирует и тестирует, поэтому компиляция должна быть быстрой. Это одна из причин, по которой большинство оптимизаций намеренно избегают на этапе тестирования / отладки. Кроме того, программный код обычно "проходит через" (см. Анимация программы ) с использованием символьного отладчика , и оптимизирующие преобразования, особенно те, которые изменяют порядок кода, могут затруднить соотнесение выходного кода с номерами строк в исходном исходном коде. Это может сбить с толку как инструменты отладки, так и программистов, использующих их.
Универсальное использование
Очень часто ожидается, что предварительно упакованное программное обеспечение будет выполняться на различных машинах и процессорах, которые могут совместно использовать один и тот же набор инструкций, но иметь разные характеристики синхронизации, кэш-памяти или памяти. В результате код может не быть настроен на какой-либо конкретный ЦП или может быть настроен так, чтобы он лучше всего работал на самом популярном ЦП, но при этом достаточно хорошо работал на других ЦП.
Специальное использование
Если программное обеспечение скомпилировано для использования на одной или нескольких очень похожих машинах с известными характеристиками, то компилятор может сильно настроить сгенерированный код для этих конкретных машин, при условии, что такие опции доступны. Важные особые случаи включают код, разработанный для параллельных и векторных процессоров , для которых используются специальные компиляторы распараллеливания .
Встроенные системы
Это частый случай специального использования. Встроенное программное обеспечение может быть точно настроено на точный размер процессора и памяти. Кроме того, стоимость или надежность системы могут быть важнее скорости кода. Например, компиляторы для встроенного программного обеспечения обычно предлагают варианты, которые уменьшают размер кода за счет скорости, потому что память - это основная стоимость встроенного компьютера. Время выполнения кода должно быть предсказуемым, а не максимально быстрым, поэтому кеширование кода может быть отключено вместе с оптимизацией компилятора, которая требует этого.

Общие темы

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

Оптимизировать общий случай
Общий случай может иметь уникальные свойства, которые позволяют использовать быстрый путь за счет медленного пути . Если чаще всего выбирается быстрый путь, в результате улучшается общая производительность.
Избегайте дублирования
Повторно используйте результаты, которые уже вычислены, и сохраните их для дальнейшего использования вместо их повторного вычисления.
Меньше кода
Удалите ненужные вычисления и промежуточные значения. Меньше нагрузки на ЦП, кеш и память обычно приводит к более быстрому выполнению. В качестве альтернативы, во встроенных системах меньшее количество кода приводит к снижению стоимости продукта.
Меньше переходов за счет использования кода прямой линии , также называемого кодом без ветвлений
Менее сложный код. Переходы (условные или безусловные переходы ) мешают предварительной выборке инструкций, замедляя выполнение кода. Использование встраивания или развертывания цикла может уменьшить количество ветвлений за счет увеличения размера двоичного файла на длину повторяемого кода. Это имеет тенденцию объединять несколько базовых блоков в один.
Местонахождение
Код и данные, к которым осуществляется доступ во времени близко друг к другу, должны быть размещены в памяти близко друг к другу, чтобы увеличить пространственную локальность ссылки .
Используйте иерархию памяти
Доступ к памяти становится все более дорогостоящим для каждого уровня иерархии памяти , поэтому перед отправкой на диск помещайте наиболее часто используемые элементы сначала в регистры, затем в кеши, а затем в основную память.
Распараллелить
Измените порядок операций, чтобы несколько вычислений могли выполняться параллельно на уровне инструкций, памяти или потока.
Более точная информация - лучше
Чем точнее информация компилятора, тем лучше он может использовать любой или все эти методы оптимизации.
Показатели времени выполнения могут помочь
Информация, собранная во время тестового прогона, может быть использована в оптимизации на основе профиля . Информация, собранная во время выполнения, в идеале с минимальными накладными расходами , может использоваться JIT- компилятором для динамического улучшения оптимизации.
Снижение силы
Замените сложные или трудные или дорогостоящие операции более простыми. Например, замена деления на константу умножением на обратную величину или использование индукционного анализа переменных для замены умножения на индекс цикла на сложение.

Конкретные техники

Оптимизация цикла

Основная статья: Оптимизация цикла

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

Индукционный анализ переменных
Грубо говоря, если переменная в цикле является простой линейной функцией индексной переменной, например j := 4*i + 1, она может обновляться соответствующим образом каждый раз при изменении переменной цикла. Это снижение силы , а также может привести к тому, что определения индексной переменной станут мертвым кодом . Эта информация также полезна для исключения проверки границ и анализа зависимостей , среди прочего.
Петлевое деление или петлевое распределение
Деление цикла пытается разбить цикл на несколько циклов в одном и том же диапазоне индексов, но каждый занимает только часть тела цикла. Это может улучшить локальность ссылок , как данных, к которым осуществляется доступ в цикле, так и кода в теле цикла.
Сращивание петель или объединение петель, набивание петель или заклинивание петель
Другой метод, который пытается уменьшить накладные расходы цикла. Когда два соседних цикла будут повторяться одинаковое количество раз независимо от того, известно ли это число во время компиляции, их тела могут быть объединены, если они не ссылаются на данные друг друга.
Инверсия петли
Этот метод изменяет стандарт то время как петли в Do / , а (также известный как повтор / до ) цикла обернуты в случае условно, уменьшая число скачков на два, за исключением случаев , когда цикл выполняется. Это дублирует проверку условий (увеличивает размер кода), но более эффективно, поскольку скачки обычно вызывают остановку конвейера . Кроме того, если начальное условие известно во время компиляции и известно, что оно не имеет побочных эффектов , if guard можно пропустить.
Петлевой обмен
Эти оптимизации меняют внутренние циклы на внешние. Когда переменные цикла индексируются в массив, такое преобразование может улучшить локальность ссылки в зависимости от макета массива.
Циклически-инвариантное движение кода
Если количество вычисляется внутри цикла во время каждой итерации, и его значение одинаково для каждой итерации, это может значительно повысить эффективность, подняв его за пределы цикла и вычислив его значение только один раз перед началом цикла. Это особенно важно для выражений вычисления адресов, генерируемых циклами по массивам. Для правильной реализации этот метод должен использоваться с инверсией цикла , потому что не весь код безопасно поднимать за пределы цикла.
Оптимизация гнезда петель
Некоторые широко распространенные алгоритмы, такие как умножение матриц, имеют очень плохое поведение кеша и чрезмерные обращения к памяти. Оптимизация вложенности циклов увеличивает количество попаданий в кэш за счет выполнения операции над небольшими блоками и использования обмена циклами.
Разворот петли
Реверсирование цикла меняет порядок, в котором значения присваиваются индексной переменной. Это тонкая оптимизация, которая может помочь устранить зависимости и, таким образом, включить другие оптимизации. Кроме того, на некоторых архитектурах реверсирование цикла способствует уменьшению кода, так как при уменьшении индекса цикла условие, которое должно быть выполнено для того, чтобы запущенная программа вышла из цикла, - это сравнение с нулем. Часто это специальная инструкция без параметров, в отличие от сравнения с числом, для которого требуется число для сравнения. Таким образом, количество байтов, необходимых для хранения параметра, сохраняется за счет обращения цикла. Кроме того, если число сравнения превышает размер слова платформы, в стандартном порядке цикла потребуется выполнить несколько инструкций, чтобы оценить сравнение, что не относится к реверсированию цикла.
Развертывание петли
При развертывании тело цикла дублируется несколько раз, чтобы уменьшить количество проверок условия цикла и количество переходов, которые ухудшают производительность из-за ухудшения конвейера команд. Оптимизация "меньше скачков". Полное развертывание цикла устраняет все накладные расходы, но требует, чтобы количество итераций было известно во время компиляции.
Расщепление петли
Разделение цикла пытается упростить цикл или устранить зависимости, разбивая его на несколько циклов, которые имеют одинаковые тела, но повторяются по разным смежным частям диапазона индексов. Полезным частным случаем является очистка цикла , которая может упростить цикл с проблемной первой итерацией, выполняя эту итерацию отдельно перед входом в цикл.
Отключение петли
Отключение перемещает условное выражение изнутри цикла за пределы цикла, дублируя тело цикла внутри каждого из предложений if и else условного выражения.
Конвейерная обработка программного обеспечения
Цикл реструктурирован таким образом, что работа, выполняемая в итерации, разбивается на несколько частей и выполняется в течение нескольких итераций. В замкнутом цикле этот метод скрывает задержку между загрузкой и использованием значений.
Автоматическое распараллеливание
Цикл преобразуется в многопоточный или векторизованный (или даже в оба) код для одновременного использования нескольких процессоров в многопроцессорной машине с общей памятью (SMP), включая многоядерные машины.

Оптимизация потока данных

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

Исключение общего подвыражения
В выражении (a + b) - (a + b)/4«общее подвыражение» относится к дублированному (a + b). Компиляторы, реализующие этот метод, понимают, что (a + b)это не изменится, и поэтому вычисляют его значение только один раз.
Постоянное сворачивание и размножение
замена выражений, состоящих из констант (например, 3 + 5) их конечным значением ( 8) во время компиляции, а не выполнение вычислений во время выполнения. Используется на большинстве современных языков.
Распознавание и устранение индукционных переменных
см. обсуждение индукционного переменного анализа выше .
Классификация псевдонимов и анализ указателей
при наличии указателей вообще сложно произвести какие-либо оптимизации, поскольку потенциально любая переменная может быть изменена при назначении области памяти. Указав, какие указатели могут указывать на какие переменные, несвязанные указатели можно игнорировать.
Устранение мертвого магазина
удаление присваиваний переменным, которые впоследствии не читаются, либо из-за окончания срока жизни переменной, либо из-за последующего присваивания, которое перезапишет первое значение.

Оптимизация на основе SSA

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

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

Оптимизация генератора кода

Распределение регистров
Наиболее часто используемые переменные должны храниться в регистрах процессора для максимально быстрого доступа. Чтобы найти, какие переменные поместить в регистры, создается граф интерференции. Каждая переменная является вершиной, и когда две переменные используются одновременно (имеют пересекающийся диапазон значений), между ними есть ребро. Этот график раскрашен с использованием, например , алгоритма Чейтина с использованием того же количества цветов, что и регистры. Если раскрашивание не удается, одна переменная «переливается» в память и раскрашивание повторяется.
Выбор инструкции
Большинство архитектур, особенно архитектуры CISC и архитектуры с множеством режимов адресации , предлагают несколько различных способов выполнения конкретной операции с использованием совершенно разных последовательностей инструкций. Задача селектора инструкций состоит в том, чтобы в целом хорошо выполнять работу по выбору инструкций, с которыми какие операторы реализовать в низкоуровневом промежуточном представлении . Например, на многих процессорах семейства 68000 и на архитектуре x86 сложные режимы адресации могут использоваться в таких операторах, как «lea 25 (a1, d5 * 4), a0», что позволяет одной инструкции выполнять значительный объем арифметических операций. с меньшим объемом памяти.
Планирование инструкций
Планирование инструкций - важная оптимизация для современных конвейерных процессоров, которая позволяет избежать остановок или пузырей в конвейере за счет кластеризации инструкций без зависимостей вместе, сохраняя при этом исходную семантику.
Рематериализация
Рематериализация пересчитывает значение вместо загрузки его из памяти, предотвращая доступ к памяти. Это выполняется в тандеме с распределением регистров, чтобы избежать утечек.
Факторинг кода
Если несколько последовательностей кода идентичны или могут быть параметризованы или переупорядочены, чтобы быть идентичными, их можно заменить вызовами общей подпрограммы. Это часто может совместно использовать код для настройки подпрограммы, а иногда и хвостовую рекурсию.
Батуты
Многие процессоры имеют меньшие инструкции вызова подпрограмм для доступа к малой памяти. Компилятор может сэкономить место, используя эти небольшие вызовы в основной части кода. Инструкции перехода в малой памяти могут обращаться к подпрограммам по любому адресу. Это увеличивает экономию места за счет факторинга кода.
Изменение порядка вычислений
Компиляторы реструктуризации, основанные на целочисленном линейном программировании , улучшают локальность данных и раскрывают больший параллелизм за счет изменения порядка вычислений. Компиляторы, оптимизирующие пространство, могут переупорядочивать код, чтобы удлинить последовательности, которые могут быть включены в подпрограммы.

Оптимизация функционального языка

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

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

Прочие оптимизации

Устранение проверки границ
Многие языки, такие как Java , требуют проверки границ для всех обращений к массивам. Это серьезное узкое место для производительности некоторых приложений, таких как научный код. Устранение проверки границ позволяет компилятору безопасно удалять проверку границ во многих ситуациях, когда он может определить, что индекс должен попадать в допустимые границы; например, если это простая переменная цикла.
Оптимизация смещения ответвлений (зависит от станка)
Выберите самое короткое смещение ветви, которое достигает цели.
Изменение порядка блоков кода
Переупорядочивание блоков кода изменяет порядок основных блоков в программе, чтобы уменьшить количество условных переходов и улучшить локальность ссылок.
Устранение мертвого кода
Удаляет инструкции, которые не влияют на поведение программы, например, определения, которые не используются, называемые мертвым кодом . Это уменьшает размер кода и устраняет ненужные вычисления.
Факторинг инвариантов ( инвариантов цикла )
Если выражение выполняется как при соблюдении условия, так и при его невыполнении, его можно записать только один раз за пределами условного оператора. Точно так же, если определенные типы выражений (например, присвоение константы переменной) появляются внутри цикла, их можно переместить из него, потому что их эффект будет одинаковым, независимо от того, выполняются ли они много раз или только один раз. . Это также известно как полное устранение избыточности. Аналогичная, но более эффективная оптимизация - это частичное устранение избыточности (PRE).
Встроенное раскрытие или расширение макроса
Когда некоторый код вызывает процедуру , можно напрямую вставить тело процедуры в вызывающий код, а не передавать ему управление. Это экономит накладные расходы, связанные с вызовами процедур, а также дает возможность для множества различных оптимизаций, зависящих от параметров, но за счет экономии места; тело процедуры дублируется каждый раз, когда процедура вызывается встроенным. Как правило, встраивание полезно в критичном к производительности коде, который выполняет большое количество вызовов небольших процедур. Оптимизация "меньше скачков". В заявлении о императивном программировании языков также является пример такой оптимизации с. Хотя операторы могут быть реализованы с помощью вызовов функций, они почти всегда реализуются с помощью встраивания кода.
Прыжковая резьба
В этой оптимизации объединяются последовательные условные переходы, полностью или частично основанные на одном и том же условии.
Например, чтобы ,if (c) { foo; } if (c) { bar; }if (c) { foo; bar; }
и к .if (c) { foo; } if (!c) { bar; }if (c) { foo; } else { bar; }
Макросжатие
Оптимизация пространства, которая распознает общие последовательности кода, создает подпрограммы («макросы кода»), которые содержат общий код, и заменяет вхождения общих кодовых последовательностей вызовами соответствующих подпрограмм. Наиболее эффективно это делается как оптимизация машинного кода , когда присутствует весь код. Этот метод был впервые использован для экономии места в интерпретируемом потоке байтов, используемом в реализации Macro Spitbol на микрокомпьютерах . Известно, что проблема определения оптимального набора макросов, который минимизирует пространство, необходимое для данного сегмента кода, является NP-полной , но эффективные эвристики достигают результатов, близких к оптимальным.
Уменьшение коллизий кеша
(например, нарушая выравнивание на странице)
Stack уменьшение высоты
Измените структуру дерева выражений, чтобы минимизировать ресурсы, необходимые для оценки выражений.
Повторный заказ теста
Если у нас есть два теста, которые являются условием для чего-то, мы можем сначала иметь дело с более простыми тестами (например, сравнение переменной с чем-то) и только затем со сложными тестами (например, с теми, которые требуют вызова функции). Этот метод дополняет ленивую оценку , но может использоваться только тогда, когда тесты не зависят друг от друга. Семантика короткого замыкания может сделать это трудным.

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

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

Межпроцедурная оптимизация распространена в современных коммерческих компиляторах от SGI , Intel , Microsoft и Sun Microsystems . Долгое время GCC с открытым исходным кодом критиковали за отсутствие мощного межпроцедурного анализа и оптимизаций, хотя сейчас ситуация улучшается. Еще один компилятор с открытым исходным кодом с полной инфраструктурой анализа и оптимизации - Open64 .

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

Практические соображения

Компилятор может выполнять самые разные оптимизации: от простых и понятных, требующих небольшого времени компиляции, до сложных и сложных, требующих значительного времени компиляции. Соответственно, компиляторы часто предоставляют параметры своей управляющей команде или процедуре, чтобы позволить пользователю компилятора выбрать, какую оптимизацию запрашивать; например, компилятор IBM FORTRAN H позволял пользователю не указывать оптимизацию, оптимизацию только на уровне регистров или полную оптимизацию. К 2000-м годам для компиляторов, таких как Clang , было обычным делом иметь ряд параметров команд компилятора, которые могли влиять на различные варианты оптимизации, начиная со знакомого -O2переключателя.

Подход к изолированной оптимизации заключается в использовании так называемых постпроходных оптимизаторов (некоторые коммерческие версии которых восходят к программному обеспечению мэйнфреймов конца 1970-х годов). Эти инструменты берут исполняемый файл оптимизирующим компилятором и оптимизируют его еще больше. Оптимизаторы после прохода обычно работают на уровне языка ассемблера или машинного кода (в отличие от компиляторов, оптимизирующих промежуточные представления программ). Одним из таких примеров является Portable C Compiler (pcc) 1980-х годов, у которого был необязательный проход, который выполнял бы пост-оптимизацию сгенерированного кода сборки.

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

История

Ранние компиляторы 1960-х годов часто были в первую очередь озабочены простой или правильной компиляцией кода, поэтому время компиляции было главной проблемой. Одним из примечательных ранних оптимизирующих компиляторов был компилятор IBM FORTRAN H конца 1960-х годов. Другим из первых и важных оптимизирующих компиляторов, в котором впервые было предложено несколько передовых методов, был компилятор для BLISS (1970), который был описан в The Design of the Optimizing Compiler (1975). К концу 1980-х годов оптимизирующие компиляторы были достаточно эффективны, поэтому программирование на языке ассемблера пришло в упадок. Это произошло вместе с разработкой микросхем RISC и расширенных функций процессора, таких как планирование инструкций и спекулятивное выполнение, которые были предназначены для оптимизации компиляторов, а не для написанного человеком кода сборки.

Список статических анализов кода

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

использованная литература

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