- Граф потока управления
-
Простые графы потока управления[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.
- postdominator tree — дерево постдоминаторов
- Аналог дерева доминаторов. Его корнем является выходной блок.
- loop header — заголовок цикла
- Иногда называется точкой входа цикла — доминатор, который является назначением обратных дуг, образующих цикл. Доминирует над всеми узлами тела цикла.
- loop pre-header — предзаголовок цикла
- Предположим, что блок M — доминатор с несколькими входными дугами, некоторые из которых являются обратными (таким образом, M — заголовок цикла). Для некоторых фаз оптимизации выгодно, чтобы блок M был разделен на два блока, Mpre и Mloop. Содержимое M и обратные дуги переносится в Mloop, остальные дуги переносятся на Mpre, и создается новая дуга от Mpre к Mloop (таким образом, Mpre стал непосредственным доминатором Mloop). Сразу после преобразования Mpre будет пустым, но оптимизации вроде выноса инвариантов (en:loop-invariant code motion) могут пополнить его. Mpre называется предзаголовком цикла, а Mloop стал заголовком цикла.
Примеры
Для фрагмента кода:
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 Method to Determine a Basis Set of Paths to Perform Program Testing.
Ссылки
- 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.
- Примеры
Категория:- Теория компиляторов
Wikimedia Foundation. 2010.
