Средства разработки приложений


Граф зависимостей по данным - часть 2


Это свойство графа будет использоваться нами в дальнейшем.

Пример функции и ее графа зависимостей по данным приведен на Рис. 1. DDG состоит из трех узлов: двух простых узлов и оператора цикла, раскрывающегося в DDG второго уровня.

Граф зависимостей по данным строится для каждой функции программы. Алгоритм построения состоит из следующих этапов:

  • Построение графа потока управления программы.
  • Выбор программных блоков, которые будут узлами текущего уровня иерархии DDG.
  • Нахождение зависимостей по данным между этими узлами с помощью алгоритма достигающих определений.
  • Если необходимо, продвинуться на следующий уровень иерархии и достроить граф.

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




Начало  Назад  Вперед



Книжный магазин