Построение срезов для программ на динамических языках
11
Построение дерева пост-доминаторов для ГПУ сводится к по-
строению дерева доминаторов для обратного ГПУ, в котором дуга
a
→
b
означает, что блок
a
непосредственно следует за блоком
b
.
В свою очередь, алгоритмы построения дерева доминаторов широко
известны и описаны, в частности в работе [9].
Граф зависимостей по управлению (
N
c
,
E
c
), составленный из ли-
нейных блоков (непрерывных участков программы, начинающихся
меткой перехода, заканчивающихся оператором условного перехода
либо безусловным переходом к вершине
End
и не содержащих иных
меток перехода или операторов перехода), можно «развернуть» в
граф (
N
co
,
E
co
) составленный из операторов. Пусть
Ops
(
v
),
v
∈
N
c
—
множество операторов, из которых состоит линейный блок
v
, а
CondJump
(
v
)
∈
Ops
(
v
) — оператор условного перехода, которым за-
канчивается
v
. Тогда
N
co
= ∩
v
∈
Nc
Ops
(
v
); (
o
1
,
o
2
)
∈
E
co
⇔ ∃
(
v
1
,
v
2
)
∈
E
c
:
(
o
1
∈
Ops
(
v
1
) ˄
o
2
=
CondJump
(
v
2
)).
Если поток управления является структурированным, каждая
вершина ГЗУ
v
1
будет зависеть по управлению ровно от одной дру-
гой вершины
v
2
; то же самое верно для ГЗУ, составленного из опера-
торов.
В случае наличия операторов локального перехода, таких как
break или continue, потребуется формировать ГПУ особым образом,
описанным в работе [10]. Каждый из этих операторов представляется
как оператор условного перехода, условие в котором всегда истинно,
и две исходящие из этого оператора дуги — одна в место перехода
(начало или конец цикла), вторая — к следующему оператору, как
будто вместо break или continue присутствует no-op.
Располагая операторным ГЗУ (
N
co
,
E
co
), можно добавлять его ду-
ги в ГПЗ в виде дуг зависимостей по управлению, но только тогда,
когда обе вершины-оператора, соединяемые дугой, уже присутству-
ют в ГПЗ (т. е. были выполнены), поскольку мы отслеживаем дина-
мические зависимости по управлению.
Опишем действия при добавлении нового оператора
o_new
в
ГПЗ. В следующем псевдокоде
succ
и
pred
— множества непосред-
ственных предшественников и потомков вершины в графе (
N
co
,
E
co
), а
функция
add_edge
добавляет в ГПЗ дугу зависимости по управлению,
если такой дуги еще нет в ГПЗ.
for o2 in pred(o_new):
add_edge(o2, o_new);
for o2 in succ(o_new):
add_edge(o_new, o_2);
Использование одних и те же вершин и дуг, представляющих за-
висимости внутри процедуры, для различных ее вызовов приводит к
появлению ложных зависимостей между разными местами вызовов.
