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

Из Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу
Some types of control flow graphs.svg

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

Дефиниција[уреди]

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

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

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

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

Пример[уреди]

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

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 доминатор са неколико улазних ивица, при чему су неке ивице задње ивице (дакле М је глава петље). Велику предност многим оптимизацијама представља могућност да се разбије блок М на два блока Mpre and Mloop. Садржај блока М и задњих ивица је смештен у Mloop, а остатак ивица је смештен у Mpre, и још се креира нова ивица од Mpre до Mloop (тако да Mpre је непосредни доминатор блока Mloop). На почетку, Mpre би био празан, али би га оптимизациони пролази испунили. Mpre се зове надглава петље, а Mloop је тада глава петље.

Види још[уреди]

Референце[уреди]

  1. ^ Yousefi, Javad (2015). Masking wrong-successor Control Flow Errors employing data redundancy. IEEE. стр. 201—205. doi:10.1109/ICCKE.2015.7365827. 
  2. 2,0 2,1 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. 

Литература[уреди]

  • 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. 

Спољашње везе[уреди]