Registry Allocation(часть 2)

Теперь более детально рассмотрим отдельные подзадачи.

Построение сетей

Нам потребуются следующие структуры данных:

  • DU_Chain - def-use цепочка
DU_Chain{
    Symbol,
    DU
};

Где Symbol - символ, используемый для представления переменной/виртуального регистра
DU - набор элементов вида <def/use, номер_блока, номер_инструкции_в_блоке>. При этом имеется один def и несколько use'ов
  • Webrecord - структура для сети
WebRecord{
    Symbol sym,
    Set def,
    Set use,
    bool spill,
    SReg sreg,
    displacement
};

Рассмотрим алгоритм создания сетей:

MakeWeb(...){
    int nWeb = 0;//счётчик для количества построенных сетей
    Set<WebRecord> Web; //набор построенных сетей

    for each du from DUChain{
        nWeb++;
        Web.push({sym = du[0], def = du[1], use = du[2], spill = false, SReg = NULL, displacement = NULL})

        do{
            old = nWeb;
            Tmp1 = Web;
            while (Tmp1 != 0){
                Web1 = TMP1.pop();
                Tmp2 = Tmp1;
                while (Tmp2 !=0    ){
                    web2 = Tmp2.pop();
                    if (web1.symb = web2.symb) && (intersection(web1.use, web2.use)){
                        web1.use = web1.use + web2.use;
                        Web = Web - {web2} ;
                        nWeb--;

                    }        

                }

            }

        }  until (old==nWebs);

    }

};

Далее, нужно завести массив Symreg[] для всех реальных и виртуальных регистров. Если nRegs - число реальных ренистров, то первые nRegs элементов заполняем реальными регистрами следующим образом

symbol = <символ реального регистра>
def = NULL
use = NULL
spill = false
sReg = NULL
displacement = NULL

Оставшиеся элементы Symreg[i] заполняем сетями:

symbol, def и use,spill - описаны в выше
sReg = i;

Конвертация промежуточного представления.

Здесь мы заменяем все переменные на соответствующие виртуальные регистры, если это не было сделано ранее.

Построение Adj_Matrix представления для Interference Graph

Adj_Matrix[i][j] = true, если между i и j есть связь b false в противном случае.
Понятно, что матрица содержит избыточную информацию, поэтому можно рассматривать нижнюю треугольную матрицу, сдвинутую на 1, поскольку диагональные элементы тоже неинтересны.

  • Все реальные регистры интерферируют между собой.

Поэтому проходим соответствующие элементы в Adj_Matrix и делаем их true.
for (i = 2; i<= nReg; i++){
for (j = 1; j <= i-1; j++) {
Adj_matrix[i][j] = true;

}
}

  • Взаимодействие между реальными и виртуальными регистрами определяется только машинной моделью.
for (i = nregs + 1; i<= nWebs; i++){
    for (j = 1; j <= nReg; j++)  {
    if (interfere(Symreg[i], Symreg[j]))
        Adj_matrix[i][j] = true;
    }
}
  • Наиболее интересна интерференция символьных регистров
for (i = nregs + 1; i<= nWebs; i++){
    for (j = 1; j <= i-1; j++)  {
    foreach symreg[i].def
        if (LiveAt(Symreg[i].def, Symreg[j]))
            Adj_matrix[i][j] = true;
    }
}

Как реализовать LiveAt (проверка вторгается ли один виртуальный регистр во время жизни другого) предлагается продумать самим.

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