Граф потока управления | это... Что такое Граф потока управления? (original) (raw)

Простые графы потока управления[1]

Граф потока управления (англ. control flow graph, CFG) — в теории компиляции — множество всех возможных путей исполнения программы, представленное в виде графa.

Обзор

В графе потока управления каждый узел (вершина) графа соответствует базовому блоку — прямолинейному участку кода, не содержащего в себе ни операций передачи управления, ни точек, на которое управление передается из других частей программы. Имеется лишь 2 исключения: точка, на которую выполняется переход, является первой инструкцией в базовом блоке, и базовый блок завершается инструкцией перехода. Направленные дуги используются в графе для представления инструкций перехода. Также, в большинстве реализаций добавлено два специализированных блока: входной блок, через который управление входит в граф и выходной блок, который завершает все пути в данном графе.

Структура CFG крайне важна для многих оптимизаций компиляторов и для утилит статического анализа кода.

Достижимость — одно из свойств графа, используемое при оптимизациях. Если блок или подграф не имеют путей до них от входного блока, то данная часть графа является недостижимой (мертвый код) при любых вариантах исполнения, и по этой причине он может быть удален из программы. Если же из данного подграфа нет путей до выходного блока, то значит этот подграф содержит бесконечный цикл. Конечно же, не все бесконечные циклы можно обнаружить по такому признаку, см. Проблема останова.

Терминология

Нижеприведенные термины часто используются при работе с графами потока управления. Иногда в переводах вместо «доминатор» используется «обязательный предшественник».

entry block — входной блок, стартовый блок

узел, с которого начинается любой путь

exit block — выходной блок

узел, на котором завершаются все пути

back edge — обратная дуга

дуга, указывающая на предка, то есть узел, который бы был пройден раньше в процессе обхода графа в глубину

critical edge — критическая дуга

an edge which is neither the only edge leaving its source block, nor the only edge entering its destination block. These edges must be split (a new block must be created in the middle of the edge) in order to insert computations on the edge without affecting any other edges.

abnormal edge — аномальная дуга

дуга с неизвестным назначением. Могут появляться, например, после преобразования конструкций обработки исключений. Эти дуги препятствуют оптимизациям.

impossible edge — невозможная дуга

(иногда называется ложная дуга) дуга, добавленная в граф исключительно для того, чтобы сохранить свойство графа о постдоминировании выходным узлом любого другого узла. Эта дуга не может быть пройдена.

dominator — доминатор

узел M доминирует над узлом N, если любой путь, достигающий N обязан предварительно пройти блок M. Входной узел доминирует над всеми остальными узлами графа.

postdominator — постдоминатор

узел M постдоминирует над узлом N, если любой путь от N к выходному блоку обязан пройти через узел M. Выходной узел постдоминирует все узлы графа.

en:Lengauer-Tarjan's algorithm.