А.О. Крючков, В.А. Крищенко
10
o1, o2 := извлечь_поля_JUMPSTO(record);
N := union( N, {o1, o2} );
E := union( E, {(o1, o2)} );
Start := найти_вершину_графа_без_предшественников(N, E);
/* вершина End уже явно присутствует во множестве N */
ГПУ := (N, E, Start, End);
По восстановленному ГПУ составляется граф зависимостей по
управлению (ГЗУ), вершинами которого являются операторы, а дуги
v
1
→
v
2
означают «оператор
v
1
зависит от
v
2
по управлению». При
построении статического среза ГЗУ стал бы подграфом ГПЗ; так как
мы строим динамический срез, только часть дуг ГЗУ будет перене-
сена в ГПЗ.
Ниже приводится алгоритм построения графа зависимостей по
управлению (
N
c
,
E
c
) на основе графа потока управления (
N
,
E
,
Start
∈
N
,
End
∈
N
). Алгоритм основан на работе [6], в которой рассматрива-
ется построение более общего вида ГЗУ.
1. Дополнить ГПУ мнимой вершиной
Entry
и дугами
Entry
→
Start
,
Entry
→
End
.
2. Построить дерево пост-доминаторов (
N
,
E
d
) (ДПД) по допол-
ненному ГПУ.
3. Положить
S
⊆
E
: (
a
,
b
)
∈
S
⇔
b
не является пост-доминатором
a
.
4. Инициализировать ГЗУ (
N
c
,
E
c
):
N
c
=
N
\{
End
},
E
c
=
∅
.
5. Повторять следующие шаги для каждой дуги (
a
,
b
)
∈
S
:
а) найти
L
=
L
(
a
,
b
) — ближайшего общего предка
a
и
b
в ДПД;
б) если
L
(
a
,
b
) =
a
, примем
v
0
=
a
; иначе
v
0
=
L
. Найдем в ДПД
путь
p
из
v
0
в
b
.
в) все вершины в этом пути, исключая
v
0
, зависят по управлению
от
a
, что следует отразить добавлением дуг в граф зависимостей по
управлению (
N
c
,
E
c
): (
v
,
a
)
∈
E
c
∀
v
∈
p
\{
v
0
}.
Результаты выполнения шагов этого алгоритма для конкретного
ГПУ показаны на рис. 6 (вершина Start в ГПУ совпадает с вершиной 1).
Рис. 6.
Результаты выполнения шагов алгоритма получения графа
зависимостей по управлению
