График потока управления - Control-flow graph

Некоторые примеры CFG:
(а) если-то-еще
(б) цикл while
(c) естественная петля с двумя выходами, например в то время как с if ... разрывом посередине; неструктурированный, но сводимый
(d) неприводимый CFG: цикл с двумя точками входа, например перейти в цикл while или for

В Информатика, а граф потока управления (CFG) это представление, с помощью график обозначение всех путей, которые могут быть пройдены через программа во время своего казнь. График потока управления возникает из-за Фрэнсис Э. Аллен,[1] кто отмечает это Риз Т. Проссер используемый булевы матрицы связности для анализа потока раньше.[2]

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

Определение

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

Из-за процедуры построения в CFG каждое ребро A → B обладает тем свойством, что:

превосходить (A)> 1 или степень (B)> 1 (или оба).[4]

Таким образом, CFG может быть получен, по крайней мере, концептуально, исходя из (полного) графа потока программы, т.е. граф, в котором каждый узел представляет отдельную инструкцию - и выполнение сжатие края для каждого ребра, которое фальсифицирует приведенный выше предикат, т. е. сужает каждое ребро, источник которого имеет единственный выход, а место назначения имеет единственный вход. Этот алгоритм, основанный на сокращении, не имеет практического значения, за исключением помощи в визуализации для понимания конструкции CFG, поскольку CFG может быть более эффективно построен непосредственно из программы с помощью сканирование основных блоков.[4]

пример

Рассмотрим следующий фрагмент кода:

0: (A) t0 = read_num1: (A) если t0 mod 2 == 02: (B) print t0 + "четное." 3: (B) goto 54: (C) print t0 + "нечетное". 5: (D) конечная программа

В приведенном выше примере у нас есть 4 основных блока: A от 0 до 1, B от 2 до 3, C на 4 и D на 5. В частности, в этом случае A - это «блок входа», D - «блок выхода». ", а строки 4 и 5 - это цели прыжка. Граф для этого фрагмента имеет ребра от A до B, от A до C, от B до D и от C до D.

Достижимость

Основная статья: Достижимость

Достижимость - свойство графика, полезное при оптимизации.

Если подграф не связан с подграфом, содержащим входной блок, этот подграф недоступен во время любого выполнения, и поэтому недостижимый код; в нормальных условиях его можно безопасно удалить.

Если блок выхода недоступен из блока входа, бесконечная петля может существовать. Не все бесконечные циклы обнаруживаются, см. Проблема с остановкой. Там также может существовать приказ об остановке.

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

Отношения доминирования

Основная статья: Доминатор (теория графов)

Блок М доминирует блок N, если каждый путь от входа, который достигает блока N, должен проходить через блок M. Блок входа доминирует над всеми блоками.

В обратном направлении блок M постдоминирует блок N, если каждый путь от N до выхода должен проходить через блок M. Выходной блок постдоминирует со всеми блоками.

Говорят, что блок M немедленно доминирует блок N, если M доминирует над N, и нет промежуточного блока P, такого что M доминирует над P, а P доминирует над N. Другими словами, M является последним доминатором на всех путях от входа до N. Каждый блок имеет уникального непосредственного доминатора.

Точно так же есть понятие непосредственный постдоминатор, аналогично непосредственный господин.

В дерево доминирования - это вспомогательная структура данных, отображающая отношения доминирующего. Существует дуга от блока M до блока N, если M является непосредственным доминатором N. Этот граф является деревом, поскольку каждый блок имеет уникальный непосредственный доминатор. Это дерево базируется на входном блоке. Дерево доминаторов можно эффективно вычислить, используя Алгоритм Ленгауэра – Тарьяна.

А постдоминаторное дерево аналогичен дерево доминирования. Это дерево укоренено в блоке выхода.

Специальные края

А задний край - это край, указывающий на блок, который уже встречался во время (DFS ) обход графа. Задние края типичны для петель.

А критический край является ребром, которое не является ни единственным ребром, выходящим из исходного блока, ни единственным ребром, входящим в его целевой блок. Эти края должны быть Трещина: новый блок должен быть создан в середине ребра, чтобы вставлять вычисления на ребро, не затрагивая другие ребра.

