Analiza protoka podataka

Analiza protoka podataka je tehnika za prikupljanje podataka o mogućem skupu vrednosti izračunatih u računarskom programu. Graf kontrole protoka programa se koristi za utvrđivanje onih delova programa na koje se može propagirati određena vrednost dodeljena promenljivoj. Skupljene informacije se često koriste od strane kompilatora kada optimizuju program.

Jednostavan način za izvođenje analize protoka podataka je da se podese jednačine kontrole podataka za svaki čvor grafa kontrole protoka i da se reše ponavljajući računanje izlaza iz ulaza za svaki čvor sve dok se čitav sistem ne stabilizuje, odnosno sve dok ne dostignemo fiksnu tačku. Ovaj opšti pristup je razvio Geri Kildal dok je predavao u Pomorskoj postdiplomskoj školi

Osnovni principi

Analiza protoka podataka je proces sakupljanja informacija o načinu na koji se koriste promenljive, definisane u programu. Analiza protoka podataka pokušava da prikupi određene informacije u svakom trenutku procedure. Uglavnom, dovoljno je prikupiti ove informacije na granama bazičnih blokova, s obzirom da ih je tada lako izračunati. U daljoj analizi protoka izlazno stanje bloka je funkcija ulaznog stanja bloka. Ova funkcija je kompozicija efekata iskaza u bloku. Ulazno stanje bloka je funkcija izlaznog stanja od svojih prethodnika. Ovo nam daje skup jednačina protoka podataka.

Za svaki blok b:

$out_{b}=trans_{b}(in_{b})$

$in_{b}=join_{p\in pred_{b}}(out_{p})$

U ovoj, $trans_{b}$ je transfer funkcija bloka $b$. Ona radi na ulaznom stanju $in_{b}$, dajući izlazno stanje $out_{b}$. Operacija povezivanja $join$ kombinuje izlazna stanja pretprocesora $p\in pred_{b}$, dajući ulazno stanje od $b$.

Nakon rešavanja ovog skupa jednačina, ulaz i/ili izlazna stanja blokova mogu se koristiti za izvođenje opcija (svojstava) programa kod granica bloka. Transfer funkcija svakog dela se posebno može primeniti za dobijanje informacija do tačke unutar bazičnog bloka. Svaki poseban tip analize protoka podataka ima svoju specifičnu transfer funkciju i operaciju povezivanja. Određeni problemi protoka podataka zahtevaju inverznu analizu protoka podataka. Ovo prati isti plan, osim što je transfer funkcija primenjena na izlaznom stanju dajući ulazno stanje i što operacija povezivanja radi na ulaznim stanjima potomaka kako bi dobili izlazno stanje. Ulazna tačka igra važnu ulogu: S obzirom na to da nema pretprocesore, njena ulazna stanja su dobro definisana na početku analize. Na primer, skup lokalnih promenljivih sa poznatim vrednostima je prazan. Ako graf kontrole protoka ne sadrži cikluse (ne postoje ni implicitna ni eksplicitna) rešavanje jednačina je jednosmerno. Samim tim graf kontrole protoka može biti topološki sortiran; pokrećući u redosledu ovog sortiranja, s obzirom da su prethodnici već procesirani tako da su njihova izlazna stanja dostupna. Ako graf kontrole protoka sadrži cikluse onda je potreban napredni algoritam.

Iterativni algoritam

Najčešći način rešavanja jednačina tokova podataka je korišćenje iterativnog algoritma.

Algoritam počinje aproksimacijom ulaznog stanja svakog bloka. Nakon toga se računaju izlazna stanja primenom funkcije prenosa na ulazna stanja. Kada se izračunaju izlazna stanja, ažuriraju se ulazna stanja operacijom spajanja. Ova dva poslednja koraka se ponavljaju sve dok se ne stigne do fiksne tačke, odnosno situacije u kojoj se ulazna stanja ne menjaju (a samim tim i izlazna).

Osnovni algoritam za rešavanje jednačina tokova podataka je sledeći pseudokod:

for i ← 1 to N

inicijalizuj čvor i

while (sve dok se skupovi menjaju)

for i ← 1 to N

ponovo kompajliraj skupove za čvor i

Konvergencija

Da bi bio upotrebljiv, iterativni pristup pre svega treba zapravo da postigne fiksnu tačku. Ovo se može garantovati nametanjem ograničenja na kombinaciju vrednosti stanja, funkcije prenosa i operacije spajanja. Za domen je bitno da je neki monotoni niz sa konačnom gornjom granicom. Monotonost obezbeđuje da će na svakoj iteraciji vrednost ostati ista ili će se povećavati, dok će konačna gornja granica obezbediti da ne može rasti na neodređeno vreme. Pa iz tog razloga ćemo na kraju doći do situacije gdje je T(x) = x za svako h, što je u stvari fiksna tačka.

Važnost redosleda obilaska

Na efikasnost iterativnog rešavanja jednačina protoka podataka utiče redosled obilaska u kojem se posećuju čvorovi. Štaviše, to zavisi od toga da li se jednačine protoka podataka koriste za analizu protoka podataka unapred ili unazad kroz graf kontrole protoka (GKP). Intuitivno, u problemu sa protokom podataka unapred, bilo bi najbolje da svi prethodnici bloka budu obrađeni pre samog bloka jer bi tada u iteraciji bile korišćene najnovije informacije. U nedostatku petlji moguće je napraviti takav redosled blokova da se ispravni izlazni podaci računaju obradom svakog bloka samo jednom.

U nastavku se razmatra nekoliko iterativnih redosleda za rešavanje jednačina protoka podataka:

• Slučajni redosled - Ovim iterativnim redosledom obilaska nije poznato da li jednačine protoka podataka rešavaju problem protoka unapred ili unazad. Zbog toga su performanse relativno loše u poređenju sa nekim specijalnim odnosno naprednim iterativnim redosledima.
• Postorder - Ovo je tipičan iterativni redosled obilaska za probleme protoka podataka unazad. Čvor se posećuje nakon što se završi posećivanje svih njegovih naslednika. Implementira se strategijom „prvo najdublji“.
• Obrnuti postorder - Ovo je tipičan iterativni redosled obilaska za probleme protoka podataka unapred. U ovakvom redosledu čvor se poseti pre nego što se poseti bilo koji od njegovih naslednika osim kada se dostigne naslednik sa spoljne (zadnje) strane.

Inicijalizacija

Inicijalne vrednosti ulaznih stanja su važne za dobijanje tačnih rezultata. Ako se rezultati koriste za optimizaciju kompajlera, oni bi trebalo da pruže konzervativne informacije, tj. kada se te informacije primene, program ne bi trebalo da menja semantiku. Iteracija algoritma fiksne tačke će uzimati vrednosti maksimalnih elemenata. Zato inicijalizacija svih blokova sa maksimalnim elementom nije korisna pa najmanje jedan blok počinje sa stanjem čija je vrednost manja od maksimuma. Sami detalji zavise od problema protoka podataka. Ako minimalni element predstavlja potpuno konzervativne informacije, rezultati se mogu bezbedno koristiti čak i tokom same iteracije. Fiksna tačka, u slučaju da predstavlja najtačnije moguće informacije, se dostiže pre nego što se sami rezultati mogu primeniti.

Primeri

U nastavku su primeri osobina računarskih programa koje se mogu izračunati pomoću analize protoka podataka. Osobine izračunate pomoću analize protoka podataka su obično samo aproksimacije stvarnih osobina. To je zato što analiza protoka podataka funkcioniše na strukturi grafa protoka podataka bez simulacije tačnog kontrolnog toka programa. Međutim, da bi i dalje bio koristan u praksi, algoritam za analizu protoka podataka obično je dizajniran za izračunavanje gornjih odnosno donjih aproksimacija realnih osobina programa.

Analiza unapred

Analiza dostupnih definicija računa za svaku tačku programa skup definicija koje mogu potencijalno dostići ovu tačku programa.

  if b==4 then
     a = 5;
  else 
     a = 3;
  endif
 
  if  a < 4 then
     ...

Dostupne definicije promenljive a u liniji 7 su skup dodela a = 5 u liniji 2 i a = 3 u liniji 4.

Analiza unazad

Analiza trenutne promenljive izračunava za svaku tačku programa promenljive koje mogu potencijalno biti kasnije pročitane pre njihovog sledećeg ažuriranja pisanja. Rezultat se tipično koristi kada se eliminiše mrtvi deo koda, tj gde se uklanjaju delovi koji dodeljuju promenljivama vrednosti koje se ne koristi kasnije. Izlazno stanje bloka je skup promenljivih koje su "žive" na kraju bloka. Njegovo ulazno stanje je skup promenljivih koje su "žive" na samom početku. Izlazna stanja su skupovi ulaznih stanja naslednika. Funkcija prenosa se primenjuje tako što se prvo prave promenljive koje su "mrtve" za pisanje, a zatim prave varijable koje su "žive" za čitanje.

b1: a = 3; 
    b = 5;
    d = 4;
    x = 100;
    if a > b then
b2:    c = a + b;
       d = 2;
b3: endif
    c = 4;
    return b * d + c;

Analiza unazad:

// in: {}
b1: a = 3; 
    b = 5;
    d = 4;
    x = 100; //x се касније не користи па зато није у спољном скупу {a, b,d}
    if a > b then
// out: {a, b,d}    //унија свих улазних стања наследника b1 => b2: {a, b}, и b3:{b, d}  

// in: {a, b}
b2: c = a + b;
    d = 2;
// out: {b, d}

// in: {b, d}
b3: endif
    c = 4;
    return b * d + c;
// out:{}

Ulazno stanje b3 sadrži samo b i d, budući da je c već napisan. Izlazno stanje b1 je unija ulaznih stanja b2 i b3. Definicija c promenljive u b2 se može ukloniti, jer c nije živo odmah nakon ickaza.

Rešavanje jednačina protoka podataka počinje sa inicijalizacijom svih ulaznih i izlaznih stanja u prazne skupove. Radna lista se inicijalizuje ubacivanjem izlaznog stanja (b3) (ovo je tipično za protok unazad). Njegova računanja ulaznih stanja se razlikuju od prethodnih; prethodnici b1 i b2 su ubačeni pa se proces nastavlja i on je sumiran u donjoj tabeli.

obrada	izlazno stanje	staro ulazno stanje	novo ulazno stanje	radna lista
b3	{}	{}	{b, d}	(b1, b2)
b1	{b, d}	{}	{}	(b2)
b2	{b, d}	{}	{a, b}	(b1)
b1	{a, b,d}	{}	{}	()

Imajte na umu da je b1 unet u listu pre b2, čime je b1 dvaput obrađeno (b1 je ponovo unet kao prethodnik b1). Ubacivanje b2 pre b1 bi omogućilo ranije izvršavanje.

Inicijalizacija sa praznim skupom je optimistička inicijalizacija: sve promenljive počinju kao mrtve. Takođe, izlazna stanja se ne mogu smanjiti između dve iteracije, iako izlazna stanja mogu biti manja od ulaznih. Ovo se može videti iz činjenice da se posle prve iteracije izlazno stanje može promeniti samo promenom ulaznog stanja. Budući da se ulazno stanje inicijalizuje pa samim tim i počinje kao prazan skup, ono može samo rasti u daljim iteracijama.

Drugačiji pristupi

Markus Monen je 2002. godine opisao novu metodu analize protoka podataka koja ne zahteva eksplicitnu konstrukciju grafa protoka podataka, već se oslanja na apstraktnoj interpretaciji programa i održavanju radnog skupa brojača programa. U svakoj uslovnoj grani, oba opcije se dodaju u radni skup. Svaka putanja se prati sa što je moguće više instrukcija (do kraja programa ili dok ima promena), a zatim se uklone iz skupa nakon čega se poziva sledeći brojač programa. Kombinacija analize protoka i analize toka podataka se pokazala kao veoma korisna i komplementarna u identifikaciji kohezivnih delova izvornog koda implementirajući funkcionalnosti sistema (npr. karakteristike, zahtevi).

Literatura

• Cooper, Keith D.; Torczon, Linda (2003) [2002-01-01]. Engineering a Compiler. Morgan Kaufmann. ISBN 978-1-55860-698-2. 
• Muchnick, Steven Stanley (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers. ISBN 978-1-55860-320-2. 
• Hecht, Matthew S. (1977). Flow Analysis of Computer Programs. Programming Languages Series. 5. Elsevier North-Holland Inc. ISBN 978-0-444-00210-5. 
• Khedker, Uday P.; Sanyal, Amitabha; Karkare, Bageshri (2009). Data Flow Analysis: Theory and Practice. CRC Press (Taylor and Francis Group). 
• Nielson, Flemming; Nielson, Hanne Riis; Hankin, Chris (2005). Principles of Program Analysis. Springer Science+Business Media.