В информатике граф потока управления ( CFG ) — это представление с использованием нотации графа всех путей, которые могут быть пройдены программой во время ее выполнения . Граф потока управления был открыт Фрэнсис Э. Аллен [1] , которая отметила, что Риз Т. Проссер раньше использовала логические матрицы связности для анализа потока. [2]
CFG важен для многих оптимизаций компилятора и инструментов статического анализа .
В графе потока управления каждый узел графа представляет собой базовый блок , т.е. прямолинейный фрагмент кода без каких-либо переходов или целей перехода ; Цели прыжка начинают блок, а прыжки заканчивают блок. Направленные ребра используются для обозначения скачков в потоке управления . В большинстве презентаций есть два специально обозначенных блока: входной блок , через который управление попадает в граф потока, и выходной блок , через который уходит весь поток управления. [3]
Благодаря процедуре построения в CFG каждое ребро A→B обладает свойством:
Таким образом, CFG можно получить, по крайней мере концептуально, начиная с (полного) графа потока программы — то есть графа, в котором каждый узел представляет отдельную инструкцию — и выполняя сжатие ребра для каждого ребра, которое фальсифицирует приведенный выше предикат, т. е. сжимая ребро. каждое ребро, источник которого имеет один выход и пункт назначения имеет один вход. Этот алгоритм, основанный на сокращении, не имеет практического значения, за исключением вспомогательного средства визуализации для понимания конструкции CFG, поскольку CFG можно более эффективно построить непосредственно из программы путем сканирования ее на наличие базовых блоков . [4]
Рассмотрим следующий фрагмент кода:
0: (A) t0 = номер_чтения1: (A) если t0 mod 2 == 02: (B) выведите t0 + «четно».3: (Б) перейти к 54: (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.
Достижимость — это свойство графа, полезное при оптимизации.
Если подграф не связан с подграфом, содержащим входной блок, этот подграф недоступен во время любого выполнения, как и недостижимый код ; в нормальных условиях его можно безопасно удалить.
Если выходной блок недоступен из входного блока, может существовать бесконечный цикл . Не все бесконечные циклы можно обнаружить, см. Проблема остановки . Там также может существовать приказ об остановке.
Недостижимый код и бесконечные циклы возможны, даже если программист не запрограммировал их явно: такие оптимизации, как постоянное распространение и константное свертывание с последующим переходом в потоки , могут свернуть несколько базовых блоков в один, привести к удалению ребер из 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 и задних ребер перемещается в Mloop , остальные ребра перемещаются в точку Mpre , и вставляется новое ребро из Mpre в Mloop ( так что Mpre является непосредственным доминантом Mloop ). Вначале M pre будет пустым, но такие проходы, как движение кода, инвариантного к циклу, могут его заполнить. M pre называется предзаголовком цикла , а цикл M будет заголовком цикла.
Приводимая CFG — это группа с ребрами, которые можно разделить на два непересекающихся набора: передние и задние ребра, такие, что: [5]
Языки структурированного программирования часто разрабатываются таким образом, что все создаваемые ими CFG являются сокращаемыми, а общие операторы структурного программирования, такие как IF, FOR, WHILE, BREAK и CONTINUE, создают сокращаемые графы. Для создания неприводимых графов необходимы такие операторы, как GOTO . Неприводимые графы также могут быть созданы с помощью некоторых оптимизаций компилятора.
Связность контура CFG определяется относительно данного дерева поиска в глубину (DFST) CFG. Этот DFST должен базироваться на начальном узле и охватывать каждый узел CFG.
Ребра в CFG, которые проходят от узла к одному из его предков DFST (включая его самого), называются задними ребрами.
Связность петли — это наибольшее количество обратных ребер, найденных в любом бесцикловом пути CFG. В приводимой CFG связность контура не зависит от выбранного DFST. [6] [7]
Связность циклов использовалась для обоснования временной сложности анализа потока данных . [6]
В то время как графы потока управления представляют поток управления одной процедуры, межпроцедурные графы потока управления представляют поток управления целыми программами. [8]
{{cite web}}: CS1 maint: archived copy as title (link)