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

Локальные peephole-оптимизации (англ. peephole — «глазок») рассматривают несколько соседних (в терминах одного из графов представления программы) инструкций (как будто «смотрит в глазок» на код), чтобы увидеть, можно ли с ними произвести какую-либо трансформацию с точки зрения цели оптимизации. В частности, они могут быть заменены одной инструкцией или более короткой последовательностью инструкций.

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

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

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

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

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

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

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

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;
}

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

Анализ индуктивных переменных

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

Деление цикла на части

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

Объединение циклов (Слияние циклов)

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

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

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

Расщепление цикла

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

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

Удаление общих подвыражений

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

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

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

Анализ индуктивных переменных (англ. Induction variable analysis)

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

Удаление тупиковых записей

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

SSA (Single Static Assignment, Единственное статическое присваивание) — это форма представления графа потока данных (DFG, Data Flow Graph), при которой каждой переменной значение присваивается только один раз. Это позволяет избежать умножения дуг в графе при множественных записях и чтениях одной переменной и облегчает анализ графа. Для этого SSA представление вводит специальные Phi-функции (узлы графа потока данных) в некоторых местах схождения в графе потока управления. Эти новые узлы являются так называемыми псевдо-присваиваниями.

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

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