U računarstvu, analiza kontrole toka je statička tehnika analize koda za određivanje kontrole toka programa. Kontrola toka je predstavljena preko grafa konrole toka (CFG). Termin i elaboracije, kao k-CFA, odnosi se na određene algoritme koji računaju kontrolu toka, kako za funkcionalne, tako i za objektno-orijentisane programske jezike.

Za mnoge imperativne programske jezike, kontrola toka programa je eksplicitno data u izvornom kodu programa. Kao rezultat, međuproceduralna kontrola toka obično se implicitno odnosi na tehniku statičke analize za određivanje funkcije primaoca ili poziva metoda u kompjuterskim programima napisanim na programskim jezicima višeg reda. Na primer, u programskom jeziku sa funkcijama višeg reda (npr. Scheme), ciljno mesto funkcije pozivaoca ne mora biti eksplicitno; u izolovanom izrazu

(lambda (f) (f x))

nije jasno na koju proceduru može da se odnosi f . U cilju određivanja mogućih ciljnih procedura, analiza kontrole toka mora uzeti u obzir to gde dati izraz može biti pozvan i koje argumente može uzeti. Tehnike poput apstraktne interpretacije, rešavanja ograničenja i sistema kucanja mogu biti iskorišćeni za analizu kontrole toka.

Cilj analize kontrole toka jeste da nađe petlje u okviru procedure (koristeći CFG reprezentaciju), i da odredi hijerarhije ugnježdavanja petlji (koje petlje se nelaze unutar nekih drugih petlji). Ove informacije nam mogu biti korisne jer:

Neki algoritmi za alokaciju registara koriste nivoe ugnježdenosti određenih naredbi kako bi izračunali, za svaku promenljivu, 'cenu' u slučaju njenog nealociranja u registar.
U suštini, želimo da najveći trud pri optimizaciji utrošimo upravo na kod koji će se najčešće izvršavati. Prirodno je pretpostaviti da će se kod u petljama izvršavati češće od drugog koda koji se ne nalazi unutar bilo kakve petlje. Čak, štaviše, dublje ugnježden kod će se, uglavnom, izvršavati mnogo češće od koda koji je manje duboko. Takođe, neke posebne optimizacije (e.g., loop invariant code motion) zahtevaju informaciju o tome koja izračunavanja se vrše u petljama, a koja van njih.

'Napomena': Može biti lako identifikovanje petlji i ugnježdenih petlji ukoliko nam je dat izvorni kod programa, međutim, to ne mora biti toliko očigledno kada se kod transformiše u neki međukod. Takođe, ukoliko se u kodu nalazi mnoštvo goto naredbi, petlje ne mogu biti jasno vidljive čak ni u izvornom kodu.

Da bismo našli petlje, mi ćemo:

Koristiti pretragu u dubinu (Depth-first search algorithm) kako bismo pronašli povratne grane stabla
Odrediti dominatore za sve CFG čvorove. Kažemo da čvor A dominira nad čvorom B ako svi putevi koji udju u čvor B moraju da prođu i kroz A (po definiciji, svaki čvor je domiator sam sebi)

Pregled pretrage u dubinu (DFS)[уреди | уреди извор]

U cilju pronalaženja petlji, cilj pretrage u dubinu je da pronađe povratne grane CFG-a. (Napomena: Postoji nekoliko načina da se utvrdi dominator za svaki čvor. Lengauer i Tarjan su kreirali efikasan algoritam koji koji koristi brojeve čvorova CFG-a dobijenih pretragom u dubinu, tako da, ukoliko koristimo njihov nalgoritam, druga namena dfs algoritma je da dodeli svakom čvoru broj. Kako nećemo detaljisati o Lengauer-Tarjan algoritmu ovde, izostavićemo dodelu DFS brojeva u našem opisu DFS algoritma )

Kako bismo obavili dubinu u pretragu CF grafa:

korak 1: skloniti oznaku sa svakog čvora korak 2: dfs(ulaz)

gde je dfs definisan na sledeci način

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";
}

Primer: Razmotrićemo sledeći graf kontrole toka(graf 1).

Jedna moguća pretraga u dubinu grafa kontrole toka je predstavljena ispod,oznakom za povratnu granu na mestu gde su otkrivene (graf 2)

