stringtranslate.com

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

Оптимизирующий компилятор — это компилятор, разработанный для генерации кода, оптимизированного в таких аспектах, как минимизация времени выполнения программы, использования памяти , размера хранилища и энергопотребления [1] . Оптимизация обычно реализуется как последовательность оптимизирующих преобразований , алгоритмов, которые преобразуют код для создания семантически эквивалентного кода, оптимизированного для некоторого аспекта. Обычно он интенсивно использует ресурсы ЦП и памяти [2] . На практике такие факторы, как доступная память и готовность программиста ждать компиляции, ограничивают оптимизации, которые может предоставить компилятор. Исследования показывают, что некоторые задачи оптимизации являются NP-полными или даже неразрешимыми [3] .

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

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

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

Локальный и глобальный масштаб

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

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

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

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

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

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

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

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

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

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

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

Языконезависимый и языкозависимый

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

Машинонезависимый против машинозависимого

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

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

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

Целевая машина
Могут ли и должны ли применяться конкретные оптимизации, может зависеть от характеристик целевой машины. Некоторые компиляторы, такие как GCC и Clang, параметризуют машинно-зависимые факторы, чтобы их можно было использовать для оптимизации для разных машин. [7]
Целевая архитектура ЦП
Архитектура машины
Предполагаемое использование
Известные случаи включают код, разработанный для параллельных и векторных процессоров , для которого используются специальные распараллеливающие компиляторы .
Прошивку для встраиваемой системы можно оптимизировать для целевого ЦП и памяти. Стоимость или надежность системы могут быть важнее скорости кода. Например, компиляторы для встраиваемого ПО обычно предлагают опции, которые уменьшают размер кода за счет скорости. Время выполнения кода может быть предсказуемым, а не максимально быстрым, поэтому кэширование кода может быть отключено вместе с оптимизациями компилятора, которые его требуют.

Общие темы

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

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

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

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

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

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

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

Проницательная оптимизация магазина

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

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

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

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

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

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

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

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

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

Функциональная оптимизация языка

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

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

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

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

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

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

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

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

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

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

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

Другое соображение заключается в том, что алгоритмы оптимизации сложны и, особенно при использовании для компиляции больших, сложных языков программирования, могут содержать ошибки, которые вносят ошибки в сгенерированный код или вызывают внутренние ошибки во время компиляции. Ошибки компилятора любого рода могут сбивать с толку пользователя, но особенно в этом случае, поскольку может быть неясно, что именно логика оптимизации виновата. [19] В случае внутренних ошибок проблема может быть частично решена с помощью «отказоустойчивой» техники программирования, в которой логика оптимизации в компиляторе кодируется таким образом, что сбой перехватывается, выдается предупреждающее сообщение, а остальная часть компиляции переходит к успешному завершению. [20]

История

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

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

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

Ссылки

  1. ^ "Оптимизации в компиляторах C++ - ACM Queue". acmqueue .
  2. ^ «Оптимизация кода при проектировании компилятора — заметки GATE CSE».
  3. ^ https://karthik.ise.illinois.edu/courses/ie511/lectures-sp-21/lecture-15.pdf. {{cite web}}: Отсутствует или пусто |title=( помощь )
  4. ^ abcdefghijk Ахо, Альфред В.; Сети, Рави; Ульман, Джеффри Д. (1986). Составители: принципы, методы и инструменты . Reading, Массачусетс: Addison-Wesley. ISBN 0-201-10088-6.
  5. ^ ab Cooper, Keith D. ; Torczon, Linda (2003) [2002-01-01]. Разработка компилятора . Morgan Kaufmann . стр. 404, 407. ISBN 978-1-55860-698-2.
  6. ^ abc Clinton F. Goss (август 2013 г.) [Впервые опубликовано в июне 1986 г.]. Оптимизация машинного кода — улучшение исполняемого объектного кода (PDF) (диссертация на степень доктора философии). Том. Технический отчет факультета компьютерных наук № 246. Институт Куранта, Нью-Йоркский университет. arXiv : 1308.4815 . Bibcode :2013arXiv1308.4815G. Архивировано (PDF) из оригинала 2022-10-09 . Получено 22 августа 2013 г.
    • Клинтон Ф. Госс (2013) [1986]. Оптимизация машинного кода — улучшение исполняемого объектного кода (диссертация доктора философии). Институт Куранта, Нью-Йоркский университет.
  7. ^ "GCC - Машинно-зависимые параметры". Проект GNU .
  8. ^ "RISC против CISC". cs.stanford.edu . Получено 2024-10-15 .
  9. ^ Джеймс Гослинг ; Билл Джой ; Гай Стил . «17 потоков и блокировок». Спецификация языка Java (ред. 1.0). 17.8 Действия Prescient Store.
  10. ^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Advanced Compiler Design Implementation . Morgan Kaufmann. стр. 329–. ISBN 978-1-55860-320-2. постоянное складывание.
  11. ^ Wegman, Mark N.; Zadeck, F. Kenneth (апрель 1991 г.). «Constant Propagation with Conditional Branches» (PDF) . ACM Transactions on Programming Languages ​​and Systems . 13 (2): 181–210. doi :10.1145/103135.103136.
  12. ^ Клик, Клиффорд; Купер, Кейт. (март 1995 г.). «Объединение анализов, объединение оптимизаций» (PDF) . Труды ACM по языкам и системам программирования . 17 (2): 181–196. doi :10.1145/201059.201061.
  13. ^ ab Cx51 Compiler Manual, версия 09.2001, стр. 155, Keil Software Inc.
  14. ^ Роберт Б. К. Дьюар ; Мартин Чарльз Голумбик ; Клинтон Ф. Госс (август 2013 г.) [Впервые опубликовано в октябре 1979 г.]. MICRO SPITBOL . Технический отчет отдела компьютерных наук. Том 11. Институт математических наук Куранта. arXiv : 1308.6096 . Bibcode : 2013arXiv1308.6096D.
  15. ^ Мартин Чарльз Голумбик ; Роберт Б. К. Дьюар ; Клинтон Ф. Госс (1980). «Макроподстановки в MICRO SPITBOL — комбинаторный анализ». Труды 11-й Юго-восточной конференции по комбинаторике, теории графов и вычислениям, Congressus Numerantium, Utilitas Math., Виннипег, Канада . Т. 29. С. 485–495.
  16. ^ Глазунов, Н. М. (25 ноября 2012 г.). «Основы научных исследований». arXiv : 1212.1651 [cs.OH].
  17. ^ Гелтон, Серж (5 августа 2019 г.). «Настройте процесс компиляции с помощью Clang: параметры оптимизации». Red Hat.
  18. ^ Майкл Эванс (декабрь 1982 г.). «Программная инженерия для среды Cobol». Communications of the ACM . 25 (12): 874–882. ​​doi :10.1145/358728.358732 . Получено 10 августа 2013 г.
  19. ^ Сан, Ченнянь и др. (18–20 июля 2016 г.). «К пониманию ошибок компилятора в GCC и LLVM». Труды 25-го Международного симпозиума по тестированию и анализу программного обеспечения . Issta 2016. стр. 294–305. doi :10.1145/2931037.2931074. ISBN 9781450343909. S2CID  8339241.
  20. ^ Шиллинг, Джонатан Л. (август 1993 г.). «Безопасное программирование в оптимизации компилятора». ACM SIGPLAN Notices . 28 (8): 39–42. doi :10.1145/163114.163118. S2CID  2224606.

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