В информатике граф потока управления ( CFG ) — это представление , с использованием графовой нотации, всех путей, которые могут быть пройдены через программу во время ее выполнения . Граф потока управления был открыт Фрэнсис Э. Аллен , [1] которая отметила, что Риз Т. Проссер ранее использовал булевы матрицы связности для анализа потока. [2]
CFG необходим для многих оптимизаций компиляторов и инструментов статического анализа .
В графе потока управления каждый узел в графе представляет собой базовый блок , т. е. прямую последовательность кода с одной точкой входа и одной точкой выхода, где внутри блока не происходит никаких ветвей или переходов. Базовые блоки начинаются с целей перехода и заканчиваются переходами или инструкциями ветвления. Направленные ребра используются для представления переходов в потоке управления . В большинстве представлений есть два специально обозначенных блока: входной блок , через который управление входит в граф потока, и выходной блок , через который весь поток управления покидает его. [3]
В силу процедуры построения в CFG каждое ребро A→B обладает следующим свойством:
Таким образом, CFG может быть получен, по крайней мере концептуально, начиная с (полного) потокового графа программы — т. е. графа, в котором каждый узел представляет отдельную инструкцию — и выполняя сокращение ребра для каждого ребра, которое фальсифицирует предикат выше, т. е. сокращение каждого ребра, источник которого имеет один выход и назначение которого имеет один вход. Этот основанный на сокращении алгоритм не имеет практического значения, за исключением наглядного пособия для понимания конструкции CFG, поскольку CFG может быть более эффективно построен непосредственно из программы путем сканирования ее на предмет базовых блоков . [4]
Рассмотрим следующий фрагмент кода:
0: (A) t0 = read_num1: (A) если t0 mod 2 == 02: (B) вывести t0 + " четно."3: (B) перейти к 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 и обратных ребер перемещается в M loop , остальные ребра перемещаются так, чтобы указывать на M pre , и вставляется новое ребро из M pre в M loop (так что M pre является непосредственным доминатором M loop ). В начале M pre будет пустым, но проходы, такие как циклически-инвариантное кодовое движение, могут заполнить его. M pre называется предварительным заголовком цикла , а M loop будет заголовком цикла.
Сократимый 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)