Page 58 - 4761

І-та операція вважається зайвою, якщо існує більш рання ідентична їй j-та операція
і ніяка змінна, від якої залежить ця операція, не змінюється третьої операцією, що лежить
між i-тою та j-тою операціями.
Наприклад, для лінійної ділянки:
Е: = Е + С * В
А: = Е + С * В
С: = Е + С * В, яку представимо у вигляді тріад наступним чином:
1) * (С, В) 4) * (С, В) 7) * (С, В)
2) + (Е, ^1) 5) + (Е, ^4) 8) + (Е, ^7)
3) : = (^2,Е) 6) : = (^5, А) 9): = (^8, С),

поява операції С * В вдруге і втретє зайва, тому що ні С, ні В не змінюються після 1-ої
тріади. Але повторне додавання Е з С * В (5-а тріада) не є зайвим, тому що після першого
додавання Е з С * В, третя тріада змінює значення Е. А третє додавання Е з С * В є зайвим
і може бути замінено посиланням на 5-у тріаду.
Алгоритм виключення зайвих операцій переглядає операціі в порядку їх появи.
Якщо i-я тріада зайва, то вона замінюється тріадою (SAME, j, 0), де операція SAME нічого
не робить і не породжує ніяких команд при генерації. Щоб стежити за внутрішньою
залежністю змінних і тріад, їм у відповідність ставляться числа незалежності за такими
правилами:
1) Спочатку для змінної А число незалежності dep (А) дорівнює нулю, так як її
початкове значення не залежить ні від однієї тріади.
2) Після обробки i-ї тріади, в якій змінній А присвоюється деяке значення, dep (А)
замінюється на i, так як її нове значення залежить від i-ї тріади.
3) При обробці i-ї тріади її число незалежності dep (i) дорівнює 1 + (максимальне з
чисел залежності її операндів).
Алгоритм виключення операцій.
Тріада SAME(j,0) означає, що деяка тріада i  тріаді j.
1. Якщо операнд посилається на тріаду SAME(j,0), то він заміняється на посилання на
тріаду з N j (^j).
2. Виконується число залежності поточної тріади з N i, виходячи з чисел залежності її
операндів.
3. Якщо існує  j-та тріада, j<i idep(I)=dep(j), то поточне тріада і заміняється на
тріаду SAME(j,0)
4. якщо поточна тріада :=, то обчислюється число залежності відповідної змінної.
Підстановка (згортка).
Операції, операнди яких відомі під час компіляції, немає необхідності виконувати
під час обчислень.
Підстановка (згортка) - це заміна змінної або ідентифікатора результату заданої або
обчисленої константи, причому ця заміна проводиться під час трансляції, а не в процесі
вирішення. Згортка головним чином застосовується до арифметичним операторім +, -, *, /.
Підстановка є повністю внутрішньоблоковою процедурою і виконується перед усуненням
зайвих команд.
При виконанні операції підстановки для кожного блоку створюється спеціальна
таблиця поточних значень змінних, яким проводиться присвоєння.
Зазвичай згортка здійснюється тільки в межах лінійної ділянки за допомогою
спеціальної таблиці Т, спочатку порожній. У процесі згортки Т містить пари (А, К) для
всіх простих змінних А, для яких відомо поточне значення К. Крім того, якщо програма у
внутрішньому поданні представлена, наприклад, у вигляді тріад, то кожна тріада, яку
можна згорнути замінюється нової тріадою (С, К, 0), де С (константа) - новий оператор,
для якого не потрібно генерувати команди, а К – результуюче значення згорнутої тріади.

56