Методики перенацілюваної генерації коду для мікропроцесорних архітектур з нерегулярним довгим командним словом

Ієрархічна графова модель (ІГМ) є трійка (H, M, L), де H – ієрархічний граф, M – функція типу, яка приписує кожному елементу (вершині, ребру і фрагменту) h ієрархічного графа H його тип M (h) W, а L – функція міток, яка приписує кожному елементу h графа H його мітку – деякий елемент L (h) V (M (h)). Семантична частина графової моделі задається за допомогою системи перетворень графових моделей, що зберігають їх еквівалентність (еквівалентних перетворень).

Графова граматика складається з множини правил (графових продукцій), які можуть ітеративно застосовуватися до графа, роблячи звичайно його локальні перетворення. Графова продукція є четвіркою (L, R, E, C), де L і R – два графи, які називаються лівою та правою частинами продукції, E – деякий механізм вбудовування, C – умови застосування продукції. Продукція p застосовується до оброблюваного графа G наступним чином:

1) знаходимо входження лівої частини L в G (за виконання умови застосування C) ;

2) видаляємо частину графа G, визначену вказаним входженням L, для одержання контекстного (або залишкового) графа D;

3) вбудовуємо в D праву частину (копію) R за допомогою механізму вбудовування E і отримуємо виведений граф H.

Вершини ІГ функцією типу M (h) поділяються на два основних класи: 1) перетворювачі, які мають не більш однієї вихідної дуги та являють собою одну або декілька інструкцій присвоєння значення змінній або виклику підпрограми; 2) розрізнювачі, що мають більш одного можливого наступника по керуванню, але не змінюють стан пам’яті (окрім змінних-лічильників), являють собою умовний оператор, оператор вибору, циклічні конструкції. На рис. 1 показано приклад структури гіпотетичної підпрограми x1 та її ІГМ (білим кольором показано перетворювачі, чорним – розрізнювачі).

Рис. 1. Приклад ієрархічної графової моделі.

Кожний перетворювач являє собою ІГ Hb (Tb, Gb), де дерево вкладеності Tb є променем; граф Gb є незв’язаним та складається з множини ациклічних орграфів Defi, (дерев), які визначають присвоєння. Кожен орграф Defi зіставлений деякій вершині Tb. Граф Hb – відображення лінійної ділянки програми, до якої не входять умовні або безумовні переходи, – базового блоку (ББ).

Орграфи, які визначають присвоєння, позначаються за допомогою дужкового запису Def (Var, Exp), де Var – змінна, яка присвоюється, Exp – значення виразу, яке присвоюється, Exp=Opn (Exp1, …, Expn) |Vari|Consti, де Opn – n-арна операція, Vari – змінна, Consti – константа. Вводиться множина змінних програми VAR={vari} та множина констант CONST={consti}. Вводяться множина типів (як базових, так і композитних) TYPES={typei}. Для множин VAR та CONST вводиться функція t=Type (vari|consti), tTYPES, яка повертає тип змінної або константи.

Дерево вкладеності ІГ програми визначає зв’язки по керуванню.

За допомогою перетворювачів відображаються зв’язки за даними в базових блоках. Скалярний оператор Si виконується раніше скалярного Sj (позначається Si Sj), якщо оператор Si лексично передує Sj (i<j). Через OUT (Si) позначається множина екземплярів змінних, які модифікуються оператором Si, через IN (Si) – множина екземплярів змінних, які використовуються тим же оператором. Оператори Si та Sj знаходяться у потоковій залежності SiSj, якщо справедливі дві умови:

1) Si Sj;

2) OUT (Si) IN (Sj) .

Антизалежність між Si та Sj (позначається Si Sj) визначається аналогічно потоковій, але умова (2) має вигляд IN (Si) OUT (Sj) . Залежність за виходом між Si та Sj (позначається SiSj) визначається аналогічно потоковій, але з умовою (2) : OUT (Si) OUT (Sj) . На базі введених формалізмів розглядаються оптимізуючі продукції (оптимізації) для ББ і для глобальної оптимізації. При створенні ІГМ після локальних оптимізацій в графах ББ залишаються лише потокові залежності.

Розглядаються деякі описи оптимізуючих графових продукцій.

1. Поширення констант – посилання на змінну, яка дорівнює константі, замінюється на константу

L = di  diSi  SjDef (di, ConstK)  Sj Si, R = (ConstK).

2. Алгебраїчні спрощення, являють собою велику кількість продукцій типу

L = {'+', '-'} (vari, 0) ; R = (vari) ; для перетворення x+0x, x-0x.

3. Для видалення повторюваних виразів використовується наступний метод. Нехай існує L = Op (…, …), та Si, Sj, такі, що Si Si, LSi, LSj. Продукція вставляє новий оператор R=SR=Def (varTEMP, L), так що для будь-якого Sk Si виконується Sk SR і SR Si. Входження L в операторах Si і Sj заміняється на змінну varTEMP.

Усі розглянуті в роботі продукції для оптимізації ББ є машиннонезалежними.

Для застосування оптимізуючих продукцій у процесі глобальної оптимізації використовується аналіз потоку даних. Для ББ B вводиться функція передачі (ФП) FB (vari), де vari – будь-яка змінна, яка відображує значення змінної vari після виконання ББ. Результатом відображення є вираз у символьному вигляді – значення vari як функція від значень певних змінних перед початком виконання ББ.

Вводиться оператор композиції  над двома ФП FB1 (vari) та FB2 (vari), нова ФП FB1B2 (vari) =FB1 (vari) FB2 (vari) являє собою ФП – результат послідовного виконання базових блоків B1