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

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

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

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

Содержание

  • 1 Определение
  • 2 Пример
  • 3 Достижимость
  • 4 Взаимосвязь доминирования
  • 5 Особые границы
  • 6 Управление циклом
  • 7 Сводимость
  • 8 Связность цикла
  • 9 График межпроцедурного управления
  • 10 См. Также
  • 11 Ссылки
  • 12 Внешние ссылки

Определение

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

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

outdegree (A)>1 или indegree (B)>1 (или оба).

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

Пример

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

0: (A) t0 = read_num 1: (A) если t0 mod 2 == 0 2: (B) print t0 + "четное". 3: (B) goto 5 4: (C) выведите 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.

Reachability

Reachability - это свойство графа, полезное при оптимизации.

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

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

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

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

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

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

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

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

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

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

Специальные ребра

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

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

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

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

Управление циклом

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

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

Сводимость

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

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

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

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

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

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

Связность петли использовалась для объяснения временной сложности анализа потока данных.

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

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

.

См. Также

Ссылки

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

Викискладе есть носители, связанные с График потока управления.
Exa mples
Последняя правка сделана 2021-05-15 11:05:59
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте