Analiza živih promenljivih
U teoriji kompajlera, analiza žive promenljive (ili jednostavno analiza života) 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.
Primeri[уреди | уреди извор]
L1: b := 3; L2: c := 5; L3: a := f(b * c); goto L1; |
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.
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:
- : Skup promenljivih koje su korišćene u s pre bilo kakve dodele.
![{\displaystyle {\mbox{GEN}}[s]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bde42b503e6ae65f77c0c3fa767a2d0fc9b9f9a6)
- : Skup promenljivih kojima je dodeljena vrednost u s (u mnogim knjigama[појаснити], KILL(s) je takođe definisano kao skup promenljivih kojima je dodeljena vrednost u s „pre bilo kakve upotrebe“, ali to ne menja rešenje jednačine protoka podataka
![{\displaystyle {\mbox{KILL}}[s]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/843c3e280d6ed7c2e7e42c116ab3fa86cbc07e41)
![{\displaystyle {\mbox{LIVE}}_{in}[s]={\mbox{GEN}}[s]\cup ({\mbox{LIVE}}_{out}[s]-{\mbox{KILL}}[s])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/958512c2d6a2ecc66fe5b62c39a93c150142465b)
![{\displaystyle {\mbox{LIVE}}_{out}[final]={\emptyset }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f990ba9f96420541277fb79b42bec51be9a36e64)
![{\displaystyle {\mbox{LIVE}}_{out}[s]=\bigcup _{p\in succ[S]}{\mbox{LIVE}}_{in}[p]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d776b57e49909524e9cacc70e365924234637f4)
![{\displaystyle {\mbox{GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{x_{1},...,x_{n}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f5c01720a2c3843fa99038c8887eba960719607)
![{\displaystyle {\mbox{KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{y\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9f993860dfa62f1c430a9b805e8684346a1d87d)
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.
Drugi primer[уреди | уреди извор]
// ulaz: {}
b1: a = 3;
b = 5;
d = 4;
x = 100; //x neće biti korišćen kasnije, tako ni u izlaznom skupu {a,b,d}
if a > b then
// izlaz: {a,b,d} //unija svih (ulaznih) naslednika od b1 => b2 : {a,b}, i b3:{b,d}
// ulaz: {a,b}
b2: c = a + b;
d = 2;
// izlaz: {b,d}
// ulaz: {b,d}
b3: endif
c = 4;
return b * d + c;
// izlaz:{}
|
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 listu(tipič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:
| obrada | izlazno stanje | staro ulazno stanje | novo ulazno stanje | radna lista |
|---|---|---|---|---|
| {} | {} | {b,d} | (b1,b2) | |
| b1 | {b,d} | {} | {} | (b2) |
| b2 | {b,d} | {} | {a,b} | (b1) |
| b1 | {a,b,d} | {} | {} | () |
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.