Register Allocation (RAL)

Register Allocation (RAL) - распределение регистров. Один из наиболее мощных оптимизационных алгоритмов.

Spill – процедура освобождения регистра в память
Fill – заполнение регистра из памяти

Есть два основных алгоритма распределения регистров:
• Global Register Allocation (GRAL) – рассматривает всю процедуру
• Local Register Allocation (LRAL) – работает с отдельными basic-блоками
вначале процедуру оптимизирует GRAL, а уже потом, то что он не смог сделать, дорабатывает LRAL. Но мы более подробно остановимся на Global Register Allocation и рассматривать локальный алгоритм не будем.

Алгоритм раскраски графа:
1. Присвоение всем переменным виртуальных регистров
2. Нахождение всех WEB (сильно связанных компонентов )
3. Построение графа зависимостей
4. Раскраска графа (кол-во цветов соответствует имеющемуся числу реальных регистров)
5. Назначение реальных регистров в соответствие одинаковым цветам

Пример:
Пусть имеется следующий кусок кода (процедура)

x = 2;
y = 4;
w = x + y;
z = x + 1;
u = x*y;
x = z*2;
use x, z, u;  <---  (т.е. по окончании нам будут нужны только x, z и u).

Действуем в соответствии с описанным выше алгоритмом.

1). Присвоение всем переменным виртуальных регистров

S1 = 2;
S2 = 4;
S3 = S1 + S2;
S4 = S1 + 1;
S5 = S1*S2;
S6 = S4*2;
use  S6, S4, S5

А так же пусть у нас есть три реальных регистра r1, r2, r3.

2). WEBы пока не ищем … о них будет рассказано позже.

3). Построение Interference Graph
Узлами графа зависимостей являются виртуальные регистры, а дуги соединяют те узлы, которые не могут быть в одной физической ячейке.

Дополняем графом реальных регистров, получим

Intgraph.gif

4). Раскрашиваем граф так, что каждый узел одного цвета не может быть соединен с узлами такого же цвета!

coloredIntgraph.gif

Если раскрасить в три цвета нельзя, то применяя spill, получим новый граф, который можно будет раскрасить в три цвета.

5).

r1 = 2;
r2 = 4;
r3 = r1 + r2;
r3 = r1 + 1;
r1 = r1*r2;
r3 = r3*2;
use r1, r2, r3.

Напишем приблизительный код такой процедуры AllocationReg( … ).

in:     (параметры передаваемые на вход)
    DUchains;     (set DUchain) 
    nblock: int;
    ninst: int array[1..nblock];
    block;
    succ;
    pred;
out:  (то что получим на выходе)
    ninst: int;
    Lblock;
    succ;
    pred;

Итак,

AllocateReg(…)
{
    repeat
        repeat
            Make_Webs(…);
            Build_AdjMtx(…);
            coalesce := coalesceReg(…);
        until !coalesce;
        Build_AdjLsts(…);
        Compute_spill_costs(…);
        PruneGraph(…);
        success := AssignReg;
        if success 
        {
            ModifyCode(…);
        }
        else
        {
            GenSpillCode(…);
        }
    until success;

}

Теперь подробнее о WEBах… Рассмотрим следующий пример:

WEBi.gif

WEB1 : y def B1; use B3;
WEB2 : x def B2,B3; use B4,B5;
WEB3 : y def B2; use B4;
WEB4 : x def B5; use B6;

На каждую сеть ложится один виртуальный регистр!

//by wonder: если есть ляпы - поправте! =)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.