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

редактировать

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

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

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

Содержание

  • 1 Типы оптимизации
  • 2 Факторы, влияющие на оптимизацию
  • 3 Общие темы
  • 4 Специальные методы
    • 4.1 Оптимизация цикла
    • 4.2 Оптимизация потока данных
    • 4.3 Оптимизация на основе SSA
    • 4.4 Оптимизация генератора кода
    • 4.5 Оптимизация функционального языка
    • 4.6 Другие оптимизации
    • 4.7 Межпроцедурная оптимизация
  • 5 Практические соображения
  • 6 История
  • 7 Список статических анализов кода
  • 8 См. Также
  • 9 Ссылки
  • 10 Внешние ссылки

Типы оптимизации

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

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

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

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

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

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

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

Общие темы

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

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

Специальные методы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Другие оптимизации

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

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

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

Межпроцедурная оптимизация является обычным явлением в современных коммерческих компиляторах от 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 an Optimizing Compiler (1975). К концу 1980-х годов оптимизирующие компиляторы оказались достаточно эффективными, поэтому программирование на языке ассемблера пришло в упадок. Это произошло вместе с разработкой микросхем RISC и расширенных функций процессора, таких как планирование инструкций и спекулятивное выполнение, которые были разработаны для оптимизации компиляторов, а не написанного человеком кода сборки.

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

См. также

Ссылки

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

Последняя правка сделана 2021-06-01 13:36:27
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте