Граф потока управления

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

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

Обзор

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

  • точка, на которую выполняется переход, является первой инструкцией в базовом блоке;
  • базовый блок завершается инструкцией перехода.

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

  • входной блок, через который управление входит в граф;
  • выходной блок, который завершает все пути в данном графе.

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

Возможны два случая: у блока или подграфа отсутствует:

Блок, не связанный со входным блоком, считается недостижимым («мёртвый» код). Достижимость — одно из свойств графа, используемое при оптимизациях. Недостижимый блок может быть удалён из программы.

Блок, не связанный с выходным блоком, содержит бесконечный цикл. Полагаясь на это высказывание, удаётся обнаружить не все бесконечные циклы из-за проблемы остановки.

При выполнении оптимизаций компилятор может создавать и «мёртвый» код, и бесконечные циклы, даже если программист явно это не кодировал. Например, после выполнения свёртки констант (англ. constant folding) и распространения констант (англ. constant propagation) оптимизация jump threading может соединить несколько блоков в один; в результате некоторые ребра могут исчезнуть и некоторые блоки могут оказаться не связанными с графом.

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

Приведённые ниже термины часто используются при работе с графами потока управления.

Edge
направленное ребро (или дуга), соединяющее блоки графа.
Entry block, входной блок, стартовый блок
блок, с которого начинается любой путь.
Exit block, выходной блок
блок, которым заканчивается любой путь.
Back edge
ребро, указывающее на предыдущий блок, то есть блок, который бы был пройден раньше в процессе обхода графа в глубину.
Critical edge
ребро, исходящее из блока с несколькими исходящими рёбрами и входящее в блок с несколькими входящими рёбрами.
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. Структура данных является деревом, поскольку любой блок имеет уникального непосредственного доминатора. Корнем дерева является входной узел. Для построения используется эффективный алгоритм Lengauer-Tarjan’s.
Postdominator tree, дерево постдоминаторов
аналог дерева доминаторов, но для постдоминаторов. Корнем дерева является выходной блок.
Loop header, заголовок цикла, точка входа цикла
блок, соединённый ребрами со всеми блоками тела цикла. Блок доминирует над всеми узлами тела цикла.
Loop pre-header, предзаголовок цикла
блок, соединённый ребром с блоком loop header; непосредственный доминатор для точки входа цикла. Пусть блок M — точка входа цикла. Для некоторых фаз оптимизации выгодно, чтобы блок M был разделён на два блока: Mpre (предзаголовок цикла) и Mloop (заголовок цикла). После разделения блока M его содержимое и обратные рёбра переносятся в блок Mloop, а остальные рёбра — в блок Mpre; затем создаётся новое ребро, соединяющее блок Mpre с блоком Mloop; таким образом блок Mpre становится непосредственным доминатором блока Mloop. Блок Mpre не будет содержать кода, пока некоторые оптимизации, например, вынос инвариантов (англ.) (англ. loop-invariant code motion), не пополнят его содержимое.

Примеры

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

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.

См. также

Примечания
  1. Joseph Poole, NIST (1991). Метод определения a basis set of paths для тестирования программ Архивная копия от 5 июня 2009 на Wayback Machine.

Ссылки
Примеры
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.