Ви є тут

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

Автор: 
Куйвашев Дмитро Васильович
Тип роботи: 
Дис. канд. наук
Рік: 
2002
Артикул:
3402U003378
129 грн
Додати в кошик

Вміст

РОЗДІЛ 2.
ІЄРАРХІЧНА ГРАФОВА МОДЕЛЬ ПРОГРАМИ
Для проведення оптимізуючих перетворень програми та генерації оптимізованого коду необхідно формалізувати внутрішнє подання програми у компіляторі. На етапі оптимізації програми використовується три види оптимізуючих перетворень: 1) локальні - на ділянках економії "базовий блок"; 2) глобальні - на ділянках економії "процедура"; 3) міжпроцедурна, де ділянкою економії є програма в цілому. Останній вид перетворень використовується в основному у компіляторах для багатопроцесорних машин і дозволяє відшуковувати паралелізм незалежних гілок між процедурами, що звертаються одного масиву або складної структури даних.
Як форма подання для базового блока в абсолютній більшості компіляторів використовується ациклічний орієнтований граф [49] - графічною формою подання будь-якого виразу є дерево. Для подання структури всієї програми використовуються графи залежностей по керуванню та даним між базовими блоками [53]. Графова форма подання є природною для програми, практично всі алгоритми синтаксичних аналізаторів мають за мету побудову графової структури [34]. Практично графова структура, хоча граф прямо не обробляється ЕОМ, є більш ефективною, ніж подання у вигляді строк символів або послідовності перетворень, тому що дозволяє у достатньо простій та компактній "графічній" формі подавати складну внутрішню структуру програми.
У випадку перенацілюваної компіляції інформація про оптимізуючи перетворення може подаватися на рівні опису цільової процесорної платформи. Тому для внутрішнього подання програми необхідно використовувати формалізми, які дозволяють чітко і однозначно описувати структуру програми за допомогою певної системи понять [86].
Природно представляти математичну модель програми у вигляді суперпозиції операторів присвоєння [12] або в термінах алгебри алгоритмів Глушкова. Математична модель програми необхідна для подання оптимізуючих перетворень та процедур генерації коду в уніфікованій формі [71]. Графічною інтерпретацією суперпозиції операторів присвоєння є граф з ієрархічною структурою, базовими елементами якого є послідовність простих присвоєнь, або в інтерпретації теорії компіляції - базові блоки (ББ). Тому і математичною моделлю програми, і уніфікованою формою подання програми у компіляторі повинна бути ієрархічна графова структура.
Введемо основні поняття ієрархічного графа та ієрархічної графової моделі, запропонованої Євстигнєєвим та Касяновим [21,85] як базові для подання структури програми при її обробці компілятором.
2.1 Ієрархічні графи
Нехай G - граф довільного вигляду. Граф C називається фрагментом графу G, що позначається C?G, якщо C утворений підмножиною G. F є ієрархія фрагментів G, якщо F є множина фрагментів G, G?F, і для будь-яких C1,C2?F або C1?C2=? або С1?С2 або C2?C1. G є головний фрагмент ієрархії F, якщо в F немає фрагментів G, які є підфрагментами C.
Ієрархічним графом (ІГ) [21] називається двійка H=(G,T), де G є граф, T - кореневе дерево, вершини якого відповідають елементам деякої ієрархії в G. T називається деревом вкладеності H, G - основним графом H. Для будь-якої вершини p?T максимальне піддерево T з коренем p позначається T(p), а G(p) - фрагмент основного графа G, відповідний до p. H(p)=(G(p),T(p)) є ієрархічний підграф H, асоційований з вершиною p.
Найліпшим поданням графової моделі програми є простий ІГ H=(G,T), де кожна вершина p?T відповідає деякому підграфу основного графа G. Тоді T називається вершинним деревом вкладеності, вершини T відповідають певним підмножинам G.
Графова модель являє собою клас графових об'єктів, які мають вигляд позначених графів з заданим на них відношенням еквівалентності. При заданні графової моделі розрізнюємо статичну (або синтаксичну) частину опису, яка визначає клас позначених графів, утворюючих вказану модель, та динамічну (або семантичну) частину, яка задає розбиття даного класу графів на класи попарно еквівалентних.
Мітки є множина об'єктів V, яка розпадається на попарно непересічні підмножини класів міток. Визначається множина об'єктів-"типів" міток W, для ?w?W поставлена у відповідність множина міток V(w)=Vi1?Vi2?...?Vis, де Vij?V - деякий клас міток для любого j.
З статичної точки зору ієрархічна графова модель є трійка (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.
Для продукції p використовується позначення G==>pH: є безпосереднє виведення H з G