Анализ потока управления

Анализ потока управления

В задачу анализа потока управления (control flow analysis) входит определение свойств передачи управления между операторами программы. Проверка многих свойств этого вида необходима для решения задач оптимизации, преобразований программ и т.д.

При решении этих задач обычно используется формальная графовая модель (т.е. анализ производится над графом потока управления), а сами задачи формулируются в теоретико-графовой форме.

Основное употребление анализа потока управления в оптимизации - это фрагментация, то есть представление графа потока управления в виде совокупности фрагментов определенного вида. Как было показано в лекции 11, такое представление необходимо для применения практически всех оптимизирующих преобразований.

Ниже будут рассмотрены основные понятия в области анализа потока управления, приведены определения некоторых фрагментов и алгоритмы их распознавания.

Граф потока управления

Основным способом представления потока управления программы является граф потока управления (см. лекции 11) - ориентированный граф с двумя выделенными вершинами start и stop , такими, что

Для произвольной дуги e обозначим через beg(e) ее начало, а через end(e) - ее конец.

Для произвольной вершины v обозначим через in(v) множество входящих в нее дуг, а через out(v) - множество исходящих дуг.

Путем в графе назовем последовательность вершин, такую, что между каждой последующей и предыдущей вершиной в графе существует ребро.

Обязательное предшествование

Вершина v обязательно предшествует вершине w , если v принадлежит каждому пути в графе от start до w . В частности, любая вершина обязательно предшествует себе самой. Отношение обязательного предшествования будем обозначать символом ' < '. Легко видеть, что это отношение рефлексивно и транзитивно, но не симметрично. Таким образом, отношение обязательного предшествования задает частичный порядок на множестве вершин графа.

Вершина v строго обязательно предшествует вершине w , если она обязательно ей предшествует, но не совпадает с ней. Отношение строгого обязательного предшествования будем обозначать символом sdom .

Вершина v непосредственно предшествует вершине w , если она является ближайшей к w вершиной, которая ей строго предшествует.

Можно показать, что множество строгих обязательных предшественников для данной вершины линейно упорядочено, а непосредственный предшественник - это максимальный элемент в этом множестве. Таким образом, отношение непосредственного предшествования - это дерево. Легко показать, что корнем этого дерева является start .

Дуга (v, w) называется обратной в том и только том случае, когда w<v .

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

Пример

На слайде приведен пример графа потока управления и соответствующего ему дерева непосредственного предшествования. Дуга (g, f) является обратной.

Глубинное остовное дерево

Нумерацией называется взаимно однозначное отображение множества вершин графа на отрезок натурального ряда [1..|V|]. Для заданной нумерации # дуга (v, w) - прямая, если #(v)<#(w) и обратная в противном случае.

Остовное дерево - это дерево, содержащее все вершины графа и некоторые его дуги. Глубинное остовное дерево - это остовное дерево, полученное при обходе в глубину. Данный обход начинается в вершине start и заключается в последовательном включении вершин и ребер графа в дерево, если их еще там нет. При этом следующий сын вершины посещается лишь тогда, когда посещены все вершины, достижимые из предыдущего сына вершины.

Существует четыре типа дуг графа по отношению к данному глубинному остовному дереву: деревянные, прямые, обратные и поперечные. Следует отличать просто обратные дуги в графе (для определения которых было использовано отношение обязательного предшествования) и обратные дуги по отношению к глубинному остовному дереву.

Легко видеть, что при построении остовного дерева возникает порядок, в котором вершины графа включаются в рассмотрение. Нумерация, которая описывает этот порядок, называется прямой ( Pre ).

Аналогично, существует порядок, в котором вершины графа исключаются из рассмотрения. Нумерация, описывающая порядок, обратный к нему, называется обратной ( Post ).

Построение глубинного остовного дерева

На слайде приведен алгоритм построения остовного дерева, определения типов дуг графа по отношению к нему и построения нумераций Pre и Post .

Алгоритм обходит вершины графа, начиная со start . При входе в очередную вершину ей присваивается очередной номер нумерации Pre , при этом номера Pre присваиваются в порядке возрастания. Далее рассматриваются все потомки этой вершины, которые еще не рассматривались. К каждому потомку применяется этот же самый шаг алгоритма - таким образом, обеспечивается обход в глубину. Наконец, после рассмотрения всех потомков текущей вершины ей присваивается очередной номер нумерации Post . При этом номера Post присваиваются в порядке убывания.

По ходу работы алгоритма поддерживается три состояния вершин:

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

Пример

На слайде приведен пример графа потока управления и одного из его глубинных остовных деревьев. Каждая вершина помечена парой номеров, первый из которых соответствует нумерации Pre, а второй - нумерации Post . Деревянные дуги показаны толстыми линиями, прямые - тонкими, пунктирными линиями показаны обратные дуги и штрих-пунктирной - единственная поперечная дуга.

Граф, полученный удалением обратных по отношению к остовному дереву дуг, называется каркасом (показан в правой части слайда). Можно показать, что каркас графа при произвольном глубинном остовном дереве не содержит контуров.

Простейшие свойства

Граф называется сводимым тогда и только тогда, когда множество обратных дуг совпадает с множеством обратных дуг относительно глубинного остовного дерева для любого такого дерева.

Простейшие свойства нумераций Pre и Post:

Сводимость является одной из основных характеристик графов потока управления. Как видно из определения, в сводимом графе обратные дуги для произвольного остовного дерева совпадают с обратными дугами относительно обязательного предшествования. Учитывая, что каждая обратная дуга определяет в графе потока управления контур (т.е. является абстракцией циклических конструкций языков программирования), циклическая структура сводимого графа является более регулярной, что упрощает анализ его свойств.

Фрагменты

Фрагментом называется произвольный подграф графа управления (под подграфом мы понимаем некоторое непустое подмножество вершин графа, содержащее все ребра графа между ними).

Для фрагмента F определяются четыре множества вершин:

Схематически соотношения между фрагментом и этими его множествами вершин показаны на слайде.

Фрагменты графа потока управления являются абстракциями конструкций управления языков программирования. Известно, что практически все языки программирования определяют сходный набор конструкций управления. Следовательно, перейдя от анализа конкретных конструкций к их обобщениям, можно разработать способы анализа свойств программ независимо от входных языков.

Далее мы рассмотрим некоторые виды фрагментов.

Альт

Альтом называется фрагмент, имеющий одну начальную вершину. Пример альтов показан на рисунке на слайде (дуги, принадлежащие альтам, выделены жирными линиями).

Легко могут быть доказаны следующие простейшие свойства альтов:

Выделение максимального альта

Приведем алгоритм выделения максимального альта, для которого данная вершина p является начальной.

Алгоритм состоит из трех шагов:

Можно показать, что в конце работы алгоритма множество "серых" вершин и будет максимальным альтом, начинающимся в вершине p .

Пример работы алгоритма показан на слайде. Крайний левый граф - это граф после первого шага. Средний рисунок изображает граф после того, как все вершины, достижимые из p , покрашены в "серый" цвет. Здесь же стрелочкой обозначена вершина, имеющая своим предком "черную" вершину. Окончательный альт показан на крайнем правом рисунке.

Построение отношения обязательного предшествования

Свойства альтов дают возможность использовать их для определения отношения обязательного предшествования. Для этого достаточно для каждой вершины построить максимальный альт, начинающийся в ней, и затем включить эту вершину во множество обязательных предшественников для каждой вершины из этого альта.

После построения отношения обязательного предшествования сводимость графа может быть проверена элементарно - достаточно построить глубинное остовное дерево и проверить, что в любой обратной по отношению к нему дуге конец обязательно предшествует началу.

Луч

Лучом называется фрагмент, который, во-первых, является альтом, а во-вторых, обладает тем свойством, что произвольная его вершина, отличная от начальной и выходной, имеет одного предка и одного потомка, каждый из которых принадлежит лучу. Иными словами, луч - это линейная последовательность вершин.

Легко видеть, что в состав лучей могут входить только деревянные дуги.

Нумерация # называется правильной, если она приписывает вершинам произвольного луча последовательные номера.

Если # - правильная нумерация, а R - максимальный луч, то можно доказать следующие утверждения:

Легко показать, что нумерации Pre и Post являются правильными.

Выделение лучей

Алгоритм выделения максимальных лучей использует свойства правильных нумераций и элементарное наблюдение, что вершина v является начальной вершиной максимального луча в том случае, если в нее входит более одного ребра, и выходной - если выходит более одного ребра.

Результатом работы алгоритма является два списка Starts и Ends , первый из которых содержит начальные вершины максимальных лучей, а второй - выходные.

