11 / 17
x
→
в ЦП не могут иметь дублей в графе в силу построения, по-
скольку такая вершина добавляется для каждой вершины
x
i
∈
X
S
,
записывающей некоторое новое значение в вершину
y
j
∈
Y
\
Y
S
.
Шаг 14. Для каждой вершины
x
i
∈
X
S
,
если
y
j
∈
F
−
1
2
x
i
,
y
j
∈
Y
\
Y
S
и
∃
x
k
∈
F
−
1
3
y
j
,
x
k
/
∈
X
S
, k < i
, то
X
←
X
∪ {
x
←
}
. При этом
F
1
x
i
−
1
←
F
1
x
i
−
1
∪ {
x
←
}
,
F
−
1
1
x
i
←
F
−
1
1
x
i
∪ {
x
←
}
и
F
2
x
←
←
y
j
, т.е. в
данном действии происходит вставка в граф
G
(2)
A
вершины-оператора
получения данных примитивного типа от ЦП.
Шаг 15. У любой вершины
∀
x
i
∈
X
C
, являющейся объединенным
блоком вычисления условия и ветвления, заменяем вершину ветвления
потоков управления, если
x
i
∈
X
?
Λ
, то
x
i
←
x
Λi
.
Шаг 16. Для каждой вершины ветвления потоков управления
x
i
∈
X
Λ
добавляем новую вершину-оператор получения данных от ЦП
x
←
:
X
←
X
∪{
x
←
}
,
F
1
x
i
−
1
←
F
1
x
i
−
1
∪{
x
←
}
,
F
−
1
1
x
i
←
F
−
1
1
x
i
∪{
x
←
}
.
В граф добавляем вершину данных примитивного типа, хранящую
информацию о результате вычисления условия ЦП в вершине тега
x
i
Y
←
Y
∪ {
y
tg
}
,
F
−
1
2
x
i
=
y
tg
.
Шаг 17. Проводится замена используемых вершинами-операторами
обработки структур данных вершин-данных примитивных типов вер-
шинами временн ´ых данных примитивного типа, т.е.
∀
y
i
/
∈
Y
S
:
x
j
∈
∈
F
3
y
i
, x
j
∈
X
S
заменяем вершину
y
i
вершиной временн ´ых данных,
сохраняя все дуги:
y
i
←
y
t
i
.
Шаг 18. Осуществляется исключение дублирующих передач дан-
ных СП. Для любой пары вершин-операторов обработки структур
x
i
и
x
j
, таких, что
∃
y
k
∈
Y
:
y
k
∈
F
−
1
2
x
i
, y
k
∈
F
−
1
2
x
j
,
y
k
/
∈
Y
S
и между
ними в графе не присутствует других вершин-операторов обработ-
ки структур, использующих
y
k
(т.е.
x
i
+1
, . . . x
j
−
1
/
∈
F
3
y
k
), проверяем
наличие вершин, записывающих новое значение в вершину
y
k
. Если
таких вершин нет, т.е.
F
−
1
3
y
k
6
⊂ {
x
i
+1
, . . . x
j
−
1
}
, то передача данных
СП для вершины
x
j
может быть исключена из графа
G
(2)
A
как дубли-
рующаяся, следовательно,
X
←
X
\
x
←
для
x
←
:
x
j
∈
F
1
x
←
. Проводим
“сшивание”
F
1
x
j
−
2
←
F
1
x
j
−
2
∪ {
x
j
}
, F
−
1
1
x
j
←
F
−
1
1
x
j
∪ {
x
j
−
2
}
.
Шаг 19. Из множества
X
удаляются все вершины-операторы,
не являющиеся операторами обработки структур, передачи, а также
терминальными или операторами ветвления, т.е.
X
←
X
\
X
p
, если
x
i
∈
X
p
, то
F
1
x
i
−
1
←
F
1
x
i
−
1
∪
x
i
+1
,
F
−
1
1
x
i
+1
←
F
−
1
1
x
i
+1
∪
x
i
−
1
.
Шаг 20. Из множества
Y
удаляются все вершины, у которых от-
сутствуют инцидентные им дуги и которые не инцидентны никаким
дугам:
Y
←
Y
\ {
y
i
}
:
F
3
y
i
=
∅
, F
−
1
3
y
i
=
∅
,
i
= 1 :
|
Y
|
.
Шаг 21. Осуществляется перенумерация вершин в множестве
X
по порядку, так что обозначение каждой вершины приобретает вид
x
S
↔
i
, а само множество
X
переходит в множество
X
S
↔
.
122 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1