Построение срезов для программ на динамических языках
13
подграфе процедуры введем вершину — точку входа
Entry
. Эта ин-
формация понадобится только на время составления ГПЗ.
Приведем алгоритм обработки записи траектории, имеющей вид
O
1
FUNCALL O
2
.
call_pos := O_1;
G_0 := subgraph_stack.peek();
G_1 := создать_новый_пустой_подграф();
Entry := создать_точку_входа();
добавить_вершину_в_подграф(G_0, O_1);
добавить_вершину_в_подграф(G_1, Entry);
пометить_как_вершину_вызова(O_1);
LAST_CALL_SITE(G_0) := O_1;
добавить_дугу_вызова(ENTRY(G_1) -> LAST_CALL_SITE(G_0));
subgraph_stack.push(G1);
При обработке записи
O
1
RETURN
в ГПЗ добавляется дуга воз-
врата из процедуры, ведущая из вершины вызова процедуры
(
LAST_CALL_SITE
(
G
0
)) в точку выхода из нее (собственно
O
1
). После
этого подграф вызываемой процедуры извлекается из стека.
В момент извлечения подграфа
G
1
из стека можно попытаться
найти уже построенный подграф
G
e
, идентичный извлекаемому
G
1
, и
произвести их объединение с целью сокращения объема памяти, рас-
ходуемого на хранение идентичных подграфов. Идентичность здесь
можно определить по равенству множеств дуг, исключая при этом
сравнении дуги, ведущие из вершины вызова или в нее. Объединение
подграфов сводится к замене дуг, ведущих в вершины в
G
1
, на дуги,
ведущие в идентичные вершины в подграфе
G
e
.
Построение среза.
Для построения среза необходимо наличие
составленного по описанной выше схеме графа программных зави-
симостей, а также оператора (критерия среза), для которого будет
выполнен поиск влияющих на результат его выполнения операторов.
Построение среза начинается с определения вершины или вершин
ГПЗ, соответствующих критерию среза. Затем выполняется поиск
вершин, достижимых из исходной по дугам зависимостей по данным
и управлению. При этом особым образом обрабатываются вершины
вызова процедур: при попадании в такую вершину в процессе поиска
достижимых рекурсивно запускается новый поиск в подграфе проце-
дуры, в которую ведет дуга «зависимости по возврату из процедуры»
из вершины вызова. В процессе рекурсивного поиска запрещается
переход по дугам вызова процедур, ведущим в вершины, отличные
от той, из которой был запущен поиск: этим гарантируется отсут-
ствие ложных зависимостей между разными местами вызовов одной
процедуры.
Множества достижимых вершин, найденных поиском в подграфе
основной программы и рекурсивно запущенных поисках в подграфах
