Теория языков программирования методов трансляции (стр. 32 )

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

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

6.4.1.  Интервалы

Определение. Если h – вершина графа управления F, определим интервал I(h) с заголовком h как такое множество вершин графа F, что

1)  h принадлежит I(h),

2)  если вершина n, еще не включена в I(h) и все дуги входящие в n, выходят из вершин, принадлежащих I(h), добавим n к I(h),

3)  Повторяем шаг 2) до тех пор, пока не останется вершин, которые можно добавить к I(h).

Пример. Рассмотрим граф управления, изображенный на рис. 11.25.

Рис. 11.25. Граф управления.

Рассмотрим интервал с начальной вершиной n1, в качестве заголовка. Согласно шагу 1) I(n1) включает n1. Поскольку единственная дуга, входящая в n2 выходит из n1 добавим n2 к I(n1), вершину n3 нельзя добавить к I(n1), так как в нее можно попасть не только из n2, но и из n5. Никаких других вершин к I(n1) добавить нельзя. Таким образом, I(n1) = {n1, n2} Продолжая разбор, получим: I(n1) = {n1, n2} I(n3) = {n3} I(n4) = {n4, n5, n6} I(n7) = {n7, n8, n9} Остается проблема нахождения заголовков. Теорема. 1)  Заголовок h доминирует над всеми остальными вершинами в I(h), хотя не обязательно все вершины над которыми он доминирует принадлежат I(h). 2)  Для каждой вершины h графа управления F интервал I(h) определяется однозначно и не зависит от порядка, в котором на шаге 2) определения интервала выбираются кандидаты для n.

3)  Каждый цикл в интервале I(h) включает заголовок интервала h

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

Алгоритм разбиения графа управления на непересекающиеся интервалы.

Вход. Граф управления F.

Выход. Множество непересекающихся интервалов, объединение которых содержит все вершины графа F.

Метод.

1)  С каждой вершиной в F свяжем два параметра: счетчик и достижимость. Счетчик для n сначала равен числу дуг входящих в n. В ходе выполнения алгоритма счетчик для n равен числу еще не пройденных дуг, входящих в n. Достижимость для n либо не определена, либо является некоторой вершиной из F. Вначале достижимость не определена для всех вершин, кроме начальной, достижимость которой есть она сама. В конечном итоге достижимостью для n станет первый найденный заголовок интервала n, такой, что из некоторой вершины интервала I(n) ведет дуга в n.

2)  Образуем список вершин, называемым списком заголовков. Вначале список заголовков содержит только начальную вершину графа F.

3)  Если список заголовков пуст, остановиться. В противном случае n – следующая вершина из списка заголовков.

4)  Затем применяем шаги 5)- 7) для построения интервала I(n). На этих шагах к списку заголовков добавляются прямые потомки вершины из I(n).

5)  I(n) строим как список вершин. Вначале I(n) содержит только вершину n и она «не помечена».

6)  Выбираем в I(n) «непомеченную вершину» n¢, помечаем ее и для каждой вершины n², в которую ведет дуга из n¢, выполняем следующие операции:

(а) Уменьшаем счетчик на 1 для n²

(б) (i) Если достижимость для n² не определена, полагаем ее равной n и делаем следующее. Если счетчик для n² равен 0 (перед этим был 1) то добавляем вершину n²’ к I(n) и переходим к шагу 7); иначе добавляем вершину n¢ к списку заголовков, если ее там не было, и переходим к шагу 7).

(ii) Если достижимость для n² равна n, а счетчик вершин n² равен 0, добавляем вершину n² к I(n) и удаляем ее из списка заголовков, если она там есть и переходим к шагу 7.

Если ни 1) ни 2) не применимы, в б) ничего не делаем.

7)  Если в I(n) остается непомеченная вершина, возвращаемся к шагу 6). Иначе список I(n) заполнен, возвращаемся к шагу 3).

Определение. Из интервалов графа управления F, можно построить другой граф управления I(F), который будем называть производным графом от F. Произвольный граф определяется так:

1)  I(F) имеет по одной вершине для каждого интервала, построенного ниже описанным алгоритмом

2)  Начальной вершиной I(F) служит интервал, содержащей начальную вершину для F.

3)  Из интервала I в интервал J ведет дуга тогда и только тогда, когда I ¹ J и из вершины I ведет дуга в заголовок интервала J.

Произвольный граф I(F) графа управления F показывает поток управления между интервалами в F. Поскольку граф I(F) сам является графом управления можно построить также граф I(I(F)) производный от I(F). Таким образом, если дан граф управления F0, можно построить последовательность графов управления F0, F1,..., Fn, называемую производной последовательностью от F, в которой Fi+1 производный граф от Fi. Граф Fi – называется i – производным графом от F0. Граф Fn – называется пределом графа F0. Нетрудно показать, что Fn всегда существует и единственен.

Если Fn состоит из одной вершины, то граф F0 называется сводимым.

Следует отметить, что если граф F0 строится по реальной программе, то он всегда сводимый.

Пример. Применим рассмотренный алгоритм для построения интервалов управления для граф рис. 11.26.

Рис. 11.26. Граф управления.

Начальной вершиной служит n1. Вначале список заголовков содержит только n1. Для построения I(n1) включаем n1 в I(n1) как непомеченную вершину. Помечаем вершину n1 ее прямым потомком n2. Для этого уменьшаем счетчик n2 с 2 до 1, полагаем достижимость до нее n1 и добавляем ее к списку заголовков. К этому моменту I(n1) не остается непомеченных вершин, так что список I(n1) = {n1} заполнен.

Список заголовков содержит потомка n2 вершины из I(n1). Для вычисления I(n2) включаем n2 в I(n2) и рассматриваем вершину n3, счетчик для которой равен 2. Уменьшаем счетчик на 1, полагаем достижимость для нее равной n2 и добавляем ее к списку заголовков. Находим таким образом, что I(n2) = {n2}.

Список заголовков содержит теперь потомка n3 из I(n2). Вычисление I(n3) начинаем теперь с занесения n3 в I(n3). Рассматриваем теперь вершины n4 и n5, уменьшая счетчик для них 1 до 0, полагая достижимость для них равной n3 и добавляя их к I(n3) как непомеченные вершины. Помечаем n4, уменьшая счетчик для n6 с 2 до 1, полагая достижимость для n6 равной n3 и добавляя n6 к списку заголовков. Помечая n5 в I(n3), уменьшаем счетчик для n6 с 1 до 0, удаляем ее из списка и добавляем к I(n3).

Чтобы пометить n6 в I(n3) делаем счетчик для n7 равным 0, полагаем достижимость для нее равной n3 и добавляем ее к I(n3). Следующей рассматривается вершина n3, поскольку есть дуга из n6 в n3. Так как достижимость для n3 равна n2, вершина n3 в данный момент не изменяет I(n3) и списка заголовков. Чтобы пометить n7, делаем счетчик n8 равным 0, полагаем достижимость для нее равной n3 и добавляем ее к I(n3). Вершина n2 также является потомком вершины n7, но так как достижимость для n2 равна n1, то n2 не добавляется ни к I(n3) ни к списку заголовков.