Зміст
1.Призначення і мети оптимізації
2.Промежуточний мова
3.Елементи топології програми
3.1. Блок (лінійний ділянка)
3.2. Сильно пов'язана область
4.Способи оптимізації
4.1. Розвантаження ділянок повторюваності
4.1.1 Зрушення інваріантних операторів
4.1.2. Скорочення глибини операції
4.2. Спрощення дій
4.2.1. Видалення індуктивних змінних і виразів
4.2.2. Заміна складних операцій на більш прості
4.2.3. Виняток надлишкових виразів
4.2.4. Інші перетворення
4.3. Реалізація дій
4.3.1. Підстановка (згортка)
4.4. Частка програми
4.4.1. Усунення ідентичних операторів
4.4.2. Заміна змінних в операторах умовного переходу та усунення зайвих визначень
4.4.3 Усунення марних операторів та змінних
4.5. Економія пам'яті
4.6. Скорочення програми
4.7. Вставка псевдоблока
5.Последовательность застосування оптимізують перетворень
1. Призначення та цілі оптимізації
Завжди бажано мати компілятор, який створює ефективно працюють об'єктні програми. Як правило, програма в кодах машини, отримана в результаті трансляції, буде займати більший об'єм пам'яті і працювати повільніше, ніж така ж програма, написана досвідченим програмістом. Термін "оптимізація" застосовується до спроб зробити вихідні програми більш "ефективними", тобто швидше працюють або більш компактними. Таким чином, оптимізацією називається поліпшення вихідний програми, а частина транслятора, яка виконує цю функцію
- Оптимізує частиною транслятора.
Оптимізує частина транслятора виконує наступні
дії:
1. Усуває недоліки програми, викликані недбалістю або низькою кваліфікацією програміста. Прикладом може служити винесення з циклу операторів, що не залежать від керуючих змінних циклу, що призведе до скорочення часу виконання програми, оскільки винесені оператори будуть виконуватися тільки один раз, а не багато разів.
2. Усуває зайві обчислення, неминуче виникають у процесі трансляції навіть при самому ретельному написанні програми на мові високого рівня. Наприклад, усунення повторного обчислення індексних виразів для елементів масиву скорочує час виконання програми та її довжину.
2. Проміжний мова
Для підвищення ефективності програми можна здійснити над нею послідовність перетворень в різні моменти процесу компіляції. Наприклад, можна оперувати з вхідною програмою, зі структурами, породжуваними на стадії синтаксичного аналізу, з кодом, породжуваним як вихід фази генерації коду. Однак оптимізувати програму, вже протранслірованную в коди машини, важко з таких причин:
по-перше, одиниці дії програми в кодах команд занадто дрібні, що вже саме по собі ускладнює аналіз,
по-друге, при трансляції вхідний програми в коди машини можлива втрата наявної в ній інформації. Наприклад, засилання проміжних результатів у різні робочі комірки пам'яті робить практично неможливою ідентифікацію однакових частин програми;
по-третє через нестандартність форматів різних елементів мови і рекурсивних конструкцій, широко використовуваних у текстах програм.
Тому, якщо транслятор виробляє оптимізацію програми, необхідно робити спеціальний прохід, що переводить програму з вихідного мови на проміжний.
Чітко сформулювати вимоги, що пред'являються до проміжного мови, важко. Проте вже з самого обгрунтування необхідності проміжного мови видно, що:
а) оператори мови не повинні бути занадто дрібними;
б) символи, ідентифікатори і числа повинні мати фіксований формат;
в) в будові операторів бажано відсутність рекурсивного;
г) повинна зберігатися вся інформація, необхідна для оптимізації, яка є у вхідному мовою;
д) мова має бути пристосований до виконання оптимізують перетворень і зручний для подальшої трансляції в коди обчислювальної машини.
Вимоги пп. "г" і "д" показують, що розробити єдиний універсальний проміжна мова для трансляції з будь-якої мови програмування в коди будь-обчислювальної машини важко. В якості проміжного мови можна використовувати польську запис, тетради, тріади, синтаксичні дерева.
При розгляді питань оптимізації будемо вважати, що програма протранслірована з вхідного на деякий проміжний мова, оператор якого має наступний загальний вигляд:
(mi) код операції аргументи оператора,
де mi - покажчик оператора, а також ідентифікатор результату команди за відсутності його привласнення деякої змінної.
Необхідно розрізняти змінні, введені програмістом (програмні змінні), і змінні, що генеруються в процесі
трансляції на проміжний мова (mi - ідентифікатори). Тим
визначенням програмної змінної та її використанням як операнда існує наступна залежність:
- Якщо програмна змінна, яка використовується в області, не визначені в ній, то передбачається, що вона визначена на всіх дорогах, що ведуть до області;
- Якщо програмна мінлива визначена і використовується в області, то всередині області існує шлях між визначенням змінної і кожним її використанням;
- Якщо програмна мінлива визначена в області, то, взагалі кажучи, це не означає, що вона визначена на кожному вихідному шляху.
Крім програми на проміжному мовою, що складається з послідовності операторів, для проведення оптимізації формуються наступні таблиці:
1. Таблиці ідентифікаторів і констант зі звичайною інформацією про змінних і константи.
2. Таблиця блоків, що визначає номери блоків (блоки Нумеа-
руются в довільному порядку), їх межі, безпосередньо попередні і наступні блоки, а також будь-яку інформацію про частоту повторення блоку.
3. Таблиця послідовності операторів, що визначає лінійну послідовність операторів у блоці. Вона містить послідовність покажчиків операторів mi. Ця таблиця необхідна, оскільки один вказівник може належати декільком операторам.
3.Елементи топології програми
3.1. Блок (лінійний ділянка)
Питання оптимізації зазвичай пов'язані з топологією програми, тобто зі способом її побудови. Для того, щоб локалізувати процеси оптимізації і не зв'язувати їх з конкретним вхідним мовою, вони проводяться всередині окремих ділянок програми, які називаються блоками і сильно пов'язаними областями.
Блок (лінійний ділянка) - виконується по порядку послідовність операторів, що має єдину точку входу - перший оператор з міткою, на який може бути передано управління, і єдину точку виходу - останній оператор.
Блок моделює частину програми на проміжному мовою, яка містить оператори присвоювання.
Формально модель лінійного ділянки може бути представлена наступним чином:
блок B - це трійка виду (P, I, U), де
(1) P - список операторів S1, S2, ... Sn (n> = 0),
(2) I - безліч вхідних змінних,
(3) U - безліч вихідних змінних.
При цьому оператором називається ланцюжок (у загальному випадку) виду
A
де A, B1 ,..., Br - змінні, Q - операція.
Тут оператор присвоює значення змінної А і посилається на B1 ,..., Br.
Якщо оператор Sj посилається на А, то або А - вхідна змінна, або здійснено присвоєння їй значення деяким оператором до Sj, (тобто деяким оператором Si, (i
Оператор S в програмі називається входом в лінійний ділянку, якщо він або перший оператор у програмі, або позначений кодом, які з'являтимуться в операторі переходу, або безпосередньо слідує за умовним оператором.
Лінійний ділянку, що відноситься до входу в ділянку S, складається з S і всіх операторів, наступних за ним аж до оператора зупину, включаючи його, або аж до входу в наступний блок.
3.2. Сильно пов'язана область
Для кожного блоку B = (P, I, U) можна знайти орієнтований ациклічні граф, який представляє цей блок. При цьому кожен лист графа (концевая вершина) відповідає одній вхідний змінної в I, а кожна його внутрішня вершина - оператору з
P. Граф відображає порядок виконання операторів програми і дає більш наочне уявлення, ніж лінійна послідовність операторів.
Якщо вершини i і j графа відповідають ділянкам i і j програми, то дуга йде з i в j, якщо
1) останній оператор ділянки i не є ні оператором переходу, ні оператором зупину, а ділянка j слід у програмі за ділянкою i або
2) останній оператор ділянки i є оператором переходу на мітку L, якій позначено перший оператор ділянки j.
Сильно пов'язаної областю спрямованого графа називається така множина його вершин, що для будь-яких двох вершин x і y (x! = Y) існує шлях з x в y.
Будемо розглядати сильно пов'язані області Ri, що володіють такими властивостями:
1) Ri є сільносвязанной областю, що складається з безлічі блоків, кожен з яких передує сам собі і слід сам за собою всередині цієї безлічі;
2) Ri! = Rj;
3) для кожного i
4. Способи оптимізації
Розрізняють дві категорії оптимізують перетворень: перетворення початкової програми в її внутрішню форму, які не залежать від об'єктного мови (машинно-незалежні) і перетворення, які здійснюються на рівні об'єктної програми (машинно-орієнтовані).
Методи першої категорії застосовні майже до будь-якого алгебраїчному мови - ФОРТРАНу, Алгол, PL/1 і.т.д.
На практиці використовується досить широкий набір машинно-незалежних оптимізують перетворень, що пов'язано з великою різноманітністю неоптимальною. До них відносяться:
- Розвантаження ділянок повторюваності;
- Спрощення дій;
- Реалізація дій;
- Чищення програми;
- Економія пам'яті;
- Скорочення програми.
4.1. Розвантаження ділянок повторюваності
Таку назву отримав спосіб оптимізації, що складається у винесенні обчислень з багаторазово проведених (виконуваних) дільниць програми на ділянки програми, рідко прохідні.
До цього виду перетворень відносяться різні чистки зон, тел циклів і тіл рекурсивних процедур, коли інваріантні (за результатом виконання) у відповідних ділянках повторюваності вирази, лінійні компоненти (тобто гамаки, обов'язково виконуються при кожному проходженні ділянки повторюваності) виносяться з нього і розміщуються перед входом до дільниці повторюваності - чистка вгору, - або коли знищують свої попередні результати лінійні компоненти або групи лінійних компонент ділянки повторюваності виносяться з нього і розміщуються за виходи з дільниці повторюваності - чистка вниз.
При чищенні вгору винесені обчислення утворюють новий обов'язковий безпосередній попередник ділянки повторюваності, а при чищенні вниз - безпосередній обов'язковий наступник ділянки повторюваності.
Зазвичай виносяться тільки такі вирази і лінійні фрагменти програми, які обов'язково виконуються при кожному проходженні розвантажуємо ділянки повторюваності.
Приклади.
а) Частка вниз перетворить цикл
для K: = 1, K 1 поки K
цикл
початок
X: = X * K;
якщо Z> 0 то Y: = sin (X);
інакше A [I]: = X 2;
кінець
до виду
для K: = 1, K 1 поки K
цикл X: = X * K;
якщо Z> 0 то Y: = sin (X);
інакше A [I]: = X 2;
б) Частка вгору перетворить цикл
для K: = 1, K 1 поки K
цикл
початок
якщо Z> 0 то Y: = 1;
інакше Y: = Z 2;
X [K]: = X [K] - Y; кінець
до виду
якщо Z> 0 то Y: = 1;
інакше Y: = Z 2;
для K: = 1, K 1 поки K
цикл X [K]: = X [K] - Y;
Прикладом чищення тіла рекурсивної функції може бути наступний:
тіло рекурсивної функції
цілий функція Ф (N)
початок
цілі Z, W;
W: = 1;
якщо X> 0 то W: = Y;
якщо N
інакше
початок
Z: = N-W; Ф: = Z * Ф (Z) кінець
кінець
містить два інваріантних гамака, в результаті винесення яких може бути отримана наступна функція:
цілий функція Ф (N)
початок
ціле N;
цілий функція F (M)
початок
ціле Z;
якщо M
інакше
початок
Z: = M-W; F: = Z * F (Z) кінець
кінець
W: = 1;
якщо X> 0 то W: = Y;
Ф: = F (N); кінець;
До групи розвантажень ділянок повторюваності також входять і різні перетворення, які здійснюють переміщення гамака по шляху, що веде до місця використання його результатів. При такому перетворенні на відміну від чисток гамак залишається в тих же зонах, циклах і процедурах.
Наприклад, за допомогою цих перетворень фрагмент
для K: = 1, K 1 поки K
цикл
початок
N: = A [K];
якщо N> 0 то перехід на L; N: = N * N;
L: якщо Z = 0 то ВИСНОВОК (N); кінець
N: = 100;
може бути перетворений до виду:
для K: = 1, K 1 поки K
цикл
якщо Z = 0 то
початок
N: = A [K];
якщо N> 0 то перехід на L; N: = N * N;
L: ВИСНОВОК (N); кінець;
N: = 100;
4.1.1 Зрушення інваріантних операторів
Розглянемо докладніше перетворення зсуву інваріантних операторів, що входить до групи перетворень з розвантаження ділянок повторюваності.
Оператор інваріантний і може бути винесений з блоку, якщо він задовольняє таким умовам:
1) зрушення оператора не призводить до того, що результат зрушуваної оператора переміщується через оператор, в якому результат використовується.
Наприклад, для блоку
(mi) * A, B
.
.
.
(mk): = C, (mi)
якщо ні A, ні B не визначаються в області, то оператор mi може бути зміщений вниз, але не може бути поставлений після оператора mk.
2) зрушення оператора не призводить до того, що між визначенням змінної та її використанням як операнда з'являється новий оператор, що присвоює цієї змінної інше значення. Наприклад, для блоку
(mi): = A, 1
.
.
(mj): = A, 10
.
.
(mk): = C, A
якщо більше ніякої оператор після mj не привласнює значення змінної A, то оператор mj може бути зміщений вниз, але не може бути поставлений після оператора mk, операторами mi, а також вгору, але не вище оператора, який використовує значення змінної A, присвоєне оператором mi.
3) зсув оператора не порушує зв'язку між зрушуваної оператором і оператором, що використовують результат зсувається в якості операнда.
Таким чином, оператор інваріантний в області, якщо його операнди не залежать від місця визначення змінних в даній області.
Як уже зазначалося, зрушення інваріантного оператора з тіла циклу скорочує час виконання програми. Особливість розглянутого методу полягає в тому, що оператор зсувається з блоку у всіх випадках, коли він може бути зміщений незалежно від того, знаходиться вона всередині циклу чи ні. Погіршення програми відбутися не може.
Необхідно також відзначити, що перед зрушенням інваріантних операторів потрібно усунути ідентичні оператори (про це мова піде пізніше), тому що вони можуть виявитися перешкодою для
зсуву операторів.
Розглянемо умови, достатні для зрушення операторів
I. Зрушення оператора, який не є оператором присвоювання, з області тому (на його вхідні шляхи) проводиться, якщо операнди оператора не залежать від місця визначення змінних в області, тобто:
1) mi - ідентифікатори, що використовуються як аргумент оператора, не визначені в блоці жодним попереднім оператором;
2) програмні змінні оператора не визначені в області.
Якщо обидва ці умови виконуються, то операнди оператора не залежать від місця визначення змінних в області.
II. Зрушення оператора присвоєння, з області тому (на його вхідні шляхи) здійснюється, якщо:
1) mi - ідентифікатори, що використовуються як аргумент оператора, не визначені в блоці жодним попереднім оператором;
2) програмні змінні, використовувані як операнда оператора не визначені в області;
3) блок є артикуляційних, тобто лежить на перетині всіх вхідних або всіх вихідних шляхів сильно пов'язаної області;
4) не існує іншого визначення або використання програмної змінної на будь-якому шляху від входу в область до цього визначення.
III. Зрушення оператора, який не є оператором присвоювання, з області вперед (на його вихідні шляху) здійснюється, якщо:
1) mi - ідентифікатори, що використовуються як аргумент оператора, не перевизначаються ні на одному шляху між оператором і точкою виходу з області;
2) програмні змінні, що використовуються як аргумент оператора не перевизначаються ні на одному шляху між оператором і точкою виходу з області;
3) mi - дороговказ, який є результатом дії оператора, не використовується на шляху між оператором і кінцем блоку.
IV. Зрушення оператора присвоєння, з області тому (на його вхідні шляхи) здійснюється, якщо:
1) mi - ідентифікатори, що використовуються як аргумент оператора, не перевизначаються ні на одному шляху між оператором і точкой виходу з області;
2) програмні змінні, що використовуються як аргумент оператора не перевизначаються ні на одному шляху між оператором і точкою виходу з області;
3) блок є артикуляційних пунктом області;
4) не існує іншого визначення
програмної змінної ні на одному шляху між визначенням і
точкою виходу з області;
5) програмна мінлива не використовується в області.
4.1.2. Скорочення глибини операції
Скорочення глибини операції - процедура винесення за межі циклу операторів, аргументи яких є функціями рекурсивно визначених змінних, і заміна їх в середині циклу простими рекурсивними операторами присвоювання, аргументи яких не залежать від інших змінних.
Сенс цієї операції в тому, що вона дозволяє виносити з циклу навіть ті оператори, операнди яких залежать від керуючої змінної циклу. На відміну від зсуву інваріантних операторів при скороченні глибини операції зрушуваної оператори замінюються більш простими і швидше виконуваними операторами
Наведемо приклад скорочення глибини операції стосовно до оператора t4: = K * 10 + I з n-го блоку:
n-й блок
L: t4: = K * 10 + I t5: = t6 + K z (t2): = z (t2) + x (t4) + y (t5) K: = K +1
перехід на L
в результаті виконання цієї операції оператор t4: = K * 10 + I зсувається в (n-1)-й блок, а в n-му блоці він замінюється оператором t4: = t4 10:
(n-1)-й блок
. . .
t4: = K * 10 + I
n-й блок
L: z (t2): = z (t2) + x (t4) + y (t5)
K: = K +1 t4: t4 = 10 t5: = t6 + K перехід на L
4.2. Спрощення дій
Даний спосіб оптимізації орієнтований на поліпшення програми за рахунок заміни груп (як правило, віддалених один від одного) обчислень на групу обчислень, що дають той же результат з точки зору всієї програми, але мають меншу складність.
4.2.1. Видалення індуктивних змінних і виразів
Ряд перетворень цього типу пов'язаний з так званими індуктивними (або лінійно-рекурсивними) обчисленнями в ділянці повторюваності програми, тобто тими, значення яких регулярно ізмененяются від повторення до повторення.) Такими перетвореннями є видалення індуктивних змінних, що означає заміну декількох індуктивних змінних циклу однієї індуктивного змінної, а також видалення індуктивних виразів з циклу.
Наприклад, застосування зазначених перетворень переводить фрагмент
для I: = 1, I 1 поки I
цикл
початок
K: = I + J; A [K]: = A [K] 1 кінець;
K: = 10;
під фрагмент
I: = 1;
для K: = I + J, K +1 поки K
цикл
початок
A [K]: = A [K] 1 кінець;
K: = 10;
Тут I, K - індуктивні змінні. У даному випадку з циклу видалено індуктивне вираз K: = I + J.
4.2.2. Заміна складних операцій на більш прості
Дуже важливим перетворенням з цієї групи є зниження сили операцій, що замінює в індуктивних обчисленнях складні операції на більш прості; наприклад, зведення в ступінь або поділ замінюється множенням (наприклад, вираз Х/4.О замінюється на вираження Х * О.25), а множення - складанням.
Наприклад, застосування цього перетворення дозволяє переходити від циклу
для K: = 1, K 1 поки K
цикл V: = (K-1) * N + I
до більш ефективно працює фрагментом:
V: = I;
для K: = 1, K 1 поки K
цикл
початок A [V]: = A [V] 1;
V: = V + N кінець
Заміна складних операцій на більш прості не завжди призводить до оптимізації, насправді це може навіть призвести до уповільнення, наприклад, для програм з циклами, що складаються з декількох частин, з яких лише деякі виконуються на кожному кроці циклу.
4.2.3. Виняток надлишкових виразів
До групи перетворень щодо спрощення дій входять також виключення надлишкових (зайвих) виразів. Воно полягає в заміні входжень виразів на змінну, значення якої таке саме, як вираження.
Наприклад, ця операція здійснює перехід від фрагмента
якщо B> 0 то
початок
A: = A 2; X: = A * B + C; кінець
інакше Y: = A * B + D;
Z: = A * B;
до фрагмента
якщо B> 0 то
початок
A: = A 2; W: = A * B; X: = W + C; кінець
інакше початок
W: = A * B; Y: = W + D; кінець;
Z = W;
4.2.4. Інші перетворення
У цю ж групу входить
економія загальних подвираженій, що замінює, наприклад, оператор
X: = (A + B) * (A + B + C)/(A + B + E) на фрагмент
Y: = A + B; X: = Y * (Y + C)/(Y + E),
а також такі перетворення, як втягування обчислення параметрів в процедуру, спрощення підстановки параметра-масиву, перебудови умовних операторів (типу заміни оператора
якщо X> 0 & & Y
на оператор
якщо X> 0 то початок якщо Y
віддалене копіювання (зокрема, що заміняє пересилання значен-
ний масиву на пересилання його покажчика), інші різні
способи перебудови структури інформаційних об'єктів в за-
лежно від характеру їх використання і з метою скорочення
часу роботи з об'єктами; різні способи реалізації пере-
сних через швидкі регістри, заміна рекурсії на цикли.
Інші оптимізують перетворення, що спрощують
дії, - це перетворення з об'єднання і з розчленовування
циклів, за перестановці заголовків циклів.
4.3. Реалізація дій
Це спосіб підвищення якості програми за рахунок виконання певних її обчислень на етапі трансляції.
Набір перетворень даного типу включає в себе наступні оптимізації:
константні дії (підстановка або згортки констант), коли відбувається виконання операцій над константами;
распроцедуріваніе - відкрита підстановка тіла процедури на місце її виклику;
ліквідація константних розпізнавачем - заміна умовного
оператора на одну з його гілок, якщо його вибирають (умовна) вираз має константні значення.
Реалізація дій здійснюється також при
- Втягування констант, коли вираження, що мають тотожне константні значення, замінюються на ці значення; при аналітичних перетворення (наприклад, замінюють Е * 1 або на Е 0 * Е на 0, де Е - довільне подвираженіе);
- Ототожненні (або втягування унікальних), що видаляє з програми оператор-пересилання виду X: = Y, де X і Y - змінні, замінюючи або входження X на Y - втягування вгору (назад) - наприклад, фрагмент Y: = F (W ); X: = Y; замінюється на X: = F (W), або входження Y на X - втягування вниз (уперед) - наприклад, X: = Y; якщо Z> 0 то W: = Y 1 інакше W: = Y 2 замінюється на фрагмент якщо Z> 0 то W: = X +1 інакше W: = X 2.
4.3.1. Підстановка (згортка)
Операції, операнди яких відомі під час компіляції, немає необхідності виконувати під час рахунку.
Підстановка (згортка) - це заміна змінної або mi-ідентифікатора результату заданої або обчисленої константою, причому ця заміна відбувається під час трансляції, а не в процесі вирішення.
Згортка головним чином застосовується до арифметичним операторам +,-,*,/, тому вони найбільш часто використовуються у вихідній програмі.
Наприклад, для лінійного ділянки
А: = 1 +1
А: = 3
В: = 7 + А,
представленого на проміжному мові у вигляді тріад:
(1) + 1,1 (2): = (1), А
(3): = 3, А (4) + 7, (3)
(5): = (4), В
1-у тріаду можна вирахувати на компіляції і замінити на результуючу константу, аналогічно можна обчислити 4-у тріаду
.
Виходить такий результат згортки:
(1): = 2, А (2): = 3, А (3): = 10, В
Підстановка є повністю внутрішньоблокових процедурою виконується перед усуненням зайвих команд.
При виконанні операції підстановки для кожного блоку створюється спеціальна таблиця поточних значень змінних, якими виробляється присвоювання.
Зазвичай згортка здійснюється лише в межах лінійного ділянки за допомогою спеціальної таблиці Т, спочатку порожній. У процесі згортки Т містить пари (А, К) для всіх простих змінних А, для яких відомо поточне значення К. Крім того, якщо програма у внутрішньому представленні представлена, наприклад, у вигляді тріад, то кожна згортається тріада замінюється
нової тріадою (С, К, 0), де С (константа) - новий оператор, для
якого не потрібно генерувати команди, а К - результуюче
значення згорнутої тріади.
Алгоритм згортки послідовно переглядає тріади лінійного ділянки і для кожної тріади робить наступне:
1) Якщо операнд є змінна, яка міститься в таблиці Т, то операнд замінюється на відповідне значення К.
2) Якщо операнд є посилання на тріаду типу (С, К, 0), то операнд замінюється на константу К.
3) Якщо все операнди є константами і операція може бути згорнута, то ця тріада виповнюється і замість неї підставляється тріада (С, К, 0), де К - результуюче значення.
4) Якщо тріада є присвоюванням А: = У значення змінної без індексу А, то:
а) якщо В - константа, то А зі значенням У заноситься в таблицю Т (старе значення А, якщо воно було, виключається);
б) якщо В - не константа, то А зі своїм значенням виключається з Т, якщо вона там була.
4.4. Частка програми
Даний спосіб підвищує якість програми за рахунок видалення з неї непотрібних об'єктів і конструкцій.
Набір перетворень цього типу містить у собі наступні оптимізації:
- Видалення ідентичних операторів;
- Видалення з програми операторів, недосяжних з управління від початкового;
- Видалення перетворювачів, інформаційно не впливають на інші оператори;
- Видалення несуттєвих операторів, тобто операторів, які не впливають на результат програми;
- Видалення непотрібних операторів, тобто операторів, обчислюється так звані мертві в цьому операторі змінні (мінлива жива, чи зайнята в деякій точці програми, якщо з цієї точки існує шлях до будь-якого використання цієї змінної, що не містить операторів, які задають їй нове значення; якщо такого шляху не існує, то мінлива називається мертвою, або вільною в цій точці);
- Видалення процедур, до яких немає звернень;
- Видалення зайвих змінних, видів, операцій і т. д.
4.4.1. Усунення ідентичних операторів
i-та операція вважається зайвою, якщо існує більш рання ідентична j-та операція і ніяка змінна, від якої залежить ця операція, не змінюється третьою операцією, що лежить між i-тій і j-тої операціями.
Оператор F вважається ідентичним і може бути усунений з програми, якщо існують інші оператори G1, G2, ... Gn, такі, що
1) оператор F і всі оператори G1, G2, ... Gn виконують одну і ту ж операцію над одними і тими ж операндами;
2) не існує шляху від присвоювання значень операндів оператора F до самого оператора F, який не проходив би сну-
чала через оператори G.
Наприклад, для лінійного ділянки:
Е: = Е + С * В
А: = Е + С * В
З: = Е + С * В,
представляється на проміжному мові у вигляді тріад наступним чином:
(1) * С, В (4) * С, В (7) * С, В
(2) + Е, (1) (5) + Е, (4) (8) + Е, (7)
(3): = (2), Е (6): = (5), А (9): = (8), З
поява операції С * У в другій і третій раз зайве, тому що ні С, ні В не змінюються після 1-ї тріади.Однако другу складання Е з С * У (5-а тріада) не є зайвим, тому що після першого складання Е з С * У 3-я тріада змінює значення Е. Але третій складання Е з С * У зайве і може бути замінено посиланням на 5-у тріаду.
Алгоритм виключення зайвих операцій переглядає операції в порядку їх появи. Якщо i-я тріада зайва (вже є ідентична j-я тріада), то вона замінюється тріадою (SAME, j, 0), де операція SAME нічого не робить і не породжує ніяких команд при генерації. Щоб стежити за внутрішньою залежністю змінних і тріад, їм у відповідність ставляться числа незалежності за наступними правилами:
1) Спочатку для змінної А число незалежності dep (А) дорівнює нулю, так як її початкове значення не залежить ні від однієї тріади.
2) Після обробки i-й тріади, в якій змінною А привласнюється деяке значення, dep (А) замінюється на i, так як її нове значення залежить від i-й тріади.
3) При обробці i-й тріади її число незалежності dep (i) дорівнює 1 + (максимальне з чисел залежності її операндів).
Числа залежності використовуються в такий спосіб: якщо i-а тріада ідентична j-й тріаді (j
Алгоритм виключення зайвих операцій для кожної тріади робить наступне:
1. Якщо операнд посилається на тріаду виду (SAME, j, 0), то він замінюється на (j).
2. Обчислюється dep (i): = число незалежності i-й тріади, рівне 1 + (максимум чисел незалежності її операндів).
3. Якщо існує ідентична j-я тріада, причому j
4. Якщо i-я тріада присвоює значення елементу масиву В або простий змінної В, то dep (В) отримує значення, рівне
i.
4.4.2. Заміна змінних в операторах умовного переходу та усунення зайвих визначень
У результаті скорочення глибини операції рекурсивна програмна мінлива (визначена через саму себе), що є керуючою в оператора умовного переходу, може бути замінена в ньому генерується змінної t (mt-кодом).
Це в свою чергу може призвести до того, що рекурсивно певна програмна мінлива використовуватися в блоці не буде і саме визначення може бути усунуто.
Визначення не використовується і може бути усунуто, якщо результат визначення не є операндом ні одного оператора рекурсивного визначення і результат цього останнього не використовується ні в якому іншому операторі.
Існування невикористовуваних визначень до оптимізації є помилкою програміста. Але після оптимізації такі визначення можуть виникнути як результат перестановки та зміни окремих операторів у процесі оптимізації.
Для даного визначення в даному блоці проводиться пошук використання цього визначення у всіх подальших командах блоку і у всіх блоках, які можуть слідувати за нім.Поіск припиняється, коли знаходиться оператор, що використовує дане визначення як аргумент. Якщо такий оператор в цьому і наступних блоках знайдений не буде, то визначення вважається невживаних і усувається.
Як тільки Коли визначення усунуто, всі оператори, від яких залежав усунених оператор, якщо вони ніде більше не використовуються, можуть бути усунені.
4.4.3 Усунення марних операторів та змінних
Якщо блок містить такий оператор S, що змінна, якій присвоюється значення в S, не є активною після цього оператора, то S - даремний оператор. Іншими словами, S
- Марний оператор, якщо він привласнює значення змінної, яка не є вихідний і на яку немає посилання в наступних операторах.
Мінлива А називається активною після виконання оператора Si, якщо
- Їй присвоєно значення оператором Si;
- Їй не присвоєно значення операторами Si 1, ... Sj;
- На неї посилається оператор Sj 1.
Якщо оператор Si привласнює значення змінної А і вона неактивна після моменту i, то
- При i> 0 можна видалити Si з P
- При i = 0 можна видалити A з I
Наприклад, нехай B = (P, I, U), де I = A, B, C, U = F, C і P складається з
F: = A + A
G: = F * C
F: = A + B
G: = A * B
Другий оператор даремний, тому що його область дії порожній. Таким чином, одне застосування перетворення усунення непотрібних операторів відображає B в B1 = (P1, I, U), де P1 складається з
F: = A + A
F: = A + B
G: = A * B
Тепер в B1 марна вхідна мінлива C і перший оператор. Застосувавши той же перетворення, можна отримати B2 = (P2, A, B, U), де P2 складається з
F: = A + B
G: = A * B
4.5. Економія пам'яті
Це спосіб покращення програми за рахунок зменшення обсягу пам'яті, що відводиться під інформаційні об'єкти програми в кожному з її можливих виконань.
У відповідну групу оптимізацій входять наступні перетворення:
- Глобальна економія пам'яті, тобто суміщення по пам'яті не існують одночасно статичних змінних;
- Зміна області існування автоматичної змінної;
- Переміщення оператора відведення пам'яті під керовану змінну по шляху, що веде до кінцевого оператору програми;
- Поєднання по пам'яті динамічних інформаційних об'єктів, наприклад, заміна стека локальних змінних або параметрів, що втягуються в рекурсію, одинарною змінної. Прикладом виконання цього перетворення є заміна функції
цілий функція F (N, M)
початок
ціле K;
якщо N = M
то F: = 1
інакше
початок
K: = M +1; F: = F (N, K) * K кінець
кінець
на функцію
цілий функція F (N, M) початок
цілий функ G (Z);
початок
ціле K
якщо N = Z
то F: = 1
інакше
початок
K: = Z 1; F: = F (K) * K кінець
кінець
F: = G (N) кінець;
4.6. Скорочення програми
При даному способі поліпшення програми досягається за рахунок скорочення її розміру.
До перетворень цього типу відноситься чистка лінійного ділянки, при якій в початкову (або в кінцеву) його вершину виносяться і замінюються на один екземпляр що є на всіх дорогах в блоці однакові конструкції. Наприклад,
якщо A> 0
то
початок
X: = X 3
Z: = 2 кінець
інакше початок X: = X 3 W: = X 4 кінець
перетвориться до виду
X: = X 3 якщо A> 0 то Z: = 2 інакше W: = X 4
До цієї ж групи входить і запроцедуріваніе - пошук в програмі схожих фрагментів та формування їх у вигляді процедури.
4.7. Вставка псевдоблока
У процесі проптімізаціі оператори, зрушуваної з блоків, збираються в псевдоблок. Після оптимізації області Rk оператори псевдоблока повинні бути вставлені в програму так, щоб вони виконувалися до (після) виконання операторів області Ri.
Для того, щоб оператори псевдоблока виконувалися на всіх вхідних (виходи) шляхах області Rk, вони повинні вставлятися в усі блоки, що безпосередньо передують (наступні) області небудь з псевдоблока повинен бути сформований блок, який буде вставлений на всі вхідні (вихідні) шляхи області Rk .
Вставка операторів в існуючі блоки або формування з псевдоблока фактичного блоку виконується за наступним алгоритмом (алгоритм розглядається для операторів, зрушених тому на вхідні шляху, для операторів, зрушених вперед, алгоритм аналогічний):
1) оператори вставляються в усі блоки, що безпосередньо передують області, які мають тільки один безпосередньо наступний блок. Вставляються оператори записуються перед оператором переходу.
2) з псевдоблока створюється формальний блок, який вставляється на всіх вхідних шляхи, що йдуть від безпосередньо попередніх блоків, що мають кілька наступників.
3) якщо вхідний блок програми належить області Rk, то псевдоблок формується в формальний блок і ставиться на неявному шляху між зовнішнім і викликає оператором і початковим блоком.
Це відповідає створення нового блоку.
5.Набор і послідовність оптимізують перетворень
Кожен із способів оптимізації може бути реалізований у вигляді окремого перетворення. У той же час практика оптимізуючий трансляції показала, що всі ці способи оптіміваціі, не співпадає один з одним, реалізують багато в чому збігаються процеси обробки програми, в основі яких лежить невелике число більш елементарних і фундаментальних перетворень програм.
Тому в реальних оптимізують трансляторах різноманітні набори способів оптимізації програм зводяться до застосування більш простих перетворень в їх поєднанні один з одним і з урахуванням їх сукупного впливу на транслюються програму.
Реально використовуються набори оптимізують перетворень не мають властивість, що дозволяє не стежити за порядком застосування перетворень. Зазвичай існують ситуації, коли застосування одного перетворення закриває возможяості застосування іншого (у цьому випадку говорять, що перші преобравованіе володіє тупиковість по отношонію до другого) або, навпаки, приводить до нових можливостей іншого перетворення (т. о. Володіє повторністю по відношенню до нього) .
Тому важливим для наявного набору оптимізують перетворень (з точки зору якості одержуваної програми) видається вибір порядку застосування перетворень з набору. Треба прагнути до того, щоб в послідовності застосування будь-яке перетворення не передувало перетворення, стосовно якого воно тупиковою, але передувало преобравованію, стосовно якого воно повторно.
Можна дати деякі приватні ре