Graf kontrole podataka
Graf kontrole podataka (GKP) je u računarstvu i informatici, koristeći notaciju grafova, reprezentacija svih puteva kroz koje je moguće proći pomoću programa, tokom njegovog izvršavanja. GKP je ključan u mnogim optimizacijama prevodioca i alatima za statičku analizu.
Definicija[uredi | uredi izvor]
U GKP-u svaki čvor grafa predstavlja bazični blok, tj. deo koda bez ikakvih skokova ili ciljeva skokova; ciljevi skokova predstavljaju početke blokova a skokovi predstavljaju krajeve blokova. Usmerene ivice (grane) se koriste za reprezentaciju skokova u kontroli toka. U većini predstavljanja, postoje dva specijalna bloka: ulazni blok, kroz koji kontrola ulazi u graf, i izlazni blok, kroz koji kontrole napuštaju graf.[1]
Zbog načina kreiranja, u GKP-u, svaka ivica A→B ima svojstvo da:
- izlazni stepen(A) > 1 ili izlazni stepen(B) > 1 (ili oba).[2]
GKP se dakle može dobiti, bar konceptualno, od punog grafa nekog programa (tj. grafa kod koga svaki čvor predstavlja individualnu instrukciju) pri primeni redukcije ivice za svaku ivicu za koju ne važi prethodno tvrđenje tj. redukcija svake ivice čiji početak ima tačno jedan izlaz i čiji kraj ima tačno jedan ulaz. Ovakav algoritam baziran na redukciji nema praktičnih primena, osim kao vizuelno pomagalo za razumevanje GKP konstrukcije, jer se GKP može mnogo efikasnije konstruisati direktno iz programa skenirajući bazične blokove.[2]
Primer[uredi | uredi izvor]
Posmatrajmo sledeći deo koda:
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
Gore vidimo 4 bazična bloka: A od 0 do 1, B od 2 do 3, C je na 4 i D je na 5. U ovom slučaju, A je "ulazni blok", D je "izlazni blok" a linije 4 i 5 su ciljevi skoka. Graf nastao od ovog fragmenta koda ima ivice od A do B, A do C, B do D i C do D.
Dostižnost[uredi | uredi izvor]
Dostižnost je svojstvo grafa koje je jako korisno u optimizaciji.
Ako podgraf nije povezan sa podgrafom koji sadrži ulazni blok, podgraf je nedostižan pri svakom pokretanju programa kao i odgovarajući deo koda; pod normalnim okolnostima, taj deo koda se može bezbedno ukloniti.
Ako pođemo od ulaznog bloka i dobijemo da je izlazni blok nedostižan, to znači da možda postoji beskonačna petlja unutar koda. Nije moguće detektovati sve beskonačne petlje. Može se desiti da u tom delu postoji i red zaustavljanja.
Nedostižan deo koda i beskonačne petlje su moguće čak i kada ih programer ne iskodira eksplicitno: optimizacije kao što su konstantna propagacija, konstantno pakovanje kao i skakanje po nitima mogu da od više bazičnih blokova naprave samo jedan, čineći da ivice nestanu sa GKP-a itd., pa i samim tim učine neke delove grafa nepovezanim.
Relacije dominantnosti[uredi | uredi izvor]
Blok M dominira (je nadmoćniji) nad blokom N ako svaki put od ulaznog bloka do bloka N mora da prođe kroz blok M. Ulazni blok dominira sve blokove.
Kažemo da blok M neposredno dominira blok N ako M dominira N, i ne postoji međublok P tako da M dominira P i P dominira N. Drugim rečima, M je poslednji dominantni blok na svim putevima od ulaznog bloka do bloka N. Svaki blok ima jedinstveni neposredni dominantni blok.
Drvo dominantnosti je pomoćna struktura podataka koja oslikava relacije dominantnosti. Postoji grana od bloka M do bloka N ako je M neposredni dominantni blok za blok N. Ovaj graf je drvo, jer svaki blok ima jedinstveni neposredni dominantni blok. Koren drveta predstavlja ulazni blok. Drvo dominantnosti se efikasno može sračunati pomoću Lenžer-Taržan-ovog algoritma.
Specijalne ivice[uredi | uredi izvor]
Zadnja ivica (eng. back edge) je ona ivica koja je povezana sa blokom koji je već posećen obilaskom grafa u dubinu. Ove ivice su karakteristične za petlje.
Kritična ivica je ona ivica koja nije niti jedina ivica koja napušta svoj izvorni blok, niti jedina ivica koja ulazi u svoj ciljni blok. Ovakve ivice moraju biti podeljene: mora se kreirati novi blok po sredini ivice, da bi se omogućila izračunavanja na ivici bez uticaja na ostale ivice.
Abnormalna ivica je ona ivica čiji je ciljni blok nepoznat. Konstrukcije za upravljanje izuzecima mogu da ih proizvedu. Često se ovakve ivice koriste pri optimizaciji.
Nemoguća ivica (poznata kao i lažna ivica) je ona ivica koja je dodata grafu jedino da omogući svojstvo da izlazni blok bude podređen svim ostalim blokovima. One se nikad ne mogu obići.
Obrada petlji[uredi | uredi izvor]
Glava petlje (često nazivan i ulazni deo petlje) je dominator (dominantan blok) koji je ujedno i cilj zadnje ivice kreirane od strane petlje. Glava petlje dominira nad svim blokovima unutar tela petlje. Blok može biti glava petlje za više od jedne petlje. Petlja može sadržati više ulaza, te u tom slučaju kažemo da ne postoji glava petlje.
Pretpostavimo da je blok M dominator sa nekoliko ulaznih ivica, pri čemu su neke ivice zadnje ivice (dakle M je glava petlje). Veliku prednost mnogim optimizacijama predstavlja mogućnost da se razbije blok M na dva bloka Mpre and Mloop. Sadržaj bloka M i zadnjih ivica je smešten u Mloop, a ostatak ivica je smešten u Mpre, i još se kreira nova ivica od Mpre do Mloop (tako da Mpre je neposredni dominator bloka Mloop). Na početku, Mpre bi bio prazan, ali bi ga optimizacioni prolazi ispunili. Mpre se zove nadglava petlje, a Mloop je tada glava petlje.
Vidi još[uredi | uredi izvor]
- Dijagram protoka podataka
- Graf
- Obilazak grafa
- Obilazak stabla
- Stablo
- Prevodilac
- Optimizacija prevodioca
Reference[uredi | uredi izvor]
- ^ Yousefi, Javad (2015). Masking wrong-successor Control Flow Errors employing data redundancy. IEEE. str. 201—205. doi:10.1109/ICCKE.2015.7365827.
- ^ a b Tarr, Peri L.; Wolf, Alexander L. (2011). Engineering of Software: The Continuing Contributions of Leon J. Osterweil. Springer Science & Business Media. str. 58. ISBN 978-3-642-19823-6.
Literatura[uredi | uredi izvor]
- Tarr, Peri L.; Wolf, Alexander L. (2011). Engineering of Software: The Continuing Contributions of Leon J. Osterweil. Springer Science & Business Media. str. 58. ISBN 978-3-642-19823-6.