Управляющий граф: различия между версиями

'''Управляющий граф''' ([[Control flow graph]], [[Flow graph]]) — основная модель программы, представляющая в виде [[орграф|орграфа]] поток управления (систему управляющих связей) в программе; в ней сохраняется только членение программы на операторы (команды, лучи), а также информация о тождественности операторов и возможных передачах управления между операторами.

В общем случае '''управляющий граф''' — это помеченный упорядоченный [[мультиграф]] с выделенными ''[[начальная вершина|начальной вершиной]]'' (''[[вход|входом]]'') и непустым множеством ''[[конечная вершина|конечных вершин]]'' (''[[выход|выходов]]'').

и не содержит [[кратные дуги|кратных дуг]], [[вершина|вершин]] с совпадающими пометками и разных конечных вершин, т.е. '''управляющий граф''' — это орграф с выделенными ''начальной'' <math>s</math> и ''конечной'' <math>t</math> вершинами, каждая вершина которого лежит хотя

Часто без ограничения общности можно считать, что из <math>t</math> не выходит и в <math>s</math> не заходит ни одна [[дуга]] '''управляющего графа''', а из каждой вершины, отличной от <math>t</math>, выходит одна или две дуги.

* ''[[Альт]],''

* ''[[Аранжировка]],''

* ''[[Аранжируемый граф]],''

* ''[[Базисная нумерация]],''

* ''[[Гамак]],''

* ''[[Гамачное представление]],''

* ''[[Достоверные отношения частоты выполнения]],''

* ''[[Зона]],''

* ''[[Зонно-интервальное представление]],''

* ''[[Иерархия вложенных альтов]],''

* ''[[Иерархия вложенных зон]],''

* ''[[Интервал]],''

* ''[[Каркас уграфа]],''

* ''[[Крупноблочная схема программ]],''

* ''[[Линейная компонента]],''

* ''[[Линейный участок]],''

* ''[[Непосредственный обязательный преемник]],''

* ''[[Одновходовый граф|Одновходовый уграф]],''

* ''[[Разборный граф]],''

* ''[[Регуляризуемый уграф]],''

* ''[[Сводимый управляющий граф]],''

* ''[[Стандартные схемы]],''

* ''[[Схема программ]],''

* ''[[Участок повторяемости]],''

* ''[[Фактор-уграф]],''

* ''[[Фрагмент]],''

* ''[[Циклический участок]].''

 

* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.