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

Предмет:

Тип роботи:

Автореферат

К-сть сторінок:

Мова:

Українська

Оцінка:

та B2. Вводиться оператор перетину  над двома ФП FB1 (vari) та FB2 (vari), нова ФП FB1B2 (vari) =FB1 (vari) FB2 (vari) робить відображення тільки для тих змінних, які будуть змінені незалежно від того, який ББ – B1 або B2 буде виконаний. Для позначення виклику підпрограми використовується функція відображення FCALL (var1, …, varn, var), де vari – фактичні параметри процедури, n – їх кількість, var – змінна, для якої будується ФП. Для циклічної конструкції C вводяться дві ФП: ітерація FCI (vari) та замикання FC* (vari), де vari – скалярна змінна. Функція FCI (vari) вертає значення vari після виконання i ітерацій циклу, функція FC* (vari) – після виконання усіх ітерацій циклу (лише якщо відома кількість операцій або змінна не змінюється в тілі циклу), функції застосовуються до циклів, в яких розпізнана індексна змінна (змінна, яка лінійно залежить від номера ітерації циклу). Для оптимізації циклу використовуються визначення та видалення індексних змінних, пошук агрегативних змінних, які створюють міжітераційні залежності, чистка циклу від зайвих обчислень, пошук та видалення циркулярних змінних (що практично не реалізовано в штатних компіляторах для ПЦОС), перетворення виразів доступу до елементів масиву.

При аналізі виразів доступу до масивів використовуються продукції (L, R, E, C) вищезазначеним способом. Для кожної вершини p дерева T графа процедури H, якщо її тип M (p) є «цикл», проводиться аналіз підпорядкованого ІГ. Застосовуються декілька типів продукцій: 1) ті, які виділяють індексні та охоплюючі змінні (лінійно залежні від індексу циклу) ; 2) ті, які виділяють редукції; 3) ті, які перетворюють вирази доступу (індексні вирази) до елементів масивів.

Зокрема, індексні змінні з довільним кроком виділяються за допомогою продукції:

L = Def (varIDX, Op1 (varIDX, ConstExp))  Type (varIDX) =«ціле» 

FCC (ConstExp) =«так», де varIDX – необхідна індексна змінна, Op1={'+', '-'}.

ФП «ітерація» для індексної змінної з довільним кроком має вигляд FCI (varIDX) =Ai+B, де A та В – константи, i – номер ітерації циклу.

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

У висновках до розділу зазначено, що ІГМ програми задовольняє вимогам, які виставляються до проміжних подань програм в оптимізуючих компіляторах: можливість формального виразу оптимізацій, збереження якості подання вхідного тексту, уніфіковане подання конструкцій програми у явному вигляді, можливість аналізу потоку даних.

У третьому розділі дисертації формалізовано опис цільової архітектури МП, опис знань про оптимізацію коду для цільової архітектури та запропоновано поліпшені методи, методики й алгоритми генерації коду для ПЦОС та мікропроцесорів з довгим командним словом (МП з ДКС).

Опис мікропроцесора складається з опису ресурсів та системи команд.

Базовими для опису ресурсів є регістри rgi та простори пам’яті MI. Регістри об’єднуються у регістрові регіони TRI={rgi}, банк регістрів є множиною регістрових регіонів RI={TRI}. Всі регістрові банки об’єднуються у множину R*={RI} регістрових банків. Визначається множина всіх просторів пам’яті M*={MI}. Вводиться множина типів даних, операції над якими апаратно реалізовані у МП: RTYPES, та функція перетворення TRT: TYPES  RTYPES, що відображає тип даних мови високого рівня у внутрішній апаратно підтриманий тип.

Для інструкцій МП вводиться множина атомарних команд AA*={ LAI }. Атомарна команда визначена двійкою LAI = (AK, KG), де AK – множина локальних атрибутів команди (ідентифікатор, час та вартість виконання, змінювані прапорці, зв’язувані функціональні пристрої), KG – орграф команди, що подає функцію передачі команди. Для визначення функціональних пристроїв вводиться множина FU*={ FUI }, кожний FUI має атрибути, які описують його апаратні характеристики. Атомарні команди об’єднуються в списки атомів (аналог вертикального кодування мікрокоманд в МП). Множина списків атомів визначається як LA* = { LAI }, за один раз може бути виконаний лише один елемент LAI, LAI = { AJ }, LAIA*, ║LAI║1. Всі атомарні команди AJLAI виконуються одночасно (аналог мікрогоризонтального кодування в МП).

Довгі команди (ДК) формуються з списків атомів. Множина ДК K*={ KI }, KI = (KGI, { (KAI, LAJ) }), де KGI – спільний атрибут команди (наприклад, предикатне виконання ДК) ; { (КАI, LAI) } – множина можливих секцій ДК, де KAI – атрибут секції ДК (окремий предикат, опціональність команди та інше), LAI -виконуваний список атомів (секція ДК), ║{ (КАI, LAI) }║1. Якщо цільовий МП має інструкції класу «ОКМД в регістрі», коли довгий регістр (64-128-256 біт) поділяється на поля однакової ширини, над якими протягом одного такту виконується одна й та ж операція як над незалежними регістрами (як Intel MMX або SSE), такі інструкції природно описуються запропонованим формалізмом.

Інтелектуалізація генерації коду. Для ефективної роботи генератора коду компілятора необхідна інформація про загальні принципи генерації коду для цільового МП. Жодна обчислювальна система не може бути використана без наявності розроблених методів (знань) про її застосування у конкретному випадку. Термін «знання» використовується для позначення евристик, якими керується програміст-експерт при розробці програми мовою низького рівня. Експертні знання не є певною системою – кожне з правил (подане у формі «якщо-то») виконується за певних умов, часто окремо від інших правил.

Назвемо сукупність експертних знань експертними продукціями,