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.6 легко выводится из положений, ведущих к теореме 14.7. Лемму 14.7 можно доказать с помощью этих же положений.

Лемма 14.6. Если v к да — вершины графа G, для которых верно, что то любой ориентированный путь из должен содержать общего предка вершин v и да в Т.

Лемма 14.7. Пусть и Р — ориентированный путь из s в да. Пусть — последняявершина Р, для которой и пусть у — первая вершина, следующая за и удовлетворяющая условиям: Если — часть пути из в у, то для

Определим для каждой вершины существует такой ориентированный путь что для будем называть полудоминатором w. Из определения следует, что

На рис. 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

(см. скан)

Рис. 14.23.

полудоминатор которой минимален. Если 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].