14.6. Доминаторы в графе программы
Пусть G — граф программы с начальной вершиной s. Если в нем вершина v входит в каждый ориентированный путь из s в w, то v называется доминатором w и обозначается DOM (w). Если v — доминатор w и любой другой доминатор w доминирует также и над v, то v называется непосредственным доминатором w и обозначается
Например, в графе программы G, представленном на рис. 14.22, а, вершина 1 является непосредственным доминатором вершины 9. Можно показать, что каждая вершина графа программы
кроме начальной вершины s, имеет единственный непосредственный доминатор. Ребра
образуют ориентированное дерево с корнем s, называемое деревом доминаторов графа G. Вершина v доминирует над вершиной w тогда и только тогда, когда она является собственным предком w в дереве доминаторов. Если граф G представляет собой схему потоков управления в программе ЭВМ, то дерево доминаторов дает информацию о том, какой вид выполнения программы является надежным. Дерево доминаторов графа программы, изображенного на рис. 14.22, а, представлено на рис. 14.22, б.
Рассмотрим алгоритм Ленгауэра и Тарьяна [14.42] для нахождения дерева доминаторов графа программы. Этот алгоритм является более простым и быстродействующим вариантом алгоритма, представленного ранее Тарьяном [14.43].
Пусть G — граф программы с начальной вершиной s. Пусть Т — дерево ПВГ для этого графа. В последующем мы будем идентифицировать вершины графа G их глубиной. Более того,
означает, что
является предком
означает, что
означает, что
является отцом у в Т.
На рис. 14.22, а сплошные ребра являются ребрами дерева, а штриховые не являются ребрами дерева по отношению к ПВГ. Полудоминатор каждой вершины указан в скобках рядом с номером вершины.
Алгоритм Ленгауэра и Тарьяна в качестве первого шага вычисляет полудоминаторы для всех вершин. Затем полудоминаторы используются для вычисления непосредственных доминаторов вершин. Следующая теорема предоставляет способ их вычисления.
Теорема 14.14. Для любой вершины
и существует такое ребро
Доказательство. Пусть
равно правой части выражения (14.6). Можно показать, используя определение полудоминаторов, что SDOM
Чтобы доказать, что SDOM
положим
и пусть
— такой ориентированный путь, что
для
Если
, то в соответствии с выражением
. Таким образом, SDOM
Предположим, что
. Пусть j — минимальное число, для которого верно, что
Такое число
существует, так как в качестве него можно использовать число
Потребуем, чтобы
при
Предположим обратное, что
для некоторых
Тогда выберем такое число i, что
и — минимально. Согласно лемме
что противоречит выбору числа
Это доказывает правомерность приведенного выше требования.
В свою очередь это влечет следующее утверждение:
Так как
то из выражения (14.6) получаем, что
Следовательно,
Таким образом, либо
либо
а мы имеем
и теорема доказана.
Перейдем к обсуждению способа определения непосредственных доминаторов по полудоминаторам.
Доказательство следующих трех лемм достаточно просто и не приводится. В доказательстве леммы 14.9 используется лемма 14.6.
Лемма 14.8. Для любой вершины
. Лемма 14.9. Для любой вершины хшфв пусть
тогда
. Лемма 14.10. Для любой вершины еафв пусть
тогда
Лемма 14.11. Пусть для вершин v и w выполняется условие
Тогда либо
Доказательство. Пусть х — произвольный собственный потомок
который является собственным предком v. Тогда существует ориентированный путь из s в v, который не включает
Конкатенацией этого пути с путем в Т из v в
мы получим ориентированный путь из s в w, который не включает
. Таким образом,
должен быть либо потомком v, либо предком
Используя приведенные выше леммы, мы докажем два результата, которые предоставляют способ определения непосредственных доминаторов по известным полудоминаторам.
Теорема 14.15. Пусть
Предположим, что для каждого и, такого, что
выполняется неравенство SDOM
Тогда
Доказательство. По лемме 14.10 IDOM
и поэтому, чтобы доказать, что
достаточно показать, что v доминирует над
.
Рассмотрим произвольный ориентированный путь Р из s в w. Пусть
последняя вершина на этом пути, для которой
Если такой вершины не существует, то
доминирует над w. Иначе пусть у — первая вершина, следующая за
по пути и удовлетворяющая условию
Пусть
— часть пути Р от
к у. Тогда по лемме
для
из этого вместе с определением полудоминаторов следует, что SDOM
Поэтому SDOM
По предположению теоремы SDOM
для каждого и, удовлетворяющего условию
. Поэтому у не может быть собственным потоком
Так как у удовлетворяет условию
то
и v входит в путь Р. Из произвольности пути Р следует, что v доминирует над
Теорема 14.16. Пусть
. Пусть и — вершина, для которой
минимальна среди вершин и, удовлетворяющих условию
. Тогда SDOM
Доказательство. Пусть
— вершина, для которой
Тогда SDOM
По лемме
— предок v и, следовательно, собственный предок
. Таким образом, по лемме 14.11 IDOM
. Чтобы доказать, что
достаточно показать, что
доминирует над
Рассмотрим произвольный ориентированный путь Р из s в
Пусть
— последняя вершина в Р, удовлетворяющая условию
Если не существует такой вершины
то IDOM
доминирует над w. Иначе пусть у — первая вершина, следующая за
в Р и удовлетворяющая условию IDOM
Как и в доказательстве теоремы 14.15, мы можем показать, используя лемму 14.7, что
Так как по лемме
то мы имеем
Следовательно,
Так как
— минимальный полудоминатор среди вершин пути в дереве из
в w, то у не может быть и собственным потомком v. Более того, у не может быть ни собственным потомком
ни предком и, поскольку в этом случае ориентированный путь, состоящий из пути в дереве из s в SDOM
с последующим таким путем SDOM
что
для
и следующим затем путем в дереве из у в и не включал бы
Однако пути из s в
не включающего
не существует.
Единственной остающейся возможностью является то, что IDOM
Таким образом,
лежит на ориентированном пути Р из s в w. Так как путь выбран произвольно, то
доминирует над
Следующий результат является непосредственным следствием теорем 14.15 и 14.16.
Теорема 14.17. Пусть
Пусть
— вершина, для которой SDOM является минимальной среди вершин и, удовлетворяющих условию
Тогда
Сейчас мы уже готовы описать алгоритм доминаторов Ленгауэра и Тарьяна. Главными шагами в этом алгоритме являются следующие действия:
Алгоритм 14.9. (Доминаторы Ленгауэра и Тарьяна.)
51. Выполнить ПВГ на данном графе программы
с начальной вершиной в качестве корня.
52. Вычислить полудоминаторы всех вершин, применяя теорему 14.14. Провести вычисления для всех вершин последовательно в порядке увеличения глубин.
S3. Неявно определить непосредственные доминаторы для каждой вершины, применяя теорему 14.17.
S4. Явно выделить непосредственные доминаторы для каждой вершины, проводя вычисления в порядке возрастания глубины вершин.
Реализация шага
тривиальна. В последующем мы будем обозначать вершины их глубинами, полученными на шаге
При описании шагов
мы используем массивы: FATHER (определенный так же, как и в разд. 14.3), SEMI, BUCKET и DOM, определенные ниже.
. 1) До вычисления полудоминатора до имеем SEMI
После вычисления полудоминатора до SEMI
. Это — множество вершин, полудоминатором которых является
.
. 1) Если после шага S3 полудоминатор до есть ее непосредственный доминатор, то
есть непосредственный доминатор до, иначе
есть такая вершина v, что
и непосредственный доминатор v является также непосредственным доминатором до. 2) После шага
есть непосредственный доминатор до. После выполнения шага
алгоритм проходит шаги
одновременно, обрабатывая вершины
в порядке уменьшения их глубин. При этом во время вычисления алгоритм поддерживает лес, содержащийся в дереве ПВГ графа G. Лес состоит из множества вершин V и множества ребер
(до),
до уже
Алгоритм использует процедуры построения леса и выделения из него информации.
Этими процедурами являются LINK
. Добавить ребро
в лес.
EVAL (у). 1) Если v — корень дерева в лесу, то EVAL
равно V. 2) Иначе, пусть
— корень дерева в лесу, которое содержит и, и пусть и — вершина, для которой SEMI
— минимальная среди вершин, удовлетворяющих условию
и, тогда EVAL
Для обработки вершины до алгоритм вычисляет полудоминатор w, применяя для этого теорему 14.14. Таким образом, алгоритм принимает вид SEMI
По завершении вычисления SEMI
есть полудоминатор до. Это следует из теоремы 14.14 и определения
Рассчитав SEMI (до), алгоритм добавляет до в BUCKET (SEMI
) и добавляет новое ребро в лес, используя LINK (FATHER (
). На этом шаг
для до завершается. Затем алгоритм выполняет шаг
рассматривая каждую вершину из BUCKET
Пусть v — такая вершина. Алгоритм неявно определяет непосредственный доминатор v с помощью теоремы 14.17. Пусть
, тогда и есть вершина, для которой выполняется FATHER
полудоминатор которой минимален. Если SEMI
, то FATHER
есть непосредственный доминатор v и алгоритм полагает
Иначе и и w имеют один и тот же непосредственный доминатор и алгоритм полагает
Этим завершается шаг
для
На шаге
алгоритм просматривает вершины в порядке возрастания их глубин, выделяя непосредственные доминаторы, неявно вычисленные на шаге
Таким образом, шаг
включает в себя следующие действия:
Для каждого
, если
Для иллюстрации работы алгоритма доминаторов рассмотрим граф программы, изображенный на рис. 14.22, а. Лес, полученный перед обработкой вершины 11, также изображен на рис. 14.23, а. Элементы массива SEMI на этой стадии указаны в скобках следом за соответствующими вершинами. Рассмотрим вершину 11. Ребра (1, 11) и (7, 11) заходят в вершину И. Поэтому SEMI
так как вершина 1 является корнем дерева в лесу. По той же причине EVAL
Таким образом, SEMI
Алгоритм добавляет ребро (7, 11) в лесу и вершину 11 в BUCKET (SEMI
Новый лес с элементами массива SEMI представлен на рис. 14.23, б. На этом завершается шаг
для вершины 11.
Алгоритм рассматривает BUCKET (FATHER
Вершина 13 является единственной вершиной, полудоминатор которой равен 7. Поэтому BUCKET
так как SEMI (11) является минимальной среди вершин и, для которых выполняется 7 13 (рис. 14.23, б). Так как SEMI
то алгоритм устанавливает
На этом завершается шаг
для вершины 11.
После того как будут выполнены шаги
и S3 для всех вершин
будут доступны и полудоминаторы всех вершин. Значения элементов массива DOM и полудоминаторов представлены выше Для каждой вершины
До сих пор для всех вершин w, кроме
. Для вершины 13 получаем
Поэтому
На этом завершается шаг
алгоритма, и мы получаем дерево доминаторов, представленное на рис. 14.22, б.
Ясно, что сложность приведенного выше алгоритма существенно зависит от реализации инструкции LINK и EVAL. Тарьян [14.44] обсуждает два метода реализации, которые используют сжатие пути. Один из них описывается ниже.
Чтобы представить лес, построенный при выполнении инструкций типа LINK, алгоритм использует два массива: LABEL и ANCESTOR. Вначале ANCESTOR
для каждой вершины V. В общем случае ANCESTOR
только если v — корень дерева в лесу, иначе ANCESTOR
является предком v в лесу.
Алгоритм поддерживает метки так, что они удовлетворяют следующему свойству: пусть v — произвольная вершина,
корень дерева в лесу, содержащем v, и пусть
будут такими, что ANCESTOR
для
Пусть
— вершина, для которой SEMI
— минимальная среди вершин
Тогда справедливо следующее свойство:
— вершина, для которой
— минимальная вершина среди вершин
удовлетворяющих условию
. Чтобы выполнить
алгоритм полагает ANCESTOR
Чтобы выполнить
алгоритм следует за указаниями на предка и определяет такую последовательность
что ANCESTOR
для Если
то алгоритм устанавливает
Иначе алгоритм полагает ANCESTOR
для 20, одновременно изменяя метки следующим образом (чтобы поддерживать упомянутое ранее свойство):
Если SEMI (LABEL)
то
Затем алгоритм устанавливает EVAL
Тарьян [14.44] показал, что сложность реализации
инструкций LINK и
инструкций EVAL с помощью описанного ранее метода равна
logn). Если мы используем более изощренную реализацию инструкций LINK и EVAL, которая также описана в работе [14.44], то алгоритм потребовал бы для своей реализации
шагов, где
— обращение функции Аккермана, определенное в предыдущем разделе.
Другие алгоритмы доминаторов представлены в работах [14.45, 14.46].