stringtranslate.com

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Общие темы

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

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

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

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

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

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

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

Провидческая оптимизация магазина

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

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

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

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

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

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

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

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

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

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

Хотя многие из них также применимы к нефункциональным языкам, они либо происходят из функциональных языков, таких как 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; }
Макросжатие
Оптимизация пространства, которая распознает общие последовательности кода, создает подпрограммы («макросы кода»), содержащие общий код, и заменяет вхождения общих последовательностей кода вызовами соответствующих подпрограмм. [4] Наиболее эффективно это делается при оптимизации машинного кода , когда присутствует весь код. Этот метод был впервые использован для экономии места в интерпретируемом потоке байтов , используемом в реализации Macro Spitbol на микрокомпьютерах . [13] Известно, что проблема определения оптимального набора макросов, который минимизирует пространство, необходимое для данного сегмента кода, является NP-полной , [4] но эффективная эвристика достигает почти оптимальных результатов. [14]
Уменьшение коллизий кэша
(например, нарушив выравнивание на странице)
Стек - уменьшение высоты
Перестройте дерево выражений, чтобы минимизировать ресурсы, необходимые для оценки выражений. [ нужны разъяснения ]
Тестовый переупорядочение
Если у нас есть два теста, являющиеся условием чего-то, мы можем сначала разобраться с более простыми тестами (например, сравнением переменной с чем-то), а только потом со сложными тестами (например, требующими вызова функции). Этот метод дополняет ленивую оценку , но может использоваться только тогда, когда тесты не зависят друг от друга. Короткое замыкание семантики может затруднить эту задачу.

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

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

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

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

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

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

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

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

История

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

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

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

Рекомендации

  1. ^ Ахо, Альфред В.; Сетхи, Рави; Уллман, Джеффри Д. (1986). Составители: принципы, методы и инструменты . Ридинг, Массачусетс: Аддисон-Уэсли. п. 585. ИСБН 0-201-10088-6.
  2. ^ Аб Купер, Кейт Д .; Торчон, Линда (2003) [2002-01-01]. Разработка компилятора . Морган Кауфманн . стр. 404, 407. ISBN. 978-1-55860-698-2.
  3. ^ Ахо, Сетхи и Уллман, Составители , стр. 554.
  4. ^ abc Клинтон Ф. Госс (август 2013 г.) [Впервые опубликовано в июне 1986 г.]. Оптимизация машинного кода - улучшение исполняемого объектного кода (PDF) (кандидатская диссертация). Том. Технический отчет отдела компьютерных наук № 246. Курантовский институт Нью-Йоркского университета. arXiv : 1308.4815 . Бибкод : 2013arXiv1308.4815G. Архивировано (PDF) из оригинала 9 октября 2022 г. Проверено 22 августа 2013 г.
    • Клинтон Ф. Госс (2013) [1986]. Оптимизация машинного кода - улучшение исполняемого объектного кода (кандидатская диссертация). Курантовский институт Нью-Йоркского университета.
  5. ^ аб Ахо, Сетхи и Ульман, Составители , стр. 596.
  6. ^ Ахо, Сетхи и Уллман, Составители , стр. 596–598.
  7. ^ «Microsoft Learn — Действия Prescient Store» . Майкрософт .
  8. ^ Ахо, Сетхи и Уллман, Составители , стр. 592–594.
  9. ^ Стивен Мучник; Мучник и партнеры (15 августа 1997 г.). Расширенная реализация проекта компилятора . Морган Кауфманн. стр. 329–. ISBN 978-1-55860-320-2. постоянное складывание.
  10. ^ Вегман, Марк Н. и Задек, Ф. Кеннет. «Постоянное распространение с условными ветвями». Транзакции ACM по языкам и системам программирования , 13 (2), апрель 1991 г., страницы 181–210.
  11. ^ Клик, Клиффорд и Купер, Кейт. «Объединение анализа, объединение оптимизаций», Транзакции ACM в языках и системах программирования , 17 (2), март 1995 г., страницы 181–196.
  12. ^ ab Руководство по компилятору Cx51, версия 09.2001, стр. 155, Keil Software Inc.
  13. ^ Роберт Б.К. Дьюар ; Мартин Чарльз Голумбик ; Клинтон Ф. Госс (август 2013 г.) [Впервые опубликовано в октябре 1979 г.]. МИКРО СПИТБОЛ . Технический отчет отдела компьютерных наук. Том. 11. Курантовский институт математических наук. arXiv : 1308.6096 . Бибкод : 2013arXiv1308.6096D.
  14. ^ Мартин Чарльз Голумбик ; Роберт Б.К. Дьюар ; Клинтон Ф. Госс (1980). «Макрозамены в МИКРО СПИТБОЛ - комбинаторный анализ». Учеб. 11-я Юго-восточная конференция по комбинаторике, теории графов и вычислениям, Конгресс Нумерантиум, Utilitas Math., Виннипег, Канада . 29 : 485–495.
  15. ^ Глазунов, Н.М. (25 ноября 2012 г.). «Основы научных исследований». arXiv : 1212.1651 [cs.OH].
  16. ^ Ахо, Сетхи и Ульман, Составители , стр. 15.
  17. ^ аб Ахо, Сетхи и Ульман, Составители , стр. 737.
  18. ↑ Гуэлтон, Серж (5 августа 2019 г.). «Настройте процесс компиляции с помощью Clang: параметры оптимизации». Красная Шапка.
  19. ^ Разработка программного обеспечения для среды Cobol. Портал.acm.org. Проверено 10 августа 2013 г.
  20. ^ Ахо, Сетхи и Ульман, Составители , стр. 736.
  21. ^ Сунь, Чэннянь; и другие. (18–20 июля 2016 г.). «На пути к пониманию ошибок компилятора в GCC и LLVM». Материалы 25-го Международного симпозиума по тестированию и анализу программного обеспечения . Иста 2016. С. 294–305. дои : 10.1145/2931037.2931074. ISBN 9781450343909. S2CID  8339241.
  22. ^ Шиллинг, Джонатан Л. (август 1993 г.). «Отказоустойчивое программирование при оптимизации компилятора». Уведомления ACM SIGPLAN . 28 (8): 39–42. дои : 10.1145/163114.163118. S2CID  2224606.
  23. ^ Ахо, Сетхи и Ульман, Составители , стр. 740, 779.

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