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

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

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

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

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

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

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

Оптимізація потоку даних заснована на аналізі потоку даних^[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. . Архів оригіналу за 2 квітня 2005. Процитовано 25 березня 2007.  стор. 8, про еквівалентність задачі створення повністю оптимізувального компілятора проблемі зупинки
3. Cooper, Keith D.; Torczon, Linda (2004). Engineering a Compiler (англ.). Morgan Kaufmann. с. 407. ISBN 1-55860-699-8. 

Література

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

Посилання

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