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

Граф потока управления ( англ. c ontrol f low g raph, CFG ) — в теории компиляции — множество всех возможных путей исполнения программы, представленное в виде графa .

Обзор

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

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

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

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

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

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

входной блок ( «мёртвый» код );
выходной блок ( бесконечный цикл ).

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

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

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

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

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

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. Структура данных является деревом, поскольку любой блок имеет уникального непосредственного доминатора. Корнем дерева является входной узел. Для построения используется эффективный алгоритм .

Postdominator tree , дерево постдоминаторов: аналог дерева доминаторов , но для постдоминаторов. Корнем дерева является выходной блок.

Loop header , заголовок цикла, точка входа цикла: блок, соединённый ребрами со всеми блоками тела цикла. Блок доминирует над всеми узлами тела цикла.

Loop pre-header , предзаголовок цикла: блок, соединённый ребром с блоком loop header ; непосредственный доминатор для точки входа цикла. Пусть блок M — точка входа цикла. Для некоторых фаз оптимизации выгодно, чтобы блок M был разделён на два блока: M _pre (предзаголовок цикла) и M _loop (заголовок цикла). После разделения блока M его содержимое и обратные рёбра переносятся в блок M _loop , а остальные рёбра — в блок M _pre ; затем создаётся новое ребро, соединяющее блок M _pre с блоком M _loop ; таким образом блок M _pre становится непосредственным доминатором блока M _loop . Блок M _pre не будет содержать кода, пока некоторые оптимизации, например, ( англ. 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.