Analiza zavisnosti

U teoriji kompajliranja, analiza zavisnosti daje red izvršenja ograničen između izraza/instrukcija. Uopšteno govoreći, izraz S2 zavisi od S1 ako S1 mora da se izvrši pre S2. Uopšteno, postoje dve klase zavisnosti - kontrolna zavisnost i zavisnost podataka.

Analiza zavisnosti određuje da li je ili nije sigurno da preuredi ili da paralizuje izraze.

Analiza zavisnosti

Analiza zavisnosti je situacija u kojoj se izvrši instrukcija programa ukoliko su prethodne instrukcije procenjene na način koji dozvoljava njihovo izvršavanje. Sledi primer takve jedne analize zavisnosti:

S1       if x > 2 goto L1
S2       y := 3   
S3   L1: z := y + 1

U ovom primeru, S2 se pokreće jedino ako je uslov u S1 pogrešan.

Zavisnost podataka

Zavisnost podataka proističe iz dva izraza koja pristupaju ili modifikuju isti resurs.

Protočna(Stvarna) zavisnost

Izraz S2 je protočna zavisnost na S1 (piše se $S1\ \delta ^{f}\ S2$) ako i samo ako S1 modifikuje resurs koji S2 čita i u izvršavanju S1 prethodi S2. Sledi primer protočne (stvarne) zavisnosti (RAW: Read After Write):

S1       x := 10
S2       y := x + c

Antizavisnost

Izraz S2 je antizavisan na S1 (piše se $S1\ \delta ^{a}\ S2$) ako i samo ako S2 modifikuje resurs koji S1 čita i u izvršavanju S1 prethodi S2. Sledi jedan primer antizavisnosti (WAR: Write After Read):

S1       x := y + c
S2       y := 10

Ovde, S2 postavlja vrednost koju ima y, ali S1 čita prethodnu vrednost od y.

Izlazna zavisnost

Izraz S2 je izlazna zavisnost na S1 (piše se $S1\ \delta ^{o}\ S2$) ako i samo ako S1 i S2 modifikuju isti resurs i u izvršavanju S1 prethodi S2. Sledi jedan primer izlazne zavisnosti (WAW: Write After Write):

S1       x := 10
S2       x := 20

Ovde, i S2 i S1 postavljaju promenljivu x.

Ulazna zavisnost

Izraz S2 je ulazna zavisnost za S1 (piše se $S1\ \delta ^{i}\ S2$) ako i samo ako S1 i S2 čitaju isti resurs i u izvršavanju S1 prethodiS2. Sledi jedan primer zavisnosti ulaza (RAR: Read-After-Read):

S1       y := x + 3
S2       z := x + 5

Ovde, i S2 i S1 pristupaju promenljivoj x. Ova zavisnost ne zabranjuje preuređivanje.

Zavisnost petlje

Problem izračunavanja zavisnosti unutar petlje, što je značajan i netrivijalni problem, rešava se pomoću analize zavisnosti petlje, koji proširuje okvir zavisnosti koji je dat ovde.

Vidi još

• Analiza programa

Literatura

• Cooper, Keith D.; & Torczon, Linda. (2005). Engineering a Compiler. Morgan Kaufmann. ISBN 978-1-55860-698-2. 
• Kennedy, Ken & Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 978-1-55860-286-1. 
• Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 978-1-55860-320-2.