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

• Определение и использование CFG

  • Граф потока управления (CFG) представляет все пути выполнения программы. 
  • CFG был открыт Фрэнсис Э. Алленом и используется для оптимизации компиляторов и анализа статического кода. 

• Структура CFG

  • Каждый узел в CFG представляет базовый блок без переходов или целевых объектов. 
  • Направленные ребра используются для представления переходов в потоке управления. 
  • Существуют два специальных блока: входной и выходной. 

• Алгоритм сжатия CFG

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

• Пример CFG

  • Приведен пример фрагмента кода с четырьмя основными блоками и соответствующими ребрами. 

• Достижимость и бесконечные циклы

  • Достижимость – это свойство CFG, полезное для оптимизации. 
  • Бесконечные циклы могут быть обнаружены, но не все из них могут быть обнаружены. 
  • Существуют приказы об остановке, которые могут привести к бесконечным циклам. 

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

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

• Специальные ребра и управление циклом

  • Заднее ребро указывает на блок, который был обнаружен во время DFS. 
  • Критическое ребро соединяет блоки, которые не являются единственными выходами или входами. 
  • Аномальное ребро имеет неизвестное назначение. 
  • Заголовок цикла – это доминант, который является целью заднего края, образующего цикл. 
  • Цикл может иметь несколько точек входа, и в этом случае у него нет “заголовка цикла”. 

• Уменьшаемость и связность контура

  • Сводимая CFG имеет ребра, которые могут быть разделены на передние и задние. 
  • Циклическая связность определяется относительно дерева поиска в глубину. 
  • Петлевая связность – это наибольшее количество задних ребер в любом контуре CFG. 

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

  • Графики потоков управления между процедурами представляют поток управления всей программой. 

• Ссылки и дополнительные ресурсы

  • Статья содержит ссылки на внешние ресурсы и инструменты для работы с CFG.