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

Оптимізувальний компілятор — компілятор, в якому використовуються різні методи отримання оптимального програмного коду при збереженні його функціональних можливостей. Найбільш поширені цілі оптимізації: скорочення часу виконання програми, підвищення продуктивності, компактифікація програмного коду, економія пам'яті, мінімізація енерговитрат, зменшення кількості операцій (введення-виведення).

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

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

Розрізняють низько- і високорівневу оптимізацію. Низькорівнева оптимізація перетворює програму на рівні елементарних команд, наприклад, інструкцій процесора конкретної ^[en]. Високорівнева оптимізація здійснюється на рівні структурних елементів програми, таких як модулі, функції, розгалуження, цикли.

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

Методи, використовувані для оптимізації, можуть бути класифіковані за сферою застосування: вони можуть впливати як на окремий оператор, так і на цілу програму. Локальні методи (зачіпають невелику частину програми) простіше реалізувати, ніж глобальні (застосовувані до всієї програми), але при цьому глобальні методи часто виявляються більш вигідними.

Peephole-оптимізація

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

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

Локальна оптимізація

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

Внутрішньопроцедурна оптимізація

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

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

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

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

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

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

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

Фактори, що впливають на оптимізацію

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

Загальні принципи

Серед принципів оптимізації, що застосовуються в різних методах оптимізації в компіляторах (деякі з них можуть суперечити один одному або бути непридатними при різних цілях оптимізації):

• зменшення надмірності: повторне використання результатів обчислень, скорочення числа переобчислень;
• компактифікація коду: видалення непотрібних обчислень і проміжних значень;
• скорочення числа переходів у коді: наприклад, використання ^[en] (англ. Inline expansion) або розмотування циклу дозволяє в багатьох випадках прискорити виконання програми ціною збільшення розміру коду;
• локальність: код і дані, доступ до яких необхідний найближчим часом, повинні бути розміщені поруч одне з одним у пам'яті, щоб дотримуватися ^[en];
• використання ієрархії пам'яті: розміщення найчастіше використовуваних даних у регістрах загального призначення, менш використовуваних — у кеші, ще менш використовуваних — в оперативній пам'яті, найрідше використовувані — на диску .
• розпаралелювання: змінення порядку операцій може дозволити виконати кілька обчислень паралельно, що прискорює виконання програми.

Конкретні методи

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

^[ru]

Якщо змінна в циклі є результатом простої лінійної функції від індуктивної змінної, наприклад for (i=0; i < 10; ++i) j = 17 * i;, То можна відповідним чином оновлювати дану змінну на кожній ітерації. Це називається ^[en].

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

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

^[ru] (Злиття циклів)

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

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

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

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

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

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

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

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

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

^[ru]

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

^[en]

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

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

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

SSA-форма і оптимізації, засновані на ній

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

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

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

Див. також

• Ефективність алгоритму

Примітки

1. http://www.cs.uiuc.edu/class/fa07/cs498mjg/notes/optimizations.pdf^{[недоступне посилання]} стор. 29-30: «Register allocation», «Instruction Scheduling»
2. (PDF). Архів оригіналу (PDF) за 2 квітня 2005. Процитовано 25 березня 2007. стор. 8, про еквівалентність задачі створення повністю оптимізувального компілятора проблемі зупинки
3. Cooper, Keith D.; Torczon, Linda (2004). Engineering a Compiler (англ.). Morgan Kaufmann. с. 407. ISBN .

Література

• Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е видання. — Москва: «Вильямс», 2008. — 1184 с. — 1500 прим. — .
• Steven Muchnick, Advanced Compiler Design and Implementation — Morgan Kaufmann, 1997 —
• Keith Cooper, Linda Torczon, Engineering a Compiler, Second Edition — Morgan Kaufmann, 2011 —

Посилання

• НОУ ІНТУЇТ | Введення в оптимізацію застосунків з використанням компіляторів Intel | Інформація / Інтуїт.ру, 2011