Propagation Packet

Propagation Packet - это пакет для будущих оптимазаций таких как deadcode elimination(как я понял), например. Сейчас же стоит целью написать только шаблон, в который в будующим мы будем вставлять наши оптимазации.

Алгоритм.

Рассмотрим следующий граф, в котором все блоки пронумерованы:
fog0.gif
Целью нашего алгоритма является создание таблицы битовых векторов.
Каждый этот битовый вектор отождествляется с дугой нашего графа. битовый вектор - это массив, каждый элемент которого представляет блок графа. Он показывает через какие блоки мы прошли по дороге к этой дуге. Этот блок отмечается 1 в массиве битового вектора. Пока обратные петли не рассматриваются.
В нашем примере это будет выглядеть так:
fog1.gif
Над каждом блоком совершается 3 операции, расчет входных битовых векторов, обработка их, изменение выходных векторов (если нужно):
fog2.gif

Реализация.

Реализация такого алгоритма следующая:

do
{
  flag = NO_UPDATE;
  for each node in cfg
  {
      bv = calc_input_bv(node);
      update_node_bv(node, bv);
      if (need_update_bv(node, bv)
      {
           update_out(node);
           flag = UPDATE;
      }
    }
}
while(flag == UPDATE);

Я скорее всего что-то недопонял. Если что, то поправьте.

Небольшие уточнениия

do
{
  flag = NO_UPDATE;
  for each node in cfg
  {
      bv = calc_input_bv(node);
      update_node_bv(node, bv);
      for each out_edge in node
      {
          edge_bv = get_edge_bv(out_edge);
          if (need_update_bv(edge_bv, bv)
          {
               update_edge_bv(out_edge,bv);
               flag = UPDATE;
          }
      }
  }
}
while(flag == UPDATE);

//dimstar

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