Анализа зависности

Из Википедије, слободне енциклопедије
Emblem-important-yellow.svg Ова страница би требало да спада у једну или више категорија.
Молимо вас да је категоришете како би могла да се повеже са сличним страницама.
Уклоните ову поруку након категоризације странице.

У теорији компајлирања, анализа зависности даје ред извршења ограничен између израза/инструкција. Уопштено говорећи, израз S2 зависи од S1 ако S1 мора да се изврши пре S2. Уопштено, постоје две класе зависности - контролна зависност и зависност података.

Анализа зависности одређује да ли је или није сигурно да преуреди или да парализује изразе.

Анализа зависности[уреди]

Анализа зависности је ситуација у којој се изврши инструкција програма уколико су претходне инструкције процењене на начин који дозвољава њихово извршавање. Следи пример такве једне анализе зависности:

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

У овом примеру, S2 се покреће једино ако је услов у S1 погрешан.

Зависност података[уреди]

Зависност података проистиче из два израза која приступају или модификују исти ресурс.

Проточна(Стварна) зависност[уреди]

Израз S2 је проточна зависност на S1 (пише се S1\ \delta^f\ S2) ако и само ако S1 модификује ресурс који S2 чита и у извршавању S1 претходи S2. Следи пример проточне(стварне) зависности (RAW: Read After Write):

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

Антизависност[уреди]

Израз S2 је антизависан на S1 (пише се S1\ \delta^a\ S2) ако и само ако S2 модификује ресурс који S1 чита и у извршавању S1 претходи S2. Следи један пример антизависности (WAR: Write After Read):

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

Овде, S2 поставља вредност коју има y, али S1 чита претходну вредност од y.

Излазна зависност[уреди]

Израз S2 је излазна зависност на S1 (пише се S1\ \delta^o\ S2) ако и само ако S1 и S2 модификују исти ресурс и у извршавању S1 претходи S2. Следи један пример излазне зависности (WAW: Write After Write):

S1       x := 10
S2       x := 20

Овде, и S2 и S1 постављају променљиву x.

Улазна зависност[уреди]

Израз S2 је улазна зависност за S1 (пише се S1\ \delta^i\ S2) ако и само ако S1 и S2 читају исти ресурс и у извршавању S1 претходиS2. Следи један пример зависности улаза (RAR: Read-After-Read):

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

Овде, и S2 и S1 приступају променљивој x. Ова зависност не забрањује преуређивање.

Зависност петље[уреди]

Проблем израчунавања зависности унутар петље, што је значајан и нетривијални проблем, решава се помоћу анализе зависности петље, који проширује оквир зависности који је дат овде.

Види још[уреди]


Литература[уреди]

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