Призначення і цілі оптимізації

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

У процесі оптимізації транслятор виконує наступні дії:

· Усуває недоліки програми, що викликані недбалістю або низькою кваліфікацією програміста. Прикладом може бути винесення з циклу операторів, що не залежать від параметрів циклу. Таке перетворення приведе до скорочення часу виконання програми, оскільки винесені оператори будуть виконуватися тільки один раз, а не багаторазово.

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

Проміжна мова

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

· по-перше, одиниці дії програми в кодах команд занадто малі, що вже саме по собі утрудняє аналіз,

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

· по-третє через нестандартність форматів різних елементів мови і рекурсивних конструкцій, широко застосовуваних у текстах програм.

Тому для оптимізації програми у процесі трансляції необхідно виконувати переворення програми з вихідної мови на проміжну. Строго сформулювати вимоги, пропоновані до проміжної мови, важко. Однак уже із самого обгрунтування необхідності проміжної мови видно, що:

а) оператори мови не повинні бути занадто дрібними;

б) символи, ідентифікатори і константи повинні мати фіксований формат;

в) в усторої операторів бажана відсутність рекурсивності;

г) повинна зберігатися вся інформація у вхідній мові, що є необхідною для оптимізації;

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

Ці вимоги свідчать, що розробити єдину універсальну проміжну мову для трансляції з будь-якої мови програмування в коди будь-якої ЕОМ важко. Як проміжну мову можна використовувати польський запис, тетради, тріади, синтаксичні дерева.

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

(mi) код операції аргументи оператора,

де mi - покажчик оператора, а також ідентифікатор результату команди при відсутності його присвоювання деякій змінній.

Необхідно розрізняти змінні, що введені програмістом (програмні змінні), і змінні, генеровані в процесі трансляції на проміжну мову (mi-ідентифікатори). Між визначенням програмної змінної і її використанням у якості операнда існує наступна залежність:

- якщо програмна змінна, використовувана в області, не визначена в ній, то передбачається, що вона визначена у всіх шляхах, що ведуть до області;

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

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

Крім програми проміжною мовою, що складається з послідовності операторів, для проведення оптимізації формуються наступні таблиці:

1. Таблиці ідентифікаторів і констант зі звичайною інформацією про змінні і константах.

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

3. Таблиця послідовності операторів, що визначає лінійну послідовність операторів у блоці. Вона містить послідовність покажчиків операторів mi. Ця таблиця необхідна, оскільки один покажчик може належати декільком операторам.

 

Елементи топології програми

6.4.1. Блок (лінійна ділянка)

 

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

Блок (лінійна ділянка) - виконувана один по одному послідовність операторів, що має єдину крапку входу - перший оператор з міткою, на який може бути передане керування, і єдину крапку виходу - останній оператор.

Блок моделює частина програми проміжною мовою, яка містить оператори присвоювання.

Формально модель лінійної ділянки може бути представлена в такий спосіб:

блок B - це трійка виду (P,I,U), де

(1) P - список операторів S1,S2,...Sn (n>=0),

(2) I - множина вхідних змінних,

(3) U - множина вихідних змінних.

При цьому оператором називається ланцюжок (у загальному випадку) виду

A <- Q B1...Br,

де A, B1,..., Br - змінні, а Q - операція.

Тут оператор привласнює значення змінній А та посилається на B1,...,Br.

Якщо оператор Sj посилається на А, то або А є вхідною змінною, або здійснене присвоювання їй значення деяким оператором до Sj, (тобто деяким оператором Si, (і<j). Таким чином, усередині блоку всі змінні, на які є посилання, до цього моменту визначені або внутрішнім чином як змінні, котрим привласнені значення, або зовнішнім як вхідні змінні. Аналогічно кожна вихідна змінна або є вхідною змінною, або їй привласнене значення деяким оператором.

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

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

 

Сильно зв'язана область

 

Для кожного блоку B=(P,I,U) можна знайти орієнтований ациклічний граф, що представляє цей блок. При цьому кожен лист графа (кінцева вершина) відповідає одній вхідний змінній у I, а кожна його внутрішня вершина - оператору з P. Граф відбиває порядок виконання операторів програми і дає більш наочне представлення, ніж лінійна послідовність операторів.

Якщо вершини і та j графа відповідають ділянкам і та j програми, то дуга йде з і в j, якщо

1) останній оператор ділянки і не є ні оператором переходу, ні оператором зупинки, а ділянка j йде в програмі за ділянкою і чи

2) останній оператор ділянки і є оператором переходу на мітку L, що позначений перший оператор ділянки j.

Сильно зв'язаною областю орієнтованого графа називається така множина його вершин, що для будь-яких двох вершин x і y (x!= y) існує шлях з x у y.

Будемо розглядати сильно зв'язані області Ri, що володіють наступними властивостями:

1) Ri є сильно зв'язаною областю, що складається з множини блоків, кожний з яких передує сам собі і йде сам за собою усередині цієї множини;

2) Ri!= Rj;

3) для кожного і<j чи перетинання Ri і Rj порожньо, чи Ri є підобластю Rj (включена в неї).

 

Способи оптимізації

 

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

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

- розвантаження ділянок повторюваності;

- спрощення дій;

- реалізація дій;

- чищення програми;

- економія пам'яті;

- скорочення програми.