Control Flow Translation

На семинаре было решено наследовать наш CF_Graph от Phx::Graphs::Graph

Мы переносим часть функциональности Phx::Graphs::FlowGraph (не всё) + то, что нужно нам.

Нам нужно для CF_Graph'а:

- ссылки на процедуру(Proc) и ссылки на дерево циклов (LoopTree).
- возможно, ссылку на фениксовский CFG, дабы не произошло потери информации. (пока я плохо себе представляю картину в целом, поэтому, может быть, это и не надо)

Далее, нам нужно описать Cfg_Node. Single_Block, IF_Block, Switch_Block, Temp_Block - описываются этим классом(то есть у нас есть набор флагов, из которых мы узнаём, какой именно этот блок). Этот класс наследуется от Phx::Graphs::Node. Думаю, полезно будет поизучать документацию также по Phx::Graphs::BasicBlock.

И следующий класс Cfg_Edge. Напомню, что по-крайней мере одное существенное свойство, о котором мы говорили, - это
указатель на branch или switch блок
В фениксовском Phx::Graphs::FlowEdge этого похоже нет.
Наследовать его имеет смысл от Phx::Graphs::Edge.

Литература
* Phoenix Documentation: Phoenix Documentation -> Reference -> Phx -> Namespaces -> Graphs -> Classes -> (Node, Graph, Edge, FlowGraph, FlowEdge, BasicBlock)

//20.10.06 snark

Внёс некоторые изменения, согласно тому, что решили на семинаре. Когда разберусь с CVS, код перенесу туда.
//21.10.06 snark

Насчёт типа node. Думаю, создать enum с перечислением возможных типов:
enum nodetype {nt_Start, ntStop, nt_Single, nt_IF, nt_Switch, nt_Temp};
Кстати, про Start и Stop я в предыдущих отчётах не писал. А это тоже важно.
Потом я не совсем понял, Call_Block - это отдельный вид блока, или пример для Single_Block.

//24.10.06 snark

Да, флаги реализуются в виде enum'а.
Call_Block делать не нужно. Если узел содержит call, то это обычный Single_Block.

//24.10.06 dimstar

Чем не устраивает класс Phx::Graphs::FlowEdge? Этот класс итак наследуется от фениксовского Edge.
Примерно наш класс должен выглядить так или нет:

class Cfg_Edge: Phx::Graphs::Edge
{
protected:
    CF_Graph *cfg;
    Cfg_Node *ptr_to_branch;
    Cfg_Node *ptr_to_switch;

public:
    void Cfg_Edge();
         ~Cfg_Edge();

    void Dump();
}

//25.10.06 firt
Re to firt: Я так понимаю, что FlowEdge всё-таки чем-то нас не устраивает. По-крайней мере dimstar, настоятельно рекомендовал наследовать от обычного Edge.

А стоит ли разделять
Cfg_Node *ptr_to_branch и
Cfg_Node *ptr_to_switch ?
По сути это ведь одно и то же. А если уж надо проверить switch это или branch, то перейдём по ссылке и узнаем.
Хотя лично я не против и разделять. Хотелось бы только определиться.
//25.10.06 snark
Перекинул коды на CVS. Думаю, что на этой странице приводить подробные коды не имеет смысла(хотя бы потому, что тогда придётся обновлять их, каждый раз, когда кто-то добавит в CVS что-то новое).

Теперь:
Идеология Control Flow Graph Framework
У нас есть класс CF_Graph.
Он используется для создания объектов Cfg_Node и Cfg_Edge и соответственно добавляет их при создании в граф.
Доступ к Cfg_Node'ам и Cfg_Edge'ам мы получаем через список System::Collections::Generic::List<…>. Эти листы
объявлены, как

typedef System::Collections::Generic::List<Cfg_Node ^> Cfg_Node_List;
typedef System::Collections::Generic::List<Cfg_Edge ^> Cfg_Edge_List;

Работать с ними можно почти как с STLевскими листами.

С Cfg_Edge и Cfg_Node работаем с помощью интерфейса родительского класса.
В Cfg_Node есть поле NodeType type;
NodeType это enum.
Как ясно из названия, это тип блока.

У Cfg_Edge есть поля
bool conditional и Cfg_Node ^ ptr_to_branch.
Отдельный ptr_to_switch IMHO нет смысла делать.

Что ещё не сделано(на мой первый взгляд)
Надо запретить доступ к родительским NewEdge и NewNode, чтобы не было конфликтов.

Насчёт InsertNodeAfter и InsertNodeBefore - их я не объявлял. В принципе можно обойтись без них (тогда нужно перенести их из public'а, что я ещё не делал), либо override'ить. Главное, чтобы все добавленные вершины и рёбра оказались в соответствующих списках.

Нужно либо запретить, либо переписать SplitEdge. Предлагаю оставить только SplitEdgeWithNode.

Start и End блоки предлагаю создавать при создании самого графа. Соответсвенно нужно ещё чтоб в интерфейсе были указатели на эти блоки. И убрать CreateStartAndEndNodes, наследованный из родительского класса.

Далее, в Cfg_Node и Cfg_Edge нужно переопределить Delete. Нужно, чтоб при этом обновлялись листы в CF_Graph.

Теперь вдруг подумалось:
У родительского класса уже есть указатель на граф. Может и не стоит создавать свой такой же.

Пока всё. Обновления следуют…
//26.10.06 snark

Замечания при беглом просмотре:
1) Branch и Switch - это инструкции, никаким боком к классу CFG_Node они не могут относится. Разделять эти понятия не имеет смысла. Нужно создать один указатель с именем Source.
2) Какая необходимость хранить все узлы и дуги в списках? Нужно иметь возможность получить Start и Stop узлы от графа. То есть всего 2 указателя в классе CFG.
3) Предлагаю сделать вот такую прослойку между Phx::Graph и нашим CFG
(многие свойства, которые внесем в прослойку будут полезны для других структур данных)
(пометьте из перечисленных те свойства, которые можно получить из родитеских классов):

class IGraph: Phx::Graphs::Graph{
    MemPool * Node_pool; // Пул для хранения узлов (optional)
    MemPool * Edge_pool; // Пул для хранения дуг (optional)
    INode * First_node;  // Ссылка на первый узел. (Есть родительский Node ^ NodeList //snark) 
    Int Nodes_number; // Кол-во узлов (Есть UInt NodeCount //snark)
    Int Edges_number; // Кол-во дуг (Этого, кажется, у родителя нет //snark)
    IGraph * Copy_graph; // Ссылка на копию
}
class INode: Phx::Graphs::Node{
    Int Number; // Номер узла 
    IGraph * Graph; // Ссылка на Граф
    INode * Copy_node; // Ссылка на копию узла
    INode * Phys_prev; // Физ. предшественник
    INode * Phys_next; // Физ. последователь
    IEdge * First_input_edge; // Первая входящая дуга (Есть Edge ^ PredEdgeList//snark)
    IEdge * First_output_edge; // Первая выходящая дуга (Есть Edge ^ SuccEdgeList//snark)
    Marker * Marker; // Маркер
}
class IEdge: Phx::Graphs::Edge{
    Inode * Pred_node; // Ссылка на предшественника дуги (Есть Node ^ PredNode//snark)
    Inode * Succ_node; // Ссылка на последователя дуги (Есть Node ^ SuccNode//snark)
    IEdge * Copy_edge; // Ссылка на копию
    Int Number; // Номер дуги
    IEdge * Next_input_edge; // Ссылка на следющую входящую дугу(есть Edge ^ NextPredEdge//snark)
    IEdge * Next_output_edge; // Ссылка на следующую выходящую дугу(есть Edge ^ NextSuccEdge//snark)
    Marker * Marker; // Маркер
}
//Далее уже CFG, наследуемся от I прослойки
class CFG: IGraph{
    CFG_Node * Start_node; // Ссылка на Start узел (Есть Node ^ StartNode //snark)
    CFG_Node * Stop_node; // Ссылка на Stop узел (Есть Node ^ EndNode//snark)
    LT * LoopTree; // Ссылка на дерево циклов
}
class CFG_Node: INode {
    CFG_Node_Type CFG_node_type; // Тип узла
    DUNode * First_phi_node; // Ссылка на первый фи-узел
    DUNode * First_oper; // Ссылка на первую операцию
    DUNode * Last_oper; // Ссылка на последнюю операцию
    Loop * Loop; // Ссылка на цикл
    Bool Is_head; // Является ли узе головой цикла
    Double Counter; // Счетчик узла
}
class CFG_Edge: IEdge{
    CFG_Edge_Type CFG_edge_type; // Тип дуги
    DUNode * Source_oper; // Ссылка на source операцию (branch, swith, or null)
    Bool is_back; // Является ли дуга обратной дугой
    Bool is_break; // Является ли дуга выходом из региона
    Double Counter; // Счетчик дуги
    Double Probability; // Вероятность дуги
}
class LT: IGraph {
    Loop * Root; // Ссылка на root (ациклический участок)
    CFG * CFG_Graph; // Ссылка на CFG Граф
}
class Loop: Inode {
    CFG_Node * Loop_head_node; // ССылка на CFG узел, который явл. говой цикла
    Bool is_reducible; // Сводимый ли цикл
}
enum {
    START;
    STOP;
    IF;
    SIMPLE;
    RETURN;
    SWITCH;
    TMP;
    RECOVER;
} CFG_Node_Type; // Типы CFG узлов
enum {
    SIMPLE;
    SWITCH;
    CONDITIONAL;
    TMP;
}CFG_Edge_Type; // Типы CFG дуг

//26.10.06 dimstar

Несколько вопросов:
- Насчёт нумерации: мы делаем какую-то свою нумерацию или пользуемся тем, что фениксовские родительские типы поддерживают свою нумерацию.
- что имеется в виду под физическим предшественником/последователем узла? Просто некоторый предшественник/последователь, позволяющий действовать с узлами, как с двусвязным списком?
//27.10.06 snark

1) С нумерацией не так все просто. В идеале нужно реализовать несколько типов нумераций (RPO, DFO и т.д.). Я все расскажу на семинарах. Пока что можно просто отнаследовать ту нумерацию, которая есть в PhxCFG.
2) Именно двунаправленный список, реализованный при помощи ссылок на последователя и предшествыенника. Зачем это нужно - ну я упоминал об этом на семинарах, но могу еще раз напомнить:
- для обхода всего графа;
- для того, чтобы иметь возможность скидывать последовательно все блоки в ассемблерный файл.
Тем не менее, лучше реализовать эту связь через ссыки в самом узле, нежели хранить эту связь в отдельном списке. Так как при удалении и добавлении узла гораздо легче апдейтить ссылки, чем добавлять и удалять элементы списка.
//27.10.06 dimstar

Теперь вроде понятно. На всякий случай уточню: получается можно использовать родительские Next и Prev (они есть). Для обхода всего графа нам всё равно, лишь бы на все узлы нашлись ссылки. Для скидывания в ассемблерный файл, порядок скидывания как раз и будет выбираться в кодогенераторе. Надо только убедиться, чтобы была возможность модифицировать его.
27.10.06 snark

Да. Именно так.
//27.10.06 dimstar

CVS updated
//29.10.06 snark

Написал реализацию для CFG, которой не связана с отличиями от родительских классов.
Теперь, кажется, есть всё для реализации алгоритма перевода фениксовского графа в наш.
По-моему разумно такой перевод осуществлять в конструкторе класса CFG.

Пока это выглядит так:

CFG::CFG(Phx::Graphs::Graph ^src)
{
        //сохраняем ссылку на копию
        Copy_graph = src;

        //создаём таблицу узлов
        System::Collections::Hashtable node_tb;

        node_tb.Clear();

        //перебираем узлы старого графа

    Phx::Graphs::Node ^ nodewalker = src->NodeList;

        do
        {
            Cfg_Node ^ newNode = NewCfgNode();

            //инициализация узла, определение необходимых свойств
            newNode->Copy_node = nodewalker;
            if (nodewalker->IsStart) 
                {
                    newNode->CFG_node_type = NT_START;
                    CfgStartNode = newNode;
                }

            if (nodewalker->IsEnd)
                {
                    newNode->CFG_node_type = NT_STOP;
                    CfgEndNode = newNode;
                }
            //...
            node_tb.Add(nodewalker, newNode);//запись в хэш-таблице. Ключ - старый узел, значение - новый узел
            nodewalker = nodewalker->Next;
        } while (nodewalker != LastNode);

        //перебираем ребра старого графа: сначала узлы, а потом ребра, исходящие из каждого узла
        nodewalker = src->NodeList;

        do
        {
            Phx::Graphs::Edge ^ edgewalker = nodewalker->SuccEdgeList;            
            Cfg_Node ^ predNode = dynamic_cast<Cfg_Node ^>( node_tb[nodewalker] );
            //обход ребер

            do
            {
                Cfg_Node ^ succNode = dynamic_cast<Cfg_Node ^>( node_tb[edgewalker->SuccNode] );                    
                Cfg_Edge ^ newEdge = NewCfgEdge(predNode, succNode);
                //инициализация ребра, определение необходимых свойств
                newEdge->Copy_edge = edgewalker;
                //...
                edgewalker = edgewalker->NextSuccEdge;
            } while (edgewalker != nodewalker->SuccEdgeListTail);

            nodewalker = nodewalker->Next;
        } while (nodewalker != LastNode);

};

Не стал пользоваться фениксовскими макросами foreach, поскольку фениксовская доументация в этом месте, по-моему, несколько отличается от действительности.
//4.11.06 snark

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