Analiza alijasa

Analiza alijasa je tehnika u teoriji kompajlera, koja se koristi za određivanje da li se lokaciji za skladištenje može pristupiti na više načina. Za dva pokazivača se kaže da su alijasi ako ukazuju na istu lokaciju.

Tehnike analize alijasa se obično klasifikuju po osetljivosti protoka i osetljivosti konteksta. One mogu odrediti može biti alijas (may-alias) ili mora biti alijas (must-alias) informacije. Termin analiza alijasa se često koristi kao sinonim za pokazivače analizatora, specifičan slučaj.

Analizatori alijasa nameravaju da naprave i izračunaju korisne informacije za razumevanje alijasa u programima.

Pregled

Generalno, analiza alijasa određuje da li ili ne zasebne memorijske reference ukazuju na isto područje memorije. Ovo omogućava kompajleru da utvrdi koje varijable u programu će biti pod uticajem izjave. Na primer, razmotrite sledeći deo koda koji pristupa članovima struktura:

p.foo = 1;
q.foo = 2;
i = p.foo + 3;

Postoje 3 moguća slučaja alijasa ovde:

1. Promenljive p i q ne mogu biti alijasi .
2. Promenljive p i q moraju biti alijasi.
3. To se ne može sa sigurnošću utvrditi u trenutku prevođenja ako su  p i q alijasi ili ne.

Ako p i q ne mogu biti alijasi, onda i = p.foo + 3; može biti promenjeno u  i = 4. Ako p i q moraju biti alijasu, onda i = p.foo + 3; može biti promenjeno u  i = 5. U oba slučaja, omogućeno nam je da izvodimo optimizacije pomoću znanja alijasa. Sa druge strane, ako se ne zna da li su p i q alijasi ili ne, onda nijedna optimizacija ne može biti izvedena i ceo kod mora biti izvršen da bi se dobio rezultat. Za 2 reference memorije se kaže da imaju may-alijas relaciju ako je njihov alijas nepoznat.

Predstavljanje analiza alijasa

U analizi alijasa, delimo memoriju programa u klase alijasa. Klase alijasa su razdvojeni skupovi lokacija koje ne mogu biti alijas jedni drugima. Za raspravu ovde, pretpostavlja se da se optimizacije urađene ovde javljaju na niskom nivou srednjeg predstavljanja programa. Za ovo se kaže da je program sastavljen u binarne operacije, skače, kreće se između registara, kreće od registara do memorije, kreće iz memorije do registara, grana, i funkcija pozivi / povratak.

Analize alijasa zasnovane na tipovima

Ako je jezik koji se sastavio  tipa bezbedan, ček kompajlerskog tipa je ispravan, a jezik nema sposobnost da stvori pokazivače koji upućuju na lokalne promenljive, (kao što su ML, Haskell, ili Java) onda se mogu upućivati neke korisne optimizacije. Postoje mnogi slučajevi u kojima znamo da  dve memorijske lokacije moraju biti u različitim klasama alijasa:

1. Dve promenljive različitih tipova ne mogu biti u istoj klasi alijasa jer je vlasništvo snažno određeno, memorije bez pozivanja (tj. pozivanja na memorijskim lokacijama ne mogu biti direktno menjana) jezika tako da dve promenljive različitih tipova ne mogu istovremeno da dele istu memorijsku lokaciju.
2. Izdvajanja lokalnih na trenutni stek okvir ne mogu biti u istoj klasi alijasa kao i bilo koja prethodna raspodela iz drugog stek okvira. To je slučaj, jer nova memorijska izdvajanja moraju biti razdvojena od svih drugih memorijskih izdvajanja.
3. Svaki zapis polja od svake vrste zapisa ima svoju klasu alijasa, generalno, jer disciplina kucanja dozvoljava obično samo evidenciju iste vrste alijasa. Pošto će svi zapisi o tipu biti čuvani u identičnom formatu u memoriji, polje može biti alijas samo sebi.
4. Slično tome, svaki spektar datog tipa ima svoj klasu alijasa.

Kada se izvodi analiza alijasa za kod, svako učitavanje i skladištenje na memoriju treba biti označeno sa svojom klasom. Onda imamo korisnu osobinu, koja daje lokacije memorije $A_{i}$ i $B_{j}$ sa $i,j$ klasama alijasa, tako da ako je $i=j$ onda $A_{i}$ may-alijas $B_{j}$, i ako $i\neq j$ onda lokacije memorije neće biti alijas.

Analize alijasa zasnovane na toku

Analize zasnovane na toku, za razliku od analiza zasnovanih na tipu, se mogu primeniti na programe na jeziku sa referencama ili tipovima sa raspoređenim ulogama . Analize zasnovane na toku se mogu koristiti umesto ili kao dodatak analizama zasnovanim na tipu. U analizi na bazi protoka, nove klase alijasa se stvaraju za svaku dodelu lokacije u memoriji, kao i za svaku globalnu i lokalnu promenljivu čija adresa je korišćena. Reference mogu da ukažu na više od jedne vrednosti tokom vremena i taj način može biti u više od jednog alijasa klase. To znači da svaki memorijski prostor ima set alijasa klase umesto jedne alijas klase.

Vidi još

• Analiza izlaza
• Analiza pokazivača
• Analiza oblika

Literatura

• Appel, Andrew W. (1998). Modern Compiler Implementation in ML. Cambridge, UK: Cambridge University Press. ISBN 978-0-521-60764-3. 

Spoljašnje veze

• Biblioteka analize alijasa - Jednostavna S biblioteka za implementaciju analiza alijasa i magistarski rad koji daje uvod u oblast.