Граф потока управления (англ. control flow graph, CFG) — в теории компиляции — множество всех возможных путей исполнения программы, представленное в виде графa.
Обзор
В графе потока управления каждый узел (вершина) графа соответствует базовому блоку — прямолинейному участку кода, не содержащему в себе ни операций передачи управления, ни точек, на которые управление передается из других частей программы. Имеется лишь два исключения:
- точка, на которую выполняется переход, является первой инструкцией в базовом блоке;
- базовый блок завершается инструкцией перехода.
Направленные дуги используются в графе для представления инструкций перехода. Также, в большинстве реализаций добавлено два специализированных блока:
- входной блок, через который управление входит в граф;
- выходной блок, который завершает все пути в данном графе.
Структура CFG важна для многих оптимизаций компиляторов и для утилит статического анализа кода.
Возможны два случая: у блока или подграфа отсутствует:
- входной блок («мёртвый» код);
- выходной блок (бесконечный цикл).
Блок, не связанный со входным блоком, считается недостижимым («мёртвый» код). Достижимость[en] — одно из свойств графа, используемое при оптимизациях. Недостижимый блок может быть удалён из программы.
Блок, не связанный с выходным блоком, содержит бесконечный цикл. Полагаясь на это высказывание, удаётся обнаружить не все бесконечные циклы из-за проблемы остановки.
При выполнении оптимизаций компилятор может создавать и «мёртвый» код, и бесконечные циклы, даже если программист явно это не кодировал. Например, после выполнения свёртки констант (англ. 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.
См. также
Примечания
- ↑ Joseph Poole, NIST (1991). Метод определения a basis set of paths для тестирования программ Архивная копия от 5 июня 2009 на Wayback Machine.
- (2015) "Masking wrong-successor Control Flow Errors employing data redundancy".: 201–205, IEEE. DOI:10.1109/ICCKE.2015.7365827.
Ссылки
- The Machine-SUIF Control Flow Graph Library
- GNU Compiler Collection Internals
- Paper «Infrastructure for Profile Driven Optimizations in GCC Compiler» by Zdeněk Dvořák et al.
- Примеры
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .