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

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

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

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

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

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

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

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

Примітки

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.