Prirodne petlje[уреди | уреди извор]

Petlja (koju zovemo i prirodna petlja) je identifikovana za svaku povratnu granu od čvora Y do čvora X tako da X dominira Z. U ovom slučaju:

X je zaglavlje petlje
telo petlje je skup čvorova N tako da:
- X dominira N, i
- postoji put N →* Y (u grafu kontrole toka) koji isključuje X

Primer: Za graf konotrole toka prikazan iznad

Povratna grana	Zaglavlje	Telo
G→E	E	F, G
H→E	E	F, H
D→C	C	D

Ako imamo zaglavlje petlje X i povratnu granu Y→X, tako da X dominira Y, možemo izračunati čvorove u telu petlje na sledeći način:

Skinuti oznaku sa svih čvorova
Označi X kao ćposećenć
Uradi DFS unazad, počevši od Y (koristeći samo posećen-neposećen oznake, nema potrebe za ću tokuć)
Svi čvorovi do kojih smo došli u ovom dfsu unazad se nalaze u telu petlje

Nesvodljivi grafovi toka[уреди | уреди извор]

Nesvodljivi grafovi kontrole toka imaju dva interesantna svojstva sa pogledom na povratne grane:

Skup povratnih grana za nesvodljivi CFG nije jedinstven (podsetimo se da dfs(n) uključuje rekurzivne pozive za svaki od n neobeleženih potomaka; za svodljiv CFG, poredak u kojem se nalaze potomci nije bitan, ali za nesvodljiv CFG taj poredak će odrediti koje grane ćemo tumačiti kao povratne)
Za svaku od ovih povratnih grana koje nisu jedinstvene, Y→X, čvor X ne dominira nad čvorom Y

Primer: Sledi prikaz kanonskog nesvdljivog grafa kontrole toka(Slika Graf 3)

Ako dfs poseti čvor B pre čvora C, tada će grana C→B biti označena kao povratna; ako, pak, poseti C pre B, tada će grana B→C biti označena kao povratna. U svakom slučaju, ni C ni B ne dominiraju jedan nad drugom.

Kao što znamo, nesvodljivi grafovi toka nisu tako česti u praksi i mogu biti transformisani u svodljive razdvajanjem čvorova. U nekim situacijama, možemo i ignorisati problem; npr. ako identifikujemo prirodne petlje u svrhu pomeranja invarijantnih izračunavanja iz petlje van petlje, zatim, ako ignorišemo petlje kao one iznad gde ciljni čvor povratne grane ne dominira nad čvorom iz kog je grana potekla, tada jednostavno nećemo uspeti da identifikujemo neke petlje, stoga, za te petlje nećemo vršiti optimizaciju (što je bezbedno, iako mođe dovesti do propuštanja prilike za optimizaciju).

Ugnježdavanje petlji[уреди | уреди извор]

Petlje sa drugačijim zaglavljima su:

izdvojena
jedna je (potpuno) ugnježdena u drugu (i.e. telo spoljne petlje obuhvata sve čvorove unutrašnje petlje)

Slede primeri: Primer1 (pogledajte sliku Graf 4):

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

Petlje
zaglavlje	telo
while(P)	svi preostali čvorovi
while(Q)	S2

Primer2 (pogledajte sliku Graf 5):

Izvorni kod while(P){

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

)

Petlje
zaglavlje	telo
while(P)	svi preostali čvorovi
do(Q)	S2, if(Q), S3, while(Q)

Petlje sa istim zaglavljem su nekada dvosmislene (i.e.,nijedna nije potpuno smeštena u drugu).CFG (slika Graf 6) (deo onoga koji smo videli ranije) je primer toga.

S obzirom da nijedna petlja nije sadržana u drugoj, bolje ih je tretirati kao pojedinačne petlje (sa zaglavljem E i telom {F, G, H}).

Petlje
zaglavlje	telo
E	F, G
E	F, H

Računanje dominatora[уреди | уреди извор]

Prisetimo se da, u svrhu identifikovanja prirodnih petlji, za svaku povratnu granu Y→X moramo utvrditi da li X dominira nad Y. Kao što smo prethodno pomenuli, postoji nekoliko načina da se odgovori na ovo pitanje. Jedan način je da iskoristimo analizu kontrole toka da , za svaki CFG čvor n, izračunamo skup čvorova koji dominiraju nad n. Druga mogućnost je d aiskoristimo Lengauer/Tarjan algoritam (oblavljen u TOPLAS 79), koji, za svaki CFG čvor n, računa n's (prvi sledeći) dominator, zatim, da iskoristimo tu informaciju da odgovorimo na sledeće pitanje: Da li čvor X dominira čvorom Y?

