Оптимізувальний компілятор

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

Наприклад, подвоєння числа може бути більш ефективно виконане з використанням лівого зсуву або шляхом додавання числа з таким самим.

В локальній оптимізації за один крок розглядається тільки інформація одного базового блоку[3]^:404</ref>. Оскільки в базових блоках немає переходів потоку управління, така оптимізація вимагає незначного аналізу (заощаджуючи час і знижуючи вимоги до пам'яті), але це також означає, що не зберігається інформація для наступного кроку.

Внутрішньопроцедурні оптимізації (англ. intraprocedural — глобальні оптимізації, що виконуються цілком в рамках одиниці трансляції (наприклад, функції або процедури)[3]^:407. За такої оптимізації опрацьовується значно більше інформації, ніж за локальної, що дозволяє досягати більш значного ефекту, але при цьому часто потрібні ресурсовитратні обчислення. За наявності у оптимізовуваній програмній одиниці глобальних змінних оптимізація такого виду може бути утруднена.

Існує значна кількість оптимізацій, що застосовуються до циклів. За великої кількості повторень циклу такі оптимізації надзвичайно ефективні, оскільки невеликим перетворенням впливають на значну частину виконання програми. Оскільки цикли — вагома частина часу виконання багатьох програм, оптимізації циклів існують практично у всіх компіляторах і є найважливішими.

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

Такі види оптимізацій аналізують відразу весь сирцевий код програми. Більша кількість інформації, що отримується даними методами, означає що оптимізації можуть бути більш ефективними в порівнянні з іншими методами. Такі оптимізації можуть використовувати досить складні методи, наприклад, виклик функції заміщається копією тіла функції (вбудовування або 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;, То можна відповідним чином оновлювати дану змінну на кожній ітерації. Це називається зниженням сили операцій.

Розподіл циклу на частини

Робиться спроба розділити цикл на кілька окремих з тим самим діапазоном індексів. Кожен новий цикл є частиною тіла вихідного циклу. Це може поліпшити локальність посилань.

Об'єднання циклів (Злиття циклів)

Інший метод, покликаний зменшити накладні витрати циклу. Якщо два сусідніх цикли повторюються однакове число разів, то їх тіла можуть бути об'єднані якщо, вони не взаємодіють.

Інверсія циклу

Цей метод змінює стандартний while цикл на цикл do / while, поставлений під деяку умову, що зменшує кількість переходів на два, для випадків, коли цикл виконується.

Розщеплення циклу

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

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

Усунення спільних підвиразів

Видалення спільних підвиразів — оптимізація компілятора, за якої шукаються примірники однакових виразів і аналізується можливість заміни їх однією змінною, що містить обчислене значення.

Згортання констант

Оптимізація, за якої зменшуються надлишкові обчислення, шляхом заміни константних виразів і змінних їх значеннями.

Аналіз індуктивних змінних

Див. опис в оптимізації циклів .

Видалення тупикових записів

Видалення присвоєнь змінних, які згодом не читаються. Присвоєння видаляється або через те що до кінця часу життя змінної вона не була прочитана, або через те що подальше присвоєння її перезапише.

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

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

На SSA засновані деякі оптимізації. Хоча окремі з них можуть працювати і без SSA, найбільш ефективними вони є в присутності SSA.