Очевидно, что одна вершина является лучом. Таким образом, множество максимальных лучей образует разбиение множества вершин графа. На иллюстрации показано это разбиение.

Сильно связный подграф

Сильно связный подграф - это фрагмент, состоящий из взаимно достижимых вершин. Компонента сильной связности - это максимальный сильно связный подграф.

Очевидно, произвольная вершина является сильно связным подграфом. Кроме того, легко показать, что множество компонент сильной связности задает разбиение множества вершин. Это разбиение показано на слайде.

Наконец, множества входных и начальных вершин для компонент сильной связности совпадают.

Как было показано в лекции 11, выделение сильно связных подграфов имеет определяющее значение для реализации чистки циклов.

Выделение сильно связных подграфов (1)

Для выделения сильно связных подграфов введем понятие области при нумерации #, а именно, областью вершины v при нумерации # назовем множество вершин с большими номерами, из которых v достижима в подграфе, состоящем из всех вершин с большими номерами.

Можно показать, что область произвольной вершины при нумерации Post сильно связна.

Выделение сильно связных подграфов (2)

Для выделения сильно связных подграфов, таким образом, достаточно научиться выделять области. Заметим, однако, что, несмотря на то, что области при нумерации Post сильно связны, это не означает, что произвольные сильно связные подграфы будут областями при нумерации Post .

Алгоритм построения области приведен на слайде. Видно, что он осуществляет движение от текущей вершины по встречным дугам, проходя только по вершинам, имеющим большие номера, чем данная, и включает их в область.

Примеры подграфов, выделенных с помощью алгоритма, приведены на иллюстрации. Стрелочками отмечены вершины, области которых выделены.

Выделение компонент сильной связности (1)

Можно показать, что компонента сильной связности является областью своей вершины, имеющей минимальный номер в нумерации Post среди всех остальных вершин этой компоненты. Такая вершина называется бивершиной.

Для выделения компонент сильной связности построим нумерацию T , такую, что для би-вершин порядок, задаваемый T -номерами, совпадает с порядком, задаваемым Post -номерами, а все компоненты сильной связности заполнены T -номерами последовательно.

Выделение сильно связных подграфов (2)

Алгоритм построения T -нумерации обходит граф в порядке возрастания Post -номеров вершин. При этом каждая вершина может находиться в двух состояниях: обработанная или необработанная. Первоначально все вершины находятся в необработанном состоянии.

Обнаружив необработанную вершину, алгоритм присваивает ей очередной номер, выделяет ее область и присваивает вершинам области очередные номера.

На рисунке на слайде показан граф с его T -нумерацией.

Иерархия вложенных зон

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

Иерархией вложенных зон называется совокупность сильно связных подграфов S , два любых из которых либо не пересекаются, либо один из них содержит другой, такая, что для произвольного сильно связного подграфа Z найдется содержащий его элемент S , который имеет с Z общую входную вершину.

Может быть показано, что набор областей всех вершин при нумерации Post является иерархией вложенных зон.

Иерархия вложенных зон - это один из способов описать циклическую структуру программы. Несмотря на то, что эта иерархия, вообще говоря, не содержит всех циклов программы, она тем не менее дает возможность рассмотреть некоторое приближение множества всех циклов.

Линейные компоненты

Линейной компонентой называется фрагмент L , обладающий следующими пятью свойствами:

Множество всех линейных компонент образует разбиение множества вершин графа. Стягивание линейных компонент переводит граф в луч.

Можно также показать, что начальная вершина линейной компоненты есть либо start, либо конечная вершина другой линейной компоненты. Наконец, можно показать, что начальная вершина произвольной линейной компоненты является бивершиной.

Выделение линейных компонент в исходном графе позволяет применять к нему оптимизирующие преобразования, рассчитанные на линейный участок.

Выделение линейных компонент в сводимом графе

Идея алгоритм выделения линейных компонент в сводимом графе опирается на использование свойств, сформулированных выше.

Алгоритм обходит граф в порядке возрастания T -номеров и добавляет вершины в текущую линейную компоненту. Признаком завершения линейной компоненты является то, что вершина со следующим номером является, во-первых, бивершиной, а во-вторых, ее номер - максимальный среди номеров всех потомков вершин текущей линейной компоненты.

Разбиение графа на линейные компоненты изображено на рисунке на слайде.

Литература к лекции