Meeting minutes (14.10.2005)

На нашей встрече в прошедшую субботу обсуждались общие и ближайшие задачи
нашей группы а также более подробный их разбор.

Итак, изначально мы делаем средства разработки, необходимые для
написания отдельных состовляющих кодогенератора, а именно: Control
Flow Framework и Data Flow Framework. После того, как эти инструменты
будут сделаны, можно будет переходить уже конкретно к трансляции кода
в ассемлерные инструкции. После выполнения этого инструментария группа
разобьется на 3 части, каждая из которых будет выполнять свой
подпроект, с своим ментором.

AR(Action Required):

  • Control Flow Translation - группа Анохина stuff
  • Data Flow Translation - группы Речистова и Костюченко

Коротко о каждом из AR:

CFTranslation

- Tрансляция CFG Феникса в CFG, который более удобен для нас.
Новый CFG наследуется от класса Graph.
В объекте CFG должны присутствовать ссылки на процедуру(Proc) и на
дерево циклов (LoopTree).
Линейный участок Cfg_Node наследуется от класса Node.
Свойства линейных участков (Cfg_Node) нового CFG:

Single Block (ex: call function)

single.gif

IF Block (ex: simple branch)

if.gif

Switch block (ex: indirect branch)

switch.gif

Temp block (ex: независимый от структуры блок с инструкциями,
который связан с стартовым и конечным блоком)

temp.gif

Дуга Cfg_Edge имеет ссылку на операцию передачи управления на эту дугу
(Null в случае отсутствия таковой).

Была предложена упрощенная версия алгоритма этой задачи:

Входные данные:
        old_cfg -  Сontrol Flow Graph который представлен в Фениксе
        old_bb - Basic Blocks - которые представлены в Фениксе 
        old_edge - дуги в CFG представленные в Фениксе

1) Создаем:
   create   new_cfg - наш новый CFG
   create   node_tb - таблица наших узлов

2) Сканируем старый CFG
   foreach old_bb in old_cfg 
           create new_bb
           create hash_entry(node_tb,new_bb,old_bb)3) Транслируем дуги:
   foreach old_bb in old_cfg
           new_bb = hash_get(node_tb,old_bb)
           foreach succ_edge in old_bb 
                   create new_edge
                   old_succ_bb = ...(succ_edge)
                   new_succ_bb = ...(old_succ_bb)
                   link (new_edge,new_bb,new_succ_bb)

Решили реализовать также DU(Def-Use Graph, Definition-Usage Graph - Граф определение-использование).
Узлом DU графа нужно сделать абстрактный узел DU_Node (наследуется от Node).
Преемниками этого абстрактного класса будут являться классы Oper_node(операция, инструкция)
и Phi_node(фи-функция). Все Oper_node линейного участка(Cfg_Node) организованны в двунаправленный список. У Cfg_Node есть ссылки на первую и последнюю операцию линейного участка. Все Phi_Node линейного участка организованны в однонаправленный список. У Cfg_Node есть ссылка на первый фи-узел линейного участка.

При трансляции должен быть реализован механизм постоения DU графа на основе построенного SSA.
Все temp переменные SSA должны быть переведены на виртуальные регистры.
Также, все локальные переменные должны быть связаны с виртуальными регистрами (v1…vn) и др.

пример логического представления простого кода:

a=0;
while (a<10)
{
    a = a+1;
}
b=a;
du1.gif

а также структуры phi-функции

du2.gif

P - предшественник (predecessor)
S - последователь (successor)

Аналогичный алгоритм был предложен для реализации DFTranslation:

- Трансляция Данных, которыми заполнет СFG Феникса в более удобный для
нас формат.

Input:
      old_cfg
      old_bb
      old_edge
      old_inst - инструкции в представлении Феникса

Create inst_tb hash

foreach old_bb in old_cfg
        create new_bb
        create hash_entry(node_tb,new_bb,old_bb) 
        create hash_entry(inst_tb,new_bb,old_bb)

foreach old_bb in old_cfg
        new_bb = hash_get(node_tb,old_bb)
        foreach old_inst in old_bb
                new_inst = hash_get (inst_tb,old_bb) 
                insert old_inst in new_bb
                create hash_entry(inst_tb, new_inst,old_inst)

foreach old_inst in old_cfg
        new_inst = hash_get(inst_tb, old_inst)
        foreach succ of old_inst
                if (is_phi) 
                   create new_phi
                   add new_phi into new_bb

                 new_succ = hash_get(node_tb, old_succ)
        create du_edge
        link(du_edge, new_inst,new_succ)

По окончании встречи разделились на три группы, которые будут
реализовывать определенные части задач, а именно:

1. Григорий Речистов (GGG)

  • Смагин
  • Жемалетдинов
  • Некрылов
  • Шумский

реализуют DF Translation

2. Александр Костюченко (MICRO)

  • Уваров
  • Бутейко
  • Шкорута
  • Каздагли

реализуют DF Translation

3. Павел Анохин

  • Баженов
  • Шевцов
  • Асеев
  • Бражников

реализуют СF Translation

Комментарий:
Я был бы признателен, если бы кто-нибудь не поленился и отобразил бы тут картинки CFG и DU графов,
которые я рисовал на доске на семинаре. Наглядные примеры всегда лучше голословного описания.

\\16.10.2006 dimstar


Привожу диаграммы рассмотренных структур и пояснения по тому, что они обозначают.

cfg

Под Базовым блоком подразумевается неветвящаяся последовательность элементарных операций, таких как присваивание, арифметика, вызовы функций(?), без ветвлений:

basic_block2

Пример простого блока - блок вызова функции:

call_block

В нём передача управления передается внешней функции, но известно, что она вернется в тот же блок (подавляющее большинство функций в реальных программах так и поступают)

Пример блоков ветвления - это представления операторов if-else и switch:

branch_switch

В этой диаграмме уже отражен тот факт, что необходимо создать представление не только для понятия "блок", но и для понятия "связь" (edge), так как по крайней мере одно существенное свойство у неё есть - это указатель на блок, с которого начался перход (см. красные указатели). Один указатель у связи, исходящей из branch-блока, имеет значение null, ибо мы всегда можем определить одну часть ветвления непосредственно идущей после branch-а, и определять предка по физическому расположению

А вообще это нужно для задач профилирования и оптимизации, см пример BBcounter из Phoenix RDK.

У swicth-блока все ветки равны, поэтому все связи хранят указатель на блок.

// GGG

16.10.2006 диаграммы с Гришей сделали
// MICRO

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