|
Оптимізувальний компіляторОптимізувальний компілятор — компілятор, в якому використовуються різні методи отримання оптимального програмного коду при збереженні його функціональних можливостей. Найбільш поширені цілі оптимізації: скорочення часу виконання програми, підвищення продуктивності, компактифікація програмного коду, економія пам'яті, мінімізація енерговитрат, зменшення кількості операцій введення-виведення. Оптимізація може відбуватися неявно під час трансляції програми, але, як правило, вважається окремим етапом роботи компілятора. Компонувальники також можуть виконувати частину оптимізацій, таких як вилучення невикористовуваних підпрограм або їх перегрупування. Оптимізація, як правило, реалізується за допомогою послідовності оптимізувальних перетворень, алгоритмів, які приймають програму і змінюють її для отримання семантично еквівалентного варіанту, але більш ефективного з точки зору деякого набору цілей оптимізації. Було показано, що деякі проблеми оптимізації коду є NP-повними[1], або навіть нерозв'язними[2]. Проте, практично багато з них вирішуються наближеними методами, що дають цілком задовільні результати. Розрізняють низько- і високорівневу оптимізацію. Низькорівнева оптимізація перетворює програму на рівні елементарних команд, наприклад, інструкцій процесора конкретної архітектури[en]. Високорівнева оптимізація здійснюється на рівні структурних елементів програми, таких як модулі, функції, розгалуження, цикли. Типи оптимізаційМетоди, використовувані для оптимізації, можуть бути класифіковані за сферою застосування: вони можуть впливати як на окремий оператор, так і на цілу програму. Локальні методи (зачіпають невелику частину програми) простіше реалізувати, ніж глобальні (застосовувані до всієї програми), але при цьому глобальні методи часто виявляються більш вигідними. Peephole-оптимізаціяЛокальні peephole-оптимізації (англ. peephole — «вічко») розглядають кілька сусідніх (в термінах одного з графів подання програми) інструкцій (як ніби «дивиться у вічко» на код), щоб побачити, чи можна їх якось трансформувати з метою оптимізації. Зокрема, вони можуть бути замінені однією інструкцією або коротшою послідовністю інструкцій. Наприклад, подвоєння числа може бути більш ефективно виконане з використанням лівого зсуву або шляхом додавання числа з таким самим. Локальна оптимізаціяВ локальній оптимізації за один крок розглядається тільки інформація одного базового блоку[3]:404. Оскільки в базових блоках немає переходів потоку управління, така оптимізація вимагає незначного аналізу (заощаджуючи час і знижуючи вимоги до пам'яті), але це також означає, що не зберігається інформація для наступного кроку. Внутрішньопроцедурна оптимізаціяВнутрішньопроцедурні оптимізації (англ. intraprocedural) — глобальні оптимізації, що виконуються цілком в рамках одиниці трансляції (наприклад, функції або процедури)[3]: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] і зазвичай як вихідні дані розглядають пов'язані між собою граф потоку керування і граф потоку даних, а також часто дерево циклів і циклову розмітку графу потоку керування. Шляхом аналізу, зокрема пропагації інформації, на цих графах, виявляють можливість оптимізації з точки зору потрібних цілей, а потім оптимізації застосовуються.
SSA-форма і оптимізації, засновані на нійSSA (Single Static Assignment, єдине статичне присвоювання) — це форма подання графа потоку даних (DFG, Data Flow Graph), за якої кожній змінній значення присвоюється тільки один раз. Це дозволяє уникнути множення дуг у графі при багатьох записах і читаннях однієї змінної і полегшує аналіз графа. Для цього SSA-подання вводить спеціальні Phi-функції (вузли графа потоку даних) у деяких місцях сходження в графі потоку управління. Ці нові вузли є так званими псевдо-присвоюваннями. Множинні визначення можливі не тільки через сходження потоку управління («або»), але через можливість читання деякого складеного значення, як цілого, яке було записано по частинах більш, ніж однією операцією («і»). В цьому випадку для підтримки SSA-форми вводяться додаткові псевдо-присвоювання всередині базових блоків, які збирають одне значення з кількох. На SSA засновані деякі оптимізації. Хоча окремі з них можуть працювати і без SSA, найбільш ефективними вони є в присутності SSA. Див. такожПримітки
Література
Посилання |
Portal di Ensiklopedia Dunia
