Азбука оптимизаций компилятора

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

Страничка будет дополняться по мере возможности.

Алгебраическое переупорядочивание

Англ.: Algebraic simplification reassociation

Прим.: В [1] данное преобразование представлено как часть алгебраических упрощений, однако в данном документе показано как отдельная оптимизация.

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

Примеры:

До После 
for(int i = 0; i < N; i++)
  for(int j = 0; j < M; j++)
    ind = (i * 2) + 4 + j + 2 + k + 1;

for(int i = 0; i < N; i++)
  for(int j = 0; j < M; j++)
    ind = j + i * 2 + k + 4 + 2 + 1;

Литература: [1]

Алгебраическое упрощение

Англ.: Algebraic simplification and reassociation

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

Примеры:

До После 
i + 0
0 + i
i - 0
- (-i)
b || true
b && false
2 * i
i * 5

i
i
i
i
true
false
i + i
(i <<2) + i

Литература: [1]

Анализ указателей

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

Примеры:

До (планирования) После (планирования) 
Такты |
  0   | *a = 1;
  3   | c = *b;

Такты |
  0   | c = *b;
      | *a = 1; // Если адреса не пересеклись, то задержка не нужна

Литература: [1]

Балансировка дерева выражений

Англ.: Tree-height balancing.

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

Примеры:

До После 
Такты |
  6   |               +
      |              / \
  5   |             +   h
      |            / \
  4   |           +   g
      |          / \
  3   |         +   f
      |        / \
  2   |       +   e
      |      / \
  1   |     +   d
      |    / \
  0   |   +   c
      |  / \
      | a   b

Такты |
  2   |                +
      |         /    АЛУ 1    \
  1   |        +               +
      |     /     \         /     \
  0   |    + АЛУ 1 +       + АЛУ 2 +
      |   / \     / \     / \     / \
      | |a   b| |c   d| |e   f| |g   h|
      | |АЛУ 1| |АЛУ 2| |АЛУ 3| |АЛУ 4|

Литература: [2]

Векторизация

Вынос инвариантов цикла

Англ.: Loop-invariant code motion.

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

Примеры:

До После 
for(int i = 0; i <N; i++)
{
  a[i] = b[i] + L * K;
}

tmp = L * K;
for(int i = 0; i <N; i++)
{
  a[i] = b[i] + tmp;
}

Литература: [3]

Вынос первых итераций цикла

Англ.: Loop peeling.

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

Примеры:

До После 
for(i = 0; i <N; i++)
{
  // loop_body
}

i = 0;
if( i <N ) { loop_body; }
i = 1;
if( i <N ) { loop_body; }
i = 2;
if( i <N ) { loop_body; }
for(i = 3; i <N; i++)
{
  // loop_body
}

Литература: [1]

Девиртуализация

Англ.: Devirtualization.

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

Примеры:

До После 
class A
{
public:
  virtual foo(){}
};

void bar(A & a)
{
  a.foo();
}

class A
{
public:
  virtual foo(){}
};

void bar(A & a)
{
  A::foo(a);
}

Литература: [11], [12]

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

Англ.: Peephole.

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

Литература: [1]

Канонизация циклов

Нумерация значений

Оптимизация условных конструкций

Англ.: If simplifications.

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

Примеры:

До После 
            ---------
            | a > d |
            ---------
             /      \
       ---------     \
       | ...   |      \
       | a > d |       \
       ---------        \
     T /      \ F        |
---------     ---------  |
| 1 ... |     | 2 ... |  |
---------     ---------  |
       \      /          /
       ---------        /
       |  ...  |--------
       ---------

            ---------
            | a > d |
            ---------
             /     |
       ---------   |
       | ...   |   |
       | a > d |   |
       ---------   |
           |       |
       ---------   |
       | 1 ... |   |
       ---------   |
           |       |
       ---------   /
       |  ...  |---
       ---------

Литература: [1]

Оптимизация конструкции switch

Англ.: Switch optimizations.

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

Примеры:

До После 
switch(c)
{
  case 1: ...; break;
  case 2: ...; break;
  ...
  case N: ...; break;
}

jmp_addr = switch_table[c];
goto jmp_addr;

case_1_label:
...
goto switch_end_label;

case_2_label:
...
goto switch_end_label;

...

case_N_label:
...
goto switch_end_label;

switch_end_label:
...

Литература: [13]

Оптимизация хвостовых вызовов

Оптимизация хвостовой рекурсии

Перестановка циклов

Планирование линейных участков

Англ.: Trace scheduling.

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

Примеры:

Граф потока управление с профилем Расположение линейных участков в итоговом коде 
         -----
         | 1 |
         -----
      10 /   \ 5
     -----   -----
     | 2 |   | 3 |
     -----   -----
   3 /   \ 7  / 
  -----  -----
  | 4 |  | 5 |
  -----  -----
      \   /
      -----
      | 6 |
      -----

     -----
   --| 1 |
   | -----
   | -----
 --|-| 2 |
 | | -----
 | | -----
 | | | 5 |<-
 | | ----- |
 | | ----- |
 | | | 6 |<|--
 | | ----- | |
 | | ----- | |
 | ->| 3 |-- |
 |   -----   |
 |   -----   |
 --->| 4 |----
     -----

Литература: [2]

Подстановка вызовов

Англ.: Function inline.

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

Примеры:

До После 
int mul(int a, int b)
{
  return a * b;
}

int sqr(int w, int h)
{
  return mul(w, h);
}

int sqr(int w, int h)
{
  return w * h;
}

Литература: [1]

Подстановка неявных вызовов

Англ.: Indirect call promotion.

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

Примеры:

До После 
int foo(void)
{
  return 10;
}
static (int) * A(void) = foo;

int bar(void)
{
  return A();
}

int foo(void)
{
  return 10;
}
static (int) * A(void) = foo;

int bar(void)
{
  return foo();
}

Понижение силы операций

Программная конвейеризация цикла

Программная предподкачка

Разрезание цикла по условию

Раскоммутация циклов

Распространение констант

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

Раскрутка цикла

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

Англ.: Constant folding

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

Примеры:

До После 
3 + 2

5

Литература: [1]

Скрутка цикла

Слияние условных конструкций

Слияние циклов

Удаление бесконечных циклов

Удаление избыточных записей

Удаление мёртвого кода

Англ.: DCE

Удаление мёртвых циклов

Англ.: DLE

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

Англ.: CSE

Удаление недостижимых узлов

Loop Lazy Code Motion

Литература