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

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

Прості графи потоку

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

• точка, на яку виконується перехід, є першою інструкцією в базовому блоці, і
• базовий блок завершується інструкцією переходу.

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

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

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

Примітки

1. Анализ потока управления в открытой распараллеливающей системе [ 1 лютого 2014 у Wayback Machine.](рос.)

Див. також

• Орієнтований граф
• Словник термінів теорії графів