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

Наконец чтобы пометить n8, не надо производить никаких операций, поскольку n8 не имеет потомков. К этому моменту в I(n3) не остается непомеченных вершин, так что I(n3) = {n3, n4, n5, n6, n7, n8}.

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

I(n1) = {n1}

I(n2) = {n2}

I(n3) = {n3, n4, n5, n6, n7, n8}.

На этих интервалах можно построить последовательность графов управления (рис. 11.27).

Рис. 11.27. Последовательность графов управления.

Пример. Рассмотрим граф рис. 11.28.

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

Интервалы для него таковы:

I(n1) = {n1}

I(n2) = {n2}

I(n3) = {n3}

В соответствие с рассмотренным алгоритмом, находим, что граф F несводим.

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

6.4.2.  Анализ потоков данных с помощью интервалов

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

Будем исходить из априорного утверждения, что анализ потоков данных с помощью интервалов связан с трактовкой графов как упакованных векторных битов. Для вычисления пересечения, объединения и дополнения множеств используются логические операции AND, OR и NOT на векторах битов.

Построим таблицы, дающие для каждого участка ℬ программы все позиции l, где определяется данная переменная A и откуда существует путь в ℬ, вдоль которого A не переопределяется. Эта информация необходима для вычисления возможных значений A при входе в участок ℬ.

Определим четыре функции, отображающие участки во множества.

Определение. Путем вычислений из оператора s1 в оператор s2 назовем последовательность операторов, начинающуюся в s1 и заканчивающуюся в s2, которая в данном порядке может выполняться в процессе выполнения программы.

Пусть ℬ участок программы P. Определим четыре множества, связанные с операторами определения:

1)  IN(ℬ) = {d Î P ½ существует такой путь вычисления из оператора определения d в первый оператор в ℬ, что никакой оператор на этом пути, кроме может быть первого оператора в ℬ, не переопределяет переменную, определенную в d}.

2)  OUT(ℬ) = {d Î P ½ существует такой путь вычисления из d в последний оператор ℬ, что никакой оператор на нем не переопределяет переменную, определенную в d}.

3)  TRANS(ℬ) = {d Î P ½ переменная, определенная в d, не определяется никаким оператором в ℬ}.

4)  GEN(ℬ) = {d Î P ½ переменная, определенная в d, не определяется никаким оператором в ℬ}.

Таким образом, IN(ℬ) содержит определения, которые могут быть активными при входе в ℬ, OUT(ℬ) содержит определения, которые могут быть активными при выходе из ℬ, TRANS(ℬ) содержит определения, передаваемые через ℬ без определения в ℬ, GEN(ℬ) содержит определения, создаваемые в ℬ, которые остаются активными при выходе из ℬ.

Легко видеть, что

OUT(ℬ) = (IN(ℬ) Ç TRANS(ℬ)) È GEN(ℬ).

Пример. Рассмотрим программу

S1: I 1

S2: J 0

S3: J J + 1

S4: read I

S5: if I < 100 goto S8

S6: write J

S7: halt

S8: I I*I

S9: goto S3

Граф программы изображен на рис. 11.29.

Определим для ℬ2 множества IN, OUT, TRANS и GEN. Оператор S1 определяет I, а S1, S2, S3 – путь вычислений, на котором I не определяется (кроме как в S1). Поскольку этот путь ведет из S1 в первый оператор участка ℬ2, ясно, что S1 Î IN(ℬ2). Аналогично можно показать, что

IN(ℬ3) = {S1, S2, S3, S8}

Отметим, что S4 не принадлежит IN(ℬ2), поскольку нет пути вычисления из S4 в S3 не переопределяющего I после S4.

OUT(ℬ2) не содержит S1, поскольку все пути вычисления из S1 в S5 переопределяют I. Далее легко проверить, что

OUT(ℬ2) = { S3, S4}

TRANS(ℬ2) = Æ

GEN(ℬ2) = { S3, S4}

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

Предположим, что ℬ1, …., ℬk – все прямые потомки участка ℬ в P. Ясно, что

IN(ℬ) = OUT(ℬi) = [(IN(ℬi) Ç TRANS(ℬi)) È GEN(ℬi)].

Для вычисления IN(ℬ) можно было бы выписать это уравнение для каждого участка программы вместе с уравнением IN(ℬ0) = Æ, где ℬ0 - начальный участок, затем попытаться разрешить систему уравнений. Однако существует более удобный метод, учитывающий преимущества представления графов управления в виде интервалов.

Дадим вначале определения понятий «вход» и «выход» интервала.

Определение. Пусть P – программа, а F0 ее граф управления. Пусть F0, F1,…, Fn – производная последовательность от F0. Каждая вершина в Fi, i ³ 1, является интервалом в Fi-1 и называется интервалом порядка i.

Входом интервала порядка 1 служит заголовок интервала. Вход интервала порядка i > 1 – это вход в заголовок интервала. Таким образом, вход любого интервала – это линейный участок исходной программы P.

Выходом интервала I(n) порядка 1 служит такой последний оператор участка ℬ в I(n), что ℬ имеет прямого потомка, который является либо заголовком интервала n, либо участком вне I(n). Выход интервала I(n) порядка i ³ 1 – это последний оператор участка ℬ, содержащегося в I(n) и такого, что в F0 есть дуга, ведущая из ℬ либо в заголовок интервала n, либо в участок вне I(n).

Отметим, что каждый участок имеет один вход и ноль или более выходов.

Пример. Пусть F0 – граф управления программы рис. 11.29. С помощью алгоритма разбиения графа на непересекающиеся интервалы, построим его разбиение на интервалы

I1 = I(ℬ1) ={ℬ1}

I2 = I(ℬ2) = {ℬ2, ℬ3, ℬ4}

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

I3 = I(I1) = { I1, I2} = {ℬ1, ℬ2, ℬ3, ℬ4}

и получить предельный граф управления, также показанный на рис. 11.30.

Рис. 11.30. Производная последовательность от графа F0.

Интервалами порядка 1 являются I1 и I2. Вход для I2 – это ℬ2. Вход для I3 – это ℬ1. Единственный выход для I1 – это оператор S2. Единственный выход для I2 – это оператор S9. Интервалом порядка 2 является I3 с входом ℬ1. Интервал I3 не имеет выходов.

Продолжим теперь функции IN, OUT, TRANS и GEN на интервалы. Пусть F0, F1,…, Fn - производная последовательность от F0, где F – граф управления для P, а I – интервал некоторого графа Fi, i ³ 1. Введем следующие основные определения:

ì IN(ℬ), если I имеет порядок 1, а ℬ - заголовок для I,

1)  IN(I) = í

îIN(I¢), если I имеет порядок i > 1, а I¢ заголовок для I.

В 2) – 4) ниже s – вход для I.

2)  OUT(I, s) = OUT(ℬ), где участок ℬ Î I таков, что s – его последний оператор.

3)  (а) TRANS(ℬ, s) = TRANS(ℬ), если s – последний оператор в ℬ.

(б) TRANS(I, s) – множество таких операторов d Î P, что существует путь без циклов I1, I2,…, Ik, состоящих исключительно из вершин в I, и такая последовательность выходов s1, s2, …, sk для I1, I2,…, Ik, соответственно, что

(i)  I1 – заголовок для I,

(ii)  в F0 участок sj является прямым предком входа для Ij+1 при 1 £ j < k,

(iii)  d Î TRANS(Ij, sj) при 1 £ j £ k,

(iv)  sk = s.

Эти условия иллюстрированы на рис. 11.31.