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

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

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

Определение [ править ]

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

Благодаря процедуре построения в CFG каждое ребро A→B обладает свойством:

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

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

Пример [ править ]

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

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. Каждый блок имеет уникального непосредственного доминатора.

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

Дерево доминаторов — это вспомогательная структура данных, изображающая отношения доминаторов. Существует дуга от блока 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]

Прямые ребра образуют ориентированный ациклический граф , все узлы которого доступны из входного узла.
Для всех задних ребер (A, B) узел B доминирует над узлом A.

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

Петлевая связность [ править ]

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

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

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

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

Межпроцедурный управления граф потока

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

См. также [ править ]

Ссылки [ править ]

^ Фрэнсис Э. Аллен (июль 1970 г.). «Анализ потока управления». Уведомления SIGPLAN . 5 (7): 1–19. дои : 10.1145/390013.808479 .
^ Риз Т. Проссер (1959). «Применение булевых матриц для анализа блок-схем». Доклады, представленные на восточной совместной компьютерной конференции IRE-AIEE-ACM 1–3 декабря 1959 г. стр. 133–138. дои : 10.1145/1460299.1460314 .
^ Юсефи, Джавад (2015). «Маскирование ошибок потока управления неправильного преемника с использованием избыточности данных». 2015 5-я Международная конференция по компьютерным технологиям и инженерии знаний (ICCKE) . IEEE. стр. 201–205. дои : 10.1109/ICCKE.2015.7365827 . ISBN 978-1-4673-9280-8 .
^ Jump up to: Перейти обратно: ^а ^б Пери Л. Тарр; Александр Л. Вольф (2011). Разработка программного обеспечения: постоянный вклад Леона Дж. Остервейла . Springer Science & Business Media. п. 58. ИСБН 978-3-642-19823-6 .
^ «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 1 августа 2020 г. Проверено 24 марта 2018 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
^ Jump up to: Перейти обратно: ^а ^б Кам, Джон Б.; Уллман, Джеффри Д. (1 января 1976 г.). «Анализ глобальных потоков данных и итеративные алгоритмы» . Журнал АКМ . 23 (1): 158–171. дои : 10.1145/321921.321938 . ISSN 0004-5411 . S2CID 162375 .
^ Оффнер, Карл. «Заметки об алгоритмах графов, используемых при оптимизации компиляторов» (PDF) . Архивировано (PDF) из оригинала 25 июля 2008 г. Проверено 13 апреля 2018 г.
^ «Анализ потока управления» (PDF) . 2016. Архивировано (PDF) из оригинала 19 декабря 2016 г.

Внешние ссылки [ править ]

Примеры

Avrora - Инструмент построения графиков потока управления, заархивировано 25 августа 2011 г. на Wayback Machine.

[1] Фрэнсис Э. Аллен (июль 1970 г.). «Анализ потока управления». Уведомления SIGPLAN . 5 (7): 1–19. дои : 10.1145/390013.808479 .

[2] Риз Т. Проссер (1959). «Применение булевых матриц для анализа блок-схем». Доклады, представленные на восточной совместной компьютерной конференции IRE-AIEE-ACM 1–3 декабря 1959 г. стр. 133–138. дои : 10.1145/1460299.1460314 .

[3] Юсефи, Джавад (2015). «Маскирование ошибок потока управления неправильного преемника с использованием избыточности данных». 2015 5-я Международная конференция по компьютерным технологиям и инженерии знаний (ICCKE) . IEEE. стр. 201–205. дои : 10.1109/ICCKE.2015.7365827 . ISBN 978-1-4673-9280-8 .

[TarrWolf2011-4] Jump up to: Перейти обратно: ^а ^б Пери Л. Тарр; Александр Л. Вольф (2011). Разработка программного обеспечения: постоянный вклад Леона Дж. Остервейла . Springer Science & Business Media. п. 58. ИСБН 978-3-642-19823-6 .

[5] «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 1 августа 2020 г. Проверено 24 марта 2018 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[:0-6] Jump up to: Перейти обратно: ^а ^б Кам, Джон Б.; Уллман, Джеффри Д. (1 января 1976 г.). «Анализ глобальных потоков данных и итеративные алгоритмы» . Журнал АКМ . 23 (1): 158–171. дои : 10.1145/321921.321938 . ISSN 0004-5411 . S2CID 162375 .

[7] Оффнер, Карл. «Заметки об алгоритмах графов, используемых при оптимизации компиляторов» (PDF) . Архивировано (PDF) из оригинала 25 июля 2008 г. Проверено 13 апреля 2018 г.

[8] «Анализ потока управления» (PDF) . 2016. Архивировано (PDF) из оригинала 19 декабря 2016 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]