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

Множина продукцій розширювана, але як мінімум, до неї належать такі типи:

1. Множина експертних змінних, кожна з яких має вигляд (Name, Value, , ), де Name – ім’я змінної, за яким відбувається доступ, Value – значення змінної; наприклад («є предикатно виконувані команди», «так», , ).

2. Графові трансформації – оптимізуючі машинно-залежні перетворення, часто перетворення виразів на одну операцію МП – (Name, , , G), де Name – ім’я продукції, G – графова продукція. Наприклад, обчислення абсолютного значення суми: L=call (ABS (int, int)  ({'+'} (vari, varj)) ; R= { 'ABS' (vari, varj).

3. Шаблони й макроси – перетворюють певні складні операції (отримання квадратного кореня, тригонометричні функції) у серію простіших операцій. Макрос визначається як (Name, , , G), де G – графова продукція з лівою частиною L=Op (x1, …, xn), де Op – замінювана операція, xj – операнди, та правою частиною R=fOp (x1, …, xn), де fOp – вираз, яким замінена операція Op, xj – ті ж самі операнди. Для більшості МП Op={ '/', ' ', '1/x', '1/ ' }.

4. Таблиці порад. Для генерації коду часто необхідно формувати таблиці, в яких перелічені процедури генерації коду, наприклад при звертаннях до складних структур даних або генерації кадру стеку. Таблиця порад визначається як (Name, , Cond, Table), де Name – ім’я продукції, Cond – вираз, який визначає номер поради у таблиці, Table – таблиця порад (G1, G2, …, Gn), кожна з яких є графовою продукцією, або оптимізуючою машиннозалежною продукцією, або макросом.

5. Множина прагм – вказівок програміста компілятору. Аналогічні експертним змінним, але їх значення може змінюватися під час компіляції програми за бажанням програміста.

Архітектура цільового МП повністю визначається як P={ M*, R*, TR*, RTYPES, AA*, LA*, K*, FU*). Знання про оптимізацію програми та генерацію коду уніфіковано описані множиною NPr*. Під формальним описом архітектури цільового процесора визначимо двійку D= (P, NPr*), яка повністю визначає поведінку ПК при генерації коду та архітектуру цільового МП.

Основні етапи генерації коду. Процес генерації коду для базового блоку складається з трьох етапів: 1) вибір інструкцій цільового МП – зіставлення певної інструкції операції з певного виразу; 2) розподіл регістрів – розміщення змінних у регістрах найефективнішим способом; 3) складання розкладу інструкцій – формування коду ББ з вибраних інструкцій з найменшим часом виконання.

Вибір інструкцій для зіставлення з ІГМ програми відбувається за допомогою повного покриття орграфа ББ графами команд одночасно з розподілом регістрів та складанням розкладу інструкцій. У процесі зіставлення для кожної змінної variVAR визначається її розміщення в пам’яті та множина регістрів для зберігання, виконуються оптимізації для зіставлення комбінованих та суміщених команд. Вводиться функція RT (t), де tRTYPES, RT (t) ={ TRi }, ||{ TRi}||1, яка зіставляє апаратному типу МП множину регістрів МП, до яких його може бути завантажено (змінні можуть бути завантажені у декілька регіонів регістрів). Коли змінна є редукцією, їй зіставляються акумуляторні регістри, які оперують з подвійною точністю. Далі кожній команді ББ зіставляються всі можливі інструкції МП. Якщо існують різні інструкції, які виконують одну операцію, але над різними типами регістрів, то команді зіставляються всі можливі інструкції. Із зіставлених інструкцій при складанні розкладу команд вибирається лише одна оптимальна.

Більшість арифметико-логічних інструкцій МП не можуть оперувати безпосередньо із значеннями у пам’яті, тому компілятор генерує послідовність команд для завантаження значень змінних у регістри. Визначається час життя копій змінних пам’яті, розташованих у регістровому файлі в певний час – регістрових змінних (РЗ). У сучасних моделях МП з ДКС та ПЦОС ємність регістрового файла сягає 64 – 256 регістрів. При кількості одночасно виконуваних операцій у ДК від 4 до 8 (або більше) можливість подачі даних з пам’яті до регістрів обмежена. За такт може оновитися лише від 1/16 до 1/32 регістрового файла. Для сучасних МП проблема подачі даних до регістрів є критичною і необхідна розробка поліпшених методів розподілу регістрів, які дозволяють ефективно використовувати великі регістрові файли сучасних МП.

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

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

Орграф ББ визначається двійкою Kb= (Vb, Eb), де V={ vi} – множина вершин двох типів, які являють собою віртуальні регістри та команди, E – множина орієнтованих ребер, які є зв’язками за даними, E= { ek }, ek= (vi, vj). На орграфі вводиться функція зв’язності fc=VV {