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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Прості графи потоку

Граф потоку керування (англ. control flow graph, CFG) — в теорії компіляції — множина всіх можливих шляхів виконання програми, представлених у вигляді графa.

У графі потоку керування кожний вузол (вершина) графа відповідає базовому блоку — прямолінійній ділянці коду, що не містить в собі ні операцій передачі керування, ні точок, на яке керування передається з інших частин програми. Є лише 2 винятки: точка, на яку виконується перехід, є першою інструкцією в базовому блоці, і базовий блок завершується інструкцією переходу. Спрямовані дуги використовуються в графі для представлення інструкцій переходу. Також в більшості реалізацій додано два спеціалізованих блоки : вхідний блок, через який керування входить в граф і вихідний блок, який завершує всі шляхи в даному графі.

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

За допомогою графа керування можна визначати недосяжні фрагменти коду, деякі види зациклення програм, можливість перегрупування операторів для використання можливостей процесора з оптимізації кешування пам'яті; також граф керування може використовуватися при контролі коректності оптимізуючих перетворень і при процедурному (intraprocedural) аналізі. Ще одне застосування графа керування — етап вставки функцій при побудові статичних форм з одноразовим привласненням (SSA — forms)[1].

Примітки[ред.ред. код]

Див. також[ред.ред. код]