Back

ⓘ Analiza živih promenljivih




                                     

ⓘ Analiza živih promenljivih

U teoriji kompajlera, analiza žive promenljive je klasična analiza protoka podataka koje izvodi kompilator za svaki tačku programa. Izvodi analizu da bi izračunao promenljive koje bi potencijalno pročitao pre sledećeg pisanja, promenljive koje su žive na izlazu iz svake tačke programa.

Ili jednostavno: promeljiva je živa ako sadrži vrednosti koje će možda biti potrebne u budućnosti.

                                     

1. Primeri

Skup živih promenljivih u liniji L3 je {b,c}, jer su oba korišćena u množenju, o time je poziv funkcije f dodeljen a. Ali skup živih promenljivih u liniji L1 je samo b kako je promenljiva c ažurirana u liniji L2. Vrednost promenljive a nije nikada korišćena. Primetimo da f može biti stanje, tako da nikada-živo dodeljivanje a može biti eliminisano, ali nemamo dovoljno informacija za odlučivanje o celini L3.

                                     

2. Izrazi u jednačini protočnosti podataka

Analiza životne sposobnosti je analiza "može unazad”. Analiza se obavlja obrnutim redosledom, i operator spajanja protoka podataka je kompletna unija. Drugim rečima, ukoliko primenimo analizu života promenljivih nad funkcijom sa posebnim brojem logičkih grana, analiza se sprovodi od kraja funkcije radeći ka početku funkcije otuda "unazad”. Promenljive će se smatrati žive ako nekoj od grana, krećući se napred u okviru funkcije, potencijalno zatreba trenutno stanje promenljive otuda "može". Ovo je kontrast u odnosu na" mora unazad” analizu koja bi umesto toga primenjuje ovo stanje na svim granama koje se kreću napred. Jednačine protoka podataka date za jednostavan blok s i postojeći blok f u analizi živih promenljivih je sledeći:

GEN =\{y\}}

Ulazno stanje u blokovima je skup promenljivih koje su žive u početku bloka. Izlazno stanje je skup promenljivih koje su žive na kraju bloka. Izlazno stanje je unija ulaznih stanja i blokova sledbenika. Funkcija prenosa izjave se primenjuje tako što se prave promenljive koje su pisano mrtve, a zatim prave promenljive koje se čitalački žive.

                                     

3. Drugi primer

Ulazno stanje b3 sadrži samo b i d, pošto je c zapisan. Izlazno stanje od b1 je unija ulaznih stanja b3 i b3. Definicija c u b3 može biti uklonjena, kako c nije živ odmah nakon iskaza.

Rešavanje jednačine protoka podataka počinje inicijalizacijom svih ulaznih stanja i izlaznih stanja u prazan skup. Radna lista je inicijalizovana ubacivanjem izlazne tačke b3 u radnu listutipično za povratnni tok. Račun ulazna stanja različit od prethodnih, pa tako njeni prethodnici b1 i b2 su ubačeni i proces se nastavlja. Progres je sumiran u sledećoj tabeli:

Primetimo da je b1 ušao u listu pre b2, zbog čega se prinudno b1 dva puta obradio b1 je ponovo unet kao predak b1. Ubacivanjm b1 pre b1 dozvolilo bi se ranije završavanje.

Inicijalizacija sa praznim skupom je jedna optimistična inicijalizacija: sve promenljive počinju kao mrtve. Primetimo da se izlazno stanje ne može suziti od jedne iteracije do druge, iako izlazno stanje može biti manje od ulaznog stanja. To možemo videti iz činjenice da se nakon prve iteracije izlazno stanje može samo promeniti promenom ulaznog stanja. Kako ulazno stanje počinje sa praznim skupom, može samo da raste u narednim iteracijama.