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

Эта статья предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/24 декабря 2012. Пока процесс обсуждения не завершён, статью можно попытаться улучшить, однако следует воздерживаться от переименований или немотивированного удаления содержания, подробнее см. руководство к дальнейшему действию. Не снимайте пометку о выставлении на удаление до окончания обсуждения. Администраторам: ссылки сюда, история (последнее изменение), журналы, удалить.

Эту страницу предлагается объединить с Оптимизация компилятора. Пояснение причин и обсуждение — на странице Википедия:К объединению/25 декабря 2012. Обсуждение длится одну неделю (или дольше, если оно идёт медленно). Дата начала обсуждения — 2012-12-25. Если обсуждение не требуется (очевидный случай), используйте другие шаблоны. Не удаляйте шаблон до подведения итога обсуждения. Номинатору: добавить секцию обсуждения

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

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

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

"Peephole" оптимизации

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

Пример

Умножение числа на 2 может быть более эффективно выполнено с использованием левого сдвига или путем сложения числа с таким же.

Локальные оптимизации

Рассматривается только информация, локальная для базового блока^[1]. Так как в базовых блоках нет контроля потока управления, эти оптимизации требуют незначительного анализа (экономя время и снижая требования к памяти), но это также означает, что не сохраняется информация для следующего шага.

Глобальные оптимизации

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

Оптимизации циклов

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

Пример

Рассмотрим следующий код:

for (int i = 0; i < n; i++) {
    x = y + z;
    a[i] = 6 * i + x * x;
}

Очевидно, что сложение и умножение можно вынести из цикла:

x = y + z;
t1 = x * x;
for (int i = 0; i < n; i++) {
    a[i] = 6 * i + t1;
}

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

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

Пример

Пусть есть некоторая функция:

int pred(int x) {
    if (x == 0)
       return 0;
    else
       return x - 1;
}

До ее встраивания код выглядел следующим образом:

 int f(int y) {
     return pred(y) + pred(0) + pred(y+1);
 }

После оптимизации:

int f(int y) {
    int temp = 0;
    if (y   == 0) temp += 0; else temp += y       - 1; /* (1) */
    if (0   == 0) temp += 0; else temp += 0       - 1; /* (2) */
    if (y+1 == 0) temp += 0; else temp += (y + 1) - 1; /* (3) */
    return temp;
}

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

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

Сама машина

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

Архитектура целевого процессора

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

RISC/CISC

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

Общие принципы

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

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

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

Уменьшение избыточности

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

Меньше кода

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

Сокращение числа переходов в коде

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

Локальность

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

Иерархия памяти

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

Распараллеливание

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

Точная информация

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

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

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

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

Анализ индукционной переменной (англ. Induction variable analysis)

Если переменная в цикле является результатом простой линейной функции от итерационной переменной, например for (i=0; i < 10; ++i) j = 17 * i;, то можно соответствующим образом обновлять данную переменную на каждой итерации. Это называется понижение силы операций.

Деление цикла на части (англ. Loop fission)

Оптимизация пытается разделить цикл на несколько отдельных с тем же диапазоном индекса. Каждый новый цикл является частью тела исходного цикла. Это может улучшить локальность ссылок (см. Принцип локальности ссылок (англ. Locality of reference)).

Объединение циклов (англ. Loop fusion)

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

Инверсия цикла (англ. Loop inversion)

Этот метод меняет стандартный while цикл на do/while цикл, поставленный под некоторое условие, что уменьшает количество переходов на два, для случаев, когда цикл выполняется.

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

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

Оптимизации потока данных основаны на анализе потока данных (англ. Data-flow analysis) и, прежде всего, зависят от распространения некоторых свойст данных в графе потока управления.

Сбор общих выражений (англ. Common subexpression elimination)

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

Свёртка констант

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

Анализ индукционной переменной (англ. Induction variable analysis)

См. описание воптимизации циклов.

Оптимизации SSA-форм

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

Примечания

1. ↑ Cooper, Keith D., and Torczon, Linda, Engineering a Compiler, Morgan Kaufmann, 2004, ISBN 1-55860-699-8 page 404
2. ↑ Cooper, Keith D., and Torczon, Linda, Engineering a Compiler, Morgan Kaufmann, 2004, ISBN 1-55860-699-8 page 407

Литература

• Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман, Компиляторы: принципы, технологии и инструментарий, 2 издание = Compilers: Principles, Techniques, and Tools. — 2 изд. — М.: Вильямс, 2008. — ISBN 978-5-8459-1349-4; ISBN 0-321-48681-1
• Steven Muchnick, Advanced Compiler Design and Implementation - Morgan Kaufmann, 1997 - ISBN 1558603204
• Keith Cooper, Linda Torczon, Engineering a Compiler, Second Edition - Morgan Kaufmann, 2011 - ISBN 978-0120884780

Ссылки

• Введение в оптимизацию приложений с использованием компиляторов Intel

Это заготовка статьи. Вы можете помочь проекту, исправив и дополнив её. Это примечание по возможности следует заменить более точным.