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

У процесі генерації коду для кожного ББ запроваджено час t, який при генерації коду для початкової вершини ББ дорівнює 0 та зростає на 1 з кожною згенерованою ДК. У циклі генерації довгої команди для Kb проглядаються готові до виконання команди (з доступними у регістрах операндами) viV. Із зіставлених операціям ББ інструкцій МП визначається множина LA'={ LAm }, виходячи з якої довга команда Ki має максимальну функцію оцінки як суму шляхів атомарних команд cbest (LA') =I, де i – шлях до кінцевої вершини цієї команди. Для МП з ДКС на формування множини LA' впливає інформація про наявність вільних функціональних пристроїв FU*.

Розподіл регістрів. Метод розподілу регістрів впливає як на час виконання скомпільованої програми, так і на час компіляції програми. На сьогодні відомо декілька методів розподілу регістрів: розфарбування графа, аналіз графу потоку даних або вирішення задачі методами цілочисельного програмування. Традиційним методом є розфарбовування вершин-ресурсів vi графа ББ KB (VB, EB) у мінімальну кількість кольорів, кожний колір зіставляється з певним регістром регістрового файла (РФ). Метод має експоненціальну складність від кількості змінних у ББ, та тільки мінімізує потребу в апаратних регістрах, але не вирішує проблему ефективного використання великого регістрового файла сучасних МП.

Альтернативним до розфарбовування графів є використання евристичних алгоритмів, наприклад сканування орграфа ББ вперед при складанні спискового розкладу. Такий метод є реалізацією методу перетину графа потоку даних, запропонованого А. П. Єршовим, який мінімізує потребу в комірках пам’яті для зберігання значень. Метод не використовує алгоритми експоненційної складності, які значно погіршують часові характеристики за мінімального збільшення ефективності алгоритму. Основною рисою алгоритму є ефективність як для простих RISC-МП, так і для ПЦОС та МП з ДКС і суперскалярних процесорів.

Для використання у МП з простими та кластеризованими регістровими файлами запропоновано метод, заснований на евристиці пошуку на графі потоку даних. Для деякого моменту часу t при обробці орграфа ББ KB= (VB, EB) генерується ДК на базі визначеної множини LA'. Визначається поточний стан регістрової пам’яті як RGB={rgi}. Вибирається max – максимальне i для LAiLA', та min – мінімальне i для LAiLA'. Позначається  максимальний час виконання команди, вводяться кількість регістрів NB=||RGB||, кількість вільних регістрів (вводиться атрибут для rgi: empI=«вільний», якщо регістр не зайнятий значенням) NBE=||ERGB={rgi | empi=«вільний» }||. Вводиться атрибут inmemi={«так», «ні»} для кожного rgi, який позначає, чи збігається значення змінної в регістрі й в відповідній комірці пам’яті (тобто чи потрібно зберегти значення у пам'яті), кількість таких регістрів є NBM=||MRGB={rgi | inmemi=«ні»}||. Розглядаються всі змінні viV, такі що minimax+C*, де 1C2 – змінні, задіяні при генерації ДК, які будуть формуватися в найближчий час (до С). Множина таких змінних позначається через VC, а реальний регістр, який відповідатиме vi – rgi. Для viVC та відповідним їм rg'iRGB послідовно під час генерації наступних ДК вивільнюються регістри, які містять змінні, що в найближчий час не знадобляться для здійснення операцій -»найбільш непотрібні значення».

Визначається множина CRGB=RGB- (SRGBMRGB) як множина змінних, продубльованих в регістрах. Знаходиться мінімальне I – час до найближчого звернення до значення, для всіх rg'iCRGB за допомогою простого перегляду вершин KB. Якщо деякі rg'i не зустрічаються в KB, то розглядаються всі наступники KB за керуванням. Якщо даний rg'i зустрічається в декількох наступниках, його i визначається так: B+min (i1, i2, …, in), де ij – знайдене i в j-му наступнику. В разі незнаходження rg'i в одному з наступників ББ B, процедура рекурсивно повторюється для цього наступника B, але якщо шлях від B до поточного ББ не перевищує мінімуму з вже обчислених значень i в інших базових блоках. Кожному rg'i зіставляється i – мінімальна відстань до наступного застосування змінної в rg'i. Після визначення i для всіх регістрів за необхідності вивільнення регістра визначається max=max (i) і для rg'i з i =max змінюється empi на значення «вільний». Метод розподілу регістрів у загальному випадку складається з таких правил:

1) якщо ||VC||>NBE та ||CRGB||<||VC||-NBE (нестача регістрів та більшість регістрів треба вивантажити у пам’ять) і в формованій ДК немає команди завантаження значення у регістр, в цю ДК необхідно вставити вивантаження rgiMRGB з максимальним часом i та вивільнити для нових змінних регістри, які зберігають найбільш непотрібні значення;

2) якщо ||VC||>NBE та ||CRGB||>||VC||-NBE (нестача