Граф потока управления (англ. 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. Выходной узел постдоминирует все узлы графа.

immediate dominator — непосредственный доминатор 

Блок M непосредственно доминирует блок N если M доминирует N, и не существует иного промежуточного блока P, который бы доминировался блоком M и доминировал над блоком N. Другими словами, M — последний доминатор в любых путях от входного блока к блоку N. У каждого блока кроме входного есть единственный непосредственный доминатор.

immediate postdominator — непосредственный постдоминатор

аналог непосредственного доминатора.

dominator tree — дерево доминаторов 

вспомогательная структура данных, содержащая информацию об отношениях доминирования. Дуга от блока M к блоку N идет тогда и только тогда, если M является непосредственным доминатором N. Этот граф является деревом, поскольку любой узел имеет уникального непосредственного доминатора. Корнем дерева является входной узел. Эффективно строится при помощи алгоритма en:Lengauer-Tarjan's algorithm.

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

Аналог дерева доминаторов. Его корнем является выходной блок.

loop header — заголовок цикла 

Иногда называется точкой входа цикла — доминатор, который является назначением обратных дуг, образующих цикл. Доминирует над всеми узлами тела цикла.

loop pre-header — предзаголовок цикла 

Предположим, что блок M — доминатор с несколькими входными дугами, некоторые из которых являются обратными (таким образом, M — заголовок цикла). Для некоторых фаз оптимизации выгодно, чтобы блок M был разделен на два блока, M_pre и M_loop. Содержимое M и обратные дуги переносится в M_loop, остальные дуги переносятся на M_pre, и создается новая дуга от M_pre к M_loop (таким образом, M_pre стал непосредственным доминатором M_loop). Сразу после преобразования M_pre будет пустым, но оптимизации вроде выноса инвариантов (en:loop-invariant code motion) могут пополнить его. M_pre называется предзаголовком цикла, а M_loop стал заголовком цикла.

Примеры

Для фрагмента кода:

0: (A) t0 = read_num
1: (A) if t0 mod 2 == 0 goto 4
2: (B)   print t0 + " is odd."
3: (B)   goto 5
4: (C) print t0 + " is even."
5: (D) end program

Граф потока управления будет состоять из 4 базовых блоков: A для строк 0-1, B для строк 2-3, C для строки 4 и D для 5й строки. Граф будет иметь дуги A -> B, A -> C, B -> D, C -> D.

См. также

• Блок-схема
• Поток управления (англ.)
• Анализ потока управления (англ.)
• Диаграмма потока управления (англ.)
• Граф зависимостей

Примечания