Metod #1(analiza kontrole toka):

Ako koristimo analizu kontrole toka da računamo dominatore, tada želimo n.prethodni da bude skup čvorova koji su dominatori nad n, isključujući sam čvor n i n.sledeći da budu svi dominatori čvora n. Primer: U predstojećem CFG, svakom čvoru je pridružen njegov skup "prethodni" (svi dominatori tekućeg čvora bez njega samog).

Sledi definicija analize dominatora, korišćenjem grafa rešetke ():

svaki element rešetke je skup CFG čvorova
operator susreta predstavlja presek skupova
funkcije kontrole toka su iste za sve čvorove: fn(S) = S unija{n}

Ova tehnika računanja dominatora ima sledeće prednosti:

Konceptualno je jednostavna i jednostavna za implementaciju. Za svaki čvor n računa sve njegove dominatore. Ali ima i sledeće mane: Može zahtevati dosta prostora(ukoliko su skupovi dominatora veliki). Postoji velika verovatnoća da se nađe mnoštvo duplikata(skup dominatora nekog čvora je vrlo verovatno identičan skupu dominatora svojih suseda) vešta implementacija može ovo uzeti u svoju korist, da se reši duplikata i time uštedi prostor. Vremenska složenost u najgorem slučaju je O(N3), gde je N broj čvorova u grafu kontrole toka. (U praksi, složenost je znatno manja.) Razlog ovome je to što broj puta u kojim je obradjen jedan čvor mođe biti jeste visina rešetke. Visina rešetke je N, tako da, u najgorem slučaju, će svaki čvor biti obradjen N puta što nas dovodi do konačnog zbira od O(N2) "obrada čvorova". Obrada jednog čvora uključuje i računanje prolaska kroz sve potomke koji se nalaze posle tih prethodnika. Operacija susreta je presek skupova, što, u najgorem slučaju, troši O(N) vremena. Tako dolazimo do konačnog rezultata za vremensku složenost pri najgorem scenariju koja iznosi O(N3).

Metod #2 (Lengauer i Tarjan): Lengauer/Tarjan algoritam pronalazi neposredni dominator (ne i potpun skup dominatora ) za svaki čvor, koji nije ulazni (čiji skup dominatora sadrži uvek isključivo samog sebe). Definicija: A je neposredni dominator čvora B ako za svaka dva čvora A i B važi: -A != B -čvor A dominira nad B -za svaki čvor C takav da C != B i C dominira nad B, C dominira nad A Na primer:

  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

Lengauer/Tarjan algoritam ima dve implementacije: Direktnija implementacija se izvršava u vremenu od O(E*log( N)) , gde E predstavlja broj grana u CFGu i N je broj čvorova u CFGu. Nešto komplikovanija implementacija se izvršava u O(E*alpha(E, N)) vremenu, gde je alfa inverz Ackermannove funkcije, tako alfa(E, N) je vrlo mala konstanta za sve razumne vrednosti E i N (tako dobijamo linearnu implementaciju).

Koristeći informacije dobijene Lengauer/Tarjan algoritmom (za svaki čvor n, njegov neposredni dominator), možemo odgovoriti na pitanje: Da li čvor X dominira nad Y? (pitanje na koje moramo da odgovorimo kako bismo rekli da li povratna grana Y→X implicira postojanje prirodne petlje):

Koristimo infrmaciju o neposrednom dominatoru kako bismo izgradili drvo dominatora (postoji grana n→m u drvetu, ukoliko je čvor n neposredni dominator čvora m).

Spustimo se niz stablo dominatora KLD(pre-order) i LDK(post-order)obilaskom, dajući svakom čvoru KLD I LDK broj.

Sa datim brojevima, kako za, tako i za obilazak, čvor X dominira čvor Y (za različite čvorove X i Y) ako za oba od sledećih važi: KLD(X) < KLD(Y), i LDK(Y) < LDK(X)

Sledi primer:

        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