Построение срезов для программ на динамических языках
7
Зависимости по управлению
проще всего определяются для ин-
терпретаторов, использующих AST-дерево: достаточно найти бли-
жайшего родителя выполняемого сейчас узла, содержащего условие
выбора той или иной ветви управления. В общем же случае потребу-
ется составлять граф потока управления (ГПУ) — ориентированный
граф, вершинами которого являются простые (линейные) блоки про-
граммы, а дуги обозначают отношение предшествия (или следова-
ния) — и определять зависимости по управлению на основе ГПУ.
Само построение ГПУ тривиально выполняется на основе любого
промежуточного представления программы, будь то AST-дерево или
байт-код.
Если поток управления структурирован, зависимости по управ-
лению никогда не пересекают границы процедур (сам вызов проце-
дуры не является зависимостью по управлению, так как не содержит
условный переход). Такие виды неструктурированной передачи
управления, как break, continue и локальный goto, также не пересека-
ют границы процедур.
Межпроцедурные зависимости по управлению возникают при
использовании механизма обработки исключений, использовании
оператора halt (который можно рассматривать как частный случай
необрабатываемого исключения) и оператора goto с переходом на
произвольное место в программе (последняя возможность отсутству-
ет в современных динамических языках). Заметим, что с точки зре-
ния ГПУ любые исключения могут возникнуть в середине линейного
блока программы и граф потока управления придется перестраивать,
даже если исключение будет обработано локально. Такую задачу
необходимо рассматривать отдельно; в данной работе мы ограничим-
ся внутрипроцедурными зависимостями по управлению и будем
строить ГПУ для отдельно взятых процедур.
С учетом возможностей кодогенерации в динамических языках
необходимо отложить составление ГПУ до того момента, когда вы-
полняемый код гарантированно будет сформирован, а именно, до
момента захода интерпретатора в процедуру. Будем предполагать,
что пока процедура выполняется, структура потока управления в ней
остается неизменной.
Процедура извлечения зависимостей по управлению из ГПУ яв-
ляется ресурсоемкой и разрабатываемый метод предполагает ее вы-
несение на этап обработки траектории, чтобы снизить нагрузку на
модифицированный интерпретатор. Сам же интерпретатор будет за-
ниматься сериализацией ГПУ для каждой процедуры, в которую он
заходит, и записью сериализованного представления в траекторию.
Простейшим сериализованным представлением ГПУ является мно-
жество дуг — пар (
o
1
,
o
2
), означающих «из оператора
o
1
возможен
