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

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

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

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

Исследования показывают, что некоторые задачи оптимизации являются NP-полными или даже неразрешимыми .

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

Категоризация

Оптимизации классифицируются различными, частично пересекающимися способами.

Локальная и глобальная область действия

Область определяет, какая часть входного кода подлежит оптимизации.

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

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

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

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

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

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

Оптимизация времени ссылки

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

Оптимизация машинного и объектного кода

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

Независимость от языка и зависимость от языка

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

Машинно-независимый и машинно-зависимый

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

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

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

Целевая машина

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

Целевая ЦП архитектура

• Количество регистров : регистры можно использовать для оптимизации производительности. Локальные переменные могут храниться в регистрах вместо стека . Доступ к временным/промежуточным результатам можно получить в регистрах, а не в более медленной памяти.

• RISC против CISC : наборы инструкций CISC часто имеют переменную длину инструкций, часто имеют большее количество возможных инструкций, которые можно использовать, и каждая инструкция может занимать разное количество времени. Наборы инструкций RISC пытаются ограничить изменчивость в каждом из них: наборы инструкций обычно имеют постоянную длину, за некоторыми исключениями, обычно меньше комбинаций регистров и операций с памятью, а также скорость выдачи инструкций (количество инструкций, выполненных за период времени, обычно целое число, кратное тактовому циклу) обычно является константой в тех случаях, когда задержка памяти не является фактором. Может быть несколько способов выполнения определенной задачи, причем CISC обычно предлагает больше альтернатив, чем RISC. Компиляторы должны знать относительную стоимость различных инструкций и выбирать лучшую последовательность команд (см. Выбор инструкций ).

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

• Количество функциональных блоков . Некоторые процессоры имеют несколько ALU и FPU , которые позволяют им одновременно выполнять несколько инструкций. Могут существовать ограничения на то, какие инструкции могут сочетаться с другими инструкциями («спаривание» — это одновременное выполнение двух или более инструкций) и какой функциональный блок может выполнять какую инструкцию. У них также есть проблемы, похожие на конфликты в трубопроводах. Инструкции можно планировать так, чтобы функциональные блоки были полностью загружены.

Архитектура машины

• Размер и тип кэша ЦП (прямое отображение, 2-/4-/8-/16-канальная ассоциативность, полностью ассоциативный): такие методы, как встроенное расширение и развертывание цикла, могут увеличить размер сгенерированного кода и уменьшить локальность кода. Программа может резко замедлиться, если часто используемый участок кода (например, внутренние циклы в различных алгоритмах) внезапно не поместится в кеш. Кроме того, кеши, которые не являются полностью ассоциативными, имеют более высокую вероятность конфликтов кеша даже в незаполненном кеше.

• Скорость передачи данных в кэш/память: они дают компилятору представление о штрафе за промахи в кэше. Используется в основном в специализированных приложениях.

Использование по назначению

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

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

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

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

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

Общие темы

Оптимизация включает в себя следующие, иногда противоречивые темы.

Оптимизация общего случая

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

Избегайте дублирования

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

Меньше кода

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

Меньше переходов за счет использования линейного кода , также называемого кодом без ветвей.

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

Местность

Код и данные, доступ к которым осуществляется близко друг к другу во времени, должны располагаться близко друг к другу в памяти, чтобы повысить пространственную локальность ссылок .

Используйте иерархию памяти

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

Распараллеливать

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

Более точная информация лучше

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

Метрики времени выполнения могут помочь

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

Снижение прочности

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

Конкретные методы

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

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

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

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

Индукционный переменный анализ

Грубо говоря, если переменная в цикле является простой линейной функцией индексной переменной, например j := 4*i + 1, его можно соответствующим образом обновлять каждый раз при изменении переменной цикла. Это снижение прочности , а также может привести к тому, что определения индексной переменной станут мертвым кодом . Эта информация также полезна для устранения проверок границ и анализа зависимостей . , среди прочего,

Петлевое деление или петлевое распределение

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

Слияние петель или объединение петель, или набивка петель, или застревание петель.

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

Инверсия цикла

Этот метод заменяет стандартный цикл while на цикл do/ while (также известный как повтор/пока ), завернутый в условие if , уменьшая количество переходов на два для случаев, когда цикл выполняется. Это дублирует проверку условия (увеличивает размер кода), но более эффективно, поскольку переходы обычно вызывают остановку конвейера . Кроме того, если начальное условие известно во время компиляции и известно, что оно не имеет побочных эффектов , защиту if можно пропустить.

Перестановка петель

Эти оптимизации заменяют внутренние циклы внешними циклами. Когда переменные цикла индексируются в массиве, такое преобразование может улучшить локальность ссылки, в зависимости от структуры массива.

Движение кода, инвариантное к циклу

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

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

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

Реверс цикла

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

Развертывание цикла

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

Разделение цикла

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

Выключение петли

При отмене переключения условное выражение перемещается из цикла наружу за счет дублирования тела цикла внутри каждого из предложений if и else условного оператора.

Конвейерная обработка программного обеспечения

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

Автоматическое распараллеливание

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

магазина

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

данных

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

Удаление общего подвыражения

В выражении (a + b) - (a + b)/4, «общее подвыражение» относится к дублированному (a + b). Составители, реализующие этот метод, понимают, что (a + b) не изменится, поэтому рассчитайте его значение только один раз.

Постоянное сворачивание и распространение

замена выражений, состоящих из констант (например, 3 + 5) с их окончательным значением ( 8) во время компиляции, а не выполнять вычисления во время выполнения. Используется в большинстве современных языков.

Распознавание и устранение индукционных переменных

см. выше обсуждение индукционного анализа переменных .

Классификация псевдонимов и анализ указателей

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

мертвых магазинов Устранение

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

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

Эти оптимизации предполагается выполнить после преобразования программы в специальную форму, называемую Static Single Assignment , в которой каждая переменная назначается только в одном месте. Хотя некоторые из них функционируют без 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-полной . но эффективная эвристика достигает почти оптимальных результатов.

Уменьшение кэша коллизий

(например, нарушив выравнивание на странице)

Стек - уменьшение высоты

Перестройте дерево выражений, чтобы минимизировать ресурсы, необходимые для оценки выражений.

Тестовый переупорядочение

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

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

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

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

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

соображения

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

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

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

История

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

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

• Анализ псевдонимов
• Анализ указателя
• Анализ формы
• Анализ побега
• Анализ доступа к массиву
• Анализ зависимостей
• Анализ потока управления
• Анализ потока данных
  • цепочки использования и определения Анализ
  • Анализ переменных в реальном времени
  • Доступный анализ выражений

См. также

• Алгоритмическая эффективность
• Выполнение функции во время компиляции
• Теорема о полной занятости
• Компиляция «точно в срок» (JIT)
• Метод Килдалла
• Оптимизация на основе профиля
• Оптимизация программы

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

• Цитаты из CiteSeer
• Руководства по оптимизации от Агнера Фога - документация по архитектуре процессора x86 и низкоуровневой оптимизации кода.