Sem5

На встрече обсуждали критерии именования классов, типы констукторов и т.п.

Общие требования.

Предложены правила именования методов, которые следует использовать в новом коде, и привесит старый к надлежащему виду.

  • Для именования полей, указывающих на следующий/предыдущий объект в двунаправленных списках, графах, деревьях использовать имена pred и succ или Pred и Succ (от Predecessor и Successor). Также возможно использовать pred и next, но только в списках [тогда уж в списках нужно использовать prev и next \\dimstar]
  • Описывать и использовать методы Set…() и Get…() для установки private-полей классов. Называть их именно так.
  • Если нужно иметь метод удаления объекта из графа/дерева/списка, именовать его Delete…(); не использовать Remove…(). Если необходимо назвать метод, который отделяет узел от дерева, в котором он содержался, именовать его Unlink…(), а вообще воздержаться от таких методов, если это возможно и целесообразно.
  • Возможно, следует создать сущность "граф", которая отвечает, в частности, за создание своих узлов. Это избавит нас от явления висячих узлов, которые только что созданы, но еще не принадлежат графу - нафига такое счастье?
  • Соответсвенно дуги (Edges) всегда создаются с указанием тех элементов, которые они соединяют, и присоединением к ним.
  • В узлах иметь указатель только на первую дугу. В этой дуге иметь укзатель на следующую дугу, исходящую из этого узла и т.д. Это позволит обходить все дуги, исходящие из одного узла, с помощью итератора (что-то вроде этого)
for ( edge = node->GetFirstSucc();
       edge != nullptr;
       edge=edge->GetNextSucc())
{
    /* Some useful operations with this edge */
    succ_node = edge->GetEdgeSucc();
    ...
}

Исправлено \\dimstar

Deninition-Usage (файлы dug.*)

  • Переписать классы DU_Node и потомков с указанием IGraph как родительского. Соответственно использовать наработки этого класса. Аналогично использовать IEdge.
  • Иметь конструктор, который создает Oper_Node не на основе Phx::IR::Instr, так как далее будут создаваться сущности, совершенно не зависящие от Phx. Единственный необходимый параметр при создании - это Opcode
  • Переименовать InstrType в Opcode, так как первое имя будет использовано потом в другом контексте.

Control-Flow (cfg.*)

  • CopyGraph() в IGraph переименовать в grpah_copy(), а лучше вообще заменить на Get…()/Set…() (тут я не очень понял), чтобы не допускать неправильного толкования назначния метода

Имелось в виду, что метод graph->CopyGraph() должен создавать копию графа со вcеми дугами и узлами, а метод graph->GetGraphCopy() должен всего лишь возвращать private поле graph_copy. \\dimstar

  • см. рекомендацию насчет DeleteEdge(). Следует переименовать/удалить Remove_Node()
  • Функциональность InheritEdge() и InheritNode() перенести в Cfg_Edge и Cfg_Node соответсвенно.
  • Что-то там с пулом не то - я не очень понял, вроде имелось в виду использовать его как хранилище памяти. Мне кажется, в добавок к managed-mode его использование так вообще грозит катастрофой. Так что без разъяснений со стороны руководства его использование не стоит расширять.

Еще были введены планы по нумерации узлов. Каждому узлу в графе надлежит иметь уникальный номер. Встает вопрос - как эти номера раздавать? Были рассмотрены следующие типы нумерации:

  • Собственная (own_ID) Номер вдается при создании, каждый раз берется число, на один больше предыдущего выданного. Ососбой пользы от него нет.
  • Depth First Order (DFO) - ???
  • Reverse Post Order (RDO_ID) - соблюдается правило: номер блока всегда больше, чем номера его предков. Необходимо придумать алгоритм выдачи номеров.

Еще была рассмотрена концепция маркеров, но тут я мало что понял.

//GGG


Попытаюсь объяснить как я понял

Концепция нумерации заключается в том, что кадому узлу сопостовляется номер, для того чтобы оптимизирующему алгоритму было проще вытаскивать объекты.

создаются они приблизительно так:

Было рассмотрено несколько типjв номеров:

own_number - номер, который задается графом, при построении CFG:

node = graph-> CreateNewNode()

dfo_number - номер, задаваемый по принципу Depht First Order.

правило данного принципа: среди successorов текущего узла есть только блоки с номерами больешми текущего (возможно строго на 1)

иллюстрация данного принципа:

.

        1

       /  \
      2   5

     / \ /

    3   6

     \ /

      7

приблизительный код данного метода выглядет так:

DFO_N = 0

NodeNumber (node)
{
   node -> dfo_number = DFO_N
   DFO_N++
   foreach succ_node
   {
      NodeNumber (node)
   }
}

но, подобный код заполняет граф все же так:

.

        1

       /  \
      2   -

     / \ /

    3   -

     \ /
      4

        1

       /  \
      2   -

     / \ /

    3   5

     \ /
      6

и в итоге:

1

       /  \
      2   7

     / \ /

    3   8

     \ /

      9

rpo_number - номер, задаваемый по принципу Reverse Post Order.

правило данного принципа: номер текущего блока больше всех его предшественников (по ирархии)

иллюстрация данного принципа:

.

        1

       /  \
      2   3

     / \ /

    4   5

     \ /

      6

приблизительный код данного метода выглядет так:

node_count = 6
DFO_N = 0
RPO_N = node_count

NodeNumber (node)
{
   node -> dfo_number = DFO_N
   DFO_N++

   foreach succ_node
   {
      NodeNumber (node)
   }

   RPO_N--
   node -> rpo_number = RPO_N
}

Сопоставление узла и номера лучше всего держать в массиве, для наиболее быстрого обращения к элементам.

В нашем компиляторе было решено использовать принцип RPO, так как он более удобный и понятный.

Так же возможне случай с обратной связью:

.

        1

       /  \
 ---> 2   3
 |
 |   / \ /
 |
 -- 4   5

     \ /

      6

Для таких случаев необходимо проверять а не задан ли уже номер для текущего узла, если да, то скорее всего мы сюда пришли по обратной связи ниже, поэтому нумерация не делается и мы возвращаемся к следующему succ_node не от текущего, а от предыдущего узла.

Если проводить RPO нумерацию, то ты придешь в узел 2 из узла 4 и будешь проверять, поставлен ли в узле 2 номер. Но фишка алгоритма в том, что в этот момент узлу 2 еще не будет поставлен номер. Так что вот тут и нужно использовать маркер, а не проверку установки номера.
\\dimstar

Некоторым узлам, опять таки для тех оптимизаций иногда необходимо присваивать маркеры с разным значением. Основное отличие маркеров от номера - он задается не всем узлам, а только тем, которые интересуют оптимизацию. Пример сопоставления одного маркера ноду:

SetNodeMarker(node,marker) - вызывается после инкримента DFO_N, либо в другом месте.

при этом marker должен быть объявлен как поле в CFG:

cfg_node
{
   int marker
}

и уже в SetNodeMarker вызывать что-то типа этого:

maker = graph-> NewMarker()

Проблема с маркерами заключается в том, что если иметь возможность присвоить каждому узлу 2, а лучше 4 маркера, то при объявлении простого массива marker[2~4] возможно наложение данных, при нескольких обходах графа. Реализацию решения этой проблемы, как я понял, нам расскажут на следующем семинаре.

ну вот вроде бы и все что я усвоил. к конце недели постараюсь реализовать нумерацию, если что не так понял - исправляйте.

Тогда уж и реализуй простые маркеры (т.е. когда существует одновременно не более 1го маркера, след. маркер выделяется просто инкементацией номера предыдущего маркера). Маркирование узлов тебе понадобится для RPO нумерации.
\\dimstar

// MICRO

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