An аномальный край край, назначение которого неизвестно. Обработка исключений конструкции могут их производить. Эти края обычно препятствуют оптимизации.

An невозможный край (также известный как фальшивый край) - это ребро, которое было добавлено к графу исключительно для того, чтобы сохранить свойство, согласно которому выходной блок постдоминирует со всеми блоками. Через него невозможно пройти.

Управление петлей

А заголовок цикла (иногда называют точка входа петли) является доминатором, который является целью петлеобразующего заднего края. Заголовок цикла доминирует над всеми блоками в теле цикла. Блок может быть заголовком цикла для более чем одного цикла. У цикла может быть несколько точек входа, и в этом случае у него нет «заголовка цикла».

Предположим, что блок M является доминатором с несколькими входящими ребрами, некоторые из которых являются задними ребрами (так что M - заголовок цикла). Чтобы разбить M на два блока M, полезно выполнить несколько проходов оптимизации.предварительно И мпетля. Содержимое M и задних краев перемещено в Mпетля, остальные ребра перемещаются в точку Mпредварительно, и новое ребро из Mпредварительно к Мпетля вставлен (так что Mпредварительно является непосредственным доминатором Mпетля). Вначале Mпредварительно будет пустым, но проходит как движение кода с инвариантным циклом мог заполнить его. Mпредварительно называется предварительный заголовок цикла, И мпетля будет заголовком цикла.

Сводимость

Приводимый CFG - это такой набор ребер, который можно разделить на два непересекающихся множества: передние и задние ребра, так что:[5]

Структурированное программирование языки часто проектируются так, что все производимые ими CFG могут быть сокращены, а общие операторы структурированного программирования, такие как IF, FOR, WHILE, BREAK и CONTINUE, создают сокращаемые графы. Для создания неприводимых графиков такие утверждения, как ПЕРЕЙТИ К необходимы. Неприводимые графы также могут быть получены с помощью некоторых оптимизаций компилятора.

Связность петель

Петлевая связность CFG определяется относительно заданного поиск в глубину дерево (DFST) CFG. Этот DFST должен быть основан на начальном узле и охватывать каждый узел CFG.

Ребра в CFG, которые идут от узла к одному из его предков DFST (включая его самого), называются задними ребрами.

Связность петель - это наибольшее количество задних ребер, найденных в любом безцикловом пути CFG. В приводимой CFG связность петли не зависит от выбранного DFST.[6][7]

Связность петель использовалась, чтобы рассуждать о временной сложности анализ потока данных.[6]

График межпроцедурного управления

В то время как диаграммы потока управления представляют собой поток управления отдельной процедуры, диаграммы потока управления между процедурами представляют собой поток управления целыми программами.[8]


Смотрите также

использованная литература

  1. ^ Фрэнсис Э. Аллен (Июль 1970 г.). «Анализ потока управления». Уведомления SIGPLAN. 5 (7): 1–19. Дои:10.1145/390013.808479.
  2. ^ Риз Т. Проссер (1959). «Приложения булевых матриц к анализу блок-схем». С. 133–138.
  3. ^ Юсефи, Джавад (2015). Маскирование ошибок неправильного преемника потока управления с использованием избыточности данных. IEEE. С. 201–205. Дои:10.1109 / ICCKE.2015.7365827.
  4. ^ а б Пери Л. Тарр; Александр Л. Вольф (2011). Разработка программного обеспечения: постоянный вклад Леона Дж. Остервейла. Springer Science & Business Media. п. 58. ISBN  978-3-642-19823-6.
  5. ^ http://www.cs.colostate.edu/~mstrout/CS553Fall06/slides/lecture13-control.pdf
  6. ^ а б Кам, Джон Б .; Ульман, Джеффри Д. (1976-01-01). «Анализ глобального потока данных и итерационные алгоритмы». Журнал ACM. 23 (1): 158–171. Дои:10.1145/321921.321938. ISSN  0004-5411.
  7. ^ Оффнер, Карл. «Заметки об алгоритмах графов, используемых при оптимизации компиляторов» (PDF). Получено 13 апреля 2018.
  8. ^ «Анализ потока управления» (PDF). 2016.

внешние ссылки

Примеры