DRAKON.SU

Текущее время: Вторник, 19 Март, 2024 05:29

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Граф потока управления
СообщениеДобавлено: Четверг, 08 Август, 2019 19:58 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5844
Откуда: Москва
Цитата:
Граф потока управления

Материал из Википедии — свободной энциклопедии

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


Содержание

1 Обзор
2 Терминология
3 Примеры
4 См. также
5 Примечания
6 Ссылки

Обзор

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

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

входной блок, через который управление входит в граф;
выходной блок, который завершает все пути в данном графе.
Структура 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.

См. также

Абстрактное синтаксическое дерево
Блок-схема
Дракон-схема
Порядок выполнения
Анализ потока управления
Граф зависимостей
Control-flow integrity
Диаграмма потока управления[en]
Цикломатическая сложность
SSA-представление

Примечания

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.

Примеры

https://web.archive.org/web/20080311004 ... th/cfg.htm
http://www.absint.com/aicall/gallery.htm
https://web.archive.org/web/20080427021 ... ample.html
http://compilers.cs.ucla.edu/avrora/cfg.html


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2024, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB