У рачунарству, анализа контроле тока је статичка техника анализе кода за одређивање контроле тока програма. Контрола тока је представљена преко графа конроле тока (ЦФГ). Термин и елаборације, као к-ЦФА, односи се на одређене алгоритме који рачунају контролу тока, како за функционалне, тако и за објектно-оријентисане програмске језике.

За многе императивне програмске језике, контрола тока програма је експлицитно дата у изворном коду програма. Као резултат, међупроцедурална контрола тока обично се имплицитно односи на технику статичке анализе за одређивање функције примаоца или позива метода у компјутерским програмима написаним на програмским језицима вишег реда. На пример, у програмском језику са функцијама вишег реда (нпр. Сцхеме), циљно место функције позиваоца не мора бити експлицитно; у изолованом изразу

(lambda (f) (f x))

није јасно на коју процедуру може да се односи f . У циљу одређивања могућих циљних процедура, анализа контроле тока мора узети у обзир то где дати израз може бити позван и које аргументе може узети. Технике попут апстрактне интерпретације, решавања ограничења и система куцања могу бити искоришћени за анализу контроле тока.

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

Неки алгоритми за алокацију регистара користе нивое угњеждености одређених наредби како би израчунали, за сваку променљиву, 'цену' у случају њеног неалоцирања у регистар.
У суштини, желимо да највећи труд при оптимизацији утрошимо управо на код који ће се најчешће извршавати. Природно је претпоставити да ће се код у петљама извршавати чешће од другог кода који се не налази унутар било какве петље. Чак, штавише, дубље угњежден код ће се, углавном, извршавати много чешће од кода који је мање дубоко. Такође, неке посебне оптимизације (е.г., лооп инвариант цоде мотион) захтевају информацију о томе која израчунавања се врше у петљама, а која ван њих.

'Напомена': Може бити лако идентификовање петљи и угњеждених петљи уколико нам је дат изворни код програма, међутим, то не мора бити толико очигледно када се код трансформише у неки међукод. Такође, уколико се у коду налази мноштво goto наредби, петље не могу бити јасно видљиве чак ни у изворном коду.

Да бисмо нашли петље, ми ћемо:

Користити претрагу у дубину (Дептх-фирст сеарцх алгоритхм) како бисмо пронашли повратне гране стабла
Одредити доминаторе за све ЦФГ чворове. Кажемо да чвор А доминира над чвором Б ако сви путеви који удју у чвор Б морају да прођу и кроз А (по дефиницији, сваки чвор је домиатор сам себи)

Преглед претраге у дубину (ДФС)[уреди | уреди извор]

У циљу проналажења петљи, циљ претраге у дубину је да пронађе повратне гране ЦФГ-а. (Напомена: Постоји неколико начина да се утврди доминатор за сваки чвор. Ленгауер и Тарјан су креирали ефикасан алгоритам који који користи бројеве чворова ЦФГ-а добијених претрагом у дубину, тако да, уколико користимо њихов налгоритам, друга намена дфс алгоритма је да додели сваком чвору број. Како нећемо детаљисати о Ленгауер-Тарјан алгоритму овде, изоставићемо доделу ДФС бројева у нашем опису ДФС алгоритма )

Како бисмо обавили дубину у претрагу ЦФ графа:

корак 1: склонити ознаку са сваког чвора корак 2: дфс(улаз)

где је дфс дефинисан на следеци начин

dfs(n) {
  označi n "u toku"
  for (svaki potomak(m) čvora n -- i.e., postoji grana n→m u CFG) {
     if (m nije označen) 
         dfs(m);
     else if (m je označen kao "u toku") 
         n→m je povratna grana;
     // else m je označen kao "završen", stoga ga ignoriši
  }
  označi n kao "završen";
}

Пример: Размотрићемо следећи граф контроле тока(граф 1).

Једна могућа претрага у дубину графа контроле тока је представљена испод,ознаком за повратну грану на месту где су откривене (граф 2)

Природне петље[уреди | уреди извор]

Петља (коју зовемо и природна петља) је идентификована за сваку повратну грану од чвора Y до чвора X тако да X доминира З. У овом случају:

X је заглавље петље
тело петље је скуп чворова Н тако да:
- X доминира Н, и
- постоји пут Н →* Y (у графу контроле тока) који искључује X

Пример: За граф конотроле тока приказан изнад

Повратна грана	Заглавље	Тело
Г→Е	Е	Ф, Г
Х→Е	Е	Ф, Х
Д→Ц	C	D

Ако имамо заглавље петље X и повратну грану Y→X, тако да X доминира Y, можемо израчунати чворове у телу петље на следећи начин:

Скинути ознаку са свих чворова
Означи X као ћпосећенћ
Уради ДФС уназад, почевши од Y (користећи само посећен-непосећен ознаке, нема потребе за ћу токућ)
Сви чворови до којих смо дошли у овом дфсу уназад се налазе у телу петље

Несводљиви графови тока[уреди | уреди извор]

Несводљиви графови контроле тока имају два интересантна својства са погледом на повратне гране:

Скуп повратних грана за несводљиви ЦФГ није јединствен (подсетимо се да дфс(н) укључује рекурзивне позиве за сваки од н необележених потомака; за сводљив ЦФГ, поредак у којем се налазе потомци није битан, али за несводљив ЦФГ тај поредак ће одредити које гране ћемо тумачити као повратне)
За сваку од ових повратних грана које нису јединствене, Y→X, чвор X не доминира над чвором Y

Пример: Следи приказ канонског несвдљивог графа контроле тока(Слика Граф 3)

Ако дфс посети чвор Б пре чвора C, тада ће грана Ц→Б бити означена као повратна; ако, пак, посети C пре Б, тада ће грана Б→Ц бити означена као повратна. У сваком случају, ни C ни Б не доминирају један над другом.

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

Угњеждавање петљи[уреди | уреди извор]

Петље са другачијим заглављима су:

издвојена
једна је (потпуно) угњеждена у другу (и.е. тело спољне петље обухвата све чворове унутрашње петље)

Следе примери: Пример1 (погледајте слику Граф 4):

 Izvorni kod     
while (P) {
        S1               
 while (Q) {  
     S2             
  }          
  S3}

Петље
заглавље	тело
wхиле(П)	сви преостали чворови
wхиле(Q)	С2

Пример2 (погледајте слику Граф 5):

Izvorni kod while(P){

  S1
  do{
     S2
     if(Q)
        break;
     S3
    }
  while(Q)

)

Петље
заглавље	тело
wхиле(П)	сви преостали чворови
до(Q)	С2, иф(Q), С3, wхиле(Q)

Петље са истим заглављем су некада двосмислене (и.е.,ниједна није потпуно смештена у другу).ЦФГ (слика Граф 6) (део онога који смо видели раније) је пример тога.

С обзиром да ниједна петља није садржана у другој, боље их је третирати као појединачне петље (са заглављем Е и телом {Ф, Г, Х}).

Петље
заглавље	тело
Е	Ф, Г
Е	Ф, Х

Рачунање доминатора[уреди | уреди извор]

Присетимо се да, у сврху идентификовања природних петљи, за сваку повратну грану Y→X морамо утврдити да ли X доминира над Y. Као што смо претходно поменули, постоји неколико начина да се одговори на ово питање. Један начин је да искористимо анализу контроле тока да , за сваки ЦФГ чвор н, израчунамо скуп чворова који доминирају над н. Друга могућност је д аискористимо Ленгауер/Тарјан алгоритам (облављен у ТОПЛАС 79), који, за сваки ЦФГ чвор н, рачуна н'с (први следећи) доминатор, затим, да искористимо ту информацију да одговоримо на следеће питање: Да ли чвор X доминира чвором Y?

Метод #1(анализа контроле тока):

Ако користимо анализу контроле тока да рачунамо доминаторе, тада желимо н.претходни да буде скуп чворова који су доминатори над н, искључујући сам чвор н и н.следећи да буду сви доминатори чвора н. Пример: У предстојећем ЦФГ, сваком чвору је придружен његов скуп "претходни" (сви доминатори текућег чвора без њега самог).

Следи дефиниција анализе доминатора, коришћењем графа решетке ():

сваки елемент решетке је скуп ЦФГ чворова
оператор сусрета представља пресек скупова
функције контроле тока су исте за све чворове: фн(С) = С унија{н}

Ова техника рачунања доминатора има следеће предности:

Концептуално је једноставна и једноставна за имплементацију. За сваки чвор н рачуна све његове доминаторе. Али има и следеће мане: Може захтевати доста простора(уколико су скупови доминатора велики). Постоји велика вероватноћа да се нађе мноштво дупликата(скуп доминатора неког чвора је врло вероватно идентичан скупу доминатора својих суседа) вешта имплементација може ово узети у своју корист, да се реши дупликата и тиме уштеди простор. Временска сложеност у најгорем случају је О(Н3), где је Н број чворова у графу контроле тока. (У пракси, сложеност је знатно мања.) Разлог овоме је то што број пута у којим је обрадјен један чвор мође бити јесте висина решетке. Висина решетке је Н, тако да, у најгорем случају, ће сваки чвор бити обрадјен Н пута што нас доводи до коначног збира од О(Н2) "обрада чворова". Обрада једног чвора укључује и рачунање проласка кроз све потомке који се налазе после тих претходника. Операција сусрета је пресек скупова, што, у најгорем случају, троши О(Н) времена. Тако долазимо до коначног резултата за временску сложеност при најгорем сценарију која износи О(Н3).

Метод #2 (Ленгауер и Тарјан): Ленгауер/Тарјан алгоритам проналази непосредни доминатор (не и потпун скуп доминатора ) за сваки чвор, који није улазни (чији скуп доминатора садржи увек искључиво самог себе). Дефиниција: А је непосредни доминатор чвора Б ако за свака два чвора А и Б важи: -А != Б -чвор А доминира над Б -за сваки чвор C такав да C != Б и C доминира над Б, C доминира над А На пример:

  CFG      Čvor    Dominatori       neposredni dominator
  ---	    ----    ----------	     -------------------
  ulaz      A       {ulaz,A}                ulaz
    |
    v       B       {ulaz, A, B}             A
    A
  /  \      C       {ulaz, A}                A
 v    v
B --> C     D       {ulaz, A, C}             C
      |
      v
      D

Ленгауер/Тарјан алгоритам има две имплементације: Директнија имплементација се извршава у времену од О(Е*лог( Н)) , где Е представља број грана у ЦФГу и Н је број чворова у ЦФГу. Нешто компликованија имплементација се извршава у О(Е*алпха(Е, Н)) времену, где је алфа инверз Ацкерманнове функције, тако алфа(Е, Н) је врло мала константа за све разумне вредности Е и Н (тако добијамо линеарну имплементацију).

Користећи информације добијене Ленгауер/Тарјан алгоритмом (за сваки чвор н, његов непосредни доминатор), можемо одговорити на питање: Да ли чвор X доминира над Y? (питање на које морамо да одговоримо како бисмо рекли да ли повратна грана Y→X имплицира постојање природне петље):

Користимо инфрмацију о непосредном доминатору како бисмо изградили дрво доминатора (постоји грана н→м у дрвету, уколико је чвор н непосредни доминатор чвора м).

Спустимо се низ стабло доминатора КЛД(пре-ордер) и ЛДК(пост-ордер)обиласком, дајући сваком чвору КЛД I ЛДК број.

Са датим бројевима, како за, тако и за обилазак, чвор X доминира чвор Y (за различите чворове X и Y) ако за оба од следећих важи: КЛД(X) < КЛД(Y), и ЛДК(Y) < ЛДК(X)

Следи пример:

        CFG              NEPOSREDNI DOMINATORI  DRVO DOMINATORA    PRE/POSLE
        enter		         A:  ulaz	     ulaz         ulaz:  1, 9
          |                      B:  A                |           A:     2, 8
          v		         C:  A	              v		  B:	 3, 1
          A		         D:  C	              A		  C:	 4, 3
         / \		         E:  A	            / | \	  D:	 5, 2
        v   v		         F:  E	           /  |  \	  E:	 6, 7
        B   C <--------+         G:  F            v   v   v       F:     7, 6
         \ / \         |         H:  F	          B   C   E       G:     8, 4
          v    +---->D--+                             |   |       H:     9, 5
  +-----> E <---------+                               v   v
  |       |\          |                               D   F
  |       v \         |                                  / \
  |       F  \        |                                 v   v
  |      /\   \       |                                 G   H
  |     /  \   \      |
  |    v    v   \     |
  +--- G    H --------+
                 |
                /
               v
              exit

Види још[уреди | уреди извор]

Референце[уреди | уреди извор]

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

https://web.archive.org/web/20140728203154/http://pages.cs.wisc.edu/~cs701-1/NOTES/3.CONTROL-FLOW-ANALYSIS.html фор теxтбоок интрапроцедурал ЦФА ин императиве лангуагес
https://web.archive.org/web/20140812102633/http://cs.au.dk/~jmi/Midtgaard-CSur-final.pdf ЦФА ин фунцтионал програмс (сурвеy)
http://cgi.di.uoa.gr/~smaragd/kcfa-pldi10.pdf фор тхе релатионсхип бетwеен ЦФА аналyсис ин фунцтионал лангуагес анд поинтс-то аналyсис ин императиве/ООП лангуагес