Граф контроле података

Граф контроле података (ГКП) је у рачунарству и информатици, користећи нотацију графова, репрезентација свих путева кроз које је могуће проћи помоћу програма, током његовог извршавања. ГКП је кључан у многим оптимизацијама преводиоца и алатима за статичку анализу.

Дефиниција

У ГКП-у сваки чвор графа представља базични блок, тј. део кода без икаквих скокова или циљева скокова; циљеви скокова представљају почетке блокова а скокови представљају крајеве блокова. Усмерене ивице (гране) се користе за репрезентацију скокова у контроли тока. У већини представљања, постоје два специјална блока: улазни блок, кроз који контрола улази у граф, и излазни блок, кроз који контроле напуштају граф.

Због начина креирања, у ГКП-у, свака ивица A→B има својство да:

излазни степен(A) > 1 или излазни степен(B) > 1 (или оба).

ГКП се дакле може добити, бар концептуално, од пуног графа неког програма (тј. графа код кога сваки чвор представља индивидуалну инструкцију) при примени редукције ивице за сваку ивицу за коју не важи претходно тврђење тј. редукција сваке ивице чији почетак има тачно један излаз и чији крај има тачно један улаз. Овакав алгоритам базиран на редукцији нема практичних примена, осим као визуелно помагало за разумевање ГКП конструкције, јер се ГКП може много ефикасније конструисати директно из програма скенирајући базичне блокове.

Пример

Посматрајмо следећи део кода:

0: (A) t0 = read_num
1: (A) if t0 mod 2 == 0
2: (B)   print t0 + " is even."
3: (B)   goto 5
4: (C) print t0 + " is odd."
5: (D) end program

Горе видимо 4 базична блока: А од 0 до 1, B од 2 до 3, C је на 4 и D је на 5. У овом случају, А је "улазни блок", D је "излазни блок" а линије 4 и 5 су циљеви скока. Граф настао од овог фрагмента кода има ивице од А до B, A до C, B до D и C до D.

Достижност

Достижност је својство графа које је јако корисно у оптимизацији.

Ако подграф није повезан са подграфом који садржи улазни блок, подграф је недостижан при сваком покретању програма као и одговарајући део кода; под нормалним околностима, тај део кода се може безбедно уклонити.

Ако пођемо од улазног блока и добијемо да је излазни блок недостижан, то значи да можда постоји бесконачна петља унутар кода. Није могуће детектовати све бесконачне петље. Може се десити да у том делу постоји и ред заустављања.

Недостижан део кода и бесконачне петље су могуће чак и када их програмер не искодира експлицитно: оптимизације као што су константна пропагација, константно паковање као и скакање по нитима могу да од више базичних блокова направе само један, чинећи да ивице нестану са ГКП-а итд., па и самим тим учине неке делове графа неповезаним.

Релације доминантности

Блок М доминира (је надмоћнији) над блоком N ако сваки пут од улазног блока до блока N мора да прође кроз блок M. Улазни блок доминира све блокове.

Кажемо да блок M непосредно доминира блок N ако М доминира N, и не постоји међублок P тако да M доминира P и P доминира N. Другим речима, М је последњи доминантни блок на свим путевима од улазног блока до блока N. Сваки блок има јединствени непосредни доминантни блок.

Дрво доминантности је помоћна структура података која осликава релације доминантности. Постоји грана од блока М до блока N ако је M непосредни доминантни блок за блок N. Овај граф је дрво, јер сваки блок има јединствени непосредни доминантни блок. Корен дрвета представља улазни блок. Дрво доминантности се ефикасно може срачунати помоћу Ленжер-Таржан-овог алгоритма.

Специјалне ивице

Задња ивица (енг. back edge) је она ивица која је повезана са блоком који је већ посећен обиласком графа у дубину. Ове ивице су карактеристичне за петље.

Критична ивица је она ивица која није нити једина ивица која напушта свој изворни блок, нити једина ивица која улази у свој циљни блок. Овакве ивице морају бити подељене: мора се креирати нови блок по средини ивице, да би се омогућила израчунавања на ивици без утицаја на остале ивице.

Абнормална ивица је она ивица чији је циљни блок непознат. Конструкције за управљање изузецима могу да их произведу. Често се овакве ивице користе при оптимизацији.

Немогућа ивица (позната као и лажна ивица) је она ивица која је додата графу једино да омогући својство да излазни блок буде подређен свим осталим блоковима. Оне се никад не могу обићи.

Обрада петљи

Глава петље (често називан и улазни део петље) је доминатор (доминантан блок) који је уједно и циљ задње ивице креиране од стране петље. Глава петље доминира над свим блоковима унутар тела петље. Блок може бити глава петље за више од једне петље. Петља може садржати више улаза, те у том случају кажемо да не постоји глава петље.

Претпоставимо да је блок M доминатор са неколико улазних ивица, при чему су неке ивице задње ивице (дакле М је глава петље). Велику предност многим оптимизацијама представља могућност да се разбије блок М на два блока M_pre and M_loop. Садржај блока М и задњих ивица је смештен у M_loop, а остатак ивица је смештен у M_pre, и још се креира нова ивица од M_pre до M_loop (тако да M_pre је непосредни доминатор блока M_loop). На почетку, M_pre би био празан, али би га оптимизациони пролази испунили. M_pre се зове надглава петље, а M_loop је тада глава петље.

Види још

• Дијаграм протока података
• Граф
• Обилазак графа
• Обилазак стабла
• Стабло
• Преводилац
• Оптимизација преводиоца

Литература

• Tarr, Peri L.; Wolf, Alexander L. (2011). Engineering of Software: The Continuing Contributions of Leon J. Osterweil. Springer Science & Business Media. стр. 58. ISBN 978-3-642-19823-6. 

Спољашње везе

• The Machine-SUIF Control Flow Graph Library
• GNU Compiler Collection Internals
• Paper "Infrastructure for Profile Driven Optimizations in GCC Compiler" by Zdeněk Dvořák et al.
• Avrora – Control Flow Graph Tool Архивирано на сајту Wayback Machine (25. август 2011)