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

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

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

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

Определение

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

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

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

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

Пример

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

0: (A) t0 = read_num
1: (A) if t0 mod 2 == 0
2: (B)   print t0 + " is even."
3: (B)   goto 5
4: (C) print t0 + " is odd."
5: (D) end program

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

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

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

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

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

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

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

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

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

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

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

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

Кроме того , существует такое понятие непосредственной postdominator , аналогично немедленному Dominator .

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

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

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

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

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

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

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

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

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

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

Сводимость

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

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

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

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

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

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

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

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

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


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

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

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

Примеры