А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 160

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 160)

9.38) со входным узлом 1. Входной узел доминирует над всеми узлами (это утверждение справедливо для любого графа потока). Узел 2 доминирует только над самим собой, поскольку управление может достичь любого другого узла вдоль пути, начинающегося с 1 — 3. Узел 3 доминирует над всеми узлами, кроме 1 и 2. Узел 4 доминирует над всеми узлами, кроме 1, 2 и 3, так как все пути из 1 должны начинаться с 1 — 2 — 3 — 4 нлн 1 — 3 — 4. Узлы 5 и б доминируют только над самими собой, поскольку управление может пропустить один узел, пройдя через другой. Наконец, узел 7 доминирует над 7, 8, 9 и 10; 8 — над 8, 9 и 1О, а 9 и 10 — только над самими собой.

и Полезным способом представления информации о доминаторах является дерево, именуемое деревом доминаторов, в котором входной узел является корнем, а каждый узел д доминирует только над своими потомками в дереве. Например, на рис. 9.39 показано дерево доминаторов для графа потока на рис. 9.38. Существование деревьев доминаторов следует из свойства доминаторов: каждый узел п имеет единственный непосредственный домипатор т, который явля- 788 Глава 9. Машинно-независимые оптимизации 9 ю Рис.

9.38. Граф потока Рис. 9.39. Дерево доминаторов лля графа потока на рис. 9.38 Свойства отношения йонг Ключевое наблюдение, касающееся доминаторов, заключается в том, что если мы возьмем любой ациклический путь от входного узла к узлу и, то все доминаторы и будут располагаться на этом пути, более того — они будут располагаться в одном и том же норядке вдоль любого пути. Чтобы понять, почему это так, предположим, что имеется один ациклический путь Р1 к и, на котором доминаторы а и 6 встречаются в указанном порядке, и другой путь Рз к и, на котором 6 предшествует а. Тогда мы можем следовать по пути Р, до а, а затем по пути Рз до и, избежав тем самым прохождения через доминатор 6. Таким образом, 6 не доминирует над и. Эта аргументация позволяет нам доказать транзитивность отношения йот: если а йот б и 6 йот с, то а йот с.

Кроме гого, отношение йот антисимметрично: если а ф Ь, невозможно одновременное выполнение а аот 6 и 6 йот а. Если и а, и 6 являются доминаторами и, то должно выполняться либо а йот 6, либо 6 йот а. Наконец, отсюда следует, что каждый узел и за исключением входного должен иметь единственный непосредственный доминатор, т.е. доминатор, находящийся ближе всего к и вдоль любого ациклического пути от входного узла до и.

ется последним доминатором и на любом пути от входного узла до и. В терминах отношения йот непосредственный доминатор ги обладает тем свойством, что если й ф и и й йот и, то й йот ги. 789 9.б. Циклы в графах потоков Мы приведем простой алгоритм для вычисления доминаторов каждого узла и в графе потока, основанный на том принципе, что если ры рз,..., рь являются предшественниками п и д ~ и, то д ггот п тогда и только тогда, когда и гтот р, для всех г.

Данная задача может быть сформулирована как задача анализа потока данных в прямом направлении. Значениями потока данных являются множества базовых блоков. Множество доминаторов узла, исключая его самого, представляет собой пересечение доминаторов всех его предшественников; таким образом, оператором сбора является пересечение множеств. Передаточная функция для блока В просто добавляет В к входному множеству узлов. Граничное условие заключается в том, что доминатором входного узла является сам входной узел. Наконец, внутренние узлы инициализируются универсальным множеством, т.е.

множеством всех узлов. Алгоритм 9.34. Поиск доминаторов Вход: граф потока С с множеством узлов Аг, множеством ребер Е н входным узлом. ВыхОд: для всех узлов и, е Х значение 27 (и), представляющее собой множество узлов, доминирующих над и. МьтОд: найти решение задачи потока данных, параметры которой показаны на рис. 9.40. Базовые блоки представляют собой узлы. В(п) =. Оит)п] лля всех пЕЛ~. а ДОМИНАТОРЫ Рнс. 9.40. Алгоритм потока данных для вычисления доминаторов Поиск доминаторов с использованием алгоритма потока данных весьма эффективен.

Узлы графа должны посещаться всего лишь несколько раз, как будет видно из раздела 9.6.7. Пример 9.35. Вернемся к графу потока на рис. 9.38 и предположим, что цикл в строках 4 — б на рнс. 9.23 посещает узлы в числовом порядке. Пусть 27 (и)— 790 Глава 9. Машинно-независимые оптимизации множество узлов в опт )и). Поскольку входной узел имеет номер 1, в строке 1 Р (1) присваивается значение ( Ц.

Узел 2 в качестве предшественника имеет только узел 1, так что Р (2) = (2) 0 Р(1). Таким образом, Р (2) устанавливается равным (1, 2). Затем рассматриваем узел 3 с предшественниками 1, 2, 4 и 8. Поскольку все внутренние узлы иннциализированы универсальным множеством Ю, Р (3) = (3) О ((1) П (1, 2) й (1, 2,..., 10) О (1, 2,..., 10)) = (1, 3) Остальные вычисления приведены на рис. 9.41.

Поскольку эти значения не изменяются при второй итерации внешнего цикла в строках 3-6 на рис. 9.23, а, они являются окончательным решением задачи о доминаторах. а Р(4) =(4) О(Р(3) ОР(7)) =(4) О((13) О(1,2,...,10)) = (13 4) Р (5) = (5) О Р (4) = (5) О (1,3,4) = (1, 3,4,5) Р(6) = (6) О Р(4) = (6) О (1,3,4) = (1,3,4,6) Р(7) = (7) 0 (Р(5) О Р(6) Г1Р(10)) = = (7) О ((1,3,4,5) О (1,3,4,6) О (1,2,...,10)) = (1,3,4,7) Р(8) = (8) 0 Р(7) = (8) О (1,3,4,7) = (1,3,4,7,8) Р(9) = (9) 11 Р(8) = (9) 0 (1,3,4,7,8) = (1,3,4,7,8 9) Р (Го) = (Го) О Р (8) = (Го) О (1,3 4 7 8) = (1, 3 4 7 8, .Гй) Рис.

9.41. Завершение вычисления доминаторов нз упражнения 9.35 9.6.2 Упорядочение в глубину Как говорилось в разделе 2.3.4, поиск в графе в глубину (оер1а-йгз1 зеагсп) однократно посещает все узлы графа, начиная с входного узла и посещая, в первую очередь, насколько это возможно, узлы, максимально удаленные от входного. Путь поиска в глубину образует глубинное остовное дерево (охватывающее вглубь дерево) 1оергц-йгз1 зрапп1пи 1гее — РРЯТ). Вспомним из раздела 2.3.4, что обход в прямом прядке посещает узел перед посещением любого из его дочерних узлов, которые затем рекурсивно посещаются в порядке слева направо. Обход в обратном порядке сначала рекурсивно слева направо посещает узлы, дочерние по отношению к текущему, а затем посещает сам текущий узел.

Есть еще один вариант упорядоченна, важный для анализа графа потока,— улорядочение в глубину (оер1п-йгз1 огдепп8), которое представляет собой обращение обратного порядка обхода. Иначе говоря, при упорядочении в глубину мы посещаем узел, затем обходим его крайний справа узел-преемник, после этого— узел, расположенный слева от него, и т.д.

Однако перед тем как строить дерево для 791 9.6. Циклы в графах потоков графа потока, следует выбрать, какой из преемников является крайним справа, какой — его левым соседом и т.д. Перед тем как перейти к алгоритму упорядочения в глубину, рассмотрим пример. Пример 9.36. Одно из возможных упорядочений в глубину графа на рис. 9.38 показано на рис.

9.42. Сплошные линии образуют дерево; пунктирные представляют собой прочие ребра графа потока. Обход дерева в глубину дает нам 1 — 3 — 4— — 6 — 7 — 8 — 10, после чего выполняется возврат к 8 и посещение 9. Затем мы снова возвращаемся в 8, отступаем в 7, б и 4 и посещаем 5. Из 5 мы возвращаемся в 4, оттуда — в 3 и 1. Из 1 посещаем 2, опять возвращаемся в 1, и на этом обход завершается. Последовательность прямого обхода, таким образом, вьплядит так: 1, 3, 4, 6, 7, 8, 10, 9, 5, 2 Последовательность обратного обхода дерева на рис.

9.42 выглядит так: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 Упорядочение в глубину, которое представляет собой обращение обратного порядка обхода, дает последовательность 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 Рнс. 9.42. Представление графа потока на рнс. 9.38 Теперь приведем алгоритм, который находит глубинное остовное дерево и упорядочение графа в глубину. Этот алгоритм для графа на рис. 9.38 находит ПРЕТ на рис. 9.42. 792 Глава 9. Машинно-независимые оптимизации Алгоритм 9.37. Глубинное остовное дерево и упорядочение графа в глубину ВхОЛ: граф потока С. Выход: РгЯТ Т графа С и порядок узлов С. Метод: используется рекурсивная процедура зеагсЬ1п), показанная на рис. 9.43. Алгоритм инициализирует все узлы С значением "непосещен'* и вызывает зеагса 1ио), где пе — входной узел. При вызове зеагсЬ (и) узел и маркируется как посещен", чтобы избежать повторного добавления и в дерево.

Процедура использует с для счета от количества узлов в С до 1, присваивая поочередно номера в порядке в глубину фп ~п] встречающимся узлам п. Множество ребер Т образует глубинное остовное дерево С. о уоЫ зеагсл (и) 1 Маркируем п как "посещен"; Гог (каждый узел а, являющийся преемником и) Ы (в "непосещен") 1 Добавляем ребро и — а в Т; яеагсй (а); грп [и) = с; с=с — 1; тагд1) 1 Т = о; Р" Множество ребер *! зог (каждый узел и из С) Маркируем и как "непосещен"; с = количество узлов в С; яеагсй (по); Рис. 9.43. Алгоритм поиска в глубину Пример 9.38. Для графа потока на рис. 9.42 алгоритм 9.37 устанавливает с равным 1О и начинает работу вызовом 5еагсЬ 11).

Характеристики

Список файлов книги