10 / 17
Шаг 5. Для любого
∀
x
i
∈
X
C
добавляем новую вершину данных
примитивного типа, хранящую информацию о результате вычисления
условия в вершине тега
x
i
:
Y
←
Y
∪ {
y
tg
}
,
F
2
x
i
=
y
tg
. Добавля-
ем в граф
G
(1)
A
вершины-операторы передачи информации о теге СП:
X
←
X
∪ {
x
истина
→
, x
ложь
→
}
,
F
1
x
i
← {
x
истина
→
, x
ложь
→
}
,
F
−
1
1
x
i
+1
=
x
истина
→
,
F
−
1
1
x
k
=
x
ложь
→
, где
x
k
— вершина в множестве
X
, соответствующая
оператору, который выполняется при ложности условия в вершине
x
i
,
либо вершина слияния потоков управления.
Шаг 6. Осуществляется исключение дублирующих передач дан-
ных. Для любой пары вершин-операторов обработки структур
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
и между ни-
ми в графе
X
не присутствует других вершин-операторов обработки
структур, использующих
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
(1)
A
как дубли-
рующая, следовательно,
XX
←
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
}
.
Шаг 7. Из множества
X
удаляются все вершины-операторы обра-
ботки структур, т.е.
X
←
X
\
X
S
, если
x
i
∈
X
S
, то
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
.
Шаг 8. Из множества
Y
удаляются все вершины, у которых од-
новременно отсутствуют инцидентные им дуги и дуги, которым они
инцидентны, т.е.
Y
←
Y
\ {
y
i
}
:
F
3
y
i
=
∅
, F
−
1
3
y
i
=
∅
,
i
= 1 :
|
Y
|
.
Шаг 9. Осуществляется перенумерация вершин в множестве
X
по
порядку, так что обозначение каждой вершины приобретает вид
x
IC
↔
i
,
а само множество
X
переходит во множество
X
IC
↔
.
Шаг 10. Осуществляется перенумерация вершин в множестве
Y
по
порядку, так что обозначение каждой вершины приобретает вид
y
pi
, а
само множество
Y
переходит во множество
Y
p
.
Шаг 11. Полученный граф является графом арифметико-логической
обработки данных примитивных типов
G
AI
←
G
(1)
A
.
Преобразование графа
G
(
2
)
A
.
Шаг 12. Пусть определено подмно-
жество
Y
S
⊂
Y
вершин-структур данных. Тогда для графа
G
(2)
A
по-
лучим подмножество вершин-операторов обработки структур данных
X
S
=
{
x
i
}
,
i
= 1 :
|
X
S
|
:
F
−
1
2
x
i
=
Y
0
, Y
0
⊂
Y
S
.
Шаг 13. Для каждой вершины
x
i
∈
X
S
, если
y
j
∈
F
2
x
i
,
y
j
∈
Y
\
Y
S
и
∃
x
k
∈
F
3
y
j
,
x
k
/
∈
X
S
, k > i
, то
X
←
X
∪ {
x
→
}
. При этом
F
1
x
i
←
F
1
x
i
∪ {
x
→
}
,
F
−
1
1
x
i
+1
←
F
−
1
1
x
i
+1
∪ {
x
→
}
и
F
−
1
2
x
→
←
y
j
. В
этом действии осуществляется вставка в граф
G
(2)
A
вершины-оператора
передачи данных примитивного типа ЦП. Вершины отправки данных
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1 121